【教學(xué)課件】第2章 數(shù)據(jù)流分析

1、.1第第2章章 數(shù)據(jù)流分析數(shù)據(jù)流分析 內(nèi)容概述內(nèi)容概述數(shù)據(jù)流分析推導(dǎo)的是數(shù)據(jù)沿著程序執(zhí)行路數(shù)據(jù)流分析推導(dǎo)的是數(shù)據(jù)沿著程序執(zhí)行路徑流動(dòng)的信息徑流動(dòng)的信息 過程內(nèi)的分析：可用表達(dá)式分析、到達(dá)定值分過程內(nèi)的分析：可用表達(dá)式分析、到達(dá)定值分析等析等 過程間分析過程間分析 Shape分析分析 理論基礎(chǔ)理論基礎(chǔ) 數(shù)據(jù)流方程的求解數(shù)據(jù)流方程的求解.2第第2章章 數(shù)據(jù)流分析數(shù)據(jù)流分析 數(shù)據(jù)流分析的用途數(shù)據(jù)流分析的用途 編譯優(yōu)化、程序維護(hù)編譯優(yōu)化、程序維護(hù) 程序安全性的檢查程序安全性的檢查 和編譯原理課程的區(qū)別和編譯原理課程的區(qū)別基于源代碼的結(jié)構(gòu)化分析方法，而不是基于基基于源代碼的結(jié)構(gòu)化分析方法，而不是基于基本

2、塊和程序流圖的分析本塊和程序流圖的分析從過程內(nèi)討論到過程間從過程內(nèi)討論到過程間強(qiáng)調(diào)理論基礎(chǔ)強(qiáng)調(diào)理論基礎(chǔ).3第第2章章 數(shù)據(jù)流分析數(shù)據(jù)流分析 數(shù)據(jù)流分析的正確性數(shù)據(jù)流分析的正確性數(shù)據(jù)流分析所得結(jié)論同程序運(yùn)行時(shí)的情況一致數(shù)據(jù)流分析所得結(jié)論同程序運(yùn)行時(shí)的情況一致需要定義機(jī)器模型和操作語義，證明所得結(jié)論需要定義機(jī)器模型和操作語義，證明所得結(jié)論對(duì)操作語義可靠對(duì)操作語義可靠由于數(shù)據(jù)流分析收集的信息同基本塊和控制流由于數(shù)據(jù)流分析收集的信息同基本塊和控制流有關(guān)，通常和變量值無關(guān)，因此不同于一般的可有關(guān)，通常和變量值無關(guān)，因此不同于一般的可靠性證明，例如靠性證明，例如Hoare邏輯的賦值公理是可靠的邏輯的賦值公

3、理是可靠的x = 1 x := x + 1 x = 2.4活躍變量分析活躍變量分析 活躍變量分析的正確性活躍變量分析的正確性需要將該正確性概念形式地表達(dá)出來需要將該正確性概念形式地表達(dá)出來在活躍變量的初值相同的不同格局下在活躍變量的初值相同的不同格局下 S, 1 和和 S, 2 執(zhí)行程序執(zhí)行程序S的結(jié)果應(yīng)該是一樣的的結(jié)果應(yīng)該是一樣的再細(xì)化一下，程序每執(zhí)行一步，得到的不同格再細(xì)化一下，程序每執(zhí)行一步，得到的不同格局局 S , 1 和和 S , 2 中，活躍變量的值都相同中，活躍變量的值都相同.5第第2章章 數(shù)據(jù)流分析數(shù)據(jù)流分析 數(shù)據(jù)流分析的基礎(chǔ)數(shù)據(jù)流分析的基礎(chǔ) 把各種數(shù)據(jù)流模式作為一個(gè)整體來抽象

4、地研把各種數(shù)據(jù)流模式作為一個(gè)整體來抽象地研究，然后可以形式地回答數(shù)據(jù)流算法的下列究，然后可以形式地回答數(shù)據(jù)流算法的下列幾個(gè)基本問題：幾個(gè)基本問題： 在什么情況下數(shù)據(jù)流分析中使用的迭代算法是正在什么情況下數(shù)據(jù)流分析中使用的迭代算法是正確的？確的？ 該迭代算法所得解的精度如何？該迭代算法所得解的精度如何？ 該迭代算法是否收斂？該迭代算法是否收斂？ 數(shù)據(jù)流方程的解的含義是什么？數(shù)據(jù)流方程的解的含義是什么？.6第第2章章 數(shù)據(jù)流分析數(shù)據(jù)流分析 為一類數(shù)據(jù)流模式建一個(gè)共同理論框架為一類數(shù)據(jù)流模式建一個(gè)共同理論框架 總結(jié)已討論過的四種數(shù)據(jù)流分析模式總結(jié)已討論過的四種數(shù)據(jù)流分析模式 整理出該框架的一些基本特

5、征或原則整理出該框架的一些基本特征或原則規(guī)范框架中的性質(zhì)空間要滿足的特征規(guī)范框架中的性質(zhì)空間要滿足的特征規(guī)范框架中遷移函數(shù)要滿足的性質(zhì)規(guī)范框架中遷移函數(shù)要滿足的性質(zhì)給出框架的定義給出框架的定義區(qū)分單調(diào)框架和分配框架的區(qū)別區(qū)分單調(diào)框架和分配框架的區(qū)別常量傳播數(shù)據(jù)流模式不是分配的常量傳播數(shù)據(jù)流模式不是分配的.7第第2章章 數(shù)據(jù)流分析數(shù)據(jù)流分析 位向量框架（位向量框架（Bit vector framework） Single-bit representation of each data flow property Separability of solution Data flow propert

6、ies can be evaluated independently Merge operation is a bitwise AND or OR operation Monotonic bit function A bit function cannot negate any bit.8第第2章章 數(shù)據(jù)流分析數(shù)據(jù)流分析 分配性蘊(yùn)涵單調(diào)性的證明分配性蘊(yùn)涵單調(diào)性的證明l1 l2 并且并且f(l1 l2) = f(l1) f(l2) 蘊(yùn)涵蘊(yùn)涵 f(l1) f(l2)證明證明 因?yàn)橐驗(yàn)閒(l2) = f(l1 l2) = f(l1) f(l2) 所以所以 f(l1) f(l2).9第第2章章 數(shù)據(jù)流

7、分析數(shù)據(jù)流分析 常量傳播框架的非分配性常量傳播框架的非分配性說明常量傳播框架沒有分配性的例子說明常量傳播框架沒有分配性的例子B1EXITz = x + yx = 2y = 3B3B2x = 3 y = 2.10第第2章章 數(shù)據(jù)流分析數(shù)據(jù)流分析 整數(shù)格整數(shù)格 表示沒有任何信息可用表示沒有任何信息可用表示可能不是常量表示可能不是常量 3 2 1 0 1 2 3 .11第第2章章 數(shù)據(jù)流分析數(shù)據(jù)流分析 用集合之間的包含關(guān)系來定義部分函數(shù)之間用集合之間的包含關(guān)系來定義部分函數(shù)之間的偏序的偏序 0,1 , 1,1 , 2,1 常函數(shù)常函數(shù)1階乘函數(shù)階乘函數(shù) 0,1 , 1,1 , 2,2 0,1 , 1

8、,1 0,1 0,5 . . . . . . . . . . . . . . . . .12第第2章章 數(shù)據(jù)流分析數(shù)據(jù)流分析 數(shù)據(jù)流方程的求解數(shù)據(jù)流方程的求解 IDEAL，基于程序所有可能執(zhí)行路徑的解，它，基于程序所有可能執(zhí)行路徑的解，它少于或等于流圖上的執(zhí)行路徑少于或等于流圖上的執(zhí)行路徑 Meet Over all Paths(MOP)，不僅匯集了所有可，不僅匯集了所有可能路徑的數(shù)據(jù)流值，而且還包括了那些不可能被能路徑的數(shù)據(jù)流值，而且還包括了那些不可能被執(zhí)行路徑的數(shù)據(jù)流值執(zhí)行路徑的數(shù)據(jù)流值 Maximum Fixed Point(MFP)，由迭代算法得到，由迭代算法得到的解的解 迭代算法得到

9、的迭代算法得到的MFP解總是安全的解總是安全的 MFP MOP IDEAL.13第第2章章 數(shù)據(jù)流分析數(shù)據(jù)流分析 MOP和和MFP的比較的比較 由由MOP的定義，有的定義，有MOPoB4 = (fB3fB1) (fB3fB2) (vENTRY) 在迭代算法在迭代算法(MFP)中，中，如果按如果按B1，B2，B3和和B4的次序的次序訪問結(jié)點(diǎn)，那么訪問結(jié)點(diǎn)，那么MFPoB4 = fB3(fB1(vENTRY) fB2(vENTRY) 說明路徑上較早說明路徑上較早匯合之影響的流圖匯合之影響的流圖B1ENTRYB4B3B2.14第第2章章 數(shù)據(jù)流分析數(shù)據(jù)流分析 敏感性分析敏感性分析 路徑敏感分析路徑敏

10、感分析根據(jù)條件分支語句中的謂詞來計(jì)算不同路徑上的根據(jù)條件分支語句中的謂詞來計(jì)算不同路徑上的信息，它能夠區(qū)分控制流圖上不同路徑的信息信息，它能夠區(qū)分控制流圖上不同路徑的信息 路徑不敏感分析路徑不敏感分析先前討論的都是路徑不敏感分析先前討論的都是路徑不敏感分析 流不敏感分析流不敏感分析語句的執(zhí)行次序?qū)Ψ治鰜碚f無關(guān)緊要，語句的執(zhí)行次序?qū)Ψ治鰜碚f無關(guān)緊要，S1; S2和和S2; S1的分析結(jié)果肯定一樣的分析結(jié)果肯定一樣 流敏感分析流敏感分析先前討論的都是流敏感分析先前討論的都是流敏感分析.15第第2章章 數(shù)據(jù)流分析數(shù)據(jù)流分析 敏感性分析敏感性分析 上下文不敏感分析上下文不敏感分析組合所有調(diào)用點(diǎn)的狀態(tài)信息，對(duì)過程體僅分析一組合所有調(diào)用點(diǎn)的狀態(tài)信息，對(duì)過程體僅分析一次，返回狀態(tài)集合的信息用于所有的返回點(diǎn)次，返回狀態(tài)集合的信息用于所有的返回點(diǎn) 上下文敏感分析上下文敏感分析區(qū)分帶不同上下文信息的不同調(diào)用區(qū)分帶不同上下文信息的不同調(diào)用.16第第2章章 數(shù)據(jù)流分析數(shù)據(jù)流