[Python-Dev] AST optimizer implemented in Python

[Stefan Behnel]

Victor Stinner, 11.08.2012 20:30:
> I started to implement an AST optimizer in Python. It's easy to create
> a new AST tree, so I'm surprised that I didn't find any existing
> project.
> 
> https://bitbucket.org/haypo/misc/src/tip/python/ast_optimizer.py

Since you're about to do pretty much the same thing, here is the code that
Cython uses for its static tree optimisations. It's not based on Python's
own AST, but most of the concepts should apply more or less directly to
that as well.

https://github.com/cython/cython/blob/master/Cython/Compiler/Optimize.py

The code uses a visitor pattern, so you basically register a tree node
callback method by naming it after the node class, e.g. "visit_NameNode()"
to intercept on variables etc. For processing builtins, we use the same
mechanism with method names like "_handle_simple_method_bytes_decode()" for
a ".decode()" method call on a "bytes" object that receives no keyword
arguments or args/kwargs ("simple").

Constant folding is a bit funny in that it calculates lots of constants,
but not all of them will be used in the code. Some are just kept around in
tree nodes to serve as support for later optimisations. Very helpful.

Some more tree processors are here, mostly infrastructure:

https://github.com/cython/cython/blob/master/Cython/Compiler/ParseTreeTransforms.py

It also contains the recursive unwinding of parallel assignments (a,b=c,d),
which leads to much better code at least at the C level. Not sure how
interesting something like this is for an interpreter. It might save some
tuples and/or stack operations along the way. Also, extended iterable
unpacking can be optimised this way.

Some builtins are generically optimised here (straight through the type
system instead of the AST):

https://github.com/cython/cython/blob/master/Cython/Compiler/Builtin.py

For refactoring the tree, we manually build tree nodes most of the time,
but for the more involved cases, we sometimes pass templates through the
parser.

The whole compiler pipeline, including all AST processing steps, is
constructed here:

https://github.com/cython/cython/blob/master/Cython/Compiler/Pipeline.py#L123

Stefan