編譯原理第8章代碼優(yōu)化

第8章代碼優(yōu)化（optimization）8.1代碼優(yōu)化綜述8.2局部?jī)?yōu)化8.3控制流分析與循環(huán)查找8.4數(shù)據(jù)流分析基礎(chǔ)8.5循環(huán)優(yōu)化的實(shí)施第8章代碼優(yōu)化（optimization）.28.1.3代碼優(yōu)化概述優(yōu)化技術(shù)分類(lèi)具優(yōu)化功能編譯器的組織第8章代碼優(yōu)化（optimization）8.2.1基本塊定義與劃分8.2.2程序的控制流圖8.2.3基本塊的DAG表示與應(yīng)用Ch8代碼優(yōu)化8.1代碼優(yōu)化綜述8.1.1代碼優(yōu)化概念

代碼優(yōu)化

在不改變程序運(yùn)行效果的前提下，對(duì)被編譯的程序進(jìn)行等價(jià)變換，使之能生成更加高效的目標(biāo)代碼。

等價(jià)：不改變程序執(zhí)行效果；

優(yōu)化整體過(guò)程

變換：引起程序形式上的變 動(dòng)；

改進(jìn)、提高程序途徑

(1)改進(jìn)算法；

(2)在源程序級(jí)上等價(jià)變換；

(3)充分利用系統(tǒng)提供的程序庫(kù)；

(4)編譯時(shí)優(yōu)化等。優(yōu)化目的

產(chǎn)生高效的目標(biāo)代碼。

時(shí)間：源程序運(yùn)行時(shí)間盡可能短；

空間：程序及數(shù)據(jù)所占空間盡可能少；Ch8代碼優(yōu)化8.1代碼優(yōu)化綜述8.1.1代碼優(yōu)化概念為什么要實(shí)施優(yōu)化

優(yōu)化程度是編譯器的一個(gè)重要技術(shù)、質(zhì)量 目標(biāo)； 無(wú)法苛求用戶(hù)對(duì)源語(yǔ)言的掌握，編程技巧 ，編寫(xiě)源程序的優(yōu)化； 編譯程序固有的缺陷：不是面對(duì)一個(gè)或一 類(lèi)具體問(wèn)題的程序，而是統(tǒng)一處理該語(yǔ)言 的各種源程序，無(wú)法盡善盡美。Ch8代碼優(yōu)化8.1代碼優(yōu)化綜述8.1.1代碼優(yōu)化概念

計(jì)算a[i][j]的addr計(jì)算b[i][j]的addr

賦值例如，

inta[25][25],b[25][25]; … a[i][j]=b[i][j]; …

對(duì)a[i][j]=b[i][j]翻譯的目標(biāo)代碼：Ch8代碼優(yōu)化8.1代碼優(yōu)化綜述8.1.1代碼優(yōu)化概念重復(fù)一.優(yōu)化所涉及的源程序的范圍

局部?jī)?yōu)化—基本塊內(nèi)優(yōu)化；

循環(huán)優(yōu)化—隱式、顯式循環(huán)體內(nèi)優(yōu)化；

全局優(yōu)化—一個(gè)源程序范圍內(nèi)優(yōu)化；二.優(yōu)化相對(duì)于編譯邏輯功能實(shí)現(xiàn)的階段

中間代碼級(jí)—目標(biāo)代碼生成前的優(yōu)化；

目標(biāo)代碼級(jí)—目標(biāo)代碼生成后的優(yōu)化。Ch8代碼優(yōu)化8.1代碼優(yōu)化綜述8.1.2優(yōu)化技術(shù)分類(lèi)Ch8代碼優(yōu)化8.1代碼優(yōu)化綜述8.1.2優(yōu)化技術(shù)分類(lèi)三.優(yōu)化具體實(shí)現(xiàn)技術(shù)的角度

1.ConstantfoldingandpropagationBeforeoptimization

X=2; Y=X+10; Z=2*Y;Afteroptimization

X=2; Y=12; Z=24;常量合并、傳播2.CommonsubexpressioneliminationBeforeoptimization

d=e+f+g; y=e+f+z;Afteroptimization

x=e+f;

d=x+g; y=x+z;3.Loopinvariantcodemotion

Beforeoptimizationb=c;for(i=0;i<3;i++) d[i]=2*b+1;Afteroptimization

b=c;

z=2*b+1; for(i=0;i<3;i++) d[i]=z;Ch8代碼優(yōu)化8.1代碼優(yōu)化綜述8.1.2優(yōu)化技術(shù)分類(lèi)824.Deadstorage/assignmenteliminationBeforeoptimization

a=5; ...Afteroptimization

a=7;

a=7;5.Jump-to-jumpeliminationBeforeoptimization

if(x) ... elsegotoJ1;

J1:gotoJ2;Afteroptimization

if(x) ... elsegotoJ2;Ch8代碼優(yōu)化8.1代碼優(yōu)化綜述8.1.2優(yōu)化技術(shù)分類(lèi)6.DeadcodeeliminationBeforeoptimization

charc;a=1;Afteroptimization

a=2;

if(c>300)

else a=2;永假式Ch8代碼優(yōu)化8.1代碼優(yōu)化綜述8.1.2優(yōu)化技術(shù)分類(lèi)7.Functionembed

BeforeoptimizationintCheck(intx)；

{ return(x>10)；

}

voidmain() { ifcheck(y)) a=5；

}Afteroptimization

voidmain() { if(y>10)a=5；

}Ch8代碼優(yōu)化8.1代碼優(yōu)化綜述8.1.2優(yōu)化技術(shù)分類(lèi)8.Looptransformation(強(qiáng)度削弱)-simpleloopCsourcecodeinttable[100];step=1;for(i=0;i<100;i+=step)table[i]=0;beforeoptimizationafteroptimization

i=0;

t1=i*4;L1:table[t1]=0;

t1=t1+4;

i++; if(i<100)gotoL1

i=0;L1:t1=i*4;

table[t1]=0; i++; if(i<100)gotoL1

LoopCh8代碼優(yōu)化8.1代碼優(yōu)化綜述8.1.2優(yōu)化技術(shù)分類(lèi)9.Looptransformation-dynamicloopCsourcecode

step=step_table[1]; for(i=0;i<MAX;i+=step) table[i]=0;

beforeoptimization

step=step_table[1]; i=0;L1:t1=i*4; table[t1]=0;

i=i+step;

if(i<MAX)gotoL1

afteroptimization

i=0;

step=step_table[1];

t1=i*4;

t2=step*4;L1:table[t1]=0;

t1=t1+t2;

i=i+step;

if(i<MAX)gotoL1

(i+step)*4=i*4+step*4

t1t2Ch8代碼優(yōu)化8.1代碼優(yōu)化綜述8.1.2優(yōu)化技術(shù)分類(lèi)10.Looptransformation-composedvariablesCsourcecode

inttable[100]; for(i=0,j=0;j<10;i++,j++)

table[10*i+j]=i;

table[0]=0 table[11]=1 table[22]=2 …… table[99]=9Ch8代碼優(yōu)化8.1代碼優(yōu)化綜述8.1.2優(yōu)化技術(shù)分類(lèi)

beforeoptimization

i=0;j=0; t1=i*10;L1:t2=t1+j;/*address*/t3=t2*4;table[t3]=i;i=i+1;t1=t1+10;j=j+1;if(j<10)gotoL1afteroptimization

i=0;j=0; t1=i*10; t2=t1+j;t3=t2*4;/*t3=0*/Repeat10times:table[t3]=i;i=i+1;t3=t3+44;Ch8代碼優(yōu)化8.1代碼優(yōu)化綜述8.1.2優(yōu)化技術(shù)分類(lèi)Beforeoptimization

intx,y,z;

x=1;

y=x;

z=1;Afteroptimization

intx,y,z;

x=1;

z=1;

y=x;Ch8代碼優(yōu)化8.1代碼優(yōu)化綜述8.1.2優(yōu)化技術(shù)分類(lèi)intfoo(intn){intx; for(inti=0;i<n;i++) x++; returnx; }

AfteroptimizationCsourcecodeintfoo(intn){intx; for(inti=0;i<n/4;i++)

{x++; x++; x++; x++;

}

for(inti=0;i<n%4;i++) x++; returnx; }Ch8代碼優(yōu)化8.1代碼優(yōu)化綜述8.1.2優(yōu)化技術(shù)分類(lèi)8.1.3Ch8代碼優(yōu)化

前端 控制流 分析具優(yōu)化功能編譯器組織

代碼 生成器 代碼 變換8.1代碼優(yōu)化綜述

代碼 優(yōu)化器 數(shù)據(jù)流 分析

局部?jī)?yōu)化

指在程序的一個(gè)基本塊內(nèi)進(jìn)行的優(yōu)化。

基本塊

一順序執(zhí)行的語(yǔ)句序列，只有惟一入口和惟一出口，且分別對(duì)應(yīng)該序列的第一個(gè)語(yǔ)句和最后一個(gè)語(yǔ)句。

基本塊特點(diǎn)

基本塊內(nèi)的語(yǔ)句是順序執(zhí)行的，沒(méi)有轉(zhuǎn) 進(jìn)轉(zhuǎn)出，分叉匯合。Ch8代碼優(yōu)化8.2局部?jī)?yōu)化8.2.1基本塊定義與劃分

基本塊劃分第1步：確定每個(gè)基本塊的入口語(yǔ)句。

根據(jù)基本塊的結(jié)構(gòu)特點(diǎn)，它的入口語(yǔ)句是下述三種類(lèi)型的語(yǔ)句之一:

(1)程序的第一個(gè)語(yǔ)句；

(2)由條件轉(zhuǎn)移語(yǔ)句或無(wú)條件轉(zhuǎn)移語(yǔ)句轉(zhuǎn)移 到的語(yǔ)句；

(3)緊跟在條件轉(zhuǎn)移或無(wú)條件轉(zhuǎn)移后面的 語(yǔ)句。Ch8代碼優(yōu)化8.2局部?jī)?yōu)化8.2.1基本塊定義與劃分第3步：凡是未包含在基本塊中的語(yǔ)句，都是程序的控制流不可到達(dá)的語(yǔ)句，直接從程序中刪除。第2步：根據(jù)確定的基本塊的入口語(yǔ)句，構(gòu)造 其所屬的基本塊。即：

(1)由該入口語(yǔ)句直到下一個(gè)入口語(yǔ)句(不包含 下一個(gè)入口語(yǔ)句)之間的所有語(yǔ)句構(gòu)成一 個(gè)基本塊；

(2)由該入口語(yǔ)句到一轉(zhuǎn)移語(yǔ)句(含該轉(zhuǎn)移語(yǔ)句

)之間的所有語(yǔ)句構(gòu)成一個(gè)基本塊；或到 程序中的停止或暫停語(yǔ)句(包含該停止或 暫停語(yǔ)句)之間的語(yǔ)句序列組成的。Ch8代碼優(yōu)化8.2局部?jī)?yōu)化8.2.1基本塊定義與劃分例8.1對(duì)如下程序段實(shí)施基本塊的劃分。⑴⑵⑶⑷⑸⑹⑺⑻⑼⑽⑾

read(limit); i=1;if(i>limit)goto(11);

read(j) if(i=1)goto(8);

sum=sum+j; goto(9);

sum=j; i++; goto(3);

write(sum);1234567Ch8代碼優(yōu)化8.2局部?jī)?yōu)化8.2.1基本塊定義與劃分

基本塊的確定Step1:求四元式序列各基本塊的入口語(yǔ)句；Step2:對(duì)求出每一個(gè)的入口語(yǔ)句構(gòu)造相應(yīng)的 基本塊；Step3:凡不屬于某一基本塊中的語(yǔ)句，皆是 程序控制流程無(wú)法到達(dá)的語(yǔ)句，直接 刪除；Ch8代碼優(yōu)化8.2局部?jī)?yōu)化8.2.1基本塊定義與劃分

程序的控制流圖

具有惟一首結(jié)點(diǎn)的有向圖。流圖G為

G=(N,E,n0)其中：

N：是流圖的所有的結(jié)點(diǎn)組成的集合。流 圖中的結(jié)點(diǎn)為基本塊。

n0：是流圖的首結(jié)點(diǎn)。

E：是流圖的所有的有向邊組成的集合。Ch8代碼優(yōu)化8.2局部?jī)?yōu)化8.2.2程序的控制流圖

流圖中的有向邊Ei的形成：

設(shè)有結(jié)點(diǎn)i到結(jié)點(diǎn)k(或說(shuō)從結(jié)點(diǎn)i到結(jié)點(diǎn)k由有向邊Ei相連)可表示為ikEi其條件是

①基本塊k在流圖中的位置緊跟在基本塊i之 后且i的出口語(yǔ)句不是無(wú)條件轉(zhuǎn)移或停語(yǔ)句；

②基本塊i的出口語(yǔ)句是goto(s)或if...goto(s)

且(s)是基本塊k的入口語(yǔ)句。Ch8代碼優(yōu)化8.2局部?jī)?yōu)化8.2.2程序的控制流圖4756例8.1程序的流圖。

1 2 3Ch8代碼優(yōu)化8.2局部?jī)?yōu)化8.2.2程序的控制流圖①readx②ready③R=x/y④ifR=0goto8⑤x=y⑥y=R⑦goto3⑧writey⑨haltreadxreadyR=x/yifR=0goto8x=yy=Rgoto3writeyhaltn0n1n2n3例8.2對(duì)如下程序段劃分基本塊，給出流圖。n0n1n2n3Ch8代碼優(yōu)化8.2局部?jī)?yōu)化8.2.2程序的控制流圖Ch8代碼優(yōu)化8.2局部?jī)?yōu)化8.2.3DAG定義與應(yīng)用

DAG（DirectedAcyclicGraph）

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

定義8.1

設(shè)G是由若干結(jié)點(diǎn)構(gòu)成的有向圖，從結(jié)點(diǎn)ni到結(jié)點(diǎn)nj的有向邊用ni→nj表示。①若存在有向邊序列ni1→ni2→…→nim，則稱(chēng)結(jié)點(diǎn)ni1

與結(jié)點(diǎn)nim之間存在一條路徑，或稱(chēng)ni1與nim是連通 的。路徑上有向邊的數(shù)目為路徑的長(zhǎng)度；②如果存在一條路徑，其長(zhǎng)度≥2，且該路徑起始和 結(jié)束于同一個(gè)結(jié)點(diǎn)，則稱(chēng)該路徑是一個(gè)環(huán)路；③如果有向圖G中任一條路徑都不是環(huán)路，則稱(chēng)G

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

基本塊的DAG表示基本塊的DAG是結(jié)點(diǎn)上帶有下列標(biāo)記的DAG①葉結(jié)點(diǎn)用標(biāo)識(shí)符或常量作為其惟一的標(biāo) 記，當(dāng)葉結(jié)點(diǎn)是標(biāo)識(shí)符時(shí)，代表名字的 初值可加下標(biāo)0；②內(nèi)部結(jié)點(diǎn)用運(yùn)算符標(biāo)記，同時(shí)也表示計(jì) 算的值；③各結(jié)點(diǎn)上可以附加一個(gè)或多個(gè)標(biāo)識(shí)符， 附加在同一結(jié)點(diǎn)上的多個(gè)標(biāo)識(shí)符具有相 同的值。Ch8代碼優(yōu)化8.2局部?jī)?yōu)化8.2.3DAG定義與應(yīng)用+bc

d0b0+a0例8.3設(shè)有基本塊如下+a–cbdca+a–cb db dDAG

★注意：

流圖的一個(gè)結(jié)點(diǎn)是一個(gè)基本塊，可用DAG表示。流圖確認(rèn)的是基本塊之間的關(guān)系，DAG確認(rèn)的是基本塊內(nèi)各四元式間的關(guān)系。–a,dCh8代碼優(yōu)化8.2局部?jī)?yōu)化8.2.3DAG定義與應(yīng)用常見(jiàn)四元式與DAG結(jié)點(diǎn)對(duì)應(yīng)關(guān)系P2260型1型2型

一個(gè)結(jié)點(diǎn)(定值語(yǔ)句)

二個(gè)結(jié)點(diǎn)(單目運(yùn)算 且定值)三個(gè)結(jié)點(diǎn)(雙目運(yùn)算、取數(shù)組元素且定值，條件句)Ch8代碼優(yōu)化8.2局部?jī)?yōu)化8.2.3DAG定義與應(yīng)用常見(jiàn)四元式簡(jiǎn)化為下述三種情況(1)A=BopC(2)A=opB(3)A=B2型

1型0型情況1情況2情況3103Ch8代碼優(yōu)化8.2局部?jī)?yōu)化8.2.3DAG定義與應(yīng)用算法8.1(基本塊的DAG的構(gòu)造算法)//初始化，置DAG為空。僅考慮0型、1型和2型①輸入：一個(gè)基本塊i輸出：含有下列信息的基本塊i的DAG：

(1)

葉結(jié)點(diǎn)、內(nèi)部結(jié)點(diǎn)按統(tǒng)一標(biāo)記；

(2)

每個(gè)結(jié)點(diǎn)有一個(gè)標(biāo)識(shí)符表（可空）；算法：

對(duì)基本塊中每一四元式依次執(zhí)行以下步驟

1.

構(gòu)造葉結(jié)點(diǎn)；

2.

捕捉已知量，合并常數(shù)；

//刪除原常數(shù)結(jié)點(diǎn)//刪除冗余的公共子表達(dá)式3.

捕捉公共子表達(dá)式；4.

捕捉可能的無(wú)用賦值；情況3情況1Ch8

代碼優(yōu)化8.2

局部?jī)?yōu)化8.2.3DAG定義與應(yīng)用例8.4設(shè)有一個(gè)基本塊的語(yǔ)句序列如下

⑴⑵⑶⑷⑸⑹⑺⑻ ⑼ ⑽T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4

T6=R-r B=T5*T6Ch8代碼優(yōu)化8.2局部?jī)?yōu)化8.2.3DAG定義與應(yīng)用P228_例7.4

34

38解:構(gòu)造DAG的過(guò)程如下：

n1T03.14

n1T03.14

n2T16.28

n1T0n2T13.146.28n3

Rn5T2

+

n4

r

n1T0n2T13.146.28n6A

* n3

Rn5T2

+

n4

rCh8代碼優(yōu)化8.2局部?jī)?yōu)化8.2.3DAG定義與應(yīng)用n6A,B,T5n5

+

*n1T0n2T1,T3n3n43.146.28Rr+*n6A,Bn5T2n1T0n2T1,T3n3n43.146.28Rr+*n6A,Bn5T2n1T0n2T1n3n43.146.28Rrn6A,B

*n1T0n2T1,T3n3n5T2,T4

+

n43.146.28RrCh8代碼優(yōu)化8.2局部?jī)?yōu)化8.2.3DAG定義與應(yīng)用+n6

A,T5

*

n1

T0

n2

T1,T3

n33.146.28Rn5

T2,T4

– n4

rn7

T6n8

B*（1）T0=3.14（2）（3）（4）T1=6.28

T3=6.28

T2=R+r（5）（6）（7）T4=T2A=6.28*T2T5=AT6=R﹣rB=A*T6

（8） （9）36Ch8

代碼優(yōu)化8.2

局部?jī)?yōu)化8.2.3DAG定義與應(yīng)用本節(jié)思路

循環(huán)優(yōu)化的重要性：循環(huán)是程序中反復(fù) 執(zhí)行的代碼序列，實(shí)施循環(huán)優(yōu)化，將高 效提高目標(biāo)代碼質(zhì)量。

循環(huán)優(yōu)化的技術(shù)準(zhǔn)備：循環(huán)查找；控制 流和數(shù)據(jù)流分析。 通過(guò)控制流分析查找循環(huán)。Ch8代碼優(yōu)化8.3控制流分析與循環(huán)查找

構(gòu)成循環(huán)條件

具有下列性質(zhì)的結(jié)點(diǎn)序列為一個(gè)循環(huán)：

1.強(qiáng)連通性。

流圖中若存在任意兩個(gè)節(jié)點(diǎn)之間必有一條通路，則通路上的任何節(jié)點(diǎn)都屬于該循環(huán)。

2.入口惟一。

入口是流圖的首結(jié)點(diǎn)或結(jié)點(diǎn)序列外某結(jié)點(diǎn)有一條有向邊引到它。Ch8代碼優(yōu)化8.3控制流分析與循環(huán)查找定義8.2（循環(huán)）

程序流圖中具有惟一入口結(jié)點(diǎn)的強(qiáng)連通子圖。1234

例如右圖，{2，3}是循環(huán)

強(qiáng)連通性成立惟一結(jié)點(diǎn)2Ch8代碼優(yōu)化8.3控制流分析與循環(huán)查找{6}{4,5,6,7}強(qiáng)連通/入口6強(qiáng)連通/入口4

{2,3,4,5,6,7}強(qiáng)連通/入口2非循環(huán)：{2,4}{2,3,4}{4,6,7}強(qiáng)連通/入口2,4強(qiáng)連通/入口2,4強(qiáng)連通/入口4,712 43765

Ch8代碼優(yōu)化例如下圖，8.3控制流分析與循環(huán)查找

循環(huán)：定義8.3(必經(jīng)結(jié)點(diǎn))

在程序流圖G中，ni和nj為任意結(jié)點(diǎn)。若從n0出發(fā)，到達(dá)nj的任何一條通路都必經(jīng)過(guò)ni，則稱(chēng)ni是nj的必經(jīng)結(jié)點(diǎn)，記作niDOMnj。必經(jīng)結(jié)點(diǎn)、必經(jīng)結(jié)點(diǎn)集與回邊定義8.4(必經(jīng)結(jié)點(diǎn)集)

在程序流圖G中，結(jié)點(diǎn)n的全部必經(jīng)結(jié)點(diǎn)，稱(chēng)為結(jié)點(diǎn)n的必經(jīng)結(jié)點(diǎn)集，記作D(n)。Ch8代碼優(yōu)化8.3控制流分析與循環(huán)查找DOM是流圖結(jié)點(diǎn)集上一個(gè)偏序關(guān)系：

(1)自反性：aDOMa (2)傳遞性：如果aDOMb,bDOMc， 則有：aDOMc。

(3)反對(duì)稱(chēng)性：若有aDOMb,bDOMa,

則有：a=b。Ch8代碼優(yōu)化8.3控制流分析與循環(huán)查找3476

405

Ch8

代碼優(yōu)化例8.5

設(shè)有如下流圖

1 28.3

控制流分析與循環(huá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}

48定義8.5（回邊）

設(shè)a→b是流圖G中一條有向邊，如果

bDOMa，則稱(chēng)a→b是流圖G中的一 條回邊。記作<a,b>。例7.5流圖中存在有向邊6→6，7→4和4→2。并且有D(6)={1,2,4,6}D(7)={1,2,4,7}D(4)={1,2,4}則則則6DOM6，4DOM7，2DOM4。皆為回邊Ch8代碼優(yōu)化8.3

控制流分析與循環(huán)查找

利用回邊求出流圖中的循環(huán)： 若<n,d>是一回邊，則由結(jié)點(diǎn)d、結(jié)點(diǎn)n以及所有通路到達(dá)n而該通路不經(jīng)過(guò)d的所有結(jié)點(diǎn)序列構(gòu)成一個(gè)循環(huán)L，d是循環(huán)L的惟一入口。

例8.5流圖中的循環(huán)：

<6,6>loop={6} <7,4>loop={4,5,6,7} <4,2>loop={2,3,4,5,6,7}Ch8代碼優(yōu)化8.3控制流分析與循環(huán)查找summary(查找循環(huán)步驟)

1.確定G的D(n)；

2.由D(n)找回邊；

3.通過(guò)回邊確定循環(huán)。Ch8代碼優(yōu)化8.3控制流分析與循環(huán)查找（summary）

Ch8代碼優(yōu)化一.局部?jī)?yōu)化1.基本塊定義入口出口2.實(shí)施—DAGDAG構(gòu)造：中間code重建：已優(yōu)化

code（summary）

Ch8代碼優(yōu)化二.循環(huán)優(yōu)化中間code基本塊G

技術(shù)準(zhǔn)備控制流分析控制流分析數(shù)據(jù)流分析

LoopD(n)回邊數(shù)據(jù)流分析：中間code+控制流采集優(yōu)化所需信息Ch8代碼優(yōu)化8.4數(shù)據(jù)流分析基礎(chǔ)一.數(shù)據(jù)流分析基礎(chǔ) 數(shù)據(jù)流分析

涉及多個(gè)基本塊范圍的優(yōu)化，編譯程 序需要收集整個(gè)程序范圍內(nèi)的有關(guān)信息及 分布在程序流程圖每個(gè)基本塊的信息，這 些信息是程序中數(shù)據(jù)流的信息，這一工作 稱(chēng)為數(shù)據(jù)流分析。di:x=a*b+c;di+1:readx;

點(diǎn)：指明語(yǔ)句在流圖基本塊中的位置。

指一個(gè)中間語(yǔ)言語(yǔ)句在其代碼序列中的 位置。

如，入口點(diǎn)指基本塊第一個(gè)中間代碼前位置；出口點(diǎn)指基本塊最后一個(gè)中間代碼后位置；相鄰點(diǎn)指兩個(gè)中間代碼之間的點(diǎn)。

例如，Ch8代碼優(yōu)化8.4數(shù)據(jù)流分析基礎(chǔ)

定值點(diǎn)：

是變量x獲得值的中間代碼的位置d，稱(chēng)為x的定值點(diǎn)。dj:readx;定值方式例如，di:x=a*b+c;

賦值語(yǔ)句

輸入語(yǔ)句函數(shù)調(diào)用的形參與實(shí)參結(jié)合Ch8代碼優(yōu)化8.4數(shù)據(jù)流分析基礎(chǔ)引用點(diǎn)：

引用變量x的中間代碼的位置d，稱(chēng)為x的引用點(diǎn)。如，dj:i=i+1定值點(diǎn)引用點(diǎn)如，dk:i++引用點(diǎn)/定值點(diǎn)Ch8代碼優(yōu)化8.4數(shù)據(jù)流分析基礎(chǔ)

到達(dá)—定值：

設(shè)有流圖G，變量A在G中某點(diǎn)d的定值到達(dá)另一點(diǎn)p，是指流圖中從點(diǎn)d有一通路到達(dá)點(diǎn)p且該通路上沒(méi)有對(duì)變量A的再定值。約定：<A>—對(duì)變量A的引用；A—對(duì)變量A的定值；Ch8代碼優(yōu)化8.4數(shù)據(jù)流分析基礎(chǔ)到達(dá)—定值d:A

有此路徑，且無(wú)對(duì) 變量A的其他定值

p:…變量A在點(diǎn)d的定值到達(dá)點(diǎn)PCh8代碼優(yōu)化8.4數(shù)據(jù)流分析基礎(chǔ)d1:i=m-1d2:d3:j=na=c1d4:i=i+1d5:j=j-1……d6:a=c2……B5B4B6B3B2B1例8.6設(shè)有如下流圖Ch8代碼優(yōu)化8.4數(shù)據(jù)流分析基礎(chǔ)

定義8.6（ud鏈） 假設(shè)在程序中某點(diǎn)P引用了變量A的值，則把G中能到達(dá)P的A的定值點(diǎn)的全體，稱(chēng)為A在引用點(diǎn)P的引用─定值鏈（即ud鏈）。d1:A

d2:Adi:<A>d3:Adi-(A)ud={d1,d2,d3}Ch8代碼優(yōu)化8.4數(shù)據(jù)流分析基礎(chǔ)?ud鏈?zhǔn)窍鄬?duì)于引用點(diǎn)的定值情況。

即某變量A在點(diǎn)d的引用的ud鏈，是變量A引 用前所有可能到達(dá)d點(diǎn)的對(duì)A定值的定值表。d1:Ad2:Ad3:Adi:<A>d4:A

di-(A)ud={d1,d4,d3}d4注銷(xiāo)掉d2Ch8代碼優(yōu)化8.4數(shù)據(jù)流分析基礎(chǔ)活躍變量：

在程序中對(duì)某變量A和某點(diǎn)P，如果存在一條從P開(kāi)始的通路，其中引用了A在點(diǎn)P的值，則稱(chēng)A在點(diǎn)P是活躍的，否則稱(chēng)A在點(diǎn)P是死亡的。d1:<A>d2:<A>

d:Ad':AA在點(diǎn)d活躍

A在點(diǎn)d,d'活躍

A在點(diǎn)d'活躍，在點(diǎn)d死亡Ch8代碼優(yōu)化8.4數(shù)據(jù)流分析基礎(chǔ)

定義8.7（du鏈） 假設(shè)在程序中某點(diǎn)P對(duì)一個(gè)變量A定值，則把該定值能到達(dá)A的引用點(diǎn)的全體，稱(chēng)為A在定值點(diǎn)P的定值—引用鏈（即du鏈）。

?du鏈?zhǔn)窍鄬?duì)于定值點(diǎn)的引用情況。

即某變量A在點(diǎn)d的定值的du鏈，是變量A定 值后所有可能的引用表。Ch8代碼優(yōu)化8.4數(shù)據(jù)流分析基礎(chǔ)d1:<A>d:A

對(duì)變量A：

d-du={d1,d2}d2:<A>du鏈Ch8代碼優(yōu)化8.4數(shù)據(jù)流分析基礎(chǔ)例8.7設(shè)有流圖

B1di:……dj:<t>tB4B3B2dj+1:

B5dk+2:<t>dk:<t>dk+1:t

B6tt在點(diǎn)dk+2的ud鏈={dj+1,dk+1}t在點(diǎn)dk的ud鏈={di,dj+1,dk+1}t在點(diǎn)di的du鏈={dj,dk}dk+2?t在點(diǎn)dj+1的du鏈

={dk+2,dj,dk}Ch8代碼優(yōu)化8.4數(shù)據(jù)流分析基礎(chǔ)

二.重要數(shù)據(jù)流方程

編譯器把程序的一部分或全部看作一個(gè)整體來(lái)收集信息，并把收集的信息分配給流圖中的各個(gè)基本塊。

到達(dá)定值信息—完成常量合并，刪除無(wú) 用賦值；

活躍變量信息—寄存器優(yōu)化；

公共子表達(dá)式信息—?jiǎng)h除冗余運(yùn)算。Ch8代碼優(yōu)化8.4數(shù)據(jù)流分析基礎(chǔ)

典型的數(shù)據(jù)流方程

out[B]=gen[B]∪(in[B]–kill[B])

其中：

B表示G中某個(gè)基本塊，也可以為語(yǔ)句；含義：

當(dāng)控制流通過(guò)一個(gè)基本塊時(shí)，在基本塊末尾得到的信息(out)是在該基本塊中產(chǎn)生的信息(gen)，或是進(jìn)入基本塊開(kāi)始點(diǎn)(in)且沒(méi)有被該基本塊注銷(xiāo)的信息(kill)；Ch8代碼優(yōu)化8.4數(shù)據(jù)流分析基礎(chǔ)

制約建立和求解數(shù)據(jù)流方程的因素1.產(chǎn)生、注銷(xiāo)的概念依賴(lài)所需要的信息，考 慮數(shù)據(jù)流方向：前后（每個(gè)基本塊Bi的有關(guān)信息利用其

前驅(qū)基本塊的信息來(lái)計(jì)算）如，到達(dá)—定值，可用表達(dá)式，復(fù)寫(xiě)傳播。

由in[B]決定out[B]Ch8代碼優(yōu)化8.4數(shù)據(jù)流分析基礎(chǔ)后前（每個(gè)基本塊Bi的有關(guān)信息利用其

后繼基本塊的信息來(lái)計(jì)算）

如，活躍變量，非常忙表達(dá)式等。

由out[B]決定in[B]2.由于數(shù)據(jù)沿流圖的控制路徑流動(dòng)，故數(shù)據(jù) 流分析受程序控制結(jié)構(gòu)影響。Ch8代碼優(yōu)化8.4數(shù)據(jù)流分析基礎(chǔ)

到達(dá)—定值數(shù)據(jù)流方程

在數(shù)據(jù)流分析中采集程序中量的定值情況(即到達(dá)點(diǎn)P的各變量的全部定值點(diǎn)信息)。

in(Bi):能到達(dá)基本塊Bi入口點(diǎn)之前的各個(gè) 變量的所有定值點(diǎn)集。

out(Bi):能到達(dá)基本塊Bi出口之后的各變量 定值點(diǎn)的集合。gen(Bi):在Bi中定值且能到達(dá)Bi出口之后的 所有定值點(diǎn)集。Ch8代碼優(yōu)化8.4數(shù)據(jù)流分析基礎(chǔ)kill(Bi):在基本塊Bi外定值，且在Bi中又重新 定值的那些變量的定值點(diǎn)的集合。out(B)=in(B)–kill(B)∪gen(B)(8.1)in(B)=∪out(P)P∈Pred(B)(8.2)到達(dá)—定值方程

其中：

gen(B)和kill(B)可從其定義出發(fā)，直接從給定的流圖求出。

P(B)表示B的所有前驅(qū)基本塊的集合。Ch8代碼優(yōu)化8.4數(shù)據(jù)流分析基礎(chǔ)

B1

d1:i=m-1 d2:j=n d3:a=u1

B2

d4:i=i+1 d5:j=j-1

B3d6:a=u2

B4

d7:j=u3例8.8設(shè)有流圖

合流算符Ch8代碼優(yōu)化8.4數(shù)據(jù)流分析基礎(chǔ)gen(B)kill(B)B1B2B3B4{d1,d2,d3}{d4,d5}{d6}{d7}

{d4,d5,d6,d7} {d1,d2,d7}{d3} {d2,d5}Ch8代碼優(yōu)化8.4數(shù)據(jù)流分析基礎(chǔ)對(duì)out(B)，可由以下條件得到：①如果某定值點(diǎn)d在in(B)中，而且被d定值的變量在

B中未被重新定值，則d也在out(B)中；②如果定值點(diǎn)d在gen(B)中,則它一定在out(B)中；③除以上兩種情況外，沒(méi)有其它定值點(diǎn)d∈out(B)。 而對(duì)于in(B)，則可知，某定值點(diǎn)d到達(dá)基本塊B的 入口點(diǎn)，當(dāng)且僅當(dāng)它到達(dá)B的某一前驅(qū)基本塊的出 口點(diǎn)。

對(duì)in(B):

是B的所有前驅(qū)基本塊的out之和。Ch8代碼優(yōu)化8.4數(shù)據(jù)流分析基礎(chǔ)算法8.2（到達(dá)—定值）輸入：G中每個(gè)基本塊B的kill[B]和gen[B]輸出：G中每個(gè)基本塊B的in[B]和out[B]方法：{

for(i=1;i<=N;i++) {in[Bi]=Φ;out[Bi]=gen[Bi];/*in[Bi]和out[Bi]的迭代初值*/}change=“真”;while(change)/*change記錄相繼2次迭代所得的in[Bi]之值不等則為“真”， 需要繼續(xù)迭代；若相等，則迭代過(guò)程結(jié)束，其值為“假”*{change=“假”; for(i=1;i<=N;i++)

/*P∈Pred(Bi)/*NEWIN記錄每次迭代后IN[Bi]的新值*{NEWIN=∪out[P]; if(NEWIN!=in[Bi]) {change=“真”;

in[Bi]=NEWIN; out[Bi]=gen[Bi]∪(in[Bi]-kill[Bi]); }

}}利用到達(dá)—定值信息計(jì)算ud鏈

(1)若在基本塊B中，某變量A的引用點(diǎn)u之前有A

的定值點(diǎn)d，且d點(diǎn)A的定值能到達(dá)點(diǎn)u,則A在u

點(diǎn)的ud鏈為e2ihhmq；

(2)若在基本塊B中，某變量A的引用點(diǎn)u之前無(wú)A

的定值點(diǎn)，則包含在IN[B]中的全部A的定值點(diǎn) 均可到達(dá)點(diǎn)u,所以in[B]中的這些A的定值點(diǎn)組 成A在u點(diǎn)的ud鏈。Ch8代碼優(yōu)化8.4數(shù)據(jù)流分析基礎(chǔ)可用表達(dá)式數(shù)據(jù)流方程

表達(dá)式x+y在點(diǎn)P可用：

如果從初始結(jié)點(diǎn)到P的每條路徑上都 計(jì)算x+y，并且在最后一個(gè)x+y到P之間未 對(duì)x或y定值，則表達(dá)式x+y在點(diǎn)P可用。 若有對(duì)x或y的定值，則可用的x+y被 注銷(xiāo)。Ch8代碼優(yōu)化8.4數(shù)據(jù)流分析基礎(chǔ)B1t1=4*i t2=4*iB2

…B3B1t1=4*i t2=4*iB2

it0=4*iB3B2中沒(méi)有對(duì)變量i的定值，則B1中的4*i在B3開(kāi)始點(diǎn)可用。B2中對(duì)變量i定值后又計(jì)算4*i，則B1中的4*i在B3開(kāi)始點(diǎn)不一定的可用。Ch8代碼優(yōu)化8.4數(shù)據(jù)流分析基礎(chǔ)可用表達(dá)式數(shù)據(jù)流方程out[B]=in[B]–kill[B]∪gen[B](8.3)(8.4)(B不是開(kāi)始?jí)K) (B1是開(kāi)始?jí)K)in(B)=∩out[P]

P是B的前驅(qū)

設(shè)in(B1)=Φ**與到達(dá)—定值區(qū)別：

(1)開(kāi)始?jí)K的處理特殊；(∵開(kāi)始?jí)K無(wú)任何表達(dá)式可用)

(2)合流算符是∩；(∵一個(gè)表達(dá)式在塊的開(kāi)始點(diǎn)可用， 只有當(dāng)它在該塊的所有前趨塊的 結(jié)束點(diǎn)可用時(shí)才行)Ch8代碼優(yōu)化8.4數(shù)據(jù)流分析基礎(chǔ)活躍變量數(shù)據(jù)流方程

inL(B)=outL(B)–defL(B)∪useL(B)(8.5)(8.6)outL(B)=∪inL(S)

S∈Succ(B)defL(B)：在基本塊B中定值，且定值之前未曾在B中 引用過(guò)的變量的集合。useL(B)：在基本塊B中引用的，但在引用前未曾在B

中定值的變量集。Ch8代碼優(yōu)化8.4數(shù)據(jù)流分析基礎(chǔ)inL(B):在基本塊B入口點(diǎn)的活躍變量的 集合。

outL(B)：在基本塊B的出口點(diǎn)的活躍變量的 集合。Ch8代碼優(yōu)化8.4數(shù)據(jù)流分析基礎(chǔ)Ch8代碼優(yōu)化8.5循環(huán)優(yōu)化實(shí)施ud鏈du鏈可實(shí)施的循環(huán)優(yōu)化代碼外提(頻度削弱)強(qiáng)度削弱刪除歸納變量循環(huán)展開(kāi)、合并…循環(huán)優(yōu)化準(zhǔn)備

1.循環(huán)查找；(控制流分析) 2.涉及循環(huán)的所有基本塊據(jù)流是沿著控制流

量的定值——引用情況信息數(shù)的數(shù)據(jù)流分析：

循環(huán)的前置結(jié)點(diǎn)

循環(huán)的前置結(jié)點(diǎn)是在循環(huán)的入口結(jié)點(diǎn)前建立的一個(gè)新結(jié)點(diǎn)（基本塊），它以循環(huán)的入口結(jié)點(diǎn)為其惟一后繼，并將原程序流圖中從循環(huán)外引至循環(huán)入口結(jié)點(diǎn)的有向邊改引至循環(huán)前置結(jié)點(diǎn)。

∵循環(huán)的入口惟一∴前置結(jié)點(diǎn)惟一Ch7代碼優(yōu)化7.5循環(huán)優(yōu)化實(shí)施L...

Bk

循環(huán)L的入口結(jié)點(diǎn) 循環(huán)L建立前置結(jié)點(diǎn)B0前的循環(huán)LBi

Bj...例8.9設(shè)有流圖(如下面左圖)...Bi

Bj...

B0

循環(huán)L的前置結(jié)點(diǎn)

Bk循環(huán)L的入口結(jié)點(diǎn) 循環(huán)L建立循環(huán)L的前置結(jié)點(diǎn)B0后Ch7代碼優(yōu)化7.5循環(huán)優(yōu)化實(shí)施

一.代碼外提

代碼外提就是將循環(huán)中的不變運(yùn)算提到循 環(huán)的前置結(jié)點(diǎn)中。這里所指的不變運(yùn)算，是指 與循環(huán)執(zhí)行次數(shù)無(wú)關(guān)的運(yùn)算或不受循環(huán)控制變 量影響的那些運(yùn)算。

例如，設(shè)循環(huán)L中有形如A=BopC的語(yǔ)句，如果B和C是常數(shù)，或者B和C雖然是變量，但到達(dá)B和C的定值點(diǎn)皆在循環(huán)L外，則在循環(huán)中每次計(jì)算出的BopC的值始終不變。Ch7代碼優(yōu)化7.5循環(huán)優(yōu)化實(shí)施例8.10給出以下源程序及該程序流圖

B3I=I+1gotoB2

B4L2:…

B1

A=0 I=1 B2

B=J+1

C=B+I A=C+AifI=100gotoB4Ch8代碼優(yōu)化8.5循環(huán)優(yōu)化實(shí)施

A=0；

I=1；L1:B=J+1；

C=B+I；

A=C+A；

if(I=100)gotoL2；

I=I+1；L2:gotoL1；

…<B3,B2>loop={B2，B3}A=0

A=C+AifI=100gotoB4

I=I+1gotoB2

I=1B=J+1

C=B+IB1B2′

B2B3

B4L2：…Ch8代碼優(yōu)化8.5循環(huán)優(yōu)化實(shí)施循環(huán)中，B2中的語(yǔ)句B=J+1，由于循環(huán)中沒(méi)有對(duì)J的定值點(diǎn)，所以J的所有引用的定值點(diǎn)都在循環(huán)外，它是循環(huán)的不變運(yùn)算，可提到循環(huán)的前置結(jié)點(diǎn)B2′中。代碼外提算法的設(shè)計(jì)

(1)查找循環(huán)中的不變運(yùn)算；（X1）(2)實(shí)施代碼外提；（X2）算法8.3（X1:查找循環(huán)中不變運(yùn)算）

設(shè)有循環(huán)L

輸入：循環(huán)L；L中的所有變量引用點(diǎn)的ud鏈信息；

輸出：查找、標(biāo)識(shí)“不變運(yùn)算”后的循環(huán)L；Ch8代碼優(yōu)化8.5循環(huán)優(yōu)化實(shí)施方法：

(1)依次查看L中各基本塊的每個(gè)語(yǔ)句，如果其中 的每個(gè)運(yùn)算對(duì)象為常數(shù)或定值點(diǎn)在L外（據(jù)ud

鏈判斷），將該語(yǔ)句標(biāo)記為“不變運(yùn)算”；(2)重復(fù)第(3)步，直至沒(méi)有新的語(yǔ)句被標(biāo)記為“

不變運(yùn)算”為止；(3)依次查看未被標(biāo)記為“不變運(yùn)算”的語(yǔ)句，如果 其運(yùn)算對(duì)象為常數(shù)或定值點(diǎn)在L外，或只有一 個(gè)到達(dá)-定值點(diǎn)且該點(diǎn)上的語(yǔ)句已標(biāo)記為“不 變運(yùn)算”，則將被查看的語(yǔ)句標(biāo)為“不變運(yùn)算”。Ch8代碼優(yōu)化8.5循環(huán)優(yōu)化實(shí)施

算法8.4（X2:代碼外提）

輸入：循環(huán)L；ud鏈信息和必經(jīng)結(jié)點(diǎn)D(ni)信息

輸出：L';(加前置塊，已經(jīng)外提“不變運(yùn)算”

后的循環(huán)L)方法：

(1)求出循環(huán)L中所有不變運(yùn)算。(callX1)

(2)對(duì)(1)求出的每一不變運(yùn)算

S：A=BopC或A=opB或A=B，

檢查是否滿(mǎn)足如下條件之一：Ch8代碼優(yōu)化8.5循環(huán)優(yōu)化實(shí)施Ch8代碼優(yōu)化8.5循環(huán)優(yōu)化實(shí)施

①

（i）S所在的結(jié)點(diǎn)是L的所有出口結(jié)點(diǎn)的必經(jīng) 結(jié)點(diǎn)；

（ii）A在L中其它地方未再定值；

（iii）L中所有A的引用點(diǎn)只有S中A的定值才 能到達(dá)；②A在離開(kāi)L后不再是活躍的，且條件①的(ii)

和(iii)成立。所指的A在離開(kāi)L后不再是活躍 的是指，A在L的任何出口結(jié)點(diǎn)的后繼結(jié)點(diǎn)

(指不屬于L的后繼）的入口處不是活躍的。

94(3)按第(1)步找出的不變運(yùn)算的順序，依次

把符合(2)的條件之一的不變運(yùn)算S外提 到L的前置結(jié)點(diǎn)中。但若S中的運(yùn)算對(duì)象 （B或C）是在L中定值的，那么，只有 當(dāng)這些定值語(yǔ)句都提到前置結(jié)點(diǎn)中后，才 可把S也外提。Ch8代碼優(yōu)化8.5循環(huán)優(yōu)化實(shí)施說(shuō)明外提的限制條件：

**di所在的結(jié)點(diǎn)是L的所有出口結(jié)點(diǎn)的必經(jīng) 結(jié)點(diǎn)；（i） 否則，將“不變運(yùn)算”外提后，會(huì)改變程 序的計(jì)算結(jié)果。Ch8代碼優(yōu)化8.5循環(huán)優(yōu)化實(shí)施L={B2,B3,B4}

不變運(yùn)算i=1j=iB1B2

ifu<vgotoB3

B3i=2u=u+1

B4

v=v-1 ifv<=20gotoB5B5例8.11設(shè)有流圖Ch8代碼優(yōu)化8.5循環(huán)優(yōu)化實(shí)施ifu<vgotoB3j=iB2

B3u=u+1

B4

v=v-1 ifv<=20gotoB5B5i=1

i=2B1

B0外提不變運(yùn)算后的流圖90Ch8代碼優(yōu)化8.5循環(huán)優(yōu)化實(shí)施**在L對(duì)i不止一次定值情況下不允許外提i=1i=3i=2u=u+1j=iB1B2ifu<vgotoB3

B3

B4

v=v-1ifv<=20gotoB5B5條件(i)不能阻擋將i=3外提90Ch8代碼優(yōu)化8.5循環(huán)優(yōu)化實(shí)施**L中所有A的引用點(diǎn)只有S中A的定值才能到達(dá)；i=1ifu<vgotoB4j=iB1B2

B3

i=2u=u+1

B4

k=i;v=v-1; ifv<=20gotoB5B5Ch8代碼優(yōu)化8.5循環(huán)優(yōu)化實(shí)施二.強(qiáng)度削弱與刪除歸納變量

強(qiáng)度削弱是將程序中強(qiáng)度高的運(yùn)算使用強(qiáng)度低的運(yùn)算替代，以便使程序運(yùn)行時(shí)間縮短。一般情況循環(huán)L中存在I=I±C且L中存在T=K*I±C呈線(xiàn)性函數(shù)求出遞增(減)量K1，用±替代*T=T±K1（T是歸納變量I是基本歸納變量）Ch8代碼優(yōu)化8.5循環(huán)優(yōu)化實(shí)施

定義8.8（基本歸納變量/歸納變量） 如果循環(huán)中變量I僅有惟一的I=I±C形式的賦值，其中C為循環(huán)不變量，則稱(chēng)I為循環(huán)中基本歸納變量。 如果I是循環(huán)中一基本歸納變量，變量J在循環(huán)中的定值總可化為I的同一線(xiàn)性函數(shù)的形式：J=C1*I±C2，其中C1，C2是循環(huán)不變量，則稱(chēng)J是歸納變量，并稱(chēng)J與I同族。Ch8代碼優(yōu)化8.5循環(huán)優(yōu)化實(shí)施循環(huán)優(yōu)化中強(qiáng)度削弱和刪除歸納變量

有次序且相關(guān)

W1(尋找歸納變量)

W2(強(qiáng)度削弱)

W3(刪除歸納變量)Ch8代碼優(yōu)化8.5循環(huán)優(yōu)化實(shí)施

算法8.5(W1：查找歸納變量)輸入：帶有到達(dá)—定值信息和循環(huán)不變運(yùn)算信息的循 環(huán)L輸出：查找循環(huán)L中的一組歸納變量方法：

step1:掃描L，找出所有基本歸納變量；（I=I±C）

step2:尋找L中只有一個(gè)定值的K（歸納變量），其形式為：K=J*C;K=C*J;K=J/C;K=J±C;K=C±J（其中：C為循環(huán)不變量；J為基本歸納變量或歸納變量；）Ch8代碼優(yōu)化8.5循環(huán)優(yōu)化實(shí)施(1)若J是基本歸納變量，K在J族中；{K、J同族}(2)若J是歸納變量，J∈K族，K、J、I同族的附加 要求：

a)在L中對(duì)J的惟一定值和對(duì)K的定值間沒(méi)有對(duì)I的 定值；

b)L外沒(méi)有J的定值可到達(dá)K；

**找出一族歸納變量，可以變換計(jì)算歸納變量的指令（*+）Ch8代碼優(yōu)化8.5循環(huán)優(yōu)化實(shí)施

算法8.6(W2：強(qiáng)度削弱)

輸入：帶有到達(dá)—定值信息的L和歸納變量族輸出：進(jìn)行強(qiáng)度削弱優(yōu)化后的L方法：依次考察基本歸納變量I，對(duì)每個(gè)形如

J=C*I±d的四元式：

step1:建立新變量S;

step2:用J=S代替原對(duì)J的定值;

step3:在L中每個(gè)I=I+n(n為常量)的四元式后加上

S=S+C*n;

step4:保證S在L入口的初值為C*I+d;Ch8代碼優(yōu)化8.5循環(huán)優(yōu)化實(shí)施算法8.7(W3：刪除歸納變量)輸入：帶有到達(dá)—定值信息、循環(huán)不變運(yùn)算信息和活 躍變量信息的L輸出：刪除歸納變量?jī)?yōu)化后的L方法：考察每個(gè)僅用于計(jì)算同族中其它歸納變量和條件分支的基本歸納變量I，取I族的一個(gè)歸納變量一個(gè)歸納變量J，將含I的測(cè)試改為用J代替。

據(jù)du鏈信息

替代后的I不再引用時(shí)，從L中刪去對(duì)I定值的語(yǔ)句Ch8代碼優(yōu)化8.5循環(huán)優(yōu)化實(shí)施例8.12

P243—例7.6(自學(xué))Ch8代碼優(yōu)化8.5循環(huán)優(yōu)化實(shí)施一.中間代碼的選擇1.便于生成目標(biāo)代碼；2.便于優(yōu)化；二.確定實(shí)施各類(lèi)優(yōu)化的內(nèi)容、次序和具體技術(shù)1.內(nèi)容：適合實(shí)施的具體優(yōu)化工作；2.次序：對(duì)提高優(yōu)化效率，減少優(yōu)化代價(jià)很重 要。

Ch8代碼優(yōu)化實(shí)施優(yōu)化的綜合考慮

綜合應(yīng)用各類(lèi)優(yōu)化技術(shù)的共性應(yīng)考慮的因素：循環(huán)優(yōu)化全局優(yōu)化局部?jī)?yōu)化會(huì)加入新的基本塊調(diào)整語(yǔ)句，撤消某個(gè)基本塊

Ch7代碼優(yōu)化控制流分析 數(shù)據(jù)流分析控制流、數(shù) 據(jù)流分析

完 善Ch7代碼優(yōu)化三.平衡提高優(yōu)化效率、減少優(yōu)化代價(jià)的矛盾

優(yōu)化效率本身的矛盾：代碼執(zhí)行時(shí)間的減少；存儲(chǔ)空間占用的減少；優(yōu)化考慮嚴(yán)密、完善，不顧及完成優(yōu)化所花費(fèi) 的代價(jià)，則會(huì)相對(duì)抵消整個(gè)編譯程序的效率、 質(zhì)量甚至影響優(yōu)化的實(shí)際效率；策略：針對(duì)具體問(wèn)題抓住主要矛盾，估計(jì)主要因素；如，*目標(biāo)機(jī)環(huán)境；*循環(huán)優(yōu)化：最內(nèi)層優(yōu)化；*數(shù)據(jù)流分析信息對(duì)優(yōu)化的應(yīng)用價(jià)值；*通用、專(zhuān)用性語(yǔ)言，庫(kù)函數(shù)、包…[1]如果NODE(B)無(wú)定義，則建立一標(biāo)記為B的葉子結(jié)點(diǎn)；①對(duì)情況3，則令NODE(B)=n，即葉子結(jié)點(diǎn)B編號(hào)為n，轉(zhuǎn)[4]；②對(duì)情況2，轉(zhuǎn)[2]的①；③對(duì)情況1，如果NODE(C)無(wú)定義，則建立一標(biāo)記為C的葉 子結(jié)點(diǎn)，并轉(zhuǎn)[2]的②；[2]//常量合并①