到达定值分析

• 定值(Definition)
  变量x的定值是(可能)将一个值赋给x的语句

• 到达定值(Reaching Definition)

  1. 如果存在一条从紧跟在定值d后面的点到达某一程序点p的路径，而且在此路径上d没有被“杀死” ( 如果在此路径上有对变量x的其它定值d′，则称变量x被这个定值d′ “杀死” 了) ，则称定值d到达程序点p。

  2. 直观地讲，如果某个变量x的一个定值d到达点p，在点p处使用的x的值可能就是由d最后赋予的。

例-可以到达各基本块的入口处的定值.png

到达定值分析的主要用途

• 循环不变计算的检测

如果循环中含有赋值x=y+z，而y和z所有可能的定值都在循环外面(包括y或z是常数的特殊情况)，那么y+z就是循环不变计算。

• 常量合并

如果对变量x的某次使用只有一个定值可以到达，并且该定值把可以到达，并且该定值把一个常量赋给x，那么可以简单地把x替换为该常量。

• 判定变量x在p点上是否未经定值就被引用

“生成”与“杀死”定值

定值d:

u = v + w

这里，“+”代表一个一般性的二元运算符；该语句“生成”了一个对变量u的定值d，并“杀死”了程序中其它对u的定值。

到达定值的传递函数

定值d的传递函数.png

注：f_d(x)是指所有定值d之后到达定值d的集合

基本块B的传递函数.png

gen_B是需要考虑在B基本块中语句被本基本块杀死的情况。

例-各基本块B的genB和killB.png

到达定值的数据流方程

到达定值的数据流方程.png

注：除了ENTRY外的其他基本块，它们在出口处到达定值的值，可以通过每个基本块的传递函数来求得。一个基本块的出口处的到达定值依赖基本块的入口处的到达定值，那么基本块的入口处的到达定值如何求呢？我们说可以到达基本块的各个前驱基本块出口处的到达地址都可以到达入口处。因此基本块B入口处的到达地址等于它的各个前驱基本块出口处的地址的并集。

到达定值方程的计算

计算到达定值的迭代算法.png

例.png

注：初始时所有基本块的出口值都是空值，用类向量七个零来表示。

例.png

引用-定值链(Use-Definition Chains)

引用-定值链(简称ud链)是一个列表，对于变量的每一次引用，到达该引用的所有定值都在该列表中。

引用定值链.png