编译原理(清华)第十二章代码生成

第12章代码生成学习目标掌握：基本块代码生成算法，寄存器分配算法理解：待用信息，活跃信息12.1代码生成概述12.2一个计算机模型12.3一个简单的代码生成器12.1代码生成概述代码生成的任务把中间代码（经过优化或未经过优化）作为输入，将其转换成特定机器的机器语言或汇编语言作为输出，这样的转换程序称为代码生成器(CodeGenerator)。目标代码生成需要考虑的基本问题：如何使生成的目标代码较短如何充分利用计算机的寄存器，减少目标代码访问存储单元的次数目标代码生成的一些共同的问题，而不讨论某个特定机器的代码生成问题寄存器分配算法目标代码的执行效率很大程度依赖于寄存器的使用；基本块的代码生成算法寄存器分配算法仅限定在一个基本块的范围内，以四元式的中间代码作为输入，以一个称作M的模型机的汇编语言作为输出。12.2一个计算机模型M模型机具有n个通用寄存器R1,R2,R3,…,Rn，它们既可以作为累加器，又可以作为变址器。约定：op表示运算，C表示常量；M表示内存单元（用变量名表示该变量所在的单元），Ri表示寄存器；*表示间接寻址寻址类型指令格式意义（设op是二目算符）直接型opRi,M(Ri)op(M)=Ri寄存器型opRi,Rj(Ri)op(Rj)=Ri变址型opRi,c(Rj)(Ri)op((Rj)+c)=Ri间接型opRi,*M(Ri)op((M))=RiopRi,*Rj(Ri)op((Rj))=RiopRi,*c(Rj)(Ri)op(((Rj)+c))=Ri1.指令系统与寻址方式令X代表Ri或者M，则(X)表示直接取X的内容作为操作对象，((X))表示一层间接，即取X的内容作为地址2.特殊指令除了上述的寻址方式和一般的运算指令之外，计算机模型的指令系统中还包括如下特殊指令主要有两大类：内存与寄存器交换类：包括LD与ST；比较与转移类：如CMP与JX等于零转X单元JzX将A单元与B单元的值进行比较，把结果置入状态字(CT)CMPA,B不为零转X单元JnzX无条件转向X单元JX等于转X单元J=X把寄存器Ri的内容存回存储单元B，即(Ri)=BSTRi,B小于转X单元JX把存储单元B的内容装入寄存器Ri，即(B)=RiLDRi,B意义指令意义指令例：条件语句ifABgotoX中间代码：（J,A,B,X）目标代码：CMPA,BJX12.3一个简单的代码生成器一个基于基本块的代码生成器它的输入是四元式中间代码，输出是M机器的汇编代码着重讨论在基本块内如何充分利用寄存器12.3.1寄存器分配原则在指令的执行代价中，寄存器的代价是最小的，因此总是希望将尽可能多的运算对象放在寄存器中；由于任何一个计算机模型中的寄存器个数都是有限的，因而需要根据一些原则，对寄存器进行分配基于基本块的寄存器分配的一般原则：当生成某变量的目标代码时，尽量让变量的值或中间结果保留在寄存器中，直到寄存器不够分配为止，这样引用变量值时可减少对内存的存取次数，提高运行速度进入基本块时所有寄存器是空闲的，当到基本块出口时，将变量的有用值存回内存，释放所有寄存器在基本块内，后边不再被引用的变量占用的寄存器应尽早释放，以提高寄存器的利用效率12.3.2待用信息链表法1.引入原因：为了把在基本块内还要被引用的变量值尽可能保存在寄存器中，不再被引用的变量所占的寄存器尽早释放，在翻译四元式i:A:=BopC时，必须知道变量A，B，C在基本块内其后的引用情况，即所谓变量的待用信息。2.基本定义：定值、引用、活跃在形如i:A:=B+C的代码中，出现在“:=”左边和右边的变量，分别被称为对变量的定值和引用，i被称为变量的定值点或引用点。若变量的值在i之后的代码序列中被引用，则称变量在i点是活跃的。待用信息在基本块中，变量A在四元式i中被定值，在i后面的四元式j中引用A值，且从i到j之间没有其他对A的定值点，称j是i中对变量A的待用信息（下次引用信息）。所有这样的待用信息jk（k=1,2,…）构成待用信息链。只在基本块内考虑待用信息，一个变量在基本块的后继中是否被引用，可从活跃变量信息得知（出基本块后，变量是否活跃需要进行全局的数据流分析才能确定）在基本块B2内：R在(3)处定值，在(4)处被引用，所以(4)是(3)中R的待用信息流程B3-B2：X在(5)处被定值，在(3)处被引用，所以X在(5)处是活跃的(1)readX(2)readY(3)R:=XmodY(4)ifR=0goto(8)(5)X:=Y(6)Y:=R(7)goto(3)(8)writeY(9)haltB1B2B3B43.基本块内求待用信息的算法假设符号表中含有变量的待用信息和活跃信息栏；四元式表上也有关于结果变量、左右操作数变量的待用和活跃信息栏。1)把基本块中各变量在符号表的登记项中的待用信息栏置为“非待用”，活跃信息栏按变量在基本块出口是否活跃而置为“活跃”或“非活跃”（假定用户变量都是活跃的，临时变量都是非活跃的）。2)从基本块出口的四元式开始由后向前依次处理各个四元式i:A:=BopC，直到处理完为止：i.把符号表中结果变量A的待用信息和活跃信息附加到四元式i上。ii.把符号表中变量A的待用信息栏和活跃信息栏分别置为“非待用”和“非活跃”。（由于在i中对A的定值只能在i以后引用，而对i以前的四元式来说A是非活跃和非待用的。）iii.把符号表中变量B和C的待用信息和活跃信息附加到四元式i上。iv.把符号表中变量B和C的待用信息栏置为“i”，活跃信息栏置为“活跃”。注意：i，ii，iii，iv的次序不能颠倒，因为B和C也可能是A求待用信息的实例有如下基本块(1)T:=A-B(2)U:=A-C(3)V:=T+U(4)D:=V+UA,B,C,D是用户变量（在基本块出口活跃）T,U,V是临时变量（在基本块出口不活跃）用“F”表示“非待用”“非活跃”，“L”表示“活跃”则该基本块的待用信息及活跃信息的计算结果如下：(F,F)(F,F)(F,L)D:=V+U4(4,L)(F,F)(4,L)V:=T+U3(F,L)(F,L)(3,L)U:=A-C2(F,L)(2,L)(3,L)T:=A-B1右操作数左操作数结果四元式序号附加在四元式上的待用及活跃信息符号表中的待用及活跃信息(F,F)(1,L)(1,L)(1)(F,F)(4,L)V(F,F)(3,L)(4,L)U(3,L)T(F,F)D(2,L)CB(2,L)(F,F)(F,F)(F,F)(F,L)(F,L)(F,L)(F,L)A(2)(3)(4)初值变量名12.3.3代码生成算法1.寄存器描述数组RVALUE为了掌握各寄存器的使用情况，用数组RVALUE记录每个寄存器的当前情况：RVALUE[Ri]={A}表示Ri的现行值是变量A的值，或说A独占Ri。RVALUE[Rj]={}表示Rj是空闲的。RVALUE[Rk]={B,C}表示Rk的现行值是变量B和C的值，或说B,C共占Rk。在复写（B:＝C）时存在多个变量共占一个寄存器。2.变量地址描述数组AVALUE生成目标代码要用到变量的地址，它可能是某寄存器Ri，也可能是内存单元（仍用变量名表示）。若变量值同时在寄存器Ri和内存，则取Ri为其地址。AVALUE[A]={Ri}表示变量A的值在Ri中，不在内存。AVALUE[B]={Rj,B}表示变量B的值在Rj中，又在内存。AVALUE[C]={C}表示变量C的值只在内存。3.寄存器分配函数GETREG以形如i:A:＝BopC的四元式为输入，返回一个寄存器R，用以存放A的结果值其算法为：1)如果B独占Ri，且B与A是同一标识符或B值不再引用，则选Ri为R并转（4）2)如果有空闲Ri，则选Ri为R并转（4）。3)释放一个Ri作为R，最好占用Ri的变量值同时在主存中，或在基本块中引用的位置最远。对Ri中不是A(结果变量)的变量M，且其值不在内存，则做如下处理：i.生成目标代码STRi,M，把变量M的值送入内存ii.修改变量地址描述：如M不是B（左操作数）则AVALUE[M]＝{M}，否则AVALUE[M]＝{Ri，M}。iii.修改寄存器描述：删除RVALUE{Ri}中的M。4)给出R，返回通过GETREG（i:A:=BopC）返回的寄存器R用于进行BopC的运算，并把结果（A值）保存在R中。4.基本块的代码生成算法开始时所有寄存器都空闲，顺序取出四元式i:A:＝BopC，按下述算法生成目标代码。到达基本块出口时，若有活跃变量占用寄存器且其值不在内存，则生成存数指令保存其值并释放寄存器。1)分配寄存器R=GETREG(i:A:=BopC)2)利用地址描述数组AVALUE[B]和AVALUE[C],确定出B和C现行值的存放位置B’和C’。如果其现行值在寄存器中，则把寄存器取作B’和C’3)如果B’≠R则生成目标代码LDR,B’;opR,C’否则生成opR,C’，如果B’或C’为R，则删除AVALUE[B]或AVALUE[C]中的R。4)令AVALUE[A]={R}，RVALUE[R]={A}。5)如果B和C的现行值是“非引用”和“非活跃”，且其值在某个Rk中，则删除RVALUE[Rk]中的B或C，删除AVALUE[B]和AVALUE[C]中的Rk。例：假设只有R1和R2两个寄存器利用基本块代码生成算法生成目标代码STR1,DD在R1中R1含有DADDR1,R2V独占的R1(4)D:=V+UV在R1中U在R2中R1含有VR2含有UADDR1,R2T独占的R1(3)V:=T+UT在R1中U在R2中R1含有TR2含有ULDR2,ASUBR2,C空闲的R2(2)U:=A-CT在R1中R1含有TLDR1,ASUBR1,B空闲的R1(1)T:=A-BAVALUERVALUE目标代码选取R四元式在基本块出口出，D占用R1，且D值不在内存，因此生成STR1,D指令保存D值，然后释放R1。本章小结以一个假想的机器指令系统为基础，介绍目标代码生成所涉及的共性问题：基本块的代码生成算法寄存器分配算法变量的待用信息和活跃信息