死代码消除

x:=3; return 7 中的 x 从未被读取，算出它对返回结果没有帮助。不过 x:=read_input(); return 7 仍读取了外界输入。死代码消除要同时证明“结果没人要”和“这次计算本身可以省去”。本页先给出一个保守而完整的死赋值删除算法。

逆序删除会产生连锁 ​

a := 3
b := a+1
return 0

返回0不读变量。逆序遇到 b:=a+1 时，b 不活跃且加法纯总，可以删；删掉之后，不再为了被删除的右侧而加入 a 的需求。再遇到 a:=3，a 也不活跃，同一轮即可删掉。

正确的块内扫描如下：

L = LiveOut[B] ∪ 终结指令的使用
从后往前看每条 x:=e：
    若 x∉L 且 e可删除：删除；L不变
    否则保留；L = (L−{x}) ∪ Vars(e)

如果删除后仍把 Vars(e) 加入 L，虽然通常不至于删错，却会把本来已经死亡的依赖保活，错失这一轮的连锁收益。

四个不能省略的边界 ​

x:=1/0; return 7 中 x 死了，但源会 trap，删除后却返回7，观察改变。若语言把除零当未定义行为而非 trap，必须另用那套精化合同论证，不能悄悄替换本页模型。

x:=f(); return 7 里的 f 可能发散。即便它没有I/O，删除也可能让原本不终止的程序返回。纯粹与总定义是不同条件。

store(p,9) 没有局部目标变量，并不因此“结果未使用”。它修改后续可能读取的存储；死存储消除需要别名、覆盖和异常等额外分析，本页不处理。

SSA 中一组互相引用却没有外部使用的 φ 循环，可能让简单的使用计数或普通活跃性互相保活。本页保守算法允许留下这种代码。按可观察根反向标记的更强删除方法还涉及控制依赖与终止保持，不能只靠“换成队列”就视为已经实现。

一个范围受控的独立接口是线性函数测试替换理路线性函数测试替换Linear function test replacement · LFTR · 线性测试替换借助已证明的h等于mi加c关系改写循环界比较，按斜率符号保序或逆序，在无其他读取和退出观察时删除原计数器，并拒绝零斜率与不适用的回绕推理。：先用已证明的仿射递推改写循环比较，再检查计数器除自身更新外不再被体内、条件或出口读取，最后成对删除初始化与递增。它为这一个封闭分量另给状态关系证明，不声称本页的保守活跃性迭代可以自动删除所有自读循环；出口仍返回计数器时明确拒绝。

跨块要重新求需求 ​

把上一例拆成 E 中 a:=3、T 中 b:=a+1，E 跳到 T，T 返回0。初始活跃性认为 T 读取 a，因此 E 的出口包含 a。第一次扫描先删掉 T 的 b，却可能仍依据旧边界保留 E 的 a。重新求活跃性后，T 的入口为空，第二次才能删 E 的 a。

算法因此循环执行“分析活跃性→逆序删除”，直到没有指令被删。下载实现仅扫描入口可达块，未可达块原样保留，不访问没有为它们建立的IN/OUT表；它没有顺便删除不可达代码。每个非空删除轮至少减少一条赋值，有限程序中最多 K 轮；最后再做一轮确认稳定。无删除时的活跃性已是当前程序的，而不是某个早期版本的残留表。

OPT-8 先经 CSE 与复制传播得到：E 定义 x=a+b、y=x；T/F 定义 u=x；J 定义 z=x、dead=x+1、r=x+x，返回r。第一次删除会去掉 dead、z、u、y，保留 x 和 r。所有控制边仍在，所以 p 仍决定走 T 还是 F，只是这两个块已没有赋值。

最终每次运行执行两次加法：x=a+b、r=x+x，返回 $2(a+b)$。这是对任意数学整数 a、b 都成立的恒等式。下载检查器实际执行变换后 IR，并对162组小输入交叉比对；有限测试检查实现，恒等式和下节保持论证承担一般保证。

为什么删除不会影响后面 ​

取一次被删赋值 x:=e。跳过它以后，源与目标的全部变量都相同，唯独 x 可以不同；源还多执行了一次不可观察且必终止的纯运算。因为 x 在语句后不活跃，任意后续路径在读 x 之前，要么先覆盖它，要么永不读它。

如果先覆盖 x，源和目标重新得到相同 x；如果不读 x，它的不同不会影响算术、分支或返回。其他变量始终对应，所以执行经过相同控制路径并产生相同观察。将有限次删除逐一组合，就得到整轮和整个迭代过程的保持性质。

这也覆盖发散路径：控制指令没有改变，保留指令的输入一致；每次被删除的操作只占有限的内部步骤。只要源无限循环，目标仍沿同样无限控制转移执行，不会凭删除无用赋值变成正常返回。若尝试把“无输出的无限循环”整体删掉，就已经超出此证明。

代价与迁移 ​

设初始过程有 N 个基本块、I 条赋值，其中 K≤I 条满足本页的删除许可；许可只说明运算可以省去，是否真死仍需活跃性证明。令 V 为变量总数。控制图不变，后续赋值和变量集合只会缩小。用 A(N,I,V) 表示这些删后程序中，一次完整活跃性求解的统一成本上界，包含图与指令扫描；它不能只由 K 决定，因为即使 K=0，过程仍可有任意多个控制块。

每个有删除的轮次至少删掉一条候选赋值，所以至多 K 轮；还须加最后一次无删除的稳定确认，合计至多 K+1 次分析和逆序扫描。若集合使用位集，每轮扫描除了赋值，还要为各可达块读取出口集合、处理终结指令并建立保留列表。沿用活跃性页的字宽 w，保守扫描上界是 $O((N+I)(1+\lceil V/w\rceil ))$ 个字操作。因此，计入初始过程复制的粗略总界为

这里用整个过程的 N、I 作上界，也覆盖原样保留不可达块的初始复制。K=0 时仍有一次分析与块扫描；V=0 时括号中的1也不能省掉。例如一条没有赋值、只有128个跳转或返回块的可达链，仍需访问128个块，并完成一次无删除的确认。

下载参考器实际用Python集合，不是打包位集；按变量标识的单位成本集合操作计，扫描的保守上界应将 $1+\lceil V/w\rceil$ 换成 $V+1$，其活跃性成本也按该实现另计。集合元素的哈希、比较或对象复制若不是单位成本，还须支付相应费用。以上衡量的是编译器工作，不是被编译程序时间。基于SSA使用链的专用工作队列可以减少重复分析，但需要另外维护使用计数、φ和控制约束。

迁移任务：给 OPT-8 加一条可观察的 print(dead)，那么 dead 与它读取的 x 都要保留，只有无用复制仍可删。再把 print 改成不执行的注释，dead恢复可删。最后把 dead 的右侧改成 1/(a-b) 并规定除零 trap：即使结果未被使用，也不能按本页白名单删掉。取 a=b=2，就得到“源trap、错误目标返回8”的具体反例。

完整任务还要求分别检查跨块两轮删除、零次循环外提和带未知分支的 SCCP，防止把某一优化的许可扩散到整条流水线。