快速计算支配者

Question

据说在将中间代码转换为静态单赋值形式时，

需要计算基本块的支配者
作为方程的不动点，这种比较明显的方法很慢
为了快速完成，您需要使用相当复杂的 Lengauer-Tarjan 算法

前两点我能看出来，第三点的道理我就不清楚了。特别是在计算前序支配树的过程中，有什么理由做不到吗？我已经在 JavaScript 中实施了一个版本，它似乎有效：

var domPreorder = [];

function doms(b) {
    b.children = [];
    for (var c of b[b.length - 1].targets)
        if (c.i == null) {
            c.i = domPreorder.length
            domPreorder.push(c)
            b.children.push(c)
            c.parent = b
            doms(c)
        }
}

f[0].i = 0
domPreorder.push(f[0])
doms(f[0])

这种方法有什么我没有发现的缺点吗？

Answer 1

啊，我现在明白了，简单的技术不能正确处理具有任意多个分叉和重新连接的控制流图。您需要能够找到绕过路径，如果您希望执行此操作的代码速度快，则需要计算并记住半支配符，然后看起来您最终会得到 Lengauer-Tarjan 或类似的东西。

Answer 2

虽然快速和正确地计算支配者确实不是微不足道的，但有比 Lengauer-Tarjan 更简单的算法，它们在实践中同样快或更快（即在大多数程序中出现的控制流图的种类），甚至尽管最坏情况的复杂性听起来很可怕。参见：Cooper, Keith D.；哈维，蒂莫西·J；和肯尼迪，肯 (2001)。 "A Simple, Fast Dominance Algorithm"

快速计算支配者

Fast calculation of dominators

compiler-construction

ssa