This is an archive of the discontinued LLVM Phabricator instance.

Introduce range based singleton searches for loop queries
ClosedPublic

Authored by jamieschmeiser on Oct 19 2022, 8:13 AM.

Details

Summary

Introduce range based singleton searches for loop queries.

Several loop queries look for a singleton by finding all instances and then
returning whether there is 1 instance or not. This can be improved by
stopping the search after 2 have been found. Introduce generic range
based singleton searches that stop after finding a second value
and use them for these loop queries.

There is no intended functional change other than improved compile-time
efficiency.

Diff Detail

Event Timeline

jamieschmeiser created this revision.Oct 19 2022, 8:13 AM
Herald added a project: Restricted Project. · View Herald TranscriptOct 19 2022, 8:13 AM
Herald added a subscriber: hiraditya. · View Herald Transcript
jamieschmeiser requested review of this revision.Oct 19 2022, 8:13 AM
Herald added a project: Restricted Project. · View Herald TranscriptOct 19 2022, 8:13 AM
jamieschmeiser added a reviewer: Restricted Project.Oct 19 2022, 11:44 AM

Thank you for the patch.

However, I think it can be improved even more. It is sufficient to just have a single Result variable but continue iterating through the list. When a second is found, return nullptr. If looking for unique items, check that the second item is actually different before returning nullptr.

This may have less code-reuse but doesn't need additional templates and is more efficient without a SmallVector. There will never be a non-stack allocation needed for, but I don't think a compiler can statically derive that. You could even create generic ranges-like helpers in STLExtras.h for this kind of algorithm and reuse is in RegionBase::getEnteringBlock() etc.

If you don't know what I mean, we can commit this patch first, then I could create a followup-one for you to review.

llvm/include/llvm/Analysis/LoopInfoImpl.h
107–108
158–159
jamieschmeiser edited the summary of this revision. (Show Details)

Respond to review comments. Remove templates and introduce
generic range-based singleton search routines.

jamieschmeiser retitled this revision from Templates for singleton loop queries to Introduce range based singleton searches for loop queries.Oct 25 2022, 9:44 AM
Meinersbur accepted this revision.Oct 26 2022, 8:47 AM

LGTM. thank you for the update.

When committing, can you add "NFC" (No Functional Change intended) to the title?

llvm/include/llvm/Analysis/LoopInfoImpl.h
86–87

I think I would have made separate versions of find_singleton instead of adding AllowRepeats so the parameter would not need to be propagated into the Predicate. However, at least in this case AllowRepeats is not a constant and could made it more complicated.

This revision is now accepted and ready to land.Oct 26 2022, 8:47 AM
This revision was landed with ongoing or failed builds.Oct 26 2022, 10:51 AM
This revision was automatically updated to reflect the committed changes.