前言
上节课中，我们初步学习了指针分析的概念和四大关键因素：堆抽象、上下文敏感性、流敏感性和分析范围。本节课，我们将继续学习指针分析，学习指针分析采用的规则、实现的方法和分析算法。
上节课提到，我们关心的语句有五类：New（如x = new T()）、Assign（如x = y）、Store（如x.f = y）、Load（如y = x.f）和Call（如r = x.k(a, ...)）。这节课我们只关注前四类语句，函数调用的指针分析将在下节课介绍。
指针分析规则
首先，我们介绍一下相关的域（domain）和记法：
- Variables: $x, y \in V$
- Fields: $f, g \in F$
- Objects: $o_{i}, o_{j} \in O$
- Instance fields: $o_{i}.f, o_{j}.g \in O \times F$
- Pointers: $\text{Pointer} = V \cup (O \times F)$
- Points-to relations: $pt: \text{Pointer} \rightarrow P(O)$
其中，$P(O)$表示$O$的幂集，$pt(p)$表示$p$的指向集合。
| 种类 | 语句 | 规则 | 图示 |
|---|---|---|---|
| New | i: x = new T() |
$\frac{}{o_{i} \in pt(x)}$ |  |
| Assign | x = y |
$\frac{o_{i} \in pt(y)}{o_{i} \in pt(x)}$ |  |
| Store | x.f = y |
$\frac{o_{i} \in pt(x),\ o_{j} \in pt(y)}{o_{j} \in pt(o_{i}.f)}$ |  |
| Load | y = x.f |
$\frac{o_{i} \in pt(x),\ o_{j} \in pt(o_{i}.f)}{o_{j} \in pt(y)}$ |  |
规则部分，横线上方是前提（premise），下方是结论（conclusion）。其中，New对应的规则的横线上方是空的，意味着无条件得出下方的结论。
指针分析实现
指针分析的目的是将指向信息在指针之间传播。值得一提的是，还有另外一种分析视角——Andersen-style analysis将指针分析视作指针的包含约束求解（inclusion constraints）。
指针分析实现的关键是，如果$pt(x)$改变了，应该将这种改变传播到$x$关联的指针上。图结构很适合这类分析。我们用指针流图（pointer flow graph，简称PFG）来表示程序中对象是如何在不同指针之间“流动”的，$pt(x)$需要被传播到图中$x$的所有后继节点上。
PFG的节点就是指针（$\text{Pointer} = V \cup (O \times F)$），代表变量或对象的域成员；对于边（$\text{Pointer} \times \text{Pointer}$）来说，一个$x \rightarrow y$的边表示指针$x$指向的对象可能（may）会流动到指针$y$。PFG的边需要根据程序语句和前面介绍的处理规则来添加：
| 种类 | 语句 | 规则 | PFG边 |
|---|---|---|---|
| New | i: x = new T() |
$\frac{}{o_{i} \in pt(x)}$ | N/A |
| Assign | x = y |
$\frac{o_{i} \in pt(y)}{o_{i} \in pt(x)}$ | $x \leftarrow y$ |
| Store | x.f = y |
$\frac{o_{i} \in pt(x),\ o_{j} \in pt(y)}{o_{j} \in pt(o_{i}.f)}$ | $o_{i}.f \leftarrow y$ |
| Load | y = x.f |
$\frac{o_{i} \in pt(x),\ o_{j} \in pt(o_{i}.f)}{o_{j} \in pt(y)}$ | $y \leftarrow o_{i}.f$ |
下面是PFG构建的一个例子：
在PFG的基础上，指针分析可以通过对该PFG计算传递闭包（transitive closure）来实现。如上图所示，指针$e$对于指针$b$来说是可达的，因此指针$b$指向的对象也可能被指针$e$指向。
时刻记得，本课程涉及的指针分析都是流不敏感分析，因此并不关注控制流顺序。
另外，“构建PFG”与“在PFG节点间传播指向关系信息”是互相依赖的。在指针分析的过程中，PFG是会动态更新的，而不是先构建PFG，再进行所谓的指针分析。
指针分析算法
接下来我们就开始研究指针分析算法。首先给出算法伪代码描述：
在目前为止我们所学的程序分析知识的基础上，这一算法是不难理解的。首先把所有创建新对象的语句处理一遍，因为它们是所有指向关系的源头和基础；紧接着是处理赋值语句，它将直接在PFG中变量之间添加边；最后是一个基于Worklist的循环，实现指向关系在指针间的传播。
Worklist包含了待处理的指向信息：$WL \subseteq \langle \text{Pointer}, P(O) \rangle ^\ast$。WL的每一项$\langle n, pts \rangle$都是指针$n$和指向对象集合$pts$构成的对，这些信息需要被传播到$n$的现有指向集合$pt(n)$中。
该算法实际上采用了差分传播（differential propagation）的思想，具体表现在while循环中：
$$ \Delta = pts - pt(n) \\ Propagate(n,\Delta) $$
这么做的目的是避免无意义的重复传播，提高效率。
下面是一个分析案例：
总结与思考
本节课，我们学习了指针分析规则、指针流图和指针分析算法。然而，目前的算法不涉及方法调用，留待下节课学习。
说起来，这个算法的处理步骤颇有“道生一，一生二，二生三，三生万物”的感觉。