Motivation#

CHA 只关注 class hierarchy 存在很大的局限性，在形如 Number n = new One() 的声明后调用 n 的某个 method 会得到多个 call target，实际其中只有一个 target 是真的，同时运用 constant propagation 会得到 NAC 的结果，是 inefficient 且 imprecise 的。

而 pointer analysis 是基于 point-to relation 的，不会出现上述情况。

Introduction to Pointer Analysis#

pointer analysis 是一个 fundamental 的 analysis，对于 OOPL，它需要解决的问题是一个指针可能指向哪些 object，同样也是为了 safety，使用的是一种 may-analysis (over-approximation)。

alias analysis 解决的问题是两个指针是否指向的是同一个 object，可以从 pointer analysis 中推导得出。

“Pointer analysis is one of the most fundamental static program analyses, on which virtually all others are built.”¹

Key Factors of Pointer Analysis#

pointer analysis 是一个较为复杂的系统性的分析，不同的 factors 会影响整个系统的 efficiency 和 precision。

factors 主要有四种：heap abstraction、context sensitivity、flow sensitivity、analysis scope。

Concerned Statements#

在 pointer analysis 中，我们只关注 pointer-affecting statements。

在 Java 中，pointers 可以分为以下几类：

• local variable: x

• static field: C.f $\leftarrow$ sometimes referred as global variable

• instance field: x.f $\leftarrow$ modeled as an object with a field

• array element: array[i] $\leftarrow$ ignore indexes. modeled as an object with a single field (may point to any value in array)

  由于在实际的代码中，array 的下标往往是以变量的形式在循环中进行访问的，这在 static analysis 中是无法进行分析的，所以我们需要忽略下标抽象为一个 object with a single field 进行 may-analysis。

  

pointer-affecting statement 可以分为以下几类：

• new: x = new T()
• assign: x = y
• store: x.f = y
• load: y = x.f
• call: r = x.k(a, ...) $\leftarrow$ Complex memory-accesses will be converted to three-address code
  • focus on virtual call

Rules#

How to Implement Pointer Analysis#

pointer analysis 的本质是在 pointers 之间 propagate point-to information，所以它的关键在于当 $pt(x)$ 改变时，要如何将 changed part propagate 到相关的 pointers。

Andersen style analysis: Pointer analysis as solving a system of inclusion constraints for pointers.³

类似于前面 control-flow 的解决方法，我们同样构建一张有向图，point-to information 可以通过有向边进行流动从而更新结点信息。

• nodes: Pointer = $V\cup (O\times F)$
• edges: Ponter $\times$ Pointer (may flow to)

对于 c.f = a 这种涉及 $o_i.f$ 的语句， $o_i.f$ 才是真正的 “variable”，因此在图上使用 $o_i.f$ 表示一个 node。

构建好 PGF 之后，pointer analysis 可以通过计算 PGF 上的 transitive closure 得到。

由于前面提到的 $o_i.f$ 在图上的表示问题（variable 和 $o_i.f$ 之间连边或者 $o.f$ 之间连边），我们可以看出来 build PFG 和 propagate point-to information on PFG 两者是互相依赖的，也就是说，PGF 是在 pointer analysis 的过程中 dynamically updated。

Alogorithms#

目前的这个 context-insensitive 的算法还是比较 trivial 的，仍然是一个 SPFA（那个已经死掉了的算法）的思路，不过这里将 4 个 rules 分别进行处理，analysis 和 build PGF 的过程是相互依赖的，analysis 的初始化对应 x = new T() rule，而 build PGF 的初始化对应 x = y rule，处理完之后利用 worklist 对 x.f = y 和 y = x.f 一边 analysis 一边 build。

需要注意的是这里的 differencial propagation $\Delta=pts-pt(n)$ ，这是一种在 program analysis 中常见且非常有效的方法，可以降低时间复杂度和空间复杂度。

Pointer Analysis with Method Calls#

显然，inter-procedural pointer analysis 需要建立 call graph。在 call graph 的建立上，CHA 根据 declared type of $a$ 来解决 call targets，而 pointer analysis 根据 $pt(a)$ 来判断。由前面对 CHA 的分析可以知道，CHA 会引入 spurious call graph edges 和 point-to relations。

PFG 中对于 call statement 的 rule 如下图所示。

由于在 $pt(x)$ 中不同的 $o_i$ 对应的 method 可能不同，所以 PFG 中不会添加 $x\to m_{this}$ 这条边。

与 PFG 的 build 一样，call graph 和 pointer analysis 也是互相依赖、同时进行的（也被称为 on-the-fly call graph construction）。在 pointer analysis 中，call graph 形成的是一个「reachable world」，除了 entry methods 以外所有的 reachable methods 都是在 pointer analysis 的过程中逐渐发现的，并且我们只会分析 reachable methods。

pointer analysis with method calls 的算法与前面的算法大体相同，除了图中的黄色部分是新加入的。

Introduction#

在动态执行的过程中，一个 method 可能在不同的 context 中被 call，使用 context insensitive (C.I.) 的分析方法会使得不同上下文中的不同的 object 流入一个 method 造成 spurious data flow，于是我们需要引入 context sensitive (C.S.) 的分析方法来提升精度。

C.S. 区分上下文有很多种方法，下面以 call site 方法为例。在 C.S. 中，最直接的引入上下文的分析方式是 clone-based context sensitive analysis：将 variables 和 methods 通过 contexts 进行 qualify，在每一个 context 下都维护 variables 和 methods 的 clone。

OOPs 通常是 heap-intensive 的，对于每一个 object 也用 context (heap-context) 进行 qualify，通常使用被 allocate 时的 context 作为标识。

Rules#

在 context sensitive 的分析的表示方法中，每个 domain 都加入了一维 context。

值得注意的是，在对 call 的处理中加入了一个 Select(c, l, c': o_i) 函数，基于 call site $l$ 时的信息来选择对应的 context

Algorithms#

context sensitive pointer analysis 其实就相当于在 C.I. 的基础上加入一维信息作为 context，同时在处理 method call 时需要使用一个 select 函数选取这个 method 的 context。

以上这张图是一个 example，如果我们将第二行的 y = id(n2) 改成 x = id(n2) 那么使用 C.S. 方法分析得到的 i 可能的 pointers 中仍然会有 spurious target，这种问题对应的则是 flow sensitivity。

C.S. 的算法如下：

可以看出 C.S. 的处理方法和 C.I. 的处理方法几乎一致，而 AddEdge 和 Propagate 更是一样。

Context Sensitivity Variants#

context sensitivity variants 可以有很多种，这里仅仅介绍了 call-site、object、type 这三种。