1. SSA 为什么成为优化器的通用语言
一句话总结： SSA 要求每个变量只被赋值一次，且定义点支配所有使用点，于是「这个值从哪来」不再需要跨块搜索，优化从全局图问题退化成稀疏的局部推理。
在传统三地址码里，同一个名字会被反复赋值。想回答「x 在这条语句处是多少」，必须沿着控制流反向搜索所有可能的定值点，这就是数据流分析要反复迭代的原因。SSA（Static Single Assignment）换了个思路：给每次赋值一个新版本号，让每个版本名只有唯一定义，把「多定义」问题在表示层面消掉。
传统三地址码: SSA 形式:
x = 1 x.1 = 1
if (c) goto L if (c) goto L
x = 2 x.2 = 2
L: goto M
y = x + 1 L:
x.3 = 2
M:
x.4 = φ(x.2, x.3)
y.1 = x.4 + 1
代价是引入了 φ 函数——一个只在基本块入口、语义为「按控制流来路选择参数」的伪指令。SSA 因此是一套两趟工程：构造时插入 φ 并重命名变量，离开 SSA 时把 φ 还原成普通复制。绝大多数中端优化都跑在 SSA 上，所以这两趟的正确性与效率直接决定整个优化管线的质量。
| 表示 | use 查 def | 优化形式 | 主要代价 |
|---|---|---|---|
| 传统三地址码 | 跨块数据流迭代 | 全局、稠密 | 每次变换后分析失效重算 |
| SSA | 直接指向唯一定义 | 稀疏、近似局部 | 构造/销毁两趟，φ 带来伪指令 |
# 数据流分析里「稀疏」的含义：use 直接持有 def 的指针
class Use:
def __init__(self, user_stmt):
self.user_stmt = user_stmt
self.def_stmt = None # 唯一可达定义，SSA 下直接绑定
class Def:
def __init__(self, name, stmt):
self.name = name
self.stmt = stmt
self.uses = [] # 反向链：所有用到它的地方
有了这条双向 def-use 链，常量传播、全局值编号、死代码消除都不再需要迭代求解数据流方程，只需沿链走一遍。
2. 支配关系与支配树
一句话总结： 块 A 支配块 B，当且仅当从入口到 B 的每条路径都经过 A；把每个块连到它的直接支配者上，就得到支配树。
支配是 φ 插入的地基。设入口块为 entry，a dom b 表示所有从 entry 到 b 的路径都经过 a。每个块 b ≠ entry 有唯一的直接支配者 idom(b)：它是 b 的所有严格支配者中「最靠近 b」的那个。把所有 b → idom(b) 的边画出来，就得到一棵以 entry 为根的支配树。
支配树有两个立刻可用的性质：其一，a dom b 等价于 a 是支配树上 b 的祖先；其二，判断「定义是否支配使用」只需在树上做祖先查询，配合 DFS 序可以在 O(1) 内回答。
经典的 Cooper-Harvey-Kennedy 算法用「逆后序 + 交点」迭代求解 idom，实现短、收敛快，几乎所有教学编译器都采用它：
def compute_dominators(preds, succs, entry, nodes):
"""Cooper-Harvey-Kennedy: 逆后序迭代求 idom"""
# 1. 先做一次 DFS 得到后序，再反转成逆后序 (rpo)
order, visited = [], set()
def dfs(n):
visited.add(n)
for s in succs[n]:
if s not in visited:
dfs(s)
order.append(n)
dfs(entry)
rpo = list(reversed(order))
index = {n: i for i, n in enumerate(rpo)}
idom = {n: None for n in nodes}
idom[entry] = entry
def intersect(a, b):
# 沿支配链上溯，直到相遇；index 越小越靠近入口
while a != b:
while index[a] > index[b]:
a = idom[a]
while index[b] > index[a]:
b = idom[b]
return a
changed = True
while changed:
changed = False
for b in rpo:
if b == entry:
continue
new_idom = None
for p in preds[b]:
if idom[p] is None: # 前驱尚未处理完
continue
new_idom = p if new_idom is None else intersect(new_idom, p)
if new_idom is not None and idom[b] != new_idom:
idom[b] = new_idom
changed = True
return idom
算法之所以正确，是因为逆后序保证「处理 b 时，b 的所有前驱要么已处理，要么还不可达」；而 intersect 用两个指针沿支配链交替上溯，天然实现「最近公共祖先」。实践中这个循环平均只跑两三轮就收敛。
3. 支配边界与 φ 函数插入
一句话总结： 块
b的支配边界DF(b)是「被b支配、但b并非其严格支配者」的块集合；只要某变量在b有定义，就需要在DF(b)的每个块里插 φ。
φ 应该插在哪里？直觉是：一个变量在 b 里被赋值，而某个块 X 有两条来路、其中一条经过 b、另一条不经过，那么 X 处这个变量可能有两个来源，需要 φ 汇合。这个 X 恰好就是支配边界的定义。
def dominance_frontier(preds, idom, entry, nodes):
"""按 Cytron 的局部性算法计算 DF"""
df = {n: set() for n in nodes}
for b in nodes:
if len(preds[b]) >= 2: # 只有多前驱块能成为边界
for p in preds[b]:
runner = p
while runner is not None and runner != idom[b]:
df[runner].add(b)
runner = idom[runner] if runner != entry else None
return df
有了 DF，最小 SSA 的 φ 插入就是标准的 worklist 迭代：变量 v 在 S 集合里有定义，就把 DF(S) 中的块加入待插列表；新插入的 φ 本身也是一次定义，于是把该块继续加入 worklist 传播，用 has 集合防重。
def insert_phis(defsites, df, nodes):
"""Cytron 最小 SSA: 为每个变量求 φ 插入点"""
phi = {n: {} for n in nodes} # phi[块][变量] = 新名字
for var, sites in defsites.items():
work = list(sites)
inserted = set(sites)
while work:
b = work.pop()
for d in df[b]:
if var not in phi[d]:
phi[d][var] = None # 占位，重命名时填
if d not in inserted:
inserted.add(d)
work.append(d) # φ 是新定义，继续传播
return phi
| 变量 | 定义点 | DF 传播后插入 φ 的块 |
|---|---|---|
x | b1 | b4（b1 的两条分支在 b4 汇合） |
y | b3 | b4 |
z | b2 | b5、b7 |
这个算法插入的 φ 数量是理论最小的（在「每个 φ 只对应一个变量」的约束下），但它只考虑可达性，不考虑活跃性：如果插入的 φ 结果从未被使用，它仍然是多余的。这就是最小 SSA 与剪枝 SSA 的差别。
4. 变量重命名与版本管理
一句话总结： 沿支配树做一次 DFS，维护「每个变量当前版本」的栈；遇定义压栈，遇使用取栈顶，离开块时弹栈。
φ 插入只是标注了「哪里需要汇合」，真正把程序改写成 SSA 的是重命名。它利用支配树的层次结构：在支配树上做深度优先遍历，维护每个变量一个「当前名字栈」。进入一个定义点就压入新版本，用到变量就取栈顶，回溯时弹出——这恰好保证「离开块后，栈状态回到进入时的样子」，与支配树的兄弟子树互不干扰。
from collections import defaultdict
def rename(entry, dom_children, blocks, phi, succs):
stack = defaultdict(list) # var -> [当前版本名, ...]
counter = defaultdict(int)
def fresh(var):
counter[var] += 1
return f"{var}.{counter[var]}"
def visit(b):
pushed = []
# (1) 本块的 φ 定义新版本，先压栈
for var in phi[b]:
name = fresh(var)
phi[b][var] = name
stack[var].append(name)
pushed.append(var)
# (2) 块内语句：先处理 use 再处理 def
for stmt in blocks[b]:
for u in stmt.uses:
stmt.rename_use(u, stack[u][-1])
for d in stmt.defs:
name = fresh(d)
stmt.rename_def(d, name)
stack[d].append(name)
pushed.append(d)
# (3) 填后继块的 φ 操作数：取当前栈顶
for s in succs[b]:
for var in phi[s]:
phi[s][var] = stack[var][-1]
# (4) 递归支配树的孩子
for c in dom_children[b]:
visit(c)
# (5) 回溯：弹出本块压入的版本
for var in pushed:
stack[var].pop()
visit(entry)
有几处容易出错。第一，块内语句必须先处理 use 再处理 def，否则 x = x + 1 会把自己的旧值错误替换成新版本。第二，φ 的操作数要在访问后继块之前填，且填的是当前块末尾的栈顶版本，因为 φ 的语义是「从这条边进来时该变量的值」。第三，未初始化变量需要一个显式的「未定义」版本，不能直接取空栈。
经过重命名，每个 use 都指向唯一 def，def-use 链自然建立，后续的稀疏优化可以直接在这张链上跑。
5. 从最小 SSA 到剪枝 SSA
一句话总结： 最小 SSA 只保证「必要」，剪枝 SSA 进一步保证「不插入结果从未被使用的 φ」，Braun 算法则干脆绕开支配边界计算。
最小 SSA 会插入一些「死 φ」：比如一个变量只在某个分支里被定义、在汇合点后从未被使用，但支配边界算法仍会在汇合点插 φ。剪枝 SSA 在插入 φ 前先做活跃性判断——只有 φ 的结果活跃才真正插入，否则跳过。这一步通常把 φ 数量减少 20% 到 40%，对后续 pass 的编译时间有直接影响。
更激进的是 Braun 等人 2013 年提出的「简单而高效」的 SSA 构造算法。它完全不计算支配边界，而是：
- 为每个块维护一个「当前定义」的哈希表（局部值编号）；
- 沿支配树 DFS，块内遇到定义就写入哈希表；
- 在块入口用哈希表把可用的定义「装填」进来，缺失的变量在块首生成 φ，并递归到支配孩子，用返回值回填 φ 的操作数。
def seal_block(b, incomplete_phis, current_def, preds, write_var):
"""Braun 算法: 当块的所有前驱都处理完后，尝试消除不完整的 φ"""
for var, phi_inst in list(incomplete_phis.get(b, {}).items()):
if len(preds[b]) == 1:
val = current_def[preds[b][0]].get(var) # 单前驱可直接替代
if val is not None:
phi_inst.replace_all_uses_with(val)
phi_inst.erase()
del incomplete_phis[b][var]
continue
write_var(b, var, phi_inst) # 否则保留 φ
incomplete_phis[b][var] = phi_inst
| 算法 | 是否算支配边界 | φ 数量 | 适用场景 |
|---|---|---|---|
| Cytron 最小 SSA | 是 | 最小（含死 φ） | 教学、结构清晰 |
| 剪枝 SSA | 是 + 活跃性 | 更少 | LLVM 早期、多数生产编译器 |
| Braun 简单算法 | 否 | 近似最小 | 前端、需要低常数的场景 |
| SSA 构造（基于值编号） | 否 | 局部最优 | JIT、按需构造 |
工程上常把「Braun 构造 + 稀疏条件常量传播」组合起来：构造时就做常量折叠，能在插 φ 前把大量分支消掉。
6. SSA 上的优化红利
一句话总结： SSA 把「多定义」变成「单定义」，于是常量传播、值编号、死代码消除都变成沿 def-use 链的一次扫描，无需迭代数据流。
拿到 SSA 后，几个重量级优化立刻变简单：
- 稀疏条件常量传播（SCCP）：在 SSA 图上做格求值，把「可达性」与「常量性」一起传播。由于每个变量单定义，一个值要么是常量、要么是「过定义」（如 φ 参数不一致），判定是局部的。
- 全局值编号（GVN）：为每个表达式算一个值编号，编号相同即等价，可做公共子表达式消除。SSA 下不必再解可用表达式数据流，直接比较编号。
- 死代码消除（DCE）：从「有副作用」的语句（store、call、return）反向沿 def-use 链标记，未标记到的定义即死。φ 的处理稍特殊——只要 φ 的任一个结果被用到，它对应的所有操作数就都算「活」。
- 寄存器分配：SSA 的每个名字是独立活值，冲突图更稀疏，图着色更快；这也是「SSA 上做寄存器分配」比传统 IR 效果好的原因。
def sccp_eval(lattice, op, args):
"""SCCP 的格求值: 未定义 / 常量 / 过定义"""
if any(a is UNDEF for a in args):
return UNDEF
if any(a is OVERDEFINED for a in args):
return OVERDEFINED
if op == "phi":
first = args[0]
return first if all(a == first for a in args) else OVERDEFINED
return CONST(eval_binop(op, [a.value for a in args]))
需要注意，SSA 形式下 φ 的「并行语义」在优化时容易被忽略：把 x = φ(a, b) 的一个参数换成常量，不等于整个 φ 变成常量，只有当所有可达参数都等于同一常量时才是常量。这正是 sccp_eval 里 all(a == first) 的由来。
7. out-of-SSA：把 φ 还原成复制
一句话总结： φ 的语义是并行赋值，直接顺序展开会踩到「丢拷贝」（源被提前覆盖）与「交换」（两变量成环），必须按依赖顺序发射并借临时变量拆环。
优化跑完后必须离开 SSA，因为真实机器没有 φ。做法是把每个 φ 在每个前驱块末尾展开成一组复制：x = φ(y, z) 在前驱 1 末尾生成 x = y，在前驱 2 末尾生成 x = z。这些复制之间是并行语义——它们必须「同时」发生，而机器只能顺序执行。
天真地逐条发射会踩两个经典坑：
# 坑 1：丢拷贝 (lost copy)
并行语义: x1 ← x2 , x2 ← x3
错误顺序: x2 = x3 # 先把 x2 覆盖
x1 = x2 # 这里拿到的是新 x2，旧 x2 丢了
正确顺序: x1 = x2 # 先读旧 x2
x2 = x3
# 坑 2：交换 (swap)
并行语义: x1 ← x2 , x2 ← x1
无论先做哪条都会破坏另一条的源，必须借道临时变量：
tmp = x1
x1 = x2
x2 = tmp
正确的顺序化算法：反复找一条「目标不是任何剩余复制的源」的复制，它可安全先发；若一条都找不到，说明存在环，就借一个临时变量打断环。
def sequentialize(copies, fresh_temp):
"""把并行复制列表顺序化，必要时插入交换临时变量"""
seq = []
copies = list(copies)
while copies:
sources = {s for _, s in copies}
ready = [(d, s) for (d, s) in copies if d not in sources]
if ready:
for c in ready: # 可安全发射
seq.append(c)
copies.remove(c)
else:
# 全部成环，例如 (a←b, b←a)：借临时变量打破
d0, s0 = copies[0]
tmp = fresh_temp()
seq.append((tmp, s0)) # tmp = s0
# 把「以 s0 为源」的复制改为以 tmp 为源
copies = [(d, tmp if s == s0 else s) for d, s in copies]
return seq
工程上还有两个配套技巧。其一是复制合并：如果 x = φ(...) 之后紧接着 y = x，可以直接把 φ 的结果名字改成 y，省掉一条复制——这就是 SSA 解构里的「copy coalescing」，它同时减少了寄存器分配的冲突图规模。其二是关键边拆分：φ 的复制要插在前驱块末尾，但若前驱有多条出边（关键边），直接插入会污染另一条路径，必须先在边上拆出一个空块再插复制。
def deconstruct_ssa(phi_map, edges, succs, fresh_temp, fresh_block):
"""phi_map[块][变量] = {前驱块: 源名}"""
pending = defaultdict(list) # 每个前驱块末尾要发射的复制
for b, phis in phi_map.items():
for var, operands in phis.items():
for pred, src in operands.items():
if pred != var: # 自复制可省略
pending[pred].append((var, src))
for pred, copies in pending.items():
outs = succs[pred]
if len(outs) > 1:
# 关键边：先拆出一个空块，避免污染另一条路径
edge_block = fresh_block()
redirect_edge(pred, edge_block, succs)
target = edge_block
else:
target = pred
for d, s in sequentialize(copies, fresh_temp):
emit_at_end(target, ("MOV", d, s))
return
其中 sequentialize 就是上一节给出的顺序化函数：先发射所有「目标不再作为源」的复制，成环时借临时变量拆开。经过这一步，φ 被彻底消掉，程序回到普通三地址码，可以交给寄存器分配与指令选择。
8. 总结
| 环节 | 核心要点 |
|---|---|
| SSA 定义 | 每变量单定义，定义支配所有使用 |
| 支配树 | idom 迭代求解，DFS 序支持 O(1) 祖先查询 |
| 支配边界 | 「被支配但非严格支配」的块，是 φ 的插入点 |
| φ 插入 | Cytron worklist 传播，插入点理论最小 |
| 变量重命名 | 支配树 DFS + 版本栈，先 use 后 def |
| 剪枝 SSA | 用活跃性过滤死 φ，减少 20%~40% φ |
| Braun 算法 | 不算支配边界，靠哈希表 + 递归回填 |
| SSA 优化红利 | SCCP / GVN / DCE 退化为沿 def-use 链扫描 |
| out-of-SSA | φ 是并行复制，须顺序化并拆环 |
| 丢拷贝与交换 | 目标不得是剩余复制的源；成环需临时变量 |
| 复制合并 | 相邻复制合并，缩小冲突图 |
SSA 是把「程序分析」从稠密迭代变成稀疏推理的关键一步：它牺牲了一点表示复杂度（φ 函数），换来的是整条中端优化管线的大幅简化。构造与销毁这两趟本身也充满取舍——最小 SSA 追求 φ 数量最少，剪枝 SSA 追求实际收益最大，Braun 算法追求常数最小，而 out-of-SSA 则要在正确性与复制数量之间找平衡。理解了支配树、支配边界与并行复制这三块基石，再去看 LLVM 的 SROA、GVN、RegAllocGreedy，就能明白它们为什么长成现在这样。
延伸阅读
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。