寄存器分配：图着色算法

背景
活跃分析
寄存器冲突图
图着色算法
溢出

背景

在编译器的中间表示中，一般会设定虚拟寄存器有无限多个（方便优化），而真实的物理寄存器是有限的，因而编译器后端在将中间表示翻译成目标指令集的时候会进行寄存器分配，也就是将无限的虚拟寄存器映射到有限的物理寄存器上。例如：

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

a + b 后a的寄存器可以被复用，e - 1后e的寄存器可以被复用，因而a、e、f可以分配相同的寄存器。

r1 := r2 + r3
r1 := r1 + r4
r1 := r1 - 1

如果两个两个临时变量t1和t2在不同的程序点只有一个是活跃的，则t1和t2可以分配相同的物理寄存器。否则，如果t1和t2如果同时活跃，则不能分配相同的物理寄存器。

接下来介绍图着色的寄存器分配算法。图着色算法首先要进行活跃分析，得到冲突图，然后通过对冲突图进行着色来解决寄存器分配问题。

活跃分析

变量的活跃分析采用数据流分析的方法，具体可以参阅南京大学的静态分析课程。这里直接给出活跃分析结果：

寄存器冲突图

活跃分析会得到每个程序点同时活跃的临时变量的集合。对于每一个集合（一个程序点）中每一对临时变量形成一条边，并将这些边加入到冲突图中。对程序中每个程序点的集合重复上述过程便形成寄存器冲突图（RIG, register interference graph）。

冲突中，顶点表示临时变量，边用于模拟两个临时变量在相同的程序点同时活跃。冲突图中每两个相连的变量不能分配相同的寄存器，例如a和c。

寄存器分配的问题就可以转换为冲突图图着色问题。图着色是给图的每个顶点进行着色，并且相连的顶点需要着不同的颜色。图的k可着色表示可以用k个颜色对图进行着色。假设物理寄存器个数为k个，如果RIG是可以k可着色的，则可以使用不多于k个寄存器完成寄存器分配。

例如，上述RIG是4可着色的，则可以使用4个寄存器完成寄存器分配。

图着色算法

图着色问题是一个NP-hard问题，但我们可以采用启发式的思想。假设图G有个节点m，它的邻节点个数少于m，令G‘为G-{m}，即G去掉节点m和相应的边形成G'。若G'能够k可着色的，那么G也可以。因为将m添加到已经着色的G'时，m的邻节点至多使用了k-1种颜色，那么总能找到一种颜色为m节点着色。因而可以使用这样的一种简化方法：

选择一个邻节点个数小于k的节点t
将节点t放入栈中，并从RIG中删除
重复上述过程直到图中只剩下一个节点

然后给栈上的节点着色：

从栈顶节点开始着色
每次选择一个不同于已经着色的邻节点的颜色进行着色

例如上述的RIG，k=4，着色过程如下：

1）初始状态：

2）去除节点a：

3）去除节点d：

4）去除节点c：

5）去除节点b：

6）去除节点e:

7）去除节点f：

8）给栈顶节点f着色：

9）给e着色，选择不同于f的颜色：

10）给b着色，选择不同于e和f的颜色：

11）给c着色，选择不同于e、f和b的颜色：

12）给d着色，选择不同于e、f和c的颜色，可以选择和b相同的颜色：

13）给a着色，选择不同于f和c的颜色，可以选择和e相同的颜色：
在这里插入图片描述

这就完成了RIG的着色，也即寄存器分配。但是，对于上述RIG，如果只有3个物理寄存器，再移除a后，则无法进行下去：
在这里插入图片描述
也就是说启发式的着色方法失败了。此时需要采用寄存器溢出的方法对上述方法进行修正。

溢出

寄存器溢出即在栈上申请一块内存来存放临时变量。例如，将f暂时存放在栈fa上，使用时候再从栈上读取。将f溢出到栈上后代码如下：

这里其实使用不同的名字 f1、f2、f3替代f更优，因为这可以减少RIG的边的数量，也即较少f活跃的区间：

此时，重新进行活跃分析，结果如下：

可以得到新的RIG图，并重新使用启发式的图着色方法即可完成寄存器分配，结果如下：
在这里插入图片描述

这里如何选择溢出的变量，有一些启发式的方法：

选择有最多冲突的变量
选择定值和使用比较少的变量
避免溢出循环体内的变量

此外，寄存器分配还可以得到一个额外的优化收获，那就是给move指令的源和目的分配相同的物理寄存器，则可以删除该move指令。

本文介绍了比较经典的图着色的寄存器分配算法，此外目前使用比较广的还有线性扫描算法、整数线性规划算法等。LLVM中支持的寄存器分配算法有4种：Basic Register Allocator、Fast Register Allocator、PBQP Register Allocator、Greedy Register Allocator。大家可以去翻阅LLVM代码了解算法细节。

参考：