Eliminarea subexpresiilor comune ( ing. Eliminarea subexpresiilor comune sau CSE) este o optimizare a compilatorului care caută calcule în program care sunt efectuate de mai multe ori în secțiunea luată în considerare și elimină a doua și următoarele operații identice, dacă este posibil și eficient . Această optimizare necesită analiza fluxului de datepentru găsirea calculelor redundante și aproape întotdeauna îmbunătățește timpul de execuție a programului atunci când este aplicat [1] .
O subexpresie dintr-un program se numește subexpresie comună dacă există o altă astfel de subexpresie care este întotdeauna evaluată înaintea celei date, iar operanzii nu se schimbă între evaluări. De exemplu, în exemplul de mai jos, expresia b * c este o subexpresie generală.
Pe baza acestei definiții, eliminarea subexpresiilor comune este o transformare care elimină evaluarea repetată a subexpresiilor comune și le înlocuiește cu utilizarea valorii stocate după prima evaluare. Cu toate acestea, în exemplul luat în considerare, este imposibil să se înlocuiască imediat subexpresia comună cu valoarea variabilei a atunci când se calculează d, deoarece această variabilă se poate modifica între calculele în cauză.
Luați în considerare următorul fragment de cod:
a = b * c + g ; d = b * c * d _I se aplică următoarea transformare:
tmp = b * c ; a = tmp + g ; d = tmp * d ;care va fi eficient dacă timpul total pentru scriere și mai multe citiri ale noii variabile „tmp” este mai mic decât timpul total petrecut evaluând expresia „b * c” de fiecare dată când aceasta apare în cod.
Există două tipuri de această optimizare:
Ambele optimizări se bazează pe analiza fluxului de date, timp în care se determină disponibilitatea expresiei în fiecare punct al programului.
Aplicația de optimizare se bazează pe analiza expresiilor disponibile . O expresie x + yeste disponibilă la un moment dat în pprogram dacă: [2]
Eficiența conversiei este determinată în principal de faptul că timpul total de scriere și mai multe citiri ale noii variabile „tmp” se dovedește a fi mai mic decât timpul total petrecut pentru evaluarea expresiei „b * c” de fiecare dată când apare în cod. În practică, o serie de alți factori afectează, de asemenea, eficiența finală, în special distribuția variabilelor între registre .
În cazuri simple, precum cel discutat mai sus, duplicarea calculelor expresiilor aritmetice este eliminată. Această optimizare este cea mai semnificativă pentru reprezentarea internă a compilatorului, de exemplu, atunci când se calculează indici de matrice, unde optimizarea manuală este foarte dificilă sau imposibilă. În unele limbaje de programare, este posibil să se formeze multe calcule identice. De exemplu, macro -urile din limbajul C, care în codul sursă nu formează aceleași expresii, dar după înlocuirea numelui macro în timpul procesării de către preprocesor cu o secvență de instrucțiuni de program, pot apărea astfel.
În cazul unei aplicări globale a optimizării, criteriile suplimentare afectează beneficiul. De exemplu, este necesar să se țină seama de contoarele de execuție ale blocurilor de bază, deoarece prin reducerea numărului static de evaluări de expresie, puteți crește numărul dinamic, ceea ce afectează negativ numărul de operații efectuate în program. Acest lucru duce la faptul că optimizarea inversă legată de clasa PRE (eliminare parțială a redundanței) poate fi benefică.