Chapter9

Run-TimeEnvironments概述存儲分配策略（Storage-allocationstrategies）訪問非局部名字（Accesstononlocalnames）參數傳遞（Parameterpassing）11/23/20221Chapter9

Run-TimeEnvironme9.1概述在生成目標代碼之前，必須了解目標代碼執(zhí)行時的環(huán)境1、空間環(huán)境目標代碼的運行都是在操作系統(tǒng)分配的一塊存儲區(qū)內進行的這塊存儲區(qū)必須容納目標代碼和目標代碼運行時的數據空間（目標代碼中指令能訪問的空間）11/23/202229.1概述在生成目標代碼之前，必須了解目標代碼執(zhí)行時的環(huán)9.1概述編譯程序分配目標程序運行時的數據空間的基本依據是設計程序語言時對程序運行中存儲空間的使用和管理辦法的規(guī)定代碼生成器在生成目標代碼時必須要體現該程序語言在設計時分配數據空間的規(guī)定11/23/202239.1概述編譯程序分配目標程序運行時的數據空間的基本依據9.1概述2、寄存器環(huán)境寄存器是目標機器中的寶貴資源如何分配寄存器提高程序運行的效率是代碼生成器主要要解決的問題，（詳細內容見下一講）**數據空間分配和寄存器分配最后都體現在生成的目標代碼中11/23/202249.1概述2、寄存器環(huán)境寄存器是目標機器中的寶貴資源如何9.1概述幾種典型程序設計語言的特點不同的語言有不同的分配數據空間的規(guī)定，有不同的組織運行時刻存儲空間的方法11/23/202259.1概述幾種典型程序設計語言的特點不同的語言有不同的分9.1概述幾種典型程序設計語言的特點與差異：CPASCALALGOLFORTRAN過程遞歸調用過程嵌套定義動態(tài)數組動態(tài)內存申請指針檢查√××√×√√×√√√√√×√×

×

×

×√11/23/202269.1概述幾種典型程序設計語言的特點與差異：CPASCA9.1概述名字的聯編（BindingsofNames）名字的左值(l-value)—內存地址，存儲名字的瞬時值名字的右值(r-value)—名字的瞬時值名字的聯編—將一個內存地址與一個名字聯系起來在程序的一次運行中，一個名字右值（瞬時值）可能會經常改變，一個名字也可能被聯編到多個地址（如遞歸調用中）11/23/202279.1概述名字的聯編（BindingsofNames9.1概述運行時刻內存的典型劃分操作系統(tǒng)收到運行目標程序的指令，分配一塊連續(xù)的內存空間使目標程序在其上運行P397Fig7.7這只是一個典型的劃分，具體語言不同，該劃分也不同棧（Stack）：支持過程的遞歸調用堆（Heap）：支持動態(tài)內存申請11/23/202289.1概述運行時刻內存的典型劃分操作系統(tǒng)收到運行目標程序9.1概述活動記錄（ActivationRecords）是一段連續(xù)的存儲區(qū)，用以存放過程的一次執(zhí)行所需要的信息，如局部數據活動記錄的結構P398Fig7.8參數域、狀態(tài)域、數據域TOP指向棧頂，TOP-SP指向局部數據區(qū)的開始位置**這只是一個一般的結構，具體語言不同，活動記錄的結構和內容也有差異11/23/202299.1概述活動記錄（ActivationRecords9.1概述過程的活動（Activation）過程的一次完整執(zhí)行（第一條語句到最后一條語句），稱為過程的一次活動過程在執(zhí)行中稱它為活著的如果允許遞歸調用，程序的一次執(zhí)行可能有同一個過程的多個實例是活著的**本章主要討論不同語言的目標程序在運行時的存儲分配策略及名字與其左值和右值的關系11/23/2022109.1概述過程的活動（Activation）過程的一次完9.2存儲分配策略靜態(tài)存儲分配（Staticallocation）編譯時確定所需的全部數據空間的大小編譯時安排好每個名字的存儲位置（相對地址）采用靜態(tài)存儲分配的典型語言是FORTRAN11/23/2022119.2存儲分配策略靜態(tài)存儲分配（Staticalloc9.2存儲分配策略FORTRAN語言程序是段結構的，主程序段+若干子程序（函數）段沒有動態(tài)數據類型，每個名字所需空間是確定的沒有遞歸調用，無需棧區(qū)沒有動態(tài)數據結構（如鏈表），沒有動態(tài)內存申請，無需堆區(qū)11/23/2022129.2存儲分配策略FORTRAN語言程序是段結構的，主9.2存儲分配策略因此，編譯時可確定數據區(qū)大小，為每個名字分配好地址FORTRAN程序運行時內存劃分為目標代碼區(qū)和靜態(tài)數據區(qū)，沒有棧區(qū)和堆區(qū)程序例子：P402example7.4Fig.7.10Fig.7.11Fig.7.1211/23/2022139.2存儲分配策略因此，編譯時可確定數據區(qū)大小，為每個名9.2存儲分配策略程序設計語言若允許遞歸調用、可變數組、可變數據結構：編譯時無法確定運行時需要的存儲空間大小動態(tài)存儲分配包括：棧式分配（Stackallocation）和堆式分配（Heapallocation）只能在運行時動態(tài)地確定，采用動態(tài)存儲分配11/23/2022149.2存儲分配策略程序設計語言若允許遞歸調用、可變數組、9.2存儲分配策略棧式存儲分配的思想：在運行空間中劃分一塊存儲空間作為棧區(qū)程序運行時每當調用一個過程，就將該過程的活動記錄壓入棧中，過程執(zhí)行完畢將它的活動記錄從棧中彈出例子：P405Fig.7.1311/23/2022159.2存儲分配策略棧式存儲分配的思想：在運行空間中劃分一9.2存儲分配策略棧式存儲分配的實現反映在目標代碼生成器的構造策略中，最終體現在生成的目標代碼中調用序列(CallSequence)目標代碼中的一個指令序列，完成調用一個過程的一系列操作，包括為被調用過程分配一個活動記錄，并在相應的域中填入信息11/23/2022169.2存儲分配策略棧式存儲分配的實現反映在目標代碼生成器9.2存儲分配策略返回序列(ReturnSequence)目標代碼中的一個指令序列，完成從一個被調用過程返回到它的調用過程的一系列操作，包括釋放被調用過程的活動記錄，并復制出返回值具體內容：P407Fig.7.1411/23/2022179.2存儲分配策略返回序列(ReturnSequenc9.2存儲分配策略有些程序設計語言允許用戶自由申請內存空間，如C的malloc和free，PASCAL的new和dispose何時申請何時釋放由用戶決定有些程序設計語言在進行數據空間分配時不服從棧式的存儲分配原則（即“先申請后釋放、后申請先釋放”）11/23/2022189.2存儲分配策略有些程序設計語言允許用戶自由申請內存空9.2存儲分配策略這時采用堆式存儲分配方案運行空間劃分一塊堆區(qū)用戶（顯式）或目標代碼需要時從這堆中借用一塊，不用時退還**這是一種完全動態(tài)的存儲分配方案11/23/2022199.2存儲分配策略這時采用堆式存儲分配方案運行空間劃分一9.3訪問非局部名字非局部名字相對于引用點所在的過程或分程序來說的程序執(zhí)行時引用的在當前過程（分程序）之外定義的變量稱為非局部名字**本節(jié)主要討論棧式存儲分配中如何訪問非局部名字11/23/2022209.3訪問非局部名字非局部名字相對于引用點所在的過程或分9.3訪問非局部名字最近嵌套的作用域規(guī)則（mostcloselynestedrule）P412這是大多數程序設計語言采用的作用域規(guī)則例子：P416Fig.7.22（過程）例子：P413Fig.7.18（塊或分程序）11/23/2022219.3訪問非局部名字最近嵌套的作用域規(guī)則P4129.3訪問非局部名字分程序（塊）結構——ALGOL和C分程序（塊）含有局部數據說明的語句序列有定界符號，允許嵌套例子：P413Fig.7.1811/23/2022229.3訪問非局部名字分程序（塊）結構——ALGOL9.3訪問非局部名字過程（活動記錄）采用棧式存儲分配，分程序中的局部數據在活動記錄的局部數據區(qū)內也采用棧式分配并列的分程序中的名字可分配同一個地址，因為它們所屬的分程序不會在同一時刻存活訪問同一過程中的局部名字可以從棧頂到棧底進行定位（同一活動記錄中）Fig.7.19**訪問其它過程中的局部名字見下面的討論11/23/2022239.3訪問非局部名字過程（活動記錄）采用棧式存儲分配，分9.3訪問非局部名字無過程嵌套定義——C程序中引用的名字或者在當前的過程中被定義，或者在所有過程之外被定義在所有過程之外被定義的變量，稱之為全局變量，被存放在靜態(tài)數據區(qū)，地址在編譯時刻確定（放符號表中）11/23/2022249.3訪問非局部名字無過程嵌套定義——C程序中引用的9.3訪問非局部名字過程中的局部名字聯編到過程的活動記錄的局部數據區(qū)中訪問非局部名字可根據符號表中該變量的地址直接到全局靜態(tài)數據區(qū)中查找11/23/2022259.3訪問非局部名字過程中的局部名字聯編到過程的活動記錄9.3訪問非局部名字有過程嵌套定義——PASCALPASCAL語言的一個例子P416過程和函數的嵌套深度（nestingdepth）訪問非局部名字的方法有兩種，一種是通過存取鏈，一種是通過DISPLAY表主程序為111/23/2022269.3訪問非局部名字有過程嵌套定義——PASCALP9.3訪問非局部名字存取鏈（accesslinks）活動記錄中的一個區(qū)，是一個指針若過程P直接嵌入在過程Q中，則P的活動記錄中的存取鏈指向Q的最近的活動記錄中的存取鏈11/23/2022279.3訪問非局部名字存取鏈（accesslinks）活9.3訪問非局部名字如何建立存取鏈？參見P417Fig.7.23（a）（b）（c）（d）區(qū)分兩種情況：P4181、Np<Nx，Np是調用者深度，Nx是被調用者深度2、Np>=NxNp–Nx+1

11/23/2022289.3訪問非局部名字如何建立存取鏈？參見P417F9.3訪問非局部名字如何利用存取鏈訪問非局部名字？根據當前過程的嵌套深度和非局部名字所在過程的嵌套深度，可以計算出需順著存取鏈前進的步數，從而對非局部名字進行訪問Np–Na11/23/2022299.3訪問非局部名字如何利用存取鏈訪問非局部名字？根據當9.3訪問非局部名字DISPLAY表是一個指向活動記錄的指針數組運行時刻要訪問的嵌套深度為i的非局部名字就在d[i]所指的活動記錄中這種方法只要一步就可到達要訪問的非局部名字的活動記錄，比存取鏈方法高效11/23/2022309.3訪問非局部名字DISPLAY表是一個指向活動記錄的9.3訪問非局部名字如何建立與維護DISPLAY表？DISPLAY表的大小由程序中嵌套深度最大的過程決定參見P421Fig.7.26（a）（b）（c）（d）11/23/2022319.3訪問非局部名字如何建立與維護DISPLAY表？9.3訪問非局部名字當建立嵌套深度為i的過程的活動記錄時，首先在新的活動記錄中保存d[i]的值，然后置d[i]指向新的活動記錄注意考慮調用和返回兩種情況當從過程中返回時，從活動記錄中恢復老的d[i]的值11/23/2022329.3訪問非局部名字當建立嵌套深度為i的過程的活動記9.4參數傳遞傳值調用（Call-by-Value）把實在參數的右值傳遞給形式參數調用序列計算實在參數的值，并將它復制到被調用過程活動記錄的參數域中這種參數傳遞方法對調用過程的活動記錄沒有影響11/23/2022339.4參數傳遞傳值調用（Call-by-Value）把實9.4參數傳遞引用調用（Call-by-Reference）把實在參數的左值（地址）傳遞給形式參數調用序列將實在參數的左值（地址）復制到被調用過程活動記錄的參數域中被調用過程對形式參數的引用其實是對實在參數的地址（在被調用過程的活動記錄中）進行引用11/23/2022349.4參數傳遞引用調用（Call-by-Referenc9.4參數傳遞復制恢復（Copy-Restore）傳遞參數同傳值調用在從被調用過程返回前，把形式參數的現行右值復制回相應的實在參數的左值中這種方法與引用調用是有區(qū)別的：在被調用過程體中訪問了非局部名字，而此非局部名字正是形式參數時P427Fig.7.3111/23/2022359.4參數傳遞復制恢復（Copy-Restore）傳遞參9.4參數傳遞傳名調用（Call-by-Name）用實在參數對過程體進行宏擴展，必要時對被調用過程中的名字進行改名（防止與調用過程中的名字重復）**例子：P456練習7.6Fig.7.5311/23/2022369.4參數傳遞傳名調用（Call-by-Name）用實在TheEnd!11/23/202237TheEnd!11/22/202237Chapter9

Run-TimeEnvironments概述存儲分配策略（Storage-allocationstrategies）訪問非局部名字（Accesstononlocalnames）參數傳遞（Parameterpassing）11/23/202238Chapter9

Run-TimeEnvironme9.1概述在生成目標代碼之前，必須了解目標代碼執(zhí)行時的環(huán)境1、空間環(huán)境目標代碼的運行都是在操作系統(tǒng)分配的一塊存儲區(qū)內進行的這塊存儲區(qū)必須容納目標代碼和目標代碼運行時的數據空間（目標代碼中指令能訪問的空間）11/23/2022399.1概述在生成目標代碼之前，必須了解目標代碼執(zhí)行時的環(huán)9.1概述編譯程序分配目標程序運行時的數據空間的基本依據是設計程序語言時對程序運行中存儲空間的使用和管理辦法的規(guī)定代碼生成器在生成目標代碼時必須要體現該程序語言在設計時分配數據空間的規(guī)定11/23/2022409.1概述編譯程序分配目標程序運行時的數據空間的基本依據9.1概述2、寄存器環(huán)境寄存器是目標機器中的寶貴資源如何分配寄存器提高程序運行的效率是代碼生成器主要要解決的問題，（詳細內容見下一講）**數據空間分配和寄存器分配最后都體現在生成的目標代碼中11/23/2022419.1概述2、寄存器環(huán)境寄存器是目標機器中的寶貴資源如何9.1概述幾種典型程序設計語言的特點不同的語言有不同的分配數據空間的規(guī)定，有不同的組織運行時刻存儲空間的方法11/23/2022429.1概述幾種典型程序設計語言的特點不同的語言有不同的分9.1概述幾種典型程序設計語言的特點與差異：CPASCALALGOLFORTRAN過程遞歸調用過程嵌套定義動態(tài)數組動態(tài)內存申請指針檢查√××√×√√×√√√√√×√×

×

×

×√11/23/2022439.1概述幾種典型程序設計語言的特點與差異：CPASCA9.1概述名字的聯編（BindingsofNames）名字的左值(l-value)—內存地址，存儲名字的瞬時值名字的右值(r-value)—名字的瞬時值名字的聯編—將一個內存地址與一個名字聯系起來在程序的一次運行中，一個名字右值（瞬時值）可能會經常改變，一個名字也可能被聯編到多個地址（如遞歸調用中）11/23/2022449.1概述名字的聯編（BindingsofNames9.1概述運行時刻內存的典型劃分操作系統(tǒng)收到運行目標程序的指令，分配一塊連續(xù)的內存空間使目標程序在其上運行P397Fig7.7這只是一個典型的劃分，具體語言不同，該劃分也不同棧（Stack）：支持過程的遞歸調用堆（Heap）：支持動態(tài)內存申請11/23/2022459.1概述運行時刻內存的典型劃分操作系統(tǒng)收到運行目標程序9.1概述活動記錄（ActivationRecords）是一段連續(xù)的存儲區(qū)，用以存放過程的一次執(zhí)行所需要的信息，如局部數據活動記錄的結構P398Fig7.8參數域、狀態(tài)域、數據域TOP指向棧頂，TOP-SP指向局部數據區(qū)的開始位置**這只是一個一般的結構，具體語言不同，活動記錄的結構和內容也有差異11/23/2022469.1概述活動記錄（ActivationRecords9.1概述過程的活動（Activation）過程的一次完整執(zhí)行（第一條語句到最后一條語句），稱為過程的一次活動過程在執(zhí)行中稱它為活著的如果允許遞歸調用，程序的一次執(zhí)行可能有同一個過程的多個實例是活著的**本章主要討論不同語言的目標程序在運行時的存儲分配策略及名字與其左值和右值的關系11/23/2022479.1概述過程的活動（Activation）過程的一次完9.2存儲分配策略靜態(tài)存儲分配（Staticallocation）編譯時確定所需的全部數據空間的大小編譯時安排好每個名字的存儲位置（相對地址）采用靜態(tài)存儲分配的典型語言是FORTRAN11/23/2022489.2存儲分配策略靜態(tài)存儲分配（Staticalloc9.2存儲分配策略FORTRAN語言程序是段結構的，主程序段+若干子程序（函數）段沒有動態(tài)數據類型，每個名字所需空間是確定的沒有遞歸調用，無需棧區(qū)沒有動態(tài)數據結構（如鏈表），沒有動態(tài)內存申請，無需堆區(qū)11/23/2022499.2存儲分配策略FORTRAN語言程序是段結構的，主9.2存儲分配策略因此，編譯時可確定數據區(qū)大小，為每個名字分配好地址FORTRAN程序運行時內存劃分為目標代碼區(qū)和靜態(tài)數據區(qū)，沒有棧區(qū)和堆區(qū)程序例子：P402example7.4Fig.7.10Fig.7.11Fig.7.1211/23/2022509.2存儲分配策略因此，編譯時可確定數據區(qū)大小，為每個名9.2存儲分配策略程序設計語言若允許遞歸調用、可變數組、可變數據結構：編譯時無法確定運行時需要的存儲空間大小動態(tài)存儲分配包括：棧式分配（Stackallocation）和堆式分配（Heapallocation）只能在運行時動態(tài)地確定，采用動態(tài)存儲分配11/23/2022519.2存儲分配策略程序設計語言若允許遞歸調用、可變數組、9.2存儲分配策略棧式存儲分配的思想：在運行空間中劃分一塊存儲空間作為棧區(qū)程序運行時每當調用一個過程，就將該過程的活動記錄壓入棧中，過程執(zhí)行完畢將它的活動記錄從棧中彈出例子：P405Fig.7.1311/23/2022529.2存儲分配策略棧式存儲分配的思想：在運行空間中劃分一9.2存儲分配策略棧式存儲分配的實現反映在目標代碼生成器的構造策略中，最終體現在生成的目標代碼中調用序列(CallSequence)目標代碼中的一個指令序列，完成調用一個過程的一系列操作，包括為被調用過程分配一個活動記錄，并在相應的域中填入信息11/23/2022539.2存儲分配策略棧式存儲分配的實現反映在目標代碼生成器9.2存儲分配策略返回序列(ReturnSequence)目標代碼中的一個指令序列，完成從一個被調用過程返回到它的調用過程的一系列操作，包括釋放被調用過程的活動記錄，并復制出返回值具體內容：P407Fig.7.1411/23/2022549.2存儲分配策略返回序列(ReturnSequenc9.2存儲分配策略有些程序設計語言允許用戶自由申請內存空間，如C的malloc和free，PASCAL的new和dispose何時申請何時釋放由用戶決定有些程序設計語言在進行數據空間分配時不服從棧式的存儲分配原則（即“先申請后釋放、后申請先釋放”）11/23/2022559.2存儲分配策略有些程序設計語言允許用戶自由申請內存空9.2存儲分配策略這時采用堆式存儲分配方案運行空間劃分一塊堆區(qū)用戶（顯式）或目標代碼需要時從這堆中借用一塊，不用時退還**這是一種完全動態(tài)的存儲分配方案11/23/2022569.2存儲分配策略這時采用堆式存儲分配方案運行空間劃分一9.3訪問非局部名字非局部名字相對于引用點所在的過程或分程序來說的程序執(zhí)行時引用的在當前過程（分程序）之外定義的變量稱為非局部名字**本節(jié)主要討論棧式存儲分配中如何訪問非局部名字11/23/2022579.3訪問非局部名字非局部名字相對于引用點所在的過程或分9.3訪問非局部名字最近嵌套的作用域規(guī)則（mostcloselynestedrule）P412這是大多數程序設計語言采用的作用域規(guī)則例子：P416Fig.7.22（過程）例子：P413Fig.7.18（塊或分程序）11/23/2022589.3訪問非局部名字最近嵌套的作用域規(guī)則P4129.3訪問非局部名字分程序（塊）結構——ALGOL和C分程序（塊）含有局部數據說明的語句序列有定界符號，允許嵌套例子：P413Fig.7.1811/23/2022599.3訪問非局部名字分程序（塊）結構——ALGOL9.3訪問非局部名字過程（活動記錄）采用棧式存儲分配，分程序中的局部數據在活動記錄的局部數據區(qū)內也采用棧式分配并列的分程序中的名字可分配同一個地址，因為它們所屬的分程序不會在同一時刻存活訪問同一過程中的局部名字可以從棧頂到棧底進行定位（同一活動記錄中）Fig.7.19**訪問其它過程中的局部名字見下面的討論11/23/2022609.3訪問非局部名字過程（活動記錄）采用棧式存儲分配，分9.3訪問非局部名字無過程嵌套定義——C程序中引用的名字或者在當前的過程中被定義，或者在所有過程之外被定義在所有過程之外被定義的變量，稱之為全局變量，被存放在靜態(tài)數據區(qū)，地址在編譯時刻確定（放符號表中）11/23/2022619.3訪問非局部名字無過程嵌套定義——C程序中引用的9.3訪問非局部名字過程中的局部名字聯編到過程的活動記錄的局部數據區(qū)中訪問非局部名字可根據符號表中該變量的地址直接到全局靜態(tài)數據區(qū)中查找11/23/2022629.3訪問非局部名字過程中的局部名字聯編到過程的活動記錄9.3訪問非局部名字有過程嵌套定義——PASCALPASCAL語言的一個例子P416過程和函數的嵌套深度（nestingdepth）訪問非局部名字的方法有兩種，一種是通過存取鏈，一種是通過DISPLAY表主程序為111/23/2022639.3訪問非局部名字有過程嵌套定義——PASCALP9.3訪問非局部名字存取鏈（accesslinks）活動記錄中的一個區(qū)，是一個指針若過程P直接嵌入在過程Q中，則P的活動記錄中的存取鏈指向Q的最近的活動記錄中的存取鏈11/23/2022649.3訪問非局部名字存取鏈（accesslinks）活9.3訪問非局部名字如何建立存取鏈？參見P417Fig.7.23（a）（b）（c）（d）區(qū)分兩種情況：P4181、Np<Nx，Np是調用者深度，Nx是被調用者深度2、Np>=NxNp–Nx+1

11/23/2022659.3訪問非局部名字如何建立存取鏈？參見P417F9.3訪問非局部名字如何利用存取鏈訪問非局部名字？根據當前過程的嵌套深度和非局部名字所在過程的嵌套深度，可以計算出需順著存取鏈前進的步數，從而對非局部名字進行訪問Np–Na11/23/2022669.3訪問非局部名字如何利