有效地消除.NET表达式树中的常见子表达式
我编写了一个DSL和一个从中生成.NET表达式树的编译器。 树中的所有表达式都是无副作用的，并且表达式保证是“非语句”表达式（没有本地，循环，块等）。 （ 编辑 ：树可能包括文字，属性访问，标准操作符和函数调用 – 这可能正在做内容中的memoization等奇特的事情，但是外部无副作用）。
现在我想对它执行“Common sub-expression elimination”优化。
例如，给定一个对应于C＃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); }
我熟悉编写表达式访问者，但这种优化的算法对我来说并不是很明显 – 我当然可以在树中找到“重复”，但显然有一些技巧来分析子内部和之间的依赖关系。树可以有效和正确地消除子表达式。
我在Google上寻找算法但是它们看起来很难实现。 此外，它们看起来非常“一般”，并不一定考虑到我所考虑的树木的简单性。
你是正确的，注意这不是一个小问题。
编译器处理它的经典方法是表达式的有向无环图（DAG）表示 。 DAG的构建方式与抽象语法树相同（可以通过遍历AST构建 – 也许是表达式访问者的工作;我不太了解C＃库），除了先前发出的子图的字典维持。 在生成具有给定子节点的任何给定节点类型之前，将查询字典以查看是否已存在。 仅当此检查失败时才会创建新的检查，然后将其添加到字典中。
由于现在节点可能来自多个父节点，因此结果是DAG。
然后首先遍历DAG以生成代码。 由于公共子表达式现在由单个节点表示，因此该值仅计算一次并存储在temp中，以便稍后在代码生成中使用时发出的其他表达式。 如果原始代码包含赋值，则此阶段会变得复杂。 由于您的树木是无副作用的，因此DAG应该是解决问题的最简单方法。
我记得， 龙书中对DAG的报道特别好。
正如其他人所指出的那样，如果你的树最终将由现有的编译器编译，那么重做那些已经存在的东西是徒劳的。
加成
我从一个学生项目（我教过）中得到了一些Java代码，因此编写了一个如何工作的小例子。 发帖太长了，但请看这里的要点 。
在输入上运行它会打印下面的DAG。 parens中的数字是（唯一ID，DAG父计数）。 需要父计数来决定何时计算本地临时变量以及何时仅使用表达式来表示节点。
Binary OR (27,1) lhs: Binary OR (19,1) lhs: Binary GREATER (9,1) lhs: Binary ADD (7,2) lhs: Binary MULTIPLY (3,2) lhs: Id 'Bar' (1,1) rhs: Number 5 (2,1) rhs: Binary MULTIPLY (6,1) lhs: Id 'Baz' (4,1) rhs: Number 2 (5,1) rhs: Number 7 (8,1) rhs: Binary LESS (18,1) lhs: ref to Binary ADD (7,2) rhs: Number 3 (17,2) rhs: Binary EQUALS (26,1) lhs: Binary ADD (24,1) lhs: ref to Binary MULTIPLY (3,2) rhs: ref to Number 3 (17,2) rhs: Id 'Xyz' (25,1)
然后它生成此代码：
t3 = (Bar) * (5); t7 = (t3) + ((Baz) * (2)); return (((t7) > (7)) || ((t7) < (3))) || (((t3) + (3)) == (Xyz));
您可以看到临时变量编号对应于DAG节点。 您可以使代码生成器更复杂，以摆脱不必要的括号，但我会留给其他人。
你正在做不必要的工作，常见的子表达式消除是抖动优化器的工作。 让我们以您的示例为例，查看生成的代码。 我这样写的：
static void Main(string[] args) { var lambda = new Func(foo => (foo.Bar * 5 + foo.Baz * 2 > 7) || (foo.Bar * 5 + foo.Baz * 2 < 3) || (foo.Bar * 5 + 3 == foo.Xyz)); var obj = new Foo() { Bar = 1, Baz = 2, Xyz = 3 }; var result = lambda(obj); Console.WriteLine(result); } } class Foo { public int Bar { get; internal set; } public int Baz { get; internal set; } public int Xyz { get; internal set; } }
x86抖动为lambda表达式生成了此机器代码：
006526B8 push ebp ; prologue 006526B9 mov ebp,esp 006526BB push esi 006526BC mov esi,dword ptr [ecx+4] ; esi = foo.Bar 006526BF lea esi,[esi+esi*4] ; esi = 5 * foo.Bar 006526C2 mov edx,dword ptr [ecx+8] ; edx = foo.Baz 006526C5 add edx,edx ; edx = 2 * foo.Baz 006526C7 lea eax,[esi+edx] ; eax = 5 * foo.Bar + 2 * foo.Baz 006526CA cmp eax,7 ; > 7 test 006526CD jg 006526E7 ; > 7 then return true 006526CF add edx,esi ; HERE!! 006526D1 cmp edx,3 ; < 3 test 006526D4 jl 006526E7 ; < 3 then return true 006526D6 add esi,3 ; HERE!! 006526D9 mov eax,esi 006526DB cmp eax,dword ptr [ecx+0Ch] ; == foo.Xyz test 006526DE sete al ; convert to bool 006526E1 movzx eax,al 006526E4 pop esi ; epilogue 006526E5 pop ebp 006526E6 ret 006526E7 mov eax,1 006526EC pop esi 006526ED pop ebp 006526EE ret
我在代码中标记了用HERE消除foo.Bar * 5子表达式的位置。 值得注意的是它没有消除foo.Bar * 5 + foo.Baz * 2子表达式，在地址006526CF处再次执行添加。 有一个很好的理由，x86抖动没有足够的寄存器来存储中间结果。 如果您查看x64抖动生成的机器代码，那么您确实看到它被消除了，r9寄存器会存储它。
这应该给出足够的理由重新考虑你的意图。 你正在做的工作不需要做。 不仅如此，由于您无法估算CPU寄存器预算，因此您可能会产生比抖动更多的代码。
不要这样做。
-
创建一个可以比较任意
Expression的SortedDictionary。
（您可以在此处定义自己的任意比较函数 – 例如，您可以按字典顺序比较表达式的类型 ，如果它们相等，那么您可以逐个比较子项。） -
浏览所有树叶并将它们添加到字典中; 如果它们已经存在，则它们是重复的，所以合并它们。
（这也是发布代码的好时机 – 例如为这个叶子创建一个新变量 – 如果它是它的第一个实例;然后你可以将发出的代码存储在字典中的object值中。） -
然后浏览所有以前的叶子的父母并将它们添加到字典中; 如果它们已经存在，则它们是重复的，所以合并它们。
-
继续逐级上升，直到到达根目录。
现在您知道所有重复项是什么以及它们出现在何处，并且您已经为所有重复项生成了代码。
免责声明：我从来没有解决过这样的问题，我只是抛出一个看似合理有效的想法：
对于树中的每个节点都有某种签名。 哈希应该做，可以处理冲突。 签名必须将所有Foo.Bar条目映射到相同的值。
遍历树（O（n））构建INTERNAL节点的签名列表（忽略叶子），对表达式大小和签名（O（n log n））的组合键进行排序。 获取列表中最小表达式的最常见项（O（n）），并使用局部变量替换表达式。 （在我们发生哈希冲突时，检查它们是否真的匹配.B）
重复这个，直到你什么也没做。 这不可能运行超过n / 2次，从而将整个操作限制为O（n ^ 2 log n）。
我同意hans-passant关于这样做的实用性。 但是，如果你在学术上研究它，你可能会对Quine-McCluskey算法感兴趣。 请注意，这是一个非常复杂的问题。 Mathematica有一个非常好的通用表达式优化器，根据您的需要，您可以只使用它 – 例如， 如果您将其表达式提供给它 ：
（foo.Bar = A，foo.Baz = B，foo.Xyz = X）