【正文】 )對不變運(yùn)算 P： x:=y op z或 x:=op y或 x:=y， 如果它滿足下述兩組條件中的一組 ?P點所在基本塊是 L所有出口結(jié)點之必經(jīng)結(jié)點； x在 L中沒有其他定值點； L中引用 x處只有 P點的定值才能到達(dá)。 歸納變量刪除 尋找歸納變量 ? 找出所有基本歸納變量 i := i ? c， 描述為 (i, 1, 0)的形式 ? 尋找只有一個賦值的 k， 其形式為 k := j*b, k := b*j, k := j / b, k := j ? b, k := b ? j 其中 b是常數(shù) ， j是基本的或非基本的歸納變量 – 若 j 是基本的且 k := j * b， 則 k屬 j族 ， 為 (j,b,0) – 若 j屬 I族 ， 為 (i, c, d)， k := b * j， 則 k屬 I族 ， 為 (i, b * c, b * d ) 歸納變量刪除 ? 循環(huán) B2 – i族 i: (i, 1, 0) – i族 t2 : (i, 4, 0) ? 循環(huán) B3 – j族 j: (j, 1, 0) – j族 t4 : (j, 4, 0) ? 循環(huán) B B B4和 B5 – 和上面一樣的 i族和 j族 i := m ?1 j := n t1 := 4 * n v := a[t1] B1 B2 i := i +1 t2 := 4 * i t3 := a[t2] if t3 v goto B2 j := j ?1 t4 := 4 * j t5 := a[t4] if t5 v goto B3 if i = j goto B6 B4 B3 B5 B6 歸納變量刪除 歸納變量的強(qiáng)度削弱 i族 j: (i,c,d) ? 用 j := s代替 j的賦值 ? 在每個賦值 i := i + n的后面 ， 緊接著它加上 s := s + c * n i族 s: (s,c,d) ? 在前置塊的末尾 加上 s := c * i /* 如果 c為 1， 則 s := i */ s := s + d /* 如果 d為 0則被省略 */ 歸納變量刪除 ? 循環(huán) B2 – i族 i: (i, 1, 0) – i族 t2 : (i, 4, 0) s2 := 4 * i（ 前置結(jié)點 ） s2 := s2 + 4（ 循環(huán)內(nèi) ） t2 := s2 （ 循環(huán)內(nèi) ） ? 循環(huán) B3 – j族 j: (j, 1, 0) – j族 t4 : (j, 4, 0) s4 := 4 * j（ 前置結(jié)點 ） s4 := s4 + 4（ 循環(huán)內(nèi) ） t4 := s4 （ 循環(huán)內(nèi) ） i := m ?1 j := n t1 := 4 * n v := a[t1] B1 B2 i := i +1 t2 := 4 * i t3 := a[t2] if t3 v goto B2 j := j ?1 t4 := 4 * j t5 := a[t4] if t5 v goto B3 if i = j goto B6 B4 B3 B5 B6 歸納變量刪除 歸納變量刪除 ? if i relop x goto B的測試 （ x不是歸納變量 ） – 取 i族的某個 j， 優(yōu)先取 c=1和 d = 0 的 j:(i,c,d） – 把每個含 i的測試改成對 j的測試 (假定 c為正 ) r := c * x /* 如果 c等于 1， 則 r := x */ r := r + d /* 如果 d為 0， 則省略 */ if j relop r goto B 歸納變量刪除 歸納變量刪除 ? if i relop x goto B的測試 （ x不是歸納變量 ） – 取 i族的某個 j， 優(yōu)先取 c=1和 d = 0 的 j:(i,c,d） – 把每個含 i的測試改成對 j的測試 (假定 c為正 ) r := c * x /* 如果 c等于 1， 則 r := x */ r := r + d /* 如果 d為 0， 則省略 */ if j relop r goto B ? if i1 relop i2 goto B的測試 – 最簡單的情況是 j1:(i1,c1,d1)和 j2:(i2,c2,d2)， 還有c1=c2且 d1=d2 – 那么 ， i1 relop i2等價于 j1 relop j2 歸納變量刪除 歸納變量刪除 ? if i relop x goto B的測試 （ x不是歸納變量 ） – 取 i族的某個 j， 優(yōu)先取 c=1和 d = 0 的 j:(i,c,d） – 把每個含 i的測試改成對 j的測試 (假定 c為正 ) r := c * x /* 如果 c等于 1， 則 r := x */ r := r + d /* 如果 d為 0， 則省略 */ if j relop r goto B ? if i1 relop i2 goto B的測試 – 最簡單的情況是 j1:(i1,c1,d1)和 j2:(i2,c2,d2)， 還有c1=c2且 d1=d2 – 那么 ， i1 relop i2等價于 j1 relop j2 ? 更復(fù)雜的情況 ， 測試的替換可能沒有價值 歸納變量刪除 ? 循環(huán) B2 – i族 i: (i, 1, 0) – i族 t2 : (i, 4, 0) s2 := s2 + 4（ 循環(huán)內(nèi) ） s2 := 4 * i（ 前置結(jié)點 ） ? 循環(huán) B3 – j族 j: (j, 1, 0) – j族 t4 : (j, 4, 0) s4 := s4 + 4（ 循環(huán)內(nèi) ） s4 := 4 * j（ 前置結(jié)點 ） i := m ?1 j := n t1 := 4 * n v := a[t1] B1 B2 i := i +1 t2 := 4 * i t3 := a[t2] if t3 v goto B2 j := j ?1 t4 := 4 * j t5 := a[t4] if t5 v goto B3 if i = j goto B6 B4 B3 B5 B6 歸納變量刪除 ? 循環(huán) B2 – i族 i: (i, 1, 0) – i族 t2 : (i, 4, 0) s2 := s2 + 4（ 循環(huán)內(nèi) ） s2 := 4 * i（ 前置結(jié)點 ） ? 循環(huán) B3 – j族 j: (j, 1, 0) – j族 t4 : (j, 4, 0) s4 := s4 + 4（ 循環(huán)內(nèi) ） s4 := 4 * j（ 前置結(jié)點 ） ? 測試 i = j由 s2 = s4代替 ， i和 j都被刪除 i := m ?1 j := n t1 := 4 * n v := a[t1] B1 B2 i := i +1 t2 := 4 * i t3 := a[t2] if t3 v goto B2 j := j ?1 t4 := 4 * j t5 := a[t4] if t5 v goto B3 if i = j goto B6 B4 B3 B5 B6 歸納變量刪除 強(qiáng)度削弱和刪除歸納變量算法可描述如下： (1) 尋找循環(huán)中的所有基本歸納變量 i 。 (3)設(shè)歸納變量 j 與基本歸納變量 i 的函數(shù)為j=c1*i+c2， 可按下列步驟作強(qiáng)度削弱： ? 在前置結(jié)點原有代碼后增加 s:=c1*I, s:=s+c2,其中 s為增設(shè)的臨時變量， c2=0時，后一語句可省略 歸納變量刪除 ? 循環(huán)中原來 j的賦值改為 j:=s； ? 在基本歸納變量遞歸賦值語句 i:= i177。 (5) 基本歸納變量 i在循環(huán)出口后不活躍，循環(huán)中除遞歸賦值本身外，只在形如 if i rop x goto A或 if x rop i goto A控制語句中被引用，則按下 列步驟刪除歸納變量。 1]試對以下基本塊 B1應(yīng)用 DAG進(jìn)行優(yōu)化。 解： 三地址代碼： (1) I := 1 (2) j := 1 B1 (3) If IM goto (30) (4) If jN goto (13) (5) T1 := I * N (6) T2 := T1 + j (7) T3 := N + 1 (8) T4 := add(A)T3 (9) T5 := add(B)T3 (10) T4[T2] := T5[T2] (11) j := j + 1 (12) Goto (4) (13) I := I+1 (14) j :=1 (15) goto (3) (30) B2 B3 B4 B5 B6 代碼外提： （ 1） I := 1 (2) j := 1 (7) T3 := N + 1 (8) T4 := add(A)T3 (9) T5 := add(B)T3 (3) If IM goto (30) (5) T1 := I * N (4) If j N goto (13) (6) T2 := T1 + j (10) T4[T2] := T5[T2] (11) j := j + 1 (12) goto (4) (13) I := I + 1 (14) j := 1 (15) goto (3) (30) B1 B2’ B2 B3’ B3 B4 B5 B6 強(qiáng)度消弱： (1) I := 1 (2) j := 1 (7) T3 := N + 1 (8) T4 :=add(A) T3 (9) T5 :=add(B)T3 (5’) T1 :=I * N (3) if I M goto (30) (4) If j N goto (13) (6) T2 := T1 + j (10) T4[T2] := T5[T2] (11) j := j + 1 (12) Goto (4) (13) I := I + 1 (5) T1 := T1 + N (14) j := 1 (15) Goto (3) (30) B1 B2’ B2 B3 B4 B5 B6 強(qiáng)度消弱 (1): （ 1） I := 1 (2) j := 1 (7) T3 := N + 1 (8) T4 := add(A)T3 (9) T5 := add(B)T3 (5) T1 := I * N (3) If IM goto (30) (5) T2 := T1 + j (4) If j N goto (13) (10) T4[T2] := T5[T2] (11) j := j + 1 (6)’ T2 := T2 + 1 (12) goto (4) (13) I := I + 1 (5)’ T1 := I + N (14) j := 1 (15) goto (3) (30) B1 B2’ B2 B3’ B3 B4 B5 B6 刪除歸納變量： (1) I := 1 (2) j := 1 (7) T3 := N + 1 (8) T4 := add(A) – T3 (9) T5 := add(B) – T3 (5) T1 := I*N (3’) R := M*N (3) If T1 R goto (30) (4‘ ) Q := T1 + N (4) If T2 Q goto (13) (10) T4[T2] := T5[T2] (11) T2 := T2 + 1 (12) Goto (4) (13) T1 := T1 + 1 (14) T2 := T1 + 1 (15) Goto (3) (30) B1 B2’ B2 B3’ B3 B4 B5 B6 [例 10。 movl $1,%eax j=1 i=5。 jle .L4 while(j?99) } } 例 題 2 一個 C語言程序如下： main() pushl %ebp { movl %esp,%ebp int i,j,k。 cmpl $99,%eax j=j+k。 while (i) { if (j) { i = j。 } 其中的遞歸調(diào)用稱為尾遞歸 .對于尾遞歸 ,編譯器可以產(chǎn)生和一般的函數(shù)調(diào)用不同的代碼 ,使得目標(biāo)程序運(yùn)行時 ,這種遞歸調(diào)用所需的存儲空間大大減少 ,也縮短了運(yùn)行時間 .對于尾遞歸 ,編譯器應(yīng)怎樣產(chǎn)生代碼 ? 例 題 4 求最大公約數(shù)的函數(shù) long gcd(p,q) long