How an Interpreter Lays Out a Stack Frame

A call instruction in bytecode has to produce something the callee can run against: a region of memory holding the callee’s arguments, its local variables, its temporaries, and enough bookkeeping to return. In a native calling convention that region is built partly by the caller and partly by the callee, with the register file holding the first several arguments. An interpreter has no such division, because there is no register file to pass arguments in. Everything goes in memory, and the layout of that memory is fixed by the runtime rather than negotiated per call.

One block per activation

The simplest and most common design allocates the entire frame at call time as a single contiguous block, sized at bytecode compile time. The method header records two maxima: the number of local variable slots and the maximum depth the operand stack reaches. The frame is the sum of the header, the locals array, and the operand stack, padded to alignment.

typedef struct Frame {
    uint8_t      *return_pc;   /* resume point in the caller's code */
    struct Frame *caller;      /* frame pointer chain */
    Value        *base;        /* first local slot; also the frame's identity */
    uint32_t      n_locals;
} Frame;

/* A frame is one allocation: header, locals, operand stack. */
static Frame *push_frame(Thread *t, uint32_t n_locals, uint32_t max_stack,
                         uint8_t *return_pc)
{
    size_t bytes = sizeof(Frame)
                 + n_locals * sizeof(Value)
                 + max_stack * sizeof(Value);
    bytes = (bytes + 15) & ~(size_t)15;   /* keep 16-byte alignment */
    if (t->stack_top + bytes > t->stack_limit) grow_or_throw(t);
    Frame *f = (Frame *)t->stack_top;
    f->return_pc = return_pc;
    f->caller    = t->current;
    f->base      = (Value *)(f + 1);
    f->n_locals  = n_locals;
    t->current   = f;
    t->stack_top = (uint8_t *)f + bytes;
    return f;
}

Allocating one block rather than three has consequences. The stack pointer moves once per call instead of three times. The frame’s extent is known from a single pointer, which makes stack overflow detection a single comparison against a limit rather than a walk. And the frame can be freed by restoring the stack pointer to the value it had before the call, with no per-field teardown. The cost is internal fragmentation: a method that declares 200 locals but uses three pays for 200 slots on every activation.

The alternative, allocating locals and operand stack separately, buys nothing in an interpreter that cannot move frames anyway, and it complicates overflow checking because two allocations can fail independently. It is used where frames are heap-allocated objects, as in implementations that need to suspend and resume them; that design is discussed in resumable frames for generators and coroutines.

Locals first, then the operand stack

Putting the locals at the low end of the frame and the operand stack immediately after them is the JVM’s arrangement, and the reason is addressing. The iload family of instructions encodes a local index as a single unsigned byte, with a wide form for larger indices. The operand stack, by contrast, is addressed implicitly: an instruction pops whatever is on top. Since only the locals need explicit addresses, they get the low, densely numbered slots.

The consequence is that the operand stack’s depth at any point is not known statically at every instruction; only its maximum is. The interpreter keeps a stack pointer that starts at the first slot after the locals and moves with each push and pop. That pointer lives in a machine register for the duration of the dispatch loop, which is the main reason a single-function dispatch loop outperforms a recursive evaluator.

Some formats invert the order. In Lua’s implementation the stack grows upward from the frame base, and registers are addressed as offsets from a base pointer that is reset at each call. Because Lua’s bytecode names registers explicitly, the “locals” and the “operand stack” are the same array: a register that holds a local early in the function may hold a temporary later, with liveness determining reuse. That is the register-machine view of a frame, and it collapses two regions into one.

Arguments arrive in the callee’s local slots

There is no separate argument area. The caller pushes arguments onto its own operand stack, in order, and the call instruction treats the top n slots as the callee’s first n locals. The new frame is placed so that those slots become the low end of the callee’s local array, either by making the callee’s base pointer point into the caller’s stack or by copying the values down into a fresh frame.

The copy-free version is what a contiguous-stack interpreter does. The caller’s operand stack and the callee’s locals overlap in the same address range, so a call costs a pointer adjustment plus the header write. This is why an interpreter can support deep recursion cheaply: the per-call cost is a handful of stores, not an allocation. It also means the argument slots are already in place when the callee starts, so the callee’s prologue does not have to move them.

The overlap has a sharp edge. If the callee’s declared local count is smaller than the number of arguments passed, the extra argument slots lie beyond the callee’s locals, inside what the callee considers its operand stack. The JVM forbids this at verification time for methods called through invokestatic and similar, because the descriptor fixes the argument count exactly. Dynamically typed formats instead let the callee decide: it receives the argument count, so it can read the extra slots as an argument list, of the kind a vararg parameter or a rest parameter names, or ignore them. Languages that report an arity error instead check the count in the call sequence before entering the frame.

The header holds what the code cannot

The header exists because some state cannot be derived from the frame’s contents. The return address is the clearest: the interpreter must know where in the caller’s code to resume, and that is a byte offset into the caller’s code array. The caller’s frame pointer is the second: unwinding and debugging both need to walk the chain, and the chain cannot be reconstructed from the locals array alone.

Most interpreters also store the callee’s code pointer, since a frame can be described without its owner. Some store a reference to the function object, needed for closures and for reflection over the activation. A few store a pointer to the exception handler table for the frame, so unwinding does not have to re-read the method metadata.

Header size matters more than it looks. At eight bytes per slot, a five-word header is 40 bytes per call, which is comparable to the locals of a small method. Engines that care about call overhead pack the header into 16 or 24 bytes, using a 32-bit code offset instead of a pointer and a 32-bit frame-pointer delta instead of an absolute pointer, so the frame can be relocated. The trade is an extra addition on every frame walk versus a smaller stack.

Alignment, overflow, and the shadow region

Two mechanical constraints shape the layout. The first is alignment: a Value slot holding a double or a pointer must be naturally aligned, so the header is padded to the slot size and the whole frame to 8 or 16 bytes. Misaligned frames on x86-64 cost little for scalar loads but break vector loads, and a runtime that stores Value in a 16-byte union will align frames to 16.

The second is overflow. Because frames are contiguous and grow downward or upward together, a stack overflow is detected by comparing the prospective top against a guard limit, not by catching a fault. The guard is placed so that the runtime can throw a catchable error before touching unmapped memory. Some implementations instead map a guard page at the end of the stack and let the resulting fault be translated into the language’s stack overflow error, which avoids a comparison per call but requires the handler to distinguish a genuine overflow from a wild pointer.

Above the frames there is usually a shadow region: a fixed area reserved for the interpreter’s own C-level calls. When an opcode needs to call into a runtime helper, the helper runs on the machine stack, but any arguments it needs from the frame must be copied out, because the helper may trigger a garbage collection that moves or inspects objects. The shadow region gives the helper a place to keep those copies where the collector can see them. Its size is bounded by the deepest helper call the interpreter can make, and it is a frequent source of subtle bugs when a new opcode calls a helper that needs one more slot than the region provides.

The metadata that lets an unwinder or debugger interpret this layout, mapping a code offset to the set of live slots, is a separate structure; see debug metadata and single stepping. What the frame layout fixes is simpler: a frame is one allocation whose size the compiler computed, whose first slots are the arguments, and whose header is the only thing that survives after the callee’s code finishes.