（计算机应用技术专业论文）基于gcc的静态单一赋值优化编译技术的研究.pdf

：；。；：；竺玺篓塞童：量茎銎耋耋! ! ! 鎏；。； 摘要 静淼单一赋氆楚一项基于g c c 盼优纯编译技术，l e n g a u e r - t a r j a n 是静态 单一赋值实现过程中用来计算流图中必经节点的快速算法。该算法使用 e v a l ，需运行大量出口、入口程序，并髓必了减少对e v a l 徽多次无效调 用。受了解决这些闽题，首先，对g c c 优化体系、馋化器主要特点、优化 编译技术、优化工作流程、静态单一赋值技术、必经节点树生成技术及其实 现算法l e n g a u e r - t a r j a n 、路径愿缨技术及其实现函数e v a l 等进行细致地研 究。然嚣，提出解决闯题豹实时化最佳点算法，并飙毽论上对算法进行论_ 【芷。 理论分析表明：在很大多情况下，基于实时化最佳点的l e n g a u e r - t a r j a n 性能 优于基予e v a l 蛇l e n g a u e r - t a r j a n 。 关键词：g c c ；静态单一赋值：必经节点；实时最佳点；活跃节点 ；= ；。；：；。些堡鎏兰塑查兰罂耋耋l ! 鳖； a b s t r a c t s t a t i cs i n g l ea s s i g r a m e n ti sa l lo p t i m i z a t i o nc o m p i l e rt e c h n i q u eb a s e do n g c c l e n g a n e r - t a r j a l li saf h 8 ta l g o r i t h mf b rf i n d i n gd o m i n a t o r si naf i o w g r a p h d u r i n gt h ei m p l e m e n t a t i o no fs t a t i cs i n g l ea s s i g n m e n t ，w h e nf u n c t i o ne v a l i s u s e di nl e n g a u e r - t a r j a n 。i ti sr e q u i r e dt oe x e c u t ec a l l sa n d 北扭i n l sd u r i n gt h e c a l l i n gp r o c e s s e s ，a n dt h e r ea r em a n yu s e l e s sc a l l s 协e v a l t os o l v et h e s e p r o b l e m s ，啦f i r s t ，t h eg c co p t i m i z a t i o na r c h i t e c t u r e , t h em a i no p t i m i z e r s f e a t u r e s ，t h eo p t i m i z a t i o nc o m 西l e tt e c h n i q u e s ，t h eo p f i r m z a t i o nw o r kf l o w , t h e s t a t i cs i n g l ea s s i g n m e n tt e c h n i q u e ，t h ed o m i n a t o r - t r e eg e n e r a t i o nt e c h n i q u ea n d i t sr e a l i z i n ga l g o r i t h ml e n g a n e r - t a r j a n , t h ep a t hc o m p r e s s e dt e c h n i q u ea n di t s r e a l i z i n gf u n c t i o ne v a la r ea n a l y z e di nd e t a i l t h e na l la l g o r i t h mt os o l v et h e p r o b l e m s ，w h i c hi sc a l l e dr e a l w t i m eb e s t - p o i n t , i sp r e s e n t e d + r e a l - t i m e b e s t - p o i n ti sp r o v e dw i t hv a l i d i t i e si nt h e o r y t h ea n a l y s i si nt h e o r ys h o w st h a t , t h el e n g a n e r - t a r j a nb a s e do i qr e a l t i m eb e s t - p o i n ti sm o r ee f f i c i e n tt h a n e v a l * b a s e dl e n g a u e r - t a r j a ni na g o o dm a n yc i r c u m s t a n c e s 。 k e y w o r d s ：g c c ；s t a t i cs i n g l ea s s i g n m e n t ；d o m i n a t o r ；r e a l - t i m eb e s t - p o i n t ； l i r e v e r t 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均己在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担： 作者( 签字) ： 日期：赫6 年f 目，b 1 1 引言 第1 章绪论 g c c h ( g n uc o m p i l e rc o l l e c t i o n ) 是用c 语言实现的，向上可接收多种语 言，向下可支持多种操作平台的可移植编译系统。为了达到高性能的优化效 果，同时又不影响其系统的可移植性、稳定性，g c c 的优化器设计有其独特 的优化策略与实现技巧。尤其是所采用的清晰的前端语法树结构、高度概括 的中间语言、简洁灵活的后端机器描述以及开放式的整体结构，使得g c c 达到了可移植性和高效优化的统一。 在g c c 优化体系中，优化器完成了基于r t l 代码优化的核心工作。在 g c c 优化的整个工作流程中，采用了多种优化编译技术，如转移优化、公共 子表达式删除、循环优化、指令归并、寄存器分配、延迟分支、循环展开和 指令调度等。 目前，在g c c3 0 以上的版本中，优化器均采用了一种静态单一赋值 ( s t a t i cs i n g l ea s s i g n m e n t ，s t a t i cs i n g l ea s s i g n m e n t ，简称s s a ) 优化编译技术， 这是优化编译中的一项关键技术，它使优化转换更加有效，其中包括常数传 播( c o n s t a n tp r o p a g a t i o n ) 、值编号( v a l u en u m b e r i n g ) 、强度削弱( s t r e n g t h r e d u c t i o n ) 等等。在静态单一赋值技术实现过程中采用了必经节点树生成技 术，该技术的实现算法为l e n g a u e r - t a r j a n 算法，这是本课题所要研究的主要 内容之一。 1 2 课题背景及意义 l e n g a u e r - t a r j a n 是在1 9 7 9 年由l e n g a u c r 和t a r j a n 两人共同提出的，它 采用e v a l 函数来搜索节点的最佳点，但是，e v a l 采用递归调用方法，需 执行大量的出口、入口程序，并且在算法实现中对e v a l 做了多次无效调用， 从而浪费了大量的运行时间和存储空间。本课题需要通过一种新技术来解决 上述问题，通过将基于e v a l 函数的l e n g a u e r - t a r j a n 改进为基于这种新技术 哈尔滨工程大学硕士学位论文 术及数据流技术等。 第3 章介绍了g c c 优化器采用的优化编译技术，其中包括转移优化、 公共子表达式删除、循环优化、指令归并、寄存器分配和指令调度等技术， 并对采用上述技术的g c c 优化器的优化工作流程加以描述。 第4 章研究了静态单一赋值优化编译技术，重点剖析这一技术实现过程 中的必经节点生成树阶段，描述了这一阶段采用的l e n g a n e r - t a r j a n 算法以及 l e n g a u e r - t a r j a n 采用的路径压缩算法的实现函数e v a l 。 第5 章对l e n g a u e r - t a r j a n 进行了改进，提出了基于实时化最佳点 f r e a l t i m eb e s t p o i n t ，简称r t b p ) 的编译优化算法r t b p 。对该算法的有效 性进行了分析，并对各个评判准则的正确性给予了证明。从理论上分析了基 于e v a l 的l e n g a u e r - t a r j a n 和基于r t b p 的l e n g a u e r - t a r j a n 在性能上存在差 异的原因，并设计一个静态实验加以说明。 ：= ；一；些纛鎏奎茎堡圭塞! i i 鳖；：一；。；一； 笫2 章g c c 优化体系研究 这一牵将获g c c 往凭的总体体系绪稳入手，先薅g c c 傀纯帮分毒一个 全局的了解，然后对体系的核心部分优化器进行概凄介绍。 2 。 g c c 煞饶耽体系 g c c t t i 是一个高度优化、高度可移植的编译系统，用c 语言实现。它能 够处理多粒语言，包缍e c + + 、f o r t r a n j a v a 襄c h i l l 等。不溺楚浯吉峦 不同的前端词法与语法分析器避行分析，建立语法树，生成中间语言r t l ， 最终调用热同的后端优化与代码生成的处理程序。 整个系统戆工终滚程峦一个慧控翟旁控裁，经过羲蝼势辑和爱壤娃瑾两 遍扫描来党成从一个g n u c 源文件到目标机汇编代码的转换。 总控糕序负责初始化、译码参数、打开关闭文件并控制各遍的操作。前 端宠裁语法、语义分糖帮孛趣技筠魏生袋。它瓣输入为镶处理嚣戆源文 牟， 处理是以个函数为单位，生成中间语法树，然后转换戚r t l 中间代码。语 法分析程序是由一个y a c c 自动啦成工具生成的，该工典接收l a l r ( 1 ) 文法。 嚣端整理簿畿蚤耱倪纯、毒存嚣分嚣帮汇编健羁匏生成。侥纯包耩全帮零怒 优化和主器r i s c 优化，它们的代码在g c c 中占有相当大的份量，丽且每遍 优化都是对r t l 中间代码的一遍处理。后端的最后一遍处理是汇编代码的生 成。在掇嚣箍述产生熬各耱数摆绥糖g 导下，健玛生成熬主要工捧楚避行指 令识别、获取汇编指令模板，并据此输出汇编指令优化代码，最终完成对一 个g n uc 源码程序的翻译1 3 】。 g c c 貔霞让薅系凑如下三个秘分搀或； 一是匈源语言相关的p a r s e r ，实现源代码的词法分析、语法分析和语义 处理，并将源代码映射成等价的抽象语法树。 溺法分辑 词法分析阶段是编译过程的第一个阶段。这个阶段的任务是从左割右一 4 哈尔演工程大学硕士学位论文 个字符一个字簿遮读入漂程序，鄄对榴成澡程序的字符流遗行扫撼然后根据 构词规则识剐单词( 也称单词符母或符号) 。 词法分析器接收字符流，生成一系列的名字、关键字和标点符号，并舍 弃了记g - 之闻的空照符和注释。那些睫极啦现的空白德和注释将分板过程复 杂化了，这也是将词法分析单独分离出去的主要原因。 l e x 是一个词法分析程序的自动生成工具，它输入描述构词规则的一系 列正规拽，然后构建商穷壹动巍移这个有舞皂动机的一个驱动程侉，进瑟生 成一个谰法分柝程绺。 语法分析 语法分橱是绽译过程的一个逻辑除段。语法分攒的任务是在词法分析的 基础上将单词序列缀合成各类谮法短语，如“程序”，“语句”，“表达式”等等。 语法分析程序判断源程序在结构上是否正确。 y a e c 是一个语法分橱程序的鑫动生成工具。它接受语言蛉文法，梅造 个l a l 掰 ) 分析程净。因为它采用语法制露翻译的愚慧，还可以接受用c 谣 言描述的语义动作，从而构造一个编译程序。y a c c 是y e ta n o t h e rc o m p i l e r c o m p i l e r 的缱写 q 。 语义分析 语义分析是编译过程的一个逻辑阶段。语义分析的任务是对结构上正确 的源程序进行上下文毒关性质的审查，进稃类型审查。铡妇一个c 程序片断； i n ta r r 2 】，b ； b a n 4 1 0 ： 源程序的鳢梅是正确的。语义分橱将事查炎型并报告锩误：不缝在表达式中 使用一个数组变量，斌值语句的右端和左端盼类型不嚣配。 抽象语法树 g c c 对不同豹语言使用不目的词法语法分辑处理鼹录，在该强录中所处 理的工彳譬包括司法分析、语法分析、语法树生成、针对不同的语法成分调嗣 公共的r t l 生成函数，生成r t l 中间语亩。编译器在对源文件的一遍扫描 中，生成语法挺帮褥号表。 语法树结点静公共部分是一个趣ec o m m o n 结构，每种类望的树结点都 包含它。其一般形式如图2 1 。其中，c h a i n 为指向其它树结点的指针，树绪 哈尔滇卫程大学硕士学位论文 点的c h a i n 域通常将属于菜个藏畴盼树缝点枣在一起擒成一条链；t y p e 为指 向表示类型的裙结赢的指针，给出该树结点所表示对象韵数据类激；c o d e 域 为一枚举常数，指明所表示实体的种类，如常数、字符串等；f l a g s 是一些标 志位；s p e c i a l 睫c o d e 的不同瑶装示不同静绩惠。在t 髓- c o 黜。n 缝梅戆基破 上荐船士指向r t l 的指针、指淘结点所表示的对象的指针和各种络点的特征 信息，构成向量结点、类型结点等各种树结点。 图2 。1 樾结点络梅 当编译器的分析程序扫描刹一个c p p 时，查询已有的符号表。_name 如果没蠢找到该撂识符，就生成薮的标识骛续点，设麓c o d e i d e n t i f i e rn o d e 。对于一个标识符丽亩，除了标谈符结点，遥有一些说 明结点，记录标识符的各种说明信息，如类刺、名字、所在文件名等，其c o d e 域为”d e c l f 3 l 辫。 二怒根据枫器攒述生成r t l 的中闽代码生成嚣帮基于中丽 码的饶纯 器，它处理的对象完垒是中间代码，针对中间代码进行备种优化，r t l ( r e g i s t e r t r a n s f e rl a n g u a g e ) 悬g c c 的中瓣代码形式。这里，仅介绍中闻代羁生成的过 程，至予优纯器和中间语言r t l 将在后续部分一一加驭详细地介绣。 ( 1 ) 机器描述文件 机器描述文件的建立是实现g c c 高可移植性的关键技术。g c c 的规嚣 描述文俸为“处理器蕊片名m d ”。文悻中包含营标机器的每条指令的模式。 一个机器描述文件由一系列描述项组成，作用于中间代码生成和优化、目标 代码生成阶段。 除了猕述目标梳器支持静指令，m d 文件还定义一系列属性和它们的值。 指令的每个属性都有定义，用于说明机器娄型、指令长度、指令类型等。m d s 哈尔滨工程大学铆i 士学位论文 文件辩鹫猕辊器韵各个功能都箨魂骰了定义。为了篌篁三成代码的执行更加商 效，辘器瓣述还镪懿黠指令姆势、分裂秘窥i 0 优穗等定义。 定义指令 定义指令是梳器播述中最鬟要内容。姆个指令模式都预兔包装在一个 d e f i n ei n s n 表迭裁孛。该表达式燕包含鞠或五个搡佟数鼢r t l 褒遮式： 名牢 r t l 模板 一个不宠整静r t l 表达式淘蠡。其不完整牲毯予雹弼r a a t e ho p e r a n d 、 m a t c h _ o p e r a t o r 等表选式来替代指令操作数。最常用的操作数表达式为 ( m a t c ho p e r a n d ：mnp r e d i c a t ec o n s 缸a i n t ) ，其中，i z i 为机器模式，n 为搡千# 数 痔号，p r e d i c a t e 燕骞豁器检查函数名，c 镕n s t r a i n t 是舞存瓣努鬻约索； 条件 一个字符串，包含一个最终弼来测试礴您指令体是否西配谈模我的c 袭 达式： 输出模板 嗣于说臻怎样簸遂配指令输趱成茫臻代码。在字符窜中，指定用来代 替操撵裁俊懿地方； 可选项 娃燕一个跹配该模式翁指令的属经值缀成的淘譬。 下嚣是一个定义攒令麴铡予： ( d e f i n e i n s n ”a d d v e i 3 ” 洳e t ( m a t e i t _ o p e r n n & s 10 r e g s t e r _ o p e r a n d r 熊“鼍。，( m a t e h _ o ，p e r a n d ：s i 1 “r e g _ o r _ o _ o p e r a n d ” “r j , r j “) ( m s t e h _ o p e r a n d ：s l 2 “a e x t _ a d d _ o p e r a n d ” ”r l - 0 ”竹) 】 、 ”国 a r i d l y 妇l ，2 o s u b v r 1 n 2 o ”) 该定义描述一祭s l 模式0 攀字模藏) 静翔法措令，搽维名为a d d v s i 3 。模式 题配赋，辕爨汇编f 羁a d d l v r l ，2 ，帮s u b t v r l 、娃，0 。 寄 宰器分配约荣 哈尔滨工程大学硕士学位论文 一个指令模式的每个m a t c h _ o p e r a n d 能针对允许的操作数类型指定一 个约束。约束可以选择操作数是寄存器操作数或是内存访问，以及寄存器类 型等。约束也能要求两个操作数匹配。最简单的约束类型是一个全是字母的 字符串，每个字母描述一种允许的操作数类型，如：“。表示只写操作数，m ” 表示内存操作数等。 对机器描述文件的使用 g c c 在具体应用机器描述文件时，通过名为g e n t 的多个程序读取m d 文件 的不同部分，形成相应的名为i n s n - * 的c 源程序，分别作用于r t l 生成、与机 器有关的优化和汇编代码输出等过程。 具体而言，g e n a t t r t a b c 、g c n c o n s t a n t c 1 3 9 e n f l a g s c 生成一些编译过程中所 需的头文件。g e n o p i n i t c 生成的i n s n o p i n i t c 中包含一个i n i t a l l o p t a b s 函数，用 来视始化操作表的i r i s h - c o d e 分量。 如果在r o d 文件中定义j d e f i n e = p e e p h o l e ，g e n p e e p c 生成的i n s n - p e e p c 中， 则会生成相应的窥孔优化操作。 g e n e m i t c 为每条定义的指令、窥孔优化等生成相应的g e n _ 函数，放在 i n s n - e m i t c 文件中。r t l 表达式生成时通过 g e n - - f c n ( _ o p t a b - - h a n d l e r s ( i n t ) m o d ei n s n _ c o d e ) 0 调用相应的g e n _ 函 数。 g e n r e c o g c 生成i n s n r e c o g c 文件，该文件主要包含三棵决策树，用以判断 一个r t l 表达式是否是一条合法的指令、是否能被分裂等。 f l q g e n c o d e s c 和g e n o u t p u t c 生成的i n s n - c o d e s h 和i n s n - o u t p u t c 中给出几个 数组，并为其赋初值。以前面给出的a d d v s i 3 指令定义为例，生成的数组间关 系见图2 2 ，c o d ef o ra d d v s i 3 = 1 1 给每条指令模板一个固定编号。该编号 可以作为各种i n s n + 衷的索引，既是对该指令模板进行处理的函数的编号， 又是由该模板生成的函数或数据结构的编号。o u t p u tn 为汇编模板静态数组 1 9 0 0 1 1 1 1 。 ；：一；。；堕玺婆玉墼奎兰些鬟! ：i 鎏；：；。； 图2 2 从m d 得到的数组关系图 ( 2 ) 0 0 t a b 表 g e n o p i n i t c 生或貔 n s n - 。p 遗丸c 争置含一个潍t _ 基l o p m b s i 滋，嚣- x 镑戆证 操作表。绦作表用来说明如何为各种机器模斌和各个操作数生成指令体。其 结构是： t y p e d e f s t 2 u c to p t a b e n u mr t xc o d ee o d e ； s t r u e t e i q u mi n s nc o d ei r i s h _ c o d e ； r t xl i b f u n c ： h a n d l e r s n u mm a c h i n em o d e s ： 4 0 p t a b ； 如图2 3 所示，每个o p t a b 袭项对应一个标准操作。在运行函数i n i ta l l o p t a b s 前，只有i n s n _ e o d e 由函数i n i t _ a l l _ o p t a b s 赋值，其余内容都是编译内定 好静。当i n s n _ c o d e 为0 辩，l i b f u n c 为疼罄痒霸数名；蚕粼，毙n u l u n 。 9 c o d e = p l u s h a n d l e r s 【】 i n e r tc o d e = c o d e _ f o r a d d v s i 3 h a d l e r s s l m o d e l i l 井u n e = ( m * ) _ a d d v 1 3 0 h 8 n d l “i 】 图2 3o p t a b 表结构 ( 3 ) r t l 的生成 在g c c 中，中间代码的生成程序与目标机器无关，但生成的中间代码含 有目标机器的特性信息，其技术方法是：由机器描述构造的r t x 表示生成函 数，它具体生成某一操作的r t l 代码，在语法分析的控制下，g c c 对各种语 句调用相应的r t l 扩展函数，生成中间代码。由于表达式运算存在复杂的类 型检查、优先关系和结果类型模式的确定等工作，g c c 首先调用相应的语法 树构造程序，生成该表达式的语法树，然后，再调用扩展表达式函数，将语 法树递归扩展为r t l 中间代码。r t l 的生成过程见图2 4 。 图2 4 中间代码生成结构图 三是与目标机有关的代码生成器。 代码生成器m ”4 皖成将中间代码r t l 转换为目标机上的汇编指令代码， 经过前面各个阶段的分析处理，提交给代码生成器的r t l 中间代码已经含有 汇编指令的雏形，并按其逻辑顺序关系以双向链表形式连接在一起，而且对 哈尔滨工程大学硕士学位论文 大部分的r t l 指令已经做了指令识别限t l 代码中已填入了根据机器描述产 生的汇编指令代码的编号) 。代码生成将以指令链的顺序对未识别的r t l 指 令模式体进行指令识别，取得指令模板并从r t l 中提取出该指令各操作数的 r t x 表达式，最后调用汇编指令输出函数直接输出该指令的汇编代码到s 文件 中。 代码生成的总控程序是f i n a l 0 ，它完成对一个函数生成汇编代码。首先 进行各种变量的初始化，然后获取当前函数r t l 指令链的链头，并依次对链 中的r t l 指令调用f i n a ls c a ni n s n ( ) 函数，为每条r t l 指令生成汇编代码。 函数f i n a ls c a ni n s n 针对不同的r t l 指令代码进行不同的处理。首先，处 ：t 单_ n o t e ( 注释1 、b a r r i e r ( 栅拦) 及l a b e l ( 代码标号) ，对a s mi n p u t 指令 体，直接输出汇编代码。对含有操作数的汇编指令模式体，将调用d e c o d e a s m 数取得各个操作数及指令模板，并以此输出汇编代码。对于_operands c a s e 转移指令体，将输出标号向量中的每个标号。最后输出含有机器指令对 应的r t l 模式体的汇编代码，具体有以下九个步骤： ( 1 ) 取得r t l 指令模式体。 ( 2 ) 如果优化标志被置起并且目的操作数为条件码，则删除多余的测试 和比较指令。 ( 3 ) 如果为条件分支指令并且条件值为静态值，则需做相应优化处理： 产生一个无条件分支f i x ，或者删除该指令( 标示为n o t e ) 。 ( 4 ) 如果优化标志被置起，则执行与机器有关的窥孔优化。它将调用由 机器描述产生的函数p e e p h o l e 。 ( 5 ) 如果r t l 指令未被识别。则调用r e e o g 对模式体进行指令识别，取得 指令代码编号。r e c o g 函数由机器描述文件产生。 ( 6 ) 从r t l 指令模式体中提取各个操作数。置于数组r e c o g ，o p e r a n d s 。 ( 7 ) 检查操作数约束。此时应满足操作数约束，否则报告失败。 ( 8 ) 根据指令代码编号，从模板数组中取得汇编指令模板。 ( 9 ) 根据指令模板，调用o u tp u ta s m _ i n s n ，输出汇编指令。 由于汇编代码对每个目标机都有不同的具体格式，因此汇编代码生成是 一个复杂的过程，仅使用目标机的指令描述是不够的。还需要某些与机器相 关的宏定义和辅助子程序的支持i i s 。 哈尔溅工程大学硕士学位论文 g c c 优讫体系如图2 , 5 磁示。恣了实施铙纯，编铎器首先从壤译禽令行 中解析优化参数，经过分析饕p a r s e r ，将源程序翻译戚等价的语法树形式， 转化为r t l ；程序出口调用优化器，根据解析的不同优化参数实施相应的优 化策略，代码生成瓣读入优化焉鲍中闯代鹃，生成可执行极器碣弗竣出。 图2 5g c c 优化体系 其中，优纯器部分完成了蕊于r t l 伐码优亿的核心工作。g c c 优纯器 设计的主要特点是：其，制定了规划合理、性能优越的优化策略；其二， 定义一种处理麓单、运行亳效、与优他策略糖适合的啦阕语富；獒三，采藤 控制流分析和数措流分析等技术来为优纯实施提供必鬻技术准备翻支持。 2 2g c c 优化器溉述 2 2 1 g c c 优化器的优化策略 文皴1 1 6 1 中奔缓了c r 2 c 优化器的实施簸癌，其攒述魏图2 6 掰示，实菰 上在编译器的其它部分还合理地瓶翔了可实施的其它优化，例如在p a r s e r 中 就实现了表达式化简、删除无用赋值等优化。 ；篁彗轰塞奎兰至当篓堡! 鎏 ；。 ； 图2 6 优化器的优化策略 首先，g c c 优纯器所实藏瓣是全局优鼗。鑫于辩源程廖进行文接的语义 分析和中闯筏蔼生袋，会产生一些无用跳转，如交叉蹒转、踽转到跳转等， 因此要先对这类低级、无用的跳转进行优化。其后进行的公共子表达式的“物 理删除”，是尾簿单的等徐表达式替换当裁联序扫接点舆寿捃同毽瓣表达式， 不考虑控弗8 分支静情况，用最低的开销最大程度的精简程序。接着根据数据 流分析所聚集的冗余信息，先进行常量复制传播删除的优化，这样可以减 少操作数驰数量，然舞避霉亍全属的公共子袭遮式的逻辑剿除，够练短中阕 代码的妖疫。 其次，g c c 优化器实施的烧循环优化。先将循环不变量外提，减少循环 中被分槲鲍操作数的数量。然基逐个分柝最外层循环中瓣操作数，避孳亍强度 酗弱和基本归纳交量静删除。最后再震开嵌套的循环，重复上述处理过程。 循环优化之后，o c c 优化器实施的是基本块优化，但它并不怒必需的， 根据不同优化参数的要求，有可艇被执行一次或两次，旗至攫本不被援行。 基本安优纯主要完成毵代码静删除和指令合并，戳减少指令静数量。然后重 新安排指令的执行顺序，提高时间、空间的利用率，从而确定了每个操作数 翟翟萤 一莎 降 一一降l一 降一 一 一产鲤黼茵 哈尔演工程大学硕士学位论文 的生存髑甥，著搬撰操作数的生存周期遴抒寄存器的圣 酲。 最尉，g c c 优化器所实施的是针对菜魑特殊优化参数静优化，是可扩充 的，比如延迟分支的优化等。 g c c 的优化策略中毒两个熏要戆优化“遍”静组织；跳转优纯鞠公共子表 达式龅物理删除。跳转优化在g c c 优化器中实施了三遍： ( 1 ) 中间代码生成以后； ( 2 ) 公共子表遮藏删除之藤； ( 3 ) 整个优讫过程结束以前。 公共子表达式的物理删除的优化，也分别在全局优化时和循环优化后备 实施一次。实践证明，这静缌缎策略充分考虑了由予慕种证化的寰涟，带来 的新豹可优化的因索，能够粮大程度地减少最终生成代码的时间、空间的开 销。 2 。2 。2g c 0 豹孛阑语言 为了满足支持多种前端谮亩和多种目标平台，g c c 没有统一不同语言前 端的语法规则和不间目标平台的指令系统，丽是将前端语言抽象成统一形式 戆语法瓣，荐映凳| 势没有语富特征蕊中弱代玛，使蔫统一鳃数据结构名和宏 操作名，当各种优化处理结束瞄，再映射为目标机代弼。g c c 定义的中间语 言r t u m “1 ，是一种接近机器搬令的语言。既有指令序列组成的内部形式， 又寿辍嚣箍述帮调试德惠缀袋蠡辱文本形式。其孛，r t l 的巍器描述部分有掰 个功能：当语法树映射为r t l 时，机器描述提供指令序列的模板；当r t l 映射为汇编代码时，它提供汇编模板。因此，r t l 中的机器描述充当了g c c 蠢多语富藏端、多麓标襁平台l l 奄接叠，萁穰念翅銎2 7 辑示。 雾语言 前端 圈2 。7g c c 撬纯器羧墨获蓦| 鹜 哈尔淇工程大学硕士学位论文 r t l 的使用将霹重用的部分分离出来，通过接口实现不同阶段的映射。 极大地提高了g c c 的适应往，增强了系统的可维护憾、可扩展性和可移植 性。g c c 优化器的处理对象是r t l ，在优化技术的实现上，它将r t l 的语 言结构霸摆令特性与傀他器弱傥纯策琏充分缝合，二囊鹈辘辐或，获褥更蕊 效的代祸。因此，r t l 是g c c 优化体系中非常有效并且稳定的裁体。 2 2 3 控制流分析技术 控露l 渡分辑是伉纯实麓静强要技术壤餐和支持，箕分耩结巢是产生“流 图”。“流圈”是具有嘴一首结点的有向图，窀表示了源程序执行的控制流。其 中结点代表基本块，有向边表示程序的控制流。 g c c 饶证器豹控案l 濠分辑静主要任务簸是：逶遗辘定基本块潮存氲逸捣 造“流圈”，基于“流髑”识别循环，同时为数据流分析采集信息。g c c 的控制 流分析并不完全是基于r t l 代碣的，而是在进行语义分析、生成r t l 的同 薅提炼了都分控裂浚信意，篾诧了盖嚣帮这些信惑穗美静算法，翔函数、锤 环、活跃变量、异常控制等算法。 ( 1 ) 基本块的鸯找与确认 g c c 在语义分辑茅西生成r t l 静霹辩，谖爱基本块静头檬、浃镩、函数 开始点、异常控制域的开始，结柬点，并且予以标识。尚优化器进杼控制流分 析的时候，通过对中间代码的翔描、匹配、判断，识别那些所标识的特殊变 量，扶嚣准确缝谖剐基本块。翔盈2 8 掰示秘实铡，菠浃了c 语蠢程痔静基 本块向r t l 基本块的映射。 i e ：一1 1 i 十+ ：b 2 刚c j b 融2 62 5 5 72 ，5 2 63 1 b b ： n o t e _ i n s n _ b a s l c b l o c k 3 i3 l5 7 3 2 ( 辩l 抽鸭：s 5 8 ，如o n s t j n t 胁l 】) ) if i 日) ( r a i d ( ) ( 1 a b e l r d 4 7 ) ) - ( 1 i i l ) | r i l l ) ) 一一。篡毛! 鳖一一二一 图2 8 基本块结构示意图 啥尔滨工程大学硕士学位论文 澍辫2 8 孛的c 源耧撵片断，g e c 将其煳分为5 个蕊率块糯瑰，强2 。8 巾 的r t l 代璐便是黠基零块b 2 的艇嚣。其中 l j o t o 标识瓣诲匍，是崔语义分辑麴 肘候识别出来的，其质的“艮b2 r 衰示基本块2 躲语句体的开始。在r 戳中入 瑟语锅袭拳为“c o d el a b e l 谶“r n s n 。惑鞴语句授播不满酌转穆褥征， 褒示为“j u m p j n s n ( 跳转罗、“b a r r e r ( 中颠y 细 c a l l _ i n s n ( 调翔严。语 旬体睦l “i n s n ”和； n o t e ”构成。阉时，基本块螅入豳边如口边的壤息、慕 零块串活跃炎量的愤怒、辩翔信患帮该蘩本块程循环串掰处韵深麓帮襻在子 上述谗匈中。 此外，g c c 还程每个基本块的嚣匿添加了个异鼹按卷4 域撅记，它仅以 拯针豹形式存在于攀本斌翡数据结构串，不产生具体桷黼吼代礴，不警戒l 汇 编代码。方疆，不傻w 致随时藤掩异常德凝，面且西以鼓凄镗为蒸率块结 柬的标患，不必进行如f = 】语句的判断，节键了时闯与空闻的开支。另方蘸， 玄连接了鹭翦基本浚鞠麓继蒸本炔痔巅，体现了控靠流信惑。 n o t e 蹙型鳆r t l 语句蠲瓷袭示额辨调试或声嘲髂息。程语义势析黠 记录2 0 种特嫌标识的变攘都袋承为 n o t e 类型，它只存在于中闻代鹦过程 孛，哥豁纯簿饶纯黪法、据嵩据撼效率，辍怒不教汇编f 褥垒簸。 ( 2 ) 边酌确议 控制流豳中，“蠢向边”能够瀵楚地反映穰序的控谨4 溅及数据淤控制溅 熬变纯擦狴，靛会鏊本旋魏偿慧瓣辩可敬遴行数据流瓣分轿。 g c c 饩纯器澍“商海边”的确认是穗识粼备基零块辩遴行的。掇搽基零 块的出口语句种类进行判断，淤蛰数据的流向熄立綦零块母基本块，或者基 本块与标号乏蠲的避辫关系。箕梅遗愿剿翔潮2 9 瑟瑟。 ；：；篁鎏玉瑟奎兰黧圭耋堡! 坚；。；： 如口语甸种类建立远的粪型遗的谭臻 。袤”蒜转基率袭一辣弩 对骧释矢量考簧的穗 基堆块列韧始他中被迫使甩酌标号 魏转 计算辨转 基本挟呻标号 瓣连。藏基奉浃舞是壤棒号瓣进 语句 返圆踺转基奉块呻纂车块出琏逸 熹搏琥，蔫箨 跳转 基攀块呻橼号 纂率块到它戢转剜的罄车块的婢 蔼掰当燕淫焉语奄对，撩幂它舞茸弱迷 锤甸 谔赠艟嚣奉曩跃异常控耪器，喜控裁异壹异霉 霰舞 氇畦转异多筹萋奉块呻橼号对。耩瓣一十港趣都霹娃鼙选蓊辩 步肆 常 异常控制器，憾建基率块弼罐个控 罄魏饕标号逸 整2 。9g c c 审有淘边瓣橡造蔗粼 ( 3 ) 循环的识别 g c c 饶纯器在进行循环确试对，采用了一种 e 鞍巧妙的方法。语义处理 时生或了鞘个重要麴探记，键最了褥环黪嚣始、锤堇 ：瓣终疰、德繇继续帮矮 环的外提点，在r t l 中分别表示为n o t e 必s nl o o pb e g ，n o t ei n s n l o o p _ e n d ，n o t ei n s n _ l o o p _ c o n t ，n o t ei n s n _ l 0 0 p v t o p 。铡 翅齐t t a - f s o 。中熬赞c 蠢骂找瓣及英对应翡酣我码，可示意毪缝袭暴为： 8 q 占涮 赫o = 1 l i , i i f f , i + + ) ：。? 。：翟篙鎏篆黧娆螂 o 譬令n o t e i n s n _ l o o p _ b e g 、s i 州 j + + ；一_ 一s 1 一 s 2 ，内 t l ：t l + l ：二$ 2 。 n o t ei n s n _ i a ，o p _ c o n t j u r n p r f l l n 0 1 r e j n s n _ l o o pf a n t ) 优化器对r t l 进行扫描，如果发现任何个属性，则将其携带的信息记 录予据液静数据结构孛，丽属穗名率身不簿记录，嚣为它 j 不参与汇编代稻 瓣生成。热巢遇到特殊媾嚣，姥懿嵌套循环、冒被其它函数蹒转裂静标号等， j 藏们会干扰循环的正常控制流，都舞使之无效。 2 。2 4 数错流分析技术 g c c 优化器要收集豫个程芹范国内的各种数据信息，进行全周优化和循 哈尔滨工程大学硕士学位论文 环优化。g c c 优化器数据流分析的实质就是对所使用的寄存器中值的生存情 况的跟踪与记录，比如，量的定值、引用信息。其功能主要由初始化模块、 自定义模块、结束模块三个模块完成。这三个模块被g c c 中的两大优化部分 中的六个功能模块调用，如图2 1 0 所示。 l 公共子表达式的物捌循环优化，基本块 l 删酴、重载后寄存铡 的优化 i 公共于表达式的喇 i 除、指令重排。局州 l 寄存器分配j 图2 1 0 数据流分析模块调用图 g c c 在进行数据流分析之前，定义了可以自动增加或者减少的全局寄存 器空间，寄存器中的存放值是各个模块的主要操作对象。每次数据流分析之 前，先调用初始化模块，后面紧跟自定义模块，而结束模块是在整个优化部 分结束后才调用一次。初始化模块的功能是：遍历当前r t l 的代码，找到所 有可能包含地址的寄存器，如堆栈、框架、参数指针和参数寄存器等，准确 且无重复地放入全局寄存器空间中。自定义模块是针对各个优化部分而言的， 每种优化都要根据具体需要和时机提取不同的数据流，定制自己的数据流分 析过程。比如，指令重排就需要寄存器依赖、内存依赖、当前活跃失效的 寄存器等信息，在它的自定义模块中，只会跟踪、提取、处理和这些信息有 关的数据，其它不做考虑。结束模块的工作就是要在所有数据使用完毕以后， 把全局寄存器空间释放掉，以节省空间。 根据g c c 优化器的优化策略，循环优化是一个功能整体，因此在图2 1 0 中它调用了全部三个模块，获取循环展开、强度削弱等需要的数据流信息。 基本块优化也是一个功能整体，而指令重排和局部寄存器的分配都是基于基 本块内部的，属于基本块优化的一部分，但是它们进行优化的时候仍然需要 啥尔滨工程大学硕士学位论文 最新的全部寄存器信息，所以都分别调用了初始化模块和自定义模块，结束 模块则是要等所有基本块的优化处理结束了再统一调用。公共子表达式的物 理删除和重载后寄存器公共子表达式的删除不属于任何功能整体，它们对代 码是即时的、局部的处理，是基于当前状态的，它们处理的结果就是为下一 次优化做准备的，所以不用调用结束模块。 g c c 中有很多关于程序的变量、值和过程使用的数据流信息：表达式是 否可以重用f 变成公共予表达式1 ，变量在哪里定义，是否改变，何时改变或 一直不变，在哪里使用，过程是否调用等。它们都可以通过自定义模块的合 理组织与安排，逐一确定下来，完成数据流分析，配合功能函数实现各种不 同的优化方法z 0 1 1 2 t 】。 2 3 本章小结 本章概述了g c c 的优化体系以及优化器的主要特点，进而从优化器的 优化策略、g c c 的中间语言、控制流技术以及数据流技术等方面对优化器的 主要特点进行了具体的阐述。 通过对本章内容的研究，概览了g c c 优化的总体结构，进而将研究g c c 优化的重点放到对g c c 优化器的研究上来。 ； 墼鎏三垒：筌垄垒圣兰蝥；一一；i 第3 章g c o 优化编译技术研究 这一章对g c c 铙诧器期戳详细遣舟绍。首壳介缀往纯器莱趱的多种倪 化编译技术的优化机理m 1 1 2 2 ，然后介绍优化器是如何将这些技术组织应用于 其工作流程中的。 3 1g o c 优化编译技术的优化机理 g c c 在r t l 士骰了大量的常窥撬纯璇及与r i s c 缋梅有关翡谯诬工作。 由于与机器有关的优化均能在机器描述的引导下进行，因此g c c 的中间代 码级优化已具有针对目标机器特点的优化功能。这些优化包括：转移优化、 公共予袋这式捌豫、疆巧往纯、 令舞并、骞存器分裁、延迟分支、褥嚣袋 开和指令调度等优化。诚然，途些优化功能只有带优化选项进行编辑时，才 能执行。 ( ) 转罄甓戴 转穆优化完成的功能为删除不可到达代码和不使用的标号 删除无操作 的移动( 如转向后续指令的转移) ；优化无条件转移之间的转移和到无条件转 移静转穆；交叉转移逶霉莰奁凝舞辞段( r e l o a d 之蓐，f m a t 之砉蓼) 霹选建被 执行。 ( 2 ) 公共子表i 鑫式删除 该饶拖的恩慧怒攘素函鼗癌豹r t l 袋羁，记录糖嚣篷嚣表迭蔑，荠爱最 小计算擞的等价表遮式替换这然同值表达斌。当控制路径发生归并时，不可 能跟踪全部的不同路径。因此，每当遇到标号时将遗忘被记录的畿达式，而 局部公絮子表达式秘除( c s e e ) 只在一个麓本袭疼逮行，全嚣公筵予表达式 删除( g c s e c ) 在基本块间进行，此处的基本块不同于数据流分析和寄存器归并 使用的基本块。 ( 3 ) 锈骂钱豫 循环优化是将循环内不变的计算移出循环