第9章目标代码生成课件

第9章目标代码生成（1）源程序编译前端中间代码代码优化中间代码代码生成器目标程序符号表代码生成器的位置第十一章目标代码生成第9章目标代码生成（1）源程序编译前端中间代码代码优化中间代1代码生成器的输入包括中间代码和符号表中的信息。目标代码一般有以下三种形式：（1）能独立执行的机器语言代码，所有地址均以定位（代真）。（2）待装配的机器语言模块。当需要执行时，由连接装入程序把它们和某些运行程序连接起来，转换成能执行的机器语言代码。（3）汇编语言代码，尚须经过汇编程序汇编，转换成可执行的机器代码。代码生成器着重考虑两个问题:一是如何使生成的目标代码较短；另一个是如何充分利用计算机的寄存器，减少目标代码中访问存储单元的次数。这两个问题直接影响代码的执行速度。第十一章目标代码生成代码生成器的输入包括中间代码和符号表中的信息。第十一2基本问题:所有代码生成器都要面对何种中间代码输入,（是式逆波兰，四元式，还是三元式？等问题）何种代码做为目标程序,选择适当的代码指令,最优的寄存器分配方案,和计算顺序等基本问提.为此本书见立了目标机器模型:并把中间代码对应的目标代码做了规定.利用待用信息,寄存器描述数组RVALUE,变量地址描述数组AVALUE等概念建立了代码生成算法.P316[例11。2]同学们应该好好研究。P317表11。4各中间代码对应的目标代码应该背过。寄存器分配：利用执行代价的概念说明如何建立更佳的寄存器分配方案。对于循环L中某变量M，如果分配一个寄存器给它专用，那么，每执行循环一次，执行代价的节省数可用公式（11。1）计算。这个计算公式应该掌握。第十一章目标代码生成基本问题:所有代码生成器都要面对何种中间代码输入,（是式逆3[例11。3]图11。4代表某程序的最内层循环，其中无条件转移和条件转移指令均以改用箭头来表示。各基本块入口之前和出口之后的活跃变量已列在图中。假定R0,R1和R2三个寄存器在该循环中将固定分配给某三个变量使用。现在，我们利用公式（11。1）计算各变量的执行代价节省数，并且取执行代价节省数最高的来确定这三个变量。解：因为B1中引用a前已对a定值，所以use(a,B1)=0;在B2,B3中a被各引用一次，且在引用前未对a定值，所以use(a,B2)=use(a,B3)=1;B4中未引用a，所以use(a,B4)=0.因为a在B1中被定值且a在B1出口是活跃的，a在B2,B3和B4出口后不是活跃的则：live(a,B1)=1Live(a,B2)=live(a,B3)=live(a,B4)=0;所以代价节省数为：1+1+2*1=4。第十一章目标代码生成[例11。3]图11。4代表某程序的最内层循环，其中无条4同样可以算出b,c,d,e,f的执行代价节省数分别为：6，3，6，4，4。按照代价节省数的大小我们把寄存器R0分配给d,R1分配给b;a,e,f的执行代价相同,可人选其一将R2分配给a.DAG的目标代码为了生成更有效的目标代码，要考虑的另一个问题是，对基本块中中间代码序列，我们应按怎样的次序来生成其目标代码呢？本节P323给出了利用基本块的DAG图给出了基本块中中间代码序列排序的方法，以便生成较优的目标代码。下面我们学习一个例子，一加深其理解：[例11。6]考察下面中间代码序列G1:第十一章目标代码生成同样可以算出b,c,d,e,f的执行5T1:=A+BT2:=A-BF:=T1*T2T1:=A-BT2:=A–CT3:=B-CT1:=T1*T2G:=T1*T3其对应的DAG如图ABC+n1--n2n4T2**-Fn3*Gn7T3n5T1n6A第十一章目标代码生成T1:=A+BABC+n1--n2n46上图的DAG含有7个结点，我们应用课本中的算法。把它们排序，主要步骤如下。第一步置初值：i=7；T的所有元素全为空null。内部结点n3和n7均满足第三步的要求，假定我们选取T[7]为结点n3。结点n3的最左子结点（内部）n1满足第5步的要求，因此按第6步，T[6]=n1.但n1的最左子结A为叶结，不满足第6步的要求。则现在只有n7满足第3步要求，于是T[5]=n7。结点n7的最左子结n6满足第5步的要求，因此T[4]=n6。结点n6的最左子结点n2同样满足第5步的要求，因此T[3]=n2.余下的满足第3步要求的尚有n4和n5，假定选取T[2]=n4。当把n5列为T[1]后，算法工作结束。至此，我们求出的图的内结点顺序为：n5,n4,n2,n6,n1,n3.按这个次序从新表示中间代码序列为G1‘为：T3:=B-C;T2:=A-C;S1:=A–B;T1:=S1*T2;G:=T1*T3;S2:=A+B;F:=S2*S1。如前所述按后一个中间代码序列生成中间代码将会较优。第十一章目标代码生成上图的DAG含有7个结点，我们应用课本中的算法。把它们7窥孔优化几种窥孔优化的方法都比较好理解，这里不再重述课本内容。第十一章目标代码生成窥孔优化第十一章目标代码生成8例题与习题解答[例11。1]假设只有R0和R1两个寄存器，对赋值语句d=(a-b)+(a-c)+(a-c)生成目标代码。并写出寄存器描述数组RVALUE和变量地址描述数组AVALUE.该赋值语句的三地址序列：t:=a-bt1:=a-ct2:=t+t1d:=t1+t2将此代码看成一基本块，并设在基本块末尾，变量d是活跃的。生成目标代码表如图：第十一章目标代码生成例题与习题解答[例11。1]假设只有R0和R1两个寄存器，对9

中间代码目标代码RVALUEAVALUEt:=a-bLDR0,aR0含tt在R0中SUBR0,bt1:=a-cLDR1,aR0含tt在R0中SUBR1,cR1含t1t1在R1中t2:=t+t1ADDR0,R1R0含t2t2在R0中R1含t1t1在R1中d:=t1+t2ADDR0,R1R0含dd在R0中STR0,dd在R0和存储器中第十一章目标代码生成第十一章目标代码生成10[例11。2]（k3）假设R0,R1和R2为可用寄存器，试对以下各表达式分别生成最优目标代码。A+(B+(C*(D+E/F+G)*H))+(I*J)解：首先生成三地址中间代码序列：T1:=E/FT2:=D+T1T3:=G+T2T4:=C*T3T5:=H*T4T6:=B+T5T7:=A+T6T8:=I*JT9:=T7+T8第十一章目标代码生成[例11。2]（k3）第十一章目标代码生成11最优的目标代码：LDR0,EDIVR0,FADDR0,GMULR0,HMULR0,CADDR0,BADDR0,ALDR1,IMULR1,JADDR0,R1[例11。3]（K1）对以下中间代码序列G:第十一章目标代码生成最优的目标代码：第十一章目标代码生成12T1:=B–CT2:=A*T1T3:=D+1T4:=E–FT5:=T3*T4W:=T2/T5假设可用寄存器为R0和R1，W是基本块出口的活跃变量，用简单代码生成算法生成目标代码，同时列出代码生成过程中的寄存器描述和变量地址描述。中间代码目标代码RVALUEAVALUET1:=B-CLDR0,BR0含T1T1在R0中SUBR0,CT2:=A*T1MULR0,AR0含T2T2在R0中STR0,T2T2同时在R0和存储器中T3:=D+1LDR1,DR1含T3T3在R1中第十一章目标代码生成T1:=B–C第十一章目标代码生成13ADDR1,#1T4:=E-FLDR0,ER0含T4T4在R0中SUBR0,FT5:=T3*T4MULR1,R0R1含T5T5在R1中LDR0,T2R0含T2T2在R0和存储器中W:=T2/T5DIVR0,R1R0含WW在R0中STR0,WW在R0和存储器中第十一章目标代码生成ADDR1,14第十一章目标代码生成第十一章目标代码生成15编译原理

优化和目标代码生成(2h)主讲：蒋伟进教授2007.03-05第十一章目标代码生成编译原理

优化和目标代码生成(2h)第十一章目标代码生成16第七章编译程序

７．1

编译程序考虑的因素７．2

执行时的内存分配７．3

代码优化第十一章目标代码生成第七章编译程序７．1编译程序考虑的因素７．2执行时177.1编译程序考虑的因素编译程序设计时，除了需要用到前面介绍的分析技术和制导翻译外，还要考虑如何从源程序数据空间映射到具体物理存储空间，也就是运行时的数据表示。在运行的时候如何组织或存放数据、在源程序中同名标识符是怎么样描述不同的对象、运行时的程序控制权是如何转移的，参数是如何传递以及如何生成质量较高的目标代码都是编译程序设计者应该考虑的问题。第十一章目标代码生成7.1编译程序考虑的因素编译程序设计时，除了需要用到187.1.1数据类型类型的合法性检查是判断数据类型是否与上下文的要求一致数据类型是对该类型数据（变量或常量）的取值是否合法以及对该类型数据的运算是否合法的一种说明。第十一章目标代码生成7.1.1数据类型类型的合法性检查是判断数据类型是否与上下197.1.2数据结构一个程序设计语言如允许使用的数组、记录、字符串、表、栈等形式的数据结构，在编译程序中应为它们提供相应的翻译。为了能对数据结构中的元素进行引用，必须完成从逻辑结构到能够访问这些数据元素的物理结构的映射。应考虑：１映射算法相对简单，根据逻辑结构容易计算出物理地址２从逻辑结构投影到物理结构时，不至于超界或存储溢出３使用的数据结构承担这种程序设计语言的主要功能４在这些数据结构定义相关的运算第十一章目标代码生成7.1.2数据结构一个程序设计语言如允许使用的数组、记207.1.3作用域规则一个程序设计语言的作用域规则确定了该程序设计语言的某个程序的不同程序块中所说明的标识符的可访问性。从另外一个角度看，在程序中当访问一个标识符通过作用域规则可确定究竟访问的是哪一个实体中说明的标识符。通常一个程序设计语言的一个标识符或数据项的作用域是在说明该标识符或数据项的程序块内。第十一章目标代码生成7.1.3作用域规则一个程序设计语言的作用域规则确定了该程217.1.4控制结构一个程序设计语言的控制结构是该语言在程序运行期间用于改变控制流的语言特征集合。第十一章目标代码生成7.1.4控制结构一个程序设计语言的控制结构是该语言在程序22７.2执行时的内存分配编译程序需要为源程序中的数据分配执行时的存储空间，编译程序从操作系统中申请编译程序计算出的所需的内存，或编译程序生成在运行时需申请内存的指令。（１）确定用来表示某一数据项的内存大小。（２）使用适当的内存分配策略，实现具体数据的作用域和生存期。（３）确定以适当的算法访问生存期内的数据，包括基本型数据结构构造类型。第十一章目标代码生成７.2执行时的内存分配编译程序需要为源程序中的数据分配执23为目标程序分配执行时所需的存储空间：一种是在目标程序运行前，由编译程序为数据结构分配存储空间，在程序的执行期间不再分配和解除这种内存分配。叫做静态存储分配。一种在程序运行期间均可以对内存实现分配或解除分配，一旦存储分配解除该存储空间内的数据便失去意义。叫做动态存储分配。第十一章目标代码生成为目标程序分配执行时所需的存储空间：第十一章目标代码生成24宗旨：

获得较好性能的代码

阶段：sourcefrontI.Rcodetargetcodeendgeneratorcode用户中间代码优化目标代码优化什么是代码优化７.３代码优化第十一章目标代码生成宗旨：获得较好性能的代码25例：intarr[10000];voidBinky(){inti;for(i=0;i<10000;i++)arr[i]=1;}intarr[10000];voidWinky(){registerint*p;for(p=arr;p<arr+10000;p++)*p=1;}第十一章目标代码生成例：intarr[10000];intarr[1000026目标：作为一个高级语言的使用者很希望编译程序所产生的代码能够和直接用机器语言编写的程序效果一样好。代码优化是指对原代码进行的变换，从而获得在时间和空间上效率相对高的程序，且一般也不是在时间和空间上最省的程序，在进行优化时应该做到：１代码的变换必须保持原程序的语义。２从理论上，变换加快了程序的速度。３这种变换是值得的第十一章目标代码生成目标：作为一个高级语言的使用者很希望编译程序所产生的代码能27优化分类按阶段分:与机器无关的优化---对中间代码进行依赖于机器的优化---对目标代码进行根据优化所涉及的程序范围分成:(1)局部优化:(基本块)应用于仅包含少量语句的小程序的优化变换。(2)循环优化:对循环中的代码进行优化(3)全局优化:大范围的优化应用于一个程序单元，如一个函数或一个过程的优化变换。第十一章目标代码生成优化分类按阶段分:第十一章目标代码生成28程序的执行效率是可以通过在编译期间进行优化变换，不改变语义重写程序段以提高程序的工作效率。虽然变换的方法很多，但是常用的大致有以下几种：１编译求值２合并预算３删除死码４减少频率５强度削弱和变换循环条件６减少重写传播第十一章目标代码生成程序的执行效率是可以通过在编译期间进行优化变换，不改变语义重29局部优化：所需要的开销相对较低，因此从优化所得到的收益也相对较低。局部优化只是在较小的程序段中进行优化，从而到达优化的目的。这种程序段称为基本段。全局优化：要产生高效的代码，编译程序仅在基本块内优化是不够的，编译程序应把程序作为一个整体来考虑，对各个基本块的信息进行数据流的分析从而达到优化的目的。全局优化同局部优化相比，全局优化需要更多的分析，以便确定优化的可行性。第十一章目标代码生成局部优化：所需要的开销相对较低，因此从优化所得到的收益也相30优化的原则等价原则有效原则时间空间合算原则优化的代价效果第十一章目标代码生成优化的原则等价原则第十一章目标代码生成31优化的基本方法去处冗余削减强度使用更快的指令第十一章目标代码生成优化的基本方法去处冗余第十一章目标代码生成32局部优化方法合并已知量临时变量改名交换语句位置代数变换第十一章目标代码生成局部优化方法第十一章目标代码生成33循环优化代码外提强度削弱A=A+1A++删除归纳变量例如循环中加法变为，循环外乘法第十一章目标代码生成循环优化代码外提第十一章目标代码生成34窥孔优化窥孔目标程序中的一个可以移动的窗口优化方法冗余存取不可到达代码控制流优化强度削弱删除无用操作第十一章目标代码生成窥孔优化窥孔第十一章目标代码生成35

7.4代码生成要考虑的主要问题——具体细节依赖于目标机器和操作系统共同的问题：充分利用寄存器基本块中全局寄存器分配：不把寄存器平均分配给各个变量使用，而是从可用的寄存器中分出几个，固定分配给几个变量单独使用。标准：以各变量在循环内需要访问主存单元的次数为标准。选择计算机指令系统选择计算次序第十一章目标代码生成7.4代码生成要考虑的主要问题——具体细节依赖于目标机器36

目标代码的三种形式

地址代真的机器代码待装配的机器代码模块汇编语言（宏汇编）

机器指令形式(opsource,destination)ADDs