一种局部寄存器分配的优化策略
姜 军 王 超 尉红梅
【摘 要】摘 要 寄存器作为机器硬件结构中有限的宝贵资源，使得寄存器分配技术成为编译器最为关键的优化技术之一。寄存器分配效率提高的关键在于如何最大限度地减少溢出带来的开销。针对这一问题，提出一种基于局部寄存器需求预估和胖点优化的局部寄存器分配优化策略，并在国产CPU SW1600的配套编译器SWCC上实现了该算法。实验表明，优化效果明显。 【期刊名称】计算机应用与软件 【年(卷),期】2013(000)012 【总页数】4
【关键词】关键词 寄存器分配 局部寄存器需求预估 胖点 SWCC
0 引言
现代计算机系统的性能越来越取决于其存储器层次结构的性能，在芯片内操作速度得到极大提高的同时，内存的性能却基本上保持不变，要使机器的性能跟上处理器的性能，就必须缩短这些延迟。寄存器作为存储器层次结构中操作速度最快的资源，使得寄存器分配技术成为编译器后端中最关键的优化技术之一，寄存器使用效率的高低将直接影响处理器的性能。针对这一点，本文提出了一种基于局部寄存器需求预估和胖点优化的局部寄存器分配优化策略，并在国产CPU SW1600的配套编译器SWCC上实现了该算法。
1 SWCC寄存器分配概述
SWCC是一个C、C++和FORTRAN语言的优化编译器，是通过把开源的Open64［1，2］编译器移植到国产 CPU SW1600上，并针对其体系结构的
特点进行优化得到的。SWCC把寄存器分配分成全局寄存器分配和局部寄存器分配两个阶段。全局寄存器分配采用的是国际上流行的图着色［3］算法，同时加入了优先级考虑以及分裂活跃区间的概念;局部寄存器分配则采用更精确的线性分配方法［4，5］，为基本块一级的局部变量分配寄存器。
2 局部寄存器需求预估
尽管寄存器分配分为全局和局部两个阶段进行，然而这两个阶段是紧密相连的，SWCC采取先做全局寄存器分配，再做局部寄存器分配的策略，那么在全局寄存器分配之前就应该充分考虑局部寄存器分配时的寄存器需求。 2.1 必要性分析
我们先来看另外一种分配时序，即先做局部寄存器分配，然后再做全局寄存器分配，这种情况自然不用考虑预估，然而除此之外弊端更大，虽然局部寄存器分配可以精确地得出每个基本块所需的寄存器数目，但是全局寄存器分配必须把所有的全局变量都分配到相应的寄存器中去，相当于在不考虑溢出的情况下要求相干图被完全着色，它使得图着色方法的难度和时空复杂性［6］变得不可预料。相比之下，这种做法很难实现。
如果采用先做全局再做局部这种分配时序，全局寄存器分配的任务只是按照一定的策略选择一些变量放到全局寄存器中。对那些没分到寄存器的变量可以留给在基本块一级采用线性分配策略的局部寄存器分配处理，问题就会简化很多。然而这样做仍会引发另一个问题:全局寄存器分配对局部寄存器的需求一无所知，只能按悲观的估计留出固定数目的寄存器供局部寄存器分配使用，如果预留的数目不能满足局部变量的需要，那么溢出就是不可避免的。
综上所述，一种比较好的方法是在全局寄存器分配之前对每个基本块进行局部
寄存器需求预估。这样既能够保证局部寄存器分配可以得到足够多的寄存器，同时又没有提高它的复杂度，它仅仅提高了局部寄存器分配的复杂度，而局部寄存器分配的复杂度相对来说比较小。 2.2 实例分析
SWCC在全局阶段给每个基本块预留5个寄存器，当基本块对寄存器的需求数大于5时，就要对其进行局部溢出处理，即在基本块中增加访存指令，如果基本块正好在循环内部，那么增加的访存指令将会产生很大的时间开销。然而，如果对基本块的需求进行预估，局部寄存器分配的压力就会减小，因为预留了寄存器，那么一些全局变量可能会直接溢出，但是这些溢出跨过的范围会更大，完全有可能使访存指令添加在循环之外，从而达到优化的目的。
我们通过一个简单的例子来说明有无预估的效果差异。如图1（a），基本块BB位于循环体内，执行频率为1000，如果全局寄存器分配之前没有进行预估，只简单地假设为5，那么A在全局分配的时候不会溢出，当对BB进行局部寄存器分配的时候，编译器发现5个寄存器并不够用，这时选择的策略很可能就是溢出一个全局寄存器，假设是A，因此在基本块的头尾就会各添加一条访存指令，如图1（b）所示，这样store和load指令都落在了循环内，显然开销要大得多。如果在全局寄存器分配之前加入预估，编译器就可以预先知道BB需要寄存器的数目，比如说需要8个，此时由于全局寄存器分配可用的寄存器变少了，那么A就可能因为无法被分配到寄存器而直接溢出，从而出现图1（c）的情况。而在给BB分配寄存器的时候，由于预留恰当，并不会产生多余的访存，这样就成功地把访存移到了循环之外。通过这个例子可以看出，增加局部寄存器估计能够合理地减少程序执行时间的开销。
一种局部寄存器分配的优化策略
