编译原理之目标代码的生成和优化

目标代码生成

一个正式的编译器后端，代码生成部分需要考虑得更加严密才可以。那么具体要考虑哪些问题呢？其实主要有三点：

• 指令的选择。同样一个功能，可以用不同的指令或指令序列来完成，而我们需要选择比较优化的方案。
• 寄存器分配。每款 CPU 的寄存器都是有限的，我们要有效地利用它。
• 指令重排序。计算执行的次序会影响所生成的代码的效率。在不影响运行结果的情况下，我们要通过代码重排序获得更高的效率。

正确的指令

我们为什么非要关注指令的选择呢？

• 按照非常机械的方式翻译代码，这种算法很幼稚，正确性没有问题，但代码量太大，代价太高。
• 指令选择的第二个原因是，实现同一种功能可以使用多种指令，特别是 CISC 指令集（可替代的选择很多，但各自有适用的场景）。
  • 对于某个 CPU 来说，完成同样的任务可以采用不同的指令。比如，实现“a := a + 1”，可以生成三条代码：

    mov a, r0 
    add $1, r0 
    mov r0, a
    

  • 也可以直接用一行代码，采用 inc 指令，而我们要看看用哪种方法总体代价最低：

    inc a
    

分配寄存器

• 寄存器优化的任务是：最大程度地利用寄存器，但不要超过寄存器总数量的限制。
• 寄存器共享的原则：如果存在两个临时变量 a 和b，它们在整个程序执行过程中，最多只有一个变量是活跃的，那么这两个变量可以共享同一个寄存器。
• 寄存器分配是编译器必须要做的一项工作，它把可以使用无限多寄存器的 IR，变成了满足物理寄存器数量的 IR，超出的要溢出到内存中保管。染色算法是其中一个可行的算法。

指令重排序

• 我们通常会把 CPU 看做一个整体，把 CPU执行指令的过程想象成，依此检票进站的过程，改变不同乘客的次序，并不会加快检票的速度。所以，我们会自然而然地认为改变顺序并不会改变总时间。

LLVM 的实现

• LLVM 的后端需要多个处理步骤来生成目标代码：
  
• LLVM 的指令选择算法是基于 DAG（有向无边图）的树模式匹配。
• 基于指令选择的处理结果，我们要对指令进行排序。但因为 DAG 不能反映没有依赖关系的节点之间的排序，所以 LLVM 要先把 DAG 转换成一种三地址模式，这个格式叫做MachineInstr。这个阶段会把指令排序，并尽量发挥指令级并行的能力。
• 接下来做寄存器的分配。LLVM 的 IR 支持无限多的寄存器，在这个环节要分配到实际的寄存器上，分配不下的就溢出到内存。
• 分配完寄存器之后，LLVM 会再做一次指令排序。因为寄存器分配，会指定确定的寄存器，而访问不同的寄存器的时钟周期，可能是不同的。对于溢出到内存中的变量，也增加了一些指令在内存和寄存器之间传输数据。利用这些信息，LLVM 可以进一步优化指令的排序。
• 做完上面的所有工作后，就可以输出目标代码了。

Maximal Munch 算法

• Maximal Munch 直译成中文，是每次尽量咬一大口的意思。具体来说，就是从树根开始，每次挑一个能覆盖最多节点的瓦片，这样就形成几棵子树。对每棵子树也都用相同的策略，这样会使得生成的指令是最少的。注意，指令的顺序要反过来，按照深度优先的策略，先是叶子，再是树根。这个算法是 Optimal 的算法。
• Optimal ，它指的是在局部，相邻的两个瓦片不可能连接成代价更低的瓦片。覆盖算法除了 Optimal 的还有Optimum 的，Optimum 是全局最优化的状态，就是代码总体的代价是最低的。