【正文】 第十章 代碼優(yōu)化 優(yōu)化的概念 ? 編譯時(shí)刻為改進(jìn)目標(biāo)程序的質(zhì)量而進(jìn)行的各項(xiàng)工作。 ? 空間效率 ? 時(shí)間效率 ? 空間效率和時(shí)間效率有時(shí)是一對(duì)矛盾，有時(shí)不能兼顧。 ? 優(yōu)化的要求： ? 必須是等價(jià)變換 (保持功能 ) ? 為優(yōu)化的努力必須是值得的。 ? 有時(shí)優(yōu)化后的代碼的效率反而會(huì)下降。 優(yōu)化的分類(lèi) ? 機(jī)器相關(guān)性 ? 機(jī)器相關(guān)優(yōu)化：寄存器優(yōu)化，多處理器優(yōu)化，特殊指令優(yōu)化，無(wú)用指令消除等。 ? 機(jī)器無(wú)關(guān)優(yōu)化： ? 優(yōu)化范圍 ? 局部?jī)?yōu)化：?jiǎn)蝹€(gè)基本塊范圍內(nèi)的優(yōu)化，常量合并優(yōu)化，公共子表達(dá)式刪除，計(jì)算強(qiáng)度削弱和無(wú)用代碼刪除。 ? 全局優(yōu)化：主要是基于循環(huán)的優(yōu)化：循環(huán)不變優(yōu)化，歸納變量刪除，計(jì)算強(qiáng)度削減。 ? 優(yōu)化語(yǔ)言級(jí) ? 優(yōu)化語(yǔ)言級(jí)：針對(duì)中間代碼，針對(duì)機(jī)器語(yǔ)言。 代碼優(yōu)化程序的結(jié)構(gòu) ? 控制流分析 的主要目的是分析出程序的循環(huán)結(jié)構(gòu)。循環(huán)結(jié)構(gòu)中的代碼的效率是整個(gè)程序的效率的關(guān)鍵。 ? 數(shù)據(jù)流分析 進(jìn)行數(shù)據(jù)流信息的收集，主要是變量的值的獲得和使用情況的數(shù)據(jù)流信息。 ? 到達(dá) 定義分析；活躍變量分析；可用表達(dá)式分析； ? 代碼變換 ：根據(jù)上面的分析，對(duì)內(nèi)部中間代碼進(jìn)行等價(jià)變換。 控制流分析 數(shù)據(jù)流分析 代碼變換 基本塊和流圖 ? 基本塊中，控制流是由第一個(gè)四元式進(jìn)入，到達(dá)最后一個(gè)四元式離開(kāi)。 ? 流圖：把一個(gè)程序的中間表示中所有的 基本塊 作為 節(jié)點(diǎn) 集合。有 邊 從節(jié)點(diǎn) n到節(jié)點(diǎn) n’當(dāng)且僅當(dāng) 控制流 可能從 n的最后的一個(gè)四元式到達(dá) n’的第一個(gè)四元式。 ? 首節(jié)點(diǎn)：該基本塊的第一個(gè)四元式是程序的第一個(gè)四元式。 流圖的構(gòu)造 ? 以所有的基本塊為節(jié)點(diǎn)集合。 ? 有 B1到 B2的邊 (B2是 B1的后繼 )當(dāng)且僅當(dāng) ： ? B1的最后一個(gè)四元式有條件或無(wú)條件地轉(zhuǎn)移到 B2的第一個(gè)四元式。 ? B2是緊緊跟隨在 B1后面的四元式，且 B1的最后四元式不是無(wú)條件轉(zhuǎn)向語(yǔ)句。 流圖的例子 本節(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) 流圖的例子 本節(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。 . . . 流圖的例子 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 基本塊的優(yōu)化 ? 公共子表達(dá)式刪除 ? 復(fù)制傳播 ? 常量合并 ? 無(wú)用代碼刪除 ? 強(qiáng)度削弱 公共子表達(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á)式刪除 局部公共子表達(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á)式刪除 局部公共子表達(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á)式刪除 全局公共子表達(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á)式刪除 全局公共子表達(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 x := a[t2] t9 := a[t4] a[t2] := t9 a[t4] := 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 x := a[t2] t9 := a[t4] a[t2] := t9 a[t4] := 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 x := a[t2] t9 := a[t4] a[t2] := t9 a[t4] := x goto B2 x := t3 a[t2] := t5 a[t4] := x goto B2 公共子表達(dá)式刪除 B6 x = a[i]。 a[i] = a[n]。 a[n] = x。 t11 := 4 * i x := a[t11] t12 := 4 * i t13 := 4 * n t14 := a[t13] a[t12] := t14 t15 := 4 * n a[t15] := x x := t3 t14 := a[t1] a[t2] := t14 a[t1] := x 公共子表達(dá)式刪除 B6 x = a[i]。 a[i] = a[n]。 a[n] = x。 a[t1]能否作為公共子表達(dá)式？ t11 := 4 * i x := a[t11] t12 := 4 * i t13 := 4 * n t14 := a[t13] a[t12] := t14 t15 := 4 * n a[t15] := x x := t3 t14 := a[t1] a[t2] := t14 a[t1] := x 公共子表達(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 把 a[t1]作為公共子表達(dá)式是不穩(wěn)妥的： 控制離開(kāi) B1進(jìn)入 B6之前可能進(jìn)入 B5，而 B5有對(duì) a的賦值 復(fù)制傳播 ? 形如 f := g的賦值語(yǔ)句叫做復(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的賦值語(yǔ)句叫做復(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的賦值語(yǔ)句叫做復(fù)制語(yǔ)句 ? 優(yōu)化過(guò)程中會(huì)大量引入復(fù)制 ? 復(fù)制傳播變換的思想是在復(fù)制語(yǔ)句 f := g之后盡可能用 g代替 f ? 復(fù)制傳播變換本身并不是優(yōu)化，但它給其它優(yōu)化帶來(lái)機(jī)會(huì) ? 常量合并 ? 無(wú)用代碼刪除 常量合并 ? 例子： l = 2**r ? * 2 t1 ? * t1 r t2 ? = t2 l ? 2*。 ? * r t2 ? = t2 l 無(wú)用代碼刪除 ? 無(wú)用代碼 是指計(jì)算結(jié)果以后不被引用的語(yǔ)句 ? 一些優(yōu)化變換可能會(huì)引入無(wú)用代碼 ? 例： debug := true。 debug := false。 . . . 測(cè)試后改成 . . . if(debug)print … if(debug)print … 無(wú)用代碼刪除 ? 無(wú)用代碼 是指計(jì)算結(jié)果以后不被引用的語(yǔ)句 ? 一些優(yōu)化變換可能會(huì)引入無(wú)用代碼 例：復(fù)制傳播可能會(huì)引入 無(wú)用代碼 x := t3 a[t2] := t5 a[t4] := t3 goto B2 a[t2] := t5 a[t4] := t3 goto B2 強(qiáng)度削弱 ? 實(shí)現(xiàn)同樣的運(yùn)算可以有多種方式。用計(jì)算較快的運(yùn)算代替較慢的運(yùn)算。 ? X2 變成 x*x。 ? 2*x或 *x 變成 x+x ? x/2 變成 x* ? anxn+an1xn1+… +a1x+a0變成 ? ((… (anx+an1)x+ an2)… )x+a1)x+a0 基本塊優(yōu)化的實(shí)現(xiàn) ? 基本塊內(nèi)部?jī)?yōu)化的實(shí)現(xiàn)的主要工具為 DAG圖。 ? 用 DAG圖表示各個(gè)值的計(jì)算 /依賴(lài)關(guān)系。 ? 圖中的標(biāo)記： ? 葉節(jié)點(diǎn)用標(biāo)識(shí)符（變量名）或常數(shù)作為唯一的標(biāo)記。葉節(jié)點(diǎn)是標(biāo)識(shí)符時(shí)，用下標(biāo) 0表示它是初值