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.

Sign up for GitHub

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

Jump to bottom

A unified framework for dataflow analysis #202

Closed
ecstatic-morse opened this issue Oct 16, 2019 · 5 comments
Closed

A unified framework for dataflow analysis #202

ecstatic-morse opened this issue Oct 16, 2019 · 5 comments
Labels
meeting-proposal meeting-scheduled

Comments

@ecstatic-morse
Copy link
Contributor

ecstatic-morse commented Oct 16, 2019 •
edited
Loading

Meeting proposal info

After rust-lang/rust#64566, which was a prerequisite for dataflow-based const validation, there are two different frameworks for dataflow analysis in the compiler. I've written a prototype along with a design document for unifying the two frameworks.

The dataflow framework is an internal API (with the exception of one use in cargo-clippy), so this is a good time to improve it if desired. Accordingly, I've made some changes in the prototype, like passing Statements and Terminators directly into the effect methods, and making the signature of call_return_effect more similar to the others. If anyone has had difficulties implementing or inspecting the results of a dataflow analysis, it would be awesome to get your feedback here.

About this issue

This issue corresponds to a meeting proposal for the compiler team
steering meeting. It corresponds to a possible topic of
discussion. You can read more about the steering meeting procedure
here.

Comment policy

These issues are meant to be used as an "announcements channel"
regarding the proposal, and not as a place to discuss the technical
details. Feel free to subscribe to updates. We'll post comments when
reviewing the proposal in meetings or making a scheduling decision.
In the meantime, if you have questions or ideas, ping the proposers
on Zulip (or elsewhere).
@ecstatic-morse ecstatic-morse mentioned this issue Oct 21, 2019
Merged
@nikomatsakis
Copy link
Contributor

We discussed this in our planning meeting today and decided to schedule it for discussion on Nov 1, 2019.

Calendar event

@mark-i-m
Copy link
Member

Match in const fn here we come!

@nikomatsakis
Copy link
Contributor

Update: Since @oli-obk will be unavailable, we've moved the date to Nov 8

@ecstatic-morse
Copy link
Contributor Author

ecstatic-morse commented Oct 25, 2019 •
edited
Loading

To clarify, this isn't blocking if and match in const fn. The necessary dataflow analysis was merged in rust-lang/rust#64566, and it has been used to check const bodies since rust-lang/rust#64470. It's just that this framework is completely separate from the existing BitDenotation: they don't share a ResultsCursor implementation, a graphviz visualizer, etc.

This design meeting is about merging the two frameworks into a single, shared one. Since this will require modifications wherever either framework is used, it is a good time to make changes to the existing API to make it easier to comprehend. It's also a good time to consider possible optimizations and extensions to this framework (extended basic blocks, customizable dataflow lattices, etc.) and make sure that the unified framework does not make any of these infeasible.

@ecstatic-morse ecstatic-morse mentioned this issue Nov 10, 2019
Merged
bors added a commit to rust-lang/rust that referenced this issue Nov 14, 2019
@bors
Auto merge of #65672 - ecstatic-morse:unified-dataflow-proto, r=<try>
1e0b457 
[WIP] A single framework for gen-kill and generic dataflow problems

This is the prototype implementation discussed in rust-lang/compiler-team#202. You can read a high-level description of it in [the proposal](https://hackmd.io/@39Qr_z9cQhasi25sGjmFnA/Skvd9rztS) for that design meeting. This would eventually supersede the existing `BitDenotation` interface.

r? @ghost

cc @rust-lang/compiler (esp. @eddyb and @pnkfelix)
bors added a commit to rust-lang/rust that referenced this issue Nov 15, 2019
@bors
Auto merge of #65672 - ecstatic-morse:unified-dataflow-proto, r=<try>
43d649e 
[WIP] A single framework for gen-kill and generic dataflow problems

This is the prototype implementation discussed in rust-lang/compiler-team#202. You can read a high-level description of it in [the proposal](https://hackmd.io/@39Qr_z9cQhasi25sGjmFnA/Skvd9rztS) for that design meeting. This would eventually supersede the existing `BitDenotation` interface.

r? @ghost

cc @rust-lang/compiler (esp. @eddyb and @pnkfelix)
@nikomatsakis
Copy link
Contributor

We had the meeting and added minutes here, closing.

bors added a commit to rust-lang/rust that referenced this issue Dec 10, 2019
@bors
Auto merge of #65672 - ecstatic-morse:unified-dataflow-proto, r=<try>
d05d264 
A single framework for gen-kill and generic dataflow problems

This is the prototype implementation discussed in rust-lang/compiler-team#202. You can read a high-level description of it in [the proposal](https://hackmd.io/@39Qr_z9cQhasi25sGjmFnA/Skvd9rztS) for that design meeting. This would eventually supersede the existing `BitDenotation` interface.

r? @ghost

cc @rust-lang/compiler (esp. @eddyb and @pnkfelix)
bors added a commit to rust-lang/rust that referenced this issue Dec 10, 2019
@bors
Auto merge of #65672 - ecstatic-morse:unified-dataflow-proto, r=<try>
5c014ac 
A single framework for gen-kill and generic dataflow problems

This is the prototype implementation discussed in rust-lang/compiler-team#202. You can read a high-level description of it in [the proposal](https://hackmd.io/@39Qr_z9cQhasi25sGjmFnA/Skvd9rztS) for that design meeting. This would eventually supersede the existing `BitDenotation` interface.

r? @ghost

cc @rust-lang/compiler (esp. @eddyb and @pnkfelix)
bors added a commit to rust-lang/rust that referenced this issue Jan 21, 2020
@bors
Auto merge of #65672 - ecstatic-morse:unified-dataflow-proto, r=pnkfelix
2cf24ab 
A single framework for gen-kill and generic dataflow problems

This is the prototype implementation discussed in rust-lang/compiler-team#202. You can read a high-level description of it in [the proposal](https://hackmd.io/@39Qr_z9cQhasi25sGjmFnA/Skvd9rztS) for that design meeting. This would eventually supersede the existing `BitDenotation` interface.

r? @ghost

cc @rust-lang/compiler (esp. @eddyb and @pnkfelix)
@ecstatic-morse ecstatic-morse mentioned this issue Mar 2, 2020
Merged
Dylan-DPC-zz pushed a commit to Dylan-DPC-zz/rust that referenced this issue Mar 27, 2020
@Dylan-DPC
Rollup merge of rust-lang#69644 - ecstatic-morse:unified-dataflow-cle…
0f6144a 
…anup, r=eddyb

Remove framework in `dataflow/mod.rs` in favor of "generic" one

This is the culmination of the work described in rust-lang/compiler-team#202. All dataflow analyses (including the one in `clippy`) have been ported to use the framework in `dataflow/generic`, which can efficiently handle both gen/kill and generic problems. This PR moves the framework in `dataflow/generic` to `dataflow/framework`, and removes the gen/kill framework in `dataflow/mod.rs`.

More comprehensive documentation for the new framework is tracked in rust-lang/rustc-dev-guide#564.

`clippy` will need to change the path it uses to import the dataflow analysis traits.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
meeting-proposal meeting-scheduled
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
3 participants
@nikomatsakis @mark-i-m @ecstatic-morse