定義可達性

在編譯器及程序設計語言理論中，一個指令的-{定義可達性}-（Reaching Definition，中國大陸譯作-{zh-hans:到达定值;zh-hant:到達定值}-）指的是一個賦值指令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 d4，d1與d4都為到达定值。
而對於d5，由於其對y的定義被d6覆蓋，其不為自身的到达定值。

分析用途
定義可達性可以看作数据流分析的一個實例。它靜態地確定在程式碼當中哪些定義可以被到達，被使用在計算UD鏈（Use-Def）以及DU鏈（Def-Use）。由於相當簡單，它在教課書當中通常被使用作數據分析的經典範例。相當於使用聯集作為數據流匯流運算（data-flow confluence operator）的正向数据流分析。
轉移函數則為：

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

換句話說，定義可達性的定义域為程序基本块集合S，值域则为程序中所有賦值語句的冪集。pred[S]為S的前驅，即控制流圖（Control flow graph）中所有後繼包含S區塊的基本塊。定義可達性中S的结果（OUT），為所有定義可達性自己前身的结果的并集減掉那些被S剃除掉的定義（KILL[S]），再加上S產生的新的定義（GEN[S]）。

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

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

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

评论 (0)