編譯原理課件07代碼優(yōu)化

1、1. 掌握優(yōu)化的基本概念第七章 代碼優(yōu)化(1) 什么是代碼優(yōu)化 : 對程序?qū)嵤└鞣N等價變換,使得變換后程序能生成的目標(biāo)代碼。的目標(biāo)代碼是指 : 目標(biāo)代碼占用的存儲空間少目標(biāo)代碼運行時間短1(2) 代碼優(yōu)化的種類：根據(jù)是否涉及具體的計算機(jī)分為 : 與機(jī)器有關(guān)的優(yōu)化(優(yōu)化工作主要在目標(biāo)代碼級上進(jìn)行) 對寄存器的優(yōu)化 多處理機(jī)的優(yōu)化特殊指令的優(yōu)化等第七章 代碼優(yōu)化2與機(jī)器無關(guān)的優(yōu)化 (優(yōu)化工作主要在中間代碼級上進(jìn)行)根據(jù)優(yōu)化對象所涉及的程序范圍分為 : 局部優(yōu)化 循環(huán)優(yōu)化 全局優(yōu)化 第七章 代碼優(yōu)化3局部優(yōu)化 是指局限于程序基本塊范圍內(nèi)的一種優(yōu)化。 局部優(yōu)化包括: 合并已知量 刪除公共子表達(dá)式(刪除

2、多余的運算) 刪除無用賦值第七章 代碼優(yōu)化4循環(huán)優(yōu)化 是指對循環(huán)中的代碼進(jìn)行優(yōu)化。 循環(huán)優(yōu)化包括: 代碼外提 刪除歸納變量 強度削弱第七章 代碼優(yōu)化5是在整個程序范圍內(nèi)進(jìn)行的優(yōu)化, 需進(jìn)行數(shù)據(jù)流分析, 花費代價很高。全局優(yōu)化 第七章 代碼優(yōu)化6S = 0；for ( i=1; i=20; i+ ) S = S + Ai*Bi ； (3) 優(yōu)化處理 例如 設(shè)有一個計算兩個向量內(nèi)積的源 程序段: 第七章 代碼優(yōu)化7 編譯程序?qū)ζ溥M(jìn)行詞法分析、語法分析、語義分析和中間代碼的生成, 得到如下一組三地址語句序列表示的中間代碼：第七章 代碼優(yōu)化8數(shù)組元素地址的計算數(shù)組指針 1001100510091013

3、10171001100210031004= +I*sizeof(數(shù)組元素)10019(1) S=0(2) I=1(3) T1=4*I(4) T2=addr(A)4(5) T3=T2T1(6) T4=4*I(7) T5=addr(B)4(8) T6=T5T4(9) T7=T3*T6(10) S=S+T7(11) I=I+1(12) if I20 goto (3)說明:= + I*sizeof(數(shù)組元素)1 =addr(A) 1+I*4addr(A) 1T2地址計算的不變部分I*4 T1地址計算的可變部分用T2T1表示數(shù)組元素的地址若一個機(jī)器字有四個字節(jié), 按字節(jié)編址:T1= 4* I T2=ad

4、dr(A) 4*1B1B210 在上圖所示的中間代碼中，根據(jù)程序流向的特點，分為B1、B2兩塊:B1是循環(huán)體外的語句序列B2是可重復(fù)執(zhí)行的循環(huán)體語句序列第七章 代碼優(yōu)化11 刪除公共子表達(dá)(刪除多余運算)公共子表達(dá)式是指在一個基本塊內(nèi)計算結(jié)果相同的子表達(dá)式。對相同的子表達(dá)式只在第一次出現(xiàn)時計算且僅計算一次，將重復(fù)計算的表達(dá)式刪除。(1) S=0(2) I=1(3) T1=4*I(4) T2=addr(A)4(5) T3=T2T1(6) T4=4*I(7) T5=addr(B)4(8) T6=T5T4(9) T7=T3*T6(10) S=S+T7(11) I=I+1(12) if I20 got

5、o (3)B1B2第七章 代碼優(yōu)化12 圖B2中公共子表達(dá)式 4*I 出現(xiàn)在四元式(3)和(6)中，而從(3)到(6)之間沒有對子表達(dá)式中的變量 I 重新賦值，因此T1=T4，第二個4*I 是多余的運算，可以刪去，將原四元式改為 : (6) T4=T1 。 (1) S=0(2) I=1(3) T1=4*I(4) T2=addr(A)4(5) T3=T2T1(6) T4=4*I(7) T5=addr(B)4(8) T6=T5T4(9) T7=T3*T6(10) S=S+T7(11) I=I+1(12) if I20 goto (3)B1B2第七章 代碼優(yōu)化13代碼外提 代碼外提是指將循環(huán)中的不變

6、運算提到循環(huán)體前面。 圖B2中，四元式 (4)T2=addr(A) 4 (7)T5=addr(B) 4(1) S=0(2) I=1(3) T1=4*I(4) T2=addr(A)4(5) T3=T2T1(6) T4=T1(7) T5=addr(B)4(8) T6=T5T4(9) T7=T3*T6(10) S=S+T7(11) I=I+1(12) if I20 goto (3)B1B2第七章 代碼優(yōu)化14由于addr(A)，addr(B)已知，T2，T5的值不隨循環(huán)的執(zhí)行而變化，因此將四元式(4)，(7)提到B2前面，得到下圖:(1) S=0(2) I=1(3) T1=4*I(4) T2=add

7、r(A)4(5) T3=T2T1(6) T4=T1(7) T5=addr(B)4(8) T6=T5T4(9) T7=T3*T6(10) S=S+T7(11) I=I+1(12) if I20 goto (3)B1B2第七章 代碼優(yōu)化15(1) S=0I=1(4) T2=addr(A)4(7) T5=addr(B)4(3) T1=4*I(5) T3=T2T1(6) T4=T1(8) T6=T5T4(9) T7=T3*T6(10) S=S+T7(11) I=I+1(12) if I20 goto (3)B1B2強度削弱 強度削弱是指在不改變運算結(jié)果的前提下，將程序中執(zhí)行時間長的運算替換成執(zhí)行時間短

8、的運算。 對計算機(jī)上的二進(jìn)制算術(shù)運算，作加法一般比作乘法的速度快。 第七章 代碼優(yōu)化16 圖中四元式(3)T1= 4*I中，I是循環(huán)控制變量，每循環(huán)一次，I 增加一個步長值 即I 值加1 ,而 T1的值增加4將 (3) T1=4*I 提到循環(huán)外 循環(huán)體內(nèi)改為 (3) T1= T1+ 4 得到下圖。(1) S=0I=1(4) T2=addr(A)4(7) T5=addr(B)4(3) T1=4*I(5) T3=T2T1(6) T4=T1(8) T6=T5T4(9) T7=T3*T6(10) S=S+T7(11) I=I+1(12) if I20 goto (3)B1B2第七章 代碼優(yōu)化17(1)

9、 S=0I=1(4) T2=addr(A)4(7) T5=addr(B)4(3) T1=4*I(5) T3=T2T1(6) T4=T1(8) T6=T5T4(9) T7=T3*T6(10) S=S+T7(11) I=I+1(12) if I20 goto (3)B1B2(1) S=0I=1(4) T2=addr(A)4(7) T5=addr(B)4(3) T1=4*I(5) T3=T2T1(6) T4=T1(8) T6=T5T4(9) T7=T3*T6(10) S=S+T7 I=I+1(3) T1=T1+4(12) if I20 goto (3)B1B2第七章 代碼優(yōu)化18(1) S=0I=1

10、(4) T2=addr(A)4(7) T5=addr(B)4(3) T1=4*I(5) T3=T2T1(6) T4=T1(8) T6=T5T4(9) T7=T3*T6(10) S=S+T7 I=I+1(3) T1=T1+4(12) if I20 goto (3)B1B2變換循環(huán)控制條件 (刪除歸納變量) 在B2中存在變量 T1 與循環(huán)控制變量 I 保持線性關(guān)系，則可由T1 取代 I , 因此對三地址語句 (12) 中的循環(huán)控制條件I 20 T180 第七章 代碼優(yōu)化19(1) S=0I=1(4) T2=addr(A)4(7) T5=addr(B)4(3) T1=4*I(5) T3=T2T1(6

11、) T4=T1(8) T6=T5T4(9) T7=T3*T6(10) S=S+T7 I=I+1(3) T1=T1+4(12) if I20 goto (3)B1B2稱這種變換為變換循環(huán)控制條件,或稱為刪除歸納變量。 變換循環(huán)控制條件后，三地址語句 (11) I = I+1可刪除。 因為變量 I 是引用 I 值來計算 I 值, 稱為對 I 遞歸賦值, I 稱為循環(huán)中的歸納變量。 第七章 代碼優(yōu)化20(1) S=0I=1(4) T2=addr(A)4(7) T5=addr(B)4(3) T1=4*I(5) T3=T2T1(6) T4=T1(8) T6=T5T4(9) T7=T3*T6(10) S=

12、S+T7 I=I+1(3) T1=T1+4(12) if T180 goto (5)B1B2合并已知量 已知量是指常數(shù)或在編譯時就能確定其值的變量。 合并已知量是指若參加運算的兩個對象在編譯時都是已知量，則可以在編譯時直接計算出它們的運算結(jié)果，不必生成目標(biāo)。 第七章 代碼優(yōu)化21 圖B1中，四元式(2) I=1，其后的兩個四元式中沒有改變 I 值，這時四元式 (3) T1= 4*I 中參加運算的兩個運算量均為已知, 因此將(3) 變換為：T1=4，得到下圖：(1) S=0I=1(4) T2=addr(A)4(7) T5=addr(B)4(3) T1=4*I(5) T3=T2T1(6) T4=T

13、1(8) T6=T5T4(9) T7=T3*T6(10) S=S+T7 I=I+1(3) T1=T1+4(12) if T180 goto (5)B1B2第七章 代碼優(yōu)化22(1) S=0I=1(4) T2=addr(A)4(7) T5=addr(B)4(3) T1=4(5) T3=T2T1(6) T4=T1(8) T6=T5T4(9) T7=T3*T6(10) S=S+T7 I=I+1(3) T1=T1+4(12) if T180 goto (5)B1B2復(fù)寫傳播 復(fù)寫傳播是指盡量不引用那些在程序中僅僅只傳遞信息而不改變其值，也不影響其運行結(jié)果的變量。圖中,T4 就是這樣一種變量。 第七章

14、代碼優(yōu)化23(1) S=0I=1(4) T2=addr(A)4(7) T5=addr(B)4(3) T1=4(5) T3=T2T1(6) T4=T1(8) T6=T5T1(9) T7=T3*T6(10) S=S+T7 I=I+1(3) T1=T1+4(12) if T180 goto (5)B1B2 四元式(6)T4=T1，下一個四元式(8)T6=T5T4，這之間T4的值沒有變化，因此將(8) 變換為 : T6=T5T1 。 這時T4成為無用的賦值。第七章 代碼優(yōu)化24(1) S=0I=1(4) T2=addr(A)4(7) T5=addr(B)4(3) T1=4(5) T3=T2T1(6)

15、T4=T1(8) T6=T5T1(9) T7=T3*T6(10) S=S+T7 I=I+1(3) T1=T1+4(12) if T180 goto (5)B1B2刪除無用賦值 對賦值語句X=Y，若在程序的任何地方都不引用X，這時該語句執(zhí)行與否對程序運行結(jié)果沒有任何作用，這種語句稱為無用賦值語句，可以刪除。 第七章 代碼優(yōu)化25(1) S=0(4) T2=addr(A)4(7) T5=addr(B)4(3) T1=4(5) T3=T2T1(8) T6=T5T1(9) T7=T3*T6(10) S=S+T7(3) T1=T1+4(12) if T180 goto (5)B1B2(1) S=0(2)

16、 I=1(3) T1=4*I(4) T2=addr(A)4(5) T3=T2T1(6) T4=4*I(7) T5=addr(B)4(8) T6=T5T4(9) T7=T3*T6(10) S=S+T7(11) I=I+1(12) if I20 goto (3)B1B2第七章 代碼優(yōu)化26 比較優(yōu)化前后的代碼序列可以發(fā)現(xiàn)經(jīng)過優(yōu)化后最終得到的代碼序列具有以下特點: 減少了循環(huán)體內(nèi)可執(zhí)行代碼，由10 條減至6條。 減少了作乘法運算的次數(shù)，由3次降 為1次。 減少了全程范圍內(nèi)使用的變量，如I， T4等變量。 第七章 代碼優(yōu)化272. 利用DAG實現(xiàn)局部優(yōu)化 第七章 代碼優(yōu)化 局部優(yōu)化是指局限于程序基本塊

17、范圍內(nèi)的一種優(yōu)化。(1) 基本塊 所謂基本塊是指程序中一組順序執(zhí)行的語句序列,其中只有一個入口語句和一個出口語句。 28從四元式序列確定基本塊的入口語句： 四元式序列的第一個語句 由條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語 句轉(zhuǎn)移到的語句 緊跟在條件轉(zhuǎn)移語句后面的語句。第七章 代碼優(yōu)化(2) 劃分基本塊的方法29確定基本塊的出口語句： 下一個入口語句的前導(dǎo)語句 轉(zhuǎn)移語句(包括轉(zhuǎn)移語句本身) 停語句(包括停語句本身)入口語句和出口語句之間組成一個基本塊。 刪去那些不屬于任何基本塊的語句，因為控制流無法到達(dá)這些語句。第七章 代碼優(yōu)化30例 給以下四元式序列劃分基本塊。（1）read C（2）A=0（3）B=1（

18、4）L1 : A=A+b（5）if BC goto L2（6）B=B+1（7）goto L1（8）L2 : write A（9）halt第七章 代碼優(yōu)化31例 給以下四元式序列劃分基本塊。（1）read C（2）A=0（3）B=1（4）L1 : A=A+b（5）if BC goto L2（6）B=B+1（7）goto L1（8）L2 : write A（9）halt第七章 代碼優(yōu)化下一個入口語句的前導(dǎo)語句轉(zhuǎn)移語句(包括轉(zhuǎn)移語句本身)停語句(包括停語句本身)四元式序列的第一個語句由條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句轉(zhuǎn)移到的語句緊跟在條件轉(zhuǎn)移語句后面的語句由條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句轉(zhuǎn)移到的語句由條件

19、轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句轉(zhuǎn)移到的語句轉(zhuǎn)移語句(包括轉(zhuǎn)移語句本身)轉(zhuǎn)移語句(包括轉(zhuǎn)移語句本身)32根據(jù)劃分基本塊的算法可以確定四元式(1)(4)(6)(8)是入口語句; (3)(5)(7)(9)是出口語句，因此分為四個基本塊 （1）read C（2）A=0（3）B=1（4）L1: A=A+b（5）if BC goto L2（6） B=B+1（7） goto L1（8）L2: write A（9）halt33(2) 利用DAG實現(xiàn)局部優(yōu)化的思想： 第七章 代碼優(yōu)化 基本塊 DAG 還原34DAG ( 無環(huán)路有向圖 )n1n4n6n2n3n5n7n8n9第七章 代碼優(yōu)化35結(jié)點帶有標(biāo)記的DAG：n1

20、Bn13.1416n1Addr(A)n3T1,T2n1Bn2COP第七章 代碼優(yōu)化36基本塊的DAG表式：(1) A=Bn1AB(2) A= op Bn2Bn1AOP(3) A=B op Cn1Bn2Cn3Aop四元式與DAG第七章 代碼優(yōu)化37圖11.9列出各種四元式及相對應(yīng)的DAG的結(jié)點形式：3839例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=R-r(10)B=T5*T6n1T03.14n1T03.14n2T16.28n3R

21、n4rn5T2+第七章 代碼優(yōu)化40對四元式(4) A=T1*T2 有：(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 n1T03.14n2T16.28n3Rn4rn5T2+n6A*第七章 代碼優(yōu)化41對四元式(5) B=A 有：(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

22、n1T03.14n2T16.28n3Rn4rn5T2+n6A,*B第七章 代碼優(yōu)化42對四元式(6) T3=2*T0 有：(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*T6n1T03.14n2T1,6.28n3Rn4rn5T2+n6A,*BT3第七章 代碼優(yōu)化43對四元式(7) T4=R+r 有：(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(

23、8) T5=T3*T4(9) T6=R-r(10)B=T5*T6T4n1T03.14n2T1,6.28n3Rn4rn5T2,+n6A,*B,T3第七章 代碼優(yōu)化44對四元式(8) T5=T3*T4 有：(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 n1T03.14n2T1,6.28n3Rn4rn5T2,+n6A,*B,T3T4T5第七章 代碼優(yōu)化45對四元式(9) T6=R- r中(1) T0=3.14(2) T1=2*T0(3)

24、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*T6n1T03.14n2T1,6.28n3Rn4rn5T2,+n6A,*B,T3T4T5n7T6-第七章 代碼優(yōu)化46對四元式(10) B=T5*T6(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*T6n1T03.14n2T1,6.28n3Rn4rn5T2,+n6A,*T3T4T5n7T6-

25、n8B*第七章 代碼優(yōu)化47 按照構(gòu)造DAG結(jié)點的順序，對每一個結(jié)點寫出其相應(yīng)的四元式表示。 (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*T6n1T03.14n2T1,6.28n3Rn4rn5T2,+n6A,*T3T4T5n7T6-n8B*第七章 代碼優(yōu)化48(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(1) T0=3

26、.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第七章 代碼優(yōu)化49 設(shè)優(yōu)化后的上述一組四元式序列為G，G較之優(yōu)化前的一組四元式G，不但代碼總數(shù)減少，而且對G中四元式(2)T1=2*T0和(6)T3=2*T0，在G中已被優(yōu)化為T1=6.28，T3=6.28，這是合并已知量的結(jié)果；對G中四元式(5)B=A，直至在下一個B被賦值時都沒有被引用，第七章 代碼優(yōu)化解釋圖在下頁50(1) T0=3.14(2) T1=6.28(3) T3=6.28(4) T2=R

27、+r(5) T4=T2(6) A=6.28*T2(7) T5=A(8) T6=R-r(9) B=A*T6(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第七章 代碼優(yōu)化合并已知量無用賦值51顯然是無用賦值，G中已被刪除；對G中具有公共子表達(dá)式的四元式(3)T2=R+r，(7)T4=R+r，G中被優(yōu)化為直接賦值T4=T2，避免了對公共子表達(dá)式R+r的重復(fù)計算。綜上所述，利用DAG可以很方便地進(jìn)行基本塊內(nèi)的優(yōu)化處理。 第七章 代碼優(yōu)化解釋圖

28、在下頁52(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(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第七章 代碼優(yōu)化公共子表達(dá)式優(yōu)化為直接賦值53例2 試對下面基本塊進(jìn)行優(yōu)化X=B*CY=B/CZ=X+YW=9*ZG=B*CT=G*GW=T*GL=WM=L1. 應(yīng)用DAG對該基本塊進(jìn)行優(yōu)化,給出

29、優(yōu)化后的語句序列2. 給出當(dāng)只有L在基本塊出口后為活躍時的優(yōu)化結(jié)果第七章 代碼優(yōu)化54n1Bn2Cn3X,*n9W,*L,GMn4Y/n5Z+n69n7WTn8*X=B*CY=B/CZ=X+YW=9*ZG=B*CT=G*GW=T*GL=WM=L第七章 代碼優(yōu)化55X=B*CG=XY=B/CZ=X+YT=G*GW=T*GL=WM=Ln1Bn2Cn3X,*n9W,*L,GMn4Y/n5Z+n69n7WTn8*按照構(gòu)造DAG結(jié)點次序重寫四元式序列第七章 代碼優(yōu)化56G=B*CT=G*GL=T*G優(yōu)化后的語句序列:X=B*CG=XY=B/CZ=X+YT=G*GW=T*GL=WM=L又因為只有L在基本塊

30、出口后為活躍, 即只有L在基本塊出口處要引用, 因此其他變量賦值語句可刪去, 其優(yōu)化結(jié)果為:第七章 代碼優(yōu)化573. 循環(huán)查找 求流圖中所有結(jié)點n 的必經(jīng)結(jié)點 集D(n)(2) 求流圖中的回邊(3) 根據(jù)回邊求循環(huán)第七章 代碼優(yōu)化58 一個程序的控制流程圖（簡稱為程序流圖或流圖）G是一個三元組 G=(N，n0，E)。其中： 控制流程圖第七章 代碼優(yōu)化59 N表示流圖的有限結(jié)點集，流圖中每一 個結(jié)點對應(yīng)程序中的一個基本塊，因 此，N實質(zhì)上就是一個程序的基本塊集。 n0表示唯一的首結(jié)點，流圖的首結(jié)點是 包含程序第一個語句的基本塊。 E表示流圖的有向邊集。 第七章 代碼優(yōu)化60 為了找出流圖中的循環(huán)

31、，需分析流圖中結(jié)點間的控制關(guān)系。因此引入必經(jīng)結(jié)點和必經(jīng)結(jié)點集的概念。第七章 代碼優(yōu)化61必經(jīng)結(jié)點 在程序流圖中，對任意兩個結(jié)點a和b，若從流圖的首結(jié)點出發(fā)，到達(dá)a的任一通路都要經(jīng)過b，則稱b是a的必經(jīng)結(jié)點，記為b DOM a。 第七章 代碼優(yōu)化62必經(jīng)結(jié)點集 流圖中結(jié)點a的所有必經(jīng)結(jié)點的集合稱為結(jié)點a的必經(jīng)結(jié)點集，記為D(a) 第七章 代碼優(yōu)化63 求流圖中所有結(jié)點n 的必經(jīng)結(jié)點集D(n)的算法思想： 結(jié)點nn 的所有前驅(qū)結(jié)點的必經(jīng)結(jié)點的交，即如果某結(jié)點d是結(jié)點n的所有前驅(qū)結(jié)點的必經(jīng)結(jié)點，則d為n的必經(jīng)結(jié)點。 第七章 代碼優(yōu)化64B1B2B3B4B5B6B7B8D(B8) = B1, B2,

32、B7, B8 流圖中各結(jié)點的必經(jīng)結(jié)點集：例1.D(B1) = B1D(B2) = B1, B2D(B3) = B1, B2, B3D(B4) = B1, B2, B3, B4D(B5) = B1, B2, B3,B5D(B6) = B1, B2, B3, B6D(B7) = B1, B2, B765求流圖中的回邊 設(shè)ab是流圖中的一條有向邊，若b DOM a，則稱ab是流圖中的一條回邊。第七章 代碼優(yōu)化66流圖中的回邊： 因為B2 DOM B7，所以B7B2是流圖中的回邊，且是流圖中的唯一回邊。 B1B2B3B4B5B6B7B8第七章 代碼優(yōu)化67求循環(huán)的算法思想： 回邊n到d組成的循環(huán): d

33、是循環(huán)的入口，n是循環(huán)的出口，循環(huán)出口n的前驅(qū)屬于循環(huán)，前驅(qū)不是d，再求前驅(qū), 直到入口d為止。第七章 代碼優(yōu)化68流圖中的循環(huán)：由回邊B7B2組成的循環(huán)是 B2,B3, B4,B5, B6,B7 B1B2B3B4B5B6B7B8第七章 代碼優(yōu)化69例2 設(shè)有如左圖所示的程序流圖:13 465782 求流圖中各結(jié)點 n 的 必經(jīng)結(jié)點集D(n)(2) 求出該流圖中的回邊(3) 求出該流圖中的循環(huán)70D(1)=1D(2)=1, 2D(3)=1, 2, 3D(4)=1, 2, 4D(5)=1, 2, 4, 5D(6)=1, 2, 4, 6D(7)=1, 2, 4, 7D(8)=1, 2, 4, 7,

34、 872為回邊3不是6的必經(jīng)結(jié)點4不是2的必經(jīng)結(jié)點回邊組成的循環(huán) :2, 3, 4, 5, 6, 713 4657822是7的必經(jīng)結(jié)點71例如圖11.12中各結(jié)點的D(n)如下：D(1)=1D(2)=1,2D(3)=1,2,3D(4)=1,2,4D(5)=1,2,4,5D(6)=1,2,4,6D(7)=1,2,4,772三.循環(huán)優(yōu)化1.代碼外提：把循環(huán)不變運算，放到循環(huán)的前面實行代碼外提時，在循環(huán)的入口結(jié)點前面建立一個新結(jié)點（基本塊），稱之為循環(huán)的前置結(jié)點73循環(huán)的前置結(jié)點以循環(huán)的入口結(jié)點為其唯一后繼，原來流圖中從循環(huán)外引到循環(huán)入口結(jié)點的有向邊，改成引到循環(huán)前置結(jié)點，如圖11.13所示：74是

35、否在任何情況下，都可把循環(huán)不變運算外提呢?觀察圖11.14：75出口結(jié)點：從該結(jié)點有一有向邊引到循環(huán)外的某結(jié)點容易看出B2,B3,B4是循環(huán)，其中B2是循環(huán)的入口結(jié)點，B4是出口結(jié)點B3中i:=2是循環(huán)不變運算，如果把i:=2提到循環(huán)的前置結(jié)點B2中，如圖11.15所示，按此程序流圖，執(zhí)行完B5時，i、j的值都為2。事實上，按圖11.14的流圖，若x=30,y=25，則B3不被執(zhí)行，執(zhí)行完B5時，i和j的值都為1，所以圖11.15的流圖改變了原來程序的運行結(jié)果7677問題的原因在于B3不是循環(huán)出口結(jié)點B4的必經(jīng)結(jié)點。所以，當(dāng)把一個不變運算提到循環(huán)的前置結(jié)點時，要求該不變運算所在的結(jié)點是循環(huán)所有

36、出口結(jié)點的必經(jīng)結(jié)點此外，如果循環(huán)中i的所有引用點只是B2中i的定值點（“點”指某一四元式的位置，對變量的“定值”指對變量賦值或輸入值）所能達(dá)到的，i在循環(huán)中不再有其他定值點，并且出循環(huán)后不再引用該i的值，那么,即使B3不是B4的必經(jīng)結(jié)點，也可以把i:=2提到B2中,因為這不影響原來程序的運行結(jié)果定值點：變量在該點被賦值或輸入值引用點：在該點使用了這個變量78在代碼外提過程，應(yīng)注意以下兩點：（1）當(dāng)把循環(huán)中的不變運算A:=B op C外提時，要求循環(huán)中其他地方不再有A的定值點（2）當(dāng)把循環(huán)中的不變運算A:=B op C外提時，要求循環(huán)中A的所有引用點都是而且僅是這個定值所能達(dá)到的79假設(shè)L為所要

37、處理的循環(huán)，查找“不變運算”的算法：（1）依次查看L中各基本塊的每個四元式，如果它的每個運算對象或為常數(shù)，或者定值點在L外，則將此四元式標(biāo)記為“不變運算”（2）重復(fù)第（3）步直至沒有新的四元式被標(biāo)記為“不變運算”為止80（3）依次查看尚未被標(biāo)記為“不變運算”的四元式，如果它的每個運算或為常數(shù)，或者定值點在L之外，或只有一個到達(dá)一定值點且該點上的四元式已被標(biāo)記為“不變運算”。則被查看的四元式標(biāo)記為“不變運算”。所謂到達(dá)一定值點是指變量在某點定值后到達(dá)的一點，通路上沒有其他該變量的定值81代碼外提算法：（1）求出循環(huán)L的所有不變運算（2）對步驟（1）所求得的每一不變運算a:A=B op C或A:=

38、op B或A:=B，檢查它是否滿足以下條件(a)或(b)：82（a）(I)s所在的結(jié)點是L的所有出口結(jié)點的必經(jīng)結(jié)點(II)A在L中其他地方未再定值(III)L中所有A的引用點只有s中A的定值才能到達(dá)（b）A在離開L之后不再是活躍的，并且條件(a)的(II)和(III)成立。所謂A在離開L后不再是活躍的是指，A在L的任何出口結(jié)點的后繼結(jié)點的入口處不是活躍的（從此點后不被引用）（3）按步驟（1）所找出的不變運算的順序，依次把符合（2）的條件(a)或(b)的不變運算s外提到L的前置結(jié)點中。如果s的運算對象（B或C）是在L中定值的，則只有當(dāng)這些定值四元式都已外提到前置結(jié)點中時，才可把s也外提到前置結(jié)點832.強度削弱與刪除歸納變量：如果循環(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同族84強度削弱與刪除歸納變量的算法：（1）利用循環(huán)不變運算信息，找出循