Skip to main content

Python/flowgraph.c

Source:

cpython 3.14 @ ab2d84fe1023/Python/flowgraph.c

Python/flowgraph.c provides the control-flow graph (CFG) data structures and analysis passes used by the bytecode compiler (compile.c). It manages basic blocks, instruction lists, jump edges, exception table entries, and the final linearization pass that converts the CFG into a flat instruction sequence.

Map​

LinesSymbolRole
1-200cfg_builder, basicblockCFG and block structs; instruction list
201-500cfg_builder_new_block, cfg_builder_addopBlock allocation; instruction append
501-900_PyCfg_OptimizeCodeUnitOptimization passes: dead-code elimination, constant folding
901-1300_PyCfg_ToInstructionSequenceLinearize CFG; assign block offsets
1301-1700_PyCfg_ResolveJumpsBackfill jump targets with final offsets
1701-2500_PyCfg_BuildInstrSequence, _PyCfg_CheckRecursionException table; stack-depth validation

Reading​

Basic block structure​

Each basicblock contains a b_instr array of cfg_instr entries and pointers to successor blocks for fall-through and jump edges. Blocks are identified by their index in the block list; jump instructions store a pointer to the target block that is converted to a byte offset at the end.

// Python/flowgraph.c:1 basicblock
typedef struct basicblock_ {
    struct basicblock_ *b_list;   /* linked list of all blocks */
    cfg_instr *b_instr;           /* instruction array */
    int b_iused, b_ialloc;        /* used / allocated instruction slots */
    struct basicblock_ *b_next;   /* fall-through successor */
    unsigned b_return: 1;         /* ends with RETURN_VALUE */
    ...
} basicblock;

CFG optimization passes​

_PyCfg_OptimizeCodeUnit runs several passes over the CFG: constant folding (e.g., LOAD_CONST 1; LOAD_CONST 2; BINARY_OP + to LOAD_CONST 3), dead-code elimination (blocks with no predecessors are removed), and jump threading (a jump-to-jump is replaced by a direct jump to the final target).

// Python/flowgraph.c:501 _PyCfg_OptimizeCodeUnit
int
_PyCfg_OptimizeCodeUnit(cfg_builder *g, PyObject *consts, PyObject *const_cache,
                        int code_flags, int nlocals, int nparams)
{
    if (optimize_basic_block(g, consts, const_cache) < 0) return -1;
    if (remove_unused_consts(g, consts) < 0) return -1;
    if (eliminate_dead_code(g) < 0) return -1;
    if (thread_jumps(g) < 0) return -1;
    return 0;
}

Jump resolution​

After CFG linearization, _PyCfg_ResolveJumps iterates all jump instructions and replaces block pointers with the final byte offset. This is the last step before the instruction sequence is handed to makecode to build the PyCodeObject.

gopy notes​

The gopy equivalent is compile/flowgraph.go, compile/flowgraph_passes.go, and compile/flowgraph_jumps.go. The architecture mirrors CPython's CFG exactly: compile/flowgraph.go provides Block and Instr, the passes in flowgraph_passes.go perform dead-code elimination and constant folding, and flowgraph_jumps.go resolves jump offsets.