斯坦福cs231(编译原理)の 7 Cool Gode Generation

代码生成简介

将ast转换为汇编代码，具体这里是mips汇编指令，cool里使用了累加寄存器$a0

堆栈在内存中，，堆栈由高地址像低地址扩增

堆栈指针：$sp or $29

具体的mips指令可以参考：misp文档

定义简单函数：

1
2
3
def fib(x) = if x = 1 then 0 else 
						 if x = 2 then 1 else
						 	fib(x-1) + fib(x-2)

对于每一个表达式e，可以生成如下MISP代码：

  • Computes the value of e in $a0（计算表达式e的值，并存储在$a0寄存器中）
  • Preservers $sp and the contents of stack (维护$sp 指针)

这样我们可以定义cgen(e) 表示为e的代码生成，并在最后将e的值存于$a0 中

1
cgen(i) = li $a0 i

代码生成是在编译阶段

汇编代码的执行是在运行时

1
2
3
4
5
6
7
8
cgen(e1 + e2) = 
	cgen(e1)
	sw $a0 0($sp)
	addiu $sp $sp -4
	cgen(e2)
	lw $t1 4($sp)
	add $a0 $t1 $a0
	addiu $a0 $sp 4

其实也就是输出对应的汇编代码

1
2
3
4
5
6
7
8
cgen(e1 + e2) = 
	cgen(e1)
	cout << 'sw $a0 0($sp)';
	cout << 'addiu $sp $sp -4;'
	cgen(e2)
	cout << 'lw $t1 4($sp)';
	cout << 'add $a0 $t1 $a0';
	cout << 'addiu $a0 $sp 4';
  • 上面为+生成汇编代码的过程，可以理解为是一个模板，其中cgen(e1)和cgen(e2)就是插槽
  • 代码生成是递归的，e1和e2也可继续向下生成代码
  • 代码生成可以是沿着AST自顶向下递归的，至少对于表达式是可以的

下面看一个函数的例子，函数有调用和函数定义两部分，这两者都依赖于AR(Active record or function frame)

简单的栈zhen满足如下规则即可：

  • 结果总是存储在$a0 中，比如两者之和就可以存于$a0 中
  • 栈zhen包含实际参数，也就是f(x1, x2, ... xn) 将会push xn, ... x1 入栈
  • 在这个简单的例子只设计参数，不包含局部变量
  • 另外，对于mips架构，需要在栈zhen内记录函数的返回地址
  • 记录函数栈zhen起始地址：fp
  • mips跳转指令：jal label

对于函数调用：

1
2
3
4
5
6
7
8
9
10
11
cgen(f(e1, ... en)) = 
	sw $fp 0($sp)
	addiu $sp $sp -4
	cgen(en)
	sw $a0 0($sp)
	addiu $sp $sp -4
	...
	cgen(e1)
	sw $a0 0($sp)
	addiu $sp $sp -4
	jal f_entry
  • 函数调用的时候，保存了fp
  • 逆序保存了实际参数
  • 函数跳转的时候，返回地址$ra 是自动保存的，这是底层实现的，我们不用管
  • 一个使用了多少空间：4*n + 4 bytes, n是参数个数，+4是一个fp 指针

对于函数定义：

1
2
3
4
5
6
7
8
cgen(def f(x1, ... xn) = e) = 
	move $fp $sp // 新的函数起始地址
	$w $ra 0($sp) // 保存返回地址
	addiu $sp $sp -4 // 扩增
	cgen(e) // 递归生成e
	lw $ra 4($sp) // 加载返回地址
	addiu $sp $sp z // 恢复栈空间
	jal $ra // 跳转回去
  • fp在高地址处
  • callee（被调用者）
  • z = 4 * n + 8，n是实际参数，8是$ra 和 $fp

上面的实现方式可以实现简单函数：

  • 函数不存在局部变量，仅仅有参数
  • 实际参数是caller push入栈的

存在问题：计算的中间结果放在栈内，变量(参数)并不能基于$sp进行偏移量查询，因为不好确定使用了多少中间变量

解决方法：使用fp查询变量(参数)

  • fp始终指向返回地址，这样不管栈怎么扩增，fp是不变的，我们可以始终基于fp查询变量（参数）

xi表示第i个实际参数，那么关于xi的代码生成如下：

1
2
cgen(xi) = 
	lw $a0 z($fp) (z = 4 * i)

🌰：def f(x, y) = e

1
2
3
4
5
6
7
8
9
10
[
old fp,
y,
x,
return addr, <= fp
? <= sp
]
X is at fp + 4
Y is at fp + 8

现实中的寄存器：

  • 尽量将值保存在寄存器中，因为更快
  • 中间值是被设计在AR中，有着一定的排列方式，可以在后续章节中看到如何使用临时变量，并把临时变量存在AR中，而非一味地push和pop

来看一个完整的例子：

1
def sumto(x) = if x = 0 then 0 else x + sumto(x – 1)

为以上函数生成代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#x in ra
sumto_entry:
	move	$fp		$sp				#fp=sp
	sw		$ra		0($sp)			#*sp=ra
	addiu	$sp		$sp		-4		#sp-=4
	lw		$a0		4($fp)			#a0=*(sp+4)(a0=x)
	sw		$a0		0($sp)			#*sp=a0
	addiu	$sp		$sp		-4		#sp-=4	
	li		$a0		0				#a0=0		
	lw		$t1		4($sp)			#t1=*(sp+4)(t1=a0=x)
	addiu	$sp		$sp		+4		#sp+=4
	beq		$a0		$t1		true1	#if a0=t1, goto true1
false1:								#x in sp - 4
	lw		$a0		4($fp)			#a0=*(4+fp)	
	sw		$a0		0($sp)			#*sp=a0
	addiu	$sp		$sp		-4		#sp-=4
	sw		$fp		0($sp)			#*sp=fp
	addiu	$sp		$sp		-4		#sp-=4
	lw		$a0		4($fp)			#a0=*(4+fp)
	sw		$a0		0($sp)			#*sp=a0
	addiu	$sp		$sp		-4		#sp-=4
	li		$a0		1				#a0=1
	lw		$t1		4($sp)			#t1=*(4+sp)
	sub		$a0		$t1		$a0		#a0=t1-a0(a0=x-1)
	addiu	$sp		$sp		4		#sp+=4
	sw		$a0		0($sp)			#*sp=a0
	addiu	$sp		$sp		-4		#sp-=4
	jal		sumto_entry				#goto sumto_entry
	lw		$t1		4($sp)			#t1=*(4+sp)
	add		$a0		$t1		$a0		#a0=t1+a0
	addiu	$sp		$sp		4		#sp+=4
	jal		endif1
true1:
	li		$a0		0				#a0=0
endif1:								#恢复调用前的状态
	lw		$ra		4($sp)			#ra=*(4+sp)
	addiu	$sp		$sp		12		#sp+=12
	lw		$fp		0($sp)			#fp=*sp
	jr		$ra						#goto address in ra

总结：

  • AR必须和代码生成器一同设计
  • 代码生成可以通过遍历AST递归做到
  • 推荐使用堆栈机生成代码，比较简单，大多数语言都是如此

运行时组织：主要是为了组织运行时代码(狭义指运行时代码生成)

代码生成的目标：准确和快

代码生成的两个假设：

  • 代码执行是串行的，即从上至下一个语句接着一个语句按照既定的顺序执行
  • 当程序被调用结束后，控制权应该交给执行本次调用的后一条语句

当然有些语言违背了这两条假设，比如说并行

变量x的生命周期：变量x起作用的一段范围（生命周期是一个动态（运行时）概念，而作用域是一个静态概念）

Rutime Organization

主要是组织代码生成的设计及相关计算模型，涉及以下内容：

  • 运行时的资源管理
  • 存储管理
  • 运行时的计算模型

前面已经讲述三部分内容：

  • Lexical analysis
  • parsing
  • semantic analysis

这三部分都是加强语言定义的方式

程序的执行方式：

  1. OS为该程序分配空间
  2. 代码北加州到这部分空间
  3. OS跳转到程序的入口

程序的内存布局： img

如上，按照传统方式，程序的内存布局如下，上面图片是简化的，实际情况下内存不一定是连续的：

  • 顶部的低地址是代码段

  • 底部的高地址

代码生成的目标：

  • 生成正确的代码
  • 生成的代码快

传统意义上里生成的代码基于以下两个假设：

  • 执行是顺序的，控制流从程序中的一个位置按定义好的顺序移动到另一个位置。
  • 调用过程时，控制流总是返回到调用后的位置。

当然有的程序语言违背了这两个假设，比如可并行运行的语言

程序的激活

激活：对子程序P的调用，称之为对P的激活，P的激活的生命周期为执行P的所有步骤（变量x的生命周期是定义x的执行部分）

生命周期是一个动态的运行时概念，而作用域是一个静态概念

对于非并行程序，激活是线性的

1
2
3
4
5
Class Main {
    g() : Int { 1 };
    f(x:Int): Int { if x = 0 then g() else f(x - 1) fi}; 
    main(): Int {{f(3); }};
}

以上代码生成的激活记录如下：

1
main -> f(3) -> f(2) -> f(1) -> f(0) -> g

基于此，因此堆栈可以跟踪整个激活记录的过程

img

激活记录（栈zhen）

管理一个过程激活所需的信息称为激活记录（AR）或栈帧（frame）

如果过程F调用G，则G的激活记录包含F和G的混合信息。

  • F被“暂停”，直到G完成，此时F恢复。
  • G的AR包含如下内容所需的信息
    • 完成G的执行
    • 恢复执行F
    • G返回值的空间
    • 实际参数
    • 指向上一个激活记录的指针
      • 控制链接； 指向G的caller的AR
    • 调用G之前的机器状态
      • 寄存器和程序计数器的内容
      • 局部变量
    • 其他临时值
  • 将返回值放在第一个栈帧中的优点是，调用方可以在与自己的帧相距固定偏移量的位置找到它；
  • 这个组织没有什么特殊的地方
    • 可以重新排列栈帧元素的顺序；
    • 可以不同地划分caller/call的职责；
    • 如果组织能够提高执行速度或简化代码生成，那么它会更好。
  • 真正的编译器将尽可能多的栈帧保存在寄存器中
    • 特别是方法的结果和参数。
  • 编译器必须在编译时确定激活记录的布局，并生成可正确访问激活记录中位置的代码。
  • 因此，AR布局和代码生成器必须一起设计！

全局变量和堆

  • 所有对全局变量的引用都指向同一个对象
    • 所以无法在激活记录中存储全局变量，因为当前AR结束后，全局变量依旧存在
  • 因此需要为全局变量分配一次固定地址
    • 具有固定地址的变量是“静态分配的”。
  • 根据语言，可能还有其他静态分配的值

动态分配的值不能存放在AR中，Bar值必须在foo的AR释放后依然存在，因为foo的调用者可能使用Bar。：

1
method foo() { new Bar }
  • 具有动态分配数据的语言使用堆来存储动态数据。
  • 代码区域包含目标代码
    • 对于许多语言，目标代码是固定大小和只读的。
  • 静态区域包含具有固定地址的数据（非代码）（例如，全局数据）
    • 固定大小，可能是可读或可写的。
  • 堆栈包含每个当前活动过程的AR
    • 每个AR通常固定大小，并且包含局部变量。
  • 堆包含所有其他数据
    • 在C中，堆由malloc和free管理。
  • 堆和堆栈都会增长
  • 必须注意不要互相影响
  • 解决方案：
    • 将堆和堆栈顶在内存的两端，然后让它们彼此靠近：
img

对齐

大多数现代机器：32/64 bit

1 byte = 8 bits

1 word = 4 or 8 bytes

一般机器要么是按字节要么按字寻址

按字对齐：

example：

1
2
3
4
5
6
[h e l l o ? ? ?][next data]
add 3 padding characters to the string

[byte byte byte byte ?    ?   ?]
										this, word aligned if next data begin from here,
										      this, not word aligned if next data begin from here,

计算模型：堆栈机&寄存器&

堆栈机唯一的存储就是堆栈

  • 指令 $ r = F(a_1, a_2, ..., a_n) $
    • 从堆栈中弹出n个操作数
    • 使用操作数计算操作F
    • 将结果r压入堆栈
  • 考虑如下两条指令
    • push i: 将整数i堆入堆栈
    • add: 相加两个整数

🌰：

1
2
3
4
push 1
push 2
push 3
add
img

累加器机，英文为“Accumulator Machine”，是一种寄存器，用来存储计算产生的中间结果。累加器机模型是一种古老的计算模型，仅能够支持单一值的累加寄存器单元，因此，基于累加器机模型设计的指令都只支持一个操作数

寄存器机，英文为 Register Machine，也译为暂存器机，这种计算模型的机器，使用特定的 CPU 寄存器组，来作为指令执行过程中数据存储和交换的容器。

在寄存器中，由于每一条参与到数据交换和处理的指令，都需要显示地标记操作数所在的寄存器，相较于堆栈机和累加器机，指令更长，但也更加灵活。

堆栈机使用栈结构作为数据存储与交换的容器，由于其“先进后出”的特性，无法直接操作位于栈底的数据，因此，在特殊情况下，机器会使用额外的指令来进行栈数据的交换过程，从而损失一定的执行效率。但另一方面，堆栈机模型实现简单，指令代码长度适中。

累加器机由于只有一个累加器寄存器可用于存储数据，因此在指令的执行过程中，可能会频繁请求机器的线形内存，从而导致一定的性能损耗。但另一方面，该模型最多只能有一个操作数，因此对应的指令代码较为精简。

寄存器机内大多数与数据操作相关的指令，都需要在执行时指定目标寄存器，因此，指令代码的长度较长。寄存器机拥有更多的数据暂存容器，一方面，灵活的数据操作导致寄存器的分配和使用规则变得复杂，另一方面，在使用得当的情况下，同样的计算逻辑，基于寄存器机模型，可以生成更为高效的指令执行结构。

纯堆栈机和纯寄存器机之间有一个中间点：n寄存器堆栈机

从概念上讲，将纯堆栈机堆栈的前n个位置保留在寄存器中。当n=1的时候，该寄存器演变成了累加器机

  • 在纯堆栈机中

    • 一次add执行三次内存操作；
    • 两次读取，一次写入堆栈。

  • 在1寄存器堆栈计算机中，add运算符只要使用如下方式即可：

    • acc <- acc + top_of_stack，acc即累加器寄存器

  • 考虑一个表达式op(e1,…,en)

    • 注意e1,…,en是子表达式。
    • 对于每个ei(0<i<n)
      • 计算ei；
      • 将结果压入堆栈。
    • 从堆栈中弹出n−1个值，计算op
    • 将结果存储在累加器中。

  • 对表达式e求值后，累加器将保留e的值，并且堆栈剩余部分不变。

img
编译原理
#编译原理，计算机基础，cool
斯坦福cs231(编译原理)の 7 Cool Gode Generation
https://mingmingjiang1.github.io/emocoder/2023/06/03/编译原理/编译原理七/
作者
迷途知返
发布于
2023年6月3日
许可协议