实现指针分析
实现指针分析,关键在于将指向关系在指针间进行传播。当x的指向产生变化时,将变化的部分传播给和x有关的指针。
指针流图
指针流图(PFG)是一个有向图,表达对象在指针间的流动。
节点:指针
边:$x\rightarrow y$表示指针$x$指向的对象可能会流向指针$y$(即可能被其指向)
Kind | Statement | PFG Edge |
---|---|---|
New | x = new T() | N/A |
Assign | x = y | $x \leftarrow y$ |
Store | x.f = y | $o_i.f \leftarrow y$ |
Load | y = x.f | $y \leftarrow o_i.f$ |
建立PFG和传播指向信息是相互促进的,在指针分析的过程中PFG是会不断更新的。
算法
WorkList
Worklist(WL)包含需要处理的指向关系
- $WL\subseteq <Pointer, P(O)>^*$
其中的每一项$<n,pts>$包含指针$n$和指向集合$pts$,而$pts$需要传播到$pt(n)$中