将有序树转换为有向无环图的算法

Question

假设我有一种编程语言，我可以写出：x = f(g(1), h(1))。在这种情况下，有向无环图将显示计算的依赖关系，就像在电子表格中一样（假设非递归表达式）：

 1
| \
g  h
 \ /
  f

这是一个简单的例子，但是在DAG中尝试“压缩”更复杂的表达式时变得更有趣了。目标是优化基于依赖性的重新计算次数。

有哪些算法和论文可用于解决这个问题？

- sw.

Answer 1

更具体来说，它是本地公共子表达式消除。在《编译原理》（Dragon Book）中给出了一个算法，即“6.1.2 基于值编号的方法构建DAG”。

- chill

Answer 2

编译器编写人员称这个问题为公共子表达式消除。每本值得一读的编译器教材都会涵盖这个主题。

没有控制流，你应该能够做一些类似于哈希共享的简单操作。

- Per