第十章 目标代码生成

词法分析语法分析语义分析中间代码优化中间代码生成目标代码生成分析合成第十章目标代码生成目标代码生成概述目标语言四元式到目标指令的翻译*寄存器分配*临时变量地址分配目标代码生成概述目标代码生成器主要任务:将中间代码转换成等价的目标机指令(包括计算指令和管理AR的指令等)，同时完成变量的地址分配,寄存器分配。输入：中间代码/TokenList/AST+[符号表]输出（多种形式可选）：绝对机器代码：执行速度快，缺乏灵活性可重定位机器代码：可分模块编译，需连接和装入汇编代码：生成的汇编代码还要经过汇编程序汇编才可运行虚拟机的代码：增加可移植性，需要虚拟机的解释器衡量目标代码质量的标准在保证语义相等的情况下，生成的目标指令的条数越少和执行速度越快一种目标机器语言目标地址形式–假设:C是常量,R是寄存器,d是偏移量,A是绝对地址(内存地址)–表示方法:(R)代表R地址对应的内容;–立即式:#C----C是值–寄存器式:R----R本身就是一个地址;–变址式:d[R]----d+(R),R的内容加上偏移d得到的地址–绝对式:A----A本身是一个地址值–间接寄存器:*R----(R),R的内容对应的地址–间接变址:*d[R]----(d+(R)),R的内容加上偏移d后得到的地址的内容;从抽象地址到目标地址(C语言)(0,off,dir)(0,off,indir)(1,off,dir)(1,off,indir)(-1,off,dir)(-1,off,indir)抽象地址形式off[gp]*off[gp](off+InitOff)[sp]*(off+InitOff)[sp](off+InitOff)[sp]*(off+InitOff)[sp]目标地址计算一种目标机器语言指令格式(依赖于具体的目标机器),寄存器在最后(与教材不同)–Op#C,R（立即-----寄存器）含义是C与(R)做op操作后,结果送到R对应地址中;–Opd[R1],R2（存储器-----寄存器）含义是((R1)+d)和(R2)做op操作后,结果送到R2对应地址中;–OpR1,R2（寄存器-----寄存器）含义是(R1)和(R2)做op操作后,结果送到R2对应地址中;–Op&A,R(绝对地址-----寄存器)含义是(A)和(R)做op操作后,结果送到R对应地址中;一种目标机器语言基本指令集合：–LoadSource,R------从Source读出送入R–StoreTarget,R------将R的内容送入Target–AddSource,R------R+Source结果送入R–Jmp(0/1),label-------跳转到label对应的地址–INR-------输入值到R–OUTR-------输出R的值–LEAA,R-------A的地址送给R从四元式生成目标代码四元式种类–运算型:(OP,A,B,T)–赋值:(ASSIG,A,size,B)–跳转和标号(JUMP,-,-,L)和(LABEL,-,-,L)–(WHILE,-,-,-),(THEN,t,-,-),(ELSE,-,-,-),……–函数相关(ENTRY,Lf,size,level)(ENDFUNC,_,_,_)参数传递(VALACT/VARACT,X,offset,size)(CALL,Lf,true,t)(RETURN,-,-,t)运算型目标代码生成(OP,A,B,T)的代码生成算法要点(不考虑优化)–确定A,B和T的目标地址,记为A.addr,B.addr和T.addr;–找到一个可用的寄存器R,–生成如下目标代码LoadA.addr,ROp*B.addr,RStoreT.addr,R例子(ADDI,a,b,t),其中a:(0,2,dir);b:(1,2,indir),t:(-1,5,dir)a的目标地址:2[gp]b的目标地址:*(2+InitOff)[sp]t的目标地址:(5+InitOff)[sp]Load2[gp],RAdd*(2+InitOff)[sp],RStore(5+InitOff)[sp],R(ASSIG,A,size,B)的代码生成size=1算法要点：①求A和B的地址。②申请寄存器RA,生成(LoadA.addr,RA)指令,③生成指令(StoreB.addr,RA);(ASSIG,t,1,f),其中t:(-1,5,dir);f:(1,2,indir)t的目标地址:(5+InitOff)[sp]f的目标地址:*(2+InitOff)[sp]Load(5+InitOff)[sp],RStore*(2+InitOff)[sp],RSize!=1,MOVEBA.addr,B.addr,n标号和JUMP的代码生成(1)思想：遇到(LABEL,L)时，不生成代码，保留（L,Pc）,Pc为当前代码下一条指令；当遇到（JUMP,L）时，则生成对应的转向指令（Jmp,Pc）(2)关键问题：可能出现标号使用在前定义在后，则需要构造转向标号链，进行回填。中间代码……(JUMP,L)……(JUMP,L)……(JUMP,L)……(LABEL,L)目标代码……………………Pc:标号地址表：{}P1:(Jmp,nil){(0,L,P1)}Pi:(Jmp,P1){(0,L,Pi)}Pk:(Jmp,Pi){(0,L,Pk)}{(1,L,Pc)}PcPcPc1条件语句四元式的代码生成条件语句特有的四元式：(THEN,t,-,-)---(Loadt,R)(Jmp0ar1,R),ar1入栈S(ELSE,-,-,-)---(Jmpar2),回填给ar1,ar2入栈S(ENDIF,-,-,-)---回填ar2(有else分支)或回填ar1(没有else分支)ifethens1elses2endife.CodeThen,t,-,-S1.codeElse,-,-,-S2.codeEndif,-,-,-循环语句的代码生成While循环特有的四元式(WHILE,-,-,-)---标记循环结构的开始，对应(LABEL,-,-,startL),不生成代码，ar1入栈S(DO,t,-,-)---是循环体的开始，判断循环条件表达式是否成立，不成立则发生跳转，生成(Loadt,R)(Jmp0ar2,R),ar2入栈S(ENDWHILE,-,-,-)---标记循环体结束，转向循环开始，重新判断循环条件是否成立回填ar2,生成(Jmpar1)(WHILE,-,-,-)E.code(DO,t,-,-)S.code(ENDWHILE,-,-,-)过程/函数代码生成(1)相关四元式：(VALACT,a,off,size),(VARACT,a,off,size)(CALL,Lf,true/false,result)(RETURN,-,-,t/-)(ENTRY,Lf,size,Level)(ENDFUNC,-,-,-)(2)★过函调用时，需要加入一些目标代码，用于完成如下工作：①申请新AR空间②参数传递③填写某些AR内容④转向相应过程体★过程/函数返回时：①传递返回值②恢复寄存器的状态③释放AR④按照返回地址返回(3)参数传递的代码：sp:当前AR的首地址；top:栈顶指针：①（VALACT,c,offset,1）:c是常量值(VALACT,a,offset,1):a是变量参数传递的目标代码生成Load#c,RStore(offset+InitOff)[top],RLoada.addr,RStore(offset+InitOff)[top],R将a.addr里面的值放入R(3)参数传递的代码：sp:当前AR的首地址；top:栈顶指针：②(VARACT,a,offset,1)参数传递的目标代码生成a.addrRStore(offset+InitOff)[top],RLEAa.addr,R（4）过程/函数调用（CALL,Lf,true,result）*保存寄存器当前内容LEAresult.addr,R(LoadR,Re_Val[top])(Loadpc+2,Re_A[top])(JMPentry(f))pc（5）过/函入口：（ENTRY,Lf,size,Level）(Load,sp,DL[top])------保留oldsp(Load,Level,L[top])------保留层数(C语言没有必要)(Load,top,sp)------修改sp(ADD,size,top)------修改top（6）过/函出口：（ENDFUNC,-,-,-）①恢复寄存器内容②(Loadsp,top）--------top=sp(LoadDL[sp],sp)------sp=CurrentAR.sp(LoadRe_A[top],R)------按照返回地址返回(JMPR)（7）返回语句：（RETURN,-,-,result）Loadresult.addr,R1StoreRe_Val[sp],R1若没有返回值：（RETURN,-,-,-）,则不生成代码例子#definen2intsum=0;intfac(inti){if(i==0)return1;if(i0)return-1;return(i*fac(i-1));}voidmain(){sum=fac(n);}(ENTRY,L1,6,0)(EQ,i,0,t2)(THEN,t2,_,_)(RETURN,_,_,1)(ENDIF,-,-,-)(ASSIG,0,1,sum)(LT,i,0,t3)(THEN,t3,_,_)(RETURN,_,_,-1)(ENDIF,_,_,_)(-,i,1,t4)(VALACT,t4,0,1)(CALL,fac,true,t5)(*,i,t5,t6)(RETURN,_,_,t6)(ENDFUNC,_,_,_)(ENTRY,L4,1,0)(VALACT,n,0,1)(CALL,fac,true,t1)(ASSIG,t1,1,sum)(ENDFUNC,_,_,_)目标代码生成四个寄存器–sp:保存当前AR的首地址;–top:保存当前栈顶地址;–gp:保存静态区的首地址;–pc:指令计数器;过程活动记录动态链地址返回地址返回值临时变量形参局部变量空间大小spoffsetInitOff=4P1:Load#0,RP2:Store1[gp],RP3:JmpP4:Loadsp,0[top]P5:Loadtop,spP6:ADD#10,top(ENTRY,L1,6,0)(EQ,i,0,t2)(THEN,t2,_,_)(RETURN,_,_,1)(ENDIF,_,_,_)(ASSIG,0,1,sum)保存动态链地址修改sp修改topP7:Load#0,RP8:EQ4[sp],RP9:Store5[sp],RP10:Load5[sp],RP11:Jmp0P12:Load#1,RP13:Store*2[sp],RP14P37P17:Load6[sp],RP18:Jmp0(THEN,t3,_,_)(RETURN,_,_,-1)(LT,i,0,t3)P21P14:Load#0,RP15:LT4[sp],RP16:Store6[sp],R(ENDIF,_,_,_)P19:Load#-1,RP20:Store*2[sp],R(-,i,1,t4)(VALACT,t4,0,1)(CALL,fac,true,t5)(*,i,t5,t6)(RETURN,_,_,t6)(ENDFUNC,_,_,_)P21:Load4[sp],RP22:Sub#1,RP23:Store7[sp],RP24:Load7[sp],RP25:Store4[top],RP26:LEA8[sp],RP27:LoadR,2[top])P26:Loadpc+2,1[top]P27:JmpP4P28:Load4[sp],RP29:Mul8[sp],RP30:Store9[sp],RP31:Load9[sp],RP32:Store*2[sp],RP33:Loadsp,topP34:Load