写在前面的话
本渣有幸成为南京大学软件学院研究生，在前往仙林校区蹭课的时候偶然发现了这门宝藏课程，听了以后感觉深有收获，但又因为课程难度较大，国庆假期归来发现遗忘较多，因此开了一坑来记录自己对每节课知识点的理解。也由于这是本人第一次开坑写博客，结构内容自有诸多不合理之处，希望有问题的地方大家可以指出。
系列文章目录
1.静态程序分析(Static Program Analysis)介绍
2.中间表示(Intermediate Representation)
3.数据流分析(Data Flow Analysis) (上)：可达性分析(Reaching Definitions)
4.数据流分析Data Flow Analysis) (下)：存活变量分析(Live Variables Analysis)及可用表达式分析(Available Expressions Analysis)
5.数据流分析基础(Data Flow Analysis-Foundations)
6.过程间分析(Interprocedural Analysis)
7.指针分析(Pointer Analysis)入门
8.指针分析基础知识(Pointer Analysis Foundations)
一、指针分析的规则
1.1 语句、域与符
上一篇文章中提到了如图五种会对指针指向的域产生影响的语句：
1.2 规则
1.2.2 Assign语句
1.2.4 Load语句
如上代码中假设a指向o1，b指向o2，那么正常来说x应该指向{o1, o2}，但是如果改成等 的话，在第二步x会指向o2，然后x反向传播使得a变成指向o2，就产生了假指针了。
这原本是 Steensgard style的一种指针分析方式，提出时间很早，由于当年的计算机硬件水平很低，此方法的提出旨在降低精度的同时大大提高效率，可如今已经不需要这种方法了。
二、如何实现指针分析
本质上，指针分析是将指向信息传播到由变量和字段构成的指针之间的过程。根据Andersen1994年提出的理论，指针分析是一种解决指针包含约束的系统，这中包含关系可以从1.2.5的图中看出。
为了实现指针分析，我们可以通过一张图来链接相关联的指针，当x的指针域pt(x)改变的时候，将改变的部分传递给x的后继。
2.1 指针流图(Pointer Flow Graph, PFG)简介
程序的指针流图是一种有向图，表示对象如何在程序中的指针之间流动。
- 节点：一个节点n表示一个变量或一个抽象对象的域，表示为 Pointer = V ? (O × F)
-
由上述过程，可以总结出指针分析主要有两个过程，一是画指针流图，二是在指针流图中更新指向信息，这两个过程交互着动态进行的。例如在画第五条边的时候就需要前面的指向信息才能画出。
三、指针分析算法
3.4 总结
以上便是整个指针分析的算法了，首先对整个程序语句进行分析，用其中的New语句和Assign语句进行初始化，得到一个部分的PFG，然后利用WL的迭代反复补充指向关系和流向关系，完善PFG中的边和节点的指向信息。
下面是一个例子的其中一步，可以大概地了解这个过程。
四、方法调用中的指针分析算法
4.1 CHA与Pointer analysis的区别
过程间的指针分析需要用到调用图call graph，这就让我们想起在第六章中讲到的CHA算法，下面来看一个例子：
- CHA：基于来处理调用信息，不精确，会引入虚假的调用边和指向关系。
- Pointer analysis：基于来处理调用信息，比较精确，因为用指针分析构造call graph，所以同时考虑到调用图和指向关系。
4.2 指针分析中的调用规则
相对于之前的过程内的指针分析算法，黄色部分是改变的部分。之前的算法的输入是程序所有语句S，而现在是分析程序的入口mentry，是一种可达性的分析，即每次操作只分析从当前处可以到达的方法，这样可以有效地减少分析时间，提高分析精度(因为这样减少了无用数据流)。
接下来解释一下用到的参数：
- S：可以到达的语句的集合
- Sm：在方法m中的语句集合
- RM：可以到达的方法的集合
- CG：调用图的边
4.3.2 初始化算法
整个算法的初始化通过第一个新增函数AddReachable(m)完成。
处理方案如红框所示，与3.2和3.3内容差不多，不赘述。
4.3.4 处理函数调用语句
简单地举个例子，可以看出各个集合中的状态如图所示，跟着走一遍差不多就懂了。
五、总结
个人觉得指针分析这块内容还是挺复杂的，需要配合上一篇文章仔细看看才能大概搞懂，如果有写的不清楚的地方欢迎讨论。
声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！