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.

llvm/include/llvm/ADT/STLExtras.h

 
 /// Provide wrappers to std::copy_if which take ranges instead of having to
 /// pass begin/end explicitly.
 template <typename R, typename OutputIt, typename UnaryPredicate>
 OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P) {
   return std::copy_if(adl_begin(Range), adl_end(Range), Out, P);
 }
 
+/// Return the single value in \p Range that satisfies
+/// \p P(<member of \p Range> *, AllowRepeats)->T * returning nullptr
+/// when no values or multiple values were found.
+/// When \p AllowRepeats is true, multiple values that compare equal
+/// are allowed.
+template <typename T, typename R, typename Predicate>
+T *find_singleton(R &&Range, Predicate P, bool AllowRepeats = false) {
+  T *RC = nullptr;
+  for (auto *A : Range) {
+    if (T *PRC = P(A, AllowRepeats)) {
+      if (RC) {
+        if (!AllowRepeats || PRC != RC)
+          return nullptr;
+      } else
+        RC = PRC;
+    }
+  }
+  return RC;
+}
+
+/// Return a pair consisting of the single value in \p Range that satisfies
+/// \p P(<member of \p Range> *, AllowRepeats)->std::pair<T*, bool> returning
+/// nullptr when no values or multiple values were found, and a bool indicating
+/// whether multiple values were found to cause the nullptr.
+/// When \p AllowRepeats is true, multiple values that compare equal are
+/// allowed.  The predicate \p P returns a pair<T *, bool> where T is the
+/// singleton while the bool indicates whether multiples have already been
+/// found.  It is expected that first will be nullptr when second is true.
+/// This allows using find_singleton_nested within the predicate \P.
+template <typename T, typename R, typename Predicate>
+std::pair<T *, bool> find_singleton_nested(R &&Range, Predicate P,
+                                           bool AllowRepeats = false) {
+  T *RC = nullptr;
+  for (auto *A : Range) {
+    std::pair<T *, bool> PRC = P(A, AllowRepeats);
+    if (PRC.second) {
+      assert(PRC.first == nullptr &&
+             "Inconsistent return values in find_singleton_nested.");
+      return PRC;
+    }
+    if (PRC.first) {
+      if (RC) {
+        if (!AllowRepeats || PRC.first != RC)
+          return {nullptr, true};
+      } else
+        RC = PRC.first;
+    }
+  }
+  return {RC, false};
+}
+
 template <typename R, typename OutputIt>
 OutputIt copy(R &&Range, OutputIt Out) {
   return std::copy(adl_begin(Range), adl_end(Range), Out);
 }
 
 /// Provide wrappers to std::replace_copy_if which take ranges instead of having
 /// to pass begin/end explicitly.
 template <typename R, typename OutputIt, typename UnaryPredicate, typename T>

llvm/include/llvm/Analysis/LoopInfoImpl.h

for (auto *Succ : children<BlockT *>(BB))
       }
 }
 
 /// getExitingBlock - If getExitingBlocks would return exactly one block,
 /// return that block. Otherwise return null.
 template <class BlockT, class LoopT>
 BlockT *LoopBase<BlockT, LoopT>::getExitingBlock() const {
   assert(!isInvalid() && "Loop not in a valid state!");
-  SmallVector<BlockT *, 8> ExitingBlocks;
-  getExitingBlocks(ExitingBlocks);
-  if (ExitingBlocks.size() == 1)
-    return ExitingBlocks[0];
-  return nullptr;
+  auto notInLoop = [&](BlockT *BB) { return !contains(BB); };
+  auto isExitBlock = [&](BlockT *BB, bool AllowRepeats) -> BlockT * {
+    assert(!AllowRepeats && "Unexpected parameter value.");
+    // Child not in current loop?  It must be an exit block.
+    return any_of(children<BlockT *>(BB), notInLoop) ? BB : nullptr;
+  };
+
+  return find_singleton<BlockT>(blocks(), isExitBlock);
 }
 
 /// getExitBlocks - Return all of the successor blocks of this loop.  These
 /// are the blocks _outside of the current loop_ which are branched to.
 ///
 template <class BlockT, class LoopT>
 void LoopBase<BlockT, LoopT>::getExitBlocks(
     SmallVectorImpl<BlockT *> &ExitBlocks) const {
   assert(!isInvalid() && "Loop not in a valid state!");
   for (const auto BB : blocks())
     for (auto *Succ : children<BlockT *>(BB))
       if (!contains(Succ))
         // Not in current loop? It must be an exit block.
         ExitBlocks.push_back(Succ);
 }
 
+/// getExitBlock - If getExitBlocks would return exactly one block,
+/// return that block. Otherwise return null.
+template <class BlockT, class LoopT>
+std::pair<BlockT *, bool> getExitBlockHelper(const LoopBase<BlockT, LoopT> *L,
+                                             bool Unique) {
+  assert(!L->isInvalid() && "Loop not in a valid state!");
+  auto notInLoop = [&](BlockT *BB,
+                       bool AllowRepeats) -> std::pair<BlockT *, bool> {
+    assert(AllowRepeats == Unique && "Unexpected parameter value.");
+    return {!L->contains(BB) ? BB : nullptr, false};
+  };
+  auto singleExitBlock = [&](BlockT *BB,
+                             bool AllowRepeats) -> std::pair<BlockT *, bool> {
+    assert(AllowRepeats == Unique && "Unexpected parameter value.");
+    return find_singleton_nested<BlockT>(children<BlockT *>(BB), notInLoop,
+                                         AllowRepeats);
+  };
+  return find_singleton_nested<BlockT>(L->blocks(), singleExitBlock, Unique);
+}
+
 template <class BlockT, class LoopT>
 bool LoopBase<BlockT, LoopT>::hasNoExitBlocks() const {
-  SmallVector<BlockT *, 8> ExitBlocks;
-  getExitBlocks(ExitBlocks);
-  return ExitBlocks.empty();
+  auto RC = getExitBlockHelper(this, false);
+  if (RC.second)
+    // found multiple exit blocks
+    return false;
+  // return true if there is no exit block
+  return !RC.first;
 }
 
 /// getExitBlock - If getExitBlocks would return exactly one block,
 /// return that block. Otherwise return null.
 template <class BlockT, class LoopT>
 BlockT *LoopBase<BlockT, LoopT>::getExitBlock() const {
-  assert(!isInvalid() && "Loop not in a valid state!");
-  SmallVector<BlockT *, 8> ExitBlocks;
-  getExitBlocks(ExitBlocks);
-  if (ExitBlocks.size() == 1)
-    return ExitBlocks[0];
-  return nullptr;
+  return getExitBlockHelper(this, false).first;
 }
 
 template <class BlockT, class LoopT>
 bool LoopBase<BlockT, LoopT>::hasDedicatedExits() const {
   // Each predecessor of each exit block of a normal loop is contained
   // within the loop.
   SmallVector<BlockT *, 4> UniqueExitBlocks;
   getUniqueExitBlocks(UniqueExitBlocks);
void LoopBase<BlockT, LoopT>::getUniqueNonLatchExitBlocks(
     SmallVectorImpl<BlockT *> &ExitBlocks) const {
   const BlockT *Latch = getLoopLatch();
   assert(Latch && "Latch block must exists");
   getUniqueExitBlocksHelper(this, ExitBlocks,
                             [Latch](const BlockT *BB) { return BB != Latch; });
 }
 
 template <class BlockT, class LoopT>
 BlockT *LoopBase<BlockT, LoopT>::getUniqueExitBlock() const {
-  SmallVector<BlockT *, 8> UniqueExitBlocks;
-  getUniqueExitBlocks(UniqueExitBlocks);
-  if (UniqueExitBlocks.size() == 1)
-    return UniqueExitBlocks[0];
-  return nullptr;
+  return getExitBlockHelper(this, true).first;
 }
 
 /// getExitEdges - Return all pairs of (_inside_block_,_outside_block_).
 template <class BlockT, class LoopT>
 void LoopBase<BlockT, LoopT>::getExitEdges(
     SmallVectorImpl<Edge> &ExitEdges) const {
   assert(!isInvalid() && "Loop not in a valid state!");
   for (const auto BB : blocks())

llvm/include/llvm/Analysis/RegionInfoImpl.h

typename Tr::LoopT *RegionBase<Tr>::outermostLoopInRegion(LoopInfoT *LI,
                                                           BlockT *BB) const {
   assert(LI && BB && "LI and BB cannot be null!");
   LoopT *L = LI->getLoopFor(BB);
   return outermostLoopInRegion(L);
 }
 
 template <class Tr>
 typename RegionBase<Tr>::BlockT *RegionBase<Tr>::getEnteringBlock() const {
+  auto isEnteringBlock = [&](BlockT *Pred, bool AllowRepeats) -> BlockT * {
+    assert(!AllowRepeats && "Unexpected parameter value.");
+    return DT->getNode(Pred) && !contains(Pred) ? Pred : nullptr;
+  };
   BlockT *entry = getEntry();
-  BlockT *enteringBlock = nullptr;
-
-  for (BlockT *Pred : make_range(InvBlockTraits::child_begin(entry),
-                                 InvBlockTraits::child_end(entry))) {
-    if (DT->getNode(Pred) && !contains(Pred)) {
-      if (enteringBlock)
-        return nullptr;
-
-      enteringBlock = Pred;
-    }
-  }
-
-  return enteringBlock;
+  return find_singleton<BlockT>(make_range(InvBlockTraits::child_begin(entry),
+                                           InvBlockTraits::child_end(entry)),
+                                isEnteringBlock);
 }
 
 template <class Tr>
 bool RegionBase<Tr>::getExitingBlocks(
     SmallVectorImpl<BlockT *> &Exitings) const {
   bool CoverAll = true;
 
   if (!exit)
bool RegionBase<Tr>::getExitingBlocks(
   }
 
   return CoverAll;
 }
 
 template <class Tr>
 typename RegionBase<Tr>::BlockT *RegionBase<Tr>::getExitingBlock() const {
   BlockT *exit = getExit();
-  BlockT *exitingBlock = nullptr;
-
   if (!exit)
     return nullptr;
 
-  for (BlockT *Pred : make_range(InvBlockTraits::child_begin(exit),
-                                 InvBlockTraits::child_end(exit))) {
-    if (contains(Pred)) {
-      if (exitingBlock)
-        return nullptr;
-
-      exitingBlock = Pred;
-    }
-  }
-
-  return exitingBlock;
+  auto isContained = [&](BlockT *Pred, bool AllowRepeats) -> BlockT * {
+    assert(!AllowRepeats && "Unexpected parameter value.");
+    return contains(Pred) ? Pred : nullptr;
+  };
+  return find_singleton<BlockT>(make_range(InvBlockTraits::child_begin(exit),
+                                           InvBlockTraits::child_end(exit)),
+                                isContained);
 }
 
 template <class Tr>
 bool RegionBase<Tr>::isSimple() const {
   return !isTopLevelRegion() && getEnteringBlock() && getExitingBlock();
 }
 
 template <class Tr>