第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)化是對(duì)代碼進(jìn)行等價(jià)變換，使得變換后的代碼的效率更高（節(jié)省運(yùn)行時(shí)間、存儲(chǔ)空間或兩者兼而有之）優(yōu)化可在編譯的不同階段進(jìn)行，最主要的優(yōu)化有中間代碼優(yōu)化（不依賴具體計(jì)算機(jī)）目標(biāo)代碼優(yōu)化（依賴于具體計(jì)算機(jī)）中間代碼優(yōu)化中間代碼源代碼編譯前端代碼生成目標(biāo)代碼目標(biāo)代碼優(yōu)化編譯的優(yōu)化工作階段優(yōu)化的分類： 根據(jù)優(yōu)化涉及的程序范圍，分為：局部優(yōu)化：在只有一個(gè)入口、一個(gè)出口的基 本塊上進(jìn)行優(yōu)化循環(huán)優(yōu)化：對(duì)循環(huán)中的代碼進(jìn)行優(yōu)化全局優(yōu)化：在整個(gè)程序范圍內(nèi)進(jìn)行的優(yōu)化中間代碼優(yōu)化常用技術(shù)1.

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

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

:=T12.合并已知量與復(fù)寫傳播如果運(yùn)算量都是已知量，則在編譯時(shí)就算出它的值，稱為合并已知量若有A:=B，稱為把B值復(fù)寫到A。如果其后有引用A的地方，且其間A、B的值都未改變，則可把對(duì)A的引用改為對(duì)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)難判定）

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

變量的賦值只被計(jì)算變量自己引用，其他變量都不引用它例（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)中對(duì)T4賦值，但T4未被引用；(1)和(5)對(duì)I賦值，但只有(5)中計(jì)算I時(shí)引用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)化中介紹：

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

求基本塊的入口語句，它們是：程序的第一個(gè)語句；或者條件轉(zhuǎn)移或無條件轉(zhuǎn)移語句的轉(zhuǎn)移目標(biāo)語句；或者緊跟在條件轉(zhuǎn)移語句后面的語句。2．對(duì)每一入口語句，構(gòu)造其所屬的基本塊:它是由該入口語句到下一入口語句(不包括下一入口語句);或到一轉(zhuǎn)移語句(包括該轉(zhuǎn)移語句);或到一停止語句(包括該停止語句) 之間的語句序列組成的。3．凡未被納入某一基本塊的語句，是不會(huì)被執(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í)行的代碼序列。因?yàn)檠h(huán)中的代碼要反復(fù)執(zhí)行，所以循環(huán)的代碼優(yōu)化對(duì)提高目標(biāo)代碼的效率將起更大的作用。11.3.1程序流圖把控制流的信息加到基本塊集合上構(gòu)成的有向圖稱為表示程序的流圖，簡稱流圖。流圖的構(gòu)造方法：點(diǎn)集：以基本塊為結(jié)點(diǎn)，含程序第一條語句的結(jié)點(diǎn)為首結(jié)點(diǎn)。邊集：從基本塊Bi向基本塊Bj引有向邊，僅當(dāng)Bj在程序中的位置緊跟在Bi之后,

且Bi的出口語句不是無條件轉(zhuǎn)移語句或停止語句?；蛘連i的出口是轉(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)不變運(yùn)算，即其結(jié)果獨(dú)立于循環(huán)執(zhí)行次數(shù)的表達(dá)式，提到循環(huán)的前面，使之只在循環(huán)外計(jì)算一次，這種優(yōu)化稱為代碼外提。循環(huán)不變運(yùn)算：運(yùn)算量為常量或在循環(huán)外定值，每次循環(huán)時(shí)其值不變的運(yù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)中的運(yùn)算量addr(A)是分配的數(shù)組A的首地址，是個(gè)常量，4也是常量，因而(4)是循環(huán)不變運(yùn)算，同樣(7)也是循環(huán)不變運(yùn)算，(4)、(7)都可提到循環(huán)前2.強(qiáng)度削弱強(qiáng)度削弱是指把程序中強(qiáng)度大的運(yùn)算替換成強(qiáng)度小的運(yùn)算。例如把乘法運(yùn)算換成加法運(yù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(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)強(qiáng)度削弱I和T1始終保持T1:=4*I的線性關(guān)系這樣把(12)的循環(huán)控制條件I≤20變換成T1≤80，程序的運(yùn)行結(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:=