skaiuijing

引言

编译器后端设计的一个问题就是代码生成，而代码生成的关键问题之一就是决定哪个值放在寄存器里面。

CPU的寄存器数量通常是有限的，当寄存器不够时怎么办呢？没有放在寄存器中的值必须放在内存中，但是寄存器本身就是最快的内存，因此，如何合理利用寄存器呢？

这就是寄存器的两大问题：寄存器分配和指派。从数学上来看，这个最优问题是NP完全的。

寄存器分配

对于源程序中的每个点，我们选择一组将被存放在寄存器中的变量。

寄存器指派

我们指定一个变量被存放在哪个寄存器中。

方法

我们可以把目标程序中特定值分配给特定的寄存器，比如，我们可以把基地址指派给一组寄存器，算术寄存器则使用另一组寄存器，栈顶指针指派给一个固定的寄存器。

例如：我们要对数组int[10]中的每个成员进行运算，其实我们只需要记录数组基地址就行了，在后面的循环中，在基地址的基础上加上偏移，就能得到要运算的变量的地址。

这种方法的优点是使代码生成器变得简单，但是寄存器使用的效率却可能很低。

我们可以把一些寄存器指派给频繁使用的变量，并且使得这些寄存器在不同几百块中的指派保持一致。

在这里，我们关注的重点内容是循环，因为程序大部分时间都会花在内部循环上。

假设把x加载到寄存器中的成本是两个成本单元，如果把x分配到寄存器中，对x的每次引用可以节省一个单位。

注意：这里的单位个人认为其实包括很多方面，例如CPU周期、内存等等。

对于循环L的每个出口基本块B，如果后续仍然要被使用，那么我们必须以两个成本单元进行保存。

然而，假设循环将迭代多次，我们可以忽略这些支出，因为每次进入循环时，这些指令只会运行一次。因为优化器更关心“每次迭代的代价”，保存的成本在“每次迭代的平均成本”里几乎可以忽略。所以会把这些一次性支出从循环内的成本模型中剔除。

如果我们假设块只迭代一次，那么有：

1	估算公式：全部基本块求和: use(x, b) + 2*live(x, b)

其中use(x, b)，是x在被保存到寄存器之前被使用的次数。因为x肯定是要被加载到寄存器中进行运算中，我们统计的收益截止时间就是在没有被运算然后加载到寄存器中之前。

如果x在B的出口处活跃且在B中被赋值，那么live(x, b) = 1，否则为0.

例如：

A块：

1
2
3

a = b + c
d = d - b
e = a + f

B块：

1 2	b = d + f e = a - c

有：

1 2	graph LR Aa(acdef)-->Ab(acdf)

在A块中，变量a被使用了两次，且在块的出口处活跃。

假设我们要把a保存到寄存器中，那么可以节省：

1	use:2 + 2 * live:1 = 4

其实和内层是一样的，这里不过多概述了。