Procedure Calls and the Stack

A procedure call transfers control from a caller to a callee and expects control to return afterward, resuming exactly where it left off. The hardware alone cannot guarantee this: a `jump` instruction has no memory of where it came from, and if procedure A calls B which calls C, the processor needs a place to keep multiple pending return addresses simultaneously, one per level of nesting. Because calls nest and unwind in last-in-first-out order — the most recently called procedure is the first to return — a stack is the natural data structure: push on entry, pop on exit, and the LIFO discipline automatically matches call nesting to return order. Concretely, the stack lives in ordinary memory, and one general-purpose register is reserved as the stack pointer (SP), conventionally pointing to the most recently pushed word. Many architectures also use a frame pointer (FP), sometimes called the base pointer, that stays fixed for the duration of one procedure's execution and gives a stable reference for accessing that procedure's arguments and local variables even as SP moves during the procedure's own pushes and pops. The contiguous block of stack memory belonging to one active call is its stack frame or activation record; it typically contains the return address, saved register values, local variables that don't fit in registers, and sometimes incoming arguments that didn't fit in argument registers. The rules that make all of this interoperate — which registers carry arguments, which carry the return value, which the callee must preserve, how the stack grows (typically downward, toward lower addresses, in most modern ISAs), and who is responsible for cleaning up pushed arguments — constitute the calling convention, formalized as part of the platform's ABI. The ABI is a social contract: nothing in the hardware enforces it, but if a compiler violates it, code compiled by another compiler (or a different function in the same program) will read garbage from the wrong registers or the wrong stack slots. This is precisely why the same convention persists across compilers on a given platform (e.g., the RISC-V calling convention, or the x86-64 System V ABI), enabling separate compilation and linking.

A procedure call consists of four coordinated phases, split between caller and callee: 1. Caller setup — place arguments in agreed argument registers (or push overflow arguments on the stack), then execute a call instruction that (a) saves the return address (often in a link register or by pushing it) and (b) jumps to the callee's first instruction. 2. Callee prologue — the callee allocates its own stack frame by decrementing SP, saves any callee-saved registers it intends to overwrite, and optionally sets up a frame pointer. 3. Callee body and epilogue — the callee executes its logic, places its result in the return-value register, restores the callee-saved registers it saved, deallocates its frame by restoring SP, and returns control via a return instruction that jumps to the saved return address. 4. Caller cleanup — the caller resumes at the instruction after the call, retrieves the return value, and (in some conventions) removes any stack arguments it pushed. The essential invariant across this whole dance is: > The stack pointer, and every register the callee promised to preserve, must have the same value immediately after the call returns as immediately before the call was made (aside from the return-value register and any register explicitly used to pass the result). Everything else — how many registers you use for arguments, whether you use a frame pointer, whether locals live in registers or on the stack — is an optimization detail layered on top of that one guarantee. ``` // Generic RISC-style calling convention. // Convention (illustrative, RISC-V-like): // a0..a7 = argument / return-value registers (caller-saved) // t0..t6 = temporary registers (caller-saved) // s0..s11 = saved registers (callee-saved) // ra = return address register // sp = stack pointer (grows toward lower addresses) CALL(callee, args...): // --- Caller side --- place args[0..k] into a0..a(k) // registers first if extra args beyond register count: push remaining args onto stack // in reverse, so first extra arg is on top jal ra, callee // "jump and link": ra <- PC+4 ; PC <- callee // control returns here after callee executes RET result <- a0 // read return value if extra args were pushed: sp <- sp + (bytes pushed) // caller cleans up (varies by convention) PROCEDURE callee: // --- Prologue --- sp <- sp - FRAME_SIZE // allocate frame (return addr + saved regs + locals) store ra -> [sp + RA_OFFSET] // save return address if callee itself calls out store s0 -> [sp + S0_OFFSET] // save any callee-saved regs this function will clobber store s1 -> [sp + S1_OFFSET] fp <- sp + FRAME_SIZE // (optional) frame pointer for stable local access // --- Body --- // ... use a0..a7 as incoming arguments ... // ... use t0..t6 freely, no need to save ... // ... use s0, s1 for values that must survive nested calls ... // ... nested call, if any: recurses into CALL(...) exactly as above ... a0 <- computed_result // place return value // --- Epilogue --- load s0 <- [sp + S0_OFFSET] // restore callee-saved regs load s1 <- [sp + S1_OFFSET] load ra <- [sp + RA_OFFSET] // restore return address sp <- sp + FRAME_SIZE // deallocate frame jr ra // "jump register": PC <- ra ``` The prologue/epilogue pair is symmetric by construction: whatever the prologue subtracted from `sp`, the epilogue adds back; whatever registers the prologue pushed, the epilogue pops in matching slots. This symmetry is exactly what re-establishes the invariant above, and it is why a stack frame can be thought of as a self-contained, self-cleaning unit — the callee leaves no trace on the stack once it returns, regardless of how much work happened in between, including arbitrarily deep recursive calls.

Note the growth direction: as calls nest deeper, `sp` moves toward lower addresses, and each frame sits directly below the frame of its caller. Returning simply moves `sp` back up, effectively deallocating the topmost frame in O(1) time regardless of what that frame contained.

Time. Each call costs a constant number of extra instructions independent of program size or recursion depth: one instruction to jump-and-link, a handful of stores in the prologue (bounded by the number of registers the callee chooses to save, a small constant, typically 0–15), and a matching handful of loads in the epilogue plus one jump-register to return. So the overhead of a single call/return pair is O(1). A program that makes $n$ calls in total (including recursive calls) therefore pays O(n) total overhead for call/return mechanics, on top of whatever work each call body does — this is why recursion is not inherently slow; the bookkeeping is cheap, and any slowness comes from the algorithm's own recursive structure (e.g., naive Fibonacci's exponential blow-up is a algorithmic issue, not a stack-mechanism issue).

Space. Each active (not-yet-returned) call occupies one frame of fixed size determined by that function's needs. If the maximum simultaneous call depth is $d$, the stack uses O(d · s) space, where $s$ is the (per-function) frame size — this is why unbounded or excessively deep recursion causes a stack overflow: the stack region is finite (a fixed-size memory segment, typically megabytes), and depth is effectively bounded by (stack size) / (average frame size).

Correctness argument. The key invariant to prove is: after `jr ra` executes in the callee, the machine state (SP, callee-saved registers, and the return address stream) matches what a call-free execution would have produced, except for the agreed-upon changes (return value in `a0`, memory side effects). The argument is by structural induction on call nesting:

• Base case: a leaf procedure that makes no further calls. Its prologue saves exactly the callee-saved registers it modifies and decrements `sp` by its frame size; its epilogue restores those registers and restores `sp` by the same amount before `jr ra`. Since these are exact inverses executed on the same, unaliased memory region (the frame it just allocated), the net effect on `sp` and callee-saved registers is zero, satisfying the invariant trivially.
• Inductive step: assume every procedure the callee calls satisfies the invariant (preserves `sp` and callee-saved registers across its own call/return). The callee's body issues zero or more such calls; by the inductive hypothesis, each one leaves `sp` and callee-saved registers as they were immediately before that call. Hence between calls, the callee's local view of `sp`/registers evolves only due to its own prologue/epilogue arithmetic, which — as in the base case — is self-canceling. Therefore the whole procedure, including all its nested calls, preserves the invariant.

This induction is exactly why separately-compiled functions, unaware of each other's internals, can call each other correctly: each only needs to trust that the ABI contract is upheld, not know how the callee is implemented. The correctness of the whole system reduces to each function locally upholding one register-preservation contract — a beautiful instance of compositional reasoning enabled by convention rather than hardware enforcement.

Tradeoffs. Caller-saved vs. callee-saved registers is a genuine time/space tradeoff: caller-saved registers avoid needless saves when the caller doesn't need a value across the call (good for temporaries), but force a save+restore around every call site that does need the value preserved. Callee-saved registers push the save/restore into the callee, done exactly once regardless of how many call sites call it — better when a function is called from many places and needs to preserve values for its callers. Real ABIs split registers into both categories to balance this. Using a frame pointer costs one extra register and a few instructions but simplifies debugging (stack walking, unwinding) and variable-length stack frames (e.g., `alloca`); omitting it ("frame-pointer omission") frees a register for general use at the cost of harder stack introspection.

Consider this small program, computing `f(3)` where `f` calls a helper `g`: ``` int g(int x) { return x x; } int f(int n) { int t = g(n) + 1; // must survive the call to g, so t's source* n needs to be preserved return t; } int main() { return f(3); } ``` We trace register/stack state using the convention from the pseudocode above (`a0` = arg/return, `s0` = callee-saved, `ra` = return address, `sp` = stack pointer; stack grows downward; assume each frame is 16 bytes for simplicity, aligned).

Two things are worth emphasizing from this trace. First, notice at step 5: `f` had to save `n` into the callee-saved register `s0` before calling `g`, because `g` is free to clobber `a0` (a caller-saved/argument register) and even `t0`–`t6`, but is contractually forbidden from clobbering `s0` without restoring it — that's exactly what lets `f` retrieve `n`'s value's role safely across the nested call, even though in this case it doesn't need `n` again (a more elaborate example — `g(n) + n` — would make this necessity obvious, since `a0` is destroyed by `g`'s own return value). Second, notice that `sp` returns to exactly 0x7F00 after `f` returns to `main`, and to exactly 0x7EF0 after `g` returns to `f` — precisely the invariant proved above, holding at every level of nesting.

The stack-based procedure call, as a hardware-supported convention, crystallized alongside the earliest stored-program computers and the first high-level, block-structured languages that needed to support recursion and nested scopes — most influentially ALGOL 60, whose formalization of the block structure required exactly the LIFO activation-record discipline described here.

Every compiled language runtime — C, C++, Rust, Go, Java's JIT, Python's CPython interpreter internals — relies on stack frames to implement function calls, recursion, and local variable scoping; this is the mechanism a debugger reads when it prints a backtrace. Operating system kernels rely on the exact same save-state/restore-state discipline, generalized, to implement context switches between threads and to handle Exceptions and Interrupts, which can be viewed as a forced procedure call triggered by hardware rather than by an explicit instruction. Compiler backends (LLVM, GCC) contain dedicated calling-convention modules per target ISA, precisely encoding which registers are caller-/callee-saved and how frames are laid out, because getting this wrong breaks interoperability between separately compiled object files. Security hardening features — stack canaries, shadow stacks, control-flow integrity — exist specifically to detect or prevent violations of the stack-frame invariant described above, making a precise understanding of calling conventions foundational to systems security as well as to compiler construction and processor design.

Ask the tutor: How does a hardware interrupt's forced "call" differ from a normal procedure call in what state must be saved?