查看“︁定義可達性”︁的源代码

在編譯器理論中，一個指令的'''定義可達性'''（Reaching Definition）必然是另外一個指令，而這個指令則是一個沒有交錯賦值指令的目標變數，舉例來說：

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

在<code>d2</code>中，<code>d1</code>為定義可達性，而在下列的範例中：

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

<code>d1</code> 在 <code>d3</code>不再是定義可達性，因為<code>d2</code>使它不再可能被到達。

== 作為分析用途 ==

'''定義可達性'''也可稱為[[数据流分析]]，它靜態的決定在程式碼當中哪些定義可以被到達，由於他相當簡單，它在教課書當中通常被使用作數據分析的經典範例。數據流匯流運算（data-flow confluence operator）則是使用聯集，而他的分析則是正向流動。定義可達性被使用在計算[[UD鏈]]以及[[DU鏈]]。

資料流方程式，給定一個基本區塊 <math>S</math>在定義可達性：

* <math>{\rm REACH}_{\rm in}[S] = \bigcup_{p \in pred[S]} {\rm REACH}_{\rm out}[p]</math>
* <math>{\rm REACH}_{\rm out}[S] = {\rm GEN}[S] \cup ({\rm REACH}_{\rm in}[S] - {\rm KILL}[S])</math>

換句話說，定義可達性的集合為<math>S</math>，<math>pred[S]</math>為<math>S</math>的前身，在[[控制流程]]圖（Control flow graph）中，<math>pred[S]</math>包含所有在<math>S</math>區塊前的基本區塊。定義可達性出來的<math>S</math>，為所有定義可達性自己前身減掉那些被<math>S</math>剃除掉的變數，再加上<math>S</math>產生的新的定義。

我們定義通用的指令<math>{\rm GEN}</math>及<math>{\rm KILL}</math>如下：

* <math>{\rm GEN}[d : y \leftarrow f(x_1,\cdots,x_n)] = \{d\}</math>
* <math>{\rm KILL}[d : y \leftarrow f(x_1,\cdots,x_n)] = {\rm DEFS}[y] - \{d\}</math>

<math>{\rm DEFS}[y]</math>為所有賦值給<math>y</math>變數定義的集合，<math>d</math>是一個獨立的標籤附加在賦值的指令，那麼定義可達性的值域就是這些指令標簽。

== 延伸閱讀 ==
*{{cite book
|author=Aho, Alfred V.; Sethi, Ravi; & Ullman, Jeffrey D.
|title=[[Compilers: Principles, Techniques, and Tools]]
|publisher=Addison Wesley
|year=1986
|isbn=0-201-10088-6}}
*{{cite book
|author=Appel, Andrew W.
|title=Modern Compiler Implementation in ML
|publisher=Cambridge University Press
|year=1999
|isbn=0-521-58274-1}}
*{{cite book
|author=Cooper, Keith D.; & Torczon, Linda.
|title=Engineering a Compiler
|publisher=Morgan Kaufmann
|year=2005
|isbn=1-55860-698-X}}
*{{cite book
|author=Muchnick, Steven S.
|title=Advanced Compiler Design and Implementation
|url=https://archive.org/details/advancedcompiler00much
|publisher=Morgan Kaufmann
|year=1997
|isbn=1-55860-320-4}}

== 另見 ==
*[[静态单赋值形式]]

[[Category:程序分析]]