1、第9章 代碼優(yōu)化,目錄,9.1 優(yōu)化技術(shù)簡(jiǎn)介 9.2 局部?jī)?yōu)化 9.3 控制流分析和循環(huán)優(yōu)化,9.1 優(yōu)化技術(shù)簡(jiǎn)介,一、代碼優(yōu)化的目的 提高目標(biāo)代碼的運(yùn)行效率。 注：效率是指目標(biāo)代碼運(yùn)行時(shí)間較短，占有空間較少。 二、代碼優(yōu)化的實(shí)質(zhì) 代碼優(yōu)化實(shí)際上是對(duì)代碼進(jìn)行等價(jià)變換，由一組代碼變成運(yùn)行結(jié)果相同的另一組代碼。,與機(jī)器無(wú)關(guān)的優(yōu)化-對(duì)中間代碼進(jìn)行； 依賴于機(jī)器的優(yōu)化-對(duì)目標(biāo)代碼進(jìn)行,三、優(yōu)化階段,四、優(yōu)化分類,根據(jù)優(yōu)化所涉及的程序范圍分成: (1)局部?jī)?yōu)化:(基本塊) (2)循環(huán)優(yōu)化:對(duì)循環(huán)中的代碼進(jìn)行優(yōu)化 (3)全局優(yōu)化:在整個(gè)程序范圍內(nèi)的優(yōu)化,五、常用優(yōu)化技術(shù)簡(jiǎn)介,1.刪除多余運(yùn)算 2.循環(huán)不變

2、代碼外提 3.強(qiáng)度削弱 4.變換循環(huán)控制條件 5.合并已知量與復(fù)寫傳播 6.刪除無(wú)用賦值,目的：提高目標(biāo)代碼速度。 例如： P:=0 for I:=1 to 20 do P:=P+AI*BI,1.刪除多余運(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),減少循環(huán)中代碼總數(shù)的重要辦法。 方法：把循環(huán)不變運(yùn)算，即其結(jié)果獨(dú)

3、立于循環(huán)執(zhí)行次數(shù)的表達(dá)式提到循環(huán)的前面，使之只在循環(huán)外計(jì)算一次。 例如： P:=0 for I:=1 to 20 do P:=P+AI*BI,2、代碼外提,(1)P:=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)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:=

4、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)度小的。例如： a) i*2 = 2*i = i+i = i1 b) i/2 = (int)(i*0.5) c) 0-1 = -1 d) f*2 = 2.0 * f = f + f e) f/2.0 = f*0.5,3.強(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:

5、=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)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+4,4、變換循環(huán)控制條件,如果在循環(huán)體內(nèi)存在一個(gè)變量T 與循環(huán)控制變量I保持線性關(guān)系，同時(shí)在循環(huán)后面不引用I，而除去I又不影響程序結(jié)果，則可以由T 取代的

6、控制循環(huán)次數(shù)的作用。從循環(huán)中刪除這這種方法稱為變換循環(huán)控制條件，或稱為刪除歸納變量。,(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 (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

7、 (9)T7:=T3*T6 (10)P:=P+T7 (3)T1:=T1+4,(12)if T1 =80 goto(5),5、合并已知量與復(fù)寫傳播,已知量就是指常數(shù)或在編譯時(shí)就能確定其值的變量。 若參加運(yùn)算的兩個(gè)對(duì)象在編譯時(shí)都是已知量，則可以在編譯時(shí)候直接計(jì)算出它們的運(yùn)算結(jié)果，不必等到程序運(yùn)行時(shí)再計(jì)算，這種變換稱為合并已知量或常數(shù)合并。 復(fù)寫傳播是指盡量不引用那些在程序中僅僅只傳遞信息而不改變其值，也不影響程序運(yùn)行結(jié)果的變量。 通過(guò)復(fù)制后沒(méi)有再改變的值可以互相替換，不會(huì)改變程序的結(jié)果。,(1)P:=0 (2)I:=1 (4)T2:=addr(A)-4 (7)T5:=addr(B)-4 (3) T

8、1:=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=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

9、)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ú)用賦值,局部?jī)?yōu)化：基本塊內(nèi)的優(yōu)化,9.2局部?jī)?yōu)化,一、基本塊 1、定義 程序中一個(gè)只有一個(gè)入口和一個(gè)出口的一段順序執(zhí)行的語(yǔ)句序

10、列，稱為程序的一個(gè)基本塊。 注：1)一個(gè)給定的程序，可以劃分為一系列的基本塊。優(yōu)化在各基本塊中分別進(jìn)行。 2)局部?jī)?yōu)化就是局限于基本塊范圍內(nèi)的優(yōu)化。 3)在運(yùn)行基本塊時(shí)，只能從其入口進(jìn)入，從出口退出。,a)求出各基本塊的入口語(yǔ)句 對(duì)四元式程序，各個(gè)基本塊的入口語(yǔ)句是： 1)程序的第一個(gè)語(yǔ)句 ；或 2)能由條件轉(zhuǎn)移語(yǔ)句和無(wú)條件轉(zhuǎn)移語(yǔ)句轉(zhuǎn)移到達(dá)的語(yǔ)句；或 3)緊跟在條件轉(zhuǎn)移語(yǔ)句后面的語(yǔ)句。 注：若條件語(yǔ)句由真轉(zhuǎn)移和假轉(zhuǎn)移兩條語(yǔ)句組成，則跟在轉(zhuǎn)移語(yǔ)句后面的語(yǔ)句是指假轉(zhuǎn)移語(yǔ)句后面的一條語(yǔ)句。,2、劃分基本塊算法,b)根據(jù)入口語(yǔ)句，構(gòu)造其所屬的基本塊 一入口語(yǔ)句所屬的基本塊是由該入口語(yǔ)句到: 下一入口語(yǔ)

11、句(不包括該入口語(yǔ)句); 或到一轉(zhuǎn)移語(yǔ)句(包括轉(zhuǎn)移語(yǔ)句); 或到一停(halt)語(yǔ)句(包括該語(yǔ)句) 之間的語(yǔ)句序列組成。 C)刪除不會(huì)被執(zhí)行的語(yǔ)句 凡是沒(méi)有納入到任何一個(gè)基本塊中的語(yǔ)句，都是程序控制流程所無(wú)法到達(dá)的語(yǔ)句，即不會(huì)被執(zhí)行到的語(yǔ)句，可將其刪除。,例：求最大公因子算法 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

12、:=X mod Y (7)X:=Y (8)Y:=T (9)goto (3) (10)write Y (11)halt,四元式序列：,基本塊的劃分：,主要是進(jìn)行已知量合并、刪除公共子表達(dá)式、刪除無(wú)用賦值。 注：僅在一個(gè)基本塊中，是否是無(wú)用賦值很難判斷。這是因?yàn)?，無(wú)用賦值有以下情形： (a)對(duì)某變量A賦值后，在程序中沒(méi)有引用； (b)對(duì)某變量A賦值后，在引用前又重新賦值； (c)對(duì)某變量A進(jìn)行自增賦值，且它僅僅被用在自增運(yùn)算中。 對(duì)上面第一和第三種情況，應(yīng)進(jìn)行全局分析。,3、塊內(nèi)優(yōu)化,1、DAG(有向無(wú)環(huán)圖)定義 a)父子結(jié)點(diǎn) 若在一有向圖中，結(jié)點(diǎn)ni有弧指向nj，則稱ni是nj的父結(jié)點(diǎn)， nj是

13、ni的子結(jié)點(diǎn)。 B)路徑與環(huán)路 若在一有向圖中，結(jié)點(diǎn)n1 n2 nk間存在有向弧n1n2 nk,則稱n1 到nk之間存在一條通路，若n1 nk則該路徑稱為環(huán)路； c)有向無(wú)環(huán)圖 若有向圖中任一路徑都不是環(huán)路，則稱該圖為無(wú)環(huán)路有向圖。,二、基本塊的DAG表示,a)葉結(jié)點(diǎn) 以一標(biāo)識(shí)符(變量名)或常數(shù)作為標(biāo)記。即，該結(jié)點(diǎn)代表該變量或常數(shù)的值。 注：1)若葉結(jié)點(diǎn)代表變量a的地址，則標(biāo)記為addr(a)。 2)通常把葉結(jié)點(diǎn)上作為標(biāo)記的標(biāo)識(shí)符加上下標(biāo)0，以表示它是該變量的初值。 b)內(nèi)部結(jié)點(diǎn) 以一運(yùn)算符作為標(biāo)記。即，該結(jié)點(diǎn)代表應(yīng)用該運(yùn)算符對(duì)其后繼結(jié)點(diǎn)所代表的值進(jìn)行運(yùn)算的結(jié)果。 c)附標(biāo)：圖中各個(gè)結(jié)點(diǎn)上可能

14、附加一個(gè)或多個(gè)標(biāo)識(shí)符，表示這些標(biāo)識(shí)符具有該結(jié)點(diǎn)所代表的值，這簡(jiǎn)稱附標(biāo)。,2、DAG結(jié)點(diǎn)標(biāo)記或附標(biāo),例如：A:=B op C 即四元式(op,B,C,A)的DAG圖為： 注：1)圖中的有向弧都省去箭頭。 2)結(jié)點(diǎn)ni是構(gòu)造DAG過(guò)程中給予各結(jié)點(diǎn)的編號(hào); 3)各結(jié)點(diǎn)下面的符號(hào)（運(yùn)算符、變量、常數(shù)）是各結(jié)點(diǎn)的標(biāo)記; 4)各結(jié)點(diǎn)右邊的標(biāo)識(shí)符是結(jié)點(diǎn)的附標(biāo)。,根據(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)為0型：,3、四元式的DAG結(jié)點(diǎn)類型,B)1型 A:=op B，即四元式(op,B,_,A)，其DAG結(jié)

15、點(diǎn)為1型：,C)2型 A:=B op C，即四元式(op,B,C,A)，其DAG結(jié)點(diǎn)為2型； A:=BC，即四元式(=,BC,_,A)，其DAG結(jié)點(diǎn)為2型； if B rop C goto (s)即四元式(jrop,B,C,(s)其DAG結(jié)點(diǎn)為2型,D)3型 DC:=B即四元式(=,B,_,DC)，其DAG結(jié)點(diǎn)為3型：,說(shuō)明：大寫字母（A、B）表示四元式中變量名； Node(A):表示A在DAG中的相應(yīng)結(jié)點(diǎn)，其值可以為n或無(wú)定義。N表示DAG中的一個(gè)結(jié)點(diǎn)值。 由基本塊構(gòu)造DAG的算法如下： 將元表和結(jié)點(diǎn)表置空。 對(duì)基本塊內(nèi)每個(gè)四元式(op,B,C,A)進(jìn)行如下操作： 1)查元表中有無(wú)結(jié)點(diǎn)B，有

16、則返回其序號(hào)，無(wú)則建立該結(jié)點(diǎn)并返回序號(hào)； 2)若四元式類型為0型，則不做任何操作；,4、基本塊的DAG構(gòu)造算法,3)若四元式類型為1型(即：A:=OP B)，則 IF node(B).標(biāo)記常量 THEN /*葉*/ 執(zhí)行OP B 得值P /*合并已知量*/ , 若node(B)是當(dāng)前四元式建立的，就刪去。 查有無(wú)node(P)結(jié)點(diǎn)，有就返回結(jié)點(diǎn)序號(hào)， 沒(méi)有就建立并返回其序號(hào) ELSE 查結(jié)點(diǎn)表是否有一結(jié)點(diǎn)，其后繼為node(B)，標(biāo) 記為OP，有就返回結(jié)點(diǎn)序號(hào)，沒(méi)有就建立并返回其序號(hào),4)若四元式類型為2型(即：A:=B OP C)，則， 查元表中有無(wú)結(jié)點(diǎn)node(C) ,有就返回結(jié)點(diǎn)序號(hào)，沒(méi)

17、有就建立并返回其序號(hào); IF ( node(B).標(biāo)記常量) AND (node(C).標(biāo)記常量 ) 執(zhí)行B OP C 得值P /*合并已知量*/ 若node(B), node(C)是當(dāng)前四元式建立的，就刪去; 查有無(wú)結(jié)點(diǎn)node(P) ,有就返回結(jié)點(diǎn)序號(hào)，沒(méi)有就建立并返回其序號(hào); ELSE 查結(jié)點(diǎn)表是否有一結(jié)點(diǎn)，其左后繼為node(B)且右后繼為node(C)，標(biāo)記為OP，有就返回結(jié)點(diǎn)序號(hào)，沒(méi)有就建立并返回其序號(hào)。;,5) 如果NODE（A）無(wú)定義，則把A附加在結(jié)點(diǎn)n上并令NODE（A）n；否則先把A從NODE（A）結(jié)點(diǎn)上的附加標(biāo)識(shí)符集中刪除（注意，如果NODE（A）是葉結(jié)點(diǎn)，則其標(biāo)記A不刪

18、除），把A附加到新結(jié)點(diǎn)n上并令NODE（A）n。轉(zhuǎn)處理下一四元式。,例如：下面程序用來(lái)求圓環(huán)內(nèi)外圓周之和及圓環(huán)正反兩面面積之和。對(duì)其優(yōu)化： Pi:=3.14 A:2*Pi*(R+r); B:=A; B:=2* Pi*(R+r)*(R-r) 由語(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)造DAG.,(1)T0:=3.14 (2)T1:=2* T0 (3)T2:

19、=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,(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,(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)T

20、6:=R-r (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*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,(1)T0:=3.14 (2)T1:=2* T0 (3)T2:=R+r (4)A:=T1*T

21、2 (5)B:=A (6)T3:=2* T0 (7)T4:=R+r (8)T5:=T3*T4 (9)T6:=R-r (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*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:=T

22、5*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,(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,1、可做到三種優(yōu)化 a)合并已知量 對(duì)任何一個(gè)四元式，若其中參與運(yùn)算的對(duì)象均是編譯時(shí)的已知量，則合并已知量，并用合并后算出

23、的常量生成一個(gè)葉結(jié)點(diǎn)。若參與運(yùn)算的已知量的葉結(jié)點(diǎn)是當(dāng)前四元式建立的結(jié)果，則可刪除。 b)刪除對(duì)變量的前一個(gè)賦值，即刪除該變量的前一個(gè)附標(biāo)。 c)檢查公共子表達(dá)式 對(duì)具有公共子表達(dá)式的所有四元式，只產(chǎn)生一個(gè)計(jì)算該表達(dá)式值的內(nèi)部結(jié)點(diǎn)，而將那些被賦值的變量附加到該結(jié)點(diǎn)。,三、DAG在基本塊優(yōu)化中的作用,2、利用DAG圖還原四元式序列 a)若為葉結(jié)點(diǎn)，無(wú)附標(biāo)，則不生成任何四元式； b)若為葉結(jié)點(diǎn)，標(biāo)記為B，附標(biāo)為A，則生成A:=B四元式；若有多個(gè)附標(biāo)，則生成值為B的相應(yīng)賦值語(yǔ)句四元式 c)若為中間結(jié)點(diǎn)，有附標(biāo)，則根據(jù)其標(biāo)記op，生成相應(yīng)四元式(如A:=B op C, A:=op B, A:=BC或if

24、 B rop C goto (s)；若有多個(gè)附標(biāo)，則除了第一個(gè)附標(biāo)用于生成相應(yīng)四元式，其它生成值為第一個(gè)附標(biāo)的賦值語(yǔ)句四元式 d)若中間結(jié)點(diǎn)無(wú)附標(biāo)，則添加一個(gè)臨時(shí)附標(biāo)SA， 然后轉(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,3、獲得其它優(yōu)化信息 a)在基本塊外定值并在基本塊內(nèi)被引用的所有標(biāo)識(shí)符，就是作為葉結(jié)點(diǎn)標(biāo)記的那些標(biāo)識(shí)符。 b)在基本塊內(nèi)被定值，且該值能在基本塊后面被引用的所有標(biāo)識(shí)符，就是DAG各結(jié)點(diǎn)上的那些附標(biāo)。

25、注：可利用上述信息，進(jìn)一步刪除四元式序列中其它情況的無(wú)用賦值，如，若某結(jié)點(diǎn)附標(biāo)，在該基本塊后面不會(huì)被引用，則不生成對(duì)該附標(biāo)賦值的四元式；若某結(jié)點(diǎn)無(wú)附標(biāo)或其附標(biāo)在基本塊后面不會(huì)被引用，且無(wú)父結(jié)點(diǎn)，則不生成計(jì)算該結(jié)點(diǎn)值的四元式；若兩個(gè)相鄰的四元式中的第一個(gè)四元式計(jì)算出來(lái)的值只在第二個(gè)四元式中被引用，則可合并這兩個(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:=R-r (9) B:=A*T6,S1:=R+r A:=6.28*s1 S2:=R-r B:=A*S

26、2,2020/9/14,51,一、控制流分析作用 1、是數(shù)據(jù)流程分析的基礎(chǔ) 2、找出程序中的循環(huán) 注：1)循環(huán)包括循環(huán)語(yǔ)句構(gòu)成的循環(huán)及條件轉(zhuǎn)移和無(wú)條件轉(zhuǎn)移構(gòu)成的循環(huán)。 2)為了找出程序中的循環(huán)，也需要進(jìn)行程序數(shù)據(jù)流程分析。,9.3 控制流分析和循環(huán)優(yōu)化,2020/9/14,52,1、程序流圖定義 以基本塊作為結(jié)點(diǎn)，控制程序流向作為有向弧，畫出的圖，稱為程序流圖。 注；1)程序流圖的特點(diǎn)是具有唯一首結(jié)點(diǎn)的有向圖。所謂首結(jié)點(diǎn)，是包含程序第一個(gè)語(yǔ)句的基本塊。 2)從首結(jié)點(diǎn)沿著流圖可到達(dá)任何結(jié)點(diǎn)。,二、程序流圖與必經(jīng)結(jié)點(diǎn)集,程序流圖三元式定義,有向邊集的構(gòu)成： 滿足下列條件之一時(shí)，結(jié)點(diǎn) I到結(jié)點(diǎn)j有有

27、向邊： 基本塊j在程序的位置緊跟在i后,且i的出口語(yǔ)句不是無(wú)條件轉(zhuǎn)移goto(S)或停語(yǔ)句 i的出口是goto(S)或if goto(S),而(S)是j的入口語(yǔ)句,(1) Read X (2) Read Y,(3) T1:=X mod Y (4) If T1=0 goto (8),(5)X:=Y (6)Y:=T1 (7)goto (3),(8)write Y (9)halt,B1,B2,B3,B4,程序流圖,分析程序流圖中結(jié)點(diǎn)間的關(guān)系 （1）m DOM n 定義 在程序流圖中,對(duì)任意兩個(gè)結(jié)點(diǎn)m和n,如果從流圖的首結(jié)點(diǎn)出發(fā),到達(dá)n的任意通路都要經(jīng)過(guò)m,則稱m是n的必經(jīng)結(jié)點(diǎn),記為m DOM n (

28、a,a DOM a) （2）必經(jīng)結(jié)點(diǎn)集 定義 結(jié)點(diǎn)n的所有必經(jīng)結(jié)點(diǎn)的集合,稱為結(jié)點(diǎn)n的必經(jīng)結(jié)點(diǎn)集,記為D(n).,2、必經(jīng)結(jié)點(diǎn)集定義,各結(jié)點(diǎ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,（3）必經(jīng)結(jié)點(diǎn)DOM的性質(zhì),自反性： a,a DOM a 傳遞性：對(duì)流圖中的任意結(jié)點(diǎn)a,b和c， 若a DOM b, b DOM c, 則有a DOM c。 反對(duì)稱性：若a DOM b且 b DOM a，則有a=b.,DOM關(guān)系是一個(gè)偏序關(guān)系。,2020/9/14,59,1、基本思想 根

29、據(jù)一個(gè)結(jié)點(diǎn)的所有父結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)集，求出該結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)集。 若設(shè)結(jié)點(diǎn)n的父結(jié)點(diǎn)是P1,P2,Pk，則D(n)=(D(P1)D(P2) D(Pk)n 2、具體實(shí)現(xiàn)方式 使用迭代方法：比較相鄰兩次迭代結(jié)果，若相同，則結(jié)束。,三、求必經(jīng)結(jié)點(diǎn)集算法,3、算法 設(shè)全部結(jié)點(diǎn)集合為N，首結(jié)點(diǎn)為n0， D(n0)=n0; for nN-N0 do D(n):=N; /*置初值*/ change=TRUE; while change /*完成若干迭代*/ change=FALSE; for n N-N0 do /*完成一次迭代*/ newd= (D(P1)D(P2) D(Pk)n; if D(n)newd c

30、hange=TRUE; D(n):=NEWD ,注：此算法中沒(méi)有規(guī)定計(jì)算結(jié)點(diǎn)的順序，若順序選的不好，效率可能很低。所以使用算法之前先將流圖中各結(jié)點(diǎn)排序，此序?yàn)樯疃葹橹髋判颉?2020/9/14,62,1、基本思想 利用必經(jīng)結(jié)點(diǎn)集求出流圖中的回邊，利用回邊找出流圖中的循環(huán)。 2、回邊定義 設(shè)ab是流圖中一條有向邊，若b dom a ，則ab是流圖中一條回邊。 注：1)可應(yīng)用必經(jīng)結(jié)點(diǎn)集求出流圖中的回邊。 2) 設(shè)nd是回邊，則該回邊構(gòu)成的循環(huán)包括如下結(jié)點(diǎn)：n、d以及不經(jīng)過(guò)d能到達(dá)n的所有結(jié)點(diǎn)。,四、查找循環(huán)算法,例：求出下圖的所有回邊,D(1)=1 D(2)=1,2 D(3)=1,2,3 D(4)

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

32、通，而且只有唯一入口點(diǎn)。 注： 1)強(qiáng)連通是指循環(huán)中任意兩個(gè)結(jié)點(diǎn)都有通路，單結(jié)點(diǎn)循環(huán)也有一弧指向自身。它保證了循環(huán)內(nèi)各結(jié)點(diǎn)的代碼都可反復(fù)執(zhí)行。 2)唯一入口點(diǎn)是指要到達(dá)循環(huán)內(nèi)任意結(jié)點(diǎn)必須經(jīng)過(guò)此入口點(diǎn)。它保證了循環(huán)優(yōu)化時(shí)，可將代碼外提到唯一入口點(diǎn)前的前置結(jié)點(diǎn)中。,2020/9/14,67,五、可歸約流圖,當(dāng)且僅當(dāng)流圖中除去回邊外，其余的邊構(gòu)成一個(gè)無(wú)環(huán)路回路，就稱流圖為可歸約流圖。 左圖為可歸約流圖。,5,4,7,6,2,1,3,2020/9/14,68,循環(huán)優(yōu)化：三種重要技術(shù) 代碼外提：產(chǎn)生的結(jié)果獨(dú)立于循環(huán)執(zhí)行次數(shù)的表達(dá)式，放到循環(huán)前面。 強(qiáng)度削弱：把程序中執(zhí)行時(shí)間較長(zhǎng)的運(yùn)算替換為時(shí)間較短的運(yùn)算。 刪除歸納變量： 對(duì)形如I:=I+C的賦值 C為循環(huán)不變量，稱I為基本歸納變量。 對(duì)形如J:=C1*I+C2,的賦值稱J為歸納變量,六、 循環(huán)優(yōu)化,（一）、代碼外提 1、循環(huán)不變量定義 形如(s)