第9章 目标代码生成

第9章目标代码及其生成目标代码生成是编译的最后一个阶段，其功能表示如下：目标生成中间代码目标代码符号表其中：中间代码—逆波兰式，三元式，四元式，语义树；…目标代码—机器语言，汇编语言，…符号表—变量的语义词典，…9.1目标代码生成的基本问题9.3多寄存器下的目标代码生成算法内容提要9.2一个简单代码生成器设计9.1目标代码生成的基本问题Ⅰ.目标代码选择问题虚拟机及其指令系统：大多数编译程序不产生绝对地址的机器代码，而是以汇编语言程序作为输出，使代码生成阶段变得容易。此外，指令集的选择以及指令的执行速度问题都是重要因素。为了使算法具有通用性，这里采用的是：•虚拟机寄存器R0,R1,…,Rn-1•虚拟机指令系统※指令的基本形式：opRi,Rj/M操作码变量的内存地址含义：Ri=(Ri)op(Rj)Ri=(Ri)op(M)或【注】若op为单目运算，则含义是：Ri=op(Rj/M)9.1目标代码生成的基本问题(续1)※常用的指令：LDRi,Rj/M……Ri=(Rj/M)STRi,Rj/M……Rj/M=(Ri)FJRi,M……若(Ri)==false则转MTJRi,M……若(Ri)==true则转MJMP_,M……无条件转MADDRi,Rj/M……Ri=(Ri)+(Rj/M)SUBRi,Rj/M……Ri=(Ri)-(Rj/M)MULRi,Rj/M……Ri=(Ri)*(Rj/M)DIVRi,Rj/M……Ri=(Ri)/(Rj/M)此外还有下述操作码op：LT(),GT(),EQ(==),LE(=),GE(=),NE(!=)AND(&&),OR(||),NO(!)取、存转向算术运算关系、逻辑运算9.1目标代码生成的基本问题(续2)Ⅱ.活跃变量与非活跃变量1.变量的定义点和应用点※设有四元式：q(BCA)B,C的应用点(q)A的定义点(q)2.活跃变量与非活跃变量【活跃变量】一个变量从某时刻(q)起，到下一个定义点止，其间若有应用点，则称该变量在q是活跃的(y)，否则称该变量在q是非活跃的(n)。【注】我们是在一个基本块内讨论变量的活跃信息的，为了处理方便，假定：(1)临时变量在基本块出口后是非活跃的(n)；(2)非临时变量在基本块出口后是活跃的(y)；9.1目标代码生成的基本问题(续3)【例9.1】求下述基本块内变量的活跃信息：x=(a+b)/(a*(a+b));i=a+b;【解】令A(i)中的i为变量A在某点的活跃信息(y/n)；则有四元式序列：(1)(+abt1)(2)(*at1t3)(3)(/t1t3x)(4)(=t1_i)(1)(+abt1)(2)(+abt2)(3)(*at2t3)(4)(/t1t3t4)(5)(=t4_x)(6)(+abt5)(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.寄存器分配规则：设当前四元式：q:A=BC(1)【主动释放】如果B已经在寄存器Ri中，则选择Ri:①若B活跃，则要保存B的值，方法是：若有空闲寄存器Rj，则生成指令STRi,Rj；否则生成指令STRi,B；②修改描述表：在Ri中删除B，填写A。(2)【选空闲者】从空闲寄存器中选一Ri；并把A填入Ri的描述表中。(3)【强迫释放】剥夺一个Ri，具体处理办法同规则(1)。1.设置描述表，记录寄存器和变量的当前状态：①某个寄存器保留着哪个变量的值;②某个变量的值是在某寄存器中还是在内存中。如何为A分配寄存器？若可交换,则C也可!9.1目标代码生成的基本问题(续5)目标代码生成是以基本块为单位的，在生成目标代码时要注意如下三个问题：(1)基本块开始时所有寄存器应是空闲的；基本块结束时应释放所占用的寄存器。(2)一个变量被赋值时，要分配一个寄存器保留其值，并且要填写相应的描述表。【例9.2】设有语句片断：while(i10){x=(a*b)/(a+(a*b));i=x;}i=1;Ⅳ.目标代码生成问题(3)为了生成高效的目标代码，生成算法中要引用寄存器的分配原则和变量的活跃信息。※目标代码生成示例：※假定：有两个可用寄存器R0,R1则从四元式到目标代码生成过程如下所示：描述表while(i10){x=(a*b)/(i+(a*b));i=x;}i=1;OBJ[p]QT[q]R0R1内存B⑤FJR0,?LDR0,i④GTR0,10JMP_,①LDR0,1②STR0,iit1⑥LDR0,a⑦MULR0,bt2⑧STR0,R1⑨ADDR0,i⑩DIVR1,R0STR1,x1112t3xSTR1,i13ix14t214ab③③(1)(=1_i)(2)(wh___)(3)(i10t1)(4)(dot1__)(5)(*abt2)(6)(+it2t3)(7)(/t2t3x)(8)(=x_i)(9)(we___)(10)9.2一个简单代码生成器设计Ⅰ.生成环境虚拟机：单一寄存器R;指令形式p:(opR,M)变量内存地址表、区和栈：•SYMBL[i]…符号表；•QT[q]…四元式区(附有变量的活跃信息)；•OBJ[p]…目标代码区；•SEM[m]…语义栈(登记待返填的目标地址)；R=(R)op(M)含义：R=op(M)或CODE(opR,M;…)…(送代码函数)把目标代码送目标区；RDV…寄存器状态变量；变量和函数：RDV==0(R空闲)；RDV==X(R被X占用)；可送多个代码BACK(pi,pj)…(返填函数)把地址pj返填到地址pi中；9.2一个简单代码生成器设计(续1)开始预处理取下一基本块取到了变量活跃信息生成取下一四元式：q基本块出口结束结束处理RDV=0执行q生成执行q生成yynn包括划分基本块Ⅱ.主控程序Ⅲ.目标代码生成算法单寄存器下的目标代码生成要点：1.表达式四元式q:(BCA)※释放寄存器，编运算指令，A不存储但登记在RDV中！2.赋值四元式q:(=B_A)※编取B(B在R中则免，否则释放寄存器)、存A指令！3.转向四元式q:(doB__)，…※释放寄存器，编转向指令，保存该地址于SEM栈中！【释放寄存器】编存储指令，保存占有寄存器的活跃变量值；通常发生在如下两个时刻：目标代码生成是以单个四元式为单位进行的！注(1)为结果变量申请寄存器时(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+COBJ[p]QT[q]BSEMRDVⅢ.目标代码生成算法(续1)【例9.3】设有赋值语句（四元式序列）：x=a-(a+b)*(c-d)+(a+b)/2;…③STR,t1④LDR,ct1(y)①LDR,a②ADDR,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)2t5(y))(6)(+t4(n)t5(n)x(y))t2(y)⑤SUBR,d⑥MULR,t1t3(y)⑦STR,t3⑧LDR,a⑨SUBR,t3t4(y)⑩STR,t4LDR,t11112DIVR,2t5(y)13ADDR,t4x(y)…•设当前四元式q:(=B_A)Ⅲ.目标代码生成算法(续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.赋值语句四元式的目标代码生成：RDV=B②RDV=B;否则CODE(LDR,B;STR,A);Ⅲ.目标代码生成算法(续4)【例9.4】设有条件语句（四元式序列）：if(ab)x=(a+b)*c;elsex=5-a*b;OBJ[p]QT[q]BSEMRDV③FJR,?t1(y)①LDR,a②GTR,bt2(y)④LDR,a⑤ADDR,b⑥MULR,cx(y)JMP_,?LDR,a⑩MULR,bt3(y)STR,t3LDR,51213SUBR,t3x(y)14⑧STR,x15③⑨15⑦STR,x⑧⑨11next(1)(a(y)b(y)t1(y))(2)(ift1(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)(-5t3(n)x(y))(8)(ie___)(三)设当前四元式q:(ie___)(二)设当前四元式q:(el___)Ⅲ.目标代码生成算法(续5)(3)若RDV==D（D!=B）则(1)返填转向地址：POP(p`);BACK(p`,p+2)返填转向地址：POP(p`);BACK(p`,p+1)①若D(y)则CODE(STR,D;LDR,B;FJR,_);②PUSH(p)；RDV=0;否则CODE(LDR,B;FJR,_);(2)编转向指令：CODE(JMP_,_);PUSH(p)(一)设当前四元式q:(ifB__)(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)OBJ[p]QT[q]BSEMRDV③FJR,?①LDR,i②LTR,10④LDR,a⑤MULR,b⑥STR,t2⑧STR,t3⑩DIVR,t31414JMP_,【例9.5】设有循环语句（四元式序列）：while(i10){x=(a*b)/(i+(a*b));i=x;}①①①③⑦ADDR,i⑨LDR,t2STR,i11STR,12xt1(y)t2(y)x(y)t3(y)13(4)(*a(y)b(y)t2(y))(1)(wh___)(2)(i(y)10t1(y))(3)(dot1(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___)记住表达式入口地址：PUSH(p+1)Ⅲ.目标代码生成算法(续7)4.循环语句四元式的目标代码生成：(二)设当前四元式q:(doB__)(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,_);(三)设当前四元式q:(we___)(1)返填转向地址：POP(p`);BACK(p`,p+2);(2)编转向表达式入口指令：POP(p`);CODE(JMP_,p`);back9.3.1基本块内活跃信息求解算法•支持:(1)在符号表上增设两个信息项（U,L）:LU…name待用信息活跃信息(2)四元式中变量的附加信息项：X(U,L)※取值：U=n/q(不待用/q待用),q为四元式序号；※取值：L=n/y(不活跃/活跃)；(1)初值：基本块内各变量SYMBL[X(U,L)]