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

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

目標代碼生成（介紹）代碼優(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)化的任務通過等價的程序變換，獲得執(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ù)據結構和算法領域相關2023/2/54《編譯原理》

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

——符號表管理關鍵字表關鍵字名字關鍵字標識begin112end113while114名字信息1信息2……信息nsum1real所在層定義/引用……2023/2/56上次課主要內容

——符號表管理層次表所在層性質起點終點直接外層本層計數(shù)2023/2/57上次課主要內容

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

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

B的入口

A的出口不是轉移語句，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入口：代碼序列的第一語句轉移語句的目標語句

轉移語句下一條語句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ù)表達式計算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)重新命名臨時變量t1代替t2,t4,t6,t7,t10,t11,t12,t15t3代替t5,t8,t13,t142023/2/519(3)刪除基本塊內的公共子表達式(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)交換語句次序減少臨時變量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)化的重點反復執(zhí)行循環(huán)的定義有唯一入口點的強連接子圖強連接子圖任意兩結點間的通路上各結點屬于子圖2023/2/522方法1：代碼外提將循環(huá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：強度削弱用較快的操作代替較慢的操作+替代*；*替代**循環(huán)歸納變量相關的強度削弱X:=K*i+Y 相關計算i:=i+C 歸納變量（K、C、Y為循環(huán)不變量）改為X:=X+KC

設X的初值=Y-KC，KC為K*C的結果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:消除歸納變量利用歸納變量相關的計算代替歸納變量的計算條件表達式的修改無用語句的刪除優(yōu)化效果語句數(shù)、乘除法數(shù)、變址運算、一般運算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目標代碼生成代碼生成的任務針對目標語言的特殊性，生成高性能的目標代碼（機器相關）2023/2/5299.4目標代碼生成輸入：中間代碼序列三地址代碼、語法結構樹、后綴式輸出：目標代碼絕對機器代碼、可重定位機器指令代碼、匯編指令代碼目標機多通用寄存器、控制棧、堆2023/2/530性能問題質量要求目標代碼效率高目標程序短實現(xiàn)方法充分利用寄存器參考目標機的結構與指令形式2023/2/531分配寄存器節(jié)省的執(zhí)行代價對象：基本塊N中的變量AUSE(N,A)：N中對A定值前，A的引用次數(shù)LIVE(N,A)：1表示A在N中被定值，且出口之后有引用；0表示其他情況。循環(huán)L中為變量A分配寄存器節(jié)省的執(zhí)行代價2023/2/532代碼生成