第十二章代码生成

第12章代码生成12.1代码生成概述将中间语言转换成特定目标机的机器语言或汇编语言。代码生成要考虑的主要问题：基本块的代码生成：在一个基本块范围内考虑如何充分利用寄存器的问题。具体细节依赖于目标机器的指令系统、硬件配置和操作系统。目标代码的质量：占用空间、执行效率12.1.1

代码生成程序在编译系统中的位置目标代码的三种形式地址代真的机器代码待装配的机器代码模块汇编语言（宏汇编）机器指令形式源程序编译前端代码优化代码生成程序符号表目标程序中间代码中间代码12.1.2设计代码生成程序的基本问题1.代码生成程序的输入中间代码和符号表中的信息语义分析时直接生成代码2.指令选择：指令系统3.寄存器分配：充分利用寄存器4.指令调度：选择计算次序指令选择选择计算机指令系统基本原则(1)减小产生代码的尺寸(2)减小目标代码的执行时间(3)降低目标代码的能耗指令选择对于同一个指令系统，对于同样的中间代码，可以选择不同的指令生成代码序列。例如：x:=y+z，其中x,y,z均为静态变量，代码序列如下：LDR0,yADDR0,zSTR0,x四元式a:=a+1用INCa一条指令即可实现。

充分利用寄存器—提高执行速度，少占用内存，开销小。通用寄存器、浮点寄存器寄存器的使用：分配和指派（1）分配：为程序的某一点选择驻留在寄存器中的一组变量。（2）指派：指定变量将要驻留的寄存器—寄存器赋值。寄存器分配

基本块中和全局的寄存器分配：不把寄存器平均分配给各个变量使用，而是从可用的寄存器中分出几个，固定分配给几个变量单独使用。标准—以各变量在循环内需要访问主存单元的次数为标准。寄存器分配

寄存器分配原则：（1）生成某变量的目标对象值时，尽量让变量的值或计算结果保留在寄存器中，直到寄存器不够分配为止。减少对内存的访问次数。（2）当到基本块出口时，将变量的值存放在内存中。因为一个基本块可能有多个后继或前驱结点，同一变量名在不同前驱结点的基本块内，出口前存放的寄存器可能不同，或没有定值，后继结点中无法使用。寄存器分配

（3）在同一基本块内后边不再被引用的变量所占用的寄存器应尽早释放，以提高寄存器的利用率。使用编号偶奇寄存器对的方法：乘法指令Mx,yx放在偶寄存器，y放在奇寄存器，积占据整个寄存器对。除法指令Dx,y被除数x占据一个偶奇寄存器对，y是单个寄存器，完成时，偶寄存器保存余数，奇寄存器保存商。寄存器分配寄存器分配(b)t:=a+bt:=t*ct:=t/dLDR0,aADDR0,bADDR0,cSRDAR0,32DIVR0,dSTR1,t(a)t:=a+bt:=t*ct:=t/dLDR1,aADDR1,bMULR0,cDIVR0,dSTR1,t最优的机器指令序列两个三地址代码序列指令调度确定程序指令的执行顺序实现(a+b)+c的优化与否的两个指令序列LDR1,aLDR1,aLDR2,bLDR2,bNOPLDR3,cADDIR1,R1,R2ADDIR1,R1,R2LDR2,c

ADDIR1,R1,R3

NOPADDIR1,R1,R2T4:=A+B-(E-(C+D))T1:=A+BMOVA,R0T2:=C+DADDB,R0T3:=E-T2MOVC,R1T4:=T1-T3ADDD,R1MOVR0,T1MOVE,R0SUBR1,R0MOVT1,R1SUBR0,R1MOVR1,T4对于同一表达式的不同顺序的四元式序列的目标代码序列T4:=A+B-(E-(C+D))T2:=C+DMOVC,R0T3:=E-T2ADDD,R0T1:=A+BMOVE,R1T4:=T1-T3SUBR0,R1MOVA,R0ADDB,R0SUBR1,R0MOVR0,T4对于同一表达式的不同顺序的四元式序列的目标代码序列12.2一个简单的代码生成程序以四元式的中间代码为输入，将其转换成给定的M计算机的目标代码在一个基本块内如何充分利用寄存器以提高目标代码的运行效率。寄存器分配的一般算法12.2.1计算机模型M计算机，具有n+1个寄存器R0~Rn作为累加器和/或变址器‘op’表示运算符，‘M’表示内存单元，变量名表示变量所在单元，‘C’表示常量，‘*’表示间址方式存取。指令包含四种类型：直接地址型、寄存器型、变址型、间址型模型计算机的指令若op是一目运算符，则“opRi，M”的意义为：op(M)⇒Ri，op为二目运算符时如下：类型指令形式意义直接地址型寄存器型变址型间接型opRi,MopRi,RjopRi,c(Rj)opRi,*MopRi,*RjopRi,*c(Rj)(Ri)op(M)⇒Ri(Ri)op(Rj)⇒Ri(Ri)op((Rj)+c)⇒Ri

(Ri)op((M))⇒Ri(Ri)op((Rj))⇒Ri(Ri)op(((Rj)+c))⇒Ri12.2.2待用信息链表法尽可能地让该变量的值保留在寄存器中尽可能引用变量在寄存器中的值释放基本块内不再引用的变量所占的寄存器可从基本块的出口由后向前扫描，对每个变量建立相应的待用信息链和活跃变量信息链。假定基本块中的变量在出口处都是活跃的。待用信息若在一个基本块中：

变量A在四元式i中被定值在i后面的四元式j中要引用A值且从i到j之间没有其它对A的定值点，这时我们称j是四元式i中对变量A的待用信息或称下次引用信息同时也称A是活跃的若A被多次引用则可构成待用信息链与活跃信息链计算待用信息的算法符号表中增加“待用信息”栏和“活跃信息”栏(1)对各基本块的符号表中的“待用信息”栏和“活跃信息”栏置初值，即把“待用信息”栏置“非待用”。对“活跃信息”栏按在基本块出口处是否为活跃而置成“活跃”或“非活跃”。这里假定变量都是活跃的，临时变量都是非活跃的。计算待用信息的算法(2)从基本块出口到基本块入口由后向前依次处理每个四元式。对每个四元式i:A:=BopC，依次执行下述步骤：a)把符号表中变量A的待用信息和活跃信息附加到四元式上。计算待用信息的算法b)把符号表中变量A的待用信息栏和活跃信息栏分别置为“非待用”和“非活跃”。由于在i中对A的定值只能在i以后的四元式才能引用，因而对i以前的四元式来说A是不活跃也不可能是待用的。计算待用信息的算法c)把符号表中变量B和C的待用信息和活跃信息附加到四元式i上。d)把符号表中变量B和C的待用信息栏置为“i”，活跃信息栏置为“活跃”。注意，以上a)和b)，c)和d)的次序不能颠倒。待用信息的例例：若用A，B，C，D表示变量，用T，U，V表示中间变量，有四元式如下：(1)

T:=A-B(2)

U:=A-C(3)

V:=T+U(4)

D:=V+U其名字表中的待用信息和活跃信息如下表，用“F”表示“非待用”“非活跃”，用“L”表示活跃。(1)(2)(3)(4)表示四元式序号。待用信息和活跃信息链待用信息链表中“待用信息链”与“活跃信息链”的每列从左至右为每从后向前扫描一个四元式时相应变量的信息变化情况，空白处为没变化。待用信息和活跃信息在四元式上的标记如下所示：(1)T(3)L:=A(2)L-BFL(2)U(3)L:=AFL-CFL(3)V(4)L:=TFF+U(4)L(4)DFL:=VFF+UFF12.2.3代码生成算法寄存器描述和地址描述为随时掌握各寄存器的使用情况用寄存器描述数组RVALUE：描述每个寄存器当前的状况，为空闲状态还是被某几个变量占用，用寄存器Ri的编号值作为下标，数组元素值为变量名。变量地址描述数组AVALUE：表示变量的存放情况，在寄存器中还是在内存中。

代码生成算法相应的表示如下：RVALUE[Ri]={A,C}表示寄存器Ri的现行值是变量A，C的值AVALUE[A]={A}表示A的值在内存中AVALUE[A]={Ri,A}表示A的值即在Ri中又在内存中AVALUE[A]={Ri}表示A的值即在Ri中基本块的代码生成算法设GETREG是一个函数过程，参数是形如i:A:=BopC的四元式对每个四元式，调用过程：getreg(i:A:=BopC)，返回一个寄存器R，存放A的结果值；对如何分配寄存器R，要用到四元式i上的待用信息。GETREG分配寄存器的算法如果B的现行值在某个寄存器Ri中，且该寄存器只包含B的值，或者B与A是同一标识符，或B在该四元式后不再被引用，则可选取Ri为所需的寄存器R。如果有尚未分配的寄存器，则从中选用一个Ri为所需的寄存器R。GETREG分配寄存器的算法从已分配的寄存器中选取一个Ri作为所需的寄存器R，其选择原则为：占用该寄存器的变量值同时在内存中，或在基本块中引用的位置最远，这样对寄存器Ri所含的变量和变量在内存中的情况必须做如下调整：即对RVALUE[Ri]中的每一变量M，如果M不是A且AVALUE[M]不包含M，则：GETREG分配寄存器的算法生成目标代码STRi，M；把不是A的变量值有送入内存。如果M不是B，则另AVALUE[M]={M}，否则，令AVALUE[M]={M，Ri}。删除RVALUE[Ri]中的M。分配寄存器后，进行代码生成，然后修改寄存器的使用信息和地址描述信息。基本块的代码生成算法1.分配操作寄存器getreg(i:A:=BopC)2.利用AVALUE[B]和AVALUE[C]，确定出B和C现行值存放位置B’和C’，如果其现行值在寄存器中，则把寄存器取作B’和C’；B’:=AVALUE[B]C’:=AVALUE[C]基本块的代码生成算法如B`≠R，则生成目标代码LDR,B’opR,C’否则，生成目标代码opR，C’如B’=Ri或C’=Ri，确定B和C占有寄存器Ri，并在四元式i后不再是活跃的，则删除AVALUE[B]或AVALUE[