目标代码生成.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,目标代码生成器的位置：,源 中间 中间 目标程序 代码 代码 程序,编译前端 代码优化 代码生成器,符号表,目标代码的形式：,1、已定位的可立即执行的机器语言代码；,2、可浮动的机器语言代码，需装配连接再执行；,3、汇编语言目标代码，需汇编再执行。,第十一章 目标代码生成,目标代码应具有高效性：,目标代码较短；,充分利用寄存器减少内存访问。,11.1 一个简单的代码生成器,P312,中两个表给出了一个模拟机的指令系统(类似汇编)。,仅介绍一个简单的目标代码生成方法：,1、依次将每条中间代码变换成等价的若干条目标代码；,2、基本块内考虑充分利用寄存器的问题。,即：基本块内计算出的变量值尽量保留在寄存器中，,直至寄存器另有用途或已到基本块的出口；,引用变量时尽量用其在寄存器中的值。,例 现有赋值语句：,A:=(B+C)*D+E,其对应的中间码：,T1:=B+C,T2:=T1*D,A:=T2+E,则前述中间码可翻译为：,LDR,B,ADDR,C,STR,T1,LDR,T1,MULR,D,STR,T2,LDR,T2,ADDR,E,STR,A,设临时变量在基本块外不用，上述代码可简化。,LDR,B,ADDR,C,MULR,D,ADDR,E,STR,A,简化,若中间码,X:=Y+Z,可翻译为:,LD R,Y,ADD R,Z,ST R,X,为完成上述简化工作，应考虑到：,1、为省略,LD R,T1,必须知道,T1,已在寄存器中；,2、为省略,ST R,T1,必须知道,T1,在基本块外不用。,为此，我们引进“,待用信息,”、“,寄存器描述数组,”、“,变量地址描述数组,”等数据结构，记录所需信息。,一、,待用信息,为了:1.将块内还将引用的变量的值尽量保存在寄存器中;,2.将块内不再引用的变量占用的寄存器尽早释放。,引入：,待用信息,及,活跃信息,（记入符号表）,。,待用信息:,对活跃变量记录下一次引用该变量的语句号；,对非活跃变量记“非待用”。,活跃信息:,还将被引用的变量记“活跃”；,不再被引用的变量记“非活跃”。,活跃信息及待用信息的构造算法：,1、在符号表中将本块各变量均填为“非待用”；,并根据该变量出口后是否引用填“活跃”或“非活跃”。,2、从出口向入口逆序扫描各语句,i:A:=B OP C,执行：,(1)在语句,i,后附加,A,的待用信息、活跃信息；,(2),A,的符号表中置：“非待用”、“非活跃”；,(3)在语句,i,后附加,B、C,的待用信息、活跃信息;,(4),B、C,的符号表中置：“待用,i”、“,活跃,y”。,注,(1)(2)(3)(4)次序不可颠倒，因,B、C,有可能为,A。,由此，各变量的引用信息由符号表及各语句的待用信息,所表示。,此外，每一条语句还应记录其中各变量的活跃信息及,待用信息。,变量 待用信息及活跃信息,T (,),A (,),B (,),C (,),变量 待用信息及活跃信息,U (,),V (,),W (,Y,),序号 中间代码语句 左值 左操作数 右操作数,1,T:=A-B,2 U:=A-C,3 V:=T+U,4 W:=V+U,(,),(,Y,),(,),(,),(,4,Y,),(,4,Y,),(,4,Y,),(,),(,),(,4,Y,),(,3,Y,),(,3,Y,),(,3,Y,),(,),(,),(,),(,3,Y,),(,),(,2,Y,),(,2,Y,),(,2,Y,),(,),(,1,Y,),(,1,Y,),例现有基本块为：,T:=A-B U:=A-C,V:=T+U,W:=V+U,且已知,W,在块后活跃，则由算法可得:,二、寄存器描述和地址描述,为合理分配寄存器，需掌握寄存器的使用情况，为此建立寄存器描述数组,RVALUE：,RVALUE,Ri,=A,表示寄存器,Ri,现为变量,A,的值;,为尽量引用变量在寄存器中的值，建立地址描述数组,AVALUE，,记录各变量的存放位置（,R,或,M）：,AVALUEA=,Ri,(,或,A),表示变量,A,的值现在寄存器,Ri,中（或在内存中）。,三、代码生成算法,对基本块中每条代码,i:A:=B OP C,执行：,1、调用,GETREG(i:A:=B OP C)，,此过程返回一个寄存,器,R，,用于存放,A,的值。,2、查,AVALUEB,及,AVALUEC，,确定,B、C,的现行存放,位置,B、C。,3、,若,BR,则生成,LD R B,OP R C,否则生成,OP R C,若,B=R,或,C=R,则从,AVALUEB,或,AVALUEC,中,删除,R;,4、,令,AVALUEA=R,且令,RVALUER=A,5、,若,B，C,在块内不再被引用，在块后不再活跃，且其现,行值在中,R,K,中，则从,RVALUER,K,中删除,B，C，,并,从,AVALUEB，AVALUEC,中,删除,R,K。,GETREG,过程：,1、若某,RVALUE,R,i,=B,且,B,在,i,的附加信息为（,）,或,B,与,A,为同标识符，则,R=,Ri,。,2、,若不存在满足上述条件的寄存器，则选择某未分配的寄存器,R,i,，,令,R=,Ri,。,3、,若不存在满足上述条件的寄存器，则选择一个已分配的寄存器,R,i,，,令,R=,Ri,，,选择条件为：,(1),Ri,中变量的值已在内存。,(2),Ri,中变量的值在块内的下一个引用点最远。,对,RVALUE,R,i,中的每个,M(,由复写语句时，,R,i,分给多个变量)执行：,(1)若,MA;,或,M=A,且,M=C,则：,若,AVALUEM,不含,M，,生成,ST,R,i,M;,(2)AVALUEM=M。,(3),删除,RVALUE,R,i,中的,M。,例：见,P316,的例11.2,可用寄存器为,R0，R1.,(1)T:=A-B;,由,GETREG,过程第,2,条，,T,的寄存器分配为,R0，,因此生成：,LD R0,A,SUB R0,B,(2)U:=A-C;,由,GETREG,过程第,2,条，,U,的寄存器分配为,R1，,因此生成：,LD R1,A,SUB R1,C,(3)V:=T+U;,由,GETREG,过程第1条，,V,的寄存器分配为,R0，,因此生成：,ADD R0,R1,(4),W:=V+U;,由,GETREG,过程第1条，,W,的寄存器分配为,R0，,因此生成：,ADD R0,R1,在基本块的出口处，对现行值仅在,R,中且块后活跃的变量应使,用,ST,语句送入内存;此例最后应加,ST R,0,W。,P317,表11.4给出了各中间代码对应的目标代码。,十一章结束,