附加题

完备的寄存器分配作为附加内容.

完备的寄存器分配

区别于不完备的寄存器分配, 我们规定一个完备的寄存器分配必须处理在寄存器指派中遇到没有任何寄存器空闲也无后续不再用到的变量占用寄存器的情况, 我们称之为 "处理冲突".

"处理冲突" 的方法一般是通过将一个正在占用寄存器的变量的值存到栈上, 将这个寄存器空闲出来, 这个过程我们又称为 "寄存器夺取", 将 "把一个寄存器的值存到栈上" 称为 "溢出".

栈约定

我们约定数据的储存空间在内存的首地址为 0x0, 于是你可以基于 x0 寄存器与偏移量定位内存空间.

寄存器分配做到什么程度也是一个宽泛的概念. 下面给出几个可以卷的点:

如何处理寄存器冲突. 按照较为朴素的想法, 每次遇到寄存器冲突就按一定方法选择一个被占用的物理寄存器, 将这个寄存器的值存到内存中, 同时将寄存器原先关联的变量关联到内存位置上. 然而在实际操作时会存在一些问题, 如何解决这些实现上的麻烦并成功完成寄存器夺取是实现上首先要考虑的点.
寄存器分配的策略. 如溢出寄存器时应溢出哪个寄存器. 最优的寄存器分配是一个 NPC 问题, 但可以通过合理的选取方法取得较优选择.
如何维护栈空间使得栈空间占用更小, 以提升访存效率.
对于基于 x0 的偏移量超过 lw, sw 指令立即数范围的访存如何解决 ?

对于本实验来说, 只要跑过样例 reg-alloc.txt 即可视为成功完成完备的寄存器分配. 我们的样例 reg-alloc.txt 也只是对于这点做验证.

Info

根据此样例的特点, 实际上对前端传来的 ir 进行重排可以直接将样例转化为一个在代码生成时寄存器不会冲突的样例, 我们不鼓励这种写法, 且此方法实现难度也较大, 但也欢迎同学们进行尝试.