Variabilă inductivă

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 6 mai 2020; verificările necesită 2 modificări .

O  variabilă inductivă este o variabilă în cicluri ale cărei valori succesive formează o progresie aritmetică. Cel mai comun exemplu este contorul de bucle. Variabilele inductive sunt adesea folosite în expresiile de index matrice.

De exemplu, în exemplul următor, iși jsunt variabile inductive:

pentru ( i = 0 ; i < 10 ; i ++ ) { j = 17 * i ; }

Metodele tradiționale de optimizare implică recunoașterea variabilelor inductive și eliminarea lor din buclă.

Aplicație pentru reducerea costurilor operațiunilor

Principiul general de optimizare este recunoașterea variabilelor inductive și înlocuirea lor cu calcule simple. De exemplu, codul de mai sus ar putea fi modificat de un compilator de optimizare , pe baza presupunerii că adunarea constantă ar fi mai ieftină decât înmulțirea:

j = -17 ; pentru ( i = 0 ; i < 10 ; i ++ ) { j = j + 17 _ }

Această aplicație este un caz special de optimizare a reducerii costurilor .

Aplicație pentru reducerea presiunii asupra registrelor

În unele cazuri, puteți utiliza această optimizare pentru a elimina complet variabila inductivă din cod. De exemplu:

extern int sum ; int foo ( int n ) { int i , j ; j = 5 _ pentru ( i = 0 ; i < n ; i ++ ) { j += 2 ; suma += j ; } suma returnata ; _ }

Bucla din funcție are două variabile inductive: iși j. Unul dintre ele poate fi reprezentat ca o funcție liniară a celuilalt, astfel încât compilatorul poate optimiza acest cod după cum urmează:

extern int sum ; int foo ( int n ) { int i ; pentru ( i = 0 ; i < n ; i ++ ) { suma += ( 5 + 2 * ( i + 1 )); } suma returnata ; _ }

Modificarea variabilei inductive

O substituție inductivă de variabilă este o transformare care recunoaște variabilele care pot fi reprezentate în funcție de un indice de buclă și le înlocuiește cu expresiile corespunzătoare. Această conversie face relațiile dintre variabile și indicii buclei explicite, ceea ce ajută la alte optimizări ale compilatorului. Luați în considerare un exemplu:

int c , i ; c = 10 _ pentru ( i = 0 ; i < 10 ; i ++ ) { c = c + 5 ; // c crește cu 5 la fiecare iterație a buclei }

În conformitate cu metoda descrisă mai sus, obținem următoarea reprezentare a codului sursă:

int c , i ; c = 10 _ pentru ( i = 0 ; i < 10 ; i ++ ) { c = 10 + 5 * ( i + 1 ); // c este o funcție a indexului }

Variabile inductive neliniare

Aceleași optimizări pot fi aplicate variabilelor inductive care nu sunt funcții liniare ale contorului de bucle. De exemplu, următorul cod:

j = 1 _ pentru ( i = 0 ; i < 10 ; i ++ ) { j = j << 1 ; }

poate fi convertit:

pentru ( i = 0 ; i < 10 ; i ++ ) { j = 1 << i + 1 ; }

Note

Literatură

  • Alfred Aho, Monica Lam, Ravi Seti, Jeffrey Ullman. Compilatoare : Principles, Techniques, and Tools = Compilatoare: Principles, Techniques, and Tools. — ediția a II-a. - M . : „Williams”, 2008. - 1184 p. - 1500 de exemplare.  - ISBN 978-5-8459-1349-4 .
  • Steven S. Muchnick. Proiectare și implementare avansată a compilatorului. — ediția a 5-a. - San Francisco: Morgan Kaufmann Publishers , 1997. - 856 p. - ISBN 1-55860-320-4 .
  • Kennedy, Ken; și Allen, Randy. Optimizarea compilatoarelor pentru arhitecturi moderne: o abordare bazată pe dependență  . - Morgan Kaufmann , 2001. - ISBN 1-55860-286-0 .
  • Allen, Francis E.; Cocke, John & Kennedy, Ken (1981), Reducerea puterii operatorului, în Munchnik, Steven S. & Jones, Neil D., Program Flow Analysis: Theory and Applications , Prentice-Hall, ISBN 978-0-13-729681- unu 
  • Cocke, John & Kennedy, Ken (noiembrie 1977), Un algoritm pentru reducerea puterii operatorului, Communications of the ACM vol . 20 (11) 
  • Cooper, Keith; Simpson, Taylor & Vick, Christopher (1995), Operator Strength Reduction , Rice University , < http://softlib.rice.edu/pub/CRPC-TRs/reports/CRPC-TR95635-S.pdf > . Preluat la 22 aprilie 2010.