Wat is Registertoewijzing (register allocation)?

Antwoord: C. Knopen zijn waarden, bogen de relatie dat ze gelijktijdig leven

In een interferentiegraaf zijn variabelen en tussenwaarden de knopen, en twee waarden die op een zeker moment beide nog worden gebruikt (leven) worden door een boog verbonden. Waarden die door een boog zijn verbonden zijn gelijktijdig nodig en kunnen niet in hetzelfde register staan. Bij k registers kan de toewijzing, als de graaf met k kleuren kan worden gekleurd zodat buren niet dezelfde kleur hebben, worden gedaan door elke kleur met een register te laten overeenkomen. Als dat niet lukt, worden sommige waarden naar het geheugen weggeschreven (spill). Het is geen graaf van de volgorde van instructies of de bedrading van registers.

Antwoord: A. Er komen instructies bij om waarden naar de stack weg te schrijven en terug te lezen, waardoor het gemakkelijk trager wordt

Een spill is het in het geheugen (op de stack) plaatsen van sommige waarden wanneer er meer gelijktijdig levende waarden zijn dan registers. Bij elk gebruik van zo'n waarde is een leesinstructie nodig en bij elke wijziging een schrijfinstructie, zodat het aantal instructies toeneemt en het door de geheugentoegangen gemakkelijk trager wordt. De compiler laat daarom vaak gebruikte waarden, bijvoorbeeld in lussen, in registers en kiest weinig gebruikte waarden om te spillen. Het aantal registers ligt vast door de CPU en neemt niet toe, en het verwijderen van overbodige waarden is iets anders.