Compiler

Van Wikipedia, de gratis encyclopedie
Spring naar navigatie Spring naar zoeken

Een compiler (ook compiler, van Engels compileren, verzamelen 'of latin compilare, hoop') is een computerprogramma , de broncode van een bepaalde programmeertaal vertaald in een vorm van een computer (direct) kunnen worden uitgevoerd. Hierdoor ontstaat een min of meer direct uitvoerbaar programma. Dit moet worden onderscheiden van tolken , bijvoorbeeld voor vroege versies van BASIC , die geen machinecode genereren .

Soms wordt er onderscheid gemaakt tussen de termen vertaler en compiler. Een vertaler vertaalt een programma van een formele brontaal naar een semantisch equivalent in een formele doeltaal. Compilers speciale vertalers die convert programma code uit probleemgeoriënteerde programmeertalen , zogenaamde hoog - programmeertalen , in uitvoerbare machinecode van een specifiek platform of een tussengelegen code ( bytecode , p-code of NET-code ). Deze scheiding tussen de termen vertaler en compiler wordt niet in alle gevallen gemaakt.

Het proces van vertalen staat ook bekend als compilatie of conversie (of met het bijbehorende werkwoord ). Het tegenovergestelde, d.w.z. de omgekeerde vertaling van machinetaal in brontekst van een bepaalde programmeertaal, wordt decompilatie genoemd en bijbehorende programma's worden decompilers genoemd .

terminologie

Een vertaler is een programma dat een in een brontaal geformuleerd programma als invoer accepteert en vertaalt naar een semantisch equivalent programma in een doeltaal. [1] In het bijzonder is het vereist dat het gegenereerde programma dezelfde resultaten levert als het gegeven programma. De assembler van de brontaal wordt vaak als een uitzondering gezien - de vertaler (in machinecode) wordt "assembler" genoemd en is i. A. niet aangeduid als een "compiler". De taak van de vertaler omvat een breed scala aan subtaken, van syntaxisanalyse tot het genereren van doelcode. Een andere belangrijke taak is het identificeren en rapporteren van fouten in het bronprogramma.

Het woord "compiler" komt van het Engelse "compileren" en betekent "compiler" in de eigenlijke zin van het woord. In de jaren vijftig was de term nog niet stevig verankerd in de computerwereld. [2] Oorspronkelijk verwees compiler naar een hulpprogramma dat een algemeen programma van individuele subroutines of formule-evaluaties samenbracht om speciale taken uit te voeren. (Deze taak wordt nu uitgevoerd door de linker , die echter ook in de compiler kan worden geïntegreerd.) De afzonderlijke subroutines werden nog "met de hand" in machinetaal geschreven . Vanaf 1954 kwam de term “algebraïsche compiler” op voor een programma dat formules automatisch omzet in machinecode. De "algebraïsche" viel in de loop van de tijd weg. [3]

Eind jaren vijftig was de term compiler nog controversieel in Engelstalige landen. Het ontwikkelteam van Fortran hield jarenlang vast aan de term 'vertaler' om naar de compiler te verwijzen. Deze aanduiding is zelfs opgenomen in de naam van de Fortran-programmeertaal zelf: Fortran is samengesteld uit For mula en Tran slation, dat is ruwweg formulevertaling. Pas in 1964 kreeg de term compiler de overhand op de term vertaler in verband met Fortran. Volgens Carsten Busch is er een "speciale ironie in de geschiedenis" dat de term compiler in het Duits wordt vertaald als "vertaler". [2] [4] Sommige Duitse publicaties gebruiken echter ook de Engelse term compiler in plaats van vertaler. [5]

In engere zin gebruiken sommige Duitstalige publicaties de technische term compiler echter alleen als de brontaal een hogere programmeertaal is dan de doeltaal. [6] Typische toepassingen zijn de vertaling van een programmeertaal op hoog niveau in de machinetaal van een computer, evenals de vertaling in bytecode van een virtuele machine . De doeltaal van compilers (in die zin) kan ook een assembler zijn . Een vertaler voor het vertalen van assembler-bronprogramma's naar machinetaal wordt een assembler genoemd . [7]

verhaal

Konrad Zuse was al bezig met het plannen van een compiler voor de eerste hogere programmeertaal die is ontworpen, de Plankalkül van Konrad Zuse - volgens de huidige terminologie. Zuse genoemd enkel programma een berekening plan en reeds in 1944 het idee om een zogenaamd bovenaanzicht vervaardigingsinrichting, die automatisch stans moet genereren tape met een overeenkomstige machine voorgenomen Zuse Z4 computer van een wiskundig berekend plan. [8e]

Concreter dan Zuse's idee van een planproductieapparaat was een concept van Heinz Rutishauser [9] voor de automatische productie van rekenplannen . In een lezing voor de Society for Applied Mathematics and Mechanics ( GAMM ) en in zijn habilitatiescriptie aan de ETH Zürich in 1951, beschreef hij welke aanvullende programmeercommando's (instructies) en hardwaretoevoegingen nodig waren voor de Z4, die toen werd gebruikt bij de ETHZ De computer kan ook worden gebruikt als hulpmiddel bij het automatisch aanmaken van programma's. [10] [11] [12]

Grace Hopper (1984)

Een vroege compiler is ontworpen door wiskundige Grace Hopper in 1949. Tot die tijd moesten programmeurs de machinecode rechtstreeks maken. (De eerste assembler is geschreven door Nathaniel Rochester voor een IBM 701 tussen 1948 en 1950.) Om dit proces te vereenvoudigen, ontwikkelde Grace Hopper een methode die het mogelijk maakte om programma's en hun subroutines te maken op een meer mens- dan machinetaalgerichte manier. uitdrukken. [13] Op 3 mei 1952 introduceerde Hopper de eerste compiler A-0 voordat de algoritmen uit een catalogus werden afgeblazen, herschreef code die in de juiste volgorde was gecompileerd, gereserveerde ruimte en de toewijzing van geheugenadressen georganiseerd. [14] Begin 1955 presenteerde Hopper een prototype van de compiler B-0 , die programma's genereerde volgens Engelse, Franse of Duitse instructies. [15] Hopper noemde haar lezing over de eerste compiler "The Education of a Computer".

De geschiedenis van de compilerconstructie werd gevormd door de huidige programmeertalen (zie het programmeertaalrooster ) en hardware-architecturen. Andere vroege mijlpalen zijn de eerste Fortran- compiler in 1957 en de eerste COBOL- compiler in 1960. Veel architectonische kenmerken van de huidige samenstellers werden echter pas in de jaren zestig ontwikkeld.

In het verleden werden programma's soms ook wel compilers genoemd, die subprogramma's bij elkaar zetten. [16] Dit omzeilt de huidige kerntaak van een compiler, omdat subroutines tegenwoordig op andere manieren kunnen worden ingevoegd: ofwel in de brontekst zelf, bijvoorbeeld door een preprocessor (zie ook precompiler ) of, in het geval van gecompileerde componenten, door een onafhankelijke schakel .

Manier van werken

De basisstappen voor het vertalen van een broncode naar een doelcode zijn:

Syntaxiscontrole
Er wordt gecontroleerd of de broncode een geldig programma vertegenwoordigt, d.w.z. of deze overeenkomt met de syntaxis van de brontaal. Eventuele gevonden fouten worden gelogd. Het resultaat is een tussenweergave van de broncode.
Analyse en optimalisatie
De tussenweergave wordt geanalyseerd en geoptimaliseerd. Deze stap varieert sterk in omvang, afhankelijk van de compiler- en gebruikersinstellingen. Het varieert van eenvoudigere efficiëntie- optimalisaties tot programma-analyse .
Code generatie
De geoptimaliseerde tussenweergave wordt vertaald in overeenkomstige commando's in de doeltaal. Verder kunnen hier doeltaalspecifieke optimalisaties worden uitgevoerd.
Opmerking: moderne compilers genereren (meestal) zelf geen code meer.
Codegeneratie tijdens runtime maakt het volgende mogelijk:
  • cross-module optimalisaties,
  • exacte aanpassingen aan het doelplatform (instructieset, aanpassing aan de mogelijkheden van de CPU),
  • Gebruik van profileringsinformatie.

Structuur van een compiler

Compilerconstructie , oftewel het programmeren van een compiler, is een zelfstandige discipline binnen de informatica .

Moderne compilers zijn verdeeld in verschillende fasen, die elk verschillende subtaken van de compiler op zich nemen. Sommige van deze fasen kunnen worden geïmplementeerd als onafhankelijke programma's (zie precompiler , preprocessor ). Ze worden achtereenvolgens uitgevoerd. Er zijn grofweg twee fasen te onderscheiden: de front-end (ook analysefase ), die de brontekst analyseert en gebruikt om een ​​toegeschreven syntaxisboom te genereren, en de back-end (ook synthesefase ), die deze gebruikt om het doelprogramma te genereren .

Frontend (ook "analysefase")

In de front-end wordt de code geanalyseerd, gestructureerd en gecontroleerd op fouten. Het is zelf verdeeld in fasen. Talen zoals moderne C ++ laten niet toe dat de syntaxisanalyse wordt onderverdeeld in lexicale analyse, syntactische analyse en semantische analyse vanwege dubbelzinnigheden in hun grammatica. Hun compilers zijn dienovereenkomstig complex.

Lexicale analyse

De lexicale analyse verdeelt de geïmporteerde brontekst in lexicale eenheden ( tokens ) van verschillende typen, bijvoorbeeld trefwoorden , identifiers , getallen , strings of operators . Dit deel van de compiler wordt een tokenizer, scanner of lexer genoemd.

Een scanner gebruikt soms een aparte screener voor spaties (overslaan witte ruimte , d.w.z. spaties, tabs, regeleinden, enzovoort) en commentaar .

Een andere functie van de lexicale analyse is om herkende tokens te associëren met hun positie (bijvoorbeeld regelnummer) in de brontekst. Indien er in de verdere analysefase fouten worden gevonden in de brontekst, die gebaseerd is op de tokens (bijvoorbeeld van syntactische of semantische aard), kunnen de gegenereerde foutmeldingen worden voorzien van een verwijzing naar de locatie van de fout.

Lexicale fouten zijn tekens of tekenreeksen die niet aan een token kunnen worden toegewezen. De meeste programmeertalen staan ​​bijvoorbeeld geen identifiers toe die met cijfers beginnen (bijvoorbeeld "3foo").

Syntactische analyse

De syntactische analyse controleert of de geïmporteerde broncode zich in de juiste structuur van de te vertalen brontaal bevindt, d.w.z. overeenkomt met de contextvrije syntaxis (grammatica) van de brontaal. De invoer wordt omgezet in een syntaxisboom . De syntactische analysator is ook bekend als een parser . Als de broncode niet overeenkomt met de grammatica van de brontaal, geeft de parser een syntaxisfout af . De op deze manier gemaakte syntaxisboom wordt geannoteerd met de "inhoud" van de knooppunten voor de volgende fase (semantische analyse); Dat betekent dat bijvoorbeeld variabele identifiers en nummers worden doorgegeven samen met de informatie dat ze dat zijn. De syntactische analyse controleert bijvoorbeeld of de haakjes correct zijn, d.w.z. elk openend haakje wordt gevolgd door een sluitend haakje van hetzelfde type, en ook zonder haakjesverstrengeling. De trefwoorden zorgen ook voor bepaalde structuren.

semantische analyse

De semantische analyse controleert de statische semantiek , d.w.z. voorwaarden op het programma die verder gaan dan de syntactische analyse. Een variabele moet bijvoorbeeld meestal zijn gedeclareerd voordat deze wordt gebruikt, en toewijzingen moeten worden gemaakt met compatibele (compatibele) gegevenstypen . Dit kan met behulp van attributengrammatica's . De knooppunten van de syntaxisstructuur die door de parser worden gegenereerd, krijgen attributen die informatie bevatten. Er kan bijvoorbeeld een lijst met alle gedeclareerde variabelen worden gemaakt. De uitvoer van de semantische analyse wordt dan een versierde of toegeschreven syntaxisboom genoemd.

Backend (ook "synthesefase")

De backend genereert de programmacode van de doeltaal uit de toegeschreven syntaxisboom die door de frontend is gemaakt.

Tussentijdse codegeneratie

Veel moderne compilers genereren een tussencode uit de syntaxisboom, die zich al relatief dicht bij de machine kan bevinden, en voeren bijvoorbeeld programma-optimalisaties uit op deze tussencode. Dit is vooral handig voor compilers die meerdere brontalen of verschillende doelplatforms ondersteunen . Hier kan de tussencode ook een uitwisselingsformaat zijn.

Programma optimalisatie

De tussencode is de basis van veel programma-optimalisaties. Zie programma-optimalisatie .

Code generatie

Tijdens het genereren van codes wordt de programmacode van de doeltaal ofwel rechtstreeks uit de syntaxisboom ofwel uit de tussencode gegenereerd. Als de doeltaal een machinetaal is, kan het resultaat direct een uitvoerbaar programma zijn of een zogenaamd objectbestand dat door koppeling met de runtime- bibliotheek en mogelijk andere objectbestanden leidt tot een bibliotheek of een uitvoerbaar programma . Dit alles wordt uitgevoerd door de codegenerator, die deel uitmaakt van het compilersysteem, soms als onderdeel van het compilerprogramma, soms als een aparte module.

Classificatie van verschillende soorten compilers

Native compiler
Compiler die de doelcode genereert voor het platform waarop het zelf draait. De code is platformspecifiek.
Cross-compiler
Compiler die op het ene platform draait en doelcode genereert voor een ander platform, bijvoorbeeld een ander besturingssysteem of een andere processorarchitectuur .
Een typische toepassing is het maken van programma's voor een ingebed systeem dat zelf geen of geen goede hulpmiddelen bevat voor het maken van software, evenals het maken of overzetten van een besturingssysteem naar een nieuw platform.
Single pass compiler
Compiler die in één keer de doelcode uit de broncode genereert (in tegenstelling tot de multi-pass compiler); de compiler leest de brontekst slechts één keer van voor naar achter en genereert tegelijkertijd het resultaatprogramma. Zo'n compiler is meestal erg snel, maar kan alleen eenvoudige optimalisaties uitvoeren. Een single-pass compiler kan alleen worden gemaakt voor bepaalde programmeertalen, bijvoorbeeld Pascal , C en C++ , omdat de programmeertaal geen forward references mag bevatten (er mag niets worden gebruikt dat niet al "hierboven" is gedeclareerd in de broncode).
Multi-pass compiler
Bij dit type compiler wordt de broncode in meerdere stappen vertaald naar de doelcode (oorspronkelijk: de broncode wordt meerdere keren ingelezen of meerdere keren "van voor naar achter" volledig doorgewerkt). In de begindagen van de compilerconstructie was het vertaalproces voornamelijk verdeeld in verschillende runs, omdat de computer vaak niet genoeg capaciteit had om de complete compiler en het te vertalen programma tegelijkertijd in het hoofdgeheugen te bewaren. Tegenwoordig wordt een multi-pass compiler voornamelijk gebruikt om forward references op te lossen ( declaratie van een identifier "verder in de broncode" als eerste gebruik) en om complexe optimalisaties uit te voeren.

Speciale vormen

  • Een transcompiler (ook wel transpiler of cross-translator genoemd ) is een speciale compiler die de broncode van de ene programmeertaal vertaalt naar de broncode van een andere programmeertaal, bijvoorbeeld van Pascal naar C. [17] Dit proces wordt "codetransformatie" of "vertalen" genoemd. Omdat veel programmeertalen echter speciale eigenschappen en prestatiekenmerken hebben, kunnen er efficiëntieverliezen optreden als deze niet in aanmerking worden genomen door de transcompiler. [18] Aangezien programmeertalen meestal verschillende programmeerparadigma's volgen , is de nieuw gegenereerde broncode vaak moeilijk leesbaar voor ontwikkelaars. Soms is handmatige nabewerking van de code nodig omdat de automatische vertaling niet in alle gevallen soepel verloopt. Er zijn ook uitgebreide subprogrammabibliotheken in veel moderne programmeertalen. Het implementeren van bibliotheekaanroepen maakt het compilatieproces nog moeilijker.
  • Compiler-compilers en compiler-generatoren zijn hulpprogramma's voor het automatisch genereren van compiler-onderdelen of complete compilers. Zie ook: ANTLR , Coco / R , JavaCC , Lex , Yacc
  • Just-in-time-compilers (of JIT-compilers ) vertalen de broncode of tussencode niet in machinecode totdat het programma is uitgevoerd. Programmaonderdelen worden pas samengesteld als ze voor de eerste keer of meerdere keren worden uitgevoerd. De mate van optimalisatie hangt meestal af van de gebruiksfrequentie van de overeenkomstige functie.
  • Met de Compreter wordt de programmabroncode eerst vertaald in een tussencode, die vervolgens tijdens runtime wordt geïnterpreteerd. Compreters moeten de voordelen van de compiler combineren met de voordelen van de interpreter . Om de uitvoeringstijd te verkorten, worden veel hedendaagse interpreters effectief intern geïmplementeerd als computers die de broncode tijdens runtime vertalen voordat het programma wordt uitgevoerd. Een bytecode-interpreter is ook een compreter, b.v. B. de virtuele machines van Java tot versie 1.2.

Programma-optimalisatie (in detail)

Veel optimalisaties die vroeger de taak van de compiler waren, worden nu binnen de CPU uitgevoerd terwijl de code wordt verwerkt. Machinecode is goed als het korte kritieke paden heeft en weinig verrassingen door verkeerd voorspelde sprongen, tijdig gegevens uit het geheugen opvraagt ​​en alle uitvoeringseenheden van de CPU gelijkelijk gebruikt.

Parallelle berekening van de hoeveelheid Mandelbrot op een Haswell i7 CPU (2014). De grafiek toont de berekeningen die gelijktijdig plaatsvinden op een core (datatype: floating point, single precision), dat wil zeggen tussen 64 en 128 berekeningen in 8 tot 16 commando's per core, verdeeld over 2 threads. Op een Haswell Core i7-5960X (8 cores) vinden tot 1024 parallelle berekeningen (96 miljard iteraties/sec) plaats, op een Haswell Xeon E7-8890 V3 tot 2304 (180 miljard iteraties/sec per socket). De taak van moderne compilers is om code te optimaliseren om deze nesting van instructies mogelijk te maken. Dit is een fundamenteel ander werk dan samenstellers aan het eind van de jaren tachtig deden.

Om de vertaling te controleren, kan de brontekst naast de instructies van de programmeertaal aanvullende speciale compilerinstructies bevatten.

Een compiler biedt meestal opties voor verschillende optimalisaties met als doel de runtime van het doelprogramma te verbeteren of de benodigde opslagruimte te minimaliseren. De optimalisaties zijn mede afhankelijk van de eigenschappen van de hardware , bijvoorbeeld hoeveel en welke registers de processor van de computer beschikbaar stelt. Het is mogelijk dat een programma na optimalisatie langzamer loopt dan zonder optimalisatie. Dit kan bijvoorbeeld gebeuren wanneer een optimalisatie voor een programmaconstructie langere code produceert die eigenlijk sneller zou worden uitgevoerd, maar die meer tijd nodig heeft om in de cache te worden geladen. Het is daarom alleen voordelig als het veelvuldig wordt gebruikt.

Sommige optimalisaties leiden ertoe dat de compiler doeltaalconstructies genereert waarvoor er geen directe equivalenten zijn in de brontaal. Een nadeel van dergelijke optimalisaties is dat het dan nauwelijks mogelijk is om het programmaverloop te volgen met een interactieve debugger in de brontaal.

Optimalisaties kunnen erg tijdrovend zijn. In veel gevallen, vooral in moderne JIT-compilers, is het daarom noodzakelijk om af te wegen of het de moeite waard is om een ​​deel van het programma te optimaliseren. Met voortijdige compilers worden alle verstandige optimalisaties gebruikt in de uiteindelijke compilatie, maar vaak niet tijdens de softwareontwikkeling (dit vermindert de vereiste compilatietijd). Voor niet-automatische optimalisaties van de kant van de programmeur kunnen tests en toepassingsscenario's worden doorlopen (zie Profiler ) om te achterhalen waar complexe optimalisaties de moeite waard zijn.

Hieronder worden enkele optimalisatie-opties voor een compiler beschouwd. Het grootste potentieel voor optimalisatie ligt echter vaak in het wijzigen van het bronprogramma zelf, bijvoorbeeld in het vervangen van een algoritme door een efficiënter algoritme . In de meeste gevallen kan dit proces niet worden geautomatiseerd, maar moet het door de programmeur worden uitgevoerd. Aan de andere kant kunnen eenvoudiger optimalisaties worden gedelegeerd aan de compiler om de broncode leesbaar te houden.

Opslaan van machinecommando's

In veel programmeertalen op hoog niveau hebt u bijvoorbeeld een hulpvariabele nodig om de inhoud van twee variabelen om te wisselen:

Opslaan van machinecommando's (MB)
Broncode Machine-opdrachten
zonder optimalisatie met optimalisatie
hilf := a a → registreren 1
Registreren 1 → help
a → registreren 1
a := b b → Registreren 1
Registreren 1 → a
b → Registreren 2
Registreren 2 → a
b := hilf help → Registreren 1
Registreren 1 → b
Registreren 1 → b
Vereist ...
variabelen 3 2
register 1 2
Activiteiten 6e 4e

Met de optimalisatie zijn slechts 4 assembler-commando's vereist in plaats van 6, en de geheugenruimte voor de hulpvariabele hilf niet vereist. Dit betekent dat deze swap sneller wordt uitgevoerd en minder werkgeheugen vereist. Dit geldt echter alleen als er voldoende registers in de processor aanwezig zijn . Het opslaan van gegevens in registers in plaats van in het hoofdgeheugen is een gebruikelijke optimalisatieoptie.

De hierboven weergegeven opdrachtvolgorde als geoptimaliseerd heeft nog een eigenschap die een voordeel kan zijn in moderne CPU's met meerdere verwerkingspijplijnen: de twee leescommando's en de twee schrijfcommando's kunnen probleemloos parallel worden verwerkt, ze zijn niet afhankelijk van het resultaat van de ander. Alleen het eerste schrijfcommando moet beslist wachten tot het laatste leescommando is uitgevoerd. Meer diepgaande optimalisatieprocessen kunnen daarom machinecommando's invoegen tussen b → register 2 en register 2 → a die behoren tot een geheel andere opdrachtregel op hoog niveau.

Statische formule-evaluatie tijdens compilatie

De berekening van de omtrek met behulp van

 pi = 3.14159
u = 2 * pi * r

kan een compiler al tijdens het compileren u = 6.28318 * r evalueren. Deze formule-evaluatie slaat de vermenigvuldiging 2 * pi tijdens de looptijd van het gegenereerde programma. Deze procedure wordt constant vouwen genoemd.

Eliminatie van dode programmacode

Als de compiler kan herkennen dat een deel van het programma nooit zal worden doorlopen, dan kan hij dit deel uit de compilatie weglaten.

Voorbeeld:

 100   ga naar 900
200   k = 3
900   ik = 7
...   ...

Als er in dit programma nooit een GOTO op spronglabel 200 , kan de instructie 200 k=3 achterwege blijven. De springinstructie 100 goto 900 is dan ook overbodig.

Detectie van ongebruikte variabelen

Als een variabele niet nodig is, hoeft er geen geheugenruimte voor te worden gereserveerd en hoeft er geen doelcode te worden gegenereerd.

Voorbeeld:

 subroutine-test (a, b)
    b = 2 * a
    c = 3,14 * b
    terugkeer b

De variabele c niet vereist: hij staat niet in de parameterlijst , wordt niet gebruikt in volgende berekeningen en wordt niet uitgevoerd. Daarom kan de instructie c = 3.14 * b weggelaten.

Loops optimaliseren

In het bijzonder probeert men loops te optimaliseren door bv

  • houdt zoveel mogelijk variabelen in registers (meestal ten minste de lusvariabele);
  • in plaats van een index, met de elementen van een veld ( Engels is access array), worden verwijzingen naar de elementen gebruikt, waardoor de inspanning om toegang te krijgen tot veldelementen laag is;
  • Berekeningen binnen de lus, die in elke run hetzelfde resultaat opleveren, worden slechts één keer vóór de lus uitgevoerd (loop-invariante codebeweging);
  • combineert twee lussen die hetzelfde waardenbereik dekken in één lus, zodat de administratieve inspanning voor de lus slechts één keer wordt gemaakt;
  • de lus wordt gedeeltelijk of (in het geval van lussen met een constant, laag aantal passages) volledig afgerold (Engelse lus uitrollen ), zodat de instructies binnen de lus meerdere keren direct achter elkaar worden uitgevoerd zonder controle van de lusconditie en een spring naar het begin van de lus die elke keer na de instructies plaatsvindt;
  • keert de lus om (vooral bij tellussen met for ), aangezien efficiënte sprongcommando's (Jump-Not-Zero) kunnen worden gebruikt bij het aftellen tot 0;
  • hervormt de lus zodat de controle van de beëindigingsvoorwaarde wordt uitgevoerd aan het einde van de lus (lussen met een initiële controle hebben altijd een voorwaardelijke en een onvoorwaardelijke springinstructie, terwijl lussen met een eindcontrole alleen een voorwaardelijke springinstructie hebben);
  • de hele lus verwijderd als deze (na wat tweaken) een lege body heeft. Dit kan er echter toe leiden dat wachtrijen die bedoeld zijn om een ​​programma te vertragen, worden verwijderd. De functies van het besturingssysteem moeten echter zoveel mogelijk voor dit doel worden gebruikt.
  • Rangschikt geneste lussen (lussen in lussen) - als de gebruikte programmeerlogica dit toelaat - in oplopende volgorde, van de buitenste lus met de minste lusdoorgangen naar de binnenste lus met de meeste lusdoorgangen. Dit voorkomt meerdere meervoudige initialisaties van de binnenste luslichamen.

Sommige van deze optimalisaties zijn nutteloos of zelfs contraproductief met de huidige processors.

Invoegen van subroutines

In het geval van kleine subroutines is de inspanning die nodig is om de subroutine aan te roepen belangrijker dan het werk dat door de subroutine wordt verricht. Compilers proberen daarom de machinecode van kleinere subroutines direct in te voegen - vergelijkbaar met hoe sommige compilers / assemblers / precompilers macro- instructies opsplitsen in broncode. Deze techniek wordt ook wel inlining genoemd. In sommige programmeertalen is het mogelijk om inline trefwoorden te gebruiken om aan de compiler aan te geven dat bepaalde subroutines moeten worden ingevoegd. Het invoegen van subroutines opent vaak verdere optimalisatiemogelijkheden, afhankelijk van de parameters.

Waarden in registers houden

Anstatt mehrfach auf dieselbe Variable im Speicher, beispielsweise in einer Datenstruktur, zuzugreifen, kann der Wert nur einmal gelesen und für weitere Verarbeitungen in Registern oder im Stack zwischengespeichert werden. In C , C++ und Java muss dieses Verhalten ggf. mit dem Schlüsselwort volatile abgeschaltet werden: Eine als volatile bezeichnete Variable wird bei jeder Benutzung wiederholt vom originalen Speicherplatz gelesen, da ihr Wert sich unterdessen geändert haben könnte. Das kann beispielsweise der Fall sein, wenn es sich um einen Hardware-Port handelt oder ein parallel laufender Thread den Wert geändert haben könnte.

Beispiel:

 int a = array [ 25 ] -> element . x ;
int b = 3 * array [ 25 ] -> element . x ;

Im Maschinenprogramm wird nur einmal auf array[25]->element.x zugegriffen, der Wert wird zwischengespeichert und zweimal verwendet. Ist x volatile, dann wird zweimal zugegriffen.

Es gibt außer volatile noch einen anderen Grund, der eine Zwischenspeicherung in Registern unmöglich macht: Wenn der Wert der Variablen v durch Verwendung des Zeigers z im Speicher verändert werden könnte, kann eine Zwischenspeicherung von v in einem Register zu fehlerhaftem Programmverhalten führen. Da die in der Programmiersprache C oft verwendeten Zeiger nicht auf ein Array beschränkt sind (sie könnten irgendwohin im Hauptspeicher zeigen), hat der Optimizer oft nicht genügend Informationen, um eine Veränderung einer Variablen durch einen Zeiger auszuschließen.

Verwendung schnellerer äquivalenter Anweisungen

Statt einer Multiplikation oder Division von Ganzzahlen mit einer Zweierpotenz kann ein Schiebebefehl verwendet werden. Es gibt Fälle, in denen nicht nur Zweierpotenzen, sondern auch andere Zahlen (einfache Summen von Zweierpotenzen) für diese Optimierung herangezogen werden. So kann zum Beispiel ( n << 1 ) + ( n << 2 ) schneller sein als n * 6 . Statt einer Division durch eine Konstante kann eine Multiplikation mit dem Reziprokwert der Konstante erfolgen. Selbstverständlich sollte man solch spezielle Optimierungen auf jeden Fall dem Compiler überlassen.

Weglassen von Laufzeitüberprüfungen

Programmiersprachen wie Java fordern Laufzeitüberprüfungen beim Zugriff auf Felder oder Variablen. Wenn der Compiler ermittelt, dass ein bestimmter Zugriff immer im erlaubten Bereich sein wird (zum Beispiel ein Zeiger, von dem bekannt ist, dass er an dieser Stelle nicht NULL ist), kann der Code für diese Laufzeitüberprüfungen weggelassen werden.

Reduktion von Paging zur Laufzeit

Eng zusammenhängende Codebereiche, zum Beispiel ein Schleifenrumpf, sollte zur Laufzeit möglichst auf der gleichen oder in möglichst wenigen Speicherseiten („Page“, zusammenhängend vom Betriebssystem verwalteter Speicherblock) im Hauptspeicher liegen. Diese Optimierung ist Aufgabe des (optimierenden) Linkers. Dies kann zum Beispiel dadurch erreicht werden, dass dem Zielcode an geeigneter Stelle Leeranweisungen („NOPs“ – N o OP eration) hinzugefügt werden. Dadurch wird der erzeugte Code zwar größer, aber wegen der reduzierten Anzahl notwendiger TLB-Cache-Einträge und notwendiger Pagewalks wird das Programm schneller ausgeführt.

Vorziehen bzw. Verzögern von Speicherzugriffen

Durch das Vorziehen von Speicherlesezugriffen und das Verzögern von Schreibzugriffen lässt sich die Fähigkeit moderner Prozessoren zur Parallelarbeit verschiedener Funktionseinheiten ausnutzen. So kann beispielsweise bei den Befehlen: a = b * c; d = e * f; der Operand e bereits geladen werden, während ein anderer Teil des Prozessors noch mit der ersten Multiplikation beschäftigt ist.

Ein Beispielcompiler

Folgendes in ANTLR erstelltes Beispiel soll die Zusammenarbeit zwischen Parser und Lexer erklären. Der Übersetzer soll Ausdrücke der Grundrechenarten beherrschen und vergleichen können. Die Parser grammatik wandelt einen Dateiinhalt in einen abstrakten Syntaxbaum (AST) um.

Grammatiken

Die Baumgrammatik ist in der Lage, die im AST gespeicherten Lexeme zu evaluieren. Der Operator der Rechenfunktionen steht in der AST-Schreibweise vor den Operanden als Präfixnotation . Daher kann die Grammatik ohne Sprünge Berechnungen anhand des Operators durchführen und dennoch Klammerausdrücke und Operationen verschiedener Priorität korrekt berechnen.

 tree grammar Eval ;
options {
	tokenVocab = Expression ;
	ASTLabelType = CommonTree ;
}
@header {
import java.lang.Math ;
}
start : line + ; //Eine Datei besteht aus mehreren Zeilen
line : compare { System . out . println ( $compare . value );}
	;

compare returns [ double value ]
	: ^ ( '+' a = compare b = compare ) { $value = a + b ;}
	| ^ ( '-' a = compare b = compare ) { $value = a - b ;}
	| ^ ( '*' a = compare b = compare ) { $value = a * b ;}
	| ^ ( '/' a = compare b = compare ) { $value = a / b ;}
	| ^ ( '%' a = compare b = compare ) { $value = a \ % b ;}
	| ^ ( UMINUS a = compare ) { $value = - 1 * a ;} //Token UMINUS ist notwendig, um den binären
                                                      //Operator nicht mit einem Vorzeichen zu verwechseln
	| ^ ( '^' a = compare b = compare ) { $value = Math . pow ( a , b );}
	| ^ ( '=' a = compare b = compare ) { $value = ( a == b ) ? 1 : 0 ;} //wahr=1, falsch=0
	| INT { $value = Integer . parseInt ( $INT . text );}
	;

Ist eines der oben als compare bezeichnete Ausdrücke noch kein Lexem, so wird es von der folgenden Lexer-Grammatik in einzelne Lexeme aufgeteilt. Dabei bedient sich der Lexer der Technik des rekursiven Abstiegs . Ausdrücke werden so immer weiter zerlegt, bis es sich nur noch um Token vom Typ number oder Operatoren handeln kann.

 grammar Expression ;
options {
	output = AST ;
	ASTLabelType = CommonTree ;
}
tokens {
	UMINUS ;
}
start : ( line { System . out . println ( $line . tree == null ? "null" : $line . tree . toStringTree ());}) + ;
line : compare NEWLINE -> ^ ( compare ); //Eine Zeile besteht aus einem Ausdruck und einem
                                              //terminalen Zeichen
compare : sum ( '=' ^ sum ) ? ; //Summen sind mit Summen vergleichbar
sum : product ( '+' ^ product | '-' ^ product ) * ; //Summen bestehen aus Produkten (Operatorrangfolge)
product : pow ( '*' ^ pow | '/' ^ pow | '%' ^ pow ) * ; //Produkte (Modulo-Operation gehört hier dazu) können
                                                  //aus Potenzen zusammengesetzt sein
pow : term ( '^' ^ pow ) ? ; //Potenzen werden auf Terme angewendet
term : number //Terme bestehen aus Nummern, Subtermen oder Summen
		| '+' term -> term
		| '-' term -> ^ ( UMINUS term ) //Subterm mit Vorzeichen
		| '(' ! sum ')' ! //Subterm mit Klammerausdruck
		;
number : INT ; //Nummern bestehen nur aus Zahlen
INT : '0' .. '9' + ;
NEWLINE : '\r' ? '\n' ;
WS : ( ' ' | '\t' | '\n' | '\r' ) + { skip ();}; //Whitespace wird ignoriert

Die Ausgabe hinter dem Token start zeigt außerdem den gerade evaluierten Ausdruck.

Ausgabe des Beispiels

Eingabe:

 5 = 2 + 3
32 * 2 + 8
(2 * 2^3 + 2) / 3

Ausgabe (in den ersten Zeilen wird nur der Ausdruck der Eingabe in der AST-Darstellung ausgegeben):

 (= 5 (+ 2 3))
(+ (* 32 2) 8)
(/ (+ (* 2 (^ 2 3)) 2) 3)
1.0
72.0
6.0

Der erste Ausdruck wird also als wahr (1) evaluiert, bei den anderen Ausdrücken wird das Ergebnis der Rechnung ausgegeben.

Literatur

Weblinks

Wiktionary: Compiler – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen
Wiktionary: kompilieren – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen

Einzelnachweise

  1. Michael Eulenstein: Generierung portabler Compiler. Das portable System POCO. (= Informatik-Fachberichte 164) Springer Verlag: Berlin, ua, 1988, S. 1; Hans-Jochen Schneider (Hrsg.): Lexikon Informatik und Datenverarbeitung. 4. Auflage, Oldenbourg Verlag: München, Berlin, 1998, 900; Manfred Broy: Informatik. Eine grundlegende Einführung. Band 2: Systemstrukturen und Theoretische Informatik. 2. Auflage, Springer Verlag: Berlin, Heidelberg, 1998, S. 173.
  2. a b Carsten Busch: Mataphern in der Informatik. Modellbildung - Formalisierung - Anwendung. Springer Fachmedien: Wiesbaden, 1998, S. 171.
  3. Axel Rogat: Aufbau und Arbeitsweise von Compilern , Kapitel 1.11: Geschichte ; Thomas W. Parsons: Introduction to Compiler Construction. Computer Science Press: New York, 1992, S. 1.
  4. Zur Übersetzung des englischen „compiler“ mit dem deutschen „Übersetzer“ siehe ua: Hans-Jürgen Siegert, Uwe Baumgarten: Betriebssysteme. Eine Einführung. 6. Auflage, Oldenbourg Verlag: München, Wien, 2007, S. 352; Christoph Prevezanos: Computer-Lexikon 2011. Markt+Technik Verlag: München, 2010, S. 940; Christoph Prevenzanos: Technisches Schreiben. Für Informatiker, Akademiker, Techniker und den Berufsalltag. Hanser Verlag: München, 2013, S. 130.
  5. So beispielsweise Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman: Compiler. Prinzipien, Techniken und Werkzeuge. 2. Auflage, Pearson Studium: München, 2008.
  6. Siehe dazu Hans-Jochen Schneider (Hrsg.): Lexikon Informatik und Datenverarbeitung. 4. Auflage, Oldenbourg Verlag: München, Berlin, 1998: Artikel „Compiler“, S. 158, und Artikel „Übersetzer“, S. 900.
  7. Hartmut Ernst, Jochen Schmidt; Gert Beneken: Grundkurs Informatik. Grundlagen und Konzepte für die erfolgreiche IT-Praxis. Eine umfassende, praxisorientierte Einführung. 5. Auflage, Springer: Wiesbaden, 2015, S. 409.
  8. Hans Dieter Hellige: Geschichten der Informatik. Visionen, Paradigmen, Leitmotive. Springer, Berlin 2004, ISBN 3-540-00217-0 , S. 45, 104, 105.
  9. Evelyn Boesch Trüeb: Heinz Rutishauser. In: Historisches Lexikon der Schweiz . 12. Juli 2010 , abgerufen am 21. Oktober 2014 .
  10. Stefan Betschon: Der Zauber des Anfangs. Schweizer Computerpioniere. In: Franz Betschon , Stefan Betschon, Jürg Lindecker, Willy Schlachter (Hrsg.): Ingenieure bauen die Schweiz. Technikgeschichte aus erster Hand. Verlag Neue Zürcher Zeitung, Zürich 2013, ISBN 978-3-03823-791-4 , S. 381–383.
  11. Friedrich L. Bauer: My years with Rutishauser.
  12. Stefan Betschon: Die Geschichte der Zukunft. In: Neue Zürcher Zeitung, 6. Dezember 2016, S. 11
  13. Inventor of the Week Archive.Massachusetts Institute of Technology , Juni 2006, abgerufen am 25. September 2011 .
  14. Kurt W. Beyer: Grace Hopper and the invention of the information age . Massachusetts Institute of Technology, 2009, ISBN 978-0-262-01310-9 ( Google Books [abgerufen am 25. September 2011]).
  15. Kathleen Broome Williams: Grace Hopper . Naval Institute Press, 2004, ISBN 1-55750-952-2 ( Google Books [abgerufen am 25. September 2011]).
  16. FL Bauer, J. Eickel: Compiler Construction: An Advanced Course . Springer, 1975.
  17. Transcompiler. In: Neogrid IT Lexikon. Abgerufen am 18. November 2011 : „Wenn ein Compiler aus dem Quellcode einer Programmiersprache den Quellcode einer anderen erzeugt (z. B. C in C++) so spricht man von einem Transcompiler.“
  18. Transpiler. bullhost.de, abgerufen am 18. November 2012 .