（计算机系统结构专业论文）谓词相关编译技术和深层代码优化.pdf

请侧相关编译技术和深层代码优化：摘要摘要指令级并行在很大程度上促进了计算机体系结构的发展和进步，同时也促使计算机的性能前进了一大步，指令级并行从出现开始就成为一个热研究领域并且在很长时间内已经取得了很多研究成果：关于指令级并行极限的研究 w a l l 9 1 】表明指令级并行理想的i p c ( i n s t r u c t i o np e rc y c l e ) 多数程序能达到5 ，其他的研究指出运用先进编译技术和理想的模型指令级并行的i p c 能超过2 位数，而实际的编译器产生的代码很难达到5 个i p c ，特别是对一款产品处理器。体系结构的设计不断给编译器支持以获得更高的指令级并行；谓词技术的支持在一定程度上对指令级并行增加了机会同时也有新的挑战，本文工作重点对谓词技术做了充分的研究，论述了谓词技术在编译技术中作用及其在体系结构中的地位，同时研究了e p i c 体系结构相关的深层代码优化，并取得以下研究成果：1 建立条件转换的代价模型，把条件转换与误预测高的分支跳转联系起来，进行预测的指令调度，精确了条件转换的代价模型，作为谓词技术支持的一部分，使条件转换与谓词分析技术能够相辅相成。2 提出一种在区域上计算谓词关系的谓词分析技术，建立了谓词关系数据库，在i a 6 4 开放源码研究编译器o r c 中实验分析了谓词技术的性能影响，进一步分析了认一6 4 体系结构谓词支持技术的作用。3 提出了避免s s a 表示的谓词分析方法，解决了多到达定值的谓词分析问题，适应了o r c 后端代码生成的中间表示c g i r ，实验表明谓词分析技术的灵活应用与准确计算对谓词的多到达定值的处理技术是高效的。4 提出并实现了谓词敏感的数据流分析框架，解决了数据流分析中存在的条件指令的定值和引用问题。谓词敏感的数据流分析产生的流分析信息一方面生成程序分析的流依赖信息，另一方面生成了活跃变量在控制流基本块之间的活跃信息，它区别谓词支持对指令调度和寄存器分配的局部影响，更能反应谓词技术在程序本身中的行为。5 提出控制流路径敏感的深层代码优化技术，在控制流的优化中容易做到的是如何消除分支，或者缩短关键路径等，而本技术把控制流路径按照程序的入口和出口对应形成不同的路径区分开来分别优化，特别对多出口的程序来说显示出优越性。6 提出l i n u x 操作系统下的程序调用共享连接深层优化技术，改进了对程序符号表属性的优化设置，进而对函数调用进行优化；并且适应e p i c体系结构特征对全局变量进行优化布局，减少了程序的访存开销，对存储优化效果明显。i a 一6 4 开放源码研究编译器o r c 作为一个健壮灵活的研究平台为本文取得的研究成果提供了保证，谓词技术的支持是i a 6 4 体系结构的新特点，o r c 中谓词相关编译技术和深层代码优化关于谓词技术的研究是一个重要组成部分；o r c 中的数据分布优化还存在不足之处，与i n t c l 的产品编译器还有差距，特别是在过程间分析中数据分布优化的应用还需要继续分析研究，相信还会取得明显的研究成果，所以在程序调用共享连接技术下的数据优化仍是未来的研究方向。关键词：条件执行，指令级并行，谓词划分图，谓词关系数据库，程序调用共享连接，数据布局i l谓词相关编译技术和深层代码优化：摘要a b s t r a c ti n s t r u c t i o n l e v e lp a r a l l e l i s mh a sg r e a t l ya c c e l e r a t e dt h ed e v e l o p m e n ta n di m p r o v e m e n to fc o m p u t e ra r c h i t e c t u r e ；l i k e w i s e ，t h ep e r f o r m a n c eo fc o m p u t e rh a sb e e ne n h a n c e db yal a r g es t e p f r o mt h eb e g i n n i n g ，i n s t r u c t i o n l e v e lp a r a l l e l i s mh a sb e e nah o tr e s e a r c ha r e af o rc o m p i l a t i o nt e c h n o l o g i e sf o ral o n gt i m ea n dal o to fa c h i e v e m e n t sh a v e b e e na c h i e v e d al i m i ts t u d yo ni n s t r u c t i o n - l e v e lp a r a l l e l i s m【w a l l 9 11i n d i c a t e dt h a ta ni d e a li n s t r u c t i o n l e v e lp a r a l l e l i s mc o u l dr e a c h5i p c ( i n s t r u c t i o n sp e rc y c l e ) f o rm o s to fp r o g r a m s h o w e v e r , c o m p i l e r sf o rr e a lm a c h i n e sh a v ed i f f i c u l t i e si ng e n e r a t i n gc o d ew i t ht h a th i g hi p c t h ed e s i g no fc o m p u t e ra r c h i t e c t u r ea i m st os u p p o r tm o r ec o m p i l e ro p t i m i z a t i o n st oe x p l o i th i g h e ri n s t r u c t i o n - l e v e lp a r a l l e l i s m ；p r e d i c a t i o ns u p p o r to f f e r so p p o r t u n i t i e sf o ri n s t r u c t i o n l e v e lp a r a l l e l i s mb u tp r e s e n t sc h a l l e n g e sf o rc o m p i l e r t h et h e s i sf o c u s e so nt h er e s e a r c ho fp r e d i c a t i o nt e c h n o l o g i e sa n de l a b o r a t e si t sa p p l i c a t i o ni nc o m p i l e ro p t i m i z a t i o na n di m p a c to nc o m p u t e ra r c h i t e c t u r e ，i nt h em e a n t i m e ，t h et h e s i ss t u d i e se p i c d e p e n d e n to p t i m i z a t i o n sa n da c h i e v e sf o l l o w i n ga c h i e v e m e n t s ：1 i n t r o d u c eac o s tm o d e lf o ri fc o n v e r s i o nt ot a k et h o s eb r a n c h e sw i t hh i g hm i s sp r e d i c t i o nr a t e si n t oa c c o n n t ，a n ds i m u l a t et h er e s o u r c e ss c h e d u l i n gw i t hp r e d i c t i o n t h ei fc o n v e r s i o np h a s eb u i l d sap r e c i s ed e c i s i o nt e c h n i q u et oc o n v e r tc o n t r o lf l o wi no r d e rt oe l i m i n a t eb r a n c h e sa n dh e l pp r e d i c a t e sa n a l y s i st e c h n i q u ew i t he a c ho t h e r2 i n t r o d u c eap r e d i c a t ea n a l y s i st e c h n i q u eb a s e do nr e g i o n st ob u i l dap i e d i c a t er e l a t i o nd a t a b a s e ( p r d b ) o ni m p r o v i n ga n de v a l u a t i n gp r d b ，t h et h e s i sm a d ev a r i o u se x p e r i m e n t si ni a 6 4o p e nr e s e a r c hc o m p i l e rr o r e ) t oe x a m i n et h ep e r f o r m a n c ei m p a c to fp r e d i c a t i o nt e c h n o l o g y , i nt h ee n d ，t h et h e s i sp r o v e st h eo v e r a l ls t a t u so f p r e d i c a t i o ni ni a 一6 43 h a n d l em u l t i p l er e a c h i n gd e f i n i t i o n si np r e d i c a t ea n a l y s i sw h i l ea v o i d i n gs s af o r m t h e r ea r en os s ar e p r e s e n t a t i o n si nc o d eg e n e r a t o ro fo r cb a c k e n d ，s ot h ef l e x i b l ea p p l i c a t i o na n da c c u r a t ec o m p u t a t i o no fp r e d i c a t ea n a l y s i sd e m o n s t r a t e st h et e c h n i q u eh a n d l i n gm u l t i p l er e a c h i n gd e f i n i t i o n st ob ee 艏c i e n t 4 ，i n t r o d u c ea n di m p l e m e n tp r e d i c a t e a w a r ed a t af l o wa n a l y s i si no r c ，r e s o l v ec o n d i t i o n a ld e f i n i t i o na n dr e f e r e n c ep r o b l e mo fp r e d i c a t e di n s t r u c t i o n si nc o n v e n t i o n a ld a t af l o wa n a l y s i s p r e d i c a t e a w a r ed a t af l o wa n a l y s i sb u i l d st h ef l o wi n f o r m a t i o nb o t l lf o rp r o g r a md a t ad e p e n d e n c ea n a l y s i sa n df o rv a r i a b l e s l i r er a n g ea n a l y s i si na n db e t w e e nb a s i cb l o c k s p r e d i c a t e a w a r ed a t af l o wa n a l y s i si sd i f f e r e n tf r o mt h ei m p a c to fp r e d i c a t i o ni ni n s t r u c t i o ns c h e d u l i n ga n dr e g i s t e ra l l o c a t i o n i ut h a ti tr e f l e c t st h ee s s e n t i a lb e h a v i o ro fp r e d i c a t i o ni np r o g r a m -5 i n t r o d u c eac o n t r o lf l o wp a t hs e n s i t i v ec o d eo p t i m i z a t i o nt e c h n i q u et h e r ea r ec o n v e n t i o n a lo p t i m i z a t i o n s ，s u c ha sr e m o v i n gb r a n c h e s ，r e d u c i n gc r i t i c a lp a t h s ，i i i滑词相关编译技术和深层代码优化e t c ；t h ep a t h s e n s i t i v et e c h n i q u ec l a s s i f i e sc o n t r o lf l o wp a t h si n t oo p t i m i z a t i o nc a n d i d a t e sa c c o r d i n gt op r o g r a me n t r yp o i n ta n dd i f f e r e n te x i tp o i n t s t h i si sav e r yh e l p f u lo p t i m i z a t i o n ，e s p e c i a l l yf o rp r o g r a m sw i t hm u l t i p l ee x i t s 6i n t r o d u c eac a l ls h a r e dl i n k i n gt e c h n i q u ef o ra d v a n c e do p t i m i z a t i o n su n d e rl i n u x ，o p t i m i z i n gs y m b o lt a b l ea t t r i b u t e sc o n f i g u r a t i o nt or e m o v er e d u n d a n tc o d eo nf u n c t i o nc a l ls i t ea n dm a k eu s eo fs m a l la r e af o rd a t al a y o u t ，r e s u l t i n gi nl e s sm e m o r ya c c e s s e s i tw i l lh e l pm o r ei ni n t e r - p r o c e d u r a la n a l y s i s ( i p a ) t ob r i n gm o r ea d v a n t a g e s i ti st h ef l e x i b l ea n dr o b u s tr e s e a r c hi n f r a s t r u c t u r eo fi a - 6 4o p e nr e s e a r c hc o m p i l e r ( o r c 、m a tg u a r a n t e e st h e s er e s e a r c ha c h i e v e m e n t s p r e d i c a t i o ns u p p o r ti so n eo ft h el l e wf e a t u r e s 洫i a 一6 4a r c h i t e c t u r e ，a n dp r e d i c a t i o nr e s e a r c hi n0 r ca i m st oe n a b l et h en e wf e a t u r eo fi a - 6 4a n de v a l u a t ei t si m p a c t t h eo p t i m i z a t i o no fd a t ap r o m o t i o ni no r cs h o w sb e n e f i t sb u tn e e d si m p r o v i n gc o m p a r i n gw i t hi n t e lp r o d u c t i o nc o m p i l e r t h ea p p l i c a t i o no fd a t ap r o m o t i o ni ni p ac a nb ee n h a n c e di nf o l l o w i n gr e s e a r c ha n dm o r ep e r f o r m a n c ew i l lb eg a i n e d ；s od a t ap r o m o t t o no p t i m i z a t i o nu n d e rc a l i s h a r e dl i n k i n gi saf u t u r er e s e a r c ha r e a k e yw o r d s ：p r e d i c a t e de x e c u t i o n ，i l p , p r e d i c a t ep a r t i t i o ng r a p h ，p r e d i c a t er e l a t i o nd a t a b a s e ，c a l ls h a r e dl i n k i n g ，d a t al a y o u tl v声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。就我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。作一：￥嵌，蹶关于论文使用授权的说明中国科学院计算技术研究所有权处理、保留送交论文的复印件，允许论文被查阅和借阅；并可以公布论文的全部或部分内容，可以采用影印、缩印或其它复制手段保存该论文。储繇节动剥徽坼秒厌蹶m ；y - 商r se第l 章引言1 1 指令级并行与谓词技术1 1 1 指令级并行第1 章引言指令级并行的研究曰的是为了发展和改进微处理器和编译器设计技术，旨在提高单处理器能够并行执行多条指令，获得更高的程序性能。然而在指令级并行i l p 发展的前三十年里，高性能单处理器中只存在较小的i l p ：尽管如此，从八卜年代开始指令级并行在计算机设 卜中形成一个重要的推动力，到九i 一年代业界丰要c p u 生产商的微处理器的设计中基本都采用了i l p 技术。指令级并行体系结构的发展早先的代表是s u p e r s c a l a r 体系结构；从七十年代新的i l p 体系结构超长指令字v l i w ( v e r yl o n gi n s t r u c t i o nw o r d ) 的出现开始，指令级并行研究取得了突飞猛进的发展；到虽新的显式并行指令汁算e p i c ( e x p l i c i tp 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 ) 体系结构的出现，它集中了s u p e r s e a l a r 和v l l w 体系结构的特点，并且增加了更多的支持编译器显式控制并行的新硬件特征。j t o r d e r s c h e d u l i t _ gm c r o a r c h i t 掣c t u r eu q t hp e t j k c tl | l e | l n r b e n c h m a r kg c c ：l s s u ew i d t hv si p cn t ll a t e l m t c r u p l w , e s s o r r e s e m z , hl a l _ f图1 - 1i p c 与发射带宽的对比多发射是提高指令级并行最直接的探索并且取得了明显的成果，然而图1 - 1的结论并不对无止尽的多发射抱有过高的期望 h t t p 3 l 。图中显示当发射带宽超过8 的时候，程序的指令级并行能力i p c ( i n s t r u c t i o n s p e r c y c l e ) 已经很难再有提升的机会了。而且从6 发射的体系结构中就应该可以挖掘最优性能的指令级并行，图中显示6 发射可以达到的比较好的平均并行度约为4 条指令周期；从软件技术上讲，编译器对指令级并行的贡献是根据体系结构的特点来做相应的优化，提高并行度。谓词相关编译技术和深层代码优化很多关于指令级并行性的研究从不同方面研究了指令级并行的能力与极限 j o u p p i 8 9 w a l l 9 1 b u t l e r 9 1 s m i t h 8 9 l a m 9 2 r a u 9 3 w a l l 9 3 p o s t i f f 9 8 l e e 0 0 ，并且用不同的方法论证了在不同条件下指令级并行可能达到的i p c 。这些研究的特点是针对产品微处理器上的指令级并行性多数只有2 1 p c 左右：而如果不考虑硬件现有的约束，而目硬件的资源电无限可阁，指令调度只要不违反程序语义即可的情况下，使用模拟器模拟理想微处理器的执行模型可以得到的指令级并行性的i p c 很容易超过l o 甚至对浮点程序更高能够达到大于3 0 0 0 匝o s t i f f 9 8 】：更容易让人理解的是，在模拟器上模拟一个资源有限、理论上能够实现的微处理器的执行模型，实验可得到的指令级并行性i p c 多数在2 到6 之间，很少有超过7 的。其中【l e e 0 0 专门研究了e p i c 体系结构上程序的指令级并行性，针对理想的e p i c体系结构模型，c a c h e 准确性1 0 0 ，无限带宽，无数端口和功能部件，指令只有单位延迟，控制流预测1 0 0 准确，i p c 高达7 2 6 ，文章依据更现实的模拟模型得到在程序间自由指令调度、函数受限的指令调度和循环受限的指令调度下的i p c 分别是6 8 ，6 2 和6 1 。研究者追求高度的指令级并行性，希望通过模拟环境下的研究促进体系结构设计的改进，对于更现实的微处理器来说指令级并行性的i p c 很难超过5 。作为e p i c 体系结构的代表基于i a - 6 4 体系结构架构的i t a n i u m t m 微处理器，发射带宽为6 ，显式的指令级并行体系，从硬件上是适合指令级并行相关的研究的。1 1 。1 。1 v l i w 体系结构在超长指令字v l i w 体系结构中，一条指令在什么时候发射，在哪个功能部件上执行都是由编译器显式指定的，并且要保证该条指令的执行和处理器上同时执行的其他指令是相互独立的。在这里我们有必要先辨析一下指令和操作的区别，操作是指个计算单元，例如一个加法操作，一个内存j 方问操作，或者一个分支跳转，它们相当于顺序执行的处理器结构中的条指令。而超长指令字体系结构的指令( v e r y l o n gi n s t r u c t i o nw o r d ) 是指一个可以同时执行的操作的集合。编译器负责确定哪些操作可以放到同一条指令中去，同时发射并且同时执行，这就是指令调度。所有准备同时发射的操作可以被放置到_ - 个超长指令字指令中，而同一条指令巾操作的顺序决定了每个操作将在哪个功能部件上执行 r a u 9 3 】。较早的具有影响力的超长指令字处理器被称为a t 纽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 ty s t e m s 7 9 】【i b m 7 6 】 i n t e l 8 9 【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 r 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 ；最近超长指令字体系结构也开始出现在微处理器上，f f 岫n 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 e b c i o g l u 8 8 】。在这一类超长指令字体系结构【f i s h e r 8 0 】 f i s h e r 8 3 】处理器中，都是由编译器决定哪些操第l 章引言作n n n n 发射，并且把可以同时发射的操作放在一个超长指令字指令中，编译器的角色实际上已经承担了程序分析和指令调度的任务【f e m n t e 8 7 。这些任务在早先的体系结构中都是由硬件完成的。1 1 1 2 e p i c 体系结构e p i c ( e x p l i c i tp 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 n t e l 公司的i a 6 4为代表，它的第一个商业化的6 4 位微处理器是i t a n i u m t m 。本文的研究工作是以n 6 4 体系结构l t a n i u m t m 处理器为目标机开展进行的，并且在o r c 编译器中实现 h t t p 2 s c h l a n 0 0 。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 a ) 体系结构进行了创新性的变革，并吸收了很多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 体系结构的设计思想体现在硬件给编译器提供的可编程性，把硬件与软件更紧密的耦台在一起，能够让编译器在编译阶段发掘更多可用的信息，并传递绘硬件，解决了现代高性能计算机中多个重要的性能瓶颈。如访存延迟、访存地址冲突解析、控制流依赖等。e p i c体系结构提供了丰富的硬件描述语义，促使编译器在更大的范围全局调度优化，发现更高的指令级并行，同时硬件提供充分的硬件资源增加指令级并行性，从而硬件和软件更完美的协作，达到更好的铿体性能。1 1 1 。3 指令级并行的硬件新特征在发掘进行指令级并行的过程。h 基本块通常比较小，很难在基本块内就获得很好的指令级并行，所以首先要解决的障碍就是怎样从不同基本块中选取指令，把它们放在一起并行执行。然而对于分支跳转指令( 通常是基本块的最后一条指令) ，只有在动态运行时才能确定程序控制流接下来的执行路径。因此为了发掘更高的指令级并行，硬件支持的动态投机执行技术被广泛采用【h w u 8 6 8 7 j s m i t h 8 8 1 ( s o h i 8 7 】 l j p a s t i 9 6 】，为了保证程序正确执行，微处理器硬件必须能够：1 在跳转操作的目标地址解析之后中止不必要的投机操作；2 消除本来不该执行却被投机执行了的指令；3 保证在它知道异常操作已经被执行以前不会有其他异常操作：4 在每个投机执行的分支跳转处保存足够的状态，以保证如果执行了错误的路径时，可以恢复到正确的执行路径。 嗣相关编译技术和深层代码优化然而，这样的机制在硬件上的设计实现代价是昂贵的；另一种选择方案是在编泽时进行代码投机移动，把后边基本块中的操作跨越分支指令移动到前边的基本块中去。这样的代码移动在很多全局指令调度 e l l i s 8 5 f i s h e r 7 9 ，8 1 算法中已经提出；而相应的硬件支持只需满足：l 当执行路径不正确能够引发异常时，有恢复处理机制：2 用于保存投机执行状态的额外寄存器。这样投机执行失败时程序将执行一段补偿代码，为了保证投机执行的准确性，必须有精确的分支预测技术来指导投机执行的进行。在相关的研究工作中，已经有很多种不同类型不同复杂度的动态机制被提出用于在程序执行时收集程序执行的统计数据信息，以提供更精确的分支预测f l e e 8 4 m c f a r i n 9 8 6 1 】l s m i t h 8 1 y e h 9 2 g o n 西l e z 9 7 。基于显式并行的e p i c 体系结构i t a n i u m t m 处理器为发掘更高的指令级并行提供了新的硬件支持，包括投机执行、谓侧执行等。谓词支持作为i t a n i u m t m 处理器的+ 个新特征，谓词支持的条件执行是解决程序分支跳转阻碍指令级并行的重要手段，早先的条件转换技术 a l l e n 8 3 开始带动了谓词技术的发展，硬件对谓词技术的支持主要是提供谓词寄存器以及指令集结构r o s a ) 对谓词的操作。1 1 2 支持谓词技术的硬件特征硬件对谓词技术的支持体现在两方面：。一是有读写谓词的寄存器，二是指令集有支持条件执行的机制。谓词寄存器是为增加对谓词的操作，支持谓词技术的体系结构在指令集上包含条件执行的指令，能够有条件地废止被选择的指令并且消除其负面影响。废止指令的条件就是谓词，存储在谓词寄存器中，在指令中是一个附加的操作数；而限定指令相应的渭词寄存器的内容则决定是否废l e 微处理器流水线中的指令。1 1 2 1 c y d r a 5c y d r a5 系统是采用了有向数据流体系结构的超长指令字( v h w ) 、多处理器系统。c y d m5 系统设计了条件执行的通用形式，其中的每一条指令字可以调度7 条操作，而其中每一个操作可以单独带限定谓词；操作中附加一个源操作数来表示谓词，这个谓词位于谓词寄存器文件中。谓词寄存器文件是由一组包含1 2 8 个1 位( 布尔值) 的寄存器组成。操作中的限定谓词在微处理器流水线的预取之后被检查，如果谓词寄存器的值是1 ，该指令就允许进入流水的下一级执行；否则就被废止。实际上限定谓词是”o ”的操作都在进入流水的执行级之前被转换成空操作”r i o o f f 。因此操作中限定谓词的值必须在完成流水的预取级时已经确定。只有三种操作可修改谓词寄存器的内容，它们是s t u f f , s t u f f _ b a r , 4第1 章引言b r t o p 。”s t u f f 操作有两个操作数，。个是目标谓词寄存器，另一个是布尔变量，其中布尔变量的值专门由比较操作产生，用来决定目标谓词寄存器的值。如果s t u f f 操作的限定谓词是1 ，目标谓词寄存器就被赋予布尔变量的值，否则该操作被废止；”s t u f fb a ，操作与此相似，只不过它会被赋予布尔变量值的非。”b r t o p ”操作用来控制循环，通过比较循环迭代计数器与循环边界来设置谓词寄存器控制下一迭代。1 1 2 2 a r m 体系结构a r m ，即a d v a n c e dr i s cm a c h i n e s 处理器，包括一类专用于低成本、低功耗的处理器，主要为嵌入式和多媒体应用程序而设计；a r m 的指令集体系结构支持所有指令的条件执行。每个指令都有一个四位条件域来指示指令执行的上下文，通过检查指令的条件域和处理器状态寄存器的条件码来计算指令的执行条件。条件码专由比较指令设置，而条件域表示了指令应该执行的比较关系，如等十、小于、小于等于。如果处理器状态寄存器中的比较指令产生的结果与条件域相匹配，则指令被正常执行；否则指令不是无效的。有了体系结构的硬件支持，a r m 编译器就能够消除指令流中的条件分支。1 1 2 3 h p l - p d 体系结构h p l - p d 体系结构中的条件执行的模型改进了c y d r a5 体系结构中的条件执行，有以下几个特点 k a t h a i l 2 0 0 0 ：设计了1 位谓词寄存器，包括静态寄存器和旋转寄存器：对谓词寄存器的操作主要是谓词比较操作，它们最多可设置2 个谓浏寄存器；还有谓词寄存器和整数寄存器之间数据转移的操作，谓词寄存器清零操作。另外，所有整型计算和标准访存操作借助控制寄存器别名能够同时操作2 3 个渭词：，类谓词比较操作和对多个寄存器同时写的特殊语义是计算布尔简约式的有效方法，并且是控制路径缩短的有效手段；大多数操作带限定谓词控制操作的执行，即条件执行。有少数操作的执行不能被废止，即使它们可能有一个或者多个输入谓词，但是这些输入谓词充当普通数值，比如循环软流水的分支跳转操作。而谓词比较操作就是4 个例外，因为很难区分是否被谓词限定。1 。1 2 。4 i m p a c t 体系结构模型i m p a c t 体系结构原型是支持静态调度、多发射的微处理器，它对条件执行的支持是从c y d r a5 系统演变而来。在设计上追求减少滑词设置指令( 这里指超标量机的指令) 和缩短谓词引用到谓词定值之间的依赖长度。谓词寄存器文谓词棚羌编译技术和深屡代码优化件设计成n + 2 的阵列式布尔( 1 位) 寄存器，对于n 个谓词总有1 位是真值、1位是假值与其对应。所以与一个谓词寄存器相关的对位值有三种组合：假真、真假、假假，其中”假假”对用于嵌套条件，说明分支跳转的两边都不必执行。在i m p a c t 体系结构模型r p ，许多指令可以修改谓词寄存器。”p r e dc l e a r ”可把个谓词寄存器的两位同时置零，而且新增了整型、无符号、浮点和双精度型的比较指令，其目标寄存器是谓词寄存嚣；目标谓训寄存器的”t ”域和f 域分别被设簧为比较结果和比较结果的反，这样就可用一条指令来设置表示”i f - t h e n - e l s e ”条件的互斥谓词。，1 1 2 5 1 a - 6 4 体系结构i a 一6 4 体系结构从设计上完全体现了显式并行的特点，指令级并行最高每个机器周期可以达到6 条操作，分为2 束，每束有3 条操作：有完备的谓词技术支持资源 n t e l 0 0 。硬件提供了6 4 个1 位谓词寄存器，第0 号谓词寄存器为永真，所有程序在任何级别都可使用谓词寄存器，并且分为前1 6 个是静态谓词寄存器，后4 8 个是旋转谓词寄存器，程序可用于换名进行软流水调度以加速循环。i a - 6 4体系结构提供了丰富的比较指令支持谓词操作，绝大多数指令都可带限定谓词，只有极少数指令无条件执行。指令集提供了位操作指令等，6 4 个1 位谓词寄存器文件可以与一个通用寄存器交互使用，指令通过”全工”模式可以并行操作多个谓词寄存器，谓词寄存器n 与通用寄存器的第n 位相互传递；可以帮助分别设置谓词寄存器文件畔i 的静态谓词寄存器和旋转寄存器。i a 一6 4 体系结构提供的谓词技术支持适合谓词技术相关的研究和优化，条件转换，控制依赖到数据依赖的转换，谓词敏感的指令调度，谓词限定的分支多路跳转等。1 1 2 6 其他系统许多同期的处理器提供+ 些形式的有限的条件执行支持。d e c 的a j p h a ，s p a r cv 9 和i n t e l 公司的奔腾p r o 处理器指令集提供了条件赋值指令。条件赋值指令功能上等价于带限定谓词的赋值。该赋值指令增加了一个额外的源操作数表示条件，与带限定谓词的赋值，条件为真时源寄存器的内容复制到目标寄存器，否则指令无效。d e c 的g e m 编译器能够利用条件赋值删除简单控制流结构中的分支跳转。h t ) 公司的p a r i s c 提供了所有分支、算术和逻辑指令来有条件地消除后续的指令：u i u c 大学的i m p a c t 编译器充分利用这一特点模拟了l i p 平台上的条件执行支持。第1 章引言1 。1 3 谓词技术谓词是限定指令执行的一个布尔值，在运行时处理器检查谓词寄存器的值，如果值为真则执行该指令，如果值为假则废止该指令相当一个空操作( n o o p ) ，谓词由一个1 位寄存器保存。谓词技术的快速发展是从条件转换技术 a l l e n 8 3 的发展而开始的，并且在指令级并行中很快发展成为一个热的研究领域。渭词技术的个典型应用就是条件转换，程序的分支跳转是阻碍指令级并行的一个重要因素：条件转换可以被用来减少指令调度时的控制流限制，它能够把控制依赖转换为数据依赖。为了从更大的调度空间获得指令级并行，谓词技术可以从条件转换和带谓词的指令投机 a u g u s t 9 8 两方面支持优化。早期的条件转换 a l l e n 8 3 在向量机上把控制依赖转换到数据依赖为代表，使用了表达式集合来表示语句执行的条件，把在不同控制流中的代码根据控制流的跳转生成不同的条件表达式来限制不同基本块的代码，从而生成更大的基本块，一方面消除了相应的分支跳转并且把控制依赖转换成了数据依赖，另一方面因为增大了基本块便于代码向量化。他们提出的方法虽然是在向量机的研究，然而条件转换是种独立的程序转换技术，所以很容易用到显式并行的指令级并行中来，【p a r k 9 1 介绍了指令级并行体系结构下的条件转换技术以及谓词技术在多方面的应用， m a h l k e 9 2 在i m p a c t - 1 编译器中提出了h y p e r b l o c k 结构，并且利用有选择的条件转换技术优化h y p e r b l o c k 结构中的控制流：相关的研究在模拟环境下的实验证明，条件转换在很多方面都取得了优化效果 w a r t e r 9 2 】【w a r t e r 9 3 】 m c c 9 6 】 c h o i 0 1 】。条件执行是谓侧技术的基本思想，它通过限定谓词在运行时的值来确定它所限定的指令是否执行 p a r k 9 1 】。条件执行与条件转换是紧密联系在一起的，条件转换生成谓词化代码，是由条件执行的指令组成，对条件执行的研究可以扩展到很多方面，影响分支跳转，改善分支预测等 m a h l k e 9 4 m c f a r i n 9 8 6 ，进行控制流优化 a u g u s t 9 7 ，提高指令投机执行 a u g u s t 9 8 m a h l k e 9 6 ，对谓词化代码的分析技术 j o h n s o n 9 6 l u 0 3 ，谓词化代码的寄存器分配 b r i g g s p h d t h e s i s e i c h 9 5 】 b r i g g s 9 4 g i l l i e s 9 6 c a l l a h a n 9 0 】，优化的指令调度 c a r t e r 0 0 s m e l 0 3 】。谓词技术支持的条件转换在软流水调度中的应用研究 w a r t e r 9 3 e i e h 9 5 】 m i l i e e v 9 8 s i a s 0 1 c h o i 0 1 】体现了谓词技术对指令级并行的显著效果，l i n p h d t h e s i s 在o r c 编译器中针对软流水优化进行研究提出优化分配栈寄存器的技术并且对程序性能贡献明显。n a n c y 等人 w a f t e r 9 3 在一个模拟8 发射的处理器上测试的结果显示条件转换可以使软件流水性能比应用层次缩减的循环调度提高4 8 ， c h o i 0 1 指出条件转换支持的软流水调度可以使浮点程序的性能提高3 5 ；a l e x a n d r e 等人使用谓词技术在软件流水中做了一个谓词敏感的寄存器分配的实验【e i c h 9 5 】，测试例子挑选了一个特殊的循环，使寄存器平均需求在最优的调度下从3 9 3 下降到3 6 5 ；然而谓词技术理论上的优点只是在软件流水7谓词相关编译技术和深层代码优化中得到了很好的实现和验证，谓词技术在消除分支预测，提高指令级并行，减少活跃变量的干涉，提高寄存器分配的效率等方面的优越性在实际针对商用微处理器的编译器中并没有实现令人满意的性能加速比。【m a h l k e 9 2 】提出h y p e r b o c k 编译技术，并且分析了它对条件执行的有效支持和优化方法，指 h 只有有选择性的条件转换才会促进程序的优化。文中使用p h g 分析h y p e r b l o c k 的谓词表达式进行了针对h y _ p e r b l o e k 的指令优化：投机、换名、合并，而很多常规的优化还没有在h y p e r b l o c k 上实现。与现有的编译器相比，先关闭i l p 的很多优化的情况下，h y p e r b l o c k 编译技术在性能上获得了一定的加速e b ，特别是在模拟机器的发射带宽比较宽的时候。只是文章采用的性能评价模型是以发射带宽为1 的基准处理器为计算标准计算了h y p e r b l o e k 技术在多发射处理器上优化的性能加速比；与基于区域的优化结构相比，区域显示了更多的优化性能 l i u 0 1 l i u 0 3 。【m a h l k e 9