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

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