后端设计

编译器后端的主要功能是将中间表示（IR）转换为目标架构的汇编代码，在我们的课程实验中即将TAC翻译为RISC-V汇编代码。与目标机器架构紧密相关的优化也会在这一阶段进行。

代码生成

目标代码的生成是后端的核心部分。通常中间表示不会与目标架构的汇编代码非常相似，一方面它们所用的指令不一样，另外中间表示也会省略掉与物理寄存器和函数调用的若干细节。这要求我们在将IR翻译为汇编指令时处理好这些缺失的部分，生成合法的汇编程序。

指令选择

对于一条IR指令，选择合适的汇编指令对应物。对于大部分算术指令，一对一翻译即可，这没有什么难度；而某些IR指令没有直接的相应汇编指令，需要被翻译为多条汇编指令。你可能需要选择相对更优的候选指令序列。一对多指令翻译包含一些微妙之处，比如可能引入额外的寄存器、有潜在的副作用、干扰数据流分析，有时将它们视为一个指令整体是更合理的选择。你可能需要恰当地选择将一条“指令”彻底地转化为汇编指令的时机。

这里举几个例子：

• 逻辑与和逻辑或。可详见step4。
• 函数调用。函数调用通常不止一条call指令，在它之前需要生成传参的指令（参数少时用mv，多的时候压栈），在它之后可能要修改栈指针。
• SSA IR中的Phi指令。通常Phi指令会被翻译为mv指令，但留意多条Phi指令同时存在的情况，它们在语义上“同时发生”，而实际指令序列具有顺序，这可能导致寄存器中的值被错误覆盖。

寄存器分配

IR里通常会假设数量无限的虚拟寄存器（或称作变量），但目标ISA（Instruction Set Architecture）通常只允许有限数量的物理寄存器，我们必须将虚拟寄存器映射到物理寄存器上。如果物理寄存器无法容纳所有的活跃变量，它们就需要溢出（spill）到栈上。大多数架构上寄存器访问开销显著低于内存访问开销，因此我们应尽量避免发生spill。

课程实验使用的寄存器分配算法非常简单，它以基本块为单位，在基本块结束处活跃的变量会全部被spill到栈上。你会发现这个算法显得比较愚蠢，产生了大量实际无用的load和store指令。因此，你需要实现一个“全局”的寄存器分配算法，它应当能够跨基本块进行分析。（这里的“全局”通常以函数为粒度）

常见的全局寄存器分配算法包括图染色和线性扫描。由于我们并没有较为严格的编译时间要求，大家可以使用step13中提到的图染色算法。该算法的一个优势在于能够顺带处理mv指令，可以消除掉无用复制，这使得你前面做代码生成时可以轻松一点（能够较为无顾虑地生成mv指令）。

寄存器分配算法中存在一个比较微妙的地方：当我们不得不选择一个变量spill时，优先选择哪个变量。通常这里是启发式的，我们需要对每个变量设置一个优先级或溢出权重（spill weight）。假设我们已知一个变量中存放的是常数，那么它的保存和恢复开销都会比其它变量更低：无须保存，恢复时只需一条li指令而不必生成load。这种低spill开销的变量可以优先成为被踢出内存的倒霉蛋候选。（思考：我们是否应该优先spill循环体中的变量？）为了给变量设定合理的溢出权重，你可能需要依赖一些分析pass的结果。

栈帧确定和最终代码生成

在代码生成的早期阶段我们无法确定最终栈帧的大小。比如在寄存器分配阶段产生的溢出变量会使得栈帧大小增加，我们需要追踪栈上变量的偏移量和大小。留意load和store指令中允许的立即数偏移范围，当一个函数具有巨大的栈帧时，你可能需要插入一些额外的代码来计算栈上的地址或访问栈上的变量，甚至需要重新进行寄存器分配。

在这里我们介绍一种可能的实现方式。我们暂不考虑VLA（variable-length array），即认为栈上的所有对象都可以在编译期确定大小。首先我们将栈上的对象统一抽象为StackObject，包括栈上的数组、溢出的临时变量、用栈传入的函数参数。然后所有对栈的操作均使用单独的“指令”，例如

• LoadFromStack t0, obj, offset: 将栈上对象obj偏移offset（立即数）处的内容加载到 t0
• StoreToStack t0, obj, offset：将t0中的内容写入到栈上对象obj偏移offset处
• LoadStackAddr t0, obj, offset：计算栈上对象obj偏移offset处的地址，将结果存放在t0

代码生成的大部分阶段均保持以上指令形式。最终确定栈帧时，统计所有栈上对象并为它们赋予一个相对栈帧的偏移。如果你打算在生成的代码中使用栈帧指针fp（frame pointer），展开的指令中可以直接使用这个偏移；如果你打算用栈指针sp进行寻址，你最好维护指令序列中sp发生的变化并计算栈上对象相对于sp的偏移（主要为了应对涉及栈传参的函数调用）。

最终我们将以上的这些“指令”展开。例如LoadFromStack可以保守地展开为以下RISC-V指令序列：

li   t0, (some immediate offset)
add  t0, sp, t0
ld   t0, 0(t0)

但大多数时候ld t0, offset(sp)就足够了。需要注意的是StoreToStack可能无法展开，也许要在更早的阶段引入额外的临时变量并将其变换为LoadStackAddr和一条store指令。

确定栈帧后生成函数的prologue和epilogue，其中主要包括callee-saved寄存器的保存与恢复、对栈指针的调整。注意有些架构可能对栈指针有对齐要求（e.g. 必须是8的整数倍）。

附：函数调用相关

处理函数调用通常需要插入额外的指令用于传参，而寄存器传参的调用约定又和寄存器分配有一定关系。在Iterated Register Coalescing的论文中并没有提及函数调用约定的处理方式，在这里以RISC-V为例进行一些说明。一种直观的想法是将函数参数对应的临时变量直接预着色为对应的参数寄存器，但这样的方案存在较明显的问题。下面展示两个C语言片段：

int f(int x) {
    // lots of stuff...
    return x;
}

在这个例子中，如果我们将x对应的临时变量直接绑定到参数寄存器a0上，那么a0即x具有超长的生命周期，可能与大量的临时变量节点相干涉。如果中间的代码含有其它函数调用，对a0的使用存在冲突，有可能需要生成大量load/store。

int swap(int x, int y) {
    // ...
    swap(y, x);
    // ...
}

对于外层swap，直观上x和y会被分别绑定到a0和a1；而中间再次调用swap时却又要求y在a0且x在a1中，这种冲突免不了一番折腾。

可以发现问题在于我们强行把参数变量和参数寄存器的生命周期绑定在了一起，而事实上调用约定只要求在传参时参数变量位于指定寄存器中。在函数体其它部分的代码中，调用约定不关心也管不着参数变量到底在哪个寄存器里。你可能会反驳：我们其实也关心，尽量让参数变量分配到对应的参数寄存器中有助于减少无意义的move指令。没错，但这个步骤可以交给寄存器分配算法和后续优化处理，在生成代码时我们更关注代码逻辑，应当将参数变量和传参时的寄存器解耦。

具体而言，这种解耦可以通过插入新的临时变量和move指令实现。（在下面的描述中只考虑寄存器传参）

• 调用其它函数前：假设函数调用的实参位于临时变量x1至xn中。那么我们引入新临时变量T1到Tn，然后按照mv Ti, xi的方式将全部xi移入Ti中，接下来再生成mv aj, Ti复制到目标参数寄存器。注意这里的2n条mv指令形成了两阶段，每个阶段内部的move指令顺序不重要，但不要跨阶段移动指令。
• 处理在寄存器中的传入参数：假设函数的形参对应临时变量x1到xn。直接在函数开头生成mv xi, ai即可。

以上面的swap函数为例子，插入上述辅助指令后的汇编伪代码如下：

swap:
    mv x, a0 # 1
    mv y, a1 # 2

    # first move phase
    mv _T0, x # 3
    mv _T1, y # 4

    # second move phase
    mv a0, _T1 # 5
    mv a1, _T0 # 6
    call swap

在经过带move合并的寄存器分配后，大概率会得到这样的汇编代码：

swap:
    mv t0, a0
    mv a0, a1
    mv a1, t0
    call swap

这里引入了最少数量的额外寄存器，正是我们所期望的变量交换代码。首先前两条mv指令提示寄存器分配算法合并x和a0、y和a1，这一分配方案是可行的，因此前两条无用mv被消去。接下来我们注意到_T0与a1相干涉（指令4的Use集合、指令3的LiveOut集合包含a1，_T0在指令3的Def集合中），因此_T0不能被分配到a1；同时_T0也与a0相干涉（指令6的Use集合，指令5的LiveOut集合包含_T0，a0在指令5的Def集合中），最终_T0被分配到一个新的寄存器t0。而_T1可以安全地被分配到a1，故指令4被视作无用指令消除。

在生成函数调用的代码时，除传参外，还需要考虑caller-saved寄存器的处理。在我们的基本实验框架中，你可以在call指令前后保存并恢复活跃且在caller-saved寄存器中的变量，这样在其它指令看来是无事发生。不过在这里有一种更简便的实现方式：将所有caller-saved寄存器加入到call指令的Def集合中，剩下的事情交给寄存器分配算法处理。考虑以下C语言片段：

int getint();
void putint(int);

int main() {
    int x = getint();
    putint(x);
    return x;
}

在寄存器分配前可能对应如下代码：

main:
    # prologue

    call getint
    mv   x, a0

    mv   a0, x # ... omitted
    call putint

    mv   a0, x
    # epilogue
    ret

采用上述方式，x处于call putint的LiveOut集合中，会与全部的caller-saved寄存器相干涉，这样x就会自动被分配到callee-saved寄存器上。经过后续优化可能的最终汇编代码如下：

main:
    # prologue
    call getint
    mv   s0, a0
    call putint
    mv   a0, s0
    # epilogue
    ret

目标架构相关优化

这里简单地举几个例子。

1. 指令选择相关的窥孔优化

   此类优化指的是将局部的几条指令替换为更优的指令序列的一类优化，并非特指。需要注意的是此类优化较为琐碎，建议按需实现。

   例如以下的RISC-V指令序列

    li t0, 0
    bne a0, t0, label1
   

   可以被替换为bne a0, zero, label1，后续再通过无用指令消除去掉li t0, 0（假设该值不再使用）。总的来说，一类优化机会包括识别出指令序列中的常量，尝试将它们嵌入至指令中（RISC-V的I型指令），并进行无效果指令消除（mv到自身、加0、乘1）、强度削减（乘除2的幂转移位，除法转乘法）等优化。

   再举一个ARM的例子。ARM的访存指令支持基址+索引*4的寻址模式（类似x86），以下汇编指令序列

    mov r1, r1, LSL #2
    add r0, r0, r1
    ldr r0, [r0]
   

   可以被合并为一条指令：

    ldr r0, [r0, r1, LSL #2]
   

   这种汇编代码模式在数组访问中较为常见。

2. 指令调度

   指令调度指的是在不影响指令逻辑的前提下调整指令的顺序，目的之一是利用现代处理器的特性提升指令级并行度。基本块内的指令调度首先会利用指令间的依赖关系构造DAG，然后利用关键路径长度、寄存器压力、处理器发射宽度等因素结合处理器功能单元的执行模型依次决定指令的执行顺序。感兴趣的同学可以自行查看相关资料。