編譯原理第十章習(xí)題答案分析

編譯原理電子教案第十章

優(yōu)化·謝強(qiáng)·計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院xieqiang@本章的主要內(nèi)容2上一頁下一頁基本塊的劃分和流圖的構(gòu)建基本塊的DAG表示及基于DAG的局部?jī)?yōu)化循環(huán)優(yōu)化本章要求3上一頁下一頁知識(shí)點(diǎn)：優(yōu)化的基本概念及方法、基本塊及程序流圖、

DAG及基于DAG的優(yōu)化、循環(huán)優(yōu)化熟練掌握：局部?jī)?yōu)化：基本塊，流圖，DAG優(yōu)化。循環(huán)優(yōu)化：代碼外提，強(qiáng)度削弱，刪除歸納變量。優(yōu)化分類4上一頁下一頁按階段分:與機(jī)器無關(guān)的優(yōu)化---對(duì)中間代碼進(jìn)行依賴于機(jī)器的優(yōu)化---對(duì)目標(biāo)代碼進(jìn)行根據(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ù)流分析(data-flow

analysis)控制流分析(control-flowanalysis)變換(transformations)本章教學(xué)線索5上一頁下一頁概述優(yōu)化技術(shù)簡(jiǎn)介局部?jī)?yōu)化循環(huán)優(yōu)化1概述6上一頁下一頁優(yōu)化的目的是為了獲得更高效的代碼，必須遵循以下原則：等價(jià)原則：優(yōu)化后不能改變程序運(yùn)行的結(jié)果有效原則：優(yōu)化后所產(chǎn)生的目標(biāo)代碼運(yùn)行時(shí)間更短、占用的存儲(chǔ)空間更小合算原則：盡可能以較低的代價(jià)獲取較好的優(yōu)化效果。常用的優(yōu)化技術(shù)：刪除公共子表達(dá)式復(fù)寫傳播刪除無用代碼代碼外提強(qiáng)度削弱刪除歸納變量本章教學(xué)線索7上一頁下一頁概述優(yōu)化技術(shù)簡(jiǎn)介局部?jī)?yōu)化循環(huán)優(yōu)化2優(yōu)化技術(shù)簡(jiǎn)介8上一頁下一頁a

=

10

*

5

+

6

-

b;優(yōu)化前：_tmp0

=

10

;_tmp1

=

5

;_tmp2

=

_tmp0

*

_tmp1

;_tmp3

=

6

;_tmp4

=

_tmp2

+

_tmp3

;_tmp5

=

_tmp4

–

b;a

=

_tmp5

;優(yōu)化后：_tmp0

=

56

;_tmp1

=

_tmp0

–

b

;a

=

_tmp1

;常數(shù)合并常數(shù)傳播_tmp4

=

0

;f0

=

_tmp4

;_tmp5

=

1

;f1

=

_tmp5

;_tmp6

=

2

;i

=

_tmp6

;f0

=

0

;f1

=

1

;i

=

2

;優(yōu)化9上一頁下一頁代數(shù)簡(jiǎn)化x+0

=

x0+x

=

xx*1

=

x1*x

=

x0/x

=

0x-0

=

xb

&&

true

=

bb

&&

false

=

falseb

||

true

=

trueb

||

false

=

bb

=

5

+

a

+

10

;優(yōu)化前：_tmp0

=

5

;_tmp1

=

_tmp0

+

a

;_tmp2

=

_tmp1

+

10

;b

=

_tmp2

;優(yōu)化后：_tmp0

=

15

;_tmp1

=

a

+

_tmp0

;b

=

_tmp1

;10上一頁下一頁b)

i/2=(int)(i*0.5)c)

0-1=-111上一頁下一頁降低運(yùn)算強(qiáng)度a)

i*2

=

2*i

=

i+i

=

i<<2d)f*2

=

2.0

*

f

=

f

+

fe)

f/2.0

=

f*0.5c

=

tmp5

+

tmp4

;復(fù)寫傳播tmp2tmp3tmp4tmp5====tmp1tmp2tmp3tmp3;*;*tmp1;tmp2

;tmp3

=

tmp1

*

tmp1

;tmp5

=

tmp3

*

tmp1

;c

=

tmp5

+

tmp3

;12上一頁下一頁P(yáng):=0for

I:=1

to

20

doP:=P+A[I]*B[I]P:=0I:=1(3)T1:=4*I(4)T2:=addr(A)-4(5)T3:=T2[T1](6)T4:=4*I(7)T5:=addr(B)-4(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)if

I<=20goto(3)(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*I(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)if

I<=20goto(3)優(yōu)化13上一頁下一頁(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*I(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)if

I<=20

goto(3)(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*I(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3")T1:=T1+4(12)if

I<=20

goto(5)優(yōu)化14上一頁下一頁(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*I(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](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(3)T1:=4(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T1](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3")T1:=T1+4(12)if

T1<=80

goto(5)優(yōu)化15上一頁下一頁(1)P:=0(2)I:=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)I:=I+1(3")T1:=T1+4(12)if

T1<=80

goto(5)(1)P:=0(2)I:=1(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)if

T1<=80

goto(5)優(yōu)化16上一頁下一頁本章教學(xué)線索17上一頁下一頁概述優(yōu)化技術(shù)簡(jiǎn)介局部?jī)?yōu)化基本塊和流圖基本塊的DAG及其應(yīng)用循環(huán)優(yōu)化3局部?jī)?yōu)化18上一頁下一頁局部?jī)?yōu)化就是以程序的基本塊為范圍進(jìn)行局部?jī)?yōu)化。3.1基本塊和流圖19上一頁下一頁基本塊：程序中一順序執(zhí)行的語句序列，其中第一句為其唯一的入口，最后一句為其唯一的出口。劃分四元式為基本塊的算法：1）求四元式程序中各個(gè)基本塊的入口語句：①程序的第一條語句能由條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句轉(zhuǎn)移到的語句緊跟在條件轉(zhuǎn)移語句后面的語句②③對(duì)每一個(gè)入口語句，其基本塊是由該入口語句到下一 個(gè)入口語句（不包括此入口語句）、或到一個(gè)轉(zhuǎn)移語 句（包括此轉(zhuǎn)移語句）、或到一個(gè)停語句(包括此停語 句）之間的語句序列組成。將未劃入基本塊的語句刪除。例：p279：read

Xread

YR=X

mod

Y(4)

if

R

=

0

goto

(8)X

=

YY=

Rgoto

(3)write

Yhalt根據(jù)規(guī)則1)，可以得出（1）、（3）、（8）、（5）是入口語句，從而由規(guī)則2）可知：基本塊為：（1）（2）、（3）（4）、（5）（6）（7）、（8）（9）。第一句條件或者無條件轉(zhuǎn)移語句轉(zhuǎn)移到的語句條件或者無條件轉(zhuǎn)移語句轉(zhuǎn)移到的語句緊跟在條件轉(zhuǎn)移語句后面的語句20上一頁下一頁流圖（控制流程圖）：一個(gè)控制流程圖是具有唯一首結(jié)點(diǎn)的有向圖，表示成：G=（N，E，n0）其中，N是基本塊集；n0是首結(jié)點(diǎn)，是含有第一條語句的基本塊；E是有向邊集。E的構(gòu)成如下：基本塊Bi和基本塊Bj滿足如下條件之一，則從Bi引一條有向邊到Bj

。1）Bj緊跟在Bi之后，且Bi的出口語句不是goto語句（無條件）。2）Bi的出口語句是“[if]goto

L”（條件/無條件轉(zhuǎn)移）語句，而L是Bj

的入L1：if

a<b

goto

L2goto

LnextL2：if

c<d

goto

L3goto

L4L3：t1

=

y

+

zx

=

t1goto

L1L4：t2

=

y

-

zx

=

t2goto

L1口語句，Bi是Bj的前驅(qū)結(jié)點(diǎn)。例：

L1：

if

a<b

goto

L2goto

Lnext21上一頁下一頁L2：

if

c<d

goto

L3goto

L4L3：

t1

=y+zx

=t1goto

L1L4：t2

=

y-zx

=t2

goto

L13.2基本塊的DAG及其應(yīng)用基本塊DAG圖的概念：圖的葉子結(jié)點(diǎn)以一標(biāo)識(shí)符或常數(shù)作為標(biāo)志，表示該結(jié)點(diǎn)代表該變量或常數(shù)的值；圖中的內(nèi)部結(jié)點(diǎn)以一運(yùn)算符作為標(biāo)記，表示該結(jié)點(diǎn)代表應(yīng)用該運(yùn)算符對(duì)其后繼結(jié)點(diǎn)所代表的值進(jìn)行運(yùn)算的結(jié)果；圖中各個(gè)結(jié)點(diǎn)上可能附加一個(gè)或多個(gè)標(biāo)識(shí)符，表示這些變量具有該結(jié)點(diǎn)所代表的值。基本塊DAG圖的構(gòu)造算法：（1）A

=

op

Bn1ABn1ABn2op假設(shè)代碼形式為（0）A=B（2）A=B

op

C或A=B[C]DAG結(jié)點(diǎn)n1ABn3n2C22上一頁下一頁op算法步驟：1.如果NODE（B）無定義，則構(gòu)造一標(biāo)記為B的葉子結(jié)點(diǎn)并定義NODE（B）為這個(gè)結(jié)點(diǎn)；如果當(dāng)前的代碼是（0）型，則記NODE（B）的值為n，轉(zhuǎn)4；如果是（1）型，則轉(zhuǎn)2（1）；如果當(dāng)前代碼是（2）型，則：（i）如果NODE（C）無定義，則構(gòu)造一標(biāo)記為C的葉結(jié)點(diǎn)，并定義NODE（C）為這個(gè)結(jié)點(diǎn)；轉(zhuǎn)2（2）。2.（1）如果NODE(B)是標(biāo)記為常數(shù)的葉結(jié)點(diǎn),則轉(zhuǎn)2(3),否則轉(zhuǎn)3(1)。若NODE(B)和NODE(C)都是標(biāo)記為常數(shù)的葉結(jié)點(diǎn),則轉(zhuǎn)2(4),否則轉(zhuǎn)3(2)。執(zhí)行opB(合并已知量),令得到的新常數(shù)為p。如果NODE（B）是處理當(dāng)前代碼時(shí)新構(gòu)造出來的結(jié)點(diǎn)，則刪除它，如果NODE(p)無定義，則構(gòu)造一用p做標(biāo)記的葉結(jié)點(diǎn)n。置NODE(p)=n，轉(zhuǎn)4。執(zhí)行B

op

C(合并已知量),令得到的新常數(shù)為p，如果NODE（B）是處理當(dāng)前代碼時(shí)新構(gòu)造出來的結(jié)點(diǎn)，則刪除它，如果NODE（p）無定義，則構(gòu)造一用p做標(biāo)記的葉結(jié)點(diǎn)。置NODE（p）=

n，轉(zhuǎn)4；23上一頁下一頁3.(1)檢查DAG中是否已有一結(jié)點(diǎn)，其唯一后繼為NODE(B)且標(biāo)記為op（即找公共子表達(dá)式）。如果沒有，則構(gòu)造該結(jié)點(diǎn)n，否則就把已有的結(jié)點(diǎn)作為它的結(jié)點(diǎn)并設(shè)該結(jié)點(diǎn)為n。轉(zhuǎn)4。24上一頁下一頁（2）檢查DAG中是否已有一結(jié)點(diǎn)，其左后繼為NODE(B)，右后繼為NODE（C），且標(biāo)為op（即找公共子表達(dá)式）。如果沒有，則構(gòu)造該結(jié)點(diǎn)n，否則就把已有的結(jié)點(diǎn)作為它的結(jié)點(diǎn)并設(shè)該結(jié)點(diǎn)為n，轉(zhuǎn)4。4.如果NODE(A)無定義，則把A附加在結(jié)點(diǎn)n上并令NODE（A）=n；否則先把A從NODE(A)結(jié)點(diǎn)上的附加標(biāo)記符集中刪除（如果NODE(A)是葉子結(jié)點(diǎn)，則其標(biāo)記A不刪除），把A附加到新結(jié)點(diǎn)n上并令NODE(A)=n。轉(zhuǎn)處理下一條代碼。DAG的應(yīng)用：根據(jù)DAG，重寫代碼，即可實(shí)現(xiàn)局部?jī)?yōu)化。例：構(gòu)造以下基本塊的DAG：（1）T0=3.14（2）T1=2*3.14T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-r（10）B=T5*T6n6n8T0-T2,T4n5+A，T5

BBT6n7n1n2

T1,T3

n3n43.14

6.28

Rr(1)

T0=3.14

(2)

T1=6.28(6)

A=6.28*T2

(7)

T5=A(3)T3=6.28

(4)T2=R+r(8)

T6=R-r

(9)

B=A*T6(5)

T4=T2**25上一頁下一頁本章教學(xué)線索26上一頁下一頁概述優(yōu)化技術(shù)簡(jiǎn)介局部?jī)?yōu)化循環(huán)優(yōu)化代碼外提強(qiáng)度削弱刪除歸納變量4循環(huán)優(yōu)化27上一頁下一頁循環(huán)：程序中可能反復(fù)執(zhí)行的代碼序列，比如高級(jí)語言中的for語句、while語句、do-until語句等都是循環(huán)語句由于循環(huán)語句常常要反復(fù)執(zhí)行，因此對(duì)其優(yōu)化，將大大提高目標(biāo)代碼的執(zhí)行效率。4.1代碼外提28上一頁下一頁在循環(huán)中如果有形如A=B

op

C的代碼，而B和C或者是

常數(shù)、或者其定值點(diǎn)在循環(huán)外，則可以將其提到循環(huán)外。方法：在循環(huán)入口點(diǎn)建立一新的結(jié)點(diǎn)（循環(huán)前置結(jié)點(diǎn)）（基本塊），將循環(huán)中可以外提的代碼放在其中。注意：（1）當(dāng)把一不變運(yùn)算外提到循環(huán)前置結(jié)點(diǎn)時(shí)，要求該不變運(yùn)算所在的結(jié)點(diǎn)是循環(huán)所有出口結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)；（2）當(dāng)把A=B

op

C外提時(shí)，要求循環(huán)中A的所有引用點(diǎn)都是而且僅僅是這個(gè)定值所能達(dá)到的。（3）對(duì)不變運(yùn)算A=B

op

C要求循環(huán)中其他地方不能再有

A的定值入口結(jié)點(diǎn)循環(huán)L入口結(jié)點(diǎn)循環(huán)

L前置結(jié)點(diǎn)外提29上一頁下一頁代碼外提的總體結(jié)構(gòu)：（1）

I=1B2（2）

if

X<Y

goto

B430上一頁下一頁B3（3）

I=2(4)X=X+1B4（5）

Y=Y-1(6)if

x<20

goto

B2B5（7）

J=II=2是循環(huán)不變運(yùn)算，是否能夠外提？B3不是循環(huán)出口結(jié)點(diǎn)B4的必經(jīng)之路，如果外提，則循環(huán)結(jié)束后，J的值一定是2，而在原來循環(huán)中，J的值可能是1。B1結(jié)論：當(dāng)把一不變運(yùn)算外提到循環(huán)前置結(jié)點(diǎn)時(shí)，要求該不變算所在的結(jié)點(diǎn)是循環(huán)所有出口結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)。如果循環(huán)中I的所有引用點(diǎn)只是B3中I的定值所能到達(dá)

I在循環(huán)中不再有其它定值點(diǎn)，并且出循環(huán)后不會(huì)再引用該I的值（即在循環(huán)外的循環(huán)后繼結(jié)點(diǎn)入口，I不是活躍的），那么即使B3不是B4的必經(jīng)結(jié)點(diǎn)，還是可以將

I=2外提。31上一頁下一頁（3）I=2（4）X=X+1（5）

Y=Y-1(6)if

x<20

goto

B2（7）

J=I（1）

I=1B2I=3（2）

if

X<Y

goto

B432上一頁下一頁B3B4B5結(jié)論：I=3也不能外提，對(duì)不變運(yùn)算A=B

op

C要求循環(huán)中其他地方不能再有A的定值。B1I=3所在結(jié)點(diǎn)B2是循環(huán)出口點(diǎn)的必經(jīng)結(jié)點(diǎn)，能否外提？A=I+1X=X+1I=2Y=Y-1if

Y<0

goto

B2J=AB333上一頁下一頁B4B5B4中的I=2為循環(huán)不變運(yùn)算，并且為循環(huán)出口的必經(jīng)之路，并且沒有再被定值是否能夠外提？B1I=1B2if

X<Y

goto

B4不能外提，否則改變J的值。結(jié)論：當(dāng)把循環(huán)不變運(yùn)算A=B

op

C外提時(shí)，要求循環(huán)中A的所有引用點(diǎn)都是而且僅僅是這個(gè)定值所能到達(dá)的。查找循環(huán)L中的不變運(yùn)算的算法：依次查看L中各個(gè)基本塊的每個(gè)代碼，如果它的每個(gè)運(yùn)算對(duì)象或?yàn)槌?shù)，或者定值點(diǎn)在L外，則將其標(biāo)記為“不變運(yùn)算”；重復(fù)（3）直到?jīng)]有新的代碼標(biāo)記為“不變運(yùn)算”；依次查看尚未被標(biāo)記為“不變運(yùn)算”的代碼，如果它的每個(gè)運(yùn)算對(duì)象或?yàn)槌?shù)，或定值點(diǎn)在L之外，或者只有一個(gè)到達(dá)一定值點(diǎn)且該點(diǎn)上的代碼已經(jīng)標(biāo)記為“不變運(yùn)算”，則把它標(biāo)記為“不變運(yùn)算”。代碼外提算法：求出循環(huán)L中所有不變運(yùn)算；對(duì)步驟（1）所求出的每一個(gè)“不變運(yùn)算”s：A=B

op

C（或

A=B），檢查它是否滿足以下條件①或②：①（i）s所在的結(jié)點(diǎn)是L的所有出口結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)A在L中其它地方未再定值；L中所有A的引用點(diǎn)只有s中的A的定值才能達(dá)到。②A在離開L后不再活躍，并且條件①的（ii）和（iii）成立。按步驟（1）所找到的不變運(yùn)算的順序，依次把符合條件①或②的不變運(yùn)算s外提到L的前置結(jié)點(diǎn)。但是如果s的運(yùn)算對(duì)象（B或C）是在L中定值的，那么只有當(dāng)這些定值代碼都已經(jīng)提到前置結(jié)點(diǎn)中時(shí)，才能將s提到前置結(jié)點(diǎn)中。34上一頁下一頁4.2強(qiáng)度削弱35上一頁下一頁強(qiáng)度削弱：就是將循環(huán)中執(zhí)行時(shí)間長(zhǎng)的運(yùn)算等價(jià)替換為執(zhí)行時(shí)間較短的運(yùn)算。一般對(duì)于乘法運(yùn)算可以替換為在循環(huán)前置結(jié)點(diǎn)進(jìn)行一次乘法運(yùn)算和循環(huán)中遞歸賦值的加法運(yùn)算。（1）如果循環(huán)中有I的遞歸賦值I=I±C（C為循環(huán)不變量），并且循環(huán)中T的賦值運(yùn)算可劃歸為T=K

*

I±C1，（C1為循環(huán)不變量），那么T的賦值運(yùn)算可以進(jìn)行強(qiáng)度削弱。（2）強(qiáng)度削弱后，循環(huán)中可能出現(xiàn)一些新無用的賦值，一般為臨時(shí)變量，可以刪除；(1)

I

=1(15)B1B2’(3)

T1=2*J(6)T4=addr(A)-11(7)T5=2*I(10)T8=addr(A)-11B2(2)

if

I>10

goto

(15)B3(4)T2=10*I(5)T3=T2+T1(8)T6=10*I(9)T7=T6+T5(11)T9=T8[T7](12)T4[T3]=T9+1(13)I=I+1(14)gotoB2(1)

I

=1(3)

T1=2*J(15)B1B2’(6)T4=addr(A)-11(7)T5=2*I(10)T8=addr(A)-11(4)T2=10*I(8)T6=10*IB2(2)

if

I>10

goto

(15)B3(5)T3=T2+T1(9)T7=T6+T5(11)T9=T8[T7](12)T4[T3]=T9+1(13)I=I+1(4’)T2=T2+10(8’)T6=T6+10(14)gotoB2B1(1)

I

=1(3)

T1=2*J(6)T4=addr(A)-11(7)T5=2*I(10)T8=addr(A)-11(4)T2=10*I(8)T6=10*I(5)T3=T2+T1(9)T7=T6+T5(15)36上一頁下一頁B2’B2(2)

if

I>10

goto

(15)B3(11)T9=T8[T7](12)T4[T3]=T9+1(13)I=I+1(4’)T2=T2+10(8’)T6=T6+10(5’)T3=T3+10(9’)T7=T7+10(14)gotoB24.3刪除歸納變量37上一頁下一頁基本歸納變量：如果循環(huán)中對(duì)變量I只有唯一的形如：I=I±C的賦值，且C為循環(huán)不變量，則稱I為循環(huán)中的基本歸納變量