Python/compile.c (part 6)

Source:

cpython 3.14 @ ab2d84fe1023/Python/compile.c ↗

This annotation covers the post-AST optimizer passes. See python_compile5_detail for comprehension, match, and exception table compilation.

Map

Lines	Symbol	Role
1-100	Basic block construction	Split instruction stream at jumps and labels
101-220	Dead code elimination	Remove unreachable blocks after RETURN/RAISE
221-360	Constant folding in CFG	LOAD_CONST 1 + LOAD_CONST 2 + BINARY_OP + -> LOAD_CONST 3
361-480	Jump threading	Replace jump-to-jump with direct target
481-600	Stack depth computation	Compute co_stacksize from the flow graph

Reading

Basic block construction

// CPython: Python/compile.c:7180 optimize_basic_block
/* A basic block is a maximal sequence of instructions with:
   - No branch instructions except at the end
   - No branch targets except at the beginning
   Jumps between blocks create the control flow graph (CFG). */
static int
optimize_basic_block(PyCompilerObject *c, basicblock *bb, PyObject *consts)
{
    struct instr *target;
    for (int i = 0; i < bb->b_iused; i++) {
        struct instr *inst = &bb->b_instr[i];
        int opcode = inst->i_opcode;
        ...
    }
}

The compiler first creates a flat instruction sequence, then splits it into basic blocks at every jump and label. This enables dataflow analysis and optimization.

Dead code elimination

// CPython: Python/compile.c:7380 mark_reachable
static int
mark_reachable(basicblock *entryblock)
{
    /* BFS from the entry block; mark all reachable blocks. */
    basicblock **stack = ...;
    while (sp > stack) {
        basicblock *b = *--sp;
        if (b->b_reachable) continue;
        b->b_reachable = 1;
        if (b->b_next && !b->b_next->b_reachable)
            *sp++ = b->b_next;
        /* Push jump targets */
        for each instruction i in b:
            if IS_JUMP(i): push(i.target);
    }
    return 0;
}

def f(): return 1; return 2 — the second return is in an unreachable block and is eliminated. Dead code elimination runs before exception table generation to avoid emitting handlers for code that will never execute.

Jump threading

// CPython: Python/compile.c:7480 jump_thread
static int
jump_thread(struct instr *inst, struct instr *target, int op)
{
    /* If target is also an unconditional jump, skip the middle.
       JUMP A -> JUMP B -> ... becomes JUMP B -> ... */
    assert(!IS_LABEL(inst->i_opcode));
    assert(IS_UNCONDITIONAL_JUMP(target->i_opcode));
    if (inst->i_target == target->i_target) return 0;  /* Already threaded */
    inst->i_target = target->i_target;
    return 1;
}

Jump threading eliminates intermediate jump blocks generated by if/else chains and loop constructs. A JUMP_FORWARD that jumps to another JUMP_FORWARD is replaced by a direct jump to the final target.

gopy notes

Basic block construction is compile.BuildFlowGraph in compile/flowgraph.go. Dead code elimination is compile.MarkReachable. Jump threading is compile.ThreadJumps. Stack depth computation is compile.ComputeStackDepth in compile/flowgraph_stackdepth.go.