代碼優(yōu)化與代碼生成課件

代碼優(yōu)化與代碼生成

代碼優(yōu)化算法優(yōu)化有效的數(shù)據(jù)結(jié)構(gòu)和算法（領(lǐng)域問(wèn)題）編譯優(yōu)化中間代碼優(yōu)化：機(jī)器無(wú)關(guān)如：常數(shù)計(jì)算、公共代碼段的提取目標(biāo)代碼優(yōu)化：機(jī)器相關(guān)如：特殊指令、特殊結(jié)構(gòu)中間代碼優(yōu)化局部?jī)?yōu)化基本塊內(nèi)部（不包括各種轉(zhuǎn)移控制）全局優(yōu)化循環(huán)優(yōu)化、控制流分析與化簡(jiǎn)、數(shù)據(jù)流分析8.1基本塊和流圖基本塊控制流從第一語(yǔ)句進(jìn)入，從最后一條語(yǔ)句離開(kāi)語(yǔ)句序列中間沒(méi)有停止或分枝關(guān)鍵：確定每個(gè)基本塊的入口(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)基本塊的劃分1)定義入口語(yǔ)句代碼序列的第一語(yǔ)句轉(zhuǎn)移語(yǔ)句的目標(biāo)語(yǔ)句轉(zhuǎn)移語(yǔ)句的下一條語(yǔ)句2)定義基本塊一入口語(yǔ)句到下一入口語(yǔ)句之前一入口語(yǔ)句到轉(zhuǎn)移語(yǔ)句或停語(yǔ)句程序流圖的構(gòu)造流圖Ｇ＝｛Ｎ，Ｅ，n0

｝Ｎ：基本塊集n0：含首語(yǔ)句的基本塊Ｅ：有向邊集合A

BA的出口為轉(zhuǎn)移語(yǔ)句，轉(zhuǎn)向B的入口B緊跟A之后，且A的出口不是goto或return以基本塊為結(jié)點(diǎn)，以控制流為有向邊例8-1：基本塊劃分和流圖i=m-1; j=n; v=a[n];while(1){ while(a[++i]<v); 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;三地址碼序列(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入口三地址碼：代碼序列的第一語(yǔ)句轉(zhuǎn)移語(yǔ)句的目標(biāo)語(yǔ)句轉(zhuǎn)移語(yǔ)句的下一條語(yǔ)句程序流圖B1(1-4)B2(5-8)B3(9-12)B4(13)B5(14-22)B6(23-30)(8)ift3<vgoto(5)(12)ift5>vgoto(9)(13)ifi>=jgoto(23)(22)goto(5)8.2局部?jī)?yōu)化(1)合并已知量常數(shù)表達(dá)式計(jì)算(2)重新命名臨時(shí)變量t1代替t2,t4,t6,t7,t10,t11,t12,t15t3代替t5,t8,t13(3)刪除公共子表達(dá)式(14)(16)、(17)(20)、(23)(25)、(26)(29)(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(4)刪除死代碼未出現(xiàn)在程序流圖中的代碼賦值未引用的指令(5)交換語(yǔ)句次序減少臨時(shí)變量8.3循環(huán)優(yōu)化循環(huán)體是優(yōu)化的重點(diǎn)反復(fù)執(zhí)行循環(huán)的定義有唯一入口點(diǎn)的強(qiáng)連接子圖強(qiáng)連接子圖任意兩結(jié)點(diǎn)間的通路上各結(jié)點(diǎn)屬于子圖方法1：代碼外提將循環(huán)不變運(yù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)方法2：強(qiáng)度削弱用較快的操作代替較慢的操作循環(huán)歸納變量相關(guān)的強(qiáng)度削弱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ǔ)句的刪除優(yōu)化效果語(yǔ)句數(shù)、乘除法數(shù)、變址運(yùn)算、一般運(yùn)算(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)if

i

>=20goto(9)(3)ifx>=76goto(7)8.4目標(biāo)代碼生成輸入：中間代碼序列三地址代碼、語(yǔ)法結(jié)構(gòu)樹(shù)、后綴式輸出：目標(biāo)代碼絕對(duì)機(jī)器代碼、可重定位機(jī)器指令代碼、匯編指令代碼目標(biāo)機(jī)多通用寄存器、控制棧、堆性能問(wèn)題質(zhì)量要求目標(biāo)代碼效率高目標(biāo)程序短實(shí)現(xiàn)方法充分利用寄存器參考目標(biāo)機(jī)的結(jié)構(gòu)與指令形式分配寄存器節(jié)省的執(zhí)行代價(jià)對(duì)象：基本塊A中的變量NUSE(N,A)：A中對(duì)N定值前的引用次數(shù)LIVE(N,A)：1表示N在A中被定值，且出口之后有引用；0表示其他情況。循環(huán)L中為變量N分配寄存器節(jié)省的執(zhí)行代價(jià)代碼生成概要計(jì)算各循環(huán)中各變量的可節(jié)省執(zhí)行代價(jià)，據(jù)此分配寄存器對(duì)于每條三地址碼，參照目標(biāo)機(jī)允許的指令形式，進(jìn)行翻譯例x:=yopz => movRi,yopRi,zmovx,Ri例8-3：代碼生成一般寄存器R0R1專用寄存器R2分配給xR3分配給t1指令種類賦值MOV比較CMP條件轉(zhuǎn)移JLE轉(zhuǎn)移JMP累加ADD生成目標(biāo)代碼(1)MOVR0,Z(2)MULR0,6(3)MOVR3,R0(4)MOVR2,-4(5)CMP