程序分析与优化 - 8 寄存器分配 - 周荣华

Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

寄存器分配

• 寄存器分配是为程序处理的值找到存储位置的问题
• 这些值可以存放到寄存器，也可以存放在内存中
• 寄存器更快，但数量有限
• 内存很多，但访问速度慢
• 好的寄存器分配算法尽量将使用更频繁的变量保存的寄存器中

• 寄存器指派
• 寄存器溢出处理
• 寄存器使用合并

8.1.2 寄存器的约束

calling convention（调用约定）

8.2 线性扫描

• 给定一个区间序列，重叠的区间必须给定不同的颜色，求最小颜色数。
• 贪婪着色有最优算法
• 但线性扫描不是贪婪着色的最优算法，而是最优算法的一个近似解。

8.2.3 区间线的线性扫描算法

``` 1 LINEARSCANREGISTERALLOCATION♧
2   active = {}
3   foreach interval i, in order of increasing start point
4     EXPIREOLDINTERVALS(i)
5     if length(active) = R then
6       SPILLATINTERVAL(i)
7     else
8       register[i] = a register removed from the pool of free registers.
9       Add i to active, sorted by increasing end point
10
11 EXPIREOLDINTERVALS(i)
12   foreach interval j in active, in order of increasing end point
13     if endpoint[j] ≥ startpoint[i] then
14       return
15     remove j from active
16     add register[j] to pool of free registers
17
18 SPILLATINTERVAL(i)
19   spill = last interval in active
20   register[i] = register[spill]
21   location[spill] = new stack location
22   remove spill from active
23   add i to active, sorted by increasing end point```

8.2.4 合并

``` 1 LINEARSCANREGISTERALLOCATIONWITHCOALESCING
2   active = {}
3   foreach interval i, in order of increasing start point
4     EXPIREOLDINTERVALS(i)
5     if length(active) = R then
6       SPILLATINTERVAL(i)
7     else
8       if definition of i is "a = b" and register[b] ∈ free registers
9         register[i] = register[i(b)]
10         remove register[i(b)] from the list of free registers
11       else
12         register[i] = a register removed from the list of free registers
13       add i to active, sorted by increasing end point```

8.2.5 生命周期黑洞

x出现后，a和b都不会再使用，也就是说x肯定是可以和a或者b共用一个寄存器的。

8.3 基于图着色的寄存器分配

8.3.1 干涉图（The Interference Graph）

• 每个变量是图的一个结点；
• 如果两个变量的生命周期存在重叠，则这2个节点在图上邻接，也就是存在一条边将2个节点连接起来，这样的边也称为干涉边（interference edges）。
• 除了干涉边，如果2个变量存在且仅存在一条move指令将2个变量关联起来，则在2个变量之间画一条虚线，称为合并边（coalescing edges）

8.4 循环进行寄存器合并

8.4.3 Coalesce

Briggs：节点a和b能合并当且仅当ab有更少的高阶（≥k）邻接节点

George：节点a和b能合并，当且仅当，所有a的邻接节点要么和b相互干涉，要么是一个低阶节点

8.4.6 溢出算法（Spilling Heuristics）

```1 SPILLCOST(v)
2   cost = 0
3   foreach definition at block B, or use at block B
4     cost += 10^N/D, where
5       N is B's loop nesting factor
6       D is v's degree in the interference graph```

8.5 寄存器分配简史

1. Chaitin, G., Auslander, M., Chandra, A., Cocke, J., Hopkins, M., and Markstein, P. "Register allocation via coloring", Computer Languages, p 47-57 (1981)，首次将图着色引入寄存器分配
2. George, L., and Appel, A., "Iterated Register Coalescing", North Holland, TOPLAS, p 300-324 (1996)，引入寄存器合并的迭代过程
3. Poletto, M., and Sarkar, V., "Linear Scan Register Allocation", TOPLAS, p895-913 (1999)，将线性扫描引入寄存器分配