编译程序的构造

编译程序的构造主要有三条途径：用某种程序语言书写编译程序通过LEX、YACC等工具进行自动构造通过现有的编译基础设施进行改造和组装13.1编译程序的书写一.编译程序的书写语言与T型图编译程序的T型图，如图13.1所示：

如果一个编译程序的源语言是X，目标语言是Y，书写语言是Z，把该编译程序记作CZXY，那么用T型图表示如图

13.2所示：二.编译程序的自展技术自展思想：先用目标机的汇编语言或机器语言书写源语言的一个子集的编译程序,然后再用这个子集作为书写语言,实现源语言的编译程序。如果把这个过程根据情况分成若干步,像滚雪球一样直到生成预计源语言的编译程序为止,把这样的实现方式称为自展技术例如，在目标机A上要实现L语言的编译程序，可以把L的核心部分划分为L1第一步：先用A机器的汇编语言或机器语言A书写L1的编译程序，表示为CAL1A，其T型图如图13.3所示：第二步：再用L1书写L语言的编译程序为CL1LA，其T型图如图13.4所示第三步：由于最终要求得到CALA，只要把CL1LA经过CAL1A即可得到CALA。可用图13.5的双层结合T型图表示：A结合T型图的原则是：（1）下面的T型图的左右上角两个语言分别与上面左右两个T型图的底部语言相同（2）上面左右两个T型图的左右上角的语言必须分别相同如果把L分出L1，L2，这个过程用三层结合的T型图表示如图13.6所示：ACALACALACAL2ACL2LACL1L2ACLL1AL可以分成核心L1，L2，…，Ln都为L1的逐步扩充，使得

L=Ln，其自展的示意图如图13.7所示：三、交叉编译程序交叉编译：在一个平台上生成另一个平台上的可执行代码。平台：指体系结构、操作系统。需要它的原因：1、目标平台上不允许或不能够安装所需要的编译程序，而又需要这个编译程序的某些特征。2、目标平台上的资源贫乏，无法运行所需要的编译程序。3、目标平台还没有建立，没有操作系统，根本上谈不上运行什么编译程序。特点：与主机编译相比，交叉编译受到的限制更多：专利、版权、技术。四、编译基础设施编译基础设施是编译程序的开发环境，它提供一系列开发编译程序的策略和工具，支持多种源语言、多目标机的编译技术，以便于人们在具有较高抽象层次的平台上进行编译程序开发和研究工作。编译基础设施为开发各种编译程序成分提供相应的生成工具。五、可重定向编译程序它能根据不同目标机,生成相应的目标代码,而普通编译程序将源程序翻译成特定目标机的汇编代码或目标代码。（1）可重定向编译程序不是针对特定机器的编译程序用户而言的可重定向。（2）可重定向编译程序不是编译程序的生成器。（3）有多个针对不同机型的可选后端。一、概述可重定向编译程序的研究和开发对于编译程序的构造具有重大意义：1、它缩短了编译程序的开发周期。2、它提高了编译程序研究的质量，使研究人员能够在抽象级的平台上开发,把精力专注于研究本身而非基础建设。3、便于更多的队伍从事编译程序研究，且其研究成果能够被很好地共享，从而可以加快步伐。4、及时针对新机器和新语言开发出配套的编译程序，减少了采用新语言和新机器的障碍，有利于为产品创造更大的市场。13.2可重定向编译程序二、支持可重定向编译的关键技术可重定向编译程序的目的是为了实现资源共享，方便于特定目标机的编译程序的剪裁和移植，因此，传统的多目标编译后端构造，中间表示、代码优化和代码生成等编译技术，应该为可重定向编译程序的开发提供依据。1、中间表示技术中间表示是在编译程序将高级语言程序翻译为汇编语言或机器代码的过程中产生的。在可重定向编译程序的研究中，应提供一种结构良好的中间表示，这种中间表示应在适当的抽象层次上，向上能支持多语言的映射，向下能适应多平台转换且宜于进行各种优化。2、机器描述技术研究表明，基于体系结构描述语言详细地指定体系结构是产生高质量机器级工具的关键技术。3、代码生成程序的构造技术一般来说，代码生成程序的构造器的输入是机器描述，输出是代码生成程序。4、目标机描述与目标代码生成的接口技术目标机描述与目标代码生成的接口，指定了与目标机无关的前端及与目标机有关的后端之间的相互联系。三、常用的可重定向编译程序1、目前在世界范围内得到广泛使用的可重定向编译程序是属于自由软件的GCC(GNUcompilercollection：/）GCC是FSF启动的GNU工程的一部分，其开发目标在于提高GNU系统中编译程序的质量。GCC目前已支持的源语言有：C、C＋＋、Objective_C、JAVA、Ada，已移植的平台有100多种，涉及30多种处理器、60多种系统。2、LCC是由普林斯顿大学的ChristopherFraser和David

Hanson开发的可重定向的ANSI

C编译程序，可供匿名使用。两者的主要区别在前端和后端的数量上：GCC支持C、C＋＋、Java等7种源语言和MIPS、ARM等36种体系结构系列。LCC源语言只支持标准C，后端支持ALPHA、MIPS

R3000、

SPARC和x86在机器描述的能力上：GCC所描述的处理器信息较多，强于LCC。在产生代码质量上：GCC经过20~30多遍的优化，大量测试表明代码的稳定性较好。LCC经过少量的优化，代码质量也比较可靠。GCC逐渐成为工业上的主流应用，LCC应用较少，且有被

GCC取代的趋势。一.GCC的总体结构编译器的工作是将源代码(通常使用高级语言编写)翻译成目标代码(通常是低级的目标代码或者机器语言)，在现代编译器的实现中，这个工作一般是分两个阶段来实现的：

第一阶段，编译器的前端接受输入的源代码，经过词法、语法和语义分析等等得到源程序的某种中间表示方式第二阶段，编译器的后端将前端处理生成的中间表示方式进行一些优化，并最终生成在目标机器上可运行的代码13.3

GCC的剖析GCC设计中有两个重要的目标：在构建支持不同硬件平台的编译器时，它的代码能够最大程度的被复用，所以

GCC必须要做到一定程度的硬件无关性。要生成高质量的可执行代码，这就需要对代码进行集中的优化。为了实现这两个目标，GCC内部使用了一种硬件平台无关的语言，它能对实际的体系结构做一种抽象，这个中间语言就是

RTL(RegisterTransferLanguage)GCC编译系统由与源语言相关的前端、与源语言无关的后端和目标机描述三部分组成，如图13.8所示：对于其支持的每种源语言，存在一个独立的、与语言相关的语法分析器。利用这些语法分析器，对不同的源语言产生相同的分析结果－语法树。二.GCC的中间表示高层中间表示为语法树，低层中间表示为RTL。RTL的语法结构类似于LISP语言的表达式，真正用于编译内部的只有91种操作码，另外的24种操作码则只出现在机器描述中。RTL的基本元素是rtx表达式，每个表达式的外部语法形式为：(code:mopn1opn2...)code为rtx的操作码,该操作码指明rtx的操作类型，如表示一条rtx指令、进行某种算术运行、引用某个符号名或寄存器以及表示某种说明等等。除此这外，code还确定rtx的操作数个数及其种类。m表示机器方式，即数据和运算结果的类型，它反映了数据类型与字长两部分信息。opn为操作数。rtx操作码可以表示5种对象：一般整数、宽整数、字符串、rtx表达式、由指向rtx的指针组成的向量。下面是一条将寄存器值送入内存的rtx表达式及其相应的树结构：(insn1113

(set

(mem:SF

(plus:S158)

(const_int32)))(reg:SF71))...图13.9中的rtx表达式表示了一条将寄存器的值送至内存的指令：RTL的基本元素rtx在形式上是统一的，但根据它们允许出现的场合可分为：指令的、具有副作用的、运算的、初等值的rtx表示指令的rtx一共有7条，其中最主要的是INSN、

JUMP_INSN、CALL_INSN、CODE_LABEL和NOTE，它们分别表示一般指令、转移指令、转子指令、标号定义和编译指导信息GCC中间表示中每条RTL指令实际上都表示着目标机的一条指令源程序中一个处理单元（函数或程序段）中所有RTL指令形成了如图13.10所示的一个完整结构：三.GCC的机器描述1.宏定义头文件：machine.h定义的主要内容：（1）编译驱动程序的宏定义：用于指导编译驱动程序以什么形式的命令行参数运行诸如预处理、编译、汇编连接等处理步骤（2）存储器的编址信息：如存储器的寻址单位、寻址方式（3）各种类型数据对象的存储约定（4）寄存器的个数、种类、名称及各种寄存器的用途约定（5）栈的安排、函数的入口、出口及调用约定（6）有关汇编语言输出的宏定义：指明汇编语言初始数据段、正文段、一般数据段等的格式要求，定义汇编输出函数的函数名（7）目标机操作系统所支持的目标文件格式或调试输出格式等等2.机器描述文件：machine.md它是一个正文文件其中除了允许以;打头的注释行外，其余均是采用RTL外部语法形式书写的rtx表达式这些rtx表达式的操作码是专门用于机器描述的9条操作码,由它们组成的机器描述包含目标机指令集的各种内容，主要包括以下几个方面：（1）目标机指令集的有关属性，主要包括：指令的分类指令的数据类型指令的长度指令的延迟槽功能部件（2）指令样板，描述目标机所支持的每一条指令相应的

RTL指令形式和汇编输出格式（3）指令样板的补充信息，指出可以进行与目标机相关的优化动作及相应的RTL指令形式define_insn具有4个或5个操作数，其形式和动作如下：操作数0为指令名，用字符串表示操作数1是一个不完全的rtx表达式或向量，称为RTL模板操作数2为一字符串，称为条件操作数3为一字符串，称为输出模板操作数4为一任选的rtx向量，称为指令属性下面是misp.md中一条指令样板的例子：(define_insn“adddf3”(set(match_operand:DF0“register_operand”“f”)(plus:DF(match_operand:DF2“register_operand”“f”)(match_operand:DF2“register_operand”“f”))))“TARGER_HARD_FLOAT”“add.d\\t%0,%1,%2”((set_attr“type”“tadd”)(set_attr“mode”“DF”)(set_attr“length”“1”)RTL模板中set和plus运算涉及的操作数均为形式如下的特殊rtx的表达式：(match_operand:mnpredicateconstaint)该表达式专门用于表示操作数n指明为第几个操作数m为操作数的方式predicate指明操作数必须满足的匹配条件constaint为对操作数的限制如图13.11所示，指令样板有两个重要作用：用于构造中间语言RTL中的指令、确定汇编代码的输出格式；它是支持多平台思想得到实现的核心部分：四.GCC的代码生成与机器描述的接口GCC的机器描述文件都是普通的正文文件，在编译过程中，如果为构造或匹配RTL在这种文件中搜索，那是极其缓慢的为此，一方面，在编译内部设计了一套专门的函数和数据结构作为编译主体与机器描述之间的接口，另一方面，在编译之外设计了一套独立的、专用的机器描述处理程序，这套程序将正文形式的机器描述转换成方便接口调用的数据结构与函数在GCC中，机器描述处理程序由11个独立的程序组成，每个程序处理机器描述文件的一部分内容，它们各自形成相应的C源程序，分别作用于RTL生成、机器相关优化和汇编代码输出等过程。其对应关系如图13.12所示：对于前面给出的mips.md中的那条双精度浮点加指令样板,经过gen*处理后产生的内容如图13.13所示：对于每个标准运算，GCC内部有一张操作表，其形式如图

13.14所示：13.4

GCC的定制一.GCC的剪裁为保证所开发的编译程序能够在该体系结构中正确运行，并能充分利用其机器特征，以进一步提高代码的质量，因此需要对所剪裁的编译程序做一些修改工作编译程序开发人员可以根据具体的目标机特性对其目标描述文件进行修改，从而避免了修改编译系统源程序的繁琐工作对MD文件的修改主要依赖于体系结构的特征参数，修改过程中主要的工作量集中在理解MD文件中的insn的含义、寻找GCC中对insn进行操作的函数GCC编译程序会产生一些THMP不支持的指令二.GCC编译程序的安装与配置（1）准备需要的头文件：下载交叉编译程序所需要的头文件包mips-inc.tgz，并在正确的目录下解压缩（2）下载需要的源程序包：目标代码工具包源码binutils-2.13、编译程序源码gcc-3.2、函数库源码glibc-2.2.5、glibc-linuxthreads-2.2.5（3）建立交叉的目标代码工具包：（4）建立一个静态的交叉编译程序：（5）建立函数库：（6）配置交叉编译程序使之支持C＋＋语言：（7）删除下述不再使用的目录：13.5

GCC的优化一.概述GCC的优化用到了绝大多数与机器无关的编译优化技术，如公共子表达式消除，常数合并等，它也利用了部分机器描述信息，进行了一些常用的、与机器相关的优化，如指令合并、指令调度等二.窥孔优化（线性窥孔优化）窥孔优化方法是通过考查一小段目标指令（窥孔）并把这些指令替换为更短更快的一段指令，从而提高目标代码的质量.所谓孔：可以看成优化对象中的一个小的活动窗口，孔中的代码根据优化的需要可以连续也可以不连续窥孔优化的一个特点是，优化后所产生的结果可能会给后面的优化提供进一步的机会1.冗余存取：如果有下面的指令：（1）STR0,A（2）LDR0,A2.不可达代码：删除不可达代码。在无条件跳转指令指令之后的无标号指令应该删除。这种操作可以重复，删除一系列指令例如，出于调度目的，在一个大程序里可能会插入一些调试语句。这些调试语句只有在调试‘开关’打开时（即

debug为1）才执行。用C语言写的源代码如下：#definedebug0…if(debug){

打印调试信息

}翻译为中间代码可能是：ifdebug=1gotoL1gotoL2L1:打印输出调试信息L2…经过初步优化，可能把它转换为：ifdebug≠1gotoL2打印输出调试信息L2：因此，上述程序相当于：gotoL2打印调试信息L2：3.控制流优化：这种不必要的连续跳转可以在窥孔优化时删除。例如：gotoL1…L1:gotoL2可以转换为：gotoL2…L1:gotoL2若没有别的语句跳转到L1，且L1:gotoL2紧跟在一个无条件语句之后，就可以将其删除。4.强度削弱：有的指令可以用花费时间更短的指令替代。例如，假设shiftleft为左移操作指令，则：MUL

R,#2可替换为shiftleftR,#1MUL

R,#4可替换为shiftleftR,#25.删除无用操作：有些指令的执行不会改变数据的结果，这种操作可以看成无用操作。例如：ADD

R,#0MUL

R,#1三.基于机器描述的窥孔优化在GCC机器描述中定义窥孔优化的模块，这样可以大大减少优化的工作量，且修改过程更加直观，并能达到良好的优化效果。窥孔优化模板的一般形式如下：(define_peephole[insn-pattern-1insn-pattern-2

…]

“condition”“template”“optionalinsn_attributer”)其中，insn-pattern等表示要匹配的相邻指令的指令样板，当一个指令序列与其匹配时将对condition进行检查，如果

condition成立则对这一系列指令进行窥孔优化。template控制已归并指令的输出。以两个（黑白）图像进行相加操作的函数为例，分别给出优化前后所输出的目标代码。两个图像相加函数的C源程序为：voidImgAdd(unsignedchar*Srcl,unsignedchar*Src2,unsignedchar*Dest,intlength){inti;for(i=0;i<length/8;i=i+8){Dest[i]=Srcl[i]+Src2[i];Dest[i+1]=Srcl[i+1]+Src2[i+1];

Dest[i+2]=Srcl[i+2]+Src2[i+2];

Dest[i+3]=Srcl[i+3]+Src2[i+3];

Dest[i+4]=Srcl[i+4]+Src2[i+4];

Dest[i+5]=Srcl[i+5]+Src2[i+5];

Dest[i+6]=Srcl[i+6]+Src2[i+6];

Dest[i+7]=Srcl[i+7]+Src2[i+7];}}多媒体指令的窥孔优化思想：将连续的四次lb、lb、addu、

sb操作用一次lw、lw、padd、sw来替代，当然需要首先判断对应的四次lb操作以及四次sw操作的内存空间是连续的例如，为实现并行加指令padd，在mips.md文件中添加的窥孔优化模板见网址窥孔优化的模板应该满足以下要求：①每一次进行加法操作的