第11章代码优化精选文档.ppt

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

1、本讲稿第一页，共七十五页本章知识点：本章知识点：局部优化局部优化控制流分析和循环优化控制流分析和循环优化数据流的分析与全局优化数据流的分析与全局优化优化技术简介优化技术简介本讲稿第二页，共七十五页 优优 化化编译前端编译前端代码优化器代码优化器代码产生代码产生控制流分析控制流分析数据流分析数据流分析代码变换代码变换代码优化器的地位和结构代码优化器的地位和结构首页首页结束结束本讲稿第三页，共七十五页1 1、优化的概念：、优化的概念：优化的定义优化的定义:对程序进行各种等价变换，使得变换后对程序进行各种等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行的代码运行结果与变换前代码运行

2、结果相同，而运行速度加大，或占用存储空间减少，或两者都有。我们速度加大，或占用存储空间减少，或两者都有。我们通常称这种变换为通常称这种变换为优化优化。11.1 11.1 优化技术简介优化技术简介首页首页结束结束本讲稿第四页，共七十五页 优化的目的是为了产生更高效的代码。由优化编译优化的目的是为了产生更高效的代码。由优化编译程序提供的对代码的各种变换必须遵循下面的原则：程序提供的对代码的各种变换必须遵循下面的原则：1)等等价价原原则则主主要要指指优优化化后后的的目目标标代代码码运运行行时时间间较较短短,以以及占用的存储空间较小。及占用的存储空间较小。2)2)有有效效原原则则 使使优优化化后后所所

3、产产生生的的目目标标代代码码运运行行时时间间确确实较短，占用的空间确实较小实较短，占用的空间确实较小 3 3）合合算算原原则则 应应尽尽可可能能以以较较低低的的代代价价取取得得较较好好的的优优化化效效果果2 2、优化的原则、优化的原则首页首页结束结束本讲稿第五页，共七十五页3、代码优化的基本方法、代码优化的基本方法按照与机器相关的程度，代码优化分为：按照与机器相关的程度，代码优化分为：u与机器相关的优化：在生成目标程序时进行的，它在很与机器相关的优化：在生成目标程序时进行的，它在很大程度上与具体的计算机有关。大程度上与具体的计算机有关。u与机器无关的优化：在语法、语义分析生成中间代码之与机器无

4、关的优化：在语法、语义分析生成中间代码之后，在中间代码上进行，这一类优化不依赖于具体的计后，在中间代码上进行，这一类优化不依赖于具体的计算机，而取决于语言的结构。算机，而取决于语言的结构。首页首页结束结束本讲稿第六页，共七十五页根据优化所涉及的程序范围分成根据优化所涉及的程序范围分成:u局部优化：基本块范围内的优化：合并已知量消局部优化：基本块范围内的优化：合并已知量消除公共子表达式，削减计算强度和删除无用代码除公共子表达式，削减计算强度和删除无用代码u循环优化：主要是基于循环的优化，包括循环不变循环优化：主要是基于循环的优化，包括循环不变式外提，归纳变量删除，计算强度削减。式外提，归纳变量删

5、除，计算强度削减。u全局优化：主要是在整个程序范围内进行的优化。全局优化：主要是在整个程序范围内进行的优化。因因为程序段是非线性的，因此需要分析程序的控制流和为程序段是非线性的，因此需要分析程序的控制流和数据流，处理比较复杂。数据流，处理比较复杂。本讲稿第七页，共七十五页4 4、优化技术、优化技术合并常量计算合并常量计算消除公共子表达式消除公共子表达式削减计算强度削减计算强度删除无用代码删除无用代码循环不变表达式外提循环不变表达式外提归纳变量删除归纳变量删除首页首页结束结束演示演示本讲稿第八页，共七十五页局限于基本块范围内的优化称为基本块内的优化局限于基本块范围内的优化称为基本块内的优化或或局

6、部优化局部优化。1 1、基本块的定义、基本块的定义 所谓所谓基本块基本块是指程序中一顺序执行的语句序是指程序中一顺序执行的语句序列，其中只有一个入口和一个出口，入口就是其列，其中只有一个入口和一个出口，入口就是其中的第一个语句，出口就是其中的最后一个语中的第一个语句，出口就是其中的最后一个语句。句。11.2 11.2 局部优化局部优化首页首页结束结束本讲稿第九页，共七十五页划分四元式程序为基本块的算法如下：划分四元式程序为基本块的算法如下：（1）求出四元式程序中各个基本块的）求出四元式程序中各个基本块的入口语句入口语句，它，它们可以是下述语句之一：们可以是下述语句之一：程序的第一个语句；程序的

7、第一个语句；2 2基本块的划分算法基本块的划分算法紧跟在条件转移语句后面的语句。紧跟在条件转移语句后面的语句。能由条件转移语句或无条件转移语句转移到能由条件转移语句或无条件转移语句转移到的目标语句；的目标语句；首页首页结束结束本讲稿第十页，共七十五页（2）对以上求出的每一入口语句构造其所属的基本）对以上求出的每一入口语句构造其所属的基本块。它是由该入口语句到另一入口语句块。它是由该入口语句到另一入口语句(不包括该入不包括该入口语句口语句)，或到一转移语句，或到一转移语句(包括该转移语句包括该转移语句)，或到一，或到一停语句（包括该停语句停语句（包括该停语句)之间的语句序列组成的。之间的语句序列

8、组成的。（3)凡未被纳入某一基本块的语句，都是程序中控制流凡未被纳入某一基本块的语句，都是程序中控制流程无法到达的语句，因而也是不会被执行到的语句，将程无法到达的语句，因而也是不会被执行到的语句，将其删除。其删除。2 2基本块的划分算法基本块的划分算法首页首页结束结束本讲稿第十一页，共七十五页【例如例如】有下列三地址代码程序：有下列三地址代码程序：1）read Xread X2）read Yread Y3）R R：=X mod Y=X mod Y4）ififR=0goto(8)5)X:=Y6)Y:=R7)goto(3)8）writeY9)halt划分为划分为4 4个基本块个基本块:B11B11

9、）、）、2 2）B23)B23)、4 4）B35B35）、）、6 6）、）、7 7）B48B48）、）、9 9）首页首页结束结束本讲稿第十二页，共七十五页【例如例如】划分基本块划分基本块(1)read(C)(2)A:=0(3)B:=1(4)L1:A:=A+B(5)ifB=CgotoL2(6)B:=B+1(7)gotoL1(8)L2:write(A)(9)halt划分为划分为4 4个基本块个基本块:B1B1（1 1）、（）、（2 2）、（）、（3 3）B2B2（4 4）、（）、（5 5）B3B3（6 6）、（）、（7 7）B4B4（8 8）、（）、（9 9）首页首页结束结束本讲稿第十三页，共七十

10、五页3 3、基本块的变换、基本块的变换基本块内可进行的优化：基本块内可进行的优化：合并已知常量和复写传播合并已知常量和复写传播临时变量改名临时变量改名交换语句的位置交换语句的位置删除公共子表达式删除公共子表达式删除无用代码删除无用代码首页首页结束结束本讲稿第十四页，共七十五页 基本块优化的实现基本块优化的实现从四元式序列构造从四元式序列构造DAG DAG，然后再从，然后再从DAGDAG重写重写四元式。四元式。4 4、基本块的有向图、基本块的有向图DAGDAG表示表示基本块内部优化实现的主要工具为：基本块内部优化实现的主要工具为：DAG(Directed DAG(Directed Acyclic

11、 GraphAcyclic Graph的缩写的缩写)u DAG:DAG:如果有向图中任一通路都不是环路如果有向图中任一通路都不是环路,则称该有向则称该有向图为无环路有向图，也称有向非循环图图为无环路有向图，也称有向非循环图,简称简称DAGDAG。u 用用DAGDAG图表示各个值的计算图表示各个值的计算/依赖关系。依赖关系。演示演示本讲稿第二十三页，共七十五页DAG图中结点的特点图中结点的特点1.1.叶结点叶结点 标记标记:标识符名标识符名(变量名变量名)或常数或常数,写在结点下面。写在结点下面。代表代表:该结点代表该变量或常数的值。该结点代表该变量或常数的值。地址的表示：地址的表示：Addr(

12、A)Addr(A)通常将其标识符加上下标通常将其标识符加上下标0,0,表示该变量的初值。表示该变量的初值。2.2.内部结点内部结点标记标记:一个运算符号，写在结点下面。一个运算符号，写在结点下面。代表代表:利用后续结点运算出来的值。利用后续结点运算出来的值。3 3图中各个结点可能附加一个或多个标识符图中各个结点可能附加一个或多个标识符,表示这些标识表示这些标识符具有该结点所代表的值，同一个结点的标识符表示相同的符具有该结点所代表的值，同一个结点的标识符表示相同的值，写在结点右面。值，写在结点右面。本讲稿第二十五页，共七十五页四元式相应的四元式相应的DAG（1）A A：=op B=op B 1

13、1型型本讲稿第二十六页，共七十五页本讲稿第二十七页，共七十五页该算法只对如下三种四元式构造该算法只对如下三种四元式构造DAGDAG：0 0型型 A:=BA:=B l l型型 A:=op BA:=op B 2 2型型 A:=B op CA:=B op C op op是双目运算符还可以是是双目运算符还可以是=或或=。基本块的基本块的DAGDAG构造算法构造算法本讲稿第二十八页，共七十五页输入：一个基本块输入：一个基本块输出：相应输出：相应DAG图图算法说明：算法说明：u通过逐个扫描四元式来逐渐建立通过逐个扫描四元式来逐渐建立DAG图。图。u函数函数node(A)的值或者是一个结点的编号的值或者是一

14、个结点的编号n或者无或者无定义。如果是前一种情况，代表存在一个结点定义。如果是前一种情况，代表存在一个结点n，A是其上的标记或附加标识符。是其上的标记或附加标识符。基本块的基本块的DAGDAG构造算法构造算法本讲稿第二十九页，共七十五页首先首先DAGDAG为空。为空。对基本块的每一四元式，依次执行：对基本块的每一四元式，依次执行：1 1如果如果NODENODE（B B）无定义，则构造一标记为）无定义，则构造一标记为B B的叶结点并定的叶结点并定义义NODENODE（B B）为这个结点；）为这个结点；如果当前四元式是如果当前四元式是0 0型，则记型，则记NODE(B)NODE(B)的值为的值为n

15、 n，转，转4 4。如果当前四元式是如果当前四元式是1 1型，则转型，则转2.(1)2.(1)。如果当前四元式是如果当前四元式是2 2型，则：型，则：(I)(I)如果如果NODE(C)NODE(C)无定义，无定义，则构造一标记为则构造一标记为C C的叶结点并定义的叶结点并定义NODE(C)NODE(C)为这个结点；为这个结点；(II)(II)转转2.(2)2.(2)本讲稿第三十页，共七十五页2（合并已知量）（合并已知量）（1）如果）如果NODE(B)是标记为常数的叶结点是标记为常数的叶结点，则转，则转2(3)，否则转，否则转3.（1）。）。（2）如果）如果NODE(B)和和NODE(C)都是标

16、记为常数的叶结点，都是标记为常数的叶结点，则转则转2.（4），否则转），否则转3.（2）。）。（3）执行）执行opB（即合并已知量），令得到的新常数为（即合并已知量），令得到的新常数为P。如果如果NODE(B)是处理当前四元式时新构造出来的结点，是处理当前四元式时新构造出来的结点，则删除它。如果则删除它。如果NODE(P)无定义，则构造一用无定义，则构造一用P做标记的做标记的叶结点叶结点n。置。置NODE(P)=n，转，转4。（4）执行）执行BopC（即合并已知量）（即合并已知量），令得到的新常数为，令得到的新常数为P。如果如果NODE(B)或或NODE(C)是处理当前四元式时新构造出来的是处

17、理当前四元式时新构造出来的结点，则删除它。如果结点，则删除它。如果NODE(P)无定义，则构造一用无定义，则构造一用P做标做标记的叶结点记的叶结点n。置。置NODE(P)=n，转，转4。基本块的基本块的DAGDAG构造算法构造算法本讲稿第三十一页，共七十五页基本块的基本块的DAGDAG构造算法构造算法3（找公共子表达式）（找公共子表达式）（1）检查）检查DAG中是否已有一结点，其唯一后继为中是否已有一结点，其唯一后继为NODE(B)，且，且标记为标记为op（即找公共子表达式）。如果没有，则构造该结点（即找公共子表达式）。如果没有，则构造该结点n，否则就把已有的结点作为它的结点并设该结点为，否则

18、就把已有的结点作为它的结点并设该结点为n，转，转4。（2）检查中）检查中DAG中是否已有一结点，其左后继为中是否已有一结点，其左后继为NODE(B)，其，其右后继为右后继为NODE(C)，且标记为，且标记为op（即找公共子表达式）。如果没（即找公共子表达式）。如果没有，则构造该结点有，则构造该结点n，否则就把已有的结点作为它的结点并设，否则就把已有的结点作为它的结点并设该结点为该结点为n，转，转4。本讲稿第三十二页，共七十五页4.4.（删除无用赋值语句）（删除无用赋值语句）如果如果NODE(A)NODE(A)无定义，则把无定义，则把A A附加在结点附加在结点n n上并令上并令NODE(A)=n

19、NODE(A)=n；否则先把；否则先把A A从从NODE(A)NODE(A)结点上附加结点上附加标识符集中删除（注意，如果标识符集中删除（注意，如果NODE(A)NODE(A)是叶结是叶结点，则其标记点，则其标记A A不删除），把不删除），把A A附加到新结点附加到新结点n n上并令上并令NODE(A)=nNODE(A)=n。转处理下一四元式。转处理下一四元式。本讲稿第三十三页，共七十五页仅含仅含0,1,20,1,2型四元式的基本块的型四元式的基本块的DAGDAG构造算法构造算法:首先：假定首先：假定DAGDAG为空，即没有任何结点。对基本块中的每一四元式依为空，即没有任何结点。对基本块中的每

20、一四元式依次执行：次执行：本讲稿第三十四页，共七十五页【例例】构造下列四元式序列的构造下列四元式序列的DAG图。图。(1)T0:=3.14(2)T1:=2*T0(3)T2:=R+r(4)A:=T1*T2(5)B:=A(6)T3:=2*T0(7)T4:=R+r(8)T5:=T3*T4(9)T6:=R-r(10)B:=T5*T6演示演示本讲稿第三十五页，共七十五页根据根据DAGDAG图重写四元式后得到如下优化的四元式序图重写四元式后得到如下优化的四元式序列：列：(1)T0:=3.14(1)T0:=3.14(2)T1:=6.28(2)T1:=6.28(合并已知量合并已知量)(3)T3:=6.28(3

21、)T3:=6.28(合并已知量合并已知量)(4)T2:=R+r(4)T2:=R+r(5)T4:=T2(5)T4:=T2(删除公共子表达式删除公共子表达式)(6)A:=6.28*T2(6)A:=6.28*T2(7)T5:=A(7)T5:=A(删除公共子表达式删除公共子表达式)(8)T6:=R-r(8)T6:=R-r(9)B:=A*T6(9)B:=A*T6(删除无用代码删除无用代码)本讲稿第三十六页，共七十五页【例例】试对以下基本块试对以下基本块B1应用应用DAG进行优化。进行优化。B1:A:=B*CD:=B/CE:=A+DF:=E*2G:=B*CH:=G*GF:=H*GL:=FM:=L并就以下两

22、种情况分别写出优化后的四元式序列：并就以下两种情况分别写出优化后的四元式序列：若某个变量在基本块后不被引用若某个变量在基本块后不被引用,可删除。可删除。本讲稿第三十七页，共七十五页（1）假设）假设G、L、M在基本块后面被引用；在基本块后面被引用；（2）假设只有）假设只有L在基本块后被引用。在基本块后被引用。解：对于解：对于B1其其DAG图：图：(1)(1)若只有若只有G G、L L、M M在基本块后被引用，则优化为：在基本块后被引用，则优化为：G:=B*CG:=B*C H:=G*G H:=G*G L:=H*G L:=H*G M:=L M:=Ln1n1n1n1+*n3n3n3n3B B B Bn

23、2n2n2n2C C C C*A,GA,GA,GA,Gn4n4n4n4/E E E En6n6n6n62 2 2 2n7n7n7n7F F F F*n8n8n8n8H H H H*F,L,MF,L,MF,L,MF,L,MD D D Dn5n5n5n5n9n9n9n9本讲稿第三十八页，共七十五页(2)若只有若只有L在基本块后被引用，则优化为：在基本块后被引用，则优化为：G:=B*CH:=G*GL:=H*G本讲稿第三十九页，共七十五页11.3 11.3 控制流分析和循环的优化控制流分析和循环的优化定定义义：以以基基本本块块为为结结点点，将将控控制制流流信信息息增增加加到到基基本本块块的的集集合合上

24、上来来表表示示一一个个程程序序而而得得到到的的有有向向图图，称称为为程程序流图序流图。如如果果一一个个结结点点的的基基本本块块入入口口语语句句是是程程序序的的第第一一条条语语句句，则此结点则此结点为首结点为首结点。如如果果在在某某个个执执行行顺顺序序中中基基本本块块B2紧紧接接在在基基本本块块B1之之后执行，则从后执行，则从B1到到B2有一条有向边。有一条有向边。一、程序流图一、程序流图本讲稿第四十页，共七十五页【例例如如】有有下下列列三三地地址址代代码码程程序序，给给出出程程序序流流程程图。图。1）read Xread X2）read Yread Y3）R R：=X mod Y=X mod

25、Y4）ififR=0goto(8)5)X:=Y6)Y:=R7)goto(3)8）writeY9)halt演示演示本讲稿第四十一页，共七十五页【例例】有下列三地址代码程序，给出程序流程图。有下列三地址代码程序，给出程序流程图。(1(1）I:=1I:=1(2)if I 10 goto(15)2)if I 10 goto(15)(3)T1:=2*J(3)T1:=2*J(4)T2:=10*I(4)T2:=10*I(5)T3:=T2+T1(5)T3:=T2+T1(6)T4:=add(A)(6)T4:=add(A)11 11(7)T5:=2*J(7)T5:=2*J(8)T6:=10*I(8)T6:=10*

26、I(9)T7:=T5+T6(9)T7:=T5+T6(10)T8:=add(A)-11(10)T8:=add(A)-11(11)T9:=T8T7(11)T9:=T8T7(12(12）T4T3:=T9+1T4T3:=T9+1(13)I:=I+1(13)I:=I+1(14)goto(2)(14)goto(2)(15)(15)演示演示本讲稿第四十二页，共七十五页循环是程序流图中具有唯一入口结点的强连通子图。循环是程序流图中具有唯一入口结点的强连通子图。说明：说明：1.1.强连通的强连通的(任意两结点间任意两结点间,必有一条通路必有一条通路,且该且该通路上各结点都属于该结点序列通路上各结点都属于该结点序

27、列)2.2.它们中间有且只有一个是入口结点。它们中间有且只有一个是入口结点。二、循环的查找二、循环的查找本讲稿第四十三页，共七十五页必经结点：必经结点：在程序流图中，对任意两个结点在程序流图中，对任意两个结点m m和和n n，若从流图的首结点出发，到达，若从流图的首结点出发，到达n n的任一的任一通路都要经过通路都要经过m m，则称，则称m m是是n n的必经结点，记为的必经结点，记为 m DOM n,m DOM n,流图中结点流图中结点n n的所有必经结点的集合，的所有必经结点的集合，称为结点称为结点n n的必经结点集，记为的必经结点集，记为D(n).D(n).回边：回边：设设n-mn-m是

28、流图中的一条有向边，且是流图中的一条有向边，且m m DOM n,DOM n,则称则称n-mn-m是流图中的一条回边。是流图中的一条回边。本讲稿第四十四页，共七十五页【例例】对下面语句划分基对下面语句划分基本块，画出程序流程图本块，画出程序流程图a:=1;ifa=bthenb:=1elsec:=1endif;d:=a+b1 1、翻译的四元式是：、翻译的四元式是：1）a:=12)IFa=bgoto4)3)goto6)4)b:=15)goto7)6)c:=17)d:=a+b;步骤：步骤：1 1、翻译为四元式、翻译为四元式2 2、划分基本块，画程、划分基本块，画程序流程图序流程图本讲稿第四十五页，共

29、七十五页2 2、划分基本块，画程序流程图、划分基本块，画程序流程图1 1）a:=1a:=12)IF a=b goto 4)2)IF a=b goto 4)3)goto 6)3)goto 6)4)b:=1 4)b:=1 5)goto 7)5)goto 7)6)c:=16)c:=17)d:=a+b;7)d:=a+b;本讲稿第四十六页，共七十五页(1)read(C)(2)A:=0(3)B:=1(4)L1:A:=A+B(5)ifB=CgotoL2(6)B:=B+1(7)gotoL1(8)L2:write(A)(9)halt【例例】对下面语句划分基本块，画出程序流程图。对下面语句划分基本块，画出程序流程

30、图。本讲稿第四十七页，共七十五页本讲稿第四十八页，共七十五页【例如例如】67341235761212121必经结点必经结点 必经结点集必经结点集D(6)=1,2,4,6D(1)=1D(2)=1,2D(3)=1,2,3D(4)=1,2,4D(5)=1,2,4,5D(7)=1,2,4,73本讲稿第四十九页，共七十五页下图给出求回边下图给出求回边n-dn-d组成的循环的算法：组成的循环的算法：procedure insen(m)procedure insen(m)；if mif m不属于不属于loop thenloop then begin begin loop:loop:loop Umloop U

31、m；把把m m下推进栈下推进栈stackstack；endend；*主程序主程序*StackStack：空；：空；loop:loop:dd；insert(n)insert(n)；while stack while stack 非空非空 dOdObeginbegin 把把stackstack的栈顶元素的栈顶元素m m上托出去上托出去 for p P(m)dOfor p P(m)dO insert(p)insert(p)end end 其中其中P(m)P(m)表示结点表示结点m m的前驱的前驱结点集，结点集，stackstack为工作栈，为工作栈，looploop为所求循环。为所求循环。inser

32、tinsert为一为一过程。过程。本讲稿第五十页，共七十五页算法的基本思想是：算法的基本思想是：由于要求回边由于要求回边n-dn-d组成组成的循环，这个循环将以的循环，这个循环将以d d为其唯为其唯入口，入口，n n是它的一是它的一个出口。若个出口。若n n不等于不等于d d，则，则n n的所有前驱结点应属于循的所有前驱结点应属于循环。当求出环。当求出n n的所有前驱后，只要它们不是循环入口的所有前驱后，只要它们不是循环入口d d，就应再求出它们的前驱，新求出的所有前驱也，就应再求出它们的前驱，新求出的所有前驱也应属于循环。然后再对新求出的所有前驱，重复应属于循环。然后再对新求出的所有前驱，重

33、复以上步骤，直到所求出的前驱是以上步骤，直到所求出的前驱是d d为止。此时算为止。此时算法结束。法结束。本讲稿第五十一页，共七十五页回边回边66循环循环6744,5,6,7422,3,4,5,6,7【例例】673412357612121231本讲稿第五十二页，共七十五页四元式序列如下：四元式序列如下：1 1）J J：=0;=0;2)L1:I=0;2)L1:I=0;3)IF I8 goto L33)IF I8 goto L34)L2:A:=B+C4)L2:A:=B+C5)B:=D*C5)B:=D*C6)L3:IF B=0 goto L4;6)L3:IF B=0 goto L4;7)write B

34、;8)goto L5;7)write B;8)goto L5;9)L4:I:=I+1;9)L4:I:=I+1;10)IF I8 goto L2;10)IF I8 goto L2;11)L5:J:=J+1;11)L5:J:=J+1;12)IF J=3 goto L1 13)HALT12)IF JB goto B4IF AB goto B4B1B1I:=2I:=2B:=I+YB:=I+YB3B3A:=A+1A:=A+1J:=M+NJ:=M+NY:=Y-1Y:=Y-1IF Y=0 goto B2IF YB goto B4IF AB goto B4B1B1I:=2I:=2B:=I+YB:=I+YB3B

35、3A:=A+1A:=A+1Y:=Y-1Y:=Y-1IF Y=0 goto B2IF Y 10 goto(15)2)if I 10 goto(15)(3)T1:=2*J(3)T1:=2*J(4)T2:=10*I(4)T2:=10*I(5)T3:=T2+T1(5)T3:=T2+T1(6)T4:=add(A)(6)T4:=add(A)11 11(7)T5:=2*J(7)T5:=2*J(8)T6:=10*I(8)T6:=10*I(9)T7:=T5+T6(9)T7:=T5+T6(10)T8:=add(A)-11(10)T8:=add(A)-11(11)T9:=T8T7(11)T9:=T8T7(12(12

36、）T4T3:=T9+1T4T3:=T9+1(13)I:=I+1(13)I:=I+1(14)goto(2)(14)goto(2)(15)(15)本讲稿第五十八页，共七十五页划分基本块并划出流程图：划分基本块并划出流程图：（1 1 1 1）I:=1I:=1I:=1I:=1(2)If I 10 goto(15)(2)If I 10 goto(15)(2)If I 10 goto(15)(2)If I 10 goto(15)(3)T1:=2*J(3)T1:=2*J(4)T2:=10*I(4)T2:=10*I(5)T3:=T2+T1(5)T3:=T2+T1(6)T4:=add(A)(6)T4:=add(

37、A)11 11(7)T5:=2*J(7)T5:=2*J(8)T6:=10*I(8)T6:=10*I(9)T7:=T5+T6(9)T7:=T5+T6(10)T8:=add(A)-11(10)T8:=add(A)-11(11)T9:=T8T7(11)T9:=T8T7(12(12）T4T3:=T9+1T4T3:=T9+1(13)I:=I+1(13)I:=I+1(14)goto(2)(14)goto(2)(15)(15)(15)(15)B1B1B1B1B2B2B2B2B3B3B3B3B4B4本讲稿第五十九页，共七十五页代码外提后：代码外提后：（1 1）I:=1I:=1(3)T1:=2*J(3)T1:=

38、2*J(6)T4:=add(A)(6)T4:=add(A)11 11(7)T5:=2*J(7)T5:=2*J(8)T8:=add(A)-11(8)T8:=add(A)-11 (2)if I 10 goto(15)(2)if I 10 goto(15)(4)T2:=10*I(4)T2:=10*I(5)T3:=T2+T1(5)T3:=T2+T1(8)T6:=10*I(8)T6:=10*I(9)T7:=T6+T5(9)T7:=T6+T5(11)T9:=T8T7(11)T9:=T8T7(12)T4T3:=T9+1(12)T4T3:=T9+1(13)I:=I+1(13)I:=I+1(14)goto (1

39、4)goto（2 2）(15)(15)(15)(15)B1B1B1B1B2B2B2B2 B2B2B2B2B3B3B3B3B4B4本讲稿第六十页，共七十五页（1 1）I I：=1=1 (3)T1:=2*J(3)T1:=2*J(6)T4:=add(A)(6)T4:=add(A)11 11(7)T5:=2*J(7)T5:=2*J(10)T8:=add(A)-11(10)T8:=add(A)-11(4)T2:=10*I(4)T2:=10*I(8)T6:=10*I(8)T6:=10*I(2)If I 10 goto(15)(2)If I 10 goto(15)(5)T3:=T2+T1(5)T3:=T2+

40、T1(9)T7:=T6+T5(9)T7:=T6+T5(11(11）T9:=T8T7T9:=T8T7(12)T4T3:=T9+1(12)T4T3:=T9+1(13)I:=I+1(13)I:=I+1(4(4)T2:=T2+10)T2:=T2+10(8(8)T6:=T6+10)T6:=T6+10(14)goto B2(14)goto B2(15)(15)(15)(15)B1B1B1B1B2B2B2B2 B2B2B2B2B3B3B3B3B4B4本讲稿第六十一页，共七十五页2、强度消弱：指把程序中执行时间较长的运算替、强度消弱：指把程序中执行时间较长的运算替换为执行时间较短的运算换为执行时间较短的运算3

41、、删除归纳变量删除归纳变量本讲稿第六十二页，共七十五页再次强度消弱再次强度消弱如果，如果，T2,T6出循出循环后不是活动变量，环后不是活动变量，则可在循环后删除。则可在循环后删除。(1)I:=1(1)I:=1(1)I:=1(1)I:=1(3)T1:=2*J(3)T1:=2*J(6)T4:=add(A)-11(6)T4:=add(A)-11(7)T5:=2*J(7)T5:=2*J(10)T8:=add(A)-11(10)T8:=add(A)-11(4)T2:=10*I(4)T2:=10*I(8)T6:=10*I(8)T6:=10*I(5)T3:=T2+T1(5)T3:=T2+T1(9)T7:=T

42、6+T5(9)T7:=T6+T5(2)if I 10 goto(15)(2)if I 10 goto(15)(11)T9:=T8T7(11)T9:=T8T7(12)T4T3:=T9+1(12)T4T3:=T9+1(13)I:=I+1(13)I:=I+1(4(4)T2:=T2+10)T2:=T2+10(8(8)T6:=T6+10)T6:=T6+10(5(5)T3:=T3+10)T3:=T3+10(9(9)T7:=T7+10)T7:=T7+10(14)goto B2(14)goto B2(15)(15)(15)(15)B1B1B1B1B2B2B2B2 B2B2B2B2B3B3B3B3本讲稿第六十三

43、页，共七十五页(15)(15)(15)(15)(2)if T3R goto(15)(2)if T3R goto(15)(3)T1:=2*J(3)T1:=2*J(6)T4:add(A)(6)T4:add(A)11 11(7)T5:=2*J(7)T5:=2*J(10)T8:=add(A)(10)T8:=add(A)11 11(4)T2:=10*I(4)T2:=10*I(8)T6:=10*I(8)T6:=10*I(5)T3:=T2+T1(5)T3:=T2+T1(9)T7:=T6+T5(9)T7:=T6+T5(2(2)R=100+T1)R=100+T1 （1 1 1 1）I I I I：=1=1=1=

44、1B1B1B1B1B2B2B2B2(11)T9:=T8T7(11)T9:=T8T7(12)T4T3:=T9+1(12)T4T3:=T9+1(5(5)T3:=T3+10)T3:=T3+10(9(9)T7:=T7+10)T7:=T7+10(14)Goto B2(14)Goto B2B2B2B2B2B3B3B3B3本讲稿第六十四页，共七十五页解：解：三地址代码：三地址代码：(1)I:=1(1)I:=1(1)I:=1(1)I:=1(2)j:=1(2)j:=1(2)j:=1(2)j:=1B1B1B1B1例例3试写出以下程序段试写出以下程序段forI:=1toMdoforj:=1toNdoAI,j:=BI

45、,j的三地址代码，然后求出其中的循环，并进行循环优化。的三地址代码，然后求出其中的循环，并进行循环优化。本讲稿第六十五页，共七十五页(3)If IM goto(30)(3)If IM goto(30)(4)If jN goto(13)(4)If jN goto(13)(5)T1:=I*N(5)T1:=I*N(6)T2:=T1+j(6)T2:=T1+j(7)T3:=N+1(7)T3:=N+1(8)T4:=add(A)-T3(8)T4:=add(A)-T3(9)T5:=add(B)-T3(9)T5:=add(B)-T3(10)T4T2:=T5T2(10)T4T2:=T5T2(11)j:=j+1(1

46、1)j:=j+1(12)goto (4)(12)goto (4)(13)I:=I+1(13)I:=I+1(14)j:=1(14)j:=1(15)goto (3)(15)goto (3)(30)(30)(30)(30)B2B2B2B2B3B3B3B3B4B4B4B4B5B5B5B5B6B6B6B6本讲稿第六十六页，共七十五页代码外提：代码外提：（1 1）I:=1I:=1(2)j:=1(2)j:=1(7)T3:=N+1(7)T3:=N+1(8)T4:=add(A)-T3(8)T4:=add(A)-T3(9)T5:=add(B)-T3(9)T5:=add(B)-T3(3)If IM goto (30

47、)(3)If IM goto (30)(5)T1:=I*N(5)T1:=I*N(4)If j N goto(13)(4)If j N goto(13)(6)T2:=T1+j(6)T2:=T1+j(10)T4T2:=T5T2(10)T4T2:=T5T2(11)j:=j+1(11)j:=j+1(12)goto (4)(12)goto (4)(13)I:=I+1(13)I:=I+1(13)I:=I+1(13)I:=I+1(14)j:=1(14)j:=1(14)j:=1(14)j:=1(15)goto (3)(15)goto (3)(15)goto (3)(15)goto (3)(30)(30)B1B

48、1B1B1B2B2B2B2 B2B2B2B2B3B3B3B3 B3B3B3B3B4B4B4B4B5B5B5B5B6B6B6B6本讲稿第六十七页，共七十五页强度消弱：强度消弱：(1)(1)I:=1I:=1(2)(2)j:=1j:=1(7)T3:=N+1(7)T3:=N+1(8)T4:=add(A)-T3(8)T4:=add(A)-T3(9)T5:=add(B)-T3(9)T5:=add(B)-T3(5(5)T1:=I*N)T1:=I*N (3)if I M goto(30)(3)if I M goto(30)(4)If j N goto(13)(4)If j N goto(13)(6)T2:=T

49、1+j(6)T2:=T1+j(10)T4T2:=T5T2(10)T4T2:=T5T2(11)j:=j+1(11)j:=j+1(12)goto (4)(12)goto (4)(13)I:=I+1(13)I:=I+1(5)T1:=T1+N(5)T1:=T1+N(14)j:=1(14)j:=1(15)goto (3)(15)goto (3)(30)(30)(30)(30)B1B1B1B1B2B2B2B2 B2B2B2B2B3B3B3B3B4B4B4B4B5B5B5B5B6B6B6B6本讲稿第六十八页，共七十五页强度消弱强度消弱(1):（1 1）I:=1I:=1(2)j:=1(2)j:=1(7)T3:

50、=N+1(7)T3:=N+1(8)T4:=add(A)-T3(8)T4:=add(A)-T3(9)T5:=add(B)-T3(9)T5:=add(B)-T3(5(5)T1:=I*N)T1:=I*N(3)If IM goto (30)(3)If IM goto (30)(5)T2:=T1+j(5)T2:=T1+j(4)If j N goto(13)(4)If j N goto(13)(10)T4T2:=T5T2(10)T4T2:=T5T2(11)j:=j+1(11)j:=j+1(6)(6)T2:=T2+1 T2:=T2+1(12)goto (4)(12)goto (4)(13)I:=I+1(13