第11章代码优化优秀课件.ppt

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

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

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

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

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

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

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

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

8、块的语句，都是程序中控凡未被纳入某一基本块的语句，都是程序中控制流程无法到达的语句，因而也是不会被执行到的制流程无法到达的语句，因而也是不会被执行到的语句，将其删除。语句，将其删除。2基本块的划分算法基本块的划分算法首页首页结束结束第11页，本讲稿共75页【例如例如】有下列三地址代码程序：有下列三地址代码程序：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）、）、2 2）B23)B23)、4

9、4）B35B35）、）、6 6）、）、7 7）B48B48）、）、9 9）首页首页结束结束第12页，本讲稿共75页【例如例如】划分基本块划分基本块(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）首页首页结束结束第13页，本讲稿共75页3 3、基本块的变换、基本块的变换基本

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

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

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

13、页该算法只对如下三种四元式构造该算法只对如下三种四元式构造DAGDAG：0 0型型 A:=BA:=B l l型型 A:=op BA:=op B 2 2型型 A:=B op CA:=B op C op op是双目运算符还可以是是双目运算符还可以是=或或=。基本块的基本块的DAG构造算法构造算法第28页，本讲稿共75页输入：一个基本块输入：一个基本块输出：相应输出：相应DAG图图算法说明：算法说明：u通过逐个扫描四元式来逐渐建立通过逐个扫描四元式来逐渐建立DAG图。图。u函数函数node(A)的值或者是一个结点的编号的值或者是一个结点的编号n或者无或者无定义。如果是前一种情况，代表存在一个结点定义

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

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

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

17、)无定义，则构造一用无定义，则构造一用P做标记的叶结点做标记的叶结点n。置。置NODE(P)=n，转，转4。基本块的基本块的DAG构造算法构造算法第31页，本讲稿共75页基本块的基本块的DAG构造算法构造算法3（找公共子表达式）（找公共子表达式）（1）检查）检查DAG中是否已有一结点，其唯一后继为中是否已有一结点，其唯一后继为NODE(B)，且，且标记为标记为op（即找公共子表达式）。如果没有，则构造该结点（即找公共子表达式）。如果没有，则构造该结点n，否则就把已有的结点作为它的结点并设该结点为否则就把已有的结点作为它的结点并设该结点为n，转，转4。（2）检查中）检查中DAG中是否已有一结点，

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

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

20、图。图。(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演示演示第35页，本讲稿共75页根据根据DAGDAG图重写四元式后得到如下优化的四元式图重写四元式后得到如下优化的四元式序列：序列：(1)T0:=3.14(1)T0:=3.14(2)T1:=6.28(2)T1:=6.28(合并已知量合并已知量)(3)T3:=6.28(3)T3:=6.28(合并已知量合并已知量)(4)T2:=R+r(4)T2:=R+r(5)T4:=T2(5)T4:

21、=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(删除无用代码删除无用代码)第36页，本讲稿共75页【例例】试对以下基本块试对以下基本块B1应用应用DAG进行优化。进行优化。B1:A:=B*CD:=B/CE:=A+DF:=E*2G:=B*CH:=G*GF:=H*GL:=FM:=L并就以下两种情况分别写出优化后的四元式序列：并就以下两种情况分别写出优化后的四元式序列：若某个变量在基本块后不被引用若某个变量

22、在基本块后不被引用,可删除。可删除。第37页，本讲稿共75页（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 Bn2n2n2n2C C C C*A,GA,GA,GA,Gn4n4n4n4/E E E En6n6n6n62 2 2 2n7

23、n7n7n7F F F F*n8n8n8n8H H H H*F,L,MF,L,MF,L,MF,L,MD D D Dn5n5n5n5n9n9n9n9第38页，本讲稿共75页(2)若只有若只有L在基本块后被引用，则优化为：在基本块后被引用，则优化为：G:=B*CH:=G*GL:=H*G第39页，本讲稿共75页11.3 11.3 控制流分析和循环的优化控制流分析和循环的优化定定义义：以以基基本本块块为为结结点点，将将控控制制流流信信息息增增加加到到基基本本块块的的集集合合上上来来表表示示一一个个程程序序而而得得到到的的有有向向图图，称称为为程程序序流图流图。如如果果一一个个结结点点的的基基本本块块入

24、入口口语语句句是是程程序序的的第第一一条语句，则此结点条语句，则此结点为首结点为首结点。如如果果在在某某个个执执行行顺顺序序中中基基本本块块B2紧紧接接在在基基本本块块B1之之后执行，则从后执行，则从B1到到B2有一条有向边。有一条有向边。一、程序流图一、程序流图第40页，本讲稿共75页【例如例如】有下列三地址代码程序，给出程序流程图。有下列三地址代码程序，给出程序流程图。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演示演示第41页，本讲

25、稿共75页【例例】有下列三地址代码程序，给出程序流程图。有下列三地址代码程序，给出程序流程图。(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*I(9)T7:=T5+T6(9)T7:=T5+T6(10)T8:=add(A)-11(10)T8:=add(A)-11(11)T9

26、:=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)演示演示第42页，本讲稿共75页循环是程序流图中具有唯一入口结点的强连通子图。循环是程序流图中具有唯一入口结点的强连通子图。说明：说明：1.1.强连通的强连通的(任意两结点间任意两结点间,必有一条通路必有一条通路,且该且该通路上各结点都属于该结点序列通路上各结点都属于该结点序列)2.2.它们中间有且只有一个是入口结点。它们中间有且只有一个是入口结点。二、循环的查找二、循环的查找第43页，本讲稿共75页必经结

27、点：必经结点：在程序流图中，对任意两个结点在程序流图中，对任意两个结点m m和和n n，若从流图的首结点出发，到达，若从流图的首结点出发，到达n n的任一通的任一通路都要经过路都要经过m m，则称，则称m m是是n n的必经结点，记为的必经结点，记为 m m DOM n,DOM n,流图中结点流图中结点n n的所有必经结点的集合，的所有必经结点的集合，称为结点称为结点n n的必经结点集，记为的必经结点集，记为D(n).D(n).回边：回边：设设n-mn-m是流图中的一条有向边，且是流图中的一条有向边，且m m DOM n,DOM n,则称则称n-mn-m是流图中的一条回边。是流图中的一条回边。

28、第44页，本讲稿共75页【例例】对下面语句划分基对下面语句划分基本块，画出程序流程图本块，画出程序流程图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、划分基本块，画、划分基本块，画程序流程图程序流程图第45页，本讲稿共75页2 2、划分基本块，画程序流程图、划分基本块，画程序流程图1）a:=12)IF a=b goto 4)3)goto 6)4)b:=1 5)

29、goto 7)6)c:=17)d:=a+b;第46页，本讲稿共75页(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【例例】对下面语句划分基本块，画出程序流程图。对下面语句划分基本块，画出程序流程图。第47页，本讲稿共75页第48页，本讲稿共75页【例如例如】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,

30、73第49页，本讲稿共75页下图给出求回边下图给出求回边n-dn-d组成的循环的算法：组成的循环的算法：procedure insen(m)procedure insen(m)；if mif m不属于不属于loop thenloop then begin begin loop:loop:loop Umloop Um；把把m m下推进栈下推进栈stackstack；endend；*主程序主程序*StackStack：空；：空；loop:loop:dd；insert(n)insert(n)；while stack while stack 非空非空 dOdObeginbegin 把把stacksta

31、ck的栈顶元素的栈顶元素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为所求循环。为所求循环。insertinsert为为一一过程。过程。第50页，本讲稿共75页算法的基本思想是：算法的基本思想是：由于要求回边由于要求回边n-dn-d组成的组成的循环，这个循环将以循环，这个循环将以d d为其唯为其唯入口，入口，n n是它的一个是它的一个出口。若出口。若n n不等于不等于d d，则，则n

32、n的所有前驱结点应属于循的所有前驱结点应属于循环。当求出环。当求出n n的所有前驱后，只要它们不是循环入口的所有前驱后，只要它们不是循环入口d d，就应再求出它们的前驱，新求出的所有前驱也应属，就应再求出它们的前驱，新求出的所有前驱也应属于循环。然后再对新求出的所有前驱，重复以上步骤，于循环。然后再对新求出的所有前驱，重复以上步骤，直到所求出的前驱是直到所求出的前驱是d d为止。此时算法结束。为止。此时算法结束。第51页，本讲稿共75页回边回边66循环循环6744,5,6,7422,3,4,5,6,7【例例】673412357612121231第52页，本讲稿共75页四元式序列如下：四元式序列

33、如下：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;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

34、 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+YB3B3A:=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:=ad

35、d(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）T4T3:=T9+1T4T3:=T9+1(13)I:=I+1(13)I:=I+1(14)goto(2)(14)goto(2)(15)(15)第58页，本讲稿共75页划分基本块并划出流程图：划分基本块并划出流程图：（1 1 1 1）I:=1I:=1I:=1I:=1(2)If I 10 goto(

36、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(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+1T4

37、T3:=T9+1(13)I:=I+1(13)I:=I+1(14)goto(2)(14)goto(2)(15)(15)(15)(15)B1B1B1B1B2B2B2B2B3B3B3B3B4B4第59页，本讲稿共75页代码外提后：代码外提后：（1 1）I:=1I:=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(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

38、:=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 (14)goto（2 2）(15)(15)(15)(15)B1B1B1B1B2B2B2B2 B2B2B2B2B3B3B3B3B4B4第60页，本讲稿共75页（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(

39、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+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

40、 B2(14)goto B2(15)(15)(15)(15)B1B1B1B1B2B2B2B2 B2B2B2B2B3B3B3B3B4B4第61页，本讲稿共75页2、强度消弱：指把程序中执行时间较长的运算替换为、强度消弱：指把程序中执行时间较长的运算替换为执行时间较短的运算执行时间较短的运算3、删除归纳变量删除归纳变量第62页，本讲稿共75页再次强度消弱再次强度消弱如果，如果，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)

41、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:=T6+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

42、:=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第63页，本讲稿共75页(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

43、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=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第64页

44、，本讲稿共75页解：解：三地址代码：三地址代码：(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,j的三地址代码，然后求出其中的循环，并进行循环优化。的三地址代码，然后求出其中的循环，并进行循环优化。第65页，本讲稿共75页(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

45、+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(11)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第66页，本讲稿共75页代码外

46、提：代码外提：（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)(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

47、 (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)B1B1B1B1B2B2B2B2 B2B2B2B2B3B3B3B3 B3B3B3B3B4B4B4B4B5B5B5B5B6B6B6B6第67页，本讲稿共75页强度消弱：强度消弱：(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

48、(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:=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(5)T1:=T1+N(5)T1:=T1+N(14)j:=1(14)j:=1(15)goto (3)(15)goto (3

49、)(30)(30)(30)(30)B1B1B1B1B2B2B2B2 B2B2B2B2B3B3B3B3B4B4B4B4B5B5B5B5B6B6B6B6第68页，本讲稿共75页强度消弱强度消弱(1):（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(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 got

50、o(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)I:=I+1(5)(5)T1:=I+N T1:=I+N(14)j:=1(14)j:=1(15)goto (3)(15)goto (3)(30)(30)(30)(30)B1B1B1B1B2B2B2B2 B2B2B2B2B3B3B3B3 B3B3B3B3B4B4B4B4B5B5B5B5B6B6B6B6第69页，本讲稿共75页删除归纳变量：