定义可达性
在编译器理论中，一个指令的定义可达性（Reaching Definition）必然是另外一个指令，而这个指令则是一个没有交错赋值指令的目标变数，举例来说：
d1 : y := 3 d2 : x := y
在d2中，d1为定义可达性，而在下列的范例中：
d1 : y := 3 d2 : y := 4 d3 : x := y
d1 在 d3不再是定义可达性，因为d2使它不再可能被到达。
作为分析用途
定义可达性也可称为数据流分析，它静态的决定在程式码当中哪些定义可以被到达，由于他相当简单，它在教课书当中通常被使用作数据分析的经典范例。数据流汇流运算（data-flow confluence operator）则是使用联集，而他的分析则是正向流动。定义可达性被使用在计算UD链以及DU链。
资料流方程式，给定一个基本区块 在定义可达性：
![{\displaystyle {\rm {REACH}}_{\rm {in}}[S]=\bigcup _{p\in pred[S]}{\rm {REACH}}_{\rm {out}}[p]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/88d90a4df4dc3fd7d5f07094e1c86593b00e56c2)
![{\displaystyle {\rm {REACH}}_{\rm {out}}[S]={\rm {GEN}}[S]\cup ({\rm {REACH}}_{\rm {in}}[S]-{\rm {KILL}}[S])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fc62c65a0828cf46b792d3a87e3cffc4161382f0)
换句话说，定义可达性的集合为，为的前身，在控制流程图（Control flow graph）中，包含所有在区块前的基本区块。定义可达性出来的，为所有定义可达性自己前身减掉那些被剃除掉的变数，再加上产生的新的定义。
![{\displaystyle pred[S]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/14ff3a07bc9cc297ab8420c3251155d4b066f742)
我们定义通用的指令及如下：
![{\displaystyle {\rm {GEN}}[d:y\leftarrow f(x_{1},\cdots ,x_{n})]=\{d\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ff7f9be7d2dc36f753cceeddbbef71e9fab32e1a)
![{\displaystyle {\rm {KILL}}[d:y\leftarrow f(x_{1},\cdots ,x_{n})]={\rm {DEFS}}[y]-\{d\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2da33640a2d7c543238f975c03ffdc9caeb4481a)
为所有赋值给变数定义的集合，是一个独立的标签附加在赋值的指令，那么定义可达性的值域就是这些指令标签。
![{\displaystyle {\rm {DEFS}}[y]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7ac2a74eaf464d0299fede5fd0aa0868aa2f78ad)
延伸阅读
- 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.