编译器将源代码（Source code） 转换为机器代码（Machine Code）。其中的流程框架是：

  • 词法分析器（Scanner），结合正则表达式，通过词法分析（Lexical Analysis）将 source code 翻译为 token。
  • 语法分析器（Parser），结合上下文无关文法（Context-Free Grammar），通过语法分析（Syntax Analysis），将 token 解析为抽象语法树（Abstract Syntax Tree, AST）
  • 语义分析器（Type Checker），结合属性文法（Attribute Grammar），通过语义分析（Semantic Analysis），将 AST 解析为 decorated AST
  • Translator，将 decorated AST 翻译为生成三地址码这样的中间表示形式（Intermediate Representation, IR），并基于 IR 做静态分析（例如代码优化这样的工作）。
  • Code Generator，将 IR 转换为机器代码。

IR: Three-Address Code

三地址码（3-Address Code）通常没有统一的格式。在每个指令的右边至多有一个操作符。
image.png
三地址码为什么叫做三地址码呢？因为每条 3AC 至多有三个地址。而一个「地址」可以是：

  • 名称 Name: a, b
  • 常量 Constant: 3
  • 编译器生成的临时变量 Compiler-generated Temporary: t1, t2

常见的 3AC 包括：

  • x = y bop z：双目运算并赋值，bop = binary operator
  • x = uop z：单目运算并赋值，uop = unary operator
  • x = y：直接赋值
  • goto L：无条件跳转，L = label
  • if x goto L：条件跳转
  • if x rop y goto L：包含了关系运算的条件跳转，rop = relational operator

基于IR生成控制流图CFG

控制流分析（Control Flow Analysis）通常指的是构建控制流图（Control Flow Graph, CFG），并以 CFG 作为基础结构进行静态分析的过程。
image.png
CFG 的一个结点可以是一条单独的 3AC，但是更常见的是一个基本块（Basic Block）。所谓基本块，就是满足以下性质的连续 3AC：

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

image.png
如何构建一个基本块呢？

  • 输入：程序 P 的一系列 3AC
  • 输出：程序 P 的基本块
  • 方法
    • 1.决定 P 的 leaders
      • P 的第一条指令就是一个 leader
      • 跳转的目标指令是一个 leader
      • 跳转指令的后一条指令，也是一个 leader
    • 2.构建 P 的基本块
      • 一个基本块就是一个 leader 及其后续直到下一个 leader 前的所有指令。

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

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

image.png
注意到每个基本块和开头指令的标号唯一对应，因此很自然地，我们可以将跳转指令的目标改为基本块的标号而非指令标号：
image.png
有了这些定义，我们就可以了解一些概念：

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

这样，我们就完成了一个控制流图的构建：
image.png