Procedure calls and stack frames in hardware

Why it exists

A procedure can be called from many places, can call other procedures and, with recursion, can call itself. So the hardware needs three things at the moment of a call: where to come back to (the return address), where the arguments are, and fresh storage for the procedure's own local variables, which must not overwrite the storage of an earlier, still-active call. A last-in first-out stack in memory solves all three: the most recent call is always the first one to finish. The hardware support is small, a stack pointer register and a CALL/RET pair, and the rest is convention. GATE asks for the contents of the stack after a sequence of calls, the value of the stack pointer, the memory a recursion needs, and what happens to the return address.

Prerequisites

You need register-indirect and displacement addressing from addressing modes, and the idea of the call stack from recursion and the call stack.

Precise definitions

The stack. A region of memory used last-in first-out, managed with a stack pointer (SP). Push stores a word and moves SP; pop reads a word and moves SP back. Two choices matter in every question:

• Direction of growth. Most machines grow the stack toward lower addresses ("descending"). Then a push decreases SP and a pop increases it.
• What SP points at. Either at the last word pushed (the top, "full") or at the next free word ("empty"). With a full descending stack: push is $SP \leftarrow SP - 1;\ M[SP] \leftarrow x$ and pop is $x \leftarrow M[SP];\ SP \leftarrow SP + 1$. With an empty descending stack the order of the two steps is swapped.

(Units: SP changes by the size of a word, 1 on a word-addressed machine, 4 on a byte-addressed machine with 4-byte words.)

CALL and RET. CALL target pushes the return address (the PC after the fetch of the CALL, i.e. the address of the next instruction) and sets $PC \leftarrow target$. RET pops the return address into the PC. Some ISAs (RISC) instead save the return address in a link register and have the callee push it only if it makes further calls.

Stack frame (activation record). The stack area belonging to one active call. A typical layout from higher to lower addresses: the arguments (pushed by the caller), the return address (pushed by CALL), the saved frame pointer (pushed by the callee), the callee's saved registers, and its local variables and temporaries. The frame pointer (FP) is a register set to a fixed point inside the frame, so that arguments and locals have fixed offsets from FP (positive for the arguments, negative for the locals) even while SP moves as temporaries are pushed.

Prologue and epilogue. On entry (prologue): push the old FP, copy SP to FP, and subtract the size of the locals from SP. On exit (epilogue): copy FP to SP (discarding the locals), pop the saved FP, then RET.

Register saving. A caller-saved register may be changed by the callee, so the caller must save it before the call if it needs the value afterwards; a callee-saved register must be restored by the callee before returning, so the callee pushes it on entry and pops it on exit. The split is a convention of the platform.

Parameter passing. Arguments are passed in registers (fast, only a few) or on the stack (any number). The result is returned in a register. Who removes the stack arguments (the caller or the callee) is also a convention.

Recursion and stack usage. Each active call has its own frame, so a recursion of depth $d$ with frames of $k$ words uses $d \cdot k$ words of stack. The depth counts simultaneously active calls, not the total number of calls: a function that makes 177 calls in all (such as fib(10)) needs only 10 frames at once. Exceeding the stack's size is a stack overflow.

Interrupts use the same mechanism: the hardware pushes the PC (and flags) before running the handler (interrupts).

How it works

The animation executes a call to f(1, 2) where f(a, b) returns $a + b$. The stack grows downward from address 100; the memory rows are the stack words. Follow SP and FP: the caller pushes the arguments, CALL pushes the return address, the prologue saves FP and allocates a local, the body reads the arguments at FP + 2 and FP + 3 and writes the local at FP − 1, and the epilogue and RET undo everything in reverse order.

After the call, SP, FP and PC are as they were (PC has advanced to the return address 13), but the old words (arguments, return address, saved FP, local) are still in memory. They are above SP, so they are dead and will be overwritten by the next call.

Worked examples

#include <stdio.h>
 
static int depth, max_depth, calls;
 
static long fact(int n) {
    depth++;
    calls++;
    if (depth > max_depth) max_depth = depth;
    long r = n <= 1 ? 1 : n * fact(n - 1);
    depth--;
    return r;
}
 
static int fib(int n) {
    depth++;
    calls++;
    if (depth > max_depth) max_depth = depth;
    int r = n < 2 ? n : fib(n - 1) + fib(n - 2);
    depth--;
    return r;
}
 
int main(void) {
    printf("fact(5) = %ld: %d calls, deepest nesting %d frames\n", fact(5), calls, max_depth);
    calls = max_depth = 0;
    printf("fib(5) = %d: %d calls, deepest nesting %d frames\n", fib(5), calls, max_depth);
    calls = max_depth = 0;
    printf("fib(10) = %d: %d calls, deepest nesting %d frames\n", fib(10), calls, max_depth);
    /* stack use = frames x frame size: with 16-byte frames */
    printf("fact(100) needs %d frames = %d bytes of stack at 16 bytes per frame\n", 100, 100 * 16);
    printf("an 8 MB stack holds about %d such frames\n", 8 * 1024 * 1024 / 16);
    return 0;
}

fact(5) = 120: 5 calls, deepest nesting 5 frames
fib(5) = 5: 15 calls, deepest nesting 5 frames
fib(10) = 55: 177 calls, deepest nesting 10 frames
fact(100) needs 100 frames = 1600 bytes of stack at 16 bytes per frame
an 8 MB stack holds about 524288 such frames

Cheat box

Traps and GATE patterns

Connections

The software view of the same mechanism, with a C program's call stack, is in recursion and the call stack and parameter passing. The frame-relative access to arguments and locals is displacement addressing. An interrupt pushes the PC just as CALL does. CALL and RET are ordinary instructions of the ISA executed in the instruction cycle: CALL's execute phase pushes, then overwrites the PC.

PYQs

Consider a processor with byte-addressable memory.
Assume that all registers, including Program
Counter (PC) and Program Status Word (PSW), are
of size 2 bytes. A stack in the main memory is
implemented from memory location (0100)16 and it
grows upward The stack pointer (SP) points to the
top element of the stack. The current value of SP is
(016E)16. The CALL instruction is of two words, the
first word is the op-code and the second word is the
starting address of the subroutine (one word = 2
bytes). The CALL instruction is implemented as
follows:
• Store the current value of the PC in the stack.
• Store the value of the PSW register in the stack.
• Load the starting address of the subroutine in PC
The content of the PC just before the fetch of a
CALL instruction is (5FA0)16. After execution of the
CALL instruction, the value of the stack pointer is

Assume that EA = (X)+ is the effective address
equal to the contents of location X, with X
incremented by one word length after the
effective address is calculated; EA = -(X) is the
effective address equal to the contents of location
X, with X decremented by one word length before
the effective address is calculated; EA = (X)- is
the effective address equal to the contents of
location X, with X decremented by one word
length after the effective address is calculated.
The format of the instruction is (opcode, source,
destination), which means (destination ← source
op destination). Using X as a stack pointer, which
of the following instructions can pop the top two
elements from the stack, perform the addition
operation and push the result back to the stack.
GATE MCQ – 2008 MCQ (1-MARKS)
GATE MCQ – 2011 MCQ (1-MARKS)
Computer Organization and Architecture

Self-check

Revision card

References