DOC PREVIEW
Princeton COS 320 - Activation Record

This preview shows page 1-2-3-25-26-27 out of 27 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Activation Records¯Modern imperative programming languages typically have local variables.– Created upon entry to function.– Destroyed when function returns.¯Each invocation of a function has its own instantiation of local variables.– Recursive calls to a function require several instantiations to exist simultaneously.– Functions return only after all functions it calls have returnedµlast-in-first-out(LIFO) behavior.– A LIFO structure called a stack is used to hold each instantiation.¯The portion of the stack used for an invocation of a function is called the function’sstack frame or activation record.Computer Science 320Prof. David Walker-1-The StackThe Stack¯Used to hold local variables.¯Large array which typically grows downwards in memory toward lower addresses,shrinks upwards.¯Push(r1):stack_pointer--;M[stack_pointer] = r1;¯r1 = Pop():r1 = M[stack_pointer];stack_pointer++;¯Previous activation records need to be accessed, so push/pop not sufficient.– Treat stack as array with index off of stackpointer.– Push and pop entire activation records.Computer Science 320Prof. David Walker-2-ExampleConsider:letfunction g(x:int) =letvary:=10inx+yendfunction h(y:int):int =y + g(y)inh(4)endComputer Science 320Prof. David Walker-3-ExampleStep 1: h(4) calledChunk of memory allocated on the stack in order to hold local variables of h. Theactivation record (or stack frame) of h is pushed onto the stack.StackFramefor hy=4Step 2: g(4) calledActivation record for g allocated (pushed) on stack.StackFramefor hy=4StackFramefor gx=4y=10Computer Science 320Prof. David Walker-4-ExampleStep 3: g(4) returns with value 14Activation record for g deallocated (popped) from stack.StackFramefor h rv = 14y=4Step 4: h(4) returns with value 18Activation record for h deallocated (popped) from stack. Stack now empty.Computer Science 320Prof. David Walker-5-Recursive ExampleCan have multiple stack frames for same function (different invocations) on stack at anygiven time due to recursion.Consider:letfunction fact(n:int):int =if n = 0 then 1else n * fact(n - 1)infact(3)endStep 1: Record for fact(3) pushed on stack.StackFramefor factn=3Computer Science 320Prof. David Walker-6-Recursive ExampleStep 2: Record for fact(2) pushed on stack.StackFramefor factn=3StackFramefor factn=2Step 3: Record for fact(1) pushed on stack.StackFramefor factn=3StackFramefor factn=2StackFramefor factn=1Computer Science 320Prof. David Walker-7-Recursive ExampleStep 4: Record for fact(0) pushed on stack.StackFramefor factn=3StackFramefor factn=2StackFramefor factn=1StackFramefor factn=0Step 5: Record for fact(0) popped off stack, 1 returned.Step 6: Record for fact(1) popped off stack, 1 returned.Step 7: Record for fact(2) popped off stack, 2 returned.Step 8: Record for fact(3) popped off stack, 3 returned. Stack now empty.Computer Science 320Prof. David Walker-8-Functional LanguagesIn some functional languages (such as ML, Scheme), local variables cannot be storedon stack.fun f(x) =letfun g(y) = x + yingendConsider:- val z = f(4)- val w = z(5)Assume variables are stack-allocated.Computer Science 320Prof. David Walker-9-Functional Language ExampleStep 1: f(4) called.Frame for f(4) pushed, g returned, frame for f(4) popped.StackFramefor fx=4Stack empty.Step 3: z(5) calledStackFramefor zy=5Memory location containing x has been deallocated!Computer Science 320Prof. David Walker-10-Functional LanguagesCombination of nested functions and functions returned as results (higher-order func-tions):¯Requires local variables to remain in existence even after enclosing function hasbeen returned.¯Activation records must be allocated on heap, not stack.Concentrate on languages which use stack.Computer Science 320Prof. David Walker-11-Stack Frame OrganizationHow is data organized in stack frame?¯Compiler can use any layout scheme that is convenient.¯Microprocessor manufactures specify “standard” layout schemes used by all com-pilers.– Sometimes referred to as Calling Conventions.– If all compilers use the same calling conventions, then functions compiled withone compiler can call functions compiled with another.– Essential for interaction with OS/libraries.Computer Science 320Prof. David Walker-12-Typical Stack Framearg n...arg 2arg 1local var 1local var 2...Return AddressTemporariesSaved RegistersStack Pointer(SP) ->Frame Pointer(FP) ->Higher AddressesLower AddressesGarbagelocal var mCurrent FramePrevious FrameCallee can access arguments byoffset from FP:argument 1: M[FP]argument 2: M[FP + 1]Local variables accessed by offsetfrom FP:local variable 1: M[FP - 1]local variable 2: M[FP - 2]Computer Science 320Prof. David Walker-13-Stack Frame ExampleSuppose f(a1, a2) calls g(b1, b2, b3)Step 1:Frame Pointer(FP) ->Previous Framea2a1Frame for fStack Pointer(SP) ->GarbageStep 2:Frame Pointer(FP) ->Previous Framea2a1Frame for fStack Pointer(SP) ->Garbageb1b2b3Computer Science 320Prof. David Walker-14-Stack Frame ExampleSuppose f(a1, a2) calls g(b1, b2, b3)Step 3:Previous Framea2a1b1b2b3GarbageFrame for fStack Pointer(SP) ->Frame Pointer(FP) ->Frame for gOLD FP/Dynamic LinkDynamic link (AKA Control link) points to the activation record of the caller.¯Optional if size of caller activation record is known at compile time.¯Used to restore stack pointer during return sequence.Computer Science 320Prof. David Walker-15-Stack Frame ExampleSuppose f(a1, a2) calls g(b1, b2, b3), and returns.Step 4Frame Pointer(FP) ->Previous Framea2a1Frame for fStack Pointer(SP) ->Garbageb1b2b3Step 5Frame Pointer(FP) ->Previous Framea2a1Frame for fGarbageb1Stack Pointer(SP) ->b2/Garbageb3/GarbageComputer Science 320Prof. David Walker-16-Parameter Passingf(a½,a¾, ..., a)¯Registers are faster than memory.¯Compiler should keep values in register whenever possible.¯Modern calling convention: rather than placing a½,a¾, ..., aon stack frame, put a½,..., a( ) in registers r ,r ·½,r ·¾,r ·¿and a·½,a·¾,a·¾, ..., a.¯If r ,r ·½,r ·¾,r ·¿are needed for other purposes, callee function must save incom-ing argument(s) in stack frame.¯C language allows programmer to take address of formal parameter and guaranteesthat formals are located at consecutive memory addresses.– If address argument has address taken, then it must be written into stack frame.– Saving it in “saved registers” area of stack won’t make it consecutive with mem-ory resident arguments.– Space must be allocated even if parameters


View Full Document

Princeton COS 320 - Activation Record

Download Activation Record
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Activation Record and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Activation Record 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?