“设基本块 $B$ 在控制流图中有按边标识的前驱 $P 1,\ldots,P k$。静态单赋值形式中的 φ 节点”
形式陈述 ​
在约定的三地址码指令集上,静态单赋值形式(static single-assignment, SSA)要求每个标量名字恰有一个静态定义,并且该定义支配它的每个普通使用。对控制流图中的使用点
“静态一次”按程序文本计数,不按运行次数计数。循环头的一条定义可以在不同迭代反复执行;它仍是一个静态定义点。入口参数和全局初值通常视作位于人工入口的定义,因此参数的首次使用并非“无定义”。块参数式 SSA 把合流值写成后继块形参;经典 SSA 则使用φ 节点,两者都必须按前驱边解释值的来源。
块参数与 φ 的对应需要连同边一起给出:
这项不变量主要针对可版本化的标量临时量。可变内存若可能由别名写入,不能仅把指针名字改成
直觉
普通程序反复给变量
SSA 没有消除控制流。名字唯一并不意味着值唯一:不同执行可以使同一个定义产生不同运行时值,例如循环中的
例子与边界
考虑菱形程序:入口给
沿真边手算得到
循环展示“静态”一词的边界。初始化
内存反例也很具体:令
推论与应用
唯一定义使常量传播、复制传播、死代码删除和值编号拥有天然的稀疏工作表。若
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.