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

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

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

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

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

優(yōu)化的原則等價(jià)原則：不改變運(yùn)行結(jié)果有效原則：優(yōu)化后時(shí)間更短，占用空間更少合算原則：應(yīng)用較低的代價(jià)取得較好的優(yōu)化效果宗旨：獲得較好性能的代碼（時(shí)間，空間）等價(jià)意圖、結(jié)果之間要權(quán)衡《編譯原理實(shí)踐及應(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í)行的語(yǔ)句序列，其中只有一個(gè)入口語(yǔ)句和一個(gè)出口語(yǔ)句，入口是其第一個(gè)語(yǔ)句，出口是其最后一個(gè)語(yǔ)句如果x:=y+z則稱對(duì)x定值,引用y和z

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

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

B1是B2的前驅(qū)，B2是B1的后繼:有一個(gè)條件或無(wú)條件轉(zhuǎn)移語(yǔ)句從B1的最后一條語(yǔ)句轉(zhuǎn)移到B2的第一條語(yǔ)句；或者在程序的序列中，B2緊接在B1的后面，并且B1的最后一條語(yǔ)句不是一個(gè)無(wú)條件轉(zhuǎn)移語(yǔ)句。流圖：有向圖。將控制流的信息增加到基本塊的集合上來(lái)表示一個(gè)*(1)readx(2)ready*(3)r=xmody(4)ifr=0goto(8)*(5)x=y(6)y=r(7)goto(3)*(8)writey(9)halt《編譯原理實(shí)踐及應(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—?jiǎng)h除公共子表達(dá)式如果表達(dá)式E已經(jīng)在前面計(jì)算過(guò)，并在計(jì)算之后E的值沒(méi)有改變，則稱該表達(dá)式為公共子表達(dá)式?？梢员苊庵貜?fù)計(jì)算。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ù)計(jì)算優(yōu)化技術(shù)1—?jiǎng)h除公共子表達(dá)式如果表達(dá)式E已經(jīng)在前面計(jì)算過(guò)，并在更大的范圍內(nèi)刪除4*i,4*j的計(jì)算，得到：在更大的范圍內(nèi)刪除4*i,4*j的計(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]，之間沒(méi)有改變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—?jiǎng)h除無(wú)用代碼a[T2]=T5a[T4]=T3gotoB2T6=T2x=T3T7=T2T8=T4T9=T5a[T2]=T5T10=T4a[T4]=T3gotoB2某些變量的賦值無(wú)用，在后面的程序中不再有用a[T2]=va[T1]=T3B5B6優(yōu)化技術(shù)3—?jiǎng)h除無(wú)用代碼a[T2]=T5T6=T2某些變量的《編譯原理實(shí)踐及應(yīng)用》第7章代碼優(yōu)化課件優(yōu)化技術(shù)4——對(duì)程序進(jìn)行代數(shù)恒等變換（合并已知量）T1=2……T2=4*T1T1=2……T2=8優(yōu)化技術(shù)4——對(duì)程序進(jìn)行代數(shù)恒等變換（合并已知量）T1=2T優(yōu)化技術(shù)4—對(duì)程序進(jìn)行代數(shù)恒等變換（降低運(yùn)算強(qiáng)度）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—對(duì)程序進(jìn)行代數(shù)恒等變換（降低運(yùn)算強(qiáng)度）a)i*優(yōu)化技術(shù)4——對(duì)程序進(jìn)行代數(shù)恒等變換（代數(shù)化簡(jiǎn)）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——對(duì)程序進(jìn)行代數(shù)恒等變換（代數(shù)化簡(jiǎn)）x+0=基本塊的DAG表示及其應(yīng)用DAGDirectedAcyclicGraph有向無(wú)環(huán)路圖基本塊的DAG是在結(jié)點(diǎn)上帶有標(biāo)記的DAGDAG表示了基本塊的計(jì)算過(guò)程葉結(jié)點(diǎn)表示標(biāo)識(shí)符或常數(shù)的值，以標(biāo)識(shí)符或常數(shù)作為標(biāo)記內(nèi)部結(jié)點(diǎn)以運(yùn)算符作為標(biāo)記，表示運(yùn)算結(jié)果邊表示了操作間的前驅(qū)和后繼的關(guān)系每個(gè)結(jié)點(diǎn)：附加標(biāo)識(shí)符標(biāo)記，可以是一個(gè)或多個(gè)標(biāo)識(shí)符都具有該結(jié)點(diǎn)代表的值基本塊的DAG表示及其應(yīng)用DAGDirectedAc用DAG進(jìn)行基本塊的優(yōu)化(0)x=y(1)x=opy(2)x=yopz用DAG進(jìn)行基本塊的優(yōu)化(0)x=y(1)x=op基本塊的DAG構(gòu)造算法:首先，DAG為空。對(duì)基本塊的每一四元式，依次執(zhí)行1，2，3，4步：1.如果NODE(B)無(wú)定義，則構(gòu)造一標(biāo)記為B的葉結(jié)點(diǎn)并定義NODE(B)為這個(gè)結(jié)點(diǎn)；如果當(dāng)前四元式是0型，則記NODE(B)的值為n，轉(zhuǎn)4。如果當(dāng)前四元式是1型，則轉(zhuǎn)2(1)。如果當(dāng)前四元式是2型，則：

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

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

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

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

(4)執(zhí)行BopC（即合并已知量），令得到的新常數(shù)為P。如果NODE(B)或NODE(C)是處理當(dāng)前四元式時(shí)新構(gòu)造出來(lái)的結(jié)點(diǎn)，則刪除它。如果NODE(P)無(wú)定義，則構(gòu)造一用P做標(biāo)記的葉結(jié)點(diǎn)n。置NODE(P)=n，轉(zhuǎn)4。2.(1)如果NODE(B)是標(biāo)記為常數(shù)的葉結(jié)點(diǎn)，則轉(zhuǎn)3.(1)檢查DAG中是否已有一結(jié)點(diǎn)，其唯一后繼為NODE(B)，且標(biāo)記為op（即找公共子表達(dá)式）。如果沒(méi)有，則構(gòu)造該結(jié)點(diǎn)n，否則就把已有的結(jié)點(diǎn)作為它的結(jié)點(diǎn)并設(shè)該結(jié)點(diǎn)為n，轉(zhuǎn)4。(2)檢查中DAG中是否已有一結(jié)點(diǎn)，其左后繼為NODE(B)，其右后繼為NODE(C)，且標(biāo)記為op（即找公共子表達(dá)式）。如果沒(méi)有，則構(gòu)造該結(jié)點(diǎn)n，否則就把已有的結(jié)點(diǎn)作為它的結(jié)點(diǎn)并設(shè)該結(jié)點(diǎn)為n，轉(zhuǎn)4。4.如果NODE(A)無(wú)定義，則把A附加在結(jié)點(diǎn)n上并令NODE(A)=n；否則先把A從NODE(A)結(jié)點(diǎn)上附加標(biāo)識(shí)符集中刪除（注意，如果NODE(A)是葉結(jié)點(diǎn)，則其標(biāo)記A不刪除），把A附加到新結(jié)點(diǎn)n上并令NODE(A)=n。轉(zhuǎn)處理下一四元式。這樣，就可由DAG重新生成原基本塊的一個(gè)優(yōu)化的代碼序列。3.(1)檢查DAG中是否已有一結(jié)點(diǎn)，其唯一后繼為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圖，可以更進(jìn)一步實(shí)現(xiàn)優(yōu)化：合并已知量，如T1，T3刪除冗余賦值，如B的第一次賦值公共子表達(dá)式的提取，如T2和T4在基本塊外被定值并在基本塊內(nèi)被引用的所有標(biāo)識(shí)符，就是作為葉結(jié)點(diǎn)上標(biāo)記的那些標(biāo)識(shí)符在基本塊內(nèi)被定值且該值能在基本塊后面被引用的所有標(biāo)識(shí)符，就是DAG各結(jié)點(diǎn)上的那些附加標(biāo)識(shí)符DAG的應(yīng)用根據(jù)DAG圖，可以更進(jìn)一步實(shí)現(xiàn)優(yōu)化：(1)

T1=R+r(2)

A=6.28*T1

(3)

T2=R-r(4)

B=S*T2

簡(jiǎn)化后的代碼序列(1)

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

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

結(jié)點(diǎn)n的所有必經(jīng)結(jié)點(diǎn)的集合,稱為結(jié)點(diǎn)n的必經(jīng)結(jié)點(diǎn)集,記為D(n).程序流圖中結(jié)點(diǎn)間的關(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é)點(diǎn)d

，結(jié)點(diǎn)

n以及有通路到達(dá)n而該通路不經(jīng)過(guò)d的所有結(jié)點(diǎn)組成，并且d是該循環(huán)的唯一入口結(jié)點(diǎn)。循環(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é)點(diǎn)序列的性質(zhì))1.強(qiáng)連通的(任意兩結(jié)點(diǎn)間,必有一條通路,且該通路上各結(jié)點(diǎn)都屬于該結(jié)點(diǎn)序列)2.它們中間有且只有一個(gè)是入口結(jié)點(diǎn)。

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

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

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

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

優(yōu)化的原則等價(jià)原則：不改變運(yùn)行結(jié)果有效原則：優(yōu)化后時(shí)間更短，占用空間更少合算原則：應(yīng)用較低的代價(jià)取得較好的優(yōu)化效果宗旨：獲得較好性能的代碼（時(shí)間，空間）等價(jià)意圖、結(jié)果之間要權(quán)衡《編譯原理實(shí)踐及應(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í)行的語(yǔ)句序列，其中只有一個(gè)入口語(yǔ)句和一個(gè)出口語(yǔ)句，入口是其第一個(gè)語(yǔ)句，出口是其最后一個(gè)語(yǔ)句如果x:=y+z則稱對(duì)x定值,引用y和z

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

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

B1是B2的前驅(qū)，B2是B1的后繼:有一個(gè)條件或無(wú)條件轉(zhuǎn)移語(yǔ)句從B1的最后一條語(yǔ)句轉(zhuǎn)移到B2的第一條語(yǔ)句；或者在程序的序列中，B2緊接在B1的后面，并且B1的最后一條語(yǔ)句不是一個(gè)無(wú)條件轉(zhuǎn)移語(yǔ)句。流圖：有向圖。將控制流的信息增加到基本塊的集合上來(lái)表示一個(gè)*(1)readx(2)ready*(3)r=xmody(4)ifr=0goto(8)*(5)x=y(6)y=r(7)goto(3)*(8)writey(9)halt《編譯原理實(shí)踐及應(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—?jiǎng)h除公共子表達(dá)式如果表達(dá)式E已經(jīng)在前面計(jì)算過(guò)，并在計(jì)算之后E的值沒(méi)有改變，則稱該表達(dá)式為公共子表達(dá)式。可以避免重復(fù)計(jì)算。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ù)計(jì)算優(yōu)化技術(shù)1—?jiǎng)h除公共子表達(dá)式如果表達(dá)式E已經(jīng)在前面計(jì)算過(guò)，并在更大的范圍內(nèi)刪除4*i,4*j的計(jì)算，得到：在更大的范圍內(nèi)刪除4*i,4*j的計(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]，之間沒(méi)有改變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—?jiǎng)h除無(wú)用代碼a[T2]=T5a[T4]=T3gotoB2T6=T2x=T3T7=T2T8=T4T9=T5a[T2]=T5T10=T4a[T4]=T3gotoB2某些變量的賦值無(wú)用，在后面的程序中不再有用a[T2]=va[T1]=T3B5B6優(yōu)化技術(shù)3—?jiǎng)h除無(wú)用代碼a[T2]=T5T6=T2某些變量的《編譯原理實(shí)踐及應(yīng)用》第7章代碼優(yōu)化課件優(yōu)化技術(shù)4——對(duì)程序進(jìn)行代數(shù)恒等變換（合并已知量）T1=2……T2=4*T1T1=2……T2=8優(yōu)化技術(shù)4——對(duì)程序進(jìn)行代數(shù)恒等變換（合并已知量）T1=2T優(yōu)化技術(shù)4—對(duì)程序進(jìn)行代數(shù)恒等變換（降低運(yùn)算強(qiáng)度）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—對(duì)程序進(jìn)行代數(shù)恒等變換（降低運(yùn)算強(qiáng)度）a)i*優(yōu)化技術(shù)4——對(duì)程序進(jìn)行代數(shù)恒等變換（代數(shù)化簡(jiǎn)）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——對(duì)程序進(jìn)行代數(shù)恒等變換（代數(shù)化簡(jiǎn)）x+0=基本塊的DAG表示及其應(yīng)用DAGDirectedAcyclicGraph有向無(wú)環(huán)路圖基本塊的DAG是在結(jié)點(diǎn)上帶有標(biāo)記的DAGDAG表示了基本塊的計(jì)算過(guò)程葉結(jié)點(diǎn)表示標(biāo)識(shí)符或常數(shù)的值，以標(biāo)識(shí)符或常數(shù)作為標(biāo)記內(nèi)部結(jié)點(diǎn)以運(yùn)算符作為標(biāo)記，表示運(yùn)算結(jié)果邊表示了操作間的前驅(qū)和后繼的關(guān)系每個(gè)結(jié)點(diǎn)：附加標(biāo)識(shí)符標(biāo)記，可以是一個(gè)或多個(gè)標(biāo)識(shí)符都具有該結(jié)點(diǎn)代表的值基本塊的DAG表示及其應(yīng)用DAGDirectedAc用DAG進(jìn)行基本塊的優(yōu)化(0)x=y(1)x=opy(2)x=yopz用DAG進(jìn)行基本塊的優(yōu)化(0)x=y(1)x=op基本塊的DAG構(gòu)造算法:首先，DAG為空。對(duì)基本塊的每一四元式，依次執(zhí)行1，2，3，4步：1.如果NODE(B)無(wú)定義，則構(gòu)造一標(biāo)記為B的葉結(jié)點(diǎn)并定義NODE(B)為這個(gè)結(jié)點(diǎn)；如果當(dāng)前四元式是0型，則記NODE(B)的值為n，轉(zhuǎn)4。如果當(dāng)前四元式是1型，則轉(zhuǎn)2(1)。如果當(dāng)前四元式是2型，則：

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

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

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

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

(4)執(zhí)行BopC（即合并已知量），令得到的新常數(shù)為P。如果NODE(B)或NODE(C)是處理當(dāng)前四元式時(shí)新構(gòu)造出來(lái)的結(jié)點(diǎn)，則刪除它。如果NODE(P)無(wú)定義，則構(gòu)造一用P做標(biāo)記的葉結(jié)點(diǎn)n。置NODE(P)=n，轉(zhuǎn)4。2.(1)如果NODE(B)是標(biāo)記為常數(shù)的葉結(jié)點(diǎn)，則轉(zhuǎn)3.(1)檢查DAG中是否已有一結(jié)點(diǎn)，其唯一后繼為NODE(B)，且標(biāo)記為op（即找公共子表達(dá)式）。如果沒(méi)有，則構(gòu)造該結(jié)點(diǎn)n，否則就把已有的結(jié)點(diǎn)作為它的結(jié)點(diǎn)并設(shè)該結(jié)點(diǎn)為n，轉(zhuǎn)4。(2)檢查中DAG中是否已有一結(jié)點(diǎn)，其左后繼為NODE(B)，其右后繼為NODE(C)，且標(biāo)記為op（即找公共子表達(dá)式）。如果沒(méi)有，則構(gòu)造該結(jié)點(diǎn)n，否則就把已有的結(jié)點(diǎn)作為它的結(jié)點(diǎn)并設(shè)該結(jié)點(diǎn)為n，轉(zhuǎn)4。4.如果NODE(A)無(wú)定義，則把A附加在結(jié)點(diǎn)n上并令NODE(A)=n；否則先把A從NODE(A)結(jié)點(diǎn)上附加標(biāo)識(shí)符集中刪除（注意，如果NODE(A)是葉結(jié)點(diǎn)，則其標(biāo)記A不刪除），把A附加到新結(jié)點(diǎn)n上并令NODE(A)=n。轉(zhuǎn)處理下一四元式。這樣，就可由DAG重新生成原基本塊的一個(gè)優(yōu)化的代碼序列。3.(1)檢查DAG中是否已有一結(jié)點(diǎn)，其唯一后繼為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圖，可以更進(jìn)一步實(shí)現(xiàn)優(yōu)化：合并已知量，如T1，T3刪除冗余賦值，如B的第一次賦值公共子表達(dá)式的提取，如T2和T4在基本塊外被定值并在基本塊內(nèi)被引用的所有標(biāo)識(shí)符，就是作為葉結(jié)點(diǎn)上標(biāo)記的那些標(biāo)識(shí)符在基本塊內(nèi)被定值且該值能在基本塊后面被引用的所有標(biāo)識(shí)符，就是DAG各結(jié)點(diǎn)上的那些附加標(biāo)識(shí)符DAG的應(yīng)用根據(jù)DAG圖，可以更進(jìn)一步實(shí)現(xiàn)優(yōu)化：(1)

T1=R+r(2)

A=6.28*T1

(3)

T2=R-r(4)

B=S*T2

簡(jiǎn)化后的代碼序列(1)

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

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

結(jié)點(diǎn)n的所有必經(jīng)結(jié)點(diǎn)的集合,稱為結(jié)點(diǎn)n的必經(jīng)結(jié)點(diǎn)集,記為D(n).程序流圖中結(jié)點(diǎn)間的關(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é)點(diǎn)d

，結(jié)點(diǎn)

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