CS61C Spring 2007

Project 02
sprintf for MIPS

Background

MIPS Stack Managing

By now, you should know how to manage the stack when writing procedures in MIPS. Let's assume you have a function light_blue, which calls a function dark_blue. The very first thing that light_blue does is to allocate space in the stack for its variables (prolog). In Figure 1 (middle) we can see that it allocates space for 4 words. light_blue eventually calls dark_blue, which allocates space for its own variables. Figure 1 (right) shows that dark_blue has allocated space for 2 words.
Figure 1

MIPS Argument Passing

The MIPS procedure calling convention uses registers $a0-$a3 for passing arguments down to procedures. If there are more than four, the remaining arguments are passed on the stack. How is this mixed with the normal stack managing? Each argument gets one word of stack space. Suppose we are trying to write in MIPS assembler a program like this:

int dark_blue (int x, int y, int quux, int bar, int bay, int baz) {

int a;
...
a = y;
...
}

int light_blue () {
int c, d, e;
...
dark_blue (3, 4, 43, 62, 1, 0);
...
}

Procedure dark_blue has six integer arguments. The space for those arguments is allocated on the stack as part of the caller's (light_blue) stack frame. In other words, light_blue, not dark_blue, must allocate the space.

Figure 2 shows this stack management method. light_blue now allocates space in the stack for its variables and the arguments that it will use to call dark_blue. We can see in Figure 2 (middle) that it allocates space for 10 words: 4 for its own consumption (variables c, d, and e as well as the return address), and 6 for calling dark_blue.

light_blue eventually calls dark_blue, which allocates space for its own variables. Figure 2 (right) shows that dark_blue has allocated space for 2 words (one for the return address and one for 'a'). Note that dark_blue can access to the 6 arguments by accessing either the $a0-$a3 registers or the beginning of the stack reserved by its caller process (light_blue).
Figure 2

The 2 spilled arguments (patterned light-blue stack) are located at the lower addresses of light_blue's stack frame.

That is, light_blue will use 0($sp) to store the argument bay and 4($sp) to store the argument baz. Therefore, dark_blue will use 8($sp) to access to the argument bay, 12($sp) to access to the argument baz, and so on.  Of course, arguments such as x are in registers (in x's case, $a0).

Note that the first spilled argument is always at the caller's stack frame lowest address, and the last spilled argument at the highest address. You have to be consistent about this so that dark_blue knows which argument is which.

light_blue:
# prolog
addi $sp, $sp, -16 # allocate stack space for 4 words:
# $ra, c, d, and e
sw $ra, 12($sp) # save $ra
# use 0($sp) to save c ($t0) when needed
# use 4($sp) to save d ($t1) when needed
# use 8($sp) to save e ($t2) when needed

# body

...

addi $t0, $0, 3 # assume this holds the value of c
addi $t1, $0, 4 # assume this holds the value of d
addi $t2, $0, 5 # assume this holds the value of e

...

# this is the call to dark_blue
addi $sp, $sp, -8 # allocate stack space for 2 words (patterned
# light-blue): the args bay, baz
sw $t0, 8($sp) # save c before calling dark_blue
sw $t1, 12($sp) # save d before calling dark_blue
sw $t2, 16($sp) # save e before calling dark_blue

add $a0, $0, $t0 # arg x = c
add $a1, $0, $t1 # arg y = d
addi $a2, $0, 43 # arg quux = 43
addi $a3, $0, 62 # bar = 62
addi $t0, $0, 1 # bay = 1, but no more registers
sw $t0, 0($sp) # so pass on the stack
add $t0, $0, $0 # baz = 0, but no more registers
sw $t0, 4($sp) # so pass on the stack
jal dark_blue
addi $sp, $sp, 8 # restore stack space used for calling dark_blue

...

# epilog
lw $ra, 12($sp) # reload return address
addi $sp, $sp, 16 # restore stack space
jr $ra # return to caller


...


dark_blue:
# prolog
addi $sp, $sp, -8 # allocate stack space for 2 words:
# $ra, a
sw $ra, 4($sp) # save $ra
# use 0($sp) to save a when needed

# body

...

add $t0, $0, $a1 # get argument y
lw $t1, 12($sp) # *** (see below)
# 8 (dark_blue's frame) + 16 = 24 up on stack
# fetched argument baz
...

# epilog
lw $ra, 4($sp) # reload return address
addi $sp, $sp, 8 # restore stack space
jr $ra # return to caller

The instruction indicated by "***" is the key to understanding the stack method of argument passing. Procedure dark_blue is referring to a word of stack memory that is from the caller's stack frame. Its own frame includes only the two words 0($sp) and 4($sp).