計算機相關(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減輕強度常數(shù)合并常量傳播過程調(diào)用（過程內(nèi)嵌、識別尾部遞歸）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ù)簡介(a)常數(shù)合并優(yōu)化技術(shù)簡介(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ù)簡介(c)代數(shù)簡化優(yōu)化技術(shù)簡介代數(shù)簡化_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ù)簡介(d)降低運算強度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)實行的優(yōu)化：合 并 已 知 量刪除多余運算刪除無用賦值解：劃分成四個基本塊B1，B2，B3，B4(1)(2)(3)(4)(5)(6)(7)(8)(9)B1B2B3B4 基本塊的DAG表示及其應(yīng)用有向

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

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

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

8、它的結(jié)點并設(shè)該結(jié)點為n，轉(zhuǎn)4。4.如果NODE(A)無定義，則把A附加在結(jié)點n上并令NODE(A)=n；否則先把A從NODE(A)結(jié)點上附加標識符集中刪除（注意，如果NODE(A)是葉結(jié)點，則其標記A不刪除），把A附加到新結(jié)點n上并令NODE(A)=n。轉(zhuǎn)處理下一四元式。而后，我們可由DAG重新生成原基本塊的一個優(yōu)化的代碼序列。例：用DAG進行基本塊的優(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