编译原理与技术讲义-第10章.ppt

青岛大学信息工程学院,编译原理与技术,第10章 目标代码生成,编译原理与技术,2,主要内容,代码生成器设计的基本问题 虚拟计算机模型 语法制导的目标代码生成 基本块和待用信息 一个简单代码生成器 代码生成技术小结,编译原理与技术,3,10.1 代码生成器设计的基本问题,代码生成在整个编译过程的位置,符号表,代码生成,中间代码生成与优化,语法树,目标程序,中间代码,中间代码,语义分析,中间代码,编译原理与技术,4,10.1 代码生成器设计的基本问题,目标程序 绝对机器代码，程序所有的内存地址，特别是程序的起始地址，在编译时都已经固定。这种代码的优点是装入机器后就可以立即执行，对于小程序可以快速编译和运行。 可重定位机器代码（可重定位目标模块），代码装入内存的起始地址可以任意改变。一组可重定位的若干目标模块，经过连接和装配后才可以运行。尽管这些工作增加了程序运行的代价，但是，可重定位机器代码的优点是灵活性。这种技术允许程序分模块编写，独立地编译成目标模块，并且从目标模块库中调用其它已经编译好的模块，便于程序开发。通常，可重定位机器代码中包含可重定位信息和连接信息。 如果目标代码是汇编语言程序，还需要汇编后才能运行。只要地址可以由偏移址及符号表中的其它信息计算得到，代码生成器就可以产生程序中名字的绝对地址或可重定位地址。这样生成代码的好处是不用生成二进制的机器代码，而是产生符号指令并用宏机制来帮助产生机器代码，使得代码生成过程变得容易。 为了可读性，本章采用汇编语言作为目标语言。,编译原理与技术,5,10.1 代码生成器设计的基本问题,指令选择 一个编译程序可以看成是一个转换系统，它把源程序转换成等价的目标代码，也就是说，对源语言种各种语言结构，依据语义确定相应的目标代码结构，即确定源语言于目标语言之间的对应关系，确保正确实现语义。显然，能否建立这样的关系直接影响到编译程序的质量。 目标机器指令系统的性质决定了指令选择的难以程度，指令系统的一致性和完备性直接影响到这种对应关系的建立。如果目标机器能一致地支持各种数据类型和寻址方式，不需特别处理例外，这种对应关系的建立就容易得多。 指令执行速度和机器特点对产生目标代码的质量也十分重要。显然，如果指令集合丰富的目标机器对于某种操作可提供集中处理的时候，应该选择效率高、执行速度快的一种。,编译原理与技术,6,10.1 代码生成器设计的基本问题,寄存器选择 计算机存储单元之间通常都是通过寄存器联系。寄存器可以保存计算的中间结果，而且运算对象在寄存器的指令一般都比运算对象在内存的指令要短且运算的快。因此，充分合理地利用寄存器对生成高质量的代码十分重要。对于寄存器的使用，应该考虑程序中的哪些变量驻留在寄存器中、驻留多长时间。进一步，哪个变量驻留在哪个寄存器。这些问题可以划分成两个子问题： 在寄存器分配期间，为程序的某一点选择驻留在寄存器中的一组变量； 在随后的寄存器指派阶段，选择变量要驻留的具体寄存器。 选择最优的寄存器指派方案极其困难，从数学以上讲，这是一个NP完全问题。如果考虑到目标机器的硬件、操作系统对寄存器使用的一些要求时，这个问题就变得更加复杂。,编译原理与技术,7,10.1 代码生成器设计的基本问题,计算顺序的选择 计算执行的顺序会影响目标代码的质量。改变运算的执行顺序可以减少需要用来保存中间结果的寄存器的个数，从而提高代码的效率。计算顺序最优选择也是一个非常困难的问题，一个NP完全问题。 本书不讨论求值顺序问题，简单地就按照源程序或中间代码生成的顺序生成目标代码。,编译原理与技术,8,10.2 虚拟计算机模型,作为目标代码生成阶段地址分配的依据 这个目标计算机模型具有n个通用寄存器R0，R1，Rn-1，它们既可以作为累加器，也可以作为变址器。 假设目标机器按字节编址，4个字接组成一个字。我们用op表示运算符，用字母M表示内存单元，用字母C表示常量，用星号*表示间址方式存取。这台机器指令的一般形式为 操作码 op 源数据域，目的数据域 的二地址指令，表示源数据域和目的据域经过op运算以后的结果存到目的数据域。,编译原理与技术,9,10.2 虚拟计算机模型,指令按照地址模式分为四类，见表10.1,如果op是一元运算符，则指令“op M，Ri”的含义为： op (M ) Ri，其余类型可以类推。 上述指令中的运算符（操作码op）包括一般计算机上常见的一些运算符，如加法ADD、减法SUB、负号NEG、乘法MUL、除法DIV、加1 INC、减1 DEC以及逻辑运算AND、NOT、OR等等。,编译原理与技术,10,10.2 虚拟计算机模型,当用作源或目的时，内存单元M和寄存器R都代表自身，例如，指令 MOV R1, M 采用直接地址寻址方式，将寄存器R1的内容存入内存单元M。 MOV 4(R1)，M 采用变址寻址方式，把寄存器R1的偏移4的单元的内容存入内存单元M，即表中(4+R1) M。 表中的间接变址寻址方式用前缀表示。例如，指令 MOV 4(R1)，R2 把地址(4+(R1)中内容所指单元的内容装入寄存器R2中。 常数用前缀#表示，下面的指令采用立即数寻址方式，把常数10装入寄存器R1： MOV #10, R1,编译原理与技术,11,10.3 语法制导的目标代码生成,利用属性文法和语法制导技术，直接产生目标代码。基本原理和技术同第9章介绍的语法制导的中间代码翻译类似，只是产生的目标语言是机器指令。 本节只讨论如何用翻译模式把源程序语言的简单赋值语句和表达式翻译成目标代码，文法如下： S id : = E E E1 + E2 | E1 E2 | E1| ( E1) | id B B1 and B2 | B1 or B2 | not B1| ( B1) | id1 relop id2 | true | false 为了简单起见，这个算术表达式E只有加法、乘法与取负运算，不包含数组、记录等复杂的结构的访问，布尔表达式B只包括了三个逻辑运算符和关系运算符。 文法表达式文法是二义性的，解决文法二义性的原则采用通常意义的优先级和结合性。下面的翻译模式把目标代码写在了文法的属性code中，所使用的函数、变量和属性等与第9章的相同。,编译原理与技术,12,10.3 语法制导的目标代码生成,（1）S id : = E p := lookup(id.name); if p = nil then error else S.code := E.code | gencode( MOV, E.place, p) （2）E E1 + E2 E.place := newtemp; E.code := E1.code | E2.code | gencode (MOV, E1.place, E.place) | gencode (ADD, E2.place, E.place)； （3）E E1 * E2 E.place := newtemp; E.code := E1.code | E2.code | gencode (MOV, E1.place, E.place) | gencode (MUL, E2.place, E.place)；,编译原理与技术,13,10.3 语法制导的目标代码生成,（4）E E1 E.place := newtemp; E.code := E1.code | gencode (MOV, E1.place, E.place)； gencode (NEG, E.place)； （5）E (E1) E.place := E1.place; E.code := E1.code ; （6）E id p := lookup (id.name); if p = nil then error else E.place := p; E.code := ;,编译原理与技术,14,10.3 语法制导的目标代码生成,在下面布尔表达式的翻译中，我们对布尔表达式的求值翻译采用了短路法。其中J| relop.op表示各种条件的转移指令（表10.2）。 （7）B B1 and B2 B1.true := newlabel; B1.false := B.false; B2.true := B.true; B2.false := B.false; B.code := B1.code | gencode (B1.true, :) | B2.code （8）B B1 or B2 B1.true := B.true; B1.false := newlabel; B2.true := B.true; B2.false := B.false; B.code := B1.code | gencode (B1.false, :) | B2.code （9）B B1 B1.true := B.false; B2.false := B.true; B.code := B1.code,编译原理与技术,15,10.3 语法制导的目标代码生成,（10）B (B1) B1.true := B.true; B2.false := B.false; B.code := B1.code ; （11）B id1 relop id2 t := newtemp; B.code := gencode (MOV, id1.place, t) | gencode (CMP, t, id2.place) | gencode (CJ| relop.op, B.true) | gencode (J, B.false) （12）B true gencode (J, B.true) （13）B false gencode (J, B. false),编译原理与技术,16,10.3 语法制导的目标代码生成,例10.1 把布尔表达式ad翻译成目标代码。按照上述翻译模式得到的机器指令如下： MOV a,t1 CMPt2,b CJB.true JB.false 其中B.true和B.false需要应用这个布尔条件的语句确定。,编译原理与技术,17,10.3 语法制导的目标代码生成,本节介绍的翻译技术可以应用在简单语言的编译器中，不适合许多大型实际的程序设计语言。主要原因包括： （1）从语义分析直接生成目标代码有许多局限性，例如，由于目标代码于机器特性紧密相关，不利于代码的移植和优化，更好的策略是先产生某种直接代码，然后再翻译成目标指令序列； （2）在上面的翻译模式中，多处用到了产生临时变量的函数newtemp，没有充分考虑目标机器体系结构中的寄存器以及变量值的使用关系，而且过多的临时变量名还会造成存储分配与寄存器分配的问题。,编译原理与技术,18,10.4 基本块和待用信息,基本块及其构造 对于给定的程序，我们通常把它划分为一系列的基本块，根据程序的控制流把这些基本块连接起来，形成程序流图。在逐步完成各个基本块的代码生成之后，就生成了整个程序的目标代码。 基本块是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句。基本块运行时只能从其入口语句进入，从出口语句退出。 例如，下面的三地址代码组成了一个基本块： t 1 := a * a t2 := a * b t3 := a * t2 t4 := t1 * t3 t5 := t4 + t2,编译原理与技术,19,10.4 基本块和待用信息,算法10.1 划分基本块 输入： 三地址语句序列 输出： 基本块列表，每个三地址语句仅在基本块中。 （1）找出三地址代码中各个基本块的入口语句，它们是： 程序的第一个语句，或者 条件语句活无条件语句的转移目标语句，或者 紧跟在条件语句之后的语句。 （2）对每一个入口语句，它所在的基本块就是由它开始到下一个入口语句之前、或者到一转移语句之前、或到程序结束的所有语句。 凡是未被纳入某一基本块的语句，都是程序控制流无法到达的语句，因而也是不会被执行的语句，可以把它们删除。,编译原理与技术,20,10.4 基本块和待用信息,例 10.2：考虑下面计算长度为20的两个向量的点积的程序段，如图10.2。begin prod := 0; index := ; do begin prod := prod + aindex*bindex; index := index + 1; end while index = 10; end 图10.2 计算点积的程序,在虚拟机器上执行这个计算的三地址代码序列如图10.3。 (1)prod := 0 (2)index := 1 t1 := 4*index /* 字长是4个字节 */ (4)t2 := a t1 /* 计算aindex */ (5)t3 := 4*index (6)t4 := b t1 /* 计算bindex * (7)t5 := t3 * t4 (8)t6 := prod + t5 (9)prod := t6 (10)t7 := index + 1 (11)index := t7 (12)if index = 20 goto (3),编译原理与技术,21,10.4 基本块和待用信息,我们运用算法10.1来决定图10.3的基本块。 按照算法的规则语句（1）是入口语句，按照规则语句（3）是条件转移的目标语句，也是入口语句； 按照规则跟随语句（12）的是入口语句。 所以，语句(1)和(2)组成了一个基本块，以语句(3)开始的程序的其它语句组成了第二个基本块。,在虚拟机器上执行这个计算的三地址代码序列如图10.3。 (1)prod := 0 (2)index := 1 t1 := 4*index /* 字长是4个字节 */ (4)t2 := a t1 /* 计算aindex */ (5)t3 := 4*index (6)t4 := b t1 /* 计算bindex * (7)t5 := t3 * t4 (8)t6 := prod + t5 (9)prod := t6 (10)t7 := index + 1 (11)index := t7 (12)if index = 20 goto (3),编译原理与技术,22,10.4 基本块和待用信息,例 10.3 考虑下面求最大公因子的三地址代码，求出所有基本块。 (1) read X (2) read Y (3) R := X mod Y (4) if R = 0 goto (8) (5) X := Y (6) Y := R (7) goto (3) (8) write Y 按照定义，可以找到四条入口语句（1）、（3）、（5）和（8）。然后，构造的四个基本块如下：,编译原理与技术,23,10.4 基本块和待用信息,流图 把程序控制流的信息增加到基本块的集合，形成一个有向图来表示程序，这样的有向图叫做流图。每个流图以基本块为结点，其中包含了程序第一条语句的基本块称为起始结点。如果在程序的某个执行序列中，基本块Bj紧跟在基本块Bi之后执行，则从Bi到Bj有一条有向边。也就是，若： 有一个条件或无条件转移语句作为Bi的最后一条语句转移到Bj的第一条语句，或者 按照程序的正文序列，Bj紧跟在Bi之后，而且Bi的最后一条语句不是一个无条件转移语句。 那么，块Bi到Bj有一条有向边。我们称Bi是Bj的前驱，Bj是Bi的后继。,编译原理与技术,24,10.4 基本块和待用信息,例10.4 对例10.2中的程序构造的流图如图10.4所示。B1是初始结点，在B2中的最后一个跳转语句改成了跳转到B1。,prod := 0 index := 1,B1,B2,t1 := 4*index t2 := a t1 t3 := 4*index t4 := b t1 t5 := t3 * t4 t6 := prod + t5 prod := t6 t7 := index + 1 index := t7 if index = 20 goto B1,编译原理与技术,25,10.4 基本块和待用信息,例10.5：对例10.3中的程序构造的流图如图10.5所示。,(1) read X (2) read Y,5）X := Y 6）Y := R 7）gogo (3),3) R := X mod Y (4) if R = 0 gogo (8),8）write X,B1,B2,B3,B4,编译原理与技术,26,10.4 基本块和待用信息,待用信息 如果三地址代码i对变量A通过赋值语句定值（即存在一个赋值语句(i) A := E），中间代码j要用A作为运算对象（引用A的值），存在一个控制可以从语句i到j的路径，并且这条路径中没有对A的其它赋值， 那么就称中间代码j引用了A在中间代码i的定值，称中间代码j是中间代码i中对变量A的待用信息或下次引用信息，同时称A在语句i是活跃变量。,编译原理与技术,27,10.4 基本块和待用信息,我们为一个基本块内的每个三地址语句x := a op b中的所有变量确定待用信息。 为了得到一个基本块内每个变量的待用信息和活跃信息，可以从基本块的出口由后向前逐句扫描每条语句对每个变量建立相应的待用信息链和活跃变量信息链。 为了简化处理，我们对于基本块内的变量分为下列两中情况处理： 对没有经过数据流分析（见11.5的介绍）且三地址代码生成的临时变量不允许在基本块外使用，那么就认为这些临时变量在基本块出口处都是不活跃的； 如果某些临时变量可以在本基本块之外引用，则把它们看作基本块之后的活跃变量，同时也把基本块的非临时变量均看作是基本块之后的活跃变量。,编译原理与技术,28,10.4 基本块和待用信息,算法10.2 计算待用信息 输入： 基本块的三地址语句序列 输出： 基本块中所有变量的待用信息和活跃信息 初始化： 把基本块中每个变量在符号表登记项中的待用信息填为“非待用”； 根据每个变量在出口之后是否活跃，在活跃信息栏填上“活跃”或“非活跃”。 从基本块出口语句到入口语句由后向前依次处理每个中间代码。对每个形式为i: A := B op C的代码，以此执行下列步骤： 把符号表中变量A的待用信息和活跃信息附加到中间代码i上； 把符号表中变量A的待用信息栏和活跃信息栏分别设置为“非待用”和“非活跃”；（因为在i中对A的定值只能在i之后才能引用，对i之前的语句而言A既不是活跃的也不可待用） 把符号表中变量B和C的待用信息和活跃信息附加到中间代码i上； 把符号表中变量B和C的待用信息设置为i，活跃信息均设置为“活跃”。,编译原理与技术,29,10.4 基本块和待用信息,例10.6 对于下列基本块，假设变量D在基本块之后活跃，计算所有变量的待用信息。 (1) T := A B (2) U := A C (3) V := TU (4) D := VU 用F表示“非待用”和“非活跃”，用L表示“活跃”，用序号表示待用信息（即下一个引用点），用二元对表示变量的待用信息和活跃信息，其中X取指为F或L，表10.3显示了符号表中待用信息和活跃信息，表10.4显示了中间代码上的待用信息和活跃信息。 对表10.3中的每一个变量，把其二元对从左到右连接起来，就得到了变量的待用信息和活跃信息变化。,编译原理与技术,30,10.4 基本块和待用信息,表10.3 例10.4的符号表中待用和活跃信息,编译原理与技术,31,10.4 基本块和待用信息,表10.4 例10.4的中间代码的待用和活跃信息,编译原理与技术,32,10.5 一个简单代码生成器,本节要介绍一个简单的代码生成器，它依次考虑每条语句以及如何在一个基本块范围内充分利用寄存器的问题，生成目标代码，并根据产生的代码修改寄存器的使用情况。 为了简单起见，假定计算结果尽量常时间地留在寄存器中，只有在下面两种情况下才把它存入内存： （1）如果需要此寄存器用于其它计算； （2）正好在转移或标号语句之前。 条件（2）暗示在基本块的结尾必须把所有的计算结果都保存起来。原因是，离开一个基本块后，可能进入几个不同基本块中的一个，或者进入一个还可以从其它基本块进入的基本块。在这两种情况下，就认为基本块引用的某个数据在入口点一定处在某个寄存器中是不妥的。因此，为了不免可能出先的错误，本节介绍的简单代码生成算法在离开基本块时，存储所有的东西。,编译原理与技术,33,10.5 一个简单代码生成器,通过一个简单的例子来说明要介绍的简单代码生成算法的一些问题。 对三地址语句 a:= b + c，我们可以生成一条简单的指令 ADD Rj, Ri（1） 把结果留在Ri。但是，可以生成这条简单指令的前提是：Rj包含了c，Ri 包含了b，而且它以后不再被引用了。 如果Ri 包含了b，而c在内存中（假设就用c表示内存单元），我们可以产生： ADDc,Ri（2） 或者 MOVc, Rj（3） ADDRj,Ri 同样要求b不再被引用了。 从机器指令执行的时间上讲，使用寄存器比使用内存单元要快。但是，任何机器的寄存器数量优先，而且某些寄存器还有特殊通途，不能作为通用寄存器使用。而且，还要考虑到存入寄存器额名字的值今后是否还要引用。所以，判定翻译模板代码优劣的因素很多、很复杂。但从本例而言，代码（1）的执行速度最快，但是，要求的条件也最多。代码（2）的执行速度由于要访问内存（c的值），比代码（1）慢，但是比（3）要快，而且，代码（1）和（2）都是一条指令，占用较少的内存。然而，如果以后肯定要使用c的值，翻译（3）比（2）更有吸引力，因为c的值已经在一个寄存器Rj中。,编译原理与技术,34,10.5 一个简单代码生成器,寄存器和地址的描述 为了在代码生成的过程中合理地分配寄存器，需要随时掌握每个寄存器的使用情况，了解它是否空闲，还是已经分配给某个或某几个变量。 使用一个数组RVALUE来动态地记录寄存器的这些信息，这个数组称作寄存器描述数组。用寄存器Ri的编号值作为寄存器描述数组的RVALUE下标，数组元素值是一个或多个变量名。 另外，一个变量的值可以存储在寄存器中，也可以存放在内存，或者同时存放在寄存器和内存中。在代码生成过程中，每当生成的指令要涉及到引用某个变量的值时，若它已经在某个寄存器，我们希望直接引用该变量在寄存器中的值，以便提高代代码的执行速度。 使用一个称作变量地址描述数AVALUE来动态地记录每个变量当前值的存放位置，这个数组的下标就用变量名。,编译原理与技术,35,10.5 一个简单代码生成器,寄存器和地址的描述 几个例子：,RVALUER1 = A, B 表示R1存储的是变量A和B的值 AVALUEA =A表示变量A的值只存放在内存中 AVALUEA = R1, A表示变量A的值同时存放在寄存器R1和内存中 AVALUEB = R1表示变量B的值只存放在寄存器R1内,编译原理与技术,36,10.5 一个简单代码生成器,寄存器的分配原则 当生成某变量的目标代码时，尽可能让变量的值或计算结果驻留在寄存器中，除非该寄存器必须用来存放其它变量的值而不得不放弃其中的内容； 达到基本块出口时，将变量的值存放到内存中，以便后续基本块的代码可以继续引用其值； 一个基本块后不再引用的变量所占用的寄存器应该尽早释放出来，以提高寄存器的使用率。 为了在一个基本块内的目标代码中让寄存器得到充分利用，需要把基本块内还要被引用的变量值尽可能地保存在寄存器中，而把基本块内不再被引用的变量所占的寄存器尽早地释放掉。在代码生成的过程中，需要不断地为程序中的变量选择寄存器。,编译原理与技术,37,10.5 一个简单代码生成器,算法10.3 寄存器选择函数GETREG 输入： 中间代码i: A := B op C 输出： 一个用来存放变量A的值的寄存器R for 每个AVALUEB中的Ri do if (RVALUERi= =B) / 把Ri的值存入内存M AVALUEM = AVALUEM Ri if (M != B | ( M= =C j n; j+) / 调用寄存器选择函数GETREG(i: A := B op C)得到一个存放A值的寄存器R； R = getreg (BBj); B = AVALUEB; C = AVALUEC; / 到B和C的存放位置B和C if (B= =R) 生成目标代码op R, C else生成目标代码 MOV B, R op R, C /* 修改寄存器描述数组和地址描述数组，释放B和C所占用的寄存器，使A只在寄存器R且独占寄存器R */ if (B= =R) AVALUEB = AVALUEB R； if (C= =R) AVALUEC = AVALUEC R； AVALUEA = R; RVALUER = A; /* 若B或C不再被引用，就释放B或C占用的每一个寄存器*/ If (B不再被引用) RVALUERi = RVALUERi B; AVALUEB = AVALUEB Ri If (C不再被引用) RVALUERi = RVALUERi C; AVALUEC = AVALUEC Ri ,编译原理与技术,40,10.5 一个简单代码生成器,例10.7 对于例10.6的三地址代码： (1) T := A B (2) U := A C (3) V := TU (4) D := VU,假设只有R0和R1两个可用的寄存器，用算法10.3和10.4生成的目标代码以及相应的寄存器描述和地址描述下表所示。 函数getreg的第一次调用返回寄存器R0来存放计算结果T。因为A不在R0中，所以产生数据移动代码“MOV A, R0”和运算代码“SUB B, R0”，然后修改寄存器和内存地址描述以表示R0包含临时变量T。代码生成以这种方式进行，直到最后一个语句处理完。这时，R1已被释放为空闲，活跃变量D的值通过指令“MOV R0, D”保留在内存当中。,编译原理与技术,41,10.5 一个简单代码生成器,各种三地址语句所对应的机器指令,编译原理与技术,42,10.5 一个简单代码生成器,机器实现条件转移的方式有两种。 根据寄存器的值是否为下面6个条件之一而进行分支：负、零、正、非负、非零和非正。在这样的机器上，象if x y，则CMP x, y把条件码设置为正；若xy，则CMP x, y把条件码设置为负。条件转移指令根据同上面一样放入条件决定向何处转移。指令CJ = z的含义是如果条件为负或者零则转移到地址z。,编译原理与技术,43,10.5 一个简单代码生成器,例10.8: 对于语句 x := y + z if x 0 goto z 可以翻译成下列目标代码 MOVy, R0 ADDz, R0 MOVR0, x CJ z 因为根据内部特征寄存器CT可以知道在ADD z, R0指令之后，它是根据x的的值设置的。,