第27卷第9期2004年9月
计算机学报CHINESE JOURNAL OF COMPUTERS
VoI.27No.9
Sept.2004
刘
张兆庆
（中国科学院计算技术研究所
北京100080）（中国科学院研究生院
北京100080）
收稿日期：2002-12-27；修改稿收到日期：2004-05-28.本课题得到国家自然科学基金（69933020）和英特尔公司资助.刘，男，1973年生，
博士研究生，主要研究方向为指令级并行、寄存器分配、多线程和低功耗编译技术.E-maiI ：Iy@张兆庆，女，1938年生，
研究员，博士生导师，主要研究方向为先进编译技术及相关编译环境.
摘要安腾
0-GKRCp
处理器引入了硬件控制的寄存器栈，寄存器栈引擎能够自动地改变寄存器栈帧指针，对栈寄
存器进行保存和恢复，从而有效地减少跨越过程调用时的寄存器值的保存和重新载入.每个过程使用的栈寄存器数量可以通过aIIoc 指令显式地指定.通常的过程内寄存器分配方法给过程分配最大需要数量的栈寄存器.但过多的栈寄存器使用会引起寄存器栈溢出/载入.如果频繁出现这样的寄存器栈溢出/载入，将严重影响程序执行性能.该文提出了一种创新的算法，能够有效地减少RSE 代价.该算法已经在开放源码编译器ORC 中得到了实现.实验
表明，SpecINT2000在使用该算法后性能普遍提高，perIbmk 的性能提高了14%，而crafty 也有3.2%的性能提高.关键词
寄存器栈；寄存器栈引擎；寄存器栈溢出/载入
中图法分类号TP302
Inter-procedural Register Allocation for RSE Optimization
LIU Yang
ZHANG Zhao-oing
（Institute of Computing Technology ，Chinese Academy of Sciences ，Beijing 100080）
（Graduate School of Chinese Academy of Sciences ，Beijing 100080）
Abstract In Itanium 0-GKRCp architecture ，a hardware managed register stack is introduced ，register stack engine （RSE ）can change the register stack frame pointers and spiII /fiII registers automaticaIIy.This mecha-nism can reduce Ioad /store operations of register across caII sites efficien
tIy.The number of stacked registers used by a procedure couId be specified by aIIoc instruction expIicitIy.TraditionaI intra-proceduraI register aIIo-cation aIgorithm wiII aIIocate max stacked registers reguired by a procedure but no more than the totaI number of stack registers.But high stack register pressure wiII Iead to freguent register stack spiII /fiII.If this event happens freguentIy ，the performance wiII be seriousIy harmed.This paper proposes an innovative aIgorithm ，which couId reduce the RSE cost efficientIy.This aIgorithm is aIready impIemented in ORC.ExperimentaI re-suIts show that the performance is improved obviousIy when this aIgorithm is appIied ，especiaIIy for perIbmk ，it has 14%performance improvement and crafty aIso has 3.2%performance improvement.Keywords
register stack ；register stack engine ；register stack spiII /fiII
1引言
寄存器分配问题，就是从需要使用寄存器的变量中选择出一个子集，放置到有限的寄存器中，从而达到尽量减少内存和寄存器间的传送开销，也就是
使程序在实际运行中执行的加载/存储操作减低到
最少的目标.研究者们已经对这个问题进行了深入
广泛的研究，并且提出了很多有效的算法［15］
.因为寄存器数量是有限的，所以对于某些没有分配到寄存器的变量，只能在使用它时把它从内存取出，执行完操作以后又把它重新存到内存里.这样的处理叫做溢出处理（spiII ）
.
除了因为过程内寄存器分配时某些变量不能得到寄存器而导致的溢出处理以外，还有很多其他原因引起的加载和存储操作.例如，在变量!的活跃区间跨越过程调用点时，被调用过程可能会使用到变量!使用的寄存器r.因此，在过程被调用之前，需要对跨越调用点的活跃区间使用的寄存器进行保存；而过程返回以后，又需要把这些寄存器从内存重新载入.研究者们针对该问题进行了很多研究，并提出了一些软件的解决方法［6，7］.
安腾0-GKRcp（Itanium0-GKRcp）处理器［8］选择了一种硬件实现方法来解决这个问题.在安腾0-GKRcp处理器中，共有l28个通用寄存器，它们被划分为两个部分：r0r3l是静态寄存器，它们对于所有过程都是可见的；r32rl27是栈寄存器，除了用于参数传递的寄存器以外，它们仅对某个特定的过程是可见的.仅对某个特定的过程可见的寄存器一起形成一个寄存器栈帧，栈帧的大小是由编译器显式地指定的.发生过程调用时，当前栈指针通过硬件自动移动到为被调用过程新分配的寄存器栈帧；过程返回时，当前栈指针又回到调用者栈帧上.这种机制避免了在跨越调用点时对于寄存器的保存和加载.寄
存器栈引擎（Register Stack Engine，RSE）是一个处理器状态机，当被调用过程要求的寄存器栈帧大于现有的可用寄存器数目时，它负责把栈中的部分寄存器拷贝到（或者从后备存储区载入）后备存储区（backing store）中，给被调用过程腾出足够的可用栈寄存器；当函数返回，它又把溢出的栈寄存器从后备存储区载入到寄存器栈中.当发生栈寄存器溢出/载入事件时，程序被阻塞，直到这个过程完成为止.
虽然这个机制大大地减少了跨越过程调用时的加载/存储操作，但是寄存器栈溢出/载入（register stack spiII/fiII）事件所造成的RSE开销也是不容忽视的.实验证明，RSE开销在有些程序中严重地影响了执行性能.使用pfmon l.l版对Spec2000INT的可执行代码进行运行时测试，发现perIbmk的执行时间中RSE开销竟然占据了23%，而crafty的RSE代价也高达4.8%.快速发展的cPU处理速度会让RSE开销在整个执行时间中所占的比例越来越大，使得该问题更加严重.
本文提出了一种全新的解决方法.在第一遍编译时，使用通常的寄存器分配，得到每个过程的寄存器使用情况反馈信息.在第二遍编译时的过程间优化阶段，读入反馈信息，并基于过程调用图，给每个过程分配一定的栈寄存器预算使用数量.在后端优
化的全局寄存器分配阶段，按照寄存器预算使用数量进行寄存器分配，每个过程使用的栈寄存器最多不得超过预算使用数量.这个算法已经在开放研究编译器ORc上实现，实验证明该算法对于控制RSE
开销和提高程序执行性能十分有效，特别是对于perIbmk，性能提高了将近l4%，crafty也有3.2%的性能提高.
本文第2节对寄存器栈的背景知识做了简单的介绍；在第3节，我们讨论了国际相关工作；第4节分析了实例，对解决的方法进行了讨论；第5节描述了算法的详细实现；第6节给出了实验数据并对实验数据进行了分析；第7节总结了本文并对未来的工作提出了展望.
!寄存器栈的背景介绍
!."寄存器栈和它的动作
栈寄存器对于每个过程来说是局部的.仅对某个给定过程可见的栈寄存器一起组成一个寄存器栈帧.每个寄存器栈帧包括4个部分：
（l）输入寄存器，input registers；（2）本地寄存器，IocaI registers；（3）输出寄存器，output registers；（4）旋转寄存器，ro-tating registers.旋转寄存器是为了方便对程序进行软流水优化处理.输入和旋转寄存器都包含在本地寄存器里.寄存器栈帧的大小是本地寄存器+输出寄存器.在Itanium0-GKRcp处理器中，每个寄存器栈帧最多可以有96个栈寄存器.寄存器栈帧的大小可以由编译器通过aIIoc指令显式地指定：
aIIoc〈target-reg〉=ar.pfs in，IocaI，out，rot"
寄存器栈引擎负责把寄存器栈帧映射到物理寄存器组的栈寄存器上，这个过程对于编译器是透明的.当一个过程被调用时，栈寄存器被重命名，从而调用者寄存器栈帧中输出寄存器的第一个变成被调用者寄存器栈帧中的r32.参数通过调用者寄存器栈帧的输出部分传递到被调用者.被调用过程从它的寄存器栈帧输入区读取参数.当被调用者返回时，寄存器再次重命名为调用者的寄存器栈帧.这个机制使得调用者的寄存器栈帧可以被保存在寄存器中而不是储存到内存里去.
这里我们用一个例子来描述寄存器栈的行为.在图l中，过程foo（）有一个从r32开始的寄存器栈帧，而过程bar（）的寄存器栈帧也是从r32开始的.执行代码只能看到和一个给定过程相关联的寄存器栈帧.
2
2.2寄存器栈的载入和溢出
当一个过程被调用时，RSE会为它分配一个寄存器栈帧，最多有96个寄存器.如果没有足够未使用的栈寄存器，它就会溢出一部分已使用的栈寄存器来腾出足够多的空间.溢出的栈寄存器值被保存到一块叫做后备存储区的内存区域中.当一个过程返回并当前过程的寄存器栈帧已经被溢出到后备存储区时，RSE需要把这个寄存器栈帧从后备存储区重新取出，放到栈寄存器中.这个过程由RSE自动执行，对编译器是透明的.
这里用一个例子来描述寄存器载入和溢出的行为.假设有三个过程，foo（），bar（）和par（）.Foo（）调用bar（）而bar（）调用par（）.如果foo（）和bar（）用完了所有96个栈寄存器，那么当par（）被调用时，foo（）的寄存器栈帧将被RSE溢出到后备存储区.当bar （）返回时，foo（）的寄存器栈帧又被RSE从后备存储区载入到栈寄存器里.这个过程会阻塞程序的执行，因此耗费大量的时间.
3国际相关工作
DouiIIet等［9］提出了一种通过在程序控制流的不同路径上插入aIIoc指令来减少RSE开销的方法.因为在程序控制流图的不同路径上，需要使用的寄存器数量是不同的，因此，该算法尝试在需要寄存器较少的路径上插入aIIoc指令来改变寄存器栈帧的
大小，从而达到减少调用点的RSE溢出的目标.但他们的实验数据很不理想，因为aIIoc指令本身也有不少开销，结果导致整体性能下降.David等［10］对RSE开销给出一个量化的估算，并且提出了一种硬件解决方法，该算法本质上是AIban等提出算法的一种硬件实现.在模拟器上的实验证明减少了很多RSE动作.但是硬件实现的代价很高，并且没有实际的机器运行性能比较.Pro64编译器也在消除RSE 开销这个问题上进行了一些工作.在Pro64编译器中，栈寄存器被划分为两个部分：栈调用者寄存器和栈被调用者寄存器（stacked caIIer registers and stacked caIIed registers）.栈调用者寄存器指的是寄存器栈帧的输出部分，而栈被调用者寄存器指的是寄存器栈帧的本地部分.如果一个活跃区间跨越过程
调用点，那么它就被分配到栈被调用者寄存器，否则被分配到栈调用者寄存器.这样，可以尽量地扩大输出部分，增加调用者和被调用者寄存器栈帧的重叠部分.但是，即使采取了这样的措施，用Pro64编译得到SpecINT2000的可执行代码运行时仍然有严重的RSE问题，perIbmk的RSE仍然达到了24%.
4问题的分析
4.1RSE开销的测量
假设有一条动态的调用路径p
1
p2…p i
!-1
p i，p i…p n.当过程p i被调用时，过程p j后在寄存器栈里的z个栈寄存器被溢出到后备存储区中.那么，当过
程调用结束，并且逐层返回到过程p
j
时，被溢出的z 个栈寄存器又会被载入到寄存器栈里.通常情况下，只要程序执行不在调用路径上中途退出，栈溢出（stack spiII）寄存器的个数和栈载入（stack fiII）寄存器的个数应该是相等的.因此，栈寄存器溢出和栈寄存器载入可以合起来看作一次寄存器栈溢出/载入.
只有被调用过程需要的栈寄存器数量大于当前寄存器栈中可用栈寄存器数量时，才会发生寄存器
栈溢出/载入.在调用路径p
1
p2…p i
!-1
p i，p i…p n.
上，设过程p
i!-1
被调用并分配寄存器栈帧以后，寄存器栈还剩余x个未使用的寄存器，而被调用过程p i需要y个栈寄存器，如果y>x，那么至少需要溢出z=y-x个栈寄存器.利用pfmon1.1版，我们研究了Itanium0-GKRcp处理器上的RSE开销和需要溢出/载入的栈寄存器个数z之间的关系.用于实验的程序包括4个过程，它们的调用关系是：A调用B，B 调用C，C调用D.A，B，C总共分配了96个栈寄存
3
器.这样，在D 被调用的时候，剩余的可用栈寄存器为0.只要过程D 需要多于0个的栈寄存器，就会发生寄存器栈溢出/载入.实验中D 分配的栈寄存器栈帧大小从1递增到96，每次分配的栈帧大小增加1.用pfmon 测量程序当过程D 分配不同数量栈寄存器时运行的RSE 开销，结果如图2所示.图中横轴表示过程D 需要的栈寄存器数量，即需要溢出/载入的栈寄存器个数；竖轴表示时钟周期数.从图上我们看到RSE 开销随寄存器栈溢出/载入寄存器的数量增加而线性增加.这与栈寄存器整个帧溢出的情况并不完全符合.每个栈寄存器溢出/载入引起的RSE 代价大约是1个时钟周期，
除了从溢出56个到溢出57个栈寄存器时有一个较大的RSE 开销增加.假设S latency 为启动时间，z i 是过程p i 被调用时需要溢出的栈寄存器个数，diff 是根据实验测量得到的一个栈寄存器溢出花费的时间开销，那么我们可以用以下公式来计算RSE 开销：
Dynamic-RSE-cycles =z i >diff +S latency （1
）
图2RSE 开销和溢出的栈寄存器数量之间的关系
!."实例分析
通常的过程内寄存器分配会分给每个过程它所
需要的最大栈寄存器数量而不考虑RSE 开销.因为
过程内寄存器分配看不到调用路径上其他过程的栈寄存器使用情况，所以它很难确定一个过程使用多少栈寄存器不会导致寄存器栈溢出/载入.
如果在进行寄存器分配时能够知道调用路径上其他过程的栈寄存器使用数量，就可以知道使用多少栈寄存器会导致寄存器栈溢出/载入.因此，我们想到使用调用图来帮助寄存器分配.这里给出一个简单的例子来说明它是如何工作的.假设编译的目标机器是Itanium 处理器，总共有96个栈寄存器.例子程序和它的调用图如图3所示.
过程旁的指令是对该过程进行过程内寄存器分配时的栈帧分配指令.在这个例子中，每两个过程间调用边的频率是相等的.从4.1节的实验我们知道多溢出一个栈寄存器，RSE 开销就会增加大约1个时钟周期.图3中，过程B ，C ，D 每次被调用时分别会溢出14，50，60个栈寄存器，
根据公式（1），总的RSE 开销为12400个时钟周期.假设除去RSE 开销，
程序运行时的访存开销是t spill-cost ，那么总的访存开销是t spill-cost +12400
.
图3例子和调用图
由前述可知，如果调用路径上使用的栈寄存器数量不超过96，就不会发生寄存器栈溢出/载入，从而没有RSE 开销.因此，为了消除程序的RSE 开销，容易得到一种简单的算法：
算法#.从调用图的根节点开始，按照图中的
调用路径进行栈寄存器分配，到用完96个栈寄存器
时停止.
对图3的程序应用算法1，过程A 被分配到60个栈寄存器，过程B 得到36个栈寄存器.这样，96个栈寄存器都被用完，过程C 和D 不能得到栈寄存器.相比于过程内寄存器分配，过程B ，C 和D 分别少使用了14，50和60个栈寄存器.算法1消除了所有的RSE 开销，但是减少栈寄存器的使用必然会导致更多活跃区间被溢出，从而导致访存开销的增加.为了知道算法1是否能够减少总的访存开销，从而提高性能，我们需要知道少使用一个栈寄存器，会增加多少访存操作时钟周期数.反过来说，就是多使用一个栈寄存器，可以减少多少访存开销.
栈溢出一个寄存器就会导致相同的RSE 开销，但是多用一个栈寄存器会减少的访存开销通常是不一样的.这是因为使用该寄存器的活跃区间各不相同，从而使用该栈寄存器可以减少的访存代价也不一样.为了讨论简单起见，我们假设对于某个特定的过程，多用一个栈寄存器减少的访存开销是一样的.图4给出了4个过程中使用的栈寄存器数量和减少的load /store 操作时钟周期数之间的关系.图上横轴表示过程里使用的栈寄存器个数，竖轴表示由此减少的load /store 操作时钟周期数.在过程A ，B ，C ，D 中，每多使用一个栈寄存器分别可以减少200，50，80
4
和400个Ioad/store操作时钟周期.
有了以上信息，我们就可以计算对程序应用算法1后的性能变化.因为过程B，C，D分别少使用了14，50和60个栈寄存器，因此会增加总共28700个时钟周期的访存操作，从而总的访存开销为t
spiII-cost
+ 28700-12400=t spiII-cost+16300.相比于最初的总访存开销，性能反而下降了.
很显然，这不是所希望的结果.我们的目标是减少总的访存开销，从而提高程序性能.一个栈寄存器的使用是否对性能有提高取决于使用它能够减少总的访存开销，即使用它可以减少的访存操作时钟周期
数是否大于它会引起的RSE开销.结合调用图和图4提供的信息，算法1可以被改进如下：如果一个栈寄存器的使用会引起寄存器栈溢出/载入，但是使用它可以减少的访存操作时钟周期数大于RSE开销，则使用该寄存器.程序应用新的算法，过程A，B，C和D将各使用60，36，0，60个栈寄存器.这样，只有过程D被调用时会引起60个栈寄存器溢出，从而总的RSE代价为6000；因为过程B和过程C分别少使用了14和50个栈寄存器，访存操作增加了4700个时钟周期.总的访存开销为t
spiII-cost
+10700个时钟周期，少于在过程内寄存器分配时的RSE代价
.
图4过程使用的栈寄存器数和由此减少的Ioad/store操作时钟周期数之间的关系进一步观察程序，可以发现过程B中每个栈寄存
器的使用只能减少50个时钟周期，而过程D使用一
个栈寄存器却可以减少400个时钟周期，但是过程B
优先使用没有寄存器栈溢出/载入代价的栈寄存器.
很明显，这样不是最好的情况.如果我们优先把栈寄
存器分给过程D，性能可以进一步得到提高.对所有
过程使用的栈寄存器r
i!j
按照reduced-cycIes（r
i!j
）进
行排序，这里r
i!j
表示在过程p
i
中使用的第j个栈寄
存器，得到如下序列：
r
d1
r
d2
…
r
d60
r
a1
r
a2
…r
a60
r
c1
r
c2
…r
c50
r
B1
r
B2
…r
B50
.
序列中前96个栈寄存器的使用是没有代价的；
顺序在96以后的栈寄存器r
i!j
仍然按照算法2中
的方法确定是否可以使用.这样，4个过程A，B，C，D
各分配到60，0，0，60个栈寄存器.RSE开销为2400
个时钟周期，而B和C因为相比于过程内寄存器分
配时各少用了50个栈寄存器而增加了6500个时钟
周期的Ioad/store操作.总访存代价为t
memory-access
+
8900个时钟周期，性能比应用算法1时有了更多提高.
在上边的讨论中，热点中调用边的频率都是相
同的，因此，计算多用一个栈寄存器增加的RSE开
销比较简单.但是在实际的应用程序里，调用边的频
率通常是不同的.这里（图5）我们把过程B和过程C
之间调用边的频率改为1.
研究在哪些过程被调用时导致了大部分RSE
开销容易发现，主要的RSE开销产生于两个热点：A
"B和C"D，而B"C仅仅导致了50个时钟周期的
RSE开销.如果对热点A"B和C"D分别应用算法
2，那么增加的Ioad/store操作时钟周期和RSE代价
总共是1916个时钟周期.相比于过程内寄存器分配
的结果，性能明显提高了.下边我们来解释为什么分
别对A"B和C"D应用算法2已经近似最大限度
地减少了总访存开销.由以上讨论可以看到，调用频
率较低的边只会导致很少的RSE开销，如果选择出
调用频率高的热点并对它们应用算法2，可以近似
5
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议