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

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

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

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

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

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

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

目前許多編譯程序采用語法制導翻譯的方法。

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

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

α∈V*語義動作

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

117.1.2屬性文法技術(shù)

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

E

TE’FT’-T

E’

12

ε

FT’ε

a

/

F

T’

b

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

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

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

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

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

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

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

其它結(jié)點：表示運算符。

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

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

SV:=ExE-EaE*Ebc抽象語法樹的特點：結(jié)構(gòu)緊湊、容易構(gòu)造、結(jié)點數(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

約定幾個符號：

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

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

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

（4）BR表示無條件轉(zhuǎn)7.2.2逆波蘭表示（后綴式）201.賦值語句的逆波蘭式<左部>:=<表達式><左部><表達式>:=例:x:=a+b*cx:=a*b-c/dxabc*+:=xab*cd/-:=7.2.2逆波蘭表示（后綴式）217.2.2逆波蘭表示（后綴式）2.GOTO語句的逆波蘭式GOTO<語句標號><語句標號>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.四元式

(運算符,運算量1,運算量2,中間結(jié)果)例:a*b+c*d(*,a,b,T1)(*,c,d,T2)(+,T1,T2,T3)對于單目運算符⊕,?如+a，-a（⊕，a，_，T）（?，a，_，T）287.2.3四元式2.表達式和賦值語句的四元式例:(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為真時轉(zhuǎn)到A處(BF,A,B,_)B為假時轉(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.三元式

(運算符,運算量1,運算量2)例:(a+b)*c(1)(+,a,b)(2)(*,(1),c)337.2.4三元式2.表達式和賦值語句的三元式例: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)缺點優(yōu)點無需臨時變量占用空間少缺點沒有保存運算結(jié)果的屬性不利于修改、優(yōu)化377.3語法制導翻譯語法制導翻譯，直觀上說就是為每個文法規(guī)則確定相應(yīng)的語義，編寫相應(yīng)的翻譯程序。7.3.1表達式的翻譯387.3.4控制語句的翻譯7.3.2說明語句的翻譯7.3.3賦值語句的翻譯7.3.1表達式翻譯表達式是語言中最基本的語法成分表達式是源程序中出現(xiàn)頻率很高的語法成分391.語法規(guī)則與代碼形式

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

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

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

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

print(*)print(/)空空

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

→E+T|E*T|?E

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

(

1)+E

(2)E→E

(

1)*E(2)

E→?E(

1)E→

(E(

1))語義動作{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è)計語言中最簡單的說明語句是用一個基本字來定義一串名字的某種性質(zhì)。Pascal語言中，變量說明部分冠以保留字VAR

作為標志，例如：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ù)說明的語法制導翻譯改寫如下：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、賦值語句的語義

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

的值賦給左部變量V。7.3.3

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

gen(w,c,d,e);beginP[n]:=(w,c,d,e);n:=n+1end；賦值語句的語法規(guī)則對應(yīng)的語義子程序為(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

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

等語句實現(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)移目標位置的確定和語句所處的環(huán)境是密切相關(guān)的。7.3.4

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

SLabel→L:7.3.4

控制語句的翻譯53轉(zhuǎn)向語句和帶標號語句的語法規(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．語法制導翻譯的概念及其翻譯的主要思想4．表達式是在源程序中出現(xiàn)頻率較高的語法成分5．變量說明的翻譯，過程或函數(shù)說明的語法制導翻譯6．賦值語句、控制語句的翻譯55總結(jié)

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

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

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

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

軟件構(gòu)造582024/11/659學習目標代碼優(yōu)化的概念循環(huán)優(yōu)化局部優(yōu)化代碼優(yōu)化的分類8代碼優(yōu)化重點：代碼優(yōu)化的定義和代碼優(yōu)化的分類難點：局部優(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)化，實質(zhì)上是對代碼進行等價變換，使得變換后的代碼具有更高的效率，包括時間效率和空間效率。目的

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

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

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

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

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

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

基本程序塊---只有一個入口、一個出口的基本程序塊

合并常量和已知量

消除公共子表達式

削減運算強度

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

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

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

削減計算強度

刪除歸納變量1、合并常量運算

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

例：

x:=3.14*2;y:=2*5*a;z:=x+0.5;合并常量運算后： 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、刪除無用賦值

刪除程序中對運行結(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、削減運算強度（運算強度大→?。?/p>

例：

fori:=1to100doa:=10*i；削減運算強度后：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、刪除多余運算(或刪除公共子表達式)公共子表達式：重復使用兩次以上的子表達式，且表達式中變量的值沒有發(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、外提不變表達式不變表達式：循環(huán)中其值始終保持不變的表達式

例：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;一個基本塊不是一個基本塊

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

基本塊，是指程序中一組順序執(zhí)行的語句序列，其中只有一個入口和一個出口，執(zhí)行時只能從其入口進入，從其出口退出。即基本塊內(nèi)的運算要么都被執(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可以看出，以上程序段可以劃分為四個基本塊B1、B2、B3、B4

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

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

圖8.2一個帶環(huán)路的有向圖圖8.3一個無環(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個四元式逐個進行處理，新產(chǎn)生的DAG

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

的

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

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