定义可达性

定义可达性也可称为数据流分析，它静态的决定在程式码当中哪些定义可以被到达，由于他相当简单，它在教课书当中通常被使用作数据分析的经典范例。数据流汇流运算（data-flow confluence operator）则是使用联集，而他的分析则是正向流动。定义可达性被使用在计算UD链以及DU链。

资料流方程式，给定一个基本区块 ${\displaystyle S}$ 在定义可达性：

• ${\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 pred[S]}$ 包含所有在${\displaystyle S}$ 区块前的基本区块。定义可达性出来的${\displaystyle S}$ ，为所有定义可达性自己前身减掉那些被${\displaystyle S}$ 剃除掉的变数，再加上${\displaystyle 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. 

• 静态单赋值形式