21

Currently I'm studying for my computer organization midterm, and I'm trying to fully understand the stack pointer and the stack. I know these following facts that surround the concept:

  • It follows the first in last out principle

  • And adding something to the stack takes a two step process:

    addi $sp, $sp, -4
sw $s0, 0($sp)

What I think is stopping me from fully understanding is that I can't come up with a relevant, self apparent situation where I would need and/or want to keep track of data with a stack pointer.

Could someone elaborate on the concept as a whole and give me some useful code examples?

Connor Black
  • 6,921
  • 12
  • 39
  • 70
  • 2
    You should use unsigned add/sub for addresses, or you're risking an exception/trap if there's an overflow (crossing the boundary between 0x7FFFFFFF and 0x80000000). – Alexey Frunze Feb 26 '13 at 23:23
  • In practice yes, but for the purposes of the test I don't think he's requiring us to understand that subtlety. – Connor Black Feb 27 '13 at 00:59

2 Answers2

41

An important use of stack is nesting subroutine calls.

Each subroutine may have a set of variables local to that subroutine. These variables can be conveniently stored on a stack in a stack frame. Some calling conventions pass arguments on the stack as well.

Using subroutines also means you have to keep track of the caller, that is the return address. Some architectures have a dedicated stack for this purpose, while others implicitly use the "normal" stack. MIPS by default only uses a register, but in non-leaf functions (ie. functions that call other functions) that return address is overwritten. Hence you have to save the original value, typically on the stack among your local variables. The calling conventions may also declare that some register values must be preserved across function calls, you can similarly save and restore them using the stack.

Suppose you have this C fragment:

extern void foo();
extern int bar();
int baz()
{
    int x = bar();
    foo();
    return x;
}

MIPS assembly may then look like:

addiu $sp, $sp, -8  # allocate 2 words on the stack
sw $ra, 4($sp)      # save $ra in the upper one
jal bar             # this overwrites $ra
sw $v0, ($sp)       # save returned value (x)
jal foo             # this overwrites $ra and possibly $v0
lw $v0, ($sp)       # reload x so we can return it
lw $ra, 4($sp)      # reload $ra so we can return to caller
addiu $sp, $sp, 8   # restore $sp, freeing the allocated space
jr $ra              # return
Jester
  • 56,577
  • 4
  • 81
  • 125
8

The MIPS calling convention requires first four function parameters to be in registers a0 through a3 and the rest, if there are more, on the stack. What's more, it also requires the function caller to allocate four slots on the stack for the first four parameters, despite those being passed in the registers.

So, if you want to access parameter five (and further parameters), you need to use sp. If the function in turn calls other functions and uses its parameters after the calls, it will need to store a0 through a3 in those four slots on the stack to avoid them being lost/overwritten. Again, you use sp to write these registers to the stack.

If your function has local variables and can't keep all of them in registers (like when it can't keep a0 through a3 when it calls other functions), it will have to use the on-stack space for those local variables, which again necessitates the use of sp.

For example, if you had this:

int tst5(int x1, int x2, int x3, int x4, int x5)
{
  return x1 + x2 + x3 + x4 + x5;
}

its disassembly would be something like:

tst5:
        lw      $2,16($sp) # r2 = x5; 4 slots are skipped
        addu    $4,$4,$5   # x1 += x2
        addu    $4,$4,$6   # x1 += x3
        addu    $4,$4,$7   # x1 += x4
        j       $31        # return
        addu    $2,$4,$2   # r2 += x1

See, sp is used to access x5.

And then if you have code something like this:

int binary(int a, int b)
{
  return a + b;
}

void stk(void)
{
  binary(binary(binary(1, 2), binary(3, 4)), binary(binary(5, 6), binary(7, 8)));
}

this is what it looks in disassembly after compilation:

binary:
        j       $31                     # return
        addu    $2,$4,$5                # r2 = a + b

stk:
        subu    $sp,$sp,32              # allocate space for local vars & 4 slots
        li      $4,0x00000001           # 1
        li      $5,0x00000002           # 2
        sw      $31,24($sp)             # store return address on stack
        sw      $17,20($sp)             # preserve r17 on stack
        jal     binary                  # call binary(1,2)
        sw      $16,16($sp)             # preserve r16 on stack

        li      $4,0x00000003           # 3
        li      $5,0x00000004           # 4
        jal     binary                  # call binary(3,4)
        move    $16,$2                  # r16 = binary(1,2)

        move    $4,$16                  # r4 = binary(1,2)
        jal     binary                  # call binary(binary(1,2), binary(3,4))
        move    $5,$2                   # r5 = binary(3,4)

        li      $4,0x00000005           # 5
        li      $5,0x00000006           # 6
        jal     binary                  # call binary(5,6)
        move    $17,$2                  # r17 = binary(binary(1,2), binary(3,4))

        li      $4,0x00000007           # 7
        li      $5,0x00000008           # 8
        jal     binary                  # call binary(7,8)
        move    $16,$2                  # r16 = binary(5,6)

        move    $4,$16                  # r4 = binary(5,6)
        jal     binary                  # call binary(binary(5,6), binary(7,8))
        move    $5,$2                   # r5 = binary(7,8)

        move    $4,$17                  # r4 = binary(binary(1,2), binary(3,4))
        jal     binary                  # call binary(binary(binary(1,2), binary(3,4)), binary(binary(5,6), binary(7,8)))
        move    $5,$2                   # r5 = binary(binary(5,6), binary(7,8))

        lw      $31,24($sp)             # restore return address from stack
        lw      $17,20($sp)             # restore r17 from stack
        lw      $16,16($sp)             # restore r16 from stack
        addu    $sp,$sp,32              # remove local vars and 4 slots
        j       $31                     # return
        nop

I hope I've annotated the code without making mistakes.

So, note that the compiler chooses to use r16 and r17 in the function but preserves them on the stack. Since the function calls another one, it also needs to preserve its return address on the stack instead of simply keeping it in r31.

PS Remember that all branch/jump instructions on MIPS effectively execute the immediately following instruction before actually transferring control to a new location. This might be confusing.

Alexey Frunze
  • 61,140
  • 12
  • 83
  • 180