计算图的支配点

# 技术笔记：计算图的支配点 来源：https://neugierig.org/software/blog/2026/08/dominators.html 几年前我写过关于依赖图的支配树（https://neugierig.org/software/blog/2023/07/dominator.html）的文章，那是我思考依赖关系时最喜欢用的技巧之一。结果我最近的一个小项目又需要支配树了，于是我投入了一些时间来加深理解。 在这篇文章中，我会介绍一个计算图支配点的算法，以及它背后的直觉。 ## 定义 有两个核心定义我会略过一些细节；你可以去读维基百科（https://en.wikipedia.org/wiki/Dominator_(graph_theory)）了解。这里有一个图可以帮助你直观理解。阅读时请将鼠标悬停在节点上。 1. 如果从图的根节点（在此例中是 `a`）到 y 的所有路径都必须经过 x，则节点 x *支配*节点 y。如果你将鼠标悬停在此处的某个节点上，它的支配点会以黄色显示。 2. 如果节点 x 是 y 上方最低的支配点，则 x *直接支配* y。悬停节点的直接支配点会以更粗的轮廓显示。 再说一次，想了解这些概念的其他解释方式或思考方法，可以看我之前的文章（https://neugierig.org/software/blog/2023/07/dominator.html）。 ## 选择算法 关于计算支配点的研究从 1959 年就持续不断，发表了各种不同实现复杂度的算法。1979 年的 Lengauer-Tarjan（简称 "LT"）似乎是标准算法，但它相对复杂，涉及生成树和并查集。 在 LLVM 中——也就是说，在一个性能确实很重要的工具中——他们似乎使用了 LT，但实现随着时间一直在变化。例如在 2017 年的这项工作（https://groups.google.com/g/llvm-dev/c/_z7rQUwBNps）中，他们提到在一次大型编译中计算了 650 万个支配树（！），于是改成了支持增量更新的方法。 2001 年发表的论文 "A Simple, Fast Dominance Algorithm" 描述了一种简单算法，他们声称这种算法既有助于学习，在实践中也比 LT 快约 2.5 倍。 后来的论文 "Finding Dominators in Practice" 比较了多种算法，关于上述声明他们写道："后来对 [Lengauer-Tarjan] 更仔细的实现得出了不同的结果（个人通信）"，这可不是个好迹象。不过，在那篇论文中，他们也收集了五种不同算法在一组图上的性能数据，发现它们都落在广度优先搜索耗时的 2-5 倍范围内，而 BFS 本身是微秒级的。也就是说，对于你或我可能关心的那种图，差异并不重要。 如果你喜欢读论文（我喜欢！这是一个值得培养的习惯！），最好直接读 "A Simple, Fast Dominance Algorithm"。但为了用自己的话加深理解，这篇文章其余部分将深入介绍 "Simple, Fast" 算法。 ## 方法 他们的论述大致分两部分。首先，他们描述了一种计算支配点的一般方法，以及它为什么有效。其次，他们展示了一种算法，利用一些表示技巧来高效地实现该方法。 一般方法将计算描述为数据流方程，它定义了每个节点的计算方式，而该计算递归地依赖于自身。 将 `dom[n]` 定义为节点 `n` 的支配点集合。那么数据流方程是： `` dom[root] = {root} dom[n] = intersect(dom[p] for p in predecessors(n)) union {n} `` 用语言描述，一个节点的支配点集合是其所有前驱节点的支配点集合的交集，再加上节点自身。（要理解这一点，别忘了 `dom[n]` 总是包含 `n` 本身！） 要计算这个，你需要循环更新每个节点，直到输出不再变化。 `` changed = True while changed: changed = False for n in nodes: new = recompute(n) if new != dom[n] dom[n] = new changed = True `` 在论文中，他们将此与其他研究联系起来，表明这会收敛到正确答案，且迭代次数相对较少——如果你按逆后序迭代节点的话，关于这一点稍后再说。就我们建立直觉的目的而言，我认为"这保证能足够快地收敛到正确结果，证明见论文"就已经足够了。 为什么这能行？在上面的示例图中，尝试将鼠标悬停在节点 `g` 或 `h` 的前驱节点上，在大脑中求黄色集合的交集，看看是否能得到它们自己的黄色集合。直观上，这些集合代表着某种从根出发的路径（虽然可能不是完整路径；看看 `g` 的支配点集合就知道了），而求交集得到的结果就是所有从根出发的路径上共同经过的节点。 按原样计算效率较低——不过我觉得如果是用 Python 之类写的程序，处理小图的话可能没问题。论文中的实际算法则更高效。 ## 遍历顺序 要理解这个算法，我们得先绕道去看看图的遍历，因为它依赖于图的逆后序遍历。 前序遍历先访问一个节点，然后访问它的子节点；后序遍历先递归地访问子节点，再访问节点本身；逆后序就是将后序的顺序反过来。 重要的是，逆后序和前序是不同的。在下面的图中，我按遍历顺序给节点编了号，方便你比较。 在前