Bytecode Compilation

Bytecode compilation is the stage that turns a validated Abstract Syntax Tree (AST) — together with the symbol tables that classify every name — into a PyCodeObject: an immutable object whose co_code field is the actual byte string the interpreter executes. Since the rewrite that landed in CPython 3.12, this is not a single translate-the-tree step. It is a small pipeline: the AST is first lowered into a flat sequence of pseudo-instructions, that sequence is reshaped into a control-flow graph (CFG) of basic blocks, the CFG is optimized and then linearized back into a sequence, and only then is that sequence assembled into real bytecode with jump offsets, an exception table, and a line table. The whole thing is driven from Python/compile.c, with code generation in codegen.c, the graph in flowgraph.c, and final assembly in assemble.c. The canonical description is InternalDocs/compiler.md: “the result of _PyAST_Compile() is a PyCodeObject … and with that you now have executable Python bytecode!”

Why a Pipeline, Not a Single Pass

The naive way to compile an AST is to recurse over the tree emitting bytecode as you go. CPython did roughly that for years, but it created a chicken-and-egg problem: jumps. When you compile an if statement you need to emit a conditional jump past the body, but you do not yet know how many bytes the body will occupy, so you cannot fill in the jump target. Worse, optimizing the result (removing dead code, threading jumps) is awkward when “the program” is already a flat byte string with hard-coded offsets.

The 3.12 architecture solves this by deferring concretization. Code generation emits pseudo-instructions — instruction-like records that carry symbolic jump labels instead of byte offsets, and may stand for several real opcodes. As InternalDocs/compiler.md puts it, these pseudo-instructions “are more abstract, and are resolved later into actual bytecode.” Only after the program has been shaped into a graph, optimized, and laid out linearly do labels become numeric offsets and pseudo-instructions become real opcodes. This staging is what makes the optimizer tractable and the jump-resolution exact.

Mental Model: AST → Sequence → Graph → Sequence → Bytecode

flowchart TD
    AST["AST + Symbol Tables"] -->|"compiler_codegen()<br/>in compile.c"| GEN["codegen.c walks the tree<br/>codegen_visit_stmt / codegen_visit_expr<br/>ADDOP macros emit pseudo-instructions"]
    GEN --> SEQ1["Instruction sequence<br/>(_PyInstructionSequence)<br/>flat list, symbolic labels"]
    SEQ1 -->|"_PyCfg_FromInstructionSequence()"| CFG["Control-flow graph<br/>basic blocks + edges<br/>(flowgraph.c)"]
    CFG -->|"_PyCfg_OptimizeCodeUnit()"| OPT["Optimized CFG<br/>(peephole, dead code, jump threading)<br/>-> Compiler Optimization Passes"]
    OPT -->|"_PyCfg_OptimizedCfgToInstructionSequence()"| SEQ2["Optimized instruction sequence<br/>+ stackdepth, nlocalsplus"]
    SEQ2 -->|"_PyAssemble_MakeCodeObject()<br/>assemble.c"| CO["PyCodeObject<br/>co_code + exception table + line table<br/>-> Code Objects"]

Figure: the bytecode-compilation pipeline as of CPython 3.14.5. The insight is that bytecode is produced twice-removed from the AST — first as an abstract sequence, then as a graph the optimizer can manipulate, and only at the very end as the concrete co_code byte string. The two boxes pointing at sibling notes mark deliberate boundaries: this note covers the spine; the optimization mechanics and the code-object layout live elsewhere.

Stage 1: Code Generation to Pseudo-Instructions

Compilation is initiated by _PyAST_Compile() in compile.c, which first builds the symbol table (see Symbol Table Construction) and then calls compiler_codegen(). That function dispatches by module kind into the code-generation entry points implemented in codegen.c — whose own header comment states: “This file implements the compiler’s code generation stage, which produces a sequence of pseudo-instructions from an AST. The primary entry point is _PyCodegen_Module() for modules, and _PyCodegen_Expression() for expressions.”

Code generation is a recursive descent over the AST. For each node type there is a visitor — codegen_visit_stmt(), codegen_visit_expr(), and many specialized helpers (codegen_with, codegen_try_except, codegen_async_for, …). The VISIT family of macros drives the recursion; the ADDOP family appends pseudo-instructions to the current block’s sequence. InternalDocs/compiler.md lists the emission macros — ADDOP, ADDOP_I (with an integer arg), ADDOP_O (with an object arg), ADDOP_NAME, ADDOP_LOAD_CONST, ADDOP_JUMP (whose target is a label, not an offset) — and these are exactly what you see in codegen.c.

The hinge between this stage and the symbol table is name resolution. The helper codegen_nameop() reads the scope the symbol-table pass computed and picks the opcode accordingly. In v3.14.5 it calls _PyST_GetScope() to fetch the scope value, then _PyCompile_ResolveNameop() to map it to an “optype,” then emits:

    int scope = _PyST_GetScope(SYMTABLE_ENTRY(c), mangled);
    /* ... */
    switch (optype) {
    case COMPILE_OP_DEREF:   /* scope FREE or CELL */
        switch (ctx) {
        case Load:  op = LOAD_DEREF;  break;   /* (class-scope variants aside) */
        case Store: op = STORE_DEREF; break;
        case Del:   op = DELETE_DEREF; break;
        } break;
    case COMPILE_OP_FAST:    /* scope LOCAL */
        switch (ctx) {
        case Load:  op = LOAD_FAST;  break;
        case Store: op = STORE_FAST; break;
        case Del:   op = DELETE_FAST; break;
        } break;
    case COMPILE_OP_GLOBAL:  /* scope GLOBAL_EXPLICIT / GLOBAL_IMPLICIT */
        switch (ctx) {
        case Load:  op = LOAD_GLOBAL;  break;
        case Store: op = STORE_GLOBAL; break;
        case Del:   op = DELETE_GLOBAL; break;
        } break;
    case COMPILE_OP_NAME:    /* module / class scope */
        switch (ctx) {
        case Load:  op = LOAD_NAME;  break;
        case Store: op = STORE_NAME; break;
        case Del:   op = DELETE_NAME; break;
        } break;
    }

Reading it: ctx is the expression context the AST attaches to a Name node — Load, Store, or Del. The pair (scope, ctx) fully determines the opcode. A LOCAL read becomes LOAD_FAST, which the dis docs define as “Pushes a reference to the local co_varnames[var_num] onto the stack.” A FREE/CELL read becomes LOAD_DEREF (“Loads the cell contained in slot i of the ‘fast locals’ storage. Pushes a reference to the object the cell contains on the stack”). A global becomes LOAD_GLOBAL. Everything else (module top level, class body) becomes LOAD_NAME (“looked up within the locals, then the globals, then the builtins”). This is why the symbol table must run first: the opcode is chosen here, at compile time, from a scope decided earlier. (The real codegen_nameop has extra branches for class-scope variants like LOAD_FROM_DICT_OR_DEREF; those are class-body subtleties cross-linked from Symbol Table Construction, elided above for clarity.)

The output of this stage is an _PyInstructionSequence — the structure whose own source file describes it as “a data structure representing a sequence of instructions, which is used by different parts of the compilation pipeline.” It is a flat, growable array of _PyInstruction records plus a labels map. Jumps point at labels; nothing is a byte offset yet.

Stage 2: Building the Control-Flow Graph

Once the instruction sequence exists, optimize_and_assemble_code_unit() in compile.c converts it into a CFG by calling _PyCfg_FromInstructionSequence(). InternalDocs/compiler.md gives the precise definition of what a CFG is and, crucially, what its nodes are:

A control flow graph (often referenced by its acronym, CFG) is a directed graph that models the flow of a program … a node of a CFG is not an individual bytecode instruction, but instead represents a sequence of bytecode instructions that always execute sequentially. Each node is called a basic block.

A basic block is a maximal run of instructions with one entry and one exit: control enters at the top and leaves only at the bottom, with no jumps into the middle and no jumps out except the last instruction. The structural rule that the documentation states is the reason jumps and blocks are co-designed:

If some bytecode instruction a needs to jump to some other bytecode instruction b, then a must occur at the end of its basic block, and b must occur at the start of its basic block.

In flowgraph.c, each basicblock carries a b_label (the jump-target label if any other block jumps to it, -1 otherwise) and a list of cfg_instr records; an instruction that is a jump stores an i_target pointer to the destination block. _PyCfg_FromInstructionSequence() builds the graph by scanning the flat sequence and starting a new block at every label and immediately after every jump or return — exactly the points the single-entry/single-exit rule requires. The graph form is what makes whole-program reasoning possible: you can ask “is this block reachable?”, “do these two blocks always execute in sequence?”, and “where does this jump actually go?” without parsing a byte string.

The graph also enables a computation that the flat sequence could not support cleanly: the maximum value-stack depth. CPython frames carry a fixed-size operand stack (see The Value Stack and Frame Evaluation), and the runtime must know its high-water mark to allocate the frame. calculate_stackdepth() in flowgraph.c walks the blocks in a worklist-style traversal, propagating the stack depth on entry to each block and adding each instruction’s stack effect (how many values it pushes minus how many it pops, from get_stack_effects()), tracking the running maxdepth. Because a basic block always executes top-to-bottom, the depth entering a block is well-defined; because the graph records every edge, the traversal reaches every reachable block. If two predecessors disagree on the entry depth, that is a compiler bug and CPython raises ValueError: Invalid CFG, inconsistent stackdepth — the graph structure is what makes that consistency check possible at all.

Stage 3: Optimization (Deferred)

With the CFG in hand, _PyCfg_OptimizeCodeUnit() runs the optimization passes — InternalDocs/compiler.md: “_PyCfg_OptimizeCodeUnit() applies various peephole optimizations,” all implemented in flowgraph.c. These include constant folding, dead-code elimination, and jump threading. The mechanism and catalogue of these passes is deliberately out of scope for this note — it is covered in Compiler Optimization Passes. What matters for the pipeline story is only that optimization operates on the graph, not on bytecode, and that afterward _PyCfg_OptimizedCfgToInstructionSequence() “converts the optimized CFG back into an instruction sequence,” also computing the maximum stack depth and the count of locals-plus-cells the frame will need (stackdepth, nlocalsplus in the v3.14.5 source).

Stage 4: Assembly into Bytecode

The final stage turns the optimized, linearized instruction sequence into the real co_code byte string and the metadata tables. InternalDocs/compiler.md describes the three jobs:

transforming pseudo instructions into actual instructions, converting jump targets from logical labels to relative offsets … construction of the exception table and locations table.

This is _PyAssemble_MakeCodeObject() in assemble.c. The v3.14.5 driver in compile.c shows the whole tail of the pipeline in one function:

    g = _PyCfg_FromInstructionSequence(u->u_instr_sequence);          /* sequence -> CFG */
    /* ... compute nlocals, nparams ... */
    _PyCfg_OptimizeCodeUnit(g, consts, const_cache, nlocals,          /* optimize the graph */
                            nparams, u->u_metadata.u_firstlineno);
    _PyCfg_OptimizedCfgToInstructionSequence(g, &u->u_metadata,       /* CFG -> sequence again */
                            code_flags, &stackdepth, &nlocalsplus,
                            &optimized_instrs);
    co = _PyAssemble_MakeCodeObject(&u->u_metadata, const_cache,      /* sequence -> PyCodeObject */
                            consts, stackdepth, &optimized_instrs,
                            nlocalsplus, code_flags, filename);

The assembler now knows the final linear order of instructions, so it can lay out bytes and compute jump offsets. Each instruction occupies a fixed-size code unit; the dis docs note that since 3.6 CPython uses “2 bytes for each instruction” (a one-byte opcode plus a one-byte argument), and since 3.11 some opcodes are followed by inline CACHE units that “mark extra space for the interpreter to cache useful data directly in the bytecode itself” (used by the specializing interpreter).

EXTENDED_ARG: arguments larger than one byte

The fixed one-byte argument creates an obvious problem: what about a jump target or a constant index above 255? The answer is the EXTENDED_ARG opcode, defined in the dis docs as:

Prefixes any opcode which has an argument too big to fit into the default one byte. ext holds an additional byte which act as higher bits in the argument. For each opcode, at most three prefixal EXTENDED_ARG are allowed, forming an argument from two-byte to four-byte.

The assembler emits these mechanically based on how many bytes the argument needs. The byte-exact emission in write_instr() (in assemble.c, v3.14.5) is a fall-through switch on the instruction’s length minus its cache slots:

    switch (ilen - caches) {
        case 4:
            codestr->op.code = EXTENDED_ARG;
            codestr->op.arg = (oparg >> 24) & 0xFF;   /* bits 31..24 */
            codestr++;
            _Py_FALLTHROUGH;
        case 3:
            codestr->op.code = EXTENDED_ARG;
            codestr->op.arg = (oparg >> 16) & 0xFF;   /* bits 23..16 */
            codestr++;
            _Py_FALLTHROUGH;
        case 2:
            codestr->op.code = EXTENDED_ARG;
            codestr->op.arg = (oparg >> 8) & 0xFF;    /* bits 15..8  */
            codestr++;
            _Py_FALLTHROUGH;
        case 1:
            codestr->op.code = opcode;                /* the real opcode */
            codestr->op.arg = oparg & 0xFF;           /* bits 7..0  */
            codestr++;
            break;
        default:
            Py_UNREACHABLE();
    }

Reading it: a four-byte argument emits three EXTENDED_ARG units (carrying the top three bytes, most-significant first) followed by the real opcode carrying the low byte; a three-byte argument emits two; and so on — the _Py_FALLTHROUGH chains the cases so the right number of prefixes is produced. At runtime the interpreter accumulates the EXTENDED_ARG bytes into the high bits of the next opcode’s argument. This is why the same logical instruction can occupy 2, 4, 6, or 8 bytes depending on its argument’s magnitude.

This interacts subtly with jump resolution. InternalDocs/compiler.md lists “converting jump targets from logical labels to relative offsets” as an assembler job — relative, meaning a jump encodes the distance to its target, not an absolute address, so that the same code is position-independent within co_code. But the distance depends on how many bytes lie between the jump and its target, and that in turn depends on whether the intervening instructions needed EXTENDED_ARG prefixes — including the jump itself. Making one jump’s argument wider shifts every later instruction’s offset, which can push another jump’s target past the 256-byte boundary and force that jump to grow too. The assembler therefore sizes instructions iteratively, recomputing offsets until the byte layout stops changing (a fixpoint), and only then writes the final relative offsets. This is the deep reason instruction length cannot be known until the very end, and it is why the pipeline keeps jumps symbolic right up to assembly.

The exception table and line table

The assembler also builds two side tables that travel with the bytecode but are not part of co_code. The exception table (co_exceptiontable) replaced the old SETUP_FINALLY/block-stack scheme in 3.11: instead of runtime bookkeeping opcodes, the compiler emits a compact table mapping each range of instruction offsets to the handler that covers it (assemble.c builds it with assemble_emit_exception_table_entry(), encoding start, size, target, and a depth/lasti field). The line table (co_linetable) maps each instruction back to a source location for tracebacks and debugging. Both are produced here; their byte encodings are a Code Objects concern and are not unpacked further in this note.

The end product is a PyCodeObject whose scope-derived fields close the loop with Symbol Table Construction: co_varnames (locals, parameters first), co_cellvars (locals captured by nested scopes), co_freevars (names this scope borrows from an outer one), co_names (names used by name-based opcodes), co_code (the bytes), co_consts (the literal pool), plus co_exceptiontable and co_linetable. The internal structure of that object — header fields, the co_code opcode layout, how the frame uses co_varnames — is the subject of Code Objects.

Inspecting the Output: dis

The practical window onto all of this is the dis module. Disassembling a closure shows the scope-driven opcode choices the pipeline made:

import dis
 
def make_adder(n):          # n is a CELL in make_adder (captured below)
    def add(x):             # add is a nested function
        return x + n        # x is LOCAL -> LOAD_FAST; n is FREE -> LOAD_DEREF
    return add
 
dis.dis(make_adder)

In the disassembly of make_adder you will see a MAKE_CELL for n (the dis docs: “Creates a new cell in slot i”), and in add you will see COPY_FREE_VARS 1 at the top (“Copies the n free (closure) variables from the closure into the frame”) followed by LOAD_FAST for x and LOAD_DEREF for n. That LOAD_FAST vs LOAD_DEREF split is the visible fingerprint of the symbol-table classification flowing through codegen_nameop into the assembled bytecode. Passing show_caches=True reveals the inline CACHE units the assembler reserved; dis(..., adaptive=True) shows specialized opcodes after the code has run hot.

Failure Modes and Common Misunderstandings

• “Bytecode is portable / stable.” It is neither. The opcode set, their numbers, and the co_code layout change every minor release — which is why .pyc files carry a magic number and are invalidated across versions. Do not hand-craft or depend on specific byte values across releases.
• Confusing pseudo-instructions with bytecode. The instruction sequence the code generator emits is not what runs. Jump targets are labels, some entries expand to multiple opcodes, and EXTENDED_ARG does not exist yet. Only after assembly is there real bytecode. Reading codegen.c and expecting it to match dis output one-to-one is a common confusion.
• Assuming compilation is the slow part. For a long-running program it is a one-time cost, cached in a .pyc (see Bytecode Caching and pyc Files). The recurring cost is in the evaluation loop, not here. Premature worry about “compile time” is usually misplaced.
• EXTENDED_ARG surprises in introspection. Tools that index into co_code by twos can be thrown off by EXTENDED_ARG prefixes and CACHE units; use dis.get_instructions() rather than manual byte arithmetic.

See Also

• Symbol Table Construction — sibling/prerequisite; supplies the scope that codegen_nameop reads.
• Python Abstract Syntax Tree — the input to code generation.
• Compiler Optimization Passes — the CFG optimizations this note deliberately defers.
• Code Objects — the PyCodeObject produced here, field by field, including co_code layout.
• Python Bytecode Instruction Set — the opcodes the assembler emits.
• The dis Module and Bytecode Disassembly — inspecting the compiled output.
• Bytecode Caching and pyc Files — how the result is cached on disk.
• CPython Compilation Pipeline — the end-to-end source-to-bytecode flow.
• Python Internals MOC — parent map.