This is an archive of the discontinued LLVM Phabricator instance.

[llvm][Uniformity] correctly use a vector as a set by uniqifying elements
ClosedPublic

Authored by sameerds on Mar 2 2023, 11:16 PM.

Details

Summary

The search for temporal divergence needs to determine a dominance frontier
defined for a cycle. The implementation uses a temporary vector to store a set
of newly discovered successors. Failing to uniqify the elements in this vector
causes a very large regression in compile time due to an exponential number of
redundant visits.

This fixes github issue #61123

Diff Detail

Event Timeline

sameerds created this revision.Mar 2 2023, 11:16 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 2 2023, 11:16 PM
Herald added a subscriber: mgrang. · View Herald Transcript
sameerds requested review of this revision.Mar 2 2023, 11:16 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 2 2023, 11:16 PM
foad accepted this revision.Mar 3 2023, 1:42 AM

Works for me, thanks! I have a larger test case that goes from about 50 s to less than 1 ms with this patch.

This revision is now accepted and ready to land.Mar 3 2023, 1:42 AM
piotr added a comment.Mar 3 2023, 1:52 AM

Would be good to add a test case, but I do realize this can be tricky.