[Patches] [ python-Patches-1346238 ] A constant folding optimization pass for the AST

[SourceForge.net]

Patches item #1346238, was opened at 2005-11-02 18:49
Message generated for change (Comment added) made by gbrandl
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=1346238&group_id=5470

Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Category: Parser/Compiler
Group: Python 2.5
Status: Open
Resolution: None
Priority: 5
Submitted By: Rune Holm (titanstar)
Assigned to: Neal Norwitz (nnorwitz)
Summary: A constant folding optimization pass for the AST

Initial Comment:
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.


----------------------------------------------------------------------

>Comment By: Georg Brandl (gbrandl)
Date: 2006-05-17 15:54

Message:
Logged In: YES 
user_id=849994

Candidate for Iceland?

----------------------------------------------------------------------

Comment By: Raymond Hettinger (rhettinger)
Date: 2006-02-19 17:12

Message:
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?

----------------------------------------------------------------------

Comment By: Rune Holm (titanstar)
Date: 2006-02-19 13:35

Message:
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.


----------------------------------------------------------------------

Comment By: Raymond Hettinger (rhettinger)
Date: 2006-02-19 10:09

Message:
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.


----------------------------------------------------------------------

Comment By: Georg Brandl (birkenfeld)
Date: 2006-02-19 09:41

Message:
Logged In: YES 
user_id=1188172

Neal, what do you think of this?

----------------------------------------------------------------------

Comment By: Rune Holm (titanstar)
Date: 2005-11-06 20:42

Message:
Logged In: YES 
user_id=858364

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

----------------------------------------------------------------------

Comment By: Simon Dahlbacka (sdahlbac)
Date: 2005-11-06 19:10

Message:
Logged In: YES 
user_id=750513

the actual patch is missing...

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=1346238&group_id=5470