三下-編譯原理

編譯原理

(PrinciplesofCompiling)2023/1/41主講：蔣宗禮辦公室：二教205電話：67392690Email：棧式存儲(chǔ)管理SPnSPn-1……SP1SP02023/1/42數(shù)組存儲(chǔ)區(qū)本過(guò)程……所轄分第臨時(shí)工作單元程一序?qū)泳植繑?shù)組說(shuō)明存分儲(chǔ)程局部變量區(qū)序分程序TOP本過(guò)程Display形式單元（m+1個(gè)）連主調(diào)分程序TOP接全局Display地址數(shù)返回地址據(jù)主調(diào)過(guò)程SP本過(guò)程TOPSP堆管理上次課主要內(nèi)容上次課主要內(nèi)容參數(shù)傳遞傳值調(diào)用引用調(diào)用復(fù)制恢復(fù)傳名調(diào)用2023/1/43A實(shí)際參數(shù)A形參XA的值間址訪AAA的地址AA的值A(chǔ)的地址將過(guò)程體嵌在調(diào)用處執(zhí)行，參數(shù)需文字替換上次課主要內(nèi)容Procedureid(X1,X2,…,Xn)X1.codeX2.code……Xn.code動(dòng)態(tài)存儲(chǔ)分配相關(guān)進(jìn)入過(guò)程體2023/1/44id(E1,E2,…,En)

E1.codea1:=E1.place…En.codean:=En.place動(dòng)態(tài)存儲(chǔ)分配相關(guān)gotopc+n+1parama1……paramancallid.place，n過(guò)程調(diào)用語(yǔ)句屬性文法2023/1/45{Elist.num:=Elist1.num+1;Elist.code:=Elist1.code||E.code||t:=newtemp;gen(t’:=’E.place);將t放入隊(duì)列q}{Elist.num:=1;Elist.code:=E.code||t:=newtemp;gen(t’:=’E.place)；建立隊(duì)列q，并將t放入q}{S.code:=Elist.code||gen(‘goto‘pc+Elist.num+1)||for隊(duì)列q中的每一項(xiàng)

tdogen(’param’t)||gen(‘call’id.place’,’Elist.num)}Elist→E Elist→Elist1,ES→callid(Elist)Ei.codeai:=Ei.placegotopc+n+1parama1……paramancallid.place，n第9章代碼優(yōu)化與

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

s[i]:=4*i+n*m每次增加4*m，且n*m重復(fù)計(jì)算：s[i]=s[i-1]+4*m2023/1/47a:=4*m;s1:=4+n*m;fori=1tonstepmdo{s[i]:=s1;

s1:=s1+a}a:=4*m;s[1]=4+n*m;fori=2tonstepmdos[i]:=s[i-1]+a;初值為4+n*m，每次增加4*m代碼優(yōu)化代碼優(yōu)化的任務(wù)通過(guò)等價(jià)的程序變換，獲得執(zhí)行速度快、占用空間少的程序2023/1/48代碼優(yōu)化fori=2to10000do{T=0; forj=2toi-1do ifi=i/j*jthen{T=1;break} ifT=0thenprint(i)}fori=2to10000do {T=0;

forj=2to

i/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)代碼優(yōu)化編譯優(yōu)化目標(biāo)代碼優(yōu)化：機(jī)器相關(guān)特殊指令的利用特殊結(jié)構(gòu)的高效利用：SIMD、MIMD、流水、向量機(jī)中間代碼優(yōu)化：機(jī)器無(wú)關(guān)如：常數(shù)計(jì)算、公共代碼段的提取2023/1/410中間代碼優(yōu)化局部?jī)?yōu)化基本塊內(nèi)部(除最后一個(gè)代碼，不含轉(zhuǎn)移控制)全局優(yōu)化循環(huán)優(yōu)化控制流分析數(shù)據(jù)流分析2023/1/4119.1基本塊和流圖基本塊控制流從第一語(yǔ)句進(jìn)入，從最后一條語(yǔ)句離開(kāi)語(yǔ)句序列中間沒(méi)有停止或分枝關(guān)鍵：確定每個(gè)基本塊的入口2023/1/412(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)移語(yǔ)句的下一條語(yǔ)句轉(zhuǎn)移語(yǔ)句的目標(biāo)第一條語(yǔ)句基本塊的劃分1)定義入口語(yǔ)句代碼序列的第一語(yǔ)句轉(zhuǎn)移語(yǔ)句的目標(biāo)語(yǔ)句轉(zhuǎn)移語(yǔ)句的下一條語(yǔ)句2)定義基本塊一入口語(yǔ)句到下一入口語(yǔ)句之前一入口語(yǔ)句到轉(zhuǎn)移語(yǔ)句(最后一條語(yǔ)句)或停語(yǔ)句2023/1/413(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)程序流圖的構(gòu)造程序流圖G={N,E,n0}以基本塊為結(jié)點(diǎn)，以控制流為有向邊N：基本塊集n0：含首語(yǔ)句的基本塊E：有向邊集合(A,B)A的出口是轉(zhuǎn)移語(yǔ)句，轉(zhuǎn)向B的入口A的出口非轉(zhuǎn)移語(yǔ)句，B緊跟A之后2023/1/414例9-1：基本塊劃分和流圖i=m-1; j=n; v=a[n];while(1)do{ whiledo(a[++i]<v); whiledo(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/1/415三地址碼序列(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ǔ)句i=m-1;j=n;v=a[n];while(1)do{while(a[++i]<v)do;while(a[--j]>v)do;if(i≥j)thenbreak;x=a[i];a[i]=a[j];a[j]=x;}x=a[i];a[i]=a[n];a[n]=x;B1B2B3B4B5B6程序流圖2023/1/417B1(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)9.2局部?jī)?yōu)化(1)合并已知量常數(shù)表達(dá)式計(jì)算2023/1/418t3:=110*xt1:=5+6t2:=t1*10t3:=t2*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(2)重新命名臨時(shí)變量——節(jié)約空間t1代替t2,t4,t6,t7,t10,t11,t12,t15t3代替t5,t8,t13,t14t1t1t1t1t1t1t1t1t1t1t1t1t1t1t1t1t3t3t3t3t3t3t3t3(3)刪除基本塊內(nèi)的公共子表達(dá)式(14)(16)、(17)(20)、(23)(25)、(26)(29)2023/1/420(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]:=x9.2局部?jī)?yōu)化(4)刪除死代碼未出現(xiàn)在程序流中的代碼賦值但未引用的指令2023/1/421B1B2B3B4B6B5B8B7t1:=a+xt2:=b*yt:=t1+zp:=t*xPrintpstop9.2局部?jī)?yōu)化(5)交換語(yǔ)句次序減少臨時(shí)變量2023/1/422t1:=a+xt2:=b*yt:=t1+zp:=t*xt1:=a+xt:=t1+zt1:=b*yp:=t*x9.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/1/423方法1：代碼外提將循環(huán)不變運(yùn)算移到循環(huán)外例 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)(1)i:=0(2)ifi≥20goto(8)(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 歸納變量，步長(zhǎng)為C(K、C、Y為循環(huán)不變量)改為X:=X+KC

設(shè)X的初值=Y-KC，KC為K*C的結(jié)果2023/1/426(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)方法3:消除歸納變量利用歸納變量相關(guān)的計(jì)算代替歸納變量的計(jì)算條件表達(dá)式的修改無(wú)用語(yǔ)句的刪除優(yōu)化效果語(yǔ)句數(shù)、乘除法數(shù)、變址運(yùn)算、一般運(yùn)算2023/1/428(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)9.4目標(biāo)代碼生成代碼生成的任務(wù)針對(duì)目標(biāo)語(yǔ)言的特殊性，生成高性能的目標(biāo)代碼(機(jī)器相關(guān))2023/1/4309.4目標(biāo)代碼生成輸入：中間代碼序列三地址代碼、語(yǔ)法結(jié)構(gòu)樹(shù)、后綴式輸出：目標(biāo)代碼絕對(duì)機(jī)器代碼、可重定位機(jī)器指令代碼、匯編指令代碼目標(biāo)機(jī)多通用寄存器、控制棧、堆2023/1/431性能問(wèn)題質(zhì)量要求目標(biāo)代碼效率高目標(biāo)程序短實(shí)現(xiàn)方法充分利用寄存器參考目標(biāo)機(jī)的結(jié)構(gòu)與指令形式2023/1/432分配寄存器節(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à)∑N∈L[use(N,A)+2*LIVE(N,A)]2023/1/433代碼生成概要計(jì)算各循環(huán)中各變量的可節(jié)省執(zhí)行代價(jià)，據(jù)此分配寄存器對(duì)于每條三地址碼，參照目標(biāo)機(jī)允許的指令形式，進(jìn)行翻譯例2023/1/434x:=yopzmovRi,yopRi,zmovx,Ri例9-3代碼生成一般寄存器R0、R1專(zhuān)用寄存器R2分配給xR3分配給t1指令種類(lèi)賦值