SSA 形式

SSA 的核心是每个值名字只有一个静态定义，使用明确关联到该定义。“静态”很重要：循环中的同一条指令可以动态执行很多次，每次产生不同结果，仍然符合 SSA。

SSA 改善数据依赖的表示，不会自动消除所有循环分析，也不要求物理寄存器无限或所有内存只能写一次。

分支里重新赋值，汇合处如何表示

普通程序先令 x=1，再根据条件可能令 x=2，最后使用 x。改成 SSA 后，两次赋值使用不同名字，汇合处增加一个 φ 定义，根据进入的前驱边选择输入。

define i32 @choose(i1 %cond) {
entry:
  br i1 %cond, label %left, label %right
left:
  br label %merge
right:
  br label %merge
merge:
  %x = phi i32 [ 2, %left ], [ 1, %right ]
  %y = add i32 %x, 1
  ret i32 %y
}

φ 不是同时求两个输入再判断条件，而是与实际控制流边关联的值选择。在此例里返回 3 或 2。它可以作为 IR 指令存在，但不要求目标 ISA 有同名机器指令。

支配：一个定义是否对使用必然可见

块 A 支配 B，表示从入口到 B 的每条路径都经过 A。对普通 SSA 使用，定义应支配使用；同块内还要先定义后使用。φ 的输入则按对应前驱边上的使用来检查。

立即支配关系在入口可达块上构成树，每个非入口节点只有一个立即支配者。CFG 中的汇合节点可以有多个前驱，却不会在支配树里有两个父节点。把菱形 CFG 直接标成支配树会混淆这两种结构。

循环中的 φ：把初值与回边值接起来

define i32 @count_to(i32 %n) {
entry:
  br label %header
header:
  %i = phi i32 [ 0, %entry ], [ %next, %body ]
  %more = icmp slt i32 %i, %n
  br i1 %more, label %body, label %exit
body:
  %next = add i32 %i, 1
  br label %header
exit:
  ret i32 %i
}

第一次进入 header 选择 0，后续从 body 回来选择上一轮的 next。定义和使用在文本或依赖图中可能形成循环，这不违反 SSA；因此需要求不动点的分析不会仅因换成 SSA 就全部变成单遍。

n=2 时，同一个静态名字怎样产生多次动态结果

文本里 %i 只有一条 φ 定义，%next 只有一条 add 定义；表格记录的是同一程序的三次动态到达，并没有引入三个冲突的静态定义。若 n=0 或负数，第一次比较就退出并返回 0，没有任何 body → header 回边执行。

把 choose 和 count_to 的两段 IR 放进同一文件 ssa.ll，可先运行 opt -passes=verify -disable-output ssa.ll。再配合下面的 C 驱动观察两条分支和零次/多次循环：

/* ssa-main.c：clang ssa.ll ssa-main.c -o ssa-demo */
extern int choose(_Bool);
extern int count_to(int);
int main(void) {
    return choose(1) != 3 || choose(0) != 2 ||
           count_to(-1) != 0 || count_to(0) != 0 || count_to(2) != 2;
}

如果保留 CFG 的 body → header 回边，却从 %i 的 φ 中删掉 [ %next, %body ]，verifier 应拒绝：φ 输入必须与前驱结构对应。若把 %next 当普通值直接用于 entry，则它的定义不支配该使用，同样应拒绝。验证器证明的是 IR 结构满足规则，不是前端已经正确表达了源程序意图。LLVM φ 规则

同一条 φ，怎样接住初值和每次回边？

将“是哪条静态指令”与“是第几次动态到达”分成两个坐标，就不会把循环误判为违反 SSA。下面始终只有一条 %i 定义；观察位置选择的是某次 header 到达，进入边决定 φ 取初值还是上一轮的结果。到 i=n 的那次只执行比较和退出，没有再计算一个并不存在的 next。

支配边界：定义的影响在哪些汇合处需要选择

DF(X) = {Y | X 支配 Y 的某个前驱，但 X 不严格支配 Y}。

“不严格支配”允许某些循环中 Y=X 的情况，所以不能把支配边界总解释为完全在 X 支配区域之外的第一个节点。

经典构造从变量的定义块开始，在迭代支配边界上插入 φ，新 φ 块也作为定义继续传播。Pruned SSA 再利用变量入口活跃性避免插入没有用途的 φ。这不是给所有变量在每个汇合点都插一次。

重命名：沿支配树维护当前版本

维护每个源变量的版本栈，进入块时为 φ 结果创建版本；扫描普通指令时先把使用替换为当前版本，再为新定义创建版本；离开该块去处理后继边时填入对应 φ 输入；递归支配树子节点后撤销本块压入的版本。

未初始化使用需要由源语言语义或前端错误处理决定，不能为了让 SSA 通过就随意填 0。不可达块也需要清理或按算法约定独立处理。

一般 CFG，包括不可规约控制流，也可以构建 SSA；不要求先把所有循环变成单入口自然循环。某些后续循环优化可能需要规约形态，那是另一个问题。

支配边界，是哪一条进入路径打破了“必经”？

“不严格支配”不能简写为“完全不支配”。下面给 M 加一条自回边：M 支配这条边的前驱 M，但不会严格支配自身，因此 M∈DF(M)。在普通菱形里选择 L 或 R，则可以看到另一条路径如何让 M 不再受该分支支配。图中颜色来自实际支配集合计算，CFG 的形状本身不是支配树。

$$\mathrm{DF}(X)=\{Y\mid \exists P\in \mathrm{pred}(Y):X\mathrm{dom}P\wedge \neg (X\mathrm{sdom}Y)\}$$

解构：φ 产生的是边上的并行复制

某条前驱边上有多个 φ 输入时，可把它们理解为同时赋值到结果位置。例如位置分配后需要 a←b 与 b←a，顺序执行会丢掉一个旧值，必须用临时位置或合适交换序列。

关键边的前驱有多个后继、后继有多个前驱，复制既不能无条件放在前驱末尾，也不能无条件放在后继开头；常通过拆边建立只属于该路径的执行位置。

φ 输入来自不同前驱，并不证明它们在整个程序中绝不同时活跃。来源值可能还在别处使用，因此共用物理位置必须经过干涉与 copy 合并检查，不能无条件把一个 φ 的所有值合成一个寄存器。

一组交换复制必须读到同一份旧状态

位置 a、b 的旧值分别为 10、20，目标并行复制是 a←b、b←a。第一条顺序复制后 a 已变成 20，第二条若再读 a 就会得到新值，最终两者都为 20。临时位置的作用是保留被提前覆盖的旧值。

old = {"a": 10, "b": 20}
expected = {"a": old["b"], "b": old["a"]}
wrong = old.copy()
wrong["a"] = wrong["b"]
wrong["b"] = wrong["a"]
assert wrong == {"a": 20, "b": 20} and wrong != expected

actual = old.copy()
temporary = actual["a"]
actual["a"] = actual["b"]
actual["b"] = temporary
assert actual == expected

这个问题发生在把 SSA 值映射到可复用的物理位置以后，不是在说 SSA 本身允许给同一个名字重新赋值。一般并行复制可能有无环链与多个环：先安排不会破坏其他旧输入的复制，遇环再引入临时位置；只有交换两项时才可以直接使用这里的三步模板。

复制不能简单搬到 P 的末尾，否则 P→X 也会执行它；也不能放到 M 的入口，否则 Q→M 也会执行来自 P 的复制。拆边后还必须将 M 的 φ 前驱标识从 P 更新为新块，而不是只改跳转目标。

旧值被覆盖以后，另一条复制还能读到它吗？

这里被覆盖的是复用的物理位置，不是重新定义 SSA 名字。目标右侧需要读同一份旧状态；选择复制动作后，画面保留每个位置的当前值和最近写入记录。先直接复制两次，再重置尝试临时位置方案，可以找到丢值发生的准确时刻。临时位置也不是魔法：若保存动作太晚，保存到的仍然是已经被覆盖的新值。

SSA 值与可变内存并存

LLVM 的 %p = alloca i32 只定义一次指针值，之后可以多次 store 到其指向的内存；每个 load 又产生新的 SSA 值。SSA 约束的是命名值，不是把整个堆变成不可变数据。

mem2reg 将适合提升的局部槽位转为 SSA 值与 φ；别名、地址逃逸和不支持的访问会影响提升。前端可以先用 alloca 表达可变局部变量，再交给提升过程，避免自己立即实现完整 SSA 构造。LLVM 可变变量教程

验证速查

检查唯一定义、类型、支配关系、φ 与前驱边对应、终结指令和不可达块处理。修改 CFG 时也要更新 φ 输入；删除一条边却保留对应输入会破坏 IR。

相关章节：LLVM IR 实战、数据流分析、寄存器分配。

参考

• LLVM Language Reference。
• LLVM：Mutable Variables。

Keywords: SSA, phi, dominator, dominance frontier, renaming, parallel copy, critical edge, mem2reg