Register Allocation

寄存器分配问题，为变量分配寄存器。变量的数量可以是无限的，CPU 内部寄存器的数量是有限的，这就牵扯到一个问题，如何为变量分配寄存器。

目前我学习了两种方法，分别是：

• 图染色寄存器分配算法
• 线性扫描寄存器分配算法

Liveness Analysis

无论是图染色算法还是线性扫描算法，都涉及到活跃变量分析。变量在某个程序点有两种状态，live 或 dead。对于变量 x 和程序点 p，判断 x 在点 p 上的值是否会在 CFG 中的某条从点 p 出发的路径中使用。如果是，就说 x 在 p 上 live；否则就说x在p上是 dead。

活跃变量分析的目的是分析程序中每一个程序点的活跃变量。活跃变量的具体过程，我会开一篇新的 blog 来写。

如图，已经分析了每一个程序点的活跃变量

活跃变量分析应该从底向上地分析，考虑每一条指令的 USE / DEF 变量。

活跃变量分析与寄存器分配有什么关系呢?

假设 T1、T2 是程序中的两个变量， 若在任何一个程序点T1 、T2 中最多只有一个变量是 live， 那么 T1 和 T2 可以共用一个寄存器；否则，T1 和 T2 不能共用一个寄存器。

图染色寄存器分配算法

将活跃变量分析的结果构成一个无向图，该图的每个顶点代表一个变量，每一条边代表变量之间的活跃关系，例如某个程序点活跃变量分析结果为：{a, f, c} 则图中 a ，f，c 用边连接起来。考虑所有程序点的活跃变量分析结果，构成一个无向图，这个图叫做推断图(interference graph)

上图中，a 和 b 没有直接连接的边，表示 a 和 b 可以共用一个寄存器；a 和 f 有直连的边，表示 a 和 f 不能共用一个寄存器。

构造好这个图后，下一步就是对该图的顶点 “染色”。 每一个颜色对应一个寄存器。染色规则与寄存器分配规则一致，因此，下文中的染色等价于寄存器分配。

如果一个图可以刚好被 k 种颜色，称这个图为 k-colorable

在寄存器分配问题中，k 指的是寄存器的数量，通过活跃变量分析构造的无向图是 k-colorable，那么这个程序最多用 k 个寄存器。实际上，并不是所有程序满足这样的需求，超过 k 个寄存器就需要 spilling，后面再讨论。

上面程序的寄存器分配结果如下

如何染色

1. 染色是一个 np-hard 问题，没有一个很高效的算法。（Kempe 启发式算法）
2. 染色数量不够（就是寄存器数量不够）

Kempe的启发式算法

Kempe 提出，若移除图中度小于 k 的顶点，构成的图能够被染色，则原图也可以被染色。

启发式染色算法

简单说，就是利用贪心思想，先处理度数较高的顶点，度数越高对图的影响程度也越大。如下图，先移出度数较低的顶点，直到所有的顶点都被移出，再以逆序对移出的顶点染色。

Spilling

无法为所有变量分配对应的寄存器，寄存器数量不够怎么办？这种情况下，有一些变量就需要存储在内存。

例如，假设 k = 3，即寄存器数量为 3

移出 a 顶点后仍不满足 3-coloring，移出 a 顶点后，其余的顶点度数都大于 3，所以这个图不可能只用三个颜色染色。

如果推断图中的每一个顶点的度都大于 k，则该图不可能用 k 个颜色染色，这时候需要选一个顶点作为存储在内存的候选，从图中移出该顶点。这个例子中选择移出顶点 f，继续做 k 染色。

最终移出的顺序为: {c,e,d,b,f,a} (左边是栈顶)

依次为 c， e， d， b 染色

栈中剩余 {f, a}

当给 f 染色的时候发现，已经没有足够的颜色（寄存器）分配给 f，f 只能分配到内存。读写内存又会涉及到寄存器。我们假设给 f 分配的内存地址为 fa

读取 f 之前，需要 load f, fa

修改 f 之后，需要 store f, fa

接下来修改代码

重新计算活跃变量

重新构建推断图

这张图就是 3-colorable，刚好可以分配3个寄存器。

线性扫描寄存器分配算法

引入一个新的概念 Live Interval，就是一个变量的大搞作用范围。

先活跃变量分析

计算变量的 Live Interval，下图中绿色就是变量的 Live Interval

有重叠部分的变量不能用一个寄存器，没有重叠的变量可以用一个寄存器。

很直观，但是效率没有图染色高。