PL-4-Interprocedural Analysis
内容提要
本文介绍过程间分析，旨在处理程序中的方法调用以提高分析精度。通过构建调用关系图（如CHA方法），从入口方法递归解析可达调用，并利用过程间控制流图（ICFG）传递数据流信息，最终显著提升常量传播等分析的准确性。
延伸解读
精度与效率的权衡
过程间分析通过考虑方法调用提升精度，但不同构造调用图的方法在精度和效率上差异显著。CHA仅依赖类继承关系，速度快但可能产生不精确的结果，例如将b.foo()解析为多个子类的方法，而实际运行时可能只调用其中一个。更精确的指针分析则能缩小目标方法集合，但计算开销更大。实际应用中需根据场景选择合适的方法。
调用图构造的迭代本质
调用图构造本质上是一个闭包计算过程：从入口方法开始，不断解析可达方法中的调用，并将新发现的方法加入工作列表，直到没有新方法为止。这一过程保证了所有可达方法都被覆盖，同时避免了重复处理已分析的方法。理解这一迭代算法有助于把握过程间分析的整体流程。
过程间数据流分析的关键点
过程间数据流分析在过程内分析的基础上增加了调用边和返回边的传递函数，用于传递参数和返回值。同时，调用点处的call-to-return边允许局部数据流直接传递，避免在分析被调用函数时保留不必要的调用者信息。此外，必须kill掉调用语句左侧的变量，否则可能导致分析结果不准确。
Q&A
什么是过程间分析？它主要解决什么问题？
过程间分析是一种程序分析技术，用于处理程序中包含方法调用的情况。它通过构建调用关系图（如CHA）和过程间控制流图（ICFG），在方法之间传递数据流信息，从而提高分析精度。它主要解决过程内分析忽略方法调用导致精度丢失的问题。
Java中方法调用分为哪几类？它们分别有什么特点？
Java中方法调用分为三类：静态调用（static call）、特殊调用（special call）和虚调用（virtual call）。静态调用不依赖实例，编译时确定；特殊调用包括super调用、构造函数和私有实例方法，编译时确定；虚调用与多态相关，运行时根据对象类型和方法签名动态分派，可能对应多个目标方法。
什么是类层次分析（CHA）？它如何解析虚调用？
类层次分析（CHA）是一种基于类继承关系图来解析虚调用的方法。它根据调用点接收变量的声明类型，假设该变量可能指向该类型及其所有子类的对象，然后在这些类中查找匹配的方法签名。CHA速度快但精度较低，常用于IDE提示。
如何通过CHA构造整个程序的调用关系图？
通过CHA构造调用关系图的步骤是：从入口方法（如main）开始，对每个可达方法中的每个调用点，使用CHA的Resolve算法解析可能的目标方法，将调用边加入调用图，并将新发现的方法加入工作列表，重复直到没有新方法可达。
什么是过程间控制流图（ICFG）？它由哪些部分组成？
过程间控制流图（ICFG）是过程内控制流图（CFG）的扩展，通过添加调用边和返回边连接不同方法的CFG。调用边从调用点连接到被调用方法的入口节点，返回边从被调用方法的返回语句连接到调用点后的返回点。
在过程间数据流分析中，如何处理调用和返回边？
在过程间数据流分析中，需要为调用边和返回边定义传递函数。调用边传递参数，返回边传递返回值。此外，在调用点处需要kill掉左值（LHS）变量，并添加call-to-return边以在调用点直接传播局部数据流，避免不必要的跨过程传播。
过程间分析相比过程内分析能带来多大的精度提升？
过程间分析能显著提高精度。例如在常量传播中，过程内分析可能将调用结果视为NAC（非常量），而过程间分析能准确传播常量值，如示例中n=10，y=43。
