編譯原理陳火旺版10-11章

優(yōu)化對代碼進(jìn)行的變換必須遵守以下原則：1.等價(jià)原則:經(jīng)優(yōu)化的代碼執(zhí)行結(jié)果不變；2.有效原則:優(yōu)化后確實(shí)執(zhí)行時(shí)間短、占用空間少;3.合算原則:以較低的代價(jià)，換取較好的優(yōu)化效果。第十章優(yōu)化優(yōu)化主要為兩類：中間代碼的優(yōu)化(不依賴硬件)目標(biāo)代碼的優(yōu)化(依賴硬件)本章討論的優(yōu)化主要指對中間代碼進(jìn)行等價(jià)的變換，使其成為執(zhí)行效率更高的中間碼。P272圖10.1給出了代碼優(yōu)化的地位和結(jié)構(gòu)。10.1概述1該語句段的中間代碼見P274圖10.2以下通過一個(gè)實(shí)例簡介各種優(yōu)化方法。例見P273中的C語言程序，以下為其部分語句： i=m-1;j=n;v=a[n]; While(1){ doi=i+1;while(a[i]<v); doj=j-1;while(a[j]>v); if(i>=j)break; x=a[i];a[i]=a[j];a[j]=x; } x=a[i];a[i]=a[n];a[n]=x;2i:=m-1;j:=n;T1:=4*n;v:=a[T1];i:=i+1;T2:=4*i;T3:=a[T2];ifT3<vgotoB2j:=j-1;T4:=4*j;T5:=a[T4];ifT5>vgotoB3ifi>=jgotoB6T6:=4*i;x:=a[T6];T7:=4*i;T8:=4*j;T9:=a[T8];a[T7]:=T9;T10:=4*j;a[T10]:=x;gotoB2T11:=4*i;x:=a[T11];T12:=4*i;T13:=4*n;T14:=a[T13];a[T12]:=T14;T15:=4*n;a[T15]:=x;B6B2B3B5B4B1每個(gè)數(shù)組元素占4個(gè)單元3一.刪除公共子表達(dá)式（多余運(yùn)算）T6:=4*i;x:=a[T6];T7:=4*i;

T8:=4*j;T9:=a[T8];a[T7]:=T9;T10:=4*j;a[T10]:=x;gotoB2B5T6:=4*i;x:=a[T6];T7:=T6;T8:=4*j;T9:=a[T8];a[T7]:=T9;T10:=T8;a[T10]:=x;GotoB2B5變換為：

因?yàn)椋築2中已有T2:=4*i，且在進(jìn)入B5前未改變過T2;B3中已有T4:=4*j，且在進(jìn)入B5前未改變過T4;所以可將B5變換為：T6:=T2;x:=a[T6];T7:=T6;

T8:=T4;T9:=a[T8];a[T7]:=T9;T10:=T8;a[T10]:=x;GotoB2B54二.復(fù)寫傳播T6:=T2;x:=a[T6];T7:=T6;

T8:=T4;T9:=a[T8];a[T7]:=T9;T10:=T8;a[T10]:=x;GotoB2B5變換為：

T6:=T2;x:=a[T2];T7:=T2;T8:=T4;T9:=a[T4];a[T2]:=T9;T10:=T4;a[T4]:=x;GotoB2B5因?yàn)椋築2中已有T3:=a[T2]，且在進(jìn)入B5前未改變過T3;B3中已有T5:=a[T4]，且在進(jìn)入B5前未改變過T5;所以可將B5變換為：T6:=T2;x:=T3;T7:=T2;T8:=T4;T9:=T5;a[T2]:=T5;T10:=T4;a[T4]:=T3;GotoB2B55三.刪除無用代碼T6:=T2;

x:=T3;T7:=T2;

T8:=T4;T9:=T5;a[T2]:=T5;T10:=T4;a[T4]:=T3;GotoB2B5對于如右圖所示的B5，由于X,T6,T7,T8,T9,T10在程序中不再使用，因此可刪除對這些變量的賦值語句。a[T2]:=T5;a[T4]:=T3;GotoB2對于B6可以像B5一樣作相應(yīng)的優(yōu)化變換：T11:=4*i;x:=a[T11];T12:=4*i;T13:=4*n;T14:=a[T13];a[T12]:=T14;T15:=4*n;a[T15]:=x;B6變換為：

T11:=T2;x:=a[T2];T12:=T2;T13:=T1;T14:=a[T1];a[T2]:=T14;T15:=T1;a[T1]:=x;B6a[T2]:=v;a[T1]:=T3;B66四.代碼外提對循環(huán)中的有些代碼，若它的結(jié)果在循環(huán)中不變，可將這些代碼提到循環(huán)外，以避免循環(huán)執(zhí)行。例：while(i<=limit-2)…變換為：

t:=limit-2while(i<=t)…五.強(qiáng)度削弱循環(huán)中的代碼，由于循環(huán)執(zhí)行多遍，應(yīng)盡量用+、-法取代*、/法等強(qiáng)度高的運(yùn)算。i:=i+1;T2:=4*i;T3:=a[T2];ifT3<vgotoB2B2變換為：

T2:=4*i;i:=i+1;T2:=T2+4;T3:=a[T2];ifT3<vgotoB2B27六.刪除歸納變量(圖10.4）

B2中的i每循環(huán)一次增值1，T2與i保持線性關(guān)系，B3中的j每循環(huán)一次遞減1，T4與j保持線性關(guān)系，我們稱這些變量為歸納變量，T2、T4強(qiáng)度削弱后，i和j僅在B4中引用，因此可將i和j的賦值語句刪除，并將B4改為:ifT2>=T4gotoB6七.合并已知量若某些表達(dá)式的運(yùn)算量在編譯時(shí)是已知的，則應(yīng)直接給出結(jié)果，而無須保留表達(dá)式。例：i:=1;T:=4*i;變換為：

i:=1;T:=4;8經(jīng)前述各種優(yōu)化處理后，最終的中間代碼如下：i:=m-1;j:=n;T1:=4*n;v:=a[T1];T2:=4*i;T4:=4*j;T2:=T2+4;T3:=a[T2];ifT3<vgotoB2T4:=T4+4;T5:=a[T4];ifT5>vgotoB3ifT2>=T4gotoB6a[T2]:=T5;a[T4]:=T3;gotoB2a[T2]:=V;a[T1]:=T3;B6B2B3B5B4B1910.2局部優(yōu)化一.基本塊及流圖基本塊：程序中一順序執(zhí)行的語句系列，其中只有一個(gè)入口和一個(gè)出口，第一個(gè)語句為入口，最后一個(gè)語句為出口。對于語句：x:=y+z我們稱該語句對x定值，對y和z引用。如果一個(gè)變量在某語句之后還將被引用，則稱變量在該點(diǎn)（語句）是活躍的。對于給定的一個(gè)程序，可以將其劃分為一系列的基本塊，分別在塊內(nèi)進(jìn)行局部優(yōu)化（基本塊內(nèi)的優(yōu)化）。以下先給出劃分基本塊的算法。101.求出程序中可做基本塊入口的語句，它們是：(1)程序的第一個(gè)語句；(2)能由條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句轉(zhuǎn)移到的語句；(3)緊跟在條件轉(zhuǎn)移語句后面的語句。2.對以上入口語句，構(gòu)造其所屬的基本塊：此入口語句到下一條入口語句前，或下一條跳轉(zhuǎn)語句，或一條停語句的語句序列組成一個(gè)基本塊。3.刪除未被納入任何基本塊的語句。例: (5)x:=y(1)readx (6)y:=R(2)ready (7)goto(3)(3)R:=xmody (8)writey(4)ifR=0goto(8) (9)halt入口語句有：(1)(3)(8)(5)基本塊有：{1,2}{3,4}{5,6,7}{8,9}113.代數(shù)變換：x:=y**2可變換為x:=y*y(強(qiáng)度削弱)以基本塊為結(jié)點(diǎn)，構(gòu)造程序的流程圖，稱為流圖。如前例程序的流圖為：B4writeyhaltreadxready R:=xmodyifR=0goto(8)x:=yy:=Rgoto(3)B1B2B3對基本塊內(nèi)的語句可以進(jìn)行如下一些優(yōu)化變換：1.合并已知量；2.交換語句位置:T1:=b+c若x,y均不為T1T2:=x+y b,c均不為T2

則可交換T1，T2兩賦值語句12二.基本塊的DAG表示及其應(yīng)用一個(gè)基本塊的DAG為如下形式的圖：(1)葉子結(jié)點(diǎn)：以一個(gè)標(biāo)識(shí)符或常數(shù)或變量的地址作為標(biāo)記。標(biāo)識(shí)符可以0為下標(biāo)，表示初值；(2)內(nèi)部結(jié)點(diǎn)：以運(yùn)算符為標(biāo)記；(3)各結(jié)點(diǎn)可附加多個(gè)標(biāo)識(shí)符，表示這些標(biāo)識(shí)符等價(jià)，且具有該結(jié)點(diǎn)的值。例見P282圖10.9(補(bǔ)充一簡單例子）構(gòu)造基本塊的DAG的算法見P282，以下簡單介紹該算法。1.基本塊的DAG表示131型：A:=OPB1、NODE(B)無定義，則構(gòu)造葉結(jié)點(diǎn)n,NODE(B)=n；2、若B為常數(shù)，則計(jì)算OPB=>P,若NODE(P)無定義，則構(gòu)造葉結(jié)點(diǎn)n,NODE(P)=n,執(zhí)行0型2。3、若B非常數(shù)，查有無OPB子樹：有：設(shè)NODE(OP)=n,執(zhí)行0型2；

無：構(gòu)造n結(jié)點(diǎn)OP,執(zhí)行0型2。0型：A:=B

1、NODE(B)無定義，則構(gòu)造葉結(jié)點(diǎn)n,NODE(B)=n；

2、NODE(A)有定義，則刪除A在原結(jié)點(diǎn)的標(biāo)記。

令NODE(A)=n。142型：A:=BOPC或A:=B[C]1、NODE(B)無定義，則構(gòu)造葉結(jié)點(diǎn)B；NODE(C)無定義，則構(gòu)造葉結(jié)點(diǎn)C；2、若B,C均為常數(shù)，則計(jì)算BOPC=>P,若NODE(P)無定義，則構(gòu)造葉結(jié)點(diǎn)n,NODE(P)=n,執(zhí)行0型2。3、若B,C不是常數(shù)，查有無BOPC子樹：有：設(shè)NODE(OP)=n,執(zhí)行0型2；

無：構(gòu)造n結(jié)點(diǎn)OP,執(zhí)行0型2

。在構(gòu)造基本塊的DAG時(shí)，當(dāng)參與運(yùn)算的結(jié)點(diǎn)均為常數(shù)時(shí)，已直接計(jì)算結(jié)果，生成新常數(shù)結(jié)點(diǎn)（合并已知量）。以下通過一個(gè)例子介紹基本塊的DAG1586571343.146.28T0T1T3Rr*+-T6T2T4T5A*BB2例：T0:=3.14 T1:=2*T0 T2:=R+r A:=T1*T2 B:=A T3:=2*T0 T4:=R+r T5:=T3*T4 T6:=R-r B:=T5*T6其DAG如右圖所示：16由該圖重寫的代碼序列如下：86571343.146.28T0T1T3Rr*+-T6T2T4T5A*BB2 T0:=3.14

T1:=6.28 T3:=6.28 T2:=R+r

T4:=T2 A:=6.28*T2

T5:=A T6:=R-r B:=A*T6已完成了如下優(yōu)化：合并已知量；刪除無用代碼；(B:=A)刪除公共子表達(dá)式。17對該基本塊還可進(jìn)行如下優(yōu)化：

T0:=3.14 T1:=6.28 T3:=6.28 T2:=R+r

T4:=T2 A:=6.28*T2

T5:=A T6:=R-r B:=A*T6假設(shè)T0--T6在基本塊后不再使用，即可刪除對其的賦值，得到如下代碼： T2:=R+r A:=6.28*T2 T6:=R-r B:=A*T6若調(diào)整語句順序如下：T6:=R-rT2:=R+rA:=6.28*T2B:=A*T6將可得到更優(yōu)的目標(biāo)代碼。18目標(biāo)代碼生成器的位置：源中間中間目標(biāo)程序代碼代碼程序編譯前端代碼優(yōu)化代碼生成器

符號(hào)表

目標(biāo)代碼的形式：1、已定位的可立即執(zhí)行的機(jī)器語言代碼；2、可浮動(dòng)的機(jī)器語言代碼，需裝配連接再執(zhí)行；3、匯編語言目標(biāo)代碼，需匯編再執(zhí)行。第十一章目標(biāo)代碼生成目標(biāo)代碼應(yīng)具有高效性：目標(biāo)代碼較短；充分利用寄存器減少內(nèi)存訪問。1911.1一個(gè)簡單的代碼生成器P312中兩個(gè)表給出了一個(gè)模擬機(jī)的指令系統(tǒng)(類似匯編)。僅介紹一個(gè)簡單的目標(biāo)代碼生成方法：1、依次將每條中間代碼變換成等價(jià)的若干條目標(biāo)代碼；2、基本塊內(nèi)考慮充分利用寄存器的問題。即：基本塊內(nèi)計(jì)算出的變量值盡量保留在寄存器中，直至寄存器另有用途或已到基本塊的出口；引用變量時(shí)盡量用其在寄存器中的值。例現(xiàn)有賦值語句：A:=(B+C)*D+E其對應(yīng)的中間