Napisałem DSL i kompilator, który generuje z niego drzewo wyrażeń .NET. Wszystkie wyrażenia w drzewie są wolne od efektów ubocznych, a wyrażenie jest gwarantowane jako wyrażenie „bez instrukcji” (brak lokalnych, pętli, bloków itp.). (Edytować: Drzewo może zawierać literały, dostęp do właściwości, standardowe operatory i wywołania funkcji - które mogą robić wymyślne rzeczy, takie jak zapamiętywanie wewnątrz, ale są zewnętrznie wolne od efektów ubocznych).

Teraz chciałbym przeprowadzić na nim optymalizację „Common sub-expression elimination”.

Na przykład, podając drzewo odpowiadające lambdzie C #:

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

... Chciałbym wygenerować odpowiednik drzewa (zignoruj ​​fakt, że niektóre semantyki zwierania są ignorowane):

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

Jestem zaznajomiony z pisaniem wyrażeń-odwiedzających, ale algorytm tej optymalizacji nie jest dla mnie od razu oczywisty - mógłbym oczywiście znaleźć „duplikaty” w drzewie, ale oczywiście istnieje pewna sztuczka do analizy zależności wewnątrz i między drzewa, aby skutecznie i poprawnie eliminować podwyrażenia.

Szukałem algorytmów w Google, ale ich implementacja wydaje się dość skomplikowana. Ponadto wydają się bardzo „ogólne” i niekoniecznie biorą pod uwagę prostotę drzew, które mam pod uwagę.