第8章代碼優(yōu)化

第11章代碼優(yōu)化學(xué)習(xí)目標(biāo)：掌握：基本塊的劃分、基本塊的DAG優(yōu)化理解：什么是局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化了解：循環(huán)優(yōu)化技術(shù)11.1 優(yōu)化技術(shù)簡介11.2 局部優(yōu)化11.3 循環(huán)優(yōu)化簡介11.1優(yōu)化技術(shù)簡介什么是優(yōu)化： 所謂優(yōu)化是對代碼進行等價變換，使得變換后的代碼的效率更高（節(jié)省運行時間、存儲空間或兩者兼而有之）優(yōu)化可在編譯的不同階段進行，最主要的優(yōu)化有中間代碼優(yōu)化（不依賴具體計算機）目標(biāo)代碼優(yōu)化（依賴于具體計算機）中間代碼優(yōu)化中間代碼源代碼編譯前端代碼生成目標(biāo)代碼目標(biāo)代碼優(yōu)化編譯的優(yōu)化工作階段優(yōu)化的分類： 根據(jù)優(yōu)化涉及的程序范圍，分為：局部優(yōu)化：在只有一個入口、一個出口的基 本塊上進行優(yōu)化循環(huán)優(yōu)化：對循環(huán)中的代碼進行優(yōu)化全局優(yōu)化：在整個程序范圍內(nèi)進行的優(yōu)化中間代碼優(yōu)化常用技術(shù)1.

刪除多余運算（刪除公共子表達式）如果子表達式E在前面計算過，且之后E中的變量值都未改變，那么E的重復(fù)出現(xiàn)稱為公共子表達式，可避免重復(fù)計算(1)和(4)中都有4*I的運算，(1)到(4)之間無對I的賦值，顯然兩次計算的值是相等的，(4)的運算是多余的例(1)T1:=4*I(2)T2:=addr(A)－4(3)T3:=T2[T1]T4:=4*I

(5)……(4)變換成T4

:=T12.合并已知量與復(fù)寫傳播如果運算量都是已知量，則在編譯時就算出它的值，稱為合并已知量若有A:=B，稱為把B值復(fù)寫到A。如果其后有引用A的地方，且其間A、B的值都未改變，則可把對A的引用改為對B引用，稱為復(fù)寫傳播。例：（1）I:=1 （2）T1:=4*I （3）T4:=T1 （4）T6:=T5[T4]I是已知量把T1的值復(fù)寫到T4（4）T6:=T5[T1]復(fù)寫傳播（2）T1:=4

合并已知量3.刪除無用賦值有些變量的賦值從未被引用，稱為無用賦值，應(yīng)刪除。無用賦值分三種情況：變量被賦值，但在程序中從未被引用（在局部范圍內(nèi)難判定）

變量賦值后未被引用又重新賦值，則前面賦值是無用的

變量的賦值只被計算變量自己引用，其他變量都不引用它例（1）I:=1（2）T1:=4（3）T3:=T2[T1]（4）T4:=T1

（5）I:=I+1（6）T1:=T1+4（7）ifT1≤80goto(3)(4)中對T4賦值，但T4未被引用；(1)和(5)對I賦值，但只有(5)中計算I時引用I如果程序其他地方不需要引用T4和I，則(4)、(1)和(5)是無用賦值，可刪除。（2）T1:=4（3）T3:=T2[T1]（6）T1:=T1+4（7）ifT1≤80goto(3)4.其他優(yōu)化技術(shù)以下優(yōu)化技術(shù)將在循環(huán)優(yōu)化中介紹：

代碼外提強度削弱變換循環(huán)控制條件（刪除歸納變量）11.2局部優(yōu)化局部優(yōu)化是指基本塊內(nèi)的優(yōu)化基本塊是指程序中一順序執(zhí)行的語句序列，其中只有一個入口語句和一個出口語句。執(zhí)行時只能從入口語句進入，從其出口語句退出11.2.1基本塊的劃分把程序（中間代碼形成）劃分成基本塊的算法：1.

求基本塊的入口語句，它們是：程序的第一個語句；或者條件轉(zhuǎn)移或無條件轉(zhuǎn)移語句的轉(zhuǎn)移目標(biāo)語句；或者緊跟在條件轉(zhuǎn)移語句后面的語句。2．對每一入口語句，構(gòu)造其所屬的基本塊:它是由該入口語句到下一入口語句(不包括下一入口語句);或到一轉(zhuǎn)移語句(包括該轉(zhuǎn)移語句);或到一停止語句(包括該停止語句) 之間的語句序列組成的。3．凡未被納入某一基本塊的語句，是不會被執(zhí)行到的語句，可以把它們刪除。例：

readXreadYR:=XmodYifR=0goto

(8)X:=YY:=Rgoto

(3)writeYhalt(1)、(3)、(5)和(8)是入口語句，分別構(gòu)成基本塊B1 {(1)、(2)}B2 {(3)、(4)}B3 {(5)、(6)、(7)}B4 {(8)、(9)}readXR:=XmodY

X:=YwriteY11.3

循環(huán)優(yōu)化簡介循環(huán)就是程序中那些可能反復(fù)執(zhí)行的代碼序列。因為循環(huán)中的代碼要反復(fù)執(zhí)行，所以循環(huán)的代碼優(yōu)化對提高目標(biāo)代碼的效率將起更大的作用。11.3.1程序流圖把控制流的信息加到基本塊集合上構(gòu)成的有向圖稱為表示程序的流圖，簡稱流圖。流圖的構(gòu)造方法：點集：以基本塊為結(jié)點，含程序第一條語句的結(jié)點為首結(jié)點。邊集：從基本塊Bi向基本塊Bj引有向邊，僅當(dāng)Bj在程序中的位置緊跟在Bi之后,

且Bi的出口語句不是無條件轉(zhuǎn)移語句或停止語句。或者Bi的出口是轉(zhuǎn)移語句(goto(s)或if…goto(s))，并且轉(zhuǎn)移目標(biāo)(s)是Bj的入口語句。例：構(gòu)造以下程序的流圖(1)readX(2)readY(3)R:=XmodY

(4)ifR=0goto

(8)(5)X:=Y(6)Y:=R(7)goto(3)(8)writeY(9)halt(1)readX(2)readY(3)R:=XmodY(4)ifR=0goto(8)(5)X:=Y(6)Y:=R(7)goto(3)(8)writeY(9)halt11.3.2循環(huán)優(yōu)化1.代碼外提把循環(huán)不變運算，即其結(jié)果獨立于循環(huán)執(zhí)行次數(shù)的表達式，提到循環(huán)的前面，使之只在循環(huán)外計算一次，這種優(yōu)化稱為代碼外提。循環(huán)不變運算：運算量為常量或在循環(huán)外定值，每次循環(huán)時其值不變的運算。(1)P:=0(2)I:=1(3)T1:=4*I(4)T2:=addr(A)－4(5)T3:=T2[T1](6)T4:=T1(7)T5:=addr(B)－4(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)ifI≤20goto(3)中間代碼段B1B2(1)P:=0(2)I:=1(4)T2:=addr(A)－4(7)T5:=addr(B)－4(3)T1:=4*I(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)IfI≤20goto(3)代碼外提后B1B2(4)中的運算量addr(A)是分配的數(shù)組A的首地址，是個常量，4也是常量，因而(4)是循環(huán)不變運算，同樣(7)也是循環(huán)不變運算，(4)、(7)都可提到循環(huán)前2.強度削弱強度削弱是指把程序中強度大的運算替換成強度小的運算。例如把乘法運算換成加法運算等(1)P:=0(2)I:=1(4)T2:=addr(A)－4(7)T5:=addr(B)－4(3)T1:=4*I(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)IfI≤20goto(3)中間代碼段(1)P:=0(2)I:=1(4)T2:=addr(A)－4(7)T5:=addr(B)－4(3)T1:=4*I(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3’)T1:=T1+4

(12)ifI≤20goto(5)強度削弱I和T1始終保持T1:=4*I的線性關(guān)系這樣把(12)的循環(huán)控制條件I≤20變換成T1≤80，程序的運行結(jié)果不變這種變換稱為變換循環(huán)控制條件經(jīng)過這一變換，循環(huán)中I的值不被引用，四元式(11)可被刪去，這是變換的目的所在。(1)P:=0(2)I:=1(4)T2:=addr(A)－4(7)T5:=addr(B)－4(3)T1:=4*I(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3’)T1:=T1+4(12)ifI≤20

goto(5)變換循環(huán)控制條件(1)P:=0(2)I:=1(4)T2:=addr(A)－4(7)T5:=addr(B)－4(3)T1:=4*I(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(3’)T1:=T1+4(12)ifT1≤80

goto(5)變換循環(huán)控制條件中間代碼段(1)P:=0(2)I:=1(4)T2:=addr(A)－4(7)T5:=addr(B)－4(3)T1:=4*I(5)T3:=