Registrace přidělení - Register allocation - Wikipedia

v optimalizace kompilátoru, přidělení registru je proces přiřazení velkého počtu cílových programů proměnné na malý počet procesor registry.

K alokaci registru může dojít přes a základní blok (přidělení místního registru), přes celou funkci /postup (přidělení globálního registru), nebo přes hranice funkcí procházející přes call-graph (přidělení meziprocesního registru). Po dokončení podle funkce / postupu konvence volání může vyžadovat vložení uložení / obnovení kolem každého call-site.

Kontext

Viz také: Překladač a Tlumočník

Zásada

Viz také: Ukládání počítačových dat a Hierarchie paměti
Různý počet skalárních registrů v nejběžnějších architekturách
Architektura32 bitů64 bitů
PAŽE1531
Intel x86816
MIPS3232
RISC-V16/3232
SPARC3131


V mnoha programovací jazyky, programátor může použít libovolný počet proměnné. Počítač umí rychle číst a psát registry v procesor, takže počítačový program běží rychleji, když v registrech CPU může být více proměnných.[1] Také někdy je přístup k registrům kódu kompaktnější, takže kód je menší a lze jej načíst rychleji, pokud používá registry spíše než paměť. Počet registrů je však omezený. Proto, když překladač překládá kód do strojového jazyka, musí se rozhodnout, jak přidělit proměnné omezenému počtu registrů v CPU.[2][3]

Ne všechny proměnné jsou při použití (nebo „live“) současně, takže po celou dobu životnosti programu lze daný registr použít k uložení různých proměnných. Dvě proměnné používané v stejný čas nelze přiřadit stejnému registru bez poškození jedné z proměnných. Pokud není dostatek registrů k uložení všech proměnných, mohou být některé proměnné přesunuty do az RAM. Tento proces se nazývá „rozlití“ registrů.[4] Po celou dobu životnosti programu může být proměnná rozlita i uložena do registrů: tato proměnná je poté považována za „rozdělenou“.[5] Přístup k RAM je podstatně pomalejší než přístup k registrům [6] a tak kompilovaný program běží pomaleji. Optimalizační kompilátor si tedy klade za cíl přiřadit registrů co nejvíce proměnných. Výška "Zaregistrujte tlak „je technický termín, který znamená, že je potřeba více rozlití a opětovného načtení; je definován Braunem a kol. jako„ počet současně živých proměnných na instrukci “.[7]

Kromě toho některé počítačové designy mezipaměti často přístupné registry. Programy lze tedy dále optimalizovat přiřazením stejného registru ke zdroji a cíli a hýbat se kdykoli je to možné. To je zvláště důležité, pokud kompilátor používá mezilehlé zastoupení jako statický formulář pro jedno přiřazení (SSA). Zejména pokud SSA není plně optimalizována, může uměle generovat další hýbat se instrukce.

Složky alokace registrů

Alokace registru tedy spočívá ve volbě umístění proměnných za běhu, tj. Uvnitř nebo vně registrů. Pokud má být proměnná uložena v registrech, musí alokátor určit, ve kterých registrech bude tato proměnná uložena. Další výzvou je nakonec určit dobu, po kterou by proměnná měla zůstat na stejném místě.

Alokátor registrů, bez ohledu na zvolenou alokační strategii, se při řešení těchto výzev může spolehnout na soubor klíčových akcí. Tyto akce lze shromáždit do několika různých kategorií:[8]

Přesunout vložení
Tato akce spočívá ve zvýšení počtu instrukcí k přesunu mezi registry, tj. Aby proměnná byla v průběhu své životnosti namísto jednoho aktivní v různých registrech. K tomu dochází v přístupu děleného živého dosahu.
Rozlití
Tato akce spočívá v uložení proměnné do paměti namísto registrů.[9]
Úkol
Tato akce spočívá v přiřazení registru k proměnné.[10]
Sloučení
Tato akce spočívá v omezení počtu tahů mezi registry, čímž se omezuje celkový počet pokynů. Například identifikací proměnné naživo napříč různými metodami a jejím uložením do jednoho registru po celou dobu její životnosti.[9]

Mnoho přístupů k alokaci registrů se optimalizuje pro jednu nebo více konkrétních kategorií akcí.

Intel 386 registrů

Běžné problémy vzniklé při přidělování registrů

Alokace registrů vyvolává několik problémů, které lze řešit (nebo jim lze zabránit) různými přístupy k alokaci registrů. Tři z nejběžnějších problémů jsou identifikovány následovně:

Aliasing
V některých architekturách může přiřazení hodnoty k jednomu registru ovlivnit hodnotu jiného: tomu se říká aliasing. Například x86 architektura má čtyři univerzální 32bitové registry, které lze také použít jako 16bitové nebo 8bitové registry.[11] V tomto případě přiřazení 32bitové hodnoty registru eax ovlivní hodnotu al registru.
Předbarvení
Tento problém slouží k vynucení přiřazení některých proměnných konkrétním registrům. Například v PowerPC konvence volání, parametry se běžně předávají v R3-R10 a návratová hodnota se předává v R3.[12]
NP-problém
Chaitin a kol. ukázal, že alokace registru je a NP-kompletní problém. Snižují zbarvení grafu problém s alokací registru problém tím, že ukazuje, že pro libovolný graf může být program sestaven tak, že alokace registru pro program (s registry představujícími uzly a strojovými registry představujícími dostupné barvy) by byla zbarvením původního grafu. Protože zbarvení grafu je problém NP-Hard a přidělení registru je v NP, dokazuje to NP-úplnost problému.[13]

Zaregistrujte techniky přidělování

K alokaci registru může dojít přes a základní blok kódu: říká se o něm, že je „místní“, a poprvé jej zmínil Horwitz a kol.[14] Jelikož základní bloky neobsahují větve, je proces alokace považován za rychlý, protože správa kontrolní tokový graf slučovací body v alokaci registru se odhalí[je zapotřebí objasnění ] časově náročná operace.[15] Předpokládá se však, že tento přístup neprodukuje tak optimalizovaný kód jako „globální“ přístup, který funguje na celé kompilační jednotce (například metodě nebo postupu).[16]

Přidělení grafu

Viz také: Barvení grafu

Alokace grafických barev je převládajícím přístupem k řešení alokace registrů.[17][18] Poprvé to navrhli Chaitin et al.[4]V tomto přístupu uzly v graf představují živé rozsahy (proměnné, dočasné, virtuální / symbolické registry), které jsou kandidáty na přidělení registrů. Hrany spojují živé rozsahy, které interferují, tj. Živé rozsahy, které jsou současně aktivní alespoň v jednom programovém bodě. Přidělení registru se poté sníží na zbarvení grafu problém, při kterém jsou barvy (registry) přiřazeny uzlům tak, že dva uzly spojené hranou nedostávají stejnou barvu.[19]

Použitím analýza živosti, lze vytvořit interferenční graf. Graf interference, což je neorientovaný graf kde uzly jsou proměnné programu, se používá k modelování, které proměnné nelze přiřadit ke stejnému registru.[20]

Zásada

Hlavní fáze v alokátoru registru pro barvení grafů ve stylu Chaitin jsou:[18]

Chaitin et al. Je iterativní barvení grafů na základě alokátoru registrů
  1. Přečíslovat: objevte informace o živém dosahu ve zdrojovém programu.
  2. Stavět: sestavte interferenční graf.
  3. Splynout: sloučí živé rozsahy neinterferujících proměnných souvisejících s pokyny pro kopírování.
  4. Náklady na únik: vypočítat náklady na únik každé proměnné. Tím se hodnotí dopad mapování proměnné na paměť na rychlost konečného programu.
  5. Zjednodušit: vytvořit uspořádání uzlů v grafu inferencí
  6. Únikový kód: vložte pokyny k rozlití, tj. načte a uložíte hodnoty pro dojíždění mezi registry a pamětí.
  7. Vybrat: přiřadit registr každé proměnné.

Nevýhody a další vylepšení

Přidělení zbarvení grafu má tři hlavní nevýhody. Nejprve se opírá o zbarvení grafu, což je NP-úplný problém, rozhodnout, které proměnné jsou rozlité. Nalezení minimálního barevného grafu je skutečně NP-úplný problém.[21] Zadruhé, pokud se nepoužívá rozdělení na živý rozsah, vypuzené proměnné se rozlévají všude: instrukce pro ukládání (respektive načítání) se vkládají co nejdříve (respektive pozdě), tj. Hned za (respektive před) definice proměnných (respektive použití). Za třetí, proměnná, která není rozlita, je po celou dobu životnosti uchovávána ve stejném registru.[22]

Na druhou stranu se jeden název registru může objevit ve více třídách registrů, kde třída je sada názvů registrů, které jsou v konkrétní roli zaměnitelné. Potom může být více názvů registrů aliasem pro jeden hardwarový registr.[23] Nakonec je zbarvení grafu agresivní technikou pro přidělování registrů, ale je výpočetně nákladné kvůli jeho použití interferenčního grafu, který může mít nejhorší velikost, která je kvadratický v počtu živých rozsahů.[24]Tradiční formulace alokace registrů grafů implicitně předpokládá jedinou banku nepřekrývajících se univerzálních registrů a nezpracovává nepravidelné architektonické prvky, jako jsou páry překrývajících se registrů, registry zvláštních účelů a více bank registrů.[25]

Jedno pozdější vylepšení přístupu k barvení grafů ve stylu Chaitin našli Briggs et al.: Nazývá se to konzervativní splynutí. Toto vylepšení přidává kritérium rozhodující, kdy lze sloučit dva živé rozsahy. Hlavně kromě požadavků na neinterferování lze sloučit dvě proměnné pouze v případě, že jejich sloučení nezpůsobí další rozlití. Briggs a kol. zavádí druhé vylepšení Chaitinových děl, což je zaujaté zbarvení. Předpjaté zbarvení se pokusí přiřadit stejnou barvu v barvení grafu živému rozsahu, který souvisí s kopírováním.[18]

Lineární skenování

Lineární skenování je dalším přístupem globálního přidělování registrů. Poprvé to navrhli Poletto et al. v roce 1999.[26] V tomto přístupu se kód nezměnil na graf. Místo toho jsou všechny proměnné lineárně skenovány, aby se určil jejich živý rozsah, představovaný jako interval. Po zjišťování živých rozsahů všech proměnných jsou intervaly procházeny chronologicky. Ačkoli by tento přechod mohl pomoci identifikovat proměnné, jejichž živé rozsahy interferují, nedochází k vytváření žádného interferenčního grafu a proměnné jsou alokovány chamtivě.[24]

Motivací pro tento přístup je rychlost; ne z hlediska doby provedení generovaného kódu, ale z hlediska času stráveného generováním kódu. Standardní přístupy k barvení grafů obvykle produkují kvalitní kód, ale mají značný význam nad hlavou,[27][28] použitý algoritmus zbarvení grafu má kvadratickou cenu.[29] Díky této funkci je lineární skenování v současné době přístup používaný v několika kompilátorech JIT, jako je Kompilátor hotspotů, V8 a Jikes RVM.[5]

Pseudo kód

Toto popisuje algoritmus, který poprvé navrhl Poletto et al.[30]

LinearScanRegisterAllocation    aktivní ← {} pro každého živý interval i, v pořadí podle rostoucího počátečního bodu dělat        ExpireOldIntervals (i) -li délka (aktivní) = R pak            SpillAtInterval (i) jiný            registrovat [i] ← registr odstraněn z fondu bezplatných registrů přidat i aktivní, seřazeno podle zvýšení koncového boduExpireOldIntervals (i)    pro každého interval j v aktivní, v pořadí rostoucího koncového bodu dělat        -li koncový bod [j] ≥ počáteční bod [i] pak            vrátit se         odstranit j z aktivního přidání registru [j] do fondu bezplatných registrůSpillAtInterval (i)    rozlit ← poslední aktivní interval -li endpoint [spill]> endpoint [i] pak        zaregistrovat [i] ← zaregistrovat [rozlití] umístění [rozlití] ← nové umístění zásobníku odebrat únik z aktivního přidání i aktivní, seřazeno podle zvýšení koncového bodu jiný        umístění [i] ← nové umístění zásobníku

Nevýhody a další vylepšení

Lineární skenování však představuje dvě hlavní nevýhody. Za prvé, kvůli svému chamtivému aspektu nebere v úvahu doživotní díry, tj. „Rozsahy, kde není potřeba hodnota proměnné“.[31][32] Kromě toho rozlitá proměnná zůstane rozlitá po celou dobu její životnosti.

Kratší živé rozsahy s přístupem SSA

Mnoho dalších výzkumných prací navázalo na algoritmus lineárního skenování Poletto. Například Traub et al. Navrhli algoritmus zvaný binpacking druhé šance, jehož cílem je generování kvalitnějšího kódu.[33][34] V tomto přístupu mají rozlité proměnné příležitost být později uloženy v registru pomocí jiného heuristický od algoritmu použitého ve standardním algoritmu lineárního skenování. Místo použití živých intervalů se algoritmus spoléhá na živé rozsahy, což znamená, že pokud je třeba rozsah rozlit, není nutné rozlit všechny ostatní rozsahy odpovídající této proměnné.

Přidělení lineárního skenování bylo také upraveno tak, aby využilo výhody Formulář SSA: vlastnosti této mezilehlé reprezentace se používají ke zjednodušení alokačního algoritmu.[35] Nejprve se zkracuje čas strávený analýzou grafu toku dat, zaměřenou na budování životních intervalů, a to zejména proto, že proměnné jsou jedinečné.[36] Následně vytváří kratší živé intervaly, protože každé nové přiřazení odpovídá novému živému intervalu.[37][38] Aby se zabránilo modelování intervalů a živých děr, Rogers ukázal zjednodušení zvané budoucí aktivní sady, které úspěšně odstranily intervaly pro 80% instrukcí [39].

Rematerializace

Viz také: Rematerializace

Problém optimálního přidělování registrů je NP-úplný. V důsledku toho kompilátoři používají heuristické techniky k přiblížení jeho řešení.

Chaitin a kol. diskutovat o několika nápadech pro zlepšení kvality rozlitého kódu. Poukazují na to, že určité hodnoty lze přepočítat jednou instrukcí a že požadovaný operand bude pro výpočet vždy k dispozici. Nazývají tyto výjimečné hodnoty „nikdy nezabité“ a berou na vědomí, že tyto hodnoty by měly být přepočítány, místo aby byly rozlity a znovu načteny. Dále poznamenávají, že nekoaleskovanou kopii nikdy nezabité hodnoty lze eliminovat jejím přepočítáním přímo do požadovaného registru.[40]

Tyto techniky se nazývají rematerializace. V praxi zahrnují možnosti rematerializace:

  • okamžité načtení celočíselných konstant a na některých strojích konstanty s plovoucí desetinnou čárkou,
  • - výpočet konstantního posunu od ukazatele rámce nebo oblasti statických dat a -
  • načítání nelokálních ukazatelů rámce z displeje.[40]

Briggs a Al rozšiřují Chaitinovu práci, aby využili možnosti rematerializace komplexních, vícehodnotných živých rozsahů. Zjistili, že každá hodnota musí být označena dostatečným množstvím informací, aby ji alokátor mohl správně zpracovat. Briggsův přístup je následující: nejprve rozdělte každý živý rozsah na hodnoty jeho komponent, poté na každou hodnotu propagujte značky rematerializace a vytvořte nové živé rozsahy z připojených hodnot se stejnými značkami.[40]

Sloučení

Viz také: Coalescing (počítačová věda)

V kontextu alokace registrů je sloučení aktem sloučení operací přesunu proměnných do proměnných přidělením těchto dvou proměnných do stejného umístění. K operaci sloučení dochází po sestavení interferenčního grafu. Jakmile jsou dva uzly sloučeny, musí získat stejnou barvu a být přiděleny ke stejnému registru, jakmile se operace kopírování stane zbytečnou.[41]

Sloučení může mít pozitivní i negativní dopad na barevnost interferenčního grafu.[9] Například jeden negativní dopad, který by splynutí mohlo mít na barevnou odvozitelnost grafu, je, když jsou dva uzly splynuty, protože výsledný uzel bude mít sjednocení okrajů těch, které se splynou.[9]Pozitivní dopad koalescence na kolorabilitu odvozeného grafu je například když uzel interferuje s oběma koalescenčními uzly, stupeň uzlu se sníží o jeden, což vede ke zlepšení celkové barevnosti interferenčního grafu.[42]

K dispozici je několik splývajících heuristik:[43]

Agresivní splynutí
to bylo poprvé představeno původním alokátorem registrů Chaitin. Tato heuristika si klade za cíl sloučit všechny neinterferující uzly související s kopírováním.[44] Z pohledu eliminace kopií má tato heuristika nejlepší výsledky.[45] Na druhou stranu, agresivní splynutí by mohlo ovlivnit barevnost odvoditelného grafu.[42]
Konzervativní sloučení
používá hlavně stejnou heuristiku jako agresivní splynutí, ale slučuje tahy tehdy a jen tehdy, pokud neohrožuje barevnost interferenčního grafu.[46]
Iterované splynutí
v danou chvíli odstraní jeden konkrétní pohyb a přitom zachová barevnost grafu.[47]
Optimistické splynutí
je založen na agresivním splynutí, ale pokud je narušena barevnost odvoditelného grafu, vzdá se co nejméně tahů.[48]

Smíšené přístupy

Hybridní alokace

Některé další přístupy k alokaci registrů neomezují pouze na jednu techniku ​​k optimalizaci využití registru. Například Cavazos et.al navrhli řešení, kde je možné použít jak lineární skenování, tak algoritmy barvení grafů.[49] V tomto přístupu se volba mezi jedním nebo druhým řešením určuje dynamicky: nejprve, a strojové učení Algoritmus se používá „offline“, to znamená ne za běhu, k vytvoření heuristické funkce, která určuje, který alokační algoritmus je třeba použít. Heuristická funkce se poté použije za běhu; ve světle chování kódu si alokátor poté může vybrat mezi jedním ze dvou dostupných algoritmů.[50]

Alokace stopového registru je nedávný přístup vyvinutý Eisl et al.[3][5] Tato technika zpracovává alokaci lokálně: spoléhá se na dynamiku profilování data k určení, které větve budou v daném regulačním vývojovém grafu nejčastěji používány. Poté odvodí sadu „stop“ (tj. Segmentů kódu), ve kterých je slučovací bod ignorován ve prospěch nejpoužívanější větve. Každá stopa je poté nezávisle zpracována alokátorem. Tento přístup lze považovat za hybridní, protože je možné použít různé algoritmy alokace registrů mezi různými stopami.[51]

Rozdělené rozdělení

Rozdělení rozdělení je další technika přidělování registrů, která kombinuje různé přístupy, obvykle považované za opačné. Například hybridní alokační techniku ​​lze považovat za rozdělenou, protože první heuristická fáze budování se provádí offline a heuristické použití se provádí online.[24] Stejným způsobem B. Diouf a kol. navrhla techniku ​​přidělování spoléhající se jak na offline, tak na online chování, konkrétně na statickou a dynamickou kompilaci.[52][53] Během fáze offline se nejprve shromáždí optimální rozlití pomocí Celočíselné lineární programování. Potom jsou živé rozsahy anotovány pomocí compressAnnotation algoritmus, který se opírá o dříve identifikovanou optimální množinu úniku. Alokace registru se provádí následně během online fáze na základě údajů shromážděných v offline fázi.[54]

V roce 2007 navrhli Bouchez a kol. Rozdělit alokaci registrů do různých fází, přičemž jedna fáze byla věnována rozlití a druhá byla věnována barvení a spojování.[55]

Srovnání mezi různými technikami

K posouzení výkonu jedné techniky přidělování registrů oproti druhé bylo použito několik metrik. Alokace registru se obvykle musí vypořádat s kompromisem mezi kvalitou kódu, tj. Kódem, který se provádí rychle, a režií analýzy, tj. Časem stráveným určováním analýzy zdrojového kódu za účelem generování kódu s optimalizovanou alokací registru. Z tohoto pohledu jsou doba provádění vygenerovaného kódu a čas strávený analýzou živosti relevantní metriky pro porovnání různých technik.[56]

Jakmile budou vybrány relevantní metriky, měl by být k dispozici kód, na který budou metriky použity, a měl by být relevantní pro daný problém, ať už tím, že odráží chování aplikace v reálném světě, nebo tím, že bude relevantní pro konkrétní problém, který chce algoritmus řešit. Novější články o alokaci registrů využívají zejména srovnávací sadu Dacapo.[57]

Viz také

Reference

  1. ^ Ditzel & McLellan 1982, str. 48.
  2. ^ Runeson & Nyström 2003, str. 242.
  3. ^ A b Eisl a kol. 2016, str. 14: 1.
  4. ^ A b Chaitin a kol. 1981, str. 47.
  5. ^ A b C Eisl a kol. 2016, str. 1.
  6. ^ „Porovnávací čísla latence v počítači / síti“. blog.morizyun.com. Citováno 8. ledna 2019.
  7. ^ Braun & Hack 2009, str. 174.
  8. ^ Koes & Goldstein 2009, str. 21.
  9. ^ A b C d Bouchez, Darte & Rastello 2007, str. 103.
  10. ^ Colombet, Brandner & Darte 2011, str. 26.
  11. ^ „Příručka pro vývojáře softwaru Intel® 64 a IA-32 Architectures, oddíl 3.4.1“ (PDF).
  12. ^ "Konvence volání 32bitové funkce PowerPC".
  13. ^ Bouchez, Darte & Rastello 2006, str. 4.
  14. ^ Horwitz a kol. 1966, str. 43.
  15. ^ Farach & Liberatore 1998, str. 566.
  16. ^ Eisl a kol. 2017, str. 92.
  17. ^ Eisl, Leopoldseder & Mössenböck 2018, str. 1.
  18. ^ A b C Briggs, Cooper & Torczon 1992, str. 316.
  19. ^ Poletto & Sarkar 1999, str. 896.
  20. ^ Runeson & Nyström 2003, str. 241.
  21. ^ Kniha 1975, str. 618–619.
  22. ^ Colombet, Brandner & Darte 2011, str. 1.
  23. ^ Smith, Ramsey & Holloway 2004, str. 277.
  24. ^ A b C Cavazos, Moss & O’Boyle 2006, str. 124.
  25. ^ Runeson & Nyström 2003, str. 240.
  26. ^ Poletto & Sarkar 1999, str. 895.
  27. ^ Poletto & Sarkar 1999, str. 902.
  28. ^ Wimmer & Mössenböck 2005, str. 132.
  29. ^ Johansson & Sagonas 2002, str. 102.
  30. ^ Poletto & Sarkar 1999, str. 899.
  31. ^ Eisl a kol. 2016, str. 2.
  32. ^ Traub, Holloway & Smith 1998, str. 143.
  33. ^ Traub, Holloway & Smith 1998, str. 141.
  34. ^ Poletto & Sarkar 1999, str. 897.
  35. ^ Wimmer & Franz 2010, str. 170.
  36. ^ Mössenböck & Pfeiffer 2002, str. 234.
  37. ^ Mössenböck & Pfeiffer 2002, str. 233.
  38. ^ Mössenböck & Pfeiffer 2002, str. 229.
  39. ^ Rogers 2020.
  40. ^ A b C Briggs, Cooper & Torczon 1992, str. 313.
  41. ^ Chaitin 1982, str. 90.
  42. ^ A b Ahn & Paek 2009, str. 7.
  43. ^ Park & ​​Moon 2004, str. 736.
  44. ^ Chaitin 1982, str. 99.
  45. ^ Park & ​​Moon 2004, str. 738.
  46. ^ Briggs, Cooper & Torczon 1994, str. 433.
  47. ^ George & Appel 1996, str. 212.
  48. ^ Park & ​​Moon 2004, str. 741.
  49. ^ Eisl a kol. 2017, str. 11.
  50. ^ Cavazos, Moss & O’Boyle 2006, str. 124-127.
  51. ^ Eisl a kol. 2016, str. 4.
  52. ^ Diouf a kol. 2010, str. 66.
  53. ^ Cohen & Rohou 2010, str. 1.
  54. ^ Diouf a kol. 2010, str. 72.
  55. ^ Bouchez, Darte & Rastello 2007, str. 1.
  56. ^ Poletto & Sarkar 1999, str. 901-910.
  57. ^ Blackburn a kol. 2006, str. 169.
  58. ^ Flajolet, Raoult a Vuillemin 1979.

Zdroje

externí odkazy