Stanford Compiler Week 6 Code Generation Part 1
课程主页：
https://www.edx.org/course/compilers
课程视频：
https://www.bilibili.com/video/BV1NE411376V?p=20&t=6
备注：
图片均来自于课件。
这次回顾代码生成第一部分。
代码生成简介
- 我们专注于为带有累加器的堆栈机生成代码；
- 我们想在真实的机器上运行生成的代码，例如MIPS处理器（或模拟器）；
- 我们使用MIPS指令和寄存器模拟堆栈机指令；
- 累加器保存在MIPS寄存器$\mathrm{$ a_0}$中；
- 堆栈保存在内存中
- 堆栈向低地址生长，这是MIPS的标准约定。
- 堆栈中下一个位置的地址保存在MIPS寄存器$\mathrm{$sp}$中
- 栈顶在地址$\mathrm{$sp} +4$处。
MIPS简介
MIPS架构是
- 原型精简指令集计算机（RISC）
- 大多数操作都将寄存器用于操作数和结果
- 使用load和store指令在内存中使用值
- 32个通用寄存器（每个32位）
- 我们使用$\mathrm{$ sp,$a0}$和$\mathrm{$t1}$（临时寄存器）
- 阅读SPIM模拟器文档以获取详细信息。
常用指令
- $\text {lw reg}_{1} \text { offset}(\mathrm{reg}_{2})$
- 从$\mathrm{reg}_{2} + \text{offset}$加载32比特字到$\text{reg}_1$
- $\text {add } \mathrm{reg}_{1} \text { reg}_{2} \text { reg}_{3}$
- $\mathrm{reg}_{1} \leftarrow \mathrm{reg}_{2}+\mathrm{reg}_{3}$
- $\text {sw reg}_{1} \text { offset}(\text {reg}_{2})$
- 从$\text{reg}_1$加载32比特字到$\mathrm{reg}_{2} + \text{offset}$
- ${\text {addiu reg}_{1} \text { reg}_{2} \text { imm}}$
- $\mathrm{reg}_{1} \leftarrow \mathrm{reg}_{2}+\mathrm{imm}$
- “$\text{u}$”意味着不查看溢出
- $\text {li reg imm }$
- $\text {reg} \leftarrow \text {imm }$
例子
考虑MIPS中$7 + 5$的堆栈机代码：
| 堆栈机代码 | MIPS汇编代码 |
|---|---|
| $\mathrm{a c c} \leftarrow 7$ | $\mathrm {li\ $a0\ 7}$ |
| $\text {push acc}$ | $\mathrm{sw\ $a 0\ 0($s p)}$ |
| $\mathrm {addiu\ $sp\ $sp-4}$ | |
| $\mathrm{a c c} \leftarrow 5$ | $\mathrm {li\ $a0\ 5}$ |
| $\text {acc} \leftarrow \text{acc + top_of_stack }$ | $\mathrm {lw\ $t1\ 4($sp) }$ |
| $\mathrm {add\ $ a0\ $a0\ $t1}$ | |
| $\text{pop}$ | $\mathrm {addiu \ $ sp\ $sp+4}$ |
代码生成1
讨论的语言
考虑具有整数和整数运算的语言
对于该语言
第一个函数定义$\mathrm f$是入口
- “main”程序
我们可以写出斐波纳契数的程序：
该语言的代码生成
- 对于每个表达式$\mathrm e$，我们生成以下MIPS代码：
- 计算$\mathrm {$a0}$中$\mathrm e$的值
- 保留$\mathrm {$sp}$和堆栈中的内容
- 我们定义一个代码生成函数$\mathrm{cgen(e)}$，其结果是为$\mathrm e$生成的代码。
常数代码生成
评估常数的代码只是将其复制到累加器中：
其中
- 红色：编译时
- 蓝色：运行时
加法的代码生成
考虑加法的例子：
代码说明：
- $\mathrm{sw\ $ a0\ 0($ sp)}$将$\mathrm{$a0}$存储到栈顶的位置。
- $\mathrm {addiu\ $sp\ $ s p\ -4}$更新栈顶位置。
- $\mathrm{lw\ $t1\ 4($sp)}$将$\mathrm{$a0}$存储到$\mathrm{$t1}$。
- $\mathrm{add\ $a0\ $t1\ $a0}$对应$\mathrm{e_1 +e_2}$
- $\mathrm {addiu\ $sp\ $ s p\ +4}$更新栈顶位置。
注意不能将$\mathrm e_1$的结果直接保存在$\mathrm {$t1}$中：
考虑如下反例
1 + (2 + 3)对应的mips代码
li $a0 1
move $t1 $a0
li $a0 2
move $t1 $a0
li $a0 3
add $a0 $t1 $a0
add $a0 $t1 $a0
#$a0 = 2 + 3 + 2 = 7讨论
$\mathrm{+}$的代码是一个模板，该模板包括$\mathrm{e_1}$和$\mathrm{e_2}$部分加上”hole”:
代码：
code(e1) ... code(e2) ...
堆栈机代码生成是递归的：
- $\mathrm{e_1 + e_2}$的代码是将$\mathrm{e_1}$和$\mathrm{e_2}$代码粘合在一起。
代码生成可以写为AST的递归下降
- 至少对于表达式。
减法的代码生成
新指令：$\text {sub } \mathrm{reg}_{1} \text { reg}_{2} \text { reg}_{3}$
- 实现功能：$\mathrm{reg}_{1} \leftarrow \mathrm{reg}_{2}-\mathrm{reg}_{3}$
条件指令
新指令：$\text {beq reg}_{1} \text { reg}_{2} \text { label }$
- 实现功能：如果$\mathrm{reg_1 = reg_2}$，则跳转到$\text{label}$。
新指令：$\text{b label}$
- 无条件跳转到$\text{label}$
MIPS代码
习题
分析：
如下代码对应$(4 - 3)$
li $a0 4
sw $a0 0($sp)
addiu $sp $sp -4
li $a0 3
lw $t1 4($sp)
sub $a0 $t1 $a0所以选择第一项。
代码生成2
函数调用和函数定义的代码取决于AR的布局
对于此此语言，非常简单的AR就足够了：
- 结果始终在累加器中
- 无需将结果存储在AR中
- 激活记录保存实际参数
- 对于$\mathrm {f(x_1,\ldots,x_n)}$，将$\mathrm {x_n,\ldots, x_1}$推入堆栈
- 这些是该语言中唯一的变量
- 结果始终在累加器中
堆栈规则保证$\mathrm{$sp}$在函数退出与函数开始前
- 无需控制链接
我们需要返回地址
指向当前激活的指针很有用
- 该指针位于寄存器$\mathrm{$fp}$（栈帧指针）中
总结：对于这种语言，带有caller栈帧指针，实际参数和返回地址的AR就足够了
图示：考虑对$\mathrm{f(x,y)}$的调用，AR是：
调用序列是（调用方和被调用方的）设置函数调用的指令。
jal指令
新指令：$\text{jal label}$
- 跳转至label，将下一条指令的地址保存在$\mathrm {$ra}$中
- 在其他架构上，返回地址通过“调用”指令存储在堆栈中
调用者保存其帧指针的值
然后以相反的顺序保存实际参数
最后，调用者将返回地址保存在寄存器$\mathrm {$ra}$中
到目前为止，AR为$4 \times n + 4$字节长
例子：
jr指令
- 新指令：$\text{jr reg}$
- 跳转到寄存器$\text{reg}$中的地址
- 注意：栈帧指针指向栈帧的顶部，而不是底部
- 被调用者弹出返回地址，实际参数和帧指针的保存值
- $\mathrm {z = 4 \times n + 8}$
- $8$对应返回地址和旧栈帧
- 例子：
变量引用
变量引用是最后的构造
函数的“变量”只是其参数
- 它们都在AR中
- 被caller push
问题：由于在保存中间结果时堆栈会增长，因此变量与$\mathrm{$sp}$的偏移量不是固定的。
解决方案：使用栈帧指针
- 始终指向堆栈上的返回地址
- 由于它不移动，因此可以用来查找变量
令$\mathrm{x_i}$为为其生成代码的函数的第$\mathrm{i}$个（$\mathrm{i=1,\ldots,n}$）形式参数
例子：对于函数$\text{def f(x,y) = e}$，激活和帧指针的设置如下：
习题
选择第一和第四项。
小结
- 激活记录必须与代码生成器一起设计；
- 可以通过递归遍历AST来完成代码生成；
- 我们建议您为Cool编译器使用堆栈机（因为这很简单）；
- 生产级编译器做不同的事情；
- 重点在于将值保存在寄存器中
- 特别是当前的栈帧；
- 中间结果放置在AR中，而不是从堆栈中push和pop。