（计算机系统结构专业论文）相连多寄存器组体系结构上的寄存器分配技术.pdf

i t i i i 多寄打嚣毋i i f , 彖结心i r j 肖仃器舒艇址术 摘要 寄存器分配是编译器后端一个十分重要的阶段。寄存器分配的有效性直接影响 着编译器的优化效果和处理器性能的发挥。随着计算机体系结构的发展，为了支持 多核多线程、畀步访存以及减少寄存器件读写瑞口出现了一类相连多寄存器组结 构的处理器在这类处理器上分配好寄存器是对编译器的一大挑战。本文对相连多 寄存器组体系结构上的寄存器分配关键技术进行了研究。本文的主要贡献如下： l ：提出了一种相连多寄存器组结构上的寄存器分配方法传统通用处理器的 寄存器组之问相互独立，各自存放不同类型数据，指令的操作数只能来自 唯一一个寄存器组在这种独立寄存器组结构上只须分别对每个寄存器组 使用目前流行的c h a i t i n 方法即可但在相连寄存器组结构的处理器上。 各寄存器组字长相同并有数据通路相连，能存放相同的数据，指令的操作 数可来自多个寄存器组。出现了需要确定变量的寄存器组属性及解决寄存 器组冲突的新问题，使得c h a i t i n 方法不再直接适用我们通过提出寄存器 组划分图的概念以及对它相应的建立、化简和分裂方法，解决了上述问 题。 2 提出了三种双操作数冲突解决技术。为了减少寄存器堆的读写端口个数， 进而提高寄存器的访问速度，有的处理器要求所有二元操作指令的两个源 操作数必须来自不同的寄存器组。随之出现的新问题是，我们既要为变量 指派寄存器组，又要为其分配寄存器，两者之间互相影响我们提出了冲 突图概念，并把这种双操作数冲突约束下的寄存器分配问题分解为二个子 问题：组指派子问题和寄存器分配子问题前者通过对冲突图2 着色解 决，后者通过对干涉图k 着色解决。根据解决这二个子问题的次序，提出 了三种方法：先于寄存器分配的组指派、后于寄存器分配的组指派，结合 式寄存器分配与组指派。 3 提出了一种复写合并与活跃区域分裂相结合的寄存器分配方法。c h a i t i n 方 法的一个缺陷是溢出一个活跃区域时会全程溢出，代价较大。我们的方法 是事先把活跃区域分裂成多个碎片，然后依赖复写合并激进地合并碎片 如果合并后的活跃区域出现分配失败，就按原来的裂痕进行反合并由此 我们获得了一种在溢出全部活跃区域、溢出部分活跃区域、用拷贝指令换 取溢出之问做出更好选择的能力。 4 为开放源码编泽器o r c 增添了新的基础设施。o r c 被国内外多所著名大 学和研究机构采用。做为其研究平台。我们在o r c 中实现了多种图着色寄 存器分配方法以及o r c 后端的s s a 表示。例如c h a i t i n 方法、b r i g g s 乐观 式着色方法、g e o r g e 迭代式合并方法和我们提出的新方法。与o r c 原有 方法相比，我们在2 5 3 p e d b m k 、1 8 6 c r a f t y 上分别取得了3 4 和1 3 3 的 性能加速比。图着色寄存器分配和s s a 表示是编译研究中二个霞要的基础 设施，我们的实现为o r c 、严台添加r 新的资源。 上【自i 提到的前i l l i 点在o r c i x p 编洋器巾实现，第三点在o r c 龙芯m i p s 编译 器巾实现。 关键词：寄存器分配，翻着色，相连多寄存器组，盟q 合j f 。活跃ix _ 域分裂 摘耍 r e g i s t e ra l l o c a t i o nf o rm a c h i n e sw i t hc o n n e c t e da n dp a r t i t i o n e d r e g i s t e rb a n k s z h a n gj u n c h a o ( c o m p u t e ra r c h i t e c t u r e ) d i r c c t e db yp r o f e s s o rz h a n gz h a o q l n g r e g i s t e ra l l o c a t i o n ( r a ) i sam a j o rp h a s ei nt h ec o m p i l e rb a c k e n d ，w h i c hh a sd e e p e f f e c to nt h eo p t i m i z a t i o nr e s u l t so fo t h e rp h a s e si nt h eb a c k e n da n dh e n c et h e p e r f o r m a n c eo fp r o c e s s o r s t os u p p o r tm u l t i c o r e , m u l t i t h r e a d a s y n c h r o n o u si oa n dt o r e d u c et h ep o f tn u m b e ro fr e g i s t e rf i l e s ，$ o m ep r o c e s s o r sa r ee q u i p p e dw i t hc o n n e c t e d a n dp a r t i t i o n e dr e g i s t e rb a n k s r e g i s t e ra l l o c a t i o no nt h i sk i n do fp r o c e s s o r si sab i g c h a l l e n g ef o rc o m p i l e r s w eh a v es t u d i e dt h er e g i s t e ra l l o c a t i o np r o b l e m so nt h i sk i n do f p r o c e s s o r s t h ew o r kd e s c r i b e di nt h i st h e s i sh a sf o l l o w i n gc o n t r i b u t i o n s ： 1 p r o p o s ear e g i s t e ra l l o c a t i o nf r a m e w o r kf o rm a c h i n e sw i t hc o n n e c t e da n dp a r t i t i o n e d r e g i s t e rb a n k s d i f f e r e n tr e g i s t e rb a n k s “l a s s e s ) a r cc r e a t e di nt h ea a d i t i o n a lg e n e r a l p u r p o s ec p u sf o rd i f f e r e n td a t at y p e s t h e ya r cm a i n l yi n d e p e n d e n ts u c ht h a t o p e r a n d so fac e r t a i ni n s t r u c t i o nc a no n l yc o m ef r o mo n er e g i s t e r b a n k t h e r e f o r e 。 w ec a l la p p l yc h a i t i n sa p p r o a c ht oe a c hr e g i s t e rb a n ki n d e p e n d e n t l y b u tf o rt h o s e p r o c e s s o r sw i t hc o n n e c t e da n dp a r t i t i o n e dr e g i s t e rb a n k s e a c hb a n ki si nt h es a m e w o r d - l e n g t ha n dc a nh o l dt h es a m ev a l u e i ns u c hw a y 。o p e r a n d so fa ni n s t r u c t i o n c a nb ep l a c e di nm u l t i p l er e g i s t e rb a n k s t h e n t h e r ec o m en e w p r o b l e m sf o rr e g i s t e r a l l o c a t i o n , t h a ti s 。w eh a v et oi d e n t i 知t h er e g i s t e rb a n ka t t r i b u t e sf o rv a r i a b l e sa n d r e s o l v et h ep o t e n t i a lc o n f l i c t sb e t w e e nr e g i s t e rb a n k s 。w h i c hm a k e sc h a i t i n s a p p r o a c hc a nn o tb ea p p l i e dd i r e c t l y i nt h i st h e s i s t h ec o n c e p to fr e g i s t e rb a n k p a r t i t i o ng r a p hi si n t r o d u c e d t h e nw es h o wh o wt o a t t a c kt h e s ep r o b l e m sb y b u i l d i n g ，s i m p l i f ya n ds p l i tt h eg r a p h 2 p r o p o s et h r e ea p p r o a c h e st os o l v i n gt h et w os o u r c eo p e r a n dc o n f l i c tp r o b l e m w e k n o wt h a tt h ea c c e s ss p e e do far e g i s t e rf i l e i si n v e r s e l yp r o p o r t i o n a lt oi t sp o r t n u m b e r t oi m p r o v et h es p e e do far e g i s t e rf i l e ，s o m ep r o c e s s o r sd e m a n dt h a tt h e t w os o u r c eo p e r a n d so f i t si n s t r u c t i o nr e s i d ei nd i f f e r e n tr e g i s t e rb a n k s w h i c hi nt u r n r e q u i r e st h er e g i s t e ra l l o c a t o rt ob o t ha s s i g nr e g i s t e rb a n k sa n da l l o c a t er e g i s t e r s a c c o r d i n g l yt ov a r i a b l e s w ei n t r o d u c et h ec o n c e p to fc o n f l i c tg r a p ha n dd i v i d et h e r e g i s t e ra l l o c a t i o np r o b l e mu n d e rs u c ht w o - s o u r c e - o p e r a n dc o n s t r a i n t si n t ot w os u b p r o b l e m s ：t h eb a n ka s s i g n m e n ts u b p r o b l e ma n dt h er e g i s t e ra l l o c a t i o ns u b p r o b l e m t h ef o r m e ri sa u a c k e db y2 - c o l o r i n gt h ec o n f l i c tg r a p ha n dt h el a r e ri sa t t a c k e db y k - c o l o r i n gt h ei n t e r f e r e n c eg r a p h a c c o r d i n gt ot h ep h a s eo r d e r i n go fs o l v i n gt h e s e t w os u b p r o b l e m s ，t h r e ea p p r o a c h e sa r ep r o p o s e d ：p r e - r ab a n ka s s i g n m e n t p o s t r a b a n ka s s i g n m e n ta n dc o m b i n e d r ab a n ka s s i g n m e n t 3 p r o p o s ear e g i s t e ra l l o c a t i o nf r a m e w o r kw i t ha g g r e s s i v el i v er a n g es p l i t t i n ga n d o p t i m i s t i cc o a l e s c i n g ad r a w b a c ko fc h a i t i n sa p p r o a c hi st h a t i tw i l ls p i l lal i v e r a n g et o t a l l yw h e ni t i ss p i l l e d o u ri d e ai st os p l i tl i v er a n g e sa g g r e s s i v e l yb e f o r e a l l o c a t i o n d u r i n ga l l o c a t i o n 。w eo p t i m i s t i c a l l ya n da g g r e s s i v e l yc o a l e s c et h es p l i r e d l i v er a n g e s i fa na g g r e g a t el i v er a n g ew i l lb es p i l l e d ，w et r yt or e s p l i ta tt h ec r a c k s a n dc o l o re a c hs p l i ti n d e p e n d e n t l y i ns u c hw a y ，w eg a i nt h eo p t i o nt os p i l lal i v e r a n g et o t a l l y ，p a r t i a l l yo ra v o i ds p i l lb yu s i n gc o p yi n s t r u c t i o n s i i i 迫多盘彳，器珂l 体彖扎构i 的搿仃嚣分札 上术 4 a d dn e wc o n t r i b u t i o n st ot h er e p o s i t o r yo ft h eo p e nr e s e a r c hc o m p i l e rf o r c ) 0 r ch a sb e e na d o p t e db ym a n yu n i v e r s i t i e sa n di n s t i t u t e sa st h e i rr e s e a r c hp l a t f o r n l w eh a v ei m p l e m e n t e dal o to f g r a p h c o l o r i n gb a s e dr e g i s t e ra l l o c a t o r si n0 r c s u c h a sc h a i t i n sa l l o c a t o r , b r i g g s so p t i m i s t i ca l l o c a t o r , g e o r g e si t e r a t i v ea l l o c a t o ra n d o u rf l e wa l l o c a t o r s d u 6 n gt h ep r o c e s s 。w ea l s oi m p l e m e n t e dt h es s a 岛册i n0 r c s b a c k e n d c o m p a r i n gw i t ht h eo r i g i n a la l l o c a t o ri no r c ，o u ra l l o c a t o rg o t3 4 a n d 1 3 3 s p e e d u pf o r2 5 3 p e r l b m ka n di8 6 c r a f i yr e s p e c t i v e l y n eg r a p hc o l o r i n g b a s e dr e g i s t e ra l l o c a t i o na n ds s af o r ma r et w oi m p o r t a n tf i e l d si nc o m p i l e rr e s e a r c h 0 l i ti m p l e m e n t a t i o na d d sn e wc o n t r i b u t i o n st oo r c sr e p o s i t o r y t h ef i r s ta n dt h es e c o n dp r o p o s a l sw e r ei m p l e m e n t e di nt h eo r c i x p c o m p i l e r t h e t h i r dw a si m p l e m e n t e di nt h eo r c g o d s o n 2c o m p i l e r k e y w o r d s ：r e g i s t e ra l l o c a t i o n ，g r a p hc o l o r i n g ，c o n n e c t e da n dp a r t i t i o n e dr e g i s t e rb a n k s ， c o a l e s c e ，l i v er a n g es p l i t v 柑i 多寄行嚣组i 体系结构i 的寄打器分魁技术 图目录 图1 1o r c 前端、中端和后端划分图3 图1 2o r c 代码生成器：4 图2 ic h a i t i n 式寄存器分配。1 0 图2 2 重命名l1 图2 3 复写合并后干涉图的保守更新1 4 图2 4 一个图着色例子- 3 ) 1 7 图2 5b r i g g s 乐观式寄存器分配1 8 图3 1n 6 4 手册对加法指令的说明。2 2 图3 2i a 6 4 加法指令编码格式。2 2 图3 3i n t e li x p 2 8 0 0 功能单元框图2 5 图3 4i x p 2 8 0 0m i e r o e n g i n e 结构图2 6 图3 5o r c 中临时名t n 的定义2 9 图3 6 在确定组属性之前删除冗余指令3 0 图3 7l 3 s w i t c h 中的一个例子3 2 图3 8 寄存器组划分图的构建、化简与活跃区域分裂3 5 图3 9 解决寄存器组冲突后的中间表示3 7 图3 1 0 同一寄存器组划分图的另一种化简方法3 8 图3 1 i 基于i l p 的寄存器分配4 2 图4 i 一个有两个奇数回路的冲突图4 5 图4 2 存在预着色节点的冲突图4 6 图4 3 一个先于寄存器分配的组指派的例子4 9 图4 4 溢出代码的优化5 0 图4 5p r e r a 导致寄存器压力不平衡。5 l 图4 6 g p r 到g p r a 和g p r b 的多对一映射5 3 图4 7 寄存器分配成功但映射失败5 5 图4 8c o m b i n e d r a 的例子6 0 图5 1 节点合并导致溢出( k = 2 ) 。6 1 图5 2 。节点合并推动化简进程( k = 3 ) 6 2 图5 3 一个激进式合并但不溢出的例子( k = 3 ) 6 3 图5 4g e o r g e 迭代式化简- 合并寄存器分配6 3 图5 5 乐观式合并一6 4 图5 6 基于基本块的活跃区域分裂6 6 图5 7 基于循环的活跃区域分裂6 7 图5 8 基于s s a 的活跃区域分裂。6 8 图5 9 分裂与溢出代价6 8 图5 1 0 分裂与冗余s t o r e 6 9 图5 1 l 活跃区域分裂与复写合并相结合的寄存器分配7 0 图5 1 2 合并时溢出代价的调整。7 l c i l i 康 图6 1s h a n g r i l a 网络程序编程环境结构图7 4 图6 2m e 上的代码生成器。7 6 图6 3s h a n g r i l a i x p 测试环境7 9 图6 4c h o w 、b r i g g s g e o r g e 相对c h a i t i n 方法的c p u 2 0 0 0i n t 加速比。8 6 图6 5c h o w 、b r i g g s 和g e o r g e 相对c h a i t i n 方法的c p u 2 0 0 0f p 加速比8 7 图6 6 s s a - s p l i t ，l o o p - s p l i t 相对g e o r g e 方法的c p u 2 0 0 0 i n t 加速比。9 0 图7 1o r cc g i r 中的基本块9 3 图7 2o r cc g i r 中的指令9 4 图7 3 0 r c c g i r 中的操作致9 4 图7 4 计算深度优先序9 5 图7 5 控制流图及其深度优先序9 5 图7 6s s a 形式示例9 6 图7 7 图7 8 图7 9 图，i 图7 1 图7 1 图7 1 图7 1 图7 1 图7 1 6 计算溢出代价 图7 1 7 着色 1 0 6 1 0 7 舸i j j = 多奇打器甜l 体系结构j 的寄玎器分秕技术 表3 1l m e l i a 6 4 寄存器组划分 表3 2i x p 2 8 0 0m i c r o e n g i n e 寄存器组 表6 im e a b i 表目录 表6 2 几个用b a k e r 编写的网络程序 2 7 7 7 表6 3p r e - r a 、p o s t - r a 和c o m b i n e d r a 分配代价细表 表6 4c p u 2 0 0 0i n t 测试程序 7 8 8 l ；：i 表6 5c p u 2 0 0 0f p 测试程序8 3 表6 6 六种寄存器分配算法8 4 表6 7c h a i t i n 、c h o w 、b r i g g s 和g e o r g e 方法的c p u 2 0 0 0i n t 运行结果8 6 表6 8c h a i t i n 、c h o w 、b r i g g s 和g e o r g e 方法的c p u 2 0 0 0f p 运行结果8 7 表6 9c h a i t i n 、b r i g g s 和g e o r g e 方法在c p u 2 0 0 0i n t 上的分配代价细表8 8 表6 1 0g e o r g e 、s s a - s p l i t 、l o o p - s p l i t 方法的c p u 2 0 0 0r n t 运_ 行结果9 0 表6 1 1s s a s p l i t l o o p s p i t 方法在c p u 2 0 0 0i p 叮上的分配情况9 1 x 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及 取得的研究成果。就我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工 作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表 示了谢意。 作者签名：弘辱蔓互 日期：二矿莎莎，孑 关于论文使用授权的说明 中国科学院计算技术研究所有权处理、保留送交论文的复印件，允 许论文被查阅和借阅；并可以公布论文的全部或部分内容，可以采用 影印、缩印或其它复制手段保存该论文。 作者签名：乒臣髯恕导师签名：j ，丕彩么日期：知西孑 第节哼i 。j 1 1 编译器与计算机体系结构 第一章引言 编译器的传统任务是将程序员容易理解的高级语言源程序翻译成目标机器上可 执行的机器代码，以免去程序员用汇编语言书写程序的繁重负担但在编译器发展 的早期人们就已经认识到，编译器更重要的任务是在产生正确的目标代码之外，还 必须保证目标代码的性能如果编译器产生的代码还不及程序员手工编写代码的一 半那么这种语言很可能就会被抛弃，这种机器的可用性也会变得很差 随着计算机性能的提升，计算机体系结构交得日趋复杂，编译器的地位也变得 更加重要。体系结构的每项革新，都离不开编译器的支持只有编译器充分利用体 系结构的特点，实施各种各样的优化技术，生成高质量的目标代码，体系结构的设 计优势才能发挥出来。比如现代微处理器常采用的超标量流水线结构，就需要编译 器通过指令调度、循环展开、软流水等技术去充分利用它提供的指令级并行性。为 充分利用处理器存储层次带来的快速局部性访问优势，编译器可以通过循环变换、 数据预取、代码重排、数据重排等提高指令或数据的局部性。在l o a d s t o r e 结构的 机器上，除了访存指令外，其它指令的操作数必须都在寄存器当中，这就要求有高 效的寄存器分配器。以i n t e li a 6 4 为代表的显式并行体系结构，更是将挖掘指令级 并行的任务很大程度上交给了编译器i a 6 4 需要编译器显式生成可并行执行的指 令束i a 6 4 提供的谓词操作、控制投机和数据投机等特性需要编译器去进行i f 转 换、投机指令调度、投机恢复代码生成等最近成为体系结构研究新热点的可重构 计算，多线程技术，多核技术也分别需要编译器去进行处理器底层结构的重构，程 序的线程划分和并行性化。 编译器不但对通用处理器来说至关重要，对传统的以汇编编程为主的嵌入式处 理器它也日益显示出了价值。一方面嵌入式应用变得复杂，程序规模变大，用汇编 编程开发效率低下另一方面产品的升级换代加速，汇编程序不易移植，不能保护 投资如果一个新产品不能快速占领市场，它将很快被淘汰 可以说，编译器是应用程序与计算机系统之间的桥梁。在追求高性能的过程 中，应当从最终需求出发，编译器和体系结构合理分工，协同设计，最终提供给用 户一个既容易编程又具有很高性能的系统。 1 2 编译器的结构 一般，一个优化编译器可分为三部分： 前端( f r o n t e n d ) ：前端负责把源程序翻译成一种中间表示( i n t e r m e d i a t e r e p r e s e n t a t i o n ，i r ) 。由于源语言结构的差异，前端可能一次或多次扫描代码。这 种翻译主要包括w 法分析，语法分析和语义制导翻译等步骤。编泽时刻错误枪查通 常在这一阶段进行。一个编译器通常支持多种语言如f o r t r a n 、c 、c h 等， 所以它就有多个前端。理想情况下，前端仅与源语言相关而与目标机器无天。 耵i 连多奇仃器纽体系结佝i ：的寄彳，器分雕技术 中端( m i d d l ee n d ) ：巾端由一系列优化器组成。每个优化器对巾问表示做特定 类型的转换( 或叫做优化) 每种优化都要在不丧失正确性的前提下尽量提高最终代 码的质量，如果能做到最优则更好理想情况下，中端应做到与源语言和目标机器 均无关。这类优化可分为全局优化和过程间优化。全局优化指在一个函数( 过程) 的 范围内进行的优化，如强度削弱循环不变量外提、常数传搔，公共子表达式册4 除 等过程间优化指跨越函数边界从多个函数中提取信息所做的优化，如死代码删 除、i n l i n i n g 、把问接函数调用变为直接函数调用等 后端( b a c k e n d ) ：后端负责把中间表示翻译成与特定机器相对的目标代码我们 也把它称作疗屑兰应发c 0 d eg e n e r a t i o n 。c c ) 通常包括这样几步：指令选择、指令 调度、寄存器分配和代码发射后端与源语言无关而与目标机器有关 这种方法把不同类型的问题有效的划分开来简化了每部分的开发与维护，更 重要的是提高了代码的可重用性例如象上面提到的，多个前端可以共享同一个中 端和后端 1 3o r c 编译器 我们的工作基于o r c ( o p e nr e s e a r c hc o m p i l e r ) 编译器1 ，在此对o r c 结构做一 简单介绍o r c 是中国科学院计算技术研究所与i n t e l 公司合作开发的一个面向 i n t e li a 6 4 l i n u x 平台的开放源码研究型编译器。除i a 6 4 平台外，我们还把o r c 移 植到了i n t e li x p 网络处理器( o r c i x p ) 和龙芯m i p s 通用处理器上。目前o r c 在 i a 6 4 l i n u x 已经发布了四个版本它的前身是s g i 公司的开放源码编译器p r 0 6 4 2 p r 0 6 4 是s g i 从它的产品编译器m i p s p r o 移植来的 图1 1 是o r c 前端、中端和后端划分图o r c 前端支持四种编程语言：c 、 c + + 、f o r t r a n 7 7 和f o r t r a n 9 0 。o r c 的中间表示称为w h i r l v & i i r l 是一种抽象 语法树。为了能让各种编译优化在最适合的中间表示上进行，w h i r l 采取了层次 结构，从最高层w h i r l 到最低层w h i r l ，共分为五层每层在语义上相同，但 每降低一层，就要丢失一些源程序的信息。相邻层之间的转换通过调用各种 l o w e r e r 来完成，这些i o w e r e r 列在图的右边，在此不做介绍图左列出了在各层 w h i r l 上所做的优化，主要包含过程间分析与优化( i n t e r - p r o c e d u r ea n a l y s i s & o p t i m i z a t i o n ，i p a i p o ) 、循环优化( l o o pn e s t e do p t i m i z a t i o n , l n o ) 以及标量全局优 化( s c a l a rg l o b a lo p t i m i z a t i o n ，w o p t ) 。i p a i p o 分信息收集，分析和优化三阶段。 收集的信息包括各调用点的形参和实参、变量被更改和引用的次数、调用点频率， 变量是否被取地址等。所做的分析包括死函数分析、数组填充和分割分析、全局符 号的属性分析、i n l i n i n g 的代价分析等。所做的优化包括死函数和死变量删除、 i n l i n i n g 、常数传播等l n o 土要包括针对循环的局部性优化、并行、循环分布、 幺模变换、数组私有化、o p e n m p 支持等。w o p t 先将w h i r l 转换为静态单赋值 ( s t a t i cs i n g l ea s s i g n m e n t ，s s a ) 形式，然后在s s a 之上实现了所有了传统全局优化 技术，例如部分冗余消除、归约变量识别、强度削弱、l o a d s t o r e 的部分冗余消除 和复巧传橘等。 ：h t t p h i p g o r cs o u r c e f o r g en e t h t l p p r 0 6 4s o u r c e f o r g e n e t 瓤节哼j v h o s t a n d a l o n ej n h n e r i p a i p o p r e o p t l n o w o p t r v l l r v | 2 c g c g | h i g h w h i r l l l o ww h i r l l v e r y l o w w h i r l l c g i r l o w e ra g g r e g a t e s u n n e s ic a l l s l o w e rc o m m a s r c o m m a s l o w e ra r r a y s l o w e rc o m p l e xn u m b e r s l o w e rh = g hi e v e ic o n t r o if i o w l o w e r l 0 l o w e rb = t f i e l d s s p a w nn e s t e dp r o c e d u r e sf o r p a r a l l e lr e g z o n s l o w e ri n t r l n s i c st oc a l l s g e n e r a t es i m u l a t i o nc o d ef o rq u a d s a d a t am a p p e dt os e g m e n t s l o w e rl o a d s ，s t o r e st of i n a lf o r m e x p o s ec o d es f 明u e n c e sf o r c o n s t a n t sa n da d d r e s s e s e x p o s es g pf o r s h a r e d e x p o s es t a t i cl i n kf o rn e s t e d p r o c e d u r e s 图1 10 r c 前端，中端和后端划分图 图1 2 是o r c 后端，也就是代码生成c g 的结构图。c g 部分的中间表示称为 c g i r 。一开始，c g 通过搿舍迸撵把最低层的w h i r l 转换为c g i r 然后是控制 流和变量值的p r o f i l i n g 。随之是区域生成，i f 转换，并行c m p 指令生成，循环优化 ( 软流水和循环展开) ，全局指令调度，寄存器分配，局部指令调度和代码发射 值得指出的是，o r c 的原有的寄存器分配采用了c h o w 的基于优先级的图着 色方法【2 6 】，分全局寄存器分配( g l o b a lr e g i s t e ra l l o c a t i o n ，g r a ) 和局部寄存器分配 ( l o c a lr e g i s t e ra l l o c a t i o n , l r a ) z 部分g r a 负责为跨越基本块边界的活跃区域分 配寄存器，而l i t a 只负责为基本块内部的活跃区域分配寄存器。我们的研究工作 并没有采用此方法，而是全新实现了基于c h a i t i n b f i g g s 的图着色寄存器分配算 法，代替了原有的g r a l r a ，以满足相连多寄存器组体系结构对寄存器分配的特 殊需求。 工+i警lii十t 耵i 适多寄打嚣卵i 体乐结 句jf r j 寄打器分眦技术 1 4 寄存器分配与优化 + l e d g e i v a l u e p r o f i l i n g 工 l r e g i o nf o r m a t i o n 上 i i n v e r s i o nll m m l i c lc m pg e n e r a t l 。n 工 l l p 。p t i l l l i z a t i o n ( s ”“u m “g ) 上 i g l o b a l i n s t r u c t , o ns c h e d u l m g ( p r c d i c a k ia n a l y s i s ，s v e c u l m i o n 1 l o u l f c em a n a g e m e m ) l g l o b a lr e g i s t e ra l l o c a t i o n ( g r a ) il o c a lr e 日, i s t e ra l l o c a t i o n ( l r a i l o c a li n s t r u c t i o ns c h e d u l i n g i c o d ee m i t l o n 图1 2 0 r c 代码生成器 寄存器分配在编译器中的位置一般比较靠后，正如o r c 编译器中寄存器分配 的位置一样，通常它在全局指令调度之后进行一是因为各类优化都已经做过， 它们可以假设有无数多个寄存器可用。二是因为寄存器分配过后，将出现大量的写 后写( w a w ) 、读后写( w a r ) 依赖，若把指令调度放在寄存器分配之后将使指令 调度受到很大约束。一般在寄存器分配过后还会进行一次基本块内的局部指令调 度因为寄存器分配可能会插入溢出代码，为了更好的性能，指令调度需要在局部 重排一下指令 作为存储层次金字塔中的最高一层，寄存器毫不例外地也遵循这样一条规律： 存储容量与访问速度成反相关。寄存器与主存比起来有如下特点。 寄存器个数很少( 比如在常见的r i s c 处理器上整型寄存器就只有3 2 个) ， 可以用少数几个比特位给它们编址；相反主存容量却可以很大通常要通 过某种寻址模式间接指定一个主存地址。 寄存器的速度很快，对寄存器的访问通常可在一个时钟周期内完成而对 主存的访问却得多个时钟周期。 极快的访廿j 速度和有限的容鼍使得寄存器成为处理器当中的一种珍贵资源。 寄存器有多种用途。最简单的情况，机器指令的操作数必须存放在寄存器当中。再 进一步。在表达式计算过程中产生的中问结果，也应当放在寄存器当中。如果再激 进一点。最好把经常访问的变量也存放在寄存器当中，以避免重复的l o a d s t o r e 。 对一个优化编洋器来说，最理想的是把经过公芡f 表式删除或循环不变譬外移而提 4 第争引二 出来的变量存放在寄存器当巾。在对下标表达式优化的研究过程巾，人们逐渐发现 了一条重要的编译技术设计方法：设i t - h 优化技术时，可以先假设订无数多个寄 存器可用，而把寄存器分配当傲一个分开的问题来处理【2 7 】。这样在设计时，就不 用考虑诸多由于资源限制而带来的约束，设计起来就相对简单了很多如果实际中 寄存器真的够用，这种分开处理的方法就很理想。但是如果寄存器不够用，这种优 化技术的效果就会降低甚至还使代码质量恶化。 寄存器分配可以在不