南大面試課程編譯課件chapter

主要內(nèi)容引言優(yōu)化的來源數(shù)據(jù)流分析部分冗余消除循環(huán)的識別、分析和優(yōu)化引言代碼優(yōu)化或者代碼改進(jìn)在目標(biāo)代碼中消除不必要的指令把一個指令序列替換為一個完成相同功能的更快的指令序列全局優(yōu)化有哪些可能的優(yōu)化或改進(jìn)機(jī)會？具體的優(yōu)化實現(xiàn)基于數(shù)據(jù)流分析技術(shù)用以收集程序相關(guān)信息的算法。優(yōu)化的來源程序的冗余冗余是使用高級程序設(shè)計語言編程的副產(chǎn)品通過抽象的易于書寫的方式編程和程序的高效之間存在矛盾。給編譯器提供了優(yōu)化的機(jī)會。優(yōu)化的示例快速排序優(yōu)化的示例（續(xù)）優(yōu)化的示例（續(xù)）全局公共子表達(dá)式表達(dá)式E之前出現(xiàn)過，其中的變量值都沒有改變過，多次出現(xiàn)這樣的E可以被稱為公共子表達(dá)式。如果E上一次計算結(jié)果賦予變量x，且x的值中間沒有被改變，那么就可以使用x而避免重新計算E。例9.1:局部優(yōu)化例9.2:考慮B2、B3和B5、B6中 的公共子表達(dá)式優(yōu)化的示例（續(xù)）消除公共子表達(dá)式后的流圖優(yōu)化-復(fù)制傳播復(fù)制語句：形如u=v這樣的復(fù)制表達(dá)式復(fù)制語句的產(chǎn)生，有時是由其公共子表達(dá)式消除優(yōu)化引入的。復(fù)制傳播轉(zhuǎn)換的基本思想 是在復(fù)制語句u=v之后盡可能的用v來替代u。優(yōu)化-死代碼的消除活躍：一個變量在一個程序點上的值可能會在以后被使用，那么這個變量在該點活躍。死：不活躍死代碼：其計算結(jié)果用于不會被使用的語句。常量折疊會產(chǎn)生一些死代碼。復(fù)制傳播也會把一些復(fù)制語句變成死代碼。優(yōu)化-代碼移動盡可能減少內(nèi)部循環(huán)的指令可能，即使可能增加循環(huán)外的指令個數(shù)也是值得的。循環(huán)不變表達(dá)式：無論循環(huán)多少次，表達(dá)式的值都不會變化的表達(dá)式。代碼移動：在進(jìn)入循環(huán)前，對循環(huán)不變表達(dá)式進(jìn)行求值。優(yōu)化-歸納變量和強(qiáng)度削減歸納變量：對于一個變量x，如果存在一個正的或負(fù)的常數(shù)c使得每次x被賦值時它的值總是增加c，那么x被稱為歸納變量。例如圖9.5

B2中的i和t2。強(qiáng)度削減：把一個高代價的運算（比如乘法）替換為一個代價較低的運算（比如加法）的轉(zhuǎn)換稱為強(qiáng)度削減。如果有一組歸納變量的值的變化保持步調(diào)一致，常?？梢詫⑦@組變量刪除只剩一個。優(yōu)化-歸納變量和強(qiáng)度削減(例)例9.6優(yōu)化-歸納變量和強(qiáng)度削減(例)刪除具有同步調(diào)變化的歸納變量Sort1i

=

m

-

12j

=

n3t1=4

*

n4v

=

a[t1]5i

=

i

+

16t2

=

4

*

i7t3

=

a[t2]8if

t3

<

v

goto

(5)9j

=

j

–

110t4

=

4

*

j11t5

=

a[t4]12if

t5

>

v

goto

(9)13if

i

>=

j

goto

(23)14t6

=

4

*

i15x

=

a[t6]16t7

=

4

*

I17t8

=

4

*

j18t9

=

a[t8]19a[t7]

=

t920t10

=

4

*

j21a[t10]

=

x22goto

(5)23t11

=

4

*

I24x

=

a[t11]25t12

=

4

*

i26t13

=

4

*

n27t14

=

a[t13]28a[t12]

=

t1429t15

=

4

*

n30a[t15]

=

x1i

=

m

-

12j

=

n3t1=4

*

n4v

=

a[t1]5i

=

i

+

16t2

=

4

*

i7t3

=

a[t2]8if

t3

<

v

goto

(5)9j

=

j

–

110t4

=

4

*

j11t5

=

a[t4]12if

t5

>

v

goto

(9)13if

i

>=

j

goto

(23)14t6

=

4

*

i15x

=

a[t6]16t7

=

4

*

I17t8

=

4

*

j18t9

=

a[t8]19a[t7]

=

t920t10

=

4

*

j21a[t10]

=

x22goto

(5)23t11

=

4

*

i24x

=

a[t11]25t12

=

4

*

i26t13

=

4

*

n27t14

=

a[t13]28a[t12]

=

t1429t15

=

4

*

n30a[t15]

=

xFind

The

Basic

BlockB1Flow

Graphi

=

m

-

1j

=

nt1

=4

*

nv

=

a[t1]i

=

i

+

1t2

=

4

*

it3

=

a[t2]if

t3

<

v

goto

B2j

=

j

–

1t4

=

4

*

jt5

=

a[t4]if

t5

>

v

goto

B3t6

=

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

*

it13

=

4

*

nt14

=a[t13]a[t12]

=

t14t15

=

4

*

na[t15]

=

xB2B3B4if

i

>=

j

goto

B6B5B6i

=

m

-

1j

=

nt1

=4

*

nv

=

a[t1]i

=

i

+

1t2

=

4

*

it3

=

a[t2]if

t3

<

v

goto

B2j

=

j

–

1t4

=

4

*

jt5

=

a[t4]if

t5

>

v

goto

B3t6

=

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

*

it13

=

4

*

nt14

=a[t13]a[t12]

=

t14t15

=

4

*

na[t15]

=

xB1Common

Subexpression

EliminationB2B3B4if

i

>=

j

goto

B6B5B6B1Common

Subexpression

Eliminationi

=

m

-

1j

=

nt1

=4

*

nv

=

a[t1]i

=

i

+

1t2

=

4

*

it3

=

a[t2]if

t3

<

v

goto

B2j

=

j

–

1t4

=

4

*

jt5

=

a[t4]if

t5

>

v

goto

B3t6

=

4

*

ix

=

a[t6]t8

=

4

*

jt9

=

a[t8]a[t6]

=

t9t10

=

4

*

ja[t10]

=

xgoto

B2t11

=

4

*

ix

=

a[t11]t12

=4

*

it13

=

4

*

nt14

=a[t13]a[t12]

=

t14t15

=

4

*

na[t15]

=

xB2B3B4if

i

>=

j

goto

B6B5B6B1Eliminationi

=

m

-

1j

=

nt1

=4

*

nv

=

a[t1]i

=

i

+

1t2

=

4

*

it3

=

a[t2]if

t3

<

v

goto

B2j

=

j

–

1t6

=

4

*

ix

=

a[t6]t8

=

4

*

jt9

=

a[t8]a[t6]

=

t9a[t8]

=

xgoto

B2t11

=

4

*ix

=

a[t11]t12

=4

*

it13

=

4

*

nt14

=a[t13]a[t12]

=

t14t15

=

4

*

na[t15]

=

xB2B3t4

=

4

*

jt5

=

a[t4]if

t5

>

v

goto

B3B4if

i

>=

j

goto

B6B5B6B1Eliminationi

=

m

-

1j

=

nt1

=4

*

nv

=

a[t1]i

=

i

+

1t2

=

4

*

it3

=

a[t2]if

t3

<

v

goto

B2j

=

j

–

1t6

=

4

*

ix

=

a[t6]t8

=

4

*

jt9

=

a[t8]a[t6]

=

t9a[t8]

=

xgoto

B2t11

=

4

*

ix

=

a[t11]t12

=4

*

it13

=

4

*

nt14

=a[t13]a[t12]

=

t14t15

=

4

*

na[t15]

=

xB2B3t4

=

4

*

jt5

=

a[t4]if

t5

>

v

goto

B3B4if

i

>=

j

goto

B6B5B6B1Eliminationi

=

m

-

1j

=

nt1

=4

*

nv

=

a[t1]i

=

i

+

1t2

=

4

*

it3

=

a[t2]if

t3

<

v

goto

B2j

=

j

–

1t6

=

4

*

ix

=

a[t6]t8

=

4

*

jt9

=

a[t8]a[t6]

=

t9a[t8]

=

xgoto

B2t11

=

4

*

ix

=

a[t11]t13

=

4

*

nt14

=a[t13]a[t11]

=

t14t15

=

4

*

na[t15]

=

xB2B3t4

=

4

*

jt5

=

a[t4]if

t5

>

v

goto

B3B4if

i

>=

j

goto

B6B5B6B1Eliminationi

=

m

-

1j

=

nt1

=4

*

nv

=

a[t1]i

=

i

+

1t2

=

4

*

it3

=

a[t2]if

t3

<

v

goto

B2j

=

j

–

1t6

=

4

*

ix

=

a[t6]t8

=

4

*

jt9

=

a[t8]a[t6]

=

t9a[t8]

=

xgoto

B2t11

=

4

*

ix

=

a[t11]t13

=

4

*

nt14

=a[t13]a[t11]

=

t14a[t13]

=

xB2B3t4

=

4

*

jt5

=

a[t4]if

t5

>

v

goto

B3B4if

i

>=

j

goto

B6B5B6Common

Subexpression

Elimination（全局）i

=

m

-

1j

=

nt1

=4

*

nv

=

a[t1]i

=

i

+

1t2

=

4

*

it3

=

a[t2]if

t3

<

v

goto

B2t6

=

4

*

ix

=

a[t6]t8

=

4

*

jt9

=

a[t8]a[t6]

=

t9a[t8]

=

xgoto

B2t11

=

4

*

ix

=

a[t11]t13

=

4

*

nt14

=a[t13]a[t11]

=

t14a[t13]

=

xB1B2B3j

=

j

–

1

t4

=

4

*

jt5

=

a[t4]if

t5

>

v

goto

B3B4if

i

>=

j

goto

B6B5B6B1Eliminationi

=

m

-

1j

=

nt1

=4

*

nv

=

a[t1]i

=

i

+

1t2

=

4

*

it3

=

a[t2]if

t3

<

v

goto

B2x

=

a[t2]t8

=

4

*

jt9

=

a[t8]a[t2]

=

t9a[t8]

=

xgoto

B2t11

=

4

*

ix

=

a[t11]t13

=

4

*

nt14

=a[t13]a[t11]

=

t14a[t13]

=

xB2B3j

=

j

–

1

t4

=

4

*

jt5

=

a[t4]if

t5

>

v

goto

B3B4if

i

>=

j

goto

B6B5B6B1Eliminationi

=

m

-

1j

=

nt1

=4

*

nv

=

a[t1]i

=

i

+

1t2

=

4

*

it3

=

a[t2]if

t3

<

v

goto

B2x

=

t3t8

=

4

*

jt9

=

a[t8]a[t2]

=

t9a[t8]

=

xgoto

B2t11

=

4

*

ix

=

a[t11]t13

=

4

*

nt14

=a[t13]a[t11]

=

t14a[t13]

=

xB2B3j

=

j

–

1

t4

=

4

*

jt5

=

a[t4]if

t5

>

v

goto

B3B4if

i

>=

j

goto

B6B5B6B1Eliminationi

=

m

-

1j

=

nt1

=4

*

nv

=

a[t1]i

=

i

+

1t2

=

4

*

it3

=

a[t2]if

t3

<

v

goto

B2x

=

t3t9

=

a[t4]a[t2]

=

t9a[t4]

=

xgoto

B2t11

=

4

*

ix

=

a[t11]t13

=

4

*

nt14

=a[t13]a[t11]

=

t14a[t13]

=

xB2B3j

=

j

–

1t4

=

4

*

jt5

=

a[t4]if

t5

>

v

goto

B3B4if

i

>=

j

goto

B6B5B6B1Eliminationi

=

m

-

1j

=

nt1

=4

*

nv

=

a[t1]i

=

i

+

1t2

=

4

*

it3

=

a[t2]x

=

t3a[t2]

=

t5a[t4]

=

xgoto

B2t11

=

4

*

ix

=

a[t11]t13

=

4

*

nt14

=a[t13]a[t11]

=

t14a[t13]

=

xB2if

t3

<

v

goto

B2B3j

=

j

–

1

t4

=

4

*

jt5

=

a[t4]if

t5

>

v

goto

B3B4if

i

>=

j

goto

B6B5B6B1Eliminationi

=

m

-

1j

=

nt1

=4

*

nv

=

a[t1]i

=

i

+

1t2

=

4

*

it3

=

a[t2]j

=

j

–

1x

=

t3a[t2]

=

t5a[t4]

=

xgoto

B2x

=

t3t14

=a[t1]a[t2]

=

t14a[t1]

=

xB2if

t3

<

v

goto

B2B3t4

=

4

*

jt5

=

a[t4]if

t5

>

v

goto

B3B4if

i

>=

j

goto

B6B5B6Similarly

for

B6Copy

Propogation

&

Dead

Code

Eliminationi=

m

-1j

=

nt1

=4

*

nv

=

a[t1]i

=

i

+

1t2

=

4

*

it3

=

a[t2]x

=

t3a[t2]

=

t5a[t4]

=

xgoto

B2x

=

t3t14

=a[t1]a[t2]

=

t14a[t1]

=

xB1B2if

t3

<

v

goto

B2B3j

=

j

–

1

t4

=

4

*

jt5

=

a[t4]if

t5

>

v

goto

B3B4if

i

>=

j

goto

B6B5B6B1Dead

Code

Eliminationi

=

m

-

1j

=

nt1

=4

*

nv

=

a[t1]i

=

i

+

1t2

=

4

*

ia[t2]

=

t5a[t4]

=

t3goto

B2t14

=a[t1]a[t2]

=

t14a[t1]

=t3B2t3

=

a[t2]if

t3

<

v

goto

B2B3j

=

j

–

1

t4

=

4

*

jt5

=

a[t4]if

t5

>

v

goto

B3B4if

i

>=

j

goto

B6B5B6B1Reduction

in

Strengthi

=

m

-

1j

=

nt1

=4

*

nv

=

a[t1]i

=

i

+

1t2

=

4

*

it3

=

a[t2]if

t3

<

v

goto

B2a[t2]

=

t5a[t4]

=

t3goto

B2t14

=a[t1]a[t2]

=

t14a[t1]

=t3B2B3j

=

j

–

1

t4

=

4

*

jt5

=

a[t4]if

t5

>

v

goto

B3B4if

i

>=

j

goto

B6B5B6Reduction

in

Strengthi

=

i

+

1t2

=

t2

+

4t3

=

a[t2]if

t3

<

v

goto

B2a[t2]

=

t5a[t4]

=

t3goto

B2t14

=a[t1]a[t2]

=

t14a[t1]

=t3B1B2B3j

=

j

–

1t4

=

t4

-4t5

=

a[t4]if

t5

>

v

goto

B3B4if

i

>=

j

goto

B6B5B6i

=

m

-

1j

=

nt1

=4

*

nv

=

a[t1]t2

=

4

*

it4

=

4

*

jB1Induction

Variable

Eliminationi

=

m

-

1j

=

nt1

=4

*

nv

=

a[t1]t2

=

4

*

it4

=

4

*

jt2

=

t2

+

4t3

=

a[t2]if

t3

<

v

goto

B2t4

=

t4

-4a[t2]

=

t5a[t4]

=

t3goto

B2t14

=a[t1]a[t2]

=

t14a[t1]

=t3B2B3t5

=

a[t4]if

t5

>

v

goto

B3B4if

t2>=

t4

goto

B6B5B6數(shù)據(jù)流分析上述所有的優(yōu)化都依賴于數(shù)據(jù)流分析數(shù)據(jù)流分析是一組用來獲取有關(guān)數(shù)據(jù)如何沿著程序執(zhí)行路徑流動的相關(guān)信息的技術(shù)。全局公共子表達(dá)式：需要確定表達(dá)式中變量的值是否改變死代碼消除：需要確定某一個賦值語句的結(jié)果是否被后續(xù)使用……數(shù)據(jù)流分析相關(guān)概念程序點基本塊中的位置，包括：第一個語句之前，兩個相鄰語句之間，和最后的語句之后。路徑點序列p1,p2,…,pn，對1和n

-1間的每個i，滿足pi是一個語句前的點，pi＋1是同一塊中位于該語句后的點，或者pi是某塊的結(jié)束點，pi＋1是后繼塊的開始點程序狀態(tài)：程序中所有變量在某個程序點的取值。數(shù)據(jù)流抽象的例子從程序狀態(tài)中獲取我們感興趣的抽象信息第一次到程序點（5） a的值為1。以后到達(dá) 該點時a的值為243。可以得出一個抽象信息，a的值集合是{1,243}，而它由{d1,d2}定值。數(shù)據(jù)流分析的模式各個程序點上可能的程序狀態(tài)，可以幫助我們進(jìn)行數(shù)據(jù)流的分析。每個程序點和一個數(shù)據(jù)流值相關(guān)聯(lián)，這個值是在該點可能觀察到的所有程序狀態(tài)的集合的抽象表示。在各種數(shù)據(jù)流分析中，每個程序點和一個數(shù)據(jù)流值相關(guān)聯(lián)。不同的數(shù)據(jù)流分析，數(shù)據(jù)流值的類型可能不同。在程序中一個語句之前和之后的數(shù)據(jù)流值可能會發(fā)生改變，需要描述這種改變(IN[s]和OUT[s]分別表示每個語句s之前和之后的數(shù)據(jù)流值)：傳遞函數(shù)正向OUT[s]=fs(IN[s])逆向IN[s]=fs(OUT[s])控制流約束假設(shè)基本塊B的語句s1,s2,…sn,IN[si+1]=out[si],i=1,2,…,n-1數(shù)據(jù)流分析的模式--基本塊上的數(shù)據(jù)流模式進(jìn)入和離開基本塊時的數(shù)據(jù)流值分別是IN[B]和OUT[B]假設(shè)基本塊由語句s1,s2,…sn順序組成。那么s1是基本塊B的第一個語句，IN[B]=IN[s1]。sn是B的最后一個語句，那么OUT[B]=OUT[sn]。我們可以用fs的傳遞函數(shù)來計算基本塊B的傳遞函數(shù)fB=fsn·…fs2·fs1

。OUT[B]=fB(IN[B])基本塊間的控制流約束IN[B]=∪P是B的一個前驅(qū)OUT[P]逆向數(shù)據(jù)流IN[B]=fB(OUT[B])OUT[B]=∪S是B的一個后繼IN[S]數(shù)據(jù)流分析到達(dá)定值分析活躍變量分析可用表達(dá)式分析到達(dá)定值分析相關(guān)概念定義/定值[definition]：使變量x（可能）獲得值的語句稱為對x的定值，一般用語句的位置表示。變量獲得值的方式：通過賦值語句；通過輸入語句；通過過程形式參數(shù)；通過過程副作用（局部過程引用全局變量）指針等使用/引用點[reference]：引用某個變量x的語句的位置稱為x的引用點。到達(dá)定值分析相關(guān)概念（續(xù)）到達(dá)-定值：假定x有定值d，如果存在一個路徑，從緊隨d的點到達(dá)某點p，并且此路徑上面沒有x的其他定值點，則稱x的定值d到達(dá)p。如果在這條路徑上有對x的其它定值，我們就說變量x的這個定值被“殺死”了。如果某個變量x的一個定值d到達(dá)了點p，在

p點使用變量x的時候，x的值是由d最后定值的。到達(dá)定值流圖示例GEN[B]：各個

變量在B內(nèi)定值，并能夠到達(dá)B的出口點的所有定值的集合。KILL[B]：是各個變量在基本塊B中重新定值，從而被注銷的

定值點的集合。到達(dá)定值的數(shù)據(jù)流分析--傳遞方程考慮一個定值d:u=v+wfd(x)=gend∪(x-killd),gend

=c7yb6nf,killd是程序中所有其它對u的定值。請注意，在到達(dá)定值分析中，x是指程序的定值集合。語句的傳遞函數(shù)可以組合構(gòu)造。f1(x)=gen1∪(x-kill1)，

f2(x)=gen2∪(x-kill2)到達(dá)定值的數(shù)據(jù)流分析--傳遞方程（續(xù)）對于一個基本塊的生成和殺死定值集合，gen中包含了所

有在緊靠基本塊之后的點上“可見”的該基本塊中的定值，它們被稱為向下可見。在一個基本塊中，一個定值是向下可見的，僅當(dāng)它沒有被同一個基本塊中較后的對同一變量的定值“殺死”。一個基本塊的kill集是所有被塊中各個語句殺死的定值的集合。一個定值可能同時出現(xiàn)在基本塊的gen集和kill集中。該定值會被該基本塊生成例9.10到達(dá)定值的數(shù)據(jù)流分析--控制流方程只要有一個定值能夠沿著至少一條路徑到達(dá)某個程序點，那么這個定值就到達(dá)該程序點。

IN[B]=∪P是B的一個前驅(qū)OUT[P]到達(dá)定值分析的數(shù)據(jù)流分析方程組假設(shè)流圖的兩個空基本塊，開始塊ENTRY和出口塊EXIT。邊界條件傳遞方程控制流方程到達(dá)定值的迭代算法對方程組進(jìn)行求解輸入：一個流圖，已知每個基本塊B的killB集和genB集。輸出：到達(dá)流圖中每個基本塊B的入口點和出口點的定值集合，即IN[B]和OUT[B]。迭代算法，逐步逼近想要求得的IN和OUT。到達(dá)定值迭代算法示例求解過程：算到達(dá)定值迭代法示例（續(xù)）比較OUT[B2]的變化活躍變量分析回顧“活躍”“死”的定義對于變量x和程序點p，x在點p上的值是否會在流圖中的某條從p出發(fā)的路徑中使用。如果是，則x在p上“活

躍”；否則x在p上是“死”的活躍變量分析：分析各個變量在各個程序點上是否活躍。通常分析在基本塊入口和出口的活躍變量集合活躍變量分析的意義為基本塊進(jìn)行寄存器分配死代碼刪除……活躍變量分析定義數(shù)據(jù)流方程此時，IN[B]和OUT[B]分別表示在緊靠基本塊B之前和緊隨B之后的點上的活躍變量的集合。defB：是在基本塊B內(nèi)的定值，但是在定值前在B中沒有被引用的變量的集合。useB：表示在基本塊中引用，但是引用前在B中沒有被定值的變量集合。例：圖9-12中。useB2={i,j},

defB2={}活躍變量分析數(shù)據(jù)流方程基于defB

和useB的定義，useB中的變量都必然被認(rèn)為在基本塊的入口處活躍。defB中的變量在B的開頭一定是死的。對于基本塊EXITIN[Exit]=Φ邊界條件，在程序的出口處沒有變量是活躍的對于不等于EXIT的基本塊B：IN[B]=useB

∪(OUT[B]-defB)如果某個變量在B中沒有定值就使用了，顯然，變量在入口處的值會被使用。如果這個變量在B的出口處活躍，并且B中沒有對它進(jìn)行定值，那么變量在入口處也是活躍的。OUT[B]=∪S是B的一個后繼IN[S]在B的某個后繼中會使用某個變量的值，那么該變量在B中也是活躍的。活躍變量分析的迭代算法輸入：一個流圖，每個基本塊B的useB和defB集輸出：每個基本塊B的入口和出口處的活躍變量集合，即IN[B]和OUT[B]可用表達(dá)式用途：尋找全局公共子表達(dá)式如果一個流圖的首節(jié)點到達(dá)點p的每個路徑上面都有對x

op

y的計算，并且在最后一個這樣的計算到點p之間某有對x,y進(jìn)行定值，那么表達(dá)式x

op

y在點p是可用的。表達(dá)式可用的直觀意義：在點p上，x

op

y已經(jīng)在之前被計算過，不需要重新計算。注意：如果有間接賦值的情況，需要保證最后的計算x

op

y的點之間不會間接改變x或者y的值：比如指針不會指向x或者y的存儲區(qū)域，特別是當(dāng)x為某個數(shù)組的時候?？捎帽磉_(dá)式示例可用表達(dá)式x

:=

y

+

z...px

:=

y

+

z.y

:=

….px

:=

y

+

z.z

:=

….py+z

在p點可用y+z

在p點不可用y+z

在p點不可用可用表達(dá)式的計算順序處理基本塊中的語句。如果在點p處可用表達(dá)式的集合是S，而q是p之后的點，且它們之間的語句

x=y+z，那么通過下面兩個步驟可以得到點q上的可用表達(dá)式集合。把表達(dá)式y(tǒng)+z加入S從S中刪除任何涉及變量x的表達(dá)式順序處理完基本塊中的最后一個語句后，S就是基本塊出口處的可用表達(dá)式集合。可用表達(dá)式的計算（示例）可用表達(dá)式的數(shù)據(jù)流分析IN[B]和OUT[B]表示B的入口和出口處的可用表達(dá)式集合。產(chǎn)生和注銷表達(dá)式的產(chǎn)生：如果某個基本塊B對x

op

y進(jìn)行計算，而以后并沒有再對x或者y重新定值，那么稱B產(chǎn)生表達(dá)式x

op

y。對表達(dá)式的注銷：如果某個基本塊B對x或者y定值，且以后沒有重新計算x

op

y，那么稱B注銷表達(dá)式xop

y。e_genB：基本塊B所產(chǎn)生的可用表達(dá)式的集合。e_killB：基本塊B所注銷掉的可用表達(dá)式的集合。e_genB和e_killB的計算對于一個基本塊B，e_genB的計算初始設(shè)置：e_genB=空；順序掃描每個語句：對于z:=x

op

y，把x

op

y加入e_genB

，從e_genB中刪除和z相關(guān)的表達(dá)式。最后的e_genB就是相應(yīng)的集合。對于一個基本塊B，e_killB的計算可用表達(dá)式數(shù)據(jù)流方程OUT[ENTRY]=

Φ在程序開始的時候，無可用表達(dá)式。B]

=

e_nB

U

(I[B]-

e_kOUT[

ge

illB)一個表達(dá)式在某個基本塊的出口點可用，或者一個表

本塊的入口點可用，必須個前驅(qū)O在某個基有前驅(qū)的是B的一達(dá)式

Bp1

p2

Np3該表達(dá)式是由它的產(chǎn)生的；或者該表達(dá)式在入口點可用，且沒有被注I銷N掉。IN[B]=

∩P

UT[p]OUTGEN要求它在所

出口點-K也IL可L

用。可用表達(dá)式計算的迭代算法輸入：一個流圖，每個基本塊的e_genB和e_killB輸出：各個基本塊入口處和出口處的可用表達(dá)式集合IN[B]和OUT[B]初始化值和前面的兩個算法不同。OUT[Bi]的初值大于實際的值。在迭代的過程中，OUT[Bi]的值逐漸縮小直到穩(wěn)定。U表示四元式的全集，就是四元式序列中所有表達(dá)式x

op

y的集合。OUT[B]初始化為表達(dá)式全集的原因例9.16數(shù)據(jù)流分析小結(jié)到達(dá)定值分析活躍變量分析可用表達(dá)式分析數(shù)據(jù)流分析的理論基礎(chǔ)有關(guān)數(shù)據(jù)流算法的基本問題數(shù)據(jù)流分析中用到的迭代算法在什么情況下是正確的？通過迭代算法得到的解準(zhǔn)確嗎？迭代算法能收斂嗎？數(shù)據(jù)流方程組的解有什么含義？通過定義一個數(shù)據(jù)流分析框架，利用離散數(shù)學(xué)中半格、偏序等概念和性質(zhì)，給出數(shù)據(jù)流分析算法的理論依據(jù)。部分冗余消除冗余：多次重復(fù)求某個表達(dá)式的值，以公共子表達(dá)式的形式出現(xiàn)，或以循環(huán)不變表達(dá)式的形式出現(xiàn)冗余消除目的：減少表達(dá)式求值的次數(shù)常常需要在很多執(zhí)行路徑中減少某個表達(dá)式求值的次數(shù)，并保證不增加任何路徑中的求值次數(shù)。盡量減少==有必要時才求需要更復(fù)雜的數(shù)據(jù)流分析技術(shù)冗余的來源全局公共子表達(dá)式循環(huán)不變表達(dá)式部分冗余表達(dá)式全局公共子表達(dá)式完全冗余，到達(dá)B4的每條路徑都計算過b+c且之后b和c沒有被定值。B4中的b+c是完全冗余b+c在B4入口點可用B2和B3的出邊的集合形成一個割集，若把該割集刪掉，則從起點到B4的路徑都被割斷循環(huán)不變表達(dá)式循環(huán)不變代碼移動部分冗余表達(dá)式冗余可能只出現(xiàn)在部分路徑上b+c在路徑B1-B2-B4冗余，在

B1-B3-B4上不冗余。放置b+c的副本來使B4中的b+c完全冗余需要添加基本塊消除的冗余關(guān)鍵邊從一個具有多個后繼的結(jié)點到達(dá)另一個具有多個前驅(qū)的節(jié)點的邊定義為流圖的關(guān)鍵邊(critical

edge)。通過在關(guān)鍵邊上引入新的基本塊，用來放置表達(dá)式，消除冗余。復(fù)制代碼以刪除冗余懶惰代碼移動部分冗余消除優(yōu)化算法目標(biāo)所有不復(fù)制代碼就能消除的表達(dá)式冗余全部消除完全冗余：基本塊B中的e完全冗余，當(dāng)且僅當(dāng)在到達(dá)B的所有路徑中，一個表達(dá)式e已經(jīng)被求過值，且之后e的分量沒有被重新定值。部分冗余：通過表達(dá)式的附加拷貝，使得部分冗余的表達(dá)式成為完全冗余。優(yōu)化后的程序不會執(zhí)行原來的程序中不執(zhí)行的運算表達(dá)式的計算盡量靠后縮短寄存器的占用時間冗余消除完全冗余部分冗余流圖中放置冗余表達(dá)式的附加拷貝，使得表達(dá)式e變成完全冗余懶惰代碼移動算法第一步：找到各個程序點上預(yù)期執(zhí)行的所有表達(dá)式如果從程序點p出發(fā)的所有路徑最終都會計算表達(dá)式b+c的值，并且b和c在那時的值就是它們在點p上的值，那么表達(dá)式b+c在程序點p上被預(yù)期執(zhí)行。第二步：在滿足表達(dá)式被預(yù)期執(zhí)行但是不可用的程序點上，放置表達(dá)式的計算第三步：把表達(dá)式盡量后延到某個程序點，在到達(dá)這個點的所有路徑上，這個表達(dá)式在這個程序點之前被預(yù)期執(zhí)行，但是還沒有使用這個值。第四步：刪除那些給只使用一次的對臨時變量賦值的語句。預(yù)期表達(dá)式如果從程序點p出發(fā)的所有路徑最終都會計算表達(dá)式b+c的值，并且b和c在那時的值就是它們在點p上的值，那么表達(dá)式b+c在程序點p上被預(yù)期執(zhí)行表達(dá)式b+c在B3、B4、B5、B6、B7和B9的入口點被預(yù)期執(zhí)行可用表達(dá)式預(yù)期執(zhí)行可以決定表達(dá)式計算的位置然而，一個基本塊B上放置的表達(dá)式的集合被定義為被預(yù)期執(zhí)行但不可用的表達(dá)式集合。理由如右圖B4可用？可后延表達(dá)式在保持程序語義并最小化冗余的情況下，把表達(dá)式的計算盡量地延后。可后延的表達(dá)式一個表達(dá)式x+y可后延到程序點p的前提如下：在所有從程序入口結(jié)點到達(dá)p的路徑中都會碰到一個位置較前的x+y，并且在最后一個這樣的位置到p之間沒有對

x+y的使用被使用的表達(dá)式表達(dá)式的活躍性分析如果從程序點p出發(fā)的一條路徑在表達(dá)式被重新求值之前使用了該表達(dá)式，那么我們說該表達(dá)式在點p上被使用。懶惰代碼移動算法運行后的結(jié)果部分冗余消除中的四個數(shù)據(jù)流分析過程懶惰代碼移動算法流圖中的循環(huán)循環(huán)對于優(yōu)化非常重要循環(huán)也是數(shù)據(jù)流分析需要經(jīng)過若干次迭代的原因識別循環(huán)循環(huán)相關(guān)概念支配節(jié)點深度優(yōu)先排序回邊