Přidělení registru

Distribuce registrů v procesu kompilace [1] je mapování množiny velkého počtu proměnných fragmentu počítačového programu (virtuálních registrů zprostředkující reprezentace) na zpravidla malou množinu fyzického mikroprocesoru . registry . Přidělení registrů lze provést v jednom základním bloku ( přidělení lokálního registru ) nebo v celém postupu ( přidělení globálního registru ).

Počítačové programy musí obvykle pracovat s velkým množstvím dat, ale většina mikroprocesorů podporuje pouze operace na pevném počtu malých „buněk“ zvaných registry. Některé procesory umožňují použití operandů uložených v paměti , ale přístup k registrům je mnohem rychlejší než přístup k paměti (i když zadanou oblast paměti lze uložit do mezipaměti ).

Problémy

Problém alokace registrů je NP-úplný [2] [3] . Typicky počet proměnných v programu daleko převyšuje dostupné fyzické registry, takže některé proměnné musí být uloženy v lokálním zásobníku. Přístupy do paměti lze minimalizovat uložením nejméně často používaných proměnných, ale určit, které proměnné jsou nejméně používané, není vždy snadné.

Za zmínku také stojí, že některé registry mají často systémový nebo servisní účel a jejich použití je omezené.

Přidělení globálního registru

Stejně jako většina ostatních optimalizací je alokace registrů založena na použití nějaké analýzy. V tomto případě se nejčastěji jedná o analýzu životnosti proměnných a analýzu toku dat.

Barvení grafu nekompatibility navržené matematikem Gregorym Khaitinem je považováno za tradiční algoritmus alokace registrů .

Každá proměnná (symbolický registr) odpovídá uzlu grafu . Pokud se životnosti proměnných protínají, jsou příslušné uzly spojeny obloukem. Graf je potřeba obarvit barvami (pokud to odpovídá počtu dostupných fyzických registrů) tak, aby žádná dvojice sousedních uzlů neměla stejnou barvu.

Stupeň uzlu grafu je počet jeho sousedů. Pokud je stupeň uzlu grafu menší než , pak je vždy možné pro něj najít barvu, která není přiřazena žádnému ze sousedů. Pokud mají všechny uzly stupeň větší než , je jedna z proměnných uložena v paměti a rozdělí se na několik uzlů nižšího stupně.

Dokud nelze graf G obarvit barvami R Iterativně odstraňte všechny uzly grafu stupně < R a zatlačte je do zásobníku Pokud byly odstraněny všechny uzly grafu, lze graf vybarvit barvami R Vyjměte uzel N ze zásobníku a přidejte jej do grafu přiřazením barvy Jinak graf G nelze obarvit barvami R Zjednodušte G výběrem uzlu k uložení do paměti a jeho rozdělením do více uzlů (uzel pro uložení do paměti je vybrán heuristicky)

Preston Briggs navrhl modifikovat Khaitinův algoritmus [4] odložením uložení proměnné do paměti, dokud nebudou barvy přiřazeny uzlům grafu. U některých nevybarvitelných grafů se tím zabrání ukládání proměnných do paměti. Například čtverec s uzly ve vrcholech může být obarven barvami, přičemž stupeň všech jeho uzlů je roven dvěma a Khaitinův algoritmus bude nucen uložit jednu z proměnných do paměti.


Poznámky

  1. ↑ POZNEJ INTUIT | Přednáška | Volba pokynů při generování kódu . Získáno 28. listopadu 2017. Archivováno z originálu 28. července 2021.
  2. ↑ Gregory J. Chaitin, Mark A. Auslander, Ashok K. Chandra, John Cocke, Martin E. Hopkins a Peter W. Markstein. "Zaregistrovat přidělení pomocí vybarvení." Počítačové jazyky, 6:47-57, 1981  .
  3. ↑ Fernando Magno Quintão Pereira, Jens Palsberg, „Přidělení registrace po klasické eliminaci SSA je NP-kompletní“  , http://pike.cs.ucla.edu/~palsberg/paper/fossacs06.pdf Archivováno od 4. března 2016 na Wayback Stroj
  4. ↑ Preston Briggs, Keith D. Cooper, Ken Kennedy, Linda Torczon. "Heuristika barvení pro alokaci registru." ACM SIGPLAN Notices, svazek 24, vydání 7, 275-284, 1989  .

Odkazy