编译原理英文课件：TargetCodeGen

-1-CompilerConstructionPrinciples&ImplementationTechniquesDr.ZhengXiaojuanProfessorSoftwareCollegeofNortheastNormalUniversityJune.2014-2-Whereweare?LexicalAnalysisscanningSyntaxAnalysisParsingSemanticAnalysisIntermediateCodeOptimizationIntermediateCodeGenerationTargetCodeGenerationanalysis/frontendsynthesis/backend运行时存储环境-3-MainContentofChapter10§10.TargetCodeGeneration10.1Introduction10.2TargetLanguage10.3TemporaryVariable10.4RegistersAllocation10.5GeneratingTargetCodefromQuadruples-4-KnowledgeRelationGraphTargetCodeGenerationwhat从中间代码生成目标代码(四元式目标机器指令)目标代码(目标机器指令集)转换抽象地址

目标地址生成目标代码函数相关函数入口函数出口函数调用函数值返回操作型赋值-5-FromIntermediateCodetoTargetCode目标代码中间代码源程序翻译过程特点:(1)执行过程的直译;(2)采用抽象地址;翻译过程特点:(1)执行过程的具体全部实现;(2)采用具体地址;(3)需要考虑运行时存储空间问题;(4)函数返回地址;-6-10.1IntroductiontoTargetCodeGenerationMaintask:在把中间代码翻译成目标代码的同时,1.给变量分配实际地址2.寄存器分配3.生成管理过程AR的代码Dependsontargetmachineandtargetmachinelanguage;-7-10.2TargetLanguage(目标代码)目标语言(目标代码)虚拟机代码(JVM)portability目标机器代码()目标代码有三种形式：

①可以立即执行的机器语言代码，所有地址都重定位；

②待装配的机器语言模块，当需要执行时，由连接装入程序把它们和某些运行程序连接起来，转换成能执行的机器语言代码；③汇编语言代码，须经过汇编程序汇编后，成为可执行的机器语言代码。-8-10.2TargetLanguage(目标代码)目标代码生成阶段应考虑直接影响到目标代码速度的三个问题：一﹑如何生成较短的目标代码；二﹑如何充分利用计算机中的寄存器，减少目标代码访问存储单元的次数；三﹑如何充分利用计算机指令系统的特点，以提高目标代码的质量。-9-一种目标机器语言目标地址形式假设:C是常量,R是寄存器,d是偏移量表示方法:(R)代表R地址对应的内容;立即式:#C----C是值寄存器式:R----R本身就是一个地址;变址式:d[R]----d+(R),R的内容加上偏移d得到的地址间接寄存器:*R----(R),R的内容对应的地址间接变址:*d[R]----(d+(R)),R的内容加上偏移d后得到的地址的内容;-10-FromAbstractAddresstoObjectAddress(CProgrammingLanguage)(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]目标地址计算-11-一种目标机器语言指令格式(依赖于具体的目标机器）OpR,#C（立即-----寄存器）含义是(R)与C做op操作后,结果送到

R对应地址中;OpR2,d(R1)（存储器-----寄存器）含义是(R2)和((R1)+d)做op操作后,结果送到

R2对应地址中;OpR1,R2（寄存器-----寄存器）含义是(R2)和(R1)做op操作后,结果送到

R1对应地址中;-12-一种目标机器语言基本指令集合：LoadR,Source------从Source读出送入RStoreR,Target------R的内容送入TargetAddR,Source------R+Source结果送入RJump(0/1)label-------跳转到label对应的地址INR-------输入值到ROUTR-------输出R的值LEAR,A-------A的地址送给R-13-10.3TemporaryVariable(临时变量)临时变量的特点数量多，寿命短；不优化，只定义一次，使用一次，且定义点和使用点在同一个基本块内；公共表达式节省，将出现多次引用。临时变量的存储空间x:=a+b-c+d,则产生的中间代码为：(+,a,b,t1)(-,t1,c,t2)(+,t2,d,t3)(:=,t3,x)

3个临时变量可共享一个临时单元。-14-临时变量的空间分配可以在中间代码生成或者目标代码生成时做;静态分配法（共享法）将临时变量的空间安排在AR栈区。计算出临时变量的活动区间，如果两个活动区间不相交，则可以共享同一单元。动态分配法（随用随分配法）过程调用时分配的AR区中不含临时变量部分，以后每当要保存临时变量的值时，动态分配到栈区。当临时变量所占的空间比较大时，这种方法比较好。-15-10.4RegisterAllocation(寄存器分配)寄存器分配应遵循的原则：寄存器优先原则：即变量的值尽可能的存放在寄存器中寄存器活跃原则：即变量的值至少有下一次的引用时才分配寄存器寄存器多载原则：即一个寄存器中可能存放多个变量的值。典型的例子是通过赋值操作的结果。源变量和被赋值的变量共用一个寄存器RegisterAlloc()doesregisterallocation,andreturnsanavailableregister;-16-10.5GeneratingTargetCodefromQuadruples四元式种类运算型:(op,A,B,T)赋值:(Assig,A,_,B)跳转和标号函数相关(ENTRY,label,size,level)(ENDFUNC,_,_)参数传递(CALL,f,true/false,result)(RETURN,_,_,t)-17-运算型目标代码生成(op,A,B,T)的代码生成算法要点(不考虑优化)确定A,B和T的目标地址,记为A.addr,B.addr和T.addr;找到一个可用的寄存器R=RegisterAlloc(),生成如下目标代码LoadR,A.addrOpR,B.addrStoreR,T.addr-18-Example(+,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]LoadR,2[gp]AddR,*(2+InitOff)[sp]StoreR,(5+InitOff)[sp]-19-（Assig,A,_,B）的代码生成

算法要点(不考虑优化)：①

求A和B的地址。②

申请寄存器R,生成(LoadR

,

A.addr)指令,③生成指令(StoreR

,B);-20-

标号和JUMP的代码生成思想：遇到(LABEL,L)时，不生成代码，保留（L,Pc）,Pc为当前代码下一条指令；当遇到（JUMP,L）时，则生成对应的转向指令（JUMP,Pc）关键问题：可能出现标号使用在前定义在后，则需要构造转向标号链，进行回填。（保留各个位置也可以）中间代码……(JUMP,L)……(JUMP,L)……(JUMP,L)……(LABEL,L)目标代码……………………Pc:标号地址表：

{}P1:(JUMP,nil){(0,L,P1)}Pi:(JUMP,P1){(0,L,Pi)}Pk:(JUMP,Pi){(0,L,Pk)}{(1,L,Pc)}PcPcPc-21-过程/函数代码生成(1)相关四元式：(VALACT,a,off,size);(VARACT,a,off,size)(PROACT,p,off,size);(FUNACT,a,off,size)(CALL,<f>,true/false,result)(ENTRY,Label,Level,size)(ENDFUNC,-,-,-)(2)过函调用时，需要加入一些目标代码，用于完成如下工作：

①申请新AR空间②参数传递③填写某些AR内容④转向相应过程体过程/函数返回时：①释放AR②恢复信息③返回值-22-

(3)参数传递的代码：sp:当前AR的首地址；top:栈顶指针：①（VALACT,c,offset,1）→LoadR,#cStoreR,(offset+InitOff)[top](VALACT,a,offset,1)→LoadR,a.addrStoreR,(offset+InitOff)[top]

参数传递的目标代码生成-23-(3)参数传递的代码：sp:当前AR的首地址；top:栈顶指针：

②(VARACT,a,offset,1)→LEAR,a.addrStoreR,(offset+InitOff)[top]参数传递的目标代码生成-24-(3)参数传递的代码：sp:当前AR的首地址；top:栈顶指针：③实在函数:(FUNACT,p,offset,1)→LoadR,EntryAddr(p)StoreR,(offset+InitOff)[top]

其中EntryAddr(p)代表的是函数p的入口地址

;

形参函数:(FUNACT,P,offset,1)→LoadR,P.addrStoreR,(offset+InitOff)[top]

其中P.addr是指形参函数P对应的单元地址;参数传递的目标代码生成-25-（4）过程/函数调用①（call,<f>,true,result）→LEAR,result.addr(StoreR,Re_Val[top])(LoadR,pc+3)(StoreR,Re_A[top])(JUMPEntryAddr(f))返回值对应变量的地址新AR的相应位置(2)返回地址新AR相应位置(3)调转到函数的入口地址;-26-（4）过程/函数调用(call,<f>,false,result)→LEAR,result.addr(StoreR,Re_Val[top])(LoadR,pc+4)(StoreR,Re_A[top])(LoadR,f.addr)(JUMP,R)返回值对应变量的地址新AR的相应位置(2)返回地址新AR相应位置(3)调转到函数的入口地址;-27-（5）过/函入口：（Entry,Label,size,Level）(Storesp,

DL[top])------保留oldsp(LoadR,Level)------保留层数(StoreR,L[top])(C语言没有必要)(Loadsp,top)------修改sp

(ADDtop,size)

------修改top记住label对应的代码地址;-28-（6）过/函出口：（ENDFUN,-,-,-）

①恢复寄存器内容

②（Loadtop,sp）--------top=sp(Loadsp,DL[sp])------sp=CurrentAR.sp

(LoadR,Re_A[top])

(JUMP,R)-29-（7）返回语句：（RETUTRN,-,-,result）

LEAR1,Re_Val[sp]LoadR2,result.addr

StoreR2,*R1

(JumpEndFun)对应本函数中(ENDFUN,_,_,_)

对应目标代码地址

-30-Exampleconstintn=5;intsum=0;intfac(inti){ifi=0return1;ifi<0return-1;return(i*fac(i-1));}voidmain(){sum=fac(n);}

(ENTRY,L1,2,0)(EQ,i,0,t1)(JUMP0,t1,_,L2)(RETURN,_,_,1)(LABEL,_,_,L2)(assign,0,_,sum)(LT,i,0,t1)(JUMP0,t1,_,L3)(RETURN,_,_,-1)(LABEL,_,_,L3)

(-,i,1,t2)(VALACT,t2,0,1)(CALL,fac,true,t3)(*,i,t3,t4)(RETURN,_,_,t4)(ENDFUNC,_,_,_)(ENTRY,L4,1,0)(VALACT,n,0,1)(CALL,fac,true,sum)(ENDFUNC,_,_,_)-31-TargetCodeGenerationFourregisterssp:保存当前AR的首地址;top:保存当前栈顶地址;gp:保存静态区的首地址;pc:程序计数器;

ActivationRecord动态链地址0[sp]返回地址1[sp]返回值2[sp]临时变量形参局部变量空间大小3[sp]spoffsetInitOff=4top-32-目标地址抽象地址目标地址sumi(fac)t1,t2,t3,t4(fac)n(main)(0,0,dir)0[gp](1,0,dir)4[sp](-1,1,dir)5[sp](1,0,dir)4[sp]-33-TargetCodeGenerationP1:LoadR,#0P2:StoreR,0[gp]P3:JumpP40

P4:Storesp,0[top]P5:Loadsp,topP6:ADD6,top

(ENTRY,L1,2,0)(EQ,i,0,t1)(JUMP0,t1,_,L2)(RETURN,_,_,1)(LABEL,_,_,L2)(assign,0,_,sum)保存动态链地址修改sp修改topP7:LoadR,#0P8:EQR,4[sp]P9:StoreR,5[sp]P10:Jump0R,P11:LoadR,#1P12:StoreR,*2[sp]P13:JumpP36P14-34-(LT,i,0,t1)(JUMP0,t1,_,L3)(RETURN,_,_,-1)(LABEL,_,_,L3)

TargetCodeGenerationP14:LoadR,#0P15:LTR,4[sp]P16:StoreR,5[sp]P17:Jump0R,P18:LoadR,#(-1)P19:StoreR,*2[sp]P20:JumpP36P21-35-TargetCodeGeneration

(-,i,1,t2)(VALACT,t2,0,1)(CALL,fac,true,t3)(*,i,t3,t4)(RETURN,_,_,t4)(ENDFUNC,_,_,_)P21:LoadR,4[sp]P22:SubR,#1P23