编译原理 代码优化.ppt
《编译原理 代码优化.ppt》由会员分享,可在线阅读,更多相关《编译原理 代码优化.ppt(51页珍藏版)》请在三一办公上搜索。
1、代码优化,代码优化的目标,提高最终目标代码的运行效率(性能)时间:运行的更快 空间:降低内存需求保持源程序的语义,代码优化的种类,窥孔优化局部优化基本块内优化全局优化基本块间优化(过程内)过程间优化程序全局优化,代码优化的种类窥孔优化,“孔”未优化的目标代码片段(windows)窥孔优化种类:删除冗余的存、取操作e.g.mov r0,a/r0-amov a,r0/a-r0,可删除 删除不可达代码,代码优化的种类窥孔优化,e.g.goto L1goto L2/语句前无标号,死代码L1:L2:控制流优化,代码优化的种类窥孔优化,goto L1L1:goto L2,goto L2L1:goto L2
2、,if ab goto L1L1:goto L2,if ab goto L2L1:goto L2,goto L1/唯一跳转L1/L1前是无条件跳转L1:if a b goto L2L3:,if a b goto L2goto L3L3:,代码优化的种类窥孔优化,强度消弱、删除无用指令e.g.MUL$8,R0-ShiftLeft$3,R0ADD$0,R1/删除,未改变R1MUL$1,R2/删除 利用目标机指令特点e.g.inc、enter(建立栈帧)leave(清除栈帧)CISC 系统的“复杂”寻址模式 其它优化措施,如常量合并、复写传播等,代码优化的种类局部优化,基本块和流图 基本块:能顺序执
3、行的程序代码序列。其入口为:程序的第一代码 条件或无条件转移代码所转到的目标代码 跟在条件或无条件转移代码后的代码 基本块划分 相邻入口中间的代码序列(仅含前一入口)某入口到程序的停止语句代码之间的代码序列 流图:由基本块按控制流方向形成的有向图基本块内优化,主要有:常量传播、合并和公共子表达式删除 复写传播与死代码(无用代码)删除,代码优化的种类全局优化,基本块间优化基本块间控制流与数据流分析技术优化措施主要有:循环优化:80/20 规则 不变式外提、归纳变量删除、强度消弱等 公共子表达式删除 常量传播、合并常量、复写传播 死代码(无用赋值)删除,典型的优化编译器的组织,中间表示,中间表示,
4、优化举例,快速排序程序片段如下,i=m 1;j=n;v=an;while(1)do i=i+1;while(aiv);if(i=j)break;x=ai;ai=aj;aj=x;x=ai;ai=an;an=x;,/B1(1)i:=m 1(2)j:=n(3)t1:=4*n(4)v:=at1,优化举例,快速排序程序片段如下,i=m 1;j=n;v=an;while(1)do i=i+1;while(aiv);if(i=j)break;x=ai;ai=aj;aj=x;x=ai;ai=an;an=x;,/B2(5)i:=i+1(6)t2:=4*i(7)t3:=at2(8)if t3 v goto(5),
5、优化举例,快速排序程序片段如下,i=m 1;j=n;v=an;while(1)do i=i+1;while(aiv);if(i=j)break;x=ai;ai=aj;aj=x;x=ai;ai=an;an=x;,/B3(9)j:=j 1(10)t4:=4*j(11)t5:=at4(12)if t5 v goto(9),优化举例,快速排序程序片段如下,i=m 1;j=n;v=an;while(1)do i=i+1;while(aiv);if(i=j)break;x=ai;ai=aj;aj=x;x=ai;ai=an;an=x;,/B4(13)if i=j goto(23),优化举例,快速排序程序片段
6、如下,i=m 1;j=n;v=an;while(1)do i=i+1;while(aiv);if(i=j)break;x=ai;ai=aj;aj=x;x=ai;ai=an;an=x;,/B5(14)t6:=4*i(15)x:=at6(16)t7:=4*i(17)t8:=4*j(18)t9:=at8(19)at7:=t9(20)t10:=4*j(21)at10:=x(22)goto(5),优化举例,快速排序程序片段如下,i=m 1;j=n;v=an;while(1)do i=i+1;while(aiv);if(i=j)break;x=ai;ai=aj;aj=x;x=ai;ai=an;an=x;,
7、/B6(23)t11:=4*i(24)x:=at11(25)t12:=4*i(26)t13:=4*n(27)t14:=at13(28)at12:=t14(29)t15:=4*n(30)at15:=x,优化举例流图,优化举例,公共子表达式删除基本块内,t6:=4*ix:=at6t7:=4*i t8:=4*jt9:=at8at7:=t9t10:=4*jat10:=xgoto B2,B5,B6,t11:=4*ix:=at11t12:=4*i t13:=4*nt14:=at13at12:=t14t15:=4*n at15:=x,变换,优化举例,公共子表达式删除基本块内,t6:=4*ix:=at6t8:
8、=4*jt9:=at8at6:=t9at8:=xgoto B2,B5,B6,t11:=4*ix:=at11t13:=4*nt14:=at13at11:=t14at13:=x,优化举例,公共子表达式删除基本块间 t2:=4*i:B2-B5 t2:=4*i:B2-B6 t4:=4*j:B3-B5 t1:=4*n:B1-B6,t6:=4*ix:=at6t8:=4*jt9:=at8at6:=t9at8:=xgoto B2,B5,B6,t11:=4*ix:=at11t13:=4*nt14:=at13at11:=t14at13:=x,变换,优化举例,公共子表达式删除基本块间 t3:=at2:B2-B5 t
9、3:=at2:B2-B6 t5:=at4:B3-B5,x:=at2t9:=at4at2:=t9at4:=xgoto B2,B5,B6,x:=at2t14:=at1at2:=t14at1:=x,变换,优化举例,公共子表达式删除基本块间B1中 v:=at1 能否作为公共子表达式?,x:=t3at2:=t5at4:=xgoto B2,B5,B6,x:=t3t14:=at1at2:=t14at1:=x,优化举例,复写传播 形成为f:=g的赋值叫做复写语句 优化过程中会大量引入复写 复写传播变换是在复写语句f:=g后,尽可能用g代表f(暗示有前提条件)复写传播变换带来 常量合并 死代码删除,x:=t3/
10、可以考虑删除at2:=t5at4:=t3goto B2,x:=t3at2:=t5at4:=xgoto B2,优化举例,复写传播,B5,B5,x:=t3/可以考虑删除t14:=at1at2:=t14at1:=t3,优化举例,复写传播,B6,B6,x:=t3t14:=at1at2:=t14at1:=x,B6中,t14:=at1 可以复写传播吗?,优化举例,循环优化 代码外提 归纳变量删除 强度削弱例:while(i=limit 2)变换成t=limit 2;/为什么提出循环?while(i=t),优化举例,强度削弱和归纳变量删除j和t4的值步伐一致地变化这样的变量叫做归纳变量在循环中有多个归纳变量
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译原理 代码优化 编译 原理 代码 优化

链接地址:https://www.31ppt.com/p-4526574.html