【教学课件】第九章代码生成.ppt
《【教学课件】第九章代码生成.ppt》由会员分享,可在线阅读,更多相关《【教学课件】第九章代码生成.ppt(36页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第九章第九章 代码生成代码生成1第九章第九章 代代 码码 生生 成成 本章内容本章内容n一个简单的代码生成算法一个简单的代码生成算法n涉及存储管理,指令选择,寄存器分配涉及存储管理,指令选择,寄存器分配和计算次序选择和计算次序选择等基本问题等基本问题前端前端代代 码码 优优 化化 器器中间中间代码代码源程序源程序代码代码生成生成器器中间中间代码代码目标目标程序程序29.1 9.1 代码生成器设计中的问题代码生成器设计中的问题9.1.1 9.1.1 目标程序目标程序n可执行目标模块可执行目标模块n可重定位目标模块可重定位目标模块n允许程序模块分别编译允许程序模块分别编译n调用其它先前编译好的程序
2、模块调用其它先前编译好的程序模块n汇编语言程序汇编语言程序n免去编译器重复汇编器的工作免去编译器重复汇编器的工作n从教学角度,增加可读性从教学角度,增加可读性39.1 9.1 代码生成器设计中的问题代码生成器设计中的问题9.1.2 9.1.2 指令的选择指令的选择n目标机器指令系统的性质决定了指令选择的目标机器指令系统的性质决定了指令选择的难易程度难易程度n指令系统的一致性和完备性是重要的因素指令系统的一致性和完备性是重要的因素n指令的速度和机器特点是另一些重要的因素指令的速度和机器特点是另一些重要的因素49.1 9.1 代码生成器设计中的问题代码生成器设计中的问题n若不考虑目标程序的效率,指
3、令的选择是直截若不考虑目标程序的效率,指令的选择是直截了当的。了当的。n如:三地址语句如:三地址语句x:=y+zx:=y+z翻译成如下代码序列:翻译成如下代码序列:(x x,y y和和z z都是静态分配)都是静态分配)nMOVMOVy,y,R0R0/*/*把把y y装入寄存器装入寄存器R0*/R0*/nADDADDz,z,R0 R0/*z/*z加到加到R0R0上上*/*/nMOVMOVR0,R0,x x/*/*把把R0R0存入存入x x中中*/*/n逐个语句地产生代码,常常得到低质量的代码逐个语句地产生代码,常常得到低质量的代码59.1 9.1 代码生成器的设计中的问题代码生成器的设计中的问题
4、语句序列语句序列 a:=b+c a:=b+c d:=a+ed:=a+e的代码如下的代码如下MOV MOV b,b,R0R0ADDADD c,c,R0R0MOVMOV R0,R0,a -a -若若a a不再使用,第三条也多余不再使用,第三条也多余MOVMOV a,a,R0R0-多余的指令多余的指令ADDADD e,e,R0R0MOVMOV R0,R0,d d69.1 9.1 代码生成器设计中的问题代码生成器设计中的问题9.1.3 9.1.3 寄存器分配寄存器分配运算对象处于寄存器中的指令通常比运算对运算对象处于寄存器中的指令通常比运算对象处于内存的指令要短一些,执行也快一些象处于内存的指令要短一
5、些,执行也快一些n寄存器分配寄存器分配选择驻留在寄存器中的一组变量选择驻留在寄存器中的一组变量n寄存器指派寄存器指派挑选变量要驻留的具体寄存器挑选变量要驻留的具体寄存器79.1 9.1 代码生成器设计中的问题代码生成器设计中的问题9.1.4 9.1.4 计算次序的选择计算次序的选择n某种计算次序可能会比其它次序需要较少的某种计算次序可能会比其它次序需要较少的寄存器来保存中间结果寄存器来保存中间结果n选择最佳次序是一个选择最佳次序是一个NPNP完全问题完全问题89.2 9.2 目目 标标 机机 器器 9.2.1 9.2.1 目标机器的指令系统目标机器的指令系统选择可作为几种微机代表的寄存器机器选
6、择可作为几种微机代表的寄存器机器n四字节组成一个字,有四字节组成一个字,有n n个通用寄存器个通用寄存器R0,R1,R0,R1,Rn-1,Rn-1。n二地址指令:二地址指令:opop 源,目的源,目的MOVMOV 将源移到目的中将源移到目的中 ADDADD 将源加到目的中将源加到目的中 SUBSUB 在目的中减去源在目的中减去源 99.3 9.3 基本块和流图基本块和流图怎样为三地址语句序列生成目标代码?怎样为三地址语句序列生成目标代码?beginbegin|(1)|(1)prod:=0 prod:=0 prod:=0;prod:=0;|(2)|(2)i:=1 i:=1 i:=1;i:=1;|
7、(3)|(3)t t1 1:=4*i:=4*i do begindo begin|(4)|(4)t t2 2:=at:=at1 1 prod:=prod+ai*bi;|(5)prod:=prod+ai*bi;|(5)t t3 3:=4*i:=4*i i:=i+1i:=i+1|(6)|(6)t t4 4:=bt:=bt3 3 end while i=20end while i=20|(7)|(7)t t5 5:=t:=t2 2*t*t4 4 endend|(8)|(8)t t6 6:=prod+t:=prod+t5 5|(9)|(9)prod:=tprod:=t6 6|(10)|(10)t t7
8、 7:=i+1:=i+1|(11)|(11)i:=ti:=t7 7|(12)if i=20 goto(3)|(12)if i=20 goto(3)109.3 9.3 基本块和流图基本块和流图9.3.1 9.3.1 基本块基本块n基本块基本块:连续的语句序列,控制流从它的开:连续的语句序列,控制流从它的开始进入,并从它的末尾离开始进入,并从它的末尾离开n再用有向边表示基本块之间的控制流信息,再用有向边表示基本块之间的控制流信息,就能得到程序的就能得到程序的流图流图119.3 9.3 基本块和流图基本块和流图将三地址语句序列划分成基本块将三地址语句序列划分成基本块n首先确定所有的入口语句首先确定所
9、有的入口语句n序列的第一个语句是入口语句序列的第一个语句是入口语句n能由条件转移语句或无条件转移语句转到的语句能由条件转移语句或无条件转移语句转到的语句是入口语句是入口语句n紧跟在条件转移语句或无条件转移语句后面的语紧跟在条件转移语句或无条件转移语句后面的语句是入口语句句是入口语句n每个入口语句到下一个入口语句之前的语句每个入口语句到下一个入口语句之前的语句序列构成一个基本块序列构成一个基本块 129.3 9.3 基本块和流图基本块和流图(1)prod:=0(2)i:=1(3)t1:=4*i(4)t2:=at1(5)t3:=4*i(6)t4:=bt3(7)t5:=t2*t4(8)t6:=pro
10、d+t5(9)prod:=t6(10)t7:=i+1(11)i:=t7(12)if i=20 goto(3)(1)prod:=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)B1B2139.3 9.3 基本块和流图基本块和流图9.3.2 9.3.2 基本块的变换基本块的变换n三地址语句三地址语句x:=y+zx:=y+z引用引用y y和和z z并对并对x x定值定值n一一个个名名字字的的值值在在基基
11、本本块块的的某某一一点点以以后后还还要要引引用的话,我们说这个名字在该点是用的话,我们说这个名字在该点是活跃活跃的的n基本块的等价基本块的等价n两个基本块计算一组同样的表达式两个基本块计算一组同样的表达式n这些表达式的值分别代表同样的活跃名字的值这些表达式的值分别代表同样的活跃名字的值n有很多等价变换可用于基本块有很多等价变换可用于基本块n局部变换局部变换n全局变换全局变换149.3 9.3 基本块和流图基本块和流图n公共子表达式删除公共子表达式删除a:=b+ca:=b+c a:=b+c a:=b+cb:=a b:=a d d b:=a b:=a d dc:=b+cc:=b+c c:=b+c
12、c:=b+cd:=a d:=a d d d:=b d:=bn无用代码删除无用代码删除定值定值x:=y+zx:=y+z以后不再引用,则称以后不再引用,则称x x为无用变量为无用变量159.3 9.3 基本块和流图基本块和流图n语句交换语句交换t t1 1:=b:=b +c+c t t2 2:=x:=x +y+yt t2 2:=x:=x +y+y t t1 1:=b:=b +c+c当且仅当当且仅当x x和和y y都不是都不是t t1 1,b b和和c c都不是都不是t t2 2 n代数变换代数变换x:=x+0 x:=x+0可以删除可以删除x:=x*1 x:=x*1 可以删除可以删除x:=y*2 x
13、:=y*2 改成改成x:=y*y x:=y*y 169.3 9.3 基本块和流图基本块和流图9.3.3 9.3.3 流图流图把把控控制制流流信信息息加加到到基基本本块块集集合合,形形成成一一个个有有向图来表示程序向图来表示程序首结点、前驱、后继首结点、前驱、后继179.3 9.3 基本块和流图基本块和流图n什么是循环什么是循环?n所有结点是强连通的所有结点是强连通的n唯一的循环入口唯一的循环入口n外循环和内循环外循环和内循环n内循环不含其它循环内循环不含其它循环prod:=0i:=1t1:=4*it2:=at1t3:=4*It4:=bt3t5:=t2*t4t6:=prod+t5prod:=t6
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 教学课件 教学 课件 第九 代码 生成
限制150内