实现常见子表达式消除

Question

8

我正在研究实现公共子表达式消除（CSE），以处理对应于大型数学表达式的表达式图（数百万个节点）。

哪些算法适用于执行此操作？我在互联网上搜索了易于实现的算法，但未找到任何内容。如果可能，该算法应具有与完整表达式图中节点数量成线性关系的复杂度。

- Joel

这个表示可能会有所帮助：http://www.masonchang.com/blog/2010/8/9/sea-of-nodes-compilation-approach.html - SK-logic

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ira Baxter · Accepted Answer

11

这些表达式没有副作用？那么最简单的方法就是将每个子表达式的树哈希到桶中，以确定子表达式消除的候选项。

这是CSE的一个特例，在单个（巨大的）"基本块"中的所有表达式都是如此。（我将这个想法用作检测重复代码的基础。）

如果这些表达式有顺序和副作用，则可能需要考虑全局值编号。

- Ira Baxter

没错，这里没有副作用。如果我正确理解了您的建议，我应该按照依赖关系的顺序循环遍历表达式的节点，并在每一步检查哈希映射中是否已经存在一个表达式。如果存在，则使用此子表达式，如果不存在，则将其添加到哈希映射中。这样理解对吗？ - Joel

没错。"按依赖关系排序" 意味着对于每棵树来说都是自下而上。 - Ira Baxter

我正在考虑这种策略。您会使用哪种哈希？ - Joel

1

并不是很重要。您需要一个哈希函数，可以将大多数树均匀地映射到桶中。如果您可以在单个叶节点上构建原始哈希函数（生成32或64位哈希值的某些内容），则可以通过简单地添加/异或子哈希的哈希来组合哈希，以获得父哈希代码。然后，哈希代码就是该哈希值对哈希映射表中桶的数量取模的结果。 - Ira Baxter