参考：
【课程笔记】南大软件分析课程7——指针分析基础（课时9/10） - 简书
--------------------------------------------------------------
1. 指针分析规则
规则：采用推导形式，横线上面是条件，横线下面是结论。
- New：创建对象，将
new T()对应的对象oi加入到x指向的指针集。 - Assign：将y指向的指针集加入到x指向的指针集。
- Store：将y指向的指针集加入到oi.f指向的指针集
-
Load：Store的反操作。
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。
示例：
PTA步骤：
- 构造PFG（根据以上示例，PFG也受指向关系影响）
- 根据PFG传播指向信息
3. 指针分析算法
（1）过程内PTA算法
符号：
-
S：程序语句的集合。
-
WL：Work list，待合并的指针信息，二元组的集合，<指针n，指向的对象集合pts>。pts将被加入到n的指向集pt(n)中。
-
PFG：指针流图。
问题：
-
为什么要去重？答：避免冗余，英文叫做Differential propagation差异传播。
-
指针集用什么数据结构存储？混合集 Hibra-set，集合元素小于16个用hash set，大于16个用big-rector 位存储。
-
开源项目有哪些？Soot、WALA、Chord。
（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;
4. 指针分析如何处理函数调用
构造调用图技术对比：
- CHA：基于声明类型，不精确，引入错误的调用边和指针关系。
- 指针分析：基于a指向的类型，更精确，构造更准的CG并对指针分析有正反馈（过程间指针分析和CG构造同时进行）。
（1）调用语句规则
call语句规则：主要分为4步。
- 找目标函数m：Dispatch(oi, k)——找出oi类型对象中的k函数，若没找到，则从父类找。
- receiver object：把x指向的对象oi传到m函数的this变量。
- 传参数：pt(aj), 1<=j<=n 传给m函数，即pt(mpj), 1<=j<=n。并建立PFG边，a1->mp1，...，an->mpn。
- 传返回值：pt(mret)传给pt(r)。并建立PFG边，r<-mret。
问题：为什么PFG中不添加oi->mthis边？
因为mthis只和oi的类型对象相关，而可能有pt(x)={new A, new B, new C}，使得pt(x)中的所有对象都流向了mthis。
（2）过程间PTA算法
问题：由于指针分析和CG构造互相影响，所以每次迭代只分析可达的函数和语句。然后不断发现和分析新的可达函数。
可达示例：
算法：黄色背景的代码是和过程内分析不同的地方。
符号：
-
mentry：入口函数
-
Sm：函数m中的语句
-
S：可达语句的集合（就是RM中的语句的集合）
-
RM：可达函数的集合
-
CG：调用图的边
-
l：调用语句
-
m：目标函数
问题：为什么ProcessCall(x, oi)中，要判断
L->m这条边是否已经加入到CG？因为x可能指向多个对象，就会多次处理ProcessCall(x, oi)，可能x中别的对象oj也指向这个目标函数m，已经将这条边加入进去了。
（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 }
如果是CHA的话，CG={5->B.foo(A), 5->A.foo(A)}，错误识别调用边。
结果：
问题：没有入口函数的？
如对库函数处理，生成调用库函数的程序。
