斷斷續(xù)續(xù)看了南京大學(xué)的靜態(tài)分析課程，總結(jié)一下，先貼一些資源
課程鏈接：
https://pascal-group.bitbucket.io/teaching.html。
作業(yè)內(nèi)容：
https://tai-e.pascal-lab.net/en/pa1.html#_1-assignment-objectives
作業(yè)工程：
https://github.com/pascal-lab/Tai-e-assignments
關(guān)于Soot的資料：
https://www.brics.dk/SootGuide/sootsurvivorsguide.pdf
https://github.com/soot-oss/soot/wiki/Tutorials
Soot官方：
https://github.com/soot-oss/soot
下載soot jar包：
https://soot-build.cs.uni-paderborn.de/public/origin/master/soot/soot-master/
國內(nèi)關(guān)于Soot的應(yīng)用：
https://github.com/wh1t3p1g/tabby

簡單理解靜態(tài)分析就是在不運(yùn)行程序的情況下對程序進(jìn)行分析。靜態(tài)分析的作用包括判斷程序是否安全（空指針引用、內(nèi)存泄漏、信息泄漏等）、增強(qiáng)對項(xiàng)目的理解（調(diào)用層次結(jié)構(gòu)）、編譯器優(yōu)化（死代碼消除）等。但是靜態(tài)分析并不能給出具體的答案：是或否。也就是它不能肯定一定安全、一定不存在死代碼等（賴斯定理）。靜態(tài)分析可以給出的是可靠性（soundness）或完整性（completeness），對應(yīng)的是漏報(bào)率（false negatives）或誤報(bào)率（false positives）。這也涉及到在確?？煽啃缘耐瑫r(shí)，在分析精度和分析速度之間做平衡。

另外，課程用兩個(gè)詞來概括大多數(shù)的靜態(tài)分析：Abstraction + Over-approximation。中文翻譯就是：抽象、過度近似。Abstraction把具體值抽象成了符號表示。

Abstraction

Transfer functions

Control Flows

1. IR

IR（Intermediate Representation，中間表示），表示了高級語言的全部信息。所謂的編譯過程是將高級語言轉(zhuǎn)換成機(jī)器指令的過程，大致如下：

Source Code -> Scanner —(Tokens)—> Parser —(AST)—> Type Checker —(Decorated AST)—> Translator —(IR)—> Code Generator -> Machine Code

Scanner階段為詞法分析（Lexical Analysis），通過正則表達(dá)式（Regular Expression）
Parser階段為語法分析（Syntax Analysis），通過上下文無關(guān)文法（Context-Free Grammar）
Type Checker階段為語義分析（Semantic Analysis），通過屬性文法（Attribute Grammar）
經(jīng)過上述過程，會將源代碼轉(zhuǎn)換成IR的形式。IR之前的步驟被稱為前端frontend?？梢钥吹絀R和AST階段相比，更貼近機(jī)器碼的形式，并且包含控制流信息，所以IR階段是更適合進(jìn)行靜態(tài)分析的階段。

AST vs IR

3AC

IR的基本格式是三地址碼格式（3-Address Code ，3AC）。三地址碼的要求是：在一條指令的右邊最多有一個(gè)操作符?！暗刂贰笨梢岳斫鉃樵?，每個(gè)指令里面包含三種元素：Name、Constant、Compiler-generated temporary，即名稱、常量和臨時(shí)變量。

t2 = a + b + 3 // 不符合三地址碼要求

// 三地址碼格式
t1 = a + b // Name: a,b
t2 = t1 + 3 // Constant:3; Compiler-generated temporary:t1, t2

// 其他常見三地址碼,  x,y,z (地址，可以是三種元素之一);
x = y bop z //bop:二進(jìn)制算術(shù)或邏輯運(yùn)算
x= uop y  // uop:一元運(yùn)算(減、反、轉(zhuǎn)換)
goto L // L:表示程序位置的標(biāo)簽
if x goto L // 跳轉(zhuǎn)
if x rop y goto L // rop:關(guān)系操作符(>，<，==，>=，<=等)

IR是語言無關(guān)的，課程中采用的IR的實(shí)現(xiàn)是Jimple。Soot中的IR實(shí)現(xiàn)包括：Baf, Jimple, Shimple和Grimp。簡單來看一個(gè)Jimple例子

// 源代碼形式
public static void main(String[] args){
    int x=0;
    for(int i=0; i<10; i++){ x=x+1; }
} 

// Jimple三地址碼形式
public static void main(String[] args){
    java.lang.String[] r0;
    int i1;
    r0 :=@parameter0: java.lang.String[];
    i1=0;
label1:
    if i1>=10 goto label2;
    i1=i1+1;
    goto label1;
label2:
    return;
}

// 方法調(diào)用源代碼形式
package org.examples;
public class MC{
    String foo(String para1, String para2){
        return para1 + " " +para2;
    }
}

// 方法調(diào)用的3AC
java.lang.String foo(java.lang.String, java.lang.String){
    org.example.MC r0;
    java.lang.String r1,r2,$r7;
    java.lang.StringBuilder $r3, $r4, $r5, $r6; // $代表臨時(shí)變量

    r0 :=@this: org.examples.MC;
    r1 :=@parameter0: java.lang.String;
    r2 :=@parameter0: java.lang.String;
    $r3 = new java.lang.StringBuilder;
    specialinvoke $r3.<java.lang.StringBuilder: void <init>()>(); // specialinvoke:call constructor\superclass method\private methods
    $r4 = virtualinvoke $r3.<java.lang.StringBuilder: java.lang.StringBuilder append(java.lang.String)>(r1); // virtualinvoke: instance methods call
    $r5 = virtualinvoke $r4.<java.lang.StringBuilder: java.lang.StringBuilder append(java.lang.String)>(" ");
    $r6 = virtualinvoke $r5.<java.lang.StringBuilder: java.lang.StringBuilder append(java.lang.String)>(r2);
    $r7 = virtualinvoke $r6.<java.lang.StringBuilder: java.lang.StringBuilder toString()>();
    return $r7;
}
interfaceinvoke:cannot optimization, checking interface implementation
staticinvoke: call static methods
// 方法聲明
method signture: class name\return type\method name(parameter types)

除3AC三地址碼格式，還有一種IR的格式稱為SSA（Static Single Assignment，靜態(tài)單一任務(wù)）。
SSA中的所有賦值都是給具有不同名稱的變量。它和3AC不同的是，每個(gè)變量都只有一個(gè)定義，每個(gè)定義都有一個(gè)新的名稱。這種相對于3AC會提升一定的精度，但是會導(dǎo)致翻譯成機(jī)器碼時(shí)效率下降

// 3AC vs SSA
p=a+b  p1=a+b
q=p-c  q1=p1-c
p=q*d  p2=q1*d

這部分內(nèi)容可以在本地寫一個(gè)類文件，如Test.class。然后從https://soot-build.cs.uni-paderborn.de/public/origin/master/soot/soot-master/下載對應(yīng)版本的jar包，類和jar文件放在同一目錄下，然后用如下命令生成Jimple文件。

java -cp sootclasses-trunk-jar-with-dependencies-4.1.0.jar soot.Main -f J -pp -cp . Test 

2. Data Flow Analysis

CFG

CFG（Control Flow Graph，控制流圖），是靜態(tài)分析的基本結(jié)構(gòu)。它其中的節(jié)點(diǎn)是一個(gè)個(gè)3AC的指令，或者一個(gè)BB（Basic Block，基礎(chǔ)塊）。

BB是連續(xù)三地址指令的最大序列，它需要滿足的要求是：BB塊中的第一個(gè)指令是該塊的唯一入口，最后一個(gè)指令是唯一出口。構(gòu)建BB的算法如下。
（1）3AC中的第一條指令是header
（2）條件或無條件跳轉(zhuǎn)的目標(biāo)是header
（3）緊隨條件跳轉(zhuǎn)的指令是header

How to build Basic Blocks

把3AC指令轉(zhuǎn)換成BB的Demo如下，根據(jù)構(gòu)建BB的算法，一共12條3AC指令。首先3AC中的第一條指令，即1是header。其次，條件或無條件跳轉(zhuǎn)(return)的目標(biāo)包括7，12，3。這三條也是header。然后，包含條件跳轉(zhuǎn)的指令是4，10，11。所以5，11，12作為緊隨條件跳轉(zhuǎn)的指令也是header?？偨Y(jié)起來，header包括：1，3，5，7，11，12。然后將leader和它的所有后續(xù)指令（直到下一個(gè)header）組成BB。

3AC轉(zhuǎn)換成BB，再轉(zhuǎn)換成CFG

構(gòu)建CFG
CFG的節(jié)點(diǎn)是BB，BB轉(zhuǎn)換成CFG則是在BB之間添加邊：對于順序指令、條件跳轉(zhuǎn)的情況，添加邊，但是如果BB對應(yīng)了無條件跳轉(zhuǎn)，其后的BB不加邊（例如B5和B6）。如上圖右側(cè)。邊的BB之間就形成了前身（predecessor）和后繼（successor）。另外，在構(gòu)建CFG的時(shí)候會添加兩個(gè)節(jié)點(diǎn)，入口Entry和出口Exit。它們不屬于可執(zhí)行IR。

數(shù)據(jù)流分析可以理解為數(shù)據(jù)如何在CFG上傳遞。主要的三種包括：（1）Reaching Definitions Analysis、（2）Live Variables Analysis、（3）Available Expressions Analysis

在理解數(shù)據(jù)流分析之前，先要了解一些基本概念：（1）輸入輸出狀態(tài)State：每次IR語句的執(zhí)行都將輸入狀態(tài)轉(zhuǎn)換為新的輸出狀態(tài)。但是分析的時(shí)候根據(jù)控制流的方向不同可以分為：前向分析Forward Analysis和后向分析Backward Analysis。前向分析的符號表示為OUT[s] = fs(IN[s])，后向分析為IN[s] = fs(OUT[s])

輸入輸出狀態(tài)

Notations for Control Flow’s Constraints

Reaching Definitions Analysis

Reaching Definitions定義如下，也就是在p點(diǎn)定義了變量v，v=xxx，在從p到q的路徑中，v沒有被重新定義（"kill"），就認(rèn)為v到達(dá)了q?？梢员硎緸?code>D: v = x op y。

Reaching Definitions

兩個(gè)約束：它的Transfer Function（傳遞函數(shù)）可以定義為OUT[B] = genB U (IN[B] - killB)；Control Flow控制流可以定義為IN[B] = Up a predecessor of B OUT[P]。所謂gen就是當(dāng)前BB中定義的變量，kill是此變量在其他BB中對應(yīng)的Definition。示例如下：

Reaching Definitions

在B1塊中，gen的變量是i,j,a，對應(yīng)的就是d1,d2,d3。kill的就是其他具有i,j,a的地方，其他具有i:d4,d7；其他具有j:d5；其他具有a:d6。所以kill的集合是d4,d5,d6,d7。
在B2塊中，gen的變量是i,j，其他具有i:d1,d7，其他具有j:d2，所以kill的集合是d1,d2,d7。以此類推。

Reaching Definitions Analysis算法如下

Reaching Definitions Analysis算法

算法Demo

Reaching Definitions Analysis算法Demo

同一個(gè)變量用相同的顏色表示，例如D2和D4都是紅色代表y。每個(gè)變量Definition初始設(shè)為0

D1 D2 D3 D4 D5 D6 D7 D8 
0  0  0  0  0  0  0  0

根據(jù)算法，每一個(gè)OUT[B]都初始化為空，也就是每個(gè)BB的OUT都設(shè)為00000000。
（1）B1
然后開始計(jì)算B1的OUT[B1]，根據(jù)Transfer Function的定義OUT[B] = genB U (IN[B] - killB)進(jìn)行計(jì)算，此時(shí)的IN為0000000，genB為11000000（因?yàn)榇藭r(shí)D1、D2有定義），killB應(yīng)該kill包含x,y的Definition，如D4，D5，D7，但是這三個(gè)目前的Definition都為0，kill后還是為0，所以killB還是0000000。最終得到的OUT[B1]=11000000 U 00000000=11000000 。U為或運(yùn)算。
（2）B2
先算B2的IN，根據(jù)定義IN[B] = Up a predecessor of B OUT[P]，先找到B2所有的前驅(qū)進(jìn)行U操作。B2的前驅(qū)包含B1和B4，二者的OUT進(jìn)行U操作，即11000000 U 00000000。此時(shí)的IN[B]=11000000。
為了計(jì)算OUT，先算一下killB，B2的m和y，只在D2中有。所以要在IN[B]的基礎(chǔ)上kill D2，即變?yōu)?code>10000000，再genB00110000，二者進(jìn)行或運(yùn)算，最終OUT[B2]結(jié)果為10110000。因?yàn)锽3和B4的前驅(qū)都只有B2，所以IN[B3]和IN[B4]的值就為OUT[B2]
（3）B3
計(jì)算B3的OUT要先從IN的10110000中Kill掉具有x的D1、D5，IN中的D5本身就是0，只killD1就可以了，即變成00110000，再與D7做或運(yùn)算，得到OUT[B3]=00110010
（4）B4
其他具有x,z的：D1、D7、D8。IN是B2的OUT，從IN中kill D1、D7、D8，得到00110000。再與D5、D6做或運(yùn)算，得到OUT[B4]=00111100
（5）B5
B5的前驅(qū)包含了B4和B3，需要先對前驅(qū)的OUT做或操作。也就是00111100 U 00110010，得到IN為00111110，然后kill掉z對應(yīng)的D6，得到00111010，再gen D8，00111011
至此，完成了第一輪的遍歷。
根據(jù)算法要求，如果有任何的BB的OUT發(fā)生了變化，就需要再進(jìn)行遍歷。最終進(jìn)行了三輪遍歷。

三輪遍歷

所有綠色的都是Final analysis result。這個(gè)序列代表哪個(gè)D能到達(dá)BB，例如B1最終結(jié)果是D1，D2能夠到達(dá)。B3是D3，D4，D6，D7能夠到達(dá)。每個(gè)應(yīng)用點(diǎn)都關(guān)聯(lián)了一個(gè)data-flow value（D序列），它代表了能否到達(dá)這個(gè)點(diǎn)的抽象。

迭代算法為什么最后會停止？首先gen和kill是固定不變的。在第二輪的時(shí)候，IN可能發(fā)生變化（more facts）：0->1 , 1->1，不可能1->0，因?yàn)橐猭ill的在第一輪就會kill，也就是OUT只會增長，不會變小。所以最極端的情況，就是所有的位都變成了1，那么也會停下來。

Live Variables Analysis

Live Variables Analysis直譯過來為存活變量分析。簡單來說就是判斷變量v在程序的某一點(diǎn)是否是Live的。圖示如下：

Live Variables Analysis

在一條路徑上有使用變量v的地方，并且在使用前v沒有被重定義，就認(rèn)為v在程序點(diǎn)p是live的。Live Variables的應(yīng)用之一就是編譯優(yōu)化，比如可用于寄存器分配。即在某些情況下，所有寄存器都已滿，我們需要使用一個(gè)寄存器，那么我們應(yīng)該傾向于使用具有dead value的寄存器。

這種方式針對的是程序中的Variables而不再是Definition。這種方法適用于逆推，首先找到use(v)的地方，即下圖中的S1，然后向上尋找v被定義的P。很容易看出OUT[B]應(yīng)該是IN[S]的集合，但是IN[B]的算法，就要分場景來看：
（1）v被重新定義了 -> IN[B]={ }
（2）B中用到了v -> IN[B]={ v }
（3）B中用到了v并且v也被重新定義了 ->看是先使用v還是先進(jìn)行了重定義 -> IN[B]={ v }或IN[B]={ }

但是在下圖的IN[B]計(jì)算公式可以和Reaching Definition Analysis進(jìn)行比較。Reaching Definition Analysis是正向的推導(dǎo)OUT[B] = genB U (IN[B] - killB)。Live Variables Analysis是逆向的推導(dǎo)IN[B]=useB U (OUT[B] - defB)。二者極為類似，都是先用集合去除要kill的或重定義的，然后并上用到的。

Live Variables Analysis逆推

對應(yīng)的算法代碼如下，同為may analysis，初始化都為空。存活變量分析算法是逆推算法，所以設(shè)IN[exit]為空

Live Variables Analysis算法

Demo如下，此處的變量序列如下。存活變量分析中所有的變量都會被納入序列中。但是Reaching Definitions Analysis只會把等號前被定義的變量放入序列。

x y z p q m k
0 0 0 0 0 0 0

Live Variables Analysis Demo

有任意的BB的IN發(fā)生了變化就需要再次進(jìn)行遍歷。顯然每個(gè)BB和初始化的0都不同了，就需要開始第二輪。最終的三輪結(jié)果如下。

三輪結(jié)果

Available Expressions Analysis

Available Expressions Analysis直譯為可用表達(dá)式分析。定義是：如果（1）從入口到p的所有路徑都必須經(jīng)過x op y的計(jì)算，并且（2）在x op y的最后一次計(jì)算之后，沒有對x或y的重新定義，則表達(dá)式x op y在程序點(diǎn)p處可用。Available Expressions Analysis可以用于檢測全局表達(dá)式。

Available Expressions Analysis圖示如下：表達(dá)式整體作為向量，IN的時(shí)候表達(dá)式是a+b，但是在BB中，a被重新定義了，按照規(guī)則需要刪除任何包括a變量的表達(dá)式，即刪除a+b。gen的是x op y，最后求并集OUT即為x op y

Available Expressions Analysis

課件中給了一個(gè)小例子來判斷表達(dá)式是否是Available的，直覺上左邊的path，x被重定義過了，像是Unavailable的。但是根據(jù)上面Available Expressions Analysis的定義：在x op y的最后一次計(jì)算后，沒有對x進(jìn)行重新定義（此處的重定義是在計(jì)算前的，符合定義）。并且由于定義要求所有路徑都必須經(jīng)過x op y的計(jì)算，所以路徑最終要取交集，而不是前面兩種分析的并集。由于左右兩條路都是Available的，那么認(rèn)為該匯聚點(diǎn)是Available的。

Understanding Available Expressions Analysis

Available Expressions Analysis算法如下

Available Expressions Analysis算法

Available Expressions Analysis算法Demo

（1）B1
B1的IN是00000，kill含y的表達(dá)式。然后和p-1取并集。得到10000
（2）B2
B2的前驅(qū)包含B110000和B411111，二者取交集（與）得到10000。kill含k和p的表達(dá)式，genz/5和e7*x。操作得到01010
繼續(xù)運(yùn)算，直到各個(gè)B的OUT不再變化。

最終結(jié)果

這三個(gè)數(shù)據(jù)流分析的方法，以x=p+q為例。一個(gè)針對Definition，即x；一個(gè)針對Variable，其中的p,q；一個(gè)針對Expression，即p+q。

數(shù)據(jù)流分析理論

課程的第五講和第六講主要是講了數(shù)據(jù)流分析中的理論，包括迭代算法、偏序、上下界、格、單調(diào)性與不動點(diǎn)定理、MOP、常量傳播、Worklist算法等內(nèi)容。

迭代算法

一個(gè)May&Forward分析的算法如下圖左上所示。簡單來說就是一個(gè)CFG擁有k個(gè)節(jié)點(diǎn)，每一次迭代都更新每個(gè)節(jié)點(diǎn)的OUT。這樣所有的節(jié)點(diǎn)就形成了一個(gè)K元組(OUT[n1], OUT[n2], ..., OUT[nk])。或抽象成(V1 ×V2 ...×Vk)，那么每一輪利用傳遞函數(shù)和控制流處理，將Vk中的一個(gè)元素抽象為Vk中的一個(gè)新元素（函數(shù)F: Vk→Vk）。直到兩個(gè)連續(xù)的K元組相同時(shí)迭代結(jié)束。

迭代算法

Xi=F(Xi)時(shí)就認(rèn)為X是一個(gè)不動點(diǎn)，整個(gè)迭代算法也達(dá)到了不動點(diǎn)。

由此也有了一系列疑問：算法是否一定能終止迭代（或者說到達(dá)不動點(diǎn)）？如果有不動點(diǎn)是只有一個(gè)還是不止一個(gè)？我們的解決方法是最好或最準(zhǔn)確的么？算法會在什么時(shí)候達(dá)到不動點(diǎn)？回答這一系列問題前，就涉及到一些數(shù)學(xué)知識。

偏序（Partial Order）

偏序集（poset）被定義為一對(P，?)，其中?是一個(gè)二元關(guān)系，定義了P上的部分排序，?具有以下屬性:
（1）自反性Reflexivity： ?a∈S，有a≤a；
（2）反對稱性Antisymmetry：?a，b∈S，a≤b且b≤a，則a=b；
（3）傳遞性Transitivity：?a，b，c∈S，a≤b且b≤c，則a≤c；

所謂的二元關(guān)系，是兩種事物之間的聯(lián)系，例如算術(shù)中的大于、等于；或者幾何學(xué)中的子集。自反性可以簡單理解為等于、小于等于、大于等于、整除等（a≤a）；反對稱性，簡單理解為a≤b且b≤a，則a=b；傳遞性比較好理解，a≤b且b≤c，則a≤c。

課程中給了幾個(gè)例子
（1）例子1，假如偏序代表<小于號，S是整數(shù)集合，問S是否為偏序集。答案是不是，首先就不滿足自反性，1<1是不成立的。
（2）例子2，假如偏序代表子集，S是英文單詞的集合，如下左圖。問S是不是偏序集。對于自反性，可以理解為對于每一個(gè)字符串，是不是自己子集的字符串。反對稱性，可以理解為A、B兩個(gè)字符串互為彼此的子集，那么兩個(gè)字符串是相等的。下面這個(gè)例子也說明了偏序只是需要部分滿足，不要求所有元素都滿足。比如sin和singing是滿足條件的，pin和sin不滿足條件。但只要有部分滿足就符合偏序。
（3）例子3，假如偏序代表子集，S是一個(gè)power set冪集（原集合中所有的子集（包括全集和空集）構(gòu)成的集）。如下右圖。所以例子2、3都滿足偏序。

偏序例子

上界和下界（Upper and Lower Bounds）

least upper bound(最小上界，縮寫為：lub，也稱為join)，可以寫為?S；greatest lower bound（最大下屆，縮寫為：glb，也稱為meet），可以寫為?S。如果S中包含兩個(gè)元素a,b，那么最小上界可以寫為a ? b，即the join of a and b。同樣，最大下屆可以寫為a ? b，即the meet of a and b。圖示如下：

Upper and Lower Bounds

PS：不是每個(gè)poset都有最小上界和最大下界，如果有的話一定是唯一的。以上圖的S自身為例，就沒有g(shù)lb（最大下界），因?yàn)榭占⒉辉赟中。證明唯一性可以利用反證法，假設(shè)g1，g2都是最大下界，那么按照偏序集定義，g1?(g2 =?P) and g2?(g1 =?P)，那么g1=g2，也就是唯一。

Lattice（格）

格：如果偏序集的每一對元素都有最小上界和最大下界，則該偏序集就是格。如果對上述偏序中的三個(gè)例子進(jìn)行是否為Lattice的判斷。例子1是，例子2不是。例子3是。因?yàn)樵诶?中，pin和sin就不存在最小上界，不滿足每一對元素都有最小上界和最大下界的條件。

Semilattice半格：只存在最小上界或最大下界中的一個(gè)。如果存在最小上界，就稱為join semilattice。如果存在最大下界，就稱為meet semilattice

Complete Lattice全格：對于一個(gè)格，其任意子集的最小上界和最大下界都存在。Lattice是任意兩個(gè)元素，而Complete Lattice是任意子集。后者要求更嚴(yán)格。對于上述偏序中的三個(gè)例子來說，例子1不是，例子2不是，例子3是。例子1中定義的是整數(shù)集合，而整數(shù)的個(gè)數(shù)可能是無窮的，所以想求上界的時(shí)候可能也是無窮的，不滿足存在最小上界的要求。例子3是。對于全格來說，它有一個(gè)最大元素T被稱做top和一個(gè)最小元素⊥被稱作bottom。

每個(gè)有限格（元素有窮）都是一個(gè)全格，但一個(gè)全格不一定是有限格。一般程序中用到的是Complete Lattice全格。

Product Lattice：對于給定格，L1 = (P1，?1)，L2 = (P2，?2)，…， Ln = (Pn，?n)，如果對于所有i， (Pi，?i)有?i(最小上界)和?i(最大下界)，那么我們可以有一個(gè)積格Ln = (P，?)。相關(guān)性質(zhì)如下：

P=P1×...×Pn
(x1,...,xn)?(y1,...,yn)?(x1 ?y1)∧...∧(xn ?yn) 
(x1,...,xn)?(y1,...,yn) = (x1 ?1 y1,...,xn ?n yn)
(x1,...,xn)?(y1,...,yn) = (x1 ?1 y1,...,xn?n yn)

如果Product Lattice中的每一個(gè)Lattice都是全格，那么這個(gè)Product Lattice也是全格

Data Flow Analysis Framework via Lattice

Data Flow Analysis Framework via Lattice

這個(gè)圖的形容是：Data flow analysis can be seen as iteratively applying transfer functions and meet/join operations on the values of a lattice。可以看出從s1到s2，是從Lattice的Bottom向上走的，經(jīng)過join操作的到Lattice的{a,b}，再經(jīng)過transfer functions，得到Lattice的最小上界。所以數(shù)據(jù)流分析可以認(rèn)為是在Lattice上應(yīng)用Transfer functions和meet/join操作。

有了這些數(shù)學(xué)知識，就回到介紹偏序之前的那些問題，（1）算法是否一定能終止迭代（或者說到達(dá)不動點(diǎn)）？如果有不動點(diǎn)是只有一個(gè)還是不止一個(gè)？我們的解決方法是最好或最準(zhǔn)確的么？算法會在什么時(shí)候達(dá)到不動點(diǎn)？

對于第（1）個(gè)問題。在上面介紹算法的時(shí)候提到OUT中的0可能變成1，但1不會變成0。所以最后有終點(diǎn)。如果要更通用的來看這個(gè)問題，則要用單調(diào)性monotonicity來解釋。對于第（2）個(gè)問題，x=f(x)的時(shí)候，函數(shù)能達(dá)到不動點(diǎn)。但是不動點(diǎn)可以有多個(gè)。即x=f(x)有多個(gè)x滿足條件。如下圖。

不動點(diǎn)

那么想要回答第（3）個(gè)問題，就需要了解單調(diào)性和不動點(diǎn)定理。

Monotonicity 單調(diào)性

如果格是單調(diào)的，那么x ? y ? f(x) ? f(y)，簡單理解就是x<=y的話，f(x)<=f(y)

Fixed Point Theorem 不動點(diǎn)定理

Fixed-Point Theorem

如果Complete Lattice是單調(diào)的，并且Lattice是有限的（finite，那么這個(gè)肯定個(gè)是全格，但全格不一定是有限的）。去尋找最小不動點(diǎn)的方法是：

先找到bottom，然后不斷通過f()去迭代bottom，那么達(dá)到不動點(diǎn)的那一刻就是最小不動點(diǎn)。同樣，先找top，然后不斷迭代，達(dá)到不動點(diǎn)那一刻就是最大不動點(diǎn)。

這個(gè)方法可以用如下的方式來證明是正確的。要證明首先（1）不動點(diǎn)存在，其次（2）不動點(diǎn)是最小/最大的，即是最優(yōu)的。對于（1）的證明：每個(gè)Lattice都有bottom和top。以bottom為例，f(bottom)也是Lattice上的值，而bottom是Lattice上的最小值，所以bottom?f(bottom)。然后根據(jù)單調(diào)性，f(bottom)是不斷增大的，但由于有限性，Lattice存在一個(gè)邊界，最終證明不動點(diǎn)。

Fixed-Point Theorem (Existence of Fixed Point)

對于（2）的證明，既然要證明最小，就可以假設(shè)有一個(gè)其他的不動點(diǎn)存在。利用數(shù)學(xué)歸納法（Induction）來證明。數(shù)學(xué)歸納法的證明步驟大致為：先設(shè)置初始條件，例如f(1)=xx，然后假設(shè)在第i次時(shí)成立，然后證明i+1次也成立。證明如下

Fixed-Point Theorem (Least Fixed Point)

那么再回答第（3）個(gè)問題的時(shí)候，如果不動點(diǎn)不止一個(gè)，怎么判斷我們的解決方法是否為最好的，那么就要看我們的是否為greatest或least的不動點(diǎn)。

那么如何把算法和不動點(diǎn)定理關(guān)聯(lián)起來？圖示如下

算法到達(dá)不動點(diǎn)

從Lattice的角度來看May和Must Analysis。如下圖。對于May來說，最開始認(rèn)為所有的Definitions都不可達(dá)，此時(shí)是unsafe的，但是如果達(dá)到了top，雖然變安全了，但是越來越不準(zhǔn)，因?yàn)檎J(rèn)為所有都可達(dá)，相當(dāng)于沒有計(jì)算。對于不同類型，May、Must Analysis來說，最準(zhǔn)的點(diǎn)也不同?；贛ay來說是Least Fixed Point，對于Must來說，是Greatest Fixed Point。

May and Must Analysis in Lattice view

從Entry到Si可能有很多條path，每條path可以被寫為P=Entry-> S1 -> S2 ->...-> Si。如果要定義整個(gè)Path的Transfer function，fsi-1的OUT就是si的IN，也是這條path的Transfer function的結(jié)果。MOP則是枚舉Entry到Si的所有path。把三條Fp（Transfer function的結(jié)果）進(jìn)行meet/join操作。所以MOP認(rèn)為是在每個(gè)路徑的末尾計(jì)算數(shù)據(jù)流值，并進(jìn)行meet/join找到最小上界lub/最大下界glb。

Meet-Over-All-Paths Solution (MOP)

我們之前用的算法是在所有匯合點(diǎn)都用join，但是MOP則是在最終點(diǎn)才會將結(jié)果join。算法和MOP之間的比較如下

與MOP的比較

根據(jù)最小上界的定義，所以x U y即是x的上界也是y的上界。由于F是單調(diào)的，那么x<y的話，f(x)<f(y)。根據(jù)這個(gè)推導(dǎo)，具體的比較如下。也就是當(dāng)F是單調(diào)的時(shí)候，MOP是比我們的算法要精準(zhǔn)的。當(dāng)F是distributive的時(shí)候，是一樣準(zhǔn)的。前面提到的需要kill/gen的都是distributive的分析方法。但是有的就不是，比如Constant Propagation

算法和MOP的比較

常量傳播（Constant Propagation）

給定在程序點(diǎn)p處的變量x，確定x是否保證在p處保持恒定值（常量）。是個(gè)must型的分析。CFG中每個(gè)節(jié)點(diǎn)的OUT包含一組對(x, v)，其中x是一個(gè)變量，v是該節(jié)點(diǎn)后x所持有的值。根據(jù)上面提到的data flow analysis framework（D，L，F(xiàn)），生成一個(gè)Lattice包括Values和operator（? or ? ），并且要定義一個(gè)Transfer Function。示例如下：

Constant Propagation – Lattice

首先是生成Lattice。NAC：not a Constant（不是常量）。UNDEF：undefined。v：值。c：常量。如果左邊來個(gè)一個(gè)x=1，右邊也是一個(gè)x=1，匯聚到一起就是常量。即c ? c=c。但如果左邊是x=1，右邊是x=2，匯聚到一起就變了不是一個(gè)常量。所以c1 ? c2 = NAC

然后是定義Transfer Function，{Variable，Variable的值}，_代表通配符。val(x)代表對變量x進(jìn)行取值。x=y op z，用f(y,z)來算這個(gè)值。判斷這個(gè)是否為常量，需要分情況討論，如果val(y)和val(z)都是常量，那么計(jì)算結(jié)果為常量。如果其中一個(gè)是NAC，那么結(jié)果就是NAC。如果有一個(gè)是UNDEF，那么結(jié)果就是UNDEF。

Constant Propagation – Transfer Function

上面提到如果算法是distributivity的，那么我們的算法和MOP結(jié)果是一致的，如果是nondistributivity，那么結(jié)果就不一致。二者的計(jì)算區(qū)別在于是否先meet/join。以下面的例子來說，在c這個(gè)點(diǎn)，我們的算法，先meet/join。那么a就是1和9進(jìn)行meet。根據(jù)Constant Propagation – Lattice的圖示，c1 ? c2 = NAC，當(dāng)a進(jìn)行meet的兩個(gè)值不同時(shí)得到的是NAC。b同理。那么c=a+b，根據(jù)上面Constant Propagation – Transfer Function的圖示，對于x=y op z來說，如果有y和z有一個(gè)是NAC，那么x就是NAC。所以此時(shí)的c也是NAC。MOP則是要先對值計(jì)算完了，再進(jìn)行meet。那么就是10和10進(jìn)行meet。結(jié)果認(rèn)為是常量10。

Constant Propagation – Nondistributivity

Worklist Algorithm

工作列表算法（Worklist Algorithm）是迭代算法Iterative Algorithm的優(yōu)化。它只遍歷有變化的Function進(jìn)行遍歷。而不是只要OUT有一個(gè)變了就要把所有的BB進(jìn)行迭代。算法一開始把所有的BB都放入到Worklist中，計(jì)算出的新的OUT和舊的OUT進(jìn)行比較，如果產(chǎn)生了變化，就把B的后繼successor加入到Worklist中。

Worklist Algorithm

過程間分析 Interprocedural Analysis

上述算法研究的都是過程內(nèi)的分析，以下面這個(gè)例子來說，x的來源會認(rèn)為是NAC，并且y=NAC，n=NAC。但是如果能將x=42真實(shí)地帶入到bar方法中。就可以得到精確的值:x=42,y=43,n=10。這就涉及到方法之間的調(diào)用，來保證方法之間傳遞數(shù)據(jù)的精確度。

void foo(){
  int n= bar(42);
}

int bar(int x){
  int y=x+1;
  return 10;
}

程序間的調(diào)用關(guān)系用調(diào)用圖來表示，它是一組從調(diào)用點(diǎn)（call-sites）到目標(biāo)方法（target methods，callees）的調(diào)用邊的集合。

Call Graph

控制流圖是程序分析、調(diào)試的基礎(chǔ)。調(diào)用圖構(gòu)造有四種主要方法：Class hierarchy analysis (CHA，類層次分析)、Rapid type analysis (RTA，快速型分析)、Variable type analysis (VTA，變量分析)、Pointer analysis (k-CFA，指針分析)（從左到右，速度逐漸變慢，精確度逐漸變高）。

Java主要有三種調(diào)用方法。3AC部分提到過，Static call是調(diào)用靜態(tài)方法，Special call包括構(gòu)造方法、私有方法和父類方法。其他的方法都被稱為Virtual call。Virtual Call的方法調(diào)度是基于（1）接收對象的類型 （2）方法簽名（Signature，標(biāo)示符）。

? Signature = class type + method name + descriptor
? Descriptor = return type + parameter types

Method Calls

Method Dispatch of Virtual Calls

Method Dispatch（方法調(diào)度）是指在面向?qū)ο缶幊讨?，如何決定在調(diào)用一個(gè)方法時(shí)哪個(gè)實(shí)現(xiàn)（implementation）會被執(zhí)行的過程。Virtual Calls只有在運(yùn)行時(shí)才能得到準(zhǔn)確的信息。例如o.foo(...)，需要知道o的具體類型，和foo()的method signature。所謂的signature包括如下：方法的class類型、方法名、返回類型和參數(shù)類型。

方法調(diào)度元素示例

Method Dispatch

函數(shù)Dispatch(??，??)用來模擬運(yùn)行時(shí)Method Dispatch過程。Dispatch的目的是找到一個(gè)能被調(diào)用的目標(biāo)函數(shù)。但面向?qū)ο笳Z言中，方法能被調(diào)用的前提是方法是非抽象（non-abstract）的。
（1）如果類c中包含一個(gè)non-abstract方法m'，且m'和m具有相同的name、descriptor。那么就相當(dāng)于找到了要被調(diào)用的函數(shù)，返回m'
（2）如果類c中沒有找到對應(yīng)方法，就在c的父類c'中尋找，如果還沒有找到就在c'的父類中尋找。依次類推直到找到對應(yīng)方法。

下面有個(gè)例子來熟悉Dispatch(??，??)，A、B、C之間是父類的關(guān)系。

class A{
  void foo(){...}
}
class B extends A{}
class C extends B{
  void foo(){...}
}
void dispatch(){
  A x=new B();
  x.foo();  // Dispatch(B, A.foo())=A.foo()，B中沒有foo方法，所以調(diào)用父類A中的方法方法

  A y=new C();
  y.foo(); // Dispatch(C, A.foo())=C.foo()，C中有同name和descriptor的方法，所以調(diào)用C中的方法
}

Class hierarchy analysis類層次分析

CHA的特點(diǎn)是需要整個(gè)程序的類層次結(jié)構(gòu)信息（繼承結(jié)構(gòu)）。然后根據(jù)declared type和receiver variable來處理Virtual Call。

A a=...  //聲明變量的類型是A，即使A a=new B();，聲明變量的類型也還是A 
a.foo(); // a就是receiver variable

a可能指向a或a所有子類的對象，需要通過查找A的類層次結(jié)構(gòu)來解析目標(biāo)方法。CHA的具體解析方法是：定義Resolve(cs)來解析可能的目標(biāo)方法。cs表示call-site調(diào)用點(diǎn)。

Resolve(cs)

這里需要注意是進(jìn)行Dispatch，而不是查找（因?yàn)椴檎抑辉诋?dāng)前類）。Dispatch在上面提到如果當(dāng)前類中沒找到對應(yīng)方法，會去父類尋找。

// (1) static call
class C{
  static T foo(P p, Q q){...}
}
C.foo(x, y); // cs:C.foo(x,y); m: <C: T foo(P,Q)>

// (2) special call 父類方法
class C extends B{
  T foo(P p, Q q){
    ...super.foo(p,q);  // cs:super.foo(p,q); m:<B: T foo(P,Q)>
  }
}

// (3) special call private方法
class C extends B { 
  T foo(P p, Q q) {
    ...
    this.bar();  // 類似static call
  }
  private T bar() 
}

// (4) special call 構(gòu)造方法
C c = new C(); // 類似static call

// (5) virtual call
class A{
  T foo(P p, Q q){...}
} 
A a=... 
a.foo(x,y); // cs: a.foo(x,y); m:<A T foo(P,Q)> c:A

一個(gè)CHA的具體例子：

class A{
  void foo(){...}
}
class B extends A{}
class C extends B{
  void foo(){...}
}
class D extends B{
  void foo(){...}
}
void resolve(){
  C c=...
  c.foo();  // Resolve(c.foo())={C.foo()} 因?yàn)楫?dāng)前類C存在foo方法，并且C沒有子類
  A a=...
  a.foo(); // Resolve(a.foo())={A.foo(), C.foo(), D.foo()}，A存在foo，且其子類C，D也存在foo。
  B b=new B();
  b.foo(); // Resolve(b.foo())={A.foo(), C.foo(), D.foo()}，B不存在foo，所以在進(jìn)行Dispatch時(shí)會查找父類
}

Dispatch時(shí)如果當(dāng)前聲明類有對應(yīng)方法，就輸出當(dāng)前類的方法，沒有找到才會去父類查找方法。而且由于CHA是根據(jù)聲明類來查找，所以B b=new B和B b=new C()沒有區(qū)別，都是要根據(jù)聲明變量B類型來查找。所以它的劣勢是不精準(zhǔn)，容易引入這種偽目標(biāo)方法。但是優(yōu)勢是速度快，只需要考慮聲明變量的類型，忽略數(shù)據(jù)流和控制流信息。

PS：IDEA就是用CHA的方法來解析目標(biāo)方法，長見識了！

IDEA與CHA

如何用CHA構(gòu)造程序調(diào)用圖？
上面說的是如何用CHA來構(gòu)造一個(gè)調(diào)用點(diǎn)。而CHA來構(gòu)造調(diào)用圖是從入口方法開始(重點(diǎn)關(guān)注main方法)，調(diào)用過程中的可達(dá)方法（對應(yīng)調(diào)用邊），對每個(gè)可達(dá)方法利用CHA來解析call-site（Resolve(cs)），直到?jīng)]有新的方法被發(fā)現(xiàn)。具體的CHA構(gòu)造調(diào)用圖的算法如下

Call Graph Construction: Algorithm

WL代表Worklist，代表需要被處理的方法。CG是調(diào)用圖集合所有的邊。RM是可達(dá)方法的集合（也就是該方法分析過了不用再分析了）。先對這三者進(jìn)行初始化，只要WL不為空就一直循環(huán)：從WL取一個(gè)方法出來，如果該方法不在RM集合中，也就是個(gè)新方法，首先將方法加入到RM集合，然后遍歷這個(gè)方法中的每一個(gè)call-site調(diào)用點(diǎn)，用Resolve(cs)來處理得到目標(biāo)方法m'的集合T。然后再對T進(jìn)行遍歷，將其中的調(diào)用邊加入到調(diào)用圖中，并且將m'加入到WL。

一個(gè)例子如下：

Call Graph Construction Demo

Interprocedural Control-Flow Graph過程間控制流圖

CFG表示單個(gè)方法的結(jié)構(gòu)，ICFG表示整個(gè)程序的結(jié)構(gòu)。通過ICFG，我們可以進(jìn)行程序間分析。ICFG = CFGs + call edges & return edges。這兩種edges的信息來自調(diào)用圖call graph。
call edges（調(diào)用邊）：從調(diào)用點(diǎn)到被調(diào)用點(diǎn)的入口節(jié)點(diǎn)
return edges（返回邊）：從被調(diào)用方的退出節(jié)點(diǎn)到其調(diào)用點(diǎn)后面的語句

void foo() {
  bar(...); // call site：調(diào)用方法的語句
  int n = 3; // return site：緊跟著調(diào)用語句的叫return site。那么return edge就是從bar的返回語句連到int n=3
}

一個(gè)ICFG的例子如下，黑色的是cfg。藍(lán)色的是call edges，紅色的是return edges。

ICFG Demo

Interprocedural Data-Flow Analysis過程間數(shù)據(jù)流分析

顧名思義就是：基于程序間控制流圖(ICFG)的方法調(diào)用分析整個(gè)程序。

相比而言，只是比CFG多了Edge transfer。它分為兩種：
? Call edge transfer: 將數(shù)據(jù)流從調(diào)用點(diǎn)轉(zhuǎn)移到被調(diào)用的入口節(jié)點(diǎn)（傳參數(shù)）
? Return edge transfer: 將數(shù)據(jù)流從被調(diào)用方的出口節(jié)點(diǎn)轉(zhuǎn)移到返回點(diǎn)（傳返回值）
? Node transfer: 和過程內(nèi)類似，但是對于方法調(diào)用節(jié)點(diǎn)b=addOne(a)，要kill左值b，因?yàn)檎嬲凳菑腶ddOne(a)的結(jié)果流回來的。

過程間數(shù)據(jù)流分析示例如下（以常量傳播為例）：

過程間數(shù)據(jù)流分析示例

b=ten()的OUT需要kill b，理由是b的值會隨著return 10返回。如果沒有killb，也就是保留b=7，那么在b=ten()和return 10交匯的時(shí)候會對7和10進(jìn)行meet。那么會認(rèn)為b不是一個(gè)常量。但實(shí)際上b=10就是一個(gè)Constant。所以在OUT時(shí)先kill b。避免精度上的損失。這個(gè)例子解釋了兩個(gè)問題，（1）b=addOne(a)和c=b-3之間的cfg邊為什么要保留 （2）為什么OUT時(shí)要kill b。

通過例子也可以看出過程內(nèi)分析是很保守的，對于b=addOne(a)會認(rèn)為b是NAC，即認(rèn)為不是常量。那么c=b-3也會因?yàn)閎是NAC，而導(dǎo)致c也是NAC。而過程間分析則較為精確。