Skip to content
Contents

Stack frames and recursion: fib step by step

Section 6.3 8 min read

  • the -O0 frame of fib: 32 bytes, three saved registers
  • the argument area: n spilled above the frame
  • activation: one frame per call, even of the same function
  • recursion needs only the stack discipline

Checked against: MIPS o32 ABI: stack frame carolyne_ref/dumps/fib_o0.dump (bfc00270–bfc002ec, the whole fib) carolyne_ref/programs/fib.c (lines 35–39)

Before you start

  • §4.4: frames, prologue and epilogue
  • §6.2: why fib saves $s0

By the end, you can

  • Draw fib's frame with every offset labeled
  • Say which activations are alive at the deepest point of fib(3)
  • Follow two saved return addresses back out through two jr $ra
  • Explain why recursion needs no hardware support

fib’s frame, drawn

GCC gave fib a 32-byte frame at -O0. Its prologue (fib_o0.dump bfc00270) is addiu sp,sp,-32, sw ra,28(sp), sw s8,24(sp), sw s0,20(sp), move s8,sp, then sw a0,32(s8). Drawn from the top:

offset from $spholdswhy
32n, the argument, spilledabove the frame, in the caller’s argument area
28saved $rafib calls fib: the inner jal overwrites $ra
24saved $fp ($s8)callee-saved; this call uses it as its frame pointer
20saved $s0callee-saved; this call keeps fib(n−1) in it
16unusedpadding to a multiple of 8
0 … 12argument areareserved for the two fib calls this call makes

The spill at 32($fp) is the interesting line. $fp equals the new $sp. So 32($fp) is the old $sp, the first word of the caller’s . Every fib keeps its n in the frame of the fib that called it, and reserves the same 16 bytes at its own bottom for the fibs it calls.

The whole function

Here is every line of fib, with the C beside it. Click a C line.

fib, complete: fib.c and the 32 words of fib_o0.dump bfc00270–bfc002ec

carolyne_ref/programs/fib.c lines 35–39; carolyne_ref/dumps/fib_o0.dump

fib.c
1int fib(int n) {
2    if (n < 3)
3        return 1;
4    return fib(n - 1) + fib(n - 2);
5}
MIPS (-O0)
bfc00270addiu sp,sp,-32
bfc00274sw    ra,28(sp)
bfc00278sw    s8,24(sp)
bfc0027csw    s0,20(sp)
bfc00280move  s8,sp
bfc00284sw    a0,32(s8)
bfc00288lw    v0,32(s8)
bfc0028cslti  v0,v0,3
bfc00290beqz  v0,bfc002a4
bfc00294nop
bfc00298li    v0,1
bfc0029cb     bfc002d4
bfc002a0nop
bfc002a4lw    v0,32(s8)
bfc002a8addiu v0,v0,-1
bfc002acmove  a0,v0
bfc002b0jal   bfc00270 <fib>
bfc002b4nop
bfc002b8move  s0,v0
bfc002bclw    v0,32(s8)
bfc002c0addiu v0,v0,-2
bfc002c4move  a0,v0
bfc002c8jal   bfc00270 <fib>
bfc002ccnop
bfc002d0addu  v0,s0,v0
bfc002d4move  sp,s8
bfc002d8lw    ra,28(sp)
bfc002dclw    s8,24(sp)
bfc002e0lw    s0,20(sp)
bfc002e4addiu sp,sp,32
bfc002e8jr    ra
bfc002ecnop

Click any highlighted line to see it light up in the other listing, and read what it does.

What to notice

Two jal bfc00270 <fib> inside fib itself. Each one runs this same code again with a new frame 32 bytes lower, and a new n spilled at the new 32(s8). When the inner call’s jr ra comes back, this frame’s $s8 still points at this frame, so 32(s8) is still this call’s n.

Run fib(3)

The runner uses the exact -O0 shape with a small _start. The stack pane follows $sp. It pauses before the first jr $ra to ask where it goes.

fib(3) with the real -O0 frame: two activations at once, two saved $ra, then the unwinding

What is on the stack, exactly, while fib(3) runs?

program (address · word · instruction)

PC →0xbfc000000x3c191000_start:lui $t9,0x1000
0xbfc000040x37390ff0ori $t9,$t9,0xff0
0xbfc000080x3c1d1000lui $sp,0x1000
0xbfc0000c0x27bd0fe0addiu $sp,$sp,4064
0xbfc000100x24040003li $a0,3
0xbfc000140x0ff00009jal 0xbfc00024
0xbfc000180x00000000nop
0xbfc0001c0xaf220004sw $v0,4($t9)
0xbfc000200xaf200008sw $zero,8($t9)
0xbfc000240x27bdffe0fib:addiu $sp,$sp,-32
0xbfc000280xafbf001csw $ra,28($sp)
0xbfc0002c0xafbe0018sw $fp,24($sp)
0xbfc000300xafb00014sw $s0,20($sp)
0xbfc000340x03a0f025move $fp,$sp
0xbfc000380xafc40020sw $a0,32($fp)
0xbfc0003c0x8fc20020lw $v0,32($fp)
0xbfc000400x28420003slti $v0,$v0,3
0xbfc000440x10400004beqz $v0,0xbfc00058
0xbfc000480x00000000nop
0xbfc0004c0x24020001li $v0,1
0xbfc000500x1000000db 0xbfc00088
0xbfc000540x00000000nop
0xbfc000580x8fc20020recurse:lw $v0,32($fp)
0xbfc0005c0x2442ffffaddiu $v0,$v0,-1
0xbfc000600x00402025move $a0,$v0
0xbfc000640x0ff00009jal 0xbfc00024
0xbfc000680x00000000nop
0xbfc0006c0x00408025move $s0,$v0
0xbfc000700x8fc20020lw $v0,32($fp)
0xbfc000740x2442fffeaddiu $v0,$v0,-2
0xbfc000780x00402025move $a0,$v0
0xbfc0007c0x0ff00009jal 0xbfc00024
0xbfc000800x00000000nop
0xbfc000840x02021021addu $v0,$s0,$v0
0xbfc000880x03c0e825done:move $sp,$fp
0xbfc0008c0x8fbf001clw $ra,28($sp)
0xbfc000900x8fbe0018lw $fp,24($sp)
0xbfc000940x8fb00014lw $s0,20($sp)
0xbfc000980x27bd0020addiu $sp,$sp,32
0xbfc0009c0x03e00008jr $ra
0xbfc000a00x00000000nop

registers — read · written this tick

HI 0x00000000LO 0x00000000PC 0xbfc00000

stack around $sp = 0x00000000 — higher addresses on top

higher addresses ↑ · each row is one word, byte 0 on the left
0x00000014
00000000
0x00000010
00000000
0x0000000c
00000000
0x00000008
00000000
0x00000004
00000000
0x00000000
00000000
0xfffffffc
00000000
0xfffffff8
00000000
lower addresses ↓ · the stack grows this way

console (what the doors printed)

▮
cycle 0/781 tick = 1 instruction (not a cycle)

tick 0 of 78

Nothing has run yet. The PC (program counter) points at the first instruction.

Every call to fib claims 32 bytes and saves $ra, $fp and $s0 in the same three slots (28, 24, 20). fib(3) calls fib(2), which returns 1 at once (n < 3); then fib(3) calls fib(1), which also returns 1. So at most two frames are alive: $sp goes 0x10000FE0 → 0x10000FC0 → 0x10000FA0 and back. Each jr $ra reads a different saved $ra. $v0 ends as 1 + 1 = 2.

What to notice

fib(3) claims a frame at 0x10000FC0. Its first call, fib(2), claims one at 0x10000FA0, finds 2 < 3, and returns 1 through its own saved $ra. fib(3) parks the 1 in $s0, calls fib(1), which uses the same address 0x10000FA0 for its frame, and returns 1. addu makes 2, and fib(3)’s jr $ra goes back to _start.

Each running call is an . At the deepest point two activations are alive: fib(3) and one child. The child’s frame sits 32 bytes below its parent’s, holds a different $ra, and reads a different n from its own 32(s8). That is all needs.

Before reading on, decide:

fib(3)'s frame occupies 0x10000FC0–0x10000FDF. Where does fib(3) spill its own n = 3?

Go deeper: what -O2 does to fib, and how your core runs the spill and reload

At -O2, GCC keeps n in a callee-saved register instead of spilling it, keeps the first result in another, drops the frame pointer, and saves only $ra and the $s registers it uses. The frame shrinks and the six lw v0,32(s8) reloads vanish. The recursion itself stays: fib still calls itself twice, and each activation still gets its own frame. Chapter 9 shows the -O2 dump beside this one.

The -O0 code has a pattern your core sees constantly: sw a0,32(s8) followed two instructions later by lw v0,32(s8). The store is still waiting in the store buffer when the load asks for the same address. Carolyne’s load/store unit searches the buffer for the newest older store to that word and takes its data directly, without waiting for the store to reach memory. That store-to-load forwarding is what keeps -O0 code from crawling, and it is one of the mechanisms the twelve control bugs of the bring-up were found in.

Can you now explain it?

fib's frame is 32 bytes: $ra at 28, $fp at 24, $s0 at 20, the argument spilled at 32 above it, an argument area below. Every call gets a fresh frame one step lower; at most two are alive in fib(3); the returns unwind through two different saved $ra.

If you remember only three things

  1. Same code, new frame, new n. The jal inside fib runs the same 32 words with $sp 32 bytes lower. 32(s8) is a different word each time.
  2. Two saved $ra, two different places to return to. fib(2) returns into fib(3); fib(3) returns to _start. Each reads its own 28(sp).
  3. The frame is the whole mechanism. No special instruction, no hardware stack. Prologue, epilogue and the argument area do everything.

Now try to explain this one yourself: call fib(4) instead. How deep does the stack get, and which activations are alive at the deepest point? How many bytes below 0x10000FE0 is $sp then?

Go deeper: a model answer, once you have tried

fib(4) calls fib(3), which calls fib(2): three activations alive at once, fib(2) being a base case. Three frames of 32 bytes: $sp reaches 0x10000FE0 − 96 = 0x10000F80. After fib(2) returns, fib(3) calls fib(1) into the same slot; after fib(3) returns, fib(4) calls fib(2) into 0x10000FA0. The deepest point is always the leftmost path of the call tree, and each extra level of n adds one frame, 32 bytes, and one more saved $ra.

Check your understanding

0/5 answered

  1. 1.How deep is the stack at the deepest point of fib(3), counting only fib's frames?

  2. 2.In fib's frame, at what offset from $sp is the saved $ra, and where is n?

  3. 3.What is `move s8,sp` in the prologue for?

  4. 4.What does recursion need from the hardware?

  5. 5.Why does fib compiled at -O2 need a smaller frame than at -O0?

Next: Chapter 7 — mult, multu and the 64-bit product.