Skip to content

Două tehnici de optimizare

13 May 2008

Am să vorbesc puțin despre optimizări, mai exact optimizări independente de mașină. Domeniul optimizărilor este foarte vast și aceste optimizări fac de obicei diferența dintre un compilator bun și unul foarte bun. După cum spuneam într-un post anterior, problema optimizării e NP completă și se utilizează algoritmi care produc cod relativ bun într-un timp rezonabil.

Compilatorul pe care îl dezvolt efectuează doar două astfel de optimizări: constant folding și dead code elimination.

Constant folding presupune înlocuirea expresiilor cu operanzi constanți (expresii ce pot fi calculate în timpul compilării) cu rezultatul lor. De exemplu, expresiei

i = (2 + 3) * 5

îi corespunde în arborele abstract de sintaxă un nod expresie binară cu operatorul * vând copii (operanzi) un nod expresie binară cu operatorul + și un nod constantă întreagă cu valoarea 5. Nodul expresie binară cu operatorul + are copii două noduri constantă întreagă cu valorile 2, respectiv 3.

Parcurgând arborele în postordine, putem procesa nodurile expresie binară cu regula – dacă ambii operanzi sunt constante, înlocuiește nodul expresie binară cu nodul constantă întreagă cu valoarea egală cu rezultatul operației. Astfel, ajungând la nodul cu operatorul +, acesta se înlocuiește cu nodul constantă întreagă având valoarea 5 (2 + 3). Din moment ce arborele e parcurs în postordine, nodul cu operația * este procesat ulterior, iar în momentul în care e procesat, și acesta are operanzi două constante astfel că expresia se reduce la un singur nod constantă întreagă cu valoarea 25.

i = 25

Desigur, operațiile ce se pot evalua la compile-time nu sunt neapărat aritmetice. Pot fi concatenări de string-uri, operații logice, egalități etc.

Pe lângă nodurile expresie binară, compilatorul mai procesează în același mod și nodurile expresie unară (expresii cu un singur operand ca minus unar și negare logică), precum și nodurile typecast. Un nod typecast conține tipul rezultat în urma cast-ului, având un singur copil (operand), ce poate fi o constantă, o expresie etc. Expresiei

(int)10.2

îi corespunde nodul typecast ce conține tipul int și un copil, nodul constantă rațională 10.2. Aceste două noduri pot fi înlocuite cu nodul constantă întreagă rezultat în urma evaluării cast-ului. Astfel, în urma unei singure parcurgeri a arborelui, toate expresiile cu operanzi constanți sunt înlocuite cu câte o singură constantă. În implementarea mea, parcurgerea arborelui nu se face exclusiv pentru optimizare astfel că, în același pas, se execută și alte evaluări. Desigur, această optimizare se poate face și pe alte tipuri de reprezentări intermediare.

Alte optimizări (pe care nu le-am implementat) ce merg mână în mână cu constant folding sunt constant propagation și utilizarea identităților algebrice. Constant propagation presupune identificarea variabilelor a căror valoare, într-un anumit punct, poate fi determinată la compile time. De exemplu, pentru

i = 2
j = i + 5

putem determina că valoarea lui i este 2 în momentul efectuării adunării, astfel că i poate fi înlocuit cu constanta întreagă 2, constant folding reducând expresia la

j = 7

eliminând astfel referirea unei variabile și o operație de adunare. Utilizarea identităților algebrice presupune transformarea expresiilor în expresii echivalente ce presupun mai puține operații, de exemplu pentru

j = 2 + i + 4

unde i nu este constant, nodurile din arborele abstract de sinatxă ar fi un nod expresie binară cu operatorul + având copii un nod constantă întreagă 2 și un nod expresie binară cu operatorul + având copii un nod referire la variabilă (i) și un nod constantă întreagă cu valoarea 4. Din moment ce valoarea lui i nu poate fi determinată, constant propagation nu se aplică iar constant folding nu poate identifica nici o expresie având ambii operanzi constanți. Expresia se poate însă rescrie ca

j = i + 2 + 4

care se poate reduce la

j = i + 6

O altă optimizare implementată este, după cum ziceam, dead code elimination. Cea mai evidentă optimizare a procesului este eliminarea din arbore a propozițiilor ce apar după un return. Evaluarea se face la nivel de bloc de cod, unde un bloc de cod este mulțimea propozițiilor cuprinse între două acolade, între begin și end etc. Trebuie avut în vedere însă că nu orice instrucțiune return din cod va fi întotdeauna executată. Dacă aceasta se găsește de exemplu în cadrul unui loop while, se poate întâmpla să nu se îndeplinească condiția de execuție a loop-ului niciodată, deci codul de după loop va fi executat chiar dacă există un return. Codul din interiorul loop-ului ce urmează instrucțiunea return poate fi însă eliminat. Astfel, parcurgând arborele în postordine, se marchează ca noduri ce ies din funcție instrucțiunile return, nodurile ce reprezintă blocuri ce conțin o astfel de instrucțiune și nodurile ce reprezintă construcții branching (if-else), unde e întâlnită o instrucțiune return pe ambele branch-uri. Când se procesează părinții acestor noduri, dacă părinții sunt noduri bloc (noduri ce au ca și copii propoziții), se elimină din arbore toate nodurile care urmează după un nod propoziție marcat ca nod ce iese din funcție. De exemplu

{
    if (a == b)
        return a;
    else
        return b;
    a = b + 5;
    Console.WriteLine(a);
}

poate fi echivalat cu

{
    if (a == b)
        return a;
    else
        return b;
}

Alte optimizări dead code elimination sunt înlocuirea unei construcții if-else, în cazul în care expresia ce reprezintă condiția poate fi evaluată la compile time, cu ramura if (dacă expresia e evaluată la compile time ca adevărată), cu ramura else (dacă e evaluată ca falsă). În cazul în care expresia e evaluată ca falsă și nu există o ramură else, se elimină din arbore toată construcția. Pentru loop-urile while, unde condiția poate fi evaluată la compile time ca falsă, se elimină din arbore întreg loop-ul. Pentru loop-urile do-while, unde condiția poate fi evaluată la compile time ca falsă, se înlocuiește loop-ul cu corpul său (eliminându-se astfel verificarea condiției) – deoarce se știe sigur că acesta va fi executat o singură dată.

do
{
    a = a + 1;
} while (0);

devine

a = a + 1;

Există multe alte optimizări, cum ar fi common subexpression elimination, loop invariant code motion, function inlining etc. despre care nu voi vorbi aici. Un punct bun de start este Dragon Book.

Îmi cer scuze că am prezentat structurile arborescente în cuvinte și nu cu desene dar în ultimele zile am desenat o mulțime de arbori pentru lucrarea de licență și mi-a ajuns🙂

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: