第12章 代碼優(yōu)化及目標(biāo)代碼生成

1、第12章 代碼優(yōu)化和目標(biāo)代碼生成第一節(jié) 代碼優(yōu)化一. 優(yōu)化的概念1. 優(yōu)化是一種等價(jià)的，有效的程序變換。n等價(jià) 不改變程序運(yùn)行結(jié)果n有效 時(shí)空效率要高2. 不同階段的優(yōu)化n源程序階段的優(yōu)化：考慮數(shù)據(jù)結(jié)構(gòu)和算法n編譯階段的優(yōu)化：中間代碼優(yōu)化和目標(biāo)代碼優(yōu)化3. 中間代碼的優(yōu)化n局部?jī)?yōu)化：在基本塊內(nèi)的優(yōu)化n全局優(yōu)化：在基本塊之間的優(yōu)化二. 基本塊基本塊的定義程序中的一段語(yǔ)句序列，它只有一個(gè)入口語(yǔ)句，即該語(yǔ)句序列的第一個(gè)語(yǔ)句；只有一個(gè)出口語(yǔ)句，即該語(yǔ)句序列的最后一個(gè)語(yǔ)句。劃分基本塊1. 入口語(yǔ)句(1) 程序的第一條語(yǔ)句(2) 能由轉(zhuǎn)向語(yǔ)句（條件或無(wú)條件）轉(zhuǎn)移到的語(yǔ)句(3) 緊跟在條件語(yǔ)句后的語(yǔ)句2.

2、出口語(yǔ)句(1) 轉(zhuǎn)向語(yǔ)句(2) 停止語(yǔ)句劃分基本塊3. 劃分基本塊的算法(1) 求出三地址碼程序中的所有入口語(yǔ)句和出口語(yǔ)句(2) 劃分基本塊：入口語(yǔ)句入口語(yǔ)句 入口語(yǔ)句出口語(yǔ)句(3) 刪除未被劃入基本塊的語(yǔ)句(1) i:=m-1(2) j:=n(3) t1:=4*n(4) v:=at1(5) i:=i+1(6) t2:=4*i(7) t3:=at2(8) if t3v goto (9)(13) if i=j goto (23)(14) t6:=4*i(15) x:=at6(16) t7:=4*i(17) t8:=4*j(18) t9:=at8(19) at7:=t9(20) t10:=4*j(

3、21) at10:=x(22) goto (5)(23) t11:=4*i(24) x:=at11(25) t12:=4*i(26) t13:=4*n(27) t14:=at13(28) at12:=t14(29) t15:=4*n(30) at15:=xB1B2B3B4B5B6三. 程序流圖程序流圖是程序結(jié)構(gòu)的圖形表示。程序流圖可定義為G = ( N , E , n0)，其中：(1) N為結(jié)點(diǎn)的集合，每個(gè)結(jié)點(diǎn)代表一個(gè)基本塊(2) 含程序第一條語(yǔ)句的基本塊為首結(jié)點(diǎn)n0(3) E為有向邊的集合，基本塊Bi與Bj之間有一條有向邊的條件是：Bj 緊跟在 Bi 之后，且 Bi 的出口語(yǔ)句不是無(wú)條件轉(zhuǎn)向

4、或停止語(yǔ)句。Bi 的出口語(yǔ)句為轉(zhuǎn)向語(yǔ)句，其轉(zhuǎn)向點(diǎn)恰為 Bj 的入口語(yǔ)句。(1)i:=m-1 (2)j:=n(3)t1:=4*n (4)v:=at1(5)i:=i+1 (6)t2:=4*i(7)t3:=at2 (8)if t3v goto(9)(13)if i=j goto(23)(14)t6:=4*i (15)x:=at6(16)t7:=4*i (17)t8:=4*j(18)t9:=at8 (19)at7:=t9(20)t10:=4*j (21)at10:=x(22)goto (5)(23)t11:=4*i (24)x:=at11(25)t12:=4*i (26)t13:=4*n(27)t14

5、:=at13 (28)at12:=t14(29)t15:=4*n (30)at15:=xB1B2B3B4B5 B6四. 局部?jī)?yōu)化局部?jī)?yōu)化就是基本塊內(nèi)的優(yōu)化。局部?jī)?yōu)化包括以下幾種方法：1. 合并已知量2. 刪除公共子表達(dá)式3. 刪除無(wú)用賦值4. 刪除死代碼1. 合并已知量對(duì)于語(yǔ)句：A := OP B 或 A := B OP C若B和C為常數(shù)，則編譯時(shí)可將A的值計(jì)算出來(lái)，存放在臨時(shí)單元T中，相應(yīng)語(yǔ)句換成：A := T2. 刪除公共子表達(dá)式對(duì)于語(yǔ)句：A := B + C*DU := V C*D如果兩個(gè)語(yǔ)句之間C和D的值未改變，則第二個(gè)語(yǔ)句可使用第一個(gè)語(yǔ)句的計(jì)算結(jié)果T：A := B + C*DU :=

6、 V T3. 刪除無(wú)用賦值如有語(yǔ)句：A := B + CA := M + N在兩個(gè)語(yǔ)句之間沒(méi)有使用過(guò)A，則第一個(gè)語(yǔ)句可以刪除：A := M + N4. 刪除死代碼語(yǔ)句：if B then S1 else S2如果B的值固定為“真”或“假”，則其中一個(gè)分支永遠(yuǎn)不會(huì)執(zhí)行，這些分支的代碼時(shí)“死代碼”，可以刪除。例題：(1) F:=1(2) C:=F+E(3) D:=F+3(4) B:=A*A(5) G:=B-D(6) H:=E(7) I:=H*G(8) J:=D/4(9) K:=J+C(10) L:=H(11) L:=I-J第一步：合并已知量，由(1) F:=1，可得：(1) F:=1(2) C:=

7、1+E(3) D:=4(4) B:=A*A(5) G:=B-4(6) H:=E(7) I:=H*G(8) J:=1(9) K:=2+E(10) L:=H(11) L:=I-1第二步：刪除公共子表達(dá)式，由(6)將(7)改為：(1) F:=1(2) C:=1+E(3) D:=4(4) B:=A*A(5) G:=B-4(6) H:=E(7) I:=E*G(8) J:=1(9) K:=2+E(10) L:=H(11) L:=I-1第三步：刪除無(wú)用賦值 (10)；其它可能的無(wú)用賦值 (1)、(2)、(3)、(6)、(8)。(4) B:=A*A(5) G:=B-4 (7) I:=E*G(9) K:=2+E

8、(11) L:=I-1五. 全局優(yōu)化循環(huán)優(yōu)化是一種重要的全局優(yōu)化方法（全局優(yōu)化的方法有多種，本節(jié)只討論循環(huán)優(yōu)化）。循環(huán)是程序中重復(fù)執(zhí)行的代碼序列，一個(gè)程序運(yùn)行的大部分時(shí)間是用在循環(huán)上的，因此循環(huán)優(yōu)化對(duì)提高程序的執(zhí)行效率具有非常重要的意義。循環(huán)的定義循環(huán)的定義：循環(huán)是程序流圖中有唯一入口結(jié)點(diǎn)的強(qiáng)連通子圖。入口結(jié)點(diǎn)：子圖中滿足下列條件之一的結(jié)點(diǎn)n：1. n是流圖的首結(jié)點(diǎn); 2. 在子圖外有一結(jié)點(diǎn)m, 它有一有向邊mn引向結(jié)點(diǎn)n。強(qiáng)連通子圖：其中的任意兩個(gè)結(jié)點(diǎn)均可互相連通的子圖。1 12 24 43 35 56 69 910107 78 8例5,6,7,8,95,6,7,8,9是循環(huán)是循環(huán)4,4,

9、,不是循環(huán)不是循環(huán)兩個(gè)入口結(jié)點(diǎn)；兩個(gè)入口結(jié)點(diǎn)；不是強(qiáng)連通子圖，不存在不是強(qiáng)連通子圖，不存在4 4到到2 2的通路；的通路；兩個(gè)問(wèn)題1. 如何定位程序中的循環(huán)？2. 如何對(duì)循環(huán)進(jìn)行優(yōu)化？必經(jīng)結(jié)點(diǎn)集：從程序流圖的首結(jié)點(diǎn)出發(fā)到達(dá)結(jié)點(diǎn)n的任一通路都必須經(jīng)過(guò)的結(jié)點(diǎn)d, 稱為n的必經(jīng)結(jié)點(diǎn)，記為d DOM n：程序流圖中結(jié)點(diǎn)n的所有必經(jīng)結(jié)點(diǎn)的集合，稱為n的必經(jīng)結(jié)點(diǎn)集，記為D(n)必經(jīng)結(jié)點(diǎn)具有如下性質(zhì)：即對(duì)任意結(jié)點(diǎn)n，有n DOM n;：若n1 DOM n2, n2 DOM n3，則n1 DOM n3;：若n1 DOM n2, n2 DOM n1，則n1=n2；例 D(1)=1 D(2)=1,2 D(3)=1

10、,2,3 D(4)=1,2,4 D(5)=1,2,4,5 D(6)=1,2,4,5,6 D(7)=1,2,4,5,6,7 D(8)=1,2,4,5,6,8 D(9)=1,2,4,5,6,9 D(10)=1,2,4,10回邊回邊：流圖G=(N,E,n0)中的有向邊nd，如果d是n的必經(jīng)結(jié)點(diǎn), 即dD(n),則稱nd為流圖的一條回邊；1 12 24 43 35 56 69 910107 78 8例該流圖有三條回邊：該流圖有三條回邊：, ,因?yàn)橐驗(yàn)? 4 DOM(5)DOM(5)，因?yàn)?，因?yàn)? 5 DOM(9)DOM(9)，因?yàn)?，因?yàn)? 2 DOM(10)DOM(10)如何定位程序中的循環(huán)：若nd是

11、流圖G=(N,E,0)的一條回邊，M是流圖中有通路到達(dá)n而該通路不經(jīng)過(guò)d的結(jié)點(diǎn)集合，則集合 LOOP=n,dM組成了G的一個(gè)子圖，稱為由回邊nd組成的。1 12 24 43 35 56 69 910107 78 81 12 24 43 35 56 69 910107 78 8例該流圖有三條回邊：該流圖有三條回邊：構(gòu)成循環(huán)構(gòu)成循環(huán)5,4,6,7,8,95,4,6,7,8,9構(gòu)成循環(huán)構(gòu)成循環(huán)9,5,6,7,89,5,6,7,8構(gòu)成循環(huán)構(gòu)成循環(huán)10,2,3,4,5,6,7,8,910,2,3,4,5,6,7,8,91 12 24 43 35 56 69 910107 78 81 12 24 43 3

12、5 56 69 910107 78 8如何對(duì)循環(huán)進(jìn)行優(yōu)化循環(huán)優(yōu)化包括以下幾種方法：1. 代碼外提2. 強(qiáng)度削弱3. 刪除歸納變量對(duì)x:=op y或x:=y op z，如果y、z均為循環(huán)不變量（常數(shù)或定值點(diǎn)在L之外），則該運(yùn)算為循環(huán)不變運(yùn)算，優(yōu)化時(shí)將該運(yùn)算提到循環(huán)入口結(jié)點(diǎn)之前所增設(shè)的結(jié)點(diǎn)中去。1. 代碼外提基本歸納變量：i := i c （c為常數(shù)）同族歸納變量：j := c1*i c2 （c1、c2為常數(shù)）基本歸納變量i每循環(huán)一次增加或減少c，與i同族的歸納變量j相應(yīng)增加或減少c1*c。因此，計(jì)算j的乘法可由加法來(lái)代替： j := j + c1*c （c1*c為常數(shù)） 2. 強(qiáng)度削弱用同族歸納

13、變量作為判斷條件，如基本歸納別無(wú)它用，則可將其刪除。例如：j = 10 * i + 5，判斷條件為 i 10 ，則將 i 10 改為 j 105，同時(shí)刪除i相關(guān)的語(yǔ)句。 3. 刪除歸納變量全局優(yōu)化實(shí)例(1)i:=1(2)if i10 goto (16)(3)t1:=2*j (4)t2:=10*i(5)t3:=t2+t1 (6)t4:=a0-11(7)t5:=2*j (8)t6:=10*i(9)t7:=t6+t5 (10)t8:=a0-11 (11)t9:=t8t7 (12)t10:=t9+1(13)t4t3:=t10 (14)i:=i+1(15)goto (2)(16) .B1B2B3B41.

14、 代碼外提(3) (6)(7)(10)(1)i:=1(2)if i10 goto (16)(3)t1:=2*j (4)t2:=10*i(5)t3:=t2+t1 (6)t4:=a0-11(7)t5:=2*j (8)t6:=10*i(9)t7:=t6+t5 (10)t8:=a0-11 (11)t9:=t8t7 (12)t10:=t9+1(13)t4t3:=t10 (14)i:=i+1(15)goto (2)(16) .B1B2B3B42. 強(qiáng)度削弱(4)(5)(8)(9)(1)i:=1(4)t2:=10*i (5)t3:=t2+t1 (8)t6:=10*i (9)t7:=t6+t5(11)t9:=

15、t8t7 (12)t10:=t9+1(13)t4t3:=t10 (14)i:=i+1(15)goto (2)(16) .(2)if i10 goto (16)(3)t1:=2*j (6)t4:=a0-11(7)t5:=2*j (10)t8:=a0-11B1B2B2B3B43.刪除歸納變量(2)(14)(1)i:=1(4)t2:=t2+10 (5)t3:=t3+10(8)t6:=t6+10 (9)t7:=t7+10(11)t9:=t8t7 (12)t10:=t9+1(13)t4t3:=t10 (14)i:=i+1(15)goto (2)(16) .(2)if i10 goto (16)(3)t1

16、:=2*j (6)t4:=a0-11(7)t5:=2*j (10)t8:=a0-11(4)t2:=10*i (5)t3:=t2+t1 (8)t6:=10*i (9)t7:=t6+t5 B1B2B2B3B44.其它優(yōu)化(1)i:=1(4)t2:=t2+10 (5)t3:=t3+10 (8)t6:=t6+10 (9)t7:=t7+10(11)t9:=t8t7 (12)t10:=t9+1(13)t4t3:=t10 (15)goto (2)(16) .(2)if t3s goto (16)(3)t1:=2*j (6)t4:=a0-11(7)t5:=2*j (10)t8:=a0-11(4)t2:=10*

17、i (8)t6:=10*i(5)t3:=t2+t1 (9)t7:=t6+t5(2)s:=100+t1 B1B2B2B3B45. 其它優(yōu)化后(1)i:=1(5)t3:=t3+10 (9)t7:=t7+10(11)t9:=t8t7 (12)t10:=t9+1(13)t4t3:=t10 (15)goto (2)(16) .(2)if t3s goto (16)(3)t1:=2*j (6)t4:=a0-11(7)t5:=2*j (10)t8:=a0-11(4)t2:=10*i (8)t6:=10*i(5)t3:=t2+t1 (9)t7:=t6+t5(2)s:=100+t1 B1B2B2B3B42 23

18、 30 06 6優(yōu)化后優(yōu)化后2 26 64 41313優(yōu)化前優(yōu)化前變址加變址加加法數(shù)加法數(shù)乘法數(shù)乘法數(shù)語(yǔ)句數(shù)語(yǔ)句數(shù)B B優(yōu)化的效果習(xí)題1. 將列程序段劃分為基本塊，構(gòu)造其程序流圖，并進(jìn)行優(yōu)化。(1) C:=100(2) A:=0(3) B:=10(4) A:=A+B(5) If B=C then goto (8)(6) B:=B+10(7) goto (4)(8) write A第二節(jié) 目標(biāo)代碼生成1. 目標(biāo)代碼生成的任務(wù)將中間代碼翻譯成等價(jià)的目標(biāo)代碼。n輸入中間代碼、符號(hào)表n輸出目標(biāo)代碼：機(jī)器代碼、匯編碼目標(biāo)代碼生成的主要問(wèn)題n需要根據(jù)目標(biāo)機(jī)器的特性，選擇合適的指令，生成最短的目代代碼；n為

19、了提高目標(biāo)代碼的執(zhí)行效率，要充分利用目標(biāo)機(jī)器的寄存器；2. 一個(gè)計(jì)算機(jī)模型n 假定一個(gè)計(jì)算機(jī)的指令形式為：OP 目的操作數(shù) ， 源操作數(shù) 其中：操作數(shù)可以是內(nèi)存地址M、寄存器R或常數(shù)C。根據(jù)操作數(shù)的尋址方式，將指令劃分為：(1) 寄存器到內(nèi)存型MOV M , Ri /* (Ri) = M */(2) 內(nèi)存到寄存器型MOV Ri , M /* (M) = Ri */(3) 寄存器型OP Ri , Rj/* (Ri) OP (Rj) = Ri */(4) 直接地址型OP Ri , M/* (Ri) OP (M) = Ri */(5) 變址型OP Ri , C(Rj)/* (Ri) OP (Rj)

20、+ C) = Ri */(6) 間接型OP Ri , *Rj /* (Ri) OP (Rj) = Ri */OP Ri , *M /* (Ri) OP (M) = Ri */OP Ri , *C(Rj) /* (Ri) OP (Rj) + C) = Ri */(7) 轉(zhuǎn)移型JX /* goto X */JC X /* if C goto X */3. 目標(biāo)代碼生成方法(1) 三地址碼x = y OP z的翻譯翻譯成的目標(biāo)代碼為：MOV Ri , yOP Ri , zMOV x , Ri(2)三地址碼goto x的翻譯翻譯成的目標(biāo)代碼為：J X（其中，X是目標(biāo)代碼中與x對(duì)應(yīng)的位置。）(3)三地址

21、碼if c(x,y) goto x的翻譯翻譯成的目標(biāo)代碼為：XYJC X（其中，XY是目標(biāo)代碼中與x，y相關(guān)的指令，C是目標(biāo)代碼中與c對(duì)應(yīng)的條件，X是目標(biāo)代碼中與x對(duì)應(yīng)的位置。）例： x = y OP z翻譯為： MOV Ri , yOP Ri , z指令執(zhí)行完后，寄存器Ri被變量x占用（或稱為：將寄存器Ri分配給變量x）。將寄存器Ri分配給變量x時(shí)應(yīng)考慮以下幾點(diǎn)：4. 簡(jiǎn)單代碼的寄存器分配(1) 如y已占用某Ri，且y在以后不再被引用，則可將Ri分配給x，第1條指令可省略。(2) 如有空余寄存器Ri ，則將其分配給x。(3) 如寄存器均被占用，則從中選擇一個(gè)Ri （a.對(duì)應(yīng)的變量在內(nèi)存中已有

22、副本的;b.對(duì)應(yīng)的變量不再被引用的;c.對(duì)應(yīng)的變量在最遠(yuǎn)處才被引用的寄存器），先保存副本（將其值保存到內(nèi)存中），再將其分配給x 。實(shí)例翻譯以下三地址碼序列：t := a - bu := a + cv := a - tw := v + u（假設(shè)當(dāng)前可用寄存器為：R0、R1）MOV R0 , aSUBR0 , b /* R0: t */MOV R1 , aADDR1 , c /* R1: u */MOV u , R1MOV R1 , aSUBR1 , R0 /* R1: v */MOV v , R1ADDR1 , u /* R1: w */5. 循環(huán)中的的寄存器分配由于訪問(wèn)寄存器比訪問(wèn)內(nèi)存要快得多

23、，從全局來(lái)看，將一定數(shù)量的寄存器固定分配給循環(huán)中頻繁引用的變量，是提高運(yùn)行效率的一種策略。如何知道給哪些變量固定分配寄存器收效最大？指令的執(zhí)行代價(jià)指令的執(zhí)行代價(jià)：一條指令訪問(wèn)內(nèi)存的次數(shù)。寄存器型 op Ri, Rj 執(zhí)行代價(jià)為1直接地址型op Ri, M執(zhí)行代價(jià)為2變址型 op Ri, C(Rj) 執(zhí)行代價(jià)為2間接型 op Ri, *Rj 執(zhí)行代價(jià)為2 op Ri, *M 執(zhí)行代價(jià)為3 op Ri, *C(Rj) 執(zhí)行代價(jià)為3固定分配寄存器節(jié)省的代價(jià)計(jì)算(1) 如果變量固定占有寄存器，則它在定值（賦值）之前的每一次引用就少訪問(wèn)一次內(nèi)存，即節(jié)省一個(gè)執(zhí)行代價(jià)。設(shè)USE(x,B)為變量x在基本塊B中被定值前的引用次數(shù)，則循環(huán)L執(zhí)行一次，可省的執(zhí)行代價(jià)為： USE(x,B)(2) 對(duì)基本塊中被定值，在基本塊后活躍的變量x，如果對(duì)它固定分配寄存器，則可省去指令MOV Mx,Ri, 因此可節(jié)省執(zhí)行代價(jià)2。令LIVE(x,B)=1(否則LIVE(x,B)=0)表示變量x在基本塊