第8章代碼優(yōu)化

1、v 解釋優(yōu)化的基本概念以及代碼優(yōu)化器的地位和結(jié)構(gòu)解釋優(yōu)化的基本概念以及代碼優(yōu)化器的地位和結(jié)構(gòu)v 說明編譯程序進(jìn)行代碼變換應(yīng)遵循的原則說明編譯程序進(jìn)行代碼變換應(yīng)遵循的原則v 通過實例說明代碼優(yōu)化通常采用的基本方法通過實例說明代碼優(yōu)化通常采用的基本方法v 介紹基本塊的概念及其劃分算法介紹基本塊的概念及其劃分算法v 說明程序流圖的構(gòu)造方法說明程序流圖的構(gòu)造方法v 介紹基本塊的介紹基本塊的DAG表示方法表示方法v 介紹循環(huán)優(yōu)化一般采用的方法介紹循環(huán)優(yōu)化一般采用的方法8.1 8.1 優(yōu)化概述優(yōu)化概述8.2 8.2 局部優(yōu)化局部優(yōu)化8.3 8.3 循環(huán)優(yōu)化循環(huán)優(yōu)化8.4 8.4 本章小結(jié)本章小結(jié)（1）優(yōu)化

2、的含義對程序進(jìn)行各種等價變換，使得從變換后的程序出發(fā)，能生成更有效的目標(biāo)代碼，稱這種變換為。（2）優(yōu)化分類根據(jù)編譯階段的不同劃分u與機器無關(guān)的中間代碼優(yōu)化與機器無關(guān)的中間代碼優(yōu)化u依賴于機器的目標(biāo)代碼優(yōu)化依賴于機器的目標(biāo)代碼優(yōu)化根據(jù)優(yōu)化對象所涉及的程序范圍劃分u局部優(yōu)化局部優(yōu)化u循環(huán)優(yōu)化循環(huán)優(yōu)化u全局優(yōu)化全局優(yōu)化 （3）代碼優(yōu)化器的地位 有很多技術(shù)和手段可以用于中間代碼這一級上的優(yōu)化?？傮w上講在一個編譯程序中優(yōu)化器的地位和結(jié)構(gòu)如下圖：（4）代碼優(yōu)化遵循的原則優(yōu)化的目的是為了產(chǎn)生更高效的代碼。由優(yōu)化編譯程序提供的，對代碼的各種變換必須遵循以下三個原則： 經(jīng)過優(yōu)化后不應(yīng)改變程序運行的結(jié)果。經(jīng)過優(yōu)化

3、后不應(yīng)改變程序運行的結(jié)果。 使優(yōu)化后所產(chǎn)生的目標(biāo)代碼運行時間較短，占用的存儲空間使優(yōu)化后所產(chǎn)生的目標(biāo)代碼運行時間較短，占用的存儲空間較小。較小。 應(yīng)盡可能以較低的代價取得較好的優(yōu)化效果。應(yīng)盡可能以較低的代價取得較好的優(yōu)化效果。（5）常用的代碼優(yōu)化的方法 刪除公共子表達(dá)式（刪除多余運算）刪除公共子表達(dá)式（刪除多余運算） 復(fù)寫傳播復(fù)寫傳播 刪除無用代碼（刪除無用賦值）刪除無用代碼（刪除無用賦值） 合并已知量合并已知量 代碼外提代碼外提 強度削弱強度削弱刪除歸納變量刪除歸納變量循環(huán)優(yōu)化（6）代碼優(yōu)化舉例我們通過一個高級語言程序的例子來了解代碼優(yōu)化的全過程。下面是一個用C語言編寫的快速排序子程序：vo

4、id quicksort (int m, int n) 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);通過第6章的中間代碼生成方法可以產(chǎn)生這個程序的中間代碼。圖82給出了程序中兩個注解行之間的語句翻譯成中間代碼序列后所對應(yīng)的程序流圖，對圖82程

5、序流圖的代碼優(yōu)化敘述如下。刪除公共子表達(dá)式如果一個表達(dá)式E在前面已計算過，并且在這之后E中變量的值沒有改變，則稱E為。在圖82的B5中分別把公共子表達(dá)式4*i和4*j的值賦給T7和T10，因此這種重復(fù)計算可以消除，即B5中的代碼變換成：T6:=4*ix:=aT6T7:=4*iT8:=4*jT9:=aT8aT7:=T9T10:=4*jaT10:=xgoto B2T6:=4*ix:=aT6T7:=T6T8:=4*jT9:=aT8aT7:=T9T10:=T8aT10:=xgoto B2對B5刪除了公共子表達(dá)式后，仍然要計算4*i和4*j ，我們還可以在更大范圍內(nèi)來考慮刪除公共子表達(dá)式的問題，即利用B

6、3中的四元式T4:=4*j可以把B5中的代碼T8:=4*j替換為T8:=T4。 同樣，利用B2中的賦值句T2:=4*i可以把B5中的代碼T6:=4*i替換為T6:=T2。 對于B6也可以同樣考慮，最后，刪除公共子表達(dá)式后的程序流圖如圖83所示。復(fù)寫傳播圖83中的B5還可以進(jìn)一步改進(jìn)，四元式T6:=T2把T2賦給了T6，而四元式x:=aT6中引用了T6的值，但這中間并沒有改變T6的值。因此，可以把x:=aT6變換為x:=aT2。這種變換稱為。用復(fù)寫傳播的方法可以把B5變?yōu)椋篢6:=T2x:=aT6T7:=T6T8:=T4T9:=aT8aT7:=T9T10:=T8aT10:=xgoto B2T6:

7、=T2x:=aT2T7:=T2T8:=T4T9:=aT4aT2:=T9T10:=T4aT4:=xgoto B2作進(jìn)一步的考察可以發(fā)現(xiàn)，在B2中計算了T3:= aT2，因此在B5中可以刪除公共子表達(dá)式，即把x:=aT2替換為x:=T3，并繼續(xù)通過復(fù)寫傳播，把B5中的aT4:=x替換為aT4 :=T3。 同樣，把B5中的T9:=aT4替換為T9:=T5，aT2:=T9替換為 aT2:=T5。 這樣B5就變?yōu)椋篢6:=T2x:=T3T7:=T2T8:=T4T9:=T5aT2:=T5T10:=T4aT4:=T3goto B2T6:=T2x:=aT2T7:=T2T8:=T4T9:=aT4aT2:=T9T

8、10:=T4aT4:=xgoto B2復(fù)寫傳播的目的是：使得對某些變量的賦值變?yōu)闊o用。刪除無用賦值對于進(jìn)行了復(fù)寫傳播后的B5，其中的變量x及臨時變量T6、T7、T8、T9、T10在整個程序中不再使用，故可以刪除對這些變量賦值的代碼。刪除無用賦值后B5變?yōu)椋?aT2:= T5 aT4:= T3 goto B2對B6進(jìn)行相同的復(fù)寫傳播和刪除無用賦值后變?yōu)椋?aT2:= v aT1:= T3復(fù)寫傳播和刪除無用賦值后的程序流圖如圖8-4所示。代碼外提對于循環(huán)中的有些代碼，如果它產(chǎn)生的結(jié)果在循環(huán)中是不變的，就可以把它提到循環(huán)外來，以避免每循環(huán)一次都要對這條代碼進(jìn)行運算。這種變換稱之為。如： while(

9、i=limit-2) . 可變換為： t:=limit-2 while(i=t). 考察圖84，沒有發(fā)現(xiàn)可外提到循環(huán)之外的不變運算。 強度削弱觀察圖84的內(nèi)循環(huán)B3，每循環(huán)一次，j的值減1；而T4的值始終與j保持著T4=4*j的線性關(guān)系，即每循環(huán)一次，T4值隨之減少4。因此，我們可以把循環(huán)中計算T4值的乘法運算變?yōu)樵谘h(huán)前進(jìn)行一次乘法運算而在循環(huán)中進(jìn)行減法運算。同樣，對循環(huán)B2中的T2=4*i也可以進(jìn)行強度削弱。經(jīng)過強度削弱后的程序流圖如圖8-5所示。 刪除歸納變量由圖84可知，B2中每循環(huán)一次，i值加1，T2與i之間保持著T2=4*i的線性關(guān)系；而B3中每循環(huán)一次，j值減1，T4與j之間保持

10、著T4=4*j的線性關(guān)系。這種變量我們稱之為。 在對T2=4*i和T4=4*j進(jìn)行了強度削弱后，i和j僅出現(xiàn)在條件句if ij goto B6中，其余地方不再被引用。因此，我們可以變換歸納變量而把此條件句變換為：if T2T4 goto B6。經(jīng)過這種變換，我們又可以將無用賦值i=i+1和j=j1刪去。刪除歸納變量后的程序流圖如圖86所示。 通過上述各種優(yōu)化，最終得到圖86的優(yōu)化結(jié)果。比較圖82和圖86可知：B2和B3中的四元式從4條減為2條，而且一條是由乘法變?yōu)榧臃ǎ籅5中的四元式由9條變?yōu)?條，B6中的四元式由8條變?yōu)?條。以上這些優(yōu)化對循環(huán)執(zhí)行來說，效果是非常明顯的。雖然B1的四元式由4

11、條變?yōu)?條，但因其僅被執(zhí)行一次，所以影響甚微。 返回基本塊及流圖基本塊及流圖 1基本塊的基本塊的DAG表示及其應(yīng)用表示及其應(yīng)用 2（1）基本塊所謂，是指程序中一順序執(zhí)行的語句序列，其中只有一個入口和一個出口，入口就是其中的第一個語句，出口就是其中的最后一個語句。對一個基本塊來說，執(zhí)行時只能從其入口進(jìn)入，從其出口退出。例如下面的三地址語句序列就形成了一個基本塊： T1:=a*a T2:=a*b T3:=2*T2 T4:=T1+T2 T5:=b*b T6:=T4+T5（2）定值和引用如果一條三地址語句為x:=y+z，則稱對x并y和z。（3）活躍的在一個基本塊中的一個名字，所謂在程序中的某個給定點是

12、，是指如果在程序中（包括在本基本塊或在其它基本塊中）它的值在該點以后被引用。（4）局部優(yōu)化局限于基本塊范圍內(nèi)的優(yōu)化稱為，或稱為。（5）劃分基本塊的算法求出四元式程序中各個基本塊的入口語句，它們是程序的第一個語句；或者程序的第一個語句；或者能由條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句轉(zhuǎn)移到的語句；或者能由條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句轉(zhuǎn)移到的語句；或者緊跟在條件轉(zhuǎn)移語句后面的語句。緊跟在條件轉(zhuǎn)移語句后面的語句。對以上求出的每一入口語句，構(gòu)造其所屬的基本塊，它是由該入口語句到另一入口語句（不包括該入口語句），或到一轉(zhuǎn)移語句（包括該轉(zhuǎn)移語句），或到一停語句（包括該停語句）之間的語句序列組成的。凡未被納入某一基本塊

13、中的語句，都是程序中控制流無法到達(dá)的語句。從而也是不會被執(zhí)行到的語句，可把它們從程序中刪除。【例 8.1】將以下求最大公因子的程序劃分為基本塊。read Xread YR:=X mod Yif R=0 goto X:=YY:=Rgoto write Yhalt解：解：（1）找入口語句 （2） 構(gòu)造基本塊 B1： B2： B3： B4：（6）基本塊內(nèi)可實現(xiàn)的變換 合并已知量合并已知量 臨時變量改名臨時變量改名 交換語句的位置交換語句的位置代數(shù)變換代數(shù)變換 （8）流圖一個（簡稱）就是具有唯一首結(jié)點的有向圖。所謂，就是從它開始到控制流程圖中任何一個結(jié)點都有一條通路的結(jié)點。我們可以把控制流程圖表示成一

14、個三元組G=(N,E,n0)；其中，N代表圖中所有結(jié)點集，E代表圖中所有有向邊集，n0代表首結(jié)點。 一個程序可用一個流圖來表示。流圖的有限結(jié)點集N就是程序的基本塊集，流圖中的結(jié)點就是程序的基本塊，流圖的首結(jié)點就是包含程序第一個語句的基本塊。流圖的有向邊集E是這樣構(gòu)成的：假設(shè)流圖中結(jié)點i和結(jié)點j分別對應(yīng)于程序的基本塊i和基本塊j，則當(dāng)下述條件有一個成立時，從結(jié)點i有一條有向邊引到結(jié)點j：（8）流圖 基本塊j在程序中的位置緊跟在基本塊i之后，并且基本塊i的出口語句不是無條件轉(zhuǎn)移語句goto(s)或停語句。 基本塊i的出口語句是goto(s)或if goto(s)，并且(s)是基本塊j的入口語句?；?/p>

15、本塊基本塊i.非非goto或或halt基本塊基本塊j基本塊基本塊i.if. goto(S)基本塊基本塊j(S).【例 8.2】將以下程序劃分為基本塊，并作出其程序流圖。read Xread YR:=X mod Yif R=0 goto X:=YY:=Rgoto write Yhaltread Xread YR:=X mod Yif R=0 goto X:=YY:=Rgoto write YhaltB1B2B4B3（1）基本塊的DAG表示基本特征 (Directed Acyclic Graph)是一種有向圖，常常用來對基本塊進(jìn)行優(yōu)化。一個基本塊的DAG是一種其結(jié)點帶有下述標(biāo)記或附加信息的DAG：

16、圖的葉結(jié)點(無后繼的結(jié)點)以一標(biāo)識符(變量名)或常數(shù)作為標(biāo)記，表示該結(jié)點代表該變量或常數(shù)的值。如果葉結(jié)點用來表示一變量A的地址，則用addr(A)作為該結(jié)點的標(biāo)記。通常把葉結(jié)點上作為標(biāo)記的標(biāo)識符加上下標(biāo)0，以表示它是該變量的初值。圖的內(nèi)部結(jié)點(有后繼的結(jié)點)以一運算符作為標(biāo)記，表示該結(jié)點代表應(yīng)用該運算符對其直接后繼結(jié)點所代表的值進(jìn)行運算的結(jié)果。圖中各個結(jié)點上可能附加一個或多個標(biāo)識符，表示這些變量具有該結(jié)點所代表的值。（2）基本塊的DAG表示 四元式與DAG結(jié)點 一個基本塊由一個四元式序列組成，且每一個四元式都可以用相應(yīng)的DAG結(jié)點表示。注：在以下各圖中u各結(jié)點圓圈中的各結(jié)點圓圈中的ni是構(gòu)造是

17、構(gòu)造DAG過程中各結(jié)點的編號。過程中各結(jié)點的編號。u各結(jié)點下面的符號各結(jié)點下面的符號(運算符、標(biāo)識符或常數(shù)運算符、標(biāo)識符或常數(shù))是各結(jié)點的標(biāo)記。是各結(jié)點的標(biāo)記。u各結(jié)點右邊的標(biāo)識符是結(jié)點上的附加標(biāo)識符。各結(jié)點右邊的標(biāo)識符是結(jié)點上的附加標(biāo)識符。u除了對應(yīng)轉(zhuǎn)移語句的結(jié)點右邊可附加一語句位置來指示轉(zhuǎn)移目標(biāo)外，除了對應(yīng)轉(zhuǎn)移語句的結(jié)點右邊可附加一語句位置來指示轉(zhuǎn)移目標(biāo)外，其余各類結(jié)點的右邊只允許附加標(biāo)識符。其余各類結(jié)點的右邊只允許附加標(biāo)識符。u除對應(yīng)于數(shù)組元素賦值的結(jié)點除對應(yīng)于數(shù)組元素賦值的結(jié)點(標(biāo)記為標(biāo)記為 =)有三個后繼外，其余結(jié)點有三個后繼外，其余結(jié)點最多只有兩個后繼。最多只有兩個后繼。、0型四元

18、式：后繼結(jié)點個數(shù)為0。n1ABn1(S)n1opBn2Aa) A:=Bb) goto (S)A:=op B、1型四元式：有一個后繼結(jié)點。、2型四元式：有兩個后繼結(jié)點。n1opBn3An2Cn1=Bn3An2Cn1ropBn3（S）n2Ca) A:= B op Cb) A:= BCc) if B rop C goto （S）、3型四元式：有三個后繼結(jié)點。DC :=Bn1=Dn4Bn2Cn3（3）僅含0,1,2 型中間代碼的基本塊DAG構(gòu)造算法 我們規(guī)定：用大寫字母(如A、B等)表示四元式中的變量名(或常數(shù))；用函數(shù)Node(A)表示A在DAG中的相應(yīng)結(jié)點，其值可為n或者無定義，并用n表示DAG中

19、的一個結(jié)點值。開始，DAG為空。對基本塊中每一條中間代碼式，依次執(zhí)行以下步驟。、如果NODE(B)無定義，則構(gòu)造一標(biāo)記為B的葉結(jié)點并定義NODE ( B)為這個結(jié)點。若當(dāng)前四元式是0型, 則記Node(B)的值為n, 轉(zhuǎn)。若當(dāng)前四元式是1型, 則轉(zhuǎn)。若當(dāng)前四元式是2型, 則：i.若Node(C)無定義，則構(gòu)造一標(biāo)記為C的葉結(jié)點, 并定義Node(C)為該結(jié)點；ii.轉(zhuǎn)。 若Node(B)是以常數(shù)標(biāo)記的葉結(jié)點，則轉(zhuǎn)，否則轉(zhuǎn)。若Node(B)和Node(C)都是以常數(shù)標(biāo)記的葉結(jié)點，則轉(zhuǎn)，否則轉(zhuǎn)。執(zhí)行op B(即合并已知量)，令得到的新常 數(shù)為P。n若若Node(B)是處理當(dāng)前四元式時新建立的結(jié)點，

20、則刪除它；是處理當(dāng)前四元式時新建立的結(jié)點，則刪除它；n若若Node(P)無定義，則構(gòu)造一個用無定義，則構(gòu)造一個用P做標(biāo)記的葉結(jié)點做標(biāo)記的葉結(jié)點n，并置，并置Node(P)= n；轉(zhuǎn)；轉(zhuǎn)。 執(zhí)行B op C(即合并已知量)，令得到的新常數(shù)為P。n若若Node(B)或或Node(C)是處理當(dāng)前四元式時新建立的結(jié)點則刪除它；是處理當(dāng)前四元式時新建立的結(jié)點則刪除它；n若若Node(P)無定義，則構(gòu)造一用無定義，則構(gòu)造一用P標(biāo)記的葉結(jié)點標(biāo)記的葉結(jié)點n，并置，并置Node(P)= n；轉(zhuǎn)；轉(zhuǎn)。 檢查DAG中是否有標(biāo)記為op且以Node(B)為唯一后繼的結(jié)點。n若有則把已有的結(jié)點作為它的結(jié)點，并設(shè)該結(jié)點為若

21、有則把已有的結(jié)點作為它的結(jié)點，并設(shè)該結(jié)點為n；n若沒有，則構(gòu)造一個新結(jié)點；轉(zhuǎn)若沒有，則構(gòu)造一個新結(jié)點；轉(zhuǎn)。檢查DAG中是否有標(biāo)記為op且其左后繼為Node(B)、右后繼為Node(C)的結(jié)點(即查找公共子表達(dá)式)。n若有，則把已有的結(jié)點作為它的結(jié)點，并設(shè)該結(jié)點為若有，則把已有的結(jié)點作為它的結(jié)點，并設(shè)該結(jié)點為n；n若沒有，則構(gòu)造一個新結(jié)點；轉(zhuǎn)若沒有，則構(gòu)造一個新結(jié)點；轉(zhuǎn)。若Node(A)無定義，則把A附加在結(jié)點n上，并令Node(A)= n；否則，先從Node(A)的附加標(biāo)識符集中將A刪去(若Node(A)是葉結(jié)點，則不能將A刪去)，然后再把A附加到新結(jié)點 n上，并令Node(A)=n。轉(zhuǎn)處理下

22、一代碼。（4）構(gòu)造DAG實例 【例 8.4】 試構(gòu)造以下基本塊G的DAG：(1) T0=3.14(2) T1:=2*T0(3)T2:=R+r(4) A: =T1*T2(5) B: =A(6) T3:=2*T0(7) T4:=R+r(8) T5:=T3*T4(9T6:=R-r(10) B:=T5*T6n13.14T0n26.28n3Rn4rT1(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

23、n5+T2n6*A,B,T3,T4,T5n7-T6n8*B（5）利用DAG進(jìn)行基本塊的優(yōu)化 利用DAG進(jìn)行基本塊優(yōu)化的基本思想：首先按基本塊內(nèi)的四元式序列順序?qū)⑺械乃脑綐?gòu)造成一個DAG，然后按構(gòu)造結(jié)點的次序?qū)AG還原成四元式序列。由于在構(gòu)造DAG的同時已作了局部優(yōu)化，所以最后所得到的是優(yōu)化過的四元式序列。例如，上例四元式序列經(jīng)優(yōu)化后得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*T6n13.14T0n2n3n4rT1n5+T2

24、n6*A,T3,T4,T5n7-T6n8*B6.28R將G和原基本塊G相比，我們看到： G中四元式中四元式(2)和和(6)都是已知量和已知量的運算，都是已知量和已知量的運算，G已合并；已合并； G中四元式中四元式(5)是一種無用賦值，是一種無用賦值，G已將它刪除；已將它刪除； G中四元式中四元式(3)和和(7)的的R+r是公共子表達(dá)式是公共子表達(dá)式,G只對它們計算了一次，只對它們計算了一次，即刪除了多余的即刪除了多余的R+r運算。運算。因此，G是對G實現(xiàn)上述三種優(yōu)化的結(jié)果。通過觀察上圖中的所有葉結(jié)點和內(nèi)部結(jié)點以及其上的附加標(biāo)識符，還可以得出以下結(jié)論： 在基本塊外被定值并在基本塊內(nèi)被引用的所有標(biāo)

25、識符就是在基本塊外被定值并在基本塊內(nèi)被引用的所有標(biāo)識符就是DAG中中相應(yīng)葉結(jié)點上標(biāo)記的標(biāo)識符；相應(yīng)葉結(jié)點上標(biāo)記的標(biāo)識符； 在基本塊內(nèi)被定值且該值能在基本塊后面被引用的標(biāo)識符就是在基本塊內(nèi)被定值且該值能在基本塊后面被引用的標(biāo)識符就是DAG各結(jié)點上的附加標(biāo)識符。各結(jié)點上的附加標(biāo)識符。這些結(jié)論可以引導(dǎo)優(yōu)化工作的進(jìn)一步深入，尤其是無用賦值的優(yōu)化，也即： 如果如果DAG中某結(jié)點上的標(biāo)識符在該基本塊之后不會被引用，就可中某結(jié)點上的標(biāo)識符在該基本塊之后不會被引用，就可以不生成對該標(biāo)識符賦值的四元式。以不生成對該標(biāo)識符賦值的四元式。 如果某結(jié)點如果某結(jié)點ni上沒有任何附加標(biāo)識符，或者上沒有任何附加標(biāo)識符，或者

26、ni上的附加標(biāo)識符在上的附加標(biāo)識符在該基本塊之后不會被引用，而且該基本塊之后不會被引用，而且ni也沒有前驅(qū)結(jié)點，這表明在基也沒有前驅(qū)結(jié)點，這表明在基本塊內(nèi)和基本塊之后都不會引用本塊內(nèi)和基本塊之后都不會引用ni的值，那么就不生成計算的值，那么就不生成計算ni結(jié)結(jié)點值的四元式。點值的四元式。如果有兩個相鄰的四元式如果有兩個相鄰的四元式A:=C op D和和B:=A，其中第一條代碼計，其中第一條代碼計算出來的算出來的A值僅在第二個四元式中被引用，則將值僅在第二個四元式中被引用，則將DAG中相應(yīng)結(jié)點中相應(yīng)結(jié)點重寫成四元式時，原來的兩個四元式可以優(yōu)化為重寫成四元式時，原來的兩個四元式可以優(yōu)化為B:=C

27、op D。假設(shè)例8.4中T0、T1、T2、T3、T4、T5和T6在基本塊后都不會被引用，則圖中的DAG就可重寫為如下的四元式序列：(1) S1:=R+r /*S1、S2為存放中間結(jié)果的臨時變量為存放中間結(jié)果的臨時變量*/(2) A:=6.28*S1(3) S2:=Rr(4) B:=A*S2以上把DAG重寫成四元式序列時，是按照原來構(gòu)造DAG結(jié)點的順序(即n5、n6、n7、n8)依次進(jìn)行的。實際上，我們還可以采用其它順序(如自下而上)重寫，只要其中的任何一個內(nèi)部結(jié)點是在其后繼結(jié)點之后被重寫并且轉(zhuǎn)移語句(如果有的話)仍然是基本塊的最后一個語句即可。返回 在程序流圖中，我們稱具有下列性質(zhì)的結(jié)點序列為

28、一個： 它們是它們是強連通強連通的，其中任意兩個結(jié)點之間必有一條通路，而且該的，其中任意兩個結(jié)點之間必有一條通路，而且該通路上各結(jié)點都屬于該結(jié)點序列；如果序列只包含一個結(jié)點，則通路上各結(jié)點都屬于該結(jié)點序列；如果序列只包含一個結(jié)點，則必有一條有向邊從該結(jié)點引到其自身。必有一條有向邊從該結(jié)點引到其自身。 它們中間它們中間有一個而且只有一個有一個而且只有一個是入口結(jié)點。是入口結(jié)點。 所謂，是指序列中具有下述性質(zhì)的結(jié)點：從序列外某結(jié)點有一條有向邊引到它，或者它就是程序流圖的首結(jié)點。也就是說，循環(huán)就是程序流圖中具有唯一入口結(jié)點的強連通子圖，從循環(huán)外要進(jìn)入循環(huán)，必須首先經(jīng)過循環(huán)的入口結(jié)點。 考慮右圖所示的

29、程序流圖：結(jié)點序列有一有向邊引到自身，且有唯一的入口結(jié)點6, 故是循環(huán)；結(jié)點序列中任兩結(jié)點間都存在通路，且有唯一入口結(jié)點2，故是循環(huán)；結(jié)點序列強連通且有唯一入口結(jié)點4，雖到結(jié)點4有向邊不止一條，但仍是循環(huán)；結(jié)點序列和，雖強連通但由于存在兩個入口結(jié)點2,4，故不是循環(huán)； 結(jié)點序列和因存在兩個入口結(jié)點4,7， 故不是循環(huán)。 1243576 代碼外提代碼外提 1強度削弱強度削弱 2刪除歸納變量刪除歸納變量 3（1）代碼外提若循環(huán)中某些運算的結(jié)果不因循環(huán)而改變，則可將其提到循環(huán)之外，從而在保持程序運行結(jié)果不變的前提下，提高了程序的運行效率，這種優(yōu)化技術(shù)稱為。 實行代碼外提時，需在循環(huán)入口結(jié)點前建立一個新結(jié)點(基本塊)，稱為循環(huán)的。循環(huán)前置結(jié)點以循環(huán)入口結(jié)點為其唯一后繼，原來流圖中從循環(huán)外引到循環(huán)入口結(jié)點的有向邊改成引到循環(huán)前置結(jié)點。 （2）施行代碼外提需要滿足的條件假定循環(huán)L中的不變運算S為A=B op C或A=op B或A=B。要求