代码优化解析.ppt
《代码优化解析.ppt》由会员分享,可在线阅读,更多相关《代码优化解析.ppt(61页珍藏版)》请在咨信网上搜索。
1、第7章代码优化词法分析器词法分析器语法分析器语法分析器中间代码生成器中间代码生成器优化段优化段源程序源程序单词符号单词符号语法单位语法单位四元式四元式表表格格管管理理出出错错处处理理目标代码生成器目标代码生成器四元式四元式目标代码目标代码 7.1 7.1 优化概述 优化是一种等价的、有效的程序变换。优化的目的是为了产生更高效的代码。由优化的编译程序提供的对代码的各种变换必须遵循下面的原则:等价原则:是指经过优化后不应改变源程序运行的结果。有效原则:经优化后所产生的目标代码运行时间较短,占用存储空间较小。合算原则:应尽可能以较低的代价取得较好的优化效果。编译前端编译前端代码优化器代码优化器编译后
2、端编译后端控制流分析控制流分析数据流分析数据流分析代码变换代码变换优化技术分类代码优化实际上是对代码进行等价变换,由一组代码变成运行结果相同的另一组代码。源程序一级的优化:对中间代码的优化,与机器无关,面向各种语言.主要包括:局部优化、循环优化、全局优化 目标代码的优化:与具体机器有关.主要包括对寄存器的优化,多处理机的优化、特殊指令的优化等优化技术分类优化技术分类局部优化:程序中顺序执行的语句序列循环优化:程序中循环语句的优化全局优化:整个程序范围内的优化优化的种类:优化的种类:删除多余运算删除多余运算(或称删除公用子表达式或称删除公用子表达式)代码外提代码外提强度消弱强度消弱变换循环控制条
3、件变换循环控制条件合并已知量合并已知量复写传播复写传播删除无用赋值删除无用赋值中间代码优化举例设、为两个一维数组,他们的初始地设、为两个一维数组,他们的初始地址分别为址分别为addr(A),addr(B),addr(A),addr(B),源程序段是源程序段是S=0S=0FOR(i=1,i=20;i+)FOR(i=1,i=20;i+)S=S+Ai+BiS=S+Ai+Bi假设机器按字节编制根据程序流向的特点,分为B1,B2两块.B1是循环体外的语句,B2是可重复执行的循环语句序列原则:通过等价变换,将尽量减少循环体中的语句,同时尽可能减少无实际意义的重复计算与赋值,尽可能降低机器运算强度,运算的级
4、别.删除公共子表达式删除公共子表达式(删除多删除多余运算余运算)公共子表达式是指在一个基本程序块内公共子表达式是指在一个基本程序块内计算结果相同的子表达式计算结果相同的子表达式代码外提代码外提是指把循环不变的运算提到循环体前面是指把循环不变的运算提到循环体前面优化前的中间代码优化前的中间代码经删除公共子表达式和代码经删除公共子表达式和代码外提后的中间代码外提后的中间代码3.3.降低运算强度降低运算强度 主要指不改变运算结果的主要指不改变运算结果的前提下前提下,将程序执行时间长的将程序执行时间长的运算替换成执行时间短的运运算替换成执行时间短的运算降低运算级别算降低运算级别经强度削弱后的中间代码经
5、强度削弱后的中间代码4.变换循环控制变量(删除归纳变量)如果在循环体内存在一个变量(或临时变量)T与循环控制变量 i保持线性关系,同时在循环后面不引用I,而除去i又不影响程序运行结果,则可由T取代循环控制变量变量 I,这种方法称为变换循环控制变量(删除归纳变量)5.合并已知量合并已知量是指若参加运算的两个对象在编译时都是已知量,则可以在编译时直接计算出它们的运算结果6.复写传播是指尽量不引用那些在程序中仅仅只传递信息而不改变其值,也不影响其运行结果的变量.经变换循环控制变量经变换循环控制变量,合并合并已知量已知量,复写传播后的中间复写传播后的中间代码代码7,7,删除无用赋值删除无用赋值减少无用
6、的变量,使代码更简洁假(1)S=0(4)T2=addr(A)-4(7)T5=addr(B)-4(3)T1=4(5)T3=T2T1(8)T6=T5T1(9)T7=T3*T6(10)S=S+T7(3)T1=T1+4(12)if T180 goto(5)B2B1真经删除无用赋值后的经删除无用赋值后的中间代码中间代码经过优化后经过优化后,代码具有以下特点代码具有以下特点:(1)(1)减少了循环体内可执行代码减少了循环体内可执行代码:10:10条条6 6条条(2)(2)减少了乘法运算次数减少了乘法运算次数:3:3次次1 1次次(3)(3)减少了全程范围内使用的变量减少了全程范围内使用的变量:i,T:i,
7、T4 47.2 局部优化合并已知量:运算对象是已知量,编译时直接计算它们的值,而不必等到程序运行时再计算。删除公共子表达式:如果一个表达式E的值,前面已经算过,并且在这之后E的值没有改变,则E称为公共子表达式,则可以避免它的重复运算,称为删除公共子表达式。(删除多余运算)删除无用赋值:如果一些变量的值在整个程序中不再被使用,则这些变量的赋值对程序的运算结果没有任何作用,则可以删除对这些变量赋值 的代码,称为删除无用赋值。局部优化基本块:一个基本块是指程序中一顺序执行的语句序列。其中只有一个入口和一个出口,入口就是其中第一个语句,出口就是最后一条语句。对于一个基本块来说,执行时只能从其入口进入,
8、从出口退出。局限于基本块范围内的优化称为基本块内的优化,或称局部优化。划分四元式程序为基本块的算法:1.求出四元式程序中各个基本块的入口语句:1)程序第一个语句,或2)能由条件转移语句或无条件转移语句转移到的语句,或3)紧跟在条件转移语句后面的语句。2.对以上求出的每个入口语句,确定其所属的基本块。它是由该入口语句到下一入口语句(不包括该入口语句)、或到一转移语句(包括该转移语句)、或一停语句(包括该停语句)之间的语句序列组成的。入口语句入口语句n n入口语句入口语句m m入口语句入口语句n n转移语句转移语句m m入口语句入口语句n n停语句停语句m m3.凡未被纳入某一基本块中的语句,都是
9、程序不可到达的语句,可以从程序中删除。例:划分基本块例:划分基本块(1)(1)read Xread X(2)(2)read Yread Y(3)(3)C:=X mod Y C:=X mod Y(4)(4)if C=0 goto(8)if C=0 goto(8)(5)(5)X:=YX:=Y(6)(6)Y:=CY:=C(7)(7)goto(3)goto(3)(8)(8)write Ywrite Y(9)(9)halthalt1.1.求出四元式程序中各个基本块的入口求出四元式程序中各个基本块的入口语句语句:1)1)程序第一个语句,或程序第一个语句,或2)2)能由条件转移语句或无条件转移能由条件转移语
10、句或无条件转移语句转移到的语句,或语句转移到的语句,或3)3)紧跟在条件转移语句后面的语句。紧跟在条件转移语句后面的语句。例:划分基本块例:划分基本块(1)(1)read Xread X(2)(2)read Yread Y(3)(3)R:=X mod YR:=X mod Y(4)(4)if R=0 goto(8)if R=0 goto(8)(5)(5)X:=YX:=Y(6)(6)Y:=RY:=R(7)(7)goto(3)goto(3)(8)(8)write Ywrite Y(9)(9)halthalt1.1.求出四元式程序中各个基本块的入口求出四元式程序中各个基本块的入口语句语句:1)1)程序
11、第一个语句程序第一个语句,或,或2)2)能由条件转移语句或无条件转移能由条件转移语句或无条件转移语句转移到的语句,或语句转移到的语句,或3)3)紧跟在条件转移语句后面的语句。紧跟在条件转移语句后面的语句。例:划分基本块例:划分基本块(1)(1)read Xread X(2)(2)read Yread Y(3)(3)R:=X mod YR:=X mod Y(4)(4)if R=0 goto(8)if R=0 goto(8)(5)(5)X:=YX:=Y(6)(6)Y:=RY:=R(7)(7)goto(3)goto(3)(8)(8)write Ywrite Y(9)(9)halthalt1.1.求出
12、四元式程序中各个基本块的入口求出四元式程序中各个基本块的入口语句语句:1)1)程序第一个语句,或程序第一个语句,或2)2)能由条件转移语句或无条件转移能由条件转移语句或无条件转移语句转移到的语句语句转移到的语句,或,或3)3)紧跟在条件转移语句后面的语句。紧跟在条件转移语句后面的语句。例:划分基本块例:划分基本块(1)(1)read Xread X(2)(2)read Yread Y(3)(3)R:=X mod YR:=X mod Y(4)(4)if R=0 goto(8)if R=0 goto(8)(5)(5)X:=YX:=Y(6)(6)Y:=RY:=R(7)(7)goto(3)goto(3
13、)(8)(8)write Ywrite Y(9)(9)halthalt1.1.求出四元式程序中各个基本块的入口语求出四元式程序中各个基本块的入口语句句:1)1)程序第一个语句,或程序第一个语句,或2)2)能由条件转移语句或无条件转移语能由条件转移语句或无条件转移语句转移到的语句句转移到的语句,或,或3)3)紧跟在条件转移语句后面的语句。紧跟在条件转移语句后面的语句。例:划分基本块例:划分基本块(1)(1)read Xread X(2)(2)read Yread Y(3)(3)R:=X mod YR:=X mod Y(4)(4)if R=0 goto(8)if R=0 goto(8)(5)(5)
14、X:=YX:=Y(6)(6)Y:=RY:=R(7)(7)goto(3)goto(3)(8)(8)write Ywrite Y(9)(9)halthalt1.1.求出四元式程序中各个基本块的入口求出四元式程序中各个基本块的入口语句语句:1)1)程序第一个语句,或程序第一个语句,或2)2)能由条件转移语句或无条件转移能由条件转移语句或无条件转移语句转移到的语句,或语句转移到的语句,或3)3)紧跟在条件转移语句后面的语句紧跟在条件转移语句后面的语句。例:划分基本块例:划分基本块(1)(1)read Xread X(2)(2)read Yread Y(3)(3)R:=X mod YR:=X mod Y
15、(4)(4)if R=0 goto(8)if R=0 goto(8)(5)(5)X:=YX:=Y(6)(6)Y:=RY:=R(7)(7)goto(3)goto(3)(8)(8)write Ywrite Y(9)(9)halthalt2.2.对以上求出的对以上求出的每个入口语句,每个入口语句,确定其所属的基确定其所属的基本块。它是由该本块。它是由该入口语句到入口语句到下一下一入口语句入口语句(不包括不包括该入口语句该入口语句)、或、或到到一转移语句一转移语句(包包括该转移语句括该转移语句)、或或一停语句一停语句(包括包括该停语句该停语句)之间的之间的语句序列组成的。语句序列组成的。程序流图:(8
16、)write Y(9)halt(5)X:=Y(6)Y:=R(7)goto(3)(3)R:=X mod Y(4)if R=0 goto(8)(1)read X(2)read YB1B2B3B4程序流图以基本块作为结点,控制程序流向作为有向弧,画出的图,称为程序流图。流图G=(N,E,n0)N:表示流图的有限结点集合,每一个结点对应一个基本块。E:流图的有向边集合;n0:表示唯一的首结点,包含程序第一个语句的基本块。程序流图程序流图每个流图以基本块为每个流图以基本块为结点结点。如果一个结点的基本。如果一个结点的基本块的入口语句是程序的第一条语句,则称此结点块的入口语句是程序的第一条语句,则称此结点
17、为首结点为首结点。如果在某个执行顺序中,基本块。如果在某个执行顺序中,基本块B B2 2紧紧接在基本块接在基本块B B1 1之后执行,则从之后执行,则从B B1 1到到B B2 2有一条有向边。有一条有向边。即,如果即,如果有一个条件或无条件转移语句从有一个条件或无条件转移语句从B B1 1的最后一条的最后一条语句转移到语句转移到B B2 2的第一条语句;或者的第一条语句;或者在程序的序列中,在程序的序列中,B B2 2紧接在紧接在B B1 1的后面,并且的后面,并且B B1 1的的最后一条语句不是一个无条件转移语句。我们最后一条语句不是一个无条件转移语句。我们就说就说B B1 1是是B B2
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 代码 优化 解析
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【天****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【天****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。