Three address code

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Three address code is een term uit de informatica waarmee een bepaald type van interne representaties voor compilers aangeduid wordt.

In het algemeen bestaat three address code uit een reeks van statements met de vorm:

x := y op z

waarbij op een willekeurige operator is en x, y en z argumenten zijn die naar geheugenadressen, registers, constanten of labels verwijzen. Hoewel three address code ook statements met één of helemaal geen argumenten kan bevatten, of statements zonder resultaatstoewijzing (doel), zijn er nooit meer dan twee argumenten en één doel. Vandaar de naam three address code.

Three address code kan beschouwd worden als een assembly voor een virtuele machine met een oneindig aantal registers. Three address code lijkt vaak op assembly voor bestaande processoren en is daardoor voor een groot deel eenvoudig in machinetaal te vertalen.

Het statement x := x + y * z kan in three address code als volgt weergegeven worden:

t1 := x * z
x := x + t1

waarbij t1 een door de compiler gegenereerde tijdelijke variabele (een register) is.

Behalve rekenkundige bewerkingen en toewijzingen zijn er in het algemeen nog een aantal soorten statements in three address codes, waaronder voorwaardelijke en onvoorwaardelijke spronginstructies, procedure-aanroepen en ondersteuning voor arrays.

Voordelen[bewerken]

Three address code heeft een aantal voordelen:

  • Ze is compact (zowel in het computergeheugen als op papier).
  • Hoewel ze sterk op machinecode lijkt is het (nog) niet nodig om registerallocatie toe te passen. Door de machine-afhankelijke registerallocatie pas later uit te voeren is een compiler eenvoudiger aan te passen voor een nieuwe doelarchitectuur.
  • Door de sterke gelijkenis met "echte" machinecode is de uiteindelijke vertaling naar machinecode relatief eenvoudig.

Implementatie[bewerken]

In het algemeen zijn er drie implementatiemethoden voor three address codes: door middel van quadruplets, triplets of indirecte triplets.

Wanneer er gebruik wordt gemaakt van quadruplets wordt de three address code gerepresenteerd door een lijst (array) waarvan iedere rij vier velden heeft (iedere rij vormt een quadruple). Eén veld bevat de operator, één veld bevat het (optionele) doel en twee velden bevatten de (optionele) argumenten.

Bij het gebruik van triplets wordt ieder statement voorgesteld door drie in plaats van vier velden: één voor de operator en twee voor de optionele argumenten. Omdat three address code gebruik kan maken van een oneindig aantal tijdelijke variabelen kunnen we ieder resultaat van een bewerking opslaan in een tijdelijke variabele die overeenkomt met de positie van die bewerking in de array van three address statements. Dus: als de bewerking 2*a op de derde rij in de array staat dan zit het resultaat van deze bewerking in de tijdelijke variabele t3.

De triplet-methode kost minder geheugen dan het gebruik van quadruplets. Het nadeel is dat als een instructie verplaatst wordt alle verwijzingen naar het resultaat van deze bewerking aangepast moeten worden. Dit maakt triplets ongeschikt als de three address code nog geoptimaliseerd wordt, wat meestal het geval is. In dat geval zijn indirecte triplets geschikter.

Met indirecte triplets worden de instructies ook voorgesteld door triplets, maar daarnaast maken we gebruik van een array die pointers naar deze triplets bevat. Deze array bepaald de volgorde waarin de (instructies in) de triplets worden uitgevoerd. Een instructie kan nu verplaatst worden door deze array aan te passen terwijl de triplets zelf hun oorspronkelijke volgorde behouden.

Bronnen, noten en/of referenties
  • Compilers, Principles, Techniques and Tools, A. V. Aho, R. Sethi en J. D. Ullman, Addison-Wesley, 1986, ISBN 0201100886
  • Engineering a Compiler, K. Cooper en L. Torczon, Morgan Kaufmann, 2003, ISBN 155860698X