Register tildeling

Fordelingen af ​​registre i kompileringsprocessen [1] er kortlægningen af ​​et sæt af et stort antal variable af et fragment af et computerprogram (virtuelle registre af en mellemrepræsentation) på, som regel, et lille sæt fysiske mikroprocessorer registre . Registertildeling kan foretages i en enkelt basisblok ( lokal registerallokering ) eller i hele proceduren ( global registerallokering ).

Typisk skal computerprogrammer arbejde med store mængder data, men de fleste mikroprocessorer understøtter kun operationer på et fast antal små "celler" kaldet registre. Nogle processorer tillader brug af operander gemt i hukommelsen , men adgang til registre er meget hurtigere end adgang til hukommelse (selvom det angivne hukommelsesområde kan cachelagres ).

Problemer

Registertildelingsproblemet er NP-komplet [2] [3] . Typisk er antallet af variable i et program langt større end de tilgængelige fysiske registre, så nogle variabler skal gemmes på den lokale stak. Hukommelsesadgange kan minimeres ved at gemme de mindst hyppigt anvendte variable der, men det er ikke altid let at bestemme, hvilke variabler der er mindst brugt.

Det er også værd at bemærke, at nogle registre ofte har et system- eller serviceformål, og deres anvendelse er begrænset.

Global registertildeling

Som de fleste andre optimeringer er registertildeling baseret på brug af nogle analyser. I dette tilfælde er det oftest analysen af ​​variables levetid og analysen af ​​dataflow.

Farvningen af ​​inkompatibilitetsgrafen foreslået af matematikeren Gregory Khaitin anses for at være en traditionel registerallokeringsalgoritme .

Hver variabel (symbolsk register) svarer til en grafknude . Hvis variablernes levetid skærer hinanden, er de tilsvarende knudepunkter forbundet med en bue. Grafen skal farves med farver (hvor den svarer til antallet af tilgængelige fysiske registre) på en sådan måde, at intet par af naboknudepunkter har samme farve.

Graden af ​​en grafknude er antallet af dens naboer. Hvis graden af ​​en grafknude er mindre end , så er det altid muligt at finde en farve til den, som ikke er tildelt nogen af ​​naboerne. Hvis alle noder har en grad større end , lagres en af ​​variablerne i hukommelsen og opdeles i flere noder af mindre grad.

Indtil graf G kan farves med R-farver Fjern iterativt alle noder i grafen med grad < R, og skub dem ind på stakken Hvis alle knudepunkter i grafen er blevet fjernet, kan grafen farves med R-farver Pop node N fra stakken og føj den til grafen ved at tildele en farve til den Ellers kan grafen G ikke farves med R-farver Forenkle G ved at vælge en node til at gemme i hukommelsen og opdele den i flere noder (den node, der skal gemmes i hukommelsen, er valgt heuristisk)

Preston Briggs foreslog at ændre Khaitins algoritme [4] ved at udsætte lagringen af ​​variablen i hukommelsen, indtil farverne er tildelt grafens noder. For nogle grafer, der ikke kan farves, undgår dette lagring af variabler i hukommelsen. For eksempel kan en firkant med noder ved hjørnerne farves med farver, mens graden af ​​alle dens noder er lig med to, og Khaitins algoritme vil blive tvunget til at gemme en af ​​variablerne i hukommelsen.


Noter

  1. ↑ KEND INTUIT | Foredrag | Valg af instruktioner i kodegenerering . Hentet 28. november 2017. Arkiveret fra originalen 28. juli 2021.
  2. ↑ Gregory J. Chaitin, Mark A. Auslander, Ashok K. Chandra, John Cocke, Martin E. Hopkins og Peter W. Markstein. "Registrer tildeling via farvning." 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 Arkiveret fra 4. marts 2016 på Wayback Maskine
  4. ↑ Preston Briggs, Keith D. Cooper, Ken Kennedy, Linda Torczon. "Farveheuristik for registertildeling." ACM SIGPLAN-meddelelser, bind 24, udgave 7, 275-284, 1989  .

Links