代碼優(yōu)化及目標(biāo)代碼生成(介紹)-編譯原理-09-(一)

1、2022-5-81第第9 9章章 代碼優(yōu)化與代碼優(yōu)化與目標(biāo)代碼生成（介紹）目標(biāo)代碼生成（介紹）n代碼優(yōu)化代碼優(yōu)化n代碼生成代碼生成2022-5-82引例引例for i=1 to n step m do si:=4*i+n*ma:=4*m; s1:=4+ n*m;for i=1 to n step m do si:=s1; s1:=s1+aa:=4*m;s1=4+n*m;for i=2 to n step m do si:=si-1+a;2022-5-83代碼優(yōu)化代碼優(yōu)化v代碼優(yōu)化的任務(wù)代碼優(yōu)化的任務(wù)通過(guò)等價(jià)的程序變換，獲得通過(guò)等價(jià)的程序變換，獲得執(zhí)行速度快、占執(zhí)行速度快、占用空間少用空間少的程

2、序的程序2022-5-84for i=2 to 10000 dofor i=2 to 10000 do T=0; T=0; for j=2 to i-1 do for j=2 to i-1 doif i=i/jif i=i/j* *j then T=1;breakj then T=1;break if T=0 then print (i) if T=0 then print (i)for i=2 to 10000 dofor i=2 to 10000 do T=0;T=0; for j=2 to i/2 do for j=2 to i/2 doif i=i/jif i=i/j* *j then

3、 T=1;breakj then T=1;break if T=0 then print (i) if T=0 then print (i)for i=2 to 10000 dofor i=2 to 10000 do T=0; T=0; for j=2 to sqrt(i) do for j=2 to sqrt(i) doif i=i/jif i=i/j* *j then T=1;breakj then T=1;break if T=0 then print (i) if T=0 then print (i)v算法優(yōu)化算法優(yōu)化例：順序查找例：順序查找與與hashhash算法算法有效的數(shù)據(jù)結(jié)有效

4、的數(shù)據(jù)結(jié)構(gòu)和算法構(gòu)和算法領(lǐng)域相關(guān)領(lǐng)域相關(guān)2022-5-85編譯原理編譯原理(Principles of Compiling)n主主 講：蔣宗禮講：蔣宗禮2022-5-86上次課主要內(nèi)容上次課主要內(nèi)容v關(guān)鍵字表關(guān)鍵字表關(guān)鍵字名字關(guān)鍵字名字關(guān)鍵字標(biāo)識(shí)關(guān)鍵字標(biāo)識(shí)beginbegin112112endend113113whilewhile114114名字名字信息信息1 1信息信息2 2信息信息n nsum1sum1real real 所在層所在層定義定義/ /引用引用2022-5-87上次課主要內(nèi)容上次課主要內(nèi)容v層次表層次表所在層所在層性質(zhì)性質(zhì)起點(diǎn)起點(diǎn)終點(diǎn)終點(diǎn)直接外層直接外層本層計(jì)數(shù)本層計(jì)數(shù)2022

5、-5-88上次課主要內(nèi)容上次課主要內(nèi)容v過(guò)程表過(guò)程表v變量表變量表v標(biāo)號(hào)表標(biāo)號(hào)表名字名字 種類(lèi)種類(lèi)類(lèi)型類(lèi)型 地址地址參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù)層次層次定義定義/引用引用名字名字種類(lèi)種類(lèi)類(lèi)型類(lèi)型長(zhǎng)度長(zhǎng)度地址地址標(biāo)志標(biāo)志2022-5-89上次課主要內(nèi)容上次課主要內(nèi)容通過(guò)等價(jià)變換，獲得執(zhí)行速度快、占用空間通過(guò)等價(jià)變換，獲得執(zhí)行速度快、占用空間少的程序少的程序2022-5-810v編譯優(yōu)化編譯優(yōu)化目標(biāo)代碼優(yōu)化：機(jī)器相關(guān)目標(biāo)代碼優(yōu)化：機(jī)器相關(guān)v特殊指令的利用特殊指令的利用v特殊結(jié)構(gòu)的高效利用：特殊結(jié)構(gòu)的高效利用：SIMDSIMD、MIDMMIDM、流水、向、流水、向量機(jī)量機(jī)中間代碼優(yōu)化：機(jī)器無(wú)關(guān)中間代碼優(yōu)化：機(jī)器

6、無(wú)關(guān)v如：常數(shù)計(jì)算、公共代碼段的提取如：常數(shù)計(jì)算、公共代碼段的提取2022-5-811v局部?jī)?yōu)化局部?jī)?yōu)化基本塊內(nèi)部（不包括各種轉(zhuǎn)移控制）基本塊內(nèi)部（不包括各種轉(zhuǎn)移控制）v全局優(yōu)化全局優(yōu)化循環(huán)優(yōu)化、控制流分析與化簡(jiǎn)、數(shù)據(jù)流分循環(huán)優(yōu)化、控制流分析與化簡(jiǎn)、數(shù)據(jù)流分析析2022-5-812v基本塊基本塊控制流從第一語(yǔ)控制流從第一語(yǔ)句進(jìn)入，從最后句進(jìn)入，從最后一條語(yǔ)句離開(kāi)一條語(yǔ)句離開(kāi)語(yǔ)句序列中間沒(méi)語(yǔ)句序列中間沒(méi)有停止或分枝有停止或分枝關(guān)鍵：確定每個(gè)關(guān)鍵：確定每個(gè)基本塊的入口基本塊的入口(1) (1) i := m - 1i := m - 1(2) j := n(2) j := n(3) t1 := 4

7、(3) t1 := 4 * * n; n;(4) v := a t1 (4) v := a t1 (5) i := i + 1(5) i := i + 1(6) t2 := 4 (6) t2 := 4 * * i; i;(7) t3 := a t2 ;(7) t3 := a t2 ;(8) if t3 v goto(8) if t3 v goto(12) if t5 v goto (9)(9)轉(zhuǎn)移語(yǔ)句的轉(zhuǎn)移語(yǔ)句的下一條語(yǔ)句下一條語(yǔ)句轉(zhuǎn)移語(yǔ)句轉(zhuǎn)移語(yǔ)句的目標(biāo)的目標(biāo)第一條語(yǔ)句第一條語(yǔ)句2022-5-813v1) 1) 定義入口語(yǔ)句定義入口語(yǔ)句代碼序列的第一語(yǔ)句代碼序列的第一語(yǔ)句轉(zhuǎn)移語(yǔ)句的目標(biāo)語(yǔ)句轉(zhuǎn)移

8、語(yǔ)句的目標(biāo)語(yǔ)句轉(zhuǎn)移語(yǔ)句的下一條語(yǔ)句轉(zhuǎn)移語(yǔ)句的下一條語(yǔ)句v2) 2) 定義基本塊定義基本塊一入口語(yǔ)句到下一入口一入口語(yǔ)句到下一入口語(yǔ)句之前語(yǔ)句之前一入口語(yǔ)句到一入口語(yǔ)句到轉(zhuǎn)移語(yǔ)句轉(zhuǎn)移語(yǔ)句或或停語(yǔ)句停語(yǔ)句(1) (1) i := m - 1i := m - 1(2) j := n(2) j := n(3) t1 := 4 (3) t1 := 4 * * n; n;(4) v := a t1 (4) v := a t1 (5) i := i + 1(5) i := i + 1(6) t2 := 4 (6) t2 := 4 * * i; i;(7) t3 := a t2 ;(7) t3 := a t2

9、 ;(8) if t3 v goto(8) if t3 v goto(12) if t5 v goto (9)(9)2022-5-814v程序流圖程序流圖，n n0 0 以基本塊為結(jié)點(diǎn)，以控制流為有向邊以基本塊為結(jié)點(diǎn)，以控制流為有向邊：基本塊集：基本塊集n n0 0 ：含首語(yǔ)句的基本塊含首語(yǔ)句的基本塊：有向邊集合：有向邊集合 ( (A, A, B)B)vA A 的出口是轉(zhuǎn)移語(yǔ)句，轉(zhuǎn)向的出口是轉(zhuǎn)移語(yǔ)句，轉(zhuǎn)向 B B 的入口的入口v A A 的出口不是的出口不是 轉(zhuǎn)移語(yǔ)句，轉(zhuǎn)移語(yǔ)句， B B 緊跟緊跟 A A 之后之后2022-5-815i = m - 1;i = m - 1;j = n;j =

10、n;v = a n ;v = a n ;while( 1 ) while( 1 ) while( a+i v );while( a+i v );while( a-j v );if( i j ) then break;if( i j ) then break;x = a i ;x = a i ; a i = a j ; a j = x; a i = a j ; a j = x; x = a i ; a i = a n ; a n = x;x = a i ; a i = a n ; a n = x;2022-5-816(1) (1) i := m - 1i := m - 1(2) j := n(2

11、) j := n(3) t1 := 4 (3) t1 := 4 * * n; n;(4) v := a t1 (4) v := a t1 (5) i := i + 1(5) i := i + 1(6) t2 := 4 (6) t2 := 4 * * i; i;(7) t3 := a t2 ;(7) t3 := a t2 ;(8) if t3 v (8) if t3 v (12) if t5 v goto (9)goto (9)(13)(13) if ij if ij goto (23)goto (23)(14)(14) t6 := 4 t6 := 4 * * i i(15) x := at6(

12、15) x := at6(16) t7 := 4 (16) t7 := 4 * * i i(17) t8 := 4 (17) t8 := 4 * * j j(18) t9 := a t8 (18) t9 := a t8 (19) a t7 := t9(19) a t7 := t9(20) t10 := 4 (20) t10 := 4 * * j j(21) a t10 := x(21) a t10 := x(22) (22) goto (5)goto (5)(23) t11 := 4 * i(24) x := at11(25) t12 := 4 * i(26) t13 := 4 * n(27)

13、 t14 := a t13 (28) a t12 := t14(29) t15 := 4 * n(30) a t15 := x入口：入口：代碼序列的第一語(yǔ)句代碼序列的第一語(yǔ)句 轉(zhuǎn)移語(yǔ)句的目標(biāo)語(yǔ)句轉(zhuǎn)移語(yǔ)句的目標(biāo)語(yǔ)句 轉(zhuǎn)移語(yǔ)句下一條語(yǔ)句轉(zhuǎn)移語(yǔ)句下一條語(yǔ)句i = m - 1;j = n;v = a n ;while( a+i v );if( i j ) then break;x = a i ;a i = a j ;a j = x;x = a i ;a i = a n ;a n = x;2022-5-8172022-5-818v(1) (1) 合并已知量合并已知量常數(shù)表達(dá)式計(jì)算常數(shù)表達(dá)式計(jì)算t3:=1

14、10t3:=110* *x xt1:=5+6t1:=5+6t2:=t1t2:=t1* *1010t3:=t2t3:=t2* *x x2022-5-819(1) (1) i := m - 1i := m - 1(2) j := n(2) j := n(3) (3) t1 t1 := 4 := 4 * * n; n;(4) v := a (4) v := a t1 t1 (5) i := i + 1(5) i := i + 1(6) (6) t2 t2 := 4 := 4 * * i; i;(7) (7) t3 t3 := a := a t2t2 ; ;(8) if (8) if t3t3 v v

15、 v goto (9)goto (9)(13)(13) if ij goto (23)if ij goto (23)(14)(14) t6t6 := 4 := 4 * * i i(15) x := a(15) x := at6t6 (16) (16) t7 t7 := 4 := 4 * * i i(17) (17) t8t8 := 4 := 4 * * j j(18) t9 := a (18) t9 := a t8t8 (19) a (19) a t7t7 := t9 := t9(20) t(20) t10 10 := 4 := 4 * * j j(21) a (21) a t10t10 :=

16、 x := x(22) (22) goto (5)goto (5)(23) t11 := 4 * i(24) x := at11(25) t12 := 4 * i(26) t13 := 4 * n(27) t14 := a t13 (28) a t12 := t14(29) t15 := 4 * n(30) a t15 := xv(2) (2) 重新命名臨時(shí)變量重新命名臨時(shí)變量t1 t1 代替代替 t2,t4,t6,t7,t10,t11,t12,t15t2,t4,t6,t7,t10,t11,t12,t15t3 t3 代代替替 t5,t8,t13,t14t5,t8,t13,t142022-5-8

17、20v(3) (3) 刪除基本塊內(nèi)的公共子表達(dá)式刪除基本塊內(nèi)的公共子表達(dá)式(14)(16)(14)(16)、(17)(20)(17)(20)、(23)(25)(23)(25)、(26)(29)(26)(29)(23) t1 := 4 * i(24) x := at1(25) t1 := 4 * i(26) t3 := 4 * n(27) t3 := a t3 (28) a t1 := t3(29) t1 := 4 * n(30) a t1 := x(23) t1 := 4 * i(24) x := at1(26) t3 := 4 * n(27) t3 := a t3 (28) a t1 :=

18、t3(30) a t3 := x2022-5-821v(4) (4) 刪除死代碼刪除死代碼未出現(xiàn)在程序流圖中的代碼未出現(xiàn)在程序流圖中的代碼賦值但未引用的指令賦值但未引用的指令v(5) (5) 交換語(yǔ)句次序交換語(yǔ)句次序減少臨時(shí)變量減少臨時(shí)變量t1:=a+xt1:=a+xt2:=bt2:=b* *y yt:=t1+zt:=t1+zp:=tp:=t* *x xt1:=a+xt1:=a+xt:=t1+zt:=t1+zt1:=bt1:=b* *y yp:=tp:=t* *x x2022-5-822v循環(huán)體是優(yōu)化的重點(diǎn)循環(huán)體是優(yōu)化的重點(diǎn)反復(fù)執(zhí)行反復(fù)執(zhí)行v循環(huán)的定義循環(huán)的定義有唯一入口點(diǎn)的強(qiáng)連接子圖有唯一入

19、口點(diǎn)的強(qiáng)連接子圖強(qiáng)連接子圖強(qiáng)連接子圖v任意兩結(jié)點(diǎn)間的通路上各結(jié)點(diǎn)屬于子圖任意兩結(jié)點(diǎn)間的通路上各結(jié)點(diǎn)屬于子圖2022-5-823v將循環(huán)不變運(yùn)算移到循環(huán)外將循環(huán)不變運(yùn)算移到循環(huán)外v例例 ：程序優(yōu)化：程序優(yōu)化i = 0;i = 0;while( i 20 ) while( i = 20 goto (8)(4) if i = 20 goto (9)2022-5-827v利用歸納變量相關(guān)的計(jì)算代替歸納變量的利用歸納變量相關(guān)的計(jì)算代替歸納變量的計(jì)算計(jì)算條件表達(dá)式的修改條件表達(dá)式的修改無(wú)用語(yǔ)句的刪除無(wú)用語(yǔ)句的刪除v優(yōu)化效果優(yōu)化效果語(yǔ)句數(shù)、乘除法數(shù)、變址運(yùn)算、一般運(yùn)算語(yǔ)句數(shù)、乘除法數(shù)、變址運(yùn)算、一般運(yùn)算20

20、22-5-828(5) x := x + 4(6) i := i + 1(7) y := t1 + x(8) goto (4)(4) x := x + 4(5) y := t1 + x(6) goto (3)(1) i := 0(2) t1 := z * 6 (3) x := -4(1) t1 := z * 6(2) x := -4(4) if i 20 goto (9)(3) if x 76 goto (7)2022-5-829生成生成v代碼生成的任務(wù)代碼生成的任務(wù)針對(duì)目標(biāo)語(yǔ)言的特殊性，生成高性能的目標(biāo)代針對(duì)目標(biāo)語(yǔ)言的特殊性，生成高性能的目標(biāo)代碼（機(jī)器相關(guān)）碼（機(jī)器相關(guān)）2022-5-830

21、v輸入：中間代碼序列輸入：中間代碼序列三地址代碼、語(yǔ)法結(jié)構(gòu)樹(shù)、后綴式三地址代碼、語(yǔ)法結(jié)構(gòu)樹(shù)、后綴式v輸出：目標(biāo)代碼輸出：目標(biāo)代碼絕對(duì)機(jī)器代碼、可重定位機(jī)器指令代碼、絕對(duì)機(jī)器代碼、可重定位機(jī)器指令代碼、匯編指令代碼匯編指令代碼v目標(biāo)機(jī)目標(biāo)機(jī)多通用寄存器、控制棧、堆多通用寄存器、控制棧、堆2022-5-831v質(zhì)量要求質(zhì)量要求目標(biāo)代碼效率高目標(biāo)代碼效率高目標(biāo)程序短目標(biāo)程序短v實(shí)現(xiàn)方法實(shí)現(xiàn)方法充分利用寄存器充分利用寄存器參考目標(biāo)機(jī)的結(jié)構(gòu)與指令形式參考目標(biāo)機(jī)的結(jié)構(gòu)與指令形式2022-5-832v對(duì)象：基本塊對(duì)象：基本塊 NN中的變量中的變量A AUSE(N, A)USE(N, A)：NN中對(duì)中對(duì) A A定值前，定值前，A A的引用次數(shù)的引用次數(shù)LIVE(N, A)LIVE(N, A)：1 1 表示表示 A A在在 NN中被定值，且中被定值，且出口出口之后之后有引用；有引用；0 0 表示其他情況。表示其他情況。v循環(huán)循環(huán) L L 中為變量中為變量 A A 分配寄存器節(jié)省的執(zhí)行代價(jià)分配寄存器節(jié)省的執(zhí)行代價(jià)LN)A,N(LIVE*)A,N(USE22022-5-833v計(jì)算各循環(huán)中各變量的可節(jié)省執(zhí)行代價(jià)，據(jù)計(jì)算各循環(huán)中各變量的可節(jié)省執(zhí)行代價(jià)，據(jù)此分配寄