Optimalisatie (compiler)

Optimalisatie is het proces waarbij een compiler de interne representatie van een te compileren computerprogramma manipuleert om het resulterende gecompileerde programma zo efficiënt mogelijk te maken. De fase van de compiler waarin dit gebeurt wordt optimalisatiefase genoemd.

Het doel van optimalisatie is het resulterende programma zo snel mogelijk en zo klein mogelijk te maken, zonder de werking van het programma te veranderen.

In het algemeen maken de meeste compilers gebruik van twee soorten optimalisatie: "gewone" optimalisatie (vanaf nu simpelweg optimalisatie genoemd) en peephole-optimalisatie.

Optimalisatie

Optimalisatie vindt plaats op een interne representatie van een te compileren programma. Deze interne representatie kan bijvoorbeeld de abstracte syntaxisboom van het programma zijn zoals die door de parser gegenereerd wordt. Een andere, en in de praktijk meer voorkomende, situatie is dat de abstracte syntaxisboom eerst vertaald wordt naar een meer algemene (programmeertaal-onafhankelijke) interne representatie. Deze wordt vervolgens geoptimaliseerd, en op basis van deze geoptimaliseerde interne versie van het programma wordt de uiteindelijke code gegenereerd.

Sommige compilers, zoals GCC, gebruiken meerdere optimalisatiefasen. Nadat de ene optimalisatie uitgevoerd is, wordt het resultaat vertaald naar een tweede (of derde, enz.) interne representatie, waarna deze door een volgende optimalisatiefase bewerkt wordt.

Voorbeelden

Enkele voorbeelden van veelvoorkomende optimalisaties zijn:

Constant folding

Constante expressies worden zo veel mogelijk uit de code gehaald. Bijvoorbeeld:
x = 10+y-5 wordt x = y+5, en
x = 3; y = x+5; wordt x = 3; y = 8;.

Wiskundige transformaties

Een expressie wordt vervangen door een eenvoudiger, equivalente expressie. Bijvoorbeeld:
x*y + x*z wordt x*(y+z).

Eliminatie van dubbele expressies (common subexpression elimination)

Een expressie die vaker voorkomt wordt verwijderd door deze slechts één keer te berekenen, en het resultaat in een tijdelijke variabele op te slaan. Bijvoorbeeld:

           a=2*(x+y);
           b=x+y+z;
           c=10*(x+y);

wordt:

           temp=x+y;
           a=2*temp;
           b=temp+z;
           c=10*temp;

Verwijderen van dode code en redundante code

Code die geen effect heeft op de werking van het programma, bijvoorbeeld omdat deze nooit uitgevoerd wordt of het resultaat nooit gebruikt wordt, wordt verwijderd.

Functie-substitutie (inline expansion, of function inlining)

Een functieaanroep wordt vervangen door de body van de functie. Dit bespaart een functieaanroep, met de bijbehorende overhead van het opslaan van registers, het aanmaken van een stackframe, enzovoort.

Staartrecursie

Als er sprake is van staartrecursie kan het huidige stackframe hergebruikt worden in plaats van een nieuw frame te gebruiken.

Loop unfolding

Een lus (Engels: loop) brengt meestal overhead met zich mee. Zo wordt in het onderstaande voorbeeld de binnenste lus 1000 keer uitgevoerd. Dat betekent dat het register dat voor variabele j gebruikt wordt 1000 keer op nul gezet moet worden, 5000 keer met 1 verhoogd moet worden en 1000 keer met 4 vergeleken moet worden.

       for (i=0; i<1000; i++) {
           for (j=0; j<4; j++) {
              data[i,j] = f(i,j);
           }
       }

Door de binnenste lus 'uit te vouwen' (Engels: to unfold) zijn die duizenden extra operaties niet langer nodig:

       for (i=0; i<1000; i++) {
              data[i,0] = f(i,0);
              data[i,1] = f(i,1);
              data[i,2] = f(i,2);
              data[i,3] = f(i,3);
       }

Peephole-optimalisatie

Peephole-optimalisatie vindt pas plaats tegen het einde van het compilatieproces en wordt uitgevoerd na de code-generatie. De gegenereerde machinecode wordt hierbij op instructieniveau geanalyseerd, waarbij gekeken wordt of kleine instructiereeksen door een efficiëntere instructiereeks vervangen kunnen worden.

De mogelijke optimalisaties bij peepholeoptimalisatie zijn sterk afhankelijk van de processor waarvoor gecompileerd wordt.

Voorbeelden

Enkele voorbeelden van peepholeoptimalisaties:

Strength reduction

Een kostbare berekening wordt vervangen door een minder kostbare berekening. Bijvoorbeeld:
a=a*2 wordt a=a<<1.
(De winst in dit voorbeeld zit hem in het feit dat vermenigvuldiging meer kloktikken kost dan een shift-operatie)

Scheduling

Soms is het zinvol om de volgorde van instructies te veranderen. Bijvoorbeeld door een rekeninstructie direct na een geheugeninstructie te plaatsen. Op een processor met pipelining kan de processor in zo'n geval alvast de berekening uitvoeren terwijl hij op het geheugen wacht.

Compiler