第11章 目标代码生成

12词法分析器语法分析器中间代码生成器优化段源程序单词符号语法单位四元式表格管理出错处理目标代码生成器四元式目标代码3•代码生成是把语法分析后或优化后的中间代码变换成目标代码。•目标代码一般有以下三种形式：–能够立即执行的机器语言代码，所有地址已经定位；–待装配的机器语言模块。执行时，由连接装配程序把它们和某些运行程序连接起来，转换成能执行的机器语言代码；–汇编语言代码。尚须经过汇编程序汇编，转换成可执行的机器语言代码。4•代码生成着重考虑的问题：–如何使生成的目标代码较短；–如何充分利用计算机的寄存器，减少目标代码中访问存贮单元的次数。–如何充分利用计算机的指令系统的特点。5§11.1基本问题代码生成器的设计细节依赖于目标语言和操作系统：内存管理、寄存器管理等。其一般问题主要有：6中间代码表示可采用不同的形式：•线性表示法如后缀式•三地址表示法如四元式；•抽象机表示法如栈式机器代码；•图表示法如语法树。1.代码生成器的输入——中间代码的表示及符号表中的信息7符号表登记了说明语句中说明的各种名字的种属、类型等信息，根据这些信息可确定名字在所属过程的数据区域中的相对地址，因此，代码生成器可以利用这些信息来决定在中间代码中的名字所指示的数据对象的运行时地址，它是可再定位的或绝对地址。82.目标程序输出的形式共有三种绝对机器代码——可立即执行待装配机器代码——连接与装入需一定代价，但灵活汇编语言代码——汇编器再加工93.指令选择指令集的一致性和完全性是重要因素。如果目标机器不能支持指令集的所有类型，则每一种例外都需要特别的处理；指令速度和机器用语也是重要因素。如果不考虑效率，则指令选择可以直接做，对每种类型的中间代码，可勾划出其框架，例：对中间代码x:=y+z可翻译成：LDR0,yADDR0,zSTR0,x10生成代码的质量取决于它的速度和大小。一个有着丰富的目标指令集的机器可以为一个给定的操作提供几种实现方法，有些实现正确但不一定是高效的。例：如果目标机器有“加1”指令INC，则用INCa实现a:=a+1是最有效的，而不是下列指令序列：LDR0,aADDR0,#1STR0,a114.寄存器分配由于指令对寄存器的操作常常要比对存储单元的操作快且指令短，因此，如何充分利用寄存器，对于生成好的代码非常重要。(1)在寄存器分配期间，为程序的某一点选择驻留在寄存器中的一组变量；(2)在随后的寄存器指派阶段，挑出变量将要驻留的具体寄存器，选择最优的寄存器指派方案是困难的，属于NP完全问题。125.计算顺序选择6.最重要的评价标准——产生正确的代码在此前提下，使设计的代码生成器能够易于实现、测试及维护，这也是重要的设计目标。计算完成的顺序会影响目标代码的有效性。13§11.2目标机器模型要设计一个好的代码生成器，必须预先熟悉目标机器和它的指令系统。•考虑一个抽象的计算机模型–具有多个通用寄存器，他们既可以作为累加器，也可以作为变址器。–运算必须在某个寄存器中进行。–含有四种类型的指令形式14类型指令形式意义(设op是二目运算符)直接地址型opRi,M(Ri)op(M)Ri寄存器型opRi,Rj(Ri)op(Rj)Ri变址型opRi,c(Rj)(Ri)op((Ri)+c)Ri间接型opRi,*MopRi,*RjopRi,*c(Rj)(Ri)op((M))Ri(Ri)op((Rj))Ri(Ri)op(((Rj)+c))Ri如果op是一目运行符，则“opRi,M”的意义为：op（M）Ri，其余类型可类推。15op包括一般计算机上常见的一些运算符，如ADD加SUB减MUL乘DIV除16指令意义LDRi,B把B单元的内容取到寄存器R，即（B）RiSTRi,B把寄存器Ri的内容存到B单元，即（Ri）BJX无条件转向X单元CMPA,B把A单元和B单元的值进行比较，并根据比较情况把机器内部特征寄存器CT置成相应状态。CT占两个二进位。根据AB或A=B或AB分别置CT为0或1或2。J＜X如CT=0转X单元J≤X如CT=0或CT=1转X单元J＝X如CT=1转X单元J≠X如CT≠1转X单元J＞X如CT=2转X单元J≥X如CT=2或CT=1转X单元17•不考虑代码的执行效率，目标代码生成是不难的，例如：A:=(B+C)*D+E翻译为四元式：T1:=B+CT2:=T1*DT3:=T2+EA:=T311.3一个简单代码生成器18假设只有一个寄存器可供使用•目标代码：LDR0，BADDR0，CSTR0，T1•假设T1，T2，T3在基本块之后不再引用:LDR0，BADDR0，CMULR0，DADDR0，ESTR0，A•四元式T1:=B+CT3:=T2+ET2:=T1*DA:=T3LDR0，T1MULR0，DSTR0，T2LDR0，T2ADDR0，ESTR0，T3LDR0，T3STR0，A1911.3一个简单代码生成器•四元式的中间代码变换成目标代码，并在一个基本块的范围内考虑如何充分利用寄存器：–尽可能留：在生成计算某变量值的目标代码时，尽可能让该变量保留在寄存器中。–尽可能用：后续的目标代码尽可能引用变量在寄存器中的值，而不访问内存。–及时腾空：在离开基本块时，把存在寄存器中的现行的值放到主存中。2011.3.1待用信息•如果在一个基本块内，四元式i对A定值，四元式j要引用A值，而从i到j之间没有A的其他定值，那么，我们称j是四元式i的变量A的待用信息。（即下一个引用点）i:A:=BopC…j:D:=AopE•假设在变量的符号表登记项中含有记录待用信息和活跃信息的栏。21•待用信息和活跃信息的表示：1(x,x)表示变量的待用信息和活跃信息。其中i表示待用信息，y表示活跃，^表示非待用和非活跃；2在符号表中，(x，x)→(x，x)表示后面的符号对代替前面的符号对；3不特别说明，所有说明变量在基本块出口之后均为非活跃变量。22•计算待用信息和活跃信息的算法步骤：1.开始时，把基本块中各变量的符号表登记项中的待用信息栏填为“非待用”，并根据该变量在基本块出口之后是不是活跃的，把其中的活跃信息栏填为“活跃”或“非活跃”；232.从基本块出口到基本块入口由后向前依次处理各个四元式。对每一个四元式i:A:=BopC，依次执行下面的步骤：1)把符号表中变量A的待用信息和活跃信息附加到四元式i上；2)把符号表中A的待用信息和活跃信息分别置为“非待用”和“非活跃”；3)把符号表中变量B和C的待用信息和活跃信息附加到四元式i上；4)把符号表中B和C的待用信息均置为i，活跃信息均置为“活跃”。24例：基本块1.T:=A-B2.U:=A-C3.V:=T+U4.W:=V+U设W是基本块出口之后的活跃变量。建立待用信息链表与活跃变量信息链表如下：25变量名初始状态→信息链(待用/活跃信息栏)T(^,y)→(3,y)→(^,^)A(^,^)→(2,y)→(1,y)B(^,^)→(1,y)C(^,^)→(2,y)U(^,^)→(4,y)→(3,y)→(^,^)V(^,^)→(4,y)→(^,^)W(^,y)→(^,^)26•附加在四元式上的待用/活跃信息表：(4)W:=V+U(3)V:=T+U(2)U:=A-C(1)T:=A-B(^,y)(^,^)(^,^)(4,y)(^,^)(4,y)(3,y)(^,^)(^,^)(3,y)(2,y)(^,^)序号四元式左值左操作数右操作数变量名初始状态→信息链(待用/活跃信息栏)→(3,y)→(^,^)→(2,y)→(1,y)→(1,y)→(2,y)→(4,y)→(^,^)→(3,y)T(^,^)A(^,^)B(^,^)C(^,^)U(^,^)V(^,^)W(^,y)→(^,^)→(4,y)→(^,^)27•寄存器描述数组RVALUE–动态记录各寄存器的使用信息–RVALUE[R]={A,B}•变量地址描述数组AVALUE–动态记录各变量现行值的存放位置–AVALUE[A]={R1,R2,A}28•补充说明：–因为寄存器的分配是局限于基本块范围之内的，一旦处理完基本块中所有四元式，对现行值在寄存器中的每个变量，如果它在基本块之后是活跃的，则要把它存在寄存器中的值存放到它的主存单元中。–要特别强调的是，对形如：A:=B的四元式，如果B的现行值在某寄存器Ri中，则无须生成目标代码，只须在RVALUE(Ri)中增加一个A，(即把Ri同时分配给B和A)，并把AVALUE(A)改为Ri。29•代码生成算法：对每个四元式:i:A:=BopC，依次执行：1.以四元式:i:A:=BopC为参数，调用函数过程GETREG(i:A:=BopC)，返回一个寄存器R，用作存放A的寄存器。2.利用AVALUE[B]和AVALUE[C]，确定B和C现行值的存放位置B’和C’。如果其现行值在寄存器中，则把寄存器取作B’和C’303.如果B’≠R，则生成目标代码：LDR,B’opR,C’否则生成目标代码opR,C’如果B’或C’为R，则删除AVALUE[B]或AVALUE[C]中的R。4.令AVALUE[A]={R},RVALUE[R]={A}。315.若B或C的现行值在基本块中不再被引用，也不是基本块出口之后的活跃变量，且其现行值在某寄存器Rk中，则删除RVALUE[Rk]中的B或C以及AVALUE[B]或AVALUE[C]中的Rk，使得该寄存器不再为B或C占用。32•寄存器分配：GETREG(i:A:=BopC)返回一个用来存放A的值的寄存器1如果B的现行值在某个寄存器Ri中，RVALUE[Ri]中只包含B，此外，或者B与A是同一个标识符，或者B的现行值在执行四元式A:=BopC之后不会再引用，则选取Ri为所需要的寄存器R，并转4；2如果有尚未分配的寄存器，则从中选取一个Ri为所需要的寄存器R，并转4；1尽可能用B独占的寄存器2后尽可能用空闲寄存器3抢占用非空闲寄存器333从已分配的寄存器中选取一个Ri为所需要的寄存器R。最好使得Ri满足一下条件：占用Ri的变量的值也同时存放在该变量的贮存单元中，或者在基本块中要在最远的将来才会引用到或不会引用到。要不要为Ri中的变量生成存数指令？1尽可能用B所在的寄存器2后尽可能用空闲寄存器3抢占用非空闲寄存器34要不要为Ri中的变量生成存数指令？对RVALUE[Ri]中每一变量M，如果M不是A，或者如果M是A又是C，但不是B并且B也不在RVALUE[Ri]中，则(1)如果AVALUE[M]不包含M，则生成目标代码STRi，M(2)如果M是B，或者M是C但同时B也在RVALUE[Ri]中，则令AVALUE[M]={M，Ri}，否则令AVALUE[M]={M}(3)删除RVALUE[Ri]中的M4给出R，返回。35例：基本块1.T:=A-B2.U:=A-C3.V:=T+U4.W:=V+U设W是基本块出口之后的活跃变量，只有R0和R1是可用寄存器，生成的目标代码和相应的RVALUE和AVALUE:36中间代码目标代码RVALUEAVALUET:=A－BU:=A－CV:=T＋UW:=V＋ULDR0，ASUBR0，BR0含有TT在R0中LDR1，ASUBR1，CR0含有TR1含有UT在R0中U在R1中ADDR0，R1R0含有VR1含有UV在R0中U在R1中ADDR0，R1R0含有WW在R0中STR0，W37§11.6窥孔优化如果用简单代码产生器依次把一条条中间代码翻译为目标代码，可能会使目标代码中包含冗余的指令或出现不太优的结构。在目标代码这一级上，可以借助一种简单但有效的技术改进代码质量，这就是窥孔优化(peepholeoptimization)38窥孔优化方法是通过考察一小段目标指令(称为窥孔)并把这些指令替换为更短和更快的一级指令，从而提高目标代码的质量。39窥孔是目标程序中的一个可移动的小窗口，窥孔中的代码不一定是相邻的，窥孔优化的一个特点是：优化后新产生的结果可能会给后面的优化提供进一步的机会。40为了得到最大的优化效果，有时需要对目标代码进行若干遍的处理。1.冗余存取(1)STR0,A(2)LDR0,A因为指