Question

2.1 编译器与静态分析器

首先介绍一下编译器与静态分析器的关系：

编译器主要目的是为了将程序员写的 Source Code 转换为机器可以理解的 Machine Code，并在转换过程中及时报错。下面以英语的语法规则为例。

第一步，通过扫描器 (Scanner) 对输入进行扫描，根据正则表达式 (Regular Expression) 进行词法分析 (Lexical Analysis)，主要是分析输入的每个字母及单词是否为合法字母及单词，接着将通过检测的内容转换为 Tokens 传入下一步。

第二步，通过解析器 (Parser) 对 Tokens 进行扫描，根据上下文无关语法 (Context-Free Grammar) 进行语法分析 (Syntax Analysis)，主要分析几个单词的组合是否符合语法结构规则，接着将通过检测的内容以抽象语法树 (AST) 的形式传入下一步。其中使用上下文无关语法进行分析是为了加快分析效率。

第三步，通过类型检查 (Type Checker)，根据属性语法 (Attribute Grammar) 进行语义分析 (Semantic Analysis)，理想的目的是为了识别像 apples eat me 这种语法结构正确但是语义错误的情况，但是实际编译器只能识别类如“不可进行 int 除以 string”之类的类型错误，故该步称为类型检测。生成进一步处理后的 AST 传入下一步。

第四步，为了进行静态分析优化，要将 Decorated AST 转换为中间表示 (IR)，一般转换为三地址码，再进行静态分析。最后通过代码生成器将优化后的代码生成机器码传给机器。

2.2 IR

2.2.1 AST vs. IR

以一个循环为例来阐述 AST 与 IR 的区别。AST 是一个语法树的形式，是一个高层级的形式，更加接近程序的源代码，语言相关的，适合做快速的类型检测，但是 缺少了控制流信息 。

IR 即为中间表示，图中以三地址码表示，是一个低层级的形式，接近机器编码，语言无关的，结构紧凑， 包含了控制流信息 ，因此更加适合用来做静态分析。

• AST
  • high-level and closed to grammar structure
  • usually language dependent
  • suitable for fast type checking
  • lack of control flow information
• IR
  • low-level and closed to machine code
  • usually language independent
  • compact and uniform
  • contains control flow information
  • usually considered as the basis for static analysis
• 所以 IR 更适合静态分析
• IR 没有固定的定义，常用三地址码

2.3 三地址码

三地址码没有形式化的定义，通常来说，三地址码就是最多有三个地址 (address) 的表达形式，并且由于这个性质，每个三地址码最多只会有一个运算符。

在 Java 中，可以利用 soot 工具来生成三地址码，在 soot 中，被称之为 Jimple。下面以一个 do-while 循环为例，来分析其三地址码。

package nju.sa.example;
public class DoWhileLoop3AC {
  public static void main(String[] args) {
    int[] arr = new int[10];
  	int i = 0;
  	do {
    	i = i + 1;
  	} while (arr[i] < 10);
  }
}

转换后的三地址码形式为：

再以 Method Call 为例，介绍下面向对象环境下的三地址码。

package nju.sa.example;
public class MethodCall3AC {
  String foo(String para1, String para2) {
    return para1 + " " + para2;
  }
  public static void main(String[] args) {
    MethodCall3AC mc = new MethodCall3AC();
    String result = mc.foo("hello", "world");
  }
}

• Java 中的 invoke 指令对应的方法调用情况：
  • invokespecial: call constructor, call superclass methods, call private methods
  • invokevirtual: instance method call
  • invokeinterface: cannot optimization, checking interface implementation
  • invokestatic: call static methods

2.4 控制流分析

控制流分析（Control Flow Analysis）通常指的是构建控制流图（Control Flow Graph, CFG），并以 CFG 作为基础结构进行静态分析的过程。

2.4.1 控制流图

• 通常采用控制流图进行控制流分析的表示
• 控制流图可以用来表示控制流的结构
• 控制流图的节点可以是单个的三地址码，不过通常是 Basic Block(BB)，如下所示。

2.4.2 Basic Block

Basic Block 是具有 以下属性 的、最大长度的三地址码组成的块单元：

• 只能从块的第一条指令进入。
• 只能从块的最后一条指令离开。

如何构建基本块：

• P 的第一条指令就是一个基本块的 leader
• 跳转的目标指令是一个基本块的 leader
• 跳转指令的后一条指令，也是一个基本块的 leader
• 一个基本块就是一个基本块的 leader 及其后续直到下一个基本块的 leader 前的所有指令。

2.4.3 边的生成

除了基本块，CFG 中还会有块到块的边。块 A 和块 B 之间有一条边，当且仅当：

• A 的末尾有一条指向了 B 开头的跳转指令。
• A 的末尾紧接着 B 的开头，且 A 的末尾不是一条无条件跳转指令。

注意到每个基本块和开头指令的标号唯一对应，因此很自然地，需要将跳转指令的目标改为基本块的标号而非指令标号：

有了这些定义，我们就可以了解一些概念：

• 若 A -> B，则我们说 A 是 B 的前驱（predecessor），B 是 A 的后继（successor）
• 除了构建好的基本块，我们还会额外添加两个结点，「入口（Entry）」和「出口（Exit）」
  • 这两个结点不对应任何 IR
  • 入口有一条边指向 IR 中的第一条指令
  • 如果一个基本块的最后一条指令会让程序离开这段 IR，那么这个基本块就会有一条边指向出口。

这样就完成了一个控制流图的构建。