公共子表达式寻找问题

duanlin

看算法导论中说，搜索两个图的子图匹配，是个NP完全问题，没有算法解。

我想请问，在编译器实现里，类似下列这种问题，是如何做到的。


x = a + b + c + d + e + f + g + m;
y = 100 + a + b + c + d + e + f + g + n + o + p + q;

在优化时，如何决策和提取 a + b + c + d + e + f + g 这个重复计算的公共表达式。

cjaizss

作为整体来说,图如果很大,取最大公共子图的确复杂度很高,但对于一个小局部,这个完全可以退化成集合的并,复杂度低

duanlin

举例中简单的单一情况，可以寻找交集不错。但实际场景中似乎依然摆脱不了他是一个多集合寻找最多公子集的这样一个问题。
举个复杂一点点的例子：

P = a + b + c + d + e + f;

Var1 = a+b+c;
Var2 = b+c+d;
Var3 = c+d+e;
Var4 = d+e+f;
Var5 = b+e;

用直观的判断（人类），在P的计算时从中间分开的结果分别保存，再将分开的内部中途结果保存的话，最少可以只计算8次加法（没有证明它是最少的）。

有没有算法解，能找到一个10次加法计算以下的？

relipmoc

公共子表达式合并，有多种方式实现，这个在做局部优化时就删掉了。
一般可以用用dag(有向无环图）来做局部优化，效果十分明显，这种表达式几乎都可以优化掉。
LZ找本编译原理教材，看里面的dag章节都有叙述。