編譯原理 第九章 代碼優(yōu)化

1、第9章 代碼優(yōu)化9.1 代碼優(yōu)化概述代碼優(yōu)化概述9.2 局部優(yōu)化局部優(yōu)化9.3 控制流程分析和循環(huán)優(yōu)化控制流程分析和循環(huán)優(yōu)化9.4 數(shù)據(jù)流分析數(shù)據(jù)流分析寄存器、多處理器、寄存器、多處理器、特殊指令優(yōu)化等特殊指令優(yōu)化等v合并已知量v常數(shù)傳播v代數(shù)化簡v強(qiáng)度削弱v復(fù)寫傳播v刪除多余運(yùn)算v循環(huán)不變代碼外提v變換循環(huán)控制條件v刪除無用賦值基本優(yōu)化技術(shù)基本優(yōu)化技術(shù)常數(shù)合并a = 10 * 5 - b; _tmp0 = 10 ; _tmp1 = 5 ; _tmp2 = _tmp0 * _tmp1 ; _tmp3 = _tmp2 b; a = _tmp3 ; _tmp0 = 56 ; _tmp1 = _tm

2、p0 b ; a = _tmp1 ;常數(shù)傳播_tmp3 = 0 ;f0 = _tmp3 ; f0 = 0 ;代數(shù)化簡x+0 = x0+x = xx*1 = x1*x = x0/x = 0 x-0 = xb & true = bb & false = falseb | true = trueb | false = b削弱運(yùn)算強(qiáng)度a) i*2 = 2*i = i+i = i2b) i/2 = (int)(i*0.5)c) f*2 = 2.0 * f = f + f復(fù)寫傳播tmp2 = tmp1 ;tmp3 = tmp2 * tmp1;tmp5 = tmp3 * tmp2 ; tmp3 = tmp1

3、 * tmp1 ; tmp5 = tmp3 * tmp1 ; (1) P:=0(2) I:=1(3) T1:=4*I(4) T2:=addr(A)-4(5) T3:=T2T1(6) T4:=4*I(7) T5:=addr(B)-4(8) T6:=T5T4(9) T7:=T3*T6(10) P:=P+T7(11) I:=I+1(12) if I=20 goto(3)優(yōu)化技術(shù)實(shí)例:P:=0for I:=1 to 20 do P:=P+AI*BI刪除多余運(yùn)算刪除多余運(yùn)算(6) T4:=T1代碼外提代碼外提(1) P:=0(2) I:=1(4) T2:=addr(A)-4(7) T5:=addr(B)

4、-4強(qiáng)度削弱強(qiáng)度削弱(3) T1:= T1+4(3) T1:=4變換循環(huán)控制條件變換循環(huán)控制條件(12) if T1=80 goto(5)復(fù)寫傳播復(fù)寫傳播(8) T6:= T5T1刪除無用賦值刪除無用賦值(1) P:=0(4) T2:=addr(A)-4(7) T5:=addr(B)-4(3) T1:=4(5) T3:=T2T1(8) T6:=T5T1(9) T7:=T3*T6(10) P:=P+T7(3)T1:=T1+4(12) if T1= C goto L2(6) B:=B+1(7) goto L1(8) L2: write (A)(9) halt基本塊內(nèi)實(shí)行的優(yōu)化基本塊內(nèi)實(shí)行的優(yōu)化:

5、合并已知量合并已知量 刪除多余運(yùn)算刪除多余運(yùn)算 刪除無用賦值刪除無用賦值 DAG(Directed Acyclic Graph): 無環(huán)有向圖無環(huán)有向圖基本塊的基本塊的DAG是在結(jié)點(diǎn)上帶有標(biāo)記的是在結(jié)點(diǎn)上帶有標(biāo)記的DAG:一個(gè)基本塊一個(gè)基本塊一個(gè)一個(gè)DAG（體現(xiàn)基本塊內(nèi)各語句的聯(lián)系）（體現(xiàn)基本塊內(nèi)各語句的聯(lián)系）niXA，B，結(jié)點(diǎn)形式：結(jié)點(diǎn)形式：運(yùn)算符（運(yùn)算符（OP）-內(nèi)部結(jié)點(diǎn)內(nèi)部結(jié)點(diǎn)標(biāo)識(shí)符標(biāo)識(shí)符常數(shù)常數(shù)葉結(jié)點(diǎn)葉結(jié)點(diǎn)標(biāo)記標(biāo)記編號(hào)編號(hào)變量變量A，具具有所代表的值有所代表的值基本塊的DAG表示及其應(yīng)用v利用DAG進(jìn)行基本塊優(yōu)化的基本思想是： 四元式序列 = DAG = 四元式序列v四類四元式：0型四

6、元式：后繼結(jié)點(diǎn)個(gè)數(shù)為0，如圖 (1)所示；1型四元式：有一個(gè)后繼結(jié)點(diǎn)，如圖(2)所示；2型四元式：有兩個(gè)后繼結(jié)點(diǎn)，如圖(3)(4)(5)3型四元式：有三個(gè)后繼結(jié)點(diǎn)，如圖(6)所示。圖51 四元式與DAG結(jié)點(diǎn)(1) T0=3.14(2) T1=2*T0(3) T2=R+r(4) A=T1*T2(5) B=A(6) T3=2*T0(7) T4=R+r(8) T5=T3*T4(9) T6= Rr (10) B=T5*T6(1) T0=3.14(2) T1=6.28(3) T3=6.28(4) T2=R+r(5) T4=T2(6) A=6.28*T2(7) T5=A(8) T6= Rr (9) B=A

7、*T6若T0、T1、T6在基本快后面不被引用，則：(1) T2=R+r(2) A=6.28*T2(3) T6= Rr (4) B=A*T69.3 9.3 控制流分析和循環(huán)優(yōu)化控制流分析和循環(huán)優(yōu)化一個(gè)控制流程圖(簡稱流圖)就是具有惟一首結(jié)點(diǎn)的有向圖。所謂首結(jié)點(diǎn)，就是從它開始到控制流程圖中任何一個(gè)結(jié)點(diǎn)都有一條通路的結(jié)點(diǎn)。有向邊有向邊 基本塊基本塊 j j 在程序的位置緊跟在在程序的位置緊跟在i i 后后, ,且且 i i 的出口語句不是轉(zhuǎn)的出口語句不是轉(zhuǎn)移或停語句移或停語句 i i 的出口是的出口是 goto(S)goto(S)或或 if goto(S), if goto(S),而而( (S S)

8、 )是是 j j 的入口語句的入口語句 i j 例如，考察下面求最大公因子的三地址代碼程序：*(1) read X (2) read Y*(3) R=X % Y (4) if(R=0) goto(8)*(5) X=Y (6) Y=R (7) goto(3)*(8) write Y (9) halt(1) read X(2) read Y(3) R=X % Y(4) if (R=0) goto(8)(5) X=Y(6) Y=R(7) goto(3)(8) write Y(9) haltB1B2B3B4循環(huán)的查找循環(huán)的查找循環(huán)優(yōu)化循環(huán)優(yōu)化尋找循環(huán)尋找循環(huán)循環(huán)定義循環(huán)定義直觀上循環(huán)的構(gòu)成直觀上循環(huán)的

9、構(gòu)成=直觀上，入口結(jié)點(diǎn)是循環(huán)中其它結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)。在程序流圖中,對(duì)任意兩個(gè)結(jié)點(diǎn)m和n,如果從流圖的首結(jié)點(diǎn)出發(fā),到達(dá)n的任意通路都要經(jīng)過m,則稱m是n的必經(jīng)結(jié)點(diǎn),記為m DOM n (a,a DOM a)結(jié)點(diǎn)n的所有的集合,稱為結(jié)點(diǎn)n的必經(jīng)結(jié)點(diǎn)集D(n).入口入口-唯一性唯一性返回返回到入口到入口的反向邊的反向邊-回邊回邊結(jié)點(diǎn)互通結(jié)點(diǎn)互通1243576D(1)=1D(2)=1，2D(3)=1，2，3D(4)=1，2，4D(5)=1，2，4，5D(6)=1，2，4，6D(7)=1，2，4，7回邊：回邊：abab是流圖中的一條有向邊，如果是流圖中的一條有向邊，如果b DOM a b DOM a ?；?/p>

10、邊：6 -6、7-4、4-2循環(huán)：循環(huán)：回邊abab組成的循環(huán)是由結(jié)點(diǎn)b b、a a以及有通路到達(dá)以及有通路到達(dá)a a而該通而該通路不經(jīng)過路不經(jīng)過b b的所有結(jié)點(diǎn)組成，并且的所有結(jié)點(diǎn)組成，并且b b是該循環(huán)的唯一入口結(jié)點(diǎn)。是該循環(huán)的唯一入口結(jié)點(diǎn)。dnk回邊：回邊：nd循環(huán)循環(huán)Ld-入口入口nkkn*不經(jīng)不經(jīng)d64,5,6,72,3,4,5,6,7圖58 給循環(huán)建立前置結(jié)點(diǎn)9.3 代碼優(yōu)化示例通過一個(gè)快速排序子程序來了解代碼優(yōu)化的全過程。void quicksort (int m, int n)int i, j, v, x; if(n=m) return; /*fragment begins h

11、ere*/ i=m1; j=n; v=an; while(1) do i=i+1; while(aiv); if(i=j) break; x=ai; ai=aj; aj=x; x=ai; ai=an; an=x; /*fragment ends here*/ quicksort(m, j); quicksort(i+1,n);圖521給出了程序中兩個(gè)注解行之間的語句翻譯成中間代碼序列后所對(duì)應(yīng)的程序流圖，其代碼優(yōu)化如下。1刪除公共子表達(dá)式v在B5中分別把公共子表達(dá)式4*i和4*j的值賦給T7和T10，因此這種重復(fù)計(jì)算可以消除，即B5中的代碼變換成：B5:T6=4*i x=aT6 T7=T6 T8

12、=4*j T9=aT8 aT7=T9 T10=T8 aT10=x goto B2v可以在更大范圍內(nèi)來考慮刪除公共子表達(dá)式的問題，即利用B3中的四元式T4=4*j可以把B5中的代碼T8=4*j替換為T8=T4。v同樣，可以把B5中的代碼T6=4*i替換為T6=T2。對(duì)于B6也可以同樣考慮，最后，刪除公共子表達(dá)式后的程序流圖如圖522所示。圖521 程序流圖 T6=4*i x=aT6T7=4*i T8=4*jT9=aT8 aT7 = T9T10=4*j aT10 =xgoto B2i=m-1 j=nT1=4*n v=aT1B1i=i+1 T2=4*iT3=aT2if T3v goto B3if i

13、=j goto B6T11=4*i x=aT11T12=4*i T13=4*nT14=aT13 aT12 = T14T15=4*naT15 =xB2B3B4B5B6FTFFTTT6=T2 x=aT6T7=T6 T8=T4T9=aT8 aT7 = T9T10=T8 aT10 =xgoto B2T11=T2 x=aT11T12=T11 T13=T1T14=aT13 aT12 = T14T15=T1aT15 =x圖522 刪除公共子表達(dá)式后的程序流圖2復(fù)寫傳播v圖522中的B5還可以把x=aT6變換為x=aT2。這種變換稱為復(fù)寫傳播。B5變?yōu)椋篢6=T2x=aT2T7=T2T8=T4T9=aT4aT

14、2= T9T10=T4aT4=xgoto B2v進(jìn)一步，在B5中可把x=aT2替換為x=T3，并繼續(xù)通過復(fù)寫傳播，把B5中的aT4=x替換為aT4 =T3。同樣，把B5中的T9=aT4替換為T9=T5，aT2=T9替換為 aT2=T5。B5變?yōu)椋篢6=T2x= T3T7=T2T8=T4T9=T5aT2= T5 T10=T4aT4= T3goto B23刪除無用賦值v進(jìn)行了復(fù)寫傳播后的B5，其中的變量x及臨時(shí)變量T6、T7、T8、T9、T10在整個(gè)程序中不再使用，故可以刪除對(duì)這些變量賦值的四元式。B5變?yōu)椋?aT2= T5 aT4= T3 goto B2v對(duì)B6進(jìn)行相同的處理后變?yōu)椋?aT2=

15、v aT1= T3v復(fù)寫傳播和刪除無用賦值后的程序流圖如圖5-23所示。圖523 復(fù)寫傳播和刪除無用賦值后的程序流圖aT2 = T5aT4 = T3goto B2i=m-1 j=nT1=4*n v=aT1B1i=i+1 T2=4*iT3=aT2if T3v goto B3if i=j goto B6aT2 = vaT1 =T3B2B3B4B5B6FTFFTT4代碼外提：沒有可外提到循環(huán)之外的不變運(yùn)算。 5強(qiáng)度削弱v觀察圖523的內(nèi)循環(huán)B3，可以把循環(huán)中計(jì)算T4值的乘法運(yùn)算變?yōu)樵谘h(huán)前進(jìn)行一次乘法運(yùn)算而在循環(huán)中進(jìn)行減法運(yùn)算。同樣，對(duì)循環(huán)B2中的T2=4*i也可以進(jìn)行強(qiáng)度削弱。經(jīng)過強(qiáng)度削弱后的程序流圖如圖5-24所示。6刪除歸納變量v由圖524可知，B2中T2與i之間保持著T2=4*i的線性關(guān)系；而B3中T4與j之間保持著T4=4*j的線性關(guān)系。在對(duì)T2=4*i和T4=4*j進(jìn)行了強(qiáng)度削弱后，i和j僅出現(xiàn)在條件句if Ij goto B6中。因此，可以變換歸納變量而把此條件