对于一个给定的程序点,可达定义(reaching definition)是一组赋值语句,这组语句定义了当前程序点中变量的值。 对于这个分析,我们的幂格是程序中所有出现的赋值语句(用CFG的节点表示)。例如下述程序:
var x,y,z;
x = input;
while (x>1) {
y = x/2;
if (y>3) x = x-y;
z = x-4;
if (z>0) x = x/2;
z = z-1;
}
output x;
描述抽象状态的格为如下:
对于每一个CFG的节点v,用$[[v]]$ 表示在当前节点之前可能定义了此节点中变量的结合。我们定义JOIN函数如下:
对于赋值语句,约束规则为:
其中,$\downarrow X$ 函数表示删除所有赋值给X的赋值语句。对于其他所有的节点,规则就是JOIN的结果:
$$ [[v]] = JOIN(v) $$
这个分析可以用来构建一个def-use图,这个图和cfg很像,图里面的边是从定义指向使用。如下是例子程序的def-use图:
def-use图是程序的进一步抽象,并且是很多广泛使用的优化技术的基础,例如死代码消除和代码提升。