《編譯原理》課件第5章

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

(op,B,C,A)?

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

ifBropCgotoL (j,_,_,L)?

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

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

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

(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)是入口語句，而四個基本塊分別是：(1)(2)，(3)(4)，(5)(6)(7)，(8)(9)。5.1.2基本塊的DAG表示

DAG(DirectedAcyclicGraph)是一種有向圖，常常用來對基本塊進行優(yōu)化。一個基本塊的DAG是一種其結點帶有下述標記或附加信息的DAG：

(1)圖的葉結點(無后繼的結點)以一標識符(變量名)或常數(shù)作為標記，表示該結點代表該變量或常數(shù)的值。如果葉結點用來表示一變量A的地址，則用addr(A)作為該結點的標記。通常把葉結點上作為標記的標識符加上下標0，以表示它是該變量的初值。

(2)圖的內(nèi)部結點(有后繼的結點)以一運算符作為標記，表示該結點代表應用該運算符對其直接后繼結點所代表的值進行運算的結果。

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

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

(1)?0型四元式：后繼結點個數(shù)為0，如圖5–1(1)所示；

(2)?1型四元式：有一個后繼結點，如圖5–1(2)所示；

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

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

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

i.如果Node(C)無定義，則構造一標記為C的葉結點，并定義Node(C)為這個結點；

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

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

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

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

試構造以下基本塊的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

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

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

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

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

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

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

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

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

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

(1)在基本塊外被定值并在基本塊內(nèi)被引用的所有標識符就是DAG中相應葉結點上標記的標識符；

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

(1)如果DAG中某結點上的標識符在該基本塊之后不會被引用，就可以不生成對該標識符賦值的四元式；

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

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

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

(2)?A=6.28*S1

(3)?S2=R?r

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

(1)?x=a[i]

(2)?a[j]=y

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

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

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

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

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

(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)。按構造流圖結點間有向邊的方法，我們得到該程序的程序流圖如圖5–3所示。圖5–3求最大公因子的程序流圖有了程序流圖，我們就可以對所要討論的循環(huán)結構給出定義。在程序流圖中，我們稱具有下列性質(zhì)的結點序列為一個循環(huán)：

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

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

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

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

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

(1)自反性：對流圖中任意結點a，都有aDOMa。

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

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

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

[解答]考察圖5–4的流圖并由必經(jīng)結點的定義容易看出：首結點1是所有結點的必經(jīng)結點；結點2是除去結點1之外所有結點的必經(jīng)結點；結點4是結點4、5、6、7的必經(jīng)結點；而結點3、5、6、7都只是其自身的必經(jīng)結點。因此，直接由定義和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)的所有結點n的必經(jīng)結點集D(n)的算法；其中，P(n)代表結點n的前驅(qū)結點集，它可以從邊集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īng)結點集的，因此迭代初值D(ni)必須取最大值，即全集N。此外，由知表示結點n的所有前驅(qū)(即父結點)的必經(jīng)結點集的交集即為n的必經(jīng)結點集。由圖5–5可看出，ni為nj的必經(jīng)結點(ni為結點nj所有前驅(qū)nk1～nkn必經(jīng)結點集的交集)，而nk1～nkn都不是nj的必經(jīng)結點。另一點要說明的是，因程序流圖中有循環(huán)情況，所以后面計算的結點其必經(jīng)結點集D(nj)的改變可能要影響到前面所計算的D(ni)值。因此，在一次迭代計算結束時，只要發(fā)現(xiàn)某一個D(nk)被改變，就必須進行下一次迭代來計算各結點的D(n)(即算法中的while循環(huán)繼續(xù)執(zhí)行)，直至全部結點的D(n)都不改變?yōu)橹?即算法中的change值為false才結束算法的執(zhí)行)。

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

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

[解答]算法求解過程如下：首先置初值： D(1)={1}? D(2)=D(3)=D(4)=D(5)=D(6)=D(7) ={1,2,3,4,5,6,7}置change為false，然后從結點2到結點7依次執(zhí)行第二個for循環(huá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}。對結點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}。其余各結點按照上述步驟可求出：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，故還要進行下一次迭代。先令change為false，然后繼續(xù)從結點2到結點7依次執(zhí)行第二個for循環(huá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)不變。對結點3，因new={3}∪D(2)={3}∪{1,2}={1,2,3}及迭代前D(3)={1,2,3}，所以D(3)=new，故D(3)不變。對其余結點n(n=4～7)求出的new均有D(n)=new，所以第二次迭代后change為false，迭代結束，第一次迭代求出的各個D(n)就是最后的結果。

2．回邊查找循環(huán)的方法是：首先應用必經(jīng)結點集來求出流圖中的回邊，然后利用回邊找出流圖中的循環(huán)?；剡叺亩x如下：假設a→b是流圖中一條有向邊，如果bDOMa，則稱a→b是流圖中的一條回邊。對于一已知流圖G，只要求出各結點n的必經(jīng)結點集，就可以立即求出流圖中的所有回邊。在求出流圖G中的所有回邊后，就可以求出流圖中的循環(huán)。如果已知有向邊n→d是一條回邊，則由它組成的循環(huán)就是由結點d、結點n以及有通路到達n但該通路不經(jīng)過d的所有結點組成的。例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是一個工作棧

loop=0eys0mg; //loop是所求的循環(huán)

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

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

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

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

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

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

(3)圖中任意兩個循環(huán)要么嵌套，要么不相交(除了可能有公共的入口結點)，對這類流圖進行循環(huán)優(yōu)化較為容易。應用結構程序設計原則寫出的程序，其流圖總是可歸約的；而應用高級語言寫出的程序，其流圖往往也是可歸約的。例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畫出該四元式序列的程序流圖G并求出G中的回邊與循環(huán)。

[解答]該四元式序列的基本塊與程序流圖如圖5–7所示。由求流圖G的所有結點n的必經(jīng)結點集D(n)?的算法可知，初始時D(B1)?～D(B8)?為全集：{B1,?B2,?B3,?B4,?B5,?B6,?B7,?B8}，而各結點的必經(jīng)結點集的求法是：必經(jīng)結點集D(Bi)?為{Bi}并上Bi所有前驅(qū)（即父結點）的必經(jīng)結點集的交集。對圖5-7（圖5-8）中各結點的必經(jīng)結點集的求法如下：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)過結點B2且有通路到達結點B7的結點只有B3、B4、B5和B6，故由回邊B7→B2組成的循環(huán)是：{B2,

B3,

B4,

B5,

B6,

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

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

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

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

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

對上述三個條件，我們給出圖5–10所示的三種流圖予以說明。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

試對圖5–14給定的程序流圖進行強度削弱優(yōu)化。

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

圖5–15例5.7強度削弱后的流圖

例5.8

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

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

例5.9

試對圖5-18給定的程序流圖進行強度削弱優(yōu)化。

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

圖5–19例5.9強度削弱后的程序流圖

3．刪除歸納變量如果循環(huán)中對變量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同族。一個基本歸納變量也是一歸納變量。一個基本歸納變量除用于其自身的遞歸定值外，往往只在循環(huán)中用來計算其它歸納變量以及控制循環(huán)的進行。此時，可以用同族的某一歸納變量來替換循環(huán)控制條件中的這個基本歸納變量，從而達到將這個基本歸納變量從程序流圖中刪去的目的。這種優(yōu)化稱為刪除歸納變量或變換循環(huán)控制條件。由于刪除歸納變量是在強度削弱以后進行的，因此，我們一并給出強度削弱和刪除歸納變量的算法如下：

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

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

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

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

C*FB(D)。

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

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

R=R+C2//如果C2=0則無此四元式

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

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

試對圖5–15給定的程序流圖進行刪除歸納變量優(yōu)化。

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

A=K*I B=J*I

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

T1=100*K ifA<T1gotoL或者改寫為

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

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

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

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

為了求出到達點p的各個變量的所有定值點，我們先對程序中所有基本塊B作如下定義：

IN[B]到達基本塊B入口之前的各個變量的所有定值點集；

OUT[B]到達基本塊B出口之后的各個變量的所有定值點集；

GEN[B]基本塊B中定值的并到達B出口之后的所有定值點集；

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

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

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

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

在此，P[B]?代表B的所有前驅(qū)基本塊（即B的父結點）的集合；OUT[B]?意為：所有進入B前并在B中沒有被修改過的某變量定值點集與B中所“生成”的該變量定值點集的并集，即先計算IN[B]?-KILL[B]，然后再與GEN[B]?相“∪”。由于所有GEN[B]?和KILL[B]?可以從給定的程序流圖中直接求出，故上式是變量IN[B]?和OUT[B]?的線性聯(lián)立方程并被稱之為到達-定值數(shù)據(jù)流方程。設程序流圖含有n個結點，則到達-定值數(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]?賦初值，則無法進行后面的∪OUT[p]?計算（結果總為φ），這將使得IN[Bi]?計算沒有變化（始終為φ）；所以，必須先給OUT[Bi]?賦初值，而這個初值只能是基本塊Bi所產(chǎn)生的GEN[Bi]。在第(7)行中，我們按程序流圖中各結點的深度為主次序依次計算各基本塊的IN和OUT。change是用來判斷結束的布爾變量；NEWIN是集合變量，對每一基本塊Bi如果前后兩次迭代計算出的NEWIN值不等，則置change為true，表示尚需進行下一次迭代；這是因為程序中可能存在著循環(huán)，即后面結點（基本塊）IN和OUT的改變可能又影響到前面已計算過的結點之IN和OUT值；所以，只要出現(xiàn)某結點的IN和OUT發(fā)生變化的情況，迭代就得繼續(xù)下去。例5.11考察圖5-22所示的程序流圖，各四元式左邊的d分別代表該四元式的位置，假設只考慮變量i和j，求其到達-定值數(shù)據(jù)流方程的解。

【解】（1）我們先求出所有基本塊B的GEN[B]?和KILL[B]。GEN[B]?和KILL[B]?用位向量來表示，程序流圖中每一點d在向量中占一位；如果d屬于某個集，則該向量的相應位為1，否則為0。由定義直接計算出的GEN[B]?和KILL[B]?值見表5.1。圖5-22程序流圖（2）圖5-23是圖5-22程序流圖的深度為主擴展樹。各基本塊的深度為B1、B2、B3、B4、B5。根據(jù)上述迭代算法求解步驟如下：圖5-23深度為主擴展樹首先置迭代初值：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í)行算法計算如下：對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對B2：因NEWIN=OUT[B1]∪OUT[B5]?=?1100000∪0000000?=?1100000?≠IN[B2]故IN[B2]?=?1100000OUT[B2]?=?(?IN[B2]?-KILL[B2]?)∪GEN[B2]?=?0110000同理對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各次迭代結果見表5.2，因第四次迭代計算出的結果與第三次迭代結果相同，故它就是最后所求的結果。

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

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

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

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

IN[B]基本塊B入口之前的活躍變量集（進入基本塊B時，哪些變量A的定值能夠到達B和B的后繼中A的哪些引用點）。

OUT[B]基本塊B出口之后的活躍變量集（離開基本塊B時，哪些變量A的定值能夠到達B的后繼中A的哪些引用點）。

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

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

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

按