【正文】 第十章 代碼優(yōu)化 學(xué)習(xí)內(nèi)容 ?優(yōu)化種類 ?循環(huán) ?全局?jǐn)?shù)據(jù)流分析 ?利用數(shù)據(jù)流信息進(jìn)行全局優(yōu)化 概述 ?目標(biāo)機(jī)器無關(guān)的優(yōu)化 ?找出程序中執(zhí)行最頻繁的部分 ?內(nèi)層循環(huán) ?數(shù)據(jù)流分析 引言 ? 代碼改進(jìn)變換的標(biāo)準(zhǔn) ?意義保持不變 ?提高速度，減小大小 ?代價適中 獲得最佳性能 貫穿本章的例子 void quicksort(int m, int n) { int i, j。 int v, x。 if (n = m) return。 i = m – 1。 j = n。 v = a[n]。 while (1) { do i = i + 1。 while (a[i] v)。 do j = j – 1。 while (a[j] v)。 if (i = j) break。 x = a[i]。 a[i] = a[j]。 a[j] = x。 } x = a[i]。 a[i] = a[n]。 a[n] = x。 quicksort(m, j)。 quicksort(i + 1, n)。 } 優(yōu)化編譯器的組織結(jié)構(gòu) ? 優(yōu)點 1. 中間代碼展現(xiàn)細(xì)節(jié)，便于優(yōu)化 2. 與目的機(jī)器無關(guān) 例 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 j := j 1 t4 := 4 * j t5 := a[t4] if t5 v goto B3 if i = j goto B6 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 B1 B2 B3 B4 B5 B6 主要優(yōu)化種類 ?局部（ local）優(yōu)化：局限基本塊內(nèi) ?全局（ global）優(yōu)化 ? 保持功能的變換 消去公共子表達(dá)式 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 B5 B5 例 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 j := j 1 t4 := 4 * j t5 := a[t4] if t5 v goto B3 if i = j goto B6 x := t3 a[t2] := t5 a[t4] := x goto B2 x := t3 t14 := a[t1] a[t2] := t14 a[t1] := x B1 B2 B3 B4 B5 B6 復(fù)制傳播 ?f := g——在隨后語句中，用 g替換 f a := d + e b := d + e c := d + e t := d + e a := t t := d + e b := t c := t x := t3 a[t2] := t5 a[t4] := x goto B2 B5 x := t3 a[t2] := t5 a[t4] := t3 goto B2 B5 無用代碼刪除 debug := false if (debug) print ... ?利用復(fù)制傳播， debug替換為 false（常量合并，constant folding） ? if語句被刪除 x := t3 a[t2] := t5 a[t4] := x goto B2 B5 a[t2] := t5 a[t4] := t3 goto B2 B5 循環(huán)的優(yōu)化 ?程序中運行最頻繁的部分 ?代碼外提， code motion ?刪除歸納變量， inductionvariable elimination ?強(qiáng)度削弱， reduction strength 代碼外提 ?表達(dá)式計算與循環(huán)次數(shù)無關(guān)（循環(huán)不變計算，loopinvariant putation） ? 循環(huán)內(nèi) ?循環(huán)入口前 while (i = limit – 2) ? t = limit – 2。 while (i t) 例 強(qiáng)度削弱 i := m – 1 j := n t1 := 4 * n v := a[t1] j := j 1 t4 := 4 * j t5 := a[t4] if t5 v goto B3 if i = j goto B6 B1 B2 B3 B4 B5 B6 i := m – 1 j := n t1 := 4 * n v := a[t1] j := j 1 t4 := t4 4 t5 := a[t4] if t5 v goto B3 if i = j goto B6 B1 B2 B3 B4 B5 B6 t4 := 4 * j j和 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 t4 := t4 4 t5 := a[t4] if t5 v goto B3 if t2 = t4 goto B6 a[t2] := t5 a[t4] := t3 goto B2 t14 := a[t1] a[t2] := t14 a[t1] := t3 B1 B2 B3 B4 B5 B6 t2 = t4與 i = j等價 基本塊的優(yōu)化 ?例 ：基本塊的 dag表示 a := b + c b := a – d c := b + c d : = a d a := b + c d := a – d c := d + c 若 b不活躍 dag的局限 ?語句 1和語句 4的等價性無法發(fā)現(xiàn) a := b + c b := b – d c := c + d d := b + c 利用代數(shù)恒等進(jìn)行優(yōu)化 ?代數(shù)恒等 x + 0 = 0 + x = x x – 0 = x x * 1 = 1 * x = x x / 1 = x ?降低強(qiáng)度 x ** 2 = x * x * x = x + x x / 2 = x * ?常量合并 2 * ? dag輔助代數(shù)優(yōu)化 ?x * y = y * x：在 dag節(jié)點創(chuàng)建中進(jìn)行額外檢查 ?x y —— x – y 結(jié)合 標(biāo)志寄存器檢測 ?結(jié)合率 a := b + c e := c + d + b ? a := b + c t := c + d e := t + b 優(yōu)化 ? a := b + c e := a + d 流圖中的循環(huán) ? d支配（ dominate） n：從流圖的開始節(jié)點到 n的任何路徑都經(jīng)過 d， d dom n ?直接支配者， immediate dominator 任何路徑上都是最后一個支配者 循環(huán)的判定 1. 具有唯一入口點， “ header‖，它應(yīng)支配循環(huán)中所有節(jié)點，否則就不是唯一入口點 2. 至少有一條路徑返回首節(jié)點 ? 找出回邊 ——back edge 邊 a→b ， b支配 a ? 例 ：上例流圖中的回邊 7→4 ， 10→7 ， 4→3 ， 8→3 ， 9→1 循環(huán)的判定（續(xù)） ? 自然循環(huán)， natural loop ? 回邊 n→d ， d及不經(jīng)過 d可到達(dá) n的節(jié)點集合， d——首節(jié)點 ? 例 ： ? 10→7 的自然循環(huán)： 10 ? 9→1 的自然循環(huán)：所有節(jié)點 算法 構(gòu)造自然循環(huán) 輸入：流圖 G和一條回邊 n→d 輸出： n→d 對應(yīng)的自然循環(huán)的節(jié)點集合 void insert(m) { if (m不在 loop中 ) { loop = loop ∪ {m}。 m壓棧到 stack。 } } 主程序 stack設(shè)置為空 。 loop := nhcuj7d3。 insert(n)。 while (stack不空 ) { pop m。 for (m的每個前驅(qū) p) insert(p)。 } 內(nèi)層循環(huán)（ inner loop） ?兩個循環(huán)若無相同首節(jié)點，則：或者不相交，或者嵌套 ?內(nèi)層循環(huán)：不包含其他循環(huán)的循環(huán) ?相同首節(jié)點情況：可看作一個循環(huán) B0 B1 B3 B2 PreHeader ?循環(huán) L，創(chuàng)建前置節(jié)點， preheader ? 只有一個后繼 ——L的首節(jié)點 ? 所有 L外指向首節(jié)點的邊 ?指向前置節(jié)點 ? 代碼外提 header loop L preheader header loop L 可約流圖 ? 循環(huán)外到循環(huán)內(nèi)的轉(zhuǎn)移 ? 流圖 G可約的充要條件 所有邊可劃分為兩個不相交的集合 ——前向邊和回邊，且滿足： 1. 前向邊構(gòu)成一個 dag，且從 G的開始節(jié)點，可到達(dá)其他任何節(jié)點 2. 回邊：前面定義 例 虛線：回邊 其他：前向邊 例 不可約的流圖 例 內(nèi)層循環(huán)： {7, 8, 10} {4, 5, 6, 7}不是循環(huán) 外層循環(huán)： {4, 5, 6, 7, 8, 10} 更外層循環(huán)： {3,4,5,6,7,8,10} 更外層循環(huán)：整個流圖 全局?jǐn)?shù)據(jù)流分析 ?數(shù)據(jù)流信息 ?解方程組 ?數(shù)據(jù)流方程 out[S] = gen[S]∪ (in[S] – kill[S]) 含義：語句結(jié)束處的信息 ?或者是語句生成的信息 ?或者是語句開始時的信息去除語句執(zhí)行中注銷的信息 數(shù)據(jù)流方程創(chuàng)建求解的因素 1. ―生成”、“注銷”的概念依賴于求解問題一般 in[S]?out[S]，還可能out[S]?in[S] 2. 數(shù)據(jù)流分析依賴于程序的控制流語句out[S]——語句有唯一出口 方程 ——基本塊層次 3. 過程調(diào)用、通過指針變量的賦值以及數(shù)組變量的賦值等語句較為微妙 點和路徑 ? 點（ point） ? 相鄰兩條語句間的位置 ? 第一條之前和最后一條語句之后的位置 ? 路徑（ path） ? p1?pn的路徑 ——點序列 p1, p2, …, p n，且對所有1=in滿足下面兩個條件之一： 1. pi是緊挨在一條語句之前的點， pi+1是同一基本塊中緊接在該語句之后的點 2. pi是某基本塊的結(jié)束點， pi+1是后繼塊的開始點 例 B5?B6的路徑： B5的結(jié)束點 ?B BB4的所有點 ?B6的開始點 d1: i := m – 1 d2: j := n d3: a := u1 d4: i := i + 1 d6: a := u2 B1 B2 B3 B4 B5 B6 d5: j := j 1 到達(dá)定義 ? 變量 x的定義（ definition） ? 明確（ unambiguous）定義：賦值、 I/O輸入 ? 模糊（ ambiguous）定義 1. x作為過程的參數(shù)（非傳值方式） x在過程的作用域中 “別名” ——x本身不是上兩種情況，但與 x等價的另一個變量是上兩種情況 2. 通過可能指向 x的指針進(jìn)行賦值， *q=y——q指向 x 到達(dá) ?定義 d到達(dá) （ reach） p ? 存在從緊跟 d的點到 p的路徑 ? 在路徑上 d沒有被注銷 ? i := m – 1, j := n到達(dá) B2 的開始點 ? 若 B B5不對 j賦值 B3中 j := j – 1后面部分 也是如此，則定義 j := j – 1到達(dá) B2開始點 ? j := j 1注銷了 j := n，