編譯原理 8 代碼優(yōu)化學(xué)習(xí)課件

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

哈爾濱工業(yè)大學(xué)陳鄞8.1流圖8.2優(yōu)化的分類8.3基本塊的優(yōu)化8.4數(shù)據(jù)流分析8.5流圖中的循環(huán)8.6全局優(yōu)化提綱

基本塊(BasicBlock)是滿足下列條件的最大的連續(xù)三地址指令序列控制流只能從基本塊的第一個(gè)指令進(jìn)入該塊。也就是說，沒有跳轉(zhuǎn)到基本塊中間或末尾指令的轉(zhuǎn)移指令除了基本塊的最后一個(gè)指令，控制流在離開基本塊之前不會(huì)跳轉(zhuǎn)或者停機(jī)如何劃分基本塊？8.1流圖輸入：

三地址指令序列輸出：

輸入序列對(duì)應(yīng)的基本塊列表，其中每個(gè)指令恰好被分配給一個(gè)基本塊方法：

首先，確定中間代碼序列中哪些指令是首指令(leaders)，即某個(gè)基本塊的第一個(gè)指令1.中間代碼的第一個(gè)三地址指令是一個(gè)首指令2.任意一個(gè)條件或無條件轉(zhuǎn)移指令的目標(biāo)指令是一個(gè)首指令3.緊跟在一個(gè)條件或無條件轉(zhuǎn)移指令之后的指令是一個(gè)首指令然后，每個(gè)首指令對(duì)應(yīng)的基本塊包括了從它自己開始，直到下一個(gè)首指令(不含)或者中間代碼的結(jié)尾指令之間的所有指令基本塊劃分算法i=m

1;j=n;v=a[n];while(1){

do

i=i+1;while(a[i]<v);

do

j=j

1;while

(a[j]>v);

if

(i>=j)break;

x=a[i];a[i]=a[j];a[j]=x;} x=a[i];a[i]=a[n];a[n]=x;例(1)i=m

1(2)j=n(3)t1=4*n

(4)v=a[t1](5)i=i+1(6)t2=4*i

(7)t3=a[t2](8)

ift3>v

goto(5)(9)j=j

1(10)t4=4*j

(11)t5=a[t4] (12)if

t5>v

goto(9)(13)if

i>=j

goto(23)(14)t6=4*i(15)x=a[t6](16)t7=4*i

(17)t8=4*j(18)t9=a[t8](19)a[t7]=t9(20)t10=4*j(21)a[t10]=x(22)

goto(5)(23)t11=4*i(24)x=a[t11](25)t12=4*i(26)t13

=4*n(27)t14

=a[t13](28)a[t12]=t14(29)t15=4*n

(30)a[t15]=x

B1B2B3B4B5B6流圖是一種表示中間代碼的方法流圖中的結(jié)點(diǎn)表示基本塊流圖中的邊指明了哪些基本塊可能緊隨一個(gè)基本塊之后運(yùn)行流圖(FlowGraphs)流圖的結(jié)點(diǎn)是一些基本塊從基本塊B到基本塊C之間有一條邊當(dāng)且僅當(dāng)基本塊C的第一個(gè)指令可能緊跟在B的最后一條指令之后執(zhí)行有兩種方式可以確認(rèn)這樣的邊：有一個(gè)從B的結(jié)尾跳轉(zhuǎn)到C的開頭的條件或無條件跳轉(zhuǎn)語句按照原來的三地址語句序列中的順序，C緊跟在之B后，且B的結(jié)尾不存在無條件跳轉(zhuǎn)語句此時(shí)稱B是C的前驅(qū)(predecessor)，C是B的后繼(successor)流圖的構(gòu)造B5B6B4B3B2B1(1)i=m

1(2)j=n(3)t1=4*n

(4)v=a[t1](5)i=i+1(6)t2=4*i

(7)t3=a[t2](8)

ift3>v

goto(5)(9)j=j

1(10)t4=4*j

(11)t5=a[t4] (12)if

t5>v

goto(9)(13)if

i>=j

goto(23)(14)t6=4*i(15)x=a[t6](16)t7=4*i

(17)t8=4*j(18)t9=a[t8](19)a[t7]=t9(20)t10=4*j(21)a[t10]=x(22)

goto(5)(23)t11=4*i(24)x=a[t11](25)t12=4*i(26)t13

=4*n(27)t14

=a[t13](28)a[t12]=t14(29)t15=4*n

(30)a[t15]=x

B1B2B3B4B5B6例i=m

1j=nt1=4*

nv=a[t1]i=i+1t2=4*

it3=a[t2]ift3

<v

goto

B2B1B2j=j

1t4=4*

jt5=a[t4]if

t5>v

goto

B3if

i>=jgoto

B6B4B3B5B6t6=4*

ix=a[t6]t7=4*

it8

=4*

jt9=a[t8]a[t7]=t9t10=4*

ja[t10]=xgoto

B2t11=4*

ix=a[t11]t12

=4*

i

t13=4*nt14=a[t13]a[t12]=t14t15=4*

n

a[t15]=x

8.1流圖8.2優(yōu)化的分類8.3基本塊的優(yōu)化8.4數(shù)據(jù)流分析8.5流圖中的循環(huán)8.6全局優(yōu)化提綱機(jī)器無關(guān)優(yōu)化針對(duì)中間代碼機(jī)器相關(guān)優(yōu)化針對(duì)機(jī)器代碼局部代碼優(yōu)化單個(gè)基本塊范圍內(nèi)的優(yōu)化全局代碼優(yōu)化面向多個(gè)基本塊的優(yōu)化8.2優(yōu)化的分類刪除公共子表達(dá)式刪除無用代碼常量合并代碼移動(dòng)強(qiáng)度削弱刪除歸納變量常用的優(yōu)化方法公共子表達(dá)式如果表達(dá)式xopy先前已被計(jì)算過，并且從先前的計(jì)算到現(xiàn)在，xopy中變量的值沒有改變，那么xopy的這次出現(xiàn)就稱為公共子表達(dá)式(commonsubexpression)①刪除公共子表達(dá)式t6=4*

ix=a[t6]t7=4*

it8

=4*

jt9=a[t8]a[t7]=t9t10=4*

ja[t10]=xgoto

B2t6=4*

ix=a[t6]t8

=4*

jt9=a[t8]a[t6]=t9a[t8]=xgotoB2i=m

1j=nt1=4*

nv=a[t1]i=i+1t2=4*

it3=a[t2]ift3

<v

goto

B2B1B2j=j

1t4=4*

jt5=a[t4]if

t5>v

goto

B3if

i>=jgoto

B6B4B3B5B6t11=4*

ix=a[t11]t12

=4*

i

t13=4*nt14=a[t13]a[t12]=t14t15=4*

n

a[t15]=x

局部公共子表達(dá)式例t6=4*

ix=a[t6]t8

=4*

jt9=a[t8]a[t6]=t9a[t8]=xgotoB2t6=4*

ix=a[t6]t8

=4*

jt9=a[t8]a[t6]=t9a[t8]=xgotoB2i=m

1j=nt1=4*

nv=a[t1]i=i+1t2=4*

it3=a[t2]ift3

<v

goto

B2B1B2j=j

1t4=4*

jt5=a[t4]if

t5>v

goto

B3if

i>=jgoto

B6B4B3B5B6t11=4*

ix=a[t11]t12

=4*

i

t13=4*nt14=a[t13]a[t12]=t14t15=4*

n

a[t15]=x

例x=a[t2]t9=a[t4]a[t2]=t9a[t4]=xgotoB2t6=4*

ix=a[t6]t8

=4*

jt9=a[t8]a[t6]=t9a[t8]=xgotoB2i=m

1j=nt1=4*

nv=a[t1]i=i+1t2=4*

it3=a[t2]ift3

<v

goto

B2B1B2j=j

1t4=4*

jt5=a[t4]if

t5>v

goto

B3if

i>=jgoto

B6B4B3B5B6t11=4*

ix=a[t11]t12

=4*

i

t13=4*nt14=a[t13]a[t12]=t14t15=4*

n

a[t15]=x

全局公共子表達(dá)式例x=a[t2]t9=a[t4]a[t2]=t9a[t4]=xgotoB2x=a[t2]t9=a[t4]a[t2]=t9a[t4]=xgotoB2i=m

1j=nt1=4*

nv=a[t1]i=i+1t2=4*

it3=a[t2]ift3

<v

goto

B2B1B2j=j

1t4=4*

jt5=a[t4]if

t5>v

goto

B3if

i>=jgoto

B6B4B3B5B6t11=4*

ix=a[t11]t12

=4*

i

t13=4*nt14

=a[t13]a[t12]=t14t15=4*

n

a[t15]=x

例x=t3a[t2]=

t5a[t4]=xgotoB2x=a[t2]t9=a[t4]a[t2]=t9a[t4]=xgotoB2i=m

1j=nt1=4*

nv=a[t1]i=i+1t2=4*

it3=a[t2]ift3

<v

goto

B2B1B2j=j

1t4=4*

jt5=a[t4]if

t5>v

goto

B3if

i>=jgoto

B6B4B3B5B6t11=4*

ix=a[t11]t12

=4*

i

t13=4*nt14=a[t13]a[t12]=t14t15=4*

n

a[t15]=x

例x=t3a[t2]=

t5a[t4]=xgotoB2t11=4*

ix=a[t11]t12

=4*

i

t13=4*nt14

=a[t13]a[t12]=t14t15=4*

n

a[t15]=x

x=t3a[t2]=t5a[t4]=xgotoB2i=m

1j=nt1=4*

nv=a[t1]i=i+1t2=4*

it3=a[t2]ift3

<v

goto

B2B1B2j=j

1t4=4*

jt5=a[t4]if

t5>v

goto

B3if

i>=jgoto

B6B4B3B5B6例t11=4*

ix=a[t11]t12

=4*

i

t13=4*nt14

=a[t13]a[t12]=t14t15=4*

n

a[t15]=x

x=t3a[t2]=t5a[t4]=xgotoB2i=m

1j=nt1=4*

nv=a[t1]i=i+1t2=4*

it3=a[t2]ift3

<v

goto

B2B1B2j=j

1t4=4*

jt5=a[t4]if

t5>v

goto

B3if

i>=jgoto

B6B4B3B5x=a[t2]t14

=a[t1]a[t2]=t14a[t1]=x

B6例x=a[t2]t14

=a[t1]a[t2]=t14a[t1]=x

x=t3a[t2]=t5a[t4]=xgotoB2i=m

1j=nt1=4*

nv=a[t1]i=i+1t2=4*

it3=a[t2]ift3

<v

goto

B2B1B2j=j

1t4=4*

jt5=a[t4]if

t5>v

goto

B3if

i>=jgoto

B6B4B3B5x=a[t2]t14

=a[t1]a[t2]=t14a[t1]=x

B6例x=a[t2]t14

=a[t1]a[t2]=t14a[t1]=x

把a(bǔ)[t1]作為公共子表達(dá)式是不穩(wěn)妥的，因?yàn)榭刂齐x開B1

進(jìn)入B6之前可能進(jìn)入B5，而B5有對(duì)a的賦值x=t3a[t2]=t5a[t4]=xgotoB2i=m

1j=nt1=4*

nv=a[t1]i=i+1t2=4*

it3=a[t2]ift3

<v

goto

B2B1B2j=j

1t4=4*

jt5=a[t4]if

t5>v

goto

B3if

i>=jgoto

B6B4B3B5全局公共子表達(dá)式a[t1]能否作為公共子表達(dá)式？B6例x=a[t2]t14

=a[t1]a[t2]=t14a[t1]=x

x=t3a[t2]=t5a[t4]=xgotoB2i=m

1j=nt1=4*

nv=a[t1]i=i+1t2=4*

it3=a[t2]ift3

<v

goto

B2B1B2j=j

1t4=4*

jt5=a[t4]if

t5>v

goto

B3if

i>=jgoto

B6B4B3B5x=t3t14

=a[t1]a[t2]=t14a[t1]=x

B6例x=t3t14

=a[t1]a[t2]=t14a[t1]=x

x=t3a[t2]=t5a[t4]=xgotoB2i=m

1j=nt1=4*

nv=a[t1]i=i+1t2=4*

it3=a[t2]ift3

<v

goto

B2B1B2j=j

1t4=4*

jt5=a[t4]if

t5>v

goto

B3if

i>=jgoto

B6B4B3B5x=t3t14

=a[t1]a[t2]=t14a[t1]=x

B6例x=t3t14

=a[t1]a[t2]=t14a[t1]=x

x=t3a[t2]=t5a[t4]=xgotoB2i=m

1j=nt1=4*

nv=a[t1]i=i+1t2=4*

it3=a[t2]ift3

<v

goto

B2B1B2j=j

1t4=4*

jt5=a[t4]if

t5>v

goto

B3if

i>=jgoto

B6B4B3B5關(guān)鍵問題：如何自動(dòng)識(shí)別公共子表達(dá)式B6例復(fù)制傳播常用的公共子表達(dá)式消除算法和其它一些優(yōu)化算法會(huì)引入一些復(fù)制語句(形如x=y的賦值語句)②刪除無用代碼x=t3a[t2]=t5a[t4]=xgotoB2B5x=t3a[t2]=t5a[t4]=t3gotoB2復(fù)制傳播常用的公共子表達(dá)式消除算法和其它一些優(yōu)化算法會(huì)引入一些復(fù)制語句(形如x=y的賦值語句)

復(fù)制傳播：在復(fù)制語句x=y之后盡可能地用y代替x例x=t3t14

=a[t1]a[t2]=t14a[t1]=x

B6x=t3t14

=a[t1]a[t2]=t14a[t1]=t3

②刪除無用代碼復(fù)制傳播常用的公共子表達(dá)式消除算法和其它一些優(yōu)化算法會(huì)引入一些復(fù)制語句(形如x=y的賦值語句)

復(fù)制傳播：在復(fù)制語句x=y之后盡可能地用y代替x復(fù)制傳播給刪除無用代碼帶來機(jī)會(huì)

無用代碼(死代碼Dead-Code

)

：其計(jì)算結(jié)果永遠(yuǎn)不會(huì)被使用的語句②刪除無用代碼x=t3t14

=a[t1]a[t2]=t14a[t1]=t3

x=t3a[t2]=t5a[t4]=t3gotoB2i=m

1j=nt1=4*

nv=a[t1]i=i+1t2=4*

it3=a[t2]ift3

<v

goto

B2B1B2j=j

1t4=4*

jt5=a[t4]if

t5>v

goto

B3if

i>=jgoto

B6B4B3B5B6a[t2]=t5a[t4]=t3gotoB2t14

=a[t1]a[t2]=t14a[t1]=t3

程序員不大可能有意引入無用代碼，無用代碼通常是因?yàn)榍懊鎴?zhí)行過的某些轉(zhuǎn)換而造成的如何自動(dòng)識(shí)別無用代碼？例t6=4*

ix=a[t6]t7=4*

it8

=4*

jt9=a[t8]a[t7]=t9t10=4*

ja[t10]=xgoto

B2i=m

1j=nt1=4*

nv=a[t1]i=i+1t2=4*

it3=a[t2]ift3

<v

goto

B2B1B2j=j

1t4=4*

jt5=a[t4]if

t5>v

goto

B3if

i>=jgoto

B6B4B3B5B6t11=4*

ix=a[t11]t12

=4*

i

t13=4*nt14=a[t13]a[t12]=t14t15=4*

n

a[t15]=x

a[t2]=t5a[t4]=t3gotoB2t14

=a[t1]a[t2]=t14a[t1]=t3

例如果在編譯時(shí)刻推導(dǎo)出一個(gè)表達(dá)式的值是常量，就可以使用該常量來替代這個(gè)表達(dá)式。該技術(shù)被稱為常量合并例：

l=2*3.14*rt1=2*3.14t2

=6.28*rl=t2t1=2*3.14t2=t1*r

l=t2

③常量合并(ConstantFolding)代碼移動(dòng)這個(gè)轉(zhuǎn)換處理的是那些不管循環(huán)執(zhí)行多少次都得到相同結(jié)果的表達(dá)式(即循環(huán)不變計(jì)算，loop-invariantcomputation)，在進(jìn)入循環(huán)之前就對(duì)它們求值④代碼移動(dòng)(CodeMotion)

優(yōu)化后程序C=1/360*pi*r*r;for(n=10;n<360;n++){ S=C*n; printf(“Areais%f”,S);}

原始程序for(n=10;n<360;n++){S=1/360*pi*r*r*n; printf(“Areais%f”,S);}(1)n=1 (8)t5

=t4*n

(2)ifn>360goto(21) (9)S=t5

(3)goto(4) … …(4)t1

=1/360 (18)t9=n+1(5)t2=t1*pi (19)n=t9

(6)t3=t2

*r (20)goto(4)(7)t4=t3*r

(21)如何自動(dòng)識(shí)別循環(huán)不變計(jì)算？循環(huán)不變計(jì)算例對(duì)于多重嵌套的循環(huán)，循環(huán)不變計(jì)算是相對(duì)于某個(gè)循環(huán)而言的。可能對(duì)于更加外層的循環(huán)，它就不是循環(huán)不變計(jì)算例： for(i=1;i<10;i++)

for(n=1;n<360/(5*i);n++) {S=(5*i)/360*pi*r*r*n;...}循環(huán)不變計(jì)算的相對(duì)性強(qiáng)度削弱用較快的操作代替較慢的操作，如用加代替乘例2*x

或2.0*x

x+xx/2

x*0.5x2

x*xanxn+an-1xn-1+…+a1x+a0

((…(anx+an-1)x+an-2)…)x+a1)x+a0⑤強(qiáng)度削弱(StrengthReduction)歸納變量對(duì)于一個(gè)變量x，如果存在一個(gè)正的或負(fù)的常數(shù)c使得每次x被賦值時(shí)它的值總增加c，那么x就稱為歸納變量(InductionVariable)循環(huán)中的強(qiáng)度削弱歸納變量可以通過在每次循環(huán)迭代中進(jìn)行一次簡(jiǎn)單的增量運(yùn)算(加法或減法)來計(jì)算i=m

1j=nt1=4*nv=a[t1]i=i+1t2=4*it3=a[t2]ift3

<vgotoB2B1B2j=j

1t4

=4*jt5=a[t4]ift5>vgotoB3ifi>=jgotoB6B4B3B6B5例i=m

1j=nt1=4*nv=a[t1]t2=4*it4

=4*ji=i+1t2=t2

+4t3=a[t2]ift3

<vgotoB2B1B2j=j

1t4=t4-4t5=a[t4]ift5>vgotoB3ifi>=jgotoB6B4B3B6B5i=m

1j=nt1=4*nv=a[t1]i=i+1t2=4*it3=a[t2]ift3

<vgotoB2B1B2j=j

1t4

=4*jt5=a[t4]ift5>vgotoB3ifi>=jgotoB6B4B3B6B5例在沿著循環(huán)運(yùn)行時(shí)，如果有一組歸納變量的值的變化保持步調(diào)一致，常?？梢詫⑦@組變量刪除為只剩一個(gè)i=m

1j=nt1=4*nv=a[t1]t2=4*it4

=4*ji=i+1t2=t2

+4t3=a[t2]ift3

<vgotoB2B1B2j=j

1t4=t4-4t5=a[t4]ift5>vgotoB3B4B3B6B5ifi>=jgotoB6⑥刪除歸納變量i=m

1j=nt1=4*nv=a[t1]t2=4*it4

=4*jt2=t2

+4t3=a[t2]ift3

<vgotoB2B1B2t4=t4-4t5=a[t4]ift5>vgotoB3if

t2>=t4

gotoB6B4B3B6B5i=m

1j=nt1=4*nv=a[t1]t2=4*it4

=4*ji=i+1t2=t2

+4t3=a[t2]ift3

<vgotoB2B1B2j=j

1t4=t4-4t5=a[t4]ift5>vgotoB3B4B3B6B5ifi>=jgotoB6⑥刪除歸納變量8.1流圖8.2優(yōu)化的分類8.3基本塊的優(yōu)化8.4數(shù)據(jù)流分析8.5流圖中的循環(huán)8.6全局優(yōu)化提綱很多重要的局部?jī)?yōu)化技術(shù)首先把一個(gè)基本塊轉(zhuǎn)換成為一個(gè)無環(huán)有向圖(directedacyclicgraph，DAG)8.3基本塊的優(yōu)化基本塊的DAG表示例

a=b+c

b=a-d

c=b+c

d=a-d基本塊中的每個(gè)語句s都對(duì)應(yīng)一個(gè)內(nèi)部結(jié)點(diǎn)N結(jié)點(diǎn)N的標(biāo)號(hào)是s中的運(yùn)算符；同時(shí)還有一個(gè)定值變量表被關(guān)聯(lián)到N，表示s是在此基本塊內(nèi)最晚對(duì)表中變量進(jìn)行定值的語句N的子結(jié)點(diǎn)是基本塊中在s之前、最后一個(gè)對(duì)s所使用的某個(gè)運(yùn)算分量進(jìn)行定值的語句對(duì)應(yīng)的結(jié)點(diǎn)。如果s的某個(gè)運(yùn)算分量在基本塊內(nèi)沒有在s之前被定值，則這個(gè)運(yùn)算分量對(duì)應(yīng)的子結(jié)點(diǎn)就是代表該運(yùn)算分量初始值的葉結(jié)點(diǎn)(為區(qū)別起見，葉節(jié)點(diǎn)的定值變量表中的變量加上下腳標(biāo)0)在為語句x=y+z構(gòu)造結(jié)點(diǎn)N的時(shí)候，如果x已經(jīng)在某結(jié)點(diǎn)M的定值變量表中，則從M的定值變量表中刪除變量x+ac對(duì)于形如x=y+z的三地址指令，如果已經(jīng)有一個(gè)結(jié)點(diǎn)表示y+z，就不往DAG中增加新的結(jié)點(diǎn)，而是給已經(jīng)存在的結(jié)點(diǎn)附加定值變量xb-+db0c0d0從一個(gè)DAG上刪除所有沒有附加活躍變量（活躍變量是指其值可能會(huì)在以后被使用的變量）的根結(jié)點(diǎn)(即沒有父結(jié)點(diǎn)的結(jié)點(diǎn))。重復(fù)應(yīng)用這樣的處理過程就可以從DAG中消除所有對(duì)應(yīng)于無用代碼的結(jié)點(diǎn)例+b0c0-++d0ecba××假設(shè)a和b是活躍變量，但c和e不是基于基本塊的DAG刪除無用代碼例

x=a[i]a[j]=yz=a[i]對(duì)于形如a[j]=y的三地址指令，創(chuàng)建一個(gè)運(yùn)算符為“[]=”的結(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)有3個(gè)子結(jié)點(diǎn)，分別表示a、j和y該結(jié)點(diǎn)沒有定值變量表該結(jié)點(diǎn)的創(chuàng)建將殺死所有已經(jīng)建立的、其值依賴于a的結(jié)點(diǎn)一個(gè)被殺死的結(jié)點(diǎn)不能再獲得任何定值變量，也就是說，它不可能成為一個(gè)公共子表達(dá)式在構(gòu)造DAG時(shí)，如何防止系統(tǒng)將a[i]誤判為公共子表達(dá)式？killedz=[]i0a0x=[]j0y0[]=數(shù)組下標(biāo)指令的表示b=12+ax=b[i]b[j]=ykilleda012b+i0=[]xj0y0[]=例2基本塊DAG的構(gòu)造算法輸入：基本塊 輸出：基本塊的DAG注釋node(x)返回最新建立的與x相關(guān)聯(lián)的結(jié)點(diǎn)假設(shè)當(dāng)前三地址語句是如下三種形式之一(i)

x=yopz(ii)

x=opy(iii)

x=y基本塊DAG的構(gòu)造依次對(duì)基本塊中的每個(gè)語句x=yopz執(zhí)行如下步驟1.如果node(y)沒有定義，則創(chuàng)建一個(gè)標(biāo)號(hào)為y0的葉節(jié)點(diǎn)，并令node(y)為該節(jié)點(diǎn)。如果是(i)型，并且node(z)沒有定義，則創(chuàng)建一個(gè)標(biāo)號(hào)為z的葉節(jié)點(diǎn)，并令node(z)為該葉節(jié)點(diǎn)。為z建立葉子節(jié)點(diǎn)。方法2.①如果語句為(i)型，確定是否有一個(gè)標(biāo)號(hào)為op，且其左右子節(jié)點(diǎn)分別為node(y)和node(z)的節(jié)點(diǎn)。如果沒有，就創(chuàng)建一個(gè)這樣的節(jié)點(diǎn)。無論是哪種情況，令n是所找到或創(chuàng)建的節(jié)點(diǎn)。②如果語句為(ii)型，確定是否有一個(gè)標(biāo)號(hào)為op，且只有一個(gè)子節(jié)點(diǎn)node(y)的節(jié)點(diǎn)。如果沒有，就創(chuàng)建一個(gè)這樣的節(jié)點(diǎn)，并令n是所找到或創(chuàng)建的節(jié)點(diǎn)。③如果語句為(iii)型，令n為node(y)。處理(i)型四元式的時(shí)候，如果op是滿足交換率的運(yùn)算符，可以允許其左右節(jié)點(diǎn)互換

3.如果node(x)沒有定義，則將node(x)設(shè)置為n,并把x加入到n的定值變量表中；如果node(x)有定義，從node(x)的定值變量表中刪除變量x，并把x加入到n的定值變量表中，并將node(x)設(shè)置為n。

(1)t1=4*i(2)t2=a[t1](3)t3=4*i(4)t4=b[t3]

(5)t5=t2*t4(6)t6=prod+t5(7)prod=t6

(8)t7=i+1(9)i=t7 (10)ifi<=20goto(1)a04i0b0prod0120t6t5t2t4t1t7(1)t3prodi+*=[]=[]*<=+例確定哪些標(biāo)識(shí)符的值在該基本塊中被引用過在DAG中創(chuàng)建了葉結(jié)點(diǎn)的那些標(biāo)識(shí)符確定哪些語句計(jì)算的值可以在基本塊外被引用在DAG構(gòu)造過程中為語句s（該語句為變量x定值）創(chuàng)建的節(jié)點(diǎn)N，在DAG構(gòu)造結(jié)束時(shí)x仍然是N的定值變量根據(jù)基本塊的DAG可以獲得一些非常有用的信息對(duì)每個(gè)具有若干定值變量的節(jié)點(diǎn)，構(gòu)造一個(gè)三地址語句來計(jì)算其中某個(gè)變量的值傾向于把計(jì)算得到的結(jié)果賦給一個(gè)在基本塊出口處活躍的變量(如果沒有全局活躍變量的信息作為依據(jù)，就要假設(shè)所有變量都在基本塊出口處活躍，但是不包含編譯器為處理表達(dá)式而生成的臨時(shí)變量)如果節(jié)點(diǎn)有多個(gè)附加的活躍變量，就必須引入復(fù)制語句，以便給每一個(gè)變量都賦予正確的值從DAG到基本塊的重組D給定一個(gè)基本塊B=3D=A+C

E=A*C

F=E+D

G=B*F

H=A+C

I=A*C

J=H+I

K=B*5L=K+J

M=L

假設(shè)：僅變量L在基本塊出口之后活躍+*E+F*G*K=15+LHIJM=B=35A0C03例D假設(shè)：僅變量L在基本塊出口之后活躍+*E+F*G*K=15+LHIJM=B=35A0C03D=A+C

E=A*CF=E+D

L=15+F

給定一個(gè)基本塊B=3D=A+C

E=A*C

F=E+D

G=B*F

H=A+C

I=A*C

J=H+I

K=B*5L=K+J

M=L

例8.1流圖8.2優(yōu)化的分類8.3基本塊的優(yōu)化8.4數(shù)據(jù)流分析8.5流圖中的循環(huán)8.6全局優(yōu)化提綱數(shù)據(jù)流分析一組用來獲取程序執(zhí)行路徑上的數(shù)據(jù)流信息的技術(shù)數(shù)據(jù)流分析應(yīng)用到達(dá)-定值分析

(Reaching-DefinitionAnalysis)活躍變量分析

(Live-VariableAnalysis)可用表達(dá)式分析

(Available-ExpressionAnalysis)在每一種數(shù)據(jù)流分析應(yīng)用中，都會(huì)把每個(gè)程序點(diǎn)和一個(gè)數(shù)據(jù)流值關(guān)聯(lián)起來8.4數(shù)據(jù)流分析(data-flowanalysis)

語句的數(shù)據(jù)流模式

IN[s]:

語句s之前的數(shù)據(jù)流值

OUT[s]: 語句s之后的數(shù)據(jù)流值

fs：語句s的傳遞函數(shù)(transferfunction)一個(gè)賦值語句s之前和之后的數(shù)據(jù)流值的關(guān)系傳遞函數(shù)的兩種風(fēng)格信息沿執(zhí)行路徑前向傳播(前向數(shù)據(jù)流問題)OUT[s]=fs(IN[s])信息沿執(zhí)行路徑逆向傳播(逆向數(shù)據(jù)流問題)IN[s]=fs(OUT[s])數(shù)據(jù)流分析模式

語句的數(shù)據(jù)流模式

IN[s]:

語句s之前的數(shù)據(jù)流值

OUT[s]: 語句s之后的數(shù)據(jù)流值

fs：語句s的傳遞函數(shù)(transferfunction)一個(gè)賦值語句s之前和之后的數(shù)據(jù)流值的關(guān)系基本塊中相鄰兩個(gè)語句之間的數(shù)據(jù)流值的關(guān)系設(shè)基本塊B由語句s1,s2,…,sn

順序組成，則

IN[si+1]=OUT[si]i=1,2,…,n-1數(shù)據(jù)流分析模式

IN[B]:

緊靠基本塊B之前的數(shù)據(jù)流值

OUT[B]:緊隨基本塊B之后的數(shù)據(jù)流值設(shè)基本塊B由語句s1,s2,…,sn

順序組成，則

IN[B]=IN[s1]

OUT[B]=OUT[sn]

fB：基本塊B的傳遞函數(shù)前向數(shù)據(jù)流問題：OUT[B]

=fB(IN[B])fB=fsn·…·fs2·fs1逆向數(shù)據(jù)流問題：IN[B]

=fB(OUT[B])fB=fs1·fs2·…·fsn

OUT[B]=OUT[sn]=fsn(IN[sn])=fsn(OUT[sn-1])=fsn·fs(n-1)(IN[sn-1])=fsn·fs(n-1)(OUT[sn-2])……=fsn·fs(n-1)·…·fs2(OUT[s1])=fsn·fs(n-1)·…

·fs2·fs1(IN[s1])=

fsn·fs(n-1)·…

·fs2·fs1(IN[B])基本塊上的數(shù)據(jù)流模式定值

(Definition)變量x的定值是(可能)將一個(gè)值賦給x的語句到達(dá)定值(ReachingDefinition)如果存在一條從緊跟在定值d后面的點(diǎn)到達(dá)某一程序點(diǎn)p的路徑，而且在此路徑上d沒有被“殺死”(如果在此路徑上有對(duì)變量x的其它定值d′，則稱變量x被這個(gè)定值d′“殺死”了)，則稱定值d到達(dá)程序點(diǎn)p直觀地講，如果某個(gè)變量x的一個(gè)定值d到達(dá)點(diǎn)p，在點(diǎn)p處使用的x的值可能就是由d最后賦予的8.4.1到達(dá)定值分析假設(shè)每個(gè)控制流圖都有兩個(gè)空基本塊，分別是表示流圖的開始點(diǎn)的ENTRY結(jié)點(diǎn)和結(jié)束點(diǎn)的EXIT結(jié)點(diǎn)（所有離開該圖的控制流都流向它）ENTRYd1:i=m-1d2:j=nd3:a=u1B1B2d4:i=i+1d5:j=j-1d6:a=u2B4B3d7:i=u3EXITIN[B]B2B3B4d1d2d3d4d5d6d7√√√×√√√××√√√√×××√√√√×例：可以到達(dá)各基本塊的入口處的定值循環(huán)不變計(jì)算的檢測(cè)如果循環(huán)中含有賦值x=y+z

，而y和z所有可能的定值都在循環(huán)外面(包括y或z是常數(shù)的特殊情況)，那么y+z就是循環(huán)不變計(jì)算到達(dá)定值分析的主要用途常數(shù)合并如果對(duì)變量x的某次使用只有一個(gè)定值可以到達(dá)，并且該定值把一個(gè)常量賦給x，那么可以簡(jiǎn)單地把x替換為該常量循環(huán)不變計(jì)算的檢測(cè)到達(dá)定值分析的主要用途判定變量x在p點(diǎn)上是否未經(jīng)定值就被引用常數(shù)合并循環(huán)不變計(jì)算的檢測(cè)到達(dá)定值分析的主要用途定值d:u=v+w該語句“生成”了一個(gè)對(duì)變量u的定值d，并“殺死”了程序中其它對(duì)u的定值這里，“+”代表一個(gè)一般性的二元運(yùn)算符“生成”與“殺死”定值fd：定值d:u=v+w的傳遞函數(shù)fd(x)=gend∪(x-killd)gend：由語句d生成的定值的集合

gend=xxnfbdrkilld：由語句d殺死的定值的集合（程序中所有其它對(duì)u的定值）生成-殺死形式到達(dá)定值的傳遞函數(shù)到達(dá)定值的傳遞函數(shù)fd：定值d:u=v+w的傳遞函數(shù)fd(x)=gend∪(x-killd)fB：基本塊B的傳遞函數(shù)fB(x)=genB∪(x-killB)

killB=kill1∪kill2∪

…∪killn被基本塊B中各個(gè)語句殺死的定值的集合genB=genn∪(genn-1–killn)∪(genn-2–killn-1–killn)∪

…∪(gen1–kill2–kill3–…–killn)基本塊中沒有被塊中各語句“殺死”的定值的集合genB1={d1,d2,d3}killB1={d4,d5,d6,d7

}genB2={d4,d5

}killB2={d1,d2,d7

}genB3={d6

}killB3={d3

}genB4={d7

}killB4={d1,d4

}ENTRYd1:i=m-1d2:j=nd3:a=u1B1B2d4:i=i+1d5:j=j-1d6:a=u2B4B3d7:i=u3EXIT例：各基本塊B的genB和killBIN[B]：到達(dá)流圖中基本塊B的入口處的定值的集合

OUT[B]：到達(dá)流圖中基本塊B的出口處的定值的集合方程OUT[ENRTY]=ΦOUT[B]=fB(IN[B])

(B≠ENTRY)fB(x)=genB∪(x-killB)

IN[B]=∪P是B的一個(gè)前驅(qū)OUT[P](B≠ENTRY)

genB和killB的值可以直接從流圖計(jì)算出來，因此在方程中作為已知量OUT[B]=genB∪(IN[B]-killB)到達(dá)定值的數(shù)據(jù)流方程OUT[ENTRY]=Φ;for(除ENTRY之外的每個(gè)基本塊B)OUT[B]=Φ;while(某個(gè)OUT值發(fā)生了改變) for(除ENTRY之外的每個(gè)基本塊B){

IN[B]=∪P是B的一個(gè)前驅(qū)OUT[P];

OUT[B]=genB∪(IN[B]-killB) }輸入：流圖G，其中每個(gè)基本塊B的genB

和killB

都已計(jì)算出來輸出：

IN[B]和OUT[B]方法：

計(jì)算到達(dá)定值的迭代算法IN[B]3OUT[B]3IN[B]2OUT[B]2IN[B]1OUT[B]1BOUT[B]0B10000000B20000000B30000000B40000000EXIT0000000OUT[ENTRY]=Φ;for(除ENTRY之外的每個(gè)基本塊B)OUT[B]=Φ;while(某個(gè)OUT值發(fā)生了改變)for(除ENTRY之外的每個(gè)基本塊B){IN[B]=∪P是B的一個(gè)前驅(qū)OUT[P];OUT[B]=genB∪(IN[B]-killB)}genB1={d1,d2,d3}killB1={d4,d5,d6,d7

}genB2={d4,d5

}killB2={d1,d2,d7

}genB3={d6

}killB3={d3

}genB4={d7

}killB4={d1,d4

}ENTRYB1B2B3EXITB4000000011100001110000001110000111000001110001111000101110010111001011100000001110000111011100111100011110000111000111100010111001011100101110000000111000011101110011110001111000011100011110001011100101110010111例genB1={d1,d2,d3}killB1={d4,d5,d6,d7

}genB2={d4,d5

}killB2={d1,d2,d7

}genB3={d6

}killB3={d3

}genB4={d7

}killB4={d1,d4

}BOUT[B]0B10000000B20000000B30000000B40000000EXIT0000000ENTRYB1B2B3EXITB4IN[B]2OUT[B]2IN[B]1OUT[B]100000001110000111000000111000011100000111000111100010111001011100101110000000111000011101110011110001111000011100011110001011100101110010111IN[B]3OUT[B]30000000111000011101110011110001111000011100011110001011100101110010111IN[B]B2B3B4d1√××d2√××d3√√√d4×√√d5√√√d6√√√d7√××例引用-定值鏈

(Use-DefinitionChains)如果塊B中變量a的引用之前有a的定值，

那么只有a的最后一次定值會(huì)在該引用的

ud鏈中如果塊B中變量a的引用之前沒有a的定值，

那么a的這次引用的ud鏈就是IN[B]中a的

定值的集合······=···a·········d:a=

·········=···a······引用-定值鏈(ud-chains)

是一個(gè)列表，對(duì)于變量的每一次引用，到達(dá)該引用的所有定值都在該列表中通過變量x在引用u處的ud鏈，可以判斷x是否是循環(huán)不變計(jì)算如果x的所有可能的定值都在循環(huán)外面，那么，x就是循環(huán)不變計(jì)算活躍變量對(duì)于變量x和程序點(diǎn)p，如果在流圖中沿著從p開始的某條路徑會(huì)引用變量x在p點(diǎn)的值，則稱變量x在點(diǎn)p是活躍(live)的，否則稱變量x在點(diǎn)p不活躍(dead)8.4.2活躍變量分析OUT[B]B1B2B3B4aijmnu1u2u3×××××√×√√√√√××××××××××××√√√√√√√√ENTRYd1:i=m-1d2:j=nd3:a=u1B1B2d4:i=i+1d5:j=j-1d6:a=u2B4B3d7:i=u3EXIT例：各基本塊的出口處的活躍變量刪除無用賦值

無用賦值：如果x在點(diǎn)p的定值在基本塊內(nèi)所有后繼點(diǎn)都不被引用，且在基本塊出口之后又是不活躍的，那么x在點(diǎn)p的定值就是無用的為基本塊分配寄存器如果所有寄存器都被占用，并且還需要申請(qǐng)一個(gè)寄存器，則應(yīng)該考慮使用已經(jīng)存放了死亡值的寄存器，因?yàn)檫@個(gè)值不需要保存到內(nèi)存如果一個(gè)值在基本塊結(jié)尾處是死的就不必在結(jié)尾處保存這個(gè)值活躍變量信息的主要用途逆向數(shù)據(jù)流問題

IN[B]

=fB(OUT[B]）fB(x)=useB∪(x-defB)defB：在基本塊B中定值，但是定值前在B中沒有被引用的變量的集合useB：在基本塊B中引用，但是引用前在B中沒有被定值的變量集合活躍變量的傳遞函數(shù)useB1={m,n,u1

}defB1

={i,j,a}useB2={i,j}defB2=ΦuseB3={u2

}defB3={a}useB4={u3

}defB4={i}ENTRYd1:i=m-1d2:j=nd3:a=u1B1B2d4:i=i+1d5:j=j-1d6:a=u2B4B3d7:i=u3EXIT例：各基本塊B的useB

和defB

IN[B]：在基本塊B的入口處的活躍變量集合

OUT[B]：在基本塊B的出口處的活躍變量集合方程

IN[EXIT]=Φ

IN[B]=fB(OUT[B]）

(B≠EXIT)fB(x)=useB∪(x-defB)OUT[B]=∪S是B的一個(gè)后繼

IN[S](B≠EXIT)useB和defB的值可以直接從流圖計(jì)算出來，因此在方程中作為已知量IN

[B]=useB∪(OUT[B]-defB)活躍變量數(shù)據(jù)流方程S1…S2SnB

IN[EXIT]=Φ;for

(除EXIT之外的每個(gè)基本塊B)IN[B]=Φ;while(某個(gè)IN值發(fā)生了改變) for

(除EXIT之外的每個(gè)基本塊B){

OUT[B]=∪S是B的一個(gè)后繼

IN[S];

IN[B]=useB

∪(OUT[B]-defB

); }輸入：流圖G，其中每個(gè)基本塊B的useB和defB都已計(jì)算出來輸出：

IN[B]和OUT[B]方法：

計(jì)算活躍變量的迭代算法OUT[B]1IN[B]1B4B3B2B1useB1={m,n,u1

}defB1={i,j,a}useB2={i,j}defB2=ΦuseB3={u2

}defB3={a}useB4={u3

}defB4={i}ENTRYB1B2B3EXITB4IN[EXIT]=Φ;for

(除EXIT之外的每個(gè)基本塊B)IN[B]=Φ;while(某個(gè)IN值發(fā)生了改變) for

(除EXIT之外的每個(gè)基本塊B){

OUT[B]=∪S是B的一個(gè)后繼

IN[S];

IN[B]=useB

∪(OUT[B]-defB

); }OUT[B]2IN[B]2u3u3u2,u3u2,u3i,j,u2,u3i,j,u2,u3m,n,u1,u2,u3i,j,u2,u3j,u2,u3j,u2,u3j,u2,u3j,u2,u3i,j,u2,u3i,j,u2,u3m,n,u1,u2,u3OUT[B]2IN[B]2i,j,u2,u3j,u2,u3j,u2,u3j,u2,u3j,u2,u3i,j,u2,u3i,j,u2,u3m,n,u1,u2,u3例OUT[B]1IN[B]1B4B3B2B1useB1={m,n,u1

}defB1={i,j,a}useB2={i,j}defB2=ΦuseB3={u2

}defB3={a}useB4={u3

}defB4={i}ENTRYB1B2B3EXITB4OUT[B]2IN[B]2u3u3u2,u3u2,u3i,j,u2,u3i,j,u2,u3m,n,u1,u2,u3i,j,u2,u3j,u2,u3j,u2,u3j,u2,u3j,u2,u3i,j,u2,u3i,j,u2,u3m,n,u1,u2,u3OUT[B]2IN[B]2i,j,u2,u3j,u2,u3j,u2,u3j,u2,u3j,u2,u3i,j,u2,u3i,j,u2,u3m,n,u1,u2,u3OUT[B]B1B2B3B4a××××i√××√j√√√√m××××n××××u1××××u2√√√√u3√√√√例定值-引用鏈(Definition-UseChains)定值-引用鏈：設(shè)變量x有一個(gè)定值d，該定值所有能夠到達(dá)的引用u的集合稱為x在d處的定值-引用鏈，簡(jiǎn)稱du鏈如果在求解活躍變量數(shù)據(jù)流方程中的OUT[B]時(shí)，將OUT[B]表示成從B的末尾處能夠到達(dá)的引用的集合，那么，可以直接利用這些信息計(jì)算基本塊B中每個(gè)變量x在其定值處的du鏈···d:x=·········=···x······d′:x=