【正文】 部變換和全局變換）來改進程序，稱為優(yōu)化 ? 介紹獨立于機器的優(yōu)化，即不考慮任何目標機器性質(zhì)的優(yōu)化變換 ? 流圖中循環(huán)的識別 ? 數(shù)據(jù)流分析 ? 代碼改進變換 引言 代碼改進變換的標準 ? 代碼變換必須保程序的含義 ? 采取安全穩(wěn)妥的策略 ? 變換減少程序的運行時間平均達到一個可度量的值 ? 變換所作的努力是值得的 引言 性能的提高 優(yōu)化可以在源程序階段也可以在編譯階段進行。算法有優(yōu)劣，有適用范圍。例如對 N個元素排序，插入排序需要， 而快速排序則為 12Nlog2Nμs， 當(dāng)N=100時兩者速度差 ，而當(dāng) N=100000時，速度差 1000余倍。 引言 優(yōu)化編譯器的組織 ? 實現(xiàn)高級結(jié)構(gòu)的操作在中間代碼中是顯式的 ? 中間代碼基本上獨立于目標機器 前 端 代 碼 生成器 代 碼 優(yōu)化器 變 換 數(shù)據(jù)流 分 析 控制流 分 析 優(yōu)化的主要種類 本節(jié)所用的例子 i = m ?1。 v = a[n]。 while(a[i]v)。while (a[j]v)。 (5) i := i + 1 x=a[i]。 a[j]=x。 a[i]=a[n]。 (8) if t3v goto (5) 優(yōu)化的主要種類 本節(jié)所用的例子 i = m ?1。 v = a[n]。 while(a[i]v)。while (a[j]v)。 (13) if i =j goto (23) x=a[i]。 a[j]=x。 a[i]=a[n]。 . . . 優(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 局部優(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 公共子表達式刪除 如果表達式 E先前已計算，并且從先前的計算到 E的再次出現(xiàn)， E中變量的值沒有改變，那么 E的這個再次出現(xiàn)稱為 公共子表達式 公共子表達式刪除 B5 x=a[i]。 a[j]=x。 a[i]=a[j]。 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 公共子表達式刪除 B5 x=a[i]。 a[j]=x。 debug := false。 while (i = t ) … 強度削弱和歸納變量刪除 j和 t4的值步伐一致地變化 ? 這樣的變量叫做 歸納變量 ? 在循環(huán)中有多個歸納變量時， 也許只需要留下一個 ? 這個操作由歸納變量刪除 過程來完成 ? 對本例可以先做強度削弱 它給刪除歸納變量創(chuàng)造機會 j := j ?1 t4 := 4 * j t5 := a[t4] if t5 v goto B3 B3 強度削弱和歸納變量刪除 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也 保持 強度削弱和歸納變量刪除 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也可以進行類似的變換 循環(huán)控制條件可以用 t2和 t4來表示 強度削弱和歸納變量刪除 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é)點 結(jié)點 d是結(jié)點 n的必經(jīng)結(jié)點， 如果從初始結(jié)點起，每條 到達 n的路徑都要經(jīng)過 d， 寫成 d dom n 每個結(jié)點是它本身的必經(jīng) 結(jié)點 循環(huán)的入口是循環(huán)中所有 結(jié)點的必經(jīng)結(jié)點 1 2 3 4 5 6 7 8 9 10 流圖中的循環(huán) 自 然循環(huán) ? 循環(huán) – 循環(huán)必須有唯一的入口點，叫做 首結(jié)點 ，首結(jié)點是循環(huán)中所有結(jié)點的必經(jīng)結(jié)點 – 至少有一種辦法重復(fù)循環(huán)，也就是至少有一條路徑回到 首結(jié)點 ? 回邊 – 如果有 a dom b ， 那么邊 b ? a叫做回邊 ? 尋找流圖中所有循環(huán)的一個辦法是找出流圖的 回邊 流圖中的循環(huán) 由回邊 n ? d確定的自然循環(huán)中的所有結(jié)點的集合 loop。 loop中的每個結(jié)點，除了 d以外，一旦加入 stack，它的前驅(qū)就要被檢查。 流圖中的循環(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) 若一個循環(huán)的結(jié)點集合是另一個循環(huán)的結(jié)點集合的子集。 B0 B1 B2 B3 有相同首節(jié)點的兩個循環(huán) 流圖中的循環(huán) 前置結(jié)點 某些變換要求我們移動語句到首結(jié)點的前面 B0 循環(huán) L (a) 整理前 ， B0是首結(jié)點 B0 B0? 循環(huán) L (b) 整理后，增加前置結(jié)點 B0? 流圖中的循環(huán) 可歸納流圖 一個流圖 G是 可歸約 的，當(dāng)且僅當(dāng) 有向邊集合 =正向邊 子集 ?回邊子集，并有性質(zhì) : ? 正向邊子集形成有向無環(huán)圖，在這個圖中，每個結(jié)點可以從 G的初始結(jié)點到達 ? 回邊子集僅由前面所講的回邊組成 流圖中的循環(huán) 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 流圖中的循環(huán) 非歸約流圖的例子 ? 初始結(jié)點是 1 ? 2 ?3和 3 ?2都不是回邊 ? 該圖不是無環(huán)的 ? 從結(jié)點 2和 3兩處進入由 它們構(gòu)成的環(huán) 3 2 1 全局數(shù)據(jù)流分析介紹 ? 編譯器需要把程序流圖作為一個整體來收集信息 ? 并把這些信息分配給流圖的各個基本塊 ? 數(shù)據(jù)流信息可以通過建立和解數(shù)據(jù)流方程來收集 ? 典型方程 out [B] = gen [B] ? (in [B] ? kill [B] ) 全局數(shù)據(jù)流分析介紹 建立和解數(shù)據(jù)流方程依賴三個因素 out [B] = gen [B] ? (in [B] ? kill [B] ) ? 產(chǎn)生和注銷的概念依賴于數(shù)據(jù)流方程所要解決的問題 ，也會出現(xiàn) 反向前進，由 out[B]來定義 in[B] ? 數(shù)據(jù)流分析受程序控制結(jié)構(gòu)影響 ? 過程調(diào)用、通過指針賦值、甚至對數(shù)組變量的賦值等的存在使得數(shù)據(jù)流分析大大復(fù)雜 全局數(shù)據(jù)流分析介紹 點和路徑 ? 點 – 基本塊中，兩個相鄰的語句之間為程序的一個 點 – 基本塊的開始點和結(jié)束點 ? 路徑 點序列 p1, p2, …, pn， 對 1和 n 1間的每個 i， 滿足 – pi是先于一個語句的點， pi＋ 1是同一塊中位于該語句后的點，或者 – pi是某塊的結(jié)束點， pi＋ 1是后繼塊的開始點 到達 定值 確切 定值：賦值語句或讀語句 ? 可能 定值：過程調(diào)用 ,別名 ,通過指針來賦值 ? 確切引用 ? 可能引用 ? 在給出簡單的例子加以區(qū)別后，我們將不考慮過程調(diào)用 ,別名 ,通過指針來賦值等引起不確定性的情況。 OUT [Bi ] : = GE N [Bi ]。 ch an ge := tr ue。 for i : = 1 to n do begin new in := ? OUT [p]。 IN [Bi] := new in。 如：到達 定值數(shù)據(jù)流方程 OUT[B]=(IN[B]KILL[B])?GEN[B] 活躍變量數(shù)據(jù)流方程 LiveIn(B)=LiveUse(B)∪ (LiveOut(B)Def(B)) 數(shù)據(jù)流問題的討論 路徑 問題 任意路徑數(shù)據(jù)流分析 討論的數(shù)據(jù)流假定這么一個性質(zhì) ， 即某條路徑為真， （ 如果存在某條路徑上被引用這個變量就認為是活躍的；如果存在任何一條路徑上被定值 ， 則就認為這個變量是被定值的 ） 。 任意路徑問題的解不能保證所需的性質(zhì)一定會滿足 ， 僅僅是可能滿足 。對于全路徑問題的解，所需的性質(zhì)可以保證總是滿足。 輸出 從控制進入 L一直到離開 L， 每次都計算同樣值的三地址語句被輸出。 ? 重復(fù)下一步，直到?jīng)]有新的語句標記為“不變”為止 ? 給下面的語句標記“不變”：它們先前沒有標記，并且所有的運算對象都是下列三種情況之一： （ a） 常量； （ b） 其所有的到達 ?定值都在 L外； （ c） 只有一個到達 ?定值 ， 這個定值是循環(huán)中已標記為 “ 不變 ” 的語句 。 (2)對不變運算 P： x:=y op z或 x:=op y或 x:=y， 如果它滿足下述兩組條件中的一組 ?P點所在基本塊是 L所有出口結(jié)點之必經(jīng)結(jié)點； x在 L中沒有其他定值點； L中引用 x處只有 P點的定值才能到達。 則將滿足條件的不變運算 ,按查不變運 運算次序 ,依次外提到 L的前置結(jié)點中。 歸納變量刪除 尋找歸納變量 ? 找出所有基本歸納變量 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