(计算机系统结构专业论文)链接后优化在龙芯上的实现.pdf_第1页
(计算机系统结构专业论文)链接后优化在龙芯上的实现.pdf_第2页
(计算机系统结构专业论文)链接后优化在龙芯上的实现.pdf_第3页
(计算机系统结构专业论文)链接后优化在龙芯上的实现.pdf_第4页
(计算机系统结构专业论文)链接后优化在龙芯上的实现.pdf_第5页
已阅读5页,还剩43页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

摘要 龙芯是由中国科学院计算技术研究所自主研制开发的一个通用芯片系列。龙芯1 号 是其第一个产品。在龙芯1 上运行的是l i n u x 系统,使用的编译器是g c c 。g c c 编译 的s p e c 2 0 0 0 程序的性能相对同主频的其他处理器比较差。造成这个问题的一个方面的 原因是因为龙芯上g c c 编译器的性能不理想。为提高龙芯上程序的性能,需要为龙芯 开发一个编译优化器。 链接后优化技术是在程序链接完成后再对整个程序进行优化的种技术,它克服了 传统编译优化局限于在分析一个函数或者一个模块的基础上做优化的缺点,能够对库函 数中的代码或定义于其他已经编译好的模块中的函数和调用它函数一起做优化。国外已 经有一些链接后优化器,a l t o 是其中的比较成功的一个。a l t o 系统是由美国a r i z o n 大学为a l p h a 处理器设计的链接后优化器。由于舢l p h a 与龙芯同样是采用r i s c 结构, 同样具有较小的指令集和寻址方式,因此将a l t o 作为在龙芯上实现链接后优化器的参 照。 本文从介绍在龙芯上实现链接后优化的意义开始,随后以a l t o 为例分析了链接后 优化器的基本系统架构,并结合龙芯中e l f 文件格式的知识逐步介绍了系统中每个模块 在龙芯上实现的详细过程。分别分析了每个环节中碰到的问题,并提出了相应的解决方 法。最后对完成的系统系进行了测试,并对测试结果做了分析。 关键词:链接后优化;a l t o :g o d s o n ;p r o f i l i n g ;e l f al i n k - - t i m e o p t i m i z e r f o rg o d s o n l i nl i n g ( c o m p u t e r a r c h i t e c t u r e ) d i r e c t e db y t a n g z h i m i n g o d s o ni st h ef i r s ts e r i a lo fg e n e r a l p r o c e s s o r i nc h i n ad e s i g n e db yi c t at h e o p e r a t i n gs y s t e mo fg o d s o n1 i sl i n u x ,a n dt h ec o m p l i e ri st h eg n ug c c f r o mc o m p a r i n g t h es p e c2 0 0 0 p r o g r a mc o m p i l e db y g c ca n dt h o s ec o m p i l e dm i p s p r oo ns g im i p s ,w e f i n dt h e p e r f o r m a n c eo fg n u g c co n g o d s o n i sn o t g o o de n o u g h t oi m p r o v et h e p e r f o r m a n c e o ft h ep r o g r a mo n g o d s o n ,w e s h o u l dd e s i g na no p t i m i z e rf o ri t d i f f e r e n tw i t ht r a d i t i o n a lo p t i m i z i n gc o m p i l e r s ,w h i c ha r el i m i t e di nt h es c o p eo ft h e i r o p t i m i z a t i o n sb yt h ef a c tt h a to n l yas i n g ef u n c t i o n ,o rp o s s i b l yas i n g l em o d u l e ,i sa v a i l a b l e f o ra n a l y s i sa n do p t i m i z a t i o n al i n k t i m eo p t i m i z e rc a l l sa n a l y s i st h r o u g ht h el i bc o d ea n d c l o s s m o d u l e s t h e r ea l em a n yl i n k - t i m eo p t i m i z e r sn o w , a n da l t oi sas u c c e s s f u lo n e a l t oi sap o s t l i n ko p t i m i z e rd e s i g n e df o rd e ca l p h a f o rs om a n ys i m i l i t u d e sb e t w e e n a l p h aa n dg o d s o n a l t oi sag u i d ef o rt h ed e s i g no fal i n k t i m eo p t i m i z e rf o rg o d s o n t h i sa r t i c l eb e g i n sf r o mi n t m d u c i n gt h ei m p o r t a n c eo ft h ew o r k ,a n dt h e nd e s c r i b i n gt h e a r c h i t e c t u r eo ft h es y s t e mb a s e do i la l t o a f t e r s t a t i n gt h ei n f o r m a t i o no f t h ee l f , w h i c hi s t h ef i l ef o r m a t ,u s e di ng o d s o n ,t h ea r t i c l ed e s c r i b e st h ee n t i r ec o u r s eo ft h ed e s i g no fa l lo ft h e m o d u l e so ft h e s y s t e m ,a n a l y s i s t h e p r o b l e m o ft h e d e s i g np r o c e s sa n d a d v a n c e st h e c o r r e s p o n d i n g r e s o l v e k e y w o r d s :a l t o ,p r o f i l i n g ,i j n k - t i m eo p t i m i z e r ,e l f ,g o d s o n 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得 的研究成果。就我所知,除了文中特别加以标注和致谢的地方外,论文中 不包含其他人已经发表或撰写过的研究成果。与我一同工作的同志对本研 究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 作者签名:毒i 於 日期: 伊妒7 3 0 关于论文使用授权的说明 中国科学院计算技术研究所有权处理、保留送交论文的复印件,允许 论文被查阅和借阅:并可以公布论文的全部或部分内容,可以采用影印、 缩印或其它复制手段保存该论文。 作者签名:专,f 被导师签名:作者签名:中,| 影i = 导师签名: :伽妒,7 妙 第一章引言 传统的编译优化器局限于在分析一个函数或者一个模块的基础上做优化。这种做法 有两个缺点,首先,库函数中的代码或定义于其他编译好的模块中的函数不能和调用它 函数一起做优化,这意味着这些函数代码里面会重复使用一些如寄存器保存和g p 寄存 器计算之类代码,这会降低程序性能。其次,分析和优化的结果不能从一个用一种语言 编写的模块传递给另外一个用另一种语言写的模块从而导致对另一个模块的优化做的不 够彻底。一种可行的解决办法是在整个程序包括库都可以被分析的时候,也就是链接后, 再对整个程序执行一次优化。 龙芯是由中科院计算技术研究所自主研制开发的一个通用芯片系列。龙芯系统上运 行的是l i n u x 系统,其上使用的编译器是g c c 。龙芯1 上g c c 编译的s p e c 程序的性 能与同主频的处理器相差甚远。其原因有两个方面,一个方面是龙芯处理器的本身性能 的限制,另一个方面是龙芯1 上g c c 编译器的性链不理想。由于链接后优化技术能一 定程度上提高程序性能,尤其是在国外已经有了为a l p h a ( 和龙芯同样采用r i s c 结构 的处理器) 设计的链接后优化器a l t o 取得了很大成功,所以为提高龙芯1 上s p e c 程序的性能,在龙芯1 上实现一个链接后优化器是可行的方法之一。 本章先简单介绍了链接后优化技术和一些成功的链接后优化器,分析了现在龙芯上 编译器的性能,指出在龙芯上实现链接后优化器的意义,随后以a l t o 为例分析了链接 后优化器的系统架构,最后说明本文的总体安排组织。 1 1 链接后编译优化技术简介 传统的编译优化器的分析和优化都局限于在个函数或者说一个模块中。这种代码 优化模式因为两个原因并不能达到他们本身应有的效果。首先,库函数中的代码或定义 于其他编译好的模块中的函数不能和调用它函数一起做优化,这意味着这些函数代码里 面会重复使用一些如寄存器保存和g p 寄存器计算之类代码,这会降低程序性能。随着 软件系统的日益复杂,程序员也越来越依赖库函数来实现代码复用。虽然现在也有一些 人在做跨模块的编译优化的工作,但是他们的工作只限于用户自己编写的模块,而对于 库函数去没有处理。其次,分析和优化的结果不能从一个用一种语言编写的模块传递给 另外一个角另一种语言写的模块从而导致对另一个模块的优化做的不够彻底。 一种可行的解决办法是在整个程序包括库都可以被分析的时候,也就是在链接的时 候,再对整个程序执行一次优化。虽然这种做法避免了传统优化的一些局限,但是同时 也带来不少问题,比如: 机器代码相对源代码而言语义信息比较少,这样使得比较困难发现控制流和数 据流信息( 慨如,对于像s v a i t c h 或c a s 。这样的语句产生的可执行代码中,很难 1 中国科学院硕士学位论文链接后优化在龙芯上的实现 判断出对应的跳转表的范围和目标地址,而在源代码中就很直接的能看出来) 传统的编译器在分析时针对的是用源代码语言表示的结构组成的源程序,它不 需要考虑许多坏的情形,如指针或数组越界。相对而言,对于可执行代码的分 析,需要考虑的都是这些比较糟糕的情形。如果一个函数的参数比较多的话, 一部分参数就必须通过堆栈来传递。在这种情况下,通过堆栈传递的参数存放 在调用函数的堆栈的顶端,被调用者以后将访问这些参数,这种情况是种典 型的不能越界的数组访问。 可执行程序比他们对应的源代码通常要大很多。这意味着在处理这些缺乏语义 信息的可执行程序时,原来在源代码级别上处理的很好的分析算法可能在可执 行代码级别上实现代价非常高,需要非常长的执行时间和非常大的执行空间。 1 2 链接后优化器介绍 国外已经有不少成功的链接后优化器,如: i s p i k e 。i s p i k e 是为i n t e l 的安腾( i t a n i u m ) 处理器开发的链接后优化器。安腾 处理器提供了丰富的性能计数器( p e r f o r m a n c ec o u n t e r ) 使得链接后优化工作的 关键收集p r o f i l i n g 信息一的代价大为降低。对于s p e e2 0 0 0 的基准测试程 序,在安腾上i s p i k e 能够使性能最高提高4 0 。对于g c c 编译出来的程序平均 性能提高了9 9 。 1 t l o 。 i t l o 同样是为安腾开发的链接后优化器。对于s p e c2 0 0 0 的基准钡4 试 程序,i t l o 能比g c c 至少提高4 。 p l t o 。p l t o 是为i n t e l 的n 3 2 结构开发的链接后优化器。i a 3 2 架构的链接 后优化比较复杂,因为它不像r i s c 结构的处理器那样具有较小的指令集,寻 址方式和通用寄存器。p l t o 对于s p e c9 5 的基准测试程序比g c c 能平均提高 6 2 。 a l t o 。a l t o 是由美国a r i z o n 大学为d e c 辽p h a 设计的一种链接后优化 器。a l t o 系统很大程度上提高了程序性能,对运行在装有3 0 0 m 的a l p h a 2 1 1 6 4 处理器和5 1 2 m 内存的机器上的s p e c9 5 的基准程序,个别程序甚至达 到了3 3 4 。具体运行结果如下图所示。 2 第一章引言 c i n t 9 5 程序 图1 1c i n t 9 5 程序 图1 2c f p 9 5 3 中国科学院硕士学位论文链接后优化在龙芯、扛的实现 1 。3 链接后优化在龙芯上实现的意义 龙芯是由中国科学院计算技术研究所自主研制开发的一个通用芯片系列。龙芯上面 运行的是l i n u x 系统,其上使用的编译器是g c c 。在龙芯1 上用g c c 编译过的s p e c 程序的性能如下图所示。从图中可以看出用在龙芯1 上g c c 编译的s p e c 程序的性能与 另外两个相差甚远。其原因可能有两个方面,一个方面是龙芯处理器的本身性能的限制, 另一个方面是龙芯上g c c 编译器的性能不理想。 图1 3g o d s o n 定点性能对比 4 第一章引言 图1 4g o d s o n 浮点性能对比 而g c c 在s g i 上与m i p s p r o 编译器性能比较如下: 图1 5g c c 性能比较 5 中国科学院硕士学位论文链接后优化在龙芯上的实现 从上面的图可以看出同样采用m i p s 指令集的机器上面g c c 的性能不尽如人意,而 龙芯正是采用的m i p s 指令集。链接后优化能在一定程度上提高程序性能,为提高龙芯 上s p e c 程序性能,在其上实现一个链接后优化器是一个可行的方法。 1 4 a i t o 架构分析 在前面介绍的链接后优化器中,a l t o 是为舢l p h a 处理器设计。龙芯1 号与a l p h a 在结构上很相似,同样是采用精简指令集结构,同样有很少的指令操作和很少的寻址方 式。而且龙芯1 上面的文件系统e l f 文件格式也与a l p h a 上的c o f f 文件格式在结构 上也有很多相似之处。因此a l t o 系统的架构对在龙芯上实现链接后优化器具有指导作 用。a l t o 具体架构如下图所示: 图1 6a l t o 系统结构 第一章引言 a i t c i 系统处理的是静态链接的程序,因为只有这样才能对库函数进行优化。首先 a l t o 对要处理的程序进行反汇编,并且根据反汇编的结果构造程序流程图。a l t o 对 程序的优化分为两种。一种是没有p r o f i l i n g 反馈信息的简单优化,称为o p t i m i z e e a s y 。 一种是基于p r o f i l i n g 反馈信息的复杂优化,称为o p t i m i z e h a r d 。为收集p r o f i l i n g 反馈信 息,a l t o 同时还实现了一个p r o f i l i n g 功能。在优化过程中修改了代码,程序中代码的 地址都发生了改变,必须对修改后的代码进行修复,以保证函数调用、分支能到达正确 的代码。 上述a l t o 架构中的各个部分都能在龙芯上实现,因此,龙芯上的链接后优化器也 采用上述架构。 1 5 论文的组织 本文从本节介绍链接后优化及其在龙芯上实现的意义出发,在本章中总体介绍了链 接后优化器系统的具体架构。随后的章节根据上面介绍的架构分别具体介绍每一个模块 在龙芯上的具体实现。 在第二章中,介绍了展开本次工作所需的基础知识一e l f 文件格式,并详细介绍 了一些我们后面工作所必须了解的龙芯1 上e l f 文件格式的一些信息。 以上章为铺垫,第三章详细描述了我们如何对一个静态链接的程序进行反汇编, 并在此基础上构造整个程序的流程图。 接着在随后的章节中着重介绍了如何针对不同的应用目的来处理反汇编后的程序, 分别从p r o f i l i n g 、o p t i m i z e e a s y 和o p t i m i z e h a r d 三个方面介绍了具体的实现方法。 在第四章和第五章分别介绍了如何做p r o f i u n g 和优化。在第六章我们重点介绍了如 何修正修改代码后所带来的一些问题。 第七章给出了最终运行的s p e c 2 0 0 0 基准程序的数据,对系统性能从多方面进行了 综合分析和评价。 最后,对整个论文进行了总结,并给出了将来的研究方向。 第二章e l f 文件格式 龙芯上使用的是e l f 文件格式。链接后优化中反汇编,汇编,以及修改后代码的修 复这三个部分都与文件格式密切相关。因此了解e l f 文件格式是实现这些环节的基础。 本章首先简单介绍e l f 文件格式和一个可执行的e l f 的组成部分;然后详细介绍 在具体在龙芯1 上e l f 文件格式的每个部分的具体意义。 2 1e l f 文件格式介绍 e l f ( e x e c u t a b l e a n dl i n k a b l ef o r m a t ) 是u n i x 系统实验室( u s l ) 作 为应用程序二进制接口( a p p l i c a t i o nb i n a r yi n t e r f a c e ) 而开发和发布的。工具接口标准委 员会( t i s ) 选择了正在发展中的e l f 标准作为工作在3 2 位i n t e l 体系上不同操作系 统之间可移植的二进制文件格式。假定开发者定义了一个二进制接口集合,e l f 标准用 它来支持流线型的软件发展。这样可以减少不同执行接口的数量从而可以减少重新编程 重新编译的代码。 e l f 格式的目标文件有三种主要的文件类型: 2 可执行文件:包含了代码和数据。这种类型的文件中指出了操作系统是如何来 创建程序进程映像的。 3 可重定位文件:包含了代码和数据( 这些数据是和其他重定位文件和共享的目 标二进制文件一起连接时使用的) 。用来和其他的目标文件一起来创建一个可执 行文件或共享文件。 4 共享目标文件( 又可叫做共享库) :包含了代码和数据( 这些数据是在连接时候 被连接器1 d 和运行时动态连接器使用的) 。用来被下面的两个链接器使用:第 一个是链接编辑器( 在l i n u x 中是l d ) ,可以和其他的可重定位和共享文件来创 建其他的目标文件,第二个是动态链接器( 在l i n u x 中是l d s o ) ,联合一个可执 行文件和其他的共享目标文件来创建一个进程映象。 e l f 文件参与文件链接( 创建一个程序) 和程序的执行( 装载一个程序) 。因此e l f 文件格式提供了一个并行的,反映在链接和执行活动中不同的需要的视角看待文件的内 容。下图显示了一个文件的组织图。 9 中国科学院硕士学位论文链接后优化在龙芯上的实现 f i g u r e1 - 1 ob j e c tf i l ef o r m a t l i n k i n g v i e we x e c u t i o nv i e w e l fh e a d e r p r o g r a m h e a d e rt a b 捂 o p t i o n a t s e c l b n l s e c t i o n n s 鲥i o nh e a d e rt a b l e e l fh e a d e r p r o g r a mh e a d e r t a b l e s e g m e n t 1 s e g m e n t 2 s e c t i o nh e e d e rt a b l e e 蕊o a i 图2 1e l f 文件结构图 由上图可以看出在一个目标文件中,在文件的开始存放着个e l f 头,描述了该文 件的组织情况。节( s e c t i o n ) 保存着目标文件的链接信息:包括指令,数据,符号表, 重定位信息,特别的节的描述会在本章的第二部分介绍。本章的第三部分讨论了段 ( s e g m e n t ) 和从程序的执行角度看文件。如果存在一个程序头表( p r o g r a m h e a d e rt a b l e ) , 那么它告诉系统如何来创建一个进程的内存映象。被用来建立进程映像( 执行一个程序) 的文件必须要有一个程序头表( p r o g r a m h e a d e rt a b l e ) ,可重定位文件不需要这个头表。 一个节头表( s e c t i o nh e a d e rt a b l e ) 描述了文件中节的信息。每个节在这个表中有一项, 每项都是一个节头结构,给出了该节的名字,大小等信息。在链接过程中的文件必须有 一个节头表,其他文件可要可不要这个节头表。 在l i n u x 中e l f 头的具体结构如下所示: # d e f i n ee in i d e n t1 6 t y p e d e fs t r u c tt u n s i g n e dc h a r e 1 f 3 2h a l e e l f 3 2h a l f e 】- f 3 2w o r d e 1 f 3 2a d d r e 1 f 3 2o f f 1 0 e _ i d e n t 【e i - n i d e n t 】: e _ t y p e ; e _ _ m a c h i n e ; e _ v e r s i o n ; e _ e n t r y ; e - p h o f f ; 第二章e l f 文件格式 e l f 3 2 o f f e l f 3 2 j f o r d e l f 3 2 h a l l e l f 3 2 h a l f e l f 3 2h a l f e l f 3 2 h a l f e l f 3 2 一h a l f e l f 3 2 h a l f ) e l f 3 2 e h d r ; e _ s h o f f : e _ f l a g s j e _ e h s i z e ; e _ p h e n t s i z e ; e _ p h n u m ; e _ s h e n t s i z e : e _ s h n u m ; e _ s h s t r n d x ; 上面的结构中有几个元素需要我们特别关注: e e n t r y该成员是系统第一个控制入口的虚拟地址,程序在那启动进程。假如 文件没有关联的入口点,该成员就保持为0 。 ee h s i z e 该成员保存着e l f 头大小( 以字节计数) 。 e p h o f f该成员保存着程序头表( p r o g r a mh e a d e r t a b l e ) 在文件中的偏移量( 以 字节计数) 。假如该文件没有程序头表的的话,该成员就保持为0 。 ep h e n t s i z e 保存着在文件的程序头表( p r o g r a mh e a d e rt a b l e ) 中一个项的大 小( 以字节计数) 。所有的入i s l 都是同样的大小。ep h n u m 保存着在程序头表 中入口的个数。因此,e ) h e n t s i z e 和e 的乘积就是程序头表的大小(以phnum 字节计数) 。假如没有程序头表( p r o g r a m h e a d e r t a b l e ) ,ep h n u m 变量为0 。 e 该成员保存着节头表(在文件中的偏移量( 以字_ s h o f f s e c t i o nh e a d e rt a b l e ) 节计数) 。假如该文件没有节头表的的话,该成员就保持为0 。es h e n t s i z e 保存 着节头的大小( 以字节计数) 。一个节头是在节头表( s e c t i o nh e a d e rt a b l e ) 的一 项;表中所有项都是同样的大小。e _ s h n u m 保存着在节头表( s e c t i o n h e a d e rt a b l e ) 中的项的数目。因此,es h e n t s i z e 和es h n u m 的乘积就是节头表的大小( 以字 节计数) 。假如文件没有节头表,es h n u m 值为0 。 e _ s h s t m d x 该成员保存着跟节名字符表( 节名字符表是e l f 文件中一种特殊的 节,它保存着其他节的名字。关于节名字符表的具体描述见下一部分) 在节头 表的索引。假如文件中没有节名字符表,该变量值为s h nu n d e f 。 2 2 节韵具体描述 一个文件的节头表中每一项都是一个节头结构,通过节头结构可以让我们定位相应 的节。节头表是个e l f 3 2 _ s h d r 结构的数组( 下面描述) ,数组中的每一个e l f 3 2 一s h d r 结 构表示一个节头。 中国科学院硕士学位论文链接后优化在龙芯上的实现 s e c t i o nh e a d e r t y p e d e fs t r u c t ( e l f 32 _ w o r ds h _ n a m e ; e l f 3 2 w o r ds h _ t y p e ; e l f 3 2 :w o r ds h _ f l a g s ; e l f 3 2 _ a d d rs h _ a d d r ; e 1 f 3 20 f fs ho f f s e t : e l f 3 2 w o r ds h _ s i z e ; e l f 3 2 _ w o r ds h _ l i n k ; e l f 3 2 w o r ds h _ i n f o ; e l f 3 2 _ w o r ds h _ a d d r a l i g n ; e l f 3 2 j f o r ds l l e n t s i z e : ) e l f 3 2 _ s h d r ; 上面的结构中有几个元素也需要我们特别关注: s h 该成员指定了这个节的名字。它的值是节名字符表中的索引。f看以_name 下的“s t r i n g t a b l e ”1 , 以n u l l 空字符结束。 s h _ t y p e 该成员指出该节的类型。如s l i t _ n u l l 表明该节头是无效的;它没有 相关的节,该节的其他成员的值都是未定义的,s h t _ s y m t a b 或 s h t _ d y n s y m 表示该节保存着一个符号表( s y m b o lt a b l e ) ,s h t _ s y m t a b 为 连接器提供标号,当然它也有可能被动态连接时使用。作为一个完整的符号表, 它可能包含了一些动态连接时不需要的标号。因此,一个目标文件可能也包含 了一个s h td y n s y m 的节,它保存着一个动态连接时所需最小的标号集合来 节省空间。s h tr e l a 和s h tr e l 表示该节保存着具有明确加数的重定位入 口。一个目标文件可能有多个重定位的节。s i l ts t r t a b 表示该节保存着一个 字符串表。一个目标文件可以包含多个字符串表的节。 s h _ f l a g s该成员是节的标记,用来描述多个属性。如s h f _ w r i f e 表示该节 含有可写的数据,s h fe x e c i n s t r 表示该节包含了可执行的机器指令。 s h _ a d d r该成员给出了该节在内存中的位置。如果该节将不出现在进程的内存 映象空间里,该成员为0 。 s h _ o f f s e t 该成员变量给出了该节在文件中的字节偏移量( 从文件开始计数) 。 s h t _ n o b i t s 类型的节在文件中不占空间。 s h _ s i z e该成员给出了节的字节大小。除非这个节的类型为s l i tn o b l t s ,否 则该节将在文件中将占有s hs i z e 个字节。s h tn o b l t s 类型的节可能在内存 中为非0 的大小,但是不占文件空间。 s h _ a d d r a l i g n该成员给出了节的地址对齐约束。文件中有一些节有地址对齐的 1 2 第二章e l f 文件格式 约束。例如,假如一个节保存着双字,系统就必须确定整个节是双字对齐。所 以s ha d d r 的值以s h 的值作为模,结果一定为。当然的,仅仅0和_addralign 0 2 的正整数次方是允许作为s h _ a d d r a l i g n 的值。0 和1 意味着该节没有对齐要求。 s he n t s i z e 一些节保存着一张固定成员大小的表,如符号表。对于这样一个节 来说,该成员给出了表中每个项的字节大小。如果该节没有保存着一张固定大 小的表,该成员就为0 。 下丽列举的是一些我们工作中要处理的一些特殊的节,它们的具体意义将在后续的 工作中进一步描述: g o t 该节保存着全局的偏移量表。 i n i t 该节保存着可执行指令,它构成了进程的初始化代码。因此,当一个程序 开始运行时,在m a i n 函数被调用之前( c 语言称为m a i n ) ,系统安排执行这个 节的中的代码。 t e x t 该节保存着程序的正文,或者说是可执行指令。 f i n i 该节保存着可执行指令,它构成了进程的终止代码。当一个程序正常退出 时,系统安排执行这个节的中的代码。 r o d a t a 该节保存着只读数据,在进程映像中构造不可写的段。 r e l a n d r e l a 。这些节保存着重定位的信息,假如文件包含了一 个可装载的段,并且这个段是重定位的,那么该节的属性将设置s h fa l l o c 位:否则该位被关闭。按照惯例, 4 】 # d e f i n e e l f 3 2 一s t t y p e ( i ) ( ( i ) & 0 x f ) # d e f i n ee l f 3 2 _ s t i n f o ( b t ) ( ( ( b ) 8 ) # d e f i n ee l f 3 2 _ rt y p e ( i ) ( ( u n s i g n e dc h a r ) ( i ) ) # d e f i n ee l f 3 2 一j l i n f o ( s ,t )( ( s ) 8 + ( u n s i g n e d c h a r ) ( t ) ) ra d d e n d 该成员指定一个常量加数( 用于计算将要存储于重定位域中的值) 。 一个重定位节关联了两个其他的节:一个符号表和一个可修改的节。该节的节头中 的成员s hi n f o 和s hl i n k ( 在上文中的关于节部分中有描述) 指示了这种关系。重定 位入口中的成员ro f f s e t 对于不同的目标文件有少许差异。在可执行和共享的目标文件 中,ro f f s e t 表示一个虚拟地址。为了使得这些文件的重定位入口更为有用( 对于动态 链接器而言) ,该节的偏移( 文件中) 应当让位于一个虚拟地址( 内存中的) 。 对于寄存器跳转,它的目标地址不是存放在g o t 中,确定它的目标地址需要关联到 不是t e x t ,i n i t 和f i n i 这三个节的重定位节的信息。如果重定的值( v a l u e ) 等于程序的 入口地址,重定位关联的值为对应的节中的值。如果重定位的类型为rm i p sg p r e l 3 2 , 此类型的重定位表示是和g p 寄存器项关联,表示重定位所关联的值要加上g p 的值。 如果重定位关联的值是代码,则表示的是个基本块的开始。而这个基本块可能就是某 个跳转的目标基本块。 3 2 3 流程图的构造 构造流程图的关键是计算出函数调用或跳转的目标地址,而函数调用的目标地址是 存放在一个叫做g o t 的全局偏移表的节中。 一般情况下,位置无关的代码不包含绝对的虚拟地址。全局偏移量表中傈存着绝对 地址。一卜程序通过位置无关的地址来索引它的g o t ( 全局偏移量表) 来获得绝对的地 址。g o t 表的格式和解释是处理器相关的。 2 2 第三章程序流程图的构造 龙芯1 中函数调用主要有如下两种情形 1 w t 9 ,0 x 1 2 a ( g p ) 1 wt 9 ,o x l 2 3 ( g p ) a d dt 9 ,0 x 1 2 3 j a l r t 9j a l r l 9 情况一 情眦一 在龙芯1 体系结构下,g o t 表可以看作是一个e l p 3 2 _ a d d r 的数组。由于g p 寄存 器值是固定的,因此,1 w 指令操作的地址也是固定的。上面所示两种情况实际上都是从 g o t 中读取相应项作为函数调用的目标地址,而g o t 中的内容也是固定的,因此可以 计算出这两种函数调用的目标地址。 在程序中有时会出现一些比较特殊的和上一部分介绍的两种情形有所不同的函数调 用形式( 如下图所示) 和寄存器跳转,它们的目标地址并不能通过简单的分析指令序列 来确定所有的目标地址,a l t o 系统中构造了一个伪函数,命名为- 一h e l l “,作为在这 些不能确定目标地址的跳转和函数调用的目标地址。 1 wa 0 ,0 x 1 2 3 ( g p ) m o v et 9 ,a 0 j a l rt 9 情况三 根据上一部分基本块的识别的结果对每一个基本块进行处理,具体如下: 对于含有分支指令的基本块,它是分支类型的基本块,存在两个出口:一个是分支 指令成功的目标块,此时用一条e tt r u e 类型的边从分支类型的基本块指向目标基本 块。另一个出口是分支不成功的目标块,也就是此分支类型基本块相邻的下一个基本块, 此时用一条e tf l a s e 类型的边指向这个相邻的基本块。 。 对于含有函数调用指令的基本块,它是函数调用类型的基本块,只有一条出去的边, 此边为e t 类型指向被调用函数的第一个基本块。同时此基本块有一条为_fun_call e t 兀j n _ l i n k 类型的边指向相邻的下一个基本块。 对于含有跳转指令的基本块,如果此基本块中跳转指令是短跳转指令,跳转的目标 是确定的,此时用一条e tj u m p 类型的边指向目标所在的基本块。一种是此时是一个 函数的返回,即跳转的目标地址放在r a 寄存器中,则此基本块是函数返回类型的,此 时我们让它用一条e te x i tl i n k 指向自己。另一种可能是普通的寄存器跳转,说明此 基本块为跳转类型的基本块,此时我们用一条e tj u m p 的边指向伪函数。 第四章代码优化 本章将介绍链接后优化的核心部分代码优化,包括我们在第一部分介绍过的 o p t i m i z e e a s y 和o p t i m i z e h a r d 两部分。其中o p t i m i z e e a s y 是没有p r o f i l i n g 反馈信息时实 现的优化,o p t i m i z e h a r d 是在有反馈信息的时候所实现的优化。这两个方面将在下面的 具体内容中分别介绍。 4 1 程序分析 在进行优化之前需要对程序进行一些分析,a l t o 中主要实现了常数传播分析和函 数间生存周期分析,这些分析同样在本系统上得到了实现。具体实现过程描述如下。 4 1 1 函数问间常数传播分析 链接时比编译时有更多的信息来分析程序间常数传播。这是因为以下两个原因:首 先,整个程序包括库函数在内都是可以分析的,其次,在链按时可以检测到并处理一些 与体系结构相关的运算,而这些运算在编译器处理使用的中间代码表示中是无法检测和 处理的。第二种情况的一个例子是龙芯中g p 寄存器的计算:g p 寄存器的值通常在每个 函数入口重新计算次,但实际情况它的值是固定不变的,这些重复计算g p 寄存器值 的代码是没有必要的,可以通过在整个程序中传播g p 寄存器的值来消除这些不必要的 代码。 本系统中所用的分析是基本的迭代常数传播分析,分析只限制于寄存器但是在整个 程序流程图全局范围进行分析。这种分析把常量参数信息从调用函数传递给被调用函数。 为提高精确度,系统考虑了函数调用返回的情况:如果一个在函数中开始时保存并且退 出时恢复的寄存器r ( r 在函数被调用之前包含一个常数c ) ,那么可以认为r 在函数调用 完成后也会含有常数c 。 4 1 2 函数问生存周期分析 函数间数据流分析可以是上下文相关的,也可以是上下文无关的。上下文无关分析 简单的把单个函数的控制流图联合成一个大的流程图并且对这个流程图采用标准的函数 内分析方法,没有对函数调用和返回边进行追踪。这种做法的好处是简单并且效率高, 不需要对函数间的控制流程进彳亍特殊处理,而且一个函数也不会因为它的不同的函数调 用点而进行重复分析。这种分析的问题是这样分析精确度不高。相反,上下文相关分析 维护着函数调用边与相应的函数返回边的信息。使得信息只在真正的函数调用和返回路 中国科学院硕士学位论文链揍启优化在龙芯上的实现 径上传播。这样提高分析精确度的代价是使得数据流分析的代价也相应提高了。 本系统实现了一个相对直接的函数间生存周期分析,分析限制在寄存器上。分析时 必须考虑m i p s 指令的特性。如系统调用s y s c a l l 指令,这条指令是操作系统的入口,必 须特殊处理,因为这条指令中所涉及的寄存器不是显式可见的。 为了使数据流信息只在真正的调用返回路径上传播,本系统为每个函数计算描述信 息。并且用这些描述信息来模拟函数调用的效果。对于一个给定的调用点,这个调用点 含有调用节点m 和一个返回节点,被调用的函数式f ,函数调用对生存周期的影响可 以通过以下两个信息来描述: 1 m a y u s e q 。表示可能被函数f 使用的寄存器。如果有一条真正的从函数f 的 入口节点到一个寄存器r 使用点的路径,路径中间没有寄存器r 的定义,则寄存 器r 可能被f 使用。m a y u s e f 表示一个寄存器集合,集合中的寄存器在函数f 入口总是活跃的 2 b y p a s s f l 。表示一个寄存器集合,集合中的寄存器如果在,活跃,那么在m 也 活跃。也就是在f 中没有从新定义的集合。 b y p a s s f 的选择可以有些弹性。可以选择一个保证在f 入口死亡的寄存器的完整集 合作为b y p a s s f 。这种选择的问题是在b y p a s s t m a y u s e 两个集合之间存在一种紧密 地依赖关系,这使得流程平衡变得复杂。也可以选择m u s t d e f i 作为b y p a s s f , m u s t d e f i 是一定会被f 定义的集合,这样避免了上面蜕的依赖关系。不难看出任何在 m u s t d e f i 年l im u s t d e t i f j 【j 之间的集合可以作为一个 。 选择的_ m a y u s e f b y p a s s i a l t o b y p a s s i 是m u s t d e t i f 的个超集。 我们的分析过程分为三步。前两部计算函数的描述信息,也就是函数的m a y u s e 和 b y p a s s 集合。第三步利用计算出来的这些信息来进行真正的生存周期计算。虽然前面两 步可以并行处理,但是这样会需要更多的空间,所以并不这么做。 如果上下文相关生存周期分析没有仔细处理函数中保存和恢复寄存器( c a l l e es a v e r e g i s t e r ) ,这种分析同样有可能变得很保守。考虑一下一个函数保存一个寄存器的内容, 然后在返回之前恢复它的情形,这个被保存的寄存器r ,首先它是一个s t o r e 操作的操作 数,因而它被函数f 使用,在随后的恢复操作中,寄存器r 又作为l o a d 操作的目的操作 数,因此是被函数f 定义。一个直观的分析会认为r 在被函数定义之前使用了。这样会 导致寄存器被认为在f 的每个调用点都是活跃的。为解决这个闻题,系统尝试着判断每 个函数中先被保存后又被恢复的寄存器( 这样的寄存器经过函数调用值不会发生变化) , 也就是c a u e e - s a v e 寄存器。如果函数f 的c a l l e e s a v e 寄存器集合,s a v e f 可以被检测出 来,我们可以把它们从m a y u s e f e p 移出来加入b y p a s s f 中。 第四章代码优化 4 2 简单优化 系统中的o p t i r n i z e e a s y 主要是对整个程序进行分析找出其中的一些无用指令,删除 这些指令来提高程序性能。具体可以分析如下: 1 计算g p 值指令的消除 对于g c c 编译出来的代码,在每个函数的都会有一段代码来计算g p 寄存器的 值或者保存g p 寄存器的值到堆栈,而这段代码对于静态链接好的程序来说是 没有必要的,完全是为了链接时重定位才需要的。所以完全可以把这段代码删 除。 2 无效指令的消除 无效指令指这种指令的执行与否根本不会影响到程序的最终结果。主要是一些 结果寄存器为0 号寄存器的一些指令或者是一些目的寄存器与源寄存器相同的 移动指令。 3 无法到达指令的消除 在编译时,无法到达指令也就是那些永远不会执行的代码一通常是由用户 自己构造的( 例如那些可有由一些表示控制的调试信息) 或者是执行其他优化 的结果这些通常可以通过函数内分析检测并消除。而链接时无法到达代码的检 测相对比较困难

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论