编译原理代码生成8.ppt
《编译原理代码生成8.ppt》由会员分享,可在线阅读,更多相关《编译原理代码生成8.ppt(59页珍藏版)》请在三一文库上搜索。
1、第八章 代 码 生 成,本章内容 一个简单的代码生成算法 涉及存储管理,指令选择,寄存器分配和计算次序选择等基本问题,8.1 代码生成器的设计中的问题,8.1.1 目标程序 可执行目标模块 可重定位目标模块 允许程序模块分别编译 调用其它先前编译好的程序模块 汇编语言程序 免去编译器重复汇编器的工作 从教学角度,增加可读性,8.1 代码生成器的设计中的问题,8.1.2 指令的选择 目标机器指令系统的性质决定了指令选择的难易程度,指令系统的统一性和完备性是重要的因素 指令的速度和机器特点是另一些重要的因素,8.1 代码生成器的设计中的问题,若不考虑目标程序的效率,指令的选择是直截了当的 三地址语
2、句x = y + z(x,y和z都是静态分配) MOV y, R0 / 把y装入寄存器R0 / ADD z, R0 / z加到R0上 / MOV R0, x / 把R0存入x中 / 逐个语句地产生代码,常常得到低质量的代码,8.1 代码生成器的设计中的问题,语句序列 a = b + c d = a + e 的代码如下 MOV b, R0 ADD c, R0 MOV R0, a MOV a, R0 ADD e, R0 MOV R0, d,8.1 代码生成器的设计中的问题,语句序列 a = b + c d = a + e 的代码如下 MOV b, R0 ADD c, R0 MOV R0, a MO
3、V a, R0 - 多余的指令 ADD e, R0 MOV R0, d,8.1 代码生成器的设计中的问题,语句序列 a = b + c d = a + e 的代码如下 MOV b, R0 ADD c, R0 MOV R0, a MOV a, R0 - 多余的指令 ADD e, R0 - 若a不再使用,第三条也 MOV R0, d - 多余,8.1 代码生成器的设计中的问题,8.1.3 寄存器分配 运算对象处于寄存器中的指令通常比运算对象处于内存的指令要短一些,执行也快一些 寄存器分配 选择驻留在寄存器中的一组变量 寄存器指派 挑选变量要驻留的具体寄存器,8.1 代码生成器的设计中的问题,8.1
4、.4 计算次序的选择 某种计算次序可能会比其它次序需要较少的寄存器来保存中间结果,8.2 目 标 机 器,8.2.1 目标机器的指令系统 选择可作为几种微机代表的寄存器机器 四字节组成一个字,有n个通用寄存器R0,R1, ,Rn-1。 二地址指令 op 源,目的 MOV 源传到目的 ADD 源加到目的 SUB 目的减去源,8.2 目 标 机 器,地址模式和它们的汇编语言形式及附加代价 模式 形式 地址 附加代价 绝对地址 M M 1 寄存器 R R 0 变址 c(R) c + contents(R) 1 间接寄存器 R contents(R) 0 间接变址 c(R) contents(c +
5、contents(R) 1 直接量 #c c 1,8.2 目 标 机 器,指令实例 MOV R0, M MOV 4(R0), M contents(4 + contents(R0) MOV 4(R0), M contents(contents (4 + contents(R0) ) ) MOV #1, R0,8.2 目 标 机 器,8.2.2 指令的代价 指令代价取成1加上它的源和目的地址模式的附加代价 指令 代价 MOV R0,R1 1 MOV R5,M 2 ADD #1, R3 2 SUB 4(R0), 12(R1) 3,8.2 目 标 机 器,a = b + c, a、b和c都静态分配内
6、存单元 MOV b, R0 ADD c, R0 代价= 6 MOV R0, a,8.2 目 标 机 器,a = b + c, a、b和c都静态分配内存单元 MOV b, R0 ADD c, R0 代价= 6 MOV R0, a MOV b, a ADD c, a 代价= 6,8.2 目 标 机 器,a = b + c, a、b和c都静态分配内存单元 若R0,R1和R2分别含a,b和c的地址,则 MOV R1, R0 ADD R2, R0 代价= 2,8.2 目 标 机 器,a = b + c, a、b和c都静态分配内存单元 若R0,R1和R2分别含a,b和c的地址,则 MOV R1, R0 A
7、DD R2, R0 代价= 2 若R1和R2分别含b和c的值,并且b的值在这个 赋值后不再需要,则 ADD R2, R1 MOV R1, a 代价= 3,8.3 基本块和流图,怎样为三地址语句序列生成目标代码? |(1) prod = 0 prod = 0; |(2) i = 1 i = 1; |(3) t1 = 4 i do |(4) t2= at1 prod = prod + ai bi; |(5 ) t3 = 4 i i = i +1; |(6 ) t4 = bt3 while (i = 20); |(7 ) t5 = t2 t4 |(8 ) t6 = prod + t5 |(9 ) p
8、rod = t6 |(10) t7 = i +1 |(11) i = t7 |(12 ) if i = 20 goto (3),8.3 基本块和流图,8.3.1 基本块 基本块:连续的语句序列,控制流从它的开始进入,并从它的末尾离开 再用有向边表示基本块之间的控制流信息,就能得到程序的流图,8.3 基本块和流图,三地址语句序列的划分基本块 首先确定所有的入口语句 序列的第一个语句是入口语句 能由条件转移语句或无条件转移语句转到的语句是入口语句 紧跟在条件转移语句或无条件转移语句后面的语句是入口语句 每个入口语句到下一个入口语句之前的语句序列构成一个基本块,8.3 基本块和流图,(1) prod
9、 = 0 (2) i = 1 (3) t1 = 4 i (4) t2= at1 (5 ) t3 = 4 i (6 ) t4 = bt3 (7 ) t5 = t2 t4 (8 ) t6 = prod + t5 (9 ) prod = t6 (10) t7 = i +1 (11) i = t7 (12 ) if i = 20 goto (3),8.3 基本块和流图,8.3.2 基本块的优化 三地址语句x = y + z引用y和z并对x定值 一个名字的值在基本块的某一点以后还要引用的话,则说这个名字在该点是活跃的 基本块的等价 两个基本块计算一组同样的表达式 这些表达式的值分别代表同样的活跃名字的值
10、 有很多等价变换可用于基本块 局部变换 全局变换,8.3 基本块和流图,删除局部公共子表达式 a = b + c a = b + c b = a d b = a d c = b + c c = b + c d = a d d = b 删除死代码 定值x = y + z以后不再引用,则称x为死变量,8.3 基本块和流图,交换相邻的独立语句 t1 = b + c t2 = x + y t2 = x + y t1 = b + c 当且仅当t1和t2不相同,x和y都不是t1, 并且b和c都不是t2 代数变换 x = x + 0 可以删除 x = x 1 可以删除 x = y 2 改成x = y y,8
11、.3 基本块和流图,8.3.3 流图 把控制流信息加到基本块集合,形成一个有向图来表示程序 首结点、前驱、后继,8.3 基本块和流图,什么是循环? 所有结点是强连通的 唯一的循环入口 外循环和内循环,8.3 基本块和流图,8.3.4 下次引用信息 为每个三地址语句x = y op z决定x、y和z的下次引用信息 i: x = y op z . . . 没有对x的赋值 j: = x . . . 没有对x的赋值 k: = x,8.3 基本块和流图,8.3.4 下次引用信息 为每个三地址语句x = y op z决定x、y和z的下次引用信息 i: x = y op z . . . 没有对x的赋值 j:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 代码 生成
链接地址:https://www.31doc.com/p-4175533.html