CDA 3101: 2008S Stack Frame Convention

Summer, 2008

Guiding principles

1. Not all procedures need a Stack Frame.
2. Procedures reference local data and excess arguments relative to the FP (Frame Pointer) only.
3. Caller manages the push/pop-ing of excess arguments.
4. Stack space used by the procedure is deallocated with the FP.
5. Good programming style is more important than efficiency.

The official CDA3101 Stack Frame convention

                                |               |       High Mem
                                +===============+
                                |     excess    |
  Callee's FP & Caller's SP ->  |   arguments   |
                                +---------------+
                                |  caller's FP  |
                                +---------------+
                                |               |
                                |   callee's    |
                                |     local     |
                                |    storage    |
                Callee's SP ->  |               |
                                +===============+
                                |               |       Low Mem

1. Caller: saves caller saved registers in ITS stack frame
2. Caller: pushes excess arguments on stack
3. Caller: call the callee (jal callee_name)
4. Callee: allocates the stack frame:

           Mem[SP-4] := Caller FP
           FP := SP
           SP := SP - ( LOCAL_STORE_SIZE + 4 )
      

5. Callee: does its work, saving callee saved registers in ITS stack frame as needed
6. Callee: restores callee saved registers preserved in its stack frame when the register is no longer needed by the callee.
7. Callee: deallocates the stack frame:

           SP := FP
           FP := Mem[SP-4]
      

8. Callee: return to caller (jr $ra)
9. Caller: Caller pops excess arguments (when appropriate)
10. Caller: Caller restores registers preserved in its stack frame (when appropriate)

Registers

The following are caller saved registers -- i.e., the callee is allowed to freely use (and therefore trash) the contents of these registers, so if the caller cares about the values stored therein, it must save them before making a procedure call:

$v0, $v1

$a0 - $a3

$t0 - $t9

$ra

Note: when a procedure call returns, the caller must assume that the caller saved registers have been trashed by the callee!

The following are callee saved registers -- i.e., the callee guarantees that it will return these registers in the condition it received them; thus if it wants to use one of these registers, it must preserve the contents before change it, and restore the original contents before returning to the caller:

$fp -- and therefore indirectly $sp

$s0 - $s7

Now for an example:

void main(void)
{
 int SUM = sum( 3 );
}

int sum( int N )
{
   int SUM = 0;

   if ( N != 0 )
        SUM = sum( N-1 );

   SUM = SUM + N;

   return SUM;
}

Callee's FP ->  |               |       High Mem
                +===============+
                |  caller's FP  |       FP-4
                +---------------+
                | caller's $s0  |       FP-8
                +---------------+
         SP ->  |  ret address  |       FP-12
                +===============+
                |               |       Low Mem

# CDA3101 - Fall 1999
# Example program
#
# By Dave Small
#
# Description:
#
#       This program illustrates the use application of the
#       official CDA3101 2000C stack-frame convention.
        
#------------------------------------------------------------------
# The text segment
#------------------------------------------------------------------
        
        .text
        .globl  main

        #----------------------------------------------------------
        # main()
        #
        # Description:
        #
        #       Computes the sum of the integers from 0 to 3.
        #
        # Algorithm:
        #
        #       void main( void )
        #       {
        #           int SUM = sum( 3 );
        #       }
        #
        # Input:
        #
        #       none
        #
        # Output:
        #
        #       sum is left in register $s0
        #
        # Register usage map:
        #
        #       $a0 = pass ARG1 to called functions
        #       $t0 = sum of the integers from 0 to 3
        #       $v0 = receive return value from called functions
        #
        # Stack-frame structure:
        #
        #       none required
        #
        
main:   addi    $a0, $0, 3      # ARG1 = 3
        jal     sum             # sum( 3 )
ret0:   move    $t0, $v0        # SUM = sum( 3 )

        # terminate execution
                
        li      $v0,  10        # return control...
        syscall                 # to SPIM

        #----------------------------------------------------------
        # sum()
        #
        # Description:
        #
        #       Recusively compute the sum of all the integers
        #       between 0 and N
        #
        # Algorithm:
        #
        #       int sum( int N )
        #       {
        #          int SUM = 0;
        #       
        #          if ( N != 0 )
        #               SUM = sum( N-1 );
        #       
        #          SUM = SUM + N;
        #       
        #          return SUM;
        #       }
        #
        # Assumptions:
        #
        #       The result will fit in a 32-bit register.
        #
        # Input:
        #
        #       N - passed in via register $a0
        #       
        # Output:
        #
        #       sum - passed out via register $v0
        #
        # Register usage map:
        #
        #       $a0 = ARG1 function argument
        #       $s0 = N
        #       $t0 = SUM
        #       $v0 = return value
        #
        # Stack-frame structure:
        #
        #       Callee's FP ->  |               |       High Mem
        #                       +===============+
        #                       |  caller's FP  |       FP-4
        #                       +---------------+
        #                       | caller's $s0  |       FP-8
        #                       +---------------+
        #                SP ->  |  ret address  |       FP-12
        #                       +===============+
        #                       |               |       Low Mem
        #
        
sum:    # setup frame and preserve callee saved registers
        
        sw      $fp, -4($sp)    # preserve caller's FP
        move    $fp, $sp        # set FP for new frame
        addi    $sp, $sp, -12   # allocate local storage on stack
        sw      $s0, -8($fp)    # preserve caller's $s0

        # check for base case

        move    $s0, $a0        # N = ARG1
        move    $t0, $0         # SUM = 0;
        beq     $s0, $0, here   # skip ahead if NOT ( N != 0 )

        # prepare for recursive call (preserve caller saved regs)
        
        sw      $ra, -12($fp)   #   preserve return address

        # recur
        
        addi    $a0, $s0, -1    #   ARG1 = N-1
        jal     sum             #   sum( N-1 )
ret1:   move    $t0, $v0        #   SUM = sum( N-1 )
        
        # recover from recursive call (restore caller saved regs)
        
        lw      $ra, -12($fp)   #   restore return address

        # finish computation

here:   add     $s0, $t0, $s0   # SUM = SUM + N
        move    $v0, $s0        # set return value to SUM

        # restore callee saved registers, destroy frame & return to caller
        lw      $s0, -8($fp)    # restore caller's $s0
        move    $sp, $fp        # deallocate local storage
        lw      $fp, -4($sp)    # restore caller's FP
        
        jr      $ra             # return SUM;