编译原理

Lab4 Report

2020-06-12 00:00 CST
2020-07-15 20:11 CST
CC BY-NC 4.0

1. 文件结构

本次新增的内容如下:

  • asm.c:MIPS汇编翻译器,函数前缀为AS

2. MIPS指令翻译

MIPS指令的翻译分为两个步骤:

  • 扫描一遍中间代码,为每个函数计算栈区大小,并为每个局部变量分配内存单元(用与$fp的偏移量来表示位置);
  • 再次扫描一遍中间代码,将线性IR翻译为MIPS指令列表;
  • 最后将之前计算栈区大小、分配内存使用的临时的内存空间回收。

2.1 寄存器分配

本次实验采用了最不动脑子的朴素分配方案。包括函数参数在内的所有数据都保存在内存上。需要使用时读入到寄存器,运算后马上把新的值溢出到内存中去。正是因为所有的值都保存在内存上,因此除了readwrite函数,没有人会使用$a0-$a3寄存器;这个做法也避免了函数调用前后需要保存、恢复这四个寄存器的问题。

2.2 内存单元分配

计算栈区大小并分配内存单元时,使用红黑树作为数据结构进行查询(一套红黑树用了三次实验,但每次都要重新看代码才能想起来自己的接口长什么样)。

  • ASPrepareFunction初始化函数栈的大小(栈的大小最小为8,负责保存栈指针和返回地址),并遍历函数中的IR指令,将其中使用到的局部变量、参数注册并分配内存地址;
  • ASRegisterVariable负责将一个IR Operand注册到红黑树数据结构中,并且在当前栈顶偏移量处新增一块内存来存储数据。

此处内存单元的分配参考的是实验的附录中Procedual Call Convention部分的内容,即函数参数保存在$fp的正方向,第一个参数的偏移量为0,而局部变量保存在$fp的负方向;第一个局部变量的偏移量为-12(前面两个是栈指针和返回地址,第三个单元才开始保存变量)。偏移量使用了size_t无符号数作为类型,所以它的最高位比特用来标记正向还是负向。如果最高位为1则为函数参数,在正方向;否则为局部变量,在负方向。

2.3 函数调用过程

由于采用朴素寄存器分配方案,函数调用中除了栈指针和返回地址,其他没有需要保存的内容。

  • 调用者负责将参数压入栈,函数调用结束后弹出;
  • 被调用者负责移动栈顶指针并保存栈指针$fp和返回地址$ra。执行return语句前需要恢复栈指针和返回地址,并恢复原先的栈顶指针。

3. 遇到的问题和实验总结

本次实验实现的比较简单,只遇到了SPIM出现了读取未对齐内存的错误。原因主要有三个:

  • 客观原因:MIPS架构本身限制lwsw指令的内存地址必须是4字节对齐的;
  • 主观bug1:定义红黑树上值的排序函数写炸了,直接导致同一个变量无法在红黑树中被找到,所以就被分配了多次内存,运行时程序读取了不同的数据;
  • 主观bug2:C–语言所有数组、结构体强制按引用(4字节地址)传值,但却按照对象的大小分配了参数的内存空间,导致读取了错误的地址和数据。

回顾这个学期的实验,四次实验中用到最多的还是红黑树(如果实验二用declarative style就可能是哈希表了)。幸好当时把红黑树实现成了抽象的数据结构,通过void *指针和函数指针的搭配接收任何类型的数据,才能在后面的实验一直用一直爽。面向将来可能出现的需求,实现一个好的API设计非常重要。(实验讲义的确也是这么说的)

致谢:依然是董杨静Massimo同学的测试仓库和测试脚本以及各路大佬的测试数据(含Lab3的官方数据)。