Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

AST-level Constant folding #73655

Closed
methane opened this issue Feb 7, 2017 · 14 comments
Closed

AST-level Constant folding #73655

methane opened this issue Feb 7, 2017 · 14 comments
Labels
3.7 (EOL) end of life interpreter-core (Objects, Python, Grammar, and Parser dirs) type-feature A feature request or enhancement

Comments

@methane
Copy link
Member

methane commented Feb 7, 2017

BPO 29469
Nosy @brettcannon, @birkenfeld, @rhettinger, @ncoghlan, @vstinner, @benjaminp, @methane, @serhiy-storchaka, @1st1
PRs
  • bpo-29469: Move constant folding at AST level #2858
  • bpo-29469: Remove unnecessary peephole optimizer #4863
  • bpo-29469: Optimize literal lists and sets iterating on the AST level. #4866
  • bpo-29469: peephole: Remove const_stack #4879
  • Dependencies
  • bpo-29463: Add docstring field to AST nodes
  • Files
  • ast-constant-folding.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 2017-12-14.18:25:10.101>
    created_at = <Date 2017-02-07.04:02:38.365>
    labels = ['interpreter-core', 'type-feature', '3.7']
    title = 'AST-level Constant folding'
    updated_at = <Date 2017-12-18.06:52:57.357>
    user = 'https://github.com/methane'

    bugs.python.org fields:

    activity = <Date 2017-12-18.06:52:57.357>
    actor = 'methane'
    assignee = 'none'
    closed = True
    closed_date = <Date 2017-12-14.18:25:10.101>
    closer = 'serhiy.storchaka'
    components = ['Interpreter Core']
    creation = <Date 2017-02-07.04:02:38.365>
    creator = 'methane'
    dependencies = ['29463']
    files = ['46555']
    hgrepos = []
    issue_num = 29469
    keywords = ['patch']
    message_count = 14.0
    messages = ['287186', '287210', '287214', '287227', '297596', '297599', '308277', '308283', '308296', '308300', '308322', '308327', '308369', '308519']
    nosy_count = 9.0
    nosy_names = ['brett.cannon', 'georg.brandl', 'rhettinger', 'ncoghlan', 'vstinner', 'benjamin.peterson', 'methane', 'serhiy.storchaka', 'yselivanov']
    pr_nums = ['2858', '4863', '4866', '4879']
    priority = 'normal'
    resolution = 'fixed'
    stage = 'resolved'
    status = 'closed'
    superseder = None
    type = 'enhancement'
    url = 'https://bugs.python.org/issue29469'
    versions = ['Python 3.7']

    @methane
    Copy link
    Member Author

    methane commented Feb 7, 2017

    spin off of bpo-11549.
    This patch uses code generator to traverse AST.

    @methane methane added the 3.7 (EOL) end of life label Feb 7, 2017
    @vstinner
    Copy link
    Member

    vstinner commented Feb 7, 2017

    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.

    @vstinner
    Copy link
    Member

    vstinner commented Feb 7, 2017

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

    @serhiy-storchaka serhiy-storchaka added interpreter-core (Objects, Python, Grammar, and Parser dirs) type-feature A feature request or enhancement labels Feb 7, 2017
    @methane
    Copy link
    Member Author

    methane commented Feb 7, 2017

    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 bpo-11549 implements other optimizations
    ported from peephole in compile.c.
    And most tough part of updating this patch is resolve conflict with this commit.
    9cea398

    I'll try to remove asdl_ct.py and ast_opt.ct in next version.

    @serhiy-storchaka
    Copy link
    Member

    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.

    @vstinner
    Copy link
    Member

    vstinner commented Jul 3, 2017

    Naoki: Can you please create a PR for your patch?

    @methane
    Copy link
    Member Author

    methane commented Dec 14, 2017

    New changeset 7ea143a by INADA Naoki in branch 'master':
    bpo-29469: Move constant folding to AST optimizer (GH-2858)
    7ea143a

    @methane methane closed this as completed Dec 14, 2017
    @rhettinger
    Copy link
    Contributor

    ISTM, the constant-tracking macros for peephole.c can also be removed, essentially reverting back to the simpler cumlc-style code in Py2.5.

    @methane
    Copy link
    Member Author

    methane commented Dec 14, 2017

    New changeset eadad1b by INADA Naoki in branch 'master':
    bpo-29469: Remove unnecessary peephole optimizer (GH-4863)
    eadad1b

    @vstinner
    Copy link
    Member

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

    @serhiy-storchaka
    Copy link
    Member

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

    @serhiy-storchaka
    Copy link
    Member

    New changeset 15a8728 by Serhiy Storchaka in branch 'master':
    bpo-29469: Optimize literal lists and sets iterating on the AST level. (bpo-4866)
    15a8728

    @methane
    Copy link
    Member Author

    methane commented Dec 15, 2017

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

    @methane
    Copy link
    Member Author

    methane commented Dec 18, 2017

    New changeset 87010e8 by INADA Naoki in branch 'master':
    bpo-29469: peephole: Remove const_stack (GH-4879)
    87010e8

    @ezio-melotti ezio-melotti transferred this issue from another repository Apr 10, 2022
    Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
    Labels
    3.7 (EOL) end of life interpreter-core (Objects, Python, Grammar, and Parser dirs) type-feature A feature request or enhancement
    Projects
    None yet
    Development

    No branches or pull requests

    4 participants