《第12章 代码生成ppt课件.ppt》由会员分享，可在线阅读，更多相关《第12章 代码生成ppt课件.ppt（28页珍藏版）》请在三一办公上搜索。
1、第十二章 代码生成,12.1 代码生成概述12.2 一个简单的代码生成程序12.3 几种常用的代码生成程序的开发方法12.4 全局寄存器分配12.5 代码生成程序的自动化构造,12.1 代码生成概述,12.1.1 目标代码的三种形式:能够立即执行的机器语言代码，所有地址均已定位；待装配的机器代码模块，当需要执行时，由连接装入程序把它们和某些运行程序连接起来，转换成能执行的机器语言代码；汇编语言代码，需经过汇编程序汇编，转换成可立即执行的机器语言代码。,12.1.2 代码生成要考虑的主要问题,具体细节依赖于目标机器和操作系统,(1)代码生成程序的输入 线性表示、三地址表示、图形表示(2)计算机指
2、令的选择 x:=y+z LD R0,y ADD R0,z ST R0,x a:=a+1 INC a(3)充分利用寄存器(寄存器分配)(4)选择计算次序(指令调度),12.2 简单的代码生成程序,12.2.1 计算机模型机器指令形式 指令意义op Ri,M(Ri)op(M)=Riop Ri,Rj(Ri)op(Rj)=Riop Ri,c(Rj)(Ri)op(Rj)+c)=Riop Ri,*M(Ri)op(M)=Riop Ri,*Rj(Ri)op(Rj)=Riop Ri,c*(Rj)(Ri)op(Rj)+c)=Ri机器指令开销(cost)op R,M 开销 2op Ri,Rj 开销 1op Ri,*
3、M 开销 3,目标机器的地址方式,12.2.2 待用信息链法,在一个基本块范围内考虑如何充分利用寄存器的问题：,l,尽可能地让该变量的值保留在寄存器中,l,尽可能引用变量在寄存器中的值,待用信息：若在一个基本块中，变量,A,在四元式,i,中被定,值，在,i,后面的四元式,j,中要引用,A,值，且从,i,到,j,之间没有其,它对,A,的定值点，这时我们称,j,是四元式,i,中对变量,A,的待用,信息或称下次引用信息，同时也称,A,是活跃的，若,A,被多次,引用则可构成待用信息链与活跃信息链。,可从基本块的出口由后向前扫描，对每个变量建立相应的待用,信息链和活跃变量信息链。,计算待用信息的算法：,
4、（1）符号表中增加“待用信息”栏和“活跃信息”栏:对各基本块的符号表中的“待用信息”栏和“活跃信息”栏置初值，即把“待用信息”栏置“非待用”，对“活跃信息”栏按在基本块出口处是否为活跃而置成“活跃”或“非活跃”。这里假定变量都是活跃的，临时变量都是非活跃的。,（2）从基本块出口到基本块入口由后向前依次处理每个四元式。对每个四元式i:A:=B op C，依次执行下述步骤：,a,）,把符号表中变量,A,的待用信息和活跃信息附加到四元式,i,上。,b,）,把符号表中变量,A,的待用信息栏和活跃信息栏分别置为,“非待用”和,“非活跃”。,（由于在,i,中对,A,的定值只能,在,i,以后的四元式才能引用
5、，因而对,i,以前的四元式来说,A,是不活跃也不可能是待用的）,c,）,把符号表中变量,B,和,C,的待用信息和活跃信息附加到四元,式,i,上。,d,）,把符号表中变量,B,和,C,的待用信息栏置为,“,i,”，活跃信,息栏置为,“活跃”。,注意，以上,a,）和,b,），,c,）和,d,）的次序不能颠倒。,12.2.3 代码生成算法,基本块的代码生成算法假设只有A:=B op C的四元式序列A 对每个四元式i:A:=B op C，依次执行下述步骤：(1)以四元式i:A:=B op C为参数，调用过程getreg(i:A:=B op C)。从getreg返回时，得到一寄存器R，用它作存放A现行值
6、的寄存器；(2)利用AVALUEB和AVALUEC，确定出B和C现行值存放位置B和C，如果其现行值在寄存器中，则把寄存器取作B和C；,其中假定d在基本块的出口是活跃的。,u,v,d,u,t,v,c,a,u,b,a,t,c,a,c,a,b,a,d,+,=,+,=,-,=,-,=,-,+,-,+,-,=,:,:,:,:,),(,),(,),(,:,源代码：,代码序列,例：赋值语句,T,4,:=A+B-(E-(C+D),四元式序列,G,T,1,：,=A+B,T,2,：,=C+D,T,3,：,=E-T,2,T,4,：,=T,1,-T,3,DAG,：,A B E,C D,n9,n3,n8,n1,n2,n
7、7,n6,n4,n5,T4,T1,T3,T2,+,-,-,+,从DAG生成目标代码,T4:=A+B-(E-(C+D),T1:=A+B MOV A,R0T2:=C+D ADD B,R0T3:=E-T2 MOV C,R1T4:=T1-T3 ADD D,R1 MOV R0,T1 MOV E,R0 SUB R1,R0 MOV T1,R1 SUB R0,R1 MOV R1,T4,T2:=C+D MOV C,R0 T3:=E-T2 ADD D,R0T1:=A+B MOV E,R1T4:=T1-T3 SUB R0,R1 MOV A,R0 ADD B,R0 SUB R1,R0 MOV R0,T4原因：T4的计
8、算紧跟在T1之后,尽可能使一个结点的求值紧接着它的最左变量的求值之后启发式排序算法(1)while存在未列入表的内部结点do(2)begin选取一个未列入表的但其全部父结点均已列 入表的结点n;(3)将n列入表中;(4)while n的最左子结点m不是叶结点并且其所有 父结点均已列入表中do(5)begin将m列入表中;(6)n:=m(7)end(8)end,基于树重写的代码生成例:ai:=b+1,:=,ind,+,Memb,const1,ind,+,consti,regsp,consta,regsp,+,+,regi,+,ADD Rj,Ri,regi,regj,(1),Reg,0,const,a,MOV#a,R,0,(7),reg,0,ADD SP,R,0,MOV#a,R0ADD SP,R0ADD i(SP),R0MOV b,R1INC R1MOV R1,*R0,12.3 常用的代码生成程序的开发方法,解释性代码生成法模式匹配代码生成法表驱动代码生成法,
