目錄：
指針分析規(guī)則
如何實(shí)現(xiàn)指針分析
指針分析算法
指針分析如何處理函數(shù)調(diào)用（過程間指針分析）
重點(diǎn)：
理解指針分析的規(guī)則夜牡、指針流圖PFG、指針分析算法堰怨。
理解指針分析調(diào)用函數(shù)的規(guī)則芥玉、過程間指針分析算法、實(shí)時(shí)調(diào)用圖構(gòu)建备图。
1.指針分析規(guī)則
首先分析前4種語句：New / Assign / Store / Load灿巧。
指針分析的域和相應(yīng)的記法：變量/函數(shù)/對(duì)象/實(shí)例域/指針，用pt表示程序中的指向關(guān)系（映射）揽涮。
規(guī)則：采用推導(dǎo)形式抠藕，橫線上面是條件，橫線下面是結(jié)論蒋困。
- New：創(chuàng)建對(duì)象幢痘，將
new T()對(duì)應(yīng)的對(duì)象oi加入到x的指針集。 - Assign：將y的指針集加入到x對(duì)應(yīng)的指針集家破。
- Store：讓oi的field指向oj颜说。
-
Load：Store的反操作。
7-1-2-規(guī)則.png
2.如何實(shí)現(xiàn)指針分析
算法要求：全程序指針分析汰聋，要容易理解和實(shí)現(xiàn)门粪。
本質(zhì)：在指針（變量/域）之間傳遞指向信息。Andersen-style分析（很普遍）——很多solving system把指針分析看作是一種包含關(guān)系烹困，eg玄妈，x = y，x包含y髓梅。
問題：當(dāng)一個(gè)指針的指向集發(fā)生變化拟蜻，必須更新與它相關(guān)的其他指針。如何表示這種傳遞關(guān)系枯饿？PFG酝锅。
PFG：用指針流圖PFG來表示指針之間的關(guān)系，PFG是有向圖奢方。
- Nodes：Pointer = V U (O x F) 節(jié)點(diǎn)n表示一個(gè)變量或抽象對(duì)象的域搔扁。
- Edges：Pointer X Pointer 邊x -> y 表示指針x指向的對(duì)象may會(huì)流入指針y。
Edges添加規(guī)則：根據(jù)程序語句 + 對(duì)應(yīng)的規(guī)則蟋字。
示例：
PTA步驟：
- 構(gòu)造PFG（根據(jù)以上示例稿蹲，PFG也受指向關(guān)系影響）
- 根據(jù)PFG傳播指向信息
3.指針分析算法
（1）過程內(nèi)PTA算法
符號(hào)：
S：程序語句的集合。
WL：Work list鹊奖，待合并的指針信息苛聘，二元組的集合，<指針n，指向的對(duì)象集合pts>设哗。pts將被加入到n的指向集pt(n)中璧尸。
PFG：指針流圖。
步驟：對(duì)每種語句都是基于第1小節(jié)的規(guī)則來實(shí)現(xiàn)熬拒。
對(duì)S中所有類似New
x = new T()的語句爷光，將<x, {oi}>加入到WL。對(duì)S中所有類似Assign
x = y的語句澎粟，調(diào)用AddEdge()將y -> x加入到PFG蛀序，<x, pt(y)>加入到WL（傳播指向信息）。遍歷WL活烙，取一個(gè)元素<n, pts>徐裸，除去pts中與pt(n)重復(fù)的對(duì)象得到
，調(diào)用Propagate(n,
n->s重贺，將<s, pts>加入到WL（根據(jù)PFG將指向信息傳遞給同名指針）。如果n表示一個(gè)變量x（x跟Store/Load指令相關(guān)）回懦，對(duì)
x.f = y的語句，調(diào)用AddEdge()將y -> oi.f加入到PFG怯晕，<oi.f, pt(y)>加入到WL（傳播指向信息）潜圃；對(duì)S中所有類似Loady = x.f的語句，調(diào)用AddEdge()將oi.f -> y加入到PFG舟茶，<y, pt(oi.f)>加入到WL（傳播指向信息）谭期。
問題：
為什么要去重？避免冗余吧凉，英文叫做Differential propagation差異傳播隧出。
指針集用什么數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)？混合集 Hibra-set阀捅，集合元素小于16個(gè)用hash set胀瞪，大于16個(gè)用big-rector 位存儲(chǔ)。
（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ù)對(duì)比：
- CHA：基于聲明類型寥闪，不精確，引入錯(cuò)誤的調(diào)用邊和指針關(guān)系磨淌。
- 指針分析：基于pt(a)疲憋，即a指向的類型，更精確梁只，構(gòu)造更準(zhǔn)的CG并對(duì)指針分析有正反饋（所以過程間指針分析和CG構(gòu)造同時(shí)進(jìn)行缚柳，很復(fù)雜）。
void foo(A a) { // pt(a) = ???
...
b = a.bar(); // pt(b) = ??? 把a(bǔ)的指向分析清楚了搪锣，就能確定a.bar()到底調(diào)用哪個(gè)對(duì)象的bar()函數(shù)秋忙，那么b的指向也明確了。
...
}
（1）調(diào)用語句規(guī)則
call語句規(guī)則：主要分為4步构舟。
- 找目標(biāo)函數(shù)m：Dispatch(oi, k)——找出pt(x)灰追，也即oi類型對(duì)象中的k函數(shù)。
-
receiver object：把x指向的對(duì)象（
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邊音五？因?yàn)閙this只和自己這個(gè)對(duì)象相關(guān)惫撰，而可能有pt(x)={new A, new B, new C}，指定對(duì)象的x只流向?qū)?yīng)的對(duì)象躺涝，是無法跨對(duì)象傳遞的厨钻。
（2）過程間PTA算法
問題：由于指針分析和CG構(gòu)造互相影響，所以每次迭代只分析可達(dá)的函數(shù)和語句坚嗜。然后不斷發(fā)現(xiàn)和分析新的可達(dá)函數(shù)夯膀。
可達(dá)示例：
算法：黃色背景的代碼是和過程內(nèi)分析不同的地方。
符號(hào)：
mentry：入口main函數(shù)
Sm：函數(shù)m中的語句
S：可達(dá)語句的集合（就是RM中的語句）
RM：可達(dá)函數(shù)的集合
CG：調(diào)用圖的邊
步驟：基于調(diào)用規(guī)則來實(shí)現(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，取一個(gè)元素<n, pts>凯肋，除去pts中與pt(n)重復(fù)的對(duì)象得到
n->s侮东，將<s, pts>加入到WL（根據(jù)PFG將指向信息傳遞給同名指針）圈盔。如果n表示一個(gè)變量x（x跟Store/Load指令相關(guān)），對(duì)
x.f = y的語句驱敲，調(diào)用AddEdge()將y -> oi.f加入到PFG，<oi.f, pt(y)>加入到WL（傳播指向信息）煤伟；對(duì)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（傳遞接收對(duì)象，上下文敏感分析將用到）吱殉，將L->m這條調(diào)用邊加入到CG掸冤；調(diào)用AddReachable(m)將新的語句加入到S，并處理New/Assign語句友雳；調(diào)用AddEdge()將實(shí)參->形參稿湿、返回值->r邊加入到PFG（傳遞參數(shù)、返回值）押赊，并將<形參,pt(實(shí)參)>饺藤、<r,pt(返回值)>加入到WL。
問題：為什么ProcessCall(x, oi)中流礁，要判斷L->m這條邊是否已經(jīng)加入到CG涕俗？因?yàn)閤可能指向多個(gè)對(duì)象，就會(huì)多次處理L這個(gè)調(diào)用指令神帅，可能x中別的對(duì)象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)}，錯(cuò)誤識(shí)別為調(diào)用邊插佛。
結(jié)果：
問題：沒有入口函數(shù)的杠巡？如對(duì)庫函數(shù)處理，生成調(diào)用庫函數(shù)的程序雇寇。
今天喝了點(diǎn)wine氢拥，整理的有點(diǎn)魔幻蚌铜。。
