（计算机软件与理论专业论文）bwdsp100编译器的研制及关键技术研究.pdf

摘要 摘要 数字信号处理( d i g i t a ls i g n a lp r o c e s s i n g ，d s p ) 普遍采取静态指令调度技 术的v l i w ( v e r yl o n gi n s t r u c t i o nw o r d ) 体系结构，在很大程度上依赖编译器 的处理。这对编译器的设计和应用，既是机遇又是挑战，比如指令分簇与调度、 单指令流和多数据流指令的处理都需要由编译器来完成。 b w d s p l 0 0 是某研究所开发的一种d s p 芯片，本文的工作是为其设计一款基 于i m p a c t 的编译器，并对b w d s p l 0 0 编译器的设计与实现技术、性能优化技术进 行了深入的研究。本文的主要工作有两个部分：首先是基于可重定向编译器 i m p a c t ，实现了从i m p a c t 到b w d s p l 0 0 编译器的移植；其次是针对b w d s p l 0 0 体 系结构的特点，提出了指令调度和分簇的优化算法及其相关实现。 i m p a c t 到b w d s p l 0 0 的移植，主要包括编译器的前端和后端。前端把c 语言 翻译成机器无关的中间语言；后端再针对b w d s p l 0 0 体系结构，把中间语言翻译 成机器能识别的汇编语言。由于前端是与机器无关的处理部分，我们的工作重点 和难点在编译器后端的制定，具体包括机器描述、指令注释、寄存器分配和生成 汇编代码等。移植后的系统能够生成b w d s p l 0 0 的汇编代码，并通过了正确性测 试。 对移植的编译器进行优化，主要包括指令分簇和指令调度。指令分簇是指把 每条指令分配到b w d s p l 0 0 的某个簇上去执行，充分利用各个簇的资源；指令调 度是指提取能够在同一时钟周期发射的指令，使之能并行执行。我们的工作设计 了一般指令和单指令流多数据流( s i m d ) 指令分簇算法，以及非循环代码和循环代 码的指令调度算法。最后实验表明，采用指令分簇算法和无分簇对比，平均执行 时间有1 倍的效果提升；s i m d 优化加速比平均达到6 4 8 ；非循环指令调度的平 均指令集并行度( i p c ) 达到4 o ；循环指令调度平均i p c 达到6 1 。 关键字：b w d s p l 0 0i m p a c t 指令分簇指令调度s i m d 软件流水 a b s t r a c t a b s t r a c t d i g i t a ls i g n a lp r o c e s s i n g ( d s p ) g e n e r a l l yu s e sas t a t i ci n s t r u c t i o ns c h e d u l i n g t e c h n i q u e sv l i w ( v e r yl o n g i n s t r u c t i o nw o r d ) a r c h i t e c t u r ew h i c hi s m a i n l y p r o c e s s e db yc o m p i l e r i tw i l lb eb o t ha l lo p p o r t u n i t ya n dac h a l l e n g ef o rc o m p i l e r t e c h n o l o g y , b e c a u s ec o m p i l e rp r o c e s s e si n s t r u c t i o nc l u s t e r i n g ，i n s t r u c t i o ns c h e d u l i n g a n ds i n g l ei n s t r u c t i o nm u l t id a t a f l o w ( s i m d ) b w d s pi0 0i sak i n do fd s p o u rw o r ki st od e s i g na ne f f e c t i v ec o m p i l e rb a s e d o ni m p a c t t h i st h e s i sh a sb e e nd i v i d e di n t ot w om a i np a r t s ：f i r s t l y , w ep o r t e d i m p a c tt ob w d s p10 0 c o m p i l e r ；s e c o n d l y , w ep r o p o s e d a n di m p l e m e n t e d i n s t r u c t i o ns c h e d u l i n ga n dc l u s t e r i n ga l g o r i t h m sb a s e do nt h ec h a r a c t e r i s t i c so f b s p10 0a r c h i t e c t u r e t h ep r o c e s so fp o r t i n gf r o mi m p a c tt ob w d s pi0 0i n c l u d e dt h ec o m p i l e r f r o n t - e n da n db a c k e n d f r o n t - e n dt r a n s l a t e dcl a n g u a g ei n t om a c h i n e i n d e p e n d e n t i n t e r m e d i a t el a n g u a g ew h i l eb a c k - e n dt r a n s l a t e di n t e r m e d i a t el a n g u a g et oa s s e m b l y c o d e a st h ef r o n t e n dp r o c e s s i n gi sm a c h i n e - i n d e p e n d e n t ，o u rm a i nw o r ki sm a k i n g t h ec o m p i l e rb a c k - e n d ，i n c l u d i n gm a c h i n ed e s c r i p t i o n ，i n s t r u c t i o na n n o t a t i o n ，r e g i s t e r a l l o c a t i o na n da s s e m b l yc o d ee m i t t i n g t h ep o r t e ds y s t e mc a ng e n e r a t eb w d s p10 0 a s s e m b l yc o d e w ea l s op a s s e dt h ec o r r e c tt e s to ft h es y s t e m t h eo p t i m i z a t i o no fp o r t e d c o m p i l e ri n c l u d e di n s t r u c t i o nc l u s t e r i n g a n d s c h e d u l i n g i n s t r u c t i o nc l u s t e r i n gi st oa s s i g ne a c hi n s t r u c t i o nt ob w d s p l 0 0 sc o r ei n o r d e rt of u l l yu s et h er e s o u r c e so ft h ep r o c e s s o r ；i n s t r u c t i o ns c h e d u l i n gi st oe x t r a c t i n s t r u c t i o n sw h i c hc o u l db el a u n c h e da tt h es a n l ec l o c kc y c l ei no r d e rt oe n a b l e p a r a l l e le x e c u t i o n w ed e s i g n e dg e n e r a la n ds i m di n s t r u c t i o nc l u s t e r i n ga l g o r i t h m s ， a n dn o n - c y c l i ca n dc y c l i ci n s t r u c t i o ns c h e d u l i n ga l g o r i t h m s t h ee x p e r i m e n t ss h o w t h a tt h ec l u s t e r i n ga l g o r i t h mc o u l dp r o m o t ea na v e r a g e1t i m e se f f e c tc o m p a r e dt o n o n - c l u s t e r i n gs y s t e m ，s i m do p t i m i z a t i o nc o u l ds p e e du pa na v e r a g eo f6 4 8 ，t h e a v e r a g ei n s t r u c t i o np e rc y c l e ( i p c ) o fn o n - c y c l i ci n s t r u c t i o ns c h e d u l i n gi s4 0w h i l e c y c l i ci s6 1 k e y w o r d s ：b w d s p 10 0 ，i m p a c t , i 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 nc l u s t e r i n g ， s i m d ，s o f t w a r ep i p e l i n i n g i i 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的 成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或 撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作 了明确的说明。 作者签名： 出 签字日期：蔓二l 幽 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学 拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构 送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入中 国学位论文全文数据库等有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内 容相一致。 保密的学位论文在解密后也遵守此规定。 酗开口保密( 年) 作者签名：磕二盗 签字日期：量厶l 蝉 导师签名：缛芬 签字日期：兰! ! ! 竖型 第一章绪论 1 1 背景介绍 1 1 1v liwd s p 结构概述 第1 章绪论 现今两个最主要的指令级并行体系结构是v l i w ( v e r yl o n gi n s t r u c t i o nw o r d ) 结构( f i s h e rja ，1 9 8 3 ) 和超标量结构( mj o h n s o n ，1 9 9 1 ) 。超标量结构专注于 利用硬件调度指令来提高效率，并提供了分支预测来避免在控制转移时产生流水 停止，但是这种结构是动态的执行调度，这使得设计变得复杂并且能耗很高。而 这种结构所需内存占了大部分的芯片面积，能耗和成本。这些问题使得超标量处 理器不适合嵌入式系统。 由于超标量体系结构丌发嵌入式系统的困难难以避免，人们越来越关注 v l i w 技术的研究( 郑飞，1 9 9 6 ) 。v l i w 技术将调度任务交给编译器来完成，并 利用编译技术静念地开发指令级并行( i l p ) ( m s c h l a n s k e r ，1 9 9 4 ) ，而其硬件逻 辑比较简单。从理论上说，它同超标量技术是等价的，但能开发更大的并行性， 并且简化硬件设计，所以被许多人认为是超标量的下一代替代技术。 d s p 概念( 魏晓云，2 0 0 3 ) 最早出现在上个世纪6 0 年代，到7 0 年代才由计 算机实现部分实时处理，当时主要用于高尖端领域。由于d s p 技术与大量运算 相关，每秒完成百万条指令运算就变为一个新的单位m i p s ( 每秒百万条指令) 。 8 0 年代，有些公司陆续设计出适合于d s p 处理技术的处理器，于是d s p 开始成 为一种高性能处理器的名称。t i 公司在1 9 8 2 年发布了第一颗d s p 芯片，名为 t m s 3 2 0 1 0 ，这是一个处理速度达5 个m i p s 的处理器。近年来，嵌入式系统发 展迅速，嵌入式系统的不断发中已经开启了很多研究课题。由嵌入式处理器带来 的挑战不同于那些普通高性能计算的系统。与高性能计算不同的是他们还要求低 能耗，低成本和更小的心- h - 门d 。面积。指令级并行的体系结构已经被发展到可以适应 高性能计算的需要，而适应嵌入式系统的指令级并行的体系结构仍处于迅速发展 和探索中。 随着多媒体和宽带通讯技术的发展以及它们被广泛的应用，新一代的使用 v l l wd s p 结构被提出来用于实现高速运算，如t s 2 0 1 。在v l i w 结构中，一条 长指令包含多个可以并行操作的类似于r i s c 简单指令的操作码，我们称之为 v l i w 的基本指令单元。每一个基本指令单元与相应的硬件相对应，控制简单。 第一章绪论 v l i w 结构的主要特点是大量并行功能单元通过一个大的共享寄存器文件互连 起来，控制逻辑比超标量简单得多。 v l l w 结构处理器为了保证较高的指令级并行( i l p ) 并满足高性能和各种 应用等，必须增加更多的可以并行执行的功能单元，但反过来增加更多的可并行 执行功能单元又需要寄存器文件增加更多的读写端口提供支持，这使得共享寄存 器文件被多个功能部件访问的时候冲突增加，处理器的时钟频率下降，面积与功 耗大大增加。在这种集中寄存器v l l w 结构中，对于n 个算术单元，随着n 的 增加，寄存器延迟增加n 引2 ，面积增加n 3 ，能耗增加n 3 。分簇结构的提出很好 的解决了集中寄存器v l i w 结构产生的这个问题( 如图1 1 ) ，并且更适合在嵌 入式系统中使用。一个分簇的v l i w 体系结构有多个寄存器文件，每个寄存器 文件只与一部分功能单元互联。每个寄存器文件和同他相连的多个功能单元组成 一个簇( c l u s t e r ) ，而簇又由互联网络相连。分簇结构在保持高时钟频率的同时， 避免了高能耗并减小了芯片面积。这种分簇结构中，对于n 个功能单元，随着n 的增加，互联总线延时增加n ，面积与功耗增加n 2 。 1 1 2v liwd s p 与编译器 图1 1 分簇体系结构 总体来讲v l i wd s p 有以下一些特点：( 1 ) 一次发射一条长指令，其中包含 多个操作，而不是像超标量处理器那样一次发射多条指令。这样做可以减轻指令 发射逻辑电路的带宽，因为超标量处理器中为了发射多条指令的需要，必须将指 令发射逻辑电路流水化，并提高带宽，使其硬件复杂化，同时增加了成本。( 2 ) 长 指令的组装由编译器完成，而不需要像超标量处理器那样由动态调度硬件完成， 从而进一步减轻硬件负担，当然也丧失了动态调度的优点。所以，v l i w 与超标 第一章绪论 量相比较，硬件相对简单、廉价。( 3 ) 为了使所有功能单元充分发挥作用，必须 要开发更多的指令并行性，即有足够多能并行执行的指令去填充v l i w ，这就需 要采用全局调度技术。 分簇的v l l wd s p 结构复杂且应用程序的复杂度不断增加，使得用汇编语 言编写应用程序难度大且效率不高，因此现在d s p 应用程序编译的编写多数采 用高级语言，比如用c 语言也可以和底层硬件打交道。采用高级语言能快速的 开发应用程序，但对编译器提出了挑战，因为高级语言到低级语言的翻译是通过 编译器来完成的，且编译器必须针对机器的体系结构，按照程序员的意思对程序 进行合理的优化。因此编译器是高级语言开发应用程序不可或缺的部分。当编译 器编译应用程序时，必须在满足正确性的前提下，通过合理的调度方法尽可能的 让更多的指令利用有限的机器资源，把没有依赖且没有资源冲突的指令放在一起 发射，以减少程序的执行时间。由于v l i wd s p 采取的是一种分簇的体系结构。 因此，还需要对其指令分簇，以充分利用各个簇上的资源。近年来随着v l i w 机 器的发展，v l i w 编译的研究也逐步深入起来。可重定向编译为v l i w 编译提供 了关键技术。 编译器的研究与发展经历了相当长的历史，现在各大高校和研究机构对于编 译技术的研究仍不失热度。现代编译器一般包括词法分析、语法分析、中间语言 生成、中语言优化、目标机汇编代码生成。而在以前由于目标机体系结构和指令 集不一样，传统的编译器的形式是一个特定的编译器支持一类目标体系结构。然 而在处理高级语言的过程中，很多模块是可以复用的。比如词法分析、语法分析 就不需要特定的体系结构去支持。于是，为了编译成分的复用和编译技术的共享 以及人们在较高抽象层次的平台上开发编译器和研究相关，在上世纪9 0 年代， 国外的一些著名高校和研究机构开始了编译基础设施研制工作。编译基础设施一 般支持不同平台，并且支持多种源语言，是一种可重定向的开发编译环境。它为 各种平台的移植和优化提供了一个基本的框架。编译器开发人员利用编译基础设 施，只需要很少的修改，就可以开发出支持目标体系结构的编译器了。比如g n u 项目的g c c ( h t t p ：g c c g n u o r g ) ，s g i 公司的o p e n 6 4 ( w w w o p e n 6 4 n e t ) ，苹果公 司的l l v m ( h t t p ：l l v m c s u i u c e d u ) 以及伊利诺伊大学香槟分校( u i u c ) 的 i m p a c t ( h t t p ：w w w c r h c u i u c e d u i m p a c t ) 都是可重向的编译器。 可重定向编译器一般分为编译器前端和编译器后端。编译前端是把高级语言 经过词法分析、语法分析转换成与机器无关的中间语言，再对中间语言进行一些 与机器无关的优化：编译后端一般是与机器相关的，它针对目标机的体系结构， 做一些与机器相关的优化，再最终生成目标机的汇编代码，而目标机的信息可以 通过机器描述让后端读入，因此，开发某种特定体系结构的编译器，只需修改机 第一章绪论 器描述，再对后端做很少的改动，就可以完成开发过程。图1 2 是可重定向编译 器的基本框架。 广 l 1 2 研究意义 图1 。2 可重定向编译器 本文工作的意义包括而不局限于以下几点： 重定向编译基础设施到b w d s p l 0 0 ，使得b w d s p l 0 0 的用户在较少损失或 不损失效率的情况下可以自由的用高级语言c 开发应用程序。 用户开发应用程序的周期的缩短和效率的提高对b w d s p l 0 0 有推广作用。 为可重定向编译基础设施到某款特定芯片的成功移植又添新的案例。 提出的指令分簇和调度算法也适用于其它类似的体系结构。 1 3 研究内容 我们的目标体系结构是一款3 2 位的v l i wd s p ，名字叫b w d s p l 0 0 。它是 由某研究所自主研制和开发。我们要研究的问题主要集中在两个方面：一、怎么 利用可重定向编译器为b w d s p l 0 0 生成能正确执行的代码。比如如何制定 b w d s p l 0 0 机器描述：如何把前端翻译出来的中间语言翻译成与机器相关 b w d s p l 0 0 能处理的汇编指令；如何对b w d s p l 0 0 进行寄存器分配；如何最终 生成b w d s p l 0 0 汇编语言。二、将可重定向编译基础设施重定向到b w d s p l 0 0 后，如何进一步利用v l i w 体系结构，提取指令级并行。因为可重定向编译目 第一章绪论 前还有局限性，与体系结构相关的优化，还须由编译器的开发者自己去制定完成。 本文就是针对这些问题一步一步制定可重定向编译器到b w d s p l 0 0 的移植 和优化。 1 4 论文组织 这篇论文各章节安排如下： 第1 章，绪论，给出了整个论文的主要研究问题。首先简要介绍了v l i wd s p 的概念及其与编译器的相互关系。接着，给出了为b w d s p l 0 0 设计编译器的研 究意义，最后，给出全文的章节安排。 第2 章，b w d s p l 0 0 编译的研制，首先介绍了一些相关工作：再对b w d s p l 0 0 编译器做了一个简要介绍；然后又分再介绍了b w d s p l 0 0 编译器的前端和后端， 前端生成与体系结构无关的中间代码并做一些常规的与机器无关的优化而后端 则是针对目标机器做了一些相关优化并生成汇编代码；最后着重介绍了机器描 述、指令注释、寄存器分配和目标代码生成。 第3 章和第4 章是讲b w d s p l0 0 编译器的优化部分。针对b w - d s p l 0 0 的体 系结构，第3 章提出了一种基于寄存器的压力的分簇算法，依次介绍了分簇算法 的动机、设计和实现，以及实验结果与分析；第4 章针对s i m d 指令，设计了 s i m d 指令的分簇算法，然后是结果的讨论。 第5 章为b w d s p l 0 0 的指令级并行部分。主要包括非循环的指令调度和循 环的指令调度技术。 第6 章为全文的总结，概括了本文的主要贡献并给出了可能的未来研究方 向。 第2 章i m p a c t 到b w d s p l 0 0 编译器的移植 2 1 引言 第2 章i m p a c t 到b w d s p l 0 0 编译器的移植 b w d s p l 0 0 编译器是基于可重定向编译器i m p a c t 的移植。我们着重修改 了i m a p c t 编译器的后端，使之能产生正确而高效的b w d s p l 0 0 汇编代码。 b w d s p l 0 0 编译器后端主要分成以下几个部分：指令注释，指令分簇，指令调 度，寄存器分配，代码生成。本人的主要工作是指令分簇和调度及汇编代码生成。 2 2 相关工作 超长指令字概念是f i s h e r 在8 0 年代提出，从那时开始，超长指令字的编译 技术就一直是体系结构和编译器研究的工作者的一个研究热点。在e p i c ( 显示 并行指令计算) 的安腾处理器出现之后，对超长指令字编译技术的研究就越发火 热。f a r a b o s c h i 等综述了指令集并行技术并重点分析了基于范围的指令调度技术 ( r e g i o n b a s e ds c h e d u l i n g ) 和循环指令调度优化技术( f a r a b o s c h i ，2 0 0 0 ) 。 很多研究机构也使用可重定向编译基础设施为特定的体系结构开发相关编 译器。r a j a g o p a l a n 等用i m p a c t 为f u j i t s uh i p e r i o nd s p 开发了编译器 ( r a j a g o p a l a n ，2 0 0 1 ) 。国防科学技术大学计算机科学技术学院也用i m p a c t 为 y h f td s p 开发了一款编译器( 胡定磊，2 0 0 7 ) 。k i m 等用z e p h y r 编译设施为p a i o n p p i i 开发了一个编译器( k i m ，2 0 0 2 ) 。清华大学计算机系用可重向编译基础设施 o p e n 6 4 为p o w e r p cp r o c e s s o r 构造了一个编译器( m i n gl i n ，2 0 0 8 ) 。这些开发者 都在原有编译器基础之上，为了提高指令级并行都针对目标体系结构进行了相关 的优化。 2 3b w d s p l0 0 编译器研制介绍 b w d s p l 0 0 是采用的是i m p a c t 可重定向编译基础设施。i m p a c t 编译器 支持c 语言，它的设计非常模块化，各个模块之间的耦合非常少，它的实质是 把编译过程分成若干个不同的阶段，每个阶段都有着各自不同的输入文件和输出 文件。i m p a c t 所产生的中间文件由脚本语言控制与它的各个模块相连。 b w d s p l 0 0 编译器的整个编译过程见图2 1 。 第2 章i m p a c t 到b w d s p l 0 0 编译器的移植 图2 1b w d s p l 0 0 编译器框架 2 3 1b w d s p l 0 0 编译器前端 b w d s p l 0 0 编译器前端使用的中间语言称为p c o d e ，它能有效的表达源语言 级信息。p c o d c 等价于语法分析过后的c 语言代码。p c o d c 分为内部数据结构和 外部文件。其中内部数据结构是抽象语法树形式，外部文件是语法树的前缀输出 的一串原子和括号。b w d s p l 0 0 编译器前端是e d g ( e d i s o nd e s i g ng r o u p ) 完 成的从c 代码到中间语言p c o d e 的转换。 剖析( p r o f i l i n g ) 过程是在p c o d e 生成之后完成的。剖析信息的生成是为了 完成后端一些高级的优化，比如软件流水和指令调度。它是将p e o d e 转换成等价 的c 语言代码，再在该代码中插入一些探针( p r o b e s ) 来收集程序执行的行为信 息，再将c 代码在目标平台上编译执行产生剖析文件信息，接着读生成的文件， 将它们的信息加在p c o d e 的适当位置。 前端的最终模块是p c o d e 到l e o d e 的转换，这一步是对中间语言的一个降低 过程( 1 0 w e r ) 。l c o d e 是一些简单的、不存在嵌套的指令。 2 3 2b w d s p l 0 0 编译器后端 b w d s p l 0 0 后端使用的中间语言是低级别的l c o d e ，它是一种与机器无关的 指令集也是一种寄存器传递语言，与大多的l o a d s t o r e 体系结构的指令集相似。 l c o d e 亦包括内部数据结构和外部文件两种表示形式。这两种表示形式在语义上 是等价的，也有基本的输入输出模块完成两种形式的转换。 第2 章i m p a c t 到b w d s p l 0 0 编译器的移植 l c o d e 的数据结构分为lf u n c ，l _ c b ，l - o p e r 三个层次。最上层的l _ f u n c 表 示一个函数( p u ) 。中间的层次是l - _ c b ，它表示一个控制块( c o n t r o lb l o c k ) 的 信息。控制块一般是一个基本块( b a s i cb l o c k ) ，也可以是一个超块( s u p e r b l o c k ) 。 最底的一层是l _ o p e r ，它是指一条条的操作指令。它们之间的关系见图2 2 所 示。 图2 2l _ f u n c ，l _ c b ，l - - o p e r 的层次图 当编译器把p c o d e 转换到l c o d e 之后会产生很多冗余信息。因此，需要做一 些常规的优化以提高汇编代码的执行效率。在l c o d e 阶段做的常规优化是与 b w d s p l 0 0 体系结构无关的，具体有：复写传播、多余l o a d s t o r e 消除、常数传 播、强度削弱、公共子表达式消除、循环不变代码外提、无用代码删除等等。 除了常规的优化之外，还可以对l c o d e 进行超标量( s u p e r s c a l a r ) 优化。超 标量优化的目的是提高指令级的并行。具体包括循环展开、寄存器重命名、累加 器变量扩展、归纳变量扩展、搜索变量扩展、操作合并、强度削弱、树高度削减 等等。有关s u p e r s c a l a r 优化可以进一步参考文献( d m l a v e r y ，1 9 9 3 ) 。 2 4 关键技术研究与实现 b w d s p l 0 0 编译器的关键技术在于重定向i m p a c t 的后端。后端代码生的 目标是把中间语言转换成目标体系结构的优化汇编代码。i m p a c t 是一种可重定 向的编译基础设施，它的很多模块都是可重定向的，各个模块都有规定它自己的 任务，它提供了基于机器描述驱动的调度模块和与机器无关的寄存器分配模块。 我们也利用了这些可重定向的模块为b w d s p l 0 0 构造后端，各个阶段都针对了 b w d s p l 0 0 的体系结构做了相应的改造和改进。 在第1 章已经提到过，b w d s p l 0 0 有4 个同构的簇( 簇x ，簇y ，簇z ，簇t ) ， 因此对b w d s p l 0 0 的指令调度和寄存器分配都涉及到了分簇的问题。有关分簇 第2 章i m p a c t 到b w d s p l 0 0 编译器的移植 的优化将在第3 章和第4 章中讨论，有关指软件流水和指令调度将在第5 章讨 论。 代码生成是以i m p a c t 前端将c 程序处理得来的与机器无关的中间代码 l c o d e 为输入，最终生成b w d s p l 0 0 汇编代码。代码生成主要分成6 个模块。 分为是指令注释，指令分簇，软件流水( b r r a u , 1 9 9 4 ) ，寄存器分配( e c h o w , 1 9 8 4 ) ，指令调度( j a f i s h e r ，1 9 8 1 ) 和汇编代码生成，如图2 3 所示，其中实 线部分为生成正确的目标代码所必须经历的阶段，虚线框是为了提高目的代码的 运行效率而采取的优化手段。 图2 3b w d s p l0 0 代码生成总体框架 下面就具体讨论机器描述、指令注释、寄存器分配、生成汇编代码。其它一 些优化模块会在后续章节做进一步的详细讨论。 2 4 1b w d s p l 0 0 机器描述 每个编译阶段在完成各自的目标时都基本上需要特定的机器信息，比如结构 的对齐方式和指令的延迟，而提供这些信息的模块正是机器描述( m a c h i n e d e s c r i p t i o n , m d e s ) 。而机器描述则提供给指令调度所需要的指令所使用的机器资 源信息。 机器描述文件是用来描述指令信息的，它包括指令的格式、指令的延迟以及 指令执行占用的资源等信息。描述机器的语言一种类似于数据库定义的语言称为 h m d e s 。由它定义的机器描述如图2 4 所示，下面分别介绍各部分的组成。 第2 章i m p a c t 到b w d s p l 0 0 编译器的移植 图2 4 机器描述文件 1 、操作格式 机器描述的格式信息描述了目标机体系结构支持哪些类型的操作数。它用了 f i e l d 和 来表示这些信息。t y p eo p e r a t i o n f o r m a t f i e l dt y p e 描述了汇编码的操作数的类型信息；而o p e r a t i o nf o r m a t 则描述 了操作数的格式信息。比如b w d s p l 0 0 的加法指令，只能是d e s t = s r c 0 十s r e l 的格式，各个操作数只能是寄存器。 2 、资源使用信息 机器描述的资源使用信息描述了处理器的资源和指令使用该资源的方式。 r e s o u r c e 用来抽象处理器的资源，比如把每个a l u 都抽象成一个r e s o u r c e ； r e s o u r c e描述了这些资源在流水线中使用的时间信息；把usage r e s o u r c eu n i t 能够产生相同运算效果的r e s o u r c eu s a g e s 归并成一组，一组就是一个功能单元 ( f u n c t i o nu n i t s ) ；t a b l eo p t i o n 描述了执行同一个运算所用的资源的集合； r e s e r v a t i o nt a b l e 描述了一条指令运行的方式，比如一条加法指令运行时需要1 个a l u 和1 个发射槽，它可以用任意的组合方式从t a b l eo p t i o n 中取出一组来 运行。 3 、延迟信息 机器描述的延迟信息描述了怎么计算指令之间的依赖距离( d e p e n d e n c e d i s t a n c e s ) 。延迟信息由两个段组成，分别是o p e a n d _ l a t e n c y 和o p e r a t i o n _ l a t e n c y ， 其中o p e r a n d _ l a t e n c y 表述了操作数被使用的时刻而o p e r a t i o n _ _ l a t e n c y 则描述了 第2 帝i m p a c t 到b w d s p l 0 0 编译器的移植 该指令在什么时候使用该操作数。 4 、操作信息 机器描述的操作信息描述了目标体系结构支持的指令以及指令是怎么被调 度的。操作信息主要由两个段组成，分别是s c h d u l i n g 和 。a l t e r n a t i v e o p e r a t i o n s c h e d u l i n g _ a l t e r n a t i v e 用来描述指令的调度方式，即指令的操作数，指令所使用 的资源以及指令之间的依赖距离。o p e r a t i o n 例举了目标体系结构支持的汇编级 指令并且还协调各条指令的调度。 2 4 2 指令注释 指令注释是后端c o d e g e n 模块的第一个阶段。指令注释的功能主要是将机器 无关的l c o d e 中间代码转换成机器相关m c o d e 中间代码，转换后的m c o d e 中间 代码中的每条指令对应一条目标机器的汇编指令，但其格式依然与l c o d e 中间代 码相似( 因为后续的调度、寄存器分配等都是使用这种格式的) 。需要特别注意 的是除法指令的注释，因为在与目标体系结构无关的l c o d e 层面上是允许出现除 法指令的，但b w d s p l 0 0 机器没有直接的除法指令。所以只能通过求倒数和乘 法器来实验除法指令。其中浮点除法是按照公式2 1 来完成的 三：0 三) + 上) 一 土一1 j ，) yyyy y ( 2 1 ) 定点除法可分解为一系列的减法和移位操作。先对被除数进行n 位右移运 算，其移位后和除数在同一个数量级或最多只差一个数量级。移位后的被除数与 除数进行比较，如果被除数大于或等于除数，商对应的位就得l ，否则为零。接 下来，被除数减去左移n 位后的除数，差值作为被除数继续进行上述运算，直到 余数为零或被除数位数小于除数位数。 举例： d i v 【( r1i ) ( r2i ) ( r3i ) 】 c b2 ： r 3 = r 2 1 r 4 = r 2 r 3 r l = r l + 1 b rr 3 = r 2 跳转到c b 2 第2 章i m p a c t 到b w d s p l 0 0 编译器的移植 2 4 3 寄存器分配 寄存器分配主要工作是在分簇完成之后，为不同簇上m c o d e 的虚拟寄存器 正确高效地分配物理的通用寄存器和地址寄存器。高效的寄存器分配实现，能够 最大限度地使用b w d s p l 0 0 提供的寄存器资源，减少寄存器溢出情况的出现 ( e c h o w , 1 9 8 4 ) 。 为保证寄存器分配的正确性，必须为生存周期存在冲突的两个虚拟寄存器分 配了不同的物理寄存器。i m p a c t 的实现中通过图着色算法来实现。考虑寄存器 分配的效率，i m p a c t 的实现中通过数据流分析得到每个虚拟寄存器出现的频 率，然后根据此频率计算出该虚拟寄存器的优先级，按优先级对虚拟寄存器进行 排序而依次分配物理寄存器。这样的实现可以有效地控制由于寄存器溢出导致的 l o a d ，s t o r e 指令出现的次数。 i m p a c t 的寄存器分配模块提供一个与机器无关的接口。通过直接在这个接 口上根据b w d s p 的寄存器结构来配置寄存器文件，就可以使用i m p a c t 中的 公共寄存器分配实现，完成寄存器分配模块的移植。 i m p a c t 的寄存器分配模块中，内部表示寄存器的数据结构为一个数组。该 数组包含了目标机器上各种类型和存储约定的寄存器。而寄存器分配的实现是直 接在这个数组上对各个虚拟寄存器分配实际的物理寄存器。这个通用的数据结构 使得实现寄存器分配时可以不考虑具体的机器。 表2 。1 存器分配内部数据类型 内部类型数据类型 r 烈t i n t e g e r r _ - l l o n g l o n g l o n g f l o a t r f l o a t r _ d o u b l e d o u b l e r _ p o i n t e r p o i n t e r 第2 章l m p a c t 到b w d s p l 0 0 编译器的移植 表2 2 寄存器分配内部存储约定 内部类型存储约定 r c a l l e r c a l l e r - s a v e dr e g i s t e r s r c a l l e e c a l l e e s a v e dr e g i s t e r s r c a l l e r m a c r o c a l l e r - s a v e dm a e r o r e g i s t e r s 当针对实际的机器时，需要将目标机器中的寄存器文件映射到这个内部数组 上。描述实际的寄存器主要通过两个属性，数据类型和存储约定。这两个属性的 主要内容见表2 1 和表2 2 。这两个属性的组合定义了一个“r e g i s t e rb a n k ，它由 所有具有相同属性的寄存器组成。我们要将目标寄存器文件中所有的r e g i s t e r b a n k 都映射到内部数组中。这个映射通过函数rd e f m ep h y s i c a lb a n k 来实现 针对b w d s p 的寄存器分配模块的移植分两部分，b w d s p 寄存器文件的映 射和寄存器分配模块中与目标机器相关的函数的修改。前者实现寄存器文件的映 射，而后者则是根据b w d s p 的机器规格和指令集修改模块中与机器相关的函 数。 函数堆栈调用模块是在寄存器分配完成之后，实现对函数调用堆栈的管理和 访问。它的主要工作有，计算函数需要的堆栈空间大小，进入和退出函数时，堆 栈指针s p 和帧指针f p 的移动，c a l l e es a v e 类型寄存器的保存和恢复，以及将访 问堆栈指令中的偏移量调整为相对s p 或者f p 的偏移量。 函数堆栈调用模块是在寄存器分配完成之后，实现对函数调用堆栈的管理和 访问。它的主要工作有，计算函数需要的堆栈空间大小，进入和退出函数时，堆 栈指针s p 和帧指针f p 的移动，c a l l e es a v e 类型寄存器的保存和恢复，以及将访 问堆栈指令中的偏移量调整为相对s p 或者f p 的偏移量 2 4 4 ；i - 编代码生成 汇编代码生成是b w d s p l 0 0 的最后一个模块，它的目的把最终的m c o d e 编 译成b w d s p l 0 0 的汇编代码。该过程主要是对函数的每个控制块的指令进行扫 描，循环的对指令进行处理。m e o d e 是与机器相关的中间语言，它有唯一的编号 对应着机器指令。翻译时，只需按照指令编号去找到相应的函数即可。对于经过 指令分簇后的指令，需要在指令的属性中取出簇的信息，再将簇的信息映射到汇 编代码中；对于指令调度过的指令，在每个控制块中，需要把在同一时间发射的 第2 章i m p a c t 到b w d s p l 0 0 编译器的移植 指令通过”| i ，符号连接起来，从而产生并行的汇编代码。 2 5 本章小结 本章主要介绍了通过可重定向编译器i m p a c t 到b w d s p l 0 0 编译器的制 定。制定b w d s p l 0 0 的编译器的重点在于编译器的后端。并着重介绍了编译器 后端一些重要的模块。 b w d s p l 0 0 机器描述规定目标机器的指令格式以及资源使用信息。 b w d s p l 0 0 代码生成模块通过指令注释、寄存器分配、汇编代码生成可以一步 步把与机器无关的中间语言翻译成b w d s p l 0 0 的汇编语言。 第3 章基于寄存器压力的v m w d s p 分簇算法 第3 章基于寄存器压力的v l l wd s p 分簇算法 3 1 引言 本章针对分簇超长字体系结构提出了一种基于寄存器压力的分簇算法。考虑 寄存器的压力可以减少寄存器的溢出，并能增加指令并性。实验结果表明，该算 法可以得到较好的优化效果。寄存器是程序运行时最宝贵的资源之一，软件流水 在对v l l wd s p 指令调度的同时，会显著的增加寄存器的压力，从而导致寄存 器溢出，软件流水中止。在以往的研究中，软件流水之前的指令分簇会更多的考 虑指令并行性，往往会把寄存器的压力交给寄存器分配阶段，当物理寄存器不够 分配时会寄存器溢出。通过考