第 10 篇建立了控制流图——基本块是节点，跳转和分支是边。结构搭好了，但编译器还不能回答两个关键问题。第一：在分支合流的位置，变量的值从哪条路径来？这个问题决定了 phi 节点的放置（第 12 篇的主题）。第二：某个变量在某个位置之后是否还会被读取？如果不会，它占用的寄存器可以释放，对它的赋值也可以删除。

回答第一个问题需要支配关系分析（dominance analysis），回答第二个问题需要活跃变量分析（liveness analysis）。两者都属于数据流分析的范畴，共享同一个计算框架：在 CFG 上反复传播信息，直到所有块的信息集合不再变化——这个终止状态叫做不动点（fixed point）。

什么是支配

从 CFG 的入口块出发，如果到达块 B 的每一条路径都必须经过块 A，就说 A 支配（dominate）B，记作 A dom B。这个定义有几个直接推论。入口块支配所有块，因为任何路径都从入口开始。每个块都支配自身，因为"经过自身"这个条件平凡成立。如果 A 支配 B 且 B 支配 C，那么 A 也支配 C——支配关系具有传递性。

严格支配（strict dominance）排除自身的情况：A 严格支配 B 当且仅当 A 支配 B 且 A 不等于 B。直接支配者（immediate dominator，缩写 idom）是离 B 最近的那个严格支配者。每个非入口块恰好有一个 idom，这是因为所有支配者构成一个从入口到 B 的链，链上最后一个元素就是最近的。

用不动点迭代计算支配集合

算法很直接。为每个块维护一个集合 dom(B)，表示支配 B 的所有块。初始化时，入口块的支配集合只包含自身；其余每个块的支配集合初始化为所有块的全集，表示"还不确定谁不支配它"。然后反复扫描所有非入口块：对每个块 B，取它所有前驱的支配集合的交集，再加上 B 自身。交集的含义是：只有同时支配所有前驱的块，才一定支配 B。重复扫描，直到整轮没有任何集合发生变化。

用菱形 CFG 走一遍完整过程。这是 if/else 编译后的典型形状：

1
2
3
4
5
   B0          ← 入口，条件判断
  /  \
B1    B2       ← if 分支 / else 分支
  \  /
   B3          ← 合流点

前驱关系：B1 和 B2 的前驱都是 B0；B3 的前驱是 B1 和 B2。

初始化（全集用 U 表示 {B0, B1, B2, B3}）：

1
2
3
4
dom(B0) = {B0}
dom(B1) = U
dom(B2) = U
dom(B3) = U

第一轮迭代，按 B1、B2、B3 的顺序处理：

1
2
3
4
5
6
7
8
9
10
11
dom(B1) = dom(B0) ∩ … ∪ {B1}
        = {B0} ∪ {B1}
        = {B0, B1}

dom(B2) = dom(B0) ∪ {B2}
        = {B0, B2}

dom(B3) = dom(B1) ∩ dom(B2) ∪ {B3}
        = {B0, B1} ∩ {B0, B2} ∪ {B3}
        = {B0} ∪ {B3}
        = {B0, B3}

第二轮扫描，每个块的集合都和上一轮相同，算法终止。结果的解读：B0 支配全部四个块；B1 只支配自身；B2 只支配自身；B3 被 B0 和自身支配。在菱形结构中，分支的两侧互不支配，合流点也不被任何一侧支配，只被公共的入口支配。

支配树

把 idom 关系画出来就得到支配树（dominator tree），根是入口块。菱形 CFG 对应的支配树：

1
2
3
    B0
  / | \
B1  B2  B3

B3 的 idom 是 B0 而不是 B1 或 B2——存在一条到 B3 不经过 B1 的路径（B0→B2→B3），所以 B1 不支配 B3，B2 同理。支配树与 CFG 是不同的图；CFG 的边表示控制流跳转，支配树的边表示"最近的必经块"关系。

支配边界

支配边界（dominance frontier，缩写 DF）标记支配范围"刚好结束"的位置。形式定义：块 B 在 DF(A) 中，当且仅当 A 支配 B 的某个前驱 P，但 A 不严格支配 B 本身。换言之，信息从 A 出发可以沿着被 A 支配的路径一直走到 P，但 P 之后的下一步（块 B）就超出了 A 的控制范围——可能有其他路径绕过 A 到达 B。

菱形 CFG 的支配边界：

1
2
3
4
DF(B0) = {}      B0 严格支配所有其他块，没有"结束"的地方
DF(B1) = {B3}    B1 支配 B3 的前驱 B1 自身，但不严格支配 B3
DF(B2) = {B3}    同理
DF(B3) = {}      B3 没有后继

支配边界正是需要插入 phi 节点的位置。如果变量 x 在 B1 和 B2 中分别被赋值，B3 是两者的支配边界，所以 B3 需要一个 phi 节点来合并两个定义。计算支配边界的做法：遍历 CFG 中每条边 P→B，沿支配树从 P 向上走到 idom(B)（不含），途经的每个节点 N 都把 B 加入 DF(N)。这个过程只访问每条 CFG 边一次乘以支配树的高度，效率足够。第 12 篇将直接使用这个结果来放置 phi 节点。

活跃变量分析

变量 v 在某个程序点是活跃的（live），意味着从该点往后存在一条执行路径，路径上会读取 v 的当前值，且在读取之前没有对 v 重新赋值。如果 v 不活跃，它的值就没有后续消费者——赋值给它的指令是死代码，它占用的寄存器可以回收。

按基本块计算两组集合。live_in(B) 是刚进入 B 时活跃的变量集合；live_out(B) 是刚离开 B 时活跃的变量集合。辅助集合 use(B) 包含块内在被赋值之前就被读取的变量，def(B) 包含块内被赋值的变量。数据流方程：

1
2
live_in(B)  = use(B) ∪ (live_out(B) - def(B))
live_out(B) = ∪ live_in(S)，对 B 的所有后继 S 取并集

live_out 的含义：如果某个后继块在入口处需要变量 v，那么在当前块出口处 v 就必须活跃。live_in 的含义：块自身读取的变量当然活跃，另外出口处活跃但在块内没被重新定义的变量，在入口处也活跃。

信息从后继流向前驱，所以这是反向数据流（backward dataflow）。与支配分析的前向传播方向相反——支配信息从入口向后继扩散，活跃信息从出口向前驱回溯。初始化所有集合为空集，从出口方向向入口方向反复迭代，直到不动点。

在循环 CFG 上手算活跃性

用下面的循环 CFG 来演示完整迭代过程。它对应 x = 0; while (x < 10) { x = x + 1; } 这段逻辑简化后的结构：

1
2
3
4
B0: x = 0               → B1
B1: cond(x < 10)        → B2（循环体）或 B3（出口）
B2: x = x + 1           → B1（回边）
B3: (exit)

先列出每个块的 use 和 def：

1
2
3
4
use(B0) = {}      def(B0) = {x}    # 只有赋值，没有读取
use(B1) = {x}     def(B1) = {}     # 条件判断读取 x，不写入
use(B2) = {x}     def(B2) = {x}    # 先读 x 再写 x
use(B3) = {}      def(B3) = {}     # 空块

所有 live 集合初始化为空。按 B3、B2、B1、B0 的顺序迭代（大致从出口到入口）。

第一轮：

1
2
3
4
5
6
7
8
9
10
11
live_out(B3) = {}（无后继）
live_in(B3)  = {} ∪ ({} - {}) = {}

live_out(B2) = live_in(B1) = {}（B1 此轮还未更新）
live_in(B2)  = {x} ∪ ({} - {x}) = {x}

live_out(B1) = live_in(B2) ∪ live_in(B3) = {x} ∪ {} = {x}
live_in(B1)  = {x} ∪ ({x} - {}) = {x}

live_out(B0) = live_in(B1) = {x}
live_in(B0)  = {} ∪ ({x} - {x}) = {}

第一轮结束时，B2 的 live_out 是空集。但 B2 的后继是 B1，而 B1 的 live_in 已经变成了 {x}。这个信息还没有传到 B2。

第二轮：

1
2
3
4
5
6
7
8
9
10
11
live_out(B3) = {}         不变
live_in(B3)  = {}         不变

live_out(B2) = live_in(B1) = {x}   ← 从 {} 变成了 {x}
live_in(B2)  = {x} ∪ ({x} - {x}) = {x}   不变

live_out(B1) = {x} ∪ {} = {x}     不变
live_in(B1)  = {x}                 不变

live_out(B0) = {x}                 不变
live_in(B0)  = {}                  不变

第三轮扫描，所有集合与第二轮相同，算法终止。

这里暴露了循环导致多轮迭代的根本原因。回边 B2→B1 构成了信息的环路：B1 的 live_in 要传给 B2 的 live_out，而 B2 的 live_in 又要传回 B1 的 live_out。在一趟线性扫描中，总有一个方向跟不上另一个方向的更新。只有回头再扫一遍，回边带来的信息才能完整传播。如果循环嵌套更深，需要的轮数也更多。

循环 CFG 的支配关系

同一个 CFG，顺手算一下支配集合：

1
2
dom(B0) = {B0}
dom(B1) = {B0} ∩ dom(B2) ∪ {B1}

B1 有两个前驱：B0 和 B2。但初始时 dom(B2) = 全集，第一轮 dom(B2) = dom(B1) ∪ {B2}。迭代一轮后稳定：

1
2
3
4
dom(B0) = {B0}
dom(B1) = {B0, B1}
dom(B2) = {B0, B1, B2}
dom(B3) = {B0, B1, B3}

支配树：

1
2
3
4
5
  B0
   |
  B1
 /  \
B2   B3

B1 是循环头，它支配循环体 B2 和出口 B3。支配边界：DF(B2) = {B1}，因为 B2 支配 B1 的前驱 B2，但 B2 不严格支配 B1。B1 恰好是循环头——phi 节点应当放在这里，合并 x 在 B0（初始赋值）和 B2（循环体内的更新）中的两个定义。

不动点为什么总能收敛

这两种分析的收敛依据相同：每轮变化是单调的，且值域有限。支配集合在每轮中只能缩小或保持不变，因为交集运算不会引入新元素——集合从全集开始，只可能丢掉不该在里面的块。活跃集合在每轮中只能扩大或保持不变，因为并集运算不会删除已有元素——集合从空集开始，只可能发现更多需要保留的变量。

块的数量和变量的数量都是有限的，所以集合能变化的次数有上界，迭代必然终止。对于可归约的 CFG（由 if/while 等结构化控制流产生的正常程序），迭代次数通常很少——循环嵌套深度加一到两轮就够了。不可归约 CFG（含有多入口循环）仍然收敛，但可能需要更多轮次。

练习

取以下嵌套循环 CFG：

1
2
3
4
5
B0 → B1
B1 → B2（内层循环体）, B4（外层出口）
B2 → B3
B3 → B2（内层回边）, B1（外层回边）
B4（exit）

假设 B0 定义变量 y，B2 使用 y，B3 定义 y。

  1. 计算每个块的支配集合和支配树。
  2. 计算 DF(B2) 和 DF(B3)，说明 phi 节点应放在哪里。
  3. 手算活跃集合，记录每轮的变化，确认至少需要两轮迭代才能收敛。
  4. 列出从 B0 到 B2 的所有不重复路径，逐条验证支配关系的正确性。

上一篇：10 - 基本块、跳转与 CFG。下一篇：12 - SSA 构造与 phi 节点。