En informática , la propagación constante condicional dispersa es una optimización que se aplica con frecuencia en los compiladores después de la conversión a la forma estática de asignación única (SSA). Simultáneamente elimina algunos tipos de código inactivo y propaga constantes a través de un programa. Además, puede encontrar valores más constantes y, por lo tanto, más oportunidades de mejora que aplicando por separado eliminación de código muerto y propagación constante en cualquier orden o cualquier número de repeticiones. [1] [2]
El algoritmo funciona realizando una interpretación abstracta del código en forma SSA. Durante la interpretación abstracta, normalmente utiliza una red plana de constantes para los valores y un entorno global que asigna las variables SSA a los valores de esta red. El quid del algoritmo reside en cómo maneja la interpretación de las instrucciones de bifurcación . Cuando se encuentra, la condición de una rama se evalúa de la mejor manera posible.dada la precisión de los valores abstractos ligados a variables en la condición. Puede darse el caso de que los valores sean perfectamente precisos (ni superior ni inferior) y, por tanto, la ejecución abstracta puede decidir en qué dirección bifurcar. Si los valores no son constantes, o una variable en la condición no está definida, entonces se deben tomar ambas direcciones de bifurcación para permanecer conservadoras.
Una vez completada la interpretación abstracta, las instrucciones que nunca se alcanzaron se marcan como código muerto. Las variables SSA que tienen valores constantes pueden entonces insertarse (propagarse a) su punto de uso. [ ejemplo necesario ]
Notas
- ^ Wegman, Mark N. y Zadeck, F. Kenneth. " Propagación constante con ramas condicionales ". ACM Transactions on Programming Languages and Systems , 13 (2), abril de 1991, páginas 181-210.
- ^ Haga clic en, Clifford y Cooper, Keith. " Combinación de análisis, combinación de optimizaciones ", Transacciones de ACM en lenguajes y sistemas de programación , 17 (2), marzo de 1995, páginas 181-196
Referencias
- Cooper, Keith D. y Torczon, Linda. Ingeniería de un compilador . Morgan Kaufmann. 2005.