（计算机系统结构专业论文）全局无环指令调度研究.pdf

摘要 指令调度是一种指令级并行技术。它既是一种微体系结构技术，也是一种编译技术。 对于后者，指令调度指的是在保持程序语义的前提下通过重耨排列指令的顺序来提高流 水的或多发射处理机的指令级并行度。随着微体系结构和微电子技术的发展，现代处理 机所包含的硬件资源越来越丰富。指令调度只有跨越基本块的边界才能够充分地发挥目 标处理机的指令级并行的潜力。本文所研究的技术就是全局调度的一种，即无环的全局 指令调度。本文的贡献包括以下几个方面： 1 _ 在d b e r n s t e i n 的面向超标量目标机的全局调度算法基础卜，提出了面向i a 一6 4 体系 结构的全局调度框架。 2 在d b e r n s t e i n 的全局指令调度算法框架上提出了层次化区域上全局调度框架。传 统的全局调度的区域是扁平的。扁平调度区域有许多缺点。一方面，由于调度器对调 度的形状有许多特定的要求，因而常常导致区域偏小。另一方面，在控制流比较简单 的情况下，扁平调度又有可能过大，因而导致过大的编译时空开销。层次化区域小存 在上述缺点。因此，应用层次化区域到db e r n s t e i n 的全局调度中是很有意义的。 3 在d b e r n s t e i n 的全局调度算法框架上集成p r e a d y 调度技术。 4 改进了d b e r n s t e i n 的全局调度算法的启发性方法。提 l 了新的优先级函数来衡量指 令优先级。 克服或减弱了该算法存在的以下3 方面缺点：( 1 ) 偏袒控制等价调度从而抑制了 指令投机。( 2 ) 过分高估指令复制的代价从而导致失去一些优化机会。f 3 ) 在指令的 优先级的评估机制中，d e l a y s u m ( ) 函数比d e p h e i g h t ( ) 重要从而不必要地延长了 关键路径的长度。 5 提出了生成树调度算法，包括调度框架和启发性方法两个方面。传统的基于非线性控 制流图的全局无环指令调度算法在评估指令的优先级别局限于基本块。而生成树调 度则能够在整个控制流的最大生成树上评估指令的优先级，因而能够更加精确地评 估指令的优先级，从而提高调度质量。 6 上述技术均在i a 一6 4 开放源码编译器o r c 巾实现。实验结果验证r 这些技术的有 效性，达到了先进水平的性能加速比。 关键宇：全局指令调度，指令级并行，i a 一6 4 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 sk i n do fi n s t r u c t i o nl e v e lp a r a l l e l i s m ( i l p ) t e c h n o l o g y i t i sb o t ham i c r o a r c h i t e c t u r et e c h n o l o g ya n dac o m p i l a t i o nt e c h n o l o g y t ob et h el a t e r ， i n s t r u c t i o ns c h e d u l i n gr e f e r st ot e c h n o l o g yt h a te x p l o i t st h ei l po fp i p e l i n e do rm u l t i i s s u e dp r o c e s s o r sb yr e o r d e r i n gt h ei n s t r u c t i o n su n d e rt h ec o n s t r a i n t so fp r e s e r v i n gt h e s e m a n t i c s w i t ht h ed e v e l o p m e n to fm i c r o a r c h i t e c t u r e ，s t a t eo fa r tp r o c e s s o r sn o r m a l l y h a sa m p l er e s o u r c e s t og e tt h ef u l lu t i l i z a t i o no ft h e s er e s o u r c e s i n s t r u c t i o ns c h e d u l i n g s h o u l db ep e r f o r m e da c r o s sb a s i cb l o c k sb o u n d a r y ，v i z ，g l o b a li n s t r u c t i o ns c h e d u l i n g t h i st h e s i sp e r f o r m sai n t e n s i v es t u d yo na c y c l i cg l o b a li n s t r u c t i o ns c h e d u l i n g ab r a n c h o fg l o b a li n s t r u c t i o ns c h e d u l i n gt e c h n o l o g y o u rc o n t r i b u t i o n si n c l u d e sf o l l o w i n ga s p e c t s ： 1 p r o p o s eag l o b a li n s t r u c t i o ns c h e d u l i n gf r a m e w o r ko r i e n t e dt oi a 一6 4 a r c h i t e c t u r e 0 u rw o r ki sb a s e du p o nd b e r n s t e i n sw o r kw h i c hi so r i e n t e dt os u p e r s c m a r 2 b a s e do i 3 d b e r n s t e i nw o r k ，w ep r o p o s eag l o b a li n s t r u c t i o ns c h e d u l i n gf r a m e w o r ko n h i e r a r c h i c a l l ys t r u c t u r e dr e g i o n ( h s r ) t h es c h e d u l i n gs c o p ef o rt r a d i t i o n a lg l o b a li n s t r u e t i o ns c h e d u l i n gi sf l a ts t r u c t u r e d af l a ts t r u c t u r e dr e g i o ni sn o r m a l l yv e r ys m a l l d u et ot h ef a c tt h a ts c h e d u l e rp o s es p e c i a lr e q u i r e m e n t so nt h es h a p eo fs c h e d u l i n g r e g i o n o nt h eo t h e rh a n d ，af l a ts t r u c t u r e dr e g i o nc ans o m e t i m e sv e r yl a r g ei ft h e c o n t r o lf l o wi ss i m p l e h s rr e g i o nh a sn os u c hf l a w s ，h e n c ei td e s e r v eoure f f o r tt o p e r f o r mi n s t r u c t i o ns c h e d u l i n go nh s r ， 3 i n t e g r a t ep r e a d yi n s t r u c t i o ns c h e d u l i n gt od b e r n s t e i n si n s t r u c t i o ns c h e d u l i n gf l a m e - w o r k 4 i m p r o v et h eh e u r i s t i co fd b e r a s t e i u sg l o b a li n s t r u c t i o ns c h e d u l i n g w ea r et r y i n g t oi m p r o v et h ef o l l o w i n g2d e l e c t s ：( 1 ) f a v o rc o n t r o le q u i v a l e n tc o d em o t i o no v e rs p e c u l a t i v ec o d em o t i o n ，t h e r e f o r es u p p r e s ss p e c u l a t i o n ；( 2 ) o v e re s t i m a t et h ec o s to fc o d e d u p l i c a t i o n ，a n dh e n c el o s ts o m eo p t i m i z a t i o no p p o r t u n i t i e s ；( 3 ) t h ec o d eo nc r i t i c a l p a t hw i l lb ed e l a y e dd u et ot h ep r i o r i t ym e c h a n i s mw e i g h sd e l a y s u m ( ) m o r et h a n d e p h e i g h t ( ) 5 p r o p o s ean o v e ls p a n n i n gt r e es c l w ( h f l i n g ( s t s ) a l g o r i t h n li n c l u d i n g2a s p e c t s ：s c h e d u l i n gf r a n l e w o i ka sw e l la si t s l l e n li s t i c i ft h ec o n t r o lf l o x 、i s1 1 0 1 1 一l i n e a i ，t r a d i t i o n a l g l o b a ls c h e d u l i n gw i l lc o n f i n e h 、1 1 i s e l v e sw i t h i nab l o c ki nt h ee v a l u a t i o uo fi n s t 1 n c t i ( n 1 sj ) r i 0 1 m - s t sc 8 1 1e 3 i l 卅pl u s t ! l k t i o n s p t i ( ) l l f 、o nal n a x i t l l l l l l ls 1 ) m u t i n gt r e e 1 ft h es c l m d u l i n 3r e g o b e ( t ll n ( 1t i l f ，s ( n ”，i sl a t g e t t l i 、p 、。a t u a t i o no fs t si su i ( ) i p 全局无环指令调度研究 p r e c i s ea n dh a sb e t t e rp e r f o r m a n c e 6w eh a v ei m p l e m e n ta l lp o i n t sw eh a v ep r o p o s e d t h ee x p e r i m e n t si n d i c a t et h e ya r e e f f e c t i v e k e y w o r d ：g l o b a li n s t r u c t i o ns c h e d u l i n g ，i n s t r u c t i o nl e v e lp a r a l l e l i s m ，i a 一6 4 声明 本人声明所呈交的论文是我个人在导师指导f 进行的研究工作及取得 的研究成果。就我所知，除了文中特别加以标注和致谢的地方外，论文中 不包含其他人已经发表或撰写过的研究成果。与我一同工作的同志对本研 究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 作者签名： 日期： 关于论文使用授权的说明 中国科学院计算技术研究所有权处理、保留送交论文的复印件，允许 论文被查阅和借阅：并可以公布论文的全部或部分内容，可以采用影印、 缩印或其它复制手段保存该论文。 作者签名：导师签名：日期： 第一章引言 1 1 编译器结构 一个编译器通常由以下3 个部分组成： 前端：前端负责把源代码转化成中间表迭式( i n t e r m e d i a t er e p r e s e n t a t i o n ) 。在这 个过程巾，前端进行了词法分析、语法分析以及语义制导翻译等步骤。前端与语言相关， 与目标机夼相关或基本不相关。一个编译器的通常支持多种编程语言，因而相应地可能 有多个前端。 中端：编译器的中端由若干优化器和分析器组成。它们通常是全局优化器分析器或 过程间的优化器分析器。全局优化器分析器是指收集整个函数的信息，并且在整个函 数上进行优化变换分析的阶段( p h a s e ) 。过程间的优化器分析器，顾名思义，是指这 样的一种的优化分析阶段：它们收集和传播信息的范围跨越函数的边界，而且它们所实 施的优化变换分析的范围也跨越了函数的边界。中端通常基本不和被编译程序所使用的 语言以及目标机相关。 后端：后端包括一组针对目标处理机的优化器组成。后端还负责将中间表示翻译成 目标处理机认识的目标代码。指令调度和寄存器分配是编译器后端十分重要的两个阶段。 以开放源码编译器o r c t e a 0 3 来说明编译的结构。o r c 是i n t e l 公司和中国科学 院的联合项目。o r c 派生于s g i 公可的开放源码编译器p r 0 6 4 ，而后者是从s g i 公司 的产品编译器m i p s p r o 移植来的。 o r c 总共由5 个模块构成：前端( f e ) 支持4 种语言：c 、c + + 、f o r t r a n7 7 和f o r t r a n 9 0 。中端包括3 个模块：过程问分析与优化( i p a i p o ) 、循环嵌套优化( l n 0 ) 和全局 标量优化( w o p t ) 后端由代码生成( c g ) 构成，如图1 1 所示。基于符号表的巾间表示 w h i r l 作为各个模块以及模块巾的各个阶段之间通讯的“载体“。w h i r l 是层次结构 的，共计6 层。1 每个模块的输入的巾问表示层次通常比输出的巾间表示的层次高。巾问 表示由高到低的递降在模块中进行。在图1 1 l h 每一个模块的入口、出口和中问过程所 使用的巾间表示由横跨“巾间表示”和“优化阶段鹏栏的箭头表示。 1 通常小把最后层中间表示c g i r 看作w h i r l 的部分，冈而、+ h i r l 肓5 层。为_ ：r | 兑叫方便 我们把c g i r 也香作、h i r l 的剐；分? 全局无环指令调度研究 优化阶段中问表示 图1 1 ：o r c 的组成 i p a & i p o 分成两个步骤进行：i p l 和i p a - l i n k 。i p l 收集被编译程序的摘要信息。 它每一次处理一个函数。i p l 收集的典型信息有：调用点相关的形参和实参、变量被更改 和引用的次数、调用点频率、a d d r e s st a k e n 等。i p a l i n k 这个步骤首先分析i p l 所取得 的摘要信息并把分析的结果标注到函数调用图( c a l lg r a p h ) 上。等分析完毕，i p a - l i n k 开始实施优化。过程问分析主要有：死函数分析、数组填充和分割分析、全局符号的属 性分析、i n l i n i n g 的代价等。因为分析的范围跨越了函数的边界，所以在过程间分析开始 之前必须合并每一个函数对应的符号表，并且还要建立调用图。过程间优化主要有：死代 码删除、常数传播、i n l i n i n g 、把一些间接调用变成直接调用等。 l n o 是一组针对循环的优化，主要目标是提高局部性( 1 0 c a l i t y ) 。它的优化主要有： 循环交换、循环f i s s i o n f u s i o n 、循环展开2 等。在有些编译器中，这些优化是通过编译 之前的一个预处理程序完成的。l n o 把这些针对循环的优化集巾在一起并且安排到巾 端进行。这种做法不仅对不同的语言提供了统一的优化手段，而且在处理上能够史加灵 活。 w o p t 的优化包括g l o b a lv 8 l u en u m b e r i n gf g v n ) c l i 9 5 1 、死代码删除、p a r t i c a l r e d u n c a n c ye l i m i n a t i o n ( p r e ) c c k + 9 7 1 1 k c l + 9 9 1 和r e g i s t e rp r o m o t i o nf l c k + 9 8 1 。 g v n 的目标是删除完全冗余的代码，而p r e 则足删除部分冗余的代码。在g v n 把1 1 间表示转变成h s s a ( h a s h e ds s a ) c c l + 9 g 式，g v n 之后的优化的巾间代码均采用这 ! 在代码生成阶段也有循蚪展t r e ( 1 j i ! = l “足提高指令级许”陡i “j l i 是局部性 端r 端 - j + 端lt黼上+i橼ili上+麟上 第一章1 引言 种形式( 包括p r e 在内) 。w o p t 的s s a 式的中间表示还有。个重要的特点是：它有 效地表示了别名和间接存贮访问操作( i n d i r e c tm e l n o r ya c c e s s ) ，这个特色使得优化阶 段能够统一地处理标量和通过指针访问的存贮变量。p r e 是w o p t 中十分重要的一个 阶段。p r e 阶段自动地完成或包括以下几种常规优化：公共子表达式删除、循环不变量 外提、c o d eh o i s t i n g 、强度削弱f k c d + 9 8 等。 c g 主要针对目标机，它的主要的阶段有：各种p r o f i l e 支持、i f - c o n v e r s i o n 、软流水、 循环展开、指令调度、寄存器分配、代码发射等。代码生成阶段主要以c g i r 作为巾间表 示。机器模型描述目标处理机的具体细节。各个阶段通过查询机器模型了解目标处理机 的的参数。 1 2 指令调度 指令调度( i n s t r u c t i o ns c h e d u l i n g ) 是一种指令级并行技术，指令调度通过调整指令 的顺序来提高流水的或多发射处理机一拍内能够执行的指令的数目( i p c ) 。指令调度既 是一种微体系结构技术也是一种编译技术。在微体系结构方面，超标量处理机通过乱序 执行发射以达到动态调度的目的。在编译方面，编译器通过重排指令的顺序来提高指令 级并行( i l p ) 度。为了区别这两者，在以下章节中，我们用“动态调度”表示微体系技术 范畴内的指令调度技术，而用“指令调度”表示编译技术范畴中的指令调度技术。 在传统的串行的并且是非流水的处理机上，代码的执行时间仅决定于所有指令延迟 的总和。所以，在这些处理机上，指令调度彳i 会提高目标代码的质量。反之，我们需要利 用指令调度技术来提高目标代码的指令级并行性。硬件上的动态调度在一定程度上削弱 了指令调度的性能 m j d 9 8 1 ，但是它不会使指令调度成为摆设。这是因为动态调度很大程 度上依赖于指令窗口( i n s t r u c t i o nw i n d o w ) 的大小，但是由于指令窗口通常很小，通过 动态调度来提高i l p 是十分有限的p 9 0 1 。 指令调度派生于水平微指令体系结构上的m i c r o c o d ec o m p a c t i o n l d s m 8 0 技术。水 平微指令体系结构的一条指令包含若干可并行执行的操作( o p c r a t o r ) 。m i c r o c o d ec o i l l p a c t i o n 的目标是让一条指令包含尽量多的操作。这个目标和指令调度提高i p c 的目标 十分接近。0 i 仅如此，许多m i c r o c o d cc o m p a c t i o n 技术可以直接应用现代的指令调度。 在f 文h 作者1 i 再区分这两个技术之间的差别。 与指令调度关系密切的另一个概念是代码移动( ( o d em c ) t i t ，u ) 。代码移动所指的范 围更广些，它包括指令调度，它还i ，j 以指其它优化技术，例如p a r t i a lr e d l m ( 1 ( ：二、e l m l - ；t t i o n k r s 9 2 1 。 全局无环指令调度研究 从被调度对象的控制流形状的角度出发，指令调度可以被划分为有环调度和无环调 度两类。顾名思义，有环调度可以顺着或逆着循环回边( b a c ke d g e ) 的方向调度指令跨 越循环迭代的边界，例女h r g p 8 2 ，h u f 9 3 ，j a i 9 1 1 。而无环调度则不然，它只能在同一个控 制层上进行指令调度。 最初的指令调度局限于基本块内部j r 7 6 ，a c d 7 4 ，l d s m 8 0 1 ，研究表明，基本块通常 很小，一个基本块潜在的指令级并行度( 儿p ) i 艮d l d 9 0 l 。随着芯片设计技术的发展，现 代处理机所包含的资源越来越丰富。指令调度只有跨越基本块的边界才能够充分发挥处 理机的多资源的特点以及程序中固有的i l p 。这样的调度我们称之为全局指令调度。有 环调度是一种全局指令调度，不论有环调度所作用的范围是否局限于单个基本块。这是 因为：循环体巾的一个基本块代表该循环所有迭代的一个相同的基本块。由于本文主要 描述无环指令调度，为了说明方便，在以下章节中，如果不引起歧义，“全局调度”仅指无 环全局指令调度。 最初的全局指令调度把局部调度简单地延伸。它们( 例如f m e t 8 1 1 ) 通常通过以下两 个步骤完成全局调度的：( 1 ) 分别调度每一个基本块( 2 ) 从一个基本块向它的相邻的基 本块移动指令以增强指令级并行度。这种调度致命的缺点在于它没有在全局上评估一条 指令的优先级。在步骤( 2 ) 进行的过程中往往发现步骤( 1 ) 的调度不合适，但是在这时 已经太迟了。 现有的全局指令调度算法按照调度区间的形状基本上可以分成两类：基于线性控制 流和基于非线性控制流。在本节所介绍的调度算法中f ja 8 1 ，h s w + 9 3 ，m l c + 9 2 1 属于第 一类型，而其它均属于第二类型。其中基于线性控制流的全局调度算法提出的时间较早， 算法本身也相对比较简单，但是缺陷也比较明显。 由于指令调度和目标处理机是高度相关的，所以在一个编译器中，指令调度不管 是有环调度还是无环调度、不管是局部调度还是全局调度被安排在编译器后端。 1 3 全局指令调度综述 在这一节巾，我们将介绍几个比较典型的著名全局调度算法。t r a c es c h e d u l i n g 和 p e r c o l a t i o ns c h e d u l i n g 在提出时是面向v l l w 体系结构的，而本节介绍的其它的调度算 法要么面向标量处理机要么没有明显地说明面向那一种体系结构。为了便于说明这两种 调度算法，区分以f 两个名词：操作( o p e r a t o r ) 和指令( i n s t n m t i o n ) 。操作指的是能够 往功能部件j ：执行的代码实体：而一一条指令包含若干可以并行执行的操作。在描述其他 弹法时，并小区分这两个名词。或者说，我仃1 麒殴日标处理机是靼发射的。 第一章1 引言 1 3 1 迹调度 迹调度( t r a c es c h e d u l i n g ，以下简写为t s ) f j a 8 1 最初应用于m i c r o c o d ec o m p a c t i o n ，但它能够同样很好地应用于超标量和e m p h v l i w 体系结构上的全局指令调度。t s 的调 度区间是多入口多出口的线性无环控制流图，即“t r a c e ”。t r a c e 是全局控制流图( c f g ) 的有向路径片段，它不包含循环。t r a c e 可以多入口多出口，即可以通过t r a c e 中的多个 基本块把控制流转移到该t r a c e 中；控制流能通过该t r a c e 中的多个基本块离开该t r a c e 。t s 的调度过程可以分成3 个步骤： 1 t r a c e 的选择：从尚未调度的控制流中找出一条频率最高的t r a c e 。 2 t r a c e 调度：建立t r a c e 上操作之间的依赖关系，然后应用l i s ts c h e d u l i n g j r 7 6 1 算 法调度整个t r a c e 就像调度单个基本块一样。 3 代码补偿( b o o kk e e p i n g ) ：在t s 调度过程中，若操作0 向上或向下跨越分枝操 作6 r ，调度器需要复制o 到t r a c e 之外的经过6 r 的路径中以保持程序的语义。 以上3 个步骤重复执行直到控制流中不再出现尚未被调度过的基本块。在步骤1 中， 为了找出一条频率最高的t r a c e ，调度器必须高度依赖于p r o f i l e 信息。在步骤2 中，调度 器不仅要象局部指令调度那样建立操作之间的数据依赖关系，还要建立如下两类依赖关 系：( 1 ) 分枝操作之间的依赖关系和( 2 ) 分枝操作和部分非分枝操作的依赖关系。前者 是为了防止调度器调整分枝操作之间的顺序一通常调整分枝操作会极大地增加调度的复 杂性，而目标代码的性能却不会有所提高。而后者为了避免一条操作被向上调度跨越一 条分枝操作从而覆盖( k i l l ) 了从这个分枝操作出发延伸到t r a c e 之外的活跃变量的值。 t s 十分简单，易于实现。但它存在许多缺点： 1 t s 完全牺牲t r a c e 之外的代码的性能来提高一条t r a c e 的质量。这样做的根据是假 定t r a c e 的执行频率要比t r a c e 之外的代码的执行频率高的多。对于科学计算程序 来说，上述假定是比较合适的。然而，对于通用应用程序来说，上述假定并不恰当， 因为通用应用程序的分枝操作常常不偏袒它的任何一个出口。 2 t s 的代码补偿过程十分复杂，尤其是向下或向上跨越j o i n t 点的调度的代码补偿 。 分复杂。 3 代码补偿过多引起代码膨胀。 克服缺点1 要求调度器必须综合程序巾不同分枝指令的重要性，即要求把调度区域扩 展到非线性的控制流上。在t s 提出1 0 年之后，f i s h e r 又提出t r a c e 一2 算法f j a 9 3 1 ，该 算法把调度区间扩展到非线性的控制流。事实i 二，基于非线性控制流图的全局调度有许 多，下文将介绍其巾比较著名的几种。为了减小跨越i o i n t 点的啕度的代码补偿的复杂 性，f h s w + 9 3 m l c + 9 2 通过尾复制消除t t a 的旁入口( t 1 0 c ( 一j o i u t 点) ，从而取 消1 - “跨越j o i u t 点的凋度一及它所带来的复杂的代码补偿。h s w 9 3m l c 4 9 2 1 p 2t i 全局无环指令调度研究 的选择( t s 步骤1 ) 从调度中分离出来以减小调度的复杂性。同时 h s w + 9 3 ，m l c + 9 2 1 还 通过l o o pp e e l i n g 等手段尽量扩大调度范围。t s 的代码补偿有些是没有必要的，有些是 可以抑s t j 的 m r g 9 3 ，e 1 1 8 6 1 。 m r g 9 3 的研究表明抑制向下指令调度对性能的影响可忽略 不计，而代码补偿则可以大大减少。t s 被应用到许多编译器中，包括著名m u l t i f l o w 产 品编译n l f k + 9 3 。 1 3 2渗透调度 渗透调度( p e r c o l a t i o ns c h e d u l i n g ，简写为p s ) f n i c 8 5 ，e n 8 9 1 作用于并行程序图( p a r a l l e l p r o g r a mg r a p h ，p p g ) 。p p g 的有向边表示控制流转移。p p g 的每一个结点表示能够并 行执行的一组操作。如果目标机是v l i w 的话，p p g 的每一个结点就是目标机的一条指 令。p p g 作为目标机为v l l w 的编译器的中间表示是很方便的。例如，支持m u l t i w a y b r a n c h 和树状指令字的v l l w 程序能够被很方便地表示出来 n p 9 0 1 。在这种情况下，p p g 的一个结点可能包含有多个分枝操作。 p s 是层次结构的：低层是由4 个核心变换构成的，核心变换是p p g 上相邻结点之间 的操作移动，它不依赖于调度器应用的任何启发性方法，详见下文；高层有一组调度变换 构成，在一定的启发性方法下，它们调用核心变换完成对程序的调度。核心变换包括： m o v e o p ：把操作o 从结点到移动到相邻结点m ，如果存在经过但不经过m 的路 径，复制。到这些路径上。 m o v e 一巧：把分枝操作从一个结点移动到它的相邻结点。 u n 锄：完全相同的多个操作可以通过下述方法删除掉：放置一个操作实例于这些相 同操作所在结点共同的祖先结点中。 d e l e t e ：代码移动可能会使得一些结点变空，这些结点可以被删除。除了d e l e t e 以外， 其它3 个变换都是代码移动。 在p s 中，操作只能从一个结点向上( 即逆着控制流方向) 移动到相邻结点。p s 没 有向下代码移动，以此保证调度是可终止的。p s 自提出以来得到了很大的发展。f m k 9 2 1 提出的改进考虑了目标处理机的资源限制。p s 假定操作的延迟为1 ，f n p 9 0 取消了这个假 定。p s 的每一次代码移动都是局部的，这不仅会产牛4 i 必要的代码复制而且还大大增加 r 编译时间。t i p s a s 9 3 1 克服了p s 的上述两个缺点。实验表明，t i p s 能够提高l o 的 调度时间，同时提高5 的调度质量。 1 3 3区域调度 区域调度( r e g i o ns c h e & d i n 9 t 以f | 简写为r s ) f g s 9 0 】以扩展的p d g f o f 、。8 7 】作为 挂序的q 1 ，间表示。p d g 在r s 叶一个仪作为程宁变换的r 具，还可资用来发现程宇巾潜在 “ 第一章1 引言 的并行性。r s 通过把并行度高的部分向并行度低的部分迁移代码从而完成指令调度。 r s 既可以应用于粗粒度并行的场合，也可以应用于细粒度并行的场合。 p d g 统一地表示程序中的控制依赖和数据依赖。由于它是层次结构的，控制和数据 依赖可以分别在不同的层次上进行处理。在p d g 上作增量式的数据流改动比较方便， 因而适合于作象指令调度这样的优化阶段的中间表示。此外，p d g 有一个很可贵的优点 是：从p d g 上很容易观察出哪些代码可以并行执行。r s 对p d g 作了一些扩展以便调 度的进行和调度的正确性。r s 中“r e g i o n ”指的是p d g 图上的结点，它表示直接依赖于 相同控制条件( 谓词) 的一组代码。“r e g i o n ”也经常出现在许多其它的全局指令调度的 算法中，在这些算法中“r e g i o n ”通常表示一个连续( 即弱连通) 的控制流子图。然而，在 p d g 的“r e g i o n ”对应的控制流不一定是连通的。 r s 通过以下3 种变换完成并行度的分布： 1 与循环相关的变换：包括循环展开和循环不变量外提。把对应于循环的r e g i o n 中剥 离( p e e l ) 若干迭代并把这些代码( 展开的迭代) 加入到并行度不足的r e g i o n 中。循 环展开本省可以用来增加r e g i o n ( 对应于循环) 的并行度。类似地，并行度不足的 r e g i o n 可以把附近区域( 对应于循环) 中的循环不变量提到该r e g i o n 区域中。 2 向上和向下的代码移动：在p d g 上，把代码从一个区域移到它的父r e g i o n 里，或者 移动到它的子r e g i o n 里。 3 区域复制和合并：复制并行度低的r e 西o n 到它的父r e g i o n 中，从而消除该r e g i o n 。 或者将这个r e g i o n 和其它r e g i o n 合并。这种变换可以消除一些分技指令。 r s 不停地重复上述变换直到p d g 中不存在一个r e g i o n 其并行度低于某个上限( 依 赖于目标处理机的并行能力) 。在r s 中，r e g i o nr 的并行度被定义为：g d ；，其中d i 表示r 中操作的的个数，皿表示r 中最长的数据依赖链的长度。尽管r s 声称它既可 以应用于粗粒度并行场合也可以应用于细粒度的并行场合。但是作者怀疑在细粒度的并 行场合下，r s 的性能可能不会太好，原因在于并行度的定义十分粗糙。r s1 i 停地从一 个区域向另一个r e g i o n 迁移并行度，直到不存在一个r e g i o n 其并彳亍度低于某个上限。 我们很难确定上述的循环( 指并行度的迁移) 的时间开销上界。在 g s 9 0 1 巾，并没有报告 r s 的调度时间。此外，尽管r s 并不依赖于p r o f i l e 信息，但是，即使p r o f i l e 信息存在 的话它也无法充分利用这个信息提高调度质量。 1 3 4b e r n s t e i n 的全局调度 b e t n s t e i n 的全局调度( g l o b a ls c h e d u l i n g ，以下简写为g s ) d r g l 】掉法也依赖 ：y ：p d g f o v 8 7 。与基于p d g 的区域调度【g s 9 0 】4 i 同的是p d g 并小作为峒度器的中间 表示，惭h 是作为调度器的个r 具。由于g s 的针对的， 有少疑功能部件的处胖机， 全局无环指令调度研究 g s 抑制代码复制。 g s 利用p d g 区分两种不同的调度：u s e f u l 调度和s p e c u l a t i v e 调度。设一条指令所 在的基本块是s ，被向上调度到基本块t ，如果sp o s t d o m i n a t et ，那么这个调度被称 为是u s e f u l 调度，反之，则称为是s p e c u l a t i v e 调度。由于g s 不支持代码复制，这两种调 度均要求td o m i n a t es 。一个从块s 到r 的s p e c u l a t i v e 调度的投机度( s p e c u l a t i v e n e s s ) 被定义为在p d g 上从t 到s 的路径长度。g s 只支持投机度为l 的s p e c u l a t i v e 调 度。这个限制也有效地保证了代码不会被复制。 g s 的调度范围也称作“r e g i o n ”，与基于p d g 的区域调度不同的是，g s 中所指的 “r e g i o n ”是指自然循环( n a t u r a ll o o p ) 的循环体( 不包括回边) 。假如整个被编译函数 没有循环的话，“r e g i o n ”指的是整个函数对应的控制流图。不管那种情况，“r e g i o n ”只 有一个入口结点。g s 并没有指出在有含嵌套循环的情况下，对应于外层循环的“r e g i o n ” 所指的范围。在这里我们暂忽略这种情况。为了区分g s 和r e g i o ns c h e d u l i n g 中“r e g i o n ” 的区别，我们用中文“区域”表示g s 中的“r e g i o n ”。 调度器从最里层的区域到最外层区域的顺序调度每一个区域。g s 不允许指令被调 度出区域之外，分枝指令的相对位置不更改( 和t r a c es c h e d u l i n g 的要求一样) 。此外， g s 只支持向上( 逆着控制流方向) 指令调度。 调度器对一个区域冗的调度描述如下：调度器以拓扑序遍历冗中的每一个基本块 于。设c ( t ) 为能够向t 提供候选指令的基本块集合。调度器从c ( t ) 中选取具有“最 高优先级”( 见下文) 的就绪指令i 调度到t 中( t 有可能本身就在t 中) 。当t 中所 有的指令都被调度过后，调度器转向下一个基本块。 调度器总是优先来自和目标基本块控制等价基本块的候选指令。这种极其偏袒来自 一部分基本块的指令的优先级机制具有很大的缺点。它甚至不能在局部( 即基本块内) 获得最优或次优的性能。因此，r s 要求在全局指令调度完毕后，对每一个基本块进行局 部指令调度。 对比于e n h a n c e dp e r c o l a t i o ns c h e d u l i n g ( e p s ) f e n 8 9 1 ，d r 9 1 1 表示e p s 更适合 于具有多功能部件的机器，例如v l i w ，而r s 主要针对超标量机器。 r s1 i 依赖于p r o f i l e 信息。但是即使p r o f i l e 信息存在并且是十分精确的，r s 也无 法利用这些信息提高调度质量。此外，r s 的启发性方法十分保守从而抑制了指令投机。 在全局指令调度中，如果从块s 调度指令z 到块t 中而目标块t 又矸id o m i n a t e s ，那么这个调度需要复制i 到经过s 的某些路径t 作为补偿代码，使得从程序的入口 到s 的每条路径上i 全少被执行一次。允许代码复制的g l o b a ls c h e d u l i n g ( c d g s ) b c h 9 1 】是在d r 9 i 基础增加对代码复制的支持。 本文的介绍的许多内容是针对c d g s 的改进，我们将在23 前小洋细介绍这个算法。 第一章1 引言 1 3 5 波沿调度 与l d r 9 1 ，b c h 9 1 - - 样，波沿调度( w a v e f f o n ts c h e d u l i n g ，以下简写为w s ) f b m m 9 9 输入也是无环区域。1 i 同的是w s 允许区域的入口可以是多个的，因而w s 较 b c h 9 1 具 有更大的灵活性。w s 在调度之前也要通过插入空基本块消除j s 边。此外，w s 还要在 区域的旁入口和旁出口插入接口块( i n t e r f a c eb l o c k ) 用来放置在旁入口处被向上调度 和在旁出口处被向下调度的指令的补偿代码。 w s 是自顶向下的调度。w a v e r o n t 是一组基本块的集合。它是已调度基本块和未调 度基本块之间的分界线：在w a v e f r o n t 之前的基本块均已被调度，w a v e f r o n t 之后均未被 调度，而调度器当前正在调度w a v e f r o n t 中的基本块。如果当前w a v e f r o n tw 中的基本 块b 被调度完毕，w 会向前进使得b 落在w 之后。在自项向下的顺序下，w a v e f r o n t 最初是调度区域中所有入口基本块的集合，v v a v e f r o n t 顺着控制流向前推进，最后一个 w a v e f r o n t 包含的基本块均为区域的出口结点。 一个基本块的候选指令既可以是m r e a d y 也可以是p r e a d y 的。如果至少存在一条 从点p 到指令i 的路径c ，i 不数据依赖于c 上的任何指令，且i 不相对于p 点m r e a d y ，我们称i 相对p 点p r e a d y 。p r e a d y 的引入增加了可选的候选指令的个数因而提高 的调度的质量。另一方面，调度器需要在目标点p 到i 一些路径上补偿代码以保持i 和 这些路径上的指令指令之间的数据依赖，从而使得i 在这些路径上至少执行2 次( 其中一 次在点p ) 。 w s 代码补偿在正在调度的区域内，所以w s 需要的在调度的同时( 而非之后) 进 行代码补偿。不同于 d r 9 1 ，b c h 9 1 1 ，w s 并不在一条代码i 调度之后立即做i 的代码 补偿，而是滞后到一个适当或者不能再滞后的时候进行。 w a v e f r o n t 的推进、p r e a d y 调度和滞后代码补偿无一不需要访问复杂的控制流信 息。在w s 中，路径集合用b i t - v e c t o r 表示。路径集合可以很方便地导出许多有用的控制 流信息和数据依赖关系。然而由于控制流所包含的路径个数在最坏情况下是结点个数的 指数倍，所以这个数据结构制约了