c# - 有效消除 .NET 表达式树中的公共(public)子表达式

Question

我已经编写了一个 DSL 和一个从中生成 .NET 表达式树的编译器。树中的所有表达式都是无副作用的，并且表达式保证是“非语句”表达式(没有局部变量、循环、 block 等)。 (编辑:树可能包括文字、属性访问、标准运算符和函数调用——它们可能在内部做一些奇特的事情，比如内存，但在外部没有副作用)。

现在我想对其进行“公共(public)子表达式消除”优化。

例如，给定一棵对应于 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 上寻找算法，但它们似乎很难快速实现。此外，它们看起来非常“笼统”，不一定考虑到我所考虑的树的简单性。

Answer 1

你在做不必要的工作，常见的子表达式消除是抖动优化器的工作。让我们以您的示例为例，看看生成的代码。我是这样写的:

    static void Main(string[] args) {
        var lambda = new Func<Foo, bool>(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 寄存器预算。

不要这样做。