The idea: a procedure call is a contract

A procedure (a function in C) is code that can be called from many places and returns to whoever called it. The caller and the callee share one set of 32 registers and one memory, so they need rules: where the arguments go, where the result comes back, how the callee finds its way back, and which registers each side may destroy. These rules are the calling convention. The hardware knows almost nothing about them: it only provides jal and jr. Everything else is an agreement between programmers and compilers.

main puts 2, 3, 4, 5 in $a0–$a3, jal diffofsums at 0x00400020 stores 0x00400024 in $ra and jumps; diffofsums adds, subtracts, puts −4 in $v0, and jr $ra jumps back to 0x00400024
The caller and callee only meet in registers: arguments in $a0–$a3, the way back in $ra, the result in $v0.

The page runs small MIPS programs one instruction at a time. The program listing is on the left (the yellow line was just executed, ► points at the next one), then the registers the programs use, the top of the stack in memory with $sp, and the calls made so far. Each tab is a program; the version menu holds a correct version and the classic ways to break it.

RuleCallerCallee
argumentsputs them in $a0–$a3reads them from $a0–$a3
return valuereads $v0 (and $v1)puts it in $v0
getting backjal stores the return address in $rajr $ra
registerssaves any $t, $a, $v it still needssaves the $s registers it changes, and $ra if it calls
stackfinds $sp and everything above it unchangedfrees exactly what it allocated

jal and jr $ra

jal label (jump and link) does two things at once: it stores PC + 4, the address of the next instruction, in register $ra (the return address), and it jumps to label. At the end the callee executes jr $ra (jump register), which copies $ra into the PC. A plain j could not do this: the callee would not know where to go back, and the same procedure is called from different places.

In Demo 1: leaf call, jal diffofsums sits at 0x00400020, so $ra becomes 0x00400024; the yellow chip flies from the listing into $ra, and at the end jr $ra flies it back. Even main is a callee: the startup code at 0x00400000 calls it with jal main, and main ends with jr $ra back to the syscall that ends the program.

Arguments and return values

The first four arguments go in $a0–$a3 and the result comes back in $v0 ($v1 for a 64-bit result). diffofsums(f, g, h, i) gets 2, 3, 4, 5 in $a0–$a3 and returns (2 + 3) − (4 + 5) = −4. A procedure with more than four arguments receives the extra ones on the stack, just above its frame.

The stack and stack frames

The stack is ordinary memory used last-in, first-out. On MIPS it starts at the top of the stack segment, $sp = 0x7FFFFFFC, and grows down: to make room, a procedure subtracts from $sp. The space one call allocates is its stack frame:

addi $sp, $sp, -8     # allocate 2 words
sw   $ra, 4($sp)      # save
sw   $s0, 0($sp)
  ...                 # body, calls
lw   $s0, 0($sp)      # restore
lw   $ra, 4($sp)
addi $sp, $sp, 8      # free the frame
jr   $ra

On the canvas each call has its own colour, used for its frame words on the stack and its row in the call tree. When a frame is freed, its words turn grey: they keep their old values (memory is not erased) but they are below $sp, and the next call will overwrite them. That is why a returned pointer to a local variable is a bug in C.

Preserved and nonpreserved registers

If every callee had to save every register it touches, calls would be slow; if none did, every caller would have to save everything. MIPS splits the registers in two (H&H Table 6.3):

Preserved (callee-saved)Nonpreserved (caller-saved)
$s0–$s7 saved registers$t0–$t9 temporaries
$ra return address$a0–$a3 arguments
$sp stack pointer$v0–$v1 return values
stack above $spstack below $sp

A callee may use a preserved register only if it puts the old value back before returning, so it saves it in its frame first (Demo 3: callee saves $s0, Code Example 6.27: main keeps x = 99 in $s0, diffofsums saves and restores it, and main returns −4 + 99 = 95). A nonpreserved register is fair game: a caller that needs one after the call must save it itself, or keep the value in an $s register instead. The page checks every return: the call-tree row says ✓ when the callee gave back $sp and $s0 unchanged, ✗ and the reason when it did not.

A leaf procedure (one that calls nobody) that uses only $t registers needs no frame at all, which is why diffofsums in Demo 1 is four instructions long.

Nested calls and $ra

jal always writes $ra. So a procedure that calls another destroys its own return address, and must save $ra on the stack before its jal and restore it before its jr $ra. In Demo 6 main calls f(5), f saves $ra and calls g(5) = 10, then returns 11. g is a leaf and needs no frame.

In Demo 7 f does not save $ra. jal g sets $ra to the instruction after it, inside f. When f executes jr $ra it jumps there, adds 1 again, reaches jr $ra again with the same $ra: an infinite loop. The page stops it the second time the same jr runs with the same $ra and $sp ($v0 = 12 by then).

Recursion: factorial

A recursive procedure is just a nested call to itself, so it follows the same rules. factorial (Code Example 6.28) saves $a0 (it needs n after the recursive call, and $a0 is nonpreserved) and $ra in a 2-word frame, calls factorial(n − 1), restores both, and returns n × factorial(n − 1). Every call gets its own frame, so every call has its own n and its own way back (Demo 8: factorial(3)):

CallFrameSaved $a0Saved $raReturns
main0x7FFFFFF8–0x00400004 (in __start)6
factorial(3)0x7FFFFFF0–F430x00400018 (in main)3 × 2 = 6
factorial(2)0x7FFFFFE8–EC20x00400050 (after the recursive jal)2 × 1 = 2
factorial(1)0x7FFFFFE0–E410x004000501 (base case)
Stack during factorial(3) at its deepest point: main frame at 0x7FFFFFF8, then 2-word frames for factorial(3), factorial(2) and factorial(1) each holding saved $a0 = n and $ra, with $sp = 0x7FFFFFE0 at the bottom
Every recursive call gets its own frame with its own n and its own return address, stacked downward from 0x7FFFFFFC.

The stack reaches its lowest point, $sp = 0x7FFFFFE0, in the base case, at call depth 4; then the frames are freed in the opposite order. factorial(4) (version menu) goes down to 0x7FFFFFD8 and returns 24. Each level costs 8 bytes of stack, which is why very deep recursion ends in a stack overflow. See Recursive Factorial for the same recursion at the language level.

When the contract is broken

A broken convention almost never fails where the mistake is. It fails later, in the caller, which trusted the contract:

BugDemoWhere it shows
caller keeps a value in $t0 across a call2every return is ✓, but main returns 1 instead of 6: the callee was allowed to overwrite $t0
callee uses $s0 without saving it (Code Example 6.25)4return ✗ ($s0 99 → −4); main returns −8 instead of 95
callee forgets addi $sp, $sp, 45return ✗ ($sp off by 4); every lw in main reads the wrong word, $ra becomes 7, jr $ra jumps to 0x00000007: crash
non-leaf does not save $ra7f returns into itself: infinite loop

Compilers follow the convention mechanically, so these bugs come from hand-written assembly, or from C code that overwrites the stack (a buffer overflow overwrites a saved $ra on purpose, and the jr $ra then jumps where the attacker wants). The Stack vs Heap in C page shows the same frames on x86-64 Linux.

What the page leaves out

  • Only $v0, $a0–$a3, $t0, $t1, $s0, $sp and $ra are drawn; the others follow the same rules ($s1–$s7 preserved, $t2–$t9 nonpreserved). Only 10 words of the stack are drawn.
  • No frame pointer $fp, no local arrays or variables in the frame, no arguments beyond four, no $gp. The real o32 ABI also reserves 16 bytes of argument space in every frame and keeps $sp 8-byte aligned.
  • No branch delay slots: as in H&H, the instruction after jal and jr does not run first. On a real MIPS it does (and $ra is PC + 8).
  • syscall here just ends the run. The return check (✓/✗), the infinite-loop detection and the crash message are drawn by the page; real hardware checks none of the convention, it only raises an address error exception for the bad jump.
  • $s0 starts at 7 to stand for a value the startup code wants back; all other registers start at 0.

Where the stack segment and 0x7FFFFFFC come from: Translating and Starting a MIPS Program. How jal and jr move the PC in hardware: The Single-Cycle MIPS Processor.