P9-10
2021-04-30 15:57:59 1 举报AI智能生成
南大软件分析P9-10
作者其他创作
大纲/内容
Pointer Analysis: Rules
Pointer-Affecting Statements（指针影响的语句）
Domains and Notations（域和符号）
Rules（规则）
概览
New
Assign
Store
Load
总结
How to Implement Pointer Analysis
我们的指向分析算法
完整的全程序指针分析
精心设计，易于理解
易于遵循和实施
如何实现指向分析？
本质上，指向分析是在指针（变量和字段）之间传播指向信息（points-to information）。
指向分析作为解决指针包含约束的系统
Key to implementation: when pt(x) is changed, propagate the changed part to the related pointers of x.
实现的关键：更改 pt(x) 时，将更改的部分传播到 x 的相关指针。
实现的关键：更改 pt(x) 时，将更改的部分传播到 x 的相关指针。
解决方案
•我们使用图来连接相关的指针。
•当pt(x)更改时，将更改的部分传播给 x 的后继者。
•我们使用图来连接相关的指针。
•当pt(x)更改时，将更改的部分传播给 x 的后继者。
Pointer Flow Graph (PFG)
定义
程序的指针流图是一个有向图，表示对象如何在程序的指针之间流动。
节点
Pointer = V ⋃ (O × F)
节点n表示抽象对象的变量或字段。
边
Pointer × Pointer
边 x->y 表示指针指向的对象 x 可能会流向指针 y（也被指针y指向）。
边
PFG边是根据程序的语句和相应的规则添加的。
一个例子
使用PFG，可以通过计算PFG的传递闭包（transitive closure）来解决指向分析。
例如，从PFG上的b可以到达e，这意味着b指向的对象可能会流向e，也可能由e指向。
实现指向分析
PFG在指向分析期间动态更新
Pointer Analysis: Algorithms
算法
Worklist (WL)
工作清单包含要处理的指向信息
WL ⊆ <Point, p(O)>*
每个工作列表条目 <n, pts> 是一对指针 n 和指向集合set的对，这意味着 pts 应该传播到 pt(n)
例如[<x, {oi}>, <y,{oj, ok}>, <oj.f, {ol}>...]
Handling of New and Assign
确保由 s 指向的每个对象也由 t 指向
Differential Propagation（差分传播）
采用差分传播以避免传播和处理多余的信息点。
pt(n) 中现有的指向信息已经传播给 n 的后继者，而无需再次传播。
例子
实际上，与原始集合相比，Δ通常较小，因此仅传播新的指向信息（Δ）可以提高效率。
此外，如后所述，在处理存储，负载和方法调用时，Δ对于效率也很重要。
Handling of Store and Load
新的指向信息可能会引入新的PFG边。
算法的一个例子
过程
结果
Pointer Analysis with Method Calls
存在方法调用时的指向分析
前面的指向分析存在的问题
过程间指向分析需要调用图
CHA：根据声明的类型解析调用目标
指针分析：基于 pt(a) 解析调用目标
调用图构造
CHA：不精确，引入虚假的调用边和指向关系
指向分析：对于调用图和指向关系，都比CHA更为精确
又称即时调用图构造
Rule: Call
规则
符号的含义
Dispatch(oi, k)：将 oi 上 k 的虚拟分配解析为目标方法（基于 oi 的类型）
mthis: m 的 this 变量
mpj: m 的 第 j 个参数
mret: 保存 m 的返回值的变量
例子
一个问题
为什么不添加 PFG 边 x -> mthis ？
接收对象应该只流到相应目标方法的this变量
PFG边 x -> mthis 会为此变量引入虚假指向关系
添加了 PFG 边 x -> mthis
没有添加 PFG 边 x -> mthis
Interprocedural Pointer Analysis（过程间指向分析）
与调用图构造一起运行
调用图形成“可到达的世界（reachable world）”
从一开始就可以使用入口点方法（例如main方法）
在分析过程中逐渐发现了其他可达的方法
仅分析可达的方法和语句
算法
总览
AddReachable(m)
扩展“reachable world”
起点为入口点方法
发现新的CG边
S
可达语句（statement）的集合
Sm
方法m中的语句的集合
RM
可达方法的集合
ProcessCall(x, oi)
CG 调用图边
Algorithms Output
Points-to Relations (pt)
Call Graph (CG)
算法的一个例子
过程
结果
0 条评论
下一页
