调用图构造（使用CHA）

调用图

调用图是程序中调用关系的表示。其中的点是所有的方法，边是从调用者到被调用者的调用关系。

面向对象语言的调用图构造

• 类层次分析（CHA）
• 快速类型分析（RTA）
• 变量类型分析（VTA）
• 指针分析（k-CFA）

越往下越精确但越慢。

Java的方法调用

invokedynamic暂不考虑。

动态分派

Java在运行时使用动态分派。实际调用的对象取决于：

• 接收对象的实际类型
• 调用的方法签名

我们在此认定一个方法用签名来作为其标识符。

• 签名=类+方法名+描述符
• 描述符=返回值+参数类型

例如以下的方法

class C {
	T foo(P p, Q q, R r){}
}

其签名为<C: T foo(P,Q,R)>，简写为C.foo(P,Q,R)

我们定义函数$Dispatch(c,m)$来模拟运行时的方法分派，其中$c$是方法的实际接收对象类型，$m$是调用时的方法签名。如果$c$包含和$m$的名称与描述符相同的非抽象方法$m^{‘}$，则$Dispatch(c,m)=m^{‘}$，否则$Dispatch(c,m)=Dispatch(c^{‘},m)$，其中$c^{‘}$是$c$的超类。

类层次分析

其需要整个程序的类型层次。根据方法调用的接收变量的声明类型来解析虚调用。

类层次分析使用保守分析，认为一个变量引用可能指向其声明类型和所有子类型。

我们定义以下方法来根据解析CHA中一次调用所有可能指向的方法

CHA的优点是快，缺点是不够精确。其最常用的场景是IDE中。

通过CHA可以构建出这个程序的一个调用图

• 从起始方法开始
• 对每个可达的方法m，对m中每次调用cs使用Resolve(cs)来解析。
• 重复以上直到没有发现新的方法。

过程间数据流分析

过程间控制流图

过程间控制流图（ICFG）包括方法内的CFG，还包括两种额外的边：

• 调用边：从调用者节点指向候选方法
• 返回边：从候选节点的退出节点指向调用的下一条语句的边

控制流分析

边转移包括调用边转移和返回边转移。

以过程间常量传播为例

节点转移：

• 调用类语句：单位函数（不处理）
• 其他语句：和过程内常量传播相同

边转移：

• 普通边：不处理、
• 调用与返回间边：kill本地变量，传播其他本地变量
• 调用边：传递参数值
• 返回边：传递返回值