可用表达式分析

看到 u:=a+b，编译器想问：这次加法是否早已算过？仅仅在源码上方找到 a+b 不够，那次计算可能位于没有走到的分支，也可能使用了后来被改写的 a。表达式在一点可用，要求每条到达该点的图路径都算过它，而且从某次这样的计算到当前点之间没有修改它的操作数。

为什么汇合必须求交 ​

在一张菱形图中，T 计算 a+b，F 什么也不做，然后汇合到 J。a+b 在 T 出口可用，在 F 出口不可用，因此在 J 入口不可用。若用并集，就会把“至少一条路径算过”误当成“当前这次运行肯定算过”。

若 T 与 F 都计算 a+b，并且都没有随后改 a 或 b，J 入口便可用。两条路可以把结果存进不同名字；这不影响表达式可用，却会影响怎样发出复用代码。

在 OPT-8 的共同程序中，E 已先算 x=a+b，之后任何块都不写 a、b，所以表达式 e=add(a,b) 沿两条路径一直保留。进入 J 时的集合恰为 {e}；执行 z=a+b 后仍为 {e}，再执行 dead=z+1 加入 add(z,1)，执行 r=u+y 再加入 add(u,y)。完整集合是三项，不包括复制 y=x。

从可用到可复用，还差一个名字 ​

t := a+b
t := 0
z := a+b

a、b 未变，最后一行的 a+b 确实可用；但 t 已经变成 0。把 z 改成 t 是错误的。正确办法可以在第一次计算时另存一个不被覆盖的新临时量，或找到其他仍保存该值的载体。可用性描述表达式，载体分析描述存储，两者不能省掉一个。

迁移任务：把 OPT-8 的 F 块赋值从 u:=a+b 改为 u:=0，再给 F 加 a:=a+1。进入 J 时 add(a,b) 应从交集中消失，即使 E 和 T 都算过。取 a=2、b=3、p=false，J 的加法应为 6；复用 E 的 x=5 会错。若只把 F 的赋值改为 u:=0 而不改 a，表达式仍然可用，原因是 E 的那次计算已覆盖两条路径；两种版本都保留 u 的定义，不引入未初始化读取。

从“可能全部可用”逐步收紧 ​

本分析是单调框架理路单调数据流分析Monotone dataflow analysis · Monotone framework · Data-flow equations在控制流图上以单调 transfer 和合流方程求解前向或后向程序事实。的前向 must 实例。先取入口可达子图，人工入口没有任何预先计算的表达式：

这里 E 是没有回边进入的人工入口，真实循环头另设为普通块。非入口集合从 U 初始化，入口从空开始；每次重算会删除未获所有路径支持的假设，直至稳定。这是在集合包含次序下求最大不动点；若改用反向信息序，也可以称最小不动点，但初始化和合流必须一起改。

为什么不全从空开始？考虑入口已经算 a+b，随后进入一个不写 a、b 的空循环。循环头既有入口边，也有回边。方程允许“循环头可用”和“循环头不可用”两个不动点，全空可能停在后者，遗漏真实全路径事实。U 初始化保留所有尚未反驳的候选，入口边最终消除无凭据假设。

入口条件也不能取 U。那会把从未执行过的计算当成免费存在。不可达块则应先剔除，避免对没有入口路径的点使用空交为 U，再把这份形式上的真空事实当优化证据。

可靠性怎样逐路径核对 ​

对一个表达式 e，可以把每条语句看成三个动作之一：改操作数则杀掉；重新正确计算且出口操作数未变则生成；其余保持。对有限入口路径复合这些动作，路径末端的布尔答案恰好表示 e 是否可用。

上述转移对交集分配：共同通过删除集合，再并入同一个 GEN，与先分别处理再求交相同。由于只考虑入口可达图且固定入口边界，经典有限分配框架的最大不动点等于所有入口图路径的交。因此分析中的每一项都有全路径保障，反方向也不会漏掉图路径意义上的可用项。真实可行路径只是图路径的子集，故可能因不可行分支而保守地漏掉优化机会。

设 Q=|U|、最大入度为 $\mathrm{\Delta }$。每块集合最多删除 Q 项，位集表示下逐次重扫前驱的工作队列保守代价为 $O((N+MQ)(\mathrm{\Delta }+1)(1+\lceil Q/w\rceil ))$ 个字操作，存储 $O(N(1+\lceil Q/w\rceil ))$。即使Q=0，因子中的1仍计入队列与图扫描。构造“某变量出现在哪些键”索引有助于生成 KILL；若每次都扫描全部表达式，必须把该代价计入转移，不能声称赋值处理恒为常数。