数据流分析之Reaching Definition Analysis
目录
（2）什么是Reaching Definition Analysis？
（3）Reaching Definition Analysis有何用处？
（4）如何实现Reaching Definition Analysis？
（1）什么是Reaching Definition？
假设变量v在程序点p处被定义（赋值），我们可以说，变量v在程序点p处的定义到达了程序点p'，如果：
a. 程序点p和p'之间存在一条路径；
b. 变量v在上述路径中没有被重新定义（赋值）；
示意图如下：
（2）什么是Reaching Definition Analysis？
设p为某程序点，v = E为v的某定义语句：
RDA是，针对程序中的每个定义（p, v = E），分析出它可能到达的所有程序点（通常是一条指令的前后处）。
等价说法是，RDA是针对程序中的每个程序点(通常是一条指令的前后处)，分析出可能到达此处的所有定义（p, v = E）。
可以看出，RDA属于may分析，即RDA分析出的结果在程序实际执行时不一定会发生。
（3）Reaching Definition Analysis有何用处？
用处很多， 举两个例子来说明：
a. 死代码去除。假设我们分析出变量v在程序点p处的定义(p, v)可能到达的程序点集合为{
}，而在这些程序点对应的指令处，变量v并没有被使用过，这表明定义(p, v)是无用代码，可直接删除以优化程序；
b. 内存泄漏检查。假设动态内存分配指令对应的定义(p, v)可能到达的程序点集合为{
（4）如何实现Reaching Definition Analysis？
数据流分析一般分forward分析和backward分析。forward分析即，按程序执行的方向来分析信息如何传播；而backward分析则是按程序执行的反方向来分析信息的传播。
对于Reaching Definition Analysis，我们要分析的信息是，针对每个程序点，可能到达此处的所有定义（p, v）。在分析之前，我们就已经知道的一个事实是，在第一个程序点（程序第一条指令之前）处，可达定义集合是空，因为此时没有一条定义出现过。而对于最后一个程序点（程序最后一条指令之后）处的可达定义集合，则没那么显而易见。因此，RDA采用forward分析是很自然的一件事情。
首先，我们需要分析信息在通过一条指令后会发生什么变化。
这里我们举例分析：
见上图，在指令p处变量v被重新定义，因此变量v的旧定义(q3,v)无法到达程序点w1之后的所有程序点（包括w2），而其新定义(p,v)能到达的程序点至少存在一个，即w2。总结一下规则：
变量v的定义（新or旧定义）能到达指令p之后的紧邻程序点q，如果：
a. 变量v在p处被重新定义（旧定义不可达，而新定义可达）；
b. 变量v在p之前的紧邻程序点就已可达，且在p处未被重新定义（无新定义，因而旧定义可达）。
此外，还需要分析多条信息在某程序点汇聚时会发生什么变化。
前面说过，RDA属于may分析，即针对每个程序点，一旦某定义可能到达此处，那么此定义就要加入到此程序点的可达定义集合中。因此当来自不同分支的可达定义集合在某程序点发生汇聚时，此程序点处的可达定义集合应是各集合的并集。
综上，对于RDA，其在处的信息传播规则如下：
其中IN(p)是指令p之前的紧邻程序点处的可达定义集合，OUT(p)是指令p之后的紧邻程序点处的可达定义集合，pred(p)是指令p的前驱指令，defs(v)是以v为变量的定义，定义的形式是(指令,变量)。
我们也能从传播规则看出RDA属于forward分析，因为OUT(p)由IN(p)运算得来。
为什么是
而不是
？
前者是先把变量v的旧定义去掉，再加入v的新定义，符合RDA中的信息传播规则。而后者先加入v的新定义，接着把v的所有定义都去掉，这显然有问题。