课程《编译原理》课件第12章-代码生成.ppt

1、2021/7/2312021/7/23212.1 12.1 目标机目标机目标代码分为两类:一是机器语言代码 一是汇编语言代码一、有代表性的目标机二、具体指令系统(R)addrA(addrA)R ST R,A LD R,A 存取 意义 R,A 种类 2021/7/233(R)(addr(A)RIADD R,A ISUB R,A IMUL R,A整数运算(R)(addr(A)RAND R,A OR R,A 逻辑运算(R)(addr(A)R ADD R,ASUB R,AMUL R,A DIV R,A 实数运算2021/7/234Real(addrA)R CONV R,A 转实(R)=true则转ad

2、drA,否则下一条(R)=false则转addrA,否则下一 条 无 条 件 转 向addrA TJMP R,A FJMP R,A JMP R,A 转向操作(R)(addrA)成立，则trueR,否则falseR LT R,ALE R,AEQ R,A GT R,AGE R,A 关系运算 2021/7/235AddrAR LDA R,A 读出地址(R)+M MR R RINC R,M 变址器加 例子：假设有函数说明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*

3、YEND 2021/7/236则生成的四元式为(当前层数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,)2021/7/237 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.

4、(FUNED,)引用型形参变量是间接变量,因此要用间接地址法.从上面中间代码生成出来的目标代码如下:1.ST ,2top 存返回地址2021/7/238 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,*x2021/7/23914.ST R1,*x15.JMP ,16.LD R1,*X17.SUB R

5、1,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 返回 2021/7/2310 在本例中,标示符的抽象地址和目标地址如下:(i,ksp)(l,i)y5sp(l,5)J4sp(l,4)X3sp(l,3)f目标地址 抽象地址 标示符 其中k=6+l 2021/7/2311 指令2转向子程序DISPLAY。它把指令3作为信息做下面工作(造本层DISPLAY表)并返回到指令4:1.0 i 2.(addr(i,2top)(i+6)top 3.i+

6、1i 4.若il则转2 5.(sp)(6+l)top 2021/7/231212.2 12.2 寄存器分配寄存器分配定义访问一次内存的代价为，则指令执行代价=访问内存次数+1 例如:1.DL R0,M MUL R0,R0 总代价=4 ADD R0,R0 2.DL R0,M ADD R0,M 总代价=6 ST R0,M2021/7/2313 3.DL R0,M MUL R0,R1 总代价=7 ST R0,M其中M表示直接存储地址。2021/7/2314使用寄存器的主要思想使用寄存器的主要思想 在目标代码中使用寄存器的主要思想是：在四元式中，每当一个变量被定义时，首先产生把值送入某一寄存器的目标代

7、码，然后在一个表里注明该变量的值在哪一寄存器中，只有当寄存器被剥夺且变量的值以后还有用时，才把寄存器中的现行值记入内存单元。当一个变量的值以后不再被引用时，就不必保存到内存中。2021/7/2315 寄存器的分配以基本块为单位。在基本块开始时所有寄存器都是空闲可用的，在结束基本块时剥夺所有寄存器，以便在下一个基本块开始时所有寄存器都是可用的。2021/7/2316 寄存器分配的中心问题有二：一是寄存器的主动释放问题，一是寄存器的剥夺（被迫释放）问题。当没有可主动释放的，又没有空闲可用的寄存器时要采取剥夺手段。两个中心问题中的主要问题是寄存器的剥夺问题。决定剥夺哪个寄存器的主要因素有下列一些：1

8、写入内存次数。2下次使用点的距离。3使用频率。2021/7/2317 每当一个寄存器被剥夺时，要把它的值写入一些内存单元中，我们希望这种写入动作最少。不同寄存器中的值在一个基本块内的使用频率是不相同的，我们希望被剥夺者（值）的使用频率是最低的。我们也希望被剥夺者的下次使用点是最远的。2021/7/231812.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)2021/7/

9、2319由上述四元式生成目标代码的过程如图所示 四 元 式 目 标 代 码 REGALLOC表 r+,a,b,T1 LD R1,a ADD R1,b 1(T1,R1,0,2,2)r*,X,T1,T2 LD R2,*X MUL R2,R1 1(T1,R1,0,4,1)2(T2,R2,0,3,1)r*,T2,Y,T3 MUL R2,*Y 1(T1,R1,0,4,1)2(T3,R2,0,4,1)r*,T3,T1,T4 MUL R2,R1 1(T4,R2,0,-,-)2021/7/232012.4 12.4 复合变量四元式的翻译复合变量四元式的翻译 复合变量有两种：VE，V.I。其中V有两 种可能：第

10、一，它是结构变量名，第二，它又 是一个复合变量。结构变量名又可分为形参名 和实在名。VE变量的四元式（最后一条）可有以下三类：.(,a,T0,T).(,A,T0,T).(,Tv,T0,T)2021/7/2321上述四元式对应的目标代码分别为：.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)2021/7/2322 V.I的四元式有以下三类：.(,rc,I,T).(,RC,I,T).(,Tv,I,T)其中I在处理上可能有两种：一

11、是I为域名I自身（名表地址），一是I为SYMBL表地址。我们需要的是I的OFF值。2021/7/2323上述三种四元式的目标代码分别如下：.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)2021/7/2324 例例 设有表达式ai*2+1*Bi*2.u和说明 VAR i,j:integer;u:real;a:ARRAY110 OF real;以及形参说明VAR B：Tname，其中Tname表示前面数组类型的名，则生成的四元式

12、和目标代码分别如下：2021/7/2325 四元式 1.(i*,i,2,T1 )2.(i+,T1,1,T2 )3.(i-,T2,1,T3 )4.(,a,T3,T4 )5.(i-,T1,1,T5 )6.(,B,T5,T6 )7.(,T6,u,T7 )8.(r*,T4,T7,T8 )2021/7/2326目标代码 1.LD R1,I 2.IMUL R1,2 3.LD R2,R1 4.IADD R2,1 5.ISUB R2,1 6.LDA ,a 7.IADD ,R2 8.ST ,T4 9.ISUB R1,1 10.LD ,B 11.IADD ,R1 12.ST ,T6 13.LD ,T6 14.RI

13、NC ,off(u)15.ST ,T7 16.LD R1,*T4 17.MUL R1,*T7 2021/7/232712.5 12.5 赋值四元式的翻译赋值四元式的翻译 赋值语句可分为以下三种：.V0:=E .V1:=V2 .f:=E 其中V0表示简单类型的变量，V1和V2是结构类型的变量，f为实在函数名。对应的赋值四元式分别为：.(=:,eres(E),vres(V0).(=:,vres(V2),vres(V1).(=:,eres(E),vres(f)2021/7/2328 例例 设有程序段 u:=i*j;X:=0;W:=i*j+u 且变量均为整型变量，X为引用型形参变量，则因公共表达式节省

14、是以基本块为单位的，而X:=0是一个块的结束（在生成四元式时），因此首先生成如下四元式：2021/7/2329 1.(i*,i,j,T1)2.(=:,T1,u)3.(=:,0,X)4.(i*,i,j,T2)5.(i+,T2,u,T3)6.(=:,T3,w)2021/7/2330当处理完四元式1，2时得到目标代码 和REGALLOC表：REGALLOCu=(R1,5,1)1.LD R1,i 2.IMUL R1,j 2021/7/2331当处理四元式3时，首先生成目标代码 3.LD R2,0 4.ST R2,*X 然后调用REGSTORE子程序，它将生成把寄存器中的值送回内存（如果必要的话）的目标

15、代码：5.ST R1,u 2021/7/2332并把REGALLOC表置成空。这样四元式5中的u不能引用寄存器中的u值。后面的目标代码如下：6.LD R1,i 7.IMUL R1,j 8.IADD R1,u REGALLOCw=(R1,，)2021/7/2333 如果四元式9是新块的入口四元式，则当前基本块结束，它将会首先生成下面的目标代码：9.ST R1，w 并把REGALLOC表置成空。2021/7/233412.6 12.6 条件语句四元式的翻译条件语句四元式的翻译 这里说的条件语句四元式主要指以下三种：.(THEN,A,，).(ELSE,，).(IFEND,，)其中最后一条不产生目标代

16、码，只完成回填工作。前二种四元式生成的目标代码形如：.LD R,loca(A)FJMP R,Jaddr .JMP ,Jaddr 其中Jaddr是转向地址。2021/7/2335 例例 设有条件语句 IF x0 THEN BEGIN x:=0;y:=1 END ELSE BEGIN x:=1;y:=0 END则生成的四元式为：1.(,x,0,T1)2.(THEN,T1,)3.(=:,0,，x)4.(=:,1,y)5.(ELSE,)6.(=:,1,x)7.(=:,0,y)8.(IFEND,)2021/7/2336最后生成的目标代码为：P+1.LD R1,x 2.GT R1,0 3.FJMP R1,

17、P+9 4.LD R1,0 5.LD R2,1 6.ST R1,x 7.ST R2,y 8.JMP ，P+13 9.LD R1,1 10.LD R2,0 11.ST R1,x 12.ST R2,y 2021/7/233712.7 12.7 循环语句四元式的翻译循环语句四元式的翻译 循环语句四元式指下面三种四元式（只考虑 WHILE循环）：.(WHILE,，).(DO,A,，).(WHEND,，)其中WHILE四元式不产生目标代码，只用于记住WHILE循环的入口（重复）地址，DO四元式将产生条件转移目标代码，其转移地址要回填，WHEND四元式将产生无条件转向循环头的目标代码，同时回填DO四元式所

18、产生的条件转移代码中的转向地址。2021/7/2338.WHILE四元式：REGSTORE；PUSH(P+1).DO四元式：同于THEN四元式.WHEND四元式：1.REGSTORE 2.POP(P);BACK(P,P+2)3.POP(P);CODE(JMP,P)2021/7/233912.8 12.8 转向语句和标号四元式的翻译转向语句和标号四元式的翻译 考虑的四四元式为：.(LABEL，l).(GOTO,，l)翻译略 2021/7/234012.9 12.9 过程、函数说明四元式的翻译过程、函数说明四元式的翻译 考虑的四元式为.(PROC,f,Noff,Moff).(FUNC,g,Noff

19、,Moff).(PROCEND,，).(FUNCEND,，)其中和，和产生相同的目标代码。2021/7/2341 这里涉及到过函子程序的入口地址问题。可有三种处理方法：一是把入口地址定为执行部分的头；一是把入口地址定为块的头，而其头目标代码为转向执行部分的转移代码；一是把入口地址定为块的头，但在每个子程序前面放一条跳过该子程序的跳跃代码。我们采用第三种处理方法。2021/7/2342PROC和FUNC四元式要完成的工作有三：1.结束基本块 2.记入口地址 3.生成目标代码PROCEND和FUNCEND四元式要完成的工作 有三：1.结束基本块 2.生成目标代码 3.回填跳跃目标代码的转移地址 2021/7/234312.10 12.10 过程、函数调用四元式的翻译过程、函数调用四元式的翻译 考虑的四元式有：.(ACT,OPR1,OFF).(CALL,f,T)2021/7/2344 当CALL为过程调用时无T部分。其中OFF是形参的区距，OPR1是实参部分，当形参为赋值型时值为1（否则为0）。下面分几种情形讨论。1.形参为赋值型形参情形 2.形参为引用型形参情形 3.形参为过函标识符情形 问题解答问题解答?