Registrera tilldelning

Fördelningen av register i kompileringsprocessen [1] är kartläggningen av en uppsättning av ett stort antal variabler av ett fragment av ett datorprogram (virtuella register av en mellanrepresentation) på, som regel, en liten uppsättning fysiska mikroprocessorer register . Registerallokering kan göras i ett enda basblock ( lokal registerallokering ) eller i hela proceduren ( global registerallokering ).

Vanligtvis måste datorprogram arbeta med stora mängder data, men de flesta mikroprocessorer stöder bara operationer på ett fast antal små "celler" som kallas register. Vissa processorer tillåter användning av operander lagrade i minnet , men åtkomst till register är mycket snabbare än åtkomst till minne (även om det angivna minnesområdet kan cachelagras ).

Problem

Registerallokeringsproblemet är NP-komplett [2] [3] . Vanligtvis är antalet variabler i ett program betydligt fler än de tillgängliga fysiska registren, så vissa variabler måste lagras på den lokala stacken. Minnesåtkomster kan minimeras genom att lagra de minst frekvent använda variablerna där, men att avgöra vilka variabler som används minst är inte alltid lätt.

Det är också värt att notera att vissa register ofta har ett system- eller tjänstesyfte och deras användning är begränsad.

Global registertilldelning

Liksom de flesta andra optimeringar baseras registertilldelningen på användning av viss analys. I det här fallet är det oftast analysen av livslängden för variabler och analysen av dataflödet.

Färgningen av inkompatibilitetsgrafen som föreslagits av matematikern Gregory Khaitin anses vara en traditionell registerallokeringsalgoritm .

Varje variabel (symboliskt register) motsvarar en grafnod . Om livstiderna för variablerna skär varandra, är motsvarande noder sammankopplade med en båge. Grafen behöver färgas med färger (där den motsvarar antalet tillgängliga fysiska register) på ett sådant sätt att inget par av närliggande noder har samma färg.

Graden av en grafnod är antalet av dess grannar. Om graden av en grafnod är mindre än , så är det alltid möjligt att hitta en färg för den som inte är tilldelad någon av grannarna. Om alla noder har en grad som är större än , lagras en av variablerna i minnet och delas upp i flera noder av mindre grad.

Tills graf G kan färgas med R-färger Ta iterativt bort alla noder i grafen med grad < R, tryck dem på stapeln Om alla noder i grafen har tagits bort kan grafen färgas med R-färger Poppa nod N från stacken och lägg till den i grafen genom att tilldela den en färg Annars kan grafen G inte färgas med R-färger Förenkla G genom att välja en nod att lagra i minnet och dela upp den i flera noder (noden som ska lagras i minnet väljs heuristiskt)

Preston Briggs föreslog att modifiera Khaitins algoritm [4] genom att skjuta upp lagring av variabeln i minnet tills färgerna tilldelas grafens noder. För vissa icke-färgbara grafer undviker detta att lagra variabler i minnet. Till exempel kan en kvadrat med noder vid hörnen färgas med färger, medan graden av alla dess noder är lika med två, och Khaitins algoritm kommer att tvingas lagra en av variablerna i minnet.


Anteckningar

  1. ↑ KÄNNA INTUIT | Föreläsning | Val av instruktioner i kodgenerering . Hämtad 28 november 2017. Arkiverad från originalet 28 juli 2021.
  2. ↑ Gregory J. Chaitin, Mark A. Auslander, Ashok K. Chandra, John Cocke, Martin E. Hopkins och Peter W. Markstein. "Registrera tilldelning via färgläggning." Computer Languages, 6:47-57, 1981  .
  3. ↑ Fernando Magno Quintão Pereira, Jens Palsberg, "Register Allocation after Classical SSA Elimination is NP-complete"  , http://pike.cs.ucla.edu/~palsberg/paper/fossacs06.pdf Arkiverad från 4 mars 2016 på Wayback Maskin
  4. ↑ Preston Briggs, Keith D. Cooper, Ken Kennedy, Linda Torczon. "Färgheuristik för registertilldelning." ACM SIGPLAN Notices, Volym 24, Issue 7, 275-284, 1989  .

Länkar