Can someone provide a visualization or detailed flow of the stack frame in this Assembly MIPS code block?

Question

addi  $sp, $sp, -32    # stack frame is 32 bytes long
sw    $ra, 20($sp)     # save return address
sw    $fp, 16($sp)     # save frame pointer
addi  $fp, $sp, 28     # set up frame pointer
sw    $a0, 0($fp)      # save argument (n)  

I'm a bit lost on how a stack frame works and I'm still fresh on understanding the process. Can someone go line by line to explain what's happening? If possible, can you also provide a visualization of the actual stack frame and where the frame pointer and stack pointer are located and how it moves?

Answer 1

To visualize, first we need to establish the direction of visualization, usually whether up or down.  Both are correct, but one may be harder to read than the other.

In any case, the stack "grows" towards lower numbered memory addresses, and shrinks towards higher numbered memory addresses.  The memory is basically always there (and doesn't move!) — the stack pointer register tells what portion of the memory is occupied/in-use, vs. unoccupied/available/free; it simply delineates free/unused stack memory from occupied/used stack memory.

For the picture with the stack growing visually "downwards":

             +------------+
0x7ffff000   |            |  <-- $sp+4   second word of occupied stack space
             +------------+
0x7fffeffc   |            |  <-- $sp     first word of occupied stack space
             +------------+
0x7fffeff8   |            |  <-- $sp-4   first word of unoccupied stack space
             +------------+ 

For the visualization with the stack growing "upwards".

             +------------+
0x7fffeff8   |            |  <-- $sp-4   first word of unoccupied stack space
             +------------+
0x7fffeffc   |            |  <-- $sp     first word of occupied stack space
             +------------+
0x7ffff000   |            |  <-- $sp+4   second word of occupied stack space
             +------------+ 

Most people find the stack growing downwards easier to understand, but it is confusing if you think of the stack frame as an object/record, because it is visually easier to see an object laid out forwards (i.e. with higher addresses later).

As an alternative we can use left/right (here lower addresses to the left, and higher to the right, the stack "grows" leftwards):

  0x7ffffeff8   0x7ffffeffc   0x7fffff000
+-------------+-------------+-------------+ 
|             |             |             |
+-------------+-------------+-------------+
 first free      first used   second used
    ^                ^            ^
    |                |            |
  $sp-4             $sp          $sp+4

I'm using the term first used/occupied to refer to the "top" of the stack.

Next, there is a single instruction that allocates stack space: addiu $sp,$sp,-32.  This instruction simply adds to the stack pointer, to compute the new location of the top of the stack.  I have used addiu because pointer arithmetic should be done using unsigned arithmetic.  (Using addi will cause an unwanted overflow trap if the stack grows past a certain point.)  -32 is negative, so it is growing the stack — enlarging the in-use portion of the stack, simply by moving the delineator, $sp.  -32 is a byte count, so in terms of words, this is 8 words (4 bytes per word on a 32-bit machine).

  0x7ffffefdc   0x7ffffefe0   0x7ffffefe4   0x7ffffefe8   0x7ffffefec   0x7ffffeff0   0x7ffffeff4   0x7ffffeff8   0x7ffffeffc   0x7fffff000
+-------------+-------------+-------------+-------------+-------------+-------------+-------------+-------------+-------------+-------------+ 
|             |             |             |             |             |             |             |             |             |             |
+-------------+-------------+-------------+-------------+-------------+-------------+-------------+-------------+-------------+-------------+ 
 <------------------ newly allocated, uninitialized -----------------------------------------------------------> <--- old previously in use --->
       ^                                                                                                               ^
       |                                                                                                               |
      $sp                                                                                                           old $sp

After this, the stack pointer doesn't move, so we can simply annotate the newly allocated storage:

      sp+0          sp+4          sp+8          sp+12        sp+16        sp+20           sp+24        sp+28         sp+32        sp+36
  0x7ffffefdc   0x7ffffefe0   0x7ffffefe4   0x7ffffefe8   0x7ffffefec   0x7ffffeff0   0x7ffffeff4   0x7ffffeff8   0x7ffffeffc   0x7fffff000
+-------------+-------------+-------------+-------------+-------------+-------------+-------------+-------------+-------------+-------------+ 
|             |             |             |             |   old $fp   |     $ra     |             |     $a0     |             |             |
+-------------+-------------+-------------+-------------+-------------+-------------+-------------+-------------+-------------+-------------+ 
 <------------------ newly allocated --------------------------------------------------------------------------> <--- old previously in use --->
       ^                                                                                                 ^              ^
       |                                                                                                 |              |
      $sp                                                                                               $fp          old $sp

That's all there is to it.  The stack is a section of memory; the value held in the stack pointer register indicates where the top of stack is, which is also the delineation between unused/free/available stack memory and in-use/already-allocated stack memory.  The stack pointer register changes in value to grow/shrink the stack (the memory doesn't move).  Any function that wants some stack space allocates by moving the stack pointer, and subsequently using $sp relative addressing.  It doesn't know the actual addresses of the stack in advance, but it knows it can use the $sp register to refer to the top of stack, and that it can compute the address of a local variable using $sp.

Thus, it doesn't matter where the stack pointer actually is, and, this allows main to call A and also main to call B and B to call A — in this scenario A is called first with only main on the stack and later with both main and B on the stack.  Since A only uses $sp relative addressing, the actual addresses it uses for its frame don't directly matter.  This also allows A, for example, to be recursive in that it can have multiple activations (stack frames on the stack).

Your snippet also establishes a frame pointer $fp, which is generally unnecessary but sometimes done anyway.  On MIPS, the stack usage is flattened: all the stack space needed for a function is generally allocated in one instruction at the beginning (called prologue).  Because of this flattening, a frame pointer is generally unnecessary.  (On x86, however, the stack pointer can be often moving, e.g. in calling another function with pushes for parameter passing, and later with pops.  Because the stack pointer is moving during execution of the body of the function, a frame pointer can be helpful, as it doesn't move during function execution.)

Before setting up the frame pointer, it saves the old value of the frame pointer into a memory location (one of the newly allocated words in the stack frame).

The frame pointer is initialized via pointer arithmetic — here to point to the highest address of the newly allocated stack space.  (The pointer arithmetic should be done with addiu instead of addi.)

Past this code fragment, the function's code can use either $sp relative loads and stores (using offset values 0..28) or use $fp relative loads and stores (using offset values 0..-28), to access the newly allocated frame memory.  Using the proper offset, we can reach the same memory location(s) with either $sp or $fp, so for example, 20($sp) is the same address as -8($fp).