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 ; }             

Aplicación a la reducción de fuerza

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 .

Aplicación para reducir la presión del registro

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 ; } 

Sustitución de variable por inducción

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 }                   

Variables de inducción no lineal

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 ); }             

Véase también

• Inducción matemática

Referencias

1. Steven Muchnick; Muchnick and Associates (15 de agosto de 1997). Implementación del diseño avanzado de compiladores . Morgan Kaufmann. ISBN 978-1-55860-320-2. variable de inducción.

Lectura adicional

• 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