vault

The Value Stack and Frame Evaluation

14 min read

The Value Stack and Frame Evaluation

CPython is a stack machine: its bytecode has no registers, so every operation takes its operands from, and leaves its results on, a per-frame value stack (also called the evaluation or operand stack). LOAD_FAST pushes a local onto it; BINARY_OP pops two and pushes one; RETURN_VALUE pops the result. Crucially, this stack is not a separate object — it shares one contiguous C array, frame->localsplus, with the frame’s fast locals, cell variables, and free variables. The value stack begins immediately after those slots, the interpreter tracks its top with a stack_pointer it keeps in a machine register, and the compiler pre-computes the maximum depth the stack can ever reach (co_stacksize) so the array can be sized exactly once when the frame is created (CPython pycore_interpframe_structs.h, v3.14.0; bytecodes.c).

This note is about the data that flows through the interpreter — where operands physically live and how they move. Its sibling The CPython Evaluation Loop covers the control side: how the loop fetches, decodes, and dispatches each instruction. Read this note to understand localsplus, the stack pointer, stack effects, and a worked a + b * c example; read that one to understand DISPATCH(), the TARGET cases, and the DSL that generates them. The frame as a heap object you can suspend is Stack Frames and the Frame Stack; the immutable bytecode-and-metadata container is Code Objects; the opcodes that push and pop are catalogued in Python Bytecode Instruction Set.

Mental Model: One Array, Two Regions

A Python frame’s variable storage is a single C array of “stack references,” declared as the final, flexible member of the frame struct (pycore_interpframe_structs.h:30–54):

struct _PyInterpreterFrame {
    _PyStackRef f_executable;   /* the code object (or None) */
    struct _PyInterpreterFrame *previous;
    ...
    _Py_CODEUNIT *instr_ptr;    /* the instruction pointer */
    _PyStackRef *stackpointer;  /* top of the value stack */
    ...
    /* Locals and stack */
    _PyStackRef localsplus[1];  /* flexible array: locals THEN value stack */
};

The name localsplus is literal: it is the locals plus the value stack, in one array. The first co_nlocalsplus slots hold named variables (function arguments and local variables, then cell variables, then free variables — in that fixed order). Everything after those slots is the value stack, growing upward as operands are pushed.

flowchart LR
    subgraph LP["frame->localsplus  (one contiguous _PyStackRef array)"]
        direction LR
        L0["[0] local a"]
        L1["[1] local b"]
        L2["[2] local c"]
        SB["Stackbase →<br/>[3] stack slot 0"]
        S1["[4] stack slot 1"]
        S2["[5] stack slot 2<br/>← co_stacksize cap"]
    end
    SP["stack_pointer<br/>(points one past the<br/>top live operand)"] -.-> S1
    note["Stackbase = localsplus + co_nlocalsplus<br/>Value stack lives in [co_nlocalsplus .. co_nlocalsplus+co_stacksize)"]

    classDef loc fill:#2d4a22,color:#fff;
    classDef stk fill:#1f3a5f,color:#fff;
    class L0,L1,L2 loc;
    class SB,S1,S2 stk;

Figure: the localsplus array for a function f(a, b, c). The insight: locals and the value stack are not two data structures — they are two regions of the same array. _PyFrame_Stackbase(frame) returns localsplus + co_nlocalsplus, the first value-stack slot. The stack_pointer register points one slot above the topmost live operand, so “push” writes *stack_pointer++ and “pop” reads *--stack_pointer. The compiler guarantees the stack never grows past co_stacksize slots, so the array is sized once and never reallocated.

This single-array design is a deliberate performance choice. Accessing local variable a is just localsplus[0] — an array index, not a dictionary lookup — which is why LOAD_FAST is “fast” (contrast the dict-based LOAD_NAME/STORE_NAME used at module scope; see Fast Locals and the LOAD_FAST Family). And because the value stack lives in the same allocation as the locals, entering a frame is a single bump of the data-stack pointer rather than separate allocations for locals and stack.

What Lives in localsplus, and Where the Stack Starts

The boundary between the two regions is computed by _PyFrame_Stackbase (pycore_interpframe.h:101):

static inline _PyStackRef *_PyFrame_Stackbase(_PyInterpreterFrame *f) {
    return (f->localsplus + _PyFrame_GetCode(f)->co_nlocalsplus);
}

co_nlocalsplus is a field of the code object, documented in code.h as “number of spaces for holding local, cell, [and free] variables” (code.h:84). It equals co_nlocals + (number of cell vars) + (number of free vars) — the three kinds of named slot that precede the value stack. So for def f(a, b, c): return a + b * c, which has three locals and no cells or free variables, co_nlocalsplus == 3 and the value stack starts at localsplus[3].

Pushing and popping are inline helpers that move stackpointer (pycore_interpframe.h:111–120):

static inline _PyStackRef _PyFrame_StackPop(_PyInterpreterFrame *f) {
    assert(f->stackpointer > f->localsplus + _PyFrame_GetCode(f)->co_nlocalsplus);
    f->stackpointer--;
    return *f->stackpointer;
}
 
static inline void _PyFrame_StackPush(_PyInterpreterFrame *f, _PyStackRef value) {
    *f->stackpointer = value;
    f->stackpointer++;
}

The asserts encode the invariant: pop must not go below Stackbase (a “stack underflow” would mean reading a local as if it were an operand), and the loop maintains Stackbase <= stackpointer <= Stackbase + co_stacksize. In the hot interpreter path the loop does not call these helpers per push/pop; it keeps the stack pointer in a C local named stack_pointer and indexes it directly (stack_pointer[-1], stack_pointer += 1), writing it back into frame->stackpointer only when it must call out to code that could observe the frame. That register-resident stack_pointer is one of the two “register variables” discussed in The CPython Evaluation Loop.

_PyStackRef, not raw PyObject*

A slot holds a _PyStackRef, not a bare PyObject*. This is a tagged reference (introduced as part of the Faster-CPython work) that can encode an ordinary owned reference, a borrowed reference (no refcount bump — used by the 3.14 LOAD_FAST_BORROW family), or a deferred reference. The interpreter manipulates _PyStackRefs with PyStackRef_DUP, PyStackRef_Borrow, PyStackRef_CLOSE, etc., rather than Py_INCREF/Py_DECREF directly. For this note the relevant fact is just that the value stack stores tagged references; the refcounting machinery behind them (deferred and biased reference counting, why borrows are safe) belongs to Deferred Reference Counting and Reference Counting.

Stack Effects: the Contract Each Opcode Declares

Every opcode declares its net effect on the stack as part of its definition in the instruction DSL (Python/bytecodes.c). The notation is (inputs -- outputs): names to the left of -- are popped; names to the right are pushed. The DSL spec states it precisely (interpreter_definition.md:146–148):

“The objects before the -- are the objects on top of the stack at the start of the instruction. Those after the -- are the objects on top of the stack at the end of the instruction.”

Concretely:

        inst(LOAD_CONST, (-- value))        // pops 0, pushes 1
        pure inst(POP_TOP, (value --))      // pops 1, pushes 0
        op(_BINARY_OP, (lhs, rhs -- res))   // pops 2, pushes 1

The net effect of BINARY_OP is therefore −1 (two in, one out). The generator reads these annotations to emit the actual stack_pointer arithmetic. You can see the correspondence in the generated LOAD_FAST, whose DSL effect (-- value) becomes (generated_cases.c.h:9098):

            stack_pointer[0] = value;   // write the pushed item
            stack_pointer += 1;         // net effect +1
            assert(WITHIN_STACK_BOUNDS());

The programmer wrote only value = PyStackRef_DUP(GETLOCAL(oparg));; the stack_pointer[0] = value; stack_pointer += 1; and the bounds assert were generated from the (-- value) annotation. This is the value-stack half of the “single source of truth” story (the control-flow half is in The CPython Evaluation Loop): the same DSL annotation drives both the runtime push and the compile-time depth calculation below.

co_stacksize: How the Maximum Depth Is Computed

Because the value stack shares the frame’s single allocation, the interpreter must know the maximum depth a function’s stack can ever reach before it allocates the frame. That number is co_stacksize, documented as “#entries needed for evaluation stack” (code.h:79). The compiler computes it by abstract interpretation of the control-flow graph: it walks every basic block, applies each instruction’s stack effect, and records the high-water mark. The function is calculate_stackdepth in flowgraph.c (flowgraph.c:809):

        for (int i = 0; i < b->b_iused; i++) {
            cfg_instr *instr = &b->b_instr[i];
            stack_effects effects;
            if (get_stack_effects(instr->i_opcode, instr->i_oparg, 0, &effects) < 0) { ... }
            int new_depth = depth + effects.net;
            if (new_depth < 0) {
                PyErr_Format(PyExc_ValueError, "Invalid CFG, stack underflow");
                goto error;
            }
            maxdepth = Py_MAX(maxdepth, depth);
            ...
            depth = new_depth;
        }
        ...
    stackdepth = maxdepth;

Walking it: starting at the entry block with depth 0, for each instruction it fetches effects.net (the same net push/pop the DSL annotation declares — get_stack_effects is generated from bytecodes.c), updates the running depth, tracks maxdepth, and follows both fall-through and jump targets through the CFG. A depth < 0 is rejected as “stack underflow” — a structurally impossible program. The final maxdepth becomes co_stacksize.

This is where stack effects are machine-checked: the same per-opcode net effect that the generator uses to emit runtime stack_pointer += N is the one the compiler uses to size the stack. If an opcode’s declared effect were wrong, either the compiler would compute a too-small co_stacksize (and the interpreter would scribble past the stack region) or the runtime push count would mismatch the compile-time reservation. Driving both from one DSL annotation guarantees they agree by construction. The interpreter even re-checks at runtime in debug builds via WITHIN_STACK_BOUNDS(), which asserts 0 <= STACK_LEVEL() <= STACK_SIZE() where STACK_SIZE() is co_stacksize (ceval_macros.h:209–213).

The total frame allocation is co_framesize words, of which co_nlocalsplus + co_stacksize is the localsplus array and the remainder is the fixed _PyInterpreterFrame header (the FRAME_SPECIALS_SIZE) (pycore_interpframe.h:122–131). Frames are carved out of a per-thread data stack by bumping a pointer by co_framesize, which is why a Python call is cheap: no malloc, just a pointer bump into pre-reserved space.

Worked Example: Evaluating a + b * c

Consider the function, disassembled on the system’s CPython 3.14.5:

def f(a, b, c):
    return a + b * c
RESUME                   0
LOAD_FAST_BORROW_LOAD_FAST_BORROW 1 (a, b)
LOAD_FAST_BORROW         2 (c)
BINARY_OP                5 (*)
BINARY_OP                0 (+)
RETURN_VALUE

co_stacksize for this function is 3 — the compiler determined the stack never holds more than three operands at once. Two 3.14-specific details are worth pausing on rather than idealizing away:

  • LOAD_FAST_BORROW_LOAD_FAST_BORROW is a fused opcode: one instruction that loads two locals, with the two local indices packed into one oparg’s nibbles (oparg >> 4 is the first, oparg & 15 the second; here oparg 1 means indices 0 and 1, i.e. a and b) (bytecodes.c:299). Fusing common pairs into one opcode saves a dispatch. Its stack effect is (-- value1, value2): net +2.
  • _BORROW means the loaded reference is borrowed — pushed as a _PyStackRef that does not bump the refcount, because the operand is only consumed within this expression and the local keeps the object alive. This is a 3.14 refinement that avoids redundant incref/decref pairs.

Here is the value stack at each step (showing only the value-stack region, with Stackbase at the bottom; co_stacksize = 3 so the region is three slots):

After RESUME                              (empty)              depth 0
LOAD_FAST_BORROW_LOAD_FAST_BORROW 1  →    [ a, b ]             depth 2   (net +2)
LOAD_FAST_BORROW 2 (c)               →    [ a, b, c ]          depth 3   (net +1)  ← high-water mark = co_stacksize
BINARY_OP 5 (*)   pops b,c pushes b*c →   [ a, (b*c) ]         depth 2   (net -1)
BINARY_OP 0 (+)   pops a,(b*c) pushes  →  [ (a+(b*c)) ]        depth 1   (net -1)
RETURN_VALUE      pops result          →  (empty), returns     depth 0   (net -1)

Reading the column of depths — 0, 2, 3, 2, 1, 0 — the maximum is 3, exactly co_stacksize. This is the high-water mark calculate_stackdepth would have found by summing net stack effects along this single straight-line path. Operator precedence (* binds tighter than +) is already baked into the order of the opcodes by the compiler: b * c is evaluated first and its result sits on the stack while a waits beneath it, then the + consumes both. The stack machine needs no precedence logic at runtime; precedence became instruction order at compile time.

You can watch the generated BINARY_OP move the pointer. Its _BINARY_OP body computes res, then (generated_cases.c.h:67–79):

                res = PyStackRef_FromPyObjectSteal(res_o);
                ...
                stack_pointer[-2] = lhs;   /* overwrite the lower of the two operands with res */
                PyStackRef_CLOSE(tmp);     /* release the consumed inputs */
                ...
                stack_pointer += -1;       /* net effect: 2 popped, 1 pushed = -1 */
                assert(WITHIN_STACK_BOUNDS());

It writes the result into stack_pointer[-2] (the lower operand’s slot), closes the two inputs, and adjusts stack_pointer by −1 — the precise materialization of the (lhs, rhs -- res) stack effect.

Failure Modes and Common Misunderstandings

“The value stack is a Python list / a separate object.” No. It is a region of the frame’s localsplus C array, holding _PyStackRefs. There is no PyListObject involved and no per-push allocation.

“Locals and the value stack are separate allocations.” No — they are one array, locals first ([0 .. co_nlocalsplus)) then the value stack ([co_nlocalsplus .. co_nlocalsplus + co_stacksize)). This is why _PyFrame_Stackbase is just pointer arithmetic.

“co_stacksize is the current depth.” No — it is the compile-time-computed maximum depth, used to size the array. The current depth is stack_pointer - Stackbase (the STACK_LEVEL() macro).

“Stack overflow grows the stack.” The value stack never grows past co_stacksize; the compiler proved it cannot. What people call a Python “stack overflow” (RecursionError) is the call stack — too many frames — not the value stack inside one frame. The value stack is fixed-size per frame by construction.

Borrowed references and the _BORROW opcodes. Reading old (pre-3.14) disassembly you would see LOAD_FAST/LOAD_FAST; in 3.14 you will often see LOAD_FAST_BORROW and fused LOAD_FAST_BORROW_LOAD_FAST_BORROW. These are the compiler choosing borrowed loads when it can prove the local outlives the operand, eliminating refcount churn. Semantically the stack effect is identical (a value is pushed); the difference is whether the pushed _PyStackRef owns a reference.

Alternatives: Stack Machine vs Register Machine

CPython is a stack virtual machine; an operation’s operands are implicit (they are “on top of the stack”). The main alternative is a register VM (e.g. Lua 5, Dalvik), where operands are explicit numbered slots and an ADD r3, r1, r2 instruction names its inputs and output. Register VMs tend to need fewer, larger instructions (less push/pop traffic) but more complex compilers; stack VMs have simpler, denser bytecode and a trivial code generator. CPython has stayed a stack machine; the Python Bytecode Instruction Set reflects that (almost every opcode is described purely by its stack effect). PyPy, GraalPy, and other implementations make different choices — CPython vs PyPy and Alternative Implementations.

Production Notes

The value stack rarely surfaces directly in application code, but its shape explains real behavior. co_stacksize (visible as f.__code__.co_stacksize) is a rough proxy for expression complexity within a function and bounds the per-frame stack memory. Deeply nested expressions raise co_stacksize; the data-stack reservation per call grows with it. Tools that reconstruct local state from a running or crashed process — py-spy, faulthandler, the new in-process remote debugging (PEP 768) — must know the localsplus layout (co_nlocalsplus locals followed by the value stack) to read locals and the operand stack out of a frame; the layout described here is exactly what those tools encode. And the stack-effect discipline is why hand-written bytecode (via types.CodeType or ctypes shenanigans) is dangerous: get an opcode’s net effect wrong relative to co_stacksize and the interpreter will read or write outside the value-stack region, corrupting the frame.

See Also

Graph View

Backlinks