第7章目标代码生成

,第二级,第三级,第四级,第五级,第,7,章 目标代码生成,第,7,章 目标代码生成,7.1,一个简单代码生成器,7.2*,汇编指令到机器代码的翻译概述,概述,目标代码生成：,目标代码生成就是将中间代码程序转换成等价的目标代码程序，完成这一功能的程序称为目标代码生成器。,代码生成器：,目标代码的常见形式,(1),可立即执行的机器语言代码。,(.exe,或,.com),(2),待装配的机器语言模块。,(.obj,或,lib),(3),汇编语言程序,生成目标代码的过程中要注意考虑的问题：,(1),生成的目标代码较短,(2),充分利用寄存器,7.1,一个简单代码生成器,简单的代码生成器,:,特点,:,生成器依次把每条中间代码变换成目标代码，,在一个基本块范围内考虑如何充分利用寄存器的问题,。,一方面生成计算某变量值的目标代码时，尽可能地让该变量的值保留在寄存器中，直到该寄存器必须用来存放其它变量的值或已达基本块出口为止；,另一方面，后续的目标代码尽可能地引用变量在寄存器中的值而不访问内存。,低效的代码生成器,:,不考虑代码的效率，可以简单地把每条中间代码,(,四元式,),映射成若干条目标指令,例如，一,C,语言语句为,A=(B+C)*D+E,，把它翻译为四元式,G,：,T,1,=B+C,T,2,=T,1,*D,A=T,2,+E,代码生成器将形如,x=y+z,的三地址代码映射为：,MOV AX,y,/*AX,为寄存器*,/,ADD AX,z,MOV x,AX,这样，上述四元式代码序列,G,就可翻译为：,(1)MOV AX,B,(2)ADD AX,C,(3)MOV T,1,AX,(4)MOV AX,T,1,(5)MUL AX,D,(6)MOV T,2,AX,(7)MOV AX,T,2,(8)ADD AX,E,(9)MOV A,AX,(4),和,(7),两条指令是多余的；,T1,、,T2,是中间代码生成时产生的临时变量，它们在出了基本块后将不再使用，故,(3),、,(6),两条指令也可删去。,高效的代码生成器,:,考虑效率和充分使用寄存器，生成如下代码：,(1)MOV AX,B,(2)ADD AX,C,(3)MUL AX,D,(4)ADD AX,E,(5)MOV A,AX,?,如何充分利用寄存器,7.1.1,待用信息与活跃信息,在一个基本块内的目标代码中，为了提高寄存器的使用效率，应将基本块内,还要被引用的值尽可能地保留在寄存器中,，而将基本块内,不再被引用的变量所占用的寄存器尽早释放,。,待用信息,：为了将基本块内还要被引用的值尽可能地保留在寄存器中,需要收集变量的待用信息。,四元式,i,：,A=B op C,四元式,j,：,X=Y op A,四元式,i,对变量,A,定值，,i,后面的四元式,j,要引用,A,且从,i,到,j,的四元式没有其它对,A,的定值点，则称,j,是四元式,i,中对变量,A,的待用信息,活跃信息,：为了将不再被引用的变量所占用的寄存器尽早释放，需要收集变量的活跃信息。,上例中如在,i,之后,A,被不再被引用，则称,A,为非活跃的，否则称,A,在,i,是活跃的；,如果,A,被多处引用，则构成了,A,的待用信息链与活跃信息链。,取得每个变量在基本块内的待用信息和活跃信息算法：,从基本块的出口由后向前扫描，对每个变量建立相应的待用信息链与活跃信息链。,基本块中的临时变量看作基本块出口之后的非活跃变量，而所有的非临时变量均看作基本块出口之后的活跃变量。如果某些临时变量能够跨基本块使用，则把这些临时变量也看成基本块出口之后的活跃变量。,假设变量的符号表内有待用信息和活跃信息栏，则计算变量待用信息的算法如下：,(1),将基本块中各变量的符号表的,待用信息栏置为“非待用”,，对,活跃信息栏,则根据该变量在基本块出口之后是否活跃而将该栏中的信息置为“活跃”或“非活跃”。,(2),从基本块出口到基本块入口由后向前依次处理各四元式。对每个四元式,i,：,A=B op C,依次执行以下步骤：,把符号表中变量,A,的待用信息和活跃信息附加到四元式,i,上；,把符号表中变量,A,的待用信息和活跃信息分别置为“非待用”和“非活跃”,；,把符号表中变量,B,和,C,的待用信息和活跃信息附加到四元式,i,上；,把符号表中,B,和,C,的待用信息置为,i,，活跃信息置为“活跃”,。,例,7.1,考察基本块：,(1)T=AB,(2)U=AC,(3)V=T+U,(4)D=V+U,其中，,A,、,B,、,C,、,D,为变量，,T,、,U,、,V,为中间变量，试求各变量的待用信息链和活跃信息链。,表,7.1,例,7.1,的待用信息链和活跃信息链,变量名,待 用 信 息,活 跃 信 息,初值,待 用 信 息 链,初值,活 跃 信 息 链,T,F,(3),F,F,L,L,F,A,F,(2),(1),L,L,B,F,(1),L,L,C,F,(2),L,L,U,F,(4),(3),F,F,L,L,F,V,F,(4),F,F,L,F,D,F,F,L,F,待用信息和活跃信息在四元式上的标记如下：,(1)T,(3)L,=A,(2)L,B,FL,(2)U,(3)L,=A,FL,C,FL,(3)V,(4)L,=T,FF,+U,(4)L,(4)D,FL,=V,FF,+U,FF,7.1.2,代码生成算法,以下代码生成算法以基本块为单位生成目标代码。优化使用寄存器基本不考虑基本块以外的情况。,寄存器描述数组,RVALUE:,动态地记录各寄存器的当前状况，并用寄存器,R,i,的编号作为它的下标,变量地址描述数组,AVALUE:,记录各变量现行值存放的位置，即其是在某寄存器中还是在某内存单元中，或者同时存在于某寄存器和某内存单元中,如：,RVALUER,i,=A,/*,寄存器,R,i,分配给变量,A*/,RVALUER,i,=A,B,/*,寄存器,R,i,分配给变量,A,和,B*/,RVALUER,i,=,/*,R,i,未分配*,/,AVALUEA=A,/*,表示,A,的值在内存中*,/,AVALUEA=R,i,/*,表示,A,的值在寄存器,R,i,中*,/,AVALUEA=R,i,A,/*,表示,A,的值既在寄存器,R,i,中又在内存中*,/,假设基本块中每个四元式的形式都是,A=B op C,，则代码生成算法是对每个四元式,i,：,A=B op C,执行下述步骤：,(1),调用函数,GETREG(i,：,A=B op C),返回存放,A,值结果的寄存器,R,。,(2),通过地址描述数组,AVALUE B,和,AVALUE C,确定出变量,B,和变量,C,的现行值存放位置,B,和,C,；如果是存放在寄存器中，则把寄存器取作,B,和,C,。,(3),如果,BR,，则,生成目标代码,：,MOV R,B,op R,C,否则生成目标代码：,op R,C,如果,B,或,C,为,R,，则删除,AVALUE B,或,AVALUE C,中的,R,。,(4),令,AVALUEA=R,并令,RVALUER=A,，表示变量,A,的现行值只在,R,中且,R,中的值只代表,A,的现行值。,R,中的值已发生变化，不等于,B,或,C,(5),如果,B,和,C,的现行值在基本块中不再被引用，它们也不是基本块出口之后的活跃变量且它们的现行值存放在寄存器,R,k,中，则删除,RVALUE R,k,中的,B,和,C,以及,AVALUE B,中的,R,k,，使寄存器,R,k,不再为,B,和,C,所占用。,函数,GETREG(i,：,A=B op C),用来得到存放,A,的当前值的寄存器,R,；其算法如下：,(1),如果,B,的现行值在某寄存器,R,i,中，且该寄存器只包含,B,的值，或者,B,和,A,是同一标识符，或者,B,在该四元式之后不再被引用，则选取,R,i,为所需寄存器并转,(4),。,(2),如有尚未分配的寄存器，则从中选取一个,R,i,为所需寄存器并转,(4),。,(3),从已分配的寄存器中选取一个,R,i,为所需寄存器,R,。选取原则为：占用,R,i,的变量的值也同时放在内存中，或者该值在基本块中要在最远的位置才会引用到。这样，对寄存器,R,i,所含的变量和变量在内存中的情况必须先做如下调整：,对,RVALUE R,i,中的每一个变量,M,，如果,M,不是,A,或者,M,既是,A,又是,C,却不是,B,，而,B,又不在,RVALUE R,i,中，则：,如果,AVALUE R,i,中不包含,M,，则生成目标代码,MOV M,R,i,；,尽可能使用,B,所在的寄存器,不行则选用空闲寄存器,再不行则选用待用位置最远的变量占用的寄存器,当,M,不是,A,时，如果,M,是,B,或者,M,是,C,且同时,B,也在,RVALUE R,i,中，则令,AVALUE M=M,R,，否则令,AVALUE M=M,；,删除,RVALUE R,i,中的,M,；,(4),给出,R,，返回。,表,7.2,例,7.2,的目标代码,四元式,目标代码,RVALUE,AVALUE,T=AB,MOV AX,A,SUB AX,B,AX,含有,T,T,在,AX,中,U=AC,MOV BX,A,SUB BX,C,AX,含有,T,BX,含有,U,T,在,AX,中,U,在,BX,中,V=T+U,ADD AX,BX,AX,含有,V,BX,含有,U,V,在,AX,中,U,在,BX,中,D=V+U,ADD AX,BX,AX,含有,D,D,在,AX,中,例,7.2,对例,7.1,，假设只有,AX,和,BX,是可用寄存器，用代码生成算法生成目标代码和相应的,RVALUE,和,AVALUE,。,处理完基本块中所有的四元式后，对现行只在某寄存器中的每个变量，如果它在基本块出口之后是活跃的，则要用,MOV,指令把它在寄存器中的值存放到数据区以它命名的内存单元中。,7.1.3,寄存器分配,以下寄存器分配考虑循环内的寄存器的使用，优化使用寄存器考虑一个循环中所有基本块变量的情况。,为有效地利用寄存器。为此，我们定义指令的执行代价如下：,每条指令的执行代价,=,每条指令访问内存单元次数,+1,循环中，某寄存器固定分配给某变量使用，那么对循环中的每个基本块，相对于原简单代码生成算法所生成的目标代码，所节省的执行代价可用下述方法计算：,(1),在原代码生成算法中，仅当变量在基本块中被定值时，其值才存放在寄存器中。现在把寄存器固定分配给某变量使用，当该变量在基本块中被定值前，每引用它一次就可以少访问一次内存，则执行代价节省,1,。,(2),在原代码生成算法中，如果某变量在基本块中被定值且在基本块出口之后是活跃的，则出基本块时要把它在寄存器中的值存放到内存单元中。现在把寄存器固定分配给某变量使用，出基本块时就无需把它的值存放到其内存单元中，则执行代价节省,2,。,循环,L,中的变量,M,，如果分配一个寄存器给它专用，那么每执行循环一次，其执行代价的节省数可用下式计算：,USE(M,B)=,基本块,B,中对,M,定值前引用,M,的次数,1,如果,M,在基本块,B,中被定值且在,B,的出口之后是活跃的,LIVE(M,B)=,0,其它情况,循环内寄存器分配原则：把寄存器固定分配给结省代价最多的变量。,例,7.3,一代码序列及程序流图如图,71,所示。假定各基本块出口之后的活跃变量均为,a,、,b,、,c,，循环中的固定寄存器为,AX,、,BX,，则将,AX,、,BX,固定分配给循环中哪两个变量可使执行代价节省得最多？,图,71,程序流图,解答,(1),考虑变量,a,的情况：基本块,B,2,中没有对,a,进行定值，且引用的次数为,1(e=ab),；基本块,B,3,没有对,a,进行定值，也没有引用,a,；基本块,B,4,对,a,进行了定值，并且定值前引用的次数为,1(a=af),。根据执行代价节省数的计算公式得到：,USE(a,B,2,)=1,；,LIVE(a,B,2,)=0,；,USE(a,B,3,)=0,；,LIVE(a,B,3,)=0,；,USE(a,B,4,)=1,；,