第八章中間代碼優(yōu)化

1、Z 引言引言Z 常量表達式優(yōu)化常量表達式優(yōu)化Z 公共表達式優(yōu)化公共表達式優(yōu)化Z 循環(huán)不變式外提循環(huán)不變式外提 優(yōu)化的目標：優(yōu)化的目標： 優(yōu)化的要求：優(yōu)化的要求： 優(yōu)化的對象：優(yōu)化的對象：深層循環(huán)和下標變量地址的計算深層循環(huán)和下標變量地址的計算 優(yōu)化的種類：優(yōu)化的種類： 常表達式優(yōu)化（合并常數項）常表達式優(yōu)化（合并常數項） 公共表達式優(yōu)化（消除重復操作）公共表達式優(yōu)化（消除重復操作） 循環(huán)不變表達式外提循環(huán)不變表達式外提 削減運算強度等等削減運算強度等等 優(yōu)化方法：優(yōu)化方法： 全局優(yōu)化：全局信息全局優(yōu)化：全局信息 局部優(yōu)化：局部信息局部優(yōu)化：局部信息 基本塊：基本塊：單入口單出口的程序段。單入口

2、單出口的程序段。 程序流圖：程序流圖：以基本塊為結點的有向圖，有向邊表示以基本塊為結點的有向圖，有向邊表示 程序執(zhí)行的流程。程序執(zhí)行的流程。 中間代碼基本塊的劃分：中間代碼基本塊的劃分： 初始代碼為第一個基本塊的入口。初始代碼為第一個基本塊的入口。 遇轉移性中間代碼時，結束當前基本塊，下一條遇轉移性中間代碼時，結束當前基本塊，下一條 代碼作為新基本塊的入口。代碼作為新基本塊的入口。 遇標號性代碼結束當前基本塊，代碼本身作為新遇標號性代碼結束當前基本塊，代碼本身作為新 基本塊的入口?；緣K的入口。 遇（遇（ASSIG, A, XASSIG, A, X）時，如果時，如果X X為引用型形參時結為引用

3、型形參時結 束當前塊，并作為該塊的出口。束當前塊，并作為該塊的出口。y := 1 ;L: if A and B then x := 0 else y := 0 ;x := x + 1 ;y := y 1 ;while x + y 0 do x := x - 1 ;z := 0 ; B1B1:(ASSIG ,1,_,y):(ASSIG ,1,_,y)B2B2:(LABEL,L):(LABEL,L) (AND, A, B, t) (AND, A, B, t) (THEN,t,_,_)(THEN,t,_,_)B3:(ASSIG,0,_,x)B3:(ASSIG,0,_,x) (ELSE,_,_,_)(

4、ELSE,_,_,_)B4:(ASSIG,0,_,y)B4:(ASSIG,0,_,y) (ENDIF,_,_,_)(ENDIF,_,_,_)B5:(ADDI,x,1,t1)B5:(ADDI,x,1,t1) (ASSIG,t1,_,x) (ASSIG,t1,_,x) (SUBI,y,1,t2) (SUBI,y,1,t2) (ASSIG,t2,_,y) (ASSIG,t2,_,y) B B1 1B B2 2 B B4 4B B3 3B B5 5B B6 6B B8 8B B7 7 程序流圖例程序流圖例B6B6:(WHILE,_,_,):(WHILE,_,_,) (ADDI,x,y,t3) (ADD

5、I,x,y,t3) (GT,t3,0,t4) (GT,t3,0,t4) (DO,t4,_,_)(DO,t4,_,_)B7:(SUBI,x,1,t5)B7:(SUBI,x,1,t5) (ASSIG,t5,_,x) (ASSIG,t5,_,x) (ENDWHILE,_,_,_)(ENDWHILE,_,_,_)B8:(ASSIG,0,_,z) B8:(ASSIG,0,_,z) 常表達式常表達式：任何時候都取固定常數值的表達式：任何時候都取固定常數值的表達式 處理思想：處理思想：針對每個基本塊，如果一個多元式的兩針對每個基本塊，如果一個多元式的兩 個分量的值已知，則計算其值，并刪掉個分量的值已知，則計

6、算其值，并刪掉 相應的中間代碼。相應的中間代碼。 原理：原理：常量定值表常量定值表ConsDefConsDef：( (Var,Val)Var,Val)。 基本塊入口置基本塊入口置ConstDefConstDef為空；為空； 對當前多元式的分量利用對當前多元式的分量利用ConstDefConstDef表進行值代換；表進行值代換； 新多元式新多元式形如（形如（ ，A, B,tA, B,t）: :如果如果A A和和B B是常數，是常數， 則計算則計算A A B B的值的值v v，并將（并將（t,vt,v）填入填入ConsDefConsDef表。并表。并 刪除該多元式；刪除該多元式； 形如（形如（AS

7、SIGASSIG，A, BA, B）: :如果如果A A是常數，則把（是常數，則把（B,AB,A） 填入填入ConsDefConsDef表，若已有表，若已有B B項，只需修改其值；項，只需修改其值； 否則從否則從ConsDefConsDef中刪除中刪除B B的登記項。的登記項。 源程序源程序 中間代碼中間代碼 ConstDef ConstDef 優(yōu)化后的代碼優(yōu)化后的代碼a:=1a:=1 (ASSIGN, 1,a) (ASSIGN, 1,a) (a,1 )(a,1 ) (ASSIGN,1,a) (ASSIGN,1,a)b:=a+1b:=a+1 (ADDI,a,1,t1) (ADDI,a,1,t1

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

9、(ASSIGN,t2,c) (t1,2)(b,2) (t2,7)(c,7)(t1,2)(b,2) (t2,7)(c,7) (ASSIGN,7,c) (ASSIGN,7,c) | 按值等價原理按值等價原理| 優(yōu)化思想優(yōu)化思想 對一個多元式的分量分別編碼，具對一個多元式的分量分別編碼，具 有相同編碼的分量等價。有相同編碼的分量等價。| 值編碼表值編碼表ValuNnmValuNnm| 可用表達式代碼表可用表達式代碼表UsableExprUsableExpr| 臨時變量等價表臨時變量等價表TempEquaTempEqua|入口處初始化：入口處初始化：ValueNum,UsableExpValueNum

10、,UsableExp和和TempEquaTempEqua為空。為空。|對當前多元式用對當前多元式用TempEquaTempEqua等價替換，生成等價替換，生成NewTupleNewTuple。|如果如果NewTupleNewTuple的的A A和和B B分量是未編碼的，則編新碼；分量是未編碼的，則編新碼；|如果多元式形如：如果多元式形如： dk:( dk:( , A, A , B, B , tk ), tk )若存在若存在didi UsableExprUsableExpr使得使得dkdk是是 di di的的ECCECC，則刪掉則刪掉dkdk，將將( (tk,ttk,ti i) )填入填入Tem

11、pEquaTempEqua表；表； 否則，為否則，為tktk編碼；把編碼；把dkdk加入到加入到UsableExprUsableExpr表；表； dk:(ASSIG, A dk:(ASSIG, A , B, B ) )則令則令B B 的值編碼等于的值編碼等于A A 的值編碼，的值編碼，填入填入ValuNumValuNum表中；表中；從從UsableExprUsableExpr刪除所有含刪除所有含B B的的 中間代碼。中間代碼。A:=B*C+B*CD:=BE:=D*C+B*C 循環(huán)的識別：循環(huán)的識別：識別循環(huán)的入口、重復體、出口部分。識別循環(huán)的入口、重復體、出口部分。 識別方法：識別方法：基于程

12、序文本，基于程序圖?；诔绦蛭谋?，基于程序圖。 外提對象：外提對象：循環(huán)不變式。循環(huán)不變式。 安全性安全性: : 除法表達式不能外提除法表達式不能外提( (除零溢出除零溢出) )； 賦值表達式不能外提賦值表達式不能外提( (不一定執(zhí)行該循環(huán)）。不一定執(zhí)行該循環(huán)）。 外提原理：外提原理： 定義定義LoopDefLoopDef是在循環(huán)體內被定義的變量集合是在循環(huán)體內被定義的變量集合; ; 對每層循環(huán)記錄對每層循環(huán)記錄LoopDef;LoopDef; 若循環(huán)體內的多元式若循環(huán)體內的多元式( ( , ,A,B,tA,B,t) )中的中的A,BA,B不在本不在本 層的層的LoopDefLoopDef中中

13、, ,則把則把( ( , ,A,B,t)A,B,t)外提到循環(huán)體外提到循環(huán)體 的入口處。的入口處。i:=1while i=100 dobegin z:=i*k*5 a:=2*k+2*k*2 i:=i+1;end FOR i :=0 TO 9 DOFOR i :=0 TO 9 DO FOR j :=0 TO 9 DOFOR j :=0 TO 9 DOFOR k:=0 TO 9 DO FOR k:=0 TO 9 DO Aijk:=(i Aijk:=(i j)j) k k ENDFORENDFOR ENDFOR ENDFOR ENDFOR ENDFOR ( , i ,100, t1 ) ( , A,t1, t2 ) ( , j ,10, t3 ) ( , t2, t3, t4 ) ( , t4, k , t5 ) ( , i , j, t6 ) ( , t6,k, t7 ) ( , t7, t5 ) ( , i ,100, t1 ) ( , A,t1, t2 ) ( , j ,