Induktionsvariabel

Inom datavetenskap är en induktionsvariabel en variabel som ökas eller minskas med ett fast belopp vid varje iteration av en loop eller är en linjär funktion av en annan induktionsvariabel.

Till exempel, i följande slinga är i och j induktionsvariabler:

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

Applikation för styrka reduktion

En vanlig kompilatoroptimering är att känna igen förekomsten av induktionsvariabler och ersätta dem med enklare beräkningar; till exempel skulle koden ovan kunna skrivas om av kompilatorn enligt följande, under antagandet att tillägget av en konstant blir billigare än en multiplikation.

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

Denna optimering är ett specialfall av hållfasthetsminskning .

Applikation för att minska registertrycket

I vissa fall är det möjligt att vända denna optimering för att helt ta bort en induktionsvariabel från koden. Till exempel:

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

Denna funktions loop har två induktionsvariabler: i och j . Antingen kan den ena skrivas om som en linjär funktion av den andra; därför kan kompilatorn optimera denna kod som om den hade skrivits

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

Induktionsvariabel substitution

Induktionsvariabelsubstitution är en kompilatortransformation för att känna igen variabler som kan uttryckas som funktioner av indexen för omslutande loopar och ersätta dem med uttryck som involverar loopindex.

Denna transformation gör förhållandet mellan variablerna och loopindex explicit, vilket hjälper andra kompilatoranalyser, såsom beroendeanalys .

Exempel:

Inmatningskod:

  
  
   0     
         
 int  c  ,  i  ;  c  =  10  ;  för  (  i  =  ;  i  <  10  ;  i  ++  )  {  c  =  c  +  5  ;  // c ökas med 5 för varje loop-iteration  } 

Utdatakod

  
  
   0     
              
 int  c  ,  i  ;  c  =  10  ;  för  (  i  =  ;  i  <  10  ;  i  ++  )  {  c  =  10  +  5  *  (  i  +  1  );  // c uttrycks uttryckligen som en funktion av loopindex  } 

Icke-linjära induktionsvariabler

Samma optimeringar kan tillämpas på induktionsvariabler som inte nödvändigtvis är linjära funktioner hos loopräknaren; till exempel slingan

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

kan konverteras till

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

Se även

• Matematisk induktion

Vidare läsning

•   Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. (1986), Compilers: Principles, Techniques, and Tools (2nd ed.), ISBN 978-0-201-10088-4
•   Allen, Francis E.; Cocke, John ; Kennedy, Ken (1981), "Reduction of Operator Strength", i Munchnik, Steven S.; Jones, Neil D. (red.), Program Flow Analysis: Theory and Applications , Prentice-Hall, ISBN 978-0-13-729681-1
•   Cocke, John ; Kennedy, Ken (november 1977), "An algorithm for reduction of operator strength", Communications of the ACM , 20 (11): 850–856, doi : 10.1145/359863.359888 , S2CID 1092505
• Cooper, Keith; Simpson, Taylor; Vick, Christopher (1995), Operator Strength Reduction (PDF) , Rice University , hämtad 22 april 2010