1、第六章 活動(dòng)記錄Activation Records,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 劉 慧,Stack：一個(gè)有序的積累或堆積。 幾乎所有的現(xiàn)代程序設(shè)計(jì)語(yǔ)言中，函數(shù)都可以有局部變量(local variables)，這些局部變量是在函數(shù)的入口創(chuàng)建的。 在同一時(shí)刻可能存在對(duì)函數(shù)的多個(gè)調(diào)用(invocations)，每個(gè)調(diào)用都有它自己的局部變量實(shí)例(instantiations)。,f 的每次調(diào)用都會(huì)創(chuàng)建 x 的一個(gè)新實(shí)例，因?yàn)榇嬖谶f歸調(diào)用，因此可以同時(shí)存在 x 的很多個(gè)實(shí)例。 類似地，每當(dāng)進(jìn)入f 的函數(shù)體時(shí)，都將創(chuàng)建一個(gè)y的新實(shí)例。,function f ( x : int) : int = let va

2、r y := x+x in if y 10 then f (y) else y-1 end,在很多語(yǔ)言中（例如C、Pascal和Tiger），當(dāng)函數(shù)返回時(shí)，局部于該函數(shù)的變量便都會(huì)消失，因?yàn)橐粋€(gè)函數(shù)只有在它調(diào)用的所有函數(shù)都返回以后，它才能返回。 函數(shù)調(diào)用是按后進(jìn)先出(LIFO)方式進(jìn)行的，如果在函數(shù)的入口創(chuàng)建局部變量，在函數(shù)的出口刪除它們，則可使用“棧”來(lái)存放它們。,6.1 Stack Frames,通常意義上的“?！保褐С謮喝?push)和彈出(pop)操作的數(shù)據(jù)結(jié)構(gòu)。 但是，局部變量會(huì)成批壓入和彈出棧，而且，當(dāng)局部變量在棧中被創(chuàng)建時(shí)，它們一般不會(huì)被立刻初始化。最后，當(dāng)向棧中壓入很多變量之后

3、，還會(huì)需要訪問(wèn)壓在棧頂之下較深的變量。 因此，抽象的壓入和彈出模式并不適合。,6.1 Stack Frames,可以將?？闯墒且粋€(gè)大型數(shù)組，并帶有一個(gè)特殊寄存器，即棧指針(stack pointer)。 棧中空間的劃分： 超出棧指針的所有位置為自由存儲(chǔ)空間(garbage)； 位于棧指針之前的位置為已分配存儲(chǔ)空間(allocated)。 棧通常只在函數(shù)的入口處增長(zhǎng)，它通過(guò)增加足以容納該函數(shù)的所有局部變量的一片存儲(chǔ)空間來(lái)擴(kuò)大棧。棧在函數(shù)的出口處收縮，收縮的空間就是入口時(shí)擴(kuò)大的空間。,6.1 Stack Frames,棧中用來(lái)存放一個(gè)函數(shù)的局部變量、參數(shù)、返回地址和其他臨時(shí)變量的這片區(qū)域稱為該函數(shù)

4、的活動(dòng)記錄(activation record)或棧幀(stack frame)。 棧幀布局的設(shè)計(jì)要考慮到指令集的體系結(jié)構(gòu)特征和被編譯的程序設(shè)計(jì)語(yǔ)言的特征?！皹?biāo)準(zhǔn)”棧幀布局便于被所有的程序設(shè)計(jì)語(yǔ)言編譯器采納，使得用不同程序設(shè)計(jì)語(yǔ)言編寫的函數(shù)可以相互調(diào)用。,傳入的參數(shù),高地址,前一棧幀,當(dāng)前棧幀,下一棧幀,低地址,幀指針,傳出的參數(shù),棧指針,該棧幀有一組由調(diào)用者傳入的參數(shù)(incoming argument) 返回地址是由CALL指令產(chǎn)生的，它告訴當(dāng)前函數(shù)結(jié)束時(shí)應(yīng)當(dāng)將控制返回至何處。 有些局部變量分配在棧幀內(nèi)，另一些保存在寄存器中 在當(dāng)前函數(shù)調(diào)其他函數(shù)時(shí)，可以用傳出參數(shù)空間來(lái)傳遞參數(shù)。,設(shè)函數(shù)g

5、()調(diào)用函數(shù)f(a1,a2, an)： g是調(diào)用者(caller)； f是被調(diào)用者(callee)。 在進(jìn)入函數(shù)f時(shí)，棧指針(Stack Pointer)指向g傳遞給f的第一個(gè)參數(shù)。在f的入口，f簡(jiǎn)單地使SP減去幀的長(zhǎng)度而分配一個(gè)新棧幀。,傳入的參數(shù),高地址,前一棧幀,當(dāng)前棧幀,下一棧幀,低地址,幀指針,傳出的參數(shù),棧指針,6.1.1 The Frame Pointer,原來(lái)的SP則變成了當(dāng)前的幀指針(Frame Pointer)。 某些棧幀布局中： FP是一個(gè)單獨(dú)的寄存器； 原來(lái)的FP保存在存儲(chǔ)器中（棧幀內(nèi)）。 當(dāng)函數(shù)f退出時(shí)，需要復(fù)制FP到SP，并取回保存在存儲(chǔ)器中的FP。 適合于棧幀大小

6、可變或不連續(xù)的情況。,傳入的參數(shù),高地址,前一棧幀,當(dāng)前棧幀,下一棧幀,低地址,幀指針,傳出的參數(shù),棧指針,6.1.1 The Frame Pointer,如果棧幀的大小是固定不變的，則對(duì)于每一個(gè)函數(shù)f，F(xiàn)P與SP所指的位置總是相差一個(gè)已知的常數(shù)：“虛”寄存器FP=SP+棧幀大小。 問(wèn)題：當(dāng)棧幀大小是常數(shù)時(shí)，為何還討論幀指針 棧幀的大小要到編譯處理相當(dāng)晚的時(shí)候才能知道，即要到給臨時(shí)變量分配的空間大小和用于保護(hù)寄存器的空間大小都已確定時(shí)。但是，盡早知道形參與局部變量的位移量是有好處的。,6.1.1 The Frame Pointer,將局部變量、表達(dá)式的中間結(jié)果和其他值保存在寄存器中，而不是放在

7、棧幀中，將有助于編譯生成的程序快速地運(yùn)行。 算術(shù)指令可以直接訪問(wèn)寄存器。 在大多數(shù)計(jì)算機(jī)中，存儲(chǔ)器的訪問(wèn)需要使用獨(dú)立的存取指令(load and store instructions)。即使在那種算術(shù)指令可以訪問(wèn)存儲(chǔ)器的計(jì)算機(jī)中，訪問(wèn)寄存器的速度也比訪問(wèn)存儲(chǔ)器快。,6.1.2 Register,假設(shè)函數(shù)f在用寄存器r保存了它的一個(gè)局部變量的同時(shí)調(diào)用過(guò)程g，而過(guò)程g也需用r完成自己的計(jì)算： 在g使用r之前先將r保護(hù)起來(lái)（將它保存在棧幀內(nèi)）； 完成計(jì)算而不再需要時(shí)將r恢復(fù)（從幀棧中取回被保存的內(nèi)容）。 保護(hù)和恢復(fù)該寄存器的責(zé)任： 如果由調(diào)用者f來(lái)保護(hù)和恢復(fù)，則稱r為調(diào)用者保護(hù)的(caller-sa

8、ve)寄存器; 如果由被調(diào)用者g來(lái)保護(hù)和恢復(fù)，則稱r為被調(diào)用者保護(hù)的(callee-save)寄存器;,6.1.2 Register,在多數(shù)計(jì)算機(jī)體系結(jié)構(gòu)中，調(diào)用者保護(hù)的寄存器和被調(diào)用者保護(hù)的寄存器的概念并不是由硬件來(lái)實(shí)現(xiàn)的，而是在機(jī)器參考手冊(cè)(machines reference manual)中規(guī)定的。 例如MIPS計(jì)算機(jī)： 保留寄存器r16-r23用于跨過(guò)程調(diào)用（屬于被調(diào)用者保護(hù)的寄存器）； 其他所有寄存器則不保留用于跨過(guò)程調(diào)用（屬于調(diào)用者保護(hù)的寄存器）。,6.1.2 Register,保護(hù)和恢復(fù)寄存器的特殊情況： 如果f知道某個(gè)變量x的值在函數(shù)調(diào)用以后將不再需要，它可以把x放在一個(gè)調(diào)用

9、者保護(hù)的寄存器中，并且在調(diào)用過(guò)程g時(shí)不保護(hù)它。 如果f有一個(gè)局部變量i，并且在若干次函數(shù)調(diào)用之前和之后都需使用，則可以把i放在某個(gè)被調(diào)用者保護(hù)的寄存器ri中，并且只在f的入口保護(hù)ri一次，在f的出口將ri取回一次。 這樣，明智地為局部變量和臨時(shí)變量選擇調(diào)用者或被調(diào)用者保護(hù)的寄存器，便可以減少程序執(zhí)行存儲(chǔ)操作的次數(shù)。,6.1.2 Register,現(xiàn)代計(jì)算機(jī)中的參數(shù)傳遞約定：一個(gè)函數(shù)的前k個(gè)參數(shù)（典型地，k=4或k=6）放在寄存器rp, rp+k-1中傳遞，剩余的參數(shù)則放在存儲(chǔ)器中傳遞。,實(shí)例：假設(shè)函數(shù)f(a1, ,an)（它從r1, ,rn接收其參數(shù)） 調(diào)用函數(shù)h(z)。它必須通過(guò)寄存器r1傳

10、遞參數(shù)z，因此f 需要在調(diào)用h之前將r1原來(lái)的內(nèi)容（a1的內(nèi)容）保護(hù)到 它的棧幀中。,6.1.3 Parameter passing,問(wèn)題1：原本假定通過(guò)將參數(shù)傳遞在寄存器中可以避免的存儲(chǔ)器訪問(wèn)，怎樣使用寄存器節(jié)省時(shí)間呢？ 某些過(guò)程并不調(diào)用其他的過(guò)程leaf procedure（葉過(guò)程），葉過(guò)程不必將傳入的參數(shù)保存到存儲(chǔ)器中，?？梢圆粸樗鼈兎峙錀?，這是一種重要的節(jié)省。 有些優(yōu)化編譯器使用過(guò)程間寄存器分配(interprocedural register allocation)，可以一次分析整個(gè)程序中的所有函數(shù)。這樣編譯器便可以給不同的過(guò)程指派不同的寄存器用于接收參數(shù)和存放局部變量。,6.1.

11、3 Parameter passing,問(wèn)題1：原本假定通過(guò)將參數(shù)傳遞在寄存器中可以避免的存儲(chǔ)器訪問(wèn)，怎樣使用寄存器節(jié)省時(shí)間呢？ 即使f不是葉過(guò)程，它仍有可能在調(diào)函數(shù)h之前完成所有需要使用參數(shù)x的操作，于是f可以重寫r1，而不需保護(hù)它。 某些體系結(jié)構(gòu)有寄存器窗口，它們使得每次函數(shù)調(diào)用都分配一組新的寄存器，而無(wú)需存儲(chǔ)訪問(wèn)。,6.1.3 Parameter passing,問(wèn)題2：如果函數(shù)f需要將傳入的參數(shù)寫到棧幀中，應(yīng)當(dāng)寫到棧幀的什么位置呢？ 直接處理方法：調(diào)用者將參數(shù)a1, ,ak傳遞至寄存器中，將參數(shù)ak+1, ,an傳遞到它自己的棧幀的末尾，即傳出參數(shù)的位置，它們將成為被調(diào)用者的傳入?yún)?shù)。

12、 如果被調(diào)用者需要將這些參數(shù)寫至存儲(chǔ)器，則可以將它們寫到標(biāo)記為局部變量的區(qū)域內(nèi)。,6.1.3 Parameter passing,取局部變量地址的一種更優(yōu)雅的方法是采用傳地址方式：程序員不必顯示地操作變量x的地址，替代地，當(dāng)x作為實(shí)參傳遞給函數(shù)f(y)時(shí)，如果y是“傳地址”參數(shù)，編譯器將生成傳遞x的地址，而不是x的值的代碼。,6.1.3 Parameter passing,當(dāng)函數(shù)f被函數(shù)g調(diào)用時(shí)，它最終必須返回，因此需要知道應(yīng)返回到何處。 將返回地址傳遞到寄存器中要更快、更靈活，并可避免存儲(chǔ)訪問(wèn)，call指令只需將返回地址（call指令后下一條指令的地址）放入指定的寄存器中。 非葉過(guò)程必須將返

13、回地址保存到自己的棧幀中； 葉過(guò)程則不需要保護(hù)它。,如果函數(shù)g中調(diào)用f的call指令位于地址a，則正確的 返回地址是a+1，即g中call指令的下一條指令處。 這個(gè)地址稱為返回地址(return address)。,6.1.4 Return addresses,綜上所述，很多局部變量以及表達(dá)式的中間結(jié)果都將分配到寄存器中。 只有下述情況將一個(gè)變量值寫入到存儲(chǔ)器中（棧幀） 該變量作為傳地址參數(shù)； 該變量被嵌套在當(dāng)前過(guò)程內(nèi)的過(guò)程訪問(wèn)； 該變量的值太大以致于不能將它放入到單個(gè)寄存器中； 該變量是一個(gè)數(shù)組，為了引用其元素需要地址運(yùn)算； 存在太多的局部變量和臨時(shí)變量，“溢出”到棧幀中。,6.1.5 Fr

14、ame-resident variables,在允許聲明嵌套函數(shù)的語(yǔ)言中，內(nèi)層函數(shù)可以調(diào)用外層函數(shù)聲明的變量，這種語(yǔ)言特征被稱為塊結(jié)構(gòu)(block struction)。,6.1.6 Static links,1 type tree = key: string, left: tree, right: tree 2 3 function prettyprint ( tree: tree): string = 4 let 5 var output :=“ ” 6 7 function write (s: string) = 8 output :=concat (output,s),函數(shù)write引

15、用了外層聲明的變量output。,函數(shù)indent引用了外層聲明的變量n和output。Indent不僅要訪問(wèn)自己的棧幀（訪問(wèn)變量i和s），還要能夠訪問(wèn)函數(shù)show的棧幀（訪問(wèn)變量n）和函數(shù)prettyprint的棧幀（訪問(wèn)變量output）。,10 function show (n:int, t:string) = 11 let function indent (s:string) = 12 (for i := i to n 13 do write(“ ”); 14 output := concat (output,s); write(“n”) 15 in if t=nil then ind

16、ent(“.”) 16 else (indent (t.key); 17 show(n+1,t.left); 18 show(n+1,t.right) 19 end 20 20 in show(0,tree); output 21 end,實(shí)現(xiàn)方法： 每當(dāng)調(diào)用函數(shù)f 時(shí)，便傳遞給f 一個(gè)指針，該指針指向在程序中直接包含f 的函數(shù)g的“當(dāng)前”（最近一次進(jìn)入的）活動(dòng)記錄。稱這個(gè)指針為靜態(tài)鏈(static link)。 舉例：Program6.3 21行，prettyprint調(diào)用show，傳遞自己的幀指針作為show的靜態(tài)鏈。 10行，show將靜態(tài)鏈（prettyprint的棧幀地址）保存在它自己的棧幀中。 15行，show調(diào)用indent，傳遞自己的幀指針作為indent的靜態(tài)鏈。,6.1.6 Static li