定義可達性

维基百科,自由的百科全书
跳转至: 导航搜索

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

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

d2中,d1為定義可達性,而在下列的範例中:

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

d1d3不再是定義可達性,因為d2使它不再可能被到達。

作為分析用途[编辑]

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

資料流方程式,給定一個基本區塊 S在定義可達性:

  • {\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])

換句話說,定義可達性的集合為Spred[S]S的前身,在控制流程圖(Control flow graph)中,pred[S]包含所有在S區塊前的基本區塊。定義可達性出來的S,為所有定義可達性自己前身減掉那些被S剃除掉的變數,再加上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是一個獨立的標籤附加在賦值的指令,那麼定義可達性的值域就是這些指令標簽。

延伸閱讀[编辑]

另見[编辑]