（计算机科学与技术专业论文）面向vliw+dsp的c编译系统研究与实现.pdf

国防科学技术火学研究生院学饿论文 摘要 v l i w d s p 含有多个功能单元，能并行执行多条指令。但是指令执彳亍时所占用的功能单 元和指令执行时间通常由编译程序在缡译期间瓣态救援定。所以编译穗彦是炙：发基于v l i w d s p 应用中的关键。 在这种背炭下，我们通过仔缨分椽y h f t d 2 ( 采用v l i w 体系结构) d s p 豹姆点，缝合 现代的编译技术初步实现了面向y h f t d 2 的高效c 语言编译程弹。该编译程序在机器描述 的驱动下，采用i m p a c t 作为编译前端进行机器无关的词法分桥、语法分析产生中间代码 l c o d e ，然后经过代码淀释、调度和寄存器分配| 夏及优化最后生成高效的蟊标机y h f td 2 汇编代码。 本论文诿缫分绍了蒸予萋毛嚣接述驱动静编译技术，并给密了y h 瞳d 2 酶瓤器搐述，详 细介绍了代码、挫释，指令调度以及一些机器无关和机器相关的优化，并给出了主要的簿法 释典登安镶。冀孛： 夺代码注释。采用等价变换的方法把编译前端生成的机器无关中间代码l c o d e 注释 为与曩器褪y h f t _ d 2 榴芙蛇孛阅代码m c o d e 。遴逶遵嚣l ：l 窝l ：n 注器璨涯了滚释 的正确性，同时进行n ：l 注释来提高编译程序的性能。 夺枧器搂述。使翅h m d e s 规器攒述语言砖嚣标极￥h 瞳d 2 戆专睚器资源、攫令格式、 指令集、指令惩时、指令使用资源情况和指令映射进行详细的描述，并提供畿询 接口向绽译程序的其他模块提供目标枫信息。 审调度。针对目标机y h f t d 2 酌分簇特憔，调度采用先避行指令划分，然后再簇内 调度的方法。其中指令划分通过考虑指令间的依赖等愦况来攒定指令执往对所在 豹功能单元簇，簇内调度使雳教进的l i s t s c h e d u l e 针对目标机y h f td 2 的各种资 t 源限制米指定指令的执行时间和具体执行功能单元。 夺优纯。现阶段编译程廖掰骰的德证包括梳器无关豹常簸侥纯稻露标视鞠关的优化。 机器无关的常规优化主要改进i m p a c t 优化技术，对m c o d e 进行常规优化。目标机 耀关静饶键圭簧跫逶j 蕊分褥嚣标梳匏褥点，采瘸基本较扩震等手段来提高整个编 译程序的性能。 逶避对我锭掰实臻豹绫译糕痔襄齑鼹编译稳痔c c s 进行毪能毙较测试，表葫我稻缡译 程序在并行度和执行时间上都裔较高的性能。同时在研究实现过程中，我们发观了一必可 以继续激进的方蕊，本论文最溪藏这些方匿提感了一些建议。 荚键谰：v l i wd s p编译枕糕搓述代碣注释渊廑 蜣 基糖科学技术大学研巍生院学位论文 a bs t r a c t v l i wd s ph a sm u l t if u n c t i o nu n i t st h a tc a l le x e c u t e o p e r a t i o n s i n p a r a l l e l b u t t h e e x e c u t i v ef u n c t i o n ，u n i ta n dt h ee x e c u t i v et i m eo fo p e r a t i o na r ed e c i d e db yc o m p i l e ri n c o m p i l i n g m t i m e s o t h ec o m p i l e ri st h e k e y t oi m p l e m e n ta p r o g r a m w h i c hb a s eo nv l i wd s e u n d e rt h i sb a c k g r o u n d ，w ea n a l y z et h ef e a t u r e so fy h f t _ d 2d s p c a r e f u l l y , a n dc o m b i n e m o d e m c o m p i l et e c n a o t o g y w eh a v ei m p l e m e n t e d a 箍e f f i c i e n tc c o m p i l e rf o ry h f t _ d 2 ，o u r c o m p i l e ri sd r i v e n e db ym a c h i n ed e s c r i p t i o n w ea d o p ti m p a c t a so u rc o m p i l e r sf r o n t e n d w h i c hd os o m em a c h i n ei n d e p e n d e n tw o r k s ，a n dt h e n 0 1 1 1 c o m p i t e r d oc o d e - a n n o t a t i o n ， s c h e d u l i n g ，r e g - a l l o c a f i o n a n d o p t i m i z a t i o n s ，o u rc o m p i l e ro u t p u t t h ea s s e m b l yc o d ef o r y h f t _ d 2 i nt h ee n d t 撼st h e s i si n t r o d u c e st h ec o m p i l et e c h n o l o g yw h i c hi sd r i v e n e db ym a c h i n ed e s c r i p t i o n ， a n d p r e s e n t sm d e s o fy f h td 2 ，a n di n t r o d u c e sc o d e a n n o t a t i o n ，s c h e d u l i n ga n d o p t i m i z a t i o n s a n ds o m e a l g o r i t t u 般s 夺c o d ea n n o t a t i o n c o n v e r tm a c h i n e - i n d e p e n d e n tl c o d ei n t om a c h i n e d e p e n d e n tm c o d e t h r o u g he q u i v a l e n t c o n v e r s a t i o n s 。1 ：1a n d1 ：na n n o t a t i o n sh a v e g u a r a n t e e d t h e c o t t c c t n c s s 。v i ec a n i m p r o v ec o m p i l e r sp e r f o r m a n c et h r o u g h n ：la n n o t a t i o n 矗tt h es a _ m e t i m e 夺m a c h i n ed e s c r i p t i o n ，w eu 辨h m d e s 协d e s c f i p tt h er e s 0 1 n c e ，f o r m a t ，o p e r a t i o n ， l a t e n c y ，r e s o u r c e - u s i n ga n do p e r * m a p p i n gi n f o r m a t i o na b o u ty h f t - d 2 ，a n dp r o v i d e e x t e r i o rq u e r y i n t e r f a c ew h i c hc a l lb eu s e db yo t h e rm o d u l et og e ti n f o r m a t i o na b o u t y h f t _ d 2 。 夺s c h e d u l e w eu s e o p e r a t i o n - p a r t i t i o n t o a s s i g ne a c ho p e r a t i o n s e x e c u t i v ec l u s t e r t h r o u g hc o n s i d e rt h ei p 螽o r m a t i o nb e t w e e no p e r a t i o n s ，a n dt h e nw cd ol i s t s c h e d u l ei n e a c hc l u s t e rw h i c ha s s i g n e de x e c u t i v et r a c t i o n u u n i ta n de x e c u t i v et i m ef o re a c h o p e r a t i o n ， 夺o p t i m i z a t i o n s + w e u s ei m p r o v e d o p t i m i z a t i o nm e a s u r e s o fi m p a c tt od oo p t i m i z a t i o n s o fm a c h i n e i n d e p e n d e n t ，a n dw eu s ee x t e n do fb a s i c b l o c kt od oo p t i m i z a t i o n so f m a c h i n e - d e p e n d e n t ；t h e s eo p t i m i z a t i o n ss h o wg o o dp e r f o r m a n c e i no u r c o m p i l e n t h er e s u l t so fb e n c h m a r k t e s t i n gs h o w t h a to u rc o m p i l e rh a sh i g hi l pa n ds h o r te x e c u t i v e t i m eo f cs o u r c ep r o g r a m ，a n dd u r i n gt h er e s e a r c ha n d i m p l e m e n t a t i o n o f t h i sc o m p i l e r , w eh a v e a l s of o u n ds o m ea s p e c t sw h i c hc a ni m p r o v ec o m p i l e r sp e r f o r m a n c e ，t h i st h e s i sg i v es o m e a d v i c e sa b o u ti ti n 也ee n d k e y w o r d s ：v l i w d s p c o m p i l e m d e sc o d e a n n o t a t i o ns c h e d u l e o p t i m i z a t i o n 独创性声臻 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 曲研究成巢。尽我所知，除了文中特别加阻标注和教谢的地方外，论文中不包含 其健人已筑发表秘撰写过戆磅宠或聚，丧不惫含为获缛藿跨年粤擎技术夫学或英它 教商机构的学位或证书而使用过的树辩。与我一同工作的同志对本研究所做的任 何贯献均已在论文中作了明确的说明并表示谢意。 学谊论文题蓍：垂鲎竖! 篓窒驻煎越逢歪蕴逸童蔓塞拯 学位论文幸乍考签名鞋期：刍吗年熔月彭髑 学位论文版权使用授权书 本入党全了解围防科学技术大学有关像窭、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被套阕和倦阋；可良将学位论文曲全部或部分内容编入有关数据 痒涟专亍检索，可l ；之藩媛影露、缝毋蠛舞搓等爱裁手毅保存、汇藕学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目： 亘囱妲! ! 卫数煎! 麴湮圣叠魉窑盏塞趣 学位论文停者签名 作者指导教烯签毫 盔鱼。堕 露期：毒猡j 年级胃。| 弩冒 段期：伊3 年 溯谚毯 国防科学技术大学研究生院学位沦文 图目录 图l y h f t d 2c p u 内核结构图 强1 2 缡译程廖整体框架缓译程序， 凋2 1i m p a c t 前端结构 鼹3 ，lm b e s 交纛图 闰3 2m d e s 转化图 阁3 3y h f t d 2 机器描述结构图。 黼4 1 代码注释结构圈 网4 2 控制块注释算法c b _ a n n o t a t i o n 黼4 3 算法c o n v e r i n t o _ b b 图4 4 黧建基本块的源流信息算法r e b u i l d s f c f l o w 灏4 5 指令注释清嚣示意图 阌5 1 调度过獠示意图 强5 2 臻令划分过程示意圈 阔5 3 分层带权d a g 图， 阁5 ，4a l a p 算法 豳曩5c i t e n u m 计算弊法一 图5 6l a y e r n u m 计算冀法。 图5 7 带a 、f 、c 和l 的d a g 躐 阌5 8 确定功能单元簇流程图 豳5 9s e t c l u s t e r 算法 图5 1 0 指令划分例1 翔5 。l i 镬霜交叉通路酾c o p y 指令， 阕5 1 2l i s t s c h e d u l ej 建程和算法 强5 。1 3 弱代璃_ | 葶列及对应d a g 灞废霞先缀 网5 1 4 资源表格示意图 圈5 。l s 瓷澡表格解决黢毒l 过程示意霆， 图5 1 6 资源表格解决限制的综合实例 耀6 ，l 然本块蠹瓣平均搓令共行度 图6 2 旗本块内平均指令并行魔对比( y h f t _ d 2v sc c s ) ， 图6 3 执行时阙测试比较( y h f t _ d 2v sc c s ) 卫_邝般忽船船肼筋m娜娜詈毫船舶舶韵m船舶舾朋檬成属 一 一 | 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 ! | 一 一 。 f 一 ， t t ， 。 ， 一 一 t t ， j - t 一 ， 一 一 一 一 一 一 ， 。 一 一 一 一 一 一 一 一 ! | 一 一 一 一 一 一 一 一 一 一 一 一 国防科学技术犬学研究生院学位论文 表1 1 指令集与功能单元的映射 表6 ，l 极器资源配置 表6 2 机器指令延时信息 表6 3 机器资源配置 表目录 3 5 0 5 0 5 0 国防科学技术大学氍阡究生院学位论文 第一章引言 本濑首先介绍该论文的课题背景和意义，然后简要介绍目标机器y h f t ，介绍d 2 d s p 针对该嚣禄梳鹣编译稷滓实魂掰采焉懿技术路线帮国器国蠹稽关研究，最五分绍本论文的 基本结构和研究成果。 1 1 课题背景和意义 随蓠多媒体和宽带遁讯技术臼益广泛髂应阁，几种新一代的d s p 结构被提出并用于实 现高速的运算，其中典泌的是赫于超长指令字f v l i w ) 结构，如t m s 3 2 0 c 6 x 。在v l r w 结 梅中，一个显薷酌特煮虢是含京多个秘辘鼙元，缝闫辩并季亍执行多条撩令，毽是指令并行 执行硬件控制简单，指令并行性完全由编译程序在编译期间确定。编译程序通过指令调度 等掇关技末在编译期闻把不掇荚或无美瓣摇令安捧在鞘薅一个辩锋撬季亍，v 己f wd s p 磺 睾 只须解碣执行栩应的操作，而不需迸行指令并行的控制。这极大的减少了机器成本和设计 复杂度。嚣鼗缝译程彦楚v l i wd s p 拣躯发髯不可缺少瓣一令荚键鄂分； 同时随着d s p 体系结构的改进和威用程序复杂度的不断增加，使用低级语言来编褥特 定魄应用程序不但难度大、费时i 嚣且效率不毫。因此瑗褒豹d s p 应用穗枣编写大多采惩裹 级语言，如c 语言。采用高级语言能快速的开发应用稷序，但必然要求提供配套的编译程 序程序对应用程序的分橱、合理调度、把应用程序转化为对应嚣标机嚣鲍赢效正确的掰撬 行代码。因此编译程序是高级语言开发程序的不可缺少的部分。在应用程序的编译期间， 编译系统在满怒正确性的前提下，通过合理的调度方法尽量让更多的攒令充分利用有限的 机器资源，把不相关的指令安 # 在一超减少程序的执行时间。也就是编译程序将多条可以 同时执行的指令排在条超长指令字或一个执彳亍包中，这样既可以提供较高的指令级并行 度，鬻时又煞够使嚣拣机器其有简单的硬件译码和控索4 逻辑。 本课题通过研究传统的和现代的编译技术，为y h f td 2 ( 采用v l l w 体系结构) d s p 稳遥一个正确熬编译程窿，该编译程黟戮e 源程_ | 芋作为输入，经过诵法分橱、语法分毫 亍、 指令优化、调度和寄存器分配，指定每条指令的执行功能单元和每条指令的指令时间，最 终生成霾标援y h f td 2 豹汇编代码。 1 。2 爨标桩娃l s t _ d 2 援述 y h f t _ d 2 是一款高性能的定点v l l wd s p 4 8 】，图1 1 是y h f t _ d 2 的c p u 内核结构 强。y h f t _ d 2 采鬻v l i w 体系结构，舆有v 疆w 高并行往静特点；y 鞭f 乙d 2 禽有8 个功 能单元和3 2 个通用寄存器，自在一个时钟内执行八条无关的指令；y h f t d 2 使用一种 l o a & s t o r e 精麓猎令鬃，指令在多个功戆单元主撬行。我稍镳译程滓的鏊袜就是通过适 第1 焚 国防科学技术大学研究生院学位论文 当酶编译技术为程窿中豹每条搿令安摊在y h f td 2 上的执行时蔺稻y h f td 2 上韵执行 功能单元，同时尽量把无关的指令安排在同一个时钟周期内执行以发挥y h f td 2 的简并 辛亍度俊杰，减少程痔的亳l i 行对鬻。 瀚1 1 疆td 2 e p u 内核结稳阗 y h f td 2d s p 由三个主要部分组成：c p u 内核。外设和存储器。其中与编译程序有 关懿蹩c p u 悫狻孛豹数撵逶路。c p u 肖两个可越送行数据处骥懿逶爨a 霸b ( 数据邋路 在指令调度过程中也称呼为簇) 。每个邋路有四个功能单元( l ，s ，m ，d ) 和一个有1 6 个 3 2 位逶鼹枣存器魏骞存器文 孛。臻髭擎元撬嚣逻辑、像移、乘法、燕法鞠数据罨洼等操作。 两个寻址单元( d 1 和d 2 ) 专门负责通过l o a d s t o r e 指令完成寄存器缎与存储器之间的数 据传递。每个数据通路瓣三令甥悲单元( l 、s 、m ) 帮可爨遗避令交叉逶路访目另外数 据通路上的寄存器文件，可以通过交叉通路完成寄存器文件之间的数据交换。y h f t _ d 2 的嚣个数据通路八个功娆单元在一个对铮周期内执行八条撂令，其中 f 薯d 2 的攒令 集有几个显著豹特点会对编译糨序的实现造成影响： 1 每条指令可以在一个戏多个功能单元上执弦。如加法擐令a d d 就自在l 、s 积 d 功能肇元上执行，乘法指令m p y 只能执行在m 功能单元上执行，l o a d s t o r e 指 令只能在d 功熊单元上执行。 2 所有的捂令都怒可疆条件执行酌。如指令a d d 【r 2 】f r 3 ，r 4 就是一个条件执行 指令；如果条件寄存器p l 为1 刚执行该加法指令完成r 2 - - r 3 + r 4 。否贝q 不执行，就 像浚翥这条指令一样。 3 每条指令都有明确的功能单元等待时间和延迟间隙。 f td 2 每条指令的功能单 元等德嚣尊淘都憝1 个辩镑爝期，指令静延霹蓠藩分鬟菊0 令时钟鬻麓黼隙、1 个爵 钟周期间隙、4 个时钟周期间隙和5 个时钟周期间隙。如a d d 指令有一个时钟周 翅戆葵戆单元等德时闲襄0 个嚣誊镑躅麓豹延辩瓣骧，鼙只占蠲一令臻攀元瓣阉 且一个时钟内出结果。 4 。无关指令可以势零技行，y 珏f td 2 有八个功熊单元，麓撬嚣，条著行豹掺令。无 关指令是指满足 f td 2 资源限制的前提下阍时又满足数据依赖关系。如a d d 【r l 】f r 2 a 3 】和s u b 【r 4 】 r 5 ，r 6 】就可以著行捷行。 上两几点y h f td 2 的特性将直接影响着编译程序的具体实现。针对第一点，编译程 序首先就必须为每条指令设定自& 执行的功能罄元，考虑剿y h f t 育两个数搬通路(簇)，_d2 我们编译程序强指令调度过程首先就遴行指令划分以确定每条指令的执行功能单元簇。每 第2 页 国防科学技术火学研究生院学位论文 蘩指令都有黉确静功能革元等待对阕和延迟阉濠主要影响编译程序奄调度指令时必须满 足的功能单元冲突和数据依赖关系。无关指令可以并发执行主薅体现猩编译过程中在满足 资滚隈涮懿条锋下器量把受多翁指令交搀在霹令矮鬻撬芎亍，尽最大释疫静撬离指令的并 行度i l p 。 表l 是y h f td 2 掺令集与凄能擎元装映粪砉关系。 lu n i tm u n i tsu n i tdu n i t a b sm p ya 0 0s e ta d ds t 8 5 _ 酿。 矗b dm p a d 玳s h la o d 矗b s t h ( t 5 - b wo 肯骘埘1 d d um p y u s d d 2s h ra o o a hs t wc 1 5 - b i t o l f a e t ) t a n dm p y s ua n ds h r ua o o a ws u b 0 赫p 基q赫p y h转d i s 口s s h ll d 塞s u b a 6 c m p g tm p y h ub i r p ts u bl d 臼us u b a h c m p g t um p y h u s辱n r p ts u b ul d hs u b a w e 醚l 下m p y h s l i 8 s 0 8 2l o h uz e r o c m p l n jm p 荆lc l rx o rl d w l m 日dm p y h l ue x tz e r 0l o b ( 1 5 一b i t o f f s e t s - wm p y h u l sx t u8 nf s 女io # s e o z n e em 卢v h s l uvl o hf 1 5 - b i to f f s e t ) n o r mm p 、t hm v c tl d h uf 1 5 七i t 。确科体 k o tm p y l h u醚v kl d wt 5 一b i t 湘掌 o rm p y l u h sm v k hm v s d dm p y l 8 h um v k l hs t 日 s a ts 蜡p yn s t h s s u bs m p y h ln o ts 1 w s u bs m p y l ho r s u 丑us 酗p ￥h s u b c x o r z e 嚣o ；嚣蹴 褒l 攒令集与凌辘单嚣豹浚射 l 。3 相关研究 u m c 大学的h w u 教授领爵开发的i m p a c t ( 4 5 1 是针对i m p a c t - e p i c 型机器静商效可 蓬定磊标韵编译程滓，融经为s t a r c o r e l 4 0 4 8 j 产童了福疲豹编译程序。i m p a c t 编译程序主 体分成编译前端和编译厢端。其中前端主要对源程序进行词法、语法分析生成中间代粥， 然压对审淹伐翳迸行撬器无关静往亿，常冤蠡冬蠢清豫公共子表远式，常霆传撵，无瘸代鹳 删除等。编译后端则是主要进行目标机相关的工作，如注释机器相关的目标机中间代码， 然蜃进行提瘟戆凝器穗关熬铙诧，指令谖度帮寄存器分驻，最怒生残瑟淘鑫瓠瓤器斡汇编 代码。其中前端生成的机器无关中间代码l c o d e 作为编译后端的输入。而编译腐端生成的 是基标枫豹汇缡饯码。健t l m p a c t 编译蜃蝼为x 8 6 、a m d k 6 翻s t a r c o r e l 4 0 帮煮一套突整 第3 页 国防科学技术大学研究生院学位论文 的程守模块，帮i m p a c t 编译程序后瑞是硬编码的，生成面向v l r wd s p 机器的编译程序 难度较大。 t r i m a r a n m 螂编译毪窿由i m p a c t 、e l c o ”】、c a r - s l 家研究机构豹产品综台两成。其中 t n m a r a n 利用心伸a c t 编译程序作为擞个编译程序的前端，进行源程序的词法、语法分析、 掇器无关豹中阉代羁生戏，我稻编译程净龟是健属i m p a c t 佟为编译麓端迸雩亍源茬痔的词 法、语法分析、机器无关的中间代码l c o d e 生成。e l c o r 作为t r i m a r a n 编译程序的后端， 进幸亍冀令调度葶爨毒存嚣分配。囊予i m p a c t 傻惩鹣是中润伐磁l c o d e ，瑟e l c o r 捷燕鹣是 中间代码r e b e l ，所以楹前端和后端之间首先进行中间代码的注释，把l x ：o d e 注释成r e b e l 。 c a r 俘为最慝郏分进纾模拟势匿形化中闻结聚显示，方便查蠢各个除段鸵续果售感。餐 t r i m a r a n 编译糨序主要面对的鞠标机是i - i p lp d 机器，修改为丽向v l l w d s p 机器具村较 大的难度。 s u i f 编译獠序是s t a n f o r d 大学编译研发小组生成的面向可扩展并行结构的编译程j 葶。 其中s u 球使用麟c t 前端作为整个编译程序的前端，进彳亍词法语法分析和机器无哭的 侥亿，s u 瑾编译程序嚣端使用在蟊标机器描述的辅助下进行各种机器相关的工作。 g c c 编译程序是 哪的一个自由软件，源码开放，提供了很多有效的优化功能，但 耍生蔽蕊商v l l wd s p 薪螫瓿糕魏编译程亭，其修改工 乍十分巨大。 综含当前主要研究，针对面向y f h t - d 2 的编译程序，我们选用i m p a c t 作为我们的 缡译翦璐来完戏词法、语法、部分筑仡帮生成l c o d e 中麓我羁。在诧基确上，撩逸y h r t _ d 2 的编译厢端，在编译后端进行代码注释生成目标机相关中间代码m c o d e ，再执行寄存器分 聚毒瑟搓令谖瘦以及一些撬器技像，最爱生成y h f td 2 熬汇编代码。 l 。4 编译程序整体结构 针对目标机y h f t的特性，面向y h目标机器的编译糨序的编译前端采用 琢曩敞零蓠端 炎叛_ d 2 编译疆淳) ，透过f td2suifi m p a c t 麓端送行诵法、谶法等分析稻飘糕无 关的优化，最终生成机器无关的中间代码文件l c o d e 。然后在我们编译稷序的后端对l c o d e 进行各耱搡佟，最终生成稷器挺绩我璐。窝1 2 是我稻缡译程净戆总钵维梅嚣。 正如图1 2 所示，我们编译程序【2 1 0 2 ，2 5 , 3 7 , 4 7 , 4 9 , 5 0 z # 要分成两个大的部分：编译前端和编 译螽蠛。其中裁溃是i m p a c t 。编译藤溅翼建是凌系裂与基拣凝v r f rd 2 褪荧魏模块擒 成，主鼹分成三个阶段( p h a s e ) ：代码淀释，优化、指令调度、寄存器分配和y h f t _ d 2 汇编代鹚的生成。其中瓣嚣令除段透过露极爨糖述( m d e s ) 以及捉嚣嫂擦说鞠( m s p e e ) 进行交甄获得目标机y h f td 2 的相关信息进行相应的工作。第一阶段处理前端生成的机 器无关中阀代码l c o d e ，生成机嚣相关的孛闻代码m c o d e ；第二除段为每条撰令安搀执行 功能单元和执行时间；第三阶段把处理m c o d e 生成y h f td 2 的汇编代码。下面简要介绍 各个模块的主要功能。 1 编译前端 1 3 , 1 7 , 3 2 3 9 , 4 0 , 4 1 , 4 羽。采用i m p a c t ，处理输入的源c 程序，进行词法、谣法 第4 页 国防科学技术大学研究生院学位论文 分析叛及一些常用酌优化，生成中间代码l c o d e 。 2 代码注释。代码注释( c o d e a n n o t a t i o n ) 把前端生成的l c o d e 转化为y h f td 2 相 关靛m c o d e ，m c o d e 是傻箱y h f td 2 弱标祝攒令静中润代码。代码注释首先通过 控制块涟释把控制块转化为严格编译意义上的基本块，再对每个基本块进行指令 注释，恕l c o d e 中煞指令壤蠲等徐豹w 河d 2 指令遥行替换。 3 机器描述 1 4 , 1 5 , 1 6 , 3 0 】和机器规格说明。机器规格说明m s p e c 描述嗣标机的一些机器字 黠赛方式( a l i g n m e n t ) 蓑怠。瓤器绉逡m a c h i n ed e s c r i p t i o n ( m d e s ) 赠是撼述 目标机y h f td 2 的机器资源、指令优化、指令调度等信息，如y h f td 2 的指令 集，y h f td 2 蛉鼹有功能单元秘毒存器资源以及各炎澡的萎连方式，y h f t _ d 2 每条指令的格式，指令执行时功能单元和指令执行延时。 4 。寄存器分配郾1 l 】。寄存嚣分配( r e g i s t e ra l l o c a t i o n ) 搬m c o d e 书指令馒震弱嶷搂 寄存器对应到y h f td 2 的3 2 个物理寄存器上。寄存器未分酉已之前m c o d e 中繇条 指令都熄使用康拟的个数无限制的虚拟寄存器。寄存嚣分配之艨m c o d e 中每条指 令都是遮行在舰d 2 物理寄存器上。 整i 。2 编译稷彦整髂结褐窝 5 代码优化。编译后端代码优化主要分成目标机无关的优化和机器相关的优化。机 器无关豹往纯主要寄螽l l 豫无舔代码等。辊器稠获豹优纯主要有为了填充捂令豹执 第5 页 国防科学技术大学研究生院学位论文 幸亍延时澜陈，逮遗拷受基本块寐扩大蘩本琰范溺等。 6 调度j 4 那，1 0 删。调度分前遍调度 4 , 3 6 】( p r e p a s ss c h e d u l i n g ) 和后遍调度( p o s t - p a s s s c h e d u l i n g ) 。灞度秀m c o d e 中每条指令分配弧芎亍霹懿敬行功能单元黧执彳亍辩间。 整个编译程序的目标就是充分发挥目标机删d 2j 岛并行性的特性，充分利用 疆f td 2 毒黢戆瓿器资源把燹多懿豢令安萎 在嚣一露镑裁嚣耀裁，戮裹莠行液寒 减少整个程序的执行时间。其中前遍调度主要进行指令的划分 1 2 , 18 1 确定每条指令所 在的功裁单元簇，指令划分尽疆把相必载援令安搀奁阏一臻簸攀元簇上藏少簇之 间的拷贝操作，从箍体上减少指令执行时间撮高指令的并行艘。指令划分降低了 指令调度的复杂性，提离了指令调度蛉灵活性。指令划分之蕨，兹遗调度为每条 指令安排簇内的执行功能单元和执行时间。使用前遍调度，不但能农寄存器分配 之前就能验证务种调度技术的优劣，还能通过合理安排指令为寄存器减少分配压 力，减少s p i l lc o d e 的产生弹l 。后遍调度只是为每条指令安排执行功畿单元和执行 时间，每条指令所在的功能单元簇和前遍调度过程中攒令划分的结果保持一致。 7 生成汇编代码。汇编 弋羁生成( a s s e m b l yg e n e r a t i o n ) 把经过调度和寄存器分黼之 后的中间代码m c o d e 处理转化为y h f td 2 的汇编代码。 编译蓠壤熬赣窭是较器无关翡中溺代璃l c o d e ，编译君端首宠就是把l c o d e 注释为 m c o d e ，m c o d e 中间代码采用l c o d e 格式，但m c o d e 中使用的怒目标机y h f td 2 的指令。 编译爱越其瞧足个都分帮是鞋m c o d e 佟隽输入，m c o d e 经过捂令调度耱骞存嚣分爱之矮最 终转化为盯td 2 的汇编代码。 在编译程序戆压端巾代码波释、撂令调度耪奄存嚣分配郝遁避帮搬器攮述m d e s 交互 来获得目标机y f hd 2 的机器信息完成各自的工作。机器描述m d e s 首先以h m d e s 机 器描述谗言描述蹩个y h f td 2 躲相关傣息，然压在使用m d e s 处理系统把h m d e s 文终 转化为编译内部表示，并提供目标机倍息查询的标准外部接口，编译衙端的其他几个部分 就是通_ i 建查询这些外部接口获得目标扰的相关傣息，如指令调度等信毖。机嚣描述可以降 低编译程序对甜标机静依赖，如果哥标机器进行了一数如指令执行单元等改动，我们只需 在机器橘述中进行相应的修改而其他部分通过稍微修改，使用原来的接口就可以生成新目 标撬的汇编代弼。 1 5 本文蔑结构 第一章，弓l 害。介缌整个谖题的背襞和意义，对编译程序赝薅晦的目标枫y h f t _ d 2 进行相兼描述，介绍编译技术的国内外相关研究，介缁编译程痔的整体结构，并对各主要 部分进行了相关的说明。 第二章，编译前端。介绍编译程序中往用i m p a c t 编译前端，并详细介绍中间代码 第三章，税器摇述。介绍了税嚣疆述驱动的编译技术，然后详细奔缁了目标枫y h f td 2 第6 页 国防科学技术大学研究生院学位论文 的杌嚣描述。 第四章，代码注释与优化。详细介绍编译尉端的代码注释，把l c o d e 转化为机器相关 秘m c o d e 串滔代羁情况，同瑟介绍编译舞赣执行镝苦耱梳器嚣关饶纯帮梳器鞠关侥纯。 第五章，调度。详细介绍编译后端的调度技术，包括首先对目标机进行指令划分确定 功笺攀元簇，然焘再褒簇痰进行指令瀵度豢定簿蔡摇令麴裁行麓撬荤元窝瓠雩予时溺。运费 绍对于指令调度的一些相关研究，同时给出了我们调度技术的主要算法和一些主要的数据 结搀。 第六章，总结与展勰。总结全文并指出其优点和可以改进的地方，同时为进一步工作 提出一烘建议。 1 6 本文的研究成果 本文对v l l w d s p 特性及编译的关键技术谶行了研究和探讨，初步实现了针对目标机 y h f td 2 ( v l i w 缝桷) d s p 瓣毫效c 语言编译疆序。在摇令鲻分、 囊令烫发移往纯上提 出了若干算法，其中有针对分簇v l i wd s p 的指令划分算法。针对目标机y h f td 2 的 l i s t s c h e d u l e 冀法，啦及基本块扩展优他莓箕法。跌第一终者在计算糗应鼹磷瓷窝计 算机工程发袭文章两篇( 见本文附录) 。 第7 受 国防科举技术大学研究生院学能论文 第二章编译前端 本章介绍编译前端i m p a c t 处理c 程序的过程以及机器无关中间代码l c o d e 。蕊向 y h f td 2 编浮疆亭豹缩译蔻灞傻嗣i m p a c t 编译蓠璃，翔敷宠戒对滚程寿遗行词法、语 法分析和生成机器无关的中间代码l e o d e 。 i m p a c t 4 5 潮1 是美黼i l l i n o i s 大学开发西囱i m p a c t - e p i c 机器编译程序，i m p a c t 前端 主要完成词法、语法分析以及一些常见的机器无关的优化，最后生成l c o d e 中间代码。 i m a p c t 蘩漆终擒蟊鹜2 瑟承。 图2 1i m p a c t 前端结构 正如图2 1 所示，i m p a c t 前端【3 2 1 蓠先针对c 输入源程序进行k & r a n s i - c 溺法、语 法分析，这部分由e d g 组成，经过e d g 分析之后生成p c o d e ；p c o d e 语义上等同予经过 语法分支了的c 代码，以抽象语法树的彤式存在。 生成p c o d e 之螽，i l v p a c t 前端首先对p c o d e 进彳予p c o d ef l a t t e n i n g 。f l a t t e n i n g 把复杂 的表达式转化成简单的袭达式，在转化过程中产生一些临时变燎用来保存中间结果。如表 这式 一f o o l 0 + f 0 0 2 0 经遘f l a t t e n i n g 之磊褥掰下嚣凡个表达式t e m p l 一f o o l ( ) ；t e m p 2 = f 0 0 2 0 ；i t e m p l + t e m p 2 ；经过f l a t t e n i n g 之后p e o d e 中所有函数调度彤式要么是单独的 霹熟f 0 0 0 ，要么是终灸袭达式黪右透菇t e m p l = f o o l 0 。避行f l a t t e n i n g 圭溪为磊麓瓣t n l i n i n g 和e x p a n s i o n 做准备。 p c o d ef l a t t e n i n g 之嚣i m p a c t 哥鼓挺p c o d e 爱自转纯为等徐戆c 代码，然螽在等徐c 綦础上获得p r o f i l i n g 信息，获得程序的执行p r o f i l e 信息。 i n l i n ee x p a n s i o n 进行走联扩张优化，把经攀技行的、代码转积小黪函数调瘸建联减少 函数调用的开销。为了简化内联扩张过程，把姆个函数部分成一个对应的p e o d e 文件，所 第8 暖 国防科学技术火学研究生院学位论文 有靛静态变量翻维构定义罄按照谴稍翻始辑在的谴嚣羹薪命名，并且繇有的名字对于蹩个 程序都是独特的。 p i p 分辑各添数迭器帮全爨变量之潮静依赖关系，瓣霹执行过程癌部酌指钟静确定纯， 消除模糊含义。 在i m p a c t 编译_ | l 誊壤熬最藤送行p c o d e 静转纯生或l c o d e 。在放e 到鬟鬣豹l c o d e 生 成过程中，每一个过程都可以谶行一系列机器觅关的优化，如代码外撮、表达式删除等常 见的饯纯。同时在生或l c o d e ：l 篷程中，m s p e c 撼供曩撂极约鼹戆售惠，懿投器字砖赛方式， 函数调用的开销指导函数内联扩张等，用于辅助完成最后的l c o d e 生成。最后输出的l c o d e 是与任何枧器无关的一种中间代码。盔我们匿国y h f t 的绽译程序中，编译蜃端接受_d2 l c o d e 你为输入，在l c o d e 基础上进行系列丽向y h f td 2 的工作，如注释、调度蒋。 下面一节对l c o d e 进行详细说明。 2 2 中间代码l c o d e l c o d e 是机器无关的中间代码，l c o d e 使用一套虚拟的l o a d s t o r e 体系结构的指令集。 每个l e o d e 文l 牛都包含对应c 诱言源獠序中戆一个或多个c 薅数，每个l c o d e 文件分威代 码( 指令放在醋数块中) 部分和数据部分。其中数据部分是定义各种数据类型以及相威的 变量等。代码部分描述的是程序的执行指令部分，如前面所说的l c o d e 中使用的是一嵇 l o a d s t o r e 指令集。编译后端的代码注释就是积l c o d e 中的指令部分滋释为对应目标机中 的指令集。 在i m p a c 芎编译箨序中，l c o d e 酌指令自顸向下分潮是函数块( lf u n c ) 、较翻块( c ! b ) 和指令( o p e r ) 。下面的数据结构说明了这种关系。 t y p e d e f s t r u c tlf u n e c h a r n a m e ； n a m eo f f u n c t i o n8 l c b f i r s t c b ； pf i r s ts e q u e n t i a lc b + ， l - c b + l a s t _ c b ； 4l a s ts e q u e n