classification
Title: Build-out an AST optimizer, moving some functionality out of the peephole optimizer
Type: Stage:
Components: Interpreter Core Versions: Python 3.4
process
Status: open Resolution:
Dependencies: 11682 Superseder:
Assigned To: Nosy List: Jeremy.Hylton, Trundle, alex, benjamin.peterson, berker.peksag, brett.cannon, daniel.urban, dmalcolm, eltoder, eric.snow, georg.brandl, gregory.p.smith, haypo, isoschiz, jcon, mark.dickinson, meador.inge, nadeem.vawda, ncoghlan, pconnell, pitrou, rhettinger, santoso.wijaya, techtonik, terry.reedy
Priority: normal Keywords: patch

Created on 2011-03-15 04:46 by eltoder, last changed 2014-03-30 19:47 by berker.peksag.

Files
File name Uploaded Description Edit
0_ast.patch eltoder, 2011-03-15 04:47
0_fold.patch eltoder, 2011-03-15 04:47
0_compile.patch eltoder, 2011-03-15 04:47
0_generated.patch eltoder, 2011-03-15 04:48
0_tests.patch eltoder, 2011-03-15 04:48
Messages (52)
msg130955 - (view) Author: Eugene Toder (eltoder) Date: 2011-03-15 04:46
As pointed out by Raymond, constant folding should be done on AST rather than on generated bytecode. Here's a patch to do that. It's rather long, so overview first.

The patch replaces existing peephole pass with a folding pass on AST and a few changes in compiler. Feature-wise it should be on par with old peepholer, applying optimizations more consistently and thoroughly, but maybe missing some others. It passes all peepholer tests (though they seem not very extensive) and 'make test', but more testing is, of course, needed.

I've split it in 5 pieces for easier reviewing, but these are not 5 separate patches, they should all be applied together. I can upload it somewhere for review or split it in other ways, let me know. Also, patches are versus 1e00b161f5f5, I will redo against head.

TOC:
1. Changes to AST
2. Folding pass
3. Changes to compiler
4. Generated files (since they're checked in)
5. Tests

In detail:

1. I needed to make some changes to AST to enable constant folding. These are
a) Merge Num, Str, Bytes and Ellipsis constructors into a single Lit (literal) that can hold anything. For one thing, this removes a good deal of copy-paste in the code, since these are always treated the same. (There were a couple of places where Bytes ctor was missing for no apparent reason, I think it was forgotten.) Otherwise, I would have to introduce at least 4 more node types: None, Bool, TupleConst, SetConst. This seemed excessive.
b) Docstring is now an attribute of Module, FunctionDef and ClassDef, rather than a first statement. Docstring is a special syntactic construction, it's not an executable code, so it makes sense to separate it. Otherwise, optimizer would have to take extra care not to introduce, change or remove docstring. For example:

def foo():
  "doc" + "string"

Without optimizations foo doesn't have a docstring. After folding, however, the first statement in foo is a string literal. This means that docstring depends on the level of optimizations. Making it an attribute avoids the problem.
c) 'None', 'True' and 'False' are parsed as literals instead of names, even without optimizations. Since they are not redefineable, I think it makes most sense to treat them as literals. This isn't strictly needed for folding, and I haven't removed all the artefacts, in case this turns out controversial.

2. Constant folding (and a couple of other tweaks) is performed by a visitor. The visitor is auto-generated from ASDL and a C template. C template (Python/ast_opt.ct) provides code for optimizations and rules on how to call it. Parser/asdl_ct.py takes this and ASDL and generates a visitor, that visits only nodes which have associated rules (but visits them via all paths).
The code for optimizations itself is pretty straight-forward.
The generator can probably be used for symtable.c too, removing ~200 tedious lines of code. 

3. Changes to compiler are in 3 categories
a) Updates for AST changes.
b) Changes to generate better code and not need any optimizations. This includes tuple unpacking optimization and if/while conditions.
c) Simple peephole pass on compiler internal structures. This is a better form for doing this, than a bytecode. The pass only deals with jumps to jumps/returns and trivial dead code.
I've also made 'raise' recognized as a terminator, so that 'return None' is not inserted after it.

4, 5. No big surprises here.
msg131070 - (view) Author: Skip Montanaro (skip.montanaro) * (Python committer) Date: 2011-03-15 23:50
I'm confused.  Why aren't there review links?
msg131071 - (view) Author: Eugene Toder (eltoder) Date: 2011-03-15 23:51
Because I don't know how to make them. Any pointers?
msg131072 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2011-03-15 23:55
> Because I don't know how to make them. Any pointers?

Martin is hacking on the tool these days... So it's no surprise it
doesn't work perfectly yet ;)
If you have a Google account you can upload these patches to
http://codereview.appspot.com/, though.
msg131074 - (view) Author: Eugene Toder (eltoder) Date: 2011-03-16 00:16
Thanks. Review link: http://codereview.appspot.com/4281051
msg131083 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2011-03-16 02:52
The review links didn't come up automatically because 336137a359ae isn't a hg.python.org/cpython revision ID.
msg131084 - (view) Author: Eugene Toder (eltoder) Date: 2011-03-16 02:55
I see. Should I attach diffs vs. some revision from hg.python.org?
msg131085 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2011-03-16 03:07
No need, since you manually created a review on appspot. The local Reitveld links are just a convenience that can avoid the need to manually create a review instance.
msg131166 - (view) Author: Eugene Toder (eltoder) Date: 2011-03-16 20:13
Any comments on the code so far or suggestions on how we should move forward?
msg131172 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2011-03-16 20:34
I've been focusing on softer targets during the sprints - I'll dig into this once I'm back home and using my desktop machine again.
msg131210 - (view) Author: Eugene Toder (eltoder) Date: 2011-03-17 02:02
I've updated patches on Rietveld with some small changes. This includes better code generation for boolops used outside of conditions and cleaned up optimize_jumps(). This is probably the last change before I get some feedback.
Also, I forgot to mention yesterday, patches on Rietveld are vs. ab45c4d0b6ef
msg131214 - (view) Author: Eugene Toder (eltoder) Date: 2011-03-17 04:12
Just for fun I've run pystones. W/o my changes it averages to about 70k, with my changes to about 72.5k.
msg131392 - (view) Author: Terry J. Reedy (terry.reedy) * (Python committer) Date: 2011-03-19 05:27
A couple of somewhat related issues:
#10399 AST Optimization: inlining of function calls
#1346238 A constant folding optimization pass for the AST
Obviously, ast optimizers should work together and not duplicate.
Nice to see increased attention.
msg131396 - (view) Author: Eugene Toder (eltoder) Date: 2011-03-19 06:02
AFAICT my patch has everything that #1346238 has, except BoolOps, which can be easily added (there's a TODO). I don't want to add any new code, though, until the current patch will get reviewed -- adding code will only make reviewing harder.

#10399 looks interesting, I will take a look.
msg131952 - (view) Author: Eugene Toder (eltoder) Date: 2011-03-24 02:40
Is anyone looking or planing to look at the patch?
msg131953 - (view) Author: Terry J. Reedy (terry.reedy) * (Python committer) Date: 2011-03-24 02:45
I suspect someone will sometime. There is bit of a backlog of older issues.
msg132310 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2011-03-27 11:15
Finally got around to reviewing this (just a visual scan at this stage) - thanks for the effort. These are mostly "big picture" type comments, so I'm keeping them here rather than burying them amongst all the details in the code review tool.

The effect that collapsing Num/Str/Bytes into a single Lit node type has on ast.literal_eval bothered me initially, but looking more closely, I think those changes will actually improve the function (string concatenation will now work, and errors like "'hello' - 'world'" should give a more informative TypeError). (Bikeshed: We use Attribute rather than Attr for that node type, perhaps the full "Literal" name would be better, too)

Lib/test/disutil.py should really be made a feature of the dis module itself, by creating an inner disassembly function that returns a string, then making the existing "dis" and "disassembly" functions print that string (i.e. similar to what I already did in making dis.show_code() a thin wrapper around the new dis.code_info() function in 3.2). In the absence of a better name, "dis_to_str" would do.

Since the disassembly is interpreter specific, the new disassembly tests really shouldn't go directly in test_compile.py. A separate "test_ast_optimiser" file would be easier for alternate implementations to skip over. A less fragile testing strategy may also be to use the ast.PyCF_ONLY_AST flag and check the generated AST rather than the generated bytecode.

I'd like to see a written explanation for the first few changes in test_peepholer.py. Are those cases no longer optimised? Are they optimised differently? Why did these test cases have to change? (The later changes in that file look OK, since they seem to just be updating tests to handle the more comprehensive optimisation)

When you get around to rebasing the patch on 3.3 trunk, don't forget to drop any unneeded "from __future__" imports.

The generated code for the Lit node type looks wrong: it sets v to Py_None, then immediately checks to see if v is NULL again.

Don't use "string" as a C type - use "char *" (and "char **" instead of "string *").

There should be a new compiler flag to skip the AST optimisation step.

A bunch of the compiler internal changes seem to make the basic flow of the generated assembly not match the incoming source code. It doesn't seem like a good idea to conflate these with the AST optimisation patch. If that means leaving the peepholer in to handle them for now, that's OK - it's fine to just descope the peepholer without removing it entirely.
msg132312 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2011-03-27 11:39
I think the biggest thing to take out of my review is that I strongly encourage deferring the changes for 5(b) and 5(c).

I like the basic idea of using a template-based approach to try to get rid of a lot of the boilerplate code currently needed for AST visitors.

Providing a hook for optimisation in Python (as Dave Malcolm's approach does) is valuable as well, but I don't think the two ideas need to be mutually exclusive.

As a more general policy question... where do we stand in regards to backwards compatibility of the AST? The ast module docs don't have any caveats to say that it may change between versions, but it obviously *can* change due to new language constructs (if nothing else).
msg132313 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2011-03-27 11:44
> As a more general policy question... where do we stand in regards to
> backwards compatibility of the AST? The ast module docs don't have any
> caveats to say that it may change between versions, but it obviously
> *can* change due to new language constructs (if nothing else).

Yes, but can existing constructs produce a different structure from one
Python version to another?
It seems to me that the ast module is the recommended way to inspect the
structure of Python code (much more so that bytecode or concrete syntax
trees). Perhaps the optimizations can leave the initial ast intact?
Perhaps with an additional API to get the optimized ast as well?
msg132314 - (view) Author: Georg Brandl (georg.brandl) * (Python committer) Date: 2011-03-27 11:50
I would provide this via another compile flag a la PyCF_ONLY_AST.  If you give only this flag, you get the original AST.  If you give (e.g.)
PyCF_OPTIMIZED_AST, you get the resulting AST after the optimization stage (or the same, if optimization has been disabled).
msg132346 - (view) Author: Eugene Toder (eltoder) Date: 2011-03-27 16:15
Thanks.

> string concatenation will now work, and errors like "'hello' - 'world'"
> should give a more informative TypeError
Yes, 'x'*5 works too.

> Bikeshed: We use Attribute rather than Attr for that node type,
> perhaps the full "Literal" name would be better
Lit seemed more in line with Num, Str, BinOp etc. No reason it can't be changed, of course.

> Lib/test/disutil.py should really be made a feature of the dis module
> itself
Agreed, but I didn't want to widen the scope of the patch. If this is something that can be reviewed quickly, I can make a change to dis. I'd add a keyword-only arg to dis and disassembly -- an output stream defaulting to stdout. dis_to_str then passes StringIO and returns the string. Sounds OK?

> Since the disassembly is interpreter specific, the new disassembly
> tests really shouldn't go directly in test_compile.py. A separate
> "test_ast_optimiser" file would be easier for alternate
> implementations to skip over.
New tests in test_compiler are not for the AST pass, but for changes to compile.c. I can split them out, how about test_compiler_opts?

> I'd like to see a written explanation for the first few changes in
> test_peepholer.py
Sure.
1) not x == 2 can be theoretically optimized to x != 2, while this test is for another optimization. not x is more robust.
2) Expression statement which is just a literal doesn't produce any code at all. This is now true for None/True/False as well. To preserve constants in the output I've put them in tuples.

> When you get around to rebasing the patch on 3.3 trunk, don't forget
> to drop any unneeded "from __future__" imports.
If you're referring to asdl_ct.py, that's actually an interesting question. asdl_ct.py is run by system installed python2, for obvious reasons. What is the policy here -- what is the minimum version of system python that should be sufficient to build python3? I tested my code on 2.6 and 3.1, and with __future__ it should work on 2.5 as well. Is this OK or should I drop 'with' so it runs on 2.4?

> The generated code for the Lit node type looks wrong: it sets v to
> Py_None, then immediately checks to see if v is NULL again.
Right, comment in asdl_c.py says:
# XXX: special hack for Lit. Lit value can be None and it
#  should be stored as Py_None, not as NULL.
If there's a general agreement on Lit I can certainly clean this up.

> Don't use "string" as a C type - use "char *" (and "char **" instead
> of "string *").
string is a typedef for PyObject that ASDL uses. I don't think I have a choice to not use it. Can you point to a specific place where char* could be used?

> There should be a new compiler flag to skip the AST optimisation step.
There's already an 'optimizations level' flag. Maybe we should make it more meaningful rather than multiplying the number of flags?

> A bunch of the compiler internal changes seem to make the basic flow
> of the generated assembly not match the incoming source code.
Can you give an example of what you mean?
The changes are basically 1) standard way of handling conditions in simple compilers 2) peephole.

> It doesn't seem like a good idea to conflate these with the AST
> optimisation patch. If that means leaving the peepholer in to handle
> them for now, that's OK - it's fine to just descope the peepholer
> without removing it entirely.
The reason why I think it makes sense to have this in a single change is testing. This allows to reuse all existing peephole tests. If I leave old peephole enabled there's no way to tell if my pass did something from disassembly. I can port tests to AST, but that seemed like more work than match old peepholer optimizations.
Is there any opposition to doing simple optimizations on compiler structures? They seem a good fit for the job. In fact, if not for stack representation, I'd say that they are better IR for optimizer than AST.

Also, can I get your opinion on making None/True/False into literals early on and getting rid of forbidden_name?

Antoine, Georg -- I think Nick's question is not about AST changing after optimizations (this can indeed be a separate flag), but the structure of AST changing. E.g. collapsing of Num/Str/Bytes into Lit.

Btw, if this is acceptable I'd make a couple more changes to make scope structure obvious from AST. This will allow auto-generating much of the symtable pass.
msg132348 - (view) Author: Eugene Toder (eltoder) Date: 2011-03-27 16:25
> and with __future__ it should work on 2.5 as well.
Actually, seems that at least str.format is not in 2.5 as well. Still the question is should I make it run on 2.5 or 2.4 or is 2.6 OK (then __future__ can be removed).
msg132349 - (view) Author: Daniel Urban (daniel.urban) * Date: 2011-03-27 16:26
> not x == 2 can be theoretically optimized to x != 2, ...

I don't think it can:

>>> class X:
...     def __eq__(self, other):
...             return True
...     def __ne__(self, other):
...             return True
... 
>>> x = X()
>>> 
>>> not x == 2
False
>>> x != 2
True
>>>
msg132350 - (view) Author: Eugene Toder (eltoder) Date: 2011-03-27 16:30
> I don't think it can:
That already doesn't work in dict and set (eq not consistent with hash), I don't think it's a big problem if that stops working in some other cases. Anyway, I said "theoretically" -- maybe after some conservative type inference.
msg132361 - (view) Author: Eugene Toder (eltoder) Date: 2011-03-27 19:52
Also, to avoid any confusion -- currently my patch only runs AST optimizations before code generation, so compile() with ast.PyCF_ONLY_AST returns non-optimized AST.
msg132362 - (view) Author: Terry J. Reedy (terry.reedy) * (Python committer) Date: 2011-03-27 20:18
While I would not be happy to use class X above, the 3.2 manual explicitly says "There are no implied relationships among the comparison operators. The truth of x==y does not imply that x!=y is false. " .
msg132382 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2011-03-28 03:52
OK, I missed the fact that the new optimisation pass isn't run under PyCF_ONLY_AST.

However, as Eugene picked up, my concern is actually with the collapsing of Str/Num/Bytes/Ellipsis into the new Lit node, and the changes to the way None/True/False are handled. They're all changes that *make sense*, but would also likely cause a variety of AST manipulations to break. We definitely don't care when bytecode hacks break, but providing the ast module means that AST manipulation is officially supported.

However, the reason I bring up new constructs, is the fact that new constructs may break AST manipulation passes, even if the old structures are left intact - the AST visitor may miss (or misinterpret) things because it doesn't understand the meaning of the new nodes.

We may need to take this one back to python-dev (and get input from the other implementations as well). It's a fairly fundamental question when it comes to the structure of any changes.
msg132453 - (view) Author: Eugene Toder (eltoder) Date: 2011-03-29 01:31
If we have to preserve backward compatibility of Python AST API, we can do this relatively easily (at the expense of some code complexity):
* Add 'version' argument to compile() and ast.parse() with default value of 1 (old AST). Value 2 will correspond to the new AST.
* Do not remove Num/Str/Bytes/Ellipsis Python classes. Make PyAST_obj2mod and PyAST_mod2obj do appropriate conversions when version is 1.
* Possibly emit a PendingDeprecationWarning when version 1 is used with the goal of removing it in 3.5

Alternative implementation is to leave Num/Str/etc classes in C as well, and write visitors (similar to folding one) to convert AST between old and new forms.

Does this sounds reasonable? Should this be posted to python-dev? Should I write a PEP (I'd need some help with this)?

Are there any other big issues preventing this to be merged?
msg132455 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2011-03-29 01:52
Eugene, I think you're doing great work here and would like to see you succeed.  In the near term, I don't have time to participate, but don't let that stop you.
msg132473 - (view) Author: anatoly techtonik (techtonik) Date: 2011-03-29 08:56
Is there any tool to see how it works step-by-step. The whole stuff is extremely interesting, but I can't fit all the details of AST processing in my head.
msg132476 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2011-03-29 10:47
Eugene: I suggest raising the question on python-dev. The answer potentially affects the PEP 380 patch as well (which adds a new attribute to the "Yield" node).

Anatoly: If you just want to get a feel for the kind of AST various pieces of code produce, then the "ast.dump" function (along with using the ast.PyCF_ONLY_AST flag in compile) may be enough.

You may also want to take a look at the AST -> dot file conversion code in Dave Malcolm's patches on #10399.
msg137785 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2011-06-07 03:36
Eugene raised the question of AST changes on python-dev [1] and the verdict was that so long as ast.__version__ is updated, AST clients will be able to cope with changes.

Benjamin Peterson made some subsequent changes to the AST (bringing the AST for try and with statements more in line with the concrete syntax, allowing source-to-source transforms to retain the original code structure).

This patch will probably need to be updated to be based on the latest version of the AST - I would be surprised if it applied cleanly to the current tip.

[1] http://mail.python.org/pipermail/python-dev/2011-April/110399.html
msg137788 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2011-06-07 05:53
Updated the title to reflect that the peephole optimizer will likely continue to exist but in a much simpler form.  Some complex peephole optimization such as constant folding can be handled more easily and more robustly at the AST level.

Other minor peephole optimizations such as jump-to-jump simplification as still bytecode level optimizations (ones that improve the quality of the generated code without visibility to higher level semantics).
msg137819 - (view) Author: Eugene Toder (eltoder) Date: 2011-06-07 12:17
Nick, if there's an interest in reviewing the patch I can update the it. I doubt it needs a lot of changes, given that visitor is auto-generated.

Raymond, the patch contains a rewrite of low-level optimizations to work before byte code generation, which simplifies them a great deal.
msg137906 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2011-06-08 13:47
As Raymond noted though, some of the block stack fiddling doesn't make sense until after the bytecode has already been generated. It's OK to have multiple optimisers at different layers, each taking care of the elements that are best suited to that level.

And yes, an updated patch against the current tip would be good. Of my earlier review comments, the ones I'd still like to see addressed are:
- finish clearing out the now redundant special casing of None/True/False
- separating out the non-AST related compiler tweaks (i.e. 3b and 3c and the associated test changes) into their own patch (including moving the relevant tests into a separate @cpython_only test case)

I'm still not 100% convinced on that latter set of changes, but I don't 
want my further pondering on those to hold up the rest of the patch. (they probably make sense, it's just that the AST level changes are much easier to review than the ones right down at the bytecode generation level - reviewing the latter means getting back up to speed on precisely how the block stack works and it will be a while before I get around to doing that. It's just one of those things where the details matter, but diving that deep into the compiler is such a rare occurrence that I have to give myself a refresher course each time it happens).
msg138413 - (view) Author: Eugene Toder (eltoder) Date: 2011-06-16 03:26
I found a problem in constant de-duplication, already performed by compiler, that needs to be fixed before this change can be merged. 

Compiler tries to eliminate duplicate constants by putting them into a dict. However, "duplicate" in this case doesn't mean just "equal", we need a stronger relationship, as there are many equal values that behave differently in some contexts, e.g. 0 and 0.0 and False or 0.0 and -0.0. To this end for each value we create a tuple of the value and it's type and have some logic for -0.0. This is handled in compiler_add_o in Python/compile.c.

This logic, however, only works for scalar values -- if we get a container with 0 and the same container with False we collapse them into one. This was not a problem before, because constant tuples were only created by peephole, which doesn't attempt de-duplication. If tuple folding is moved to AST we start hitting this problem:

>>> dis(lambda: print((0,1),(False,True)))
  1           0 LOAD_GLOBAL              0 (print)
              3 LOAD_CONST               1 ((0, 1))
              6 LOAD_CONST               1 ((0, 1))
              9 CALL_FUNCTION            2
             12 RETURN_VALUE

The cleanest solution seems to be to introduce a new rich comparison code: Py_EQUIV (equivalent) and implement it at least in types that we support in marshal. This will simplify compiler_add_o quite a bit and make it work for tuples and frozensets.
I'm open to other suggestions.
msg139395 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2011-06-29 06:21
Marking the PEP 380 implementation as a dependency, as I expect it to be easier to update this patch to cope with those changes than it would be the other way around.
msg160608 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2012-05-14 11:50
Bumping the target version to 3.4.

This is still a good long term idea, but it's a substantial enough change that we really want to land it early in a development cycle so we have plenty of time to hammer out any issues.
msg160662 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2012-05-14 20:28
Good call, Nick.
msg168146 - (view) Author: Terry J. Reedy (terry.reedy) * (Python committer) Date: 2012-08-13 21:29
In msg132312 Nick asked "where do we stand in regards to backwards compatibility of the AST?"

The current ast module chapter, second sentence, says ""The abstract syntax itself might change with each Python release;" this module helps to find out programmatically what the current grammar looks like."
where 'current grammar' is copied in 30.2.2. Abstract Grammar.

I do not know when that was written, but it clearly implies the the grammark, which defines node classes, is x.y version specific. I think this is the correct policy just so we can make changes, hopefully improvements, such as the one proposed here.
msg169894 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2012-09-05 23:48
I'm working on a AST optimizer for Python 2.6-3.3:
https://bitbucket.org/haypo/astoptimizer

It is implemented in Python and is able to optimize much more cases than the current bytecode peepholer.
msg169895 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2012-09-06 00:11
All of the optimisations that assume globals haven't been shadowed or rebound are invalid in the general case.

E.g. print(1.5) and print("1.5") are valid for *our* print function, but we technically have no idea if they're equivalent in user code.

In short, if it involves a name lookup and that name isn't reserved to the compiler (e.g. __debug__) then no, you're not allowed to optimise it at compile time if you wish to remain compliant with the language spec. Method calls on literals are always fair game, though (e.g. you could optimise "a b c".split())

Any stdlib AST optimiser would need to be substantially more conservative by default.
msg169896 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2012-09-06 00:25
> All of the optimisations that assume globals haven't been shadowed
> or rebound are invalid in the general case.

My main idea is that the developer of the application should be able to annotate functions and constants to declare them as "optimizable" (constant). I chose to expect builtins as not being overrided, but if it breaks applications, it can be converted to an option disabled by default.

There is a known issue: test_math fails because pow() is an alias to matH.pow() in doctests. The problem is that "from math import *" is called and the result is stored in a namespace, and then "pow(2,4)" is called in the namespace. astoptimizer doesn't detect that pow=math.pow because locals are only set when the code is executed (and not at compilation) with something like: exec(code, namespace). It is a limitation of the optimizer. A workaround is to disable optimizations when running tests.

It is possible to detect that builtins are shadowed (ex: print=myprint). astoptimizer has an experimental support of assignments, but it only works on trivial examples yet (like "x=1; print(x)") and is disabled by default (because it is buggy). I also plan to disable some optimizations if globals(), vars() or dir() is called.
msg169897 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2012-09-06 00:40
> Any stdlib AST optimiser would need to be substantially more conservative by default.

FYI The test suite of Python 2.7 and 3.3 pass with astoptimizer... except some "minor" (?) failures:

 * test_math fails for the reason explained above
 * test_pdb: it looks to be an issue with line number (debuggers don't like optimizers :-))
 * test_xml_etree and test_xml_etree_c: reference count of the None singleton

The test suite helped me to find bugs in my optimizer :-)

I also had to add some hacks (hasattr) for test_ast (test_ast generates invalid AST trees). The configuration should also be adapted for test_peepholer, because CPython peepholer uses a limit of 20 items, whereas astoptimizer uses a limit of 4096 bytes/characters for string by default. All these minor nits are now handled in a specific "cpython_tests" config.
msg169898 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2012-09-06 00:48
No, you're assuming global program analysis and *that is not a valid assumption*.

One of the key features of Python is that *monkeypatching works*. It's not encouraged, but it works.

You simply cannot play games with name lookups like this without creating something that is no longer Python.
msg169899 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2012-09-06 00:50
You also have to be very careful of the interface to tracing functions, such as profilers and coverage analysis tools.
msg169900 - (view) Author: Eugene Toder (eltoder) Date: 2012-09-06 01:20
> Method calls on literals are always fair game, though (e.g. you could optimise "a b c".split())
What about optimizations that do not change behavior, except for different error messages? E.g. we can change
y = [1,2][x]
to
y = (1,2)[x]
where the tuple is constant and is stored in co_consts. This will, however, produce a different text in the exception when x is not 0 or 1. The type of exception is going to be the same.
msg169902 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2012-09-06 01:45
The peephole optimiser already makes optimisations like that in a couple of places (e.g. set -> frozenset):

>>> def f(x):
...    if x in {1, 2}: pass
...
>>> f.__code__.co_consts
(None, 1, 2, frozenset({1, 2}))

It's name lookup semantics that are the real minefield. It's one of the reasons PyPy's JIT can be so much more effective than a static optimiser - because it's monitoring real execution and inserting the appropriate guards it's not relying on invalid assumptions about name bindings.
msg169903 - (view) Author: Eugene Toder (eltoder) Date: 2012-09-06 03:42
If I'm not missing something, changing
x in [1,2]
to
x in (1,2)
and
x in {1,2}
to
x in frozenset([1,2])
does not change any error messages.

Agreed that without dynamic compilation we can pretty much only track literals (including functions and lambdas) assigned to local variables.
msg185286 - (view) Author: Brett Cannon (brett.cannon) * (Python committer) Date: 2013-03-26 18:05
http://bugs.python.org/issue17515 might also play into this if it happens to go in.
msg193656 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2013-07-24 15:21
Just noting for the record (since it appears it was never brought back to the comments): it is expected that programs that manipulate the AST may require updates before they will work on a new version of Python. Preserving AST backwards compatbility is too limiting to the evolution of the language, so only source compatibility is promised.
msg193657 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2013-07-24 15:22
(That was the outcome of the suggested AST discussions on python-dev that were mentioned earlier)
History
Date User Action Args
2014-03-30 19:47:10berker.peksagsetnosy: + berker.peksag
2014-03-30 06:04:57ncoghlanlinkissue21074 superseder
2013-07-24 15:22:31ncoghlansetmessages: + msg193657
2013-07-24 15:21:52ncoghlansetmessages: + msg193656
2013-04-19 21:24:41isoschizsetnosy: + isoschiz
2013-04-19 19:15:08pconnellsetnosy: + pconnell
2013-03-26 18:05:09brett.cannonsetmessages: + msg185286
2012-09-06 03:42:49eltodersetmessages: + msg169903
2012-09-06 01:45:36ncoghlansetmessages: + msg169902
2012-09-06 01:20:24eltodersetmessages: + msg169900
2012-09-06 00:50:25ncoghlansetmessages: + msg169899
2012-09-06 00:48:56ncoghlansetmessages: + msg169898
2012-09-06 00:40:49hayposetmessages: + msg169897
2012-09-06 00:25:24hayposetmessages: + msg169896
2012-09-06 00:11:42ncoghlansetmessages: + msg169895
2012-09-05 23:48:50hayposetnosy: + haypo
messages: + msg169894
2012-08-13 21:29:50terry.reedysetmessages: + msg168146
2012-07-25 03:10:25meador.ingesetnosy: + meador.inge
2012-07-23 12:43:45Jeremy.Hyltonsetnosy: + Jeremy.Hylton
2012-07-19 04:55:41gregory.p.smithsetnosy: + gregory.p.smith
2012-05-14 20:28:35rhettingersetmessages: + msg160662
2012-05-14 11:50:14ncoghlansetmessages: + msg160608
versions: + Python 3.4, - Python 3.3
2011-07-09 20:55:28eric.snowsetnosy: + eric.snow
2011-06-29 20:58:43jconsetnosy: + jcon
2011-06-29 06:21:51ncoghlansetdependencies: + PEP 380 reference implementation for 3.3
messages: + msg139395
2011-06-16 03:26:03eltodersetmessages: + msg138413
2011-06-08 13:47:10ncoghlansetmessages: + msg137906
2011-06-07 12:17:43eltodersetmessages: + msg137819
2011-06-07 05:53:33rhettingersetmessages: + msg137788
title: Rewrite peephole to work on AST -> Build-out an AST optimizer, moving some functionality out of the peephole optimizer
2011-06-07 03:36:55ncoghlansetmessages: + msg137785
2011-03-29 10:47:01ncoghlansetmessages: + msg132476
2011-03-29 08:56:37techtoniksetnosy: + techtonik
messages: + msg132473
2011-03-29 01:52:54rhettingersetmessages: + msg132455
2011-03-29 01:31:38eltodersetmessages: + msg132453
2011-03-28 03:52:34ncoghlansetmessages: + msg132382
2011-03-27 20:18:19terry.reedysetmessages: + msg132362
2011-03-27 19:52:53eltodersetmessages: + msg132361
2011-03-27 16:30:11eltodersetmessages: + msg132350
2011-03-27 16:26:11daniel.urbansetmessages: + msg132349
2011-03-27 16:25:01eltodersetmessages: + msg132348
2011-03-27 16:15:43eltodersetmessages: + msg132346
2011-03-27 11:50:50georg.brandlsetmessages: + msg132314
2011-03-27 11:44:43pitrousetmessages: + msg132313
2011-03-27 11:39:44ncoghlansetmessages: + msg132312
2011-03-27 11:15:23ncoghlansetmessages: + msg132310
2011-03-24 02:45:03terry.reedysetmessages: + msg131953
2011-03-24 02:40:21eltodersetmessages: + msg131952
2011-03-19 19:06:56skip.montanarosetnosy: - skip.montanaro
2011-03-19 09:46:03georg.brandlsetnosy: + georg.brandl
2011-03-19 06:02:25eltodersetnosy: skip.montanaro, brett.cannon, rhettinger, terry.reedy, mark.dickinson, ncoghlan, pitrou, nadeem.vawda, benjamin.peterson, alex, Trundle, dmalcolm, daniel.urban, santoso.wijaya, eltoder
messages: + msg131396
2011-03-19 05:27:41terry.reedysetnosy: + terry.reedy
messages: + msg131392
2011-03-19 05:23:26terry.reedylinkissue11462 superseder
2011-03-18 17:05:53nadeem.vawdasetnosy: + nadeem.vawda
2011-03-18 12:47:42mark.dickinsonsetnosy: + mark.dickinson
2011-03-17 04:12:22eltodersetnosy: skip.montanaro, brett.cannon, rhettinger, ncoghlan, pitrou, benjamin.peterson, alex, Trundle, dmalcolm, daniel.urban, santoso.wijaya, eltoder
messages: + msg131214
2011-03-17 02:02:56eltodersetnosy: skip.montanaro, brett.cannon, rhettinger, ncoghlan, pitrou, benjamin.peterson, alex, Trundle, dmalcolm, daniel.urban, santoso.wijaya, eltoder
messages: + msg131210
2011-03-16 23:32:15alexsetnosy: + alex
2011-03-16 20:34:47ncoghlansetnosy: skip.montanaro, brett.cannon, rhettinger, ncoghlan, pitrou, benjamin.peterson, Trundle, dmalcolm, daniel.urban, santoso.wijaya, eltoder
messages: + msg131172
2011-03-16 20:13:32eltodersetnosy: skip.montanaro, brett.cannon, rhettinger, ncoghlan, pitrou, benjamin.peterson, Trundle, dmalcolm, daniel.urban, santoso.wijaya, eltoder
messages: + msg131166
2011-03-16 03:07:42ncoghlansetnosy: skip.montanaro, brett.cannon, rhettinger, ncoghlan, pitrou, benjamin.peterson, Trundle, dmalcolm, daniel.urban, santoso.wijaya, eltoder
messages: + msg131085
2011-03-16 02:55:41eltodersetnosy: skip.montanaro, brett.cannon, rhettinger, ncoghlan, pitrou, benjamin.peterson, Trundle, dmalcolm, daniel.urban, santoso.wijaya, eltoder
messages: + msg131084
2011-03-16 02:52:00ncoghlansetnosy: skip.montanaro, brett.cannon, rhettinger, ncoghlan, pitrou, benjamin.peterson, Trundle, dmalcolm, daniel.urban, santoso.wijaya, eltoder
messages: + msg131083
2011-03-16 00:16:07eltodersetnosy: skip.montanaro, brett.cannon, rhettinger, ncoghlan, pitrou, benjamin.peterson, Trundle, dmalcolm, daniel.urban, santoso.wijaya, eltoder
messages: + msg131074
2011-03-15 23:55:43pitrousetnosy: skip.montanaro, brett.cannon, rhettinger, ncoghlan, pitrou, benjamin.peterson, Trundle, dmalcolm, daniel.urban, santoso.wijaya, eltoder
messages: + msg131072
2011-03-15 23:51:05eltodersetnosy: skip.montanaro, brett.cannon, rhettinger, ncoghlan, pitrou, benjamin.peterson, Trundle, dmalcolm, daniel.urban, santoso.wijaya, eltoder
messages: + msg131071
2011-03-15 23:50:08skip.montanarosetnosy: + skip.montanaro
messages: + msg131070
2011-03-15 22:20:36ncoghlansetnosy: + brett.cannon
2011-03-15 11:52:26ncoghlansetnosy: + dmalcolm, ncoghlan
2011-03-15 08:57:14daniel.urbansetnosy: + daniel.urban
2011-03-15 05:02:40pitrousetnosy: + benjamin.peterson
2011-03-15 05:00:57santoso.wijayasetnosy: + santoso.wijaya
2011-03-15 04:54:03Trundlesetnosy: + Trundle
2011-03-15 04:53:35eltodersetnosy: + rhettinger, pitrou
2011-03-15 04:48:11eltodersetfiles: + 0_tests.patch
2011-03-15 04:48:01eltodersetfiles: + 0_generated.patch
2011-03-15 04:47:46eltodersetfiles: + 0_compile.patch
2011-03-15 04:47:36eltodersetfiles: + 0_fold.patch
2011-03-15 04:47:18eltodersetfiles: + 0_ast.patch
keywords: + patch
2011-03-15 04:46:42eltodercreate