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

第8章代碼優(yōu)化（optimization）8.1代碼優(yōu)化綜述8.2局部優(yōu)化8.3控制流分析與循環(huán)查找8.4數(shù)據(jù)流分析基礎(chǔ)8.5循環(huán)優(yōu)化的實施第8章代碼優(yōu)化（optimization）.28.1.3代碼優(yōu)化概述優(yōu)化技術(shù)分類具優(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)化

在不改變程序運行效果的前提下，對被編譯的程序進行等價變換，使之能生成更加高效的目標代碼。

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

優(yōu)化整體過程

變換：引起程序形式上的變 動；

改進、提高程序途徑

(1)改進算法；

(2)在源程序級上等價變換；

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

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

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

時間：源程序運行時間盡可能短；

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

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

計算a[i][j]的addr計算b[i][j]的addr

賦值例如，

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

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

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

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

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

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

目標代碼級—目標代碼生成后的優(yōu)化。Ch8代碼優(yōu)化8.1代碼優(yōu)化綜述8.1.2優(yōu)化技術(shù)分類Ch8代碼優(yōu)化8.1代碼優(yōu)化綜述8.1.2優(yōu)化技術(shù)分類三.優(yōu)化具體實現(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ù)分類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ù)分類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ù)分類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ù)分類8.Looptransformation(強度削弱)-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ù)分類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ù)分類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ù)分類

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ù)分類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ù)分類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ù)分類8.1.3Ch8代碼優(yōu)化

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

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

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

局部優(yōu)化

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

基本塊

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

基本塊特點

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

基本塊劃分第1步：確定每個基本塊的入口語句。

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

(1)程序的第一個語句；

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

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

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

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

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

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局部優(yōu)化8.2.1基本塊定義與劃分

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

程序的控制流圖

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

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

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

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

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

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

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

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

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

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

1 2 3Ch8代碼優(yōu)化8.2局部優(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對如下程序段劃分基本塊，給出流圖。n0n1n2n3Ch8代碼優(yōu)化8.2局部優(yōu)化8.2.2程序的控制流圖Ch8代碼優(yōu)化8.2局部優(yōu)化8.2.3DAG定義與應(yīng)用

DAG（DirectedAcyclicGraph）

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

定義8.1

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

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

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

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

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

★注意：

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

一個結(jié)點(定值語句)

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

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

(1)

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

(2)

每個結(jié)點有一個標識符表（可空）；算法：

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

1.

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

2.

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

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

捕捉公共子表達式；4.

捕捉可能的無用賦值；情況3情況1Ch8

代碼優(yōu)化8.2

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

⑴⑵⑶⑷⑸⑹⑺⑻ ⑼ ⑽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局部優(yōu)化8.2.3DAG定義與應(yīng)用P228_例7.4

34

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

n1T03.14

n1T03.14

n2T16.28

n1T0n2T13.146.28n3

Rn5T2

+

n4

r

n1T0n2T13.146.28n6A

* n3

Rn5T2

+

n4

rCh8代碼優(yōu)化8.2局部優(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局部優(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

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

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

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

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

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

1.強連通性。

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

2.入口惟一。

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

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

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

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

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

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

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

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

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

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

(3)反對稱性：若有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，則稱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é)點d、結(jié)點n以及所有通路到達n而該通路不經(jīng)過d的所有結(jié)點序列構(gòu)成一個循環(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.通過回邊確定循環(huán)。Ch8代碼優(yōu)化8.3控制流分析與循環(huán)查找（summary）

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

code（summary）

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

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

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

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

點：指明語句在流圖基本塊中的位置。

指一個中間語言語句在其代碼序列中的 位置。

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

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

定值點：

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

賦值語句

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

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

到達—定值：

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

有此路徑，且無對 變量A的其他定值

p:…變量A在點d的定值到達點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è)在程序中某點P引用了變量A的值，則把G中能到達P的A的定值點的全體，稱為A在引用點P的引用─定值鏈（即ud鏈）。d1:A

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

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

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

在程序中對某變量A和某點P，如果存在一條從P開始的通路，其中引用了A在點P的值，則稱A在點P是活躍的，否則稱A在點P是死亡的。d1:<A>d2:<A>

d:Ad':AA在點d活躍

A在點d,d'活躍

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

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

?du鏈是相對于定值點的引用情況。

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

對變量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在點dk+2的ud鏈={dj+1,dk+1}t在點dk的ud鏈={di,dj+1,dk+1}t在點di的du鏈={dj,dk}dk+2?t在點dj+1的du鏈

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

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

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

到達定值信息—完成常量合并，刪除無 用賦值；

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

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

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

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

其中：

B表示G中某個基本塊，也可以為語句；含義：

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

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

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

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

后繼基本塊的信息來計算）

如，活躍變量，非常忙表達式等。

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

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

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

in(Bi):能到達基本塊Bi入口點之前的各個 變量的所有定值點集。

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

其中：

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ǔ)對out(B)，可由以下條件得到：①如果某定值點d在in(B)中，而且被d定值的變量在

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

對in(B):

是B的所有前驅(qū)基本塊的out之和。Ch8代碼優(yōu)化8.4數(shù)據(jù)流分析基礎(chǔ)算法8.2（到達—定值）輸入：G中每個基本塊B的kill[B]和gen[B]輸出：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ù)迭代；若相等，則迭代過程結(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]); }

}}利用到達—定值信息計算ud鏈

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

的定值點d，且d點A的定值能到達點u,則A在u

點的ud鏈為lnynobw；

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

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

表達式x+y在點P可用：

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

…B3B1t1=4*i t2=4*iB2

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

P是B的前驅(qū)

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

(1)開始塊的處理特殊；(∵開始塊無任何表達式可用)

(2)合流算符是∩；(∵一個表達式在塊的開始點可用， 只有當(dāng)它在該塊的所有前趨塊的 結(jié)束點可用時才行)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中 引用過的變量的集合。useL(B)：在基本塊B中引用的，但在引用前未曾在B

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

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

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

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

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

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

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

Bk

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

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

Bj...

B0

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

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

一.代碼外提

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

例如，設(shè)循環(huán)L中有形如A=BopC的語句，如果B和C是常數(shù)，或者B和C雖然是變量，但到達B和C的定值點皆在循環(huán)L外，則在循環(huán)中每次計算出的BopC的值始終不變。Ch7代碼優(yōu)化7.5循環(huán)優(yōu)化實施例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)化實施

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)化實施循環(huán)中，B2中的語句B=J+1，由于循環(huán)中沒有對J的定值點，所以J的所有引用的定值點都在循環(huán)外，它是循環(huán)的不變運算，可提到循環(huán)的前置結(jié)點B2′中。代碼外提算法的設(shè)計

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

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

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

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

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

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

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

算法8.4（X2:代碼外提）

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

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

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

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

(2)對(1)求出的每一不變運算

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

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

①

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

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

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

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

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

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

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

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

不變運算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)化實施ifu<vgotoB3j=iB2

B3u=u+1

B4

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

i=2B1

B0外提不變運算后的流圖90Ch8代碼優(yōu)化8.5循環(huán)優(yōu)化實施**在L對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)化實施**L中所有A的引用點只有S中A的定值才能到達；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)化實施二.強度削弱與刪除歸納變量

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

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

有次序且相關(guān)

W1(尋找歸納變量)

W2(強度削弱)

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

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

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

step2:尋找L中只有一個定值的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)化實施(1)若J是基本歸納變量，K在J族中；{K、J同族}(2)若J是歸納變量，J∈K族，K、J、I同族的附加 要求：

a)在L中對J的惟一定值和對K的定值間沒有對I的 定值；

b)L外沒有J的定值可到達K；

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

算法8.6(W2：強度削弱)

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

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

step1:建立新變量S;

step2:用J=S代替原對J的定值;

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

S=S+C*n;

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

據(jù)du鏈信息

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

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

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

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

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

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

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