編譯原理第9章

1、第第9 9章章 代碼優(yōu)化代碼優(yōu)化目錄 9.1 優(yōu)化技術(shù)簡(jiǎn)介優(yōu)化技術(shù)簡(jiǎn)介 9.2 局部?jī)?yōu)化局部?jī)?yōu)化 9.3 控制流分析和循環(huán)優(yōu)化控制流分析和循環(huán)優(yōu)化9.1 優(yōu)化技術(shù)簡(jiǎn)介一、代碼優(yōu)化的目的一、代碼優(yōu)化的目的 提高目標(biāo)代碼的運(yùn)行效率。提高目標(biāo)代碼的運(yùn)行效率。注：效率是指目標(biāo)代碼運(yùn)行時(shí)間較短，占注：效率是指目標(biāo)代碼運(yùn)行時(shí)間較短，占有空間較少。有空間較少。二、代碼優(yōu)化的實(shí)質(zhì)二、代碼優(yōu)化的實(shí)質(zhì) 代碼優(yōu)化實(shí)際上是對(duì)代碼進(jìn)行代碼優(yōu)化實(shí)際上是對(duì)代碼進(jìn)行等價(jià)等價(jià)變變換，由一組代碼變成換，由一組代碼變成運(yùn)行結(jié)果相同運(yùn)行結(jié)果相同的另的另一組代碼。一組代碼。與機(jī)器無(wú)關(guān)的優(yōu)化與機(jī)器無(wú)關(guān)的優(yōu)化-對(duì)中間代碼進(jìn)行；對(duì)中間代碼進(jìn)

2、行；依賴于機(jī)器的優(yōu)化依賴于機(jī)器的優(yōu)化-對(duì)目標(biāo)代碼進(jìn)行對(duì)目標(biāo)代碼進(jìn)行三、優(yōu)化階段三、優(yōu)化階段四、優(yōu)化分類四、優(yōu)化分類 根據(jù)優(yōu)化所涉及的程序范圍分成根據(jù)優(yōu)化所涉及的程序范圍分成: :(1)(1)局部?jī)?yōu)化局部?jī)?yōu)化:(:(基本塊基本塊) )(2)(2)循環(huán)優(yōu)化循環(huán)優(yōu)化: :對(duì)循環(huán)中的代碼進(jìn)行優(yōu)化對(duì)循環(huán)中的代碼進(jìn)行優(yōu)化(3)(3)全局優(yōu)化全局優(yōu)化: :在整個(gè)程序范圍內(nèi)的優(yōu)化在整個(gè)程序范圍內(nèi)的優(yōu)化五、常用優(yōu)化技術(shù)簡(jiǎn)介五、常用優(yōu)化技術(shù)簡(jiǎn)介1.刪除多余運(yùn)算刪除多余運(yùn)算2.循環(huán)不變代碼外提循環(huán)不變代碼外提3.強(qiáng)度削弱強(qiáng)度削弱4.變換循環(huán)控制條件變換循環(huán)控制條件5.合并已知量與復(fù)寫傳播合并已知量與復(fù)寫傳播6.刪除

3、無(wú)用賦值刪除無(wú)用賦值目的：提高目標(biāo)代碼速度。目的：提高目標(biāo)代碼速度。例如：例如：p:=0for i:=1 to 20 do p:=p+ai*bi1.刪除多余運(yùn)算（刪除公共子表達(dá)式）：刪除多余運(yùn)算（刪除公共子表達(dá)式）：(1)p:=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)p:=p+t7(11)i:=i+1(12)if i=20 goto(3)(1)p:=0(2)i:=1(3)t1:=4*i(4)t2:=addr(a)-4(5)t3:=t2t1(

4、6)t4:=t1(7)t5:=addr(b)-4(8)t6:=t5t4(9)t7:=t3*t6(10)p:=p+t7(11)i:=i+1(12)if i=20 goto(3) 減少循環(huán)中代碼總數(shù)的重要辦法。減少循環(huán)中代碼總數(shù)的重要辦法。方法：把方法：把循環(huán)不變運(yùn)算循環(huán)不變運(yùn)算，即其結(jié)果獨(dú)立于循環(huán)執(zhí)行，即其結(jié)果獨(dú)立于循環(huán)執(zhí)行次數(shù)的表達(dá)式提到循環(huán)的前面，使之只在循環(huán)外次數(shù)的表達(dá)式提到循環(huán)的前面，使之只在循環(huán)外計(jì)算一次。計(jì)算一次。例如：例如：p:=0for i:=1 to 20 do p:=p+ai*bi2、代碼外提、代碼外提(1)p:=0(2)i:=1(3)t1:=4*i(4)t2:=addr(a

5、)-4(5)t3:=t2t1(6)t4:=t1(7)t5:=addr(b)-4(8)t6:=t5t4(9)t7:=t3*t6(10)p:=p+t7(11)i:=i+1(12)if i=20 goto(3)(1)p:=0(2)i:=1(3)t1:=4*i(5)t3:=t2t1(8)t6:=t5t4(9)t7:=t3*t6(10)p:=p+t7(11)i:=i+1(12)if i=20 goto(3)(4)t2:=addr(a)-4(7)t5:=addr(b)-4(6)t4:=t1基本思想：把強(qiáng)度大的運(yùn)算換算成強(qiáng)度小的?；舅枷耄喊褟?qiáng)度大的運(yùn)算換算成強(qiáng)度小的。例如：例如：a) i*2 = 2*i

6、= i+i = i1b) i/2 = (int)(i*0.5)c) 0-1 = -1d) f*2 = 2.0 * f = f + fe) f/2.0 = f*0.53.強(qiáng)度削弱強(qiáng)度削弱(1)p:=0(2)i:=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)p:=p+t7(11)i:=i+1(12)if i=20 goto(3)(1)p:=0(2)i:=1(4)t2:=addr(a)-4(7)t5:=addr(b)-4(5)t3:=t2t1(6)t4:=t1(8)

7、t6:=t5t4(9)t7:=t3*t6(10)p:=p+t7(11)i:=i+1(12)if i=20 goto(5)(3)t1:=4*i(3)t1:=t1+44、變換循環(huán)控制條件 如果在循環(huán)體內(nèi)存在一個(gè)變量如果在循環(huán)體內(nèi)存在一個(gè)變量t 與循環(huán)與循環(huán)控制變量控制變量i保持線性關(guān)系，同時(shí)在循環(huán)保持線性關(guān)系，同時(shí)在循環(huán)后面不引用后面不引用i，而除去，而除去i又不影響程序結(jié)又不影響程序結(jié)果，則可以由果，則可以由t 取代的控制循環(huán)次數(shù)的取代的控制循環(huán)次數(shù)的作用。從循環(huán)中刪除這這種方法稱為作用。從循環(huán)中刪除這這種方法稱為變變換循環(huán)控制條件換循環(huán)控制條件，或稱為，或稱為刪除歸納變量刪除歸納變量。(1)p

8、:=0(2)i:=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)p:=p+t7(11)i:=i+1(3)t1:=t1+4(12)if i=20 goto(5)(1)p:=0(2)i:=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)p:=p+t7(3)t1:=t1+4(12)if t1 =80 goto(5)5、合并已知量與復(fù)寫傳

9、播、合并已知量與復(fù)寫傳播 已知量就是指常數(shù)或在編譯時(shí)就能確定其值的已知量就是指常數(shù)或在編譯時(shí)就能確定其值的變量。變量。 若參加運(yùn)算的兩個(gè)對(duì)象在編譯時(shí)都是已知量，若參加運(yùn)算的兩個(gè)對(duì)象在編譯時(shí)都是已知量，則可以在編譯時(shí)候直接計(jì)算出它們的運(yùn)算結(jié)果，則可以在編譯時(shí)候直接計(jì)算出它們的運(yùn)算結(jié)果，不必等到程序運(yùn)行時(shí)再計(jì)算，這種變換稱為不必等到程序運(yùn)行時(shí)再計(jì)算，這種變換稱為合合并已知量并已知量或或常數(shù)合并常數(shù)合并。 復(fù)寫傳播復(fù)寫傳播是指盡量不引用那些在程序中僅僅只是指盡量不引用那些在程序中僅僅只傳遞信息而不改變其值，也不影響程序運(yùn)行結(jié)傳遞信息而不改變其值，也不影響程序運(yùn)行結(jié)果的變量。果的變量。 通過(guò)通過(guò)復(fù)制后

10、沒(méi)有再改變的值復(fù)制后沒(méi)有再改變的值可以互相替換，不可以互相替換，不會(huì)改變程序的結(jié)果會(huì)改變程序的結(jié)果。(1)p:=0(2)i:=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)p:=p+t7(3)t1:=t1+4(12)if t1=80 goto(5)(1)p:=0(2)i:=1(4)t2:=addr(a)-4(7)t5:=addr(b)(5)t3:=t2t1(6)t4:=t1(9)t7:=t3*t6(10)p:=p+t7(3)t1:=t1+4(12)if t1=

11、80 goto(5)(3)t1:=4(8)t6:=t5t1(1)p:=0(2)i:=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)p:=p+t7(3)t1:=t1+4(12)if t1=80 goto(5)(1)p:=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)p:=p+t7(3)t1:=t1+4(12)if t1=80 goto(5)6.刪除無(wú)用賦值刪

12、除無(wú)用賦值局部?jī)?yōu)化：基本塊內(nèi)的優(yōu)化局部?jī)?yōu)化：基本塊內(nèi)的優(yōu)化9.2局部?jī)?yōu)化局部?jī)?yōu)化一、基本塊一、基本塊1、定義、定義 程序中一個(gè)程序中一個(gè)只有一個(gè)入口和一個(gè)出口只有一個(gè)入口和一個(gè)出口的一段順序執(zhí)行的一段順序執(zhí)行的語(yǔ)句序列，稱為程序的一個(gè)基本塊。的語(yǔ)句序列，稱為程序的一個(gè)基本塊。注：注：1)一個(gè)給定的程序，可以劃分為一系列的基本塊一個(gè)給定的程序，可以劃分為一系列的基本塊。優(yōu)化在各基本塊中分別進(jìn)行。優(yōu)化在各基本塊中分別進(jìn)行。2)局部?jī)?yōu)化就是局限于基本塊范圍內(nèi)的優(yōu)化局部?jī)?yōu)化就是局限于基本塊范圍內(nèi)的優(yōu)化。3)在運(yùn)行基本塊時(shí)，只能從其入口進(jìn)入，從出口退在運(yùn)行基本塊時(shí)，只能從其入口進(jìn)入，從出口退出。出。a)

13、求出各基本塊的入口語(yǔ)句求出各基本塊的入口語(yǔ)句 對(duì)四元式程序，各個(gè)對(duì)四元式程序，各個(gè)基本塊的入口語(yǔ)句基本塊的入口語(yǔ)句是：是： 1)程序的程序的第一個(gè)語(yǔ)句第一個(gè)語(yǔ)句 ；或；或 2)能由條件轉(zhuǎn)移語(yǔ)句和無(wú)條件轉(zhuǎn)移語(yǔ)句能由條件轉(zhuǎn)移語(yǔ)句和無(wú)條件轉(zhuǎn)移語(yǔ)句轉(zhuǎn)移到達(dá)轉(zhuǎn)移到達(dá)的的語(yǔ)句；或語(yǔ)句；或 3)緊跟在緊跟在條件轉(zhuǎn)移語(yǔ)句條件轉(zhuǎn)移語(yǔ)句后面的語(yǔ)句。后面的語(yǔ)句。注：注：若條件語(yǔ)句由真轉(zhuǎn)移和假轉(zhuǎn)移兩條語(yǔ)句組成，若條件語(yǔ)句由真轉(zhuǎn)移和假轉(zhuǎn)移兩條語(yǔ)句組成，則跟在轉(zhuǎn)移語(yǔ)句后面的語(yǔ)句是指假轉(zhuǎn)移語(yǔ)句后面的則跟在轉(zhuǎn)移語(yǔ)句后面的語(yǔ)句是指假轉(zhuǎn)移語(yǔ)句后面的一條語(yǔ)句。一條語(yǔ)句。2、劃分基本塊算法、劃分基本塊算法b)根據(jù)入口語(yǔ)句，構(gòu)造其所屬

14、的基本塊根據(jù)入口語(yǔ)句，構(gòu)造其所屬的基本塊 一一入口語(yǔ)句所屬的基本塊入口語(yǔ)句所屬的基本塊是由該入口語(yǔ)是由該入口語(yǔ)句到句到: 下一入口語(yǔ)句下一入口語(yǔ)句(不包括該入口語(yǔ)句不包括該入口語(yǔ)句); 或到一轉(zhuǎn)移語(yǔ)句或到一轉(zhuǎn)移語(yǔ)句(包括轉(zhuǎn)移語(yǔ)句包括轉(zhuǎn)移語(yǔ)句); 或到一?；虻揭煌?halt)語(yǔ)句語(yǔ)句(包括該語(yǔ)句包括該語(yǔ)句) 之間的語(yǔ)句序列組成。之間的語(yǔ)句序列組成。 c)刪除不會(huì)被執(zhí)行的語(yǔ)句刪除不會(huì)被執(zhí)行的語(yǔ)句 凡是沒(méi)有納入到任何一個(gè)基本塊中的語(yǔ)凡是沒(méi)有納入到任何一個(gè)基本塊中的語(yǔ)句，都是程序控制流程所無(wú)法到達(dá)的語(yǔ)句句，都是程序控制流程所無(wú)法到達(dá)的語(yǔ)句，即不會(huì)被執(zhí)行到的語(yǔ)句，可將其刪除。，即不會(huì)被執(zhí)行到的語(yǔ)句，可將

15、其刪除。例：求最大公因子算法 begin read x; read y; while (x mod y0) do begin t:=x mod y; x:=y; y:=t end; write y end(1)read x(2)read y(3) t1:=x mod y(4) if t10 goto (6)(5)goto (10)(6)t:=x mod y(7)x:=y(8)y:=t(9)goto (3)(10)write y(11)halt四元式序列：四元式序列：(1)read x(2)read y(3) t1:=x mod y(4) if t10 goto (6)(5)goto (10)(

16、6)t:=x mod y(7)x:=y(8)y:=t(9)goto (3)(10)write y(11)halt基本塊的劃分：基本塊的劃分： 主要是進(jìn)行主要是進(jìn)行已知量合并、刪除公共子表達(dá)式、已知量合并、刪除公共子表達(dá)式、刪除無(wú)用賦值。刪除無(wú)用賦值。注：僅在一個(gè)基本塊中，是否是注：僅在一個(gè)基本塊中，是否是無(wú)用賦值無(wú)用賦值很難判很難判斷。這是因?yàn)?，無(wú)用賦值有以下情形：斷。這是因?yàn)?，無(wú)用賦值有以下情形： (a)對(duì)某變量對(duì)某變量a賦值后，在程序中沒(méi)有引用；賦值后，在程序中沒(méi)有引用； (b)對(duì)某變量對(duì)某變量a賦值后，在引用前又重新賦值；賦值后，在引用前又重新賦值； (c)對(duì)某變量對(duì)某變量a進(jìn)行自增賦值

17、，且它僅僅被用在進(jìn)行自增賦值，且它僅僅被用在自增運(yùn)算中。自增運(yùn)算中。對(duì)上面第一和第三種情況，應(yīng)進(jìn)行全局分析。對(duì)上面第一和第三種情況，應(yīng)進(jìn)行全局分析。3、塊內(nèi)優(yōu)化1、dag(有向無(wú)環(huán)圖有向無(wú)環(huán)圖)定義定義a)父子結(jié)點(diǎn)父子結(jié)點(diǎn) 若在一有向圖中，結(jié)點(diǎn)若在一有向圖中，結(jié)點(diǎn)ni有弧指向有弧指向nj，則稱，則稱ni是是nj的父結(jié)點(diǎn)，的父結(jié)點(diǎn)， nj是是ni的子結(jié)點(diǎn)。的子結(jié)點(diǎn)。b)路徑與環(huán)路路徑與環(huán)路 若在一有向圖中，結(jié)點(diǎn)若在一有向圖中，結(jié)點(diǎn)n1 n2 nk間存在有間存在有向弧向弧n1n2 nk,則稱則稱n1 到到nk之間存在一之間存在一條通路，若條通路，若n1 nk則該路徑稱為環(huán)路；則該路徑稱為環(huán)路；c)

18、有向無(wú)環(huán)圖有向無(wú)環(huán)圖 若有向圖中任一路徑都不是環(huán)路，則稱該圖若有向圖中任一路徑都不是環(huán)路，則稱該圖為無(wú)環(huán)路有向圖。為無(wú)環(huán)路有向圖。二、基本塊的二、基本塊的dag表示表示a)葉結(jié)點(diǎn)葉結(jié)點(diǎn) 以一以一標(biāo)識(shí)符標(biāo)識(shí)符(變量名變量名)或常數(shù)或常數(shù)作為標(biāo)記。即，該結(jié)點(diǎn)代作為標(biāo)記。即，該結(jié)點(diǎn)代表該變量或常數(shù)的值。表該變量或常數(shù)的值。注：注：1)若葉結(jié)點(diǎn)代表變量若葉結(jié)點(diǎn)代表變量a的地址，則標(biāo)記為的地址，則標(biāo)記為addr(a)。 2)通常把葉結(jié)點(diǎn)上作為標(biāo)記的標(biāo)識(shí)符加上下標(biāo)通常把葉結(jié)點(diǎn)上作為標(biāo)記的標(biāo)識(shí)符加上下標(biāo)0，以表示它是該變量的初值。以表示它是該變量的初值。 b)內(nèi)部結(jié)點(diǎn)內(nèi)部結(jié)點(diǎn) 以一以一運(yùn)算符運(yùn)算符作為標(biāo)記。

19、即，該結(jié)點(diǎn)代表應(yīng)用該運(yùn)算作為標(biāo)記。即，該結(jié)點(diǎn)代表應(yīng)用該運(yùn)算符對(duì)其后繼結(jié)點(diǎn)所代表的值進(jìn)行運(yùn)算的結(jié)果。符對(duì)其后繼結(jié)點(diǎn)所代表的值進(jìn)行運(yùn)算的結(jié)果。c)附標(biāo)附標(biāo)：圖中各個(gè)結(jié)點(diǎn)上可能：圖中各個(gè)結(jié)點(diǎn)上可能附加一個(gè)或多個(gè)標(biāo)識(shí)符附加一個(gè)或多個(gè)標(biāo)識(shí)符，表示這些標(biāo)識(shí)符具有該結(jié)點(diǎn)所代表的值，這簡(jiǎn)稱表示這些標(biāo)識(shí)符具有該結(jié)點(diǎn)所代表的值，這簡(jiǎn)稱附標(biāo)附標(biāo)。2、dag結(jié)點(diǎn)標(biāo)記或附標(biāo)結(jié)點(diǎn)標(biāo)記或附標(biāo)例如：a:=b op c 即四元式(op,b,c,a)的dag圖為：注：注：1)圖中的有向弧都省去箭頭。圖中的有向弧都省去箭頭。2)結(jié)點(diǎn)結(jié)點(diǎn)ni是構(gòu)造是構(gòu)造dag過(guò)程中給予各結(jié)點(diǎn)的過(guò)程中給予各結(jié)點(diǎn)的編號(hào)編號(hào);3)各結(jié)點(diǎn)各結(jié)點(diǎn)下面下面的符

20、號(hào)（運(yùn)算符、變量、常數(shù)）是各結(jié)的符號(hào)（運(yùn)算符、變量、常數(shù)）是各結(jié)點(diǎn)的標(biāo)記點(diǎn)的標(biāo)記;4)各結(jié)點(diǎn)各結(jié)點(diǎn)右邊右邊的標(biāo)識(shí)符是結(jié)點(diǎn)的附標(biāo)的標(biāo)識(shí)符是結(jié)點(diǎn)的附標(biāo)。n1n2n3bcaop 根據(jù)其對(duì)應(yīng)結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)，可分為根據(jù)其對(duì)應(yīng)結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)，可分為0型、型、1型、型、2型和型和3型四種類型。型四種類型。 a)0型型a:=b, goto(s)即四元式即四元式(:=,b,_,a),其其dag結(jié)點(diǎn)為結(jié)點(diǎn)為0型：型： n1ba3、四元式的、四元式的dag結(jié)點(diǎn)類型結(jié)點(diǎn)類型n1sb)1型型a:=op b，即四元式，即四元式(op,b,_,a)，其，其dag結(jié)點(diǎn)結(jié)點(diǎn)為為1型：型：n1ban2opc)2型型 a:=b

21、 op c，即四元式，即四元式(op,b,c,a)，其，其dag結(jié)點(diǎn)為結(jié)點(diǎn)為2型；型；a:=bc，即四元式，即四元式(=,bc,_,a)，其，其dag結(jié)點(diǎn)為結(jié)點(diǎn)為2型；型；if b rop c goto (s)即四元式即四元式(jrop,b,c,(s)其其dag結(jié)點(diǎn)為結(jié)點(diǎn)為2型型n1n2n3bcaopn1n2n3bca=n1n2n3bc(s)ropd)3型型 dc:=b即四元式即四元式(=,b,_,dc)，其，其dag結(jié)點(diǎn)為結(jié)點(diǎn)為3型：型：n2n3n4bc=n1d說(shuō)明：說(shuō)明：大寫字母（大寫字母（a、b）表示四元式中變量名；）表示四元式中變量名； node(a):表示表示a在在dag中的相應(yīng)結(jié)點(diǎn)

22、，其值可以為中的相應(yīng)結(jié)點(diǎn)，其值可以為n或無(wú)定義?；驘o(wú)定義。n表示表示dag中的一個(gè)結(jié)點(diǎn)值。中的一個(gè)結(jié)點(diǎn)值。由基本塊構(gòu)造由基本塊構(gòu)造dag的算法如下：的算法如下：將元表和結(jié)點(diǎn)表置空。將元表和結(jié)點(diǎn)表置空。對(duì)基本塊內(nèi)每個(gè)四元式對(duì)基本塊內(nèi)每個(gè)四元式(op,b,c,a)進(jìn)行如下操作：進(jìn)行如下操作： 1)查元表中有無(wú)結(jié)點(diǎn)查元表中有無(wú)結(jié)點(diǎn)b，有則返回其序號(hào)，無(wú)則建，有則返回其序號(hào)，無(wú)則建立該結(jié)點(diǎn)并返回序號(hào)；立該結(jié)點(diǎn)并返回序號(hào)；2)若四元式類型為若四元式類型為0型，則不做任何操作；型，則不做任何操作；4 4、基本塊的、基本塊的dag構(gòu)造算法構(gòu)造算法3)若四元式類型為若四元式類型為1型型(即：即：a:=op b

23、)，則，則 if node(b).標(biāo)記常量標(biāo)記常量 then /*葉葉*/ 執(zhí)行執(zhí)行op b 得值得值p /*合并已知量合并已知量*/ , 若若node(b)是當(dāng)前四元式建立的，就刪去。是當(dāng)前四元式建立的，就刪去。 查有無(wú)查有無(wú)node(p)結(jié)點(diǎn)，有就返回結(jié)點(diǎn)序號(hào)，結(jié)點(diǎn)，有就返回結(jié)點(diǎn)序號(hào)， 沒(méi)有就建立并返回其序號(hào)沒(méi)有就建立并返回其序號(hào) else 查結(jié)點(diǎn)表是否有一結(jié)點(diǎn)，其后繼為查結(jié)點(diǎn)表是否有一結(jié)點(diǎn)，其后繼為node(b)，標(biāo)，標(biāo) 記為記為op，有就返回結(jié)點(diǎn)序號(hào)，沒(méi)有就建立并返回其，有就返回結(jié)點(diǎn)序號(hào)，沒(méi)有就建立并返回其序號(hào)序號(hào)4)若四元式類型為若四元式類型為2型型(即：即：a:=b op c)，則

24、，則， 查元表中有無(wú)結(jié)點(diǎn)查元表中有無(wú)結(jié)點(diǎn)node(c) ,有就返回結(jié)點(diǎn)序號(hào)，沒(méi)有就返回結(jié)點(diǎn)序號(hào)，沒(méi)有就建立并返回其序號(hào)有就建立并返回其序號(hào);if ( node(b).標(biāo)記常量標(biāo)記常量) and (node(c).標(biāo)記常量標(biāo)記常量 ) 執(zhí)行執(zhí)行b op c 得值得值p /*合并已知量合并已知量*/ 若若node(b), node(c)是當(dāng)前四元式建立的，就刪去是當(dāng)前四元式建立的，就刪去; 查有無(wú)結(jié)點(diǎn)查有無(wú)結(jié)點(diǎn)node(p) ,有就返回結(jié)點(diǎn)序號(hào)，沒(méi)有就建有就返回結(jié)點(diǎn)序號(hào)，沒(méi)有就建立并返回其序號(hào)立并返回其序號(hào); else 查結(jié)點(diǎn)表是否有一結(jié)點(diǎn)，其左后繼為查結(jié)點(diǎn)表是否有一結(jié)點(diǎn)，其左后繼為node(b)

25、且右且右后繼為后繼為node(c)，標(biāo)記為，標(biāo)記為op，有就返回結(jié)點(diǎn)序號(hào)，沒(méi)，有就返回結(jié)點(diǎn)序號(hào)，沒(méi)有就建立并返回其序號(hào)。有就建立并返回其序號(hào)。; 5) 如果如果node（a）無(wú)定義，則把）無(wú)定義，則把a(bǔ)附加在結(jié)點(diǎn)附加在結(jié)點(diǎn)n上并令上并令node（a）n；否則先把；否則先把a(bǔ)從從node（a）結(jié)點(diǎn)上的附加標(biāo)識(shí)符集中刪除（注意，如果結(jié)點(diǎn)上的附加標(biāo)識(shí)符集中刪除（注意，如果node（a）是葉結(jié)點(diǎn)，則其標(biāo)記）是葉結(jié)點(diǎn)，則其標(biāo)記a不刪除），把不刪除），把a(bǔ)附加到附加到新結(jié)點(diǎn)新結(jié)點(diǎn)n上并令上并令node（a）n。轉(zhuǎn)處理下一四元。轉(zhuǎn)處理下一四元式。式。 例如：下面程序用來(lái)求圓環(huán)內(nèi)外例如：下面程序用來(lái)求圓環(huán)內(nèi)外

26、圓周之和及圓環(huán)正反兩面面積圓周之和及圓環(huán)正反兩面面積之和。對(duì)其優(yōu)化：之和。對(duì)其優(yōu)化： pi:=3.14 a:2*pi*(r+r); b:=a; b:=2* pi*(r+r)*(r-r)由語(yǔ)法制導(dǎo)翻譯生成右邊的四元由語(yǔ)法制導(dǎo)翻譯生成右邊的四元式序列式序列(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)造為四元式程序段構(gòu)造dag. to 3.14 (a)n1(1)t0:=3.14(2)t1:=2* t0(3)t2:=r

27、+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 t0 t1 3.14 6.28 (b)n2n1(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 t2 + t0 t1 3.14 6.28 r r (c)n2n5n3n1n4(1)t0:=3.14(2)t1:=2* t0(3)t2:=r+r(4)a:=t1*t2(5)b:=a(6)

28、t3:=2* t0(7)t4:=r+r(8)t5:=t3*t4(9)t6:=r-r(10)b:=t5*t6 a * t2 + t0 t1 3.14 6.28 r r (d)n2n5n3n1n4n6(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 a,b * t2 + t0 t1 3.14 6.28 r r (e)n2n5n3n1n4n6(1)t0:=3.14(2)t1:=2* t0(3)t2:=r+r(4)a:=t1*t2(5)b

29、:=a(6)t3:=2* t0(7)t4:=r+r(8)t5:=t3*t4(9)t6:=r-r(10)b:=t5*t6 a,b * t2 + t0 t1,t3 3.14 6.28 r r (f)n2n5n3n1n4n6(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 a,b * t2,t4 + t0 t1,t3 3.14 6.28 r r (g)n2n5n3n1n4n6(1)t0:=3.14(2)t1:=2* t0(3)t2:=r

30、+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 a,b,t5 * t2,t4 + t0 t1,t3 3.14 6.28 r r (h)n2n5n3n1n4n6(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 a,b,t5 * t2,t4 t6 + - t0 t1,t3 3.14 6.28 r rn2n5n3n7n1n4n6(1

31、)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 b * a,t5 * t2,t4 t6 + - t0 t1,t3 3.14 6.28 r r (j)n2n5n3n7n1n4n6n8(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*t61、可做到三種優(yōu)化可做到三種優(yōu)化 a)合并

32、已知量合并已知量 對(duì)任何一個(gè)四元式，若其中參與運(yùn)算的對(duì)象均是編譯對(duì)任何一個(gè)四元式，若其中參與運(yùn)算的對(duì)象均是編譯時(shí)的已知量，則合并已知量，并用合并后算出的常量生時(shí)的已知量，則合并已知量，并用合并后算出的常量生成一個(gè)葉結(jié)點(diǎn)。若參與運(yùn)算的已知量的葉結(jié)點(diǎn)是當(dāng)前四成一個(gè)葉結(jié)點(diǎn)。若參與運(yùn)算的已知量的葉結(jié)點(diǎn)是當(dāng)前四元式建立的結(jié)果，則可刪除。元式建立的結(jié)果，則可刪除。 b)刪除對(duì)變量的前一個(gè)賦值刪除對(duì)變量的前一個(gè)賦值，即刪除該變量的前一個(gè)附，即刪除該變量的前一個(gè)附標(biāo)。標(biāo)。 c)檢查公共子表達(dá)式檢查公共子表達(dá)式 對(duì)具有公共子表達(dá)式的所有四元式，只產(chǎn)生一個(gè)計(jì)算對(duì)具有公共子表達(dá)式的所有四元式，只產(chǎn)生一個(gè)計(jì)算該表達(dá)式

33、值的內(nèi)部結(jié)點(diǎn)，而將那些被賦值的變量附加到該表達(dá)式值的內(nèi)部結(jié)點(diǎn)，而將那些被賦值的變量附加到該結(jié)點(diǎn)。該結(jié)點(diǎn)。三、dag在基本塊優(yōu)化中的作用2、利用利用dag圖還原四元式序列圖還原四元式序列 a)若為葉結(jié)點(diǎn)，無(wú)附標(biāo)，則不生成任何四元式；若為葉結(jié)點(diǎn)，無(wú)附標(biāo)，則不生成任何四元式； b)若為葉結(jié)點(diǎn)，標(biāo)記為若為葉結(jié)點(diǎn)，標(biāo)記為b，附標(biāo)為，附標(biāo)為a，則生成，則生成a:=b四元四元式；若有多個(gè)附標(biāo)，則生成值為式；若有多個(gè)附標(biāo)，則生成值為b的相應(yīng)賦值語(yǔ)句四元的相應(yīng)賦值語(yǔ)句四元式式 c)若為中間結(jié)點(diǎn)，有附標(biāo)，則根據(jù)其標(biāo)記若為中間結(jié)點(diǎn)，有附標(biāo)，則根據(jù)其標(biāo)記op，生成相應(yīng)，生成相應(yīng)四元式四元式(如如a:=b op c,

34、a:=op b, a:=bc或或if b rop c goto (s)；若有多個(gè)附標(biāo)，則除了第一個(gè)附標(biāo)用于生成相應(yīng)四；若有多個(gè)附標(biāo)，則除了第一個(gè)附標(biāo)用于生成相應(yīng)四元式，其它生成值為第一個(gè)附標(biāo)的賦值語(yǔ)句四元式元式，其它生成值為第一個(gè)附標(biāo)的賦值語(yǔ)句四元式 d)若中間結(jié)點(diǎn)無(wú)附標(biāo)，則添加一個(gè)臨時(shí)附標(biāo)若中間結(jié)點(diǎn)無(wú)附標(biāo)，則添加一個(gè)臨時(shí)附標(biāo)sa， 然后然后轉(zhuǎn)轉(zhuǎn)c) (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 b * a,t5 * t2,t

35、4 t6 + - t0 t1,t3 3.14 6.28 r r (j)n2n5n3n7n1n4n6n83、獲得其它優(yōu)化信息、獲得其它優(yōu)化信息 a)在基本塊外定值并在基本塊內(nèi)被引用的所有標(biāo)識(shí)符，在基本塊外定值并在基本塊內(nèi)被引用的所有標(biāo)識(shí)符，就是作為葉結(jié)點(diǎn)標(biāo)記的那些標(biāo)識(shí)符。就是作為葉結(jié)點(diǎn)標(biāo)記的那些標(biāo)識(shí)符。 b)在基本塊內(nèi)被在基本塊內(nèi)被定值定值，且該值能在基本塊后面被引用，且該值能在基本塊后面被引用的所有標(biāo)識(shí)符，就是的所有標(biāo)識(shí)符，就是dag各結(jié)點(diǎn)上的那些各結(jié)點(diǎn)上的那些附標(biāo)附標(biāo)。注：可利用上述信息，進(jìn)一步刪除四元式序列中其它注：可利用上述信息，進(jìn)一步刪除四元式序列中其它情況的無(wú)用賦值，如，若某結(jié)點(diǎn)附標(biāo)

36、，在該基本塊后情況的無(wú)用賦值，如，若某結(jié)點(diǎn)附標(biāo)，在該基本塊后面不會(huì)被引用，則不生成對(duì)該附標(biāo)賦值的四元式；若面不會(huì)被引用，則不生成對(duì)該附標(biāo)賦值的四元式；若某結(jié)點(diǎn)無(wú)附標(biāo)或其附標(biāo)在基本塊后面不會(huì)被引用，且某結(jié)點(diǎn)無(wú)附標(biāo)或其附標(biāo)在基本塊后面不會(huì)被引用，且無(wú)父結(jié)點(diǎn)，則不生成計(jì)算該結(jié)點(diǎn)值的四元式；若兩個(gè)無(wú)父結(jié)點(diǎn)，則不生成計(jì)算該結(jié)點(diǎn)值的四元式；若兩個(gè)相鄰的四元式中的第一個(gè)四元式計(jì)算出來(lái)的值只在第相鄰的四元式中的第一個(gè)四元式計(jì)算出來(lái)的值只在第二個(gè)四元式中被引用，則可合并這兩個(gè)四元式。二個(gè)四元式中被引用，則可合并這兩個(gè)四元式。 (1)t0:=3.14 (2)t1:=6.28 (3) t3:=6.28 (4) t2

37、:=r+r (5) t4:=t2 (6)a:=6.28*t2 (7) t5:=a (8) t6:=r-r (9) b:=a*t6s1:=r+ra:=6.28*s1s2:=r-rb:=a*s211/4/202151一、控制流分析作用一、控制流分析作用1、是數(shù)據(jù)流程分析的基礎(chǔ)、是數(shù)據(jù)流程分析的基礎(chǔ)2、找出程序中的循環(huán)、找出程序中的循環(huán)注：注：1)循環(huán)包括循環(huán)語(yǔ)句構(gòu)成的循環(huán)及條件循環(huán)包括循環(huán)語(yǔ)句構(gòu)成的循環(huán)及條件轉(zhuǎn)移和無(wú)條件轉(zhuǎn)移構(gòu)成的循環(huán)。轉(zhuǎn)移和無(wú)條件轉(zhuǎn)移構(gòu)成的循環(huán)。2)為了找出程序中的循環(huán)，也需要進(jìn)行程序?yàn)榱苏页龀绦蛑械难h(huán)，也需要進(jìn)行程序數(shù)據(jù)流程分析。數(shù)據(jù)流程分析。9.3 控制流分析和循環(huán)優(yōu)化控制

38、流分析和循環(huán)優(yōu)化11/4/2021521、程序流圖定義程序流圖定義 以以基本塊基本塊作為結(jié)點(diǎn)，作為結(jié)點(diǎn)，控制程序流向控制程序流向作為有向作為有向弧，畫出的圖，稱為程序流圖?；?，畫出的圖，稱為程序流圖。注；注；1)程序流圖的特點(diǎn)是具有程序流圖的特點(diǎn)是具有唯一首結(jié)點(diǎn)唯一首結(jié)點(diǎn)的有的有向圖。所謂向圖。所謂首結(jié)點(diǎn)首結(jié)點(diǎn)，是包含程序第一個(gè)語(yǔ)句的，是包含程序第一個(gè)語(yǔ)句的基本塊?；緣K。2)從首結(jié)點(diǎn)沿著流圖可到達(dá)任何結(jié)點(diǎn)。從首結(jié)點(diǎn)沿著流圖可到達(dá)任何結(jié)點(diǎn)。二、程序流圖與必經(jīng)結(jié)點(diǎn)集二、程序流圖與必經(jīng)結(jié)點(diǎn)集程序流圖程序流圖（流圖）（流圖）：具有唯一首結(jié)點(diǎn)的有向圖：具有唯一首結(jié)點(diǎn)的有向圖g=（n，e，n0） n：結(jié)

39、點(diǎn)集：結(jié)點(diǎn)集 基本塊集基本塊集 e：有向邊集：有向邊集 n0：首結(jié)點(diǎn)：首結(jié)點(diǎn) 包含程序第一個(gè)包含程序第一個(gè) 語(yǔ)句的基本塊語(yǔ)句的基本塊程序流圖三元式定義程序流圖三元式定義有向邊集的構(gòu)成：有向邊集的構(gòu)成： 滿足下列條件之一時(shí)，結(jié)點(diǎn)滿足下列條件之一時(shí)，結(jié)點(diǎn) i到結(jié)點(diǎn)到結(jié)點(diǎn)j有有向有有向邊：邊：基本塊基本塊j在程序的位置在程序的位置緊跟緊跟在在i后后,且且i的出口的出口語(yǔ)句語(yǔ)句不是不是無(wú)條件轉(zhuǎn)移無(wú)條件轉(zhuǎn)移goto(s)或停語(yǔ)句或停語(yǔ)句i的出口是的出口是goto(s)或或if goto(s),而而(s)是是j的的入口語(yǔ)句入口語(yǔ)句(1) read x(2) read y(3) t1:=x mod y(4)

40、 if t1=0 goto (8)(5)x:=y(6)y:=t1(7)goto (3)(8)write y(9)haltb1b2b3b4b1b2b3b4程序流圖分析程序流圖中結(jié)點(diǎn)間的關(guān)系分析程序流圖中結(jié)點(diǎn)間的關(guān)系（1）m dom n 定義定義 在程序流圖中在程序流圖中,對(duì)任意兩個(gè)結(jié)點(diǎn)對(duì)任意兩個(gè)結(jié)點(diǎn)m和和n,如果從流圖的如果從流圖的首結(jié)點(diǎn)出發(fā)首結(jié)點(diǎn)出發(fā),到達(dá)到達(dá)n的任意的任意通路都要經(jīng)過(guò)通路都要經(jīng)過(guò)m,則稱則稱m是是n的必經(jīng)結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn),記記為為m dom n ( a,a dom a)集集 定義定義 結(jié)點(diǎn)結(jié)點(diǎn)n的所有的所有的集合的集合,稱為結(jié)點(diǎn)稱為結(jié)點(diǎn)n的必經(jīng)結(jié)點(diǎn)集的必經(jīng)結(jié)點(diǎn)集,記為記為d(n

41、).集定義1234657各結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)集為：各結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎ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,7 自反性：自反性： a,a dom a 傳遞性：對(duì)流圖中的任意結(jié)點(diǎn)傳遞性：對(duì)流圖中的任意結(jié)點(diǎn)a,b和和c， 若若a dom b, b dom c, 則有則有a dom c。 反對(duì)稱性：若反對(duì)稱性：若a dom b且且 b dom a，則，則有有a=b.dom關(guān)系是一個(gè)偏序關(guān)系。關(guān)系是一個(gè)偏序關(guān)系。11/4/2021591、基本思想、基本思想 根據(jù)一個(gè)結(jié)點(diǎn)的所有父結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)集，根據(jù)一個(gè)結(jié)

42、點(diǎn)的所有父結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)集，求出該結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)集。求出該結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)集。 若設(shè)結(jié)點(diǎn)若設(shè)結(jié)點(diǎn)n的父結(jié)點(diǎn)是的父結(jié)點(diǎn)是p1,p2,pk，則，則d(n)=(d(p1)d(p2) d(pk)n2、具體實(shí)現(xiàn)方式、具體實(shí)現(xiàn)方式 使用迭代方法：比較相鄰兩次迭代結(jié)果，若使用迭代方法：比較相鄰兩次迭代結(jié)果，若相同，則結(jié)束。相同，則結(jié)束。三、求必經(jīng)結(jié)點(diǎn)集算法三、求必經(jīng)結(jié)點(diǎn)集算法3、算法、算法設(shè)全部結(jié)點(diǎn)集合為設(shè)全部結(jié)點(diǎn)集合為n，首結(jié)點(diǎn)為，首結(jié)點(diǎn)為n0， d(n0)=n0; for nn-n0 do d(n):=n; /*置初值置初值*/ change=true; while change /*完成若干迭代完成若干

43、迭代*/ change=false; for n n-n0 do /*完成一次迭代完成一次迭代*/ newd= (d(p1)d(p2) d(pk)n; if d(n)newd change=true; d(n):=newd 注：此算法中沒(méi)有規(guī)定計(jì)算結(jié)點(diǎn)的順序，注：此算法中沒(méi)有規(guī)定計(jì)算結(jié)點(diǎn)的順序，若順序選的不好，效率可能很低。所以使若順序選的不好，效率可能很低。所以使用算法之前先將流圖中各結(jié)點(diǎn)排序，此序用算法之前先將流圖中各結(jié)點(diǎn)排序，此序?yàn)樯疃葹橹髋判?。為深度為主排序?1/4/2021621、基本思想、基本思想 利用必經(jīng)結(jié)點(diǎn)集求出流圖中的回邊，利用回邊利用必經(jīng)結(jié)點(diǎn)集求出流圖中的回邊，利用回邊找

44、出流圖中的循環(huán)。找出流圖中的循環(huán)。2、回邊定義、回邊定義 設(shè)設(shè)ab是流圖中一條有向邊，若是流圖中一條有向邊，若b dom a ，則，則ab是流圖中一條回邊。是流圖中一條回邊。注：注：1)可應(yīng)用必經(jīng)結(jié)點(diǎn)集求出流圖中的回邊?？蓱?yīng)用必經(jīng)結(jié)點(diǎn)集求出流圖中的回邊。2) 設(shè)設(shè)nd是回邊，則該回邊構(gòu)成的循環(huán)包括如下是回邊，則該回邊構(gòu)成的循環(huán)包括如下結(jié)點(diǎn)：結(jié)點(diǎn)：n、d以及不經(jīng)過(guò)以及不經(jīng)過(guò)d能到達(dá)能到達(dá)n的所有結(jié)點(diǎn)。的所有結(jié)點(diǎn)。四、查找循環(huán)算法四、查找循環(huán)算法例：求出下圖的所有回邊例：求出下圖的所有回邊1234657d(1)=1d(2)=1,2d(3)=1,2,3d(4)=1,2,4d(5)=1,2,4,5d(

45、6)=1,2,4,6d(7)=1,2,4,7有有6 dom 6 ,4 dom 7 ,2 dom 4故：故：66，74，42都是流圖都是流圖的回邊。的回邊。解：首先，求出必經(jīng)結(jié)點(diǎn)集：解：首先，求出必經(jīng)結(jié)點(diǎn)集：3、查找循環(huán)的算法、查找循環(huán)的算法1)找出回邊找出回邊nd；2)則則n,d必定屬于必定屬于nd回邊組成的循環(huán)回邊組成的循環(huán)l中，即中，即, l:=n,d;3)若若 nd且且n的父結(jié)點(diǎn)的父結(jié)點(diǎn)n不在不在l中，則中，則將它添至將它添至l中，即中，即l:=ln;4)對(duì)對(duì)3)求出的父結(jié)點(diǎn)求出的父結(jié)點(diǎn)n重復(fù)執(zhí)行重復(fù)執(zhí)行3)，直，直至不再有新結(jié)點(diǎn)加入至不再有新結(jié)點(diǎn)加入l為止。為止。 1234657回邊對(duì)

46、應(yīng)的循環(huán)結(jié)點(diǎn)：回邊對(duì)應(yīng)的循環(huán)結(jié)點(diǎn)：667 442循環(huán)結(jié)點(diǎn)：循環(huán)結(jié)點(diǎn)：6循環(huán)結(jié)點(diǎn)：循環(huán)結(jié)點(diǎn)：7,4,5,6循環(huán)結(jié)點(diǎn)：循環(huán)結(jié)點(diǎn)：4,2,3,7,5,64、定理、定理 對(duì)于對(duì)于循環(huán)循環(huán)必定滿足強(qiáng)連通，而且只有唯一入必定滿足強(qiáng)連通，而且只有唯一入口點(diǎn)?？邳c(diǎn)。注：注： 1)強(qiáng)連通是指循環(huán)中強(qiáng)連通是指循環(huán)中任意兩個(gè)結(jié)點(diǎn)都有通路任意兩個(gè)結(jié)點(diǎn)都有通路，單結(jié)點(diǎn)循環(huán)也有一弧指向自身。它保證了循，單結(jié)點(diǎn)循環(huán)也有一弧指向自身。它保證了循環(huán)內(nèi)各結(jié)點(diǎn)的代碼都可反復(fù)執(zhí)行。環(huán)內(nèi)各結(jié)點(diǎn)的代碼都可反復(fù)執(zhí)行。 2)唯一入口點(diǎn)是指要到達(dá)唯一入口點(diǎn)是指要到達(dá)循環(huán)內(nèi)任意結(jié)點(diǎn)必循環(huán)內(nèi)任意結(jié)點(diǎn)必須經(jīng)過(guò)此入口點(diǎn)須經(jīng)過(guò)此入口點(diǎn)。它保證了循環(huán)優(yōu)化

47、時(shí)，可將。它保證了循環(huán)優(yōu)化時(shí)，可將代碼外提到唯一入口點(diǎn)前的前置結(jié)點(diǎn)中。代碼外提到唯一入口點(diǎn)前的前置結(jié)點(diǎn)中。11/4/202167五、可歸約流圖五、可歸約流圖 當(dāng)且僅當(dāng)流圖中除去當(dāng)且僅當(dāng)流圖中除去回邊外，其余的邊構(gòu)回邊外，其余的邊構(gòu)成一個(gè)無(wú)環(huán)路回路，成一個(gè)無(wú)環(huán)路回路，就稱流圖為可歸約流就稱流圖為可歸約流圖。圖。左圖為可歸約流圖。左圖為可歸約流圖。5 47 621 311/4/202168 循環(huán)優(yōu)化：三種重要技術(shù)循環(huán)優(yōu)化：三種重要技術(shù) 代碼外提：產(chǎn)生的結(jié)果獨(dú)立于循環(huán)執(zhí)行次數(shù)的代碼外提：產(chǎn)生的結(jié)果獨(dú)立于循環(huán)執(zhí)行次數(shù)的表達(dá)式，放到循環(huán)前面。表達(dá)式，放到循環(huán)前面。 強(qiáng)度削弱：把程序中執(zhí)行時(shí)間較長(zhǎng)的運(yùn)算替

48、換強(qiáng)度削弱：把程序中執(zhí)行時(shí)間較長(zhǎng)的運(yùn)算替換為時(shí)間較短的運(yùn)算。為時(shí)間較短的運(yùn)算。 刪除歸納變量：刪除歸納變量： 對(duì)形如對(duì)形如i:=i+c的賦值的賦值 c為循環(huán)不變量，稱為循環(huán)不變量，稱i為為基本歸納變量?；練w納變量。對(duì)形如對(duì)形如j:=c1*i的賦值稱的賦值稱j為歸納變量為歸納變量六、六、 循環(huán)優(yōu)化循環(huán)優(yōu)化（一）、代碼外提（一）、代碼外提1、循環(huán)不變量定義、循環(huán)不變量定義 形如形如(s) a:=b op c四元式，若四元式，若 (1) b、c為常量；為常量； (2) 到達(dá)到達(dá)(s)點(diǎn)的點(diǎn)的b、c定值點(diǎn)均在循環(huán)外；定值點(diǎn)均在循環(huán)外； (3)到達(dá)到達(dá)(s)點(diǎn)的點(diǎn)的b、c定值點(diǎn)雖在循環(huán)內(nèi)，但只定值點(diǎn)雖在循環(huán)內(nèi)，但只有一個(gè)定值點(diǎn)且已被標(biāo)為循環(huán)不變運(yùn)算。有一個(gè)定值點(diǎn)且已被標(biāo)為循環(huán)不變運(yùn)算。則則(s)為循環(huán)不變運(yùn)算，為循環(huán)不變運(yùn)算，a、b、c為循環(huán)不變量。為循環(huán)不變量。注：循環(huán)不變量不論循環(huán)執(zhí)行多少次均始終保注：循環(huán)不變量不論循環(huán)執(zhí)行多少次均始終保持不變，有可能外提到循環(huán)外，以