（计算机科学与技术专业论文）yhftdsp编译关键技术分析及实现.pdf

国防科学技术大学研究生院硕士学位论文 摘要 f t d s p 是国防科学技术大学自主研制的高性能数字信号处理器，其特有的体系结 构和指令集使已有的d s p 编译器无法满足其应用需求。而支持高级语言编程有助于降低面 向d s p 芯片的程序设计，有利于d s p 产品的推广。因此，针对t d s p 编译关键技术 的研究具有重要意义。 本文针对疆t d s p 的寄存器分配算法、指令级并行开发技术和编译器设计与实现方 法进行了研究。 本文主要贡献如下： 1 、针对世t d s p 的体系结构特点，基于最优染色算法，在g c c 中实现了d o c ( d s p o p t i m a lc o l o r i n g ，d s p 最优染色算法) 寄存器分配器。实验表明，该算法比g c c 原有乐 观染色算法产生的溢出变量更少，代码质量更高。 2 、本文对当前的主要开发指令级并行的编译技术进行了分析研究，并在g c c 中实现 了列表调度算法。提出前遍调度+ 寄存器分配+ 后遍调度的方案，保证有较高的i l p ，又不 会产生太多的变量溢出。 3 、最后，在分析g c c 编译器的实现原理的基础上，通过移植o c c ，实现了 f t d s p 编译器原型。实验证明，该d s p 编译器产生的汇编代码，经过汇编、链接生成的可执行文 件在y h f t d s p 上运行正确。 主题词：y h f t - d s p ，g c c 编译器移植，寄存器分配，指令级并行开发 第i 页 国防科学技术大学研究生院硕士学位论文 a b s t r a c t f t - d s pi sah i g h p e r f o r n l a n c ed i g i t a ls i g n a lp r o c e s s o rd e s i g n e db yn a t i o n a l u n i v e r s i t yo fd e f e n s et e c h n o l o g y n l ea r c h i t e c t u r ea n di n s t r u c t i o ns e ta l ed e s i g n e d 、析t l l i n t e l l e c t u a lp r o p e r t y ，w h i c hm a k e st h ee x i s t i n gc o m p i l e r su n s u i t a b l e b u tac o m p i l e rf o r y h f t - d s pi su r g e n tt os u p p o r tt h ew i d eu s eo fy h f t d s p i nt h i sp a p e r ，t h ek e yc o m p i l a t i o n t e c h n o l o g i e sf o ry h f t d s pa r es t u d i e da n dt h ey h f t d s pc o m p i l e ri sd e v e l o p e d t h em a i nc o n t r i b u t i o n sa r e 嬲f o l l o w s ： 1 b a s e do ny h f t - d s p sa r c h i t e c t u r e ，d o c ( d s po p t i m a lc o l o r i n g ) a l g o r i t h mi s p r o p o s e do nt h ef o u n d a t i o no fo p t i m a lc o l o r i n ga l g o r i t h m a n dt h ed o cr e g i s t e ra l l o c a t o ri s i m p l e m e n t e di ng c c e x p e r i m e n t ss h o wt h a tt h ea l l o c a t o ri sb e t t e rt h a no p t i m i s t i cc o l o r i n ga t s p i l l e dv a r i a b l er e d u c t i o na n dc o d eq u a l i t yi m p r o v e m e n t 2 n l es c h e m et h a ti n s t r u c t i o n sa r es c h e d u l e db e f o r ea n da f t e rr e g i s t e ra l l o c a t i o ni s p r o p o s e d i tc a l la s s u r em o r ei l p ，b u tl e s ss p i l l e dv a r i a b l e s a n dl i s ts c h e d u l i n ga l g o r i t h mi s i m p l e m e n t e df o rs c h e d u l e ri ng c c 3 b a s e do nt h es t u d yo fg c c c o m p i l e r sw o r k i n gp r i n c i p l e s g c ci sp o r t e dt oy h f t - d s p a r c h i t e c t u r e e x p e r i m e n t ss h o wt h a t ，t h ea s m c o d eg e n e r a t e db yt h ec o m p i l e rc a nb et r a n s l a t e d ， b ya s s e m b e ra n dl i n k e r , t oe x e c u t a b l ef i l ew h i c hc a n e x e c u t er i g h t l yo ny h f t - d s p k e yw o r d s ：y h f t - d s p ，g c cp o r t i n g ，r e g i s t e ra l l o c a t i o n ，i n s t r u c t i o n l e v e l - p a r a l l e l e x p o r a t i o n 第i i 页 国防科学技术大学研究生院硕士学位论文 表1 1 表1 2 表4 1 表4 2 表5 1 表5 2 表5 3 表5 4 表目录 f t d s p 部分指令集：8 功能单元和指令操作间的映射8 依赖边延迟的计算公式3 6 资源冲突表格3 8 词法分析器的主要功能及实现函数4 2 操作数类型及备选项51 操作数备选项5 5 i f 结构测试结果6 0 第1 v 页 国防科学技术大学研究生院硕士学位论文 图目录 图1 1 编译器总体结构2 图1 2d s p 编译器的目标代码生成6 图1 3y h f t - d s p 系统结构图7 图2 1 识别标识符的有限状态机1 2 图2 。2 语法树的生长过程1 4 图2 3 语法树的构造过程1 4 图2 4l r 分析器的工作过程1 5 图2 5 属性传递17 图2 6 运行时的内存分配1 9 图3 1c h a i t i n 寄存器分配算法的主要流程2 2 图3 2 具有2 - c o l o r i n g 的钻石图2 2 图3 3 b r i g g s 寄存器分配算法的主要流程2 3 图3 4 b r i g g s 算法处理寄存器对的加边方法2 3 图3 。5 冲突图的简化2 5 图3 6 先为顶点b 分配寄存器2 5 图3 7 后为顶点b 分配寄存器2 5 图3 8s p e cb e n c h m a r k 套件中溢出变量( 结点) 的函数比例2 9 图4 1 模调度示意图3 2 图4 2 分簇v l i w 结构示意图3 3 图4 3l i s t 调度过程示意图和算法3 5 图4 4 调度中资源冲突的解决3 8 图5 1g c c 编译系统的工作流程4 0 图5 2g c c 编译器c c l 的结构4 1 图5 3y h f t d s p 的堆栈框架布局4 9 图5 4 编译器测试原理5 7 第v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题目： ) 丛里! 尘婴缉受差链技苤金逝亟塞理 学位论文作者签名：j 歪兰塾一 日期：力p 笋年p 月7 日 学位论文版权使用授权书 本入完全了解国防科学技术大学有关保留使用学位论文的规定本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阕；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文题目：! 旦堡堕缟鋈差链拉盔金盘丞塞理 学位论文作者签名： 作者指导教师签名： 日期： 日期： 日 日 刁u 月 月 l 年 年 7 9 ，o 国防科学技术大学研究生院硕士学位论文 第一章绪论 1 1 课题背景及意义 随着信息技术的不断发展，数字信号处理器( d s p ，d i g i t a ls i g n a lp r o c e s s o r ) 已广泛 应用于航空航天、视频处理等领域。 f t d s p 系列是我们学校研发的数字信号处理芯片，。 为了推广应用，就必须具备配套的应用开发套件( 如t i 公司的c c s ，c o d ec o m p o s e rs t u d i o ) 来支持比较复杂和更加高级的应用；同时，由于产品生产周期缩短，芯片对高级语言编程 也提出了要求，这就要求我们不仅能设计并生产芯片，而且必须提供芯片相应的工具链。 由于当前的c p u 还只是基于二进制的指令执行机制，因此将源语言代码转化为可执行的二 进制文件然后再加载到c p u 执行也就成为了必然之路，而这些对于高级的语言( 如c 语 言) 来说，就必须通过编译、汇编、连接的过程，来得到最终可直接加载的二进制代码。 而编译器是整个过程中不可缺少的。 f t d s p 采用特定的体系结构和指令系统，已有的 d s p 编译器不能满足应用需求。基于此，本课题对特定d s p 芯片的编译器关键技术进行研 究以及实现，具有十分重要的意义。 1 2 编译技术 编译技术是计算机领域的关键技术之一。它随着计算机语言和体系结构的发展而发 展。编译器研究者们经过几十年的不懈努力，在编译理论、技术和实验上取得了丰富成果。 a h o 等【、m u c m c k 【2 】、a l l e n 和k e n n e d y 3 1 的著作描述了其中部分成果。如图1 1 所示， 编译器的工作过程一般划分为多个阶段，每个阶段把程序从一种表示形式转换为另一种形 式。 词法分析：扫描源程序字符串，根据语言的词法规则将源程序划分为一组单词。 语法分析：在词法分析基础上，根据语言的语法规则把单词串划分为各类语法单位。 语义分析：检查程序是否满足源语言要求的静态语义属性。 中间代码生成：根据语言的语义规则把各类语法单位翻译成中间代码，例如四元式、 三元式、间接三元式等。 代码优化：对中间代码进行等价变换，产生更高效的代码。目标代码生成把优化后的 中间代码转换成目标代码。目标代码可以是汇编指令代码、可重定向指令代码，或绝对指 令代码。 符号表管理：构造、查找、或更新源程序各种信息的表格。 出错处理：对编译过程中发现的错误进行管理，把有关出错信息报告给用户。 编译器的各阶段常划分为前端和后端两部分。前端主要依赖于源语言，大体和目标机 第1 页 国防科学技术大学研究生院硕士学位论文 器无关。前端一般包括词法分析、语法分析、语义分析、中间代码生成，以及一些代码优 化。后端依赖于目标机器和中间语言，和源语言无关。后端一般包括一些代码优化和目标 代码生成。编译的若干阶段的工作常组合成“遍”。 源程序 目标程序 图1 1 编译器总体结构 图1 1 中的代码优化阶段可分成控制流分析、数据流分析以及机器无关优化三部分。 控制流分析是数据流分析的基础，它们都是编译优化需要的工具。控制流分析构造程序的 基本块和控制流图，查找程序中的循环。分析程序中所有变量的定值和引用之间关系的工 作称为数据流分析。数据流分析有多种方法，如迭代数据流分析、区间分析、结构分析等。 机器无关优化作用于中间代码，其中部分重要优化列举如下。 第2 页 国防科学技术大学研究生院硕士学位论文 公共子表达式删除：删除公共予表达式的重复计算，并用保存的值来代替它们。 参数折叠：在编译时计算操作数是常数的表达式。 死代码删除：任何计算如果其结果从来不被使用，则删除此计算不影响源程序语义。 循环优化：又包括多种优化，例如，代码外提、强度消弱、删除归纳变量等。 目标代码生成器主要由三部分构成：代码选择器、寄存器分配器、指令调度器。 代码选择确定使用哪些目标机器指令实现程序的中间表示，使得总体开销最小。树模 式匹配和动态规划技术常被用来自动生成代码选择器。 寄存器分配确定如何充分利用寄存器，使得目标代码中访问存储单元的次数最少。基 于冲突图的图染色算法是寄存器分配的常用方法。 指令调度确定在程序运行时各指令在哪个机器周期开始执行，在保持程序语义条件下 重排指令顺序以充分挖掘处理器的指令级并行( i l p ，i n s t r u c t i o nl e v e l p a r a l l e l i s m ) ，使得 程序运行时间最短。列表调度( l i s ts c h e d u l i n g ) 是常用的指令调度技术。 另一类重要的编译技术是针对向量巨型计算机、多处理器计算机的向量化、并行化编 译技术，例如挖掘f o r t r a n 程序中的并行性，尤其是循环级并行。依赖性理论，尤其是循环 依赖是这类优化的重要基础。并行编译技术的部分内容包括循环规范化、循环交换、i f 转 换等控制流处理技术、别名分析等过程间分析和优化。a l l e n 和k e n n e d y 3 j 的著作详细描述 了并行编译的理论和技术。b a c o n 等1 4 j 给出了有关综述。 1 3d s p 编译技术 d s p 针对特定应用需求，采用了不规则的体系结构，相应的d s p 编译技术也具有自己 的特点。本节首先分析d s p 体系结构特点，然后分析d s p 编译技术的特点。 1 3 1d s p 的发展及其体系结构特点 编译技术总是和体系结构相联系的。本小节介绍数字信号处理器的发展，并分析了主 流d s p 的体系结构特点。 1 3 1 1d s p 的发展 d s p 的发展一直伴随着应用技术的发展，由简单的数字信号处理要求，如数字滤波、 回声抵消等，到复杂的数字处理，如自适应滤波、v i t e r b i 解码，现在发展到面向多媒体应 用和媒体网关的数字处理，如音视频流的编解码、语音频带的m o d e m 、x d s l 线路调制、 软件无线电等。可以预见，当特定应用的整体要求复杂到一定程度时，不同应用间的适应 性要求将会推动d s p 的发展，使d s p 的速度越来越快、带宽越来越大，与通用的微处理 器的主要技术也越来越接近。 与此相对应，d s p 处理器的发展经历了传统d s p 处理器、增强型d s p 处理器和高性 第3 页 国防科学技术大学研究生院硕士学位论文 能d s p 处理器等三个阶段1 5 j i 6 l 。 传统型和增强型d s p 使用特殊的硬件和复杂而不规则的指令，一条指令包含多个操 作。这使得难以对其进行编程，也难以为其开发高效编译器。为了获得更高的性能，并且 有利于相应编译器的开发与优化，新一代的高性能d s p 处理器都采用了多指令流出的体系 结构。与传统和增强型d s p 相比，多流出d s p 处理器使用简单指令集，一条指令只完成 一个操作。这种处理器将简单指令并行地发射出去，并同时执行，从而大幅提高了i l p 。 由于使用简单指令集简化了译码和执行操作，相对于传统和增强型d s p 处理器，多流出 d s p 可以采用更高的时钟频率。 多流出体系结构有超标量( s u p e r s c a l a r ) 和超长指令字( v l i w ，v e r yl o n gi n s t r u c t i o n w o r d ) 两种。在v l i w 结构中，指令的并行化排列在程序编译时进行，在指令执行阶段指 令的前后排列顺序不变。在s u p e r s c a l a r 处理器中，在执行的过程中由专门的硬件根据数据 相关和资源相关等决定指令的并行执行，这种方法可以提供更高的指令执行并行度，但提 高了硬件的复杂度；并且在超标量处理器中，指令的动态调度会使得同一段程序在不同的 情况下执行的时间不同，影响程序员对程序执行时间的预测。因此在高性能d s p 处理器极 少使用超标量结构，而往往采用v l i w 体系结构。目前，主流的d s p 厂商都推出了自己的 v l i w 结构的高性能d s p ，如t i 的t m s 3 2 0 c 6 x 系y u t n 、a d 的t i g e r s h a r c 系列【引、以 及m o t o r o l a 与l u c e n t 联合推出的s t a r c o r e t 9 j 系列等。 1 3 1 2d s p 的体系结构特点 通过比较上述各厂家的v l i w 体系结构的d s p ( 以下简称v l i wd s p ) ，可以发现它 们的一些共同特点： 1 、v l i wd s p 大都采用类r i s c 指令集，使用通用寄存器文件，结构规整，具有潜在 的易编程性，使得v l i w 处理器的编译优化更容易完成。 2 、含有大量的数据通路和多个可以并行的运算部件，由于数据相关和资源相关性通 过编译器进行处理，因此硬件本身具有较简单的控制逻辑，如中断处理等。 3 、支持谓词执行( p r e d i c a t e de x e c u t i o n ) 。每条指令都有一个谓词决定其执行与否： 谓词为真的指令正常执行；谓词为假的指令变成空操作( n o p ) 。 4 、分簇结构( c l u s t e r e d ) 。为了降低寄存器文件的复杂度，提升频率，许多v l i wd s p 采用了分簇结构【7 】【8 】【l o 】，即将寄存器文件分成若干组，每组寄存器对应若干计算单元。 5 、为了支持多个并行的指令同时执行，v l i wd s p 处理器都有较大的指令译码器、总 线、寄存器和存储器带宽。 6 、广泛采用片上存储器。由于d s p 面向的是数据密集型应用，因此存储器访问速度 对处理器的性能影响很大。v l i wd s p 中往往都有片上的程序和数据存储器，提供高带宽 和快速的取指、访存操作，解决c p u 与外部存储器速度不匹配的问题。 第4 页 国防科学技术大学研究生院硕士学位论文 7 、支持s i m d 指令。v l i wd s p 中的s i m d ( 单指令多数据，s i n g l ei n s t r u c t i o nm u l t i p l e d a t a ) 指令的实现方式是以寄存器为单位的，寄存器可以被划分成若干个较小的相互独立 的单元( 子寄存器) ，这样整个寄存器就变成了一个向量，s i m d 指令就可以对向量中的 所有单元进行相同的运算。使用s 1 m d 指令可以极大地提高d s p 处理多媒体计算的性能。 8 、为了降低硬件的复杂度，v l i wd s p 一般不存在硬件上的调度机制、冲突检测机制， 也不含有通用v l i w 处理器中常见的对前瞻执行( s p e c u l a t e de x e c u t i o n ) 机制的支持。 1 3 2d s p 编译器的作用 d s p 应用对于时间、空间的要求非常严格，传统上为了实现高效的处理，通常采用手 工编写汇编代码的形式来开发应用程序。和高级编程语言相比，汇编语言有如下缺点： 1 、语言晦涩，难以掌握。每当开发人员为新的处理器平台开发应用软件，就必须学 习该处理器的汇编语言，这些汇编语言形式多样，功能各异，难以掌握，增加了软件的开 发难度。 2 、开发周期长，成本巨大。汇编代码的代码量往往是对应高级语言代码量的数倍， 调试困难，大大增加了开发的周期和耗费的人力。 3 、不具有可移植性，平台转移工作量大。当应用程序转移到新的开发平台的时候， 开发人员必须重新编写软件代码，而高级语言就不存在这样的问题，只要用对应平台的编 译器重新编译高级语言，生成目标代码即可。 由于汇编语言开发周期长、代码可重用性差，严重影响了产品的上市时间，并难以降 低成本，已经不适合开发周期越来越短的现实，使用高级语言编写代码，通过高效的编译 器将之转换为目标代码成为主流选择。c 语言是效率最高的通用高级编程语言，所以目前 绝大多数d s p 支持的高级语言编译器都是c 编译器。 v l i wd s p 芯片采用静态指令调度技术，它的流水线是非保护的，没有用于防止资源 冲突和隐藏流水线延时的硬件互锁机制，指令是否可以并行执行以及指令的执行顺序，完 全依赖于编译器对程序中指令依赖关系的静态分析。因此，v l i wd s p 的高性能是否能够 发挥出来，完全取决于编译器效率的高低，最大程度挖掘i l p 的能力。 d s p 作为一种专用处理器，通常将某个调试优化完成的程序载入后长久的运行，即有 “r o p o ( r u no n ep r o g r a mo n l y ) 特性，即使花费较多时间对目标程序进行优化也是 值得的。因此相对通用编译器而言，些花费时间较大优化算法就可以用在d s p 编译器中。 并且目前d s p 采用的是交叉编译的方式，让计算能力强的主机花费大量时间，产生一个优 化的目标d s p 程序是可行的。 1 3 3d s p 编译器的特点 编译器是将高级语言翻译成低级目标语言的软件，是计算机领域最基础、最重要的系 统软件。编译器应用中桌面系统已经有几十年的历史了，但是在d s p 处理器系统中的应用 第5 页 国防科学技术大学研究生院硕士学位论文 还很少。本节介绍d s p 编译器开发的特点。 l 、支持d s p 专用算法和体系结构 d s p 采用了与通用处理器不相同的体系结构，具有许多独有的特点。例如，d s p 体系 结构针对数字信号处理中最常用运算类型的特点，分离了数据流和指令流，使哈佛结构成 为d s p 的主流结构：d s p 大都采用了具有“乘法累加器 的运算内核和流水线结构，对常 用纯数值运算，可达到单指令周期完成一次基本运算，与早期通用处理器完成一次乘法运 算需要几十个指令周期相比，运算效率大大提高。d s p 编译器必须在代码生成过程中，充 分利用这些硬件特点，生成为硬件优化的目标代码。传统的编译器技术越来越难以适应d s p 的苛刻要求，必须发展出d s p 编译器专用的代码生成算法。 2 、生成高效的目标代码 d s p 应用程序通常都是实时程序，一个实时软件需要满足一定的时间约束条件。为了 提高数据计算速度和运行效率，d s p 一般都带有多个特殊的功能单元，传统的编译技术很 难对这种体系结构生成高效的目标代码f l l 】f 1 2 】。d s p 编译器必须能够充分利用这些功能单 元，提高生成代码的运行效率。在桌面系统中，存储器的价格非常便宜，编译器很少考虑 目标代码空间尺寸的问题，代码生成、寄存器分配和指令调度是分阶段完成的，而d s p 应 用程序通常都存储在片上存储器，片上存储器价格昂贵，存储容量非常有限，这就要求d s p 编译器必须生成尽可能紧凑的目标代码，减少程序的存储空间需求。因此，在目标代码生 成阶段，编译器要同时考虑d s p 寄存器分配和指令调度，才能产生优化的目标代码。如图 1 2 所示。 图1 2d s p 编译器的目标代码生成 1 4y h f t - d s p 的体系结构及指令集 y h f t d s p 芯片是一款高性能的3 2 位定点d s p ，采用了有分簇的v l i w 结构，最多 可以同时发射8 条3 2 位并行指令。主要应用于图形、图像和数字信号处理等领域。结构 上，y i t d s p 的数据通路由两个簇a 和b 组成，每个簇包括一个寄存器文件和四个可并 第6 页 国防科学技术大学研究生院硕士学位论文 行工作的功能单元( a l ，b c ，m u 和l d ) ，各簇功能单元一般只访问本簇内的寄存器 文件，但a l 、b c 和m u 也可以通过交叉通路访问另一簇的寄存器文件。寄存器文件a 和b 中的部分寄存器还可以充当条件寄存器。 1 4 1 体系结构特点 y h f t d s p 体系结构采用v l i w 结构，单指令字长3 2 位，8 条指令组成一个指令包， 总字长2 5 6 位，芯片最高时钟频率3 0 0 m h z 。y h f t d s p 系统结构如图1 3 所示。 i 定时器1ii 中断选择子l i l pc 础e 一 定时器0自动配置模块 -l i 取指单元 一 7 l 外部存储接1 2 1 4 - - 8 - - - - 4 1r 广 i f - 4 ) - 一( e m i f ) 一j r a 指令派发单元 b 田田 寄 _ l 2 寄 _ n 上 存多通道缓冲串存 一 指令译码单元i 器 _ 4 - 器 王互 c a c h e e d m a e i ( m c b s p0 ) 文 _ c匕 一- 文 控 件 一 控制寄存器 件 r 中断控制 广 制 多通道缓冲串 一- _ 器 _ 4 - 一 n c i ( m c b s p1 ) t tc p u 核tt 1 l1 l 上 1 l 主机接1 2 1 l l dc a c h e 卜 _ 4 - ( h p i ) 图1 3y h f t - d s p 系统结构图 体系结构上的主要特点有： 1 、算术单元，包括硬件乘法器和多功能单元，为了提高乘法速度，在唧t d s p 内 部设置硬件乘法器来完成乘法操作。 2 、总线结构。断t d s p 采用独立程序总线和数据总线的哈佛总线结构，大大提高 了程序执行的效率。 3 、专用寻址单元。y h f t d s p 有支持地址计算的算术单元地址产生器。它还支 持位寻址和循环寻址。 4 、片内存储器。y h f t d s p 内部集成有1 7 m b 的程序r a m 和数据r a m 。 5 、流水处理。这是提高y h f t d s p 上程序执行效率的主要手段之一，在y h f t - d s p 内部，每条指令的执行分为取指、解码、执行等若干阶段，每个阶段称为一级流水。流水 技术使若干条指令的不同执行阶段并行化，因而能够提高程序的执行速度。 y h f t d s p 属于类r i s c 结构，从而使得它的c 编译器有更高的效率，因此也可以称 其为面向c 语言结构的d s p ，这使得其在大多数的应用中可以采用c 语言编写程序，从而 可以充分利用大量的c 描述的算法程序，并获得远胜于传统的d s p 程序的可维护性、可 移植性、可复用性，缩短开发周期。 第7 页 国防科学技术大学研究生院硕士学位论文 1 4 2 指令系统及指令集 f t d s p 有丰富的指令，一些比较常用和重要的指令如表1 1 所示，包括指令格式 及其所执行的操作。 表1 1y l 口t d s p 部分指令集 指令名 指令格式执行操作 a b s d p s r c ，d s t6 4 位双精度数取绝对值 a b s s p s r c ，d s t3 2 位单精度数取绝对值 a d d a d s r c l ，s r c 2 ，d s t3 2 位单精度数线性或环形加法( 据a m r 判断) a d d d p s r c l ，s r c 2 ，d s t 6 4 位双精度数加法 a d d s p s r c l ，s r c 2 ，d s t 3 2 位单精度数加法 c m p e q d ps r c l ，s r c 2 ，d s t6 4 位双精度数比较，相等d s t 置1 否则为0 c m p e q s ps r c l ，s r c 2 ，d s t 3 2 位单精度数比较，相等d s t 置1 否则为0 c 口g t d p s r c l ，s r c 2 ，d s t 6 4 位双精度数比较，s r c l s r c 2 则d s t 置1 否则为0 c m p g t s p s r c l ，s r c 2 ，d s t 3 2 位单精度数比较，s r c l s r c 2 则d s t 置1 否则为0 c m 口l t d p s r c l ，s r c 2 ，d s t 6 4 位双精度数比较，s r c l 双精度 3 2 位逻辑操作整型单精度 3 2 位算术操作 3 2 4 0 位移位和3 2 位位操作 比较倒数和倒数平方根操作 3 2 位逻辑操作 b c 单元绝对值操作 转移 单精度 双精度 常数产生 寄存器与控制寄存器传递( 仅s 2 ) m u 单元 1 61 6 乘法操作 3 23 2 乘法操作；浮点乘法操作 3 2 位加、减、线性循环寻址计算 l s 单元5 位常数偏移量存取、1 5 位常数偏移量5 位常数偏移量双字读取 存取( 仅d 2 ) 第8 页 国防科学技术大学研究生院硕士学位论文 1 5 本文的研究内容及文章结构 1 5 1 研究内容 本文的研究内容包括： l 、分析了编译器实现的关键技术及d s p 编译器的特点，为下一步研究d s p 关键编译 技术做充分的准备； 2 、针对影响代码质量的寄存器分配问题，分析研究了传统的图染色寄存器分配算法 及其改进算法，在此基础上提出并实现了基于最优图染色算法的寄存器分配算法； 3 、研究分析了采用v l i w 体系结构的d s p 的指令级并行开发技术以及资源冲突解决 策略，并采用前遍调度+ 寄存器分配+ 后遍调度的方案在g c c 中实现了列表调度算法，采 用二维资源表解决资源冲突问题，保证了程序运行的正确性： 4 、剖析了g c c 编译器的工作原理，并基于g c c 实现了皿t d s p 编译器原型。 5 、利用黑盒测试方法对产生的编译器进行正确性测试； 1 5 2 论文结构 本文共六章： 第一章绪论。介绍了课题的研究背景、研究意义、研究内容，为后面的章节奠定基 础： 第二章编译器工作流程分析。对包括词法分析、语法分析、中间代码生成、运行时 环境管理、目标代码生成等在内的编译器流程进行分析，明确工作重点； 第三章基于最优染色算法的寄存器分配算法。对图染色寄存器分配算法及其改进算 法进行了深入研究，并在此基础上提出基于最优染色算法的寄存器分配算法，实验证明该 算法减少了变量溢出，提高了代码质量； 第四章指令级并行开发和资源冲突解决策略分析。分析v l i wd s p 中的指令级开发 技术以及资源冲突解决方法，并在g - c c 中实现列表调度算法； 第五章面向y h f t d s p 的g c c 编译器开发。在剖析g c c 编译器c e l 的的基础上， 将g c c 移植到y h f t d s p 体系结构上，实现了初步可用的c 编译器，并利用黑盒测试方 法对其进行相关测试； 第六章结束语。对所做的工作进行了总结，并对未来的研究工作进行了展望。 国防科学技术大学研究生院硕士学位论文 第二章编译器工作过程 编译器各模块的关键技术是相关技术的基础。为了明确工作重点，本章研究分析编译 器的工作流程，包括：词法分析、语法分析、中间代码生成、运行时环境以及目标代码生 成，见图1 1 。 2 1 语言与文法 表述- 1 7 语言就是描述这种语言所包含的句子1 1 6 1 。如果这种语言只含有有限句子，只 要把所有的句子列出来，就能完整地描述该语言。但一种语言很可能包含有无穷句子，从 而无法穷举出所有的句子，但是可以构造一些规则来定义句子的组成结构，从而得以表述 - - 1 7 语言，这样的语言描述被称为文法。描述一种语言的文法包含四个要裂1 7 1 ： 1 、终结符号集。终结符表示构成语言的最基本单位，例如在汉语中，最基本的单位 是汉字、数字和标点符号；在英语中，最基本的单位是字母、数字和标点符号；对于一门 编程语言，最基本的单位是所有合法的标识符，在文法上都属于终结符号。终结符号集用 v t 表示。 2 、非终结符号集。非终结符表示一门语言中的语法实体或变量，它是由该语言终结 符集合中的终结符按照某些规则组成的有穷序列。例如汉语中的词语、句子；英语中的单 词等都属于其所属语言的非终结符。非终结符号集用v n 来表示。终结符号集和非终结符 号集都统称符号集，用v 来表示，即v = v t u v n 。 3 、规则集。规则集描述了语言文法中非终结符号的产生规则，根据给定规则就能描 述- 1 7 语言中的所有合法句子。规则一般采用产生式的形式来表示，是形如a b 的有序 对，其中0 【是符号集v 的正闭包旷中的一个符号，b 则是v 中的一个符号。0 【称为规则左 部，b 称为规则右部，规则集用p 来表示，习惯上在产生式中用小写字母表示终结符号， 大写字母表示非终结符号。如果a 哼p 是文法的规则，丫和6 是v + 中的任意符号，如有符 号串v ，w 满足v - 吖a 8 ，w l p 6 ，则说w 是v 的直接推导，或者说v 是w 的直接规约，可 以记作v - w 。如果存在直接推导序列：v = 、o - w 1 - = w i l _ w ( n 0 ) ，则称v 推导出w ， 或者称w 规约到v 。如果在推导的任何一步v = w 中，始终都是对v 中的最左或最右非终 结符进行替换，则称这种推导为最左或最右推导，其中最右推导被称为规范推导。 4 、开始符号s 。开始符号s 是一个非终结符号，如果符号串x 是由文法开始符s 推导 出来且仅含有终结符号的符号串，则称x 为文法的句子。文法句子x 的集合就是对该文法 所表示语言的表述。s 至少要在文法的一条规则中作为左部出现。 对于- n 语言的文法g ，可形式化定义为四元组( v n ，v t ，p ，s ) 。根据施于文法规 则的限制不同，可以把文法分为0 到3 型四类文法。 第1 0 页 国防科学技术大学研究生院硕士学位论文 _ - - t - - t - - t - - v - - v - - w - - v - - t - - w m v m 0 型文法和1 型文法是上下文相关文法，它们的产生式规则表现为：a l a a 2 - - a l b a 2 ， 其中a 1 、a 2 和b ( v ，uv n ) 。，a v n 。因为只有a 出现在a 1 和a 2 的上下文中，才允 许用b 取代a ，所以被称为上下文相关文法。 2 型文法和3 型文法都是上下文无关文法。2 型文法的每一个产生式( 1 - - 争b 满足：a v s ，p ( v t u v n ) 。3 型文法的产生式形如a 寸a b 或a a ，a 和b v n ，a e v t 。可 以看出：在2 型和3 型文法中用另个字符串取代一个非终结符时，与该非终结符所在的 上下文无关；同时，3 型文法要求每个产生式的右部第一个符号一定要是终结符号，这个 特点可以用来对给定的符号串进行规约分析，3 型文法也称为正规文法，它所定义的语言 称为正规语言。 句型与句子：设g 是一文法，s 是文法的开始符号，如果符号串x 是从开始符号s 推 导出来的，则称x 是文法g 的句型；若x 仅由终结符号组成，则称x 为g 的句子。 短语与句柄：若a b c 是文法g 的一个句型，如果由文法开始符s 可推导出句型a a c ， 且由非终结符a 可以推导出b ，则称b 是句型a b c 相对于非终结符a 的短语。特别，如果 j 怜b ，则称b 是句型a b c 相对于规则a 专b 的直接短语或简单短语。一个句型的最左直接 短语称为该句型的句柄。 2 2 词法分析 2 2 1 词法与正规式 词法分析是编译的第一个阶段，它的主要任务是从左到右逐个字符地对源程序进行扫 描，产生一个单词序列用于语法分析【l 引。词法分析器将源程序以字符流形式作为输入，根 据规则产生对于给定编程语言合法的单词( w o r d ) 或符号流( t o k e ns t r e a m ) 作为输出。 一门语言单词的构成法称为词法，大多数程序设计语言的词法都能用正规文法来描 述，正规文法描述的是v t 上的正规集。对任意一个正规文法，存在着一个定义同- - f - 语 言的正规式：反之亦然。正规式又称为正则表达式，是用来表示正规集的工具，可以用它 方便的描述单词符号。 正则表达式定义递归定义如下【1 7 】： 设字母表为，辅助字母表= ，f ，i ，( ，) ) l 、和占都是上的正规式，它们所表示的正规集分别为和 s ) ； 2 、v a e ，如果a 是上的一个正规式，它所表示的正规集为 a ) ； 3 、假定e l 和e 2 都是上的正规式，它们所表示的正规集分别为l e 1 ) 和l e 2 ) ，那 么e l ，e l l e 2 ，e l e 2 和e l 也都是正规式，他们所表示的正规集分为l ( e 1 ) ，l ( e 1 ) ul ( e 2 ) ， l ( e 1 ) l ( e 2 ) 和( l ( e 1 ) ) ； 4 、有限次使用上述三步骤得到的表达式才是上的正规式，仅由这些正规式表示的 第1 1 页 国防科学技术大学研究生院硕士学位论文 字集才是上的正规集。 例如，在一门程序设计语言中，规定标识符是由字母开头，后面可接零到多个字母或 数字的组合，首先给出定义标识符的正规文法的产生式： l e t t e r - - ( a l b l c l d l e l t q g l h l il il k l l l m l n l o l p l q l r l s l t l u l v l w l x l y l z ) d i g i t a l 寸( 0 1 11 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 ) b 寸占id i g i t a lbl e t t e rb a _ 占ld i g i t a lbl e t t e rb i d e n t i f i e r - - l e t t e ra 然后可以利用上述的规则构造出和正规文法向等价的正规式，下面就是用来描述标识 符的正规式： ( a l b l e l iz ) ( ( a l b l ej i z ) l ( 0 111 2 i i9 ) ) 2 2 2 有限自动机与词法程序 有限自动机是具有离散输入输出系统的数学模型。它具有有限的内部状态，系统可以 根据当前所处的状态和面临的输入字符决定系统的后继行为，其当前状态概括了过去输入 处理的信息，它可以被看做是一种识别装置。对于上面例子中的标识符，我们也可以用图 2 1 中的有限状态机来识别其是否是合法的标识符。 图2 1 识别标识符的有限状态机 图中每一个圆圈表示一个状态，s 0 是初始状态，表示状态机还没有任何输入；每一条 弧线表示状态之间的转换，称为状态转换函数；弧上的标识表示当状态机处于某种状态时， 遇到该标识的输入，状