（计算机系统结构专业论文）龙芯Ⅰ编译器中的指令调度相关优化.pdfVIP

摘要 摘要 指令调度相关的优化是现代编译器后端的重要组成部分。本文就通用处理器 龙芯i 的编译器中机器模型、静态指令调度、和全局延迟槽调度等与指令调度相 关的问题进行了研究。 机器模型有助于提高编译器的灵活性和可移植性，它把后端优化所需要的机 器信息集中在一起并转换为后端可用的形式。本文首先介绍了现有的几种主流编 译器的机器模型，包括g c c ，p r 0 6 4 等。然后详细的分析了o r cf o p e nr e s e a r c h c o m p i e r ) 的机器模型，并通过龙芯i 编译器机器模型的实际移植过程探讨了机器 模型移植的般过程和原则。 静态指令调度决定指令执行顺序，屏蔽指令间由于依赖关系而产生的延迟， 从而提高了指令的并行度。本文首先分析了硬件动态调度和静态指令调度之间的 关系，说明了静态指令调度的必要性，然后介绍了指令调度在龙芯i 编译器中的 具体实现，最后给出了实验结果以说明指令调度的实际效果。 出于龙芯i 处理器中采用了延迟槽来减少由于分支而造成的延迟，因此优化 编译器如何高效的利用延迟槽对于性能来说十分重要。本文对延迟槽调度中调度 范围，所处编译阶段等问题进行了分析，对全局延迟槽调度可能出现的冲突及候 选指令的区域进行了研究，提出了一种全局延迟槽调度算法，并用实验结果证明 它有较好的性能和健壮性。 关键词：编译龙芯i 处理器机器模型静态指令调度全局延迟槽调度 a b s t r a c t o p t i m i z e dt e c h n i q u e o fi n s t r u c t i o ns c h e d u l i n go ng o d s o n - i c o m p i l e r j i a n gy i ( 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 db yw u c h e n g y o n g a b s t r a c t i n s t r u c t i o ns c h e d u l i n gi sav e r yi m p o r t a n tp h a s ei nt h eb a c ke n do fa no p t i m i z e d c o m p i l e r t h i st h e s i s i sb a s e do nt h ea u t h o r sw o r ki nd e v e l o p i n ga no p t i m i z i n g c o m p i l e rf o rt h eg o d s o n ip r o c e s s o r , w h i c hi s ag e n e r a lp u r p o s ep r o c e s s o rd e s i g n e d b yt h e i n s t i t u t eo fc o m p u t i n gt e c h n o l o g ya n dd i s c u s s e st h r e ei s s u e sr e l a t e dt o i n s t r u c t i o ns c h e d u l i n g ：t h em a c h i n em o d e l m es t a t i ci n s t r u c t i o ns c h e d u l i n ga n dt h e g l o b a ld e l a y s l o ts c h e d u l i n g m a c h i n em o d e li sd e s i g n e dt oi m p r o v et h ef l e x i b i l i t ya n dp o r t a b i l i t yo f c o m p i l e r i t e n c a p s u l a t e st h ei n f o r m a t i o no fh a r d w a r ea n dp r o v i d e sq u e r yi n t e r f a c e s t oo t h e r c o m p o n e n t so ft h eb a c ke n do fa nc o m p i l e r w ed i s c u s s e ds e v e r a lk i n d so f m a c h i n e m o d e l su s e di nc o m p i l e r sl i k eg c ca n dp r 0 6 4 t t i e nw ea n a l y z et h em a c h i n em o d e l o f t h eo p e nr e s e a r c hc o m p i l e r ( o r c ) f i n a l l yw ed e s c r i b et h em e t h o dw eu s et op o r t t h em a c h i n em o d e lo f o r cf o rt h eg o d s o n ip r o c e s s o r s t a t i ci n s t r u c t i o ns c h e d u l i n gd e c i d e st h ee x e c u t i o no r d e ro fi n s t r u c t i o n sa n d i m p r o v e st h ei 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 yr e d u c i n gs t a l l c a u s e db yd e p e n d e n c e s w ed i s c u s st h ei n t e r a c t i o n sb e t w e e ns t a t i ca n dd y n a m i ci n s t r u c t i o ns c h e d u l i n ga n d s h o wt h a ts t a t i ci n s t r u c t i o ns c h e d u l i n gi sb e n e f i c i a le v e nt h eh a r d w a r eh a sd y n a m i c s c h e d u l i n g w ea l s od e s c r i b et h ef r a m e w o r ko f i n s t r u c t i o ns c h e d u l i n gi no u r c o m p i l e r a n dp r e s e n te x p e r i m e n t a lr e s u l t st os h o wi t sp e r f o r m a n c e g o d s o n - ip r o c e s s o ru s e sd e l a ys l o t st or e d u c et h eb r a n c hl a t e n c ya n dp e n a l t yo f b r a n c hm i s p r e d i c t i o n s i ti s i m p o r t a n tf o ro u rc o m p i l e rt ot a k ea d v a n t a g eo fd e l a y s l o t se f f e c t i v e l y w ea n a l y z et h es c o p eo f d e l a ys l o ts c h e d u l i n g p r e s e n tam e t h o d t o s o l v ep o s s i b l ec o n f l i c t si ng l o b a ls c h e d u l i n go f d e l a ys l o t sa n di m p r o v e t h es e l e c t i o n o f s c h e d u l i n gc a n d i d a t e s t h e nw cp r e s e n taa l g o r i t h mo fg l o b a ld e l a ys l o ts c h e d u l i n g e x p e r i m e n t r e s u l t ss h o wt h a to u r a p p r o a c hi se f f e c t i v ea n d r o b u s t k e yw o r d ：c o m p i l e r , g o d s o n - ip r o c e s s o r , m a c h i n em o d e l ，s t a t i c i n s t r u c t i o n s c h e d u l i n g ，g l o b a ld e l a ys l o ts c h e d u l i n g 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作 及取得的研究成果。就我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工 作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。 作者签名：荔襄 关于论文使用授权的说明 日期：泐伊f 习 中国科学院计算技术研究所有权处理、保留送交论文的复印件， 允许论文被查阅和借阅；并可以公布论文的全部或部分内容，可以采 用影印、缩印或其它复制手段保存该论文。 作者签名：蒋褒导师签名：粜z 吻日期渺“7 引言 第一章引言 本篇论文内容的基础是作者在龙芯i 编译器中的工作。龙芯i 微处理器是中 科院计算所自主开发的一款兼容m i p s 体系结构的通用处理器，它兼容m i p si i i 的大多数指令，并采用的单发射超流水结构。在处理器的设计中，它采用了目前 微处理器设计中的一些先进技术，包括t o m a s u l o 动态调度算法、寄存器换名、 转移预测和推测执行、精确例外处理、6 4 位的浮点运算部件。除此之外，它还 实现了模块化的系统结构以及硬件支持的系统安全设计等技术 1 】。 作者所在的计算所先进编译组针对这款芯片开发了龙芯i 编译器。作者在这 个编译器的开发过程当中承担了包括机器模型，指令调度和全局延迟槽调度等部 分的移植和实现，并以此为基础就一些更深层次的问题进行了探讨。本论文就是 基于作者在龙芯i 编译器上的工作撰写的。 1 1 龙芯i 编译器框架简介 龙芯i 编译器是由o r c 编译器移植而来。o r c ( o p e nr e s e a r c hc o m p i l e r ) 是计算所编译组和i n t e l 公司微处理器技术实验室合作的一个项目，目的是在新 出现的i a 一6 4 体系结构上为学术界提供一个开放源码的公共编译研究平台。而 o r c 同时具有的良好的模块结构以及灵活性和健壮性，使得它有了作为研究平 台和应用软件开发工具的双重价值。基于以上考虑，我们选择了o r c 作为我们 移植和优化的基础，在此基础上，由于目标机的不同，我们去掉一些i a 6 4 相 关优化而加入一些和龙芯i 处理器相关的优化。 和大部分常见的编译器一样，龙芯i 编译器的结构分为前端( f r o n te n d ) ，中 端( m i d d l ee n d ) 和后端( b a c k e n d ) ，前端的工作主要依赖于源语言而与目标机 器无关。通常这些阶段包括词法分析，语法分析，中间代码生成等，某些优化工 作也可以在前端做，包括与前端每个阶段相关的出错处理工作和符号表管理工 作，由于前端的工作，编译器的其他部分可以不考虑来自何种语言的源代码。而 中端介于前端和后端之间，在我们的编译器当中，中端的中闻表示即工作对象是 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 的第三层开始，就 有一些诸如传参寄存器等机器相关信息进入中间表示当中。而后端工作主要指那 些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代 码生成，其中包括了诸如指令调度，寄存器分配等优化，其中有的优化还需要特 定体系结构的支持，其流程如图1 1 所示。 龙芯l 编译器中的指令调度相关优化 1 1 枫器模型 r e g i o n 构造 + 循环优化( 展开) 全局指令调度 寄存器分配 局部指令调度 图1 1 龙芯i 编译器后端优化主要流程 我们提到在编译器当中，后端优化是依赖于目标机的，也就是说各个优化部 分需要考虑不同机器的不同特性，从而有不同的处理方式。过去的编译器将各种 机器信息都散落在代码中间，而现代的编译器为了提高灵活性和可移植性，将这 一些游离在各个部分的机器信息单独形成一个部分，称作机器模型。也就是说如 果编译器需要移植到不同的机器上，只需简单的改动相应信息，则可使编译器继 续使用。 图1 2 优化和机器模型的关系图 这样其他优化部分当需要考虑具体的机器信息时，则利用统一的接口访问机 器模型，获得硬件信息。这样既可以使访问简单化，还可以保证不鼠优化部分都 获得了一致的结果，并且任何修改也能反应到其他各个优化部分。采用这种设计 的另一个好处是可以对机器信息的使用者隐藏机器信息文件生成的细节，符合软 件工程学中模块化的思想。 本文第二章将首先描述现有的几种机器模型，然后通过阐述龙芯i 编译器机 器模型的实际移植过程揭示机器模型移植的一般过程和原则。 引言 1 3 静态指令调度 丌发指令级并行性是实现高性能计算的重要途径。而指令调度是编译器实现 指令级并行的主要手段，它根据指令之间的依赖关系和目标体系结构的资源决定 指令执行顺序，从而屏蔽指令间由于依赖关系而产生的延迟，最大限度的发挥处 理器的功能部件的作用，提高指令的并行度。特别是体系结构中大多设计有多个 功能部件和比较深的流水线级数，那么对于代码中并行度的进步发掘更显重 要。 相比近年出现的v l i w 体系结构，由于龙芯i 芯片采用的是兼容m i p s 的结 构，采用t o m a s u l o 算法乱序执行的机制，因此也有分析指令问依赖关系，调整 指令顺序的功能。那么首先我们必须回答一个很现实的问题：静态指令调度是否 还有必要? 本文第三章首先分析了硬件动态调度和我们的静念指令调度之间的 关系，说明了静态指令调度的必要性，然后介绍了指令调度在龙芯i 编译器中的 具体实现，最后给出了对c p u 2 0 0 0 测试包的实测结果，以说明指令调度的实际 效果。 1 4 全局延迟槽调度 龙芯i 处理器属于精简指令集( r i s c ) 一类的体系结构，在采用这种体系 结构的流水处理器中，分支指令是提高性能的一个重要障碍，这是因为从程序上 看，其下一条指令的地址将被分支指令的结果所决定，但是这个结果需要在分支 指令执行到比较后的流水级时才能产生，中间的延迟会造成流水线停顿等待分支 结果，从而直接影响后续指令序列的执行，降低指令并行度 2 。解决此类问题 的办法包括分支预测和投机执行，分支预测指的是根据分支指令历史跳转的方向 来推测当前跳转的方向。投机执行就是根据这个推测在实际结果还没有真正出来 的时候执行后续指令，如果猜测错误，再利用恢复机制恢复到原始状态。延迟槽 结构也是一个解决此类问题的办法，延迟槽位于分支指令的后面，罩面可以放上 不受分支指令结果影响的指令，它的目的是在等待分支指令结果的时候，流水线 不至于停顿。延迟槽的使用是由编译器决定的，因此，如何让延迟槽得到尽量的 填充以及如何将延迟槽调度融入到整个编译优化的框架中，成为获得高性能的编 译器的一个重要因素。 本文第四章主要对全局和局部延迟槽调度进行了比较，并在整个编译器的框 架内讨论了延迟槽调度和其他优化阶段的关系从而确定了它在编译器优化过程 中的位置。钉对前人关于全局延迟槽调度的分类，我们给出了具体的填充办法， 并讨论了可能出现的冲突和预防措施。然后，为了减少编译时间以及降低实现难 度，我们还利用编译器中已有优化，对候选指令的区域进行了改进。最后，我们 设计并实现了一个全局延迟槽调度算法。 龙芯i 编译器中的指令调度相关优化 1 5 论文的组织 本文的组织是这样的： 第一章是引言，它将对整个论文结构和内容做一个简介。 第二章将介绍机器模型的相关背景以及龙芯i 编译器相关部分的移植。 第三章的内容是介绍在硬件存在动态调度情况下，编译器静态指令调度的动 机和静态指令调度在龙芯i 编译器中的的实现，以及最后的实验结果。 第四章中我们给出了全局延迟槽调度的必要性，完成了设计与实现，并在此 基础上进行了实验和分析。 4 机器模型 第二章机器模型 机器模型是编译器的基础设施之一。出于对提高编译器健壮性、灵活性的考 虑，编译器的各种优化应基于机器模型访问机器信息，而不应该把不同的机器信 息散落在编译器不同部分。编译器通过机器模型封装信息，这也是遵循软件工程 中数据和代码的分离的原则，从而达到提高代码重用性，缩短编译器的开发周期 的目的。 2 1 现有几种机器模型简介 下面我们将列举几种比较典型的机器模型设计。 21 1g g c 的机器模型 g c c 的机器模型主要包括两部分，部分为描述目标机各种参数的宏定义文 件m a c h i n e h ，另一部分为描述目标机指令集的机器描述文件m a c h i n e m d 。f 3 】宏 定义文件主要规定了包括存储器编址信息，数据对象存储约定，寄存器性质，调 用约定等内容。而后者由采用r t l ( r e g i s t e rt r a n s f e rl a n g u a g e ，g c c 的中间表 示) 外部语法形式书写的r t x 表达式组成，其内容主要包括： 1 ) 目标机指令集的有关属性，如分类，数据类型，长度，延迟槽属性，功 能部件等。 2 ) 指令样板，描述目标机所支持的每一条指令相应的r t l 指令形式和汇编 输出格式。 3 ) 指令样板的补充信息，指出可以进行与目标相关的优化动作及相应的 r t l 指令形式。 这中间的指令样板有着两个重要的作用：用于构造中间语言r t l 中的指令和 用于确定汇编码的输出格式，这是支持多平台思想得以实现的核心部分。 从上面的内容我们可以看出这样的机器描述文件是一个普通的正文文件，为 了能让编译器方便查询，g c c 一方面在编译内部设计了一套专门的函数和数据 结构作为编译主体与机器描述之间的接口，编译主体通过这些函数和数据结构获 得机器模型的内容，另一方面，在编译之外设计了一套独立的，专用的机器描述 处理程序，这套程序将正文形式的机器描述转换成含有接口所需数据结构与函数 的c 源程序。这些c 源程序与g c c 编译的其他源程序一起构成了完整的编译程 序集合，其处理程序如图所示： 燕芯i 编译嚣中的指令调度相关优化 图2 一lg c c 机器描述处理程序 作为多语种多平台编译系统的典型例子，g - c c 的兼容性和可移植性得到公 认，在此当中，灵活的机器模型所起的作用是非常巨大的。 2 1 2p r 0 6 4 的机器模型 p r 0 6 4 是s g i 升发的开放源码6 4 位编译器，其目标体系结构是i a 一6 4 。p r 0 6 4 本身的机器模型部分根据硬件信息的进行分类，如指令格式，寄存器信息，调用 约定等，将同一类信息放在信息文件中，并调用相应的生成函数，从而生成需要 含有数据结构、数据表、和函数接口的头文件和c 文件。这些被生成的函数和 数据将会被编译器其他部分调用和访问。我们可以从图中看出简单的过程： i s a “xf ，1i g a _ g e nr _ 1 o p e o d e 图2 2p r 0 6 4 机器模型处理程序图 但是我们看到p r 0 6 4 中的生成器实际上也是大量的c 文件，而硬件信息则是 直接写在代码中。这样如果需要改动某种信息，我们需要找到特定的文件和特定 的地方才能定位出修改处。因此这种机器模型的生成方式给移植带来了不便，同 时p r 0 6 4 存在部分硬件信息直接写在优化部分的代码中，例如旁路延迟信息，由 于其难咀统一的特性，p r 0 6 4 不能自动生成，而这一部分信息是很有可能更改的， 这就需要去浩瀚的编译器代码中寻找并且更改。 因此这一类的机器模型灵活性和移植性都略显不足，这是与当初编译器设计 机器模型 的初衷有关的，相比起来，g c c 在设计之初就有支持多平台的要求，而p r 0 6 4 的前身是s g i 公司面向m i p s 的商用编译器m i p s p r o ，相对于灵活性，它更多的 注重的是性能等方面的考虑。 2 2 龙芯i 编译器机器模型 我们曾经在前面提到，机器模型的作用就是为编译器提供机器相关信息，以 便编译器的其他阶段可以依此生成机器相关代码或者进行机器相关的优化。比如 在编译器的指令选择阶断，这里编译器需要做的是把低层的中间语言w h i r l 转 换成更为低层，也就是更为贴近机器指令格式的中间表示c g i r ，在这个过程当 中，就需要机器模型提供机器指令集中所有指令的格式信息，又如在指令调度阶 段，每条指令的发射延迟和结果延迟是指令如何进行重排的重要依据，我们将在 第三章中揭示，如果延迟的信息给的不准确，将会给指令调度的最终结果带来很 大的负面影响， 所以，我们构造机器模型，首先就要熟悉目标机的微体系结构，并提取当中 编译需要的信息。 2 2 1 龙芯i 体系结构简介 龙芯i 微处理器采用了自行设计的基于操作队列复用的动态流水线结构 1 ， 其中包括： 流水级：定点运算7 级( 取指、译码、重命名、发射、执行、写回、 提交) ；浮点运算的执行阶段为3 级，因此一共9 级。 1 个取指部件、1 个译码部件，系统接口部件； 一操作队列内含8 项，通用寄存器及浮点寄存器各3 2 个。 一1 个定点a n 逻辑运算部件，1 个定点乘除部件，1 个全流水的浮点加 部件和1 个全流水的浮点乘除部件，1 个访存部件： 一4 8 项t l b ，每项两页，页大小在4 k b - 4 m b 之间； 一分离的指令c a c h e 和数据c a c h e ，各为8 k b ，动态索引，二路组相联； 在指令集方面，龙芯i 兼容了大部分m i p s i i 的指令以及一部分m i p s i i i 的指 令，目前没有实现的指令如表2 1 所示： 表2 一l 龙芯i 中没有实现的指令 指令m i p s 指令集 l w l ，l w r ，s w l ，s w r i i s q r t i l 6 4 位定点指令 i l l 6 4 位访存指令( 除了l d c l 与s d c l ) i i i 6 4 位c p 0 指令 i i i 龙芯i 编译器中的指令调度相关优化 在执行上述指令代码在g o d s o n - 1 处理器中将产生保留指令例外( e x c c o d e = 1 0 ) 出于性能的考虑，我们还必须了解每类指令的各种延迟，如表2 2 所示 表2 2 龙芯i 指令的延迟 指令分类发射延迟( 最小)结果延迟( 最小) a l u 指令 l2 ( 除乘除之外的所有定点指令) 定点乘 i3 定点除 3 23 3 浮点a l u 指令 1 4 ( 浮点加，定点浮点 ( 包括浮点加、比较、分支、及定点浮点转换) 转换)2 ( 其他指令) 浮点乘 l5 浮点除2 3 ( 单精度)2 4 ( 单精度) 5 5 ( 双精度)5 6 ( 双精度) 访存指令 l3 ( c a c h e 命中) c p 0 指令 13 a b i ( a p p l i c a t i o nb i n a r yi n t e r f a c e ) 也是机器模型需要描述的一个重要部分， 其中包括函数调用中参数的传递规则以及一些特殊寄存器的使用规定等，龙芯i 处理器出于对m i p s 体系结构的兼容，采用的是0 3 2 的a b i ，这是一种标准的a b i ， 在这里就不再赘述，具体的表述可以参见 ( s e em i p sr u n ) ) 【1 8 】一书。 2 2 2o r c 编译器机器模型简介 龙芯i 编译器的机器模型框架大体继承的是0 r c 的机器模型，因此我们在 这里简单介绍o r c 编译器的机器模型，相对于o r c 的前身p r 0 6 4 来说，在机器 模型方面，它维持了原来的访问接口不变f 4 】，但是调整了机器描述的格式和生 成函数，使得可移植性和灵活性有了大幅提高。 首先，它的机器描述文件叫做k n o b s f i l e ，在机器信息描述的格式上，它采取 了一种可读性更强，语法更为简单的描述方式，现列举如下： 1 t y p ee n u mt y p en a m e = e n n m ( i t e m i ，i t e m 2 ，i t e m n ) ，这类似于高级语言的 枚举类型，用来界定一个特定的集合，比：t y p er e g c l a s s = e n u m ( i n t e g e r ，f l o a t ，p r e d i c a t e ，b r a n c h ，a p p l i c a t i o n ，c o n t r 0 1 ) 就枚举了所有寄 存器的类型。 2 a r r a y _ _ n a m e ：a r r a y 【i n d e x _ t y p e 】o f i t e m _ t y p e ，这类似于高级语言的数组， 它的主要目的是完成一组被描述的对象集合到一种性质的映射，而且这种 性质描述相对于对象来说是唯一的。比如：b i d c o m ew i d t h ：a r r a y f b i d c o m et 】o f i n t ，它定义了一个数组b i d c o m rw i d t h ，它的作用是把指令 机器模型 中的某个盛放操作的槽映射到长度上面，在这里这个长度显然相对于每个 槽来说是唯一的。 3 a t t r i b u t en a m e + = “a t t r i b u t es t r i n g l ，a t t r i b u t e s t r i n 9 2 ”；这种描述方式适用 于表示一组被描述的对象集合到多种性质的映射，而且这种性质描述相对 于对象来说是唯一的。比如说：o p c o d e + = ” ， ， ， ， ， ， ， , 这就是用来描述一条指令的操作码，助记 符，操作数格式表中的索引等等多种性质。 4 b i t m a s ka r r a y ：a r r a y 【a r r a yi n d e x 】o f b i t m a s k ( e n u m e r a t i o n _ t y p e ) ，这是第 二种语法现象的一种扩展模式，它也是用来完成一组被描述的对象集合到 一种性质的映射，而且这种性质描述相对于对象来说是不唯一的。如果采 用这种语法形式描述，生成层会使用到比特位来记录属性的情况，这样能 够节省建立期间的空间和加快判断是否具有某一属性的速度。比如： u n i t p r o p ：a r r a y 【s t r i n g 】o fb i t m a s k ( e u n _ t ) 它描述的是指令到可发射该条 指令的功能部件的映射，由于一条指令可能在不同的功能部件上都能发 射，所以我们采用这种方式。 5 v a r i a b l ed e f i n i t i o n ：v a r i a b l e ：= ，这是一个简单的一一对应关系，比如 说：p r o c e s s o r _ n a m e ：= ”p r o c e s s o r * * * ”；表示我们的目标处理器是 p r o c e s s o r + + + 。 依托于这几种简单的语法所代表的描述方式，整个k n o b s f i l e 文件组成了一个 以指令和存储结构为中心的层次描述结构，图2 3 和图2 4 给出了这样的一个 结构。 图2 3 以指令为中心的层次结构 龙芯i 编译器中的指令调度相关优化 图2 4 以存储结构为中心的层次结构 在图中，箭头的尾端是被描述的对象，顶端表示的是描述的属性，箭头上方 的数字对应我们刚才给出的几种语法现象类别，代表描述的方式。由于属性本身 又有可能被更具体的属性描述，层次结构就这样形成了，在图2 3 中有一些菱 形的属性，这表示它还被更多的属性所描述，只是限于篇幅，没有办法一一列举， 如寄存器就还包括一些具体的寄存器的属性，包括大小，个数以及a b i 当中和 寄存器相关的一些内容。 和2 1 中所描述的几个编译器的机器模型一样，我们的机器模型最终也要生 成一些包含机器信息的c 文件，所以在机器描述文件和最终生成的机器信息文 件中间有一个生成的过程，这个过程可以用图2 5 表示，在图中，k a p l 分析层， k a p i i a 6 4 层和e k a p i 层指的是一些用来解析k n o b s f i l e 当中信息的，不同层次 的应用程序接口。 k a p l 分析层有一个类似于语法分析器的功能，这时候提供的接口是与信息 文件中具体被描述对象或者描述的性质无关的，而k a p i i a 6 4 层和e k a p i 层访 问k a p l 分析层的接口，根据具体被描述的对象和描述的性质生成相关的接口。 在生成层中，信息按类划分，如指令操作码，指令格式等，每类信息都有自己的 生成函数，它们利用k a p i i a 6 4 层和e k a p i 层的接口最终生成所谓外部机器描 述，也就是编译器可用的机器信息。 i o 机器模型 图2 5 机器描述实现模型 下面我们用一个实际例子来说明各层的作用以及相互的关系： 我们上面提到的操作与操作码的关系在k n o b s f i l e 当中有所描述，而且用的是 第三种描述方法，具体是o p c o d e 忙” ， ”，为了 把它解析成编译器可用的格式，首先，k a p i 层提供一个接口 k a p ia t t r i b u t e 4 i n d e x ，它的作用是完成操作到后面描述属性的一大段字符串的映 射，这个接口是普适于所有用第三种描述方法描述的机器信息的。 在这个接口之上，e k a p i 层提供了一个接口e k a p io p n a m e 4 i d ，它通过对 刚才所述的k a p i 层接口的调用，提供了一个操作在k o n b s f i l e 中的顺序索引到操 作码的映射，这一个接口是仅适用于k n o b s f i l e 中特定内容的。在这里，e k a p i 层与k a p i i a 6 4 层的功能是相近的，只不过e k a p i 层表示的是o r c 以及龙蕊编 译器当中相对原始版本增加的接口。 按下来，生成层函数o p c o d eg e n e r a t o r 调用e k a p i 层提供的接口，生成所 有操作的操作码列表，并完成了操作到操作码映射的接口t o pn a m e 。至此，我 们完成了这部分信息的解析。 从信息解析的过程，我们可以看出，访问机器描述文件的底层接口被k a p l 分析层封装起来了，由于这一层不与实际信息的内容有关，针对各种不同类别信 息的高层可以共同调用k a p l 分析层中的接口，这样不但最大限度的减少了冗余 的接口，而且使得安全性和灵活性大大提高。 2 2 3 机器模型的移植 由于机器模型需要随时适应目标机变化升级的需求，因此它的移植和升级是 一个非常重要的过程，我们从o r c 中面向i t a n i u m 机器的机器模型移植到龙芯i 编译器就完成了这样一个过程。 从机器描述的实现模型我们可以看出，机器信息从k o n b s f i l e 当中的内部形式 到编译器可用的外部形式分四个层次，在移植过程当中，为了得到合适的机器信 龙芯i 编译器中的指令调度相关优化 息外部形式，这四个层次都要做相应的改动以适应新的要求。下面我们将分别阐 述各层改动的原则： 1 ) 机器描述文件即k n o b s f i l e 。从上面的描述我们可以得到，k n o b s f i l e 是按 照特定的语法规则对目标机体系结构的描述，因此，体系结构的变化将会直接影 响到k o n b s f i l e 的内容。在图2 3 和图2 4 当中我们已经把所有的k n o b s f i l e 机 器信息组织成个树状的层次结构，在这个结构当中，我们可以形象的看到，父 子结点的关系就是被描述和描述的关系，因此，我们应该首先确定微体系结构当 中有哪些信息发生了变化，如果说靠近根结点的结点发生了变化，那么它的子结 点的描述就很有可能发生变化，例如在我们的移植过程当中，从i t a n i u m 到龙芯 i ，指令集已经发生了很大的变化，也就是对应到那张层次图中，根结点发生了 变化，因此，包括指令操作码，指令性质列举，功能部件对应情况，寄存器的描 述，a b i 等等的几乎所有的信息都会有相应的变化。 其中，这些信息当中的大部分由于在原来的k n o b s f i l e 当中已经有了具体描述 的格式，其改动相对简单，比如说寄存器的个数信息。然而，有些信息是原来的 k n o b s f i l e 当中所没有描述的，比如说对发射延迟的描述，由于原来的i t a n i u m 当 中所有的功能部件都是全流水的，因此发射延迟缺省都是1 ，而龙芯i 处理器当 中含有不流水的除法部件，因此我们应该考虑在2 - 2 2 当中列举的几种合法的描 述方式当中选取合适的一种对它进行描述。很显然，这种描述应该是一个功能部 件到整数( 即发射延迟周期数) 的映射，因此我们选用第3 种描述方法，并构造 一个数组r e s l a t e n c y ：a r r a y f ut 】o f i n t 来完成这个描述。在此之后，显然，对于 这种情况，光改动k n o b s f i l e 是不够的，为了真正能够生成编译器可用的信息， 我们还要在e k a p i 层和生成层当中去添加接口，这部分工作将在后面详细介绍。 2 ) k a p i 层。按照我们刚才的分析，这一层次类似于语法分析，它是与k n o b s f i l e 当中具体的信息无关的，所以几乎不用作什么改动。但是，在k a p i 层的设计当 中，还给它赋予了一定的安全功能，在这一层当中也保留了一份包括功能部件种 类，个数等被认为是相对稳定的微体系结构方面的信息。在进行语法分析的时候， 它不但要对描述这些信息的内容格式正确性进行检查，还要把这些信息具体的值 和自己保留的值进行比较，如果不匹配，机器信息的生成过程也会告失败。因此， 当体系结构有较大的变化的时候，我们还需要对k a p i 层这份保留的信息进行更 新。 3 ) e k a p i 层，这一层是利用k a p i 层的结果生成一些和k n o b s f i l e 信息相关 的接口供生成层用，因此，在k n o b s f i l e 当中添加了新的描述之后，我们就必须 随之添加新的e k a p i 层中的接口，在1 ) 中所举例子中，我们可以利用k a p i 层提供的用来描述变量到整数映射的接口k a p i 来访问所添_getintegervariable 加的信息，最后生成了一个e k a p i 的接口，用来表示功能_reslatency4issueport 部件到发射延迟的映射。 4 ) 生成层，这是机器信息流动的最后一层，在e k a p i 层新添加了接口以后， 这里也将添加新的接口，最终新生成机器外部描述的一部分，还是接着1 ) 的例 机器模型 子，利用上边所提到的指令操作码到功能部件的映射以及功能部件到发射延迟的 映射，我们生成一个叫r s l r e s l a t e n c y 的接i s l ，他能够根据提供的指令操作码 快速查询到相应的发射延迟，然后，在指令调度的资源管理模块即微调度模块， 就可以调用这个接口获得每条指令的发射延迟信息从而指导我们的指令调度。 2 3 结论与展望 从我们机器描述文件的格式分析可以看出，相对于前几种编译器的机器模 型，我们的机器描述文件的描述方式更简单，可读性更强。而从上面的移植过程 可以看出，不论是机器描述文件本身内容的组织还是内部机器信息到外部机器信 息的转换过程，都有着比较清晰的层次结构，在进行升级修改的时候，很容易确 定变化所影响的范围，这充分说明了这个机器模型的灵活性和可移植性。 另一方面，机器模型也面临着一些挑战，首先，我们知道，机器模型大多使 用的是描述性的语言，随着体系结构的不断发展，不断会有一些精心设计的体系 结构特征涌现，这对机器模型的描述能力就是一个考验，只有不断的丰富我们的 描述手段，才能精确的描述这些特征，编译器也才有可能利用这些特征，最终实 现高性能，另外，我们看到的编译器各自都拥有自己的机器描述和机器信息生成 流程，而且互相不通用，这样每当体系结构有更新的时候都要各自重新编写机器 描述。如果考虑使用通用的描述语言来描述机器模型，那么在新的体系结构推出 的时候，不同的编译平台就有可能共享一份标准的机器描述。 龙芯i 编译器中的指令调度相关优化 第三章静态指令调度 静态指令调度是编译器后端优化的一个非常重要的阶段。我们知道，现代的 处理器当中绝大部分都使用流水线结构，即指令是流水执行的，我们知道理想的 流水线可能使得作业效率有成倍的提高，但是对应到计算机处理器当中的流水 线，要想达到效率最优是非常困难的，这就是因为指令之间的数据依赖和结构相 关所造成的，静态指令调度就是在还不知道程序某些动态信息和行为的情况下， 根据所分析的指令之间依赖关系以及目标机的资源状况，对指令序列进行重排， 从而减少流水线停顿，以期缩短程序的执行时间。 3 1 背景简介 2 1 各种指令调度的方法 按照调度范围划分，指令调度可以分为局部指令调度和全局指令调度。前者 的调度范围是一个基本块，而后者可以跨越基本块的边界。对于前一种调度，范 围相对比较小，而且由基本块的构造我们得知代码序列呈线性状，因此调度起来 比较容易。对此，j o s e p hf i s h e r 在他的博士论文【6 】中给出了一个评价：“基本块 内调度不是一个最重要的问题，因为我们所能找到的好的策略都相差无几，已经 接近于最优了。”而对于全局指令调度来说，根据调度的区域是否存在回边，又 可以分为无环调度和有环调度，前者就是我们所指的“狭义”的指令调度，后者 包括软件流水等优化手段，由于代码的移动不再受控制流边界的限制，就会增加 复杂性。 实现静态指令调度就必须考虑以下两个问题，关于指令调度的研究也多从这 两个方面展开： 1 ) 调度的算法。 指令调度已经证明了是一个n p 完全问题，因此，必须找到启发性方法，l i s t s c h e d u l i n g 5 就是非常常见的一种方法，它的特征是以启发式信息作为驱动，采 用贪心算法，每次调度一个时间槽，它已经应用于多种调度范围之中并达到了好 的效果。除此之外，p h i l i pj 在他的博士论文中【4 】借鉴a i 中的技术提出了i t e r a t i v e r e p a i rs c h e d u l i n g ，它的调度过程分两步，它先不考虑资源限制得到最好的调度， ( 这就是一个最短路径问题) ，然后再根据资源限制做相应“r e p a i r ”调整。 2 ) 调度的范围。 全局指令调度不同于局部指令调度的地方就在于其调度范围不仅仅限于基 本块，但是我们知道，由于代码移动要跨过控制流的边界，那么复杂性就会加大， 因此，如果调度的范围过小，那么在进行调度的时候同时考虑的指令就会少，从 而影响我们调度的效果，而过大，则会加大处理的难度，甚至导致编译时间达到 静态指令调度 不能忍受的程度，因此决定一个足够大而且易于控制的调度区域对指令调度的效 果有直接的影响。 t r a c es c h e d u l i n g 7 就是根据p r o f i l i n g 信息或者启发性算法，构造一条t r a c e ， 它是由很多顺序的基本块构成，程序的执行有很大的概率就是沿着这条t r a c e ，然 后把t r a c e 当作调度范围进行调度，在此过程中，跨越基本块的调度有可能要在o f f t r a c e 的基本块里插入补偿代码，可以举出一个最坏的例子代码中指令数量由 o ( n ) 激增至0 ( n i l ! ) 。【1 5 】因此这种方法的实质是牺牲一部分o f f - - t r a c e 代码的效 率换取t r a c e 中代码的效率，因此它比较适用于代码执行存在明显热路径的程序， 而且需要有比较好的类似p r o f i l i n g 的技术来找到程序中存在的热路径。m u l t i f l o w c o m p i l e r 就是用了这种调度算法。s u p e r b l o c ks c h e d u l i n g 8 和h y p e r b l o c k s c h e d u l i n g 9 都是对这种方法的改进。它们针对补偿代码过多的特点，对调度区 域做了进一步限制，比如说s u p e r b l o c ks c e h d u l i n g 当中的调度区域s u p e r b l o c k 就禁 止边入口的存在，也就是说不可能有某一条指令同时是t r a c e 和o f f - - t r a c e 当中跳转 的目标，其中s u p e r b l o c ks c h e d u l i n g 被应用于了i m p a c tc o m