（通信与信息系统专业论文）面向媒体处理器可重定目标编译器的设计研究.pdf

浙江大学博士学位论文 摘要 本文针对作者参加的国家8 6 3 超大规模集成电路设计重大专项“s o c 中3 2 位数字信号 处理器芯片开发和设计平台技术研究”项目，对编译系统中的可重定目标编译器和汇编器的 设计与开发、目标代码优化以及编译系统的验证进行了研究和探讨。面向媒体处理器的可重 定目标编译系统包括c 编译器、汇编器、链接器、以及软件仿真器，本文主要研究可重定目 标编译器和汇编器的构建技术和目标代码优化，以及对c 编译器和汇编器验证的研究。 编译前端的实现技术包括词法分析、语法语义分析和中间代码生成技术等，针对a n s ic 的程序结构，分别设计了函数、块、数据结构、类型、表达式、标识符等语法树结点，并将 语法树分成编译层次、函数声明和块三个不同层次，使语法树具有清晰的层次结构，有利于 编译程序的语法和语义分析，以及从语法树到r t l 中间表示的转换。 可重定目标编译器主要包括三个方面的内容：中间表示、机器描述和编译主体与机器描 述之间的接口技术。本文以自行开发的3 2 位媒体处理器m d 3 2 为目标机器，提出了可重定 目标编译器的系统结构，并就构成可重定目标编译器的三个主要组成部分进行了分析和研 究。重点研究了机器描述与代码生成之间的关系、如何选用合适的中间表示进行目标机器指 令系统的描述、树模式匹配的目标代码生成技术等。除了窗口寻址方式和比特反转寻址方式 以外，开发的c 编译器己能够面向媒体处理器m d 3 2 生成汇编代码。 在可重定目标编译器中，通过指令模板匹配生成目标代码的方式限制了高效的并行指令 的生成，同时，并行指令的操作数类型与单操作指令的要求不一致也是限制并行指令生成的 一个重要因素。本文在分析了上述两个限制并行指令生成的主要因素以及很难在编译器中实 现并行指令生成的基础上，提出了在汇编级检查指令的操作数类型，通过插入l w 或s w 指令来 改变操作数类型及指令调度的方法，能够有效的生成并行指令，提高了代码运行效率和代码 密度。统计数据表明：代码执行效率平均可以提高1 4 ，而代码密度平均提高1 1 7 5 。 在媒体处理应用程序代码中存在着相当多的局部变量，这些局部变量的使用范围( 生存 期) 通常都很小。相关指令在流水中需要局部变量的值可以直接从旁路逻辑中得到，并在流 水中完成局部变量值的全部使用。基于软硬件协同设计的思想，在研究局部变量生存期算法 的基础上本文提出了通过编译器指令编码实现对硬件结构的使能控制。即控制流水输出结 果是否写回寄存器文件，以减少对寄存器文件的写次数，从而降低寄存器文件端口的读写压 力。软件仿真结果表明，对d s p 中不同的应用程序平均可以减少9 4 的寄存器文件写次数。 本文最后对编译系统的验证进行了研究，提出引入参考编译器和参考仿真器的测试方 法，并通过在仿真器中插装代码生成动态数据信息( d d i ) 文件，能够将错误定位到函数级， 给编译器的调试带来很大的便利。 关键词：可重定目标编译器；代码生成器；代码优化；中间表示；机器描述；媒体处理器 一i 一 瘩经f 乍耆、导师同叠 盒文黼 浙江大学博士学位论文 a b s t r a c t b a s e do n “d e v e l o p m e n to f3 2 _ b i td s pc h i pi ns o ca n dr e s e a r c ho fd e s i g np l a t f o r i n t e c h n i q u e ”( n a t i o n a lh i g ht e c h n o l o g yr e s e a r c h & d e v e l o p m e n tp r o g r a mo f c h i n a ) t h i sp a p e ri s i n v o l v e dw i t ht h ed e v e l o p m e n to f r e t a r g e t a b l ec o m p i l e r , t h eo p t i m i z a t i o no fo b j e c tc o d ea n dt h e v e r i f i c a t i o no f c o m p i l i n g s y s t e m a c c o r d i n gt o t h e p r o g r a ms t r u c t u r e o fa n s ic ，s o m es y n t a x - t r e e n o d e sa r ed e s i g n e di n f r o n t - e n d ，i n c l u d i n gf u n c t i o n ，b l o c k ，d a t as t r u c t u r e ，t y p e ，e x p r e s s i o n ，i d e n t i f i e ra n d s oo n ，s y n t a x t r e ei sd i v i d e di n t ot h r e el e v e l s ，n a m e l yp r o g r a ml e v e l ，f u n c t i o nl e v e la n db l o c kl e v e l ，w h i c ha r e u s e f u lf o ra n a l y s i so f s y n t a xa n ds e m a n t i ci nc o m p i l e ra sw e l la st r a n s f e r r i n gs y n t a xd e ei n t or t l r e t a r g e t a b l ec o m p i l e rm a i n l yi n c l u d e si n t e r m e d i a t er e p r e s e n t a t i o n ，m a c h i n ed e s c r i p t i o na n d i n t e r f a c et e c h n i q u eb e t w e e nc o m p i l e ra n dm a c h i n ed e s c r i p t i o n a st a r g e tm a c h i n e ，m d 3 2 ，i s d e s i g n e db yo u r s e l t h es t r u c t u r eo fr e t a r g e t a b l ec o m p i l e rp r e s e n t e di nt h i sp a p e ri s r e s e a r c h e d t h e r e l a t i o n s h i pb e t w e e nm a c h i n ed e s c r i p t i o na n dc o d eg e n e r a t i o n ，a n dt h et e c h n i q u eo f m a p p i n g r t li n t o o b j e c tc o d eb yt r e ep a t t e r nm a t c h i n ga r e d e s c r i b e di n d e t a i l e x c e p tf o r c i r c u l a r a d d r e s s i n ga n db i t - r e v e r s e da d d r e s s i n g ，o u rcc o m p i l e rh a v ef i n i s h e da n dc a ng e n e r a t ea s s e m b l e c o d ef o rm e d i a p r o c e s s o rm d 3 2 i nr e t a r g e t a b l ecc o m p i l e r , a l li n s t r u c t i o n s ，i n c l u d i n gp a r a l l e li n s t r u c t i o n s ，a r eg e n e r a t e d t h r o u g h i n s t r u c t i o n p a t t e r nm a t c h i n g , w h i c h i s v e r y d i f f i c u l tt o g e n e r a t e e f f e c t i v e p a r a l l e l i n s t r u c t i o n s m e a n w h i l eo p e r a n dt y p e r e q u i r e d b yp a r a l l e l i n s t r u c t i o n si sa n o t h e ri m p o r t a n t f a c t o rt or e s t r i c tg e n e r a t i n gp a r a l l e li n s t r u c t i o n s b a s e do nt h e s et w of a c t o r sm e n t i o n e da b o v e a n dt h ed i f f i c u l t yt oi m p l e m e n ti nc c o m p i l e r , t h i sp a p e rp r o p o s e da m e t h o d o f m o d i 母i n go p e r a n d t y p eb yi n s e r t i n g i n s t r u c t i o nl wo rs wa ta s s e m b l el e v e la sw e l li l l si n s t r u c t i o ns c h e d u l i n g t h e r e f o r e ，t h i sc a ng e n e r a t ee f f e c t i v ep a r a l l e l i n s t r u c t i o n sa n dc o r r e s p o n d i n g l y i m p r o v et h e p e r f o r m a n c ea n dd e n s i t yo fo b j e c tc o d e t h e s t a t i s t i cd a t as h o wt h a tt h ep e r f o r m a n c eo fo b j e c t c o d e m a y b e i m p r o v e d b y l 4 a v e r a g e w h i l e t h e d e n s i t y m a yb e i m p r o v e d b y l l 7 5 a v e r a g e i nt h ea p p l i c a t i o np r o g r a m so f e m b e d d e ds y s t e m ，t h el i f e t i m eo f m a n yl o c a lv a r i a b l e su s u a l l y a r es h o r t l i v e d ，a n dw i l lb er e p l a c e db yr e g i s t e r si na s s e m b l e rc o d e s f u r t h e r m o r e ，i np i p e l i n et h e v a l u e so fl o c a lv a r i a b l e sn e e d e db yd e p e n d e n ti n s t r u c t i o n sm a yb ed i r e c t l yg o a e nf r o mb y p a s s i n g l o g i c ，a n ds o m eo f t h e m c a l lc o m p l e t ea l lu s a g e w i t hs o r w a r ea n dh a r d w a r ec o - d e s i g nm e t h o d ， t h i sp a p e rp r o p o s e sa na l g o r i t h mt oc a l c u l a t er e g i s t e rl i f e t i m ei np r o g r a m s ，a n dt h ec o n t r o lo f w r i t i n gr e s u l t s b a c ki n t or fi s i m p l e m e n t e dt h r o u g h a ne n a b l ec o n t r o ls i g n a l p r o v i d e db y i n s t r u c t i o ne n c o d i n ga tc o m p i l et i m e t h er e s u l t so f s i m u l a t i o ns h o wt h a tt h ea v e r a g en u m b e ro f w r i t eo p e r a t i o no nr fi sr e d u c e db y9 4 f o rv a r i o u sa p p l i c a t i o np r o g r a m s b a s e do nt h et r a d i t i o n a lc o m p l i e rt e s t i n g ，t h i sp a p e rp r o p o s e sam e t h o dt h a ti n t r o d u c e sa r e f e r e n c ec o m p i l e ri n t oc o m p i l e rt e s t i n g b yc o l l e c t i n gd y n a m i cd a t ai n f o r m a t i o n ( d d i ) f i l e si n s o f t w a r es i m u l a t o r , b u g si nt e s t e dc o m p i l e rc a nb el o c a t e di nf u n c t i o nl e v e l k e y w o r d s ：r e t a r g e t a b l ec o m p i l e r ：c o d e g e n e r a t o r ；c o d e o p t i m i z a t i o n ；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 ；m a c h i n ed e s c r i p t i o n ；m e d i a p r o c e s s o r - - i l l - - 浙江大学博士学位论文 第1 章序论 编译器开发的原理和技术涉及编程语言、计算机体系结构、语言理论、算法、以及软件 工程等领域。早期编译的主要工作是如何处理从算术公式到机器代码的转换，在这一时期， 编译器的结构和功能都非常简单。编译器辅助开发工具的产生大大简化了编译器开发人员的 工作，提高了编译器的开发效率，并且降低了编译器出错率。 尽管当前基本编译原理已经比较成熟，但是编译器基础设施的不完善妨碍了面向特定目 标机器编译器的研究与开发。制定标准的、系统的开发工具实现更多地代码自动生成，以及 构建结构良好、可读性强、易维护、可重用的编译器，将有助于缩短编译器开发周期。可重 定目标编译器的研究与开发技术是当前编译器领域研究工作的一个热点，本章主要介绍编译 器和重定目标编译器的发展历史、存在的问题及其相关技术：对编译器后端代码生成技术进 行了重点说明；本文编译器的目标机器是自行开发的m d 3 2 媒体处理器，本章最后介绍肺3 2 媒体处理器的指令系统、流水结构、寄存器文件等结构特征。 1 1 编译器的发展历史 编泽系统是任何计算机系统中不可缺少的重要部分“1 ，编译系统的研制因其技术复杂、 难度较高而需要投入较多的人力、物力和花费较长的研制周期。过去编译器均是针对某一特 定语言和目标机而编写的。随着计算机的飞速发展，过去那种编写编译器的方法己很难满足 实际需要。图1 - 1 显示了编译系统与计算机系统的关系，可以看到，操作系统和应用程序的 开发都离不开编译系统的支持。 图卜1 编译系统在计算机系统里的位置示意图 在八十年代初，针对各种程序设计语言的后端具有较大共性的特点，国外相继开发了支 持多种语言的编译系统”1 ，并很快成为各计算机公司编译系统采用的通用方法。在这种编译 系统种，每种语言具有独立的前端，所有语言共享一个后端。这大大降低了开发编译系统的 开销。这种支持多语言的编译系统虽然满足了快速开发编译器的需要，但对计算机硬件不断 更新换代的飞速发展仍显得力不从心。1 。虽在七十年代末、八十年代初有一些人致力支持多 第1 章序论 目标机编译系统的研究，但由于受到各种条件的限制，仅停滞于理论研究和实验阶段。 进入八十年代后期，随着国外各种软件公司的兴起以及计算机芯片不断推陈出新，对支 持多目标机的编译系统的研制显得越来越重要“1 ，编译程序的开发者深刻地意识到：只有支 持多语言、多目标机的编译系统才具有较强的生命力和市场竞争力。 另外，为便于开展对计算机体系结构、编译程序语言和编程环境的实验研究，必须能够 快速地产生高质量的编译器，而编译器的构造是一个劳动密集型的工作，经常是一个瓶颈”1 。 虽然对于编译前端自动生成工具的研究已比较成熟，并开发了一些普遍使用的工具，如l e x 、 y a c c 等，但对编译后端的自动生成的研究仍处于探讨阶段。f s f ( f r e es o f t w a r ef o u n d a t i o n ) 和美国相继启动了g n u 系统“和n c i ( n a t i o n a lc o m p i l e ri n t r a s t r u c t u r e ) 工程“”1 ，其 部分研究目标是为聚集全世界的研究力量，协作发展编译器技术，促进技术产业化。 1 2 可重定目标编译器的研究技术 从狭义上讲，编译器是把用高级语言编写的程序翻译成对等的可在某一计算机上执行的 目标代码或机器代码的软件系统：从广义上讲，编译器概念可以进一步延伸，可以是把种 高级语言翻译成另一种高级语言，也可以是把一种机器语言翻译成另一种机器语言，或是把 一种高级语言翻译成中间表示形式等等。如图卜2 所示，传统编译器通常实现的是将高级源 代码转换成特定目标机器的汇编语言”。 图1 - 2 传统编译器与可重定目标编译器的比较 与传统编译器不同的是，可重定目标编译器拥有多个目标机器，编译器中机器相关部分 被隔离在一些易于被替换以便重新定向到不同目标机器上的模块之中，机器相关的这部分信 息就是机器描述，如图卜2 所示的处理器描述。可重定目标编译器接收机器描述的信息并将 编译器重定向到特定的目标机器，生成一个特定目标机器的编译器”。 1 2 1 可重定目标编译器概述 编译器一般分为前端和后端。前端技术目前已经比较成熟，也有了许多自动化工具如 l e x ，y a c c ”3 等。后端接受前端生成的“中间表示”，进行优化并且产生特定硬件平 一2 浙江大学博士学位论文 台的汇编语言。由于中间表示的定义形式各不相同，目标硬件平台的机器信息更是千差万别， 二者都很难采用形式化的描述，也就很难构造出自动化= _ i = = 具。由此，编译器后端成为影响编 译器构造效率的瓶颈”。 当前提高编译器后端的构造效率采取的方法之一是设计可以重定向的编译器后端。所谓 “重定向”，就是在构造编译器后端时采用一定技术，使该后端可以很容易地接受机器描述 信息，并可以根据机器描述生成相应的汇编语言。构造可重定向的编译器主要需要解决三个 问题“”： 需要设计一种对目标机恰当的描述，这种描述既要能描述系统与硬件的共性，也要 能描述它们各自的特性，同时还要适合于编译程序的处理； 需要设计出一种较好的中间语言，这种中间语言应该在适当的层次上，向上能支撑 多语言的映射，向下能适应多平台的转换，并且适合于进行各种优化： 在机器描述与代码生成器之间需要仔细地设计一种统一的接口。 c g g ( c o d eg e n e r a t o rg e n e r a t o r ) 。”“”能够利用这些资源描述来自动构造一个代码产 生器c g 和代码优化器“。图卜2 为可重定向目标编译器自动生成编译器的整体图示，其中 最右的方框内是所生成的一个完整的编译器。 图卜3 可重定向目标编译器结构示意图 前端( f r o n te n d ) 包括词法分析、语法分析、创建符号表、语义分析和生成中间代码。 同时前端也进行一部分代码优化( 高层优化) 和出错处理。前端主要依赖于源语言，与目标 机体系结构无关。 后端( b a c ke n d ) 包括代码优化部分、代码选择、代码生成、寄存器分配”、必 要的出错处理以及符号表操作。后端包括编译器中与目标机器相关的部分，通常这些部分独 立于源语言，而仅仅依赖于中间表示和目标机器。 编译器的自动生成工具可以自动生成编译器的各种部件。利用词法分析器的生成器( 如 l e x 工具) ，可以为正则表达式生成词法分析器；利用语法分析器的生成器( 如y a c c 工具) ， 一3 一 第1 章序论 可以为上下文无关的文法生成移进一规约语法分析器：利用代码生成器的生成器c g g ，可以 为目标机器生成代码生成器( c g ) 。表卜1 是关下可重定目标编译器面向不同目标的分类情 况，这个分类并不是绝对的，例如，g c c ( g n uc o m p i l e rc o l l e c t i o n ) “2 “”1 也可以 面向d s p 生成目标机器的编译器，但生成的汇编代码质量欠佳而已。 表卜1 面向不同目标的可重定目标编译器 面向g p p面向d s p面向& s i p ”1面向v l i w商崩 l c cf i b u r g )r e d a c op e a si m p a c tc 肛s s 蓑纂i 粼劁鬻鬓雾雾蓊鬻赣蘩麓黼l 纂i 鋈l ；蒸壤冀缓滕霪黼鬻蘸鬟蒸i i 霾蘸雾 p a g o d e s p a m s u i f ( o l i v e )e x p r e s s t r i m e d i au c c l 蒸溪蘸匿蘸鬻l 囊冀囊鬓黛蠢麟糕鬃麓刺l 麓麟蛹鞲鋈| | _ 1 | i 蓊纛麟蓊| 1 | i i 攥鬻 燃| | z e p h y r v p o m e s c a l ；：i 薹鍪鲤i 篷鬯鍪薹鎏鋈鍪遴i 耋塑塑_ _ _ _ _ l | l | l 鋈i 羹l 鋈薹鏊鍪鍪蓥墼墼筮鬯鎏l | 薹鋈鋈_ i _ i _ l 这里不对每个编译器进行介绍，下面只对儿个典型的编译器作一个简要的说明，参见表 l 一2 对几种典型编泽器的比较情况。 z e p h y r “编译器使美国启动的n c i 工程的主要部分之一，它是由弗吉尼大学和普林 斯顿人学联合开发的。z e p h y r 以v p o ( v e r yp o r t a b l eo p t i m i z e r ) 为核心，支持机器指令 级的优化，目酊已爿j 于开发了支持j a v a 、c + 十等多种源语言，支持a l p h a 、m i p s 、m o q t o l a8 8 1 0 0 等2 0 多种处理器的编译器。 z e p h y r 也提供了两层中间表示，对其高级中间表示没有明显的限制，它可为前端输出 的任意形式，机器信息通过代码扩充器( c o d ee x p a n d e r ) 一次性地进入编译丰体，使编译 成分间的耦合度较低。低级中问表示具有强类型树形式结构的r t l ( r e g is t e rt r a n s f e r 1 i s t ) ，其语义描述与任何机器无关。z e p h y r 提供一个语言c s d l 以进行机器规格说明，并 提供了一些标准操作码，对于一个新的目标机而言，只定义其特有的部分指令就可以了，从 而使机器描述比较简洁且可复用性好。另外，由于用户可以定义新的r t l 操作符，这虽然提 高了机器描述地灵活性，但不利于从高级中间表示到r t l 表示的转换，因此其代码扩充器需 要手t 编写。 s u i f “编译器是美国启动的n c i 上程的另一个主要部分，它是由斯坦福大学开发的。 s u i f 以s u i f 中问格式( v e r yp o r t a b l eo p t i m i z e r ) 为核心，支持高级的优化，如自动并 行优化和面向对象优化。s u i f 编译器目前提供了c 和f o r t r a n 前端、高级并行和局部优化 器，一个优化m i p s 后端和一系列编译器开发工具。s u i f 中间格式是用c + + 实现的一种典型 的高级中间表示，它提供了表达语言程序的共同格式，其核心部分采用了基于类库的面向对 象层次结构。s u i f 中问格式的主要设计目标在丁支持过程间分析和高级优化，且方便于优 化和分析的扩展。它是相当灵活的，允许编译遍的扩充和重新排序，但这种灵活性是以性能 为代价，因此不适用于开发编译器，但在教学和编译技术研究种得到广泛使用。 4 浙江人学博上学位论文 表卜2 几种具有代表性编译器的比较 编译器名笺篙耋等霎 机嚣描述中问表示薯鬻主要应用 合度 领域 细岍一写翼罴墓雾竺箬描述具有嚣篙示不刘艮较低嚣技术 稳 燃鬻黧醚鬟鬓l 黧燮麓鬻鬻鬻 m 一凹半裟薯蒙鲫肋既鞭张纛问l c 狲o d e l c o d e 胍弛桃嚣貅 器处理的l m d e s低层为 研究 誉8 鬣簟鬻囊麓黧瓣鬻 s u i f 手_ r ：编写机器描述具有较好的灵话性面向对象的层次结构较低教学与科 研 i b t p a c t ( i l l i n o i sm i c r o a r c h i t e c t u r ep r o j e c tu t i l i z i n ga d v a n c e dc o m p i l e r t e c h n o o g y ) 编译器是由伊利斯诺大学开发的，它具有谓词编译、指令级并行优化、编译器 工程推测、基于侧面优化、高级的机器描述、基于指针的依赖分析和追踪等高级特征。通过 分析和论证硬件的层次和编译器支持以便于理解体系结构升级的代价和有效性，从而为微 处理器工业提供关键性、体系结构专门知识和编译器原犁的研究。i b l p a c t 的主要重点在于 展示、提高和利用指令级并行。 i m p a c t 提供了具有不同形式的两种机器描述语言：1 1 m d e s 和l m d e s ，其中h m d e s 的语法 形式与人的直觉相符，具有较好的可读性和可修改性，利用转换器将h b l d e s 转换为l t m i ) e s ， 为用户提供友好的语法检查器，利用l m d e s 文件实现编译器对机器描述的快速装载。编译接 口函数与其支撑的体系结构无关，基本接口函数不使用编译器内部的数据结构，利用这些基 本函数，可构造功能更强大的编译器内部函数。 t r i m a r a n 。“系统是编译和性能监测的集成，它是由惠普公司和伊利斯诺大学联合开发 的，主要面向e p i c ( e x p l i c i t l yp a r a l l e li n s t r u c t i o nc o m p u t i n g ) 体系结构，支持指令 级并行体系结构的编译后端技术研究，易于实现分析和优化模块的添加、删除和越级。 t r i m a r a n 系统也提供了详细的模拟环境和灵活的性能监测环境。 t r i m a r a n 提供了基于图的中间表示，实现r 数据依赖图、控制流图的可视化。t r i a r a n 也是利用一种基于关系数据库的机器描述语言的特殊格式i i m i ) e s 进行机器规格说明。利用转 换器，h r d e s 描述被转换为l m d e s 文件装入到编译器，爿 建成m d s 数据库的内部结构。m d s 数据库可供t r i m a r a n 中的各个模块利用m o s 接口进行调用。 s g ip r 0 6 4 ”“编译器是由s g i 公司开发的，它为运行在l i n u x 操作系统上的i n t e li a6 4 体系结构提供了一套优化编译器上具。它支持的源语言有c ，c + + ，f o r t r a n 9 0 9 5 和0 p e l l i p 。 第1 章序论 尽管s g ip r 0 6 4 以s g i 现有的编译器系列为基础，但由于i a 一6 4 自身还不够成熟，到目前为 j l 至少有两个用其编译的s p e c2 0 0 0 基准程序不能够正确执行。 p r 0 6 4 提供了可分为5 个层次的中间表示w h i r l ，其中一个中间表示是r t l 。在编译过 程中，中间代码依次降低，多数优化算法绑定在特定层次的中间表示上。多层次中间表示的 使用，实现了多种源语言为多种目标机器产生代码的编译器的集成。 1 2 2 面临的技术问题 编译器的研究已取得了相当大的进展，有大量的先进技术和工具为之提供支持。编译器 的发展不仅受到编译技术因素的影响，许多其他因素也会对其产生不容忽视的影响。在一些 重要因素的影响下，编译器的研究与应用存在着以下几个方面的问题。 ( 1 ) 传统的编译技术自身有待于进一步提高 编译器的发展以传统的编译技术的发展为基础，由于计算机体系结构的日益复杂化，尤 其是异构体系结构的使用，而在嵌入式系统的开发中资源和限制的相对重要性各不相同。 因此，现有的传统编译技术，如代码生成、代码优化、寄存器分配和指令调度等技术己很难 满足需求，有待于进一步提高和发展。 ( 2 ) 机器描述工具急需完善和规范化 由于机器描述工具的重要性，上述的编译器分别提供了自己的机器描述工具，如g c c 的r t l “。，z e p h y r 的c s d l 以及i m p a c t 和t r i m a r a n 的m d e s 等等。这些机器描述工具虽在理 论和应用等方面均具有重要价值，但仍然存在着一些问题。这主要体现在以下两个方面： 对机器描述的抽象层次、描述内容没有统一的标准，对于描述一个新的体系结构， 往往觉得无从下手，保证机器描述的正确性和完备性尤其困难： 虽然一些目标环境有许多共同特征，由于机器描述工具在支持可扩展性和可复用性 等方面存在着一定的不足，如g c c 的r t l ，因此复用已有的机器描述比较困难。 由此可见，为提高机器描述语言的适用性和机器规格说明的质量，有必要建立统一的机 器描述规范，提供友好的机器描述工具。 ( 3 ) 后端自动构造工具尚需有突破性的进展 在编译系统中，中间代码的语义是内部的、且是很明确的。由于用目标机的性质来解释 这些语义，将中问代码语义的形式化描述与目标机器的形式化描述相结台存在一定的围难， 因此，编译后端自动构造工具的出现比词法分析器的构造的出现要晚得多。在2 0 世纪7 0 、 8 0 年代，出现了得许多编译后端得自动构造技术，开发了一系列代码生成器的生成器，如 b e g 1 ，i b u r g “”1 和o l i v e ”1 等。它们大致可分为解释性代码生成、模式匹配代码生成和 表驱动代码生成三大类。上述一些编译器也提供了相应的代码生成器的自动构造技术，如 g c c 等，这种利用声明性描述构造代码生成器要比手工编写容易，而且所需的工作量少，但 其产生代码的执行效率往往还不足手工开发的十分之一，从而很难为广大用户所接受。 一6 一 浙江人学博士学位论文 因此，些编译器的代码生成器仍是手工编写的，如z e p h y r 等，为迎合嵌入式系统开 发的需要，提高自动构造的代码生成器的适用性，其技术尚需有突破性的进展。 ( 4 ) 编译器的使用存在一定的剧难 这些编译器的主要不足之处，在于它与实际应用尚有一定的距离。首先，使新编译器由 一些即插即用的对象组成是多数编译器的主要设计目标之一，而实际上，编译器成分间存在 一定的依赖关系，创建可操作的、有效的编译器对象集合是很困难的，例如：若中间表示发 生变化，流图的创建对象是否仍然能正常工作是一个问题。 由此可见，对于开发者而言，复用其中的某些成分或许比较容易，但对一般的_ h j 户来讲， 复用是很困难的。其次，熟练掌握一个编译器的使用比较困难，从而使之很难为广大编译器 的开发者所接受。最后，多数编译器是针对研究性应用的，它们常常以牺牲性能和代码大小 以换取灵活性，从而使用其产生高质量的编译器是不切实际的。 1 3 可重定目标编译器的设计方法 可重定目标编译器实现技术重点在于后端的设计与实现技术，对下现存的高级语言，有 三种方法来产生面向d s p 的编译器1 2 2 1 1 “”： 从头开始构造一个编译器。当没有任何工具可用于构建编译器的某一个部分时，这 是唯一可行的方法。这种方法已用于那些专用d s p 语言的处理器，包括6 0 s p l 和 g a b r i e l ，即使编译器的某些部分可由软件工具来自动产生，总的来说这种方法是 困难和繁琐的。这种方法产生的编泽器所生成的目标代码效率很低，对代码的优化 能力比预期的差。 重定向一个现存的编译器到新的处理器。对于c 语言，通常选用可移植c 编译器 ( p c c ) 。这种方法已成功的将可移植c 编译器重定向到各种各样的处理器结构，例 如a t & td s p 3 2 、t it m s 3 2 0 c 3 0 、及其它的可编程d s p 。p e g 不提供人量的代码优化， 也不支持c 语言之外的其它语言。 使用编译器产生工具包( c g t s ) “”“7 产生一个编译器这种工具包能用来产生个 完整的编译器，包括对输入程序进行语法分析的前端、执行代码优化的中间阶段、 执行代码产生和窥孔优化的后端。这种工具包是基于“通用的编译器”的概念，如 图卜4 所示，前端将源程序语言转换成共同的中间表示( i r ) ，后端将中问表示转 换成特定的机器语言。 源镡叠罐震辫罐霁凳 图卜4 通用编译器的结构 使用第三种方法并不是意味着要重新构建一个c g t s ，因为构建c g t s 比构建一个编译器 要幽难的多，它要求对任何一个产生的编译器提供所有的功能，包括所有的优化能力，然而 7 第1 章序论 至今还没有为可编程d s p 生成一个有效优化的编译器。然而，在相同的时间内，使用c g t s 方法只要对目标机器进行描述，就可以构造目标机器的编译器，这中方法更具普遍性和高效 率5 “。 1 3 1 典型可重定目标编译器的构建技术 如前所述，可重定目标编译器有多种：面向通用处理器6 p p ”1 的，面向信号处理器d s p 的，面向指令级并行处理器v l i w 的等等。这里主要介绍两个可重定目标编译器：g c c 和l c c 。 g c c 是一个被广泛使用的、功能强大的可重定目标编译器，能够生成比较优化的汇编代 码。但g c c 的源代码非常庞大，注释不详细。可读性欠佳；g c c 没有完整的开发文档，不利 于程序理解；g c c 的前端和后端没有一个清晰的划分，中间表示r t l 已经与目标机器相关， 这些因素给重用g c c 的代码带来了很大困难，通过g c c 为某个目标机器生成编译器的工作也 是非常艰辛的。 l c c 是支持a n s ic 的可重定目标编译器，目标无关的前端和机器相关的后端划分清晰、 任务明确，通过接口把这两部分紧密地连成一个有机整体。l c c 采用d a g 图“2 “作为中间表示， 与目标机器无关。与g c c 相比，l c c 编译器的源代码很小，但生成的汇编代码效率较差。 1 3 1 1g c c 的构建技术 g c c ( g n uc o m p i l e rc o l l e c t i o n ) 是f s f “启动的g n u 工程的一部分，其开发目标在于 提高g n u 系统中编译器的质量。g c c 目前已支持的源语言有c ，c + + ，o b j e c t i v e c ，f o r t r a n ， a d a ，已移植的平台有1 0 0 多种，涉及3 0 多种处理器，6 0 多种系统“。g c c 属于自由软件， 在全世界范围内得到了广泛使用”“。 g c c 是一个用c 语言实现的优化可移植编译系统，高度的优化和可移植性能是该编译系 统晟为突出的两大特点。其设计思想的核心包括三个方面“： 目标机器描述与定义机制。g c c 对每个目标机的指令系统都有一个机器描述文件 ( m d ) ，在该文件中，对每条指令所完成的操作以及各操作数的机器级存储模式和 数据模式都以代数式的形式给出了清楚的描述。 r t l 中间表示机制。g c c 从不同系统结构的机器语言中抽象出共性的操作，以形成 一个适合编译分析加工的中间语言一一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 能在 机器描述引导下进行中间代码的生成，程序代码与机器无关，但中问代码已含有给 定目标机的指令信息，适合执行某些与机器相关的指令归并、窥孔优化及指令重排 序等优化。 一8 一 浙江大学博士学位论文 图卜5g c c 编译器的结构 g c c 编译器的结构见图1 5 ，采用两层中问表示，它们分别为语法树和r t l 表达的中间 代码。在词法分析过程中，首先将读入的每条语句转换成语法树的形式，然后转换为r t l 。 g c c 的r t l 代码则由一条一条的指令组成，每条r t l 指令实际上都抽象地表达了目标机的一 条指令。但对同一条指令的操作意义而言，不同的目标机完成这一操作的指令条数、操作数 的形式以及汇编格式各不相同，从而使其机器描述几乎不具有可复用性。由于前端产生的语 法树没有保留，且机器信息从不同的编译阶段进入，从而使其编译成分间具有较高的耦合度。 对于任何目标机，由于r t l 指令i n s n 集合“不发生变化，使语法树到r t l 中间表示的转换 比较简单，从而使其编译后端可以自动产生。 g c c 整个系统的工作流程由一个总控程序控制，至少经过两遍扫描完成从一个g n uc 源 文件到目标机器汇编代码的转换。第一遍扫描又称为前端分析，它完成上述的语法、语义分 析和中间代码的生成这三部分工作。它的输入为预处理后的源文件，输出是r t l 中间代码。 语法分析是这遍扫描的核心，它控制着各种语义成分的翻译和中间代码的生成经过语法树 的过渡后再生成中间代码。语法分析程序是由一个类似y a c c 的自动生成工具b i s o n ”“生成 的，该t 具接收l a l r ( 1 ) 语法“”o l 。 第二遍扫描又称为后端处理，完成高性能优化、寄存器的分配和汇编代码生成。优化分 为常规优化和r i s c 优化”“。前者包括跳转优化、公共子表达式删除、循环优化、数据 流分析和指令归并等。后者包括延迟分枝、指令重排和循环展开等优化，其中指令归并优化、 r i s c 优化及汇编代码生成均是在目标机器描述的引导下，通过模板匹配算法完成的。在g c c 编译器对源文件进行编译的过程中，有三个主要的转变“： 前端读取源文件并且建立语法树。这部分内容仅仅和语言相关，而和目标机器无关。 根据有名字的指令模板，从语法树产生r t l 中间代码，链入r t l 的双向链表。从中 间代码开始，在g c c 中被称为后端，因为r t l 的产生已经与目标机器有关了，是在 机器描述的引导下生成的。 将r t l 指令i n s n 与r t l 模板”“进行匹配产生汇编代码。将r t l 双向链表中的i n s n 一个一个的与机器描述文件中的r t l 模板进行匹配，如果匹配，则取得相应的汇编 模扳，调用汇编输出函数将汇编代码输出到汇编文件中。 一9 一 第1 章序论 1 3 1 2l c c 的构建技术 l c c “4 ”是p r i n c e t o n 大学开发的一个a n s ic 的编译器，作为编译器本身并没有什么奇 特之处，但作为编译器与现代编译器基础设施研究是一个良好的范例，l c c 应用并整合了 z e p h y r 项目中一些编译器实现技术，如图卜6 所示。l c c 的开发目标是：代码简单；目标可重 定向；实现交叉编译；编译速度快：能支持a n s ic 语言全集。 l c c 中使用“操作符”( o p e r a t o r ) 这个名称，来抽象程序的各种操作。它的重定向策 略是对目标机器编写一个“机器描述”文件，包括规则和函数，主要用来确定每个操作符和 目标机汇编语言的语义对应关系。文件中还有函数调用规则，寄存器分配算法等其他和机器 相关的信息。以此文件作为机器相关信息的输入，构造出代码生成器。l c c 的特点是比较简 单，它的机器描述文件比g c c 要短小的多，重定向的工作量较小，但生成代码质量较低。 图卜6l c c 编译器的结构 l c c 编译器源代码非常简练，词法分析、语法和语义分析没有使用自动生成工具，而是 用手工编程实现的。语法分析后产生语法树，并从语法树直接生成目标机器的汇编代码。l