1. 优化概述与 IR 优化框架
一句话总结： 优化在保持程序语义的前提下减少执行开销，框架上呈现为一系列可重复执行的 IR 变换。
优化不做任何功能上的改动，只追求更少的指令、更少的内存访问与更快的执行路径。优化分为机器无关优化（在 IR 层）与机器相关优化（在指令选择与寄存器分配层）。框架上，优化器通常按遍（pass）组织，每遍实现一个变换，遍与遍之间保持 IR 不变式，例如 SSA 性质或基本块边界。
原始三地址码:
t1 = 2 * 10
t2 = a + t1
x = t2
常量折叠后:
t1 = 20
t2 = a + t1
x = t2
| 优化类别 | 典型变换 | 收益来源 |
|---|---|---|
| 常量类 | 常量折叠、常量传播 | 消除运行时计算 |
| 死代码类 | 无用赋值删除 | 减少指令数 |
| 冗余类 | 公共子表达式消除 | 复用计算 |
| 循环类 | 不变量外提、强度削减 | 降低循环代价 |
| 数据流类 | 到达定义、活跃分析 | 支撑其余优化 |
优化的正确性要求每次变换保持观察语义：可观察的副作用（内存写入、外部调用、异常）不能改变顺序或删除。编译器通常引入内存依赖分析来区分纯计算指令与有副作用的指令，宁可保守也不冒险做错优化。
2. 常量折叠与常量传播
一句话总结： 常量折叠在编译期直接计算常量表达式，常量传播把已知常量沿数据流传递到使用处。
常量折叠是最简单的优化：形如 t1 = 2 * 10 的指令在编译期就算出 20。折叠对字面量运算、类型转换、取数组长度等纯函数操作都适用。常量传播更进一步：当某变量确定持有常量值时，所有读取该变量的指令都能用常量替换，从而为后续折叠创造机会。两者往往交替执行直至不动点。
def constant_propagation(cfg):
worklist = list(cfg.blocks())
values = {v: UNDEF for v in all_vars(cfg)}
while worklist:
b = worklist.pop()
for insn in b.instructions:
if insn.op == "const":
values[insn.dest] = insn.value
elif is_binary(insn.op):
l = values.get(insn.left, UNDEF)
r = values.get(insn.right, UNDEF)
if l is not UNDEF and r is not UNDEF:
insn.replace_with_const(fold(insn.op, l, r))
values[insn.dest] = fold(insn.op, l, r)
elif l is UNDEF and r is UNDEF:
values[insn.dest] = UNDEF
else:
values[insn.dest] = NOT_CONST
| 传播状态 | 含义 | 处理 |
|---|---|---|
| UNDEF | 从未定义 | 等待定义 |
| 常量 c | 确定常量 | 替换使用处 |
| NOT_CONST | 不可能是常量 | 停止传播 |
| 汇合处 | 不同路径值不一 | 取公共值 |
常量传播的关键是路径汇合处的处理：两条路径一个给常量、一个给非常量，则汇合点后视为非常量。这可以用格（lattice）理论建模。过度传播常量会引入语言差异，例如浮点折叠可能改变舍入行为，因此多数编译器默认不开浮点重关联，或通过 -ffast-math 类选项显式开启。
2.1 格上的传播与汇合
常量传播可以用格论建模：每个变量的信息处于「未定义、某常量、非常量」三值格中。两个路径汇合时取两者的最大下界，非常量是所有常量的上界。这样一套统一的抽象解释框架不仅能处理常量，还能推广到区间分析与符号分析，同一份迭代引擎复用多种抽象。
格结构:
┌────────────┐
│ NOT_CONST │ ← 顶元素
├────────────┤
│ ...常量...│
├────────────┤
│ UNDEF │ ← 底元素
└────────────┘
汇合规则:
const(c) ⊓ const(d) = const(c) 若 c == d
const(c) ⊓ NOT_CONST = NOT_CONST
UNDEF ⊓ x = x
3. 死代码消除
一句话总结： 死代码消除删除结果永不被使用的赋值，尤其针对常量传播后暴露的冗余。
死代码有两类：一类是永远执行不到的指令，另一类是定义后从未被读取的赋值。后者称为不可达定义，是死代码消除的主要目标。做法是先做活跃变量分析，找出每个程序点的活跃变量集合，然后删除所有「定义变量不活跃」的赋值指令。删除本身可能暴露新的死代码，因此要迭代到不动点。
死代码消除前:
t1 = 1
t2 = 2
t3 = t1 + t2 # t3 之后从未使用
x = 5
return x
消除后:
x = 5
return x
def liveness(cfg):
live_out = {b: set() for b in cfg.blocks()}
changed = True
while changed:
changed = False
for b in reversed(cfg.blocks()):
# gen: 先用后定义的变量; kill: 被定义的变量
live_in = (live_out[b] - b.kill) | b.gen
if live_in != live_out[b]:
live_out[b] = live_in
changed = True
return live_out
def remove_dead_code(cfg, live_out):
for b in cfg.blocks():
for insn in b.instructions:
if defines_var(insn) and insn.dest not in live_out[b]:
if not has_side_effect(insn):
b.remove(insn)
| 死代码来源 | 示例 | 分析工具 |
|---|---|---|
| 冗余赋值 | x = 1; x = 2 | 活跃变量 |
| 未使用临时量 | 表达式展开产物 | 活跃变量 |
| 常量传播后 | 条件永远假的分支 | 常量传播 |
| 不可达分支 | return 后语句 | 可达性分析 |
死代码消除是优化循环的收尾步骤：很多优化会产生冗余定义，例如公共子表达式消除后原计算指令变为死代码。注意有副作用的调用（I/O、内存写）不能被误删，即便其结果未使用。这条约束是所有删除类优化的安全底线。
4. 公共子表达式消除
一句话总结： 公共子表达式消除让相同的计算只执行一次，用已计算的值替换重复计算。
当同一表达式的计算在相同操作数下重复出现且中间操作数未被修改时，第二次计算可以复用第一次的结果。这种优化在数组下标计算、指针寻址与循环体内反复出现的计算中收益巨大。全局公共子表达式消除需要支配关系：第一次计算必须支配第二次计算，才能保证第一次的值在第二次处仍然可用。
def gvn(blocks):
# 全局值编号: 为每个表达式分配编号
value_table = {}
for b in blocks:
for insn in b.instructions:
key = (insn.op, insn.left, insn.right)
if key in value_table:
# 用已编号的值替换本指令
insn.replace_with(value_table[key])
else:
vn = fresh_value_number()
value_table[key] = vn
insn.value_number = vn
| 场景 | 原始 | 优化后 |
|---|---|---|
| 下标计算 | a[i4+1] 与 b[i4+1] | 提取公共 t |
| 循环外提 | 循环内 constant 计算 | 移出循环 |
| 指针寻址 | p->x 多次访问 | 计算一次地址 |
| 调用去重 | 纯函数同参数 | 复用结果 |
实现上常用值编号（value numbering）：把表达式规范化为键，相同键即相同值。本地版本在基本块内做线性扫描，全局版本依赖支配树。公共子表达式消除与常量传播、复写传播配合使用，效果远好于单独应用。危险之处在于别名：若两个内存位置可能被中间指令修改，就不能安全复用。
5. 循环优化
一句话总结： 循环是性能热点，循环优化把开销从循环内搬到循环外，或把高强度运算降级为低强度运算。
循环优化首先识别循环结构，常用自然循环定义：有单一入口、从入口可到达内部任意块、从任意内部块可回到入口。循环不变代码外提把循环体内不随迭代变化的计算搬到循环之前执行；强度削减把乘法变成加法；循环展开减少分支开销；循环合并与交换则用于改善缓存与并行性。
强度削减前:
for i in 0..n:
t = i * 4
use(t)
强度削减后:
t = 0
for i in 0..n:
use(t)
t = t + 4
| 循环优化 | 做法 | 风险 |
|---|---|---|
| 不变代码外提 | 移至前置块 | 需保证循环至少执行一次 |
| 强度削减 | 乘转加 | 溢出行变更敏感 |
| 循环展开 | 复制循环体 | 代码膨胀 |
| 循环分布 | 拆成多个循环 | 局部性损失 |
| 循环融合 | 合并相邻循环 | 数据依赖检查 |
循环不变量外提需要证明该计算在循环内结果不变，例如操作数不被循环内语句修改。强度削减把 i * 4 变为每次加 4 的递推，关键是正确初始化与同步。循环展开以空间换时间，减少跳转与分支预测开销。这些优化在 LLVM 的 LoopInfo 与 GIMPLE 的 loop pass 中均有成熟实现。
6. 数据流分析基础
一句话总结： 数据流分析以传递函数在格上迭代到不动点，是众多优化共享的公共基础设施。
数据流分析把程序抽象成在格上传播的事实：每个程序点维护一个信息集合，指令作为传递函数修改集合。经典分析包括到达定义、活跃变量、可用表达式与可能用变量。框架上，从入口或出口按前向或后向传播，遇到汇合处按交或并合并，直到集合不再变化。位向量与工作表算法让分析高效。
def reaching_definitions(cfg):
# 前向传播, 汇合取并集
in_defs = {b: set() for b in cfg.blocks()}
out_defs = {b: set() for b in cfg.blocks()}
changed = True
while changed:
changed = False
for b in cfg.blocks():
in_defs[b] = set.union(*(out_defs[p] for p in b.preds))
new_out = (in_defs[b] - b.kill) | b.gen
if new_out != out_defs[b]:
out_defs[b] = new_out
changed = True
return in_defs, out_defs
| 分析 | 方向 | 汇合 | 格信息 | 用途 |
|---|---|---|---|---|
| 到达定义 | 前向 | 并 | 定义集合 | 常量传播 |
| 活跃变量 | 后向 | 并 | 变量集合 | 死代码、寄存器 |
| 可用表达式 | 前向 | 交 | 表达式集合 | CSE |
| 可能用变量 | 后向 | 并 | 变量集合 | 活跃变量变体 |
数据流分析的框架性认识让编译器可以统一实现多种分析，只需更换传递函数与合并算子。迭代到不动点的终止性依赖格的高度有限，位向量表示保证有限格。大规模函数上分析性能由工作表顺序与位向量长度决定，循环嵌套深时还需注意迭代次数可能退化为多项式级。
6.1 从框架到具体分析
每个数据流分析只需向框架提供四件套：方向（前向或后向）、合并算子（交或并）、传递函数与初始值。例如活跃变量分析是后向传播、汇合取并集、gen/kill 作传递函数；可用表达式分析是前向传播、汇合取交集。框架的复用让编译器新增分析时只需写几十行描述而非整套迭代循环，也便于统一做稀疏化与并行化加速。
class DataflowProblem:
def __init__(self, direction, meet, transfer, init):
self.direction = direction # fwd / bwd
self.meet = meet # set.union / set.intersection
self.transfer = transfer # gen/kill 函数
self.init = init # 空集或全集
def solve(cfg, prob):
in_facts = {b: prob.init for b in cfg.blocks()}
out_facts = {b: prob.init for b in cfg.blocks()}
changed = True
while changed:
changed = False
for b in cfg.blocks():
if prob.direction == "fwd":
in_facts[b] = prob.meet(*(out_facts[p] for p in b.preds))
else:
out_facts[b] = prob.meet(*(in_facts[s] for s in b.succs))
new = prob.transfer(b, in_facts[b] if prob.direction == "fwd"
else out_facts[b])
if new != out_facts[b] if prob.direction == "fwd" else new != in_facts[b]:
changed = True
if prob.direction == "fwd":
out_facts[b] = new
else:
in_facts[b] = new
return in_facts, out_facts
7. SSA 上的优化
一句话总结： SSA 让每个变量只有一个定义点，优化算法因此更简单、更精确，也更容易证明正确性。
SSA 形式下，常量传播变得直接：变量定义即确定其常量状态，汇合处用 φ 函数处理多值。死代码消除在 SSA 上等价于删除「无使用处」的定义，无需复杂活跃分析。全局值编号在 SSA 上可精确到每个版本变量。循环分析在支配树上可直接识别自然循环。
def ssa_dce(fn):
# 删除所有 use 为空的定义与纯计算
changed = True
while changed:
changed = False
for insn in fn.instructions:
if defines(insn) and not insn.uses:
if not has_side_effect(insn):
fn.remove(insn)
changed = True
def ssa_constant_prop(fn):
for insn in fn.instructions:
if insn.op == "const":
for use in insn.dest.uses:
if is_binary(use.op) and both_const(use):
fold_const_binary(use)
| SSA 优化 | 非 SSA 等价物 | 简化点 |
|---|---|---|
| 全局值编号 | 可用表达式 | 无需考虑重叠定义 |
| 常量传播 | 到达定义传播 | φ 合并即精确 |
| 死代码消除 | 活跃变量分析 | 直接按 use 计数 |
| 循环不变量外提 | 定义支配检查 | 支配树现成 |
SSA 让优化器的正确性论证大幅简化，因此 LLVM 与 GCC 的中层优化几乎都建在 SSA 上。SSA 并非银弹：φ 函数的插入位置需要支配边界计算，寄存器分配前还要消去 SSA。但综合收益使 SSA 成为现代编译器优化 IR 的事实标准。
8. 总结
| 环节 | 要点 |
|---|---|
| 优化框架 | 按遍执行、保持 IR 不变式 |
| 常量折叠 | 编译期算完纯常量表达式 |
| 常量传播 | 沿数据流把常量送到使用处 |
| 死代码消除 | 删除不可达与不可活跃定义 |
| 公共子表达式 | 支配下复用相同计算 |
| 循环优化 | 外提、削减、展开等热点手段 |
| 数据流分析 | 格上迭代不动点的公共底座 |
| SSA 优化 | 唯一定义让分析与证明更简单 |
中间代码优化在不改变语义的前提下把程序打磨得更快，是编译器中工程密度最高的部分之一。优化的取舍永远在正确性、编译时间与运行性能之间平衡。下一站将把优化后的 IR 翻译成目标机指令。
延伸阅读
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。