定義可達性

在編譯器理論中，一個指令的定義可達性（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 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. 

另見

• 静态单赋值形式