

首页  思维导图  详情



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 的后继者。

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)

算法的一个例子

过程

结果

 收藏

立即使用

P15

 收藏

立即使用

P14

 收藏

立即使用

P16

 收藏

立即使用

czgggggggg

职业：研究生

去主页

 Collect

Get Started

p2p还款

 Collect

Get Started

p2p投资

 Collect

Get Started

P2P公司关系图

 Collect

Get Started

10-10-10旁观思维





0 条评论

下一页