第11章代码优化ppt课件

《第11章代码优化ppt课件》由会员分享，可在线阅读，更多相关《第11章代码优化ppt课件（75页珍藏版）》请在装配图网上搜索。

1、编编 译译 原原 理理 代码优化代码优化首页首页结束结束教学目的：正确了解代码优化的定义和各教学目的：正确了解代码优化的定义和各种能够的优化概念；掌握用种能够的优化概念；掌握用DAGDAG表示进展部表示进展部分优化的方法、循环优化技术。分优化的方法、循环优化技术。教学重点与难点：教学重点与难点：部分优化；部分优化；DAGDAG的构造与运用、循环优化。的构造与运用、循环优化。学时分配：学时分配：4 4学学时时编编 译译 原原 理理 代码优化代码优化首页首页结束结束本章知识点：本章知识点：部分优化部分优化控制流分析和循环优化控制流分析和循环优化数据流的分析与全局优化数据流的分析与全局优化优化技术简

2、介优化技术简介编 译 原 理 代码优化编译前端编译前端代码优化器代码优化器代码产生代码产生控制流分析控制流分析数据流分析数据流分析代码变换代码变换代码优化器的位置和构造代码优化器的位置和构造首页首页终了终了编 译 原 理 代码优化1 1、优化的概念：、优化的概念：优化的定义优化的定义:对程序进展各种等价变换，对程序进展各种等价变换，使得变换后的代码运转结果与变换前使得变换后的代码运转结果与变换前代码运转结果一样，而运转速度加大，代码运转结果一样，而运转速度加大，或占用存储空间减少，或两者都有。或占用存储空间减少，或两者都有。我们通常称这种变换为优化。我们通常称这种变换为优化。11.1 11.1

3、 优化技术简介优化技术简介首页首页终了终了编 译 原 理 代码优化 优化的目的是为了产生更高效的代码。由优化编优化的目的是为了产生更高效的代码。由优化编译程序提供的对代码的各种变换必需遵照下面的译程序提供的对代码的各种变换必需遵照下面的原那么：原那么：1)1)等价原那么等价原那么 主要指优化后的目的代码运转主要指优化后的目的代码运转时间较短时间较短,以及占用的存储空间较小。以及占用的存储空间较小。2)2)有效原那么有效原那么 使优化后所产生的目的代码运转使优化后所产生的目的代码运转时间确实较短，占用的空间确实较小时间确实较短，占用的空间确实较小 3 3合算原那么合算原那么 应尽能够以较低的代价

4、获得较好应尽能够以较低的代价获得较好的优化效果的优化效果2 2、优化的原那么、优化的原那么首页首页终了终了编 译 原 理 代码优化3、代码优化的根本方法、代码优化的根本方法按照与机器相关的程度，代码优化分为：按照与机器相关的程度，代码优化分为：与机器相关的优化：在生成目的程序时进展与机器相关的优化：在生成目的程序时进展的，它在很大程度上与详细的计算机有关。的，它在很大程度上与详细的计算机有关。与机器无关的优化：在语法、语义分析生成与机器无关的优化：在语法、语义分析生成中间代码之后，在中间代码上进展，这一中间代码之后，在中间代码上进展，这一类优化不依赖于详细的计算机，而取决于类优化不依赖于详细的

5、计算机，而取决于言语的构造。言语的构造。首页首页终了终了编编 译译 原原 理理 代码优化代码优化首页首页结束结束根据优化所涉及的程序范围分成根据优化所涉及的程序范围分成:部分优化：根本块范围内的优化：合并知量部分优化：根本块范围内的优化：合并知量消除公共子表达式，削减计算强度和删消除公共子表达式，削减计算强度和删除无用代码除无用代码循环优化：主要是基于循环的优化，包括循循环优化：主要是基于循环的优化，包括循环不变式外提，归纳变量删除，计算强环不变式外提，归纳变量删除，计算强度削减。度削减。全局优化：主要是在整个程序范围内进展的全局优化：主要是在整个程序范围内进展的优化。优化。由于程序段是非线性

6、的，因此需由于程序段是非线性的，因此需求分析程序的控制流和数据流，处置比求分析程序的控制流和数据流，处置比较复杂。较复杂。编 译 原 理 代码优化4 4、优化技术、优化技术合并常量计算合并常量计算消除公共子表达式消除公共子表达式削减计算强度削减计算强度删除无用代码删除无用代码循环不变表达式外提循环不变表达式外提归纳变量删除归纳变量删除首页首页终了终了演示演示编 译 原 理 代码优化局限于根本块范围内的优化称为根本块内的优化局限于根本块范围内的优化称为根本块内的优化或部分优化或部分优化 。1 1、根本块的定义、根本块的定义 所谓根本块是指程序中一顺序执行的语句序所谓根本块是指程序中一顺序执行的语

7、句序列，其中只需一个入口和一个出口，入口就是其列，其中只需一个入口和一个出口，入口就是其中的第一个语句，出口就是其中的最后一个语中的第一个语句，出口就是其中的最后一个语句。句。11.2 11.2 部分优化部分优化首页首页终了终了编 译 原 理 代码优化划分四元式程序为根本块的算法如下：划分四元式程序为根本块的算法如下：1求出四元式程序中各个根本块的入口求出四元式程序中各个根本块的入口语句，它们可以是下述语句之一：语句，它们可以是下述语句之一：程序的第一个语句；程序的第一个语句；2 2根本块的划分算法根本块的划分算法紧跟在条件转移语句后面的语句。紧跟在条件转移语句后面的语句。能由条件转移语句或无

8、条件转移语句转移到的能由条件转移语句或无条件转移语句转移到的目的语句；目的语句；首页首页终了终了编 译 原 理 代码优化2对以上求出的每一入口语句构造其所属的根对以上求出的每一入口语句构造其所属的根本块。它是由该入口语句到另一入口语句本块。它是由该入口语句到另一入口语句(不包括不包括该入口语句该入口语句)，或到一转移语句，或到一转移语句(包括该转移语句包括该转移语句)，或到一停语句或到一停语句包括该停语句包括该停语句)之间的语句序列组之间的语句序列组成的。成的。3)凡未被纳入某一根本块的语句，都是程序中凡未被纳入某一根本块的语句，都是程序中控制流程无法到达的语句，因此也是不会被执行控制流程无法

9、到达的语句，因此也是不会被执行到的语句，将其删除。到的语句，将其删除。2 2根本块的划分算法根本块的划分算法首页首页终了终了编 译 原 理 代码优化【例如例如】有以下三地址代码程序：有以下三地址代码程序：1read X2read Y3R：=X mod Y4if R=0 goto (8)5)X:=Y6)Y:=R7)goto (3)8write Y9)halt划分为划分为4 4个根本块个根本块:B11B11、2 2 B23)B23)、4 4 B35B35、6 6、7 7 B48B48、9 9 首页首页终了终了编 译 原 理 代码优化【例如例如】划分根本块划分根本块(1)read(C)(1)read

10、(C)(2)A:=0(2)A:=0(3)B:=1(3)B:=1(4)L1:A:=A+B(4)L1:A:=A+B(5)if B=C goto (5)if B=C goto L2L2(6)B:=B+1(6)B:=B+1(7)goto L1(7)goto L1(8)L2:write(A)(8)L2:write(A)(9)halt(9)halt划分为划分为4 4个根本块个根本块:B1B11 1、2 2、3 3 B2B24 4、5 5 B3B3 6 6、7 7 B4B48 8、9 9 首页首页终了终了编 译 原 理 代码优化3 3、根本块的变换、根本块的变换根本块内可进展的优化：根本块内可进展的优化：合

11、并知常量和复写传播合并知常量和复写传播暂时变量改名暂时变量改名交换语句的位置交换语句的位置删除公共子表达式删除公共子表达式删除无用代码删除无用代码首页首页终了终了编 译 原 理 代码优化删除公共子表达式删除公共子表达式 假设一个表达式假设一个表达式E E的值已计算过，并且在此之后的值已计算过，并且在此之后E E中变量的值没有改动，那么称中变量的值没有改动，那么称E E为公共子表达式，为为公共子表达式，为防止反复计算而删除，称为删除公共子表达式防止反复计算而删除，称为删除公共子表达式【例如例如】x:=(a+b)x:=(a+b)*c-(a+b)2c-(a+b)2t1=a+b;t1=a+b;t2=t

12、1t2=t1*c;c;t3=a+b;t3=a+b;t4=t32t4=t32X:=t2-t4;X:=t2-t4;t1=a+b;t1=a+b;t2=t1 t2=t1*c;c;t4=t12t4=t12 X:=t2-t4;X:=t2-t4;变换后变换后首页首页终了终了编 译 原 理 代码优化 x+y*t-a*(x+y*t)/(y*t)(1)(*，y，t，t1)(2)(+，x，t1，t2)(3)(*，y，t，t3)(4)(+，x，t3，t4)(5)(*，a，t4，t5)(6)(*，y，t，t6)(7)(/，t5，t1，t7)(8)(-，t2，t7，t8)消除公共子表达式之后：消除公共子表达式之后：(1)

13、(*，y，t，t1)(2)(+，x，t1，t2)(3)(*，a，t2，t5)(4)(/，t5，t1，t7)(5)(-，t2，t7，t8)【例如例如】前往前往首页首页终了终了编 译 原 理 代码优化删除无用代码删除无用代码 假设某些变量的值在整个程序中不再运用，假设某些变量的值在整个程序中不再运用，那么这些变量的赋值对程序运转结果没有任何作那么这些变量的赋值对程序运转结果没有任何作用，那么就可以删除对这些变量赋值的代码，称用，那么就可以删除对这些变量赋值的代码，称为删除无用代码或删除无用赋值。为删除无用代码或删除无用赋值。【例如例如】假设假设T7T7、T8T8、T6T6在以后的程序中不在以后的程

14、序中不再运用再运用T6:=T2T6:=T2X:=T3X:=T3T7:=T2T7:=T2T8:=T4T8:=T4aT2:=T5aT2:=T5aT4:=T3aT4:=T3变换后变换后aT2:=T5aT2:=T5aT4:=T3aT4:=T3前往前往首页首页终了终了编 译 原 理 代码优化合并知量合并知量a=10 a=10*5+6-5+6-b;b;t0=10;t0=10;t1=5;t1=5;t2=t0 t2=t0*t1;t1;t3=6;t3=6;t4=t2+t3 t4=t2+t3；t5=t4 b;t5=t4 b;a=t5;a=t5;合并后：合并后：t0=56;t1=t0 b;a=t1;首页首页终了终了

15、编 译 原 理 代码优化【例例】d=2*3.14*r(1)(*，2，3.14，t1)(2)(*，t1，r，t2 )(3)(=，t2，d )2*3.14的值在编译时辰就可以确定。的值在编译时辰就可以确定。(1)(*，6.28，r，t2)(2)(=，t2，d )首页首页终了终了前往前往编 译 原 理 代码优化复写传播复写传播 构成为构成为f:=g的赋值叫做复写语句。的赋值叫做复写语句。优化过程中会大量引入复写。优化过程中会大量引入复写。复写传播变换的做法是在复写语句复写传播变换的做法是在复写语句f:=g后，尽能够用后，尽能够用g代表代表f。复写传播变换本身并不是优化，但它给其它优化如常量合并和死代

16、码复写传播变换本身并不是优化，但它给其它优化如常量合并和死代码删除带来时机。删除带来时机。编编 译译 原原 理理 代码优化代码优化首页首页结束结束t2=t1;t3=t2*t1;t4=t3;t5=t3*t2;c=t5+t4;t3=t1*t1;t5=t3*t1;c=t5+t3;【例例】前往前往编编 译译 原原 理理 代码优化代码优化首页首页结束结束重新命名暂时变量例如:t:=b+c u:=b+c前往前往交换语句次序目的：减少暂时变量【例如】相邻两个语句 t1:=b+c t2:=x+y t2:=x+y t1:=b+c编编 译译 原原 理理 代码优化代码优化首页首页结束结束根本块优化的实现根本块优化的

17、实现 从四元式序列构造从四元式序列构造DAG DAG，然后再从，然后再从DAGDAG重写四元式。重写四元式。4 4、根本块的有向图、根本块的有向图DAGDAG表示表示根本块内部优化实现的主要工具为：根本块内部优化实现的主要工具为：DAG(Directed Acyclic GraphDAG(Directed Acyclic Graph的缩写的缩写)DAG:DAG:假设有向图中任一通路都不是环路假设有向图中任一通路都不是环路,那么那么称该有向图为无环路有向图，也称有向非循环图称该有向图为无环路有向图，也称有向非循环图,简称简称DAGDAG。用用DAGDAG图表示各个值的计算图表示各个值的计算/依赖

18、关系。依赖关系。演示演示编编 译译 原原 理理 代码优化代码优化首页首页结束结束前往前往编 译 原 理 代码优化DAG图中结点的特点图中结点的特点1.叶结点叶结点 标志标志:标识符名标识符名(变量名变量名)或常数或常数,写在结点写在结点下面。下面。代表代表:该结点代表该变量或常数的值。该结点代表该变量或常数的值。地址的表示：地址的表示：Addr(A)通常将其标识符加上下标通常将其标识符加上下标0,表示该变量的表示该变量的初值。初值。2.2.内部结点内部结点 标志标志:一个运算符号，写在结点下面。一个运算符号，写在结点下面。代表代表:利用后续结点运算出来的值。利用后续结点运算出来的值。3 3图中

19、各个结点能够附加一个或多个标识符图中各个结点能够附加一个或多个标识符,表示这些标表示这些标识符具有该结点所代表的值，同一个结点的标识符表示一识符具有该结点所代表的值，同一个结点的标识符表示一样的值，写在结点右面。样的值，写在结点右面。编编 译译 原原 理理 代码优化代码优化首页首页结束结束四元式相应的四元式相应的DAGDAG1A：=op B 1型型编编 译译 原原 理理 代码优化代码优化首页首页结束结束编 译 原 理 代码优化该算法只对如下三种四元式构造该算法只对如下三种四元式构造DAGDAG：0 0型型 A:=BA:=B l l型型 A:=op BA:=op B 2 2型型 A:=B op

20、CA:=B op C op op是双目运算符还可以是是双目运算符还可以是=或或=。根本块的根本块的DAGDAG构造算法构造算法编 译 原 理 代码优化输入：一个根本块输入：一个根本块输出：相应输出：相应DAG图图算法阐明：算法阐明：经过逐个扫描四元式来逐渐建立经过逐个扫描四元式来逐渐建立DAG图。图。函数函数node(A)的值或者是一个结点的编号的值或者是一个结点的编号n或者无或者无定义。假设是前一种情况，代表存在一个结点定义。假设是前一种情况，代表存在一个结点n，A是其上的标志或附加标识符。是其上的标志或附加标识符。根本块的根本块的DAGDAG构造算法构造算法编编 译译 原原 理理 代码优化

21、代码优化首页首页结束结束首先首先DAGDAG为空。为空。对根本块的每一四元式，依次执行：对根本块的每一四元式，依次执行：1 1假设假设NODENODEB B无定义，那么构造一标志为无定义，那么构造一标志为B B的叶的叶结点并定义结点并定义NODENODEB B为这个结点；为这个结点；假设当前四元式是假设当前四元式是0 0型，那么记型，那么记NODE(B)NODE(B)的值为的值为n n，转，转4 4。假设当前四元式是假设当前四元式是1 1型，那么转型，那么转2.(1)2.(1)。假设当前四元式是假设当前四元式是2 2型，那么：型，那么：(I)(I)假设假设NODE(C)NODE(C)无无定义，

22、那么构造一标志为定义，那么构造一标志为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)都是标志为常数都是标志为常数的叶结点，那么转的叶结点，那么转2.4，否那么转，否那么转3.2。3执行执行op B即合并知量即合并知量，令得到的新常，令得到的新常数为数为P。假设。假设NODE(B)是处置当前四元式时新构是处置当前四元式

23、时新构造出来的结点，那么删除它。假设造出来的结点，那么删除它。假设NODE(P)无无定义，那么构造一用定义，那么构造一用P做标志的叶结点做标志的叶结点n。置。置NODE(P)=n，转，转4。4执行执行B op C即合并知量即合并知量，令得到的新，令得到的新常数为常数为P。假设。假设NODE(B)或或NODE(C)是处置当是处置当前四元式时新构造出来的结点，那么删除它。假前四元式时新构造出来的结点，那么删除它。假设设NODE(P)无定义，那么构造一用无定义，那么构造一用P做标志的叶做标志的叶结点结点n。置。置NODE(P)=n，转，转4。根本块的根本块的DAGDAG构造算法构造算法编 译 原 理

24、 代码优化根本块的根本块的DAGDAG构造算法构造算法 3找公共子表达式找公共子表达式1检查检查DAG中能否已有一结点，其独一后继为中能否已有一结点，其独一后继为NODE(B)，且标志为，且标志为op即找公共子表达式即找公共子表达式。假。假设没有，那么构造该结点设没有，那么构造该结点n，否那么就把已有的结点，否那么就把已有的结点作为它的结点并设该结点为作为它的结点并设该结点为n，转，转4。2检查中检查中DAG中能否已有一结点，其左后继为中能否已有一结点，其左后继为NODE(B)，其右后继为，其右后继为NODE(C)，且标志为，且标志为op即即找公共子表达式找公共子表达式。假设没有，那么构造该结

25、点。假设没有，那么构造该结点n，否那么就把已有的结点作为它的结点并设该结点为否那么就把已有的结点作为它的结点并设该结点为n，转转4。编编 译译 原原 理理 代码优化代码优化首页首页结束结束4.4.删除无用赋值语句删除无用赋值语句假设假设NODE(A)NODE(A)无定义，那么把无定义，那么把A A附加在结点附加在结点n n上上并令并令NODE(A)=nNODE(A)=n；否那么先把；否那么先把A A从从NODE(A)NODE(A)结点结点上附加标识符集中删除上附加标识符集中删除留意，假设留意，假设NODE(A)NODE(A)是叶结点，那么其标志是叶结点，那么其标志A A不删除不删除，把，把A

26、A附加附加到新结点到新结点n n上并令上并令NODE(A)=nNODE(A)=n。转处置下一四。转处置下一四元式。元式。编编 译译 原原 理理 代码优化代码优化首页首页结束结束仅含仅含0,1,20,1,2型四元式的根本块的型四元式的根本块的DAGDAG构造算法构造算法:首先：假定首先：假定DAGDAG为空，即没有任何结点。对根本块中的每为空，即没有任何结点。对根本块中的每一四元式依次执行：一四元式依次执行：编编 译译 原原 理理 代码优化代码优化首页首页结束结束【例例】构造以下四元式序列的构造以下四元式序列的DAG图。图。(1)T0:=3.14(2)T1:=2*T0(3)T2:=R+r(4)A

27、:=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)T3:=6.28(合并知量合并知量)(4)T2:=R+r(4)T2:=R+r(5)T4:=T2(5)T4:=T2(删除公共子表删除公共子表达式达式)(6)A:=6.28(6)A:=6.28*T2

28、T2(7)T5:=A(7)T5:=A(删除公共子表删除公共子表达式达式)(8)T6:=R-r(8)T6:=R-r(9)B:=A(9)B:=A*T6(T6(删除无用代码删除无用代码)编 译 原 理 代码优化【例例】试对以下根本块试对以下根本块B1运用运用DAG进展优化。进展优化。B1:A:=B*C D:=B/C E:=A+D F:=E*2 G:=B*C H:=G*G F:=H*G L:=F M:=L 并就以下两种情况分别写出优化后的四元式序列：并就以下两种情况分别写出优化后的四元式序列：假设某个变量在根本块后不被援用假设某个变量在根本块后不被援用,可删除。可删除。编 译 原 理 代码优化1假设假

29、设G、L、M在根本块后面被援用；在根本块后面被援用；2假设只需假设只需L在根本块后被援用。在根本块后被援用。解：对于解：对于B1其其DAG图：图：(1)(1)假设只需假设只需G G、L L、M M在根本块后被援用，那么优化为：在根本块后被援用，那么优化为：G:=BG:=B*C C H:=G H:=G*G G L:=H L:=H*G G M:=L M:=L编 译 原 理 代码优化(2)假设只需假设只需L在根本块后被援用，那么优化为：在根本块后被援用，那么优化为：G:=B*C H:=G*G L:=H*G编 译 原 理 代码优化11.3 11.3 控制流分析和循环的优化控制流分析和循环的优化 定义：

30、以根本块为结点，将控制流信息添加到定义：以根本块为结点，将控制流信息添加到根本块的集合上来表示一个程序而得到的有向图根本块的集合上来表示一个程序而得到的有向图，称为程序流图。，称为程序流图。假设一个结点的根本块入口语句是程序的第假设一个结点的根本块入口语句是程序的第一条语句，那么此结点为首结点。一条语句，那么此结点为首结点。假设在某个执行顺序中根本块假设在某个执行顺序中根本块B2紧接在根本紧接在根本块块B1之后执行，那么从之后执行，那么从B1到到B2有一条有向边。有一条有向边。一、程序流图一、程序流图编编 译译 原原 理理 代码优化代码优化首页首页结束结束【例如例如】有以下三地址代码程序，给出

31、程序流有以下三地址代码程序，给出程序流程图。程图。1read X2read Y3R：=X mod Y4if R=0 goto (8)5)X:=Y6)Y:=R7)goto (3)8write Y9)halt演示演示编编 译译 原原 理理 代码优化代码优化首页首页结束结束【例例】有以下三地址代码程序，给出程序流程图。有以下三地址代码程序，给出程序流程图。(1(1I:=1I:=1(2)if I 10 goto(15)(2)if I 10 goto(15)(3)T1:=2(3)T1:=2*J J(4)T2:=10(4)T2:=10*I I(5)T3:=T2+T1(5)T3:=T2+T1(6)T4:=a

32、dd(A)11(6)T4:=add(A)11(7)T5:=2(7)T5:=2*J J(8)T6:=10(8)T6:=10*I 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(12T4T3:=T9+1T4T3:=T9+1(13)I:=I+1(13)I:=I+1(14)goto(2)(14)goto(2)(15)(15)演示演示编 译 原 理 代码优化循环是程序流图中具有独一入口结点的强连通子循环是程序流图中具有独一入口结点的强连通子图。图。阐明：阐明：1.1.强连通的强连

33、通的(恣意两结点间恣意两结点间,必有一条通路必有一条通路,且该通路上各结点都属于该结点序列且该通路上各结点都属于该结点序列)2.2.它们中间有且只需一个是入口结点。它们中间有且只需一个是入口结点。二、循环的查找二、循环的查找编编 译译 原原 理理 代码优化代码优化首页首页结束结束必经结点：在程序流图中，对恣意两个结必经结点：在程序流图中，对恣意两个结点点m m和和n n，假设从流图的首结点出发，到达，假设从流图的首结点出发，到达n n的任一通路都要经过的任一通路都要经过m m，那么称，那么称m m是是n n的必经的必经结点，记为结点，记为 m DOM n,m DOM n,流图中结点流图中结点n

34、 n的一切的一切必经结点的集合，称为结点必经结点的集合，称为结点n n的必经结点集，的必经结点集，记为记为D(n).D(n).回边：设回边：设n-mn-m是流图中的一条有向边，且是流图中的一条有向边，且m m DOM n,DOM n,那么称那么称n-mn-m是流图中的一条回边。是流图中的一条回边。编 译 原 理 代码优化【例例】对下面语句划对下面语句划分根本块，画出程分根本块，画出程序流程图序流程图a:=1;a:=1;if a=b thenif a=b then b:=1 b:=1 else else c:=1 c:=1endif;endif;d:=a+bd:=a+b1 1、翻译的四元式是：、

35、翻译的四元式是：1 1a:=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 1、翻译为四元式、翻译为四元式2 2、划分根本块，画、划分根本块，画程序流程图程序流程图编编 译译 原原 理理 代码优化代码优化首页首页结束结束2 2、划分根本块，画程序流程图、划分根本块，画程序流程图1 1a:=1a:=12)IF a=b goto 4)2)IF a=b goto 4)3)goto 6)3)goto 6

36、)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【例例】对下面语句划分根本块，画出程序流程图。对下面语句划分根本块，画出程序流程图。编 译 原 理 代码优化划分成四个基本块划分成四个基本块 B1，B2，B3，B4 B1 (1)(2)(3)基本块内实行的优化基本块内实行的优化:合并已知量合并已知量 删除多余运算删除多余运

37、算 B2 (4)删除无用赋值删除无用赋值 (5)B3 (6)(7)B4 (8)(9)编 译 原 理 代码优化【例如例如】6 73 4 1 2 3 5 7 6 1 2 1 2 1 2 1必经结点必经结点 必经结点集必经结点集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,7 3编 译 原 理 代码优化以下图给出求回边以下图给出求回边n-dn-d组成的循环的算法：组成的循环的算法：procedure insen(m)procedure insen(m)；if mif m不属于不属于loop thenloop

38、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 把把stackstack的栈顶元素的栈顶元素m m上托出去上托出去 for p P(m)dOfor p P(m)dO insert(p)insert(p)end end 其中其中P(m)P(m)表示结点表示结点m m的前的前驱结点集，驱结点集，stack

39、stack为任务为任务栈，栈，looploop为所求循环。为所求循环。insertinsert为一为一过程。过程。编编 译译 原原 理理 代码优化代码优化首页首页结束结束算法的根本思想是：由于要求回边算法的根本思想是：由于要求回边n-dn-d组成的循环，这个循环将以组成的循环，这个循环将以d d为为其唯其唯入口，入口，n n是它的一个出口。假是它的一个出口。假设设n n不等于不等于d d，那么，那么n n的一切前驱结点的一切前驱结点应属于循环。当求出应属于循环。当求出n n的一切前驱后，的一切前驱后，只需它们不是循环入口只需它们不是循环入口d d，就应再求，就应再求出它们的前驱，新求出的一切前

40、驱出它们的前驱，新求出的一切前驱也应属于循环。然后再对新求出的也应属于循环。然后再对新求出的一切前驱，反复以上步骤，直到所一切前驱，反复以上步骤，直到所求出的前驱是求出的前驱是d d为止。此时算法终了。为止。此时算法终了。编 译 原 理 代码优化回边回边 6 6循环循环 6 7 4 4,5,6,7 4 2 2,3,4,5,6,7【例例】6 73 4 1 2 3 5 7 6 1 2 1 2 1 2 3 1编 译 原 理 代码优化四元式序列如下：四元式序列如下：1 1J J：=0;=0;2)L1:I=0;2)L1:I=0;3)IF I8 goto L33)IF I8 goto L34)L2:A:=

41、B+C4)L2:A:=B+C5)B:=D5)B:=D*C 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 goto B4IF AB goto B4B1B1I:=2I:=2B:=I+YB:=I+YB3B3A:=A+1A:=A+1J:=M+NJ:=M+N

42、Y:=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(3)T1:=2*J J(4)T2:=10(4)T2:=10*I I(5)T3:=T2+T1(5)T3:=T2+T1(6)T4:=add(A)11(6)T4:=add(A)11(7)T5:=2(7)T5:=2*J J(8)T6:=10(8)T6:=10*I I(9)T7:=T5

43、+T6(9)T7:=T5+T6(10)T8:=add(A)-11(10)T8:=add(A)-11(11)T9:=T8T7(11)T9:=T8T7(12(12T4T3:=T9+1T4T3:=T9+1(13)I:=I+1(13)I:=I+1(14)goto(2)(14)goto(2)(15)(15)编 译 原 理 代码优化 划分根本块并划出流程图：划分根本块并划出流程图：(3)T1:=2(3)T1:=2*J J(4)T2:=10(4)T2:=10*I I(5)T3:=T2+T1(5)T3:=T2+T1(6)T4:=add(A)11(6)T4:=add(A)11(7)T5:=2(7)T5:=2*J

44、 J(8)T6:=10(8)T6:=10*I 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(12T4T3:=T9+1T4T3:=T9+1(13)I:=I+1(13)I:=I+1(14)goto(2)(14)goto(2)B4B4编 译 原 理 代码优化 代码外提后：代码外提后：1 1 I:=1 I:=1(3)T1:=2(3)T1:=2*J J(6)T4:=add(A)11(6)T4:=add(A)11(7)T5:=2(7)T5:=2*J J(8)T8:=add(A)-

45、11(8)T8:=add(A)-11(2)if I 10 goto(15)(2)if I 10 goto(15)(4)T2:=10(4)T2:=10*I I(5)T3:=T2+T1(5)T3:=T2+T1(8)T6:=10 (8)T6:=10*I 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 2B4B4编 译 原 理 代码优化1 1 I I：=1=1(3)T1:=2(3)T1:=2*J J(6)T4:=add

46、(A)(6)T4:=add(A)1111(7)T5:=2 (7)T5:=2*J J(10)T8:=add(A)-11(10)T8:=add(A)-11(4)T2:=10 (4)T2:=10*I I(8)T6:=10 (8)T6:=10*I 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(11T9:=T8T7T9:=T8T7(12)T4T3:=T9+1(12)T4T3:=T9+1(13)I:=I+1(13)I:=I+1(4)T2:=T2+10(4)T2:=T2+1

47、0(8)T6:=T6+10(8)T6:=T6+10(14)goto B2(14)goto B2B4B4编 译 原 理 代码优化2、强度消弱：指把程序中执行时间较长的运算、强度消弱：指把程序中执行时间较长的运算交换为执行时间较短的运算交换为执行时间较短的运算 3、删除归纳变量、删除归纳变量编 译 原 理 代码优化再次强度消弱再次强度消弱 假设，假设，T2,T6出出循环后不是活动循环后不是活动变量，那么可在变量，那么可在循环后删除。循环后删除。(3)T1:=2(3)T1:=2*J J(6)T4:=add(A)-11(6)T4:=add(A)-11(7)T5:=2(7)T5:=2*J J(10)T8

48、:=add(A)-11(10)T8:=add(A)-11(4)T2:=10(4)T2:=10*I I(8)T6:=10(8)T6:=10*I 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)T2:=T2+10(4)T2:=T2+10(8)T6:=T6+10(8)T6:=T6+10(5)T3:=T3+10(5)T3:=T3+

49、10(9)T7:=T7+10(9)T7:=T7+10(14)goto B2(14)goto B2编 译 原 理 代码优化 (2)if T3R goto(15)(2)if T3R goto(15)(3)T1:=2(3)T1:=2*J J(6)T4:add(A)11(6)T4:add(A)11(7)T5:=2(7)T5:=2*J J(10)T8:=add(A)11(10)T8:=add(A)11(4)T2:=10(4)T2:=10*I I(8)T6:=10(8)T6:=10*I I(5)T3:=T2+T1(5)T3:=T2+T1(9)T7:=T6+T5(9)T7:=T6+T5(2)R=100+T1

50、(2)R=100+T1(11)T9:=T8T7(11)T9:=T8T7(12)T4T3:=T9+1(12)T4T3:=T9+1(5)T3:=T3+10(5)T3:=T3+10(9)T7:=T7+10(9)T7:=T7+10(14)Goto B2(14)Goto B2编 译 原 理 代码优化解：解：三地址代码：三地址代码：例例3 试写出以下程序段试写出以下程序段 for I:=1 to M do for j:=1 to N do AI,j :=BI,j 的三地址代码，然后求出其中的循环，并进展循环优化。的三地址代码，然后求出其中的循环，并进展循环优化。编 译 原 理 代码优化 (3)If IM

51、goto(30)(3)If IM goto(30)(4)If jN goto(13)(4)If jN goto(13)(5)T1:=I(5)T1:=I*N 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(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)got

52、o (3)(15)goto (3)编 译 原 理 代码优化代码外提：代码外提：1 1I:=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(5)T1:=I*N 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

53、(11)j:=j+1(12)goto (4)(12)goto (4)(30)(30)编 译 原 理 代码优化强度消弱：强度消弱：I:=1I:=1j:=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)T1:=I(5)T1:=I*N 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

54、:=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)编 译 原 理 代码优化强度消弱强度消弱(1):1 1I:=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)T1:=I(5)T1:=I*N N(3)If IM goto (

55、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)T2:=T2+1(6)T2:=T2+1(12)goto (4)(12)goto (4)(13)I:=I+1(13)I:=I+1(5)T1:=I+N(5)T1:=I+N(14)j:=1(14)j:=1(15)goto (3)(15)goto (3)编 译 原 理 代码优化 删除归纳变量：删除归纳变量：I:=1I:=1j:=1j:=1(7)T

56、3:=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)T1:=I(5)T1:=I*N N(3)R:=M(3)R:=M*N N(3)If T1 R goto(30)(3)If T1 R goto(30)(4)Q:=T1+N(4)Q:=T1+N(4)If T2 Q goto (13)(4)If T2 Q goto (13)(10)T4T2:=T5T2(10)T4T2:=T5T2(11)T2:=T2+1(11)T2:=T2+1(12)goto (4)(12)goto (4)(13)T1:=T1+1

57、(13)T1:=T1+1(14)T2:=T1+1(14)T2:=T1+1(15)goto (3)(15)goto (3)编 译 原 理 代码优化例例3给出下面循环语句的流图并进展优化：给出下面循环语句的流图并进展优化：语句：语句：for I:=1 to 10 do AI,J*5:=J+2 其中其中 A 为为10X10二维数组二维数组 解解:1 1I:=1I:=1(2)If I10 goto(11)(2)If I10 goto(11)(3)T1:=J(3)T1:=J*5 5(4)T2:=I(4)T2:=I*1010(5)T3:=T1+T2(5)T3:=T1+T2(6(6T4:=add(A)-11

58、T4:=add(A)-11(7)T5:=J+2(7)T5:=J+2(8)T4T3:=T5(8)T4T3:=T5(9)I:=I+1(9)I:=I+1(10)goto B2(10)goto B2编 译 原 理 代码优化代码外提：代码外提：(3(3T1:=JT1:=J*5 5(6)T4:=add(A)11(6)T4:=add(A)11(7)T5:=J+2(7)T5:=J+2(2)If I10 goto(11)(2)If I10 goto(11)(4)T2:=I(4)T2:=I*10 10(5)T3:=T1+T2(5)T3:=T1+T2(8)T4T3(8)T4T3：=T5=T5(9)I:=I+1(9)

59、I:=I+1(10)goto B2(10)goto B2编 译 原 理 代码优化 强度消弱：强度消弱：1 1 I:=1 I:=1(3)T1:=J(3)T1:=J*5 5(6(6T4:=Add(A)11T4:=Add(A)11(7)T5:=J+2(7)T5:=J+2(4)T2:=I(4)T2:=I*10 10(5)T3:=T1+T2(5)T3:=T1+T2(2)If I10 goto(11)(2)If I10 goto(11)(8)T4T3:=T5(8)T4T3:=T5(9)I:=I+1(9)I:=I+1(4)T2:=T2+10(4)T2:=T2+10(5)T3:=T3+10(5)T3:=T3+

60、10(10)goto B2(10)goto B2编 译 原 理 代码优化 删除归纳变量：删除归纳变量：(1)I:=1(1)I:=1(3)T1:=J(3)T1:=J*5 5(6)T4:=Add(A)11(6)T4:=Add(A)11(7)T5:=J+2(7)T5:=J+2(4)T2:=I(4)T2:=I*10 10(5)T3:=T1+T2(5)T3:=T1+T2(2)R:=T1+100(2)R:=T1+100(2)If T3 R goto(11)(2)If T3 R goto(11)(8)T4T3:=T5(8)T4T3:=T5(5)T3:=T3+10(5)T3:=T3+10(10)goto B2(10)goto B2编编 译译 原原 理理 代码优化代码优化首页首页结束结束作 业P272 4P272 4、6 62 2、7 7