En programación informática , el código invariante de bucles consiste en declaraciones o expresiones (en un lenguaje de programación imperativo ) que se pueden mover fuera del cuerpo de un bucle sin afectar la semántica del programa. El movimiento de código invariante de bucles (también llamado elevación o promoción escalar ) es una optimización del compilador que realiza este movimiento automáticamente.
En el siguiente ejemplo de código, se pueden aplicar dos optimizaciones.
int i = 0 ; mientras ( i < n ) { x = y + z ; a [ i ] = 6 * i + x * x ; ++ i ; } Aunque el cálculo x = y + zy x * xes invariante en bucles, se deben tomar precauciones antes de mover el código fuera del bucle. Es posible que la condición del bucle sea false(por ejemplo, si ntiene un valor negativo), y en tal caso, el cuerpo del bucle no debería ejecutarse en absoluto. Una forma de garantizar un comportamiento correcto es usar una rama condicional fuera del bucle. Evaluar la condición del bucle puede tener efectos secundarios , por lo que una evaluación adicional por parte del ifconstructo debería compensarse reemplazando el whilebucle con un do {} while. Si el código se usa do {} whileen primer lugar, no es necesario todo el proceso de protección, ya que se garantiza que el cuerpo del bucle se ejecutará al menos una vez.
int i = 0 ; si ( i < n ) { x = y + z ; int const t1 = x * x ; hacer { a [ i ] = 6 * i + t1 ; ++ i ; } mientras ( i < n ); } Este código se puede optimizar aún más. Por ejemplo, la reducción de fuerza podría eliminar las dos multiplicaciones dentro del bucle ( 6*iy a[i]), y la eliminación de la variable de inducción podría entonces eludirse ipor completo. Dado que 6 * idebe estar en sintonía consigo imisma, no hay necesidad de tener ambas.
Generalmente, se utiliza un análisis de definiciones de alcance para detectar si una declaración o expresión es invariante al bucle.
Por ejemplo, si todas las definiciones de alcance para los operandos de alguna expresión simple están fuera del bucle, la expresión se puede sacar del bucle.
Trabajos recientes que utilizan el análisis de dependencia del flujo de datos [1] permiten detectar no solo comandos invariantes sino también fragmentos de código más grandes, como un bucle interno. El análisis también detecta cuasi-invariantes de grados arbitrarios, es decir, comandos o fragmentos de código que se vuelven invariantes después de un número fijo de iteraciones del cuerpo del bucle.
El código invariante de bucle que se ha extraído de un bucle se ejecuta con menos frecuencia, lo que proporciona una mayor velocidad. Otro efecto de esta transformación es que permite almacenar constantes en registros y no tener que calcular la dirección ni acceder a la memoria (o línea de caché) en cada iteración.
Sin embargo, si se crean demasiadas variables, habrá una gran presión sobre los registros , especialmente en procesadores con pocos registros, como el x86 de 32 bits . Si el compilador se queda sin registros, se derramarán algunas variables . Para contrarrestar esto, se puede realizar la optimización inversa, la rematerialización .