第9章目标代码生成

1、第9章目标代码生成,源程序,编译前端,中间,代码,代码优化,中间,代码,代码生成器,目标程序,符号表,代码生成器的位置,代码生成器的输入包括中间代码和符号表中的信息。目标代码一般有以下三种形式：（1）能独立执行的机器语言代码，所有地址均以定位（代真）。（2）待装配的机器语言模块。当需要执行时，由连接装入程序把它们和某些运行程序连接起来，转换成能执行的机器语言代码。（3）汇编语言代码，尚须经过汇编程序汇编，转换成可执行的机器代码。代码生成器着重考虑两个问题:一是如何使生成的目标代码较短；另一个是如何充分利用计算机的寄存器，减少目标代码中访问存储单元的次数。这两个问题直接影响代码的执行速度。,基本

2、问题:所有代码生成器都要面对何种中间代码输入,（是逆波兰式，四元式，还是三元式？等问题）何种代码做为目标程序,选择适当的代码指令,最优的寄存器分配方案,和计算顺序等基本问提.为此本书见立了目标机器模型:并把中间代码对应的目标代码做了规定.利用待用信息,寄存器描述数组RVALUE,变量地址描述数组AVALUE等概念建立了代码生成算法.寄存器分配：利用执行代价的概念说明如何建立更佳的寄存器分配方案。,目标代码生成的有关问题,目标机器语言的确定：确定目标代码的形式，目标机，和目标语言。也可以使用一些中间表示方式，比如三元式，四元式等。语言结构目标代码的确定：确定语言中的各类语言结构和目标代码结构之间

3、的对应关系。运行时刻存储管理：程序运行的时刻，需要为变量分配存储空间。在编译时刻可以确定变量所需要的空间，和偏移地址。而实际的地址要等到运行时刻才可以确定。寄存器分配：合理利用寄存器可以使得程序运行效率比较高。求值顺序的选择：代码生成程序的设计：,目标机器,按字节编址，以4个字节为一个字.通用寄存器R0，R1，Rn-1。两地址指令形式：opsource，destination其中op是一个操作码，source和destination称为源和目的，是数据域。例如有如下的操作码：MOV（将源移到目的中）ADD（将源加到目的中）SUB（在目的中减去源）,目标机器的地址方式,contents(a)表示

4、由a所代表的寄存器或存储单元的内容。有关地址方式及它们的汇编语言形式和有关开销如表所示。,指令开销开销是与一条指令的长度（按字计算）相对应的。对绝大多数机器和绝大多数指令而言，用来从存储器中获取一条指令的时间超过了执行该指令的时间。指令开销=源地址开销+目的地址开销+11MOVR0，R112MOVR5，M23ADD#1，R324SUB4（R0），*12（R1）3contents(contents(12contents(R1)contents(4+contents(R0),生成高质量目标机器代码的一些困难。如，a:=bc用不同的指令序列来实现：1MOVb,R0ADDc，R0cost6MOVR0,

5、a2MOVb,aADDc,acost=6假定R0,R1和R2中分别存放了a,b和c的地址：3MOV*R1,*R0ADD*R2,*R0cost2,假定R1和R2中分别包含b和c的值，并且b的值在这个赋值以后不再需要，则我们还有:4ADDR2,R1MOVR1,acost3有效地利用它的地址能力和寄存器。,不考虑代码的执行效率，目标代码生成是不难的，例如：A:=(B+C)*D+E翻译为四元式：T1:=B+CT2:=T1*DT3:=T2+EA:=T3,示例,假设只有一个寄存器可供使用,目标代码：LDR0，BADDR0，CSTR0，T1,假设T1，T2，T3在基本块之后不再引用:LDR0，BADDR0，

6、CMULR0，DADDR0，ESTR0，A,四元式T1:=B+C,T3:=T2+E,T2:=T1*D,A:=T3,LDR0，T1MULR0，DSTR0，T2,LDR0，T2ADDR0，ESTR0，T3,LDR0，T3STR0，A,一个简单的代码生成器充分利用寄存器，即，一方面尽可能地让变量的值保留在寄存器中（即不编出把该变量的值存到内存单元的指令），直到该寄存器必须用来存放别的变量值或者已到达基本块出口为止；另一方面，后续的目标代码尽可能地引用变量在寄存器中的值，而不访问主存。,例如，a：bc（1）Ri中存放了b的值，而Rj中存放了c的值,且b在此语句之后不再活跃。ADDRj，Ri其开销为1，

7、结果在Ri中。（2）b存放在Ri中，而c在一个存储单元里，并假定b不再活跃。ADDc，Ri其开销为2（3）或者MOVc，RjADDRj，Ri其开销为3,寄存器描述器和地址描述器,代码生成算法将使用寄存器描述器和地址描述器来记录寄存器的内容和名字的地址,1寄存器描述器记录每个寄存器的当前内容，每当需要一个新的寄存器时，首先查看此描述器。假定在初始时寄存器描器指示所有的寄存器均为空。当对基本块进行代码生成时，每个寄存器在任一给定时刻将保留零个或多个名字的值。2地址描述器记录在运行时刻的一个名字的当前值存放的一个位置或多个位置。它可能是一个寄存器地址、一个栈地址、一个存储单元地址、或这些地址的一个集

8、合。,代码生成算法对每个形如i：x：yopz下次引用信息依次执行下述步骤：1L：=getreg（i：x:=yopz）L常常是一个寄存器，也可能是一个存储单元，用来存放计算yopz所得的结果。2.考虑y的地址描述器以确定y，y为y的值当前的存放位置。若y的值同时在主存中和一个寄存器中，那么y取寄存器更好。若y的值尚不在L中，则生成指令:MOVy，L,3生成指令opz，L其中z为z的值存放的地址。同样，若z的值同时存放在主存中和一个寄存器中，则取z为寄存器。然后，更新x的地址描述器以记录x在L中。如果L是一个寄存器，则更新这个寄存器描述器以记录该寄存器存有x的值。4如果y和（或）z的当前值没有下次

9、引用，在基本块的出口又是非活跃的，并且是在寄存器中，则更新y的和（或）z的寄存器描述器和地址描述器以表示，在执行i：x：yopz之后，这些寄存器不再包含y和（或）z的值。,一旦处理完一个基本块的所有三地址语句，生成MOVRx,Mx存储那些在基本块的出口处是活跃的并且还不在它的存储单元中的名字x的值。为进行这一工作，使用寄存器描述器来确定哪些名字的当前值仍保留在寄存器中，使用地址描述器来确定其中哪些名字的当前值还不在它的存储单元里，使用活跃变量信息来确定是否需要存储其当前值。,实现函数getreg（i：x：yopz）简单方法:（1）y的值是在一个寄存器中，且该寄存器不保留其它任何名字的值，并且在

10、执行x：yopz以后y为“非活跃”“无下次引用”，那么就返回y的寄存器作为L,并更新y的地址描述器以表示y已不在L;（2）如果（1）失败，则当有空寄存器时,就返回一个这样的寄存器;,（3）如果（2）失败，若x在该基本块中有一个下次引用，或者op是一个需要寄存器的算符，则找一个已被占用的寄存器R。如果R的值尚未在存储单元中，则将R的值存放到一个单元M中，并且更新地址描述器为M。如果R同时保存了几个变量的值，则对每个需要存储的变量值都应生成一条MOV指令。（4）如果x在该基本块中不再被引用，或者没有找到合适的被占用的寄存器，则选择x的存储单元作为L。,例：基本块1.T:=A-B2.U:=A-C3.

11、V:=T+U4.D:=V+U设W是基本块出口之后的活跃变量，只有R0和R1是可用寄存器，生成的目标代码和相应的寄存器描述数组RVALUE和地址描述数组AVALUE:,中间代码目标代码RVALUEAVALUE,T:=AB,U:=AC,V:=TU,D:=VU,LDR0，ASUBR0，B,R0含有T,T在R0中,LDR1，ASUBR1，C,R0含有TR1含有U,T在R0中U在R1中,ADDR0，R1,R0含有VR1含有U,V在R0中U在R1中,ADDR0，R1,R0含有D,D在R0中,STR0，D,本章小结,1.目标代码的形式；2.目标机的指令系统；3.代码生成算法。,再见！,编译原理,第十一章代码

12、生成,词法分析器,语法分析器,中间代码生成器,优化段,表格管理,出错处理,目标代码生成器,代码生成是把语法分析后或优化后的中间代码变换成目标代码。目标代码一般有以下三种形式：能够立即执行的机器语言代码，所有地址已经定位；待装配的机器语言模块。执行时，由连接装配程序把它们和某些运行程序连接起来，转换成能执行的机器语言代码；汇编语言代码。尚须经过汇编程序汇编，转换成可执行的机器语言代码。,代码生成着重考虑的问题：如何使生成的目标代码较短；如何充分利用计算机的寄存器，减少目标代码中访问存贮单元的次数。如何充分利用计算机的指令系统的特点。,11.1基本问题,代码生成器的输入代码生成器的输入包括源程序的

13、中间表示，以及符号表中的信息类型检查,11.1基本问题,目标程序绝对机器代码、可再定位机器语言、汇编语言采用汇编代码作为目标语言指令选择a:=a+1INCaLDR0,aADDR0,#1STR0,a,11.1基本问题,寄存器分配在寄存器分配期间，为程序的某一点选择驻留在寄存器中的一组变量。在随后的寄存器指派阶段，挑出变量将要驻留的具体寄存器。计算顺序选择,11.2目标机器模型,考虑一个抽象的计算机模型具有多个通用寄存器，他们既可以作为累加器，也可以作为变址器。运算必须在某个寄存器中进行。含有四种类型的指令形式,如果op是一目运行符，则“opRi,M”的意义为：op（M）Ri，其余类型可类推。,o

14、p包括一般计算机上常见的一些运算符，如ADD加SUB减MUL乘DIV除,11.3一个简单代码生成器,四元式的中间代码变换成目标代码，并在一个基本块的范围内考虑如何充分利用寄存器：尽可能留：在生成计算某变量值的目标代码时，尽可能让该变量保留在寄存器中。尽可能用：后续的目标代码尽可能引用变量在寄存器中的值，而不访问内存。及时腾空：在离开基本块时，把存在寄存器中的现行的值放到主存中。,11.3.1待用信息,如果在一个基本块内，四元式i对A定值，四元式j要引用A值，而从i到j之间没有A的其他定值，那么，我们称j是四元式i的变量A的待用信息。（即下一个引用点）i:A:=BopCj:D:=AopE假设在变

15、量的符号表登记项中含有记录待用信息和活跃信息的栏。,待用信息和活跃信息的表示：1(x,x)表示变量的待用信息和活跃信息。其中i表示待用信息，y表示活跃，表示非待用和非活跃；2在符号表中，(x，x)(x，x)表示后面的符号对代替前面的符号对；3不特别说明，所有说明变量在基本块出口之后均为非活跃变量。,计算待用信息和活跃信息的算法步骤：1.开始时，把基本块中各变量的符号表登记项中的待用信息栏填为“非待用”，并根据该变量在基本块出口之后是不是活跃的，把其中的活跃信息栏填为“活跃”或“非活跃”；,2.从基本块出口到基本块入口由后向前依次处理各个四元式。对每一个四元式i:A:=BopC，依次执行下面的步

16、骤：1)把符号表中变量A的待用信息和活跃信息附加到四元式i上；2)把符号表中A的待用信息和活跃信息分别置为“非待用”和“非活跃”；3)把符号表中变量B和C的待用信息和活跃信息附加到四元式i上；4)把符号表中B和C的待用信息均置为i，活跃信息均置为“活跃”。,例：基本块1.T:=A-B2.U:=A-C3.V:=T+U4.D:=V+U设W是基本块出口之后的活跃变量。建立待用信息链表与活跃变量信息链表如下：,附加在四元式上的待用/活跃信息表：,(4)D:=V+U,(3)V:=T+U,(2)U:=A-C,(1)T:=A-B,(,y),(,),(,),(4,y),(,),(4,y),(3,y),(,),

17、(,),(3,y),(2,y),(,),序号四元式左值左操作数右操作数,变量名初始状态信息链(待用/活跃信息栏),(3,y),(,),(2,y),(1,y),(1,y),(2,y),(4,y),(,),(3,y),(,),(4,y),(,),寄存器描述数组RVALUE动态记录各寄存器的使用信息RVALUER=A,B变量地址描述数组AVALUE动态记录各变量现行值的存放位置AVALUEA=R1,R2,A,补充说明：因为寄存器的分配是局限于基本块范围之内的，一旦处理完基本块中所有四元式，对现行值在寄存器中的每个变量，如果它在基本块之后是活跃的，则要把它存在寄存器中的值存放到它的主存单元中。要特别强

18、调的是，对形如：A:=B的四元式，如果B的现行值在某寄存器Ri中，则无须生成目标代码，只须在RVALUE(Ri)中增加一个A，(即把Ri同时分配给B和A)，并把AVALUE(A)改为Ri。,代码生成算法：对每个四元式:i:A:=BopC，依次执行：1.以四元式:i:A:=BopC为参数，调用函数过程GETREG(i:A:=BopC)，返回一个寄存器R，用作存放A的寄存器。2.利用AVALUEB和AVALUEC，确定B和C现行值的存放位置B和C。如果其现行值在寄存器中，则把寄存器取作B和C,3.如果BR，则生成目标代码：LDR,BopR,C否则生成目标代码opR,C如果B或C为R，则删除AVALUEB或AVALUEC中的R。4.令AVALUEA=R,RVALUER=A。,5.若B或C的现行值在基本块中不再被引用，也不是基本块出