Note
This PEP has been withdrawn and moved to the Pythondeveloper’s guide.
Historically (through 2.4), compilation from source code to bytecodeinvolved two steps:
Historically, this is not how a standard compiler works. The usualsteps for compilation are:
Starting with Python 2.5, the above steps are now used. This changewas done to simplify compilation by breaking it into three steps.The purpose of this document is to outline how the latter three stepsof the process works.
This document does not touch on how parsing works beyond what is neededto explain what is needed for compilation. It is also not exhaustivein terms of the how the entire system works. You will most likely needto read some source to have an exact understanding of all details.
Python’s parser is an LL(1) parser mostly based on theimplementation laid out in the Dragon Book[Aho86].
The grammar file for Python can be found in Grammar/Grammar with thenumeric value of grammar rules are stored in Include/graminit.h. Thenumeric values for types of tokens (literal tokens, such as:,numbers, etc.) are kept in Include/token.h). The parse tree made up ofnode* structs (as defined in Include/node.h).
Querying data from the node structs can be done with the followingmacros (which are all defined in Include/token.h):
CHILD(node*,int)RCHILD(node*,int)NCH(node*)STR(node*): for aCOLON tokenTYPE(node*)Include/graminit.hREQ(node*,TYPE)LINENO(node*)To tie all of this example, consider the rule for ‘while’:
while_stmt:'while'test':'suite['else'':'suite]
The node representing this will haveTYPE(node)==while_stmt andthe number of children can be 4 or 7 depending on if there is an ‘else’statement. To access what should be the first ‘:’ and require it be anactual ‘:’ token,(REQ(CHILD(node,2),COLON).
The abstract syntax tree (AST) is a high-level representation of theprogram structure without the necessity of containing the source code;it can be thought of as an abstract representation of the source code. Thespecification of the AST nodes is specified using the Zephyr AbstractSyntax Definition Language (ASDL)[Wang97].
The definition of the AST nodes for Python is found in the fileParser/Python.asdl .
Each AST node (representing statements, expressions, and severalspecialized types, like list comprehensions and exception handlers) isdefined by the ASDL. Most definitions in the AST correspond to aparticular source construct, such as an ‘if’ statement or an attributelookup. The definition is independent of its realization in anyparticular programming language.
The following fragment of the Python ASDL construct demonstrates theapproach and syntax:
module Python{ stmt = FunctionDef(identifier name, arguments args, stmt* body, expr* decorators) | Return(expr? value) | Yield(expr value) attributes (int lineno)}The preceding example describes three different kinds of statements;function definitions, return statements, and yield statements. Allthree kinds are considered of type stmt as shown by ‘|’ separating thevarious kinds. They all take arguments of various kinds and amounts.
Modifiers on the argument type specify the number of values needed; ‘?’means it is optional, ‘*’ means 0 or more, no modifier means only onevalue for the argument and it is required. FunctionDef, for instance,takes an identifier for the name, ‘arguments’ for args, zero or morestmt arguments for ‘body’, and zero or more expr arguments for‘decorators’.
Do notice that something like ‘arguments’, which is a node type, isrepresented as a single AST node and not as a sequence of nodes as withstmt as one might expect.
All three kinds also have an ‘attributes’ argument; this is shown by thefact that ‘attributes’ lacks a ‘|’ before it.
The statement definitions above generate the following C structure type:
typedefstruct_stmt*stmt_ty;struct_stmt{enum{FunctionDef_kind=1,Return_kind=2,Yield_kind=3}kind;union{struct{identifiername;arguments_tyargs;asdl_seq*body;}FunctionDef;struct{expr_tyvalue;}Return;struct{expr_tyvalue;}Yield;}v;intlineno;}
Also generated are a series of constructor functions that allocate (inthis case) a stmt_ty struct with the appropriate initialization. The‘kind’ field specifies which component of the union is initialized. TheFunctionDef() constructor function sets ‘kind’ to FunctionDef_kind andinitializes the ‘name’, ‘args’, ‘body’, and ‘attributes’ fields.
Before discussing the actual implementation of the compiler, a discussion ofhow memory is handled is in order. To make memory management simple, an arenais used. This means that a memory is pooled in a single location for easyallocation and removal. What this gives us is the removal of explicit memorydeallocation. Because memory allocation for all needed memory in the compilerregisters that memory with the arena, a single call to free the arena is allthat is needed to completely free all memory used by the compiler.
In general, unless you are working on the critical core of the compiler, memorymanagement can be completely ignored. But if you are working at either thevery beginning of the compiler or the end, you need to care about how the arenaworks. All code relating to the arena is in either Include/pyarena.h orPython/pyarena.c .
PyArena_New() will create a new arena. The returned PyArena structure willstore pointers to all memory given to it. This does the bookkeeping of whatmemory needs to be freed when the compiler is finished with the memory it used.That freeing is done with PyArena_Free(). This needs to only be called instrategic areas where the compiler exits.
As stated above, in general you should not have to worry about memorymanagement when working on the compiler. The technical details have beendesigned to be hidden from you for most cases.
The only exception comes about when managing a PyObject. Since the restof Python uses reference counting, there is extra support addedto the arena to cleanup each PyObject that was allocated. These casesare very rare. However, if you’ve allocated a PyObject, you must tellthe arena about it by calling PyArena_AddPyObject().
The AST is generated from the parse tree (see Python/ast.c) using thefunctionPyAST_FromNode().
The function begins a tree walk of the parse tree, creating various ASTnodes as it goes along. It does this by allocating all new nodes itneeds, calling the proper AST node creation functions for any requiredsupporting functions, and connecting them as needed.
Do realize that there is no automated nor symbolic connection betweenthe grammar specification and the nodes in the parse tree. No help isdirectly provided by the parse tree as in yacc.
For instance, one must keep track of which node in the parse treeone is working with (e.g., if you are working with an ‘if’ statementyou need to watch out for the ‘:’ token to find the end of the conditional).
The functions called to generate AST nodes from the parse tree all havethe name ast_for_xx where xx is what the grammar rule that the functionhandles (alias_for_import_name is the exception to this). These in turncall the constructor functions as defined by the ASDL grammar andcontained in Python/Python-ast.c (which was generated byParser/asdl_c.py) to create the nodes of the AST. This all leads to asequence of AST nodes stored in asdl_seq structs.
Function and macros for creating and usingasdl_seq* types as foundin Python/asdl.c and Include/asdl.h:
asdl_seq_new()asdl_seq_GET()asdl_seq_SET()asdl_seq_LEN(asdl_seq*)If you are working with statements, you must also worry about keepingtrack of what line number generated the statement. Currently the linenumber is passed as the last parameter to each stmt_ty function.
A control flow graph (often referenced by its acronym, CFG) is adirected graph that models the flow of a program using basic blocks thatcontain the intermediate representation (abbreviated “IR”, and in thiscase is Python bytecode) within the blocks. Basic blocks themselves area block of IR that has a single entry point but possibly multiple exitpoints. The single entry point is the key to basic blocks; it all hasto do with jumps. An entry point is the target of something thatchanges control flow (such as a function call or a jump) while exitpoints are instructions that would change the flow of the program (suchas jumps and ‘return’ statements). What this means is that a basicblock is a chunk of code that starts at the entry point and runs to anexit point or the end of the block.
As an example, consider an ‘if’ statement with an ‘else’ block. Theguard on the ‘if’ is a basic block which is pointed to by the basicblock containing the code leading to the ‘if’ statement. The ‘if’statement block contains jumps (which are exit points) to the true bodyof the ‘if’ and the ‘else’ body (which may be NULL), each of which aretheir own basic blocks. Both of those blocks in turn point to thebasic block representing the code following the entire ‘if’ statement.
CFGs are usually one step away from final code output. Code is directlygenerated from the basic blocks (with jump targets adjusted based on theoutput order) by doing a post-order depth-first search on the CFGfollowing the edges.
With the AST created, the next step is to create the CFG. The first stepis to convert the AST to Python bytecode without having jump targetsresolved to specific offsets (this is calculated when the CFG goes tofinal bytecode). Essentially, this transforms the AST into Pythonbytecode with control flow represented by the edges of the CFG.
Conversion is done in two passes. The first creates the namespace(variables can be classified as local, free/cell for closures, orglobal). With that done, the second pass essentially flattens the CFGinto a list and calculates jump offsets for final output of bytecode.
The conversion process is initiated by a call to the functionPyAST_Compile() in Python/compile.c . This function does both theconversion of the AST to a CFG andoutputting final bytecode from the CFG. The AST to CFG step is handledmostly by two functions called by PyAST_Compile(); PySymtable_Build() andcompiler_mod() . The former is in Python/symtable.c while the latter is inPython/compile.c .
PySymtable_Build() begins by entering the starting code block for theAST (passed-in) and then calling the proper symtable_visit_xx function(with xx being the AST node type). Next, the AST tree is walked withthe various code blocks that delineate the reach of a local variableas blocks are entered and exited using symtable_enter_block() andsymtable_exit_block(), respectively.
Once the symbol table is created, it is time for CFG creation, whosecode is in Python/compile.c . This is handled by several functionsthat break the task down by various AST node types. The functions areall named compiler_visit_xx where xx is the name of the node type (suchas stmt, expr, etc.). Each function receives astructcompiler*and xx_ty where xx is the AST node type. Typically these functionsconsist of a large ‘switch’ statement, branching based on the kind ofnode type passed to it. Simple things are handled inline in the‘switch’ statement with more complex transformations farmed out to otherfunctions named compiler_xx with xx being a descriptive name of what isbeing handled.
When transforming an arbitrary AST node, use the VISIT() macro.The appropriate compiler_visit_xx function is called, based on the valuepassed in for <node type> (soVISIT(c,expr,node) callscompiler_visit_expr(c,node)). The VISIT_SEQ macro is very similar,but is called on AST node sequences (those values that were created asarguments to a node that used the ‘*’ modifier). There is alsoVISIT_SLICE() just for handling slices.
Emission of bytecode is handled by the following macros:
ADDOP()ADDOP_I()ADDOP_O(structcompiler*c,intop,PyObject*type,PyObject*obj)ADDOP_NAME()ADDOP_JABS()ADDOP_JREL()Several helper functions that will emit bytecode and are namedcompiler_xx() where xx is what the function helps with (list, boolop,etc.). A rather useful one is compiler_nameop().This function looks up the scope of a variable and, based on theexpression context, emits the proper opcode to load, store, or deletethe variable.
As for handling the line number on which a statement is defined, ishandled by compiler_visit_stmt() and thus is not a worry.
In addition to emitting bytecode based on the AST node, handling thecreation of basic blocks must be done. Below are the macros andfunctions used for managing basic blocks:
NEW_BLOCK()NEXT_BLOCK()compiler_new_block()Once the CFG is created, it must be flattened and then final emission ofbytecode occurs. Flattening is handled using a post-order depth-firstsearch. Once flattened, jump offsets are backpatched based on theflattening and then a PyCodeObject file is created. All of this ishandled by calling assemble() .
Sometimes a new feature requires a new opcode. But adding new bytecode isnot as simple as just suddenly introducing new bytecode in the AST ->bytecode step of the compiler. Several pieces of code throughout Python dependon having correct information about what bytecode exists.
First, you must choose a name and a unique identifier number. The officiallist of bytecode can be found in Include/opcode.h . If the opcode is to takean argument, it must be given a unique number greater than that assigned toHAVE_ARGUMENT (as found in Include/opcode.h).
Once the name/number pairhas been chosen and entered in Include/opcode.h, you must also enter it intoLib/opcode.py and Doc/library/dis.rst .
With a new bytecode you must also change what is called the magic number for.pyc files. The variableMAGIC in Python/import.c contains the number.Changing this number will lead to all .pyc files with the old MAGICto be recompiled by the interpreter on import.
Finally, you need to introduce the use of the new bytecode. AlteringPython/compile.c and Python/ceval.c will be the primary places to change.But you will also need to change the ‘compiler’ package. The key filesto do that are Lib/compiler/pyassem.py and Lib/compiler/pycodegen.py .
If you make a change here that can affect the output of bytecode thatis already in existence and you do not change the magic number constantly, makesure to delete your old .py(c|o) files! Even though you will end up changingthe magic number if you change the bytecode, while you are debugging your workyou will be changing the bytecode output without constantly bumping up themagic number. This means you end up with stale .pyc files that will not berecreated. Runningfind.-name'*.py[co]'-execrm-f{}';' should delete all .pyc files youhave, forcing new ones to be created and thus allow you test out your newbytecode properly.
The result ofPyAST_Compile() is a PyCodeObject which is defined inInclude/code.h . And with that you now have executable Python bytecode!
The code objects (byte code) is executed in Python/ceval.c . This filewill also need a new case statement for the new opcode in the big switchstatement in PyEval_EvalFrameEx().
MAGIC) for bytecode versioningThis section lists known experiments involving the compiler (includingbytecode).
Skip Montanaro presented a paper at a Python workshop on a peephole optimizer[1].
Michael Hudson has a non-active SourceForge project named Bytecodehacks[2] that provides functionality for playing with bytecodedirectly.
An opcode to combine the functionality of LOAD_ATTR/CALL_FUNCTION was creatednamed CALL_ATTR[3]. Currently only works for classic classes andfor new-style classes rough benchmarking showed an actual slowdown thanks tohaving to support both classic and new-style classes.
Compilers:Principles,Techniques,andTools,http://www.amazon.com/exec/obidos/tg/detail/-/0201100886/104-0162389-6419108Source:https://github.com/python/peps/blob/main/peps/pep-0339.rst
Last modified:2025-02-01 08:59:27 GMT