（计算机科学与技术专业论文）基于谓词执行的编译优化技术的研究与实现.pdf

国防科学技术人学研究生院学位论文 摘要 不断挖掘指令级并行性( i l p ) 是提高处理器性能的关键，而分支跳转指令造 成的控制相关，严重限制了i l p 的开发。针对此问题，超长指令字体系结构的高 性能数字信号处理器( d s p ) 提供了对条件执行指令的支持。为使此指令的优势得 以充分发挥，本文深入研究了谓词执行编译优化技术，主要取得了以下研究成果： 1 设计并实现了支持谓词执行的编译框架。该框架基于h y p e r b l o c k 区域结构， 解决了全谓词转换带来的资源缺乏问题，很好地对d s p 条件执行指令提供了支持， 为指令调度和优化模块开发i l p 提供了更大的自由空间。 2 给出了谓词相关的分析与优化。对代码实施谓词转换后，为了更好地进行 代码优化、指令调度和寄存器分配，文中首先介绍了j o h nw s i a s 等人提出的基于 二进制决策图的谓词分析系统( p a s ) 和基于谓词流图的数据流分析方法；然后， 提出了结合芯片自身体系结构特点的谓词优化过程。该过程简化了程序的控制逻 辑，减少了对谓词寄存器的使用，提高了编译性能。 3 提出了适于谓词执行的寄存器分配算法。为了缓解谓词执行带来的寄存器 分配压力，在p a s 基础上，对传统寄存器分配算法中建立干涉图一步进行改进， 提出了一种新的建立精化干涉图的算法。该算法对带谓词的代码较合理地分配了 寄存器，减少了寄存器溢出情况，从而缩短了代码的执行时间。 实验结果表明，本文设计实现的基于谓词执行的编译优化技术，充分发挥了 d s p 条件执行指令的优势，、提高了指令并行度，缩短了代码执行时间，获得了较 好的性能提高。 关键词：谓词执行条件执行指令h y p e r b i o c k 谓词分析系统谓词优化 数字信号处理器寄存器分配编译优化 笪堕型堂垫查尘竺婴圣生堕鲎堡鎏苎 a b s t r a e t i n s t n l c t i o nl e v e l p a r a l l e lp r o c e s s i n gi s t h ek e yt e c h n o l o g yt o i m p r o v et h e p e r f o 潮a n c eo fc u f r e n tp r o c e s s o f s ，w h i l et h ec o n 拄0 1d e p e n d e n c e sc a u s e db yb r a c h e s b e c o m eb o t t l e n c c k so fe x p l o i t i n gi l p t h e f o r e ，t h ei n s t m c t i o ns e t so fr c c e n tv l i w d s p so 抒e rs u p p o nf o rb r a n c 行e ee x e c u t i o no fc o n d i t i o n a ls t a t e m e n t si nt 王1 ef l o 册o f s o c a l l e dc o n d i t i o n a li n s t n l c t i o n s 1 no r d e rt oe x e nt h ea d v a n t a g c so fs u c hk i n d i n s t m c t i o n s ，t h i sp a p e r ，a i m i b ga ti 堇h p f 口v i n gi l pa sh i g ha sp o s s i b l e ，d o e sae k e p r e s e a r c ho np f e d j c a t e de 黼e u t i o n ，m 越n gm a i nc o n t r i b u i o n sa sf o l l o w s ： 1 ac o m p j j e r 抒a m e w o r kf b rp r e d j c a t e de x e c u 6 0 nj sd e s j g n e da 1 1 di m p l 啪e n t e d 。 b a s e do nt h er e g i o no fh y p e r b l o c k ，t h e 肭m e w o f kr e s o l v e sp r o b l e m sc a u s e db y 凡u i f _ c o n v e f s i o 氇a i | ds 哗p o n sd s p sc o n d i t i o n 班i n s 打u c t i o b se 腩e t i v e l y ，a n dp r o v i d e s l a 礓e rs p a c ef o rs c h e d u l i n g 趾do p t i m i z i n gm o 【l u l e st oi m p r o v ei l p 2 p r e d i c a t e s p e c m ca n a l y s i s a i l do p t i m i z a t i o n sa r ep r e s e n t e d i no r d e rt od o o p t i m i z a t i o n ，s c h o d l l l i n ga n df e g i s t e ra l l o c a t i o no nt l l ep r e d i c a t e dc o d em o r ee f f l c i e n t l y ， w e 是r s | i n 拄喇驻c ep r e d i c a l ea 肋l y s i ss y s t c m ( p a s ) b 丑s e d 醐b i n a f yd e c i s i 鞠d ；a g f 锄， w h i c hi sp r o p o s e db yj o h nw s i a se t c ，a n dt h em e t h o do fd a t an o wa 1 1 a l y s i su s i n g 胁d i c a t ef l o wg r a p h a n dt l l e n ，ap r o c e d u r eo fp r e d i c a t eo p t i m i z a t i o ni sp u tf o n v a r d ， w h i c hi n c o 驴r a t e sm ea r c h t e c t u r ec h a r a c t e r i s t i c so fv l i wd sp ，i h ep f o c e d u r eu s e s t h ef e l a d o n sa m o n gp 础i c a t e sp f g v i d e db y a st os i m 瓣i 每p r e d i c a t ee x p f e s s i o n s ，s u c h t h a t 氇ec o n h 静ll o 西cb e c o m e ss i m p l e r ，a n dt l l on u m b e ro fu s e dp r e d i c a t e dr e g i s t e r s b e c o q n e ss m a n e l 3 an e wr e g i s t e ra l l o c a t i o na l g o r i 也mf o rp r e d i c a t e dc o d ei sp r o p o s e d i no r d e rl o r e l i e v e 出ep r e s s u f eo fr e g i s 重e ff c q u i m e mb u g h t 姆p r e d 主e a t e de x e c l | t i o n ，w em o d i 玲 伽es t e po fc o n s 昀c 曲gi 融崩l c c 印) ho ft 璐d i t i o n 萄r e g i s t e r 萄1 0 c a t i o na l g o r i t h i n ， a n da c c o r d i n gt or e l a t i o i l s 踟o n gp r e d i c a t e s ，w ep r e s e n tan e wa 1 9 0 r i t f o f c o n s 廿u c t m gr c f i n e di n t e r f b r e n c e 卿h a sar e s m t ，f e g i s t e ra l l o e a t i o nf o fp f e d i c a t e d e o d ei sm o f cf a 蛀b n a la n d 块ee 8 s e so f 糟g i s e fs p 】1 i n ga r cr e d u c e d 拍er e s u l 招o fe x p e r i m e n td e m o n s t m t eh i 荫e rl l pi se 冲l o i t e d ，a n dc o d ee x e c u t i o n t i m ei ss h o r t e n e do b v i o u s l y s om ec o m p i l e rp e d b n n a i l c ei si m p r o v e dg r e a t l y 1 ( e ，7 w o r d s ： c o n d i t i o n a li n s t n l c l i o n s p r e d i c a t 勰e x e c u l i o n ，h y p e r b l o c p r e d i c a t ea n a l y s i ss y s t e m ，p r e d i c a t eo p t i m i z a t i o n ，v l u d s p r e g i s t e ra l l o c 靠t i o n ， c o m p i l e ro p t i m i z a t i o n 国防科学技术大学研究生院学位论文 图目录 图1 1 课题来源示意图3 图2 1 谓诩攘行代码示倒6 图2 t 2 谁c o n v e r s i o n 代码示例7 图3 1 谓词全转换的代码示例l o 图3 2 基予h y p e r b l o c k 的编译框架l l 图3 3i m a p c t 编译前端结构1 2 图3 4l c o d e 肉部表示的层次结构1 4 图3 5 基本块的选择示倒1 5 图3 6 选择基本块的算法1 6 图3 7 尾复制算法1 7 图3 8 尾复制算法的应用实例1 8 图3 9 循环剥离算法1 8 图3 1 0i o o pp e e l i n g 技术示例1 9 图3 1 1 经i f _ c o n v e r s i o n 转换看的h y p e r b l o c k 1 9 图3 1 2r k 转换算泫2 0 图3 。1 3 计算后支配集算法2 1 图3 1 4 计算控制依赖集合算法。2 2 图3 ，1 5 控制流图示例2 2 图3 1 6 确定r k 函数2 3 图3 1 7 扩大函数k 的定义2 4 图3 1 8 代码生成器框图2 5 图4 1 谓词代码示例3 0 图4 2 区间有限域表示示例3 1 图4 t 3i t e 范式的b d d 3 1 图4 4条件b d d 3 2 图4 5谓词b d d 3 3 图4 6 谓词流图示静j 3 4 图4 7 谓词块添跃变量定义使用集合的计算3 6 图4 。8 谓湖优化代码示例3 7 图4 9 谓词优化过程3 7 图4 1 0 谓词定义代码3 8 图4 1 1w c 中的一段循环代码示例3 9 旦堕型兰茎查盔堂竖至兰堕主垃鎏苎 图5 1 谓词代码， 图5 2 图5 3 图5 4 图5 5 图6 1 图6 2 ( a ) 传统干涉躅，( b ) 糕化干涉图 计算生命周期的算法 建立精化干涉图的算法 图着色算法4 8 编译优化后的加速眈5 2 y h f 孓d s p 7 0 0 与t m s 3 2 0 c 6 0 0 0 的编译优化加速比豹对扰图5 4 v 蚪甜钙 国防科学技术大学研究生院学位论文 表目录 表2 1 表3 1 表3 2 表3 _ 3 表4 1 表4 _ 2 表6 1 i m p a c t 渭词定义指令的语义 图3 1 5 中基本块的控制依赖集合 不带条件谓词的谓词定义指令的注释一 带条件谓词的谓词定义指令的注释 w c 示例代码谓词优化前调度情况表 w c 示例代码谓词优化后调度情况表 m i b e n c h 基准测试程序组一 7 2 3 2 6 2 7 4 2 4 2 5 0 v l 独创性声明 本人声明所星交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文申不包含其他人已 经发表和撰写过的研究成果，也不急含为获得国防莘串学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文题目： 基量遮遢挂筮数缝竖佬毡燕垄鲤竖窒生塞巍 学位论文作者签名： 王匡i 聋日期：如d 多年f 月侈日 学位论文版权使用授权书 本人完全了解国防科学技术大学袁关保留、使用学位论文的规定。本人授权国 防科学技术大学可毅保留并向西家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阏和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复剁手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目： 基王逼翊执短煦编竖位毡技盛鲍殛窀曼塞塑 学位论文作者签名 俸者指导教帮签名 l 0荔矧。 1 日期：j 瞄年f f 月日 甚期：如国一年f f 月，咱 国防科学技术大学研究生院学位论文 第一章引言 本意首先说明课题的研究背景及意义，然后在介绍国内外相关研究的旗础上， 概括了本文的主要工作和创新，最后给出了文章的组织结构。 1 1 课题背景与意义 现如今，高速数字信号处理器( d s p ) 在社会生活的各个领域已得到广泛应用， 除了在发展初期的数字移动电话、无线电基站、中心局交换机等通信应用领域外， 邋来也在向网络、雷达、声纳、医用仪器、图像处理、信息家电等领域不甑拓展。 据预测，到2 0 0 7 年d s p 的市场将达到5 0 0 亿美元i lj 。 睫羲d s p 在多媒体和宽带通讯按术的广泛瘦弼，d s p 应用程净鹄复杂度也在 不断增加，这导致使用低级语言来编写特定的应用程序，不但难度大、费时而且 效率不裔。因此，现在的d s p 应掰程序的编写大多采用高级语言，如e 语言，这 必然要求提供与d s p 芯片配套的编译器，实现从高级语言源代码到目标机对应汇 编代码的转换。即可编译性已成为现代d s p 区别于传统d s p 的重要特征1 2j 。另 方恧，几种薪一代的d s p 体系结构被提出并用于实现离速运算，其中比较典型的 是超长指令字( v l i w ) 结构，该结构的尼著特点是含有多个功能单元，能同时并行 执行多条捂令，但硬件控裁简单，指令并行牲完全出编译程澎在编译赣闻确定p 】。 综合两个方面可知，编译程序已成为v l l w d s p 性能发挥的一个关键部分。 为了充分发挥v l l wd s p 芯片的性能，编译系统在满足正确性的前撮下，要 尽可能地对代码进行优化，以便不断提高指令级并行度，充分利用有限的机器资 源，缩短代码的执行时间。机器相关的各种优化技术，例如指令调度，通常需要 在一个较大的范围进行才有助于其优化性能的发挥，而程序申分支指令的存在， 使得基本块的规模变小，从而缩小了可供调度的范围，大大降低了调度性能i 4j 。 鼗终，分支居的指令调度需要擐据分支豹执行结果进行，两分支指令的延迟又搦 对较长，这将导致流水线较长时间的停顿，从而严重影响代码的执行时间。一种 常见豹辫低分支延迟影响的方法是采用分支预测，都根据程缪特征预测调度菜 支的指令。然而，该策略存在着不容忽视的问题，例如，黪程序很难进行准确 的预测；当预溯失败时，作废预测执行指令的工作需要较大开销。所以，为了更 好的进行优化，就应该有效地处理分支和分支引起的控毒4 相关。 针对分支带来的问题，一种更赢接的处理方法就是消除分支。采用此法的比 较常见的技术谓词执行技术被提出”1 。该技术消除了程序中的分支指令，把 程序中的控制相关转变为数据相关，从而解决了分支带来的系列问题，使得多 条控制路径上豹指令合菸到一条路径。研究结粜表明：合并多个控制流能够将指 第l 页 霸防科学技术大学研究生院学位论文 令级并行增加到原寒的3 倍【5 】，能够有效地提离其他代码变换技术( 懿软流水和 模块调度) 的性能，而且谓词执行技术能够平均消除2 7 的分支以及5 6 的分支 预测错误【6 ，”j 。 本课题正是在学院研制的一款v l l wd s p 对应的已正确运行的编译器的基础 上，结合芯片自身体系结构特点，实施谓词执行优化技术，从而消除了分支带来 豹缺陷，提高了指令级并行度，缩短了代码执行时问，最终使得该款v l l wd s p 芯片豹性能褥到了受好她发挥3 9 ，4 。 综上所述，本谍题的研究既密深刻的理论意义，又有实际的应用份值。 1 2 相关研究 谓词执行技术的研究源于1 9 8 3 年，a l l o n 等人首先提出了i f _ c o n v e r s i o n 技术【4 1 ， 即通过将控制相关转换为数据相关来优化代码；接着，f e h 撕t e 等人提出了基于程 序相关图的i f c o n v e r s i o n 算法 7 1 ：惠酱实验室的p a r k 和s c l l l a j l s k e r 对f e r r a l l t e 等 人的算法遴行改进，提出了被广泛使用的r k 转换算法 葚j ，我们在文中就采用了 此算法。 为解决全消词转换带来的资源缺乏的闯题，r a i n e rl e u p e 稻提出了一种选择算 法1 9j ，即擞据保留分支控制流和实施谓词转换题种实现方襄下的执行时闯，选择 时间较少的方案来实施。然而，采用此种算法可能会因缺乏对程序行为的考察而 造成代码平均执行时间较长。m a l l l k e 和d a v i dc l i n 等人引入了h y p e r b l o c k 区域结 构l ”j ，其思想是通过对程序行为的考察，根据一定的启发式规则，选择部分基本 块来构造h y p c r b l o c k ，对进入区域的路径可优先分配资源，这便减少了资源竞争， 便于谓词执行优化技术性能豹发挥。本文在此蚋k o c k 区域结构豹基础上，提 出了很好的支持d s p 条件执行指令的编译框架，整个课越正是在该框架下舞屡的。 引入谓词之后，为了更好地进行指令调度和寄存器分配，需要对谓溺数据流 进行分析。l o r ic a t e r 等人提出了谓词相关的静态单独赋值的方法】，2 0 0 0 年， 他们又发表了基于谓词的路径分析与熏命名的文章j 。s a m a h l k e 等人给出了谓 词层次图i j ，r + j o b n s o n 等人建立了谓词查询系统】，这两种方法都能准确地分 析出谓词赫的某些关系，僵不全面且都存在一定的局限性。a u g t l s t 等人提出了用 二进制决策图( b i n a r yd e c i s i o nd i a 掣黜，b d d ) 柬准确遣表示谓调和条件之间的逻 辑关系 l “，根据逻辑关系进行带谓词的数据流分析却程序决策逻辑优化( p f o g f a m d e c i s i o nl o g i c a lo p t i m i z a l i o n ，p d l o ) ，尽可能减少谓词的数目，以便节省对谓词 寄存器的使用。 对代码实施谓词执行优化技术后，为了缓解寄存器分配的压力，需要对传统 的寄存器分配算法1 2 。2 6 】中建立干涉图一步进行改进，即建立精化的干涉图。钳对 第2 页 国防科学技术大学研究生巯学倪论文 此问题，e i c h e n b e r g e r 和d a v i d s o n 提出了基于p f a c t s 谡词分析法的构建算法 ”，d a v i dm g i t 儿e s 等人提出了基于谓词划分图的构建算法【1 6 】，但这两种方法 都存在定的局限性。 本课题正是在这些前人们所做工作的基础上，结合我们j 占片自身体系结构特 点，对谓词执行技术的相关内容进行石井究，并将研究成果在我们的编译器上付诸 实现。 1 3 主要工作与创新 本课题来源于国家8 6 3 计划“飞腾工程”项目，如辫1 1 所示。该矮匿研制的 y h f t - d s p 7 0 0 芯片是一款基于分簇v l l w 的裹性能定点d s p ，其“c 编漆器”子 项目的任务就是为y h f t _ d s p 7 0 0 芯片构造一个正确高效的编译器，实现从c 语 言源代码到对应目标机汇编代码的转换。 “飞腾工程” | i 基于v l l w 豹定点d s p l i c 编泽器 i 本课题 图1 1 课题来源示意闰 本课题正是在“c 编译器”子项目已实现了一个功能正确的编译器的赫础上， 实旌了谓词执行编译优化技术，具体说来，主要包括以下三个方露的工 乍： 第，提出了支持谓词执行的总体编译框架。为了尧服分支跳转指令的缺陷， 高性能v l l wd s p 的体系结构提供了对条件执行指令的支持。为使此指令的优势 得以充分发挥，文中提出了基于h y p e r b l o c k 区域结构的编译框架，该框架克服了 全谓词转换带来的问题，为指令调度和优化模块提高i l p 提供了较大空间。整个 谋题正蹙在此框架下开展进行的。 第二，给出了谓词楣关的分树与优化。对代码实施谓词转换后，为了更好地 进行代码优化、指令调度和寄存器分配，文中黄先分绍了j o h nw l s i 豁等人提出的 基于二进制决策图( b d d ) 的谓词分析系统( p r e d i c a t e da j l a l y s i ss y s t e m ，p a s ) 和基于 谓词流图的数据流分析方法；然后，在p a s 的纂础上，提出了结合芯片自身体系 结构特点的谓词优化过程。该优化过程使得程序的控制决策简单化，决策高度降 第3 页 因防科学技术犬学研究生院学位论文 低，对浸词寄存器的使用减少，从面提高了编译性能。 第三，提出了适于谓词执行的寄存器分配算法。为了缓解谡词执露带来的寄 存器分配聪力，在谓词分析系统基础i 二，对传统寄存器分配算法中建立干涉图一 步进行改进，提出了一种新的建立精化干涉图的算法。该算法较合理地对带谓词 的代硝分配了寄存器，减少了寄存器溢出情况，缩短了代码执行时间，获得了较 好的性能提高。 1 4 本文结构 第一章，首先说明了课题的研究背景及意义，然藤在介绍国内夕 相关磅究的 基础上，概括了本文的主要工作和仓4 叛，最后给出了文章的组织结构。 第二章，首先给出谓词执行技术的基本概念；然后介绍i m p a c t 体系结构中 的渭词执行，着重阐述各种类型的谓词定义指令的语义；最后给出目标机 y i f d s p 7 0 0 芯片的体系结构及其对谓游执行的支持。 第三章，在h y p e 南l o c k 区域结构的基础上，针对y h f 嚣d s 7 0 0 芯片体系结 章句的特点，提出了支持疆词执行优化技术豹绽译框架，然意对框架串的每一步进 行了具体阐述。 第四章，酋先详细介绍了j o h nw s i a s 等人提出的种基于b d d 的谓词分析 系统；然后，概括阐述了基于谓词流圈的数据流分析方法，最后，在p a s 的基础 上，提出了结合芯片y h f t - d s p 7 0 0 自身体系结构特点的谓词优化过程。 第五章，首先概括介绍了基于图着色的传统寄存器分配算法，然后，在谓词 分丰厅系统基础上，对传统寄j | 筝器分配算法中建立二f 涉图步进行改遂，提崮了一 种新的建立精他干涉图的算法。 第六章，把支持谓词执行的编译框架、谓词分析系统、谓调优化过程和改进 的寄存器分配算法在学院研制的y h f t _ d s p 7 0 0 芯片的编译器上实现，通过基准 程序测试，给出实验结果，并进行性能分析和评测。 第七章，概括全文，总结课题所做工作及研究成果，并对进一步的研究进行 了展望。 第4 页 国防科学技术大学研究生院学位论文 第二章谓词执行技术 本章将首先给出谓调执行技术的基本概念；然后介绍l m p a c t 体系结构中的 谓词执行，着重潮述各种类型的谬词定义指令的语义；最后给出目标橇 y h f t _ d s p 7 0 0 芯片的体系结构及其对谓词执行的支持。 2 1 基本穰念 所谓谓词执行就是种消除分支，把程序中的控制相关转换为数据相关的技 术i ”。该技术通过i b c o n v e r s i o n 过程首先将条件分支转换为谓词定义指令，从而达 到消除分支的目的；然后，对依赖分支执彳亍的指令增加布尔型源操作数条件 谓词，使得指令的执行与否依赖于萁对应条件谓词的值。如此控制相关转换为数 据相关，多条控裁路径合并为一条路径，指令呈线性缎织方式，这为君两阶段的 优化和调度提供了熨大的自由空间，对编译性髓的提高大存裨益。同时，条件转 换能够消除一部分难以预测的分支，从而避免了运行时因分支预测失败造成的性 能损失。 如图2 1 所示，( a ) 为一段包含分支的源代码；( b ) 为( a ) 中的代码实施i f _ c o n v e r s i o n 技术后的线性代码；( c ) 为调度后的代码。可以看出，通过i c o n v e r s i o n 过程，( a ) 中的条 牛分支指令( 1 ) 被转换为( b ) 中定义谓词p l 和p 2 的指令，当比较条件c o n d l 的结果为囊时，p l 就被赋值为l ，p 2 被赋值为o ，否则p l 裁被斌值为o ，p 2 被赋 值为l ；( a ) 中的条件分支指令( 5 ) 被转换为( b ) 中定义谓词p 3 秘一的指令，当比较 条件c o n d 2 的结果为真时，p 3 被赋值为1 ，p 4 被赋值为o ，否则，p 3 被赋值为o ， p 4 被赋值为1 ：对于依赖于此两个分支的指令( 2 ) 、( 4 ) 和( 6 ) ，都被转换为带谓词源 操作数的谓词( 条件) 执行指令，当谓词p l 为1 时，指令( 2 ) 执行，r 1 的值增加， 当谓词p 2 为l 时，指令( 4 ) 执行，r 1 的值减少，当谓词p 4 为l 对，指令( 6 ) 执行， r 2 瓣值增加；否则，当这些消词执幸亍指令的条件谓词为o 时，( 2 ) 、( 4 ) 和( 6 ) 三条指 令就楣当予空操作，不改变任凭俊。这保持了艨来的分支语义，囝对被转换焉的 指令( 2 ) 、( 4 ) 和( 6 ) 的取指操作不必等待分支结果得到后进行，可无条件地被取指， 然后根据条件谓词的值来决定是否执行。如此分支指令被消除，控制相关被变为 数据相荚，四条执行路径合并为一条路径，对于三流出的处理器，原来的代码要 四个周期的调度时间，转换后的代码只需两个周期，转换后的指令( 2 ) 、( 4 ) 和( 6 ) 可 同甜执行，如图2 。l ( c ) 所示。可见，谓词执行的实施可以允许更多指令重叠执行， 消除了控制楣关，从焉可更好缝提高l l 。p 。 第5 页 国防辩学技术犬学研究生院学位论文 ( ) p i ，p 2 ；c o n d l ( 2 ) r 1 _ l 十t ( 5 ) p 3 ，面= c o n d 2 i ( 6 ) r 2 = r 2 十l ( p 4 2 。2 基予l m p a c t 体系结构的谓词执行 如图2 2 ( a ) 是一段带有分支嵌套的c 代码，i m p a c t 前端通过i f _ c o n v e r s i o n 转 换，得到如图2 2 ( b ) 所示的谓词代码。( a ) 中的四个i f 条件分支转换为( b ) 中的前五 条谓词定义指令，( a ) 中的a ，b ，c ，d 四条语句被转换为( b ) 中的后四条谓词执行指令。 接下来，我们将介绍( b ) 代码中各条语句的语义【2 3 ，2 引。 第6 页 国防科学技术火学研究生院学侮论文 i f f x 一8 x 8 ) 8 t m 匕a ； i f ( x = = 0 ) s t m t b ； e l s e s t l t c ； i f x 一8 ) p 1 ) p 3 t ，p 2 o f 慧r 1 8 ) ( p 3 ) p 4u t = ( r 1 = = 0 ) ( p 2 p 5 u t = ( r l ( b ) 谓词转换后的调度代码 图3 1谓词全转换的代码示例 图3 1 ( b ) 是源代码( a ) 进行谓词转换后的优化调度代码。对于三流出处理器，图 ( a ) 中的代码需要三个周期的调凄时间，丽转换嚣的代码( b ) 却需要四个周期的调度 时闽。为舞谓词转换后，反而增加了调度时问昵? 这是因为合并路径之嚣，每条 分支路径上的指令都要调度，这便增加了要流瞧指令的数露，从薅等致指令的调 度时间被延长。由此可见，并不是只要实施谓词执行优化就能缩短调度时间，性 能的提高与否还取决于被选择进入谓词区域的分支路径是否恰当。如果编译程序 选择了合适的分支实施谓词执行，那么它可以在很大程度上提高性能，否则，可 能反而使性能鞠显下降。所以，并不髭将所有的指令都要进行谓词转换，应在保 醋分支控制流程谓词转换之润进行权衡。 针对此，r a i 搬l e u p e r s 提出了一种选择算法【9 】：首先建立两种方案下执行时 间的评测表，然后根据评测表选择时间较少的方案束实施。其中评测表的建立是 基于对分支语句中执行时间较长一支的评佑。然而，当执行时间较长的一支实际 不经常执行时，采用此种算法可能会造成平均执行时间较长。为了克服全谓词转 换的缺陷，m a l l k e 和d a v i dc l i n 等人引入了h y p e r b l o c k 区域结构 o i ，其思想是 第1 0 页 胬防科学技术大学研究生院学位沦文 通过对程窿行为的考察，根据一定的癌发式规娴，选择部分基本块来构造 h y p e f b l o c k ，对进入h 择e r b l o c k 区域的基本块实施谓词转换、优先分配资源，如此 可减少资源竞争，从而昭决了全谓词转换荣来的资源缺乏问题。硬究表明，该方 法便于谓词执行优化技术性能的发挥。其中所谓的h y p e r b l o c k 是指i ；担一些基本块 组成的区域，该区域只允许有一个入口，但可有多个出口。 本章正是在h v p e r b l o c k 区域结构的基础上，针对y h f t - d s p 7 0 0 芯片体系结 构的特点，提龋了支持谓词挠行优化技术的编译框架，整体结构如图3 - 2 所示 p o 4 ”。该框絮酋先由l m 黔c t i 端编译产生中闯代码l c o d e ，然后挑选出合适的 基本块来构建h y 辨r b l o c k 区域，露对区域肉黔代码进行l o “e r s i o n 转换，之后进 行谓词相关的分板与优化，最后经过编译后端的代码生成器输出汇编调度代码。 接下来，我们将分小节对框架中的每一步进行舆体地介绍。 i m p a c t 编译前端 业 l 中闼代码 守 i 选择基本块i u 构建h y p e r b l o c k l j i f c o n v e r 鲥o n 转换 i ， 谓词分析与优化 l j 代码生成器i 图3 2 基于h y p e r b i o c k 的编译框架 3 1l m p a c t 编译前端 编译前端我们采用i m p a c t 前端( 类似s u i f 编译程序) ，该前端首先对c 语 言编写的代码进行词法、语法和语义分析，然后进行机器无关的优化，最后将其 转化为机器无关的中蝎代码i 。c o d e 。i m a p c t 蓠端结构如图3 3 掰示 2 ，大熬可 分为以下六个步骤进行。 第1 1 页 国防科学技术大学研究生院学位论文 1 ，l 熹刭篓卜叫p c o d e 产一f 1 a t t e n i n g 卜一p c 。d e t oe l 一一一 一一一“_ _ l _ r 一【 一一i 一，。一一 7 8 。芋8 。! w s 。e c ， ， 上： 二ll r j h 等8 i l 。名怒。h 。劂；。卜7 a e 产 p r 0 吣lr 。 = = j 二一一：二：j 一 。尝； 一二影曲，l 9 戮? 。h k 础 l j 。l 一 j 3 1 1 生成p c o d e 圈3 3l m a p c t 编译前端结构 正如图3 3 所示，i m p a c 罩蘸端首先使用e d i s o nd i e s i g 芏ig r o u p ( e d g ) 工其 2 0 1 ， 对输入的c 源程序进行k & 刚a n s i c 词法、语法分析，生成p c o ( 1 e 。p c o 曲语义上