Induktiv variabel

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 6 maj 2020; kontroller kräver 2 redigeringar .

En  induktiv variabel är en variabel i cykler vars successiva värden bildar en aritmetisk progression. Det vanligaste exemplet är loopräknaren. Induktiva variabler används ofta i arrayindexuttryck.

Till exempel, i följande exempel, ioch jär induktiva variabler:

för ( i = 0 ; i < 10 ; i ++ ) { j = 17 * i ; }

Traditionella optimeringsmetoder innebär att känna igen induktiva variabler och ta bort dem från slingan.

Ansökan för att minska kostnaderna för operationer

Den allmänna optimeringsprincipen är att känna igen induktiva variabler och ersätta dem med enkla beräkningar. Till exempel kan koden ovan modifieras av en optimeringskompilator , baserat på antagandet att konstant addition skulle vara billigare än multiplikation:

j = -17 ; för ( i = 0 ; i < 10 ; i ++ ) { j = j + 17 _ }

Denna applikation är ett specialfall av kostnadsreduktionsoptimering .

Applikation för att minska trycket på register

I vissa fall kan du använda denna optimering för att helt ta bort den induktiva variabeln från din kod. Till exempel:

extern int summa ; int foo ( int n ) { int i , j ; j = 5 _ för ( i = 0 ; i < n ; i ++ ) { j += 2 ; summa += j ; } retursumma ; _ }

Slingan i funktionen har två induktiva variabler: ioch j. En av dem kan representeras som en linjär funktion av den andra, så kompilatorn kan optimera denna kod enligt följande:

extern int summa ; int foo ( int n ) { int i ; för ( i = 0 ; i < n ; i ++ ) { summa += ( 5 + 2 * ( i + 1 )); } retursumma ; _ }

Ändring av induktiv variabel

En induktiv variabelsubstitution är en transformation som känner igen variabler som kan representeras som en funktion av ett loopindex och ersätter dem med motsvarande uttryck. Denna konvertering gör relationerna mellan variabler och loopindex explicita, vilket hjälper andra kompilatoroptimeringar. Tänk på ett exempel:

int c , i ; c = 10 _ för ( i = 0 ; i < 10 ; i ++ ) { c = c + 5 ; // c ökar med 5 på varje iteration av loopen }

I enlighet med metoden som beskrivs ovan får vi följande representation av källkoden:

int c , i ; c = 10 _ för ( i = 0 ; i < 10 ; i ++ ) { c = 10 + 5 * ( i + 1 ); // c är en funktion av index }

Icke-linjära induktiva variabler

Samma optimeringar kan tillämpas på induktiva variabler som inte är linjära funktioner hos loopräknaren. Till exempel följande kod:

j = 1 _ för ( i = 0 ; i < 10 ; i ++ ) { j = j << 1 ; }

kan konverteras:

för ( i = 0 ; i < 10 ; i ++ ) { j = 1 << i + 1 ; }

Anteckningar

Litteratur

  • Alfred Aho, Monica Lam, Ravi Seti, Jeffrey Ullman. Compilers : Principles, Techniques and Tools = Compilers: Principles, Techniques and Tools. — 2:a upplagan. - M . : "Williams", 2008. - 1184 sid. - 1500 exemplar.  - ISBN 978-5-8459-1349-4 .
  • Steven S. Muchnick. Avancerad kompilatordesign och implementering. — 5:e upplagan. - San Francisco: Morgan Kaufmann Publishers , 1997. - 856 sid. - ISBN 1-55860-320-4 .
  • Kennedy, Ken; & Allen, Randy. Optimera kompilatorer för moderna arkitekturer: en beroendebaserad metod  . - Morgan Kaufmann , 2001. - ISBN 1-55860-286-0 .
  • Allen, Francis E.; Cocke, John & Kennedy, Ken (1981), Reduction of Operator Strength, i Munchnik, Steven S. & Jones, Neil D., Program Flow Analysis: Theory and Applications , Prentice-Hall, ISBN 978-0-13-729681- ett 
  • Cocke, John & Kennedy, Ken (november 1977), En algoritm för minskning av operatörsstyrka, 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 > . Hämtad 22 april 2010.