实现公共子表达式消除

Question

我正在研究对应于大数学表达式(数百万个节点)的表达式图实现公共子表达式消除(CSE).

什么算法适合执行此操作？我在互联网上搜索一个易于实现的算法,但我找不到任何东西.如果可能,算法应该具有完整表达图的节点数的线性复杂度.

Answer 1

这些表达没有副作用？然后,最简单的方法是将每个子表达式的树哈希到桶中,以确定子表达式消除的候选者.这是CSE的一个特例,其中所有表达式都在一个(巨大的)"基本块"中.(我使用这个想法作为检测重复代码的基础.)

如果表达式具有顺序和副作用,您可能需要考虑值编号.