Introduce range based singleton searches for loop queries

[jamieschmeiser]

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.

[Meinersbur]

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]

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

[Meinersbur]

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.