《编译原理2011课件第12章代码生成》由会员分享，可在线阅读，更多相关《编译原理2011课件第12章代码生成（35页珍藏版）》请在金锄头文库上搜索。
1、第十二章 代码生成,代码生成要考虑的主要问题 基本块的代码生成(在一个基本块范围内考虑如何充分利用寄存器的问题) 从dag生成代码,l,代码生成要考虑的主要问题,具体细节依赖于目标机器和操作系统,共同的问题：,1.,充分利用寄存器,基本块中,全局,寄存器分配：不把寄存器平均分配给各个变量使,用，而是从可用的寄存器中分出几个，固定分配给几个变量单,独使用。标准以各变量在循环内需要访问主存单元的次数,为标准。,2.,选择计算机指令系统,3.,选择计算次序,目标代码的三种形式,地址代真的机器代码,待装配的机器代码模块,汇编语言,（宏汇编）,机器指令形式 (op source ,destination
2、) ADD s,d / d+s SUB s,d /d-s MOV s,d /s d 机器指令开销 (cost) MOV R,M 开销 2 ADD #1 ,R 开销 2 MOV R0,R1 开销 1,目标机器的地址方式,a:=b+c 1. MOV b, R0 ADD c, R0 cost=6 MOV R0, a 2. MOV b, a ADD c, a cost=6 假定R0, R1和R2中分别存放了a, b和c的地址, 采用: 3. MOV *R1, *R0 ADD *R2, *R0 cost=2 假定R1和R2中分别包含b和c的值, 并且b的值在这个赋值以后不再需要, 则还可有 4. ADD
3、 R2, R1 MOV R1, a cost=3,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 T1:= A+B MOV E,R1 T4:=T1-T3 SUB R0,R1 MOV A,R0 ADD B, R0 SUB R1,R0 MOV R0,T4,简单的代码生成器,（基本块
4、内）,在一个基本块范围内考虑如何充分利用寄存器的问题：,l,尽可能地让该变量的值保留在寄存器中,l,尽可能引用变量在寄存器中的值,待用信息：若在一个基本块中，变量,A,在四元式,i,中被定,值，在,i,后面的四元式,j,中要引用,A,值，且从,i,到,j,之间没有其,它对,A,的定值点，这时我们称,j,是四元式,i,中对变量,A,的待用,信息或称下次引用信息，同时也称,A,是活跃的，若,A,被多次,引用则可构成待用信息链与活跃信息链。,可从基本块的出口由后向前扫描，对每个变量建立相应的待用,信息链和活跃变量信息链。,计算待用信息的算法：,对各基本块的符号表中的,“待用信息”栏和,“活跃信息”,
5、栏置初值，即把,“待用信息”栏置,“非待用”，对,“活跃,信息”栏按在基本块出口处是否为活跃而置成,“活跃”或,“非活跃”。这里假定变量都是活跃的，临时变量都是非,活跃的。,符号表中增加“待用信息”栏和“活跃信息”栏,从基本块出口到基本块入口由后向前依次处理每个四元,式。对每个四元式,i:,A,:=,B op C,，依次执行下述步骤：,a,）,把符号表中变量,A,的待用信息和活跃信息附加到四元式,i,上。,b,）,把符号表中变量,A,的待用信息栏和活跃信息栏分别置为,“非待用”和,“非活跃”。,（由于在,i,中对,A,的定值只能,在,i,以后的四元式才能引用，因而对,i,以前的四元式来说,A,
6、是不活跃也不可能是待用的）,c,）,把符号表中变量,B,和,C,的待用信息和活跃信息附加到四元,式,i,上。,d,）,把符号表中变量,B,和,C,的待用信息栏置为,“,i,”，活跃信,息栏置为,“活跃”。,注意，以上,a,）和,b,），,c,）和,d,）的次序不能颠倒。,其中假定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
7、+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 T1:= A+B
8、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,: =,
9、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,选择实验最终报告内容 1. 概述: 源、目标语言 实现工具（平台） 运行平台 2. 结构设计说明 各功能模块描述 3. 主要成分描述 (1) 符号表 (2) 运行时存储组织和管理 (3) 语法分析方法 (4) 中间代码表示 4. 开发过程和完成情况,12,3,基于树重写的代码生成,例：,ai:=b+1,替换,模版,动作,例子：,前缀表示,:=ind + ind +const,a,reg,sp,ind + const,i,+ mem,b,const,1,语法制导翻译模式,
