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

優(yōu)化對代碼進行的變換必須遵守以下原則：1.等價原則:經(jīng)優(yōu)化的代碼執(zhí)行結(jié)果不變；2.有效原則:優(yōu)化后確實執(zhí)行時間短、占用空間少;3.合算原則:以較低的代價，換取較好的優(yōu)化效果。第十章優(yōu)化優(yōu)化主要為兩類：中間代碼的優(yōu)化(不依賴硬件)目標代碼的優(yōu)化(依賴硬件)本章討論的優(yōu)化主要指對中間代碼進行等價的變換，使其成為執(zhí)行效率更高的中間碼。P272圖10.1給出了代碼優(yōu)化的地位和結(jié)構(gòu)。10.1概述1該語句段的中間代碼見P274圖10.2以下通過一個實例簡介各種優(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每個數(shù)組元素占4個單元3一.刪除公共子表達式（多余運算）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變換為：

因為：B2中已有T2:=4*i，且在進入B5前未改變過T2;B3中已有T4:=4*j，且在進入B5前未改變過T4;所以可將B5變換為：T6:=T2;x:=a[T6];T7:=T6;

T8:=T4;T9:=a[T8];a[T7]:=T9;T10:=T8;a[T10]:=x;GotoB2B54二.復寫傳播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因為：B2中已有T3:=a[T2]，且在進入B5前未改變過T3;B3中已有T5:=a[T4]，且在進入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)…五.強度削弱循環(huán)中的代碼，由于循環(huán)執(zhí)行多遍，應(yīng)盡量用+、-法取代*、/法等強度高的運算。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強度削弱后，i和j僅在B4中引用，因此可將i和j的賦值語句刪除，并將B4改為:ifT2>=T4gotoB6七.合并已知量若某些表達式的運算量在編譯時是已知的，則應(yīng)直接給出結(jié)果，而無須保留表達式。例：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í)行的語句系列，其中只有一個入口和一個出口，第一個語句為入口，最后一個語句為出口。對于語句：x:=y+z我們稱該語句對x定值，對y和z引用。如果一個變量在某語句之后還將被引用，則稱變量在該點（語句）是活躍的。對于給定的一個程序，可以將其劃分為一系列的基本塊，分別在塊內(nèi)進行局部優(yōu)化（基本塊內(nèi)的優(yōu)化）。以下先給出劃分基本塊的算法。101.求出程序中可做基本塊入口的語句，它們是：(1)程序的第一個語句；(2)能由條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句轉(zhuǎn)移到的語句；(3)緊跟在條件轉(zhuǎn)移語句后面的語句。2.對以上入口語句，構(gòu)造其所屬的基本塊：此入口語句到下一條入口語句前，或下一條跳轉(zhuǎn)語句，或一條停語句的語句序列組成一個基本塊。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(強度削弱)以基本塊為結(jié)點，構(gòu)造程序的流程圖，稱為流圖。如前例程序的流圖為：B4writeyhaltreadxready R:=xmodyifR=0goto(8)x:=yy:=Rgoto(3)B1B2B3對基本塊內(nèi)的語句可以進行如下一些優(yōu)化變換：1.合并已知量；2.交換語句位置:T1:=b+c若x,y均不為T1T2:=x+y b,c均不為T2

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

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

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

2、NODE(A)有定義，則刪除A在原結(jié)點的標記。

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

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

。在構(gòu)造基本塊的DAG時，當參與運算的結(jié)點均為常數(shù)時，已直接計算結(jié)果，生成新常數(shù)結(jié)點（合并已知量）。以下通過一個例子介紹基本塊的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)刪除公共子表達式。17對該基本塊還可進行如下優(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)的目標代碼。18目標代碼生成器的位置：源中間中間目標程序代碼代碼程序編譯前端代碼優(yōu)化代碼生成器

符號表

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