編譯原理：第九章 代碼優(yōu)化

1、第九章 代 碼 優(yōu) 化通過程序變換（局部變換和全局變換）來改進程序，稱為優(yōu)化介紹獨立于機器的優(yōu)化，即不考慮任何目標機器性質(zhì)的優(yōu)化變換流圖中循環(huán)的識別數(shù)據(jù)流分析代碼改進變換9.1 優(yōu)化的主要種類9.1.1 代碼改進變換的標準代碼變換必須保程序的含義采取安全穩(wěn)妥的策略變換減少程序的運行時間平均達到一個可度量的值變換所作的努力是值得的9.1 優(yōu)化的主要種類本節(jié)所用的例子i = m 1; j = n; v = an;(1) i := m 1while (1) (2) j := n do i = i +1; while(aiv);(4) v := at1 if (i = j) break;(5) i :

2、= i + 1 x=ai; ai=aj; aj=x;(6) t2 := 4 * i (7) t3 := at2 x=ai; ai=an; an=x;(8) if t3 v goto (5)9.1 優(yōu)化的主要種類本節(jié)所用的例子i = m 1; j = n; v = an;(9) j := j 1 while (1) (10) t4 := 4 * j do i = i +1; while(aiv);(12) if t5v goto (9) if (i = j) break;(13) if i =j goto (23) x=ai; ai=aj; aj=x;(14) t6 := 4 * i(15 )

3、x := at6x=ai; ai=an; an=x;. . .9.1 優(yōu)化的主要種類i := m 1j := nt1 := 4 * nv := at1i := i + 1t2 := 4 * it3 := at2if t3 v goto B3if i = j goto B6B4B3B5B69.1 優(yōu)化的主要種類9.1.2 公共子表達式刪除B5 x=ai; ai=aj; aj=x;t6 := 4 * ix := at6t7 := 4 * i t8 := 4 * jt9 := at8at7 := t9t10 := 4 * jat10 := xgoto B29.1 優(yōu)化的主要種類B5 x=ai; ai

4、=aj; aj=x;t6 := 4 * ix := at6t7 := 4 * i t8 := 4 * jt9 := at8at7 := t9t10 := 4 * jat10 := xgoto B29.1 優(yōu)化的主要種類B5 x=ai; ai=aj; aj=x;t6 := 4 * ix := at6t7 := 4 * i t8 := 4 * jt9 := at8at7 := t9t10 := 4 * jat10 := xgoto B2t6 := 4 * ix := at6t8 := 4 * jt9 := at8at6 := t9at8 := xgoto B29.1 優(yōu)化的主要種類i := m 1

5、j := nt1 := 4 * nv := at1i := i + 1t2 := 4 * it3 := at2if t3 v goto B3if i = j goto B6B4B3B5B69.1 優(yōu)化的主要種類B5 x=ai; ai=aj; aj=x;t6 := 4 * ix := at6t7 := 4 * i t8 := 4 * jt9 := at8at7 := t9t10 := 4 * jat10 := xgoto B2t6 := 4 * ix := at6t8 := 4 * jt9 := at8at6 := t9at8 := xgoto B29.1 優(yōu)化的主要種類B5 x=ai; ai=

6、aj; aj=x;t6 := 4 * ix := at6t7 := 4 * i t8 := 4 * jt9 := at8at7 := t9t10 := 4 * jat10 := xgoto B2t6 := 4 * ix := at6t8 := 4 * jt9 := at8at6 := t9at8 := xgoto B2x := at2t9 := at4at2 := t9at4 := xgoto B29.1 優(yōu)化的主要種類i := m 1j := nt1 := 4 * nv := at1i := i + 1t2 := 4 * it3 := at2if t3 v goto B3if i = j g

7、oto B6B4B3B5B69.1 優(yōu)化的主要種類B5 x=ai; ai=aj; aj=x;t6 := 4 * ix := at6t7 := 4 * i t8 := 4 * jt9 := at8at7 := t9t10 := 4 * jat10 := xgoto B2t6 := 4 * ix := at6t8 := 4 * jt9 := at8at6 := t9at8 := xgoto B2x := at2t9 := at4at2 := t9at4 := xgoto B29.1 優(yōu)化的主要種類B5 x=ai; ai=aj; aj=x;t6 := 4 * ix := at6t7 := 4 * i

8、 t8 := 4 * jt9 := at8at7 := t9t10 := 4 * jat10 := xgoto B2t6 := 4 * ix := at6t8 := 4 * jt9 := at8at6 := t9at8 := xgoto B2x := at2t9 := at4at2 := t9at4 := xgoto B2x := t3at2 := t5at4 := xgoto B29.1 優(yōu)化的主要種類B6 x = ai; ai = an; an = x;t11 := 4 * ix := at11t12 := 4 * i t13 := 4 * nt14 := at13at12 := t14t

9、15 := 4 * n at15 := x x := t3t14 := at1at2 := t14at1 := x 9.1 優(yōu)化的主要種類B6 x = ai; ai = an; an = x;at1能否作為公共子表達式？t11 := 4 * ix := at11t12 := 4 * i t13 := 4 * nt14 := at13at12 := t14t15 := 4 * n at15 := x x := t3t14 := at1at2 := t14at1 := x 9.1 優(yōu)化的主要種類i := m 1j := nt1 := 4 * nv := at1i := i + 1t2 := 4 *

10、 it3 := at2if t3 v goto B3if i = j goto B6B4B3B5B6把at1作為公共子表達式是不穩(wěn)妥的 9.1 優(yōu)化的主要種類9.1.3 復(fù)寫傳播形成為f := g的賦值叫做復(fù)寫語句優(yōu)化過程中會大量引入復(fù)寫t := d + ea := t 刪除局部公共子表達式期間引進復(fù)寫t := d + eb := tc := tc := d + eb := d + ea := d + e9.1 優(yōu)化的主要種類9.1.3 復(fù)寫傳播形成為f := g的賦值叫做復(fù)寫語句優(yōu)化過程中會大量引入復(fù)寫復(fù)寫傳播變換的做法是在復(fù)寫語句f := g后，盡可能用g代表fx := t3at2 :=

11、t5at4 := t3goto B2x := t3at2 := t5at4 := xgoto B29.1 優(yōu)化的主要種類9.1.3 復(fù)寫傳播形成為f := g的賦值叫做復(fù)寫語句優(yōu)化過程中會大量引入復(fù)寫復(fù)寫傳播變換的做法是在復(fù)寫語句f := g后，盡可能用g代表f復(fù)寫傳播變換本身并不是優(yōu)化，但它給其它優(yōu)化帶來機會常量合并死代碼刪除9.1 優(yōu)化的主要種類9.1.4 死代碼刪除死代碼是指計算的結(jié)果決不被引用的語句一些優(yōu)化變換可能會引起死代碼例：debug := true; debug := false;. . . 測試后改成 . . .if (debug) print if (debug) prin

12、t 9.1 優(yōu)化的主要種類9.1.4 死代碼刪除死代碼是指計算的結(jié)果決不被引用的語句一些優(yōu)化變換可能會引起死代碼例：復(fù)寫傳播可能會引起死代碼刪除x := t3at2 := t5at4 := t3goto B2at2 := t5at4 := t3goto B29.1 優(yōu)化的主要種類9.1.5 代碼外提代碼外提是循環(huán)優(yōu)化的一種循環(huán)優(yōu)化的其它重要技術(shù)歸納變量刪除強度削弱例：while (i = limit 2 ) 變換成t = limit 2;while (i v goto B3B39.1 優(yōu)化的主要種類i := m 1j := nt1 := 4 * nv := at1B1B2j := j 1t4 := t4 4t5 := at4if t5 v goto B3B4B3B5B6t4 := 4 * jif i = j goto B6j := j 1t4 := 4 * jt5 := at4if t5 v goto B3B3除第一次外，t4 = 4 * j在B3的入口一定保持在j := j 1后，關(guān)系t4 = 4 * j + 4也保持9.1 優(yōu)化的主要種類i := m 1j := nt1 := 4 * nv := at1i := i + 1t2 := 4 * it3 := at2if t3 v goto B3if i = j goto B6B4B3B5B6B2也可以進行