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

# Notations  pt(p)代表的是指针p可能指向的对象。如在下面的代码块后，pt(x)可能指向的目标可以记为
${o_2,o_4}$
（以行号作为object的下标）。
1
if(...){
2
x = new A();
3
} else {
4
x = new B();
5
}
Copied!

# Pointer Analysis: Rules     ## Summary # How to Implement Pointer Analysis • 前提：y=x.f
$o_i \in pt(x)$
• 结论：
$pt(o_i.f) \subset pt(y)$
Key to implementation: when 𝑝𝑡(𝑥)is changed, propagate the changed part to the related pointers of 𝑥 ## Pointer Flow Graph

Pointer Flow Graph (PFG) of a program is a directed graph that expresses how objects flow among the pointers in the program.

• Node: 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 𝑥 may flow to (and also be pointed to by) pointer 𝑦 ## Example

$o_i$
，根据上述规则，我们能够从左侧的程序语句从上到下构建出右侧的指针流图。  PFG的整个构造过程，需要在构建PFG和在已有的PFG上传递指向关系这两个步骤间循环往复。这两个步骤是相互依赖的，所以需要精心设计算法来实现分析。 # Pointer Analysis: Algorithms

## Introduction to algorithm

• 由于做流不敏感分析。输入为Set，丢失了语句的顺序关系也没关系。
• WorkList：保存接下来要处理的指向信息，与BFS中的队列作用类似。
• pts定义：Each worklist entry 𝑛, 𝑝𝑡𝑠 is a pair of pointer 𝑛 and points-to set 𝑝𝑡𝑠, which means that 𝑝𝑡𝑠 should be propagated to 𝑝𝑡(𝑛)
• E.g.,
$[(x,\{o_i\}),(y,\{o_j, o_k\}),(x.f,\{(o_l)\}),\dots]$ ## Handling of New and Assign • 前三行代码做初始化的工作，并针对所有的New语句，将所有的初始指向关系加入WorkList。注意pt(n)初始化后为空集{}，随着算法的迭代会增加元素。
• 之后的两行代码处理Assign语句，添加y->x的边到PFG中。添加边的具体算法如下 ### Propagate  ### Detial-Differential Propagation

1
Solve(𝑆)
2
...
3
while WL is not empty do
4
remove 𝑛, 𝑝𝑡𝑠 from WL
5
Δ = pts – pt(n) // Differential Propagation
6
Propagate(n, Δ) // Differential Propagation
Copied! $\{o_1, o_3\}$ $\{o_5\}$ • In practice, Δ is usually small compared with the original set, so propagating only the new points-to information (Δ)
• Besides, Δ is also important for efficiency when handling stores, loads, and method calls, as explained later ## The Algorithm-Review ## Example

1
b = new C();
2
a = b;
3
c = new C();
4
c.f = a;
5
d = c;
6
c.f = d;
7
e = d.f;
Copied! # Key points

• Rules for pointer analysis
• PFG(Pointer flow graph)
• Algorithm for pointer analysis