A region that grows down
The
starts near the top of the data memory and grows toward lower addresses.
$sp, the stack pointer, always holds the lowest address in use. On your
test machine it starts at 0x10003FF0, just under the doors; crt0 sets it
(§2.2).
The rules, all of them:
| to | write | effect on $sp |
|---|---|---|
| claim N bytes (“push”) | addiu $sp,$sp,-N | goes down by N |
| save a register | sw reg,off($sp) | unchanged |
| restore a register | lw reg,off($sp) | unchanged |
| release N bytes (“pop”) | addiu $sp,$sp,N | goes up by N |
N is a multiple of 8, by the o32 convention. There is no push and no
pop: one addiu opens a whole frame, and plain stores fill it.
Watch two frames
The runner claims a frame, saves two registers, claims a second frame inside
it, and then unwinds both. The stack pane follows $sp.
Two nested frames: the stack grows down, then comes back up
Where does a function keep the registers it must not destroy, and how does $sp move?
program (address · word · instruction)
| PC → | 0xbfc00000 | 0x3c1d1000 | _start:lui $sp,0x1000 |
| 0xbfc00004 | 0x27bd3ff0 | addiu $sp,$sp,16368 | |
| 0xbfc00008 | 0x24100007 | li $s0,7 | |
| 0xbfc0000c | 0x241f0100 | li $ra,256 | |
| 0xbfc00010 | 0x27bdfff8 | addiu $sp,$sp,-8 | |
| 0xbfc00014 | 0xafbf0004 | sw $ra,4($sp) | |
| 0xbfc00018 | 0xafb00000 | sw $s0,0($sp) | |
| 0xbfc0001c | 0x24100009 | li $s0,9 | |
| 0xbfc00020 | 0x27bdfff8 | addiu $sp,$sp,-8 | |
| 0xbfc00024 | 0xafb00000 | sw $s0,0($sp) | |
| 0xbfc00028 | 0x8fb00000 | lw $s0,0($sp) | |
| 0xbfc0002c | 0x27bd0008 | addiu $sp,$sp,8 | |
| 0xbfc00030 | 0x8fb00000 | lw $s0,0($sp) | |
| 0xbfc00034 | 0x8fbf0004 | lw $ra,4($sp) | |
| 0xbfc00038 | 0x27bd0008 | addiu $sp,$sp,8 | |
| 0xbfc0003c | 0xafa00008 | sw $zero,8($sp) |
registers — read · written this tick
stack around $sp = 0x00000000 — higher addresses on top
console (what the doors printed)
▮tick 0 of 16
Nothing has run yet. The PC (program counter) points at the first instruction.
Every addiu $sp,$sp,-8 moves the PC chip's neighbour $sp DOWN by 8 and opens two new word slots below the old top. sw fills them; lw reads them back; addiu $sp,$sp,8 gives them up. At the end $sp is exactly where it started and $s0 and $ra have their old values.
What to notice
Each addiu $sp,$sp,-8 moves $sp down and two fresh words appear under
the old top. The second frame sits below the first. Unwinding is the mirror
image: lw, then addiu $sp,$sp,8. At the end $sp is back at
0x10003FF0, and $s0 and $ra have their old values.
Before reading on, decide:
Tick 12 is the first `addiu $sp,$sp,8`. What is $sp after it, and which frame is now on top?
The smallest real frame: print_char
A function’s slice of the stack is its
.
The code that builds it is the prologue; the code that removes it is the
epilogue. Here is print_char from hello.c at -O0, the smallest frame
in the program.
print_char: one C statement, and the frame GCC wraps around it at -O0
carolyne_ref/carolyne_io.h; hello_o0.dump bfc000b0–bfc000e8
1void print_char(char value)2{3 CAROLYNE_PUTCHAR = (unsigned char)value;4}bfc000b0addiu sp,sp,-8bfc000b4sw s8,4(sp)bfc000b8move s8,spbfc000bcmove v0,a0bfc000c0sb v0,8(s8)bfc000c4lbu v1,8(s8)bfc000c8lui v0,0x1000bfc000ccori v0,v0,0x3ff0bfc000d0sw v1,0(v0)bfc000d4nopbfc000d8move sp,s8bfc000dclw s8,4(sp)bfc000e0addiu sp,sp,8bfc000e4jr rabfc000e8nopClick any highlighted line to see it light up in the other listing, and read what it does.
What to notice
The epilogue is the prologue backwards: lw undoes sw, addiu +8 undoes
addiu -8. $ra is never saved, because print_char calls nothing. And
value is parked at 8(s8), above the frame, in space the caller set
aside: the o32 argument area.
main’s 32-byte frame
main calls other functions, so it must save $ra too. Its prologue at
bfc0018c is addiu sp,sp,-32, sw ra,28(sp), sw s8,24(sp), move s8,sp.
The frame, drawn from the top down:
offset from $sp | holds | who uses it |
|---|---|---|
| 28 | the saved $ra | restored before jr ra |
| 24 | the saved $s8 | restored before return |
| 16 | i, the loop counter | sw zero,16(s8), lw v0,16(s8) |
| 0 … 15 | the argument area | space for $a0–$a3 of every function main calls |
The bottom 16 bytes are the o32 rule: a caller always leaves room for the
callee to spill its four argument registers. print_char’s sb v0,8(s8)
wrote into exactly this area of its caller.
Go deeper: why stacks grow down, and what the argument area is for
Early machines put the program and its data at low addresses and let them
grow upward as the program allocated memory. The stack was placed at the top
and grown downward, so the two regions could share whatever was in between
without either knowing the other’s size. MIPS, C and every operating system
since inherited the habit. Your test machine has no heap, but the shape is the
same: data at 0x10000000, the stack from 0x10003FF0 downward.
The 16-byte argument area is a 1980s compromise. o32 passes the first four
arguments in $a0–$a3 for speed, but a function may need their addresses (a
& on a parameter) or run out of registers. So the caller reserves the stack
slots those four values would have used, and the callee may store them
there. print_char does exactly that at -O0 with sb v0,8(s8). At -O2 the
store disappears, but the space is still reserved.
Can you now explain it?
The stack is memory below $sp that grows toward lower addresses. A frame is claimed with addiu -N, filled with sw, emptied with lw and released with addiu +N. Every frame is a multiple of 8 and keeps 16 bytes at the bottom for its callees' arguments.
If you remember only three things
- $sp is the lowest address in use. Push subtracts, pop adds. The newest frame is the lowest one.
- No push instruction, no pop instruction. One addiu opens the frame; sw and lw at fixed offsets do the saving. The epilogue is the prologue in reverse.
- A frame has a shape. Saved $ra and $s registers at the top, locals in the middle, 16 bytes of argument area at the bottom (o32).
Now try to explain this one yourself: print_char saves $s8 but not
$ra, while main saves both. Using §2.2’s table, say why each function
saves exactly what it saves.
Go deeper: a model answer, once you have tried
$ra is overwritten by jal. main calls print_str and print_int, so
its own return address would be destroyed by the first call; it must save
$ra first. print_char calls nothing, so $ra still holds the way back at
jr ra, and saving it would be wasted work. $s8 is callee-saved: any
function that changes it must put it back. Both functions use $s8 as their
frame pointer at -O0, so both save the caller’s value and restore it. At -O2
neither uses $s8, and print_char needs no frame at all.
Check your understanding
0/5 answered1.$sp starts at 0x10003FF0. After two `addiu sp,sp,-8`, where is it, and how big is the stack in use?
2.print_char begins `addiu sp,sp,-8` then `sw s8,4(sp)`. Where is the old s8 saved?
3.Why do MIPS functions use `addiu` once and then `sw` at offsets, instead of a push instruction?
4.'The stack grows downward' means which of these?
5.main's frame is 32 bytes and print_char's is 8, although print_char saves only one register. Why 8 and not 4?