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

第五章

代碼優(yōu)化5.1局部?jī)?yōu)化5.2循環(huán)優(yōu)化優(yōu)化的概念代碼優(yōu)化對(duì)代碼進(jìn)行等價(jià)變換，使得變換后的代碼具有更高的時(shí)間效率和空間效率?？臻g效率和時(shí)間效率有時(shí)是一對(duì)矛盾，有時(shí)不能兼顧。優(yōu)化要求必須是等價(jià)變換(保持功能)為優(yōu)化的努力必須是值得的機(jī)器相關(guān)性機(jī)器相關(guān)優(yōu)化：寄存器優(yōu)化，多處理器優(yōu)化，特殊指令優(yōu)化，無(wú)用指令消除等。機(jī)器無(wú)關(guān)優(yōu)化：對(duì)中間代碼的優(yōu)化。優(yōu)化范圍局部?jī)?yōu)化：?jiǎn)蝹€(gè)基本塊范圍內(nèi)的優(yōu)化，包括常量合并、公共子表達(dá)式刪除、計(jì)算強(qiáng)度削弱和無(wú)用代碼刪除等。全局優(yōu)化：主要是基于循環(huán)的優(yōu)化，包括循環(huán)不變量代碼外提、刪除歸納變量、計(jì)算強(qiáng)度削弱等。優(yōu)化語(yǔ)言級(jí)優(yōu)化語(yǔ)言級(jí)：針對(duì)中間代碼，針對(duì)機(jī)器語(yǔ)言。代碼優(yōu)化的分類(lèi)控制流分析的主要目的是分析出程序的循環(huán)結(jié)構(gòu)。循環(huán)結(jié)構(gòu)中的代碼的效率是整個(gè)程序的效率的關(guān)鍵。數(shù)據(jù)流分析進(jìn)行數(shù)據(jù)流信息的收集，主要是變量的值的獲得和使用情況的數(shù)據(jù)流信息。到達(dá)-定義分析；活躍變量分析；可用表達(dá)式分析；代碼變換：根據(jù)上面的分析，對(duì)內(nèi)部中間代碼進(jìn)行等價(jià)變換?？刂屏鞣治鰯?shù)據(jù)流分析代碼變換代碼優(yōu)化主要完成的工作5.1局部?jī)?yōu)化指基本塊內(nèi)的優(yōu)化。基本塊：是指程序（本課本中假設(shè)已經(jīng)是四元式表示的程序了）中一順序執(zhí)行的語(yǔ)句序列，其中只有一個(gè)入口語(yǔ)句和一個(gè)出口語(yǔ)句。5.1.1基本塊的劃分入口語(yǔ)句（1）四元式語(yǔ)句序列的第一個(gè)語(yǔ)句；（2）條件轉(zhuǎn)移語(yǔ)句或無(wú)條件轉(zhuǎn)移語(yǔ)句轉(zhuǎn)移到的目標(biāo)語(yǔ)句；（3）緊跟在條件轉(zhuǎn)移語(yǔ)句后面的語(yǔ)句。出口語(yǔ)句（1）下一個(gè)入口語(yǔ)句的前導(dǎo)語(yǔ)句；（2）轉(zhuǎn)移語(yǔ)句（包括其自身）；（3）停語(yǔ)句（包括其自身）?；緣K的劃分1、求出四元式程序之中各個(gè)基本塊的入口語(yǔ)句。2、對(duì)每一入口語(yǔ)句，構(gòu)造其所屬的基本塊。即由該入口語(yǔ)句到出口語(yǔ)句之間的語(yǔ)句序列。3、凡未被納入某一基本塊的語(yǔ)句，都是程序中控制流程無(wú)法到達(dá)的語(yǔ)句，因而也是不會(huì)被執(zhí)行到的語(yǔ)句，可以把它們刪除。(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為其劃分基本塊?！纠坑兴脑酱a程序如下：5.1.2基本塊的DAG表示DAG

指有向無(wú)環(huán)圖（DirectedAcyclicGraph

），常用來(lái)對(duì)基本塊進(jìn)行優(yōu)化?；緣K的DAG是在結(jié)點(diǎn)上帶有標(biāo)記的DAG。

葉結(jié)點(diǎn)代表名字的初值，以唯一的標(biāo)識(shí)符（變量名字或常數(shù)）標(biāo)記。通常用x0表示變量名字x的初值。

內(nèi)部結(jié)點(diǎn)用運(yùn)算符作為標(biāo)記。

所有結(jié)點(diǎn)都可有一個(gè)或多個(gè)附加標(biāo)識(shí)符，表示這些變量具有該結(jié)點(diǎn)所代表的值。

（其他四元式的

DAG

結(jié)點(diǎn)形式參見(jiàn)教材P131圖5-1）DAG

結(jié)點(diǎn)

ABAopBop

n1n2BCn1n2n1n3n1n2四元式A=BA=opBA=BopCA運(yùn)算符標(biāo)記四元式和與其對(duì)應(yīng)的DAG結(jié)點(diǎn)形式

基本塊DAG表示的構(gòu)造算法設(shè)A=B,A=opB,A=BopC分別為第0、1、2型四元式，設(shè)函數(shù)Node(name)返回最近創(chuàng)建的關(guān)聯(lián)于name的結(jié)點(diǎn)。首先，置DAG為空。

對(duì)基本塊的每一個(gè)四元式，依次執(zhí)行下列步驟：

若Node(B)無(wú)定義，則創(chuàng)建一個(gè)標(biāo)記為B的葉結(jié)點(diǎn)，并令Node(B)為這個(gè)結(jié)點(diǎn)；

(1)對(duì)于2型四元式，若Node(C)無(wú)定義，再創(chuàng)建標(biāo)記為C的葉結(jié)點(diǎn)，并令Node(C)為這個(gè)結(jié)點(diǎn)。若Node(B)和Node(C)都是標(biāo)記為常數(shù)的葉結(jié)點(diǎn)，執(zhí)行BopC，令得到的新常數(shù)為p。若Node(p)無(wú)定義，則構(gòu)造一個(gè)用p做標(biāo)記的葉結(jié)點(diǎn)n,置Node(p)=n。

若Node(B)或Node(C)是處理當(dāng)前語(yǔ)句時(shí)新構(gòu)造出來(lái)的結(jié)點(diǎn)，則刪除它。（這一步有合并已知量的作用）若Node(B)

或Node(C)不是標(biāo)記為常數(shù)的葉結(jié)點(diǎn)，則檢查是否存在某個(gè)標(biāo)記為op的結(jié)點(diǎn)，其左孩子是Node(B)

，而右孩子是Node(C)

？若無(wú)，則創(chuàng)建這樣的結(jié)點(diǎn)。若有，則把已有的結(jié)點(diǎn)作為它的結(jié)點(diǎn)并且無(wú)論有無(wú)，都令該結(jié)點(diǎn)為n。（這一步有刪除多余運(yùn)算的作用）(2)對(duì)于1型四元式若Node(B)

是標(biāo)記為常數(shù)的葉結(jié)點(diǎn)，則執(zhí)行opB，令得到的新常數(shù)為p.若Node(p)無(wú)定義，則構(gòu)造一個(gè)用p

做標(biāo)記的葉結(jié)點(diǎn)n，置node(p)=n。若Node(B)

是處理當(dāng)前語(yǔ)句時(shí)新構(gòu)造出來(lái)的結(jié)點(diǎn)，則刪除它。（這一步有合并已知量的作用）若Node(B)

不是標(biāo)記為常數(shù)的葉結(jié)點(diǎn)，則檢查是否存在某個(gè)標(biāo)記為op的結(jié)點(diǎn)，其唯一的孩子是Node(B)？若無(wú)，則創(chuàng)建這樣的結(jié)點(diǎn);若有，則把已有的結(jié)點(diǎn)作為它的結(jié)點(diǎn)；并且無(wú)論有無(wú)，都令該結(jié)點(diǎn)為n。

（這一步有刪除多余運(yùn)算的作用）若Node(A)無(wú)定義，則把A附加在葉結(jié)點(diǎn)n上并令Node(A)=n；否則，先從Node(A)的附加標(biāo)識(shí)符集中將A刪去（如果Node(A)是葉結(jié)點(diǎn)，則不能將A刪去），然后再把A附加到新結(jié)點(diǎn)n上，并令Node(A)=n。（這一步有刪除無(wú)用賦值的作用）

基本塊DAG表示的構(gòu)造舉例（P132例5.1）T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T6

n13.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T6

n1

n23.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T66.28T1

n5

n1

n2

n3

n43.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T66.28T1R0r0+T2

n6

n5

n1

n2

n3

n43.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T66.28T1R0r0+T2*A

n6

n5

n1

n2

n3

n43.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T66.28T1R0r0+T2*A,B

n6

n5

n1

n2

n3

n43.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T66.28T1,T3R0r0+T2*A,B

n6

n5

n1

n2

n3

n43.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T66.28T1,T3R0r0+T2,T4*A,B

n6

n5

n1

n2

n3

n43.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T66.28T1,T3R0r0+T2,T4*A,B,T5

n6

n5

n7

n1

n2

n3

n43.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T66.28T1,T3R0r0+T2,T4*A,B,T5-T6

n8

n6

n5

n7

n1

n2

n3

n43.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T66.28T1,T3R0r0+T2,T4*A,T5-T6*B

從基本塊的DAG表示可得到等價(jià)的基本塊從下圖的DAG可得到右邊的新的基本塊（經(jīng)拓?fù)渑判蚣疤砑舆m當(dāng)?shù)膹?fù)寫(xiě)語(yǔ)句）

n8

n6

n5

n7

n1

n2

n3

n43.14T0T0=3.14T1=6.28T3=6.28T2=R+rT4=T2A=6.28*T2T5=AT6=R-rB=A*T66.28T1,T3R0r0+T2,T4*A,T5-T6*B

從基本塊的DAG表示可得到等價(jià)的基本塊

比較變換前后的基本塊T0=3.14T1=6.28T3=6.28T2=R+rT4=T2A=6.28*T2T5=AT6=R-rB=A*T6T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T6所作的優(yōu)化合并已知量刪除多余運(yùn)算刪除無(wú)用賦值利用DAG進(jìn)行基本塊優(yōu)化的基本思想：首先按基本塊內(nèi)的四元式序列順序?qū)⑺械乃脑綐?gòu)造成一個(gè)DAG，然后按照構(gòu)造結(jié)點(diǎn)的次序?qū)AG還原成四元式序列。注意：由于在構(gòu)造DAG的同時(shí)已經(jīng)做了局部?jī)?yōu)化，所以最后所得到的就是經(jīng)過(guò)優(yōu)化過(guò)的四元式序列。5.2循環(huán)優(yōu)化循環(huán)體是優(yōu)化的重點(diǎn)控制流圖具有惟一首結(jié)點(diǎn)的有向圖。用來(lái)給出循環(huán)的定義。給出找出程序中循環(huán)的算法。循環(huán)的定義具有唯一入口結(jié)點(diǎn)的強(qiáng)連通子圖。強(qiáng)連通子圖任意兩結(jié)點(diǎn)間的通路上各結(jié)點(diǎn)屬于子圖。循環(huán)的查找方法見(jiàn)課本P138第5.2.2小節(jié)！5.2.3循環(huán)優(yōu)化代碼外提強(qiáng)度削弱刪除歸納變量方法1：代碼外提將循環(huán)不變運(yùn)算移到循環(huán)外?！纠坑谐绦蛉缦拢噷?duì)其進(jìn)行優(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)不變運(yùn)算的定義：P142查找循環(huán)中不變運(yùn)算的算法描述：P144代碼外提算法描述：P144方法2：強(qiáng)度削弱把程序中執(zhí)行時(shí)間較長(zhǎng)的運(yùn)算替換為執(zhí)行時(shí)間較短的運(yùn)算。X:=K*i+Y 相關(guān)計(jì)算i=i+C 歸納變量（K、C、Y為循環(huán)不變量）改為X=X+K*C（設(shè)X的初值=Y-K*C）(4)x=4*i(5)i=i+1(6)y=t1+x(7)goto(3)(5)x=x+4(6)i=i+1(7)y=t1+x(8)goto(4)(1)i=0(2)t1=z*6(1)i=0(2)t1=z*6(3)x=-4(3)ifi>=20goto(8)(4)ifi>=20goto(9)方法3:消除歸納變量利用歸納變量相關(guān)的計(jì)算代替歸納變量的計(jì)算條件表達(dá)式的修改無(wú)用語(yǔ)句的刪除(5)x=x+4(6)i=i+1(7)y=t1+x(8)goto(4)(4)x=x+4(5)y=t1+x(6)goto(3)(1)i=0(2)t1=z*6(3)x=-4(1)t1=z*6(2)x=-4(4)ifi>=20goto(9)(3)ifx>=76

goto(7)強(qiáng)度削弱和刪除歸納變量的算法描述：

P147代碼優(yōu)化示例本節(jié)所用的例子i=m1;(1)i=m1j=n;(2)j=nv=a[n];(3)t1=4*n (4)v=a[t1]while(1){ doi=i+1;while(a[i]<v);(5)i=i+1(6)t2=4*i(7)t3=a[t2](8)ift3<vgoto(5)doj=j1;while(a[j]>v);(9)j=j1(10)t4=4*j(11)t5=a[t4] (12)ift5>vgoto(9)if(i>=j)break;(13)ifi>=jgoto(23)x=a[i];(14)t6=4*i(15)x=a[t6]a[i]=a[j];(16)t7=4*i(17)t8=4*j(18)t9=a[t8](19)a[t7]=t9

a[j]=x;(20)t10=4*j(21)a[t10]=x(22)goto(5)}

x=a[i];(23)t11=4*i(24)x=a[t11]a[i]=a[n];(25)t12=4*i(26)t13=4*n(27)t14=a[t13](28)a[t12]=t14a[n]=x; (29)t15=4*n(30)a[t15]=xi=m1j=nt1=4*nv=a[t1]i=i+1t2=4*it3=a[t2]ift3<vgoto

B2B1B2j=j1t4=4*jt5=a[t4]ift5>vgoto

B3ifi>=jgoto

B6B4B3B5B61、刪除公共子表達(dá)式、復(fù)寫(xiě)傳播B5x=a[i];a[i]=a[j];a[j]=x;t6=4*ix=a[t6]t7=4*it8=4*jt9=a[t8]a[t7]=t9t10=4*ja[t10]=xgoto

B2B5x=a[i];a[i]=a[j];a[j]=x;t6=4*ix=a[t6]t7=4*i

t8=4*jt9=a[t8]a[t7]=t9t10=4*ja[t10]=xgoto

B2B5x=a[i];a[i]=a[j];a[j]=x;t6=4*ix=a[t6]t7=4*i

t8=4*jt9=a[t8]a[t7]=t9t10=4*ja[t10]=xgoto

B2t6=4*ix=a[t6]t8=4*jt9=a[t8]a[t6]=t9a[t8]=xgoto

B2B5x=a[i];a[i]=a[j];a[j]=x;t6=4*ix=a[t6]t7=4*it8=4*jt9=a[t8]a[t7]=t9t10=4*ja[t10]=xgoto

B2t6=4*ix=a[t6]t8=4*jt9=a[t8]a[t6]=t9a[t8]=xgoto

B2x=a[t2]t9=a[t4]a[t2]=t9a[t4]=xgoto

B22、刪除無(wú)用賦值B5x=a[i];a[i]=a[j];a[j]=x;t6=4*ix=a[t6]t7=4*i

t8=4*jt9=a[t8]a[t7]=t9t10=4*ja[t10]=xgoto

B2t6=4*i