Dominator Tree：一条程序路径上谁是必经之地？

在一段程序里，有些代码块是“必经之路”：不管从入口走哪条合法路径，想抵达后面的某个位置，都必须先经过它。编译器把这种关系称为 dominance，并可以把它组织成 Dominator Tree，也就是支配树。

用地图理解支配关系

把函数的控制流想成一张道路地图，入口是城市大门，基本块是路口。若从大门到路口 B 的所有道路都要经过路口 A，那么 A 就支配 B。入口天然支配所有可达位置，而越靠近入口、越被许多路径共享的节点，支配范围通常越大。

支配树不是原始控制流图的复制品。它只保留“谁是某个节点最近的必经上游”这层关系，因此可以帮助编译器快速回答：一条定义在某个使用点之前是否总是可用？某个检查是否覆盖了所有后续路径？循环入口在哪里？

在 SSA 形式中，变量定义必须满足支配关系：定义点应该支配使用点，否则某条路径可能还没执行定义就使用了变量。编译器还会利用支配树进行代码提升、公共子表达式消除、循环分析和控制流简化。

如果控制流发生变化，支配树也要及时更新。LLVM 的实现提供了重新计算、插入边、删除边和查询最近公共支配者等能力。这些细节说明，支配关系不是一次性画出来的静态图片，而是优化过程中会持续变化的分析结果。

调用图关注“哪个函数调用了哪个函数”；支配树关注“同一个函数内部，哪些控制流节点是另一些节点的必经之路”。一个是跨函数的关系，一个是函数内部的路径关系。

理解这个术语，对阅读编译器错误、静态分析报告和 AI 生成的复杂条件代码很有帮助。看到一串嵌套 if、循环和提前返回时，可以问：某个检查到底覆盖了哪些路径？它是不是所有危险操作的真正必经前置条件？

Dominator Tree 解决的是“谁必须先经过”的问题。它把控制流图中隐含的路径规律显式化，是 SSA、循环优化和代码安全分析的重要基础设施。