編譯第十章.ppt

1、第十章 優(yōu) 化 10.1 概述 10.2 局部優(yōu)化 10.3 循環(huán)優(yōu)化 復(fù)習(xí)題,10.1 概 述 一、優(yōu)化的概念 優(yōu)化：對程序進行各種等價交換，使得從變換后的程序出發(fā)，能生成更有效的目標代碼，稱這種變換為優(yōu)化。 二、代碼優(yōu)化器的地位 有很多技術(shù)和手段可以用于中間代碼這一級上的優(yōu)化?？傮w上講在一個編譯程序中優(yōu)化器的地位和結(jié)構(gòu)如下圖：,編譯前端,代碼優(yōu)化器,代碼產(chǎn)生,控制流分析,數(shù)據(jù)流分析,代碼變換,圖 10-1 代碼優(yōu)化器的地位和結(jié)構(gòu),三、等價變換三原則 等價原則 經(jīng)過優(yōu)化后不應(yīng)改變程序運行的結(jié)果。 有效原則 使優(yōu)化后所產(chǎn)生的目標代碼運行時間較短，占用的存儲空間較小。 合算原則 應(yīng)盡可能以較低的

2、代階取得較好的優(yōu)化效果。,四、優(yōu)化的方法 刪除公共子表達式（刪除多余運算） 復(fù)寫傳播 刪除無用代碼（刪除無用賦值） 合并已知量 代碼外提 強度削弱 刪除歸納變量,循環(huán)優(yōu)化,五、代碼優(yōu)化示例 我們通過一個高級語言程序的例子來了解代碼優(yōu)化的全過程。下面是一個用C語言編寫的快速排序子程序： void quicksort (m, n) int m, n; int i,j; int v, x;,if(nv); if(i=j) break;,x=ai; ai=aj; aj=x; x=ai; ai=an; an=x; /*fragment ends here*/ quicksort(m, j); quick

3、sort(i+1,n); ,通過第七章的中間代碼生成方法可以產(chǎn)生這個程序的中間代碼。圖102給出了程序中兩個注解行之間的語句翻譯成中間代碼序列后所對應(yīng)的程序流圖，對圖102程序流圖的代碼優(yōu)化敘述如下。,i:=i+1 T2:=4*i T3:=aT2 if T3v goto B2,j:=j-1 T4:=4*j T5:=aT4 if T5v goto B3,if i=j goto B6,T6:=4*i x:=aT6 T7:=4*i T8:=4*j T9:=aT8 aT7:=T9 T10:=4*j aT10:=x goto B2,T11:=4*i x:=aT11 T12:=4*i T13:=4*n T

4、14:=aT13 aT12:=T14 T15:=4*n aT15:=x,i:=m-1 j:=n T1:=4*n v:=aT1,B1,B2,B3,B4,B5,B6,圖102 程序流圖,1刪除公共子表達式 公共子表達式：如果一個表達式E在前面已計算過，并且在這之后E中變量的值沒有改變，則稱E為公共子表達式。 在圖102的B5中分別把公共子表達式4*i和4*j的值賦給T7和T10，因此這種重復(fù)計算可以消除，即B5中的代碼變換成：,T6:=4*i x:=aT6 T7:=4*i T8:=4*j T9:=aT8 aT7:=T9 T10:=4*j aT10:=x goto B2,T6:=4*i x:=aT6

5、 T7:=T6 T8:=4*j T9:=aT8 aT7:=T9 T10:=T8 aT10:=x goto B2,對B5刪除了公共子表達式后，仍然要計算4*i和4*j ，我們還可以在更大范圍內(nèi)來考慮刪除公共子表達式的問題，即利用B3中的四元式T4:=4*j可以把B5中的代碼T8:=4*j替換為T8:=T4。 同樣，利用B2中的賦值句T2:=4*i可以把B5中的代碼T6:=4*i替換為T6:=T2。 對于B6也可以同樣考慮，最后，刪除公共子表達式后的程序流圖如圖103所示。,i:=i+1 T2:=4*i T3:=aT2 if T3v goto B2,j:=j-1 T4:=4*j T5:=aT4 i

6、f T5v goto B3,if i=j goto B6,T6:=T2 x:=aT6 T7:=T6 T8:=T4 T9:=aT8 aT7:=T9 T10:=T8 aT10:=x goto B2,T11:=T2 x:=aT11 T12:=T11 T13:=T1 T14:=aT13 aT12:=T14 T15:=T1 aT15:=x,i:=m-1 j:=n T1:=4*n v:=aT1,B1,B2,B3,B4,B5,B6,圖103 刪除公共子表達式后,2復(fù)寫傳播 圖103中的B5還可以進一步改進，四元式T6:=T2把T2賦給了T6，而四元式x:=aT6中引用了T6的值，但這中間并沒有改變T6的值。

7、因此，可以把x:=aT6變換為x:=aT2。這種變換稱為復(fù)寫傳播。用復(fù)寫傳播的方法可以把B5變?yōu)椋?T6:=T2 x:=aT6 T7:=T6 T8:=T4 T9:=aT8 aT7:=T9 T10:=T8 aT10:=x goto B2,T6:=T2 x:=aT2 T7:=T2 T8:=T4 T9:=aT4 aT2:=T9 T10:=T4 aT4:=x goto B2,作進一步的考察可以發(fā)現(xiàn)，在B2中計算了T3:= aT2，因此在B5中可以刪除公共子表達式，即把x:=aT2替換為x:=T3，并繼續(xù)通過復(fù)寫傳播，把B5中的aT4:=x替換為aT4 :=T3。 同樣，把B5中的T9:=aT4替換為T

8、9:=T5，aT2:=T9替換為 aT2:=T5。 這樣B5就變?yōu)椋?復(fù)寫傳播的目的是：使得對某些變量的賦值變?yōu)闊o用。,T6:=T2 x:=aT2 T7:=T2 T8:=T4 T9:=aT4 aT2:=T9 T10:=T4 aT4:=x goto B2,T6:=T2 x:=T3 T7:=T2 T8:=T4 T9:=T5 aT2:=T5 T10:=T4 aT4:=T3 goto B2,3刪除無用賦值 對于進行了復(fù)寫傳播后的B5，其中的變量x及臨時變量T6、T7、T8、T9、T10在整個程序中不再使用，故可以刪除對這些變量賦值的代碼。刪除無用賦值后B5變?yōu)椋?aT2:= T5 aT4:= T3 g

9、oto B2 對B6進行相同的復(fù)寫傳播和刪除無用賦值后變?yōu)椋?aT2:= v aT1:= T3 復(fù)寫傳播和刪除無用賦值后的程序流圖如圖10-4所示。,i:=i+1 T2:=4*i T3:=aT2 if T3v goto B2,j:=j-1 T4:=4*j T5:=aT4 if T5v goto B3,if i=j goto B6,aT2:=T5 aT4:=T3 goto B2,aT2:=v aT1:=T3,i:=m-1 j:=n T1:=4*n v:=aT1,B1,B2,B5,圖104 復(fù)寫傳播和刪除無用賦值后,B3,B4,B6,4代碼外提 對于循環(huán)中的有些代碼，如果它產(chǎn)生的結(jié)果在循環(huán)中是不變

10、的，就可以把它提到循環(huán)外來，以避免每循環(huán)一次都要對這條代碼進行運算。這種變換稱之為代碼外提。如： while(i=limit-2) . 可變換為： t:=limit-2 while(i=t). 考察圖104，沒有發(fā)現(xiàn)可外提到循環(huán)之外的不變運算。,5強度削弱 觀察圖104的內(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)前進行一次乘法運算而在循環(huán)中進行減法運算。同樣，對循環(huán)B2中的T2=4*i也可以進行強度削弱。經(jīng)過強度削弱后的程序流圖如圖10-5所示。,i:=i+1 T2:=

11、T2+4 T3:=aT2 if T3v goto B2,j:=j-1 T4:=T4-4 T5:=aT4 if T5v goto B3,if i=j goto B6,aT2:=T5 aT4:=T3 goto B2,aT2:=v aT1:=T3,i:=m-1 j:=n T1:=4*n v:=aT1 T2:=4*i T4:=4*j,B1,B2,B5,圖105 對B2、B3進行強度削弱,B3,B4,B6,6刪除歸納變量 由圖104可知，B2中每循環(huán)一次，i值加1，T2與i之間保持著T2=4*i的線性關(guān)系；而B3中每循環(huán)一次，j值減1，T4與j之間保持著T4=4*j的線性關(guān)系。這種變量我們稱之為歸納變量

12、。 在對T2=4*i和T4=4*j進行了強度削弱后，i和j僅出現(xiàn)在條件句if ij goto B6中，其余地方不再被引用。因此，我們可以變換歸納變量而把此條件句變換為：if T2T4 goto B6。經(jīng)過這種變換，我們又可以將無用賦值i=i+1和j=j1刪去。刪除歸納變量后的程序流圖如圖106所示。,T2:=T2+4 T3:=aT2 if T3v goto B2,T4:=T4-4 T5:=aT4 if T5v goto B3,if T2=T4 goto B6,aT2:=T5 aT4:=T3 goto B2,aT2:=v aT1:=T3,i:=m-1 j:=n T1:=4*n v:=aT1 T2

13、:=4*i T4:=4*j,B1,B2,B5,圖106 刪除歸納變量后的結(jié)果,B3,B4,B6,通過上述各種優(yōu)化，最終得到圖106的優(yōu)化結(jié)果。比較圖102和圖106可知：B2和B3中的四元式從4條減為2條，而且一條是由乘法變?yōu)榧臃?；B5中的四元式由9條變?yōu)?條，B6中的四元式由8條變?yōu)?條。以上這些優(yōu)化對循環(huán)執(zhí)行來說，效果是非常明顯的。雖然B1的四元式由4條變?yōu)?條，但因其僅被執(zhí)行一次，所以影響甚微。,10.2 局部優(yōu)化 一、基本塊及流圖 1.基本塊 （1）定義 基本塊： 指程序中一順序執(zhí)行的語句序列，其中只有一個入口和一個出口，入口就是其中的第一個語句，出口就是其中的最后一個語句。 局部優(yōu)化

14、：局限于基本塊范圍內(nèi)的優(yōu)化稱為基本塊內(nèi) 優(yōu)化，或稱為局部優(yōu)化。,定值和引用：對三地址語句：x:=y+z，我們 稱對x定值并引用y和z。 活躍的：在一個基本塊中的一個名字，所謂 在程序中的某個給定點是活躍的， 是指如果在程序中（包括在本基本 塊或其它基本塊中）它的值在該點 以后被引用。,（2）劃分基本塊的算法 1求出四元式程序中各個基本塊的入口語句，它們是 程序的第一個語句；或者 能由條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句轉(zhuǎn)移到的語 句；或者 緊跟在條件轉(zhuǎn)移語句后面的語句。 2對以上求出的每一入口語句，構(gòu)造其所屬的基本塊，它是由該入口語句到另一入口語句（不包括該入口語句），或到一轉(zhuǎn)移語句（包括該轉(zhuǎn)移語句）

15、，或到一停語句（包括該停語句）之間的語句序列組成的。,3凡未被納入某一基本塊中的語句，都是程序中控制流無法到達的語句。從而也是不會被執(zhí)行到的語句，可把它們從程序中刪除。 例 10.1：將以下求最大公因子的程序劃分為基本塊。,read X read Y R:=X mod Y if R=0 goto X:=Y Y:=R goto write Y halt,解：（1）找入口語句 （2） 構(gòu)造基本塊 B1： B2： B3： B4：,（3）基本塊內(nèi)可實現(xiàn)的變換 合并已知量 臨時變量改名 交換語句的位置 代數(shù)變換,2.流圖,一個控制流程圖(簡稱流圖)就是具有惟一首結(jié)點的有向圖。 所謂首結(jié)點，就是從它開始到

16、控制流程圖中任何一個結(jié)點都有一條通路的結(jié)點。 我們可以把控制流程圖表示成一個三元組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：,(1) 基本塊j在程序中的位置緊跟在基本塊i之后，并且基本塊i的出口語句不是無條件轉(zhuǎn)移語句goto(s)或停語句。 (2) 基本塊i的出

17、口語句是goto(s)或if goto(s)，并且(s)是基本塊j的入口語句。 在以后的討論中，我們所涉及的流圖都是程序流圖。,例 10.2 將以下程序劃分為基本塊，并作出其程序流圖。,(1) read X (2) read Y (3) R:=X mod Y (4) if R=0 goto (8) (5) X:=Y (6) Y:=R (7) goto (3) (8) write Y (9) halt,(1) read X (2) read Y,(3) R:=X mod Y (4) if R=0 goto (8),(5) X:=Y (6) Y:=R (7) goto (3),(8) write

18、Y (9) halt,(1) read X (2) read Y (3) R:=X mod Y (4) if R=0 goto (8) (5) X:=Y (6) Y:=R (7) goto (3) (8) write Y (9) halt,B1,B2,B4,B3,二、基本塊的DAG表示及其應(yīng)用 1基本塊的DAG表示基本特征 DAG(Directed Acyclic Graph)是一種有向圖，常常用來對基本塊進行優(yōu)化。一個基本塊的DAG是一種其結(jié)點帶有下述標記或附加信息的DAG： (1) 圖的葉結(jié)點(無后繼的結(jié)點)以一標識符(變量名)或常數(shù)作為標記，表示該結(jié)點代表該變量或常數(shù)的值。如果葉結(jié)點用來

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

20、的標識符是結(jié)點上的附加標識符。 除了對應(yīng)轉(zhuǎn)移語句的結(jié)點右邊可附加一語句位置來指示轉(zhuǎn)移目標外，其余各類結(jié)點的右邊只允許附加標識符。 除對應(yīng)于數(shù)組元素賦值的結(jié)點(標記為 =)有三個后繼外，其余結(jié)點最多只有兩個后繼。,0型四元式：后繼結(jié)點個數(shù)為0。 A:=B goto (S),n1,A,B,n1,(S),1型四元式：有一個后繼結(jié)點。 A:=op B,n1,op,B,n2,A,2型四元式：有兩個后繼結(jié)點。 A:= B op C,n1,op,B,n3,A,n2,C,2型四元式：有兩個后繼結(jié)點。 A:= BC,n1,=,B,n3,A,n2,C,2型四元式：有兩個后繼結(jié)點。 if B rop C goto

21、（S）,n1,rop,B,n3,（S）,n2,C,3型四元式：有三個后繼結(jié)點。 DC :=B,n1,=,D,n4,B,n2,C,n3,(2)僅含0,1,2 型中間代碼的基本塊DAG構(gòu)造算法 我們規(guī)定：用大寫字母(如A、B等)表示四元式中的變量名(或常數(shù))；用函數(shù)Node(A)表示A在DAG中的相應(yīng)結(jié)點，其值可為n或者無定義，并用n表示DAG中的一個結(jié)點值。 開始，DAG為空, 若Node(B)無定義, 則構(gòu)造一個標記為B的葉結(jié)點, 并定義Node(B)為該結(jié)點, 然后根據(jù)下述情況進行處理： 若當(dāng)前四元式是0型, 則記Node(B)的值 為n, 轉(zhuǎn)。 若當(dāng)前四元式是1型, 則轉(zhuǎn)。 若當(dāng)前四元式是

22、2型, 則： i.若Node(C)無定義，則構(gòu)造一標記為 C的葉結(jié)點, 并定義Node(C)為該結(jié)點； ii.轉(zhuǎn)。, 若Node(B)是以常數(shù)標記的葉結(jié)點，則轉(zhuǎn)，否則 轉(zhuǎn)。 若Node(B)和Node(C)都是以常數(shù)標記的葉結(jié)點，則 轉(zhuǎn)，否則轉(zhuǎn)。 執(zhí)行op B(即合并已知量)，令得到的新常 數(shù)為P。若 Node(B)是處理當(dāng)前四元式時新建立的結(jié)點，則刪除 它；若Node(P)無定義，則構(gòu)造一個用P做標記的葉 結(jié)點n，并置Node(P)= n；轉(zhuǎn)。 執(zhí)行B op C(即合并已知量)，令得到的新常數(shù)為P。 若Node(B)或Node(C)是處理當(dāng)前四元式時新建立的 結(jié)點則刪除它；若Node(P)無

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

24、加到新結(jié)點 n上，并令Node(A)=n。轉(zhuǎn)處理下一代碼。 （3） 構(gòu)造DAG實例 例 10.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 (9) T6:=R-r (10) B:= T5* T6 解: 按順序處理各四元式后構(gòu)造的DAG如下：,n1,3.14,T0,n2,6.28,n3,R,n4,r,T1,(1) T0:=3.14 (2) T1:= 2*T0 (3) T2:=R+r (4) A:= T1

25、* T2 (5) B:=A (6) T3:= 2*T0 (7) T4:=R+r (8) T5:= T3* T4 (9) T6:=R-r (10) B:= T5* T6,n5,+,T2,n6,*,A,B,T3,T4,T5,n7,-,T6,n8,*,B,3.利用DAG進行基本塊的優(yōu)化 利用DAG進行基本塊優(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*T6,n1,3.14,T0,n2,n3,n4,r,T1,n5,+,T2,n6,*,A,T3,T4,T5,n7,-,T6,n8,*,B,6.28,R,將G和原基本塊G相比，我們看到： (1) G中四元式(2)和(6)都是已知量和已知量的運算，G已合并； (2) G中四元式(5)是一種無用賦值，G已將它刪除； (3)