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

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