This patch adds the following: A visitor interfacegeneralized from the existing ast pass code in order tomake it easy to write ast passes that only care aboutspecific node types. A constant folding pass that looksfor operations involving number or string literals, andcalculates these at compile time. Example code snippetsthat this pass will optimize:3 + 4 + x => 7 + x2 ** 2 ** 2 => 164 and 5 and x and 6 => x and 64 or 5 or x => 44 and 5 and ~6 => -7When combined with patch 1346214, the compiler willalso optimize statements likeif 2**2**2 - 16: expensive_computation() => nothingThe patch adds two new files:Include/optimize.h andPython.optimize.c. This was done because I anticipateadding more AST optimizations later using the samevisitor interface, andPython/compile.c is already verycrowded with byte code generation and bytecodeoptimization. If new files aren't desired, I couldeasily change the pass to add the extra code to compile.cThis patch combined with patch 1346214 passes the unittests on all the platforms I've tested it on, namely:macos 10.3/ppclinux/x86linux/amd64linux/ppclinux/ia64valgrind on linux/x86 does not reveal any additionalleaks or uninitialized accesses that aren't already inthe svn head.

Logged In: YES user_id=750513the actual patch is missing...

Logged In: YES user_id=858364Sorry, I'm new to the sourceforge patch tracker. The patch should be attached now.

Logged In: YES user_id=1188172Neal, what do you think of this?

Logged In: YES user_id=80475This 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,)*2000Both 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=858364It 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 statementif 1-1: some_code()both passes are able to transform this intoif 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=80475I'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=849994Candidate for Iceland?

Logged In: YES user_id=33168Shoot.  I missed this.  Bumping priority so hopefully I willremember to take a look at this after 2.5 is out.  We stillneed to split up compile.c along the lines of Jeremy's 2006PyCon presentation (1-2 extra files).  I think one extrafile was for assembly.  I don't remember the details now.

Raymond wrote in his recent response onissue2499 (a patch that addsunary '+' 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.""" (Seemsg64618.)This looks like the relevant patch.  I would like to take a look at thepatch, but since it is more than 2 years old, maybe someone has anupdated version.  Please advise.

I'm working on the AST optimization code for 2.7 (?) in thetlee-ast-optimize branch. I've since adopted some of the ideas from thispatch, but I'll take another look when I get a chance. The foldingoperation 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 usingfile6850 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 possibilitiesI 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 fromr62457) has lots of interesting work:  e.g.http://svn.python.org/view/python/branches/tlee-ast-optimize/Python/optimize.c?view=logThis appears to not be quite the same starting point; he added a PyCF_NO_OPTIMIZE flag toInclude/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] = valueto 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, thenissue 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 ASTincludes 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 = 1BAR = FOO + 2 + 4$ python --versionPython 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 --versionPython 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 inissue29469.