编译原理代码优化.ppt

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

1、第八章第八章 代码优化代码优化8.1 什么是代码优化什么是代码优化8.2 局部优化局部优化8.3 循环优化循环优化8.4 数据流分析数据流分析第八章第八章 优化优化8.1 8.1 什么是代码优化什么是代码优化n1、优化：、优化：对程序进行各种等价变换，使变换后的程序能生成更有效的目标代码。优化可在编译的任何阶段进行，但最主要的一类优化是对中间代码进行优化。n2、常见的优化方式、常见的优化方式 删除多余运算（又称删除公共子表达式）代码外提：循环体中不变的运算提到循环体外 强度削弱：把乘法变成加法1/4/20232中南大学软件学院 陈志刚第八章第八章 优化优化 变换循环控制条件：目的是删除那些纯粹

2、为控制循环而设立的语句，因此又称删除归纳变量。合并已知量：对于那些编译时便可静态确定的运算结果事先运算出来，不必等到运行程序时再执行。复写传播：某些变量的值并未被改变，便赋给其他变量，则可直接引用原值本身。删除无用赋值：有些变量在赋值后并未引用，却又被重新赋值了，称为无用赋值（前面的赋值）1/4/20233中南大学软件学院 陈志刚第八章第八章 优化优化3、优化分类、优化分类n按阶段分:与机器无关的优化-对中间代码进行 依赖于机器的优化-对目标代码进行n根据优化所涉及的程序范围分成:(1)局部优化:在程序基本块内进行的优化。(2)循环优化:在程序循环体内进行的优化。(3)全局优化:在整个程序范围

3、内进行的优化。n优化工作 数据流分析(control-flow analysis)控制流分析(data-flow analysis)变换(transformations)1/4/20234中南大学软件学院 陈志刚第八章第八章 优化优化4、优化技术简介、优化技术简介 1.删除多余运算 2.循环不变代码外提 3.强度削弱 4.变换循环控制条件 5.合并已知量与复写传播 6.删除无用赋值例：例：P:=0 for I:=1 to 20 do P:=P+AI*BI1/4/20235中南大学软件学院 陈志刚第八章第八章 优化优化(1)P:=0(2)I:=1(3)T1:=4*I(4)T2:=addr(A)-

4、4(5)T3:=T2T1(6)T4:=4*I(7)T5:=addr(B)-4(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)if I=20 goto(3)(1)P:=0(2)I:=1(3)T1:=4*I(5)T3:=T2T1(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)if I=20 goto(3)(4)T2:=addr(A)-4(7)T5:=addr(B)-4(6)T4:=T11/4/20236中南大学软件学院 陈志刚第八章第八章 优化优化(1)P:=0(2)I:=1(4)T2:=addr(A)

5、-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)if I=20 goto(3)n(1)P:=0n(2)I:=1n(4)T2:=addr(A)-4n(7)T5:=addr(B)-4n(5)T3:=T2T1n(6)T4:=T1n(8)T6:=T5T4n(9)T7:=T3*T6n(10)P:=P+T7n(11)I:=I+1n(12)if I=20 goto(5)(3)T1:=4*I(3)T1:=T1+41/4/20237中南大学软件学院 陈志刚第八章第八章

6、优化优化(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)if I=20 goto(5)(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(5)T3:=T2T1(6)T4:=T1(8)T6:=T5 (9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3)T1:=T1+4(12)if =80 goto(5)(3)T1:=4

7、T1T11/4/20238中南大学软件学院 陈志刚第八章第八章 优化优化(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T1(9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3)T1:=T1+4(12)if T1=80 goto(5)(1)P:=0(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4(5)T3:=T2T1(8)T6:=T5T1(9)T7:=T3*T6(10)P:=P+T7(3)T1:=T1+4(12)if T1=C

8、goto L2 (6)B:=B+1 (7)goto L1 (8)L2:write(A)(9)halt1/4/202312中南大学软件学院 陈志刚第八章第八章 优化优化1/4/202313中南大学软件学院 陈志刚第八章第八章 优化优化基本块的基本块的DAG表示及其应用表示及其应用DAG Directed Acyclic Graph 无环路有向图无环路有向图基本块的基本块的DAG是在结点上带有标记的是在结点上带有标记的DAG 叶结点叶结点 独特的标识符独特的标识符(名字名字,常数常数)标记标记 内部结点内部结点 运算符号标记运算符号标记 各个结点各个结点 附加标识符标记附加标识符标记1/4/202

9、314中南大学软件学院 陈志刚第八章第八章 优化优化用用DAG进行基本块的优化进行基本块的优化四元式四元式DAG结点结点0型：型：A:=B(:=,B,A)n1 A B1型型:A:=op B(op,B,A)n2 A op n1 B2型型:A:=B op C(op,B,C,A)n3 Aop n1 n2B Cn1n2n1n3n1n21/4/202315中南大学软件学院 陈志刚第八章第八章 优化优化1/4/202316中南大学软件学院 陈志刚第八章第八章 优化优化1/4/202317中南大学软件学院 陈志刚第八章第八章 优化优化1/4/202318中南大学软件学院 陈志刚第八章第八章 优化优化例：例：

10、1/4/202319中南大学软件学院 陈志刚第八章第八章 优化优化1/4/202320中南大学软件学院 陈志刚第八章第八章 优化优化1/4/202321中南大学软件学院 陈志刚第八章第八章 优化优化1/4/202322中南大学软件学院 陈志刚第八章第八章 优化优化1/4/202323中南大学软件学院 陈志刚第八章第八章 优化优化1/4/202324中南大学软件学院 陈志刚第八章第八章 优化优化1/4/202325中南大学软件学院 陈志刚第八章第八章 优化优化1/4/202326中南大学软件学院 陈志刚第八章第八章 优化优化1/4/202327中南大学软件学院 陈志刚第八章第八章 优化优化1/4

11、/202328中南大学软件学院 陈志刚第八章第八章 优化优化控制流程图控制流程图（流图）：具有唯一首结点的有向图（流图）：具有唯一首结点的有向图G=（N，E，n0）N：结点集：结点集 基本块集基本块集 E：有向边集：有向边集 n0：首结点：首结点 包含程序第一个包含程序第一个 语句的基本块语句的基本块8.3 循环优化1/4/202329中南大学软件学院 陈志刚第八章第八章 优化优化1/4/202330中南大学软件学院 陈志刚第八章第八章 优化优化1/4/202331中南大学软件学院 陈志刚第八章第八章 优化优化1/4/202332中南大学软件学院 陈志刚第八章第八章 优化优化1/4/20233

12、3中南大学软件学院 陈志刚第八章第八章 优化优化分析程序流图中结点间的关系分析程序流图中结点间的关系m DOM n 定义 在程序流图中在程序流图中,对任意两个结点对任意两个结点m和和n,如果从流图的首结点出发如果从流图的首结点出发,到达到达n的任意通路都的任意通路都要经过要经过m,则称则称m是是n的必经结点的必经结点,记为记为m DOM n (a,a MOD a)必经结点必经结点集集 定义 结点结点n的所有的所有必经结点必经结点的集合的集合,称为结点称为结点n的的必经结点集必经结点集,记为记为D(n).1/4/202334中南大学软件学院 陈志刚第八章第八章 优化优化例例:6 73 4 1 2

13、 3 5 7 6 1 2 1 2 1 2 1必经结点必经结点 必经结点集必经结点集D(1)=1D(2)=1,2D(3)=1,2,3D(4)=1,2,4D(5)=1,2,4,5D(6)=1,2,4,6D(7)=1,2,4,7 31/4/202335中南大学软件学院 陈志刚第八章第八章 优化优化循环的查找循环的查找循环的查找算法循环的查找算法回边：假设回边：假设 ab是流图中的一条有向边，如果是流图中的一条有向边，如果b DOM a，则，则称称 a b是流图中的一条回边。是流图中的一条回边。有向边有向边 ndnd是回边，组成的循环是由结点是回边，组成的循环是由结点d，结点，结点 n以及有以及有通路

14、到达通路到达 n而该通路不经过而该通路不经过 d的所有结点组成，并且的所有结点组成，并且d是该循是该循环的唯一入口结点。环的唯一入口结点。循环循环(结点序列的性质结点序列的性质)1.1.强连通的强连通的(任意两结点间任意两结点间,必有一条通路必有一条通路,且该通路上各且该通路上各结点都属于该结点序列结点都属于该结点序列)2.2.它们中间有且只有一个是入口结点它们中间有且只有一个是入口结点.1/4/202336中南大学软件学院 陈志刚第八章第八章 优化优化 8.4 数据流分析数据流分析1.活跃变量数据流方程活跃变量数据流方程2.到达到达-定值数据流方程定值数据流方程3.讨论讨论 数据流问题分类数

15、据流问题分类 路径路径 数据流方程解不唯一数据流方程解不唯一1/4/202337中南大学软件学院 陈志刚第八章第八章 优化优化活跃变量的数据流分析活跃变量的数据流分析所所谓谓活活跃跃变变量量就就是是它它的的当当前前值值还还将将被被引引用用（在在赋赋予予一一个个新新值值之之前前）。在在全全局局范范围围来来分分析析的的话话，一一个个变变量量是是活活跃跃的的，如如果果存存在在一一条条路路径径使使得得该该变变量量被被重重新新定定值值之之前它的当前值还要被引用。前它的当前值还要被引用。通通过过全全局局活活跃跃变变量量分分析析，识识别别出出其其当当前前值值不不再再活活跃跃（即即，它它的的值值已已经经死死了

16、了）的的那那些些变变量量。死死变变量量的的值值在在基基本本块块的的出出口口处处不需要保存。不需要保存。1/4/202338中南大学软件学院 陈志刚第八章第八章 优化优化令令B为一个基本块，为一个基本块，定义定义LiveIn(B)为在基本块为在基本块B入口处为活跃的变量的集合。入口处为活跃的变量的集合。定定义义LiveOut(B)为为基基本本块块B的的出出口口处处的的活活跃跃变变量量的的集集合合。LiveIn和和LiveOut并并不不是是相相互互独独立立的的，令令S（B）为为流流图图中中基基本本块块B的的后后继的集合，则有继的集合，则有 LiveOut(B)=LiveIn(i)i s(B)如果基

17、本块没有后继，则其如果基本块没有后继，则其LiveOut为空为空令令LiveUse(B)为为B中中被被定定值值之之前前要要引引用用变变量量的的集集合合。这这个个集集合合由由基基本本块块B中中的的语语句句唯唯一一确确定定。容容易易看看出出，如如果果v LiveUse(B)，则则v LiveIn(B)；即即LiveIn(B)LiveUse(B)。令令Def(B)为为在在B中中定定值值的的变变量量集集合合。如如果果一一个个变变量量在在基基本本块块B的的出出口口处处为为活活跃跃的的且且v Def(B)，则则它它在在B的的入入口口处处也也是是活活跃跃的的，即即：LiveIn(B)LiveOut(B)-D

18、ef(B)因此有：因此有：LiveIn(B)=LiveUse(B)(LiveOut(B)-Def(B)即即：一一个个变变量量在在基基本本块块入入口口处处为为活活跃跃的的，则则一一定定有有：或或者者它它在在基基本本块块的的LiveUse集集中中，或或者者它它在在基基本本块块的的出出口口处处为为活活跃跃的的且且在在基基本本块中没有重新定值块中没有重新定值 1/4/202339中南大学软件学院 陈志刚第八章第八章 优化优化a:=1;if a=b then b:=1 else c:=1endif;d:=a+ba:=1if a=b goto B2b:=1c:=1d:=a+bB1B2B3B41/4/202

19、340中南大学软件学院 陈志刚第八章第八章 优化优化提取提取Def和和LiveUse集合集合基本基本块块DefLiveUseB1abB2bB3cB4da,ba:=1if a=b goto B2b:=1c:=1d:=a+bB1B2B3B41/4/202341中南大学软件学院 陈志刚第八章第八章 优化优化从最后一个基本块开始由后往前计算，可以得到一定的解从最后一个基本块开始由后往前计算，可以得到一定的解 LiveIn(B)=LiveUse(B)(LiveOut(B)-Def(B)LiveOut(B)=LiveIn(i)i s(B)LiveOut(B4)=，因，因此：此：LiveIn(B4)=Liv

20、eUse(B4)=a,b-d现在现在LiveOut(B2)=LiveIn(B4)=a,b-dLiveOut(B3)=LiveIn(B4)=a,b-dLiveIn(B2)=LiveOut(B2)-Def(B2)=a,b-b-d=a-dLiveIn(B3)=LiveOut(B3)-Def(B3)=a,b c-d=a,b c-dLiveOut(B1)=LiveIn(B2)LiveIn(B3)=a a,b-d=a,b-d c 最后最后LiveIn(B1)=LiveUse(B1)(LiveOut(B1)-Def(B1)=b(a,b c-d a)=b-d c a:=1if a=b goto B2b:=1c

21、:=1d:=a+bB1B2B3B41/4/202342中南大学软件学院 陈志刚第八章第八章 优化优化分析程序中所有变量的定值和引用之间的关系分析程序中所有变量的定值和引用之间的关系到达到达-定值数据流方程定值数据流方程OUTB=(INB-KILLB)GENBINB=OUTp p PBPB:B的所有前驱基本块的所有前驱基本块GENB:B中定值并到达中定值并到达B出口之后的所有定值点集出口之后的所有定值点集.KILLB:B之外的那些定值点集之外的那些定值点集,其定值的变量在其定值的变量在B中中 又重新定值又重新定值.INB:到到B入口之前入口之前(紧紧)的各变量的所有定值点集的各变量的所有定值点集

22、OUTB:到达到达B出口之后出口之后(紧紧)各变量的所有定值点集各变量的所有定值点集.1/4/202343中南大学软件学院 陈志刚第八章第八章 优化优化1/4/202344中南大学软件学院 陈志刚第八章第八章 优化优化GEN位向量KILLB1d1,d211000000011100B2d300100001000000B3d400010000100100B4d500001000101000B5 00000000000000INBOUTBB101111001100000B211111000111100B301111000011000B400110000010100B5001110000111001/

23、4/202345中南大学软件学院 陈志刚第八章第八章 优化优化1/4/202346中南大学软件学院 陈志刚第八章第八章 优化优化1/4/202347中南大学软件学院 陈志刚第八章第八章 优化优化 入口结点入口结点 循环循环L 前置结点前置结点 入口结点入口结点 循环循环L 1/4/202348中南大学软件学院 陈志刚第八章第八章 优化优化1/4/202349中南大学软件学院 陈志刚第八章第八章 优化优化123451/4/202350中南大学软件学院 陈志刚第八章第八章 优化优化1/4/202351中南大学软件学院 陈志刚第八章第八章 优化优化 B1 B2 B3 B4 B5(1)I:=1I:=3

24、;(2)if xy goto(3)(3)I:=2(4)x:=x+1(5)y:=y-1(6)if y=20 goto B2(7)J:=I1/4/202352中南大学软件学院 陈志刚第八章第八章 优化优化 B1 B2 B3 B4 B5(1)I:=1(2)if xy goto(3)(3)I:=2(4)x:=x+1(5)k:=I;y:=y-1(6)if y=20 goto B2(7)J:=I1/4/202353中南大学软件学院 陈志刚第八章第八章 优化优化当把循环中的不变运算当把循环中的不变运算s:s:A:=B op C外提时注意：外提时注意：（2）要求循环中其它地方不再有要求循环中其它地方不再有A

25、A的定值点。的定值点。（3 3）要求循环中要求循环中A A的所有引用点都是而且仅仅是这个定值所能的所有引用点都是而且仅仅是这个定值所能达到的达到的（1 1）要求）要求s s所在结点是循环的所有出口结点的必经结点所在结点是循环的所有出口结点的必经结点（4 4）要求）要求A A在离开循环之后不再是活跃的在离开循环之后不再是活跃的1/4/202354中南大学软件学院 陈志刚第八章第八章 优化优化数据流问题的讨论数据流问题的讨论合流问题合流问题向向前前流流（forward-flow)(信信息息流流的的方方向向与与控控制制流流是是一一致致的的)和向后流（和向后流（backward flow）对对每每个个

26、基基本本块块有有一一个个IN集集合合和和一一个个Out集集合合,在在同同一一基基本本块块中中，In和和Out集合的关系集合的关系对对于于向向前前流流问问题题：Out(B)=Used(B)(In(B)Killed(B)对对于于向向后后流流问问题题：In(B)=Used(B)(Out(B)Killed(B)作作为为一一个个边边界界条条件件，向向前前流流问问题题中中的的起起始始基基本本块块的的In和和向向后后流流问问题题中中最最后后一一个个基基本本块块的的Out集集合合必必须须指指明明，通通常常，这这些些边边界条件集或者为空，或者包含所有可能的值，因问题而定。界条件集或者为空，或者包含所有可能的值，

27、因问题而定。如：到达如：到达-定值数据流方程定值数据流方程 OUTB=(INB-KILLB)GENB活跃变量数据流方程活跃变量数据流方程LiveIn(B)=LiveUse(B)(LiveOut(B)-Def(B)1/4/202355中南大学软件学院 陈志刚第八章第八章 优化优化数据流问题的讨论路径数据流问题的讨论路径问题问题任意路径数据流分析任意路径数据流分析讨讨论论的的数数据据流流假假定定这这么么一一个个性性质质，即即某某条条路路径径为为真真，（如如果果存存在在某某条条路路径径上上被被引引用用这这个个变变量量就就认认为为是是活活跃跃的的；如如果果存存在在任任何何一一条条路路径径上上被被定定值

28、值，则则就就认认为为这这个个变变量量是是被被定定值值的的）。这这种种数数据据流流问问题题被被称称为为任任意意路路径径问问题题。任任意意路路径径问问题题的的解解不不能能保保证证所所需需的的性性质质一一定定会会满足，仅仅是可能满足。满足，仅仅是可能满足。全路径数据流分析全路径数据流分析数据流问题也可以用全路径（数据流问题也可以用全路径（all-path）形式来解决，形式来解决，使所需的性质在所有可能的路径都满足。对于全路径使所需的性质在所有可能的路径都满足。对于全路径问题的解，所需的性质可以保证总是满足。问题的解，所需的性质可以保证总是满足。1/4/202356中南大学软件学院 陈志刚第八章第八章

29、 优化优化数据流问题的解不一定唯一数据流问题的解不一定唯一考考察察图图10.20的的流流图图，其其中中有有一一个个简简单单的的循循环环。在在这这个个流流图图中中，没没有有对对任任何何变变量量定定值值，a在在B4中中被被引引用用。应应用用向向后后流流方方法法传传播播可可以以得得到到一一个个最最明明显显的的解解，即即四四个个基基本本块块的的LiveIn集集合合均均为为a。但是，不太合理的解也是可能的。但是，不太合理的解也是可能的。1/4/202357中南大学软件学院 陈志刚第八章第八章 优化优化若若Def(B1)=Def(B2)=Def(B3)=Def(B4)=Liveuse(B1)=Liveus

30、e(B1)=Liveuse(B1)=Liveuse(B1)=a则最明显的解：则最明显的解：LiveIn(B1)=LiveIn(B1)=LiveIn(B1)=LiveIn(B1)=aB1B2B3B41/4/202358中南大学软件学院 陈志刚第八章第八章 优化优化例如，下面解是满足数据流方程的：例如，下面解是满足数据流方程的：基本块基本块LiveInLiveOutB1a,ba,bB2a,ba,bB3a,ba,bB4a注意b没有在任何基本块中被引用！问题所在是基本块B2和B3互为祖先；而且，因为b从未定值（所有Def集为空），一旦b被包括在LiveIn集合中，它就永远消除不了1/4/202359中南大学软件学院 陈志刚