《編譯原理實踐及應(yīng)用》第7章代碼優(yōu)化課件

代碼優(yōu)化第七章代碼優(yōu)化第七章

本章要求主要內(nèi)容：代碼優(yōu)化的主要功能，局部優(yōu)化、全局優(yōu)化和循環(huán)優(yōu)化的相關(guān)概念，各種優(yōu)化技術(shù)重點掌握：代碼優(yōu)化技術(shù)，基本塊、流圖、DAG的概念，必經(jīng)結(jié)點、回邊、循環(huán)的概念，各種優(yōu)化技術(shù)。本章要求主要內(nèi)容：代碼優(yōu)化的主要功能，局部優(yōu)化、全局優(yōu)化和代碼優(yōu)化所地位和作用：7.1概述代碼優(yōu)化所地位和作用：7.1概述實際上很多地方可以對代碼的執(zhí)行效率進行改進，主要講對中間代碼的優(yōu)化代碼優(yōu)化：對程序進行等價變換，使得從變換后的程序出發(fā)，能夠生成更有效的目標(biāo)代碼。實際上很多地方可以對代碼的執(zhí)行效率進行改進，主要講對中間代碼優(yōu)化分類按階段分:

與機器無關(guān)的優(yōu)化--對中間代碼進行依賴于機器的優(yōu)化--對目標(biāo)代碼進行根據(jù)優(yōu)化所涉及的程序范圍分成:(1)局部優(yōu)化:(基本塊)(2)循環(huán)優(yōu)化:對循環(huán)中的代碼進行優(yōu)化

(3)全局優(yōu)化:大范圍的優(yōu)化優(yōu)化分類按階段分:

優(yōu)化的原則等價原則：不改變運行結(jié)果有效原則：優(yōu)化后時間更短，占用空間更少合算原則：應(yīng)用較低的代價取得較好的優(yōu)化效果宗旨：獲得較好性能的代碼（時間，空間）等價意圖、結(jié)果之間要權(quán)衡《編譯原理實踐及應(yīng)用》第7章代碼優(yōu)化課件中間代碼優(yōu)化技術(shù)優(yōu)化工作數(shù)據(jù)流分析(data-flowanalysis)

控制流分析(control-flowanalysis)變換(transformations)中間代碼優(yōu)化技術(shù)優(yōu)化工作快速排序程序voidquicksort(intm,intn){inti,j,v,x; if(n<m)return;

i=m-1;j=n;v=a[n]; while(1){ doi=i+1;while(a[i]<v); doj=j-1;while(a[j]>v); if(i>=j)break; x=a[i];a[i]=a[j];a[j]=x;} x=a[i];a[i]=a[n];a[n]=x; quicksort(m,j);quicksort(i+1,n);}(1)i=m–1(2)j=n(3)T1=4*n(4)v=a[T1](5)i=i+1(6)T2=4*i(7)T3=a[T2](8)ifT3<vgoto(5)(9)j=j–1(10)T4=4*j(11)T5=a[T4](12)ifT5>vgoto(9)(13)ifi>=jgoto(23)(14)T6=4*i(15)x=a[T6](16)T7=4*i(17)T8=4*j(18)T9=a[T8](19)a[T7]=T9(20)T10=4*j(21)a[T10]=x(22)goto(5)(23)T11=4*j(24)x=a[T11](25)T12=4*i(26)T13=4*n(27)T14=a[T13](28)a[T12]=T14(29)T15=4*n(30)a[T15]=x中間代碼快速排序程序voidquicksort(intm,int7.2基本塊的優(yōu)化

基本塊：是指程序中一順序執(zhí)行的語句序列，其中只有一個入口語句和一個出口語句，入口是其第一個語句，出口是其最后一個語句如果x:=y+z則稱對x定值,引用y和z

在一個基本塊內(nèi)的一個名字,在程序中的某個給定點是活躍的，是指如果在程序中它的值在該點之后被引用.7.2基本塊的優(yōu)化 基本塊：是指程序中一順序執(zhí)行的語句入口語句：1．程序的第一個語句；或者，2．條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句的轉(zhuǎn)移目標(biāo)語句（此處的轉(zhuǎn)移語句包括各種控制的轉(zhuǎn)向，如call，return，end，stop等）；或者3．緊跟在條件轉(zhuǎn)移語句后面的語句。執(zhí)行：對于一個基本塊，執(zhí)行時只能從其入口進入，從其出口退出入口語句：執(zhí)行：劃分基本塊的算法求出四元式程序之中各個基本塊的入口語句對每一入口語句，構(gòu)造其所屬的基本塊。它是由該語句到下一入口語句（不包括下一入口語句），或到一轉(zhuǎn)移語句（包括該轉(zhuǎn)移語句），或到一停語句（包括該停語句）之間的語句序列組成的。凡未被納入某一基本塊的語句，都是程序中控制流程無法到達(dá)的語句，因而也是不會被執(zhí)行到的語句，可以把它們刪除。一般把過程調(diào)用語句作為一個單獨的基本塊劃分基本塊的算法求出四元式程序之中各個基本塊的入口語句*(1)readx(2)readyB1*(3)r=xmody(4)ifr=0goto(8)B2*(5)x=y(6)y=r(7)goto(3)B3*(8)writey(9)haltB4例：*(1)readx(2)ready*(3)r=xmody(4)ifr=0goto(8)*(5)x=y(6)y=r(7)goto(3)*(8)writey(9)halt*(1)readxB1*(3)r=xmodyB2*(

流圖：有向圖。將控制流的信息增加到基本塊的集合上來表示一個程序。流圖以基本塊為單位。如果按順序執(zhí)行，就畫一條有向邊?；緣K間的關(guān)系:(前驅(qū),后繼)

B1是B2的前驅(qū)，B2是B1的后繼:有一個條件或無條件轉(zhuǎn)移語句從B1的最后一條語句轉(zhuǎn)移到B2的第一條語句；或者在程序的序列中，B2緊接在B1的后面，并且B1的最后一條語句不是一個無條件轉(zhuǎn)移語句。流圖：有向圖。將控制流的信息增加到基本塊的集合上來表示一個*(1)readx(2)ready*(3)r=xmody(4)ifr=0goto(8)*(5)x=y(6)y=r(7)goto(3)*(8)writey(9)halt《編譯原理實踐及應(yīng)用》第7章代碼優(yōu)化課件練習(xí)f0=0f1=1ifm<=1gotoL3i=2L1:ifi<=mgotoL3L2:f2=f0+f1f0=f1f1=f2i=i+1gotoL1L3:returnm12345f0=0f1=1ifm<=1gotoL3i=2L1:ifi<=mgotoL3L2:f2=f0+f1f0=f1f1=f2i=i+1gotoL1L3:returnm12345練習(xí)f0=012345f0=0i=12345f0=0f1=1ifm<=1gotoL3i=2L1:ifi<=mgotoL3L2:f2=f0+f1f0=f1f1=f2i=i+1gotoL1L3:returnm1234512345f0=0i=2L1:ifi<=m快速排序算法中間代碼的基本塊和流圖(1)i=m–1(2)j=n(3)T1=4*n(4)v=a[T1](5)i=i+1(6)T2=4*i(7)T3=a[T2](8)ifT3<vgoto(5)(9)j=j–1(10)T4=4*j(11)T5=a[T4](12)ifT5>vgoto(9)(13)ifi>=jgoto(23)(14)T6=4*i(15)x=a[T6](16)T7=4*i(17)T8=4*j(18)T9=a[T8](19)a[T7]=T9(20)T10=4*j(21)a[T10]=x(22)goto(5)(23)T11=4*j(24)x=a[T11](25)T12=4*i(26)T13=4*n(27)T14=a[T13](28)a[T12]=T14(29)T15=4*n(30)a[T15]=x快速排序算法中間代碼的基本塊和流圖(1)i=m–1(優(yōu)化技術(shù)1—刪除公共子表達(dá)式如果表達(dá)式E已經(jīng)在前面計算過，并在計算之后E的值沒有改變，則稱該表達(dá)式為公共子表達(dá)式?？梢员苊庵貜?fù)計算。T6=4*ix=a[T6]T7=4*iT8=4*jT9=a[T8]a[T7]=T9T10=4*ja[T10]=xgotoB2T6=4*ix=a[T6]T7=T6T8=4*jT9=a[T8]a[T7]=T9T10=T8a[T10]=xgotoB24*i，4*j重復(fù)計算優(yōu)化技術(shù)1—刪除公共子表達(dá)式如果表達(dá)式E已經(jīng)在前面計算過，并在更大的范圍內(nèi)刪除4*i,4*j的計算，得到：在更大的范圍內(nèi)刪除4*i,4*j的計算，得到：優(yōu)化技術(shù)2—復(fù)寫傳播T6=T2x=T3T7=T2T8=T4T9=T5a[T2]=T5T10=T4a[T4]=T3gotoB2T6=T2x=a[T6]T7=T6T8=T4T9=a[T8]a[T7]=T9T10=T8a[T10]=xgotoB2T6=T2，x=a[T6]，之間沒有改變T6,因此，可以直接寫x=a[T2]在B2中T3=a[T2]因此，x=T3優(yōu)化技術(shù)2—復(fù)寫傳播T6=T2T6=T2T6=T2，x=a[優(yōu)化技術(shù)3—刪除無用代碼a[T2]=T5a[T4]=T3gotoB2T6=T2x=T3T7=T2T8=T4T9=T5a[T2]=T5T10=T4a[T4]=T3gotoB2某些變量的賦值無用，在后面的程序中不再有用a[T2]=va[T1]=T3B5B6優(yōu)化技術(shù)3—刪除無用代碼a[T2]=T5T6=T2某些變量的《編譯原理實踐及應(yīng)用》第7章代碼優(yōu)化課件優(yōu)化技術(shù)4——對程序進行代數(shù)恒等變換（合并已知量）T1=2……T2=4*T1T1=2……T2=8優(yōu)化技術(shù)4——對程序進行代數(shù)恒等變換（合并已知量）T1=2T優(yōu)化技術(shù)4—對程序進行代數(shù)恒等變換（降低運算強度）a)i*2=2*i=i+i=i<<2b)i/2=(int)(i*0.5)c)0-1=-1d)f*2=2.0*f=f+fe)f/2.0=f*0.5優(yōu)化技術(shù)4—對程序進行代數(shù)恒等變換（降低運算強度）a)i*優(yōu)化技術(shù)4——對程序進行代數(shù)恒等變換（代數(shù)化簡）x+0=x0+x=xx*1=x1*x=x0/x=0x-0=xb&&true=bb&&false=falseb||true=trueb||false=b優(yōu)化技術(shù)4——對程序進行代數(shù)恒等變換（代數(shù)化簡）x+0=基本塊的DAG表示及其應(yīng)用DAGDirectedAcyclicGraph有向無環(huán)路圖基本塊的DAG是在結(jié)點上帶有標(biāo)記的DAGDAG表示了基本塊的計算過程葉結(jié)點表示標(biāo)識符或常數(shù)的值，以標(biāo)識符或常數(shù)作為標(biāo)記內(nèi)部結(jié)點以運算符作為標(biāo)記，表示運算結(jié)果邊表示了操作間的前驅(qū)和后繼的關(guān)系每個結(jié)點：附加標(biāo)識符標(biāo)記，可以是一個或多個標(biāo)識符都具有該結(jié)點代表的值基本塊的DAG表示及其應(yīng)用DAGDirectedAc用DAG進行基本塊的優(yōu)化(0)x=y(1)x=opy(2)x=yopz用DAG進行基本塊的優(yōu)化(0)x=y(1)x=op基本塊的DAG構(gòu)造算法:首先，DAG為空。對基本塊的每一四元式，依次執(zhí)行1，2，3，4步：1.如果NODE(B)無定義，則構(gòu)造一標(biāo)記為B的葉結(jié)點并定義NODE(B)為這個結(jié)點；如果當(dāng)前四元式是0型，則記NODE(B)的值為n，轉(zhuǎn)4。如果當(dāng)前四元式是1型，則轉(zhuǎn)2(1)。如果當(dāng)前四元式是2型，則：

(1)如果NODE(C)無定義，則構(gòu)造一標(biāo)記為C的葉結(jié)點并定義NODE(C)為這個結(jié)點；

(2)轉(zhuǎn)2(2)基本塊的DAG構(gòu)造算法:首先，DAG為空。2.(1)如果NODE(B)是標(biāo)記為常數(shù)的葉結(jié)點，則轉(zhuǎn)2(3)，否則轉(zhuǎn)3(1)。

(2)如果NODE(B)和NODE(C)都是標(biāo)記為常數(shù)的葉結(jié)點，則轉(zhuǎn)2(4)，否則轉(zhuǎn)3(2)。

(3)執(zhí)行opB（即合并已知量），令得到的新常數(shù)為P。如果NODE(B)是處理當(dāng)前四元式時新構(gòu)造出來的結(jié)點，則刪除它。如果NODE(P)無定義，則構(gòu)造一用P做標(biāo)記的葉結(jié)點n。置NODE(P)=n，轉(zhuǎn)4。

(4)執(zhí)行BopC（即合并已知量），令得到的新常數(shù)為P。如果NODE(B)或NODE(C)是處理當(dāng)前四元式時新構(gòu)造出來的結(jié)點，則刪除它。如果NODE(P)無定義，則構(gòu)造一用P做標(biāo)記的葉結(jié)點n。置NODE(P)=n，轉(zhuǎn)4。2.(1)如果NODE(B)是標(biāo)記為常數(shù)的葉結(jié)點，則轉(zhuǎn)3.(1)檢查DAG中是否已有一結(jié)點，其唯一后繼為NODE(B)，且標(biāo)記為op（即找公共子表達(dá)式）。如果沒有，則構(gòu)造該結(jié)點n，否則就把已有的結(jié)點作為它的結(jié)點并設(shè)該結(jié)點為n，轉(zhuǎn)4。(2)檢查中DAG中是否已有一結(jié)點，其左后繼為NODE(B)，其右后繼為NODE(C)，且標(biāo)記為op（即找公共子表達(dá)式）。如果沒有，則構(gòu)造該結(jié)點n，否則就把已有的結(jié)點作為它的結(jié)點并設(shè)該結(jié)點為n，轉(zhuǎn)4。4.如果NODE(A)無定義，則把A附加在結(jié)點n上并令NODE(A)=n；否則先把A從NODE(A)結(jié)點上附加標(biāo)識符集中刪除（注意，如果NODE(A)是葉結(jié)點，則其標(biāo)記A不刪除），把A附加到新結(jié)點n上并令NODE(A)=n。轉(zhuǎn)處理下一四元式。這樣，就可由DAG重新生成原基本塊的一個優(yōu)化的代碼序列。3.(1)檢查DAG中是否已有一結(jié)點，其唯一后繼為NODE例：求下列基本塊的DAG(1)

T0=3.14(2)

T1=2*T0(3)

T2=R+r(4)

A=T1*T2(5)

B=A(6)

T3=2*T0(7)

T4=R+r(8)

T5=T3*T4(9)

T6=R-r(10)

B=T5*T6

例：求下列基本塊的DAG(1)

T0=3.14(1)

T0=3.14(2)

T1=2*T0(3)

T2=R+r(4)

A=T1*T2(5)

B=A(6)

T3=2*T0(7)

T4=R+r(8)

T5=T3*T4(9)

T6=R-r(10)

B=T5*T6

(1)

T0=3.14(1)

T0=3.14(2)

T1=2*T0(3)

T2=R+r(4)

A=T1*T2(5)

B=A(6)

T3=2*T0(7)

T4=R+r(8)

T5=T3*T4(9)

T6=R-r(10)

B=T5*T6

(1)

T0=3.14(1)

T0=3.14(2)

T1=2*T0(3)

T2=R+r(4)

A=T1*T2(5)

B=A(6)

T3=2*T0(7)

T4=R+r(8)

T5=T3*T4(9)

T6=R-r(10)

B=T5*T6

(1)

T0=3.14(1)

T0=3.14(2)

T1=2*T0(3)

T2=R+r(4)

A=T1*T2(5)

B=A(6)

T3=2*T0(7)

T4=R+r(8)

T5=T3*T4(9)

T6=R-r(10)

B=T5*T6

(1)

T0=3.14DAG的應(yīng)用根據(jù)DAG圖，可以更進一步實現(xiàn)優(yōu)化：合并已知量，如T1，T3刪除冗余賦值，如B的第一次賦值公共子表達(dá)式的提取，如T2和T4在基本塊外被定值并在基本塊內(nèi)被引用的所有標(biāo)識符，就是作為葉結(jié)點上標(biāo)記的那些標(biāo)識符在基本塊內(nèi)被定值且該值能在基本塊后面被引用的所有標(biāo)識符，就是DAG各結(jié)點上的那些附加標(biāo)識符DAG的應(yīng)用根據(jù)DAG圖，可以更進一步實現(xiàn)優(yōu)化：(1)

T1=R+r(2)

A=6.28*T1

(3)

T2=R-r(4)

B=S*T2

簡化后的代碼序列(1)

T1=R+r簡化后的代碼序列循環(huán)：程序中可能反復(fù)執(zhí)行的代碼序列,也是優(yōu)化的重點7.3循環(huán)優(yōu)化循環(huán)：程序中可能反復(fù)執(zhí)行的代碼序列,也是優(yōu)化的重點7.3循程序流圖中結(jié)點間的關(guān)系mDOMn定義

在程序流圖中,對任意兩個結(jié)點m和n,如果從流圖的首結(jié)點出發(fā),到達(dá)n的任意通路都要經(jīng)過m,則稱m是n的必經(jīng)結(jié)點,記為mDOMn每個結(jié)點是它本身的必經(jīng)結(jié)點；循環(huán)的入口是循環(huán)中所有結(jié)點的必經(jīng)結(jié)點。必經(jīng)結(jié)點集定義

結(jié)點n的所有必經(jīng)結(jié)點的集合,稱為結(jié)點n的必經(jīng)結(jié)點集,記為D(n).程序流圖中結(jié)點間的關(guā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}例：D(1)={1}循環(huán)的查找算法回邊：假設(shè)a→b是流圖中的一條有向邊，如果bDOMa，則稱a→b是流圖中的一條回邊。循環(huán)的查找如果有向邊n→d是回邊，組成的循環(huán)是由結(jié)點d

，結(jié)點

n以及有通路到達(dá)n而該通路不經(jīng)過d的所有結(jié)點組成，并且d是該循環(huán)的唯一入口結(jié)點。循環(huán)的查找算法回邊：假設(shè)a→b是流圖中的一條有向邊，如果b回邊66循環(huán){6}74{4,5,6,7}42{2,3,4,5,6,7}循環(huán)(結(jié)點序列的性質(zhì))1.強連通的(任意兩結(jié)點間,必有一條通路,且該通路上各結(jié)點都屬于該結(jié)點序列)2.它們中間有且只有一個是入口結(jié)點。

回邊66循環(huán){6}循環(huán)優(yōu)化循環(huán)優(yōu)化的關(guān)鍵哪些基本塊構(gòu)成一個循環(huán)循環(huán)優(yōu)化的方法代碼外提強度削弱刪除歸納變量循環(huán)優(yōu)化循環(huán)優(yōu)化的關(guān)鍵循環(huán)的性質(zhì)兩個循環(huán)的關(guān)系：圖中任意兩個循環(huán)要么是嵌套的，要么不相交（可能有公共的入口結(jié)點）內(nèi)循環(huán)：不包含任何其它循環(huán)的循環(huán)如果兩個自然循環(huán)有相同的首結(jié)點，且兩個循環(huán)不是一個嵌在另一個里面時，可以考慮將二者合并，當(dāng)成是一個循環(huán)B0B1B2B3循環(huán)的性質(zhì)兩個循環(huán)的關(guān)系：B0B1B2B3變量A在某點d的定值到達(dá)另一點u，是指流圖中從d由一通路到達(dá)u且該通路上沒有A的其他定值變量A在某點d的定值到達(dá)另一點u，是指流圖中從d由一通路到達(dá)優(yōu)化技術(shù)5—代碼外提對循環(huán)中的有些代碼，如果它產(chǎn)生的結(jié)果在循環(huán)中是不變的，可以提到循環(huán)外面while(i<=limit-2)…….t=limit-2while(i<=t)…….優(yōu)化技術(shù)5—代碼外提對循環(huán)中的有些代碼，如果它產(chǎn)生的結(jié)果在循代碼外提把循環(huán)不變計算提到循環(huán)外面，在入口結(jié)點的前面創(chuàng)建一個新的基本塊，叫做前置結(jié)點。前置結(jié)點唯一的后繼是L的首結(jié)點將原來從L外到達(dá)L首結(jié)點的邊都改成進入前置結(jié)點從L內(nèi)到達(dá)入口結(jié)點的邊不變代碼外提把循環(huán)不變計算提到循環(huán)外面，在入口結(jié)點的前面創(chuàng)建一個并不是所有情況下，循環(huán)中的不變運算都可以外提。右圖中的B3塊中的I=2是不變運算，但不能外提，因為它并不是所有結(jié)點的必經(jīng)結(jié)點。并不是所有情況下，循環(huán)中的不變運算都可以外提。forI=1to10doA[I,2*J]=A[I,2*J]+1(1)I=1(2)IfI>10goto15(3)T1=2*J(4)T2=10*I(5)T3=T2+T1(6)T4=addr(A)-11(7)T5=2*J(8)T6=10*I(9)T7=T6+T5(10)T8=addr(A)-11(11)T9=T8[T7](12)T4[T3]=T9+1(13)I=I+1(14)gotoB2(15)B1B2B3(1)I=1(2)IfI>10goto15(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(15)B1B2B3(3)T1=2*J(6)T4=addr(A)-11(7)T5=2*J(10)T8=addr(A)-11forI=1to10doA[I,2*J]=A[I優(yōu)化技術(shù)6—強度削弱j=j-1T4=4*jT5=a[T4]ifT5>vgotoB3T4=T4-4T5=a[T4]ifT5>vgotoB3B3J每次減1后再做乘4操作改為先賦值后，T4的計算用減法運算T4=4*j是指把程序中執(zhí)行時間長的運算替換為執(zhí)行時間較短的運算優(yōu)化技術(shù)6—強度削弱j=j-1B3J每次減1后再做乘4操作改《編譯原理實踐及應(yīng)用》第7章代碼優(yōu)化課件優(yōu)化技術(shù)7—刪除歸納變量基本歸納變量：如果循環(huán)中對變量I只有唯一的形如I:=I±c的賦值，c是循環(huán)不變量歸納變量：如果I是循環(huán)中的基本歸納變量，J在循環(huán)中的賦值總是可以化為I的同一線性函數(shù)，即J:=C1*I±c2。同時稱J與I同族優(yōu)化技術(shù)7—刪除歸納變量基本歸納變量：如果循環(huán)中對變量I只有一個基本歸納變量除用于自身的遞歸定值外，一般在循環(huán)中用來計算其他歸納變量及控制循環(huán)的進行，此時，可以用與它同族的某一歸納變量來控制循環(huán)的進行刪除歸納變量一般是在強度削弱以后進行的(1)i=1(2)IfI>10goto15(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(15)B1B2B3(3)T1=2*j(6)T4=addr(A)-11(7)T5=2*j(10)T8=addr(A)-11一個基本歸納變量除用于自身的遞歸定值外，一般在循環(huán)中用來計算刪除歸納變量當(dāng)進行強度削弱后，B4中i,j的比較可以使用T2,T4IfT2>=T4gotoB6刪除歸納變量當(dāng)進行強度削弱后，B4中i,j的比較可以使用T2代碼優(yōu)化第七章代碼優(yōu)化第七章

本章要求主要內(nèi)容：代碼優(yōu)化的主要功能，局部優(yōu)化、全局優(yōu)化和循環(huán)優(yōu)化的相關(guān)概念，各種優(yōu)化技術(shù)重點掌握：代碼優(yōu)化技術(shù)，基本塊、流圖、DAG的概念，必經(jīng)結(jié)點、回邊、循環(huán)的概念，各種優(yōu)化技術(shù)。本章要求主要內(nèi)容：代碼優(yōu)化的主要功能，局部優(yōu)化、全局優(yōu)化和代碼優(yōu)化所地位和作用：7.1概述代碼優(yōu)化所地位和作用：7.1概述實際上很多地方可以對代碼的執(zhí)行效率進行改進，主要講對中間代碼的優(yōu)化代碼優(yōu)化：對程序進行等價變換，使得從變換后的程序出發(fā)，能夠生成更有效的目標(biāo)代碼。實際上很多地方可以對代碼的執(zhí)行效率進行改進，主要講對中間代碼優(yōu)化分類按階段分:

與機器無關(guān)的優(yōu)化--對中間代碼進行依賴于機器的優(yōu)化--對目標(biāo)代碼進行根據(jù)優(yōu)化所涉及的程序范圍分成:(1)局部優(yōu)化:(基本塊)(2)循環(huán)優(yōu)化:對循環(huán)中的代碼進行優(yōu)化

(3)全局優(yōu)化:大范圍的優(yōu)化優(yōu)化分類按階段分:

優(yōu)化的原則等價原則：不改變運行結(jié)果有效原則：優(yōu)化后時間更短，占用空間更少合算原則：應(yīng)用較低的代價取得較好的優(yōu)化效果宗旨：獲得較好性能的代碼（時間，空間）等價意圖、結(jié)果之間要權(quán)衡《編譯原理實踐及應(yīng)用》第7章代碼優(yōu)化課件中間代碼優(yōu)化技術(shù)優(yōu)化工作數(shù)據(jù)流分析(data-flowanalysis)

控制流分析(control-flowanalysis)變換(transformations)中間代碼優(yōu)化技術(shù)優(yōu)化工作快速排序程序voidquicksort(intm,intn){inti,j,v,x; if(n<m)return;

i=m-1;j=n;v=a[n]; while(1){ doi=i+1;while(a[i]<v); doj=j-1;while(a[j]>v); if(i>=j)break; x=a[i];a[i]=a[j];a[j]=x;} x=a[i];a[i]=a[n];a[n]=x; quicksort(m,j);quicksort(i+1,n);}(1)i=m–1(2)j=n(3)T1=4*n(4)v=a[T1](5)i=i+1(6)T2=4*i(7)T3=a[T2](8)ifT3<vgoto(5)(9)j=j–1(10)T4=4*j(11)T5=a[T4](12)ifT5>vgoto(9)(13)ifi>=jgoto(23)(14)T6=4*i(15)x=a[T6](16)T7=4*i(17)T8=4*j(18)T9=a[T8](19)a[T7]=T9(20)T10=4*j(21)a[T10]=x(22)goto(5)(23)T11=4*j(24)x=a[T11](25)T12=4*i(26)T13=4*n(27)T14=a[T13](28)a[T12]=T14(29)T15=4*n(30)a[T15]=x中間代碼快速排序程序voidquicksort(intm,int7.2基本塊的優(yōu)化

基本塊：是指程序中一順序執(zhí)行的語句序列，其中只有一個入口語句和一個出口語句，入口是其第一個語句，出口是其最后一個語句如果x:=y+z則稱對x定值,引用y和z

在一個基本塊內(nèi)的一個名字,在程序中的某個給定點是活躍的，是指如果在程序中它的值在該點之后被引用.7.2基本塊的優(yōu)化 基本塊：是指程序中一順序執(zhí)行的語句入口語句：1．程序的第一個語句；或者，2．條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句的轉(zhuǎn)移目標(biāo)語句（此處的轉(zhuǎn)移語句包括各種控制的轉(zhuǎn)向，如call，return，end，stop等）；或者3．緊跟在條件轉(zhuǎn)移語句后面的語句。執(zhí)行：對于一個基本塊，執(zhí)行時只能從其入口進入，從其出口退出入口語句：執(zhí)行：劃分基本塊的算法求出四元式程序之中各個基本塊的入口語句對每一入口語句，構(gòu)造其所屬的基本塊。它是由該語句到下一入口語句（不包括下一入口語句），或到一轉(zhuǎn)移語句（包括該轉(zhuǎn)移語句），或到一停語句（包括該停語句）之間的語句序列組成的。凡未被納入某一基本塊的語句，都是程序中控制流程無法到達(dá)的語句，因而也是不會被執(zhí)行到的語句，可以把它們刪除。一般把過程調(diào)用語句作為一個單獨的基本塊劃分基本塊的算法求出四元式程序之中各個基本塊的入口語句*(1)readx(2)readyB1*(3)r=xmody(4)ifr=0goto(8)B2*(5)x=y(6)y=r(7)goto(3)B3*(8)writey(9)haltB4例：*(1)readx(2)ready*(3)r=xmody(4)ifr=0goto(8)*(5)x=y(6)y=r(7)goto(3)*(8)writey(9)halt*(1)readxB1*(3)r=xmodyB2*(

流圖：有向圖。將控制流的信息增加到基本塊的集合上來表示一個程序。流圖以基本塊為單位。如果按順序執(zhí)行，就畫一條有向邊。基本塊間的關(guān)系:(前驅(qū),后繼)

B1是B2的前驅(qū)，B2是B1的后繼:有一個條件或無條件轉(zhuǎn)移語句從B1的最后一條語句轉(zhuǎn)移到B2的第一條語句；或者在程序的序列中，B2緊接在B1的后面，并且B1的最后一條語句不是一個無條件轉(zhuǎn)移語句。流圖：有向圖。將控制流的信息增加到基本塊的集合上來表示一個*(1)readx(2)ready*(3)r=xmody(4)ifr=0goto(8)*(5)x=y(6)y=r(7)goto(3)*(8)writey(9)halt《編譯原理實踐及應(yīng)用》第7章代碼優(yōu)化課件練習(xí)f0=0f1=1ifm<=1gotoL3i=2L1:ifi<=mgotoL3L2:f2=f0+f1f0=f1f1=f2i=i+1gotoL1L3:returnm12345f0=0f1=1ifm<=1gotoL3i=2L1:ifi<=mgotoL3L2:f2=f0+f1f0=f1f1=f2i=i+1gotoL1L3:returnm12345練習(xí)f0=012345f0=0i=12345f0=0f1=1ifm<=1gotoL3i=2L1:ifi<=mgotoL3L2:f2=f0+f1f0=f1f1=f2i=i+1gotoL1L3:returnm1234512345f0=0i=2L1:ifi<=m快速排序算法中間代碼的基本塊和流圖(1)i=m–1(2)j=n(3)T1=4*n(4)v=a[T1](5)i=i+1(6)T2=4*i(7)T3=a[T2](8)ifT3<vgoto(5)(9)j=j–1(10)T4=4*j(11)T5=a[T4](12)ifT5>vgoto(9)(13)ifi>=jgoto(23)(14)T6=4*i(15)x=a[T6](16)T7=4*i(17)T8=4*j(18)T9=a[T8](19)a[T7]=T9(20)T10=4*j(21)a[T10]=x(22)goto(5)(23)T11=4*j(24)x=a[T11](25)T12=4*i(26)T13=4*n(27)T14=a[T13](28)a[T12]=T14(29)T15=4*n(30)a[T15]=x快速排序算法中間代碼的基本塊和流圖(1)i=m–1(優(yōu)化技術(shù)1—刪除公共子表達(dá)式如果表達(dá)式E已經(jīng)在前面計算過，并在計算之后E的值沒有改變，則稱該表達(dá)式為公共子表達(dá)式?？梢员苊庵貜?fù)計算。T6=4*ix=a[T6]T7=4*iT8=4*jT9=a[T8]a[T7]=T9T10=4*ja[T10]=xgotoB2T6=4*ix=a[T6]T7=T6T8=4*jT9=a[T8]a[T7]=T9T10=T8a[T10]=xgotoB24*i，4*j重復(fù)計算優(yōu)化技術(shù)1—刪除公共子表達(dá)式如果表達(dá)式E已經(jīng)在前面計算過，并在更大的范圍內(nèi)刪除4*i,4*j的計算，得到：在更大的范圍內(nèi)刪除4*i,4*j的計算，得到：優(yōu)化技術(shù)2—復(fù)寫傳播T6=T2x=T3T7=T2T8=T4T9=T5a[T2]=T5T10=T4a[T4]=T3gotoB2T6=T2x=a[T6]T7=T6T8=T4T9=a[T8]a[T7]=T9T10=T8a[T10]=xgotoB2T6=T2，x=a[T6]，之間沒有改變T6,因此，可以直接寫x=a[T2]在B2中T3=a[T2]因此，x=T3優(yōu)化技術(shù)2—復(fù)寫傳播T6=T2T6=T2T6=T2，x=a[優(yōu)化技術(shù)3—刪除無用代碼a[T2]=T5a[T4]=T3gotoB2T6=T2x=T3T7=T2T8=T4T9=T5a[T2]=T5T10=T4a[T4]=T3gotoB2某些變量的賦值無用，在后面的程序中不再有用a[T2]=va[T1]=T3B5B6優(yōu)化技術(shù)3—刪除無用代碼a[T2]=T5T6=T2某些變量的《編譯原理實踐及應(yīng)用》第7章代碼優(yōu)化課件優(yōu)化技術(shù)4——對程序進行代數(shù)恒等變換（合并已知量）T1=2……T2=4*T1T1=2……T2=8優(yōu)化技術(shù)4——對程序進行代數(shù)恒等變換（合并已知量）T1=2T優(yōu)化技術(shù)4—對程序進行代數(shù)恒等變換（降低運算強度）a)i*2=2*i=i+i=i<<2b)i/2=(int)(i*0.5)c)0-1=-1d)f*2=2.0*f=f+fe)f/2.0=f*0.5優(yōu)化技術(shù)4—對程序進行代數(shù)恒等變換（降低運算強度）a)i*優(yōu)化技術(shù)4——對程序進行代數(shù)恒等變換（代數(shù)化簡）x+0=x0+x=xx*1=x1*x=x0/x=0x-0=xb&&true=bb&&false=falseb||true=trueb||false=b優(yōu)化技術(shù)4——對程序進行代數(shù)恒等變換（代數(shù)化簡）x+0=基本塊的DAG表示及其應(yīng)用DAGDirectedAcyclicGraph有向無環(huán)路圖基本塊的DAG是在結(jié)點上帶有標(biāo)記的DAGDAG表示了基本塊的計算過程葉結(jié)點表示標(biāo)識符或常數(shù)的值，以標(biāo)識符或常數(shù)作為標(biāo)記內(nèi)部結(jié)點以運算符作為標(biāo)記，表示運算結(jié)果邊表示了操作間的前驅(qū)和后繼的關(guān)系每個結(jié)點：附加標(biāo)識符標(biāo)記，可以是一個或多個標(biāo)識符都具有該結(jié)點代表的值基本塊的DAG表示及其應(yīng)用DAGDirectedAc用DAG進行基本塊的優(yōu)化(0)x=y(1)x=opy(2)x=yopz用DAG進行基本塊的優(yōu)化(0)x=y(1)x=op基本塊的DAG構(gòu)造算法:首先，DAG為空。對基本塊的每一四元式，依次執(zhí)行1，2，3，4步：1.如果NODE(B)無定義，則構(gòu)造一標(biāo)記為B的葉結(jié)點并定義NODE(B)為這個結(jié)點；如果當(dāng)前四元式是0型，則記NODE(B)的值為n，轉(zhuǎn)4。如果當(dāng)前四元式是1型，則轉(zhuǎn)2(1)。如果當(dāng)前四元式是2型，則：

(1)如果NODE(C)無定義，則構(gòu)造一標(biāo)記為C的葉結(jié)點并定義NODE(C)為這個結(jié)點；

(2)轉(zhuǎn)2(2)基本塊的DAG構(gòu)造算法:首先，DAG為空。2.(1)如果NODE(B)是標(biāo)記為常數(shù)的葉結(jié)點，則轉(zhuǎn)2(3)，否則轉(zhuǎn)3(1)。

(2)如果NODE(B)和NODE(C)都是標(biāo)記為常數(shù)的葉結(jié)點，則轉(zhuǎn)2(4)，否則轉(zhuǎn)3(2)。

(3)執(zhí)行opB（即合并已知量），令得到的新常數(shù)為P。如果NODE(B)是處理當(dāng)前四元式時新構(gòu)造出來的結(jié)點，則刪除它。如果NODE(P)無定義，則構(gòu)造一用P做標(biāo)記的葉結(jié)點n。置NODE(P)=n，轉(zhuǎn)4。

(4)執(zhí)行BopC（即合并已知量），令得到的新常數(shù)為P。如果NODE(B)或NODE(C)是處理當(dāng)前四元式時新構(gòu)造出來的結(jié)點，則刪除它。如果NODE(P)無定義，則構(gòu)造一用P做標(biāo)記的葉結(jié)點n。置NODE(P)=n，轉(zhuǎn)4。2.(1)如果NODE(B)是標(biāo)記為常數(shù)的葉結(jié)點，則轉(zhuǎn)3.(1)檢查DAG中是否已有一結(jié)點，其唯一后繼為NODE(B)，且標(biāo)記為op（即找公共子表達(dá)式）。如果沒有，則構(gòu)造該結(jié)點n，否則就把已有的結(jié)點作為它的結(jié)點并設(shè)該結(jié)點為n，轉(zhuǎn)4。(2)檢查中DAG中是否已有一結(jié)點，其左后繼為NODE(B)，其右后繼為NODE(C)，且標(biāo)記為op（即找公共子表達(dá)式）。如果沒有，則構(gòu)造該結(jié)點n，否則就把已有的結(jié)點作為它的結(jié)點并設(shè)該結(jié)點為n，轉(zhuǎn)4。4.如果NODE(A)無定義，則把A附加在結(jié)點n上并令NODE(A)=n；否則先把A從NODE(A)結(jié)點上附加標(biāo)識符集中刪除（注意，如果NODE(A)是葉結(jié)點，則其標(biāo)記A不刪除），把A附加到新結(jié)點n上并令NODE(A)=n。轉(zhuǎn)處理下一四元式。這樣，就可由DAG重新生成原基本塊的一個優(yōu)化的代碼序列。3.(1)檢查DAG中是否已有一結(jié)點，其唯一后繼為NODE例：求下列基本塊的DAG(1)

T0=3.14(2)

T1=2*T0(3)

T2=R+r(4)

A=T1*T2(5)

B=A(6)

T3=2*T0(7)

T4=R+r(8)

T5=T3*T4(9)

T6=R-r(10)

B=T5*T6

例：求下列基本塊的DAG(1)

T0=3.14(1)

T0=3.14(2)

T1=2*T0(3)

T2=R+r(4)

A=T1*T2(5)

B=A(6)

T3=2*T0(7)

T4=R+r(8)

T5=T3*T4(9)

T6=R-r(10)

B=T5*T6

(1)

T0=3.14(1)

T0=3.14(2)

T1=2*T0(3)

T2=R+r(4)

A=T1*T2(5)

B=A(6)

T3=2*T0(7)

T4=R+r(8)

T5=T3*T4(9)

T6=R-r(10)

B=T5*T6

(1)

T0=3.14(1)

T0=3.14(2)

T1=2*T0(3)

T2=R+r(4)

A=T1*T2(5)

B=A(6)

T3=2*T0(7)

T4=R+r(8)

T5=T3*T4(9)

T6=R-r(10)

B=T5*T6

(1)

T0=3.14(1)

T0=3.14(2)

T1=2*T0(3)

T2=R+r(4)

A=T1*T2(5)

B=A(6)

T3=2*T0(7)

T4=R+r(8)

T5=T3*T4(9)

T6=R-r(10)

B=T5*T6

(1)

T0=3.14DAG的應(yīng)用根據(jù)DAG圖，可以更進一步實現(xiàn)優(yōu)化：合并已知量，如T1，T3刪除冗余賦值，如B的第一次賦值公共子表達(dá)式的提取，如T2和T4在基本塊外被定值并在基本塊內(nèi)被引用的所有標(biāo)識符，就是作為葉結(jié)點上標(biāo)記的那些標(biāo)識符在基本塊內(nèi)被定值且該值能在基本塊后面被引用的所有標(biāo)識符，就是DAG各結(jié)點上的那些附加標(biāo)識符DAG的應(yīng)用根據(jù)DAG圖，可以更進一步實現(xiàn)優(yōu)化：(1)

T1=R+r(2)

A=6.28*T1

(3)

T2=R-r(4)

B=S*T2

簡化后的代碼序列(1)

T1=R+r簡化后的代碼序列循環(huán)：程序中可能反復(fù)執(zhí)行的代碼序列,也是優(yōu)化的重點7.3循環(huán)優(yōu)化循環(huán)：程序中可能反復(fù)執(zhí)行的代碼序列,也是優(yōu)化的重點7.3循程序流圖中結(jié)點間的關(guān)系mDOMn定義

在程序流圖中,對任意兩個結(jié)點m和n,如果從流圖的首結(jié)點出發(fā),到達(dá)n的任意通路都要經(jīng)過m,則稱m是n的必經(jīng)結(jié)點,記為mDOMn每個結(jié)點是它本身的必經(jīng)結(jié)點；循環(huán)的入口是循環(huán)中所有結(jié)點的必經(jīng)結(jié)點。必經(jīng)結(jié)點集定義

結(jié)點n的所有必經(jīng)結(jié)點的集合,稱為結(jié)點n的必經(jīng)結(jié)點集,記為D(n).程序流圖中結(jié)點間的關(guā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}例：D(1)={1}循環(huán)的查找算法回邊：假設(shè)a→b是流圖中的一條有向邊，如果bDOMa，則稱a→b是流圖中的一條回邊。循環(huán)的查找如果有向邊n→d是回邊，組成的循環(huán)是由結(jié)點d

，結(jié)點

n以及有通路到達(dá)n而該通路不經(jīng)過d的所有結(jié)點組成，并且d是該循環(huán)的唯一入口結(jié)點。循環(huán)的查找算法回邊：假設(shè)a→b是流圖中的一條有向邊，如果b