Я написал DSL и компилятор, который генерирует из него дерево выражений .NET. Все выражения в дереве не имеют побочных эффектов, и это выражение гарантированно будет выражением «без оператора» (без локальных элементов, циклов, блоков и т. Д.). (редактировать: Дерево может включать литералы, доступ к свойствам, стандартные операторы и вызовы функций - которые могут делать причудливые вещи, такие как запоминание внутри, но без побочных эффектов извне).

Теперь я хотел бы выполнить оптимизацию «Устранение общих подвыражений».

Например, дано дерево, соответствующее лямбде C #:

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

... Я хотел бы создать эквивалент дерева (игнорируйте тот факт, что некоторые из семантики короткого замыкания игнорируются):

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);
}

Я знаком с написанием выражений-посетителей, но алгоритм для этой оптимизации для меня не сразу очевиден - я, конечно, мог бы найти «дубликаты» в дереве, но, очевидно, есть некоторая хитрость для анализа зависимостей внутри и между деревья для эффективного и правильного устранения подвыражений.

Я искал алгоритмы в Google, но они кажутся довольно сложными для быстрой реализации. Кроме того, они кажутся очень «общими» и не обязательно учитывают простоту деревьев, которые я имею в виду.