第9章目标代码生成

1、 第第 9 章章 目标代码及其生成目标代码及其生成 目标代码生成目标代码生成是编译的最后一个阶段，其功能表示如下：是编译的最后一个阶段，其功能表示如下：目标生成目标生成中间代码中间代码目标代码目标代码符号表符号表其中：其中：中间代码中间代码 逆波兰式，三元式，四元式，语义树；逆波兰式，三元式，四元式，语义树；目标代码目标代码 机器语言，汇编语言，机器语言，汇编语言，符符 号号 表表 变量的语义词典，变量的语义词典，9.1 目标代码生成的基本问题目标代码生成的基本问题9.3 多寄存器下的目标代码生成算法多寄存器下的目标代码生成算法内容内容提要提要9.2 一个简单代码生成器设计一个简单代码生成器设

2、计9.1 目标代码生成的基本问题目标代码生成的基本问题. 目标代码选择问题目标代码选择问题v 虚拟机及其指令系统：虚拟机及其指令系统： 大多数编译程序不产生绝对地址的机器代码，而是大多数编译程序不产生绝对地址的机器代码，而是以以汇编语言程序汇编语言程序作为输出，使代码生成阶段变得容易。作为输出，使代码生成阶段变得容易。 此外，此外，指令集的选择指令集的选择以及以及指令的执行速度指令的执行速度问题都问题都是是重要因素重要因素。为了使算法具有通用性，这里采用的是：。为了使算法具有通用性，这里采用的是： 虚拟机寄存器虚拟机寄存器 R0 , R1 , , Rn-1 虚拟机指令系统虚拟机指令系统 指令的

3、基本形式：指令的基本形式：op Ri , Rj/M操作码操作码变量的内变量的内存地址存地址含义：含义： Ri = (Ri) op (Rj)Ri = (Ri) op (M)或或【注注】若若 op 为单目运算，则含义是：为单目运算，则含义是：Ri = op(Rj/M)9.1 目标代码生成的基本问题目标代码生成的基本问题(续续1) 常用的指令：常用的指令：LD Ri, Rj/M Ri = (Rj/M)ST Ri, Rj/M Rj/M =(Ri)FJ Ri, M 若若 (Ri)=false 则转则转 MTJ Ri, M 若若 (Ri)=true 则转则转 MJMP _, M 无条件转无条件转 MADD

4、 Ri, Rj/M Ri =(Ri) + (Rj/M)SUB Ri, Rj/M Ri =(Ri) - - (Rj/M)MUL Ri, Rj/M Ri =(Ri) * * (Rj/M)DIV Ri, Rj/M Ri =(Ri) / (Rj/M)此外还有下述此外还有下述 操作码操作码 op ：LT(),EQ(=),LE(=),NE(!=)AND(&),OR(|),NO(!)取、存取、存转转 向向算术算术运算运算关系、逻关系、逻辑运算辑运算9.1 目标代码生成的基本问题目标代码生成的基本问题(续续2).活跃变量与非活跃变量活跃变量与非活跃变量1. 变量的定义点和应用点变量的定义点和应用点 设

5、有四元式：设有四元式：q( B C A )B,C的应用点的应用点(q)A的定义点的定义点(q)2. 活跃变量与非活跃变量活跃变量与非活跃变量【活跃变量活跃变量】一个一个变量变量从某时刻从某时刻(q)起起，到下一个到下一个定义点止，其间若定义点止，其间若有应用点有应用点，则称该变量在，则称该变量在q是活是活跃的跃的(y)，否则称否则称该该变量变量在在q是非活跃的是非活跃的(n)。 【注注】我们是在我们是在一个基本块内一个基本块内讨论讨论变量的活跃信息变量的活跃信息的，为了处理方便，假定：的，为了处理方便，假定：(1) 临时变量在临时变量在基本块出口基本块出口后后是非活跃的是非活跃的(n)； (2

6、) 非临时变量在非临时变量在基本块出口基本块出口后后是活跃的是活跃的(y)； 9.1 目标代码生成的基本问题目标代码生成的基本问题(续续3)【例例9.1】求下述基本块内变量的求下述基本块内变量的活跃信息活跃信息：x=(a+b)/(a*(a+b);i=a+b;【解解】令令 A(i)中的中的 i 为为变量变量A 在某点的在某点的活跃信息活跃信息(y/n)；则有四元式序列：则有四元式序列：(1) ( + a b t1 )(2) ( * a t1 t3 )(3) ( / t1 t3 x )(4) ( = t1 _ i )(1) ( + a b t1 )(2) ( + a b t2 )(3) (* a

7、t2 t3 )(4) ( / t1 t3 t4 )(5) ( = t4 _ x )(6) ( + a b t5 )(7) ( = t5 _ i )优化后优化后(1) (+ a(y) b (y) t1(y) )(2) (* a(y) t1(y) t3(y) )(3) (/ t1(y) t3(n) x(y) )(4) (= t1(n) _ i(y) ) 附有附有活跃信息活跃信息的四元式：的四元式：9.1 目标代码生成的基本问题目标代码生成的基本问题(续续4).寄存器的分配问题寄存器的分配问题 寄存器寄存器操作快操作快且且指令短指令短，如何充分利用它如何充分利用它？2. 寄存器寄存器分配规则分配规则

8、：设当前四元式：设当前四元式：q: A=B C(1)【主动释放主动释放】如果如果B已经在寄存器已经在寄存器Ri中，则选择中，则选择Ri: 若若 B 活跃活跃，则要保存，则要保存B的值，方法是：若有空闲的值，方法是：若有空闲寄存器寄存器Rj，则生成指令则生成指令 ST Ri,Rj； 否则生成指令否则生成指令 ST Ri,B； 修改修改描述表：描述表：在在Ri中删除中删除 B，填写，填写A。(2)【选空闲者选空闲者】从空闲寄存器中选一从空闲寄存器中选一 Ri； 并把并把 A 填入填入Ri的描述表中。的描述表中。 (3)【强迫释放强迫释放】剥夺一个剥夺一个 Ri，具体处理办法同规则，具体处理办法同规

9、则(1)。1. 设置设置描述表描述表，记录记录寄存器寄存器和和变量变量的当前状态的当前状态： 某个寄存器保留着哪个变量的值某个寄存器保留着哪个变量的值; 某个变量的值是在某寄存器中还是在内存中。某个变量的值是在某寄存器中还是在内存中。如何如何为为A分配分配寄存寄存器？器？若若 可交换可交换,则则C也可也可!9.1 目标代码生成的基本问题目标代码生成的基本问题(续续5) 目标代码生成是以目标代码生成是以基本块为单位基本块为单位的，在生成目标代的，在生成目标代码时要注意如下三个问题：码时要注意如下三个问题：(1) 基本块基本块开始开始时所有寄存器应是时所有寄存器应是空闲空闲的；基本块的；基本块结束

10、结束时应时应释放释放所占用的寄存器。所占用的寄存器。(2) 一个变量被赋值时，要分配一个一个变量被赋值时，要分配一个寄存器寄存器保留其值，保留其值，并且要填写相应的并且要填写相应的描述表描述表。【例例9.2】设有语句片断：设有语句片断：while (i10) x=(a*b)/(a+(a*b);i=x;i=1;. 目标代码生成问题目标代码生成问题(3) 为了生成为了生成高效的目标代码高效的目标代码，生成算法中要引用，生成算法中要引用寄存寄存器的分配原则器的分配原则和和变量的活跃信息。变量的活跃信息。 目标代码生成示例：目标代码生成示例：假定：有两个可用寄存器假定：有两个可用寄存器 R0,R1则从

11、四元式到目标代码生成过程如下所示：则从四元式到目标代码生成过程如下所示：描述表描述表while (i10) x=(a*b)/(i+(a*b);i=x;i=1; OBJp QTq R0 R1 内存内存BFJ R0, ? LD R0,i GT R0,10JMP _, LD R0,1 ST R0,iit1LD R0,a MUL R0,b t2ST R0,R1 ADD R0,i DIV R1,R0ST R1,x11 12t3xST R1,i13ix14t214ab(1) (= 1 _ i )(2) (wh _ _ _ )(3) ( i 10 t1 )(4) ( do t1 _ _ )(5) (* a

12、b t2 )(6) (+ i t2 t3 )(7) (/ t2 t3 x )(8) (= x _ i )(9) (we _ _ _ )(10)9.2 一个简单代码生成器设计一个简单代码生成器设计. 生成环境生成环境v 虚拟机虚拟机：单一寄存器：单一寄存器 R ; 指令形式指令形式 p:(op R , M )变量内存地址变量内存地址v 表、区和栈表、区和栈： SYMBLi 符号表；符号表； QTq 四元式区四元式区(附有变量的附有变量的活跃信息活跃信息)； OBJp 目标代码区；目标代码区； SEMm 语义栈语义栈(登记待登记待返填返填的目标地址的目标地址)；R = (R)op(M)含义：含义：

13、R = op(M)或或 CODE(op R,M;)(送代码函数送代码函数)把目标代码送目标区；把目标代码送目标区； RDV 寄存器状态变量；寄存器状态变量；v 变量和函数变量和函数：RDV= 0 (R空闲空闲) ； RDV= X (R被被X占用占用)； 可送多个代码可送多个代码 BACK(pi,pj)(返填函数返填函数)把地址把地址 pj 返填到地址返填到地址 pi 中；中；9.2 一个简单代码生成器设计一个简单代码生成器设计(续续1)开始开始预处理预处理取下一取下一基本块基本块取到了取到了变量变量活跃信息活跃信息生成生成取下一取下一四元式四元式：q基本块基本块出口出口结束结束结束处理结束处理

14、RDV=0执行执行q生成生成执行执行q生成生成yynn包括划分包括划分基本块基本块. 主控程序主控程序. 目标代码生成算法目标代码生成算法q 单寄存器下的目标代码单寄存器下的目标代码生成要点生成要点： 1.表达式四元式表达式四元式 q:( B C A ) 释放寄存器，编运算指令，释放寄存器，编运算指令，A不存储但登记在不存储但登记在RDV中！中！ 2.赋值四元式赋值四元式 q:( = B _ A ) 编取编取B(B在在R中则免，否则中则免，否则释放寄存器释放寄存器)、存、存A指令！指令！ 3.转向四元式转向四元式 q:( do B _ _ )， 释放寄存器，编转向指令，保存该地址于释放寄存器，

15、编转向指令，保存该地址于SEM栈中！栈中！ 【释放寄存器释放寄存器】编编存储存储指令，保存占有寄存器的指令，保存占有寄存器的活跃活跃变量变量值；通常发生在如下两个时刻：值；通常发生在如下两个时刻：目标代码生成是以目标代码生成是以单个四元式单个四元式为单位进行的！为单位进行的！注注(1) 为结果变量申请寄存器时为结果变量申请寄存器时(2) 基本块出口时基本块出口时. 目标代码生成算法目标代码生成算法(续续2) 1. 表达式四元式的目标代码生成：表达式四元式的目标代码生成： 设当前扫描的四元式设当前扫描的四元式 q: ( B C A) (1) 按检索到的信息生成目标代码：按检索到的信息生成目标代码

16、： 算符算符 对应对应的的操作码操作码 若若 RDV=0 则则 CODE( LD R,B ； R,C ); 若若 RDV=B 则则 若若 B(y) 则则 CODE( ST R,B ； R,C ); 否则否则 CODE( R,C ); 若若 RDV=C 且且 可交换可交换 则则 若若 C(y) 则则 CODE( ST R,C ； R,B ); 否则否则 CODE( R,B ); 若若 D(y) 则则 CODE( ST R,D ; LD R,B ; R,C );否则否则 CODE( LD R,B ; R,C );(2) 变量变量 A 申请寄存器申请寄存器 RDV = A ; 若若 RDV=D（上述

17、三种情况之外上述三种情况之外 ） 则则 如如 B+C OBJp QTqBSEMRDV. 目标代码生成算法目标代码生成算法(续续1)【例例9.3】设有赋值语句（四元式序列）：设有赋值语句（四元式序列）：x=a-(a+b)*(c-d)+(a+b)/2;ST R,t1 LD R,c t1(y)LD R,a ADD R,b(1) (+ a(y) b(y) t1(y)(2) (- c(y) d(y) t2(y)(3) (* t1(y) t2(n) t3(y)(4) (- a(y) t3(n) t4(y)(5) (/ t1(n) 2 t5(y)(6) (+ t4(n) t5(n) x(y) t2(y)SU

18、B R,dMUL R,t1 t3(y)ST R,t3 LD R,aSUB R,t3 t4(y)ST R,t4 LD R,t11112DIV R,2 t5(y)13ADD R,t4 x(y) 设当前四元式设当前四元式 q: (= B _ A). 目标代码生成算法目标代码生成算法(续续3)(1) 若若 RDV=0 则则 CODE( LD R,B ; ST R,A ); (2) 若若 RDV=B 则则 CODE( ST R,A );(3) 若若 RDV=D（D!=B ）则）则 若若 D(y) 则则 CODE( ST R,D ; LD R,B ; ST R,A ); 2. 赋值语句四元式的目标代码生成

19、：赋值语句四元式的目标代码生成：RDV =B RDV =B;否则否则 CODE( LD R,B ; ST R,A ); . 目标代码生成算法目标代码生成算法(续续4)【例例9.4】设有条件语句（四元式序列）：设有条件语句（四元式序列）：if(ab)x=(a+b)*c;else x=5-a*b; OBJp QTqBSEMRDVFJ R, ? t1(y)LD R,a GT R,bt2(y)LD R,a ADD R,bMUL R,cx(y)JMP_,? LD R,a MUL R,bt3(y) ST R,t3 LD R,51213SUB R,t3x(y)14ST R,x1515ST R,x 11nex

20、t (1) ( a(y) b(y) t1(y)(2) (if t1(n) _ _ )(3) (+ a(y) b(y) t2(y)(4) (* t2(n) c(y) x(y)(5) (el _ _ _ )(6) (* a(y) b(y) t3(y)(7) (- - 5 t3(n) x(y)(8) (ie _ _ _ ) (三三) 设当前四元式设当前四元式 q:( ie _ _ _ ) (二二) 设当前四元式设当前四元式 q:( el _ _ _ ). 目标代码生成算法目标代码生成算法(续续5)(3) 若若 RDV=D（D!=B） 则则 (1) 返填转向地址返填转向地址： POP(p);BACK(

21、p,p+2)v 返填转向地址返填转向地址： POP(p);BACK(p,p+1) 若若 D(y) 则则 CODE( ST R,D ; LD R,B ;FJ R,_ ); PUSH(p) ；RDV =0; 否则否则 CODE( LD R,B ;FJ R,_ ); (2) 编转向指令编转向指令：CODE( JMP _, _ ); PUSH(p) (一一) 设当前四元式设当前四元式 q:( if B _ _ )(1) 若若 RDV=0 则则 CODE( LD R,B ; FJ R,_ ); PUSH(p)； 3. 条件语句四元式的目标代码生成：条件语句四元式的目标代码生成：(2) 若若 RDV=B

22、则则 CODE( FJ R,_ ); PUSH(p)；RDV =0;SEM栈栈顶地址弹顶地址弹到到p中中把地址把地址p+2填到填到p中中当前目标当前目标代码编号代码编号 back. 目标代码生成算法目标代码生成算法(续续6) OBJp QTqBSEMRDVFJ R, ? LD R,i LT R,10LD R,a MUL R,bST R,t2ST R,t3DIV R,t31414JMP _, 【例例9.5】设有循环语句（四元式序列）：设有循环语句（四元式序列）：while (i10) x=(a*b)/(i+(a*b);i=x;ADD R,i LD R,t2ST R,i11ST R,12xt1(y

23、)t2(y)x(y)t3(y)13(4) (* a(y) b(y) t2(y)(1) (wh _ _ _ )(2) ( i(y) 10 t1(y)(3) ( do t1(n) _ _ )(5) (+ i(y) t2(y) t3(y)(6) (/ t2(n) t3(n) x(y)(7) (= x(y) _ i(y)(8) (we _ _ _ )(9)next (一一) 设当前四元式设当前四元式 q:(wh _ _ _ )v 记住表达式入口地址：记住表达式入口地址： PUSH(p+1). 目标代码生成算法目标代码生成算法(续续7) 4. 循环语句四元式的目标代码生成：循环语句四元式的目标代码生成：

24、(二二) 设当前四元式设当前四元式 q:(do B _ _ )(1) 若若 RDV=0 则则 CODE( LD R,B ; FJ R,_ ); PUSH(p)； (2) 若若 RDV=B 则则 CODE( FJ R,_ ); PUSH(p); RDV =0;(3) 若若 RDV=D（D!=B） 则则 若若 D(y) 则则 CODE( ST R,D ; LD R,B ;FJ R,_ ); PUSH(p); RDV =0;否则否则 CODE( LD R,B ;FJ R,_ ); (三三) 设当前四元式设当前四元式 q:(we _ _ _ )(1) 返填转向地址返填转向地址： POP(p);BACK

25、(p,p+2);(2) 编转向表达式入口指令编转向表达式入口指令：POP(p);CODE(JMP _,p); back9.3.1 基本块内基本块内活跃信息活跃信息求解算法求解算法 支持支持: (1) 在符号表上增设两个信息项（在符号表上增设两个信息项（U,L）:LUname待用信息待用信息活跃信息活跃信息(2) 四元式中变量的附加信息项：四元式中变量的附加信息项：X(U,L) 取值：取值：U=n/q(不待用不待用/q待用待用),q为四元式序号；为四元式序号； 取值：取值：L=n/y(不活跃不活跃/活跃活跃) ；(1) 初值：基本块内各变量初值：基本块内各变量 SYMBLX(U,L)分别填写：分

26、别填写：若若 X为为非临时变量非临时变量 则置则置 X(n,y) , 否则置否则置 X(n,n)(2) 逆序逆序扫描基本块内各四元式扫描基本块内各四元式(设为设为 q:( B C A) ):执行：执行： QTq:A(U,L) = SYMBLA(U,L); SYMBLA(U,L) =(n,n); QTq:B,C(U,L) = SYMBLB,C(U,L); SYMBLB,C(U,L) =(q,y); 算法算法9.3 多寄存器下的目标代码生成算法多寄存器下的目标代码生成算法 L UXabcdt1t2xt5t4t3 9.3 多寄存器下的目标代码生成算法多寄存器下的目标代码生成算法(续续1) 【例例9.

27、6】基本块内下述四元基本块内下述四元式序列活跃信息生成过程：式序列活跃信息生成过程：QTq: q:( B(U,L) C(U,L) A(U,L)SYMBLX(U,L)(1) (+ a( , ) b( , ) t1( , )(2) (- c( , ) d( , ) t2( , )(3) (* t1( , ) t2( , ) t3( , )(4) (- a( , ) t3( , ) t4( , )(5) (/ t1( , ) 2 t5( , ) (6) (+ t4( , ) t5( , ) x( , )ynynynynnnnnynnnnnnnn ynnn nn n6y6y6 ynnn n5y6 yn

28、nn y4yn n4y4 ynn5 y3yn n3y3 ynnn y2yn y 2y3 ynn4 y1yn y1y9.3 多寄存器下的目标代码生成算法多寄存器下的目标代码生成算法(续续2) 支持支持: (1) 设置设置描述表描述表 RDLR1,R2,Rn;M，记录寄存记录寄存(2) 几个变量可共享同一寄存器！如几个变量可共享同一寄存器！如 RDL.Ri=X,Y;算法算法器器Ri，变量，变量X的的现行值状态现行值状态！9.3.2 寄存器分配函数寄存器分配函数 GETR(q) 设当前扫描的四元式为设当前扫描的四元式为 q:( B C A ). 【主动释放主动释放】 若若 B(U,L)=( ,y)

29、且且 B RDL.M 则则 若有若有 RDL.Rj=，则则否则否则 CODE( ST Ri,B );RDL.Ri- -=B; RDL.M+=B; 否则否则 RDL.Ri- -=B;1. 若有若有Ri，使，使RDL.Ri=B ;则则 CODE( ST Ri,Rj );RDL.Ri- -=B;RDL.Rj=B; R=Ri;转转 .;删除删除B加入加入B存入存入B仅有仅有 2. 若有若有Ri，使，使 RDL.Ri=C 且且 可交换可交换，则，则 交换交换B,C(改变四元式改变四元式)；转；转 ;.【选空闲者选空闲者】若有若有RDL.Ri=,则则 R=Ri ;转转 ;.【强迫释放强迫释放】RDL.M- -=A; RETURN( R,B=LOCR(B);C=LOCR(C) ); 剥夺一个剥夺一个 Ri (剥夺条件是剥夺条件是 对对 每一个每一个DRDL.Ri： D( ,n) 或或 D(较大较大,y) , 或或 Ri中共享变量数最少中共享变量数最少,) 对每一个对每一个 DRDL.Ri:.【实施分配实施分配】 若若 D(U,L)=( ,y)且且 D RDL.M 则则 CODE( ST Ri,D ); RDL.Ri- -=D;RDL