精品课程《编译原理》PPT课件第12章代码生成

12.1目标机,目标代码分为两类:一是机器语言代码一是汇编语言代码一、有代表性的目标机二、具体指令系统,例子：假设有函数说明FUNCTIONf(VARX:real;J:integer):real;BEGINX:=2.5+JIFX2.5THENX:=X+1ELSEX:=X-1.0;f:=X*YEND,则生成的四元式为(当前层数l-1):1.(FUNC,f,Noff,Moff)2.(CONV,J,T1)3.(r+,2.5,T1,T2)2.5+J4.(=:,T2,X)X:=2.5+J5.(,X,2.5,T3)X2.54.(THEN,T3,)5.(CONV,1,T4)6.(r+,X,T4,T5)X+17.(=:,T5,X)X:=X+18.(ELSE,),9.(r-,X,1.0,T6)X-1.010.(=:,T6,X)X:=X-1.011.(IFEND,)12.(r*,X,Y,T7)X*Y13.(=:,T7,f)f:=X*Y14.(FUNED,),引用型形参变量是间接变量,因此要用间接地址法.从上面中间代码生成出来的目标代码如下:,1.ST,2top存返回地址,2.JMP,DISPLAY形成DISPLAY表3.-l,l(top)sp4.STtop,sp(top)+Moftop5.RINCtop,Moff6.CONVR1,J7.ADDR1,2.58.STR1,*X9.LDR1,*x10.GTR1,2.511.FJMPR1,12.CONVR1,113.ADDR1,*x,14.STR1,*x15.JMP,16.LDR1,*X17.SUBR1,1.018.STR1,*x19.LDR1,*X20.MULR1,y21.STR1,3sp22.STSP,top(sp)top23.LDSP,0top(0top)sp24.JMP,2top返回,在本例中,标示符的抽象地址和目标地址如下:,其中k=6+l,指令2转向子程序DISPLAY。它把指令3作为信息做下面工作(造本层DISPLAY表)并返回到指令4:,1.0i2.(addr(i,2top)(i+6)top3.i+1i4.若il则转25.(sp)(6+l)top,12.2寄存器分配,定义访问一次内存的代价为，则指令执行代价=访问内存次数+1,例如:1.DLR0,MMULR0,R0总代价=4ADDR0,R02.DLR0,MADDR0,M总代价=6STR0,M,3.DLR0,MMULR0,R1总代价=7STR0,M其中M表示直接存储地址。,使用寄存器的主要思想,在目标代码中使用寄存器的主要思想是：在四元式中，每当一个变量被定义时，首先产生把值送入某一寄存器的目标代码，然后在一个表里注明该变量的值在哪一寄存器中，只有当寄存器被剥夺且变量的值以后还有用时，才把寄存器中的现行值记入内存单元。当一个变量的值以后不再被引用时，就不必保存到内存中。,寄存器的分配以基本块为单位。在基本块开始时所有寄存器都是空闲可用的，在结束基本块时剥夺所有寄存器，以便在下一个基本块开始时所有寄存器都是可用的。,寄存器分配的中心问题有二：一是寄存器的主动释放问题，一是寄存器的剥夺（被迫释放）问题。当没有可主动释放的，又没有空闲可用的寄存器时要采取剥夺手段。两个中心问题中的主要问题是寄存器的剥夺问题。决定剥夺哪个寄存器的主要因素有下列一些：1写入内存次数。2下次使用点的距离。3使用频率。,每当一个寄存器被剥夺时，要把它的值写入一些内存单元中，我们希望这种写入动作最少。不同寄存器中的值在一个基本块内的使用频率是不相同的，我们希望被剥夺者（值）的使用频率是最低的。我们也希望被剥夺者的下次使用点是最远的。,12.3表达式四元式的翻译,例设有表达式X*(a+b)*Y*(a+b)其中X和Y为间接量，a和b为直接量，且类型均为实型，则生成的四元式为：1(r+,a,b,T1)2(r*,X,T1,T2)3(r*,T2,Y,T3)4(r*,T3,T1,T4),由上述四元式生成目标代码的过程如图所示,12.4复合变量四元式的翻译,复合变量有两种：VE，V.I。其中V有两种可能：第一，它是结构变量名，第二，它又是一个复合变量。结构变量名又可分为形参名和实在名。VE变量的四元式（最后一条）可有以下三类：.(,a,T0,T).(,A,T0,T).(,Tv,T0,T),上述四元式对应的目标代码分别为：,.LDA,addr(a)IADD,loca(T0)ST,addr(T).LD,addr(A)IADD,loca(T0)ST,addr(T).LD,addr(Tv)IADD,loca(T0)ST,addr(T),V.I的四元式有以下三类：.(,rc,I,T).(,RC,I,T).(,Tv,I,T)其中I在处理上可能有两种：一是I为域名I自身（名表地址），一是I为SYMBL表地址。我们需要的是I的OFF值。,上述三种四元式的目标代码分别如下：,.LDA,addr(rc)RINC,off(I)ST,addr(T).LD,addr(RC)RINC,off(I)ST,addr(T).LD,addr(Tv)RINC,off(I)ST,addr(T),例设有表达式ai*2+1*Bi*2.u和说明VARi,j:integer;u:real;a:ARRAY110OFreal;以及形参说明VARB：Tname，其中Tname表示前面数组类型的名，则生成的四元式和目标代码分别如下：,四元式,目标代码,12.5赋值四元式的翻译,赋值语句可分为以下三种：.V0:=E.V1:=V2.f:=E其中V0表示简单类型的变量，V1和V2是结构类型的变量，f为实在函数名。对应的赋值四元式分别为：.(=:,eres(E),vres(V0).(=:,vres(V2),vres(V1).(=:,eres(E),vres(f),例设有程序段u:=i*j;X:=0;W:=i*j+u且变量均为整型变量，X为引用型形参变量，则因公共表达式节省是以基本块为单位的，而X:=0是一个块的结束（在生成四元式时），因此首先生成如下四元式：,当处理完四元式1，2时得到目标代码,和REGALLOC表：REGALLOCu=(R1,5,1),当处理四元式3时，首先生成目标代码,并把REGALLOC表置成空。这样四元式5中的u不能引用寄存器中的u值。后面的目标代码如下：,如果四元式9是新块的入口四元式，则当前基本块结束，它将会首先生成下面的目标代码：,12.6条件语句四元式的翻译,这里说的条件语句四元式主要指以下三种：.(THEN,A,，).(ELSE,，).(IFEND,，)其中最后一条不产生目标代码，只完成回填工作。前二种四元式生成的目标代码形如：.LDR,loca(A)FJMPR,Jaddr.JMP,Jaddr其中Jaddr是转向地址。,例设有条件语句IFx0THENBEGINx:=0;y:=1ENDELSEBEGINx:=1;y:=0END则生成的四元式为：,最后生成的目标代码为：,12.7循环语句四元式的翻译,循环语句四元式指下面三种四元式（只考虑WHILE循环）：.(WHILE,，).(DO,A,，).(WHEND,，)其中WHILE四元式不产生目标代码，只用于记住WHILE循环的入口（重复）地址，DO四元式将产生条件转移目标代码，其转移地址要回填，WHEND四元式将产生无条件转向循环头的目标代码，同时回填DO四元式所产生的条件转移代码中的转向地址。,.WHILE四元式：REGSTORE；PUSH(P+1).DO四元式：同于THEN四元式.WHEND四元式：1.REGSTORE2.POP(P);BACK(P,P+2)3.POP(P);CODE(JMP,P),12.8转向语句和标号四元式的翻译,考虑的四四元式为：.(LABEL，l).(GOTO,，l)翻译略,12.9过程、函数说明四元式的翻译,考虑的四元式为.(PROC,f,Noff,Moff).(FUNC,g,Noff,Moff).(PROCEND,，).(FUNCEND,，)其中和，和产生相同的目标代码。,这里涉及到过函子程序的入口地址问题。可有三种处理方法：一是把入口地址定为执行部分的头；一是把入口地址定为块的头，而其头目标代码为转向执行部分的转移代码；一是把入口地址定为块的头，但在每个子程序前面放一条跳过该子程序的跳跃代码。我们采用第三种处理方法。,PROC和FUNC四元式要完成的工作有三：1.结束基本块2.记入口地址3.生成目标代码PROCEND和FUNCEND四元式要完成的工作有三：1.