到达定义分析

在 x:=1; x:=2; return x 中，返回值来自第二次赋值。加入分支以后，答案可能不再只有一个：一条路最后写了 1，另一条路最后写了 2。到达定义分析给每次赋值一个身份，列出一个程序点上可能提供当前值的那些身份。它记录值的来源，不直接计算值是多少。

一张菱形图中的七次赋值 ​

以下用块名加块内序号标识赋值；p 是布尔输入，a、b 是整数输入。

E: E.1 x := a+b
   E.2 y := x
   if p goto T else F
T: T.1 u := a+b
   goto J
F: F.1 u := a+b
   goto J
J: J.1 z := a+b
   J.2 dead := z+1
   J.3 r := u+y
   return r

进入 J 时，x 只可能来自 E.1，y 只可能来自 E.2，u 则可能来自 T.1 或 F.1。完整集合是

两个 u 定义同时出现在集合里，表示两种不同路径，绝不表示一次执行拥有两个“当前 u”。J.1 和 J.2 尚未执行，所以它们不能提前进入这个入口集合。执行 J.3 时，只从当时的集合中筛出定义 u 与 y 的身份，就得到该条加法的定义—使用连接。

把循环变成有限求解 ​

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

人工入口的 Boundary 是输入定义集，其他块为零。先删除从入口在图上不可达的块，再将所有 IN、OUT 初始化为空，把全部保留块放入工作队列。取出 B 后重算；只有 OUT 改变，才将 B 的后继加入队列。队列去重只影响工作量，不改变方程。

先处理不可达性有实质作用。若有无人能进入的 U，执行 U.1 u:=99; goto J，不该让 U.1 污染 J。普通 gen 转移会从空集合产生 U.1，故“所有节点从空开始”本身并不能解决不可达区域的问题。

再看一个循环：E 令 d0:x:=0，H 检查是否继续，B 执行 d1:x:=x+1 并回 H，退出 X 返回 x。第一次传播后，H 收到 d0；回边传播后，H 又收到 d1，最终 $IN[H]=IN[X]=\{d0,d1\}$。B 中右侧 x 的来源也是这两者，而 B 出口只有 d1。循环反复执行的同一赋值仍用同一个静态身份，分析不为每轮创造新 d1。

为什么不会遗漏真实来源 ​

对一条有限图路径的长度归纳。零长度入口路径由输入定义覆盖；沿不写 x 的语句走一步，原来源保留；沿写 x 的语句走一步，旧来源被删，新身份被加入。汇合的并集覆盖任意前驱。因此任何真正到达的定义都会进入某轮传播结果。

反方向也成立于本页的图路径定义：初始事实有入口见证，GEN 有经过本语句的见证，并集选择某个前驱见证，KILL 只删事实。每个保留下来的身份都可附上一条没有再次写同变量的图路径。有限不动点因而恰好等于图路径上的到达定义；具体运行是图路径的子集，结果对真实执行可靠，但可能多报不可行路径的来源。

有限身份集有 D 项，每个节点集合只会增长，最多新增 D 项，故过程终止。N 个块、M 条边、最大入度 $\mathrm{\Delta }$，用宽 w 的位集时，一次完整转移和每份前驱合并需 $O((1+\lceil D/w\rceil ))$ 个字操作；基本工作队列的保守界可写成 $O((N+MD)(\mathrm{\Delta }+1)(1+\lceil D/w\rceil ))$，另计构建块摘要。显式保存 IN/OUT 需要 $O(N(1+\lceil D/w\rceil ))$ 个字。这里的1项计入空事实域仍需执行的队列和边界工作，不声称每个程序点只访问一次。

从分析事实走向变换 ​

如果使用 x 的地方只看到一个定义 d，可以连接这次使用与 d；还不能仅凭这一点，把 d 的右侧文本原样搬来。例如 d 是 x:=a+b，随后 a 被改写，再使用 x。x 仍来自 d，却等于旧 a+b。若改成现场重算，就丢失了捕获旧操作数值的效果。复制传播理路复制传播Copy propagation · Available-copy analysis以可用复制对证明替换点两个变量仍同值，在任一端重定义时失效，并把跨分支的可靠替换与后续死代码删除分开。与可用表达式理路可用表达式分析Available-expression analysis · Available expressions用全路径交集计算已经算过且操作数未改变的表达式，以正确入口、先杀后生和自依赖检查支持安全复用。分别检查这种失效条件。

迁移任务：把菱形图 F 的定义改为 F.1 u:=0。进入 J 的身份集合不变，返回值却在 p 为假时从 $2(a+b)$ 变成 $a+b$。再删除 F.1，并在 E 新增 E.3 u:=9：进入 J 的 u 来源应为 T.1 与 E.3。两问用来区分“身份集合”与“数值计算”，以及跳过写入与写入常量零。

OPT-8 完整任务给出菱形图的全表、实际 IR 变换和检查器；每种分析在同一份输入上回答不同的问题。