編譯原理第十一章

代碼優(yōu)化簡介2優(yōu)化：是對代碼進(jìn)行等價變換，使得變換后的代碼運(yùn)行結(jié)果與變換前代碼運(yùn)行結(jié)果相同，而運(yùn)行速度加大或占用存儲空間少，或兩者都有。編譯程序的優(yōu)化工作旨在生成較好性能的目標(biāo)代碼，為此，編譯程序需要對代碼（中間代碼或目標(biāo)代碼）進(jìn)行各種方式的變換變換的宗旨是：等價-經(jīng)優(yōu)化工作變換后的代碼運(yùn)行結(jié)果應(yīng)與原來程序運(yùn)行結(jié)果一樣。3優(yōu)化工作階段可在中間代碼生成之后和（或）目標(biāo)代碼生成之后進(jìn)行中間代碼的優(yōu)化是對中間代碼進(jìn)行等價變換。目標(biāo)代碼的優(yōu)化是在目標(biāo)代碼生成之后進(jìn)行的，在很大程度上依賴于具體的機(jī)器4依據(jù)優(yōu)化所涉及的程序范圍，可分為局部優(yōu)化、循環(huán)優(yōu)化和全局優(yōu)化三個不同的級別。局部優(yōu)化指的是在只有一個入口、一個出口的基本程序塊上進(jìn)行的優(yōu)化。循環(huán)優(yōu)化是對循環(huán)中的代碼進(jìn)行的優(yōu)化。全局優(yōu)化是在整個程序范圍內(nèi)進(jìn)行的優(yōu)化。

5常用的優(yōu)化技術(shù)有：刪除多余運(yùn)算，循環(huán)不變代碼外提，強(qiáng)度削弱，變換循環(huán)控制條件，合并已知量與復(fù)寫傳播刪除無用賦值。舉例6

P∶=0

forI∶=1to20do

P∶=P+A[I]*B[I];

假定每個元素占4個字長編址

經(jīng)過編譯得到的中間代碼如圖

7刪除多余運(yùn)算（刪除公共子表達(dá)式）

優(yōu)化的目的在于使生成的目標(biāo)代碼較少而執(zhí)行速度較快3and6代碼外提

結(jié)果獨立于循環(huán)執(zhí)行次數(shù)的表達(dá)式，提到循環(huán)的前面,使之只在循環(huán)外計算一次4and789強(qiáng)度削弱：把強(qiáng)度大的運(yùn)算換算成強(qiáng)度小的運(yùn)算T1的值與I保持線性關(guān)系，每次總是增加4

10變換循環(huán)控制條件：I和T1始終保持T1＝4*I的線性關(guān)系，把四元式（12）的循環(huán)控制條件I≤20變換成T1≤80

合并已知量與復(fù)寫傳播

四元式（3）可變?yōu)門1＝4

四元式(6)把T1的值復(fù)寫到T4中，四元式（8）要引用T4的值，而從四元式（6）到四元式（8）之間未改變T4和T1的值，則將四元式（8）改為T6∶=T5[T1]1112刪除無用賦值（6）對T4賦值，但T4未被引用；另外，（2）和（11）對I賦值，但只有（11）引用I

13局部優(yōu)化指基本塊內(nèi)的優(yōu)化基本塊是指程序中一個順序執(zhí)行的語句序列，其中只有一個入口語句和一個出口語句?？刂屏髦荒軓钠淙肟谡Z句進(jìn)入，從其出口語句退出,沒有中途停止或分支局部優(yōu)化工作包括對于一個給定的程序，把它劃分為一系列的基本塊,在各個基本塊范圍內(nèi)分別進(jìn)行優(yōu)化如何分基本塊？14基本塊的劃分先定義基本塊的入口語句：

①程序的第一個語句；或者，

②條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句的轉(zhuǎn)移目標(biāo)語句；或者，

③緊跟在條件轉(zhuǎn)移語句后面的語句。15劃分中間代碼（四元式程序）為基本塊的算法其步驟如下：

①求出四元式程序中各個基本塊的入口語句。

②對每一入口語句，構(gòu)造其所屬的基本塊。它是由該入口語句到下一入口語句（不包括下一入口語句），或到一轉(zhuǎn)移語句（包括該轉(zhuǎn)移語句），或到一停語句（包括該停語句）之間的語句序列組成的。

③凡未被納入某一基本塊的語句、都是程序中控制流程無法到達(dá)的語句，因而也是不會被執(zhí)行到的語句，可以把它們刪除。16(1)read(C)(2)A:=0(3)B:=1(4)L1:A:=A+B(5)ifB>=CgotoL2(6)B:=B+1(7)gotoL1(8)L2:write(A)(9)halt

語句（1）是程序的第一個語句，因此它是入口語句。

語句（4）和語句（8）是條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句的轉(zhuǎn)移目標(biāo)語句，因此是入口語句。

語句（6）是緊跟在條件轉(zhuǎn)移語句后面的語句，因此是入口語句。

語句（1），（2）和（3）構(gòu)成一個基本塊，語句（4）和（5）構(gòu)成一個基本塊，語句（6）和（7）構(gòu)成一個基本塊，語句（8）和（9）構(gòu)成一個基本塊。17基本塊內(nèi)的優(yōu)化變換兩類重要的局部等價變換可用于基本塊：保結(jié)構(gòu)的變換和代數(shù)變換基本塊的主要保結(jié)構(gòu)變換是

①刪除公共子表達(dá)式

②刪除無用代碼

③重新命名臨時變量

④交換語句次序

代數(shù)變換可以把基本塊計算的表達(dá)式集合變換成代數(shù)等價的集合。其中常用的變換是那些可以簡化表達(dá)式或用較快運(yùn)算代替較慢運(yùn)算的變換

18有四元式程序：

t1:=4-2

t2:=t1/2

t3:=a*t2

t4:=t3*t1

t5:=b+t4

c:=t5*t5

19進(jìn)行合并已知量變換后得到：

t1:=2

t2:=t1/2

t3:=a*t2

t4:=t3*t1

t5:=b+t4

c:=t5*t5

20再進(jìn)行復(fù)寫傳播和刪除無用賦值等變換后得到：

t2:=2/2

t3:=a*t2

t4:=t3*2

t5:=b+t4

c:=t5*t5

21再進(jìn)行合并已知量變換后得到：

t2:=1

t3:=a*t2

t4:=t3*2

t5:=b+t4

c:=t5*t522再進(jìn)行復(fù)寫傳播和刪除無用賦值等變換后得到：

t3:=a*1

t4:=t3*2

t5:=b+t4

c:=t5*t5

接著使用代數(shù)變換后有：

t3:=a

t4:=t3*2

t5:=b+t4

c:=t5*t5

23使用復(fù)寫傳播和刪除無用賦值變換后又有：

t4:=a*2

t5:=b+t4

c:=t5*t5

再使用代數(shù)變換：

t4:=a+a

t5:=b+t4

c:=t5*t5

24重新命名臨時變量：

t1:=a+a

t5:=b+t1

c:=t5*t5

還可減少臨時變量：

t1:=a+a

t1:=b+t1

c:=t1*t1OK25基本塊的DAG表示一個有向圖中，我們稱任一有向邊ni→nj(或表示為有序?qū)Γ╪i，nj）)中的結(jié)點ni為結(jié)點nj的前驅(qū)（父結(jié)），結(jié)點nj為結(jié)點ni的后繼（子結(jié)）。任一有向邊序列n1→n2，n2→n3，…，nk-1→nk為從結(jié)點n1到結(jié)點nk的一條通路。如果其中n1＝nk，則稱該通路為環(huán)路如果有向圖中任一通路都不是環(huán)路，則稱該有向圖為無環(huán)路有向圖，簡稱DAG

2627此處要用到的有向圖，是一種其結(jié)點帶有下述標(biāo)記或附加信息的DAG：

①圖的葉結(jié)點，即無后繼的結(jié)點，以一標(biāo)識符（變量名）或常數(shù)作為標(biāo)記，表示這個結(jié)點代表該變量或常數(shù)的值。如果葉結(jié)點用來代表某變量A的地址，則用addr（A）作為這個結(jié)點的標(biāo)記。通常把葉結(jié)點上作為標(biāo)記的標(biāo)識符加上下標(biāo)0，以表示它是該變量的初值。

②圖的內(nèi)部結(jié)點，即有后繼的結(jié)點,以一運(yùn)算符作為標(biāo)記，表示這個結(jié)點代表應(yīng)用該運(yùn)算符對其后繼結(jié)點所代表的值進(jìn)行運(yùn)算的結(jié)果。

③圖中各個結(jié)點上可能附加一個或多個標(biāo)識符，表示這些變量具有該結(jié)點所代表的值。28這種DAG可用來描述計算過程，又稱為描述計算過程的DAG一個基本塊，可用一個DAG來表示。下圖列出各種四元式及相對應(yīng)的DAG的結(jié)點形式。圖中ni為結(jié)點編號，結(jié)點下面的符號（運(yùn)算符、標(biāo)識符或常數(shù)）是各結(jié)點的標(biāo)記，各結(jié)點右邊的標(biāo)識符是結(jié)點的附加標(biāo)識符。29（0）A：=B（：=，B，-，A）

（1）A：=opB（op，B，-，A）（2）A：=BopC（op，B，C，A）

30假設(shè)DAG各結(jié)點信息將用某種適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)來存放。并設(shè)有一個標(biāo)識符（包括常數(shù)）與結(jié)點的對應(yīng)表。NODE（A）是描述這種對應(yīng)關(guān)系的一個函數(shù)，它的值或者是一個結(jié)點的編號n，或者無定義。前一個情況代表DAG中存在一個結(jié)點n，A是其上的標(biāo)記或附加標(biāo)識符。31下面是僅含0，1，2型四元式的基本塊的DAG構(gòu)造算法。

首先，DAG為空。

對基本塊的每一四元式，依次執(zhí)行：

1．如果NODE（B）無定義，則構(gòu)造一標(biāo)記為B的葉結(jié)點并定義NODE（B）為這個結(jié)點；

如果當(dāng)前四元式是0型，則記NODE（B）的值為n，轉(zhuǎn)4。

如果當(dāng)前四元式是1型，則轉(zhuǎn)2.（1）。

如果當(dāng)前四元式是2型，則：（Ⅰ）如果NODE（C）無定義，則構(gòu)造一標(biāo)記為C的葉結(jié)點并定義NODE（C）為這個結(jié)點，（Ⅱ）轉(zhuǎn)2.（2）。

2．

（1）如果NODE（B）是標(biāo)記為常數(shù)的葉結(jié)點，則轉(zhuǎn)2.（3），否則轉(zhuǎn)3.（1）。

（2）如果NODE（B）和NODE（C）都是標(biāo)記為常數(shù)的葉結(jié)點，則轉(zhuǎn)2.（4），否則轉(zhuǎn)3.（2）。

（3）執(zhí)行op

B（即合并已知量），令得到的新常數(shù)為P。如果NODE（B）是處理當(dāng)前四元式時新構(gòu)造出來的結(jié)點，則刪除它。如果NODE（P）無定義，則構(gòu)造一用P做標(biāo)記的葉結(jié)點n。置NODE（P）＝n，轉(zhuǎn)4.。

（4）執(zhí)行B

op

C(即合并已知量)，令得到的新常數(shù)為P。如果NODE（B）或NODE（C）是處理當(dāng)前四元式時新構(gòu)造出來的結(jié)點，則刪除它。如果NODE（P）無定義，則構(gòu)造一用P做標(biāo)記的葉結(jié)點n。置NODE（P）＝n，轉(zhuǎn)4.。323．

（1）檢查DAG中是否已有一結(jié)點，其唯一后繼為NODE（B），且標(biāo)記為op（即找公共子表達(dá)式）。如果沒有，則構(gòu)造該結(jié)點n，否則就把已有的結(jié)點作為它的結(jié)點并設(shè)該結(jié)點為n，轉(zhuǎn)4.。

（2）檢查DAG中是否已有一結(jié)點，其左后繼為NODE（B），右后繼為NODE（C），且標(biāo)記為op(即找公共子表達(dá)式)。如果沒有，則構(gòu)造該結(jié)點n，否則就把已有的結(jié)點作為它的結(jié)點并設(shè)該結(jié)點為n。轉(zhuǎn)4.。

4．如果NODE（A）無定義，則把A附加在結(jié)點n上并令NODE（A）＝n；否則先把A從NODE（A）結(jié)點上的附加標(biāo)識符集中刪除（注意，如果NODE（A）是葉結(jié)點，則其標(biāo)記A不刪除），把A附加到新結(jié)點n上并令NODE（A）＝n。轉(zhuǎn)處理下一四元式。

33例試構(gòu)造以下基本塊G的DAG。

(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*T63435將圖11.10（k）的基本塊G的DAG按原來構(gòu)造其結(jié)點的順序，重新寫成四元式，得到以下的四元式序列G′

G’:(1)T0∶=3.14

(2)T1∶=6.28

(3)T3∶=6.28

(4)T2∶=R+r

(5)T4∶=T2

(6)A∶=6.28*T2

(7)T5∶=A

(8)T6∶=R-r

(9)B∶=A*T6

原來：G

(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．G中的代碼（2）和（6）的已知量都已合并。

2．G中（5）的無用賦值已被刪除。

3．G中（3）和（7）的公共子表達(dá)式R+r只被計算一次，刪除了多余運(yùn)算。

所以G′是G的優(yōu)化結(jié)果。36控制流分析和循環(huán)優(yōu)化循環(huán)中的代碼反復(fù)執(zhí)行，因而為了提高目標(biāo)代碼的效率必須著重考慮循環(huán)的代碼優(yōu)化。進(jìn)行循環(huán)優(yōu)化必須找出程序中的循環(huán)，這就需要對程序的控制流程進(jìn)行分析37控制流程圖一個控制流程圖就是具有唯一首結(jié)點的有向圖。首結(jié)點就是從它開始到控制流程圖中任何結(jié)點都有一條通路的結(jié)點。把一個控制流程圖表示成一個三元組G＝（N，E，n0），其中，N代表圖中所有結(jié)點集，E代表圖中所有有向邊集，n0代表首結(jié)點。控制流程圖簡稱為流圖。

38一個程序可用一個流圖來表示。流圖中的有限結(jié)點集N就是程序的基本塊集，流圖中的結(jié)點就是程序中的基本塊。流圖的首結(jié)點就是包含程序第一個語句的基本塊。程序流圖中的有向邊集E是這樣構(gòu)成的：

假設(shè)流圖中結(jié)點i和結(jié)點j分別對應(yīng)于程序的基本塊i和基本塊j，則當(dāng)下述條件1)或2)有一個成立時，從結(jié)點i有一有向邊引向結(jié)點j：

1).基本塊j在程序中的位置緊跟在基本塊i之后，并且基本塊的出口語句不是無條件轉(zhuǎn)移語句goto（s）或停語句。

2).基本塊i的出口語句是goto（s）或if…goto（s），并且（s）是基本塊j的入口語句。39(1)readx

(2)ready

(3)r∶=xmody

(4)ifr=0goto(8)

(5)x∶=y

(6)y∶=r

(7)goto(3)

(8)writey

(9)halt4041流圖的簡潔表示42在程序流圖中，我們稱具有下列性質(zhì)的結(jié)點序列為一個循環(huán)：

①它們是強(qiáng)連通的。也即，其中任意兩個結(jié)點之間，必有一條通路，而且該通路上各結(jié)點都屬于該結(jié)點序列。如果序列只包含一個結(jié)點，則必有一有向邊從該結(jié)點引到其自身。

②它們中間有且只有一個是入口結(jié)點。所謂入口結(jié)點，是指序列中具有下述性質(zhì)的結(jié)點：

從序列外某結(jié)點，有一有向邊引到它，或者它就是程序流圖的首結(jié)點。

因此，我們定義的循環(huán)就是程序流圖中具有唯一入口結(jié)點的強(qiáng)連通子圖，從循環(huán)外要進(jìn)入循環(huán)，必須首先經(jīng)過循環(huán)的入口結(jié)點。

43在程序流圖中，對任意兩個結(jié)點m和n，如果從流圖的首結(jié)點出發(fā)，到達(dá)n的任一通路都要經(jīng)過m，則稱m是n的必經(jīng)結(jié)點，記為mDOMn。流圖中結(jié)點n的所有必經(jīng)結(jié)點的集合，稱為結(jié)點n的必經(jīng)結(jié)點集，記為D（n）。

循環(huán)的入口結(jié)點是循環(huán)中所有結(jié)點的必經(jīng)結(jié)點。

44

D(1)={1}

D(2)={1,2}

D(3)={1,2,3}

D(4)={1,2,4}

D(5)={1,2,4,5}

D(6)={1,2,4,6}

D(7)={1,2,4,7}45循環(huán)的查找算法假設(shè)a→b是流圖中的一條有向邊，如果bDOMa，則稱a→b是流圖中的一條回邊。

如果已知有向邊n→d是回邊，那么就可以求出由它組成的循環(huán)。該循環(huán)就是由結(jié)點d、結(jié)點n以及有通路到達(dá)n而該通路不經(jīng)過d的所有結(jié)點組成，并且d是該循環(huán)的唯一入口結(jié)點。46有向邊6→6、7→4、4→2是回邊。因為根據(jù)前例的結(jié)果有6DOM6，4DOM7，2DOM4，其它有向邊都不是回邊。對于例子，由回邊6→6組成的循環(huán)就是｛6｝,由回邊7→4組成的循環(huán)是｛4，5，6，7｝；由回邊4→2組成的循環(huán)是｛2，3，4，5，6，7｝。47循環(huán)優(yōu)化循環(huán)優(yōu)化的三種重要技術(shù)是代碼外提；刪除歸納變量和強(qiáng)度削弱。只對代碼外提再進(jìn)行一些討論48代碼外提這種變換把循環(huán)不變運(yùn)算，即產(chǎn)生的結(jié)果獨立于循環(huán)執(zhí)行次數(shù)的表達(dá)式，放到循環(huán)的前面所討論的循環(huán)只存在一個入口。實行代碼外提時，在循環(huán)的入口結(jié)點前面建立一個新結(jié)點（基本塊），稱之為循環(huán)的前置結(jié)點。循環(huán)的前置結(jié)點以循環(huán)的入口結(jié)點為其唯一后繼，原來流圖中從循環(huán)外引到循環(huán)入口結(jié)點的有向邊，改成引到循環(huán)前置結(jié)點4950前置結(jié)點也是唯一的,循環(huán)中外提的代碼將全部提至前置結(jié)點中EG是否在任何情況下，都可把循環(huán)不變運(yùn)算外提呢?5152｛B2，B3，B4｝是循環(huán)，其中B2是循環(huán)的入口結(jié)點，B4是出口結(jié)點B3中i∶=