第12章-代码生成

武汉理工大学计算机科学系林泓第十二章代码生成•12.1代码生成概述•12.2一个简单的代码生成程序•12.3几种常用的代码生成程序的开发方法•12.4全局寄存器分配•12.5代码生成程序的自动化构造武汉理工大学计算机科学系林泓12.1代码生成概述12.1.1目标代码的三种形式:•能够立即执行的机器语言代码，所有地址均已定位；•待装配的机器代码模块，当需要执行时，由连接装入程序把它们和某些运行程序连接起来，转换成能执行的机器语言代码；•汇编语言代码，需经过汇编程序汇编，转换成可立即执行的机器语言代码。武汉理工大学计算机科学系林泓12.1.2代码生成要考虑的主要问题——具体细节依赖于目标机器和操作系统(1)代码生成程序的输入线性表示、三地址表示、图形表示(2)计算机指令的选择x:=y+zLDR0,yADDR0,zSTR0,xa:=a+1INCa(3)充分利用寄存器(寄存器分配)(4)选择计算次序(指令调度)武汉理工大学计算机科学系林泓12.2简单的代码生成程序12.2.1计算机模型机器指令形式指令意义opRi,M(Ri)op(M)=RiopRi,Rj(Ri)op(Rj)=RiopRi,c(Rj)(Ri)op((Rj)+c)=RiopRi,*M(Ri)op((M))=RiopRi,*Rj(Ri)op((Rj))=RiopRi,c*(Rj)(Ri)op(((Rj)+c))=Ri机器指令开销(cost)opR,M开销2opRi,Rj开销1opRi,*M开销3武汉理工大学计算机科学系林泓目标机器的地址方式地址方式汇编形式地址增加的开销直接地址方式MM1寄存器方式RR0间接寄存器方式*Rcontents(R)0索引方式c(R)c+contents(R)1间接索引方式*c(R)contents(c+contents(R))1武汉理工大学计算机科学系林泓12.2.2待用信息链法在一个基本块范围内考虑如何充分利用寄存器的问题：l尽可能地让该变量的值保留在寄存器中l尽可能引用变量在寄存器中的值待用信息：若在一个基本块中，变量A在四元式i中被定值，在i后面的四元式j中要引用A值，且从i到j之间没有其它对A的定值点，这时我们称j是四元式i中对变量A的待用信息或称下次引用信息，同时也称A是活跃的，若A被多次引用则可构成待用信息链与活跃信息链。可从基本块的出口由后向前扫描，对每个变量建立相应的待用信息链和活跃变量信息链。武汉理工大学计算机科学系林泓计算待用信息的算法：（1）符号表中增加“待用信息”栏和“活跃信息”栏:对各基本块的符号表中的“待用信息”栏和“活跃信息”栏置初值，即把“待用信息”栏置“非待用”，对“活跃信息”栏按在基本块出口处是否为活跃而置成“活跃”或“非活跃”。这里假定变量都是活跃的，临时变量都是非活跃的。武汉理工大学计算机科学系林泓（2）从基本块出口到基本块入口由后向前依次处理每个四元式。对每个四元式i:A:=BopC，依次执行下述步骤：a）把符号表中变量A的待用信息和活跃信息附加到四元式i上。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)表示四元式序号。武汉理工大学计算机科学系林泓待用信息和活跃信息待用信息活跃信息变量名初值待用信息链初值活跃信息链AF(2)(1)LLLBF(1)LLCF(2)LLDFFLFTF(3)FFLFUF(4)(3)FFLLFVF(4)FFLF表中“待用信息链”与“活跃信息链”的每列从左至右为每从后向前扫描一个四元式时相应变量的信息变化情况，空白处为没变化。待用信息和活跃信息在四元式上的标记如下所示：(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+UFF武汉理工大学计算机科学系林泓12.2.3代码生成算法基本块的代码生成算法假设只有A:=BopC的四元式序列A．对每个四元式i:A:=BopC，依次执行下述步骤：(1)以四元式i:A:=BopC为参数，调用过程getreg(i:A:=BopC)。从getreg返回时，得到一寄存器R，用它作存放A现行值的寄存器；(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[B]={R}，并令RVALUE[R]={A}，以表示变量A的现行值只在R中并且R中的值只代表A的现行值；（5）如B或C的现行值在基本块中不再被引用，它们也不是基本块出口之后的活跃变量（由四元式i上的附加信息知道），并且其现行值在某个寄存器Rk中，则删除RVALUE[Rk]中的B或C以及AVALUE[B]或AVALUE[C]中的Rk，使该寄存器不再为B或C所占用。B．处理完基本块中所有四元式之后，对现行值在某寄存器R中的每个变量M，若它在出口之后使活跃的，则生成STR，M，放到主存中。武汉理工大学计算机科学系林泓其中假定d在基本块的出口是活跃的。uvdutvcaubatcacabad+=+=-=-=-+-+-=::::)()()(:源代码：武汉理工大学计算机科学系林泓代码序列语句生成的代码寄存器描述器地址描述器t:=a－bLDR0,aSUBR0,b空寄存器R0包含tt在R0中u:=a－cLDR1,aSUBR1,cR0包含tR1包含ut在R0中u在R1中v:=t＋uADDR0,R1R0包含vR1包含uu在R1中v在R0中d:=v＋uADDR1,R0STRR0,dR0包含dd在R0中d在R0中和存储器中武汉理工大学计算机科学系林泓例：赋值语句T4:=A+B-(E-(C+D))四元式序列GT1：=A+BT2：=C+DT3：=E-T2T4：=T1-T3DAG：ABECDn9n3n8n1n2n7n6n4n5T4T1T3T2+--+从DAG生成目标代码武汉理工大学计算机科学系林泓T4:=A+B-(E-(C+D))T1:=A+BMOVA,R0T2:=C+DADDB,R0T3:=E-T2MOVC,R1T4:=T1-T3ADDD,R1MOVR0,T1MOVE,R0SUBR1,R0MOVT1,R1SUBR0,R1MOVR1,T4武汉理工大学计算机科学系林泓T2:=C+DMOVC,R0T3:=E-T2ADDD,R0T1:=A+BMOVE,R1T4:=T1-T3SUBR0,R1MOVA,R0ADDB,R0SUBR1,R0MOVR0,T4原因：T4的计算紧跟在T1之后武汉理工大学计算机科学系林泓尽可能使一个结点的求值紧接着它的最左变量的求值之后启发式排序算法(1)while存在未列入表的内部结点do(2)begin选取一个未列入表的但其全部父结点均已列入表的结点n;(3)将n列入表中;(4)whilen的最左子结点m不是叶结点并且其所有父结点均已列入表中do(5)begin将m列入表中;(6)n:=m(7)end(8)end武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓3t2t:1t4t6t:2te4t:3t8t5t:4tc6t:5tba:6ted:8t*=+=-=*=-=+=+=武汉理工大学计算机科学系林泓基于树重写的代码生成例:a[i]:=b+1:=ind+Membconst1ind+constiregspconstaregsp++武汉理工大学计算机科学系林泓regi+{ADDRj,Ri}regiregj武汉理工大学计算机科学系林泓(1)regiconstc{MOV#c,Ri}(2)regimema{MOVa,Ri}(3)mem{MOVRi,a}(4)mem{MOVRj,*Ri}(5)regi{MOVc(Rj),Ri}:=memaregi:=memaregjindconstcregjregi+武汉理工大学计算机科学系林泓(6)regi{ADDc(Rj),Ri}(7)regi{ADDRj,Ri}(8)regi{INCRi}+regiindconstcregj++regicost1+regiregj武汉理工大学计算机科学系林泓:=ind+Membconst1ind+constiregSPreg0+(1)Reg0consta{MOV#a,R0}(7)reg0{ADDSP,R0}+reg0regSP武汉理工大学计算机科学系林泓indconstiregSP++reg0indconstiregSP+:=indreg0+membconst1武汉理工大学计算机科学系林泓MOV#a,R0ADDSP,R0ADDi(SP),R0MOVb,R1INCR1MOVR1,*R0+reg1const1:=indreg1reg0武汉理工大学计算机科学系林泓12.3常用的代码生成程序的开发方法•解释性代码生成法•模式匹配代码生成法•表驱动代码生成法