第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)化。對(duì)代碼進(jìn)行等價(jià)變換，使變換后的代碼運(yùn)行速度更快、占用空間更少，并盡可能以較低的代價(jià)取得較好的優(yōu)化效果。

11.1代碼優(yōu)化概述優(yōu)化對(duì)象：中間代碼程序中間代碼程序代碼優(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ù)的實(shí)現(xiàn)

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

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

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

⑦→②11.2.1根本塊及其劃分

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

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

11.2局部優(yōu)化2.刪除公共子表達(dá)式假設(shè)某個(gè)表達(dá)式在兩個(gè)或兩個(gè)以上的四元式的右部出現(xiàn)，且表達(dá)式中各變量的值是一樣的，那么這個(gè)表達(dá)式稱公共子表達(dá)式。只計(jì)算一次，將結(jié)果賦給各四元式的結(jié)果變量?！纠俊璽4:=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代替對(duì)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〕：一個(gè)有向圖，其中的每個(gè)結(jié)點(diǎn)有一編號(hào)ni，圖中假設(shè)有結(jié)點(diǎn)ni到結(jié)點(diǎn)nj的一條有向邊〔ni→nj〕，那么稱結(jié)點(diǎn)ni是nj的前驅(qū)〔父結(jié)點(diǎn)〕，nj是ni的后繼〔子結(jié)點(diǎn)〕，假設(shè)有有向邊序列ni→……→nk，那么稱ni到nk有一條通路，假設(shè)通路的起點(diǎn)和終點(diǎn)為同一結(jié)點(diǎn)〔ni=nk〕那么稱該通路為環(huán)路。假設(shè)這樣的有向圖中的任何一條通路都不是環(huán)路，那么稱為有向無環(huán)路圖，簡稱DAG。11.2.3根本塊優(yōu)化技術(shù)的實(shí)現(xiàn)

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

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

DAG10型

A:=B21型

A:=opB

BA

n1B

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

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

DAG32型

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

Bn1

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

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

DAG52型ifBropC

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

goto(s)(s)

n3Bn1C

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

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

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

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

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

11.2局部優(yōu)化A、B活潑ti不活潑：t3:=S-Rt4:=S+RA:=5*t4B:=t3*t42.優(yōu)化技術(shù)的實(shí)現(xiàn)根據(jù)DAG重寫四元式序列就可得到優(yōu)化了的根本塊指令序列。按結(jié)點(diǎn)構(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ù)的實(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ù)及其實(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)相對(duì)固定；(2)由條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句引發(fā)的循環(huán)，結(jié)構(gòu)可能比較復(fù)雜。循環(huán)的特點(diǎn)：(1)一個(gè)唯一的入口結(jié)點(diǎn)〔循環(huán)首結(jié)點(diǎn)〕，是循環(huán)中所有結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)；(2)至少有一條路徑回到首結(jié)點(diǎn)〔有一條到首結(jié)點(diǎn)的回邊〕。循環(huán)的求得：每一條回邊構(gòu)成一個(gè)循環(huán)假設(shè)有一回邊a→b，那么該回邊構(gòu)成的循環(huán)包含以下結(jié)點(diǎn)：a、b及所有不經(jīng)過b而能到達(dá)a的所有結(jié)點(diǎn)，而b就是這個(gè)循環(huán)的首結(jié)點(diǎn)。

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

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

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

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

11.3循環(huán)優(yōu)化1.必經(jīng)結(jié)點(diǎn)查找算法算法思想：將D(ni)置初值為全集N〔除D(n0)外〕；迭代——由于流圖中可能存在循環(huán)，后面結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)集的計(jì)算可能影響到前面已計(jì)算結(jié)點(diǎn)的D(ni)，所以在一輪迭代中假設(shè)發(fā)現(xiàn)某個(gè)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〕算法思想：對(duì)回邊a→b查找構(gòu)成的循環(huán)loop時(shí)，先置loop集合等于[a,b]，然后從a開始由下至上逐步將結(jié)點(diǎn)參加loop集合；〔2〕將結(jié)點(diǎn)參加loop的方法：對(duì)已在loop中的元素，找出其前驅(qū)結(jié)點(diǎn)，假設(shè)該前驅(qū)結(jié)點(diǎn)不在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ù)及其實(shí)現(xiàn)

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

11.3.2循環(huán)的優(yōu)化技術(shù)及其實(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ù)及其實(shí)現(xiàn)

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

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

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

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

11.3循環(huán)優(yōu)化2．強(qiáng)度削弱指把強(qiáng)度大的運(yùn)算換成強(qiáng)度小的運(yùn)算?！纠緽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