Movimiento de código invariante en bucle
 | Este artículo necesita citas adicionales para su verificación . ( enero de 2021 ) |
En programación de computadoras , el código invariante de bucle 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 en bucle (también llamado elevación o promoción escalar ) es una optimización del compilador que realiza este movimiento automáticamente.
Ejemplo
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 el ciclo, se deben tomar precauciones antes de mover el código fuera del ciclo. 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 el comportamiento correcto es utilizar una rama condicional fuera del ciclo. La evaluación de la condición del bucle puede tener efectos secundarios , por lo que una evaluación adicional por parte del ifconstructo debe compensarse reemplazando el whilebucle con a do {} while. Si el código se usó do {} whileen primer lugar, no se necesita 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 la 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 eliminarse por icompleto. Dado que 6 * idebe estar en sintonía consigo imismo, no es necesario tener ambos.
Detección de código invariante
Por lo general, se utiliza un análisis de definición de alcance para detectar si una declaración o expresión es invariante en bucle.
Por ejemplo, si todas las definiciones de alcance para los operandos de alguna expresión simple están fuera del ciclo, la expresión se puede mover fuera del ciclo.
Un trabajo reciente que utiliza el análisis de dependencia del flujo de datos [1] permite detectar no solo comandos invariantes sino 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.
Beneficios
El código invariante de bucle que se ha sacado de un bucle se ejecuta con menos frecuencia, lo que proporciona una aceleración. Otro efecto de esta transformación es permitir que las constantes se almacenen en registros y no tener que calcular la dirección y acceder a la memoria (o línea de caché) en cada iteración.
Sin embargo, si se crean demasiadas variables, habrá una alta presión de registro , 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, rematerialización .
Ver también
Otras lecturas
- Aho, Alfred V .; Sethi, Ravi; Y Ullman, Jeffrey D. (1986). Compiladores: principios, técnicas y herramientas. Addison Wesley. ISBN 0-201-10088-6 .
Referencias
- ^ Moyen, Jean-Yves; Rubiano, Thomas; Seiller, Thomas (2017). "Detección de fragmentos cuasi-invariantes de bucle". Tecnología automatizada para verificación y análisis . 10482 : 91-108. doi : 10.1007 / 978-3-319-68167-2_7 .
enlaces externos
