[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Raymond Hettinger]

Raymond Hettinger  added the comment:

I think this particular issue can be closed in now.  After it was written, the 
AST optimizer has been built-out and some peephole logic has moved.

Other adjustments and improvements can be continue to be done in the other open 
issues.

--
resolution:  -> fixed
stage:  -> resolved
status: open -> closed

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Brett Cannon]

Change by Brett Cannon :


--
nosy:  -brett.cannon

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Mateusz Bysiek]

Changes by Mateusz Bysiek :


--
nosy: +mbdevpl

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[STINNER Victor]

STINNER Victor added the comment:

I created the issue #29471: "AST: add an attribute to FunctionDef to 
distinguish functions from generators and coroutines".

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[INADA Naoki]

INADA Naoki added the comment:

I submit new issues:

* #29463 for AST change (change docstring from first statement to attribute).
* #29469 for constant folding

Note that this issue contains more peephole -> AST optimization changes.
But I want to start these two patch to ease review and discussion.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Alex Gaynor]

Changes by Alex Gaynor :


--
nosy:  -alex

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[STINNER Victor]

STINNER Victor added the comment:

Naoki: Can you please open a new issue for your ast-docstring.patch change? I 
like it, but this issue became too big, and I'm not sure that everyone in the 
nosy list is interested by this specific change.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[INADA Naoki]

INADA Naoki added the comment:

I've tried to update ast_opt.c[t] without changing AST.
But I can't find clear way to solve "foo" + "bar" docstring problem.

This patch adds only docstring to AST.

--
Added file: http://bugs.python.org/file46542/ast-docstring.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Gregory P. Smith]

Changes by Gregory P. Smith :


--
nosy:  -gregory.p.smith

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[STINNER Victor]

STINNER Victor added the comment:

INADA Naoki added the comment:
> My motivation is improve speed,

Ah, if the motivation is performance, I would like to see benchmark
results :-) I understand that an AST optimizer would help to produce
more efficient bytecode, right?

> reduce memory usage,

I noticed an issue with the peephole optimizer: the constant folding
step keeps original constants. Moving constant folding to the AST
stage fixes this issue by design.

> and quicker startup time for real world applications.

You mean faster import time on precompiled .pyc files, right? It's
related to the hypothetical faster bytecode.

> If some optimization in FAT optimizer has significant speedup, I want to try 
> it.

See http://fatoptimizer.readthedocs.io/en/latest/microbenchmarks.html#microbench

FYI it took me something like 2 months to build FAT Python
"infrastructure": fix CPython bugs, design guards, design the AST
optimizer, write unit tests, etc. I didn't spend much time on
efficient optimizations. But for my first rule was to not break the
CPython test suite! Not break the Python semantics, otherwise it would
be impossible to put enable the optimizer by default in CPython, which
is my long term goal.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[INADA Naoki]

INADA Naoki added the comment:

My motivation is improve speed, reduce memory usage, and quicker
startup time for real world applications.  If some optimization in
FAT optimizer has significant speedup, I want to try it.

But this time, my motivation is I felt "everyone think constant folding
should go to AST from peephole, there is a patch about it, but unfortunately
it was suspended (because of lack of reviewers, maybe)."

As reading #28813, I think there are consensus about constant folding
should go AST.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Eugene Toder]

Eugene Toder added the comment:

Yes, doing optimizations on AST in CPython is unlikely to give any sizable 
speed improvements in real world programs. Python as a language is not suited 
for static optimization, and even if you manage to inline a function, there's 
still CPython's interpreted overhead and boxed types that dwarf the effect of 
the optimization.

The goal of this patch was never to significantly improve the speed. It was to 
replace the existing bytecode peephole pass with cleaner and simpler code, 
which also happens to produce slightly better results.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[STINNER Victor]

STINNER Victor added the comment:

At the AST level, you have a wide range of possible optimizations. See the 
optimizations that I implemented in fatoptimizer (FAT Python) to have an idea:
http://fatoptimizer.readthedocs.io/en/latest/optimizations.html

FAT Python adds guards checked at runtime, something not possible (not wanted) 
here.

But if you start with constant folding, why not implementing constant 
propagation as well? What about loop unrolling?

Where is the limit? If you implement the AST optimizer in C, the limit will 
probably be your C skills and your motivation :-) In Python, the limit is more 
the Python semantics which is... hum... not well defined. For example, does it 
break the Python semantics to replace [i for i in (1, 2, 3)] with [1, 2, 3]? 

What if you use a debugger? Do yo expect a list comprehension or a literal list?

FYI I suspended my work on FAT Python because almost no other core developer 
was interested. I didn't get any support, whereas I need support to push core 
FAT Python features like function specialization and runtime checks (PEP 510, 
see also PEP 511). Moreover, I failed to show any significant speedup on 
non-trivial functions. I abandoned before investigating function inlining, even 
if FAT Python already has a basic support for function inlining.

This issue is open since 2011. The question is always the same: is it worth it?

An alternative is to experiment an AST optimizer outside CPython and come back 
later with more data to drive the design of such optimizer. With FAT Python, I 
chose to add hooks in the Python compiler, but different people told me that 
it's possible to do that without such hook but importlib (importlib hooks).

What do you think Naoki?

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Brett Cannon]

Brett Cannon added the comment:

Dropping ast.Lit is fine. As for the docstring part, I'm torn. Yes it's nice as 
that will show up semantically in the Python code, but it's also easy to check 
for by just looking if the first statement is a Str (or Constant if that's what 
we make all strings). So I'll say I'm +0 on the docstring part.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[INADA Naoki]

INADA Naoki added the comment:

Before trying advanced optimizations, I want move suspended obvious 
optimizations forwards.

For example, removing unused constants is suspended because constant folding
should be moved from peephole to AST.  This is why I found this issue.

After that, I'm thinking about shrinking stacksize. frame_dealloc (scans whole 
stack) is one of hot functions.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[STINNER Victor]

STINNER Victor added the comment:

If you would like to implement constant folding at the AST level, I suggest
you to look at my fatoptimizer project:
https://github.com/haypo/fatoptimizer/blob/master/fatoptimizer/const_fold.py

The tricky part is to avoid operations when we know that it will raise an
exception or create an object too big according to our constraints.

I would prefer to implement an AST optimizer in Python, but converting C
structures to Python objects and then back to C structures has a cost. I'm
not sure that my optimizer implemented in Python is fast enough.

By the way, an idea would be to skip all optimizations in some cases like
for script.py when running python3 script.py.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[INADA Naoki]

INADA Naoki added the comment:

>> We have already Constant and NameConstant.  So it seems there are no need for
>> None, Bool, TupleConst, SetConst nodes.
> Yes, Constant is Victor's version of Lit.

Then, may I remove ast.Lit, and use Constant and NameConstant?


>> I think converting Num, Str, Bytes, Ellipsis into Constant in folding stage
>> is easier than fixing all tests.
> Fixing tests was fairly easy the last time. I think the question is what 
> changes to the public API of AST are acceptable.

I think backward compatibility is not guaranteed.
But there are some usage of ast. 
(https://github.com/search?l=Python=2=ast.Num=Code=%E2%9C%93 )

So I think we should make change small as possible.


>> Take docstring before constant folding isn't enough?
>> (I'm sorry if I'm wrong.  I haven't tried it yet.)
> It may be doable, but seems very messy. Instead of a clean pipeline text -> 
> AST -> Optimized AST -> bytecode, you have to collect all docstrings, and 
> pass them around in a side structure.
>
> With the current code there can be a simple fix. If original string literals 
> are Str, but constant-folded string  constants are Constant, only treat Strs 
> as docstrings. Then the optimizer needs a change to always preserve Str as a 
> first statement in a function/module, and that's it.
> I still think that having a dedicated docstring attribute in AST is cleaner, 
> though.

OK.


>> They are all NameConstant already.
> Keep in mind this patch is 6 years old :)

I know. I want to move this patch forward, but I'm not frontend (parser, AST, 
and compiler) expert.
I can't make design decision without expert's advice.  Thanks for your reply.

Then, may I update the patch in following  direction?

* Remove ast.Lit.
* Keep docstring change.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Eugene Toder]

Eugene Toder added the comment:

> We have already Constant and NameConstant.  So it seems there are no need for
> None, Bool, TupleConst, SetConst nodes.
Yes, Constant is Victor's version of Lit.

> I think converting Num, Str, Bytes, Ellipsis into Constant in folding stage
> is easier than fixing all tests.
Fixing tests was fairly easy the last time. I think the question is what 
changes to the public API of AST are acceptable.

> Take docstring before constant folding isn't enough?
> (I'm sorry if I'm wrong.  I haven't tried it yet.)
It may be doable, but seems very messy. Instead of a clean pipeline text -> AST 
-> Optimized AST -> bytecode, you have to collect all docstrings, and pass them 
around in a side structure.

With the current code there can be a simple fix. If original string literals 
are Str, but constant-folded string constants are Constant, only treat Strs as 
docstrings. Then the optimizer needs a change to always preserve Str as a first 
statement in a function/module, and that's it.
I still think that having a dedicated docstring attribute in AST is cleaner, 
though.

> They are all NameConstant already.
Keep in mind this patch is 6 years old :)

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[INADA Naoki]

INADA Naoki added the comment:

> 1. Changes to AST

I'm working on updating this part. There are some failing tests remains. 
But I doubt this stage is worth enough for now.

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

We have already Constant and NameConstant.  So it seems there are no need for
None, Bool, TupleConst, SetConst nodes.

I think converting Num, Str, Bytes, Ellipsis into Constant in folding stage
is easier than fixing all tests.


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

Take docstring before constant folding isn't enough?
(I'm sorry if I'm wrong.  I haven't tried it yet.)


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

They are all NameConstant already.

--
Added file: http://bugs.python.org/file46467/change-ast.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Nick Coghlan]

Nick Coghlan added the comment:

Hugo, Serhiy, and Victor: I think you're all agreeing with each other, but to 
make sure I'm understanding the point correctly:

1. ast.literal_eval() is currently safe from malicious code like "10 ** 
10" or "1073741824 * 'a'" because it only traverses addition and 
subtraction nodes, so any such operations will just throw ValueError (As a 
point of interest: unary plus and minus are required to support positive and 
negative numeric literals, while binary addition and subtraction are required 
to support complex number literals. So the status quo isn't precisely the 
result of a conscious security decision, it's just a minimalist implementation 
of exactly what's necessary to support all of the builtin types, which also 
provides some highly desirable security properties when evaluating untrusted 
code)


2. an eager constant folding optimisation in the AST tier would happen *before* 
literal_eval filtered out the multiplication and exponentiation nodes, and 
hence would make literal_eval vulnerable to remote DOS attacks in cases where 
it is expected to be safe

However, that's not exactly how this patch works: if you pass "PyCF_ONLY_AST" 
as ast.parse does, it *doesn't* run the constant-folding step. Instead, the 
constant folding is run as an AST-to-AST transform during the AST-to-bytecode 
compilation step, *not* the initial source-to-AST step. (see 
http://bugs.python.org/issue11549#msg132361 )

This has a few nice properties:

- ast.literal_eval() remains safe
- source -> AST -> source transformation pipelines continue to preserve the 
original code structure
- externally generated AST structures still benefit from the AST optimisation 
pass
- we don't need a new flag to turn this optimisation pass off when generating 
the AST for a given piece of source code

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[STINNER Victor]

STINNER Victor added the comment:

> Currently there is no a bug in ast.literal_eval() because the '**' operator 
> is not accepted.

The doc says "This can be used for safely evaluating strings containing Python 
values from untrusted sources without the need to parse the values oneself. It 
is not capable of evaluating arbitrarily complex expressions, for example 
involving operators or indexing."
https://docs.python.org/dev/library/ast.html#ast.literal_eval

I don't think that it's a bug, but a deliberate design choice. a**b is an 
obvious trick to DoS a server (high CPU and memory usage).

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

> Since the Python compiler doesn't produce ast.Constant, there is no
change in practice in ast.literal_eval(). If you found a bug, please
open a new issue.

Currently there is no a bug in ast.literal_eval() because the '**' operator is 
not accepted.

>>> ast.literal_eval("2**2**32")
Traceback (most recent call last):
  File "", line 1, in 
  File "/home/serhiy/py/cpython/Lib/ast.py", line 85, in literal_eval
return _convert(node_or_string)
  File "/home/serhiy/py/cpython/Lib/ast.py", line 84, in _convert
raise ValueError('malformed node or string: ' + repr(node))
ValueError: malformed node or string: <_ast.BinOp object at 0xb6f2fa4c>

But if move the optimization to AST level this can add a vulnerability to DOS 
attack. The optimizer should do additional checks first than execute operators 
that can return too large value or take too much CPU time. Currently this 
vulnerability have place in the peephole optimizer.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

Good point Hugo. Yes, this should be taken into account when move constant 
folding to AST level. Thank you for the reminder.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[STINNER Victor]

STINNER Victor added the comment:

Hugo Geoffroy added the comment:
> I would like to point out that the changes in `ast.literal_eval` may have 
> some security risk for code that do not expect this function to return an 
> object with user-controlled length (for example, with `2**32*'X'`). AFAIK, 
> this is not possible with the current version of `literal_eval`.

Since the Python compiler doesn't produce ast.Constant, there is no
change in practice in ast.literal_eval(). If you found a bug, please
open a new issue.

> At least [this library](https://pypi.python.org/pypi/serpent) would have a 
> serious risk of remote DoS :

I tried hard to implement a sandbox in Python and I failed:
https://lwn.net/Articles/574215/

I don't think that literal_eval() is safe *by design*.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Hugo Geoffroy]

Hugo Geoffroy added the comment:

I would like to point out that the changes in `ast.literal_eval` may have some 
security risk for code that do not expect this function to return an object 
with user-controlled length (for example, with `2**32*'X'`). AFAIK, this is not 
possible with the current version of `literal_eval`.

At least [this library](https://pypi.python.org/pypi/serpent) would have a 
serious risk of remote DoS :

> Because it only serializes literals and recreates the objects using 
> ast.literal_eval(), the serialized data is safe to transport to other 
> machines (over the network for instance) and de-serialize it there.

Sorry for the noise if this is a useless/incorrect consideration.

--
nosy: +pstch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[STINNER Victor]

STINNER Victor added the comment:

> @haypo, how do you think about ast.Lit and ast.Constant?

I already made two changes in Python 3.6 :-)

I added ast.Constant to Python 3.6. While it's not used by .py=>AST compiler, 
it is understood by the AST->bytecode compiler (ex: handle correctly special 
cases like docstrings).
https://docs.python.org/dev/whatsnew/3.6.html#ast
=> issue #26146

Moreover, I also modified the format of the co_lnotab structure to support 
negative line number delta. So a code transformer can move instructions and 
preserve the Python traceback feature.
https://docs.python.org/dev/whatsnew/3.6.html#changes-in-the-python-api
=> see the PEP 511

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[INADA Naoki]

INADA Naoki added the comment:

@haypo, how do you think about ast.Lit and ast.Constant?
Is this patch updated to use ast.Constant?
Or ast.Constant should be used only for some transform like constant folding?

--
versions: +Python 3.7 -Python 3.6

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[INADA Naoki]

Changes by INADA Naoki :


--
nosy: +inada.naoki

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[STINNER Victor]

STINNER Victor added the comment:

> I also see that Victor has been doing some of the same work, e.g. #26146.

ast.Constant idea directly comes from your work. The implementatiln may ve
different.

It's a first step for AST optimizers.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Eugene Toder]

Eugene Toder added the comment:

Serhiy: Nice! Yes, _PyCode_ConstantKey solved the problem.

But #16619 went in the opposite direction of this patch, and introduced a new 
type of literal node instead of unifying the existing ones. Kind of a shame, 
since *this* patch, I believe, both fixes that bug and removes the unreachable 
code in the example :)

I also see that Victor has been doing some of the same work, e.g. #26146.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

Yes, the patch is outdated, conflicts with current code (and would conflict 
even more after pushing the wordcode patch) and contains bugs. But it moved in 
right direction, I think your _PyCode_ConstantKey() could help to fix bugs. I'm 
going to revive this issue.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Eugene Toder]

Eugene Toder added the comment:

Fairly sure it's 5 years old.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[STINNER Victor]

STINNER Victor added the comment:

"issue11549.patch: serhiy.storchaka, 2016-05-11 08:22: Regenerated for review"

diff -r 1e00b161f5f5 PC/os2emx/python33.def
--- a/PC/os2emx/python33.defWed Mar 09 12:53:30 2011 +0100
+++ b/PC/os2emx/python33.defWed May 11 11:21:24 2016 +0300

The revision 1e00b161f5f5 is 4 years old. The patch looks very outdated :-/

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

Regenerated for review.

--
nosy: +serhiy.storchaka
Added file: http://bugs.python.org/file42810/issue11549.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Nick Coghlan]

Changes by Nick Coghlan ncogh...@gmail.com:


--
versions: +Python 3.6 -Python 3.4

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue11549
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Berker Peksag]

Changes by Berker Peksag berker.pek...@gmail.com:


--
nosy: +berker.peksag

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue11549
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Nick Coghlan]

Nick Coghlan added the comment:

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.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue11549
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Nick Coghlan]

Nick Coghlan added the comment:

(That was the outcome of the suggested AST discussions on python-dev that were 
mentioned earlier)

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue11549
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Phil Connell]

Changes by Phil Connell pconn...@gmail.com:


--
nosy: +pconnell

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue11549
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Martin Morrison]

Changes by Martin Morrison m...@ensoft.co.uk:


--
nosy: +isoschiz

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue11549
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Brett Cannon]

Brett Cannon added the comment:

http://bugs.python.org/issue17515 might also play into this if it happens to go 
in.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue11549
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[STINNER Victor]

STINNER Victor added the comment:

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.

--
nosy: +haypo

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue11549
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Nick Coghlan]

Nick Coghlan added the comment:

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.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue11549
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[STINNER Victor]

STINNER Victor added the comment:

 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.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue11549
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[STINNER Victor]

STINNER Victor added the comment:

 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.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue11549
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Nick Coghlan]

Nick Coghlan added the comment:

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.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue11549
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Nick Coghlan]

Nick Coghlan added the comment:

You also have to be very careful of the interface to tracing functions, such as 
profilers and coverage analysis tools.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue11549
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Eugene Toder]

Eugene Toder added the comment:

 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.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue11549
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Nick Coghlan]

Nick Coghlan added the comment:

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.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue11549
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Eugene Toder]

Eugene Toder added the comment:

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.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue11549
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Terry J. Reedy]

Terry J. Reedy added the comment:

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.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue11549
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Meador Inge]

Changes by Meador Inge mead...@gmail.com:


--
nosy: +meador.inge

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue11549
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Jeremy Hylton]

Changes by Jeremy Hylton jhyl...@gmail.com:


--
nosy: +Jeremy.Hylton

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue11549
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Gregory P. Smith]

Changes by Gregory P. Smith g...@krypto.org:


--
nosy: +gregory.p.smith

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue11549
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Nick Coghlan]

Nick Coghlan ncogh...@gmail.com added the comment:

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.

--
versions: +Python 3.4 -Python 3.3

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue11549
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Raymond Hettinger]

Raymond Hettinger raymond.hettin...@gmail.com added the comment:

Good call, Nick.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue11549
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Eric Snow]

Changes by Eric Snow ericsnowcurren...@gmail.com:


--
nosy: +ericsnow

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue11549
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Nick Coghlan]

Nick Coghlan ncogh...@gmail.com added the comment:

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.

--
dependencies: +PEP 380 reference implementation for 3.3

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue11549
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[John O'Connor]

Changes by John O'Connor tehj...@gmail.com:


--
nosy: +jcon

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue11549
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Eugene Toder]

Eugene Toder elto...@gmail.com added the comment:

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_FUNCTION2
 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.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue11549
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Nick Coghlan]

Nick Coghlan ncogh...@gmail.com added the comment:

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).

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue11549
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Eugene Toder]

Eugene Toder elto...@gmail.com added the comment:

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.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue11549
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11549] Build-out an AST optimizer, moving some functionality out of the peephole optimizer

[Raymond Hettinger]

Raymond Hettinger raymond.hettin...@gmail.com added the comment:

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).

--
title: Rewrite peephole to work on AST - Build-out an AST optimizer, moving 
some functionality out of the peephole optimizer

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue11549
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com