4.4 支配树、支配边界与自然循环

4.4 支配树、支配边界与自然循环

本节摘要：支配树是 CFG 上的"必经关系"压缩成的树结构，支配边界是"必经关系失效"的边界线清单——两者共同构成现代编译器最常用的结构事实：SSA 的 phi 置放、自然循环识别、控制依赖计算全部踩在它们上面。本节给出支配与支配边界的严格定义，讲 Cooper-Harvey-Kennedy 迭代求支配树的算法（不到二十行、可现场手算），推导支配边界的计算公式，并把上一节的回边定义接上：支配关系一到位，循环识别只剩一次反向遍历。读完你应当能把一张 8 块以内的 CFG 的支配树、支配边界、自然循环全部手算出来。

3.3 构造 SSA 时直接引用了支配边界公式，4.3 定义回边时用了支配关系——本节把这两笔欠账一次还清。三组概念（支配树、支配边界、自然循环）共享同一个源头"支配"，学完本节你会发现它们是同一个事实的三种投影。

一、支配与支配树：必经关系的完全体

复述定义以便引用。d 支配 n（d dom n）：从入口到 n 的每条路径都经过 d。d 严格支配 n：支配且 d ≠ n。直接支配者 idom(n)：严格支配 n 的结点中，被其他所有严格支配者支配的那个——"最近的必经点"。全部 idom 边构成支配树，根是入口块。

支配树的三个立即可用性质：

1. 入口支配一切；支配关系是偏序（自反、反对称、传递）；
2. n 的支配者集合 = 支配树上从根到 n 的路径，查询 O(树深)；
3. 若 a dom b 且 b dom c，则 a dom c（传递性是"必经"语义的直接后果）。

迭代求支配树（Cooper-Harvey-Kennedy，LLVM 实际采用的思想）把支配当作数据流方程解：Dom(n) = {n} ∪ ⋂ Dom(p)（p 遍历已处理的前驱），idom 取 Dom(n) 中除自身外"最深"的元素。初始化只有入口为 {入口}，其余为全集，按逆后序迭代到不动：

IDom(cfg):
    逆后序 = RevPostOrder(cfg, 入口)
    idom[入口] = 入口
    changed = true
    while changed:
        changed = false
        for n in 逆后序 且 n ≠ 入口:
            newDom = ⋂ Dom(p) for p in preds(n) 中已处理的 p
            newDom = newDom ∪ {n}
            if newDom ≠ Dom[n]:
                Dom[n] = newDom; changed = true
    for n ≠ 入口: idom[n] = Dom[n] 中除 n 外最后加入的元素
​

实际实现不存完整 Dom 集（那是平方级），只存 idom，"交"用"沿 idom 链双指针对爬"完成，整体接近线性。手算小图时用集合版直觉更快，工程版只是把同样的语义折进 idom 链。

二、支配边界：必经的失效线

定义：结点 n 的支配边界 DF(n) = { y | 存在 y 的前驱 p，使 n dom p 且 n 不严格支配 y }。读法：控制流从 p 跨到 y 时，"n 必经"这层保护失效了——y 是 n 的势力范围正前方的城门。

计算不需要逐对检查（那是立方级），一次自底向上的树上演算就够。先定义支配者孩子：n 在支配树上的孩子结点集合。公式：

DF(n) = DF_local(n) ∪ ⋃ DF_up(c) 的过滤结果
DF_local(n) = { y ∈ succ(n) | n 不严格支配 y }          # 本块的出边直接贡献
对支配树每个孩子 c:
    对 y ∈ DF(c):
        if n 不支配 y（或 y == n）: DF(n) += y          # 孩子的边界向上冒泡
​

直觉版读法：DF_local 是"我自己直接跳出了我的势力范围"；DF_up 是"我的子树里有人跳出了势力范围，若跳出后仍归我管（我支配 y）则对我无所谓，否则记到我的账上"。一遍逆支配树序遍历即可算完，复杂度线性。

这张表一旦在手，三件大事同时解锁。SSA 置放（3.3 的算法照抄）：phi 位置 = 定值点沿 DF 迭代传播。控制依赖：块 y 控制依赖于块 n，当且仅当 y ∈ DF(n)——门控 SSA（3.4）需要的那份"路径条件"清单，就是 DF 表的镜像。自然循环的最后一环见下。

图：一个 8 块 CFG 的三张投影——支配树、DF 表、自然循环

三、手算示范：从 CFG 到三张表

按上图 CFG 过一遍迭代法（逆后序 B6, B5, B4, B3, B2, B1, B0）：

初始化: Dom(B0)={B0}, 其余=全集
第1轮:
  Dom(B1) = {B1} ∪ (Dom(B0) ∩ Dom(B4)=全集) = {B0,B1}
  Dom(B3) = {B3} ∪ Dom(B1) = {B0,B1,B3}
  Dom(B2) = {B2} ∪ Dom(B1) = {B0,B1,B2}
  Dom(B4) = {B4} ∪ Dom(B3) = {B0,B1,B3,B4}
  Dom(B5) = {B5} ∪ Dom(B2) = {B0,B1,B2,B5}
  Dom(B6) = {B6} ∪ (Dom(B4) ∩ Dom(B5)) = {B0,B1,B6}
第2轮: 无变化 → 收敛；idom: B1←B0, B2←B1, B3←B1, B4←B3, B5←B2, B6←B1
​

回边核对：B4→B1（B1 ∈ Dom(B4) ✓）、B5→B1（✓）。自然循环：从 B4 反向收集 {B4,B3,B2,B1}，从 B5 反向收集 {B5,B2,B1}；同头合并 → 循环体 {B1,B2,B3,B4,B5}。注意 B2 同时被两条回边的遍历经过——它属于循环，但它的 idom 链（B2←B1）说明它"不经过 B3/B5 也能到"，这正是支配树与反向遍历各自捕捉的不同侧面。

💡 关键直觉：支配树是"从入口看的必经"，自然循环的反向遍历是"从回边看的来路"。前者回答"谁挡在前面"，后者回答"谁能绕进来"——一个静态一个动态视角，拼起来才是完整控制流。

四、工程提示与易错点

• 迭代法的前驱次序敏感：交集运算只对"已处理过"的前驱生效，首轮遇到未处理前驱要跳过；忘跳会算出空交集、支配树整体错位。
• 支配边界公式里 y == n 的特例：循环头的 DF 包含自己（B1 ∈ DF(B1) 的来源）——这是循环携带变量 phi 长在循环头的根本原因，漏掉这个特例，SSA 构造在循环上必错。
• 不可约图的支配树仍有定义，但此时"回边"可能不存在（互相不支配），自然循环识别失效——4.3 的节点分裂在此处接手。
• 复杂度台账：CHK 迭代支配树近线性，DF 表线性，自然循环识别线性——全套结构事实的总开销与 SSA 构造同阶，这也是"现代 IR 默认 SSA"的隐形前提：地基便宜，才盖得起楼。

本节要点回顾：

• 支配/严格支配/idom/支配树：必经关系的完全体，CHK 迭代法近线性可手算；
• 支配边界定义与公式：DF(n) = 本地出边失效 + 子树冒泡未控者；循环头的 DF 含自身；
• 三表联动：支配树 → DF 表（SSA 置放、控制依赖）→ 回边+反向遍历 → 自然循环；
• 同头合并：共享头的回边圈同一个循环，循环树良构；
• 手算流程：逆后序迭代 idom → 支配树序算 DF → 逐回边圈体，全程纸笔可完成。

结构事实齐了，值域分析的最后一个盲区还亮着：指针。下一节把数据流框架的值域换成指向图，让"内存"也进入可推理范围。