目录：
-
指针分析规则
-
如何实现指针分析
-
指针分析算法
-
指针分析如何处理函数调用（过程间指针分析）
重点：
理解指针分析的规则、指针流图PFG、指针分析算法。
理解指针分析调用函数的规则、过程间指针分析算法、实时调用图构建。
1.指针分析规则
首先分析前4种语句：New / Assign / Store / Load。
指针分析的域和相应的记法：变量/函数/对象/实例域/指针，用pt表示程序中的指向关系（映射）。
7-1-1-标记方法.png
规则：采用推导形式，横线上面是条件，横线下面是结论。
- New：创建对象，将
new T()对应的对象oi加入到x的指针集。 - Assign：将y的指针集加入到x对应的指针集。
- Store：让oi的field指向oj。
-
Load：Store的反操作。
7-1-2-规则.png
2.如何实现指针分析
算法要求：全程序指针分析，要容易理解和实现。
本质：在指针（变量/域）之间传递指向信息。Andersen-style分析（很普遍）——很多solving system把指针分析看作是一种包含关系，eg，x = y，x包含y。
问题：当一个指针的指向集发生变化，必须更新与它相关的其他指针。如何表示这种传递关系？PFG。
PFG：用指针流图PFG来表示指针之间的关系，PFG是有向图。
- Nodes：Pointer = V U (O x F) 节点n表示一个变量或抽象对象的域。
- Edges：Pointer X Pointer 边x -> y 表示指针x指向的对象may会流入指针y。
Edges添加规则：根据程序语句 + 对应的规则。
7-2-1-PFG边规则.png
示例：
7-2-2-PFG示例.png
PTA步骤：
- 构造PFG（根据以上示例，PFG也受指向关系影响）
- 根据PFG传播指向信息
3.指针分析算法
（1）过程内PTA算法
7-3-0-PTA算法_过程内.png
符号：
-
S：程序语句的集合。
-
WL：Work list，待合并的指针信息，二元组的集合，<指针n，指向的对象集合pts>。pts将被加入到n的指向集pt(n)中。
-
PFG：指针流图。
步骤：对每种语句都是基于第1小节的规则来实现。
-
对S中所有类似New
x = new T()的语句，将<x, {oi}>加入到WL。 -
对S中所有类似Assign
x = y的语句，调用AddEdge()将y -> x加入到PFG，<x, pt(y)>加入到WL（传播指向信息）。 -
遍历WL，取一个元素<n, pts>，除去pts中与pt(n)重复的对象得到
，调用Propagate(n,
n->s，将<s, pts>加入到WL（根据PFG将指向信息传递给同名指针）。 -
如果n表示一个变量x（x跟Store/Load指令相关），对
x.f = y的语句，调用AddEdge()将y -> oi.f加入到PFG，<oi.f, pt(y)>加入到WL（传播指向信息）；对S中所有类似Loady = x.f的语句，调用AddEdge()将oi.f -> y加入到PFG，<y, pt(oi.f)>加入到WL（传播指向信息）。
问题：
-
为什么要去重？避免冗余，英文叫做Differential propagation差异传播。
-
指针集用什么数据结构存储？混合集 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.指针分析如何处理函数调用
构造调用图技术对比：
- CHA：基于声明类型，不精确，引入错误的调用边和指针关系。
- 指针分析：基于pt(a)，即a指向的类型，更精确，构造更准的CG并对指针分析有正反馈（所以过程间指针分析和CG构造同时进行，很复杂）。
void foo(A a) { // pt(a) = ???
...
b = a.bar(); // pt(b) = ??? 把a的指向分析清楚了，就能确定a.bar()到底调用哪个对象的bar()函数，那么b的指向也明确了。
...
}
（1）调用语句规则
call语句规则：主要分为4步。
7-4-1-call规则.png
- 找目标函数m：Dispatch(oi, k)——找出pt(x)，也即oi类型对象中的k函数。
-
receiver object：把x指向的对象（
pt(x)）传到m函数的this变量，即mthis - 传参数：pt(aj), 1<=j<=n 传给m函数，即p(mpj), 1<=j<=n。建立PFG边，a1->mp1，...，an->mpn。
- 传返回值：pt(mret)传给pt(r)。建立PFG边，r<-mret。
问题：为什么PFG中不添加x->mthis边？因为mthis只和自己这个对象相关，而可能有pt(x)={new A, new B, new C}，指定对象的x只流向对应的对象，是无法跨对象传递的。
（2）过程间PTA算法
问题：由于指针分析和CG构造互相影响，所以每次迭代只分析可达的函数和语句。然后不断发现和分析新的可达函数。
可达示例：
7-4-2-可达示例.png
算法：黄色背景的代码是和过程内分析不同的地方。
7-4-3-PTA算法_过程间.png
符号：
-
mentry：入口main函数
-
Sm：函数m中的语句
-
S：可达语句的集合（就是RM中的语句）
-
RM：可达函数的集合
-
CG：调用图的边
步骤：基于调用规则来实现。
-
首先调用AddReachable(mentry)，将入口函数mentry的语句加到S中。处理New
x = new T()语句，把<x, {oi}>加入到WL；处理Assignx = y语句，调用AddEdge(y, x)加入边到PFG。 -
跟过程内指针分析一样，遍历WL，取一个元素<n, pts>，除去pts中与pt(n)重复的对象得到
n->s，将<s, pts>加入到WL（根据PFG将指向信息传递给同名指针）。 -
如果n表示一个变量x（x跟Store/Load指令相关），对
x.f = y的语句，调用AddEdge()将y -> oi.f加入到PFG，<oi.f, pt(y)>加入到WL（传播指向信息）；对S中所有类似Loady = x.f的语句，调用AddEdge()将oi.f -> y加入到PFG，<y, pt(oi.f)>加入到WL（传播指向信息）。 -
最后调用ProcessCall(x, oi)，处理与x相关的call指令。取出S中类似
r = x.k(a1,...,an)的调用语句L，首先调用Dispatch(oi, k)解出调用的目标函数m，把<mthis, {oi}>加入到WL（传递接收对象，上下文敏感分析将用到），将L->m这条调用边加入到CG；调用AddReachable(m)将新的语句加入到S，并处理New/Assign语句；调用AddEdge()将实参->形参、返回值->r边加入到PFG（传递参数、返回值），并将<形参,pt(实参)>、<r,pt(返回值)>加入到WL。
问题：为什么ProcessCall(x, oi)中，要判断L->m这条边是否已经加入到CG？因为x可能指向多个对象，就会多次处理L这个调用指令，可能x中别的对象oj早就已经将这条边加入进去了。
（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()；添加到调用图 | |||||
| 8 | [<B.foothis, {o4}>, <r, o11>] | {A.main(), B.foo()} | AddReachable(B.foo())；添加到可达函数 | |||||
| 9 | [<B.foothis, {o4}>, <r, o11>, <y, {o3}>] | {a->y, r->c}
|
AddEdge()；添加参数边、返回值边 | |||||
| 10 | [<r, o11>, <y, {o3}>] | <B.foothis, {o4}> | pt(B.foothis)={o4}； | while开头，B.foothis没有调用任何函数 | ||||
| 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)}，错误识别为调用边。
结果：
7-4-5-result.png
问题：没有入口函数的？如对库函数处理，生成调用库函数的程序。
今天喝了点wine，整理的有点魔幻。。
网友评论