代碼優(yōu)化與目標(biāo)代碼生成(介紹)-編譯原理-09-(一)

第9章代碼優(yōu)化與

目標(biāo)代碼生成（介紹）代碼優(yōu)化代碼生成2023/2/51引例fori=1tonstepmdo

s[i]:=4*i+n*ma:=4*m;s1:=4+n*m;fori=1tonstepmdo{s[i]:=s1;s1:=s1+a}a:=4*m;s[1]=4+n*m;fori=2tonstepmdo

s[i]:=s[i-1]+a;2023/2/52代碼優(yōu)化代碼優(yōu)化的任務(wù)通過等價(jià)的程序變換，獲得執(zhí)行速度快、占用空間少的程序2023/2/53代碼優(yōu)化fori=2to10000do{T=0; forj=2toi-1do ifi=i/j*jthen{T=1;break} ifT=0thenprint(i)}fori=2to10000do {T=0; forj=2toi/2do ifi=i/j*jthen{T=1;break} ifT=0thenprint(i)}fori=2to10000do {T=0; forj=2tosqrt(i)do ifi=i/j*jthen{T=1;break} ifT=0thenprint(i)}算法優(yōu)化例：順序查找與hash算法有效的數(shù)據(jù)結(jié)構(gòu)和算法領(lǐng)域相關(guān)2023/2/54《編譯原理》

(PrinciplesofCompiling)主講：蔣宗禮2023/2/55上次課主要內(nèi)容

——符號(hào)表管理關(guān)鍵字表關(guān)鍵字名字關(guān)鍵字標(biāo)識(shí)begin112end113while114名字信息1信息2……信息nsum1real所在層定義/引用……2023/2/56上次課主要內(nèi)容

——符號(hào)表管理層次表所在層性質(zhì)起點(diǎn)終點(diǎn)直接外層本層計(jì)數(shù)2023/2/57上次課主要內(nèi)容

——符號(hào)表管理過程表變量表標(biāo)號(hào)表名字種類類型地址參數(shù)個(gè)數(shù)層次……定義/引用名字種類類型長度地址……標(biāo)志2023/2/58上次課主要內(nèi)容代碼優(yōu)化通過等價(jià)變換，獲得執(zhí)行速度快、占用空間少的程序算法優(yōu)化2023/2/59代碼優(yōu)化編譯優(yōu)化目標(biāo)代碼優(yōu)化：機(jī)器相關(guān)特殊指令的利用特殊結(jié)構(gòu)的高效利用：SIMD、MIDM、流水、向量機(jī)中間代碼優(yōu)化：機(jī)器無關(guān)如：常數(shù)計(jì)算、公共代碼段的提取2023/2/510中間代碼優(yōu)化局部優(yōu)化基本塊內(nèi)部（不包括各種轉(zhuǎn)移控制）全局優(yōu)化循環(huán)優(yōu)化、控制流分析與化簡(jiǎn)、數(shù)據(jù)流分析2023/2/5119.1基本塊和流圖基本塊控制流從第一語句進(jìn)入，從最后一條語句離開語句序列中間沒有停止或分枝關(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)轉(zhuǎn)移語句的下一條語句轉(zhuǎn)移語句的目標(biāo)第一條語句2023/2/512基本塊的劃分1)定義入口語句代碼序列的第一語句轉(zhuǎn)移語句的目標(biāo)語句轉(zhuǎn)移語句的下一條語句2)定義基本塊一入口語句到下一入口語句之前一入口語句到轉(zhuǎn)移語句或停語句(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)2023/2/513程序流圖的構(gòu)造程序流圖Ｇ＝｛Ｎ，Ｅ，n0

｝以基本塊為結(jié)點(diǎn)，以控制流為有向邊Ｎ：基本塊集n0：含首語句的基本塊Ｅ：有向邊集合(A,B)A的出口是轉(zhuǎn)移語句，轉(zhuǎn)向

B的入口

A的出口不是轉(zhuǎn)移語句，B緊跟

A之后2023/2/514例9-1：基本塊劃分和流圖i=m-1; j=n; v=a[n];while(1){ while(a[++i]<v); while(a[--j]>v); if(i≥j)thenbreak; x=a[i]; a[i]=a[j];a[j]=x;}x=a[i];a[i]=a[n];a[n]=x;2023/2/515三地址碼序列(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≥j

goto(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入口：代碼序列的第一語句轉(zhuǎn)移語句的目標(biāo)語句

轉(zhuǎn)移語句下一條語句i=m-1;j=n;v=a[n];while(a[++i]<v);while(a[--j]>v);if(i≥j)thenbreak;x=a[i];a[i]=a[j];a[j]=x;x=a[i];a[i]=a[n];a[n]=x;2023/2/516程序流圖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)2023/2/5179.2局部優(yōu)化(1)合并已知量常數(shù)表達(dá)式計(jì)算t3:=110*xt1:=5+6t2:=t1*10t3:=t2*x2023/2/518(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≥j

goto(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(2)重新命名臨時(shí)變量t1代替t2,t4,t6,t7,t10,t11,t12,t15t3代替t5,t8,t13,t142023/2/519(3)刪除基本塊內(nèi)的公共子表達(dá)式(14)(16)、(17)(20)、(23)(25)、(26)(29)(14)t1:=4*i(15)x:=a[t1](16)t1:=4*i(17)t3:=4*j(18)t9:=a[t3](19)a[t1]:=t9(20)t1:=4*j(21)a[t1]:=x(22)goto(5)(23)t1:=4*i(24)x:=a[t1](25)t1:=4*i(26)t3:=4*n(27)t3:=a[t3](28)a[t1]:=t3(29)t1:=4*n(30)a[t1]:=x(14)t1:=4*i(15)x:=a[t1](17)t3:=4*j(18)t9:=a[t3](19)a[t1]:=t9(21)a[t3]:=x(22)goto(5)(23)t1:=4*i(24)x:=a[t1](26)t3:=4*n(27)t3:=a[t3](28)a[t1]:=t3(30)a[t3]:=x2023/2/520(4)刪除死代碼未出現(xiàn)在程序流圖中的代碼賦值但未引用的指令(5)交換語句次序減少臨時(shí)變量t1:=a+xt2:=b*yt:=t1+zp:=t*xt1:=a+xt:=t1+zt1:=b*yp:=t*x2023/2/5219.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)屬于子圖2023/2/522方法1：代碼外提將循環(huán)不變運(yùn)算移到循環(huán)外例：程序優(yōu)化i=0;while(i<20){x=4*i;i++;y=z*6+x}2023/2/523(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)2023/2/524方法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+KC

設(shè)X的初值=Y-KC，KC為K*C的結(jié)果2023/2/525(4)x:=4*i(5)i:=i+1(6)y:=t1+x(7)goto(3)(5)x:=x+4(4*1)(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)2023/2/526方法3:消除歸納變量利用歸納變量相關(guān)的計(jì)算代替歸納變量的計(jì)算條件表達(dá)式的修改無用語句的刪除優(yōu)化效果語句數(shù)、乘除法數(shù)、變址運(yùn)算、一般運(yùn)算2023/2/527(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)if

x≥76

goto(7)2023/2/5289.4目標(biāo)代碼生成代碼生成的任務(wù)針對(duì)目標(biāo)語言的特殊性，生成高性能的目標(biāo)代碼（機(jī)器相關(guān)）2023/2/5299.4目標(biāo)代碼生成輸入：中間代碼序列三地址代碼、語法結(jié)構(gòu)樹、后綴式輸出：目標(biāo)代碼絕對(duì)機(jī)器代碼、可重定位機(jī)器指令代碼、匯編指令代碼目標(biāo)機(jī)多通用寄存器、控制棧、堆2023/2/530性能問題質(zhì)量要求目標(biāo)代碼效率高目標(biāo)程序短實(shí)現(xiàn)方法充分利用寄存器參考目標(biāo)機(jī)的結(jié)構(gòu)與指令形式2023/2/531分配寄存器節(jié)省的執(zhí)行代價(jià)對(duì)象：基本塊N中的變量AUSE(N,A)：N中對(duì)A定值前，A的引用次數(shù)LIVE(N,A)：1表示A在N中被定值，且出口之后有引用；0表示其他情況。循環(huán)L中為變量A分配寄存器節(jié)省的執(zhí)行代價(jià)2023/2/532代碼生成