北京航空航天大学《编译原理》第11章 代码优化(1).pdf

《北京航空航天大学《编译原理》第11章 代码优化(1).pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第十一章代码优化••概述概述••优化的例子优化的例子••基本块的优化基本块的优化••循环优化循环优化北京航空航天大学计算机学院11.1概述代码优化（codeoptimization)指编译程序为了生成高质量的目标程序而做的各种加工和处理。时间效率（减少运行时间）目的：提高目标代码运行效率空间效率（减少内存容量）原则：进行优化必须严格遵循“不能改变原有程序语义”原则。北京航空航天大学计算机学院分类：从优化的层次，与机器是否有关，分为：独立于机器的优化：即与目标机无关的优化，通常是在中间代码上进行的优化。与机器有关的优化：充分利用系统资源，（指令系统，寄存器资源）。从

2、优化涉及的范围，又分为：局部优化：是指在基本块内进行的优化。循环优化：对循环语句所生成的中间代码序列上所进行的优化。全局优化：顾名思义，跨越多个基本块的全局范围内的优化。因此它是指在非线性程序段上（包括多个基本块,GOTO,循环）的优化。需要进行全局控制流和数据流分析，复杂。北京航空航天大学计算机学院[定义]基本块（basicblock)满足以下三个条件的程序段，称为基本块：•只有一个入口和一个出口，且语句为顺序执行的程序段。•所有转移语句的目的语句都是基本块的第一条语句。•转移语句的下一条语句是基本块的第一条语句。•如果块中任一语句被执行，则该块内的所有语句也将

3、被执行（无分支），且执行次数一样（无循环）。北京航空航天大学计算机学院例：书上的例子1.FACTOR=2基本块1⊕2.EXP1=…2⊕3.IF()GOTO103⊕4.BASE=2.0⊕⊕基本块4105.FACTOR=FACTOR**25⊕6.GOTO206⊕⊕1110.BASE=…基本块⊕2011.FACTOR…20.Q=⊕21基本块21.RETURN（先编号，后画图→决定基本块）北京航空航天大学计算机学院优化所花费的代价和优化产生的效果可用下图表示：优化的效果局部优化循环优化全局优化优化的代价北京航空航天大学计算机学院•图的左部表示只要做些简单的处理，便能得到明

4、显的优化效果。这相当于局部优化。•若要进一步提高优化效果，就要逐步付出更大的代价——循环优化。•全局优化进一步提高。优化的效果局部循环全局优化优化优化优化的代价北京航空航天大学计算机学院为什么要优化？•有的大型计算程序一运行就要花上几十分钟，甚至好几小时，这时为优化即使付出些代价也是值得的。•另外，程序中的循环往往要占用大量的计算时间。所以为减少循环执行时间所进行的优化对减少整个程序的运行时间有很大的意义。——尤其有实时要求的程序。如市场决策，供需及求益的平衡•至于（像学生作业之类的）简单小程序（占机器内存，运行速度均可接受），或在程序的调试阶段，花费许多代价去进

5、行一遍又一遍的优化就毫无必要了。北京航空航天大学计算机学院11.2优化的基本方法和例子注：实际的优化应在中间代码或目标代码上进行。但为了便于说明，这里用源程序形式举例。（1）利用代数性质（代数变换）•编译时完成常量表达式的计算，整数类型与实型的转换。例：a:=5+6+x→a:=11+x又如：设x为实型，x:=3+1可变换成x:=4.0•下标变量引用时，其地址计算的一部分工作可在编译时预先做好（运行时只需计算“可变部分”即可）。北京航空航天大学计算机学院•运算强度削弱：用一种需要较少执行时间的运算代替另一种运算，以减少运行时的运算强度时、空开销）如x**2→x*x3

6、*x→x+x+x8*x,4*x等换成左移运算x/2,x/16等换成右移运算x:=x+1变为INCx指令x/5→x*0.2等利用机器硬件所提供的一些功能，如左移，右移操作，利用它们做乘法或除法，具有更高的代码效率。北京航空航天大学计算机学院（2）复写(copy)传播如x:=y这样的赋值语句称为复写语句。由于x和y值相同，所以当满足一定条件时，在该赋值语句下面出现的x可用y来代替。例如：x:=y;x:=y;u:=2*x;→u:=2*y;v:=x+1;v:=y+1;这就是所谓的复写传播。(copypropagation)若以后的语句中不再用到若以后的语句中不再用到xx时

7、，则上面的时，则上面的x:=yx:=y可删去。可删去。北京航空航天大学计算机学院若上例中不是x:=y而是x:=3。则复写传播变成了常量传播，即x:=y;x:=3;u:=6;v:=4;u:=2*x;u:=2*x;v:=x+1;v:=x+1;又如t:=y/z;x:=t;11若这里t为暂时（中间）变量，以后不再使用，则可变换为1x:=y/z;此外常量传播，引起常量计算，如：pi=3.14159r=pi/180.0此时：pi=3.14159r=0.0174644（常量计算）北京航空航天大学计算机学院（3）删除公共子表达式具有相同值的子表达式在两个以上地方出现时，称它为公共

8、子表达式(