編譯原理簡(jiǎn)明教程（第3版）-課件 第8章 代碼優(yōu)化

新工科建設(shè)·計(jì)算機(jī)類(lèi)系列教材

免費(fèi)提供編譯原理16目錄第一章概述第二章形式語(yǔ)言理論基礎(chǔ)第三章自動(dòng)機(jī)理論基礎(chǔ)第四章詞法分析第五章語(yǔ)法分析—自頂向下分析方法第六章語(yǔ)法分析—自底向上分析方法第七章語(yǔ)義分析及中間代碼的生成第八章代碼優(yōu)化第九章目標(biāo)代碼的生成第十章符號(hào)表和出錯(cuò)處理第十一章

面向?qū)ο笳Z(yǔ)言的編譯第十二章

并行編譯技術(shù)第十三章

軟件構(gòu)造22024/11/63學(xué)習(xí)目標(biāo)代碼優(yōu)化的概念循環(huán)優(yōu)化局部?jī)?yōu)化代碼優(yōu)化的分類(lèi)8代碼優(yōu)化重點(diǎn)：代碼優(yōu)化的定義和代碼優(yōu)化的分類(lèi)難點(diǎn)：局部?jī)?yōu)化、循環(huán)優(yōu)化

目錄8.1代碼優(yōu)化概述8.2局部?jī)?yōu)化8.3循環(huán)優(yōu)化8.4本章小結(jié)4定義

所謂優(yōu)化，實(shí)質(zhì)上是對(duì)代碼進(jìn)行等價(jià)變換，使得變換后的代碼具有更高的效率，包括時(shí)間效率和空間效率。目的

獲得性能較好的代碼，即要盡量縮小存儲(chǔ)空間，還要盡量提高運(yùn)行速度。

58.1代碼優(yōu)化概述8.1.1代碼優(yōu)化的定義優(yōu)化可在編譯的不同階段進(jìn)行：源代碼設(shè)計(jì)階段--程序員選擇好的算法和語(yǔ)句語(yǔ)義分析階段--如何生成高質(zhì)量的中間代碼中間代碼--采用優(yōu)化技術(shù)目標(biāo)代碼--有效利用寄存器、指令、處理機(jī)

678.1.2代碼優(yōu)化的分類(lèi)1、與機(jī)器的相關(guān)性

與機(jī)器有關(guān)的優(yōu)化：寄存器的優(yōu)化、多處理機(jī)的優(yōu)化、特殊指令的優(yōu)化、無(wú)用代碼的消除。與機(jī)器無(wú)關(guān)的優(yōu)化：基本塊的優(yōu)化、循環(huán)優(yōu)化。2、優(yōu)化范圍

局部?jī)?yōu)化：基本程序塊上進(jìn)行的優(yōu)化

全局優(yōu)化：全局程序范圍內(nèi)的優(yōu)化88.1.2代碼優(yōu)化的分類(lèi)1、局部?jī)?yōu)化：基本程序塊上進(jìn)行的優(yōu)化

基本程序塊---只有一個(gè)入口、一個(gè)出口的基本程序塊

合并常量和已知量

消除公共子表達(dá)式

削減運(yùn)算強(qiáng)度

刪除無(wú)用代碼2、全局優(yōu)化：全局程序范圍內(nèi)的優(yōu)化

循環(huán)優(yōu)化是全局優(yōu)化：

外提循環(huán)不變表達(dá)式

削減計(jì)算強(qiáng)度

刪除歸納變量1、合并常量運(yùn)算

運(yùn)算對(duì)象是常量或在編譯時(shí)已知，則在編譯時(shí)直接計(jì)算出結(jié)果，不必等到運(yùn)行時(shí)再去計(jì)算。

例：

x:=3.14*2;y:=2*5*a;z:=x+0.5;合并常量運(yùn)算后： x:=6.28;y:=10*a;z:=6.78;98.1.3優(yōu)化技術(shù)簡(jiǎn)介優(yōu)化前的四元式：(1)(*

,3.14,2,T1)(2)(:=,T1

,_,

x)(3)(*

,2

,5,T2)(4)(*

,T2

,a,T3)(5)(:=,T3

,_,

y)(6)(+

,x

,0.5,T4)(7)(:=,T4

,

_,

z)優(yōu)化后：

(1) (:=,6.28,_,x)(2)(*

,10

,a,y)(3)(:=,6.78,_,z)

102、刪除無(wú)用賦值

刪除程序中對(duì)運(yùn)行結(jié)果沒(méi)有任何作用的賦值變量。

例：

x:=2+a；

y:=2+b；

x:=2*a*b;y:=x*y;刪除無(wú)用賦值后：

y:=2+b；

x:=2*a*b;y:=x*y;11優(yōu)化前的四元式：(1)(+,2,a,x)(2)(+,2,b,y)(3)(*,2,

a,T1)(4)(*,T1,b,x)(5)(*,x,y,y)優(yōu)化后的四元式：

(1)(+,2，b,y)(2)(*,2，a,T1)(3)(*,T1，b,x)(4)(*,x，y,y)

123、削減運(yùn)算強(qiáng)度（運(yùn)算強(qiáng)度大→?。?/p>

例：

fori:=1to100doa:=10*i；削減運(yùn)算強(qiáng)度后：a:=0；fori:=1to100doa:=a+10;優(yōu)化后的四元式：

(1)(:=,0

,_,a)(2)(:=,1

,_,i)(3)(<=,i,100,T1)(4)(BF,(8),T1,_)(5)(+

,a,10,a)(6)(+

,i,1,

i)(7)(BR,(3),_,_)(8)()134、刪除多余運(yùn)算(或刪除公共子表達(dá)式)公共子表達(dá)式：重復(fù)使用兩次以上的子表達(dá)式，且表達(dá)式中變量的值沒(méi)有發(fā)生變化。

例：x:=a*(b+c)+d;y:=a*(b+c)-d;

14優(yōu)化前：

(1)(+,b,c,T1)

(2)(*,a,T1,T2)(3)(+,T2,d,x)

(4)(+,b,c,T3)

(5)(*,a,T3,T4)(6)(-,T4,d,y)優(yōu)化后：

(1)(+,b,c,T1)(2)(*,a,T1,T2)(3)(+,T2,d,x)(4)(-,T2,d,y)

155、外提不變表達(dá)式不變表達(dá)式：循環(huán)中其值始終保持不變的表達(dá)式

例：fori:=1to100dobeginx:=(a+b)*(c+d)*i;y:=x+i；end優(yōu)化后的程序：e:=(a+b)*(c+d);fori:=1to100dobeginx:=e*i;y:=x+i；end16優(yōu)化前的四元式：(1)(:=,1,_,i)(2)(<=,i,100,T1)(3)(BF,(11),T1,_)(4)(+, a,b,T2)(5)(+, c,d,T3)(6)(*, T2,T3,T4)(7)(*, T4,i,x)(8)(+, x,i,y)(9)(+, i,1,i)(10)(BR,(2),_,_)(11)( )

17優(yōu)化后的四元式：(1)(:=,1,_，i)(2)(+,a,b,T1)(3)(+,c,d,T2)(4)(*,T1,T2,e)(5)(<=,i,100,T3)(6)(BF,(11),T3,_)(7)(*,e,i,x)(8)(+,x,i,y)(9)(+,i,1,i)(10)(BR,(5),_,_)(11)( )

18198.2局部?jī)?yōu)化a=10;b=a*10;

c=a+b;s=0;k=1;if(k<5)s=s+k;elses=s-k;一個(gè)基本塊不是一個(gè)基本塊

局部?jī)?yōu)化是指局部范圍內(nèi)的優(yōu)化。把程序劃分為若干個(gè)“基本塊”，優(yōu)化的工作將分別在各個(gè)基本塊內(nèi)進(jìn)行。8.2.1基本塊的劃分

基本塊，是指程序中一組順序執(zhí)行的語(yǔ)句序列，其中只有一個(gè)入口和一個(gè)出口，執(zhí)行時(shí)只能從其入口進(jìn)入，從其出口退出。即基本塊內(nèi)的運(yùn)算要么都被執(zhí)行，要么都不執(zhí)行。208.2.1基本塊的劃分例題8.1、

考察下列四元式序列：(1)(=,(2)(+,(3)(>,(4)(

BF,(5)(_,(6)(=,(7)(BR,(8)(*,(9)(end,100,i,k,(8),

k,T3

,

(3),i,_,_,j,T1

,

T2

,

1,_,_,j,_,k)T1)T2))T3)k)_)k)_)圖8.1基本塊劃分示例

由圖8.1可以看出，以上程序段可以劃分為四個(gè)基本塊B1、B2、B3、B4

，而且各基本塊之間通過(guò)一些有向邊連接起來(lái)，這種有向圖稱(chēng)為程序流圖或流圖。218.2.2基本塊的DAG表示8.2.2基本塊的DAG表示

為了便于對(duì)基本塊進(jìn)行優(yōu)化，引進(jìn)一種有效的數(shù)據(jù)結(jié)構(gòu)——無(wú)回路有向圖(DirectedAcyclicGraph，DAG)。228.2.2基本塊的DAG表示

圖8.2一個(gè)帶環(huán)路的有向圖圖8.3一個(gè)無(wú)環(huán)路的有向圖238.2.2基本塊的DAG表示(1)(=,3.14,_,

T1)(2)(*,2,

T1

,T2)(3)(+,R,r,

T3)(4)(*,T2

,T3

,A)(5)(=,A,_,

B)(6)(*,2,

T1

,T4)(7)(+,R,r,

T5)(8)(*,T4

,T5

,T6)(9)(?,R,

r,T7)(10)(*,T5

,T7

,

B)例題8.2構(gòu)造以下基本塊G1的DAG248.2.2基本塊的DAG表示利用算法8.2對(duì)以上基本塊中10個(gè)四元式逐個(gè)進(jìn)行處理，新產(chǎn)生的DAG

子圖依次如圖8.5(a)~(j)所示，其中，圖8.5(j)即為要構(gòu)造的DAG。圖8.5基本塊G

的

DAG258.2.3基本塊優(yōu)化的實(shí)現(xiàn)將四元式表示成相應(yīng)的DAG

后，就可利用DAG對(duì)基本塊進(jìn)行優(yōu)化。實(shí)際上，在對(duì)基本塊執(zhí)行算法8.2的過(guò)程中，已完成了對(duì)基本塊進(jìn)行優(yōu)化的一系列基本工作。268.2.3基本塊優(yōu)化的實(shí)現(xiàn)利用這樣的DAG，按照原來(lái)構(gòu)造其節(jié)點(diǎn)的順序，重建四元式序列G2如下：(=,3.14,_,T1)(2)(=,6.28,_,T2)(3)(=,6.28,_,T4)(4)(+,R,r,T3)(5)(=,T3,_,T5)(6)(*,6.28,T3,A)(7)(=,A,_,T6)(8)(_,R,r,T7)(9)(=,T5,T7,B)278.3循環(huán)優(yōu)化循環(huán)是程序設(shè)計(jì)中一種重要的數(shù)據(jù)結(jié)構(gòu)，程序運(yùn)行時(shí)花費(fèi)在循環(huán)上的時(shí)間往往占整個(gè)運(yùn)行時(shí)間的很大部分，因此對(duì)循環(huán)的優(yōu)化實(shí)為提高程序運(yùn)行效率的重要途徑。對(duì)循環(huán)的優(yōu)化實(shí)為提高程序運(yùn)行效率的重要途徑。288.3.1循環(huán)的查找為了進(jìn)行循環(huán)的優(yōu)化，首先要查找程序中的循環(huán)。在程序流圖中，具有下列性質(zhì)的節(jié)點(diǎn)序列(即一組基本塊)稱(chēng)為程序中的一個(gè)循環(huán)：①在這組節(jié)點(diǎn)中，有且只有一個(gè)是入口節(jié)點(diǎn)。②這組節(jié)點(diǎn)是強(qiáng)連通的，即任意兩個(gè)節(jié)點(diǎn)之間必有一條通路(特別當(dāng)這組節(jié)點(diǎn)僅含一個(gè)節(jié)點(diǎn)時(shí)，必有從此節(jié)點(diǎn)到其自身的有向邊)。298.3.1循環(huán)的查找【例8.3】圖8.6是一個(gè)程序流圖。按照上述關(guān)于循環(huán)的定義可知，圖8.6中，節(jié)點(diǎn)序列{6，7，8}以及{4，6，7，8}、{4，5，6，7，8}、{3，4，5，6，7，8}都是循環(huán)；而節(jié)點(diǎn)序列{3，4}、{4，5，6，7}雖然是強(qiáng)連通的，但因它們的入口節(jié)點(diǎn)不唯一，所以不是循環(huán)。圖8.6一個(gè)程序流圖308.3.2循環(huán)優(yōu)化的實(shí)現(xiàn)循環(huán)優(yōu)化的三種主要技術(shù)削減運(yùn)算強(qiáng)度外提循環(huán)中的不變表達(dá)式刪除歸納變量1、外提循環(huán)中的不變表達(dá)式318.3.2循環(huán)優(yōu)化的實(shí)現(xiàn)所謂循環(huán)中的不變表達(dá)式是指該表達(dá)式的值不隨循環(huán)的重復(fù)執(zhí)行而改變。為了實(shí)現(xiàn)循環(huán)中不變表達(dá)式的外提，需解決如下三個(gè)問(wèn)題：①如何查找循環(huán)中的不變表達(dá)式；②找到的不變表達(dá)式是否可以外提；③把不變表達(dá)式提到循環(huán)外的什么地方。328.3.2循環(huán)優(yōu)化的實(shí)現(xiàn)相關(guān)概念：（1）變量的“定值點(diǎn)”：是指在四元式序列中變量被賦值或輸入值的某一四元式的位置。（2）變量的“引用點(diǎn)”：是指在四元式序列中變量被引用的某一四元式的位置。（3）“到達(dá)一定值點(diǎn)”：是指變量在某點(diǎn)定值后到達(dá)的一點(diǎn)。（4）“活躍變量”：是指在流圖中，從某一點(diǎn)P出發(fā)的通路上有該變量的引用點(diǎn)。（5）“循環(huán)的前置節(jié)點(diǎn)”：是指在循環(huán)的入口節(jié)點(diǎn)前面建立一個(gè)新節(jié)點(diǎn)(基本塊)。338.3.2循環(huán)優(yōu)化的實(shí)現(xiàn)例題、

x=10,y=20時(shí)，執(zhí)行路徑為B2→B3→B4→B5

，j=2;x=30,y=22時(shí)，執(zhí)行路徑為B2

→B4

→B2

→B4

→B5,j=1。圖8.7在循環(huán)L

前設(shè)置前置節(jié)點(diǎn)圖8.8程序流程一2、削減運(yùn)算強(qiáng)度348.3.2循環(huán)優(yōu)化的實(shí)現(xiàn)

削減運(yùn)算強(qiáng)度是把程序中執(zhí)行時(shí)間較長(zhǎng)的運(yùn)算替換為執(zhí)行時(shí)間較短的運(yùn)算，以提高目標(biāo)程序的執(zhí)行效率。358.3.2循環(huán)優(yōu)化的實(shí)現(xiàn)例如，對(duì)于如下循環(huán)語(yǔ)句:i=a;while(i<=b){…

x=i*k…}把循環(huán)中的乘法運(yùn)算用遞歸加法運(yùn)算來(lái)實(shí)現(xiàn)。368.3.2循環(huán)優(yōu)化的實(shí)現(xiàn)假定k和n都是在循環(huán)中不變的常量，且在循環(huán)中沒(méi)有x

的其他定值點(diǎn)，那