第9章 目标代码生成

1、第9章目标代码及其生成,目标代码生成是编译的最后一个阶段，其功能表示如下：,其中：,9.1目标代码生成的基本问题,9.3多寄存器下的目标代码生成算法,内容提要,9.2一个简单代码生成器设计,9.1目标代码生成的基本问题,.目标代码选择问题,虚拟机及其指令系统：,大多数编译程序不产生绝对地址的机器代码，而是以汇编语言程序作为输出，使代码生成阶段变得容易。此外，指令集的选择以及指令的执行速度问题都是重要因素。为了使算法具有通用性，这里采用的是：,虚拟机寄存器R0,R1,Rn-1,虚拟机指令系统,操作码,变量的内存地址,含义：,Ri=(Ri)op(Rj),【注】若op为单目运算，则含义是：,Ri=o

2、p(Rj/M),9.1目标代码生成的基本问题(续1),常用的指令：,LDRi,Rj/MRi=(Rj/M),STRi,Rj/MRj/M=(Ri),FJRi,M若(Ri)=false则转M,TJRi,M若(Ri)=true则转M,JMP_,M无条件转M,ADDRi,Rj/MRi=(Ri)+(Rj/M),SUBRi,Rj/MRi=(Ri)-(Rj/M),MULRi,Rj/MRi=(Ri)*(Rj/M),DIVRi,Rj/MRi=(Ri)/(Rj/M),此外还有下述操作码op：,LT(),EQ(=),LE(=),NE(!=),AND(i=a+b;,【解】令A(i)中的i为变量A在某点的活跃信息(y/n

3、)；,则有四元式序列：,附有活跃信息的四元式：,9.1目标代码生成的基本问题(续4),.寄存器的分配问题,寄存器操作快且指令短，如何充分利用它？,2.寄存器分配规则：设当前四元式：q:A=BC,(1)【主动释放】如果B已经在寄存器Ri中，则选择Ri:,若B活跃，则要保存B的值，方法是：若有空闲,寄存器Rj，则生成指令STRi,Rj；,否则生成指令STRi,B；,修改描述表：在Ri中删除B，填写A。,(2)【选空闲者】从空闲寄存器中选一Ri；并把A填入Ri的描述表中。,(3)【强迫释放】剥夺一个Ri，具体处理办法同规则(1)。,1.设置描述表，记录寄存器和变量的当前状态：,某个寄存器保留着哪个变

4、量的值;,某个变量的值是在某寄存器中还是在内存中。,如何为A分配寄存器？,若可交换,则C也可!,9.1目标代码生成的基本问题(续5),目标代码生成是以基本块为单位的，在生成目标代码时要注意如下三个问题：,(1)基本块开始时所有寄存器应是空闲的；基本块结束时应释放所占用的寄存器。,(2)一个变量被赋值时，要分配一个寄存器保留其值，并且要填写相应的描述表。,【例9.2】设有语句片断：,.目标代码生成问题,(3)为了生成高效的目标代码，生成算法中要引用寄存器的分配原则和变量的活跃信息。,目标代码生成示例：,假定：有两个可用寄存器R0,R1,则从四元式到目标代码生成过程如下所示：,描述表,FJR0,?

5、,LDR0,iGTR0,10,JMP_,LDR0,1STR0,i,i,t1,LDR0,aMULR0,b,t2,STR0,R1ADDR0,i,DIVR1,R0,STR1,x,t3,x,STR1,i,i,x,t2,ab,9.2一个简单代码生成器设计,.生成环境,虚拟机：单一寄存器R;指令形式p:(opR,M),变量内存地址,表、区和栈：,SYMBLi符号表；,QTq四元式区(附有变量的活跃信息)；,OBJp目标代码区；,SEMm语义栈(登记待返填的目标地址)；,R=(R)op(M),含义：,R=op(M),或,CODE(opR,M;)(送代码函数)把目标代码送目标区；,RDV寄存器状态变量；,变量

6、和函数：,可送多个代码,BACK(pi,pj)(返填函数)把地址pj返填到地址pi中；,9.2一个简单代码生成器设计(续1),.主控程序,.目标代码生成算法,单寄存器下的目标代码生成要点：,1.表达式四元式q:(BCA),释放寄存器，编运算指令，A不存储但登记在RDV中！,2.赋值四元式q:(=B_A),编取B(B在R中则免，否则释放寄存器)、存A指令！,3.转向四元式q:(doB_)，,释放寄存器，编转向指令，保存该地址于SEM栈中！,【释放寄存器】编存储指令，保存占有寄存器的活跃变量值；通常发生在如下两个时刻：,目标代码生成是以单个四元式为单位进行的！,注,(1)为结果变量申请寄存器时,(

7、2)基本块出口时,.目标代码生成算法(续2),1.表达式四元式的目标代码生成：,设当前扫描的四元式q:(BCA),(1)按检索到的信息生成目标代码：,算符对应的操作码,若RDV=0则CODE(LDR,B；R,C);,若RDV=B则,若B(y)则CODE(STR,B；R,C);,否则CODE(R,C);,若RDV=C且可交换则,若C(y)则CODE(STR,C；R,B);,否则CODE(R,B);,若D(y)则CODE(STR,D;LDR,B;R,C);,否则CODE(LDR,B;R,C);,(2)变量A申请寄存器RDV=A;,若RDV=D（上述三种情况之外）则,如B+C,.目标代码生成算法(续

8、1),【例9.3】设有赋值语句（四元式序列）：,x=a-(a+b)*(c-d)+(a+b)/2;,STR,t1LDR,c,t1(y),LDR,aADDR,b,t2(y),SUBR,d,MULR,t1,t3(y),STR,t3LDR,a,SUBR,t3,t4(y),STR,t4LDR,t1,DIVR,2,t5(y),ADDR,t4,x(y),.目标代码生成算法(续3),(1)若RDV=0则CODE(LDR,B;STR,A);,(2)若RDV=B则CODE(STR,A);,(3)若RDV=D（D!=B）则,若D(y)则CODE(STR,D;LDR,B;STR,A);,2.赋值语句四元式的目标代码生

9、成：,RDV=B,RDV=B;,否则CODE(LDR,B;STR,A);,.目标代码生成算法(续4),【例9.4】设有条件语句（四元式序列）：,if(ab)x=(a+b)*c;elsex=5-a*b;,FJR,?,t1(y),LDR,aGTR,b,t2(y),LDR,aADDR,b,MULR,c,x(y),JMP_,?,LDR,aMULR,b,t3(y),STR,t3LDR,5,SUBR,t3,x(y),STR,x,STR,x,next,.目标代码生成算法(续5),(3)若RDV=D（D!=B）则,(1)返填转向地址：POP(p);BACK(p,p+2),返填转向地址：POP(p);BACK(

10、p,p+1),若D(y)则CODE(STR,D;LDR,B;FJR,_);,PUSH(p)；RDV=0;,否则CODE(LDR,B;FJR,_);,(2)编转向指令：CODE(JMP_,_);PUSH(p),(1)若RDV=0则CODE(LDR,B;FJR,_);PUSH(p)；,3.条件语句四元式的目标代码生成：,(2)若RDV=B则CODE(FJR,_);PUSH(p)；RDV=0;,SEM栈顶地址弹到p中,把地址p+2填到p中,当前目标代码编号,back,.目标代码生成算法(续6),FJR,?,LDR,iLTR,10,LDR,aMULR,b,STR,t2,STR,t3,DIVR,t3,J

11、MP_,【例9.5】设有循环语句（四元式序列）：,ADDR,i,LDR,t2,t1(y),t2(y),x(y),t3(y),next,记住表达式入口地址：PUSH(p+1),.目标代码生成算法(续7),4.循环语句四元式的目标代码生成：,(1)若RDV=0则CODE(LDR,B;FJR,_);PUSH(p)；,(2)若RDV=B则CODE(FJR,_);PUSH(p);RDV=0;,(3)若RDV=D（D!=B）则,若D(y)则CODE(STR,D;LDR,B;FJR,_);,PUSH(p);RDV=0;,否则CODE(LDR,B;FJR,_);,(1)返填转向地址：POP(p);BACK(p

12、,p+2);,(2)编转向表达式入口指令：POP(p);CODE(JMP_,p);,back,9.3.1基本块内活跃信息求解算法,支持:(1)在符号表上增设两个信息项（U,L）:,待用信息,活跃信息,(2)四元式中变量的附加信息项：X(U,L),取值：U=n/q(不待用/q待用),q为四元式序号；,取值：L=n/y(不活跃/活跃)；,(1)初值：基本块内各变量SYMBLX(U,L)分别填写：,若X为非临时变量则置X(n,y),否则置X(n,n),(2)逆序扫描基本块内各四元式(设为q:(BCA):,执行：,QTq:A(U,L)=SYMBLA(U,L);,SYMBLA(U,L)=(n,n);,Q

13、Tq:B,C(U,L)=SYMBLB,C(U,L);,SYMBLB,C(U,L)=(q,y);,算法,9.3多寄存器下的目标代码生成算法,9.3多寄存器下的目标代码生成算法(续1),【例9.6】基本块内下述四元式序列活跃信息生成过程：,QTq:,SYMBLX(U,L),ny,n,n,nn,nn,6,y,6,y,6y,n,n,nn,5,y,6y,n,n,ny,4,y,nn,4,y,4y,n,n,5y,3,y,nn,3,y,3y,n,n,ny,2,y,ny,2,y,3y,n,n,4y,1,y,ny,1,y,9.3多寄存器下的目标代码生成算法(续2),支持:(1)设置描述表RDLR1,R2,Rn;M

14、，记录寄存,(2)几个变量可共享同一寄存器！如RDL.Ri=X,Y;,算法,器Ri，变量X的现行值状态！,9.3.2寄存器分配函数GETR(q),设当前扫描的四元式为q:(BCA),.【主动释放】,若B(U,L)=(,y)且BRDL.M则,若有RDL.Rj=，则,否则CODE(STRi,B);RDL.Ri-=B;RDL.M+=B;,否则RDL.Ri-=B;,1.若有Ri，使RDL.Ri=B;则,CODE(STRi,Rj);RDL.Ri-=B;RDL.Rj=B;,R=Ri;转.;,删除B,加入B,存入B,仅有,2.若有Ri，使RDL.Ri=C且可交换，则,交换B,C(改变四元式)；转;,.【选空

15、闲者】,若有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)且DRDL.M则,CODE(STRi,D);RDL.Ri-=D;RDL.M+=D;,否则RDL.Ri-=D;,R=Ri;转;,取变量B的现行值地址，寄存器优先！,9.3多寄存器下的目标代码生成算法(续3),9.3多寄存器下的目标代码生成算法(续4),9.3.3目标代码生成算法设计,.表达式的目标代码生成,1.GETR(q,R,B,C);,2.若RB;则CODE(LDR,B;R,C;);,否则CODE(R,C);,3.对所有Ri,有RDL.Ri-=A;RDL.M-=A;RDL.R=A;,.赋值四元式的目标代码生成,支持:四元式的活跃信息；寄存器分配算法；,1.GETR(q,R,B,C);,2.若RB;则CODE(LDR,B);RDL.R=B;,3.对所有