Skip to the content.

Interprocedural-Analysis 过程间分析

Motivation

之前的章节中都没有考虑方法调用,然而在实际的程序中方法调用非常常见,那么我们如何分析带方法调用的程序呢?最简单的处理方式是(这里仍然以常量传播作为一个例子):做最保守的假设,即为函数调用返回NAC。而这种情况会丢失精度引入过程间分析能够提高精度。如果使用最简单的处理方式,下图中的n和y分析结果都不是常量,尽管我们能够一眼看出他们的运行时值是n=10,y=43。

image-20220107114512388

Definition of Call Graph 定义调用关系图

A representation of calling relationships in the program.

调用关系图表达调用关系(中文讲起来确实很奇怪),一个简单的例子如下:

image-20220107150238931

Call Graph Construction 调用关系图构造

Call Graph有很多种不同的构造方法,我们接下来会讲解两个极端:

最准确(Pointer Analysis)和最快速(Class Hierarchy Analysis)。

image-20220107150252086


Call types in Java ( Java中调用的类型 )

本课主要关注Java的调用关系图构建。为此,我们需要先了解Java中调用的类型。Java中call可分为三类(不需要理解透彻,之后会详细介绍):

image-20220107150646057

Virtual call and dispatch 虚拟调用和调度

Virtual call是几种调用中最为复杂的一种,我们首先重点讨论它。在动态运行时,Virtual call基于两点决定调用哪个具体方法:

  1. Type of object
  2. Method signature
    • Signature = class type + method name + descriptor
    • Descriptor = return type + parameter types

image-20220107153346073Java中Dispatch机制决定具体调用哪个方法:c是一个类的定义,m是一个方法。如果能在本类中找到name和descriptor一致的方法,则调用c的方法,否则到父类中寻找。

We define function Dispatch(𝑐, 𝑚) to simulate the procedure of run-time method dispatch.

练习问题

Q:两次对foo的调用分别调用了哪个类的foo?

image-20220107153400873

A:分别调用A和C中定义的foo方法。

image-20220107153500519


Class Hierarchy Analysis (CHA) 类继承分析

Definition of CHA 定义CHA

Call Resolution of CHA

Algorithm of Resolve

下面介绍解析调用的算法。

image-20220107151331750

Static call 静态调用

image-20220107151414307

Special call 特殊调用

image-20220107151421589

image-20220107151629828

Virtual call

image-20220107151836029

一个例子

三个调用都是Virtual call。是上述算法中的第三种情况。

image-20220107152329361

CHA的特征

  1. 只考虑类继承结构,所以很快
  2. 因为忽略了数据流和控制流的信息,所以不太准确

CHA的应用

常用于IDE中,给用户提供提示。比如写一小段测试代码,看看b.foo()可能会调用哪些函数签名。可以看出CHA分析中认为b.foo()可能调用A、C、D中的foo()方法。(实际上这并不准确,因为b实际上是B类对象,不会调用子类C、D中的方法,但胜在快速)

image-20220107152401284

Call Graph Construction调用关系图构造

Idea

image-20220107152420605


Algorithm 迭代算法

image-20220107152432496

Example
  1. 初始化

image-20220107152442884

  1. 处理main后向WL中加入A.foo()

image-20220107152448377

  1. 中间省略一些步骤,这里面对C.bar()时,虽然会调用A.foo(),但由于A.foo()之前已经处理过(在集合RM中),之后不会再进行处理

image-20220107152453913

  1. 这里C.m()是不可达的死代码

image-20220107152503008

注:忽略new A()对构造函数的调用,这不是例子的重点。


Interprocedural Control-Flow Graph 过程间控制流图

ICFG = CFGs + call & return edges

ICFG可以通过CFG加上两种边构造得到。

  1. Call edges: from call sites to the entry nodes of their callees
  2. Return edges: from return statements of the callees to the statements following their call sites (i.e., return sites)

例如:

image-20220107152541657

image-20220107152547949

Interprocedural Data-Flow Analysis 过程间数据流分析

定义与比较

目前这一分析领域没有标准方法。首先对过程间和过程内的分析做一个对比,并以常量传播(本校同学第一次实验作业主题,需要一到六课的基础)为例子进行解释。

image-20220107152757201

Edge transfer处理引入的call & return edge。为此,我们需要在之前章节的CFG基础上增加三种transfer函数。

image-20220107152805475

Example

image-20220107152813946

小问题

这一段有存在的必要吗?

image-20220107152820121

Such edge (from call site to return site) is named call-to-return edge. It allows the analysis to propagate local data-flow (a=6 in this case) on ICFG.

如果没有这一段,那么a就得“出国”去浪费地球资源——在分析被调用函数的全程中都需要记住a的值,这在程序运行时会浪费大量内存。

image-20220107152843173

要记得在调用语句处kill掉表达式左边的值,否则会造成结果的不准确,如:

image-20220107152854591

过程间分析有多重要?

讲到这里,我们回到故事的开头,看看过程间分析的引入到底能带来多大的精度提高吧。上述例子应用过程间分析的完整推导如下:

image-20220107152937742

而如果只做过程内分析,则精度大大下降

image-20220107152942920