# 指针分析理论（下）

首先回顾一下在上一篇文章中列出的大纲。

1. Pointer Analysis: Rules
2. How to Implement Pointer Analysis
3. Pointer Analysis: Algorithms
4. Pointer Analysis with Method Calls

承接上一篇，本文谈谈包含指针分析如何处理函数调用。接下来用指针分析的方式来构建Call graph，先来对比一下CHA和指针分析两种方法：

* CHA: imprecise, introduce spurious call graph edges and points-to relations
* Pointer analysis: more precise than CHA, both for call graph and points-to relations(a.k.a on-the-fly call graph construction)

## Pointer Analysis with Method Calls

本课将给出一个包含函数间分析的适用于全程序的算法。

考虑下面这样一小段代码，显然，我们必须要有过程间的分析，才能有更准确的分析结果。

```java
void foo(A a) {
    …
    // 𝑝𝑡(𝑎) = ?
    b = a.bar();
    // 𝑝𝑡(𝑏) = ?    
    …
}
```

### Rule for Call

和过程间分析紧密相关的是过程调用的处理。也就是上节课提到的最后一条与Call有关的规则。

这个规则看起来复杂得多，我们一点一点来解析。首先，请读者们暂停一下，回忆一般语言如何处理过程调用。即过程调用时到底发生了什么。

各个符号的定义为：

![](https://4182415683-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MJC1RRYQ991XoNX219t%2Fuploads%2Fgit-blob-cb0a109a34901a3365e82015006f18d33cedf2d4%2Fimage-20201201151956869.png?alt=media)

![](https://4182415683-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MJC1RRYQ991XoNX219t%2Fuploads%2Fgit-blob-e56c02b59eff96661bb4333da1a4e65ded2def6d%2Fimage-20201126230831572.png?alt=media)

> 一个参考答案：保存现场，构造调用栈帧，传递参数，跳转到目标函数开始执行……目标函数执行完毕跳转回来，后从预定的位置取返回值（若需要），恢复现场，继续往下执行……

在静态分析中，我们更多地关心数据流，而非控制流。而针对Java，处理函数调用的数据流可以分为以下四个部分：

1. 确定目标方法。用第7课介绍过的Dispatch函数完成。
2. 传receiver object

![](https://4182415683-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MJC1RRYQ991XoNX219t%2Fuploads%2Fgit-blob-cf2f33e52e524737490de273452c7d6aa8bf9392%2Fimage-20201126184745576.png?alt=media)

1. 传参数

![](https://4182415683-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MJC1RRYQ991XoNX219t%2Fuploads%2Fgit-blob-09b059d7e02b025dbfe44940cfc15407020da2d1%2Fimage-20201126185008506.png?alt=media)

1. 传返回值

![](https://4182415683-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MJC1RRYQ991XoNX219t%2Fuploads%2Fgit-blob-95ebc7b7ffc9e4e684ea64bf84a76584b37abe77%2Fimage-20201126185233403.png?alt=media)

因此，我们可以对应规则，在PFG上添加Edge实现过程间信息的传递。完整的规则如下：

![](https://4182415683-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MJC1RRYQ991XoNX219t%2Fuploads%2Fgit-blob-191d4ddf762959928b517f05a0021e04fb499023%2Fimage-20201126231116221.png?alt=media)

#### Detail-1

**Question: Why not add PFG edge 𝑥 →** $$𝑚\_{𝑡ℎ𝑖𝑠}$$**？**

通过这两个图可以直观地说明原因：

![](https://4182415683-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MJC1RRYQ991XoNX219t%2Fuploads%2Fgit-blob-a231743a54ae179375f08d7bfe7cc32832de3366%2Fimage-20201126231403264.png?alt=media)

![](https://4182415683-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MJC1RRYQ991XoNX219t%2Fuploads%2Fgit-blob-359e5410a80457852616df49fef09c59ccc21901%2Fimage-20201126231437769.png?alt=media)

*在每次算法执行时，*$$o\_i$$*是确定的某个（只有一个）对象，然后针对这个对象做Dispatch，能够找到对应的唯一的receiver object.*

#### Detail-2

像之前用CHA做过程间分析时一样，我们需要将分析的过程和Call graph构建的过程结合起来。

![](https://4182415683-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MJC1RRYQ991XoNX219t%2Fuploads%2Fgit-blob-5061652e0ced6333c92c820a56ffd22097fdc6bb%2Fimage-20201126231722298.png?alt=media)

不同的是，这次我们只分析从main方法（或者一般性地说，程序入口）开始可达的部分。原因有二：

1. 提升分析速度。因为我们能够避免分析不会被执行到的死代码。
2. 提升分析精度。避免了unreachable部分的代码调用reachable部分方法时可能引起的精度下降。

![](https://4182415683-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MJC1RRYQ991XoNX219t%2Fuploads%2Fgit-blob-5e5d3a78512d82fdfb32d8c3d14fecb0521ca480%2Fimage-20201126191225969.png?alt=media)

## Algorithm: PA with Method Calls

接下来介绍一个具体的、易于理解和实现的算法。由于指针分析是静态程序分析的基础，理解了这个看起来枯燥的算法后，更容易在静态程序分析领域触类旁通。~~而且据说后面两节课会学得更加轻松~~

![](https://4182415683-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MJC1RRYQ991XoNX219t%2Fuploads%2Fgit-blob-dfe4105d384211b4e1eb0b55cc3044d23a05491b%2Fimage-20201126191650221.png?alt=media)

算法整体上来说和上一节课所介绍的大框架相似，黄色标记的部分是这次新加入的部分。绿色部分是对新的全局变量的说明：

* S里的statements就是RM里methods的statements（语句）
* Call Graph和指针集作为最后的输出。

### Function: AddReachable

AddReachable的作用是：

* **输入参数**m是最新的可达方法。
* 函数修改维护全局的RM、S和$$S\_m$$，并处理新的方法m中的New和Assign语句。

![](https://4182415683-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MJC1RRYQ991XoNX219t%2Fuploads%2Fgit-blob-8a4297f142773a4d3867a9443ea56e5cf9d4a55f%2Fimage-20201126194125039.png?alt=media)

#### Detail-3

**Question: 为什么要检查l->m是否在CG中，即为什么同样的l->m可能不止一次地被处理？**

*l代表call site。可以用行号作为call site的label。*

> Answer: $$o\_j, o\_k$$同样可能通过Dispatch返回同一个m。

### Function:ProcessCall

ProcessCall的作用是：

* 输入的$$o\_i$$是x新指向的目标。
* 函数在可达的语句集合S中，选择所有与x有关的过程调用，做之前提到的数据流相关四步处理（确定被调用方法、传对象、传参数，传返回值）。

![](https://4182415683-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MJC1RRYQ991XoNX219t%2Fuploads%2Fgit-blob-c580c62ad5f056b5ec6664ffbe155c7c017eb0e3%2Fimage-20201126195311513.png?alt=media)

![](https://4182415683-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MJC1RRYQ991XoNX219t%2Fuploads%2Fgit-blob-989236edd7c8504f26704a7a20e0d000724acb53%2Fimage-20201126195425756.png?alt=media)

## Example

**利用之前学习的算法分析以下代码，构建Call graph和PFG。**

```java
class A {
    static void main() {
        A a = new A();
        A b = new B();
        A c = b.foo(a);
    }
    A foo(A x) { … }  
}
class B extends A {
    A foo(A y) {
        A r = new A();
        return r;
    }
}
```

答案如下：

![](https://4182415683-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MJC1RRYQ991XoNX219t%2Fuploads%2Fgit-blob-407c3e59c3712f6ef477770c9de1fb81582710be%2Fimage-20201126201000426.png?alt=media)

这个流不敏感的分析算法在分析精度上仍然可以改进。我们将在接下来的课程中学习精度更高的流敏感分析。

## Key points

* Pointer analysis **rule for method call**
* **Algorithm** for inter-procedural pointer analysis
* **On-the-fly call graph construction**


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://ranger-nju.gitbook.io/static-program-analysis-book/ch3/pointer-analysis/03-03-pointer3-analysis-spa.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.