編譯原理演示文稿7.ppt

1、第七章 編譯程序 7.1 編譯程序考慮的因素 編譯程序設(shè)計時，除了需用到前介紹的分析技術(shù)和制導(dǎo)翻譯技術(shù)外，還要考慮如何從源程序數(shù)據(jù)空間映射到具體物理存儲空間，也就是運行時的數(shù)據(jù)表示。在運行時如何組織或存放數(shù)據(jù)、在源程序中同名標識符是怎樣描述不同的對象、運行時的程序控制權(quán)是如何轉(zhuǎn)移和參數(shù)是如何傳遞的以及如何生成質(zhì)量較高的目標代碼都是編譯程序設(shè)計者需考慮的問題。,7.1.1 數(shù)據(jù)類型 類型的合法性檢查是判斷數(shù)據(jù)的類型是否與上下文的要求相一致，例如Pascal的運算符+不能作用在字符型數(shù)據(jù)上，而C語言的+卻能作用在字符型數(shù)據(jù)上。在數(shù)據(jù)類型上定義的各種運算通常包括賦值和一系列類型轉(zhuǎn)換規(guī)則，這些規(guī)則保證

2、了作用在數(shù)據(jù)對象上的某個運算符順便通過由編譯程序的類型的合法性檢查，并實現(xiàn)其合法的算和賦值。因此，給出定義： 定義7.1 數(shù)據(jù)類型是對該類型數(shù)據(jù)（變量或常量）的取值是否合法以及對該類型據(jù)的運算是否合法的一種說明。,實現(xiàn)和完成數(shù)據(jù)類型的合法性檢查，它包括以下任務(wù)： (1) 檢查運算符作用在運算對象上的合法性，這一合法性保證了該運算能產(chǎn)生正確的運算結(jié)果。 (2) 根據(jù)程序設(shè)計語言運算符的類型轉(zhuǎn)換規(guī)則，將一種類型數(shù)據(jù)轉(zhuǎn)換成另一種數(shù)據(jù)類型。 (3) 能夠使用相應(yīng)的目標機器指令實現(xiàn)這種在上述類型上定義的運算。,例:設(shè)有Pascal程序段 var a,b:integer; x:real; begin re

3、ad(a); b:=10; x:=a mod b; a:=a-x*10 end;,對于讀語句read(a)和賦值語句b:=10都滿足簡單的類型檢查。在賦值語句x:=a mod b中雖然a mod b的結(jié)果是整型的，但仍能滿足將a mod b的結(jié)果賦給實型變量x。這是因為在Pascal中定義了將整型轉(zhuǎn)換成實型的轉(zhuǎn)換規(guī)則，因而編譯程序需生成將a mod b的結(jié)果轉(zhuǎn)換成實型的指令代碼。而對于語句a:=a-x*10，雖然通過Pascal定義的類型規(guī)則可以將a轉(zhuǎn)換成實型，求出a-x*10的結(jié)果類型為實型，但Pascal不允許將實型賦給整型，則出錯。,例:設(shè)有C語言程序段 int a,b; real x;

4、 scanf(“%d”, ,可以看出，上述二個程序段期望完成的功能是一樣的，但前者不能通過編譯，而后者能順利通過編譯的類型檢查，這是因為C語言中賦值語句a:=a-x*10中也包含了強制將實型轉(zhuǎn)換成整型。 根據(jù)語言的類型定義方式，可以將類型分為基本類型和構(gòu)造類型，基本類型是指系統(tǒng)已定義的數(shù)據(jù)類型，如C語言中的整型、浮點型（實型）、字符型。構(gòu)造類型的指通過基本類型或已定義的類型構(gòu)造出的新的數(shù)據(jù)類型，如Pascal中的數(shù)組、記錄和集合。引進了構(gòu)造類型后，類型的合法性檢查變得復(fù)雜。其檢查方法有二大類，一類是名字等價，另一類是結(jié)構(gòu)等價。 所謂名字等價也就是如果二個類型是等價的，當且僅當二個類型的名字或與

5、類型名字的別名是等價的。,例:設(shè)有Pascal程序段 type int=integer; var a:integer; b:integer; c:int; a和b是同一類型名integer故它們是等價的；雖然a和c的類型名不同，但是int是integer的一種別名，故a和c的類型還是等價的。 所謂結(jié)構(gòu)等價也就是如果二個類型是等價的，當且僅當二個類型具有相同的類型表達式。,定義7.2 類型表達式是遞歸定義的: (1) 類型表達式是基本數(shù)據(jù)類型 (2) 類型表達式是由數(shù)組、記錄、集合、指針、函數(shù)等作用在類型表達式上的類型。 檢查類型的名字等價相對簡單，只要為定義的類型名建立一張符號表，通過查表就可

6、以判定二個類型是否名字等價。雖然，對于類型的等價的直觀概念是結(jié)構(gòu)等價，但結(jié)構(gòu)等價檢查的實現(xiàn)方法稍復(fù)雜。需為每個類型建立表示類型的結(jié)構(gòu)樹或無環(huán)有向圖，如圖為類型。 record name :array1.20 of char; age:integer end; 的樹結(jié)構(gòu)表示。 其中，array中的integer 表示下標的類型,對于如說明鏈表或樹的數(shù)據(jù)結(jié)構(gòu)的定義時，需遞歸定義。因此遞歸定義的類型圖為無環(huán)有向圖。圖為類型 type link=node; node=record name :array1.20 of char; next:link end; 的無環(huán)有向圖。,檢查二個類型是結(jié)構(gòu)等價，只

7、要二個類型結(jié)構(gòu)樹或無環(huán)有向圖相等即可。檢查類型等價也分成靜態(tài)檢查和動態(tài)檢查。由編譯程序能完成的類型檢查叫做靜態(tài)類型檢查；由目標程序運行時所作的類型檢查就稱為動態(tài)類型檢查。一般地，如果要在生成的目標代碼中完成類型檢查，則目標代中不但要保存數(shù)據(jù)的值，而且還保存該數(shù)據(jù)的類型，則可完工成相應(yīng)的動態(tài)類型檢查。因算法語言的類型檢查多數(shù)是靜態(tài)的類型檢查，在這里僅介紹了靜態(tài)的類型檢查。,7.1.2 數(shù)據(jù)結(jié)構(gòu) 一種程序設(shè)計語言如允許使用的數(shù)組、記錄、集合、字符串、表、棧等形式的數(shù)據(jù)結(jié)構(gòu)，在編譯程序中應(yīng)為它們提供相應(yīng)的翻譯。為了能對這些數(shù)據(jù)結(jié)構(gòu)中的元素的引用，編譯程序必須完成從這些數(shù)據(jù)的邏輯結(jié)構(gòu)到訪問這些數(shù)據(jù)元素

8、的物理結(jié)構(gòu)的映射。 使用上述數(shù)據(jù)結(jié)構(gòu)應(yīng)考慮： (1) 映射算法相對簡單，根據(jù)邏輯結(jié)構(gòu)容易計算出物理地址。 (2) 從邏輯結(jié)構(gòu)投影到物理結(jié)構(gòu)時，不至于越界或存儲溢出。 (3) 使用的數(shù)據(jù)結(jié)構(gòu)承擔這種程序設(shè)計語言的主要功能。 (4) 在這些數(shù)據(jù)結(jié)構(gòu)上定義的運算。,例:設(shè)有類Pascal程序段 program example(input,output); type student=record no:integer; name:array1.10 of char; score:integer end; weekday=(sun,mon,tue,wed,thu,fri,sat); var st:arr

9、ay1.50 of student; day:weekday; i,j:integer; begin today:= sun; i:=1; sti.no:=30; :=wang fang end.,從上可以看出，st是一個記錄型的數(shù)組，它首先通過數(shù)組的映射計算出sti的地址，然后再通過記錄的映射分別計算出sti.no 和 的地址。對于枚舉類型的數(shù)據(jù)sun,mon,tue,wed,thu,fri,sat如何描述它們的值和在枚舉類型的數(shù)據(jù)上的運算。對于字符串應(yīng)考慮是否允許整體賦值和字符串是否允許連接等運算，運算后的結(jié)果到存儲器中。連接后的結(jié)果如超出字

10、符串設(shè)定的長度，如何強制或報錯。 如要實現(xiàn)一個“?！钡臄?shù)據(jù)類型，就應(yīng)該考慮是否設(shè)置棧的最大容量，棧上的運算如：push和pop。棧元素所允許的數(shù)據(jù)類型，如棧元素的類型允許是數(shù)組、記錄、集合、字符串，但不能是表或棧。還要考慮如何將棧頂映射的物理存儲空間。如設(shè)定靜態(tài)的定長的棧空間用指針或下標指示當前棧頂或設(shè)定不定長的動態(tài)空間當入棧時申請存儲空間，出棧時返回存儲空間。,7.1.3 作用域規(guī)則 一個程序設(shè)計語言的作用域規(guī)則確定了該程序設(shè)計語言的某個程序的不同程序塊中所說明的標識符的可訪問性。從另一個角度來看，在程序中當訪問一個標識符通過作用域規(guī)則可確定究竟訪問的是哪一個實體中說明的標識符。一般來說一個

11、程序設(shè)計語言的一個標識符或數(shù)據(jù)項的作用域是在說明該標識符或數(shù)據(jù)項的程序塊內(nèi)，如Pascal中的標識符的作用域規(guī)則，敘述如下： (1) 一個標識符的作用域是從該標識符的定義點開始至定義該標識符的分程序結(jié)束為止，包含在這個分程序中的所有內(nèi)分程序，并遵循規(guī)則2。 (2) 當一個標識符x在分程序A中被定義，在A所包含的分程序B中又重新被定義，則分程序B以及包含在B中的所有分所出的x不再是A中定義的x，而是B中定義的x。,例:設(shè)有Pascal程序段 program example(input,output); var x,y: real; procedure pro; var y,z: integer;

12、 begin x:=y; end begin end.,在過程pro中賦值語句x:=y的x為主程序中說明的x，而y為過程序中說明的y。 作用域還包括文件作用域，如C語言的函數(shù)作用域是從說明點開始，一直延伸到源文件結(jié)束。 作用域規(guī)則的不同直接影響到編譯程序需生成的代碼。作用域規(guī)則分為靜態(tài)作用域和動態(tài)作用域二種。靜態(tài)作用域是指當標識符在本分程序中沒有說明時，到說明該分程序的上一分程序中找相應(yīng)的標識符，依次類推直至找到該標識符或整個上層分程序中均沒找到該標識符為止。否則出錯。動態(tài)作用域是指當標識符在本分程序邏輯中沒有說明時，到調(diào)用該分程序的程序中找，依次類推直至找到該標識符或整個調(diào)用程序中均沒找到該

13、標識符為止，同樣動態(tài)作用域也分為找到和出錯。顯然上述Pascal中的作用域規(guī)則是靜態(tài)作用域規(guī)則，靜態(tài)作用域規(guī)則在編譯中處理要比動態(tài)作用域的處理簡單些。,7.1.4 控制結(jié)構(gòu) 一種程序設(shè)計語言的控制結(jié)構(gòu)是該語言在程序運行期間用于改變控制流的語言特征集合。它包括有條件控制轉(zhuǎn)移，條件執(zhí)行、循環(huán)控制、過程序調(diào)用、轉(zhuǎn)移和出口。編譯程序在翻譯時必須保證源程序不能違法控制結(jié)構(gòu)的語義。如Pascal中只能從循環(huán)體內(nèi)轉(zhuǎn)向循環(huán)體外、C語言中不能從一個函數(shù)轉(zhuǎn)向另一個函數(shù)、BASIC中不能在循環(huán)體內(nèi)修改循環(huán)變量的值，而C沒有這種限制。 例:錯誤的控制結(jié)構(gòu) begin for i:=1 to 10 begin labe

14、l:x:=x+1; end; goto label end,程序的控制結(jié)構(gòu)實際是程序執(zhí)行權(quán)的轉(zhuǎn)移。為了減少程序員編制的源程序中的錯誤。通常對程序的結(jié)構(gòu)一定的約定。因此，在設(shè)計或翻譯程序設(shè)計語言的的控制結(jié)構(gòu)時，需考慮： 設(shè)定或限制某種程序的控制，應(yīng)滿足程序設(shè)計的方法學(xué)或結(jié)構(gòu)化程序設(shè)計的思想。 對每一種程序的控制結(jié)構(gòu)，均能用編譯的翻譯技術(shù)來實現(xiàn)翻譯。 提供程序的控制結(jié)構(gòu)有利于程序員實現(xiàn)程序和查找源程序的錯誤。 綜上所述，如何實現(xiàn)控制結(jié)構(gòu)的翻譯也是編譯程序必須考慮的問題。,7.2 運行時的內(nèi)存分配 編譯程序需要為常量或變量等數(shù)據(jù)分配運行時的存儲空間。編譯程序從操作系統(tǒng)中申請編譯程序計算出的所需的內(nèi)存

15、或者編譯程序生成在運時需申請內(nèi)存的指令。 內(nèi)存分配包括以下3個任務(wù)： (1) 確定用來表示某一數(shù)據(jù)項的內(nèi)存的大小。 (2) 使用適當?shù)膬?nèi)存分配策略實現(xiàn)具體數(shù)據(jù)的作用域和生命期。 (3) 確定以適當?shù)乃惴ㄔL問生命期內(nèi)的數(shù)據(jù)，包括基本型數(shù)據(jù)構(gòu)造型數(shù)據(jù)。 以上三個任務(wù)實際上是完成邏輯數(shù)據(jù)到具體數(shù)據(jù)的映射。根據(jù)內(nèi)存分配的時機，分為靜態(tài)存儲分配和動態(tài)存儲分配方式。采用哪一種分配策略是根據(jù)源語言的結(jié)構(gòu)特點、源語言的數(shù)據(jù)類型、源語言中的作用域規(guī)則，源語言存儲管理和組織的方式的復(fù)雜度都會影響到存儲空間的分配策略。 下面就存儲分配的主要技術(shù)，進行分析和討論。,7.2.1 靜態(tài)和動態(tài)內(nèi)存分配 為目標程序分配運行時

16、所需的存儲空間，一種是在目標程序運行前，由編譯程序為數(shù)據(jù)分配存儲空間，在程序的運行期間不再分配和解除這種內(nèi)存分配。另一種在程序運行期間均可以對內(nèi)存實現(xiàn)分配或解除分配，一旦存儲分配解除該存儲空間內(nèi)的數(shù)據(jù)便失去意義。前者稱為靜態(tài)存儲分配，后者稱為動態(tài)存儲分配。 定義7.3 內(nèi)存結(jié)合是指數(shù)據(jù)項的邏輯地址映射到內(nèi)存物理地址的聯(lián)系 內(nèi)存分配和內(nèi)存結(jié)合是兩個不同的概念，內(nèi)存分配相當于在上網(wǎng)時用戶申請了用戶名，此時網(wǎng)絡(luò)營運商將某個用戶名“分配”給了該用戶，但此時該用戶不一定在上網(wǎng)。內(nèi)存結(jié)合相當于網(wǎng)絡(luò)用戶用了申請到的用戶名上網(wǎng)。網(wǎng)絡(luò)用戶的結(jié)合從用戶的上網(wǎng)起至該用戶下網(wǎng)止。,內(nèi)存分配是實現(xiàn)內(nèi)存結(jié)合的過程和手段，

17、內(nèi)存結(jié)合在內(nèi)存解除分配時終止。源程序數(shù)據(jù)項的結(jié)合時刻決定編譯程序的處理方式。當編譯程序可以產(chǎn)生內(nèi)存分配的代碼時，不要在運行產(chǎn)生這種分配。這會影響到目標程序的效率。由于內(nèi)存分配的時機不同，引入靜態(tài)存儲分配和動態(tài)存儲分配的兩種方式。 1. 靜態(tài)存儲分配 在靜態(tài)存儲分配中，編譯程序在運行前為數(shù)據(jù)分配內(nèi)存。典型的靜態(tài)存儲分配是在編譯時分配的。這要求編譯程序在編譯時能確定目標程序運行中據(jù)需的全部數(shù)據(jù)空間的大小，編譯程序?qū)?shù)據(jù)和內(nèi)存結(jié)合從而實現(xiàn)存儲分配。編譯程序一旦實現(xiàn)靜態(tài)存儲分配，在整個程序運行期間不再進行存儲分配或解除存儲分配的工作直到整個程序運行結(jié)束。如C語言中的全局變量和靜態(tài)變量都是靜態(tài)存儲分配的

18、。,例:圖說明了下列C語言程序段的靜態(tài)數(shù)據(jù)存儲分配 int a,b,c; char d100; int f (); main() int x=5,y=8; printf(“%d ”,f (x);) printf(“%d ”,g (y);) int f(int n) static int p=0; p+=n; return(p); ,int g(int m) static float q=0; q+=m; return(q); 圖中的陰影部分表示其它數(shù)據(jù)的存儲空間。 靜態(tài)存儲分配的限制： (1) 數(shù)據(jù)對象的長度和它在內(nèi)存中的位置在編譯時都是已知的 (2) 不能建立如遞歸過程或遞歸函數(shù)中的一個名字

19、對應(yīng)多個存儲空間的結(jié)合 (3) 不能建立數(shù)據(jù)對象長度不定的存儲空間,2. 動態(tài)存儲分配 為了避免上述對靜態(tài)存儲分配的限制，引進了動態(tài)存儲分配。動態(tài)分配的數(shù)據(jù)區(qū)在運行不是一成不變的，它有時引入，有時退出，是一個動態(tài)的變化過程。動態(tài)存儲分配分為二大類，一類是隨著程序單元的進入而分配，隨著程序單元的退出而撤銷。另一類是由程序控制其分配和撤銷。它們分別用棧和堆來實現(xiàn)，被稱為棧式動態(tài)存儲分配和堆式動態(tài)存儲分配。 a)棧式動態(tài)分配 當一個程序設(shè)計語言允許遞歸時，則每次進入該遞歸過程或函數(shù)時，就應(yīng)分配一塊大小相同的內(nèi)存。當該過程或函數(shù)結(jié)束時相應(yīng)的內(nèi)存釋放。由于遞歸過程或函數(shù)的進入和退出符合棧的先進后出的原則

20、，故這一類存儲分配可用棧實現(xiàn)。把每次進入過程或函數(shù)需分配的數(shù)據(jù)區(qū)稱為活動記錄。,活動記錄包括（如圖所示）： (1) 連接數(shù)據(jù) a) 老的SP。 每個活動記錄，有一個基址指針稱為SP。為了撤銷本活動記錄時能指出上一個調(diào)用者的活動記錄就應(yīng)保存調(diào)用者的SP稱為老的SP。而老的棧頂不必保存，因為老的棧頂為現(xiàn)SP-1（設(shè)SP占一個存儲單元） b) 返回地址 返回地址是指子程序完成后的返回地址（對于函數(shù)還要返回其函數(shù)值）。 (2) 程序狀態(tài)字 為保存調(diào)用者的機器信息，如程序計數(shù)器、標志寄存器和寄存器的值，在返回時，預(yù)以恢復(fù)。 (3) 參數(shù)個數(shù) (4)形式單元 存放實在參數(shù)的值或地址。,(5) 局部數(shù)據(jù) 局

21、部數(shù)據(jù)包括：局部變量、靜態(tài)數(shù)組的數(shù)據(jù)區(qū)、動態(tài)數(shù)組的內(nèi)情向量和臨時工作單元。,例:設(shè)有程序結(jié)構(gòu)如下所示： program main; 全局變量或數(shù)組說明； proc R; end R; proc Q; end Q; 在采用棧式動態(tài)分配時，因每進入一個過程就為該過程或函數(shù)分配存儲空間。則圖（a）表示主程序中調(diào)用了R；在R中又調(diào)用了Q的存儲結(jié)構(gòu)。圖（b）表示在Q中又調(diào)用了Q的存儲結(jié)構(gòu)。圖（c）表示在Q退出，又調(diào)用了R的存儲結(jié)構(gòu)。圖（d）表示在R退出的存儲結(jié)構(gòu)。圖（e）表示在Q退出的存儲結(jié)構(gòu)。圖（f）表示在R退出的存儲結(jié)構(gòu)。,經(jīng)過討論了棧的存儲分配，還要考慮過程式或函數(shù)調(diào)用和返回需完成的工作。前面第六

22、章說過過程調(diào)用的四元式序列是： par T1 par T2 par T3 par Tn call P,n,現(xiàn)考慮四元式par和call是如何執(zhí)行的，也就是par和call要完成怎樣的工作。對于每個par Ti 需產(chǎn)生把參數(shù)填入活動記錄的指令。由于SP、返回地址、參數(shù)個數(shù)和程序狀態(tài)字的所需的字節(jié)數(shù)對于某個過程來說是不變的且可以計算出的，因此，每個參數(shù)存放的地址（相對于SP的地址）也是可以計算出的,設(shè)其和為m，則對于par Ti可翻譯成類似于如下指令： TOP+ i+m:= Ti 這里TOP為老的TOP，每個參數(shù)均只占一個單元，Ti為參數(shù)的值或參數(shù)的地址。 四元式call P,n應(yīng)翻譯成： TOP

23、+1 := SP /*保護現(xiàn)行的SP*/ TOP+i+1 :=當前寄存器值 /*保護現(xiàn)場*/ TOP+m-1 :=n /*保存參數(shù)個數(shù)*/ call P,進入過程P后，應(yīng)賦新的SP，保護返回地址（返回地址也可以由指令call P保存系統(tǒng)的棧中），定義新的TOP值。即執(zhí)行指令： SP:= TOP+1 SP+1 :=返回地址 TOP：=TOP+L /*L為P過程所需的單元數(shù)*/ 當執(zhí)行到過程、函數(shù)的返回語句或過程、函數(shù)中的語句全部被執(zhí)行完畢應(yīng)返回調(diào)用者。其工作為計算出內(nèi)存出棧后的TOP、將復(fù)原老的SP，對于函數(shù)還應(yīng)將函數(shù)值存放到指定的連接單元中，然后執(zhí)行返子指令： TOP:= SP -1 SP:=

24、 SP+0 /*如返回的是函數(shù)則執(zhí)行一條將函數(shù)值保存到指定單元或寄存中*/ RET /*返回調(diào)用程序*/ 在這里SP、TOP、參數(shù)等均只占一個單元，若它們占用不等長的單元在編譯中也是可以計算出的，其實現(xiàn)方法類似。,b)堆式動態(tài)存儲分配 當一種程序設(shè)計語言允許用類似于Pascal中new和dispose語句申請和釋放內(nèi)存，則不能用棧式存儲分配，這因為其申請和釋放的次序不滿足先進后出的條件。這種數(shù)據(jù)只能借助于一種稱為堆式動態(tài)存儲分配的方法來實現(xiàn)。假定程序運行時有一個較大的存儲空間，當用戶申請堆內(nèi)存時，就分配一塊，不用時返回。由于分配和返回的時間沒有規(guī)律可循。當程序運行一段時間后，原來一塊較大的存儲

25、空間很可能分成很多很多塊。然而當需要長度為N的存儲空間只能尋找比N大或相等的內(nèi)存塊分配，以此往復(fù)。最后在存儲器池中出現(xiàn)了很多碎片。這些碎片就很難再為程序其它部分所用。為了解決碎片問題，一種方法是通過移動將碎片合并在一起，但這種方法是低效的，移動需化費很多機時。另一種方法是將原較大的存儲空間分成若干等長的塊，申請時分配以塊為單位不足一塊的長度也分配一塊，返回時則必定也是以塊為單位的。這樣解決了碎片問題，即外零頭問題。但以塊為單位分配浪費了塊內(nèi)的存儲空間，也就是生成了內(nèi)零頭。這種方法雖然在分配時沒有完全利用全部存儲空間，但提高了系統(tǒng)的效率。由于操作系統(tǒng)也需要管理內(nèi)存，在編譯實現(xiàn)時直接可以利用操作系

26、統(tǒng)的內(nèi)存管理，即需要內(nèi)存時，向操作系統(tǒng)申請內(nèi)存，釋放時直接將內(nèi)存返回操作系統(tǒng)。,7.2.2 嵌套結(jié)構(gòu)的內(nèi)存分配 前面介紹的棧式動態(tài)存儲分配，每個過程或函數(shù)只能使用局部變量不能使用非局部變量，這與Pascal語言結(jié)構(gòu)的特點是不同的。Pascal允許過程嵌套定義，也就是在過程或函數(shù)內(nèi)需要使用非局部變量。下面是有嵌套過的Pascal程序。 program sort(input,output); var a:array1.10 of integer; x:integer; procedure readarray; var a endreadarray procedure exchange(i,j:in

27、teger); begin x:=ai; ai:=aj; aj:=x endexchange,procedure quicksort(m,n:integer); var k,v:integer; function partition(y,z:integer):integer; var i,j:integer; begin a v exchange(i,j); endpartition; beginendquicksort; beginendsort,為了處理一致性，把主程序sort看作最外層過程。這樣過程說明的嵌套情況為： sort readarray exchange quicksort p

28、artition 雖然在過程readarray、exchange、partition引變量a，但該變量卻為主程序中的a。在過程exchange中還引用了主程序中的x。下面要解決如何調(diào)用外層中的變量。 在這里介紹靜態(tài)作用域，動態(tài)作用域的調(diào)用方式可參照此方法稍作修改，也能完成。從上圖中可以看出，無論是靜態(tài)作用域還是動態(tài)作用域當內(nèi)層過程需調(diào)用外層變量時，其外層過程的活動記錄必然在棧中。要調(diào)用外層變量只要在內(nèi)層過程中指出外層變量的活動記錄的位置（SP）值，再根據(jù)由符號表中指出的外層變量的相對位置就可以得到該外層變量的地址。,方法一：在活動記錄中增加區(qū)頭向量 考慮程序的執(zhí)行次序為： sortquicks

29、ortquicksortpartitionexchange 對于exchange可能用到的外層變量為sort的變量；對于partition可能用到的外層變量為quicksort 和sort的變量。以sort標記為0層；,readarray、exchange、quicksort標記為1層；partition標記為2層，則第i層過程中除了能調(diào)用本層變量外，還能調(diào)用第0層至第i-1層的外層變量。把從第0層至第i層活動記錄的地址存放在一起組成了區(qū)頭向量，如圖所示。,當sort調(diào)用quicksort時，quicksort的區(qū)頭向量為sort的區(qū)頭向量和quicksort活動記錄的地址。對于quickso

30、rt調(diào)用quicksort時，不能用前面一個quicksort的區(qū)頭向量再加上本層活動記錄的地址，發(fā)現(xiàn)quicksort和quicksort是并列的，也就是層數(shù)相同的，因此允許調(diào)用的外層變量是相同的，故可從前面的quicksort中拷貝層數(shù)個地址再加上本層活動記錄的地址組成新的區(qū)頭向量。類似地，partition從第2個quicksort過程中拷貝層數(shù)個地址再加上本層活動記錄地址組成新的區(qū)頭向量。exchange從partition過程中拷貝層數(shù)個地址再加上本層活動記錄地址組成新的區(qū)頭向量。,設(shè)有圖嵌套調(diào)用的情形，下面分另討論不同之處調(diào)用Pi的區(qū)頭向量的構(gòu)造情況。 在 Pi中調(diào)用Pi，則從P0

31、Pi-1均是Pi可以調(diào)用的，因此從上一層Pi的區(qū)頭向量中拷貝P0Pi-1的地址，加上Pi活動記錄的地址組成新的區(qū)頭向量。在 Pi+1中調(diào)用Pi，則從P0Pi-1均是Pi可以調(diào)用的，而Pi 和Pi+1不是Pi的外層不要間接調(diào)用或不能調(diào)用，因此從上一層Pi+1的區(qū)頭向量中拷貝P0Pi-1的地址，加上Pi活動記錄的地址組成新的區(qū)頭向量。同理，在 Pi+1中調(diào)用Pi，拷貝P0Pi-1的地址加上Pi活動記錄的地址組成新的區(qū)頭向量。最后討論在 Pi+2中調(diào)用Pi，則仍然是從P0Pi-1均是Pi的外層，而Pi 、Pi+1和Pi+2不是Pi的外層，因此從上一層Pi+2的區(qū)頭向量中拷貝P0Pi-1的地址，加上P

32、i活動記錄的地址也就組成了所需的區(qū)頭向量。,綜上所述，對于調(diào)用第i層的過程只要從前面調(diào)用者中拷貝0i-1個地址，加上本數(shù)據(jù)區(qū)的地址組成新的區(qū)頭向量。這樣要在活動記錄中增加稱之為區(qū)頭向量的部分，如圖所示。 每個過程的d值和過程的層數(shù)l在編譯時都是可以計算出來的，則四元式call P,n應(yīng)翻譯成： TOP+1 := SP /*保護現(xiàn)行的SP*/ TOP+i+1 :=當前寄存器值 /*保護現(xiàn)場*/ TOP+m-1 :=n /*保存參數(shù)個數(shù)*/,從調(diào)用者的區(qū)頭向量中拷貝l個單元至進入過程的區(qū)頭向量中；將TOP+1即新的SP放入?yún)^(qū)頭向量的最后單元，組成新的區(qū)頭向量。 call P設(shè)訪問外層變量的層數(shù)為l

33、i，則訪問外層變量的語句翻譯成： x:=SP li+d,或SP li+d:=x 的指令。 圖表示執(zhí)行次序為sortquicksortquicksortpartitionexchange的區(qū)頭向量變化圖。 方法二：在活動記錄中增加訪問鏈 在過程的活動記錄中增加一個稱為訪問鏈的的指針，當過程q在源程序中嵌套p中，則將q中訪問鏈直接指向p。那么執(zhí)行次序為： sortquicksortquicksortpartitionexchange,具有訪問鏈的存儲器棧變化圖，如上所示。下面需解決二個問題： (1) 如何建立訪問鏈 (2) 怎樣根據(jù)訪問鏈獲得外層變量 建立訪問鏈也就是在運行時能求過程說明的直接外層

34、。由于主程序沒有外層，故編譯程序需為進入主程序時，生成置主程序的訪問鏈為空指令。下面討論執(zhí)行中過程R（可能為主程序）調(diào)用過程S時，怎樣求出S的訪問鏈。在編譯時R和S的層數(shù)都是可以求出分別記為lR和lS。R可以調(diào)用S，則S在R的作用域內(nèi)，可得lSlR+1。當lS = lR+1時，則S是在R內(nèi)說明的，也就是S是R的直接外層，只要生成將S的訪問鏈置為指向R的SP（或R的訪問鏈）的指令。,當lS = lR時，則S和R是并列的它們具有相同的直接外層，也就是R的外層也就是S的外層，只要生成將R的訪問鏈賦給S的訪問鏈的指令即可。lSlR時，S的直接外層必然在棧中，即R必然被S的直接外層直接或間接調(diào)用，否則S

35、不在作用域內(nèi)。因此，只要對訪問鏈向前搜索lR - lS層，即可得到S的直接外層。編譯程序生對訪問鏈向前搜索lR - lS層的指令和將也為第lS的訪問鏈賦給S的訪問鏈。如R的層數(shù)為5，S的層數(shù)為2，則向前搜索3級求得層數(shù)也為2的活動記錄，它的訪問鏈即為S的訪問鏈。 獲得外層變量的方法與上述類似。設(shè)有p過程中訪問了變量a，那么p過程的層數(shù)記為lp，變量a層數(shù)記為la，只要向前搜索la - lp層,就可得到變量a所在的活動記錄中，由于a的相對位置在編譯中也是在符號表中可以查到的，故能生成對變量a訪問的指令。,分程序內(nèi)含有數(shù)據(jù)說明語句起源于Algol，但C語言中延用此概念，C語言的分程序的語法為 說明

36、 語句 也就是在C語言中的復(fù)合語句中，允許說明變量。而且在分程序的語句中還可以再有說明。這種具有嵌套性的分程序稱為分程序結(jié)構(gòu)。一個分程序結(jié)構(gòu)的語言的說明作用域遵循最近嵌套原則： (1) 一個分程序B中說明的作用域包括B，除了在B內(nèi)的分程序重新說明 (2) 如果名字x不在B中說明，則x是最靠近且B有說明x的分程序說明的x,設(shè)有程序段： main() /*分程序B0開始*/ int a=0; int b=0; /*分程序B1開始*/ int b=1; /*分程序B2開始*/ int a=2; printf(“%d,%dn”,a,b); /*分程序B2結(jié)束*/ /*分程序B3開始*/ int b=3

37、; printf(“%d,%dn”,a,b); /*分程序B3結(jié)束*/,printf(“%d,%dn”,a,b); /*分程序B1結(jié)束*/ printf(“%d,%dn”,a,b); /*分程序B0結(jié)束*/ 則在B0中說明的int a=0的作用域為B0- B2；在B0中說明的int b=0的作用域為B0- B1；在B1中說明的int b=1的作用域為B1- B3；在B2中說明的int a=2的作用域為B2；在B3中說明的int b=3的作用域為B3。其變量標分別記為：a0,b0,b1,a2,b3。 分程序結(jié)構(gòu)也可以用棧式存儲分配來實現(xiàn)。因為每個變量作用域也符合先進后出的特點。解決分程序邏輯結(jié)構(gòu)

38、的存儲分配，可采用下列二種方法。一是把分看成一個無參過程，用上述過程嵌套的方法來解決。這種過程的特點是只說明一次，也只使用一次，它在分程序前調(diào)用，在分程序結(jié)束退出，調(diào)用外即為說明之處。二是把一個過程體中所需的存儲一次全部分配好。由于B2中說明的a和B3中說明的b的作用域不相交，故可分同一塊存儲空間，如下圖所示。,在動態(tài)作用域中，進入新的過程時僅當新過程中說明了同名變量時，解釋為新的存儲。解決動態(tài)作用的方法也有二種，一是所謂深訪問，它在活動記錄中存放一個控制鏈指向上一級調(diào)用過程，也可利用SP指針。當發(fā)現(xiàn)非局部變量時從控制鏈一級一級向前搜索，直至搜索到為止，這種搜索可能深入棧中，因此而得名。搜索的

39、深度取決于程序的運行，而編譯時不能決定的。另一種所謂淺訪問，它采用體外循環(huán)的方法，為每個同名變量的名字分配靜態(tài)的數(shù)據(jù)空間，當進入有同名變量的過程時將靜態(tài)區(qū)的同名變量值保存到過程的同名變量的位置上，在過程的整個運行過程中，使用靜態(tài)區(qū)同名變量，過程結(jié)束后將先前保存在過程內(nèi)的變量恢復(fù)。兩種方法各有優(yōu)缺點。深訪問訪問非局部變量是需較長的時間，但它不需要額外的開銷。而淺訪問可以直接訪問非局部變量，但需要一些輔助的時間和空間來維護。,7.2.3 數(shù)組的分配和訪問 由于靜態(tài)數(shù)組所需空間的大小是在編譯時可以計算出來的，因此可在嵌套結(jié)構(gòu)的棧式存儲分配中只要為每個數(shù)組分直接分配相應(yīng)的存儲空間。下標變量的訪問無論是

40、本層變量還是外層變量都可以用前面介紹過的方法翻譯成通過基址SP和相對位置訪問下標變量的值。 動態(tài)數(shù)組的所需的空間在運行時才能確定，這樣動態(tài)數(shù)組的存儲空間也只能在運行時分配。前面說過編譯程序需為內(nèi)情向量分配了存儲空間，然后生成填寫內(nèi)情向量的指令。下面討論動態(tài)數(shù)組的空間存放在何處。一種方法是將動態(tài)數(shù)組的空間存放在堆內(nèi)存中，此時可以生成為動態(tài)數(shù)組申請堆存儲的指令，并將首地址也填入內(nèi)情向量中。當訪問下標變量時，則編譯程序可以生成要根據(jù)下標變量的下標和數(shù)組的內(nèi)情向量求出數(shù)組元素在堆中的存儲位置。,另外，應(yīng)該注意在過程結(jié)束時，還需生成一條將堆內(nèi)存返回的指令，不然會造成存儲器的泄漏。嚴重時還會造成系統(tǒng)癱瘓。

41、另一種方法也將動態(tài)數(shù)組的存儲空間分配在棧中。當進入嵌套過程時，其活動記錄的狀態(tài)如圖(a)所示。此時應(yīng)填寫動態(tài)數(shù)組的內(nèi)情向量，TOP+1作為第一個動態(tài)數(shù)組的首地址。此時該動態(tài)數(shù)組所需的存儲空間可以計算出來了，可在棧頂分配該動態(tài)數(shù)組的存儲空間。并將棧指針指向新的棧頂。如有二個或二個以上的動態(tài)數(shù)組，則繼續(xù)為每個動態(tài)數(shù)組分配內(nèi)存。以次類推，最后棧指針指向如圖(b)中的TOP位置。此方法當過程退出時，則不必生成返回內(nèi)存的指令，這是因為退出過程時TOP賦的是SP-1，SP賦的是過程中保存的老的SP，指向調(diào)用者的活動記錄。達到將動態(tài)數(shù)組分配的內(nèi)存和原來的活動記錄一起返回給棧。,7.3 代碼優(yōu)化 作為一個高級

42、語言的使用者很希望編譯程序所產(chǎn)生的代碼能夠和直接用機器語言編寫的程序的效果一樣好。但事實上很難做到這一點，即使能做到這一點，也許所需化費實現(xiàn)優(yōu)化的時間和空間比優(yōu)化所得到的節(jié)省的時間多得多。在這里介紹的代碼優(yōu)化是指對原代碼進行變換，從而獲得時間和空間效率相對高的程序，而不一定且一般也不是時間和空間最省的程序。在進行優(yōu)化時應(yīng)做到： (1) 代碼的變換必須保持原程序的語義 (2) 從理論上，變換加快了程序的速度 (3) 這種變換是值得的 如果一種所謂的優(yōu)化改變了原程序的語義 實際上產(chǎn)生了一個錯誤程序，這種變換也是無效的。盡管在優(yōu)化后可能對于一些程序反而比原來增加了開銷，但總體來說是節(jié)省的，而且節(jié)省應(yīng)

43、達到一個可度量的值，不然優(yōu)化中的損失不可能在運行中彌補。由于各個機器的指令系統(tǒng)是不同的，即使是相同的四元式程序所生成的“最優(yōu)”的代碼也是不同的.其優(yōu)化算法也可能是不同的。為了算法的一致性在這里僅討論與目標機器無關(guān)的優(yōu)化算法。,一個程序的優(yōu)化是由下面兩個階段構(gòu)成的： (1) 局部優(yōu)化：應(yīng)用于僅包括少量語句的小程序的優(yōu)化變換。 (2) 全局優(yōu)化：應(yīng)用于一個程序單元，如一個函數(shù)或一個過程的優(yōu)化變換。 7.3.1 優(yōu)化變換 程序的執(zhí)行效率是可以通過地編譯期優(yōu)化變換是重寫程序段以提高程序的工作效率而不改變語義。雖然變換的方法很多但常用的大致有下列幾種： 1. 編譯求值 一般來說程序的目標代碼可能要運行多

44、次，而編譯只編譯一次。如果一些原屬于執(zhí)行時完成的工作能在編譯時解決，則提前完成這些工作。如在計算sin(3.1415927/6)時，3.1415927/6的值在編譯時可以計算的，其值為0.523598783，運行時只要執(zhí)行sin(0.523598783)。因此程序的執(zhí)行效率是可以通過地編譯期間完成程序中的執(zhí)行語義來提高的。這時編譯程序消除了程序在執(zhí)行時的需求，從而達到減少程序的執(zhí)行時間、提高程序的工作效率。編譯時的求值卻體現(xiàn)了這一點。,2. 合并運算 設(shè)有程序段： x:=a+b+c+d; if a+b0 then ; y:=(a+b)*(b+c)+d; 則子表達式a+b在不同的表達式中均使用過

45、，因此只要計算一次a+b的值，其余的值就可以使用該臨時變量的值。而將其它公共子表達式刪除。 實現(xiàn)這種優(yōu)化過程首先要識別產(chǎn)生相同值的表達式，在這里a和b都有沒有重新被定值，故子表達式相同即為值相同。其次計算相同的子表達式，用已存放在臨時變量的值逐個代替試寫出算術(shù)表達式。 表達式的等價可以考慮它們的運算對象是否程序所在位置處于相同的值。如一般情況下a+b值和b+a的值是等價的,還有執(zhí)行過c:=b后，a*b和a*c是等價的。實現(xiàn)這種“代數(shù)等價”，雖然提高了優(yōu)化的效率，但同時也增加了優(yōu)化的花費。,例:寫出算術(shù)表達式a+b*c-(c*b+a-c)/(b*c+d)優(yōu)化后的四元式 （1）（* ,b,c,t1

46、） （2）（+,a,t1,t2） （3）（-, t2,c,t3） （4）（+,t1,d,t4） （5）（/, t3,t4,t5） （6）（-, t2,t5,t6）,3. 刪除死碼 如果能在程序中刪除其代碼而不影響程序的運行結(jié)果的代碼被稱為“死碼”，“死碼”可以通過程序的控制流來獲得，如條件語句： if x3 then if x，而x在程序的其它處從未被引用過，顯然x:=也為“死碼”。刪除這種“死碼”時應(yīng)注意，只有當?shù)膱?zhí)行不會產(chǎn)生副作用時可以刪除，也就是它不包含函數(shù)或過程，即使含有函數(shù)但沒有函數(shù)的副作用，才能刪除它。,4. 減少頻率 減少頻率是指程序中執(zhí)行頻率高的程序段移至程序執(zhí)行頻率低的程序部

47、分中。其主要變換有相對循環(huán)不變量的內(nèi)碼外提。如程序段： for i:=1 to 1000 do begin x:=1; y:=5*x; z:=y+i end 此時循環(huán)體內(nèi)的語句x:=1和y:=5*x;需執(zhí)行1000次，且它們相對于循環(huán)變量i來說是不變的，因此將它們提出循環(huán)，置循環(huán)體外。即為： x:=1; y:=5*x; for i:=1 to 1000 do z:=y+i 這樣對于語句x:=1和y:=5*x僅執(zhí)行一次。,例:設(shè)有循環(huán)語句 c:=0; FOR i:=1 TO n DO BEGIN a:=x*y; b:=m*m; c:=c+b*b END 試寫循環(huán)外提后的四元式序列。 根據(jù)題意，可

48、寫出循環(huán)語句的四元式序列為： （1）（:= 0,_,c） （2）（:= 1,_,i） （3）（jl,n,i,14） （4）（*, x,y,t1） （5）（:=,t1,_,a） （6）（*, m,m,t2）,（7）（:=, t2,_,b） （8）（*, b,b,t3） （9）（+,c, t3, t4） （10）（:=, t4,_,c） （11）（+, i,1, t5） （12）（:=, t5,_,i） （13）（jmp, _,_,3） 由于a:=x*y是循環(huán)不變運算，則可外提。b2與c之和雖然賦給了c，但b本身對于循環(huán)變量來說也是不變的，故也可以外提。其外提后生成的四元式如下：,（1）（:= 0

49、,_,c） （2）（:= 1,_,i） （3）（*, x,y,t1） （4）（:=,t1,_,a） （5）（*, m,m,t2） （6）（:=, t2,_,b） （7）（*, b,b,t3） （8）（jl,n,i,14） （9）（+,c, t3, t4） （10）（:=, t4,_,c） （11）（+, i,1, t5） （12）（:=, t5,_,i） （13）（jmp, _,_,8）,5. 強度削弱和變換循環(huán)條件 強度削弱是指用一個運算速度較快的運算符代替耗時較多的運算符，也就是將強度高的運算符削減為低強度的運算符。如：X2寫成X*X，2*X寫成X+X。 在循環(huán)中的強度削弱方法為： (1)

50、 設(shè)循環(huán)變量為i，對于循環(huán)體內(nèi)的運算L:=K*i+C可削弱為T:=T+K (2) 對臨時變量T賦初值C (3) 刪除強度削弱后的無用變量,例:設(shè)有循環(huán)語句 FOR i:=1 TO n DO BEGIN L:=K*i+C; END 則削弱為： T:=C; FOR i:=1 TO n DO BEGIN T:=T+K L:=T; END,強度削弱對于程序循環(huán)中數(shù)組的訪問是十分重要的，如在一個Pascal循環(huán)中的數(shù)組引用ai,j的地址，這樣就造成了高強度的運算i*n(按行存放)，用上述方法就可以大地降低運算的強度。但需要注意的是這種方法不能適用于下標變量允許為實數(shù)（浮點數(shù)）類型，這是因為實數(shù)在累加時會

51、產(chǎn)生積累誤差，最后的T中不是所需的K*i+C。 設(shè)有循環(huán)語句: for (i=1;i=n;i+) t=4*i; x=f(t); 由于在循環(huán)語句中i和t的關(guān)系始終保持4倍的關(guān)系，而且循環(huán)內(nèi)的其它部分也沒有引用i，則可將循環(huán)條件改變?yōu)?for (t=1;t=4*n; t+=4) 這樣經(jīng)過變換后i的值在循環(huán)內(nèi)不再引用，故可在循環(huán)中刪節(jié)除，從而達到優(yōu)化的目的。,6. 減少復(fù)寫傳播 把形如b:=a的賦值語句稱為復(fù)寫語句，簡稱復(fù)寫。當b:=a;c:=b時，只要a在被新的賦值之后的程序不再引用b，則可用c:= a代替c:=b。 【例7-10】設(shè)有程序段 y:=x;z:=y;z:=y; t1:=f(y); t

52、2:=g(z); 則改寫為： t1:=f(x); t2:=g(x);,7.3.2 局部優(yōu)化 局部優(yōu)化所需的化費相對較低，也就從優(yōu)化所得到的收益也相對較低。局部優(yōu)化顧名思義只是在較小的程序段中進行優(yōu)化，從而達到優(yōu)化的目的。這種程序段稱為“基本塊”。 定義7.4 基本塊是指程序中的一語句的順序序列(S1,S2, Sn)，其中只有第一個語句(S1)允許有是程序的控制語句轉(zhuǎn)移的目的語句和最后一個語句(Sn)允許是一個控制轉(zhuǎn)移語句。 基本塊劃分算法： (1) 求出稱為入口的基本塊的第一個語句，如：程序的第一個語句或有控制語句轉(zhuǎn)入的語句。 (2) 對于每一入口語句構(gòu)造其所屬的基本塊： 1)由入口語句到下一

53、入口語句的前一語句 2)由入口語句到一轉(zhuǎn)移語句 3)由入口語句到一停語句 (3) 對于未被劃入任一基本塊的語句，為通過任何基本塊都不能到達該語句，故為無用語句應(yīng)刪除。,對于基本塊內(nèi)的公共子表達式的刪除，可采用計算出每項個定值的四元式編號，當兩個子表達式完全相同時，則它們具有相同的定值的四元式編號，表示在二個四元式之間沒有新的定值。 為了簡單起見。在基本塊內(nèi)將四元式編號以1開始的連續(xù)號碼編號。由于一個被定值的變號與被定值的變量有關(guān)，則在符號表中的每一變量增加一個稱為定值編號的屬性。設(shè)有(n) A:=B op C，其中n為對A定值的四元式編號，B、C為變量，op為運算符。在符號表中需保存每個變量定

54、值的位置n，對尚未定值的變量符號表中的定值編號的屬性以0表示。另外建立一四元式的符號表，為每個四元式的運算對象上都上都附加一個定值信息來指出該運算對象，這些信息也用四元式的編號表示。,再為每個四元式保存一個引用信息表示是否要為程序中的其它處引用而保留其值，其初值為false。當設(shè)表達式e是e的子表達式，在翻譯是時形成了關(guān)于e的四元組時，其運算對象所關(guān)聯(lián)的定值信息可從符號表中獲得。將新產(chǎn)生的四元式和四元式符號表中現(xiàn)有的四元式比較，如果存在一個登記項為k的與新的四元組完全匹配的四元式，則說明其值與新的表達式的值完全相同，也就是新的四元式不必存放在四元式符號表中，用四元式符號表k的結(jié)果名代替e中的對

55、象，并對四元式k的引用信息置為true，以便決定該值是否保存到臨時變量中。,例:設(shè)有基本塊： (:=,3.14 ,_,t1) (*,2, t1, t2) (*,x, y, t3) (*,t1 , t2, a) (:=,a, _, b) (*,2, t1, t4) (*,x, y, t5) (*,t4 , t5, t6) (*,x , y, t7) (*,t6 , t7, b),其局部優(yōu)化的過程為設(shè)所有變量的定值編號為0，當四元式(:=,3.14 ,_,t1)、(*,2, t1, t2)和(*,x, y, t3)進入時為圖(a)；,當四元式(*,t1 , t2, a)和(:=,a, _, b)進

56、入時，如圖(b)；,優(yōu)化四元式(*,2, t1, t4)時，在四元式表中查到匹配的四元式(2)，故該四元不要入表，以后以t2代替原來的t4；同樣四元式(*,x, y, t5)只要用t3代替t5；則對于四元式(*,t4 , t5, t6)將改為(*,t2 , t3, t4)填表。四元式 (*,x , y, t7) 也能找到匹配的四元式，則不要添加到表中；最后(*,t6 , t7,b)添入表中為(*,t4 , t3,b)，并將t2 和 t3的引用信息改為true,如圖(c)。,上述方法很容易地擴充到編譯時的合并常量。對于語句a:=n，其中a為變量，n為常量。則在在常量表中加入常量n，其登記項為k，

57、并將定值位置k與a相關(guān)聯(lián)用-k表示。當生成一個四元組是，如果每個運算對象都是一個常量或是一個負的定值位置時，就可以實常量合并。 例:將上例中加入用合并常量算法 加入用合并常量算法后其結(jié)果，如圖所示。,7.3.3 全局優(yōu)化 要產(chǎn)生高效的代碼，編譯程序僅在基本塊內(nèi)優(yōu)化是不夠的。編譯程序應(yīng)把程序作為一整體來考慮，對各個基本塊的信息進行數(shù)據(jù)流的分析從而達到優(yōu)化的目的。全局優(yōu)化和局部優(yōu)化相比，全局優(yōu)化需要更多的分析，以便確定優(yōu)化的可行性。這里僅介紹全局子表達式的消除，包括公共表達式的消除和死代碼的消除。 設(shè)有子表達式存在于程序的若干基本塊中，記為SB = bi|bi是基本塊。設(shè)子表達式存在于程序的一組基

58、本塊中，且在某個bk中存在對子表達式的求值。當程序的每次執(zhí)行，都能滿足下列兩個條件，則在基本塊bi中子表達式是可以消除的。 (1) 基本塊bi只在已執(zhí)行了一次或多次的某個bk后執(zhí)行。 (2) 在基本塊bk對的最后一次求值后，沒有改變中的變量的值。,第一個條件保證了基本塊bi中的子表達式已被求值；第二個條件則保證了在基本塊bk求得的值和在基本塊bi求得的值是等價的。如子表達式為x*y，則不能改變變量x或y的值。 定義7.5 程序流程圖是一個三元組G=(N,E,n0)，其中，N為圖的所有結(jié)點的集合也就是基本塊的集合。E表示圖中的有向圖中的邊集，邊(bi,bj)它表示基本塊bi的最后一個語句轉(zhuǎn)向基本

59、塊bj的第一個語句。n0表示程序的開始結(jié)點。,利用程序流程圖分析基本塊的控制和數(shù)據(jù)流的關(guān)系，實際上是分析基本塊之間的關(guān)系是否滿足上述二個條件。下面介紹一些基本概念： (1) 前趨和后繼：若(bi,bj)E，則稱bi是bj的前趨，bj是bi的后繼。 (2) 路徑：路徑是從一個結(jié)點沿邊序列到另一個結(jié)點的邊的有序序列。 (3) 祖先和后代：若存在一條從bi到bj的路徑，則稱為bi是bj的祖先, bj是bi的后代。 (4) 活躍變量：如果變量a在一個基本塊bi的某個程序點pi處定值，并在以后的程序中引用該值，則稱變量a是活躍的,控制流分析是對一個程序進行分析以收集與程序結(jié)構(gòu)相關(guān)的信息。數(shù)據(jù)流分析是對程序中使用的數(shù)據(jù)進行分析，以收集對優(yōu)化有用的信息，能用來判斷是否能對程序段進行優(yōu)化。 定義7.6 如果在基本塊bi包含一個對子表達式求值，且從求值之后不再包括對表達式中的運算對象的賦值，或子表達式在基本塊是入口有效bi不再包括對表達式中的運算對象的賦值稱子