中科大2021－2022學(xué)年秋季第一學(xué)期《編譯原理與技術(shù)》第十一講 代碼優(yōu)化（1）

1、代碼優(yōu)化7/25/20221編譯原理與技術(shù)之代碼優(yōu)化代碼優(yōu)化的目標(biāo)提高最終目標(biāo)代碼的運(yùn)行效率（性能） 時(shí)間：運(yùn)行的更快 空間：降低內(nèi)存需求保持源程序的語(yǔ)義7/25/20222編譯原理與技術(shù)之代碼優(yōu)化代碼優(yōu)化的種類(lèi)窺孔優(yōu)化局部?jī)?yōu)化基本塊內(nèi)優(yōu)化全局優(yōu)化基本塊間優(yōu)化（過(guò)程內(nèi)）過(guò)程間優(yōu)化程序全局優(yōu)化7/25/20223編譯原理與技術(shù)之代碼優(yōu)化代碼優(yōu)化的種類(lèi)窺孔優(yōu)化“孔”未優(yōu)化的目標(biāo)代碼片段（windows）窺孔優(yōu)化種類(lèi)： 刪除冗余的存、取操作e.g.mov r0, a / r0 - amov a, r0 / a - r0, 可刪除 刪除不可達(dá)代碼7/25/20224編譯原理與技術(shù)之代碼優(yōu)化代碼優(yōu)化的種

2、類(lèi)窺孔優(yōu)化 e.g. goto L1goto L2 / 語(yǔ)句前無(wú)標(biāo)號(hào)，死代碼L1: L2: 控制流優(yōu)化7/25/20225編譯原理與技術(shù)之代碼優(yōu)化代碼優(yōu)化的種類(lèi)窺孔優(yōu)化goto L1L1: goto L2goto L2L1: goto L2if ab goto L1L1: goto L2if ab goto L2L1: goto L2goto L1 /唯一跳轉(zhuǎn)L1 /L1前是無(wú)條件跳轉(zhuǎn)L1: if a b goto L2L3:if a ShiftLeft $3, R0ADD $0, R1 / 刪除，未改變R1MUL $1, R2 / 刪除 利用目標(biāo)機(jī)指令特點(diǎn)e.g. inc、enter(建立棧

3、幀）leave（清除棧幀） CISC 系統(tǒng)的“復(fù)雜”尋址模式 其它優(yōu)化措施，如常量合并、復(fù)寫(xiě)傳播等7/25/20227編譯原理與技術(shù)之代碼優(yōu)化代碼優(yōu)化的種類(lèi)局部?jī)?yōu)化基本塊和流圖 基本塊：能順序執(zhí)行的程序代碼序列。其入口為： 程序的第一代碼 條件或無(wú)條件轉(zhuǎn)移代碼所轉(zhuǎn)到的目標(biāo)代碼 跟在條件或無(wú)條件轉(zhuǎn)移代碼后的代碼 基本塊劃分 相鄰入口中間的代碼序列（僅含前一入口） 某入口到程序的停止語(yǔ)句代碼之間的代碼序列 流圖：由基本塊按控制流方向形成的有向圖基本塊內(nèi)優(yōu)化，主要有： 常量傳播、合并和公共子表達(dá)式刪除 復(fù)寫(xiě)傳播與死代碼（無(wú)用代碼）刪除7/25/20228編譯原理與技術(shù)之代碼優(yōu)化代碼優(yōu)化的種類(lèi)全局優(yōu)化

4、基本塊間優(yōu)化基本塊間控制流與數(shù)據(jù)流分析技術(shù)優(yōu)化措施主要有： 循環(huán)優(yōu)化 ：80/20 規(guī)則 不變式外提、歸納變量刪除、強(qiáng)度消弱等 公共子表達(dá)式刪除 常量傳播、合并常量、復(fù)寫(xiě)傳播 死代碼（無(wú)用賦值）刪除7/25/20229編譯原理與技術(shù)之代碼優(yōu)化典型的優(yōu)化編譯器的組織前 端代 碼生成器代 碼優(yōu)化器變 換數(shù)據(jù)流分 析控制流分 析中間表示中間表示7/25/202210編譯原理與技術(shù)之代碼優(yōu)化優(yōu)化舉例快速排序程序片段如下，i = m 1; j = n; v = an; while (1) do i = i +1; while(aiv); if (i = j) break; x=ai; ai=aj; aj

5、=x; x=ai; ai=an; an=x;/B1(1) i := m 1(2) j := n(3) t1 := 4 * n(4) v := at17/25/202211編譯原理與技術(shù)之代碼優(yōu)化優(yōu)化舉例快速排序程序片段如下，i = m 1; j = n; v = an; while (1) do i = i +1; while(aiv); if (i = j) break; x=ai; ai=aj; aj=x; x=ai; ai=an; an=x;/B2(5) i := i + 1(6) t2 := 4 * i(7) t3 := at2(8) if t3 v goto （5）7/25/2022

6、12編譯原理與技術(shù)之代碼優(yōu)化優(yōu)化舉例快速排序程序片段如下，i = m 1; j = n; v = an; while (1) do i = i +1; while(aiv); if (i = j) break; x=ai; ai=aj; aj=x; x=ai; ai=an; an=x;/B3(9) j := j 1(10) t4 := 4 * j(11) t5 := at4(12) if t5 v goto (9)7/25/202213編譯原理與技術(shù)之代碼優(yōu)化優(yōu)化舉例快速排序程序片段如下，i = m 1; j = n; v = an; while (1) do i = i +1; while(

7、aiv); if (i = j) break; x=ai; ai=aj; aj=x; x=ai; ai=an; an=x;/B4(13) if i = j goto (23)7/25/202214編譯原理與技術(shù)之代碼優(yōu)化優(yōu)化舉例快速排序程序片段如下，i = m 1; j = n; v = an; while (1) do i = i +1; while(aiv); if (i = j) break; x=ai; ai=aj; aj=x; x=ai; ai=an; an=x;/B5(14) t6 := 4 * i(15) x := at6(16) t7 := 4 * i (17) t8 := 4

8、 * j(18) t9 := at8(19) at7 := t9(20) t10 := 4 * j(21) at10 := x(22) goto (5)7/25/202215編譯原理與技術(shù)之代碼優(yōu)化優(yōu)化舉例快速排序程序片段如下，i = m 1; j = n; v = an; while (1) do i = i +1; while(aiv); if (i = j) break; x=ai; ai=aj; aj=x; x=ai; ai=an; an=x;/B6(23) t11 := 4 * i(24) x := at11(25) t12 := 4 * i (26) t13 := 4 * n(27

9、) t14 := at13(28) at12 := t14(29) t15 := 4 * n(30) at15 := x7/25/202216編譯原理與技術(shù)之代碼優(yōu)化優(yōu)化舉例流圖i := m 1j := nt1 := 4 * nv := at1i := i + 1t2 := 4 * it3 := at2if t3 v goto B2B1B2j := j 1t4 := 4 * jt5 := at4if t5 v goto B3if i = j goto B6B4B3B5B67/25/202217編譯原理與技術(shù)之代碼優(yōu)化優(yōu)化舉例公共子表達(dá)式刪除基本塊內(nèi)t6 := 4 * ix := at6t7 :

10、= 4 * i t8 := 4 * jt9 := at8at7 := t9t10 := 4 * jat10 := xgoto B2B5B6t11 := 4 * ix := at11t12 := 4 * i t13 := 4 * nt14 := at13at12 := t14t15 := 4 * n at15 := x 變換7/25/202218編譯原理與技術(shù)之代碼優(yōu)化優(yōu)化舉例公共子表達(dá)式刪除基本塊內(nèi)t6 := 4 * ix := at6t8 := 4 * jt9 := at8at6 := t9at8 := xgoto B2B5B6t11 := 4 * ix := at11t13 := 4 *

11、nt14 := at13at11 := t14at13 := x 7/25/202219編譯原理與技術(shù)之代碼優(yōu)化優(yōu)化舉例公共子表達(dá)式刪除基本塊間 t2:=4 * i : B2 - B5 t2:=4 * i : B2 - B6 t4:= 4 * j : B3 - B5 t1:= 4 * n : B1 - B6t6 := 4 * ix := at6t8 := 4 * jt9 := at8at6 := t9at8 := xgoto B2B5B6t11 := 4 * ix := at11t13 := 4 * nt14 := at13at11 := t14at13 := x 變換7/25/202220編

12、譯原理與技術(shù)之代碼優(yōu)化優(yōu)化舉例公共子表達(dá)式刪除基本塊間 t3:=at2 : B2 - B5 t3:=at2 : B2 - B6 t5:= at4 : B3 - B5x := at2t9 := at4at2 := t9at4 := xgoto B2B5B6x := at2t14 := at1at2 := t14at1 := x 變換7/25/202221編譯原理與技術(shù)之代碼優(yōu)化優(yōu)化舉例公共子表達(dá)式刪除基本塊間B1中 v := at1 能否作為公共子表達(dá)式？x := t3at2 := t5at4 := xgoto B2B5B6x := t3t14 := at1at2 := t14at1 := x

13、7/25/202222編譯原理與技術(shù)之代碼優(yōu)化優(yōu)化舉例復(fù)寫(xiě)傳播 形成為f := g的賦值叫做復(fù)寫(xiě)語(yǔ)句 優(yōu)化過(guò)程中會(huì)大量引入復(fù)寫(xiě) 復(fù)寫(xiě)傳播變換是在復(fù)寫(xiě)語(yǔ)句f := g后，盡可能用g代表f（暗示有前提條件）復(fù)寫(xiě)傳播變換帶來(lái) 常量合并 死代碼刪除7/25/202223編譯原理與技術(shù)之代碼優(yōu)化x := t3 /可以考慮刪除at2 := t5at4 := t3goto B2x := t3at2 := t5at4 := xgoto B2優(yōu)化舉例復(fù)寫(xiě)傳播B5B57/25/202224編譯原理與技術(shù)之代碼優(yōu)化x := t3 /可以考慮刪除t14 := at1at2 := t14at1 := t3 優(yōu)化舉例復(fù)寫(xiě)

14、傳播B6B6x := t3t14 := at1at2 := t14at1 := x B6中，t14 := at1 可以復(fù)寫(xiě)傳播嗎？7/25/202225編譯原理與技術(shù)之代碼優(yōu)化優(yōu)化舉例循環(huán)優(yōu)化 代碼外提 歸納變量刪除 強(qiáng)度削弱例：while (i = limit 2 ) 變換成t = limit 2; /為什么提出循環(huán)？while (i v goto B3B37/25/202227編譯原理與技術(shù)之代碼優(yōu)化優(yōu)化舉例i := m 1j := nt1 := 4 * nv := at1B1B2j := j 1t4 := t4 4t5 := at4if t5 v goto B3B4B3B5B6t4 :=

15、 4 * jif i = j goto B6j := j 1t4 := 4 * jt5 := at4if t5 v goto B3B3除第一次外，t4 = 4 * j在B3的入口一定保持在j := j 1后，關(guān)系t4 = 4 * j + 4也保持7/25/202228編譯原理與技術(shù)之代碼優(yōu)化i := m 1j := nt1 := 4 * nv := at1t2 := 4 * it4 := 4 * jt2 := t2 + 4t3 := at2if t3 v goto B2B1B2t4 := t4 4t5 := at4if t5 v goto B3if t2 = t4 goto B6at2 :=

16、t5at4 := t3goto B2B4B3B5t14 := at1at2 := t14at1 := t3B6優(yōu)化舉例7/25/202229編譯原理與技術(shù)之代碼優(yōu)化代碼優(yōu)化（續(xù)） 循環(huán)優(yōu)化簡(jiǎn)介7/25/202230編譯原理與技術(shù)之代碼優(yōu)化流圖中的循環(huán)循環(huán)定義 程序流圖中有唯一入口的強(qiáng)連通子圖必經(jīng)結(jié)點(diǎn)（集合） d DOM n 表示結(jié)點(diǎn)d是結(jié)點(diǎn)n的必經(jīng)結(jié)點(diǎn)，如果從流圖的開(kāi)始結(jié)點(diǎn)出發(fā)到達(dá)結(jié)點(diǎn)n的每條路徑上必須經(jīng)過(guò)結(jié)點(diǎn)d?；剡?n-d, 如果d DOM n。7/25/202231編譯原理與技術(shù)之代碼優(yōu)化流圖中的循環(huán)自然循環(huán) 由回邊 n-d 確定的循環(huán)Loop(n-d) Loop(n-d) = d U

17、流圖中所有不經(jīng)過(guò)結(jié)點(diǎn) d 而能達(dá)到結(jié)點(diǎn) n 的其它結(jié)點(diǎn)可歸約流圖 去除流圖中的回邊后的子圖是無(wú)環(huán)有向圖 結(jié)構(gòu)化程序流圖是可歸約的 存在不可歸約流圖7/25/202232編譯原理與技術(shù)之代碼優(yōu)化流圖中的循環(huán)1234567891012345678910e.g. 右邊流圖的必經(jīng)結(jié)點(diǎn)樹(shù)e.g. 一個(gè)流圖7/25/202233編譯原理與技術(shù)之代碼優(yōu)化流圖中的循環(huán)自然循環(huán)回邊10 7 循環(huán)7, 8, 10回邊7 4 循環(huán)4, 5, 6, 7, 8, 10回邊4 3和8 3 循環(huán)3, 4, 5, 6, 7, 8, 10回邊9 11, 2, 3, 4, 5, 6, 7, 8, 9, 1012345678910

18、e.g. 一個(gè)流圖7/25/202234編譯原理與技術(shù)之代碼優(yōu)化循環(huán)優(yōu)化代碼外提 循環(huán)不變計(jì)算 前置結(jié)點(diǎn)B0B0循環(huán)L(b) 外提代碼放在前置結(jié)點(diǎn)B0B0循環(huán)L(a) 代碼外提前，B0是首結(jié)點(diǎn)7/25/202235編譯原理與技術(shù)之代碼優(yōu)化循環(huán)優(yōu)化代碼外提尋找循環(huán)不變計(jì)算（1）標(biāo)記循環(huán)各結(jié)點(diǎn)（基本塊）中的語(yǔ)句x := y + z為不變計(jì)算，如果y和z均為常量或定值點(diǎn)在循環(huán)外（ud鏈）；（2）檢查其余語(yǔ)句，如 w := x + u，如果x和u均為常量或定值點(diǎn)在循環(huán)外，或其唯一能達(dá)到的定值點(diǎn)已標(biāo)記, 如（1）中的x，則標(biāo)記該語(yǔ)句；（3）重復(fù)（2）直至沒(méi)有語(yǔ)句被標(biāo)記為不變計(jì)算為止。 7/25/2022

19、36編譯原理與技術(shù)之代碼優(yōu)化循環(huán)優(yōu)化代碼外提如何實(shí)施代碼外提？考察已標(biāo)記的循環(huán)不變計(jì)算，P: x := y + z ， 如果滿(mǎn)足，（1）P點(diǎn)所在基本塊是所有循環(huán)出口結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)；（2）x 在循環(huán)中沒(méi)有其它定值點(diǎn)；（3）循環(huán)中對(duì) x 的引用均來(lái)自 P 點(diǎn)的定值。問(wèn)題：如果 P 點(diǎn)定值滿(mǎn)足（2）和（3），而不滿(mǎn)足（1），能否外提該代碼？7/25/202237編譯原理與技術(shù)之代碼優(yōu)化循環(huán)優(yōu)化代碼外提非法代碼外提case 1i := 1B1if u v goto B3B2i := 2u := u + 1B3v := v -1if v = 20 goto B5B4j := iB5代碼外提i := 1B

20、1if u v goto B3B2u := u + 1B3v := v -1if v = 20 goto B5B4j := iB5i := 2B6j：我要17/25/202238編譯原理與技術(shù)之代碼優(yōu)化循環(huán)優(yōu)化代碼外提非法代碼外提case 2B2代碼外提i := 1B1i := 3if u v goto B3i := 2u := u + 1B3v := v -1if v = 20 goto B5B4j := iB5i := 1B1i := 3if u v goto B3u := u + 1B3v := v -1if v = 20 goto B5B4j := iB5i := 2B6j：2呢？我要

21、外提？7/25/202239編譯原理與技術(shù)之代碼優(yōu)化循環(huán)優(yōu)化代碼外提非法代碼外提case 3i := 1B1i := 3if u v goto B3i := 2/外提u := u + 1B3k := iv := v -1if v = 20 goto B5B4j := iB5i , 你從哪里來(lái)？7/25/202240編譯原理與技術(shù)之代碼優(yōu)化循環(huán)優(yōu)化歸納變量 基本歸納變量 i :（i，1，0），循環(huán)中有唯一定值，形如 i := i + n，n 為常量。 i 族歸納變量 j :（i，c，d），如果循環(huán)中變量 j 的唯一定值滿(mǎn)足 j := i * c d，c和d為循環(huán)不變量。 更多的i 族歸納變量 k

22、 , k 的定值形式為：k := j * b, k := b * j, k := j / b, k := j + b , k := b + j,b 為循環(huán)不變量，j 為 i 族歸納變量（i，c，d） ，則 k 亦為i 族歸納變量。7/25/202241編譯原理與技術(shù)之代碼優(yōu)化循環(huán)優(yōu)化強(qiáng)度消弱 i 族歸納變量 j : ( i, c, d ), j := i * c + d; 引入新變量 s ，在循環(huán)前置塊末尾添加如下語(yǔ)句：s := c * i0 / if c = 1 then s := i0 s := s + d / if d = 0 then no code 變量 j 的定值語(yǔ)句變?yōu)?j :=

23、 s; 在基本歸納變量 i 定值語(yǔ)句，i := i n 后添加語(yǔ)句s := s + c * n; s 也是i 族歸納變量 s : ( i, c, d )7/25/202242編譯原理與技術(shù)之代碼優(yōu)化循環(huán)優(yōu)化刪除歸納變量 如果基本歸納變量 i ,循環(huán)出口后不活躍，在循環(huán)中除了遞歸賦值外，僅出現(xiàn)在若干條件測(cè)試語(yǔ)句中，如 if i op x goto L 等，則可以考慮刪除此基本歸納變量。 選擇 i 族歸納變量 j : (i, c, d), 用以下語(yǔ)句序列，s := c * x;s := s + d;if j op s goto L 替代 if i op x goto L 刪除語(yǔ)句 i := i +

24、 n 7/25/202243編譯原理與技術(shù)之代碼優(yōu)化循環(huán)優(yōu)化舉例e.g. 對(duì)以下偽C程序片段進(jìn)行有關(guān)循環(huán)優(yōu)化int A100100100;for ( i 0 ; i100; i+)for ( j = 0; j100; j+)for ( k = 0; k100; k+)A i j k i * j * k;7/25/202244編譯原理與技術(shù)之代碼優(yōu)化循環(huán)優(yōu)化舉例代碼外提for ( i 0 ; i100; i+)for ( j = 0; j100; j+)for ( k = 0; k100; k+)A i j k i * j * k;對(duì)于最內(nèi)層循環(huán)k而言，為循環(huán)不變計(jì)算7/25/202245編譯原

25、理與技術(shù)之代碼優(yōu)化循環(huán)優(yōu)化舉例代碼外提for ( i 0 ; i100; i+)for ( j = 0; j100; j+) t1 = addr( A i j );t2 = i * j;for ( k = 0; k100; k+)t1 k t2 * k; / Loop jA i 在循環(huán)j中保持“不變”7/25/202246編譯原理與技術(shù)之代碼優(yōu)化循環(huán)優(yōu)化舉例代碼外提for ( i 0 ; i100; i+) t3 = addr( A i );for ( j = 0; j100; j+) t1 = addr( t3 j );t2 = i * j;for ( k = 0; k100; k+)t1 k t2 * k; / Loop j / Loop i歸納表達(dá)式（變量）7/25/202247編譯原理與技術(shù)之代碼優(yōu)化循環(huán)優(yōu)化舉例強(qiáng)度消弱for ( i 0 ; i100; i+) t3 = addr( A i );t4 = 0; / i * j 的初值for ( j = 0; j100; j+) t1 = addr( t3 j );t2 = t4;t5 = 0; / t2 * k 的初值for ( k = 0; k100;