（计算机科学与技术专业论文）vxworks操作系统的重新编译和优化研究与实现.pdf

国防科学技术大学研究生院学位论文 摘要 v x w o r k s 嵌入式操作系统是美国风河公司推出的款嵌入式操作系统，具有 高可靠性和强实时性等特点。该嵌入式操作系统采用了多任务机制、微内核，支 持网络、文件系统、i o 管理、p o s i x 标准扩展、c + + 标准和其他标准。v x w o r k s 嵌入式操作系统的编译器使用的是开源的g c c 编译器。该编译器是可移植的优化 编译器，能够生成高质量的目标代码。 本文通过对v x w o r k s 嵌入式操作系统的编译过程进行详细的分析和研究，明 确了编译的过程中环境变量的作用和编译器的使用。在此基础上通过修改相应的 环境变量和改写相应的批处理文件来使用改进后的编译器编译v x w o r k s 。 在改进后的编译器上，设计并实现了一种新的函数内联机制，改变编译器对 于程序中的内联函数的操作，减小了生成的系统镜像的大小，并对各种宏定义值 下的系统镜像大小进行了测试。循环变换是一种在计算密集型应用中广泛使用的 优化技术。在做循环变换之前，为了保证程序语义的正确性需要先进行数据依赖 性的分析。g c c 中原有的数据依赖性分析机制对于非线性数组分析能力较弱，对 于多索引下标数组的分析也存在很大的不足。本文设计并实现了一种新的增强型 递归链依赖分析算法，有效的提高了对循环间多索引数据依赖关系分析的能力， 为循环变换的开展提供了更好的前提条件。 主题词：g c c ，v x w o r k s ，函数内联，递归链 国防科学技术大学研究生院学位论文 a b s t r a c t v x w o r k si sa l le m b e d d e do p e r a t i n gs y s t e mm a d eb yw i n d r i v e rc o r p o r a t i o n ，t h e c h a r a c t e r i s t i co fw h i c hi sh i g hr e l i a b l ea n ds t r o n gr e a l t i m e v x w o r k sm a k e su s eo f m u l t i t a s km e c h a n i s m ，m i c r o - k e r n e l ，p r o v i d e st h es u p p o r to fn e t w o r k ，f i l es y s t e m ，i o s y s t e m ，e x p a n d i n gs t a n d a r do fp o s i x ，t h es t a n d a r do fc + + a n do t h e rs t a n d a r d s t h e c o m p i l e rf o rv x w o r k si sg c c ，w h i c hi sa no p e ns o u r c ec o m p i l e r t h i sc o m p i l e ri sa t r a n s p l a n t a b l ea n do p t i m i z e da n dc a nc r e a t eh i g h q u a l i t yo b j e c tc o d e t h i sp a p e rh a sad e t a i l e da n a l y s i sa n di n v e s t i g a t i o nt ot h ec o m p i l i n gp r o c e s so f v x w o r k s ，a tl a s tf o u n dt h ew a yo fu s i n gc o m p i l e ra n dt h ea c t i o no fe n v i r o n m e n t v a r i a b l ei nt h ep r o c e s s a f t e ra l lt h ew o r k ，w et r yt om o d i f yt h ee n v i r o n m e n tv a r i a b l e a n dt h e b a tf i l et o c o m p i l yt h ev x w o r k sw i t ht h en e wc o m p i l e r , w h i c hh a sb e e n i m p r o v e d i nt h en e wc o m p i l e r ，t h i sp a p e rh a sd e s i g n e da n di m p l e m e n t e dan e wf u n c t i o n i n l i n em e c h a n i s mt oc h a n g et h ec o m p i l e rh a n d l i n gt h ei n l i n ef u n c t i o ni nt h ep r o g r a m b yt h i sm e a n s ，h e r eh a sr e d u c e dt h es i z eo ft h es y s t e mi m a g e ，a n dt e s tt h es i z eo fs y s t e m i m a g ei nu s i n go fd i f f e r e n tm a c r od e f i n i t i o n c i r c u l a t i n gt r a n s f o r m a t i o ni su s e d f r e q u e n c yi nt h ea p p l i c a t i o no fd e n s ec o m p u t i n g f o rg u a r a n t i n gt h ec o r r e c to fs e m a n t i c ， t h ea n a l y s i so ft h ed a t ad e p e n d e n c eb e t w e e nl o o p sm u s tb e e nc o m p l e t e db e f o r e t h e o r i g i n a la n a l y s i so fd a t ad e p e n d e n c eb e t w e e nl o o p si ng c c i sw e a kf o rn o n l i n ea r r a y a n dm o r es u b s c r i p ti n d e x e s t h i sp a p e rh a sd e s i g n e da n di m p l e m e n t e da ne n h a n c e c h a i n so fr e c u r r e n c ea r i t h m e t i c ，w ec o u l de f f e c t i v e l yr a i s et h ec a p a b i l i t yo fa n a l y s i n g d a t ad e p e n d e n c ei nt h en o n l i n ea r r a y ，w h i c hh a sm a n yi n d e x e s ，a n da l s oc o u l dp r o v i d e b e t t e rp r i o rc o n d i t i o nf o rc i r c u l a t i n gt r a n s f o r m a t i o n k e yw o r d s ：g c c ，v x w o r k s ，f u n c t i o ni n l i n e ，c h a i n so fr e c u r r e n c e 国防科学技术大学研究生院学位论文 表目录 表1 1 常用的优化技术8 表2 1 调整自动内联函数大小后的镜像2 2 表2 2 限制代码增长后的代码大小2 2 表3 1 递归链计算规则2 8 表3 2 分解后的递归式3 0 表3 3 被增强型递归链测试算法检测出的依赖关系3 3 表3 4 三种测试算法的时间消耗3 3 表4 1 文件u s r d e p e n d c 中直接通过宏定义调用的源文件列表4 4 表4 2 文件u s r d e p e n d c 打包的宏定义选项。4 5 表4 3 文件u s r d e p e n d c 通过关系式来定义的宏定义4 6 表4 4 文件u s r e x t r a c 中对文件的选择列表4 7 表4 5 文件u s r e x t r a c 中初始化操作的选择列表4 8 表4 6 文件u s r e x t r a c 中判断操作的选择列表。4 9 表4 7g c c 体系结构选项5 l 国防科学技术大学研究生院学位论文 图目录 图1 1v x w o r k 嵌入式操作系统的组成2 图1 2v x w o r k 嵌入式操作系统的网络结构2 图1 3i o 系统结构3 图1 4g c c 的整体结构图5 图1 5g c c 目标代码的生成6 图1 6 编译器的优化层次7 图1 7g c c 的优化策略。8 图2 1 引导镜像的加载1 4 图2 2 系统镜像的加载。1 4 图2 3 最大内存消耗对比图1 5 图2 4 控制代码大小1 7 图2 5 提高程序性能18 图2 6 对代码增长体积的控制18 图2 7 内联函数间的关系图1 9 图3 1 现代计算机的存储系统结构2 4 图3 2 三种依赖关系分析函数间的关系2 6 图3 3 依赖分析的函数调用图j 3 1 图4 1v x w o r k s 系统镜像的编译过程1 3 6 图4 2v x w o r k s 系统镜像的编译过程2 3 7 图4 3v x w o r k s 系统镜像的编译过程3 3 7 图4 4v x w o r k s 系统镜像的编译过程4 3 8 图4 5 编译v x w o r k s 系统镜像时的m a k e f i l e 文件调用关系图3 9 图4 6 编译工具的文件调用关系j 4 0 图4 7 依赖性分析的文件路径4 3 图4 8 设置编译需要的环境变量5 2 图4 9 在m s d o s 中使用g c c 重新编译v x w o r k s 5 2 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目：! 茎里q ! 垒兰握佳丕统鲍重堑缉圣塑选丝堑窒皇塞理 学位论文作者签名：垄臼盘翌! 旦 日期：留年2 月22 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文作者签名： 作者指导教师签名： 日期： 夕多年，2 月? z 日 日期：2 p 髟年f1 + 月2 3 日 国防科学技术大学研究生院学位论文 第一章引言 在过去的几十年里，i t 产业迅猛发展，嵌入式系统的应用己经深入到生产和 生活的各个方面。上世纪七十年代晚期后陆续出现了专门为嵌入式系统开发的嵌 入式操作系统，比如v x w o r k s 、u c l i n u x 、w i n d o w sc e 等等。由于嵌入式系统的 r a m 普遍较小，增加了嵌入式系统开发的难度，为了方便开发往往采用交叉编译 器。 由于g c c ( g n uc o m p i l e rc o l l e c t ) 具备高度的可移植性、生成的代码质量高， 非常适合于为嵌入式系统提供编译支持。因此被广泛应用在嵌入式开发领域。美 国风河公司的经典嵌入式操作系统v x w o r k s 就是采用的该编译器。 另外，因为嵌入式系统对应用程序的执行速度，可靠性和代码大小要求更高， 要求编译器能够尽量对代码进行优化。所以，通过对g c c 编译器进行深入分析与 研究后，实现一些特定的编译优化具有非常重要的意义。 1 1 嵌入式操作系统v x w o r k s 概述 v x w o r k s 嵌入式操作系统是美国风河公司推出的一个实时嵌入式操作系统。 风河公司在实时嵌入式操作系统领域是全世界公认的最具有实力的公司。风河公 司开发的v x w o r k s 强实时嵌入式操作系统是一个运行在目标机上的高性能、可裁 减的嵌入式操作系统。该嵌入式操作系统采用了任务机制、微内核，支持网络、 文件系统、i o 管理、p o s i x 标准扩展、c + + 标准和其他标准支持【。 v x w o r k s 以其高可靠性和强实时性被广泛地应用在通信、军事、航空、航天 等高精尖技术领域及实时性要求极高的领域中，如卫星通讯、军事演习、弹道制 导、飞机导航等。 1 1 1v x w o r k s 嵌入式操作系统的基本组成 v x w o r k s 嵌入式操作系统的基本组成部件主要有以下五个部分： 板级支持包b s p 微内核 网络系统 文件系统 i o 系统 板级支持包b s p 板级支持包( b o a r ds u p p o r tp a c k a g e ) 为各种开发板的硬件功能提供了统一的 软件接口，这些接口包括硬件初始化、中断的生成和处理、硬件时钟和计时器管 理、总线内存地址映射、内存分配等。每个板级支持包提供了一个r o m 启动( b o o t 国防科学技术大学研究生院学位论文 r o m ) 或其它启动机制。 图1 1v x w o r k 嵌入式操作系统的组成 微内核 v x w o r k s 嵌入式操作系统的核心，也被称作w i n d ，包括多任务调度( 采用优 先级抢占方式) 、任务间的同步、任务间通信机制、中断处理，看门狗和内存管理 机制。一个多任务环境允许实时应用程序以独立任务的方式构造，每个任务拥有 独立的执行区域和相关的系统资源。 网络系统 v x w o r k s 嵌入式操作系统的网络结构如下图所示，它提供了网络系统的“透 明”访问，包括与b s d 套接字兼容的编程接口，远程过程调用( i 冲c ) 、远程文件 访问、b o o t p 代理和a r p 代理。v x w o r k s 所有的网络机制都遵循标准i n t e m e t 协 议。 t a r g e t r i f t p s e r v e l l 一，、一，i d n s r i p p v v 2 1 t p h p t，。c 儿e n t 厶： p i n g r p c 卜j r l o g i n 回叵圈巨矿 d h c p o s p f f 篇 s o c k e tr a ws 。c k e t t c pu d p - pi c m pi g m p a r p m 叮x s h a r e d m e m o r y n e t w o r k e t h e r n e ts l i p 1 p p 图1 2v x w o r k 嵌入式操作系统的网络结构 国防科学技术大学研究生院学位论文 文件系统 v x w o r k s 嵌入式操作系统提供了适合于实时系统的( 快速) 文件系统。它包 括几种支持块设备( 如磁盘) 的本地文件系统。v x w o r k s 也支持s c s i 磁带设备的 本地文件系统。v x w o r k si o 体系结构甚至还支持在一个单独的v x w o r k s 系统上 同时并存几个不同的文件系统。v x w o r k s 支持四种文件系统：d o s f s 、r t 1 l f s 、r a w f s 和t a p e f s 。 i o 系统 v x w o r k s 的i o 系统分为基本i o 、缓存i o 和格式化i o ，并提供基本的c 库。其中基本i o 与u n i x 标准兼容，为各种设备提供了简单一致、与设备无关的 访问接口。在基本i o 的基础上v x w o r k s 还提供了与a n s ic 相兼容的缓存i o 接 口( s t d i o ) 和格式化i o 接口( f i o l i b ) ，如下图所示左侧为函数调用主线。 图1 3i o 系统结构 1 1 2v x w o r k s 嵌入式操作系统的应用现状 常见的嵌入式操作系统有w i n d o w sc e 、u c o s i i 、r t - l i n u x 、v x w o r k s 等。 其中，w i n d o w sc e 是微软开发的一个开放的、可升级的、支持3 2 位运算的体积 小巧的实时操作系统，它可以在多种处理器架构上运行( 如x 8 6 、a r m ) ，其内核为 2 0 0 k b 。w i n d o w sc e 嵌入式操作系统是“软实时 的操作系统，可以应用于对时 限要求并不是很严格的地方。w i n d o w sc e 继承了传统的w i n d o w s 图形界面，可以 在w i n d o w sc e 平台上使用w i n d o w s9 5 9 8 上的编程工具，这就使得绝大多数 w i n d o w s 上的应用软件只需简单的修改和移植就可以在w i n d o w sc e 平台上继续 使用。w i n d o w sc e 的缺点是开机速度慢和容易死机。u c o s i i 较简单，且开源， 但功能有限，实际中用的比较少。r t - l i n u x 是在l i n u x 基础上实现了一个基于优 先级的抢占式实时内核，适合在需要提供比较复杂的系统服务、有较大的r o m 和 国防科学技术大学研究生院学位论文 洲空间时使用。 v x w o r k s 是2 0 世纪9 0 年代从美国风河公司引进的嵌入式实时操作系统软件， 具有很好的可靠性和实时性。v x w o r k s 是被业内公认的经典的强实时嵌入式操作 系统，美军的f 1 6 、e a 1 8 战斗机、b 2 隐形轰炸机和爱国者导弹上使用了v x w o r k s ： 1 9 9 7 年4 月在火星登陆的“火星探测者登陆车上也使用了v x w o r k s ；2 0 0 5 年7 月4 日，与坦普尔1 号彗星相撞的“深度撞击”号上的探测器搭载的r a 7 5 0 太空计 算机上也安装了嵌入式实时操作系统v x w o r k s 。 1 2g c c 编译器概述 g c c 是f s f 发起人r i c h a r dm s t a l l m a n 于1 9 8 7 年3 月2 2 日首次发布的可移 植的优化编译器，高度的可移植性和高质量的目标代码是g c c 的最大特点【2 】。 g c c 是用c 语言实现的，支持多种语言( c 、c + + 、f o r t r a n 、p a s c a l 等) 、多 种体系结构( p o w e r p c 、a r m 、m i p s 、s u p e r h 、1 3 8 6 、m 6 8 k 、s p a r c 、a l p h a 等) 的、可优化、可移植的编译系统。g c c 机器描述文件对目标机器的特点及其 每条指令都进行了详尽的描述，用户可以通过选择( 或改变) g c c 的机器描述文 件，使g c c 生成满足应用需要的目标机器代码。 1 - 2 1g c c 的设计思想 g c c 最主要的目标是为各种体系结构的平台构造一个优化的编译器。为了实 现高度的可移植性，g c c 的设计者们设计了非常新颖而独到的设计思想。其核心 设计思想包括以下三个方面【3 j ： r t l 中间代码表示机制 目标机描述与定义机制 由目标机的机器描述引导中间代码生成及优化机制 中间语言的使用是编译器实现代码优化和高度可移植的一项关键技术。g c c 从不同体系结构的机器语言中抽象出共性的操作，以形成一个适合编译时分析加 工的中间语言寄存器传输语言r t l ，该语言是一个描述硬件结构中寄存器值 互相转换与传送的语言。除了极少数的优化( 如表达式的先行计算) ，其它所有优 化都是在r t l 级上进行的。这个语言既可描述g n uc 中的各种运算和控制操作( 由 于它在操作和数据模式上类似于汇编语言) ，又便于对其进行深入的优化和汇编代 码的生成。 国防科学技术大学研究生院学位论文 前端分析 i 树优化 j r r t l 中间代码生 成 i 代码优化 i 汇编代码生成 图1 4 g c c 的整体结构图 在g c c 中，每种体系结构都有相应的一个机器描述文件( t a r g e t m d ) 。在这个 文件中，对该体系结构的每条指令所完成的操作以及各操作数的机器级存储模式 和数据模式，都以代数式的形式给出了详细的描述。对于用这个方法难以表示的 信息，g c c 将它们作为特定的参数定义在体系结构宏定义文件( t a r g e t h ) 中。例 如，机器的字长、寄存器的个数及使用规则、内存编址特性等。由于在r t l 中间 代码生成阶段，不同的编译参数组合会有不同的生成策略，而且每个体系结构汇 编语言代码的输出格式仅用机器描述文件是不能完全描述的。因此，g c c 对每个 体系结构都设置了一个目标机c 文件( t a r g e t c ) ，作为对上述两个文件内容的补充。 用户通过改写这三个文件，就可以完成g c c 向新的体系结构的移植。 g c c 最具特色的设计思想就是由体系结构的机器描述文件引导中间代码的生 成和优化。在传统的编译器中，中间代码的生成和优化都与具体的目标机器无关 的。因此，它们的中间代码不能表现目标机的指令特点和优化信息，这使目标代 码的质量受到很大的限制。而在g c c 中，由于机器描述文件中指令条目的设置是 依据g c c 内定的独立于具体机器的“原子操作”，并且指令描述中含有对应的中 间代码的操作与数据模式，使g c c 能在机器描述文件的引导下进行中间代码的生 成。同时，由于机器描述文件包含了目标机的具体特性，使得在它的引导下生成 的中间代码也含有给定体系结构的指令信息。这样，就可以在中间代码上执行某 些与机器相关的指令归并、窥孔优化及指令重排序等优化操作。 1 2 2g c c 的后端概述 如下图所示，g c c 的后端大致由三个部分组成：一个完成r t l 代码的生成、 国防科学技术大学研究生院学位论文 一个完成r t l 代码的优化、一个完成目标代码的生成。这三个部分都是通过目标 机器描述( m a c h i n ed e s c r i p t i o n ) 由一系列后端生成器进行操作的。这些后端生成 器都以g e n 开头，包括1 2 个相关的后端生成器。g c c 的后端负责实现各种优化操 作、寄存器的分配和汇编代码的生成。优化包括全部的常规优化和主要的r i s c 优 化，后端的代码在整个g c c 源代码中占有相当大的比例，后端的最后一遍处理是 汇编代码的生成。当经过前面几遍的分析处理后，提交的r t l 代码己经含有汇编 指令的雏形。在机器描述文件中的各种数据结构的引导下，最终生成汇编代码。【4 】 汇编代码的生成主要是完成指令的识别、汇编指令模板的获取，并据此输出汇编 指令模板和汇编指令代码，完成对一个g n uc 代码的编译。 g c c 的中间语言称为寄存器传递语言( r e g i s t e rt r a n s f e rl a n g u a g e ，r t l ) 。 g c c 编译器绝大部分工作都是对一种r t l 语言描述的中间表示形式进行加工处 理。r t l 中间代码是g c c 的核心数据结构，这种结构实际上表示的是一种树结构。 r t l 中间代码的内部数据结构是复杂的双向链表结构，外部正文表示用来进行机 器描述和调试输出。在生成r t l 的过程中，还要进行一些其他工作( 清除公共子 表达式，指令调度，循环优化和寄存器分配等) 。在完成了这些简单的优化后，还 会有很多更复杂的优化在后端进行。另外，把寄存器分配到堆栈也是在r t l 的生 成过程中实现的。 u n s s a 翻舔l 砑 图1 5g c c 目标代码的生成 在r t l 生成后的所有编译工作都脱离了某种具体语言的特征。g c c 使各种语 言在编译优化的实现上得到了统一，使得各种语言可以共享现有的最优的优化方 法。g c c 将各种语言映射成同等语义的g c c 标准语言r t l 。因此，如果要使g c c 支持一种新的高级语言，只需要修改g c c 的前端预处理程序。同时，r t l 还是 g c c 与多种机器平台的接口，所有的机器描述均由r t l 的外部形式书写。这样就 可以在使用统一的数据结构和宏定义的情况下，对不同的体系结构生成不同的目 标代码。 目标机器描述( m a c h i n ed e s c r i p t i o n ) 将r t l 代码的生成、优化和目标代码的 生成三者联系起来。通过r t l 对目标机器的配置进行描述，就可以得到特定目标 机器的g c c 后端。目标机器描述是目标机指令集的一个形式化说明文件，它针对 国防科学技术大学研究生院学位论文 q 州c 中的各种操作模式，描述了特定目标机支持的操作和实现情况。编译器根 据由机器描述生成的数据结构和函数定义集合，进行中间代码的生成以及中间代 码到汇编代码的映射。 为了解决编译系统的高度优化和高度可移植之间的矛盾，g c c 引入了“标准 指令 的思想【5 1 。大约2 0 0 个“标准指令是从各种目标机的指令集中抽象出来的， 同时又能表达g n uc 中的各种基本操作。目标机器描述( m a c h i n ed e s c r i p t i o n ) 由两部分组成：描述指令模板的m a c h i n e m d 文件和有关目标机宏定义的m a c h i n e h 文件( 其中m a c h i n e 对应具体的目标机，例如a r n l 、i 3 8 6 、m 6 8 k 、r s 6 0 0 0 、s p a r e 等等) ，m a c h i n e m d 文件对具体的机器指令进行描述，还有一些对目标机器的描述 以宏定义的形式记录在m a c h i n e h 文件中。而这两个文件中调用的函数在m a c h i n e c 中进行定义。一个机器描述文件由一系列指令描述项组成，它们包括指令定义描 述项、扩展定义描述项、窥孔优化描述项、分割指令描述项和指今属性描述项。 1 - 2 3g c c 的优化概述 前端分析 i 高层优化 t 0 局部优化 i 全局优化 i 与机器相关优化 i 代码生成 图1 6 编译器的优化层次 编译器所采用的优化技术可以分为如下四类1 6 j ：高层优化，通常作用于源程序 代码，其输出作为后面优化阶段的输入；局部优化，仅仅作用于基本块内代码的 优化；全局优化，将局部优化扩展到整个代码；与机器相关的优化，试图充分地 发挥特定体系结构的特点。 下表列出了基于以上划分的几种常用的优化技术。 围防科学技术大学研究牛院学位论文 表1 1 常用的优化技术 优化技术类别 优化技术实例 循环展开 高层优化 过程内嵌 局部公共子表达式删除 局部优化常数传播 堆栈高度削弱 全局公共子表达式删除 复制传播 全局优化代码移动 强度削减 归并变量删除 与机器相关 寄存器分配的图着色技术 指令调度软件流水 的优化 指令调度分支偏移优化 g c c 的优化策略如下图所示。 图1 7 g c c 的优化策略 首先，g c c 执行的是全局优化。由于对源程序进行直接的语义分析和中间代 码生成时会生成一些无用跳转，如交叉跳转、跳转到跳转等，因此要先对这类低 级、无用的跳转进行优化【7 j 。其后进行的公共子表达式的“物理删除 ，是用简单 的等价表达式替换当前顺序扫描点具有相同值的表达式，不考虑控制分支的情况， 用最低的开销最大程度的精简程序。接着根据数据流分析所采集的冗余信息，先 国防科学技术大学研究生院学位论文 进行常量复制传播删除的优化，这样可以减少操作数的数量，然后进行全局的公 共子表达式的逻辑删除，缩短中间代码的长度。 其次，g c c 执行的是循环优化。先将循环不变量外提，减少循环中被分析的 操作数的数量。然后逐个分析最外层循环中的操作数，进行强度削弱和基本归纳 变量的删除。最后再展开嵌套的循环，重复上述处理过程。 循环优化之后，g c c 执行的是基本块优化，但它并不是必须的，根据不同优 化参数的要求，有可能被执行一次或两次，甚至根本不被执行。基本块优化主要 完成“死代码的删除和指令合并，以减少指令的数量。然后重新安排指令的执 行顺序，提高时间、空间的利用率，从而确定了每个操作数的生存周期，并根据 操作数的生存周期进行寄存器的分配。 最后，g c c 执行的是针对某些特殊优化参数的优化，比如延迟分支的优化等。 当然，这些优化策略的执行并不是“一步到位 的。跳转优化在g c c 优化器 中执行了四遍，分别在中间代码生成以后、公共子表达式删除之后、寄存器分配 和重载后和整个优化过程结束以前【8 】。公共子表达式的物理删除的优化，也分别在 全局优化前和循环优化后各执行一次。实践证明，这种组织策略充分考虑了由于 某种优化的执行，带来的新的可优化的因素，能够很大程度地减少最终生成代码 的时间、空间的开销。 1 3 本文主要工作及其研究现状 v x w o r k s 嵌入式操作系统是个强实时嵌入式操作系统，其配套的集成开发环 境t o r n a d o 集成的是开源的编译器g c c 。由于使用的g c c 版本比较旧( g c c 2 9 6 ) ， 新版本的g c c 功能虽然强大但是很多编译参数需要修改，容易产生不可预测的错 误。所以需要在现在使用的版本上进行修改。现在使用的g c c 版本对于函数内联 的支持不足，无法为循环变换提供准确性较高的数据间依赖关系例，需要对其进行 改进。为了能够使用改进后的g c c 编译v x w o r k s 嵌入式操作系统，需要对v x w o r k s 嵌入式操作系统的编译过程进行详细的分析和研究。在编译v x w o r k s 嵌入式操作 系统时，需要对很多配置文件和系统文件进行管理和操作，这就涉及到很多环境 变量的修改和重新定义、脚本文件的修改和重写、以及对编译选项的分析和重写， 难度比较大，到目前为止还没有人做过有关这方面的工作。这就需要首先彻底的 弄清楚v x w o r k s 嵌入式操作系统的编译过程，然后对其中的每一步都进行分析， 改写其中的参数和选项。重新编译v x w o r k s 嵌入式操作系统有助于彻底弄清楚 v x w o r k s 的编译过程和t o r n a d o 开发环境在交叉编译的过程中所起到的作用，为自 主研发高效率的嵌入式操作系统及其开发环境做好理论和实践准备。 可执行的嵌入式操作系统镜像一般而言分为2 个部分：操作系统部分和应用 程序部分。对于操作系统部分，在满足系统基本要求的情况下代码越小越好。由 国防科学技术大学研究生院学位论文 于嵌入式系统对于代码体积的苛刻限制，导致不可能使用较大的存储器。所以使 用新的函数内联机制来操作代码内的内联函数显得十分重要。对于函数内联机制， 不同的编译器采用的机制基本相同。当然程序员也可以在编写代码的时候调用某 些宏定义( i n l i n e ) 或在编译程序时使用某些选项来要求进行函数内联，但最终是 否内联还是的有编译器决定。在经典的v c + + 编译器中，程序员可以通过关键字 i n l i n e 指定相应的函数进行内联，也可以通过“i n e 来指定允许的内联深度depth ( 可以是完全不内联0 ，也可以是最大化无限制的2 5 5 ) ，还可以使用# p r a g m ai n l i n e r e c u r s i o n 来决定内联函数是否可以递归调用自身。但是，对于内联的具体操作则 程序员无法做最终的决定。在程序编译的过程中，编译器是根据自身具有的默认 情况进行判断的。而该默认参数是一般情况下的，没有考虑特殊情况下如何处理。 在g c c 原有的内联机制中只是对函数的整体大小有限制( 函数内联后的指令数不 能超过1 0 0 0 0 ) 1 7 1 ，这样不加区分的内联使得很多内联后降低效率的函数也被内联 了。g c c 编译器过于强调执行效率所以倾向于多进行内联，这样在提高程序执行 效率的同时增大了代码的体积【l 引。出于代码简化的需要，v x w o r k s 嵌入式操作系 统中大量函数都是比较小的函数，所以使用g c c 时内联操作较多。本文设计一种 新的机制来判断函数是否应该内联以及对于内联后的代码体积进行很好的控制。 并对不同宏定义值情况下的镜像大小进行了测试。 在计算密集型的应用中，循环变换可以极大的提高应用的程序的速度。但在 进行循环变换之前需要先完成数据依赖性分析，找出循环数据的依赖关系。数据 依赖性的分析通常是一个无法完全解决的n p 问题。当前很多有实际应用的算法都 是通过牺牲精确性来换取分析的速度。但是，过低的精确性会导致大量的不确定 的依赖关系，这就极大的妨碍了对于应用程序的优化。近来，有很多对于应用递 归链技术到编译时的分析阶段的研究【l ，v a ne n g e l e n 提出了使用c h a i n so f r e c u r r e n c e s ( c r s ) 代数式，使用基于递归链c r 的变种来进行对归纳变量的分析算 法。常用的数据依赖关系分析方法主要有：d e l t a 测试、o m e g a 测试、最大公因子 ( g r e a t e s tc o m m o nd i v i s o rg c d ) 测试、b a n e r j e e 测试( 极值测试) 、r a n g e 测试 和p o w e r 测试和等。此外还有基于递归链的数据依赖分析。d e l t a 测试是一种简单 而有效的数据依赖关系分析方法。首先根据循环索引在两个数组下标中出现的次 数，将数组下标划分为零索引变量( z i v ) 、单索引变量( s ) 和多索引变量( m i v ) 。 其中，零索引变量和单索引变量之间的数据依赖关系可以利用解丢番图方程的方 法分析出来【l 。对于多索引变量之间的数据依赖关系，d e l t a 测试将耦合数组中的 每个s i v 下标生成的约束条件传给相同耦合数组中的其他s i v 下标，根据约束相 交来求解依赖关系是否存在以及存在依赖的情况下的依赖距离和依赖方向。但该 方法计算量很大，极易导致编译时间过长，在实际应用中往往需要和其他方法一 起使用。 另一种在实际应用中用的比较多的依赖关系测试方法是o m e g a 测试。该测试 国防科学技术大学研究生院学位论文 方法可以精确的解决线性相关问题，同时也可以解决很多非线性的问题。由于 o m e g a 测试测试不需要很多库函数的支持也可以精确的解决线性相关问题，所以 在一般情况下都是适用的。但是，o m e g a 测试的复杂性( 是分析数量的指数级) 太高【1 2 】，极大的降低了应用时的依赖分析的速度。另一方面，o m e g a 测试对于非 线性表达式的分析不够精确，只能得到粗略的结果。下面的例子证明，实际应用 中往往无法避免遇到非线性问题。 d oi = 1 m d oj = 1 i i j - - i j + l i j k l = i j k l + i j + l d ok = i + l ，m d ol = 1 k i j k l = i j k l + i x i j k l ( i j k l ) = x k l ( l ) c o n t n e c o n t i n u e u k l = i j k l + i j + l e f t c o n t i n u e c o n t 州e 在上述代码中，使用o m e g a 测试根本无法得到精确的结果。因为在变量x i j k l 中下标出现了多个值的组合。此时就只能假定变量x i j k l 之间存在依赖关系。而 这样做无疑会降低分析结果的精确性。 e n g e l e nv a n 等人对递归链进行了研究【1 3 1 ，使得可以使用递归链的公式来检测 和替换归纳变量以及进行值域分析。使用递归链来分析任何定义归纳变量的线性 表达式、多项式表达式或者几何级数表达式时，首先根据归纳变量的递归关系形 成一个递归链代数式。然后利用递归链代数式在多项式和几何函数的加法或乘法 运算中封闭的性质，可以很容易的计算索引表达式和指针访问。 在比较分析的基础上，本文提出并实现了一个能比较简单的确定循环间依赖 关系的增强递归链算法。在不显著提高资源消耗的情况下，提高数据依赖的分析 能力，能够对非线性数组访问和多索引下标数组进行分析，找出其中的自输出依 赖关系。为循环变换的开展提供尽可能充分的数据间依赖关系。提高循环迭代中 数据访问的“空间局部性 和“时间局部性”，从而提高代码的运行速度。 1 4 本文主要创新点 本论文的创新点主要有以下三点： 1 ) 嵌入式操作系统的编译过程很复杂。目前还没有对v x w o r k s 嵌入式操作系 统在新的编译环境下进行编译的先例。在编译v x w o r k s 嵌入式操作系统的过程中， 国防科学技术大学研究生院学位论文 需要对很多配置文件和系统文件进行管理和操作，这就涉及到很多环境变量的修 改和重新定义、脚本文件的修改和重写、以及对编译选项的分析和修改，难度比 较大。由于在这个过程中不仅需要对各个文件的具体编译选项进行指定，还要对 如何在编译的过程中添加或删除构件进行管理。但是现代嵌入式操作系统结构一 般都比较复杂，内部构件间互相关联，所以需要使用很多条件语句进行判断操作， 工作量比较大。只有在清楚编译的具体过程和构件间的关联的情况下才能进行具 体的操作。在这个过程中需要改写很多脚本文件和批处理文件，调试的难度较大。 本文通过认真扎实的分析研究工作，成功的使用了改进后的g c c 编译器重新编译 v x w o r k s 嵌入式操作系统。 2 ) 本文在分析清楚原有的( g c c 2 9 6 ) 上的实现机制后，设计并实现了一种 新的函数内联机制。原有的内联机制比较简单，只要函数满足内联后函数的代码 大小不超过全局变量i n l i n em a xi n s n s 规定的最大值内联操作就会进行【l9 。，在这个 过程中不会判断函数的大小是否过大。容易造成代码体积的膨胀。新的函数内联 机制既能够对于函数是否内联能够做到自动的识别，而且还使得内联后代码的效 率得到提高，并且能够对最终生成的函数大小进行有效的控制。对于内联的过程 中这些定义值对代码的影响和内联后对整个系统镜像大小的影响目前尚缺乏研究 和相关资料【2 0 1 。由于编译器的构造比较复杂。要在其上进行改进需要对其结构非 常熟悉。在决定函数是否内联前，需要考虑的因素很多：该内联函数是否被标记 为内联、函数大小是否合适、内联后原函数的代码大小膨胀是否过于巨大、什么 样的函数适合自动内联等等。 3 ) 本文设计并实现了一种新的消耗资源比较少的算法进行依赖关系的检测。 嵌套循环内数据间的依赖关系很复杂，为了使循环变换后的代码效率尽可能的最 优，需要分析出尽可能多的数据间依赖关系。但原有的分析机制对于非线性数组 和多索引数组的依赖关系无法进行分析。虽然在原系统中通过对变量操作前后是 否被“改写”来判断是否存在依赖关系在大多数情况下是可行的，但由此带来的 不准确的数据间依赖信息会影响到后续的循环变换的开展。通过对递归链的分析 与研究，本文提出了一种新的增强型递归链算法。该算法利用连续函数两端点间 的值一定存在的推论和递归链的单调性，在不显著增加系统开销的情况下能够分 析出更多的依赖关系。 1 5 本文组织结构 本文后续章节的组织如下： 第二章深入分析v