编译原理 第12章(清华大学).ppt

《编译原理 第12章(清华大学).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第12章代码生成代码生成要考虑的主要问题基本块的代码生成(在一个基本块范围内考虑如何充分利用寄存器的问题)从dag生成代码代码生成要考虑的主要问题——具体细节依赖于目标机器和操作系统共同的问题：1.充分利用寄存器基本块中全局寄存器分配：不把寄存器平均分配给各个变量使用，而是从可用的寄存器中分出几个，固定分配给几个变量单独使用。标准——以各变量在循环内需要访问主存单元的次数为标准。2.选择计算机指令系统3.选择计算次序目标代码的三种形式地址代真的机器代码待装配的机器代码模块汇编语言（宏汇编）机器指令形式(opsource,destination)ADDs,d//d+sSUBs,d//d-sMO

2、Vs,d//sd机器指令开销(cost)MOVR,M开销2ADD#1,R开销2MOVR0,R1开销1目标机器的地址方式地址方式汇编形式地址增加的开销直接地址方式MM1寄存器方式RR0间接寄存器方式*Rcontents(R)0索引方式c(R)c+contents(R)1间接索引方式*c(R)contents(c+contents(R))1a:=b+c1.MOVb,R0ADDc,R0cost=6MOVR0,a2.MOVb,aADDc,acost=6假定R0,R1和R2中分别存放了a,b和c的地址,采用:3.MOV*R1,*R0ADD*R2,*R0cost=2假定R1和R2中分别包含b和c的值,

3、并且b的值在这个赋值以后不再需要,则还可有4.ADDR2,R1MOVR1,acost=3T4:=A+B-(E-(C+D))T1:=A+BMOVA,R0T2:=C+DADDB,R0T3:=E-T2MOVC,R1T4:=T1-T3ADDD,R1MOVR0,T1MOVE,R0SUBR1,R0MOVT1,R1SUBR0,R1MOVR1,T4T2:=C+DMOVC,R0T3:=E-T2ADDD,R0T1:=A+BMOVE,R1T4:=T1-T3SUBR0,R1MOVA,R0ADDB,R0SUBR1,R0MOVR0,T4．简单的代码生成器（基本块内）在一个基本块范围内考虑如何充分利用寄存器的问题：l尽可

4、能地让该变量的值保留在寄存器中l尽可能引用变量在寄存器中的值待用信息：若在一个基本块中，变量A在四元式i中被定值，在i后面的四元式j中要引用A值，且从i到j之间没有其它对A的定值点，这时我们称j是四元式i中对变量A的待用信息或称下次引用信息，同时也称A是活跃的，，若A被多次引用则可构成待用信息链与活跃信息链。可从基本块的出口由后向前扫描，对每个变量建立相应的待用信息链和活跃变量信息链。计算待用信息的算法：对各基本块的符号表中的“待用信息”栏和“活跃信息”栏置初值，即把“待用信息”栏置“非待用”，对“活跃信息”栏按在基本块出口处是否为活跃而置成“活跃”或“非活跃”。这里假定变量都是活跃的，临时

5、变量都是非活跃的。符号表中增加“待用信息”栏和“活跃信息”栏从基本块出口到基本块入口由后向前依次处理每个四元式。对每个四元式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）的次序不能颠倒。其中假定d在基本

6、块的出口是活跃的。代码序列从dag生成目标代码例：赋值语句T4:=A+B-(E-(C+D))四元式序列GT1：=A+BT2：=C+DT3：=E-T2T4：=T1-T3DAG：ABECDn9n3n8n1n2n7n6n4n5T4T1T3T2+--+T4:=A+B-(E-(C+D))T1:=A+BMOVA,R0T2:=C+DADDB,R0T3:=E-T2MOVC,R1T4:=T1-T3ADDD,R1MOVR0,T1MOVE,R0SUBR1,R0MOVT1,R1SUBR0,R1MOVR1,T4T2:=C+DMOVC,R0T3:=E-T2ADDD,R0T1:=A+BMOVE,R1T4:=T1-T3SU

7、BR0,R1MOVA,R0ADDB,R0SUBR1,R0MOVR0,T4原因：T4的计算紧跟在T1之后尽可能使一个结点的求值紧接着它的最左变量的求值之后启发式排序算法(1)while存在未列入表的内部结点do(2)begin选取一个未列入表的但其全部父结点均已列入表的结点n;(3)将n列入表中;(4)whilen的最左子结点m不是叶结点并且其所有父结点均已列入表中do(5)begin将m列入表中;(6)n:=