《編譯原理》第10章 優(yōu)化

編譯原理第十章優(yōu)化編輯ppt源程序詞法分析器錯(cuò)誤處理器符號管理表語法分析器語義分析器中間代碼生成器代碼優(yōu)化器代碼生成器編輯ppt第十章優(yōu)化優(yōu)化概述局部優(yōu)化循環(huán)優(yōu)化編輯ppt第十章優(yōu)化優(yōu)化：對程序進(jìn)行各種等價(jià)變換，使得從變換后的程序出發(fā)，能生成更有效的目標(biāo)代碼。等價(jià)：指不改變程序的運(yùn)行結(jié)果。有效：指目標(biāo)代碼運(yùn)行時(shí)間短，占用的存儲空間小。編輯ppt10.1概述優(yōu)化的目的產(chǎn)生更高效的代碼。優(yōu)化必須遵循一定的原則：等價(jià)原則：經(jīng)過優(yōu)化后不應(yīng)改變程序運(yùn)行的結(jié)果；有效原則：使優(yōu)化后所產(chǎn)生的目標(biāo)代碼運(yùn)行時(shí)間較短，占用的存儲空間較小；合算原則：應(yīng)盡可能以較低的代價(jià)取得較好的優(yōu)化效果。編輯ppt10.1概述優(yōu)化的三個(gè)不同級別：局部優(yōu)化循環(huán)優(yōu)化全局優(yōu)化優(yōu)化的種類：刪除多余運(yùn)算(或稱刪除公用子表達(dá)式)代碼外提強(qiáng)度消弱變換循環(huán)控制條件合并已知量復(fù)寫傳播刪除無用賦值編輯pptvoidquicksort(m,n);intm,n; { inti,j; intv,x; if(n<=m)return; /*fragmentbeginshere*/ 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; /*fragmentendshere*/ quicksort(m,j);quicksort(i+1,n);}編輯ppt中間代碼程序段

i:=m-1j:=nT1:=4*nv:=a[T1]B1i:=i+1T2:=4*iT3:=a[T2]ifT3<vgotoB2B2j:=j-1T4:=4*jT5:=a[T4]ifT5>vgotoB3B3ifi>=jgotoB6B4T6:=4*ix:=a[T6]T7:=4*iT8:=4*jT9:=a[T8]a[T7]=T9T10:=4*j

a[T10]=xgotoB2B5T11:=4*ix:=a[T11]T12:=4*iT13:=4*nT14:=a[T13]a[T12]=T14T15:=4*na[T15]=xB6編輯ppt中間代碼程序段

i:=m-1j:=nT1:=4*nv:=a[T1]B1i:=i+1T2:=4*i

T3:=a[T2]ifT3<vgotoB2B2j:=j-1T4:=4*j

T5:=a[T4]ifT5>vgotoB3B3ifi>=jgotoB6B4T6:=4*ix:=a[T6]T7:=4*iT8:=4*jT9:=a[T8]a[T7]=T9T10:=4*j

a[T10]=xgotoB2B5T11:=4*ix:=a[T11]T12:=4*iT13:=4*nT14:=a[T13]a[T12]=T14T15:=4*na[T15]=xB6編輯ppt公共子表達(dá)式i:=m-1j:=nT1:=4*nv:=a[T1]B1i:=i+1T2:=4*iT3:=a[T2]ifT3<vgotoB2B2j:=j-1T4:=4*jT5:=a[T4]ifT5>vgotoB3B3ifi>=jgotoB6B4T6:=4*ix:=a[T6]T7:=4*iT8:=4*jT9:=a[T8]a[T7]=T9T10:=4*j

a[T10]=xgotoB2B5T11:=4*ix:=a[T11]T12:=4*iT13:=4*nT14:=a[T13]a[T12]=T14T15:=4*na[T15]=xB6如果一個(gè)表達(dá)式E在前面已經(jīng)計(jì)算過，且在這之后E中變量的值沒有改變，則稱E為公共子表達(dá)式編輯ppt刪除公用子表達(dá)式后i:=m-1j:=nT1:=4*nv:=a[T1]B1i:=i+1T2:=4*iT3:=a[T2]ifT3<vgotoB2B2j:=j-1T4:=4*jT5:=a[T4]ifT5>vgotoB3B3ifi>=jgotoB6B4T6:=4*ix:=a[T6]T7:=4*iT8:=4*jT9:=a[T8]a[T7]=T9T10:=4*j

a[T10]=xgotoB2B5T11:=4*ix:=a[T11]T12:=4*iT13:=T1T14:=a[T13]a[T12]=T14T15:=T13a[T15]=xB6編輯ppti:=m-1j:=nT1:=4*nv:=a[T1]B1i:=i+1T2:=4*iT3:=a[T2]ifT3<vgotoB2B2j:=j-1T4:=4*jT5:=a[T4]ifT5>vgotoB3B3ifi>=jgotoB6B4T6:=4*ix:=a[T6]T7:=4*iT8:=4*jT9:=a[T8]a[T7]=T9T10:=4*j

a[T10]=xgotoB2B5T11:=4*ix:=a[T11]T12:=4*iT13:=T1T14:=a[T13]a[T12]=T14T15:=T13a[T15]=xB6公共子表達(dá)式編輯ppt刪除公用子表達(dá)式后i:=m-1j:=nT1:=4*nv:=a[T1]B1i:=i+1T2:=4*iT3:=a[T2]ifT3<vgotoB2B2j:=j-1T4:=4*jT5:=a[T4]ifT5>vgotoB3B3ifi>=jgotoB6B4T6:=T2x:=a[T6]T7:=T6T8:=4*jT9:=a[T8]a[T7]=T9T10:=4*j

a[T10]=xgotoB2B5T11:=T2x:=a[T11]T12:=T11T13:=T1T14:=a[T13]a[T12]=T14T15:=T13a[T15]=xB6編輯ppti:=m-1j:=nT1:=4*nv:=a[T1]B1i:=i+1T2:=4*iT3:=a[T2]ifT3<vgotoB2B2j:=j-1T4:=4*jT5:=a[T4]ifT5>vgotoB3B3ifi>=jgotoB6B4T6:=T2x:=a[T6]T7:=T6T8:=4*jT9:=a[T8]a[T7]=T9T10:=4*j

a[T10]=xgotoB2B5T11:=T2x:=a[T11]T12:=T11T13:=T1T14:=a[T13]a[T12]=T14T15:=T13a[T15]=xB6公共子表達(dá)式編輯ppt刪除公用子表達(dá)式后i:=m-1j:=nT1:=4*nv:=a[T1]B1i:=i+1T2:=4*iT3:=a[T2]ifT3<vgotoB2B2j:=j-1T4:=4*jT5:=a[T4]ifT5>vgotoB3B3ifi>=jgotoB6B4T6:=T2x:=a[T6]T7:=T6T8:=T4T9:=a[T8]a[T7]=T9T10:=T8a[T10]=xgotoB2B5T11:=T2x:=a[T11]T12:=T11T13:=T1T14:=a[T13]a[T12]=T14T15:=T13a[T15]=xB6編輯ppt復(fù)寫傳播i:=m-1j:=nT1:=4*nv:=a[T1]B1i:=i+1T2:=4*iT3:=a[T2]ifT3<vgotoB2B2j:=j-1T4:=4*jT5:=a[T4]ifT5>vgotoB3B3ifi>=jgotoB6B4T6:=T2x:=a[T6]T7:=T6T8:=T4T9:=a[T8]a[T7]=T9T10:=T8a[T10]=xgotoB2B5T11:=T2x:=a[T11]T12:=T11T13:=T1T14:=a[T13]a[T12]=T14T15:=T13a[T15]=xB6B5中，T6:=T2和x:=a[T6]中間T6的值沒變過，可把x:=a[T6]改寫成x:=a[T2]，這種變換稱為復(fù)寫傳播。編輯ppt復(fù)寫傳播i:=m-1j:=nT1:=4*nv:=a[T1]B1i:=i+1T2:=4*iT3:=a[T2]ifT3<vgotoB2B2j:=j-1T4:=4*jT5:=a[T4]ifT5>vgotoB3B3ifi>=jgotoB6B4T6:=T2x:=a[T2]T7:=T2T8:=T4T9:=a[T8]a[T2]=T9T10:=T8a[T10]=xgotoB2B5T11:=T2x:=a[T11]T12:=T11T13:=T1T14:=a[T13]a[T12]=T14T15:=T13a[T15]=xB6編輯ppt復(fù)寫傳播i:=m-1j:=nT1:=4*nv:=a[T1]B1i:=i+1T2:=4*iT3:=a[T2]ifT3<vgotoB2B2j:=j-1T4:=4*jT5:=a[T4]ifT5>vgotoB3B3ifi>=jgotoB6B4T6:=T2x:=a[T2]T7:=T2T8:=T4T9:=a[T8]a[T2]=T9T10:=T8a[T10]=xgotoB2B5T11:=T2x:=a[T11]T12:=T11T13:=T1T14:=a[T13]a[T12]=T14T15:=T13a[T15]=xB6編輯ppt復(fù)寫傳播i:=m-1j:=nT1:=4*nv:=a[T1]B1i:=i+1T2:=4*iT3:=a[T2]ifT3<vgotoB2B2j:=j-1T4:=4*jT5:=a[T4]ifT5>vgotoB3B3ifi>=jgotoB6B4T6:=T2x:=a[T2]T7:=T2T8:=T4T9:=a[T8]a[T2]=T9T10:=T8a[T10]=xgotoB2B5T11:=T2x:=a[T2]T12:=T2T13:=T1T14:=a[T13]a[T2]=T14T15:=T13a[T15]=xB6編輯ppt復(fù)寫傳播i:=m-1j:=nT1:=4*nv:=a[T1]B1i:=i+1T2:=4*iT3:=a[T2]ifT3<vgotoB2B2j:=j-1T4:=4*jT5:=a[T4]ifT5>vgotoB3B3ifi>=jgotoB6B4T6:=T2x:=a[T2]T7:=T2T8:=T4T9:=a[T8]a[T2]=T9T10:=T8a[T10]=xgotoB2B5T11:=T2x:=a[T2]T12:=T2T13:=T1T14:=a[T13]a[T2]=T14T15:=T13a[T15]=xB6編輯ppt復(fù)寫傳播i:=m-1j:=nT1:=4*nv:=a[T1]B1i:=i+1T2:=4*iT3:=a[T2]ifT3<vgotoB2B2j:=j-1T4:=4*jT5:=a[T4]ifT5>vgotoB3B3ifi>=jgotoB6B4T6:=T2x:=a[T2]T7:=T2T8:=T4T9:=a[T4]a[T2]=T9T10:=T4a[T4]=xgotoB2B5T11:=T2x:=a[T2]T12:=T2T13:=T1T14:=a[T13]a[T2]=T14T15:=T13a[T15]=xB6編輯ppt復(fù)寫傳播i:=m-1j:=nT1:=4*nv:=a[T1]B1i:=i+1T2:=4*iT3:=a[T2]ifT3<vgotoB2B2j:=j-1T4:=4*jT5:=a[T4]ifT5>vgotoB3B3ifi>=jgotoB6B4T6:=T2x:=a[T2]T7:=T2T8:=T4T9:=a[T4]a[T2]=T9T10:=T4a[T4]=xgotoB2B5T11:=T2x:=a[T2]T12:=T2T13:=T1T14:=a[T13]a[T2]=T14T15:=T13a[T15]=xB6編輯ppt復(fù)寫傳播i:=m-1j:=nT1:=4*nv:=a[T1]B1i:=i+1T2:=4*iT3:=a[T2]ifT3<vgotoB2B2j:=j-1T4:=4*jT5:=a[T4]ifT5>vgotoB3B3ifi>=jgotoB6B4T6:=T2x:=a[T2]T7:=T2T8:=T4T9:=a[T4]a[T2]=T9T10:=T4a[T4]=xgotoB2B5T11:=T2x:=a[T2]T12:=T2T13:=T1T14:=a[T1]a[T2]=T14T15:=T1a[T1]=xB6編輯ppt復(fù)寫傳播i:=m-1j:=nT1:=4*nv:=a[T1]B1i:=i+1T2:=4*iT3:=a[T2]ifT3<vgotoB2B2j:=j-1T4:=4*jT5:=a[T4]ifT5>vgotoB3B3ifi>=jgotoB6B4T6:=T2x:=a[T2]T7:=T2T8:=T4T9:=a[T4]a[T2]=T9T10:=T4a[T4]=xgotoB2B5T11:=T2x:=a[T2]T12:=T2T13:=T1T14:=a[T1]a[T2]=T14T15:=T1a[T1]=xB6編輯ppt復(fù)寫傳播i:=m-1j:=nT1:=4*nv:=a[T1]B1i:=i+1T2:=4*iT3:=a[T2]ifT3<vgotoB2B2j:=j-1T4:=4*jT5:=a[T4]ifT5>vgotoB3B3ifi>=jgotoB6B4T6:=T2x:=a[T2]T7:=T2T8:=T4T9:=a[T4]a[T2]=T9T10:=T4a[T4]=xgotoB2B5T11:=T2x:=a[T2]T12:=T2T13:=T1T14:=va[T2]=vT15:=T1a[T1]=xB6編輯ppt復(fù)寫傳播i:=m-1j:=nT1:=4*nv:=a[T1]B1i:=i+1T2:=4*iT3:=a[T2]ifT3<vgotoB2B2j:=j-1T4:=4*jT5:=a[T4]ifT5>vgotoB3B3ifi>=jgotoB6B4T6:=T2x:=a[T2]T7:=T2T8:=T4T9:=a[T4]a[T2]=T9T10:=T4a[T4]=xgotoB2B5T11:=T2x:=a[T2]T12:=T2T13:=T1T14:=va[T2]=vT15:=T1a[T1]=xB6編輯ppt復(fù)寫傳播i:=m-1j:=nT1:=4*nv:=a[T1]B1i:=i+1T2:=4*iT3:=a[T2]ifT3<vgotoB2B2j:=j-1T4:=4*jT5:=a[T4]ifT5>vgotoB3B3ifi>=jgotoB6B4T6:=T2x:=T3T7:=T2T8:=T4T9:=a[T4]a[T2]=T9T10:=T4a[T4]=T3gotoB2B5T11:=T2x:=T3T12:=T2T13:=T1T14:=va[T2]=vT15:=T1a[T1]=T3B6編輯ppt復(fù)寫傳播i:=m-1j:=nT1:=4*nv:=a[T1]B1i:=i+1T2:=4*iT3:=a[T2]ifT3<vgotoB2B2j:=j-1T4:=4*jT5:=a[T4]ifT5>vgotoB3B3ifi>=jgotoB6B4T6:=T2x:=T3T7:=T2T8:=T4T9:=a[T4]a[T2]=T9T10:=T4a[T4]=T3gotoB2B5T11:=T2x:=T3T12:=T2T13:=T1T14:=va[T2]=vT15:=T1a[T1]=T3B6編輯ppt復(fù)寫傳播i:=m-1j:=nT1:=4*nv:=a[T1]B1i:=i+1T2:=4*iT3:=a[T2]ifT3<vgotoB2B2j:=j-1T4:=4*jT5:=a[T4]ifT5>vgotoB3B3ifi>=jgotoB6B4T6:=T2x:=T3T7:=T2T8:=T4T9:=T5a[T2]=T5T10:=T4a[T4]=T3gotoB2B5T11:=T2x:=T3T12:=T2T13:=T1T14:=va[T2]=vT15:=T1a[T1]=T3B6編輯ppt刪除無用賦值i:=m-1j:=nT1:=4*nv:=a[T1]B1i:=i+1T2:=4*iT3:=a[T2]ifT3<vgotoB2B2j:=j-1T4:=4*jT5:=a[T4]ifT5>vgotoB3B3ifi>=jgotoB6B4T6:=T2x:=T3T7:=T2T8:=T4T9:=T5a[T2]=T5T10:=T4a[T4]=T3gotoB2B5T11:=T2x:=T3T12:=T2T13:=T1T14:=va[T2]=vT15:=T1a[T1]=T3B6編輯ppt刪除無用賦值后i:=m-1j:=nT1:=4*nv:=a[T1]B1i:=i+1T2:=4*iT3:=a[T2]ifT3<vgotoB2B2j:=j-1T4:=4*jT5:=a[T4]ifT5>vgotoB3B3ifi>=jgotoB6B4a[T2]=T5a[T4]=T3gotoB2B5a[T2]=va[T1]=T3B6編輯ppt強(qiáng)度削弱i:=m-1j:=nT1:=4*nv:=a[T1]B1i:=i+1T2:=4*i

T3:=a[T2]ifT3<vgotoB2B2j:=j-1T4:=4*j

T5:=a[T4]ifT5>vgotoB3B3ifi>=jgotoB6B4a[T2]=T5a[T4]=T3gotoB2B5a[T2]=va[T1]=T3B6編輯ppt強(qiáng)度削弱后i:=m-1j:=nT1:=4*nv:=a[T1]T2:=4*iT4:=4*jB1i:=i+1T2:=T2+4

T3:=a[T2]ifT3<vgotoB2B2j:=j-1T4:=T4-4

T5:=a[T4]ifT5>vgotoB3B3ifi>=jgotoB6B4a[T2]=T5a[T4]=T3gotoB2B5a[T2]=va[T1]=T3B6編輯ppt刪除歸納變量i:=m-1j:=nT1:=4*nv:=a[T1]T2:=4*iT4:=4*jB1i:=i+1T2:=T2+4T3:=a[T2]ifT3<vgotoB2B2j:=j-1T4:=T4-4T5:=a[T4]ifT5>vgotoB3B3ifi>=jgotoB6B4a[T2]=T5a[T4]=T3gotoB2B5a[T2]=va[T1]=T3B6編輯ppt刪除歸納變量后i:=m-1j:=nT1:=4*nv:=a[T1]T2:=4*iT4:=4*jB1T2:=T2+4T3:=a[T2]ifT3<vgotoB2B2T4:=T4-4T5:=a[T4]ifT5>vgotoB3B3ifT2>=T4gotoB6B4a[T2]=T5a[T4]=T3gotoB2B5a[T2]=va[T1]=T3B6編輯ppt中間代碼程序段（優(yōu)化前）

i:=m-1j:=nT1:=4*nv:=a[T1]B1i:=i+1T2:=4*iT3:=a[T2]ifT3<vgotoB2B2j:=j-1T4:=4*jT5:=a[T4]ifT5>vgotoB3B3ifi>=jgotoB6B4T6:=4*ix:=a[T6]T7:=4*iT8:=4*jT9:=a[T8]a[T7]=T9T10:=4*j

a[T10]=xgotoB2B5T11:=4*ix:=a[T11]T12:=4*iT13:=4*nT14:=a[T13]a[T12]=T14T15:=4*na[T15]=xB6編輯ppt中間代碼程序段（優(yōu)化后）i:=m-1j:=nT1:=4*nv:=a[T1]T2:=4*iT4:=4*jB1T2:=T2+4T3:=a[T2]ifT3<vgotoB2B2T4:=T4-4T5:=a[T4]ifT5>vgotoB3B3ifT2>=T4gotoB6B4a[T2]=T5a[T4]=T3gotoB2B5a[T2]=va[T1]=T3B6編輯ppt10.2局部優(yōu)化基本塊：指程序中一順序執(zhí)行語句序列，其中只有一個(gè)入口和一個(gè)出口。入口就是其中第一個(gè)語句，出口就是其中最后一個(gè)語句。例:基本塊T1:=a*aT2:=a*bT3:=2*T2T4:=T1+T2T5:=b*bT6:=T4+T5如果一條三地址語句為x:=y+z，則稱對x定值并引用y和z。在一個(gè)基本塊中的一個(gè)名字，所謂在程序中的某個(gè)給定點(diǎn)是活躍的，是指如果在程序中(包括在本基本塊或在其它基本塊中)它的值在該點(diǎn)以后被引用。編輯ppt10.2局部優(yōu)化局限于基本塊范圍內(nèi)的優(yōu)化稱為基本塊內(nèi)的優(yōu)化，或稱局部優(yōu)化。對一個(gè)給定的程序，我們可以把它劃分成一系列的基本塊。在各個(gè)基本塊范圍內(nèi)，分別進(jìn)行優(yōu)化。如何將四元式劃分成基本塊？編輯ppt劃分四元式程序?yàn)榛緣K的算法:1.求出四元式程序中各個(gè)基本塊的入口語句:1)程序第一個(gè)語句，或2)能由條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句轉(zhuǎn)移到的語句，或3)緊跟在條件轉(zhuǎn)移語句后面的語句。編輯ppt劃分四元式程序?yàn)榛緣K的算法:2.對以上求出的每個(gè)入口語句，確定其所屬的基本塊。它是由該入口語句到下一入口語句(不包括該入口語句)之間的語句序列組成的。入口語句n……入口語句m編輯ppt劃分四元式程序?yàn)榛緣K的算法:2.對以上求出的每個(gè)入口語句，確定其所屬的基本塊。它是由該入口語句到下一入口語句(不包括該入口語句)、或到一轉(zhuǎn)移語句(包括該轉(zhuǎn)移語句)之間的語句序列組成的。入口語句n……入口語句m入口語句n……轉(zhuǎn)移語句m編輯ppt劃分四元式程序?yàn)榛緣K的算法:2.對以上求出的每個(gè)入口語句，確定其所屬的基本塊。它是由該入口語句到下一入口語句(不包括該入口語句)、或到一轉(zhuǎn)移語句(包括該轉(zhuǎn)移語句)、或一停語句(包括該停語句)之間的語句序列組成的。入口語句n……入口語句m入口語句n……轉(zhuǎn)移語句m入口語句n……停語句m3.凡未被納入某一基本塊中的語句，可以從程序中刪除。編輯ppt例：劃分基本塊(1) readX(2) readY(3) R:=XmodY(4) ifR=0goto(8)(5) X:=Y(6) Y:=R(7) goto(3)(8) writeY(9) halt1.求出四元式程序中各個(gè)基本塊的入口語句:1)程序第一個(gè)語句，或2)能由條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句轉(zhuǎn)移到的語句，或3)緊跟在條件轉(zhuǎn)移語句后面的語句。編輯ppt例：劃分基本塊(1) readX(2) readY(3) R:=XmodY(4) ifR=0goto(8)(5) X:=Y(6) Y:=R(7) goto(3)(8) writeY(9) halt1.求出四元式程序中各個(gè)基本塊的入口語句:1)程序第一個(gè)語句，或2)能由條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句轉(zhuǎn)移到的語句，或3)緊跟在條件轉(zhuǎn)移語句后面的語句。編輯ppt例：劃分基本塊(1) readX(2) readY(3) R:=XmodY(4) ifR=0goto(8)(5) X:=Y(6) Y:=R(7) goto(3)(8) writeY(9) halt1.求出四元式程序中各個(gè)基本塊的入口語句:1)程序第一個(gè)語句，或2)能由條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句轉(zhuǎn)移到的語句，或3)緊跟在條件轉(zhuǎn)移語句后面的語句。編輯ppt例：劃分基本塊(1) readX(2) readY(3) R:=XmodY(4) ifR=0goto(8)(5) X:=Y(6) Y:=R(7) goto(3)(8) writeY(9) halt1.求出四元式程序中各個(gè)基本塊的入口語句:1)程序第一個(gè)語句，或2)能由條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句轉(zhuǎn)移到的語句，或3)緊跟在條件轉(zhuǎn)移語句后面的語句。編輯ppt例：劃分基本塊(1) readX(2) readY(3) R:=XmodY(4) ifR=0goto(8)(5) X:=Y(6) Y:=R(7) goto(3)(8) writeY(9) halt1.求出四元式程序中各個(gè)基本塊的入口語句:1)程序第一個(gè)語句，或2)能由條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句轉(zhuǎn)移到的語句，或3)緊跟在條件轉(zhuǎn)移語句后面的語句。編輯ppt例：劃分基本塊(1) readX(2) readY(3) R:=XmodY(4) ifR=0goto(8)(5) X:=Y(6) Y:=R(7) goto(3)(8) writeY(9) halt2.對以上求出的每個(gè)入口語句，確定其所屬的基本塊。它是由該入口語句到下一入口語句(不包括該入口語句)、或到一轉(zhuǎn)移語句(包括該轉(zhuǎn)移語句)、或一停語句(包括該停語句)之間的語句序列組成的。編輯ppt流圖每個(gè)流圖以基本塊為結(jié)點(diǎn)。如果一個(gè)結(jié)點(diǎn)的基本塊的入口語句是程序的第一條語句，則稱此結(jié)點(diǎn)為首結(jié)點(diǎn)。如果在某個(gè)執(zhí)行順序中，基本塊B2緊接在基本塊B1之后執(zhí)行，則從B1到B2有一條有向邊。即，如果有一個(gè)條件或無條件轉(zhuǎn)移語句從B1的最后一條語句轉(zhuǎn)移到B2的第一條語句；或者在程序的序列中，B2緊接在B1的后面，并且B1的最后一條語句不是一個(gè)無條件轉(zhuǎn)移語句。我們就說B1是B2的前驅(qū)，B2是B1的后繼。編輯ppt(1) readX(2) readY(3) R:=XmodY(4) ifR=0goto(8)(5) X:=Y(6) Y:=R(7) goto(3)(8) writeY(9) halt(8)writeY(9)halt(5)X:=Y(6)Y:=R(7)goto(3)(3)R:=XmodY(4)ifR=0goto(8)(1)readX(2)readYB1B2B3B4編輯ppt10.2 局部優(yōu)化局限于基本塊范圍內(nèi)的優(yōu)化稱為基本塊內(nèi)的優(yōu)化，或稱局部優(yōu)化。在一個(gè)基本塊內(nèi)通常可以實(shí)行下面的優(yōu)化:刪除公共子表達(dá)式刪除無用賦值合并已知量臨時(shí)變量改名交換語句的位置代數(shù)變換編輯ppt優(yōu)化措施合并已知量

T1:=2…T2:=4*T1 變換成

T2:=8臨時(shí)變量改名

T:=b+c 其中T是一個(gè)臨時(shí)變量名。把這個(gè)語句改成：S:=b+c編輯ppt優(yōu)化措施交換語句的位置

T1:=b+cT2:=x+y代數(shù)變換

x:=x+0或x:=x*1（可直接刪掉）

x:=y**2變換成 x:=y*y編輯ppt10.2.2 基本塊的DAG表示及其應(yīng)用有向圖有向邊:ninj前驅(qū)：ni是nj的前驅(qū)后繼：nj是ni的后繼通路:n1n2,n2n3,...,nk-1nk環(huán)路：n1=nkDAG：無環(huán)路有向圖(DirectedAcyclicGraph)n1n2n3n4n1n2n3n4編輯ppt7.1.2圖表示法圖表示法DAG抽象語法樹無循環(huán)有向圖(DirectedAcyclicGraph，簡稱DAG)對表達(dá)式中的每個(gè)子表達(dá)式，DAG中都有一個(gè)結(jié)點(diǎn)一個(gè)內(nèi)部結(jié)點(diǎn)代表一個(gè)操作符，它的孩子代表操作數(shù)在一個(gè)DAG中代表公共子表達(dá)式的結(jié)點(diǎn)具有多個(gè)父結(jié)點(diǎn)編輯ppt

a:=b*(-c)+b*(-c)的圖表示法assigna+*buminuscDAGassigna+*buminusc抽象語法樹*buminusc編輯pptDAG對應(yīng)的代碼：

T1:=-cT2:=b*T1T5:=T2+T2a:=T5assigna+*buminuscDAG編輯ppt描述計(jì)算過程的DAG是一種帶有下述標(biāo)記或附加信息的DAG:n13.14n3n4Rrn5+T2,T4圖的葉結(jié)點(diǎn)以一標(biāo)識符或常數(shù)作為標(biāo)記，表示該結(jié)點(diǎn)代表該變量或常數(shù)的值;圖的內(nèi)部結(jié)點(diǎn)以一運(yùn)算符作為標(biāo)記，表示該結(jié)點(diǎn)代表應(yīng)用該運(yùn)算符對其后繼結(jié)點(diǎn)所代表的值進(jìn)行運(yùn)算的結(jié)果;圖中各個(gè)結(jié)點(diǎn)上可能附加一個(gè)或多個(gè)標(biāo)識符(稱附加標(biāo)識符)表示這些變量具有該結(jié)點(diǎn)所代表的值。編輯ppt10.2.2基本塊的DAG表示及應(yīng)用一個(gè)基本塊，可用一個(gè)DAG來表示與各四元式相對應(yīng)的DAG結(jié)點(diǎn)形式:四元式 DAG圖(0)0型:A:=B(:=，B，-，A)

n1AB編輯ppt四元式

DAG

圖(1)1型:A:=opB(op，B，-，A)n1ABn2op(2)2型:A:=BopC(op，B，C，A)n2ABn1opn3C編輯ppt四元式

DAG圖(3)2型:A:=B[C](=[]，B[C]，-，A)n2ABn1=[]n3C(4)2型:ifBropCgoto(s)(jrop，B，C，(s))n2(s)Bn1ropn3C編輯ppt四元式 DAG圖(5)3型:D[C]:=B([]=，B，-，D[C])(6)0型:goto(s)(j，-，-，(s))(s)n1n2Bn1[]=n4Cn3D編輯ppt假設(shè)DAG各結(jié)點(diǎn)信息將用某種適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)存放(如鏈表)。另設(shè)置一個(gè)標(biāo)識符與結(jié)點(diǎn)的對應(yīng)函數(shù):編輯ppt0，1，2型四元式的基本塊的DAG構(gòu)造算法對基本塊中每一四元式，依次執(zhí)行以下步驟:1.準(zhǔn)備操作數(shù)的結(jié)點(diǎn)2.合并已知量3.刪除公共子表達(dá)式4.刪除無用賦值編輯ppt1.準(zhǔn)備操作數(shù)的結(jié)點(diǎn)

如果NODE(B)無定義，則構(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型，則(i)如果NODE(C)無定義，則構(gòu)造一標(biāo)記為C的葉結(jié)點(diǎn)并定義NODE(C)為這個(gè)結(jié)點(diǎn)；(ii)轉(zhuǎn)2(2)。1.準(zhǔn)備操作數(shù)的結(jié)點(diǎn)2.合并已知量3.刪除公共子表達(dá)式4.刪除無用賦值

A:=opB

A:=BopC

A:=B編輯ppt2.合并已知量(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)造出來的結(jié)點(diǎn)，則刪除它。如果NODE(P)無定義，則構(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)造出來的結(jié)點(diǎn)，則刪除它。如果NODE(P)無定義，則構(gòu)造一用P作標(biāo)記的葉結(jié)點(diǎn)n。置NODE(P)=n，轉(zhuǎn)4。1.準(zhǔn)備操作數(shù)的結(jié)點(diǎn)2.合并已知量3.刪除公共子表達(dá)式4.刪除無用賦值

A:=opB

A:=BopC編輯ppt3.尋找公共子表達(dá)式(1)檢查DAG中是否已有一結(jié)點(diǎn)，其唯一后繼為NODE(B)且標(biāo)記為op(即公共子表達(dá)式)。如果沒有，則構(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á)式)。如果沒有，則構(gòu)造該結(jié)點(diǎn)n，否則，把已有的結(jié)點(diǎn)作為它的結(jié)點(diǎn)并設(shè)該結(jié)點(diǎn)為n。轉(zhuǎn)4。1.準(zhǔn)備操作數(shù)的結(jié)點(diǎn)2.合并已知量3.刪除公共子表達(dá)式4.刪除無用賦值

A:=BopC

A:=BopC編輯ppt4.刪除無用賦值如果NODE(A)無定義，則把A附加在結(jié)點(diǎn)n上并令NODE(A)=n;否則，先把A從NODE(A)結(jié)點(diǎn)上的附加標(biāo)識符集中刪除(注意，如果NODE(A)是葉結(jié)點(diǎn)，則其A標(biāo)記不刪除)。把A附加到新結(jié)點(diǎn)n上并置NODE(A)=n。轉(zhuǎn)處理下一四元式。1.準(zhǔn)備操作數(shù)的結(jié)點(diǎn)2.合并已知量3.刪除公共子表達(dá)式4.刪除無用賦值編輯ppt例10.4 試構(gòu)造以下基本塊G的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編輯ppt(1) T0:=3.14n13.14T0n26.28T1n3n4Rrn5+T2n6*A,B,T3,T4,T5n7T6-n8*B(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*T6T6編輯ppt優(yōu)化后的四元式(1) T0:=3.14(2) T1:=6.28(3) T3:=6.28(4) T2:=R+r(5) T4:=T2(6)A:=6.28*T2(7) T5:=A(8) T6:=R-r(9) B:=A*T6n13.14T0n26.28T1n3n4Rrn5+T2n6*A,B,T3,T4,T5n7T6-n8*BT6(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編輯ppt優(yōu)化后的四元式——若只有A和B是出基本塊之后活躍的

優(yōu)化后的代碼只剩下4句：(1)T2:=R+r(2)A:=6.28*T2(3)T6:=R-r(4)B:=A*T6變量替換后代碼為：(1)S1:=R+r(2)A:=6.28*S1(3)S2:=R-r(4) B:=A*S2n13.14T0n26.28T1n3n4Rrn5+T2n6*A,B,T3,T4,T5n7T6-n8*BT6編輯ppt從DAG中還能得到其他的優(yōu)化信息：在基本塊外被定值并在基本塊內(nèi)被引用的所有標(biāo)識符，就是作為葉子結(jié)點(diǎn)上標(biāo)記的那些標(biāo)識符。在基本塊內(nèi)被定值并且該值在基本塊后面可以被引用的所有標(biāo)識符，就是DAG各結(jié)點(diǎn)上的那些附加標(biāo)識符。編輯ppt10.3循環(huán)優(yōu)化對循環(huán)中的代碼，可以實(shí)行：代碼外提強(qiáng)度消弱刪除歸納變量(變換循環(huán)控制條件)循環(huán)展開循環(huán)合并

編輯ppt10.3.1代碼外提所謂變量A在某點(diǎn)d的定值到達(dá)另一點(diǎn)u（或稱變量A的定值點(diǎn)d到達(dá)另一點(diǎn)u），是指流圖中從d有一通路到達(dá)u且該通路上沒有A的其它定值。d:A:=BopC…u:D:=AopE循環(huán)不變運(yùn)算:對四元式A:=BopC,若B和C是常數(shù)，或者到達(dá)它們的B和C的定值點(diǎn)都在循環(huán)外。把循環(huán)不變運(yùn)算提到循環(huán)體外。編輯ppt入口結(jié)點(diǎn)循環(huán)L入口結(jié)點(diǎn)循環(huán)L前置結(jié)點(diǎn)編輯ppt代碼外提條件forI:=1to10do A[I,2*J]:=A[I,2*J]+1(1) I:=1(2)ifI>10goto(15)(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)gotoB2B3B2B1(15)編輯ppt(1) I:=1(2)ifI>10goto(15)(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)gotoB2B3B2B1(15)(1) I:=1(2)ifI>10goto(15)(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)gotoB2B3B2B1(15)(3)T1=2*J(6)T4=addr(A)-11(7)T5=2*J(10)T8=addr(A)-11B2’編輯ppt(1) I:=1(2)ifX<YgotoB3B1B2(3)I:=2(4)X:=X+1(5)Y:=Y-1(6)ifY<=20gotoB5(7)J:=IB3B4B5X=30,Y=25B1B2

B4

B2

B4

…

B2

B4

B5J=1,I=1編輯ppt(3) I:=2(2)ifX<YgotoB3B1B2(4)X:=X+1(5)Y:=Y-1(6)ifY<=20gotoB5(7)J:=IB3B4B5(1) I:=1B2’X=30,Y=25B1B2

B4

B2

B4

…

B2

B4

B5J=2,I=2代碼外提條件:不變運(yùn)算所在的結(jié)點(diǎn)是L所有出口結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)——即不變運(yùn)算是循環(huán)L必須要執(zhí)行的語句編輯ppt(1) I:=1(2‘)I:=3(2)ifX<YgotoB3B1B2(3)I:=2(4)X:=X+1(5)Y:=Y-1(6)ifY<=20gotoB5(7)J:=IB3B4B5考慮:

X=1,Y=2

B2B3

B4

B2

B4

B5I=3,J=3編輯ppt(2‘) I:=3(2)ifX<YgotoB3B1B2(3) I:=2(4)X:=X+1(5)Y:=Y-1(6)ifY<=20gotoB5(7)J:=IB3B4B5(1) I:=1B2’考慮考慮:

X=1,Y=2

:B2B3

B4

B2

B4

B5I=2,J=2代碼外提條件:A在循環(huán)中其他地方未再定值,才能把循環(huán)不變運(yùn)算A:=BopC外提;

編輯ppt考慮:

X=0,Y=2

B2B3

B4

B2

B4

B5A=2,J=2(1) I:=1(2)ifX<YgotoB3B1B2(3)A:=I+1(4)X:=X+1(5)I:=2(6)Y:=Y-1(7)ifY<=0gotoB5(8)J:=AB3B4B5編輯ppt(5) I:=2(2)ifX<YgotoB3B1B2(3)A:=I+1(4)X:=X+1(6)Y:=Y-1(7)ifY<=20gotoB5(8)J:=AB3B4B5(1) I:=1B2’考慮:

X=0,Y=2

B2B3

B4

B2

B4

B5A=3,J=3S(A:=BOPC)外提條件:循環(huán)中所有A的引用點(diǎn)只有S中的A的定值才能到達(dá)。編輯pptS(A:=BOPC)外提條件:(1)不變運(yùn)算所在的結(jié)點(diǎn)是L所有出口結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn).(2)A在循環(huán)中其他地方未再定值(3)循環(huán)中所有A的引用點(diǎn)只有S中的A的定值才能到達(dá)。編輯ppt查找循環(huán)L的不變運(yùn)算的算法：依次查看L中各基本塊的每個(gè)四元式，如果它的每個(gè)運(yùn)算對象或?yàn)槌?shù)，或者定值點(diǎn)在L外，則將次四元式標(biāo)記為"不變運(yùn)算";重復(fù)第3步直至沒有新的四元式被標(biāo)記為"不變運(yùn)算"為止;依次查看尚未被標(biāo)記為"不變運(yùn)算"的四元式，如果它的每個(gè)運(yùn)算對象或?yàn)槌?shù)，或定值點(diǎn)在L之外，或只有一個(gè)到達(dá)-定值點(diǎn)且該點(diǎn)上的四元式已被標(biāo)記為"不變運(yùn)算"，則把被查看的四元式標(biāo)記為"不變運(yùn)算"。編輯ppt代碼外提算法:1.求出循環(huán)L的所有不變運(yùn)算2.對每個(gè)不變運(yùn)算s:A:=BopC或A:=opB或A:=B檢查是否滿足條件(1)或(2)

(1)(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á)。編輯ppt(2)A在離開L后不再是活躍的，并且條件(1)的(ii)和(iii)成立。所謂A在離開L后不是活躍的是指，A在L的任何出口結(jié)點(diǎn)的后記結(jié)點(diǎn)入口處不是活躍的。3.按步驟1所找出的不變運(yùn)算的次序，依次把符合條件2的條件(1)或(2)的不變運(yùn)算s外提到L的前置結(jié)點(diǎn)中。但是，如果s的運(yùn)算對象(B或C)是在L中定值的，那么，只有當(dāng)這些定值四元式都已外提到前置結(jié)點(diǎn)中時(shí)，才能把s也外提到前置結(jié)點(diǎn)中。編輯ppt10.3.2強(qiáng)度消弱把程序中執(zhí)行時(shí)間較長的運(yùn)算轉(zhuǎn)換為執(zhí)行時(shí)間較短的運(yùn)算。編輯ppt(1) I:=1(2)ifI>10goto(15)(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)gotoB2B3B2B1(15)(3)T1=2*J(6)T4=addr(A)-11(7)T5=2*J(10)T8=addr(A)-11B2’(1) I:=1(2)ifI>10goto(15)(5)T3=T2+T1(9)T7=T6+T5(11)T9=T8[T7](12)T4[T3]=T9+1(13)I:=I+1(4‘)T2=T2+10(8’)T6=T6+10(14)gotoB2B3B2B1(15)(3)T1=2*J(6)T4=addr(A)-11(7)T5=2*J(10)T8=addr(A)-11(4)T2=10*I(8)T6=10*IB2’編輯ppt(1) I:=1(2)ifI>10goto(15)(5)T3=T2+T1(9)T7=T6+T5(11)T9=T8[T7](12)T4[T3]=T9+1(13)I:=I+1(4‘)T2=T2+10(8’)T6=T6+10(14)gotoB2B3B2B1(15)(3)T1=2*J(6)T4=addr(A)-11(7)T5=2*J(10)T8=addr(A)-11(4)T2=