定义可达性

在编译器及程式设计语言理论中，一个指令的定義可達性（Reaching Definition，中国大陆译作到达定值）指的是一个赋值指令x = ...的效果是否可能影响到其他指令... = x。举例来说：

d1 : y := 3
d2 : x := y

在d2中，d1为定义可达性。

而在下列的范例中：

d1 : y := 3
d2 : y := 4
d3 : x := y

d1 在 d3不再是定义可达性，因为d2使它不再可能被到达。 需要注意的是，由于循环的存在，一个指令对其自身也可能存在定义可达性，如：

d1 : x = 0
d2 : y = 0
d3 : while x < 5:
d4 :   x = x + 1
d5 :   y = y + 1
d6 :   y = y + 1

对于d4，d1与d4都为到达定值。 而对于d5，由于其对y的定义被d6覆盖，其不为自身的到达定值。

分析用途

定义可达性可以看作数据流分析的一个实例。它静态地确定在代码当中哪些定义可以被到达，被使用在计算UD链（Use-Def）以及DU链（Def-Use）。由于相当简单，它在教课书当中通常被使用作数据分析的经典范例。相当于使用并集作为数据流汇流运算（data-flow confluence operator）的正向数据流分析。 转移函数则为：

• ${\displaystyle {\rm {REACH}}_{\rm {in}}[S]=\bigcup _{p\in pred[S]}{\rm {REACH}}_{\rm {out}}[p]}$
• ${\displaystyle {\rm {REACH}}_{\rm {out}}[S]={\rm {GEN}}[S]\cup ({\rm {REACH}}_{\rm {in}}[S]-{\rm {KILL}}[S])}$

换句话说，定义可达性的定义域为程序基本块集合${\displaystyle S}$，值域则为程序中所有赋值语句的幂集。${\displaystyle pred[S]}$为${\displaystyle S}$的前驱，即控制流图（Control flow graph）中所有后继包含${\displaystyle S}$区块的基本块。定义可达性中${\displaystyle S}$的结果（OUT），为所有定义可达性自己前身的结果的并集减掉那些被${\displaystyle S}$剃除掉的定义（${\displaystyle KILL[S]}$），再加上${\displaystyle S}$产生的新的定义（${\displaystyle GEN[S]}$）。

我们定义通用的指令${\displaystyle {\rm {GEN}}}$及${\displaystyle {\rm {KILL}}}$如下：

• ${\displaystyle {\rm {GEN}}[d:y\leftarrow f(x_{1},\cdots ,x_{n})]=\{d\}}$
• ${\displaystyle {\rm {KILL}}[d:y\leftarrow f(x_{1},\cdots ,x_{n})]={\rm {DEFS}}[y]-\{d\}}$

${\displaystyle {\rm {DEFS}}[y]}$为所有赋值给${\displaystyle y}$变量定义的集合，${\displaystyle d}$是一个独立的标签附加在赋值的指令，那么定义可达性的值域就是这些指令标签。

延伸阅读

• Aho, Alfred V.; Sethi, Ravi; & Ullman, Jeffrey D. Compilers: Principles, Techniques, and Tools. Addison Wesley. 1986. ISBN 0-201-10088-6.
• Appel, Andrew W. Modern Compiler Implementation in ML. Cambridge University Press. 1999. ISBN 0-521-58274-1.
• Cooper, Keith D.; & Torczon, Linda. Engineering a Compiler. Morgan Kaufmann. 2005. ISBN 1-55860-698-X.
• Muchnick, Steven S. Advanced Compiler Design and Implementation. Morgan Kaufmann. 1997. ISBN 1-55860-320-4.

另见

• 静态单赋值形式