《十二章节代码生成》由会员分享，可在线阅读，更多相关《十二章节代码生成（36页珍藏版）》请在金锄头文库上搜索。
1、十二章节代码生成Stillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope。有生命必有希望。有生命必有希望l 代码生成要考虑的主要问题代码生成要考虑的主要问题具体细节依赖于目标机器和操作系统具体细节依赖于目标机器和操作系统共同的问题：共同的问题：1. 充分利用寄存器充分利用寄存器基本块中基本块中全局全局 寄存器分配：不把寄存器平均分配给各个变量使寄存器分配：不把寄存器平均分配给各个变量使用，而是从可用的寄存器中分出几个，固定分配给几个变量单用，而是从可用的寄存器中分出几个，固定分配给几个变量单独使用。标准独使用。标准以各变量
2、在循环内需要访问主存单元的次数以各变量在循环内需要访问主存单元的次数为标准。为标准。2. 选择计算机指令系统选择计算机指令系统3. 选择计算次序选择计算次序 目标代码的三种形式目标代码的三种形式 地址代真的机器代码地址代真的机器代码 待装配的机器代码模块待装配的机器代码模块 汇编语言汇编语言（宏汇编）（宏汇编）机器指令形式机器指令形式(op source ,destination)ADD s,d / d+s SUB s,d /d-s MOV s,d /s d机器指令开销机器指令开销 (cost) (cost)MOV R,M 开销开销 2ADD #1 ,R 开销开销 2MOV R0,R1 开销开
3、销 1目标机器的地址方式地址方式汇编形式地址增加的开销直接地址方式MM1寄存器方式RR0间接寄存器方式*Rcontents(R)0索引方式c(R)c+contents(R)1间接索引方式*c(R)contents(c+contents(R)1a:=b+c1. MOV b, R0ADD c,R0cost=6MOV R0, a2.MOV b,aADD c,acost=6 假定R0, R1和R2中分别存放了a, b和c的地址, 采用:3.MOV *R1,*R0ADD *R2,*R0cost=2 假定R1和R2中分别包含b和c的值, 并且b的值在这个赋值以后不再需要, 则还可有4.ADD R2,R1M
4、OV R1,acost=3T4:=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, T4T2:=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 简单的代码生成器简单的代码生成器 （基本块内）（基本块内）在一个
5、基本块范围内考虑如何充分利用寄存器的问题：在一个基本块范围内考虑如何充分利用寄存器的问题：l 尽可能地让该变量的值保留在寄存器中尽可能地让该变量的值保留在寄存器中l 尽可能引用变量在寄存器中的值尽可能引用变量在寄存器中的值 待用信息：若在一个基本块中，变量待用信息：若在一个基本块中，变量 A在四元式在四元式i中被定中被定值，在值，在i后面的四元式后面的四元式j中要引用中要引用A值，且从值，且从i到到j之间没有其之间没有其它对它对A的定值点，这时我们称的定值点，这时我们称 j是四元式是四元式i中对变量中对变量A的待用的待用信息或称下次引用信息，同时也称信息或称下次引用信息，同时也称A是活跃的，若
6、是活跃的，若A被多次被多次引用则可构成待用信息链与活跃信息链。引用则可构成待用信息链与活跃信息链。可从基本块的出口由后向前扫描，对每个变量建立相应的待用可从基本块的出口由后向前扫描，对每个变量建立相应的待用信息链和活跃变量信息链。信息链和活跃变量信息链。计算待用信息的算法：计算待用信息的算法： 对各基本块的符号表中的对各基本块的符号表中的“待用信息待用信息”栏和栏和 “活跃信息活跃信息”栏置初值，即把栏置初值，即把 “待用信息待用信息”栏置栏置“非待用非待用”，对，对 “活跃活跃信息信息”栏按在基本块出口处是否为活跃而置成栏按在基本块出口处是否为活跃而置成 “活跃活跃”或或“非活跃非活跃”。这
7、里假定变量都是活跃的，临时变量都是非。这里假定变量都是活跃的，临时变量都是非活跃的。活跃的。符号表中增加符号表中增加“待用信息待用信息”栏和栏和“活跃信息活跃信息”栏栏 从基本块出口到基本块入口由后向前依次处理每个四元从基本块出口到基本块入口由后向前依次处理每个四元式。对每个四元式式。对每个四元式i: A:=B op C，依次执行下述步骤：，依次执行下述步骤：a） 把符号表中变量把符号表中变量A的待用信息和活跃信息附加到四元式的待用信息和活跃信息附加到四元式i上。上。b） 把符号表中变量把符号表中变量A的待用信息栏和活跃信息栏分别置为的待用信息栏和活跃信息栏分别置为“非待用非待用”和和“非活跃
8、非活跃”。（由于在（由于在i中对中对A的定值只能的定值只能在在i以后的四元式才能引用，因而对以后的四元式才能引用，因而对 i以前的四元式来说以前的四元式来说A是不活跃也不可能是待用的）是不活跃也不可能是待用的）c） 把符号表中变量把符号表中变量B和和C的待用信息和活跃信息附加到四元的待用信息和活跃信息附加到四元式式i上。上。d） 把符号表中变量把符号表中变量B和和C的待用信息栏置为的待用信息栏置为“ i”，活跃信，活跃信息栏置为息栏置为“活跃活跃”。注意，以上注意，以上a）和）和b），），c）和）和d）的次序不能颠倒。）的次序不能颠倒。其中假定d在基本块的出口是活跃的。代码序列从dag生成目标
9、代码例：赋值语句例：赋值语句 T4:=A+B-(E-(C+D)四元式序列四元式序列GT1：=A+BT2：=C+DT3：=E-T2T4：=T1-T3DAG： A B E C Dn9n3n8n1n2n7n6n4n5 T4 T1 T3 T2 + - - +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, T4T2:=C+D MOV C,R0 T3:=E-T2 ADD
10、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的计算紧跟在的计算紧跟在T1之后之后 尽可能使一个结点的求值紧接着它的最左变量的求值之后启发式排序算法(1) while存在未列入表的内部结点do(2) begin选取一个未列入表的但其全部父结点均已列 入表的结点n; (3) 将n列入表中; (4) while n的最左子结点m不是叶结点并且其所有 父结点均已列入表中do(5) begin将m列入表中;(6) n: =m(7) end(8) end基于树重写的代码生成基于
11、树重写的代码生成例例:ai:=b+1: =ind+Membconst1ind+constiregspconstaregsp+regi+ADD Rj,Riregiregj: =ind+Membconst1ind+constiregSPreg0+MOV #a, R0ADD SP, R0ADD i(SP),R0MOV b,R1INC R1MOV R1, *R0选择实验最终报告内容1. 概述: 源、目标语言实现工具（平台）运行平台2. 结构设计说明各功能模块描述3. 主要成分描述(1) 符号表(2) 运行时存储组织和管理(3) 语法分析方法(4) 中间代码表示4. 开发过程和完成情况123 基于树重写的代码生成基于树重写的代码生成例：例：ai:=b+1替换替换 模版模版 动作动作 例子：例子：前缀表示前缀表示:=ind + ind +consta regsp ind + consti + memb const1语法制导翻译模式语法制导翻译模式
