第10讲-目标生成

第十讲

目标代码生成目标代码的形式抽象机模型简单代码生成器寄存器分配1CompilerPrinciples源程序编译前端中间代码代码优化中间代码代码生成器目标程序符号表

代码生成器的位置编译程序的最后一个阶段的工作是生成目标代码，它以源程序的中间代码作为输入，以等价的目标代码作为输出。2CompilerPrinciples代码生成器的输入包括中间代码和符号表中的信息，输出的目标代码一般有以下三种形式：（1）能独立执行的机器语言代码，所有地址均已定位。（2）待装配的机器语言模块。当需要执行时，由连接装入程序把它们和某些运行程序连接起来，转换成能执行的机器语言代码。（3）汇编语言代码，尚须经过汇编程序汇编，转换成可执行的机器代码。

3CompilerPrinciples代码生成器的设计细节要依赖于目标语言和操作系统，因此必须考虑以下问题:1.如何使生成的目标代码较短；2.如何充分利用计算机的寄存器，减少目标代码中访问存储单元的次数；3.计算顺序的选择；4.充分利用目标计算机的指令系统的特点。这些问题都直接影响到生成的代码的质量（速度和大小）。这里我们不打算针对某台具体机器谈代码生成，只是通过一个抽象的目标机器模型来说明如何生成有效的代码。4CompilerPrinciples§1.抽象机模型我们这儿使用的机器具有多个通用寄存器，它们既可以做累加器，也可作为变址器。这台机器含有如下四种类型的指令：5CompilerPrinciples

以上指令中的运算符op包括一般计算机上常见的一些运算符，如ADD,SUB,MUL,DIV等。现将某些指令的意义说明如下：6CompilerPrinciples例：

STR0,M将寄存器R0的内容存入存储单元M中;STR0,4(R1)将R0中的值存入(4+(R1))所指单元;LDR0,*4(R1)将(4+(R1))之值所指单元的内容装入R0中;LDR0,#1将常数1装入寄存器R0中；7CompilerPrinciples§2.简单代码生成器这儿介绍一个简单代码生成器，它依次将每条中间代码变换成目标代码，并且在一个基本块范围内考虑如何充分利用寄存器的问题。基本思想：在一个基本块内，当生成计算某个变量的值的目标代码时，尽可能地使该值保留在寄存器中——即不编出把该变量的值送主存单元的指令，这样后继的目标代码尽可能地引用变量在寄存器中的值，而减少对主存的访问。而在基本块结束时，因为一个基本块可能有几个后继，而且每个后继亦可能有几个前驱，所以此时应把寄存器中的变量值存到主存单元，以使后继基本块能取到该变量的值。8CompilerPrinciples

我们知道，任何一台计算机的通用寄存器个数是有限的，不可能、也没必要给每个变量固定地分配一个寄存器。也就是说，对于在基本块内不再使用的变量所占用的寄存器要及时释放，这样一来，每当翻译一条中间代码A:=BopC时，必须预先知道A,B,C是否还会在该基本块中被引用，以及要引用到哪些中间代码为止。为此，我们引入以下术语：

9CompilerPrinciples一、待用信息

在一个基本块中，若四元式i对A定值，四元式j要引用A的值，而从i到j之间再没有A的其他定值，那么，我们称四元式j为i的关于变量A的待用信息。

注意：这里我们仅对基本块内考虑待用信息，一个变量在基本块的后继中是否被引用，可从活跃变量信息得知。

为了取得每个变量在基本块内的待用信息，可从基本块的出口由后向前扫描，对每个变量建立相应的待用信息链和活跃变量信息链。10CompilerPrinciples如果不进行数据流分析，我们可以认为所有临时变量都不能跨基本块引用，于是基本块中的所有临时变量均认为是基本块出口之后非活跃的，而所有非临时变量均认为是基本块出口之后的活跃变量。

同时在符号表中增加“待用信息”栏和“活跃信息”栏，于是可按如下方法计算变量的待用信息：11CompilerPrinciples算法步骤：(1)开始时从基本块入口依次扫描四元式，把基本块中各变量的符号表登记项中的待用信息栏填为“非待用”，并根据该变量在基本块出口之后是不是活跃的，把其中的活跃信息栏填为“活跃”或“非活跃”。(2)从基本块出口到基本块入口由后向前依次处理每个四元式，对i:A:=BopC执行：

①把符号表中变量A的待用信息和活跃信息附加到中间代码i上；②把符号表中A的待用信息和活跃信息分别置为“非待用”和“非活跃”；（因为在i中对A的定值只能在i以后的四元式中引用，所以对在i之前的四元式来说，A是不活跃也不待用的。）12CompilerPrinciples③把符号表中变量B和C的待用信息和活跃信息附加到中间代码i上；④把符号表中B和C的待用信息置为i，活跃信息置为“活跃”。上述步骤执行过后，通过符号表和附加在各个四元式上的待用信息就建立起一个链，该链指出了某个变量在基本块内的各个引用位置。要注意的是，上面的各步骤次序不能颠倒，因为B和C也可能是A。如果四元式为A:=opB或A:=B，这些步骤也是一样的，只是不涉及到C而已。13CompilerPrinciples14CompilerPrinciples15CompilerPrinciples二、寄存器描述和地址描述

1.寄存器描述：建立一个编译用的寄存器描述数组RVALUE，它动态地记录着各寄存器的使用情况：空闲，还是分配给某个变量或某几个变量。2.地址描述：建立一个变量地址描述数组AVALUE，它动态地记录各变量现行值的存放位置：是在某寄存器中，还是在某个主存单元中，或者即在寄存器中又在主存中。有了以上的准备工作后，我们就可以着手进行一个基本块的代码生成了。16CompilerPrinciples三、基本块的代码生成算法为简单起见，只考虑形如A:=BopC的四元式序列。对每个四元式i:A:=BopC，依次执行下述步骤：1.以四元式i:A:=BopC为参数，调用过程getreg(i:A:=BopC)。从getreg返回时，得到一寄存器R，用它作存放A现行值的寄存器；2.利用AVALUE[B]和AVALUE[C]，确定出B和C现行值存放位置B´和C´；Getreg()是一个函数过程，详见P316。17CompilerPrinciples3.如B´≠R，则生成目标代码LDR,B´opR,C´否则，生成目标代码opR，C´；如B´或C´为R，则删除AVALUE[B]或AVALUE[C]中的R4.令AVALUE[A]={R}，并令RVALUE[R]={A}，以表示变量A的现行值只在R中并且R中的值只代表A的现行值；5.如B或C的现行值在基本块中不再被引用，它们也不是基本块出口之后的活跃变量（由四元式i上的附加信息知道），并且其现行值在某个寄存器Rk中，则删除RVALUE[Rk]中的B或C以及AVALUE[B]或AVALUE[C]中的Rk，使该寄存器不再为B或C所占用。18CompilerPrinciples例，对于计算D:=(A-B)+(A-C)+(A-C)的四元式：T:=A-BU:=A-CV:=T+UD:=V+U

假设只有R0,R1两个可用寄存器，则生成目标如下：19CompilerPrinciples

在处理完基本块中所有代码后，对现行值只在某个寄存器中的变量M，如果它在基本块出口之后是活跃的，则必须把它存到主存中去，上例中的最后一条指令STR0,D就是如此。以上所谈简单代码生成器的构造中，对寄存器的使用我们已经谈了几个基本原则：每生成一条目标代码时，如果操作数在寄存器则用寄存器作操作数地址，不用的寄存器要尽早释放等。那么，如何才能更有效的使用寄存器呢？下面我们就来讨论一下这个问题。20CompilerPrinciples§3.寄存器分配现在我们将考虑范围从基本块扩大到循环，因为程序中执行次数最多的部分是循环。同时，我们不把寄存器平均分配给各个变量使用，而是从可用的寄存器中化出一部分，固定分配给那些在循环中要访问主存单元的变量。为此，再引入一个新术语：

1.指令的执行代价：每条指令的执行代价=访问主存单元次数+1例：opRi,Rj执行代价为1opRi,M执行代价为2opRi,*Rj执行代价为2opRi,*M执行代价为321CompilerPrinciples于是，我们可以对循环中每个变量计算一下，如果在循环中把某个寄存器固定分配给该变量使用，可以节省多少执行代价。根据计算的结果，就可以把可用的几个寄存器固定分配给节省执行代价最多的变量，从而使这几个寄存器发挥最大作用。下面，我们就介绍计算各变量执行代价的算法。22CompilerPrinciples2.计算节省的变量执行代价：

(1)在原简单代码生成算法中，只有当变量在基本块中被定值时，其值才放在寄存器中，现在把寄存器固定分配某变量使用。因此，当该变量在基本块中被定值前，每引用它一次就可以少访问主存一次，执行代价就节省1。(2)在原代码生成算法中，若某变量在基本块中被定值且在基本块出口之后是活跃的，则出基本块时要把其值由寄存器存储到主存单元；现在把寄存器固定分配该变量使用，就无须再往主存里放了。因此，执行代价节省2。23CompilerPrinciples

对循环L中某变量M，如果分配一个寄存器给它专用，那么每执行循环一次，节省的执行代价为：

ΣB∈L[USE(M,B)+2*LIVE(M,B)]其中：USE(M,B)表示在基本块B中对M定值前引用M的次数，如果M在基本块B中定值并且在B的出口之后是活跃的，则LIVE(M,B)=1，其它情况为0。注意，这儿忽略了几个因素：①如果M在循环入口之前是活跃的，在循环中还要给M分配一个固定寄存器，那么在循环入口处，必须先把M从主存单元中取到寄存器中，其代价为2；如果M在循环出口之后是活跃的，则还要存到主存去，也要花费代价2。这些在公式计算时都略去了。24CompilerPrinciples②在每一次循环中，各个基本块并不一定都能执行到，在上述公式中这种情况也忽略了。

例：下图代表某程序的最内层循环，其中无条件转移和条件转移指令均改用箭头来表示。各基本块入口之前和出口之后的活跃变量已列在图中。假定有三个通用寄存器R0,R1和R2，可以在循环中固定分配给三个变量使用。现在，我们利用上述公式计算各变量的执行代价节省数，然后取执行代价节省数最高的三个变量来分配寄存器。(P319)25CompilerPrinciplesa:=b+cd:=d-be:=a+ff:=a-db:=d+fe:=a-cb:=d+cbcdfacdefacdecdefacdfcdefbcdefbdef是活跃变量bcdef是活跃变量B1B2B3B426CompilerPrinciples解：因为B1中引用a前已对a定值，所以use(a,B1)=0;在B2,B3中a被各引用一次，且在引用前未对a定值，所以use(a,B2)=use(a,B3)=1;B4中未引用a，所以use(a,B4)=0。因为a在B1中被定值且a在B1出口是活跃的，a在B2,B3和B4出口后不是活跃的，所以：live(a,B1)=1live(a,B2)=live(a,B3)=live(a,B4)=0;则代价节省数为：1+1+2*1=4。