Interne representatie

Een interne representatie (vaak intermediate representation genoemd), afgekort IR, is een concept uit de informatica. Met een interne representatie wordt een interne en tijdelijke datastructuur bedoeld die een computerprogramma gebruikt om zijn invoer op te slaan alvorens deze verder te verwerken.

De term wordt voornamelijk gebruikt als het gaat over compilers en interpreters.

De parser van de compiler ontleedt de broncode (het invoerprogramma) en zet deze om in een abstracte syntaxis. Deze abstracte syntaxis wordt vervolgens omgezet naar een interne representatie^[1] waarop vervolgens verschillende bewerkingen worden uitgevoerd alvorens deze interne representatie om te zetten naar een uitvoerprogramma (de gecompileerde versie van het invoerprogramma).

Het omzetten van een invoerprogramma naar een abstracte syntaxisboom en vervolgens naar een IR gebeurt in de front-end van de compiler. De gegeneerde IR wordt vervolgens doorgegeven aan het middle-end. Vervolgens wordt er een aantal bewerkingen (optimalisaties en controles) op de geproduceerde IR uitgevoerd. Hierna wordt de IR doorgegeven aan de back-end, die de IR omzet in machinetaal en aanvullende, machine-afhankelijke optimalisaties toepast.

Het is niet ongebruikelijk dat een compiler gebruikmaakt van meerdere, verschillende IR's. In dat geval wordt de eerste IR van het te compileren programma, nadat deze geanalyseerd en geoptimaliseerd is, omgezet naar een tweede, andere IR. Deze wordt vervolgens ook geoptimaliseerd alvorens deze omgezet wordt naar het uitvoerprogramma, of weer naar een derde IR.

Ook de meeste interpreters maken gebruik van een IR. Nadat deze IR geoptimaliseerd is wordt deze echter niet zoals bij compilers doorgegeven aan een back-end die een uitvoerprogramma samenstelt. In plaats daarvan wordt de IR direct uitgevoerd. Zulke interpreters zijn in feite een soort compilers zonder back-end en hun IR heeft vaak de vorm van machinecode voor een virtuele machine.

Het gebruik van een IR in een compiler heeft twee redenen.

Modulariteit

Het gebruik van een IR bevordert de modulariteit van de compiler en maakt het makkelijker de compiler uit te breiden. Om de compiler een nieuwe programmeertaal te laten ondersteunen hoeft er alleen een nieuwe front-end gemaakt te worden die broncode in deze nieuwe taal omzet in de IR van de compiler. De middle-end en back-end hoeven niet aangepast te worden. Of als de compiler een nieuwe machine-architectuur moet ondersteunen, hoeft er alleen een nieuwe back-end gemaakt te worden die de IR omzet in machinetaal voor deze nieuwe architectuur.

Optimalisatie

De vorm van de IR (of IR's) die een compiler gebruikt worden zo gekozen dat deze optimalisaties mogelijk maken die met een abstracte syntaxis of de uiteindelijke machinecode niet mogelijk zijn. Bij compilers die meerdere interne representaties gebruiken zijn deze vaak zo gekozen dat ze elk andere, aanvullende optimalisaties mogelijk maken.

In het algemeen zijn er drie soorten interne representaties te onderscheiden:

Boomstructuur

De interne representatie heeft de vorm van boom (of graaf). Een abstracte syntaxisboom is een voorbeeld van een IR met een boomstructuur.

Lineair

De interne representatie bestaat uit een lijst van instructies (ook wel pseudocode genoemd) voor een abstracte machine. Voorbeelden hiervan zijn bytecode en de three address codes die in veel compilers gebruikt worden.

Een tussenvorm tussen beide

Een voorbeeld hiervan is een IR die lineaire pseudocode gebruikt voor het weergeven van blokken van instructies zonder spronginstructies en deze blokken in een boomstructuur plaatst die de control flow (en dus de spronginstructies) van het programma representeert.

In compilers die meerdere IR's gebruiken, is de eerste IR meestal een boomstructuur en de laatste IR vaak een lineaire IR, met daar tussenin eventueel tussenvormen.

IR's kunnen ook ingedeeld worden naar hun mate van abstractie. Hoe abstracter een IR is, hoe verder hij afstaat van de uiteindelijke machinecode die de compiler genereerd en de hardware-specifieke details die daarbij komen kijken. Abstracte IR's worden high-level genoemd en IR's die dichter bij machinecode staan worden low-level genoemd. Uiteraard zijn er allerlei tussenvormen mogelijk.

High-level

Als er gebruik wordt gemaakt van meerdere IR's worden high-level IR's gebruikt in het begin van het compilatieproces. De abstracte syntaxisboom is een high-level IR. High-level IR's zijn onder andere geschikt voor het analyseren en optimaliseren van de control flow van een te compileren programma.

Low-level

Low-level IR's hebben vaak een bijna één-op-één-relatie met de te produceren machinecode: iedere pseudo-instructie (of node) in de IR staat voor één machinecode-instructie. Low-level IR's zijn daarom vaak min of meer machine-specifiek. Een low-level IR leent zich goed voor machine-specifieke peep-hole-optimalisaties.

Niet alleen compilers en interpreters gebruiken interne representaties. Een voorbeeld van een ander programma dat een IR gebruikt is de webbrowser. Nadat een browser de HTML en andere inhoud van een webpagina ontvangen heeft, wordt deze omgezet in een IR alvorens deze op het scherm te tonen.