CP216: Lab 06 - Spring 2025 - Stack Frames

The CPUlator: https://cpulator.01xz.net/?sys=arm-de1soc.

Stack Frame

In the Subroutines lab we learned how to call a subroutine, how to pass parameters to a subroutine, how to return a value in a register, and how to preserve registers on a stack.

These techniques are sufficient for relatively simple subroutines, but what if we require more parameters, or we need to pass parameters by reference and alter them, or we need to use local variables beyond the registers available?

A stack frame is memory on the stack that is used to pass parameters to a subroutine, and to set aside memory for local variables within that subroutine. The stack frame makes use of three registers to perform its duties:

• the stack pointer (sp), which contains the address of the current top of the stack.
• the frame pointer (fp), which keeps track of location in the stack between the parameters and the local variables / local register saves.
• the link register (lr), which keeps track of the program line to execute when the subroutine finishes.

The various calls at the beginning and end of the subroutine definition are called the stack frame prologue and the stack frame epilogue.

The Prologue

1. Push the frame pointer (fp) and link register (lr) onto the stack. The frame pointer is being preserved. The link register is set by the Branch Link (bl) instruction and contains the address of the instruction immediately following the subroutine call.
2. Save the current stack top (sp) to the frame pointer (fp).
3. Allocate local variable storage space on the stack.
4. Push registers to preserve onto the stack.

The Epilogue

1. Pop preserved registers from the stack.
2. Deallocate local variable storage space from the stack.
3. Pop the frame pointer (fp) and program counter (pc) from the stack. The program counter now contains the value stored in the link register when it was pushed. Execution of the calling program resumes at the line after the subroutine call.

At the end of this, the state of memory, except for returned values in r0, or updated parameter values, should be the same as it was before the subroutine was called.

Memory set aside on the stack is local to the subroutine because when the stack frame is collapsed after the subroutine is done, all reference to the memory is removed. (The temporary values may still be there, as the stack frame does not 'clean up' or zero-out the memory used in the stack, but those values can be ignored, and will be overwritten by other uses of the stack.)

Local variables are particularly useful in complex subroutines that require a large amount of memory (for example, using 64 bit numbers - beyond the scope of this lab), or when a large number of variables are necessary and there are insufficient registers available to handle this number. (Subroutines this complex are also beyond the scope of this lab.)

The following subroutine swap illustrates the use of a stack frame with local variables. The subroutine takes the addresses of two memory locations as parameters and swaps their contents. Its equivalent function signature in C is:
void swap(*x, *y)
(The entire program is available at swap.s.)

        
//-------------------------------------------------------
swap:
/*
-------------------------------------------------------
swaps location of two values in memory.
Equivalent of: swap(*x, *y)
-------------------------------------------------------
Parameters:
  x - address of first value
  y - address of second value
Local variable
  temp (4 bytes on stack)
Uses:
  r0 - address of x
  r1 - address of y
  r2 - value to swap
-------------------------------------------------------
*/
stmfd   sp!, {fp}       // push frame pointer
mov     fp, sp          // save current stack top to frame pointer
sub     sp, sp, #4      // set aside space for local variable temp
stmfd   sp!, {r0-r2}    // preserve other registers

ldr     r0, [fp, #4]    // get address of x
ldr     r1, [fp, #8]    // get address of y

ldr     r2, [r0]        // get value at x
str     r2, [fp, #-4]   // copy value of x to temp

ldr     r2, [r1]        // get value at y
str     r2, [r0]        // store value of y in x

ldr     r2, [fp, #-4]   // get temp
str     r2, [r1]        // store value of temp in y

ldmfd   sp!, {r0-r2}    // pop preserved registers
add     sp, sp, #4      // remove local storage
ldmfd   sp!, {fp}       // pop frame pointer
bx      lr              // return from subroutine

      

As this code demonstrates, we can't totally get rid of our reliance on registers - since we cannot move data directly from one memory location to another memory location, we must use registers as intermediates - but we can reduce the number of registers used. In the code above, r2 is the only register used to hold the values to swap. The 4 bytes set aside on the stack for 'temp' are used to store one of the two values temporarily.

The call to swap in C is:

    
  int x = 5;
  int y = 9;
  swap (&x, &y);  // Pass parameters by reference

The &a syntax in C merely means pass the memory address of the variable a rather than the value stored in a to the subroutine.

The assembler call to swap is:

    
ldr    r1, =y
stmfd  sp!, {r1}     // Push address of y
ldr    r1, =x
stmfd  sp!, {r1}     // Push address of x
bl     swap          // Call subroutine

  

a and b are arbitrary labelled memory locations containing the values to swap.

Note: parameters must be pushed onto the stack in right-to-left order. For this subroutine the address for the second parameter (*y) is pushed first, and the address for the first parameter (*x) is pushed second. Thus the parameter values are stored on the stack in order from top (first) to bottom (last).

The subroutine prologue consists of:

    
stmfd   sp!, {fp}       // push frame pointer
mov     fp, sp          // save current stack top to frame pointer
sub     sp, sp, #4      // set aside space for local variable temp
stmfd   sp!, {r0-r2}    // preserve other registers

  

Note: when pushing multiple registers using {r0-r3} the register contents are pushed in right to left order, with r0 ending up at the top of the stack. Even if the order given in the instructions was {r3,r1,r0,r2}, the order on the stack would still be r0 down to r3. If you require the stack contents to be in a different order, you must issue separate stmfd instructions in the order you require values to be on the stack.

We have now created a stack frame that contains parameters, local variables, preserved registers, and an easy way to access all of them. The frame consists of the following parts:

The stack grows down - the diagram is 'upside-down' because the simulator stack shows lower stack addresses at the top, and higher stack addresses at the bottom. Pushing data onto the stack decreases the value of the address of the top of the stack.

The key to understanding the stack frame is the use of the frame pointer (fp). The frame pointer gives us access to both the parameters on the stack and the local variables on the stack with just an offset value. We do not need to know the actual address of either parameters or local variables, we just have to know how far from the frame pointer they are. We can now easily access the parameters pushed onto the stack as offsets from the value in the frame pointer register. The first four bytes at the frame pointer address are the preserved frame pointer value, the second four bytes are the preserved link register value, so the first parameter is four bytes below the frame pointer address ([fp, #4]), and the second eight bytes below the frame pointer address ([fp, #8]). If there were more parameters they would be further down the stack. By using the frame pointer, we don't care how many bytes are stored on the stack above that address - those bytes don't enter into our parameter location calculations.

Local variables are stored on the stack a minimum of four bytes above the frame pointer and are accessed with a negative offset. However, this particular subroutine does not use any local variables on the stack - that will be dealt with in a later lab.

We can now copy the swap address parameters into the subroutine's temporary registers and get the values stored at those addresses:

    
ldr     r0, [fp, #4]    // get address of x
ldr     r1, [fp, #8]    // get address of y

  

The actual swapping is done by copying the values to swap from memory into the local temp variable, and then back into the opposite memory locations. This is the equivalent of the C code:

    
void swap (int *x, int *y) {
  int temp = *x;
  *x = *y;
  *y = temp;
}

The assembler swap is:

    
ldr     r0, [fp, #4]    // get address of x
ldr     r1, [fp, #8]    // get address of y

ldr     r2, [r0]        // get value at x
str     r2, [fp, #-4]   // copy value of x to temp

ldr     r2, [r1]        // get value at y
str     r2, [r0]        // store value of y in x

ldr     r2, [fp, #-4]   // get temp
str     r2, [r1]        // store value of temp in y

Because of the way that the stack frame is constructed, parameters are at a positive offset from the frame pointer fp (e.g. x is at +4 bytes, y is at +8 bytes), while the local variables are at a negative offset from the frame pointer (e.g. temp is at -4 bytes). This makes it very easy to distinguish parameters from local variables.

When the subroutine finishes it has to remove itself from the stack. This means copying all temporary register values stored on the stack back to the original registers, including the preserved frame pointer. The preserved link register is copied into the program counter rather than back to the link register because that value is the address of the code to be executed after the subroutine finishes. Local variable memory must be released. Thus the subroutine epilogue consists of:

    
ldmfd   sp!, {r0-r2}    // pop preserved registers
add     sp, sp, #4      // remove local storage
ldmfd   sp!, {fp}       // pop frame pointer
bx      lr              // return from subroutine

  

We're not quite finished. Upon returning to the main program the stack pointer still refers to the last parameter pushed on top of the stack, and that has to be cleaned up. The line:

    
bl    swap           // call subroutine
add   sp, sp, #8     // release parameter memory from stack

  

cleans up the stack by returning the address of the top of the stack to what it was before the parameter was pushed onto it. Note that we don't have to pop the parameterS, we merely have to reset the stack pointer. The value added to the stack pointer depends on the number of parameters originally pushed onto the stack. Since we pushed two 4-byte parameters we have to add eight bytes to return the stack pointer to its original value.

Note that if you look at the actual stack memory, it still contains the values pushed onto it - updating the stack pointer is not the same as cleaning up the stack contents. This is not an issue. The values in the stack memory area are just 'noise' and will be overwritten the next time values are pushed onto the stack.

The following dynamic diagram shows how the stack frame for this program is handled:

1. Complete the strncmp subroutine in l06_t01.s. The main program is complete, you must write the subroutine prologue and epilogue (i.e. the code that sets up the subroutine stack and extracts the parameters from the stack to the appropriate registers).

   ---

2. Complete the main program in l06_t02.s. Find the minimum and maximum values in a list, and save those two values in the addresses pointed to by the min and max parameters.

   ---

3. Complete both the main program and the subroutine in l06_t03.s. The subroutine logic is complete, you must write the code that pushes the parameters onto the stack, and the subroutine prologue and epilogue.

   ---

Zip your files together in zip file named login_l06.zip (using your Laurier login, of course) and submit that zip file to the MLS dropbox.