compiler-construction - 快速计算支配者

Question

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

1. 需要计算基本块的支配者

2. 作为方程的固定点，有些明显的方法是缓慢的

3. 要快速完成，您需要使用相当复杂的 Lengauer-Tarjan 算法

我可以看到前两点，但我不清楚第三点背后的原因。特别是在计算前序支配树的过程中，有什么理由不能这样做吗？我已经在 J​​avaScript 中实现了一个版本，它似乎可以工作：

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 更简单的算法在实践中同样快或更快（即在大多数程序中出现的控制流图的种类上），即使在最坏的情况下复杂性听起来很可怕。见：库珀，基思 D。哈维，蒂莫西 J；和肯尼迪，肯（2001 年）。“一种简单、快速的优势算法”

Answer 2

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