代碼優(yōu)化課件

優(yōu)化編譯器的組織前端代碼生成器代碼優(yōu)化器變換數(shù)據(jù)流分析控制流分析10.1.1

代碼改進變換的原則（1）等價原則。經(jīng)過優(yōu)化后不應改變程序運行的結果。（2）有效原則。使優(yōu)化后所產(chǎn)生的目標代碼運行時間較短，占用的存儲空間較小。（3）合算原則。應盡可能以較低的代價取得較好的優(yōu)化效果。10.1

優(yōu)化的概述10.1.2

優(yōu)化的主要種類本節(jié)所用的例子i=m

1;j=n;v=a[n]; (1)i:=m

1while(1){ (2)j:=ndoi=i+1;while(a[i]<v); (3)t1:=4*ndoj=j

1;while(a[j]>v); (4)v:=a[t1]if(i>=j)break; (5)i:=i+1x=a[i];a[i]=a[j];a[j]=x; (6)t2:=4*i} (7)t3:=a[t2]x=a[i];a[i]=a[n];a[n]=x; (8)ift3<vgoto(5)

10.1

優(yōu)化的概述本節(jié)所用的例子i=m

1;j=n;v=a[n]; (9)j:=j

1while(1){ (10)t4:=4*jdoi=i+1;while(a[i]<v); (11)t5:=a[t4] doj=j

1;while(a[j]>v); (12)ift5>vgoto(9)if(i>=j)break; (13)ifi>=jgoto(23)x=a[i];a[i]=a[j];a[j]=x; (14)t6:=4*i} (15)x:=a[t6]x=a[i];a[i]=a[n];a[n]=x; ...

i:=m

1j:=nt1:=4*nv:=a[t1]i:=i+1t2:=4*it3:=a[t2]ift3

<vgoto

B2B1B2j:=j

1t4:=4*jt5:=a[t4]ift5>vgoto

B3ifi>=jgoto

B6B4B3B5B610.1

優(yōu)化的概述(1)公共子表達式刪除B5x=a[i];a[i]=a[j];a[j]=x;t6:=4*ix:=a[t6]t7:=4*it8:=4*jt9:=a[t8]a[t7]:=t9t10:=4*ja[t10]:=xgoto

B210.1

優(yōu)化的概述B5x=a[i];a[i]=a[j];a[j]=x;t6:=4*ix:=a[t6]t7:=4*i

t8:=4*jt9:=a[t8]a[t7]:=t9t10:=4*ja[t10]:=xgoto

B210.1

優(yōu)化的概述B5x=a[i];a[i]=a[j];a[j]=x;t6:=4*ix:=a[t6]t7:=4*i

t8:=4*jt9:=a[t8]a[t7]:=t9t10:=4*ja[t10]:=xgoto

B2t6:=4*ix:=a[t6]t7:=t6

t8:=4*jt9:=a[t8]a[t7]:=t9t10:=t8a[t8]:=xgoto

B210.1

優(yōu)化的概述(2)復寫傳播形成為f:=g的賦值叫做復寫優(yōu)化過程中會大量引入復寫t6:=4*ix:=a[t6]t7:=4*i

t8:=4*jt9:=a[t8]a[t7]:=t9t10:=4*ja[t10]:=xgoto

B2t6:=4*ix:=a[t6]t7:=t6

t8:=4*jt9:=a[t8]a[t7]:=t9t10:=t8a[t10]:=xgoto

B210.1

優(yōu)化的概述(2)復寫傳播復寫傳播是在復寫語句f:=g后，盡可能用g代表f，目的是使某些變量的賦值變?yōu)闊o用t6:=4*ix:=a[t6]t7:=4*i

t8:=4*jt9:=a[t8]a[t7]:=t9t10:=4*ja[t10]:=xgoto

B2t6:=4*ix:=a[t6]t7:=t6

t8:=4*jt9:=a[t8]a[t7]:=t9t10:=t8a[t10]:=a[t6]goto

B2t6:=4*ix:=a[t6]t7:=t6

t8:=4*jt9:=a[t8]a[t6]:=t9t10:=t8a[t8]:=a[t6]goto

B210.1

優(yōu)化的概述(3)刪除無用代碼無用代碼是指計算的結果決不被引用的語句一些優(yōu)化變換可能會引起無用代碼x:=t3a[t2]:=t5a[t4]:=t3goto

B2a[t2]:=t5a[t4]:=t3goto

B2x:=t3a[t2]:=t5a[t4]:=xgoto

B210.1

優(yōu)化的概述(4)代碼外提代碼外提是循環(huán)優(yōu)化的一種循環(huán)優(yōu)化的其它重要技術歸納變量刪除強度削弱例：while(i

<=limit

2)…

變換成 t=limit

2; while(i<=t)…10.1

優(yōu)化的概述(5)強度削弱和歸納變量刪除j和t4的值步伐一致地變化這樣的變量叫做歸納變量在循環(huán)中有多個歸納變量時，也許只需要留下一個這個操作由歸納變量刪除過程來完成對本例可以先做強度削弱它給刪除歸納變量創(chuàng)造機會j:=j

1t4:=4*jt5:=a[t4]ift5>vgoto

B3B310.2局部優(yōu)化怎樣為三地址語句序列生成目標代碼？begin |(1) prod:=0 prod:=0; |(2) i:=1 i:=1; |(3) t1:=4*i dobegin |(4) t2:=a[t1] prod:=prod+a[i]*b[i];|(5) t3:=4*i i:=i+1 |(6) t4:=b[t3] endwhilei<=20 |(7) t5:=t2*t4

end |(8) t6:=prod+t5 |(9) prod:=t6 |(10) t7:=i+1 |(11) i:=t7

|(12) ifi<=20goto(3)10.2局部優(yōu)化10.2.1基本塊基本塊：連續(xù)的語句序列，控制流從它的開始進入，并從它的末尾離開再用有向邊表示基本塊之間的控制流信息，就能得到程序的流圖10.2局部優(yōu)化三地址語句序列的劃分基本塊首先確定所有的入口語句序列的第一個語句是入口語句能由條件轉移語句或無條件轉移語句轉到的語句是入口語句緊跟在條件轉移語句或無條件轉移語句后面的語句是入口語句每個入口語句到下一個入口語句之前的語句序列構成一個基本塊

10.2局部優(yōu)化(1) prod:=0(2) i:=1(3) t1:=4*i(4) t2:=a[t1](5) t3:=4*i(6) t4:=b[t3](7) t5:=t2*t4

(8) t6:=prod+t5(9) prod:=t6(10) t7:=i+1(11) i:=t7(12) ifi<=20goto(3)(1)prod:=0(2)i:=1(3)t1:=4*i(4)t2:=a[t1](5)t3:=4*I(6)t4:=b[t3](7)t5:=t2*t4(8)t6:=prod+t5(9)prod:=t6(10)t7:=i+1(11)i:=t7(12)ifi<=20goto(3)B1B210.2局部優(yōu)化基本塊的變換三地址語句x:=y+z引用y和z并對x定值一個名字的值在基本塊的某一點以后還要引用的話，我們說這個名字在該點是活躍的10.2局部優(yōu)化合并已知量 a:=2......(中間沒有改變a的值) b:=a*4 //可以變換為b:=8臨時變量改名10.2局部優(yōu)化交換相鄰的獨立語句 t1:=b

+c t2:=x

+y t2:=x

+y t1:=b

+c當且僅當x和y都不是t1，b和c都不是t2

代數(shù)變換 x:=x+0 可以刪除

x:=x*1 可以刪除

x:=y**2 改成x:=y*y有沒有基本塊優(yōu)化的形式化方法？10.2局部優(yōu)化10.2.2基本塊的DAG表示1）圖的葉結點以標識符或常數(shù)作為標記 2）圖的內(nèi)部結點以一運算符作為標記，表示該結點是應用該運算符對其后繼結點所代表的值進行運算的結果3）各結點可能附加一個或多個標識符，表示這些變量具有該結點所代表的值算法演示10.3循環(huán)優(yōu)化循環(huán)是程序中那些可能反復執(zhí)行的代碼序列。對循環(huán)中的代碼，可以實行代碼外提、強度削弱和刪除歸納變量等優(yōu)化10．3．l代碼外提10．3．2強度削弱

10．3．3刪除歸納變量代碼外提將循環(huán)不變語句提到循環(huán)的前置結點中并不是所有的循環(huán)不變語句都可以外提我們討論三個條件（并非是必要條件）10.3循環(huán)優(yōu)化語句s:x:=y+z可以外提的條件含s的塊是循環(huán)所有出口結點的必經(jīng)結點i:=1ifu<vgoto

B3v:=v

1ifu<=20goto

B5i:=2u:=u+1j:=iB5B4B3B2B110.3循環(huán)優(yōu)化10.3循環(huán)優(yōu)化語句s:x:=y+z可以外提的條件循環(huán)中沒有其它語句對x定值考查B2-B3-B4-B2-B4-B5i：=3外提，j=2不外提，i=3i:=1i:=3ifu<vgoto

B3v:=v

1ifu<=20goto

B5i:=2u:=u+1j:=iB5B4B3B2B110.3循環(huán)優(yōu)化語句s:x:=y+z可以外提的條件x的其它定值都不能到達循環(huán)中x的引用考查B4的循環(huán)不變運算i:=2s是出口必經(jīng)的循環(huán)中唯一的i定值點x=0y=2B2B3B4B2B4B5i:=1ifx<ygoto

B3i:=2y:=y

1ify<=0goto

B5a:=i+1x:=x+1j:=aB5B4B3B2B110.3循環(huán)優(yōu)化強度削弱：執(zhí)行時間較長的運算替換為執(zhí)行時間較短的運算13)i:=i+14)8)計算的t2,t6是i的線性函數(shù)強度削弱的結果10.1610.16中對t3,t7進行強度削弱1)i:=1B1B2’3)t1:=2*j6)t4:=addr(A)-117)t5:=2*j10)t8:=addr(A)-114)t2:=10*i5)t3:=t2+t18)t6:=10*i9)t7:=t6+t511)t9:=t8[t7]12)t4[t3]:=t9+113)i:=i+114)gotoB2B32)ifi>10goto15B215)......10.3循環(huán)優(yōu)化歸納變量刪除循環(huán)歸納變量:在循環(huán)中，其值的每次改變都增加或減少某個固定的常量基本歸納變量：在循環(huán)中只有一個形如i:=i

c的i，其中c是常量其