第5章代碼優(yōu)化.ppt

1、第五章 代碼優(yōu)化,5.1 局部優(yōu)化 5.2 循環(huán)優(yōu)化 5.3 代碼優(yōu)化示例,源程序經(jīng)過詞法分析、語法分析、語義分析等階段的編譯工作，得到了與源程序功能等價(jià)的中間代碼。由于這種中間代碼是 “ 機(jī)械生成 ” 的結(jié)果，因而必然存在效率不高和有冗余代碼的現(xiàn)象，需要進(jìn)行代碼優(yōu)化。 代碼優(yōu)化的含義：對代碼進(jìn)行等價(jià)變換，使得變換后的代碼具有更高的時(shí)間效率和空間效率。 代碼優(yōu)化的目的：是提高目標(biāo)程序的質(zhì)量。,優(yōu)化原則: 等價(jià)原則：經(jīng)過優(yōu)化不應(yīng)該改變程序運(yùn)行的結(jié)果。 有效原則：優(yōu)化后所產(chǎn)生的目標(biāo)代碼運(yùn)行時(shí)間確實(shí)較短，占用的空間確實(shí)較小。 合算原則：應(yīng)盡可能以較低的代價(jià)取得較好的優(yōu)化效果，應(yīng)為值得優(yōu)化的程序進(jìn)行優(yōu)

2、化。,常用的代碼優(yōu)化技術(shù)： 刪除多余運(yùn)算（刪除公共子表達(dá)式） 代碼外提 強(qiáng)度削弱 變化循環(huán)控制條件 合并已知量與復(fù)寫傳播 刪除無用賦值 根據(jù)優(yōu)化對象所涉及的范圍，優(yōu)化可分為局部優(yōu)化、循環(huán)優(yōu)化和全局優(yōu)化。,5.1 局部優(yōu)化,局部優(yōu)化是指對代碼的每一個(gè)線性部分所進(jìn)行的優(yōu)化，這個(gè)線性部分只存在一個(gè)入口和一個(gè)出口，這個(gè)線性部分稱之為基本塊。 基本塊內(nèi)可進(jìn)行的優(yōu)化有：刪除公共子表達(dá)式，刪除無用代碼，復(fù)寫傳播，合并已知常量等。,5.1.1 基本塊的劃分方法 基本塊是指程序中一順序執(zhí)行的語句序列，其中只有一個(gè)入口和一個(gè)出口，入口就是該序列的第一個(gè)語句，出口就是該序列的最后一個(gè)語句。 對一個(gè)基本塊來說，執(zhí)行時(shí)

3、只能從其入口進(jìn)入，從其出口退出。 對一個(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) 確定滿足以下條件的出口語句 下一個(gè)入口語句的前導(dǎo)語句； 轉(zhuǎn)移語句(包括轉(zhuǎn)移語句自身)； 停語句(包括停語句自身)。,(3) 劃分基本塊 對每個(gè)入口語句，確定其基本塊。它是由該入口語句到下一個(gè)入口語句(不包括下一個(gè)入口語句)，或到一個(gè)轉(zhuǎn)

4、移語句(包括該轉(zhuǎn)移語句)，或到一個(gè)停語句(包括該停語句)之間的語句序列組成。 凡未包含在基本塊內(nèi)的語句，都是控制流程不可到達(dá)的語句，故予以刪除。,補(bǔ)充說明：為敘述方便，我們把四元式寫成更為直觀的三地址代碼形式，如： (op,B,C,A) A=B op C (jrop,B,C,L) if B rop C goto L (j,_,_,L) goto L,例如，考察下面求最大公因子的三地址代碼程序： (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

5、 其中(1)(3)(5)(8)是入口語句，(2)(4)(7)(9)是出口語句。不同顏色的部分是四個(gè)基本塊。,5.1.2 基本塊的DAG表示 DAG(Directed Acyclic Graph)是一種有向無環(huán)圖，常常用來對基本塊進(jìn)行優(yōu)化。一個(gè)基本塊的DAG是一種其結(jié)點(diǎn)帶有下述標(biāo)記或附加信息的DAG： (1) 圖的葉結(jié)點(diǎn)以一個(gè)標(biāo)識符(變量名)或常數(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)識符加上下標(biāo)0，表示它是該變量的初值。,(2) 圖的內(nèi)部結(jié)點(diǎn)以一個(gè)運(yùn)算符作為標(biāo)記，此結(jié)點(diǎn)代表應(yīng)用該運(yùn)算符對其直接后繼

6、結(jié)點(diǎn)所表示的值進(jìn)行運(yùn)算的結(jié)果。 (3) 圖中各個(gè)結(jié)點(diǎn)上可能附加一個(gè)或多個(gè)標(biāo)識符，表示這些變量具有該結(jié)點(diǎn)所代表的值。 圖51給出了不同四元式和與其對應(yīng)的DAG 結(jié)點(diǎn)形式。,圖中各結(jié)點(diǎn)圓圈中的 ni 是構(gòu)造DAG過程中各結(jié)點(diǎn)的編號，而各結(jié)點(diǎn)下面的符號(運(yùn)算符、標(biāo)識符或常數(shù))是各結(jié)點(diǎn)的標(biāo)記，各結(jié)點(diǎn)右邊的標(biāo)識符是結(jié)點(diǎn)上的附加標(biāo)識符。 除了對應(yīng)轉(zhuǎn)移語句的結(jié)點(diǎn)右邊可附加一語句位置來指示轉(zhuǎn)移目標(biāo)外，其余各類結(jié)點(diǎn)的右邊只允許附加標(biāo)識符。除對應(yīng)于數(shù)組元素賦值的結(jié)點(diǎn)(標(biāo)記為 =)有三個(gè)后繼外，其余結(jié)點(diǎn)最多只有兩個(gè)后繼。,利用DAG進(jìn)行基本塊優(yōu)化的基本思想： 首先按基本塊內(nèi)的四元式序列順序?qū)⑺械乃脑綐?gòu)造成一個(gè)D

7、AG，然后按構(gòu)造結(jié)點(diǎn)的次序?qū)AG還原成四元式序列。 由于在構(gòu)造DAG的同時(shí)已作了局部優(yōu)化，所以最后所得到的是優(yōu)化過的四元式序列。,為了DAG構(gòu)造算法的需要，將圖51中的四元式按照其對應(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)。,說明：對于3型四元式，對于數(shù)組賦值的情形需特殊考慮，暫不討論。對四元式(7)也不涉及，下面僅討論含0、1、2型四元式的基本塊的DAG構(gòu)造算法。 規(guī)定

8、：用大寫字母(如A、B等)表示四元式中的變量名(或常數(shù))；用函數(shù)Node(A)表示A在DAG中的相應(yīng)結(jié)點(diǎn)，其值記為n(用n表示DAG中的一個(gè)結(jié)點(diǎn)值)或者無定義(未命名或未加標(biāo)記)。,形如“A=B”的0型四元式的構(gòu)造算法,(1) 若 Node(B) 無定義，則構(gòu)造一標(biāo)記為B的葉結(jié)點(diǎn)并定義為Node(B) ，并記 Node(B) 的值為n。,僅含0、1、2型四元式的基本塊DAG構(gòu)造算法分別描述如下(算法開始前， DAG為空)：,(2) 若 Node(A) 無定義，則把A附加在結(jié)點(diǎn) n 上并令Node(A)= n；否則，先從Node(A)的附加標(biāo)識符集中將A刪去(注意: 若Node(A)是葉結(jié)點(diǎn),

9、則不能將A刪去)，然后再把A附加到新結(jié)點(diǎn)n上，并令Node(A)=n。,優(yōu)化工作：刪除無用賦值,形如“A=op B”的1型四元式的構(gòu)造算法,(1)若Node(B)無定義，則構(gòu)造一標(biāo)記為B的葉結(jié)點(diǎn)并定義為Node(B),(5)若Node(A)無定義，則把A附加在結(jié)點(diǎn)n上并令Node(A)= n；否則先從Node(A)的附加標(biāo)識符集中將A刪去(注意: 若Node(A)是葉結(jié)點(diǎn), 則不能將A刪去)，然后再把A附加到新結(jié)點(diǎn)n上，并令Node(A)=n。,(4)檢查DAG中是否有標(biāo)記為op且以Node(B)為惟一后繼的結(jié)點(diǎn)。若有，則把已有的結(jié)點(diǎn)作為它的結(jié)點(diǎn)并設(shè)該結(jié)點(diǎn)為n；若沒有，則構(gòu)造一個(gè)新結(jié)點(diǎn)；轉(zhuǎn)(5

10、)。,刪除無用賦值,查找公共子表達(dá)式，刪除多余運(yùn)算,合并已知量,形如“A=B op C”的1型四元式的構(gòu)造算法,(1)若 Node(B) 無定義，則構(gòu)造一標(biāo)記為 B 的葉結(jié)點(diǎn)，并定義為Node(B)；如果Node(C)無定義，則構(gòu)造一標(biāo)記為C的葉結(jié)點(diǎn)，并定義為Node(C)。,(2)若Node(B)和Node(C)都是以常數(shù)標(biāo)記的葉結(jié)點(diǎn)，則轉(zhuǎn)(3)，否則轉(zhuǎn)(4)。 (3)執(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)(5)。,(4)檢查DAG中是否

11、有標(biāo)記為op且其左后繼為Node(B)、右后繼為Node(C)的結(jié)點(diǎn)。若有，則把已有的結(jié)點(diǎn)作為它的結(jié)點(diǎn)并設(shè)該結(jié)點(diǎn)為n；若沒有，則構(gòu)造一個(gè)新結(jié)點(diǎn)；轉(zhuǎn)(5)。,(5)若Node(A)無定義，則把A附加在結(jié)點(diǎn)n上并令Node(A)= n；否則先從Node(A)的附加標(biāo)識符集中將A刪去(注意: 若Node(A)是葉結(jié)點(diǎn), 則不能將A刪去)，然后再把A附加到新結(jié)點(diǎn)n上，并令Node(A)=n。,合并已知量,查找公共子表達(dá)式，刪除多余運(yùn)算,刪除無用賦值,解：按照算法順序處理每一四元式后構(gòu)造出的DAG如圖52所示，其中每一子圖(1)、(2)、(10)分別對應(yīng)四元式(1)(10)的DAG構(gòu)造。,(1) T0=

12、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,例5.1：構(gòu)造以下基本塊的DAG：,圖52 DAG,5.1.3 利用DAG進(jìn)行基本塊的優(yōu)化處理 利用DAG進(jìn)行基本塊優(yōu)化處理的基本思想是：按照構(gòu)造DAG結(jié)點(diǎn)的順序，對每一個(gè)結(jié)點(diǎn)寫出其相應(yīng)的四元式表示。根據(jù)例5.1 DAG結(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

13、=T2 (6) A=6.28*T2 (7) T5=A (8) T6= Rr (9) B=A*T6,因此，G 是對G實(shí)現(xiàn)上述三種優(yōu)化的結(jié)果。,(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,(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相比，可以

14、看到：,通過觀察DAG圖中的所有葉結(jié)點(diǎn)和內(nèi)部結(jié)點(diǎn)以及其上的附加標(biāo)識符，可以得出以下結(jié)論： 在基本塊外被定值并在基本塊內(nèi)被引用的所有標(biāo)識符就是DAG中相應(yīng)葉結(jié)點(diǎn)上標(biāo)記的標(biāo)識符； 在基本塊內(nèi)被定值且該值能在基本塊后面被引用的標(biāo)識符就是DAG各結(jié)點(diǎn)上的附加標(biāo)識符。,以上結(jié)論可以引導(dǎo)優(yōu)化工作的進(jìn)一步深入，尤其是無用賦值的優(yōu)化： 如果DAG中某結(jié)點(diǎn)上的標(biāo)識符在該基本塊之后不會(huì)被引用，就可以不生成對該標(biāo)識符賦值的四元式。 如果某結(jié)點(diǎn) ni 上沒有任何附加標(biāo)識符，或者 ni 上的附加標(biāo)識符在該基本塊之后不會(huì)被引用，而且 ni 也沒有前驅(qū)結(jié)點(diǎn)，這表明在基本塊內(nèi)和基本塊之后都不會(huì)引用 ni 的值，那么就不生成計(jì)

15、算 ni 結(jié)點(diǎn)值的四元式。 如果有兩個(gè)相鄰的四元式A=C op D和B=A，其中第一條代碼計(jì)算出來的A值僅在第二個(gè)四元式中被引用，則將DAG中相應(yīng)結(jié)點(diǎn)重寫成四元式時(shí)，原來的兩個(gè)四元式可以優(yōu)化為B=C op D。,說明： 把DAG重寫成四元式序列時(shí)，是按照原來構(gòu)造DAG結(jié)點(diǎn)的順序依次進(jìn)行的。實(shí)際上，還可以采用其它順序(如自下而上)重寫，只要其中的任何一個(gè)內(nèi)部結(jié)點(diǎn)是在其后繼結(jié)點(diǎn)之后被重寫并且轉(zhuǎn)移語句(如果有的話)仍然是基本塊的最后一個(gè)語句即可。,5.1.4 DAG構(gòu)造算法的進(jìn)一步討論 自學(xué) 當(dāng)基本塊中有數(shù)組元素引用、指針和過程調(diào)用時(shí)，構(gòu)造DAG算法就較為復(fù)雜。例如，考慮如下的基本塊G： (1) x

16、=ai (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)造對數(shù)組a的元素賦值句的結(jié)點(diǎn)時(shí)，就“注銷”所有標(biāo)記為 且左邊變量是a(可加上或減去一個(gè)常數(shù))的結(jié)點(diǎn)。對這樣的結(jié)點(diǎn)再添加附加標(biāo)識符是非法的，從而取消了它作為公共子表達(dá)式的資格。,對指針賦值語句*p=

17、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)識符(包括作為葉結(jié)點(diǎn)上標(biāo)記的標(biāo)識符)都予以注銷，這也就意味著DAG中所有的結(jié)點(diǎn)也都被注銷。,在一個(gè)基本塊中的一個(gè)過程調(diào)用將注銷所有的結(jié)點(diǎn)，因?yàn)閷Ρ徽{(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=y則必須跟在x

18、=ai之后。下面，根據(jù)上述討論把重寫四元式時(shí)DAG中結(jié)點(diǎn)間必須遵守的順序歸納如下：,(1) 對數(shù)組a中任何元素的引用或賦值，都必須跟在原來位于其前面的(如果有的話，下同)對數(shù)組a任何元素的賦值之后；對數(shù)組a任何元素的賦值，都必須跟在原來位于其前面的對數(shù)組a任何元素的引用之后。 (2) 對任何標(biāo)識符的引用或賦值，都必須跟在原來位于其前面的任何過程調(diào)用或通過指針的間接賦值之后；任何過程調(diào)用或通過指針的間接賦值，都必須跟在原來位于其前面的任何標(biāo)識符的引用或賦值之后。,5.2 循環(huán)優(yōu)化,5.2.1 程序流圖與循環(huán) 為了進(jìn)行循環(huán)優(yōu)化，必須先找出程序中的循環(huán)。由程序語言的循環(huán)語句形成的循環(huán)是不難找出的，但

19、由條件轉(zhuǎn)移語句和無條件轉(zhuǎn)移語句同樣可以形成程序中的循環(huán)，并且其結(jié)構(gòu)更加復(fù)雜。 為找出程序中的循環(huán)，需要對程序中的控制流程進(jìn)行分析?？梢詰?yīng)用程序的控制流程圖來定義循環(huán)，并找出程序中的循環(huán)。,控制流程圖(簡稱流圖)就是具有惟一首結(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)。 流圖的有限結(jié)點(diǎn)集N就是程序的基本塊集，流圖中的結(jié)點(diǎn)就是程序的基本塊，流圖的首結(jié)點(diǎn)就是包含程序第一個(gè)語句的基本塊。,流圖的有向邊集E的構(gòu)成：假設(shè)流圖中結(jié)點(diǎn)i和結(jié)點(diǎn)j分別

20、對應(yīng)于程序的基本塊i和基本塊j，當(dāng)下述條件有一個(gè)成立時(shí)，從結(jié)點(diǎn)i有一條有向邊引到結(jié)點(diǎn)j： 基本塊j在程序中的位置緊跟在基本塊i之后，并且基本塊i的出口語句不是無條件轉(zhuǎn)移語句goto(s)或停語句。 基本塊i的出口語句是goto(s)或if goto(s)，并且(s)是基本塊j的入口語句。,程序流圖和基本塊的DAG區(qū)別： 程序流圖是對整個(gè)程序而言的，它表示了各基本塊(對應(yīng)流圖中的一個(gè)結(jié)點(diǎn))之間的控制關(guān)系，圖中可以出現(xiàn)環(huán)路； DAG是對基本塊而言的，是局限于該基本塊內(nèi)的無環(huán)路有向圖，它表示了這個(gè)基本塊內(nèi)各四元式的操作及相互關(guān)系。,以下面求最大公因子的三地址代碼程序?yàn)槔齺砬笃涑绦蛄鲌D。,(1) re

21、ad 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,圖53 求最大公因子的程序流圖,(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,B,1,B,2,B,3,B,4,在程序流圖中，稱具有下列性質(zhì)的結(jié)點(diǎn)序列為一個(gè)循環(huán)： (1) 它們是強(qiáng)連通的，其中任意兩個(gè)結(jié)點(diǎn)之間必有一條通路，而且該通路上各結(jié)點(diǎn)都屬于該結(jié)點(diǎn)

22、序列；如果序列只包含一個(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)。 例如，對圖53所示的程序流圖，結(jié)點(diǎn)序列B2，B3是程序中的一個(gè)循環(huán)，其中B2是循環(huán)的惟一入口結(jié)點(diǎn)。,圖54 所示的程序流圖，結(jié)點(diǎn)序列： 6 、 2, 3, 4, 5, 6, 7 4, 5, 6, 7 是強(qiáng)連通且有惟一入口結(jié)點(diǎn)，是我們所定義的循環(huán)。 而結(jié)點(diǎn)序列：2, 4 、 2, 3, 4 、 4, 5, 7 、 4, 6, 7 存在兩個(gè)入口結(jié)點(diǎn)，不是我們所定義的循環(huán)。,5.2.2

23、 循環(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)集的定義。 在程序流圖中，對任意結(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)；對任何結(jié)點(diǎn)n來說都有 n DOM n。 若將DOM視為流圖結(jié)點(diǎn)集上定義的關(guān)系，則具有下述性質(zhì)： (1) 自反性：流圖中任意結(jié)點(diǎn)a，都有a DOM a。 (2) 傳遞性：流圖中任意結(jié)點(diǎn)a、b、c，若有a DOM b與 b DOM

24、 c，則必有a DOM c。 (3) 反對稱性：若存在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)。 解：直接由定義和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; /*入口結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)集合只含

25、入口結(jié)點(diǎn)*/ for (nNn0) D(n)=N; /*置初值,所有結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)集合包括全部結(jié)點(diǎn)*/ Change = true; while (change) change = false; for (nNn0) /*對除入口結(jié)點(diǎn)外的所有結(jié)點(diǎn)*/ new = n(D(p); /* 其中pP(n)，D(p) 表示結(jié)點(diǎn)n的所有前驅(qū)(即:父結(jié)點(diǎn))的必經(jīng)結(jié)點(diǎn)的交集，即為n的必經(jīng)結(jié)點(diǎn)集*/ if (new!=D(n) change=true; D(n)=new; ,圖55 ni為nj的必經(jīng)結(jié)點(diǎn)示意,例5.3 應(yīng)用求流圖必經(jīng)結(jié)點(diǎn)集的算法求圖54流圖各結(jié)點(diǎn)n的D(n)。 解: 算法求解過程如下： 首先置

26、初值： 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)。,對結(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。 對結(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) = 1,2,3。 其余各結(jié)點(diǎn)按照上述步驟可

27、求出： 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)。 對結(jié)點(diǎn)2: new =2D(1)D(4) =211,2,4 =21=1,2 而迭代前D(2)=1,2，所以D(2)=new，故D(2)不變。,對結(jié)點(diǎn)3: new

28、= 3D(2) = 31,2 = 1,2,3 迭代前D(3)=1,2,3，所以D(3)=new，故D(3)不變。 對其余結(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是流圖中的一條回邊。 如果已知有向邊nd(d是n的必經(jīng)結(jié)點(diǎn))是一條回邊，則由它組成的循環(huán)就是: 由結(jié)點(diǎn)d、結(jié)點(diǎn)n以及有通路到達(dá)n但該通路不經(jīng)過d的所有結(jié)點(diǎn)組成的

29、。 對于已知流圖G，只要求出各結(jié)點(diǎn)n的必經(jīng)結(jié)點(diǎn)集，就可以求出流圖中的所有回邊，通過回邊就可以求出流圖中的循環(huá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是回邊。 容易看出，其它有向邊都不是回邊。,尋找由回邊(nd)組成循環(huán)的算法： main ( ) stack=空; /* stack是一個(gè)工作棧 */ loop=d; /* nd是一條回邊， loop是所

30、求的循環(huán) */ insert(n); while (stack非空) 彈出stack棧頂元素m; for (pP(m) /* P(m)為結(jié)點(diǎn)m的前驅(qū)結(jié)點(diǎn)(父結(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)。然后再對新求出的所有前驅(qū)重復(fù)上述過程，直到所

31、求出的前驅(qū)都是d為止。,圖5-4中的循環(huán)如下： 必經(jīng)結(jié)點(diǎn)集合： 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 回邊： 循環(huán)： 666 744,5,6,7 422,3,4,5,6,7,3可歸約流圖 一個(gè)流圖被稱為可歸約的，當(dāng)且僅當(dāng)流圖中除去回邊之外，其余的邊構(gòu)成一個(gè)無環(huán)路流圖。 例如，圖54中的流圖就是一個(gè)可歸約流圖，而圖55則是一個(gè)不可歸約流圖，因?yàn)閳D56中雖然有23，但沒有3 DOM 2，即23不是一個(gè)回邊，對32也是如此。,如果程序流圖是可歸約的，那么程序中任何可能反復(fù)執(zhí)行的代碼都會(huì)

32、被由回邊求循環(huán)的算法納入到一個(gè)循環(huán)當(dāng)中。從代碼優(yōu)化的角度來說，可歸約流圖具有下述3個(gè)重要的性質(zhì)： (1) 圖中任何直觀意義下的環(huán)路都屬于我們所定義的循環(huán)。 (2) 只要找出圖中的所有回邊，對回邊應(yīng)用查找循環(huán)的方法就可以找出流圖中的所有循環(huán)。 (3) 圖中任意兩個(gè)循環(huán)要么嵌套，要么不相交(除了可能有公共的入口結(jié)點(diǎn))，對這類流圖進(jìn)行循環(huán)優(yōu)化較為容易。 應(yīng)用結(jié)構(gòu)化程序設(shè)計(jì)原則寫出的程序，其流圖總是可歸約的。,例5.4：四元式序列如下： (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 got

33、o 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) halt 畫出該四元式序列的程序流圖G并求出G中的回邊與循環(huán)。,解：該四元式序列的基本塊與程序流圖如圖所示。各結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)集如下： D(B1)=B1 D(B2)=B1,B2 D(B3)=B1,B2,B3 D(B4)=B1,B2,B4 D(B5)=B1,B2,B4,B5 D(B6)=B1,B2,B4,B6 D(B7)=B1,B2,B4,B7 D(B8)=B1,B2,B4,B7,B8

34、,考查流圖中的有向邊B7B2 已知D(B7) = B1,B2,B4,B7，所以有B2 DOM B7，即B7B2是流圖中的回邊。容易看出，其它有向邊都不是回邊。 因B7B2是一條回邊，則在流圖中能夠不經(jīng)過結(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,5.2.3 循環(huán)優(yōu)化 對循環(huán)中的代碼，可以實(shí)行代碼外提、強(qiáng)度削弱和刪除歸納變量等優(yōu)化。 1代碼外提 代碼外提是將循環(huán)中的不變運(yùn)算提到循環(huán)前面。不變運(yùn)算是指其運(yùn)算結(jié)果不受循環(huán)影響的表達(dá)式。,實(shí)行代碼外提優(yōu)化前，在循環(huán)唯一入口結(jié)點(diǎn)前面建立一個(gè)新結(jié)點(diǎn)，稱為循環(huán)的

35、前置結(jié)點(diǎn)。循環(huán)前置結(jié)點(diǎn)以循環(huán)入口結(jié)點(diǎn)為其惟一后繼，原來流圖中從循環(huán)外引到循環(huán)入口結(jié)點(diǎn)的有向邊改成引到循環(huán)前置結(jié)點(diǎn)，如圖58所示。,圖58 給循環(huán)建立前置結(jié)點(diǎn),循環(huán)中的不變運(yùn)算并不是在任何情況下都可以外提，對循環(huán)L中的不變運(yùn)算S(S:A=B op C 或 A=op B 或A=B)，要求滿足下述條件才可以進(jìn)行外提： (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所示的三種流圖可以對上述三個(gè)條件予以說明。,圖59 代碼外提的程序流圖示例,圖510 將圖58(a)中的I=2外提后的程序

36、流圖,圖59(a)中 B3不是出口結(jié)點(diǎn)B4的必經(jīng)結(jié)點(diǎn)，將B3中的循環(huán)不變運(yùn)算I=2外提到循環(huán)前置結(jié)點(diǎn)B2中，將改變原來程序運(yùn)行的結(jié)果，如圖510所示。,外提后改變了原來程序運(yùn)行的結(jié)果，故此種情況不能進(jìn)行外提。,查找循環(huán)L中“不變運(yùn)算”的算法： (1)依次查看L中各基本塊的每個(gè)四元式，如果它的每個(gè)運(yùn)算對象或?yàn)槌?shù)、或定值點(diǎn)在L外，則將此四元式標(biāo)記為“不變運(yùn)算”。 (2)依次查看尚未被標(biāo)記為“不變運(yùn)算”的四元式，如果它的每個(gè)運(yùn)算對象或?yàn)槌?shù)、或定值點(diǎn)在L之外、或只有一個(gè)定值點(diǎn)可以到達(dá)且該點(diǎn)上的四元式已標(biāo)記為“不變運(yùn)算”，則把被查看的四元式標(biāo)記為“不變運(yùn)算”。 例如：循環(huán)中的A=3已標(biāo)記為“不變運(yùn)算

37、”，則對循環(huán)中A=3定值點(diǎn)可惟一到達(dá)的X=A+2也標(biāo)記為“不變運(yùn)算”（若有多個(gè)對A的定值點(diǎn)可達(dá)X=A+2，X的值將會(huì)因A的不同定值而變化，則不能進(jìn)行標(biāo)記）。 (3)重復(fù)(2)直至沒有新的四元式被標(biāo)記為“不變運(yùn)算”。,代碼外提算法： (1) 求出循環(huán)L的所有不變運(yùn)算。 (2) 對步驟(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的引用點(diǎn)只有S中A的定值才能到達(dá)。, A在離開L后不再是活躍的，并且條件的ii.和iii.成立。 所

38、謂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)算對象(B或C)是在L中定值的，那么只有當(dāng)這些定值四元式都已外提到前置結(jié)點(diǎn)中時(shí)，才可把S也外提到前置結(jié)點(diǎn)中(B、C的定值四元式提到前置結(jié)點(diǎn)后，S的運(yùn)算對象B、C就屬于定值點(diǎn)在L之外，因此也就是真正的“不變運(yùn)算”)。,圖511 例5.5的程序流圖,例5.5: 試對圖511給定的程序流圖進(jìn)行代碼外提優(yōu)化。 解: 程序流圖中不變運(yùn)算是B3中的I=2和B4中的J=M+N。 進(jìn)行代碼

39、外提時(shí)，只能將J=M+N提到循環(huán)前置結(jié)點(diǎn)，而B3中的I=2不能外提。代碼外提后的程序流圖如圖512。,圖512 代碼外提后的程序流圖,2強(qiáng)度削弱 強(qiáng)度削弱是指把程序中執(zhí)行時(shí)間較長的運(yùn)算替換為執(zhí)行時(shí)間較短的運(yùn)算。強(qiáng)度削弱不僅可對乘法運(yùn)算實(shí)行(將循環(huán)中的乘法運(yùn)算用遞歸加法運(yùn)算來替換)，對加法運(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)中刪除。,例5.6 對圖513給定的程序

40、流圖進(jìn)行強(qiáng)度削弱優(yōu)化。 解: 圖中B2的A=K*I和B=J*I因K、J的定值都在循環(huán)之外，可將K、J視為常量，而每次循環(huán)I=I+1時(shí)，對應(yīng)A=K*I和B=J*I分別增加K和J。因此，可以將A=K*I和B=J*I外提到前置結(jié)點(diǎn)B2中，同時(shí)在B2的I=I+1之后分別給A和B增加一個(gè)常量 K和J。強(qiáng)度削弱后的流圖如圖514。,圖513 程序流圖,圖514 強(qiáng)度削弱后的流圖,例5.7 對圖515給定的程序流圖進(jìn)行強(qiáng)度削弱優(yōu)化。（加法強(qiáng)度削弱） 解: B2中的C=B+I，B的定值點(diǎn)在循環(huán)之外，故相當(dāng)于常數(shù)；而另一加數(shù)I值由B3中的I=I+1決定；因此，B2中C=B+I的C值增量與B3中的I相同，為常數(shù)1

41、。 可以對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所示。,圖515 例5.7的程序流圖,圖516 例5.7強(qiáng)度削弱后的流圖,例5.8 試對圖5-17給定的程序流圖進(jìn)行強(qiáng)度削弱優(yōu)化。 解:B3中的T2是遞歸賦值的變量，每循環(huán)一次增加10。由T3=T2+T1計(jì)算T3時(shí)要引用T2，另一運(yùn)算對象T1是循環(huán)不變量，所以每循環(huán)一次，T3值的增量與T2相同，即常數(shù)10。因此，可以對T3進(jìn)行強(qiáng)度削弱，即將T3=T2+T1外提到前置結(jié)點(diǎn)B2中，同時(shí)在T2=T2+10的后面給T3增加一個(gè)常量10。強(qiáng)度削弱后的結(jié)果

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

43、歸納變量或變換循環(huán)控制條件。 刪除歸納變量在強(qiáng)度削弱以后進(jìn)行。,下面一并給出強(qiáng)度削弱和刪除歸納變量的算法： (1) 利用循環(huán)不變運(yùn)算信息，找出循環(huán)L中所有基本歸納變量。 (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與基本歸

44、納變量D同族且它們的函數(shù)關(guān)系為FB(D)，那么若L外B的定值點(diǎn)不能到達(dá)S，且L中B的定值點(diǎn)與S之間未曾對D定值，則X就是D，A與基本歸納變量D是同族的歸納變量，且A與D的函數(shù)關(guān)系是： FA(D)=C*B=C*FB(D)。,(3) 進(jìn)行強(qiáng)度削弱優(yōu)化 對(2)中找出的每一歸納變量A，假設(shè)A與基本歸納變量B同族，且A與B的函數(shù)關(guān)系為FA(B)=C1*B+C2，其中C1和C2均為循環(huán)不變量，執(zhí)行以下步驟： 建立一個(gè)新的臨時(shí)變量SFA(B) 。若兩個(gè)歸納變量A和A都與B同族且FA(B)=FA(B)，則只建立一個(gè)臨時(shí)變量。 在循環(huán)前置結(jié)點(diǎn)原有的四元式后增加如下四元式： SFA(B) =C1*B SFA(B

45、) = SFA(B) +C2 (實(shí)現(xiàn)A=C1*B+C2) 如果C2=0，則無四元式SFA(B) = SFA(B) +C2 。, 把循環(huán)中原來對A賦值的四元式改為A= SFA(B) 。 在循環(huán)中基本歸納變量B的惟一賦值B=BE (E是循環(huán)不變量)后增加如下四元式： SFA(B) = SFA(B) C1*E 注：B增減E則A相應(yīng)地增減C1*E，即SFA(B)增減 C1*E。 如果C11，且E是變量名，則上式為： T= C1*E SFA(B) = SFA(B) T 其中T為臨時(shí)變量。,(4) 刪除對歸納變量的無用賦值 依次考察第(3)步中每一歸納變量A，如果在 A= SFA(B) 與循環(huán)中任何引用A

46、的四元式之間沒有對 SFA(B) 的賦值且A在循環(huán)出口之后不活躍，則刪除 A= SFA(B) 并把所有引用A的地方改為引用SFA(B) 。,(5) 刪除基本歸納變量 如果基本歸納變量 B 在循環(huán)出口之后不是活躍的，并且在循環(huán)中除在其自身的遞歸賦值中被引用外，只在形為 if B rop Y goto Z (或 if Y rop B goto Z)中被引用，則： 選取一個(gè)與B同族的歸納變量M, 設(shè)FM(B)=C1*B+C2 說明：盡可能使所選M的FM(B)簡單，并且可能的話，使M是循環(huán)中其它四元式要引用的，或者是循環(huán)出口之后的活躍變量。, 建立一臨時(shí)變量 R，并用下列四元式來替換 if B rop

47、 Y goto Z 四元式： R=C1* Y R=R+ C2 if FM(B) rop R goto Z 即將原判斷條件： B rop Y 改為：(C1*B+C2)rop(C1*Y+C2) 也就是：FM(B) rop R 刪除循環(huán)中對B遞歸賦值的四元式。,例5.9 對圖5-14給定的程序流圖進(jìn)行刪除歸納變量優(yōu)化。 解：由圖5-14可知，循環(huán)中I是基本歸納變量，A、B是與I同族的歸納變量且具有如下的線性關(guān)系： A=K*I B=J*I,圖514 強(qiáng)度削弱后的流圖,循環(huán)控制條件I100完全可用A100*K或B100*J來替代。這樣，基本塊B2中的控制條件和控制語句可改寫為： T1=100*K if AT1 goto L 或者改寫為： T2=100*J if B T2 goto L 程序流圖如圖519。,圖519 變換循環(huán)控制條件的流圖,循環(huán)控制條件經(jīng)過以上改變之后，就可以刪除基本塊B2中的語句I=I+1；而語句T1=100*K是循環(huán)中的不變運(yùn)算，故可由基本塊B2外提到基本塊B2。 最后，經(jīng)刪除歸納變量及代碼外提后得到的程序流圖如圖520所示。,5.3 代碼優(yōu)化示例,通過用C語言編寫的快速排序子程序示例進(jìn)一步了解代碼優(yōu)化的全過程： void quicksort (m, n) int m, n; int i,j; int v, x; if(nv); if(i=j) break;,x