Implementación de la eliminación de subexpresiones comunes

Estoy buscando implementar la eliminación de subexpresiones (CSE) común para gráficos de expresiones correspondientes a expresiones matemáticas grandes (millones de nodos).Implementación de la eliminación de subexpresiones comunes

¿Qué algoritmos son adecuados para realizar esto? Estaba buscando en Internet un algoritmo fácil de implementar, pero no pude encontrar nada. Si es posible, el algoritmo debería tener una complejidad lineal en el número de nodos del gráfico de expresión completo.

Fuente

2012-07-04 Joel

Esta representación puede ayudar: http://www.masonchang.com/blog/2010/8/9/sea-of-nodes-compilation-approach.html –

Estas son expresiones sin efectos secundarios? Entonces lo más fácil de hacer es agrupar los árboles para cada sub-expresión en cubos para determinar los candidatos para la eliminación de la sub-expresión. Este es un caso especial de CSE donde todas las expresiones están en un único (gran) "bloque básico". (Utilizo esta idea como base para detectar duplicate code.)

Si las expresiones tienen orden y efectos secundarios, es posible que desee considerar Value Numbering.

Fuente

2012-07-04 10:50:33

Correcto, no hay efectos secundarios. Si entiendo tu sugerencia correctamente, debería recorrer los nodos de la expresión, en el orden de las dependencias, y en cada paso verificar si una expresión ya está presente en un mapa hash. Si está presente, entonces use esta subexpresión, si no, agréguela al mapa hash. ¿Esto es entendido correctamente? – Joel

Sí. "En el orden de las dependencias" significa de abajo hacia arriba para cada árbol. –

Estaba pensando en esta estrategia. ¿Qué tipo de hash usarías? – Joel

Implementación de la eliminación de subexpresiones comunes

Respuesta

Cuestiones relacionadas