編譯原理及實現(xiàn)技術(shù)：23-中間代碼優(yōu)化1

第六章：中間代碼優(yōu)化（1）

代碼優(yōu)化的階段欲提高源程序的運行速度，需要經(jīng)過幾個階段的優(yōu)化：用戶對源程序進行優(yōu)化編譯器前端對中間代碼進行優(yōu)化編譯器后端對目標代碼進行優(yōu)化中間代碼優(yōu)化的分類從優(yōu)化的種類來看，中間代碼的優(yōu)化可有如下分類：局部優(yōu)化循環(huán)上的優(yōu)化循環(huán)不變式外體削減運算強度基本塊的優(yōu)化常表達式節(jié)省公共子表達式節(jié)省。全局優(yōu)化全局數(shù)據(jù)流分析，從而使優(yōu)化的效果更好。常見的編譯優(yōu)化的種類數(shù)學(xué)上的優(yōu)化：（-，a，0，t1）（*，a，1，t2）2*a轉(zhuǎn)化成a+a，a2轉(zhuǎn)化成a*a原則上說，可以不計算的則直接刪去其四元式，直接寫出結(jié)果；高運算強度的可以轉(zhuǎn)化成低運算強度的。常見的編譯優(yōu)化的種類表達式短路問題E=E1orE2E=E1andE2E1E2orETEFE1E2andEFET常見的編譯優(yōu)化的種類常表達式的節(jié)省在我們的計算過程中有一個表達式是3*3.14，這個實際上是兩個常數(shù)，他的結(jié)果我是可以計算出來的，這樣我們在編譯的過程中把3*3.14算出來，在目標程序的進行中就不用進行計算了。公共子表達式節(jié)省(消除重復(fù)操作)t=b*c;e=b*c+b*c;c=b*c+10;d=b*c+d;a[i][j]+a[i][k]常見的編譯優(yōu)化的種類循環(huán)不變量式提while(k<10){a[k]=b*c;k=k+1}t=b*c;while(k<10){a[k]=t;k=k+1;}如果有表達式的值在循環(huán)中不會改變，就需要把它提到循環(huán)體外面，可以大大提高目標程序的運行效率常見的編譯優(yōu)化的種類削減程序的運算強度是指用強度低的運算代替強度大的運算，通常也是針對循環(huán)的。forj:=1to100doA[j]=3*j+10;m=13;forj:=1to100do{A[j]=m;m=m+3;}常見的編譯優(yōu)化的種類寄存器優(yōu)化涉及到目標程序執(zhí)行的時候，如何分配目標機的寄存器。消除無用語句、消除冗余代碼。if(E1恒等于true)S1elseS2S1常見的編譯優(yōu)化的種類中間變量的優(yōu)化屬于空間上的優(yōu)化，假如兩個臨時變量的活動區(qū)不相交，則可以共用同一個存儲單元。目標代碼優(yōu)化通過確定目標代碼減少目標程序指令個數(shù)來提高執(zhí)行效率。譬如兩個運算分量都在寄存器中可以直接參與計算，不需要將其存入內(nèi)存后導(dǎo)出計算。常見的編譯優(yōu)化的種類全局優(yōu)化對程序全局進行數(shù)據(jù)流分析，優(yōu)化技術(shù)比較復(fù)雜，會導(dǎo)致編譯代價很大，優(yōu)化的效果也不是十分明顯，只有在特殊需求的情況下才要進行。基本塊的定義基本塊是指程序的一組順序執(zhí)行的語句序列，其中只有一個出口和一個入口。入口：基本塊的第一條語句；出口：基本塊的最后一條語句；語句1語句2語句n語句1語句2語句n語句1語句2語句n基本塊的劃分原則整個四元式序列的第一個四元式為基本塊的入口四元遇轉(zhuǎn)移性四元式時，結(jié)束當前基本塊，并把該四元式作為當前基本塊的出口，下一條四元式作為新基本塊的入口遇標號性四元式時結(jié)束當前基本塊，四元式本身作為新基本塊的入口遇到對地址引用型變量賦值四元式時，結(jié)束當前基本塊塊，并作為該塊的出口?；緣K的劃分原則轉(zhuǎn)移性四元式是指在生成目標代碼時一定產(chǎn)生跳轉(zhuǎn)指令的四元式。例如：（goto，—，—，L）（then，t，—，—）（else，—，—，—）（do，t，—，—）基本塊的劃分原則標號性四元式也稱定位性四元式，起到一個定位的作用不產(chǎn)生跳轉(zhuǎn)指令，例如：(LABEL,—,—,L)(ENTRY,F,—，—)(WHILE,—,—,—)(ENDIF,—,—,—)基本塊劃分的例子設(shè)有源程序如下：y:=1;L:ifAandBthenx:=0elsey:=0;x:=x+1;y:=y–1;whilex+y>0dox:=x-1;z:=0;注：x,y為非引用型整數(shù)類型形參。(ASSIGN,1,_,y)(LABEL,_,_,L)(AND，A,B,t0)(THEN,t0,-,-)(ASSIG,0,-，x)(ELSE,-,-,-)(ASSIG,0,_,y)(ENDIF,-,-,-)(+,x,1,t1)(ASSIG,t1,_,x)(-，

y,1,t2)(ASSIGN,t2,_,y)(WHILE,-,-,-)(ADDI,x,y,t3)(GT,t3,0,t4)(DO,t4,-,-)(-,x,1,t5)(ASSIG,t5,x)(ENDWHILE,-,-,-)(ASSIGN,0,_,Z)(ASSIG,1,-,y)(LABEL,-,-,L)(AND,A,B,t0)(THEN,t0,-,-)(ASSIG,0,-,x)(ELSE,-,-,-)(ASSIG,0,-,y)(ENDIF,-,-,-)(ADDI,x,1,t1)(ASSIG,t1,-,x)(SUBI,y,1,t2)(ASSIG,t2,-,y)(WHILE,-,-,-)(ADDI,x,y,t3)(GT,t3,0,t4)(DO,t4,-,-)(SUBI,x,1,t5)(ASSIG,t5,-,x)(ENDWHILE,-,-,-)(ASSIG,0,-,z)B1B2B3B4B5B6B7B8基本塊劃分的例子程序流圖程序流圖是以基本塊為節(jié)點的有向圖。B2B5B3B4B1B6B7B8常表達式節(jié)省常表達式：在編譯過程中能夠計算出常量值的表達式處理思想：針對每個基本塊，如果一個多元式的兩個分量的值已知，則計算其值，并刪掉相應(yīng)的中間代碼。常表達式節(jié)省例:假設(shè)有下列語句：a:=m+10;b:=a+m;c:=a+b–d;并假設(shè)當執(zhí)行第一個語句時，m總是取常數(shù)10，則上列語句可優(yōu)化如下：a:=20;b:=30;c:=50–d;常表達式節(jié)省原理：常量定值表ConstDef：(Var,Val)?；緣K入口置ConstDef為空；對當前四元式的分量利用ConstDef表進行值代換；新多四式形如（，A,B,t）:如果A和B是常數(shù)，則計算AB的值v，并將（t,v）填入ConsDef表，并刪除該多元式

形如（ASSIG，A,B）:如果A是常數(shù)，則把（B,A）填入ConsDef表，若已有B項，只需修改其值；否則從ConsDef中刪除B的登記項。

常表達式局部優(yōu)化的例子源程序中間代碼ConstDef優(yōu)化后的代碼a:=1(ASSIGN,1,a)(a,1)(ASSIGN,1,a)b:=a+1(ADDI,a,1,t1)(a,1)(t1,2)

（)

(ASSIGN,t1,b)(a,1)(t1,2)(b,2)(ASSIGN,2,b)a:=x(ASSIGN,x,a)(t1,2)(b,2)(ASSIGN,a,x)c:=b+5(ADDI,b,5,t2)(t1,2)(b,2)(t2,7)(