i:=m-1 T1:=4*n v: =aT B ii> Fj goto B」B i:=i+1 I2:=4 X: -a 5/x:a/T, B T3:=a[T2 T,:=T if T3<v goto B 2 13 9 a a T,=to 14·-a113 a Tml=T T a T4:=4 goto B if Ts>v goto B3 删除公用子表达式后
❑删除公用子表达式后 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:=a [T6 ] T7 := T6 T8 := T4 T9 :=a [T8 ] a [T7 ]=T9 T10:= T8 a [T10]=x goto B2 B5 T11:= T2 x:=a [T11] T12:= T11 T13:= T1 T14:=a [T13] a [T12]=T14 T15:= T13 a [T15]=x B6
i:=m-1 -n T1:=4*n v: =aT B if i>=i goto B B i:=i+1 T,:=4 x:a T 5x:a T T3:=a[T2 2 6 if T3<v goto B2 13· a 14 a 13 a ITRl=T T 13 T:=4 goto B if Ts>v goto B 口复写传播 T6:=T2把T2的值赋给T6,x=a「T6]引用了T6的值,这中间T6的值没变,可把x:=a T6变为x:=a[T2],称为复写传播
❑复写传播 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:=a [T6 ] T7 := T6 T8 := T4 T9 :=a [T8 ] a [T7 ]=T9 T10:= T8 a [T10]=x goto B2 B5 T11:= T2 x:=a [T11] T12:= T11 T13:= T1 T14:=a [T13] a [T12]=T14 T15:= T13 a [T15]=x B6 T6:= T2把T2的值赋给T6,x:=a [T6]引用了T6的值，这中间T6的值没变，可把x:=a [T6]变为x:=a [T2]，称为复写传播
i:=m-1 -n T1:=4*n v: =aT B if i>=i goto B B i:=i+1 T,:=4 x: =aT 5x:aT T3:=a[T2 2 12:=T if T3<v goto B2 13· To: =a T a Tll a T2l=T9 IT2lFT :=T ITEX T:=4 goto B if Ts>v goto B 复写传播()后
❑复写传播 ( 一 ) 后 i:=m - 1 j:=n T1 :=4*n v:=a[T 1 ] B 1 i:=i+1 T2 :=4*i T 3 :=a[T 2 ] if T 3<v goto B 2 B 2 j:=j - 1 T 4 :=4*j T 5 :=a[T 4 ] if T 5>v goto B 3 B 3 if i>=j goto B 6 B 4 T 6 := T 2 x:=a[T 2 ] T 7 := T 2 T 8 := T 4 T 9 :=a [T 4 ] a [T 2 ]=T 9 T10:= T 4 a [T 4 ]=x goto B 2 B 5 T11:= T 2 x:=a [T 2 ] T12:= T 2 T13:= T 1 T14:=a [T 1 ] a [T 2 ]=T14 T15:= T 1 a [T 1 ]=x B 6
i:=m-1 -n T1:=4*n v: a B if i>=i goto B B =i+1 I2:=4*j x: =aT Bs|x:=a「 5 T3: =aTl 2 if T3<v goto B2 13· To: =a T 14:=a[T1l a T2=T14 10 T EX IT=X TA=4* goto B if ts>y goto B 复写传播()后 进一步考察:在B5里用到了x:=a[T2在B2里已经计算过了,在B5里可以删除公共子表 达式,将x:=a[2改为x:=T3进而通过复写传播把a「T4=x改为a「T4]=T3
❑复写传播(一)后 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:=a[T2 ] T7 := T2 T8 := T4 T9 :=a [T4 ] a [T2 ]=T9 T10:= T4 a [T4 ]=x goto B2 B5 T11:= T2 x:=a [T2 ] T12:= T2 T13:= T1 T14:=a [T1 ] a [T2 ]=T14 T15:= T1 a [T1 ]=x B6 进一步考察：在B5里用到了x:=a[T2]在B2里已经计算过了，在B5里可以删除公共子表 达式，将x:=a[T2]改为x:=T3,进而通过复写传播把a [T4]=x改为a [T4]=T3
i:=m-1 . n T1:=4*n V:-a B ifi>= i goto B6」B i:=i+1 I,:=4*i 2 B 5x: :=aTl 2 T:= T ifT<v goto B2 To:=T 8 13·11 a T2I=Ts 14-V a 10 a T:=4 goto B2 a T=T3 ifTs>v goto B3 复写传播(二)后
❑复写传播 ( 二 ) 后 i:=m - 1 j:=n T1 :=4*n v:=a[T 1 ] B 1 i:=i+1 T2 :=4*i T 3 :=a[T 2 ] if T 3<v goto B 2 B 2 j:=j - 1 T 4 :=4*j T 5 :=a[T 4 ] if T 5>v goto B 3 B 3 if i>=j goto B 6 B 4 T 6 := T 2 x:=T 3 T 7 := T 2 T 8 := T 4 T 9 :=T 5 a [T 2 ]=T 5 T10:= T 4 a [T 4 ]= T 3 goto B 2 B 5 T11:= T 2 x:=T 3 T12:= T 2 T13:= T 1 T14:= v a [T 2 ]=v T15:= T 1 a [T 1 ]= T 3 B 6