《編譯原理PPT課件第六章中間代碼優(yōu)化》由會員分享，可在線閱讀，更多相關(guān)《編譯原理PPT課件第六章中間代碼優(yōu)化（43頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、1 局部優(yōu)化 循環(huán)優(yōu)化 優(yōu)化目的: 提高運行速度, 減少存儲空間.第六章 中間代碼優(yōu)化內(nèi)容 :第一節(jié) 優(yōu)化概述 2 右面為循環(huán)的中間代碼:對該段中間代碼,可以進(jìn)行如下優(yōu)化:1 刪除多余運算 見(3),(6)兩四元式的 4*I,(6) 可以改寫為: T4:=T1, 從而減少了一次乘法.參見下頁四元式表(1) PROD:=0(2) I:=1(3) T1:=4*I(4) T2:=addr(A)-4(5) T3:=T2T1(6) T4:=4*I(7) T5:=addr(B)-4(8) T6:=T5T4(9) T7:=T3*T6(10) PROD:=PROD+T7(11) I:= I+1(12) if

2、I=20 goto(3) 3 (1) PROD:=0(2) I:=1(3) T1:=4*I(4) T2:=addr(A)-4(5) T3:=T2T1(6) T4:=T1(7) T5:=addr(B)-4(8) T6:=T5T4(9) T7:=T3*T6(10) PROD:=PROD+T7(11) I:= I+1(12) if I代碼外提 (4)與(7)每次循環(huán)其值都不變,稱為循環(huán)不變量.可以放到循環(huán)前,減少循環(huán)中的運算.參見下頁四元式表 4 (1) PROD:=0(2) I:=1(4) T2:=addr(A)-4(7) T5:=addr(B)-4(3) T1:=4*I(5) T3:=T2T1(

3、6) T4:=T1(8) T6:=T5T4(9) T7:=T3*T6(10) PROD:=PROD+T7(11) I:= I+1(12) if I強度削弱 由于每次循環(huán) I 都增加 1,因此, T1遞增 4 , 可把 (3) 改為T1:=T1+4 ,放在(11)之后,并在循環(huán)前對 I 賦初值 T1:=4*I.(12)改為 goto (5).參見下頁四元式表 5 (1) PROD:=0(2) I:=1(4) T2:=addr(A)-4(7) T5:=addr(B)-4(3) T1:=4*I(5) T3:=T2T1(6) T4:=T1(8) T6:=T5T4(9) T7:=T3*T6(10) PR

4、OD:=PROD+T7(11) I:= I+1(3) T1:=T1+4(12) if I變換控制條件 由于 I 只用作循環(huán)控制, 而 T1=4*I ,因此, 可用 T1 替換 I , I=20 等價于 T1=80,把(12)改為 if T1=80 goto(5)這樣, 可以刪掉無用的 I .參見下頁四元式表 6 (1) PROD:=0(2) I:=1(4) T2:=addr(A)-4(7) T5:=addr(B)-4(3) T1:=4*I(5) T3:=T2T1(6) T4:=T1(8) T6:=T5T4(9) T7:=T3*T6(10) PROD:=PROD+T7(3) T1:=T1+4(1

5、2) if T1合并已知量 由于(3)中的 I 在 (2)賦值后仍然為 1,因此可改為:T1:=46 復(fù)寫 (6)中 T1 復(fù)制到 T4,而(6)到(8)之間沒有改變T1 和 T4, 因此(8) 可以改為: T6:=T5T1 ,從而使(6)式無用.參見下頁四元式表 7 (1) PROD:=0(2) I:=1(4) T2:=addr(A)-4(7) T5:=addr(B)-4(3) T1:=4(5) T3:=T2T1(6) T4:=T1(8) T6:=T5T1(9) T7:=T3*T6(10) PROD:=PROD+T7(3) T1:=T1+4(12) if T1刪除無用賦值 (2) 和 (6)

6、 兩四元式為無用四元式,可以刪除. 最終優(yōu)化后,得到下頁四元式表 8 (1) PROD:=0(4) T2:=addr(A)-4(7) T5:=addr(B)-4(3) T1:=4(5) T3:=T2T1(8) T6:=T5T1(9) T7:=T3*T6(10) PROD:=PROD+T7(3) T1:=T1+4(12) if T1=80 goto(5)(1) PROD:=0(2) I:=1(3) T1:=4*I(4) T2:=addr(A)-4(5) T3:=T2T1(6) T4:=4*I(7) T5:=addr(B)-4(8) T6:=T5T4(9) T7:=T3*T6(10) PROD:=

7、PROD+T7(11) I:= I+1(12) if I 定義: 基本塊是一順序執(zhí)行的中間代碼序列,僅包含一個入口 四元式 和一個出口四元式,第一條四元式為入口四元式,最后 一條四元式為出口四元式.中間部分不含轉(zhuǎn)移四元式.2 基本塊的劃分 給定一四元式程序,可以通過如下算法,劃分基本塊: 10基本塊劃分算法:1) 求四元式程序中所有基本入口四元式,包括: a) 程序的第一條四元式; b) 轉(zhuǎn)移語句轉(zhuǎn)移到的四元式; c) 條件語句之后的第一條四元式.2) 對每一入口四元式,構(gòu)造一個基本塊: 從該入口四元式到下一入口四元式之前的一條四元式, 或到一轉(zhuǎn)移語句,或到一停止語句之間的四元式序列 組成.3

8、) 凡未納入這些基本塊的四元式,為無用四元式,可以刪除. 11示例:設(shè)四元式程序如下:(1) read (X)(2) read (Y)(3) R:=X MOD Y(4) if R=0 goto (8)(5) X:=Y(6) Y:=R(7) goto (3)(8) write (Y)(9) halt基本入口四元式包括: (1) 程序第一條四元式 (3) 轉(zhuǎn)移語句轉(zhuǎn)移到的四元式 (5) 條件語句之后的第一條四元式 (8) 轉(zhuǎn)移語句轉(zhuǎn)移到的四元式由此可以得到四個基本塊.(見下頁) 12 (8) write (Y)(9) halt(1) read (X)(2) read (Y)(3) R:=X MOD

9、 Y(4) if R=0 goto (8)(5) X:=Y(6) Y:=R(7) goto (3) B1B2B3B4 13二 基本塊內(nèi)的優(yōu)化 基本塊內(nèi)可以進(jìn)行以下幾種優(yōu)化:合并已知量,刪除多余運算(公共子表達(dá)式)刪除無用賦值 優(yōu)化手段: DAG 1 DAG 的定義 DAG 是有向無環(huán)路圖的簡稱,結(jié)點的基本形式如右圖: n i 為結(jié)點名, val 為結(jié)點值標(biāo)記, op 為結(jié)點的運算. n ini1 ni2op val 142 四元式的 DAG 表示 考慮下面三種類型的四元式,DAG表示如右所示0 型: (:=, B, , A)1 型: (op, B, , A)2 型: (op,B,C,A) n

10、i B,An in k A Bop An ini1 ni2 B Cop 153 基本塊的 DAG 構(gòu)造算法及優(yōu)化令 NODE(A)= 若 DAG 中存在值標(biāo)記為 A 的結(jié)點 n ,則返回 n ; 否則 返回 null.基本塊的 DAG 構(gòu)造算法如下: (1) 令 DAG =null (2) for 基本塊的 每一四元式 do 若 NODE(A) 未被引用,或有多個值標(biāo)記 , 則 刪除 值標(biāo)記 A; /(刪除無用賦值) 根據(jù)四元式類型,分別轉(zhuǎn)到 T0,T1,T2 處 T0 : /(:=, B, , A) 若NODE(B)= null 生成值標(biāo)記為 B 的葉結(jié)點 n否則 令 n= NODE(B);

11、 把 A 添加在 n 結(jié)點的右側(cè); 返回 (2) 16 T1 : /(op, B, , A) 若 B 為已知量 / 合并已知量 執(zhí)行 op B , 得到一新常數(shù) p, 若NODE(p)= null 生成值標(biāo)記為 p 的葉結(jié)點 n 否則 令 n= NODE(p); 把 A 添加在 n 結(jié)點的右側(cè); 返回 (2) 否則 若 DAG 中存在型如右式的子圖 則把 A 添加在 n 結(jié)點的右側(cè); 返回 (2) /合并多余運算 否則 若NODE(B)= null 生成值標(biāo)記為 B 的葉結(jié)點 n1 否則 令 n1= NODE(B); 建立一運算為 op ,值標(biāo)記為 A 的結(jié)點 n, 從 n 連一邊到 n1 ,

12、返回(2) n n 1 Bop 17 T2 : /(op, B, C , A) 若 B ,C為已知量 / 合并已知量 執(zhí)行 op B , 得到一新常數(shù) p, 若NODE(p)= null 生成值標(biāo)記為 p 的葉結(jié)點 n 否則 令 n= NODE(p); 把 A 添加在 n 結(jié)點的右側(cè); 返回 (2) 否則 若 DAG 中存在型如右式的子圖 則把 A 添加在 n 結(jié)點的右側(cè); 返回 (2) /合并多余運算 否則 若NODE(B)= null 生成值標(biāo)記為 B 的葉結(jié)點 n1 否則 令 n1= NODE(B); 若NODE(C)= null 生成值標(biāo)記為 C 的葉結(jié)點 n2 否則 令 n2= NO

13、DE(C); 建立一運算為 op ,值標(biāo)記為 A 的結(jié)點 n, 從 n 分別連邊到 n1 , n2 ,返回(2) n n 1 n 2 B Cop 184 示例:設(shè)基本塊如下:(1) A:=x+y(2) T0:=3.14(3) T1:=2*T0(4) T2:=R+r(5) A:=T1*T2(6) B:=A(7) T3:=2*T0(8) T4:=R+r(9) T5:=T3*T4(10) T6:=R-r(11) B:=T5*T6 19DAG 如下3 1 2 x y+ A 4 3.14,T0 5 6.28,T1,T3 6 R 7 r8 T2,T4 10 T69 A,B,T511 B+ -* * 20生

14、成DAG 后,實質(zhì)上已經(jīng)進(jìn)行了局部優(yōu)化,再把 DAG 還原得到如下四元式:(1) T0:=3.14(2) T1:=6.28(3) T3:= 6.28(4) T2:=R+r(5) T4:= T2(6) A:=6.28*T2(7) T5:=A(8) T6:=R-r(9) B:= A *T6 21第三節(jié) 循環(huán)優(yōu)化 循環(huán)是由循環(huán)語句,if 及 goto 語句構(gòu)成. 為了找出中間代碼程序中的所有循環(huán),就要對程序的流程進(jìn)行分析,流程是以基本塊為單位的,因為基本塊內(nèi)無循環(huán).一 控制流程圖與循環(huán)的定義1控制流程圖的 定義:控制流程圖是具有唯一首結(jié)點的有向圖,簡稱為流圖.可表示為三元式:G =( N,E,n0

15、)N 為結(jié)點集,每 一結(jié)點為一基本塊;E 為有向邊,代表流向; n0為首結(jié)點,它包含了程序的第一條語句. 222 流圖的構(gòu)造方法 (1) 若基本塊 j 在程序中的位置緊跟在基本塊 i 之后,且 i 的出口語句非 goto (s), 則: (2)若基本塊 i 的出口語句為 goto (s), 或 if.goto (s),而( s ) 是基本塊 j 的入口語句,則:示例: i j i j 23設(shè)四元式程序如下:(1) read (X)(2) read (Y)(3) R:=X MOD Y(4) if R=0 goto (8)(5) X:=Y(6) Y:=R(7) goto (3)(8) write

16、(Y)(9) halt (8) write (Y)(9) halt(1) read (X)(2) read (Y)(3) R:=X MOD Y(4) if R=0 goto (8)(5) X:=Y(6) Y:=R(7) goto (3) B1B2B3B4流圖 243 循環(huán)的定義 流圖中,滿足下面兩條性質(zhì)的結(jié)點序列稱為一個循環(huán):(1) 結(jié)點序列為強連通的;(任意兩點間都有通路,且通路上的結(jié)點都屬于結(jié)點序列)(2) 結(jié)點序列中僅有一個入口結(jié)點.示例:右面為一流圖結(jié)點序列 6 , 4,5,6,7 , 2,3,4,5,6,7是滿足以上定義的循環(huán);但結(jié)點序列 2,4, 2,3,4, 4,5,7, 4,6

17、,7不是上述意義下的循環(huán). 12 4 3 6 5 7 25二 查找循環(huán) 為了建立循環(huán)的查找算法,首先介紹幾個基本概念: 必經(jīng)結(jié)點集,回邊,可歸約流圖1 必經(jīng)結(jié)點集定義: 若從流圖首結(jié)點出發(fā)到達(dá) nj 的通路都必須經(jīng)過 ni ,則稱ni 為 nj 的必經(jīng)結(jié)點, 記為 ni DOM nj ; 流圖中結(jié)點 n 的所有必經(jīng)結(jié)點,稱為 n 的必經(jīng)結(jié)點集, 記為 D(n). 26 12 4 3 6 5 7 例如: 右圖各結(jié)點的必經(jīng)結(jié)點集為:D(1)=1D(2)=1,2D(3)=1,2,3D(4)=1,2,4D(5)=1,2,4,5D(6)=1,2,4,6D(7)=1,2,4,7 27 設(shè) p1,p2.pk

18、 是 n 的所有前趨結(jié)點, 根據(jù)定義,若 所有 pi ( 1ik )均有 d DOM pi ,則 d DOM n, 即D(n)= n D(p1) D(p2) . D(pk) 求 D(n) 的算法 (1) 令 D(n0)= n0 ; D(i)= N (i n0); (2) 對每一個 ni (i n0),temp= ni D(p1) D(p2) . D(pk);/ p1,p2.pk 為 ni 的所有前趨結(jié)點 if D(ni) temp then D(ni) :=temp (3) 重復(fù)(2), 直到所有D(ni)不再改變. d p1 p2 pk n 282 回邊定義: 設(shè) ba是流圖中一條有向邊,且

19、 a D(b), 則ba稱是流圖中的一條回邊. 可以從必經(jīng)結(jié)點集中求出回邊:for b N do for a DOM(b) do if 為一條有向邊 then 為回邊3 可規(guī)約流圖定義: 一個流圖稱為可規(guī)約流圖,但且僅當(dāng)流圖中除去回邊而剩余部分構(gòu)成無環(huán)路流圖. ba回邊DOM 294循環(huán)查找算法定理: 若流圖為可規(guī)約流圖,已知有向邊 ba 是一條回邊,則由結(jié)點 b,a 以及有通路到達(dá) b 而不經(jīng)過 a 的所有結(jié)點序列構(gòu)成流圖的一個循環(huán).查找回邊ba構(gòu)成的循環(huán)算法:(1) 令 loop:=b,a; push(S,b);(2) if not empty(S) then n:=pop(s); for

20、 (m in pn) do / pn 為 n 的前趨結(jié)點集 if (m not in loop) then loop:=loop+m;push(S,m) 30三 優(yōu)化信息-ud 集 為了進(jìn)行循環(huán)優(yōu)化,還應(yīng)分析變量的定值及引用關(guān)系,這種關(guān)系稱為 引用-定值鏈,或稱為 引用-定值集.定義: 若變量 A 在四元式 d 定值,并存在一條通路到達(dá)四元式 u ,且 該通路上沒有 A 的其它定值,則稱 A 在 d 的定值到達(dá) u .定義:如在 u 處引用了變量 A,則凡能到達(dá) u 的 A 的所有定值點,構(gòu)成了 A 在 u 處的引用-定值集 ,記為: udA. 下面介紹如何求 ud集.1 到達(dá)-定值方程 31

21、首先定義四個基本集合:INB : 代表到達(dá)基本塊 B 入口點時的各變量的所有定值點集;OUTB:代表到達(dá)基本塊 B 出口點時的各變量的所有定值點集;G ENB:表示 B 中所定值的且到達(dá) B 之后的定值點集;KILLB: 表示屬于 B 外的定值點,而這些定值點所定值的變量在 B中又被重新定值 這幾個集合滿足如下方程: OUTB=(INB - KILL(B) G ENB INB = OUTp1 OUTp2 . OUTpk p1 , p2. pk 為B的前趨結(jié)點.該方程即為到達(dá)-定值方程,求解該方程,得到INB . 322求 ud A 算法如下: 若 B 中,變量 A 的引用點 u 之前有 A 的

22、定值點 d,且到達(dá) u ,則 ud A = d ; 否則 ud A = di | di INB 且 di為A的定值點. 這樣,可以求出每個變量在引用點 u 的定值狀況. 33四 循環(huán)的幾種基本優(yōu)化 下面介紹三種循環(huán)優(yōu)化: 代碼外提,強度削弱,刪除歸納變量.代碼外提定義: 對于循環(huán)中的語句 A:= B op C, 若 B 及 C 均為常量,或者 為 循環(huán)中未改變的變量, 那么每次循環(huán) A的值都一樣,稱A:= B op C 為不變運算. 對于不變運算,有可能把 A:= B op C 放到循環(huán)前,具體做法是: a) 建立一前置結(jié)點; b) 循環(huán)入口結(jié)點(唯一的) 為前置結(jié)點的唯一后繼; c) 循環(huán)外

23、流向入口結(jié)點的有向邊,改為流向前置結(jié)點; d) 把循環(huán)中可以外提的不變運算放在前置結(jié)點中.見下圖: 34循環(huán)入口結(jié)點循環(huán)外流向前置結(jié)點前置結(jié)點循環(huán)入口結(jié)點 下面討論兩個問題:(1)哪些是循環(huán)中的不變運算?(2) 循環(huán)中的哪些不變運算可以放到前置結(jié)點中?循環(huán)外流向入口結(jié)點循環(huán)內(nèi)結(jié)點循環(huán)內(nèi)結(jié)點改為 351 不變運算的確定算法 (1) 察看循環(huán)中的每條四元式,若每個運算對象或為常量,或定值點在循環(huán)外的變量,則標(biāo)記為不變運算; (2) 察看尚未標(biāo)記為不變運算的四元式,若每個運算對象或為常量,或定值點在循環(huán)外的變量,或在循環(huán)內(nèi)具有唯一定值點的變量且該定值點已經(jīng)標(biāo)記為不變運算,則標(biāo)記為不變運算; (3)重

24、復(fù) (2),直到不產(chǎn)生新的不變運算. 362 代碼外提算法 (1) 對循環(huán)中每一不變運算 (S) A:=B op C (包括 A:= op C 或 A:=B), 檢查是否滿足如下條件之一 : a) S所在的結(jié)點是循環(huán)所有出口結(jié)點的必經(jīng)結(jié)點, 且 S為變量A 在循環(huán)中唯一 定值點, 且 A 的定值點 S 能到達(dá)循環(huán)中所有 A 的引用點; b) S為 變量 A 在循環(huán)中唯一 定值點, 且 A 的定值點 S 能到達(dá)循環(huán)中所有 A 的引用點, 且 A 在循環(huán)之后不再引用. (2) 把循環(huán)中滿足條件 a) 或 b) 的不變運算移至前置結(jié)點中, 若運算對象 B 或 C 是在循環(huán)中定值, 則只有當(dāng) B 或

25、C 的定值點四元式已放入前置結(jié)點中后,才可以把 S 外提. 37強度削弱 強度削弱是指循環(huán)中,把執(zhí)行時間較長的運算轉(zhuǎn)換為執(zhí)行時間較短的運算. 下面僅討論乘法運算轉(zhuǎn)換為加法運算.( 注:并非每個乘運算都可以進(jìn)行強度削弱)定義: 若循環(huán)中對 B 只有唯一的遞歸賦值 B:=B+C 且 C 為循環(huán)不變量,則稱 B 為循環(huán)的基本歸納變量.定義: 若 B 為基本歸納變量,而 A 在循環(huán)中的定值,可以化歸為 B 的線性函數(shù): A:=C1*B+C2 (C1 , C2為循環(huán)不變量 ) 則稱 A 為歸納變量,并稱 A與 B同族. 38一般而言,若循環(huán)中有遞歸賦值 B:=B+C (B 每次循環(huán)遞增常量C) 而 循環(huán)

26、中對 A 的賦值為 B 的線性函數(shù) A :=C1*B+C2 (C1 , C2為常數(shù) ) 那么,循環(huán)中A :=C1*B+C2的乘運算可轉(zhuǎn)換為加運算,具體做法如下:在前置結(jié)點中添加: A :=C1*B+C2 令 C = C1 *C原A :=C1*B+C2 改為: A:=A在 B:=B+C 之后增加: A:=A+C 39示例: 根據(jù)定義 I 為基本歸納變量; T2,T6 為與 I 同族的歸納變量; T3,T7 可轉(zhuǎn)化為: T3:= 10*I +T1 ( T1為循環(huán)不變量) T7:= 10*I +T5 ( T5為循環(huán)不變量) 也為 與 I 同族的歸納變量; 下面是對 T2 進(jìn)行強度削弱的示例: (1)

27、 I:=1(2) T1:=2*J(3) T4:=addr(A)-11(4) T5:= 2*J(5) T8:=addr(A)-11(7) T2:=10*I(8) T3:=T2+T1(9) T6:= 10*I(10) T7:=T6+T5(11) T9:=T8T7(12) T4T3:=T9+1(13) I:=I+1(14) goto (6)(6) if I10 goto(15) 40基本歸納變量: I:=I+1 (C=1)T2 與 I 同族 : T2:=10*I+0 (C1=10,C2=0 )在前置結(jié)點中添加: T2 :=10*I令 C = 10原A :=C1*B+C2 改為: T2:=T2在 I:=I+1 之后增加: T2:=T2+10同理,T6,T3,T7 也一樣處理. 41刪除基本歸納變量 具體做法如下: 若基本歸納變量 B 在循環(huán)出口之后不再引用,且在循環(huán)中除B:=B+C 處被引用外,只在型如 if B rop Y goto (s) 中被引用,則 (1) 選一與B 同族的歸納變量 M , M與 B 有如下線性關(guān)系: M=C1*B+C2(2)建立一臨時變量 R,在前置結(jié)點中增加 R:=C1*Y+C2(3)用if M rop R goto (s) 替換 if B rop Y goto (s) (4)刪除循環(huán)中四元式 B:=B+C 42本章習(xí)題 P168 4. 9. 43