一种基于分区域优先级的寄存器分配算法

A Register Allocation Algorithm Based on Regions Priority

编译器速度和生成代码质量是衡量寄存器分配阶段性能的两个关键因素,现代的即时编译器要求在尽可能短的时间内编译出高质量的代码。传统的基于图着色的算法和线性扫描算法均不能很好地满足这个要求,该文提出一种基于矩阵填充的区域优先级寄存器分配算法,不追求理论上完美的寄存器分配,而采用贪婪式的方法,对程序循环区域进行分割,按区域内生命域的长度和溢出权重两种优先级排序方法进行物理寄存器分配,再扩展到整个程序段。算法在保留线性分配时间的同时产生了高质量的代码,应用于编译SSA形式的PTX指令到多核平台的过程中,基于该编译平台的实验证明了该文改进算法的有效性。

Compiling speed and code quality are two key factors to evaluate the performance of register allocation. Modern Just In Time （JIT） compilers desire the best code in least time. Neither traditional graph coloring algorithm nor linear scan algorithm can satisfy the condition perfectly. A regions priority algorithm is proposed in this paper, which does not pursue the perfect register allocation in theory but takes greedy design method. The program is divided by loop region, on which physical register allocation is implemented by dealing lifetime length priority queue and spill weight priority queue. Then the allocation extends to the whole program. This algorithm creates high quality code in linear time and is applied to the compiler which compiles PTX instructions in SSA to traditional multicore platform. The experiment based on this compiler verifies the effectiveness of the algorithm.