譯原理課件第8章-代碼優(yōu)化

1、第八章 代碼優(yōu)化8.1 什么是代碼優(yōu)化8.2 局部優(yōu)化8.3 循環(huán)優(yōu)化8.4 數(shù)據(jù)流分析22022/7/318.1 什么是代碼優(yōu)化1、優(yōu)化： 對程序進行各種等價變換，使變換后的程序能生成更有效的目標代碼。 優(yōu)化可在編譯的任何階段進行，但最主要的一類優(yōu)化是對中間代碼進行優(yōu)化。2、常見的優(yōu)化方式 刪除多余運算（又稱刪除公共子表達式） 代碼外提：循環(huán)體中不變的運算提到循環(huán)體外 強度削弱：把乘法變成加法32022/7/31 變換循環(huán)控制條件：目的是刪除那些純粹為控制循環(huán)而設(shè)立的語句，因此又稱刪除歸納變量。 合并已知量：對于那些編譯時便可靜態(tài)確定的運算結(jié)果事先運算出來，不必等到運行程序時再執(zhí)行。 復寫傳

2、播：某些變量的值并未被改變，便賦給其他變量，則可直接引用原值本身。 刪除無用賦值：有些變量在賦值后并未引用，卻又被重新賦值了，稱為無用賦值（前面的賦值）42022/7/313、優(yōu)化分類按階段分: 與機器無關(guān)的優(yōu)化-對中間代碼進行 依賴于機器的優(yōu)化-對目標代碼進行根據(jù)優(yōu)化所涉及的程序范圍分成: (1)局部優(yōu)化:在程序基本塊內(nèi)進行的優(yōu)化。 (2)循環(huán)優(yōu)化:在程序循環(huán)體內(nèi)進行的優(yōu)化。 (3)全局優(yōu)化:在整個程序范圍內(nèi)進行的優(yōu)化。優(yōu)化工作 數(shù)據(jù)流分析(control-flow analysis) 控制流分析(data-flow analysis) 變換(transformations)52022/7/

3、314、優(yōu)化技術(shù)簡介 1.刪除多余運算 2.循環(huán)不變代碼外提 3.強度削弱 4.變換循環(huán)控制條件 5.合并已知量與復寫傳播 6.刪除無用賦值例： P:=0 for I:=1 to 20 do P:=P+AI*BI62022/7/31(1)P:=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)P:=P+T7(11)I:=I+1(12)if I=20 goto(3)(1)P:=0(2)I:=1(3)T1:=4*I(5)T3:=T2T1(8)T6:=T5

4、T4(9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)if I=20 goto(3)(4)T2:=addr(A)-4(7)T5:=addr(B)-4(6)T4:=T172022/7/31(1)P:=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)P:=P+T7(11)I:=I+1(12)if I=20 goto(3)(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(5)T3:=T2T

5、1(6)T4:=T1(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)if I=20 goto(5)(3)T1:=4*I(3)T1:=T1+482022/7/31(1)P:=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)P:=P+T7(11)I:=I+1(3)T1:=T1+4(12)if I=20 goto(5)(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4

6、(5)T3:=T2T1(6)T4:=T1(8)T6:=T5 (9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3)T1:=T1+4(12)if =80 goto(5)(3)T1:=4T1T192022/7/31(1)P:=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)P:=P+T7(11)I:=I+1(3)T1:=T1+4(12)if T1=80 goto(5)(1)P:=0(4)T2:=addr(A)-4(7)T5:=addr(B)

7、-4(3)T1:=4(5)T3:=T2T1(8)T6:=T5T1(9)T7:=T3*T6(10)P:=P+T7(3)T1:=T1+4(12)if T1= C goto L2 (6) B:=B+1 (7) goto L1 (8) L2: write (A) (9) halt132022/7/31142022/7/31基本塊的DAG表示及其應(yīng)用DAG Directed Acyclic Graph 無環(huán)路有向圖基本塊的DAG是在結(jié)點上帶有標記的DAG 葉結(jié)點 獨特的標識符(名字,常數(shù))標記 內(nèi)部結(jié)點 運算符號標記 各個結(jié)點 附加標識符標記152022/7/31用DAG進行基本塊的優(yōu)化四元式DAG結(jié)點

8、0型：A:=B(:=,B,A) n1 A B1型: A:=op B(op,B, ,A) n2 A op n1 B2型: A:=B op C(op, B, C,A) n3 Aop n1 n2B Cn1n2n1n3n1n2162022/7/31172022/7/31182022/7/31192022/7/31例：202022/7/31212022/7/31222022/7/31232022/7/31242022/7/31252022/7/31262022/7/31272022/7/31282022/7/31292022/7/31控制流程圖（流圖）：具有唯一首結(jié)點的有向圖G=（N，E，n0） N：結(jié)

9、點集 基本塊集 E：有向邊集 n0：首結(jié)點 包含程序第一個 語句的基本塊8.3 循環(huán)優(yōu)化302022/7/312022/7/31322022/7/31332022/7/31342022/7/31分析程序流圖中結(jié)點間的關(guān)系m DOM n 定義 在程序流圖中,對任意兩個結(jié)點m和n,如果從流圖的首結(jié)點出發(fā),到達n的任意通路都要經(jīng)過m,則稱m是n的必經(jīng)結(jié)點,記為m DOM n (a,a MOD a)必經(jīng)結(jié)點集 定義 結(jié)點n的所有必經(jīng)結(jié)點的集合,稱為結(jié)點n的必經(jīng)結(jié)點集,記為D(n).352022/7/31例: 6 73 4 1 2 3 5 7 6 1 2 1 2 1 2 1必經(jīng)結(jié)點 必經(jīng)結(jié)點集D(1)=

10、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 3362022/7/31循環(huán)的查找循環(huán)的查找算法回邊：假設(shè)ab是流圖中的一條有向邊，如果b DOM a，則稱a b是流圖中的一條回邊。有向邊nd是回邊，組成的循環(huán)是由結(jié)點d，結(jié)點n以及有通路到達n而該通路不經(jīng)過 d的所有結(jié)點組成，并且d是該循環(huán)的唯一入口結(jié)點。循環(huán)(結(jié)點序列的性質(zhì))1.強連通的(任意兩結(jié)點間,必有一條通路,且該通路上各結(jié)點都屬于該結(jié)點序列)2.它們中間有且只有一個是入口結(jié)點.372022/7/31 8.4 數(shù)據(jù)流分析1.活躍變量數(shù)據(jù)流方程2.到達-

11、定值數(shù)據(jù)流方程3.討論 數(shù)據(jù)流問題分類 路徑 數(shù)據(jù)流方程解不唯一382022/7/31活躍變量的數(shù)據(jù)流分析所謂活躍變量就是它的當前值還將被引用（在賦予一個新值之前）。在全局范圍來分析的話，一個變量是活躍的，如果存在一條路徑使得該變量被重新定值之前它的當前值還要被引用。通過全局活躍變量分析，識別出其當前值不再活躍（即，它的值已經(jīng)死了）的那些變量。死變量的值在基本塊的出口處不需要保存。392022/7/31令B為一個基本塊，定義LiveIn(B)為在基本塊B入口處為活躍的變量的集合。定義LiveOut(B)為基本塊B的出口處的活躍變量的集合。LiveIn和LiveOut并不是相互獨立的，令S（B）

12、為流圖中基本塊B的后繼的集合，則有 LiveOut(B)=LiveIn(i) is(B) 如果基本塊沒有后繼，則其LiveOut為空令LiveUse(B)為B中被定值之前要引用變量的集合。這個集合由基本塊B中的語句唯一確定。容易看出，如果vLiveUse(B)，則vLiveIn(B)； 即LiveIn(B) LiveUse(B)。令Def(B)為在B中定值的變量集合。如果一個變量在基本塊B的出口處為活躍的且vDef(B)，則它在B的入口處也是活躍的，即： LiveIn(B) LiveOut(B)- Def(B)因此有：LiveIn(B)= LiveUse(B)(LiveOut(B)- Def(

13、B)即：一個變量在基本塊入口處為活躍的，則一定有：或者它在基本塊的LiveUse集中，或者它在基本塊的出口處為活躍的且在基本塊中沒有重新定值 402022/7/31a:=1;if a=b then b:=1 else c:=1endif;d:=a+ba:=1if a=b goto B2b:=1c:=1d:=a+bB1B2B3B4412022/7/31提取Def和LiveUse集合基本塊DefLiveUseB1abB2bB3cB4da,ba:=1if a=b goto B2b:=1c:=1d:=a+bB1B2B3B4422022/7/31從最后一個基本塊開始由后往前計算，可以得到一定的解 Liv

14、eIn(B)= LiveUse(B)(LiveOut(B)- Def(B) LiveOut(B)=LiveIn(i) is(B)LiveOut(B4)=，因此：LiveIn(B4)= LiveUse(B4)= a,b-d現(xiàn)在LiveOut(B2)=LiveIn (B4)=a,b -dLiveOut(B3)=LiveIn (B4)= a,b -dLiveIn(B2) = LiveOut(B2)- Def(B2)= a,b- b -d = a -dLiveIn(B3) = LiveOut(B3)- Def(B3)= a,b c -d = a,b c -dLiveOut(B1) = LiveIn (

15、B2) LiveIn (B3)= a a,b -d = a,b -d c 最后LiveIn(B1)=LiveUse(B1)(LiveOut(B1)-Def(B1) = b(a,b c -d a) = b -d c a:=1if a=b goto B2b:=1c:=1d:=a+bB1B2B3B4432022/7/31分析程序中所有變量的定值和引用之間的關(guān)系到達-定值數(shù)據(jù)流方程OUTB=(INB-KILLB)GENBINB= OUTp pPBPB:B的所有前驅(qū)基本塊GENB:B中定值并到達B出口之后的所有定值點集.KILLB:B之外的那些定值點集,其定值的變量在B中 又重新定值.INB:到B入口之

16、前(緊)的各變量的所有定值點集OUTB:到達B出口之后(緊)各變量的所有定值點集.442022/7/31452022/7/31GEN位向量KILLB1d1,d211000000011100B2d300100001000000B3d400010000100100B4d500001000101000B5 00000000000000INBOUTBB101111001100000B211111000111100B301111000011000B400110000010100B500111000011100462022/7/31472022/7/31482022/7/31 入口結(jié)點 循環(huán)L 前置結(jié)點

17、入口結(jié)點 循環(huán)L 492022/7/31502022/7/3112345512022/7/31522022/7/31 B1 B2 B3 B4 B5(1)I:=1I:=3;(2)if xy goto(3)(3)I:=2(4)x:=x+1(5)y:=y-1(6)if y=20 goto B2(7)J:=I532022/7/31 B1 B2 B3 B4 B5(1)I:=1(2)if xy goto(3)(3)I:=2(4)x:=x+1(5)k:=I;y:=y-1(6)if y=20 goto B2(7)J:=I542022/7/31當把循環(huán)中的不變運算s:A:=B op C外提時注意：（2） 要求循

18、環(huán)中其它地方不再有A的定值點。（3） 要求循環(huán)中A的所有引用點都是而且僅僅是這個定值所能達到的（1）要求s所在結(jié)點是循環(huán)的所有出口結(jié)點的必經(jīng)結(jié)點（4）要求A在離開循環(huán)之后不再是活躍的552022/7/31中南大學軟件學院 陳志剛數(shù)據(jù)流問題的討論合流問題向前流（forward-flow)(信息流的方向與控制流是一致的)和向后流（backward flow）對每個基本塊有一個IN集合和一個Out集合,在同一基本塊中，In和Out集合的關(guān)系對于向前流問題：Out (B) = Used (B) (In(B) Killed (B)對于向后流問題：In (B) = Used (B) (Out (B) Killed (B)作為一個邊界條件，向前流問題中的起始基本塊的In和向后流問題中最后一個基本塊的Out集合必須指明，通常，這些邊界條件集或者為空，或者包含所有可能的值，因問題而定。如：到達-定值數(shù)據(jù)流方程 OUTB=(INB-KILLB)GENB活躍變量數(shù)據(jù)流方程LiveIn(B)=LiveUse(B)(LiveOut(B)-Def(B)562022/7/31數(shù)據(jù)流問題的討論路徑問題任意路徑數(shù)據(jù)流分析討論的數(shù)據(jù)流假定這么一個性質(zhì)，即某條路