#compilers #优化
本页目录

经典优化

七种每个优化 pipeline 必做的经典优化——从常数折叠到循环不变量外提到 SROA——每一种如何利用数据流分析找到机会,以及不能做时的硬限制(副作用、volatile、不可规约控制流)。

概述

数据流分析提供了"在某点,哪个表达式已计算过/哪个变量还活着"的信息。这篇讲利用这些信息做什么:七个工业编译器必做的优化,每种怎么用数据流分析的结果找到优化机会,以及什么时候不能做(制约条件比你想的多)。这些优化在 LLVM 里对应不同 pass,在编译流水线里被反复跑——一 pass 的优化为下一 pass 创造机会。

所有优化的前提:在 SSA 形式 下做。SSA 的 def-use 链让每项优化都是 O(n) 或 O(n log n) 的稀疏操作。

1. 常数折叠与传播

常数折叠(constant folding):编译时计算常量表达式:

x = 2 + 3    →  x = 5
y = a * 0    →  y = 0

常数传播(constant propagation):把所有用到常量定义的地方替换为常量:

x = 5
y = x + 1    →  y = 6

这两通常在同一个 pass 做(一遍传播,一遍折叠,递归直到饱和)。SSA 下只需沿着 def-use 链替换,不需要数据流分析——每个变量的定义点在 SSA 中唯一。

条件(conditional constant propagation)更强:利用 if (false) { ... } 的常量条件消除不可能分支,让分支内的代码不被编译——这是 Wegman-Zadeck 算法的核心,基于 SSA 的稀疏条件常数传播(SCCP)。

2. CSE(公共子表达式消除)

问题⁠:a = b + c; ... ; d = b + c 如果 b 和 c 在中间都没被修改,第二次 b + c 是公共子表达式,可以直接用 a 的值。

实现依赖于 available expressions(来自 数据流分析):

对于每个表达式 e = x op y:
  在 available expressions 信息中查: e 在当前点是否"仍有效"
  如果有效: 用已有的结果, 删除当前计算
  否则: 保留当前计算, 标记 e 为"在此处可用"

LLVM 用 GVN(Global Value Numbering) 做 CSE 的泛化——不只看"同一表达式的两次出现",而是给每个值分配一个编号,两个不同表达式的值如果相等(如 x+1 和 1+x,交换律成立时编号相同),共享同一值。

3. DCE(死代码消除)

问题⁠:一条指令产出的值如果从未被使用,这条指令可以删除。

DCE 在 SSA 下极其简单——沿 def-use 链:

worklist = 所有指令
for 每条指令:
    if 该指令的产出的值无使用者 (use 列表为空) 且 该指令无副作用 (不是 store/call/IO):
        标记为 dead
        对该指令的每个操作数: 检查该操作数的定义者, 可能因为失去这个使用者而变 dead
迭代直到不动点

不能消除的几条硬限制:store(改变内存,可能被其他地方 load)、call(可能有副作用,即使返回值没被用)、volatile load/store(显式要求保留)。有副作用的指令只能消除当编译器证明该副作用的值也不被观察——这需要更重的分析(如 MemorySSA,见下)。

4. Inlining(内联)

问题⁠:call @f 把 f 的函数体直接复制到调用点,消掉函数调用开销(传参/跳转/返回),并为后续优化暴露上下文(函数体在特定参数值下可能触发新的常数折叠/CSE/DCE)。

内联的取舍不是"做或不做",而是什么时候做⁠:

决策因素:
  - 函数体大小 (小函数内联, 大函数可能不 -- 阈限可调)
  - 调用次数 (只调用一次的函数, 内联后可直接删除原函数体)
  - 循环内调用 (循环体里的调用更多被内联, 因为内联后可能触发循环优化)
  - 递归函数只内联前 N 层 (防止无限展开)

LLVM 的内联 pass 基于 cost model——每个 call site 估算内联后 size 变化和性能收益,逐个决定。

5. LICM(循环不变量外提)

问题⁠:在循环体里每次迭代都计算同一个值的表达式,提到循环外只算一次:

while (i < n) {                    t = a + b          ← 提到循环之前
    x = a + b;        →           while (i < n) {
    i = i + 1;                         i = i + 1;
}                                  }

实现依赖 loop detection(找自然循环——有一个 header block 支配所有 body block,且有一个 back edge 回到 header):

对于循环 L 中的每条指令 instr:
    if instr 的操作数在循环内都不变 (是循环常量的定义, 或来自循环外):
        if instr 在所有到达它的路径上都被同一条指令支配 (不会从某些路径跳过):
            if instr 没有副作用:
                把 instr 移到循环前置块 (preheader)  → 原位置删除

前两个条件保证"移出去不会改变语义",第三个排除有循环依赖的指令。

6. Loop Unrolling(循环展开)

复制循环体 N 次,减少分支/回边/归纳变量更新的开销:

for i in 0..4:                     a[0] = b[0] + c[0]
    a[i] = b[i] + c[i]      →     a[1] = b[1] + c[1]
                                   a[2] = b[2] + c[2]
                                   a[3] = b[3] + c[3]

LLVM 默认展开 2–4 次,完全展开只在循环边界是编译时常量时。展开后常触发 CSE 和向量化(SLP)——相邻的两个 load 变成一次 SIMD load。

7. SROA(Scalar Replacement of Aggregates)

把"整个结构体的 alloca + load/store 字段"替换为"每个字段独立变量":

原始:                              SROA 后:
%struct = alloca {i32, float}      ; (alloca 被拆掉)
%f0 = gep %struct, 0, 0           %x = ...
store i32 %x, ptr %f0             %y = ...
%f1 = gep %struct, 0, 1           %add = add i32 %x, ...
store float %y, ptr %f1
%r = load i32, ptr %f0            → 每个字段变成独立 SSA 虚拟寄存器
%add = add i32 %r, 1              mem2reg 继续把 load/store 提升掉

SROA 是 mem2reg 的前置——把聚合拆成字段,才能 mem2reg 把每个字段单独提升到 SSA。两者搭配是 LLVM 优化 pipeline 开机第一组 pass。

优化顺序与重复跑

优化 pass 不是跑一次就够——A pass 的优化为 B pass 创造新机会,B pass 又为 A pass 创造新机会。LLVM 的 pass pipeline 反复跑多轮(内联→CSE→DCE→LICM→...),每轮清理上一轮的残渣。循环优化(LICM + Unrolling)常单独放一阶段,集中做大规模循环变换,然后跟着新一轮标量优化。

参考

  • Dragon Book: Chapters 9–10 — 机器无关优化的完整分类
  • Cooper/Torczon: "Engineering a Compiler", Chapters 8–10 — 每种优化的算法和伪代码
  • LLVM: lib/Transforms/Scalar/ (标量 pass), lib/Transforms/IPO/(过程间 pass), lib/Analysis/ (数据流分析)

Keywords: constant folding, constant propagation, SCCP, CSE, common subexpression elimination, GVN, global value numbering, DCE, dead code elimination, inlining, cost model, LICM, loop invariant code motion, loop unrolling, SROA, scalar replacement, mem2reg, pass pipeline, phase ordering

相关页面

© 2026 liz's doc