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 consiste en reconocer la existencia de variables de inducción y reemplazarlas por cálculos más sencillos; por ejemplo, el código anterior podría ser reescrito por el compilador de la siguiente manera, bajo el supuesto de que la suma de una constante será más económica 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 ; }devolver 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 se hubiera escrito

extern int suma ;int foo ( int n ) { for ( int i = 0 ; i < n ; ++ i ) { sum += 5 + 2 * ( i + 1 ); }devolver suma ; }

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

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

Ejemplo:

Código de entrada:

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

Código de salida

entero 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) , Universidad Rice , consultado el 22 de abril de 2010.