目標(biāo)程序運(yùn)行時(shí)的存儲組織

1、第10章目標(biāo)程序運(yùn)行時(shí)的存儲組織110.1 臨時(shí)變量的存儲分配存儲分配的原因：四元式產(chǎn)生大量臨時(shí)變量(每個(gè)運(yùn)算產(chǎn)生一個(gè))，如不采取措施就會浪費(fèi)大量存儲單元。例：ci的四元式 1.(-, i, 1, T1) 2.(*, T1,5, T2) 3.(, c, T2,T3)2四元式QTi定義變量Y,則稱i為Y的定義點(diǎn)；如果四元式QTj使用變量Z的值,則稱j為Z的使用點(diǎn)。臨時(shí)變量的存儲分配可在中間代碼一級進(jìn)行,也可在目標(biāo)代碼一級進(jìn)行。現(xiàn)在的目標(biāo)是讓更多的臨時(shí)變量共享內(nèi)存單元。采用動態(tài)分配法，不直接給變量分配單元，只是確定抽象地址。 3定義點(diǎn)和使用點(diǎn)全部落在一個(gè)基本塊內(nèi)的臨時(shí)變量稱之為良型臨時(shí)變量。只被定

2、義一次，且只被定義一次。定義點(diǎn)與使用點(diǎn)在一個(gè)基本塊內(nèi)。良性臨時(shí)變量的特點(diǎn)：基本塊1基本塊2定義點(diǎn)使用點(diǎn)4設(shè)i為臨時(shí)變量T的定義點(diǎn)，j為最后一個(gè)使用點(diǎn)，則稱區(qū)間i,j為T的活動區(qū)。設(shè)i,j和k,l是兩個(gè)活動區(qū),如果j=k或l=i,則稱兩個(gè)活動區(qū)不相交。 基本塊T1的活動區(qū)ijklT2的活動區(qū)T1的活動區(qū)ikjlT2的活動區(qū)5例子：設(shè)有語句Y:=(A*B+C)*B-D，則四元式為： 1.(*, A, B, T1) A*B2.(+, T1,C, T2) A*B+C3.(*, T2,B, T3) (A*B+C)*B4.(-, T3,D, T4) (A*B+C)*B-D5.(=:,T4,X )6各臨時(shí)變

3、量的定義點(diǎn)分別為：T11，T22，T33，T44各臨時(shí)變量的最后使用點(diǎn)分別為： T12，T23，T34，T45各臨時(shí)變量的活動區(qū)分別為：T11,2，T22,3，T33,4，T44,57結(jié)論: 每個(gè)臨時(shí)變量的活動區(qū)均不相交。T1，T2，T3和T4將占用同一存儲單元,從而實(shí)現(xiàn)節(jié)省存儲的目標(biāo)。 盡管在四元式中出現(xiàn)了很多臨時(shí)變量,但實(shí)際占用存儲單元的還是極少數(shù)。810.2 靜態(tài)鏈、動態(tài)鏈1. 以過程為單位的動態(tài)存儲分配 所謂以過程為單位的動態(tài)存儲分配就是以過程調(diào)用為單位來設(shè)置數(shù)據(jù)區(qū)。即設(shè)計(jì)一個(gè)數(shù)據(jù)空間棧，當(dāng)程序運(yùn)行時(shí)，每調(diào)用某過程一次，就根據(jù)該過程的說明為該過程在數(shù)據(jù)區(qū)棧的頂部分配一定數(shù)量的數(shù)據(jù)單元，

4、稱為該過程的數(shù)據(jù)區(qū)。當(dāng)調(diào)用完畢，則釋放該過程的數(shù)據(jù)區(qū)。9設(shè)有源程序：program main(input, output) const a =10; var b, c: integer; d, e: real; procedure p ( x: real ); var f: real; procedure q ( y: real ); const g = 5; var h: boolean; procedure r ( z:integer );pqr10 var i: integer; begin if e0 then q ( f ); end; r begin r ( a ); end; q

5、 begin q ( e ); end; p pqr11 procedure t ( ); var j: real; begin p ( e ); end; t begin t; end; maint12程序運(yùn)行順序和建立的數(shù)據(jù)區(qū)：主程序tp(e)q(e)r(a) q(f) 當(dāng)e0時(shí)主程序ttttt主程序主程序主程序主程序主程序p(e)p(e)p(e)p(e)q(e)q(e)q(e)r(a)r(a)q(f)123654132. 以過程為單位的存儲分配方案的實(shí)現(xiàn)主ptqr0層1層2層3層程序運(yùn)行順序：主程序tpqr14 靜態(tài)鏈：指向定義該過程的直接外層過程(或主程序)運(yùn)行時(shí)刻的數(shù)據(jù)區(qū)的首(基)地

6、址。 靜態(tài)鏈作用：當(dāng)動態(tài)地為某個(gè)過程在運(yùn)行棧頂部建立數(shù)據(jù)區(qū)后，其中靜態(tài)鏈為相應(yīng)過程體內(nèi)引用的所有變量提供了尋址途徑，使得這些變量能以它們各自擁有的存儲單元參與運(yùn)算。15 動態(tài)鏈：指向調(diào)用該過程前正在運(yùn)行的過程的數(shù)據(jù)區(qū)的首(基)地址。 返回地址：記錄了調(diào)用該過程時(shí)目標(biāo)程序的斷點(diǎn)，即當(dāng)時(shí)的程序地址寄存器的值，是調(diào)用語句指令的下一條指令的地址。 動態(tài)鏈和返回地址的作用：為了當(dāng)一個(gè)過程運(yùn)行結(jié)束后，恢復(fù)其調(diào)用前的運(yùn)行狀態(tài)。16主ptqr0層1層2層3層靜態(tài)層次：主程序 p q r 0層 1層 2層 3層17一個(gè)過程的靜態(tài)外層是唯一的，而動態(tài)外層不唯一。 運(yùn)行順序可以是: 主程序tpqr主程序 主程序tp

7、qrq主程序 主程序tpqrqr主程序動態(tài)層次：調(diào)用該過程前正在運(yùn)行的過程。1810.3 過程的活動記錄過程的一次調(diào)用將占用內(nèi)存的一片單元。在沒有可變長度數(shù)據(jù)類型的情況下對于每個(gè)過程來說，其單元片長度是固定的。在四元式方案里該長度被記錄在過程函數(shù)說明的頭四元式中，稱上述單元片為過程的活動記錄。 Display表如下圖：19top外層sp地址先行DISPLAY地址返回地址函數(shù)值形參單元本層DSPLAY表臨時(shí)變量單元局部變量單元N321sp0l +1項(xiàng)d 項(xiàng)編譯時(shí)可確定20 設(shè)一個(gè)變量X的抽象地址為(k,off),則它所對應(yīng)的動態(tài)地址addr(k,off)可按下式計(jì)算:addr(k,off)=DI

8、SPLAY(k)+off =CONTENT(sp+N+k)+off其中N是編譯可確定的。當(dāng)k為現(xiàn)役過程的層數(shù)時(shí)，有：addr(k,off)=sp+off 21例1：設(shè)有：主pqP0P1P2即靜態(tài)鏈為：主程序pq，假設(shè)動態(tài)鏈也為：主程序pq。播放動畫22DL外層SP的地址，主程序特殊直接定義外層過程的Display表的首地址RA返回地址函數(shù)值、形參單元本層Display表(主程序首地址)局部變量、臨時(shí)變量單元主程序23DL先行Display表，存主程序Display表的首地址SPRA返回地址函數(shù)值、形參單元主程序的Display表P過程活動記錄首地址SPDisplay表變量單元主程序p24DL先

9、行Display表，存P過程Display表的首地址SPRA返回地址函數(shù)值、形參單元主程序的Display表P過程活動記錄首地址SPP過程Display表q過程活動記錄首地址SPDisplay表變量單元主程序pq25例2: 現(xiàn)有靜態(tài)鏈和動態(tài)鏈相同的程序 靜態(tài)鏈 主程序 p q 動態(tài)鏈 主程序 p q 已知x的抽象地址為x( k, off )。當(dāng)程序運(yùn)行到q時(shí),求x的值。分析： 1. 當(dāng)x為q過程的變量，求x的值。 2 . 當(dāng)x為p過程的變量，求x的值。 3. 當(dāng)x為主程序的變量，求x的值。26例3: 現(xiàn)有靜態(tài)鏈和動態(tài)鏈不相同的程序 主程序 p q r t動態(tài)鏈為：主程序 t p q r27活動

10、記錄： 主程序t 過程r 過程q 過程p 過程Display表主程序Display表本層首地址函數(shù)值、形參RA返回地址主程序Display表首地址變量DL動態(tài)鏈2810.4 活動記錄的填寫每當(dāng)調(diào)用一過程時(shí)，要建立新的活動記錄；每當(dāng)退出一過程時(shí)，要刪除現(xiàn)役活動記錄；這些工作都要目標(biāo)程序來完成，主要由過程語句、過程入口和過程出口部分來完成。過程語句所完成的工作：1. 在要建立的新活動記錄里保存現(xiàn)役活動記錄的始地址: 0top:=sp. (動態(tài)鏈)292.在要建立的新活動記錄里記入先行DISPLAY表的始地址: (靜態(tài)鏈) 1)實(shí)在過程語句情形: 1top:=sp+N. 2)形式過程語句情形: 1top:=(第二形參單元). 其中第二個(gè)形參單元是給過程語句名分配的第二個(gè)單元.3.把實(shí)參信息傳送到新活動記錄區(qū)的形參單元中.4.轉(zhuǎn)向相應(yīng)過程的目標(biāo)程序.30過程入口處完成的工作：1. 在要建立的新活動記錄里保存返回地址: 2top:=返回地址. (返回地址)2. 在要建立的新活動記錄里生成DISPLAY表: 從1top所指的先行DISPLAY表自底向上抄錄 l 個(gè)單元的內(nèi)容( l