实验内容
pa5中我们将完成编译器的后端，至此这个简单的编译器就完成了其所有的阶段。
一个典型的编译器后端分为以下三个步骤(排名分先后)：
指令选择(instruction selection)，为中间代码选择合适的汇编指令，这一阶段的汇编指令中仍然使用类似中间代码的虚拟寄存器
指令调度(instruction scheduling)，通过恰当地安排指令的顺序，发掘流水线等硬件并行性的加速效果，减少访存的延迟的影响，充分利用分支延迟槽等
寄存器分配(register allocation)，为汇编指令中涉及到的虚拟寄存器分配实际的寄存器，同时将无法分配的部分spill到栈上
可以看出第二步对于我们这个简单的编译器其实不是必要的，我们就不实现这个部分了(我们没有考虑mips的分支延迟槽，spim模拟器的默认选项下这个功能也是关闭的)。
值得注意的是，java版本的实验中先进行寄存器分配，后进行指令选择，也就是说寄存器分配的对象是中间代码而非带有虚拟寄存器的汇编代码。这样做也许可以减小一定工作量(存疑，因为我之前做实验的时候也没有觉得这=比我们的框架简单)，然而这样并不便于处理平台相关的信息，例如实现调用约定和spill寄存器等，需要很生硬的在中间代码中强行加入这种并不"中间"的东西，同时也可能失去了一定的优化机会，这在后面会提到。
实验框架已经提供了指令选择，实现的很简单，基本上属于简单的macro expansion[1]方法，不过在mips这种risc指令集下，指令选择的空间不是很大，因此效果也不会和精心选择的结果相比差太多(相比于x86而言)。除macro expansion外，还有例如tree rewriting，dag rewriting等指令选择的方式，感兴趣的同学可以自己查阅资料。
寄存器分配分为局部寄存器分配和全局寄存器分配，局部寄存器分配在基本块层次进行，一般使用一些简单的贪心策略即可，效果一般不如全局寄存器分配；全局寄存器分配可以跨越基本块层次，来到函数层次，甚至跨越函数层次，进行过程间的寄存器分配。全局寄存器分配比较正统的方法一般是图着色和线性扫描，对更多方法感兴趣的同学可以自己查阅相关资料。
框架中已经提供了一个暴力的寄存器分配算法：最简单的寄存器分配，就是不进行寄存器分配，所有的虚拟寄存器都存放在栈中，只利用有限的几个寄存器进行运算，且运算的结果也立即写入内存。不难想象这样的实现是非常低效的。
本阶段的任务是函数层次的全局寄存器分配，我们将会根据论文[2]实现基于图着色的全局寄存器分配，并且要求实现mips调用约定[3]。下面讲解的内容在两篇课程教案[3]中有比较形象的解释，可供参考。讲解的主要目的还是希望大家能获得一个形象的认识，很多地方说的可能不是很精确，其实我个人也认为对代码实现不是很有指导价值。建议大家直接阅读论文[2]，其中有相当详细的伪代码，大家可以用于对照实现。
参考资料:
[1] Instruction Selection: Principles, Methods, and Applications
[2] Iterated Register Coalescing
[3]
Lecture 14 Register Allocation & Spilling
Last updated