公共子表达式消除

如果 a、b 都没有变化，第二次计算 a+b 可以直接读取第一次的结果。难处在“第一次”不一定存在于当前路径上，结果也可能早被覆盖。公共子表达式消除（CSE）要同时回答两件事：表达式是否可用，哪个值现在还能代表它。

CSE 先省去两次加法 ​

OPT-8 的源程序在每条执行路径中依次做：x=a+b、u=a+b、z=a+b、dead=z+1、r=u+y，其中 y=x。前面三条都在算同一个表达式，后两条不是。

CSE 把 T 与 F 的 u=a+b、J 的 z=a+b 改为复制 x。当 a=2、b=3 时，x=5，所走分支的 u=5，J 的 z=5、dead=6、r=10。控制路径与所有被使用的值不变，每次运行的加法从5次降为3次：x、dead、r。接着复制传播得到 r=x+x；再删掉无用 dead 和复制链，才降为2次。不能把整条流水线的全部收益都归到 CSE 名下。

优化后的每条路径只执行一条 u:=x，虽然源文件里有 T、F 两份静态赋值。静态指令数与一次运行的动态计数要分别统计。

没有共同支配定义时怎么办 ​

考虑 E 直接分支，T 做 u=a+b，F 做 v=a+b，J 做 z=a+b。J 处表达式可用，但 u 未在 F 路定义，v 未在 T 路定义，二者都不能直接成为全路径载体。

可以引入新鲜 t，在两个分支里保存结果：T 改为 t:=a+b; u:=t，F 改为 t:=a+b; v:=t，J 改为 z:=t。每条进入 J 的路径都已设置 t；t 不属于源变量，所以不会覆盖源状态。这种非 SSA 临时量有两个定义，若目标要求 SSA，则为两分支各用 tT、tF，在 J 加 t:=phi(T:tT,F:tF)。

这里只消除了各路径都重复的一次计算，没有增加原本不执行 e 的路径。若 F 没算 e，就不满足全可用条件；可以研究在 F 插入一次计算的部分冗余消除，但那是另一项代码移动算法，必须核算新增执行和陷阱，不能在 CSE 名下直接外推。

一个逐运行的保持证明 ​

对有锚点版本，取任一运行到替换点。支配保证它已经经过锚点；沿中间路径，t 不被覆盖，e 的操作数也不被覆盖，故 t 中仍保存按当前操作数计算 e 的结果。确定性确保该结果唯一。把 e 改为读取 t，赋给 z 的值相同，随后程序状态在全部源变量上保持一致。

对于分支接线版本，则在每条生成 t 的路径建立同样不变式：进入 J 前，t=e 的当前值。所有进入边都有赋值，所以汇合时成立。不必要求两条路径的 a、b 彼此相同，只要求每条路径上保存的值与那条路径当前的操作数匹配。

在本页的纯总模型里，省去计算也不删去异常、事件或发散。若 e 是 load(p)，期间的别名写入会使它改变；若 e 是随机调用，重复调用本来就可以不同；若 e 是可能 trap 的运算，则需要另证被删掉的那次计算不提供新的可观察失败。单纯比较表达式文本无法处理这些扩展。

成本不能只看算术次数 ​

CSE 的分析成本包含可用表达式、支配和载体失效检查。有了这些证据，扫描 K 个候选并发出替换代码是 O(K) 加表达式键查询的工作；不能把这一后半段称为整个 CSE 的复杂度。

运行时算术减少，也可能延长 t 的活跃范围，增加寄存器压力和 spill。数学整数加法的位成本取决于操作数长度，CPU 上的耗时还受指令选择和缓存影响。OPT-8 只报告语义层的运算计数，不给机器码加速倍率。

迁移任务：在 F 中先写 a:=a+1，再算 u=a+b，其他块不变。取 a=2、b=3、p=false，源的 x=5、u=6、z=6、y=5，最终 r=11。E 的 x 已不能替代 F 和 J 的 a+b；请指出它同时在哪项可用性证明中失效。再只在 F 写 x:=0，则 a+b 仍可用，但 x 载体失效，错误替换会算错。这两题分别检查操作数与载体。