斯坦福cs231(编译原理)の 10 Register Allocation

引入

中间代码使用了无限制的临时变量

• 简化了代码生成和优化
• 复杂了向汇编转换的过程

实际情况寄存器是有限的，不能无限制的使用，所以在向汇编转换的时候使用有限的寄存器。

Register allocation is as old as compilers

• Register allocation was used in the original FORTRAN compiler in the ‘50s
• Very crude algorithms

A breakthrough came in 1980 – Register allocation scheme based on graph coloring – Relatively simple, global and works well in practice

思路：

• 将多个临时变量分配给同一个寄存器
• 同时不改变原来的语义

考虑如下程序：

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

如果仅仅使用三个寄存器的话，这里假设a和e在使用完之后立马dead：

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

给众多的临时变量分配有限的寄存器并且相互不冲突这是重中之重：

• 如果在程序在某个运行点临时变量t1和t2不同时存活，那么t1和t2可以共享相同的寄存器
• 否则，t1和t2不能同时分配给一个寄存器

image-20230520152040397

基于之间的活跃变量分析构建无向图(寄存器干扰图, RIG)：

• 节点是临时变量
• 边表示这两个节点对应的变量同时在某个时刻存活
• 如果节点之间没有边，说明节点可以共享一个寄存器

如下：

• 例如，b和c不能在同一寄存器中
• 例如，b和d可以在同一寄存器中

img

RIG构建完成后，寄存器分配算法与体系架构无关，不依赖任何机器属性

图染色

图着色是对节点的颜色分配，使得通过边连接的节点具有不同的颜色

如果一个图可以用k种颜色按照上述规则着色，则该图形为k−colorable（这里的颜色就是寄存器，k为寄存器数量）

进一步的，如果RIG是k−colorable，则存在不超过k个寄存器的寄存器分配。

图染色算法：

The following works well in practice:
  – Pick a node t with fewer than k neighbors
  – Put t on a stack and remove it from the RIG
  – Repeat until the graph has one node
Assign colors to nodes on the stack
  – Start with the last node added
  – At each step pick a color different from those assigned
  	to already colored neighbors

下面这张图里第四个才符合题意

img

变量溢出

image-20230520152930506

在这种情况下，我们无法将所有值都保存在寄存器中，这个时候会选择一些变量放入内存；其他变量继续图染色，这些溢出的变量将会有以下操作：

选择哪些变量溢出呢？

可能的启发式方法：

• spill冲突最多的临时变量（这个时候边比较多）
• spill定义和用途很少的临时变量（因为很少用，放到内存里，也无伤大雅）
• 在内部循环中避免spill（因为循环里一直会复用缓存或者寄存器，如果spill了变量到内存，可能会很大程度降低运行速度，见下面缓存部分）

Before each operation that reads f, insert
f := load fa
After each operation that writes f, insert
store f, fa

image-20230520152957854

重新计算活跃变量：

image-20230520153015201

New liveness information is almost as before

​ – Note f has been split into three temporaries

fi is live only

​ – Between a fi := load fa and the next instruction

​ – Between a store fi, fa and the preceding instr.

Spilling reduces the live range of f

​ – And thus reduces its interferences

​ – Which results in fewer RIG neighbors

image-20230520153209988

管理缓存

缓存的速度介于寄存器和内存中间，可作为缓冲存在，如果没有缓冲的话，寄存器和内存直接交互，由于访问内存的速度远远小于访问寄存器的速度，这样整个程序会是相对较慢的，所以缓存很重要；

image-20230520151753508

通常情况下，寄存器和内存交互的值，会放在缓存里，每次寄存器访问数据先去缓存里查找，如果没有，才去内存里查找，如果缓存一直没有命中，那么缓存也就失去了它的价值。

• 编译器非常擅长管理寄存器
  • 比程序员要好得多
• 但是编译器不善于管理缓存
  • 这个问题仍然留给程序员
  • 尚有一个未解决的问题，编译器可以做些什么来提高缓存性能

考虑如下程序：

for(j := 1; j < 10; j++)
	for(i=1; i<1000000; i++) 
		a[i] *= b[i]

上面的代码由于内部循环很大，而且每次i都会变化，如果缓存没有足够的大小，那么a[i]和b[i]就一直命中不了缓存；相反，下面的代码在10次以内，一定都是可以缓存的，速度至少比上面代码快10倍。

for(i=1; i<1000000; i++)
	for(j := 1; j < 10; j++) 
		a[i] *= b[i]

像这种交换for循环的优化，很少有编译器实现，因为难以发现什么样的循环可以优化，事实上，大部分情况下，还是需要程序员自己去优化这种case的。