Repository navigation
A constant folding optimization pass for the AST #42545
Description
| BPO | 1346238 |
|---|---|
| Nosy | @rhettinger, @terryjreedy, @pfalcon, @abalkin, @vstinner, @benjaminp, @alex, @methane, @davidmalcolm, @serhiy-storchaka |
| Superseder | |
| Files |
Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.
Show more details
GitHub fields:
assignee = None
closed_at = <Date 2017-12-14.13:12:04.894>
created_at = <Date 2005-11-02.18:49:15.000>
labels = ['interpreter-core', 'performance']
title = 'A constant folding optimization pass for the AST'
updated_at = <Date 2017-12-14.13:12:04.882>
user = 'https://bugs.python.org/titanstar'bugs.python.org fields:
activity = <Date 2017-12-14.13:12:04.882>
actor = 'serhiy.storchaka'
assignee = 'nnorwitz'
closed = True
closed_date = <Date 2017-12-14.13:12:04.894>
closer = 'serhiy.storchaka'
components = ['Interpreter Core']
creation = <Date 2005-11-02.18:49:15.000>
creator = 'titanstar'
dependencies = []
files = ['6850', '19513']
hgrepos = []
issue_num = 1346238
keywords = ['patch']
message_count = 21.0
messages = ['48953', '48954', '48955', '48956', '48957', '48958', '48959', '48960', '48961', '64646', '66388', '120516', '120541', '120562', '120563', '120566', '131393', '207130', '207202', '286389', '308295']
nosy_count = 15.0
nosy_names = ['jhylton', 'nnorwitz', 'rhettinger', 'terry.reedy', 'pfalcon', 'belopolsky', 'sdahlbac', 'titanstar', 'vstinner', 'thomaslee', 'benjamin.peterson', 'alex', 'methane', 'dmalcolm', 'serhiy.storchaka']
pr_nums = []
priority = 'normal'
resolution = 'duplicate'
stage = 'resolved'
status = 'closed'
superseder = '29469'
type = 'performance'
url = 'https://bugs.python.org/issue1346238'
versions = ['Python 3.3']
Activity
titanstar commentedon Nov 2, 2005
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
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.
sdahlbac commentedon Nov 6, 2005
Logged In: YES
user_id=750513
the actual patch is missing...
titanstar commentedon Nov 6, 2005
Logged In: YES
user_id=858364
Sorry, I'm new to the sourceforge patch tracker. The patch should be
attached now.
birkenfeld commentedon Feb 19, 2006
Logged In: YES
user_id=1188172
Neal, what do you think of this?
rhettinger commentedon Feb 19, 2006
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.
titanstar commentedon Feb 19, 2006
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
both passes are able to transform this into
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.
rhettinger commentedon Feb 19, 2006
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?
birkenfeld commentedon May 17, 2006
Logged In: YES
user_id=849994
Candidate for Iceland?
nnorwitz commentedon Jul 30, 2006
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.
abalkin commentedon Mar 28, 2008
Raymond wrote in his recent response on bpo-2499 (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.
thomaslee commentedon May 8, 2008
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.
davidmalcolm commentedon Nov 5, 2010
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.
rhettinger commentedon Nov 5, 2010
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.
davidmalcolm commentedon Nov 5, 2010
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:
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 bpo-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.
davidmalcolm commentedon Nov 6, 2010
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)
alex commentedon Nov 6, 2010
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::
As v.__index__ could theoretically mutate l.
terryjreedy commentedon Mar 19, 2011
bpo-11549 Rewrite peephole to work on AST
includes constant folding. I have not compared.
pfalcon commentedon Jan 1, 2014
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
vstinner commentedon Jan 3, 2014
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/
rhettinger commentedon Jan 27, 2017
I applaud any effort to move constant folding out of the peepholer and into AST.
serhiy-storchaka commentedon Dec 14, 2017
Have been implemented in bpo-29469.