静态程序分析chapter3 - 数据流分析详述（Reaching Definitions、Live Variables、Available Expressions Analysis）
文章目錄
- 二、
- 數據流分析
- introduction1
- introduction2
- 輸入和輸出狀態
- 轉換函數
- 數據流分析應用
- 1，Reaching Definitions Analysis
- 概述
- 用途
- 分析流程
- 1，抽象
- 2，轉換函數
- 3，控制流處理
- 4，算法實現
- 1，初始化
- 2，第一輪迭代
- 3，第二輪迭代
- 4，第三輪迭代
- 小結
- 2，Live Variables Analysis
- 概述
- 用途
- 分析流程
- 前向分析與后向分析
- 1，抽象
- 2，轉換函數
- 3，控制流處理
- 4，算法實現
- 1，初始化
- 2，第一輪迭代
- 3，第二輪迭代
- 4，第三輪迭代
- 3，Available Expressions Analysis
- 概述
- 用途
- 分析流程
- 1，抽象
- 2，轉換函數
- 3，控制流處理
- must analysis 可能會產生漏報的示例：
- 4，算法實現
- 1，初始化
- 2，第一輪迭代
- 3，第二輪迭代
- 總結
二、
數據流分析
introduction1
??????數據流分析：怎樣的數據？如何流向？在什么上分析？
??????怎樣的數據？我們所關心的感興趣的屬性，比如像之前提到過的變量的符號（抽象和過近似見博客：https://blog.csdn.net/Little_ant_/article/details/118701090），需要對屬性進行抽象。
??????如何流向？一般情況下需要采用過近似，包括轉換函數和控制流處理。通常情況下視問題的不同，需要采用 over-approximate 或 under-approximate，對應的是傾向于 Sound 和 Complete。通常將采用的 over-approximate 的數據流分析稱為 may analysis，將采用的 under-approximate 的數據流分析稱為 must analysis。因為 may analysis 是偏向于 Sound 的，所以它分析的結果可能是真的；而 must analysis 是偏向于 Complete 的，所以它分析的結果一定是真的。
??????在什么上分析？在 CFG 上來分析（CFG是在 IR 上建立的，IR 是由待分析程序得到的），CFG 包括節點和邊。在節點上分析遵循的方法是轉換函數，在邊上的分析遵循的是控制流處理。
introduction2
輸入和輸出狀態
??????針對一條 IR 語句和我們感興趣的屬性，在該語句執行前屬性的狀態稱為輸入狀態；在該語句執行后屬性的狀態稱為輸出狀態。在順序執行時，上一條語句的輸出狀態是下一條語句的輸入狀態。在有分支的情況下，匯合點之前的輸入狀態和多條分支的輸出狀態均有關，需要對這些輸出狀態進行某種操作，具體為哪種操作取決于具體的問題。見下圖：其中 s1、s2、s3 為 IR 語句。
??????在一個數據流分析應用中，在每一個程序點都會關聯一個數據流狀態，這個數據流狀態是我們能夠在該點處能夠觀測到的所關心屬性的抽象之后的全部狀態。比如在對所有變量的符號判斷中，抽象之后的符號域中有 5 個元素：+、-、O、T、⊥。對下圖中程序，一些程序點處的數據流狀態被列出在右側綠色區域中。
??????數據流分析就是在所有程序點的輸入狀態和輸出狀態上，采用某種近似方法（包括轉換函數和控制流處理）對程序進行分析，從而得到針對某種問題的解決方案。
轉換函數
?????? 前向分析：按著程序執行流的方向進行分析，可認為是由輸入得到輸出。后向分析：按著程序執行流的反方向進行分析，可認為是由輸出得到輸入。
??????轉換函數：描述某一條語句 s 的輸入狀態 IN[s] 和輸出狀態 OUT[s] 之間的轉換關系。在前向分析中，描述如何通過 IN[s] 得到 OUT[s]；在后向分析中，描述如何通過 OUT[s] 得到 IN[s]。如下圖：
??????存在一個基本塊 B ，它包含有語句 s1、s2、s3 … sn 。
??????那么在基本塊之內有：IN[s2] = OUT[s1]、IN[s3] = OUT[s2]、IN[s4] = OUT[s3] …即之前提到過的 “在順序執行時，上一條語句的輸出狀態是下一條語句的輸入狀態”。
??????如果 B 的前驅為 P1 和 P2，后繼為 S1 和 S2 ，在基本塊之間有：IN[B] = IN[s1]、OUT[B] = OUT[sn] 。從而得到 OUT[B] 和 IN[B] 的關系與 B 中的所有語句的轉換函數有關，并且在前向分析中： B 的輸入狀態 IN[B] 和它的所有前驅的輸出狀態 OUT[P] 有關系；后向分析中：B 的輸出狀態 OUT[B] 和它的所有后繼的輸入狀態 IN[S] 有關系。在下圖中，淡黃色部分表示前向分析，淡紅色部分表示后向分析，Λ表示 meet operator。
數據流分析應用
??????下面介紹三個基本的數據流分析應用示例。
1，Reaching Definitions Analysis
概述
??????注意在這里 definition 的意思不是定義，而是賦值/初始化。
??????Reaching Definition Analysis ：A definition d at program point p reaches a point q if there is a path from p to q such that d is not “killed” along that path . 中文翻譯為：在程序點 p 處，存在一個賦值語句 d 表示對某個變量進行賦值，如果在通往之后的程序點 q 之間的任意一條路徑上，d 是存活的（即該變量并沒有被重新賦值，仍然是之前的那個值），那么認為在 p 處的賦值語句 d 能夠到達 q 點（即 d 在 q 處依然是有效的）。
??????Reaching Definitions Analysis是，針對程序中的每個賦值語句（d, v = C），分析出它可能到達的所有程序點（通常是一條指令的前后處）。等價說法是，RDA是針對程序中的每個程序點(通常是一條指令的前后處)，分析出可能到達此處的所有賦值語句（d, v = E）。
??????可以看出，它屬于 may analysis。因為只要存在一條路徑上沒有對變量 v 重新賦值，就認為原來的賦值語句 v = C 是有效地，但是，可能會在別的路徑上對 v 重新賦值（令 v = C1）。所以并不能確定該賦值語句 100% 能夠到達之后的程序點，這取決于程序執行時走的哪條路徑。may analysis 采用的是過近似，即哪怕有99條路徑上變量 v 都被賦值/初始化了，但是有一條路徑上沒有，那這一條路徑也是需要考慮的，因為程序是有可能走這條沒有被賦值/初始化的路徑的，過近似的特點就是不放過任何一個程序執行時可能的行為（不放過任何一條路徑），所以它得到的結果有可能是真的。
用途
??????可用于死代碼去除。對于某條賦值語句（d, v = C）,它可以到達的程序點假設為 p1、p2、p3 … 那么如果在這些程序點處，發現變量 v 并沒有被使用過，從而得出該賦值語句是一條無用代碼，刪除該賦值語句 d 做代碼優化。
??????簡單的內存泄露檢查。原理是類似的，對于動態內存分配指令（d，v = new …）,判斷在該語句所有可達的程序點處，是否存在有 delete 語句，如果這些可達程序點處均沒有 delete 語句，則認為發生了內存泄露。
??????簡單的錯誤檢測。我們首先在 entery 塊中對程序中的變量引入一條條假的賦值/初始化語句（即這些變量還沒有被賦值/初始化），如果在之后某條假賦值語句的的可達程序點處，發現這個變量被使用了，那么有可能發生了錯誤（變量在賦值/初始化前被使用）。“可能” 意味著不確定，因為有可能別的路徑上存在這個變量的賦值/初始化語句。
分析流程
??????可以發現：對于 RDA，在程序的第一條語句之前，還沒有任何語句被執行，那么在此處所有賦值語句都是不可達的。而在程序的最后一條語句之后，所有的賦值語句是否可達并不確定，所以我們采用前向分析，從第一條語句至最后一條語句。
1，抽象
??????抽象：因為我們關心的是程序中所有變量的賦值語句都能到達哪些程序點，那么就需要對這些賦值語句進行抽象。這里采用位向量來表示。假設程序中有賦值語句100個，那么需要有100個比特位來表示，第一位表示第一條賦值語句是否可達，若可達置為1，不可達置為0。那么在第一個程序點（程序的第一條語句之前）處，置這100個比特位均為0，表示均不可達。
2，轉換函數
??????轉換函數：在前向分析中的轉換函數是計算如何從輸入狀態得到輸出狀態，我們以一條語句來進行分析。
??????假設存在一條語句 D：v = x op y ，這一條語句使用變量 x 和 y 對變量 v 賦值。重申：我們分析的是程序中所有賦值語句，判斷它們在各個程序點處的可達情況。所以得出：在語句 D 執行之后的程序點處，賦值語句 D 中變量 v 是可達的，而在程序中其余的對 v 的賦值語句在此是不可達的。而對于變量 x、y，仍然保持在語句 D 執行之前的可達性。 新的賦值語句 D 的比特位在此設置為 1，其余的對 v 的賦值語句全設置為 0.
??????轉換函數用公式表示為：OUT[B] = genB U (IN[B] - killB) ??????U表示或操作。
??????B表示一個基本塊，這個公式做兩件事：令其他地方的賦值語句不可達，設置當前的新賦值語句可達。當然對于每一條語句也是一樣適用的。下圖計算程序中的基本塊的 genB 和 killB:
3，控制流處理
??????控制流處理：在有分支的情況下，假設基本塊 B 的兩個前驅為 P1 和 P2。現在討論IN[B]，如果OUT[P1]中的某些賦值語句的變量是可達的，而在OUT[P2]中的這些賦值語句的變量是不可達的，根據 RDA 的定義，只要有一條路徑上某個變量是可達的，就認為它是可達的。所以應該采用或操作，1 或 0 = 1。
??????控制流處理用公式表示為：IN[B] = U OUT[P]（p is a predecessor of B ）
4，算法實現
??????在抽象、轉換函數和控制流處理之后，關于 RDA 的算法如下圖：
??????這個算法是一個迭代算法，可以當做模板應用于別的數據流分析中。算法的輸入是 CFG ，輸出是判斷每一個程序點（這里以基本塊為單位）處所有賦值語句是否可達。
1，初始化
??????初始化語句第一步，令 entry 的輸出狀態為空，這個之前講過，需要從語義上來理解：因為此處之前沒有任何語句，所以在這里所有賦值語句均是不可達的。
??????初始化語句第二步，令除了 entry 之外的其他基本塊的輸出狀態也為空，為空的原因后面會講到，總之 may analysis 通常都會初始化為空集，用符號⊥來表示，稱為 bottom。而 must analysis 剛好相反，常被初始化為滿集，用符號 T 來表示，稱為 top。
??????while 循環的判定條件為任何一個基本塊的 OUT 集合發生改變時，循環主體是對除了 entry 塊的其余基本塊做：控制流處理和轉換函數的實現。至于這個循環一定會停止的原因后面再講，我們先通過一個例子熟悉這個迭代算法，見下圖：一共有8個賦值語句，5個基本塊，緊接著會對算法執行流程做說明。
??????初始化：初始化的結果如上圖的黑色字體來表示，按照算法描述，所有的 OUT 均初始化為 0000 0000。
2，第一輪迭代
??????第一輪迭代：執行循環體，用紅色字體來表示執行結果，如上圖顯示的是 IN[B1] = OUT[entry] = 0000 0000。
前向分析繼續往下走，按照轉換函數計算出：OUT[B1] = 1100 0000 U （0000 0000 - 0001 1010）= 1100 0000。這里的減法運算為：1-1=0、1-0=1、0-1=0、0-0=0。
IN[B2] = OUT[B4] U OUT[B1] = 0000 0000 U 1100 0000 = 1100 0000;
OUT[B2] = 0011 0000 U （1100 0000 - 0100 0000）= 1011 0000。
IN[B3] = OUT[B2];
OUT[B3] = 0000 0010 U （1011 0000 - 1000 1000）= 0011 0010。
IN[B4] = OUT[B2];
OUT[B4] = 0000 1100 U （1011 0000 - 1000 0011）= 0011 1100。
IN[B5] = OUT[B4] U OUT[B3] = 0011 1100 U 0011 0010 = 0011 1110;
OUT[B5] = 0000 0001 U （0011 1110 - 0000 0100）= 0011 1011。
??????根據算法的循環判定條件，存在有基本塊的 OUT 發生了變化（事實上所有基本塊的 OUT 都發生了變化，不再是初始的 0000 0000了），那么將進入第二輪迭代。第一輪迭代執行完畢的結果如下圖：
3，第二輪迭代
??????第二輪迭代：在上圖第一輪的執行結果上進行，IN[B1]保持不變，IN[B1] = OUT[entry] = 0000 0000。
前向分析繼續往下走，按照轉換函數計算出：OUT[B1] = 1100 0000 U （0000 0000 - 0001 1010）= 1100 0000。
IN[B2] = OUT[B4] U OUT[B1] = 0011 1100U 1100 0000 = 1111 1100;
OUT[B2] = 0011 0000 U （1111 1100 - 0100 0000）= 1011 1100。
IN[B3] = OUT[B2];
OUT[B3] = 0000 0010 U （1011 1100 - 1000 1000）= 0011 0110。
IN[B4] = OUT[B2];
OUT[B4] = 0000 1100 U （1011 1100 - 1000 0011）= 0011 1100。
IN[B5] = OUT[B4] U OUT[B3] = 0011 1100 U 0011 0110 = 0011 1110;
OUT[B5] = 0000 0001 U （0011 1110 - 0000 0100）= 0011 1011。
??????根據算法的循環判定條件，存在有基本塊的 OUT 發生了變化（B2，B3），那么將進入第三輪迭代。第二輪迭代執行完畢的結果如下圖：
4，第三輪迭代
??????第三輪迭代：在上圖第二輪的執行結果上進行，IN[B1]保持不變，IN[B1] = OUT[entry] = 0000 0000。
前向分析繼續往下走，按照轉換函數計算出：OUT[B1] = 1100 0000 U （0000 0000 - 0001 1010）= 1100 0000。
IN[B2] = OUT[B4] U OUT[B1] = 0011 1100 U 1100 0000 = 1111 1100;
OUT[B2] = 0011 0000 U （1111 1100 - 0100 0000）= 1011 1100。
IN[B3] = OUT[B2];
OUT[B3] = 0000 0010 U （1011 1100 - 1000 1000）= 0011 0110。
IN[B4] = OUT[B2];
OUT[B4] = 0000 1100 U （1011 1100 - 1000 0011）= 0011 1100。
IN[B5] = OUT[B4] U OUT[B3] = 0011 1100 U 0011 0110 = 0011 1110;
OUT[B5] = 0000 0001 U （0011 1110 - 0000 0100）= 0011 1011。
??????根據算法的循環判定條件，所有基本塊的 OUT 都沒有發生變化，迭代停止，算法執行完畢。第三輪迭代執行完畢的結果如下圖：
??????此時那些綠色字體表示的就是算法的最終結果，我們在每一個程序點處得到了所有賦值語句的最終狀態（是否可達）。
小結
??????數據流分析：我們首先在每一個程序點處關聯一個數據流值，這個數據流值是對該程序點處可以觀測到的所有可能的程序狀態做抽象得到的 ；然后對所有程序點處應用某種近似（over-appro or under-appro）方法得到某種結論的分析手段。（可直白的認為：在抽象域上，采用轉換函數和控制流處理對程序分析并得出結論）
??????RDA可應用于死代碼消除，在上面例子中，對于賦值語句 D1，它的可達程序點為 OUT[B1] 和 OUT[B2]。而在 B1 和 B2 兩個基本塊中可以發現 D1 中的變量 x 并沒有被使用過，所以賦值語句 D1 在這個程序就是一條死代碼，于程序而言，它的存在沒什么意義，應予以刪除。
??????迭代為什么能停止？
??????可以發現：根據轉換函數的公式，一個基本塊中的 genB 和 killB 在每一輪的迭代中是不會發生變化的，因為程序沒有改變，只有 IN[B] 發生變化，OUT[B] 才會發生變化，而由初始化可知，所有程序點的 OUT 是初始化為空集的（bottom），所以 OUT[B] 只能增長或不變，而不會下降，即不會從 1 變為 0。這些可能增長的狀態（從 0 變為 1）在之后的迭代中會流向 IN[B] 并生成新的 OUT[B] （這里忽略掉控制流處理，因為它也不能將 1 變為 0）。這個新的 OUT[B] 因為 genB 和 killB 始終是不變的，而它又可能保留有更多的狀態，所以它比之前會包含更多的 1 。而程序之中的賦值語句數量是有限的，那么最多當 OUT[B] 增長為滿集（全為1）時，程序的 OUT 集就不再發生變化了，那么算法就會停止。當算法的所有 OUT 集不發生變化時，稱這個狀態為該算法的不動點（fixed point）。
2，Live Variables Analysis
概述
??????RDA是對賦值語句的可達性進行判定，應用于死代碼消除中的判斷某個變量在程序點是否被使用便是LVA的工作，這兩者結合起來便構成了死代碼消除。
??????LVA ：Live variables analysis tells whether the value of variable v at program point p could be used along some path in CFG starting at p. If so, v is live at p; otherwise, v is dead at p. 在程序點 p 處，一個變量 v 的值如果被 CFG 中在 p 之后直到程序結束的任何一條路徑上被使用，則認為 v 在 p 處是存活的，否則為死亡的。
??????注意：這里指的是在程序點 p 處變量 v 的值會不會在之后被使用，如果變量在程序點之后直到程序結束的某一條路徑上，先是被重新賦值，然后再被使用，那么顯而易見，在 p 處變量 v 是死亡的。
??????LVA 在每一個程序點處判斷程序中所有變量的存活性，可以看出，它也屬于 may analysis ，因為在某個程序點之后，只要存在一條路徑上某個變量是存活的，就認為該變量存活，但是在程序中別的路徑上該變量可能是死亡的，所以并不能確定該變量是100%存活的，這取決于程序執行時走的哪條路徑。may analysis 采用的是過近似，即哪怕有99條路徑上變量 v 都是存活的，但是有一條路徑上沒有，那這一條路徑也是需要考慮到的，因為程序執行時是有可能走這條路徑的，過近似的特點就是不放過任何一個程序執行時可能的行為（不放過任何一條路徑），所以它得到的結果有可能是真的。
用途
??????LVA 可用于寄存器分配上。當所有寄存器上都存在數據時，而我們又需要使用一個寄存器，就可以采用 LVA 淘汰掉一個寄存器，因為這個寄存器中的數據值一直到程序結束時都不會被使用。
分析流程
??????對于 RDA ，它是判斷在程序點 p 處的賦值語句在之后的程序點上的可達性，是依據于當前的情況去判斷之后程序點上的狀態，采用的是前向分析；而 LVA 是根據在 p 處之后的路徑上判斷在 p 處的變量是否被使用，從而判斷在 p 處變量的存活性，就是說：它是從后往前分析的，通過 p 后面的情況得到 p 處的結果。
??????并且可以可發現：所以對于 LVA ，在程序的最后一條語句之后，所有變量在此處都是死亡的，因為后面不會有語句執行了，也就不存在變量被使用了；而在程序的第一條語句之前，我們無法判斷在此處變量的存活性，所以我們采用后向分析。
前向分析與后向分析
??????對于如下代碼：
a = 1; b = 2; c = a + 8; b = 9; d = b + c;??????通過前向分析，在第二條語句執行之后：在 RDA 中，我們可以輕易得到，賦值語句 a =1 和 b = 2 在此處是可達的。而在 LVA 中，因為沒有執行后面的三行代碼，我們并不清楚在此處所有變量的存活性，程序必須走完最后一行才可以判斷，所以需要采用后向分析。
1，抽象
??????抽象：因為我們關心的是程序中所有變量在所有程序點的存活性，那么就需要對這些變量進行抽象。這里采用位向量來表示。類似的：假設程序中有變量100個，那么需要有100個比特位來表示，第一位表示第一個變量是否存活，若存活置為1，死亡置為0。那么在最后一個程序點（程序的最后一條語句之后）處，置這100個比特位均為0，表示均不存活。
2，轉換函數
??????轉換函數：在后向分析中的轉換函數是計算如何從輸出狀態得到輸入狀態。
??????要判斷一個變量在程序點 p 處的存活性，首先需要判斷之后的基本塊中該變量是否被使用，其次需要注意的是只有在重新賦值語句之前被使用才表示在 p 處存活，我們來分析一下可能存在的語句情況：
??????假設存在有三個基本塊，其中基本塊 P 是 B 的前驅，基本塊 S1 是 B 后繼。變量 v 在 P 中被賦值/初始化，S1 是程序中最后一個基本塊（除過 Exit），在 S1 中變量 v 被使用。下面需要針對 B 中可能存在的情況對 IN[B] 處變量 v 的存活性進行討論：
若：
??????B中語句為：k = n ;??????按照定義，在 IN[B] 處變量 v 存活。
??????B中語句為：k = v ;??????按照定義，在 IN[B] 處變量 v 存活。
??????B中語句為：v = 2 ;??????因為之前的 v 還沒有被使用，就對 v 重新賦值，所以在 IN[B] 處變量 v 死亡。
??????B中語句為：v = v - 1 ;??????因為先執行等式右邊的表達式再對 v 重新賦值，即使用在賦值之前，故在 IN[B] 處變量 v 存活。
??????B中語句為：v = 2 ; k = v ;??????重新賦值在使用之前，故在 IN[B] 處變量 v 死亡。
??????B中語句為：k = v ; v = 2 ;??????和上面剛好相反，使用在重新賦值之前，故在 IN[B] 處變量 v 存活。
??????得出轉換函數為：IN[B] = useB U (OUT[B] - redefB)
??????U 表示或操作。只要存在 redefinition 就要減去，之后再加上 “used before redefinition” 的情況（通過 U 操作）。OUT[B] 表示沒有被重新賦值的其他變量的狀態。
3，控制流處理
??????控制流處理：在有分支的情況下，假設基本塊 B 的兩個后繼為 S1 和 S2。現在討論OUT[B]，如果IN[S1]中的某些變量是存活的，而在IN[S2]中的這些變量是死亡的，根據 RDA 的定義，只要在 B 之后有一條路徑上某個變量是存活的，就認為它是存活的。所以應該采用或操作，1 或 0 = 1。
??????控制流處理用公式表示為：OUT[B] = U IN[S]（S is a successor of B ）
??????關于轉換函數和控制流處理也可以參考下圖：其中 defB 和上面的 redefB 意思相同。
4，算法實現
??????在抽象、轉換函數和控制流處理之后，關于 LVA 的算法如下圖：
??????這個算法也是一個迭代算法，算法的輸入是 CFG ，輸出是判斷每一個程序點（這里以基本塊為單位）處所有變量是否存活。
1，初始化
??????初始化語句第一步，令 exit 的輸出狀態為空，這個之前講過，需要從語義上來理解：因為此處之后沒有任何語句，所以在這里所有變量均是死亡的。
??????初始化語句第二步，令除了 exit 之外的其他基本塊的輸出狀態也為空，為空的原因后面會講到，總之 may analysis 通常都會初始化為空集，用符號⊥來表示，稱為 bottom。而 must analysis 剛好相反，常被初始化為滿集，用符號 T 來表示，稱為 top。
??????while 循環的判定條件為任何一個基本塊的 IN 集合發生改變時，循環主體是對除了 exit 塊的其余基本塊做：控制流處理和轉換函數的實現。我們先通過一個例子熟悉這個算法，見下圖：一共有7個變量，5個基本塊，緊接著會對算法執行流程做說明。
??????初始化：初始化的結果如上圖的黑色字體來表示，按照算法描述，所有的 IN 均初始化為 000 0000。
2，第一輪迭代
??????第一輪迭代：執行循環體，用紅色字體來表示執行結果，如上圖顯示的是 OUT[B5] = IN[exit] = 000 0000。
后向分析繼續往下走，按照轉換函數計算出：IN[B5] = 000 1000 U（000 0000 - 001 0000）= 000 1000。這里的減法運算為：1-1=0、1-0=1、0-1=0、0-0=0。
OUT[B3] = IN[B5] = 000 1000;
IN[B3] = 100 0000 U （000 1000 - 100 0000）= 100 1000。
OUT[B4] = IN[B5] U IN[B2] = 000 1000 U 000 0000 = 000 1000;
IN[B4] = 010 0000 U （000 1000 - 100 0100）= 010 1000。
OUT[B2] = IN[B3] U IN[B4] = 100 1000 U 010 1000 = 110 1000;
IN[B2] = 000 0001 U （110 1000 - 010 0010）= 100 1001。
OUT[B1] = OUT[B4] = IN[B2] = 100 1001。
IN[B1] = 001 1100 U （100 1001 - 110 0000）= 001 1101。
??????根據算法的循環判定條件，存在有基本塊的 IN 發生了變化（事實上所有基本塊的 IN 都發生了變化，不再是初始的 000 0000了），那么將進入第二輪迭代。第一輪迭代執行完畢的結果如下圖：
3，第二輪迭代
??????第二輪迭代：在上圖第一輪的執行結果上進行，OUT[B5] 保持不變， OUT[B5] = IN[exit] = 000 0000。后向分析繼續往下走，按照轉換函數計算出：IN[B5] = 000 1000 U（000 0000 - 001 0000）= 000 1000。
OUT[B3] = IN[B5] = 000 1000;
IN[B3] = 100 0000 U （000 1000 - 100 0000）= 100 1000。
OUT[B4] = IN[B5] U IN[B2] = 000 1000 U 100 1001 = 100 1001;
IN[B4] = 010 0000 U （100 1001 - 100 0100）= 010 1001。
OUT[B2] = IN[B3] U IN[B4] = 100 1000 U 010 1001 = 110 1001;
IN[B2] = 000 0001 U （110 1001 - 010 0010）= 100 1001。
OUT[B1] = OUT[B4] = IN[B2] = 100 1001。
IN[B1] = 001 1100 U （100 1001 - 110 0000）= 001 1101。
??????根據算法的循環判定條件，存在有基本塊的 IN 發生了變化（B4），那么將進入第三輪迭代。第二輪迭代執行完畢的結果如下圖：
4，第三輪迭代
??????第三輪迭代：在上圖第二輪的執行結果上進行，OUT[B5] 保持不變， OUT[B5] = IN[exit] = 000 0000。后向分析繼續往下走，按照轉換函數計算出：IN[B5] = 000 1000 U（000 0000 - 001 0000）= 000 1000。
OUT[B3] = IN[B5] = 000 1000;
IN[B3] = 100 0000 U （000 1000 - 100 0000）= 100 1000。
OUT[B4] = IN[B5] U IN[B2] = 000 1000 U 100 1001 = 100 1001;
IN[B4] = 010 0000 U （100 1001 - 100 0100）= 010 1001。
OUT[B2] = IN[B3] U IN[B4] = 100 1000 U 010 1001= 110 1001;
IN[B2] = 000 0001 U （110 1001 - 010 0010）= 100 1001。
OUT[B1] = OUT[B4] = IN[B2] = 100 1001。
IN[B1] = 001 1100 U （100 1001 - 110 0000）= 001 1101。
??????根據算法的循環判定條件，所有基本塊的 IN 都沒有發生變化，迭代停止，算法執行完畢。第三輪迭代執行完畢的結果如下圖：
??????此時那些綠色字體表示的就是算法的最終結果，我們在每一個程序點處得到了所有變量的存活狀態。
3，Available Expressions Analysis
概述
??????AEA ：An expression x op y is available at program point p if (1) all paths from the entry to p must pass through the evaluation of x op y, and (2) after the last evaluation of x op y, there is no redefinition of x or y 。在程序點 p 處，一個表達式 x op y （IR的值 ）是否有效取決于：（1）所有從 entry 到 p 處的路徑都必須執行 x op y 表達式。（2）在每一條路徑最后一次執行 x op y 后，都不能重新對 x 或者 y 賦值。
??????AEA 在每一個程序點處判斷程序中所有表達式的有效性，可以看出，它屬于 must analysis ，因為從 entry 到 p 處的路徑都必須執行 x op y 表達式，并且都不能重新對 x 或者 y 賦值，must analysis 采用的是 under-appro，它要求所有路徑上的行為都必須符合要求，哪怕有一條路徑不符合要求也不行，相對的是 may analysis ，它要求只要有一條路徑符合要求就可以了。從這里能夠看出，may analysis 在控制流處理時一般取或操作（1 op 0 = 1），而 must analysis 應該取與操作（1 op 0 = 0）。所以 must analysis 得到的結果必然是真的，缺點是可能存在有漏報。
用途
??????用作優化：在程序點 p 處，可以用 p 之前的某一條路徑上最后一次執行 x op y 的結果來代替表達式 x op y ，這樣就不需要在 p 處重新計算表達式 x op y 的值了 。（類似于 C 中的 #define ??x op y ? number） 下面這個示例形象地說明了 AEA 的用途，建議閱讀完分析流程的前三小節之后食用。
??????圖片的左邊表示在最后一條語句之前表達式 e16 * x 是有效的。這個是由 AEA 的定義得出的結論，雖然 a 的值與 b 的值不相等，但是不妨礙做右側的編譯優化：這個優化是在表達式 e16 * x 有效的程序點處，將該表達式統一用一個臨時變量 t 做替換，不再保留原來的變量 a、b、c ，當程序執行時，如果走左邊的路徑，原來 c 的值等于 b 的值，如果走右邊的路徑，原來 c 的值等于 a 的值。也就不要求 a 的值等于 b 的值啦。
分析流程
??????對于 AEA ，它是判斷從 entry 開始到當前程序點之間所有表達式的在當前程序點的有效性，應該采用前向分析。
??????并且可以發現：對于 AEA ，在程序的第一條語句之前，沒有任何表達式被執行，所以在此處所有表達式都不是有效的；而在程序的最后一條語句之后，我們無法判斷在此處表達式的有效性，所以我們采用前向分析。
1，抽象
??????抽象：因為我們關心的是程序中所有表達式在所有程序點的有效性，那么就需要對這些表達式進行抽象。這里采用位向量來表示。類似的：假設程序中有表達式100個，那么需要有100個比特位來表示，第一位表示第一個表達式是否有效，若有效置為1，否則置為0。那么在第一個程序點（程序的第一條語句之前）處，置這100個比特位均為0，表示均不有效。
2，轉換函數
??????轉換函數：在前向分析中的轉換函數是計算如何從輸入狀態得到輸出狀態，我們以一條語句來進行分析。
??????假設存在一條語句 D：a = x op y ，這一條語句使將表達式 x op y 的結果賦給 a。所以得出：在語句 D 執行之后的程序點處，新的表達式 x op y 肯定是有效的，而所有含有 a 的表達式在此時均不是有效的，因為 a 在此處被重新賦值了。。 新的表達式 x op y 的比特位在此設置為 1，其余和 a 相關的表達式全設置為 0.
??????轉換函數用公式表示為：OUT[B] = genB U (IN[B] - killB) ??????U表示或操作。
??????B表示一個基本塊，genB 表示符合要求的有效表達式，而 killB 表示與被重新賦值的變量相關的表達式。公式對于每一條語句也是一樣適用的。
3，控制流處理
??????控制流處理：在有分支的情況下，假設基本塊 B 的兩個前驅為 P1 和 P2。現在討論 IN[B] ，如果 OUT[P1] 中的某些表達式是有效的，而在 OUT[P2] 中的這些表達式不是有效的，根據 AEA 的定義 “必須保證每一條路徑都是有效的”，認為 IN [B] 不是有效的。所以應該采用與操作，1 與 0 = 0。
??????控制流處理用公式表示為：IN[B] = ∩ OUT[P]（P is a predecessor of B ）
must analysis 可能會產生漏報的示例：
??????上圖左側得到在最后一條語句之前該表達式不是有效的無可厚非，那如果恰好是右側的那一種情況呢？雖然它實際上是有效的，但是數據流分析認為它不是有效的，這便是產生了漏報。
4，算法實現
??????在抽象、轉換函數和控制流處理之后，關于 AEA 的算法如下圖：
??????這個算法是一個迭代算法，算法的輸入是 CFG ，輸出是判斷每一個程序點（這里以基本塊為單位）處所有表達式是否有效。
1，初始化
??????初始化語句第一步，令 entry 的輸出狀態為空，這個之前講過，需要從語義上來理解：因為此處之前沒有任何語句，所以在這里所有表達式均不是有效的。
??????初始化語句第二步，令除了 entry 之外的其他基本塊的輸出狀態也為滿，為滿的原因后面會講到，總之 may analysis 通常都會初始化為空集，用符號⊥來表示，稱為 bottom。而 must analysis 剛好相反，常被初始化為滿集，用符號 T 來表示，稱為 top。
?????? 在這里多講一句，前兩個例子中 1 op 0 = 1，所以不難看出總體上是從 0 → 1進行的；而 AEA 是 must analysis，1 op 0 = 0，總體上是從 1 → 0 進行的，所以需要將所有的 OUT 初始化為滿集。也可以理解為 may analysis 是單調遞增的，而 must analysis 是單調遞減的。而它的算法停止條件和 may analysis是類似的，因為must 是遞減的，所以最多減小到全為 0 的時候這個算法就停止。
??????while 循環的判定條件為任何一個基本塊的 OUT 集合發生改變時，循環主體是對除了 entry 塊的其余基本塊做：控制流處理和轉換函數的實現。我們先通過一個例子熟悉這個迭代算法，見下圖：一共有5個表達式，5個基本塊，緊接著會對算法執行流程做說明。
??????初始化：初始化的結果如上圖的黑色字體來表示，按照算法描述，entry 的 OUT 初始化為 00000，其余的 OUT 初始化為 11111。
2，第一輪迭代
??????第一輪迭代：執行循環體，用紅色字體來表示執行結果，如上圖顯示的是 IN[B1] = OUT[entry] = 00000。
前向分析繼續往下走，按照轉換函數計算出：OUT[B1] = 10000 U （00000 - 00101）= 10000。這里的減法運算為：1-1=0、1-0=1、0-1=0、0-0=0。
IN[B2] = OUT[B4] ∩ OUT[B1] = 11111 ∩ 10000 = 10000;
OUT[B2] = 01010 U （10000 - 10000）= 01010。
IN[B3] = OUT[B2];
OUT[B3] = 00001 U （01010 - 01000）= 00011。
IN[B4] = OUT[B2];
OUT[B4] = 00110 U （01010 - 00010）= 01110。
IN[B5] = OUT[B4] ∩ OUT[B3] = 01110 ∩ 00011 = 00010;
OUT[B5] = 01010 U （00010 - 00101）= 01010。
??????根據算法的循環判定條件，存在有基本塊的 OUT 發生了變化（事實上所有基本塊的 OUT 都發生了變化，不再是初始的 11111了），那么將進入第二輪迭代。第一輪迭代執行完畢的結果如下圖：
3，第二輪迭代
??????第二輪迭代：在上圖第一輪的執行結果上進行，IN[B1]保持不變，IN[B1] = OUT[entry] = 00000。
前向分析繼續往下走，按照轉換函數計算出：OUT[B1] = 10000 U （00000 - 00101）= 10000。
IN[B2] = OUT[B4] ∩ OUT[B1] = 01110∩ 10000 = 00000;
OUT[B2] = 01010 U （00000 - 10000）= 01010。
IN[B3] = OUT[B2];
OUT[B3] = 00001 U （01010 - 01000）= 00011。
IN[B4] = OUT[B2];
OUT[B4] = 00110 U （01010 - 00010）= 01110。
IN[B5] = OUT[B4] ∩ OUT[B3] = 01110 ∩ 00011 = 00010;
OUT[B5] = 01010 U （00010 - 00101）= 01010。
??????根據算法的循環判定條件，此時沒有基本塊的 OUT 發生了變化，迭代停止，算法執行完畢。第二輪迭代執行完畢的結果如下圖：
??????此時那些藍色字體表示的就是算法的最終結果，我們在每一個程序點處得到了所有表達式的有效性。
總結
??????本文首先講述了數據流分析的基本方法，并通過三個經典的示例來闡述了如何對一個具體地問題采用數據流分析。在這三個示例中，我詳細介紹了實現數據流分析的具體細節，比如：抽象（根據問題來選擇被抽象的對象），轉換函數（一般通過一個語句/基本塊得到其一般形式），控制流處理（通過問題來確定采用 與 or 或）。關于采用前向分析還是后向分析的原因，應該采用 may 還是 must 的原因，在邊界處（entry 和 exit）的初始化值和別的初始化語句應該為空還是滿的原因在文中也多次提到，不再贅述。
??????簡單在聊一下對一個問題做數據流分析的流程：
??????首先對問題進行分析，分析之后能夠得到 如何抽象，采用前向還是后向，采用 may 還是 must 和在邊界處的初始化值，然后在確定了采用 may 或 must 之后，就可以得到 除邊界外的初始化語句值 和 控制流處理采用 與 or 或。而轉換函數是需要另外對具體的語句/基本塊來分析得到的。
??????三個應用的差異性比較見下圖：
??????后面會繼續介紹靜態程序分析的理論基礎-格理論。未完待續~
??????行文倉促，文章較長，若存在筆誤，抱歉！
總結
以上是生活随笔為你收集整理的静态程序分析chapter3 - 数据流分析详述（Reaching Definitions、Live Variables、Available Expressions Analysis）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 静态程序分析chapter2 - IR（
- 下一篇： 静态程序分析chapter4 - 基于格