Skip to content
Tutorials Center
My learning

Topics

Lesson 41 of 61 ยท Code Generation and Runtimes

Runtime Environments: Stack, Heap and Frames

Learn how compiled programs use memory at run time: activation records, call stacks, calling conventions, static links and closures, with a simulation.

Everything so far happened at compile time. A compiler also has to plan what the program will look like at run time: where each variable lives, how a function call passes arguments and returns a result, and how a nested function reaches the variables of the function around it. The set of conventions that answers those questions is the runtime environment. The code generator must follow it exactly, or a call would clobber the caller's data.

This lesson covers the layout of memory, the activation record (stack frame) that every call creates, calling conventions, the two kinds of links between frames, and closures, which are the reason some data must live on the heap. You will run two simulations of a call stack, one that prints real-looking frames and one that follows access links.

The storage layout of a running program

A typical process has four regions:

Region Holds Lifetime
Code (text) Machine instructions, constants Whole run
Static data Global variables, string literals Whole run, size known at compile time
Stack Frames of active function calls Allocated at call, freed at return
Heap Objects created on demand (new, malloc, list literals) Until freed or collected

The stack and the heap usually sit at opposite ends of the free address space and grow toward each other. Stack memory is cheap: allocating a frame is a single subtraction on the stack pointer. Heap memory is flexible but costs more, since an allocator must find a free block and something must decide when it can be reused (garbage collection is one answer).

Activation records

Each time a function is called, the runtime creates an activation record (also called a stack frame) for that one activation. Because the lifetimes of calls are properly nested (the last function called is the first to return), a stack is the perfect structure. Recursion works because every call gets its own frame with its own copy of the parameters and locals.

A typical frame contains:

  • the arguments passed in (some may travel in registers instead),
  • the return address: where to resume in the caller,
  • the saved frame pointer: the caller's frame pointer, restored on return; this is also called the dynamic link, because it points to the frame of whoever called us at run time,
  • saved registers that the callee uses but must restore,
  • local variables and temporaries, including values that register allocation had to spill,
  • the return value slot, unless the value is returned in a register.
flowchart TD
    subgraph high["higher addresses"]
        M["main's frame<br/>locals, saved fp, return address"]
    end
    M --> F1["fact(4) frame<br/>n = 4, saved fp, return address"]
    F1 --> F2["fact(3) frame<br/>n = 3, saved fp, return address"]
    F2 --> F3["fact(2) frame, the newest<br/>stack pointer points here"]

Each call pushes a frame below the caller's. The dynamic link of every frame points to the frame above it.

Compiled code addresses variables as fixed offsets from the frame pointer: the first parameter might be at fp + 16, a local at fp - 8. The offsets are decided at compile time, so there is no name lookup at run time. That is one reason compiled languages are fast.

Calling conventions

A calling convention is the contract between caller and callee. It settles where arguments go (the first few in registers, the rest on the stack), where the return value comes back, which registers a callee may freely overwrite (caller-saved) and which it must restore before returning (callee-saved), and who removes the arguments from the stack. Conventions differ between platforms: the System V convention on Linux and macOS uses rdi, rsi, rdx, rcx, r8, r9 for the first six integer arguments on x86-64, while Windows uses rcx, rdx, r8, r9. Code from separate compilers can only be linked together because they obey the same convention.

A call sequence breaks down into four steps. The caller evaluates the arguments and places them. The call instruction pushes the return address and jumps. The callee's prologue saves the old frame pointer, sets the new one and reserves space for locals. When the function finishes, the epilogue restores the registers and the frame pointer, and the return instruction jumps back.

A simulated call stack

The program below does not execute machine code. It runs an ordinary recursive factorial in Python, but each call also builds a model frame with an address range, a return address and a dynamic link, on a model stack that grows downward from address 1000. The log shows the calls and returns, and a snapshot is drawn when the recursion is deepest.

Python Frames, return addresses and dynamic links

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the log first: it shows the nesting, with each return undoing one call. Then read the snapshot from the top. The newest frame sits at the lowest addresses (981 to 984) and the oldest, main, at the highest (997 to 999). Four frames of fact hold four different values of n at the same time, which is exactly what recursion needs. Each fact frame knows its caller through the saved frame pointer and knows where to resume through the return address. When fact(1) returns, its frame vanishes, and the space can be reused by the next call. Notice the stack never needs a free operation.

Languages that allow nested functions (Pascal, Python, JavaScript, Go closures, Swift) have a second problem. A function inner defined inside middle can use the variables of middle, and of the function around that. The dynamic link does not help: the function that called inner is not necessarily the function where inner was written. The compiler adds a static link (also called an access link) to each frame, pointing to the frame of the function's lexically enclosing function.

flowchart LR
    I["inner frame<br/>no locals"] -- "static link" --> M["middle frame<br/>y = 20"]
    M -- "static link" --> O["outer frame<br/>x = 10"]

To read x from inside inner, follow two static links. The number of hops is known at compile time from the nesting depth.

The compiler knows how many levels separate the use from the declaration, so it can generate "follow the static link twice, then read the variable at offset 0". An alternative is a display: an array indexed by nesting depth that holds a pointer to the current frame at each depth, which gives constant-time access instead of a chain walk. Languages without nested functions, such as C, need neither.

Closures and the heap

If a nested function can only be called while its enclosing function is active, frames on the stack are enough. But many languages let a function escape: it can be returned or stored. Then the frame of the enclosing function would be popped from the stack while the inner function still needs its variables. The language implementation solves this by pairing the code with its environment into a closure and keeping that environment on the heap (or at least copying the captured variables there).

The second simulation models static links with Env objects and Closure values. Part one follows two static links. Part two builds a counter factory, where the environment must survive after make_counter has returned.

Python Static links and closures that outlive their frame

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In part one inner finds y one static link up and x two links up. In part two, the two counters keep independent state ([1, 2, 3] and [101, 102]) because each call of make_counter created its own environment, and each tick closure points to one of them. The "heap (captured)" label is the key point: a variable that a closure captures cannot live in a stack frame that will disappear. Real compilers run an escape analysis to find which variables actually need to move to the heap, and keep the rest on the stack. A closure that never escapes, such as a callback passed down to a sort function, can often be as cheap as an ordinary call.

Activation trees

Every call of a function is one activation. If you draw each activation as a node and connect it to the activations it calls, you get the activation tree of a program run. It has three properties that explain why the stack is the right structure:

  • The root is the activation of main (or the program's entry point).
  • A node's children appear left to right in the order the calls were made, and a child finishes before its parent does.
  • The control stack at any moment holds exactly the path from the root to the activation that is running now. Entering a call pushes a node; returning pops it.

Because lifetimes are nested like this, the stack depth is the height of the tree at that point, not the number of nodes. A recursive function such as fib makes a big tree (9 activations for fib(4)) but needs only as many frames as the tree is tall. The program records the tree for fib(4) and prints the control stack when the deepest activation is running.

Python The activation tree and control stack of fib(4)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The tree shows the repeated work in naive fib (the leaf fib(1) is computed three times). The stack line shows the other lesson: when fib(1) runs at the bottom-left, only four frames exist. When the tree is explored further to the right, the frames of finished activations were already popped and the space is reused. The second half of the program shows what happens if you refuse to use a frame per activation: the factorial keeps its n in one fixed slot (as early languages did with static allocation), the inner calls overwrite it, and the answer is 1 instead of 120.

Static, stack and heap allocation compared

A compiler has three strategies for deciding where a variable lives, and most programs use all three:

Static allocation Stack allocation Heap allocation
Decided at compile time at call time at run time, on request
Address fixed for the whole run relative to the frame pointer returned by the allocator
Size must be known at compile time when the function is called (fixed per function; dynamic arrays are the exception) not until the request
Lifetime the whole program until the function returns until freed, or until a collector finds it unreachable
Recursion not supported: all activations would share one copy supported: one frame per activation works, since objects are independent of calls
Cost none at run time one pointer adjustment allocator search, possible fragmentation, GC
Examples globals, static variables, string literals, constants locals, parameters, return addresses, saved registers new, malloc, lists and dictionaries, closures that escape

The choice follows from one question: can the compiler prove the lifetime? If the value lives as long as the program, it goes in static storage. If it dies when the function returns (the nesting rule from the activation tree), it goes on the stack. If it must survive the function that created it or its size is only known later, it goes on the heap, and something (you, a reference count, an ownership rule or a garbage collector) must reclaim it. Early Fortran used only static allocation, which is why it had no recursion; ALGOL introduced the stack; Lisp needed the heap.

Stack overflow and heap management

Because the stack has a fixed maximum size (often 1 to 8 MB for the main thread), unbounded recursion eventually runs out of space and the runtime reports a stack overflow. Tail-call elimination is one way to avoid it. The heap has its own failure modes: leaks when memory is never released, and dangling pointers when it is released too early. Languages answer with manual free, reference counting, ownership rules, or a collector. Those strategies are the next topics in this chapter.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why is a stack the right data structure for activation records?

    Because calls nest, the frames are created and destroyed in last-in, first-out order, so allocation is just moving the stack pointer.
  2. 2. What is the difference between the dynamic link and the static link?

    The dynamic link reflects who called us at run time; the static link reflects where the function was written, which is what non-local variable access needs.
  3. 3. Why must a closure's captured variables sometimes live on the heap?

    An escaping closure outlives the activation that defined its variables, so those variables need storage whose lifetime is not tied to the stack frame.
  4. 4. What does a calling convention specify?

    Caller and callee, possibly compiled by different compilers, must agree on registers and stack usage for calls to work.

Summary

  • The activation tree of a run shows why a stack suffices (the control stack is the root-to-active path), and static, stack and heap allocation differ in who decides lifetime and when.
  • A running program uses code, static data, a stack for call frames and a heap for dynamically allocated data.
  • Each call creates an activation record with arguments, return address, saved frame pointer (dynamic link), saved registers and locals; compiled code reaches them at fixed offsets from the frame pointer.
  • A calling convention fixes how arguments, results and registers are used so separately compiled code can interoperate.
  • Nested functions need static links (or a display) to reach variables of enclosing scopes.
  • Closures that escape their defining call need their environment on the heap; escape analysis keeps the other cases cheap.

Next: Code Generation and Instruction Selection