已阅读5页,还剩104页未读, 继续免费阅读
(计算机系统结构专业论文)基于区域的编译技术和栈寄存器优化.pdf.pdf 免费下载
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
基于区域的编译技术和栈寄存器优化:摘要 摘要 为了提高指令级并行,编译器必须进行大量的优化。而复杂的编译优化算法 需要耗费大量的编译时间和资源。为了减少编译的时间,并且给研究者提供一个 灵活的研究平台,同时保证编译性能不受损害,本文提出了一种灵活的区域构造 框架。在研究过程中,我们发现r s e ( r e g i s t e rs t a c ke n g i n e ) 开销在某些程序的运 行过程中占有很大的比例,针对这个问题,提出了一种能够有效减少r s e 开销 提高代码性能的方法。 文章的主要贡献有如下几点: 1 提出了一个新的区域构造框架,作为编译器各优化阶段的统一编译单位。 这个区域构造框架是分层次的,其形状和大小可以根据优化阶段的需要灵活控 制。控制流图中的所有基本块都至少被一个区域所包含。区域之间是以树状的关 系组织在一起。 2 提出了一个可以参数化设定最大尾复制比率和最小出口概率限制的单入 口多出口区域构造算法。实验表明该算法构造的区域对于适应不同的优化阶段以 提供足够多的优化机会是非常有效的。 3 提出了区域属性的概念。区域的属性可以在编译器不同的优化阶段被设 定,观察,维护和清除。这些属性对于维护区域前后优化阶段的效果是非常重要 的。 4 提出了一个r s e 开销的代价模型;基于这个代价模型,提出了过程间栈 寄存器配额分配问题。 5 基于前述的量化代价模型,给出了一个过程间栈寄存器分配算法。该算法 可以有效地减少总的内存访问开销,从而提高程序的执行性能。 6 提出了一种可重计值活跃区间的优化寄存器分配方法。对于某些可重计值 的活跃区间,由于它的定义点的总执行频率大于它的引用点的总执行频率,则它 没有被分配到寄存器时,溢出处理会从这些定义点移动到引用点的基本块里去执 行,减少了实际执行时的代码执行时间。 7 上述算法均在o r c 编译器中实现,并利用s p e c 2 0 0 0 i n t 程序对提出的算 法进行了测试,对比了基于区域的编译和基于函数的编译时不同的优化效果。实 验结果表明,区域的构造大大地减少了程序的编译时间,同时提高了程序的执行 性能。过程问的寄存器分配算法对于r s e 开销比较大的程序,性能的提高非常 显著。而对于一些r s e 开销不是很明显的程序,性能并没有明显的变化,或者 略微有所提高。对可重计值活跃区间的优化则对p e r l b m k 的性能有明显提高。总 体而言,程序的执行性能有了比较显著的提高。最后,对以上算法的扩展进行了 讨论,提出了可以在未来继续深入研究的问题。 随着处理器执行频率的加快,存储优化问题必将越来越受到研究者的重视, 基于酝域的编译技术和栈寄存嚣优化 可以预期我们的工作对以后的处理器的编译器也有羹要的参考价值a 关键词:区域单入多出区域多入多出区域寄存器栈引擎寄存器栈帧 i l 基于区域的编译技术和栈寄存器优化:摘要 a b s t r a c t l i u y a n g ( c o m p u t e ra r c h i t e c t u r e ) d i r e c t e d b yz h a n gz h a o q i n g i no r d e rt oi m p r o v ei n s t r u c t i o nl e v e lp a r a l l e l i s m ,c o m p i l e r st e n dt oa d o p tm o r e a g g r e s s i v ea n dc o m p l e xo p t i m i z a t i o na l g o r i t h m s b u t t o o c o m p l e xa n da g g r e s s i v e o p t i m i z a t i o na l g o r i t h mw i l l c o s tm u c hc o m p i l a t i o nt i m ea n dr e s o u r c e s i no r d e rt o r e d u c ec o m p i l a t i o nt i m ea n dp r o v i d er e s e a r c h e r saf l e x i b l er e s e a r c hp l a t f o r m ,o nt h e m e a n w h i l e ,p r o v e t h e c o m p i l a t i o np e r f o r m a n c e ,w ep r o p o s e d af l e x i b l e r e g i o n f o r m a t i o ni n f r a s t r u c t u r e i no r d e rt os o l v et h i sp r o b l e mt h a tr s ec o s ti sv e r ys e r i o u s f o rs o m ep r o g r a m s ,w ep r o p o s e dae f f e c t i v ea l g o r i t h mt or e d u c er s ec o s ta n d i m p r o v e o v e r a l le x e c u t i o n p e r f o r m a n c e t h em a i nc o n t r i b u t i o n so f t h e s i sa r e : 1w ep r o p o s ean e wr e g i o nf o r m a t i o ni n f i a s t r u c t u r e t h i sr e g i o nf o r m a t i o n i n f r a s t r u c t u r ei sh i e r a r c h i c a l s i z ea n d s h a p eo f r e g i o n s c o u l db ec o n t r o l l e df l e x i b l yb y s e t t i n gs p e c i f i cp a r a m e t e r s e v e r yb a s i cb l o c ki nt h ec o n t r o lf l o wi sc o n t a i n e db y a t l e a s to n e r e g i o n r e g i o n sa r eo r g a n i z e d i nat r e e 2w e p r o p o s e as i n g l ee n t r ym u l t i p l ee x i t sr e g i o nf o r m a t i o na l g o r i t h mw i t hm a x t a i l d u p l i c a t e r a t i oa n dm i ne x i t p r o b a b i l i t yc o n s t r a i n t s e x p e r i m e n t s s h o wt h i s a l g o r i t h m i s v e r y e f f e c t i v ei n f o r m i n gr e g i o n s w h i c hc o u l d p r o v i d ee n o u g h o p t i m i z a t i o no p p o r t u n i t i e sf o r d i f f e r e n to p t i m i z a t i o n p h a s e s 3w e p r o p o s et h ea t t r i b u t e so fr e g i o n r e g i o na t t r i b u t e sc o u l db es e t o b s e r v e d , m a i n t a i n e da n dd e l e t e da c r o s sd i f f e r e n to p t i m i z a t i o np h a s e s t h e s ea t t r i b u t e sa r ev e r y i m p o r t a n tf o rg u a r a n t e eo f t h eo p t i m i z a t i o ne f f e c t s 4w e p r o p o s ear s e c o s tm o d e l ,a n db a s e do nt h i sc o s tm o d e l ,w ep m p o s e dt h e i n t e r - p r o c e d u r a ls t a c k e dr e g i s t e rq u o t aa s s i g n m e n tp r o b l e m 5w e pr o p o s eain t e r - p r o c e d u r a l st a c k e d r e g i s t e r al l o c a t i o na l g o r i t h m ,a n ditis i m p l e m e n t e d i no r c c o m p i l e r t h i sa l g o r i t h m c o u l dr e d u c et h eo v e r a l l s p i l l t o m e m o r ya c c e s st i m es oa st oi m p r o v et h ep r o g r a me x e c u t i o np e r f o r m a n c e t h i sa l g o r i t h mi sb a s e do nt h ec o s tm o d e lp r o p o s e db yu s 6w ep r o p o s eam e t h o dt od e c i d ew h e t h e ra l l o c a t i n gas t a c k e dr e g i s t e rt o r e m a t e r i a l i z a b l el i v er a n g e s f o rar e m a t e r i a l i z a b l el i v er a n g e s ,i ft h et o t a le x e c u t i o n f r e q u e n c yo f t h eb a s i cb l o c k sw h e r ei ti sd e f i n e di sg r e a t e rt h e nt h et o t a le x e c u t i o n f r e q u e n c yo f t h eb a s i cb l o c k sw h e r ei ti su s e d ,t h e nw en e e dn o ta l l o c a t ear e g i s t e rt o i tb e c a u s es p i l lc o u l dm o v et h o s ed e f i n et ot h eb a s i cb l o c k sw h e r ei ti su s e d ,t h e r e f o r e r e d u c et h ee x e c u t i o nf r e q u e n c yo f l o a d s i i i 基于区域的编译技术和找鹰存器优化 7e x t e n s i o no ft h ea l g o r i t h m sa r ed i s c u s s e d t h ep r o b l e m sc o u l db ef u r t h e r s t u d i e da n di m p l e m e n t e di nt h ef u t u r ei sp o i n t e do u t , 8a l lt h e s e a l g o r i t h m s a l e i m p l e m e n t e d i no r cc o m p i l e ra n dt e s t e d b y s p e c 2 0 0 0 i n t b e n c h m a r k 。w e c o m p a r e t h e c o m p i l a t i o n t i m ea n d c o m p i l a t i o n p e r f o r m a n c eb e t w e e nw i t ha n dw i t h o u tr e g i o nf o r m a t i o n e x p e r i m e n t s s h o wt h a t r e g i o nf o r m a t i o ng r e a t l yr e d u c et h ec o m p i l m i o nt i m ea n di m p r o v et h ep e r f o r m a n c e - i n t e r p r o c e d u r a l s t a c k e d r e g i s t e r m l o c a t i o n i m p r o v e t h e p e r f o r m a n c e o ft h o s e p r o g r a m sw i t ho b v i o u sr s e c o s tb u th a sn o tn e g a t i v ee f f e c tt ot h o s eb e n c h m a r k s w i t h o u to b v i o u sr s ec o s ta n dt h em e t h o dd e c i d ew h e t h e rar e m a t e r i a l i z a b l el i v e r a n g es h o u l db ea l l o c a t e das t a c k e dr e g i s t e ri m p r o v et h ep e r f o r m a n c eo fp e r l b m k g r e a t l y i ng e r n e r a l ,o u ra l g o r i t h m h a s p o s t i v e e f f e c to np r o g r a m p e r f o r m a n c e w i t ht h es p e e d u po fc p u f r e q u e n c y , m e m o r yo p t i m i z a t i o np r o b l e m w i l lb em o r e i m p o r t a n t 。i ti se x p e c t e dt h a t o u rw o r kw i l la l s ob ev e r yi m p o r t a n to nt h ef u t u r e p r o c e s s o r s ,b u tn o to n l y i t a n i u m p r o c e s s o r k e y w o r d s :r e g i o n ,s i n g l ee n t r ym u l t i p l e e x i t sr e g i o n ,m u l t i p l ee n t r i e sm u l t i p l ee x i t s r e g i o n tr e g i s t e r s t a e ke n g i n e tr e g i s t e rs l a c k f r a m e 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作 及取得的研究成果。就我所知,除了文中特别加以标注和致谢的地方 外,论文中不包含其他人已经发表或撰写过的研究成果。与我一同工 作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。 作者签名: 言 f 肠弓 日期:2 。6 3 葺j 国悖可 关于论文使用授权的说明 中国科学院计算技术研究所有权处理、保留送交论文的复印件, 允许论文被查阅和借阅;并可以公布论文的全部或部分内容,可以采 用影印、缩印或其它复制手段保存该论文。 作者签名:盲、f 佰3 导师签名: 仅讹厌日期:勘。评t 倍f 媚 第一章引言 1 1 指令级并行 1 1 1 超长指令字体系结构 第一章引言 在超长指令字体系结构中,每条指令在什么时候,哪个执行部件上执行都是 显式指定的,并且要保证该条指令的执行和处理器上同时执行的其他指令是相对 独立的。在这里我们先澄清一下指令和操作的区别。所谓操作,指的是一个计算 单元。例如,一个加法操作,一个内存加载操作,或者一个分支跳转,这些就是 顺序执行的处理器结构中的一条指令。而一个超长指令字指令( v e r yl o n g i n s t r u c t i o n w o r d ) 就是一个可以同时执行的操作的集合。编译器负责确定哪些操 作可以放到同一条指令中去。这个过程叫做调度。所有打算同时发射的操作被放 置到一个超长指令字指令中。而在同一条指令中操作的顺序确定了每个操作在哪 个功能部件上执行。 较早的超长指令字处理器被称为a t t a c h e da r r a yp r o c e s s o r s 【c h a r l e s w o r t h 8 1 f l o a t i n g p o i n t y s t e m s 7 9 i b m 7 6 】 i n t e l 8 9 a 【r u g g i e r 0 6 9 】,其中最著名的是浮点系 统的产品,例如a p 一1 2 0 b ,f p s 1 6 4 ,f p s 2 6 4 等。下一代的产品是微型超级计 算机:m u l t i f l o wt r a c e 系列机器 c o l w e l l 8 8 ,9 0 】,c y d r o m e 的c y d r a 5 b e c k 9 3 】 r a u 8 8 r a u 8 9 】;最近超长指令字体系结构也开始出现在微处理器上,例如 k o h n 8 9 】 l a b r o u s s e 8 8 ,9 0 a ,9 0 b p e t e r s o n 8 1 】。这些处理器叫做超长指令字体系结构 【f i s h e r 8 3 ,它们都需要编译器确定哪些操作可以同时发射,并且把同时发射的 操作放在一个超长指令字中。 1 1 2e p i c 体系结构 i a 6 4 是第一个商业化的6 4 位e p i c ( e x p l i c i t p a r a l l e li n s t r u c t i o nc o m p u t i n g ) 处 理器。我们的研究工作就是以i a 6 4 体系结构为目标体系结构进行的。e p i c 体系 结构对超长指令字( v l i w , v e r yl o n gi n s t r u c t i o nw o r d ) 体系结构进行了革命性的 变革,并吸收了很多s u p e r s c a l a r 处理器的优点。过去以m u l t i f l o w 和c y d r o m e 为 代表的超长指令字体系结构只能对运行数学计算这样的应用性能比较好但是对 于标量应用的效果就不是很好了。并且,当时的超长指令字体系结构没有很好的 指令兼容性。而一个真正的通用处理器必须在运行标量应用和数学计算应用时都 可以取得较好的性能。e p i c 体系结构继承了超长指令字体系结构能够静态确定 代码执行顺序,显式地表示并行性的思想,同时引入了很多超标量体系结构的特 基于鲑域的编泽技术和拽寄存器优化 征。e p i c 的思想体现在如下三个方灏: 1 能够在壤译露确定掺令懿撬褥毒手巅,纛就是,所有指令按照嚣么颓唐执行 主要是由编译器来控制的,而体系结构为编译实现这个目标提供便利。 2 禁些憾援下,揍令戆撬行蹶摩只有在运行黠才黥确切她翅道。铡摇,条罄 跳转执行。但是通常情况下,跳转大多是向着某个分支执行的次数比较多。e p i c 的思想是,让编译器能够静态地,按照更可能的情况进行编译。倒女爨,对于数值 投机和控制投机的硬件支持就体现了这个思想。 3 编译器能够把编译时确定的信息传递绘硬件,例如,哪些指令同时执行, 以及使用了哪鎏资源等。 k a t h a i l 2 0 0 0 s c h l a n s k e r 2 0 0 0 】 为了实现这些思想,更大限度媳利用程序中可能的指令级并行,e p i c 体系 结鞠爝热了戳下熬磐特征: 一对数值和控制投机的支持 黠游诱戆支持 _ 通过并行比较缩短布尔操作的关键路径长度 疆l 孛黠予指令阕依赖关系数凌态测试 编译器可以驻式地控制加载存储操作的内存层次 l 一些资源对缀译器是可见的,编译器可跌蹲它们进行控趔 一增加了方便软流水执行的旋转寄存嚣 等等。 作为种e p i c 处理器,i a 6 4 体系结构也在硬件体系结构中支持谓词,数值 和控制投机,预取,以及为软流水 l a i n 8 8 实现增加的旋转寄存器栈。【h l t m a n 0 0 。 1 1 3 些支持指令级并行的硬件技术 超长指令字处理器的好处是可以使得处理器中的发射邋辑相对于超标擞体 系结槐来说魄较篾攀,但是它的不到之处是霹默同时执行斡撵佟集会在编译隧裁 已经确定了,这样在以后每次执行时都是固定的。在个指令中可以同时执行多 个操作还意眯着具有每次发射多令分支跳转援令的熊力。现在有很多葶申类型的多 路分支指令被提, 冉, c o l w e l l 8 8 】f e b c i o g l u 8 8 】( f i s h e r 8 0 n i c o l a u 8 5 a ,i a 6 4 体系结 构中也实现了这种多路跳转攒令。 在进行措令级并行计算时首先遇到的障褥就是通常每个基本块的大小都是 比较小的,遥样,传统的基本块内优化能够发掘的指令级并行非常有限。因此, 为了究分巅鞠处瑾嚣提供静攒令缀并行麓力,藏必须能够驮不藏基本浃中选取指 令,把它们放在一起同时执行。然而对于分支跳转指令( 通常是在基本块的最后 一条撩令) ,只有在麓态运行辩才裁确定接下寒撬露稻一个蘩零块。蠢毙,为了 发掘更多指令级并行,动态投机执行被广泛采用 h w u 8 6 ,8 7 s m i t h 8 8 s o h i 8 7 。 第一章引言 其中一种方案是主要由硬件完成的。在这钟方案中,硬件必须能够: 1 在跳转操作被r e s o l v e d 以后中止不必要的投机操作。 2 消除本来不该执行但是却被投机执行了的指令。 3 保证在它知道异常操作已经被执行以前不会有其他异常操作。 4 在每个投机执行的分支跳转处保存足够的状态,以保证如果执行了错误的 路径时,可以恢复到正确的执行路径。 但是,这样的机制在硬件上实现是代价昂贵的。另一种选择方案是在编译时 进行代码投机移动,把后边基本块中的操作跨越分支指令移动到前边的基本块中 去。这样的代码移动在很多全局指令调度【e l l i s 8 5 】 f i s h e r 7 9 ,8 1 算法中是普遍存 在的。这样,需要的硬件支持就会少很多,只需: l 当执行路径不正确能够引发异常时,有恢复处理机制。 2 用于保存投机执行状态的额外寄存器。 当投机执行运行到错误路径上时,总是会造成很大的开销,因此,必须有精 确的分支预测技术来指导投机执行的进行。这样,很多种不同类型不同复杂度的 动态机制就被提出用于在程序执行时收集程序执行的统计数据,以提供更精确的 分支预测 l e e 8 4 m e f a r i n 9 8 6 s m i t h 81 y e h 9 2 。 谓词执行是一种体系结构特征,单个操作是否执行由一个布尔值来确定。条 件转换 a l l e n 8 3 n - j 被用来减少指令调度时的控制流限制,它能够把控制依赖转 换为数据依赖,这也需要硬件中提供谓词寄存器来支持条件转换的执行。 1 1 4 指令级并行的编译技术 指令调度和寄存器分配是指令级并行编译技术中的核心问题,但是其他的优 化算法,例如投机执行,条件转换等也对更好的指令调度性能有着很关键的作用。 下边,我们就对这些算法的做一个简单的回顾。 过去有很多能够跨越基本块的边界进行指令调度的算法被提出。轨迹调度 f f i s h e r 7 9 f i s h e r 8 1 】,s u p e r b l o c k c h a n 9 9 1 和h y p e r b l o e k 调度 m a h l k e 9 2 都在一 个被称为轨迹的区域上进行指令代码移动。一条轨迹是由一个连续的基本块集合 组成的。t r e e g i o n 调度使用了一个程序控制流图的决策树予图做为一个调度区 域。e b c i o g l u 的超长指令字调度 m o o n 9 2 用一种决策树的形式来放置指令。 b e m s t e i n r o d e h 则描述了一种使用一个程序依赖图p d g f e r r a n t e 8 7 做为框架 结构来进行全局指令调度。在大多数调度算法中,控制流变化被用于简化有旁入 边或者在控制流中有合并点的区域。h y p e r b l o c k 调度使用条件转换来消除调度区 域中的控制流。尾复制,虽然会增加代码量,但是也被用于消除调度区域的旁入 边。轨迹调度允许调度范围内有旁入边,但是它只允许调度范围是一个线状的区 域。而波前调度 b h a r a d w a j 9 9 允许调度范围是一个多入1 3 多出口的区域。并且, 基于区域的编译技术和栈寄存器优化 它用延迟补偿来解决了调度过程中补偿代码的放置问题。 在寄存器分配方面,c h a i t i n 首先采用了图着色的算法 c h a i t i n 8 2 来进行寄存 器分配。在此基础之上,后来的研究者对它进行了各种改进。例如,f r e d 提出了 基于优先级的 c h o w 8 4 寄存器分配算法。这个算法是基于启发式信息一一个优先 级函数来确定活跃区间的着色顺序。而b r i g g s b r i g g s 9 4 】使用了静态单赋值表 示来确定活跃区间的分裂点,并且活跃区间的分裂是在着色前进行的。一个活跃 区间,如果它不能被分配到寄存器,就会被分裂。t e r a 编译器f 1 2 为程序构造了 一个层次树这个树对应于程序的控制流层次。l u e h l u e h p h d t h e s i s 提出了基 于融合的寄存器分配算法,并且对寄存器分配中跨越调用点时调用者寄存器和被 调用者寄存器的使用进行了优化 l u e h 9 7 1 。 虽然指令调度和寄存器分配作为指令级并行优化的核心,但是一系列其他的 分析,优化和变换对于生成高质量的代码也是很重要的。例如,在目前指令调度 仍然把一个函数调用视为代码移动的障碍。这样,在程序频繁执行的部分对内部 函数和用户函数的内联就显得十分重要 d e h n e r t 9 3 l i n n 8 8 l o w n e y 9 3 1 。 特定的面向循环的分析和优化主要是为了提高模调度的质量。条件转换和适 当地放置谓词控制使得有控制流的循环能够被进行模调度 a l l e n 8 3 】【d e h n e r 【9 3 d e h n e r t 8 9 】【p a r k 9 1 。同样,条件转换对于指令调度范围的扩大也有很大的好处。 消除跨越循环多个迭代的带下标的加载和储存操作对于r e s m i i 和r e c m i i 有很 大的影响 c a l l a h a n 9 0 】 d e h n e r t 9 3 】【r a u 9 2 】,同样,它对于进行了循环展开的循环 进行轨迹调度也很有作用。 另外,一个对所有指令级并行优化都存在的重要问题是内存引用的模糊性。 也就是,不能确定两个内存引用是否访问同一个内存地址。针对这个研究题目一 依赖分析,已经在向量计算领域进行了长达2 0 多年广泛深入的研究 z i m aa n d c h a p m a n 9 0 1 。对于向量计算机,编译器试图确定在不同迭代中的两个内存访问 是否访问的是同一个地址。因为如果访问的是同一个地址,那么这个循环就不能 进行向量化。从指令级并行的角度来看,无论这两个内存访问是否对应到同一个 地址,这个依赖分析信息都是有益处的。另外,为了使得指令调度在不能确切知 道内存访问是否对应到同一个地址时也能够自由移动,数值投机也作为指令级并 行的一种优化策略而采用。 1 2 本文的贡献 由前述可以看到,为了提高指令级并行执行,编译器必须进行大量的优化。 而复杂的编译优化算法需要耗费大量的编译时间和资源。为了减少编译的时间, 并且提供给研究者一个灵活的研究平台,同时保证编译性能不下降,本文提出了 一种灵活的区域构造框架。另外,r s e 开销在某些程序的运行过程中占有很大的 4 第一章引言 比例,针对这个问题,提出了一种能够有效减少r s e 开销并提高编译性能的方 法。 在区域的构造方面,我们的贡献主要是: a 提出了属性的概念,每个区域可以由不同的属性标记,而这些属性可以 在跨越不同的优化阶段时被观察到,并且不同的优化阶段会对这些属性进行维 护。在我们的系统中,总共提出了四种属性:不可跨越区域边界进行优化,不可 再优化,边界不可分割以及区域不可再划分。这是过去的研究工作所没有论及过 的。 b 提出了最小出口概率和最大尾复制比率的概念,用于控制单入口多出口区 域构造时的形状,大小和代码复制量,以保证给不同的优化阶段提供充分的优化 机会,同时保证编译优化的性能。这种有限制条件的单入口多出口区域构造算法 在过去的工作中是没有的。在本系统中,后端优化的大部分阶段都是基于单入口 多出口域进行的,因此这些限制条件对于保证区域的形状和代码复制量,从而保 证基于区域的编译优化阶段的性能具有重要的意义。 c 提出了新的区域构造框架。在该区域构造框架中,函数的所有基本块都 被划分到至少一个区域中,而所有的区域被组织成树状的形式。区域树总共包含 四种类型的区域:循环区域,非正常区域,单入口多出口区域和多入口多出口区 域。非正常区域的目的是为了把不适合优化的部分划分出来,保证不会对其他区 域的优化造成困难。 d 在o r c 编译器中实现了基于区域的优化编译框架,并且在这个框架上实 现了基于区域的条件转换,谓词分析,指令调度等技术。实验结果表明,基于区 域的优化技术大大地减少了程序的编译时间,最高可以减少接近5 6 的编译时 间,并且对某些程序的性能,在峰值优化选项时有大幅度的性能提高,最高达到 了1 4 。而过去的区域构造算法并没有对有区域构造和没有区域构造时的编译性 能进行过比较。 在程序的栈寄存器性能优化方面,有如下的贡献: a 提出了个有效的r s e 开销代价模型。分析了栈寄存器溢出回填时以时 钟周期为单位的代价,并使用监测安腾处理器事件的软件p f r a o n 对这个代价进 行了比较精确的测量,得到了一个根据栈寄存器溢出数量来计算最后的溢出代价 公式。 b 提出了一种过程间的栈寄存器分配解决算法,这个算法基于前边提出的 代价模型和加权调用图,为每个函数分配一个栈寄存器使用配额。 c 在o r c 开放源码编译器中实现了该算法,实验结果表明该算法对于程序 的性能有很大的提高,特别是对于那些r s e 代价很高的程序。最多有1 4 的性 能提高。而对于那些r s e 代价很小的程序,没有太多的性能提高,但是也没有 对性能产生坏的影响。至今未见有减少程序的r s e 开销从而提高程序的执行性 基于区域的编译技术和栈寄存器优化 能的研究工作报导。 d 提出了一种更为有效的寄存器分配改进算法。对于程序中某些活跃区间 的溢出不会增加内存处理代价的现象进行了分析,并且提出了一种改进的算法, 使得p e r l b m k 的程序性能有大幅度的提高。 1 3 文奎的组织 这篇论文分为八章。首先,第一章对研究工作的背景进行了简单的介绍,并 且说明了本文的主要贡献。 第二章对i a 6 4 体系结构和o r c 编译器的中间表示语言以及它的整体框架 结构进行了简单的介绍。 第三章详细描述了o r c 编译器的后端优化,包括条件转换,谓词分析,指 令调度,以及投机执行等。这些优化阶段都是基于区域进行的。 第四章对区域的设计和构造进行了详细的阐述,包括区域属性的设置,区域 的类型,区域的构造限制条件等,并提出了区域构造的算法以及该算法应用于控 制流图的实例分析。 第五章对o r c 编译器中实现的区域从编译时间和编译性能两个方面和基于 函数的编译进行了实验比较,并对实验数据进行了分析。 第六章阐述了程序执行时由于累积栈寄存器使用过多而导致的r s e 开销问 题,并且对这个问题进行了实验分析,提出了一个基于加权调用树和过程内寄存 器分配反馈信息的过程间栈寄存器分配方法。另外,分析了寄存器分配中出现的 一些问题并提出了改进算法。 第七章对我们提出的算法进行了实验。实验结果显示我们的算法对于程序执 行性能的提高具有非常明显的效果,尤其是r s e 开销比较大的程序,最多竟然 达到了1 4 。而对于活跃区间进行的分析和优化更进一步地提升了p e r l b m k 的程 序性能。 第八章给出了文章的总结,讨论了未来可能进行的研究工作。 6 第二章安腾处理器和o r c 编译器概述 第二章ia 6 4 体系结构和0 r 0 编译器概述 21i a 6 4 体系结构 i a 6 4 体系结构是第一个商业化的e p i c 处理器。它是惠普公司和英特尔公司 合作研究开发的。i a 6 4 体系结构具有如下的一些特征 i n t m a n 0 0 : 一显式的指令并行: 为了支持显式的指令并行,i a 6 4 体系结构引入了一些能够很好地融合编译器 和处理器的机制。i a 6 4 体系结构每个时钟周期可以发射六条指令,这六条指 令又分为两个指令束。i a 6 4 体系结构编译器在编译时静态地确定指令的执行 顺序,选择指令束的模版和确定指令在指令束中的位置。同时,它还通过一 些机制使得编译代码把编译时的信息传递给硬件,例如指令模版,分支后缀 和缓存操作后缀等。这对于减少分支跳转时和缓存不命中导致的开销是非常 重要的。 一提高指令级并行的硬件特征: 为了减少指令执行在关键路径上的延迟时间,i a 6 4 体系结构增加了对控制投 机和数值投机的硬件支持。另外,i a 6 4 体系结构还增加了对谓词的支持,这 样可以消除分支指令,把条件依赖转换为数值依赖,增加基本块的大小,扩 大指令调度的范围。同时,还可以消除分支预测错误的开销。i a 6 4 体系结构 增加了对循环进行软流水优化的硬件支持,可以减少进行优化时的开销。并 且,对分支指令谓词执行以减少分支跳转的开销。i a 6 4 体系结构还使用了寄 存器栈来减少在过程被调用和返回时不必要的寄存器溢出和回填处理。另外, 体系结构还提供了大量的硬件资源以支持指令级并行,它拥有1 2 8 个浮点和 整数寄存器,6 4 个谓词寄存器以及8 个分支寄存器。并且,i a 6 4 体系结构还 提供了多个功能单元和多个内存访问端口。这样,可以减少因为争夺硬件资 源而造成的指令相关 _ 致力于提高软件性能: 为了适应不同的软件应用,提高应用程序的执行性能,i a 6 4 体系结构还对软 件模块化有特别的支持,有高性能的浮点运算结构,并且增加了特别的多媒 体指令。 虽然i a 6 4 体系结构中增加了很多支持指令级并行的硬件特征,但是如何充 分地利用这些硬件特征,发掘程序中的指令级并行机会,还需要编译器做很多的 工作。 基于区域的编译技术和栈寄存器优化 优化险段生间蠢丞翻谨z 隆低动佳 v h o s t a n d a l o n e o p t i m i z e r i p a p r e o p t l n o w o p t r v l l r v l 2 c g 卑甲甲 v e r yh i g hw h i r l r h i g hw h i r l m i dw h i r l l o ww h l r l i v e r yl o w w h i r l i c gm a c h l n e i n s t r u c t i o n r e p r e s e n t a t i o n f r o n te n d s l o v e ra g g r e g a t e s u n - n e s tc a l l s l o w e rc o m m a s r c o m m a s l o v e ra r r a y s l o v e rc o m p l e xn u m b e r s l o v e rh i g hl e v e lc o n t r o lf l o w l o w e ri o 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 i o n s l o v e rb i t - f i e l d s l o w e ri n t r i n s i c st oc a l l s l o v 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 e q 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 c1 i n kf o rn e s t e d p r o c e d u r e s g e n e r a t es i m u l a t i o nc o d ef o r q u a d s a 1 1d a t am a p p e dt os e g m e n t s m a po p c o d e st ot a r g e t m a c h i n eo p c o d e s c o d eg e n e r a t i o n 图io r c 编译器中间表示持续翻译的过程 8 篇二章安腾处理嚣和o r c 编译器概避 2 20 r 0 并放源鹞编译舔 o r c 开敖灏鹞编译器是在开放源码编译器p r 0 6 4 懿基础土宠藏熬。p r 0 6 4 本 身包括了很多的先进优化和编译技术,下边我们对这个编译器做一个简单的描 述。 p r 0 6 4 编译嚣是一个基于l i n u x 操作系统,面向i t a n i u m 。处理器的优化编译 器。它撼供了一系列编译优化,包括过援闻分据秘优化,循环嵌套优化和并行化, 以及全硒优化,用于反馈信息擞成的插装以及旗子反馈信息的优化等。在o r c 编译器中,中间表示叫做w h i r l w h i r l l 。w h i r l 中间袭示是树状结构的,有引 用指向符号表。这种中闯表示霹戳灵活遣向上对应多种编程语言,向下霹应多种 目标机器。 在今天豹编译嚣中,优伲已经成为令不霹绥靛部分,瑟缡译器懿嚣端氇交 得越来越庞大和复杂。当我们在编译器中增加不同种类的优化时,也在增加着编 泽器磊壤兹复杂疫。对予增麴熬每一舞饶往算法,我翻必矮更热注意编译器麴健 壮性,因为每种新的优化都可能对编译器带来新的不稳定性。而优化都是在中间 表示墩上逶孬瓣,辑以,设诗个戆搜每个优位除段郝可以农其上进学奏效的 操作的中间表示是非常麓要的。p r 0 6 4 编译器的中间表示w h 砒分为:最高层 ( v e r y h i g h w h i r l ) ,高屡( h i g h w h i r l ) ,书间层( m i d w h i r l ) ,低慰( l o w w h i r l ) ,最 低层( v e r yl o ww h i r l ) ,直到最低的机器代码表示c g i r 。在优化的过程中,中间 表示也在不断地被降低别更低屡的中间表示。圈l 描述了编译过程和中间表示的 层次之间的关系。在编译器中,每个优化阶段都是在巢个特定的中闻表示层j : 进行的。前端首先生成最高级别的中间寝示。优化处理和继续降低中间液示层次 的过程闻时送行,在这羹我稍爵黻把中闯表示降抵静过稷称为戆中闻表示及当蘸 层转换到更低级别的层。最后,代码生成器把最低级别的中间表示翻译为它自己 霹瑷帮瓣标撬熬代码秘嚣配戆凌都表示。因为中闻表承簿羝豹蓬程是逐渐进行 的,因此一个额外的好处是每个降低的过程都会比较简单和容易。编译器的逻辑 筑纯模式魏蘸2 掰暴。 p r 0 6 4 编译器的编译过程由以下几个部分顺序完成:前端,过程间分析和优 化,季毳臻嵌套优纯积荠行纯,全羯优化,以及鬣端魏代碣生戏爨。其编译滚程如 图3 所示。 过理间分攒包括:调用撼的构造,过程问别名分析,数组区域分析等。过稷 闯优化怒和过稷间分析紧密结合在一起的,它毹括如过程的内联和复制,死函数 和变量的删除,常数传播,代粥和数据布局等。循环嵌簇和并彳亍化包括循环级依 赖分析,针对革处理器的循环嶷挟,自渤并行纯等。在循环交换中,所肖优话怒 基于统一的代价模型的,它会把循环向量依赖信息传递到后端的代码生成部分。 循环交换包括了基本一t 掰有豢麟酶循环交换我毒 :,翔镰弱:交换,镶繇分爱,锤繇 奎 基于区域的编译
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026年村务工作题库(含答案)
- 消防设施操作员初级技能考试备考指南及答案
- 船舶通信原理与设备练习题及答案
- 质量检测与安全考试模拟试卷及答案
- 统计学在环境监测数据共享中的应用备考习题集及答案
- 初级经济师金融产品销售模拟试题及答案
- 2026年二级营销师考试题库带答案
- 2026年基金从业资格考试证券市场基础知识专项训练题库及答案
- 药理学药物药代模拟试题及答案
- 房地产经纪人考试房地产法律法规专项练习题库及答案
- 骨髓移植后血型鉴定课件
- 肾动脉栓塞介入术
- 《邮轮烹饪英语》-《邮轮烹饪英语》-Appendixes
- 魅力辽宁课件
- 天津市2021-2024年中考满分作文59篇
- 口腔正畸接诊流程技巧
- 军队职工抚恤管理办法
- GB/T 39542.3-2025技术制图活动铅笔第3部分:黑铅芯HB铅芯弯曲强度
- 班级历程回顾
- 森林旅游学习通超星期末考试答案章节答案2024年
- 县乡教师选调进城考试-教育法律法规题库含答案(突破训练)
评论
0/150
提交评论