调用图构造

CHA问：“按类定义，这个对象有可能是哪类？”RTA再加一条过滤：“从入口可到达的代码，真的有机会造出这个类吗？”后者通常少些边，但类是否会被分配与方法是否可达互相依赖，必须一边发现、一边更新。

这两种方法都不按运行时间排序。即使一个分配语句在调用之后，流不敏感的RTA仍可能用它扩大该调用的候选集。调用图说明潜在调用关系，不是一段运行日志。

新发现的分配会反过来改变旧调用点 ​

类A和子类B都实现方法 f。入口代码为：

main:
    x = new B
    x.f()                 // c

B.f:
    makeA()

makeA:
    y = new A
    return y

A.f:
    return

假设 x 的静态类型声明为A。CHA从一开始就在调用点 $c$ 放入 A.f 和 B.f。RTA则逐步得到：

实际运行中，x始终指向B，makeA的返回值也没有赋给x。因此A.f仍是一条伪边。RTA可靠地保留了真实B.f，却因为全局类集合而失去变量级区别；指针分析公理库Andersen 包含式指针分析Andersen pointer analysis · Inclusion-based points-to analysis地址获取、复制、解引用读写如何生成只增的points-to包含约束。可以继续问“哪个对象能流到x”，从而进一步过滤目标。

若删除B.f中的makeA调用，而makeA又没有其他入口，RTA不会因源码中出现 new A 就加入A。扫描所有方法中的分配而不管可达性，会退化为另一种更粗算法，不能仍用上面的迭代过程解释结果。

继承不等于产生一份新的方法 ​

再增加C继承B，但不重写f。new C使C进入已分配类集后，dispatch(C,f)仍是B.f；图中应加入B.f这条边，而不是虚构一个C.f方法节点。多继承、接口默认方法及语言的派发规则需要相应调整lookup，不能只比较类名字。

开放世界的边界 ​

如果外部插件可以稍后装载D并重写f，封闭世界结果不能直接用于删除该派发分支。可以显式把未知实现建成保守外部目标，或在受控的全程序构建中证明类集已经封闭。反射、JNI与回调也需模型；“分析器没看到”不是不可发生的证据。

CHA可靠性的理由是：真实接收者动态类必须满足其静态类型限制，实际派发方法必在枚举结果里。RTA还需对真实执行归纳：入口可达；每次真实分配所在的方法已可达，因此相应类进入 $A$；真实虚调用的接收者来自某个允许分配，于是目标最终加入 $R$。环境可以提供预先创建对象时，它们的类也必须列为初始输入，归纳才能成立。

设方法数为 $m$、候选分配类数为 $k$、可达调用点数为 $c$。显式表最多有 $ck$ 次“调用点、动态类”组合，方法和类各只首次入队一次。预先处理继承lookup并对每个组合去重的工作队列，可把主体工作计为程序扫描加 $O(ck)$ 次派发查询；若每次沿深度 $h$ 的继承链查询，需再乘相应的 $h$。这个界不包括把反射或动态代码转换成模型的成本。

调用图常用于删除不可达代码、估算递归分量、构造过程间控制流图和安全扫描。但方法级图中的一个环只说明存在潜在递归依赖，不证明每次执行都会递归，也不证明递归无法终止。进一步区分调用和返回，应进入上下文敏感的过程间分析公理库上下文敏感的过程间分析Context-sensitive interprocedural analysis · Interprocedurally valid paths把函数出口连回所有调用者会产生什么假执行，调用串和摘要怎样约束返回。。