南大《软件分析》9.0 Pointer Analysis Foundations I

首先给出了指针分析中常用的一些数学概念

由于上面这些概念对于理解后面的内容很关键（实在不理解可以根据后面的例子来边看边理解这些内容），所以这里对上面的一些符号表示做出一些解释：

x, y ∈ V：表示程序中出现的所有变量都包含在 V 中

f, g ∈ F：表示程序中出现的所有实例成员都包含在 F 中

oi, oj ∈ O：程序中所有根据 allocation site 分配的对象都包含在 O 中

oi.f, oj.g ∈ O × F：表示程序中所有出现的某个对象的成员都包含在 O × F 中

Pointer = V ⋃ (O × F)：Pointer 即指针，含义就是程序中所有的变量以及所有的对象成员都包含在 V ⋃ (O × F)

注意事项： 其中 pt(p) 可以理解为 p 的所有可能指向对象的集合。

Pointer Analysis: Rules

其次，这里分别给出了影响指针值的四种语句对应的 Rule，其中横线上方的属于前提，下方属于结论，kind new 其所对应的 Rule 上方为空，代表其为无条件满足。

上图为各个 Rule 所对应的图解说明。

How to Implement Pointer Analysis

指针分析算法的目标：

全程序的指针分析
易理解
易实现

指针分析本质上分析指针之间传播其所指向的对象集信息。算法实现的关键是：

when pt(x) is changed, propagate the changed part to the related pointers of 𝑥.

PFG

这里介绍一个重要概念 PFG（Pointer Flow Graph），PFG 是一个有向图，且其能够表示在指针之间的对象流动信息。其构成如下：

Nodes: Pointer = V ⋃ (O × F)
A node n represents a variable or a field of an abstract object
Edges: Pointer × Pointer
An edge 𝑥 → 𝑦 means that the objects pointed by pointer x may flow to (and also be pointed to by) pointer y

其中需要注意的是 PFG 的边的添加依赖于程序中的所有语句（statements）和对应的规则（前面提到的 rule）。

以下通过一个例子说明 PFG 的建立过程：

需要注意的是第5条语句e = d.f，由已知信息，这个信息可以理解为 c 和 d 都可以指向相同的这个对象，从而也就有了到 e 的这条边。

在实现指针分析这个算法上，建立 PFG 和在 PFG 上传播的 pt 集是相互依赖的，先来看下面这张图

前面在解释第5条语句的时候，利用到了 pt 集的信息，从而构建出了到 e 的这条边（PFG依赖pt）。但是 pt 集的信息也需要依赖 PFG 这个该怎么理解呢，上面这张图中给出的 pt 集可以看作是程序初始状态的 pt 集，随着 PFG 的建立，也会添加一些别的 pt 集信息，如下图所示：

而上面这些新的 pt 集信息则是根据 PFG 来创建出来的，因此，这两者之间是相互依赖的，这一点也会体现在后面具体的算法实现上。

Pointer Analysis: Algorithms

这一部分是重中之中，前面的铺垫都是围绕这个算法来进行的，下面来具体看看这个算法的表示形式：

首先来对这个算法的几个全局变量进行解释：

S：输入程序中所有的语句集合，类似于前面例子里面①..⑤那几个语句的形式

PFG：即指针流向图

WL：顾名思义工作列表，工作列表中包含所有需要被处理的 pts 信息，表示形式为 𝑊L ⊆ <Pointer,𝒫(O)>，每一个 WL 条目，由一个指针 n 和 pts（points-to set）构成，代表 pts 应该被传播到 pt(n)

这里对算法逐步进行解释：

首先是两条 foreach 遍历程序中所有 new 和 assign 语句（分别对应前面部分提到的两条rule所对应的语句，即 new 和 assign），这一部分相当于先初始化 WL 的内容，并且在 PFG 中添加分配边，需要注意的是前面这两部分并没有涉及到 store/load 两条语句，这会在后面进行处理。

其次，由于算法中调用了一个方法 AddEdge，这里来看看该方法的具体实现：

一开始先判断 s → t 这条边是否已在 PFG 中，若不存在则向 PFG 中添加这条边，同时如果 pt(s) 不为空，则将添加 <t, pt(s)> 到 WL，这句实际上意思就是说 pt(s) 的信息需要被传播到 pt(t) 中，但这个处理过程会放在后面的 while 循环中遍历处理。

总结：AddEdge 所做的就是两点：一是向源点和目标点添加一条边；二是将后继节点的 <t, pt(s)> 添加到 WL

这一部分再来关注while循环，首先会将 <n, pts> 从 WL 中移出，然后计算 Δ，值为 pts 减去 pt(n)，实际上这个 Δ 就是上面段话提到的需要将 pt(s) 传播到 pt(t) 中的剩余部分(x中已存在的信息不回被传播，如上图右边所示，已经包含在 x 中了，所以不会在 Δ 的范围内)。

同样的，上面的算法也引入了一个新的方法 Propagate，其具体内容如下：

首先判断 pts 是否为空，否则将其 pts 信息 union 到 pt(n) 中（这实际上就是我们前面一直所说的传播），第③部分同 addedge 中所做的最后一步一样，将所有在 PFG 中位于 n 的后继节点 s 添加 <s, pts> 添加到 WL，因为前面的结果不仅影响到当前节点 n，同时也影响到 n 的所有后继节点（传播）。