（计算机科学与技术专业论文）vliw+dsp汇编器与代码生成器的设计与实现.pdf

国防科学技术人学研究生院学位论文 摘要 与传统d s p s 相比，现代d s p s 采用更多的i l p 技术以提高机器性能。另一方面，它 们呈现出规整的、可编译的体系结构，使得能够为它们构造高效的优化编译器。本文讨 论这样一款d s p ，它采用分簇的v l l w 体系结构，能够在单个时钟周期同时执行多个操 作。我们叙述这款v l l wd s p 的汇编器和代码生成器的构造。 为了便于对向前引用的处理，v l i wd s p 汇编器组织成两遍结构。第一遍仅记录源 文件中的符号( 标号) 信息，第二遍重新扫描源文件，利用先前收集的信息产生目标文 件。v l l wd s p 汇编器的特点包括：借助l c x 和y a c c 生成词法和语法分析器；汇编语句 在汇编器中以内部表示的形式存在：指令的编码信息存于数据表格，编码指令时使用通 用的过程查询这些表格以决定指令的编码格式和o p c o d e ，然后调用相应的编码函数产生 机器代码。 v l i wd s p 代码生成器在i m p a c tc 编译器框架基础上实现。我们为v l l wd s p 定 制它的机器规格说明和机器描述，并利用i m p a c t 的模板构造它的代码生成器。v l l w d s p 体系结构的一个显著特点是分簇，即大而集中的寄存器文件被分成多个块，每个块 与几个功能单元相关联组成簇。与这一特点相对应，代码生成的一个重要步骤是簇分配， 即为每个操作及其操作数映射合适的簇。簇分配应使得各簇的功能单元得到充分利用， 并设法减少簇之间的数据传递。我们给出统一的簇分配与调度算法( u a s ) 针对v l l w d s p 的实现，算法的特点是簇分配与调度一同进行，当调度一个操作时，同时为这个操 作和它的操作数分配合适的簇。 关键词：；t - 编器代码生成器v l i wd s p 簇分配调度u a s 国防科学技术大学研究生院学何论文 a b s t r a c t c o m p 盯e dw i 也t r a d i t i o n a ld s p s m o d e r nd s p su s em o r ei l pt e c h n o l o g i e st oi m p r o v e t h e i rp e r f o r m a n c e o nt h eo t h e rh a n d ，m e yp r e s e n tr e g u l a ra n dc o m p i l a b l ea r c h i t e c t u r e s ， w h i c he n a b l ec o n s t r u c t i o no fe f f i c i e n t , o p t i m i z i n gc o m p l i e r sf o rt h e m i nt h i st h e s i sw e d i s c u s ss u c had s p ，w h i c hu s e sac l u s t e r e dv l i wa r c h i t e c t u r ea n dc a np e r f o r mm u l t i p l e o p e r a t i o n ss i m u l t a n e o u s l yd u r i n gas i n g l ec l o c kc y c l e w ed e s c r i b et h ec o n s t r u c t i o no ft h e a s s e m b l e ra n dt h ec o d eg e n e r a t o ro f v l i wd s e t oe a s et h ep r o c e s s i n go ff o r w a r dr e f e r e n c e s ，o u ra s s e m b l e ri so r g a n i z e da sat w o - p a s s s t r u c t u r e i nt h ef i r s tp a s s ，i to n l yr e c o r d si n f o r m a t i o na b o u ts y m b o l s ( 1 a b e l s ) i nt h es o u r c ef i l e i nt h es e c o n dp a s s ，i ts c a n st h es o u r c ef i l ea g a i n ，a n db yu s i n gt h ei n f o r m a t i o nc o l l e c t e de a r l i e r g e n e r a t e st h eo b j e c tf i l e t h ev l i wd s pa s s e m b l e r sf e a t u r e si n c l u d e ：i tu s e sl e xa n dy a c ct o g e n e r a t et h el e x e ra n dt h ep a r s e rr e s p e c t i v e l y ；a na s s e m b l ys t a t e m e n te x i s t sa sa ni n t e r n a l r e p r e s e n t a t i o ni nt l l ea s s e m b l e r ；i n s t r u c t i o n s e n c o d i n gi n f o r m a t i o ni ss a v e di nt h ed a t at a b l e s a n dw h e ne n c o d i n ga ni n s t r u c t i o nag e n e r i cp r o c e d u r ei se m p l o y e dt os e a r c ht h e s et a b l e st o d e c i d eo ni t se n c o d i n gf o r m a ta n do p c o d e ，a n dt h e nac o r r e s p o n d i n ge n c o d i n gf u n c t i o ni s c a l l e dt op r o d u c ei t sm a c h i n ec o d e o u rc o d eg e n e r a t o ri s i m p l e m e n t e db a s e do ni m p a c tcc o m p i l e rf r a m e w o r k w c c u s t o m i z e dam a c h i n es p e c i f i c a t i o na n dam a c h i n ed e s c r i p t i o nf o rt h ev l i wd s p , a n d c o n s t r u c t e dt h ec o d eg e n e r a t o ru s i n gt h et e m p l a t ep r o v i d e db yi m p a c t o n eo f t h ep r o m i n e n t f e a t u r e so f o u rd s p sa r c h i t e c t u r ei sc l u s t e r i n g ，t h a ti s ，ab i gc e n t r a l i z e dr e g i s t e rf i l ei ss p i r t e d i n t om o r es m a l lp i e c e s ，e a c ha n di t ss e v e r a la s s o c i a t e df u n c t i o n a lu n i t sf o r m i n gac l u s t e r w i t l l t h i sf b a t l l r e ，a ni m p o r t a n tp h 弱eo fo a rc o d eg e n e r a t i o ni sc l u s t e ra s s i g n i n g ，w h i c hm a p s o p e r a t i o n sa n dt h e i ro p e r a n d st oa p p r o p r i a t ec l u s t e r s c l u s t e ra s s i g n m e n ts h o u l dm a k e m a ) ( i m a lu s eo ff u n c t i o n a iu n i t sa c r o s sc l u s t e r s a n dr e d u c ei n t c r c l u s t e rd a t am o v e m e n t b e s i d e s w ei m p l e m e n t e dt h eu n i f i e da s s i g na n ds c h e d u l e ( u a s ) a l g o r i t h mt os u p p o r tc l u s t e r a s s i g n m e n t ，w h i c hh a st h ef o l l o w i n gf e a t u r e s ：c l u s t e ra s s i g m n ga n ds c h e d u l i n ga r eu n i f i e d ， a n dw h e ns c h e d u l i n ga no p e r a t i o n t h eo p e r a t i o na n di t so p e r a n d sa r ea s s i g n e dt ot h e i r a p p r o p r i a t ec l u s t e r sa tt h es a m et i m e k e y w o r d s ：a s s e m b l e r , c o d eg e n e r a t i o n ，v l i wd s p , c l u s t e ra s s i g n i n g ，s c h e d u l i n g ，u a s 国防科学技术大学研究生院学位论文 图2 1 。i w d s p 的数据通路 图目录 图2 - 2v l i wd s p 的流水线。 图3 - 1v l i wd s p 汇编器的处理流程一 图3 - 2 。1 wd s p 汇编器的结构 图3 - 3 语句数据结构 图3 - 4 汇编命令数据结构 图3 5 执行包数据结构 图3 - 6 指令数据结构 图3 7 操作数数据结构 ! ； 9 1 0 1l 11 1 ：! 图3 - 8 表达式数据结构1 2 图3 - 9 地址数据结构 图3 1 0 语法分析器的部分文法规则1 4 图3 - l l 识别操作数的文法规则1 4 图3 1 2 段数据结构l5 图3 1 3 符号数据结构1 6 图3 1 4 v l i w d s p 部分机器指令格式1 7 图3 1 5 功能单元数据结构1 8 图3 1 6 功能单元表的部分内容一1 8 图3 1 7 寄存器数据结构 图3 1 8 寄存器表的部分内容 ll 1 8 图3 - 19 控制寄存器数据结构一1 9 图3 - 2 0 控制寄存器表的部分内容1 9 图3 2 l 操作数类型的表示一1 9 图3 2 2 操作数类型1 9 图3 - 2 3 判断操作数类型是否兼容的算法2 0 图3 2 4 获取指令操作数类型的算法一2 1 图3 2 5 指令格式的表示2 l 图3 - 2 6 指令编码映射表2 2 图3 - 2 7 指令表及其数据结构2 3 图3 - 2 8 求解指令各操作数的类型的算法一2 3 图3 2 9 求解指令编码映射表匹配项的算法2 3 图3 3 0 重定位的数据结构2 4 图3 - 3lc o f f 文件格式2 5 图4 一li m p a c tc 编译器框图一2 7 v 国防科学技术大学研究生院学位论文 图4 - 2l c o d e 内部表示的层次结构 图4 3h m d e s 2 的段层次结构 图5 - 1v l l wd s p 的函数参数传递约定 图5 - 2v l l wd s p 运行栈结构 图6 - 1v l l wd s p 代码生成器框图 图6 23 2 位常量传递的注释 图6 3j s r 的注释一 图7 1 分簇的机器结构 图7 2u a s 算法 图7 - 3i m p a c t 调度器的结构 图7 4i m p a c t 的l i s t 调度算法 图7 5 簇分配与调度算法 图7 _ 6 交叉通路可否使用的判断 图7 7s l o t 对于代码输出的影响 图7 - 8f i r 滤波器程序 图7 - 9f i r2l 程序 2 9 31 3 3 3 4 3 8 图7 1 0f i r _ 1 - 2 程序6 2 图7 1 lf i r 滤波器的程序流图 图7 - 1 2 寄存器数量不受限时i i r 不同展开版本的加速比比较 图7 1 3 f i r21 和f i r12 内循环的部分程序依赖图。 图7 1 4 寄存器数量不受限时优先权函数的比较 图7 一1 5 使用n o n e 和r a n d o m 作优先权函数时的簇分配 图7 - 1 6 寄存器数量受限时f i r 不同展开版本的加速比比较 图7 1 7f i r14 内循环的部分程序依赖图 图7 1 8f i r22 内循环的部分程序依赖图 图7 - 1 9 寄存器数量受限时优先权函数的比较 甜”娟弱曲酡酡 以“酊酊酌卯卵醯 国防科学技术人学研究生院。学位论文 表目录 表2 - 1 指令的执行阶段描述5 表6 1 边延迟的计算公式4 2 表7 1 簇分配算法的特征4 8 表7 - 2 寄存器数量不受限时的f i r 执行时间6 3 表7 - 3 寄存器数量受限时的f i r 执行时间6 6 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果尽我所知，除了文中特另4 加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意 学位论文题目：坠巡旦望正籀墨生岱堡垒盛墨煎遮盐生塞墨 学位论文作者签名 陈鸯蠡式 日期：p 。舛，月修日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：婴理q 望垂缠墨星岱塑生成墨盟遮! 士量塞塑 学位论文作者签名：盟童：丛 日期：，d d ，年，月r ，日 日期： 弘疗年j 月9 日 图防科学技术人学研究生院学位论文 第一章引言 1 1 课题背景及研究内容 高速通信应用正在飞速增长，数字信号处理器( d s p s ) 在其中扮演了重要角色。事 实上，d s p s 已经成为无处不在的促成音频、视频和通信一体化的“赋能者”【l j 。 传统d s p s 是针对特殊的应用需求而设计的，其不规整的体系结构使得为它们难以 设计出好的系统软件，d s p 应用的编程一般使用低级的汇编语言。随着d s p 应用面越来 越广，复杂度越来越深，若仍旧使用汇编语言，则会出现程序员不够用、应用开发进程 受阻的情况。为了避免这种情况，就需要能够用易于掌握的高级语言来编写应用程序。 这种需求促使d s p s 体系结构由不规整向规整转变，成为可编译的。可编译性是现代d s p s 区别于传统d s p s 的重要特征”j 。 另一方面，d s p 应用的主流算法其内部循环大都可表达为向量运算，这些运算具有 天然的指令级并行性( i n s t r u c t i o n l e v e l p a r a l l e l i s m ，i l p ) 拉j 。例如，典型的d s p 核心程 序f i r 滤波器可以表示为肌= c # 。此外，多数d s p s 应用于对实时处理有特殊需求 的嵌入式环境，这种环境要求d s p s 具有很好的性能。采用i l p 技术是改进机器性能的 一种重要途径。 i l p 处理器常用的两种体系结构为超标量和超长指令字( v l i w ) 。为了取得更高性 能，现代d s p s 大都使用v l l w 体系结构。v l l w 是一种水平指令结构，每条指令包含 多个并行执行的、相互间独立的简单操作。v l l w 体系结构为编译器呈现出一种简洁的 界面，有利于构造高效的优化编译器。事实上，v l l w 体系结构依赖编译器静态地确定 程序各操作的调度顺序，编译器对于v l l w 机器性能的发挥至关重要。采用v l l w 体系 结构的d s p s 有s t a r c o r es c l 4 0 、a d it i g e r s h a r c 、t ic 6 0 0 0 系列p j 等，而c 6 0 0 0 系列 凭借与之搭配的优秀的集成开发环境c c s 在d s p s 市场占据了很大份额。 本文的论述将围绕一款由国防科大计算机学院研制的定点v l i wd s p l ，主要讨论它 的汇编器和代码生成器的构造实现。汇编器将汇编语言源程序转换为二进制目标文件。 除了阐明这一过程的具体实现，本文需要解决如何使得转换过程尽可能地独立于机器的 指令编码格式的问题。作为编译器后端的重要组成部分，代码生成器将中间代码转换为 优化的目标机器代码。由于本文的v l l wd s p 的几个独有特性，使得为它开发代码生成 器面临挑战。一个最显著特性就是分簇( c l u s t e r i n g ) 3 2 】【3 9 l ，即处理器内核被分成了2 块 ( 称为簇) ，每块由1 个寄存器文件和4 个与之关联的功能单元组成。功能单元能够便捷 地访问本地簇的寄存器，远地簇的寄存器访问则要通过共享的簇间数据通路。分簇有效 工塞些垄堑型递坐：! ! 型望i ! 型煎釜簦望! ： 第1 页 国防科学技术人学研究生院学位论文 地降低了硬件设计的复杂度。从而c p u 的时钟周期可以更快p 9 1 。但是，分簇给编译器 的设计带来了挑战。编译器调度操作时( 在代码生成时发生) ，不仅要充分利用处理器的 功能单元，而且还要使得簇间的数据传递不会过于频繁。也就是说，编译器需要为操作 和它的操作数分配合适的簇，以减少对共享的簇间通路使用的冲突【3 粥。簇分配和调度是 本文的重要研究内容。 1 2 本文贡献 本文主要有以下四个方面的贡献： 第一，给出了v l i wd s p 汇编器的设计与实现。相比常见的标量机器，v l i w 机器 的汇编器其处理过程有诸多不同。例如，指令汇编时，汇编器需要同时处理多条并行的 指令，它们组成一个执行包，接着汇编器需要将这些执行包组织成取指包输出。 第二，透过v l l wd s p 汇编器的构造，本文给出了一种快速构造汇编器的方法【4 引。 这种方法的特点是：借助l e x 和y a c c l 7 1 分别生成词法和语法分析器；指令在汇编器中以 内部表示的形式存在；指令的编码信息存放在数据表格中，编码指令时使用通用的过程 查询这些表格以决定指令的编码格式，然后调用相应的编码函数产生机器代码。使用这 种方法构造的汇编器是易修改的。 第三，给出了v l l w d s p 代码生成器【删【4 5 】的构造。本文的代码生成器基于i m p a c t c 编译器框架【9 j 构造实现。本文讨论了如何定制机器规格说明和机器描述，针对分簇的 机器，机器描述需要作哪些权衡。接着讨论了代码生成的各阶段怎样实现。 第四，实现了簇分配与调度算法。簇分配是分簇机器特有的本文的代码生成器使 用u a s 算法1 4 0 1 做簇分配和调度，本文给出了该算法实现的详细描述。 1 3 论文结构 第二章叙述v l i wd s p 的体系结构，重点讨论与汇编器和代码生成器相关的机器特 性。第三章给出v l i wd s p 汇编器的设计与实现，讨论了汇编器的处理流程、重要模块 的算法实现和一些关键数据结构的设计。第四章描述i m p a c tc 编译器的框架结构。第 五章给出v l l wd s p 的机器规格说明和机器描述。第六章讨论v l l wd s p 代码生成器各 阶段的任务和实现策略。第七章给出簇分配与调度的算法实现。第八章总结全文，并对 今后的工作作一番展望。 第2 页 国防科学技术人学研究生院学位论文 第二章v l i wd s p 的体系结构 本章主要叙述v l i wd s p 的对于编译器或汇编器可见的体系结构特性。这些特性主 要涉及机器的资源约束、指令的执行延迟、指令打包的方法和条件执行。2 1 节描述c p u 的数据通路，给出编译调度时应满足的资源约束。2 2 节简述流水线，给出指令的执行 延迟。2 3 节介绍取指包和执行包的概念。2 4 节介绍条件执行特性。 2 1c p o 的数据通路 v l i wd s p 的c p u 数据通路如图2 1 所示。从图上可看出，c p u 包含两个并列的数 据通路a 和b ( 即簇a 和b ) ，它们分别连着通用寄存器文件a 和b 。每个数据通路包 括四个功能单元( a l 、b c 、m u 、l d ) ，这些功能单元之间相互独立，可同时执行指 令。每个数据通路还各有一个交叉通路( x ) ，用以访问另一通路的寄存器。以下小节进 一步讨论数据通路的各种资源。 图2 1v l i w d s p 的数据通路 2 1 1 通用寄存器文件 数据通路a 和b 各有一个寄存器文件，它们均包含1 6 个3 2 位寄存器。v l l wd s p 支持的定点数据类型有3 2 位数、压缩1 6 位数和4 0 位长型数。3 2 位数自然存放在一个 寄存器中。压缩1 6 位数存放在寄存器的高1 6 位或低1 6 位。v l i wd s p 支持一些s i m d 指令，它们能同时操作一个寄存器中的两个1 6 位数。4 0 位长型数存放在相邻的寄存器 对中。 寄存器访问具有以下限制： 每个时钟周期读同一寄存器的次数不能超过4 ( 条件寄存器的读取除外) ； 第3 页 国防科学技术人学研究生院学位论文 每个时钟周期写同一寄存嚣的次数不能超过l 。 2 1 2 功能单元 数据通路a 和b 各包括四个功能单元，每个功能单元能执行一定范围的操作，叙述 如下： a l 单元主要执行算术、比较和逻辑运算操作： b c 单元主要执行算术、逻辑运算、移位、位操作、分支和常数传递等操作： m u 单元主要执行1 6 位的乘法操作； l d 单元主要执行加减法、地址计算和l o a d 、s t o r e 操作。 从上面的叙述可看出，有些操作仅能被特定的功能单元执行，而另外的操作可被多 个功能单元执行。v l i wd s p 操作的指令集是类r i s c 的。 2 1 3 交叉通路 数据通路a 和b 各有一个交叉通路x ，它允许功能单元从另一通路的寄存器文件读 取操作数。交叉通路的使用具有以下限制： 只有a l 的s r c l 和s r c 2 、b c 和m u 的s r c 2 能够使用交叉通路： 每个时钟周期交叉通路只能被一个功能单元的某个输入使用。 2 1 4 存储访问通路 存储访问通路包括传递数据的通路l d s t 和传递地址的通路d a 。每个数据通路均 有自己的存储访问通路，记为t 。t 通路被l o a d 、s t o r e 操作使用，能够执行l o a d 、s t o r e 的功能单元为l d 。实际上l d 只计算访存地址，访存使用哪个t 通路由目的寄存器( 对 于l o a d ) 或源数据寄存器( 对于s t o r e ) 所在的数据通路决定。例如，在l d l 单元执行 的l o a d ，它的目的寄存器为b 2 ，则l o a d 使用的访存通路为t 2 。 2 1 5 资源约束小结 v l l wd s p 的资源约束大致有以下几种情况： 每个时钟周期不能有两个操作同时使用一个功能单元： 每个时钟周期传递数据的通路不能被多次使用，并且若两个数据通路部分重叠， 则它们不能同时被使用； x 通路仅能供某些功能单元的某些输入使用； 每个时钟周期读同一寄存器的次数不能超过4 ( 条件寄存器的读取除外) ，写同一 寄存器的次数不能超过1 。 2 2 流水线和指令延迟 v l i w d s p 的流水线分为程序读取、译码和执行三站，每一站又出若干个阶段组成， 如图2 - 2 所示。程序读取站包含程序地址生成( p g ) 、程序地址发送( p s ) 、程序访问等 第4 页 国防科学技术火学研究生院学位论文 待( p w ) 和程序接收( p r ) 4 个阶段。每个时钟周期c p u 从存储器读取一个取指包， 它由连续的8 条指令组成。每个取指包又可细分为多个执行包，执行包之间串行分派， 一程序读取 + 译码+ 一执行+ 图2 - 2 v l i w d s p 的流水线 其内部的指令并行分派。 译码站包括指令分派( d p ) 和指令译码( d c ) 两个阶段。在d p 阶段，指令分派部 件将一个执行包的指令并行分派到各自对应的译码器。在d c 阶段，指令被译码器译码。 表2 - 1 指令的执行阶段描述 指令类型 单周期1 6 x 1 6 乘法 s t o r e l o a d分支 e 1 计算结果并写读操作数井开计算地址计算地址产生p g 阶段 入寄存器 始计算的目标地址 执 计算结果并写发送地址和数发送地址至存 e 2 行 入寄存器据至存储器储器 e 3 访问存储器访问存储器 阶 e 4 数据送回c p u 段 写数据至寄存 e 5 器 延迟槽olo45 执行站分为5 个阶段( e l e 5 ) 。指令类型不同，执行它们需要的执行阶段数也不 同，表2 1 给出了各类指令的执行阶段描述。所有指令它们的源操作数( 若存在的话) 都在e l 阶段开始前读取。单周期指令的目的操作数在e l 阶段结束前写入，乘法指令和 l o a d 指令的目的操作数分别在e 2 和e 5 阶段写入。这几类指令的延迟槽个数等于指令执 行阶段数减1 。 s t o r e 写存储器在e 3 阶段，l o a d 读存储器也在e 3 阶段，又由于v l i wd s p 只有l o a d 和s t o r e 指令能够访存，所以只要s t o r e 在l o a d 的前一拍流出，l o a d 指令就能读s t o r e 向 内存写的值，即s t o r e 的延迟槽个数为0 。 分支指令没有目的操作数，它的延迟槽个数等于从分支目标地址产生到目标地址处 的指令进入执行阶段所需的时钟周期数减l 。分支地址在e l 阶段产生，它直接送往程序 读取部件以产生p g 阶段的程序地址。分支目标指令进入执行阶段还需经历程序读取站 的剩余3 个阶段、译码- 站的2 个阶段和e l 阶段，共6 个阶段。所以，分支的延迟槽个 数为5 。 f 常情况，每条指令按照图2 - 2 的阶段顺序流经指令流水线。但是，存储器阻塞和 中断会改变这一顺序。出于存储器阻塞的处理对于编译器是透明的，以下我们仅讨论中 第5 夏 国防科学技术人学研究生院学位论文 断对流水线执行顺序的影响。 2 2 1 中断带来的影响 v l i wd s p 有两种处理中断的模式，使用哪一种取决于当前执行阶段的指令是否有 分支指令，或者有指令在某条分支指令的延迟槽中。 当中断抵达c p u 时，若当前处于执行阶段的所有指令既非分支指令，也不处在某条 分支指令的延迟槽中，则c p u 废弃流水线上( 执行站之前) 所有宋分派的指令，但允许 那些已经处于执行阶段的指令继续执行完。反之，若有分支指令或者有指令处在某条分 支指令的延迟槽中，则中断处理要被推迟，直到分支延迟槽中的所有指令都分派完为止。 上面的叙述可以看出中断改变了已派发和未派发指令的相对延迟，因此除分支指令 外，其它指令的延迟槽填充必须谨慎进行。例如，假定下面的代码片段不在分支指令的 延迟槽中，执行前，寄存器a 1 值为0 ，寄存器a o 指向值为1 0 的内存单元。a d d 在l d w 的延迟槽中，它将a 1 与a 2 的值相加，结果放入寄存器a 3 ( 由于a 1 为0 ，a 3 实际是 a 2 的副本) 。如果中断发生时l d w 已派发，而a d d 恰好未派发，那么l d w 将更新 a 1 ( a 1 的值将为1 0 ) ，接着中断被处理，之后a d d 将a 1 与a 2 的值相加，结果放入 a 3 ( 等于a 2 + 1 0 ) 。显然，结果不正确。之所以出现这种情况是因为中断改变了l d w 写 a 1 和a d d 读a l 应有的先后次序。 + a 0 a 1 a 1 ，a 2 ，a 3 3 a 1 ，a 4 ，a 5 2 3 取指包和执行包 如前所述，c p u 从存储器读取指令的基本单位是取指包，一个取指包包含多个执行 包，每个执行包由多条并行分派的指令组成。执行包的各指令是相互独立的，它们的组 合不受限制，只需满足机器的资源约束即可。v l i wd s p 这种特有的两级打包指令的方 法能够显著地缩短代码长度，减少运行时的访存次数和功耗。 执行包由编译器调度或手工调度形成，取指包则由汇编器合成。c p u 从存储器读取 取指包并分派其中的各执行包的过程正好与汇编器使用执行包合成取指包并将取指包存 放至目标文件的过程相反。有关使用执行包合成取指包的过程在第三章叙述。 2 4 条件执行 v l i w d s p 包括几个条件寄存器：b o 、b 1 、b 2 、a 1 和a 2 。几乎所有的指令都可条 件执行，即指令是否执行依赖于条件寄存器的值。使用条件执行，可以消除程序的一些 控制相关，提高程序的i l p 。 第6 页 1 1 1 1 d l u l a m w d p y d o o p l a n m 国防科学技术人学研究生院学f ) = 论文 第三章v l i wd s p ；i - 编器 汇编器与早期的存储程序计算机相伴出现【5 1 ，它接受和处理符号指令，产生机器指 令。之后，汇编器依次引入了标号、宏和予过程库等特征，其功能大大扩充，它本身也 成为系统程序的组成部分。 汇编器实现汇编语言源程序至二进制目标文件的转换。汇编语言是一种与特定机器 相关的低级程序设计语言，其语句分为助记符指令语句和汇编命令( a s s e m b l e r d i r e c t i v e ) 语句两种类型，指令语旬最后汇编成相应的机器指令，汇编命令语句则由汇编器在汇编 过程中解释执行。 本章给出v l i wd s p 汇编器的设计实现。3 1 节概述c o f f 目标文件，给出了段、 重定位等重要概念。3 2 节简述v l i wd s p 的汇编语言。3 3 节给出汇编器的结构设计， 讨论了遍、遍的任务分工问题。3 4 至3 8 节介绍汇编器各部分的实现。3 4 节讨论语句 的内部表示，3 5 节讨论词法和语法分析器的构造，3 6 节讨论段表和符号表的组织维护， 3 7 节给出了指令汇编的方法，3 8 节给出合成取指包的方法，3 9 节讨论重定位的表示， 3 1 0 节讨论c o f f 目标文件的形成。 3 1c o f f 目标文件 v l i wd s p 目标文件的格式为c o m m o no b j e c tf i l ef o r m a t ( c o f f ) 。c o f f 将代码和 数据按段组织，有利于模块化编程。3 1 1 节简述段的概念，3 1 2 节叙述段的处理过程， 3 1 _ 3 节讨论重定位( r e l o c a t i o n ) ，3 1 4 节叙述外部符号。 3 1 1 段 段是c o f f 文件组织代码和数据的最小单位，它在存储器映像图( m e m o r ym a p ) 上 占据一段连续的地址空间。缺省时c o f f 文件包含三个段：t e x t 段( 通常包含可执行代 码) 、d a t a 段( 通常包含已初始化的数据) 和b s s 段( 通常为未初始化的变量预留空间) 。 此外，还可以创建具名段( n a m e ds e c t i o n s ) ，它们的用法与缺省段类似。 段有两种基本类型：己初始化的段和未初始化的段。已初始化的段包含数据或代码。 例如，t e x t 和d a t a 段都是已初始化的段，利用s e c t 命令还可创建具名的己初始化段。未 初始化的段用于为未初始化的变量( 数据) 在存储器映像图上预留空间。例如，b s s 段 是未初始化的，利用u s e c t 命令还可创建具名的未初始化段。 3 i 2 段的处理 一个段它包含哪些代码和数据，汇编语占有以下规定： 第7 页 国防科学技术人学研究生院学位论文 初始化段的命令( t e x t 、d a t a 和s e c t ) 建立一个新的段( 如果之前这个段不存在 的话) 的同时，也告诉汇编器后续的代码和数据属于这个段，直至出现下一个初始化段 的命令。 未初始化段的命令( b s s 和u s e g ) 仅作用于本行语句，为变量在相应的段预留空 间。 汇编器处理代码时需要为每个段维持单独的段程序计数器( s p c ) 。最初，每个段的 s p c 均为0 。当为某个段汇编一条指令或定义一个数据时，汇编器需要更新该段的s p c 。 遇到初始化段的命令，汇编器暂停当前段的汇编，转去汇编新的段。 3 1 3 重定位 汇编器认为每个段都从地址0 开始，然而实际上不可能，连接器需要为每个段重新 映射酋地址。标号标记段的某个位置，是可重定位的符号，标号的引用称为可重定位引 用。汇编器每当遇到一次可重定位引用，需要创建个重定位条目。连接时，当确定了 每个段的首地址，以及每个可重定位符号的地址后，连接器检查所有的可重定位条目， 依据条目类型更新相关的程序代码。c o f f 文件的每个段均有表格记录重定位条目。 3 1 4 外部符号 汇编语言允许定义和引用外部符号，相应地c o f f 文件有存放这些外部符号的表格。 连接时，连接器确定表格中包含的所有外部符号的地址。c l e f 命令定义一个可供其它模 块引用的全局符号，r e f 和g l o b a l 命令引用在其它模块定义的全局符号。 3 2j i - 编语言介绍 v l i wd s p 汇编语言的语句格式为： 1 a b e l ： 】 阳【 r e g i s t e r 】m n e m o n i c 【u n i ts p e c i f i e r o p e r a n dl i s t 【；c o m m e n t 方括号括起的域是可选的。“l a b e l ：】”是标号域；“是并行条，表示当前指令与前指 令并行执行，连续多个“旷连接的指令组成执行包；“l r e g i s t e r j ”是条件执行域，表示 当前指令是否执行依赖条件寄存器r e g i s t e r 的值：“u n i ts p e c i f i e r ”是功能单元域；“o p e r a n d l i s t ”是操作数域；“；c o m m e n t ”是注释域。当语句是汇编命令时，标号域、并行条、功 能单元域等都省略。 3 2 1 汇编命令 汇编命令主要有五类：定义段的、初始化常量的、执行对齐的、定义和引用外部符 号的和结束汇编的。定义段的命令创建段，若是初始化的段，将该段设置为当前段。初 始化常量的命令在当前段增加新的初始化数据。执行对齐的命令根据对齐要求调整当前 段的s p c 。定义和引用外部符号的命令用来定义和引用全局标号。结束汇编命令结束汇 编过程。 第8 页 国防科学技术人学研究生院学位论文 3 3 ；i - 编器结构设计 汇编包括的任务有：源语句行的词法和语法分析、汇编命令的解释执行、符号指令 的汇编、符号表维护和目标文件生成。由于源程序允许有向前引用，因此一次汇编可能 不能解决所有的引用。处理向前引用的方法不同可得到不同的汇编器结构h 1 【5 】( 6 l 。 v l l wd s p 汇编器采用两遍扫描的办法处理解决向前引用。第一遍汇编器仅确定标 号地址，而不产生机器代码。第一遍结束时，符号表应包含程序定义的所有标号。第二 遍汇编器重新扫描源程序，利用第一遍收集的标号信息产生机器代码。对于v l i wd s p ， 由于标号是附属于段的，所以段的信息也在第一遍收集。 与两遍扫描相关的问题是遍之间如何衔接。符号表和段表记录第一遍的处理结果， 对于经第一遍解析的源语句行，为了简化，我们没有设计一种中间语言表示，第二遍仍 从源文件读入语句行。汇编器的处理流程如图3 - l 所示，图中的实线表示数据流，虚线 表示控制流。 汇编 源程序 目标程序 图3 - 1v l i wd s p ；l - 编器的处理流程 3 3 1v l i wd s p 汇编器的结构 v l i wd s p 汇编器采用主从式结构，如图3 2 所示。源语句在汇编器内部采用内部 表示的形式。每次主程序从“词法和语法分析器”获取源文件的一个汇编命令或者执行 包的内部表示，接着调用“汇编命令处理”模块或“执行包处理”模块处理这个内部表 示。以第二遍为例，对于执行包，“执行包处理”模块先调用“指令汇编”模块产生机器 指令，然后调用“取指包合成”模块将执行包的机器代码加入至当前的取指包。若使用 第9 页 器 ，j、l 国防科学技术人学研究生院学侮论文 图3 2 v l | w d s p 汇编器的结构 了重定位引用，还需生成重定位条目。对于汇编命令，“汇编命令处理”模块执行该命令。 若是定义数据的命令则要将产生的数据送往“取指包合成”模块。如果还有重定位引用， 则要调用“重定位处理”模块。最后，当遇到汇编结束命令或者抵达文件尾时，主程序 调用“目标文件合成”模块生成最后的目标文件。图中的“内部表示l i b ”和“表达式计 算”是公用模块。 除了上述模块，汇编器需要维持段表、符号表、当前段和s p c 、遍指示等数据结构 的更新。第二遍扫描完源文件时，段表和符号表包含足够的信息，以便“目标文件合成 模块”合成目标文件。此外，汇编器还有反映指令特性和编码格式的数据结构，例如， 指令表、寄存器表、功能单元表、指令格式表、指令编码映射表等。借助这些数据结构 可以使得指令汇编过程与特