边局部部分冗余消除

想删除汇合处的计算，必须先给每条来路准备同一份交接约定：“进入后可以读取 h。”已经算过的来路把当时结果另存到 h；没有算过的来路在最后一条入边上补一次。原来保存结果的名字是否还活着，就不再靠猜测。

这里把补算放得很靠近目标，是因为目标第一条指令必定使用该值，中间没有条件分叉或操作数写入。这个局部结构给出直接的逐路径证明，不需要借用完整 PRE 的全局最优性结论。

有可用表达式，却没有可靠的旧变量 ​

取 a=2、b=3，p、q 决定路径：

E: if p goto T else F
T: x := a+b
   x := 0
   goto J
F: if q goto J else X
J: z := a+b
   answer := z*2
   return answer
X: return -1

原图中 OUT(T)=true、OUT(F)=false，因此 IN(J)=false。T 路的表达式仍可用，x 却已被覆盖为0。把 J 直接改为 z:=x，会使本应返回10的 T 路返回0；只计算可用性而不安排载体是不够的。

正确变换在 T 写 h:=a+b; x:=h; x:=0，在 F→J 上插入 h:=a+b，再把 J 改为 z:=h。取 p=1，源加法两次、目标一次，都返回10；取 p=0、q=1，两边都加一次并返回10；取 p=q=0，两边都不加，直接返回−1。

F→J 是关键边，因为 F 还可去 X，J 还有来自 T 的边。若把补算塞到 F 的分支前，p=q=0 时仍返回−1，却多做一次加法。这直接违反本页的路径运算保证。若擅自把 e 扩成可能失败的运算，旁路甚至可能新增陷阱；纯总前提不能默默放宽。

缺少载体也有可执行坏例：只在 F→J 补 h，却不在 T 保存原计算，随后令 J 读 h。走 T 路时 h 从未初始化，参考执行器会明确拒绝这次读取。不能用“另一条路给 h 赋过值”修复当前运行。

回边可以已有值，首次进入仍必须初始化 ​

考虑一个受 n 控制的累加循环。入口设 i=sum=0，H 检查 i<n，真时第一次进入 J，假时直接到 X 返回 sum。J 先算 z=a+b，再到 B 累加 sum:=sum+z、i:=i+1；B 再检查 i<n，真时直接回 J，假时到 X。

a、b 在循环内不变。对目标 J 的第一条加法，H→J 缺失，B→J 已有。算法只拆首次进入边 H→J，并把 J 改读 h；回边仍直接进入 J。n=3、a=2、b=3 时返回15，选定加法从3次变为1次。n=0 时走 H→X，既不进入新块，也不计算 h，仍返回0且加法0次。

若在 B 中加入 b:=b+1，OUT(B) 变为 false；两条进入 J 的边都没有可靠旧值，算法返回 no_available_edge，保留源程序。n=3 时各轮 z 为5、6、7，返回18；错误地沿回边继续复用首次 h=5 会返回15。这是操作数失效，不是缺少更激进的代码移动技巧。

一次局部改写不能替代完整 PRE ​

本算法只处理块首位置。如果 e 位于块中间，需要先核对之前指令是否改变操作数、控制或可观察行为，或者显式把程序点拆成块；不能直接把本页的入边证据套到后面的使用处。

它也不自动把语义相同、文本不同的表达式合并。支配作用域值编号理路支配作用域值编号Dominance-scoped value numbering · Dominator-based value numbering · DVNT沿 SSA 支配树维护可回退的表达式表，用值代表识别跨块冗余，区分等值与载体可用，保守处理未解循环φ并执行变换后的程序。能按值代表组织键，但两种接口采用不同载体纪律；若要组合，应明确如何把结果转成合法的无 φ 标量 IR，再重新计算当前图的可用性。

静态程序可能变大：本例 T 多一条复制，缺失边多一个块，J 仍保留一次复制。路径加法减少并不保证寄存器压力、全部指令数或墙钟时间减少。h 的活跃范围也可能跨过多个原块。

可用性与载体初始化的联合不变量 ​

证明时同步执行源与目标，在原程序点比较全部源变量，允许目标多一个 h。对于原分析判为 e 可用的程序点，另保持 h 已定义且等于按当前源操作数计算 e 的值。

初始可用性为空，不要求 h 预先存在。遇到非目标的 x:=e，目标先把相同结果保存到 h，再复制给 x；若 x 不改 e 的操作数，新的 h=e 不变量成立。若 x 就是一个操作数，源分析也不会在出口生成可用性，所以不强求旧 h 等于更新后的 e。其他写操作数的语句杀掉分析事实；不写操作数的语句保持关系。

现在到达目标 J。若来自已有边，原 OUT 的全路径性质和刚才的不变量给出 h=e；若来自缺失边，新块刚用相同源状态计算 h=e。新块不写源变量，并无其他分支。故 J 的 z:=h 与源 z:=e 对源状态的影响完全相同。若这次赋值又使 e 在出口可用，它没有改 e 的操作数，h 也就继续满足所需不变量。

这一证明不会在循环中用未来计算作初始化依据。首次到达任何原点仍从人工入口开始归纳；原可用性采用固定入口与最大不动点的全路径保证，而缺失入口边显式补上 h。每次回边只是同一个逐路径归纳的下一步，目标之前的已知 h 是已经执行的事实。

分支读取和返回读取都保持，因此原块路径与返回值相同。新增边块只有一条有限计算和无条件跳转，不会自己形成新循环。有限原执行只展开成有限目标执行；无限原块路径也仍对应无限目标路径，纯总运算没有引入新的发散来源。

怎样严格配对运算次数 ​

除目标外，每条原 e 计算只换成一条 h:=e 加一条复制，因此 e 的次数不变。每次到达目标 J，源恰计算一次 e。若走已有边，目标这次计算零次；若走缺失边，目标在专属边块计算一次，然后 J 只复制。每次新增计算都能唯一配对到紧接着被删除的那次目标计算。

所以对每条终止运行，以及按相同原程序点对齐的有限执行前缀，选定表达式在目标中的计算次数不超过源。这里的“对应前缀”把专属边块与后续目标指令视为一个有限匹配片段；若把目标停在边块中间，却把源停在尚未计算的 J 之前，就不是同一个对齐点。证明不比较任意两个独立机器时钟下的计数。

所得保证只是不增加，并不要求每个输入都严格减少。始终走缺失边的运行省零次，始终绕过目标的运行也省零次。新增复制、变量存储与大整数运算的位成本仍要单独计费。

分析与实际参考器的成本 ​

令 N、M、K 分别为原块数、边数和指令及操作数总大小。对固定的一个表达式，块出口可用性只有真假两值，从 true 初始化后每块至多变成 false 一次。参考器每轮重扫图与块内指令，故至多 N 个严格轮次加一个稳定轮，成本 O((N+1)(N+M+K))，可用性表本身占 O(N)；图和程序存储另计。

得到可用性后，复制程序、记录原计算、扫描目标入边和插入专属块需要 O(N+M+K) 工作与同阶输出空间。新鲜名字用按前缀递增的计数器检查冲突，不为每个新块从零重新扫描全部已生成名字。每条缺失边最多增加一个块，不会把循环展开成无穷图。

参考器还独立验证所有变量在使用前已定义，这不是上面的单表达式分析。若源变量数为 Q，一组块出口定义集合至多删除 NQ 个成员；每轮集合交和指令扫描可保守界为 O((Q+1)(N+M+1)+K)。验证因此有 O((NQ+1)((Q+1)(N+M+1)+K)) 的粗界，存储 O(N(Q+1)+M+K)。输入检查被多个公开函数调用，输出也重验；总成本应把各次验证相加，并对新增块和载体使用更新后的规模。

可执行终点交付三条分支路径、关键边旁路坏例、丢失载体坏例、零轮与回边、操作数被改写后的拒绝，以及源/目标按原块投影后的完整状态轨迹。有限预算耗尽只说明检查了一个前缀，不是一般终止或发散判定器。