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

1、第七章第七章 代碼優(yōu)化代碼優(yōu)化(1) 代碼優(yōu)化的基本概念(2) 基本塊內(nèi)的代碼優(yōu)化(3) 基于循環(huán)的代碼優(yōu)化(4) 窺孔優(yōu)化7.1 概述概述 提高代碼質(zhì)量的技術(shù)稱代碼優(yōu)化： 與機器有關(guān)的優(yōu)化，即在目標(biāo)代碼上進行，如對寄存器的優(yōu)化、多處寄存器的優(yōu)化、多處理機的優(yōu)化、特殊指令的優(yōu)化等理機的優(yōu)化、特殊指令的優(yōu)化等。有時因為這種優(yōu)化只觀察中間代碼或目標(biāo)代碼的相鄰部分，并對其進行優(yōu)化，所以又稱為窺孔優(yōu)化窺孔優(yōu)化。 與機器無關(guān)的優(yōu)化，一般在中間代碼上進行，根據(jù)優(yōu)化對象所涉及的程序范圍，又分為局部優(yōu)化、局部優(yōu)化、循環(huán)優(yōu)化和全局優(yōu)化循環(huán)優(yōu)化和全局優(yōu)化。這類優(yōu)化不依賴于目標(biāo)機，是本章的重點內(nèi)容。 例7.1 設(shè)A

2、、B分別為兩個一維數(shù)組，A0、B0或addr(A)、addr(B)分別表示它們的初始地址，給定源程序段：S=0; n=1001; /循環(huán)循環(huán)1000次次For(i=1; in; i+) s=s + Ai * Bi;A, B是一維數(shù)組，每個數(shù)占4個字節(jié)w=4，中間代碼如圖7.1所示，注意，程序運行時，注意，程序運行時，首先要判斷循環(huán)控制變量首先要判斷循環(huán)控制變量i是否超界，若越界是否超界，若越界則一次也不執(zhí)行循環(huán)體，與具體程序語言的則一次也不執(zhí)行循環(huán)體，與具體程序語言的規(guī)定有關(guān)。規(guī)定有關(guān)。圖圖7.1 P146 n=211 刪除公共子表達式刪除公共子表達式 （刪除多余運算、公共表達式節(jié)?。▌h除多

3、余運算、公共表達式節(jié)?。?公共子表達式是指在一個基本程序塊內(nèi)計算結(jié)果相同的子表達式。如圖中的四元式（5）和（8），（8）可刪除，并將引用T4的改為引用T1。即刪除四元式（8）后再將（10）中的T4改為T1（這一步也可在刪除無用賦值時處理）。結(jié)果如圖7-2所示。2 代碼外提 代碼外提是指將循環(huán)中的不變運算提到循環(huán)體前面。若循環(huán)體內(nèi)的某些運若循環(huán)體內(nèi)的某些運算，不管循環(huán)體運算多少次，都不影響算，不管循環(huán)體運算多少次，都不影響循環(huán)結(jié)束后的計算結(jié)果，則這類運算稱循環(huán)結(jié)束后的計算結(jié)果，則這類運算稱不變運算。不變運算。不變運算放在循環(huán)體內(nèi)只會增加代碼的執(zhí)行時間。 如本例中的T2和T5（分別在四元式（6）和

4、（9）中），程序裝入內(nèi)存后，數(shù)組的首地址是確定的，可見T2、T5不隨循環(huán)體的執(zhí)行而變化，可以提到循環(huán)體外。結(jié)果如圖7-3所示。 3 強度削弱（或稱削減運算強度） 實際上是將乘法運算改寫為加法運算的一種方法：（*，a，i，T）其中，a是常量，i是循環(huán)控制變量，而且只有這類乘法運算可以進行強度削弱。如本例中的四元式(5)（*，4，i，T1）注意注意T1的值的變化規(guī)律：的值的變化規(guī)律：i=1 T1=4i=2 T1=8i=3 T1=12i=4 T1=16 每循環(huán)一次T1的值增加4，如果在循環(huán)體外給T1賦初值4*i，將（5）刪除，并在四元式(14)之前插入一個四元式：（+，T1，4，T1） 同樣可以達到

5、每循環(huán)一次T1增加4的目的，就本例來說，999次乘法變成了1000次加法，也就是說削減了運算強度，提高了目標(biāo)代碼執(zhí)行的效率。結(jié)果如圖7-4所示。4 變換循環(huán)控制條件（刪除歸納變量） For循環(huán)中，控制變量i的作用域是本循環(huán)體，如果在循環(huán)體內(nèi)存在一個變量或臨時變量T與i保持線性關(guān)系，同時在循環(huán)體后面不引用i，而除去i又不影響程序結(jié)果，則可由T取代i的控制循環(huán)次數(shù)的作用（實際上，用算法實現(xiàn)是很困難的實際上，用算法實現(xiàn)是很困難的）。從循環(huán)中刪除i，這種方法稱為變換循環(huán)體控制條件或者稱為刪除歸納變量。 本例中，i與T1保持線性關(guān)系，若在循環(huán)體外不再引用i，則循環(huán)控制條件可以改變?yōu)門14*n，即刪除刪除

6、四元式（四元式（13）并將四元式（）并將四元式（3）改為：）改為：（，T1，4*n，T0）5 合并已知量（合并常量、常表達式節(jié)?。?若四元式中的兩個運算量都是常數(shù)，則在編譯時就計算出結(jié)果，不必等到程序運行時再計算。6 其它： 復(fù)寫傳播； 刪除無用賦值7.2 局部優(yōu)化7.2.1 基本塊的劃分方法基本塊是指代碼序列中一組順序執(zhí)行的語句序列。其中只有一個入口，一個出口，并且入口是基本塊的第一個四元式，出口是基本塊的最后一個四元式 。（不能用語句，一般來說，一個語（不能用語句，一般來說，一個語句對應(yīng)多個四元式）句對應(yīng)多個四元式） 劃分基本塊實質(zhì)上是準(zhǔn)確定義入口四元式和出口四元式。1 從四元式序列確定滿

7、足以下條件的入口四元式（1）四元式序列的第一個四元式 （2）由條件或無條件轉(zhuǎn)移語句能轉(zhuǎn)到的四元式 （3）緊跟在條件轉(zhuǎn)移語句后面的四元式 2 確定滿足以下條件的出口四元式（1）下一個入口四元式的前導(dǎo)四元式（2）轉(zhuǎn)移四元式（包括自身）（3）停四元式（包括自身）3 構(gòu)造基本塊，刪除那些不屬于任何基本塊的四元式 在一個基本塊內(nèi)一般可以實行3種優(yōu)化：合并已知量或稱合并常量、合并公共子表達式、刪除無用賦值。7.2.2 基本塊上的優(yōu)化 DAG法、值編碼法、依賴數(shù)法、邏輯尺法等。DAG是無循環(huán)有向圖，是實現(xiàn)某種共享的理想工具，是軟件中的一種重要概念。7.3 循環(huán)上的優(yōu)化 （實質(zhì)上是一種局部優(yōu)化方法，可以作為7

8、.2.3小節(jié)）常用優(yōu)化方法： 代碼外提、強度削減7.4 窺孔優(yōu)化 窺孔優(yōu)化方法是一種簡單但有效的改進代碼質(zhì)量的技術(shù)。這種技術(shù)主要通過分析一小段目標(biāo)指令（稱為窺孔），并把這些指令替換為更快和更短的一段指令，從而提高代碼的質(zhì)量。 為了得到最大的優(yōu)化效果，有時需要對目標(biāo)代碼進行若干處理，進行窺孔優(yōu)化后的代碼結(jié)構(gòu)有可能給后續(xù)的優(yōu)化提供進一步的處理機會，這也是窺孔優(yōu)化的顯著特點之一。 窺孔是指目標(biāo)程序中的一個小窗口，窺孔中的代碼可以不相鄰。窺孔優(yōu)化主要包括刪除冗余存取指刪除冗余存取指令、刪除不可達代碼、控制流優(yōu)化、令、刪除不可達代碼、控制流優(yōu)化、強度削減、刪除無用操作等處理強度削減、刪除無用操作等處理。刪除冗余存取指令刪除冗余存取指令 (1) mov str , AX AXstr (2) mov AX , str strAX (1)將寄存器AX 中的數(shù)據(jù)保存到存儲器（即變量）str中 (2)從存儲器str中取數(shù)據(jù)裝入AX 中顯然，若(1)(2)兩條代碼連續(xù)出現(xiàn)，(2)可刪除。刪除不可達代碼刪除不可達代碼 不可達代碼是指程序的控制流不能到達的代碼，例 Goto L1 S1語句序列 L1：S2語句序列 若S1語句序列中無標(biāo)號語句，則S1語句序列即為不可達代碼，可以刪除。刪除無用操作刪除無用操作ADD