寄存器分配问题,为变量分配寄存器。变量的数量可以是无限的,CPU 内部寄存器的数量是有限的,这就牵扯到一个问题,如何为变量分配寄存器。 目前我学习了两种方法,分别是:
Liveness Analysis无论是图染色算法还是线性扫描算法,都涉及到活跃变量分析。变量在某个程序点有两种状态, 活跃变量分析的目的是分析程序中每一个程序点的活跃变量。活跃变量的具体过程,我会开一篇新的 blog 来写。 如图,已经分析了每一个程序点的活跃变量 image-20210220181511694 活跃变量分析应该从底向上地分析,考虑每一条指令的 USE / DEF 变量。 活跃变量分析与寄存器分配有什么关系呢? 假设 T1、T2 是程序中的两个变量, 若在任何一个程序点T1 、T2 中最多只有一个变量是 图染色寄存器分配算法将活跃变量分析的结果构成一个无向图,该图的每个顶点代表一个变量,每一条边代表变量之间的活跃关系,例如某个程序点活跃变量分析结果为:{a, f, c} 则图中 a ,f,c 用边连接起来。考虑所有程序点的活跃变量分析结果,构成一个无向图,这个图叫做推断图(interference graph) image-20210220183127694 上图中,a 和 b 没有直接连接的边,表示 a 和 b 可以共用一个寄存器;a 和 f 有直连的边,表示 a 和 f 不能共用一个寄存器。 构造好这个图后,下一步就是对该图的顶点 “染色”。 每一个颜色对应一个寄存器。染色规则与寄存器分配规则一致,因此,下文中的染色等价于寄存器分配。 如果一个图可以刚好被 k 种颜色,称这个图为 image-20210220183928133 在寄存器分配问题中,k 指的是寄存器的数量,通过活跃变量分析构造的无向图是 上面程序的寄存器分配结果如下 image-20210220184340321 如何染色
Kempe的启发式算法 Kempe 提出,若移除图中度小于 k 的顶点,构成的图能够被染色,则原图也可以被染色。 image-20210220191254681 启发式染色算法 image-20210220191355930 简单说,就是利用贪心思想,先处理度数较高的顶点,度数越高对图的影响程度也越大。如下图,先移出度数较低的顶点,直到所有的顶点都被移出,再以逆序对移出的顶点染色。 image-20210220191908548 Spilling无法为所有变量分配对应的寄存器,寄存器数量不够怎么办?这种情况下,有一些变量就需要存储在内存。 例如,假设 k = 3,即寄存器数量为 3 image-20210220193509718 移出 a 顶点后仍不满足 3-coloring,移出 a 顶点后,其余的顶点度数都大于 3,所以这个图不可能只用三个颜色染色。 移出a顶点 如果推断图中的每一个顶点的度都大于 k,则该图不可能用 k 个颜色染色,这时候需要选一个顶点作为存储在内存的候选,从图中移出该顶点。这个例子中选择移出顶点 f,继续做 k 染色。 最终移出的顺序为: {c,e,d,b,f,a} (左边是栈顶) 依次为 c, e, d, b 染色 image-20210220194547868 栈中剩余 {f, a} 当给 f 染色的时候发现,已经没有足够的颜色(寄存器)分配给 f,f 只能分配到内存。读写内存又会涉及到寄存器。我们假设给 f 分配的内存地址为 fa 读取 f 之前,需要 load f, fa 修改 f 之后,需要 store f, fa 接下来修改代码 image-20210220194843485 image-20210220194926779 重新计算活跃变量 image-20210220194957943 重新构建推断图 image-20210220195015865 这张图就是 3-colorable,刚好可以分配3个寄存器。 线性扫描寄存器分配算法引入一个新的概念 Live Interval,就是一个变量的大搞作用范围。 先活跃变量分析 image-20210220202054895 计算变量的 Live Interval,下图中绿色就是变量的 Live Interval image-20210220202145894 有重叠部分的变量不能用一个寄存器,没有重叠的变量可以用一个寄存器。 很直观,但是效率没有图染色高。 |
|