《程序设计语言与编译》课程PPT教学课件（高职）第二十五讲 循环优化

3.循环优化 (1)代码外提 (2)强度削弱 °基本归纳变量,i唯一定值,i:=i±c 同族归纳变量,j:=c1*i±C2 则变成j:三j±c1*c,但j必须在循环外赋初 值j:=c1*i±c2

3. 循环优化 (1)代码外提 (2)强度削弱 •基本归纳变量，i有唯一定值，i := i c •同族归纳变量，j := c1  i  c2 则变成j := j  c1  c , 但j必须在循环外赋初 值 j :＝ c1 * i  c2

(3)删除归纳变量 即改用同族归纳变量作为判断条件 例如将1>10改为t2>100+t1 因原来t3:=10*i+t1 而100+t1即10*10+t1

(3)删除归纳变量 即改用同族归纳变量作为判断条件 例如将 i > 10 改为 t3 > 100 + t1 因原来t3 := 10 * i + t1 ， 而100 ＋ t1 即 10 * 10 + t1

优化之 BI B2 (2)if1>10goto(16) B3 (3)t1:=2* 4)t2:=10*1 (5)t3:=2+t1(6)t4:=a0-11 (7)t5:=2 (8)t6:=10*1 (9)t7:=t6+t5(10)t8:=a0-11 11)t9:=t8[t7](12)t10:=t9+1 (13)4|t3]:=t10(14)n:=i+1 (15)goto(2) B4 (16)

(1)i:=1 (2)if i>10 goto (16) (3)t1:=2*j (4)t2:=10*i (5)t3:=t2+t1 (6)t4:=a0-11 (7)t5:=2*j (8)t6:=10*i (9)t7:=t6+t5 (10)t8:=a0-11 (11)t9:=t8[t7] (12)t10:=t9+1 (13)t4[t3]:=t10 (14)i:=i+1 (15)goto (2) (16) …... 优化之前 B1 B2 B3 B4

代码外提后 BI B2 (3)t1:=2 (6)t4:=a0-11 (7)t5:=2* (10)t8:=a0-11 (2ifi>10goo(16) B2 B3 (4)t2:=10*1(5)t3:=t2+t1 (8)t6:=10*1(9)t7:=t6+t5 1)t9:=8[t7](12)t10:=t9+1 (13)t4[t3]:t10(14)i=i+1 (15)goto(2 (16) B4

(1)i:=1 (4)t2:=10*i (5)t3:=t2+t1 (8)t6:=10*i (9)t7:=t6+t5 (11)t9:=t8[t7] (12)t10:=t9+1 (13)t4[t3]:=t10 (14)i:=i+1 (15)goto (2) (16) …... (2)if i>10 goto (16) (3)t1:=2*j (6)t4:=a0-11 (7)t5:=2*j (10)t8:=a0-11 代码外提后 B1 B2’ B2 B3 B4

强度削弱后 BI ()i:=1 B2 3)1:=2*j(6)t4:=a0-11 (7)t5:=2*j (1080 4)t2:=10*1(8)t6:=10* (5)t3:=t2+tl(9)t7:=t6+5 (2)if i>10 goto(16) B2 l1)t9:=8[t7](12)t10:=9+1 B3 (13)4t3]:=t10(14):=i+1 (4)t2:=t2+10(83)t6:=t6+10 (5)t3:=t3+10(9)t7:=t7+10 (15)goto(2) (16) B4

(1)i:=1 (11)t9:=t8[t7] (12)t10:=t9+1 (13)t4[t3]:=t10 (14)i:=i+1 (4’)t2:=t2+10 (8’)t6:=t6+10 (5’)t3:=t3+10 (9’)t7:=t7+10 (15)goto (2) (16) …... (2)if i>10 goto (16) (3)t1:=2*j (6)t4:=a0-11 (7)t5:=2*j (10)t8:=a0-11 (4)t2:=10*i (8)t6:=10*i (5)t3:=t2+t1 (9)t7:=t6+t5 强度削弱后 B1 B2’ B2 B3 B4

删除归纳变量后 BI ()i:=1 B2 3)1:=2*j(6)t4:=a0-11 (7)t5:=2*j(10t8:=a0-11 4)t2:=10*1(8)t6:=10* (5)t3:=t2+tl(9)t7:=t6+5 (2)s:=100+tl (2”)ift3> s goto(16) B2 (1199897(12)1019+1B3 (13)t4[t3]:=t10(4)t2:=t2+10 (8)6:+6+10(5)3=t3+10 (9)t7:t7+10(15)goto(2) (16) B4

(1)i:=1 (11)t9:=t8[t7] (12)t10:=t9+1 (13)t4[t3]:=t10 (4’)t2:=t2+10 (8’)t6:=t6+10 (5’)t3:=t3+10 (9’)t7:=t7+10 (15)goto (2) (16) …... (2’’)if t3>s goto (16) (3)t1:=2*j (6)t4:=a0-11 (7)t5:=2*j (10)t8:=a0-11 (4)t2:=10*i (8)t6:=10*i (5)t3:=t2+t1 (9)t7:=t6+t5 (2’)s:=100+t1 删除归纳变量后 B1 B2’ B2 B3 B4

另例:(1)PROD:=0 2I:=1 (3)T1:于4 (4)T2:=a0-4 (5)T3:=12[T1 (6)T4:=4*I (7)T5:=b0-4 (8)T6:=T5[TI4 (9)17:=T3*T6 (10)PROD: -PROD+ T7 (11)I:=Ⅰ+1 (12)ifI≤20goto(3) 进行:(1)删除多余运算,代码外提 (2)强度削弱 (3)变换循环控制条件,复写传播,合并已知量 (4)删除无用赋值

另例：(1)PROD := 0 (2)I := 1 (3)T1 := 4 * I (4)T2 := a0 – 4 (5)T3 := T2[T1] (6)T4 := 4 * I (7)T5 := b0 – 4 (8)T6 := T5[T4] (9)T7 := T3 * T6 (10)PROD := PROD + T7 (11)I := I + 1 (12)if I ≤ 20 goto (3) 进行:(1)删除多余运算，代码外提 (2)强度削弱 (3)变换循环控制条件，复写传播，合并已知量 (4)删除无用赋值

删除多余运算,代码外提 26?(PROD: =022 (2 (4)T2:=a0-4 (7)T5:=bo-4 (3)T1:=4* (5)T3:=T2[T1 (6)T4:=T (8)16:=1514 (9)T7: T3*T6 (10)PROD: PROD+ T7 (11)I:=I+1 (12)ifI≤20goto(3)

删除多余运算，代码外提 (1)PROD := 0 (2)I := 1 (4)T2 := a0 – 4 (7) T5 := b0 – 4 (3) T1 := 4 * I (5)T3 := T2[T1] (6)T4 := T1 (8) T6 := T5[T4] (9) T7 := T3 * T6 (10) PROD := PROD + T7 (11) I := I +1 (12)if I≤20 goto (3)

强度削弱 3(PROD: 0 2)I:=1 (4)12:=a0-4 (7)T5:=b-4 (3)T1:=4*I (5)T3:=T2[T1] (6)T4:=T1 (8)T6:=T5[4] (9)T7:=T3*T6 10)PROD: PROD+ T7 (11)I:=I+1 (33)T1:=T1+4 (12 )if I< 20 goto(5)

强度削弱 (1)PROD := 0 (2)I := 1 (4)T2 := a0 – 4 (7) T5 := b0 – 4 (3) T1 := 4 * I (5)T3 := T2[T1] (6)T4 := T1 (8) T6 := T5[T4] (9) T7 := T3 * T6 (10) PROD := PROD + T7 (11) I := I +1 (3’)T1 := T1 + 4 (12) if I ≤ 20 goto (5)

变换循环控制条件,合并口知量,复写传播 (1)PROD:=0 (2)=1 (4)12:=a0-4 (7)T5:b-4 (3)T1:=4 (5)T3:=T2[T (6)T4:=T1 (8)T6:=T5[T1] (9)T7:=T3*T6 10)PROD: = PROD+ T7 )I:=1+1 (3)Tl:=T1+4 (12)ifT1≤80goto(5)

变换循环控制条件，合并已知量，复写传播 (1)PROD := 0 (2)I := 1 (4)T2 := a0 – 4 (7) T5 := b0 – 4 (3) T1 := 4 (5)T3 := T2[T1] (6)T4 := T1 (8) T6 := T5[T1] (9) T7 := T3 * T6 (10) PROD := PROD + T7 (11) I := I +1 (3’)T1 := T1 + 4 (12) if T1 ≤ 80 goto (5)