En la teoría del compilador , la eliminación de subexpresiones comunes ( CSE ) es una optimización del compilador que busca instancias de expresiones idénticas (es decir, todas evalúan el mismo valor) y analiza si vale la pena reemplazarlas con una sola variable que contenga el valor calculado. [1]
En el siguiente código:
a = b * c + g;d = b * c * e;
Puede que valga la pena transformar el código a:
tiempo = b * c;a = tiempo + g;d = tiempo * e;
si el coste de almacenamiento y recuperación tmpes menor que el coste de calcular b * cun tiempo extra.
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 en un programa si:
b*cantes de llegar a p ,bo cdespués de la evaluación sino antes de p .El análisis costo/beneficio realizado por un optimizador calculará si el costo de almacenar tmpes menor que el costo de la multiplicación; en la práctica, otros factores como qué valores se guardan en qué registros también son significativos.
Los escritores de compiladores distinguen dos tipos de CSE:
Ambos tipos se basan en el análisis del flujo de datos para saber qué expresiones están disponibles en qué puntos de un programa.
Los beneficios de realizar CSE son tan grandes que se trata de una optimización de uso común.
En casos simples como el del ejemplo anterior, los programadores pueden eliminar manualmente las expresiones duplicadas mientras escriben el código. La mayor fuente de errores comunes de ejecución son las secuencias de código intermedias generadas por el compilador, como los cálculos de indexación de matrices , donde no es posible que el desarrollador intervenga manualmente. En algunos casos, las características del lenguaje pueden crear muchas expresiones duplicadas. Por ejemplo, las macros de C , donde las expansiones de macros pueden dar como resultado subexpresiones comunes que no son evidentes en el código fuente original.
Los compiladores deben ser prudentes con la cantidad de valores temporales que crean para almacenar valores. Una cantidad excesiva de valores temporales genera una presión en los registros que puede provocar que se derramen registros en la memoria, lo que puede llevar más tiempo que simplemente volver a calcular un resultado aritmético cuando es necesario.
Eliminación de subexpresiones comunes.