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

第11章代碼優(yōu)化學習目標：掌握：基本塊的劃分、基本塊的DAG優(yōu)化理解：什么是局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化了解：循環(huán)優(yōu)化技術11.1 優(yōu)化技術簡介11.2 局部優(yōu)化11.3 循環(huán)優(yōu)化簡介11.1優(yōu)化技術簡介什么是優(yōu)化： 所謂優(yōu)化是對代碼進行等價變換，使得變換后的代碼的效率更高（節(jié)省運行時間、存儲空間或兩者兼而有之）優(yōu)化可在編譯的不同階段進行，最主要的優(yōu)化有中間代碼優(yōu)化（不依賴具體計算機）目標代碼優(yōu)化（依賴于具體計算機）中間代碼優(yōu)化中間代碼源代碼編譯前端代碼生成目標代碼目標代碼優(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)化常用技術1.

刪除多余運算（刪除公共子表達式）如果子表達式E在前面計算過，且之后E中的變量值都未改變，那么E的重復出現(xiàn)稱為公共子表達式，可避免重復計算(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.合并已知量與復寫傳播如果運算量都是已知量，則在編譯時就算出它的值，稱為合并已知量若有A:=B，稱為把B值復寫到A。如果其后有引用A的地方，且其間A、B的值都未改變，則可把對A的引用改為對B引用，稱為復寫傳播。例：（1）I:=1 （2）T1:=4*I （3）T4:=T1 （4）T6:=T5[T4]I是已知量把T1的值復寫到T4（4）T6:=T5[T1]復寫傳播（2）T1:=4

合并已知量3.刪除無用賦值有些變量的賦值從未被引用，稱為無用賦值，應刪除。無用賦值分三種情況：變量被賦值，但在程序中從未被引用（在局部范圍內(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)化技術以下優(yōu)化技術將在循環(huán)優(yōu)化中介紹：

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

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

readXreadYR:=XmodYifR=0goto

(8)X:=YY:=Rgoto

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

X:=YwriteY11.3

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

且Bi的出口語句不是無條件轉移語句或停止語句?；蛘連i的出口是轉移語句(goto(s)或if…goto(s))，并且轉移目標(s)是Bj的入口語句。例：構造以下程序的流圖(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)不變運算，即其結果獨立于循環(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的線性關系這樣把(12)的循環(huán)控制條件I≤20變換成T1≤80，程序的運行結果不變這種變換稱為變換循環(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:=