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

編譯原理

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

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

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

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

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

A:=B*C;

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

程序的第一個(gè)中間代碼；②

能由轉(zhuǎn)移代碼轉(zhuǎn)移到的中間代碼；③

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

凡未被納入基本塊中的中間代碼，都是程序中控制流程無法到達(dá)，也是不會(huì)被執(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三地址碼基本塊基本塊內(nèi)的優(yōu)化方法在一個(gè)基本塊內(nèi)通常有三種優(yōu)化方法:合并已知量刪除無用賦值（較困難）刪除多余運(yùn)算161.合并已知量如果源程序中某些運(yùn)算的運(yùn)算對(duì)象的值在編譯時(shí)是已知的，則在編譯時(shí)，就可以執(zhí)行這些運(yùn)算，從而不必在運(yùn)行時(shí)再執(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;實(shí)現(xiàn)方法：用一些T表使變量和已知值配對(duì)。Name(名字)Cons(常量)18合并已知量?jī)?yōu)化步驟若運(yùn)算對(duì)象為T表中的量，則用相應(yīng)的cons值代替它；若為形如Ti:=O1opO2的代碼(op僅指+、-、*、/)，且兩個(gè)運(yùn)算對(duì)象均為常數(shù)，則合并常數(shù)，將所得結(jié)果與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.刪除多余運(yùn)算多余運(yùn)算：在此計(jì)算之前已存在一個(gè)與它完全相同的運(yùn)算，且該運(yùn)算所依賴的全部變量中沒有一個(gè)在這兩次運(yùn)算之間被別的運(yùn)算所改變。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:=