第十一章代码优化.ppt

《第十一章代码优化.ppt》由会员分享，可在线阅读，更多相关《第十一章代码优化.ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第11章章代码优化代码优化学习目标：学习目标：掌握：基本块的划分掌握：基本块的划分理解：什么是局部优化、循环优化、全局优化理解：什么是局部优化、循环优化、全局优化了解：循环优化技术了解：循环优化技术11.1优化技术简介优化技术简介11.2局部优化局部优化11.3循环优化简介循环优化简介11.1 优化技术简介优化技术简介什么是优化：什么是优化：所所谓谓优优化化是是对对代代码码进进行行等等价价变变换换，使使得得变变换换后后的的代代码码的的效效率率更更高高（节节省省运运行行时时间间、存存储储空空间间或两者兼而有之）或两者兼而有之）优优化化可可在在编编译译的的不不同同阶阶段段进进行行，最最主主要要的

2、的优优化化有有中间代码优化中间代码优化（不依赖具体计算机）（不依赖具体计算机）目标代码优化目标代码优化（依赖于具体计算机）（依赖于具体计算机）中间代码优化中间代码优化中间代码中间代码源代码源代码编译前端编译前端代码生成代码生成目标代码目标代码目标代码优化目标代码优化编译的优化工作阶段编译的优化工作阶段优化的分类：优化的分类：根据优化涉及的程序范围，分为：根据优化涉及的程序范围，分为：局局部部优优化化：在在只只有有一一个个入入口口、一一个个出出口口的的基基本块上进行优化本块上进行优化循环优化循环优化：对循环中的代码进行优化：对循环中的代码进行优化全局优化全局优化：在整个程序范围内进行的优化：在整

3、个程序范围内进行的优化中间代码优化常用技术中间代码优化常用技术1.删除多余运算删除多余运算（删除公共子表达式）（删除公共子表达式）如果子表达式如果子表达式E在前面计算过，且之后在前面计算过，且之后E中的变中的变量值都未改变，那么量值都未改变，那么E的重复出现称为公共子的重复出现称为公共子表达式，可避免重复计算表达式，可避免重复计算(1)和和(4)中都有中都有4*I的运算，的运算，(1)到到(4)之间无对之间无对I的的赋值，赋值，显然两次计算的值是相等的，显然两次计算的值是相等的，(4)的运算是多余的的运算是多余的例例(1)T1:=4*I(2)T2:=addr(A)4(3)T3:=T2T1(4)

4、T4:=4*I(5)(5)(4)变换成变换成T4:=T12.合并已知量与复写传播合并已知量与复写传播如果运算量都是已知量，则在编译时就算出它的值，如果运算量都是已知量，则在编译时就算出它的值，称为称为合并已知量合并已知量若有若有A:=B，称为把称为把B值值复写复写到到A。如果其后有引用如果其后有引用A的地方，且其间的地方，且其间A、B的的值都未改变，则可把对值都未改变，则可把对A的的引用改为对引用改为对B引用，称为引用，称为复写传播复写传播。例：例：（1）I:=1（2）T1:=4*I（3）T4:=T1（4）T6:=T5T4 I是已知量是已知量把把T1的值复写到的值复写到T4（4）T6:=T5T

5、1 复写传播复写传播（2）T1:=4 合并已知量合并已知量3.删除无用赋值删除无用赋值有些变量的赋值从未被引用，称为无用赋值，应删除。有些变量的赋值从未被引用，称为无用赋值，应删除。无用赋值分三种情况：无用赋值分三种情况：变量被赋值，但在程序中从未被引用（在局部范围变量被赋值，但在程序中从未被引用（在局部范围内难判定）内难判定）变量赋值后未被引用又重新赋值，则前面赋值是变量赋值后未被引用又重新赋值，则前面赋值是无用的无用的变量的赋值只被计算变量自己引用，其他变量都变量的赋值只被计算变量自己引用，其他变量都不引用它不引用它例例（1）I:=1（2）T1:=4（3）T3:=T2T1（4）T4:=T1

6、 （5）I:=I+1（6）T1:=T1+4（7）if T180 goto (3)(4)中对中对T4赋值，但赋值，但T4未被引用；未被引用；(1)和和(5)对对I赋值，但只有赋值，但只有(5)中计算中计算I时引用时引用I如果程序其他地方不需要引用如果程序其他地方不需要引用T4和和I，则则(4)、(1)和和(5)是无用赋值，可删除。是无用赋值，可删除。（2）T1:=4（3）T3:=T2 T1（6）T1:=T1+4（7）if T180 goto (3)4.其他优化技术其他优化技术以下优化技术将在循环优化中介绍：以下优化技术将在循环优化中介绍：代码外提代码外提强度削弱强度削弱变换循环控制条件变换循环控

7、制条件（删除归纳变量）（删除归纳变量）11.2 局部优化局部优化局部优化是指基本块内的优化局部优化是指基本块内的优化基本块基本块是指程序中一顺序执行的语句序列，其是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句。执行时中只有一个入口语句和一个出口语句。执行时只能从入口语句进入，从其出口语句退出只能从入口语句进入，从其出口语句退出11.2.1 基本块的划分基本块的划分把程序（中间代码形成）划分成基本块的算法：把程序（中间代码形成）划分成基本块的算法：1.求基本块的求基本块的入口语句入口语句，它们是：，它们是：1)程序的第一个语句；或者程序的第一个语句；或者2)条条件件转转移移或

8、或无无条条件件转转移移语语句句的的转转移移目目标标语语句句；或者或者3)紧跟在紧跟在条件转移条件转移语句后面的语句。语句后面的语句。2对每一入口语句，构造其所属的基本块对每一入口语句，构造其所属的基本块:它它是是由由该该入入口口语语句句到到下下一一入入口口语语句句(不不包包括括下下一入口语句一入口语句);或到一转移语句或到一转移语句(包括该转移语句包括该转移语句);或到一停止语句或到一停止语句(包括该停止语句包括该停止语句)之间的语句序列组成的。之间的语句序列组成的。3凡凡未未被被纳纳入入某某一一基基本本块块的的语语句句，是是不不会会被被执执行到的语句，可以把它们删除。行到的语句，可以把它们删

9、除。例：例：(1)read X(2)read Y(3)R:=X mod Y(4)if R=0 goto (9)(5)X:=Y(6)Y:=R(7)goto (3)(8)write X(9)write Y(10)halt首先找出基本块的入口语句首先找出基本块的入口语句(1)、(3)、(5)和和(8)是入口语是入口语句；句；根据每个入口语句分别构成根据每个入口语句分别构成基本块基本块B1(1)、(2)B2(3)、(4)B3(5)、(6)、(7)B4(9)、(10)删除所有基本块外的语句删除所有基本块外的语句(8)(1)read X(3)R:=X mod Y(5)X:=Y(9)write Y11.3循

10、环优化简介循环优化简介循环就是程序中那些可能反复执行的代码序列。循环就是程序中那些可能反复执行的代码序列。因因为为循循环环中中的的代代码码要要反反复复执执行行，所所以以循循环环的的代代码优化对提高目标代码的效率将起更大的作用。码优化对提高目标代码的效率将起更大的作用。11.3.1 程序流图程序流图把控制流的信息加到基本块集合上构成的有向图把控制流的信息加到基本块集合上构成的有向图称为表示程序的流图，简称称为表示程序的流图，简称流图流图。流图的构造方法：流图的构造方法：点集点集：以基本块为结点，含程序第一条语句的结：以基本块为结点，含程序第一条语句的结点为首结点。点为首结点。边集边集：从基本块：

11、从基本块Bi向基本块向基本块Bj引引有向边，仅当有向边，仅当1)Bj在在程序中的位置紧跟在程序中的位置紧跟在Bi之后之后,且且Bi的出口语的出口语句句不是不是无条件转移语句无条件转移语句或停止语句。或停止语句。或者或者2)Bi的出口是转移语句的出口是转移语句(goto(s)或或ifgoto(s)，并且转移目标并且转移目标(s)是是Bj的入口语句。的入口语句。例：构造以下程序的流图例：构造以下程序的流图(1)read X(2)read Y(3)R:=X mod Y(4)if R=0 goto (9)(5)X:=Y(6)Y:=R(7)goto (3)(8)Write X(9)write Y(10)

12、halt(1)readX(2)readY(3)R:=XmodY(4)ifR=0goto(9)(5)X:=Y(6)Y:=R(7)goto(3)(9)writeY(10)halt11.3.2循环优化循环优化1.代码外提代码外提把循环不变运算，即其结果独立于循环执行次把循环不变运算，即其结果独立于循环执行次数的表达式，提到循环的前面，使之只在循环数的表达式，提到循环的前面，使之只在循环外计算一次，这种优化称为代码外提。外计算一次，这种优化称为代码外提。循环不变运算循环不变运算：运算量为常量或在循环外定值，：运算量为常量或在循环外定值，每次循环时其值不变的运算。每次循环时其值不变的运算。(1)P:=0

13、(2)I:=1(3)T1:=4*I(4)T2:=addr(A)4(5)T3:=T2T1(6)T4:=T1(7)T5:=addr(B)4(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)ifI20goto(3)中间代码段中间代码段B1B2(1)P:=0(2)I:=1(4)T2:=addr(A)4(7)T5:=addr(B)4(3)T1:=4*I(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)IfI20goto(3)代码外提后代码外提后B1B2(4)中的运算量中的运

14、算量addr(A)是分配是分配的数组的数组A的首地址，是个常的首地址，是个常量，量，4也是常量，因而也是常量，因而(4)是是循环不变运算，同样循环不变运算，同样(7)也也是循环不变运算，是循环不变运算，(4)、(7)都可提到循环前都可提到循环前2.强度削弱强度削弱强强度度削削弱弱是是指指把把程程序序中中强强度度大大的的运运算算替替换换成成强强度小的运算。例如把乘法运算换成加法运算等度小的运算。例如把乘法运算换成加法运算等(1)P:=0(2)I:=1(4)T2:=addr(A)4(7)T5:=addr(B)4(3)T1:=4*I(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T4(9)

15、T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)IfI20goto(3)中间代码段中间代码段(1)P:=0(2)I:=1(4)T2:=addr(A)4(7)T5:=addr(B)4(3)T1:=4*I(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3)T1:=T1+4(12)ifI20goto(5)强度削弱强度削弱I和和T1始终保持始终保持T1:=4*I的线性的线性关系关系这样把这样把(12)的循环控制条件的循环控制条件I20变换成变换成T180，程序的运程序的运行结果不变行结果不变这种变换称

16、为变换循环控制条这种变换称为变换循环控制条件件经过这一变换，循环中经过这一变换，循环中I的值的值不被引用，四元式不被引用，四元式(11)可被删去，可被删去，这是变换的目的所在。这是变换的目的所在。(1)P:=0(2)I:=1(4)T2:=addr(A)4(7)T5:=addr(B)4(3)T1:=4*I(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3)T1:=T1+4(12)ifI20goto(5)3.变换循环控制条件变换循环控制条件(1)P:=0(2)I:=1(4)T2:=addr(A)4(7)T5:=add

17、r(B)4(3)T1:=4*I(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(3)T1:=T1+4(12)ifT180goto(5)变换循环控制条件变换循环控制条件中间代码段中间代码段(1)P:=0(2)I:=1(4)T2:=addr(A)4(7)T5:=addr(B)4(3)T1:=4*I(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3)T1:=T1+4(12)ifI20goto(5)本章小结本章小结主要讨论在中间代码级别上进行的优化主要讨论在中间代码级别上进行的优化优化的种类：局部优化、循环优化、全局优化优化的种类：局部优化、循环优化、全局优化基本块内的优化基本块内的优化v删除公共子表达式、合并已知量、复写传播删除公共子表达式、合并已知量、复写传播、删除无用赋值删除无用赋值循环优化循环优化代码外提、强度削弱、变换循环控制条件代码外提、强度削弱、变换循环控制条件