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

1、12.1 12.1 目的机目的机目的代码分为两类:一是机器言语代码 一是汇编言语代码一、有代表性的目的机二、详细指令系统(R)addrA (addrA)R ST R, A LD R, A 存取 意义 R, A 种类 (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 实数运算Real(addrA)R CONV R, A 转实 ( R ) = t r u e 那 么 转addrA,否那么下一条

2、(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 关系运算 AddrAR LDA R, A 读出地址 (R)+MR 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*YEND 那么生成的四元

3、式为(当前层数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*

4、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, *x14.ST R1, *x15.J

5、MP , 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 前往 在本例中,标示符的笼统地址和目的地址如下: (i,ksp) (l,i) y5sp (l,5) J4sp (l,4) X3sp (l,3) f目的地址 笼统地址 标示符 其中k=6+l 指令2转向子程序DISPLAY。它把指令3作为信息做下面任务(造本层DISPLAY表)并前往到指令4: 1.0 i 2.(addr(i

6、,2top)(i+6)top 3.i+1i 4.假设il那么转2 5.(sp)(6+l)top 12.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,M 3. DL R0,M MUL R0,R1 总代价=7 ST R0,M其中M表示直接存储地址。运用存放器的主要思想运用存放器的主要思想 在目的代码中运用存放器的主要思想是：在四元式中，每当一个变量被定义时，首先产生把值送入某一存放器的目的代码，然后在一个

7、表里注明该变量的值在哪一存放器中，只需当存放器被剥夺且变量的值以后还有用时，才把存放器中的现行值记入内存单元。当一个变量的值以后不再被援用时，就不用保管到内存中。 存放器的分配以根本块为单位。在根本块开场时一切存放器都是空闲可用的，在终了根本块时剥夺一切存放器，以便在下一个根本块开场时一切存放器都是可用的。 存放器分配的中心问题有二：一是存放器的自动释放问题，一是存放器的剥夺被迫释放问题。当没有可自动释放的，又没有空闲可用的存放器时要采取剥夺手段。两个中心问题中的主要问题是存放器的剥夺问题。 决议剥夺哪个存放器的主要要素有以下一些： 1写入内存次数。 2下次运用点的间隔。 3运用频率。 每当一

8、个存放器被剥夺时，要把它的值写入一些内存单元中，我们希望这种写入动作最少。不同存放器中的值在一个根本块内的运用频率是不一样的，我们希望被剥夺者值的运用频率是最低的。我们也希望被剥夺者的下次运用点是最远的。 12.3 12.3 表达式四元式的翻译表达式四元式的翻译 例例 设有表达式设有表达式 X X* *(a+b)(a+b)* *Y Y* *(a+b)(a+b) 其中其中X X和和Y Y为间接量，为间接量，a a和和b b为直接量，且为直接量，且类型均为实型，那么生成的四元式为：类型均为实型，那么生成的四元式为： 1 1(r+, a, b, T1)(r+, a, b, T1) 2 2(r(r*

9、*, X, T1, T2), X, T1, T2) 3 3(r(r* *, T2, Y, T3), T2, Y, T3) 4 4(r(r* *, T3, T1, T4), T3, T1, T4)由上述四元式生成目的代码的过程如下图 四 元 式 目 标 代 码 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(

10、T3, R2, 0, 4, 1) r*,T3,T1,T4 MUL R2, R1 1(T4, R2, 0, -, -) 12.4 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 , add

11、r(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 ,

12、 addr(Tv) RINC , off(I) ST , addr(T) 例例 设有表达式设有表达式aiai* *2+12+1* *BiBi* *2.u2.u和阐明和阐明 VAR i, j: integer; VAR i, j: integer; u: real; u: real; a: ARRAY110 OF real; a: ARRAY110 OF real; 以及形参阐明以及形参阐明VAR BVAR B：TnameTname，其中，其中TnameTname表表示前面数组类型的名，那么生成的四元式和示前面数组类型的名，那么生成的四元式和目的代码分别如下：目的代码分别如下： 四元式 1. (

13、 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 )目的代码 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 ,

14、R1 12. ST , T6 13. LD , T6 14. RINC ,off(u) 15. ST , T7 16. LD R1, *T4 17. MUL R1, *T7 12.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) 例例 设有程序段设有程序段

15、 u: = iu: = i* *j;j; X: = 0; X: = 0; W: = i W: = i* *j+uj+u 且变量均为整型变量，且变量均为整型变量，X X为援用型形参变为援用型形参变量，那么因公共表达式节省是以根本块量，那么因公共表达式节省是以根本块为单位的，而为单位的，而X:=0X:=0是一个块的终了在是一个块的终了在生成四元式时，因此首先生成如下四生成四元式时，因此首先生成如下四元式：元式： 1. (i*, i, j, T1) 2. (=:, T1, , u) 3. (=:, 0, , X) 4. (i*, i, j, T2) 5. (i+, T2, u, T3) 6. (=:

16、, T3, , w) 当处置完四元式1，2时得到目的代码 和REGALLOC表：REGALLOCu=(R1, 5, 1) 1. LD R1, i 2. IMUL R1, j 当处置四元式3时，首先生成目的代码 3. LD R2, 0 4. ST R2, *X 然后调用REGSTORE子程序，它将生成把寄存器中的值送回内存（如果必要的话）的目标代码： 5. ST R1, u 并把REGALLOC表置成空。这样四元式5中的u不能援用存放器中的u值。后面的目的代码如下： 6. LD R1, i 7. IMUL R1, j 8. IADD R1, u REGALLOCw =(R1,，) 假设四元式9是

17、新块的入口四元式，那么当前根本块终了，它将会首先生成下面的目的代码： 9. ST R1， w 并把REGALLOC表置成空。 12.6 12.6 条件语句四元式的翻译条件语句四元式的翻译 这里说的条件语句四元式主要指以下三种： . (THEN, A, ，) . (ELSE, ，) . (IFEND,，) 其中最后一条不产生目的代码，只完成回填任务。前二种四元式生成的目的代码形如： . LD R, loca(A) FJMP R, Jaddr . JMP , Jaddr 其中Jaddr是转向地址。 例例 设有条件语句设有条件语句 IF x0 THEN BEGIN x:=0;y:=1 ENDIF x

18、0 THEN BEGIN x:=0;y:=1 END ELSE BEGIN x:=1;y:=0 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, , , ) 最后生成的目的代码为： P+1. LD R1, x 2. GT R1, 0 3. FJMP R1, P+9 4. LD

19、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 12.7 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(J