编译原理第12章 代码生成

编译原理之

代码生成华东交通大学软件学院万仲保代码生成概述目标代码的主要目标目标代码的主要形式生成目标代码衡量指标计算机模型简单的代码生成器全局寄存器分配代码生成概述代码生成是把经过语法分析或优化后的中间代码作为输入，将其转换成特定机器的机器语言或汇编语言作为输出，这样的转换程序称为代码生成器。代码生成的任务是在编译前端生成的中间代码的基础上，生成等价有效的目标代码，这也是一种程序变换，变换的结果是产生目标代码。等价是任一种程序变换的基本要求，因此讨论将集中在目标代码和如何产生有效的目标代码上。有效，是指目标代码占用的空间要省，运行的时间要短，这涉及充分利用寄存器和生成优化的代码序列的问题。目标代码的主要目标第一．使所生成的目标代码尽可能地短。第二，能较充分地发挥目标计算机可用资源的效率，如尽可能地使用执行速度较快的指令；充分利用计算机的寄存器或变址器，以节省访问内存的时间，等等。目标代码的主要形式具有绝对地址的机器语言程序可浮动的机器语言程序汇编语言形式的程序绝对地址的机器语言程序优点：最为有效，因为它们在存储空间中有固定的位置，一旦产生出此种形式的目标程序之后，便可直接投入运行。缺点：不能独立地完成源程序各程序块的编译，即使是供源程序调用的子程序也必须同时进行编译，因而灵活性较差。通常是在程序较短，而调试工作量较大的情况下，采用此种方式。可浮动的机器语言程序有较大的灵活性，故为许多编译程序所采用，只有执行连接装入程序本身需耗费一些时间。目标程序由若干个目的模块组成，各个模块中都包含目标程序中的一部分代码，且这些代码可在存储空间进行浮动(即可将它们装入到存储空间的任何位置)。此外，在各目的模块中还含有一些连接信息(如本模块需引用的其它模块中的符号名或子程序入口名)。对此种形式的目标代码，需经过连接装入程序把它们和所需的运行子程序的目的模块连接起来之后，才能投入运行。汇编语言形式的程序汇编语言形式较容易实现一些，但需在编译完毕之后额外增加一个汇编目标程序的阶段。尽管此种方式有某些优点，但并不是一种最好的方案。计算机模型假定一个计算机具有n个通用寄存器为R0，R1，…，Rn-l。它们既可作为累加器又可作为变址器，设定：用“op”表示运算符；用“M”表示内存单元；用变量名表示该变量所在的单元；“C”表示常量；“*”表示间址方式存取。模型机的指令形式模型机主要指令的意义模型机寻址方式模型机的指令形式类型指令形式意义（设op是二目运算符）直接地址型opRi,M(Ri)opM⇒Ri寄存器型opRi,Rj(Ri)op(Rj)⇒Ri变址型opRi,c(Rj)(Ri)op((Rj)+c)⇒Ri间接型opRi,*M(Ri)op(M)⇒RiopRi,*Rj(Ri)op((Rj))⇒RiopRi,*c(Rj)(Ri)op(((Rj)+c))⇒Ri模型机主要指令的意义指令意义指令意义LDRi，B把B单元的内容取到寄存器R，即(B)⇒RiJ<XJ≤X如CT＝0转X单元。如CT=0或CT＝1转X单元。STRi，B把寄存器Ri的内容存到B单元，即(Ri)⇒BJ=X如CT＝1转X单元。JB无条件转向X单元J≠X如CT≠1转X单元。CMPA，B把A单元和B单元的值进行比较，并根据比较情况把机器内部特征寄存器CT置成相应状态。根据A＜B或A＝B或A>B分别置CT为0或1或2。J>X

J≥X如CT＝2转X单元。如CT＝2或CT=1转X单元。模型机寻址方式编码名称助记符含义汇编后的情况1寄存器模式R(R)为操作数2间接寄存模式*R(R)为操作数地址3变址模式X(R)(R)+X为操作数地址X之值在本指令之后的单元中4间接变址模式*X(R)(R)+X为存放操作数地址的单元地址X之值在本指令之后的单元中5直接操作数#XX为操作数文字常数X在本指令之后的单元中6绝对地址XX为符号名，其值为操作数X的数据单元地址在本指令之后的单元中7间接地址*XX为符号名，其值为操作数地址X的数据单元地址在本指令之后的单元中生成目标代码衡量指标目标程序（指令条数）；执行目标程序所占的机器时间；目标程序所有指令执行代价的总和。简单的代码生成器寄存器分配的原则待用信息链表法代码生成算法寄存器分配的原则(1)当生成某变量的目标代码时，尽量让变量的值或计算结果保留在寄存器中直到寄存器不够分配时为止，这样引用变量值时可减少对内存的存取次数，以提高运行速度。(2)当到基本块出口时，将变量的值存放在内存中，因为一个基本块可能有多个后继结点或多个前驱结点，同一个变量名在不同前驱结点的基本块内出口前存放的R可能不同，或没有定值，所以应在出口前把寄存器的内容放在内存中，这样从基本块外入口的变量值都在内存中。(3)对于在一个基本块内后边不再被引用的变量所占用的寄存器应尽早释放，以提高寄存器的利用效率。待用信息链表法待用信息：在基本块B中，变量A在i点的值，j点引用，并且i→j的通路上没有A的其他定值和引用，则j为i处A的下一个引用点，即待用信息。计算变量待用信息的步骤示例计算变量待用信息的步骤(1)对各基本块的符号表中的“待用信息”栏和“活跃信息”栏置初值，即把“待用作息”栏置“非待用”，对“活跃信息”栏按在基本块出口处是否为活跃而置成“活跃”或“非活跃”。这里假定变量都是活跃的，临时变量都是非活跃的。(2)从基本块出口到基本块入口由后向前依次处理每个四元式i：A：=BopC，依次执行下述步骤：a)把符号表中变量A的待用信息和活跃信息附加到四元式i上。b)把符号表中变量A的待用信息栏和活跃信息栏分别置为“非待用”和“非活跃”。(由于在i中对A的定值只能在i以后的四元式才能引用，因而对i以前的四元式却说，A是不活跃也不可能是待用的）c)把符号表中B和C的待用信息和活跃信息附加到四元式i上。d)把符号表中B和C的待用信息栏置为“i”，活跃信息栏置为“活跃”。注意，以上a)和b)，c)和d)的次序不能颠倒。计算变量待用信息的示例例若用A，B，C，D表示变量，用T，U，V表示中间变量，有四元式如下：(1)T：=A-B(2)U：=A-C(3)V：=T+U(4)D：=V+U待用信息和活跃信息在四元式上的标记四元式的序号四元式上的标记(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代码生成算法寄存器描述:为了在代码生成中充分利用寄存器，生成尽可能简短的代码，将使用寄存器描述数组RVALUE[Ri]记录寄存器Ri是空闲着，还是已分配给某些变量。地址描述：将使用变量地址描述数组AVALUE[A]来记录变量A的现行值是存放在某个寄存器中，还是在某个主存单元中，或者既在寄存器中又在主存中。相关约定GETREG分配寄存器的算法代码生成算法相关约定过程函数GETREG(P:x:=yopz)给出参数P：x:=yopz，当然也意味着给出了语句P处的待用信息、活跃信息及当时各寄存器描述数组和变量地址描述数组，据此，为变量x分配寄存器R，以R作为函数值返回。RVALUE[Ri]＝{A，C}表示Ri的现行值是变量A，C的值。VALUE[A]＝{A}表示A的值在内存中。AVALUE[A]＝{Ri，A}表示A的值在寄存器Ri中又在内存中。AVALUE[A]＝{Ri}表示变量A的值在寄存器Ri中。GETREG分配寄存器的算法(1)如果B的现行值在某寄存器Ri中，且该寄存器只包含B的值，或者B与A是同一标识符，或B在该四元式后不会再被引用，则可选取Ri为所需的寄存器R，并转(4)。(2)如果有尚未分配的寄存器，则从中选用一个Ri为所需的寄存器R，并转(4)。(3)从已分配的寄存器中选取一个Ri作为所需寄存器R，其选择原则为：占用该寄存器的变量值同时在主存中，或在基本块中引用的位置最远。这样对寄存器Ri所含的变量和变量在主存中的情况必须先做如下调整：即对RVALU[Ri]中的每一变量M，如果M不是A且AVALUE[M]不包含M，则需完成以下处理：a)生成目标代码STRi，M；即把不是A的变量值由Ri中送入内存中。b)如果M不是B，则令AVALUE[M]={M}，否则，令AVALUE[M]={M，R}。c)删除RVALU[Ri]中的M。(4)给出R，返回。这样，一旦得到了一个为四元式运算的操作寄存器R，就可以进行代码生成，而当目标代码生成完成后，则又需修改寄存器的使用信息和地址描述信息。算法的流程图GETREG算法的流程图开始B’=R?C’=R?B’是否待用?B’=Ri?C’是否待用?C’=Ri?修改B的地址描述AVALUE[B]：=AVALUE[B]-{R}修改C的地址描述AVALUE[C]：=AVALUE[C]-{R}修改A的地址描述AVALUE[A]：={R}AVALUE[R]：={A}释放B所占用的寄存器RiRVALUE[Ri]：=RVALUE[Ri]-{B}AVALUE[B]：=AVALUE[B]-{Ri}释放C所占用的寄存器RiRVALUE[Ri]：=RVALUE[Ri]-{C}AVALUE[C]：=AVALUE[C]-{Ri}结束YNYYYNNNNYY代码生成算法对于语句P：x:=yopz，执行下列步骤：(1)调用GETREG(P：x:=yopz)，设返回的寄存器为R，供x存放现行值。(2)由变量地址描述数组AVALUE[y]、AVALUE[z]确定变量y、z的现行值存放位置y′，z′，当现行值在寄存器中时，便将该寄存器作为y′或z′。(3)如果y′≠R，生成目标代码MOVy′RopRz′否则只生成目标代码opRz′。当y′或z′为R时，删除AVALUE[y]或AVALUE[z]中的R。(4)修改两个描述数组，表示x占用R，即含AVALUE[x]={R}，RVALUE[R]={x}。

(5)如果在P点y或z不再被引用(不待用，不活跃)，并且其现行值占用某寄存器R′，则释放该寄存器R′，即从RVALUE[R′]中删去y或z，从AVALUE[y]或AVALUE[z]中删去R′。代码生成算法的流程图开始结束分配操作寄存器R：GETREG（i：A：=BopC）取B，C现行存放的位置B’，C’B：=AVALUE[B]C：=AVALUE[C]B’=R?生成目标码opRC’生成目标码LDR，B’opRC’修改寄存器使用的信息和地址描述信息YN全局寄存器分配四元式的目标代码形式分配寄存器的原则：降低目标代码执行代价。分配寄存器的策略计算目标代码执行代价的方法执行循环一次所节省的执行代价总数计算执行代价需考虑因素示例四元式的目标代码形式四元式指令说明A：=BMOVB，R若当前B的值在其一寄存器R中，则不必产生目标代码，而只须把A添加到R的描述符中，并把A的地址描述符置为R(即指明A的当前值仅在R中)即可。当B在块中不再被引用且在块的出口之后不活跃时，还应从R的描述符中删去B，从B的地址描述符中删去R。但若B的当前值只在内存单元中，如果仅简单地把A的地址描述符置为B的内存地址，那么，若不对A的值采取保护措施，A的值就会为B的再定值所影响。可见，在此情况下，还是为它产生一条形如MOVB，R的指令较为稳妥。R是分配给A的寄存器。A：=opB对它的处理与对二元运算的处理极为类似。A：=B[I]MOVI，RMOVB(R),R执行代价为5，I的当前值不在寄存器中，则产生之。MOVB(Ri),R执行代价为3，I的当前值在某一寄存器Ri中时，则仅产生之。A[T]:=BMOVI,RMOVB,A(Ri)执行代价为6，I的当前值不在寄存器中，则产生之。MOVB,A(Ri)执行代价为4，I的当前值在某一寄存器Ri中时，则仅产生之。四元式的目标代码形式(二)四元式指令说明A:=P↑MOV*P,A执行代价为4MOVP,RMOV*R,R执行代价为4MOV*Ri,R2，特别，当P的当前值在某一寄存器R6中时，可产生的指令。如果A的当前值在块内还会被引用，且此时尚有未被占用的寄存器R供A使用，则最好按第二或第三种形式产生目标代码。P↑:=AMOVA,*PMOVA,RMOVR,*PMOVA,*RgotoXBRX’X’是序号为X的四元式的目标代码首址。IfAropbgotoXCMPA,BJropX’X’是序号为X的四元式的目标代码首址。如果A和(或)B的当前值在寄存器中，则在产生目标代码时，应尽可能用寄存器寻址模式。分配寄存器的策略首先，所考虑的范围需从一个基本块扩大至一个循环L，故对于在L的某基本块B中定值的变量V，如果它已占用一个固定的寄存器，而且V在B的出口之后活跃，则不必再把V的值存放到内存单元之中。其次，对于循环中的每一变量V，还需估计当它独占一个寄存器时，对于降低执行代价的效果有多大。显然，应将寄存器优先分配给那些降低执行代价效果最为显著的一些变量。计算目标代码执行代价的方法如果V在B中被定值，且V的定值点之后有其引用点，则按生成代码算法为B生成代码时，一般是把V的当前值保留在某一寄存器R中。如果在整个循环L中，把R作为V的一个独占寄存器，则对于基本块B而言，不仅V的定值点之后的引用点可引用R中之值，而且其前的V的引用点也可以引用(甚至在L的其它基本块中也同样可以引用，如果该V的定值能到达这些引用点的话)。然而，在生成代码算法中，仅考虑了前一情况，而对后一情况却未加以考虑(因为生成代码算法并未把R作为V的一个独占寄存器)，因此，在现在的情况下，对于B中V的定值点之前的那些四元式，如果在为它们生成目标代码时，也把对v的引用处理为对R内容的引用，则使其中的每一个对V的引用都节省了执行代价1。由于现在已为B中的变量V分配了固定的寄存器，因此，当V在B的出口之后活跃时，也就不必把V的值送入内存，这样一来，就使执行代价又节省了2。执行循环一次所节省的执行代价总数对于循环L中的某一变量，当给它分配了一个固定的寄存器之后，则每执行循环一次所节省的执行代价总数(相对于按代码生成算法生成的代码)为：

＝(USE(V，B)+2*LIVE(V，B))（B∊L）其中：USE(V，B)为基本块B中V的定值点之前对V引用的次数；1当V在B中定值，且V在B的出口之后活跃LIVE（V，B）＝0其它计算执行代价需考虑因素1．若V在L的入口之前是活跃的，且在L中已给V分配了固定的寄存器R，则应在L的前置结点中，产生将V之值从内存单元取至R的指令，故所增加的执行代价为2。此外，对于循环的每一出口块B，设B’是B在循环外的一个直接后继块，若V在B’前活跃，则当由B退出循环时，应将V的当前值由R送入内存，由此可能增加的执行代价为2，好在上述两方面的操作仅分别在循环的入口之前和退出循环时执行一次，故将它们略去不计将不会对之值产生太大的影响。2．执行代价计算公式是在这样的假定下推出的，即每循环一次都遍及循环中的各个基本块，然而实际情况并非总是如此，有时甚至会出