（计算机系统结构专业论文）基于机器学习的编译优化适应性研究.pdf

摘要 编译器的开发者所面对的各种编译优化常常都是非常复杂的，甚至是n p 问题。所 以编译器开发者会从复杂问题中抽取出多个属性来构建模型去描述目标优化，以期得到 近优解。但是在实际开发中，所构建的模型可能没有全面准确描述目标优化，或者构建 的模型对需要编译的目标程序描述不够合理而无法得到期望的性能，这需要我们有针对 性地修改目标优化。另一方面，编译器所面向的硬件结构是非常复杂的，并且发展迅速。 当硬件结构发生改变，编译优化也需要进行相应调整。这些都对编译优化的调优提出了 多方面要求，编译优化适应性研究的出发点是如何让优化的调试过程自动进行，在有限 的时间内寻找到更为合适的优化配置，包括优化选项的组合，优化模型的参数调整等。 迭代编译和机器学习是常用的两种方法，本文中的研究都是基于机器学习展开，主要贡 献如下： 1 提出基于静态分析的快速机器学习，这是一种基于遗传算法的机器学习。机器 学习通常都是非常耗时的过程，如果采用程序的运行时间作为遗传算法中的适应值，对 于c p u 2 0 0 0 这样的大型程序来说，机器学习将花费好几天的时问。而基于静态分析的快 速机器学习的主要思想是g 在编译过程中收集优化生成的静态信息来作为机器学习的适 应值；然后通过限定静态分析的热点区域，进一步减少静态分析的时间和空间开销，同 时保证一定的精确度。最后，可以进一步添加部分动态时的信息，以增加机器学习的能 力。 2 根据基于静态分析的快速机器学习思想，本文就寄存器分配提出了两种快速机 器学习方法：溢出代码敏感的机器学习和溢出代码与热函数敏感的机器学习。溢出代码 敏感的机器学习是将寄存器分配中产生的溢出代码作为活跃区问的权值函数的适应值， 能大大降低时间开销，同时采用热文件来限定机器学习的范围，使其能较好地突出目标 优化的作用。而溢出代码与热函数敏感的机器学习，其适应值为溢出代码加上p r o f i l i n g 信息，这能更为准确描述溢出代码在程序中的分布和溢出代码对程序的影响。溢出代码 与热函数敏感的机器学习仍然仅需要较少的时问开销，同时此机器学习被限定在热函数 中，不但进一步缩小学习范围而且使学习热点更突出。 3 介绍如何基于o r c 编译器构建溢出代码敏感的机器学习和溢出代码与热函数 敏感的机器学习平台。并就这两种方法针对c p u 2 0 0 0 这样的大型程序对o r c 编译器中 的寄存器分配进行了学习，其实验数据分析表明了这两种学习方法的有效性。 4 为了衡量不同基于静态分析的机器学习，我们提出了机器学习衡量模型e f l e a 。 主要考虑两方面因素：适应值的变化和相应性能的变化。并就c p u 2 0 0 0 的机器学习结果 进行了衡量和分析。 5 为进一步弄清参与机器学习的各个优化因素在编译优化中的重要性和相互之间 的关系，本文提出了基于粗糙集理论的机器学习信息挖掘。研究的目标为机器学习中生 成的中问文件，其包含作为遗传基因的表达式及其相应的适应值。借助粗糙集理论中的 摘要 属性相对约简与求核，我们可以找到可被消除的因素和作为“核”的最重要的因素。通 过计算各个因素的相对重要性，可以量化各个因素的在权值函数中的作用，这将对进一 步的编译优化调试提供有力支持。 综上，本文提出了基于静态分析的快速机器学习：并对寄存器分配提出了溢出代码 敏感的机器学习和溢出代码与热函数敏感的机器学习；然后通过e 疖e c t 模型和基于粗糙 集理论的信息挖掘来探求为什么机器学习得到的结果能给编译优化带来好处。我期望通 过这个“知其然，知其所以然”的过程，让机器学习为编译优化适应性研究带来更多的 信息，为编译器开发者构建更好的优化带来更多的机会。 关键词：编译优化适应性，编译优化，寄存器分配，快速机器学习，机器学习衡量 模型，粗糙集 r e s e a r c h0 1 1c o m p i l e r a d a p d o nw i t hm a c h i n e l e a r n i n g h u z h a n g i i n ( c o m p u t e r a r c h i t e c t u r e ) d i r e c t e db y z h a n gz h a o q i n g c o m p i l e rw r i t e r sa l w a y sf a c et h ec h a l l e n g eo f n p h a r dp r o b l e ms u c ha sr e g i s t e ra l l o c a t i o n a n di n s t r u c t i o ns c h e d u l i n g t of i n da l le f f e c t i v ea n di n e x p e n s i v es o l u t i o ni sad i f i q c u l tw o r k w h i l es o l u t i o n sa r ee x p e c t e dt oi n t e r a c tw i t ho t h e ro p t i m i z a t i o n sw e l l ，a n dg e t t i n ga l lo ft h e m c o n c e r t e di sad a u n t i n gw o r k o nt h eo t h e rh a n d , t h ec o m p l i c a t e dc o m p u t e ra r c h i t e c t u r ea n d v a r i o u sa p p l i c a t i o n sm a k ec o m p i l e rw r i t e r s w o r kh a r d e ls i n c ei ti si m p o s s i b l et of i n dab e s t m o d e lc o n s i d e r i n ga l lf a c t o r s ，c o m p i l e rw r i t e r sh a v et oe x t r a c ts o m ea b s t r a c t i o na n dc r e a t e h e u r i s t i cm o d e lb a s e do na s s u m p t i o n s ，w h i c hp e r h a p sd on o tr e f l e c tt h er e a ls i t u a t i o n s t h e w o r kd e s c r i b e di nt h i st h e s i sh a s f o l l o w i n gc o n t r i b u t i o n s ： p r o p o s e df a s tm a c h i n el e a r n i n gm e t h o db a s e ds t a t i ca n a l y s i s m a c h i n el e a r n i n gi sat i m e c o s tp r o g r e s sa n d t a k i n gt h em n t i r n eo fo b j e c tp r o g r a ma st h ef i t n e s so fm a c h i n el e a r n i n gw i l l m a k e st h i sp r o g r e s sl o n g e r t h e r e f o r ef o rh u g ea p p l i c a t i o n s ，s u c ha sc p u 2 0 0 0 , t i m ec o s ti s e v e nu n b e a r a b l e s ow ep r e s e n t e daf a s tm a c h i n el e a r n i n gm e t h o db a s e ds t a t i ca n a l y s i s ，t h e m a i ni d e ai st h a tw ec a uu s et h ei n f o r m a t i o nc o l l e c t e di nt h ec o m p i l a t i o np r o g r e s st oe v a l u a t e t h ec o r r e s p o n d i n go p t i m i z a t i o n , a n dd u m p i n gs o m ei n f o r m a t i o ni nc o m p i l i n gp r o g r e s sd o c s n t p u ta n ye x t r ab u r d e no nc o m p i l e r u s u a l l ys o m es t a t i ci n f o r m a t i o nr e f l e c t so p t i m i z a t i o n d e s i g n e r si d e a , f o re x a m p l er e d u c i n gs p i i lc o d ei st h em a i ni d e ao fs o m er e g i s t e ra l l o c a t i o n t h e nw ew i l lf o c u so nh o tr e g i o n st or e d u c et h et i m ec o s ta n dm a k et h ee v a l u a t i o nm o r e a c c u r a t e f u r t h e r m o r ew i t ht h eh e l po fp m f d i n gi n f o r m a t i o no u rf a s tm a c h i n e l e a r n i n gc a nd oa b e t t e r j o b s p i l lc o d es e n s i t i v el e a r n i n ga n ds p i l lc o d e & h o tf u n c t i o ns e n s i t i v el e a r n i n ga r eg i v e n b a s e do ht h ei d e ao ff a s tm a c h i n el e a r n i n gm e t h o df o rr e g i s t e ra l l o c a t i o n s p i l lc o d es e n s i t i v e m e t h o dc a nb ei m p l e m e n t e de a s i l yi nr e g i s t e ra l l o c a t i o no fm o s tc o m p i l e r sw i t h o u ta n y d y n a m i ci n f o r m a t i o no rp r o f i l i n gf e e d b a c ks u p p o r t , a n do n l ys p i l lc o d e so fh o tf i l e sa r eu s e dt o e v a l u a t et h eo p t i m i z a t i o n s p i l lc o d ea n dh o tf u n c t i o ns e n s i t i v ei sam o r ea c c u r a t em e t h o d , w h i c hf o c u so nh o tf u n c t i o n sa n dt a k em es p i l lc o d e s e x e c u t i o nf r e q u e n c y 勰f i m e s sw i t ht h e e d g ep r o f i l i n g ss u p p o r t t h e s et w om e t h o d so n l ya n a l y z et h es p i l lc o d e sg e n e r a t e db yr e g i s t e r a l l o c a t i o na n dd on o tn e e dt oe x e c u t et h ep r o g r a m , t h ef e e d b a c ko f p r o f i l i n gc a nb ec a l c u l a t e d b e f o r et h em a c h i n el e a r n i n ga n db es h a r e db ye a c hg e n eo fg e n e t i ca l g o r i t h mb e c a u s et h e r e g i s t e ra l l o c a t i o nh a r d yc h a n g e st h ec o n t r o lf l o wg r a p h t h u so u rf a s tm a c h i n el e a r n i n g m e t h o d sa r em r c hf a s t e r 也a nm e t h o dn s e de x e c u t i o nt i m ea sf i t n e s s d e t a i l so fh o wt oi m p l e m e n to u rs p i i lc o d es e n s i t i v el e a r n i n ga n ds p i uc o d e & h o t f u n c t i o ns e n s i t i v el e a r n i n gb a s e do nm e t ao p t i m i z a t i o nt ot r a i nt h er e g i s t e ra l l o c a t i o no fo p e n n i r e s e a r c hc o m p i l e rf o rg o d s o n 2i sg i v e n t h e nt h ee x p e r i m e n tr e s u l to fc p u 2 0 0 0 c i n t ， w h i c hi sc o m p i l e dw i t ht h ec o m p i l e rw h o s er e g i s t e ra l l o c a t i o nh a st h eb e s tp r i o r i t yf u n c t i o n f o u n db yo u rf a s tm a c h i n el e a r n i n g , h a ss h o w no u rm e t h o d sc a ni m p r o v et h ep e r f o r m a n c eo f c p u 2 0 0 0 c i n ta n do u rl e a r n i n gt i m ei ss t i l lu n d e rl i m i t , o n l ya b o u t5h o u r s w ea l s op r o p o s e h o wt od e t e r m i n et h ei n i t i a lp o p u l a t i o ns i z ea n dt h en u m b e ro fg e n e r a t i o ni ne x p e r i e n c e e f f e c tm o d e l , am a c h i n el e a r n i n gr e s u l tb a s e dm o d e l ，i sg i v e nt oa n a l y z et h er e l a t i o n b e t w e e nt h es p e e d u po ff i t n e s sa n dt h es p e e d u po fp e r f o r m a n c ei m p r o v e m e n ta n dt r yt of e e d b a c ks o m ea p p l i c a t i o n s p e c i f i ci n f o r m a t i o nt oc o m p i l e rw r i t e r t h ee f f e c tv a l u eo fs p i l lc o d e s e n s i t i v el e a r n i n ga n d s p i l lc o d e & h o t f u n c t i o ns e n s i t i v el e a r n i n gf o rc p u 2 0 0 0 c i n ti sg i v e n a n dh e l p su st oa n a l y z et h e s et w om e t h o d sf u r t h e r t h eo n ei m p o r t a n tr e s u l ti ss p i l lc o d ea n d h o tf u n c t i o ns e n s i t i v el e a r n i n gi sm o r ea c c u r a t et h a ns p i l lc o d es e n s i t i v el e a r n i n gj n s ta sw e w a n t c d w e 仃yt ou s er o u g hs e t sb a s e dd a t am i n i n go fm a c h i n el e a r n i n gf o rc o m p i l e rd e v e l o p m e n t t oa n s w e rt h eq u e s t i o n h yt h i s r e s u l tp r i o r i 哆f u n c t i o nf o u n db ym a c h i n el e a r n i n gc a n i m p r o v et h ep e r f o r m a n c eo fg i v e np r o g r a m ? ”e a c hp r i o r i t yf u n c t i o na n dc o r r e s p o n d i n gf i t n e s s i so u rr e s e a r c ho b j e c t w eb u i l dt h ed e c i s i o nt a b l ew h o s ec o n d r i o na t t r i b u t ei st h ed e r i v a t i v eo f f a c t o r so fp r i o r i t yf u n c t i o na n dt a r g e ta t t r i b u t ei sf i t n e s s t h e nu s et h em e t h o d so fr o u g hs e t s ， s u c ha sr e l a t i v er e d u c t i o na n dr e l a t i v ee f f e c tc a l c u l a t i o n , w ec a nk n o ww h i c ha r et h ec o r e so f p r o f i t yf u n c t i o na n dw h i c ha r eu s e l e s sf o rp r i o r i t yf u n c t i o n f u r t h e r m o r ew ec a ns o r tt h e f u c t o r si ne f f e c tv a l u e w i t ht h e s ei n f o r m a t i o nw ec a ne x p l o i tm o r ec h a n c ef o ro p t i m i z a t i o n t u n i n g t os u mu p ，f a s tm a c h i n el e a r n i n gc a na c c e l e r a t et h em a c h i n el e a r n i n gf o rc o m p i l e r d e v e l o p m e n t t h ee x p e r i m e n tr e s u l to fs p i l lc o d es e n s i t i v el e a r n i n ga n ds p i l lc o d e & h o t f u n c t i o ns e n s i t i v el e a r n i n gf o rr e g i s t e ra l l o c a t i o nh a ss h o w n0 1 1 1 f a s tm e t h o d sc a nn o to n l y r e d u c et h et i m ec o s tb u ta l s oi m p r o v et h ep e r f o r m a n c eo fo b j e aa p p l i c a t i o ns i g n i f i c a n t l y o n t h eo t h e rh a n dw eh a v eb u i l te f f e c tm o d e lt oe v a l u a t et h em a c h i n el e a r n i n gr e s u l lb e c a u s e e f f e c tm o d e li so n l yac o a r s em o d e lc a no n l yw e i g ht h ew h o l em a c h i n el e a r n i n g , t h e nw eu s e r o u g hs e t sb a s e dd a t am i n i n gt of i n dt h es i g n i f i c a n c eo fe a c hf a c t o ro fp r i o r i t yf u n c t i o na n d w h i c ha r em o s ti m p o r t a n tf o rt h eo p t i m i z a t i o n i tc a nh e l pc o m p i l e rd e s i g n e rt ob u i l dab e t t e r m o d e l w eb e l i e v em a c h i n el e a r n i n gw i l lb e c o m em o r ea n dm o r eu s e f u lf o rc o m p i l e r d e v e l o p m e n tw h e nc o m p i l e rt u r n sm o r ea n dm o r ec o m p l e x k e y w o r d s ：c o m p i l e ra d a p t i o n , c o m p i l e ro p t i m i z a t i o n , r e g i s t e ra l l o c a t i o n ，f a s t m a c h i n el e a r n i n g ，e v a l u a t i o nm o d e l , r o u g hs e t s i v 图目录 图1 1 编译器组织结构。 图1 2o r c 编译器结构图 图1 3o r c 后端优化组织图。 图1 4o r c 移植到龙芯体系结构上所需修改 2 4 图1 5 龙芯编译器与g c c 针对c p u 2 0 0 0 整点性能的r a t i o 值比较 图1 6 龙芯编译器与c , c c 针对c p u 2 0 0 0 浮点性能的r a t i o 值比较 图2 1 通过插桩实现运行时多版本 7 7 图2 2 在不同执行次数下r e s i d 函数的执行时间和i p c 值1 4 图2 3 几个s p e c 例子在不同执行次数下的执行次数和运行时间1 5 图2 4 对代码片断进行插桩以识别稳定区域 图2 5r e s i d 函数每次迭代时的执行次数 图2 6 快速迭代编译获得的性能提升 图2 7 控制流与谓词 图2 8 图2 9 语法树的交叉和变异 m e t ao p t i m i z a t i o n 流程 。2 3 图2 1 0m e t ao p t i m i z a t i o n 对于构建超块学习结果 图2 1 1m e t a o p t i m i z a t i o n 对于寄存器分配学习结果 图2 1 2m e t ao p t i m i z a t i o n 对于数据预取学习结果 图3 1 表调度算法 图3 2 图着色寄存器分配框架 图3 3 基于静态分析的快速机器学习框架 图3 4 结合热点区域的基于静态分析的快速机器学习 图3 5 结合热点区域的结合p r o f i l i n g 的静态分析的快速机器学习 图3 6 溢出代码敏感的机器学习框架。4 1 i x 签 拍 拍 拍 勉 孙 卯 粥 图目录 图3 7 溢出代码与热函数敏感的机器学习 图3 8 o r c 中e d g ep r o f d i n g 示意 图4 1f i n c h 代码结构图 图4 2 图4 3 o r c 与机器学习函数库调用关系 f a n a l y z e r 图形化输出 4 9 5 5 图4 4 溢出代码敏感的机器学习不同代所耗费时间 5 9 图4 5 溢出代码与热函数敏感的机器学习不同代所耗费时间 图4 6 溢出代码敏感的机器学习：初始种群1 0 ，遗传5 代 图4 7 溢出代码敏感的机器学习：初始种群2 5 ，遗传5 代 图4 8 溢出代码敏感的机器学习：初始种群5 0 ，迭代7 代 。6 6 图4 9 溢出代码敏感的机器学习：初始种群7 5 ，迭代5 代 图4 1 0 溢出代码敏感的机器学习# 初始种群1 0 0 ，迭代5 代。 图4 1 1 溢出代码与热函数敏感的机器学习：初始种群5 0 ，遗传5 代。 图4 1 2 基于静态分析机器学习对c p u 2 0 0 0 c i n t 性能影响。 图5 1 基于静态分析的机器学习适应值与性能提升对比 图6 1 基于粗糙集的机器学习信息挖掘框架图 x 砸 醯 醯 醯 田 的 订 记 表2 1 测试例子运行行为统计 表目录 表2 2m e t ao p t i m i z a t i o n 可用运算符 表3 1c h a i t i n 、b f i g g s 和g e o r g e 方法的分配代价明细表 表4 1o r c 动态库及其相关优化。 表4 2b e 的m a k e f i l e 修改 表4 3 c g 的m a k e f i l e 修改 表4 4 表4 5 机器运行环境。 部分机器学习配置。 表4 6 交叉编译平台配置 1 8 2 4 3 9 5 4 表4 7c t u 2 0 0 0 c l n t 热点文件与热点函数 表6 1 机器学习第一代和最后一代生成的中间文件示例 表6 2 可被采集的合法运算符 表6 3 决策表样例 表6 4 条件属性相对决策属性的约简算法。 表6 5 求条件属性相对决策属性的核的算法 表6 6 计算条件属性重要性算法。 x l 1 0 0 声明 我声明本论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，本论文中不 包含其他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 作者签名：雪。1 查芥冬日期：2 多占2 论文版权使用授权书 本人授权中国科学院计算技术研究所可以保留并向国家有关部门或机 构送交本论文的复印件和电子文档，允许本论文被查阅和借阅，可以将本 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编本论文。 ( 保密论文在解密后适用本授权书。) 作者签名：刍l 蚕彳袒签名：j 红托反e t 其, i ：名扩矿莎2 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 1 编译器组织结构 一般如图1 1 所示，一个编译器可分为三部分： 前端( 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 ) 。由于源语言结构的差异，自口端可能一次或多次扫描代码。这种翻译 主要包括词法分析，语法分析和语义制导翻译等步骤。编译时刻错误检查通常在这一阶 段进行。一个编译器通常支持多种语言，如f o r t r a n 、c 、c + + 等，所以它就有多个前 端。理想情况下前端仅与源语言相关而与目标机器无关。 中端( m i d d l ee n d ) ：中端由一系列优化器组成。每个优化器对中间表示做特定类型的 转换( 或叫做优化) 。每种优化都要在不丧失正确性的前提下尽量提高最终代码的质量， 如果能做到最优则更好。理想情况下，中端应做到与源语言和目标机器均无关。这类优 化可分为全局优化和过程间优化。全局优化指在一个函数( 过程) 的范围内进行的优化， 如强度削弱、循环不变量外提、常数传播、公共子表达式删除等。过程间优化指跨越函 数边界，从多个函数中提取信息所做的优化。如死代码删除、i n l i n i n g 、把间接函数调用 变为直接函数调用等。 后端( b a c k e n d ) ：后端负责把中间表示翻译成与特定机器相对的目标代码。我们也把 它称作代码生成( c o d eg e n e r a t i o n ，c g ) 。通常包括这样几步：指令选择、指令调度、寄 存器分配和代码发射。后端通常与源语言无关而与目标机器有关。这种方法把不同类型 的问题有效的划分开来，简化了每部分的开发与维护，更重要的是提高了代码的可重用 性。例如象上面提到的，多个前端可以共享同一个中端和后端。 可见在编译器的中端和后端有大量的优化，通常我们并不能保证这些优化能对任何 2 第一章引占 例子都是适用的，故编译器开发者常常会构建各种各样的启发式算法来描述目标问题。 并且当编译器移植到其它平台上时，构建的启发式算法也需要进行调整。此外，各个编 译优化之间还存在相互影响。可见，对编译优化适应性进行研究是整个编译器开发中的 重要部分。 1 20 f i c 编译器 我们的工作基于o r c ( o p e nr e s e a r c hc o m p i l e 0 编译器：1 ，在此对o r e 结构做一简单 介绍。o r c 是中国科学院计算技术研究所与i n t e l 公司合作开发的一个面向i n t e l i 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 e 在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 w s p r o 移植来的。o r c 编译器追求的是为国际科学研究的前沿提供 先进的平台和优越的性能。 2 0 0 1 年1 2 月通过科学院组织的专家技术鉴定，鉴定意见称：“o r c 在开放源码 的i a - 6 4 编译系统的健壮性、灵活性和性能方面达到国际领先水平。”o r c 通过了c p u 性能基准测试程序包一c p u 2 0 0 0 的测试，性能比此前最先进的开放源码编译器p r 0 6 4 提高2 0 以上。o r c 具备良好的模块结构、健壮性、可配置性和可扩展性，具有作为 研究平台和应用软件开发工具的双重价值。在诸多关键技术上取得了创新性成果，两项 专利申请已被美国专利与商标局受理。我国要研制有自主知识产权的c p u ，就必须有自 己的编译器。o r c 可方便地移植到其它的平台上。利用编译技术可降低硬件设计的难度， 并为实现低功耗、安全等特殊需求提供支持。o r c 以开放源码的方式向全社会公开，为 其他从事相关研究的单位或人员提供一个高水准的工作平台，大大推动相关的研究。多 所国内外著名大学和公司基于o r c 开展了研究开发工作。o r c1 0 版于2 0 0 2 年1 月发 布，1 1 版于2 0 0 2 年7 月发布，o r c 2 0 版于2 0 0 3 年1 月发表，累计已有两万多人次下 载。 图1 2 是o r c 前端、中端和后端划分图。o r e 自口端支持四种编程语占：c 、c + + 、 f o m a n 7 7 和f o m a n 9 0 。o r c 的中间表示称为w h i r l 。w h i r l 是一种抽象语法树。 为了能让各种编译优化在最适合的中间表示上进行，w h i r l 采取了层次结构，从最高 层w h i r l 到最低层w h i r l 9 共分为五层。每层在语义上相同，但每降低一层，就要 丢失一些源程序的信息。相邻层之间的转换通过调用各种l o w e r e r 来完成，这些l 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 p n e s t e do p t i m i z a t i o n , l n 以及标量全局优化( 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 ) 。 l h t t p ： q ) f o r c s o u r c c f o r g * n c t 2 h t t w p r 0 6 4 s o u r c e f o r g e a m e t 3 苹f 机器学习的编译优化适应性研究 t a i t 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 的部分冗 余消除和复写传播等。 v h o r v l 2 c g c g lv e r v h i 口h l w h i r r 卜g h w h i r l 1 m ；dv v h l r l 1 l o ww h i r l i t v e r y 1 0 ww h i r l i c g i r l o w e r a g g r e g a t e s u n , d l 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 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 i g hl e v e lc o n t r o lf l o w l o w e r l 0 l o w e rb i 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 , o h s - l o w e ri n t r 扩t s i c st oc a h s g e n o r o t os i m u l a t i o nc x d d of o ra u a a hd a t am a p p e dt os e 铆n e n t s l o w e ri o a d s s t o r e st of i n a il 甜f n e x p u s e 毛 | es 州u 嚣1 1 e $ f ，f c o n s t a n t sa r t 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 x p 0 3 s t a “cl i n kf o rn e $ t e d p r o c e d u r e s 图1 2o r c 编译器结构图 图1 3 是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 指令生成，循环优化( 软流水和 循环展开) ，全局指令调度，寄存器分配，局部指令调度和代码发射。 4 d 一 砖一 耐iil丰芏 b o r c 编译器中的部分优化是针对i a 6 4 体系结构，需要特定的硬件支持。如i f c o n v e r s i o n 需要谓词寄存器支持。投机操作需要投机指令支持等。而在其后介绍的针对 龙芯体系结构对o r c 移植，我们会舍弃这些特定优化，并针对龙芯体系结构对编译器 常用优化进行调试和优化，以期得到更好的性能。 1 3 龙芯编译器