本页目录
SSA 形式
现代编译器优化的基石:每个变量恰好被赋值一次,数据流分析从迭代不动点退化为稀疏图上的单遍扫描。支配树、支配边界和 φ 函数是让这个约束在所有控制流图上成立的三件工具。
概述
常规 IR(三地址码)里,同一个变量可能被多次赋值——数据流分析时,对某个变量 x 的引用,要回溯找到"是哪次赋值产生的"。这在大型函数里不仅是性能问题,更是正确性问题(多个赋值点通过不同路径到达同一使用点)。
SSA(Static Single Assignment) 的核心约束极其简洁:每个变量在程序正文中恰被定义一次。这看似苛刻,但引入 φ 函数(phi function) 后,任何可规约控制流都能转换成 SSA。一旦进入 SSA,数据流分析的很多问题从"迭代求解"变成"单遍扫描"——因为每个值只有一个定义点,use-def 链是确定的,O(n) 而不是 O(n²)。
为什么 SSA 让分析变简单:一个对比
常规 IR:
x = 1 ← def1
if (cond)
x = 2 ← def2 (覆盖 def1)
y = x + 1 ← 这里的 x 来自 def1 还是 def2? 取决于 cond
要知道 y = x + 1 用了哪次赋值,必须做 reaching definition 分析(迭代数据流,最坏 O(n²))。
SSA 等价形式:
x1 = 1 ← 唯一 def
if (cond)
x2 = 2 ← 唯一 def
x3 = φ(x1, x2) ← 根据控制流选择 x1 或 x2
y = x3 + 1 ← 确定用 x3, x3 的定义点就是 φ——不依赖迭代分析
每一个使用点直接指向唯一定义点——稀疏表示(sparse representation),数据流信息不再需要在整个 CFG 上传播,只需在 def-use 图上一遍扫描。这就是 SSA 成为现代优化基础设施的原因。
构造 SSA 的三个关键概念
支配树(dominator tree)
节点 A 支配(dominate)节点 B,当且仅当从入口到 B 的每一条路径都经过 A。支配关系构成一棵树(根是入口块):
entry支配所有块block1支配block2,block3,block4block2和block3互相不支配(从 entry 到 block2 不一定经过 block3)
支配树从 CFG 计算:用 Cooper 的工程化算法(O(n·|V|)，小规模 CFG 上表现良好)或 Lengauer-Tarjan(O(n log n),大规模 CFG)。dominator 是 SSA 构造的基础——每个变量的定义点在支配树中"覆盖"它后续的可达使用点。
支配边界(dominance frontier)
但变量不会只在"被支配"的点里使用。当控制流汇合时(如 if-else 的结束处),两个不同定义会"碰面"。支配边界精确定义这些汇合点:
DF(X) = {Y | X 支配 Y 的某个前驱, 但 X 不严格支配 Y}
直译:Y 是第一个"不再被 X 支配"的节点——Y 有一个来自 X 支配区域的边,但 Y 本身在 X 的支配区之外。这些 Y 就是需要插 φ 函数的位置。
φ 函数:控制流汇合处的选择器
φ 函数不是真正的指令——它是一个表示法:"我根据实际进入的控制流边,选择对应来源的值"。
x3 = φ(block2→x1, block3→x2)
↑ 如果从 block2 进入 → x3 = x1; 如果从 block3 进入 → x3 = x2
在代码生成阶段,φ 函数被消解为寄存器/内存上的实际 move——共享同一物理位置,或从多个来源寄存器合并(解构 SSA)。
Cytron 算法:高效构造 SSA
Cytron(1991)的算法至今是标准——LLVM 和 GCC 都用它。两步:
Step 1:确定 φ 的插入位置
使用支配边界:
对所有定义过变量 v 的块 D:
对所有 D 的支配边界中的块 F: ← F 是汇合点
在 F 入口插 φ(v)
然后把 F 也当成"定义了 v"的块 (因为 φ 本身也是定义)
递归到 F 的支配边界
实际上对所有变量同时做——一次遍历支配边界,为每个变量记住需要 φ 的块。
Step 2:重命名变量
在支配树上做前序遍历,维护当前每个变量名对应的版本号栈:
rename(block):
for each φ in block:
给 φ 的结果一个新的变量版本 (如 x3)
把 x → x3 压入 x 的版本栈
for each 指令 in block:
对每条指令的每个使用:
查变量版本栈: 用当前栈顶版本替换
对每条指令的定义:
给新版本号 (如 x2)
把该变量 → 新版本号 压入栈
for each block 的后继:
填后继的 φ 参数: 用当前各变量的栈顶版本
for each block 的支配树子节点:
rename(child) ← 递归
弹出当前 block 压入的所有版本号 ← 出作用域
这个重命名过程在支配树上一次 O(N) 遍历完成所有变量的版本编号——比"每个变量的定义点在 CFG 上做 reaching definition"快一个数量级。
解构 SSA:从 φ 回到可执行代码
SSA 的 φ 函数不是真实指令,代码生成前必须解构(destruction):
解构前: 解构后 (copy 方式):
L1: x1 = 1 L1: x = 1
goto L3 goto L3
L2: x2 = 2 L2: x = 2
goto L3 goto L3
L3: x3 = φ(x1, x2) L3: ← x 已经是正确的值了
use(x3) use(x)
思路:如果 φ 的各个来源可以共享同一寄存器,就不需要额外指令——只需在控制流的前驱块末尾把值放进同一个寄存器。关键是一个 φ 的多个来源不能同时活跃(它们来自互斥的路径),所以共享同一物理位置是安全的。
复杂情况:多个 φ 互相引用,或者 φ 和普通指令有依赖循环(如 x = φ(y, z); y = x + 1,在循环里)——这是"lost copy"和"swap"问题,需要插入临时变量打破循环。Cooper 等人(1998)的经典 out-of-SSA 算法。更高效的实现参考后续研究如 Pereira & Palsberg(2004)。
SSA 在 LLVM 中的地位
LLVM IR 是全 SSA 的:每个虚拟寄存器(%1, %2, ...)只被赋值一次。alloca/load/store 绕过了 SSA(通过内存别名),LLVM 的 mem2reg pass 把能提升的 alloca-store-load 提升为 SSA 虚拟寄存器——这是进入优化 pipeline 的第一关。
一旦进入 SSA,LLVM 的大多数 pass(inlining, GVN, LICM, DCE, loop unrolling)全部基于 SSA 做稀疏分析——这是 LLVM 优化速度快且精准的根本原因。
权衡与失败模式
- φ 插入过多:支配边界保守计算可能在某些不可达路径上插多余的 φ → SSA 解构后会被死代码消除处理,不影响正确性,但中间占用更多虚拟寄存器。
- 不可规约控制流(irreducible CFG):goto 或 tail call 导致的 CFG 可能没有支配树意义上的"单入口循环头"——标准算法需要先做 CFG 规约化(node splitting)。
- 解构 SSA 引入额外 copy:φ 解构可能插入大量 copy 指令 → 后续寄存器分配时,coalescing 把能合并的 copy 消掉(SSA 解构 + 寄存器分配是一对搭档,见 寄存器分配)。
参考
- Cytron et al. (1991): "Efficiently Computing Static Single Assignment Form and the Control Dependence Graph" — SSA 构造的原始算法
- Cooper/Torczon: "Engineering a Compiler", Chapters 8–9 (SSA 的完整讲解,含支配树的计算)
- LLVM:
lib/Transforms/Utils/Mem2Reg.cpp,lib/Transforms/Utils/SSAUpdater.cpp— 工业级 SSA 实现
Keywords: SSA, static single assignment, φ-function, phi node, dominator, dominance frontier, Cytron algorithm, renaming, out-of-SSA, SSA destruction, sparse analysis, mem2reg, irreducible CFG, use-def chain, virtual register