Skip to content

静态单赋值形式

Static single-assignment form · SSA form · 静态单赋值

通过变量版本化和控制流合流操作,使每个标量名字仅有一个静态定义且定义支配其使用的中间表示形式。

条目类型
定义

形式陈述

在约定的三地址码指令集上,静态单赋值形式(static single-assignment, SSA)要求每个标量名字恰有一个静态定义,并且该定义支配它的每个普通使用。对控制流图中的使用点 u 与其名字 xi 的唯一定义点 di,核心不变量为

didomu.

“静态一次”按程序文本计数,不按运行次数计数。循环头的一条定义可以在不同迭代反复执行;它仍是一个静态定义点。入口参数和全局初值通常视作位于人工入口的定义,因此参数的首次使用并非“无定义”。块参数式 SSA 把合流值写成后继块形参;经典 SSA 则使用φ 节点,两者都必须按前驱边解释值的来源。

块参数与 φ 的对应需要连同边一起给出:B(x) 有前驱边 PiB(ai),等价于在 B 入口写 x:=ϕ(Pi:ai)i。这个改写是表示层等价,不表示任意 SSA 都必须采用三地址文本;本页的三地址码分类明确限于前述指令集。图式、续延式或块参数式 IR 也可满足唯一定义不变量。

这项不变量主要针对可版本化的标量临时量。可变内存若可能由别名写入,不能仅把指针名字改成 p1,p2 就宣称内存处于 SSA;需要 memory SSA、effect token 或明确的读写别名模型。调用可能读写的内存、volatile 访问与原子操作同样位于这一边界。

直觉

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

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

例子与边界

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

x0:=0;x1:=x0+1  x2:=x0+2;x3:=ϕ(x1,x2);returnx3.

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

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

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

推论与应用

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

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

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

参考资料
  • Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck, “Efficiently Computing Static Single Assignment Form and the Control Dependence Graph,” ACM TOPLAS 13(4), 1991, pp. 451–490.
  • Andrew W. Appel, Modern Compiler Implementation in ML, Cambridge University Press, 1998, Chapter 19.
  • Fabrice Rastello, ed., SSA-based Compiler Design, Springer, 2022, Chapters 1–3.
关系图谱6 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
分类位置

上位 / 更一般

下位 / 直接特例

暂未标注直接特例。