第6章：数据流分析与程序优化

活跃变量

若变量当前值可能在被重新定义前被读取，则该变量在此处活跃。基本块 B 的活跃性方程为

OUT[B]=\bigcup_{S\in succ(B)}IN[S],\qquad IN[B]=USE[B]\cup(OUT[B]-DEF[B]).

USE 只包含块内定义前使用的变量。分析逆着控制流传播，因为后续使用决定之前的值是否需要保存。

在有限变量集合上，从空集合开始反复应用单调转移，集合只会增大，最终到达固定点。这个固定点包含 CFG 所允许路径的使用，因此可能把实际不可达路径也算入，是保守近似。

块 B 为 x=y+1，后继需要 x,z，则 $OUT[B]=\{x,z\}$ 、 $DEF[B]=\{x\}$ 、 $USE[B]=\{y\}$ ，所以 $IN[B]=\{y,z\}$ 。旧 x 已被覆盖，不必从前驱带入。

若 B 改为 x=x+1，USE 也包含 x，入口就必须保留旧值。同一个名字出现在左右两侧时，定义与使用顺序不能混淆。

常量传播为每个值维护“尚无信息、某个常量、不能确定为常量”等抽象状态。两个前驱分别得到 3 与 3，合流仍是 3；分别得到 3 与 4，合流不能确定为单一常量。

条件分支也可提供可达性信息。若条件已知为真，删除假分支可能让更多值成为常量；分析与变换经常需要迭代。

死代码删除可移除结果无人使用且无可观察副作用的操作。一个结果未使用的函数调用仍可能写文件或抛异常，因此不能仅据活跃性删除。

公共子表达式消除要求操作数值相同且表达式效果可复用。循环不变代码外提还要考虑循环零次执行的情况：将除法移到循环前，可能在原本不执行循环时新增除零异常。

浮点中的 x+0=x 也要核对带符号零、NaN、舍入及语言允许的优化模式。代数恒等式不必然是所有机器语义下的等价变换。