« 上一篇下一篇 »

变量表达式算法可用

交汇运算是交集运算,任何发现x+y在某个程序点上不可用的理由都会在流图中沿着所有可能的路径向前传播,直到x+y被重新计算并再次变得可用为止。第二,只有两个理由可能会使x+y变成不可用的。

1)因为x或y在基本块B中被定值且其后没有计算x+y,因此x+y被杀死。在这种情况下,我们第一次应用传递函数fs的时候,x+y就会从OUT[B]中被删除。

2)在某些路径中,x+y—直没有被计算。因为x+y肯定不会在OUT[ENTRY]中,并且它也不会在上面说的那条路径中被生成。我们可以通过对路径长度的归纳来证明x + y最终会从这条路径的所有基本块的IN和OUT值中删除。

因此,当各个IN和OUT值不再改变的时候,迭代算法给出的解将只包含真正的可用表达式。

1)各个IN和OUT的值决不会增长。也就是说,这些集合在后来的取值总是它们前面取值的子集(不一定是真子集)。

2)如果表达式e从IN[B]或0UT[S]中被删除,那么必然相应地存在一条从流图人口到达B的开始处或结尾处的路径,要么e在这条路径上从没有被计算过,要么在最后一次对e计算之后,e的某个参数被重新定值了。

3)如果表达式最终保留在IN[B]或0UT[B]中,那么相应地从流图人口到基本块B开始处或结尾处的所有路径中,e都被计算,且在最后一次计算e之后,e的参数都没有被重新定值。

细心的人可能注意到在算法中,我们可以把各个基本块B的初始化为OUT[B],这样可以减少一些运行时间。类似地,我们还可以把useB初始化为 IN[B]。我们没有这么做的原因是为了用统一的方法来处理这个主题。我们将再次看到这一点。但是,可以把e_genB初始化为0UT[B]吗?为什么可以或不可以?

我们的数据流分析没有利用条件跳转的语义。假设我们在一个基本块的结尾处找到一个如下的测试:

if (x < 10) goto ...

我们如何利用对测试表达式x<10的理解来改进有关到达定值的知识?请记住,在这里“改进”意味着我们要消除某些实际上永远不可能达到某个程序点的到达定值。

« 上一篇下一篇 »