Previously, in How CPython Processes Python Source Code, we followed three input points: file input, string input and stream input. We saw how each one became a single struct tok_state, and how the lexer turned it into tokens. This article picks up from what happens when those tokens reach the parser, all the way to the output you see on your screen.
We will maintain our example file addition.py:
x = 40
y = 2
print(x + y)
This is the flow of how the process is going to look like:
tokens
|
v
PEG parser Parser/parser.c
|
v
AST Parser/Python.asdl
|
v
AST preprocess Python/ast_preprocess.c
|
v
symbol table Python/symtable.c
|
v
codegen Python/codegen.c
|
v
instruction sequence
|
v
CFG optimizer Python/flowgraph.c
|
v
assembler Python/assemble.c
|
v
code object
|
v
eval loop Python/ceval.c
| Python/bytecodes.c
v
42
The function run_mod() takes over after the parser. In the previous article we mentioned that:
The stream path never gets here. Its tokens go back to Python as TokenInfo objects.
Which means the file input and string input hand their AST (Abstract Syntax Tree) to the run_mod() function.
run_mod() first calls _PyAST_Compile() to turn the AST into a code object. Secondly, it calls run_eval_code_obj(), which calls PyEval_EvalCode() to run it.
Everything between the AST and the code object happens inside _PyAST_Compile(), in Python/compile.c:
PyCodeObject *
_PyAST_Compile(mod_ty mod, PyObject *filename, PyCompilerFlags *pflags,
int optimize, PyArena *arena)
{
assert(!PyErr_Occurred());
compiler *c = new_compiler(mod, filename, pflags, optimize, arena);
if (c == NULL) {
return NULL;
}
PyCodeObject *co = compiler_mod(c, mod);
compiler_free(c);
assert(co || PyErr_Occurred());
return co;
}
new_compiler() runs the AST preprocess and builds the symbol table. compiler_mod() runs codegen, the optimizer and the assembler.
Tokens To AST In The Parser
The parser isn't written by hand, rule by rule. Instead, Python's syntax is described in a grammar, which acts as a set of instructions for what valid Python code looks like. This grammar lives in Grammar/python.gram.
This grammar-driven PEG parser is fairly new. It arrived in Python 3.9 with PEP 617, replacing the older LL(1) parser, which was removed entirely in 3.10. The old parser could only look one token ahead, which made some syntax impossible to express. The PEG parser lifted that limit and opened the door to many of the language features of the last few years, such as the match statement, parenthesized context managers and better error messages.
Grammar describes the rules. We still need C code that can read Python source code and understand its structure. That's where pegen, CPython's parser generator, comes in. Pegen reads the grammar and automatically generates the C parser in Parser/parser.c, whose first line is:
// @generated by pegen from python.gram
To change Python's syntax, you need to edit the grammar first and run make regen-pegen.
Once the parser has been generated, it needs to know which grammar rule to start with. That decision is made by _PyPegen_parse(). The starting rule depends on what kind of Python code is being parsed. A file uses Py_file_input, so parsing starts at file_rule:
void *
_PyPegen_parse(Parser *p)
{
...
// Run parser
void *result = NULL;
if (p->start_rule == Py_file_input) {
result = file_rule(p);
} else if (p->start_rule == Py_single_input) {
result = interactive_rule(p);
} else if (p->start_rule == Py_eval_input) {
result = eval_rule(p);
} else if (p->start_rule == Py_func_type_input) {
result = func_type_rule(p);
}
return result;
}
The string input we looked at in Part 1 follows the same path:
python -c "x = 40; y = 2; print(x + y)"
Even though we pass a string rather than run a .py file, CPython still treats it as a complete Python program. _PyRun_SimpleStringFlagsWithName() also uses Py_file_input, which tells the parser to start at file_rule. Whether we run a .py file or pass code using -c, the parser follows the same path from this point onward.
Py_file_input is also what exec() uses, since it can run multiple statements. Besides Py_file_input, CPython has three other parsing modes, matching the other branches in _PyPegen_parse():
Py_single_input: used by the interactive Python shell (REPL) to process one statement at a time.Py_eval_input: used byeval(), which expects a single expression.Py_func_type_input: parses function signature type comments such as(int, str) -> bool, the old pre-annotation way of writing types. It only ever produces an AST, never runnable code.
Python's built-in compile() function lets you choose between all four with its mode argument: 'exec', 'eval', 'single' or 'func_type'.
Each grammar rule lists alternatives in order. The parser tries them top to bottom and takes the first match. The code in { } is the action that builds the AST node. The whole file is a list of statements followed by ENDMARKER, which indicates the end of the input.
file[mod_ty]: a=[statements] ENDMARKER { _PyPegen_make_module(p, a) }
Each line of our program (addition.py) is a simple_stmt:
simple_stmt[stmt_ty] (memo):
| assignment
| &"type" type_alias
| e=star_expressions { _PyAST_Expr(e, EXTRA) }
...
The first two lines of our program match assignment. print(x + y) fails assignment and falls through to star_expressions, which wraps it in an Expr node.
x = 40 matches this alternative of assignment:
| a[asdl_expr_seq*]=(z=star_targets '=' { z })+ b=annotated_rhs !'=' tc=[TYPE_COMMENT] {
_PyAST_Assign(a, b, NEW_TYPE_COMMENT(p, tc), EXTRA) }
star_targets recognizes the assignment target (x), while annotated_rhs recognizes the value being assigned (40). Once the rule matches, _PyAST_Assign() creates an Assign node representing the assignment.
The parser recognizes print(...) as a function call, while the addition x + y is handled by the sum rule:
sum[expr_ty]:
| a=sum '+' b=term { _PyAST_BinOp(a, Add, b, EXTRA) }
| a=sum '-' b=term { _PyAST_BinOp(a, Sub, b, EXTRA) }
| term
Every alternative in the grammar becomes a block of C. Here is sum '+' term in the generated parser.c, trimmed:
{ // sum '+' term
...
Token * _literal;
expr_ty a;
expr_ty b;
if (
(a = sum_rule(p)) // sum
&&
(_literal = _PyPegen_expect_token(p, 14)) // token='+'
&&
(b = term_rule(p)) // term
)
{
...
_res = _PyAST_BinOp ( a , Add , b , EXTRA );
...
goto done;
}
p->mark = _mark;
...
}
Each && is one item in the rule. If any item fails, p->mark = _mark rewinds to where the alternative started and the next alternative is tried. This rewind is called backtracking, a feature of the PEG parser.
The parser obtains tokens from _PyPegen_expect_token(). _PyPegen_expect_token() checks the available tokens. When another token is needed, _PyPegen_fill_token() calls _PyTokenizer_Get(), the lexer function we explored in Part 1.
Backtracking gives the parser flexibility, but also causes repeated work. When an alternative fails, the parser may return to an earlier position and re-evaluate the same grammar rule on the same tokens. CPython uses memoization to avoid this. Memoization is caching previous parsing results.
Rules marked with memo, such as simple_stmt, check whether a result has already been cached at the current token position:
if (_PyPegen_is_memoized(p, simple_stmt_type, &_res)) {
Left-recursive rules, which refer to themselves first, always use the cache. sum is one of them. sum_rule() seeds the cache with a failure. It then re-runs sum_raw() in a loop, growing the match each time, until it stops getting longer. That is how 1 + 2 + 3 parses as (1 + 2) + 3.
If the first pass fails, _PyPegen_run_parser() parses the whole input again with the invalid_* rules switched on:
// Make a second parser pass. In this pass we activate heavier and slower checks
// to produce better error messages and more complete diagnostics. Extra "invalid_*"
// rules will be active during parsing.
Token *last_token = p->tokens[p->fill - 1];
reset_parser_state_for_error_pass(p);
_PyPegen_parse(p);
Those rules exist only to produce good messages. For instance, invalid_expression produces this:
print(x y)
^^^
SyntaxError: invalid syntax. Perhaps you forgot a comma?
Valid Python code never needs this second pass. The additional checks only run when the first parsing attempt fails.
Once parsing succeeds, the result is an Abstract Syntax Tree (AST), a structured representation of the Python program. The available AST node types are defined in Parser/Python.asdl. Some of the node definitions used in our example are:
mod = Module(stmt* body, type_ignore* type_ignores)
| Assign(expr* targets, expr value, string? type_comment)
| Expr(expr value)
| BinOp(expr left, operator op, expr right)
| Call(expr func, expr* args, keyword* keywords)
| Constant(constant value, string? kind)
| Name(identifier id, expr_context ctx)
The C constructors we have seen in the grammar, such as _PyAST_Assign() and _PyAST_BinOp(), are defined in Python/Python-ast.c. This file is generated automatically, from Parser/Python.asdl using Parser/asdl_c.py. We can inspect the resulting AST ourselves by running python -m ast addition.py.
For our original program:
x = 40
y = 2
print(x + y)
The output looks like this:
Module(
body=[
Assign(
targets=[
Name(id='x', ctx=Store())],
value=Constant(value=40)),
Assign(
targets=[
Name(id='y', ctx=Store())],
value=Constant(value=2)),
Expr(
value=Call(
func=Name(id='print', ctx=Load()),
args=[
BinOp(
left=Name(id='x', ctx=Load()),
op=Add(),
right=Name(id='y', ctx=Load()))]))])
The parser already knows x is being stored on line 1 and loaded on line 3.
AST Preprocessing and Symbol Table Analysis
Once CPython has generated the AST, the next step is to prepare it for compilation into bytecode. Before generating bytecode, compiler_setup() performs two important operations: AST preprocessing and symbol table analysis.
Here is how both of these operations look:
if (!_PyAST_Preprocess(mod, arena, filename, c->c_optimize, merged, 0)) {
return ERROR;
}
c->c_st = _PySymtable_Build(mod, filename, &c->c_future);
a. AST Preprocessing
The function _PyAST_Preprocess() examines the AST and a few transformations before compilation continues.
In Python 3.14, the preprocessing logic is implemented in Python/ast_preprocess.c. In this stage, a couple of processes take place:
- String formatting optimisation:
fold_binop()turns expressions such as"%s" % (a,)into more efficient forms. - Pattern-matching optimisation: constant expressions in
matchpatterns are folded. - Control-flow warnings: the preprocessor identifies
return,break, orcontinuestatements insidefinallyblocks and emits warnings.
In Python 3.14, general constant folding no longer happens during AST preprocessing.
None of the preprocessing transformations described above apply to our program, which means the AST glides through this part unaltered.
b. Symbol Table Analysis
After preprocessing, CPython calls the following:
c->c_st = _PySymtable_Build(mod, filename, &c->c_future);
The code above builds a symbol table, which helps the compiler understand how variables and other names are used throughout the program. Namely, when CPython encounters x = 40, it needs to know that x is being assigned a value. Additionally, when it encounters print(x + y) it needs to recognise that x and y are being read, while print is being called.
The compiler must determine which scope each name belongs to, e.g. local or global. This is done in Python/symtable.c in two passes:
i. Recording how names are used: CPython walks through the AST and records how each name is used. Each Name node in the AST has a context that describes its role. Store indicates that a name is being assigned a value. Load indicates that a name is being read.
For example, in x = 40, x has a Store context because we are assigning a value to it. In print(x + y), print, x, and y have Load contexts because their values are being accessed:
case Name_kind:
if (!st->st_cur->ste_in_unevaluated_annotation) {
if (!symtable_add_def_ctx(st, e->v.Name.id,
e->v.Name.ctx == Load ? USE : DEF_LOCAL,
LOCATION(e), e->v.Name.ctx)) {
The important expression in the above statement is:
e->v.Name.ctx == Load ? USE : DEF_LOCAL
This checks the context of a name and records whether it is being used (USE) or defined locally (DEF_LOCAL).
For our example, CPython records that:
xis assigned a value and later used.yis assigned a value and later used.printis used but never assigned a value in our module.
CPython then uses these records during the second pass to determine the scope of each name.
ii. Determining variable scopes: Once CPython knows how each name is used, it needs to determine where that name belongs. This happens primarily through the analyze_name() function. The function examines the information collected during the first pass and assigns a scope classification to each name.
In this case:
LOCAL: a name defined in the current scope.GLOBAL_IMPLICIT: a name that is used without a local definition and is not captured from an enclosing function scope.
For our addition.py program, CPython determines that x and y are local symbols within the module's scope because they are both assigned values there.
Moreover, print is different. We never define or assign print anywhere in our program. As a result, CPython classifies it as an implicit global name. This means that when the program runs, Python looks for print in the module's global namespace. If it isn't found, it continues searching the built-in namespace until it finds it.
We can inspect the symbol table generated for our program using Python's symtable module, by running python -m symtable addition.py.
The relevant symbol classifications are:
symbol table for module from file 'addition.py':
local symbol 'x': use, def_local
local symbol 'y': use, def_local
global_implicit symbol 'print': use
The symbol table calls x and y local because they are assigned in the module's own block. At the module level, the local namespace is the global namespace (the same dict). At runtime, they act as the module's globals and are accessible to any function in that file.
AST preprocessing prepares the syntax tree. The symbol table analysis determines how names should be resolved.
For our addition.py example, the AST remains unchanged during preprocessing, but the symbol table provides the compiler with information about x, y, and print.
With the AST and symbol table ready, CPython can now begin generating the instructions that will eventually execute our program.
AST to Instruction Sequence
This stage is handled by compiler_mod(). It generates an instruction sequence from the AST and then passes it to the optimiser and assembler.
static PyCodeObject *
compiler_mod(compiler *c, mod_ty mod)
{
PyCodeObject *co = NULL;
int addNone = mod->kind != Expression_kind;
if (compiler_codegen(c, mod) < 0) {
goto finally;
}
co = _PyCompile_OptimizeAndAssemble(c, addNone);
finally:
_PyCompile_ExitScope(c);
return co;
}
The code generation happens in Python/codegen.c. CPython walks through the AST and generates instructions using macros such as VISIT to process AST nodes and ADDOP to emit instructions.
When CPython begins generating code for a module, it starts by emitting two instructions: RESUME and ANNOTATIONS_PLACEHOLDER. This happens inside codegen_enter_scope():
ADDOP_I(c, loc, RESUME, RESUME_AT_FUNC_START);
if (scope_type == COMPILE_SCOPE_MODULE) {
ADDOP(c, loc, ANNOTATIONS_PLACEHOLDER);
}
RESUME marks the beginning of execution. ANNOTATIONS_PLACEHOLDER reserves a position for module annotation code, which supports the lazy evaluation of annotations. Since our program contains no annotations, the placeholder is removed during a later compilation stage.
The first statement, x = 40, is represented in the AST as an Assign node. When the compiler encounters an assignment, it first visits the value being assigned and then the target receiving that value. This is shown in codegen_visit_stmt():
case Assign_kind:
{
Py_ssize_t n = asdl_seq_LEN(s->v.Assign.targets);
VISIT(c, expr, s->v.Assign.value);
for (Py_ssize_t i = 0; i < n; i++) {
...
VISIT(c, expr,
(expr_ty)asdl_seq_GET(s->v.Assign.targets, i));
}
break;
}
The value 40 is a Constant node, so CPython generates a LOAD_CONST instruction to load it. Next, the target x is a Name node, which is handled by codegen_nameop(). This is where the symbol table from the previous step comes in handy. codegen_nameop() checks the scope of x and uses _PyCompile_ResolveNameop() to determine which type of instruction should be generated.
Although x is classified as LOCAL in the symbol table, it belongs to the module scope rather than a function scope. CPython uses a NAME instruction instead of a fast-local instruction, as shown below:
case COMPILE_OP_NAME:
switch (ctx) {
case Load:
op = (SYMTABLE_ENTRY(c)->ste_type == ClassBlock
&& _PyCompile_IsInInlinedComp(c))
? LOAD_GLOBAL
: LOAD_NAME;
break;
case Store: op = STORE_NAME; break;
case Del: op = DELETE_NAME; break;
}
As a result, the statement x = 40 produces:
LOAD_CONST 40
STORE_NAME x
The same process applies to y = 2. If these assignments were inside a function, CPython would normally use STORE_FAST instead of STORE_NAME.
The final statement, print(x + y), is represented in the AST as an Expr node containing a Call expression. The codegen_stmt_expr() function visits the expression and emits POP_TOP to discard its return value, since the result of the print() call is not used. The function call is handled by codegen_call():
VISIT(c, expr, e->v.Call.func);
...
ADDOP(c, loc, PUSH_NULL);
loc = LOC(e);
ret = codegen_call_helper(c, loc, 0,
e->v.Call.args,
e->v.Call.keywords);
For our file, CPython first loads print, emits PUSH_NULL as part of the calling convention, and then processes the argument x + y before generating the CALL instruction.
The argument x + y is a BinOp node, which means it follows a simple order: visit the left operand, visit the right operand, and then emit the binary operation:
case BinOp_kind:
VISIT(c, expr, e->v.BinOp.left);
VISIT(c, expr, e->v.BinOp.right);
ADDOP_BINARY(c, loc, e->v.BinOp.op);
break;
For x + y, this produces:
LOAD_NAME x
LOAD_NAME y
BINARY_OP +
Once the addition has been evaluated, CALL invokes print() with the result, and POP_TOP discards the function's return value. Because module execution must return None, the addNone flag passed by compiler_mod() causes LOAD_CONST None and RETURN_VALUE to be added before optimisation.
After code generation and the addition of the module's return instructions, CPython has produced an instruction sequence for our program.
The following shows the unoptimised instruction sequence. At this point the compiler keeps the constants in a list, [40, 2, None]: 40 is at index 0, 2 is at index 1, and None is at index 2. LOAD_CONST 0 therefore means "load the constant at index 0", which is 40.
RESUME 0
ANNOTATIONS_PLACEHOLDER
LOAD_CONST 0 (40)
STORE_NAME 0 (x)
LOAD_CONST 1 (2)
STORE_NAME 1 (y)
LOAD_NAME 2 (print)
PUSH_NULL
LOAD_NAME 0 (x)
LOAD_NAME 1 (y)
BINARY_OP 0 (+)
CALL 1
POP_TOP
LOAD_CONST 2 (None)
RETURN_VALUE
This listing comes from _testinternalcapi.compiler_codegen(), an internal CPython test hook that is available only in builds that include CPython's test modules.
At this stage CPython has converted our AST into a sequence of unoptimised instructions.
The instruction sequence is then passed to the next compilation stage, where the Control Flow Graph (CFG) optimizer can simplify and optimize it before assembly.
CFG Optimizer
CPython moves on to optimising the instruction sequence before converting it into bytecode. optimize_and_assemble_code_unit() converts the instruction sequence into a CFG, applies optimisations, and then passes the result to the assembler.
_PyCfg_FromInstructionSequence() divides the instructions into basic blocks. A basic block is a set of instructions with no jumps in between except at the ends. While building the blocks it also handles the ANNOTATIONS_PLACEHOLDER instruction we encountered during code generation. If the module contains annotation code, it is inserted at this position.
Since our addition.py program has no annotations, the placeholder is removed.
_PyCfg_OptimizeCodeUnit() then runs the passes in order:
/** Optimization **/
RETURN_IF_ERROR(optimize_cfg(g, consts, const_cache, firstlineno));
RETURN_IF_ERROR(remove_unused_consts(g->g_entryblock, consts));
RETURN_IF_ERROR(
add_checks_for_loads_of_uninitialized_variables(
g->g_entryblock, nlocals, nparams));
RETURN_IF_ERROR(insert_superinstructions(g));
RETURN_IF_ERROR(push_cold_blocks_to_end(g));
RETURN_IF_ERROR(resolve_line_numbers(g, firstlineno));
For our example, two of these optimisations are relevant.
i. Small integers: maybe_instr_make_load_smallint() replaces LOAD_CONST with LOAD_SMALL_INT when the constant is an integer between 0 and 255.
Instead of looking up the integer in the code object's constant table, LOAD_SMALL_INT stores its value directly in the instruction's argument. These small integers are preallocated as immortal Python objects.
if (!overflow && _PY_IS_SMALL_INT(val)) {
assert(_Py_IsImmortal(newconst));
INSTR_SET_OP1(instr, LOAD_SMALL_INT, (int)val);
return 1;
}
The allowed range can be checked in _PY_IS_SMALL_INT.
In our example, both 40 and 2 fall within this range, so their LOAD_CONST instructions are replaced with LOAD_SMALL_INT. However, if we had written x = 300, the compiler would still use LOAD_CONST, since 300 is outside the supported range.
ii. Removing unused constants: Originally, our instruction sequence referenced the constant table [40, 2, None]. After replacing the integer loads with LOAD_SMALL_INT, no instruction refers to 2 in the constant table any more.
The remove_unused_consts() function removes unused constants, with one important exception:
// The first constant may be docstring; keep it always.
index_map[0] = 0;
CPython always preserves the first constant because it may represent the module's docstring. For our program, this means 40 stays in the constant table, while 2 is removed.
The resulting constants are (40, None). Since 2 was removed, the index of None changes from 2 to 1.
This CFG optimisation stage is also where general constant folding now takes place.
To clarify, if we wrote print(40 + 2), the optimiser would calculate 40 + 2 during compilation and replace the expression with 42:
LOAD_NAME 0 (print)
PUSH_NULL
LOAD_SMALL_INT 42
CALL 1
Our actual program, however, uses x + y. Because these are variable names rather than constant expressions, the compiler cannot fold the addition at this stage, so BINARY_OP remains.
After these optimisations, the instruction sequence for addition.py becomes:
RESUME 0
LOAD_SMALL_INT 40
STORE_NAME 0 (x)
LOAD_SMALL_INT 2
STORE_NAME 1 (y)
LOAD_NAME 2 (print)
PUSH_NULL
LOAD_NAME 0 (x)
LOAD_NAME 1 (y)
BINARY_OP 0 (+)
CALL 1
POP_TOP
LOAD_CONST 1 (None)
RETURN_VALUE
Both integer loads now use LOAD_SMALL_INT. The ANNOTATIONS_PLACEHOLDER has disappeared, and None has moved to constant index 1.
With these optimisations complete, CPython can now assemble the instructions into a code object.
The Assembler
This is handled by _PyAssemble_MakeCodeObject(). The function resolves jump targets, encodes the instructions into bytecode, and packages the result into a Python code object.
struct assembler a;
int res = assemble_emit(&a, instrs, umd->u_firstlineno, const_cache);
if (res == SUCCESS) {
co = makecode(umd, &a, const_cache, consts, maxdepth, nlocalsplus,
code_flags, filename);
}
assemble_emit() writes the instructions into their bytecode representation, followed by the line-number and exception tables.
Each instruction is encoded by write_instr() as a 2-byte code unit:
- One byte stores the opcode.
- One byte stores the instruction argument.
If an argument is larger than 255, CPython uses EXTENDED_ARG prefixes to represent it.
Some instructions also require additional inline cache entries: empty slots written straight after the instruction. They look like wasted space for now, but they are what lets the interpreter speed up hot code later. We'll come back to them at the end of the Execution section.
int caches = _PyOpcode_Caches[opcode];
...
case 1:
codestr->op.code = opcode;
codestr->op.arg = oparg & 0xFF;
codestr++;
break;
...
while (caches--) {
codestr->op.code = CACHE;
codestr->op.arg = 0;
codestr++;
}
Once the bytecode has been emitted, makecode() packages it together with the constants, names, and metadata tables into a code object using _PyCode_New().
If we compile our source using compile(src, "addition.py", "exec"), the resulting code object contains:
co_consts (40, None)
co_names ('x', 'y', 'print')
co_stacksize 4
co_code 44 bytes
The co_consts tuple contains the remaining constants, whereas co_names stores the names referenced by the instructions. The co_stacksize value tells the interpreter the maximum stack space required by this code. For our program, it is 4, because the stack reaches its largest size when it contains print, NULL, x, and y.
Here is the resulting bytecode, displayed as hexadecimal bytes grouped into 2-byte code units:
80 00 RESUME 0
5e 28 LOAD_SMALL_INT 40
74 00 STORE_NAME 0 (x)
5e 02 LOAD_SMALL_INT 2
74 01 STORE_NAME 1 (y)
5d 02 LOAD_NAME 2 (print)
21 00 PUSH_NULL
5d 00 LOAD_NAME 0 (x)
5d 01 LOAD_NAME 1 (y)
2c 00 BINARY_OP 0 (+)
00 00 CACHE
00 00 CACHE
00 00 CACHE
00 00 CACHE
00 00 CACHE
34 01 CALL 1
00 00 CACHE
00 00 CACHE
00 00 CACHE
1f 00 POP_TOP
52 01 LOAD_CONST 1 (None)
23 00 RETURN_VALUE
There are 14 instructions and 8 cache entries: five for BINARY_OP and three for CALL. That gives us 22 code units, or 44 bytes in total.
To exemplify, in 5e 28 LOAD_SMALL_INT 40, 0x5e identifies the opcode, while 0x28 is the hexadecimal representation of 40, stored directly in the argument byte.
We can inspect the assembled instructions using python -m dis addition.py. This displays the instructions with their corresponding line numbers, while normally hiding the inline cache entries.
At this point, our program has been compiled into a code object containing the bytecode needed for execution.
Execution
With the code object ready, CPython can finally execute our program.
Back in pythonrun.c, run_eval_code_obj() calls PyEval_EvalCode(). PyEval_EvalCode() wraps the code object in a function, using the module's dictionary as both its global and local namespace. It then calls _PyEval_Vector(), which creates an execution frame and passes it to _PyEval_EvalFrame():
static inline PyObject*
_PyEval_EvalFrame(PyThreadState *tstate, _PyInterpreterFrame *frame, int throwflag)
{
EVAL_CALL_STAT_INC(EVAL_CALL_TOTAL);
if (tstate->interp->eval_frame == NULL) {
return _PyEval_EvalFrameDefault(tstate, frame, throwflag);
}
return tstate->interp->eval_frame(tstate, frame, throwflag);
}
Normally, execution continues into _PyEval_EvalFrameDefault(), CPython's main interpreter loop. The loop reads the bytecode instructions and executes their corresponding operations.
Interestingly, the instruction implementations are not written directly in ceval.c. They are defined in Python/bytecodes.c using a small domain-specific language. A code generator then converts these definitions into Python/generated_cases.c.h, which is included by ceval.c.
The generated file begins with:
// This file is generated by Tools/cases_generator/tier1_generator.py
// from:
// Python/bytecodes.c
// Do not edit!
When the interpreter executes our file, the first relevant instruction is LOAD_SMALL_INT 40, which pushes the preallocated integer 40 onto the stack without creating a new integer object. Its implementation is defined in bytecodes.c:
replicate(4) inst(LOAD_SMALL_INT, (-- value)) {
assert(oparg < _PY_NSMALLPOSINTS);
PyObject *obj = (PyObject *)&_PyLong_SMALL_INTS[_PY_NSMALLNEGINTS + oparg];
value = PyStackRef_FromPyObjectImmortal(obj);
}
The (-- value) notation describes the instruction's stack effect. Whatever sits left of -- is popped off the stack, and whatever sits right of it is pushed on. Here the left side is empty, so the instruction pops nothing and pushes value. CPython's evaluation stack grows upward, so pushing value moves the stack pointer one slot higher. The generated code does stack_pointer += 1.
STORE_NAME 0 pops that value from the stack and stores it under co_names[0], which is 'x', in the module's dictionary:
inst(STORE_NAME, (v -- )) {
PyObject *name = GETITEM(FRAME_CO_NAMES, oparg);
PyObject *ns = LOCALS();
...
if (PyDict_CheckExact(ns)) {
err = PyDict_SetItem(ns, name, PyStackRef_AsPyObjectBorrow(v));
}
}
The assignment y = 2 follows the same process, using LOAD_SMALL_INT 2 and STORE_NAME 1.
LOAD_NAME 2 looks up the name 'print'. This lookup is handled by _PyEval_LoadName(). _PyEval_LoadName() looks in the local namespace first, then the global namespace, and finally the built-in namespace.
Since print is not defined in our module, CPython finds the built-in print() function. After PUSH_NULL, LOAD_NAME x, and LOAD_NAME y, the stack contains [ print | NULL | 40 | 2 ].
BINARY_OP 0 now performs the addition. It pops the two operands, 40 and 2, calls the appropriate addition operation, and pushes the result back onto the stack:
op(_BINARY_OP, (lhs, rhs -- res)) {
PyObject *lhs_o = PyStackRef_AsPyObjectBorrow(lhs);
PyObject *rhs_o = PyStackRef_AsPyObjectBorrow(rhs);
assert(_PyEval_BinaryOps[oparg]);
PyObject *res_o = _PyEval_BinaryOps[oparg](lhs_o, rhs_o);
...
res = PyStackRef_FromPyObjectSteal(res_o);
DECREF_INPUTS();
}
After the addition, the stack becomes [ print | NULL | 42 ].
The CALL 1 instruction calls print() with one argument: 42. This produces the output 42. The call returns None, which is left on the stack. POP_TOP discards that return value, while LOAD_CONST None and RETURN_VALUE finish executing the module.
CPython can still optimise instructions further while the program is running. This is where the inline cache entries added by the assembler come in. They hold the state of the specialising adaptive interpreter (PEP 659). For example, BINARY_OP contains both a specialisation counter and the generic binary operation:
macro(BINARY_OP) = _SPECIALIZE_BINARY_OP + unused/4 + _BINARY_OP;
As an instruction executes repeatedly, CPython can replace it with a specialised version based on the types it encounters.
Our addition.py module runs only once, so it does not execute the addition enough times to trigger this kind of specialisation.
After one execution, dis.dis(code, adaptive=True) shows that RESUME has become RESUME_CHECK and LOAD_CONST None has become LOAD_CONST_IMMORTAL, while BINARY_OP remains generic.
However, consider moving the addition into a function:
def add(x, y):
return x + y
If we call this function 1,000 times with integers, CPython can specialise its instructions. The resulting adaptive disassembly can look like:
RESUME_CHECK 0
LOAD_FAST_BORROW_LOAD_FAST_BORROW 1 (x, y)
BINARY_OP_ADD_INT 0 (+)
RETURN_VALUE
Here, BINARY_OP has become BINARY_OP_ADD_INT, a specialised instruction for adding integers that avoids generic binary-operation dispatch. The function also uses LOAD_FAST_BORROW instead of LOAD_NAME. This comes from the scope decisions made during symbol table analysis and code generation.
The two load operations have also been combined into a single superinstruction through the insert_superinstructions() pass performed during CFG optimisation. This pass allows CPython to combine compatible instructions into a single, more efficient instruction, reducing the overhead of executing them separately.
Visual flow of the whole process from both articles:
source
|
+----------------+----------------+
| | |
v v v
FILE * C string readline()
(file input) (string input) (stream input)
| | |
_PyTokenizer_ _PyTokenizer_ _PyTokenizer_ PART 1
FromFile() FromUTF8() FromReadline() How CPython Processes
| | | Python Source Code
+----------------+----------------+
|
v
struct tok_state Parser/lexer/state.h
|
v
_PyTokenizer_Get() Parser/lexer/lexer.c
|
v
tokens
|
+----------+-----------+
| |
v v
PEG parser tokenize module
(file, string) (stream stops here,
| prints TokenInfo)
=================|=============================================================
| PART 2
v How CPython Compiles
PEG parser Parser/parser.c and Runs Python Code
|
v
AST Parser/Python.asdl
|
v
AST preprocess Python/ast_preprocess.c
|
v
symbol table Python/symtable.c
|
v
codegen Python/codegen.c
|
v
instruction sequence
|
v
CFG optimizer Python/flowgraph.c
|
v
assembler Python/assemble.c
|
v
code object
|
v
eval loop Python/ceval.c
| Python/bytecodes.c
v
42
That brings us to the end of our 2-part series for the three lines of Python code. In part 1, a file, a string or a stream became one struct tok_state, and the lexer turned its characters into tokens.
In this article, those tokens became an AST. The symbol table worked out where every name lives, codegen turned the tree into instructions, the optimizer tightened them, and the assembler packed them into a 44-byte code object. Finally, the eval loop ran those bytes one instruction at a time and printed 42.
Each stage hands the next one a simpler form of the same program:
x = 40 ... source
NAME 'x' ... tokens
Assign(...) AST
local 'x' symbol table
LOAD_CONST 0 instruction sequence
LOAD_SMALL_INT optimized instructions
5e 28 74 00 ... code object
42 output
To try these steps on your own you can run the following:
# tokens
python -m tokenize addition.py
# AST
python -m ast addition.py
# scopes
python -m symtable addition.py
# bytecode
python -m dis addition.py
You do not have to know all this to write Python obviously, but now anytime you encounter an error or a function speeds up, you will know which stage did it and where to look.
References
- Grammar/python.gram
- Parser/pegen.c
- Parser/Python.asdl
- Python/pythonrun.c
- Python/bltinmodule.c
- Python/compile.c
- Python/ast_preprocess.c
- Python/symtable.c
- Python/codegen.c
- Python/flowgraph.c
- Python/assemble.c
- Python/ceval.c
- Python/bytecodes.c
- Include/internal/pycore_ceval.h
- Include/internal/pycore_long.h
Generated files:
CPython internals docs:
Python documentation:
- Full grammar specification
- Abstract Syntax Trees
symtable:Access to the compiler's symbol tablesdis:Disassembler for Python bytecode- compile()
- Code objects (data model)
- PyEval_EvalCode()
PEPs: