編譯原理簡明教程（第3版）-課件 第7、8章 語義分析及中間代碼的生成、代碼優(yōu)化

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

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

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

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

軟件構(gòu)造22024/11/63學(xué)習(xí)目標(biāo)語義分析的概念語法制導(dǎo)翻譯常見語法成分的表示中間代碼語言7語義分析及中間代碼的生成重點(diǎn)：語義分析的概念、常見的中間語言形式難點(diǎn)：常見語法成分的表示

目錄7.1語義分析概述7.2中間語言代碼7.3語法制導(dǎo)翻譯7.4本章小結(jié)47.1.1語義分析的概念5語義分析：分析語法結(jié)構(gòu)的含義，將其表示成中間語言或生成目標(biāo)指令。語義形式化(或形式語義學(xué))：是個(gè)專門的研究課題，如操作語義學(xué)、公理語義學(xué)、指稱語義學(xué)等。不論哪種方法，其本身的符號系統(tǒng)比較繁雜，其描述文本不易讀，因此都不能成為標(biāo)準(zhǔn)的形式語義系統(tǒng)。7.1.1語義分析的概念6主要指程序中所用標(biāo)識(shí)符及與其相關(guān)的數(shù)據(jù)對象的含義如if語句、for循環(huán)等結(jié)構(gòu)；由語言來定義。7.1.1語義分析的概念7語義分析的基本任務(wù)：類型的確定類型的檢查確認(rèn)含義其他語義檢查數(shù)據(jù)對象的數(shù)據(jù)類型對運(yùn)算及運(yùn)算量的類型檢查確認(rèn)控制結(jié)構(gòu)的含義不允許體外到體內(nèi)等7.1.1語義分析的概念控制結(jié)構(gòu)的含義有兩種確定形式：形式化：如E→E+T|E-T|T

先“*，/”后“+，-”T→T*F|T/F|F左結(jié)合……p→(E)|i非形式：如賦值語句含義，非形式化的規(guī)定

V：=e

87.1.2屬性文法技術(shù)

目前許多編譯程序采用語法制導(dǎo)翻譯的方法。

不是一種形式化系統(tǒng)，但比較接近形式化。以語法分析為主導(dǎo)的語義處理，即在語法分析的過程中嵌入語義處理程序，生成中間代碼或目標(biāo)代碼。97.1.2屬性文法技術(shù)1.增量式文法文法中加入語義動(dòng)作符號。一般形式：A

(α|{f（…）；})*

α∈V*語義動(dòng)作

作用：在語法分析時(shí)，遇到帶有語義動(dòng)作的花括號即執(zhí)行語義動(dòng)作，執(zhí)行完后再進(jìn)行下一步分析。10為了實(shí)現(xiàn)語法制導(dǎo)翻譯，對文法中終結(jié)符號和非終結(jié)符號引進(jìn)一些屬性，例如，變量的數(shù)據(jù)類型、表達(dá)式的值以及存儲(chǔ)器中變量的地址等。以描述相應(yīng)語言結(jié)構(gòu)的語義值。7.1.2屬性文法技術(shù)例：表達(dá)式文法G[E]：

117.1.2屬性文法技術(shù)

對于表達(dá)式“12-a/b”，語法樹如下：

E

TE’FT’-T

E’

12

ε

FT’ε

a

/

F

T’

b

ε127.1.2屬性文法技術(shù)

對于表達(dá)式“12-a/b”，帶有語義動(dòng)作的語法樹如下：

E

TE’FT’-T{writecode(‘-’)}E’

12{writecode(‘12’)}εFT’

ε

a{writecode(‘a(chǎn)’)}/F{writecode(‘/’)}T’

b{writecode(‘b’)}

ε

13執(zhí)行相應(yīng)的子程序后打印出逆波蘭式12ab/-7.1.2屬性文法技術(shù)2.屬性文法（1）文法的屬性:

指與文法符號相關(guān)信息,如它的類型、值、代碼序列、符號表內(nèi)容等。

繼承屬性：用于“自上而下”傳遞信息（非終結(jié)符可有）

綜合屬性：用于“自下而上”傳遞信息（VT或VN）

（2）屬性文法：

指在語言的文法中增加了屬性的文法。

記號N.t表示與非終結(jié)符N相聯(lián)的屬性t

屬性有助于更詳細(xì)地指定文法中的代碼生成動(dòng)作。147.1.2屬性文法技術(shù)例：G[E]屬性文法：157.2中間語言代碼采用中間語言的優(yōu)點(diǎn)：有利于重定目標(biāo),即一種中間表示可以生成不同的目標(biāo)語言。有利于提高目標(biāo)代碼的質(zhì)量，因?yàn)榭蓪χ虚g語言進(jìn)行與機(jī)器無關(guān)的優(yōu)化。

常見的中間語言有：抽象語法樹、逆波蘭式、四元式、三元式。167.2.1抽象語法樹抽象語法樹：經(jīng)變換后的語法樹

(去掉一些對翻譯不必要的信息)。

葉結(jié)點(diǎn)：表示運(yùn)算對象，如常量或變量。

其它結(jié)點(diǎn)：表示運(yùn)算符。

在語法規(guī)則中有些符號起標(biāo)點(diǎn)符號或解釋的作用。17如：x:=a-b*c

語法樹和抽象語法樹如下：

SV:=ExE-EaE*Ebc抽象語法樹的特點(diǎn)：結(jié)構(gòu)緊湊、容易構(gòu)造、結(jié)點(diǎn)數(shù)少的圖形表示。assign(:=)x-a*bc7.2.1抽象語法樹187.2.2逆波蘭表示（后綴式）例：a+b*cabc*+(a+b)*cab+c*a+b*c/(d-e)abc*de-/++a/*-bcde抽象語法樹逆波蘭式是抽象語法樹的線性表示。即：后序遍歷抽象語法樹便得到逆波蘭式19

約定幾個(gè)符號：

（1）BL表示轉(zhuǎn)向某標(biāo)號處

（2）BT表示條件為真轉(zhuǎn)

（3）BF表示條件為假轉(zhuǎn)

（4）BR表示無條件轉(zhuǎn)7.2.2逆波蘭表示（后綴式）201.賦值語句的逆波蘭式<左部>:=<表達(dá)式><左部><表達(dá)式>:=例:x:=a+b*cx:=a*b-c/dxabc*+:=xab*cd/-:=7.2.2逆波蘭表示（后綴式）217.2.2逆波蘭表示（后綴式）2.GOTO語句的逆波蘭式GOTO<語句標(biāo)號><語句標(biāo)號>BL例:GOTO1010BL227.2.2逆波蘭表示（后綴式）3.條件語句的逆波蘭表示IF(e)THENS1ELSES2逆波蘭式:<e的逆波蘭式><順序號1>BF<S1的逆波蘭式><順序號2>BR<S2的逆波蘭式>237.2.2逆波蘭表示（后綴式）例:IFm<nTHENk:=i*j+2ELSEk:=i*j-2(1)mn<(4)15BF(6)kij*2+:=(13)22BR(15)kij*2-:=(22)或:mn<15BFkij*222BRkij*2-:=247.2.2逆波蘭表示（后綴式）例：if(a<b)thenx:=a+belsex:=a-b(1)ab<(4)13BF(6)xab+:=(11)18BR(13)xab-:=(18)或:ab<13BFxab+:=18BRxab-:=257.2.2逆波蘭表示（后綴式）4.循環(huán)語句的逆波蘭式Fori:=mTonDosfor(i=m;i<=n;i++){s}首先展開，i:=m;10:IFi<=nTHENBEGINS;i:=i+1;GOTO10;END267.2.2逆波蘭表示（后綴式）例：FORi=1TO100DOs:=s+i展開

i:=1;10:IFi<=100THEN

BEGINs:=s+i;i:=i+1;GOTO10END

(1)i1:=(4)10:(6)i100<=23BF(11)ssi+:=(16)ii1+:=(21)10BL(23)277.2.3四元式1.四元式

(運(yùn)算符,運(yùn)算量1,運(yùn)算量2,中間結(jié)果)例:a*b+c*d(*,a,b,T1)(*,c,d,T2)(+,T1,T2,T3)對于單目運(yùn)算符⊕,?如+a，-a（⊕，a，_，T）（?，a，_，T）287.2.3四元式2.表達(dá)式和賦值語句的四元式例:(1)a+b*c/d(*,b,c,T1)(/,T1,d,T2)(+,a,T2,T3)

(2)-b*(c+d)(?,b,_,T1)

(+,c,d,T2)(*,T1,T2,T3)

(3)x:=-b*(c+d)(?,b,_,T1)(+,c,d,T2)(*,T1,T2,T3)(:=,T3,_,x)297.2.3四元式3.轉(zhuǎn)向語句和條件語句的四元式(BR,A,_,_)無條件轉(zhuǎn)到序號如A處(BT,A,B,_)B為真時(shí)轉(zhuǎn)到A處(BF,A,B,_)B為假時(shí)轉(zhuǎn)到A處307.2.3四元式例:IFa>bTHENmax:=aELSEmax:=b

四元式(1)(>,a,b,T1)(2)(BF,(5),T1,_)(3)(:=,a,_,max)(4)(BR,(6),_,_)(5)(:=,b,_,max)(6)()317.2.3四元式4.

循環(huán)語句的四元式FORi:=1TO100DOs:=s+i首先展開

四元式:(1)(:=,1,_,i)

i:=1

(2)(<=,i,100,T1)

10:IFi<=100THEN

(3)(BF,(7),T1,_)

BEGIN

(4)(+,s,i,s)

s:=s+i;

(5)(+,i,1,i)i:=

i+1;

(6)(BR,(2),_,_)GOTO10;

(7)END

327.2.4三元式1.三元式

(運(yùn)算符,運(yùn)算量1,運(yùn)算量2)例:(a+b)*c(1)(+,a,b)(2)(*,(1),c)337.2.4三元式2.表達(dá)式和賦值語句的三元式例:a*(b-c)/d+e(1)(-,b,c)(2)(*,a,(1))(3)(/,(2),d)(4)(+,(3),e)X:=a*(b-c)/d+e(5)(:=,(4),x)a+b*(c-d)-e/f(1)(-,c,d)(2)(*,b,(1))(3)(+,a,(2))(4)(/,e,f)(5)(-,(3),(4))347.2.4三元式3.轉(zhuǎn)向語句和條件語句的三元式IFa<bTHENx:=a+bELSEx:=a-b(1)(<,a,b)(2)(BF,(6),(1))(3)(+,a,b)(4)(:=,(3),x)(5)(BR,(8),_)(6)(-,a,b)(7)(:=,(6),x)(8)357.2.4三元式4.循環(huán)語句的三元式FORi:=1TO100DOsum:=sum+i首先展開：三元式：i:=1

(1)(:=,1,i)10:IFi<=100THEN(2)(<=,i,100)BEGIN

(3)(BF,(9),(2))sum:=sum+i;(4)(+,sum,i)i:=i+1;(5)(:=,(4),sum)GOTO10(6)(+,i,1)END(7)(:=,(6),i)(8)(BR,(2),_)(9)367.2.4三元式三元式的優(yōu)缺點(diǎn)優(yōu)點(diǎn)無需臨時(shí)變量占用空間少缺點(diǎn)沒有保存運(yùn)算結(jié)果的屬性不利于修改、優(yōu)化377.3語法制導(dǎo)翻譯語法制導(dǎo)翻譯，直觀上說就是為每個(gè)文法規(guī)則確定相應(yīng)的語義，編寫相應(yīng)的翻譯程序。7.3.1表達(dá)式的翻譯387.3.4控制語句的翻譯7.3.2說明語句的翻譯7.3.3賦值語句的翻譯7.3.1表達(dá)式翻譯表達(dá)式是語言中最基本的語法成分表達(dá)式是源程序中出現(xiàn)頻率很高的語法成分391.語法規(guī)則與代碼形式

7.3.1表達(dá)式翻譯40(1).算數(shù)表達(dá)式的逆波蘭表示的語法制導(dǎo)翻譯

語法規(guī)則E→E+T

E→E?TE→TT→T*FT→T/FT→FF→(E)

F→i語義子程序print(+)print(-)空

print(*)print(/)空空

print(id7.3.1表達(dá)式翻譯41(2).算數(shù)表達(dá)式到四元式的語法制導(dǎo)翻譯表達(dá)式文法：E

→E+T|E*T|?E

|(E)|i的翻譯算法可由下面的語義動(dòng)作予以描述：語法規(guī)則E→E

(

1)+E

(2)E→E

(

1)*E(2)

E→?E(

1)E→

(E(

1))語義動(dòng)作{E.place:=Newtemp;gen(+,E(1).place,E(2).place,E.place)}{E.place:=Newtemp;gen(*,E(1).place,E(2).place,E.place)}{E.place:=Newtemp;gen(Θ,E(1).place,_,E.place)}{E.place:=E(1).place}{E.place:=entry(i)}7.3.2說明語句的翻譯421、變量說明的翻譯程序設(shè)計(jì)語言中最簡單的說明語句是用一個(gè)基本字來定義一串名字的某種性質(zhì)。Pascal語言中，變量說明部分冠以保留字VAR

作為標(biāo)志，例如：VARm,n:integer;x,y:real;a:ARRAY[1..100]OFreal;7.3.2說明語句的翻譯432、過程或函數(shù)說明的翻譯

過程和函數(shù)說明又可以包含說明部分和語句部分，因此過程和函數(shù)是分程序，且可以嵌套。過程說明和函數(shù)說明的語法規(guī)則為:Pf→P|FP→Procedure

id(xy);

BLOF→functionid(xy):fnamet;BLOBLO→LB

CON

TP

VA

Pfs

begin

StatendPfs→Pf|PfsPfStat→S|Stat;S7.3.2說明語句的翻譯44其四元式為(1)(proc,p,L1,k1)(2)(func,f,L2,k2)(3)(+,i,j,T1)(4)(/,T1,2,T2)(5)(:=,T2,_,f)(6)(funend,_,_,_)(7)(/,x2,2,T3)(8)(+,num,T3,T4)(9)(:=,T4,_,X1)(10)(*,m,x1,T5)(11)(:=,T5,_,a1)(12)(proend,_,_,_)過程說明：Procedure

p(varx1:real;x2:real);const

num=100;var

a1:real;m:integer;function

f(i,j:ineger):integer;beginf:=(i+j)/2end;beginx1:=num+x2/2；a1:=m*x1end;7.3.2說明語句的翻譯45將前述過程和函數(shù)說明的語法制導(dǎo)翻譯改寫如下：Pf→P|FP→Pidxy);BLOF→Fid

xy);fnamet;BLOPid→procedure

id(Fid→function

id(Pfs→Pf|PfsPfBLO→LB

CON

TP

VA

Pfs

begin

Statend7.3.2說明語句的翻譯46從而有與語法規(guī)則相應(yīng)的語義子程序如下：(1)pf→p{}/*空*/(2)pf→f

{}/*空*/(3)p→pid

xy);BLO{gen(proend,_,_,_)(4)F→Fid

xy);fnamet;BLO{gen(funend,_,_,_)}(5)Pid→Procedure

id(

{gen(proc,adr(id),L,k)(6)Fid→function

id(

{gen

(func,adr(id),L,k,)}(7)Pfs→pf{}/*空*/(8)Pfs→Pfs

Pf7.3.3

賦值語句的翻譯471、賦值語句的語法規(guī)則S→V:=E2、賦值語句的語義

賦值語句的語義可解釋為把右部表達(dá)式E

的值賦給左部變量V。7.3.3

賦值語句的翻譯483、語法制導(dǎo)翻譯技術(shù)其引進(jìn)的四元式生成子程序表示形式為：Procedure

gen(w,c,d,e);beginP[n]:=(w,c,d,e);n:=n+1end；賦值語句的語法規(guī)則對應(yīng)的語義子程序?yàn)?1)S→Assig

E{gen(:=,S[i-2],_,s[i-1])}(2)Assig→i:={S[i]:=adr(id),i:=i+1}7.3.4

控制語句的翻譯49

在源程序中，控制語句用于實(shí)現(xiàn)程序流程的控制，一般程序流程控制分為三種基本結(jié)構(gòu)：順序結(jié)構(gòu)，一般用復(fù)合語句實(shí)現(xiàn)。選擇結(jié)構(gòu)，用if和case等語句實(shí)現(xiàn)。循環(huán)結(jié)構(gòu)，用for、while、repeat

等語句實(shí)現(xiàn)。

7.3.4

控制語句的翻譯501．三種基本控制結(jié)構(gòu)的翻譯:三種結(jié)構(gòu)可用如下方法描述：(1)S→ifEthenS(2)|if

E

thenSelseS(3)|whileEdo

S(4)|begin

L

end(5)|A(6)L→L;S(7)|S7.3.4

控制語句的翻譯51對于下面嵌套的if語句：

在E1和E2為真的情況下執(zhí)行S1，執(zhí)行完S1之后的那條無條件轉(zhuǎn)移指令不僅應(yīng)跳過S2代碼，還應(yīng)跳過S3代碼。這也就是說，轉(zhuǎn)移目標(biāo)位置的確定和語句所處的環(huán)境是密切相關(guān)的。7.3.4

控制語句的翻譯522.語句標(biāo)號和轉(zhuǎn)移語句的翻譯:大多數(shù)程序設(shè)計(jì)語言中的轉(zhuǎn)移語句是通過標(biāo)號和goto語句實(shí)現(xiàn)的，語句標(biāo)號用于標(biāo)識(shí)一個(gè)語句，一個(gè)帶標(biāo)號語句的形式是L:S帶標(biāo)號語句的語法規(guī)則為Ls→L:S轉(zhuǎn)向語句的語法規(guī)則為S→gotoL為便于語法制導(dǎo)翻譯，帶標(biāo)號語句的語法規(guī)則改寫為LS→Label

SLabel→L:7.3.4

控制語句的翻譯53轉(zhuǎn)向語句和帶標(biāo)號語句的語法規(guī)則對應(yīng)的語義子程序如下：S→gotoL{gen(goto,_,_,L)}Ls→Label

S{空}Label→L:{gen(label,_,_,L)}547.4本章小結(jié)1．語義分析就是分析語法結(jié)構(gòu)含義，語義分析部分以語法分析部分的輸出作為輸入2．四種中間語言代碼：抽象語法樹、逆波蘭表示、四元式和三元式3．語法制導(dǎo)翻譯的概念及其翻譯的主要思想4．表達(dá)式是在源程序中出現(xiàn)頻率較高的語法成分5．變量說明的翻譯，過程或函數(shù)說明的語法制導(dǎo)翻譯6．賦值語句、控制語句的翻譯55總結(jié)

本章我們學(xué)習(xí)了語義分析的基本概念，屬性文法技術(shù)及常用的中間代碼（抽象語法樹、逆波蘭式、四元式、三元式）等內(nèi)容。下一章將學(xué)習(xí)代碼優(yōu)化。THANKS56THANKS新工科建設(shè)·計(jì)算機(jī)類系列教材

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

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

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

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

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

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

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

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

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

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

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

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

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

合并常量和已知量

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

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

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

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

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

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

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

運(yùn)算對象是常量或在編譯時(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;658.1.3優(yōu)化技術(shù)簡介優(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)

662、刪除無用賦值

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

例：

x:=2+a；

y:=2+b；

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

y:=2+b；

x:=2*a*b;y:=x*y;67優(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)

683、削減運(yùn)算強(qiáng)度（運(yùn)算強(qiáng)度大→小）

例：

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)()694、刪除多余運(yùn)算(或刪除公共子表達(dá)式)公共子表達(dá)式：重復(fù)使用兩次以上的子表達(dá)式，且表達(dá)式中變量的值沒有發(fā)生變化。

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

70優(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)

715、外提不變表達(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；end72優(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)( )

73優(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)( )

74758.2局部優(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è)基本塊

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

基本塊，是指程序中一組順序執(zhí)行的語句序列，其中只有一個(gè)入口和一個(gè)出口，執(zhí)行時(shí)只能從其入口進(jìn)入，從其出口退出。即基本塊內(nèi)的運(yùn)算要么都被執(zhí)行，要么都不執(zhí)行。768.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

，而且各基本塊之間通過一些有向邊連接起來，這種有向圖稱為程序流圖或流圖。778.2.2基本塊的DAG表示8.2.2基本塊的DAG表示

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

圖8.2一個(gè)帶環(huán)路的有向圖圖8.3一個(gè)無環(huán)路的有向圖798.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的DAG808.2.2基本塊的DAG表示利用算法8.2對以上基本塊中10個(gè)四元式逐個(gè)進(jìn)行處理，新產(chǎn)生的DAG

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

的

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

后，就可利用DAG對基本塊進(jìn)行優(yōu)化。實(shí)際上，在對基本塊執(zhí)行算法8.2的過程中，已完成了對基本塊進(jìn)行優(yōu)化的一系列基本工作。828.2.3基本塊優(yōu)化的實(shí)現(xiàn)利用這樣的DAG，按照原來構(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)838.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í)間的很大部分，因此對循環(huán)的優(yōu)化實(shí)為提高程序運(yùn)行效率的重要途徑。對循環(huán)的優(yōu)化實(shí)為提高程序運(yùn)行效率的重要途徑。848.3.1循環(huán)的查找為了進(jìn)行循環(huán)的優(yōu)化，首先要查找程序中的循環(huán)。在程序流圖中，具有下列性質(zhì)的節(jié)點(diǎn)序列(即一組基本塊)稱為程序中的一個(gè)循環(huán)：