目錄：
指針分析規(guī)則
如何實現(xiàn)指針分析
指針分析算法
指針分析如何處理函數(shù)調(diào)用（過程間指針分析）
重點：
理解指針分析的規(guī)則、指針流圖PFG、指針分析算法。
理解指針分析調(diào)用函數(shù)的規(guī)則、過程間指針分析算法、實時調(diào)用圖構(gòu)建。
1.指針分析規(guī)則
首先分析前4種語句：New / Assign / Store / Load。
指針分析的域和相應(yīng)的記法：變量/函數(shù)/對象/實例域/指針，用pt表示程序中的指向關(guān)系（映射）。
規(guī)則：采用推導(dǎo)形式，橫線上面是條件，橫線下面是結(jié)論。
- New：創(chuàng)建對象，將
new T()對應(yīng)的對象oi加入到x的指針集。 - Assign：將y的指針集加入到x對應(yīng)的指針集。
- Store：讓oi的field指向oj。
-
Load：Store的反操作。
7-1-2-規(guī)則.png
2.如何實現(xiàn)指針分析
算法要求：全程序指針分析，要容易理解和實現(xiàn)。
本質(zhì)：在指針（變量/域）之間傳遞指向信息。Andersen-style分析（很普遍）——很多solving system把指針分析看作是一種包含關(guān)系，eg，x = y，x包含y。
問題：當(dāng)一個指針的指向集發(fā)生變化，必須更新與它相關(guān)的其他指針。如何表示這種傳遞關(guān)系？PFG。
PFG：用指針流圖PFG來表示指針之間的關(guān)系，PFG是有向圖。
- Nodes：Pointer = V U (O x F) 節(jié)點n表示一個變量或抽象對象的域。
- Edges：Pointer X Pointer 邊x -> y 表示指針x指向的對象may會流入指針y。
Edges添加規(guī)則：根據(jù)程序語句 + 對應(yīng)的規(guī)則。
示例：
PTA步驟：
- 構(gòu)造PFG（根據(jù)以上示例，PFG也受指向關(guān)系影響）
- 根據(jù)PFG傳播指向信息
3.指針分析算法
（1）過程內(nèi)PTA算法
符號：
S：程序語句的集合。
WL：Work list，待合并的指針信息，二元組的集合，<指針n，指向的對象集合pts>。pts將被加入到n的指向集pt(n)中。
PFG：指針流圖。
步驟：對每種語句都是基于第1小節(jié)的規(guī)則來實現(xiàn)。
對S中所有類似New
x = new T()的語句，將<x, {oi}>加入到WL。對S中所有類似Assign
x = y的語句，調(diào)用AddEdge()將y -> x加入到PFG，<x, pt(y)>加入到WL（傳播指向信息）。遍歷WL，取一個元素<n, pts>，除去pts中與pt(n)重復(fù)的對象得到
，調(diào)用Propagate(n,
n->s，將<s, pts>加入到WL（根據(jù)PFG將指向信息傳遞給同名指針）。如果n表示一個變量x（x跟Store/Load指令相關(guān)），對
x.f = y的語句，調(diào)用AddEdge()將y -> oi.f加入到PFG，<oi.f, pt(y)>加入到WL（傳播指向信息）；對S中所有類似Loady = x.f的語句，調(diào)用AddEdge()將oi.f -> y加入到PFG，<y, pt(oi.f)>加入到WL（傳播指向信息）。
問題：
為什么要去重？避免冗余，英文叫做Differential propagation差異傳播。
指針集用什么數(shù)據(jù)結(jié)構(gòu)存儲？混合集 Hibra-set，集合元素小于16個用hash set，大于16個用big-rector 位存儲。
（2）示例
1 b = new C();
2 a = b;
3 c = new C();
4 c.f = a;
5 d = c;
6 c.f = d;
7 e = d.f;
| WL | 正處理 | PFG | 指針集 | 處理語句 | 算法語句 | |
|---|---|---|---|---|---|---|
| 1 | [<b, {o1}>, <c, {o3}>] | 1，3 | 處理New | |||
| 2 | [<b, {o1}>, <c, {o3}>] | a<-b；d<-c； | 2，4 | 處理Assign | ||
| 3 | [<c, {o3}>] | <b, {o1}> | a<-b；d<-c； | pt(b)={o1} | while開頭 | |
| 4 | [<c, {o3}>], <a, {o1}>] | a<-b；d<-c； | Propagate()傳遞，沒有b.f語句 | |||
| 5 | [<a, {o1}>] | <c, {o3}> | a<-b；d<-c； | pt(c)={o3} | while開頭 | |
| 6 | [<a, {o1}>, <d, {o3}>] | a<-b；d<-c； | Propagate()傳遞，有c.f語句 | |||
| 7 | [<a, {o1}>, <d, {o3}>] | a<-b；d<-c；o3.f<-a；o3.f<-d； 7-3-1-PFG.png
|
4，6 | 處理Store/Load，添加邊 | ||
| 8 | [<d, {o3}>] | <a, {o1}> | pt(a)={o1}； | while開頭 | ||
| 9 | [<d, {o3}>,<o3.f, {o1}>] | Propagate()傳遞 | ||||
| 10 | [<o3.f, {o1}>] | <d, {o3}> | pt(d)={o3} | while開頭 | ||
| 11 | [<o3.f, {o1}>, <o3.f, {o3}>] | Propagate()傳遞，有d.f語句 | ||||
| 12 | [<o3.f, {o1}>, <o3.f, {o3}>] | a<-b；d<-c；o3.f<-a；o3.f<-d；e<-o3.f； 7-3-2-PFG.png
|
7 | 處理Load，添加邊 | ||
| 13 | [<o3.f, {o3}>] | <o3.f, {o1}> | pt(o3.f)={o1}； | while開頭 | ||
| 14 | [<o3.f, {o3}>, <e, {o1}>] | Propagate()傳遞 | ||||
| 15 | [<e, {o1}>] | <o3.f, {o3}> | pt(o3.f)={o1, o3} | while開頭 | ||
| 16 | [<e, {o1}>, <e, {o3}>] | Propagate()傳遞 | ||||
| 17 | <e, {o1}>；<e, {o3}> |  7-3-3-PFG.png
|
pt(e)={o1, o3} | while開頭 |
4.指針分析如何處理函數(shù)調(diào)用
構(gòu)造調(diào)用圖技術(shù)對比：
- CHA：基于聲明類型，不精確，引入錯誤的調(diào)用邊和指針關(guān)系。
- 指針分析：基于pt(a)，即a指向的類型，更精確，構(gòu)造更準(zhǔn)的CG并對指針分析有正反饋（所以過程間指針分析和CG構(gòu)造同時進(jìn)行，很復(fù)雜）。
void foo(A a) { // pt(a) = ???
...
b = a.bar(); // pt(b) = ??? 把a的指向分析清楚了，就能確定a.bar()到底調(diào)用哪個對象的bar()函數(shù)，那么b的指向也明確了。
...
}
（1）調(diào)用語句規(guī)則
call語句規(guī)則：主要分為4步。
- 找目標(biāo)函數(shù)m：Dispatch(oi, k)——找出pt(x)，也即oi類型對象中的k函數(shù)。
-
receiver object：把x指向的對象（
pt(x)）傳到m函數(shù)的this變量，即mthis - 傳參數(shù)：pt(aj), 1<=j<=n 傳給m函數(shù)，即p(mpj), 1<=j<=n。建立PFG邊，a1->mp1，...，an->mpn。
- 傳返回值：pt(mret)傳給pt(r)。建立PFG邊，r<-mret。
問題：為什么PFG中不添加x->mthis邊？因為mthis只和自己這個對象相關(guān)，而可能有pt(x)={new A, new B, new C}，指定對象的x只流向?qū)?yīng)的對象，是無法跨對象傳遞的。
（2）過程間PTA算法
問題：由于指針分析和CG構(gòu)造互相影響，所以每次迭代只分析可達(dá)的函數(shù)和語句。然后不斷發(fā)現(xiàn)和分析新的可達(dá)函數(shù)。
可達(dá)示例：
算法：黃色背景的代碼是和過程內(nèi)分析不同的地方。
符號：
mentry：入口main函數(shù)
Sm：函數(shù)m中的語句
S：可達(dá)語句的集合（就是RM中的語句）
RM：可達(dá)函數(shù)的集合
CG：調(diào)用圖的邊
步驟：基于調(diào)用規(guī)則來實現(xiàn)。
首先調(diào)用AddReachable(mentry)，將入口函數(shù)mentry的語句加到S中。處理New
x = new T()語句，把<x, {oi}>加入到WL；處理Assignx = y語句，調(diào)用AddEdge(y, x)加入邊到PFG。跟過程內(nèi)指針分析一樣，遍歷WL，取一個元素<n, pts>，除去pts中與pt(n)重復(fù)的對象得到
n->s，將<s, pts>加入到WL（根據(jù)PFG將指向信息傳遞給同名指針）。如果n表示一個變量x（x跟Store/Load指令相關(guān)），對
x.f = y的語句，調(diào)用AddEdge()將y -> oi.f加入到PFG，<oi.f, pt(y)>加入到WL（傳播指向信息）；對S中所有類似Loady = x.f的語句，調(diào)用AddEdge()將oi.f -> y加入到PFG，<y, pt(oi.f)>加入到WL（傳播指向信息）。最后調(diào)用ProcessCall(x, oi)，處理與x相關(guān)的call指令。取出S中類似
r = x.k(a1,...,an)的調(diào)用語句L，首先調(diào)用Dispatch(oi, k)解出調(diào)用的目標(biāo)函數(shù)m，把<mthis, {oi}>加入到WL（傳遞接收對象，上下文敏感分析將用到），將L->m這條調(diào)用邊加入到CG；調(diào)用AddReachable(m)將新的語句加入到S，并處理New/Assign語句；調(diào)用AddEdge()將實參->形參、返回值->r邊加入到PFG（傳遞參數(shù)、返回值），并將<形參,pt(實參)>、<r,pt(返回值)>加入到WL。
問題：為什么ProcessCall(x, oi)中，要判斷L->m這條邊是否已經(jīng)加入到CG？因為x可能指向多個對象，就會多次處理L這個調(diào)用指令，可能x中別的對象oj早就已經(jīng)將這條邊加入進(jìn)去了。
（3）示例
1 class A {
2 static void main(){
3 A a = new A();
4 A b = new B();
5 A c = b.foo(a);
6 }
7 A foo(Ax){...}
8 }
9 class B extends A {
10 A foo(A y) {
11 A r=newA();
12 return r;
13 }
14 }
| WL | 正處理 | PFG | 指針集 | RM | CG | 語句 | 算法語句 | |
|---|---|---|---|---|---|---|---|---|
| 1 | [] | {} | {} | {} | 初始化 | |||
| 2 | [] | {A.main()} | 1，2 | AddReachable(mentry) | ||||
| 3 | [<a,{o3}>, <b,{o4}>] | 3，4 | ||||||
| 4 | [<b,{o4}>] | <a,{o3}> | pt(a)={o3}； | while開頭 | ||||
| 5 | [] | <b,{o4}> | pt(b)={o4} | while開頭 | ||||
| 6 | [] | 5 | ProcessCall(b, o4) | |||||
| 7 | [<B.foothis, {o4}>] | {5->B.foo(A)} | m=Dispatch(o4, foo())=B.foo()；添加到調(diào)用圖 | |||||
| 8 | [<B.foothis, {o4}>, <r, o11>] | {A.main(), B.foo()} | AddReachable(B.foo())；添加到可達(dá)函數(shù) | |||||
| 9 | [<B.foothis, {o4}>, <r, o11>, <y, {o3}>] | {a->y, r->c}  |
AddEdge()；添加參數(shù)邊、返回值邊 | |||||
| 10 | [<r, o11>, <y, {o3}>] | <B.foothis, {o4}> | pt(B.foothis)={o4}； | while開頭，B.foothis沒有調(diào)用任何函數(shù) | ||||
| 11 | [<y, {o3}>, <c, {o11}>] | <r, o11> | pt(r)={o11}； | while開頭 | ||||
| 12 | <y, {o3}>, <c, {o11}> | pt(y)={o3}；pt(c)={o11} | while開頭 |
如果是CHA的話，CG={5->B.foo(A), 5->A.foo(A)}，錯誤識別為調(diào)用邊。
結(jié)果：
問題：沒有入口函數(shù)的？如對庫函數(shù)處理，生成調(diào)用庫函數(shù)的程序。
今天喝了點wine，整理的有點魔幻。。
