读 LLVM 源码、读 paper、追编译器 pipeline 时,经常碰到 DCE GVN LICM SCCP 这种缩写炸弹。每个名字背后都是一个独立的算法 + 一个独立的术语圈。本文不是教你怎么实现这些 pass,而是给你一张速查表——每个 pass 给出英文全称、中文意思、做什么、为什么有用。
0. 阅读说明
按”优化作用的范围”分六类:
本地(单 op / 单 block) → 函数级 → 循环 → 跨函数 → 后端 → 特殊
简单 复杂
分析便宜 分析昂贵
后面所有 pass 都按这个顺序展开。每个 pass 一段:
缩写 / 英文全称 / 中文
做什么:一句话
为什么有用:对后续优化的影响
典型例子:简化的前后对比
Part 1:本地级(peephole / within basic block)
最便宜的一类——只看几条相邻指令,看到模式就改。
1. Constant Folding(常量折叠)
| |
|---|
| 做什么 | 编译期把已知常量的运算算掉 |
| 为什么有用 | 减少运行时计算 + 暴露更多优化机会 |
| 例子 | add 2, 3 → 5 |
2. Algebraic Simplification(代数化简)
| |
|---|
| 做什么 | 利用代数恒等式化简 |
| 为什么有用 | 把”复杂的写法”压成”简单的写法” |
| 例子 | add x, 0 → x、mul x, 1 → x、xor x, x → 0 |
LLVM 里这部分叫 InstCombine(Instruction Combining,指令组合),一个超大杂烩 pass,几千行模式匹配规则。
3. Strength Reduction(强度降低)
| |
|---|
| 做什么 | 把昂贵操作换成便宜操作 |
| 为什么有用 | 乘法/除法很慢,移位很快 |
| 例子 | mul x, 8 → shl x, 3、div x, 2 → shr x, 1 |
4. CSE(Common Subexpression Elimination,公共子表达式消除)
| |
|---|
| 做什么 | 同一个表达式算了多次,只算一次 |
| 为什么有用 | 省重复计算 |
| 例子 | t1 = a+b; ...; t2 = a+b → t1 = a+b; ...; t2 = t1 |
5. DCE(Dead Code Elimination,死代码消除)
| |
|---|
| 做什么 | 计算结果没人用 → 整条指令删掉 |
| 为什么有用 | 缩小代码体积 + 配合其它优化级联触发 |
| 例子 | t = a + b; (t 后面没人用) → 删掉 |
6. ADCE(Aggressive DCE,激进死代码消除)
| |
|---|
| 做什么 | DCE 的强化版,反向工作——只有”有副作用 / 影响 return”的指令才保留 |
| 为什么有用 | 能消掉只有指令之间互相用、但整体没有”对外”作用的循环 |
Part 2:函数级(intra-procedural)
看整个函数的数据流和控制流,需要 SSA 形式。
7. mem2reg(Memory to Register,内存升寄存器)
8. SCCP(Sparse Conditional Constant Propagation,稀疏条件常量传播)
| |
|---|
| 做什么 | 沿 SSA 边传播常量,同时考虑控制流可达性 |
| 为什么有用 | 比朴素常量传播强——能识别”if (false) 里的分支不可达” |
| 例子 | if (false) { x = 5 } else { x = 10 }; return x → return 10 |
9. GVN(Global Value Numbering,全局值编号)
| |
|---|
| 做什么 | 给每个 SSA value 算一个”值编号”,值相等的合并 |
| 为什么有用 | CSE 的全局加强版——跨 basic block 工作 |
| 例子 | 不同 block 算出来的 a+b 能识别成同一个值 |
10. SROA(Scalar Replacement of Aggregates,聚合分解为标量)
| |
|---|
| 做什么 | 把局部 struct / array 拆成多个独立 scalar 变量 |
| 为什么有用 | 拆完之后 mem2reg 能 promote 它们 |
| 例子 | struct {a, b} x → 两个独立的 x.a、x.b 变量 |
11. Reassociation(重结合)
| |
|---|
| 做什么 | 调整算术表达式顺序,让相关计算靠近 |
| 为什么有用 | 暴露 CSE / 常量折叠机会 |
| 例子 | (a + 5) + (b + 7) → (a + b) + 12 |
12. Sink(代码下沉)
| |
|---|
| 做什么 | 把指令往后挪到真正用它的地方 |
| 为什么有用 | 减少”虽然算了但走不到”的指令 |
| 例子 | 算了个值,然后 if 里才用 → 把算的指令挪进 if |
13. Hoist / LICM 之外的代码外提
类似 Sink 的反向,见 LICM(下面循环类)。
Part 3:循环级(loop optimizations)
循环里的指令重复执行 N 次,值得花更多分析成本。需要先做 LCSSA / 循环识别。
| |
|---|
| 做什么 | 把循环内定义、循环外使用的 SSA value 用 phi 节点封装 |
| 为什么有用 | 后续循环优化前提条件——保证循环边界处的数据流清晰 |
15. LICM(Loop Invariant Code Motion,循环不变代码外提)
| |
|---|
| 做什么 | 把循环里”每次值都一样”的计算挪到循环外 |
| 为什么有用 | 一次计算代替 N 次 |
| 例子 | for (i=0; i<n; i++) x = a*b; arr[i] = x → x = a*b; for (...) arr[i] = x |
16. Loop Unrolling(循环展开)
| |
|---|
| 做什么 | 把循环体复制多份,减少迭代次数 |
| 为什么有用 | 省 branch + 暴露更多 ILP(指令级并行) |
| 例子 | for (i=0; i<4; i++) a[i]=0 → a[0]=0; a[1]=0; a[2]=0; a[3]=0 |
17. Loop Vectorization(循环向量化)
| |
|---|
| 做什么 | 把”对每个元素做一样的事”的循环编成 SIMD 指令 |
| 为什么有用 | 用一条指令处理 4/8/16 个数据 |
| 例子 | for (i) c[i]=a[i]+b[i] → 用 SSE/AVX _mm_add_ps 一次算 4 个 |
18. SLP Vectorization(Superword-Level Parallelism,超字并行向量化)
| |
|---|
| 做什么 | 在直线代码里找可向量化的相邻操作 |
| 为什么有用 | 不需要循环就能向量化 |
| 例子 | x.r=a; x.g=b; x.b=c; x.a=d → 一条 SIMD store |
19. Loop Fusion(循环融合)
| |
|---|
| 做什么 | 两个相邻循环合并成一个 |
| 为什么有用 | 减少循环开销 + 改善缓存局部性 |
| 例子 | for (i) a[i]=0; for (i) b[i]=0 → for (i) { a[i]=0; b[i]=0 } |
20. Loop Distribution(循环分裂)
| |
|---|
| 做什么 | Fusion 的反向——把一个循环拆成两个 |
| 为什么有用 | 拆出来的某半可能能向量化 |
21. Loop Interchange(循环交换)
| |
|---|
| 做什么 | 嵌套循环的内外层调换 |
| 为什么有用 | 改善缓存访问模式(列主序 → 行主序) |
| 例子 | for i for j a[i][j]=... → for j for i a[i][j]=...(取决于布局) |
22. IndVarSimplify(Induction Variable Simplify,归纳变量简化)
| |
|---|
| 做什么 | 把循环计数器规范化(类型统一、初值简化) |
| 为什么有用 | 后续循环 pass 的预处理 |
Part 4:跨函数(interprocedural)
把多个函数放一起看,需要”全程序”视图。
23. Inlining(函数内联)
| |
|---|
| 做什么 | 把被调用函数的函数体复制到调用点 |
| 为什么有用 | 省 call 开销 + 在更大上下文里跑其它优化 |
| 例子 | f() { return 2*x; } g() { y = f(); } → g() { y = 2*x; } |
关键挑战是启发式——什么时候内联划算?太多内联代码爆炸,太少错过优化。LLVM 用 cost-model + inline-threshold。
24. IPSCCP(Interprocedural SCCP,跨函数稀疏常量传播)
| |
|---|
| 做什么 | SCCP 的跨函数版本——参数 / 返回值都参与常量传播 |
| 例子 | 全局只有一处调用 f(5),可以把 f 里的参数当成 5 优化 |
25. Escape Analysis(逃逸分析)
| |
|---|
| 做什么 | 判断一个对象的生命周期是否”逃出”当前函数 / 线程 |
| 为什么有用 | 不逃逸的对象可以栈上分配(省 GC)/ 寄存器分配 |
| 例子 | Java 里 new SmallObj() 没逃出方法 → JIT 栈上分配 |
26. DSE(Dead Store Elimination,死存储消除)
| |
|---|
| 做什么 | 一个 store 写进去的值之后被另一个 store 覆盖(中间没人读)→ 第一个删 |
| 为什么有用 | 省内存写 |
| 例子 | *p = 1; *p = 2 → *p = 2 |
27. Tail Call Optimization(尾调用优化)
| |
|---|
| 做什么 | 函数末尾的 call 用 jump 代替(复用当前栈帧) |
| 为什么有用 | 递归不会栈溢出 + 省 push/pop |
28. LTO / ThinLTO(Link-Time Optimization,链接期优化)
| |
|---|
| 做什么 | 链接时再做一遍跨编译单元的优化(普通编译是 per-file 的) |
| 为什么有用 | 跨文件的 inline / DCE / IPSCCP 都能做 |
| ThinLTO | LTO 的轻量版——并行化更好,工业界主流 |
Part 5:后端 / 代码生成(codegen)
LLVM IR → 目标机器码这一段。
29. Instruction Selection(指令选择)
| |
|---|
| 做什么 | 给每条 LLVM IR 指令选一条目标平台机器指令 |
| 实现 | LLVM 有两套:SelectionDAG(老,DAG-based 模式匹配,用 TableGen)+ GlobalISel(新,逐渐替换) |
| 例子 | LLVM add nsw i32 a, b → x86 add eax, ebx |
30. Register Allocation(寄存器分配)
| |
|---|
| 做什么 | 把无限 SSA value 映射到有限物理寄存器,超的部分 spill 到栈 |
| 三大家族 | Linear Scan(快,代码质量中等)/ Graph Coloring(慢,质量高)/ SSA-based(PBQP) |
| 实现 | LLVM 默认 Greedy(混合算法),-O0 用 fast,-O2/3 用 greedy |
31. Instruction Scheduling(指令调度)
| |
|---|
| 做什么 | 重排指令顺序,避免流水线停顿(填充延迟槽 / hazard) |
| 为什么有用 | 现代 CPU 乱序执行已经做了大部分,但编译期调度还有价值(尤其 in-order GPU 上) |
32. Peephole Optimization(窥孔优化)
| |
|---|
| 做什么 | 后端的”InstCombine”——看几条相邻机器指令,识别模式简化 |
| 例子 | x86 mov eax, 0 → xor eax, eax(更短 + 不影响 flag) |
Part 6:特殊技术
33. PGO(Profile-Guided Optimization,基于剖析的优化)
| |
|---|
| 做什么 | 先跑一次插桩版,收集运行时数据(哪些分支走得多、哪些函数热),再用这些数据指导优化 |
| 为什么有用 | 让 inline / 块布局 / 分支预测都用真实数据 |
34. AutoFDO / CSSPGO
PGO 的分支:AutoFDO 用 Linux perf 数据(不用插桩),CSSPGO 加 call stack 上下文。
35. Constant Propagation(常量传播)
| |
|---|
| 做什么 | 知道某个变量在某点的值是常量 → 把后面所有用替换成那个常量 |
| 跟 SCCP 区别 | 朴素版,不考虑控制流可达性 |
36. Bounds Check Elimination(边界检查消除)
| |
|---|
| 做什么 | 数组访问编译期能证明在界内 → 删掉运行时边界检查 |
| 谁需要 | 安全语言(Rust / Java / Swift) |
Part 7:LLVM Pass Manager 速记
LLVM 把 pass 组织成 PassManager,Old(Legacy)和 New 两套。
# 用新版 PM 跑指定 pass
opt -passes='mem2reg,instcombine,sccp,gvn,dce' input.ll -o output.ll
# -O0 / -O1 / -O2 / -O3 / -Os / -Oz 各自打包了一组 pass
opt -O2 input.ll -o output.ll
# 看 -O2 实际包含哪些 pass
opt -O2 --print-pipeline-passes input.ll
记住这个 --print-pipeline-passes ——做 LLVM 工作时经常用,看 pass 顺序。
38. 一句话总结
30+ 个优化 pass 的名字看起来吓人,但本质上是 6 类工具——本地清扫、函数级 SSA 上的分析、循环上的重塑、跨函数协调、目标机器码生成、剖析驱动的微调。每个 pass 做的事都很局部、很简单,但级联起来就是现代编译器从一行 C / Rust / Swift 到一段紧凑机器码的全过程。读 LLVM 源码或自己写优化 pass 时把这张表当词典查就够,不需要会实现每一个。
系列上一篇: mem2reg 为什么有效:从’看得见所有读写’说起