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 ciclo o es una función lineal de otra variable de inducción. [1]
Por ejemplo, en el siguiente ciclo, i
y j
son variables de inducción:
para ( i = 0 ; i < 10 ; ++ i ) { j = 17 * i ; }
Aplicación a la reducción de la 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 compilador podría reescribir el código anterior 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 la fuerza .
Aplicación para reducir la presión del registro
En algunos casos, es posible revertir esta optimización para eliminar una variable de inducción del código por completo. Por ejemplo:
extern int suma ; int foo ( int n ) { int i , j ; j = 5 ; para ( i = 0 ; i < n ; ++ i ) { j + = 2 ; suma + = j ; } devolución de suma ; }
El ciclo de esta función tiene dos variables de inducción: i
y j
. Cualquiera de los dos puede reescribirse como una función lineal del otro; por lo tanto, el compilador puede optimizar este código como si hubiera sido escrito
extern int suma ; int foo ( int n ) { int i ; para ( i = 0 ; i < n ; ++ i ) { suma + = 5 + 2 * ( i + 1 ); } devolución de suma ; }
Sustitución de variables de inducción
La sustitución de variables de inducción es una transformación del compilador para reconocer variables que pueden expresarse como funciones de los índices de bucles circundantes y reemplazarlas con expresiones que involucran índices de bucles.
Esta transformación hace que la relación entre las variables y los índices de bucle sea explícita, lo que ayuda a otros análisis de compiladores, como el análisis de dependencia .
Ejemplo:
Codigo de entrada:
int c , i ; c = 10 ; para ( i = 0 ; i < 10 ; i ++ ) { c = c + 5 ; // c se incrementa en 5 para cada iteración del ciclo }
Código de salida
int c , i ; c = 10 ; para ( i = 0 ; i < 10 ; i ++ ) { c = 10 + 5 * ( i + 1 ); // c se expresa explícitamente como una función del índice de bucle }
Variables de inducción no lineales
Las mismas optimizaciones se pueden aplicar a las 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 ; }
se puede convertir a
para ( i = 0 ; i < 10 ; ++ i ) { j = 1 << ( i + 1 ); }
Ver también
Referencias
- ^ Steven Muchnick; Muchnick y Asociados (15 de agosto de 1997). Implementación avanzada del diseño del compilador . Morgan Kaufmann. ISBN 978-1-55860-320-2.
variable de inducción.
Otras lecturas
- Aho, Alfred V .; Sethi, Ravi; Ullman, Jeffrey D. (1986), Compiladores: Principios, técnicas y herramientas (2a 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.), Program Flow Analysis: Theory and Applications , 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", Comunicaciones del ACM , 20 (11), doi : 10.1145 / 359863.359888
- Cooper, Keith; Simpson, Taylor; Vick, Christopher (1995), Operator Strength Reduction (PDF) , Rice University , consultado el 22 de abril de 2010