第8章代碼優化（optimization）8.1代碼優化綜述8.2局部優化8.3控制流分析與循環查找8.4數據流分析基礎8.5循環優化的實施第8章代碼優化（optimization）.28.1.3代碼優化概述優化技術分類具優化功能編譯器的組織第8章代碼優化（optimization）8.2.1基本塊定義與劃分8.2.2程序的控制流圖8.2.3基本塊的DAG表示與應用Ch8代碼優化8.1代碼優化綜述8.1.1代碼優化概念

代碼優化

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

等價：不改變程序執行效果；

優化整體過程

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

改進、提高程序途徑

(1)改進算法；

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

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

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

產生高效的目標代碼。

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

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

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

計算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代碼優化8.1代碼優化綜述8.1.1代碼優化概念重復一.優化所涉及的源程序的范圍

局部優化—基本塊內優化；

循環優化—隱式、顯式循環體內優化；

全局優化—一個源程序范圍內優化；二.優化相對于編譯邏輯功能實現的階段

中間代碼級—目標代碼生成前的優化；

目標代碼級—目標代碼生成后的優化。Ch8代碼優化8.1代碼優化綜述8.1.2優化技術分類Ch8代碼優化8.1代碼優化綜述8.1.2優化技術分類三.優化具體實現技術的角度

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代碼優化8.1代碼優化綜述8.1.2優化技術分類824.Deadstorage/assignmenteliminationBeforeoptimization

a=5; ...Afteroptimization

a=7;

a=7;5.Jump-to-jumpeliminationBeforeoptimization

if(x) ... elsegotoJ1;

J1:gotoJ2;Afteroptimization

if(x) ... elsegotoJ2;Ch8代碼優化8.1代碼優化綜述8.1.2優化技術分類6.DeadcodeeliminationBeforeoptimization

charc;a=1;Afteroptimization

a=2;

if(c>300)

else a=2;永假式Ch8代碼優化8.1代碼優化綜述8.1.2優化技術分類7.Functionembed

BeforeoptimizationintCheck(intx)；

{ return(x>10)；

}

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

}Afteroptimization

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

}Ch8代碼優化8.1代碼優化綜述8.1.2優化技術分類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代碼優化8.1代碼優化綜述8.1.2優化技術分類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代碼優化8.1代碼優化綜述8.1.2優化技術分類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代碼優化8.1代碼優化綜述8.1.2優化技術分類

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代碼優化8.1代碼優化綜述8.1.2優化技術分類Beforeoptimization

intx,y,z;

x=1;

y=x;

z=1;Afteroptimization

intx,y,z;

x=1;

z=1;

y=x;Ch8代碼優化8.1代碼優化綜述8.1.2優化技術分類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代碼優化8.1代碼優化綜述8.1.2優化技術分類8.1.3Ch8代碼優化

前端 控制流 分析具優化功能編譯器組織

代碼 生成器 代碼 變換8.1代碼優化綜述

代碼 優化器 數據流 分析

局部優化

指在程序的一個基本塊內進行的優化。

基本塊

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

基本塊特點

基本塊內的語句是順序執行的，沒有轉 進轉出，分叉匯合。Ch8代碼優化8.2局部優化8.2.1基本塊定義與劃分

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

根據基本塊的結構特點，它的入口語句是下述三種類型的語句之一:

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

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

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

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

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

)之間的所有語句構成一個基本塊；或到 程序中的停止或暫停語句(包含該停止或 暫停語句)之間的語句序列組成的。Ch8代碼優化8.2局部優化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代碼優化8.2局部優化8.2.1基本塊定義與劃分

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

程序的控制流圖

具有惟一首結點的有向圖。流圖G為

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

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

n0：是流圖的首結點。

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

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

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

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

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

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

1 2 3Ch8代碼優化8.2局部優化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代碼優化8.2局部優化8.2.2程序的控制流圖Ch8代碼優化8.2局部優化8.2.3DAG定義與應用

DAG（DirectedAcyclicGraph）

無環路的有向圖。

定義8.1

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

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

為無環路有向圖。

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

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

★注意：

流圖的一個結點是一個基本塊，可用DAG表示。流圖確認的是基本塊之間的關系，DAG確認的是基本塊內各四元式間的關系。–a,dCh8代碼優化8.2局部優化8.2.3DAG定義與應用常見四元式與DAG結點對應關系P2260型1型2型

一個結點(定值語句)

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

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

(1)

葉結點、內部結點按統一標記；

(2)

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

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

1.

構造葉結點；

2.

捕捉已知量，合并常數；

//刪除原常數結點//刪除冗余的公共子表達式3.

捕捉公共子表達式；4.

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

代碼優化8.2

局部優化8.2.3DAG定義與應用例8.4設有一個基本塊的語句序列如下

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

T6=R-r B=T5*T6Ch8代碼優化8.2局部優化8.2.3DAG定義與應用P228_例7.4

34

38解:構造DAG的過程如下：

n1T03.14

n1T03.14

n2T16.28

n1T0n2T13.146.28n3

Rn5T2

+

n4

r

n1T0n2T13.146.28n6A

* n3

Rn5T2

+

n4

rCh8代碼優化8.2局部優化8.2.3DAG定義與應用n6A,B,T5n5

+

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

*n1T0n2T1,T3n3n5T2,T4

+

n43.146.28RrCh8代碼優化8.2局部優化8.2.3DAG定義與應用+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

代碼優化8.2

局部優化8.2.3DAG定義與應用本節思路

循環優化的重要性：循環是程序中反復 執行的代碼序列，實施循環優化，將高 效提高目標代碼質量。

循環優化的技術準備：循環查找；控制 流和數據流分析。 通過控制流分析查找循環。Ch8代碼優化8.3控制流分析與循環查找

構成循環條件

具有下列性質的結點序列為一個循環：

1.強連通性。

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

2.入口惟一。

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

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

例如右圖，{2，3}是循環

強連通性成立惟一結點2Ch8代碼優化8.3控制流分析與循環查找{6}{4,5,6,7}強連通/入口6強連通/入口4

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

Ch8代碼優化例如下圖，8.3控制流分析與循環查找

循環：定義8.3(必經結點)

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

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

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

(3)反對稱性：若有aDOMb,bDOMa,

則有：a=b。Ch8代碼優化8.3控制流分析與循環查找3476

405

Ch8

代碼優化例8.5

設有如下流圖

1 28.3

控制流分析與循環查找

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（回邊）

設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代碼優化8.3

控制流分析與循環查找

利用回邊求出流圖中的循環： 若<n,d>是一回邊，則由結點d、結點n以及所有通路到達n而該通路不經過d的所有結點序列構成一個循環L，d是循環L的惟一入口。

例8.5流圖中的循環：

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

1.確定G的D(n)；

2.由D(n)找回邊；

3.通過回邊確定循環。Ch8代碼優化8.3控制流分析與循環查找（summary）

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

code（summary）

Ch8代碼優化二.循環優化中間code基本塊G

技術準備控制流分析控制流分析數據流分析

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

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

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

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

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

例如，Ch8代碼優化8.4數據流分析基礎

定值點：

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

賦值語句

輸入語句函數調用的形參與實參結合Ch8代碼優化8.4數據流分析基礎引用點：

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

到達—定值：

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

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

p:…變量A在點d的定值到達點PCh8代碼優化8.4數據流分析基礎d1:i=m-1d2:d3:j=na=c1d4:i=i+1d5:j=j-1……d6:a=c2……B5B4B6B3B2B1例8.6設有如下流圖Ch8代碼優化8.4數據流分析基礎

定義8.6（ud鏈） 假設在程序中某點P引用了變量A的值，則把G中能到達P的A的定值點的全體，稱為A在引用點P的引用─定值鏈（即ud鏈）。d1:A

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

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

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

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

d:Ad':AA在點d活躍

A在點d,d'活躍

A在點d'活躍，在點d死亡Ch8代碼優化8.4數據流分析基礎

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

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

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

對變量A：

d-du={d1,d2}d2:<A>du鏈Ch8代碼優化8.4數據流分析基礎例8.7設有流圖

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代碼優化8.4數據流分析基礎

二.重要數據流方程

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

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

活躍變量信息—寄存器優化；

公共子表達式信息—刪除冗余運算。Ch8代碼優化8.4數據流分析基礎

典型的數據流方程

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

其中：

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

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

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

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

由in[B]決定out[B]Ch8代碼優化8.4數據流分析基礎后前（每個基本塊Bi的有關信息利用其

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

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

由out[B]決定in[B]2.由于數據沿流圖的控制路徑流動，故數據 流分析受程序控制結構影響。Ch8代碼優化8.4數據流分析基礎

到達—定值數據流方程

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

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

out(Bi):能到達基本塊Bi出口之后的各變量 定值點的集合。gen(Bi):在Bi中定值且能到達Bi出口之后的 所有定值點集。Ch8代碼優化8.4數據流分析基礎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)可從其定義出發，直接從給定的流圖求出。

P(B)表示B的所有前驅基本塊的集合。Ch8代碼優化8.4數據流分析基礎

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設有流圖

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

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

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

對in(B):

是B的所有前驅基本塊的out之和。Ch8代碼優化8.4數據流分析基礎算法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]之值不等則為“真”， 需要繼續迭代；若相等，則迭代過程結束，其值為“假”*{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鏈為pg2i25v；

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

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

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

如果從初始結點到P的每條路徑上都 計算x+y，并且在最后一個x+y到P之間未 對x或y定值，則表達式x+y在點P可用。 若有對x或y的定值，則可用的x+y被 注銷。Ch8代碼優化8.4數據流分析基礎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代碼優化8.4數據流分析基礎可用表達式數據流方程out[B]=in[B]–kill[B]∪gen[B](8.3)(8.4)(B不是開始塊) (B1是開始塊)in(B)=∩out[P]

P是B的前驅

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

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

(2)合流算符是∩；(∵一個表達式在塊的開始點可用， 只有當它在該塊的所有前趨塊的 結束點可用時才行)Ch8代碼優化8.4數據流分析基礎活躍變量數據流方程

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代碼優化8.4數據流分析基礎inL(B):在基本塊B入口點的活躍變量的 集合。

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

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

量的定值——引用情況信息數的數據流分析：

循環的前置結點

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

∵循環的入口惟一∴前置結點惟一Ch7代碼優化7.5循環優化實施L...

Bk

循環L的入口結點 循環L建立前置結點B0前的循環LBi

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

Bj...

B0

循環L的前置結點

Bk循環L的入口結點 循環L建立循環L的前置結點B0后Ch7代碼優化7.5循環優化實施

一.代碼外提

代碼外提就是將循環中的不變運算提到循 環的前置結點中。這里所指的不變運算，是指 與循環執行次數無關的運算或不受循環控制變 量影響的那些運算。

例如，設循環L中有形如A=BopC的語句，如果B和C是常數，或者B和C雖然是變量，但到達B和C的定值點皆在循環L外，則在循環中每次計算出的BopC的值始終不變。Ch7代碼優化7.5循環優化實施例8.10給出以下源程序及該程序流圖

B3I=I+1gotoB2

B4L2:…

B1

A=0 I=1 B2

B=J+1

C=B+I A=C+AifI=100gotoB4Ch8代碼優化8.5循環優化實施

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

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

設有循環L

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

輸出：查找、標識“不變運算”后的循環L；Ch8代碼優化8.5循環優化實施方法：

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

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

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

算法8.4（X2:代碼外提）

輸入：循環L；ud鏈信息和必經結點D(ni)信息

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

后的循環L)方法：

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

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

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

檢查是否滿足如下條件之一：Ch8代碼優化8.5循環優化實施Ch8代碼優化8.5循環優化實施

①

（i）S所在的結點是L的所有出口結點的必經 結點；

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

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

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

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

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

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

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

不變運算i=1j=iB1B2

ifu<vgotoB3

B3i=2u=u+1

B4

v=v-1 ifv<=20gotoB5B5例8.11設有流圖Ch8代碼優化8.5循環優化實施ifu<vgotoB3j=iB2

B3u=u+1

B4

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

i=2B1

B0外提不變運算后的流圖90Ch8代碼優化8.5循環優化實施**在L對i不止一次定值情況下不允許外提i=1i=3i=2u=u+1j=iB1B2ifu<vgotoB3

B3

B4

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

B3

i=2u=u+1

B4

k=i;v=v-1; ifv<=20gotoB5B5Ch8代碼優化8.5循環優化實施二.強度削弱與刪除歸納變量

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

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

有次序且相關

W1(尋找歸納變量)

W2(強度削弱)

W3(刪除歸納變量)Ch8代碼優化8.5循環優化實施

算法8.5(W1：查找歸納變量)輸入：帶有到達—定值信息和循環不變運算信息的循 環L輸出：查找循環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為循環不變量；J為基本歸納變量或歸納變量；）Ch8代碼優化8.5循環優化實施(1)若J是基本歸納變量，K在J族中；{K、J同族}(2)若J是歸納變量，J∈K族，K、J、I同族的附加 要求：

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

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

**找出一族歸納變量，可以變換計算歸納變量的指令（*+）Ch8代碼優化8.5循環優化實施

算法8.6(W2：強度削弱)

輸入：帶有到達—定值信息的L和歸納變量族輸出：進行強度削弱優化后的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代碼優化8.5循環優化實施算法8.7(W3：刪除歸納變量)輸入：帶有到達—定值信息、循環不變運算信息和活 躍變量信息的L輸出：刪除歸納變量優化后的L方法：考察每個僅用于計算同族中其它歸納變量和條件分支的基本歸納變量I，取I族的一個歸納變量一個歸納變量J，將含I的測試改為用J代替。

據du鏈信息

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

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

Ch8代碼優化實施優化的綜合考慮

綜合應用各類優化技術的共性應考慮的因素：循環優化全局優化局部優化會加入新的基本塊調整語句，撤消某個基本塊

Ch7代碼優化控制流分析 數據流分析控制流、數 據流分析

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

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