代碼優(yōu)化課件

代碼優(yōu)化9.1

優(yōu)化的主要種類9.1.1

代碼改進(jìn)變換的標(biāo)準(zhǔn)代碼變換必須保程序的含義采取安全穩(wěn)妥的策略變換減少程序的運(yùn)行時(shí)間平均達(dá)到一個(gè)可度量的值變換所作的努力是值得的9.1

優(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)

9.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; ...

9.1

優(yōu)化的主要種類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

B6B4B3B5B69.1

優(yōu)化的主要種類9.1.2公共子表達(dá)式刪除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

B29.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]t8:=4*jt9:=a[t8]a[t6]:=t9a[t8]:=xgoto

B29.1

優(yōu)化的主要種類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

B6B4B3B5B69.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]t8:=4*jt9:=a[t8]a[t6]:=t9a[t8]:=xgoto

B29.1

優(yōu)化的主要種類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

B2t6:=4*ix:=a[t6]t8:=4*jt9:=a[t8]a[t6]:=t9a[t8]:=xgoto

B2x:=a[t2]t9:=a[t4]a[t2]:=t9a[t4]:=xgoto

B29.1

優(yōu)化的主要種類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

B6B4B3B5B69.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]t8:=4*jt9:=a[t8]a[t6]:=t9a[t8]:=xgoto

B2x:=a[t2]t9:=a[t4]a[t2]:=t9a[t4]:=xgoto

B29.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]t8:=4*jt9:=a[t8]a[t6]:=t9a[t8]:=xgoto

B2x:=a[t2]t9:=a[t4]a[t2]:=t9a[t4]:=xgoto

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

B29.1

優(yōu)化的主要種類B6x=a[i];a[i]=a[n];a[n]=x;t11:=4*ix:=a[t11]t12:=4*it13:=4*nt14:=a[t13]a[t12]:=t14t15:=4*na[t15]:=xx:=t3t14:=a[t1]a[t2]:=t14a[t1]:=x9.1

優(yōu)化的主要種類B6x=a[i];a[i]=a[n];a[n]=x;a[t1]能否作為公共子表達(dá)式？t11:=4*ix:=a[t11]t12:=4*it13:=4*nt14:=a[t13]a[t12]:=t14t15:=4*na[t15]:=xx:=t3t14:=a[t1]a[t2]:=t14a[t1]:=x9.1

優(yōu)化的主要種類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

B6B4B3B5B6 把a(bǔ)[t1]作為公共子表達(dá)式是不穩(wěn)妥的

9.1

優(yōu)化的主要種類9.1.3復(fù)寫傳播形成為f:=g的賦值叫做復(fù)寫語句優(yōu)化過程中會大量引入復(fù)寫t:=d+ea:=t刪除局部公共子表達(dá)式期間引進(jìn)復(fù)寫t:=d+eb:=tc:=tc:=d+eb:=d+ea:=d+e9.1

優(yōu)化的主要種類9.1.3復(fù)寫傳播形成為f:=g的賦值叫做復(fù)寫語句優(yōu)化過程中會大量引入復(fù)寫復(fù)寫傳播變換的做法是在復(fù)寫語句f:=g后，盡可能用g代表fx:=t3a[t2]:=t5a[t4]:=t3goto

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

B29.1

優(yōu)化的主要種類9.1.3復(fù)寫傳播形成為f:=g的賦值叫做復(fù)寫語句優(yōu)化過程中會大量引入復(fù)寫復(fù)寫傳播變換的做法是在復(fù)寫語句f:=g后，盡可能用g代表f復(fù)寫傳播變換本身并不是優(yōu)化，但它給其它優(yōu)化帶來機(jī)會常量合并死代碼刪除9.1

優(yōu)化的主要種類9.1.4死代碼刪除死代碼是指計(jì)算的結(jié)果決不被引用的語句一些優(yōu)化變換可能會引起死代碼例：debug:=true; debug:=false;... 測試后改成...if(debug)print… if(debug)print…9.1

優(yōu)化的主要種類9.1.4死代碼刪除死代碼是指計(jì)算的結(jié)果決不被引用的語句一些優(yōu)化變換可能會引起死代碼例：復(fù)寫傳播可能會引起死代碼刪除x:=t3a[t2]:=t5a[t4]:=t3goto

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

B29.1

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

<=limit

2)…變換成 t=limit

2; while(i<=t)…9.1

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

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

B3B39.1

優(yōu)化的主要種類i:=m

1j:=nt1:=4*nv:=a[t1]B1B2j:=j

1t4:=t4

4t5:=a[t4]ift5>vgoto

B3B4B3B5B6t4:=4*jifi>=jgoto

B6j:=j

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

B3B3除第一次外，t4=4*j在B3的入口一定保持在j:=j

1后，關(guān)系t4=4*j+4也保持9.1

優(yōu)化的主要種類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

B6B4B3B5B6B2也可以進(jìn)行類似的變換循環(huán)控制條件可以用t2和t4來表示9.1

優(yōu)化的主要種類i:=m

1j:=nt1:=4*nv:=a[t1]t2:=4*it4:=4*jt2:=t2+4t3:=a[t2]ift3

<vgoto

B2B1B2t4:=t4

4t5:=a[t4]ift5>vgoto

B3ift2>=t4

goto

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

B2B4B3B5t14:=a[t1]a[t2]:=t14a[t1]:=t3B69.1

優(yōu)化的主要種類9.1.7優(yōu)化編譯器的組織實(shí)現(xiàn)高級結(jié)構(gòu)的操作在中間代碼中是顯式的中間代碼基本上獨(dú)立于目標(biāo)機(jī)器前端代碼生成器代碼優(yōu)化器變換數(shù)據(jù)流分析控制流分析9.2

流圖中的循環(huán)9.2.1必經(jīng)結(jié)點(diǎn)結(jié)點(diǎn)d是結(jié)點(diǎn)n的必經(jīng)結(jié)點(diǎn)，如果從初始結(jié)點(diǎn)起，每條到達(dá)n的路徑都要經(jīng)過d，寫成d

dom

n每個(gè)結(jié)點(diǎn)是它本身的必經(jīng)結(jié)點(diǎn)循環(huán)的入口是循環(huán)中所有結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)123456789109.2

流圖中的循環(huán)9.2.2

自然循環(huán)循環(huán)循環(huán)必須有唯一的入口點(diǎn)，叫做首結(jié)點(diǎn)，首結(jié)點(diǎn)是循環(huán)中所有結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)至少有一種辦法重復(fù)循環(huán)，也就是至少有一條路徑回到首結(jié)點(diǎn)回邊如果有a

domb，那么邊b

a叫做回邊尋找流圖中所有循環(huán)的一個(gè)辦法是找出流圖的回邊9.2

流圖中的循環(huán)自然循環(huán)回邊10

7循環(huán){7,8,10}回邊7

4循環(huán){4,5,6,7,8,10}回邊4

3和8

3循環(huán){3,4,5,6,7,8,10}回邊9

1{1,2,3,4,5,6,7,8,9,10}123456789109.2

流圖中的循環(huán)內(nèi)循環(huán) 若一個(gè)循環(huán)的結(jié)點(diǎn)集合是另一個(gè)循環(huán)的結(jié)點(diǎn)集合的子集。兩個(gè)循環(huán)有相同的首結(jié)點(diǎn),但并非一個(gè)結(jié)點(diǎn)集是另一個(gè)的子集，則看成一個(gè)循環(huán)。B0B1B2B3有相同首節(jié)點(diǎn)的兩個(gè)循環(huán)9.2

流圖中的循環(huán)9.2.3前置結(jié)點(diǎn)某些變換要求我們移動語句到首結(jié)點(diǎn)的前面B0循環(huán)L(a)整理前，B0是首結(jié)點(diǎn)B0B0

循環(huán)L(b)整理后，增加前置結(jié)點(diǎn)B0

9.2

流圖中的循環(huán)9.2.4可歸納流圖 一個(gè)流圖G是可歸約的，當(dāng)且僅當(dāng) 有向邊集合=正向邊子集

回邊子集，并有性質(zhì):正向邊子集形成有向無環(huán)圖，在這個(gè)圖中，每個(gè)結(jié)點(diǎn)可以從G的初始結(jié)點(diǎn)到達(dá)回邊子集僅由前面所講的回邊組成

9.2

流圖中的循環(huán)12345678910123456789109.2

流圖中的循環(huán)非歸約流圖的例子初始結(jié)點(diǎn)是12

3和3

2都不是回邊該圖不是無環(huán)的從結(jié)點(diǎn)2和3兩處進(jìn)入由它們構(gòu)成的環(huán)

3219.3

全局?jǐn)?shù)據(jù)流分析介紹編譯器需要把程序流圖作為一個(gè)整體來收集信息并把這些信息分配給流圖的各個(gè)基本塊數(shù)據(jù)流信息可以通過建立和解數(shù)據(jù)流方程來收集典型方程 out[B]=gen[B]

(in[B]

kill[B]) 9.3

全局?jǐn)?shù)據(jù)流分析介紹建立和解數(shù)據(jù)流方程依賴三個(gè)因素 out[B]=gen[B]

(in[B]

kill[B])產(chǎn)生和注銷的概念依賴于數(shù)據(jù)流方程所要解決的問題，也會出現(xiàn)反向前進(jìn)，由out[B]來定義in[B]數(shù)據(jù)流分析受程序控制結(jié)構(gòu)影響過程調(diào)用、通過指針賦值、甚至對數(shù)組變量的賦值等的存在使得數(shù)據(jù)流分析大大復(fù)雜9.3

全局?jǐn)?shù)據(jù)流分析介紹9.3.1點(diǎn)和路徑點(diǎn)基本塊中，兩個(gè)相鄰的語句之間為程序的一個(gè)點(diǎn)基本塊的開始點(diǎn)和結(jié)束點(diǎn)路徑點(diǎn)序列p1,p2,…,pn，對1和n-1間的每個(gè)i，滿足pi是先于一個(gè)語句的點(diǎn)，pi＋1是同一塊中位于該語句后的點(diǎn)，或者pi是某塊的結(jié)束點(diǎn)，pi＋1是后繼塊的開始點(diǎn)9.3

全局?jǐn)?shù)據(jù)流分析介紹9.3.2到達(dá)-定值確切定值：賦值語句或讀語句可能定值：過程調(diào)用,別名,通過指針來賦值確切引用可能引用在給出簡單的例子加以區(qū)別后，我們將不考慮過程調(diào)用、別名、通過指針來賦值等引起不確定性的情況。9.3

全局?jǐn)?shù)據(jù)流分析介紹x的定值語句d能到達(dá)點(diǎn)pd:x:=… d:x:=… d:x:=…. . .. d1:x:=… d1:*y:=… . . .p p pd到達(dá)p d不能到達(dá)p d到達(dá)p

d被注銷 d1也能到達(dá)p9.3

全局?jǐn)?shù)據(jù)流分析介紹i:=m

1和j:=n都能到達(dá)B2的開始點(diǎn)j:=j

1也能到達(dá)B2的開始點(diǎn)j:=n不能到

B4d1:i:=m

1d2:j:=nd3:a:=u1B1B2B4B3B5B6d4:i:=i+1d5:j:=j

1d6:a:=u29.3

全局?jǐn)?shù)據(jù)流分析介紹d:x:=… d:x:=… d:x:=…. . .. d1:x:=… d1:*y:=… . . .p p pd可以到達(dá)p d不能到達(dá)p d能到達(dá)p

d被注銷 d1也能到達(dá)p到達(dá)-定值是不精確的，但是穩(wěn)妥的會使我們失去某些實(shí)際是安全的變換9.3

全局?jǐn)?shù)據(jù)流分析介紹到達(dá)-定值的迭代算法gen[B]：B中能到達(dá)B的結(jié)束點(diǎn)的定值語句kill[B]：整個(gè)程序中決不會到達(dá)B結(jié)束點(diǎn)的定值in[B]：能到達(dá)B的開始點(diǎn)的定值集合out[B]：能到達(dá)B的結(jié)束點(diǎn)的定值集合兩組方程（根據(jù)gen和kill求解in和out） in[B]=

out[P]

P是B的前驅(qū) out[B]=gen

[B]

(in[B]

kill[B]) 9.3

全局?jǐn)?shù)據(jù)流分析介紹

in[B] B1

0000000B20000000B30000000

B40000000

gen[B1]={d1,d2,d3}kill[B1]={d4,d5,d6,d7}gen[B2]={d4,d5}kill[B2]={d1,d2,d7}gen[B3]={d6}kill[B3]={d3}gen[B4]={d7}kill[B4]={d1,d4}d1:i:=m

1d2:j:=nd3:a:=u1B1B2d7:i:=u3B4d4:i:=i+1d5:j:=j

1d6:a:=u2B39.3

全局?jǐn)?shù)據(jù)流分析介紹

in[B] out[B]B1

00000001110000B20000000 0001100B30000000

0000010

B40000000

0000001gen[B1]={d1,d2,d3}kill[B1]={d4,d5,d6,d7}gen[B2]={d4,d5}kill[B2]={d1,d2,d7}gen[B3]={d6}kill[B3]={d3}gen[B4]={d7}kill[B4]={d1,d4}d1:i:=m

1d2:j:=nd3:a:=u1B1B2d7:i:=u3B4d4:i:=i+1d5:j:=j

1d6:a:=u2B39.3

全局?jǐn)?shù)據(jù)流分析介紹

in[B] out[B]B1

00000001110000B211100010001100B30000000

0000010

B40000000

0000001gen[B1]={d1,d2,d3}kill[B1]={d4,d5,d6,d7}gen[B2]={d4,d5}kill[B2]={d1,d2,d7}gen[B3]={d6}kill[B3]={d3}gen[B4]={d7}kill[B4]={d1,d4}d1:i:=m

1d2:j:=nd3:a:=u1B1B2d7:i:=u3B4d4:i:=i+1d5:j:=j

1d6:a:=u2B39.3

全局?jǐn)?shù)據(jù)流分析介紹

in[B] out[B]B1

00000001110000B211100010011100B30000000

0000010

B40000000

0000001gen[B1]={d1,d2,d3}kill[B1]={d4,d5,d6,d7}gen[B2]={d4,d5}kill[B2]={d1,d2,d7}gen[B3]={d6}kill[B3]={d3}gen[B4]={d7}kill[B4]={d1,d4}d1:i:=m

1d2:j:=nd3:a:=u1B1B2d7:i:=u3B4d4:i:=i+1d5:j:=j

1d6:a:=u2B39.3

全局?jǐn)?shù)據(jù)流分析介紹

in[B] out[B]B1

00000001110000B211100010011100B300111000000010

B40000000

0000001gen[B1]={d1,d2,d3}kill[B1]={d4,d5,d6,d7}gen[B2]={d4,d5}kill[B2]={d1,d2,d7}gen[B3]={d6}kill[B3]={d3}gen[B4]={d7}kill[B4]={d1,d4}d1:i:=m

1d2:j:=nd3:a:=u1B1B2d7:i:=u3B4d4:i:=i+1d5:j:=j

1d6:a:=u2B39.3

全局?jǐn)?shù)據(jù)流分析介紹

in[B] out[B]B1

00000001110000B211100010011100B300111000001110B40000000

0000001gen[B1]={d1,d2,d3}kill[B1]={d4,d5,d6,d7}gen[B2]={d4,d5}kill[B2]={d1,d2,d7}gen[B3]={d6}kill[B3]={d3}gen[B4]={d7}kill[B4]={d1,d4}d1:i:=m

1d2:j:=nd3:a:=u1B1B2d7:i:=u3B4d4:i:=i+1d5:j:=j

1d6:a:=u2B39.3

全局?jǐn)?shù)據(jù)流分析介紹

in[B] out[B]B1

00000001110000B211100010011100B300111000001110B400111100000001gen[B1]={d1,d2,d3}kill[B1]={d4,d5,d6,d7}gen[B2]={d4,d5}kill[B2]={d1,d2,d7}gen[B3]={d6}kill[B3]={d3}gen[B4]={d7}kill[B4]={d1,d4}d1:i:=m

1d2:j:=nd3:a:=u1B1B2d7:i:=u3B4d4:i:=i+1d5:j:=j

1d6:a:=u2B39.3

全局?jǐn)?shù)據(jù)流分析介紹

in[B] out[B]B1

00000001110000B211100010011100B300111000001110B400111100010111gen[B1]={d1,d2,d3}kill[B1]={d4,d5,d6,d7}gen[B2]={d4,d5}kill[B2]={d1,d2,d7}gen[B3]={d6}kill[B3]={d3}gen[B4]={d7}kill[B4]={d1,d4}d1:i:=m

1d2:j:=nd3:a:=u1B1B2d7:i:=u3B4d4:i:=i+1d5:j:=j

1d6:a:=u2B39.3

全局?jǐn)?shù)據(jù)流分析介紹

in[B] out[B]B1

00000001110000B211101110011100B300111000001110B400111100010111gen[B1]={d1,d2,d3}kill[B1]={d4,d5,d6,d7}gen[B2]={d4,d5}kill[B2]={d1,d2,d7}gen[B3]={d6}kill[B3]={d3}gen[B4]={d7}kill[B4]={d1,d4}d1:i:=m

1d2:j:=nd3:a:=u1B1B2d7:i:=u3B4d4:i:=i+1d5:j:=j

1d6:a:=u2B39.3

全局?jǐn)?shù)據(jù)流分析介紹

in[B] out[B]B1

00000001110000B211101110011110B300111000001110B400111100010111gen[B1]={d1,d2,d3}kill[B1]={d4,d5,d6,d7}gen[B2]={d4,d5}kill[B2]={d1,d2,d7}gen[B3]={d6}kill[B3]={d3}gen[B4]={d7}kill[B4]={d1,d4}d1:i:=m

1d2:j:=nd3:a:=u1B1B2d7:i:=u3B4d4:i:=i+1d5:j:=j

1d6:a:=u2B39.3

全局?jǐn)?shù)據(jù)流分析介紹

in[B] out[B]B1

00000001110000B211101110011110B300111100001110B400111100010111gen[B1]={d1,d2,d3}kill[B1]={d4,d5,d6,d7}gen[B2]={d4,d5}kill[B2]={d1,d2,d7}gen[B3]={d6}kill[B3]={d3}gen[B4]={d7}kill[B4]={d1,d4}d1:i:=m

1d2:j:=nd3:a:=u1B1B2d7:i:=u3B4d4:i:=i+1d5:j:=j

1d6:a:=u2B39.3

全局?jǐn)?shù)據(jù)流分析介紹in[B]=

out[P]

P是B的前驅(qū)out[B]=gen

[B]

(in[B]

kill[B]) 到達(dá)-定值方程是正向的方程，另一類數(shù)據(jù)流方程是反向的到達(dá)-定值方程的合流算符是求并集，另一類數(shù)據(jù)流方程的合流算符是求交集到達(dá)-定值的信息存儲為引用-定值鏈（或叫ud鏈），指能到達(dá)變量的某個(gè)引用的所有定值9.3

全局?jǐn)?shù)據(jù)流分析介紹9.3.3可用表達(dá)式x:=y+z x:=y+z x:=y+z. . .. y:=… z:=… . . .p p py+z在p點(diǎn)

y+z在p點(diǎn)

y+z在p點(diǎn)可用

不可用 不可用9.3

全局?jǐn)?shù)據(jù)流分析介紹t1:=4*i?t2:=4*iB1B2B3t1:=4*ii:=t0:=4*it2:=4*iB1B2B39.3

全局?jǐn)?shù)據(jù)流分析介紹計(jì)算可用表達(dá)式的方程out[B]=e_gen[B]

(in[B]

e_kill

[B])in[B]=

out[P] （B不是初始塊）

P是B的前驅(qū)in[B1]=

（B1是初始塊）和到達(dá)-定值方程的區(qū)別初始塊的in處理為特殊情況合流算符是交集運(yùn)算而不是并集運(yùn)算到達(dá)-定值求最小解，可用表達(dá)式求最大解9.3

全局?jǐn)?shù)據(jù)流分析介紹in集合的不同初值比較in[B2]=out[B1]

out[B2]（以B2為例）

out[B2]=G

(in[B2]

K)B1B2Oj+1=G

(Ij

K)I

j+1=out[B1]

Oj+1I0=

I0=UO

1=G O

1=U

KI1=out[B1]

G I1=out[B1]

KO

2=G O

2=G

(out[B1]

K)9.3

全局?jǐn)?shù)據(jù)流分析介紹9.3.4活躍變量分析x的值在p點(diǎn)開始的路徑上被引用，我們說x在p點(diǎn)活躍，否則稱x在p點(diǎn)是死亡的in[B]：開始點(diǎn)的活躍變量集合out[B]：結(jié)束點(diǎn)的活躍變量集合def[B]：塊B中有定值且該定值前無引用的變量集use[B]：塊B中有引用且在該引用前無定值的變量集9.3

全局?jǐn)?shù)據(jù)流分析介紹in[B]：開始點(diǎn)的活躍變量集合out[B]：結(jié)束點(diǎn)的活躍變量集合def[B]：塊B中有定值且該定值前無引用的變量集use[B]：塊B中有引用且在該引用前無定值的變量集in[B]=use[B]

(out[B]

def[B])out[B]=

in[S]

S是B的后繼9.3

全局?jǐn)?shù)據(jù)流分析介紹定值

引用鏈（du鏈）du鏈問題是計(jì)算對變量（如x）定值的所有引用語句s的集合可以建立數(shù)據(jù)流方程來求解定值

引用信息9.4

代碼改進(jìn)變換依賴于上節(jié)收集的數(shù)據(jù)流信息進(jìn)行代碼改進(jìn)變換有些變換可以一起完成，但這里是逐個(gè)討論代替不了局部變換9.4

代碼改進(jìn)變換9.4.1

公共子表達(dá)式刪除對每個(gè)s:

x:=y+z，若y+z在塊的開始點(diǎn)可用,在s前沒有y或z的定值，則執(zhí)行下面的步驟：從該塊開始反向搜索，找出到達(dá)該塊開始點(diǎn)的y+z的計(jì)算建立新變量u把上面找到的每個(gè)語句w:=y+z改成 u:=y+z w:=u用x:=u代替語句s9.4

代碼改進(jìn)變換例c:=d+eb:=d+ea:=d+et:=d+ea:=tt:=d+eb:=tc:=t9.4

代碼改進(jìn)變換該方法并非都是改進(jìn)（若運(yùn)行時(shí)主要走那條紅色路徑）c:=d+eb:=d+ea:=d+et:=d+ea:=tt:=d+eb:=tc:=t9.4

代碼改進(jìn)變換只能刪除明顯的公共子表達(dá)式a:=x+y 和 c:=x+yb:=a*z d:=c*z漏掉了a*z和c*z有相同的值這個(gè)事實(shí)但是若和復(fù)寫傳播聯(lián)系起來，可以找出這樣的公共子表達(dá)式9.4

代碼改進(jìn)變換t2:=4*it3:=a[t2]t6:=4*it7:=a[t6](a)u:=4*it2:=ut3:=a[t2]t6:=ut7:=a[t6](b)u:=4*it2:=ut3:=a[u

]t6:=ut7:=a[u

](c)9.4

代碼改進(jìn)變換9.4.2

復(fù)寫傳播 s:x:=y . . .

u::=x…用y代替x的前提是：語句s是到達(dá)u的唯一的x定值從s到u的每條路徑，包括穿過u若干次的路徑上，沒有對y的賦值9.4

代碼改進(jìn)變換建立新的數(shù)據(jù)流分析方程來解決第二個(gè)前提in[B]和out[B]：復(fù)寫語句s:

x:=y的集合c_gen

[B]：出現(xiàn)在塊B中的s:x:=y，且塊B中該語句的后面沒有對x或y的定值c_kill[B]：不在塊B中的s:x:=y，且x或y在塊B中賦值9.4

代碼改進(jìn)變換建立新的數(shù)據(jù)流分析方程來解決第二個(gè)前提in[B]和out[B]：復(fù)寫語句s:x:=y的集合c_gen

[B]：出現(xiàn)在塊B中的s:x:=y，且塊B中該語句的后面沒有對x或y的定值c_kill[B]：不在塊B中的s:x:=y，且x或y在塊B中賦值

out[B]=c_gen

[B]

(in[B]

c_kill[B])

in[B]=

out[P]（B不是初始塊）

P是B的前驅(qū) in[B1

]=

（B1是初始塊）

9.4

代碼改進(jìn)變換c_gen

[B1]={x:=y}c_gen

[B3]={x:=z}c_kill

[B1]={x:=z}c_kill[B2]={x:=y}c_kill

[B3]={x:=y}in[B1]=

,in[B2]=in[B3]=out[B1]={x:=y}out[B2]=

,out[B3]=in[B4]=out[B4]={x:=z}in[B5]=out[B2]

out[B4]=

x:=y:=x

:=xy:=

x:=zB4B5B3B2B19.4

代碼改進(jìn)變換9.4.3

尋找循環(huán)不變計(jì)算輸入

循環(huán)L，對L的每個(gè)三地址語句，有ud鏈可用。輸出

從控制進(jìn)入L一直到離開L，每次都計(jì)算同樣值的三地址語句被輸出。方法把運(yùn)算對象都是常量（或其所有的到達(dá)

定值都在L外）的語句，標(biāo)記為“不變”語句。重復(fù)下一步，直到?jīng)]有新的語句標(biāo)記為“不變”為止給下面的語句標(biāo)記“不變”：它們先前沒有標(biāo)記，并且所有的運(yùn)算對象都是下列三種情況之一：（a）常量；（b）其所有的到達(dá)

定值都在L外；（c）只有一個(gè)到達(dá)

定值，這個(gè)定值是循環(huán)中已標(biāo)記為“不變”的語句。9.4

代碼改進(jìn)變換9.4.4

代碼外提將循環(huán)不變語句提到循環(huán)的前置結(jié)點(diǎn)中并不是所有的循環(huán)不變語句都可以外提我們討論三個(gè)條件（并非是必要條件）9.4

代碼改進(jìn)變換語句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:=iB5B4B3B2B19.4

代碼改進(jìn)變換語句s:x:=y+z可以外提的條件循環(huán)中沒有其它語句對x定值i:=1i:=3ifu<vgoto

B3v:=v

1ifu<=20goto

B5i:=2u:=u+1j:=iB5B4B3B2B19.4

代碼改進(jìn)變換語句s:x:=y+z可以外提的條件x的其它定值都不能到達(dá)循環(huán)中x的引用i:=1ifu<vgoto

B3k:=iv:=v

1ifu<=20goto

B5i:=2u:=u+1j:=iB5B4B3B2B19.4

代碼改進(jìn)變換9.4.5

歸納變量刪除循環(huán)歸納變量:在循環(huán)中，其值的每次改變都增加或減少某個(gè)固定的常量基本歸納變量：在循環(huán)中只有一個(gè)形如i:=i

c的i，其中c是常量其它歸納變量:在循環(huán)中僅定值一次，并且其值是某個(gè)基本歸納變量的線性函數(shù)，例如

j定值為c

i+d，描述為(i,c,d)9.4

代碼改進(jìn)變換尋找歸納變量找出所有基本歸納變量i:=i

c，描述為(i,1,0)的形式尋找只有一個(gè)賦值的k，其形式為 k:=j*b,k:=b*j,k:=j

/b,k:=j

b,k:=b

j其中b是常數(shù)，j是基本的或非基本的歸納變量 例如，若k:=j*b若j是基本的，則k屬j族，為(j,b,0)若j屬i族，為(i,c,d)，則k屬i族，為(i,b*

c,b*

d)9.4

代碼改進(jìn)變換循環(huán)B2i族 i:(i,1,0)i族 t2:(i,4,0)循環(huán)B3j族 j:(j,1,0)j族 t4:(j,4,0)外循環(huán)B2、B3、B4和B5和上面一樣的i族和j族i:=m

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

B2j:=j

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

B3ifi>=jgoto

B6B4B3B5B69.4

代碼改進(jìn)變換歸納變量的強(qiáng)度削弱 i族

j:(i,c,d)

用j:=s代替j的賦值在每個(gè)賦值i:=i+n的后面，緊接著它加上

s:=s

+c

*

n

i族

s:(i,c,d)在前置塊的末尾加上 s:=c

*i /*

如果c為1，則s:=i*/ s

:=s+d /*

如果d為0則被省略*/9.4

代碼改進(jìn)變換循環(huán)B2i族 i:(i,1,0)i族 t2:(i,4,0) s2:=4*i（前置結(jié)點(diǎn)） s2:=s2+4（循環(huán)內(nèi)） t2:=s2（循環(huán)內(nèi)）循環(huán)B3j族 j:(j,1,0)j族 t4:(j,4,0) s4:=4*j（前置結(jié)點(diǎn)） s4:=s4

4（循環(huán)內(nèi)） t4:=s4（循環(huán)內(nèi)）i:=m

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

B2j:=j

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

B3ifi>=jgoto

B6B4B3B5B69.4

代碼改進(jìn)變換歸納變量刪除ifirelopx

goto

B的測試（x不是歸納變量）取i族的某個(gè)j，優(yōu)先取c=1和d=0的j:(i,c,d）把每個(gè)含i的測試改成對j的測試(假定c為正)

r

:=c*x /*如果c等于1，則r

:=x

*/ r

:=r+d /*如果d為0，則省略*/ ifj

relopr

goto

B9.4

代碼改進(jìn)變換歸納變量刪除ifirelopx

goto

B的測試（x不是歸納變量）取i族的某個(gè)j，優(yōu)先取c=1和d=0的j:(i,c,d）把每個(gè)含i的測試改成對j的測試(假定c為正)

r

:=c*x /*如果c等于1，則r

:=x

*/ r

:=r+d /*如果d為0，則省略*/ ifj

relopr

goto

Bifi1

relopi2

goto

B的測試最簡單的情況是j1:(i1,c1,d1)和j2:(i2,c2,d2)，還有c1=c2且d1=d2那么，i1

relopi2等價(jià)于j1

relopj29.4

代碼改進(jìn)變換歸納變量刪除ifirelopx

goto

B的測試（x不是歸納變量）取i族的某個(gè)j，優(yōu)先取c=1和d=0的j:(i,c,d）把每個(gè)含i的測試改成對j的測試(假定c為正)

r

:=c*x /*如果c等于1，則r:=x

*/ r

:=r+d /*如果d為0，則省略*/ ifj

relopr

goto

Bifi1

relopi2

goto

B的測試最簡單的情況是j1:(i1,c1,d1)和j2:(i2,c2,d2)，還有c1=c2且d1=d2那么，i1

relopi2等價(jià)于j1

relopj2更復(fù)雜的情況，測試的替換可能沒有價(jià)值9.4

代碼改進(jìn)變換循環(huán)B2i族 i:(i,1,0)i族 t2:(i,4,0) s2:=s2+4（循環(huán)內(nèi)） s2:=4*i（前置結(jié)點(diǎn)）循環(huán)B3j族 j:(j,1,0)j族 t4:(j,4,0) s4:=s4

4（循環(huán)內(nèi)） s4:=4*j（前置結(jié)點(diǎn)）i:=m

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

B2j:=j

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

B3ifi>=jgoto

B6B4B3B5B69.4

代碼改進(jìn)變換循環(huán)B2i族 i:(i,1,0)i族 t2:(i,4,0) s2:=s2+4（循環(huán)內(nèi)） s2:=4*i（前置結(jié)點(diǎn)）循環(huán)B3j族 j:(j,1,0)j族 t4:(j,4,0) s4:=s4+4（循環(huán)內(nèi)） s4:=4*j（前置結(jié)點(diǎn)）測試

i>=j由s2>=s4代替，i和j都被刪除i:=m

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

B2j:=j

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

B3ifi>=jgoto

B6B4B3B5B6本章要點(diǎn)對各類優(yōu)化的理解，包括常量合并、公共子表達(dá)式刪除、復(fù)寫傳播、死代碼刪除、循環(huán)優(yōu)化（代碼外提、歸納變量刪除、強(qiáng)度削弱）等掌握建立程序流圖的算法和流圖中自然循環(huán)的識別算法對各種數(shù)據(jù)流分析方程的認(rèn)識和區(qū)分，和對這些方程迭代求解方法的理解，針對各種問題建立數(shù)據(jù)流方程了解如何利用控制流分析的信息和各種數(shù)據(jù)流分析的信息進(jìn)行各類代碼改進(jìn)變換

例題1UNIX下的C編譯命令cc的選擇項(xiàng)g和O的解釋如下,其中dbx的解釋是“dbxisanutilityforsource-leveldebuggingandexecutionofprogramswritteninC”。試說明為什么用了選擇項(xiàng)g后，選擇項(xiàng)O便被忽略。-gProduceadditionalsymboltableinformationfordbx(1)anddbxtool(1)andpass-lgoptiontold(1)(soastoincludetheglibrary,thatis:/usr/lib/libg.a).Whenthisoptionisgiven,the-Oand-Roptionsaresuppressed.-O[level]Optimizetheobjectcode.Ignoredwhen either-g,-go,or-aisused....例題2一個(gè)C語言程序如下：main() pushl%ebp

{ movl%esp,%ebp

inti,j,k; movl$1,%eax --j=1 i=5; movl$6,%edx --k=6 j=1; L4: while(j<100){ addl%edx,%eax--j=j+6 k=i+1; cmpl$99,%eax j=j+k; jle.L4 --while(j

99) }}例題2一個(gè)C語言程序如下：main() pushl%ebp

{ movl%esp,%ebp

inti,j,k; movl$1,%eax --j=1 i=5; movl$6,%edx --k=6 j=1; L4: while(j<100){ addl%edx,%eax--j=j+6 k=i+1; cmpl$99,%eax j=j+k; jle.L4 --while(j

99) }復(fù)寫傳播、常量合并、代碼外提、刪除無用賦值

} 對i，j和k分配內(nèi)存單元也成為多余，從而被取消

例題3一個(gè)C語言程序

main(){ longi,j;

while(i){ if(j){i=j;} }}生成的匯編碼見右邊

pushl%ebp

movl%esp,%ebp

subl$8,%esp.L2:

cmpl$0,-4(%ebp)

jne.L4

jmp.L3.L4:

cmpl$0,-8(%ebp)

je.L5

movl-8(%ebp),%eax

movl%eax,-4(%ebp).L5:

jmp.L2.L3:例題3whileE1doS1L2： E1的代碼 真轉(zhuǎn)L4 無條件轉(zhuǎn)L3 L4： S1的代碼

JMPL2L3:ifE2thenS2

E2的代碼

假轉(zhuǎn)L5 S2的代碼L5：例題3whileE1doS1 當(dāng)它們嵌套時(shí)，代碼結(jié)構(gòu)變成

L2： E1的代碼 L2： E1的代碼 真轉(zhuǎn)L4 真轉(zhuǎn)L4

無條件轉(zhuǎn)L3 無條件轉(zhuǎn)L3L4： S1的代碼 L4： E2的代碼

JMPL2 假轉(zhuǎn)L5

L3: S2的代碼ifE2thenS2 L5： JMPL2

E2的代碼 L3：

假轉(zhuǎn)L5 S2的代碼L5：例題3whileE1doS1 當(dāng)它們嵌套時(shí)，代碼結(jié)構(gòu)變成

L2： E1的代碼 L2： E1的代碼 真轉(zhuǎn)L4 真轉(zhuǎn)L4

無條件轉(zhuǎn)L3 無條件轉(zhuǎn)L3L4： S1的代碼 L4： E2的代碼

JMPL2 假轉(zhuǎn)L5

L3: S2的代碼ifE2thenS2 L5： JMPL2

E2的代碼 L3：

假轉(zhuǎn)L5 S2的代碼L5：例題3whileE1d