10.4 支配关系与循环
若从程序入口到基本块 B 的每一条执行路径都必须经过基本块 A，则称 A 支配（dominates） B。这种"必经节点"关系是控制流图结构分析的核心骨架，也是编译器优化框架的基础。支配关系并非可有可无的装饰，而是多种重要优化的先决条件：循环识别、代码外提、SSA 形式的 phi 节点放置，都以这个概念为基础。直觉上，如果想要绕过某个块而到达 B，却无论走哪条路都绕不过去，那个块就是 B 的支配者。
程序入口块支配图中所有其他块——任何执行都必然从入口出发，因此入口的"必经"地位是无条件的。除入口块以外，每个基本块都存在唯一一个直接支配者（immediate dominator），即在支配链上距离它最近、又严格支配它的那个块。将所有"直接支配"关系集合起来，就形成一棵以入口为根、以各块为节点的支配树（dominator tree），每个块在树中的父节点就是它的直接支配者。
计算支配
标准不动点公式如下：
迭代到不动点即可。入口只被自身支配，其余块取所有前驱支配集合的交集。
该公式将每个块 的支配集定义为： 自身，加上所有前驱块支配集合的交集。入口块的支配集只含自身，因为它没有前驱；对其他每个块，若某候选支配者未能出现在至少一条进入路径上，就不满足"必经"条件，因此取交集恰好筛掉这类候选者。反复用该公式更新每个块的支配集，直到没有任何集合再发生变化——即达到不动点（fixpoint）——计算结束。
从实现角度来说，初始时可将每个块（除入口外）的支配集设为全集，然后逐轮收缩。按逆后序（reverse postorder，RPO）遍历块可以最快传播前驱信息，对于可归约流图往往只需两三次迭代便收敛。更高效的 Lengauer-Tarjan 算法利用深度优先生成树，在接近线性的时间内直接计算直接支配者，是生产级编译器处理大型函数的首选方案。
循环就是回边
当控制流图中存在一条回边（back edge） ，且目标节点 支配源节点 时，就出现了一个自然循环（natural loop）。 称为循环的头部（header），它支配整个循环体；循环体由所有满足"不经过 即可到达 "条件的块组成，再加上 本身。从程序入口到 的路径必然经过 ，而从 出发最终可以通过 重新回到 ，这正是"循环"在图结构层面的本质含义。
这个定义把"循环"从语法层面的概念——比如 for、while、do-while——转化为纯粹的图结构属性，使编译器无需依赖具体语言语法，就能统一识别和处理各种形态的循环，包括 goto 语句构成的非结构化循环。优化器的大量循环变换都以这个结构定义为前提，而不关心源码中使用了哪种循环语法。
为什么重要
支配关系决定了 phi 节点的放置位置。在将程序转换为 SSA 形式时，只有在控制流汇合点且来自不同前驱的值可能不同的地方，才需要插入 phi 节点；而支配边界（dominance frontier）恰好精确刻画了这些位置，避免既不漏插又不多插。支配关系同样界定了循环不变量代码外提（loop-invariant code motion，LICM）的安全范围：只有当某个计算在所有循环出口路径上都一定会被执行时，才能安全地将其上提到循环前，这正是由支配关系来保证的。代码上提（hoisting）、代码下沉（sinking）等移动优化同样依赖支配结构来判断移动后的语义是否与原来等价。把支配关系算正确，一整族优化才能安全实施。
支配树
直接支配者构成一棵树：每个块的父节点是它最近的严格支配者，根节点是程序入口块，叶节点是不支配其他任何块的出口块。支配树并非仅供理论分析的辅助结构，而是优化遍（pass）实际遍历的数据结构。计算 SSA 形式时，phi 放置算法需要遍历支配树、计算每个变量定义点的支配边界；循环不变量外提时，从当前指令的所在块沿支配树向上走，寻找最远的安全外提点；支配树的后序遍历常用来按正确的依赖顺序处理基本块，确保分析信息从前驱向后继正确传播。支配树越精确，基于它的优化和分析结果就越好。
循环解剖
在自然循环结构中，各组成部分都有精确的术语：头部（header）是循环的唯一入口点，支配整个循环体中所有的块；闩（latch）是携带回边、将控制流送回头部的那个块；前置头（preheader）是编译器在头部之前人工插入的一个新块，它的唯一后继是头部，且所有从循环外进入头部的路径都经过它——有了前置头，外提的循环不变代码就有了放置点，而不会扰乱头部的 phi 节点；循环出口（exit edge）是从循环内部跳出到循环外的边，出口目标块称为退出后继（exit successor）。优化器针对这些特定位置实施变换：循环不变量移入前置头，归纳变量（induction variable）在循环体内识别并化简，只在循环内有定义的变量被约束在循环的作用域中。清晰的循环解剖使每种变换都有明确的作用目标，也便于相互组合。
嵌套与不可归约
当一个循环的头部支配另一个循环的头部时，就形成了循环嵌套（loop nesting），内层循环完全包含在外层循环头部的支配范围之内。绝大多数实际代码是可归约的（reducible）：每个循环都有单一头部，嵌套关系干净，回边的目标都是其源的严格支配者，不存在跨越嵌套层级的任意跳转。手写 goto 语句或某些状态机编码风格可能产生不可归约流（irreducible flow），即多条入边来自互不支配的源节点，使得单一头部的假设不再成立。面对不可归约流，编译器要么将其变换为可归约形式（如节点分裂），要么对这部分区域退回到更保守的分析策略，丧失某些循环优化机会。理解这层区别，就能理解为何某些手写的底层代码难以被编译器深度优化。
实战洞见
考虑一个"菱形加回边"的经典结构：从头部 分叉出两条路径（then 分支和 else 分支），它们在汇合点 合并，再有一条回边从 回到 。支配关系立即揭示： 支配 ， 带有指向 的回边，因此 是循环入口， 是循环的闩，循环体包含从 到 所有受 支配的块。这一结论不依赖源码中使用了什么语法结构，只读取支配树和回边信息即可得出。这种"从图属性直接读取语义"的能力，正是基于 CFG 的优化比基于 AST 的优化通常更通用、更强大的原因。