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

1、11.1 11.1 代碼優(yōu)化種類代碼優(yōu)化種類從代碼的范圍上分為 :局部優(yōu)化全局優(yōu)化 主要的局部優(yōu)化有基本塊上的優(yōu)化和循環(huán)上的優(yōu)化。 基本塊上的優(yōu)化主要有常表達(dá)式節(jié)省(合并常數(shù))、公共表達(dá)式節(jié)省(消除多余運(yùn)算)。 循環(huán)上的優(yōu)化主要有不變表達(dá)式外提和削減運(yùn)算強(qiáng)度。除了這些較典型的優(yōu)化外還有: 1.消除無用賦值。 2.刪除無用的0和1： A*1 處理為A A*0 處理為0 A0 處理為A A/1 處理為A 0/A 處理為0 等等。 3.合并符號:(-X)*(-Y)處理為X*Y 4.用乘法代替指數(shù)運(yùn)算: A*2 處理為A*A A*3 處理為A*A*A 等。11.2 11.2 基本塊基本塊基本塊可定義于

2、原代碼,中間代碼,也可定義于目標(biāo)代碼。關(guān)于目標(biāo)代碼的基本塊的定義是：說一個目標(biāo)代碼是基本塊,當(dāng)且僅當(dāng)該段只有一個入口和一個出口。定義于原代碼,中間代碼的基本塊定義類似?；緣K的特點(diǎn)是其中的代碼要么全執(zhí)行,要么全不執(zhí)行,不能在中途轉(zhuǎn)出,也不能從中間轉(zhuǎn)入。 基本塊類似程序中的函數(shù)，軟件工程中的模塊。基本塊的劃分方法：1. 把第一個四元式作為第一個基本塊的入口四元式。第一個四元式第一個四元式2. 當(dāng)遇標(biāo)號性四元式時，結(jié)束當(dāng)前塊，并作為新塊的入口四元式。標(biāo)號性四元式標(biāo)號性四元式第一個四元式第一個四元式3. 當(dāng)遇轉(zhuǎn)移性四元式時，結(jié)束當(dāng)前塊，并作為當(dāng)前塊的出口四元式。他們的后繼四元式作為新的入口四元式。

3、轉(zhuǎn)移性四元式轉(zhuǎn)移性四元式4. 當(dāng)遇形如(=:, A , , X)的賦值四元式(其中X為引用形參)時，結(jié)束當(dāng)前塊，并作為該塊的出口四元式。 含引用形參含引用形參賦值四元式賦值四元式 標(biāo)號性的四元式有： ( label， l )( while， )( proc， q，Noff，Moff )( func， f，Noff，Moff )( ifend， ) 等。 ( goto， ， ， l )( then， B， ， )( else， ， ， )( whend， ， )( call， g， ， )( call， f， ， T ) 等。 轉(zhuǎn)移性的四元式有： 例子：設(shè)有一程序段 Y:=1； 100：if A

4、B then X:=0 else Y:=0; X:=X+1； Y:=Y-1； if A， A， B， T1) AB (then，T1，) (=：， 0， ， X ) X:=0 (else， ) (=：， 0 ， ，Y ) Y:=0 ( ifend，) ( +, X ， 1， T2 ) X+1 ( =:, T2， ，X ) X:=X+1 ( , Y ， 1 ， T3 ) Y-1 ( =:, T3, , Y ) Y:=Y-1 ( , A , B , T4 ) A， A， B， T1) AB (then，T1，) 轉(zhuǎn)移性四元式 B3: (=：， 0， ， X ) X:=0 (else， ) 轉(zhuǎn)移性四

5、元式 B4: (=：， 0 ， ，Y ) Y:=0 B5: ( ifend，) 標(biāo)號性四元式 ( +, X ， 1， T2 ) X+1 ( =:, T2， ，X ) X:=X+1 ( , Y ， 1 ， T3 ) Y-1 ( =:, T3, , Y ) Y:=Y-1 ( , A , B , T4 ) AB ( then, T4, , ) 轉(zhuǎn)移性四元式B6: ( goto, ，100 ) 轉(zhuǎn)移性四元式B7: ( ifend, , , ) 標(biāo)號性四元式 ( =: 0 ， ， Z ) Z:=0 B1 B2 B3 B4 B5 B6 B7 程序圖如下:11.3 11.3 常表達(dá)式節(jié)省常表達(dá)式節(jié)省常表達(dá)式

6、節(jié)省也叫合并常數(shù)。它的優(yōu)化范圍通常取基本塊。優(yōu)化工作可在生成四元式的同時進(jìn)行，也可在生成四元式后進(jìn)行。前一種方法叫單遍掃描法，而后一種叫多遍掃描法。例：設(shè)有程序代碼a:=10；b:=2*a；c:=a*b；可以轉(zhuǎn)化為：a:=10；b:=20；c:=200；優(yōu)化后的四元式： 1)(=:， 10，-, a) 2)(=:， 20，-, b) 3)(=:，200，-, c)下面介紹獨(dú)立進(jìn)行的多遍掃描法，用到變量值表VVL，其結(jié)構(gòu)如下：VVLk： NAME VALU 變量名部分值部分多遍掃描常表達(dá)式節(jié)省算法VVL表置空，令i指向本塊的第一個四元式.若對j=1,2,存在k:QTi.OPRj=VVLk.NAM

7、E,則做QTi.OPRj:=VVLk.VALU (從表中取值) 3. 若OTi.不是運(yùn)算符,則轉(zhuǎn)向5.(進(jìn)一步判別該四元式是否為賦值語句)4. 如果QTi.OPRj(j=1,2)都是常數(shù),則計(jì)算結(jié)果,填VVL表,并刪除四元式QTi: ENTRY(QTi.RESU, cons) (填寫表中值) QTi:=(, , , ) (四元式節(jié)省) 轉(zhuǎn)向6.其中ENTRY是填寫VVL表的子程序, cons表示計(jì)算結(jié)果的CONSL表地址.若有同名項(xiàng),則只改內(nèi)容.5.若QTi.“:=”則轉(zhuǎn)向6;否則 (賦值語句) (a)若QTi.OPR1是常數(shù),則填VVL表: ENTRY(QTi.RESU, QTi.OPR1)

8、 (b)若QTi.OPR1是非常數(shù),則刪VVL表: DELET(QTi.RESU) 其中DELET(X)表示從VVL表刪去包含X名字的項(xiàng),如果沒有那種項(xiàng),則什么也不做.6.i:=i+1;若QTi不是出口型四元式,則轉(zhuǎn)向2,否則結(jié)束.例：合并常數(shù) i:=2+5; j:=i+3; k:=2*i+j; i:=i*j+k+m;(=,T7,-,l) 11.(=:,T7,-,l) (+,94,m,T7) 10.(+,T6,m,T6) 9.(T6,94) ($,-,-,-) 9.(+,T5,k,T6) 8.(T5,70)($,-,-,-) 8.(*,i,j,T5) i:=i*j+k+m;7.(k,24) (

9、=:,24,-,k) 7.(=:,T4,-,k) 6.(T4,24) ($,-,-,-) 6.(+,T3,j,T4) 5.(T3,14) ($,-,-,-) 5.(*,2,i,T3) k:=2*i+j;4.(j,10) (=:,10,-,j) 4.(=:,T2,-,j) 3.(T2,10) ($,-,-,-) 3.(+,i,3,T2) j:=i+3;2.(i,7) (=:,7,-,i) 2.(=:,T1,-,i) 1.(T1,7) ($,-,-,-) 1.(+,2,5,T1) i:=2+5;VVL表 合并后的合并前的源代碼 11.4 11.4 公共表達(dá)式節(jié)省公共表達(dá)式節(jié)省 公共表達(dá)式節(jié)省的范圍

10、是一個基本塊。如果兩個四元式的和OPR1及OPR2的值分別相同,則稱這兩個四元式等價。如果在基本塊中出現(xiàn)多個等價四元式,則除了第一個外其他的均可節(jié)省。 公共表達(dá)式節(jié)省工作是通過四元式的節(jié)省來實(shí)現(xiàn)的。實(shí)現(xiàn)四元式節(jié)省的關(guān)鍵是判別兩個四元式是否等價。例:設(shè)有程序段： D:=D+C*B; A:=D+C*B; C:=D+C*B;問:是否可以寫成下面的程序? T:=D+C*B; D:= T; A:= T; C:= T;它的四元式所構(gòu)成的基本塊為： 1(*，C, B, T1) C*B 2(+, D, T1, T2) D+C*B 3(=:,T2, D ) D:=D+C*B 4(*, C, B, T3) C*B

11、 5(+, D, T3, T4) D+C*B 6(=:,T4, A ) A:=D+C*B 7(*, C, B, T5) C*B 8(+, D, T5, T6) D+C*B 9(=: T6, C ) C:=D+C*B其中四元式1，4，7的運(yùn)算符、OPR1、OPR2均相等，所以可以用T1代替T3、T5。 1(*，C, B, T1) C*B 2(+, D, T1, T2) D+C*B 3(=:,T2, D ) D:=D+C*B 4( ) 被省略 5(+, D, T T1 1, T4) D+C*B 6(=:,T4, A ) A:=D+C*B 7( ) 被省略 8(+, D, T T1 1, T6) D

12、+C*B 9(=: T6, C ) C:=D+C*B 其中四元式2,5,8的運(yùn)算符、OPR1、OPR2均相等但5、8中的D與2中的不同所以不可以用T2代替T4、T6。四元式5和8相同因此四元式8對5是多余的。經(jīng)優(yōu)化后可得到下列四元式代碼： 1(*, C, B，T1) 2(+, D, T1，T2) 3(=:,T2,，D) 4( )被省略 5(+, D, T1，T3) 6(=, T3,A) 7( )被省略 8( )被省略 9( =:,T3,C) 公共表達(dá)式節(jié)省是通過四元式的節(jié)省來實(shí)現(xiàn)的。目前已提出多種實(shí)現(xiàn)方法，其中包括：值編碼法，依賴數(shù)法，邏輯尺法，DAG法等。 值編碼方法： 按一定規(guī)則給四元式中

13、的每個變量進(jìn)行編碼,使得具有相同編碼的變量具有相同值。判定兩個四元式是否等價的方法是看其分量的編碼是否分別相同。判斷四元式等價的關(guān)鍵是判斷兩個變量的值是否等價。使問題復(fù)雜化的主要因素是間接變量的存在。間接變量:引用型形參變量 存復(fù)合變量地址的臨時變量為了判斷一個變量是否依賴于間接變量,引進(jìn)編碼 # ,首先使間接變量取編碼#; 其次,假設(shè)(, A , B , C) 且A , B 中有一個編碼取#,則令C的編碼取#。如果四元式有一分量的編碼為#,則該四元式就不可節(jié)省。 設(shè)當(dāng)前四元式為(, A, B, C)，且用newn表示新的編碼值。值編碼規(guī)則： 1.開始對一切X,令n(X)=0,以表示未編過碼。

14、 2.若操作數(shù)A是未編過碼的并且是非間接變量，則給新的編碼（否則給老的編碼） IF indirect(A) THEN N(A):=# ELSE IF n(A)=0 THEN n(A)=newn 3.對操作數(shù)B類似步驟2。 4.對于C的處理過程是： a) (=:, A, -, C)情況 IF direct(C) THEN n(C):=n(A) ELSE n(C):=# b) ( ,A,B,C),(,A,B,C)情況 n(C):=# c) 其他情況： IF n(A)=# n(B)=# THEN n(C):=# ELSE n(C):=newn例：(下邊四元式中沒有間接變量) X:=1 Z:=X*Y

15、X:=1 W:=X*Y 得到的四元式如下： 4 4 6.(=:, T2,-,W) 1 2 4 5.(*, X, Y,T2) 1 1 4.(=:, 1，-,X) 3 3 3.(=:, T1,-,Z) 1 2 3 2.(*, X，Y,T1) 1 1 1.(=：,1,-,X) 編 碼 四 元 式 多邊掃描公共表達(dá)式節(jié)省算法： 設(shè)新老變量名表為ML,每當(dāng)一個四元式被節(jié)省時要填寫ML表。1.置ML表為空,令所有量均無編碼,i:=i0.2.若QTi的OPR1或OPR2ML,則用ML中的 老名代替OPR1或OPR2. （使用新老變量名表ML）3.若QTi為非考慮類,則轉(zhuǎn)8.（處理下一四元式）4.對QTi中的

16、三個變量進(jìn)行編碼.5.若QTi.=“=:”,則轉(zhuǎn)8.例： A:=3*X+Y B:=(3*X+Y)*A得到的四元式如下：6.若QTi的OPR1或OPR2的編碼為#,則轉(zhuǎn)8.7.若存在i使QTiQTi(等價),則 a. QTi:= ($,-，- ，-) b. MLm:=(QTi.RESU, QTi.RESU) （填寫新老變量名表ML）8.i:=i+1;若本塊未完轉(zhuǎn),否則結(jié)束.(=:,T5,-,B) 8 8 7.(=:,T5,-,B) (*,T2,A,T5) 5(7) 5 8 6.(*,T4,A,T5) ($,-,-,-) 3(6) 4 7 5.(+,T3,Y,T4) ($,-,-,-) 1 2 6

17、 4.(*,3,X,T3) (=:,T2,-,A) 5 5 3.(=:,T2,-,A) (+,T1,Y,T2) 3 4 5 2.(+,T1,Y,T2) (*,3,X,T1) 1 2 3 1.(*,3,X,T1)優(yōu) 化 后 編 碼 優(yōu) 化 前 例：設(shè)有語句列 X:=X*Y+ +Z; Y:=X*Y+ +Z; Z:=X*Y-Z 試用值編碼法寫出優(yōu)化和優(yōu)化后的四元式中間代碼。 優(yōu)化前1.(*, X,Y,T1 )2.(+,T1,Z,T2 )3.(:=,T2,-,X )4.(*, X, Y,T3 )5.(+, T3,Z,T4 )6.(:=,T4,-,Y )7.(*, X, Y,T5 )8.(-, T5,Z

18、,T6 )9.(:=,T6,-,Z ) 優(yōu)化前 編碼1.(*, X,Y,T1 ) (1,2,3)2.(+,T1,Z,T2 ) (3,4,5)3.(:=,T2,-,X ) (5, 5)4.(*, X, Y,T3 ) (5,2,6)5.(+, T3,Z,T4 ) (6,4,7)6.(:=,T4,-,Y ) (7, 7)7.(*, X, Y,T5 ) (5,7,8)8.(-, T5,Z,T6 ) (8,4,9)9.(:=,T6,-,Z ) (9, 9) 優(yōu)化前 編碼 優(yōu)化后 1.(*, X,Y,T1 ) (1,2,3) (*,X, Y,T1)2.(+,T1,Z,T2 ) (3,4,5) (+,T1,

19、Z,T2)3.(:=,T2,-,X ) (5, 5) (:=,T2,-,X)4.(*, X, Y,T3 ) (5,2,6) ( *,X,Y,T3)5.(+, T3,Z,T4 ) (6,4,7) ( +,T3,Z,T4)6.(:=,T4,-,Y ) (7, 7) (:=,T4,-,Y)7.(*, X, Y,T5 ) (5,7,8) ( *,X,Y,T5)8.(-, T5,Z,T6 ) (8,4,9) ( -,T5,Z,T6)9.(:=,T6,-,Z ) (9, 9) (:=,T6,-,Z) 基本塊上的優(yōu)化算法（同時進(jìn)行常表達(dá)式和公共表達(dá)式節(jié)省。例：設(shè)有 VAR a:ARRAY110 OF 110

20、 OF integer 和 aij:=aij-1(-,j,1，T4) 7 2 8 4.(-,j, 1,T4) (,a,T2,T3) 6 5 #3.(,a,T2,T3) (*,T1,10,T2) 3 4 5 2.(*,T1,10,T2) (-,i, 1,T1) 1 2 3 1.(-,i, 1,T1)優(yōu) 化 后 編 碼 優(yōu) 化 前 (=:,T11,-,T5) # # 12.(=:,T11,-, T5) (,a,T10,T11) # 12 # 11.(,T6,T10,T11) (-,T4,1, T10) 8 2 12 10.(-,T9,1,T10) ($,-，- ，-) 7 2 11 9.(-,j,

21、1,T9) ($,-，- ，-)6 5 #8.(,a,T7,T8) ($,-，- ，-)3 4 10 7.(*,T6,10,T7) ($,-，- ，-)1 2 9 6.(-,i,1,T6)(,T3,T4,T5)# 8 #5.(,T3,T4,T5)11.5 11.5 不變表達(dá)式外提不變表達(dá)式外提 如果一個表達(dá)式E在一個循環(huán)中不改變值，則稱它為該循環(huán)的不變表達(dá)式. 不變表達(dá)式外提的意思是把循環(huán)中的不變表達(dá)式提到循環(huán)外邊去。例：設(shè)有 i:=1; WHILE i=1000 DO Ai:=X*Y則從編譯程序角度看它就等價于 由于X*Y在循環(huán)體中始終不改變值，它是循環(huán)中的不變表達(dá)式。把它提到外邊得: i:

22、=1; T:=X*Y; WHILE i=1000 DO Ai:=T例：設(shè)有 j:=1; WHILE j=1000 DO Aij:=0則從編譯程序角度看它就等價于 j:=1; WHILE j=1000 DO BEGIN T1:=i-1; T2:=T1*10; T3:=AT2; T4:=j-1; T5:=T3T4; T5:=0 END 把循環(huán)的不變表達(dá)式提到循環(huán)外邊，則得到如下的程序段： j:=1; T1:=i-1; T2:=T1*10 T3:=AT2 WHILE j=1000 DO BEGIN T4=j-1; T5:=T3T4; T5:=0 END 外提優(yōu)化通常只考慮加、減、乘等算法以及關(guān)系運(yùn)算

23、和邏輯運(yùn)算等，稱它們?yōu)榭赏馓徇\(yùn)算。一般不考慮除法運(yùn)算。變量也可分為可外提量與不可外提量。T:=a/Y; WHILE B DO IF Y=0 THEN X:=Y ELSE X:=a/YWHILE B DO IF Y=0 THEN X:=Y ELSE X:=T 為了識別哪些變量是循環(huán)不變量,對每個循環(huán)構(gòu)造一個變量定義表VDL。該表記錄循環(huán)中被定義的變量。外提時首先把被提的四元式提到外提區(qū)YTL中,最后再把它插到四元式區(qū)中。 當(dāng)進(jìn)行循環(huán)上的優(yōu)化時，基本塊上的優(yōu)化已結(jié)束。 外提算法:1.求本層QT和VDL區(qū)的始地址.2.若當(dāng)前QTi是不可外提類,則轉(zhuǎn)向5.3.若QTi的OPR1或OPR2VDL.則轉(zhuǎn)向

24、5.4.（QTi可外提時） a)把QTi提到外提表YTL中. b)把QTi.RESU從本層VDL提到外層VDL c)刪除四元式QTi.5.準(zhǔn)備讀下一四元式,若未讀完則轉(zhuǎn)向2.6.把外提表的內(nèi)容插入到表的相應(yīng)位置中.VDL表的設(shè)計(jì)形式: t NAME VDLd: 其中t取0或1。1表示該變量已經(jīng)被外提。開始時t取0，每當(dāng)相應(yīng)變量被外提時把t的位置置成1。在查VDL表時只查t=0的元素。例：設(shè)有循環(huán)語句 i:=1; WHILE i 100 DO BEGIN Z:=i*K*5; A:=2*K+2*K*2; i:=i+1 END 則當(dāng)掃描完循環(huán)部分時生成的四元式和VDL表如下圖所示。 i:=1; WHILE: T1:=i100;TEST: T1?DO: T2:=i*K; Z:=T2*5; T3:=2*K; T4:=T3*2; T5:=T3+T4; A:=T5; i:=i+1WHENDi 0A 0T5 0T4 0T3 0Z 0T2 0T1 0外層 NAME tVDL表 現(xiàn)在要回頭掃描本層四元式并進(jìn)行外提。 i:=1; T3:=2*K; T4:=T3*2; T5:=T3+T4; WHILE: T1:=i=100;TEST: T1?DO: T2:=i*K; Z:=T2*5; A:=T5; i:=i+1WHENDi 0A 0T5 1T4 1T3 1Z 0T2