第七章目标代码生成

第7章目标代码生成代码生成是指把语法分析后或者优化后的中间代码(如四元式或三元式)变换成目标代码，所生成的目标代码一般有如下三种形式：(1)能够立即执行的机器语言代码，它们通常放在固定的存储区中并可直接执行，如PC机中后缀为 .COM或 .EXE的文件。(2)待装配的机器语言模块，其地址均为相对地址，所以不能直接执行。当需要执行时由连接装配程序把它们与其它运行程序和库函数连接起来，装配成可执行的机器语言代码，如PC机中后缀为 .OBJ的文件都属于待装配的模块(文件)。(3)汇编语言程序，必须通过汇编程序的汇编方可转换成可执行的机器语言代码，如PC机中后缀为 .ASM的文件即为汇编语言程序。一个高级语言程序的目标代码要经常、反复使用，因此代码生成要着重考虑两个问题：一是如何使生成的目标代码较短，二是如何充分利用计算机的寄存器以减少目标代码中访问存储单元的次数。生成的目标代码越短，寄存器的利用越充分，目标代码的质量也就越高。设计一个代码生成器需要考虑具体的机器结构、指令格式、字长及寄存器个数和种类，并且与指令的语义和所用的操作系统、存储管理等都密切相关。7.1一个简单代码生成器一个简单的代码生成器，此生成器依次把每条中间代码变换成目标代码，并且在一个基本块范围内考虑如何充分利用寄存器的问题。一方面，在基本块中，当生成计算某变量值的目标代码时，尽可能地让该变量的值保留在寄存器中(即不编出把该变量的值存到内存单元的指令)，直到该寄存器必须用来存放其它变量的值或已达基本块出口为止；另一方面，后续的目标代码尽可能地引用变量在寄存器中的值而不访问内存。如一C语言语句A=(B+C)*D+E，翻译为四元式G：T1=B+CT2=T1*DA=T2+E如果不考虑代码的效率，可以简单地把每条中间代码(四元式)映射成若干条目标指令，如将x=y+z映射为MOVAX,y/*AX为寄存器*/ADDAX,zMOVx,AX其中，x、y、z均为数据区的内存变量。上述四元式代码序列G可翻译为(1) MOVAX,B(2) ADDAX,C(3) MOVT1,AX(4) MOVAX,T1(5) MULAX,D(6) MOVT2,AX(7) MOVAX,T2(8) ADDAX,E(9) MOVA,AX从正确性来看，这种翻译不存在问题，但却存在冗余。指令序列中的(4)和(7)两条指令是多余的；而T1、T2均是中间代码生成时产生的临时变量，它们在出了基本块后将不再使用，故(3)、(6)两条指令也可删去。因此，在考虑了效率和充分使用寄存器之后，应生成如下代码：(1) MOVAX,B(2) ADDAX,C(3) MULAX,D(4) ADDAX,E(5) MOVA,AX为了实现这一目的，代码生成器就必须了解一些信息：在产生T2=T1*D对应的目标代码时，为了省去指令MOVAX,T1，就必须知道T1的当前值已在寄存器AX中；为了省去MOVT1,AX，就必须知道出了基本块后T1不再被引用。7.1.1待用信息与活跃信息在一个基本块内的目标代码中，为了提高寄存器的使用效率，应将基本块内还要被引用的值尽可能地保留在寄存器中，而将基本块内不再被引用的变量所占用的寄存器尽早释放。每当翻译一条四元式如A=BopC时，需要知道在基本块中还有哪些四元式要对变量A、B、C进行引用，为此，需要收集一些待用信息。在一个基本块中，四元式i对变量A定值，如果i后面的四元式j要引用A且从i到j的四元式没有其它对A的定值点，则称j是四元式i中对变量A的待用信息，同时也称A是活跃的。如果A被多处引用，则构成了A的待用信息链与活跃信息链。为了取得每个变量在基本块内的待用信息和活跃信息，可从基本块的出口由后向前扫描，对每个变量建立相应的待用信息链与活跃信息链。如果没有进行数据流分析并且临时变量不允许跨基本块引用，则把基本块中的临时变量均看作基本块出口之后的非活跃变量，而把所有的非临时变量均看作基本块出口之后的活跃变量。如果某些临时变量能够跨基本块使用，则把这些临时变量也看成基本块出口之后的活跃变量。假设变量的符号表内有待用信息和活跃信息栏，则计算变量待用信息的算法如下：(1)首先将基本块中各变量的符号表的待用信息栏置为“非待用”，对活跃信息栏则根据该变量在基本块出口之后是否活跃而将该栏中的信息置为“活跃”或“非活跃”。(2)从基本块出口到基本块入口由后向前依次处理各四元式。对每个四元式i：A=BopC依次执行以下步骤：①把符号表中变量A的待用信息和活跃信息附加到四元式i上；②把符号表中变量A的待用信息和活跃信息分别置为“非待用”和“非活跃”；③把符号表中变量B和C的待用信息和活跃信息附加到四元式i上；④把符号表中变量B和C的待用信息置为i，活跃信息置为“活跃”。注意：以上①～④次序不能颠倒，如果四元式出现A=opB或者A=B形式，则以上执行步骤完全相同，只是其中不涉及变量C。例7.1考察基本块：(1) T=A−B(2) U=A−C(3) V=T+U(4) D=V+U其中，A、B、C、D为变量，T、U、V为中间变量。试求各变量的待用信息链和活跃信息链。[解答]我们根据计算变量待用信息的算法得到各变量的待用信息链和活跃信息链如表7.1所示。表中的“F”表示“非待用”或“非活跃”，“L”表示“活跃”，(1)～(4)分别表示基本块中的四个四元式。待用信息链和活跃信息链的每列从左到右为每行从后向前扫描一个四元式时相应变量的信息变化情况(空白处表示没有变化)。表7.1例7.1的待用信息链和活跃信息链待用信息活跃信息变量名初值待用信息链初值活跃信息链TF(3)FFLFAF(2)(1)LLLBF(1)LLCF(2)LLUF(4)(3)FFLLFVF(4)FFLFDFFLF待用信息和活跃信息在四元式上的标记如下(每个变量都先去掉待用信息链和活跃信息链最右的值，然后由右向左依次引用所出现的值)：(1) T(3)L=A(2)L − BFL(2) U(3)L=AFL − CFL(3) V(4)L=TFF+U(4)L(4) DFL=VFF+UFF7.1.2代码生成算法为了在代码生成中进行寄存器分配，需要随时掌握各寄存器的使用情况，即它是处于空闲状态还是已分配给某个变量或已分配给某几个变量。通常用一个寄存器描述数组RVALUE动态地记录各寄存器的当前状况，并用寄存器Ri的编号作为它的下标。此外，还需建立一个变量地址描述数组AVALUE来记录各变量现行值存放的位置，即其是在某寄存器中还是在某内存单元中，或者同时存在于某寄存器和某内存单元中，可以有如下表示：RVALUE[Ri]={A}/*寄存器Ri分配给变量A*/RVALUE[Ri]={A,B}/*寄存器Ri分配给变量A和B*/RVALUE[Ri]={}/*未分配*/AVALUE[A]={A}/*表示A的值在内存中*/AVALUE[A]={Ri}/*表示A的值在寄存器Ri中*/AVALUE[A]={Ri,A}/*表示A的值既在寄存器Ri中又在内存中*/假设基本块中每个四元式的形式都是A=BopC，则代码生成算法是对每个四元式i：A=BopC执行下述步骤：(1)调用函数GETREG(i：A=BopC)返回存放A值结果的寄存器R。(2)通过地址描述数组AVALUE[B]和AVALUE[C]确定出变量B和变量C的现行值存放位置B'和C'；如果是存放在寄存器中，则把寄存器取作B'和C'。(3)如果B'≠R，则生成目标代码：MOVR,B'opR,C'否则生成目标代码：opR,C'如果B'或C'为R，则删除AVALUE[B]或AVALUE[C]中的R。(4)令AVALUE[A]={R}并令RVALUE[R]={A}，表示变量A的现行值只在R中且R中的值只代表A的现行值。(5)如果B和C的现行值在基本块中不再被引用，它们也不是基本块出口之后的活跃变量且它们的现行值存放在寄存器Rk中，则删除RVALUE[Rk]中的B和C以及AVALUE[B]中的Rk，使寄存器Rk不再为B和C所占用。函数GETREG(i：A=BopC)用来得到存放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，则生成目标代码MOVM,Ri；②当M不是A时，如果M是B或者M是C且同时B也在RVALUE[Ri]中，则令AVALUE[M]={M,R}，否则令AVALUE[M]={M}；③删除RVALUE[Ri]中的M。(4)给出R，返回。例7.2对例7.1，假设只有AX和BX是可用寄存器，用代码生成算法生成目标代码及其相应的RVALUE和AVALUE。[解答]用代码生成算法生成的目标代码及其相应的RVALUE和AVALUE，如表7.2所示。表7.2例7.2的目标代码四元式目标代码RVALUEAVALUET=A−BMOVAX,ASUBAX,BAX含有TT在AX中U=A−CMOVBX,ASUBBX,CAX含有TBX含有UT在AX中U在BX中V=T+UADDAX,BXAX含有VBX含有UV在AX中U在BX中D=V+UADDAX,BXAX含有DD在AX中对其它形式的四元式也可仿照上述算法生成其目标代码。这里特别要指出的是，对形如A=B的复写，如果B的现行值在某寄存器Ri中，那么无需生成目标代码，只需在RVALUE[Ri]中增加一个A(即把Ri同时分配给B和A)，把AVALUE[A]改为Ri；而且如果其后B不再被引用，还可把RVALUE[Ri]中的B和AVALUE[B]中的Ri删除。处理完基本块中所有的四元式后，对现行只在某寄存器中的每个变量，如果它在基本块出口之后是活跃的，则要用MOV指令把它在寄存器中的值存放到数据区以它命名的内存单元中。为进行这一工作，我们利用寄存器描述数组RVALUE来决定其中哪些变量的现行值在寄存器中，再利用地址描述数组AVALUE来决定其中哪些变量的现行值尚不在其内存单元中，最后利用活跃变量信息来决定其中哪些变量是活跃的。例如，由例7.2的表7.2查RVALUE栏可知：U和D的值在寄存器中，而从AVALUE栏知U和D的值都不在内存单元中，如果D在基本块出口之后是活跃变量，则在表7.2所生成的目标代码后面还要生成一条目标代码：MOVD,AX7.1.3寄存器分配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;************************************datasegment;定义数据