第9章代碼優化與

目標代碼生成（介紹）代碼優化代碼生成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代碼優化代碼優化的任務通過等價的程序變換，獲得執行速度快、占用空間少的程序2023/2/53代碼優化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)}算法優化例：順序查找與hash算法有效的數據結構和算法領域相關2023/2/54《編譯原理》

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

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

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

——符號表管理過程表變量表標號表名字種類類型地址參數個數層次……定義/引用名字種類類型長度地址……標志2023/2/58上次課主要內容代碼優化通過等價變換，獲得執行速度快、占用空間少的程序算法優化2023/2/59代碼優化編譯優化目標代碼優化：機器相關特殊指令的利用特殊結構的高效利用：SIMD、MIDM、流水、向量機中間代碼優化：機器無關如：常數計算、公共代碼段的提取2023/2/510中間代碼優化局部優化基本塊內部（不包括各種轉移控制）全局優化循環優化、控制流分析與化簡、數據流分析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局部優化(1)合并已知量常數表達式計算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)刪除死代碼未出現在程序流圖中的代碼賦值但未引用的指令(5)交換語句次序減少臨時變量t1:=a+xt2:=b*yt:=t1+zp:=t*xt1:=a+xt:=t1+zt1:=b*yp:=t*x2023/2/5219.3循環優化循環體是優化的重點反復執行循環的定義有唯一入口點的強連接子圖強連接子圖任意兩結點間的通路上各結點屬于子圖2023/2/522方法1：代碼外提將循環不變運算移到循環外例：程序優化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：強度削弱用較快的操作代替較慢的操作+替代*；*替代**循環歸納變量相關的強度削弱X:=K*i+Y 相關計算i:=i+C 歸納變量（K、C、Y為循環不變量）改為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:消除歸納變量利用歸納變量相關的計算代替歸納變量的計算條件表達式的修改無用語句的刪除優化效果語句數、乘除法數、變址運算、一般運算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性能問題質量要求目標代碼效率高目標程序短實現方法充分利用寄存器參考目標機的結構與指令形式2023/2/531分配寄存器節省的執行代價對象：基本塊N中的變量AUSE(N,A)：N中對A定值前，A的引用次數LIVE(N,A)：1表示A在N中被定值，且出口之后有引用；0表示其他情況。循環L中為變量A分配寄存器節省的執行代價2023/2/532代碼生成