【正文】 第十章 代 碼 優(yōu) 化 通過(guò)程序變換（局部變換和全局變換）來(lái)改進(jìn)程序，稱為優(yōu)化 ? 介紹獨(dú)立于機(jī)器的優(yōu)化，即不考慮任何目標(biāo)機(jī)器性質(zhì)的優(yōu)化變換 ? 流圖中循環(huán)的識(shí)別 ? 數(shù)據(jù)流分析 ? 代碼改進(jìn)變換 引言 代碼改進(jìn)變換的標(biāo)準(zhǔn) ? 代碼變換必須保程序的含義 ? 采取安全穩(wěn)妥的策略 ? 變換減少程序的運(yùn)行時(shí)間平均達(dá)到一個(gè)可度量的值 ? 變換所作的努力是值得的 引言 性能的提高 優(yōu)化可以在源程序階段也可以在編譯階段進(jìn)行。算法有優(yōu)劣，有適用范圍。源程序設(shè)計(jì)時(shí)算法的選擇極需斟酌，需要在時(shí)間復(fù)雜性、空間復(fù)雜性上作出比較以決定對(duì)算法的取舍。例如對(duì) N個(gè)元素排序，插入排序需要， 而快速排序則為 12Nlog2Nμs， 當(dāng)N=100時(shí)兩者速度差 ，而當(dāng) N=100000時(shí)，速度差 1000余倍。很明顯，源程序階段的優(yōu)化不是編譯程序能夠和應(yīng)該完成的。 引言 優(yōu)化編譯器的組織 ? 實(shí)現(xiàn)高級(jí)結(jié)構(gòu)的操作在中間代碼中是顯式的 ? 中間代碼基本上獨(dú)立于目標(biāo)機(jī)器 前 端 代 碼 生成器 代 碼 優(yōu)化器 變 換 數(shù)據(jù)流 分 析 控制流 分 析 優(yōu)化的主要種類 本節(jié)所用的例子 i = m ?1。 j = n。 v = a[n]。 (1) i := m ?1 while (1) { (2) j := n do i = i +1。 while(a[i]v)。 (3) t1 := 4 * n do j =j ?1。while (a[j]v)。 (4) v := a[t1] if (i = j) break。 (5) i := i + 1 x=a[i]。 a[i]=a[j]。 a[j]=x。 (6) t2 := 4 * i } (7) t3 := a[t2] x=a[i]。 a[i]=a[n]。 a[n]=x。 (8) if t3v goto (5) 優(yōu)化的主要種類 本節(jié)所用的例子 i = m ?1。 j = n。 v = a[n]。 (9) j := j ?1 while (1) { (10) t4 := 4 * j do i = i +1。 while(a[i]v)。 (11) t5 := a[t4] do j =j ?1。while (a[j]v)。 (12) if t5v goto (9) if (i = j) break。 (13) if i =j goto (23) x=a[i]。 a[i]=a[j]。 a[j]=x。 (14) t6 := 4 * i } (15 ) x := a[t6] x=a[i]。 a[i]=a[n]。 a[n]=x。 . . . 優(yōu)化的主要種類 i := m ?1 j := n t1 := 4 * n v := a[t1] i := i + 1 t2 := 4 * i t3 := a[t2] if t3 v goto B2 B1 B2 j := j ?1 t4 := 4 * j t5 := a[t4] if t5 v goto B3 if i = j goto B6 B4 B3 B5 B6 局部?jī)?yōu)化 t6 := 4 * I x := a[t6] t7 := 4 * i t8 := 4 * j t9 := a[t8] a[t7] := t9 t10 := 4 * j a[t10] := x goto B2 t11 := 4 * i x := a[t11] t12 := 4 * i t13 := 4 * n t14 := a[t13] a[t12] := t14 t15 := 4 * n a[t15] := x 公共子表達(dá)式刪除 如果表達(dá)式 E先前已計(jì)算，并且從先前的計(jì)算到 E的再次出現(xiàn)， E中變量的值沒(méi)有改變，那么 E的這個(gè)再次出現(xiàn)稱為 公共子表達(dá)式 公共子表達(dá)式刪除 B5 x=a[i]。 a[i]=a[j]。 a[j]=x。 t6 := 4 * i x := a[t6] t7 := 4 * i t8 := 4 * j t9 := a[t8] a[t7] := t9 t10 := 4 * j a[t10] := x goto B2 公共子表達(dá)式刪除 B5 x=a[i]。 a[i]=a[j]。 a[j]=x。 t6 := 4 * i x := a[t6] t7 := 4 * i t8 := 4 * j t9 := a[t8] a[t7] := t9 t10 := 4 * j a[t10] := x goto B2 公共子表達(dá)式刪除 B5 x=a[i]。 a[i]=a[j]。 a[j]=x。 t6 := 4 * i x := a[t6] t7 := 4 * i t8 := 4 * j t9 := a[t8] a[t7] := t9 t10 := 4 * j a[t10] := x goto B2 t6 := 4 * i x := a[t6] t8 := 4 * j t9 := a[t8] a[t6] := t9 a[t8] := x goto B2 公共子表達(dá)式刪除 i := m ?1 j := n t1 := 4 * n v := a[t1] i := i + 1 t2 := 4 * i t3 := a[t2] if t3 v goto B2 B1 B2 j := j ?1 t4 := 4 * j t5 := a[t4] if t5 v goto B3 if i = j goto B6 B4 B3 B5 B6 復(fù)寫傳播 形成為 f := g的賦值叫做 復(fù)寫語(yǔ)句 優(yōu)化過(guò)程中會(huì)大量引入復(fù)寫 t := d + e a := t 刪除局部公共子表達(dá)式期間引進(jìn)復(fù)寫 t := d + e b := t c := t c := d + e b := d + e a := d + e 復(fù)寫傳播 形成為 f := g的賦值叫做 復(fù)寫語(yǔ)句 ? 優(yōu)化過(guò)程中會(huì)大量引入復(fù)寫 ? 復(fù)寫傳播變換的做法是在復(fù)寫語(yǔ)句 f := g后，盡可能用 g代表 f x := t3 a[t2] := t5 a[t4] := t3 goto B2 x := t3 a[t2] := t5 a[t4] := x goto B2 復(fù)寫傳播 ? 成為 f := g的賦值叫做 復(fù)寫語(yǔ)句 ? 優(yōu)化過(guò)程中會(huì)大量引入復(fù)寫 ? 復(fù)寫傳播變換的做法是在復(fù)寫語(yǔ)句 f := g后，盡可能用 g代表 f ? 復(fù)寫傳播變換本身并不是優(yōu)化，但它給其它優(yōu)化帶來(lái)機(jī)會(huì) – 常量合并 – 死代碼刪除 死代碼刪除 死代碼 是指計(jì)算的結(jié)果決不被引用的語(yǔ)句 ? 一些優(yōu)化變換可能會(huì)引起死代碼 例： debug := true。 debug := false。 . . . 測(cè)試后改成 . . . if (debug) print … if (debug) print … 死代碼刪除 ? 代碼 是指計(jì)算的結(jié)果決不被引用的語(yǔ)句 ? 一些優(yōu)化變換可能會(huì)引起死代碼 例：復(fù)寫傳播可能會(huì)引起 死代碼刪除 x := t3 a[t2] := t5 a[t4] := t3 goto B2 a[t2] := t5 a[t4] := t3 goto B2 循環(huán)優(yōu)化 代碼外提 歸納變量刪除 強(qiáng)度削弱 代碼外提 ? 代碼外提是 循環(huán)優(yōu)化的一種 例： while (i = limit ? 2 ) … 變換成 t = limit ? 2。 while (i = t ) … 強(qiáng)度削弱和歸納變量刪除 j和 t4的值步伐一致地變化 ? 這樣的變量叫做 歸納變量 ? 在循環(huán)中有多個(gè)歸納變量時(shí)， 也許只需要留下一個(gè) ? 這個(gè)操作由歸納變量刪除 過(guò)程來(lái)完成 ? 對(duì)本例可以先做強(qiáng)度削弱 它給刪除歸納變量創(chuàng)造機(jī)會(huì) j := j ?1 t4 := 4 * j t5 := a[t4] if t5 v goto B3 B3 強(qiáng)度削弱和歸納變量刪除 i := m ?1 j := n t1 := 4 * n v := a[t1] B1 B2 j := j ?1 t4 := t4 ? 4 t5 := a[t4] if t5 v goto B3 B4 B3 B5 B6 t4 := 4 * j if i = j goto B6 j := j ?1 t4 := 4 * j t5 := a[t4] if t5 v goto B3 B3 除第一次外， t4 = 4 * j在 B3的入口 一定保持 在 j := j ?1后， 關(guān)系 t4 = 4 * j + 4也 保持 強(qiáng)度削弱和歸納變量刪除 i := m ?1 j := n t1 := 4 * n v := a[t1] i := i + 1 t2 := 4 * i t3 := a[t2] if t3 v goto B2 B1 B2 j := j ?1 t4 := 4 * j t5 := a[t4] if t5 v goto B3 if i = j goto B6 B4 B3 B5 B6 B2也可以進(jìn)行類似的變換 循環(huán)控制條件可以用 t2和 t4來(lái)表示 強(qiáng)度削弱和歸納變量刪除 i := m ?1 j := n t1 := 4 * n v := a[t1] t2 := 4 * i t4 := 4 * j t2 := t2 + 4 t3 := a[t2] if t3 v goto B2 B1 B2 t4 := t4 ? 4 t5 := a[t4] if t5 v goto B3 if t2 = t4 goto B6 a[t2] := t5 a[t4] := t3 goto B2 B4 B3 B5 t14 := a[t1] a[t2] := t14 a[t1] := t3 B6 基本塊的變換 ? DAG 流圖中的循環(huán) 必經(jīng)結(jié)點(diǎn) 結(jié)點(diǎn) d是結(jié)點(diǎn) n的必經(jīng)結(jié)點(diǎn)， 如果從初始結(jié)點(diǎn)起，每條 到達(dá) n的路徑都要經(jīng)過(guò) d， 寫成 d dom n 每個(gè)結(jié)點(diǎn)是它本身的必經(jīng) 結(jié)點(diǎn) 循環(huán)的入口是循環(huán)中所有 結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn) 1 2 3 4 5 6 7 8 9 10 流圖中的循環(huán) 自 然循環(huán) ? 循環(huán) – 循環(huán)必須有唯一的入口點(diǎn)，叫做 首結(jié)點(diǎn) ，首結(jié)點(diǎn)是循環(huán)中所有結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn) – 至少有一種辦法重復(fù)循環(huán)，也就是至少有一條路徑回到 首結(jié)點(diǎn) ? 回邊 – 如果有 a dom b ， 那么邊 b ? a叫做回邊 ? 尋找流圖中所有循環(huán)的一個(gè)辦法是找出流圖的 回邊 流圖中的循環(huán) 由回邊 n ? d確定的自然循環(huán)中的所有結(jié)點(diǎn)的集合 loop。 方法 由結(jié)點(diǎn) n開(kāi)始，考慮已置入 loop的每個(gè)結(jié)點(diǎn) m， m?d， 以保證 m的前驅(qū)也能置入loop， 這個(gè)算法在圖 。 loop中的每個(gè)結(jié)點(diǎn)，除了 d以外，一旦加入 stack，它的前驅(qū)就要被檢查。注意，因?yàn)?d是初始時(shí)置入循環(huán)，我們決不會(huì)考察它的前驅(qū)，因此僅找出那些不經(jīng)過(guò) d可以到達(dá) n的結(jié)點(diǎn)。 流圖中的循環(huán) 自然循環(huán) ? 回邊 10 ? 7 循環(huán) {7, 8, 10} ? 回邊 7? 4 循環(huán) {4, 5, 6, 7, 8, 10} ? 回邊 4 ? 3和 8 ? 3 循環(huán) {3, 4, 5, 6, 7, 8, 10} ? 回邊 9 ? 1 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 1 2 3 4 5 6 7 8 9 10 流圖中的循環(huán) 內(nèi)循環(huán) 若一個(gè)循環(huán)的結(jié)點(diǎn)集合是另一個(gè)循環(huán)的結(jié)點(diǎn)集合的子集。 兩個(gè)循環(huán)有相同的首結(jié)點(diǎn) , 但并非一個(gè)結(jié)點(diǎn)集是另一個(gè) 的子集，則看成一個(gè) 循環(huán)。 B0 B1 B2 B3 有相同首節(jié)點(diǎn)的兩個(gè)循環(huán) 流圖中的循環(huán) 前置結(jié)點(diǎn) 某些變換要求我們移動(dòng)語(yǔ)句到首結(jié)點(diǎn)的前面 B0 循環(huán) L (a) 整理前 ， B0是首結(jié)點(diǎn) B0 B0? 循環(huán) L (b) 整理后，增加前置結(jié)點(diǎn) B0? 流圖中的循環(huán) 可歸納流圖 一個(gè)流圖 G是 可歸約 的，當(dāng)且僅當(dāng)