六、代码生成，《编译原理》（本科教学版），第2版

零、前言

0.1 编译器前端到后端

前端对源程序进行进行分析并产生中间表示，后端则在此基础上生成目标代码。

前面几章介绍了编译器前端的主要内容，接下来会进入中间端和后端的部分。

中间端和后端的大致架构：

抽象语法树经过若干次中间表示和翻译，得到汇编代码。这是一个抽象层次逐渐降低的过程。

上世纪七八十年代时的做法是仅通过一次代码生成然后得到汇编，这样的做法由于抽象层次跨度太大，所以实现困难。

现代编译器的选择往往是经过多次生成而向目标代码逐渐靠近。

一、代码生成

1.1 代码生成的任务

• 负责把源程序翻译成“目标机器”上的代码
  • 目标机器：
    • 可以是真实物理机器
    • 可以是虚拟机
  • 两个重要任务
    • 给源程序的数据分配计算资源
    • 给源程序的代码选择指令

1.2 给数据分配计算资源

• 源程序的数据：
  • 全局变量、局部变量、动态分配等
• 机器计算资源：
  • 寄存器、数据区、代码区、栈区、堆区
• 根据程序的特点和编译器的设计目标，合理的为数据分配计算资源
  • 例如：变量放在内存里还是寄存器里？

1.3 给代码选择合适的机器指令

• 源程序的代码
  • 表达式运算、语句、函数等
• 机器指令
  • 算术运算、比较、跳转、函数调用返回
• 用机器指令实现高层代码的语义
  • 等价性
  • 对机器指令集体系结构(ISA)的熟悉

我们将研究两种不同的ISA上的代码生成技术

• 栈计算机Stack
• 寄存器计算机Reg

1.4 栈式计算机

• 栈式计算机在历史上非常流行
  • 上世纪70年伐曾有很多栈式计算机
• 但今天已经基本上已经退出了历史舞台
  • 效率问题
• 我们还要讨论栈式计算机的代码生成技术的原因是：
  • 给栈式计算机生成代码是最容易的
  • 仍然有许多栈式的虚拟机
    • Pascal P code
    • Java virtual machine (JVM)
    • Postscript
    • ……

1.4.1 栈式计算机Stack的结构

• 内存
  • 存放所有的变量
• 栈
  • 进行运算的空间
• 执行引擎
  • 指令的执行

1.4.2 栈计算机的指令集

指令的语法

s -> push NUM
   | load x			// 栈操作
   | store x		// 访存
   | add
   | sub		    // 算数运算
   | times
   | div

指令的语义：push

NUM push 到栈上，NUM是立即数，不需要访存

push NUM:
	top ++
	stack[top] = NUM

指令的语义：load x

从内存读到栈上

load x:
	top ++
	stack[top] = x

指令的语义：store x

store x:
	x = stack[top]
	top --

指令的语义：add

add:
	temp = stack[top - 1] + stack[top]
	top -= 2
	push temp

指令的语义：sub

sub:
	temp = stack[top - 1] - stack[top]
	top -= 2
	push temp

指令的语义：times

times:
	temp = stack[top - 1] * stack[top]
	top -= 2
	push temp

指令的语义：div

div:
	temp = stack[top - 1] / stack[top]
	top -= 2
	push temp

1.4.3 变量的内存分配伪指令

• Stack 机器只支持一种数据类型int，并且给变量x分配内存的伪指令是
  • .int x
• Stack 机器在装载一个程序时，就会读取伪指令，并且给相关变量分配内存空间

示例

int x;
int y;
int z;

x = 10;
y = 5;
z = x + y;
y = z * x;

对应的指令为：

.int x
.int y
.int z

1: push 10
3: store x
4: push 5
5: store y
6: push x
7: push y
8: add
9: store z
10: load z
11: load x
12: times
13: store y

1.4.4 栈式计算机的代码生成

1.4.4.1 递归下降代码生成算法：从C到Stack

P -> D S
D -> T id; D 
   | 
T -> int
   | bool
S -> id = E
   | printi(E)
   | printb(E)
E -> n
   | id
   | true
   | false
   | E + E
   | E && E

Gen_P(D S);
Gen_D(T id; D);
Gen_T(T);
Gen_S(S);
Gen_E(E);

指令的语法

s -> push NUM
   | load x			// 栈操作
   | store x		// 访存
   | add
   | sub		    // 算数运算
   | times
   | div

1.4.4.2 递归下降代码生成算法：表达式的代码生成

// 不变式(始终为真)：表达式的值总在栈顶
// emit: 发送指令
Gen_E(E e) 
	switch(e)
		case n:	emit ("push n"); break;
		case id: emit ("load id"); break;
		case true: emit ("push 1"); break;
		case false: emit ("push 0"); break;
		case e1 + e2:
			Gen_E(e1);
			Gen_E(e2);
			emit ("add");
			break;

		case e1 && e2:
			Gen_E(e1);
			Gen_E(e2);
			emit ("and");
			break;
			

1.4.4.3 递归下降代码生成算法：语句的代码生成

// 不变式：栈的规模不变
Gen_S(S s)
	switch (s)
		case id=e: Gen_E(e);
			emit("store id");
			break
		case printi(e): Gen_E(e);
			emit("printi")
			break
		case printb(e): Gen_E(e);
			emit("printb");
			break;

1.4.4.4 递归下降代码生成算法：类型的代码生成

Get_T(T t)
	switch (t)
		case int: emit(".int");
			break;
		case bool: emit(".bool");
			break;

1.4.4.5 递归下降代码生成算法：变量的代码生成

Get_D(T id; D)
	Get_T(T);	// -> .int / .bool
	emit(" id");
	Gen_D(D);

1.4.4.6 递归下降代码生成算法：程序的代码生成

// 不变式：只生成 .int 类型
Gen_P(D S)
	Gen_D(D);
	Gen_S(S);

比如上述程序：

• 先调用该程序的Gen_P
• 然后在 Gen_P内调用 Gen_D, Gen_S
• 在 Gen_D, Gen_S 中在递归调用

1.4.5 如何运行生成代码？

• 找一台真正的物理机
• 写一个虚拟机（解释器）
  • 类似于JVM
• 在 非栈式计算机上进行模拟：
  • 例如，可以在x86上模拟栈式计算机的行为
    • 用x86的调用模拟栈

1.5 寄存器计算机及其代码生成

1.5.1 寄存器计算机

• 寄存器计算机是目前最流行的机器体系结构之一
  • 效率很高
  • 机器体系结构规整
• 机器基于寄存器架构
  • 典型的有16、32或者更多个寄存器
    • 所有操作都在寄存器中进行
  • 访存都通过load/store进行
    • 内存不能直接运算

1.5.2 寄存器计算机Reg的结构

• 内存
  • 存放溢出的变量
• 寄存器
  • 进行运算的空间
  • 假设有无限多个
• 执行引擎
  • 指令的执行

1.5.3 寄存器计算机的指令集

// 指令的语法
s -> movn n, r
   | mov r1, r2			|	数据移动
   | load [x], r		|
   | store r, [x]		|	访存
   | add r1, r2, r3		|
   | sub r1, r2, r3		|	算术运算
   | times r1, r2, r3	|
   | div r1, r2, r3		|

1.5.3.1 变量的寄存器分配伪指令

• Reg 机器只支持一种数据类型int，并且给变量x分配寄存器的伪指令是：
  • .intx
• 在代码生成的阶段，假设Reg机器上有无限多个寄存器
  • 因此每个声明变量和临时变量都会占用一个(虚拟)寄存器
  • 把虚拟寄存器分配到物理寄存器的过程称为寄存器分配

1.5.4 递归下降代码生成算法：从C到reg

Gen_E:

// 不变式：表达式的值在函数返回的寄存器中
R_t Gen_E(E e) 
	switch (e)
        case n: r = fresh();
            	emit("movn n, r");
            	return r;
        case id: r = fresh();
            	 emit("mov id, r");
			    return r;
		case true: r = fresh();
				  emit("movn 1, r");
				  return r;
		case false: r = fresh();
				  emit("movn 0, r");
				  return r;
		case e1+e2: r1 = Gen_E(e1);
				   r2 = Gen_E(e2);
				   r = fresh();
				   emit("add r1, r2, r3");
				   return r;
		case e1&&e2: r1 = Gen_E(e1);
				   r2 = Gen_E(e2);
				   r = fresh();
				   emit("and r1, r2, r3");
				   return r;		// 非短路

Gen_S:

Gen_S(S s)
	switch (s)
		case id=e: r = Gen_E(e);
				  emit("mov r, id");
				  break;
		case printi(e): r = Gen_E(e);
				  	   emit("printi r");
				  	   break;
		case printb(e): r = Gen_E(e);
				  	   emit("printb r");
				  	   break;

Gen_T:

// 不变式，只生成.int类型
Gen_T(T t)
	switch (t)
		case int:	emit (". int");
				    break;
		case bool:	emit(". int");
				    break;

Gen_D:

// 不变式，只生成.int类型
Gen_D(T id; D)
	Gen_T(T);
	emit(" id");
	Gen_D(D);

Gen_P:

// 不变式，只生成int类型
Gen_P(D S)
	Gen_D(D);
	Gen_S(S);

源代码生成了右边的汇编级代码

1.5.5 如何运行生成的代码

• 写一个虚拟机（解释器）
• 在真实的物理机器上运行
  • 需进行寄存器分配