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

1、第第10章章 代碼優(yōu)化代碼優(yōu)化1代碼優(yōu)化的目標(biāo)代碼優(yōu)化的目標(biāo)減少目標(biāo)程序所占用的存儲(chǔ)空間；減少目標(biāo)程序所占用的存儲(chǔ)空間；( (空間少空間少) )提高目標(biāo)程序的運(yùn)行速度。提高目標(biāo)程序的運(yùn)行速度。( (時(shí)間短時(shí)間短) ) 優(yōu)化優(yōu)化可以在編譯的不同階段進(jìn)行可以在編譯的不同階段進(jìn)行，通常，通常優(yōu)化可以再中間代碼和目標(biāo)代碼生成之后進(jìn)優(yōu)化可以再中間代碼和目標(biāo)代碼生成之后進(jìn)行。本章行。本章討論的是對(duì)中間代碼進(jìn)行等價(jià)變換。討論的是對(duì)中間代碼進(jìn)行等價(jià)變換。2 根據(jù)優(yōu)化所涉及的程序范圍，中間代碼根據(jù)優(yōu)化所涉及的程序范圍，中間代碼優(yōu)化分為三類：優(yōu)化分為三類：代碼優(yōu)化的分類代碼優(yōu)化的分類 對(duì)對(duì)一段一段順順序序語(yǔ)句序列

2、語(yǔ)句序列優(yōu)化。優(yōu)化。 對(duì)中對(duì)中循環(huán)循環(huán)的的代碼序列優(yōu)化。代碼序列優(yōu)化。 在在整個(gè)整個(gè)程序程序范圍內(nèi)進(jìn)行的范圍內(nèi)進(jìn)行的優(yōu)化。優(yōu)化。局部?jī)?yōu)化局部?jī)?yōu)化循環(huán)優(yōu)化循環(huán)優(yōu)化全局優(yōu)化全局優(yōu)化310.1 基本塊基本塊與程序控制與程序控制流圖流圖4一、基本一、基本塊塊基本塊：是指程序中一順序執(zhí)行的語(yǔ)句序列，基本塊：是指程序中一順序執(zhí)行的語(yǔ)句序列，其中其中只有只有一個(gè)入口語(yǔ)句一個(gè)入口語(yǔ)句( (第一個(gè)語(yǔ)句第一個(gè)語(yǔ)句) )和一個(gè)和一個(gè)出口語(yǔ)句出口語(yǔ)句( (最后一個(gè)語(yǔ)句最后一個(gè)語(yǔ)句) )。 對(duì)于對(duì)于一個(gè)基本塊來(lái)說(shuō)，執(zhí)行時(shí)只能從其一個(gè)基本塊來(lái)說(shuō)，執(zhí)行時(shí)只能從其入口語(yǔ)句進(jìn)入，從其出口語(yǔ)句退出。入口語(yǔ)句進(jìn)入，從其出口語(yǔ)句退出

3、。5 根據(jù)基本塊的定義，它是一個(gè)按順序執(zhí)根據(jù)基本塊的定義，它是一個(gè)按順序執(zhí)行的代碼序列，而且只能從它的唯一入口進(jìn)行的代碼序列，而且只能從它的唯一入口進(jìn)入，從其唯一的出口退出，期間不發(fā)生任何入，從其唯一的出口退出，期間不發(fā)生任何分叉。分叉。任何控制轉(zhuǎn)移四元式任何控制轉(zhuǎn)移四元式出口語(yǔ)句出口語(yǔ)句所轉(zhuǎn)向的目標(biāo)語(yǔ)句所轉(zhuǎn)向的目標(biāo)語(yǔ)句入口語(yǔ)句入口語(yǔ)句6 1. 程序的第一個(gè)語(yǔ)句；程序的第一個(gè)語(yǔ)句；或者或者， 2. 條件轉(zhuǎn)移語(yǔ)句或無(wú)條件轉(zhuǎn)移語(yǔ)句的轉(zhuǎn)條件轉(zhuǎn)移語(yǔ)句或無(wú)條件轉(zhuǎn)移語(yǔ)句的轉(zhuǎn) 移目標(biāo)語(yǔ)句；移目標(biāo)語(yǔ)句；或者或者 3. 緊跟在條件轉(zhuǎn)移語(yǔ)句后面的語(yǔ)句。緊跟在條件轉(zhuǎn)移語(yǔ)句后面的語(yǔ)句。入口語(yǔ)句入口語(yǔ)句7劃分基本塊的步

4、驟劃分基本塊的步驟1、求四元式序列中各個(gè)基本塊的、求四元式序列中各個(gè)基本塊的入口語(yǔ)句入口語(yǔ)句。2、對(duì)每一入口語(yǔ)句，構(gòu)造所屬的基本塊，該基本塊、對(duì)每一入口語(yǔ)句，構(gòu)造所屬的基本塊，該基本塊由：由：（1）該入口語(yǔ)句到下一入口語(yǔ)句（）該入口語(yǔ)句到下一入口語(yǔ)句（不包括不包括下一入口下一入口語(yǔ)句）之間的語(yǔ)句序列組成；或，語(yǔ)句）之間的語(yǔ)句序列組成；或，（2）該入口語(yǔ)句到一轉(zhuǎn)移語(yǔ)句（）該入口語(yǔ)句到一轉(zhuǎn)移語(yǔ)句（包括包括該轉(zhuǎn)移語(yǔ)句）該轉(zhuǎn)移語(yǔ)句）之間的語(yǔ)句序列組成；或，之間的語(yǔ)句序列組成；或，（3）該入口語(yǔ)句到一停語(yǔ)句（）該入口語(yǔ)句到一停語(yǔ)句（包括包括該停語(yǔ)句）之間該停語(yǔ)句）之間的語(yǔ)句序列組成。的語(yǔ)句序列組成。3、

5、凡是未包含在某一基本塊中的語(yǔ)句，都是程序中、凡是未包含在某一基本塊中的語(yǔ)句，都是程序中控制流程不可達(dá)的語(yǔ)句，可刪除它們?？刂屏鞒滩豢蛇_(dá)的語(yǔ)句，可刪除它們。8例子例子 (1) read a (2) read b (3) r:=a mod b (4) if r=0 goto (8) (5) a:= b (6) b:= r (7) goto (3) (8) write b (9) haltB1B2B3B49二、程序控制二、程序控制流程圖（流圖）流程圖（流圖）定義：以基本塊為結(jié)點(diǎn)，控制程序流向定義：以基本塊為結(jié)點(diǎn)，控制程序流向作作 為有向邊，畫出的有向圖稱為流圖。為有向邊，畫出的有向圖稱為流圖。特點(diǎn)：

6、特點(diǎn)： 具有具有唯一唯一首結(jié)點(diǎn)的首結(jié)點(diǎn)的有向圖；有向圖； 從首結(jié)點(diǎn)開始到流圖中任何結(jié)點(diǎn)都有通路。從首結(jié)點(diǎn)開始到流圖中任何結(jié)點(diǎn)都有通路。 如果如果一個(gè)結(jié)點(diǎn)的基本塊的入口語(yǔ)句是程一個(gè)結(jié)點(diǎn)的基本塊的入口語(yǔ)句是程序的第一條語(yǔ)句，則稱此結(jié)點(diǎn)為首結(jié)點(diǎn)。序的第一條語(yǔ)句，則稱此結(jié)點(diǎn)為首結(jié)點(diǎn)。10一個(gè)控制流程圖可表示成一個(gè)一個(gè)控制流程圖可表示成一個(gè)三元組：三元組：G=(N，E，n0)N：所有結(jié)點(diǎn)：所有結(jié)點(diǎn)(基本塊基本塊)集；集；E：所有有向邊集；：所有有向邊集；n0 ：首結(jié)點(diǎn)。：首結(jié)點(diǎn)。11有向邊有向邊 當(dāng)下述條件有一個(gè)成立時(shí)，從結(jié)點(diǎn)當(dāng)下述條件有一個(gè)成立時(shí)，從結(jié)點(diǎn)i有有一有向邊引向結(jié)點(diǎn)一有向邊引向結(jié)點(diǎn)j： 基本

7、基本塊塊j在程序的位置緊跟在在程序的位置緊跟在i后，且后，且i的出的出口語(yǔ)句不是口語(yǔ)句不是無(wú)條件無(wú)條件轉(zhuǎn)移或停語(yǔ)句；轉(zhuǎn)移或停語(yǔ)句； i的出口是的出口是goto(S)或或if goto(S)，而，而(S)是是j的的入口語(yǔ)句。入口語(yǔ)句。 i j12例子：構(gòu)造例子：構(gòu)造以下程序的流圖以下程序的流圖B1B2B4B313B1B2B3B4 (1) read a (2) read b (3) r:=a mod b (4) if r=0 goto (8) (5) a:= b (6) b:= r (7) goto (3) (8) write b (9) halt10.2 局部?jī)?yōu)化局部?jī)?yōu)化14局部?jī)?yōu)化是指基本塊內(nèi)

8、的優(yōu)化。局部?jī)?yōu)化是指基本塊內(nèi)的優(yōu)化。對(duì)于一個(gè)給定的程序，可以把它劃分為一系對(duì)于一個(gè)給定的程序，可以把它劃分為一系列的基本塊。在各個(gè)基本塊內(nèi)列的基本塊。在各個(gè)基本塊內(nèi)分別分別進(jìn)行優(yōu)化。進(jìn)行優(yōu)化。15一、局部?jī)?yōu)化種類一、局部?jī)?yōu)化種類16 在一個(gè)基本塊內(nèi)，可以進(jìn)行合并已知量、在一個(gè)基本塊內(nèi)，可以進(jìn)行合并已知量、刪除公共子表達(dá)式和刪除無(wú)用賦值三種優(yōu)化刪除公共子表達(dá)式和刪除無(wú)用賦值三種優(yōu)化措施。措施。 合并已知量是合并已知量是指在編譯時(shí)就對(duì)指在編譯時(shí)就對(duì)表達(dá)式中能計(jì)算表達(dá)式中能計(jì)算的部分先計(jì)算，的部分先計(jì)算，并用該值替換這并用該值替換這部分表達(dá)式，而部分表達(dá)式，而不必生成相應(yīng)的不必生成相應(yīng)的代碼。代碼。

9、 刪除公共子表刪除公共子表達(dá)式就是使基本達(dá)式就是使基本塊內(nèi)相同的子表塊內(nèi)相同的子表達(dá)式只計(jì)算一次，達(dá)式只計(jì)算一次，把重復(fù)計(jì)算的表把重復(fù)計(jì)算的表達(dá)式刪去，從而達(dá)式刪去，從而避免多余的運(yùn)算。避免多余的運(yùn)算。 變量變量A被定值被定值后不再被引用或后不再被引用或未經(jīng)引用又發(fā)生未經(jīng)引用又發(fā)生了對(duì)了對(duì)A的第二次的第二次定值，則前一定定值，則前一定值為無(wú)用賦值，值為無(wú)用賦值，應(yīng)刪掉。應(yīng)刪掉。二、基本二、基本塊的塊的DAG表示表示DAG Directed Acyclic Graph 無(wú)環(huán)路有向圖無(wú)環(huán)路有向圖定義：定義：(1)在一個(gè)有向圖中，若結(jié)點(diǎn)在一個(gè)有向圖中，若結(jié)點(diǎn)ni有弧指向結(jié)點(diǎn)有弧指向結(jié)點(diǎn)nj，則則ni

10、是是nj的的父結(jié)點(diǎn)父結(jié)點(diǎn)，nj是是ni的的子結(jié)點(diǎn)子結(jié)點(diǎn)；(2)若若n1,n2,nk間存在有向弧間存在有向弧n1n2nk，則稱則稱n1到到nk之間存在一條之間存在一條通路通路，若，若n1=nk，則，則稱該通路為稱該通路為環(huán)路環(huán)路；(3)若有向圖中任意通路都不是環(huán)路，則稱該圖若有向圖中任意通路都不是環(huán)路，則稱該圖為為無(wú)環(huán)路有向圖無(wú)環(huán)路有向圖（DAG）。）。17基本塊的基本塊的DAG表示表示優(yōu)化中用到的有向圖是一種結(jié)點(diǎn)帶有下述標(biāo)優(yōu)化中用到的有向圖是一種結(jié)點(diǎn)帶有下述標(biāo)記或附加信息的記或附加信息的DGA:(1) 圖圖的葉結(jié)點(diǎn)以一標(biāo)識(shí)符或常數(shù)做標(biāo)記，的葉結(jié)點(diǎn)以一標(biāo)識(shí)符或常數(shù)做標(biāo)記，表示該結(jié)點(diǎn)代表該變量或常

11、數(shù)的值。表示該結(jié)點(diǎn)代表該變量或常數(shù)的值。(2) 圖圖的內(nèi)部結(jié)點(diǎn)以一運(yùn)算符作為標(biāo)記；的內(nèi)部結(jié)點(diǎn)以一運(yùn)算符作為標(biāo)記；(3) 圖圖中各個(gè)結(jié)點(diǎn)上可能附加一個(gè)或多個(gè)標(biāo)中各個(gè)結(jié)點(diǎn)上可能附加一個(gè)或多個(gè)標(biāo)識(shí)符，表示這些標(biāo)識(shí)符具有該結(jié)點(diǎn)所代表識(shí)符，表示這些標(biāo)識(shí)符具有該結(jié)點(diǎn)所代表的值，簡(jiǎn)稱附標(biāo)。的值，簡(jiǎn)稱附標(biāo)。18四元式對(duì)應(yīng)的四元式對(duì)應(yīng)的DAG結(jié)點(diǎn)形式結(jié)點(diǎn)形式按其四元式對(duì)應(yīng)結(jié)點(diǎn)的后繼個(gè)數(shù)分成四種類按其四元式對(duì)應(yīng)結(jié)點(diǎn)的后繼個(gè)數(shù)分成四種類型：型：0型、型、1型、型、2型、型、3型。型。0型型：1型：型：2型：型：19例子：構(gòu)造例子：構(gòu)造以下基本塊的以下基本塊的DAG20(1) T0:=3.14(2) T1:=2*T0

12、(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三、用三、用DAG實(shí)現(xiàn)基本塊優(yōu)化實(shí)現(xiàn)基本塊優(yōu)化DAG圖可做到如下三種優(yōu)化：圖可做到如下三種優(yōu)化：(1) 合并已知量合并已知量 對(duì)任何一個(gè)四元式，如果其中參與運(yùn)對(duì)任何一個(gè)四元式，如果其中參與運(yùn)算的對(duì)象都是編譯時(shí)的已知量，那么合并算的對(duì)象都是編譯時(shí)的已知量，那么合并已知量，并用合并后算出的常量生成一個(gè)已知量，并用合并后算出的常量生成一個(gè)葉結(jié)點(diǎn)；葉結(jié)點(diǎn)；21(2) 利用公共子表達(dá)式，刪除多余運(yùn)算利用公共子表達(dá)式，刪除多余

13、運(yùn)算 對(duì)具有公共子表達(dá)式的所有四元式，只對(duì)具有公共子表達(dá)式的所有四元式，只產(chǎn)生一個(gè)計(jì)算該表達(dá)式值的內(nèi)部節(jié)點(diǎn)，把那產(chǎn)生一個(gè)計(jì)算該表達(dá)式值的內(nèi)部節(jié)點(diǎn)，把那些賦值的變量附加到該節(jié)點(diǎn)上。些賦值的變量附加到該節(jié)點(diǎn)上。22(3) 刪除無(wú)用賦值刪除無(wú)用賦值 如果如果某變量被賦值之后，隨后又被賦新某變量被賦值之后，隨后又被賦新值，那么可刪除對(duì)變量的前一個(gè)賦值。值，那么可刪除對(duì)變量的前一個(gè)賦值。23n8n8n6n6n7n7n5n5n3n3n1n1n2n2n4n43.14T06.28T1,T3Rr+-T6T2,T4A,T5*B(1) T0:=3.14(2) T1:=6.28(3) T3:=6.28(4) T2:=

14、R+r(5) T4:=T2(6) A:=6.28*T2(7) T5:=A(8) T6:=R-r(9) B:=A*T6由由DAG生成優(yōu)化后的代碼序列生成優(yōu)化后的代碼序列24注意事項(xiàng)注意事項(xiàng) 若若結(jié)點(diǎn)有多個(gè)附標(biāo)結(jié)點(diǎn)有多個(gè)附標(biāo)A1，A2，An， 有兩種情況：有兩種情況： (1) 若若結(jié)點(diǎn)是葉結(jié)點(diǎn)，標(biāo)記為結(jié)點(diǎn)是葉結(jié)點(diǎn)，標(biāo)記為B，則，則A1:=B，A2:=B，An:=B； (2) 若若為內(nèi)部結(jié)點(diǎn)，則除第一附標(biāo)為內(nèi)部結(jié)點(diǎn)，則除第一附標(biāo)A1外，其外，其他附標(biāo)生成他附標(biāo)生成A2:=A1，A3:=A1，An:=A1。 25DAG在基本塊優(yōu)化中的作用在基本塊優(yōu)化中的作用 將一基本塊的每一個(gè)四元式依次表示成對(duì)應(yīng)將一

15、基本塊的每一個(gè)四元式依次表示成對(duì)應(yīng)的一個(gè)的一個(gè)DAG，再按原來(lái)構(gòu)造，再按原來(lái)構(gòu)造DAG結(jié)點(diǎn)的順結(jié)點(diǎn)的順序重寫四元式序列，便可得到序重寫四元式序列，便可得到“合并已知常合并已知常量量”、“刪除無(wú)用賦值刪除無(wú)用賦值”、“刪除多余運(yùn)算刪除多余運(yùn)算”后的等價(jià)基本塊。后的等價(jià)基本塊。對(duì)于出了基本塊以后不再引用的名字，可以對(duì)于出了基本塊以后不再引用的名字，可以不生成對(duì)其進(jìn)行的賦值運(yùn)算，而用臨時(shí)變量不生成對(duì)其進(jìn)行的賦值運(yùn)算，而用臨時(shí)變量存放相應(yīng)的運(yùn)算結(jié)果。存放相應(yīng)的運(yùn)算結(jié)果。26例：試對(duì)基本塊例：試對(duì)基本塊P (1)應(yīng)用應(yīng)用DAG進(jìn)行優(yōu)化，進(jìn)行優(yōu)化， (2) 假定只有假定只有R、H在基本塊出口是活躍的在基本

16、塊出口是活躍的,寫出優(yōu)化后的四元式序列。寫出優(yōu)化后的四元式序列。27S0:=2S1:=3/S0S2:=T - CS3:=T + CR:=S0/S3H:=RS4:=3/S1S5:=T + CS6:=S4/S5H:=S6*S2 S0 2n0 S1 1.5n1-n4S2T Cn2n3S3n5+ R/n6, H ,S4,S5, S6 H*n728S0:=2S4:=2S1:=1.5S2:=T - CS3:=T + CS5:=S3R:=2/S3S6:=RH:=R*S229(1) 應(yīng)用應(yīng)用DAG進(jìn)行優(yōu)化進(jìn)行優(yōu)化S0:=2S4:=2S1:=1.5S2:=T - CS3:=T + CS5:=S3R:=2/S3S

17、6:=RH:=R*S2S2:=T - CS3:=T + CR:=2/S3H:=R*S2(2) 假定假定只有只有R、H在基本塊出口是活躍在基本塊出口是活躍的的3010.3 循環(huán)循環(huán)優(yōu)化優(yōu)化31循環(huán)就是程序中那些可能反復(fù)執(zhí)行的代碼序循環(huán)就是程序中那些可能反復(fù)執(zhí)行的代碼序列。因?yàn)檠h(huán)中的代碼要反復(fù)執(zhí)行，所以必列。因?yàn)檠h(huán)中的代碼要反復(fù)執(zhí)行，所以必須著重考慮循環(huán)的代碼優(yōu)化。須著重考慮循環(huán)的代碼優(yōu)化。首先要找出程序中的循環(huán)，這就需要對(duì)程序首先要找出程序中的循環(huán)，這就需要對(duì)程序的控制流程進(jìn)行分析。的控制流程進(jìn)行分析。使用使用控制流程圖控制流程圖對(duì)循環(huán)給出定義。對(duì)循環(huán)給出定義。32一、循環(huán)一、循環(huán)的性質(zhì)的性

18、質(zhì) 在程序流圖中，稱具有下列性質(zhì)的在程序流圖中，稱具有下列性質(zhì)的結(jié)點(diǎn)序列結(jié)點(diǎn)序列為一個(gè)循環(huán)：為一個(gè)循環(huán)： 1. 它們是它們是強(qiáng)連通強(qiáng)連通的。的。 2. 它們中間它們中間有且只有有且只有一個(gè)是一個(gè)是入口結(jié)點(diǎn)入口結(jié)點(diǎn)。33強(qiáng)連通強(qiáng)連通一組結(jié)點(diǎn)是強(qiáng)連通的，即：一組結(jié)點(diǎn)是強(qiáng)連通的，即：l 其中任意兩個(gè)結(jié)點(diǎn)之間，必有一條通路，其中任意兩個(gè)結(jié)點(diǎn)之間，必有一條通路，使得它們之間使得它們之間相互可達(dá)相互可達(dá)；l 該通路上各結(jié)點(diǎn)都屬于該結(jié)點(diǎn)序列。該通路上各結(jié)點(diǎn)都屬于該結(jié)點(diǎn)序列。34注意：如果序列中只有一個(gè)結(jié)點(diǎn)，則必有一注意：如果序列中只有一個(gè)結(jié)點(diǎn)，則必有一有向邊從該結(jié)點(diǎn)引到其自身。有向邊從該結(jié)點(diǎn)引到其自身。入口

19、結(jié)點(diǎn)入口結(jié)點(diǎn) 所謂入口結(jié)點(diǎn)，是指序列中具有下述性所謂入口結(jié)點(diǎn)，是指序列中具有下述性質(zhì)的結(jié)點(diǎn)：質(zhì)的結(jié)點(diǎn)： 從序列外某結(jié)點(diǎn)，有一有向邊引到它，從序列外某結(jié)點(diǎn)，有一有向邊引到它，或者或者它就是程序流圖的首結(jié)點(diǎn)。它就是程序流圖的首結(jié)點(diǎn)。35定義：在程序流圖中具有定義：在程序流圖中具有唯一入口結(jié)點(diǎn)的強(qiáng)連通子唯一入口結(jié)點(diǎn)的強(qiáng)連通子圖。圖。 二、循環(huán)二、循環(huán)的定義的定義36注意：從循環(huán)外要進(jìn)入注意：從循環(huán)外要進(jìn)入循環(huán)，必須首先經(jīng)過循循環(huán)，必須首先經(jīng)過循環(huán)的入口結(jié)點(diǎn)。環(huán)的入口結(jié)點(diǎn)。1243657三、循環(huán)三、循環(huán)的查找的查找 上面給出了構(gòu)成循環(huán)應(yīng)具備的條件，為上面給出了構(gòu)成循環(huán)應(yīng)具備的條件，為了找到程序流圖中的

20、循環(huán)，需要分析流圖中了找到程序流圖中的循環(huán)，需要分析流圖中結(jié)點(diǎn)間的控制關(guān)系。結(jié)點(diǎn)間的控制關(guān)系。 為此引入為此引入必經(jīng)結(jié)點(diǎn)必經(jīng)結(jié)點(diǎn)和和必經(jīng)結(jié)點(diǎn)集必經(jīng)結(jié)點(diǎn)集的定義。的定義。37v必經(jīng)結(jié)點(diǎn)：對(duì)任意兩個(gè)結(jié)點(diǎn)必經(jīng)結(jié)點(diǎn)：對(duì)任意兩個(gè)結(jié)點(diǎn)d和和n，若從首結(jié)，若從首結(jié)點(diǎn)出發(fā)，到達(dá)點(diǎn)出發(fā)，到達(dá)n的各條通路都必須經(jīng)過的結(jié)的各條通路都必須經(jīng)過的結(jié)點(diǎn)點(diǎn)d，稱，稱d為為n的必經(jīng)結(jié)點(diǎn)，記作的必經(jīng)結(jié)點(diǎn)，記作 d DOM n。v必經(jīng)結(jié)點(diǎn)集：必經(jīng)結(jié)點(diǎn)集：n的全部必經(jīng)結(jié)點(diǎn)的集合，記的全部必經(jīng)結(jié)點(diǎn)的集合，記作作D(n)。38 設(shè)設(shè)結(jié)點(diǎn)結(jié)點(diǎn)n的父結(jié)點(diǎn)的父結(jié)點(diǎn)是是P1，P2，Pk，則：，則：D(n)= n ( D(Pi) 1ik求必經(jīng)結(jié)

21、點(diǎn)集的算法求必經(jīng)結(jié)點(diǎn)集的算法39舉例舉例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,7401243657循環(huán)的查找循環(huán)的查找 回邊回邊回邊：設(shè)回邊：設(shè)ab是流圖中一條是流圖中一條有向邊，若有向邊，若b dom a，則稱，則稱ab時(shí)流圖中的一條回邊。時(shí)流圖中的一條回邊。411243657圖中的回邊有：圖中的回邊有：66，74，42查找循環(huán)算法查找循環(huán)算法每一條回邊構(gòu)成一個(gè)循環(huán)：每一條回邊構(gòu)成一個(gè)循環(huán)： 設(shè)設(shè)nd是回邊，則該回邊構(gòu)成的循環(huán)是回邊，則該回邊構(gòu)成的循環(huán)包括下列結(jié)點(diǎn)包括下列結(jié)點(diǎn)： n、d以及不經(jīng)

22、過以及不經(jīng)過d能到達(dá)能到達(dá)n的所有結(jié)點(diǎn)。的所有結(jié)點(diǎn)。42431243657回邊回邊42循環(huán)循環(huán)=4 , 2 , 3 , 7 , 5 , 6回邊回邊74循環(huán)循環(huán)=7，4，5，6回邊回邊66循環(huán)循環(huán)=6查找循環(huán)算法查找循環(huán)算法(1)找出回邊找出回邊nd；(2)則則n、d必定屬于必定屬于nd回邊組成的循環(huán)回邊組成的循環(huán)L中中， L:=n,d(3)若若n d且且n的父節(jié)點(diǎn)的父節(jié)點(diǎn)n不在不在L中，則將中，則將它添它添 加加L中，中，L:=L n(4)對(duì)對(duì)(3)求出的父節(jié)點(diǎn)求出的父節(jié)點(diǎn)n重復(fù)重復(fù)(3)，直至不再，直至不再有有 新新節(jié)點(diǎn)加入為止。節(jié)點(diǎn)加入為止。44四、循環(huán)四、循環(huán)優(yōu)化優(yōu)化在找出了程序流圖中的

23、循環(huán)之后，就可以針在找出了程序流圖中的循環(huán)之后，就可以針對(duì)每個(gè)循環(huán)進(jìn)行優(yōu)化工作。對(duì)每個(gè)循環(huán)進(jìn)行優(yōu)化工作。循環(huán)優(yōu)化的三種重要技術(shù)：循環(huán)優(yōu)化的三種重要技術(shù)： 1. 代碼外提代碼外提 2. 刪除歸納變量刪除歸納變量 3. 強(qiáng)度削弱強(qiáng)度削弱45用例子初步理解優(yōu)化措施用例子初步理解優(yōu)化措施P:=0for I:=1 to 20 do P:=P+AI*BI461.刪除多余刪除多余運(yùn)算運(yùn)算 (刪除公共子表達(dá)式刪除公共子表達(dá)式) 對(duì)于兩個(gè)相同的表對(duì)于兩個(gè)相同的表達(dá)式計(jì)算，若它的達(dá)式計(jì)算，若它的計(jì)算結(jié)果相同，則計(jì)算結(jié)果相同，則沒必要重復(fù)的生成沒必要重復(fù)的生成兩條運(yùn)算指令。兩條運(yùn)算指令。(1) P:=0(2) I:

24、=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)T4:=T1472.代碼外提代碼外提 把結(jié)果獨(dú)立于循環(huán)把結(jié)果獨(dú)立于循環(huán)執(zhí)行次數(shù)的表達(dá)式執(zhí)行次數(shù)的表達(dá)式提到循環(huán)的前面。提到循環(huán)的前面。(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

25、(3)(4)T2:=addr(A)-4(7)T5:=addr(B)-4(6)T4:=T1483.強(qiáng)度削弱強(qiáng)度削弱 把強(qiáng)度大的運(yùn)算換把強(qiáng)度大的運(yùn)算換算成強(qiáng)度小的運(yùn)算。算成強(qiáng)度小的運(yùn)算。如把乘法換算成加如把乘法換算成加法。法。(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+449(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=

26、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(5)T3:=T2T1(6)T4:=T1(8)T6:=T5 (9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3)T1:=T1+4(12)if goto(5)(3)T1:=4T1T1 =80 4.變換循環(huán)控制條件變換循環(huán)控制條件 5.合并已知量與復(fù)寫傳播合并已知量

27、與復(fù)寫傳播506.刪除無(wú)用賦值刪除無(wú)用賦值(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(11)I:=I+1(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)51循環(huán)優(yōu)化

28、的一些基本概念循環(huán)優(yōu)化的一些基本概念點(diǎn)：程序中某一個(gè)四元式的位置點(diǎn)：程序中某一個(gè)四元式的位置；定值點(diǎn)：對(duì)某變量賦值或輸入值的四元式位定值點(diǎn)：對(duì)某變量賦值或輸入值的四元式位置置；引用點(diǎn)：引用某變量的四元式位置引用點(diǎn)：引用某變量的四元式位置；5253變量變量A的到達(dá)與定值：的到達(dá)與定值：d是是A的定值點(diǎn)，的定值點(diǎn)，u是是A的引用點(diǎn)，存在一條從的引用點(diǎn)，存在一條從d到到u的通路，并此路的通路，并此路上沒有上沒有A的其他定值點(diǎn)，稱的其他定值點(diǎn)，稱d點(diǎn)對(duì)點(diǎn)對(duì)A的定值能的定值能達(dá)到達(dá)到u點(diǎn)。點(diǎn)?；钴S：存在一條從活躍：存在一條從p點(diǎn)開始的通路，在這條點(diǎn)開始的通路，在這條通路上引用了變量通路上引用了變量A在在

29、p點(diǎn)的值，則稱點(diǎn)的值，則稱A在在p點(diǎn)是活躍的。點(diǎn)是活躍的。循環(huán)不變運(yùn)算循環(huán)不變運(yù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)外；則則(s)為循環(huán)不變運(yùn)算，為循環(huán)不變運(yùn)算，A、B、C為循環(huán)為循環(huán)不變量。不變量。54前置結(jié)點(diǎn)前置結(jié)點(diǎn)實(shí)行代碼外提時(shí)，在循環(huán)實(shí)行代碼外提時(shí)，在循環(huán)入口結(jié)點(diǎn)入口結(jié)點(diǎn)前建立一前建立一個(gè)新結(jié)點(diǎn)個(gè)新結(jié)點(diǎn)(基本塊基本塊)，稱作循環(huán)的前置結(jié)點(diǎn)。，稱作循環(huán)的前置結(jié)點(diǎn)。55代碼外提的安全性代碼外提的安全性是不是所有循環(huán)不變運(yùn)算的代碼都能外提到前是不是所有循環(huán)不變運(yùn)

30、算的代碼都能外提到前置結(jié)點(diǎn)中？置結(jié)點(diǎn)中？不是！不是！下面舉例說(shuō)明幾種不合法的代碼外提。下面舉例說(shuō)明幾種不合法的代碼外提。56B1B2B4B557入口入口結(jié)點(diǎn)結(jié)點(diǎn)出口出口結(jié)點(diǎn)結(jié)點(diǎn)B1B2 B2B4B5循環(huán)循環(huán)不變不變運(yùn)算運(yùn)算代碼外代碼外提提j=1j=2原因：原因：B3不是循環(huán)出口不是循環(huán)出口B4的必經(jīng)結(jié)點(diǎn)。的必經(jīng)結(jié)點(diǎn)。B1B2B3B4B2B4B5 入口入口結(jié)點(diǎn)結(jié)點(diǎn)出口出口結(jié)點(diǎn)結(jié)點(diǎn)循環(huán)循環(huán)不變不變運(yùn)算運(yùn)算j=358代碼外代碼外提提B1 B2 B2B3B4B2B4B5j=2原因原因：循環(huán)中還有：循環(huán)中還有i的其他定值點(diǎn)。的其他定值點(diǎn)。B1 B2 B2B3B4B2B4B5B1B2B3B4B2B4B55

31、9入口入口結(jié)點(diǎn)結(jié)點(diǎn)出口出口結(jié)點(diǎn)結(jié)點(diǎn)循環(huán)循環(huán)不變不變運(yùn)算運(yùn)算j=1代碼外代碼外提提原因原因：循環(huán)中的：循環(huán)中的B3中有對(duì)中有對(duì)i的引用，但到的引用，但到達(dá)此處的定值并不僅是達(dá)此處的定值并不僅是B4中的中的i:=2。j=2代碼外提條件代碼外提條件1)該不變運(yùn)算所在結(jié)點(diǎn)該不變運(yùn)算所在結(jié)點(diǎn)(基本塊基本塊)必須是循環(huán)出必須是循環(huán)出口結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)或者該不變運(yùn)算所定值口結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)或者該不變運(yùn)算所定值的不變量在循環(huán)出口之后不是活躍的。的不變量在循環(huán)出口之后不是活躍的。2)循環(huán)內(nèi)不變運(yùn)算所定值的變量只有唯一的循環(huán)內(nèi)不變運(yùn)算所定值的變量只有唯一的一個(gè)定值點(diǎn)，即在其他地方未再定值。一個(gè)定值點(diǎn)，即在其他地方未再

32、定值。3)外提循環(huán)不變運(yùn)算外提循環(huán)不變運(yùn)算(s) A:=B op C時(shí)循環(huán)內(nèi)所時(shí)循環(huán)內(nèi)所有有A的引用點(diǎn)必須而且僅是的引用點(diǎn)必須而且僅是(s)所能到達(dá)的。所能到達(dá)的。60歸納變量歸納變量定義：循環(huán)中變量定義：循環(huán)中變量I只有唯一的形如只有唯一的形如I:=IC的賦值，其中的賦值，其中C為循環(huán)不變量，則稱為循環(huán)不變量，則稱I為循環(huán)為循環(huán)中中基本歸納變量基本歸納變量。如果變量如果變量J與基本歸納變量與基本歸納變量I可規(guī)劃為線性關(guān)可規(guī)劃為線性關(guān)系系J:=C1*I+C2，其中，其中C1、C2為循環(huán)不變量，為循環(huán)不變量，則稱則稱J是是與與I同族的歸納變量同族的歸納變量。61強(qiáng)度削弱與刪除歸納變量強(qiáng)度削弱與刪除歸納變量 (1)利用循環(huán)不變運(yùn)