《第12章 代码生成讲义》由会员分享，可在线阅读，更多相关《第12章 代码生成讲义（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)= Ri op Ri, Rj (Ri) op (Rj)= Ri op Ri, c(Rj) (Ri) op( (Rj)+c)= Ri op Ri, *M (Ri) op (M)= Ri op Ri, *Rj (Ri) op (Rj)= Ri op Ri, c*(Rj) (Ri) op( (R
3、j)+c)= Ri 机器指令开销 (cost) op R, M 开销 2 op Ri, Rj 开销 1 op Ri, *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
5、,的待用信息栏和活跃信息栏分别置为,“非待用”和,“非活跃”。,（由于在,i,中对,A,的定值只能,在,i,以后的四元式才能引用，因而对,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) 以四
6、元式i: A:=B op C为参数，调用过程getreg(i: A:=B op C)。从getreg返回时，得到一寄存器R，用它作存放A现行值的寄存器； (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
7、,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,n7,n6,n4,n5,T4,T1,T3,T2,+,-,-,+,从DAG生成目标代码,T4:=A+B-(E-(C+D),T1:= A+B MOV A,R0 T2:=C+D ADD B,R0 T3:=E-T2 MOV C,R1 T4:=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,R0
8、T1:= A+B MOV E,R1 T4:=T1-T3 SUB R0,R1 MOV A,R0 ADD B, R0 SUB R1,R0 MOV R0,T4 原因：T4的计算紧跟在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, R0 ADD SP, R0 ADD i(SP),R0 MOV b,R1 INC R1 MOV R1, *R0,12.3 常用的代码生成程序的开发方法,解释性代码生成法 模式匹配代码生成法 表驱动代码生成法,
