Я написал DSL и компилятор, который генерирует из него дерево выражений .NET. Все выражения внутри дерева не имеют побочных эффектов, и выражение гарантируется как выражение "без выражения" (без локалей, циклов, блоков и т.д.). (Изменить). Дерево может включать в себя литералы, права доступа к функциям, стандартные операторы и вызовы функций, которые могут быть полезными, например, внутри memoization, но внешне свободны от побочных эффектов).
Теперь я хотел бы выполнить оптимизацию "Общего исключения подвыражений" на нем.
Например, для дерева, соответствующего С# lambda:
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);
}
Я знаком с написанием expression-visitors, но алгоритм для этой оптимизации не сразу ясен для меня - я мог бы, конечно, найти "дубликаты" в дереве, но, очевидно, есть трюк для анализа зависимостей внутри и между суб-деревьями для эффективного и правильного устранения подвыражений.
Я искал алгоритмы для Google, но они кажутся довольно сложными для реализации. Кроме того, они кажутся очень "общими" и не обязательно учитывают простоту деревьев, которые я имею в виду.
