编译器与静态分析

源代码被编译为机器码的过程：

1. 通过Scanner进行词法分析，得到一系列Tokens
2. 通过Parser进行语法分析，得到抽象语法树AST
3. 通过Type Checker进行语义分析，得到增强AST
4. 通过转换器变成中间表示IR
5. 通过静态分析器进行静态分析，得到优化过的IR
6. 通过代码生成器生成机器码

AST与IR

AST的特点：

• 层次更高、更靠近语法结构
• 与语言有关
• 适合类型检查
• 缺少控制流信息

IR的特点：

• 层次更低、更靠近机器代码
• 一般与语言无关
• 较为精简
• 具有控制流信息
• 一般认为是静态分析的基础

IR：三地址码（3AC）

三地址码（3AC）：等号右边只有最多一个操作符。

例如 t2 = a + b +3，转换为3AC即为：

1. t1 = a + b
2. t2 = t1 + 3

每个3AC语句最多包含三个“地址”。地址包含变量、常量、临时变量。

常见的3AC语句：

• x = y bop z
• x = uop y
• x = y
• goto L
• if x goto L
• if x rop y goto L

控制流分析

控制流分析一般指构建控制流图的过程

基本块（Basic Block）

基本块是程序中满足以下条件的最大的3AC序列：

• 只能从起始处开始执行，不存在goto到第二条及以后的语句。
• 只能从结尾处结束执行，除了最后一条语句外不能有跳转。

基本块构建算法

输入：程序P的3AC序列

输出：程序P的基本块列表

算法：

1. 决定每个基本块的头部：
   • P的第一条指令是一个基本块的头
   • 被跳转到的指令是一个基本块的头
   • 一条跳转指令紧接的指令是一个基本块的头
2. 构建基本块：从一个基本块的头，到下一个基本块的头的前一条指令构成一个基本块。

控制流图

控制流图的节点均为基本块。

当且仅当基本块A和B满足以下条件之一时，控制流图中存在一条A到B的边：

• A中的跳转语句跳转到B
• B在指令序列中紧接在A之后，且A的结尾不为无条件跳转语句