> For the complete documentation index, see [llms.txt](https://mashplant.gitbook.io/decaf-doc/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mashplant.gitbook.io/decaf-doc/pa5/shi-yan-nei-rong.md).

# 实验内容

pa5中我们将完成编译器的后端，至此这个简单的编译器就完成了其所有的阶段。

一个典型的编译器后端分为以下三个步骤(排名**分先后**)：

1. 指令选择(instruction selection)，为中间代码选择合适的汇编指令，这一阶段的汇编指令中仍然使用类似中间代码的虚拟寄存器。可以将这一步的结果看成更低一级的中间代码
2. 指令调度(instruction scheduling)，通过恰当地安排指令的顺序，发掘流水线等硬件并行性的加速效果，减少访存的延迟的影响，充分利用分支延迟槽等
3. 寄存器分配(register allocation)，为汇编指令中涉及到的虚拟寄存器分配实际的寄存器，同时将无法分配的部分spill到栈上

第二步对于我们这个简单的编译器其实不是必要的，我们就不实现这个部分了(我们没有考虑mips的分支延迟槽，spim模拟器的默认选项下这个功能也是关闭的)。

实验框架已经提供了指令选择，实现的很简单，基本上属于简单的macro expansion\[1]方法，不过在mips这种risc指令集下，指令选择的空间不是很大，因此效果也不会和精心选择的结果相比差太多(相比于x86而言)。除macro expansion外，还有例如tree rewriting，dag rewriting等指令选择的方式，感兴趣的同学可以自己查阅资料。需要说明的是，目前我们的框架中经指令选择生成的指令有很多都是伪指令，这些指令需要汇编器或者spim模拟器的协助才能正确翻译为真正的mips汇编；而且，为了实现诸如`Print`之类的内部函数，我们用到了很多spim模拟器设定的系统调用，而并非实际os(如linux)规定的系统调用。

寄存器分配分为局部寄存器分配和全局寄存器分配。局部寄存器分配在基本块层次进行，一般使用一些简单的贪心策略，效果往往不如全局寄存器分配，一般只会应用在一些对编译速度和开销非常重视的场景里，如一些运行在低端设备上的jit编译器。全局寄存器分配可以跨越基本块层次，来到函数层次，特定情况下甚至可以跨越函数层次，进行过程间的寄存器分配，实际的编译器大多数采用全局寄存器分配。全局寄存器分配比较正统的方法一般是图着色和线性扫描，对更多方法感兴趣的同学可以自己查阅相关资料。

框架中已经提供了一个暴力的寄存器分配算法：最简单的寄存器分配，就是不进行寄存器分配，所有的虚拟寄存器都存放在栈中，只利用有限的几个寄存器进行运算，且运算的结果也立即写入内存。不难想象这样的实现是非常低效的。

本阶段的任务是实现全局寄存器分配，我们将会根据论文\[2]实现基于图着色的全局寄存器分配，并且要求实现mips调用约定\[4]。下面讲解的内容在两篇课程教案\[3]中有比较形象的解释，可供参考。这个文档的讲解的主要目的还是希望大家能对相关概念获得一个形象的认识，很多地方说的可能不是很精确，其实**我个人也认为对代码实现不是很有指导价值**。建议大家直接阅读论文\[2]，其中有**相当详细的伪代码**，大家可以用于对照实现。

实验框架中已经基本搭建好了寄存器分配的框架，理想状况下应该只需要修改`graph_alloc.rs`，只关心寄存器分配的算法即可，对于指令集的各种细节理论上应该完全无需在意。不过为了能够更好的理解整个过程，还是建议大家认真阅读相关代码和文档。

参考资料(可能需要科学上网):

\[1] [Instruction Selection: Principles, Methods, and Applications](https://www.diva-portal.org/smash/get/diva2:951540/FULLTEXT01.pdf)

\[2] [Iterated Register Coalescing](http://www.cse.iitm.ac.in/~krishna/cs6013/george.pdf)

\[3]

[Lecture 14 Register Allocation & Spilling](https://www.cs.cmu.edu/afs/cs/academic/class/15745-s16/www/lectures/L14-Register-Allocation.pdf)

[Lecture 23 Register Allocation: Coalescing](https://www.cs.cmu.edu/afs/cs/academic/class/15745-s16/www/lectures/L23-Register-Coalescing.pdf)

\[4] [MIPS Calling Convention](https://courses.cs.washington.edu/courses/cse410/09sp/examples/MIPSCallingConventionsSummary.pdf)

\[5] [Register Allocation & Spilling via Graph Coloring](https://cs.gmu.edu/~white/CS640/p98-chaitin.pdf)