He escrito un DSL y un compilador que genera un árbol de expresiones .NET a partir de él. Todas las expresiones dentro del árbol están libres de efectos secundarios y se garantiza que la expresión sea una expresión de "no declaración" (no locales, bucles, bloques, etc.). (Editar: El árbol puede incluir literales, accesos a propiedades, operadores estándar y llamadas a funciones, que pueden estar haciendo cosas extravagantes como la memoria interna, pero están exentas de efectos secundarios externos.

Ahora me gustaría realizar la optimización "Eliminación de subexpresión común" en él.

Por ejemplo, dado un árbol correspondiente a la C # lambda:

foo =>      (foo.Bar * 5 + foo.Baz * 2 > 7) 
         || (foo.Bar * 5 + foo.Baz * 2 < 3)  
         || (foo.Bar * 5 + 3 == foo.Xyz)

... Me gustaría generar el equivalente en árbol de (ignorar el hecho de que se está ignorando parte de la semántica de cortocircuito):

foo =>
{
     var local1 = foo.Bar * 5;

     // Notice that this local depends on the first one.        
     var local2 = local1 + foo.Baz * 2; 

     // Notice that no unnecessary locals have been generated.
     return local2 > 7 || local2 < 3 || (local1 + 3 == foo.Xyz);
}

Estoy familiarizado con la escritura de visitantes de expresión, pero el algoritmo para esta optimización no es inmediatamente obvio para mí; por supuesto, podría encontrar "duplicados" dentro de un árbol, pero obviamente hay algún truco para analizar las dependencias dentro y entre los subgrupos. Árboles para eliminar las sub-expresiones de manera eficiente y correcta.

Busqué algoritmos en Google pero parecen bastante complicados de implementar rápidamente. Además, parecen muy "generales" y no necesariamente tienen en cuenta la simplicidad de los árboles que tengo.