Un compilator de optimizare este un compilator care folosește diverse metode pentru a obține un cod de program mai optim, menținând în același timp funcționalitatea acestuia. Cele mai comune obiective de optimizare sunt: reducerea timpului de execuție a programului, creșterea performanței, compactarea codului programului, economisirea memoriei, minimizarea costurilor energetice, reducerea numărului de operațiuni I/O .
Optimizarea poate apărea implicit în timpul traducerii unui program, dar este în general considerată un pas separat în munca compilatorului. De asemenea, linkerii pot efectua o parte din optimizări, cum ar fi eliminarea subrutinelor neutilizate sau reordonarea acestora .
Optimizarea este de obicei implementată printr-o serie de transformări de optimizare, algoritmi care preiau un program și îl modifică pentru a produce o variantă echivalentă semantic care este mai eficientă pentru un set de obiective de optimizare. Unele probleme de optimizare a codului s-au dovedit a fi NP-complete [1] , sau chiar indecidabile [2] . Cu toate acestea, practic multe dintre ele sunt rezolvate prin metode euristice, care dau rezultate destul de satisfăcătoare.
Distingeți între optimizarea la nivel scăzut și la nivel înalt. Optimizarea la nivel scăzut transformă programul la nivelul instrucțiunilor elementare, de exemplu, instrucțiuni ale unui procesor cu o anumită arhitectură . Optimizarea la nivel înalt se realizează la nivelul elementelor structurale ale programului, cum ar fi module, funcții, ramuri, cicluri.
Metodele utilizate în optimizări pot fi clasificate după sfera de aplicare: pot afecta atât o singură instrucțiune, cât și un întreg program. Metodele locale (care afectează o mică parte a programului) sunt mai ușor de implementat decât metodele globale (se aplică întregului program), dar metodele globale sunt adesea mai benefice.
Optimizările peephole locale iau în considerare mai multe instrucțiuni adiacente (în ceea ce privește unul dintre graficele reprezentării programului) (ca și cum ar fi „privind prin vizor ” la cod) pentru a vedea dacă este posibil să se efectueze vreo transformare cu ele în ceea ce privește optimizarea poartă. În special, ele pot fi înlocuite cu o singură instrucțiune sau cu o secvență mai scurtă de instrucțiuni.
De exemplu, dublarea unui număr se poate face mai eficient folosind o schimbare la stânga sau prin adăugarea numărului la același.
În optimizarea locală, sunt luate în considerare doar informațiile unui bloc de bază pe pas [3] . Deoarece nu există tranziții ale fluxului de control în blocurile de bază , aceste optimizări necesită puțină analiză (economisirea timpului și reducerea cerințelor de memorie), dar înseamnă, de asemenea, că nu sunt stocate informații pentru următorul pas.
Optimizările intraprocedurale ( engleză intraprocedural ) sunt optimizări globale care sunt efectuate în întregime în cadrul unei unități de traducere (de exemplu, funcții sau proceduri) [4] . Cu o astfel de optimizare, sunt implicate mult mai multe informații decât în cea locală, ceea ce vă permite să obțineți efecte mai semnificative, dar acest lucru necesită adesea calcule care consumă mult resurse. Dacă există variabile globale în unitatea de program care este optimizată, optimizarea de acest fel poate fi dificilă.
Există un număr mare de optimizări aplicate buclelor. Cu un număr mare de iterații ale buclei, astfel de optimizări sunt extrem de eficiente, deoarece o parte semnificativă a execuției programului este afectată de o mică transformare. Deoarece buclele reprezintă o parte semnificativă a timpului de execuție al multor programe, optimizările buclelor există în aproape toate compilatoarele și sunt cele mai importante.
De exemplu, prin identificarea invarianților buclei , uneori este posibil să eliminați unele operații din buclă pentru a nu efectua calcule repetate redundante.
Astfel de tipuri de optimizări analizează simultan întregul cod sursă al programului. Cantitatea mai mare de informații extrase prin aceste metode înseamnă că optimizările pot fi mai eficiente decât alte metode. Astfel de optimizări pot folosi metode destul de complexe, de exemplu, un apel de funcție este înlocuit cu o copie a corpului funcției (inline sau inline).
Exemplu Să fie o funcție:
int pred ( int x ) { dacă ( x == 0 ) returnează 0 ; altfel întoarcere x - 1 ; }Înainte de a-l încorpora, codul arăta astfel:
int f ( int y ) { return pred ( y ) + pred ( 0 ) + pred ( y + 1 ); }După optimizare:
int f ( int y ) { int temp = 0 ; dacă ( y == 0 ) temp += 0 ; else temp += y - 1 ; /* (unu) */ dacă ( 0 == 0 ) temp += 0 ; else temp += 0 - 1 ; /* (2) */ dacă ( y + 1 == 0 ) temp += 0 ; else temp += ( y + 1 ) - 1 ; /* (3) */ temperatura de retur ; }Încorporarea funcției elimină supraîncărcarea asociată apelurilor de funcții. În plus, după inline, este posibil să se aplice optimizări intra-procedurale care au fost imposibil sau prea greu de implementat înainte. Cu toate acestea, inlining-ul are dezavantajele sale, ca aproape orice optimizare - crește dimensiunea statică a codului, ceea ce poate duce la efecte negative în părțile echipamentului care sunt sensibile la acest factor.
Printre factorii care influențează optimizarea, atât caracteristicile de calcul ale mașinii țintă (de exemplu, numărul și viteza de ceas a nucleelor de procesor, dimensiunea memoriei cache a procesorului , lățimea de bandă a magistralei sistemului , cantitatea de RAM), cât și arhitectura țintei. procesor (în special, în diferite arhitecturi sunt disponibile un număr diferit de registre de uz general, conducta de calcul este implementată diferit ). O altă clasă de factori care afectează optimizarea sunt scenariile de utilizare a codului țintă, de exemplu, țintele de optimizare pot varia semnificativ pentru codul de depanare și testare, rulare ocazională, utilizare continuă, aplicații încorporate sau independente.
Printre principiile de optimizare utilizate în diferite metode de optimizare din compilatoare (unele dintre ele se pot contrazice sau pot fi inaplicabile pentru diferite obiective de optimizare):
Optimizările fluxului de date se bazează pe analiza fluxului de date și de obicei iau în considerare graficul fluxului de control și graficul fluxului de date conectate între ele ca date de intrare, precum și adesea arborele buclei și etichetarea buclei a graficului fluxului de control. Analizând, în special, propagarea informațiilor, pe aceste grafice, se relevă posibilitatea de optimizare în ceea ce privește obiectivele dorite, iar apoi se aplică optimizările.
Eliminarea subexpresiilor comune Eliminarea subexpresiilor comune este o optimizare a compilatorului care caută instanțe de expresii identice și analizează posibilitatea înlocuirii lor cu o singură variabilă care conține valoarea calculată. Convoluția constantelor Optimizări care reduc calculele redundante prin înlocuirea expresiilor și variabilelor constante cu valorile acestora. Analiza variabilelor inductive ( ing. Analiza variabilelor de inducție ) Consultați descrierea în Optimizarea ciclului . Ștergerea înregistrărilor fără margini Ștergeți atribuirile variabilelor care nu sunt citite ulterior. Atribuirea este eliminată fie pentru că variabila nu a fost citită înainte de sfârșitul duratei de viață a variabilei, fie pentru că o atribuire ulterioară o va suprascrie.SSA (Single Static Assignment, Single Static Assignment) este o formă de reprezentare Data Flow Graph (DFG) în care fiecărei variabile i se atribuie o valoare o singură dată. Acest lucru evită multiplicarea arcurilor în grafic în timpul scrierilor și citirilor multiple ale unei variabile și facilitează analiza graficului. Pentru a face acest lucru, vizualizarea SSA introduce funcții Phi speciale (noduri ale graficului fluxului de date) în unele puncte de convergență din graficul fluxului de control. Aceste noi noduri sunt așa-numitele pseudo-atribuții.
Definițiile multiple sunt posibile nu numai datorită convergențelor fluxului de control ("sau"), ci și datorită posibilității de a citi o valoare compozită ca întreg, care a fost scrisă în părți prin mai multe operații ("și"). În acest caz, pentru a menține forma SSA, în interiorul blocurilor de bază sunt introduse pseudo-atribuții suplimentare, care colectează o valoare din mai multe.
Unele optimizări se bazează pe SSA. Deși unele dintre ele pot funcționa fără SSA, ele sunt cele mai eficiente atunci când SSA este prezent.