Stack Frames
Stack Frame
Example
Let’s consider the following set of
functions in a file called try.c void foo(void)
{
void bar(111,222);
bar(int a, int b) }
{
int x, y; gcc -S -m32 try.c
x = 555;
y = a+b;
}
Code Generated
foo:
bar:
pushl %ebp
pushl %ebp
movl %esp, %ebp
movl %esp, %ebp
subl $8, %esp
subl $16, %esp
movl $222, 4(%esp)
movl $555, -4(%ebp)
movl $111, (%esp)
movl 12(%ebp), %eax
call bar
movl 8(%ebp), %edx
leave
addl %edx, %eax
ret
movl %eax, -8(%ebp)
leave
ret
Example Cont..
bar: # --------- start of the function bar()
pushl %ebp # save the incoming frame pointer
movl %esp, %ebp # set the frame pointer to the current top of stack
subl $16, %esp # increase the stack by 16 bytes (stacks grow down)
movl $555, -4(%ebp) # x=555 a is located at [ebp-4]
movl 12(%ebp), %eax # 12(%ebp) is [ebp+12], which is the second
parameter
movl 8(%ebp), %edx # 8(%ebp) is [ebo+8], which is the first parameter
addl %edx, %eax # add them
movl %eax, -8(%ebp) # store the result in y
leave #
ret #
Example Cont..
foo: # --------- start of the function foo()
pushl %ebp # save the current frame pointer
movl %esp, %ebp # set the frame pointer to the current top of the stack
subl $8, %esp # increase the stack by 8 bytes (stacks grow down)
movl $222, 4(%esp) # this is effectively pushing 222 on the stack
movl $111, (%esp) # this is effectively pushing 111 on the stack
call bar # call = push the instruction pointer on the stack and branch to foo
leave # done
ret #
Figure 1. Before call to bar
Figure 2. At entry to bar
Figure 3. In bar
Figure 4. In bar
Stack-based allocation of space for subroutines
Ø B has called itself once, recursively, before
calling C.
Ø If D returns and C calls E, E’s frame
(activation record) will occupy the same
space previously used for D’s frame.
Ø At any given time, the stack pointer (sp)
register points to the first unused location on
the stack (or the last used location on some
machines), and the frame pointer (fp)
register points to a known location within the
frame of the current subroutine.
Ø The relative order of fields within a frame
may vary from machine to machine and
compiler to compiler.
Subroutine Nesting
• In a language with nested subroutines and static scoping.
• Pascal, Ada, list, Scheme
• Static chain is used to locate objects.
• Each stack frame contains a reference to the frame of the lexically
surrounding subroutine, called Static Link.
• Dynamic link: saved value of fp for return.
• The static and dynamic links may or may not be the same, depending on
whether the current routine was called by its lexically surrounding routine, or
by some other routine nested in that surrounding routine.
Nesting of Subroutines
Ø Within B, C, and D, all
five routines are visible.
Ø Within A and E, routines
A, B, and E are visible,
but C and D are not.
Ø Given the calling
sequence A, E, B, D, C,
in that order, frames will
be allocated on the stack
as shown at right, with
the indicated static and
dynamic links.
Static Scoping For Functions
Static Scoping For Functions Cont..
Static Scoping For Functions Cont..
Static Scoping for Functions Cont..
Calling Sequences
Ømaintenance of stack is responsibility of calling sequence
Øcode executed by caller immediately before and after a
subroutine call
Øsubroutine prologue and epilogue
Øcode performed at beginning/end of subroutine
Øsometimes calling sequence includes all three
Calling Sequences
Calling Sequences
Ø The caller
1. Saves any caller-saves registers whose values will be needed after the call
2. Computes the values of arguments and moves them into the stack or
registers
3. Computes the static link (if this is a language with nested subroutines), and
passes it as an extra, hidden argument
4. Uses a special subroutine call instruction to jump to the subroutine,
simultaneously passing the return address on the stack or in a register
Calling Sequences
Ø In its prologue, the callee
1. allocates a frame by subtracting an appropriate constant
from the sp
2. saves the old frame pointer into the stack, and assigns it
an appropriate new value
3. saves any callee-saves registers that may be overwritten
by the current routine (including the static link and return
address, if they were passed in registers)
Calling Sequences
After the subroutine has completed, the epilogue
1. moves the return value (if any) into a register or a
reserved location in the stack
2. restores callee-saves registers if needed
3. restores the fp and the sp
4. jumps back to the return address
Calling Sequences
Finally, the caller
1. moves the return value to wherever it is needed
2. restores caller-saves registers if needed
References
• [Link]