第7章目标代码生成.ppt

第7章 目标代码生成,7.1 一个简单代码生成器 7.2*汇编指令到机器代码的翻译概述,概述,目标代码生成：目标代码生成就是将中间代码程序转换成等价的目标代码程序，完成这一功能的程序称为目标代码生成器。代码生成器：目标代码的常见形式(1)可立即执行的机器语言代码。(.exe或.com)(2)待装配的机器语言模块。(.obj或lib)(3)汇编语言程序生成目标代码的过程中要注意考虑的问题：(1)生成的目标代码较短(2)充分利用寄存器,7.1 一个简单代码生成器,简单的代码生成器:特点:生成器依次把每条中间代码变换成目标代码，在一个基本块范围内考虑如何充分利用寄存器的问题。一方面生成计算某变量值的目标代码时，尽可能地让该变量的值保留在寄存器中，直到该寄存器必须用来存放其它变量的值或已达基本块出口为止；另一方面，后续的目标代码尽可能地引用变量在寄存器中的值而不访问内存。,低效的代码生成器:不考虑代码的效率，可以简单地把每条中间代码(四元式)映射成若干条目标指令 例如，一C语言语句为A=(B+C)*D+E，把它翻译为四元式G：T1=B+C T2=T1*D A=T2+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 T1,AX(4)MOV AX,T1(5)MUL AX,D(6)MOV T2,AX(7)MOV AX,T2(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的待用信息链和活跃信息链,待用信息和活跃信息在四元式上的标记如下：(1)T(3)L=A(2)LBFL(2)U(3)L=AFLCFL(3)V(4)L=TFF+U(4)L(4)DFL=VFF+UFF,7.1.2 代码生成算法以下代码生成算法以基本块为单位生成目标代码。优化使用寄存器基本不考虑基本块以外的情况。寄存器描述数组RVALUE:动态地记录各寄存器的当前状况，并用寄存器Ri的编号作为它的下标变量地址描述数组AVALUE:记录各变量现行值存放的位置，即其是在某寄存器中还是在某内存单元中，或者同时存在于某寄存器和某内存单元中如：,RVALUERi=A/*寄存器Ri分配给变量A*/RVALUERi=A,B/*寄存器Ri分配给变量A和B*/RVALUERi=/*Ri未分配*/AVALUEA=A/*表示A的值在内存中*/AVALUEA=Ri/*表示A的值在寄存器Ri中*/AVALUEA=Ri,A/*表示A的值既在寄存器Ri中又在内存中*/,假设基本块中每个四元式的形式都是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的现行值在基本块中不再被引用，它们也不是基本块出口之后的活跃变量且它们的现行值存放在寄存器Rk中，则删除RVALUE Rk中的B和C以及AVALUE B中的Rk，使寄存器Rk不再为B和C所占用。,函数GETREG(i：A=B op C)用来得到存放A的当前值的寄存器R；其算法如下：(1)如果B的现行值在某寄存器Ri中，且该寄存器只包含B的值，或者B和A是同一标识符，或者B在该四元式之后不再被引用，则选取Ri为所需寄存器并转(4)。(2)如有尚未分配的寄存器，则从中选取一个Ri为所需寄存器并转(4)。(3)从已分配的寄存器中选取一个Ri为所需寄存器R。选取原则为：占用Ri的变量的值也同时放在内存中，或者该值在基本块中要在最远的位置才会引用到。这样，对寄存器Ri所含的变量和变量在内存中的情况必须先做如下调整：对RVALUE Ri中的每一个变量M，如果M不是A或者M既是A又是C却不是B，而B又不在RVALUE Ri中，则：如果AVALUE Ri中不包含M，则生成目标代码MOV M,Ri；,尽可能使用B所在的寄存器,不行则选用空闲寄存器,再不行则选用待用位置最远的变量占用的寄存器,当M不是A时，如果M是B或者M是C且同时B也在RVALUE Ri中，则令AVALUE M=M,R，否则令AVALUE M=M；删除RVALUE Ri中的M；(4)给出R，返回。,表7.2 例7.2的目标代码,例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的情况：基本块B2中没有对a进行定值，且引用的次数为1(e=ab)；基本块B3没有对a进行定值，也没有引用a；基本块B4对a进行了定值，并且定值前引用的次数为1(a=af)。根据执行代价节省数的计算公式得到：USE(a,B2)=1；LIVE(a,B2)=0；USE(a,B3)=0；LIVE(a,B3)=0；USE(a,B4)=1；LIVE(a,B4)=1；因此，变量a在一次循环中执行代价的节省总数为：,USE(a,B)+2*LIVE(a,B)BL,=1+0+1+2*(0+0+1)=4,(2)对于变量b有：USE(b,B2)=2；LIVE(b,B2)=1；USE(b,B3)=1；LIVE(b,B3)=1；USE(b,B4)=0；LIVE(b,B4)=0；因此，变量b在一次循环中执行代价的节省总数为：,USE(b,B)+2*LIVE(b,B)BL,=2+1+0+2*(1+1+0)=7,(3)对于变量c有：USE(c,B2)=2；LIVE(c,B2)=1；USE(c,B3)=1；LIVE(c,B3)=0；USE(c,B4)=1；LIVE(c,B4)=0；因此，变量c在一次循环中执行代价的节省总数为：,USE(c,B)+2*LIVE(c,B)BL,=2+1+1+2*(1+0+0)=6,7.1.4 源程序到目标代码生成示例 我们以PC机的汇编语言作为目标代码，且假定可用的寄存器为AX、BX、CX和DX，则一C语言源程序转换为四元式代码序列，然后再转换为目标代码程序(转换中不考虑优化)的结果如下：,(1)C语言源程序(局部)while(ab)if(m=n)a=a+1;elsewhile(k=h)x=x+2;m=n+x*(m+y);,(2)四元式代码序列100(j,a,b,102)101(j,_,_,117)102(j=,m,n,104)103(j,_,_,107)104(+,a,1,T1)105(=,T1,_,a)106(j,_,_,112)107(j=,k,h,109)108(j,_,_,112)109(+,x,2,T2),110(=,T2,_,x)111(j,_,_,107)112(+,m,y,T3)113(*,x,T3,T4)114(+,n,T4,T5)115(=,T5,_,m)116(j,_,_,100),(3)目标代码程序(汇编语言程序);File:compile.asm;*data segment;定义数据段 h DW k DW m DW n DW x DW,y DW a DW b DWdata ends;数据段定义结束;*code segment;定义代码段main proc far;程序的执行部分assum cs:code,ds:data,start:push dssub bx,bxpush bxmov bx,data;设置DS段为当前数据段mov ds,bx;语句翻译由此开始：100:mov AX,a cmp AX,b jg 102,101:mp 117102:mov AX,mcmp AX,njge 104103:jmp 107104:mov AX,aadd AX,1D105:mov BX,AXmov a,BX;跳出基本块前保存寄存器中已改变的变量值106:jmp 112,107:mov AX,kcmp AX,hje 109108:jmp 112109:mov AX,xadd AX,2D110:mov BX,AXmov x,BX;跳出基本块前保存寄存器中已改变的变量值111:jmp 107112:mov AX,m,add AX,y 113:mul x114:mov BX,nadd BX,AX115:mov CX,BXmov m,CX;跳出基本块前保存寄存器中已改变的变量值116:jmp 100117:retmain endp,code ends;代码段定义结束end start,