1、編譯的過程：編譯的過程：11.1 優(yōu)化技術(shù)簡(jiǎn)介優(yōu)化技術(shù)簡(jiǎn)介 優(yōu)化優(yōu)化：對(duì)程序進(jìn)行各種：對(duì)程序進(jìn)行各種等價(jià)等價(jià)變換，使得從變換后的程變換，使得從變換后的程序出發(fā)，能生成更序出發(fā)，能生成更有效有效的目標(biāo)代碼。的目標(biāo)代碼。等價(jià)等價(jià)：指不改變程序的運(yùn)行結(jié)果。：指不改變程序的運(yùn)行結(jié)果。有效有效：指目標(biāo)代碼運(yùn)行時(shí)間短，占用的存儲(chǔ)空間小。：指目標(biāo)代碼運(yùn)行時(shí)間短，占用的存儲(chǔ)空間小。注：和以前學(xué)習(xí)的算法優(yōu)化的異同注：和以前學(xué)習(xí)的算法優(yōu)化的異同11.1 優(yōu)化技術(shù)簡(jiǎn)介優(yōu)化技術(shù)簡(jiǎn)介 依據(jù)優(yōu)化所涉及的程序范圍，可分為：依據(jù)優(yōu)化所涉及的程序范圍，可分為：局部優(yōu)化局部優(yōu)化： 只有一個(gè)入口、一個(gè)出口的基本程序塊上進(jìn)行只有一個(gè)

2、入口、一個(gè)出口的基本程序塊上進(jìn)行優(yōu)化優(yōu)化循環(huán)優(yōu)化循環(huán)優(yōu)化： 對(duì)循環(huán)中的代碼進(jìn)行優(yōu)化對(duì)循環(huán)中的代碼進(jìn)行優(yōu)化全局優(yōu)化全局優(yōu)化： 在整個(gè)程序范圍內(nèi)進(jìn)行的優(yōu)化在整個(gè)程序范圍內(nèi)進(jìn)行的優(yōu)化11.1 優(yōu)化技術(shù)簡(jiǎn)介優(yōu)化技術(shù)簡(jiǎn)介 優(yōu)化的種類：優(yōu)化的種類：刪除多余運(yùn)算刪除多余運(yùn)算( (或稱刪除公用子表達(dá)式或稱刪除公用子表達(dá)式) )代碼外提代碼外提強(qiáng)度消弱強(qiáng)度消弱變換循環(huán)控制條件變換循環(huán)控制條件合并已知量合并已知量( (編譯時(shí)能夠確定的值編譯時(shí)能夠確定的值) )復(fù)寫傳播復(fù)寫傳播刪除無用賦值刪除無用賦值有程序段如下：有程序段如下：數(shù)組下標(biāo)是從數(shù)組下標(biāo)是從1開始：開始：P:=0for I:=1 to 20 do P:=

3、P+AI*BI經(jīng)過編譯后得到的中間經(jīng)過編譯后得到的中間代碼如右圖所示（假設(shè)代碼如右圖所示（假設(shè)每個(gè)數(shù)據(jù)元素占每個(gè)數(shù)據(jù)元素占4個(gè)個(gè)字節(jié)）：字節(jié)）：(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(4)T2:=addr(A)-4(5)T3:=T2T1(6)T4:=4*I(7)T5:=addr(B)-4(8)T6:=T5T4

4、(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(4)T2:=addr(A)-4(5)T3:=T2T1(6)T4:=T1(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)刪除多刪除多余運(yùn)算余運(yùn)算(1)P:=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*

5、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(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(3)T1:=4*I(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(

6、11)I:=I+1(12)if I=20 goto(3)強(qiáng)度強(qiáng)度消弱消弱(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(3)T1:=4*I(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(11)

7、I:=I+1(3)T1:=T1+4(12)if I=20 goto(5)變換循變換循環(huán)控制環(huán)控制條件條件(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 T1=80 goto(5)(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*

8、T6(10)P:=P+T7(11)I:=I+1(3)T1:=T1+4(12)if T1=80 goto(5)合并已知合并已知量和復(fù)寫量和復(fù)寫傳播傳播(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(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4(5)T3:=T2T1

9、(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)-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) halt(1) read (C)(2) A:= 0(3) B:= 1(4) L1: A:=A + B(

10、5) if B= C goto L2(6) B:=B+1(7) goto L1(8) L2: write (A)(9) halt基本塊的變換基本塊的變換 刪除公共子表達(dá)式刪除公共子表達(dá)式 刪除無用代碼刪除無用代碼 合并已知量合并已知量 重新命名臨時(shí)變量重新命名臨時(shí)變量 變換語句次序變換語句次序 合并已知量合并已知量 T T1 1:=2:=2 T T2 2:=4:=4* *T T1 1變換成變換成T T2 2:=8:=8 臨時(shí)變量改名臨時(shí)變量改名 T:=b+cT:=b+c其中其中T T是一個(gè)臨時(shí)變量名。把這個(gè)語句改成：是一個(gè)臨時(shí)變量名。把這個(gè)語句改成： S:=b+cS:=b+c 交換語句的位置交

11、換語句的位置 T1:=b+c T2:=x+y 代數(shù)變換代數(shù)變換 x:=x+0或或 x:=x*1 x:=y*2變換成變換成x:=y*y 自學(xué)自學(xué) 基本塊的有向圖（基本塊的有向圖（Directed Acyclic Graph,DAG）表示與應(yīng)用）表示與應(yīng)用11.3 控制流分析和循環(huán)優(yōu)化控制流分析和循環(huán)優(yōu)化 在一個(gè)程序流程中，循環(huán)是必不可少的一種控制結(jié)構(gòu)。在一個(gè)程序流程中，循環(huán)是必不可少的一種控制結(jié)構(gòu)。 循環(huán)中的代碼要反復(fù)執(zhí)行，因此為了提高目標(biāo)代碼的循環(huán)中的代碼要反復(fù)執(zhí)行，因此為了提高目標(biāo)代碼的效率必須著重考慮循環(huán)的優(yōu)化代碼。效率必須著重考慮循環(huán)的優(yōu)化代碼。 如何找出程序中的循環(huán)如何找出程序中的循環(huán)

12、 對(duì)程序中的控制流程進(jìn)行分析，本章采用控制流程對(duì)程序中的控制流程進(jìn)行分析，本章采用控制流程圖。圖。11.3.1 程序流程圖程序流程圖 每個(gè)流圖以基本塊為每個(gè)流圖以基本塊為結(jié)點(diǎn)結(jié)點(diǎn)。如果一個(gè)結(jié)點(diǎn)的基本塊的。如果一個(gè)結(jié)點(diǎn)的基本塊的入口語句是程序的第一條語句，則稱此結(jié)點(diǎn)為入口語句是程序的第一條語句，則稱此結(jié)點(diǎn)為首結(jié)點(diǎn)首結(jié)點(diǎn)。 如果在某個(gè)執(zhí)行順序中，基本塊如果在某個(gè)執(zhí)行順序中，基本塊B2緊接在基本塊緊接在基本塊B1之之后執(zhí)行，則從后執(zhí)行，則從B1到到B2有一條有向邊。有一條有向邊。(1)read X(2) read Y(3) R:=X mod Y(4) if R=0 goto (8)(5) X:=Y(

13、6) Y:=R(7) goto (3)(8) write Y(9) halt(8) write Y(9) halt(5) X:=Y(6) Y:=R(7) goto (3)(3) R:=X mod Y(4) if R=0 goto (8)(1) read X(2) read YB1B2B3B4程序流程圖如下：程序流程圖如下：如果在某個(gè)執(zhí)行順序中，如果在某個(gè)執(zhí)行順序中，基本塊基本塊B2緊接在基本塊緊接在基本塊B1之后執(zhí)行，則從之后執(zhí)行，則從B1到到B2有有一條有向邊。一條有向邊。11.3.2 循環(huán)的查找循環(huán)的查找n 分析程序流圖中結(jié)點(diǎn)間的關(guān)系分析程序流圖中結(jié)點(diǎn)間的關(guān)系m DOM n 定義定義 在程

14、序流圖中在程序流圖中,對(duì)任意兩個(gè)結(jié)點(diǎn)對(duì)任意兩個(gè)結(jié)點(diǎn)m和和n,如果從如果從流圖的首結(jié)點(diǎn)出發(fā)流圖的首結(jié)點(diǎn)出發(fā),到達(dá)到達(dá)n的任意通路都要經(jīng)過的任意通路都要經(jīng)過m,則稱則稱m是是n的必經(jīng)結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn),記為記為m DOM n ( a,a DOM a)集集 定義定義 結(jié)點(diǎn)結(jié)點(diǎn)n的所有的所有的集合的集合,稱為結(jié)點(diǎn)稱為結(jié)點(diǎn)n的必的必經(jīng)結(jié)點(diǎn)集經(jīng)結(jié)點(diǎn)集,記為記為D(n).例例 : 6 73 4 1 2 3 5 7 6 1 2 1 2 1 2 1 必經(jīng)結(jié)點(diǎn)集必經(jīng)結(jié)點(diǎn)集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 3回邊

15、回邊： 假設(shè)假設(shè)ab是流圖中的一條有向邊，如果是流圖中的一條有向邊，如果b DOM a，則，則ab是流圖是流圖中的一條中的一條回邊。回邊。 對(duì)于一已知流圖，只要求出各結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)集，就可以求出對(duì)于一已知流圖，只要求出各結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)集，就可以求出流圖中所有的回邊。流圖中所有的回邊。必經(jīng)結(jié)點(diǎn)集必經(jīng)結(jié)點(diǎn)集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 6 73 4 1 2 3 5 7 6 1 2 1 2 1 2 1 3回邊回邊 4 2 66 7 4 循環(huán)：循環(huán)： 有向邊有向邊nd是回邊，組成的循環(huán)是由結(jié)

16、點(diǎn)是回邊，組成的循環(huán)是由結(jié)點(diǎn)d、節(jié)點(diǎn)、節(jié)點(diǎn)n以以及有通路到達(dá)及有通路到達(dá)n而該通路不經(jīng)過而該通路不經(jīng)過d的所有節(jié)點(diǎn)組成，并的所有節(jié)點(diǎn)組成，并且且d是該循環(huán)的唯一入口節(jié)點(diǎn)。是該循環(huán)的唯一入口節(jié)點(diǎn)?；剡吇剡?66：該回邊組成的循環(huán)：該回邊組成的循環(huán)所包含的節(jié)點(diǎn)為所包含的節(jié)點(diǎn)為6回邊回邊7 4：該回邊組成的循環(huán)：該回邊組成的循環(huán)所包含的節(jié)點(diǎn)為所包含的節(jié)點(diǎn)為4,5,6,7回邊回邊4 2：該回邊組成的循環(huán)：該回邊組成的循環(huán)所包含的節(jié)點(diǎn)為所包含的節(jié)點(diǎn)為2,3,4,5,6,7 6 73 4 1 2 3 5 7 6 1 2 1 2 1 2 1 311.3.3 循環(huán)優(yōu)化循環(huán)優(yōu)化 1.代碼外提代碼外提 2.強(qiáng)度消

17、弱與刪除歸納變量強(qiáng)度消弱與刪除歸納變量(1)I:=1(2) if XY goto B3B1B2(3) I:=2(4) X:=X+1(5) Y:=Y-1(6) if Y=20 goto B5(7) J:=IB3B4B5 X=30, Y=25 J=1, I=11. 代碼外提代碼外提找循環(huán)不變運(yùn)算找循環(huán)不變運(yùn)算循環(huán)：循環(huán)：B2，B3，B4循環(huán)不變運(yùn)算是否循環(huán)不變運(yùn)算是否都可以提到循環(huán)外面？都可以提到循環(huán)外面？(1)I:=1(2) if XY goto B3B1B2(3) I:=2(4) X:=X+1(5) Y:=Y-1(6) if Y=20 goto B5(7) J:=IB3B4B5 X=25, Y

18、=30 J=2, I=2 代碼外提條件代碼外提條件:不變運(yùn)算不變運(yùn)算A所在的結(jié)點(diǎn)是循環(huán)所有出口結(jié)點(diǎn)所在的結(jié)點(diǎn)是循環(huán)所有出口結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn).(1)I:=1(2) I:=3(2) if XY goto B3B1B2(3) I:=2(4) X:=X+1(5) Y:=Y-1(6) if Y=20 goto B5(7) J:=IB3B4B5 考慮考慮: B2 B3 B4 B2 B4 B5 I=3, J=3不變運(yùn)算不變運(yùn)算A所在的結(jié)點(diǎn)是循環(huán)所有出口結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)一定能外提？所在的結(jié)點(diǎn)是循環(huán)所有出口結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)一定能外提？ 考慮考慮: B2 B3 B4 B5 I=2, J=2 代碼外提條件代碼外

19、提條件: A在循環(huán)中其他地方未再定值在循環(huán)中其他地方未再定值,才能把循環(huán)才能把循環(huán)不變運(yùn)算不變運(yùn)算A:=B op C外提外提; (1)I:=1(2) I:=3(2) if XY goto B3B1B2(3) I:=2(4) X:=X+1(5) Y:=Y-1(6) if Y=20 goto B5(7) J:=IB3B4B5 代碼外提條件代碼外提條件: 不變運(yùn)算不變運(yùn)算A所在的結(jié)點(diǎn)是循環(huán)所有出口結(jié)點(diǎn)的必經(jīng)所在的結(jié)點(diǎn)是循環(huán)所有出口結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)，結(jié)點(diǎn)， 并且并且A在循環(huán)中其他地方未再定值在循環(huán)中其他地方未再定值,才能把才能把循環(huán)不變運(yùn)算循環(huán)不變運(yùn)算A:=B op C外提外提; 或或 不變運(yùn)算不變運(yùn)算A在循環(huán)中其他地方未再定值，并且出了在循環(huán)中其他地方未再定值，并且出了A所屬的循環(huán)后，不在引用所屬的循環(huán)后，不在引用A(1)I:=1(2) I:=3(3) if XY goto B3B1B2(4) X:=X+1(5) Y:=Y-1(6) if Y=20 goto B5(7) J:=IB3B4B5(1)I:=1(3) if XY goto B3B1B2(4) X:=X+1(5)