編譯原理教程05代碼優(yōu)化.ppt

1、5.1 局部優(yōu)化 5.2 循環(huán)優(yōu)化 *5.3 全局優(yōu)化概述 *5.4 代碼優(yōu)化示例 習(xí)題五,第5章代 碼 優(yōu) 化,代碼優(yōu)化的含義 進(jìn)行代碼優(yōu)化的時(shí)間 代碼優(yōu)化的種類,源程序經(jīng)過詞法分析、語法分析、語義分析等階段的編譯工作，得到了與源程序功能等價(jià)的中間代碼。但是，由于這種中間代碼是“機(jī)械生成”的結(jié)果，因而必然存在效率不高和有冗余代碼的現(xiàn)象，還需進(jìn)行代碼優(yōu)化。 代碼優(yōu)化的含義是：對(duì)代碼進(jìn)行等價(jià)變換，使得變換后的代碼具有更高的時(shí)間效率和空間效率。代碼優(yōu)化的目的是提高目標(biāo)程序的質(zhì)量。,1.代碼優(yōu)化的含義,優(yōu)化可以在編譯的不同階段進(jìn)行，但最主要的一類優(yōu)化是在目標(biāo)代碼生成以前進(jìn)行的，即對(duì)語義分析后的中間代

2、碼進(jìn)行優(yōu)化，這種優(yōu)化的優(yōu)點(diǎn)是不依賴于具體的計(jì)算機(jī)。 另一類重要的優(yōu)化是在生成目標(biāo)代碼時(shí)進(jìn)行的，它在很大程度上依賴于具體的計(jì)算機(jī)。本章討論前一種與機(jī)器無關(guān)的中間代碼優(yōu)化。,2.進(jìn)行代碼優(yōu)化的時(shí)間,根據(jù)優(yōu)化對(duì)象所涉及的程序范圍，優(yōu)化又分為 局部優(yōu)化、循環(huán)優(yōu)化和全局優(yōu)化。 一個(gè)程序從結(jié)構(gòu)上看，作為結(jié)點(diǎn)的基本塊是其基礎(chǔ)。因?yàn)榛緣K的結(jié)構(gòu)最簡單、因素最單純，所以它也是優(yōu)化的基礎(chǔ)，對(duì)基本塊的優(yōu)化就是局部優(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ù)流分析的問題。,3.代碼優(yōu)化的種類,5.1 局 部 優(yōu) 化,基本

3、塊的劃分方法 基本塊的DAG表示,5.1.1 基本塊的劃分方法 所謂基本塊，是指程序中一順序執(zhí)行的語句序列，其中只有一個(gè)入口和一個(gè)出口，入口就是該序列的第一個(gè)語句，出口就是該序列的最后一個(gè)語句。對(duì)一個(gè)基本塊來說，執(zhí)行時(shí)只能從其入口進(jìn)入，從其出口退出。對(duì)一個(gè)給定的程序，我們可以把它劃分為一系列基本塊，在各個(gè)基本塊范圍內(nèi)進(jìn)行的優(yōu)化稱為局部優(yōu)化。劃分基本塊的關(guān)鍵問題是準(zhǔn)確定義入口和出口語句。下面我們給出劃分四元式程序?yàn)榛緣K的算法： (1) 從四元式序列確定滿足以下條件的入口語句： 四元式序列的第一個(gè)語句； 能由條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句轉(zhuǎn)移到的語句； 緊跟在條件轉(zhuǎn)移語句后面的語句。,(2) 確定

4、滿足以下條件的出口語句： 下一個(gè)入口語句的前導(dǎo)語句； 轉(zhuǎn)移語句(包括轉(zhuǎn)移語句自身)； 停語句(包括停語句自身)。,例如，考察下面求最大公因子的三地址代碼程序： (1) read X (2) read Y (3) R=X % Y (4) if R=0 goto(8) (5) X=Y (6) Y=R (7) goto(3) (8) write Y (9) halt 根據(jù)上述劃分基本塊的算法可確定四元式(1)、(3)、(5)、(8)是入口語句，而四個(gè)基本塊分別是：(1)(2)，(3)(4)，(5)(6)(7)，(8)(9)。,5.1.2 基本塊的DAG表示 DAG(Directed Acyclic

5、Graph)是一種有向圖，常常用來對(duì)基本塊進(jìn)行優(yōu)化。一個(gè)基本塊的DAG是一種其結(jié)點(diǎn)帶有下述標(biāo)記或附加信息的DAG： (1) 圖的葉結(jié)點(diǎn)(無后繼的結(jié)點(diǎn))以一標(biāo)識(shí)符(變量名)或常數(shù)作為標(biāo)記，表示該結(jié)點(diǎn)代表該變量或常數(shù)的值。如果葉結(jié)點(diǎn)用來表示一變量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è)四元式序列組成，且

6、每一個(gè)四元式都可以用相應(yīng)的DAG結(jié)點(diǎn)表示。圖51給出了不同四元式和與其對(duì)應(yīng)的DAG結(jié)點(diǎn)形式。圖中，各結(jié)點(diǎn)圓圈中的ni是構(gòu)造DAG過程中各結(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)移語句的結(jié)點(diǎn)右邊可附加一語句位置來指示轉(zhuǎn)移目標(biāo)外，其余各類結(jié)點(diǎn)的右邊只允許附加標(biāo)識(shí)符。除對(duì)應(yīng)于數(shù)組元素賦值的結(jié)點(diǎn)(標(biāo)記為 =)有三個(gè)后繼外，其余結(jié)點(diǎn)最多只有兩個(gè)后繼。,圖51 四元式與DAG結(jié)點(diǎn),利用DAG進(jìn)行基本塊優(yōu)化的基本思想是：首先按基本塊內(nèi)的四元式序列順序?qū)⑺械乃脑綐?gòu)造成一個(gè)DAG，然后按構(gòu)造結(jié)點(diǎn)的次序?qū)AG還原成四元式序列。由

7、于在構(gòu)造DAG的同時(shí)已做了局部優(yōu)化，所以最后所得到的是優(yōu)化過的四元式序列。 為了DAG構(gòu)造算法的需要，我們將圖51中的四元式按照其對(duì)應(yīng)結(jié)點(diǎn)的后繼結(jié)點(diǎn)個(gè)數(shù)分為四類： (1) 0型四元式：后繼結(jié)點(diǎn)個(gè)數(shù)為0，如圖51(1)所示； (2) 1型四元式：有一個(gè)后繼結(jié)點(diǎn)，如圖51(2)所示； (3) 2型四元式：有兩個(gè)后繼結(jié)點(diǎn)，如圖51(3)、(4)、(5)所示； (4) 3型四元式：有三個(gè)后繼結(jié)點(diǎn)，如圖51(6)所示。,我們規(guī)定：用大寫字母(如A、B等)表示四元式中的變量名(或常數(shù))；用函數(shù)Node(A)表示A在DAG中的相應(yīng)結(jié)點(diǎn)，其值可為n或者無定義，并用n表示DAG中的一個(gè)結(jié)點(diǎn)值。這樣，每個(gè)基本塊僅

8、含0、1、2型四元式的DAG構(gòu)造算法如下(對(duì)基本塊的每一個(gè)四元式依次執(zhí)行該算法)： (1) 若Node(B)無定義，則構(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)無定義，則構(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í)行op

9、 B(即合并已知量)，令得到的新常數(shù)為P。若Node(B)是處理當(dāng)前四元式時(shí)新建立的結(jié)點(diǎn)，則刪除它；若Node(P)無定義，則構(gòu)造一用P做標(biāo)記的葉結(jié)點(diǎn)n并置Node(P)=n；轉(zhuǎn)(4)。 執(zhí)行B op C(即合并已知量)，令得到的新常數(shù)為P。若Node(B)或Node(C)是處理當(dāng)前四元式時(shí)新建立的結(jié)點(diǎn)，則刪除它；若Node(P)無定義，則構(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；若沒有，則構(gòu)造一個(gè)新結(jié)點(diǎn)；轉(zhuǎn)(4)。 檢查DAG中是

10、否有標(biāo)記為op且其左后繼為Node(B)、右后繼為Node(C)的結(jié)點(diǎn)(即查找公共子表達(dá)式)。若有，則把已有的結(jié)點(diǎn)作為它的結(jié)點(diǎn)并設(shè)該結(jié)點(diǎn)為n；若沒有，則構(gòu)造一個(gè)新結(jié)點(diǎn)；轉(zhuǎn)(4)。 (4) 若Node(A)無定義，則把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)，而

11、是執(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)重新寫為四元式時(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í)符集中刪除的操作則意味著刪除了無用賦值(對(duì)A賦值后但在該A值引用之前又重新對(duì)A進(jìn)行了賦值，則前一個(gè)賦值為無用賦值)。 綜上所述，DAG可以在基本塊內(nèi)實(shí)現(xiàn)合并已知量、刪除無用賦值和刪除多余

12、運(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=Rr (10) B= T5*T6 解答 按照算法順序處理每一四元式后構(gòu)造出的DAG如圖52所示，其中每一子圖(1)、(2)、(10)分別對(duì)應(yīng)四元式(1)(10)的DAG構(gòu)造。,DAG構(gòu)造過程,(1) T0=3.14,(2) T1=2*T0,DAG構(gòu)造過程,(3) T2=R+r,DAG構(gòu)造過程,(4) A=T1*T2,DAG構(gòu)造過程,(5) B=A,D

13、AG構(gòu)造過程,(6) T3=2*T0,DAG構(gòu)造過程,(7) T4=R+r,DAG構(gòu)造過程,(8) T5=T3*T4,DAG構(gòu)造過程,(9) T6=R-r,DAG構(gòu)造過程,(10) B=T5*T6,圖52 DAG,構(gòu)造過程說明如下： (1) 對(duì)應(yīng)圖52(2)，四元式T1=2*T0首先執(zhí)行算法中的步驟(1)，因Node(B)無定義，所以構(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í)行B op C并令新結(jié)點(diǎn)為P

14、(=6.28)。由于Node(P)無定義，故構(gòu)造Node(P)=Node(6.28)。此外，因Node(B)=Node(2)是處理當(dāng)前四元式時(shí)新構(gòu)造出來的結(jié)點(diǎn)，故刪除n2。接下來執(zhí)行算法步驟(4)，因Node(A)無定義而將T1附加在結(jié)點(diǎn)n3上，并令Node(T1)=6.28；最后DAG生成了2個(gè)結(jié)點(diǎn)n1和n3，因結(jié)點(diǎn)n2被刪除而將n3改名為n2。圖52(2)的形成過程實(shí)際上也是合并已知量的優(yōu)化過程。,(2) 圖52(4)中T1、T2已有定義，則僅生成一個(gè)新結(jié)點(diǎn)n6并將A附加在n6上。圖5-2(5)中結(jié)點(diǎn)B已有定義，故直接附加在n6上。 (3) 圖52(6)的處理過程與圖52(2)略同，但在生

15、成P時(shí)因其已在DAG中(即Node(6.28)，故不生成新結(jié)點(diǎn)而直接將T3附加在結(jié)點(diǎn)6.28上。 (4) 圖52(7)的生成過程實(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無定義而將T4附加在結(jié)點(diǎn)n5上。,(5) 圖52(9)中，變量R和r已在DAG中有相應(yīng)的結(jié)點(diǎn)，執(zhí)行“”操作后，產(chǎn)生的新結(jié)點(diǎn)P無定義，故僅生成一個(gè)新結(jié)點(diǎn)n7并將T6標(biāo)記于其上。 (6) 圖52(10)中，對(duì)當(dāng)前四元式B=T5*T6，DAG中已有結(jié)點(diǎn)T5和T6；執(zhí)行算法步驟(4)時(shí)因結(jié)點(diǎn)B已有定義且不是葉結(jié)點(diǎn)，

16、故先將原B從DAG中刪除，然后生成一個(gè)新結(jié)點(diǎn)n8，將B附加其上并令Node(B)=n8。這一處理過程實(shí)質(zhì)上是刪除了無用賦值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)寫出其相應(yīng)的四元式表示。 我們根據(jù)例5.1DAG結(jié)點(diǎn)的構(gòu)造順序，按照圖52(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= Rr (9) B=A*T6,將G和原基本塊G相比，我們看到：

17、(1) G中四元式(2)和(6)都是已知量和已知量的運(yùn)算，G已合并； (2) G中四元式(5)是一種無用賦值，G已將它刪除； (3) G中四元式(3)和(7)的R+r是公共子表達(dá)式，G只對(duì)它們計(jì)算了一次，即刪除了多余的R+r運(yùn)算。 因此，G是對(duì)G實(shí)現(xiàn)上述三種優(yōu)化的結(jié)果。,通過觀察圖52(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)一步深入，尤其是無用賦值

18、的優(yōu)化，也即： (1) 如果DAG中某結(jié)點(diǎn)上的標(biāo)識(shí)符在該基本塊之后不會(huì)被引用，就可以不生成對(duì)該標(biāo)識(shí)符賦值的四元式； (2) 如果某結(jié)點(diǎn)ni上沒有任何附加標(biāo)識(shí)符，或者ni上的附加標(biāo)識(shí)符在該基本塊之后不會(huì)被引用，而且ni也沒有前驅(qū)結(jié)點(diǎn)，這表明在基本塊內(nèi)和基本塊之后都不會(huì)引用ni的值，那么就不生成計(jì)算ni結(jié)點(diǎn)值的四元式； (3) 如果有兩個(gè)相鄰的四元式A=C op D和B=A，其中第一條代碼計(jì)算出來的A值僅在第二個(gè)四元式中被引用，則將DAG中相應(yīng)結(jié)點(diǎn)重寫成四元式時(shí)，原來的兩個(gè)四元式可以優(yōu)化為B=C op D。,假設(shè)例5.1中T0、T1、T2、T3、T4、T5和T6在基本塊后都不會(huì)被引用，則圖5-2(

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

20、(2) aj=y (3) z=ai,如果我們用構(gòu)造DAG的算法來構(gòu)造上述基本塊的DAG，則ai就是一個(gè)公共子表達(dá)式；且由所構(gòu)造的DAG重寫出優(yōu)化后的四元式序列G如下： (1) x=ai (2) z=x (3) aj=y 如果ij，則G與G是等效的。但是，如果i=j且yai，則將y值賦給aj的同時(shí)也改變了ai的值(因i=j)；這時(shí)z值應(yīng)為改變后的ai值(即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ì)指針賦值語

21、句*p=w(其中p是一個(gè)指針)也會(huì)產(chǎ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è)過程調(diào)用將注銷所有的結(jié)點(diǎn)，因?yàn)閷?duì)被調(diào)用過程的情況缺乏了解，所以我們必須假定任何變量都可能因產(chǎn)生副作用而發(fā)生變化。,此外，當(dāng)把DAG重寫成四元式時(shí)，如果我們不是按照原來構(gòu)造DAG結(jié)點(diǎn)的順序進(jìn)行重寫，那么DAG中的某些結(jié)點(diǎn)必須遵守一定的順序。例如，在上述基本塊G中，z=ai必須跟在aj=y之后，而aj=

22、y則必須跟在x=ai之后。下面，我們根據(jù)上述討論把重寫四元式時(shí)DAG中結(jié)點(diǎn)間必須遵守的順序歸納如下： (1) 對(duì)數(shù)組a中任何元素的引用或賦值，都必須跟在原來位于其前面的(如果有的話，下同)對(duì)數(shù)組a任何元素的賦值之后；對(duì)數(shù)組a任何元素的賦值，都必須跟在原來位于其前面的對(duì)數(shù)組a任何元素的引用之后。,(2) 對(duì)任何標(biāo)識(shí)符的引用或賦值，都必須跟在原來位于其前面的任何過程調(diào)用或通過指針的間接賦值之后；任何過程調(diào)用或通過指針的間接賦值，都必須跟在原來位于其前面的任何標(biāo)識(shí)符的引用或賦值之后。 總之，當(dāng)對(duì)基本塊重寫時(shí)，任何數(shù)組a的引用不允許互相調(diào)換次序，并且任何語句不得跨越一個(gè)過程調(diào)用語句或者通過指針的間接賦

23、值。,5.2 循 環(huán) 優(yōu) 化 5.2.1 程序流圖與循環(huán) 為了進(jìn)行循環(huán)優(yōu)化，必須先找出程序中的循環(huán)。由程序語言的循環(huán)語句形成的循環(huán)是不難找出的，但由條件轉(zhuǎn)移語句和無條件轉(zhuǎn)移語句同樣可以形成程序中的循環(huán)，并且其結(jié)構(gòu)可能更加復(fù)雜。因此，為了找出程序中的循環(huán)，就需要對(duì)程序中的控制流程進(jìn)行分析。我們應(yīng)用程序的控制流程圖來給出循環(huán)的定義并找出程序中的循環(huán)。 一個(gè)控制流程圖(簡稱流圖)就是具有惟一首結(jié)點(diǎn)的有向圖。所謂首結(jié)點(diǎn)，就是從它開始到控制流程圖中任何一個(gè)結(jié)點(diǎn)都有一條通路的結(jié)點(diǎn)。我們可以把控制流程圖表示成一個(gè)三元組G=(N,E,n0)；其中，N代表圖中所有結(jié)點(diǎn)集，E代表圖中所有有向邊集，n0代表首結(jié)點(diǎn)。

24、,一個(gè)程序可用一個(gè)流圖來表示。流圖的有限結(jié)點(diǎn)集N就是程序的基本塊集，流圖中的結(jié)點(diǎn)就是程序的基本塊，流圖的首結(jié)點(diǎn)就是包含程序第一個(gè)語句的基本塊。流圖的有向邊集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的出口語句不是無條件轉(zhuǎn)移語句goto(s)或停語句。,(2) 基本塊i的出口語句是goto(s)或if goto(s)，并且(s)是基本塊j的入口語句。 在以后的討論中，我們所涉及的流圖都是程序流圖。程序流圖和基本塊的DAG是不同的概念。程序流圖

25、是對(duì)整個(gè)程序而言的，它表示了各基本塊(對(duì)應(yīng)流圖中的一個(gè)結(jié)點(diǎn))之間的控制關(guān)系，圖中可以出現(xiàn)環(huán)路；DAG是對(duì)基本塊而言的，是局限于該基本塊內(nèi)的無環(huán)路有向圖，它表示了這個(gè)基本塊內(nèi)各四元式的操作及相互關(guān)系。,我們?nèi)砸韵旅媲笞畲蠊蜃拥娜刂反a程序?yàn)槔齺砬笃涑绦蛄鲌D： (1) read X (2) read Y (3) R=X % Y (4) if R=0 goto (8) (5) X=Y (6) Y=R (7) goto (3) (8) write Y (9) halt 我們知道，該程序的基本塊分別為(1)(2)，(3)(4)，(5)(6)(7)和(8)(9)。按構(gòu)造流圖結(jié)點(diǎn)間有向邊的方法，我們得到

26、該程序的程序流圖如圖53所示。,圖53 求最大公因子的程序流圖,有了程序流圖，我們就可以對(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)過循環(huán)的入口結(jié)點(diǎn)。對(duì)于

27、性質(zhì)(1)，任意兩個(gè)結(jié)點(diǎn)之間必有一條通路，即通路上的尾結(jié)點(diǎn)到首結(jié)點(diǎn)之間也有一條通路(實(shí)際上可認(rèn)為無首尾之分)，這就構(gòu)成了一個(gè)環(huán)形通路。該通路上的各結(jié)點(diǎn)都屬于該結(jié)點(diǎn)序列，即從通路上的任何結(jié)點(diǎn)開始所構(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ì)圖53所示的程序流圖，由上述循環(huán)的定義可知，結(jié)點(diǎn)序列B2，B3是程序中的一個(gè)循環(huán)，其中，B2是

28、循環(huán)的惟一入口結(jié)點(diǎn)。 對(duì)圖54所示的程序流圖，結(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)。,圖54 程序流圖,5.2.2

29、循環(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)過m，則稱m是n的必經(jīng)結(jié)點(diǎn)，記為m DOM n；流圖中結(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來說都有n DOM n。,如果把DOM看作流圖結(jié)點(diǎn)集上定義的一個(gè)關(guān)系，則由定義容易看出它具有下述性質(zhì)： (1) 自反性：對(duì)流圖中任意結(jié)點(diǎn)a，都有a DOM a。 (2) 傳遞性：對(duì)流圖中任意結(jié)點(diǎn)a、b、c，若存在

30、a DOM b和b DOM c,則必有a DOM c。 (3) 反對(duì)稱性：若存在a DOM b和b DOM a，則必有a=b。 因此，關(guān)系DOM是一個(gè)偏序關(guān)系，任何結(jié)點(diǎn)n的必經(jīng)結(jié)點(diǎn)集是一個(gè)有序集。 例5.2 求圖54中流圖各結(jié)點(diǎn)的D(n)。,解答 考察圖54的流圖并由必經(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

31、，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 (nNn0) D(n)=N; /*置初值*/ change=true; while (change) change=false; for (nNn0) ,if (new!=D(n) change=true; D(n)=new; ,注意：由于算法中是利用所有前驅(qū)信息進(jìn)行運(yùn)算來獲得某結(jié)點(diǎn)對(duì)應(yīng)的必經(jīng)結(jié)點(diǎn)集的，因此迭代初值D(ni)必須取最大值，即全集N。此外，由 知表示結(jié)點(diǎn)n的所有前驅(qū)(即父

32、結(jié)點(diǎn))的必經(jīng)結(jié)點(diǎn)集的交集即為n的必經(jīng)結(jié)點(diǎn)集。由圖55可看出，ni為nj的必經(jīng)結(jié)點(diǎn)(ni為結(jié)點(diǎn)nj所有前驅(qū)nk1nkn必經(jīng)結(jié)點(diǎn)集的交集)，而nk1nkn都不是nj的必經(jīng)結(jié)點(diǎn)。另一點(diǎn)要說明的是，因程序流圖中有循環(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)行下一次迭代來計(jì)算各結(jié)點(diǎn)的D(n)(即算法中的while循環(huán)繼續(xù)執(zhí)行)，直至全部結(jié)點(diǎn)的D(n)都不改變?yōu)橹?即算法中的change值為false才結(jié)束算法的執(zhí)行)。,圖55 ni為nj的必經(jīng)結(jié)點(diǎn)示意,例5.3 應(yīng)用求流圖必經(jīng)結(jié)點(diǎn)集的算

33、法求圖54所示程序流圖各結(jié)點(diǎn)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，然后從結(jié)點(diǎn)2到結(jié)點(diǎn)7依次執(zhí)行第二個(gè)for循環(huán)。 對(duì)結(jié)點(diǎn)2，因new=2D(1)D(4)=211,2,3,4,5,6,7 =21=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=3D(2)=31,2=1,2,3 但迭代前D(3)=1,2,3,4,5,6,7，故D(3) new，因此令D(3

34、)=1, 2, 3。,其余各結(jié)點(diǎn)按照上述步驟可求出： D(4)=4D(2)D(3)D(7)=41,21,2,31,2,3,4,5,6,7=1,2,4 D(5)=5D(4)=1,2,4,5 D(6)=6D(4)=1,2,4,6 D(7)=7D(5)D(6)=71,2,4,51,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=2D(1)D(4) =211,2,4 =21=1,2 而迭代前D(2)=1,2，所以D(2)=new，故D(2)不變。 對(duì)結(jié)點(diǎn)

35、3，因 new=3D(2) =31,2=1,2,3 及迭代前D(3)=1,2,3，所以D(3)=new，故D(3)不變。 對(duì)其余結(jié)點(diǎn)n(n=47)求出的new均有D(n)=new，所以第二次迭代后change為false，迭代結(jié)束，第一次迭代求出的各個(gè)D(n)就是最后的結(jié)果。,2回邊 查找循環(huán)的方法是：首先應(yīng)用必經(jīng)結(jié)點(diǎn)集來求出流圖中的回邊，然后利用回邊找出流圖中的循環(huán)。 回邊的定義如下：假設(shè)ab是流圖中一條有向邊，如果b DOM a，則稱ab是流圖中的一條回邊。 對(duì)于一已知流圖G，只要求出各結(jié)點(diǎn)n的必經(jīng)結(jié)點(diǎn)集，就可以立即求出流圖中的所有回邊。在求出流圖G中的所有回邊后，就可以求出流圖中的循環(huán)。

36、如果已知有向邊nd是一條回邊，則由它組成的循環(huán)就是由結(jié)點(diǎn)d、結(jié)點(diǎn)n以及有通路到達(dá)n但該通路不經(jīng)過d的所有結(jié)點(diǎn)組成的。,例5.4 求出圖54所示程序流圖的所有回邊。 解答 (1) 已知D(6)=1,2,4,6，因存在66且6 DOM 6，故66是回邊； (2) 已知D(7)=1,2,4,7，因存在74且4 DOM 7，故74是回邊； (3) 已知D(4)=1,2,4，因存在42且2 DOM 4，故42是回邊。 容易看出，其它有向邊都不是回邊。,尋找由回邊組成循環(huán)的算法如下： main () stack=空; /*stack是一個(gè)工作棧*/ loop=d; /*loop是所求的循環(huán)*/ inser

37、t(m); while (stack非空) 彈出stack棧頂元素m; for (pP(m) /*P(m)為結(jié)點(diǎn)m的前驅(qū)結(jié)點(diǎn)集*/ insert (p); ,void insert (m) if (mloop) loop=loopm; 把m壓入棧stack; 此算法中求回邊nd組成循環(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ù)上述過程，直到所求出的前驅(qū)都是d為止。,3可歸約流

38、圖 一個(gè)流圖被稱為可歸約的，當(dāng)且僅當(dāng)流圖中除去回邊之外，其余的邊構(gòu)成一個(gè)無環(huán)路流圖。例如，圖54中的流圖就是一個(gè)可歸約流圖，而圖56則是一個(gè)不可歸約流圖，因?yàn)閳D56中雖然有23，但沒有3 DOM 2，即23不是一個(gè)回邊，對(duì)32也是如此。 如果程序流圖是可歸約的，那么程序中任何可能反復(fù)執(zhí)行的代碼都會(huì)被求回邊的算法納入到一個(gè)循環(huán)當(dāng)中。,圖56 不可歸約流圖,可歸約流圖是一類非常重要的流圖，從代碼優(yōu)化的角度來說，它具有下述重要的性質(zhì)： (1) 圖中任何直觀意義下的環(huán)路都屬于我們所定義的循環(huán)。 (2) 只要找出圖中的所有回邊，對(duì)回邊應(yīng)用查找循環(huán)的方法，就可以找出流圖中的所有循環(huán)。 (3) 圖中任意兩個(gè)

39、循環(huán)要么嵌套，要么不相交(除了可能有公共的入口結(jié)點(diǎn))，對(duì)這類流圖進(jìn)行循環(huán)優(yōu)化較為容易。 應(yīng)用結(jié)構(gòu)程序設(shè)計(jì)原則寫出的程序，其流圖總是可歸約的；而應(yīng)用高級(jí)語言寫出的程序，其流圖往往也是可歸約的。,例5.5 四元式序列如下： (1) J=0； (2) L1：I=0； (3) if I 8 goto L3; (4) L2：A=B+C； (5) B=D*C; (6) L3：if B=0 goto L4; (7) write B; (8) goto L5; (9) L4 ：I= I+1; (10) if I8 goto L2; (11) L5：J= J+1; (12) ifJ3 goto L1; (13)

40、 halt 畫出該四元式序列的程序流圖G并求出G中的回邊與循環(huán)。,解答 該四元式序列的基本塊與程序流圖如圖57所示。 圖57中各結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)集如下： D(B1)=B1 D(B5)=B1,B2,B4,B5 D(B2)=B1,B2 D(B6)=B1,B2,B4,B6 D(B3)=B1,B2,B3 D(B7)=B1,B2,B4,B7 D(B4)=B1,B2,B4 D(B8)=B1,B2,B4,B7,B8 考察流圖中的有向邊B7B2且已知D(B7)= B1,B2,B4,B7，所以有B2 DOM B7，即B7B2是流圖中的回邊。容易看出，其它有向邊都不是回邊。 因B7B2是一條回邊，則在流圖中能夠不經(jīng)

41、過結(jié)點(diǎn)B2且有通路到達(dá)結(jié)點(diǎn)B7的結(jié)點(diǎn)只有B3、B4、B5和B6，故由回邊B7B2組成的循環(huán)是： B2, B3, B4, B5, B6, B7。,圖57 例5.5的程序流圖,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)為其惟一后繼，原來

42、流圖中從循環(huán)外引到循環(huán)入口結(jié)點(diǎn)的有向邊改成引到循環(huán)前置結(jié)點(diǎn)，如圖58所示。,圖58 給循環(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=B op C或A= op B或A=B，要求滿足下述條件(A在離開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á)。,圖59 代碼外提的程序流圖示例,對(duì)上述三個(gè)條件，我們給出圖59所示的三種

43、流圖予以說明。,(1) 對(duì)圖59(a)，先將B3中的循環(huán)不變運(yùn)算I=2外提到循環(huán)前置結(jié)點(diǎn)B2中，如圖510所示。 由圖59(a)可知，B3并不是出口結(jié)點(diǎn)B4的必經(jīng)結(jié)點(diǎn)。如果令X=30，Y=25，則按圖59(a)的程序流圖，B3是不會(huì)執(zhí)行的；于是，當(dāng)執(zhí)行到B5時(shí)，I的值是1。但是，如果按圖510執(zhí)行，則執(zhí)行到B5時(shí)，I的值總是2，因此圖510改變了原來程序運(yùn)行的結(jié)果。出現(xià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)。,圖510 將圖58(a)中的I=2外提后的程序流圖,(2) 考查圖59(b)，現(xiàn)在

44、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í)行的順序是B2B3B4B2B4B5，則到達(dá)B5時(shí)I值為2；但如果不把B2中的I=3外提，則經(jīng)過以上執(zhí)行順序到達(dá)B5時(shí)，I值為3。由此可知，當(dāng)把循環(huán)中的不變運(yùn)算A=B op C外提時(shí)，要求循環(huán)中其它地方不再有A的定值點(diǎn)。,(3) 考查圖59(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)，不僅

45、B4中I的定值能夠到達(dá)，而且B1中I的定值也能到達(dá)?，F(xiàn)在考慮進(jìn)入循環(huán)前X=0和Y=2時(shí)的情況，此時(shí)循環(huán)的執(zhí)行順序?yàn)锽2B3B4B2B4B5，當(dāng)?shù)竭_(dá)B5時(shí)A值為2；但如果把B4中的I=2外提，則到達(dá)B5時(shí)A值為3。因此當(dāng)把循環(huán)不變運(yùn)算A=B op C外提時(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之外

46、，或只有一個(gè)到達(dá)一定值點(diǎn)且該點(diǎn)上的四元式已標(biāo)記為“不變運(yùn)算”，則把被查看的四元式標(biāo)記為“不變運(yùn)算”。 (3) 重復(fù)第(2)步直至沒有新的四元式被標(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=B op C或A= op B或A=B，檢查它是否滿足以下條件： i. S所在的結(jié)點(diǎn)是L的所有出口結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)； ii. A在L中其它地方未再定值； iii. L中所有A的引

47、用點(diǎn)只有S中A的定值才能到達(dá)。 A在離開L后不再是活躍的(即離開L后不會(huì)引用該A值)，并且條件的ii.和iii.兩條成立。所謂A在離開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)算”了)。 注意：如果把滿足條件(

48、2)的不變運(yùn)算A=B op C外提到前置結(jié)點(diǎn)中，則執(zhí)行完循環(huán)后得到的A值可能與不進(jìn)行外提的情形所得的A值不同，但因?yàn)殡x開循環(huán)后不會(huì)引用該A值，所以這不影響程序的運(yùn)行結(jié)果。,例5.6 試對(duì)圖511給定的程序流圖進(jìn)行代碼外提優(yōu)化。 解答 確定不變運(yùn)算的原則是依次查看循環(huán)中各基本塊的每個(gè)四元式，如果它的每個(gè)運(yùn)算對(duì)象為常數(shù)或者定值點(diǎn)在循環(huán)外，則將此四元式標(biāo)記為“不變運(yùn)算”。查看圖511所示的程序流圖，可以找出的不變運(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)并

49、非只有B3的I定值能夠到達(dá)，故B3中的I=2不能外提。最后，得到代碼外提后的程序流圖如圖512所示。,圖511 例5.6的程序流圖,圖512 代碼外提后的程序流圖,2強(qiáng)度削弱 強(qiáng)度削弱是指把程序中執(zhí)行時(shí)間較長的運(yùn)算替換為執(zhí)行時(shí)間較短的運(yùn)算。強(qiáng)度削弱不僅可對(duì)乘法運(yùn)算實(shí)行(將循環(huán)中的乘法運(yùn)算用遞歸加法運(yùn)算來替換)，對(duì)加法運(yùn)算也可實(shí)行。 如果循環(huán)中有I的遞歸賦值I=IC(C為循環(huán)不變量)，并且循環(huán)中T的賦值運(yùn)算可化歸為T=K*IC1(K和C1為循環(huán)不變量)，那么T的賦值運(yùn)算可以進(jìn)行強(qiáng)度削弱。 進(jìn)行強(qiáng)度削弱后，循環(huán)中可能出現(xiàn)一些新的無用賦值，如果它們在循環(huán)出口之后不是活躍變量則可以從循環(huán)中刪除。此外，

50、對(duì)下標(biāo)變量地址計(jì)算來說，強(qiáng)度削弱實(shí)際就是實(shí)現(xiàn)下標(biāo)變量地址的遞歸計(jì)算。,例5.7 試對(duì)圖513給定的程序流圖進(jìn)行強(qiáng)度削弱優(yōu)化。 解答 由圖513所示的流圖可以看出，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)度削弱后的流圖如圖514所示。,圖513 例5.7的程序流圖,圖514 例5.7強(qiáng)度削弱后的流圖,例5.8 試對(duì)圖515給定的程序流圖進(jìn)行強(qiáng)度削弱優(yōu)化。,圖51

51、5 例5.8的程序流圖,解答 強(qiáng)度削弱不僅可對(duì)乘法運(yùn)算進(jìn)行，也可對(duì)加法運(yùn)算進(jìn)行。由于本題中的四元式程序不存在乘法運(yùn)算，所以只能進(jìn)行加法運(yùn)算的強(qiáng)度削弱。從圖515中可以看到，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é)果如圖516所示。,圖516 例5.8強(qiáng)度削弱后的流圖,例5.9 試對(duì)圖5-17給定的程序流圖

52、進(jìn)行強(qiáng)度削弱優(yōu)化。 解答 由圖517的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é)果如圖518所示。,圖517 例5.9的程序流圖,圖518 例5.9強(qiáng)度削弱后的程序流圖,3刪除歸納變量 如果循環(huán)中對(duì)變量I只有惟一的形如I=IC的賦值，且其中C為循環(huán)不變量，則稱I為循環(huán)中的基本歸納變量。 如果

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

54、納變量。 (2) 找出所有其它歸納變量A，并找出A與已知基本歸納變量X的同族線性函數(shù)關(guān)系FA(X)；即： 在L中找出形如A=B*C、A=C*B、A=B/C、A=BC、A=CB的四元式，其中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與

55、D的函數(shù)關(guān)系是FA(D)=C*B=C*FB(D)。,(5) (刪除基本歸納變量)如果基本歸納變量B在循環(huán)出口之后不是活躍的，并且在循環(huán)中除在其自身的遞歸賦值中被引用外，只在形為if B rop Y goto Z(或if Y rop B goto Z)中被引用，則： 選取一與B同族的歸納變量M，并設(shè)FM(B)=C1*B+C2(盡可能使所選M的FM(B) 簡單，并且可能的話，使M是循環(huán)中其它四元式要引用的或者是循環(huán)出口之后的活躍變量)。 建立一臨時(shí)變量R，并用下列四元式： R=C1* Y (如果C1=1則C1不出現(xiàn)) R=R+ C2 (如果C2=0則無此四元式) if FM(B) rop R go

56、to Z (或if R rop FM(B) goto Z) 來替換if B rop Y goto Z(或if Y rop B goto Z)，即將原判斷條件B rop Y改為(C1*B+C2) rop (C1*Y+C2)，也就是FM(B) rop R。 刪除循環(huán)中對(duì)B遞歸賦值的四元式。,例5.10 試對(duì)圖514給定的程序流圖進(jìn)行刪除歸納變量優(yōu)化。 解答 由圖514可知，循環(huán)中I是基本歸納變量，A、B是與I同族的歸納變量且具有如下的線性關(guān)系： A=K*I B=J*I,因此，循環(huán)控制條件I100完全可用A100*K或B100*J來替代。這樣，基本塊B2中的控制條件和控制語句可改寫為 T1=100*

57、K if AT1 goto L 或者改寫為 T2=100*J if AT2 goto L 此時(shí)的程序流圖如圖519所示。,圖519 變換循環(huán)控制條件的程序流圖,循環(huán)控制條件經(jīng)過以上改變之后，就可以刪除基本塊B2中的語句I=I+1；而語句T1=100*K是循環(huán)中的不變運(yùn)算，故可由基本塊B2外提到基本塊B2中。最后，經(jīng)刪除歸納變量及代碼外提后得到的程序流圖如圖520所示。,圖520 刪除歸納變量及代碼外提后的程序流圖,5.3 代碼優(yōu)化示例 我們通過一個(gè)高級(jí)語言程序的例子來了解代碼優(yōu)化的全過程。下面是一個(gè)用C語言編寫的快速排序子程序： void quicksort (m, n) int m, n;

58、int i,j; int v, x; if(n=m) return; /*fragment begins here*/ i=m1; j=n; v=an;,while(1) do i=i+1; while(aiv); if(i=j) break; x=ai; ai=aj; aj=x; ,x=ai; ai=an; an=x; /*fragment ends here*/ quicksort(m, j); quicksort(i+1,n); 通過第四章的中間代碼生成方法可以產(chǎn)生這個(gè)程序的中間代碼。圖521給出了程序中兩個(gè)注解行之間的語句翻譯成中間代碼序列后所對(duì)應(yīng)的程序流圖，對(duì)圖521程序流圖的代碼優(yōu)

59、化敘述如下。,圖521 程序流圖,1刪除公共子表達(dá)式 在圖521的B5中分別把公共子表達(dá)式4*i和4*j的值賦給T7和T10，因此這種重復(fù)計(jì)算可以消除，即B5中的代碼變換成： B5: T6=4*i x=aT6 T7=T6 T8=4*j T9=aT8 aT7=T9 T10=T8 aT10=x goto B2,對(duì)B5刪除了公共子表達(dá)式后，仍然要計(jì)算4*i和4*j ，我們還可以在更大范圍內(nèi)來考慮刪除公共子表達(dá)式的問題，即利用B3中的四元式T4=4*j可以把B5中的代碼T8=4*j替換為T8=T4。 同樣，利用B2中的賦值句T2=4*i可以把B5中的代碼T6=4*i替換為T6=T2。 對(duì)于B6也可以同樣考慮，最后，刪除公共子表達(dá)式后的程序流圖如圖522所示。,圖522 刪除公共子表達(dá)式后的程序流圖,2復(fù)寫傳播 圖522中的B5還可以進(jìn)一步改進(jìn)，四元式T6=T2把T2賦給了T6，而四元式x=aT6中引用了T6的值，但