活跃变量分析

一行赋值完成以后，哪些旧值还不能丢？只要未来可能读取某个值，而且在读取之前没有重新定义它，就要继续保管。活跃变量分析从使用点向后寻找这些需要保留的值，因此信息的传播方向与程序的执行方向相反。

同一菱形图的完整边界 ​

使用到达定义页理路到达定义分析Reaching definitions analysis · 到达定值分析沿控制流保留每个变量可能最近执行的赋值，以入口定义、逐语句杀生与最小不动点建立定义到使用的可靠连接。的 E、T、F、J 程序：E 计算 x=a+b、y=x；T 与 F 各计算 u=a+b；J 依次计算 z=a+b、dead=z+1、r=u+y，返回 r。

J 的逆序轨迹尤其值得手算：返回前是 {r}；越过 r:=u+y 后为 {u,y}；越过 dead:=z+1 后为 {z,u,y}；越过 z:=a+b 后为 {a,b,u,y}。dead 自己从未活跃，但它的右侧 z 在原程序中仍是一次使用。因此普通活跃性不会自动假装某条语句已经删除；死代码消除理路死代码消除Dead-code elimination · DCE · Dead assignment elimination删除结果不再需要且计算纯粹总定义的赋值，重新计算需求直至稳定，保留控制流、陷阱、副作用和终止行为。需要在实际删除之后更新分析。

块级 USE 也不是块内所有 USE 的无序并集。E 中 y:=x 的 x 先在同块定义，所以 x 不属于 E 的“进入时即需要”的 USE。顺序扫描块，从 USE 中只加入当前尚未在 DEF 出现的读变量，再把当前写变量加入 DEF，就得到正确块摘要。

φ 的使用属于哪一条边 ​

φ 节点理路SSA 的 φ 节点Phi node · Phi function · φ 节点在 SSA 控制流汇合块中按实际进入的前驱边选择对应版本，并以并行方式定义合流值的伪指令。 v:=phi(T:x,F:y) 在从 T 来时读 x，从 F 来时读 y。它不在 J 入口同时读取两个变量。令 $PhiDef(J)$ 为 J 顶部 φ 的结果集，$PhiUse(P,J)$ 为对应 P→J 槽位的输入集；若 LiveIn(J) 定义在 φ 之后、普通指令之前，则

这里计算的是保留全部 φ 指令时的普通活跃性，所有对应槽位都作为使用；若先删除死 φ，才可缩减这些使用。P 的 OUT 是各离开边 LiveEdge 的并集。J 普通指令向后扫描的起点不再把 φ 当普通指令重复处理。

例如 J 只返回 v，则 φ 后 LiveIn(J)={v}。T→J 上只需要 x，F→J 上只需要 y。把 {x,y} 都传给每个前驱虽是保守近似，却会制造不必要的同时活跃，进而增加寄存器干涉。本单元可运行检查器的主 IR 没有 φ；这条边敏感扩展在此给出公式与独立纸面验算，SCCP 页另有 φ 的专用实现。

工作队列怎样处理回边 ​

这是单调数据流框架理路单调数据流分析Monotone dataflow analysis · Monotone framework · Data-flow equations在控制流图上以单调 transfer 和合流方程求解前向或后向程序事实。的后向 may 实例，合流保留任一后继的需求。后向方程是

正常出口 OUT 为空；返回值由返回指令 USE 加入，不要既把返回藏起来、又以空出口为由忘掉它。所有集合从空开始，把全部可达块入队。某块 IN 改变时通知它的前驱，因为前驱的未来需求变了。

循环中可能要多轮：若 B 增加一个使用，需求沿回边传到循环头，再沿前驱继续传递。值只增加，变量总数 V 有限，所以每个块最多增加 V 项。对每条有限见证路径归纳，最终集合不会漏掉其首次读取；反过来，每次 USE 生成和后继传播都能构造一条见证路径。因此得到的是图路径定义的精确最小不动点，而非具体可行路径的完美判定。

用位集和去重工作队列，N 个块、M 条边、最大出度 $\mathrm{\Delta }$ 时，逐次重扫全部后继的保守代价为 $O((N+MV)(\mathrm{\Delta }+1)(1+\lceil V/w\rceil ))$ 个字操作，存储为 $O(N(1+\lceil V/w\rceil ))$。块内逐语句展开时还要处理指令数。因子中的1保留V=0时仍需进行的队列与图扫描。变量很多但集合很稀时可以使用稀疏集合，不能继续套相同的位操作常数。

活跃事实如何使用 ​

若 x 不在一条赋值之后活跃，赋值的新值不会在任何图路径上被使用。但能否删掉该指令，还要看右侧是否有副作用、陷阱或发散；x:=read_input() 即使 x 死了仍会消耗输入。活跃性回答“值需不需要”，不回答“这次计算能不能不发生”。

迁移任务：删掉菱形图的 dead:=z+1 后重新计算。J.1 的 z 没有使用了，但普通分析仍会把计算 z 时的 a、b 列入 J 的入口；再删掉 z:=a+b，J 入口才变为 {u,y}。另将返回改为 return z，则 r 死了，z 成为真正的返回需求。请分别写出两种变更的逆序轨迹，不只改集合表的最后一格。