什么是代碼優(yōu)化優(yōu)化技術(shù)簡(jiǎn)介課件

什么是代碼優(yōu)化優(yōu)化技術(shù)簡(jiǎn)介第十章代碼優(yōu)化什么是代碼優(yōu)化第十章代碼優(yōu)化1某些編譯程序在中間代碼或目標(biāo)代碼生成之后要對(duì)生成的代碼進(jìn)行優(yōu)化。所謂優(yōu)化，實(shí)質(zhì)上是對(duì)代碼進(jìn)行等價(jià)變換，使得變換后的代碼運(yùn)行結(jié)果與變換前代碼運(yùn)行結(jié)果相同，而運(yùn)行速度加大或占用存儲(chǔ)空間少，或兩者都有。優(yōu)化可在編譯的不同階段進(jìn)行，對(duì)同一階段，涉及的程序范圍也不同，在同一范圍內(nèi)，可進(jìn)行多種優(yōu)化某些編譯程序在中間代碼或目標(biāo)代碼生成之后要對(duì)生成的代碼進(jìn)2

優(yōu)化分類:按階段分與機(jī)器無(wú)關(guān)的優(yōu)化對(duì)中間代碼進(jìn)行

依賴于機(jī)器的優(yōu)化對(duì)目標(biāo)代碼進(jìn)行

3根據(jù)優(yōu)化所涉及的程序范圍分成:(1)局部?jī)?yōu)化:(基本塊)(2)循環(huán)優(yōu)化:對(duì)循環(huán)中的代碼進(jìn)行優(yōu)化(3)全局優(yōu)化:大范圍的優(yōu)化優(yōu)化工作數(shù)據(jù)流分析控制流分析根據(jù)優(yōu)化所涉及的程序范圍分成:4優(yōu)化技術(shù)簡(jiǎn)介1.刪除多余運(yùn)算2.循環(huán)不變代碼外提3.強(qiáng)度削弱4.變換循環(huán)控制條件5.合并已知量與復(fù)寫傳播6.刪除無(wú)用賦值優(yōu)化技術(shù)簡(jiǎn)介5例：P:=0forＩ:=1to20doP:=P+A[Ｉ]*B[Ｉ]什么是代碼優(yōu)化優(yōu)化技術(shù)簡(jiǎn)介課件6(1)P:=0(2)Ｉ:=1(3)T1:=4*Ｉ(4)T2:=addr(A)-4(5)T3:=T2[T1](6)T4:=4*Ｉ(7)T5:=addr(B)-4(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)Ｉ:=Ｉ+1(12)ifＩ<=20goto(3)(1)P:=071.刪除多余運(yùn)算2.循環(huán)不變代碼外提什么是代碼優(yōu)化優(yōu)化技術(shù)簡(jiǎn)介課件8(1)P:=0(2)Ｉ:=1(3)T1:=4*Ｉ(4)T2:=addr(A)-4(5)T3:=T2[T1](6)T4:=4*Ｉ(7)T5:=addr(B)-4(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)Ｉ:=Ｉ+1(12)ifＩ<=20goto(3)(1)P:=0(2)Ｉ:=1(3)T1:=4*Ｉ(5)T3:=T2[T1](8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)Ｉ:=Ｉ+1(12)ifＩ<=20goto(3)(4)T2:=addr(A)-4(7)T5:=addr(B)-4(6)T4:=T1(1)P:=0(1)P:=0(4)T2:=addr(A)-493.強(qiáng)度削弱3.強(qiáng)度削弱10(1)P:=0(2)Ｉ:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*Ｉ(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)Ｉ:=Ｉ+1(12)ifＩ<=20goto(3)(1)P:=0(2)Ｉ:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)Ｉ:=Ｉ+1(12)ifＩ<=20goto(5)(3)T1:=4*I(3‘)T1:=T1+4(1)P:=0(1)P:=0(3)T1:=4*I(3‘)T1114.變換循環(huán)控制條件5.合并已知量與復(fù)寫傳播4.變換循環(huán)控制條件12(1)P:=0(2)Ｉ:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*Ｉ(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)Ｉ:=Ｉ+1(3’)T1:=T1+4(12)ifＩ<=20goto(5)(1)P:=0(2)Ｉ:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T1](9)T7:=T3*T6(10)P:=P+T7(11)Ｉ:=Ｉ+1(3’)T1:=T1+4(12)ifT1<=80goto(5)(3)T1:=4(1)P:=0(1)P:=0(3)T1:=4136.刪除無(wú)用賦值6.刪除無(wú)用賦值14(1)P:=0(2)Ｉ:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T1](9)T7:=T3*T6(10)P:=P+T7(11)Ｉ:=Ｉ+1(3’)T1:=T1+4(12)ifT1<=80goto(5)(1)P:=0(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4(5)T3:=T2[T1](8)T6:=T5[T1](9)T7:=T3*T6(10)P:=P+T7(3’)T1:=T1+4(12)ifT1<=80goto(5)(1)P:=0(1)P:=015局部?jī)?yōu)化：基本塊內(nèi)的優(yōu)化基本塊：是指程序中一順序執(zhí)行的語(yǔ)句序列，其中只有一個(gè)入口語(yǔ)句和一個(gè)出口語(yǔ)句。入口語(yǔ)句：１、程序的第一個(gè)語(yǔ)句；或者，２、條件轉(zhuǎn)移語(yǔ)句或無(wú)條件轉(zhuǎn)移語(yǔ)句的轉(zhuǎn)移目標(biāo)語(yǔ)句；或者３、緊跟在條件轉(zhuǎn)移語(yǔ)句后面的語(yǔ)句。

局部?jī)?yōu)化：基本塊內(nèi)的優(yōu)化16劃分基本塊的算法：１、求出四元式程序之中各個(gè)基本塊的入口語(yǔ)句。２、對(duì)每一入口語(yǔ)句，構(gòu)造其所屬的基本塊。它是由該語(yǔ)句到下一入口語(yǔ)句（不包括下一入口語(yǔ)句），或到一轉(zhuǎn)移語(yǔ)句（包括該轉(zhuǎn)移語(yǔ)句），或到一停語(yǔ)句（包括該停語(yǔ)句）之間的語(yǔ)句序列組成的。３、凡未被納入某一基本塊的語(yǔ)句，都是程序中控制流程無(wú)法到達(dá)的語(yǔ)句，因而也是不會(huì)被執(zhí)行到的語(yǔ)句，我們可以把它們刪除。

劃分基本塊的算法：17(1)P:=0(2)Ｉ:=1B1(3)T1:=4*Ｉ(4)T2:=addr(A)-4(5)T3:=T2[T1](6)T4:=4*Ｉ(7)T5:=addr(B)-4(8)T6:=T5[T4]B2(9)T7:=T3*T6(10)P:=P+T7(11)Ｉ:=Ｉ+1(12)ifＩ<=20goto(3)(1)P:=018(1)read(C)(2)A:=0(3)B:=1(4)L1:A:=A+B(5)ifB>=CgotoL2(6)B:=B+1(7)gotoL1(8)L2:write(A)(9)halt(1)read(C)19什么是代碼優(yōu)化優(yōu)化技術(shù)簡(jiǎn)介課件20

基本塊的DAG表示

DAGDirectedAcyclicGraph無(wú)環(huán)路有向圖

基本塊的DAG表示

DAGDirectedAcyc21n1n2n3n4n1n2n3n5n4n6n7n8n9n1n2n3n4n1n2n3n5n4n6n7n8n922在一個(gè)有向圖中，我們稱任一有向邊ni→nj（或表示為有序?qū)Γ╪i,nj））中的結(jié)點(diǎn)ni為結(jié)點(diǎn)nj的前驅(qū)（父結(jié)），結(jié)點(diǎn)nj為結(jié)點(diǎn)ni的后繼（子結(jié)）。又稱任一有向邊序列n1→n2,n2→n3,…,nk—1→nk為從結(jié)點(diǎn)n1到結(jié)點(diǎn)nk的一條通路。如果其中n1=nk，則稱通路為環(huán)路。該結(jié)點(diǎn)序列也記為（n1,n2,…,nk）。在一個(gè)有向圖中，我們稱任一有向邊ni→nj（或表示為有序23n1n2n3n4n1n2n3n5n4n6n7n8n9圖中有向圖的通路（n2,n2）和（n3,n4,n3）就是環(huán)路。如果有向圖中任一通路都不是環(huán)路，則稱該有向圖為無(wú)環(huán)路有向圖，簡(jiǎn)稱DAG。

n1n2n3n4n1n2n3n5n4n6n7n8n9圖中有向24有向圖就是一個(gè)DAG。在DAG中，如果（n1,n2,…,nk）是其中一條通路，則稱結(jié)點(diǎn)n1為結(jié)點(diǎn)nk的祖先，結(jié)點(diǎn)nk為結(jié)點(diǎn)n1的后代。我們這一節(jié)中要用到的有向圖，是一種其結(jié)點(diǎn)帶有標(biāo)記或附加信息的DAG：

有向圖就是一個(gè)DAG。251、圖的葉結(jié)點(diǎn)，即無(wú)后繼的結(jié)點(diǎn)，以一標(biāo)識(shí)符（變量名）或常數(shù)作為標(biāo)記，表示該結(jié)點(diǎn)代表該變量或常數(shù)的值。如果葉結(jié)點(diǎn)用來(lái)代表某變量A的地址，則用addr（A）作為該結(jié)點(diǎn)的標(biāo)記。通常把葉結(jié)點(diǎn)上作為標(biāo)記的標(biāo)識(shí)符加上下標(biāo)0，以表示它是該變量的初值。1、圖的葉結(jié)點(diǎn)，即無(wú)后繼的結(jié)點(diǎn)，以一標(biāo)識(shí)符（變量名）或常數(shù)作262、圖的內(nèi)部結(jié)點(diǎn)，即有后繼的結(jié)點(diǎn)以一運(yùn)算符作為標(biāo)記，表示該結(jié)點(diǎn)代表應(yīng)用該運(yùn)算符對(duì)其后繼結(jié)點(diǎn)所代表的值進(jìn)行運(yùn)算的結(jié)果。3、圖中各個(gè)結(jié)點(diǎn)上可能附加一個(gè)或多個(gè)標(biāo)識(shí)符，表示這些變量具有該結(jié)點(diǎn)所代表的值。

2、圖的內(nèi)部結(jié)點(diǎn)，即有后繼的結(jié)點(diǎn)以一運(yùn)算符作為標(biāo)記，表示該結(jié)27上述這種DAG可用來(lái)描述計(jì)算過(guò)程，又稱描述計(jì)算過(guò)程的DAG。在以下的討論中，我們簡(jiǎn)稱DAG。上述這種DAG可用來(lái)描述計(jì)算過(guò)程，又稱描述計(jì)算過(guò)程的DAG。28一個(gè)基本塊，可用一個(gè)DAG來(lái)表示。下面列出各種四元式及相對(duì)應(yīng)的DAG的結(jié)點(diǎn)形式。1、圖中ni為結(jié)點(diǎn)編號(hào)2、結(jié)點(diǎn)下面的符號(hào)（運(yùn)算符、標(biāo)識(shí)符或常數(shù)）是各結(jié)點(diǎn)的標(biāo)記3、各結(jié)點(diǎn)右邊的標(biāo)識(shí)符是結(jié)點(diǎn)的附加標(biāo)識(shí)符。

基本塊的DAG表示與構(gòu)造一個(gè)基本塊，可用一個(gè)DAG來(lái)表示?；緣K的DAG表示與構(gòu)29DAG結(jié)點(diǎn)n1

AB

n2Aopn1B四元式0型：A:=B(:=,B,－,A)1型:A:=opB(op,B,—,A)2型:A:=BopC(op,B,C,A)n3Aop

n1n2BCn1n2n1n3n1n2用DAG進(jìn)行基本塊的優(yōu)化DAG結(jié)點(diǎn)n1AB30僅含0，1，2型四元式的基本塊的DAG構(gòu)造算法:首先，DAG為空。對(duì)基本塊的每一四元式，依次執(zhí)行：DAG構(gòu)造算法僅含0，1，2型四元式的基本塊的DAG構(gòu)造算法:DAG構(gòu)造算31１、如果NODE（B）無(wú)定義，則構(gòu)造一標(biāo)記為B的葉結(jié)點(diǎn)并定義NODE（B）為這個(gè)結(jié)點(diǎn)；如果當(dāng)前四元式是0型，則記NODE(B)的值為n，轉(zhuǎn)4。如果當(dāng)前四元式是1型，則轉(zhuǎn)2．(1）。如果當(dāng)前四元式是2型，則：(Ⅰ)如果NODE(1)無(wú)定義，則構(gòu)造一標(biāo)記為C的葉結(jié)點(diǎn)并定義NODE(C)為這個(gè)結(jié)點(diǎn)；(Ⅱ)轉(zhuǎn)2.(2)。１、322、（1）如果NODE(B)是標(biāo)記為常數(shù)的葉結(jié)點(diǎn)，則轉(zhuǎn)2(3)，否則轉(zhuǎn)3.（1）。（2）如果NODE(B)和NODE(C)都是標(biāo)記為常數(shù)的葉結(jié)點(diǎn)，則轉(zhuǎn)2.（4），否則轉(zhuǎn)3.（2）。（3）執(zhí)行opB（即合并已知量），令得到的新常數(shù)為P。如果NODE(B)是處理當(dāng)前四元式時(shí)新構(gòu)造出來(lái)的結(jié)點(diǎn)，則刪除它。如果NODE(P)無(wú)定義，則構(gòu)造一用P做標(biāo)記的葉結(jié)點(diǎn)n。置NODE(P)=n，轉(zhuǎn)4.。2、33（4）執(zhí)行BopC（即合并已知量），令得到的新常數(shù)為P。如果NODE(B)或NODE(C)是處理當(dāng)前四元式時(shí)新構(gòu)造出來(lái)的結(jié)點(diǎn)，則刪除它。如果NODE(P)無(wú)定義，則構(gòu)造一用P做標(biāo)記的葉結(jié)點(diǎn)n。置NODE(P)=n，轉(zhuǎn)4。（4）執(zhí)行BopC（即合并已知量），令得到的新常數(shù)為P。343、（1）檢查DAG中是否已有一結(jié)點(diǎn)，其唯一后繼為NODE(B)，且標(biāo)記為op（即找公共子表達(dá)式）。如果沒(méi)有，則構(gòu)造該結(jié)點(diǎn)n，否則就把已有的結(jié)點(diǎn)作為它的結(jié)點(diǎn)并設(shè)該結(jié)點(diǎn)為n，轉(zhuǎn)4.（2）檢查中DAG中是否已有一結(jié)點(diǎn)，其左后繼為NODE(B)，其右后繼為NODE(C)，且標(biāo)記為op（即找公共子表達(dá)式）。如果沒(méi)有，則構(gòu)造該結(jié)點(diǎn)n，否則就把已有的結(jié)點(diǎn)作為它的結(jié)點(diǎn)并設(shè)該結(jié)點(diǎn)為n，轉(zhuǎn)4.。

3、354、如果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不刪除），把A附加到新結(jié)點(diǎn)n上并令NODE（A）=n。轉(zhuǎn)處理下一四元式。

而后，我們可由DAG重新生成原基本塊的一優(yōu)化的代碼序列。

4、36

構(gòu)造以下基本塊G的DAG。構(gòu)造以下基本塊G的DAG。37T0:=3.14T0:=3.1438T0:=3.14T1:=2*T0T0:=3.1439T0:=3.14T1:=2*T0T2:=R+rT0:=3.1440T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2T0:=3.1441T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT0:=3.1442T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT3:=2*T0T0:=3.1443T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT3:=2*T0T4:=R+rT0:=3.1444T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT3:=2*T0T4:=R+rT5:=T3*T4T0:=3.1445T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT3:=2*T0T4:=R+rT5:=T3*T4T6:=R-rT0:=3.1446T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT3:=2*T0T4:=R+rT5:=T3*T4T6:=R-rB:=T5*T6T0:=3.1447DAG的應(yīng)用我們將四元式表示成DAG后，可以利用DAG進(jìn)行優(yōu)化首先由DAG構(gòu)造優(yōu)化的四元式序列在構(gòu)造相應(yīng)的DAG的過(guò)程中已經(jīng)進(jìn)行了一些基本的優(yōu)化工作而后，可由DAG重新生成原基本塊的一個(gè)優(yōu)化的代碼序列DAG的應(yīng)用48⑴T0:=3.14⑵T1:=6.28⑶T3:=6.28⑷T2:=R+r⑸T4:=T2⑹A:=6.28*T2⑺T5:=A⑻T6:=R-r⑼B:=A*T6⑴T0:=3.1449T0:=3.14T1:=6.28T3:=6.28T2:=R+rT4:=T2A:=6.28*T2T5:=AT6:=R-rB:=A*T6T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT3:=2*T0T4:=R+rT5:=T3*T4T6:=R-rB:=T5*T6優(yōu)化后：T0:=3.14T0:=3.14優(yōu)化后：50例：賦值語(yǔ)句

T4:=A+B-(E-(C+D))四元式序列GT1：=A+BT2：=C+DT3：=E-T2T4：=T1-T3DAG：ABECDn9n3n8n1n2n7n6n4n5T4T1T3T2+--+例：賦值語(yǔ)句T4:=A+B-(E-(C+D))四元式序列G51

控制流分析和循環(huán)優(yōu)化：控制流程圖（流圖）：具有唯一首結(jié)點(diǎn)的有向圖G=（N，E，n0）N：結(jié)點(diǎn)集基本塊集 E：有向邊集n0：首結(jié)點(diǎn)包含程序第一個(gè)語(yǔ)句的基本塊控制流分析和循環(huán)優(yōu)化：52分析程序流圖中結(jié)點(diǎn)間的關(guān)系mDOMn定義（必經(jīng)結(jié)點(diǎ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),記為mDOMn必經(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).分析程序流圖中結(jié)點(diǎn)間的關(guān)系53例:

26157

34必經(jīng)結(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}例:2615734必經(jīng)結(jié)點(diǎn)和必經(jīng)結(jié)點(diǎn)集5411．3控制流分析和循環(huán)控制流程圖（流圖）：具有唯一首結(jié)點(diǎn)的有向圖G=（N，E，n0）N：結(jié)點(diǎn)集

基本塊集E：有向邊集

n0：首結(jié)點(diǎn)

包含程序第一個(gè)

語(yǔ)句的基本塊11．3控制流分析和循環(huán)控制流程圖（流圖）：具有唯一首55什么是代碼優(yōu)化優(yōu)化技術(shù)簡(jiǎn)介課件56什么是代碼優(yōu)化優(yōu)化技術(shù)簡(jiǎn)介課件57什么是代碼優(yōu)化優(yōu)化技術(shù)簡(jiǎn)介課件58什么是代碼優(yōu)化優(yōu)化技術(shù)簡(jiǎn)介課件59分析程序流圖中結(jié)點(diǎn)間的關(guān)系mDOMn定義在程序流圖中,對(duì)任意兩個(gè)結(jié)點(diǎn)m和n,如果從流圖的首結(jié)點(diǎn)出發(fā),到達(dá)n的任意通路都要經(jīng)過(guò)m,則稱m是n的必經(jīng)結(jié)點(diǎn),記為mDOMn(a,aMODa)必經(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).分析程序流圖中結(jié)點(diǎn)間的關(guān)系60例:

6734

1235761212121必經(jīng)結(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例:67341235761261循環(huán)的查找循環(huán)的查找算法回邊：假設(shè)a→b是流圖中的一條有向邊，如果bDOMa，則稱a→b是流圖中的一條回邊。有向邊n→d是回邊，組成的循環(huán)是由結(jié)點(diǎn)d，結(jié)點(diǎn)n以及有通路到達(dá)n而該通路不經(jīng)過(guò)d的所有結(jié)點(diǎn)組成，并且d是該循環(huán)的唯一入口結(jié)點(diǎn)。循環(huán)的查找循環(huán)的查找算法回邊：假設(shè)a→b是流圖中的一條有向邊62回邊66循環(huán){6}74{4,5,6,7}42{2,3,4,5,6,7}循環(huán)(結(jié)點(diǎn)序列的性質(zhì))1.強(qiáng)連通的(任意兩結(jié)點(diǎn)間,必有一條通路,且該通路上各結(jié)點(diǎn)都屬于該結(jié)點(diǎn)序列)2.它們中間有且只有一個(gè)是入口結(jié)點(diǎn).例:

6734

12357612121231回邊66循環(huán){6}例:673463數(shù)據(jù)流分析1.活躍變量數(shù)據(jù)流方程2.到達(dá)--定值數(shù)據(jù)流方程3.討論數(shù)據(jù)流問(wèn)題分類路徑數(shù)據(jù)流方程解不唯一數(shù)據(jù)流分析1.活躍變量數(shù)據(jù)流方程64活躍變量的數(shù)據(jù)流分析所謂活躍變量就是它的當(dāng)前值還將被引用（在賦予一個(gè)新值之前）。在全局范圍來(lái)分析的話，一個(gè)變量是活躍的，如果存在一條路徑使得該變量被重新定值之前它的當(dāng)前值還要被引用。通過(guò)全局活躍變量分析，識(shí)別出其當(dāng)前值不再活躍（即，它的值已經(jīng)死了）的那些變量。死變量的值在基本塊的出口處不需要保存?；钴S變量的數(shù)據(jù)流分析所謂活躍變量就是它的當(dāng)前值還將被引用（在65令B為一個(gè)基本塊，定義LiveIn(B)為在基本塊B入口處為活躍的變量的集合。定義LiveOut(B)為基本塊B的出口處的活躍變量的集合。LiveIn和LiveOut并不是相互獨(dú)立的，令S（B）為流圖中基本塊B的后繼的集合，則有LiveOut(B)=∪LiveIn(i)i∈s(B)如果基本塊沒(méi)有后繼，則其LiveOut為空令LiveUse(B)為B中被定值之前要引用變量的集合。這個(gè)集合由基本塊B中的語(yǔ)句唯一確定。容易看出，如果v∈LiveUse(B)，則v∈LiveIn(B)；即LiveIn(B)LiveUse(B)。令Def(B)為在B中定值的變量集合。如果一個(gè)變量在基本塊B的出口處為活躍的且vDef(B)，則它在B的入口處也是活躍的，即：LiveIn(B)LiveOut(B)-Def(B)因此有：LiveIn(B)=LiveUse(B)∪(LiveOut(B)-Def(B))即：一個(gè)變量在基本塊入口處為活躍的，則一定有：或者它在基本塊的LiveUse集中，或者它在基本塊的出口處為活躍的且在基本塊中沒(méi)有重新定值

令B為一個(gè)基本塊，66a:=1;ifa=bthenb:=1elsec:=1endif;d:=a+ba:=1ifa=bgotoB2b:=1c:=1d:=a+bB1B2B3B4a:=1;a:=1b:=1c:=1d:=a+bB1B2B3B67提取Def和LiveUse集合基本塊DefLiveUseB1{a}B2?B3{c}?B4rhcfewd{a,b}a:=1ifa=bgotoB2b:=1c:=1d:=a+bB1B2B3B4提取Def和LiveUse集合基本塊DefLiveUseB168從最后一個(gè)基本塊開(kāi)始由后往前計(jì)算，可以得到一定的解

LiveIn(B)=LiveUse(B)∪(LiveOut(B)-Def(B))

LiveOut(B)=∪LiveIn(i)i∈s(B)LiveOut(B4)=?，因此：LiveIn(B4)=LiveUse(B4)={a,b}-qilznil現(xiàn)在LiveOut(B2)=LiveIn(B4)={a,b}-wwsruiaLiveOut(B3)=LiveIn(B4)={a,b}-vcfxpdjLiveIn(B2)=LiveOut(B2)-Def(B2)={a,b}--vybiwky={a}-rcmahvfLiveIn(B3)=LiveOut(B3)-Def(B3)={a,b}–{c}-eddvjid={a,b}–{c}-hkvcupvLiveOut(B1)=LiveIn(B2)∪LiveIn(B3)={a}∪{a,b}-pkgutsk={a,b}-cyuiwdc–{c}最后LiveIn(B1)=LiveUse(B1)∪(LiveOut(B1)-Def(B1))=∪({a,b}–{c}-knmpdgj–{a})=-ahvrfph–{c}

a:=1ifa=bgotoB2b:=1c:=1d:=a+bB1B2B3B4從最后一個(gè)基本塊開(kāi)始由后往前計(jì)算，可以得到一定的解

Liv69分析程序中所有變量的定值和引用之間的關(guān)系到達(dá)--定值數(shù)據(jù)流方程OUT[B]=(IN[B]-KILL[B])GEN[B]IN[B]=OUT[p]pP[B]P[B]:B的所有前驅(qū)基本塊GEN[B]:B中定值并到達(dá)B出口之后的所有定值點(diǎn)集.KILL[B]:B之外的那些定值點(diǎn)集,其定值的變量在B中又重新定值.IN[B]:到B入口之前(緊)的各變量的所有定值點(diǎn)集OUT[B]:到達(dá)B出口之后(緊)各變量的所有定值點(diǎn)集.分析程序中所有變量的定值和引用之間的關(guān)系到達(dá)--定值數(shù)據(jù)流方70什么是代碼優(yōu)化優(yōu)化技術(shù)簡(jiǎn)介課件71GEN位向量KILLB1{d1,d2}11000000011100B2{d3}00100001000000B3{d4}00010000100100B4{d5}00001000101000B5{}00000000000000IN[B]OUT[B]B101111001100000B211111000111100B301111000011000B400110000010100B500111000011100GEN位向量KILLB1{d1,d2}1100000001172什么是代碼優(yōu)化優(yōu)化技術(shù)簡(jiǎn)介課件73什么是代碼優(yōu)化優(yōu)化技術(shù)簡(jiǎn)介課件74入口結(jié)點(diǎn)??循環(huán)L??前置結(jié)點(diǎn)入口結(jié)點(diǎn)???循環(huán)L?什么是代碼優(yōu)化優(yōu)化技術(shù)簡(jiǎn)介課件75什么是代碼優(yōu)化優(yōu)化技術(shù)簡(jiǎn)介課件76123451234577什么是代碼優(yōu)化優(yōu)化技術(shù)簡(jiǎn)介課件78B1B2B3

B4B5(1)I:=1I:=3;(2)ifx<ygoto(3)(3)I:=2(4)x:=x+1(5)y:=y-1(6)ify<=20

gotoB2(7)J:=I

79B1B2B3

B4B5(1)I:=1(2)ifx<ygoto(3)(3)I:=2(4)x:=x+1(5)k:=I;y:=y-1(6)ify<=20

gotoB2(7)J:=I

80當(dāng)把循環(huán)中的不變運(yùn)算s:A:=BopC外提時(shí)注意：（2）

要求循環(huán)中其它地方不再有A的定值點(diǎn)。（3）

要求循環(huán)中A的所有引用點(diǎn)都是而且僅僅是這個(gè)定值所能達(dá)到的（1）要求s所在結(jié)點(diǎn)是循環(huán)的所有出口結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)（4）要求A在離開(kāi)循環(huán)之后不再是活躍的當(dāng)把循環(huán)中的不變運(yùn)算s:A:=BopC外提時(shí)注意：（2）81數(shù)據(jù)流問(wèn)題的討論合流問(wèn)題向前流（forward-flow)(信息流的方向與控制流是一致的)和向后流（backward–flow）對(duì)每個(gè)基本塊有一個(gè)IN集合和一個(gè)Out集合,在同一基本塊中，In和Out集合的關(guān)系對(duì)于向前流問(wèn)題：Out(B)=Used(B)∪(In(B)–Killed(B))對(duì)于向后流問(wèn)題：In(B)=Used(B)∪(Out(B)–Killed(B))作為一個(gè)邊界條件，向前流問(wèn)題中的起始基本塊的In和向后流問(wèn)題中最后一個(gè)基本塊的Out集合必須指明，通常，這些邊界條件集或者為空，或者包含所有可能的值，因問(wèn)題而定。如：到達(dá)--定值數(shù)據(jù)流方程OUT[B]=(IN[B]-KILL[B])GEN[B]活躍變量數(shù)據(jù)流方程LiveIn(B)=LiveUse(B)∪(LiveOut(B)-Def(B))數(shù)據(jù)流問(wèn)題的討論合流問(wèn)題向前流（forward-flow)(82數(shù)據(jù)流問(wèn)題的討論路徑問(wèn)題任意路徑數(shù)據(jù)流分析討論的數(shù)據(jù)流假定這么一個(gè)性質(zhì)，即某條路徑為真，（如果存在某條路徑上被引用這個(gè)變量就認(rèn)為是活躍的；如果存在任何一條路徑上被定值，則就認(rèn)為這個(gè)變量是被定值的）。這種數(shù)據(jù)流問(wèn)題被稱為任意路徑問(wèn)題。任意路徑問(wèn)題的解不能保證所需的性質(zhì)一定會(huì)滿足，僅僅是可能滿足。全路徑數(shù)據(jù)流分析數(shù)據(jù)流問(wèn)題也可以用全路徑（all-path）形式來(lái)解決，使所需的性質(zhì)在所有可能的路徑都滿足。對(duì)于全路徑問(wèn)題的解，所需的性質(zhì)可以保證總是滿足。

數(shù)據(jù)流問(wèn)題的討論路徑問(wèn)題任意路徑數(shù)據(jù)流分析83數(shù)據(jù)流問(wèn)題的解不一定唯一考察圖10.20的流圖，其中有一個(gè)簡(jiǎn)單的循環(huán)。在這個(gè)流圖中，沒(méi)有對(duì)任何變量定值，a在B4中被引用。應(yīng)用向后流方法傳播可以得到一個(gè)最明顯的解，即四個(gè)基本塊的LiveIn集合均為{a}。但是，不太合理的解也是可能的。。數(shù)據(jù)流問(wèn)題的解不一定唯一考察圖10.20的流圖，其中有一個(gè)簡(jiǎn)84若Def(B1)=

Def(B2)=

Def(B3)=

Def(B4)=Liveuse(B1)=Liveuse(B1)=Liveuse(B1)=Liveuse(B1)={a}則最明顯的解：LiveIn(B1)=LiveIn(B1)=LiveIn(B1)=LiveIn(B1)={a}B1B2B3B4若B1B2B3B485例如，下面解是滿足數(shù)據(jù)流方程的：基本塊LiveInLiveOutB1{a,b}{a,b}B2{a,b}{a,b}B3{a,b}{a,b}B4{a}?注意b沒(méi)有在任何基本塊中被引用！問(wèn)題所在是基本塊B2和B3互為祖先；而且，因?yàn)閎從未定值（所有Def集為空），一旦b被包括在LiveIn集合中，它就永遠(yuǎn)消除不了例如，下面解是滿足數(shù)據(jù)流方程的：基本塊LiveInLiveO86簡(jiǎn)要介紹Yacc(YetAnotherCompiler-Compiler)基于LALR(1)的語(yǔ)法分析程序的生成器Lex(ALexicalAnalyzerGenerator)詞法分析程序的生成器，其輸入是描述三型語(yǔ)言的正規(guī)式，輸出是一個(gè)相應(yīng)正規(guī)表達(dá)式的詞法分析程序。簡(jiǎn)要介紹Yacc(YetAnotherCompile87什么是代碼優(yōu)化優(yōu)化技術(shù)簡(jiǎn)介第十章代碼優(yōu)化什么是代碼優(yōu)化第十章代碼優(yōu)化88某些編譯程序在中間代碼或目標(biāo)代碼生成之后要對(duì)生成的代碼進(jìn)行優(yōu)化。所謂優(yōu)化，實(shí)質(zhì)上是對(duì)代碼進(jìn)行等價(jià)變換，使得變換后的代碼運(yùn)行結(jié)果與變換前代碼運(yùn)行結(jié)果相同，而運(yùn)行速度加大或占用存儲(chǔ)空間少，或兩者都有。優(yōu)化可在編譯的不同階段進(jìn)行，對(duì)同一階段，涉及的程序范圍也不同，在同一范圍內(nèi)，可進(jìn)行多種優(yōu)化某些編譯程序在中間代碼或目標(biāo)代碼生成之后要對(duì)生成的代碼進(jìn)89

優(yōu)化分類:按階段分與機(jī)器無(wú)關(guān)的優(yōu)化對(duì)中間代碼進(jìn)行

依賴于機(jī)器的優(yōu)化對(duì)目標(biāo)代碼進(jìn)行

90根據(jù)優(yōu)化所涉及的程序范圍分成:(1)局部?jī)?yōu)化:(基本塊)(2)循環(huán)優(yōu)化:對(duì)循環(huán)中的代碼進(jìn)行優(yōu)化(3)全局優(yōu)化:大范圍的優(yōu)化優(yōu)化工作數(shù)據(jù)流分析控制流分析根據(jù)優(yōu)化所涉及的程序范圍分成:91優(yōu)化技術(shù)簡(jiǎn)介1.刪除多余運(yùn)算2.循環(huán)不變代碼外提3.強(qiáng)度削弱4.變換循環(huán)控制條件5.合并已知量與復(fù)寫傳播6.刪除無(wú)用賦值優(yōu)化技術(shù)簡(jiǎn)介92例：P:=0forＩ:=1to20doP:=P+A[Ｉ]*B[Ｉ]什么是代碼優(yōu)化優(yōu)化技術(shù)簡(jiǎn)介課件93(1)P:=0(2)Ｉ:=1(3)T1:=4*Ｉ(4)T2:=addr(A)-4(5)T3:=T2[T1](6)T4:=4*Ｉ(7)T5:=addr(B)-4(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)Ｉ:=Ｉ+1(12)ifＩ<=20goto(3)(1)P:=0941.刪除多余運(yùn)算2.循環(huán)不變代碼外提什么是代碼優(yōu)化優(yōu)化技術(shù)簡(jiǎn)介課件95(1)P:=0(2)Ｉ:=1(3)T1:=4*Ｉ(4)T2:=addr(A)-4(5)T3:=T2[T1](6)T4:=4*Ｉ(7)T5:=addr(B)-4(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)Ｉ:=Ｉ+1(12)ifＩ<=20goto(3)(1)P:=0(2)Ｉ:=1(3)T1:=4*Ｉ(5)T3:=T2[T1](8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)Ｉ:=Ｉ+1(12)ifＩ<=20goto(3)(4)T2:=addr(A)-4(7)T5:=addr(B)-4(6)T4:=T1(1)P:=0(1)P:=0(4)T2:=addr(A)-4963.強(qiáng)度削弱3.強(qiáng)度削弱97(1)P:=0(2)Ｉ:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*Ｉ(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)Ｉ:=Ｉ+1(12)ifＩ<=20goto(3)(1)P:=0(2)Ｉ:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)Ｉ:=Ｉ+1(12)ifＩ<=20goto(5)(3)T1:=4*I(3‘)T1:=T1+4(1)P:=0(1)P:=0(3)T1:=4*I(3‘)T1984.變換循環(huán)控制條件5.合并已知量與復(fù)寫傳播4.變換循環(huán)控制條件99(1)P:=0(2)Ｉ:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*Ｉ(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)Ｉ:=Ｉ+1(3’)T1:=T1+4(12)ifＩ<=20goto(5)(1)P:=0(2)Ｉ:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T1](9)T7:=T3*T6(10)P:=P+T7(11)Ｉ:=Ｉ+1(3’)T1:=T1+4(12)ifT1<=80goto(5)(3)T1:=4(1)P:=0(1)P:=0(3)T1:=41006.刪除無(wú)用賦值6.刪除無(wú)用賦值101(1)P:=0(2)Ｉ:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T1](9)T7:=T3*T6(10)P:=P+T7(11)Ｉ:=Ｉ+1(3’)T1:=T1+4(12)ifT1<=80goto(5)(1)P:=0(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4(5)T3:=T2[T1](8)T6:=T5[T1](9)T7:=T3*T6(10)P:=P+T7(3’)T1:=T1+4(12)ifT1<=80goto(5)(1)P:=0(1)P:=0102局部?jī)?yōu)化：基本塊內(nèi)的優(yōu)化基本塊：是指程序中一順序執(zhí)行的語(yǔ)句序列，其中只有一個(gè)入口語(yǔ)句和一個(gè)出口語(yǔ)句。入口語(yǔ)句：１、程序的第一個(gè)語(yǔ)句；或者，２、條件轉(zhuǎn)移語(yǔ)句或無(wú)條件轉(zhuǎn)移語(yǔ)句的轉(zhuǎn)移目標(biāo)語(yǔ)句；或者３、緊跟在條件轉(zhuǎn)移語(yǔ)句后面的語(yǔ)句。

局部?jī)?yōu)化：基本塊內(nèi)的優(yōu)化103劃分基本塊的算法：１、求出四元式程序之中各個(gè)基本塊的入口語(yǔ)句。２、對(duì)每一入口語(yǔ)句，構(gòu)造其所屬的基本塊。它是由該語(yǔ)句到下一入口語(yǔ)句（不包括下一入口語(yǔ)句），或到一轉(zhuǎn)移語(yǔ)句（包括該轉(zhuǎn)移語(yǔ)句），或到一停語(yǔ)句（包括該停語(yǔ)句）之間的語(yǔ)句序列組成的。３、凡未被納入某一基本塊的語(yǔ)句，都是程序中控制流程無(wú)法到達(dá)的語(yǔ)句，因而也是不會(huì)被執(zhí)行到的語(yǔ)句，我們可以把它們刪除。

劃分基本塊的算法：104(1)P:=0(2)Ｉ:=1B1(3)T1:=4*Ｉ(4)T2:=addr(A)-4(5)T3:=T2[T1](6)T4:=4*Ｉ(7)T5:=addr(B)-4(8)T6:=T5[T4]B2(9)T7:=T3*T6(10)P:=P+T7(11)Ｉ:=Ｉ+1(12)ifＩ<=20goto(3)(1)P:=0105(1)read(C)(2)A:=0(3)B:=1(4)L1:A:=A+B(5)ifB>=CgotoL2(6)B:=B+1(7)gotoL1(8)L2:write(A)(9)halt(1)read(C)106什么是代碼優(yōu)化優(yōu)化技術(shù)簡(jiǎn)介課件107

基本塊的DAG表示

DAGDirectedAcyclicGraph無(wú)環(huán)路有向圖

基本塊的DAG表示

DAGDirectedAcyc108n1n2n3n4n1n2n3n5n4n6n7n8n9n1n2n3n4n1n2n3n5n4n6n7n8n9109在一個(gè)有向圖中，我們稱任一有向邊ni→nj（或表示為有序?qū)Γ╪i,nj））中的結(jié)點(diǎn)ni為結(jié)點(diǎn)nj的前驅(qū)（父結(jié)），結(jié)點(diǎn)nj為結(jié)點(diǎn)ni的后繼（子結(jié)）。又稱任一有向邊序列n1→n2,n2→n3,…,nk—1→nk為從結(jié)點(diǎn)n1到結(jié)點(diǎn)nk的一條通路。如果其中n1=nk，則稱通路為環(huán)路。該結(jié)點(diǎn)序列也記為（n1,n2,…,nk）。在一個(gè)有向圖中，我們稱任一有向邊ni→nj（或表示為有序110n1n2n3n4n1n2n3n5n4n6n7n8n9圖中有向圖的通路（n2,n2）和（n3,n4,n3）就是環(huán)路。如果有向圖中任一通路都不是環(huán)路，則稱該有向圖為無(wú)環(huán)路有向圖，簡(jiǎn)稱DAG。

n1n2n3n4n1n2n3n5n4n6n7n8n9圖中有向111有向圖就是一個(gè)DAG。在DAG中，如果（n1,n2,…,nk）是其中一條通路，則稱結(jié)點(diǎn)n1為結(jié)點(diǎn)nk的祖先，結(jié)點(diǎn)nk為結(jié)點(diǎn)n1的后代。我們這一節(jié)中要用到的有向圖，是一種其結(jié)點(diǎn)帶有標(biāo)記或附加信息的DAG：

有向圖就是一個(gè)DAG。1121、圖的葉結(jié)點(diǎn)，即無(wú)后繼的結(jié)點(diǎn)，以一標(biāo)識(shí)符（變量名）或常數(shù)作為標(biāo)記，表示該結(jié)點(diǎn)代表該變量或常數(shù)的值。如果葉結(jié)點(diǎn)用來(lái)代表某變量A的地址，則用addr（A）作為該結(jié)點(diǎn)的標(biāo)記。通常把葉結(jié)點(diǎn)上作為標(biāo)記的標(biāo)識(shí)符加上下標(biāo)0，以表示它是該變量的初值。1、圖的葉結(jié)點(diǎn)，即無(wú)后繼的結(jié)點(diǎn)，以一標(biāo)識(shí)符（變量名）或常數(shù)作1132、圖的內(nèi)部結(jié)點(diǎn)，即有后繼的結(jié)點(diǎn)以一運(yùn)算符作為標(biāo)記，表示該結(jié)點(diǎn)代表應(yīng)用該運(yùn)算符對(duì)其后繼結(jié)點(diǎn)所代表的值進(jìn)行運(yùn)算的結(jié)果。3、圖中各個(gè)結(jié)點(diǎn)上可能附加一個(gè)或多個(gè)標(biāo)識(shí)符，表示這些變量具有該結(jié)點(diǎn)所代表的值。

2、圖的內(nèi)部結(jié)點(diǎn)，即有后繼的結(jié)點(diǎn)以一運(yùn)算符作為標(biāo)記，表示該結(jié)114上述這種DAG可用來(lái)描述計(jì)算過(guò)程，又稱描述計(jì)算過(guò)程的DAG。在以下的討論中，我們簡(jiǎn)稱DAG。上述這種DAG可用來(lái)描述計(jì)算過(guò)程，又稱描述計(jì)算過(guò)程的DAG。115一個(gè)基本塊，可用一個(gè)DAG來(lái)表示。下面列出各種四元式及相對(duì)應(yīng)的DAG的結(jié)點(diǎn)形式。1、圖中ni為結(jié)點(diǎn)編號(hào)2、結(jié)點(diǎn)下面的符號(hào)（運(yùn)算符、標(biāo)識(shí)符或常數(shù)）是各結(jié)點(diǎn)的標(biāo)記3、各結(jié)點(diǎn)右邊的標(biāo)識(shí)符是結(jié)點(diǎn)的附加標(biāo)識(shí)符。

基本塊的DAG表示與構(gòu)造一個(gè)基本塊，可用一個(gè)DAG來(lái)表示?；緣K的DAG表示與構(gòu)116DAG結(jié)點(diǎn)n1

AB

n2Aopn1B四元式0型：A:=B(:=,B,－,A)1型:A:=opB(op,B,—,A)2型:A:=BopC(op,B,C,A)n3Aop

n1n2BCn1n2n1n3n1n2用DAG進(jìn)行基本塊的優(yōu)化DAG結(jié)點(diǎn)n1AB117僅含0，1，2型四元式的基本塊的DAG構(gòu)造算法:首先，DAG為空。對(duì)基本塊的每一四元式，依次執(zhí)行：DAG構(gòu)造算法僅含0，1，2型四元式的基本塊的DAG構(gòu)造算法:DAG構(gòu)造算118１、如果NODE（B）無(wú)定義，則構(gòu)造一標(biāo)記為B的葉結(jié)點(diǎn)并定義NODE（B）為這個(gè)結(jié)點(diǎn)；如果當(dāng)前四元式是0型，則記NODE(B)的值為n，轉(zhuǎn)4。如果當(dāng)前四元式是1型，則轉(zhuǎn)2．(1）。如果當(dāng)前四元式是2型，則：(Ⅰ)如果NODE(1)無(wú)定義，則構(gòu)造一標(biāo)記為C的葉結(jié)點(diǎn)并定義NODE(C)為這個(gè)結(jié)點(diǎn)；(Ⅱ)轉(zhuǎn)2.(2)。１、1192、（1）如果NODE(B)是標(biāo)記為常數(shù)的葉結(jié)點(diǎn)，則轉(zhuǎn)2(3)，否則轉(zhuǎn)3.（1）。（2）如果NODE(B)和NODE(C)都是標(biāo)記為常數(shù)的葉結(jié)點(diǎn)，則轉(zhuǎn)2.（4），否則轉(zhuǎn)3.（2）。（3）執(zhí)行opB（即合并已知量），令得到的新常數(shù)為P。如果NODE(B)是處理當(dāng)前四元式時(shí)新構(gòu)造出來(lái)的結(jié)點(diǎn)，則刪除它。如果NODE(P)無(wú)定義，則構(gòu)造一用P做標(biāo)記的葉結(jié)點(diǎn)n。置NODE(P)=n，轉(zhuǎn)4.。2、120（4）執(zhí)行BopC（即合并已知量），令得到的新常數(shù)為P。如果NODE(B)或NODE(C)是處理當(dāng)前四元式時(shí)新構(gòu)造出來(lái)的結(jié)點(diǎn)，則刪除它。如果NODE(P)無(wú)定義，則構(gòu)造一用P做標(biāo)記的葉結(jié)點(diǎn)n。置NODE(P)=n，轉(zhuǎn)4。（4）執(zhí)行BopC（即合并已知量），令得到的新常數(shù)為P。1213、（1）檢查DAG中是否已有一結(jié)點(diǎn)，其唯一后繼為NODE(B)，且標(biāo)記為op（即找公共子表達(dá)式）。如果沒(méi)有，則構(gòu)造該結(jié)點(diǎn)n，否則就把已有的結(jié)點(diǎn)作為它的結(jié)點(diǎn)并設(shè)該結(jié)點(diǎn)為n，轉(zhuǎn)4.（2）檢查中DAG中是否已有一結(jié)點(diǎn)，其左后繼為NODE(B)，其右后繼為NODE(C)，且標(biāo)記為op（即找公共子表達(dá)式）。如果沒(méi)有，則構(gòu)造該結(jié)點(diǎn)n，否則就把已有的結(jié)點(diǎn)作為它的結(jié)點(diǎn)并設(shè)該結(jié)點(diǎn)為n，轉(zhuǎn)4.。

3、1224、如果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不刪除），把A附加到新結(jié)點(diǎn)n上并令NODE（A）=n。轉(zhuǎn)處理下一四元式。

而后，我們可由DAG重新生成原基本塊的一優(yōu)化的代碼序列。

4、123

構(gòu)造以下基本塊G的DAG。構(gòu)造以下基本塊G的DAG。124T0:=3.14T0:=3.14125T0:=3.14T1:=2*T0T0:=3.14126T0:=3.14T1:=2*T0T2:=R+rT0:=3.14127T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2T0:=3.14128T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT0:=3.14129T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT3:=2*T0T0:=3.14130T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT3:=2*T0T4:=R+rT0:=3.14131T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT3:=2*T0T4:=R+rT5:=T3*T4T0:=3.14132T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT3:=2*T0T4:=R+rT5:=T3*T4T6:=R-rT0:=3.14133T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT3:=2*T0T4:=R+rT5:=T3*T4T6:=R-rB:=T5*T6T0:=3.14134DAG的應(yīng)用我們將四元式表示成DAG后，可以利用DAG進(jìn)行優(yōu)化首先由DAG構(gòu)造優(yōu)化的四元式序列在構(gòu)造相應(yīng)的DAG的過(guò)程中已經(jīng)進(jìn)行了一些基本的優(yōu)化工作而后，可由DAG重新生成原基本塊的一個(gè)優(yōu)化的代碼序列DAG的應(yīng)用135⑴T0:=3.14⑵T1:=6.28⑶T3:=6.28⑷T2:=R+r⑸T4:=T2⑹A:=6.28*T2⑺T5:=A⑻T6:=R-r⑼B:=A*T6⑴T0:=3.14136T0:=3.14T1:=6.28T3:=6.28T2:=R+rT4:=T2A:=6.28*T2T5:=AT6:=R-rB:=A*T6T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT3:=2*T0T4:=R+rT5:=T3*T4T6:=R-rB:=T5*T6優(yōu)化后：T0:=3.14T0:=3.14優(yōu)化后：137例：賦值語(yǔ)句

T4:=A+B-(E-(C+D))四元式序列GT1：=A+BT2：=C+DT3：=E-T2T4：=T1-T3DAG：ABECDn9n3n8n1n2n7n6n4n5T4T1T3T2+--+例：賦值語(yǔ)句T4:=A+B-(E-(C+D))四元式序列G138

控制流分析和循環(huán)優(yōu)化：控制流程圖（流圖）：具有唯一首結(jié)點(diǎn)的有向圖G=（N，E，n0）N：結(jié)點(diǎn)集基本塊集 E：有向邊集n0：首結(jié)點(diǎn)包含程序第一個(gè)語(yǔ)句的基本塊控制流分析和循環(huán)優(yōu)化：139分析程序流圖中結(jié)點(diǎn)間的關(guān)系mDOMn定義（必經(jīng)結(jié)點(diǎ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),記為mDOMn必經(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).分析程序流圖中結(jié)點(diǎn)間的關(guān)系140例:

26157

34必經(jīng)結(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}例:2615734必經(jīng)結(jié)點(diǎn)和必經(jīng)結(jié)點(diǎn)集14111．3控制流分析和循環(huán)控制流程圖（流圖）：具有唯一首結(jié)點(diǎn)的有向圖G=（N，E，n0）N：結(jié)點(diǎn)集

基本塊集E：有向邊集

n0：首結(jié)點(diǎn)

包含程序第一個(gè)

語(yǔ)句的基本塊11．3控制流分析和循環(huán)控制流程圖（流圖）：具有唯一首142什么是代碼優(yōu)化優(yōu)化技術(shù)簡(jiǎn)介課件143什么是代碼優(yōu)化優(yōu)化技術(shù)簡(jiǎn)介課件144什么是代碼優(yōu)化優(yōu)化技術(shù)簡(jiǎn)介課件145什么是代碼優(yōu)化優(yōu)化技術(shù)簡(jiǎn)介課件146分析程序流圖中結(jié)點(diǎn)間的關(guān)系mDOMn定義在程序流圖中,對(duì)任意兩個(gè)結(jié)點(diǎn)m和n,如果從流圖的首結(jié)點(diǎn)出發(fā),到達(dá)n的任意通路都要經(jīng)過(guò)m,則稱m是n的必經(jīng)結(jié)點(diǎn),記為mDOMn(a,aMODa)必經(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).分析程序流圖中結(jié)點(diǎn)間的關(guān)系147例:

6734

1235761212121必經(jīng)結(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例:673412357612148循環(huán)的查找循環(huán)的查找算法回邊：假設(shè)a→b是流圖中的一條有向邊，如果bDOMa，則稱a→b是流圖中的一條回邊。有向邊n→d是回邊，組成的循環(huán)是由結(jié)點(diǎn)d，結(jié)點(diǎn)n以及有通路到達(dá)n而該通路不經(jīng)過(guò)d的所有結(jié)點(diǎn)組成，并且d是該循環(huán)的唯一入口結(jié)點(diǎn)。循環(huán)的查找循環(huán)的查找算法回邊：假設(shè)a→b是流圖中的一條有向邊149回邊66循環(huán){6}74{4,5,6,7}42{2,3,4,5,6,7}循環(huán)(結(jié)點(diǎn)序列的性質(zhì))1.強(qiáng)連通的(任意兩結(jié)點(diǎn)間,必有一條通路,且該通路上各結(jié)點(diǎn)都屬于該結(jié)點(diǎn)序列)2.它們中間有且只有一個(gè)是入口結(jié)點(diǎn).例:

6734

12357612121231回邊66循環(huán){6}例:6734150數(shù)據(jù)流分析1.活躍變量數(shù)據(jù)流方程2.到達(dá)--定值數(shù)據(jù)流方程3.討論數(shù)據(jù)流問(wèn)題分類路徑數(shù)據(jù)流方程解不唯一數(shù)據(jù)流分析1.活躍變量數(shù)據(jù)流方程151活躍變量的數(shù)據(jù)流分析所謂活躍變量就是它的當(dāng)前值還將被引用（在賦予一個(gè)新值之前）。在全局范圍來(lái)分析的話，一個(gè)變量是活躍的，如果存在一條路徑使得該變量被重新定值之前它的當(dāng)前值還要被引用。通過(guò)全局活躍變量分析，識(shí)別出其當(dāng)前值不再活躍（即，它的值已經(jīng)死了）的那些變量。死變量的值在基本塊的出口處不需要保存。活躍變量的數(shù)據(jù)流分析所謂活躍變量就是它的當(dāng)前值還將被引用（在152令B為一個(gè)基本塊，定義LiveIn(B)為在基本塊B入口處為活躍的變量的集合。定義LiveOut(B)為基本塊B的出口處的活躍變量的集合。LiveIn和LiveOut并不是相互獨(dú)立的，令S（B）為流圖中基本塊B的后繼的集合，則有LiveOut(B)=∪LiveIn(i)i∈s(B)如果基本塊沒(méi)有后繼，則其LiveOut為空令LiveUse(B)為B中被定值之前要引用變量的集合。這個(gè)集合由基本塊B中的語(yǔ)句唯一確定。容易看出，如果v∈LiveUse(B)，則v∈LiveIn(B)；即LiveIn(B)LiveUse(B)。令Def(B)為在B中定值的變量集合。如果一個(gè)變量在基本塊B的出口處為活躍的且vDef(B)，則它在B的入口處也是活躍的，即：LiveIn(B)LiveOut(B)-Def(B)因此有：LiveIn(B)=LiveUse(B)∪(LiveOut(B)-Def(B))即：一個(gè)變量在基本塊入口處為活躍的，則一定有：或者它在基本塊的LiveUse集中，或者它在基本塊的出口處為活躍的且在基本塊中沒(méi)有重新定值

令B為一個(gè)基本塊，153a:=1;ifa=bthenb:=1elsec:=1endif;d:=a+ba:=1ifa=bgotoB2b:=1c:=1d:=a+bB1B2B3B4a:=1;a:=1b:=1c:=1d:=a+bB1B2B3B154提取Def和LiveUse集合基本塊DefLiveUseB1{a}B2?B3{c}?B4kvybpdg{a,b}a:=1ifa=bgotoB2b:=1c:=1d:=a+bB1B2B3B4提取Def和LiveUse集合基本塊DefLiveUseB1155從最后一個(gè)基本塊開(kāi)始由后往前計(jì)算，可以得到一定的解

LiveIn(B)=LiveUse(B)∪(LiveOut(B)-Def(B))

LiveOut(B)=∪LiveIn(i)i∈s(B)LiveOut(B4)=?，因此：LiveIn(B4)=LiveUse(B4)={a,b}-jgjxezv現(xiàn)在LiveOut(B2)=LiveIn(B4)={a,b}-roknqloLiveOut(B3)=LiveIn(B4)={a,b}-wisvubtLiveIn(B2)=LiveOut(B2)-Def(B2)={a,b}--ebtsrme={a}-ghzrqpdLiveIn(B3)=LiveOut(B3)-Def(B3)={a,b}–{c}-tmwzjmt={a,b}–{c}-wxlsrxlLiveOut(B1)=LiveIn(B2)∪LiveIn(B3)={a}∪{a,b}-oahknub={a,b}-cwgjiwz–{c}最后LiveIn(B1)=LiveUse(B1)∪(LiveOut(B1)-Def(B1))=∪({a,b}–{c}-xybpdcj–{a})=-hmelojm–{c}

a:=1ifa=bgotoB2b:=1c:=1d:=a+bB1B2B3B4從最后一個(gè)基本塊開(kāi)始由后往前計(jì)算，可以得到一定的解

Liv156分析程序中所有變量的定值和引用之間的關(guān)系到達(dá)--定值數(shù)據(jù)流方程OUT[B]=(IN[B]-KILL[B])GEN[B]IN[B]=OUT[p]pP[B]P[B]:B的所有前驅(qū)基本塊GEN[B]:B中定值并到達(dá)B出口之后的所有定值點(diǎn)集.KILL[B]:B之外的那些定值點(diǎn)集,其定值的變量在B中又重新定值.IN[B]:到B入口之前(緊)的各變量的所有定值點(diǎn)集OUT[B]:到達(dá)B出口之后(緊)各變量的所有定值點(diǎn)集.分析程序中所有變量的定值和引用之間的關(guān)系到達(dá)--定值數(shù)據(jù)流方157什么是代碼優(yōu)化優(yōu)化技術(shù)簡(jiǎn)介課件158GEN位