編譯原理課件：Chapter-11 代 碼 優(yōu) 化

1、第十一章 代 碼 優(yōu) 化11.1 概述11.2 優(yōu)化的例子11.3 基本塊的優(yōu)化11.4 循環(huán)優(yōu)化111.1 概述 經(jīng)過前面各章所介紹的各個編譯階段，我們已經(jīng)可以把源程序變換成目標(biāo)代碼了，但這樣生成的目標(biāo)代碼效率未必是最高的。代碼優(yōu)化（code optimization)目的：提高目標(biāo)代碼運行效率 原則：進行優(yōu)化必須嚴格遵循“不能改變原有程序語義”原則。 時間效率（減少運行時間）空間效率（減少內(nèi)存容量）2優(yōu)化的分類： 從優(yōu)化的層次，與機器是否有關(guān)，分為： 從優(yōu)化涉及的范圍，又分為： 獨立于機器的優(yōu)化：即與目標(biāo)機無關(guān)的優(yōu)化，通常是在中間代碼上進 行的優(yōu)化。與機器有關(guān)的優(yōu)化：充分利用系統(tǒng)資源（指令

2、系統(tǒng)，寄存器資源）。局部優(yōu)化：是指在基本塊內(nèi)進行的優(yōu)化。循環(huán)優(yōu)化：對循環(huán)語句所生成的中間代碼序列上所進行的優(yōu)化。全局優(yōu)化：顧名思義，跨越多個基本塊的全局范圍內(nèi)的優(yōu)化。因此它是指在非線性程序段上（包括多個基本塊, GOTO, 循環(huán)）的優(yōu)化。需要進行全局控制流和數(shù)據(jù)流分析，比較復(fù)雜。3定義基本塊（basic block ) 滿足以下三個條件的程序段，稱為基本塊：只有一個入口和一個出口，且語句為順序執(zhí)行的程序段。它使得所有轉(zhuǎn)向該基本塊的入口都是該基本塊的第一條語句。如果塊中任一語句被執(zhí)行，則該塊內(nèi)的所有語句也將被執(zhí)行（無分支），且執(zhí)行次數(shù)一樣（無循環(huán)）。4例：書上第252頁圖11.1的FORTRAN

3、語言例子（先編號，后畫圖決定基本塊）FACTOR = A( I ) + 2.0 * B( I )EXP 1 = ABS( FACTOR )IF ( KEY.NE.0 ) GO TO 10 BASE = 2.0FACTOR = FACTOR * 2GO TO 2010. BASE = 10.011. FACTOR = SQRT( FACTOR )20. Q = ( BASE * EXP ) * FACTOR21. RETURN基本塊基本塊基本塊13456201011212基本塊5優(yōu)化所花費的代價和優(yōu)化產(chǎn)生的效果可用下圖表示：優(yōu)化的代價 局部優(yōu)化循環(huán)優(yōu)化全局優(yōu)化優(yōu)化的效果 6圖的左部表示只要做些簡

4、單的處理，便能得到明顯的優(yōu)化效果。這相當(dāng)于局部優(yōu)化。若要進一步提高優(yōu)化效果，就要逐步付出更大的代價循環(huán)優(yōu)化。全局優(yōu)化進一步提高。優(yōu)化的代價 局部優(yōu)化循環(huán)優(yōu)化全局優(yōu)化優(yōu)化的效果 7為什么要優(yōu)化？有的大型計算程序一運行就要花上幾十分鐘，甚至好幾小時。這時為優(yōu)化即使付出些代價也是值得的。另外，程序中的循環(huán)往往要占用大量的計算時間，所以為減少循環(huán)執(zhí)行時間所進行的優(yōu)化對減少整個程序的運行時間有很大的意義。 尤其有實時要求的程序，如市場決策，供需及求益的平衡。對于像學(xué)生作業(yè)之類的簡單小程序(占機器內(nèi)存、運行速度均可接受)，或在程序的調(diào)試階段，花費許多代價去進行一遍又一遍的優(yōu)化就毫無必要。811.2 優(yōu)化的

5、基本方法和例子 在這一節(jié)中，我們將介紹一些有代表性的優(yōu)化處理方法和例子。實際的優(yōu)化應(yīng)在中間代碼或目標(biāo)代碼上進行。但為了便于說明，這兒我們用源程序形式舉例。（1）利用代數(shù)性質(zhì)(代數(shù)變換) 編譯時完成常量表達式的計算，整數(shù)類型與實型的轉(zhuǎn)換。 例： a := 5 + 6 + x a := 11 + x 又如： 設(shè) x 為實型，x := 3 + 1 可變換成x := 4.09 下標(biāo)變量引用時，其地址計算的一部分工作可在編譯時預(yù)先做好(運行時只需計算“可變部分”即可)。例如：二維數(shù)組定義為：Array l1 : u1, l2 : u2 令di = ui li + 1, i = 1, 2 /每一維的尺寸假

6、如數(shù)組元素按行存放，則Array i1, i2 的位置為D = a + ( i1 - l1) d2 + ( i2 l2 ) * m / m為每個元素所占大小 = a ( l1 d2 + l2 ) * m + ( i1 d2 + i2 ) * m = CONSPART + VARPART10如 x * 2 x * x 3 * x x + x + x 8 * x , 4 * x 等換成左移運算 x / 2 , x / 16 等換成右移運算 x := x + 1 變?yōu)镮NC x指令 x / 5 x * 0.2 等利用機器硬件所提供的一些功能，如左移、右移操作做乘法或除法，具有更高的代碼效率。 運算強

7、度削弱：用一種需要較少執(zhí)行時間的運算代替另一種運算，以減少運行時的運算強度(時、空開銷)。11（2） 復(fù)寫(copy)傳播如 x := y 這樣的賦值語句稱為復(fù)寫語句。由于 x 和 y 值相同，所以當(dāng)滿足一定條件時，在該賦值語句下面出現(xiàn)的 x 可用 y 來代替。例如： x := y ; x := y ; u := 2 * x ; u := 2 * y ; v := x + 1 ; v := y + 1 ; 這就是所謂的復(fù)寫傳播 (copy propagation) 。若以后的語句中不再用到 x 時，則上面的 x := y 可刪去。12若上例中不是x := y而是 x := 3。則復(fù)寫傳播變成了

8、常量傳播。即 u := 6; v := 4;又如 t1 := y / z; x := t1;若這里 t1為暫時(中間)變量，以后不再使用，則可變換為 x := y / z;此外常量傳播，引起常量計算，如： pi = 3.14159 r = pi / 180.0此時：pi = 3.14159 r = 0.0174532 （常量計算）x := y; u := 2 * x; v := x + 1;x := 3; u := 2 * x; v := x + 1;13（3） 刪除公共子表達式例如：x := ( -y + z ) * z / 2 - ( -y + z )其中： ( -y + z )是公共子表

9、達式。 我們可用DAG (directed acyclic graph，有向無循環(huán)圖)來表示具有公共子表達式的抽象語法樹。具有相同值的子表達式在兩個以上地方出現(xiàn)時，稱它為公共子表達式(common subexpression)。14顯然，對于公共子表達式只要計算1次即可。x := ( -y + z ) * z / 2 - ( -y + z )+yz:=x*/215（4） 刪除冗余代碼冗余代碼就是毫無實際意義的代碼，又稱死代碼 (dead code)或無用代碼(useless code)。例如： x := x + 0; x := x * 1; 等又例： FLAG := TRUE IF FLAG

10、THEN FLAG永真 ELSE 另外在程序中為了調(diào)試常有如下： if debug then 的語句。 但當(dāng)debug為false時，then后面的語句便永遠不會執(zhí)行。這就是可刪去的冗余代碼。 ( 可用條件編譯 #if DEBUG 程序編寫，而源代碼中還應(yīng)留著）16（5） 循環(huán)優(yōu)化經(jīng)驗告訴我們：“程序運行時間的80%是由僅占源程序20%的部分執(zhí)行的”。二八定律(Pareto Principle)這20%的源程序就是循環(huán)部分，特別是多重循環(huán)的最內(nèi)層的循環(huán)部分。因此減少循環(huán)部分的目標(biāo)代碼對提高整個程序的時間效率有很大作用。 for i = 1 to 10 for j = 1 to 100 x :=

11、 x + 0 ； y := 5 + 7 + x ;優(yōu)化一條，少10*100次運算17除了對循環(huán)體進行優(yōu)化，還有專用于循環(huán)的優(yōu)化循環(huán)不變式的代碼外提 不變表達式：不隨循環(huán)控制變量改變而改變的表達式或子表 達式。如： FOR I := E1 STEP E2 TO E3 DO BEGIN S := 0.2 * 3.1416 * R P := 0.35 * I V := S * P不能外提!不變表達式可外提18如 while do x := （b * b - 4.0 * a * c ) 若a, b, c的值在該循環(huán)體中不改變時，則可將循環(huán)不變式移到循環(huán)之外，即變?yōu)椋?t1 := b * b - 4.0

12、 * a * c while do x := ( t1) 從而減少計算次數(shù) 也稱為頻度削弱。19循環(huán)展開 循環(huán)展開是一種優(yōu)化技術(shù)。它將構(gòu)成循環(huán)體的代碼(不包括控制循環(huán)的測試和轉(zhuǎn)移部分)，重新產(chǎn)生許多次(這可在編譯時確定)，而不僅僅是一次。以空間換時間!例：PL/1中的初始化循環(huán) DO I = 1 TO 30 A I = 0.0 END I := 1L1: IF I 30 THEN GOTO L2 代碼5條語句 A I = 0.0 共執(zhí)行5*30 I = I+1 條語句 GOTO L1L2:A1 = 0.0 30條語句A2 = 0.0 （指令）執(zhí)行 也是30條語句A30 = 0.0 展開20說明

13、： 循環(huán)一次執(zhí)行5條語句才給一個變量賦初值。展開后，一條語句就能賦一個值，運行效率高。 優(yōu)化在生成代碼時進行，并不是修改源程序。 必須知道循環(huán)的初值、終值及步長。 但非所有展開都是合適的。如上例中循環(huán)展開后節(jié)省了測試和轉(zhuǎn)移語句：2*30=60語句。 增加29條省60條 但若循環(huán)體中不是一條而是40條，則展開將有40*30=1200條，但省的仍是60條，就不算優(yōu)化了。 判斷準(zhǔn)則：1. 主存資源豐富 處理機時間昂貴 2. 循環(huán)體語句越少越好循環(huán)展開有利（大型機）21實現(xiàn)步驟：識別循環(huán)結(jié)構(gòu)，確定循環(huán)的初值、終值和步長。判斷。以空間換時間是否合算來決定是否展開。展開。重復(fù)產(chǎn)生循環(huán)體所需的代碼個數(shù)?？臻g

14、只多二條，但省了20次測試時間（只循環(huán)10次）比較復(fù)雜：在對空間與時間進行權(quán)衡時，還可以考慮一種折衷的辦法，即部分展開循環(huán)。如上例展為：DO I = 1 TO 10 STEP 3 A I = 0.0 A I + 1 = 0.0 A I + 2 = 0.0END;DO I = 1 TO 30 A I = 0.0 END22c) 歸納變量的優(yōu)化和條件判斷的替換歸納變量(induction variable): 在每一次執(zhí)行循環(huán)迭代的過程中，若某變量的值固定增加（或減少）一個常量值，則稱該變量為歸納變量(induction variable)。即若當(dāng)前執(zhí)行循環(huán)的第 j 次迭代，歸納變量的值應(yīng)為c *

15、 j + c, 這里 c 和 c 都是循環(huán)不變式。例： for i := 1 to 10 do ai := bi + ci23中間變量t1 ， t3 ， t6 都是歸納變量。t1 := 4 * i , t3 := 4 * i , t6 := 4 * i i := 1 labb: if i 10 goto labe t1 := 4 * i t2 := b t1 t3 := 4 * i t4 := c t3 t5 := t2 + t4 t6 := 4 * i a t6 := t5 i := i + 1 goto labb labe:for i:= 1 to 10 do ai := bi + ciu

16、 := 4labb:if u 40 goto labetb := b u tc := c u t := tb + tca u := tu := u + 4goto labblabe:優(yōu)化24d) 其它循環(huán)優(yōu)化方法 把多重嵌套的循環(huán)變成單層循環(huán)。 把 n 個相同形式的循環(huán)合成一個循環(huán)等。對于循環(huán)優(yōu)化的效果是很明顯的。某FORTRAN 77 編譯程序，在進行不同級別的優(yōu)化后所得的目標(biāo)代碼指令數(shù)為： 優(yōu)化級別 循環(huán)內(nèi)的指令數(shù)（包括循環(huán)條件判斷） 0（不優(yōu)化） 21 1（局部優(yōu)化） 16 2（循環(huán)優(yōu)化） 6 3（全局優(yōu)化） 525（6） in_line 展開 把過程（或函數(shù)）調(diào)用改為in_line展開

17、可節(jié)省許多處理過程（函數(shù)）調(diào)用所花費的開銷。如： procedure m( i , j : integer; max : integer); begin if i j then max := i else max := j end;省去了函數(shù)調(diào)用時參數(shù)壓棧，保存返回地址等指令。這也僅僅限于簡單的函數(shù)。若有過程調(diào)用 m ( k , 0, max );則內(nèi)置展開后為： if k 0 then max := k else max := 0;26（7）其他， 如控制流方法如 BR L 無條件轉(zhuǎn)移 為不可達代碼 L : 又如：轉(zhuǎn)移到轉(zhuǎn)移指令的指令 BR L1 BR L2 L1: BR L2 L1: BR L2優(yōu)化27還有： BRCC L1 當(dāng)條件CC成立，轉(zhuǎn)到L1 BR L2L1: . 可改進為： BR CC L2 當(dāng)條件不能成立時 ，轉(zhuǎn)到L2 L1: 此外還有其它方法。且隨著軟件技術(shù)的飛速發(fā)展，不斷會有新的優(yōu)化方法推出。28練習(xí)：作常數(shù)合并優(yōu)化的表達式屬性翻譯文法及語