静态单赋值形式

普通程序反复给变量 $x$ 赋值，读者必须沿路径判断某次读取看到哪一个版本。SSA 把这项路径推理预先编码进名字：$x_0,x_1,x_2$ 各有唯一来源，合流处再明确选择来自哪条边。于是“哪次定义到达这次使用”从集合问题变成直接的定义—使用边，许多稀疏优化只需沿这些边传播。

SSA 没有消除控制流。名字唯一并不意味着值唯一：不同执行可以使同一个定义产生不同运行时值，例如循环中的 $x_2:=x_1+1$ 每轮都会得到新数。SSA 的静态图把可能反复执行的一条指令保留为一个节点，运行轨迹仍由 CFG 决定。

考虑菱形程序：入口给 $x:=0$，条件为真时执行 $x:=x+1$，为假时执行 $x:=x+2$，汇合后返回 $x$。版本化后可写成

沿真边手算得到 $x_3=x_1=1$，沿假边得到 $x_3=x_2=2$。若删掉合流定义而让返回任意使用 $x_1$，假路径上其定义不支配使用，程序便不是合法 SSA；这是一项可由图结构检查的不变量，而非变量名看起来带下标即可。

循环展示“静态”一词的边界。初始化 $i_0:=0$，循环头定义 $i_1:=\varphi (i_0,i_2)$，循环体定义 $i_2:=i_1+1$ 并回跳。$i_1$ 在每次进入循环头时执行，却只出现一个定义点；第一次选入口边的 $i_0$，以后选回边的 $i_2$。若把 φ 当作同时读取两个运行时值的普通函数，第一次迭代会错误地要求尚未执行的 $i_2$。

在同一张图上构造与消解 ​

下面固定纯标量、精确自然数运算；没有内存、异常或外部事件。输入是 $n\in \mathbb{N}$ 与布尔量 $s$，观察是返回的三元组。$t$ 是块内临时量，三个跨块变量为 $a,b,k$。原程序为

E: a := 1; b := 2; k := 0; goto H
H: if k < n then goto B else goto X
B: t := a; a := b; b := t; k := k + 1
   if s then goto X else goto H
X: return (a,b,k)

$B$ 每次交换两个数并增加计数；$s$ 为真时一次循环体后提前退出。所有节点可达，边集为 $E\to H,H\to B,H\to X,B\to H,B\to X$。支配集与支配边界理路支配边界Dominance frontier · DF · 支配前沿收集某节点的支配影响首次可能在控制流汇合处停止的节点，为 SSA 合流定义定位。逐项代入定义得到：

例如 $H$ 支配回边尾 $B$，却不严格支配自身，所以 $H\in \mathrm{DF}(H)$；$H$ 严格支配 $X$，故 $X\notin \mathrm{DF}(H)$。$B$ 支配通往 $X$ 的前驱 $B$，但路径 $E,H,X$ 绕过 $B$，所以 $X\in \mathrm{DF}(B)$。支配树是 $E$ 的孩子 $H$，$H$ 的孩子 $B,X$。

放置 φ 与栈式改名 ​

按φ 节点放置算法理路φ 节点放置算法Phi-node placement · Iterated dominance-frontier placement · φ 放置从各变量定义块的迭代支配边界计算 SSA 合流定义，并以活跃性区分 minimal、semi-pruned 与 pruned 形式。，对变量 $v$，把原定义块放入工作表。每取出 $D$，遍历 $\mathrm{DF}(D)$，在尚无 $v$ 的 φ 的块放一个，并把新定义块加入工作表；重复直到没有新位置。这是迭代边界而非单轮扫描。若采用 pruned SSA，只在 $v$ 于该块入口活跃时放置。入口活跃表示存在从该块入口到一次读取的路径，沿路尚未重新定义 $v$，可由反向活跃性方程求得。[3]

本例 $a,b,k$ 的定义块均为 $\{E,B\}$，它们的迭代边界均为 $\{H,X\}$，而两处都入口活跃。$t$ 只在 $B$ 内先定义后使用，不在 $H,X$ 入口活跃，故不放 $t$ 的 φ。以下明确使用这个 pruned 版本，不把未初始化的 $t$ 填进循环头。

采用SSA 构造的栈式改名理路SSA 构造算法SSA construction algorithm · Dominance-based SSA construction · SSA 重命名先以迭代支配边界插入 φ，再沿支配树用每变量版本栈重命名定义、使用和前驱边参数。，按支配树深度优先遍历，并给每个原变量维护名字栈。规则是：

1. 进入块时，先为各 φ 的结果生成新名字并压栈，暂不读取其参数。
2. 顺序处理普通指令：右侧和分支读取当前栈顶；左侧生成新名字后压栈。因此 k:=k+1 先读旧版本再产生新版本。
3. 对每条出边，为后继 φ 的这一条边填入当前栈顶。
4. 递归处理支配树孩子，返回时弹出本块压入的名字，恢复父层环境。

这与经典栈式算法的参数填充时机一致。[1] 依次访问 $E,H,B,X$ 时，$a,b,k$ 三栈的顶部变化为

在 $E$ 就填好 $H$ 的入口槽；访问 $H$ 时填 $X$ 的 $H$ 槽；访问 $B$ 时填 $H$ 的回边槽和 $X$ 的 $B$ 槽。$X$ 本身在 $B$ 之后才访问，也不影响已记录的参数。最终为

E: a0 := 1; b0 := 2; k0 := 0; goto H
H: a1 := phi(E:a0, B:a2)
   b1 := phi(E:b0, B:b2)
   k1 := phi(E:k0, B:k2)
   if k1 < n then goto B else goto X
B: t1 := a1; a2 := b1; b2 := t1; k2 := k1 + 1
   if s then goto X else goto H
X: a3 := phi(H:a1, B:a2)
   b3 := phi(H:b1, B:b2)
   k3 := phi(H:k1, B:k2)
   return (a3,b3,k3)

输入 $n,s$ 视作入口定义。普通使用的定义均支配使用；$a_2$ 不支配 $H$，但它支配作为其 φ 使用位置的边尾 $B$。首次从 $E$ 进入 $H$ 时不读取 $a_2$，没有未定义读取。

逐条边证明改名保持原值 ​

令原环境为 $\sigma$，SSA 的当前运行环境为 $\rho$。在 $H$ 的 φ 执行之后关联

在 $B$ 的普通指令执行之后，右侧改为 $(a_2,b_2,k_2)$；在 $X$ 的 φ 执行之后，右侧改为 $(a_3,b_3,k_3)$。这不是要求所有历史版本都等于当前原变量，而是按控制点选当前版本。

• $E\to H$：两边初始化相同，$H$ 同时取三个 0 版本，关系成立。
• $H\to B$：比较读取相同 $k,n$，所以选择同一条边。若进入 $B$，顺序赋值都把 $(a,b,k)$ 变成 $(b,a,k+1)$；$t_1$ 保存旧 $a_1$，得到块末关系。
• $H\to X$：$X$ 取 $(a_1,b_1,k_1)$，恰为原环境。
• $B\to H$：两边依据同一输入 $s$ 选边；$H$ 取块末的 $(a_2,b_2,k_2)$，恢复头部关系。
• $B\to X$：$X$ 同样取块末三个版本，返回三元组相同。

这五种情况覆盖所有边。沿任意有限执行前缀归纳，就覆盖任意次数回边；随后相同返回指令给出相同观察。本例还必定终止：$n=0$ 时直接返回；否则 $s$ 为真时执行一次 $B$，为假时每轮 $k$ 增一，恰在 $k=n$ 退出。一般循环的语义保持则不能把“某条静态定义只出现一次”误当作终止证明。经典构造证明同样以执行路径上的当前值关系为核心。[1]

同一程序中的关键边与复制环 ​

先显式进行复制传播 ​

上面的原始 SSA 中，$a_2=b_1,b_2=t_1=a_1$。将 $t_1,a_2,b_2$ 的使用替换为各自来源后，删除这三条复制，得到

H: a1 := phi(E:a0, B:b1)
   b1 := phi(E:b0, B:a1)
   k1 := phi(E:k0, B:k2)
   if k1 < n then goto B else goto X
B: k2 := k1 + 1
   if s then goto X else goto H
X: a3 := phi(H:a1, B:b1)
   b3 := phi(H:b1, B:a1)
   k3 := phi(H:k1, B:k2)
   return (a3,b3,k3)

$E$ 不变。替换的每次读取都位于相应来源可用的位置；尤其 $H$ 的两个结果定义都支配边尾 $B$。回边槽读取的是离开 $B$ 时的旧 $a_1,b_1$，再同时写下一轮的两个结果，因此这一含相互引用的循环 φ 仍合法。复制环由明确的复制传播产生，没有暗中合并可能互相干涉的寄存器。

复制只应发生在被选中的边上 ​

进行SSA 消解理路SSA 消解SSA destruction · Out-of-SSA translation · SSA deconstruction把 φ 的按边并行赋值降为普通复制，通过拆分关键边、打破复制环和安全合并名字保持语义。时，对每条入边收集后继块的 φ 所要求的并行复制。优化后五条边对应

关键边的源块有多个后继，目标块有多个前驱；这里是 $H\to X,B\to H,B\to X$。为每条这样的边插入独立块 $C_{HX},C_{BH},C_{BX}$，例如把 $B\to H$ 改成 $B\to C_{BH}\to H$，复制放在 $C_{BH}$。进入新块的分支标签与原边一致，后继的参数槽也随边更新。$E$ 只有一个后继，所以 $E\to H$ 的复制可直接放在 $E$ 末尾。这一边拆分与并行复制约定见文献。[3]

为什么不能把回边复制提前塞到 $B$ 的分支前？取 $n=2,s=\mathsf{true}$。第一次到 $B$ 时 $a_1=1,b_1=2$，正确 $B\to X$ 应返回 $(2,1,1)$。若先执行原本属于 $B\to H$ 的交换，把 $a_1,b_1$ 改成 $(2,1)$，再走 $B\to X$，其复制读取 $(b_1,a_1)$，错误返回 $(1,2,1)$。若放在 $H$ 入口不按边选择，又会错误处理首次进入。这是同一程序中的实质差异，不只是“这条边叫关键边”的命名规定。

保存一个旧值，消除回边复制环 ​

$C_{BH}$ 的交换不能顺写成 a1:=b1; b1:=a1，否则旧 $(1,2)$ 会变成 $(2,2)$。取不在程序中出现的新临时量 $u$，正确序列为

u := a1
a1 := b1
b1 := u
k1 := k2

四条指令依次执行。若旧值为 $(A,B,K_2)$，执行后就是 $(B,A,K_2)$；$u$ 不进入观察。其余三组非空复制的目标与所有源互异，按任何顺序写均不会毁掉待用源值。

一般并行复制也有直接算法：先删去 d:=d；若某目标 $d$ 不再被任何剩余复制作为源读取，则可先执行 d:=s 并删去它。若无这种目标，剩余有限依赖图中有环；选一个目标 $d$，用新临时量保存它的旧值，并把所有剩余右侧的 $d$ 改为该临时量。此后 $d$ 不再被读取，可以消去至少一条复制。不同目标只写一次，每次断环后都有删除，故算法终止。

这两种动作都保持不变量：“已输出的顺序指令执行后，再同时执行剩余复制，与原并行复制在所有非临时位置上的最终值相同。”安全删除不会覆盖剩余源；断环只把旧源换成其保存值。归纳直到剩余为空，就得到顺序化的正确性。这里不声称最少临时量；空间更紧的算法及其机械化证明见文献。[2]

把边拆分和复制顺序化合在一起，每次原边转移都由一段有限、无分支的新路径匹配；路径末的非临时状态等于原 φ 的同时更新。因此逐边关系继续成立。新增块不会自行循环，返回值不变；对一般可能发散的程序，这种每边有界有限展开也不会把有限执行变成发散或吞掉无限执行。

内存与效果边界 ​

内存反例也很具体：令 $p$ 与 $q$ 可能别名，先做 $\mathrm{store}(p,1)$，再做 $\mathrm{store}(q,2)$，最后 $\mathrm{load}(p)$。即使 $p,q$ 各只定义一次，结果仍可能是 $2$。标量 SSA 不会凭空证明两次存储独立。

唯一定义使常量传播、复制传播、死代码删除和值编号拥有天然的稀疏工作表。若 $x_4$ 的定义确定为常量，分析只需访问它的使用者；但 φ 的输入边、异常边与隐式内存使用必须包括在定义—使用图中，否则所谓“无使用”会漏掉真实依赖。

支配作用域值编号理路支配作用域值编号Dominance-scoped value numbering · Dominator-based value numbering · DVNT沿 SSA 支配树维护可回退的表达式表，用值代表识别跨块冗余，区分等值与载体可用，保守处理未解循环φ并执行变换后的程序。把这项优化出口具体化：按操作数的值代表建立表达式键，沿支配树保存并撤回可用载体，同块重复φ仅在输入编号已知时合并。它保留未解回边，不能把静态定义唯一误读为循环中的运行值不变。若改在无φ标量形式上消除只在部分来路重复的运算，边局部部分冗余消除理路边局部部分冗余消除Edge-local partial redundancy elimination · Incoming-edge PRE · 入边部分冗余消除对选定块首表达式按原图可用性保存载体，只在缺失入边补算并拆分关键边，以逐状态模拟证明正确及对应路径上的运算计数不增加。另行建立新鲜载体并在缺失入边补算；两项算法都不能替代本页的构造与消解证明。

SSA 不是目标机器通常直接执行的格式。进入寄存器分配前，编译器往往消解 φ、拆分关键边并安排并行复制。构造与消解必须各自保持语义；仅证明输入和输出都满足某种名字格式，不足以证明它们运行结果相同。

memory SSA 可为每次可能写内存的操作产生新内存版本，并让 load 使用支配它的版本；分支汇合时也需要内存 φ。它能把别名分析结果编码为稀疏依赖，却不会自己证明两个地址不别名。若外部调用的 mod/ref 摘要漏掉一次写入，内存版本链会显得合法但 load 仍可能读错值。