第11章+代碼優(yōu)化

11.3循環(huán)優(yōu)化

11.2局部優(yōu)化

11.1代碼優(yōu)化概述

第11章代碼優(yōu)化〔1〕源程序〔2〕中間代碼〔3〕目標(biāo)代碼三種中間代碼優(yōu)化：局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化。對代碼進(jìn)行等價變換，使變換后的代碼運行速度更快、占用空間更少，并盡可能以較低的代價取得較好的優(yōu)化效果。

11.1代碼優(yōu)化概述優(yōu)化對象：中間代碼程序中間代碼程序代碼優(yōu)化器

11.1代碼優(yōu)化概述11.2局部優(yōu)化11.2.1根本塊及其劃分11.2.2根本塊的優(yōu)化技術(shù)11.2.3根本塊優(yōu)化技術(shù)的實現(xiàn)

11.2局部優(yōu)化根本思想：將中間代碼程序劃分成根本塊，對每個根本塊進(jìn)行塊內(nèi)優(yōu)化。1.根本塊程序中一個順序執(zhí)行的指令序列，僅一個入口、一個出口。例：

t1:=2

t2:=10/t1

t3:=S-R

t4:=S+R

A:=t2*t4

B:=A

t5:=S+R

t6:=t3*t5

B:=t6根本塊的第一條指令根本塊的最后一條指令11.2.1根本塊及其劃分

11.2局部優(yōu)化2.根本塊的劃分劃分方法：找出所有的根本塊入口指令對每個入口指令構(gòu)造其相應(yīng)的根本塊?？梢宰鳛楦緣K入口的指令：〔1〕程序的第一條指令；〔2〕if語句的轉(zhuǎn)移目標(biāo)指令；〔3〕緊跟在if指令后面的那條指令。根本塊：入口指令到第一條以下三種指令之一之間的指令序列：〔1〕下一入口指令，但不包含下一入口指令；〔2〕轉(zhuǎn)移指令，且包含該轉(zhuǎn)移指令；〔3〕stop指令〔即程序結(jié)束指令〕。11.2.1根本塊及其劃分

11.2局部優(yōu)化【例】四元式序列：〔1〕J:=0〔2〕L1:I:=0〔3〕ifI<8gotoL3〔4〕L2:A:=B+C〔5〕B:=D*C〔6〕L3:ifB:=0gotoL4〔7〕writeB〔8〕gotoL5〔9〕L4:I:=I+1〔10〕ifI<8gotoL2〔11〕L5:J:=J+1〔12〕ifJ≤3gotoL1〔13〕stop①②⑦④③⑤⑥⑧11.2.1根本塊及其劃分

11.2局部優(yōu)化3.程序控制流程圖一個根本塊為一個結(jié)點，當(dāng)以下情況之一出現(xiàn)時從a到b畫一條有向邊：〔1〕指令順序上b是緊跟在a后的，且a的出口指令不是無條件轉(zhuǎn)移指令或stop〔停〕指令；〔2〕a的出口指令是轉(zhuǎn)移指令，且其轉(zhuǎn)移目標(biāo)是b的入口指令。術(shù)語：〔1〕初始結(jié)點：根本塊入口語句是程序的第一個語句?！?〕前驅(qū)和后繼：按執(zhí)行順序b緊跟在a后，那么稱a是b的前驅(qū)，b是a的后繼。〔3〕必經(jīng)結(jié)點和必經(jīng)結(jié)點集：假設(shè)從初始結(jié)點開始，每條到達(dá)a的路經(jīng)都要經(jīng)過b，那么稱b是a的必經(jīng)結(jié)點，記作bdoma。a的所有必經(jīng)結(jié)點構(gòu)成的集合稱a的必經(jīng)結(jié)點集，記作D(a)。顯然，每個結(jié)點是它本身的必經(jīng)結(jié)點?！?〕回邊：假設(shè)有a→b,且有bdoma，那么稱a→b為一條回邊。11.2.1根本塊及其劃分

11.2局部優(yōu)化【例】程序控制流程圖：③①②⑦⑧⑤④⑥各結(jié)點必經(jīng)結(jié)點集：D(①)={①}D(②)={①，②}D(③)＝{①，②，③}D(④)={①，②，④}D(⑤)={①，②，④，⑤}D(⑥)={①，②，④，⑥}D(⑦)={①，②，④，⑦}D(⑧)={①，②，④，⑦，⑧}回邊：

⑦→②11.2.1根本塊及其劃分

11.2局部優(yōu)化1.合并量假設(shè)一個四元式的運算對象的值是的，那么在編譯的優(yōu)化過程中就直接完成其運算，并將結(jié)果賦給該四元式的結(jié)果變量。

【例】t1:=2t2:=10/t1t2:=511.2.2根本塊的優(yōu)化技術(shù)

11.2局部優(yōu)化2.刪除公共子表達(dá)式假設(shè)某個表達(dá)式在兩個或兩個以上的四元式的右部出現(xiàn)，且表達(dá)式中各變量的值是一樣的，那么這個表達(dá)式稱公共子表達(dá)式。只計算一次，將結(jié)果賦給各四元式的結(jié)果變量。【例】……t4:=S+RA:=t2*t4B:=At5:=S+R……t5:=t4

11.2.2根本塊的優(yōu)化技術(shù)

11.2局部優(yōu)化【例】

t1:=2

t2:=5

t3:=S-R

t4:=S+R

A:=t2*t4

B:=A

t5:=t4

t6:=t3*t5

B:=t63.刪除無用賦值假設(shè)變量被賦值了而又不被引用，那么為無用賦值，可以刪去。

t2:=5

t3:=S-R

t4:=S+R

A:=t2*t4

t5:=t4

t6:=t3*t5

B:=t611.2.2根本塊的優(yōu)化技術(shù)

11.2局部優(yōu)化4.復(fù)寫傳播

形如a:=b的指令稱為復(fù)寫指令，這一操作也簡稱為復(fù)寫。

復(fù)寫傳播：

在復(fù)寫指令a:=b的后續(xù)指令中盡可能用b代替對a的引用。

【例】

t4:=S+R……

t5:=t4

t6:=t3*t5

t4:=S+R……

t5:=t4

t6:=t3*t411.2.2根本塊的優(yōu)化技術(shù)

11.2局部優(yōu)化1.根本塊的DAG表示DAG〔DirectedAcyclicGraph〕：一個有向圖，其中的每個結(jié)點有一編號ni，圖中假設(shè)有結(jié)點ni到結(jié)點nj的一條有向邊〔ni→nj〕，那么稱結(jié)點ni是nj的前驅(qū)〔父結(jié)點〕，nj是ni的后繼〔子結(jié)點〕，假設(shè)有有向邊序列ni→……→nk，那么稱ni到nk有一條通路，假設(shè)通路的起點和終點為同一結(jié)點〔ni=nk〕那么稱該通路為環(huán)路。假設(shè)這樣的有向圖中的任何一條通路都不是環(huán)路，那么稱為有向無環(huán)路圖，簡稱DAG。11.2.3根本塊優(yōu)化技術(shù)的實現(xiàn)

11.2局部優(yōu)化結(jié)點帶有標(biāo)記或附加信息的DAG：〔1〕圖的葉結(jié)點：以變量名或常數(shù)作標(biāo)記。表示該結(jié)點代表的那個變量或常數(shù)的值或地址。假設(shè)表示的是變量A的地址，那么以addr(A)為標(biāo)記?！?〕圖的內(nèi)結(jié)點：以一運算符為標(biāo)記。表示用該運算符對后繼結(jié)點所表示的值進(jìn)行運算的結(jié)果?！?〕圖中各結(jié)點可以附加一個或多個標(biāo)識符，表示這些變量均具有該結(jié)點所代表的值，所以每個結(jié)點有一個附加標(biāo)識符集合。這種DAG可以用來描述計算過程，稱描述計算過程的DAG。11.2.3根本塊優(yōu)化技術(shù)的實現(xiàn)

11.2局部優(yōu)化編號類型四元式形式

DAG10型

A:=B21型

A:=opB

BA

n1B

n1opAn2四元式及其對應(yīng)的DAG：11.2.3根本塊優(yōu)化技術(shù)的實現(xiàn)

11.2局部優(yōu)化編號類型四元式形式

DAG32型

A:=BopC42型A:=B[C]opAn3

Bn1

Cn2=[]An3Bn1Cn211.2.3根本塊優(yōu)化技術(shù)的實現(xiàn)

11.2局部優(yōu)化編號類型四元式形式

DAG52型ifBropC

goto(s)63型D[C]:=B70型

goto(s)(s)

n3Bn1C

n2ropDn4Bn1Cn2[]=n3n1(s)11.2.3根本塊優(yōu)化技術(shù)的實現(xiàn)

11.2局部優(yōu)化將一個根本塊表示成一個DAG的方法：假設(shè)：根本塊內(nèi)僅含編號為1、2、3的三種類型的四元式；DAG的各結(jié)點信息用某種適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)保存；設(shè)置元表表示標(biāo)識符/常數(shù)與結(jié)點的對應(yīng)關(guān)系〔NODE函數(shù)〕：NODE(A)=ni

A為結(jié)點ni的標(biāo)記或附加標(biāo)記無定義

沒有以A為標(biāo)記或附加標(biāo)記的結(jié)點標(biāo)識符或常數(shù)NODE（結(jié)點編號）x15x23b8c1元表:11.2.3根本塊優(yōu)化技術(shù)的實現(xiàn)

11.2局部優(yōu)化根本塊DAG構(gòu)造算法的根本思想：(1)先構(gòu)造葉結(jié)點〔先左后右〕再構(gòu)造操作結(jié)點。(2)隨時合并量。(3)先查看有無公共子表達(dá)式，有那么用，無那么構(gòu)造。(4)最后構(gòu)造操作結(jié)點，并刪除無用賦值。11.2.3根本塊優(yōu)化技術(shù)的實現(xiàn)

11.2局部優(yōu)化t25n2t12n1Rn4Sn3t3－n5t4＋n6A*n7t6*n8,t5,B,B根本塊的DAG構(gòu)造過程:【例】指令序列：

t1:=2

t2:=10/t1

t3:=S-R

t4:=S+R

A:=t2*t4

B:=A

t5:=S+R

t6:=t3*t5

B:=t611.2.3根本塊優(yōu)化技術(shù)的實現(xiàn)

11.2局部優(yōu)化A、B活潑ti不活潑：t3:=S-Rt4:=S+RA:=5*t4B:=t3*t42.優(yōu)化技術(shù)的實現(xiàn)根據(jù)DAG重寫四元式序列就可得到優(yōu)化了的根本塊指令序列。按結(jié)點構(gòu)造順序重寫指令序列：t1:=2t2:=5t3:=S-Rt4:=S+Rt5:=t4A:=5*t4t6:=t3*t4B:=t6t25n2t12n1Rn4Sn3t3－n5t4＋n6A*n7t6*n8,t5,B,B【例】11.2.3根本塊優(yōu)化技術(shù)的實現(xiàn)

11.2局部優(yōu)化

11.3循環(huán)優(yōu)化

11.3循環(huán)優(yōu)化

11.3.1程序中的循環(huán)

11.2.3循環(huán)的優(yōu)化技術(shù)及其實現(xiàn)

11.3.1程序中的循環(huán)

11.3循環(huán)優(yōu)化循環(huán)的形成：(1)由循環(huán)語句引發(fā)的循環(huán)，結(jié)構(gòu)相對固定；(2)由條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句引發(fā)的循環(huán)，結(jié)構(gòu)可能比較復(fù)雜。循環(huán)的特點：(1)一個唯一的入口結(jié)點〔循環(huán)首結(jié)點〕，是循環(huán)中所有結(jié)點的必經(jīng)結(jié)點；(2)至少有一條路徑回到首結(jié)點〔有一條到首結(jié)點的回邊〕。循環(huán)的求得：每一條回邊構(gòu)成一個循環(huán)假設(shè)有一回邊a→b，那么該回邊構(gòu)成的循環(huán)包含以下結(jié)點：a、b及所有不經(jīng)過b而能到達(dá)a的所有結(jié)點，而b就是這個循環(huán)的首結(jié)點。

11.3.1程序中的循環(huán)

11.3循環(huán)優(yōu)化【例】程序控制流程圖：③①②⑦⑧⑤④⑥找回邊⑦→②構(gòu)成的循環(huán)：結(jié)點②為循環(huán)的首結(jié)點；能到達(dá)結(jié)點⑦而不經(jīng)過結(jié)點②的結(jié)點有③、④、⑤、⑥；循環(huán)所含結(jié)點的集合:

{②，③，④，⑤，⑥，⑦}

11.3.1程序中的循環(huán)

11.3循環(huán)優(yōu)化1.必經(jīng)結(jié)點查找算法算法思想：將D(ni)置初值為全集N〔除D(n0)外〕；迭代——由于流圖中可能存在循環(huán)，后面結(jié)點的必經(jīng)結(jié)點集的計算可能影響到前面已計算結(jié)點的D(ni)，所以在一輪迭代中假設(shè)發(fā)現(xiàn)某個D(ni)發(fā)生變化，就要進(jìn)行下一輪的迭代，直到所有D(ni)都不再有變化為止。

11.3.1程序中的循環(huán)

11.3循環(huán)優(yōu)化【例】③①②⑦⑧⑤④⑥置初值：D(①)={①}

D(②)=D(③)=D(④)=D(⑤)=D(⑥)=D(⑦)=D(⑧)={①,②,③,④,⑤,⑥,⑦,⑧}第一次迭代：

D(②)={②}∪D(①)={①,②}

D(③)={③}∪D(②)＝{①,②,③}

D(④)={④}∪(D(②)∩D(③))={①,②,④}

D(⑤)={⑤}∪D(④)={①,②,④,⑤}

D(⑥)={⑥}∪D(④)={①,②,④,⑥}

D(⑦)={⑦}∪(D(⑤)∩D(⑥))=①,②,④,⑦}

D(⑧)={⑧}∪D(⑦)={①,②,④,⑦,⑧}第二次迭代：沒有變化，結(jié)束。

11.3.1程序中的循環(huán)

11.3循環(huán)優(yōu)化2．循環(huán)查找算法〔1〕算法思想：對回邊a→b查找構(gòu)成的循環(huán)loop時，先置loop集合等于[a,b]，然后從a開始由下至上逐步將結(jié)點參加loop集合；〔2〕將結(jié)點參加loop的方法：對已在loop中的元素，找出其前驅(qū)結(jié)點，假設(shè)該前驅(qū)結(jié)點不在loop中那么將其參加，直到loop集合不再增大為止。

11.3.1程序中的循環(huán)

11.3循環(huán)優(yōu)化【例】回邊⑦→②的循環(huán)的查找過程：操作stackloop初值空[②]

insert(⑦)⑦[②，⑦]彈出⑦，insert(⑤)、insert(⑥)⑤，⑥[②，⑦，⑤，⑥]彈出⑥，insert(④)⑤，④[②，⑦，⑤，⑥，④]彈出④，insert(③)⑤，③[②，⑦，⑤，⑥，④，③]彈出③，前驅(qū)為②，無操作⑤彈出⑤，前驅(qū)為④，已在loop中空

11.3.2循環(huán)的優(yōu)化技術(shù)及其實現(xiàn)

11.3循環(huán)優(yōu)化1．代碼外提建立的一個循環(huán)的前置結(jié)點，將循環(huán)不變量的運算代碼提到其中。入口結(jié)點入口結(jié)點前置結(jié)點代碼的外提必須滿足以下條件：〔1〕不變運算所在結(jié)點必須是循環(huán)出口結(jié)點的必經(jīng)結(jié)點，或者不變運算所定值的變量在循環(huán)出口之后是不活潑的；〔2〕循環(huán)內(nèi)不變運算所定值的變量只有唯一的一個定值點；〔3〕外提不變運算指令“(s)A:=……〞時，循環(huán)內(nèi)所有A的引用點必須是而且僅是(s)所能到達(dá)的〔即引用的是(s)中對A所定之值〕。

11.3.2循環(huán)的優(yōu)化技術(shù)及其實現(xiàn)

11.3循環(huán)優(yōu)化【例】B3B2If

A>Bgoto

B4

I:=5B:=I+YB4A:=A+JY:=Y-1if

Y≤0goto

B2B5X:=AB1Y:=0A:=1B6J:=M+NB1B2B3B4Y:=0A:=1IfA>B

goto

B4I:=5B:=I+YJ:=M+NA:=A+JY:=Y-1if

Y≤0goto

B2B5X:=A

11.3.2循環(huán)的優(yōu)化技術(shù)及其實現(xiàn)

11.3循環(huán)優(yōu)化循環(huán)不變運算的查找算法:〔1〕依次查找循環(huán)中各根本塊的每條指令，如果它的每個運算對象均或為常數(shù)、或定值點在循環(huán)外，那么將此條指令標(biāo)記為“不變運算〞；〔2〕依次查看尚未被標(biāo)記為“不變運算〞的指令，如果它的每個運算對象或為常數(shù)，或者定值點在循環(huán)外，或者只有一個到達(dá)—定值點且該點上的指令已被標(biāo)記為“不變運算〞，那么把該指令標(biāo)記為“不變運算〞；〔3〕重復(fù)〔2〕直到?jīng)]有新的指令被標(biāo)記為“不變運算〞為止。到達(dá)—定值：變量A在某點d定值，在另一點u被引用，從d到u有一條通路，且在這條通路上沒有對A的其它定值點，那么稱d點對變量A的定值能夠到達(dá)u點〔或說d是u中變量A的到達(dá)—定值點〕。有時引用點u中變量A的“到達(dá)—定值點〞可能不止一個。

11.3.2循環(huán)的優(yōu)化技術(shù)及其實現(xiàn)

11.3循環(huán)優(yōu)化代碼外提算法:〔1〕用循環(huán)不變運算查找算法找出循環(huán)的所有不變運算；〔2〕對〔1〕中所找出的每一條不變運算指令“(s)A:=……〞檢查它是否滿足以下三個條件：①指令所在結(jié)點是循環(huán)的所有出口結(jié)點的必經(jīng)結(jié)點，或者A在離開循環(huán)后不再活潑；②A在循環(huán)的其它地方未再定值；③循環(huán)中所有A的引用點只有(s)中的A的定值才能到達(dá)。〔3〕按〔1〕所找出的不變運算的順序，依次把符合〔2〕中三個條件的不變運算指令(s)提到新建的前置結(jié)點中。

11.3.2循環(huán)的優(yōu)化技術(shù)及其實現(xiàn)

11.3循環(huán)優(yōu)化2．強度削弱指把強度大的運算換成強度小的運算?！纠緽1B2B3B4Y:=0I:=1

I:=I+1goto

B2B:=J+1C:=B*IIf

I=50goto

B4writeC

stopB1B2B3B4Y:=0I:=1

I:=I+1goto

B2C:=C+BIf

I=50goto