Registerallocatie
Registerallocatie is een onderdeel van het compileren van de broncode van een computerprogramma. Tijdens de registerallocatie-fase bepaalt de compiler hoe de registers in het uiteindelijke programma gebruikt worden.
Omdat voor een processor de toegang tot een register relatief snel is vergeleken met de toegang tot het geheugen heeft het de voorkeur om tijdens de uitvoering van een programma de gegevens waarmee gewerkt wordt zo veel mogelijk in registers te hebben in plaats van in het geheugen. Het aantal registers op een processor is echter beperkt (oudere processors hadden soms slechts 4 of 8 registers ter beschikking van een programma).
Het doel van registerallocatie is om op basis van gegevens over het te compileren programma een zo efficiënt mogelijk gebruik van registers te realiseren in het gecompileerde programma.
Plaats in de compiler bewerken
Registerallocatie vindt plaats nadat de compiler het bronprogramma heeft vertaald naar een interne representatie (intermediate representation, of IR). Deze IR kan een soort abstracte assembler of een syntaxisboom zijn. Hoewel de gebruikte IR per compiler verschilt, hebben ze allemaal gemeen dat de individuele instructies (de nodes in het geval van een syntaxisboom) een vrijwel één-op-één relatie hebben met de machine-instructies van de processor waarvoor gecompileerd wordt.
Dankzij deze gelijkenis tussen de IR en de te genereren instructies heeft de compiler al een goed beeld over hoe het uiteindelijke programma er uit gaat zien. Dit is noodzakelijk voor een succesvolle allocatie-strategie.
De IR maakt gebruik van een in principe oneindig aantal tijdelijke registers: iedere keer dat er een nieuw register nodig is voor een berekening wordt er een nieuw tijdelijke register gebruikt. Tijdens de registerallocatie wordt aan elk van deze tijdelijke registers een van de (echte) machineregisters toegewezen.
Doelen bewerken
De compiler probeert bij registerallocatie aan de volgende voorwaarden te voldoen:
- Zolang een register data bevat die in gebruik (live) is, wordt dit register niet voor andere data gebruikt. Zou dat namelijk wel gebeuren, dan moet de oude data eerst worden weggeschreven naar een ander register of het geheugen, en dat kost extra instructies en tijd.
- Als er in de IR data van het ene naar het andere tijdelijke register wordt verplaatst, krijgen beide tijdelijke registers indien mogelijk hetzelfde machineregister toegewezen. In zo'n geval kan de verplaats-instructie simpelweg achterwege gelaten worden.
Werkwijze bewerken
Om tot een goede registerallocatie te komen voert de compiler een liveness analysis uit. Als twee tijdelijke registers a en b niet tegelijk in gebruik zijn (live zijn), kunnen ze gebruikmaken van hetzelfde register. Gelukkig zijn er op ieder moment in een programma slechts een beperkt aantal variabelen (tijdelijke registers zijn de variabelen van de IR) in gebruik. Zijn er op sommige momenten meer variabelen live dan er machineregisters beschikbaar zijn, dan worden de overige variabelen in het geheugen gehouden (dit wordt spilling genoemd).
Om een liveness analysis uit te voeren, voert de compiler eerst een control flow-analyse uit. Dat houdt in dat de compiler alle mogelijke paden door het IR-programma vaststelt. In een programma zonder conditionele statements is dat er maar één, maar de meeste programma's hebben een groot aantal conditionele statements en dus een groot aantal mogelijke paden. Heeft de compiler eenmaal alle mogelijke paden berekend, dan kan vervolgens vastgesteld worden welke variabelen nooit tegelijk live zijn en dus hetzelfde register mogen gebruiken. Om vervolgens een semioptimale[1] registerallocatie te verkrijgen gebruikt een compiler meestal een vorm van graph coloring (graafkleuring).
Is dit gebeurd, dan heeft ieder tijdelijk register (variabele) in de IR een machineregister toegewezen gekregen en kan de compiler vervolgens machinecode genereren (code generation).
Zie ook bewerken
Bronnen, noten en/of referenties
|