Hispanopedia WikiEn la teoría de compiladores , la eliminación de subexpresiones comunes ( CSE ) es una optimización del compilador que busca instancias de expresiones idénticas (es decir, que todas se evalúan al mismo valor) y analiza si vale la pena reemplazarlas con una sola variable que contenga el valor calculado. [ 1 ]
Ejemplo
En el siguiente código:
a = b * c + g; d = b * c * e;
Puede que valga la pena transformar el código a:
tmp = b * c; a = tmp + g; d = tmp * e;
si el costo de almacenamiento y recuperación tmpes menor que el costo de calcular b * cun tiempo adicional.
Principio
La posibilidad de realizar CSE se basa en el análisis de expresiones disponibles (un análisis de flujo de datos ). Una expresión b*cestá disponible en un punto p de un programa si:
- cada ruta desde el nodo inicial hasta p se evalúa
b*cantes de llegar a p , - y no hay asignaciones para
bocdespués de la evaluación pero antes de p .
El análisis de costo/beneficio realizado por un optimizador calculará si el costo de almacenamiento tmpes menor que el costo de la multiplicación; en la práctica, otros factores como qué valores se almacenan en qué registros también son importantes.
Los escritores de compiladores distinguen dos tipos de CSE:
- La eliminación de subexpresiones comunes locales funciona dentro de un único bloque básico.
- La eliminación global de subexpresiones comunes funciona en todo un procedimiento,
Ambos tipos se basan en el análisis del flujo de datos para determinar qué expresiones están disponibles en qué puntos de un programa.
Beneficios
Los beneficios de realizar CSE son tan grandes que se trata de una optimización de uso común.
En casos sencillos como el del ejemplo anterior, los programadores pueden eliminar manualmente las expresiones duplicadas al escribir el código. La principal fuente de expresiones duplicadas son las secuencias de código intermedias generadas por el compilador, como las utilizadas para los cálculos de indexación de matrices , donde el desarrollador no puede intervenir manualmente. En algunos casos, las características del lenguaje pueden generar muchas expresiones duplicadas. Por ejemplo, las macros de C , donde la expansión de macros puede dar lugar a subexpresiones comunes que no aparecen en el código fuente original.
Los compiladores deben ser prudentes con la cantidad de variables temporales que crean para almacenar valores. Un número excesivo de valores temporales genera presión en los registros, lo que puede provocar que estos se sobrescriban en la memoria, un proceso que puede tardar más que simplemente recalcular el resultado de una operación aritmética cuando sea necesario.
Véase también
Referencias
- Steven S. Muchnick , Diseño e implementación de compiladores avanzados ( Morgan Kaufmann , 1997), págs. 378-396
- John Cocke . "Eliminación global de subexpresiones comunes". Actas de un simposio sobre construcción de compiladores , ACM SIGPLAN Notices 5(7), julio de 1970, páginas 850–856.
- Briggs, Preston, Cooper, Keith D., y Simpson, L. Taylor. " Numeración de valores ". Software-Practice and Experience , 27(6), junio de 1997, páginas 701-724.
- Optimizaciones del compilador
