第6章中间代码生成

导读

中间代码生成是编译过程中连接前端（分析与语义处理）和后端（优化与目标代码生成）的关键环节。中间代码是一种介于高级语言和机器语言之间的表示形式，它既要保留源程序的语义信息，又要足够接近目标机器以便后续处理。

一个好的中间表示（Intermediate Representation, IR）应该具备以下特性：

易于生成：能够高效地从源程序或AST转换而来
易于翻译：能够方便地转换为目标机器代码
易于优化：能够支持各种代码优化变换
与机器无关：不依赖于特定的目标机器架构

本章将系统介绍中间代码的各种表示形式，包括图形表示（如AST、DAG）、线性表示（如三地址码、双地址码、单地址码），以及布尔表达式的中间代码生成。我们还将讨论声明语句、控制流语句、过程调用等复杂结构的翻译方法。

通过本章的学习，你将理解编译器为什么需要中间代码，不同的中间表示各有什么优缺点，以及如何为各种语言结构生成正确的中间代码。

核心概念详解

6.1 中间表示的作用

中间表示在编译器中扮演着承上启下的角色：

源程序 → [前端] → 中间表示 → [优化] → 优化后的中间表示 → [后端] → 目标代码

为什么需要中间表示？

解耦前端和后端：前端负责语言特定的分析，后端负责机器相关的代码生成。通过中间表示，可以实现N种源语言 × M种目标机器的组合，而只需要N个前端和M个后端（而不是N×M个完整的编译器）。

支持代码优化：中间表示提供了进行优化变换的合适抽象层次。许多优化在源代码层面或机器代码层面都难以实现。

支持多趟编译：中间表示可以存储在文件中，允许编译器分多趟执行，减少内存需求。

便于调试和分析：中间表示比机器代码更易理解，便于调试和性能分析。

6.2 图形表示：抽象语法树（AST）

抽象语法树（AST）是源程序语法结构的树状表示，是编译过程中最常用的中间表示之一。

AST的特点：

每个内部节点代表一个运算
叶子节点代表运算的操作数
省略了语法中的冗余信息（如括号、分号）
自然地表达了运算的优先级和结合性

AST的构建：

在语法制导翻译中，AST通过综合属性来构建。每个非终结符有一个 node 属性，表示对应子树的根节点。

python

class AST:
    pass

class BinOp(AST):
    def __init__(self, op, left, right):
        self.op = op
        self.left = left
        self.right = right

class UnaryOp(AST):
    def __init__(self, op, operand):
        self.op = op
        self.operand = operand

class Num(AST):
    def __init__(self, value):
        self.value = value

class Var(AST):
    def __init__(self, name):
        self.name = name

class Assign(AST):
    def __init__(self, target, value):
        self.target = target
        self.value = value

6.3 图形表示：有向无环图（DAG）

有向无环图（DAG）是AST的紧凑版本，它通过共享公共子表达式来减少冗余。

DAG与AST的区别：

AST中每个运算都有独立的节点
DAG中相同的子表达式共享同一个节点
DAG更适合表示公共子表达式优化

示例：

对于表达式 a + a * (b - c) + (b - c) * d：

AST（每个运算独立节点）：

+
       / \
      +   *
     / \ / \
    a  * d
      / \
     b   -
        / \
       b   c

DAG（共享公共子表达式 b - c）：

+
       / \
      +   *
     / \ / \
    a  * d
      / \
     *   n1
    / \ / \
   a n1 b  c

这里 n1 代表 b - c，被两个乘法共享。

DAG的构建算法：

python

class DAGBuilder:
    def __init__(self):
        self.nodes = {}  # 值到节点的映射

    def make_leaf(self, op, value=None):
        key = (op, value)
        if key not in self.nodes:
            self.nodes[key] = LeafNode(op, value)
        return self.nodes[key]

    def make_node(self, op, left, right):
        key = (op, left, right)
        if key not in self.nodes:
            self.nodes[key] = InternalNode(op, left, right)
        return self.nodes[key]

6.4 三地址码

三地址码（Three-Address Code, TAC）是最常用的线性中间表示。每条指令最多有三个操作数，形式为：

x = y op z

其中 x、y、z 可以是名字、常数或编译器生成的临时变量。op 可以是算术运算符、逻辑运算符、地址操作等。

三地址码的指令类型：

类型	形式	说明
算术运算	`x = y op z`	op 为 +、-、*、/ 等
一元运算	`x = op y`	op 为 -、not 等
复制	`x = y`	将y的值复制给x
无条件跳转	`goto L`	跳转到标签L
条件跳转	`if x relop y goto L`	条件满足时跳转
过程调用	`call proc, n`	调用过程proc，参数个数n
返回值	`return y`	返回值y
数组访问	`x = y[i]`	数组元素读取
数组赋值	`x[i] = y`	数组元素写入
地址操作	`x = &y`	取地址
间接引用	`x = *y`	间接读取

三地址码的表示：

python

class ThreeAddressCode:
    def __init__(self, op, arg1=None, arg2=None, result=None):
        self.op = op
        self.arg1 = arg1
        self.arg2 = arg2
        self.result = result

    def __str__(self):
        if self.op in ('+', '-', '*', '/'):
            return f"{self.result} = {self.arg1} {self.op} {self.arg2}"
        elif self.op == 'goto':
            return f"goto {self.arg1}"
        elif self.op == 'if':
            return f"if {self.arg1} goto {self.arg2}"
        elif self.op == '=':
            return f"{self.result} = {self.arg1}"
        # ...

6.5 三地址码的生成

三地址码的生成通过语法制导翻译实现。每个非终结符有两个属性：

addr：存放值的变量名（或临时变量）
code：生成的三地址码序列

表达式翻译的翻译方案：

E → E₁ + T    { E.addr = newtemp();
                 E.code = E₁.code || T.code ||
                          gen(E.addr '=' E₁.addr '+' T.addr) }
E → T         { E.addr = T.addr;
                 E.code = T.code }
T → T₁ * F    { T.addr = newtemp();
                 T.code = T₁.code || F.code ||
                          gen(T.addr '=' T₁.addr '*' F.addr) }
T → F         { T.addr = F.addr;
                 T.code = F.code }
F → ( E )     { F.addr = E.addr;
                 F.code = E.code }
F → id        { F.addr = id.entry;
                 F.code = "" }
F → num       { F.addr = num.value;
                 F.code = "" }

对于表达式 a + b * c，生成的三地址码：

t1 = b * c
t2 = a + t1

6.6 布尔表达式的翻译

布尔表达式在控制流语句中起着关键作用。布尔表达式的翻译有两种主要策略：

策略1：数值表示

将布尔值视为数值（true=1, false=0），使用算术运算计算布尔表达式。

B → B₁ or B₂    { B.addr = newtemp();
                    gen(B.addr '=' B₁.addr '|' B₂.addr) }
B → B₁ and B₂   { B.addr = newtemp();
                    gen(B.addr '=' B₁.addr '&' B₂.addr) }
B → not B₁      { B.addr = newtemp();
                    gen(B.addr '=' '!' B₁.addr) }

策略2：控制流表示（短路求值）

利用条件跳转实现短路求值，这是大多数编译器采用的策略。

每个布尔表达式关联两个标签：

true_label：表达式为真时跳转到的标签
false_label：表达式为假时跳转到的标签

B → id₁ relop id₂  { gen("if" id₁ relop id₂ "goto" B.true)
                       gen("goto" B.false) }
B → B₁ or B₂       { B₁.false = B₂.true = newlabel();
                       B.true = B.true; B.false = B.false }
B → B₁ and B₂      { B₁.true = newlabel();
                       B₂.true = B.true; B₂.false = B.false }
B → not B₁         { B.true = B₁.false; B.false = B₁.true }

对于 a < b or c < d and e < f，生成的代码：

if a < b goto true_label
goto L1
L1: if c < d goto L2
    goto false_label
L2: if e < f goto true_label
    goto false_label
true_label: ...
false_label: ...

6.7 控制流语句的翻译

if语句的翻译：

S → if B then S₁
    { B.true = newlabel();
      B.false = S.next;
      S.code = B.code || gen(B.true ":") || S₁.code }

S → if B then S₁ else S₂
    { B.true = newlabel();
      B.false = L1 = newlabel();
      S.next = S₁.next = S₂.next = newlabel();
      S.code = B.code || gen(B.true ":") || S₁.code ||
               gen("goto" S.next) || gen(L1 ":") || S₂.code ||
               gen(S.next ":") }

while语句的翻译：

S → while B do S₁
    { S.begin = newlabel();
      B.true = newlabel();
      B.false = S.next;
      S₁.next = S.begin;
      S.code = gen(S.begin ":") || B.code ||
               gen(B.true ":") || S₁.code ||
               gen("goto" S.begin) || gen(S.next ":") }

对于 while a < b do x = x + 1，生成的三地址码：

L1: if a < b goto L2
    goto L3
L2: t1 = x + 1
    x = t1
    goto L1
L3:

for语句的翻译：

S → for (E₁; B; E₂) S₁
    { S.begin = newlabel();
      B.true = newlabel();
      B.false = S.next;
      S₁.next = L1 = newlabel();
      S.code = E₁.code || gen(S.begin ":") || B.code ||
               gen(B.true ":") || S₁.code ||
               gen(L1 ":") || E₂.code ||
               gen("goto" S.begin) || gen(S.next ":") }

6.8 过程调用的翻译

过程调用需要处理参数传递、控制转移和返回值。

过程调用的三地址码：

call proc, n

其中 proc 是过程名，n 是参数个数。参数通过 param 指令传递：

param arg₁
param arg₂
...
param argₙ
call proc, n

函数调用的翻译：

S → call id ( args )
    { S.code = args.code ||
               gen("param" args.arg₁) ||
               gen("param" args.arg₂) ||
               ...
               gen("call" id.entry "," args.count) }

返回值的处理：

S → return E
    { S.code = E.code || gen("return" E.addr) }

6.9 声明语句的翻译

声明语句需要处理类型信息的记录和存储分配。

简单声明的翻译：

D → T id
    { enter(id.name, T.type, offset);
      offset += T.width }
T → int
    { T.type = int; T.width = 4 }
T → float
    { T.type = float; T.width = 8 }
T → array num of T₁
    { T.type = array(T₁.type);
      T.width = T₁.width * num.value }
T → record D
    { T.type = record;
      T.width = D.width }

符号表的更新：

python

class SymbolTable:
    def __init__(self):
        self.entries = {}
        self.offset = 0

    def enter(self, name, type, width):
        self.entries[name] = {
            'type': type,
            'offset': self.offset,
            'width': width
        }
        self.offset += width

重要知识点

6.10 类型表达式的翻译

类型表达式描述数据类型的结构。类型表达式的翻译需要计算类型的宽度和结构。

T → int           { T.type = int; T.width = 4 }
T → float         { T.type = float; T.width = 8 }
T → pointer T₁    { T.type = pointer(T₁.type);
                     T.width = 8 }
T → array T₁      { T.type = array(T₁.type);
                     T.width = T₁.width }
T → T₁ × T₂      { T.type = product(T₁.type, T₂.type);
                     T.width = T₁.width + T₂.width }

6.11 后缀表示（逆波兰表示）

后缀表示是一种线性中间表示，运算符跟在操作数之后。它不需要括号就能无歧义地表示表达式。

中缀到后缀的转换：

中缀: a + b * c
后缀: a b c * +

中缀: (a + b) * c
后缀: a b + c *

中缀: a + b + c
后缀: a b + c +

后缀表示的求值：

使用栈来求值后缀表达式：

遇到操作数，压入栈

遇到运算符，弹出两个操作数，计算结果，压入栈

最后栈中只剩一个值，即为结果

6.12 静态单赋值形式（SSA）

静态单赋值形式（Static Single Assignment, SSA）是一种特殊的中间表示，其中每个变量只被赋值一次。

SSA的特点：

每个变量只有一个定义点
使用 φ 函数来合并不同控制流路径的值
便于进行数据流分析和优化

示例：

普通三地址码：

x = 1
x = x + 1
y = x * 2

SSA形式：

x₁ = 1
x₂ = x₁ + 1
y₁ = x₂ * 2

带控制流的SSA：

if (cond) {
    x₁ = 1
} else {
    x₂ = 2
}
x₃ = φ(x₁, x₂)

这里 φ(x₁, x₂) 表示根据控制流来源选择 x₁ 或 x₂ 的值。

6.13 中间代码的优化机会

中间代码为优化提供了丰富的机会：

局部优化（基本块内）：

常量折叠：t1 = 3 + 5 → t1 = 8
常量传播：t1 = 8; t2 = t1 * 2 → t2 = 16
公共子表达式消除：t1 = a * b; t2 = a * b → t2 = t1
死代码消除：删除未被使用的赋值

全局优化（跨基本块）：

全局公共子表达式消除
循环不变量外提
归纳变量消除
过程间优化

常见误区

误区一：中间代码越接近源语言越好

中间代码需要在"接近源语言"和"接近目标机器"之间取得平衡。太接近源语言则难以优化和翻译，太接近目标机器则失去了机器无关性。三地址码是一个较好的折中。

误区二：中间代码只需要一种表示

实际编译器通常使用多种中间表示。例如，LLVM使用：

AST（前端分析）
LLVM IR（主中间表示，SSA形式）
SelectionDAG（指令选择阶段）

每种表示都有其特定的用途和优化阶段。

误区三：中间代码生成不影响最终代码质量

中间代码的质量直接影响后续优化和目标代码生成的效果。一个设计不良的中间表示可能限制优化的空间，增加目标代码生成的难度。

误区四：三地址码的每条指令都对应一条机器指令

三地址码是抽象的中间表示，一条三地址码可能对应多条机器指令，也可能被优化掉。三地址码的目的是清晰地表达语义，而非直接映射到机器。

实践应用

6.14 实际编译器中的中间表示

LLVM IR：

基于SSA形式
强类型系统
支持三种等价表示：内存格式（内存中的数据结构）、文本格式（.ll文件）、二进制格式（.bc文件）
被Clang、Rust、Swift等编译器使用

Java字节码：

栈式虚拟机指令集
紧凑的二进制格式
支持JIT编译

GCC GIMPLE/RTL：

GIMPLE：三地址码形式，用于高层优化
RTL：更接近机器，用于低层优化和代码生成

V8 TurboFan IR：

用于JavaScript引擎的中间表示
基于海图（Sea of Nodes）表示
支持JIT编译和优化

6.15 中间代码的调试

调试中间代码的方法：

打印中间代码：将中间代码以可读格式输出

可视化：将AST或DAG可视化为图形

逐步执行：模拟中间代码的执行过程

对比分析：对比优化前后的中间代码

本章小结

本章系统介绍了中间代码生成的理论和实践。核心内容包括：

中间表示的作用：解耦前端和后端，支持代码优化和多趟编译。

图形表示：AST和DAG，DAG通过共享公共子表达式实现紧凑表示。

三地址码：最常用的线性中间表示，每条指令最多三个操作数。

布尔表达式翻译：数值表示和控制流表示（短路求值）两种策略。

控制流翻译：if、while、for等语句的翻译方案。

过程调用翻译：参数传递、控制转移和返回值的处理。

SSA形式：每个变量只赋值一次的中间表示，便于优化。

中间代码是编译器的核心数据结构，其设计质量直接影响编译器的整体性能。

第6章 中间代码生成

导读

核心概念详解

6.1 中间表示的作用

6.2 图形表示：抽象语法树（AST）

6.3 图形表示：有向无环图（DAG）

6.4 三地址码

6.5 三地址码的生成

6.6 布尔表达式的翻译

6.7 控制流语句的翻译

6.8 过程调用的翻译

6.9 声明语句的翻译

重要知识点

6.10 类型表达式的翻译

6.11 后缀表示（逆波兰表示）

6.12 静态单赋值形式（SSA）

6.13 中间代码的优化机会

常见误区

误区一：中间代码越接近源语言越好

误区二：中间代码只需要一种表示

误区三：中间代码生成不影响最终代码质量

误区四：三地址码的每条指令都对应一条机器指令

实践应用

6.14 实际编译器中的中间表示

6.15 中间代码的调试

本章小结

第6章中间代码生成