高效消除.NET表达式树中的常见子表达式

一尘不染

高效消除.NET表达式树中的常见子表达式

algorithm

我已经编写了一个DSL和一个从中生成.NET表达式树的编译器。树中的所有表达式都是无副作用的，并且保证该表达式是“非声明”表达式（没有局部变量，循环，块等）。（
编辑：该树可能包括文字，属性访问，标准运算符和函数调用-可能在内部做一些很有趣的事情，例如备注，但在外部没有副作用）。

现在，我要对其执行“公共子表达式消除”优化。

例如，给定一棵与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上寻找算法，但要快速实施它们似乎很复杂。而且，它们看起来非常“通用”，并不一定要考虑我所考虑的树木的简单性。

阅读 221

2020-07-28

共1个答案

一尘不染

您没错，这不是一个小问题。

编译器处理该问题的经典方法是该表达式的有向无环图（DAG）表示。DAG的构建方式与抽象语法树相同（并且可以通过遍历AST来构建-
也许是表达式访问者的工作；我对C＃库了解不多），除了以前发出的子图的字典被维持。在使用给定的子代生成任何给定的节点类型之前，请查阅该词典以查看是否已经存在。仅当此检查失败时，才创建新的检查，然后将其添加到字典中。

由于现在一个节点可能来自多个父节点，因此结果是DAG。

然后首先遍历DAG深度以生成代码。由于公共子表达式现在由单个节点表示，因此该值仅计算一次并存储在临时文件中，以供以后在代码生成中使用的其他表达式使用。如果原始代码包含分配，则此阶段会变得很复杂。由于您的树木没有副作用，因此DAG应该是解决问题的最直接方法。

我记得，《龙》一书中
DAG的覆盖范围特别好。

正如其他人指出的那样，如果您的树最终将由现有的编译器编译，则重做已经存在的目录是徒劳的。

加成

我在一个学生项目（我教过的）中放置了一些Java代码，因此总结了一个有关其工作原理的小例子。发布时间太长，请在此处查看要点。

在您的输入上运行它会在下面打印DAG。括号中的数字是（唯一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节点。您可以使代码生成器更加复杂，以消除不必要的括号，但我将其留给其他人使用。

2020-07-28