前言
课程网站为Static Program Analysis | Tai-e
因为上周三忙着做团支书的工作以及各种其他事情，课上没有仔细的听，所以之后再花时间重新看b站的视频课程。顺便就此机会准备后面的课都通过视频的形式来学习了。这门课还是在观看视频的时候反复理解和思考才是更高效的，即使我之前会线下去上课，回来之后还是有一些地方要自己好好研究的。所以后续以这种形式既不会错过知识内容，也可以增加我的效率。
从这节课开始就是从谭添老师开始上了，前面听说从这一部分开始会有一些动态的分析，而且难度也会开始变得更高。针对过程间分析我们要了解的主要有 Call Graph Construction（ CHA ）、Interprocedural Control-Flow Graph 和 Interprocedural Data-Flow Analysis。
Motivation
过程内分析过于保守，假设调用后都不是常量，丢失了精度。所以我们需要过程间分析，首先就需要调用图，来得到调用边（Call edges）。
Call Graph Construction（ CHA ）
一个调用图是一个从 call-sites 到目标方法的调用边的集合。
本课程主要对 OOPLs 构建调用图(focus on Java)，这节课会学习Class hierarchy analysis（ CHA ），下节课会学习Pointer analysis（k-CFA）。
越往上速度越快，越往下精度越高。
了解JAVA中的call：
| Static call | Special call | Virtual call | |
|---|---|---|---|
| Instruction | invokestatic | invokespecial | invokeinterface invokevirtual |
| Receiver objects | ×无实例 | √有实例 | √有实例 |
| Target methods | ·Static methods (静态方法) | ·Constructors (构造函数) ·Private instance methods (类自己的私有方法) ·Superclass instance methods (父类的实例方法) |
·Other instance methods (其他实例方法) |
| # Target methods 个数 | 1 | 1 | ≥1 (polymorphism) 多态 |
| Determinacy 确定时机 | Compile-time (编译时) | Compile-time (编译时) | Run-time (运行时) |
构造调用图的关键在于处理virtual call，其中关键的一个步骤叫做Method Dispatch，基于：
- receive object 的具体类型
- 方法的签名signature
-
Signature = class type + method name +descriptor
-
Descriptor = return type + parameter types
-
Dispatch(c,m)这个算法用来找到类为c，c中包含名为m且有方法体的方法。若c中未找到，就去父类中找。
在这个基础上我们通过一个算法 CHA 找到 某一个调用点 cs（call site）可能的目标方法：
对于静态方法，目标方法就是这个方法本身，对于special call ，有三种情况，分别是前面提到的构造方法、私有方法和父类实例方法，对于前两种其实是不需要Dispatch的，但是第三种需要，而Dispatch可以覆盖这三种。然后对于 virtual call ，我们需要对于 cs 声明的类型的所有子类去做Dispatch，最终返回此处的目标方法。
这里举了一个例子说明 virtual call 的同时，还说明了一点，也就是 b.foo() 它实际上调用的就是 A.foo() ，所以在这里后面的C.foo() D.foo() 都是多余的调用目标.
CHA的优点就是很快，他只考虑在 cs 声明的类型和他的继承结构，忽略了实际的数据和控制流信息。所以它的缺点就是不够精确，比如上文可能引入的多余目标
接下来我们就可以通过 CHA 来构建整个程序的调用图，我们从 Entry 开始，主要就是main函数，对于每一个可达的方法，利用 CHA 解析他的每一个 cs 的目标方法，重复这个过程直到不再有新方法出现。算法如下：
Interprocedural Control-Flow Graph
CFG 是一个单独的方法之内的结构，而 ICFG 则是包含了不同方法的 CFG 以及加上两个额外的边，分别是 Call edges 和 Return edges。一个是从 cs 指向被调用的方法的 Entry nodes ，一个是从exit nodes 指向跟在 cs 之后的下一条语句（return sites）。
而这两条边就来自于调用图。而原来的边（如下图黄色背景中的边）就被称作call-to-return edges，我们并不会删掉他，这一点会在后面解释。
InterproceduralData-Flow Analysis
根据 ICFG ，我们对整个包含方法调用的整个程序做分析。我们可以通过下表看到和 CFG 对比：
| Intraprocedura | Interprocedural | |
|---|---|---|
| Program representation | CFG | ICFG = CFGs + call & return edges |
| Transfer functions | Node transfer | Node transfer + edge transfer |
这里的 edge transfer 主要包括两种：
- Call edge transfer:将数据流从 cs 传递到被调用方法的 entry node（along call edges）主要传递参数值
- Return edge transfer:将数据流从被调用方法的 exit node 传递到 return site（along return edges）主要传递返回值
对于Node transfer，当遇到形如 b = addOne(a)这种形式的时候，和原来的不同，要将左边的变量的值留给edge transfer来处理，否则他可能导致不精确的问题，如下图所示：
这里会将b识别为NAC，显然是不准确的。
另外，前文提到的 call-to-return edges 为什么会保留下来，就是为了在这里避免将某一个 local data-flow 传递到 method 中去，否则会非常低效。我们就可以通过 ICFG 上的 call-to-return edges 来获得数据流的传递。如图所示：
总之，通过过程间的分析可以比原来的过程内分析得到的结果更加准确。