中间代码生成——基础内容

中间代码生成是编译器前端部分的最后内容，负责生成可以为链接器所用的中间表示。这种中间表示比源语言更加低级且接近计算机底层，但是又不像汇编语言那样可以直接在硬件上执行。这种中间表示通常以抽象语法树或三地址代码的形式出现，我们在本部分内容中将详细介绍这两者及其变种。除此之外，中间代码生成时通常还会进行一些静态检查，比如检查各种语句的位置是否正确、类型是否匹配等，本部分也会处理这些内容。

编译器可能会使用从高级到低级的多种中间表示，高级的中间表示更适合进行静态检查，而低级的中间表示更适合生成代码。中间表示也不一定以抽象的数据结构或自行创造的语言出现，C语言，由于其较强的表示力和易于编译成机器代码的特性，也常常作为中间语言出现。用C语言作为中间语言的编译器包括Cfront（早期C++编译器）、GHC（Haskell编译器）和Cython（Python编译器）等。

抽象语法树及其变体

正如我们此前所介绍的，抽象语法树，简称语法树，可以相当容易地从语法分析中生成，且能够保留程序的逻辑关系，因此是常见的中间表示。本节中我们将介绍利用有向无环图（Directed Acyclic Graph, DAG）表示抽象语法树的变种，这种变种可以识别并优化公共子表达式。

表达式的有向无环图

考虑表达式a+a*(b-c)+(b-c)*d。这个表达式当中，子表达式a出现了两次，而(b-c)也出现了两次。在通常的语法树中，这会导致多个相同子树的出现。如果我们重用这些子树，就会把抽象语法树转化成一个有向无环图，如下图所示：

我们知道，可以用以下SDD生成抽象语法树：

产生式	语义规则
$E \to E_1 + T $	`E.node = new Node('+', E1.node, T.node)`
$E \to E_1 - T $	`E.node = new Node('-', E1.node, T.node)`
$E \to T $	`E.node = T.node`
$T \to T_1 * F $	`T.node = new Node('*', T1.node, F.node)`
$T \to (E) $	`T.node = E.node`
$T \to \mathbf{id} $	`T.node = new Leaf(id, id.entry)`
$T \to \mathbf{num} $	`T.node = new Leaf(num, num.val)`

这个SDD在利用产生式生成抽象语法树时，对每个表达式都会生成一个新的结点。实际上，我们只需要稍稍修改Node和Leaf两个构造函数即可。我们在构造新的结点之前，首先检查是否已经生成过一样的结点，如果已经生成过了，就直接返回原结点，而不重新构造新的结点即可。

语法树或DAG的结点通常保存在一个记录（即结构体）数组之中，其中的每一个元素表示一个结点。这个记录的第一个字段通常是运算符代码，即这个结点的标号。对叶子节点，其还有一个额外的字段，指向符号表的条目或者一个常数值；对内部节点，其有两个（可能有更多）额外的字段，保存指向其叶节点的指针（或数组下标）。

如果所有结点都被这样保存在一个数组之中，那么我们可以用数组的下标来指向一个结点，表达式根节点的整数下标称作表达式的值编码。实现中我们通常使用指针或引用，出于习惯也把它们称作值编码。

出于由表达式快速寻找值编码的要求，我们可以用哈希表（也称散列表）来保存每个表达式的值编码，为此我们需要为结点的数据设计一个哈希函数。

三地址代码

在三地址代码中，一条指令的右侧最多只有一个运算符和两个运算分量，而不允许出现组合的算数表达式。因此，像x+y*z这样的表达式必须被翻译成两条三地址代码：t=y*z; r=x+t，其中t和r都是生成的临时名字。三地址代码拆分了表达式和控制流语句的嵌套结构，因此常见于目标代码的生成和优化。

上文所述的DAG可以被翻译成如下三地址代码：

t1 = b - c
t2 = a * t1
t3 = a + t1
t4 = t1 * d
t5 = t3 + t4

三地址代码的约定

三地址代码基于两个基本概念：地址和指令。

地址通常就是指令的操作数，通常具有以下形式之一：

名字：即源程序中的各种名字，在实现中通常以指向符号表的指针替代；
常量或字面量：常量涉及不同类型中的转型问题，这一问题将在下面的文章中介绍；
临时变量：编译器为每个需要的临时变量生成一个新的名字，然后在分配寄存器时尽可能地把它们合并起来。

而指令通常具有以下形式：

运算并赋值：形如x = y op z或x = op y的指令，前者为双目运算符，包括常见的算数和逻辑运算；后者为单目运算符，包括单目减、逻辑非和转型运算。
复制：形如x = y、x[i] = y或x = y[i]、x = &y或*x = y等的指令。
1. x = y：直接赋值，可类比于寄存器寻址；
2. x[i] = y或x = y[i]：类似C中的数组访问，x[i] = y表示把距xi个内存单元的地址复制为y的值，可类比于偏移寻址；
3. x = &y、*x = y或x = *y：类似C中的指针，把一个地址当作指针进行复制，可类比于间接寻址。
控制流指令：包括分支和函数调用：
1. 分支指令：包括无条件跳转指令goto Label、条件跳转指令if x goto Label、if False x goto Label和if x relop y goto Label；
2. 过程调用：param x表示把x作为参数压栈、call y, n和x = call y, n表示调用函数y，使用栈上的n个参数并把参数出栈，然后返回值（若有）保存到x中，return y表示从过程中返回。我们在此处不具体描述其实现。

考虑语句：

do i = i + 1； while(a[i] < v);

可以翻译成三地址代码：

L:  t1 = i + 1
    i = t1
    t2 = i * 8
    t3 = a[t2]
    if t3 < v goto L

这里假设数组一个元素占用8个字节。除了只为需要跳转到的指令编号之外，我们还可以为每一条指令从前到后依次标号，然后直接用标号进行跳转。

四元式与三元式

我们已经描述了三地址代码的各种组成，但是还没有描述其实现方法。在这一节中，我们将描述两种实现三地址代码的数据结构：四元式和三元式，以及三元式的变体，间接三元式。

四元式

四元式是一种简单的表示方法。考虑到三地址代码中至多只有两个运算分量、一个结果分量和一个运算符，四元式足以表示所有情况。

一个四元式（Quadruple）有四个字段：op、arg1、arg2和result。对于通常的三地址代码x = y + z，其字段result为x，arg1和arg2分别为y和z，而op为+。

如果三地址代码只有一个运算分量，那么我们规定其占用arg1而把arg2留空。如果三地址代码没有结果分量（如param），那么我们把result也留空。如果三地址代码表示跳转，那么我们约定标号保存在result的位置。只有三地址代码表示复制（如x = y）时，我们才把op设为=，其余情况下赋值是隐含的。

考虑赋值语句a = b * -c + b * -c，其三地址代码（没有任何优化，单目减用minus以区别于双目减）为：

t1 = minus c
t2 = b * t1
t3 = minus c
t4 = b * t3
t5 = t2 + t4
a = t5

那么其对应的四元式为：

op	arg1	arg2	result
minus	c		t1
*	b	t1	t2
minus	c		t3
*	b	t3	t4
+	t2	t4	t5
=	t5		a

实现时通常用符号表的指针表示程序中的变量，而用一个特殊类型（如Temp）的实例来表示生成的临时变量。

三元式

我们注意到在四元式中存在大量用来保存临时变量的字段，而这些临时变量通常是用来保存三地址代码的中间结果的。我们可以直接引用这个三地址代码从而获取其中间值，而不必生成临时变量。

在三元式（Triple）中，我们用三个字段op、arg1和arg2来描述一个算数运算，而如果需要使用其他三元式的中间结果，则直接引用那条指令即可。实际上，对于表达式而言，三元式表示几乎和DAG表示等价：在DAG中，每个结点有指向子表达式的指针，而在三元式中，也使用这样的指针访问中间结果。但是对控制流指令，三元式和DAG就大不相同了。

对于复制语句x = y，我们把x放在arg1里面，y放在arg2里面。对于需要更多运算分量的三地址代码，可以拆分成两个三元式。比如对于x[i] = y，可以把x[i]放在一个三元式里面，然后把y放在另一个里，然后在第二个三元式的arg1中引用第一个。

对于同一个表达式，其三元式为：

序号	op	arg1	arg2
0	minus	c
1	*	b	(0)
2	minus	c
3	*	b	(2)
4	+	(1)	(3)
5	=	a	(4)

我们用括号中的序号表示引用某条三元式的结果。

三元式相较于四元式的最大缺点在于其依赖于三元式的顺序。在优化时，我们会经常交换一些表达式的顺序甚至删去或添加一些表达式，这会导致表格中的引用失效。为了解决这个问题，我们引入间接三元式的概念。

在间接三元式中，我们不直接操作三元式，而是把所有生成的三元式单独储存起来，然后生成程序的指令列表中并不含有具体的三元式，而是含有指向三元式的指针。这样，当我们操作指令列表时，就只是操作这些指针，而不会操作具体的三元式，从而不会打乱三元式之间的相对顺序。

静态单赋值形式

静态单赋值形式（Static Single Assignment form, SSA）是一种和三地址代码相似的中间表示形式。 SSA和三地址代码最大的不同就是其所有赋值是一次性的，也就是说所有变量都是静态的，且只接受了一次赋值。这种表示形式可以简化优化工作。

对三地址代码：

p = a + b
q = p - c
p = q * d
p = e - p
q = p + q

同一程序的SSA形式可能为：

p1 = a + b
q1 = p1 - c
p2 = q1 * d
p3 = e - p
q2 = p3 + q1

注意每次重新赋值时，SSA都会使用不同的变量名，以确保静态单赋值的特点。

然而，静态单赋值并不总是可能的，考虑以下C语言代码：

int x = (foo > 0 ? 114 : 514);

此时，根据控制流的不同，x可能具有不同的值，因此无法生成SSA形式的代码。为了解决这个问题，引入了$\phi$函数，这一函数表示将两个值根据控制流不同合并起来。此时，上面的代码可以写成：

if(foo > 0)
    x1 = 114;
else
    x2 = 514;
x3 = φ(x1, x2);

类型和声明

在中间代码生成中，类型在翻译和静态检查中都有非常重要的作用。在翻译中，我们需要知道关于类型的信息才能生成正确的中间代码，比如生成数组相关代码时就需要数组元素的大小和数组的长度；在静态检查中，我们需要保证运算符和运算分量的类型匹配、函数声明和其返回值的类型匹配等，尤其是对静态类型的语言。

在这一节中，我们将主要考察前者，即如何利用类型的信息生成中间代码。

类型表达式

各种语言之中都存在复合类型，而这些复合类型的声明也符合各种结构，因此，类比算术表达式，我们提出类型表达式的概念。类型表达式可以是各种基本类型（即“一类公民”）或是类型构造算子作用在类型表达式上产生的表达式。

比如，C语言类型int [2][3]表示由两个数组组成的数组，其中每个数组各自包含三个整数。用类型表达式，可以写成array(2, array(3, int))。这种表达式也可以组织成抽象语法树的形式，只是相较于一般算数表达式（中缀表达式），这种表达式常常是以前缀的形式出现的。

我们递归地类型表达式：

基本类型是一个类型表达式，我们约定其中包括boolean、char、integer、float和void。
每个类名（结构体名）是一个类型表达式，也可以用类型构造算子record构造新的记录（结构体）。使用record构造记录时，必须指明每个字段的类型和名称，我们将在声明一节给出其语法。
将类型构造算子array作用于一个非负整数和类型表达式上，可以产生一个类型表达式，表示数组。
使用类型构造算子→可以构造函数类型的类型表达式。比如integer → float表示从整数到浮点数的一个函数。
类型表达式的笛卡尔积也是类型表达式，这可以用来构造列表或元组以及函数的参数列表。
类型表达式可以含有取值为类型表达式的变量（类似C++中的模板）。

在实际语言中，时常能看到“递归类型”。考虑以下C++代码：

class Cell
{
    int data;
    Cell * next;
}

这个代码中递归地使用了Cell这一类型，以实现一个单向链表。本节介绍的处理技巧也适用于这种递归类型。

类型等价

我们在检查类型时，时常会遇到要求某两个类型表达式所表示的类型相同的情况。这个问题的复杂之处在于，一个类型表达式中的类型可能是另一个类型表达式的别名，正如C语言中typedef关键字所作的那样。为此，我们定义两个等价关系：结构等价（Structurally equivalent）和名称等价（Name equivalent）。

两个类型结构等价，当且仅当：

它们是相同的基本类型，或
它们是由结构等价类型通过相同的类型构造算子构造出的，或
其中一个类型是另一个的别名。

如果所有类型名都只代表其自身，而非另一个类型的别名，那么两个类型名称等价，当且仅当：

它们是相同的基本类型，或
它们是由名称等价类型通过相同的类型构造算子构造出的，或

如果我们以DAG的形式组织类型表达式，那么名称等价关系可以很容易地用哈希表校验。结构等价的判定比较复杂，尤其是类型表达式中含有类型变量的情况，其判定需要使用并查集，我们在类型检查一节再仔细介绍它。

存储布局

我们研究由下面这个简化的文法组成的类型声明： $\begin{aligned} D \quad &\to \quad T \ \mathbf{id}; D \; \vert \; \epsilon \\ T \quad &\to \quad B C \; \vert \; \mathbf{record} '\{' D '\}' \\ B \quad &\to \quad \mathbf{int} \; \vert \; \mathbf{float} \\ C \quad &\to \quad \epsilon \; \vert \; [\mathbf{num}] C \end{aligned}$ 为了区别花括号和语义动作，我们给它们加上一对引号。

我们可以通过变量类型得出其在运行时所需的内存数列，从而在编译时我们就可以为它们确定相对地址（绝对地址在链接时才能确定）。这些信息可以保存在变量的符号表条目之中。传统上，动态分配的内存应当位于堆内存区，且在编译时不能确定。为此，我们可以为其预留一个指针的位置。

类型的宽度（Width）是类型的一个对象或实例所需的存储单元（通常是字节）的数量。一个基本类型的宽度总是整数，而为数组或类（或记录）所分配的空间通常是连续的。大部分语言中，指针是一个特殊的类型，其大小与所指的类型无关。

在为类型分配存储空间时，还要特别考虑对齐的问题。对大部分处理器，其处理的数据的地址总是按2的次方对齐的，其中大部分是按4字节对齐的。这就是说，所有类型的首字节所在的地址总是能被4整除的。因此，假设一个聚合类型的理论宽度为10字节，实际上它的一个对象通常会占用12字节。如果运行空间比较宝贵，编译器可能对数据进行压缩，此时不再为对齐而插入额外的字节。但是处理器通常不能处理这种数据，因此在使用时还需要执行额外的指令进行转化。在这一节中，我们暂时不考虑对齐的问题。

我们首先考虑单个声明，没有聚合类型（记录）的情况。以下翻译方案可以求出声明的类型和类型的宽度。 $\begin{aligned} T \quad &\to \quad B \; \{ C.t = B.type; C.w = B.width \} \; C \; \{ T.type = C.type; T.width = C.width\} \\ B \quad &\to \quad \mathbf{int} \; \{ B.type=integer; B.width=4 \} \\ B \quad &\to \quad \mathbf{float} \; \{ B.type=float; B.width=8 \} \\ C \quad &\to \quad \epsilon \; \{C.type = C.t; C.width = C.w\} \\ C \quad &\to \quad [\mathbf{num}] \; \{C_1.t = C.t; C_1.w = C.w \} \; C_1 \\ & \{C.type = array(num, C_1.type); C.width = C_1.width \} \\ \end{aligned}$ 正如我们此前介绍的那样，我们先把$B$的属性用继承的方式不断向下传递，最后通过$C$的综合属性求值。

声明的序列

我们接下来考虑一串连续的声明，在这种声明中，不仅需要计算每个对象所占用的空间，还需要在符号表中分配它们的相对位置，即确定偏移。虽然对一般的连续声明，我们并不一定需要让被声明的变量严格顺序排列，但计算它们的偏移可以用来为聚合类型分配空间。我们可以向SDT中加入以下代码： $\begin{aligned} P \quad &\to \quad \{\text{offset} = 0\} \; D \\ D \quad &\to \quad T \ \mathbf{id} \ ; \; \{insert(\mathbf{id}.lexeme, T.type, \text{offset}); \text{offset} = \text{offset} + T.width\} \; D_1 \\ D \quad &\to \quad \epsilon \end{aligned}$ insert表示向符号表中插入一个条目，给出这个条目的类型和偏移。

聚合类型

接下来考虑聚合类型（即类和记录）的分配。为方便起见，我们假设每个记录都有自己的符号表，其中保存了每个字段的类型和（相对记录首字节的）偏移。

我们继续向SDT中加入内容： $\begin{aligned} T \quad \to \quad & \mathbf{record} \ '\{' \; &\{ Env.push(top); top = new STable(); \\ & & Stack.push(offset); offset = 0 \} \\ & D \ '\}' &\{ T.type = record(top); T.width = offset; \\ & & top = Env.pop(); offset = Stack.pop(); \} \end{aligned}$

其中$top$是一个指向（记录专有的）符号表的指针，而$record(top)$表示给出一个符号表的指针，返回其对应的类型。 $Env$是符号表指针的栈，$Stack$是偏移的栈。和C++ STL不同，我们规定栈的pop()函数也返回栈顶元素。

对记录和对类的方法是一致的，因为类中的方法（成员函数）并不占用任何空间。

Twitter Facebook LinkedIn