編譯程序原理與實現(xiàn)：第8章 中間代碼優(yōu)化

1、第八章 中間代碼優(yōu)化 8.1 中間代碼優(yōu)化概述 8.2 基本塊劃分 8.3 常量表達(dá)式局部優(yōu)化 8.4 公共表達(dá)式局部優(yōu)化 8.5 循環(huán)不變式外提 8.6 其他各類優(yōu)化介紹8.1 中間代碼優(yōu)化概述為什么在中間代碼上進行優(yōu)化？有些優(yōu)化只在中間代碼一級進行優(yōu)化的目標(biāo)最小的代價，提高目標(biāo)程序運行速度是否優(yōu)化，優(yōu)化到何種程度取決于編譯器設(shè)計者中間代碼優(yōu)化的分類按照優(yōu)化范圍：分為局部優(yōu)化和非局部優(yōu)化(循環(huán)優(yōu)化和全局優(yōu)化)按照優(yōu)化方法：分為常量表達(dá)式優(yōu)化，公共子表達(dá)式優(yōu)化，循環(huán)不變量外提優(yōu)化8.1 中間代碼優(yōu)化概述常量表達(dá)式優(yōu)化(合并常數(shù))v = a*b+c, 若a = 2, b=3, c=5 則可用v

2、= 11替換u = v +3; u替換成14公共子表達(dá)式節(jié)省(消除重復(fù)操作)t = b*c; e = b*c+b*c; c=b*c+10; d = b*c+d;t = b*c; e = t+t; c=b*c+10;d = b*c+d;循環(huán)不變量外提while (k10) ak = b*c; k=k+1t = b*c; while(k0 do x=x-1; z=0;(ASSIG,1,-,y)(LABEL,-,-,L)(AND,A,B,t)(THEN,t,-,-)(ASSIG,0,-,x)(ELSE,-,-,-)(ASSIG,0,-,y)(ENDIF,-,-,-)(ADDI,x,1,t1)(ASS

3、IG,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)(ASSIG,1,-,y)(LABEL,-,-,L)(AND,A,B,t)(THEN,t,-,-)(ASSIG,0,-,x)(ELSE,-,-,-)(ASSIG,0,-,y)(ENDIF,-,-,-)(ADDI,x,1,t1)(ASSIG,t1,-,x)(SUBI,y,1,t2)(ASSIG,t2,-,y)(WHI

4、LE,-,-,-)(ADDI,x,y,t3)(GT,t3,0,t4)(DO,t4,-,-)(SUBI,x,1,t5)(ASSIG,t5,-,x)(ENDWHILE,-,-,-)(ASSIG,0,-,z)B1B2B3B4B5B6B7B8程序流圖：以基本塊為結(jié)點的有向圖在一個基本塊上進行的優(yōu)化稱為局部優(yōu)化在多個基本塊上進行的優(yōu)化稱為非局部優(yōu)化循環(huán)優(yōu)化(多個基本塊)全局優(yōu)化(整個程序流圖)B2B5B3B4B1B6B7B88.3 常量表達(dá)式的局部優(yōu)化常量表達(dá)式：任何時候都取固定常數(shù)值的表達(dá)式優(yōu)化方法：用常量值替換原來的運算i = 30; j = 2*i; k = i*j; 可用 k=1800代替 優(yōu)化

5、的關(guān)鍵：知道哪些量取常數(shù)值方法：建立常量定義表ConDef (id, value)優(yōu)化算法：在入口處，ConDef為空；讀取一個四元式tuple,對tuple中的分量進行值替換得newtuple;若newtuple是(,A,B,t)情形：且A,B都是常數(shù)值，則計算A B的值v，并在ConDef中填入(t,v),同時刪除四元式(,A,B,t)；若newtuple是(ASSIG,A,-,B)情形：若A是常數(shù)，則把(B,A)填入ConDef中(若已有B的表項，則只需修改B的值)；否則，從ConDef中刪除B的表項。重復(fù)2-4直到基本塊結(jié)束x = 10y = x+1;x=a;z=y+5;(ASSIG,

6、10,-x)(ADDI,x,1,t1) (ASSIG,t1,-,y)(ASSIG,a,-,x)(ADDI,y,5,t2)(ASSIG,t2,-,z)ConDefx10t111y11t216z1611168.4 公共表達(dá)式的局部優(yōu)化等價四元式: 兩個運算型四元式(1,A1,B1,t1)和(2,A2,B2,t2)，若1= 2, A1和A2的值相同，B1和B2的值相同，則稱這兩個四元式等價公共表達(dá)式節(jié)省：當(dāng)一個基本塊中出現(xiàn)多個等價四元式時，除第一個四元式以外，其他的均可節(jié)省。關(guān)鍵：判斷四元式等價方法：建立可用表達(dá)式表UsableExpr 建立值編碼表ValuNum (id, Vno) 建立臨時變量等

7、價表PAIR: (ti,tj)在基本塊入口處，置ValuNum, UsableExpr,PAIR為空逐條掃描基本塊的中間代碼。對當(dāng)前四元式tuple中運算分量進行等價替換(用PAIR替換)，設(shè)所得代碼為newtuple.如果newtuple是dj : (,A,B,tj)，進行如下操作：若A是首次出現(xiàn)，則把(A,NewVN)填入ValuNum;若B是首次出現(xiàn)，則把(B,NewVN)填入ValuNum;若存在di : (,A,B,ti)UsableExpr,使得dj代碼是di代碼的公共表達(dá)式，則刪除tuple,將(ti,tj)填入PAIR，同時(tj) = (ti);否則，把(tj, NewVN)

8、填入ValuNum中，把dj加到UsableExpr中；如果newtuple是dj: (ASSIG,A,-,B)，進行如下操作：從UsableExpr中刪除含B的所有可用表達(dá)式代碼；若A是首次出現(xiàn)，則把(A,NewVN)填入ValuNum；令 (B) = (A);1. (*,b,c,t1)2. (*,b,c,t2)3. (+,t1,t2,t3)4. (:=,t3,-,a)5. (:=,b,-,d)6. (*,d,c,t4)7. (*,b,c,t5)8. (+t4,t5,t6)9. (:=,t6,-,e)ValuNumUsableExprPAIR(b,1)(c,2)(t1,3)1(t2,t1)(

9、t2,3)(t3,4)3(a,4)(d,1)(t4,3)(t4,t1)(t5,3)(t5,t1)(t6,4)(t6,t3)(e,4)t1t1t1t38.5 循環(huán)不變式外提優(yōu)化思想: 將值在循環(huán)里不發(fā)生改變的表達(dá)式運算提到循環(huán)外面進行i =1; while i1000 do ai = x*y;i =1; t = x*y; while i1000 do ai = t;關(guān)鍵： 識別循環(huán)結(jié)構(gòu)(循環(huán)入口，循環(huán)體，循環(huán)出口) 判斷循環(huán)不變式 判斷循環(huán)不變量方法：識別循環(huán)：(WHILE,-,-,-) 入口 (DO,e.form,-,-) 循環(huán)體開始 (ENDWHILE,-,-,-) 出口識別循環(huán)不變量：建立

10、循環(huán)定義表LoopDef8.5 循環(huán)不變式外提優(yōu)化外提對象: 除法運算不外提while e do if y=0 then x=y; else x=a/y; 賦值不外提: (賦值操作的左部和右部都是循環(huán)不變式)外提策略：凡是循環(huán)不變式都外提只外提一定被執(zhí)行的循環(huán)不變式8.5 循環(huán)不變式外提優(yōu)化生成中間代碼過程中構(gòu)造本層循環(huán)的LoopDef;當(dāng)結(jié)束一層循環(huán)的中間代碼時，做如下操作：掃描本層循環(huán)的一個中間代碼，設(shè)(,A,B,t)若不是可外提操作碼，則轉(zhuǎn)1掃描下一代碼；若是外提操作碼，則檢查A,B是否屬于本層LoopDef，若都不屬于，則轉(zhuǎn)4，否則轉(zhuǎn)1；若A和B都是本層循環(huán)不變量，則作：將(,A,B,

11、t)外提到本層循環(huán)入口處；把t從本層LoopDef移到外層LoopDef.刪除原(,A,B,t)。重復(fù)1-4直到本層循環(huán)結(jié)束。i =1;while i=100 dobegin z=i*k*5;a = 2*k+2*k*2;i=i+1;end(ASSIG,1,-, i)(WHILE,-,-,-)(LE,i,100,t1)(DO,t1,-,-)(MULTI,i,k,t2)(MULTI,t2,5,t3)(ASSIG,t3,-,z)(MULTI,2,k,t4)(MULTI,t4,2,t5)(ADDI,t4,t5,t6)(ASSIG,t6,-,a)(ADDI,i,1,t7)(ASSIG,t7,-,i)(E

12、NDWHILE,-,-,-)(ASSIG,1,-i)(WHILE,-,-,-)(LE,i,100,t1)(DO,t1,-,-)(MULTI,i,k,t2)(MULTI,t2,5,t3)(ASSIG,t3,-,z)(ASSIG,t6,-,a)(ADDI,i,1,t7)(ASSIG,t7,-,i)(ENDWHILE,-,-,-)1j-1jt1t2t3zt4t5t6at7iLoofDefi(ASSIG,1,-i)(MULTI,2,k,t4)(MULTI,t4,2,t5)(ADDI,t4,t5,t6)(WHILE,-,-,-)(LE,i,100,t1)(DO,t1,-,-)(MULTI,i,k,t2)

13、(MULTI,t2,5,t3)(ASSIG,t3,-,z)(ASSIG,t6,-,a)(ADDI,i,1,t7)(ASSIG,t7,-,i)(ENDWHILE,-,-,-)循環(huán)不變式外提應(yīng)從最內(nèi)層循環(huán)開始！(MULTI,2,k,t4)(MULTI,t4,2,t5)(ADDI,t4,t5,t6)8.6 其他各類優(yōu)化介紹消減運算強度：用強度低的運算代替強度高的運算for j=1 to 100 do aj = j*3+10m=13;for j=1 to 100 do begin aj=m; m=m+3 end8.6 其他各類優(yōu)化介紹復(fù)寫傳播：把a = b類型賦值語句去掉a = b; c=a+1; d=a+c; a=;c =b+1; d=b+c; a=;8.6 其他各類優(yōu)化介紹無用代碼消除：a = E, 在后面程序段中沒有對a的引用，可將該賦值語