# 寄存器分配

寄存器分配算法类型：

1. 线性扫描
    1. Poletto
    2. lifetime hole
    3. linear scan on SSA
2. 图着色
    1. Chaitin
    2. Graph Coloring on SSA
3. Other techniques
    1. Rematerialization
    2. pbqp

# Linear Scan

线性扫描由Poletto等人在1999年首次提出。

线性扫描分配寄存器前需要

1. 对基本块进行排序，给出一个线性序（Depth-First order较优）

2. 决定变量的活跃区间（活跃变量分析）

   [活跃区间的定义]

   变量v的活跃区间为[i,j]表示在任意i'<i或者j'>j的指令，v均不为活跃变量。但在[i,j]内，可能有部分指令处，v也不为活跃变量。

## Poletto

Poletto版本的线性扫描不是在SSA形式上的，需要进行Phi指令消除（同Lab4）

算法介绍如下：

1.前置条件：给定R个可用寄存器和一个活跃区间列表（包含所有变量的活跃区间），该列表以起点（即[i,j]中的i）递增的顺序排列。

2.伪代码：

```C++
//线性扫描算法
LinearScan:
    active <- {}
    //维护有序列表active，存储当前在寄存器中的变量的活跃区间，按终点([i,j]中的j)递增顺序排列
    for each live interval i, in order of increasing start point
    //遍历所有变量的活跃区间
        ExpireOldIntervals(i)
        //移除所有过期的区间
        if length(active) = R then //表示此时所有寄存器均不空闲
            SpillAtInterval(i)
            //溢出一个当前活跃区间
        else //存在空闲的寄存器
            register[i] <- a register removed from pool of free registers
            //为变量i赋予一个空闲的寄存器
            add i to active, sorted by incresing end point
            //将i的活跃区间加入active，并排序

//移除所有过期的区间：
//过期区间：终点在新区间起点之前的区间
ExpireOldIntervals(i):
    for each interval j in active, in order of increasing end point
     //遍历列表active
        if endpoint[j] ≥ startpoint[i] then
         //当找到一个未过期区间后退出循环
            return
        remove j from active
        //在active中移除过期区间
        add register[j] to pool of free registers
        //释放过期区间对应的寄存器

//溢出一个当前活跃区间：
//决定要溢出哪个区间有多种选择方法，此处我们选择溢出终点最晚的区间（即列表active中最后的区间或者新区间)
SpillAtInterval(i):
    spill <- last interval in active
    //spill初始化为active中最后的区间
    //比较列表active中最后的区间和新区间
    if endpoint[spill] > endpoint[i] then //溢出active中最后的区间
        register[i] <- register[spill]
        //spill的寄存器给新区间所代表的变量
        location[spill] <- new stack location
        remove spill from active
        add i to active, sorted by increasing end point
        //spill移出active，i加入active
    else //溢出新区间
        location[i] <- new stack location
```

3.算法复杂度分析：变量个数为V，寄存器个数为R。当查找列表方式为二分查找时，复杂度为$O(V\log R)$，为线性查找时，复杂度为$O(VR)$。



更多介绍参考如下文章：

[http://web.cs.ucla.edu/~palsberg/course/cs132/linearscan.pdf](http://web.cs.ucla.edu/~palsberg/course/cs132/linearscan.pdf)

## Live Ranges with Lifetime Holes

Poletto版本的活跃变量区间是一大块的，它没有考虑到区间的lifetime hole，即 "不需要变量值的区间"。

以下两篇文章在非SSA形式上处理了带有hole的活跃变量区间

[https://dl.acm.org/doi/10.1145/277650.277714](https://dl.acm.org/doi/10.1145/277650.277714)

[https://dl.acm.org/doi/10.1145/1064979.1064998](https://dl.acm.org/doi/10.1145/1064979.1064998)

## Linear Scan on SSA

以上参考文献都在非SSA形式上工作，对于llvm ir，需要将phi指令手动转换成赋值语句，比较麻烦

这篇文章在SSA形式上进行线性扫描

[https://dl.acm.org/doi/10.1145/1772954.1772979](https://dl.acm.org/doi/10.1145/1772954.1772979)

其简要思想即为在代码生成阶段进行phi resolution

### 建议

不进行Phi指令消除，对SSA form的IR进行最简易的线性扫描（Poletto），在emitting machine code时插入move指令

# Graph Coloring

图着色寄存器分配是解决寄存器分配的主要方法，其生成的代码质量较线性扫描更高，但是也更加耗时。

在这种算法中，图的节点代表活跃变量区间，两个节点相连代表存在相互干扰的区间，即至少在一个程序点上同时存在的区间。然后，寄存器分配简化为图的着色问题，其中颜色（寄存器）被分配给节点，使得由边连接的两个节点不会得到相同的颜色。

使用活跃变量分析，可以建立一个interference graph干扰图。干扰图是一个无向图，其中的节点是程序的变量，用来模拟哪些变量不能被分配到同一个寄存器。

## Chaitin

经典算法，伪代码见

[https://dl.acm.org/doi/10.1145/872726.806984](https://dl.acm.org/doi/10.1145/872726.806984)

## Graph Coloring on SSA

SSA带来的特性能够简化图着色，参考

[https://dl.acm.org/doi/10.1007/11688839_20](https://dl.acm.org/doi/10.1007/11688839_20)

# Rematerialization

Chaitin等人讨论了几个提高溢出代码质量的想法。他们指出，某些数值可以在一条指令中**重新计算**，而且所需的操作数总是可以用来计算的

[https://dl.acm.org/doi/10.1145/143103.143143](https://dl.acm.org/doi/10.1145/143103.143143)

## PBPQ

LLVM的其中一个分配器，采用线性规划，参考

[https://dl.acm.org/doi/10.1007/11860990_21](https://dl.acm.org/doi/10.1007/11860990_21)

[https://dl.acm.org/doi/abs/10.1145/513829.513854](https://dl.acm.org/doi/abs/10.1145/513829.513854)