classification
Title: AST-level Constant folding
Type: enhancement Stage: resolved
Components: Interpreter Core Versions: Python 3.7
process
Status: closed Resolution: fixed
Dependencies: 29463 Superseder:
Assigned To: Nosy List: benjamin.peterson, brett.cannon, georg.brandl, inada.naoki, ncoghlan, rhettinger, serhiy.storchaka, vstinner, yselivanov
Priority: normal Keywords: patch

Created on 2017-02-07 04:02 by inada.naoki, last changed 2017-12-15 09:22 by inada.naoki. This issue is now closed.

Files
File name Uploaded Description Edit
ast-constant-folding.patch inada.naoki, 2017-02-07 04:02 review
Pull Requests
URL Status Linked Edit
PR 2858 merged inada.naoki, 2017-07-25 07:10
PR 4863 merged inada.naoki, 2017-12-14 11:17
PR 4866 merged serhiy.storchaka, 2017-12-14 14:54
PR 4879 open inada.naoki, 2017-12-15 09:20
Messages (13)
msg287186 - (view) Author: INADA Naoki (inada.naoki) * (Python committer) Date: 2017-02-07 04:02
spin off of #11549.
This patch uses code generator to traverse AST.
msg287210 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2017-02-07 08:55
I suggest you to look at my AST optimizer, especially the constant folding part:
https://github.com/haypo/fatoptimizer/blob/master/fatoptimizer/const_fold.py

And the unit tests, search for BaseConstantFoldingTests:
https://github.com/haypo/fatoptimizer/blob/master/test_fatoptimizer.py#L1980

IHMO we must have a long test suite on this AST optimizer, because it's common that the AST changes in subtle ways, AST is complex and so we should prevent regressions. You may simply copy my unit tests.

My optimizer implements more optimization: just remove unit tests on cases which you don't want to optimize.
msg287214 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2017-02-07 09:01
With this change, the Python compiler doesn't emit ast.Num nor ast.Str, right?

If we merge such change, we should prepare projects using AST. There is something like that in pip, but I failed to remind which one :-/ It should be easy: apply your patch, try to install something using pip and see the traceback ;-)
msg287227 - (view) Author: INADA Naoki (inada.naoki) * (Python committer) Date: 2017-02-07 11:32
Do you mean https://github.com/pypa/pip/blob/403e398330c8e841e4633aceda859430f5f7b913/pip/_vendor/distlib/markers.py ?

This doesn't affect, maybe.
Constant folding is executed right before producing bytecode.
It doesn't affect to PyCF_ONLY_AST.

BTW, how do you feel asdl_ct.py?

I feel it's too much only for constant folding, but it is too less for other advanced optimizations.
Actually, original patch in #11549 implements other optimizations
ported from peephole in compile.c.
And most tough part of updating this patch is resolve conflict with this commit.
https://github.com/python/cpython/commit/9cea398e237d4d75c6012e23a33d01b17f5dffcc

I'll try to remove asdl_ct.py and ast_opt.ct in next version.
msg297596 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2017-07-03 14:26
In general the patch LGTM. I haven't found bugs.

I think that at this stage we can asdl_ct.py and ast_opt.ct and use just their result, ast_opt.c (maybe rename to optimize.c?) The grammar is not often changed, and in that case it would be not hard to modify the code manually. In any case compile.c should be modified manually. After removing no-op functions like astfold_operator() and inlining simple functions like astfold_arg() the code should be clearer.

Instead of converting all kinds of constants to Constant_kind, you could use is_const() and get_const_value() from compile.c.

I suggest to remove the parts of the peepholer that are superseeded by the AST optimizer.

As for preventing expensive calculations, there is a patch for the peepholer that does this. I wait on implementing the AST-level constant folding for adapting that patch for it.
msg297599 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2017-07-03 14:39
Naoki: Can you please create a PR for your patch?
msg308277 - (view) Author: INADA Naoki (inada.naoki) * (Python committer) Date: 2017-12-14 07:47
New changeset 7ea143ae795a9fd57eaccf490d316bdc13ee9065 by INADA Naoki in branch 'master':
bpo-29469: Move constant folding to AST optimizer (GH-2858)
https://github.com/python/cpython/commit/7ea143ae795a9fd57eaccf490d316bdc13ee9065
msg308283 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2017-12-14 09:21
ISTM, the constant-tracking macros for peephole.c can also be removed, essentially reverting back to the simpler cumlc-style code in Py2.5.
msg308296 - (view) Author: INADA Naoki (inada.naoki) * (Python committer) Date: 2017-12-14 13:18
New changeset eadad1b97f64619bfd246b9d3b60d25f456e0592 by INADA Naoki in branch 'master':
bpo-29469: Remove unnecessary peephole optimizer (GH-4863)
https://github.com/python/cpython/commit/eadad1b97f64619bfd246b9d3b60d25f456e0592
msg308300 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2017-12-14 14:35
Thank you very much Naoki for taking time to implement this obvious "optimization", rewriting the peephole optimizer at the AST level, rather than modifying bytecode which is more complex to get it right and had annoying side effect (like inefficient stack size, now fixed: bpo-26549).
msg308322 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2017-12-14 17:19
PR 4866 also fixes the bug in optimizing chained 'i' and 'not in'.

For example `1 in [1, 2] == [1, 2]` results in False (should be True) because it is changed to `1 in (1, 2) == [1, 2]`, and (1, 2) != [1, 2].
msg308327 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2017-12-14 18:24
New changeset 15a8728415e765f57e37f431f09e5c5821a04063 by Serhiy Storchaka in branch 'master':
bpo-29469: Optimize literal lists and sets iterating on the AST level. (#4866)
https://github.com/python/cpython/commit/15a8728415e765f57e37f431f09e5c5821a04063
msg308369 - (view) Author: INADA Naoki (inada.naoki) * (Python committer) Date: 2017-12-15 09:22
> ISTM, the constant-tracking macros for peephole.c can also be removed, essentially reverting back to the simpler cumlc-style code in Py2.5.

I tried it in GH-4879.
History
Date User Action Args
2017-12-15 09:22:07inada.naokisetmessages: + msg308369
2017-12-15 09:20:48inada.naokisetpull_requests: + pull_request4773
2017-12-14 18:25:10serhiy.storchakasetstatus: open -> closed
2017-12-14 18:24:33serhiy.storchakasetmessages: + msg308327
2017-12-14 17:19:46serhiy.storchakasetmessages: + msg308322
2017-12-14 14:55:15serhiy.storchakasetstatus: closed -> open
2017-12-14 14:54:48serhiy.storchakasetpull_requests: + pull_request4757
2017-12-14 14:35:31vstinnersetmessages: + msg308300
2017-12-14 13:18:28inada.naokisetmessages: + msg308296
2017-12-14 13:12:04serhiy.storchakalinkissue1346238 superseder
2017-12-14 11:17:05inada.naokisetpull_requests: + pull_request4753
2017-12-14 09:21:16rhettingersetnosy: + rhettinger
messages: + msg308283
2017-12-14 08:27:59serhiy.storchakalinkissue26549 superseder
2017-12-14 08:18:10serhiy.storchakalinkissue28813 superseder
2017-12-14 07:49:27inada.naokisetstatus: open -> closed
resolution: fixed
stage: patch review -> resolved
2017-12-14 07:47:22inada.naokisetmessages: + msg308277
2017-07-25 07:10:59inada.naokisetpull_requests: + pull_request2909
2017-07-03 14:39:54vstinnersetmessages: + msg297599
2017-07-03 14:26:45serhiy.storchakasetmessages: + msg297596
2017-02-07 11:32:27inada.naokisetmessages: + msg287227
2017-02-07 09:10:57serhiy.storchakasetnosy: + brett.cannon, georg.brandl, ncoghlan, benjamin.peterson, serhiy.storchaka, yselivanov

type: enhancement
components: + Interpreter Core
stage: patch review
2017-02-07 09:01:57vstinnersetmessages: + msg287214
2017-02-07 08:55:31vstinnersetnosy: + vstinner
messages: + msg287210
2017-02-07 04:02:52inada.naokisetdependencies: + Add `docstring` field to AST nodes
2017-02-07 04:02:38inada.naokicreate