西北工业大学编译原理第九章 代码优化.ppt

1、(第九章 代码优化),1,代码优化的概念,代码优化指的是编译时刻为改进目标程序的质量而进行的各项工作。 空间效率 时间效率 空间效率和时间效率是一对矛盾，有时不能兼顾 优化的要求： 必须是等价变换 为优化做出的努力必须是值得的,2,优化的分类,机器相关性： 机器相关优化：寄存器优化，多处理器优化，特殊指令优化，无用指令消除等。-针对汇编语言或机器语言 机器无关优化：-针对中间代码 优化范围： 局部优化：基本块范围内的优化，即合并常量计算，消除公共子表达式，删除无用代码和削减计算强度。 全局优化：主要是基于循环的优化，即循环不变式优化，归纳变量删除，计算强度削减。,3,(第九章 代码优化),9.

2、1 基本块的优化 9.2 与循环有关的优化,4,9.1 基本块的优化,基本块的优化是局部优化，输入是组成基本块 的四元式序列，输出是优化了的四元式序列。 1.基本块的概念 2.基本块的识别步骤 3.基本块的优化 4.基本块优化算法的实现,5,6,基本块的概念,所谓基本块，是指程序中一顺序执行无分叉的代码序列，只有一个入口和一个出口，入口是第一个语句，出口是最后一个语句()。 对于一个给定的程序，可以把它划分为一系列的基本块，在各基本块范围内，分别进行局部优化。 给定一个程序，划分基本块的步骤() ？,7,T1=A*B T2=3/2 T3=T1-T2 X=T3 C=2 T4=A*B T5=18+

3、C T6=T4*T5 Y=T6,下面是一个基本块的例子：,基本块（续）,8,1). 确定各基本块的入口： 程序的第一条指令； 紧跟在条件转移指令后面的指令。 条件转移语句或无条件转移语句转向的目标指令；,基本块的识别步骤,9,2). 对每个入口指令,构造其所属的基本块: 基本块是由该入口到下一入口之间的指令序列构成(不含下一入口)； 或是由该入口到一转移指令之间的指令序列构成(包括该转移指令)； 或是由该入口到停机指令为止的所有指令序列构成(包括该停机指令)。 3). 执行上述两步操作后，凡未包含在任何基本块中的指令，都是控制不可能达到的指令，应删除。,基本块的识别步骤（续）,10,划分基本块

4、的例子：,read x t1=x0 if_false t1 goto L1,fact=1,label L2 t2=fact*x fact=t2 t3=x-1 x=t3 t4=x if_false t4 goto L2,write fact,label L1 halt,B1,B2,B3,B4,B5,基本块的识别步骤（续）,基本块的优化,合并常量计算 消除公共子表达式 削减计算强度 删除无用代码,11,合并常量计算 例子：l = 2*3.14*r t1=2*3.14 t2=t1*r l=t2 2*3.1415926的值在编译时刻就可以确定。 t2=6.28*r l=t2,12,基本块的优化(续),

5、消除公共子表达式 例如：1) a=b+c , 2) b=a-d, 3) c=b+c4) d=a-d 显然，第2)和4)个四元式计算的是同一个值，所以第四个四元式可以修改成d=b。 对于第1和3个四元式，虽然都是计算b+c，但是他们的值其实是不同的，所以不能消除公共子表达式。,13,基本块的优化(续),消除公共子表达式（续） 公共表达式：如果某个表达式E先前已经计算，且从上次计算到现在，E中的变量的值没有改变。那么E的这次出现称为公共子表达式。 利用先前的计算结果，可以避免对公共子表达式的重复计算。,基本块的优化(续),14,削减计算强度:实现同样的运算可以有多种方式，用计算较快的运算代替较慢的

6、运算 x2 变成x*x。 2*x或2.0*x 变成x+x x/2 变成x*0.5 anxn+an-1xn-1+a1x+a0 变成 (anx+an-1)x+ an-2)x+a1)x+a0,15,基本块的优化(续),删除无用代码 如果四元式z=x op y之后，对z赋予的该值再也没有被使用到，那么这个四元式是无用的。 例如: t0=a;t0+=5; x=t0; ; t0+=1; t0=b; y=b; 赋值t0+=1可被删除。,16,基本块的优化(续),基本块优化的实现,基本块内部优化实现的主要工具为DAG图。 用DAG图表示各个值的计算/依赖关系。 基本块DAG图构造算法 输入：一个基本块 输出：

7、相应DAG图 算法说明： 通过逐个扫描四元式来逐渐建立DAG图。,17,0型：A= B 1型： A =op B (单目运算） 2型： C= A op B 将数组A的第i个元素的地址存放t: Ai=t 四元式 ：=Ait 将数组A的第i个元素存放到t: t=Ai 四元式： =Ait if_false t1 goto L1 四元式 ：relop t1 false L1,四元式的分类,18,基本块优化的实现(续),基本块优化的实现(续),基本块的DAG表示 下图依次列出了如下各种四元式相对应DAG图中的节点形式： (0) A = B 注：B是节点n1的标记 ，放在节点n1的下方，A是节点n1第一个附

8、加标识.,n1,19,(1) A = op B 节点n1称为n2的后继 Op是n2的标记 (2) A = B op C 节点n1和n2分别称为节点n3的后继 Op是n3的标记,基本块优化的实现(续),20,B,由基本块构造DAG算法的描述： 首先，DAG为空。对基本块的每一四元式，依次执行以下步骤： 步骤1：对于任意(0)、(1)、(2)型四元式，如果节点B在DAG中无定义，则构造一标记为B的叶节点，记node (B)=n 。 如果当前的四元式为(0)型，则转步骤4。 如果当前的四元式为(1)型，则转步骤2的 。 如果当前的四元式为(2)型，如果node (C)无定义，则构造一个标记为C的叶节

9、点node (C), 转步骤2的 。,基本块优化的实现(续),21,由基本块构造相应的DAG算法的描述：（续）,步骤2： 如果node (B) 是标记为常数的叶节点，则转步骤2的，否则转步骤3的。 执行op B（即合并已知量），令得到的新常数为p。 如果node (B)是处理当前四元式时新构造节点，则删除它。 如果node (P)无定义，则构造一个用P做标记的叶节点 n，否则设该节点为n ，转步骤4 。,22,步骤2： 如果node (B) 和node (C)都是标记为常数的叶节点，则转步骤2的，否则转步骤3的 。 执行B op C(即合并已知量)，令得到的新常数为P，如果node (B) 或

10、node (C)是处理当前四元式时新构造的节点，则删除它，如果node (P)无定义，则构造一个用P做标记的叶节点 n ，否则设该节点为n ，转步骤4 。,由基本块构造相应的DAG算法的描述：（续）,23,由基本块构造相应的DAG算法的描述：（续）,步骤3： 检查DAG中是否已有一节点，其唯一后继为node(B) ，且操作标记为op(即找公共子表达式)。如果没有，则构造该节点n，否则设该节点为n,转步骤4 。 检查DAG中是否已有一节点，其左后继为node (B)，右后继为node (C)且标记为op(即找公共子表达式)。如果没有，则构造节点n，否则设该节点为n，转步骤4 。,24,由基本块构

11、造相应的DAG算法的描述：（续）,步骤4： 如果node (A)有定义，把A从node (A)节点上附加标识集中删除； 把A附加在节点n上并令node (A)=n； 接着处理下一个四元式。,25,利用上述算法构建DAG图，然后按DAG图中节点建立次序重构基本块，则可得到优化后的基本块。,26,基本块优化的实现(续),从DAG重建四元式序列算法：按照DAG图中的各个节点生成的次序，对每个节点n作如下处理： 若n是叶子节点，且附加标识符表为空，则不生成四元式。 若n是内部节点，第一个附加标识符为z1，根据其标记op和子节点数目，生成下列形式的四元式。 有两个子节点，生成 z1 = x op y 只

12、有一个子节点，生成z1 = op x,基本块优化的实现(续),27,从DAG重建四元式序列算法(续),如果节点n的标识符中包含多个附加标识符z1,z2,zk(k2)时： 还要生成如下所示的一系列四元式 z2 = z1 zk =z1,28,T1,T2,T3,X,C,T6,Y,T4,T5,DAG构造实例：,T1=A*B T2=3/2 T3=T1-T2 X=T3 C=5 T4=A*B C=2 T5=18+C T6=T4*T5 Y=T6,C,基本块优化的实现(续),29,21,22,23,24,25,1. T1=A*B 2. T2=1.5 3. T3=T1-1.5 4. X=T3 5. T4= T1

13、6. C=2 7. T5=20 8. T6=T1*20 9. Y=T6,利用上述构建的DAG图，按节点建立次序重构基本块，则可得到经上述优化后的基本块：,由基本块构造相应的DAG算法的描述：（续）,30,对于DAG构造算法中的步骤2：如果参与运算的对象都是编译时的常量，则它并不生成计算该节点值的内部节点，而是执行该运算，将计算结果生成一个叶节点，步骤2起到了合并常量计算的作用。,基本块优化的实现(续),31,对于DAG构造算法中的步骤3其作用是检查公共子表达式，对具有公共子表达式的所有四元式，它只生成一个计算该表达式值的内部节点，而把那些被赋值的变量标识附加到该节点上，这样可以删除公共子表达式

14、。,基本块优化的实现(续),32,对于DAG构造算法中的步骤4具有删除无用赋值的作用，如果某变量被赋值后，在它被引用前又被重新赋值，则步骤4把变量从具有前一个值的节点上删除。,基本块优化的实现(续),33,34,基本块优化的实现(续),DAG的其他应用 削弱计算强度优化：在构造DAG时可以根据代数恒等式进行各种情况的识别，例如，当识别出标记为*的节点，有一个子节点（左或右）为2或2.0，便可以把乘法运算代之以加法运算，其他情况类似；,复写四元式删除：例如: t0=a;t0+=5; x=t0; ; t0+=1; t0=b; y=b; 如果尽量用b替代t0，可能使t0不被使用，从而这个复写四元式称

15、为无用的四元式（赋值四元式t0=b称为复写四元式，用b替代t0称为复写传播 ）。 通过构造DAG图可以获得下列信息： 在基本块中，其值被引用的标识符 结果能够在基本块外被引用它所计算之值的四元式z = x op y,35,基本块优化的实现(续),(第九章 代码优化),9.1 基本块的优化 9.2 与循环有关的优化,36,9.2 与循环有关的优化,37,循环部分在一个程序中可能仅占很小比例，然而运行时间却可能在整个运行时间上占到很大部分，因此，对循环的优化往往是改进程序质量的关键。 与循环有关的优化是全局优化，输入是流图（有向图或其他便于存储和处理的形式）,9.2 与循环有关的优化(续),9.2

16、.1 循环不变表达式外提 9.2.2 归纳变量删除 9.2.3 计算强度削减 9.2.4 循环优化的实现,38,9.2.1循环不变式外提,有些表达式位于循环之内，但是该表达式的值不随着循环的重复执行而改变，该表达式被称为循环的不变表达式。 如果把这个表达式提取到循环外面，该计算就仅被执行一次。从而可以获得更好的效率。,39,9.2.1循环不变式外提(续),循环不变式的例子 计算半径为r，从10度到360度的扇形的面积： for(n=1; n36; n+) S:=10/360*pi*r*r*n; printf(“Area is %f”, S); 由于表达式10/360*pi*r*r中的各个量在循

17、环过程中不改变，所以，可以修改程序如下： C= 10/360*pi*r*r; for(n=1; n36; n+) S:=C*n; printf(“Area is %f”, S); 修改后的程序中，C的值仅需计算一次，而原来的程序需要计算35次。,40,循环不变式的相对性：对于多重嵌套的循环，循环不变四元式是相对于某个循环而言的。可能对于更加外层的循环，它就不是循环不变式。 例子： for(i = 1; i10; i+) for(n=1; n360/(5*i); n+) S:=(5*i)/360*pi*r*r*n;. 5*i和(5*i)/360*pi*r*r对于n的循环（内层循环）是不变表达式，

18、但是对于外层循环，它们不是循环不变表达式。,41,9.2.1循环不变式外提(续),9.2 与循环有关的优化(续),9.2.1 循环不变表达式外提 9.2.2 归纳变量删除 9.2.3 计算强度削减 9.2.4 循环优化的实现,42,在循环中，如果变量i的值随着循环的每次重复都固定地增加或者减少某个常量，则称i为循环的归纳变量。 如果在一个循环中有多个归纳变量，归纳变量的个数往往可以减少，甚至减少到1个。减少归纳变量的优化称为归纳变量的删除。,43,9.2.2 归纳变量删除,9.2.2 归纳变量删除(续),设某程序中有如下循环: i=a; while(i=c) ;d=i*k;i+=b; d与i为

19、归纳变量,d=i*k在循环内恒真,故条件i=c等价于d=c*k. 若i只用于控制循环,则可省略,将循环控制条件改为 T2:=c*k; if_false d=T2 goto B4 有关i的四元式均可删除.见下面图示。,(1) i:=a B1,(2) if_false i=c goto B4 B2,(3) d:=i*k （4）i:=i+b (5） goto B2, B4,44,(4) if_false d=T2 goto B4 B2,(5) d:=d+T1 B3 (6) goto B2, B4,(1)d:=a*k B2 (2) T1:=b*k (3) T2:=c*k,(1) i:=a B1,(2)

20、 if_false i=c goto B4 B2,(3) d:=i*k B3 （4）i:=i+b （5） goto B2, B4,归纳变量i删除前,归纳变量i删除后,45,归纳变量删除优化需要解决的问题,找出归纳变量 确定要删除的归纳变量 确定要进行的等价变换,9.2.2 归纳变量删除(续),46,9.2 与循环有关的优化(续),9.2.1 循环不变表达式外提 9.2.2 归纳变量删除 9.2.3 计算强度削减 9.2.4 循环优化的实现,47,9.2.3计算强度削减,关于循环的优化，也可进行计算强度缩减优化，计算强度削减包括归纳变量计算强度的削减与数组元素地址计算的强度削减。 在删除归纳变量

21、的过程中，已经将一些乘法运算转换成为加法运算，这是计算强度缩减的一种-归纳变量计算强度缩减。,48,9.2.3计算强度削减(续),计算强度削减（下标变量） 对于数组Tan1n2nm，其下标变量ai1i2i3im的地址计算如下： base+d；其中base为a000的地址。 d=(i1*n2+i2)*n3+i3)*nm+im)*sizeof(T); 当数组元素下标满足某些特定条件时，地址的计算可以使用加法来代替计算d时的乘法。,49,下标变量计算强度的削减（例子） for(v1=v10; v1v1f; v1+) for(v2=v20; v2v2f; v2+) Ai1i2 设i1, i2都可以表示

22、成：Ck0+Ck1*V1+Ck2*V2(k=1,2); Ai1i2的地址为base+d; d=(i1*n2+i2); 将i1,i2的表达式代入d的表达式，可以得到d=(C10*n2+C20)+ (C11*n2+C21) *V1 )+ (C12*n2+C22) *V2 =C0+C1*V1+C2*V2. 每次内循环d的值增加C2；每次外循环d的值增加C1（但是V2被重置）。,50,9.2.3计算强度削减(续),可以这样计算Ai1i2的地址： 在循环开始的时候，设置初值d1=(base+C0)+C1*V10; 在进入外层循环后，进入内存循环前，设置d2=d1+C2*V20 在内存循环，使用d2作为地

23、址获取Ai1i2的值。 内存循环体每次运行结束之前，将d2的值增加C2。 每次外层循环体运行结束之前，将d1的值增加C1。 显然，对于Ai1i2的地址计算变成了加法运算。,51,9.2.3计算强度削减(续),下标变量计算强度的削减结果,D1 = base+C0+C1*V10; for(v1=v10; v1v1f; v1+) D2 = D1+C2*V20; for(v2=v20; v2v2f; v2+) *D2; D2+=C2; D1+= C1; ,52,9.2.3计算强度削减(续),满足下述条件下标变量成为可优化的。 相应的数组是常界数组：数组的上下界都是常量 下标变量中的下标表达式是循环控制

24、变量的线性表达式,53,9.2.3计算强度削减(续),9.2 与循环有关的优化(续),9.2.1 循环不变表达式外提 9.2.2 归纳变量删除 9.2.3 计算强度削减 9.2.4 循环优化的实现,54,9.2.4 循环优化的实现,9.2.4.1 流图 9.2.4.2 循环结构的识别 9.2.4.3 数据流分析 9.2.4.4 优化实现,55,9.2.4.1 流图,流图：把控制流信息加到基本块集合所形成的有向图称为流图。 即将一个程序的中间表示中所有的基本块作为流图的节点集合 ，节点之间的有向边代表控制流。 有边从节点n到节点n当且仅当控制流可能从n的最后的一个四元式到达n的第一个四元式。 首

25、节点：一个基本块，当其第一个四元式是程序的第一个四元式时，该节点所对应的节点成为流图的首节点。,56,9.2.4.1 流图(续),流图的构造 将所有的基本块作为流图的节点集合。 有节点B1到节点B2的边(B2是B1的后继)，当且仅当下述两个条件之一成立： B1的最后一个四元式有条件或无条件地转移到B2的第一个四元式。 B2是紧紧跟随在B1后面的四元式序列，且B1的最后四元式执行完毕后可以到B2的第一个四元式(下页图示)。,57,57,流图的例子,在转移语句中，目标标号作为基本块的编号，可以避免因为四元式的变动而引起麻烦。,58,I=1 Goto B3,I=I+1,If_false （I N）

26、B5,Got0 B6,T=M+I M=T Goto B3,108 ,B1,B2,B3,B4,B5,B6,58,9.2.4 循环优化的实现,9.2.4.1 流图 9.2.4.2 循环结构的识别 9.2.4.3 数据流分析 9.2.4.4 优化实现,59,是实现对循环优化的前提,通过数据流分析，实现与循环有关的优化（例如：通过数据流方程可以求解循环不变式）,循环结构的识别是循环优化的第一个步骤； 经过语义分析，内部中间表示中已无循环结构的痕迹，不能由关键字while、do或for识别循环结构； 流图中的循环结构，有两个基本性质： 循环必具有唯一的入口点，称为首节点，它是循环中所有节点的必经节点；

27、对于循环中的任何一个节点，必定至少存在一条路径回到首节点。,60,60,9.2.4.2 循环结构的识别,循环的识别针对流图进行。 定义9.1 节点m是节点n的必经节点：如果流图中，从某个初始节点出发，每一条到达节点n的路径都必须经过m，那么称m是节点n的必经节点。记为m dom n。 任何节点都是自己的必经节点。 m为n的前驱，n为m的后继。 定义9.2 节点n的直接必经节点：从初始节点到达n的所有路径上，节点n的最后一个必经节点称为直接必经节点。 在必经节点的基础上，引进回边的概念，便可实现循环的识别。,61,9.2.4.2 循环结构的识别(续),9.2.4.2 循环结构的识别(续),定义9

28、.3 回边： 假定流图中存在两个节点M和N满足M dom N。如果存在从节点N到M的有向边N-M，那么这条边称为回边。 定义9.4 回边N-M的自然循环：对于回边N-M，找出所有不经过M而到达N的所有节点，连同节点M与N，构成以M为首节点的一个循环，即是回边N-M的自然循环。（画一个图示） 一个自然循环用构成它的所有节点的集合来表示。 循环的识别就是识别流图中的回边及组成回边的自然循环的一切节点，同时保证其仅有唯一的首节点。,62,9.2.4.2循环结构的识别(续),自然循环的例子 3 dom 4，3 dom 8 回边4-3, 8-3的自然循环3,4,5,6,7,8,10 4 dom 7 回边

29、7-4的自然循环4,5,6,7,8,10 7 dom 10 10-7的自然循环7，8，10,63,9.2.4.2循环结构的识别(续),回边寻找方法 首先列出所有从首节点开始，不带圈的路径。 节点N的必经节点的集合为满足以下条件的节点M： 所有包含N的路径P，节点M都在N的前面出现。 回边集合如下： N-M | N是一个节点，M在N的必经节点集合中 N-M表示从节点N到M的有向边,64,9.2.4.2循环结构的识别(续),自然循环的寻找算法 输入:回边N-M; 输出: 回边对应的自然循环. 算法:下页,65,自然循环的寻找算法： 设置loop=N,M; push(stack, N); while

30、 non-empty(stack) do m = top(stack); pop(stack); for m的每个前驱节点p if p is_not_in loop then loop += p; push(stack,p); ,9.2.4.2循环结构的识别(续),66,9.2.4 循环优化的实现,9.2.4.1 流图 9.2.4.2 循环结构的识别 9.2.4.3 数据流分析 9.2.4.4优化实现,67,是实现对循环优化的前提,通过数据流分析，实现与循环有关的优化（例如：通过数据流方程可以求解循环不变式）,9.2.4.3 数据流分析 (续),数据流分析 到达-定值数据流方程 活跃变量数据流

31、方程 可用表达式数据流方程,68,9.2.4.3数据流分析,定义9.5 定值：使变量x获得值的四元式称为对x的定值，一般用四元式的位置d表示，d也称为x的定值点。 变量获得值的方式： 通过赋值语句； 通过输入语句； 通过函数形式参数传递取得值； 定义9.6 引用点：引用某个变量x的四元式的位置称为x的引用点。 数据流分析就是分析程序中所有变量的定值与引用之间的关系（到达-定值数据流方程）。,69,定义9.7 到达-定值：假定x有定值点d， 如果存在某条路径，从d点可以到达某点p，称x的定值d到达p。 如果d之后p之前某点处对变量x有最新定值，则点p处便不能引用x在点d处的定值，称x的定值d被注

32、销，因而点d处的定值不能到达点p。,70,1.到达定值数据流方程,定义9.7引用-定值链：设变量x有一个引用点u，变量x的所有能到达u的一切定值称为x在u点处的引用-定值链，简称ud链 通过变量x在循环内某引用点u的ud链，就能确定x在点u处的值是在何处定值的，从而判断x是否是循环不变量 如何计算循环内一切变量引用点处的ud链？ 循环由若干个基本块构成，即计算构成循环的各基本块内一切变量的引用点处的ud链； 计算的目的：通过变量x在循环内某引用点u的ud链，从而判断x是否是循环不变量，从而进行循环表达式优化。,71,1.到达定值数据流方程（续）,INB: 表示能到达基本块B的入口点之前的各变量

33、定值点集合。 在基本块B中，点p处x的ud链的计算方式如下： 如果在B中，点p之前有x的定值点d，且这个定值能够到达p，则点p处x的ud链是d。 如果在B中，点p之前没有x的定值点d，则INB中关于变量x的每个定值都能到达点p，即点p处x的ud链就是INB中关于x的定值点的集合。 如何求解INB？,72,1.到达定值数据流方程（续）,1.到达定值数据流方程（续）,为了求解INB，首先给出如下定义： PB：基本块B的所有直接前驱节点基本块的集合。 OUTB：能够到达基本块B的出口点之后的各个变量定值点的集合。 KILLB：在基本块B外定值，而在基本块B中又重新定值的变量定值点的集合。 GENB：

34、各个变量在B内定值，并能够到达B的出口点之后的所有定值点的集合。,73,1.到达定值数据流方程（续）,到达定值数据流方程（）： INB = U OUTp where p is in PB OUTB = GENB U (INB-KILLB) 其中： GENB可以从基本块中求出：使用DAG图就可以得到。 KILLB中，对于整个流图中的所有x的定值点，如果B中有对x的定值，那么该定值点在KILLB中。 在求解INB的过程中，假设GENB和 KILLB已知。,74,方程求解算法,使用迭代方法求解INB和OUTB ： 对于任意基本块：INB=空；OUTB=GENB; change = TRUE; whi

35、le(change) change = FALSE; for each B do INB = U OUTp where p is in PB; oldout = OUTB; OUTB = GENB U (INB-KILLB); if(OUTB != oldout) change = TRUE; ,75,算法例子,GENB1=d1,d2,d3 KILLB1=d4,d5,d6,d7 GENB2=d4,d5 KILLB2=d1,d2,d7 GENB3=d6 KILLB3=d3 GENB4=d7 KILLB4=d1,d4,B1,B2,B3,B4,76,计算过程,初始化： INB1 = INB2 = I

36、NB3 = INB4 =空 OUTB1=d1,d2,d3 OUTB2=d4,d5 OUTB3=d6 OUTB4=d7 第一次循环： INB1=空； INB2 =d1,d2,d3,d7; INB3=d4,d5； INB4=d4,d5,d6；OUTB1=d1,d2,d3; OUTB2=d3,d4,d5,77,计算过程（续）,结果： INB1=空； OUTB1=d1,d2,d3； INB2=d1,d2,d3,d5,d6,d7； OUTB2=d3,d4,d5,d6； INB3=d3,d4,d5,d6；OUTB3=d4,d5,d6； INB4=d3,d4,d5,d6； OUTB4=d3,d5,d6,d7；,78,9.2.4 循环优化的实现,9.2.4.1 流图 9.2.4.2 循环结构的识别 9.2.4.3 数据流分析 9.2.4.4 优化实现,79,9.2.4.4 优化实现,根据数据流分析，可以获得流图中基本块之间的数据流信息，利用这些信息，可以实现与循环有关的优化，进一步实现全局优化。,80,9.2.4.4 优化实现（续）,循环不变表达式优化 如何识别循环？（求解回边的自然循环） 如何识别循环中的不变表达式？（根据已求解的变量的ud链识别） 把循环表达式外提到什么地方？ 什么条件下，不变表达式可以外提？,81,