大三-編譯原理第11章代碼優(yōu)化

第第11章wuchxcourse@sinacom第11章代碼優(yōu)化學(xué)習(xí)學(xué)習(xí)目掌中間代碼優(yōu)化的基本思了11.1概目提高目標(biāo)程序的效率11.111.1概2．注意事項(xiàng)：⑴等價(jià)原則——不應(yīng)改變程序⑵有效原則——優(yōu)化后的目標(biāo)代碼效率確實(shí)提高⑶合算原則——以較低的代價(jià)取得較好的優(yōu)化效果11.1概3．優(yōu)化的消除公共子表達(dá)式利用(基本塊優(yōu)化)刪除無用賦循環(huán)不變式循環(huán)優(yōu)化強(qiáng)度削T7:=T6T7:=T6T10:=T8gotoT7:=T6T10:=T8gotogoto11.2基本塊優(yōu)化11.2基本塊優(yōu)化中只有一個(gè)和一個(gè)出口，就是第一個(gè)語句，出口就其進(jìn)入，從其出口退出。11.2基本塊優(yōu)化① 語程序的第一個(gè)語句能由條件轉(zhuǎn)語句/無條件轉(zhuǎn)語句轉(zhuǎn)移到的語句緊跟在條件轉(zhuǎn)移語句后面②對(duì)每 語句，構(gòu)造其所屬的基本由 語句到另 語句(不含該語句)到一轉(zhuǎn)移語句(包括到一停語句(包括①①read②read③R:=Xmod④ifR=0goto⑤⑥⑦goto⑧wrtie⑨①read②read③R:=X④ifR=0goto⑤⑥⑦goto⑧wrtie⑨程序的流11.2基本塊優(yōu)3 11.2基11.2基本塊優(yōu)3 T7:= T10:= goto goto刪除公共子表達(dá)T7:=T6T10:=T8goto復(fù)goto刪除無用代11.2基本塊優(yōu)基本塊的DAG(DirectedAcyclicGraph)表示葉結(jié)點(diǎn)用標(biāo)識(shí)符(變量名)或常數(shù)作為其惟一的標(biāo)記，當(dāng)葉結(jié)點(diǎn)是標(biāo)識(shí)符時(shí)，代表名字的初值，給它加下標(biāo)0；結(jié)點(diǎn)個(gè)結(jié)點(diǎn)上的若干個(gè)標(biāo)識(shí)符有相同的值。11.2基本塊優(yōu)化411.2基本塊優(yōu)化4．基本塊的DAG(DirectedAcyclicGraph)表示本算法只對(duì)如下三種四元式構(gòu)造0型1型opA2型opAB引進(jìn)函數(shù)noeA)，它將返回與標(biāo)識(shí)符A相應(yīng)的最近建立的結(jié)點(diǎn)。o是雙目運(yùn)算符，還可以是或。步驟1初始DAG步驟2依次對(duì)基本塊中的每一個(gè)四元式“opABC”，步驟3如果noeA)沒有定義，則建立葉結(jié)點(diǎn)，標(biāo)記為A，讓noe(A)等于這個(gè)結(jié)點(diǎn)。如果對(duì)于2型四元式noeB)沒有定義，則建立葉結(jié)點(diǎn)，這時(shí)標(biāo)記為B，且讓noe(B)等于該新建結(jié)點(diǎn)，如果noeA)和noeB)都是已知常量，則執(zhí)行Aop合并常量)，得到新常量P，為P建立一個(gè)葉結(jié)點(diǎn)，標(biāo)記為P，如果nodeA)或noe(B)是處理當(dāng)前四元式時(shí)建立的新結(jié)點(diǎn)，則刪除它?；净緣K的DAG圖的構(gòu)造算步驟4對(duì)三種四元式分別處理如下①對(duì)于0型，讓n是node(A)②對(duì)于1型，查看是否存在標(biāo)記為o的結(jié)點(diǎn)，且它有惟一的子結(jié)點(diǎn)noe(A)。如果不存在，則建立這樣的結(jié)點(diǎn)。讓n是找到或建立的結(jié)點(diǎn)。③對(duì)于2型，查看是否存在標(biāo)記為o的結(jié)點(diǎn)，且其左右子結(jié)點(diǎn)分別是nodeA)與noeB)。如果不存在，則建立這樣的結(jié)點(diǎn)。讓是找到或建立的結(jié)點(diǎn)。步驟5當(dāng)C為標(biāo)識(shí)符時(shí)，從node(C)的標(biāo)識(shí)符表刪去C，11.2基本塊優(yōu)5．利用DAG①從基本塊構(gòu)造②從DAG重寫11.2基11.2基本塊優(yōu)5．利用DAG圖進(jìn)行基本塊的優(yōu)n-11t9:=t4-n8+n10-n6t3+n2t1*n5t2* 111.2基本塊優(yōu)n7*n6R,H/nSn4-n5+3/ n0S0,S4n1 (104)(107)(10) B(103)(102)'(+,T，10,T(110)(104)(:=，TB刪除歸納變11.311.3如循環(huán)中對(duì)變量I只有惟一的形如I:=I±C的賦值，且C為循環(huán)的區(qū)域常量，則稱I為循環(huán)的基本歸納變量?；練w納變量除用于自身的遞歸定值外，往往只在循環(huán)中用來計(jì)算其它歸納變量以及用來控制循環(huán)的進(jìn)行。(103)(+，I，T1，T2)B(102)(*，10，k，T(107)(:=，T4(109)(:=，T(103)(+，I，T，T(100)(102)B3(103)B4(109)(:=，T刪除公共子表達(dá)(110)B1(100)(:=,1,_,BB(102)(*，10，k，T)B(103)(104)(j，_，_(103)(104)(:=，TB(102)‘(+,T,10,T(110)(j,_,_消減強(qiáng)(106)(+，J，T，T(110)(j，_，_B1(100)B(101)(j>,k,10,(111)優(yōu)化B(100)(101)'(j>,T(102)第11章小結(jié)第11章小結(jié)《編譯原理》(第1版《編譯原理》(第2版等， 技大等， 技大《程序設(shè)計(jì)語言