Code generatie (compiler) - Code generation (compiler)

Bij het berekenen , codegeneratie is het proces waarbij een compiler is codegenerator converteert enkele tussenrepresentatie van de broncode in een vorm (bijvoorbeeld machinecode ) die gemakkelijk kunnen worden uitgevoerd door een machine.

Geavanceerde compilers voeren doorgaans meerdere passages uit over verschillende tussenvormen. Dit proces met meerdere fasen wordt gebruikt omdat veel algoritmen voor code-optimalisatie gemakkelijker één voor één kunnen worden toegepast, of omdat de invoer voor één optimalisatie afhankelijk is van de voltooide verwerking die door een andere optimalisatie wordt uitgevoerd. Deze organisatie vergemakkelijkt ook de creatie van een enkele compiler die zich op meerdere architecturen kan richten, aangezien alleen de laatste van de codegeneratiestadia (de backend ) van doel naar doel hoeft te veranderen. (Zie Compiler voor meer informatie over compilerontwerp .)

De invoer voor de codegenerator bestaat meestal uit een ontleden-boom of een abstracte syntaxis-boom . De boom wordt omgezet in een lineaire reeks instructies, meestal in een tussentaal zoals een drie-adrescode . Verdere stadia van compilatie kunnen al dan niet "codegeneratie" worden genoemd, afhankelijk van of ze een significante verandering in de representatie van het programma met zich meebrengen. (Een kijkgaatje-optimalisatiepas wordt bijvoorbeeld waarschijnlijk niet "codegeneratie" genoemd, hoewel een codegenerator een kijkgaatje-optimalisatiepas kan bevatten.)

Hoofdtaken

Naast de basisconversie van een tussenweergave naar een lineaire reeks machine-instructies, probeert een typische codegenerator de gegenereerde code op de een of andere manier te optimaliseren.

Taken die typisch deel uitmaken van de "codegeneratie" -fase van een geavanceerde compiler, zijn onder meer:

Instructieselectie wordt typisch uitgevoerd door een recursieve postorder-traversal uit te voeren op de abstracte syntaxisboom, waarbij bepaalde boomconfiguraties worden vergeleken met sjablonen; de boom W := ADD(X,MUL(Y,Z))kan bijvoorbeeld worden omgezet in een lineaire reeks instructies door recursief de reeksen voor t1 := Xen te genereren t2 := MUL(Y,Z)en vervolgens de instructie uit te zenden ADD W, t1, t2.

In een compiler die een tussentaal gebruikt, kunnen er twee fasen zijn voor het selecteren van instructies: één om de ontledingsboom om te zetten in tussencode, en een tweede fase veel later om de tussencode om te zetten in instructies van de instructieset van de doelcomputer. Deze tweede fase vereist geen doorkruising door bomen; het kan lineair worden gedaan en omvat meestal een eenvoudige vervanging van bewerkingen in de tussentaal door hun overeenkomstige opcodes . Echter, indien de compiler is eigenlijk een vertaalprogramma (bijvoorbeeld één die converteert Java tot C ++ ) en de tweede codegeneratie fase kan omvatten het opbouwen van een boom uit de lineaire tussencode.

Genereren van runtime-code

Wanneer codegeneratie plaatsvindt tijdens runtime , zoals bij just-in-time compilatie (JIT), is het belangrijk dat het hele proces efficiënt is met betrekking tot ruimte en tijd. Wanneer bijvoorbeeld reguliere expressies worden geïnterpreteerd en gebruikt om code te genereren tijdens runtime, wordt vaak een niet-deterministische eindige-toestandsmachine gegenereerd in plaats van een deterministische, omdat de eerste meestal sneller kan worden gemaakt en minder geheugenruimte in beslag neemt dan de laatste. Ondanks dat het over het algemeen minder efficiënte code genereert, kan het genereren van JIT-code profiteren van profileringsinformatie die alleen beschikbaar is tijdens runtime.

Verwante concepten

De fundamentele taak van het nemen van input in één taal en het produceren van output in een niet-triviaal andere taal kan worden begrepen in termen van de fundamentele transformationele operaties van de formele taaltheorie . Bijgevolg zijn sommige technieken die oorspronkelijk werden ontwikkeld voor gebruik in compilers, ook op andere manieren gebruikt. Bijvoorbeeld, YACC (Yet Another parsergenerator ) draait input Backus-Naur vorm en zet het om een parser C . Hoewel het oorspronkelijk is gemaakt voor het automatisch genereren van een parser voor een compiler, wordt yacc ook vaak gebruikt om het schrijven van code te automatiseren die moet worden gewijzigd telkens wanneer specificaties worden gewijzigd.

Veel geïntegreerde ontwikkelomgevingen (IDE's) ondersteunen een of andere vorm van automatische broncodegeneratie , waarbij vaak gebruik wordt gemaakt van algoritmen die vergelijkbaar zijn met compilercodegeneratoren, hoewel deze doorgaans minder gecompliceerd zijn. (Zie ook: Programmatransformatie , Datatransformatie .)

Reflectie

Over het algemeen probeert een syntaxis- en semantische analysator de structuur van het programma uit de broncode te halen, terwijl een codegenerator deze structurele informatie (bijvoorbeeld datatypes ) gebruikt om code te produceren. Met andere woorden, de eerste voegt informatie toe, terwijl de laatste een deel van de informatie verliest . Een gevolg van dit informatieverlies is dat reflectie moeilijk of zelfs onmogelijk wordt. Om dit probleem tegen te gaan, voegen codegenerators vaak syntactische en semantische informatie in naast de code die nodig is voor uitvoering.

Zie ook

Referenties