编译原理 第7章 目标代码生成

第7章目标代码生成第7章目标代码生成7.1一个简单代码生成器7.2汇编指令到机器代码的翻译概述第7章目标代码生成7.1一个简单代码生成器我们首先介绍一个简单的代码生成器，此生成器依次把每条中间代码变换成目标代码，并且在一个基本块范围内考虑如何充分利用寄存器的问题。一方面，在基本块中，当生成计算某变量值的目标代码时，尽可能地让该变量的值保留在寄存器中(即不编出把该变量的值存到内存单元的指令)，直到该寄存器必须用来存放其它变量的值或已达基本块出口为止；另一方面，后续的目标代码尽可能地引用变量在寄存器中的值而不访问内存。第7章目标代码生成例如，一C语言语句为A=(B+C)*D+E，把它翻译为四元式G：T1=B+CT2=T1*DA=T2+E如果不考虑代码的效率，可以简单地把每条中间代码(四元式)映射成若干条目标指令，如将x=y+z映射为：MOVAX,y/*AX为寄存器*/ADDAX,zMOVx,AX第7章目标代码生成其中，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第7章目标代码生成虽然从正确性来看，这种翻译不存在问题，但它却存在冗余。在上述指令序列中，(4)和(7)两条指令是多余的；而T1、T2均是中间代码生成时产生的临时变量，它们在出了基本块后将不再使用，故(3)、(6)两条指令也可删去。所以，在考虑了效率和充分使用寄存器之后，应生成如下代码：第7章目标代码生成(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章目标代码生成7.1.1待用信息与活跃信息在一个基本块内的目标代码中，为了提高寄存器的使用效率，应将基本块内还要被引用的值尽可能地保留在寄存器中，而将基本块内不再被引用的变量所占用的寄存器尽早释放。每当翻译一条四元式如A=BopC时，需要知道在基本块中还有哪些四元式要对变量A、B、C进行引用，为此，需要收集一些待用信息。在一个基本块中，四元式i对变量A定值，如果i后面的四元式j要引用A且从i到j的四元式没有其它对A的定值点，则称j是四元式i中对变量A的待用信息，同时也称A是活跃的；如果A被多处引用，则构成了A的待用信息链与活跃信息链。第7章目标代码生成为了取得每个变量在基本块内的待用信息和活跃信息，可从基本块的出口由后向前扫描，对每个变量建立相应的待用信息链与活跃信息链。如果没有进行数据流分析并且临时变量不允许跨基本块引用，则把基本块中的临时变量均看作基本块出口之后的非活跃变量，而把所有的非临时变量均看作基本块出口之后的活跃变量。如果某些临时变量能够跨基本块使用，则把这些临时变量也看成基本块出口之后的活跃变量。假设变量的符号表内有待用信息和活跃信息栏，则计算变量待用信息的算法如下：第7章目标代码生成(1)首先将基本块中各变量的符号表的待用信息栏置为“非待用”，对活跃信息栏则根据该变量在基本块出口之后是否活跃而将该栏中的信息置为“活跃”或“非活跃”。(2)从基本块出口到基本块入口由后向前依次处理各四元式。对每个四元式i：A=BopC依次执行以下步骤：第7章目标代码生成①把符号表中变量A的待用信息和活跃信息附加到四元式i上；②把符号表中变量A的待用信息和活跃信息分别置为“非待用”和“非活跃”；③把符号表中变量B和C的待用信息和活跃信息附加到四元式i上；④把符号表中B和C的待用信息置为i，活跃信息置为“活跃”。第7章目标代码生成例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章目标代码生成[解答]我们根据计算变量待用信息的算法得到各变量的待用信息链和活跃信息链如表7.1所示。表中的“F”表示“非待用”或“非活跃”，“L”表示“活跃”，(1)～(4)分别表示基本块中的四个四元式。待用信息链和活跃信息链的每列从左到右为每行从后向前扫描一个四元式时相应变量的信息变化情况(空白处表示没有变化)。第7章目标代码生成表7.1例7.1的待用信息链和活跃信息链变量名待用信息活跃信息初值待用信息链初值活跃信息链TF(3)FFLLFAF(2)(1)LLBF(1)LLCF(2)LLUF(4)(3)FFLLFVF(4)FFLFDFFLF第7章目标代码生成待用信息和活跃信息在四元式上的标记如下：(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+UFF第7章目标代码生成7.1.2代码生成算法为了在代码生成中进行寄存器分配，需要随时掌握各寄存器的使用情况，即它是处于空闲状态还是已分配给某个变量或已分配给某几个变量。通常用一个寄存器描述数组RVALUE动态地记录各寄存器的当前状况，并用寄存器Ri的编号作为它的下标。此外，还需建立一个变量地址描述数组AVALUE来记录各变量现行值存放的位置，即其是在某寄存器中还是在某内存单元中，或者同时存在于某寄存器和某内存单元中，可以有如下表示：第7章目标代码生成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中又在内存中*/第7章目标代码生成为了简单起见，假设基本块中每个四元式的形式都是A=BopC，则代码生成算法是对每个四元式i：A=BopC执行下述步骤：(1)调用函数GETREG(i：A=BopC)返回存放A值结果的寄存器R。(2)通过地址描述数组AVALUE[B]和AVALUE[C]确定出变量B和变量C的现行值存放位置B'和C'；如果是存放在寄存器中，则把寄存器取作B'和C'。第7章目标代码生成(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的现行值。第7章目标代码生成(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)。第7章目标代码生成(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；第7章目标代码生成②当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章目标代码生成表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中第7章目标代码生成对其它形式的四元式也可仿照上述算法生成其目标代码。这里特别要指出的是，对形如A=B的复写，如果B的现行值在某寄存器Ri中，那么无需生成目标代码，只需在RVALUE[Ri]中增加一个A(即把Ri同时分配给B和A)，把AVALUE[A]改为Ri；而且如果其后B不再被引用，还可把RVALUE[Ri]中的B和AVALUE[B]中的Ri删除。处理完基本块中所有的四元式后，对现行只在某寄存器中的每个变量，如果它在基本块出口之后是活跃的，则要用MOV指令把它在寄存器中的值存放到数据区以它命名的内存单元中。第7章目标代码生成为进行这一工作，我们利用寄存器描述数组RVALUE来决定其中哪些变量的现行值在寄存器中，再利用地址描述数组AVALUE来决定其中哪些变量的现行值尚不在其内存单元中，最后利用活跃变量信息来决定其中哪些变量是活跃的。例如，由例7.2的表7.2查RVALUE栏可知：U和D的值在寄存器中，而从AVALUE栏知U和D的值都不在内存单元中，又由例7.1表7.1知，D在基本块出口之后是活跃变量，所以，在表7.2所生成的目标代码后面还要生成一条目标代码：MOVD,AX第7章目标代码生成7.1.3寄存器分配由于寄存器数量有限，为了生成更有效的目标代码，就必须考虑如何更有效地利用寄存器。为此，我们定义指令的执行代价如下：每条指令的执行代价=每条指令访问内存单元次数+1假定在循环中，某寄存器固定分配给某变量使用，那么对循环中的每个基本块，相对于原简单代码生成算法所生成的目标代码，所节省的执行代价可用下述方法计算：第7章目标代码生成(1)在原代码生成算法中，仅当变量在基本块中被定值时，其值才存放在寄存器中。现在把寄存器固定分配给某变量使用，当该变量在基本块中被定值前，每引用它一次就可以少访问一次内存，则执行代价节省1。(2)在原代码生成算法中，如果某变量在基本块中被定值且在基本块出口之后是活跃的，则出基本块时要把它在寄存器中的值存放到内存单元中。现在把寄存器固定分配给某变量使用，出基本块时就无需把它的值存放到其内存单元中，则执行代价节省2。第7章目标代码生成因此，对循环L中的变量M，如果分配一个寄存器给它专用，那么每执行循环一次，其执行代价的节省数可用下式计算：其中，USE(M,B)=基本块B中对M定值前引用M的次数1如果M在基本块B中被定值且在B的出口之后是活跃的LIVE(M,B)==0其它情况B∈L∑[USE(M,B)+2*LIVE(M,B)]第7章目标代码生成例7.3一代码序列及程序流图如图7–1所示。假定各基本块出口之后的活跃变量均为a、b、c，循环中的固定寄存器为AX、BX，则将AX、BX固定分配给循环中哪两个变量可使执行代价节省得最多？第7章目标代码生成(1)a＝b－c(2)d＝a＋4(3)e＝a－b(4)f＝c＋e(5)b＝b＋c(6)c＝b－f(7)ifb＜cgoto(10)B1B5(8)b＝b－c(9)f＝b＋fB2B3(10)a＝a－f(11)ifa≥fgoto(3)(12)haltB4图7–1程序流图第7章目标代码生成[解答](1)考虑变量a的