4.2 到达定值与活跃变量：不动点迭代实战

4.2 到达定值与活跃变量：不动点迭代实战

本节摘要：到达定值（前向 may）回答"这个程序点上，x 的值可能来自哪次赋值"；活跃变量（后向 may）回答"x 以后还会不会被读"。两者是数据流框架使用频率最高的两次落地：前者养活常量传播与传播类优化，后者养活死代码删除与寄存器分配。本节用同一段代码把两个分析从 gen/kill 到逐轮迭代完整手算一遍，并给出工作表算法的伪代码与位向量实现要点。读完你应当能独立对 5 块以内的 CFG 做出正确的不动点计算，且知道轮数为什么不会爆炸。

4.1 把框架立起来了，本节让它动起来。选这两个分析做实战有讲究：到达定值是前向代表，活跃变量是后向代表——方向一换，方程、初值、遍历顺序全要跟着换，正好把 4.1 的四象限踩实两格。

一、样例与基本块划分

先立题目。下面这段代码连同它的 CFG，是本节全程的唯一练习场：

B0:  i = 1              ← 定值 d1: i
     j = 0              ← 定值 d2: j
     goto B1
B1:  if i <= 10 goto B2 else goto B4     ← 循环头，两个前驱
B2:  j = j + i          ← 定值 d3: j
     t = a[i]           ← 定值 d4: t
     i = i + 1          ← 定值 d5: i
     goto B1
B4:  use j              ← 循环出口
​

基本块 B3 在此省略（假设 else 分支直接跳到 B4，不影响演示）。注意 B1 是天然汇合点：i 有两个来路（B0 的 d1 与 B2 的 d5），这个形状跟 3.2 讲 phi 时的循环例子一模一样——phi 置放的位置感，本质上就是到达定值分析给的。

二、到达定值：gen/kill 与逐轮迭代

对每个块算两个集合。gen：块内最后一次定值及其之前的、未被覆盖的定值——"穿过这个块后，哪些定值仍然活着"。kill：块内被覆盖掉的定值——"进入块前已有的定值里，哪些被本块的重新定值废掉了"。

gen(B0) = {d1, d2}   kill(B0) = {d5, d3}   # d1 废掉所有旧 i 定值，d2 废 d3
gen(B1) = {}         kill(B1) = {}
gen(B2) = {d3, d4, d5}  kill(B2) = {d2, d1}
gen(B4) = {}         kill(B4) = {}
​

初值纪律：may 分析从 ⊥（空集）起步，但入口块 IN 额外补上"越过入口边界的伪定值"（未初始化变量的来路，严格实现会记进这里）。方程：IN[n] = ∪ OUT[p]，OUT[n] = gen[n] ∪ (IN[n] − kill[n])。按 B0 → B1 → B2 → B4 的顺序迭代：

解读第2轮的 IN[B1]：从 B0 直接来时 i 的来路是 d1；绕循环一圈来时是 d5；j 的来路只剩 d3（d2 在 B2 里被杀）。j = j + i 里的 j 是"上一圈的 j"——到达定值把"上一圈"这个动态概念变成了静态集合。基于此可以做的判断：IN[B4] 里的 j 来路只有 d3，说明 j 必定在 B2 被赋过值，"使用未初始化变量"的警告就长在这类事实上。

三、活跃变量：方向反转后的再演练

活跃变量问"x 在此点之后还会被读吗"，信息从后往前流：IN[n] = use[n] ∪ (OUT[n] − def[n])，OUT[n] = ∪ IN[s]（s 遍历后继）。初值从出口边界（⊥ 或"live-out 汇点"）开始，遍历顺序建议逆着控制流：B4 → B2 → B1 → B0。

第1轮: IN[B4] = {j}          # 出口处 j 仍被用
       IN[B2] = {j, i, a}    # use j?否——但 OUT[B2] 含 B1→B2 传来的 {i,j}，减 def {j,t,i} 加 use {a,i,j}
       IN[B1] = {i, j}       # use i(判断), 传出 {j,i,a} 减无 def
第2轮: OUT[B2] = IN[B1] = {i,j} → IN[B2] = {a, i, j}   # 稳定
第3轮: 无变化，收敛
​

逐块读一遍结果。IN[B2] 含 a：数组 a 在循环体内被读，寄存器分配要给它留位置（或每次访存）。t 不在任何 IN 里：t 定义后只在块内被用——若这个用途也取消了，t 的定值就是死代码，可整条删除。这就是活跃变量喂给死代码删除的判定方式：定值 d 死亡当且仅当它定义的变量在 d 之后立刻不活跃；删除引发级联（供数指令跟着死），直到不动。

四、工作表算法与实现要点

朴素的"每轮扫全部块"在块多的函数上浪费明显。工作表（worklist）算法只把"输出变了"的块的后继（前向）或前驱（后向）重新排队：

Worklist(cfg, 方向, gen, kill):
    for n in cfg: IN[n]=⊥; OUT[n]=⊥        # may 分析初值
    入口/出口边界条件补齐（含伪定值）
    W = 全部块（按逆后序/正后序入队）
    while W 非空:
        n = W.pop()
        old = OUT[n]
        IN[n]  = ∪ OUT[p] for p in preds(n)   # 前向；后向换成 succ 与 IN/OUT 对调
        OUT[n] = gen[n] ∪ (IN[n] − kill[n])
        if OUT[n] ≠ old:
            for s in succ(n): W.push(s)       # 只惊动受影响的邻居
​

实现层面三条经验。其一，位向量是集合的自然编码：每个定值/变量占一位，并交减对应位运算，一块 64 位字吞下几十个元素，现代编译器的经典分析几乎全走位向量。其二，遍历序决定轮数：逆后序让前向分析"顺着流走"，每圈至多回头一次；乱序也能收敛，只是白转。其三，不动点不要求最速：工作表收敛到的不动点与全量迭代相同（单调性保证），选择只影响速度。

⚠️ 易错点：后向分析的 OUT 初值忘补"程序出口仍然活跃"的变量（比如作为返回值的全局、跨函数可见的名字）。初值纪律错了，收敛照样发生——只是收敛到错误的不动点，且不报任何错。

本节要点回顾：

• gen/kill 是分析语义的全部压缩：块内"新造什么、废掉什么"，一进一出两个集合；
• 到达定值（前向 may）：汇合点取并，j = j + i 的"上一圈"从此可静态枚举；
• 活跃变量（后向 may）：死代码判定 定值后立刻不活跃，删除会级联到不动；
• 工作表算法：变化驱动，位向量加速，逆后序压轮数；结果与全量迭代一致；
• 初值纪律：may 从 ⊥、must 从 ⊤，出口/入口边界条件别漏。

两个分析都还只盯着标量。下一章先解决"控制流长什么样"的结构问题，把循环圈出来——4.2 这个 10 圈的循环之所以能被优化，靠的正是下一节的支配树。