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

[eltoder]

BPO	11549
Nosy	@birkenfeld, @rhettinger, @terryjreedy, @mdickinson, @ncoghlan, @pitrou, @vstinner, @benjaminp, @Trundle, @methane, @davidmalcolm, @meadori, @durban, @jeremyhylton, @eltoder, @ericsnowcurrently, @berkerpeksag, @serhiy-storchaka, @phmc, @pstch, @mbdevpl
Dependencies	bpo-11682: PEP 380 reference implementation for 3.3
Files	0_ast.patch 0_fold.patch 0_compile.patch 0_generated.patch 0_tests.patch issue11549.patch: Regenerated for review change-ast.patch ast-docstring.patch

^{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 2020-01-26.06:07:31.706>
created_at = <Date 2011-03-15.04:46:42.255>
labels = ['interpreter-core', '3.7']
title = 'Build-out an AST optimizer, moving some functionality out of the peephole optimizer'
updated_at = <Date 2020-01-26.06:07:31.705>
user = 'https://github.com/eltoder'

bugs.python.org fields:

activity = <Date 2020-01-26.06:07:31.705>
actor = 'rhettinger'
assignee = 'none'
closed = True
closed_date = <Date 2020-01-26.06:07:31.706>
closer = 'rhettinger'
components = ['Interpreter Core']
creation = <Date 2011-03-15.04:46:42.255>
creator = 'eltoder'
dependencies = ['11682']
files = ['21198', '21199', '21200', '21201', '21202', '42810', '46467', '46542']
hgrepos = []
issue_num = 11549
keywords = ['patch']
message_count = 81.0
messages = ['130955', '131070', '131071', '131072', '131074', '131083', '131084', '131085', '131166', '131172', '131210', '131214', '131392', '131396', '131952', '131953', '132310', '132312', '132313', '132314', '132346', '132348', '132349', '132350', '132361', '132362', '132382', '132453', '132455', '132473', '132476', '137785', '137788', '137819', '137906', '138413', '139395', '160608', '160662', '168146', '169894', '169895', '169896', '169897', '169898', '169899', '169900', '169902', '169903', '185286', '193656', '193657', '265296', '265553', '265554', '265607', '265613', '265621', '286503', '286528', '286530', '286531', '286532', '286534', '286535', '286539', '286542', '286588', '286589', '286591', '286592', '286668', '286697', '286725', '286726', '286730', '287120', '287121', '287187', '287217', '360721']
nosy_count = 26.0
nosy_names = ['georg.brandl', 'rhettinger', 'terry.reedy', 'mark.dickinson', 'ncoghlan', 'pitrou', 'vstinner', 'techtonik', 'nadeem.vawda', 'benjamin.peterson', 'Trundle', 'methane', 'dmalcolm', 'meador.inge', 'daniel.urban', 'Jeremy.Hylton', 'santoso.wijaya', 'eltoder', 'eric.snow', 'jcon', 'berker.peksag', 'serhiy.storchaka', 'pconnell', 'isoschiz', 'pstch', 'mbdevpl']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = None
url = 'https://bugs.python.org/issue11549'
versions = ['Python 3.7']

[eltoder]

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.

[smontanaro]

I'm confused. Why aren't there review links?

[eltoder]

Because I don't know how to make them. Any pointers?

[pitrou]

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.

[eltoder]

Thanks. Review link: http://codereview.appspot.com/4281051

[ncoghlan]

The review links didn't come up automatically because 336137a359ae isn't a hg.python.org/cpython revision ID.

[eltoder]

I see. Should I attach diffs vs. some revision from hg.python.org?

[ncoghlan]

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.

[eltoder]

Any comments on the code so far or suggestions on how we should move forward?

[ncoghlan]

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.

[eltoder]

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

[eltoder]

Just for fun I've run pystones. W/o my changes it averages to about 70k, with my changes to about 72.5k.

[terryjreedy]

A couple of somewhat related issues:
bpo-10399 AST Optimization: inlining of function calls
bpo-1346238 A constant folding optimization pass for the AST
Obviously, ast optimizers should work together and not duplicate.
Nice to see increased attention.

[eltoder]

AFAICT my patch has everything that bpo-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.

bpo-10399 looks interesting, I will take a look.