[Python-Dev] AST optimizer implemented in Python

[Victor Stinner]

Hi,

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

To test its peephole optimizations (by checking manually its final
bytecode), I wrote a patch for Python to disable Python internal
peephole optimizer (on bytecode):
https://bitbucket.org/haypo/misc/src/tip/python/compile_disable_peephole.patch

--

There is BytecodeAssembler [1], but it seems to be specialized on
bytecode. There are (at least?) 3 different issues to implement an AST
optimizer, but in C, not in Python:

http://bugs.python.org/issue1346238
http://bugs.python.org/issue10399
http://bugs.python.org/issue11549

--

My proof-of-concept only implements very basic optimizations like 1+1
=> 2 or "abcdef"[:3] => "abc", but it should easy to extend it to do
more interesting optimization like function inlining.

To allow more optimization, the optimizer permits to declare variables
as constant. For example, sys.hexversion is replaced by its value by
the optimizer, and checks like "sys.hexversion > 0x3000000" are done
at compile time. This feature can be used to drop completly debug code
at compilation, without the need of a preprocessor. For example, calls
to logging.debug() can simply be dropped if the log level is hardcoded
to ERROR (40).

Other idea to improve this optimizer:
 - move invariant out of loops. Example: "x=[]; for i in range(10):
x.append(i)" => "x=[]; x_append=x.append; for i in range(10):
x_append(i)". Require to infer the type of variables.
 - unroll loops
 - inline small functions
 - etc.

To be able to use such optimizer on a whole Python project, a new
function (ex: sys.setastoptimizer()) can be added to CPython to call
the optimizer between the compilation to AST and the compilation to
bytecode. So the optimizer would be optionnal and it avoids bootstrap
issues.

[1] http://pypi.python.org/pypi/BytecodeAssembler

Victor