Ani*_*Ani 17 .net c# algorithm optimization expression-trees
我编写了一个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);
}
我熟悉编写表达式访问者,但这种优化的算法对我来说并不是很明显 - 我当然可以在树中找到"重复",但显然有一些技巧来分析子内部和之间的依赖关系.树可以有效和正确地消除子表达式.
我在谷歌上寻找算法,但它们似乎很难快速实施.而且,它们看起来非常"一般",并不一定考虑到我所考虑的树木的简单性.
Han*_*ant 13
你正在做不必要的工作,常见的子表达式消除是抖动优化器的工作.我们以您的示例为例,查看生成的代码.我这样写的:
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
我foo.Bar * 5用HERE 标记了代码中用于消除子表达式的位置.值得注意的是它没有消除foo.Bar * 5 + foo.Baz * 2子表达式,在地址006526CF再次执行添加.有一个很好的理由,x86抖动没有足够的寄存器来存储中间结果.如果您查看x64抖动生成的机器代码,那么您确实看到它被消除了,r9寄存器会存储它.
这应该给出足够的理由重新考虑你的意图.你正在做的工作不需要做.不仅如此,你是容易产生更坏的代码比抖动会产生,因为你没有估计CPU寄存器预算的奢侈品.
不要这样做.
你是正确的指出这不是一个小问题.
编译器处理它的经典方法是表达式的有向无环图(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));
您可以看到temp var数字对应于DAG节点.您可以使代码生成器更复杂,以摆脱不必要的括号,但我会留给其他人.