代碼優(yōu)化課件

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

代碼改進(jìn)變換的原則（1）等價(jià)原則。經(jīng)過優(yōu)化后不應(yīng)改變程序運(yùn)行的結(jié)果。（2）有效原則。使優(yōu)化后所產(chǎn)生的目標(biāo)代碼運(yùn)行時(shí)間較短，占用的存儲空間較小。（3）合算原則。應(yīng)盡可能以較低的代價(jià)取得較好的優(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)公共子表達(dá)式刪除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ù)寫傳播形成為f:=g的賦值叫做復(fù)寫優(yōu)化過程中會大量引入復(fù)寫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ù)寫傳播復(fù)寫傳播是在復(fù)寫語句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)刪除無用代碼無用代碼是指計(jì)算的結(jié)果決不被引用的語句一些優(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)化的其它重要技術(shù)歸納變量刪除強(qiáng)度削弱例：while(i

<=limit

2)…

變換成 t=limit

2; while(i<=t)…10.1

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

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

B3B310.2局部優(yōu)化怎樣為三地址語句序列生成目標(biāo)代碼？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ù)的語句序列，控制流從它的開始進(jìn)入，并從它的末尾離開再用有向邊表示基本塊之間的控制流信息，就能得到程序的流圖10.2局部優(yōu)化三地址語句序列的劃分基本塊首先確定所有的入口語句序列的第一個(gè)語句是入口語句能由條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句轉(zhuǎn)到的語句是入口語句緊跟在條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句后面的語句是入口語句每個(gè)入口語句到下一個(gè)入口語句之前的語句序列構(gòu)成一個(gè)基本塊

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定值一個(gè)名字的值在基本塊的某一點(diǎn)以后還要引用的話，我們說這個(gè)名字在該點(diǎn)是活躍的10.2局部優(yōu)化合并已知量 a:=2......(中間沒有改變a的值) b:=a*4 //可以變換為b:=8臨時(shí)變量改名10.2局部優(yōu)化交換相鄰的獨(dú)立語句 t1:=b

+c t2:=x

+y t2:=x

+y t1:=b

+c當(dāng)且僅當(dāng)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）圖的葉結(jié)點(diǎn)以標(biāo)識符或常數(shù)作為標(biāo)記 2）圖的內(nèi)部結(jié)點(diǎn)以一運(yùn)算符作為標(biāo)記，表示該結(jié)點(diǎn)是應(yīng)用該運(yùn)算符對其后繼結(jié)點(diǎn)所代表的值進(jìn)行運(yùn)算的結(jié)果3）各結(jié)點(diǎn)可能附加一個(gè)或多個(gè)標(biāo)識符，表示這些變量具有該結(jié)點(diǎn)所代表的值算法演示10.3循環(huán)優(yōu)化循環(huán)是程序中那些可能反復(fù)執(zhí)行的代碼序列。對循環(huán)中的代碼，可以實(shí)行代碼外提、強(qiáng)度削弱和刪除歸納變量等優(yōu)化10．3．l代碼外提10．3．2強(qiáng)度削弱

10．3．3刪除歸納變量代碼外提將循環(huán)不變語句提到循環(huán)的前置結(jié)點(diǎn)中并不是所有的循環(huán)不變語句都可以外提我們討論三個(gè)條件（并非是必要條件）10.3循環(huán)優(yōu)化語句s:x:=y+z可以外提的條件含s的塊是循環(huán)所有出口結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)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的其它定值都不能到達(dá)循環(huán)中x的引用考查B4的循環(huán)不變運(yùn)算i:=2s是出口必經(jīng)的循環(huán)中唯一的i定值點(diǎn)x=0y=2B2B3B4B2B4B5i:=1ifx<ygoto

B3i:=2y:=y

1ify<=0goto

B5a:=i+1x:=x+1j:=aB5B4B3B2B110.3循環(huán)優(yōu)化強(qiáng)度削弱：執(zhí)行時(shí)間較長的運(yùn)算替換為執(zhí)行時(shí)間較短的運(yùn)算13)i:=i+14)8)計(jì)算的t2,t6是i的線性函數(shù)強(qiáng)度削弱的結(jié)果10.1610.16中對t3,t7進(jìn)行強(qiáng)度削弱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)中，其值的每次改變都增加或減少某個(gè)固定的常量基本歸納變量：在循環(huán)中只有一個(gè)形如i:=i

c的i，其中c是常量其