第12章-代码生成ppt课件.ppt

《第12章-代码生成ppt课件.ppt》由会员分享，可在线阅读，更多相关《第12章-代码生成ppt课件.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓第十二章 代码生成 12.1 12.1 代码生成概述代码生成概述 12.2 12.2 一个简单的代码生成程序一个简单的代码生成程序 12.3 12.3 几种常用的代码生成程序的开发方法几种常用的代码生成程序的开发方法 12.4 12.4 全局寄存器分配全局寄存器分配 12.5 12.5 代码生成程序的自动化构造代码生成程序的自动化构造武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓12.1 12.1 代码生成概述代码生成概述12.1.1 目标代码的三种形式目标代码的三种形式: 能够立即执行的机器语言代码，所有地址均已能够立即执行的

2、机器语言代码，所有地址均已定位；定位； 待装配的机器代码模块，当需要执行时，由连待装配的机器代码模块，当需要执行时，由连接装入程序把它们和某些运行程序连接起来，接装入程序把它们和某些运行程序连接起来，转换成能执行的机器语言代码；转换成能执行的机器语言代码； 汇编语言代码，需经过汇编程序汇编，转换成汇编语言代码，需经过汇编程序汇编，转换成可立即执行的机器语言代码。可立即执行的机器语言代码。武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓 12.1.2 12.1.2 代码生成要考虑的主要问题代码生成要考虑的主要问题具体细节依赖于目标机器和操作系统具体细节依赖于目标机器和操作系统(1)代码生

3、成程序的输入代码生成程序的输入 线性表示、三地址表示、图形表示线性表示、三地址表示、图形表示(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 (

4、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, *M 开销开销 3武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓目标机器的地址方式目标机器的地址方式地址方式汇编形式地址增加的开销直接地址方式MM1寄存器方式RR0间接寄存器方式*Rcontents(R)0索引方式c(R)c+

5、contents(R)1间接索引方式*c(R)contents(c+contents(R)1武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓12.2.2 12.2.2 待用信息链法待用信息链法 在一个基本块范围内考虑如何充分利用寄存器的问题：在一个基本块范围内考虑如何充分利用寄存器的问题：l 尽可能地让该变量的值保留在寄存器中尽可能地让该变量的值保留在寄存器中l 尽可能引用变量在寄存器中的值尽可能引用变量在寄存器中的值 待用信息：若在一个基本块中，变量待用信息：若在一个基本块中，变量 A在四元式在四元式i中被定中被定值，在值，在i后面的四元式后面的四元式j中要引用中要引用A值，且从值，

6、且从i到到 j之间没有其之间没有其它对它对A的定值点，这时我们称的定值点，这时我们称 j是四元式是四元式i中对变量中对变量A的待用的待用信息或称下次引用信息，同时也称信息或称下次引用信息，同时也称 A是活跃的，若是活跃的，若A被多次被多次引用则可构成待用信息链与活跃信息链。引用则可构成待用信息链与活跃信息链。可从基本块的出口由后向前扫描，对每个变量建立相应的待用可从基本块的出口由后向前扫描，对每个变量建立相应的待用信息链和活跃变量信息链。信息链和活跃变量信息链。武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓计算待用信息的算法：计算待用信息的算法： （1 1）符号表中增加）符号表中增加

7、“待用信息待用信息”栏和栏和“活跃信息活跃信息”栏栏: : 对各基本块的符号表中的对各基本块的符号表中的“待用信息待用信息”栏和栏和“活跃信活跃信息息”栏置初值，即把栏置初值，即把“待用信息待用信息”栏置栏置“非待用非待用”，对，对“活活跃信息跃信息”栏按在基本块出口处是否为活跃而置成栏按在基本块出口处是否为活跃而置成“活跃活跃”或或“非活跃非活跃”。这里假定变量都是活跃的，临时变量都是非活。这里假定变量都是活跃的，临时变量都是非活跃的。跃的。武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓 （2 2）从基本块出口到基本块入口由后向前依次处理每个四）从基本块出口到基本块入口由后向前依次

8、处理每个四元元式。对每个四元式式。对每个四元式i:A := B op C，依次执行下述步骤：，依次执行下述步骤：a） 把符号表中变量把符号表中变量A的待用信息和活跃信息附加到四元式的待用信息和活跃信息附加到四元式i上。上。b） 把符号表中变量把符号表中变量A的待用信息栏和活跃信息栏分别置为的待用信息栏和活跃信息栏分别置为“非待用非待用”和和“非活跃非活跃”。（由于在（由于在i 中对中对A的定值只能的定值只能在在 i以后的四元式才能引用，因而对以后的四元式才能引用，因而对 i以前的四元式来说以前的四元式来说A是不活跃也不可能是待用的）是不活跃也不可能是待用的）c） 把符号表中变量把符号表中变量B

9、和和 C的待用信息和活跃信息附加到四元的待用信息和活跃信息附加到四元式式 i上。上。d） 把符号表中变量把符号表中变量B和和 C的待用信息栏置为的待用信息栏置为“ i”，活跃信，活跃信息栏置为息栏置为“活跃活跃”。注意，以上注意，以上a）和）和b），），c）和）和d）的次序不能颠倒。）的次序不能颠倒。武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓12.2.3 代码生成算法代码生成算法 基本块的代码生成算法基本块的代码生成算法假设只有假设只有A:=B op C的四元式序列的四

10、元式序列A 对每个四元式对每个四元式i: A:=B op C，依次执行下述，依次执行下述步骤：步骤：(1) 以四元式以四元式i: A:=B op C为参数，调用过程为参数，调用过程getreg(i: A:=B op C)。从。从getreg返回时，得到一返回时，得到一寄存器寄存器R，用它作存放，用它作存放A现行值的寄存器；现行值的寄存器；(2) 利用利用AVALUEB和和AVALUEC，确定出，确定出B和和C现行值存放位置现行值存放位置B和和C，如果其现行值在寄，如果其现行值在寄存器中，则把寄存器取作存器中，则把寄存器取作B和和C；武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓武汉理

11、工大学计算机科学系林泓武汉理工大学计算机科学系林泓其中假定其中假定d在基本块的出口是活跃的。在基本块的出口是活跃的。uvdutvcaubatcacabad+ += =+ += =- -= =- -= =- -+ +- -+ +- -= =:)()()(:源代码：源代码：武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓代码序列武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓例：赋值语句例：赋值语句 T4:=A+B-(E-(C+D)四元式序列四元式序列GT1：=A+BT2：=C+DT3：=E-T2T4：=T1-T3DAG： A B E C Dn9n3n8n1n2n7n6n4n5 T

12、4 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

13、 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不

14、是叶结点并且其所有不是叶结点并且其所有 父结点均已列入表中父结点均已列入表中do(5) begin将将m列入表中列入表中;(6) n: =m(7) end(8) end武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓3t2t:1t4t6t:2te4t:3t8t5t:4tc6t:5tba:6ted:8t* *= =+ += =- -= =* *= =- -= =+ += =+ += =武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓基于树重写的代码生成基于树重写的代码生成例例:ai:=b+1: =ind+Membconst1

15、ind+constiregspconstaregsp+武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓regi+ADD Rj,Riregiregj武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓(1) regi constcMOV #c, Ri(2) regi memaMOV a, Ri(3) mem MOV Ri, a(4) mem MOV Rj, *Ri(5) regi MOV c(Rj), Ri: =memaregi: =memaregjindconstcregjregi+武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓(6) regi ADD c(Rj), Ri

16、(7) regi ADD Rj, Ri(8) regi INC Ri+regiindconstcregj+regicost1+regiregj武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓: =ind+Membconst1ind+constiregSPreg0+(1) Reg0 constaMOV #a, R0(7) reg0 ADD SP, R0+reg0regSP武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓indconstiregSP+reg0indconstiregSP+: =indreg0+membconst1武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓MOV #a, R0ADD SP, R0ADD i(SP),R0MOV b,R1INC R1MOV R1, *R0+reg1const1: =indreg1reg0武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓12.3 常用的代码生成程序的开发方法常用的代码生成程序的开发方法 解释性代码生成法 模式匹配代码生成法 表驱动代码生成法