（计算机系统结构专业论文）嵌入式c编译器优化技术的研究与实现.pdf

摘要 摘要 优化功能在编译器设计中是至关重要的，编译器优化分为基于中间代码的 与机器无关的优化和基于目标代码的与机器相关的优化。本论文针对一款1 6 位 嵌入式c p u 系统c 编译器的设计，分析了原编译器设计中存在的优化功能缺陷 和不足，根据这款1 6 位嵌入式c p u 系统c 编译器的体系结构，提出了针对特 殊f o r 语句和基于d a g 森林表示中间代码的循环不变表达式外提的循环优化方 案；在分析目标机体系结构的基础上，为最大限度的利用目标机特性，提出了 针对目标代码的可扩展模板的窥孔优化方案。文中还介绍了这两种优化方案的 实现方法，并针对编程语句，将优化前后的代码量和执行性能进行了比较与分 析。 关键字：中间代码循环优化目标代码窥孔优化 a b s t r a c t o p l t i m i z a t i o n a lf u n c t i o n sa l e c r u c i a lt oc o m p i l e rd e s i g n g e n e r a l l y , c o m p i l e r o p t i i i l i z a t i o n d i v i d e si n t o m a c h i n e i n d e p e n d e n to p t i m i z a t i o n b a s e do nt h e i n t e r l a n g u a g e a n dm a c h i n e d e p e n d e n to p t i m i z a t i o n b a s e do i l t h eo b j e c tc o d e a c c o r d i n gt o a16 b i te m b e d d e dc p us y s t e mcc o m p i l e rd e s i g n ，t h i sp 印e r a n a l y z e so p t i m i z a t i o n a l f u n c t i o n sd e f i c i e n c i e s a n ds h o r t c o m i n g si no n g m a i c o h l p i l e rd e s i g n a c c o r d i n g t ot h i s16 - b i te m b e d d e dc p us y s t e mcc o m p i l e r a r c l l i t e c t u r e t h ep a p e rp u t sf o r w a r dl o o po p t i m i z a t i o ns c h e m ea b o u ts p e c i a l t o r s t a ：t e m e n ta n dl o o p i n v a r i a n te x p r e s s i o n m o t i o nd e s i g n p r o p o s a lb a s e do nt h e i n t e r l a n g u a g ee x p r e s s e db yt h ed a g f o r e s t m e a n w h i l e ，i no r d e rt om a x i m i z et h e b e n e f i t so ft h et a r g e tm a c h i n ec h a r a c t e r i s t i c s ，t h i sp a p e rp u t sf o r w a r dt h ep e e p n o l e 讲) t i m i z a t i o ns c h e m eb a s e do ne x t e n s i b l ep a t t e r n t h ep a p e ra l s o i n t r o d u c e st h e i m p l e m e n t a t i o n so ft h e t w oo p t i m i z a t i o nm e t h o d ，a n da i m i n g a tp r o g r 舢n g p r o b l e m s ，c o m p a r e sa n da n a l y z e st h ea m o u n to fc o d ea n d t h ep e r f o r m a n c eo fc o d e b e t w e e nb e f o r et h eo p t i m i z a t i o n a li m p l e m e n t a t i o na n d a f t e r k e y w o r d s ： i n t e r l a n g u a g eo b j e c tc o d el o o po p t i m i z a t i o n p e e p h o l eo p t i m i z a t i o n i i 图目录 图目录 图2 1中间代码优化结构7 图3 11 6 位嵌入式c p u 系统c 编译器体系结构1 3 图3 2 * p t r = 5 3 的抽象语法树1 4 图3 3 * p t r = 5 3 的d a g 节点1 5 图3 4 后端模块关系图2 l 图4 11 6 位嵌入式c p u 系统c 编译器优化方案图2 7 图4 2 特殊f o r 语句优化系统框架图3 0 图4 31 6 位嵌入式c p u 系统c 编译器特殊f o r 语句的实现流程图3 3 图4 4 基于d a g 代码表循环不变表达式外提优化实现流程4 1 图4 5 活动变量列表建立流程图4 3 图4 6 循环不变表达式的外提森林形成流程图4 6 图4 7 外提森林外提流程图4 7 图5 1 模板使用示意图5 8 图5 2 基于可扩张模板窥孔优化系统结构图6 2 图5 3 基于可扩张模板窥孔优化的优化流程图6 4 图5 4 窥孔优化各函数之间调用关系6 6 v i 表目录 表目录 表3 1函数信息与中间代码对应关系表2 0 表3 2 后端接口功能表2 1 表3 3目标机寄存器的介绍2 4 表4 11 6 位嵌入式c p u 系统c 编译器语句处理表3 l 表4 2 活动变量列表建立的函数功能描述4 5 表4 3 循环不变表达式外提的相关函数及其功能描述4 8 表4 4 特殊f o r 语句优化测试结果5 2 表5 1 模板定义的通配符形式及意义5 8 表5 2 窥孔优化涉及的主要函数及其功能6 5 v i i 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：孪海丰 知t 弓年f 月瑚日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年 月 日 各密级的最长保密年限及书写格式规定如下： 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作 所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含 任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉 及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学 位论文原创性声明的法律责任由本人承担。 学位论文作者签名：蔷洛半 功g 年f 月2 9 日 第一章绪论 第一章绪论 第一节嵌入式c p u 系统与编译器 随着计算机技术的高速发展，嵌入式系统已经在工业控制、信息家电、办 公自动化、移动通信、仪器仪表等各个领域得到了广泛应用。随着国内外各种 嵌入式产品的进一步开发和推广，嵌入式技术和人们的生活结合的越来越紧密。 嵌入式系统是以应用为中心，以计算机技术为基础，并且软、硬件系统可 随系统需求进行裁剪，可满足应用系统对功能、可靠性、成本、体积、功耗有 严格要求的专用计算机系统【2 们。一般嵌入式系统包括硬件和软件两部分。硬件 部分主要由嵌入式微处理器和外围硬件设备组成。软件部分包括操作系统软件 和应用程序。在一些嵌入式系统中系统软件和应用程序是绑定在一起的，这些 程序直接在嵌入式系统芯片上运行，以提高系统的执行效率。因此，在嵌入式 系统中高级语言编译器要根据具体嵌入式c p u 系统的特点进行设计和优化。 1 1 1 嵌入式c p u 系统特点 嵌入式系统的核心是嵌入式c p u 。嵌入式c p u 一般具备以下几个特点： 1 ) 对实时多任务有很强的支持能力，能完成多任务并具有快速的中断响应 时间，从而使内部的代码和实时内核的执行时间减少到最低限度。 2 ) 具有功能很强的存储区保护功能。这是由于嵌入式系统的软件结构己模 块化，而为了避免在软件模块之间出现错误的交叉作用，设计了强大的存储区 保护功能，这样做既保证了程序的有效运行，同时也有利于系统的诊断与测试 分析。 3 ) 具有良好的可扩展的系统结构，配合高效率的开发系统，能以最快速度 开发出满足应用需要的高性能嵌入式微处理器系统。 4 ) 满足低功耗处理需求，尤其是用于便携式无线移动计算和移动通信设备 中靠电池供电的嵌入式系统更是如此。比如有的系统功耗需求只有m w 甚至州 级。 1 6 位嵌入式c p u 是我们实验室自行设计和研发的一款嵌入式r i s c 微处理 】 第一章绪论 器，该c p u 除了具有通常嵌入式c p u 的一般特征外，还具有以下特点： 1 ) 采用典型的哈佛体系结构。 2 ) 具有简单高效的指令系统、固定指令格式，大多数指令在单周期内完成。 3 ) 采用l o a d s t o r e 结构。因为访问存储器指令所需要的时间比较长， 在目标代码中要尽量减少使用这类指令。 4 ) 硬布线控制逻辑，使得大多数指令在单周期内执行完成，以减少为程序 技术中的指令解释开销。 5 ) 包含丰富的寄存器，其中供用户使用的寄存器多达1 2 8 个。 6 ) 具有很强的中断处理能力，能够快速有效地处理系统和外部触发的各种 中断请求。 7 ) 具有方便灵活的系统扩展能力，可用系统软件和专用控制程序方便地对 系统资源( 如外部接口配置，系统专用处理模块等) 进行配置。 该1 6 位嵌入式c p u 具备的这些特点使其具有高效性、实时性，可以应用在 很多嵌入式领域中。+ 1 1 2 嵌入式系统对高级语言的要求 嵌入式应用软件是实现嵌入式系统功能的关键。随着需要解决的问题越来 越复杂，特别是嵌入式操作系统的出现，传统的只能针对特定的体系结构和处 理器而开发的纯汇编语言和机器语言越来越应对不了今天系统更加复杂的应用 需求。而高级语言因其具有良好的通用性和丰富的软件支持，可移植性好、易 于维护等特点受到广泛青睐。同时因高级语言环境与具体嵌入式系统c p u 的体 系结构无直接关联，在完成应用软件设计时不必过分考虑c p u 结构和硬件体系 特征，从而可大大提高了嵌入式应用系统的开发速度。随着嵌入式系统应用范 围的不断扩大和嵌入式实时操作系统r t o s ( r e a lt i m eo p e r a t i n gs y s t e m ) 的广泛 使用，为其引入高级语言和相应的嵌入式编译器是嵌入式系统发展的必然趋势。 另外，高级语言的引用，使得嵌入式应用开发人员得以从枯燥的汇编语言 开发方式中解放出来，同时也促使嵌入式有了更为广阔的应用空间。 2 第一章绪论 1 1 3 嵌入式系统对编译器优化的要求 由于嵌入式系统对于硬件资源方面的敏感性，使得嵌入式软件的设计对时 间和空间都有严格限制。为了生成高质量的目标代码，更好的为嵌入式系统服 务，嵌入式系统中编译器的优化工作显得更为重要。 区别于一般计算机中的高级语言编译器，嵌入式系统中的编译器要提供专 门的优化功能，以提高目标代码执行效率。一般来说，优秀的嵌入式系统编译 器生成的代码长度和执行时间仅比以汇编语言编写的同样功能程序长5 0 0 - , 2 0 ， 而这个效率差别，完全可以由现代微控制器的高速度、大存储器空间以及产品 提前进入市场的优势来弥补。编译质量的不同，是区别嵌入式编译器工具的重 要指标【l o j 。 优化的目的是最大限度的提升目标代码的性能，最大限度的利用处理器的 性能，如加大寄存器利用率，减少寄存器溢出，将机器编译的目标代码质量靠 近人工编写的目标代码质量。所以对嵌入式编译器进行优化研究是非常有价值 的。 第二节嵌入式c p u 系统c 编译器基本功能 为了使我们的1 6 位嵌入式c p u 系统适应嵌入式发展的潮流，拥有高级语言 开发环境，我们为其成功开发了一款嵌入式c 编译器一1 6 位嵌入式c p u 系统 c 编译器。该编译器具有以下基本功能： ( 1 ) 能够出色的完成标准c 程序的编译工作。 ( 2 ) 提供了通用的字符串操作开发库。 ( 3 ) 提供了建立在i t c o s i i 等小型操作系统上的标准输入输出、文件管理、 内存管理等和操作系统密切相关的开发库。 ( 4 ) 提供简单的调试功能。 由于该编译器在优化方面做的工作不多，使的编译生成的目标代码质量不 够高。而这一点对其在嵌入式方面应用有着负面的影响，在一定程度上制约了 系统应用与推广。本文主要针对该编译器的优化问题，进行分析和研究，提出 优化改进方案，并对这款嵌入式c p u 系统c 编译器进行优化设计及代码优化后 检测。 3 第一章绪论 第三节本文研究的主要内容 本论文对我们自主研发的1 6 位嵌入式c p u 系统开发工具链中的c 编译器 进行优化方面的研究。本论文主要从对c 语言源程序中语句分析优化和c 编译 器编译后的汇编语言程序分析优化两个层面对优化问题进行讨论。特别重点讨 论了在c 语言程序优化技术中较为重要的循环优化问题和讨论c 编译后对汇编 程序中一种更方便、更有效的窥孔优化可扩展模板的窥孔优化技术问题。 在c 语言源程序优化分析层面，主要从特殊f o r 语句、循环不变表达式外提 两个方面对循环优化进行研究。这里特殊f o r 语句指的是能根据其f o r 语句的基 本信息判断出f o r 语句的执行情况( 包括不能确定循环次数、至少执行一次循环 和一次循环也不执行三种情况) ，讨论如何根据这三种不同情况来生成不同的目 标代码从而达到优化目的方法。循环不变表达式外提的目的是，将循环中不随 循环发生改变的表达式放到循环外面执行从而减少执行时间。本文研究和分析 了循环不变表达式在何种情况下能够外提到循环之外执行的条件，分析和总结 了循环不变代码外提后对中间代码和寄存器分配与释放带来的影响，并讨论如 何消除这种影响的方法，从而实现循环不变表达式外提。 在编译后对汇编语言层面，主要是针对我们的1 6 位嵌入式c p u 系统c 编 译器中已实现的优化基于模板的窥孔优化技术进行分析研究，在讨论这种 优化的实现理论和特色的同时指出存在的不足，提出实现一种优化效果更佳、 可扩张性更强、使用更方便的窥孔优化基于可扩展模板的窥孔优化技术。 同时，文章还介绍了这两种优化方案在我们1 6 位嵌入式c p u 系统c 编译 器中的实现方法，并通过对针对性的测试用例优化前后的代码量和执行性能进 行比较与分析，进而佐证本优化研究给目标代码质量带来的程序代码质量的提 高和程序运行效率的提高。 第四节论文的组织结构 本论文将主要通过以下几章讨论针对嵌入式c p u 系统c 编译器优化技术的 研究与实现。 第二章简要介绍了当前常用的c 编译器优化技术，并说明了各种优化技术 的优化内容。 4 第一章绪论 第三章介绍了我们已实现的嵌入式c p u 系统c 编译器的体系结构。分别从 前端、中间代码表示和后端代码生成三个方面进行了介绍，在介绍的同时对该 编译器已实现的优化技术进行分析，提出了其中的不足和改进方法。 第四章详细研究了循环优化在1 6 嵌入式c p u 系统c 编译器中的实现方案。 论文研究实现了特殊形式f o r 语句的优化，同时提出并实现了基于d a g 森林形 式表示中间代码的循环不变表达式外提优化方案。最后通过对比编译器优化前 后生成的目标代码说明了优化效果。 第五章介绍对编译后汇编语言程序先前做的基于模板的窥孔优化技术特 点，提出并实现了一种效果更佳、使用方便、可扩张性强的窥孔优化一可扩展 模板的窥孔优化，并通过具体实例展示了这种窥孔优化的给目标代码质量带来 的提高。 第六章总结了我们所研究的优化工作，指出1 6 位嵌入式c p u 系统c 编译 器在优化方面还存在那些缺陷，并提出了进一步改进的思路。 5 第二章常用c 编译器优化技术介绍 第二章常用c 编译器优化技术介绍 代码优化是指在保持实现功能不变的情况下，通过对程序实施各种等价变 换，从而生成更有效的目标代码。代码优化的目的是为了提高程序效率，主要 通过两个方面来体现【2 2 】： l 、减少目标代码的执行时间。 2 、减少目标代码占用的存储空间。 代码优化技术分为两大类：一类是机器无关的代码优化，涉及和程序设计 语言相关的部分，这部分优化工作主要在代码分析阶段和生成中间代码阶段完 成；另一类是与机器相关的代码优化，这部分涉及和机器特性相关的内容，是 在生成目标代码阶段完成。 机器无关的代码优化主要包括口3 】： 1 、局部优化，在程序的基本块范围内进行。一个基本块是指程序中一组顺 序执行的指令序列，其中只有一个入口( 第一个指令) 和一个出口( 最后一个指令) 。 2 、循环优化，在整个循环范围内进行，由于循环执行的重复性，使得对循 环中哪怕很小的一点改进都可能在很大程度上提高代码执行效率。循环优化历 来都是代码优化的重点关注内容。 3 、全局优化，在整个程序范围内进行。显然循环优化也属于全局优化的内 容。 机器相关的代码优化主要包括： 1 、寄存器分配中的优化。即如何管理和使用各种寄存器，合理利用寄存器 资源，把最活跃的变量放入寄存器中，尽量避免寄存器溢出。 2 、窥孑l 优化。在局部范围内对目标代码进行优化，不断用高效率的代码替 换低效率的代码。 从编译过程来说，优化将在中间代码和目标代码两方面来分别进行。显然 中间代码适合与机器无关代码的优化，而目标代码和机器的特性有着紧密的联 系，这部分适合机器相关的代码优化。 6 第二章常用c 编译器优化技术介绍 第一节与机器无关优化技术介绍 2 1 1中间代码优化介绍口1 中间代码优化阶段由三部分组成，分别称为控制流分析、数据流分析和代 码变换。图2 1 显示了中间代码的优化结构。 图2 1 中间代码优化结构 控制流分析就是对代码的所有可执行路径进行分析，并将分析结果记录表 示出来，通常使用流图来描述所有的可执行路径。控制流分析一般为两个步骤， 首先划分基本块，然后建立流图。 数据流分析阶段收集数据项定义和使用方面的信息，这些信息包括活跃变 量和可用表达式等数据流信息【3 】。同时还会检测循环不变表达式和已被计算出的 表达式等信息。由于数据分析可以获得流图中基本块之间的数据流信息，因此 可以进行循环优化和各种全局优化。 代码变换是对中间代码的表示进行逐个判断，在基本块范围能进行局部优 化，同时基于控制流和数据流得到的信息进行更大范围的代码替换，从而实现 循环的优化和其他全局优化。 2 1 2 局部优化策略 局部优化是指局限于基本块范围内的优化。对于给定的程序，我们可以把 它划分成一系列的基本块，然后在各个基本块内分别进行优化口2 1 。局部优化通 7 第二章常用c 编译器优化技术介绍 常包括如下策略： 1 、常数表达式计算( 或称为常数折叠) 【l 】 常数表达式计算，指的是在编译时计算其操作数已知是常数的表达式，并 用计算结果替换该表达式。如对于表达式1 + 2 的引用，可以用其计算结果3 代 替。 2 、删除局部公共子表达式 公共子表达式是指那些在一条已知路径上至少执行两次以上的计算，并且 在这两个计算之间该表达式的操作数没有发生变化。那么当下次用到该表达式 时，就可以直接使用上次的计算结果，而不需要对该表达式再计算一次。 公共子表达式消除的思想是搜索函数内部的代码，记录相同值的表达式， 并用最小计算量的等价表达式以替换这些同值表达式。第一次计算出表达式的 值并放入寄存器中，当下次使用的时候直接读取寄存器即可。 当这种优化局限于基本块中进行时，就称为删除局部公共子表达式优化。 3 、消减计算强度 这种优化方法是指用运算速度快的计算代替运算速度较慢的计算。通常指 用加减法计算来替换乘除法运算。 4 、删除无用代码 无用代码指的是那些计算结果决不被引用的代码。无用代码主要是由一些 优化变换产生的，它们在执行中永远不会得到引用，删除无用代码优化就是删 除这些不被引用的代码。 2 1 3 循环优化策蚪2 2 】 循环优化是在整个循环范围内进行的优化，一个循环可能包括若干个基本 块。在i t 界，循环有“9 0 一1 0 规则之说，即9 0 的时间花费在1 0 的代码上。 因此，循环优化的收效可能是最高的，尤其是对内循环的优化更是如此。哪怕 对循环做小小的改进都会收到很好的效果f 8 】。所以循环历来是优化的重点目标。 循环优化主要包括如下策略【2 4 】： 1 、循环不变表达式外提 这种优化是效果非常明显的循环优化，它的主要思想是将循环体中那些不 随循环的重复而值发生变化的表达式放在循环体外面来执行。这样可以使原来 8 第二章常用c 编译器优化技术介绍 在循环中的那些将被多次执行的不变表达式将只被执行一次。 2 、归纳变量删除 在循环中如果变量i 的值随着循环的每次重复都是增加或减少某个固定的 常量，则称变量i 为循环的归纳变量【l 】。 如果一个循环中包含多个这样的归纳变量，可以通过用归纳变量相关的计 算来代替归纳变量的计算，从而使归纳变量数减少到很少的几个甚至一个。 3 、消减计算强度 对于循环来说，这种优化主要应用于下标数组的计算中【l 】。 从上面的论述我们可以知道，循环优化在优化模块中占有极其重要的位置， 而原1 6 位嵌入式c p u 系统的c 编译器却没有对循环进行任何优化。为了弥补 这个缺陷，本次将对循环优化进行深入研究。这是本文讨论的重点，将在第四 章中给出详细论述。 2 1 4 全局优化策略 全局优化是将整个程序作为优化对象，对程序进行全面分析，并采用全局 信息进行大范围优化。全局优化包括如下策略： 1 、删除公共子表达式 在全局范围内删除公共子表达式，而局部公共子表达式删除是把公共子表 达式的范围限制在一个基本块中。 2 、条件删除 对于恒等或恒不等的条件进行删除处理，如i f ( 1 ) 为恒等条件而i f ( o ) 为恒不 等条件，对于恒等条件可以删除条件判断，而恒不等则删除所有其条件语句内 容。 3 、删除多余赋值 多余赋值指类似于x = y ；y ；这样的赋值，第二个赋值是多余的。这种优化 就是通过对语句的分析，实现删除这样的多余赋值语句。 4 、删除无用代码 在全局范围内删除无用代码。 9 第二章常用c 编译器优化技术介绍 第二节与机器相关优化技术介绍 2 2 1 寄存器分配 如何利用有限的寄存器资源生成高效的目标代码是寄存器分配的关键。寄 存器分配的任务是使生成的目标代码应尽可能少地访问主存，尽可能的把使用 频率高的变量放入寄存器中【1 9 】。 一般来说寄存器分配包括两部分：一是分配，决定哪些值占用寄存器；二 是指派，为每个值指派某个特定寄存器【钔。 通常寄存器分为两类【2 】：全局寄存器和临时寄存器。第一类就是我们所说的 寄存器变量，寄存器分配程序通常会按照变量的使用次数来决定那个变量放在 寄存器中存储。由于维护寄存器的代价昂贵，全局寄存器的使用限制在函数内， 即只有局部变量才能存储在全局寄存器中。这和c 语言中寄存器变量的使用范 围一致。第二类称为临时寄存器或易失寄存器。这种寄存器使用在基本块中存 储临时变量和中间变量。这些变量只在基本块中使用，寄存器分配程序只在需 要临时寄存器时才进行分配。为了避免寄存器溢出，通常临时变量不再被使用 后，会立即释放此寄存器。 寄存器溢出是指当需要寄存器保存值时，而寄存器分配程序已分配完了所 有寄存器，没有寄存器可用了。此时需把某个寄存器中的值放入存储器中，然 后把此寄存器分配给其他变量，当再需要此值时会重新读取到寄存器中，这要 花费昂贵的代价，所以临时寄存器使用完毕后要及时释放。 2 2 2 窥孑l 优化介绍 窥孔优化【l1 1 刀( p e e p h o l eo p t i m i z a t i o n ) 主要是针对目标代码( 有时也可应用于 中间代码【l5 】) 进行局部扫描，进而进行优化处理的一种技术。一般它只考虑目 标代码中一段很短的指令序列，如果发现符合要求的代码序列就用更快更短的 代码序列替换。这些被检查的指令短序列被称为窥孔，窥孔优化是对目标代码 进行局部改进的简单而有效的技术，它只考虑目标代码中很短的指令序列，一 般为连续的几条指令。这种优化的效果很大程度取决于考虑的代码条数多少上， 代码条数太少会漏掉一些可以优化的语句，代码条数太多需要维护的信息太多， 1 0 第二章常用c 编译器优化技术介绍 浪费掉太长的时间。一般采用一个基本语句块作为一个窥孔是比较合适的做法。 窥孔优化有以下几类典型的优化内容： 窥孔优化有一下几类典型的优化【l l 】： 1 、多余的存取指令的删除 如生成指令中包含： 爹翁”。粕誓产移繁鬻燃缪缈嬲燃鬻燃缫鬻鳓嬲黝缫燃缫缫缪獬燃黝嘲 琵浚渤l 携飘；溺貔巍瓣彘德荔戮滋貔貔渤戮缀瓣彩燧忿滚锄簇渤凌施兹糍锄缀缀貔貔渤缀缀施貔锄赫黝施级黝缀磊i 鬓磊簇 显然，后一条指令是不必要的，删除这样的指令可以从时间和空间上都取 得好的效果，而且不会影响程序的执行结果。 2 、消除不可达代码 在生成的指令中，任何无条件分支语句后面出现的无标号语句均可删除， 因为它们永远不会被执行到。 3 、控制流优化 在生成指令中若包含从一个g o t o 语句跳转到另一个g o t o 语句时，则第一个 g o t o 语句可改为直接跳到第二个g o t o 的目的地；当消除所有非直接g o t o 后，消 除标号后跟g o t o 的句子。 4 、代数化简 利用代数恒等式进行等价变换。常用方法有常量拆叠、代数简化和强度削 减。 5 、特殊指令的使用 当目标机指令包含有高效实现某些专门操作的指令时，如果能找出允许使 用这些指令的情况并替换，将会改进目标代码的执行效率。 窥孔优化具有每次优化可能引起新的优化机会，如果要作出最大的优化( 不 考虑编译的时间) ，可能需要对目标代码进行重复扫描并进行窥孔优化 7 1 。 第三章1 6 位嵌入式芯片c 编译器的实现介绍 第三章原c 编译器实现及优化技术介绍 第一节c 编译器实现技术途径 在第一章中我们谈到，为了使一款1 6 位嵌入式c p u 系统拥有高级语言开发 能力，我们成功开发了一款基于该嵌入式c p u 的c 编译器1 6 位嵌入式c p u 系统c 编译器。该编译器主要是通过分析l c c 架构，采用了其前端实现结构并 依据我们目标机的特色重写其后端来实现的【9 】。 l c c 是一款可重定向的a n s ic 编译器【1 32 0 1 ，其主要特点是与目标机无关的 前端将c 源程序的转换成中间结构传递给后端，由后端把这些结构翻译成目标 机上的汇编代码。而其后端是可重定向，采用规定的机器描述方式来描述不同 的后端芯片就能为各芯片生成特定的目标代码。 我们的c 编译器就是通过对l c c 后端代码生成器按照我们1 6 位芯片的特 色进行重新定向完成的。我们主要从以下三方面进行了设计【2 0 j ： 一、应用程序二进制接口 编译器的应用程序二进制接口( a p p l i c a t i o nb i n a r yi n t e r f a c e 简称a b i ) 本质 上是由它的体系结构确定的。a b i 包含了与目标机的全部接口信息，比如，c 语 言数据类型如何对应到字节和位，数据类型的存储空间分配，如何调用函数和 如何返回函数值等信息。 只有通过a b i 接口，编译器才能了解目标机是如何完成应用程序的具体操 作，并依照此信息完成编译生成符合要求的目标代码。由于应用程序二进制接 口是直接与目标机的体系结构相关的，因此不同的目标机需要定义不同的接口。 为此，我们根据1 6 位嵌入式c p u 的特色制定了符合其要求的a b i ( 主要是通过 修改c h 中的i n t e r f a c e 结构来实现) 。 二、寄存器使用约定 我们的1 6 位嵌入式c p u 系统提供了多达6 4 个可自由分配的寄存器。为了 合理的使用这些寄存器生成高效的目标代码，我们规定了它们使用范围，同时 为了生成正确的目标代码还制定了一些特殊用途的寄存器。关于这6 4 个寄存器 的具体用途将在3 2 3 中具体介绍。 1 2 第三章1 6 位嵌入式芯片c 编译器的实现介绍 同时l c c 提供的是至多3 2 个寄存器的使用规则，这和我们寄存器数目不符， 为此，我们将对l c c 编译器的寄存器使用规则进行相应的修改，使之符合我们 处理器寄存器的特色。 三、制定目标机的规约规则 l c c 代码生成器根据事先设定的规约规则对d a g 6 ( 关于d a g 论文将在 下节进行介绍) 进行归约、注释，从而生成目标机代码。规约规则是按照一定 的语法规则结合目标机的特性来制定的树文法。后端代码生成器会根据这些规 约规则为每个d a g 选择合适的注释。我们根据目标机特性共设计实现了1 5 5 条 归约规则。 第二节c 编译器实现体系结构 1 6 位嵌入式c p u 系统c 编译器在体系结构上采用传统的前端和后端实现形 式【5 1 。前端完成传统的词法分析、语法分析和语义分析生成分析树，并把分析树 转换成以d a g ( 有向无环图) 森林为核心的中间代码形式。后端则根据d a g 提供的信息，完成寄存器分配、汇编代码生成和汇编代码输出。图3 1 显示了 1 6 位嵌入式c p u 系统c 编译器的体系结构。 c 编译器前端c 编译器后端 | ： 0 j蔓一誊 爹笺 蠹 。i * 0 豫j奄薯 谭雾_ 。鹂j、鸫 荔彰 釜黉： 争i专 瓢j 叠薯： 黪“ 徊j 瀛写 谚 j 一譬 0 i _ 夔i i 器j 纂马 ， 谖j 砖 法一j 法篡 p 鬻 翁。务i 壤i“瓣 一麓 图3 11 6 位嵌入式c p u 系统c 编译器体系结构 为了更好的说明1 6 位嵌入式c p u 系统c 编译器的工作流程，下面将从其 前端编译、中间代码生成和表示及后端实现三个方面进行介绍。 3 2 1前端编译完成工作 前端编译就是完成词法分析、语法分析及语义分析这三个阶段的翻译工作， 1 3 第三章1 6 位嵌入式芯片c 编译器的实现介绍 把c 源代码用中间代码的形式表示出来。 词法分析阶段【4 】：在该阶段词法分析器和扫描器读入源程序，通过分析会产 生语言的基本词法单元单词，单词由单词编码和附加值组成。例如表达式 * p t r = 5 3 包含了5 个单词，对其进行词法分析会被表示成下面的形式，其中备 注是对附加值进行的解释，不是词法分析的产物： 其中单词编码i d 和i c o n 分别表示标识符和常量，单字符单词( 如操作符 和分隔符) 的单词编码为字符本身，其他单词通过预定义的常量作为单词编码， 关键字采用单独的编码与标识符区分开来。 词法分析还会记录每个单词的源坐标，用于标记发生错误的位置及记录符 号的定义点。 语法分析阶段【4 】：语法分析阶段分析词法分析提供的单词序列，确认输入的 是否符合语言的文法规则，并建立输入源程序的内部表示分析树( 抽象语 法树) 。例如根据前面的词法分析的信息会形成如图3 2 所示的抽象语法树： a s g n + i a d d r l + p p t r c n st + i 5 3 图3 2 * p t r = 5 3 的抽象语法树 语义分析阶段【4 】：语义分析阶段分析表达式构成的分析树将其转换中间代码 表示的d a g 节点，并根据表达式的语义对基本块进行划分形成d a g 森林，并 放入中间代码表中。语义分析除了把d a g 森林放入中间代码表外，还把单词的 源坐标、复合语句的开始和结束等信息放入中间代码表。关于中间代码的表示 将在下节进行详细的介绍。图3 3 表示了语法阶段形成的抽象语法树经过语义分 析形成的d a g 。 1 4 第三章 1 6 位嵌入式芯片c 编译器的实现介绍 a s g m 图3 3 * p t r = 5 3 的d a g 节点 编译器前端这部分是针对程序语言的，与目标机器无关。16 位嵌入式c p u 系统c 编译器的这部分实现和编译原理介绍的大致相同，这里就不再多说了。 3 2 2中间代码表示方式 从c 源程序中，我们可以看到程序主要由函数组成。函数又由变量、标号、 常量、操作符和表达式等组成。这些信息经过前端编译后，分别被转换成相应 的形式存储在中间代码表中。中间代码结构是进行与目标机无关优化研究的的 关键，我们将在下章介绍的与目标机无关的循环优化就是在中间代码表基础上 完成的。下面将对中间代码表的主要方面分别进行介绍。 3 2 2 1符号的存储方式 符号是编译器保存信息的基本单位。程序中出现的变量、标号、常量、类 型信息和变量的寄存器分配信息都保存在符号中，同时还要保存变量的作用域 和临时变量的信息。编译器将通过这些信息进行公共子表达式的删除，寄存器 和栈的分配来生成目标代码。 1 6 位嵌入式c p u 系统c 编译器通过定义结构体s y m b o l 来保存这些信息， 下面我们通过其定义来描述各种信息是如何保存的。 1 5 第三章 1 6 位嵌入式芯片c 编译器的实现介绍 i n ts c l a s s ；“”一。；。“。? j j ”? “i ”4 j ? _ 。j “j ”一”? ? 。“9 。j 4 i ；9 。j 枣该域保存的是变鬣、函数、常遂、结构、联台和枚举等类型信息 t y p et y p e ； 枣这个指针用予指翔”同作硝域”内的上个符号，这是个倒链表宰7 s y m b o l u p ； 产标注信息是否为编译器生成的瓶时变鬟零 u n s i g n e dt e m p o r a r y ：1 ； 誊埔予袭示撇期e 内容是否为编译时产生的母1 u n s i g n e dg e n e r a t e d ：1 ； 。 芦用予标识符号是否被定义宰一 、，一。 ” m a s i 秘e d d e f i n e d ：l ；r 。 ： ： 缓。幸标注变量被弓| 用的粗略计数，主要羽予寄存器分配譬， ，7 。l 鬻f l o a t r e f ； _ 一 。 7 ：鬟 黪 ：一， “ 一 ?， 秀 戮，极域包客了一些仅有编译焉端处理使耀豹域，主要保存了寄存器分配程序分配给该贺 錾餐( 定义交鳖和临时变媾) 的寄存器信息。彩，。 ，一 j 7 鬟 甏? x s y m b o lx ；。 。 、。“_ j|+，凑 由上面定义可以看到s y m b o l 结构体包含了一个变量的名称、类型、存储类 型、作用域等信息。这些可以很清楚的表示了一个变量。至于标号和常量也采 用这种形式存储。结构中的其他元素记录了编译器对符号的一些操作，如寄存 器分配、临时变量生成等。 3 2 2 2 d a g 节点表示方式【4 】 上节介绍了常量、变量等在符号中的存储。而由表达式、标号和跳转指令 构成的可执行代码是由d a g 节点来描述的。整个函数体通过构成的d a g 组成 多个d a g 森林来表示。我们的目标代码( 汇编代码) 都是根据其信息生成的。 编译器通过d a g 节点来存储这些信息。 下面介绍下d a g 节点的表示结构及各元素表示的意义： 1 6 第三章1 6 位嵌入式芯片c 编译器的实现介绍 o p 存储节点的d a g 操作符，我们根据操作符来理解节点表达的意义。1 6 位嵌入式c p u 系统c 编译器的d a g 操作符由通用操作符加类型后缀组成。如 表示加法的通用a d d 和表示整型的后缀i 组成a d d i 。此时，当o p = a d d i 时 我们就知道此节点表示两个整数相加。 通用操作符和类型后缀都由枚举变量定义。具体后缀定义如下： d a g 操作符通过枚举来实现，每个d a g 操作数由唯一的一个枚举值表示。 其定义格式如下： 爹霉磊基 巨 貔 - + 缀崩“，施，j 暑。i ； ； 为了可以更好的从操作符中分出其通用操作符和类型后缀。提供了下面两 个宏： 其中o p 是表示操作符类型的枚举值。这两个宏可以帮助我们很好的获得通 用操作符和类型后缀。k i d s 的元素指向操作数的节点。l i n k 指向森林中下一个 d a g 的根。 s y m s 域存放一些d a g 操作也使用一个或两个符号表指针为操作数。后端有 时需要对d a g 节点进行操作，为了保证不对前端的信息作出更改。使用s y m s 1 7 第三章1 6 位嵌入式芯片c 编译器的实现介绍 的第三个元素来符号保存其信息。如给节点分配的寄存器、公共子表达式删除 时生成的临时变量都存储在此元素中。 c o u n t 记录了节点的值被使用或被其他节点引用的次数。只有来自k i d s 的引 用才被计数，来自l i n k 的引用不表示对节点值的使用，不被计数。事实上，l i n k 只对根节点有意义。共享节点是指c o u n t 大于1 的节点，它生成的代码只对节点 计算一次，但是节点的值被使用c o u n t 次。x 域是后端对节点的扩展1 4 j 。 d a g 森林是指d a g 中的根节点通过l i n k 连接在一起形成的。d a g 森林表 示的一个基本块中的所有语句，即一个基本块中的每个语句表示一个d a g ，基 本块所有的语句组成一个d a g 森林。 我们前面介绍了图3 3 是表达式* p t f 5 6 形成的d a g 节点，该节点记录了该 表达式的所有信息。d a g 森林就是把这些d a g 节点通过l i n k 连接在一起的。 表达式通过d a g 节点表示出来，基本块由d a g 森林表示。那么整个函数 该如何表示出来呢? 为了解决这些问题，下面将研究分析中间代码表的生成和 表示，介绍函数的各种信息是如何在中间代码表中表示的。 3 2 2 3 中间代码的表示 编译器前端通过词法分析、语法分析、语义分析把表达式、跳转和标号表 示成d a g 。每个函数的这些d a g 组成相应的d a g 森林将被放在代码表中被串 在一起。代码表代表了函数的代码。这个代码表就是我们的中间代码表，前端 通过分析构造中间代码表，而后端根据中间代码表的信息调用函数为不同的后 端生成对应的目标代码。中间代码表的主要结构如下： 产 枣 。 黔： u ； 7 。、 ，一， ，t ? i j - p 。秀 遂庞锄磊；蹴缀荔磊缓女荔荔缓缀黝褫缀磊女蠢缀镢黧簇嚣燃编虢缴女褫象基磊荔自搋自渤凌貔象妊女貔；鬃渤囊荔渤缝荔锄i 燃篇 k i n d 标识其对应的代码表的类型，由定义可以知道代码码一共可以由1 0 种 类型，每种类型表示不同的意义，用于不同的方面。 1 8 黟粉缀戮缀黔笏黔荔缴僦缈艮 第三章1 6 位嵌入式芯片c 编译器的实现介绍 s t a r t 域标识代码表的开始，一个中间代码表对应唯一的s t a r t 域。 除了s t a r t 以外，代码表的每个类型都对应一个u 域值。下面将对代码表的 类型和其对应的于的意义进行一一介绍。 b l o c k b e g 和b l o c k e n d 入口标示复合语句的边界。 b l o c k b e g 对应u 域的b l o c k ，存储了编译复合语句所需的信息。由于再循环 代码外提过程中会对该域做必要的更改，这里先介绍下其各项表示的意义。 l e v e l 表示的是与代码块相关的作用域值，l o c a l s 是一个以n u l l 结尾的数组， 该数组中存放了代码块中声明的局部变量的符号表指针。x 域表示代码块在编译 后端中的e n v 值，包括代码块开始时的栈偏移和寄存器的使用情况。t a b l e 域是 作为调试用的。 b l o c k e n d 对应u 域的c o d eb e g i n 指向与之匹配的b l o c k b e g 。这样每个复合 语句由b l o c k b e g 开始，由其对应的b l o c k e n d 结束。 l o c a l 和a d d r e s s 标示必须通过l o c a l 和a d d r e s s 接口函数来通知编译后端的 局部变量。l o c a l 对应u 域的s y m b o lv a r 。当局部变量没被定义过，会调用相关 函数在代码码中为起添加一个l o c a l 入口。v a t 则指向这个变量。最常出现的就 是生成临时变量。a d d r e s s 对应u 域的a d d r ，记录了g e n c o d e 调用接口函数a d d r e s s 传递的必要信息。 d e f p o i n t 入口定义了执行点的位置，对应于u 域的p o i n t 。它主要是用于调 试器设