資料流分析

資料流分析 是一種用於收集電腦程式在不同點計算的值的資訊的技術。一個程式的控制流圖（control flow graph, CFG）被用來確定對變數的一次賦值可能傳播到程式中的哪些部分。這些資訊通常被編譯器用來最佳化程式。資料流分析的一個典型的例子就是可到達定義的計算。

進行資料流分析的最簡單的一種形式就是對控制流圖的某個節點建立資料流方程，然後通過迭代計算，反覆求解，直到到達不動點。這個方法是由蓋瑞·基爾多在海軍研究生院任教時發明的。

基本原理

資料流分析試圖獲得程式中每一點的特定資訊。通常，在基本塊的界限內就可以獲得這些資訊，因為很容易計算基本塊中的資訊。在前向流分析(forward flow analysis)中，一個塊的結束狀態是這個塊起始狀態的一個函式。函式由塊內的語句的影響資訊組成。一個塊的開始狀態是它的前驅的結束狀態的函式。這就產生了一系列的資料流方程：

對於每一個塊b:

$out_{b}=trans_{b}(in_{b})$

$in_{b}=join_{p\in pred_{b}}(out_{p})$

在這裡，$trans_{b}$ 是塊$b$的 轉移函式。它作用於入口狀態$in_{b}$，並產生出口狀態$out_{b}$。連接運算子 $join$將塊$b$的前驅節點$p\in pred_{b}$的出口狀態聯合起來，產生入口狀態$b$。

在求解這一系列方程之後，塊的入口和出口狀態可以被用來獲得程式在塊內的屬性。每條語句的轉移函式可以被分別的用於獲得在一個基本塊內的某一點的資訊。

每一個特定類型的資料流分析都有它自己的特定的轉移函式和連接運算子。一些資料流問題需要後向資料流分析。和前向資料流分析類型相比，後向資料流分析使用的轉移函式使用出口狀態來產生入口狀態，連接運算子作用於後繼節點的入口狀態以產生出口狀態。

(在前向流分析中的)入口點起著重要的作用：因為它沒有前驅節點，它的入口資訊在分析開始時是明確的。比如，可以確定的局部變數的值的集合此時為空。如果控制流圖並不包含迴圈（在程式中顯性的或隱性的迴圈），只需直接求解資料流方程即可。此時可以對控制流圖的基本塊進行拓撲排序；按照排序後的結果依次計算，則每個塊的入口狀態都可以在塊起始處計算，因為此時塊的所有前驅節點都已經計算過了，所以它們的出口狀態是可以獲得的。如果控制流圖包含迴圈，那麼就需要一個更進階的演算法。

迭代演算法

最常用的用於求解資料流方程的方法是使用迭代演算法。它由每個塊的近似入口狀態資訊出發。然後應用轉移函式基於這些入口狀態資訊計算出口狀態資訊。然後，使用連接運算子更新入口狀態資訊。最後兩步將一直進行下去直至到達不動點: 即此時入口狀態資訊和出口狀態資訊都不再改變。

一個基本的求解資料流方程的演算法是迴圈迭代演算法:

for i ← 1 to N

初始化節點i

while (有集合發生了改變)

for i ← 1 to N

重新計算節點i處的集合

收斂性分析

為了可用性的要求，迭代演算法應該可以真正到達不動點。這可以通過對狀態的值域的聯合，轉移函式以及連接運算子加上限制條件來保證。

值域應該是有界的 且有序。(比如，不存在一個無限的遞增鏈$x_{1}$ < $x_{2}$ < ...)。轉移函式和連接運算子應該是單調的。單調性保持了對值的每次迭代操作要麼與之前一致，要麼會變大，而有界性保證了它不會無限增大下去。因此最終我們會到達一個狀態對於所有的x，有T(x) = x，此時即是不動點。

後向分析

• 活性變數

活躍變數分析計算每個程式點上的那些在重新定義前可以被潛在的使用的變數。這個的典型應用是用於死碼刪除，移除那些給變數賦值但之後變數未被使用的語句。

塊的入口狀態是在上個塊的末端仍然具有活性的變數的集合。

// out: {} b1: a = 3; b = 5; d = 4; if a > b then // in: {a,b,d} // out: {a,b} b2: c = a + b; d = 2; // in: {b,d} // out: {b,d} b3: endif c = 4; return b * d + c; // in:{}

其它方法

在2002年，Mohnen描述了資料流分析的一個新方法，這種方法不需要顯式的構造資料流圖,取代了依賴於程式的抽象解釋，並保持程式計數器工作列表集合的方法。在每個條件分支，對應的兩條路徑的目標都被加入工作列表中。每一條路徑被儘可能多的指令跟隨（直到程式結束點或直到沒有變化），然後從工作列表中被移除並取回下一個程式計數。

位向量問題

上述例子中的問題是資料流的值是一個集合，比如可到達定義集(使用位元位來表示程式中定義的位置)，或是活性變數的集合。這些集合可以通過位向量有效的表示，向量中的每一位表示一個特定元素是否屬於集合。使用這種表示，連接運算和轉移函式就可以通過按位元邏輯運算實現。連接運算子是一個典型的取併集或取交集操作，可以通過位元運算符邏輯或和邏輯與實現。每個塊的轉移函式可以被分解為產生集和殺死集。

舉例來說，在活性變數分析中，連接運算子是取併集操作。殺死集就是那些在當前塊中被重新定義的變數的集合，而產生集就是當前塊中在重新定義變數值之前使用的變數的集合。資料流方程因此變為 $in_{b}=\bigcup _{s\in succ_{b}}out_{s}$

$out_{b}=(in_{b}-kill_{b})\cup gen_{b}$

在邏輯運算中，這可以看做是

in(b) = 0

for s in succ(b)

in(b) = in(b) or out(s)

out(b) = (in(b) and not kill(b)) or gen(b)

敏感性分析討論

資料流分析本質上是流分析。資料流分析是典型的路徑不敏感的，儘管可以定義資料流方程產生路徑敏感的分析是可能的。

以下介紹的內容並不特定於資料流分析。

• 一個流敏感的分析會考慮程式中語句的順序。舉例來說，一個流不敏感的指標分析可能認為"變數x和y可能指向了同一位置"，而一個流敏感分析會認為"在語句20後，變數x和y可能指向了同一位置"。
• 一個路徑敏感的分析計算了依賴於分支條件的謂詞的不同的資訊。比如，如果一個分支條件是x>0，那麼在條件不滿足的分支，分析會假設x<=0；而在滿足條件的分支，會假設x>0確實成立。
• 一個上下文敏感的分析是一個互動過程分析，在分析目標函式的呼叫時它將考慮呼叫的資訊。特別的，使用上下文資訊，可以回退到原始的呼叫點，而如果沒有這種資訊，分析時就必須回退到所有可能的呼叫點，而喪失潛在的精度。

相關連結

• 可到達定義
• 活性分析
• 明確賦值分析

補充書目、位址及網址

• Aho, Alfred V. Sethi, Ravi. Ullman, Jeffrey D. Compilers: Principles, Techniques and Tools. Addison Wesley. 1986.
• Appel, Andrew W. Modern Compiler Implementation in ML. Cambridge University Press. 1999.
• Cooper, Keith D. and Torczon, Linda. Engineering a Compiler. Morgan Kaufmann. 2005.
• Muchnick, Steven S. Advanced Compiler Design and Implementation. Morgan Kaufmann. 1997.
• Hecht, Matthew S. Flow Analysis of Computer Programs. Elsevier North-Holland Inc. 1977.