Variable de inducción

En informática , una variable de inducción es una variable que aumenta o disminuye en una cantidad fija en cada iteración de un bucle o es una función lineal de otra variable de inducción. ^[1]

Por ejemplo, en el siguiente bucle, iy json variables de inducción:

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

Una optimización común del compilador es reconocer la existencia de variables de inducción y reemplazarlas con cálculos más simples; por ejemplo, el código anterior podría ser reescrito por el compilador de la siguiente manera, asumiendo que la adición de una constante será más barata que una multiplicación.

j = -17 ;  

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

Esta optimización es un caso especial de reducción de fuerza .

En algunos casos, es posible revertir esta optimización para eliminar por completo una variable de inducción del código. Por ejemplo:

extern int suma ;  

int foo ( int n ) { int j = 5 ;   
       

    para ( int i = 0 ; i < n ; ++ i ) { j += 2 ; suma += j ; }         
          
          
    

    devuelve suma ; } 

El bucle de esta función tiene dos variables de inducción: iy j. Cualquiera de ellas puede reescribirse como una función lineal de la otra; por lo tanto, el compilador puede optimizar este código como si hubiera sido escrito

extern int suma ;  

int foo ( int n ) { para ( int i = 0 ; i < n ; ++ i ) { suma += 5 + 2 * ( i + 1 ); }   
             
                
    

    devuelve suma ; } 

La sustitución de variables por inducción es una transformación del compilador para reconocer variables que pueden expresarse como funciones de los índices de los bucles circundantes y reemplazarlas con expresiones que involucran índices de bucles.

Esta transformación hace explícita la relación entre las variables y los índices de bucle, lo que ayuda a otros análisis del compilador, como el análisis de dependencia .

Ejemplo:

Código de entrada:

int c = 10 ;   

for ( int i = 0 ; i < 10 ; i ++ ) { c = c + 5 ; // c se incrementa en 5 para cada iteración del bucle }         
         

Código de salida

int c = 10 ;   

for ( int i = 0 ; i < 10 ; i ++ ) { c = 10 + 5 * ( i + 1 ); // c se expresa explícitamente como una función del índice del bucle }         
              

Las mismas optimizaciones se pueden aplicar a variables de inducción que no son necesariamente funciones lineales del contador de bucle; por ejemplo, el bucle

j = 1 ;  

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

Puede convertirse en

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

• Inducción matemática

• Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. (1986), Compiladores: principios, técnicas y herramientas (2.ª ed.), ISBN 978-0-201-10088-4
• Allen, Francis E.; Cocke, John ; Kennedy, Ken (1981), "Reducción de la fuerza del operador", en Munchnik, Steven S.; Jones, Neil D. (eds.), Análisis del flujo de programas: teoría y aplicaciones , Prentice-Hall, ISBN 978-0-13-729681-1
• Cocke, John ; Kennedy, Ken (noviembre de 1977), "Un algoritmo para la reducción de la fuerza del operador", Communications of the ACM , 20 (11): 850–856, doi : 10.1145/359863.359888 , S2CID  1092505
• Cooper, Keith; Simpson, Taylor; Vick, Christopher (1995), Reducción de la fuerza del operador (PDF) , Rice University , consultado el 22 de abril de 2010