到达定值

我们可能希望找出在某个程序点上一个变量可能有哪些值，以及这些值可能在哪里定值。考虑下面这段代码：

$$\begin{aligned} &d_1: \quad a \leftarrow 1 \\ &d_2: \quad \text{if read() <= 0 goto } d_6 \\ &d_3: \quad b \leftarrow a \\ &d_4: \quad a \leftarrow 6 \\ &d_5: \quad \text{goto } d_2 \\ &d_6: \quad \text{other instructions} \\ \end{aligned}$$

我们可能对程序点( $d_6$ )上的所有程序状态进行总结：$a$ 的值总是 ${1, 6}$ 中的一个，而它由 ${d_1, d_4}$ 中的一个定值。可能沿着某条路径到达某个程序点的定值称为到达定值(reaching definition)。

到达定值是最常见和有用的数据流模式之一。只要知道当控制到达程序中每个点的时候，每个变量 $x$ 可能在程序中的哪些地方被定值，我们就可以确定很多有关 $x$ 的性质。比如，一个编译器能够根据到达定值信息知道 $x$ 在点 $p$ 上的值是否为常量，而如果 $x$ 在点 $p$ 上被使用，则调试器可以指出 $x$ 是否未经定值就被使用。

未定值先使用

我们可以在流图的入口处对每个变量 $x$ 引入一个哑定值(dummy definition)。如果 $x$ 的哑定值到达了一个可能使用 $x$ 的程序点 $p$，那么 $x$ 就可能在定值之前被使用。请注意，我们永远不能绝对肯定这个程序包含一个错误。因为有可能存在某种原因使得到达 $p$ 点而没有真正对 $x$ 赋值的路径实际上并不存在。这个原因可能涉及复杂的逻辑问题。考虑以下程序片段：

int x;		// x_dummy
if (不透明谓词（一个复杂的数论真命题）) {
    x = 10; // x_1
}
printf("%d\n", x); // x_2

分析器可能无法推导分支条件恒为真。实际上，分析器会插入 $\phi$ 函数（$\phi$ 函数的作用请参考这里 ）：

$$x_2 \leftarrow \phi(x_{dummy}, x_1)$$

由于 $x_{dummy}$ 和 $x_1$ 的值一定不同。所以分析器必须假设 $x_{dummy}$ 和 ${x_1}$ 都可能到达第五行代码。但实际上 $x$ 未定义的情况永远不会发生，但是编译器根据分析结果将会报告 $x$ 可能存在未定义被使用。这个反例展示了静态分析的根本局限性，它能识别所有可能的错误路径，但无法确定哪些路径会在实际执行中发生。这就是为什么到达定值分析只能给出“可能存在未定义使用”的警告，而非确定性结论。