第十二章代码生成ppt课件

1、1第十二章代码生成v第一节第一节 代码生成概述代码生成概述v第二节第二节 一个简单的代码生成程序一个简单的代码生成程序v第三节第三节 几种常用的代码生成程序的开发方法几种常用的代码生成程序的开发方法v第四节第四节 全局寄存器分配（图着色法）全局寄存器分配（图着色法）v第五节第五节 代码生成程序的自动化构造代码生成程序的自动化构造2知识结构知识结构312.1代码生成概述v代码生成代码生成是把经过语法分析或优化后的中间代码转换成是把经过语法分析或优化后的中间代码转换成特定目标机的机器语言或汇编语言，这样的转换程序称特定目标机的机器语言或汇编语言，这样的转换程序称为为代码生成程序代码生成程序v衡量目

2、标代码的质量主要从占用衡量目标代码的质量主要从占用空间空间和执行和执行效率效率两个方两个方面综合考虑面综合考虑第十二章代码生成4一.代码生成程序在编译系统中的位置v代码生成程序在编译系统中的位置如图代码生成程序在编译系统中的位置如图12.1所示：所示：5v目标代码一般有3种形式：（1）能够立即执行的机器语言代码，所有地址均已定位）能够立即执行的机器语言代码，所有地址均已定位（2）待装配的机器语言模块，当需要执行时，由连接装入）待装配的机器语言模块，当需要执行时，由连接装入程序把它们和某些运行程序连接起来，转换成能执行的机程序把它们和某些运行程序连接起来，转换成能执行的机器语言代码器语言代码（3

3、）汇编语言代码，尚需经过汇编程序汇编，转换成可执）汇编语言代码，尚需经过汇编程序汇编，转换成可执行的机器语言代码行的机器语言代码6二.设计代码生成程序的基本问题1.代码生成程序的输入：代码生成程序的输入：v代码生成程序的输入由前端所产生的中间表示和符号表代码生成程序的输入由前端所产生的中间表示和符号表中的信息组成中的信息组成v代码生成程序可以利用符号表中的信息来决定中间代码代码生成程序可以利用符号表中的信息来决定中间代码中的名字所指示的数据对象的运行时地址中的名字所指示的数据对象的运行时地址72.指令选择：指令选择：v所谓指令选择所谓指令选择，是指寻找一个合适的目标机指令序列以，是指寻找一个合

4、适的目标机指令序列以实现给定的中间表示实现给定的中间表示v例如，对中间代码例如，对中间代码x:=y+z，其中，其中x,y,z均为静态分配的变均为静态分配的变量，可以翻译成下述代码序列：量，可以翻译成下述代码序列：ld r0,y /*将将y放入寄存器放入寄存器r0*/add r0,z /*将将z与与r0相加相加*/st r0,x /*将将r0的值存入的值存入x*/8v生成代码的质量取决于它的执行速度和代码序列的长度生成代码的质量取决于它的执行速度和代码序列的长度v例如，如果目标机器有例如，如果目标机器有“加加1”指令（指令（inc），那么代码），那么代码a:=a+1用用inc a实现是最有效的，

5、而不是用以下的指令序实现是最有效的，而不是用以下的指令序列实现：列实现：ld r0,a add r0,#1 st r0,a9v指令选择的基本原则：（1）减少产生代码的尺寸）减少产生代码的尺寸（2）减少目标代码的执行时间）减少目标代码的执行时间（3）降低目标代码的能耗）降低目标代码的能耗这三者在某些情况下有可能会出现冲突，在具体选择这三者在某些情况下有可能会出现冲突，在具体选择的过程中应做折中考虑的过程中应做折中考虑103.寄存器分配：寄存器分配：v寄存器分配的工作是确定在程序的哪个点将哪些变量或寄存器分配的工作是确定在程序的哪个点将哪些变量或中间量的值放在寄存器中比较有益中间量的值放在寄存器中

6、比较有益v将经常使用的操作数保存在寄存器中是比较有利的将经常使用的操作数保存在寄存器中是比较有利的v 一些目标机可能具有不同类型的寄存器，对寄存器使用一些目标机可能具有不同类型的寄存器，对寄存器使用的一致性方面也存在一定的约束的一致性方面也存在一定的约束11v寄存器的使用可以分成：（1）分配阶段：为程序的某一点选择驻留在寄存器中的一）分配阶段：为程序的某一点选择驻留在寄存器中的一组变量组变量（2）指派阶段：挑出变量将要驻留的具体寄存器，即寄存）指派阶段：挑出变量将要驻留的具体寄存器，即寄存器赋值器赋值12v寄存器分配原则：（1）生成某变量的目标对象值时，尽量让变量的值或计算）生成某变量的目标对

7、象值时，尽量让变量的值或计算结果保留在寄存器中直到寄存器不够分配为止结果保留在寄存器中直到寄存器不够分配为止（2）当到基本块出口时，将变量的值存放在内存中）当到基本块出口时，将变量的值存放在内存中（3）在同一基本块内后面不再被引用的变量所占用的寄存）在同一基本块内后面不再被引用的变量所占用的寄存器应迟早释放，以提高寄存器的利用率器应迟早释放，以提高寄存器的利用率13v例如，考虑图例如，考虑图12.2的两个三地址代码序列，它们仅有的区的两个三地址代码序列，它们仅有的区别是第别是第2个语句的算符不同，其最短代码序列在图个语句的算符不同，其最短代码序列在图12.3中中给出：给出：14154.指令调度

8、：指令调度：v指令调度是指确定程序指令的执行顺序指令调度是指确定程序指令的执行顺序v例如，若在例如，若在mips4kc上计算表示式上计算表示式(a+b)+c，可用表，可用表12.1中两个不同的指令序列，它们的主要不同在于指令中两个不同的指令序列，它们的主要不同在于指令顺序和寄存器的赋值：顺序和寄存器的赋值：161712.2一个简单的代码生成程序一.计算机模型v假定一台假定一台m计算机具有计算机具有n+1个通用寄存器为个通用寄存器为r0,r1,r,rn，它们既可作为累加器又可作为变址器它们既可作为累加器又可作为变址器v如果用如果用opop表示运算符，用表示运算符，用m m表示内存单元，用变量名表

9、示表示内存单元，用变量名表示该变量所在的单元，该变量所在的单元，c c表示常量，表示常量，* *表示间址方式存取表示间址方式存取18v指令形式可包含以下四种类型，见表指令形式可包含以下四种类型，见表12.2：若若op是一目运算符，则是一目运算符，则op ri,m的意义为：的意义为：op(m)ri以上指令中的以上指令中的op包括一般计算机上常见的一些运算符包括一般计算机上常见的一些运算符j19某些指令的意义说明如表某些指令的意义说明如表12.3：20二.待用信息链表法v若在一个基本块中，变量若在一个基本块中，变量a在四元式在四元式i中被定值，在中被定值，在i后面后面的四元式的四元式j中要引用中要

10、引用a值，且从值，且从i到到j之间没有其他对之间没有其他对a的定的定值点，这时称值点，这时称j是四元式是四元式i中对变量中对变量a的的待用信息待用信息或称或称下次下次引用信息引用信息，同时也，同时也称称a是活跃的是活跃的，若，若a被多处引用则可构被多处引用则可构成成待用信息链待用信息链与与活跃信息链活跃信息链v为了得到在一个基本块内每个变量的待用信息和活跃信为了得到在一个基本块内每个变量的待用信息和活跃信息，可以从基本块出口的四元式开始息，可以从基本块出口的四元式开始由后向前由后向前扫描，为扫描，为每个变量名建立相应的待用信息链和活跃变量信息链每个变量名建立相应的待用信息链和活跃变量信息链21

11、v考虑到处理的方便，假定对基本块中的变量考虑到处理的方便，假定对基本块中的变量在出口处都是在出口处都是活跃活跃的，而的，而对基本块内的临时变量可分为两种情况处理：对基本块内的临时变量可分为两种情况处理：对于没有经过数据流分析，且中间代码生成的算法中不允对于没有经过数据流分析，且中间代码生成的算法中不允许在基本块外引用的临时变量，则这些临时变量在基本块许在基本块外引用的临时变量，则这些临时变量在基本块出口处都认为是不活跃的出口处都认为是不活跃的如果中间代码生成时的算法允许某些临时变量在基本块外如果中间代码生成时的算法允许某些临时变量在基本块外引用时，则假定这些临时变量被认为是活跃的引用时，则假定

12、这些临时变量被认为是活跃的22v在变量的符号表的记录项中设定了待用信息和活跃信息的栏目，其算法步骤如下：（1）对各基本块的符号表中的）对各基本块的符号表中的“待用信息待用信息”栏置栏置“非待用非待用”，对对“活跃信息活跃信息”栏，按在基本块出中处是否为活跃而置成栏，按在基本块出中处是否为活跃而置成“活活跃跃”或或“非活跃非活跃”，假定，假定外部变量外部变量都是都是活跃活跃的，的，临时变量临时变量都都是是非活跃非活跃的的23（2）从后向前从后向前依次处理每个四元式依次处理每个四元式i ： a:=b op c，在符号，在符号表中依次执行下述步骤：表中依次执行下述步骤：a的待用信息和活跃信息附加到的

13、待用信息和活跃信息附加到i上上把把a置成置成非待用非待用f和和非活跃非活跃fb和和c的待用信息和活跃信息附加到的待用信息和活跃信息附加到i上上把把b和和c待用信息待用信息置为置为i，活跃信息活跃信息置成置成活跃活跃l24v例如，四元式如下： (a,b,c,d是变量，t,u,v是中间变量)(1)t:=a-b(2)u:=a-c(3)v:=t+u(4)d:=v+u25变量变量待用信息待用信息活跃信息活跃信息初值初值 待用信息链待用信息链初值初值活跃信息链活跃信息链a ab bc cd dt tu uv v表12.4 待用信息链和活跃信息链llfffffffffll(4)(4)f(3)(3)f(2)(

14、2)f(1)(1)flffflllfllllf(4)dfl:=vff+uff(3)v(4)l:=tff+u(4)l(2)u(3)l:=afl-cfl(1)t(3)l:=a(2)l-bfl(4)d:=v+u(3)v:=t+u(2)u:=a-c(1)t:=a-b(4)d:=v+u(3)v:=t+u(2)u:=a-c(1)t:=a-b(4)d:=v+u(3)v:=t+u(2)u:=a-c(1)t:=a-b(4)d:=v+u(3)v:=t+u(2)u:=a-c(1)t:=a-b(4)d:=v+u(3)v:=t+u(2)u:=a-c(1)t:=a-b26表表12.4中中“待用信息链待用信息链”与与“活跃

15、信息链活跃信息链”的的每列每列，从左从左至右至右为每当为每当从后向前从后向前扫描一个四元式时扫描一个四元式时相应变量相应变量的信息变化情的信息变化情况，况，空白处为没变化空白处为没变化v vu ut td dc cb ba a活跃信息链活跃信息链初值初值待用信息链待用信息链初值初值 活跃信息活跃信息待用信息待用信息变量变量llfffffffffll(4)(4)f(3)(3)f(2)(2)f(1)(1)flffflllfllllf(4)(3)(2)(1)(4)(3)(2)(1) dvuvtuuactabdvuvtuuactab27三.代码生成算法v寄存器和内存地址的描述：寄存器和内存地址的描述：

16、rvalueri=a,c表示表示ri的现行值是变量的现行值是变量a，c的值的值avaluea=a表示表示a的值在内存中的值在内存中avaluea=ri,a表示表示a的值在的值在ri中又在内存中中又在内存中avaluea=ri表示变量表示变量a的值在寄存器的值在寄存器ri中中28v寄存器分配和代码生成的具体算法：设设retreg是一个函数过程，它的参数是一个形如是一个函数过程，它的参数是一个形如i: a:=b op c的四元式，每次调用的四元式，每次调用getreg(i: a:=b op c)则返回则返回一个寄存器一个寄存器r，用以存放，用以存放a的结果值的结果值对如何给出寄存器对如何给出寄存器

17、r，要用到四元式，要用到四元式i上的待用信息，以使上的待用信息，以使寄存器分配合理，对每个四元式的代码生成都要调用函数寄存器分配合理，对每个四元式的代码生成都要调用函数getreg29vgetreg分配寄存器的算法为：（1）如果）如果b的现行值在某寄存器的现行值在某寄存器ri中，且该寄存器只包含中，且该寄存器只包含b的值，或者的值，或者b与与a是同一标识符，或是同一标识符，或b在该四元式后不会再被在该四元式后不会再被引用，则可选择引用，则可选择ri为所需的寄存器为所需的寄存器r，并转（，并转（4）30（2）如果有尚未分配的寄存器，则从中选用一个）如果有尚未分配的寄存器，则从中选用一个ri为所需

18、的为所需的寄存器寄存器r，并转（，并转（4）31（3）从已分配的寄存器中选取一个）从已分配的寄存器中选取一个ri作为所需寄存器作为所需寄存器r，其其选择原则为：选择原则为：占用该寄存器的变量值同时在主存中，或在基占用该寄存器的变量值同时在主存中，或在基本块中引用的位置最远，这样对寄存器本块中引用的位置最远，这样对寄存器ri所含的变量和变量所含的变量和变量在主存中的情况必须先做如下调整：即对在主存中的情况必须先做如下调整：即对rvalueri中的中的每一变量每一变量m，如果，如果m不是不是a且且avaluem不包含不包含m，则需完则需完成以下处理：成以下处理：生成目标代码生成目标代码stri，m

19、；即把不是；即把不是a的变量值由的变量值由ri中送中送入内存中入内存中如果如果m不是不是b，则令，则令avaluem=m，否则，令，否则，令avaluem=m,ri删除删除rvalueri中的中的m32（4）给出）给出r，返回，返回33v这样，一旦得到一个为四元式运算的操作寄存器这样，一旦得到一个为四元式运算的操作寄存器r，就可，就可以进行代码生成，而当目标代码生成完成后，则又需修改以进行代码生成，而当目标代码生成完成后，则又需修改寄存器的使用信息和地址信息寄存器的使用信息和地址信息v用图用图12.4和图和图12.5给出算法的流程图：给出算法的流程图：34353612.3几种常用的代码生成程序

20、的开发方法一.解释性代码生成法v解释性代码生成文法解释性代码生成文法是建立一个代码生成专用语言，用这是建立一个代码生成专用语言，用这种语言以宏定义、子程序等形式描述代码生成过程种语言以宏定义、子程序等形式描述代码生成过程v通过这些宏定义和子程序把中间语言解释为目标代码通过这些宏定义和子程序把中间语言解释为目标代码v这种方法使机器描述与代码生成算法结合在一起，与机器这种方法使机器描述与代码生成算法结合在一起，与机器的联系直接反映在算法中的联系直接反映在算法中v机器描述是通过过程的形式提供的，如采用把源程序映像机器描述是通过过程的形式提供的，如采用把源程序映像成两地址代码序列的方法进行代码生成过程

21、中，对加法的成两地址代码序列的方法进行代码生成过程中，对加法的代码生成算法如下：代码生成算法如下：37macro add x,yif type of x=integer and type of y=integerthen iadd x,yelse if type of x=float and type of y=floatthen fadd x,yelse error38v其中含有对其中含有对iadd与与fadd的宏调用，以生成目标机上的的宏调用，以生成目标机上的整数和浮点数加法指令，如对整数和浮点数加法指令，如对ibm360机，机，iadd可写为：可写为：macro add a,bfrom

22、a in r1,b in r2emit (ar a,b) result in r1from a in r,b in memit(a a,b) result in rfrom a in m,b in remit(a b,a) result in r39v这种算法的局限性在于：这种算法的局限性在于：（1）由于目标机的多样性、寻址方式、指令的差异等等，）由于目标机的多样性、寻址方式、指令的差异等等，给中间代码的设计带来困难给中间代码的设计带来困难（2）代码生成语言与机器密切相关，可移植性受到限制）代码生成语言与机器密切相关，可移植性受到限制（3）目标机的描述与代码生成算法混在一起，当描述改变）目标机

23、的描述与代码生成算法混在一起，当描述改变时，势必引起算法的改变时，势必引起算法的改变（4）需进行指令的选择、指令的排序等低层次的繁琐工作）需进行指令的选择、指令的排序等低层次的繁琐工作，产生的目标代码质量依赖于设计者的经验和能力，产生的目标代码质量依赖于设计者的经验和能力（5）代码生成的视野有限，虽可进行一定范围的优化，但）代码生成的视野有限，虽可进行一定范围的优化，但对协调上下文有关的优化较困难对协调上下文有关的优化较困难40二二.模式匹配代码生成法模式匹配代码生成法v模式匹配代码生成方法是把对机器的描述与代码生成的算模式匹配代码生成方法是把对机器的描述与代码生成的算法分开法分开v而对在解释

24、性代码生成方法中，所需做的较繁重的具体情而对在解释性代码生成方法中，所需做的较繁重的具体情况分析的解释工作用模式匹配来代替况分析的解释工作用模式匹配来代替41v也就是建立一个代码生成用的机器描述语言，用以形式地也就是建立一个代码生成用的机器描述语言，用以形式地描述目标机的资源、指令及其语义等有关信息描述目标机的资源、指令及其语义等有关信息v代码生成程序根据这些信息，自动地把中间语言程序翻译代码生成程序根据这些信息，自动地把中间语言程序翻译成目标机的汇编语言或机器代码成目标机的汇编语言或机器代码v但在这种方法中，需通过形式描述的模式如实地反应机器但在这种方法中，需通过形式描述的模式如实地反应机器

25、的特性，这并不是一件容易的事，而且进行模式匹配时耗的特性，这并不是一件容易的事，而且进行模式匹配时耗费时间很长，其目标代码的质量也不太理想费时间很长，其目标代码的质量也不太理想42三.表驱动代码生成法v表驱动代码生成方法表驱动代码生成方法，实质上是模式匹配代码生成方法的，实质上是模式匹配代码生成方法的更进一步自动化，它是模仿从语法描述构造表和表驱动的更进一步自动化，它是模仿从语法描述构造表和表驱动的 一种语法分析方法一种语法分析方法v首先，把对目标机的形式化描述进行预加工转换成代码生首先，把对目标机的形式化描述进行预加工转换成代码生成表成表v然后，用表驱动的代码生成程序，来驱动代码生成表然后，

26、用表驱动的代码生成程序，来驱动代码生成表v最后，把中间语言的内部表示翻译成目标机的汇编代码最后，把中间语言的内部表示翻译成目标机的汇编代码v也就是说，也就是说，它是用一个代码生成程序的生成器自动地构造它是用一个代码生成程序的生成器自动地构造一个代码生成程序一个代码生成程序43v这种表驱动代码生成方法的这种表驱动代码生成方法的好处好处是：容易使用和修改，并是：容易使用和修改，并且能较容易地为不同的计算机构造适合于它们自己的代码且能较容易地为不同的计算机构造适合于它们自己的代码生成程序生成程序v这样将能增强编译程序的可移植性和灵活性，但是它所生这样将能增强编译程序的可移植性和灵活性，但是它所生成的

27、目标代码的质量，将依赖于机器描述的完善程序成的目标代码的质量，将依赖于机器描述的完善程序v最好的方法是用形式化的方法完善地描述一台计算机，但最好的方法是用形式化的方法完善地描述一台计算机，但这并不是一件容易的事，因而这种方法有待进一步改进和这并不是一件容易的事，因而这种方法有待进一步改进和完善完善4412.4全局寄存器分配（图着色法）一.概述v为减少存取操作的次数，可以将频繁使用的变量保留在固为减少存取操作的次数，可以将频繁使用的变量保留在固定的寄存器中，并使之贯穿不同的基本块边界，定的寄存器中，并使之贯穿不同的基本块边界，这就是全这就是全局寄存器分配问题局寄存器分配问题v1971年年john

28、 cokes提出，全局寄存器分配可以视为一种图提出，全局寄存器分配可以视为一种图着色问题着色问题v图着色法最初在实验性编译程序图着色法最初在实验性编译程序ibm370pl/i中使用，中使用，且很快得到广泛的推广且很快得到广泛的推广45v图着色法的基本思想：图着色法的基本思想：将一个程序的所有对象和可供使用将一个程序的所有对象和可供使用的实际寄存器视为一个无向图的不同结点的实际寄存器视为一个无向图的不同结点若两个对象间满足下列条件之一，则在它们之间引入一条若两个对象间满足下列条件之一，则在它们之间引入一条边，以表示它们相互干扰：边，以表示它们相互干扰：同时为活跃变量的两个对象同时为活跃变量的两个

29、对象一个对象与之不能也不应该分配的寄存器一个对象与之不能也不应该分配的寄存器46通过这种方式，构造出相应程序的干扰图通过这种方式，构造出相应程序的干扰图然后利用最大可供使用寄存器数的颜色种数，对干扰图的然后利用最大可供使用寄存器数的颜色种数，对干扰图的所有结点进行着色所有结点进行着色在对干扰图进行着色过程中，用尽量少的颜色、且将相邻在对干扰图进行着色过程中，用尽量少的颜色、且将相邻结点赋予不同的颜色结点赋予不同的颜色47不同的颜色对应于不同的实际寄存器，若目标机具有不同的颜色对应于不同的实际寄存器，若目标机具有r个个寄存器，则可用寄存器，则可用r种颜色对该干扰图进行着色种颜色对该干扰图进行着色

30、这个着色过程就是对该干扰图进行有效的寄存器赋值这个着色过程就是对该干扰图进行有效的寄存器赋值若不存在若不存在r种颜色，必须将其中一些变量或临时变量放在种颜色，必须将其中一些变量或临时变量放在内存中而不是寄存器中，这个过程称为内存中而不是寄存器中，这个过程称为spilling48v图着色的基本算法如下：（1）建立）建立web对象对象（2）用相邻矩阵表示干扰图）用相邻矩阵表示干扰图（3）利用相邻矩阵合并寄存器，查找拷贝）利用相邻矩阵合并寄存器，查找拷贝sisj，若，若si与与sj不相互干扰，将不相互干扰，将sj的使用替换为的使用替换为si的使用，并将代码中的的使用，并将代码中的sj去去掉。若完成寄

31、存器合并掉。若完成寄存器合并,返回到第（返回到第（1）步，否则继续下一步）步，否则继续下一步（4）构造干扰图的相邻列表表示）构造干扰图的相邻列表表示（5）计算）计算spill开销。对每个符号寄存器，计算将其开销。对每个符号寄存器，计算将其spill到内到内存后又将其重新存入到寄存器中的开销存后又将其重新存入到寄存器中的开销49（6）干扰图的修剪。从干扰图的相邻列表中排除结点及其）干扰图的修剪。从干扰图的相邻列表中排除结点及其相应的边。所采用的方法为相应的边。所采用的方法为degreer和消极试探法和消极试探法（7）寄存器赋值。利用相邻列表，尽量给每个结点着色，）寄存器赋值。利用相邻列表，尽量给

32、每个结点着色，且使没有两个相邻的结点具有同样的颜色。若成功，将每个且使没有两个相邻的结点具有同样的颜色。若成功，将每个符号寄存器用与之具有相同颜色的实际寄存器替换，分配终符号寄存器用与之具有相同颜色的实际寄存器替换，分配终止。若失败，进行下一步止。若失败，进行下一步（8）寄存器的）寄存器的spill。将需要。将需要spill符号寄存器中的值放在内存符号寄存器中的值放在内存中，然后插入中，然后插入spill函数函数(必要时再重新装入必要时再重新装入),返回到第（返回到第（1）步）步50二.图着色寄存器分配法的相关技术1.web对象：对象：vweb是用于分配寄存器的数据对象：一个是用于分配寄存器的

33、数据对象：一个web要么是一个要么是一个定值定值-引用链，要么是几个相交的链的最大引用链，要么是几个相交的链的最大“并集并集”v图图12.6为一个抽象数据流图片断为一个抽象数据流图片断,给出了给出了2个变量（个变量（x和和y）的定义和使用：的定义和使用：5152v可以将其划分为可以将其划分为4个个web：其中一个：其中一个web为在块为在块b2定义，由定义，由块块b4和和b5使用，和另一个块使用，和另一个块b3中定义，由块中定义，由块b5使用的两个使用的两个链的联合。其他的用链形成另外的一些链的联合。其他的用链形成另外的一些web。4个个web如下如下所示：所示：web componentsw

34、1 def x in b2, def x in b3, use x in b4, use x in b5w2 def x in b5, use x in b6w3 def y in b2, use y in b4w4 def y in b1, use y in b3利用利用web代替变量名的主要好处在于，可以区分程序中具代替变量名的主要好处在于，可以区分程序中具有相同命名但表示不同意义的变量，以方便寄存器的分配有相同命名但表示不同意义的变量，以方便寄存器的分配532.干扰图的表示：干扰图的表示：v在干扰图中，每个实际寄存器和每个在干扰图中，每个实际寄存器和每个web分别为干扰图的分别为干扰图的

35、一个结点一个结点v与某个结点相连的边数，称为该结点的度与某个结点相连的边数，称为该结点的度degreev图图12.6中中4个个web间的干扰图如图间的干扰图如图12.7所示：所示：54v若所有的寄存器是同构的，则没有必要将寄存器包括在干若所有的寄存器是同构的，则没有必要将寄存器包括在干扰图中扰图中v若目标机有两个以上的专用寄存器集合，则对这两类寄存若目标机有两个以上的专用寄存器集合，则对这两类寄存器的分配可以分开处理，这样可以减少干扰图的复杂性，器的分配可以分开处理，这样可以减少干扰图的复杂性，并使之具有较少的限制并使之具有较少的限制55v对干扰图所占用空间和访问时间进行折中考虑，采用下述两种

36、表示方法：（1）相邻矩阵表示法：）相邻矩阵表示法：相邻矩阵相邻矩阵adjmtx2.nwebs,1.nwebs-1是一个低三角矩阵是一个低三角矩阵,其中，矩阵的行与列分别表示干扰图中的结点其中，矩阵的行与列分别表示干扰图中的结点若第若第i个寄存器与第个寄存器与第j个寄存器是相邻的，则个寄存器是相邻的，则adjmtxmax(i,j),min(i,j)的值为真，否则为假的值为真，否则为假矩阵表示实现了干扰图的快速建立，同时，能快速确定某矩阵表示实现了干扰图的快速建立，同时，能快速确定某两个结点是否是相邻的两个结点是否是相邻的56（2）相邻列表表示：）相邻列表表示：相邻列表用具有相邻列表用具有6个成分

37、的数组表示：个成分的数组表示：color：为一整数，其值为该结点所选颜色的值：为一整数，其值为该结点所选颜色的值,初始值初始值disp：用于寄存器：用于寄存器spilling，表示相应符号寄存器，表示相应符号寄存器spill到某到某个栈的偏移地址，初始值个栈的偏移地址，初始值spcost：spill开销，对符号寄存器开销，对符号寄存器,初值为初值为0对实际寄存器，对实际寄存器， 初值为初值为nint：图中余下的与之相邻的结点数：图中余下的与之相邻的结点数adjnds：图中余下的与之相邻的结点列表：图中余下的与之相邻的结点列表rmvadj：已从图中去掉的相邻结点列表：已从图中去掉的相邻结点列表5

38、7优点：能比较方便地确定有多少结点与给定的结点相邻，优点：能比较方便地确定有多少结点与给定的结点相邻，且有哪些结点与之相邻且有哪些结点与之相邻相邻矩阵主要用于寄存器合并，相邻列表主要用于实际的相邻矩阵主要用于寄存器合并，相邻列表主要用于实际的着色过程着色过程因此，一般情况下，首先建立相邻矩阵，并在寄存器合并因此，一般情况下，首先建立相邻矩阵，并在寄存器合并过程中对其进行不断修改，然后根据相邻矩阵建立相应的过程中对其进行不断修改，然后根据相邻矩阵建立相应的相邻列表相邻列表583.寄存器合并：寄存器合并：v寄存器合并是一种复写传播变换，用于消除从一个寄存器寄存器合并是一种复写传播变换，用于消除从一

39、个寄存器到另一个寄存器的拷贝到另一个寄存器的拷贝v查找寄存器拷贝指令的中间代码，即查找寄存器拷贝指令的中间代码，即sjsi，若，若sj与与si不不相互干扰，则查找向相互干扰，则查找向si写数据的指令，对其进行修改，并写数据的指令，对其进行修改，并将其中相应数据写到寄存器将其中相应数据写到寄存器sj中，移去拷贝指令；且在干中，移去拷贝指令；且在干扰图中将扰图中将sj与与si合并为一个结点。该结点的度为为结点合并为一个结点。该结点的度为为结点sj和和si度的并集度的并集59v保证合并后为r可着色的情况下，才进行合并，为此需要两条安全策略：（1）若合并后所得结点）若合并后所得结点(a,b)具有小于具

40、有小于r个度大于或等于个度大于或等于r的的邻居，则结点邻居，则结点a和结点和结点b是可以合并的是可以合并的（2）对结点）对结点a的每个邻居的每个邻居t,要么要么t与结点与结点b已是相互干扰的，已是相互干扰的，要么要么t的度小于的度小于r，则这种合并是安全的，则这种合并是安全的60v寄存器合并是一种功能强大的变换，其主要作用在于：（1）简化编译过程，如消除不必要的拷贝操作）简化编译过程，如消除不必要的拷贝操作（2）在过程调用之前，保证参数值被移到合适的寄存器中）在过程调用之前，保证参数值被移到合适的寄存器中（3）对源和目的操作数有特殊要求的机器指令，使其操作）对源和目的操作数有特殊要求的机器指令

41、，使其操作数和结果在适当的位置数和结果在适当的位置（4）对操作数或结果值需要使用寄存器对的指令，保证能）对操作数或结果值需要使用寄存器对的指令，保证能够为其分配寄存器对，等等够为其分配寄存器对，等等614.spilling开销的计算：开销的计算：vspilling的结果可能会将一个的结果可能会将一个web分解为两个或多个分解为两个或多个web，从而减少干扰图中的干扰从而减少干扰图中的干扰v例如例如,通过将图通过将图12.6中引入相应的存取操作中引入相应的存取操作,如图如图12.8所示：所示：6263v这样这样web w1被分成被分成4个个web: w5、 w6、 w7、 w8：web comp

42、onentsw2 def x in b5, use x in b6w3 def y in b2, use y in b4w4 def y in b1, use y in b3w5 def x in b2, tmp x in b2w6 def x in b3, tmp x in b3w7 xtmp in b4, use x in b4w8 xtmp in b5, use x in b564v所得的干扰图如图所得的干扰图如图12.9所示：所示：65v干扰图的相邻列表中每项有一个成分干扰图的相邻列表中每项有一个成分spcost。spcost用于计用于计算算spilling相应符号寄存器所需要的开销相

43、应符号寄存器所需要的开销vspill一个一个web的开销可表示为：的开销可表示为：其中，其中，def、use、copy是是 web的单个定义、使用和拷贝：的单个定义、使用和拷贝： defwt 、usewt和和 copywt相对权值相对权值66v在计算spill开销的过程中，应该考虑下述因素：（1）若重新计算一个）若重新计算一个web的值比重新装载更有效，可对其的值比重新装载更有效，可对其进行重新计算，因此，选择重新计算的开销进行重新计算，因此，选择重新计算的开销（2）若）若spill了某条拷贝指令的源操作数或目的操作数，则了某条拷贝指令的源操作数或目的操作数，则可以不再考虑该指令可以不再考虑该

44、指令（3）若在同一基本块中，某个被）若在同一基本块中，某个被spill的值需要多次使用，的值需要多次使用，且直到最后一次使用，重新装载的值一直是活跃的，则在该且直到最后一次使用，重新装载的值一直是活跃的，则在该基本块中，只需做一次取操作基本块中，只需做一次取操作675.干扰图的修剪：干扰图的修剪：（1）degreer规则：规则：v结点的度结点的度degree表示与之相邻结点的个数表示与之相邻结点的个数v基本思想：基本思想：对给定包含一个度小于对给定包含一个度小于r的结点的干扰图是的结点的干扰图是r可着色的，当且仅当不包含该结点的干扰图是可着色的可着色的，当且仅当不包含该结点的干扰图是可着色的v

45、当然，这种规则并不是对所有的干扰图都适用。如图当然，这种规则并不是对所有的干扰图都适用。如图12.10可以分别为可以分别为2可着色的和可着色的和3可着色的，但却不能利用这可着色的，但却不能利用这种规则进行修剪：种规则进行修剪：6869（2）消极试探法：）消极试探法：v消极试探法是通过排除图中消极试探法是通过排除图中degreer的结点以对第一种的结点以对第一种方法进行推广方法进行推广v基本原理：基本原理：因为某个结点具有因为某个结点具有r或更多的相邻结点，这些或更多的相邻结点，这些相邻结点并不需要所有的均具有不同的颜色相邻结点并不需要所有的均具有不同的颜色,进一步地说进一步地说,它们并一定能用

46、完它们并一定能用完r种颜色种颜色v通过从图中反复查找度小于通过从图中反复查找度小于r的结点，开始对图进行着色的结点，开始对图进行着色v选择一个选择一个degreer的结点消极地放入栈中，选择原则：的结点消极地放入栈中，选择原则：根据其根据其spill cost值除以其目前的度，所得的值最小的结点值除以其目前的度，所得的值最小的结点优先级最高优先级最高70三.示例v如图如图12.11所示，代码片断中使用了符号寄存器：所示，代码片断中使用了符号寄存器：71v假设可供分配使用的寄存器为假设可供分配使用的寄存器为r2 、r3、 r4，分别为其建，分别为其建立干扰图和相邻矩阵，如图立干扰图和相邻矩阵，如

47、图12.12所示：所示：72v由于符号寄存器由于符号寄存器s1在退出块在退出块b1时，时，s0从其定义点之后都不从其定义点之后都不再是活跃的，因此它们的再是活跃的，因此它们的spill开销值都为无穷大，如图开销值都为无穷大，如图12.13所示：所示：73v符号寄存器符号寄存器s1无相邻结点，首先将其先放入栈中。实际寄无相邻结点，首先将其先放入栈中。实际寄存器存器r2 、r3、 r4以及符号寄存器以及符号寄存器s4、s9的度都为的度都为2，依次将，依次将它们放入栈中，它们放入栈中，s9 s4 r4 r3 r2 s1。干扰图的修剪过程如。干扰图的修剪过程如图图12.14所示：所示：74v修剪后的干

48、扰图如图修剪后的干扰图如图12.14(a)所示，可以看出，结点所示，可以看出，结点s8的度的度小于小于3，也将其压入栈中：，也将其压入栈中：s8 s9 s4 r4 r3 r2 s1v这时，所得的干扰图如图这时，所得的干扰图如图12.14(b)所示：所示：v在余下的干扰图中，每个结点的度都大于或等于在余下的干扰图中，每个结点的度都大于或等于3，只好，只好使用消极试探法，即把使用消极试探法，即把s7放入栈中，这样简化了干扰图使放入栈中，这样简化了干扰图使其变成如图其变成如图12.14(c)所示：所示：v进而将进而将s5压入栈中。这时所有的结点的度都小于压入栈中。这时所有的结点的度都小于3，将它，将

49、它们依次都放入栈中：们依次都放入栈中：s2 s3 s6 s5 s7 s8 s9 s4 r4 r3 r2 s175v依次将各个结点从栈中弹出的同时给它们赋予不同颜色值依次将各个结点从栈中弹出的同时给它们赋予不同颜色值,并根据并根据adjlsts.rmvadj 域的值重构干扰图域的值重构干扰图v当弹出当弹出3个结点时，干扰图如图个结点时，干扰图如图12.15所示：所示：76v当弹出第四个结点，即当弹出第四个结点，即s5就没有可供使用的颜色。这时就就没有可供使用的颜色。这时就需要进行寄存器的需要进行寄存器的spilling。分别将块。分别将块b4中的中的s7和和s5 spilling到内存中，其基址

50、寄存器为到内存中，其基址寄存器为r10，偏移量，偏移量disp分别为分别为0和和4。所得的代码的片断如图所得的代码的片断如图12.16所示：所示：7778v重新为其建立干扰图，如图重新为其建立干扰图，如图12.17所示：所示：79v利用利用degreer规则对其进行修剪，并将实际寄存器赋给与规则对其进行修剪，并将实际寄存器赋给与之具有相同颜色的符号寄存器，所得的代码片断如图之具有相同颜色的符号寄存器，所得的代码片断如图12.18所示：所示：8012.5代码生成程序的自动化构造v在在20世纪世纪70年代和年代和80年代，开始出现了编译后端的自动构年代，开始出现了编译后端的自动构造技术，开发了一系

51、列代码生成程序的构造器，如：造技术，开发了一系列代码生成程序的构造器，如：beg、iburg、twig、mburg等等v研究声明，这种利用声明性描述构造代码生成程序要比手研究声明，这种利用声明性描述构造代码生成程序要比手工编写容易，而且需要的工作量少，但其产生代码的执行工编写容易，而且需要的工作量少，但其产生代码的执行效率往往还不足手工开发的十分之一，从而很难为广大用效率往往还不足手工开发的十分之一，从而很难为广大用户所接受户所接受81v如图如图12.19所示，代码生成程序的构造器的输入是代码生成所示，代码生成程序的构造器的输入是代码生成描述，输出是代码生成程序：描述，输出是代码生成程序：82

52、一.模式匹配与动态规划v这种方法是由这种方法是由aho、ganapathi和和tjiang开发的开发的v基本思想：基本思想：将目标机指令将目标机指令用树重写规则用树重写规则表示，机器指令集表示，机器指令集合表示为一个树模式集合，且将描述不同指令的树模式赋合表示为一个树模式集合，且将描述不同指令的树模式赋予相对权值以表示执行该指令的相对代价，然后利用动态予相对权值以表示执行该指令的相对代价，然后利用动态规划技术选择最优的指令集合来计算相应的规划技术选择最优的指令集合来计算相应的中间表示树中间表示树。通过在中间表示树中重复查找与相应模板相匹配的子树并通过在中间表示树中重复查找与相应模板相匹配的子树

53、并用相应的替换结点进行重写，用相应的替换结点进行重写，即在将每个中间表示树规约即在将每个中间表示树规约为一个简单的结点过程中产生目标代码为一个简单的结点过程中产生目标代码83v树重写规则可表示为：label:patterncost=actionlabel是与文法规则左边的非终结符相对应的标识符是与文法规则左边的非终结符相对应的标识符pattern为树模式为树模式cost部分是由代码生成程序执行的部分是由代码生成程序执行的c代码。当某个子树与一代码。当某个子树与一个特定模式相匹配时，它返回一个开销值供动态规划算法个特定模式相匹配时，它返回一个开销值供动态规划算法使用，同时确定是否该模式满足匹配子

54、树的语义标准使用，同时确定是否该模式满足匹配子树的语义标准action部分也是部分也是c代码。若模式匹配成功且动态规划算法推代码。若模式匹配成功且动态规划算法推断出该模式是整个树的最小覆盖的一部分，则可执行。断出该模式是整个树的最小覆盖的一部分，则可执行。action的可能包含动作有：用另一个树替换被匹配的子树的可能包含动作有：用另一个树替换被匹配的子树、输出代码或别的动作、输出代码或别的动作若若cost被删除，则返回一个缺省值并假定模式匹配成功被删除，则返回一个缺省值并假定模式匹配成功若若action被删除，则表示什么都不做被删除，则表示什么都不做 84v优化原则：若其所有的子问题已经得到比

55、较优化的解，则优化原则：若其所有的子问题已经得到比较优化的解，则通过一种特殊的方法将所有子问题的解结合起来，可以得通过一种特殊的方法将所有子问题的解结合起来，可以得到整个问题的最优解到整个问题的最优解v动态规划算法为动态规划算法为ir树的每个结点赋一个开销值，其值为以树的每个结点赋一个开销值，其值为以覆盖该结点为根的子树的最好指令序列的各指令开销的总和覆盖该结点为根的子树的最好指令序列的各指令开销的总和85v图图12.20为简单的树重写系统：为简单的树重写系统： 86v重写规则用树的形式描述，断言重写规则用树的形式描述，断言isshort()确定它的参数是确定它的参数是否可以放进否可以放进sp

56、arc指令的指令的13位常量域位常量域k中中v相应的相应的twig规格说明如图规格说明如图12.21所示：所示： 878889prologue实现函数实现函数isshort()label声明部分列出所有作为标号的标识符声明部分列出所有作为标号的标识符node声明列出除标号标识符之外所有出现在模式中的标识符声明列出除标号标识符之外所有出现在模式中的标识符 $为指向被特定模式匹配的树的根结点的指针为指向被特定模式匹配的树的根结点的指针$i$为指向该根结点第为指向该根结点第i个孩子的指针个孩子的指针abort通过返回一个无穷大的开销，终止模式匹配过程通过返回一个无穷大的开销，终止模式匹配过程node

57、ptr为结点的类型为结点的类型getreg()是寄存器分配器是寄存器分配器emit_.()子程序的作用是输出指令子程序的作用是输出指令90v考虑下面一段中间代码：考虑下面一段中间代码：st(add(ld(r8,8),add(r2,ld(r8,4)v相应的中间表示树如图相应的中间表示树如图12.22所示：所示： 91v路径串可用整数标号替换结点标识符如图路径串可用整数标号替换结点标识符如图12.23所示：所示： 92v图图12.20的所有规则构造一个自动机，其路径串和规则如图的所有规则构造一个自动机，其路径串和规则如图12.24所示：所示： 93v结果自动机如图结果自动机如图12.25所示：所示

58、： 94二.基于语法制导的代码生成程序自动构造技术v也称为也称为graham-glanville方法方法v它利用类似于上下文无关文法的规则和相应的机器指令模它利用类似于上下文无关文法的规则和相应的机器指令模板描述机器操作板描述机器操作v当一条代码生成描述规则与一条波兰式中缀表示字符串的当一条代码生成描述规则与一条波兰式中缀表示字符串的子字符串相匹配，且满足有关的语义限制时，将被匹配的子字符串相匹配，且满足有关的语义限制时，将被匹配的部分用相应规则左边的符号替代，同时输出实例化后相应部分用相应规则左边的符号替代，同时输出实例化后相应的指令模板的指令模板vgraham-glanville代码生成程

59、序由中间语言变换、模式匹代码生成程序由中间语言变换、模式匹配器和指令生成配器和指令生成3部分组成部分组成 95v图图12.26中中(a)给出了给出了lir指令的子集，其中每个参数的位置指令的子集，其中每个参数的位置用一个数字表示，以用于中间表示字符串与代码生成规则用一个数字表示，以用于中间表示字符串与代码生成规则和指令模板的匹配和指令模板的匹配v相应的规则和相应的规则和sparc的指令模板如图的指令模板如图12.26(b)和和(c)所示所示v其中，其中，r.n表示寄存器，表示寄存器，k.n表示常量，表示常量，表示空字符串表示空字符串v数字数字n的作用：协调模式匹配与代码输出的关系、在规则的作用

60、：协调模式匹配与代码输出的关系、在规则中描述语法限制中描述语法限制 9697v下面以图下面以图12.27的的lir代码序列的目标代码生成为例：代码序列的目标代码生成为例：在波兰式代码中，用在波兰式代码中，用表示表示load（取）操作，（取）操作，表示表示store（存）操作，（存）操作，mov表示从寄存器到寄存器的拷贝表示从寄存器到寄存器的拷贝图图12.28为该代码序列的树形表示为该代码序列的树形表示假设当代码序列结束时，寄存器假设当代码序列结束时，寄存器r3和和r4不是活跃的不是活跃的因此，在树形图中不需要显式表示，但因此，在树形图中不需要显式表示，但r1和和r2需要保留需要保留该代码序列用