This patch adds the following: A visitor interface
generalized from the existing ast pass code in order to
make it easy to write ast passes that only care about
specific node types. A constant folding pass that looks
for operations involving number or string literals, and
calculates these at compile time. Example code snippets
that this pass will optimize:

3 + 4 + x => 7 + x

2 ** 2 ** 2 => 16

4 and 5 and x and 6 => x and 6

4 or 5 or x => 4

4 and 5 and ~6 => -7


When combined with patch 1346214, the compiler will
also optimize statements like

if 2**2**2 - 16: expensive_computation() => nothing

The patch adds two new files: Include/optimize.h and
Python.optimize.c. This was done because I anticipate
adding more AST optimizations later using the same
visitor interface, and Python/compile.c is already very
crowded with byte code generation and bytecode
optimization. If new files aren't desired, I could
easily change the pass to add the extra code to compile.c

This patch combined with patch 1346214 passes the unit
tests on all the platforms I've tested it on, namely:
macos 10.3/ppc
linux/x86
linux/amd64
linux/ppc
linux/ia64

valgrind on linux/x86 does not reveal any additional
leaks or uninitialized accesses that aren't already in
the svn head.

Logged In: YES 
user_id=750513

the actual patch is missing...

Logged In: YES 
user_id=858364

Sorry, I'm new to the sourceforge patch tracker. The patch should be 
attached now.

Logged In: YES 
user_id=1188172

Neal, what do you think of this?

Logged In: YES 
user_id=80475

This should be compared to the constant folding already 
added to Py2.5 via the peepholer:
   dis.dis(compile('x=2+3', '', 'exec'))

Also, make sure it doesn't go over the top consuming 
memory for the likes of:

  '-' * 100
  (None,)*2000

Both of those should not be optimized away at compile-time.

Also, be sure not optimize away -0.0.  Thet is not the 
same as +0.0.  The distinction is important for branch 
cuts in cmath.

Logged In: YES 
user_id=858364

It avoids generating constant objects with sizes above 20 (in a similar fashion 
as the bytecode peepholer), and checks whether the operand of unary minus 
is non-zero in order to avoid changing -0.0.

As for the bytecode peephole optimizer, this AST constant folder performs 
quite similar optimizations, but optimizes partially constant and/or and 
comparative expressions in addition. This patch should however not be seen 
as a replacement for the bytecode constant folder, but rather as a 
complement. An optimizing compiler typically contains many forms of 
constant folding in the different phases of compilation, since many later 
optimizations benefit from constant folding (warranting early constant 
folding), and some optimizations might emit code that benefit from constant 
folding again (warranting late constant folding). For an example of the 
former, consider the statement

if 1-1: some_code()

both passes are able to transform this into

if 0: some_code()

but since the AST constant folder is run before the dead code eliminator at 
<http://python.org/sf/1346214>, these two together are able to optimize 
the if statement away altogether.

Note that this patch probably won't apply cleanly anymore, since it was 
written three months ago and the AST code has undergone quite a few 
changes since then. But if there is interest in applying this patch, I'll gladly 
update it for the current trunk.

Logged In: YES 
user_id=80475

I'm +1 on the idea, but won't have an opportunity to 
review the patch in detail (to check for possible semantic 
changes).  Neal, what do you think?

Logged In: YES 
user_id=849994

Candidate for Iceland?

Logged In: YES 
user_id=33168

Shoot.  I missed this.  Bumping priority so hopefully I will
remember to take a look at this after 2.5 is out.  We still
need to split up compile.c along the lines of Jeremy's 2006
PyCon presentation (1-2 extra files).  I think one extra
file was for assembly.  I don't remember the details now.

Raymond wrote in his recent response on issue2499 (a patch that adds
unary '+' and 'not' folding to peephole optimizer):

"""
 More importantly, we decided that the peepholer is the wrong place to 
do much of this work.  Most of the peepholer is going to be migrated 
up the chain, after the AST is generated, but before the opcodes are 
generated.  That is a faster, more reliable, and more general 
approach.
""" (See msg64618.)

This looks like the relevant patch.  I would like to take a look at the
patch, but since it is more than 2 years old, maybe someone has an
updated version.  Please advise.

I'm working on the AST optimization code for 2.7 (?) in the
tlee-ast-optimize branch. I've since adopted some of the ideas from this
patch, but I'll take another look when I get a chance. The folding
operation is already mostly in-place.

FWIW, I'm working on fixing up the this patch to work against py3k; I'm assuming there's still interest in the AST visitor + specific optimization passes approach.

David, it would be great if an optional AST optimization pass could do something that we don't already have (perhaps, loop invariant code motion when python is called with -OO or somesuch).  The AST tree makes it possible for the first time to provide some non-trivial optimizations, so aim high.

I've been working on this against the py3k branch.  I'm attaching what I've got so far.

I foolishly didn't check the tlee-ast-optimize branch, instead using file6850 as a base.

Rune Holm/titanstar, I assume you've signed a PSF contributor agreement?

Changes since titanstar's original patch:
  - rework to apply against py3k
  - reformatted tabs to 4-space indentation; tried to reformat to PEP-7 as much as possible
  - added stmt types: With_kind, Nonlocal_kind
  - added expr types: IfExp_kind, Bytes_kind, SetComp_kind, DictComp_kind, Ellipsis_Kind
  - removed Print_kind, Exec_kind, Repr_kind
  - reworked Raise_kind
  - added "col_offset" and "arena" arguments; pass in the PyArena from the compiler as the context of the visitor
  - removal of all "free_expr" and "asdl_seq_free" calls on the assumption that PyArena now handles all of this (am I correct in thinking this?)
  - String -> Bytes in create_ast_from_constant_object
  - added test_optimize selftest suite, though this is based on bytecode disassembly, rather than direct inspection of the AST
  - I've fixed it up so it compiles and passes regrtest, but I suspect I've missed optimization possibilities

I did a little performance testing using the py3k version of the benchmark suite; currently it's a slight regression for some tests, a slight improvement for others; nothing impressive yet.

Thomas Lee's AST optimization branch (branched from r62457) has lots of interesting work:
  e.g. http://svn.python.org/view/python/branches/tlee-ast-optimize/Python/optimize.c?view=log

This appears to not be quite the same starting point; he added a PyCF_NO_OPTIMIZE flag to Include/pythonrun.h (and other places), which seems like a good way to see the effect of the optimization pass.  He also removed the peepholer; maybe it's worth doing that, but it seems worth at least keeping the test suite around to ensure a lack of regressions.

I can look at cherrypicking Thomas' work/porting it to py3k.

Re: "aiming high": I'd love to add new optimizations, but it's not clear to me what's permissable.  In particular, is it permissable for an optimization pass to assume that there are no external modifications to the locals within a frame?

It's possible to write code like this:
    frame = inspect.currentframe()
    inspect.getouterframes(frame)[-depth][0].f_locals[name] = value
to manipulate locals; whether or not this actually affects running code in the current implementation of CPython seems hit-or-miss to me right now, I think depending on exactly when fastlocals get written back to the f_locals dictionary (I could have miswritten the precise code).

By strategically manipulating locals in other frames, we can break pretty-much any typical compiler optimization: locals can appear or change from under us, or change attribute values, or gain side-effects to their __getattr__ (e.g. writing to disk).

If it is permissable for an optimization pass to assume that there are no external modifications to the locals within a frame, then issue 4264 might be one to investigate: this is a patch on top of Tom Lee's work (to do local type-inference to replace list.append with LIST_APPEND).   Ideas for other optimizations would be most welcome.

Another optimization idea: detect local dictionaries that are only ever used in non-mutating ways, and convert them to constants, rather than rebuilding the dict from scratch each time.

See e.g. htmlparser.py:adjustSVGAttributes etc within the bm_html5lib benchmark (though this doesn't seem to be ported to py3k yet)

ISTM that you don't need to worry about mutating locals, the locals() function is explicitly documented as not necessarily affecting local variables (not sure if frame objects have the same documentation).

If you want a free optimization opportunity: BINARY_SUBSCR with a list for the first argument who's contents are all constant, this can be optimized to turn it into a tuple which can be load const'd (as we do in the case of an in check), note that this cannot be used in the case of::

    l = [1, 2, 3]
    l[v]

As v.__index__ could theoretically mutate l.

#11549 Rewrite peephole to work on AST
includes constant folding. I have not compared.

8 years after the original patch, there's still no trivial constant folding in bytecode generated (because peephole of course is not a real optimizer to consistently catch all cases):

$ cat const.py 
FOO = 1
BAR = FOO + 2 + 4

$ python --version
Python 2.7.3

$ python -OO -m dis const.py
  1           0 LOAD_CONST               0 (1)
              3 STORE_NAME               0 (FOO)

  2           6 LOAD_NAME                0 (FOO)
              9 LOAD_CONST               1 (2)
             12 BINARY_ADD          
             13 LOAD_CONST               2 (4)
             16 BINARY_ADD          
             17 STORE_NAME               1 (BAR)
             20 LOAD_CONST               3 (None)
             23 RETURN_VALUE        

$ python3.3 --version
Python 3.3.3

$ python3.3 -OO -m dis const.py
  1           0 LOAD_CONST               0 (1) 
              3 STORE_NAME               0 (FOO) 

  2           6 LOAD_NAME                0 (FOO) 
              9 LOAD_CONST               1 (2) 
             12 BINARY_ADD           
             13 LOAD_CONST               2 (4) 
             16 BINARY_ADD           
             17 STORE_NAME               1 (BAR) 
             20 LOAD_CONST               3 (None) 
             23 RETURN_VALUE

My astoptimizer project has an experimental support of constant folding. It works in the same file, or constants can be propagated to other files using config.add_constant('NAME', value).

https://bitbucket.org/haypo/astoptimizer/

I applaud any effort to move constant folding out of the peepholer and into AST.

Have been implemented in issue29469.