編譯原理

CompilerTheory第九章代碼優(yōu)化9.1概述9.2基本塊內的優(yōu)化第9章代碼優(yōu)化29.1優(yōu)化概述1.優(yōu)化概念2.優(yōu)化方法合并已知量刪除多余運算代碼外提強度消弱刪除無用賦值31.優(yōu)化概念等價原則：對程序或中間代碼進行各種等價變換，使得從變換后的程序出發(fā)，能生成更有效的目標代碼。有效原則：優(yōu)化的目的在于既要設法縮小存儲空間，又要盡量提高運行速度，而且更偏重于提高運行速度。合算原則：應盡可能以較低的代價取得較好的優(yōu)化效果。4說明不同的用戶要求的優(yōu)化程度不同，有的可能不需要優(yōu)化。解決辦法是產生幾個編譯的版本：COM1：不優(yōu)化；COM2：低級優(yōu)化；COM3：高級優(yōu)化；5優(yōu)化分類與計算機無關的優(yōu)化在源程序或中間語言一級上進行（講）注重于程序的結構，對程序流程進行有效性、等價性處理。與計算機有關的優(yōu)化依賴具體計算機的硬件環(huán)境，在生成目標代碼時進行優(yōu)化。6全局優(yōu)化與局部優(yōu)化從優(yōu)化與源程序的關系出發(fā)，又可將優(yōu)化分為：全局優(yōu)化：以整個程序作為對象進行全面分析（如數(shù)據(jù)流分析）局部優(yōu)化：(基本塊內，循環(huán))在特定范圍內利用該范圍的特點進行優(yōu)化（講）7優(yōu)化方法——合并已知量例：A:=5*4+B;C:=2*3.14*R;5*42*3.14常數(shù)運算，不用運行即可知道結果，因此，可在編譯時計算出結果。優(yōu)化后：A:=20+B;C:=6.28*R8優(yōu)化方法——刪除多余運算刪除多余運算：即找出公共子表達式A:=B*C*D+E;C:=B*C*D-E;T:=B*C*D;A:=T+E;C:=T-E;B:=B*C+E;A:=B*C-E;不能優(yōu)化，∵B的值變了。910優(yōu)化方法——代碼外提將循環(huán)不變運算提到循環(huán)外。

FORI:=1TO1000DOA[I]:=B*C;循環(huán)不變運算11優(yōu)化方法——強度消弱一般只用于循環(huán)中。

FORI:=1TO1000DOA[I]:=I*25;255075…A[1]A[2]A[3]優(yōu)化方法——刪除無用賦值無用賦值：

X:=B+C;A:=B-C;

A:=B*C;X:=B+C;A:=B-C;…

A:=B*C;

…若此句之后沒有用到A的值，則此句為多余賦值;若此句之后也沒有用到B、C的值，則對B、C的賦值也是無用的（∵B、C的賦值只是為A而用的）無用賦值的種類很多，要從整個程序來判斷。129.2基本塊內的優(yōu)化基本塊：指程序中一組順序執(zhí)行的語句序列，其中只有一個入口和一個出口，它們分別為第一個和最后一個運行的語句。對一個基本塊來說，執(zhí)行時只能從其入口進入，從其出口退出。1314劃分基本塊的方法(1)求出中間代碼中各個基本塊的入口語句。①

程序的第一個中間代碼；②

能由轉移代碼轉移到的中間代碼；③

緊跟在條件轉移代碼后面的中間代碼。(2)對每一入口中間代碼，構造其基本塊。由每一個入口中間代碼到下一入口中間代碼（不包括該入口中間代碼）；由每一個入口中間代碼到一轉移中間代碼（包括該轉移中間代碼）；由每一個入口中間代碼到"停"中間代碼(包括該"停"中間代碼)之間的語句序列組成。⑶

凡未被納入基本塊中的中間代碼，都是程序中控制流程無法到達，也是不會被執(zhí)行到的，把它們從程序中刪除。15示例ifAandBthenZ:=X+YelseZ:=X-Y;U:=P+Q*Z;V:=P-Q*Z;(1)T1:=AandB(2)IfT1=0goto6(3)T2:=X+Y(4)Z:=T2(5)goto8(6)T3:=X-Y(7)Z:=T2(8)T4:=Q*Z(9)T5:=P+T4(10)U:=T5(12)T6:=Q*Z(13)T7:=P-T4(14)V:=T7T1:=AandBT3:=X-YT2:=X+YT4:=Q*Z三地址碼基本塊基本塊內的優(yōu)化方法在一個基本塊內通常有三種優(yōu)化方法:合并已知量刪除無用賦值（較困難）刪除多余運算161.合并已知量如果源程序中某些運算的運算對象的值在編譯時是已知的，則在編譯時，就可以執(zhí)行這些運算，從而不必在運行時再執(zhí)行它們。如：A:=2*3.14+B

A:=6.28+B

I:=3+5I:=817示例I:=2+5;J:=I+3;K:=2*I+J;I:=J+K+M;I:=7;J:=10;K:=24;I:=34+M;實現(xiàn)方法：用一些T表使變量和已知值配對。Name(名字)Cons(常量)18合并已知量優(yōu)化步驟若運算對象為T表中的量，則用相應的cons值代替它；若為形如Ti:=O1opO2的代碼(op僅指+、-、*、/)，且兩個運算對象均為常數(shù)，則合并常數(shù)，將所得結果與Ti一起填入T表,并刪除此代碼。若為形如A:=B的代碼：若B為常數(shù)，則將A與此常數(shù)填入T表；若T表中已有A，則更新A的值。若B不為常數(shù)，但A在T表中，則將A從T表中刪除19I:=2+5;J:=I+3;K:=2*I+J;I:=J+K+M;(1)T1:=2+5(2)I:=T1(3)T2:=I+3(4)J:=T2(5)T3:=2*I(6)T4:=T3+J(7)K:=T4(8)T5:=J+K(9)T6:=T5+M(10)I:=T6(1)I:=7;(2)J:=10;(3)K:=24(4)T6:=34+M(5)I:=T6優(yōu)化前優(yōu)化后T表NameconsT17I

7T210J10T314T424K24T534202.刪除多余運算多余運算：在此計算之前已存在一個與它完全相同的運算，且該運算所依賴的全部變量中沒有一個在這兩次運算之間被別的運算所改變。A:=X*(Y-Z)B:=X/(Y-Z)T:=Y-Z;A:=X*T;B:=X/T;2122D:=D+C*B;A:=D+C*B;C:=D+C*B;(1)T1:=C*B;(2)T2:=D+T1;(3)D:=T2;(4)T3:=C*B;(5)T4:=D+T3;(6)A:=T4;(7)T5:=C*B(8)T6:=D+T5(9)C:=T6(1)T1:=C*B;(2)T2:=D+T1;(3)D:=T2;(4)T4:=D+T1;(5)A:=T4;(6)T6:=D+T1(7)C:=