资料： https://www.bilibili.com/video/BV1GQ4y1T7zm?from=search&seid=7528278619420042576

01:30 Motivation

04:40 Call Graph Construction(CHA)

65:40 Interprocedural Control-Flow Graph

71:45 Interprocedural Data-Flow Analysis

Problem of Intraprocedural Analysis

过程内的常量传播过于保守，造成结果的不准确

如上所示，对于一个常量传播:

void foo() {
  int n = ten();  // 返回一个常量10
  addOne(42); // 传出一个常量42
}

int ten() {
  return 10;
}

int addOne(int x) {
  int y = x + 1;  // y值本程序中是确定的，但是只做过程内分析是不确定的。
  return y;
}

涉及到过程间方法调用的元素： 1. Call site(实参) 2. function decl(形参) 。

实际上，在分析foo的时候n就是10, 在分析addOne的时候x就是42,y就是43，但是过程内分析的时候，是不知道过程外的信息的，因此这里就是NAC。

在传统的过程内分析中，都是保守的假设(safe-approximation)。

在过程间分析时，作为caller, foo就可以通过return边得到n的值。

作为callee, addOne就可以通过call边得到x和y的值。(caller得return, callee得实参)。

这样就可以弥补过程内数据流分析过度假设造成精度的丢失。

做过程间分析需要的信息有：

构造call graph
根据call graph，构造ICFG（过程间控制流图）
IDFG（过程间数据流分析）

Call Graph

为了过程间分析，引入了call graph。

本图foo函数作为caller，call了bar和baz, bar又调用了baz。

重要程度不言而喻（要有过程间的控制流边，就先要建立call graph边那(所有跨函数分析的基础)）

构造CG

蓝色为精度指标，绿色为速度指标。这里介绍CHA。

首先看下java中函数调用方法。

static call: 静态调用（有点像非oo的function call）
Special call:
- 如：
- 1. 调用构造函数
  2. 调用类自己的私有的实例方法
  3. 调用父类中的实例方法
Virtual call: 其他调用实例方法(大部分的oo调用，用来实现__多态__特性)

static call和special call的目标方法只有一个，比较好处理的。关键是处理virtual call。

在程序中，某一个程序点在其运行时Receiving objects的不同，可能调用不同的目标方法，所以由于__多态__的原因(polymorphism), 一个virtual call在运行期间调用的method可能是__大于一个__的(运行时才能决定，取决于运行时的具体reciving object)。

所以对于OO语言，如何处理virtual call 是构造call graph的关键所在

Method Dispatch of Virtual Calls

在处理virtual call中，一个关键的步骤就是method dispatch。

__Dispatch__在过程间分析中比较重要的一个概念。

在程序运行时， call site调用 virtual call, 要去解这个方法需要两个关键：

Receiver object 的具体类型。（右边例子里变量o指向的对象的具体类型）
Call site处方法的具体签名。(右边的例子里为foo(...))

动态的时候去求解这个virtual call的过程也叫做method dispatch

通过一个signature可以确定唯一的一个方法：

Class type: 类名
Method name: 方法名
Descriptor：由两部分构成： 1.返回值类型 2. 参数类型

定义一个函数Dispatch，这个函数模拟了动态时dispatch一个virtual call的具体过程。他的输入就是c(receiver object 的类型)， m(call si te这一点方法的签名)。

dispatch函数的目的是找到一个能够被调用的方法，必须是一个具体的有方法体的方法，所以返回的必须是一个非抽象的方法。

首先在c类中找是否有这样一个非抽象方法m',
如果c没有，就去找c的所有父类c'(注意，是找父类)，直到找到目标方法m'。

这个例子中有ABC三个类，如果dispatch中x.foo()这个call site的两个元素：1. x: receiver object的具体类型是 B(因为它指向 new B()这个类), 2. Foo()这个call site的签名： <B: void foo() > 。所以首先回到B类中进行dispatch, B类中没有foo方法，就去父类A中去找。

y.foo()中就是C的foo方法, 因为他的dispatch函数中，c是receiver object 指向的new C() 类型，而且内部有一个foo方法供m匹配上。

CHA(Class Hierarchy Analysis)

Dispatch

CHA是用来解整个程序call graph的一方法，他需要知道整个程序的class以及继承信息。核心思想是对于一个virtual call，基于这个virtual call的声明类型(不是recevier的具体类型)，以及receiver variable a。

核心思想是给定一个receiver variable a, 他可能会指向他的类型下的所有子类型(即本身)。

来看CHA的算法：

CS： call site, 即调用点

T: target methods，返回的目标方法

m: 目标方法的签名

有三个分支，分别处理static call, special call和virtual call

static call: 静态调用直接放入
Special call: special call有三种：父类方法(super), 构造方法和似有方法

其中父类方法比较特殊，需要Dispatch(cm,m) cm指的是方法m的类型(不是声明类型，A c = new C(), 从C类找)。
Virtual call:

注意这里不是唯一的了，所以使add 目标调用点的声明类型开始找所有符合方法签名m的本类或子类中的c'。

注意三点：

从本类以及子类中找所有的foo方法
其中包含dispatch, 如果本类中没有foo, 回望父类中找，因此Resolve(b.foo())中B无foo(),因此dispatch到了A.foo()。
和new B()无关(尽管new B()中不能调c.foo(), d.foo())，还是根据variable b的声明类(即B类)去找。

通过CHA构建Call Graph

从入口方法开始，没遇到一个可达方法，去解目标方法，得到新的方法后，再去解新的方法的可达方法。。。知道算法停止，得到call grap:

三个数据结构：

WL: worklist , 需要被处理的目标方法，开始只有入口方法。
CG: Call graph, 存调用变。
RM: 可达方法，一个方法进入RM说明已经分析过了。

算法：

一个大的While循环。以起初main方法为例，首先将main方法从worklist中取出来，如果main方法不在RM中说明没有分析过，进入call graph分析过程，从main方法中找到所有的call site, 对每一个call site进行单个call site结点的CHA resolve(cs)得到该call site所有可能的target method, 对于每一个target method m', 将其在call graph中与main方法中对应的call site相连(cs->m'), 并将这些target method标记为可达method(add m' to WL), 此时main方法加入到RM里了，之后不会再被重复分析。(每次分析的目标方法:remove m from WL, add m to RM)。

虚线是call graph其中C.m()并无调用关系。此时WL=[]，构造完成，其中橙色的是每一个需要分析的method, 从中去找每一个call site（如B.bar()这个函数体为空，因此无任何call site), 找到所有call site, 对每个call site进行CHA 的resolve，得到调用边放入(cg，即虚线关系)，新增加的method放入WL（如果和RM重复就不分析了，因为已经分析过了）。