第11章 代碼優(yōu)化

第11章代碼優(yōu)化11．1

什么是代碼優(yōu)化11．2

局部優(yōu)化11．3

控制流程分析和循環(huán)

何謂代碼優(yōu)化：

所謂優(yōu)化，實質(zhì)上是對代碼進行等價變換，使得變換后的代碼運行結(jié)果與變換前代碼運行結(jié)果相同，而運行速度加大或占用存儲空間少，或兩者都有。一般，優(yōu)化工作階段可在中間代碼生成之后和（或）目標代碼生成之后進行，如圖所示：編譯程序的優(yōu)化工作的宗旨：生成較好性能的目標代碼。為此，編譯程序需要對代碼（中間代碼或目標代碼）進行各種方式的變換，變換必須保證：等價----經(jīng)優(yōu)化工作變換后的代碼運行結(jié)果應(yīng)與原來程序運行結(jié)果一樣。優(yōu)化分類根據(jù)優(yōu)化所涉及的程序范圍分成:(1)局部優(yōu)化:(基本塊)(2)循環(huán)優(yōu)化:對循環(huán)中的代碼進行優(yōu)化(3)全局優(yōu)化:大范圍的優(yōu)化按階段分:與機器無關(guān)的優(yōu)化---對中間代碼進行依賴于機器的優(yōu)化--對目標代碼進行常用的優(yōu)化技術(shù)有：刪除多余運算，循環(huán)不變代碼外提，強度削弱，變換循環(huán)控制條件，合并已知量，復(fù)寫傳播與刪除無用賦值。1、刪除多余運算如果有表達式e1和e2，且它們的值始終相同，則e2的計算部分可以省略，只要用e1的值即可。例：A:=B*D+1;E:=B*D-1;G:=B*D+2;

其中三個B*D的子表達式始終一致，因此，可以優(yōu)化為：

T1:=B*D;A:=T1+1;E:=T1-1;G:=T1+2;例：A:=B*D;B:=B*D;C:=B*D;

三個式子中的B*D形式相同，但第三個式子中的B*D與前兩個式中的B*D的值不同，因此，第三個B*D不能省?？蓛?yōu)化：T1:=B*D;A:=T1;B:=T1;C:=B*D;注意：只有形式相同還不行，必須值也要相同，即形式相同并不能保證值相同。例:P:=0;forI:=1to20doP:=P+A[I]*B[I];將它翻譯為四元式的形式假定數(shù)組的每個元素占4個字節(jié)，add(A)是A數(shù)組的基址，W是元素的字節(jié)寬度，low為數(shù)組的下界，一維數(shù)組A[i]的地址：add(A)+(i-low)*W=add(A)+(i-1)*4=add(A)-4+4*i(1)P:=0(2)I:=1(3)T1:=4*I(4)T2:=addr(A)-4(5)T3:=T2[T1](6)T4:=4*I(7)T5:=addr(B)-4(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)ifI<=20goto(3)P:=0;forI:=1to20doP:=P+A[I]*B[I];代碼外提(4),(7)提到循環(huán)外面。刪除公共子表達式見兩圖中的（3）（6）變化。2、代碼外提（循環(huán)外提）例：A:=B*C1000次并且B與C是不變量則可以把B*C提到循環(huán)的外面，這就減少了999次運算。再見上頁圖T1:=B*CA:=T11000次3、強度削弱把高強度的運算改為低強度的運算。如把乘法改為加法：a*2=2*a=a+a例fori:=1Step2untilndoBeginB:=i*k;End

其中K是不變量因此可以優(yōu)化為：

T1:=1*k;T2:=2*k;fori:=1Step2untilndobeginB:=T1;T1:=T1+T2;Endi=1時，B＝1*ki=3時，B＝3*ki=5時，B＝5*k即每次增加2*k(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*I(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)ifI<=20goto(3)(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)ifI<=20goto(5)(3)T1:=4*I(3‘)T1:=T1+4強度削弱4、變換循環(huán)條件如上例中，因為I與T1始終保持T1:=4*I的關(guān)系，將循環(huán)條件I≤20變成T1≤80，整個程序運行結(jié)果不變，這樣變化的好處是(11)號四元式便可以刪除。(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*I(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3’)T1:=T1+4(12)ifI<=20goto(5)(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3’)T1:=T1+4(12)if<=80goto(5)(3)T1:=4T1T1變換循環(huán)控制條件，合并已知量，復(fù)寫傳播5、合并已知量：例：a=10*5+6-b;tmp0=10;tmp1=5;tmp2=tmp0*tmp1;tmp3=6;tmp4=tmp2+tmp3;tmp5=tmp4-ba=tmp5;合并已知量后：tmp0=56;tmp1=tmp0-b;a=tmp1;(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*I(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3’)T1:=T1+4(12)ifI<=20goto(5)(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3’)T1:=T1+4(12)if<=80goto(5)(3)T1:=4T1T1合并已知量6、復(fù)寫傳播例1：tmp2=tmp1;tmp3=tmp2*tmp1;tmp4=tmp3;tmp5=tmp3*tmp2;c=tmp5+tmp4;優(yōu)化后變?yōu)椋簍mp3=tmp1*tmp1;tmp5=tmp3*tmp1;c=tmp5+tmp3;(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*I(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3’)T1:=T1+4(12)ifI<=20goto(5)(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3’)T1:=T1+4(12)if<=80goto(5)(3)T1:=4T1T1復(fù)寫傳播(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T1](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3’)T1:=T1+4(12)ifT1<=80goto(5)(1)P:=0(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4(5)T3:=T2[T1](8)T6:=T5[T1](9)T7:=T3*T6(10)P:=P+T7(3’)T1:=T1+4(12)ifT1<=80goto(5)刪除無用賦值(1)

read(C)(2)A:=0(3)B:=1(4)L1:A:=A+B(5)ifB>=CgotoL2(6)B:=B+1(7)gotoL1(8)L2:write(A)(9)halt(1)

read(C)(2)A:=0(3)B:=1(4)L1:A:=A+B(5)ifB>=CgotoL2(6)B:=B+1(7)gotoL1(8)L2:write(A)(9)halt程序流圖的構(gòu)造以基本塊為結(jié)點，以控制流為有向邊流圖Ｇ＝｛Ｎ，Ｅ，n0

｝Ｎ：基本塊集n0：含首語句的基本塊Ｅ：有向邊集合ABA的出口為轉(zhuǎn)移語句，轉(zhuǎn)向B的入口B緊跟A之后，且A的出口不是無條件轉(zhuǎn)移語句goto(s)或return(1)

read(C)(2)A:=0(3)B:=1(4)L1:A:=A+B(5)ifB>=CgotoL2(6)B:=B+1(7)gotoL1(8)L2:write(A)(9)halt例基本塊劃分和流圖i=m-1; j=n; v=a[n];while(1){ doi=i+1;while(a[i]<v); doj=j-1;while(a[j]>v); if(i>=j) break; x=a[i]; a[i]=a[j]; a[j]=x;}x=a[i]; a[i]=a[n]; a[n]=x;C語言數(shù)組a[i]的地址a+(i-low)*W三地址序列：(1)i:=m-1(2)j:=n(3)t1:=4*n;(4)v:=a[t1](5)i:=i+1(6)t2:=4*i;(7)t3:=a[t2];(8)ift3<vgoto(5)(9)j:=j-1(10)t4:=4*j;(11)t5:=a[t4];(12)ift5>vgoto(9)(13)ifi>=jgoto(23)(14)t6:=4*i(15)x:=a[t6](16)t7:=4*i(17)t8:=4*j(18)t9:=a[t8](19)a[t7]:=t9(20)t10:=4*j(21)a[t10]:=x(22)goto(5)(23)t11:=4*i(24)x:=a[t11](25)t12:=4*i(26)t13:=4*n(27)t14:=a[t13](28)a[t12]:=t14(29)t15:=4*n(30)a[t15]:=x程序流圖B1(1-4)B2(5-8)B3(9-12)B4(13)B5(14-22)B6(23-30)基本塊的DAG表示及其應(yīng)用DAGDirectedAcyclicGraph

無環(huán)路有向圖(P253)基本塊的DAG是在結(jié)點上帶有標記的DAG葉結(jié)點：無后繼的結(jié)點,以一標識符(名字,常數(shù))標記,表示該結(jié)點代表該變量或常數(shù)的值。如果葉子結(jié)點代表該變量A的地址，則addr(A)作為該結(jié)點的信息。內(nèi)部結(jié)點：即有后繼的結(jié)點，以運算符號標記表示該結(jié)點代表應(yīng)用該運算符對其后繼結(jié)點所表示的值進行運算的結(jié)果。各個結(jié)點：圖中各結(jié)點可能附加一個或多個標識符標記表示這些變量具有該結(jié)點表示的值四元式DAG結(jié)點(0)A:=B(:=,B,—,A)n1

AB(1):A:=opB(op,B,

—,A)

n2Aopn1B(2):A:=BopC(op,B,C,A)n3Aop

n1n2BCn1n2n1n3n1n2四元式與DAG結(jié)點：（3）A：=B[C]（=[]，B[C]，-，A）

（4）ifBropCgoto（s）（jrop，B，C，（s））

（5）D[C]：=B（[]=，B，-，D[C]）

（6）goto（s）（j，-，-，（s））

四元式序列G:T0:=3.14T0:=3.14T1:=2*T0T0:=3.14T0:=3.14T1:=2*T0T2:=R+rT0:=3.14T1:=2*T0T2:=R+rA:=T1*T2T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT3:=2*T0T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT3:=2*T0T4:=R+rT0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT3:=2*T0T4:=R+rT5:=T3*T4T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT3:=2*T0T4:=R+rT5:=T3*T4T6:=R-rT0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT3:=2*T0T4:=R+rT5:=T3*T4T6:=R-rB:=T5*T6G’:把G′和原基本塊G相比，可以看出：

1．G中的代碼（2）和（6）的已知量都已合并。

2．G中（5）的無用賦值已被刪除。

3．G中（3）和（7）的公共子表達式R+r只被計算一次，刪除了多余運算。

所以G′是G的優(yōu)化結(jié)果。G:(1)T0:=3.14(2)T1:=2*T0(3)T2:=R+r(4)A:=T1*T2(5)B:=A(6)T3:=2*T0(7)T4:=R+r(8)T5:=T3*T4(9)T6:=R-r(10)B:=T5*T6G′

(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

11.3控制流分析和循環(huán)優(yōu)化

因為循環(huán)中的代碼要反復(fù)執(zhí)行，因而為了提高目標代碼的效率必須著重考慮循環(huán)的代碼優(yōu)化。要進行循環(huán)優(yōu)化。首先必須找出程序中的循環(huán)，為找出程序中的循環(huán)，就需要對程序的控制流程進行分析。②它們中間有且只有一個是入口結(jié)點。所謂入口結(jié)點，是指序列中具有下述性質(zhì)的結(jié)點：

從序列外某結(jié)點，有一有向邊引到它，或者它就是程序流圖的首結(jié)點。在程序流圖中，我們稱具有下列性質(zhì)的結(jié)點序列稱為一個循環(huán)：

①它們是強連通的。也即，其中任意兩個結(jié)點之間，必有一條通路，如果序列只包含一個結(jié)點，則必有一有向邊從該結(jié)點引到其自身。

例如，圖中的程序流圖，根據(jù)定義:結(jié)點序列｛6｝，｛4，5，6，7｝以及｛2，3，4，5，6，7｝都是循環(huán)；而結(jié)點序列｛2，4｝，｛2，3，4｝，｛4，6，7｝以及｛4，5，7｝雖然都是強連通的，但因它們的入口結(jié)點不唯一，所以都不是上述意義下的循環(huán)。

必經(jīng)結(jié)點和必經(jīng)結(jié)點集的定義。在程序流圖中，對任意兩個結(jié)點m和n，如果從流圖的首結(jié)點出發(fā)，到達n的任一通路都要經(jīng)過m，則稱m是n的必經(jīng)結(jié)點，記為mDOMn。流圖中結(jié)點n的所有必經(jīng)結(jié)點的集合，稱為結(jié)點n的必經(jīng)結(jié)點集，記為D（n）。直接由定義和DOM的性質(zhì)，可以求得：

D(1)={1}

D(2)={1,2}

D(3)={1,2,3}

D(4)={1,2,4}

D(5)={1,2,4,5}

D(6)={1,2,4,6}

D(7)={1,2,4,7}它具有以下性質(zhì)：

1.自反性：

對流圖中任意結(jié)點a，有aDOMa。

2.傳遞性：

對流圖中任意結(jié)點a、b和c。若aDOMb，bDOMc,則有aDOMc。

3.反對稱性：

若aDOMb且bDOMa，則必有a＝b。

循環(huán)的查找循環(huán)的查找算法回邊：假設(shè)a→b是流圖中的一條有向邊，如果bDOMa，則稱a→b是流圖中的一條回邊。有向邊n→d是回邊，組成的循環(huán)是由結(jié)點d，結(jié)點n以及有通路到達n而該通路不經(jīng)過d的所有結(jié)點組成，并且d是該循環(huán)的唯一入口結(jié)點。例:

回邊6674(因為4是7的必經(jīng)結(jié)點)42(因為2是4的必經(jīng)結(jié)點)如圖所示求回邊和循環(huán)D(1)={1}

D(2)={1,2}

D(3)={1,2,3}

D(4)={1,2,4}

D(5)={1,2,4,5}

D(6)={1,2,4,6}

D(7)={1,2,4,7}假設(shè)a→b是流圖中的一條有向邊，如果bDOMa(b是a的必經(jīng)結(jié)點)，則稱a→b是流圖中的一條回邊。已知有向邊n→d是回邊，該循環(huán)就是由結(jié)點d、結(jié)點n以及有通路到達n而該通路不經(jīng)過d的所有結(jié)點組成，并且d是該循環(huán)的唯一入口結(jié)點。循環(huán){6}{4,5,6,7}{2,3,4,5,6,7}對圖中的流圖：

(1)求出流圖中各結(jié)點n的必經(jīng)結(jié)點集D(n)；

(2)求出流圖中的回邊；

(3)求出流圖中的循環(huán)。

解答：

（1）

D(1)={1}

D(2)={1,2}

D(3)={1,2,3}

D(4)={1,2,3,4}

D(5)={1,2,3,5}

D(6)={1,2,3,6}

D(7)={1,2,7}

D(8)={1,2,7,8}

(2)回邊72(3)循環(huán){2，3，4，5，6，7}

代碼外提：減少循環(huán)中代碼數(shù)目的一個重要辦法是代碼外提。前面已經(jīng)介紹了一個代碼外提的例子.這種變換把循環(huán)不變運算，即產(chǎn)生的結(jié)果獨立于循環(huán)執(zhí)行次數(shù)的表達式，放到循環(huán)的前面。這里，所討論的循環(huán)只存在一個入口。實行代碼外提時，在循環(huán)的入口結(jié)點前面建立一個新結(jié)點（基本塊），稱之為循環(huán)的前置結(jié)點。循環(huán)的前置結(jié)點以循環(huán)的入口結(jié)點為其唯一后繼，原來流圖中從循環(huán)外引到循環(huán)入口結(jié)點的有向邊，改成引到循環(huán)前置結(jié)點，如圖所示：

循環(huán)優(yōu)化循環(huán)優(yōu)化的三種重要技術(shù)是：代碼外提；刪除歸納變量和強度削弱。將循環(huán)不變運算移到循環(huán)外例11-2：程序優(yōu)化i=0;while(i<20){x=4*i;i++;y=z*6+x;}(3)x:=4*i(4)i:=i+1(5)t1:=z*6(6)y:=t1+x(7)goto(2)(4)x:=4*i(5)i:=i+1(6)y:=t1+x(7)goto(3)(1)i:=0(1)i:=0(2)t1:=z*6(2)ifi>=20goto(8)(3)ifi>=20goto(8)是否在任何情況下，都可把循環(huán)不變運算外提呢?下面我們看一個例子。

例考察下面的流圖。

容易看出｛B2，B3，B4｝是循環(huán)，其中B2是循環(huán)的入口結(jié)點，B4是出口結(jié)點。所謂出口結(jié)點，是指循環(huán)中具有這樣性質(zhì)的結(jié)點：從該結(jié)點有一有向邊引到循環(huán)外的某結(jié)點。

圖1圖中的B3中i∶=2是循環(huán)不變運算。如果我們把i∶=2提到循環(huán)的前置結(jié)點B2’中，如圖所示：

結(jié)果是否相同？為什么？如果我們按照圖2的程序流圖執(zhí)行，執(zhí)行到B5時，i的值總為2，則j的值也為2。事實上，按圖1的流圖，若x＝30，y＝25，則B3不被執(zhí)行，執(zhí)行到B5時，i和j的值都為1，所以圖2的流圖改變了原來程序的運行結(jié)果。

問題的原因在于B3不是循環(huán)出口結(jié)點B4的必經(jīng)結(jié)點。所以，當(dāng)把一個不變運算提到循環(huán)的前置結(jié)點時，要求該不變運算所在的結(jié)點是循環(huán)所有出口結(jié)點的必經(jīng)結(jié)點。

當(dāng)把循環(huán)中的不變運算s:A:=BopC外提時注意：(2)要求循環(huán)中其它地方不再有A的定值點。

(3)要求循環(huán)中A的所有引用點都是而且僅僅是這個定值所能達到的（1）要求s所在結(jié)點是循環(huán)的所有出口結(jié)點的必經(jīng)結(jié)點基本歸納變量：如果在循環(huán)中，對變量I只有唯一的形如：I:=I±C的賦值，且C為循環(huán)不變量，則稱I為循環(huán)中的基本歸納變量。歸納變量的刪除：歸納變量：如果I為循環(huán)中的一個基本歸納變量，J在循環(huán)中的定值總是可以化為I的同一線性函數(shù)也即J＝C1*I±C2,其中C1、C2都是循環(huán)不變量，則稱J為的歸納變量，并稱它與I同族。一個基本歸納變量也是歸納變量。例：P250圖11.3到P251圖11.6I為基本歸納變量，T1為歸納變量，開始有兩個歸納變量I與T1，最后減為1個。歸納變量的刪除，一方面可以刪除歸納變量，同時也可以削弱計算強度。如果有一個循環(huán)中的多個歸納變量，歸納變量的個數(shù)往往可以減少，甚至減到1。減少歸納變量的優(yōu)化稱為歸納變量的刪除。i:=i+1t2:=4*i;t3:=a[t2];ift3<vgotoB2i:=m-1J:=nt1:=4*nV:=a[t1]B1B2j:=j-1t4:=4*j;t5:=a[t4];ift5>vgoto

B3B3ifi>=jgotoB6t11:=4*ix:=a[t11]t12:=4*it13:=4*nt14:=a[t13]a[t12]:=t14t15:=4*na[t15]:=xB6t6:=4*ix:=a[t6]t7:=4*it8:=4*jt9:=a[t8]a[t7]:=t9t10:=4*ja[t10]:=xgotoB2B5B4對如圖所示的代碼進行優(yōu)化:刪除公用表達式復(fù)寫傳播刪除無用的賦值刪除歸納變量強度削弱變換循環(huán)條件i:=i+1t2:=4*i;t3:=a[t2];ift3<vgotoB2i:=m-1J:=nt1:=4*nV:=a[t1]B1B2j:=j-1t4:=4*j;t5:=a[t4];ift5>vgoto

B3B3ifi>=jgotoB6t11:=4*ix:=a[t11]t12:=4*it13:=4*nt14:=a[t13]a[t12]:=t14t15:=4*na[t15]:=xB6t6:=4*ix:=a[t6]t7:=4*it8:=4*jt9:=a[t8]a[t7]:=t9t10:=4*ja[t10]:=xgotoB2B5B4刪除公用表達式刪除公用表達式后i:=i+1t2:=4*i;t3:=a[t2];ift3<vgotoB2i:=m-1J:=nt1:=4*nV:=a[t1]B1B2j:=j-1

t4:=4*j;t5:=a[t4];ift5>vgoto

B3B3ifi>=jgotoB6t11:=t2x:=a[t11]t12:=t11t13:=t1t14:=a[t13]a[t12]:=t14t15:=t1a[t15]:=xB6t6:=t2x:=a[t6]t7:=t6t8:=t4t9:=a[t8]a[t7]:=t9t10:=t8a[t10]:=xgotoB2B5B4i:=i+1t2:=4*i;t3:=a[t2];ift3<vgotoB2i:=m-1J:=nt1:=4*nV:=a[t1]B1B2j:=j-1

t4:=4*j;t5:=a[t4];ift5>vgoto

B3B3ifi>=jgotoB6t11:=t2x:=a[t11]t12:=t11t13:=t1t14:=a[t13]a[t12]:=t14t15:=t1a[t15]:=xB6t6:=t2x:=a[t6]t7:=t6t8:=t4t9:=a[t8]a[t7]:=t9t10:=t8a[t10]:=xgotoB2B5B4t6:=t2x:=a[t6]=a[t2]=t3t7:=t2t8:=t4t9:=a[t8]=a[t4]=t5a[t7]=a[t2]:=t9=t5t10:=t8=t4a[t10]=a[t4]:=xgotoB2B5t11:=t2x:=a[t11]=a[t2]=t3t12:=t11=t2t13:=t1t14:=a[t13]=a[t1]a[t12]=a[t2]:=t14=a[t1]=vt15:=t1a[t15]=a[t1]:=x=t3B6B5,B6經(jīng)復(fù)寫傳播t6:=t2x:=a[t6]=a[t2]=t3t7:=t2t8:=t4t9:=a[t8]=a[t4]=t5a[t7]=a[t2]:=t9=t5t10