8.1 数据流分析与优化合法性：删掉的代码为什么真的能删

编译器前端经过词法、语法和语义分析后生成 TAC 或 SSA 形式的 IR。它语义正确，却可能包含临时变量、未使用赋值和重复计算。后端必须先证明变换合法，再生成目标机器码；“看着多余”不算证明。

优化的目标不是让 IR 更短，而是在源语言允许的可观察行为范围内生成成本更低的等价程序。

本课目标

• 用 CFG 数据流方程理解跨块事实；
• 区分常量折叠、传播、CSE、DCE 与 LICM；
• 为溢出、浮点、内存和异常建立合法性条件；
• 维护 pass 前置条件、分析缓存和验证器。

1. 基本块内并不意味着无需证明

t0 = add a, b
t1 = mul t0, c
t2 = add a, b
t3 = mul t2, d

若 a、b 在两次 add 间未改变，且 add 具有相同类型、溢出与异常语义，可让 t2 复用 t0。在 SSA 中操作数 identity 已经固定，但内存读取、调用和浮点环境仍可能阻止合并。

常见局部转换：

• constant folding：编译时计算常量表达式；
• algebraic simplification：如在合法条件下 x+0 → x；
• common subexpression elimination：复用已算表达式；
• copy propagation：用来源替换纯复制；
• dead code elimination：删除无用且无副作用的定义。

每个转换都要列前置条件。整数是否模 $2^n$ 回绕、溢出是否 trap 或未定义，会改变重分组和强度削弱的合法范围。对普通整数，x+0 本身不会溢出；浮点 x+0 却还要考虑有符号零等规则。前置条件应针对具体转换，不能只笼统写“注意溢出”。

2. 数据流分析是图上的不动点

以“到达定义”为例，块 $B$ 的入口事实来自所有前驱出口的合并：

$$IN[B]=\bigcup _{P\in pred(B)}OUT[P],$$$$OUT[B]=GEN[B]\cup (IN[B]-KILL[B]).$$

从初始值开始反复更新，直到所有集合稳定。循环让信息沿回边多次传播，所以不能只按源码顺序扫一遍。

不同分析的方向和合并操作不同：

• reaching definitions：前向、并集；
• available expressions：前向、交集；
• liveness：后向、并集；
• definite assignment：通常前向、交集。

选择初始值还与 may/must 分析有关。到达定义是 may 分析，下面从空集增长，并把参数或外部初始定义放入入口边界；must 分析通常需要不同的初始化。有限格与单调传递函数保证这种迭代终止，其他抽象域可能需要 widening。方程写对但边界条件错，仍可能漏掉真实路径。

这个完整示例的 CFG 是 entry → header → body → header，并有 header → exit。d0、d1 是对同一变量 x 的两个定义；到达定义集合保存的是定义身份，不是变量名。入口没有外部定义：

pred = {
    "entry": [], "header": ["entry", "body"],
    "body": ["header"], "exit": ["header"],
}
gen = {"entry": {"d0"}, "header": set(), "body": {"d1"}, "exit": set()}
kill = {"entry": {"d1"}, "header": set(), "body": {"d0"}, "exit": set()}
inside = {block: set() for block in pred}
outside = {block: set() for block in pred}
changed = True
while changed:
    changed = False
    for block, parents in pred.items():
        incoming = set().union(*(outside[parent] for parent in parents))
        outgoing = gen[block] | (incoming - kill[block])
        changed |= incoming != inside[block] or outgoing != outside[block]
        inside[block], outside[block] = incoming, outgoing
print(sorted(inside["header"]))  # ['d0', 'd1']
print(sorted(outside["body"]))   # ['d1']

3. 常量传播与分支可达性

普通常量传播记录 value 是常量、非常量还是未知。稀疏条件常量传播（SCCP）同时追踪 SSA value 与可执行 CFG 边：

cond = const false
br cond, then, else

若 then 边不可执行，汇合点来自这条不可执行路径的 φ 输入可被忽略，死分支内的计算也可进一步删除。这里的“不可达”由当前 IR 语义证明，不是基于一次运行采样猜测。

折叠操作必须使用目标语义而不是编译器宿主语言的默认行为。例如交叉编译时整数位宽、浮点格式和舍入规则可能不同。

4. DCE 要问结果与效果

t = pure_add a, b       // t 无使用，可删
u = load volatile p     // u 无使用，仍不可随意删
v = call write_log()    // 返回值无使用，调用有副作用
w = div x, y            // 若可能 trap，删除会改变行为

IR 应显式或通过指令描述表回答：

• 是否读写内存；
• 是否可能抛异常或 trap；
• 是否 volatile/atomic；
• 是否与外部状态交互；
• 是否保证终止；
• 是否影响浮点状态或同步顺序。

“结果没人用”只证明数据结果是死的，不证明操作本身不可观察。

5. CSE、GVN 与内存别名

对纯 SSA 运算，可按 opcode、类型、操作数和语义标志构造 value number；浮点与溢出标志不能遗漏。复用一个等价值还要求该定义在替换后的使用点可用，例如支配普通 SSA 使用。相同编号本身不证明控制流条件满足。

内存读取更难：

x = load p
store q, 1
y = load p

对这里的普通、非原子且非 volatile 读写，只有证明 p 与 q 的访问字节范围不重叠，或 store 不影响该 load，并满足其他内存语义条件，才能令 y=x。仅有 p != q 不一定证明多字节范围不重叠。别名分析通常保守回答 may-alias；不确定时放弃优化，保证正确性。

调用也可能读写未知内存。函数效果摘要、readonly/pure 属性与跨过程分析能扩大优化范围，但错误属性会直接造成错误代码。

6. 循环不变代码外提

把循环内表达式移到 preheader，需要至少证明：

• 操作数在循环中不变；
• 新位置执行不会引入原本不会发生的异常；
• 内存读取未被循环中的可能别名写入改变；
• 移动不违反原子、volatile 或同步顺序；
• 若循环可能零次，新位置提前执行仍可观察等价。

for (...) {
    t = a * b
    use(t)
}

若 a*b 无可观察效果且可安全推测执行，通常容易外提；仅仅“不写内存”并不排除 trap、异常或不终止。可能除零的除法移到循环前，在零次循环时会凭空制造异常。

7. 强度削弱需要正确例子

设 i 从零开始，每次递增一，原循环计算字节地址：

address = base + i * 8

可引入归纳变量：

address = base
若还有下一轮，address += 8

这把每轮乘法变成加法，但还要证明迭代次数、溢出、指针越界和退出路径语义一致。现代硬件上乘法未必昂贵，转换价值要结合目标成本模型。

“把 i=i*2 改为 i=i+1”改变了数列，不是强度削弱。

8. 浮点优化受语义约束

浮点加法不保证结合律，存在满足下式的输入，并不是任意三个数都会不相等：

$$(a+b)+c\ne a+(b+c).$$

在常见的 IEEE 754 binary64 Python 实现上：

a, b, c = 1e16, -1e16, 1.0
print((a + b) + c)  # 1.0
print(a + (b + c))  # 0.0

NaN、无穷大、有符号零、舍入模式和异常标志也会影响转换。编译器只有在语言规则、显式 fast-math 标志或已证明条件允许时，才能做 reassociation、把除法换成倒数乘法等变换。

这与交换律不是同一问题。对普通有限值，a+b 与 b+a 通常相同；真正普遍受限的是重分组和特殊状态语义。

9. Pass 管线要维护分析有效性

一个 pass 改 CFG 后，支配树、循环信息、liveness 等缓存可能失效。pass manager 应让转换声明：

• 需要哪些分析；
• 保留哪些分析；
• 修改了 CFG、指令还是类型；
• 运行后需调用哪些 verifier。

优化次序也会互相启发：常量传播暴露死分支，DCE 删除残余，简化 CFG 又为下一轮 φ 简化创造机会。应设置收敛条件和迭代预算，防止两个转换来回改写。

常见误区

• 数学等价就能优化：源语言的溢出、异常和浮点语义可能区分它们。
• 无使用结果的指令都是死代码：操作本身可能有可观察效果。
• 别名分析不确定时可以猜不别名：优化器应保守放弃，除非语言契约提供保证。
• 优化 pass 独立运行即可：CFG 改写会使其他分析结果失效。

练习

1. 对一段含分支的 IR 写 reaching-definitions 方程并迭代到稳定。
2. 判断 load、volatile load、纯函数调用和可能 trap 的除法能否在结果未用时删除。
3. 给 LICM 构造一个“循环零次导致提前异常”的反例。
4. 为一个 CFG 简化 pass 列出必须失效的分析缓存。

小结

优化不是模式替换合集，而是带证明义务的程序变换。数据流分析提供跨路径事实，IR 效果模型和语言语义决定哪些转换合法，pass 管线则负责维护这些事实仍然有效。

下一课把优化后的虚拟操作交给目标机器：选择合法指令、遵守 ABI，并把无限虚拟寄存器放进有限物理寄存器。