資料流分析

數據流分析 是一種用於收集計算機程序在不同點計算的值的信息的技術。一個程序的控制流圖（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.