基于两类寄存器互为缓存方法的DSP寄存器分配溢出处理优化算法
|
摘要
寄存器是处理器硬件中有限的宝贵资源,这使得寄存器分配成为编译器中最为关键的过程之一。影响寄存器分配效果的关键因素之一是溢出带来的访存开销。针对DSP处理器具有两类通用寄存器的情况,以图着色全局寄存器分配方法为基本方法,提出两类寄存器间的一种互补利用策略和相应的寄存器溢出优化算法。该策略改进了传统图着色方法,通过生命周期分析的结果,将同类寄存器分配候选者之间的冲突关系和不同类寄存器分配候选者之间的冲突关系区分开来,并把它们表示在一张无向图中。与传统的图着色算法相比,改进的算法能充分考虑不同类寄存器之间的相互约束关系,减少寄存器溢出时的访存操作,从而有利于提高代码的性能。
Register allocation has become one of the most important optimization techniques for compiler for that registers are limited and valuable resources in hardware architecture of computer.One of the key factors affecting the results of register allocation is the access and storage costs incurred from spilling signed registers.For DSP architectures with two classes of general-purpose registers,this paper proposed a complementary utilization strategy between the registers and a corresponding register spilling optimization algorithm on the basis of graph coloring register allocation method.Through distinguishing the interference between candidates of the same register class from those of different register classes,an undirected graph is built by improving the analysis for variables' live ranges.Compared with the conventional graph coloring register allocation,the improved algorithm fully consideres the interferences among the register allocation candidates for two register classes,thus achiving less memory access operations in register spilling and higher code performance.
Register allocation has become one of the most important optimization techniques for compiler for that registers are limited and valuable resources in hardware architecture of computer.One of the key factors affecting the results of register allocation is the access and storage costs incurred from spilling signed registers.For DSP architectures with two classes of general-purpose registers,this paper proposed a complementary utilization strategy between the registers and a corresponding register spilling optimization algorithm on the basis of graph coloring register allocation method.Through distinguishing the interference between candidates of the same register class from those of different register classes,an undirected graph is built by improving the analysis for variables' live ranges.Compared with the conventional graph coloring register allocation,the improved algorithm fully consideres the interferences among the register allocation candidates for two register classes,thus achiving less memory access operations in register spilling and higher code performance.
引文
[1] AHO A V,SETHI R,ULLMAN J D.Compilers,Principles,Techniques[M].Boston:Addison wesley,1986.
[2] RAU B R,LEE M,TIRUMALAI P P,et al.Register allocation for software pipelined loops[C]//Acm Sigplan Conference on Programming Language Design & Implementation.1992:283-299.
[3] REN K,YAN X L,SUN L L,et al.ASIP register allocator based on improved graph coloring algorithm[J].Journal of Zhejiang University,2010(12):2309-2313.(in Chinese)任坤,严晓浪,孙玲玲,等.基于改进图染色算法的 ASIP 寄存器分配器[J].浙江大学学报(工学版),2010(12):2309-2313.
[4] JIANG J,WANG C,YU H M .A Local Register Allocation Optimization Strategy[J].Computer Applications and Software,2013(12):215-217.(in Chinese)姜军,王超,尉红梅.一种局部寄存器分配的优化策略[J].计算机应用与软件,2013(12):215-217.
[5] BRIGGS P,COOPER K D,KENNEDY K,et al.Coloring,heuristics for register allocation[J].ACM SIGPLAN Notices,1989,24(7):275-284.
[6] CHAITIN G J.Register allocation & spilling via graph coloring[J].ACM Sigplan Notices.ACM,1982,17(6):98-105.
[7] CHAITIN G J,AUSLANDER M A,CHANDRA A K,et al.Register allocation via coloring[J].Computer languages,1981,6(1):47-57.
[8] ACM Transactions on Programming Languages and Systems [M].Association for Computing Machinery,1979.
[9] BRIGGS P,COOPER K D,TORCZON L.Coloring register pairs[J].Acm Letters on Programming Languages & Systems,1992,1(1):3-13.
[10] BRIGGS P,COOPER K D,TORCZON L.Improvements to graph coloring register allocation[J].Acm Transactions on Programming Languages & Systems,1994,16(3):428-455.
[11] PENG Z S,DUAN Y Y,WANG B.Introduction of Mainstream Processor Architecture and Intel Microarchitecture Development[J].Information System Engineering,2017(3):29-31.(in Chinese)彭圳生,段妍羽,王赟.主流处理器架构及英特尔微架构发展分析[J].信息系统工程,2017(3):29-31.
[12] WANG X,FU J W,HE H.Instruction Processing Method Based on ARM Instruction Set in General DSP[J].Microelectronics and Computers,2016,33(9):10-14.(in Chinese)王旭,付家为,何虎.基于ARM指令集的通用DSP中指令相关处理方法[J].微电子学与计算机,2016,33(9):10-14.
[13] NICKERSON B R.Graph coloring register allocation for processors with multi-register operands[C]//ACM Sigplan 1990 Conference on Programming Language Design and Implementation.ACM,1990:40-52.
[14] WOLFE J.Optimizing Super-compilers for Supercomputers[M]// Optimizing Super-compilers for Supercomputers.MIT Press Cambridge,MA,USA,1990.
[15] HUANG L,FENG X B.Combined instruction scheduling and register allocation techniques[J].Application Research of Computers,2008,25(4):979-982.(in Chinese)黄磊,冯晓兵.结合的指令调度与寄存器分配技术[J].计算机应用研究,2008,25(4):979-982.
[16] Instruction Set Manual of YHFT-Matrix2 DSP[G].Institute of Microelectronics,National University of Defense Technology.2013.(in Chinese)YHFT-Matrix2 DSP 指令集手册[G].国防科学技术大学计算机学院微电子所.2013.
[2] RAU B R,LEE M,TIRUMALAI P P,et al.Register allocation for software pipelined loops[C]//Acm Sigplan Conference on Programming Language Design & Implementation.1992:283-299.
[3] REN K,YAN X L,SUN L L,et al.ASIP register allocator based on improved graph coloring algorithm[J].Journal of Zhejiang University,2010(12):2309-2313.(in Chinese)任坤,严晓浪,孙玲玲,等.基于改进图染色算法的 ASIP 寄存器分配器[J].浙江大学学报(工学版),2010(12):2309-2313.
[4] JIANG J,WANG C,YU H M .A Local Register Allocation Optimization Strategy[J].Computer Applications and Software,2013(12):215-217.(in Chinese)姜军,王超,尉红梅.一种局部寄存器分配的优化策略[J].计算机应用与软件,2013(12):215-217.
[5] BRIGGS P,COOPER K D,KENNEDY K,et al.Coloring,heuristics for register allocation[J].ACM SIGPLAN Notices,1989,24(7):275-284.
[6] CHAITIN G J.Register allocation & spilling via graph coloring[J].ACM Sigplan Notices.ACM,1982,17(6):98-105.
[7] CHAITIN G J,AUSLANDER M A,CHANDRA A K,et al.Register allocation via coloring[J].Computer languages,1981,6(1):47-57.
[8] ACM Transactions on Programming Languages and Systems [M].Association for Computing Machinery,1979.
[9] BRIGGS P,COOPER K D,TORCZON L.Coloring register pairs[J].Acm Letters on Programming Languages & Systems,1992,1(1):3-13.
[10] BRIGGS P,COOPER K D,TORCZON L.Improvements to graph coloring register allocation[J].Acm Transactions on Programming Languages & Systems,1994,16(3):428-455.
[11] PENG Z S,DUAN Y Y,WANG B.Introduction of Mainstream Processor Architecture and Intel Microarchitecture Development[J].Information System Engineering,2017(3):29-31.(in Chinese)彭圳生,段妍羽,王赟.主流处理器架构及英特尔微架构发展分析[J].信息系统工程,2017(3):29-31.
[12] WANG X,FU J W,HE H.Instruction Processing Method Based on ARM Instruction Set in General DSP[J].Microelectronics and Computers,2016,33(9):10-14.(in Chinese)王旭,付家为,何虎.基于ARM指令集的通用DSP中指令相关处理方法[J].微电子学与计算机,2016,33(9):10-14.
[13] NICKERSON B R.Graph coloring register allocation for processors with multi-register operands[C]//ACM Sigplan 1990 Conference on Programming Language Design and Implementation.ACM,1990:40-52.
[14] WOLFE J.Optimizing Super-compilers for Supercomputers[M]// Optimizing Super-compilers for Supercomputers.MIT Press Cambridge,MA,USA,1990.
[15] HUANG L,FENG X B.Combined instruction scheduling and register allocation techniques[J].Application Research of Computers,2008,25(4):979-982.(in Chinese)黄磊,冯晓兵.结合的指令调度与寄存器分配技术[J].计算机应用研究,2008,25(4):979-982.
[16] Instruction Set Manual of YHFT-Matrix2 DSP[G].Institute of Microelectronics,National University of Defense Technology.2013.(in Chinese)YHFT-Matrix2 DSP 指令集手册[G].国防科学技术大学计算机学院微电子所.2013.