定義可達性

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

另見

• 靜態單賦值形式