第10讲--目标生成.ppt

第十讲 目标代码生成;源程序; 代码生成器的输入包括中间代码和符号表中的信息，输出的目标代码一般有以下三种形式： （1）能独立执行的机器语言代码，所有地址均已定位。 （2）待装配的机器语言模块。当需要执行时，由连接装入程序把它们和某些运行程序连接起来，转换成能执行的机器语言代码。 （3）汇编语言代码，尚须经过汇编程序汇编，转换成可执行的机器代码。 ; 代码生成器的设计细节要依赖于目标语言和操作系统，因此必须考虑以下问题: 1.如何使生成的目标代码较短； 2.如何充分利用计算机的寄存器，减少目标代码中访问存储单元的次数； 3.计算顺序的选择； 4.充分利用目标计算机的指令系统的特点。 这些问题都直接影响到生成的代码的质量（速度和大小）。 这里我们不打算针对某台具体机器谈代码生成，只是通过一个抽象的目标机器模型来说明如何生成有效的代码。;§1.抽象机模型; 以上指令中的运算符op包括一般计算机上常见的一些运算符，如ADD,SUB,MUL,DIV等。现将某些指令的意义说明如下：;例： ST R0,M 将寄存器R0的内容存入存储单元M中; ST R0,4(R1) 将R0中的值存入(4+(R1))所指单元; LD R0,*4(R1) 将(4+(R1))之值所指单元的内容装入R0中; LD R0,#1 将常数1装入寄存器R0中；;§2.简单代码生成器; 我们知道，任何一台计算机的通用寄存器个数是有限的，不可能、也没必要给每个变量固定地分配一个寄存器。也就是说，对于在基本块内不再使用的变量所占用的寄存器要及时释放，这样一来，每当翻译一条中间代码A:=B op C时，必须预先知道A,B,C是否还会在该基本块中被引用，以及要引用到哪些中间代码为止。为此，我们引入以下术语： ; 一、待用信息 在一个基本块中，若四元式i对A定值，四元式j要引用A的值，而从i到j之间再没有A的其他定值，那么，我们称四元式j为i的关于变量A的待用信息。 注意：这里我们仅对基本块内考虑待用信息，一个变量在基本块的后继中是否被引用，可从活跃变量信息得知。 为了取得每个变量在基本块内的待用信息，可从基本块的出口由后向前扫描，对每个变量建立相应的待用信息链和活跃变量信息链。 ; 如果不进行数据流分析，我们可以认为所有临时变量都不能跨基本块引用，于是基本块中的所有临时变量均认为是基本块出口之后非活跃的，而所有非临时变量均认为是基本块出口之后的活跃变量。 同时在符号表中增加“待用信息”栏和“活跃信息”栏， 于是可按如下方法计算变量的待用信息：;算法步骤： (1)开始时从基本块入口依次扫描四元式，把基本块中各变量的符号表登记项中的待用信息栏填为“非待用”，并根据该变量在基本块出口之后是不是活跃的，把其中的活跃信息栏填为“活跃”或“非活跃”。 (2)从基本块出口到基本块入口由后向前依次处理每个四元式，对i: A:=B op C执行： ①把符号表中变量A的待用信息和活跃信息附加到中间代码i上； ②把符号表中A的待用信息和活跃信息分别置为“非待用”和“非活跃”；（因为在i中对A的定值只能在i以后的四元式中引用，所以对在i之前的四元式来说，A是不活跃也不待用的。）; ③把符号表中变量B和C的待用信息和活跃信息附加到中间代码i上； ④把符号表中B和C的待用信息置为i，活跃信息置为“活跃”。 上述步骤执行过后，通过符号表和附加在各个四元式上的待用信息就建立起一个链，该链指出了某个变量在基本块内的各个引用位置。 要注意的是，上面的各步骤次序不能颠倒，因为B和C也可能是A。如果四元式为A:=op B或A:=B，这些步骤也是一样的，只是不涉及到C而已。;14;15; 二、寄存器描述和地址描述 1.寄存器描述：建立一个编译用的寄存器描述数组RVALUE，它动态地记录着各寄存器的使用情况：空闲，还是分配给某个变量或某几个变量。 2.地址描述：建立一个变量地址描述数组AVALUE，它动态地记录各变量现行值的存放位置：是在某寄存器中，还是在某个主存单元中，或者即在寄存器中又在主存中。 有了以上的准备工作后，我们就可以着手进行一个基本块的代码生成了。; 三、基本块的代码生成算法 为简单起见，只考虑形如A:=B op C的四元式序列。对每个四元式i: A:=B op C，依次执行下述步骤： 1.以四元式i: A:=B