第十章代码优化哈工大王宏志.ppt

《第十章代码优化哈工大王宏志.ppt》由会员分享，可在线阅读，更多相关《第十章代码优化哈工大王宏志.ppt（117页珍藏版）》请在三一文库上搜索。

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

2、化程序的结构,控制流分析的主要目的是分析出程序的循环结构。循环结构中的代码的效率是整个程序的效率的关键。 数据流分析进行数据流信息的收集，主要是变量的值的获得和使用情况的数据流信息。 到达-定义分析；活跃变量；可用表达式； 代码变换：根据上面的分析，对内部中间代码进行等价变换。,控制流分析,数据流分析,代码变换,基本块和流图,基本块中，控制流是由第一个四元式进入，到达最后一个四元式离开。 流图：把一个程序的中间表示中所有的基本块作为节点集合。有边从节点n到节点n当且仅当控制流可能从n的最后的一个四元式到达n的第一个四元式。 首节点：对应的基本块的第一个四元式是程序的第一个四元式。,流图的构造,

3、以所有的基本块为节点集合。 有B1到B2的边（B2是B1的后继）当且仅当： B1的最后一个四元式有条件或无条件地转移到B2的第一个四元式。 B2是紧紧跟随在B1后面的四元式，且B1的最后四元式不是无条件转向语句。,流图的例子,在转移语句中，目标标号转变称为基本块的编号，可以避免因为四元式的变动而引起的麻烦。,= 1 _ i = 1 _ f = 0 _ a,= i 10 B4,= f _ b + f a t1 = t1 _ f = b _ a + i 1 t2 = t2 _ i GO B2,= f fib,B1,B2,B3,B4,基本块的优化,常量合并 公共子表达式删除 强度削弱 无用代码删除,

4、常量合并,例子：l = 2*3.14*r * 2 3.14 t1 * t1 r t2 = t2 l 2*3.1415926的值在编译时刻就可以确定。 * 6.28 r t2 = t2 l,公共子表达式删除,+ b c a - a d b + b c c - a d d 显然，第2和4个四元式计算的是同一个值，所以第四个四元式可以修改为 = b _ d。 对于第1和3个四元式，虽然都是计算b+c，但是他们的值其实是不同的，所以不能完成处理。 公共子表达式：如果某个表达式先前已经计算，且从上次计算到现在，E中的变量的值没有改变。那么E的这次出现就称为公共子表达式。 利用先前的计算结果，可以避免对公

5、共子表达式的重复计算。,例子,x+y*t-a*(x+y*t)/(y*t) * y t t1 + x t1 t2 * y t t3 + x t3 t4 * a t4 t5 * y t t6 / t5 t1 t7 - t2 t7 t8 消除公共子表达式之后： * y t t1 + x t1 t2 * a t2 t5 / t5 t1 t7 - t2 t7 t8,强度削弱,实现同样的运算可以有多种方式。用计算较快的运算代替较慢的运算。 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+

6、a1)x+a0,无用代码删除,如果四元式op x y z之后，z的值再也没有被使用到，那么这个四元式是无用的。 无用的四元式往往意味着程序的错误，一般不会出现在正确的程序里面。 多数无用四元式是由优化引起的。 = t1 t3，如果我们尽量用t1替代t3，可能使t3不被使用，从而这个四元式称为无用的四元式。,等价变换的分类,保结构等价变换 删除公共子表达式和删除无用代码，重新命名临时变量和交换独立四元式的顺序等。 + x y t变成+ x y u + a b t1 + x y t2变成 + x y t2 + a b t1 代数等价变换利用了代数恒等性质， 强度削弱。2x=x+x, B and t

7、rue = B. 需要考虑双目运算符的可交换特性。,基本块优化的实现,基本块内部优化的实现的主要工具为DAG图。 用DAG图表示各个值的计算/依赖关系。 图中的标记： 叶子节点的标记为标识符（变量名）或常数作为唯一的标记。叶子节点是标识符时，用下标0表示它时初值。 内部节点用运算符号作为标记，表示计算的值。每个节点的值都可以用关于变量初始值的表达式表示。 各节点可能附加有一个或者多个标识符。同一个节点的标识符表示相同的值。,DAG图的例子,+ b c a - a d b + b c c - a d d,四元式的分类,0型： = x _ y 1型： op x _ y(单目运算） 2型： op x

8、 y z relop x y z(z是序号),基本块DAG图构造算法,输入：一个基本块 输出：相应DAG图 算法说明： 通过逐个扫描四元式来逐步建立DAG图。 函数node(x)表示和标识符x相应的最近建立的节点。他代表扫描到当前的四元式的时候，标识符x的值对应的节点。 步骤1：初始化：无任何节点，node对任何标识符无定义。 步骤2：依次对基本块中的每个四元式op x y z执行如下步骤。 如果node(x)没有定义，建立叶子节点，标记为x，让node(x) 等于这个节点。如果node(y)没有定义，为y建立节点。 如果四元式为0型，n=node(x); 如果四元式为1型，寻找标记为op且子

9、节点为node(x)的节点，如果找不到，建立这样的节点n。,基本块DAG图构造算法（续）,对于2型四元式，查看是否存在标记为op的节点，且其左右子节点分别为node(x)和node(y)。如果找不到，建立这样的节点n。 步骤3：如果z为标识符，从node(z)中删除标识符z，并把z加入到找到或者建立的节点n的标识符表中，并设置node(z)为n。 说明： 处理2型四元式的时候，如果op是可交换的运算符，可以允许其左右节点可以互换。,生成DAG图的例子,* 4 i t1 = a t1 t2 * 4 i t3 = b t3 t4 * t2 t4 t5 + prod t5 t6 = t6 prod

10、+ i 1 t7 = t7 i = i 20 (3),DAG图的应用,公共子表达式：构造中，寻找是否有标记为op且子节点为node(x), node(y)的节点时，自然完成了公共子表达式的寻找。 在基本块中，其值被引用的标识符：构造了叶子节点的标识符。 结果能够在基本块外被引用的四元式op x y z。设它对应的节点为n，如果DAG图构造结束的时候，n的标志符表不为空。,=和&=运算符的处理,对数组的赋值需要特别的处理，这是因为数组的下标是变量。对于数组元素的赋值可能改变数组中任何一个元素的值。 = A i t1 = A j t2 &= y t2 t2 = A i t3 Ai并不是公共子表达式

11、。 在处理对数组A的元素的赋值四元式的时候，应该注销所有以=为标记，A为左节点的节点。从而不可能在此节点的标识符表中再附上其他的标识符。 处理对指针所指空间的赋值的时候，同样要注销相应的节点。如果不能确定指针指向的范围，那么，需要注销所有的节点。,A,i,=,j,=,t1,t2,y,&=,=,从DAG图到四元式序列,在DAG图中，有些运算已经进行了合并。 如果不考虑=和&=算符，可以依照DAG图中的拓扑排序得到的次序进行。但是，有了=和&=算符之后，计算的次序必须修正。 实际上，我们可以按照各个节点生成的顺序来从DAG图生成四元式序列。,从DAG重建四元式序列算法,按照DAG图中各个节点的生成

12、次序对每个节点作如下处理： 若是叶子节点，且附加标识符表为空，不生成四元式。 若是叶子节点，标记为x，附加标识符为z，生成= x z。 若是内部节点，附加标识符为z，根据其标记op和子节点数目，生成下列4种形式的四元式。 Op不是=或者=，也不是relop，有两个子节点，生成 op x y z 如果是=或者=，生成op x y z。 如果是relop，生成 relop x y z，z是基本块序号。 只有一个子节点，生成 op x _ z。,从DAG重建四元式序列算法(续),若是内部节点，且无附加标识符，则添加一个局部于本基本块的临时性附加标识符，按照上一情况生成。 如果节点的标识符重包含多个附

13、加标识符z1,z2,zk时： 若是叶子节点，标记为z，生成一系列四元式 = z z1 = z z2 = z zn 不是叶子节点，生成四元式序列： = z z2 = z zn,使用DAG图进行优化的例子 (四元式序列),四元式序列片断: * 4 i t10 = A t10 t11 = t11 x * 4 i t12 = A t12 t13 * 4 j t14 = A t14 t15 &= t15 t13 t13 * 4 j t16 = A t16 t17 &= x t17 t17 i j B2,使用DAG图进行优化的例子 (DAG图),在第10个节点生成后, node(t11)变成无定义.,1:

14、 4,2: i,3: *,t10,4: A,t12,5:=,t11,6:=,t13,8:*,7: j,t14,9: =,t15,10:&=,t16,11:=,t17,12: &=,13: ,B2,x,从DAG图到四元式序列,* 4 i t10 (3) = A t10 t11 (5) := t11 x (5) = A t10 t13 (6) * 4 j t14 (8) = A t14 t15 (9) &= t15 t13 t13 (10) = A t14 t17 (11) &= x t17 t17 (12) i j B2 (13),DAG的其他应用,常量合并: * 2 pi t1 * t1 r

15、t2 = t2 l 无用代码删除: 对于= t10 t12，如果t12不需要使用，那么，这个四元式不需要生成。,与循环有关的优化,循环不变表达式外提。 归纳变量删除。 计算强度削弱,循环不变式（代码）外提,有些表达式位于循环之内，但是该表达式的值不随着循环的重复执行而改变，该表达式被称为循环的不变表达式。 如果按照前面讲的代码生成方案，每一次循环都讲计算一次。 如果把这个表达式提取到循环外面，该计算就只被执行一次。从而可以获得更加好的效率。,循环不变式的例子,计算半径为r的从10度到360度的扇形的面积： for(n=1; n36; n+) S:=10/360*pi*r*r*n; printf

16、(“Area is %f”, S); 显然，表达式10/360*pi*r*r中的各个量在循环过程中不改变。可以修改程序如下： C= 10/360*pi*r*r*n; for(n=1; n36; n+) S:=C*n; printf(“Area is %f”, S); 修改后的程序中，C的值只需要被计算一次，而原来的程序需要计算36次。,四元式的循环不变式,(1)= 1 n (2) n 36 (21) (3)GOF (4) (4)/ 10 360 tl (5)* tl pi t2 (6)* t2 r t3 (7)* t3 r t4 (8)* t4 n t5 (9)= t5 S (18)+ n 1

17、 t9 (19)= t9 n (20)GO (4) (21) 其中，四元式4,5,6,7是循环不变四元式。,循环不变四元式的相对性,对于多重嵌套的循环，循环不变四元式是相对于某个循环而言的。可能对于更加外层的循环，它就不是循环不变式。 例子： 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、么条件下，不变表达式可以外提？,归纳变量的删除（例子）,例子： Prod=0; i = 1; for(i = 1; i= 20; i+) prod += prod+A4*i*B4*i; * 4 i t1 = a t1 t2 * 4 i t3 = b t3 t4 * t2 t4 t5 + prod t5 t6 = t6 prod + i 1 t7 = t7 i = i 20 B2 i作为计数器。每次重复，i的值增加1，而Ai, Bi对应的地址t1, t3增加4。 我们可以删除i，而使用t1或者t3进行循环结束条件的测试。,归纳变量的删除,在循环中，如果变量i的值随着循环的每次重复都固定地增加或者

19、减少某个常量，则称i为循环的归纳变量。 如果在一个循环中有多个归纳变量，归纳变量的个数往往可以减少，甚至减少到1个。减少归纳变量的优化称为归纳变量的删除。,归纳变量的删除（四元式例子）,= 0 prod = l i,* 4 i t1 = a t1 t2 * 4 i t3 = b t3 t4 * t2 t4 t5 + prod t5 t6 = t6 prod + i 1 t7 = t7 i = i 20 B2,= 0 prod = 0 t1,+ 4 t1 t1 + 4 t3 t3 = a t1 t2 = b t3 t4 * t2 t4 t5 + prod t5 t6 = t6 prod = t1

20、 80 B2,归纳变量的删除,归纳变量的删除一方面可以删除变量，减少四元式，另外，删除归纳变量同时也削减了计算强度。 为了进行归纳变量删除优化，必要的是找出归纳变量。,计算强度削弱,在删除归纳变量的过程中,已经将一些乘法运算转换成为加法运算。 还有一类经常可以被应用的是对于下标变量地址的计算。,计算强度削减（下标变量）,对于数组T an1n2nm，其下标变量ai1i2i3im的地址计算如下： base+d；其中base为a000的地址。 d=(i1*n2+i2)*n3+i3)*nm+im)*sizeof(T); 当满足某些情况的时候，地址的计算可以使用加法来代替乘法。,下标变量计算强度的削减（

21、例子）,for(v1=v10; v1v1f; v1+) for(v2=v20; v2v2f; v2+) Ai1i2i3 i1, i2, i3都可以表示成为：Ck0+Ck1*V1+Ck2*V2(k=1,2,3); Ai1i2i3的地址为base+d; d=(i1*n2*n3+i2*n3+i3); 将i1,i2,i3的表达式代入d的表达式，可以得到d=C0+C1*V1+C2*V2.,下标变量计算强度的削减（例子）,显然，在上面的例子中，每次内循环d的值增加C2；每次外循环, d的值增加C1（但是V2被重置）。 显然我们可以这样计算Ai1i2i3的地址： 在循环开始的时候，设置初值d1=(base+

22、C0)+C1*V10; 在进入外层循环后，进入内存循环前，设置d2=d1+C2*V20 在内存循环，使用d2作为地址获取Ai1i2i3的值。 内存循环体每次运行结束之前，将d2的值增加C2。 每次外层循环体运行结束之前，将d1的值增加C1。 显然，对于Ai1i2i3的地址计算变成了加法运算。,下标变量计算强度的削减结果,D1 = base+C0+C1*V10; for(v1=v10; v1v1f; v1+) D2 = D1+C2*V20; for(v2=v20; v2v2f; v2+) *D2; D2+=C2; D1+= C1; ,下标地址优化计算的条件,相应的数组是常界数组：数组的上下界都是

23、常量。 下标变量中的下标表达式是循环控制变量的线性表达式。 满足上述条件的称为可优化下标变量。 在C语言中，要求循环控制变量每次循环的变动是常数。,循环优化的实现,循环结构的识别 数据流分析 代码转换,循环结构的识别,对于源程序来说，识别循环是比较方便的。但是代码的优化是针对四元式序列的，所以识别循环必须针对流图进行。 定义8.3 如果流图中，从某个初始节点出发，每一条到达节点n的路径都必须经过m，那么称m是节点n的必经节点。记为m dom n。 任何节点都是自己的必经节点。 m为n的前驱，n为m的后继。 直接必经节点：从初始节点到达n的所有路径上，节点n的最后一个必经节点称为直接必经节点。,

24、循环满足的条件,循环必须有唯一的入口节点，称为首节点。 对于循环中任何一个节点，必定至少有一个路径回到首节点。,回边和自然循环,定义8.4 假定流图中存在两个节点M和N满足M dom N。如果存在从节点N到M的有向边N-M，那么这条边称为回边。 定义8.5 在流图中，给定一个回边N-M，对应与这个回边的自然循环为：M，以及所有可以不经过M而到达N的节点。M为该循环的首节点。 用节点的集合表示自然循环。,自然循环的例子,3 dom 4 回边4-3 4 dom 7 回边7-4 10-7的自然循环7，8，10 7-4的自然循环4,5,6,7,8,10 4-3，8-3的自然循环3,4,5,6,7,8,

25、10,回边寻找算法,首先列出所有从首节点开始，不带圈的路径。 节点N的必经节点的集合为满足以下条件的节点M： 所有包含N的路径P, M都在N的前面出现。 回边集合如下： NM | N是一个节点，M在N的必经节点集合中,寻找自然循环的算法,输入:回边N-M; 输出: 回边对应的自然循环. 算法: 设置loop=N,M; push(stack, N); while non-empty(stack) do m = top(stack); pop(stack); for m的每个前驱节点p if p is_not_in loop then loop += p; push(stack,p); ,算法的说

26、明,节点M在初始时刻已经在loop中所以, M的前驱不可能被加入到loop中。 如果N-M不是回边，那么，首节点会被加入到loop中。此时算法不能得到自然循环。,相关概念,通常，循环互不相交，或者一个在另外一个里面。 内循环：不包含其他循环的循环称为内循环。 如果两个循环具有相同的首节点，那么很难说一个包含另外一个。此时把两个循环合并。,B0,B1,B2,B3,可归约流图,可归约流图：删除了其中回边之后，可以构成无环有向图的流图。 特性：不存在循环外向循环内部的转移，进入循环必须通过其首节点。 实际的程序对应的流图一般都是可归约的流图。 没有goto语句的结构化程序的流图总是可归约的。一般使用

27、goto语句的程序也是可归约的。,B1,B2,B3,数据流分析相关概念,变量获得值的方式： 通过赋值语句； 通过输入语句； 通过过程形式参数； 点：流图基本块中的位置，包括：第一个四元式之前，两个相邻四元式之间，和最后的四元式之间。 定值：使变量x获得值的四元式称为对x的定值，一般用四元式的位置表示。 引用点：引用某个变量x的四元式的位置称为x的引用点。,数据流分析的种类,到达-定义数据流方程 活跃变量数据流方程 可用表达式数据流方程,到达-定义数据流方程,到达-定义：假定x有定义d，如果存在一个路径，从紧随d的点到达某点p，并且此路径上面没有被注销，则称x的定义d到达p。这表明，在p点使用变

28、量x的时候，x的值可能是由d点赋予的。 引用-定义链：设变量x有一个引用点u，变量x的所有能过到达u的一切定义称为x在u点处的引用-定义链，简称ud链。 显然，通过变量x在引用点u的ud链，可以判断x是否循环不变的。,到达定义数据流方程（记号）,INB: 表示基本块B的入口点处各个变量的定点集合。 如果B中点p之前有x的定义点d，且这个定义能够到达p，则点p处x的ud链是d。 否则，点p处x的ud链就是IBB中关于x的定义点的集合。 PB：B的所有前驱基本块的集合。 GENB：各个变量在B内定义，并能够到达B的出口点的所有定义的集合。 OUTB：各个变量的能够到达基本块B的出口点的所有定义的集

29、合。 KILLB：是各个变量在基本块B中重新定义，即在此块内部被注销的定义点的集合。,到达定义数据流方程,INB = OUTp where p isin PB OUTB = GENB(INB-KILLB) 其中： GENB可以从基本块中求出：使用DAG图就可以得到。 KILLB中，对于整个流图中的所有x的定义点，如果B中有对x的定义，那么该定义点在KILLB中。,方程求解算法,使用迭代方法。 初始值设置为：INBi=空；OUTB=GENBi; change = TRUE; while(change) change = FALSE; for each B do INB = OUTp where

30、p isin PB; OUTB = GENB(INB-KILLB); oldout = OUTB; if(OUTB != oldout) change = TRUE; ,算法例子,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,计算过程,初始化： INB1 = INB2 = INB3 = INB4 =空 OUTB1=d1,d2,d3, OUTB2=d4,d5 OUTB3=d6, OUTB4=d7. 第一次循环： I

31、NB1=空; INB2 =d1,d2,d3,d7; INB3=d4,d5; INB4=d4,d5,d6; OUTB1=d1,d2,d3; OUTB2=d3,d4,d5 结果： 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;,活跃变量数据流方程,判断在基本块出口之后，变量的值是否还被引用的这种判断工作称为活跃变量分析。 消除复写四元式的依据就是对活跃变量的分析。如果某个变量

32、的值在以后不被引用，那么该复写四元式可以被消除。 对于变量x和流图上的某个点p，存在一条从p开始的路径，在此路径上在对x定值之前引用变量x的值，则称变量x在点p是活跃变量，否则称x在点p不活跃。 无用赋值：对于x在点p的定值，在所有基本块内不被引用，且在基本块出口之后又是不活跃的，那么x在点p的定义是无用的。,记号,L_INB: 基本块B的入口点的活跃变量集合。 L_OUTB: 是在基本块B的出口点的活跃变量集合。 L_DEFB: 是在基本块b内的定值，但是在定义前在B中没有被引用的变量的集合。 L_USEB: 表示在基本块中引用，但是引用前在B中没有被定义的变量集合。 其中，L_DEFB和L

33、_USEB是可以从基本块B中直接求得的量，因此在方程中作为已知量。,活跃变量数据流方程,L_INB = L_USEB(L_OUTB-L_DEFB) L_OUTB = L_INs，其中s遍历B的所有后继。 变量在某点活跃，表示变量在该点的值在以后会被使用。 第一个方程表示： 如果某个变量在B中没有定义就使用了，显然，变量在在入口处的值会被使用。 如果这个变量在B的出口处活跃，并且B中没有对他进行定义，那么变量在入口处也是活跃的。 第二个方程表示： 在B的某个后记中会使用该后继的入口处的值，那么他其实也可能使用B的出口处的值。,活跃变量数据流方程求解,设置初值：L_INBi=空; 重复执行一下步骤

34、直到L_INBi不再改变： for(i=1; in; i+) L_OUTBi= L_INs; s是Bi的后继； L_INBi=L_USEBi(L_OUTBi-L_DEFBi); ,活跃变量数据流方程例子,L_DEFB1=i,j,a L_USEB1=m,n, u1 L_DEFB2=空 L_USEB2=i,j L_DEFB3=a L_USEB3=u2 L_DEFB4=i L_USEB4=u3,迭代过程,第一次循环： L_OUTB1=空 L_INB1=m,n,u1 L_OUTB2=空 L_INB2=i,j L_OUTB3=i,j L_INB3=i,j,u2 L_OUTB4=i,j,u2 L_INB4

35、=j,u2,u3 第二次循环： L_OUTB1=i,j,u2,u3 L_INB1=m,n,u1,u2,u3 L_OUTB2=i,j,u2,u3 L_INB2=i,j,u2,u3 L_OUTB3=i,j,u2,u3 L_INB3=i,j,u2,u3 L_OUTB4=i,j,u2,u3 L_INB4=j,u2,u3 第三次循环各个值不再改变，完成求解。,可用表达式数据流方程,如果一个流图的首节点到达点p的每个路径上面都有对x op y的计算，并且在最后一个这样的计算到点p之间没有对x,y进行定值，那么表达式x op y在点p是可用的。 表达式可用的直观意义：在点p上，x op y已经在之前被计算过

36、，不需要重新计算。 注意：如果对于有间接赋值四元式的情况，需要保证最后的计算x op y的点之间不会间接改变x,或者y的值：比如指针不会指向x或者y的存储区域，特别是当x为某个数组的时候。 书上的讲解是针对没有间接赋值四元式的情况处理的。,概念,对表达式的注销：如果某个基本块B对x或者y定值，且以后没有重新计算x op y，那么称B注销表达式x op y。 表达式的产生：如果某个基本块B对x op y进行计算，而以后并没有在对x或者y重新定值，那么称B产生表达式x op y。 表达式的全集：在计算某个流图中的可用表达式的时候，表达式的讨论范围被限定在该出现在流图中的四元式对应的表达式。,记号,

37、E_OUTB：在基本块出口处的可用表达式集合。 E_INB：在基本块入口处的可用表达式集合。 E_GENB：基本块B所产生的可用表达式的集合。 E_KILLB：基本块B所注销掉的可用表达式的集合。 E_GENB和E_KILLB的值可以直接从流图计算出来。因此在数据流方程中，可以将E_GENB和E_KILLB当作已知量看待。,E_GENB的计算,对于一个基本块B，E_GENB的计算过程如下： 初始设置：E_GENB=空； 顺序扫描每个四元式： 对于四元式op x y z，把x op y加入E_GENB， 从E_GENB中删除和z相关的表达式。 最后的E_GENB就是相应的集合。,E_KILLB的

38、计算,设流图的表达式全集为E; 初始设置：EK = 空； 顺序扫描基本块的每个四元式： 对于四元式op x y z，把表达式x op y从EK中消除； 把E中所有和z相关的四元式加入到EK中。 扫描完所有的四元式之后，EK就是所求的E_KILLB。,数据流方程,E_OUTB=(E_INB-E_KILLB)U E_GENB E_INB= E_OUTp B!=B1, p是B的前驱。 E_INB1=空集 说明： 在程序开始的时候，无可用表达式。(3) 一个表达式在某个基本块的入口点可用，必须要求它在所有前驱的出口点也可用。（2） 一个表达式在某个基本块的出口点可用，或者该表达式是由它的产生的；或者该

39、表达式在入口点可用，且没有被注销掉。（1）,方程求解算法,迭代算法 初始化：E_INB1=空; E_OUTB1=E_GENB1;E_OUTBi=U-E_KILLBi(i=2) 重复执行下列算法直到E_OUT稳定: FOR（i=2; i=n ;i+) E_INBi= E_OUTp, p是Bi的前驱； E_OUTBi=E_GENBi (E_INBi-E_KILLBi); ,算法说明,初始化值和前面的两个算法不同。E_OUTBi的初值大于实际的值。 在迭代的过程中，E_OUTBi的值逐渐缩小直到稳定。 U表示四元式的全集，就是四元式序列中所有表达式x op y的集合。,寻找循环不变表达式算法,输入：

40、循环L，已经建立的UD链 输出：不变四元式 步骤1：若四元式的运算分量或者是常数，或者其所有定义点在循环外部，则标记此四元式为不变。 步骤2：重复执行下面的步骤： 如果一个四元式没有被加过标记，且运算分量要么是常数，要么其UD链中的定义点在循环外，或者该定义点已经被加过标记，则标记此四元式为不变。 说明：一个四元式的是不变的，当且仅当其分量在循环中是不变的。主要有三种情况：常量，定义点在循环外部，或者定义点的四元式也是不变的。,不变四元式外提方法,对于不变四元式，可以在进入循环之前首先计算该四元式的值，然后在循环内部使用该值。 可以将四元式的值外体到紧靠循环之前。,首节点,前置节点,代码外提不

41、合法的情况（1）,= 1 i, u v B3,+ u 1 u,- v 1 v = v 20 B5,= i j,= 2 i,代码外提不合法的情况（2）,= 1 i = 3 i, u v B3,= 2 i + u 1 u,- v 1 v = v 20 B5,= i j,代码外提不合法的情况（3）,不变四元式外提的条件,不变四元式s=op x y z可以外提的条件： s所在的基本块节点是循环所有出口节点的必经节点。出口节点是指有后继节点在循环外的节点。（反例：情况1） 循环中z没有其他的定值点。（反例：情况2） 循环中z的引用点仅由s到达。（反例：情况3）,外提算法,步骤1：寻找一切不变四元式。 步

42、骤2：对于找到的每个循环，检查是否满足上面说的三个条件。 步骤3：按照不变四元式找出的次序，把所找到的满足上述条件的四元式外提到前置节点中。 如果四元式有分量在循环中定值，只有将定值点外提后，该四元式才可以外提。,循环不变式外提的例子,= 1 i = 0 k,1) + i 1 k 2) * 2 k t u v B3,+ u 1 u,- v 1 v = v 20 B5,= i j,= 1 i = 0 k, u v B3,+ u 1 u,- v 1 v = v 20 B5,= i j,1)+ i 1 k 2)* 2 k t,关于归纳变量的优化,基本归纳变量：如果循环中，对于i的定值只有形状如i =

43、 i + c的定值，那么i称为循环的基本归纳变量。 归纳变量族：如果循环中对变量j的定值都是形状如j=C1*i+C2，且i为基本归纳变量，那么称j为归纳变量，且属于i族。i属于i族。 对于定值为C1*i+C2的i族归纳变量j，我们用(i,C1, C2)来表示。 对于i族的归纳变量(i,C1, C2)，要求循环内部对此变量进行定值的时候，一定是赋给C1*i+C2。,例子（源程序）,for(i = 0; i100; i+) j = 4*i; printf(“%i”, j); i是基本归纳变量。j是i族归纳变量，可以表示为(i, 4, 0)。,寻找循环的归纳变量算法,步骤1：扫描循环的四元式，找出所

44、有基本归纳变量。对应于每个基本归纳变量的三元组如(i,1,0)。 步骤2：寻找循环中只有一个赋值的变量k，且对它的定值为如下形式，k=j*b, k=b*j, k=j/b, k=j+(-)b, k=b+(-)j。其中j为基本归纳变量，或者已经找到的归纳变量。 如果j为基本归纳变量，那么k属于j族。k对应的三元式可以确定。 如果j不是基本归纳变量，且属于i族，那么我们还要求： 循环中对j的赋值以及和对k的赋值之间没有对i的赋值，且 没有j在循环外的定值可以到达k的这个定值点。 j的三元式可以相应确定。,算法说明,关于j不是基本归纳变量的时候，算法中的两个要求实际上是保证：对k进行赋值的时候，j变量

45、当时的值一定等于C1*（i当时的值）+C2。,归纳变量的计算强度削弱算法,对于每个基本归纳变量i，对其族中的每个归纳变量j(i, c, d)执行下列步骤： 建立新的临时变量t。 用= t j四元式代替对j的赋值。 对于每个定值i=i+n之后，添加t=t+c*n。 在前置节点的末尾，添加四元式* c i t和+ t d t。使得在循环开始的时候, t=c*i+t。 当两个归纳变量具有同样的三元式的时候，可以只建立一个临时变量。,算法的说明,在优化过程中，为j(i,c,d)引入的变量t保证了在任何时刻(不包括在对i新定值后并且在t重新定值前，但是由于两者的四元式时紧连的）都满足t=c*i+d。 如

46、果在某些情况下，程序运行时对j的定值的次数远远少于对i的定值，经过优化的程序需要对t多次赋值，实际的效率可能降低。,归纳变量的删除,有些归纳变量的作用就是控制循环的次数。如果循环出口处的判断可以使用其它的变量代替，那么可以删除这些归纳变量。,归纳变量的删除算法,步骤1：对于每个基本归纳变量，取i族的某个归纳变量j（尽量使得c,d简单）。把每个对i的测试修改称为用j代替。 relop i x B修改为relop i c*x+d B。 relop i1 i2 B，如果能够找到三元组(i1, c,d)和(i2,c,d)，那么可以将其修改为relop j1 j2 B(假设c0)。 如果归纳变量不再被引

47、用，那么可以删除和它相关的四元式。 如果基本归纳变量在循环出口处活跃，上面的算法不可以直接使用。 步骤2：考虑对j的赋值= t j。如果每次对j引用和这个赋值四元式之间没有任何对t的赋值（此时，每次使用j的时候都有t=j)，可以在引用j的地方用t代替，同时删除四元式= t j（如果j在循环的出口处活跃，需要增加= t j）。,全局公共子表达式消除,对于循环中某个四元式op x y z，如果在所有到达这个四元式的路径上，已经计算了x op y，且计算之后x,y的值再没有修改过，那么显然我们可以使用以前计算得到的值。 可用表达式表达的就是这个概念。 如果有四元式op x y z，且在四元式前，表达式x op y可用，那么我们可以用下面