--- title: Procedures module: Machine-Level Programming moduleNumber: 1 lessonNumber: 5 order: 105 summary: > How a function call works at the machine level: the run-time stack, call and ret passing control through a saved return address, the System V convention that routes the first six arguments through %rdi..%r9 and the result through %rax, the caller-saved versus callee-saved split, the stack frame, and a recursive factorial traced through its frames. topics: [Machine-Level Programming] sources: - book: Bryant & O'Hallaron ref: "CS:APP — §3.7 Procedures (The Run-Time Stack, Control Transfer, Data Transfer, Local Storage, Recursion)" --- A procedure call must do several things at once: transfer control to the callee and back, pass arguments in, return a result out, and let both functions use the registers without trampling each other's data. x86-64 splits this work between two instructions — `call` and `ret` — and a body of conventions, the **System V AMD64 ABI**, that the hardware does not enforce but every compiler obeys. This lesson assembles the full picture of a function call. ## The run-time stack Each active function call needs private storage: space for local variables that do not fit in registers, for saved registers, and for arguments beyond the sixth. That storage is a **stack frame**, and frames are stacked on the same downward- growing run-time stack from [data movement](/computer-architecture/machine-level-x86-64/data-movement). When a function is called its frame is pushed; when it returns its frame is popped. `%rsp` marks the current top. $$ % caption: The run-time stack with two frames. The caller's frame sits at higher % caption: addresses; call pushed the return address; the callee's frame grows % caption: downward below it, with %rsp at the current top. \begin{tikzpicture}[font=\footnotesize, >=stealth, cell/.style={draw, minimum width=30mm, minimum height=8mm, inner sep=1pt, align=center}] \definecolor{acc}{HTML}{2348F2} \node[cell] (c1) at (0,2.4) {caller's locals}; \node[cell] (c2) at (0,1.6) {args 7, 8, \dots}; \node[cell, draw=acc, fill=acc!8] (ra) at (0,0.8) {return address}; \node[cell] (e1) at (0,0.0) {saved registers}; \node[cell, draw=acc, thick] (e2) at (0,-0.8) {callee's locals}; % brace labels for the two frames \node[anchor=west, font=\scriptsize] at (2.0,2.0) {caller frame}; \node[anchor=west, font=\scriptsize] at (2.0,-0.4) {callee frame}; \node[anchor=west, text=acc, font=\scriptsize] at (2.0,-0.8) {$\gets$ $\mathtt{\%rsp}$ (top)}; % growth direction \draw[->, thick] (-2.4,2.4) -- (-2.4,-0.8) node[midway, left, font=\scriptsize, align=center] {lower\\addr}; \end{tikzpicture} $$ ## call and ret The control transfer is the job of two instructions, and both use `%rsp` and the stack. - `call Label` **pushes** the address of the instruction immediately after the `call` (the **return address**) onto the stack, then sets `%rip` to `Label`. It is `pushq` of the return address plus a `jmp`. - `ret` **pops** the return address off the stack into `%rip`, resuming the caller at the instruction after its `call`. $$ % caption: call and ret. call pushes the return address (lowering %rsp by 8) and % caption: jumps to the callee; ret pops it back into %rip, restoring %rsp. \begin{tikzpicture}[font=\footnotesize, >=stealth, cell/.style={draw, minimum width=26mm, minimum height=7mm, inner sep=1pt, align=center}] \definecolor{acc}{HTML}{2348F2} % before call \node[font=\footnotesize] at (0,2.0) {before \texttt{call}}; \node[cell] (b1) at (0,1.1) {caller data}; \node[cell, draw=acc] (b2) at (0,0.4) {}; \node[anchor=west, text=acc, font=\scriptsize] at (1.5,0.4) {$\gets$ $\mathtt{\%rsp}$}; % after call \node[font=\footnotesize] at (5.5,2.0) {after \texttt{call}}; \node[cell] (a1) at (5.5,1.1) {caller data}; \node[cell, draw=acc, fill=acc!8] (a2) at (5.5,0.4) {return addr}; \node[cell, draw=acc, thick] (a3) at (5.5,-0.3) {}; \node[anchor=west, text=acc, font=\scriptsize] at (7.0,-0.3) {$\gets$ $\mathtt{\%rsp}$ (-8)}; \draw[->, thick] (2.4,0.4) -- (4.2,0.4); \end{tikzpicture} $$ Seen as control flow rather than stack edits, the pair is a round trip: `call` remembers where it was and jumps away; `ret` reads that remembered address and jumps back. The saved return address is what lets control resume in the caller. $$ % caption: call and ret as a control round-trip. call saves the address of the next % caption: instruction and jumps into the callee; ret reads that saved address and % caption: jumps back, resuming the caller exactly where it left off. \begin{tikzpicture}[font=\footnotesize, >=stealth, ins/.style={draw, minimum width=30mm, minimum height=6mm, inner sep=2pt, align=left}] \definecolor{acc}{HTML}{2348F2} % caller column \node[ins] (c1) at (0,1.4) {$\mathtt{call\ mult2}$}; \node[ins, draw=acc, thick] (c2) at (0,0.5) {$\mathtt{movq\ \%rax,(\%rbx)}$}; \node[font=\scriptsize] at (0,2.1) {caller}; % callee column \node[ins] (e1) at (6.0,1.4) {$\mathtt{mult2:\ ...}$}; \node[ins] (e2) at (6.0,0.5) {$\mathtt{ret}$}; \node[font=\scriptsize] at (6.0,2.1) {callee}; % call jump \draw[->, thick] (c1.east) -- (e1.west) node[midway, above, font=\scriptsize] {jump in}; % ret jump back to the saved next-instruction; label below the V, off the path \draw[->, thick, acc] (e2.south) -- (3.0,-0.55) -- (c2.south); \node[font=\scriptsize, text=acc] at (3.0,-0.95) {return to saved address}; \end{tikzpicture} $$ Because the return address sits in ordinary stack memory, anything that overwrites it redirects where `ret` goes — the mechanism behind the buffer overflows of [the final lesson](/computer-architecture/machine-level-x86-64/memory-layout-and-buffer-overflows). ## Passing arguments and returning a value The System V convention routes the **first six** integer or pointer arguments through registers, in a fixed order, and any further arguments on the stack. The result comes back in `%rax`. $$ % caption: Argument registers in order. The first six integer/pointer arguments go % caption: in %rdi, %rsi, %rdx, %rcx, %r8, %r9; the seventh onward go on the stack; % caption: the return value comes back in %rax. \begin{tikzpicture}[font=\footnotesize, reg/.style={draw, minimum width=15mm, minimum height=8mm, inner sep=0pt, align=center}] \definecolor{acc}{HTML}{2348F2} \foreach \n/\r/\x in {1/{\%rdi}/0, 2/{\%rsi}/1.9, 3/{\%rdx}/3.8, 4/{\%rcx}/5.7, 5/{\%r8}/7.6, 6/{\%r9}/9.5} { \node[reg] at (\x,0) {$\mathtt{\r}$}; \node[font=\scriptsize, text=acc] at (\x,0.85) {arg \n}; } \node[reg, draw=acc, thick] (rv) at (4.75,-1.8) {$\mathtt{\%rax}$}; \node[anchor=west, text=acc, font=\scriptsize] at (5.7,-1.8) {return value}; \end{tikzpicture} $$ ```c [add3.c] long add3(long a, long b, long c) { return a + b + c; } ``` ```asm [add3.s] add3: leaq (%rdi,%rsi), %rax # rax = a + b (args in %rdi, %rsi) addq %rdx, %rax # rax = a + b + c (third arg in %rdx) ret # return value already in %rax ``` ### When there are more than six arguments The first six arguments ride in registers; a seventh and beyond travel on the stack, placed there by the caller just below the return address. A function of eight arguments makes the boundary concrete: `a`..`f` arrive in the six registers, and `g` and `h` sit on the stack, which the callee reads as displacements off `%rsp`. ```c [add8.c] long add8(long a, long b, long c, long d, long e, long f, long g, long h) { return a + b + c + d + e + f + g + h; // g, h passed on the stack } ``` ```asm [add8.s] add8: addq %rsi, %rdi # a + b addq %rdx, %rdi # + c addq %rcx, %rdi # + d addq %r8, %rdi # + e addq %r9, %rdi # + f (last register arg) addq 8(%rsp), %rdi # + g (7th arg, on the stack) addq 16(%rsp), %rdi # + h (8th arg, next stack slot) movq %rdi, %rax # return the running sum ret ``` The register arguments come in the fixed order `%rdi, %rsi, %rdx, %rcx, %r8, %r9`, exactly the sequence the figure above lists. The seventh and eighth are the interesting part: at function entry `(%rsp)` holds the return address `call` just pushed, so the caller placed `g` at `8(%rsp)` and `h` at `16(%rsp)`, right above it. Reading `8(%rsp)` and `16(%rsp)` recovers them in order. This is the mechanism to watch for whenever a function takes many arguments — the register slots fill first, then the overflow spills onto the caller's stack. ## Caller-saved versus callee-saved The registers are shared between caller and callee, so the convention partitions them by **who is responsible** for a register's value surviving a call.[^saved] > **Definition (Register save discipline).** A **callee-saved** register > (`%rbx`, `%rbp`, `%r12`, `%r13`, `%r14`, `%r15`) must hold the same value after a > call as before it; a callee that wants to use one must save and restore it. A > **caller-saved** register (all the others, including the argument registers and > `%rax`) may be freely overwritten by a callee, so a caller that needs its value > across a call must save it first. This convention is why [the first lesson's](/computer-architecture/machine-level-x86-64/the-machines-view) `multstore` wrapped its body in `pushq %rbx` / `popq %rbx`: it needed a register that survived the inner `call mult2`, chose the callee-saved `%rbx`, and therefore took on the obligation to preserve the caller's `%rbx` by saving it. | Class | Registers | Who preserves | | --- | --- | --- | | Callee-saved | `%rbx`, `%rbp`, `%r12`–`%r15` | the callee, if it uses them | | Caller-saved | `%rax`, `%rcx`, `%rdx`, `%rsi`, `%rdi`, `%r8`–`%r11` | the caller, if needed across a call | $$ % caption: The register file split by save discipline. Callee-saved registers % caption: survive a call by contract, so a caller can trust them; caller-saved ones % caption: may be clobbered, so a caller must spill any it still needs. \begin{tikzpicture}[font=\footnotesize, reg/.style={draw, minimum width=12mm, minimum height=6mm, inner sep=0pt, font=\scriptsize}] \definecolor{acc}{HTML}{2348F2} % callee-saved group \node[font=\scriptsize, text=acc] at (1.95,1.65) {callee-saved (survive a call)}; \foreach \r/\x in {{\%rbx}/0, {\%rbp}/1.3, {\%r12}/2.6, {\%r13}/3.9} { \node[reg, draw=acc, fill=acc!8] at (\x,1.0) {$\mathtt{\r}$};} \node[reg, draw=acc, fill=acc!8] at (0,0.3) {$\mathtt{\%r14}$}; \node[reg, draw=acc, fill=acc!8] at (1.3,0.3) {$\mathtt{\%r15}$}; % caller-saved group \node[font=\scriptsize] at (8.3,1.65) {caller-saved (may be clobbered)}; \foreach \r/\x in {{\%rax}/6.3, {\%rcx}/7.6, {\%rdx}/8.9, {\%rsi}/10.2} { \node[reg] at (\x,1.0) {$\mathtt{\r}$};} \foreach \r/\x in {{\%rdi}/6.3, {\%r8}/7.6, {\%r9}/8.9, {\%r10}/10.2} { \node[reg] at (\x,0.3) {$\mathtt{\r}$};} \node[reg] at (6.3,-0.4) {$\mathtt{\%r11}$}; % divider \draw[black, dashed] (5.0,-0.7) -- (5.0,1.8); \end{tikzpicture} $$ ## A stack frame through a two-deep call The conventions become concrete when traced through an actual call chain. Let `main` call `p`, and `p` call `q`. The interesting function is `p`, because it holds a value across a call: ```c [chain.c] long q(long y) { return y + 1; } long p(long x) { long t = q(x); // q is free to clobber the caller-saved registers return x + t; // but x must survive the call to q } ``` `p` needs `x` both before and after `call q`, and `q` may overwrite every caller-saved register, including the argument register `%rdi` that carried `x` in. So `p` copies `x` into a **callee-saved** register, `%rbx`, and takes on the matching obligation: save the caller's `%rbx` on entry, restore it on exit. ```asm [chain.s] p: pushq %rbx # save caller's %rbx (obligation for using it) movq %rdi, %rbx # keep x in callee-saved %rbx across the call call q # t = q(x), result in %rax addq %rbx, %rax # rax = x + t popq %rbx # restore caller's %rbx ret q: leaq 1(%rdi), %rax # return y + 1 ret ``` Watch the stack at three moments. After `p`'s prologue, its frame holds the return address into `main` and the saved `%rbx`. When `p` executes `call q`, a second return address (into `p`) is pushed, growing the stack to its deepest point. When `q` returns, that address is popped and the stack shrinks back to exactly the shape it had before the call. $$ % caption: The stack at three moments of main -> p -> q. (A) inside p after its % caption: prologue; (B) inside q at the deepest point, one return address deeper; % caption: (C) back in p after q returns, restored to the shape of (A). %rsp marks % caption: the top; the stack grows downward. \begin{tikzpicture}[font=\footnotesize, >=stealth, cell/.style={draw, minimum width=24mm, minimum height=6.5mm, inner sep=1pt, align=center}] \definecolor{acc}{HTML}{2348F2} % ---- (A) inside p, before call q ---- \node[font=\footnotesize] at (0,1.7) {(A) in \texttt{p}, before \texttt{call q}}; \node[cell] (a1) at (0,0.9) {ret addr $\to$ \texttt{main}}; \node[cell, draw=acc, thick] (a2) at (0,0.25) {saved \texttt{\%rbx}}; \node[anchor=west, text=acc, font=\scriptsize] at (1.35,0.25) {$\gets$ \%rsp}; % ---- (B) inside q, deepest ---- \node[font=\footnotesize] at (5,1.7) {(B) in \texttt{q}, deepest}; \node[cell] (b1) at (5,0.9) {ret addr $\to$ \texttt{main}}; \node[cell] (b2) at (5,0.25) {saved \texttt{\%rbx}}; \node[cell, draw=acc, thick] (b3) at (5,-0.4) {ret addr $\to$ \texttt{p}}; \node[anchor=west, text=acc, font=\scriptsize] at (6.35,-0.4) {$\gets$ \%rsp}; % ---- (C) back in p, after q returns ---- \node[font=\footnotesize] at (10,1.7) {(C) in \texttt{p}, after \texttt{q}}; \node[cell] (c1) at (10,0.9) {ret addr $\to$ \texttt{main}}; \node[cell, draw=acc, thick] (c2) at (10,0.25) {saved \texttt{\%rbx}}; \node[anchor=west, text=acc, font=\scriptsize] at (11.35,0.25) {$\gets$ \%rsp}; % growth arrow on the far left \draw[->, thick] (-2.4,0.9) -- (-2.4,-0.4) node[midway, left, font=\scriptsize, align=center] {grows\\down}; \end{tikzpicture} $$ The `call`/`ret` pair moves `%rsp` by exactly 8 in each direction, so the frame is back to its `(A)` shape the instant `q` returns. `p`'s own `popq %rbx` then undoes the prologue, and `p`'s `ret` returns the stack to `main` untouched. Every function that plays by the rules leaves the stack exactly as it found it. ## A recursive call traced Recursion needs nothing special: each call gets its own frame, so each invocation's locals and saved state are independent. Here is recursive factorial and its frames. ```c [rfact.c] long rfact(long n) { if (n <= 1) return 1; return n * rfact(n - 1); } ``` ```asm [rfact.s] rfact: cmpq $1, %rdi # compare n, 1 jg .Lrec # if n > 1, recurse movl $1, %eax # base case: return 1 ret .Lrec: pushq %rbx # save callee-saved %rbx movq %rdi, %rbx # keep n across the recursive call leaq -1(%rdi), %rdi # arg = n - 1 call rfact # rax = rfact(n - 1) imulq %rbx, %rax # rax = n * rfact(n - 1) popq %rbx # restore %rbx ret ``` The function stashes `n` in callee-saved `%rbx` because it must survive the recursive `call`, which is free to clobber the caller-saved argument registers. As the recursion descends, each level pushes its own return address and `%rbx`, so the stack carries one frame per pending call. $$ % caption: The stack during rfact(3) at the deepest point. Each pending call left a % caption: frame holding its saved %rbx (its own n) and a return address; the base % caption: case at the top unwinds back up, multiplying as ret returns. \begin{tikzpicture}[font=\footnotesize, >=stealth, cell/.style={draw, minimum width=34mm, minimum height=7mm, inner sep=1pt, align=center}] \definecolor{acc}{HTML}{2348F2} % frame for rfact(3) \node[cell] (r3) at (0,2.8) {ret addr (caller)}; \node[cell] (b3) at (0,2.1) {saved \texttt{\%rbx} $= 3$}; % frame for rfact(2) \node[cell] (r2) at (0,1.3) {ret addr (into rfact)}; \node[cell] (b2) at (0,0.6) {saved \texttt{\%rbx} $= 2$}; % deepest active: rfact(1) base case (no rbx push) \node[cell, draw=acc, thick] (r1) at (0,-0.2) {ret addr (into rfact)}; \node[anchor=west, text=acc, font=\scriptsize] at (2.2,-0.2) {$\gets$ $\mathtt{\%rsp}$ (top)}; \node[anchor=west, font=\footnotesize] at (2.2,2.45) {\texttt{rfact(3)}}; \node[anchor=west, font=\footnotesize] at (2.2,0.95) {\texttt{rfact(2)}}; \draw[->, thick] (-2.6,2.8) -- (-2.6,-0.2) node[midway, left, font=\scriptsize, align=center] {lower\\addr}; \end{tikzpicture} $$ Unwinding multiplies on the way back: `rfact(1)` returns `1`, `rfact(2)` computes $2 \cdot 1$, `rfact(3)` computes $3 \cdot 2$, each `ret` popping a frame and each restored `%rbx` supplying that level's `n`. Follow `rfact(3)` value by value to see the role of the saved `%rbx`. The outer call saves the caller's `%rbx`, sets `%rbx = 3`, and calls `rfact(2)`. That call saves the `%rbx` holding 3, sets `%rbx = 2`, and calls `rfact(1)`. The innermost call takes the base case, returning `%rax = 1` without touching `%rbx` at all. Now the returns fire in reverse: back in `rfact(2)`, `%rbx` was restored to 2 by nothing yet — it is still 2 because this frame set it — so `imulq %rbx, %rax` gives $2 \cdot 1 = 2$; its `popq %rbx` then restores the caller's `%rbx` to 3. Back in `rfact(3)`, `%rbx` is 3, so `imulq` gives $3 \cdot 2 = 6$, and its `popq` restores the original caller's `%rbx`. The result $6 = 3!$ emerges in `%rax`. Each frame's private `%rbx` held that level's `n` across the deeper call, which is the entire reason recursion needs no special machinery: the stack gives every invocation its own copy. $$ % caption: rfact(3) traced through descent and return. Each level saves its %rbx % caption: (its own n) before recursing; on the way back, imulq multiplies the % caption: returned value by that n, yielding 1, then 2, then 6. \begin{tikzpicture}[font=\footnotesize, >=stealth, lvl/.style={draw, minimum width=30mm, minimum height=6.5mm, inner sep=2pt, align=left, font=\scriptsize}] \definecolor{acc}{HTML}{2348F2} \node[lvl] (d3) at (0,1.5) {$\mathtt{rfact(3)}$: $\mathtt{\%rbx}=3$, call down}; \node[lvl] (d2) at (0,0.75) {$\mathtt{rfact(2)}$: $\mathtt{\%rbx}=2$, call down}; \node[lvl] (d1) at (0,0.0) {$\mathtt{rfact(1)}$: base, return $1$}; \node[lvl, draw=acc, text=acc] (u2) at (0,-0.75) {return $2$ x $1 = 2$ to $\mathtt{rfact(3)}$}; \node[lvl, draw=acc, text=acc] (u3) at (0,-1.5) {return $3$ x $2 = 6$ to caller}; \draw[->, thick] (d3.east) -- (3.7,1.5) -- (3.7,0.0) -- (d1.east); \node[right, font=\scriptsize] at (3.7,0.75) {descend}; \draw[->, thick, acc] (d1.west) -- (-2.8,0.0) -- (-2.8,-1.5) -- (u3.west); \node[left, acc, font=\scriptsize] at (-2.8,-0.75) {unwind}; \end{tikzpicture} $$ ## Tail calls and unwinding the stack Two topics the wider literature treats that CS:APP touches only lightly are worth knowing because they change what the stack does. The first is the **tail call**. When the very last action of a function is to call another and return its result — like `return g(x);` with nothing after — the current frame is no longer needed once `g` starts, so a compiler can reuse it: instead of `call g; ret`, it emits a plain `jmp g`, letting `g`'s own `ret` return directly to the original caller. This **tail-call optimization** turns a chain of recursive tail calls into a loop that uses constant stack space instead of one frame per call, which is why a tail-recursive loop does not overflow the stack the way naive `rfact` eventually would. The optimization is central to how functional-language compilers target the same machine, and gcc and clang both perform it at `-O2`.[^tailcall] The second is **stack unwinding**: given a `%rsp` deep in a call chain, how does a debugger or a C++ exception reconstruct the sequence of pending calls? When the compiler omits the frame pointer (the common case now that `%rbp` is a general register), the saved return addresses are still on the stack, but their exact offsets vary per function. The answer is out-of-band metadata: the compiler emits **DWARF** call-frame information — a table, keyed by instruction address, describing where each function saved the return address and callee-saved registers. A debugger walks the stack by consulting this table frame by frame, and the same information drives C++ exception propagation. It is the reason an optimized, frame-pointer-free binary can still produce a correct backtrace.[^dwarf] > **Takeaway.** A call is `call` (push return address, jump) paired with `ret` (pop > it back into `%rip`), riding the downward stack. The System V convention passes > args 1–6 in `%rdi`, `%rsi`, `%rdx`, `%rcx`, `%r8`, `%r9`, the rest on the stack, > and returns in `%rax`. Callee-saved registers (`%rbx`, `%rbp`, `%r12`–`%r15`) > must be preserved by whoever uses them; all others are caller-saved. Recursion is > just one frame per pending call. [^saved]: **Bryant & O'Hallaron**, _CS:APP_, §3.7.5 — Local Storage in Registers: the System V partition of the integer registers into caller-saved and callee-saved, with `%rbx`, `%rbp`, and `%r12`–`%r15` callee-saved. [^tailcall]: **Appel**, _Modern Compiler Implementation in ML_ (1998), §6.2 — tail-call optimization, replacing a call-in-tail-position and return with a jump so tail-recursive calls run in constant stack space. [^dwarf]: **DWARF Debugging Information Format Committee**, _DWARF Version 5_ (2017), §6.4 — Call Frame Information: the per-address table describing where return addresses and callee-saved registers live, used to unwind frames without a frame pointer.