精品课程《编译原理第12章代码生成》PPT课件.ppt
12.1 目标机,目标代码分为两类:一是机器语言代码 一是汇编语言代码一、有代表性的目标机二、具体指令系统,例子：假设有函数说明FUNCTION f(VAR X:real;J:integer):real;BEGIN X:=2.5+J IF X2.5 THEN X:=X+1 ELSE X:=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+J 4.(=:,T2,X)X:=2.5+J 5.(,X,2.5,T3)X2.5 4.(THEN,T3,)5.(CONV,1,T4)6.(r+,X,T4,T5)X+1 7.(=:,T5,X)X:=X+1 8.(ELSE,),9.(r-,X,1.0,T6)X-1.0 10.(=:,T6,X)X:=X-1.0 11.(IFEND,)12.(r*,X,Y,T7)X*Y 13.(=:,T7,f)f:=X*Y 14.(FUNED,),引用型形参变量是间接变量,因此要用间接地址法.从上面中间代码生成出来的目标代码如下:,1.ST,2top 存返回地址,2.JMP,DISPLAY 形成DISPLAY表 3.-l,l(top)sp 4.ST top,sp(top)+Moftop 5.RINC top,Moff 6.CONV R1,J 7.ADD R1,2.5 8.ST R1,*X 9.LD R1,*x10.GT R1,2.511.FJMP R1,12.CONV R1,113.ADD R1,*x,14.ST R1,*x15.JMP,16.LD R1,*X17.SUB R1,1.018.ST R1,*x19.LD R1,*X20.MUL R1,y21.ST R1,3sp22.ST SP,top(sp)top23.LD SP,0top(0top)sp24.JMP,2top 返回,在本例中,标示符的抽象地址和目标地址如下:,其中k=6+l,指令2转向子程序DISPLAY。它把指令3作为信息做下面工作(造本层DISPLAY表)并返回到指令4:,1.0 i 2.(addr(i,2top)(i+6)top 3.i+1i 4.若il则转2 5.(sp)(6+l)top,12.2 寄存器分配,定义访问一次内存的代价为，则指令执行代价=访问内存次数+1,例如:1.DL R0,M MUL R0,R0 总代价=4 ADD R0,R0 2.DL R0,M ADD R0,M 总代价=6 ST R0,M,3.DL R0,M MUL R0,R1 总代价=7 ST R0,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和说明 VAR i,j:integer;u:real;a:ARRAY110 OF real;以及形参说明VAR B：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,，)其中最后一条不产生目标代码，只完成回填工作。前二种四元式生成的目标代码形如：.LD R,loca(A)FJMP R,Jaddr.JMP,Jaddr 其中Jaddr是转向地址。,例 设有条件语句 IF x0 THEN BEGIN x:=0;y:=1 END ELSE BEGIN x:=1;y:=0 END则生成的四元式为：,最后生成的目标代码为：,12.7 循环语句四元式的翻译,循环语句四元式指下面三种四元式（只考虑 WHILE循环）：.(WHILE,，).(DO,A,，).(WHEND,，)其中WHILE四元式不产生目标代码，只用于记住WHILE循环的入口（重复）地址，DO四元式将产生条件转移目标代码，其转移地址要回填，WHEND四元式将产生无条件转向循环头的目标代码，同时回填DO四元式所产生的条件转移代码中的转向地址。,.WHILE四元式：REGSTORE；PUSH(P+1).DO四元式：同于THEN四元式.WHEND四元式：1.REGSTORE 2.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.结束基本块 2.生成目标代码 3.回填跳跃目标代码的转移地址,12.10 过程、函数调用四元式的翻译,考虑的四元式有：.(ACT,OPR1,OFF).(CALL,f,T),当CALL为过程调用时无T部分。其中OFF是形参的区距，OPR1是实参部分，当形参为赋值型时值为1（否则为0）。下面分几种情形讨论。1.形参为赋值型形参情形 2.形参为引用型形参情形 3.形参为过函标识符情形,
