編譯原理及實現(xiàn)技術(shù)課件：第八章 中間代碼優(yōu)化

1、第八章 中間代碼優(yōu)化 引言 常量表達式優(yōu)化 公共表達式優(yōu)化 循環(huán)不變式外提 優(yōu)化的目標：提高程序運行速度 優(yōu)化的要求：正確性、效果、適度 優(yōu)化的對象：深層循環(huán)和下標變量地址的計算 優(yōu)化的種類： 常表達式優(yōu)化（合并常數(shù)項） 公共表達式優(yōu)化（消除重復(fù)操作） 循環(huán)不變表達式外提 削減運算強度等等 優(yōu)化方法： 全局優(yōu)化：全局信息 局部優(yōu)化：局部信息基本塊和程序流圖 基本塊：單入口單出口的程序段。 程序流圖：以基本塊為結(jié)點的有向圖，有向邊表示 程序執(zhí)行的流程。 中間代碼基本塊的劃分：初始代碼為第一個基本塊的入口遇轉(zhuǎn)移性中間代碼時，結(jié)束當前基本塊，下一條代碼作為新基本塊的入口遇標號性代碼結(jié)束當前基本塊，代

2、碼本身作為新基本塊的入口。遇（ASSIG, A, X）時，如果X為引用型形參時結(jié)束當前塊，并作為該塊的出口?；緣K劃分的例子y:=1;L:if A and B then x:=0 else y:=0;x:=x+1;y:=y-1;while x+y0 do x:=x-1;z:=0; 基本塊劃分的例子B1:(ASSIG ,1,_,y)B2:(LABEL,L) (AND, A, B, t) (THEN,t,_,_)B3:(ASSIG,0,_,x) (ELSE,_,_,_)B4:(ASSIG,0,_,y) (ENDIF,_,_,_)B5:(ADDI,x,1,t1) (ASSIG,t1,_,x) (SU

3、BI,y,1,t2) (ASSIG,t2,_,y) B1B2 B4B3B5B6B8B7 程序流圖例B6:(WHILE,_,_,) (ADDI,x,y,t3) (GT,t3,0,t4) (DO,t4,_,_)B7:(SUBI,x,1,t5) (ASSIG,t5,_,x) (ENDWHILE,_,_,_)B8:(ASSIG,0,_,z) 常表達式局部優(yōu)化常表達式：任何時候都取固定常數(shù)值的表達式處理思想：針對每個基本塊，如果一個多元式的兩個分量的值已知，則計算其值，并刪掉相應(yīng)的中間代碼。原理：常量定值表ConsDef：(Var,Val)。基本塊入口置ConstDef為空；對當前多元式的分量利用Con

4、stDef表進行值代換；新多元式形如（,A,B,t）:如果A和B是常數(shù)，則計算AB的值v，并將（t,v）填入ConsDef表。并刪除該多元式形如（ASSIG,A,-,B）:若A是常數(shù)，則把（B,A）填入ConsDef表（對于表中原有的B對應(yīng)的項，只需修改其值）；否則從ConsDef中刪除B的登記項。 常表達式局部優(yōu)化的例子源程序 中間代碼 ConstDef 優(yōu)化后的代碼a:=1 (ASSIG,1,a) (a,1 ) (ASSIG,1,a)b:=a+1 (ADDI,a,1,t1)(a,1)(t1,2) 空 (ASSIG,t1,b) (a,1)(t1,2)(b,2) (ASSIG,2,b)a:=x

5、 (ASSIG,x,a) (t1,2)(b,2) (ASSIG,x,a)c:=b+5 (ADDI,b,5,t2)(t1,2)(b,2)(t2,7) 空 (ASSIG,t2,c) (t1,2)(b,2)(t2,7)(c,7) (ASSIG,7,c) 基于值編碼的公共表達式局部優(yōu)化按值等價原理優(yōu)化思想：對一個多元式的分量分別編碼，具有相同編碼的分量等價。值編碼表ValuNum，變量（常量）及其值編碼?？捎帽磉_式代碼表UsableExpr，基本塊中間代碼地址。臨時變量等價表TempEqua（PAIR），等價的臨時變量偶對?；谥稻幋a的公共表達式節(jié)省優(yōu)化算法基本塊入口處初始化：置空表。對塊中多元式用T

6、empEqua等價替換生成新多元式。如果多元式的A和B分量未編碼，則編新碼；如果多元式形如dk:(,A,B,tk)且存在di:(,A,B,ti) UsableExpr中使得dk是di的公共表達式，則刪掉dk，將(tk,ti)填入TempEqua表；否則，為tk編碼；把dk加入到UsableExpr表；如果多元式形如dk:(ASSIG,A,-,B)則令B的值編碼等于A的值編碼，填入ValuNum表中；從UsableExpr刪除所有含B的中間代碼。基于值編碼的優(yōu)化實例A:=B*C+B*CD:=BE:=D*C+B*C循環(huán)不變式外提優(yōu)化循環(huán)的識別：入口、重復(fù)體以及出口的識別。識別方法：基于程序文本，基

7、于程序圖。外提對象：循環(huán)不變式安全性: 除法表達式不能外提(除零溢出)賦值表達式不能外提(不一定執(zhí)行該循環(huán)）外提原理：變量信息表LoopDef是在循環(huán)體內(nèi)被定義的變量集合;對每層循環(huán)記錄LoopDef;若循環(huán)體內(nèi)的多元式(,A,B,t)中的A,B不在本層的LoopDef中,則把(,A,B,t)外提到循環(huán)體的入口處。循環(huán)優(yōu)化實例i=1;while(i=100)z=i*k*5;a=2*k+2*k*2;i=i+1;外提實例FOR i :=0 TO 9 DO FOR j :=0 TO 9 DOFOR k:=0 TO 9 DO Aijk:=(ij)k 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 ,10, t3 ) ( , t2, t3, t4 ) ( , i , j, t6 ) ( , t4, k , t5 ) ( , t6,k, t7 ) ( , t7, t5 ) (