φ 节点放置算法

每个定义像向下游涂一种颜色。只要所有入口路径都经过同一定义区域，颜色不必合并；到支配边界时，来自该区域的颜色第一次可能遇到绕开它的颜色，于是需要 φ 给汇合后的值一个新名字。新名字继续向下传播，因此还要迭代边界，直到没有新的合流点。

活跃性回答另一问题：汇合后的值未来会不会在重新定义前被读取。DF 说“不同定义可能相遇”，liveness 说“相遇结果是否有用”。pruned SSA 将两种信息相交，减少无用 φ；若在无活跃性证明时凭感觉删 φ，可能让某条定义—使用路径失去唯一来源。

设 $x$ 在菱形两支 $A,B$ 中定义，二者在 $J$ 汇合，且 $J$ 后返回 $x$。有 $J\in \mathrm{DF}(A)\cap \mathrm{DF}(B)$，故第一轮在 $J$ 放 $x_3:=\varphi (A:x_1,B:x_2)$。因为返回在重新定义前读取 $x$，$x$ 对 $J$ live-in，minimal 与 pruned 两种算法都保留此 φ。

若把返回改为先执行 $x:=0$ 再读 $x$，控制流完全不变，IDF 仍含 $J$，minimal SSA 仍可放 φ；但旧值在 $J$ 不 live，pruned SSA 不放。这个成对例子说明少放一条 φ 不能仅由 CFG 推出，也说明 pruned 比 minimal “更少”并非 minimal 一词自相矛盾：两者优化目标和约束口径不同。

嵌套汇合说明迭代不可省。定义块 $A,B$ 在 $J_1$ 汇合，$J_1$ 的一路又与不经过 $J_1$ 的定义块 $C$ 在 $J_2$ 汇合。第一轮产生 $J_1$，把它视作新定义后才会把 $J_2$ 找出。只取 $\mathrm{DF}(\mathrm{Def}(x))$ 一次，可能漏掉 $J_2$，使其后使用无法由单一定义支配。

工作表实现应按变量维护“是否已放置”和“是否已入队”标记，避免循环 CFG 中重复插入。复杂度由定义数、DF 边与实际 φ 数共同决定；先为所有变量在所有多前驱块放节点虽易实现，却会放大重命名、优化和后续消解成本。

放置只是 SSA 构造的第一阶段。此时 φ 参数仍可保留原变量占位符；第二阶段必须沿支配树重命名定义和使用，并按具体前驱边填写参数。若放置正确而重命名时把参数写到错误边，得到的仍是语义错误程序。异常边、关键边与不可达块也必须采用与 CFG、支配计算相同的边集合。