支配作用域值编号

VN 像一本“这些名字已经证明谈的是同一个值”的记录。H 则回答更具体的问题：“沿当前所有入口路径，哪个名字现在真的装着这个值？”第一本记录可以提到别处的名字，第二本不能拿尚未执行的分支给当前路径供货。

支配树提供自然的作用域。走进一个孩子，它继承祖先计算；处理完后回到父节点，那些仅在该孩子里得到的载体就退出作用域。它与词法环境的入栈、出栈相似，但这里的树来自每条控制路径都必须经过的节点。

一份包含复制与两个 φ 的完整例子 ​

输入 a=2、b=3、c=4，p 决定走哪一条分支：

E: t := a+b
   u := a
   if p goto T else F
T: x := u+b
   left := x*c
   goto J
F: y := a+b
   right := y*c
   goto J
J: z := phi(T:left, F:right)
   w := phi(T:left, F:right)
   r := z+w
   k := w+z
   s := t+t
   return (r,k,s)

入口建立 VN(u)=a，并把 add(a,b)→t 放入 H。T 中 x 的键因此是 add(a,b)，可改为 x:=t；F 中 y 同样改为 y:=t。left 与 right 的乘法表达式虽然也相同，却分别位于兄弟分支，没有共同支配的乘法载体，故两条乘法都保留。

J 的 z 合并两条不同名字，先保留代表 z。w 的逐前驱映射与 z 完全一致，因此 VN(w)=z。r 的键变成 add(z,z)，k 的键也变成 add(z,z)，于是 k:=r。这个等值不依赖加法交换律：真正被比较的两个有序参数已经逐项相同。

无论 p 为0还是1，源与目标都得到 z=w=20、r=k=40、s=10，返回 (40,40,10)。目标中的 x、y、k 仍有原位置的定义，只是改为复制；两个 φ 也仍执行。每个经过的源块末尾，所有已经定义的源名字都与原程序同值。

静态算术指令从8条降到5条；一次运行只走一边，动态算术从6次降到4次。复制次数从1次增到3次，φ 数量不变。这里只报告语义层操作计数，不把算术减少自动换成机器码加速。

兄弟分支为什么不能借名字 ​

把入口的 t 计算删去，令 T 计算 x=a+b，F 计算 y=a+b，J 用 φ(T:x,F:y) 返回所选值。两条路都返回5，但 x 没有在 F 路定义。如果 H 在退出 T 后不回退，F 可能错误改为 y:=x；取 p=0，执行会读到未初始化的 x。

这个反例不是说两次加法不相等，而是说不能用一边的存储载体代表另一边的运行。若要让相同值跨分支统一，还需要合法合流或专门的放置算法；仅把 H 改成永不删除的全局哈希表会丢掉支配保证。

静态名字在循环中仍可每轮改变 ​

循环头用 i:=φ(E:0,B:next) 与 sum:=φ(E:0,B:acc)。当 i<n 时进入 B，执行 one=i+1、again=i+1、acc=sum+again、next=i+1，再回到头；否则返回 sum。

第一次访问循环头时，next 和 acc 尚未编号，因此两个 φ 都取得新代表。循环体仍可把 again 与 next 改为 one 的复制，因为 one 在这一轮先算出同一 i+1。n=3 时两边都返回6，源体每轮4次加法，目标每轮2次，共12对6；n=0 时两边都没有体内加法。

one 不是跨全部迭代不变的常量。它在每次进入 B 时重新定义为1、2、3，后面的复制读取当轮 one。SSA 的“单赋值”是静态定义点唯一，不能据此缓存第一次循环的运行值。

支配作用域怎样保证实际值可复用 ​

先建立局部表不变量：H 中每个载体的定义位于当前支配树祖先，或位于当前块已处理的较早位置；它记录的键使用已证明等值的操作数代表。新增计算满足不变量，沿树下降只继承支配祖先，退出时删除局部键，因而兄弟分支不会泄漏载体。

仅说“SSA 名字不会重新赋值”仍不足以证明循环。本页需要动态版本的事实：若某个操作数定义支配载体定义，而载体又支配当前复用点，那么在最近一次载体计算后、到这次复用前，操作数不可能被重新执行定义却绕过载体。否则，把首次到达那个操作数定义的入口路径与这段绕过载体的后缀拼接，就得到一条到复用点却不经过载体的入口路径，矛盾。同块内则由普通指令的顺序保证。

因此载体保存的操作数版本仍适用于这次复用。对处理顺序归纳，复制传播保持等值，已有键逐分量使用同值操作数，纯确定操作便得到同一结果。将 x:=op(...) 改为 x:=r 不改变 x 或任何其他源名字的值。

φ 的平凡情况在每条入边都取同一个已知代表；同块重复情况则在同一条实际入边选择相同代表。未解回边保持独立，不需要循环猜测。把这些关系用于后续普通读取或对应 φ 槽，仍保持选择到的实际值；原 φ 同时读取旧入边值的约定不变。

逐块组合，分支条件与返回值相同，所有原块都按同一顺序执行。每块只做有限个纯总运算或复制，所以不会把有限执行变成发散，也不会吞掉原来的无限控制流。对可能不终止的程序，有限测试只能检查前缀；全局结论由这项逐块关系保证。

分开计算分析、变换与目标成本 ​

若已经给出正确的支配树，令 K 为指令与参数槽的总大小，N、M 为块数和边数。在固定元数、固定大小键及平均常数时间哈希假设下，普通指令扫描、作用域登记和撤回共 O(K+N+M)；VN 与作用域表占 O(K+N) 空间。没有重复复制整张 H，是这个界成立的关键。

参考器还为确定性展示排序支配树孩子和 φ 前驱槽，分别计 O(N log(N+1)) 与各 φ 的 O(d log(d+1))，d 为该 φ 的输入槽数。程序复制、最后的槽改写与输入输出验证也要计费；数学大整数的计算和字符串比较不能按无限精度常数免费处理。

支配关系并非免费输入。参考器为透明采用集合交的同步方程，而不是实现高效支配树算法：非入口集合从全体块开始，每个严格轮次至少删除一项，粗略至多 N² 个严格轮次；每轮集合工作可界为 O(N(N+M))，得到保守 O(N³(N+M)) 上界与 O(N²+M+K) 存储。输入和输出都验证 SSA，包含重复的支配检查；这不改变粗界，却应包含在实际运行成本中。

这个算法既不完备判定程序值等价，也不保证最少动态计算。它保留未解循环 φ，不能凭空发现分配律等代数关系，无法直接消除只有部分路径先算过的表达式。边局部部分冗余消除理路边局部部分冗余消除Edge-local partial redundancy elimination · Incoming-edge PRE · 入边部分冗余消除对选定块首表达式按原图可用性保存载体，只在缺失入边补算并拆分关键边，以逐状态模拟证明正确及对应路径上的运算计数不增加。转而在缺失入边补计算，并单独证明载体初始化和路径计数，不应与本页哈希表作用域混在一起。

可执行终点要求交出实际代表表、被替换的三条指令、两个分支和循环的状态轨迹，并运行兄弟载体泄漏的失败例。随后检查一种需要新增边计算、仅靠本页不能完成的冗余。