稀疏条件常量传播

普通常量传播看到一条路传来10、另一条路传来未知输入，就只能说汇合结果未知。但如果第二条路根本走不到呢？SCCP 一边找常量，一边确定哪些控制边需要考虑：常量能排除分支，排除分支又能使更多值成为常量。这两个过程必须一起求稳定结果。

一个完整的常量链 ​

E: a := 4
   b := 6
   c := (a == 4)
   if c goto T else F
T: t := a+b
   goto J
F: f := q                 // q是任意整数输入
   goto J
J: v := phi(T:t,F:f)
   w := v*2
   d := (w == 20)
   if d goto R else B
R: return w
B: return 99

激活 E 后，a=4、b=6、c=true，于是只激活 E→T。T 给出 t=10，再激活 T→J。J 的 φ 只看已激活的 T→J 槽，所以 v=10；随后 w=20、d=true，只激活 J→R。最终可达块集合为 {E,T,J,R}，q虽为 $\mathrm{\top }$，却没有通过未激活的 F→J 污染 v。

若忽略条件、把两条边预先都激活，f便为 $\mathrm{\top }$，φ得到 $10\bigsqcup \mathrm{\top }=\mathrm{\top }$，无法继续发现 w=20。这是条件分析带来的精度，SSA使用链则承担稀疏传播的效率；两项贡献不同。

三项边界防止过度承诺 ​

把 E 的条件改成布尔输入p。若 T给10、F给14，则两边激活，v和w都是 $\mathrm{\top }$，J 的两个出口都保留。若改为两边都给10，即使p未知，φ仍为10，后面的 d仍为真。下载实现同时检查这两个迁移。

再考虑两条分支分别产生 (x,y)=(1,1) 和 (2,2)，汇合后计算 z=x−y。逐变量常量域把x、y都视为 $\mathrm{\top }$，所以基础规则无法推出z=0；两者相等这一关系已丢失。SCCP可靠，并不意味着找到所有语义常量。

这里的 $\mathrm{\perp }$ 也不是目标语言的任意位模式或LLVM的undef。把编译器中间状态与源程序未定义语义混用，会让等待规则或删除规则失去依据。真实工业IR还需单独处理异常、浮点、内存、poison和可见效果。

为什么稳定后的删除可信 ​

中间时刻的未激活边还可能在以后被发现，因此不能提前把它删掉；同样，中间的常量以后可能升到 $\mathrm{\top }$。只有两个队列都为空，并且所有上述约束满足，才可以使用结果改写程序。

对任一真实有限执行前缀按步数归纳。入口边已激活，输入参数由 $\mathrm{\top }$ 覆盖。若真实执行到普通赋值，各输入此前的真实值已被抽象值覆盖；相应转移便覆盖这次结果。若到φ，实际前驱边已被纳入 X，它的槽值参与合流，因此覆盖所选值。若遇分支，稳定值要么是匹配真实结果的常量，要么是 $\mathrm{\top }$，算法都已经纳入实际下一条边。沿前缀归纳，所有真实执行边都在 X 中。

这也排除了“真实走到条件却永久为 $\mathrm{\perp }$”的情况：良构、已定义的输入和有限执行前缀会逐层提供值证据，队列稳定时不能仍遗漏这些约束。因而未激活边不可真实执行；稳定常量在每次实际定义执行时都取该值。程序可以删除未激活块、折叠已证常量分支，并把相关读取改成常量，仍要维护剩余φ槽和CFG良构性。

本页检查器完整实现该分析，输出边、值和事件列表；它没有自动发出清理后的SSA。主例可手工读成直接返回20，是独立的终点答案，不把分析结果文件误称为编译器已完成全部清理。

复杂度必须说明φ的实现 ​

设 N 个指令与块、M 条控制边、U 次定义—使用出现。每个值最多发生两次严格上升，每条控制边最多激活一次；固定元数普通运算的工作因此与这些事件数线性相关。

但若每次有φ消息都重新扫描它的 k 个槽，该φ最多收到 O(k) 次新边或输入变化消息，代价可能为 O(k²)。下载检查器就是这种简单实现，故总界为 $O(N+M+U+\sum _{\varphi }{k}_{\varphi }^2)$，另计常量算术位成本，存储为 $O(N+M+U)$。维护每个槽的已合流贡献并增量更新，可以将φ工作降到线性；没有实施这种维护时不能直接引用原论文的线性结论。

终点请先不运行脚本，写出主例从START→E到J→R的全部激活边，列出f为何仍为 $\mathrm{\perp }$ 而q为 $\mathrm{\top }$。再完成p未知的两种迁移，并解释检查器的有限常量链不证明任意源程序一定终止。