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 s stack frame or activation record Computer Science 320 Prof David Walker 1 The Stack The 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 stack pointer Push and pop entire activation records Computer Science 320 Prof David Walker 2 Example Consider let function g x int let var y 10 in x y end function h y int int y g y in h 4 end Computer Science 320 Prof David Walker 3 Example Step 1 h 4 called Chunk of memory allocated on the stack in order to hold local variables of h The activation record or stack frame of h is pushed onto the stack Stack Frame for h y 4 Step 2 g 4 called Activation record for g allocated pushed on stack Stack Frame y 4 for h Stack x 4 Frame y 10 for g Computer Science 320 Prof David Walker 4 Example Step 3 g 4 returns with value 14 Activation record for g deallocated popped from stack Stack Frame y 4 for h rv 14 Step 4 h 4 returns with value 18 Activation record for h deallocated popped from stack Stack now empty Computer Science 320 Prof David Walker 5 Recursive Example Can have multiple stack frames for same function different invocations on stack at any given time due to recursion Consider let function fact n int int if n 0 then 1 else n fact n 1 in fact 3 end Step 1 Record for fact 3 pushed on stack Stack Frame n 3 for fact Computer Science 320 Prof David Walker 6 Recursive Example Step 2 Record for fact 2 pushed on stack Stack Frame n 3 for fact Stack Frame n 2 for fact Step 3 Record for fact 1 pushed on stack Stack Frame n 3 for fact Stack Frame n 2 for fact Stack Frame n 1 for fact Computer Science 320 Prof David Walker 7 Recursive Example Step 4 Record for fact 0 pushed on stack Stack Frame n 3 for fact Stack Frame n 2 for fact Stack Frame n 1 for fact Stack Frame n 0 for fact Step 5 Step 6 Step 7 Step 8 Record for fact 0 popped off stack 1 returned Record for fact 1 popped off stack 1 returned Record for fact 2 popped off stack 2 returned Record for fact 3 popped off stack 3 returned Stack now empty Computer Science 320 Prof David Walker 8 Functional Languages In some functional languages such as ML Scheme local variables cannot be stored on stack fun f x let fun g y x y in g end Consider val z f 4 val w z 5 Assume variables are stack allocated Computer Science 320 Prof David Walker 9 Functional Language Example Step 1 f 4 called Frame for f 4 pushed g returned frame for f 4 popped Stack Frame for f x 4 Stack Frame for z y 5 Stack empty Step 3 z 5 called Memory location containing x has been deallocated Computer Science 320 Prof David Walker 10 Functional Languages Combination of nested functions and functions returned as results higher order functions Requires local variables to remain in existence even after enclosing function has been returned Activation records must be allocated on heap not stack Concentrate on languages which use stack Computer Science 320 Prof David Walker 11 Stack Frame Organization How is data organized in stack frame Compiler can use any layout scheme that is convenient Microprocessor manufactures specify standard layout schemes used by all compilers Sometimes referred to as Calling Conventions If all compilers use the same calling conventions then functions compiled with one compiler can call functions compiled with another Essential for interaction with OS libraries Computer Science 320 Prof David Walker 12 Typical Stack Frame Higher Addresses Frame Pointer FP arg n arg 2 arg 1 local var 1 local var 2 local var m Return Address Previous Frame Callee can access arguments by offset from FP argument 1 M FP argument 2 M FP 1 Current Frame Local variables accessed by offset from FP Temporaries Saved Registers local variable 1 M FP 1 local variable 2 M FP 2 Stack Pointer SP Garbage Lower Addresses Computer Science 320 Prof David Walker 13 Stack Frame Example Suppose f a1 a2 calls g b1 b2 b3 Step 1 Previous Frame Frame Pointer FP a2 a1 Frame for f Stack Pointer SP Garbage Step 2 Previous Frame Frame Pointer FP a2 a1 Frame for f Stack Pointer SP Computer Science 320 Prof David Walker b1 b2 b3 Garbage 14 Stack Frame Example Suppose f a1 a2 calls g b1 b2 b3 Step 3 Previous Frame a2 a1 Frame for f Frame Pointer FP b1 b2 b3 OLD FP Dynamic Link Frame for g Stack Pointer SP Garbage Dynamic 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 320 Prof David Walker 15 Stack Frame Example Suppose f a1 a2 calls g b1 b2 b3 and returns Step 4 Previous Frame Frame Pointer FP a2 a1 Frame for f Stack Pointer SP b1 b2 b3 Garbage Step 5 Previous Frame Frame Pointer FP a2 a1 Frame for f Stack Pointer SP Computer Science 320 Prof David Walker b1 b2 Garbage b3 Garbage Garbage 16 Parameter Passing f 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 incoming argument s in stack frame C language allows programmer to take address of formal parameter and guarantees that 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 memory resident arguments Space must be allocated even if parameters are passed through register Computer Science 320 Prof David Walker 17 Parameter Passing If register argument has address taken callee writes register into corresponding space Frame Pointer FP a n a k 1 space for a k Stack