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

刪除多余運算（刪除公共子表達式）如果子表達式E在前面計算過，且之后E中的變量值都未改變，那么E的重復出現稱為公共子表達式，可避免重復計算(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.刪除無用賦值有些變量的賦值從未被引用，稱為無用賦值，應刪除。無用賦值分三種情況：變量被賦值，但在程序中從未被引用（在局部范圍內難判定）

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

變量的賦值只被計算變量自己引用，其他變量都不引用它例（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.其他優化技術以下優化技術將在循環優化中介紹：

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

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

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

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

且Bi的出口語句不是無條件轉移語句或停止語句。或者Bi的出口是轉移語句(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循環優化1.代碼外提把循環不變運算，即其結果獨立于循環執行次數的表達式，提到循環的前面，使之只在循環外計算一次，這種優化稱為代碼外提。循環不變運算：運算量為常量或在循環外定值，每次循環時其值不變的運算。(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)是分配的數組A的首地址，是個常量，4也是常量，因而(4)是循環不變運算，同樣(7)也是循環不變運算，(4)、(7)都可提到循環前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)的循環控制條件I≤20變換成T1≤80，程序的運行結果不變這種變換稱為變換循環控制條件經過這一變換，循環中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)變換循環控制條件(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)變換循環控制條件中間代碼段(1)P:=0(2)I:=1(4)T2:=addr(A)－4(7)T5:=addr(B)－4(3)T1:=4*I(5)T3:=