7.4 与循环有关的优化 循环部分在一个程序中可能仅占很小比例，然而运行时间可能在整个运行时间上占到很大部分。因此，对循环的优化往往是改进程序质量的关键。减少循环结构内的指令数，即使增加了循环外的指令，也会使程序的运行时间大大减少。 7.4.1 循环优化的种类 与循环有关的优化有： 循环不变表达式外提 归纳变量删除 计算强度削减 归纳变量计算强度削减 数组元素存储地址计算强度削减,1. 循环不变表达式外提 概念：循环不变表达式，是循环中，其值不随循环的重复执行而变化的表达式。例如， for (k=1; k=18; k=k+1) S=0.5*a*b*sin(10*(pi/180)*k); printf(“a=%f,b=%f,夹角是%d时三角形面积=%8.2fn“, a, b, k*10, S); 改写成下列形式，功效的提高是明显的。 c1=0.5*a*b; c2=10*(pi/180); for (k=1; k=18; k=k+1) S=c1*sin(c2*k); printf(“a=%f,b=%f,夹角是%d时三角形面积=%fn“, a,b,k*10, S); 注意：优化是在内部中间表示级进行的,这里仅说明思路。,又如， for (i=1; i=m; i=i+1) for (j=1; j=n; j=j+1) c1=0.5*ai*bj; c2=10*(pi/180); for (k=1; k=18; k=k+1) S=c1*sin(c2*k); printf(“a=%f,b=%f,夹角是%d时三角形面积=%fn“, ai, bj, k*10, S); 应用循环不变表达式外提优化的思想，又可改写成： c2=10*(pi/180); for (i=1; i=m; i=i+1) c1i=0.5*ai； for (j=1; j=n; j=j+1) c1=c1i*bj; for(k=1; k=18; k=k+1) S=c1*sin(c2*k); printf(“a=%f,b=%f,夹角是%d时三角形面积=%fn“,ai,bj,k*10, S); 功效的提高尤其明显,如10*(pi/180)的计算次数从18mn次减少到1次。,进行与循环相关的优化时，应首先对照翻译方案，按规范方式把循环结构展成由if和goto语句组成的等价结构，然后写出四元式序列，再进行优化。 规范展开如下： 对于while语句： while (E) S 展开成： Loop：if (E) S goto Loop; 对于do-while语句： do S while (E); 展开成： Loop：S if (E) goto Loop； 对于for语句： for(E1; E2; E3) S 展开成： E1；Loop：if(E2) goto Finish； S E3； goto Loop； Finish：,例 for (k=1; k=18; k=k+1) S=0.5*a*b*sin(10*(pi/180)*k); printf(“a=%f,b=%f,夹角是%d时三角形面积=%8.2fn“, a, b, k*10, S); 其中pi为常量3.1416。 规范展开如下： k=1; Loop: if(!(k=18) goto Finish; S=0.5*a*b*sin (10*(pi/180)*k); printf(“a=%f,b=%f,夹角是%d时三角形面积=%fn“, a, b, k*10, S); k=k+1; goto Loop; Finish :,然后写出相应的四元式序列如下。 (1) := 1 k (13) := t7 S (2) = k 18 (5) (14) * k 10 t8 (3) GO (4) (15) PARAM “ a=%f,b=%f,n“ (4) GO (24) (16) PARAM a (5) * 0.5 a t1 (17) PARAM b (6) * t1 b t2 (18) PARAM t8 (7) / pi 180 t3 (19) PARAM S (8) * 10 t3 t4 (20) CALL printf 5 (9) * t4 k t5 (21) + k 1 t9 (10) PARAM t5 (22) := t9 k (11) CALL sin 1 t6 (23) GO (2) (12) * t2 t6 t7 (24) 可优化的是 。 注意，如果把计算S的表达式改写成： S=a*b/2*sin (k*10*(pi/180); 还能进行循环不变表达式外提优化吗？,循环不变表达式外提的优化必须解决的几个问题： 1)如何识别循环中的不变表达式? 2)把循环不变表达式外提到何处? 3)什么条件下可以外提循环不变表达式?,2. 归纳变量删除 循环的归纳变量: 在循环中每次重复执行循环体，都增加或减少某个固定常量值的变量。 归纳变量删除优化：减少归纳变量个数的优化。 归纳变量删除优化之例。,例 假定要求计算首项为3与等差为3的等差数列前30项之和S。通常可写出如下的C程序： S=0； for(k=1; k=30; k=k+1) j=3*k; S=S+j; 首先按规范方式展开上述for循环如下： S=0; k=1; Loop: if (!(k=30) goto Finish; j=3*k; S=S+j; k=k+1; goto Loop; Finish: 易见有归纳变量k与j。,从源程序级上看，可删除k, 用关于j的比较控制循环次数。修改如下： S=0; j=0; Loop: if (!(j90) goto Finish; j=j+3; S=S+j; goto Loop; Finish: 考察相应的四元式序列： (1) := 0 S (7) := t1 j (2) := 1 k (8) + S j t2 (3) = k 30 (6) (9) := t2 S (4) GO (5) (10) + k 1 t3 (5) GO (13) (11) := t3 k (6) * 3 k t1 (12) GO (3) 其中有归纳变量k、j、t1与t3，可以删除k、j与t3。,最终可写出四元式序列如下： (1) := 0 S (6) + t1 3 t1 (2) := 0 t1 (7) + S t1 t2 (3) = t1 87 (6) (8) := t2 S (4) GO (5) (9) GO (3) (5) GO (10) 显然，删除了变量k的四元式序列与删除之前的四元式序列等价。 概括起来，归纳变量删除优化是减少循环的归纳变量个数的优化。 在进行归纳变量删除优化时，要点是： 找出要删除的归纳变量 确定要进行的等价变换,3. 计算强度削减 两类：对循环中归纳变量计算强度的削减 对数组元素地址计算的计算强度削减 对循环中归纳变量计算强度的削减 原有的四元式 (6) * 3 k t1 运算是乘法*，而在归纳变量删除优化之后成为 (6) + t1 3 t1 其中的运算是加法+，因此关于归纳变量t1的计算强度消减了。,(2)* 数组元素的存储地址计算的计算强度削减 数组元素的存储地址计算: T An 定义的一维数组A, 元素Ai之存储地址为: base+(i1)sizeof(T)= (basesizeof(T) +isizeof(T) T An1n2 定义的二维数组，元素Aij之存储地址为： base+(i-1)n2+(j-1)sizeof(integer) =(base- (1n2+1)sizeof(integer) + (in2+j)sizeof(integer),T An1n2nm定义的m维数组A， 元素Ai1i2im的地址可确定如下： base+(i11)n2n3nm +(i21) n3n4nm+ +(im-11)nm+(im 1) sizeof(T) =base (n2+1)n3+1)nm+1)sizeof(T) +(i1n2+i2)n3+i3)nm+im)sizeof(T) 让 C=(n2+1)n3+1)nm+1)sizeof(T) d=(i1n2+i2)n3+i3)nm+im)sizeof(T) 则Ai1i2im的地址为： baseC+d,循环中数组元素地址计算强度削减优化的基本思想：当满足某些特定条件时，使计算d时的乘法用加法来替代。 for(V1=v10; V1=v1f; V1=V1+1) for(V2=v20; V2=v2f; V2=V2+1) Ai1i2i3 如果诸ik 形如Ck0+Ck1V1+Ck2V2(k=1,2,3), 其中Ck0、Ck1、Ck2都是常量, 则Ai1i2i3地址计算base-C+d中， d=(C10+C11V1+C12V2)n2n3 +(C20+C21V1+C22V2)n3 +(C30+C31V1+C32V2) =(C10n2n3+C20n3+C30) +(C11n2n3+C21n3+C31)V1 +(C12n2n3+C22n3+C32)V2 = C0+C1V1+C2V2,循环中数组元素地址之计算能进行优化的条件是： 1)相应数组是常界数组 2)数组元素中的下标表达式ik(k=1,2,m,m是数组维数)是循环控制变量Vj (j=1,2,n, n是循环嵌套层数)的线性式： ik=Ck0+Ck1V1+Ck2V2+CklVl 其中，Ck0、Ck1、Ckl 都是整型常量。,V1=v10； D1=(baseC+C0)+C1*V1; L1：if(V1v1f) goto EXIT1； V2=v20; D2=D1+C2*V2; L2：if (V2v2f) goto EXIT2； . 通过D2引用Ai1i2i3或对其赋值 . V2=V2+1; D2=D2+C2; goto L2； EXIT2： V1=V1+1; D1=D1+C1; goto L1； EXIT1：,7.4.2 循环优化的基础 1. 流图与循环结构的识别 为了清晰地表达四元式序列中各基本块之间的控制联系，引进流图的概念。 流图是把控制流信息加到基本块集合所形成的有向图。现在流图中的结点是基本块，结点之间的有向边代表控制流。一个结点，如果相应的基本块中第一个四元式是四元式序列的第一个四元式，称该结点是流图的首结点。 思路：以流图为基础，在流图中找自然循环。 结点m是结点n的必经结点：如果流图中从某初始结点出发，每条到达结点 n 的路径都要经过结点 m，表示为m dom n。 循环的入口结点是循