[issue11549] Rewrite peephole to work on AST

Eugene Toder report at bugs.python.org
Tue Mar 15 05:46:43 CET 2011


New submission from Eugene Toder <eltoder at gmail.com>:

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.

----------
components: Interpreter Core
messages: 130955
nosy: eltoder
priority: normal
severity: normal
status: open
title: Rewrite peephole to work on AST
versions: Python 3.3

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue11549>
_______________________________________


More information about the Python-bugs-list mailing list