計(jì)算機(jī)相關(guān)編譯原理代碼優(yōu)化

1、Chapter 代碼優(yōu)化8A Survey of Code Optimizations Techniques 代碼優(yōu)化技術(shù)考察 A Survey of Code Optimizations Techniques 代碼優(yōu)化技術(shù)考察 Principal Sources of Code Optimizations 1) Register AllocationGood use of registers is the most important feature of efficient code.2) Unnecessary OperationsThe second major source of c

2、ode improvement is to avoid generating code for operations that are redundant or unnecessary.3) Costly Operations減輕強(qiáng)度常數(shù)合并常量傳播過(guò)程調(diào)用（過(guò)程內(nèi)嵌、識(shí)別尾部遞歸）4) Prediction Program Behaviora = 10 * 5 + 6 - b;_tmp0 = 10 ;_tmp1 = 5 ;_tmp2 = _tmp0 * _tmp1 ;_tmp3 = 6 ;_tmp4 = _tmp2 + _tmp3 ; _tmp5 = _tmp4 b;a = _tmp5 ;_

3、tmp0 = 56 ;_tmp1 = _tmp0 b ;a = _tmp1 ; 優(yōu)化技術(shù)簡(jiǎn)介(a)常數(shù)合并優(yōu)化技術(shù)簡(jiǎn)介(b)常數(shù)傳播_tmp4 = 0 ;f0 = _tmp4;_tmp5 = 1 ;f1 = _tmp5;_tmp6 = 2 ;i = _tmp6 ;f0 = 0 ;f1 = 1 ;i = 2 ;x+0 = x0+x = xx*1 = x1*x = x0/x = 0 x-0 = xb & true = bb & false = falseb | true = trueb | false = b優(yōu)化技術(shù)簡(jiǎn)介(c)代數(shù)簡(jiǎn)化優(yōu)化技術(shù)簡(jiǎn)介代數(shù)簡(jiǎn)化_tmp0 = 5 ;_tmp1 = _tm

4、p0 + a ;_tmp2 = _tmp1 + 10 ;b = _tmp2 ; _tmp0 = 15 ; _tmp1 = a + _tmp0 ; b = _tmp1 ;例：b = 5 + a + 10 ; 優(yōu)化技術(shù)簡(jiǎn)介(d)降低運(yùn)算強(qiáng)度a) i*2 = 2*i = i+i = i= C goto L2(6) B:=B+1(7) goto L1(8) L2: write (A)(9) halt基本塊內(nèi)實(shí)行的優(yōu)化：合 并 已 知 量刪除多余運(yùn)算刪除無(wú)用賦值解：劃分成四個(gè)基本塊B1，B2，B3，B4(1)(2)(3)(4)(5)(6)(7)(8)(9)B1B2B3B4 基本塊的DAG表示及其應(yīng)用有向

5、無(wú)環(huán)圖(DAG-Directed Acyclic Graph)基本塊的DAG是在結(jié)點(diǎn)上帶有標(biāo)記的DAG 葉結(jié)點(diǎn)：獨(dú)特的標(biāo)識(shí)符(名字,常數(shù))標(biāo)記 內(nèi)部結(jié)點(diǎn)：運(yùn)算符號(hào)標(biāo)記 各個(gè)結(jié)點(diǎn)：附加標(biāo)識(shí)符標(biāo)記四元式DAG結(jié)點(diǎn)n1 AB n10型：A:=B(:=, B,A) Aopn1 n2B Cn2n1n32型: A:=B op C(op, B, C,A) 用DAG進(jìn)行基本塊的優(yōu)化A op Bn1n21型: A:=op B(op, B, ,A)首先，DAG為空。對(duì)基本塊的每一四元式，依次執(zhí)行：1如果NODE（B）無(wú)定義，則構(gòu)造一標(biāo)記為B的葉結(jié)點(diǎn)并定義NODE（B）為這個(gè)結(jié)點(diǎn)；如果當(dāng)前四元式是0型，則記NODE

6、(B)的值為n，轉(zhuǎn)4。如果當(dāng)前四元式是1型，則轉(zhuǎn)2(1）。如果當(dāng)前四元式是2型，則： (I) 如果NODE(1)無(wú)定義，則構(gòu)造一標(biāo)記為C的葉結(jié)點(diǎn)并定義NODE(1) 為這個(gè)結(jié)點(diǎn)； (II) 轉(zhuǎn)2 (2) 僅含0，1，2型四元式的基本塊的DAG構(gòu)造算法:2（1）如果NODE(B)是標(biāo)記為常數(shù)的葉結(jié)點(diǎn) ，則轉(zhuǎn)2(3)，否則轉(zhuǎn)3（1）。（2）如果NODE(B)和NODE(C)都是標(biāo)記為常數(shù)的葉結(jié)點(diǎn)，則轉(zhuǎn)2（4），否則轉(zhuǎn)3（2）。（3）執(zhí)行op B（即合并已知量），令得到的新常數(shù)為P。如果NODE(B)是處理當(dāng)前四元式時(shí)新構(gòu)造出來(lái)的結(jié)點(diǎn)，則刪除它。如果NODE(P)無(wú)定義，則構(gòu)造一用P做標(biāo)記的葉結(jié)點(diǎn)n

7、。置NODE(P)=n，轉(zhuǎn)4。（4）執(zhí)行B op C（即合并已知量），令得到的新常數(shù)為P。如果NODE(B)或NODE(C)是處理當(dāng)前四元式時(shí)新構(gòu)造出來(lái)的結(jié)點(diǎn)，則刪除它。如果NODE(P)無(wú)定義，則構(gòu)造一用P做標(biāo)記的葉結(jié)點(diǎn)n。置NODE(P)=n，轉(zhuǎn)4。3（1）檢查DAG中是否已有一結(jié)點(diǎn)，其唯一后繼為NODE(B)，且標(biāo)記為op（即找公共子表達(dá)式）。如果沒(méi)有，則構(gòu)造該結(jié)點(diǎn)n，否則就把已有的結(jié)點(diǎn)作為它的結(jié)點(diǎn)并設(shè)該結(jié)點(diǎn)為n，轉(zhuǎn)4。（2）檢查中DAG中是否已有一結(jié)點(diǎn)，其左后繼為NODE(B)，其右后繼為NODE(C)，且標(biāo)記為op（即找公共子表達(dá)式）。如果沒(méi)有，則構(gòu)造該結(jié)點(diǎn)n，否則就把已有的結(jié)點(diǎn)作為

8、它的結(jié)點(diǎn)并設(shè)該結(jié)點(diǎn)為n，轉(zhuǎn)4。4.如果NODE(A)無(wú)定義，則把A附加在結(jié)點(diǎn)n上并令NODE(A)=n；否則先把A從NODE(A)結(jié)點(diǎn)上附加標(biāo)識(shí)符集中刪除（注意，如果NODE(A)是葉結(jié)點(diǎn)，則其標(biāo)記A不刪除），把A附加到新結(jié)點(diǎn)n上并令NODE(A)=n。轉(zhuǎn)處理下一四元式。而后，我們可由DAG重新生成原基本塊的一個(gè)優(yōu)化的代碼序列。例：用DAG進(jìn)行基本塊的優(yōu)化(1) T0:=3.14(2) T1:=2*T0(3) T2:=R+r(4) A:=T1*T2(5) B:=A(6) T3:=2*T0(7) T4:=R+r(8) T5:=T3*T4(9) T6:=R-r(10) B:=T5*T6例：(1)

9、T0:=3.14(2) T1:=2*T0(3) T2:=R+r(4) A:=T1*T2(5) B:=A(6) T3:=2*T0(7) T4:=R+r(8) T5:=T3*T4(9) T6:=R-r(10) B:=T5*T6 To 3.14 (a) n1 T0 T1 3.14 6.28 (b)n2n1例：(1) T0:=3.14(2) T1:=2*T0(3) T2:=R+r(4) A:=T1*T2(5) B:=A(6) T3:=2*T0(7) T4:=R+r(8) T5:=T3*T4(9) T6:=R-r(10) B:=T5*T6 T2 + T0 T1 3.14 6.28 R r (c)n2n5

10、n3n1n4例：(1) T0:=3.14(2) T1:=2*T0(3) T2:=R+r(4) A:=T1*T2(5) B:=A(6) T3:=2*T0(7) T4:=R+r(8) T5:=T3*T4(9) T6:=R-r(10) B:=T5*T6 A * T2 + T0 T1 3.14 6.28 R r (d)n2n5n3n1n4n6例：(1) T0:=3.14(2) T1:=2*T0(3) T2:=R+r(4) A:=T1*T2(5) B:=A(6) T3:=2*T0(7) T4:=R+r(8) T5:=T3*T4(9) T6:=R-r(10) B:=T5*T6 A,B * T2 + T0

11、T1 3.14 6.28 R r (e)n2n5n3n1n4n6例：(1) T0:=3.14(2) T1:=2*T0(3) T2:=R+r(4) A:=T1*T2(5) B:=A(6) T3:=2*T0(7) T4:=R+r(8) T5:=T3*T4(9) T6:=R-r(10) B:=T5*T6 A,B * T2 + T0 T1,T3 3.14 6.28 R r (f)n2n5n3n1n4n6例：(1) T0:=3.14(2) T1:=2*T0(3) T2:=R+r(4) A:=T1*T2(5) B:=A(6) T3:=2*T0(7) T4:=R+r(8) T5:=T3*T4(9) T6:=

12、R-r(10) B:=T5*T6 A,B * T2,T4 + T0 T1,T3 3.14 6.28 R r (g)n2n5n3n1n4n6例：(1) T0:=3.14(2) T1:=2*T0(3) T2:=R+r(4) A:=T1*T2(5) B:=A(6) T3:=2*T0(7) T4:=R+r(8) T5:=T3*T4(9) T6:=R-r(10) B:=T5*T6 A,B,T5 * T2,T4 + T0 T1,T3 3.14 6.28 R r (h)n2n5n3n1n4n6例：(1) T0:=3.14(2) T1:=2*T0(3) T2:=R+r(4) A:=T1*T2(5) B:=A(

13、6) T3:=2*T0(7) T4:=R+r(8) T5:=T3*T4(9) T6:=R-r(10) B:=T5*T6 A,B,T5 * T2,T4 T6 + - T0 T1,T3 3.14 6.28 R rn2n5n3n7n1n4n6例：(1) T0:=3.14(2) T1:=2*T0(3) T2:=R+r(4) A:=T1*T2(5) B:=A(6) T3:=2*T0(7) T4:=R+r(8) T5:=T3*T4(9) T6:=R-r(10) B:=T5*T6 B * A,T5 * T2,T4 T6 + - T0 T1,T3 3.14 6.28 R r (j)n2n5n3n7n1n4n6n8例：(1) T0:=3.14(2) T1:=2*T0(3) T2:=R+r(4) A:=T1*T2(5) B:=A(6) T3:=2*T0(7) T4:=R+r(8) T5:=T3*T4(9) T6:=R-r(10) B:=T5*T6(1) T0:=3.14(2) T1:=6.2