This is an archive of the discontinued LLVM Phabricator instance.

[ADT] Add a new data structure for managing a priority worklist where re-insertion of entries into the worklist moves them to the end.
ClosedPublic

Authored by chandlerc on Jun 29 2016, 3:56 PM.

Details

Summary

This is fairly similar to a SetVector, but helps in the case where in
addition to not inserting duplicates you want to adjust the sequence of
a pop-off-the-back worklist.

I'm not at all attached to the name of this data structure if others
have better suggestions, but this is one that David Majnemer brought up
in IRC discussions that seems plausible.

I've trimmed the interface down somewhat from SetVector's interface
because several things make less sense here IMO: iteration primarily.
I'd prefer to add these back as we have users that need them. My use
case doesn't even need all of what is provided here. =]

I've also included a basic unittest to make sure this functions
reasonably.

Diff Detail

Event Timeline

chandlerc updated this revision to Diff 62298.Jun 29 2016, 3:56 PM
chandlerc retitled this revision from to [ADT] Add a new data structure for managing a priority worklist where re-insertion of entries into the worklist moves them to the end..
chandlerc updated this object.
chandlerc added a subscriber: llvm-commits.
sanjoy added a subscriber: sanjoy.Jun 29 2016, 4:11 PM

Drop by comments.

include/llvm/ADT/PriorityWorklist.h
28

Don't we have autobrief these days?

40

Can we re-use DenseMapInfo<T> for this (say the tombstone value)?

88

Why T in one place and value_type in another?

95

We should have a way to fail an assert if someone tries to insert the sentinel "null" value.

177

This is only to avoid templates and lamda, right? If so, would be nice to state that explicitly.

MatzeB added a subscriber: MatzeB.Jun 29 2016, 4:13 PM

I'm wondering if it is worth creating a whole new templated type here, do you expect more than one user?

include/llvm/ADT/PriorityWorklist.h
110–114

Should this rather be V.back() == T()? Or alternatively you could document that T needs to be implicitely convertible to bool with everything but the NULL value being false...

(Similar in the assert and another instance later).

I'm wondering if it is worth creating a whole new templated type here, do you expect more than one user?

If the new template were complex, I wouldn't have. But this is actually easier than me getting this right in the one user I have in mind, and that user already needs two of them (one for SCC* and the other for RefSCC*).

Working on the rest of the comments now....

chandlerc added inline comments.Jun 29 2016, 4:55 PM
include/llvm/ADT/PriorityWorklist.h
28

I just forgot. Fixed.

40

We could I guess, but I expect these to essentially always be pointers, and the dense map empty and tombstones for those are going to be less efficient than testing for zero... I mean, probably it doesn't matter, but T() more accurately matches the naive code I would have written by hand and am packaging up here and so that's what I used.

If you or others feel strongly, I would use the empty key as these are in fact empty slots.

88

the value_type came from SetVector. I prefer the easier to read T personally, made it consistent.

95

Done.

110–114

Yes, good catch. Fixed here and elsewhere.

177

I guess, this was copied directly from SetVector. I can just delete all of this until someone needs it if you like (my one user doesn't need it).

chandlerc updated this revision to Diff 62316.Jun 29 2016, 4:56 PM

Updates based on code review feedback.

MatzeB accepted this revision.Jun 29 2016, 5:08 PM
MatzeB added a reviewer: MatzeB.

LGTM

This revision is now accepted and ready to land.Jun 29 2016, 5:08 PM
sanjoy accepted this revision.Jun 29 2016, 5:11 PM
sanjoy added a reviewer: sanjoy.

lgtm too

include/llvm/ADT/PriorityWorklist.h
42

ok

179

Given that there are tests, I'm fine with this.

Thanks all, submitting. Let me know if there are further suggestions around this.

include/llvm/ADT/PriorityWorklist.h
179

There was actually a bug here... I've improved the test and fixed the bug. =]

This revision was automatically updated to reflect the committed changes.