i:=m-1 . n T1:=4*n V:-a B ifi>= i goto B6」B H+1 I,:=4*i 11 B T:=T 5|x: :=aTl 2 ifT3<v goto B2 T:T 12 T:=T 13 a 5 a T21 10° a T:=4 goto B2 a T1=T3 if Ts>v goto B 删除无用赋值 复写传播的目的是为了使某些赋值变得无用,对于进行了复写传播的变量,由于这些 变量在整个程序中都不再使用,因此它们的赋值对程序没有任何影响,可删去
❑删除无用赋值 i:=m-1 j:=n T1 :=4*n v:=a[T1 ] B1 i:=i+1 T2 :=4*i T3 :=a[T2 ] if T3<v goto B2 B2 j:=j-1 T4 :=4*j T5 :=a[T4 ] if T5>v goto B3 B3 if i>=j goto B6 B4 T6 := T2 x:=T3 T7 := T2 T8 := T4 T9 :=T5 a [T2 ]=T5 T10:= T4 a [T4 ]= T3 goto B2 B5 T11:= T2 x:=T3 T12:= T2 T13:= T1 T14:= v a [T2 ]=v T15:= T1 a [T1 ]= T3 B6 复写传播的目的是为了使某些赋值变得无用，对于进行了复写传播的变量，由于这些 变量在整个程序中都不再使用，因此它们的赋值对程序没有任何影响，可删去
i:=m-1 -n T1:=4*n v: =aT B if i>=j goto B6B i:=i+1 T,:=4 5 T3:=a[T2 2 if T3<v goto B2 a 2 a 2 goto B3 a 2 T:=4 if Ts>v goto B 删除无用赋值后
❑删除无用赋值后 i:=m-1 j:=n T1 :=4*n v:=a[T1 ] B1 i:=i+1 T2 :=4*i T3 :=a[T2 ] if T3<v goto B2 B2 j:=j-1 T4 :=4*j T5 :=a[T4 ] if T5>v goto B3 B3 if i>=j goto B6 B4 a [T2 ]=T5 a [T4 ]= T3 goto B2 B5 a [T2 ]=v a [T1 ]=T3 B6
i:=m-1 . n T1:=4*n V:-a B ifi>= i goto B6」B i:=i+1 T:=4*i B 5 T3: =aTl 2 ifa<v goto B2 a 215 a 2 a goto B2 if Ts>v goto B 强度削弱
❑强度削弱 i:=m-1 j:=n T1 :=4*n v:=a[T1 ] B1 i:=i+1 T2 :=4*i T3 :=a[T2 ] if T3<v goto B2 B2 j:=j-1 T4 :=4*j T5 :=a[T4 ] if T5>v goto B3 B3 if i>=j goto B6 B4 a [T2 ]=T5 a [T4 ]= T3 goto B2 B5 a [T2 ]=v a [T1 ]=T3 B6
i:=m-1 T1:=4*n v:=aTl B ifi>= i goto B6」B TA:=4 i:=i+1 B 5 a T3:=a[T2 215 a 2 f T3<v goto B goto B2 a T=T3 B3 Ts: =aTl ifte>y goto B 口强度削弱后 将循环内的乘法运算变为循环外的一次乘法和循环内的加、减法运算
❑强度削弱后 i:=m-1 j:=n T1 :=4*n v:=a[T1 ] T2 :=4*i T4 :=4*j B1 i:=i+1 T2 := T2+4 T3 :=a[T2 ] if T3<v goto B2 B2 j:=j-1 T4 := T4 -4 T5 :=a[T4 ] if T5>v goto B3 B3 if i>=j goto B6 B4 a [T2 ]=T5 a [T4 ]= T3 goto B2 B5 a [T2 ]=v a [T1 ]=T3 B6 将循环内的乘法运算变为循环外的一次乘法和循环内的加、减法运算
i:=m-1 J: -n T1:=4 l· v:=aT1 B fi>= i goto B6」B T:=4*i TA=4* i:=i+1 5 2 a 2 a a 2 ift <y goto B a goto B 2 s:=a[T4l fTs>v goto B 删除归纳变量 注意到每次循环加1,而始终保持2=4*的线性关系,而j每次循环减1,而4始终保持t4=4」的线性关系。这种变量 称为归纳变量。注意到除了在B4的条件判断外,其他地方都不用,因此可将条件 goto B6变为>=4 oB6删去B2和B3中和的代码
❑删除归纳变量 i:=m-1 j:=n T1 :=4*n v:=a[T1 ] T2 :=4*i T4 :=4*j B1 i:=i+1 T2 := T2+4 T3 :=a[T2 ] if T3<v goto B2 B2 j:=j-1 T4 := T4 -4 T5 :=a[T4 ] if T5>v goto B3 B3 if i>=j goto B6 B4 a [T2 ]=T5 a [T4 ]= T3 goto B2 B5 a [T2 ]=v a [T1 ]=T3 B6 注意到i每次循环加1,而t2始终保持t2=4*i的线性关系，而j每次循环减1,而t4始终保持t4=4*j的线性关系。这种变量 称为归纳变量。注意到i和j除了在B4的条件判断外，其他地方都不用，因此可将条件if i>=j goto B6变为if t2>=t4 goto B6,删去B2和B3中i和j的代码