译原理课件第8章-优化.ppt

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

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

3、 数据流分析(control-flow analysis)控制流分析(data-flow analysis)变换(transformations)第八章第八章 优化优化52023-1-264、优化技术简介、优化技术简介 1.删除多余运算 2.循环不变代码外提 3.强度削弱 4.变换循环控制条件 5.合并已知量与复写传播 6.删除无用赋值例：例：P:=0 for I:=1 to 20 do P:=P+AI*BI第八章第八章 优化优化62023-1-26(1)P:=0(2)I:=1(3)T1:=4*I(4)T2:=addr(A)-4(5)T3:=T2T1(6)T4:=4*I(7)T5:=addr(

4、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:=T1第八章第八章 优化优化72023-1-26(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:

5、=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+4第八章第八章 优化优化82023-1-26(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:

6、=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:=4T1T1第八章第八章 优化优化92023-1-26(1)P:=0(2)I:=1(4)T2:=addr(A)-4(

7、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 goto L2 (6)B:=B+1 (7)goto L1 (8)L2:write(A)(9)halt第八章第八章 优化优化132023

8、-1-26划划分分成成四四个个基基本本块块 B1，B2，B3，B4 B1 (1)(2)(3)基基本本块块内内实实行行的的优优化化:合合并并已已知知量量 删删除除多多余余运运算算 B2 (4)删删除除无无用用赋赋值值 (5)B3 (6)(7)B4 (8)(9)第八章第八章 优化优化142023-1-26基本块的基本块的DAG表示及其应用表示及其应用DAG Directed Acyclic Graph 无环路有向图无环路有向图基本块的基本块的DAG是在结点上带有标记的是在结点上带有标记的DAG 叶结点叶结点 独特的标识符独特的标识符(名字名字,常数常数)标记标记 内部结点内部结点 运算符号标记运算

9、符号标记 各个结点各个结点 附加标识符标记附加标识符标记第八章第八章 优化优化152023-1-26用用 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 Cn1n2n1n3n1n2第八章第八章 优化优化162023-1-26仅仅含含 0，1，2 型型四四元元式式的的基基本本块块的的 DAG 构构造造算算法法:首首先先，DAG 为为空空。对对基基本本块块的的每每一一四四元元式式，依依次次执执行行：1

10、如如果果 NODE（B）无无定定义义，则则构构造造一一标标记记为为 B 的的叶叶结结点点并并定定义义 NODE（B）为为这这个个结结点点；如如果果当当前前四四元元式式是是 0 型型，则则记记 NODE(B)的的值值为为 n，转转 4。如如果果当当前前四四元元式式是是 1 型型，则则转转 2(1）。如如果果当当前前四四元元式式是是 2 型型，则则：(I)如如果果 NODE(1)无无定定义义，则则构构造造一一标标记记为为 C 的的叶叶结结点点并并定定义义 NODE(1)为为这这个个结结点点；(II)转转 2(2)第八章第八章 优化优化172023-1-262（1）如如果果 NODE(B)是是标标记

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

12、知量量），令令得得到到的的新新常常数数为为P。如如果果 NODE(B)或或 NODE(C)是是处处理理当当前前四四元元式式时时新新构构造造出出来来的的结结点点，则则删删除除它它。如如果果 NODE(P)无无定定义义，则则构构造造一一用用 P做做标标记记的的叶叶结结点点 n。置置 NODE(P)=n，转转 4。第八章第八章 优化优化182023-1-263（1）检检查查 DAG 中中是是否否已已有有一一结结点点，其其唯唯一一后后继继为为NODE(B)，且且标标记记为为 op（即即找找公公共共子子表表达达式式）。如如果果没没有有，则则构构造造该该结结点点 n，否否则则就就把把已已有有的的结结点点作

13、作为为它它的的结结点点并并设设该该结结点点为为 n，转转 4。（2）检检查查中中 DAG 中中是是否否已已有有一一结结点点，其其左左后后继继为为NODE(B)，其其右右后后继继为为 NODE(C)，且且标标记记为为 op（即即找找公公共共子子表表达达式式）。如如果果没没有有，则则构构造造该该结结点点 n，否否则则就就把把已已有有的的结结点点作作为为它它的的结结点点并并设设该该结结点点为为 n，转转 4。4.如如果果 NODE(A)无无定定义义，则则把把 A 附附加加在在结结点点 n 上上并并令令NODE(A)=n；否否则则先先把把 A 从从 NODE(A)结结点点上上附附加加标标识识符符集集中

14、中删删除除（注注意意，如如果果 NODE(A)是是叶叶结结点点，则则其其标标记记 A 不不删删除除），把把 A 附附加加到到新新结结点点 n 上上并并令令 NODE(A)=n。转转处处理理下下一一四四元元式式。而而后后，我我们们可可由由 DAG 重重新新生生成成原原基基本本块块的的一一个个优优化化的的代代码码序序列列。第八章第八章 优化优化192023-1-26(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例：例：第八章第八章 优化

15、优化202023-1-26 To 3.14 (a)n1 T0 T1 3.14 6.28 (b)n2n1 T2 +T0 T1 3.14 6.28 R r (c)n2n5n3n1n4第八章第八章 优化优化212023-1-26 A *T2 +T0 T1 3.14 6.28 R r (d)n2n5n3n1n4n6第八章第八章 优化优化222023-1-26 A,B *T2 +T0 T1 3.14 6.28 R r (e)n2n5n3n1n4n6第八章第八章 优化优化232023-1-26 A,B *T2 +T0 T1,T3 3.14 6.28 R r (f)n2n5n3n1n4n6第八章第八章 优化

16、优化242023-1-26 A,B *T2,T4 +T0 T1,T3 3.14 6.28 R r (g)n2n5n3n1n4n6第八章第八章 优化优化252023-1-26 A,B,T5 *T2,T4 +T0 T1,T3 3.14 6.28 R r (h)n2n5n3n1n4n6第八章第八章 优化优化262023-1-26 A,B,T5 *T2,T4 T6 +-T0 T1,T3 3.14 6.28 R rn2n5n3n7n1n4n6第八章第八章 优化优化272023-1-26 B *A,T5 *T2,T4 T6 +-T0 T1,T3 3.14 6.28 R r (j)n2n5n3n7n1n4n

17、6n8第八章第八章 优化优化282023-1-26(1)T0:=3.14(2)T1:=6.28(3)T3:=6.28(4)T2:=R+r(5)T4:=T2(6)A:=6.28*T2(7)T5:=A(8)T6:=R-r(9)B:=A*T6第八章第八章 优化优化292023-1-26控制流程图控制流程图（流图）：具有唯一首结点的有向图（流图）：具有唯一首结点的有向图G=（N，E，n0）N：结点集：结点集 基本块集基本块集 E：有向边集：有向边集 n0：首结点：首结点 包含程序第一个包含程序第一个 语句的基本块语句的基本块8.3 循环优化第八章第八章 优化优化302023-1-26有有向向边边 基基

18、本本块块 j j 在在程程序序的的位位置置紧紧跟跟在在 i i 后后,且且 i i 的的出出口口语语句句不不是是转转移移或或停停语语句句i i 的的出出口口是是 g go ot to o(S S)或或 i if f g go ot to o(S S),而而(S S)是是 j j 的的入入口口语语句句 i j第八章第八章 优化优化2023-1-26例例：*(1)read x(20read y*(3)r:=x m od y(4)if r=0 goto(8)*(5)x:=y(6)y:=r(7)goto(3)*(8)w rite y(9)halt第八章第八章 优化优化322023-1-26(1)rea

19、d x B1(2)read y(3)r:=x mod y B2(4)if r=0 goto(8)(5)x:=y (8)write y B4(6)y:=r B3 (9)halt(7)goto(3)第八章第八章 优化优化332023-1-26 1 2 4 3第八章第八章 优化优化342023-1-26分析程序流图中结点间的关系分析程序流图中结点间的关系m DOM n 定义 在程序流图中在程序流图中,对任意两个结点对任意两个结点m和和n,如果从流图的首结点出发如果从流图的首结点出发,到达到达n的任意通路都的任意通路都要经过要经过m,则称则称m是是n的必经结点的必经结点,记为记为m DOM n (a,

20、a MOD a)集集 定义 结点结点n的所有的所有的集合的集合,称为结点称为结点n的的必经结点集必经结点集,记为记为D(n).第八章第八章 优化优化352023-1-26例例:6 73 4 1 2 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 3第八章第八章 优化优化362023-1-26循环的查找循环的查找循环的查找算法循环的查找算法回边：假设回边：假设 ab 是流图中的一条有向边，如果是流图中的一条有向边，如果b D

21、OM a，则，则称称 a b 是流图中的一条回边。是流图中的一条回边。有向边有向边 ndnd是回边，组成的循环是由结点是回边，组成的循环是由结点d，结点，结点 n以及有以及有通路到达通路到达 n而该通路不经过而该通路不经过 d的所有结点组成，并且的所有结点组成，并且d是该循是该循环的唯一入口结点。环的唯一入口结点。循环循环(结点序列的性质结点序列的性质)1.1.强连通的强连通的(任意两结点间任意两结点间,必有一条通路必有一条通路,且该通路上各且该通路上各结点都属于该结点序列结点都属于该结点序列)2.2.它们中间有且只有一个是入口结点它们中间有且只有一个是入口结点.第八章第八章 优化优化3720

22、23-1-26 8.4 数据流分析数据流分析1.活跃变量数据流方程活跃变量数据流方程2.到达到达-定值数据流方程定值数据流方程3.讨论讨论 数据流问题分类数据流问题分类 路径路径 数据流方程解不唯一数据流方程解不唯一第八章第八章 优化优化382023-1-26活跃变量的数据流分析活跃变量的数据流分析所谓活跃变量就是它的当前值还将被引用所谓活跃变量就是它的当前值还将被引用（在赋予一个新值之前）。在全局范围（在赋予一个新值之前）。在全局范围来分析的话，一个变量是活跃的，如果来分析的话，一个变量是活跃的，如果存在一条路径使得该变量被重新定值之存在一条路径使得该变量被重新定值之前它的当前值还要被引用。

23、前它的当前值还要被引用。通过全局活跃变量分析，识别出其当前值通过全局活跃变量分析，识别出其当前值不再活跃（即，它的值已经死了）的那不再活跃（即，它的值已经死了）的那些变量。死变量的值在基本块的出口处些变量。死变量的值在基本块的出口处不需要保存。不需要保存。第八章第八章 优化优化392023-1-26令令B为一个基本块，为一个基本块，定义定义LiveIn(B)为在基本块为在基本块B入口处为活跃的变量的集合。入口处为活跃的变量的集合。定义定义LiveOut(B)为基本块为基本块B的出口处的活跃变量的集合。的出口处的活跃变量的集合。LiveIn和和LiveOut并不是相互独立的，令并不是相互独立的，

24、令S（B）为流图中基本块）为流图中基本块B的后的后继的集合，则有继的集合，则有 LiveOut(B)=LiveIn(i)is(B)如果基本块没有后继，则其如果基本块没有后继，则其LiveOut为空为空令令LiveUse(B)为为B中被定值之前要引用变量的集合。这个集合由中被定值之前要引用变量的集合。这个集合由基本块基本块B中的语句唯一确定。容易看出，如果中的语句唯一确定。容易看出，如果vLiveUse(B)，则则vLiveIn(B)；即即LiveIn(B)LiveUse(B)。令令Def(B)为在为在B中定值的变量集合。如果一个变量在基本块中定值的变量集合。如果一个变量在基本块B的出的出口处为

25、活跃的且口处为活跃的且v Def(B)，则它在，则它在B的入口处也是活跃的，即：的入口处也是活跃的，即：LiveIn(B)LiveOut(B)-Def(B)因此有：因此有：LiveIn(B)=LiveUse(B)(LiveOut(B)-Def(B)即：一个变量在基本块入口处为活跃的，则一定有：或者它在基本即：一个变量在基本块入口处为活跃的，则一定有：或者它在基本块的块的LiveUse集中，或者它在基本块的出口处为活跃的且在基集中，或者它在基本块的出口处为活跃的且在基本块中没有重新定值本块中没有重新定值 第八章第八章 优化优化402023-1-26a:=1;if a=b then b:=1 el

26、se c:=1endif;d:=a+ba:=1if a=b goto B2b:=1c:=1d:=a+bB1B2B3B4第八章第八章 优化优化412023-1-26提取提取Def和和LiveUse集合集合基本基本块块DefLiveUseB1abB2bB3cB4da,ba:=1if a=b goto B2b:=1c:=1d:=a+bB1B2B3B4第八章第八章 优化优化422023-1-26从最后一个基本块开始由后往前计算，可以得到一定的解从最后一个基本块开始由后往前计算，可以得到一定的解 LiveIn(B)=LiveUse(B)(LiveOut(B)-Def(B)LiveOut(B)=LiveI

27、n(i)is(B)LiveOut(B4)=，因此：，因此：LiveIn(B4)=LiveUse(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)

28、=b(a,b c-d a)=b-d c a:=1if a=b goto B2b:=1c:=1d:=a+bB1B2B3B4第八章第八章 优化优化432023-1-26分析程序中所有变量的定值和引用之间的关系分析程序中所有变量的定值和引用之间的关系到达到达-定值数据流方程定值数据流方程OUTB=(INB-KILLB)GENBINB=OUTp p PBPB:B的所有前驱基本块的所有前驱基本块GENB:B中定值并到达中定值并到达B出口之后的所有定值点集出口之后的所有定值点集.KILLB:B之外的那些定值点集之外的那些定值点集,其定值的变量在其定值的变量在B中中 又重新定值又重新定值.INB:到到B入口

29、之前入口之前(紧紧)的各变量的所有定值点集的各变量的所有定值点集OUTB:到达到达B出口之后出口之后(紧紧)各变量的所有定值点集各变量的所有定值点集.第八章第八章 优化优化442023-1-26 d1 B1 d2 d3 B2 d4 B3 d5 B4 d6 B5 d7 到达一定值I:=2J:=I+1I:=1J:=J+1J:=J-4 :=I :=J第八章第八章 优化优化452023-1-26GEN位向量KILLB1d1,d211000000011100B2d300100001000000B3d400010000100100B4d500001000101000B5 00000000000000INB

30、OUTBB101111001100000B211111000111100B301111000011000B400110000010100B500111000011100第八章第八章 优化优化462023-1-26求求解解数数据据流流方方程程(含含 n 个个结结点点的的流流图图)begin for i:=1 to n do begin IN Bi:=;OUTBi :=GENBi;end;change:=true;while change do begin change:=false;for i:=1 to n do begin newin:=OUTp;/p PBi if newin INBi t

31、hen begin change:=ture;INBi:=newin;OUTBi:=(INBi KILLBi)GENBi end end end end第八章第八章 优化优化472023-1-26应用 -查找循环不变式(量)x:=y+z 条件 y和z的所有可能的定值点在该循环外.ud链 若 x:=y+z是循环不变式,w是循环外定值的.则v:=x+w也是循环不变式 -全局优化第八章第八章 优化优化482023-1-26 入口结点入口结点 循环循环L 前置结点前置结点 入口结点入口结点 循环循环L 第八章第八章 优化优化492023-1-26 B1 B2 B3 B4 B5(1)i:=1(2)if

32、x y goto B3(5)y:=y-1(6)if y=20 gotoB5(3)i:=2(4)x:=x+1(7)j:=i第八章第八章 优化优化502023-1-2612345第八章第八章 优化优化512023-1-26 B1 B2 B2 B3 B4 B5 i:=2 if x y goto B3y:=y-1if y=20 gotoB5x:=x+1 j:=i i:=1第八章第八章 优化优化522023-1-26 B1 B2 B3 B4 B5(1)I:=1I:=3;(2)if xy goto(3)(3)I:=2(4)x:=x+1(5)y:=y-1(6)if y=20 goto B2(7)J:=I第八

33、章第八章 优化优化532023-1-26 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:=I第八章第八章 优化优化542023-1-26当把循环中的不变运算当把循环中的不变运算s:s:A:=B op C外提时注意：外提时注意：（2）要求循环中其它地方不再有要求循环中其它地方不再有A A的定值点。的定值点。（3 3）要求循环中要求循环中A A的所有引用点都是而且仅仅是这个定值所能的所有引用点都是而且仅仅是这个定值所能达到的达到的（1 1）要求）要求s s所在结点是

34、循环的所有出口结点的必经结点所在结点是循环的所有出口结点的必经结点（4 4）要求）要求A A在离开循环之后不再是活跃的在离开循环之后不再是活跃的第八章第八章 优化优化552023-1-26中南大学软件学院 陈志刚数据流问题的讨论数据流问题的讨论合流问题合流问题向前流（向前流（forward-flow)(信息流的方向与控制流是一致信息流的方向与控制流是一致的的)和向后流（和向后流（backward flow）对每个基本块有一个对每个基本块有一个IN集合和一个集合和一个Out集合集合,在同一基本块中，在同一基本块中，In和和Out集合的关系集合的关系对于向前流问题：对于向前流问题：Out(B)=U

35、sed(B)(In(B)Killed(B)对于向后流问题：对于向后流问题：In(B)=Used(B)(Out(B)Killed(B)作为一个边界条件，向前流问题中的起始基本块的作为一个边界条件，向前流问题中的起始基本块的In和向后流和向后流问题中最后一个基本块的问题中最后一个基本块的Out集合必须指明，通常，这些边集合必须指明，通常，这些边界条件集或者为空，或者包含所有可能的值，因问题而定。界条件集或者为空，或者包含所有可能的值，因问题而定。如：到达如：到达-定值数据流方程定值数据流方程 OUTB=(INB-KILLB)GENB活跃变量数据流方程活跃变量数据流方程LiveIn(B)=LiveU

36、se(B)(LiveOut(B)-Def(B)第八章第八章 优化优化562023-1-26数据流问题的讨论路径数据流问题的讨论路径问题问题任意路径数据流分析任意路径数据流分析讨论的数据流假定这么一个性质，即某条路径为真，讨论的数据流假定这么一个性质，即某条路径为真，（如果存在某条路径上被引用这个变量就认为是活跃（如果存在某条路径上被引用这个变量就认为是活跃的；如果存在任何一条路径上被定值，则就认为这个的；如果存在任何一条路径上被定值，则就认为这个变量是被定值的）。这种数据流问题被称为任意路径变量是被定值的）。这种数据流问题被称为任意路径问题。任意路径问题的解不能保证所需的性质一定会问题。任意路

37、径问题的解不能保证所需的性质一定会满足，仅仅是可能满足。满足，仅仅是可能满足。全路径数据流分析全路径数据流分析数据流问题也可以用全路径（数据流问题也可以用全路径（all-path）形式来解决，）形式来解决，使所需的性质在所有可能的路径都满足。对于全路径使所需的性质在所有可能的路径都满足。对于全路径问题的解，所需的性质可以保证总是满足。问题的解，所需的性质可以保证总是满足。第八章第八章 优化优化572023-1-26数据流问题的解不一定唯一数据流问题的解不一定唯一考察图考察图10.20的流图，其中有一个简单的循环。的流图，其中有一个简单的循环。在这个流图中，没有对任何变量定值，在这个流图中，没有

38、对任何变量定值，a在在B4中中被引用。应用向后流方法传播可以得到一个最被引用。应用向后流方法传播可以得到一个最明显的解，即四个基本块的明显的解，即四个基本块的LiveIn集合均为集合均为a。但是，不太合理的解也是可能的。但是，不太合理的解也是可能的。第八章第八章 优化优化582023-1-26若若Def(B1)=Def(B2)=Def(B3)=Def(B4)=Liveuse(B1)=Liveuse(B1)=Liveuse(B1)=Liveuse(B1)=a则最明显的解：则最明显的解：LiveIn(B1)=LiveIn(B1)=LiveIn(B1)=LiveIn(B1)=aB1B2B3B4第八章第八章 优化优化592023-1-26例如，下面解是满足数据流方程的：例如，下面解是满足数据流方程的：基本块基本块LiveInLiveOutB1a,ba,bB2a,ba,bB3a,ba,bB4a注意b没有在任何基本块中被引用！问题所在是基本块B2和B3互为祖先；而且，因为b从未定值（所有Def集为空），一旦b被包括在LiveIn集合中，它就永远消除不了