COOL Compiler-Part5

PA5

读文档

最后一个 PA，那必然是要把剩下来的文档全部读完。需要预先看一遍带是 cool-tour.pdf 的第7章 Runtime System 和 PA5 handout，至于 cool-manual.pdf 的第13章语义部分倒是可以一边实现一边看。

先看 handout：

代码量巨大无比，竟然是 PA4 的2倍（悲
文件简述：cgen.{cc|hh} 大部分需要写的代码，和 PA4 类似的结构，从 AST 的根节点开始进行 cgen；cool-tree.h 和 PA4 类似；cgen_supp.cc 定义辅助函数；emit.h 里面有一些 MIPS 汇编和符号宏定义；剩下的都是老熟人了。
主要任务：
- 生成全局常量（prototype objects）
- 生成全局表，class_nameTab class_objTab 还有方法调用表
- 生成每个类的初始化代码
- 生成方法定义推荐的实现方法还是分两部分，先生成对象布局，然后第二遍在生成每个表达式的代码。
提醒注意：这次没有必要去“逆向”参考编译器了，因为它实现了一些高级功能比如寄存器分配优化，这个 PA5 并不要求这个。
运行时错误处理：manual 规定了6种运行时错误，生成的代码需要检测三种：(static) dispatch on void, case on void, missing branch；除零可以交给模拟器；剩下两种由 Runtime 处理。
GC：有一个3个命令行开关控制垃圾回收系统相关的功能。默认情况下不打开 -g 开关，此时不启用 GC，也就是说这是一个选做功能；-t 迫使 GC 系统在每次分配对象的时候进行回收；-T 的功能交给实现，可能会用来实现一些其他的运行时检查。实现 GC 功能的时候，需要认真阅读 Runtime 手册相关内容。这里可以去看看 CS143 课程网站上的那个单独的 cool-runtime.pdf，似乎写的更加详细一些。
测试工具：和 PA4 类似，提供了一个 -c 选项来设置全局变量 cgen_debug。同时提供了一个第三方实现的 Coolaid 工具对生成的 MIPS 汇编进行一些检查，说不定会有帮助。最后关于 Spim 的 warning 可能会有用。

然后看看 Runtime System：

首先是对象布局：GC Tag 设为-1；Object Size 也得填上；dispatch pointer 因为不会被 runtime 用到，所以需要自己设计 dispatch 表；对于属性，Int 只有一个32位整数、Bool 也是如此、String 有一个32位的长度+后面全部是 ASCII 字节（最后需要 word 对齐），然后还有空指针 void。
然后是一个叫原型对象（Prototype Object）的东西：COOL 里面新建对象的方法是使用 Object.copy()，因此我们需要生成这些供其复制的东西，也就是 prototype object。生成的时候需要正确设置前面的头部，对于属性，三个基本类型有自己的规定，其余类型的属性随意设置。
栈和寄存器约定：方法调用参数放在栈上、从左到右依次压栈，a0 寄存器里面放 self 对象指针。指定了一组 Scratch registers 供 runtime routine 存放临时数据，因此需要调用者保存；还有堆指针和堆界限两个寄存器，完全由 runtime 控制。其他的都可以用。
Label：生成的代码需要和 runtime 一起变成最后执行的机器码，因此有一些 label 是指定的，就类似于接口一样的东西。有些 label 是 runtime 提供给我们使用的，也有一些需要我们生成供 runtime 使用。有一句话 There is no need for code that initializes an object of class Bool if the generated code contains definitions of both Bool objects in the static data area. 没看懂
执行初始化：Runtime 预定义了一些代码来调用 main 方法。首先通过 Main prototype 生成一个 Main 类的对象并用 Main_init 初始化，该初始化方法依次执行 Main 的基类的初始化最后初始化 Main；然后调用 Main.main，在 a0 里面放上 Main 的指针并设置 ra；执行结束后，Main.main 返回，这里打印出提示信息并终止执行。不过实际上我们并不需要关心这个问题，只需要知道 main 会首先被执行、以及 self object 会被默认放在 a0 里面。

一些踩坑

测评脚本硬编码了一些东西，因此需要进行一些修改以使其能够正常工作。它会调用绝对路径 /usr/class/cs143/bin/spim，这个最好就是复制一份到对应的目录；还有一个问题就是它的 spim 好像和下发的不一样（简单逆向了一下），因此它的标准输出中 spim 的打印信息有一处和我们的 spim 不一样：它的 handler 打印的是绝对路径，而我的是相对路径。试了好几种方法都没法改，看字符串表发现是硬编码的，因此只能改测试样例的标准输出。默认运行会导致数据被重新解压覆盖，因此需要先单独解压，然后修改，实际测试的时候用不重新解压数据的参数。具体如下：

# Assume you are in directory `assignments/PA5/`
sudo mkdir -pv /usr/class/cs143
sudo cp -r ../../bin /usr/class/cs143
sudo cp -r ../../lib /usr/class/cs143
perl pa5-grading.pl -v
find ./grading -type f -exec sed -i 's;/usr/class/cs143/cool;..;g' {} +
perl pa5-grading.pl -r

实现说明

这个里面的细节实在是太多了，如果要全部写清楚的话就很抽象，所以就简单写写要点吧。

在开始之前，建议把它实现的继承树实现给换成 PA4 里面自己写的，这样可以省去看它的抽象代码的功夫。平心而论，他写的基础代码质量真的不咋地，效率低下还有内存泄漏，无力吐槽。

主要的实现还是分成两个部分，第一个部分先线性地去生成一些必要的静态数据表，然后再递归地去生成表达式代码。这也说明了整个代码的结构，前面一堆是数据段，后面一堆是代码段。

关于静态数据的生成，主要参考 Runtime System 说明，里面应该把所有必须生成和建议的实现方式都说到了。然后 skeleton 已经写了一些部分的生成代码，主要看 CgenClassTable::code()，它生成了所有需要用 .globl 声明的符号（但是可能没有定义，具体的符号见 Figure 3）、所有的常量对象（String、Int、Bool 这三种基本类型的字面值常量，都被转换成了静态的对象格式存放在数据段里面）以及 GC 标志。我们需要生成的东西有：

class_nameTab：类名表，按照 class tag 排序
_dispTab：每个对象的函数表，可以自己设计，不过还是直接按照继承和扫描顺序填算了
_protoObj：每个对象的原型对象，建议给每个属性填上默认值，这样后面就可以少生成一些代码，因为复制的时候就相当于已经把没有初始化表达式的属性给赋默认值了，不需要单独生成加载默认值的代码了。
class_objTab：这个在 cool-tour.pdf 里面没写，但是单独的 cool-runtime.pdf 里面写了。它的用处是处理 SELF_TYPE 的东西。如果对象是 SELF_TYPE，就只能通过 class tag 来确定它的运行时类型然后动态绑定，而不能在编译时确定它调用的方法。所以需要一个对象表，里面放上 _init 和 _protoObj，用的时候拿 tag 查表。

为了生成这些表，还需要做一些额外的工作，不过最后思考一下，可以在一次先序遍历中解决所有的问题。为了生成 dispatch 表，需要统计一个类中的所有方法，这就涉及到了继承和重写基类方法；为了生成 protoObj，需要指派 tag 并统计所有的属性，这里也需要考虑继承的问题。因为后面要用到 tag 在运行时判断继承关系，因此 tag 不能随便分配，需要按照遍历顺序依次分配。

做完以上的工作之后，我们就可以开始进行正式的代码生成了。代码生成主要是表达式的生成，最后每个函数包装一下。我基本上就是按照课上讲的 Accumulator 模型写的，除非是调用 Runtime 的地方，其他的代码都仅使用 a0 和 t1 这两个寄存器做计算。不过课上的模型毕竟是简化过的，基本上能生成一大半的代码。剩下的部分需要额外处理局部变量的引入和属性的查询，需要自己写一个从符号到存储位置的映射表。因为我懒得单独做临时变量的地址分配了（其实不难做，只需要额外遍历一次 AST 就可以了），所以分配临时变量就直接压栈了。不过索引临时变量还是用的是 $fp 的相对偏移，因此维护了一个全局变量来记录当前用了分配的变量用的是哪一个地址（类似于一个小的栈，分配的时候+1，离开作用域的时候-1）。函数的参数也在栈上，在函数开始时候要把参数加入到表里。当然，除了栈之外，属性也是映射表的一部分，所以表项要加一个域来指示符号是在栈上还是在堆上（即相对于对象指针的偏移量）。

除了表达式的生成，还有函数的生成。

首先需要确定的就是 calling convention，我是用了比较方便实现的结构：调用者只需要压参数就行了，然后把被调用者所属的对象指针塞进 $a0；被调用者负责保存 $fp,$s0,$ra 这三个寄存器，同时负责回收参数占用的空间。

关于参数，由于 COOL 规定了函数参数从左到右求值（冷知识：C 语言没有规定，取决于编译器实现），因此我让栈顶放最后一个参数（但是正常的系统中是栈顶是第一个参数）这样比较好写（求值一个 push 一个），因此在取参数的时候要特别注意。

关于寄存器的使用，一共涉及到 8 个寄存器

$sp 栈指针，动态变化，需要维护栈平衡
$fp 帧指针，在一个函数上下文中是固定的，用来确定局部变量的位置
$ra 返回地址，没啥好说的。
$s0 存放 self object，每个函数可能不一样，所以要在入口保存旧的并加载新的，在出口恢复旧的。
$a0 有两种情况，一种是作为参数，一般是把目标函数的 self object 放在里面传进过程调用里面；另一种是作为返回值，无论是函数的返回值还是表达式的返回值，反正得到的结果都放在里面。
$t1 临时变量，因为 RISC 架构只能两个寄存器之间做运算。
$a1 $t2 在我的实现中，这两个仅仅是用来给 Runtime 传参数的时候才会设置的，其他地方不会用到也不需要保存。

需要生成的代码有两大块，对象初始化代码和方法代码。
新建一个对象分两步，首先调用 Object.copy 从原型对象复制一份，然后调用对应类的初始化方法来完成属性初始化。初始化方法只有一个参数 $a0 放的是需要被初始化的对象指针，主要是也是两步，先调用基类的初始化代码，然后把自己新增的且有初始化表达式的属性依次按表达式求值。之所以只生成有 init 表达式的属性代码，是因为前面写原型的时候就把那些没有 init 表达式的属性的默认值给填上去了。
方法代码就正常生成吧，不同的是，初始化代码每个类都要生成，而方法代码则不需要生成预定义的5个类的方法。还有就是生成之前记得把参数列表和属性给加到符号表里面。

关于实现部分，就简单描述如上，剩下的细节就去看手册吧，写不动。

完结感言

至此，这个编译器就算是做完了。实验是 3.17 正式开始做的，前天调完最后一个 PA 是 4.1，前前后后做了有半个月的样子，一共写了近 4000 行代码。唯一的感觉是，真累啊。这个 Lab 既没有友好的框架代码，也没有完善的文档说明，工程量还巨大，如果不是我特地去找了找测试脚本，估计还得再多花不少时间写测试样例。总之相比做过的其他几个实验，这个的体验顶多算是及格。

就难度而言，其实是没有多难的，看上去折磨只不过是因为它的不完善导致每个 PA 开始之前会困惑好长时间，然后堆代码堆个上千行，最后调 edge case 再调半天。那些算法一个没做，我觉得倒是不如像 xv6 那样，给一个基础的系统，然后让我写寄存器分配或者是控制流分析这些进阶功能。对于编译的理解，好像也没有在理论课的基础上提升多少：PA1 学习 COOL，没啥大用；PA2 写 flex，练了练怎么写正则表达式；PA3 写 Bison，练了练怎么写 BNF 文法，背后的原理啥也没学会；PA4 写语义检查，也就是实现了课上讲的类型规则系统；PA5 生成代码，纯纯的 MIPS 汇编。

硬要说我学到了什么的话，大概就是了解了一下编译器的完整流程吧。总之不是很推荐做这个实验，有这功夫不如去写写它的 Written Assignment，还有详细的参考答案，感觉比做这个 PA 要更有用那么一些。

无论如何，完结撒花，就酱。