《編譯原理》課件第5章

5.1局部?jī)?yōu)化5.2循環(huán)優(yōu)化5.3全局優(yōu)化概述5.4代碼優(yōu)化示例習(xí)題五第5章代碼優(yōu)化源程序經(jīng)過(guò)詞法分析、語(yǔ)法分析、語(yǔ)義分析等階段的編譯工作，得到了與源程序功能等價(jià)的中間代碼。但是，由于這種中間代碼是“機(jī)械生成”的結(jié)果，因而必然存在效率不高和有冗余代碼的現(xiàn)象，還需進(jìn)行代碼優(yōu)化。代碼優(yōu)化的含義是：對(duì)代碼進(jìn)行等價(jià)變換，使得變換后的代碼具有更高的時(shí)間效率和空間效率。代碼優(yōu)化的目的是提高目標(biāo)程序的質(zhì)量。優(yōu)化可以在編譯的不同階段進(jìn)行，但最主要的一類優(yōu)化是在目標(biāo)代碼生成以前進(jìn)行的，即對(duì)語(yǔ)義分析后的中間代碼進(jìn)行優(yōu)化，這種優(yōu)化的優(yōu)點(diǎn)是不依賴于具體的計(jì)算機(jī)。另一類重要的優(yōu)化是在生成目標(biāo)代碼時(shí)進(jìn)行的，它在很大程度上依賴于具體的計(jì)算機(jī)。本章討論前一種與機(jī)器無(wú)關(guān)的中間代碼優(yōu)化。根據(jù)優(yōu)化對(duì)象所涉及的程序范圍，優(yōu)化又分為局部?jī)?yōu)化、循環(huán)優(yōu)化和全局優(yōu)化。一個(gè)程序從結(jié)構(gòu)上看，作為結(jié)點(diǎn)的基本塊是其基礎(chǔ)。因?yàn)榛緣K的結(jié)構(gòu)最簡(jiǎn)單、因素最單純，所以它也是優(yōu)化的基礎(chǔ)，對(duì)基本塊的優(yōu)化就是局部?jī)?yōu)化。循環(huán)是程序中要反復(fù)執(zhí)行的部分，優(yōu)化的效益當(dāng)然很大，所以循環(huán)優(yōu)化是優(yōu)化工作的一個(gè)重點(diǎn)。針對(duì)整個(gè)程序的優(yōu)化即全局優(yōu)化，它涉及到對(duì)程序數(shù)據(jù)流分析的問(wèn)題。我們?cè)诖酥饕懻摼植績(jī)?yōu)化與循環(huán)優(yōu)化。為了敘述方便，從本章開(kāi)始把四元式寫(xiě)成更為直觀的三地址代碼形式，如：

(op,B,C,A)?

A=BopC (jrop,B,C,L)?

ifBropCgotoL (j,_,_,L)?

gotoL5.1局部?jī)?yōu)化5.1.1基本塊的劃分方法所謂基本塊，是指程序中一順序執(zhí)行的語(yǔ)句序列，其中只有一個(gè)入口和一個(gè)出口，入口就是該序列的第一個(gè)語(yǔ)句，出口就是該序列的最后一個(gè)語(yǔ)句。對(duì)一個(gè)基本塊來(lái)說(shuō)，執(zhí)行時(shí)只能從其入口進(jìn)入，從其出口退出。對(duì)一個(gè)給定的程序，我們可以把它劃分為一系列基本塊，在各個(gè)基本塊范圍內(nèi)進(jìn)行的優(yōu)化稱為局部?jī)?yōu)化。劃分基本塊的關(guān)鍵問(wèn)題是準(zhǔn)確定義入口和出口語(yǔ)句。下面我們給出劃分四元式程序?yàn)榛緣K的算法：

(1)從四元式序列確定滿足以下條件的入口語(yǔ)句：①四元式序列的第一個(gè)語(yǔ)句；②能由條件轉(zhuǎn)移語(yǔ)句或無(wú)條件轉(zhuǎn)移語(yǔ)句轉(zhuǎn)移到的語(yǔ)句；③緊跟在條件轉(zhuǎn)移語(yǔ)句后面的語(yǔ)句。

(2)確定滿足以下條件的出口語(yǔ)句：①下一個(gè)入口語(yǔ)句的前導(dǎo)語(yǔ)句；②轉(zhuǎn)移語(yǔ)句(包括轉(zhuǎn)移語(yǔ)句自身)；③停語(yǔ)句(包括停語(yǔ)句自身)。例如，考察下面求最大公因子的三地址代碼程序：

(1)?readX

(2)?readY

(3)?R=X%Y

(4)?ifR=0goto(8)

(5)?X=Y

(6)?Y=R

(7)?goto(3)

(8)?writeY

(9)?halt根據(jù)上述劃分基本塊的算法可確定四元式(1)、(3)、(5)、(8)是入口語(yǔ)句，而四個(gè)基本塊分別是：(1)(2)，(3)(4)，(5)(6)(7)，(8)(9)。5.1.2基本塊的DAG表示

DAG(DirectedAcyclicGraph)是一種有向圖，常常用來(lái)對(duì)基本塊進(jìn)行優(yōu)化。一個(gè)基本塊的DAG是一種其結(jié)點(diǎn)帶有下述標(biāo)記或附加信息的DAG：

(1)圖的葉結(jié)點(diǎn)(無(wú)后繼的結(jié)點(diǎn))以一標(biāo)識(shí)符(變量名)或常數(shù)作為標(biāo)記，表示該結(jié)點(diǎn)代表該變量或常數(shù)的值。如果葉結(jié)點(diǎn)用來(lái)表示一變量A的地址，則用addr(A)作為該結(jié)點(diǎn)的標(biāo)記。通常把葉結(jié)點(diǎn)上作為標(biāo)記的標(biāo)識(shí)符加上下標(biāo)0，以表示它是該變量的初值。

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

(3)圖中各個(gè)結(jié)點(diǎn)上可能附加一個(gè)或多個(gè)標(biāo)識(shí)符，表示這些變量具有該結(jié)點(diǎn)所代表的值。一個(gè)基本塊由一個(gè)四元式序列組成，且每一個(gè)四元式都可以用相應(yīng)的DAG結(jié)點(diǎn)表示。圖5–1給出了不同四元式和與其對(duì)應(yīng)的DAG結(jié)點(diǎn)形式。圖中，各結(jié)點(diǎn)圓圈中的ni是構(gòu)造DAG過(guò)程中各結(jié)點(diǎn)的編號(hào)，而各結(jié)點(diǎn)下面的符號(hào)(運(yùn)算符、標(biāo)識(shí)符或常數(shù))是各結(jié)點(diǎn)的標(biāo)記，各結(jié)點(diǎn)右邊的標(biāo)識(shí)符是結(jié)點(diǎn)上的附加標(biāo)識(shí)符。除了對(duì)應(yīng)轉(zhuǎn)移語(yǔ)句的結(jié)點(diǎn)右邊可附加一語(yǔ)句位置來(lái)指示轉(zhuǎn)移目標(biāo)外，其余各類結(jié)點(diǎn)的右邊只允許附加標(biāo)識(shí)符。除對(duì)應(yīng)于數(shù)組元素賦值的結(jié)點(diǎn)(標(biāo)記為[]=)有三個(gè)后繼外，其余結(jié)點(diǎn)最多只有兩個(gè)后繼。圖5–1四元式與DAG結(jié)點(diǎn)

利用DAG進(jìn)行基本塊優(yōu)化的基本思想是：首先按基本塊內(nèi)的四元式序列順序?qū)⑺械乃脑綐?gòu)造成一個(gè)DAG，然后按構(gòu)造結(jié)點(diǎn)的次序?qū)AG還原成四元式序列。由于在構(gòu)造DAG的同時(shí)已做了局部?jī)?yōu)化，所以最后所得到的是優(yōu)化過(guò)的四元式序列。為了DAG構(gòu)造算法的需要，我們將圖5–1中的四元式按照其對(duì)應(yīng)結(jié)點(diǎn)的后繼結(jié)點(diǎn)個(gè)數(shù)分為四類：

(1)?0型四元式：后繼結(jié)點(diǎn)個(gè)數(shù)為0，如圖5–1(1)所示；

(2)?1型四元式：有一個(gè)后繼結(jié)點(diǎn)，如圖5–1(2)所示；

(3)?2型四元式：有兩個(gè)后繼結(jié)點(diǎn)，如圖5–1(3)、(4)、(5)所示；

(4)?3型四元式：有三個(gè)后繼結(jié)點(diǎn)，如圖5–1(6)所示。我們規(guī)定：用大寫(xiě)字母(如A、B等)表示四元式中的變量名(或常數(shù))；用函數(shù)Node(A)表示A在DAG中的相應(yīng)結(jié)點(diǎn)，其值可為n或者無(wú)定義，并用n表示DAG中的一個(gè)結(jié)點(diǎn)值。這樣，每個(gè)基本塊僅含0、1、2型四元式的DAG構(gòu)造算法如下(對(duì)基本塊的每一個(gè)四元式依次執(zhí)行該算法)：

(1)若Node(B)無(wú)定義，則構(gòu)造一標(biāo)記為B的葉結(jié)點(diǎn)并定義Node(B)為這個(gè)結(jié)點(diǎn)，然后根據(jù)下列情況做不同處理：①若當(dāng)前四元式是0型，則記Node(B)的值為n，轉(zhuǎn)(4)。②若當(dāng)前四元式是1型，則轉(zhuǎn)(2)①。③若當(dāng)前四元式是2型，則：

i.如果Node(C)無(wú)定義，則構(gòu)造一標(biāo)記為C的葉結(jié)點(diǎn)，并定義Node(C)為這個(gè)結(jié)點(diǎn)；

ii.轉(zhuǎn)(2)②。

(2)①若Node(B)是以常數(shù)標(biāo)記的葉結(jié)點(diǎn)，則轉(zhuǎn)(2)③，否則轉(zhuǎn)(3)①。②若Node(B)和Node(C)都是以常數(shù)標(biāo)記的葉結(jié)點(diǎn)，則轉(zhuǎn)(2)④，否則轉(zhuǎn)(3)②。③執(zhí)行opB(即合并已知量)，令得到的新常數(shù)為P。若Node(B)是處理當(dāng)前四元式時(shí)新建立的結(jié)點(diǎn)，則刪除它；若Node(P)無(wú)定義，則構(gòu)造一用P做標(biāo)記的葉結(jié)點(diǎn)n并置Node(P)=n；轉(zhuǎn)(4)。④執(zhí)行BopC(即合并已知量)，令得到的新常數(shù)為P。若Node(B)或Node(C)是處理當(dāng)前四元式時(shí)新建立的結(jié)點(diǎn)，則刪除它；若Node(P)無(wú)定義，則構(gòu)造一用P做標(biāo)記的葉結(jié)點(diǎn)n并置Node(P)=n；轉(zhuǎn)(4)。

(3)①檢查DAG中是否有標(biāo)記為op且以Node(B)為惟一后繼的結(jié)點(diǎn)(即查找公共子表達(dá)式)。若有，則把已有的結(jié)點(diǎn)作為它的結(jié)點(diǎn)并設(shè)該結(jié)點(diǎn)為n；若沒(méi)有，則構(gòu)造一個(gè)新結(jié)點(diǎn)；轉(zhuǎn)(4)。②檢查DAG中是否有標(biāo)記為op且其左后繼為Node(B)、右后繼為Node(C)的結(jié)點(diǎn)(即查找公共子表達(dá)式)。若有，則把已有的結(jié)點(diǎn)作為它的結(jié)點(diǎn)并設(shè)該結(jié)點(diǎn)為n；若沒(méi)有，則構(gòu)造一個(gè)新結(jié)點(diǎn)；轉(zhuǎn)(4)。

(4)若Node(A)無(wú)定義，則把A附加在結(jié)點(diǎn)n上并令Node(A)=n；否則，先從Node(A)的附加標(biāo)識(shí)符集中將A刪去(注意，若Node(A)是葉結(jié)點(diǎn)，則不能將A刪去)，然后再把A附加到新結(jié)點(diǎn)n上，并令Node(A)=n。注意：算法中步驟(2)的①、②用于判斷結(jié)點(diǎn)是否為常數(shù)，而步驟(2)的③、④則是對(duì)常數(shù)的處理。對(duì)任何一個(gè)四元式，如果其中參與運(yùn)算的對(duì)象都是編譯時(shí)的已知量，那么(2)并不生成計(jì)算該結(jié)點(diǎn)值的內(nèi)部結(jié)點(diǎn)，而是執(zhí)行該運(yùn)算并用計(jì)算出的常數(shù)生成一個(gè)葉結(jié)點(diǎn)，所以(2)的作用是實(shí)現(xiàn)合并已知量。步驟(3)的作用是檢查公共子表達(dá)式。對(duì)具有公共子表達(dá)式的所有四元式，它只產(chǎn)生一個(gè)計(jì)算該表達(dá)式值的內(nèi)部結(jié)點(diǎn)，而把那些被賦值的變量標(biāo)識(shí)符附加到該結(jié)點(diǎn)上。這樣，當(dāng)把該結(jié)點(diǎn)重新寫(xiě)為四元式時(shí)，就刪除了多余運(yùn)算。步驟(4)的功能是將(1)～(3)的操作結(jié)果賦給變量A，也即將標(biāo)識(shí)符A標(biāo)識(shí)在操作結(jié)果的結(jié)點(diǎn)n上，而執(zhí)行把A從Node(A)上的附加標(biāo)識(shí)符集中刪除的操作則意味著刪除了無(wú)用賦值(對(duì)A賦值后但在該A值引用之前又重新對(duì)A進(jìn)行了賦值，則前一個(gè)賦值為無(wú)用賦值)。綜上所述，DAG可以在基本塊內(nèi)實(shí)現(xiàn)合并已知量、刪除無(wú)用賦值和刪除多余運(yùn)算的優(yōu)化。例5.1

試構(gòu)造以下基本塊的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*T6

[解答]按照算法順序處理每一四元式后構(gòu)造出的DAG如圖5–2所示，其中每一子圖(1)、(2)、…、(10)分別對(duì)應(yīng)四元式(1)～(10)的DAG構(gòu)造。圖5–2DAG構(gòu)造過(guò)程說(shuō)明如下：

(1)對(duì)應(yīng)圖5–2(2)，四元式T1=2*T0首先執(zhí)行算法中的步驟(1)，因Node(B)無(wú)定義，所以構(gòu)造一個(gè)標(biāo)記為2的葉結(jié)點(diǎn)并定義Node(2)為這個(gè)結(jié)點(diǎn)。因當(dāng)前四元式是2型且Node(C)已有定義(此時(shí)為Node(T0))，轉(zhuǎn)算法步驟(2)②。因Node(B)=Node(2)和Node(C)=Node(T0)都是標(biāo)記為常數(shù)的葉結(jié)點(diǎn)，則執(zhí)行BopC并令新結(jié)點(diǎn)為P(=6.28)。由于Node(P)無(wú)定義，故構(gòu)造Node(P)=Node(6.28)。此外，因Node(B)=Node(2)是處理當(dāng)前四元式時(shí)新構(gòu)造出來(lái)的結(jié)點(diǎn)，故刪除n2。接下來(lái)執(zhí)行算法步驟(4)，因Node(A)無(wú)定義而將T1附加在結(jié)點(diǎn)n3上，并令Node(T1)=6.28；最后DAG生成了2個(gè)結(jié)點(diǎn)n1和n3，因結(jié)點(diǎn)n2被刪除而將n3改名為n2。圖5–2(2)的形成過(guò)程實(shí)際上也是合并已知量的優(yōu)化過(guò)程。

(2)圖5–2(4)中T1、T2已有定義，則僅生成一個(gè)新結(jié)點(diǎn)n6并將A附加在n6上。圖5-2(5)中結(jié)點(diǎn)B已有定義，故直接附加在n6上。

(3)圖5–2(6)的處理過(guò)程與圖5–2(2)略同，但在生成P時(shí)因其已在DAG中(即Node(6.28))，故不生成新結(jié)點(diǎn)而直接將T3附加在結(jié)點(diǎn)6.28上。

(4)圖5–2(7)的生成過(guò)程實(shí)質(zhì)上是刪除多余運(yùn)算(刪除公共子表達(dá)式)的優(yōu)化。因?yàn)镈AG中已有葉結(jié)點(diǎn)R與葉結(jié)點(diǎn)r，并且執(zhí)行op操作后得到的新結(jié)點(diǎn)T2也已經(jīng)在DAG中，故執(zhí)行算法步驟(4)時(shí)因T4無(wú)定義而將T4附加在結(jié)點(diǎn)n5上。

(5)圖5–2(9)中，變量R和r已在DAG中有相應(yīng)的結(jié)點(diǎn)，執(zhí)行“?”操作后，產(chǎn)生的新結(jié)點(diǎn)P無(wú)定義，故僅生成一個(gè)新結(jié)點(diǎn)n7并將T6標(biāo)記于其上。

(6)圖5–2(10)中，對(duì)當(dāng)前四元式B=T5*T6，DAG中已有結(jié)點(diǎn)T5和T6；執(zhí)行算法步驟(4)時(shí)因結(jié)點(diǎn)B已有定義且不是葉結(jié)點(diǎn)，故先將原B從DAG中刪除，然后生成一個(gè)新結(jié)點(diǎn)n8，將B附加其上并令Node(B)=n8。這一處理過(guò)程實(shí)質(zhì)上是刪除了無(wú)用賦值B=A。5.1.3利用DAG進(jìn)行基本塊的優(yōu)化處理利用DAG進(jìn)行基本塊優(yōu)化處理的基本思想是：按照構(gòu)造DAG結(jié)點(diǎn)的順序，對(duì)每一個(gè)結(jié)點(diǎn)寫(xiě)出其相應(yīng)的四元式表示。我們根據(jù)例5.1DAG結(jié)點(diǎn)的構(gòu)造順序，按照?qǐng)D5–2(10)寫(xiě)出四元式序列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'和原基本塊G相比，我們看到：

(1)?G中四元式(2)和(6)都是已知量和已知量的運(yùn)算，G'已合并；

(2)?G中四元式(5)是一種無(wú)用賦值，G'已將它刪除；

(3)?G中四元式(3)和(7)的R+r是公共子表達(dá)式，G'只對(duì)它們計(jì)算了一次，即刪除了多余的R+r運(yùn)算。因此，G'是對(duì)G實(shí)現(xiàn)上述三種優(yōu)化的結(jié)果。通過(guò)觀察圖5–2(10)中的所有葉結(jié)點(diǎn)和內(nèi)部結(jié)點(diǎn)以及其上的附加標(biāo)識(shí)符，還可以得出以下結(jié)論：

(1)在基本塊外被定值并在基本塊內(nèi)被引用的所有標(biāo)識(shí)符就是DAG中相應(yīng)葉結(jié)點(diǎn)上標(biāo)記的標(biāo)識(shí)符；

(2)在基本塊內(nèi)被定值且該值能在基本塊后面被引用的標(biāo)識(shí)符就是DAG各結(jié)點(diǎn)上的附加標(biāo)識(shí)符。這些結(jié)論可以引導(dǎo)優(yōu)化工作的進(jìn)一步深入，尤其是無(wú)用賦值的優(yōu)化，也即：

(1)如果DAG中某結(jié)點(diǎn)上的標(biāo)識(shí)符在該基本塊之后不會(huì)被引用，就可以不生成對(duì)該標(biāo)識(shí)符賦值的四元式；

(2)如果某結(jié)點(diǎn)ni上沒(méi)有任何附加標(biāo)識(shí)符，或者ni上的附加標(biāo)識(shí)符在該基本塊之后不會(huì)被引用，而且ni也沒(méi)有前驅(qū)結(jié)點(diǎn)，這表明在基本塊內(nèi)和基本塊之后都不會(huì)引用ni的值，那么就不生成計(jì)算ni結(jié)點(diǎn)值的四元式；

(3)如果有兩個(gè)相鄰的四元式A=CopD和B=A，其中第一條代碼計(jì)算出來(lái)的A值僅在第二個(gè)四元式中被引用，則將DAG中相應(yīng)結(jié)點(diǎn)重寫(xiě)成四元式時(shí)，原來(lái)的兩個(gè)四元式可以優(yōu)化為B=CopD。假設(shè)例5.1中T0、T1、T2、T3、T4、T5和T6在基本塊后都不會(huì)被引用，則圖5-2(10)中的DAG就可重寫(xiě)為如下的四元式序列：

(1)?S1=R+r//S1、S2為存放中間結(jié)果的臨時(shí)變量

(2)?A=6.28*S1

(3)?S2=R?r

(4)?B=A*S2以上把DAG重寫(xiě)成四元式序列時(shí)，是按照原來(lái)構(gòu)造DAG結(jié)點(diǎn)的順序(即n5、n6、n7、n8)依次進(jìn)行的。實(shí)際上，我們還可以采用其它順序(如自下而上)重寫(xiě)，只要其中的任何一個(gè)內(nèi)部結(jié)點(diǎn)是在其后繼結(jié)點(diǎn)之后被重寫(xiě)并且轉(zhuǎn)移語(yǔ)句(如果有的話)仍然是基本塊的最后一個(gè)語(yǔ)句即可。5.1.4DAG構(gòu)造算法的進(jìn)一步討論當(dāng)基本塊中有數(shù)組元素引用、指針和過(guò)程調(diào)用時(shí)，構(gòu)造DAG算法就較為復(fù)雜。例如，考慮如下的基本塊G：

(1)?x=a[i]

(2)?a[j]=y

(3)?z=a[i]如果我們用構(gòu)造DAG的算法來(lái)構(gòu)造上述基本塊的DAG，則a[i]就是一個(gè)公共子表達(dá)式；且由所構(gòu)造的DAG重寫(xiě)出優(yōu)化后的四元式序列G'如下：

(1)?x=a[i]

(2)?z=x

(3)?a[j]=y如果i≠j，則G與G'是等效的。但是，如果i=j且y≠a[i]，則將y值賦給a[j]的同時(shí)也改變了a[i]的值(因i=j)；這時(shí)z值應(yīng)為改變后的a[i]值(即y值)，與x不等。為了避免這種情況的發(fā)生，當(dāng)我們構(gòu)造對(duì)數(shù)組a的元素賦值句的結(jié)點(diǎn)時(shí)，就“注銷”所有標(biāo)記為[?]且左邊變量是a(可加上或減去一個(gè)常數(shù))的結(jié)點(diǎn)。我們認(rèn)為對(duì)這樣的結(jié)點(diǎn)再添加附加標(biāo)識(shí)符是非法的，從而取消了它作為公共子表達(dá)式的資格。對(duì)指針賦值語(yǔ)句*p=w(其中p是一個(gè)指針)也會(huì)產(chǎn)生同樣的問(wèn)題，如果我們不知道p可能指向哪一個(gè)變量，那么就認(rèn)為它可能改變基本塊中任何一個(gè)變量的值。當(dāng)構(gòu)造這種賦值句的結(jié)點(diǎn)時(shí)，就需要把DAG各結(jié)點(diǎn)上的所有標(biāo)識(shí)符(包括作為葉結(jié)點(diǎn)上標(biāo)記的標(biāo)識(shí)符)都予以注銷，這也就意味著DAG中所有的結(jié)點(diǎn)也都被注銷。在一個(gè)基本塊中的一個(gè)過(guò)程調(diào)用將注銷所有的結(jié)點(diǎn)，因?yàn)閷?duì)被調(diào)用過(guò)程的情況缺乏了解，所以我們必須假定任何變量都可能因產(chǎn)生副作用而發(fā)生變化。此外，當(dāng)把DAG重寫(xiě)成四元式時(shí)，如果我們不是按照原來(lái)構(gòu)造DAG結(jié)點(diǎn)的順序進(jìn)行重寫(xiě)，那么DAG中的某些結(jié)點(diǎn)必須遵守一定的順序。例如，在上述基本塊G中，z=a[i]必須跟在a[j]=y之后，而a[j]=y則必須跟在x=a[i]之后。下面，我們根據(jù)上述討論把重寫(xiě)四元式時(shí)DAG中結(jié)點(diǎn)間必須遵守的順序歸納如下：

(1)對(duì)數(shù)組a中任何元素的引用或賦值，都必須跟在原來(lái)位于其前面的(如果有的話，下同)對(duì)數(shù)組a任何元素的賦值之后；對(duì)數(shù)組a任何元素的賦值，都必須跟在原來(lái)位于其前面的對(duì)數(shù)組a任何元素的引用之后。

(2)對(duì)任何標(biāo)識(shí)符的引用或賦值，都必須跟在原來(lái)位于其前面的任何過(guò)程調(diào)用或通過(guò)指針的間接賦值之后；任何過(guò)程調(diào)用或通過(guò)指針的間接賦值，都必須跟在原來(lái)位于其前面的任何標(biāo)識(shí)符的引用或賦值之后?？傊?，當(dāng)對(duì)基本塊重寫(xiě)時(shí)，任何數(shù)組a的引用不允許互相調(diào)換次序，并且任何語(yǔ)句不得跨越一個(gè)過(guò)程調(diào)用語(yǔ)句或者通過(guò)指針的間接賦值。5.2循環(huán)優(yōu)化5.2.1程序流圖與循環(huán)為了進(jìn)行循環(huán)優(yōu)化，必須先找出程序中的循環(huán)。由程序語(yǔ)言的循環(huán)語(yǔ)句形成的循環(huán)是不難找出的，但由條件轉(zhuǎn)移語(yǔ)句和無(wú)條件轉(zhuǎn)移語(yǔ)句同樣可以形成程序中的循環(huán)，并且其結(jié)構(gòu)可能更加復(fù)雜。因此，為了找出程序中的循環(huán)，就需要對(duì)程序中的控制流程進(jìn)行分析。我們應(yīng)用程序的控制流程圖來(lái)給出循環(huán)的定義并找出程序中的循環(huán)。一個(gè)控制流程圖(簡(jiǎn)稱流圖)就是具有惟一首結(jié)點(diǎn)的有向圖。所謂首結(jié)點(diǎn)，就是從它開(kāi)始到控制流程圖中任何一個(gè)結(jié)點(diǎn)都有一條通路的結(jié)點(diǎn)。我們可以把控制流程圖表示成一個(gè)三元組G=(N,E,n0)；其中，N代表圖中所有結(jié)點(diǎn)集，E代表圖中所有有向邊集，n0代表首結(jié)點(diǎn)。一個(gè)程序可用一個(gè)流圖來(lái)表示。流圖的有限結(jié)點(diǎn)集N就是程序的基本塊集，流圖中的結(jié)點(diǎn)就是程序的基本塊，流圖的首結(jié)點(diǎn)就是包含程序第一個(gè)語(yǔ)句的基本塊。流圖的有向邊集E是這樣構(gòu)成的：假設(shè)流圖中結(jié)點(diǎn)i和結(jié)點(diǎn)j分別對(duì)應(yīng)于程序的基本塊i和基本塊j，則當(dāng)下述條件有一個(gè)成立時(shí)，從結(jié)點(diǎn)i有一條有向邊引到結(jié)點(diǎn)j：

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

(2)基本塊i的出口語(yǔ)句是goto(s)或if…goto(s)，并且(s)是基本塊j的入口語(yǔ)句。在以后的討論中，我們所涉及的流圖都是程序流圖。程序流圖和基本塊的DAG是不同的概念。程序流圖是對(duì)整個(gè)程序而言的，它表示了各基本塊(對(duì)應(yīng)流圖中的一個(gè)結(jié)點(diǎn))之間的控制關(guān)系，圖中可以出現(xiàn)環(huán)路；DAG是對(duì)基本塊而言的，是局限于該基本塊內(nèi)的無(wú)環(huán)路有向圖，它表示了這個(gè)基本塊內(nèi)各四元式的操作及相互關(guān)系。我們?nèi)砸韵旅媲笞畲蠊蜃拥娜刂反a程序?yàn)槔齺?lái)求其程序流圖：

(1)?readX

(2)?readY

(3)?R=X%Y

(4)?ifR=0goto(8)

(5)?X=Y

(6)?Y=R

(7)?goto(3)

(8)?writeY

(9)?halt我們知道，該程序的基本塊分別為(1)(2)，(3)(4)，(5)(6)(7)和(8)(9)。按構(gòu)造流圖結(jié)點(diǎn)間有向邊的方法，我們得到該程序的程序流圖如圖5–3所示。圖5–3求最大公因子的程序流圖有了程序流圖，我們就可以對(duì)所要討論的循環(huán)結(jié)構(gòu)給出定義。在程序流圖中，我們稱具有下列性質(zhì)的結(jié)點(diǎn)序列為一個(gè)循環(huán)：

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

(2)它們中間有一個(gè)而且只有一個(gè)是入口結(jié)點(diǎn)。所謂入口結(jié)點(diǎn)，是指序列中具有下述性質(zhì)的結(jié)點(diǎn)：從序列外某結(jié)點(diǎn)有一條有向邊引到它，或者它就是程序流圖的首結(jié)點(diǎn)。注意：此處定義的循環(huán)就是程序流圖中具有惟一入口結(jié)點(diǎn)的強(qiáng)連通子圖。從循環(huán)外要進(jìn)入循環(huán)，必須先經(jīng)過(guò)循環(huán)的入口結(jié)點(diǎn)。對(duì)于性質(zhì)(1)，任意兩個(gè)結(jié)點(diǎn)之間必有一條通路，即通路上的尾結(jié)點(diǎn)到首結(jié)點(diǎn)之間也有一條通路(實(shí)際上可認(rèn)為無(wú)首尾之分)，這就構(gòu)成了一個(gè)環(huán)形通路。該通路上的各結(jié)點(diǎn)都屬于該結(jié)點(diǎn)序列，即從通路上的任何結(jié)點(diǎn)開(kāi)始所構(gòu)成的序列都包含該通路上的所有結(jié)點(diǎn)，這仍然構(gòu)成了一個(gè)環(huán)形通路。因此，性質(zhì)(1)是任何一種循環(huán)結(jié)構(gòu)所必須具備的，否則該結(jié)點(diǎn)序列必有一部分是不可能反復(fù)執(zhí)行的。性質(zhì)(2)出于對(duì)循環(huán)優(yōu)化的考慮，當(dāng)需要把循環(huán)中某些代碼(如不隨循環(huán)反復(fù)執(zhí)行而改變的運(yùn)算)提到循環(huán)之外時(shí)，可以將代碼提到循環(huán)結(jié)構(gòu)的惟一入口結(jié)點(diǎn)的前面。例如，對(duì)圖5–3所示的程序流圖，由上述循環(huán)的定義可知，結(jié)點(diǎn)序列{B2，B3}是程序中的一個(gè)循環(huán)，其中，B2是循環(huán)的惟一入口結(jié)點(diǎn)。對(duì)圖5–4所示的程序流圖，結(jié)點(diǎn)序列{6}因其只有一個(gè)結(jié)點(diǎn)且有一有向邊引到自身，并且只有惟一的入口結(jié)點(diǎn)6，故是我們所定義的循環(huán)。而{2,3,4,5,6,7}中的任意兩個(gè)結(jié)點(diǎn)之間都存在通路(即為強(qiáng)連通)，且有惟一的入口結(jié)點(diǎn)2，故也是我們所定義的循環(huán)。此外，{4,5,6,7}也是強(qiáng)連通且有惟一入口結(jié)點(diǎn)4，雖然到入口結(jié)點(diǎn)4的有向邊不止一條，但仍然是我們所定義的循環(huán)。而{2,4}和{2,3,4}，它們雖然是強(qiáng)連通的，但卻存在兩個(gè)入口結(jié)點(diǎn)2、4，故不是我們所定義的循環(huán)。{4,5,7}和{4,6,7}也因其存在兩個(gè)入口結(jié)點(diǎn)4、7而不是我們所定義的循環(huán)。

圖5–4程序流圖5.2.2循環(huán)的查找我們已經(jīng)了解了我們所定義的循環(huán)，下面介紹由編譯程序來(lái)實(shí)現(xiàn)的循環(huán)查找。

1．必經(jīng)結(jié)點(diǎn)集為了找出程序流圖中的循環(huán)，需要分析流圖中結(jié)點(diǎn)的控制關(guān)系，為此我們引入必經(jīng)結(jié)點(diǎn)和必經(jīng)結(jié)點(diǎn)集的定義。在程序流圖中，對(duì)任意結(jié)點(diǎn)m和n，如果從流圖的首結(jié)點(diǎn)出發(fā)，到達(dá)n的任一通路都要經(jīng)過(guò)m，則稱m是n的必經(jīng)結(jié)點(diǎn)，記為m

DOMn；流圖中結(jié)點(diǎn)n的所有必經(jīng)結(jié)點(diǎn)的集合稱為結(jié)點(diǎn)n的必經(jīng)結(jié)點(diǎn)集，記為D(n)。顯然，循環(huán)的入口結(jié)點(diǎn)是循環(huán)中所有結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)；此外，對(duì)任何結(jié)點(diǎn)n來(lái)說(shuō)都有nDOMn。如果把DOM看作流圖結(jié)點(diǎn)集上定義的一個(gè)關(guān)系，則由定義容易看出它具有下述性質(zhì)：

(1)自反性：對(duì)流圖中任意結(jié)點(diǎn)a，都有aDOMa。

(2)傳遞性：對(duì)流圖中任意結(jié)點(diǎn)a、b、c，若存在aDOMb和bDOMc,?則必有aDOMc。

(3)反對(duì)稱性：若存在aDOMb和bDOMa，則必有a=b。因此，關(guān)系DOM是一個(gè)偏序關(guān)系，任何結(jié)點(diǎn)n的必經(jīng)結(jié)點(diǎn)集是一個(gè)有序集。例5.2

求圖5–4中流圖各結(jié)點(diǎn)的D(n)。

[解答]考察圖5–4的流圖并由必經(jīng)結(jié)點(diǎn)的定義容易看出：首結(jié)點(diǎn)1是所有結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)；結(jié)點(diǎn)2是除去結(jié)點(diǎn)1之外所有結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)；結(jié)點(diǎn)4是結(jié)點(diǎn)4、5、6、7的必經(jīng)結(jié)點(diǎn)；而結(jié)點(diǎn)3、5、6、7都只是其自身的必經(jīng)結(jié)點(diǎn)。因此，直接由定義和DOM的性質(zhì)可求得：

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}下面我們給出求流圖G=(N，E，n0)的所有結(jié)點(diǎn)n的必經(jīng)結(jié)點(diǎn)集D(n)的算法；其中，P(n)代表結(jié)點(diǎn)n的前驅(qū)結(jié)點(diǎn)集，它可以從邊集E中直接求出。D(n0)

={n0};for(

n∈N?{n0}

)D(n)

=N;//置初值change=true;while(

change

){change=false;

for(

n∈N?{n0}

){new={n};if(

new!=D(n)

){change=true;D(n)

=new;}}}注意：由于算法中是利用所有前驅(qū)信息進(jìn)行∩運(yùn)算來(lái)獲得某結(jié)點(diǎn)對(duì)應(yīng)的必經(jīng)結(jié)點(diǎn)集的，因此迭代初值D(ni)必須取最大值，即全集N。此外，由知表示結(jié)點(diǎn)n的所有前驅(qū)(即父結(jié)點(diǎn))的必經(jīng)結(jié)點(diǎn)集的交集即為n的必經(jīng)結(jié)點(diǎn)集。由圖5–5可看出，ni為nj的必經(jīng)結(jié)點(diǎn)(ni為結(jié)點(diǎn)nj所有前驅(qū)nk1～nkn必經(jīng)結(jié)點(diǎn)集的交集)，而nk1～nkn都不是nj的必經(jīng)結(jié)點(diǎn)。另一點(diǎn)要說(shuō)明的是，因程序流圖中有循環(huán)情況，所以后面計(jì)算的結(jié)點(diǎn)其必經(jīng)結(jié)點(diǎn)集D(nj)的改變可能要影響到前面所計(jì)算的D(ni)值。因此，在一次迭代計(jì)算結(jié)束時(shí)，只要發(fā)現(xiàn)某一個(gè)D(nk)被改變，就必須進(jìn)行下一次迭代來(lái)計(jì)算各結(jié)點(diǎn)的D(n)(即算法中的while循環(huán)繼續(xù)執(zhí)行)，直至全部結(jié)點(diǎn)的D(n)都不改變?yōu)橹?即算法中的change值為false才結(jié)束算法的執(zhí)行)。

圖5–5ni為nj的必經(jīng)結(jié)點(diǎn)示意例5.3

應(yīng)用求流圖必經(jīng)結(jié)點(diǎn)集的算法求圖5–4所示程序流圖各結(jié)點(diǎn)n的D(n)。

[解答]算法求解過(guò)程如下：首先置初值： D(1)={1}? D(2)=D(3)=D(4)=D(5)=D(6)=D(7) ={1,2,3,4,5,6,7}置change為false，然后從結(jié)點(diǎn)2到結(jié)點(diǎn)7依次執(zhí)行第二個(gè)for循環(huán)。對(duì)結(jié)點(diǎn)2，因new={2}∪D(1)∩D(4)={2}∪{1}∩{1,2,3,4,5,6,7}

={2}∪{1}={1,2}但迭代前D(2)={1,2,3,4,5,6,7}，故D(2)≠new，因此置change=true并令D(2)={1,2}。對(duì)結(jié)點(diǎn)3，因new={3}∪D(2)={3}∪{1,2}={1,2,3}但迭代前D(3)={1,2,3,4,5,6,7}，故D(3)≠new，因此令D(3)={1,2,3}。其余各結(jié)點(diǎn)按照上述步驟可求出：D(4)={4}∪D(2)∩D(3)∩D(7)={4}∪{1,2}∩{1,2,3}∩{1,2,3,4,5,6,7}={1,2,4}D(5)={5}∪D(4)={1,2,4,5}D(6)={6}∪D(4)={1,2,4,6}D(7)={7}∪D(5)∩D(6)={7}∪{1,2,4,5}∩{1,2,4,6}={1,2,4,7}一次迭代完畢后，因change為true，故還要進(jìn)行下一次迭代。先令change為false，然后繼續(xù)從結(jié)點(diǎn)2到結(jié)點(diǎn)7依次執(zhí)行第二個(gè)for循環(huán)。對(duì)結(jié)點(diǎn)2，因

new={2}∪D(1)∩D(4)={2}∪{1}∩{1,2,4}

={2}∪{1}={1,2}而迭代前D(2)={1,2}，所以D(2)=new，故D(2)不變。對(duì)結(jié)點(diǎn)3，因new={3}∪D(2)={3}∪{1,2}={1,2,3}及迭代前D(3)={1,2,3}，所以D(3)=new，故D(3)不變。對(duì)其余結(jié)點(diǎn)n(n=4～7)求出的new均有D(n)=new，所以第二次迭代后change為false，迭代結(jié)束，第一次迭代求出的各個(gè)D(n)就是最后的結(jié)果。

2．回邊查找循環(huán)的方法是：首先應(yīng)用必經(jīng)結(jié)點(diǎn)集來(lái)求出流圖中的回邊，然后利用回邊找出流圖中的循環(huán)?；剡叺亩x如下：假設(shè)a→b是流圖中一條有向邊，如果bDOMa，則稱a→b是流圖中的一條回邊。對(duì)于一已知流圖G，只要求出各結(jié)點(diǎn)n的必經(jīng)結(jié)點(diǎn)集，就可以立即求出流圖中的所有回邊。在求出流圖G中的所有回邊后，就可以求出流圖中的循環(huán)。如果已知有向邊n→d是一條回邊，則由它組成的循環(huán)就是由結(jié)點(diǎn)d、結(jié)點(diǎn)n以及有通路到達(dá)n但該通路不經(jīng)過(guò)d的所有結(jié)點(diǎn)組成的。例5.4

求出圖5–4所示程序流圖的所有回邊。

[解答](1)已知D(6)={1,2,4,6}，因存在6→6且6DOM6，故6→6是回邊；

(2)已知D(7)={1,2,4,7}，因存在7→4且4DOM7，故7→4是回邊；

(3)已知D(4)={1,2,4}，因存在4→2且2DOM4，故4→2是回邊。容易看出，其它有向邊都不是回邊。尋找由回邊組成循環(huán)的算法如下：voidmain(?){stack=空; //stack是一個(gè)工作棧

loop=97rfjzt; //loop是所求的循環(huán)

insert(?m?);while(?stack非空?){

彈出stack棧頂元素m;for(?p∈P(?m?)?) //P(?m?)為結(jié)點(diǎn)m的前驅(qū)結(jié)點(diǎn)集

insert(?p?);}}voidinsert(?m?){if(?mloop?){loop=loop∪{m};把m壓入棧stack;}}此算法中求回邊n→d組成循環(huán)的所有結(jié)點(diǎn)的方法是：由于循環(huán)以d為其惟一入口，n是循環(huán)的一個(gè)出口，因而只要n不同時(shí)是循環(huán)入口d，那么n的所有前驅(qū)就應(yīng)屬于循環(huán)。在求出n的所有前驅(qū)之后，只要它們不是循環(huán)入口d，就應(yīng)再繼續(xù)求出它們的前驅(qū)，而這些新求出的所有前驅(qū)也應(yīng)屬于循環(huán)。然后再對(duì)新求出的所有前驅(qū)重復(fù)上述過(guò)程，直到所求出的前驅(qū)都是d為止。

3．可歸約流圖一個(gè)流圖被稱為可歸約的，當(dāng)且僅當(dāng)流圖中除去回邊之外，其余的邊構(gòu)成一個(gè)無(wú)環(huán)路流圖。例如，圖5–4中的流圖就是一個(gè)可歸約流圖，而圖5–6則是一個(gè)不可歸約流圖，因?yàn)閳D5–6中雖然有2→3，但沒(méi)有3DOM2，即2→3不是一個(gè)回邊，對(duì)3→2也是如此。如果程序流圖是可歸約的，那么程序中任何可能反復(fù)執(zhí)行的代碼都會(huì)被求回邊的算法納入到一個(gè)循環(huán)當(dāng)中。圖5–6不可歸約流圖可歸約流圖是一類非常重要的流圖，從代碼優(yōu)化的角度來(lái)說(shuō)，它具有下述重要的性質(zhì)：

(1)圖中任何直觀意義下的環(huán)路都屬于我們所定義的循環(huán)。

(2)只要找出圖中的所有回邊，對(duì)回邊應(yīng)用查找循環(huán)的方法，就可以找出流圖中的所有循環(huán)。

(3)圖中任意兩個(gè)循環(huán)要么嵌套，要么不相交(除了可能有公共的入口結(jié)點(diǎn))，對(duì)這類流圖進(jìn)行循環(huán)優(yōu)化較為容易。應(yīng)用結(jié)構(gòu)程序設(shè)計(jì)原則寫(xiě)出的程序，其流圖總是可歸約的；而應(yīng)用高級(jí)語(yǔ)言寫(xiě)出的程序，其流圖往往也是可歸約的。例5.5

四元式序列如下：

(1) J=0；

(2)L1： I=0；

(3) ifI<8gotoL3;

(4)L2： A=B+C；

(5) B=D*C;

(6)L3： ifB=0gotoL4;

(7) writeB;

(8) gotoL5;

(9)L4： I=I+1;

(10) ifI<8gotoL2;

(11)L5： J=J+1;

(12) if

J≤3gotoL1;

(13) halt畫(huà)出該四元式序列的程序流圖G并求出G中的回邊與循環(huán)。

[解答]該四元式序列的基本塊與程序流圖如圖5–7所示。由求流圖G的所有結(jié)點(diǎn)n的必經(jīng)結(jié)點(diǎn)集D(n)?的算法可知，初始時(shí)D(B1)?～D(B8)?為全集：{B1,?B2,?B3,?B4,?B5,?B6,?B7,?B8}，而各結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)集的求法是：必經(jīng)結(jié)點(diǎn)集D(Bi)?為{Bi}并上Bi所有前驅(qū)（即父結(jié)點(diǎn)）的必經(jīng)結(jié)點(diǎn)集的交集。對(duì)圖5-7（圖5-8）中各結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)集的求法如下：D(B1)?={B1}D(B2)?={B2}∪D(B1)∩D(B7)?={B2}∪{B1}∩{B1,?B2,?B3,?B4,?B5,?B6,?B7,?B8}={B1,?B2}D(B3)?={B3}∪D(B2)∩D(B6)?={B3}∪{B1,?B2}∩{B1,?B2,?B3,?B4,?B5,?B6,?B7,?B8}={B1,?B2,?B3}D(B4)?={B4}∪D(B2)∩D(B3)?={B4}∪{B1,?B2}∩{B1,?B2,?B3}={B1,?B2,?B4}D(B5)?={B5}∪D(B4)?={B1,?B2,?B4,?B5}D(B6)?={B6}∪D(B4)?={B1,?B2,?B4,?B6}D(B7)?={B7}∪D(B5)∩D(B6)?={B7}∪{B1,?B2,?B4,?B5}∩{B1,?B2,?B4,?B6}={B1,?B2,?B4,?B7}D(B8)?={B8}∪D(B7)?={B8}∪{B1,?B2,?B4,?B7}={B1,?B2,?B4,?B7,?B8}考察流圖中的有向邊B7→B2且已知D(B7)?={B1,?B2,?B4,?B7}，所以有B2DOMB7，即B7→B2是流圖中的回邊。容易看出，其它有向邊都不是回邊。因B7→B2是一條回邊，則在流圖中能夠不經(jīng)過(guò)結(jié)點(diǎn)B2且有通路到達(dá)結(jié)點(diǎn)B7的結(jié)點(diǎn)只有B3、B4、B5和B6，故由回邊B7→B2組成的循環(huán)是：{B2,

B3,

B4,

B5,

B6,

B7}。圖5–7例5.5的程序流圖B1B2B3B4B5B6B7B8圖5-8例5.5結(jié)點(diǎn)形式的程序流圖5.2.3循環(huán)優(yōu)化對(duì)循環(huán)中的代碼可以實(shí)行代碼外提、強(qiáng)度削弱和刪除歸納變量等優(yōu)化。

1．代碼外提循環(huán)中的代碼要隨著循環(huán)反復(fù)執(zhí)行，但其中某些運(yùn)算的結(jié)果并不因循環(huán)而改變，對(duì)于這種不隨循環(huán)變化的運(yùn)算，可以將其外提到循環(huán)外。這樣，程序的運(yùn)行結(jié)果仍保持不變，但程序的運(yùn)行效率卻提高了。我們稱這種優(yōu)化為代碼外提。實(shí)行代碼外提時(shí)，在循環(huán)入口結(jié)點(diǎn)前面建立一個(gè)新結(jié)點(diǎn)(基本塊)，稱為循環(huán)的前置結(jié)點(diǎn)。循環(huán)前置結(jié)點(diǎn)以循環(huán)入口結(jié)點(diǎn)為其惟一后繼，原來(lái)流圖中從循環(huán)外引到循環(huán)入口結(jié)點(diǎn)的有向邊改成引到循環(huán)前置結(jié)點(diǎn)，如圖5–9所示。圖5–9給循環(huán)建立前置結(jié)點(diǎn)因?yàn)樵谖覀兯x的循環(huán)結(jié)構(gòu)中，其入口結(jié)點(diǎn)是惟一的，所以前置結(jié)點(diǎn)也是惟一的。循環(huán)中外提的代碼將統(tǒng)統(tǒng)外提到前置結(jié)點(diǎn)中。但是，循環(huán)中的不變運(yùn)算并不是在任何情況下都可以外提的。對(duì)循環(huán)L中的不變運(yùn)算S：A=BopC或A=opB或A=B，要求滿足下述條件(A在離開(kāi)L后仍是活躍的)：

(1)?S所在的結(jié)點(diǎn)是L的所有出口結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)；

(2)?A在L中其它地方未再定值；

(3)?L中的所有A的引用點(diǎn)只有S中A的定值才能到達(dá)。圖5–10代碼外提的程序流圖示例

對(duì)上述三個(gè)條件，我們給出圖5–10所示的三種流圖予以說(shuō)明。

(1)對(duì)圖5–10(a)，先將B3中的循環(huán)不變運(yùn)算I=2外提到循環(huán)前置結(jié)點(diǎn)B2'中，如圖5–11所示。由圖5–10(a)可知，B3并不是出口結(jié)點(diǎn)B4的必經(jīng)結(jié)點(diǎn)。如果令X=30，Y=25，則按圖5–10(a)的程序流圖，B3是不會(huì)執(zhí)行的；于是，當(dāng)執(zhí)行到B5時(shí)，I的值是1。但是，如果按圖5–11執(zhí)行，則執(zhí)行到B5時(shí)，I的值總是2，因此圖5–11改變了原來(lái)程序運(yùn)行的結(jié)果。出現(xiàn)以上問(wèn)題是因?yàn)锽3不是循環(huán)出口結(jié)點(diǎn)B4的必經(jīng)結(jié)點(diǎn)，因此當(dāng)把一不變運(yùn)算外提到循環(huán)前置結(jié)點(diǎn)時(shí)，要求該不變運(yùn)算所在的結(jié)點(diǎn)是循環(huán)所有出口結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)。

圖5–11將圖5–9(a)中的I=2外提后的程序流圖

(2)考查圖5–10(b)，現(xiàn)在I=3所在的結(jié)點(diǎn)B2是循環(huán)出口結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)，但循環(huán)中除B2外，B3也對(duì)I定值。如果把B2中的I=3外提到循環(huán)前置結(jié)點(diǎn)中，且循環(huán)前X=21和Y=22，程序此時(shí)執(zhí)行的順序是B2→B3→B4→B2→B4→B5，則到達(dá)B5時(shí)I值為2；但如果不把B2中的I=3外提，則經(jīng)過(guò)以上執(zhí)行順序到達(dá)B5時(shí)，I值為3。由此可知，當(dāng)把循環(huán)中的不變運(yùn)算A=BopC外提時(shí)，要求循環(huán)中其它地方不再有A的定值點(diǎn)。

(3)考查圖5–10(c)，不變運(yùn)算I=2所屬結(jié)點(diǎn)B4本身就是出口結(jié)點(diǎn)，而且此循環(huán)只有一個(gè)出口結(jié)點(diǎn)，同時(shí)循環(huán)中除B4外其它地方?jīng)]有I的定值點(diǎn)；因此，它滿足外提的條件(1)、(2)。我們注意到，對(duì)循環(huán)中B3的I的引用點(diǎn)，不僅B4中I的定值能夠到達(dá)，而且B1中I的定值也能到達(dá)。現(xiàn)在考慮進(jìn)入循環(huán)前X=0和Y=2時(shí)的情況，此時(shí)循環(huán)的執(zhí)行順序?yàn)锽2→B3→B4→B2→B4→B5，當(dāng)?shù)竭_(dá)B5時(shí)A值為2；但如果把B4中的I=2外提，則到達(dá)B5時(shí)A值為3。因此當(dāng)把循環(huán)不變運(yùn)算A=BopC外提時(shí)，要求循環(huán)中A的所有引用點(diǎn)都是而且僅僅是該定值所能到達(dá)的。根據(jù)以上討論，給出查找所需處理的循環(huán)L中的不變運(yùn)算和代碼外提的算法如下：

(1)依次查看L中各基本塊的每個(gè)四元式，如果它的每個(gè)運(yùn)算對(duì)象為常數(shù)或者定值點(diǎn)在L外，則將此四元式標(biāo)記為“不變運(yùn)算”。

(2)依次查看尚未被標(biāo)記為“不變運(yùn)算”的四元式，如果它的每個(gè)運(yùn)算對(duì)象為常數(shù)或定值點(diǎn)在L之外，或只有一個(gè)到達(dá)一定值點(diǎn)且該點(diǎn)上的四元式已標(biāo)記為“不變運(yùn)算”，則把被查看的四元式標(biāo)記為“不變運(yùn)算”。

(3)重復(fù)第(2)步直至沒(méi)有新的四元式被標(biāo)記為“不變運(yùn)算”為止。例如，循環(huán)中的A=3已標(biāo)記為“不變運(yùn)算”，則對(duì)循環(huán)中A=3定值點(diǎn)可惟一到達(dá)的X=A+2也標(biāo)記為“不變運(yùn)算”。找出了循環(huán)的不變運(yùn)算就可以進(jìn)行代碼外提了。代碼外提算法如下：

(1)求出循環(huán)L的所有不變運(yùn)算。

(2)對(duì)步驟(1)所求得的每一不變運(yùn)算S：A=BopC或A=opB或A=B，檢查它是否滿足以下條件：①i.??S所在的結(jié)點(diǎn)是L的所有出口結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)；

ii.?A在L中其它地方未再定值；

iii.L中所有A的引用點(diǎn)只有S中A的定值才能到達(dá)。②A在離開(kāi)L后不再是活躍的(即離開(kāi)L后不會(huì)引用該A值)，并且條件①的ii.和iii.兩條成立。所謂A在離開(kāi)L后不再是活躍的，是指A在L的任何出口結(jié)點(diǎn)的后繼結(jié)點(diǎn)(當(dāng)然是指那些不屬于L的后繼)的入口處不是活躍的。

(3)按步驟(1)所找出的不變運(yùn)算的順序，依次把步驟(2)中滿足條件的不變運(yùn)算S外提到L的前置結(jié)點(diǎn)中。但是，如果S的運(yùn)算對(duì)象(B或C)是在L中定值的，那么只有當(dāng)這些定值四元式都已外提到前置結(jié)點(diǎn)中時(shí)，才可把S也外提到前置結(jié)點(diǎn)中(B、C的定值四元式提到前置結(jié)點(diǎn)后，S的運(yùn)算對(duì)象B、C就屬于定值點(diǎn)在L之外了，因此也就是真正的“不變運(yùn)算”了)。

注意：如果把滿足條件(2)②的不變運(yùn)算A=BopC外提到前置結(jié)點(diǎn)中，則執(zhí)行完循環(huán)后得到的A值可能與不進(jìn)行外提的情形所得的A值不同，但因?yàn)殡x開(kāi)循環(huán)后不會(huì)引用該A值，所以這不影響程序的運(yùn)行結(jié)果。例5.6

試對(duì)圖5–12給定的程序流圖進(jìn)行代碼外提優(yōu)化。

[解答]確定不變運(yùn)算的原則是依次查看循環(huán)中各基本塊的每個(gè)四元式，如果它的每個(gè)運(yùn)算對(duì)象為常數(shù)或者定值點(diǎn)在循環(huán)外，則將此四元式標(biāo)記為“不變運(yùn)算”。查看圖5–12所示的程序流圖，可以找出的不變運(yùn)算是B3中的I=2和B4中的J=M+N。進(jìn)行代碼外提時(shí)，只能將J=M+N提到循環(huán)前置結(jié)點(diǎn)。因?yàn)锽3中的I=2雖然是不變運(yùn)算，但B3不是循環(huán)所有出口結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)，且循環(huán)中所有I的引用點(diǎn)并非只有B3的I定值能夠到達(dá)，故B3中的I=2不能外提。最后，得到代碼外提后的程序流圖如圖5–12所示。圖5–12例5.6的程序流圖

圖5–13代碼外提后的程序流圖

2．強(qiáng)度削弱強(qiáng)度削弱是指把程序中執(zhí)行時(shí)間較長(zhǎng)的運(yùn)算替換為執(zhí)行時(shí)間較短的運(yùn)算。強(qiáng)度削弱不僅可對(duì)乘法運(yùn)算實(shí)行(將循環(huán)中的乘法運(yùn)算用遞歸加法運(yùn)算來(lái)替換)，對(duì)加法運(yùn)算也可實(shí)行。如果循環(huán)中有I的遞歸賦值I=I±C(C為循環(huán)不變量)，并且循環(huán)中T的賦值運(yùn)算可化歸為T=K*I±C1(K和C1為循環(huán)不變量)，那么T的賦值運(yùn)算可以進(jìn)行強(qiáng)度削弱。進(jìn)行強(qiáng)度削弱后，循環(huán)中可能出現(xiàn)一些新的無(wú)用賦值，如果它們?cè)谘h(huán)出口之后不是活躍變量則可以從循環(huán)中刪除。此外，對(duì)下標(biāo)變量地址計(jì)算來(lái)說(shuō)，強(qiáng)度削弱實(shí)際就是實(shí)現(xiàn)下標(biāo)變量地址的遞歸計(jì)算。例5.7

試對(duì)圖5–14給定的程序流圖進(jìn)行強(qiáng)度削弱優(yōu)化。

[解答]由圖5–14所示的流圖可以看出，B2中的A=K*I和B=J*I因計(jì)算K、J的四元式都在循環(huán)之外，故可將K、J看作常量，而每次循環(huán)I=I+1即I增加1時(shí)，對(duì)應(yīng)A=K*I和B=J*I分別增加K和J。因此，可以將A=K*I和B=J*I外提到前置結(jié)點(diǎn)中，同時(shí)在B2的I=I+1之后分別給A和B增加一個(gè)常量K和J。進(jìn)行強(qiáng)度削弱后的流圖如圖5–15所示。圖5–14例5.7的程序流圖

圖5–15例5.7強(qiáng)度削弱后的流圖

例5.8

試對(duì)圖5–16給定的程序流圖進(jìn)行強(qiáng)度削弱優(yōu)化。圖5–16例5.8的程序流圖

[解答]強(qiáng)度削弱不僅可對(duì)乘法運(yùn)算進(jìn)行，也可對(duì)加法運(yùn)算進(jìn)行。由于本題中的四元式程序不存在乘法運(yùn)算，所以只能進(jìn)行加法運(yùn)算的強(qiáng)度削弱。從圖5–16中可以看到，B2中的C=B+I，B的定值點(diǎn)在循環(huán)之外，故相當(dāng)于常數(shù)；而另一加數(shù)I值由B3中的I=I+1決定，即每循環(huán)一次I值增1，也即每循環(huán)一次，B2中C=B+I的C值增量與B3中的I相同，為常數(shù)1。因此，我們可以對(duì)C進(jìn)行強(qiáng)度削弱，即將B2中的四元式C=B+I外提到前置結(jié)點(diǎn)B2'中，同時(shí)在B3中I=I+1之后給C增加一個(gè)常量1。進(jìn)行強(qiáng)度削弱后的結(jié)果如圖5–17所示。圖5–17例5.8強(qiáng)度削弱后的流圖

例5.9

試對(duì)圖5-18給定的程序流圖進(jìn)行強(qiáng)度削弱優(yōu)化。

[解答]由圖5–18的B3看到，T2是遞歸賦值的變量，每循環(huán)一次增加一個(gè)常量10。因T3=T2+T1，計(jì)算T3值時(shí)要引用T2的值，它的另一運(yùn)算對(duì)象是循環(huán)不變量T1，所以每循環(huán)一次，T3值的增量與T2相同，即常數(shù)10。因此，我們可以對(duì)T3進(jìn)行強(qiáng)度削弱，即將T3=T2+T1外提到前置結(jié)點(diǎn)B2'中，同時(shí)在T2=T2+10的后面給T3增加一個(gè)常量10。進(jìn)行以上強(qiáng)度削弱后的結(jié)果如圖5–19所示。圖5–18例5.9的程序流圖

圖5–19例5.9強(qiáng)度削弱后的程序流圖

3．刪除歸納變量如果循環(huán)中對(duì)變量I只有惟一的形如I=I±C的賦值，且其中C為循環(huán)不變量，則稱I為循環(huán)中的基本歸納變量。如果I是循環(huán)中一基本歸納變量，J在循環(huán)中的定值總是可化歸為I的同一線性函數(shù)，也即J=C1*I±C2，其中C1和C2都是循環(huán)不變量，則稱J是歸納變量，并稱它與I同族。一個(gè)基本歸納變量也是一歸納變量。一個(gè)基本歸納變量除用于其自身的遞歸定值外，往往只在循環(huán)中用來(lái)計(jì)算其它歸納變量以及控制循環(huán)的進(jìn)行。此時(shí)，可以用同族的某一歸納變量來(lái)替換循環(huán)控制條件中的這個(gè)基本歸納變量，從而達(dá)到將這個(gè)基本歸納變量從程序流圖中刪去的目的。這種優(yōu)化稱為刪除歸納變量或變換循環(huán)控制條件。由于刪除歸納變量是在強(qiáng)度削弱以后進(jìn)行的，因此，我們一并給出強(qiáng)度削弱和刪除歸納變量的算法如下：

(1)利用循環(huán)不變運(yùn)算信息，找出循環(huán)中所有的基本歸納變量。

(2)找出所有其它歸納變量A，并找出A與已知基本歸納變量X的同族線性函數(shù)關(guān)系FA(X)；即：①在L中找出形如A=B*C、A=C*B、A=B/C、A=B±C、A=C±B的四元式，其中B是歸納變量，C是循環(huán)不變量。②假設(shè)找出的四元式為S：A=C*B，這時(shí)有：

i.如果B就是基本歸納變量，則X就是B，A與基本歸納變量B是同族的歸納變量，且A與B的函數(shù)關(guān)系就是FA(B)=C*B。

ii.如果B不是基本歸納變量，假設(shè)B與基本歸納變量D同族且它們的函數(shù)關(guān)系為FB(D)，那么如果L外B的定值點(diǎn)不能到達(dá)S且L中B的定值點(diǎn)與S之間未曾對(duì)D定值，則X就是D，A與基本歸納變量D是同族的歸納變量，且A與D的函數(shù)關(guān)系是FA(D)=C*B=

C*FB(D)。

(5)?(刪除基本歸納變量)如果基本歸納變量B在循環(huán)出口之后不是活躍的，并且在循環(huán)中除在其自身的遞歸賦值中被引用外，只在形為ifBropYgotoZ(或ifYropBgotoZ)中被引用，則：①選取一與B同族的歸納變量M，并設(shè)FM(B)=C1*B+C2(盡可能使所選M的FM(B)簡(jiǎn)單，并且可能的話，使M是循環(huán)中其它四元式要引用的或者是循環(huán)出口之后的活躍變量)。②建立一臨時(shí)變量R，并用下列四元式：

R=C1*Y//如果C1=1則C1不出現(xiàn)

R=R+C2//如果C2=0則無(wú)此四元式

ifFM(B)ropRgotoZ//或ifRropFM(B)gotoZ

來(lái)替換ifBropYgotoZ(或ifYropBgotoZ)，即將原判斷條件BropY改為(C1*B+C2)rop(C1*Y+C2)，也就是FM(B)ropR。③刪除循環(huán)中對(duì)B遞歸賦值的四元式。例5.10

試對(duì)圖5–15給定的程序流圖進(jìn)行刪除歸納變量?jī)?yōu)化。

[解答]由圖5–15可知，循環(huán)中I是基本歸納變量，A、B是與I同族的歸納變量且具有如下的線性關(guān)系：

A=K*I B=J*I

因此，循環(huán)控制條件I<100完全可用A<100*K或B<100*J來(lái)替代。這樣，基本塊B2中的控制條件和控制語(yǔ)句可改寫(xiě)為

T1=100*K ifA<T1gotoL或者改寫(xiě)為

T2=100*J ifA<T2gotoL此時(shí)的程序流圖如圖5–20所示。圖5–20變換循環(huán)控制條件的程序流圖

循環(huán)控制條件經(jīng)過(guò)以上改變之后，就可以刪除基本塊B2中的語(yǔ)句I=I+1；而語(yǔ)句T1=100*K是循環(huán)中的不變運(yùn)算，故可由基本塊B2外提到基本塊B2'中。最后，經(jīng)刪除歸納變量及代碼外提后得到的程序流圖如圖5–21所示。圖5–21刪除歸納變量及代碼外提后的程序流圖

5.3全局優(yōu)化概述

5.3.1到達(dá)-定值與引用-定值鏈為了進(jìn)行全局優(yōu)化，需要分析程序中所有變量的定值（即對(duì)變量賦值）和引用之間的關(guān)系。首先，我們介紹下面兩個(gè)重要概念：（1）到達(dá)-定值：所謂變量A在某點(diǎn)d的定值到達(dá)另一點(diǎn)p，是指程序流圖中從d有一通路到達(dá)p且該通路上沒(méi)有A的其它定值。（2）引用-定值鏈（簡(jiǎn)稱為ud鏈）：假設(shè)在程序中某點(diǎn)p引用了變量A的值，則把能夠到達(dá)p的A的所有定值點(diǎn)的全體，稱為A在引用點(diǎn)p的引用-定值鏈。

為了求出到達(dá)點(diǎn)p的各個(gè)變量的所有定值點(diǎn)，我們先對(duì)程序中所有基本塊B作如下定義：

IN[B]到達(dá)基本塊B入口之前的各個(gè)變量的所有定值點(diǎn)集；

OUT[B]到達(dá)基本塊B出口之后的各個(gè)變量的所有定值點(diǎn)集；

GEN[B]基本塊B中定值的并到達(dá)B出口之后的所有定值點(diǎn)集；

KILL[B]基本塊B外滿足下述條件的定值點(diǎn)集：這些定值點(diǎn)所定值的變量在B中已被重新定值。也即，GEN[B]?為基本塊B所“生成”的定值點(diǎn)集，KILL[B]?為被基本塊B“注銷”的定值點(diǎn)集；GEN[B]?和KILL[B]?均可從給定的程序流圖直接求出。

我們先對(duì)程序中的所有基本塊B求出其IN[B]；一旦求出所有基本塊B的IN[B]，就可按下述規(guī)則求出到達(dá)B中某點(diǎn)p的任一變量A的所有定值點(diǎn)：（1）如果B中p的前面有A的定值，則到達(dá)p的定值點(diǎn)是唯一的，它就是與p最靠近的那個(gè)A的定值點(diǎn)；（2）如果B中p的前面沒(méi)有A的定值，則到達(dá)p的A的所有定值點(diǎn)就是IN[B]?中A的那些定值點(diǎn)。怎樣求得IN[B]?和OUT[B]?呢？對(duì)于OUT[B]?容易看出：（1）如果定值點(diǎn)d在GEN[B]?中，那么它一定也在OUT[B]?中；（2）如果某定值點(diǎn)d在IN[B]?中且被d定值的變量在B中沒(méi)有被重新定值，則d也在OUT[B]?中；（3）除（1）、（2）外沒(méi)有其它定值點(diǎn)d能夠到達(dá)B的出口之后，即dOUT[B]。對(duì)于IN[B]?可以看出：某定值點(diǎn)d到達(dá)基本塊B的入口之前，當(dāng)且僅當(dāng)它到達(dá)B的某一前驅(qū)基本塊的出口之后。

綜上所述，我們可得到所有基本塊B的IN[B]?和OUT[B]?的計(jì)算公式：

OUT[B]?=IN[B]?-KILL[B]∪GEN[B]IN[B]?=

在此，P[B]?代表B的所有前驅(qū)基本塊（即B的父結(jié)點(diǎn)）的集合；OUT[B]?意為：所有進(jìn)入B前并在B中沒(méi)有被修改過(guò)的某變量定值點(diǎn)集與B中所“生成”的該變量定值點(diǎn)集的并集，即先計(jì)算IN[B]?-KILL[B]，然后再與GEN[B]?相“∪”。由于所有GEN[B]?和KILL[B]?可以從給定的程序流圖中直接求出，故上式是變量IN[B]?和OUT[B]?的線性聯(lián)立方程并被稱之為到達(dá)-定值數(shù)據(jù)流方程。設(shè)程序流圖含有n個(gè)結(jié)點(diǎn)，則到達(dá)-定值數(shù)據(jù)流方程可用下述迭代算法求解。（1）for(?i=1;?i<=n;?i++?)（2）{IN[Bi]?=φ;（3）OUT[Bi]?=GEN[Bi];}//置初值（4）change=true;（5）while(?change?)（6）{change=false;（7）for(?i=1;?i<=n;?i++?)（8）{NEWIN=;（9）if(?NEWIN!=IN[Bi]?)（10）{change=true;（11）IN[Bi]?=NEWIN;（12）OUT[Bi]?=(?IN[Bi]?-KILL[Bi]?)∪GEN[Bi];（13）}（14）}（15）}

在上述算法第（3）行中，如果不給OUT[Bi]?賦初值，則無(wú)法進(jìn)行后面的∪OUT[p]?計(jì)算（結(jié)果總為φ），這將使得IN[Bi]?計(jì)算沒(méi)有變化（始終為φ）；所以，必須先給OUT[Bi]?賦初值，而這個(gè)初值只能是基本塊Bi所產(chǎn)生的GEN[Bi]。在第(7)行中，我們按程序流圖中各結(jié)點(diǎn)的深度為主次序依次計(jì)算各基本塊的IN和OUT。change是用來(lái)判斷結(jié)束的布爾變量；NEWIN是集合變量，對(duì)每一基本塊Bi如果前后兩次迭代計(jì)算出的NEWIN值不等，則置change為true，表示尚需進(jìn)行下一次迭代；這是因?yàn)槌绦蛑锌赡艽嬖谥h(huán)，即后面結(jié)點(diǎn)（基本塊）IN和OUT的改變可能又影響到前面已計(jì)算過(guò)的結(jié)點(diǎn)之IN和OUT值；所以，只要出現(xiàn)某結(jié)點(diǎn)的IN和OUT發(fā)生變化的情況，迭代就得繼續(xù)下去。例5.11考察圖5-22所示的程序流圖，各四元式左邊的d分別代表該四元式的位置，假設(shè)只考慮變量i和j，求其到達(dá)-定值數(shù)據(jù)流方程的解。

【解】（1）我們先求出所有基本塊B的GEN[B]?和KILL[B]。GEN[B]?和KILL[B]?用位向量來(lái)表示，程序流圖中每一點(diǎn)d在向量中占一位；如果d屬于某個(gè)集，則該向量的相應(yīng)位為1，否則為0。由定義直接計(jì)算出的GEN[B]?和KILL[B]?值見(jiàn)表5.1。圖5-22程序流圖（2）圖5-23是圖5-22程序流圖的深度為主擴(kuò)展樹(shù)。各基本塊的深度為B1、B2、B3、B4、B5。根據(jù)上述迭代算法求解步驟如下：圖5-23深度為主擴(kuò)展樹(shù)首先置迭代初值：IN[B1]?=?IN[B2]?=?IN[B3]?=?IN[B4]?=?IN[B5]?=?0000000OUT[B1]?=GEN[B1]?=?1100000OUT[B2]?=GEN[B2]?=?0010000OUT[B3]?=?GEN[B3]?=?0001000OUT[B4]?=?GEN[B4]?=?0000100OUT[B5]?=?GEN[B5]?=?0000000按深度為主次序?qū)1、B2、B3、B4、B5執(zhí)行算法計(jì)算如下：對(duì)B1：用NEWIN=OUT[B2]?=?0010000?≠IN[B1]

所以change=trueIN[B1]?=?0010000OUT[B-1]?=?(?IN[B1]-KILL[B1]?)∪GEN[B1]?=IN[B1]KILL[B1]∪GEN[B1]=?0010000∧1100011∪1100000?=?0000000∪1100000=?1100000對(duì)B2：因NEWIN=OUT[B1]∪OUT[B5]?=?1100000∪0000000?=?1100000?≠IN[B2]故IN[B2]?=?1100000OUT[B2]?=?(?IN[B2]?-KILL[B2]?)∪GEN[B2]?=?0110000同理對(duì)B3：IN[B3]?=OUT[B2]?=?0110000OUT[B3]?=?(?IN[B3]?-KILL[B3]?)∪GEN[B3]?=?0011000B4：IN[B4]?=OUT[B3]?=?0011000OUT[B4]?=(?IN[B4]?-KILL[B4]?)∪GEN[B4]?=?0010100B5：IN[B5]?=OUT[B3]∪OUT[B4]?=?0011000∪0010100?=?0011100OUT[B5]?=(?IN[B5]?-KILL[B5]?)∪GEN[B5]?=?0011100各次迭代結(jié)果見(jiàn)表5.2，因第四次迭代計(jì)算出的結(jié)果與第三次迭代結(jié)果相同，故它就是最后所求的結(jié)果。

我們知道，程序流圖中IN[B2]?處為循環(huán)入口，迭代繼續(xù)的原因是后面結(jié)點(diǎn)計(jì)算出的IN和OUT又隨循環(huán)影響到前面結(jié)點(diǎn)的IN和OUT值，故在此只要兩次迭代的IN[B2]?不發(fā)生變化，就無(wú)需繼續(xù)迭代。在表5.2中，由于循環(huán)入口處的IN[B2]?在第二次和第三次值（下劃線處）是相同的，故無(wú)需再進(jìn)行第四次迭代了。

我們可以應(yīng)用到達(dá)-定值信息來(lái)計(jì)算各個(gè)變量在任何引用點(diǎn)的引用-定值鏈，即先找出其所有的引用點(diǎn)，然后再應(yīng)用規(guī)則求各點(diǎn)的ud鏈。這個(gè)規(guī)則就是：（1）如果在基本塊B中，變量A的引用點(diǎn)p之前有A的定值點(diǎn)d，并且A在點(diǎn)d的定值到達(dá)p，那么A在點(diǎn)p的ud鏈就是7hlprj3；（2）如果在基本塊B中，變量A的引用點(diǎn)p之前沒(méi)有A的定值點(diǎn)，那么IN[B]?中A的所有定值點(diǎn)均到達(dá)p，它們就是A在點(diǎn)p的ud鏈。5.3.2定值-引用鏈（du鏈）

我們已經(jīng)知道了如何計(jì)算一個(gè)變量A在引用點(diǎn)的ud鏈，即能到達(dá)該引用點(diǎn)的A的所有定值點(diǎn)。反之，對(duì)一個(gè)變量A在某點(diǎn)p的定值，也可計(jì)算該定值能夠到達(dá)的A的所有引用點(diǎn)，它稱為該定值點(diǎn)的定值-引用鏈（簡(jiǎn)稱du鏈）。

對(duì)程序中某變量A和某點(diǎn)p，如果存在一條從p開(kāi)始的道路，其中引用了A在點(diǎn)p的值，則稱A在點(diǎn)p是活躍的。對(duì)于基本塊B，如果OUT[B]?僅給出哪些變量的值在B的后繼中還會(huì)使用的信息，而且還同指出它們?cè)贐的后繼中哪些點(diǎn)會(huì)被使用；那么就可直接應(yīng)用這種信息來(lái)計(jì)算B中任一變量A在定值點(diǎn)p的du鏈。在此，只要對(duì)B中p后面部分進(jìn)行掃描：如果B中p后面沒(méi)有A的其它定值點(diǎn)，則B中p后面A的所有引用點(diǎn)加上OUT[B]?中A的所有引用點(diǎn)就是A在定值點(diǎn)p的du鏈；如果B中p后面有A的其它定值點(diǎn)，則從p到p距離最近的那個(gè)A的定值點(diǎn)之間的A的所有引用點(diǎn)，就是A在定值點(diǎn)p的du鏈。所以，問(wèn)題歸結(jié)為如何計(jì)算出帶有上述引用點(diǎn)信息的OUT[B]。我們定義：

IN[B]基本塊B入口之前的活躍變量集（進(jìn)入基本塊B時(shí)，哪些變量A的定值能夠到達(dá)B和B的后繼中A的哪些引用點(diǎn)）。

OUT[B]基本塊B出口之后的活躍變量集（離開(kāi)基本塊B時(shí)，哪些變量A的定值能夠到達(dá)B的后繼中A的哪些引用點(diǎn)）。

USE[B]所有含?(p,?A)?的集；其中p是B中某點(diǎn)，p引用變量A的值且B中在p前面沒(méi)有A的定值點(diǎn)。

DEF[B]所有含?(p,?A)?的集；其中p是不屬于B的某點(diǎn)，p引用變量A的值但A在B中被重新定值。

顯然，USE和DEF可以從給定的程序流圖中直接求出，問(wèn)題是如何計(jì)算IN和OUT。對(duì)已經(jīng)介紹過(guò)的到達(dá)-定值方程，那里的基本塊B的IN集是由IN的所有前驅(qū)的OUT集計(jì)算出來(lái)的，這是一個(gè)由前往后的計(jì)算過(guò)程。對(duì)于我們現(xiàn)在需要計(jì)算的基本塊活躍變量來(lái)說(shuō)，根據(jù)定義它應(yīng)該是一個(gè)由后往前的計(jì)算過(guò)程，即從某基本塊所有后繼的IN來(lái)求得該基本塊的OUT；這是因?yàn)椋簩?duì)在某點(diǎn)p定值的變量A，只有在以后引用了它，才表示變量A從p開(kāi)始是活躍的，所以只有從后面尋找引用了哪些變量并向前尋找這些變量相應(yīng)的定值點(diǎn)，即此時(shí)才能確定與這些找到定值點(diǎn)開(kāi)始所對(duì)應(yīng)的變量才是活躍的；因此，計(jì)算基本塊的活躍變量這個(gè)過(guò)程是由后向前進(jìn)行的。

按