Question

1.1 概念

本质上来说，一个调用图就是从调用点到目标方法(callee) 的 一系列调用边 。

程序调用图是过程间分析的基础，可以用于程序优化、理解、调试、测试等。

1.2 分类

Call Graph 有很多种不同的构造方法，本文接下来会讲解两个极端：最准确的和最快速的。

调用图构造主要作用于面向对象语言，即以 Java 为代表的，面向对象的语言。一般用到如图四种算法，其中 CHA 是最快的，指针分析 K-CHA 是最准的，本文主要将 CHA，后面的文章会讲指针分析。

1.3 Java 中的方法调用形式

• Instruction：指 Java 的 IR 中的指令
• Receiver objects：方法调用对应的实例对象（static 方法调用不需要对应实例）。
• Target methods：表示 IR 指令到被调用目标方法的映射关系
• Num of target methods：call 对应的可能被调用的目标方法的数量。Virtual call 与动态绑定和多态实现有关，可以对应多个对象下的重写方法。所以 Virtual call 的可能对象可能超过 1 个 。
• Determinacy：指什么时候能够确定这个 call 的对应方法。Virtual call 与多态有关，只能在运行时决定调用哪一个具体方法的实现。其他两种 call 都和多态机制不相关，编译时刻就可以确定。

1.4 Virtual Call 的方法调度函数 (Dispatch)

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

1. virtual call 返回内容的接收对象是谁： c
2. 调用点处的 方法签名：m
   1. Signature = class type + method name + descriptor
   2. Descriptor = return type + parameter types

本文中的方法签名定义如下：

定义 Dispatch(c,m) 函数来描述函数间的分配关系：Java 中 Dispatch 机制决定具体调用哪个方法，c 是类名，m 是一个方法。如果能在本类中找到 name 和 descriptor 一致的方法，则调用 c 的方法，否则到父类中寻找。

一个示例：Dispatch 关注 Receiver Object 即 new B() 和方法签名： A.foo()