Data Flow Analysis Applications

Data Flow Analysis Application

Reaching Definitions Analysis

判断变量的定义能否到达某一点，即该变量的定义是否被覆盖了。

Transfer Function:

Control Flow:

gen和kill的计算：

Algorithm:

为什么迭代算法最终能够停下来：kill是固定的，所以被kill掉的definition一次也不会出现在out中，这也就导致不可能存在某一个definition，其在某一轮迭代中存在于OUT[B]，而在之后的某一轮中不存在于OUT[B]，即OUT只增不减，最多增长为全1。

Live Variable Analysis

判断变量在某一点的值是否会在之后被使用到，即变量在该点的值在被使用前是否被重新定义了。当寄存器满时，应该优先淘汰不会被用到的变量所占据的寄存器，即 dead variable 的寄存器。注意，这里是对“变量”进行分析，而Reaching Definition Analysis则是对“变量的定义”进行分析。

该问题使用Backward Analysis，即由OUT[B]推导出IN[B]。

Transfer Function:

Control Flow:

其中在计算use和def时，需要注意：如果在同一个BB中，该变量既被使用又被定义，则需要根据其被使用和定义的先后顺序来决定其是否出现在use和def中。这里的use是用来计算IN[B]的，所以判断某个变量是否属于use，应该以IN[B]时刻变量的值为基准。

例如下面的Basic Block：

b = a + 1;
a = b + 1;
x = x - 3；

这里变量a先被使用，后被定义，所以a应该出现在IN[B]中，故a应该出现在use中。而变量b先被定义再被使用，所以b不应该出现在IN[B]中，故b不应该出现在use中。变量x也是先被使用再被定义，所以同变量a。

Algorithm:

Available Expression Analysis

若从Entry到点 的任意一条路径都需要计算表达式 ，且在表达式 的最后一次计算后， 和 均没有被重新定义，则称表达式 在 点是 available 的。

Transfer Function:

Control Flow:

注意这里的Control Flow用的是交集，即表达式在所有前驱节点都available时，其在B才是available的。

在计算gen和kill时，也需要根据表达式的计算和变量重新定义的顺序来决定其是否出现在gen中，关键在于看在最后一次计算后，变量是否被重新定义。

Algorithm:

Conclusion

Reaching Definitions Analysis 和 Live Variable Analysis 都是 May Analysis ，即 Complete Analysis。 Available Expressions Analysis 是 Must Analysis ， 即 Sound Analysis。