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, i
y j
son 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: i
y 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 ); }
variable de inducción.