GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — gh-114058: Foundations of the Tier2 redundancy eliminator by Fidget-Spinner · Pull Request #115085 · python/cpython

Conversation

@Fidget-Spinner

@Fidget-Spinner Fidget-Spinner commented Feb 6, 2024 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Member

This sets up the tier 2 optimizer's redundancy eliminator foundations.

It does the following:

  • Aliasing information for types (not on all expressions though, that is too expensive)
  • Basic Type propagation
  • Basic Guard elimination

It's basically a port of #114059 over using Mark's DSL. Constant propagation and a lot of type propagation rules torn out, for the sake of simpler code for now. We can easily add more later. I just want to get the foundations in.

I expect no speedups for this, as for simpler reviewing, most of the code is torn out. However, I believe that #114059 already shows this approach has potential for speedups.

  • Issue: Tier 2 optimizer's abstract interpreter #114058

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
Fidget-Spinner and others added 5 commits February 6, 2024 12:57
@Fidget-Spinner
bring over changes from old branch
169e08d
@Fidget-Spinner @markshannon
Port over to Mark's DSL
e270364 
Co-Authored-By: Mark Shannon <[email protected]>
@Fidget-Spinner @JuliaPoo @gvanrossum
reduce diff
e8a8b78 
Co-Authored-By: Jules <[email protected]>
Co-Authored-By: Guido van Rossum <[email protected]>
@Fidget-Spinner
fix passthrough
bb6137a
@Fidget-Spinner
fix tests
9b15f9e
@Fidget-Spinner
Fidget-Spinner requested review from brandtbucher, ericsnowcurrently, gvanrossum and markshannon as code owners February 6, 2024 14:42
@bedevere-app bedevere-app Bot added the awaiting core review label Feb 6, 2024
@bedevere-app bedevere-app Bot mentioned this pull request Feb 6, 2024
Tier 2 optimizer's abstract interpreter #114058
Closed
@Fidget-Spinner Fidget-Spinner mentioned this pull request Feb 6, 2024
gh-114058: The Tier2 Optimizer #114059
Closed
@Fidget-Spinner
fix mypy issues
66bfce5
Eclips4
Eclips4 reviewed Feb 6, 2024
View reviewed changes
Comment thread Tools/cases_generator/tier2_abstract_generator.py Resolved

Uh oh!

There was an error while loading. Please reload this page.
Eclips4
Eclips4 reviewed Feb 6, 2024
View reviewed changes
Comment thread Tools/cases_generator/tier2_abstract_generator.py Resolved

Uh oh!

There was an error while loading. Please reload this page.
Comment thread Tools/cases_generator/tier2_abstract_generator.py Resolved

Uh oh!

There was an error while loading. Please reload this page.
Comment thread Tools/cases_generator/tier2_abstract_generator.py Resolved

Uh oh!

There was an error while loading. Please reload this page.
Fidget-Spinner added 3 commits February 6, 2024 23:19
@Fidget-Spinner
fix tests and address review
3789cd9
@Fidget-Spinner
add tests for abstract cases generator
20d087b
@Fidget-Spinner
patchcheck
0f58526
Eclips4
Eclips4 reviewed Feb 6, 2024
View reviewed changes
Comment thread Tools/cases_generator/interpreter_definition.md Resolved

Uh oh!

There was an error while loading. Please reload this page.
markshannon
markshannon reviewed Feb 6, 2024
View reviewed changes

@markshannon markshannon left a comment

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This looks much closer to what I think we need. Thanks.

What's the API for _Py_UOpsSymType? It isn't clear what's internal and what's API.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
Comment thread Python/optimizer_analysis.c Resolved

Uh oh!

There was an error while loading. Please reload this page.
Comment thread Python/optimizer_analysis.c Resolved

Uh oh!

There was an error while loading. Please reload this page.
Comment thread Python/optimizer_analysis.c
_Py_UOpsSymType **stack_pointer;
_Py_UOpsSymType **stack;
_Py_UOpsSymType **locals;
} _Py_UOpsAbstractFrame;

@markshannon markshannon Feb 6, 2024

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

You can use much the same layout as an actual frame and put the locals and stack at the end:

    ...
    _Py_UOpsSymType **stack_pointer;
    _Py_UOpsSymType *localsplus[1];
}

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions

@Fidget-Spinner Fidget-Spinner Feb 7, 2024 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Member Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I initially did that, but this new layout is easier for inlining, because it actually models the state if all frames were to be inlined. So it makes things like calculating the new locals offset easier.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions

@markshannon markshannon Feb 7, 2024

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

But we aren't inlining yet, and we might choose a different approach. Making it a single struct would make memory management simpler.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions

@Fidget-Spinner Fidget-Spinner Feb 7, 2024 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Member Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Right now making it a single struct would make memory management a little more complex, because my "frames" are just an array of static sized structs. Their localsplus is just accessing a giant pool. frame->prev is just index--. It's all rather clean. And I just need to manage memory once instead of for 7 giant frames.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions

@markshannon markshannon Feb 8, 2024

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Ideally, we won't be doing any allocations, just reusing a buffer on the thread-state. But's that future PR.
But we still need to manage the memory within that buffer, and monolithic frames will make that simpler.
This should be fine for now, though.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
Comment thread Python/optimizer_analysis.c Resolved

Uh oh!

There was an error while loading. Please reload this page.
Comment thread Python/optimizer_analysis.c Resolved

Uh oh!

There was an error while loading. Please reload this page.
Comment thread Python/optimizer_analysis.c Resolved

Uh oh!

There was an error while loading. Please reload this page.
Comment thread Python/optimizer_analysis.c Resolved

Uh oh!

There was an error while loading. Please reload this page.
Comment thread Python/optimizer_analysis.c Resolved

Uh oh!

There was an error while loading. Please reload this page.
Comment thread Python/tier2_redundancy_eliminator_bytecodes.c Resolved

Uh oh!

There was an error while loading. Please reload this page.
Comment thread Python/tier2_redundancy_eliminator_bytecodes.c Resolved

Uh oh!

There was an error while loading. Please reload this page.
@markshannon

markshannon commented Feb 6, 2024

Copy link
Copy Markdown
Member

How hard would it be to change the API to take PyTypeObject * for the types in the API? It would make it easier to use.
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@Fidget-Spinner

Fidget-Spinner commented Feb 6, 2024 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Member Author

How hard would it be to change the API to take PyTypeObject * for the types in the API? It would make it easier to use.

Quite possible. I can just convert to the internal representation internally. (The representation is just to save space, and support unions in the future).

The only thing is there are some "types" that cant be represented using pytype object. In that case I will special case them.
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
Fidget-Spinner added 5 commits February 7, 2024 15:36
@Fidget-Spinner
Address review
c55ba14
@Fidget-Spinner
reduce diff, add tests
e34a0f5
@Fidget-Spinner
fix compilation problems
229aab0
@Fidget-Spinner
don't needlessly clear aliasing information
3c8def4
@Fidget-Spinner
remove is_const for now
649b0c7
@markshannon

markshannon commented Feb 7, 2024

Copy link
Copy Markdown
Member

The only thing is there are some "types" that cant be represented using pytype object. In that case I will special case them.

It is probably best to add those cases to the API.
For example if you have "not NULL" or "NULL" as nodes in the lattice, then adding a new/set_null and new/set_not_null API would make sense.
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
markshannon
markshannon reviewed Feb 7, 2024
View reviewed changes
Comment thread Python/optimizer_analysis.c Resolved

Uh oh!

There was an error while loading. Please reload this page.
markshannon
markshannon reviewed Feb 7, 2024
View reviewed changes
Comment thread Tools/cases_generator/tier2_abstract_generator.py Resolved

Uh oh!

There was an error while loading. Please reload this page.
@Fidget-Spinner
Address review
702a6fc
markshannon
markshannon reviewed Feb 13, 2024
View reviewed changes
Comment thread Python/optimizer_analysis.c Outdated

#define GETLOCAL(idx) ((ctx->frame->locals[idx]))

#define REPLACE_OP(op, arg, oper) \

@markshannon markshannon Feb 13, 2024

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I don't like macros that assume context, and we rarely (maybe never) want to set the oparg or operand.

Suggested change
#define REPLACE_OP(op, arg, oper) \
#define REPLACE_OP(INST, OP) (INST)->opcode = (OP)

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions

@Fidget-Spinner Fidget-Spinner Feb 13, 2024

Copy link
Copy Markdown
Member Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

We will need operand once we start burning in _LOAD_CONST_INLINE and friends.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
markshannon
markshannon reviewed Feb 13, 2024
View reviewed changes
Comment thread Python/optimizer_analysis.c Resolved

Uh oh!

There was an error while loading. Please reload this page.
markshannon
markshannon reviewed Feb 13, 2024
View reviewed changes
Comment thread Python/optimizer_analysis.c Resolved

Uh oh!

There was an error while loading. Please reload this page.
markshannon
markshannon reviewed Feb 13, 2024
View reviewed changes
Comment thread Python/optimizer_analysis.c


static void
remove_unneeded_uops(_PyUOpInstruction *buffer, int buffer_size)

@markshannon markshannon Feb 13, 2024

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Has this changed, or has it just moved?

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions

@Fidget-Spinner Fidget-Spinner Feb 13, 2024

Copy link
Copy Markdown
Member Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I did not change it. It just moved.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
markshannon
markshannon reviewed Feb 13, 2024
View reviewed changes
Comment thread Python/optimizer_analysis.c Outdated
// The only valid error we can raise is MemoryError.
// Other times it's not really errors but things like not being able
// to fetch a function version because the function got deleted.
return PyErr_Occurred() ? -1 : 0;

@markshannon markshannon Feb 13, 2024

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Why do you need to check PyErr_Occurred()? uop_redundancy_eliminator should not be returning -1 unless an error has occurred.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions

@Fidget-Spinner Fidget-Spinner Feb 13, 2024

Copy link
Copy Markdown
Member Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

In the old code, constant propagation could raise MemoryError.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
markshannon
markshannon reviewed Feb 13, 2024
View reviewed changes
Comment thread Include/cpython/pystats.h Resolved

Uh oh!

There was an error while loading. Please reload this page.
markshannon
markshannon reviewed Feb 13, 2024
View reviewed changes
Comment thread Python/optimizer_analysis.c Resolved

Uh oh!

There was an error while loading. Please reload this page.
Fidget-Spinner added 4 commits February 13, 2024 19:01
@Fidget-Spinner
address review
77e56ff
@Fidget-Spinner
Merge remote-tracking branch 'upstream/main' into tier2_redundancy_el…
c457098 
…iminator
@Fidget-Spinner
rename inst -> this_instr
fcd31af
@Fidget-Spinner
address review
92b211c
markshannon
markshannon reviewed Feb 13, 2024
View reviewed changes
Comment thread Python/tier2_redundancy_eliminator_bytecodes.c Resolved

Uh oh!

There was an error while loading. Please reload this page.
Fidget-Spinner added 5 commits February 13, 2024 19:17
@Fidget-Spinner
remove whitespace
1bf6ef8
@Fidget-Spinner
remove assert
ea3755f
@Fidget-Spinner
remove enabled
f09e3c3
@Fidget-Spinner
fix up error codes
9670b23
@Fidget-Spinner
fix error code again
38420c3
@markshannon
markshannon self-requested a review February 13, 2024 12:16
markshannon
markshannon approved these changes Feb 13, 2024
View reviewed changes

@markshannon markshannon left a comment

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Looks good now.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
gvanrossum reacted with hooray emoji ericsnowcurrently reacted with heart emoji
All reactions
  • 🎉 1 reaction
  • ❤️ 1 reaction
@bedevere-app bedevere-app Bot added awaiting merge and removed awaiting changes labels Feb 13, 2024
@Fidget-Spinner
Fidget-Spinner enabled auto-merge (squash) February 13, 2024 12:20
@Fidget-Spinner
Fidget-Spinner disabled auto-merge February 13, 2024 12:32
@Fidget-Spinner
Fidget-Spinner merged commit 7cce857 into python:main Feb 13, 2024
@bedevere-app bedevere-app Bot removed the awaiting merge label Feb 13, 2024
@Fidget-Spinner
Fidget-Spinner deleted the tier2_redundancy_eliminator branch February 13, 2024 13:24
fsc-eriker pushed a commit to fsc-eriker/cpython that referenced this pull request Feb 14, 2024
@Fidget-Spinner @markshannon
@JuliaPoo @gvanrossum @fsc-eriker
pythongh-114058: Foundations of the Tier2 redundancy eliminator (pyth…
1e5b86d 
…onGH-115085)

---------

Co-authored-by: Mark Shannon <[email protected]>
Co-authored-by: Jules <[email protected]>
Co-authored-by: Guido van Rossum <[email protected]>
@sobolevn sobolevn mentioned this pull request Feb 16, 2024
Add Python/tier2_redundancy_eliminator_cases.c.h to .gitattributes as generated #115551
Merged
@mdboom mdboom mentioned this pull request Mar 15, 2024
pystats: New optimizer stats for _Py_uop_analyze_and_optimize are missing from the table #116879
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@Eclips4 Eclips4 Eclips4 left review comments
@markshannon markshannon markshannon approved these changes
@gvanrossum gvanrossum Awaiting requested review from gvanrossum
@ericsnowcurrently ericsnowcurrently Awaiting requested review from ericsnowcurrently ericsnowcurrently is a code owner
@brandtbucher brandtbucher Awaiting requested review from brandtbucher

Uh oh!

There was an error while loading. Please reload this page.

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

Uh oh!

There was an error while loading. Please reload this page.

3 participants

@Fidget-Spinner @markshannon @Eclips4
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.