[NFC] Factor out predecessors collection into a separate method

[mkazantsev]

Summary

It may be reused in a different piece of logic.

[reames]

LGTM. Don't see where you're going with this, but the patch is obvious correct and doesn't make anything particularly messy.

[mkazantsev]

I need it for https://reviews.llvm.org/D50891

Tracking down instructions that write memory is pretty much the same as with control flow. Thinking about it even more, we can generalize much more things there.

[mkazantsev]

Another application of that is that we can cache this method (its users don't change control flow, so the set of predecessors should remain unchanged).

include/llvm/Analysis/MustExecute.h

 /// LoopSafetyInfo needs to be recomputed. If a meaningful modifications to the
 /// loop were made and the info wasn't recomputed properly, the behavior of all
 /// methods except for computeLoopSafetyInfo is undefined.
 class LoopSafetyInfo {
   bool MayThrow = false;       // The current loop contains an instruction which
                                // may throw.
   // Contains information about implicit control flow in this loop's blocks.
   mutable ImplicitControlFlowTracking ICF;
+
+  /// Collect all blocks from \p CurLoop which lie on all possible paths from
+  /// the header of \p CurLoop (inclusive) to BB (exclusive) into the set
+  /// \p Predecessors. If \p BB is the header, \p Predecessors will be empty.
+  void collectTransitivePredecessors(
+      const Loop *CurLoop, const BasicBlock *BB,
+      SmallPtrSetImpl<const BasicBlock *> &Predecessors) const;
+
 public:
   // Used to update funclet bundle operands.
   DenseMap<BasicBlock *, ColorVector> BlockColors;
 
   /// Returns true iff any block of the loop for which this info is contains an
   /// instruction that may throw or otherwise exit abnormally.
   bool anyBlockMayThrow() const;
 

lib/Analysis/MustExecute.cpp

static bool CanProveNotTakenFirstIteration(const BasicBlock *ExitBlock,
   if (!SimpleCst)
     return false;
   if (ExitBlock == BI->getSuccessor(0))
     return SimpleCst->isZeroValue();
   assert(ExitBlock == BI->getSuccessor(1) && "implied by above");
   return SimpleCst->isAllOnesValue();
 }
 
-
-bool LoopSafetyInfo::allLoopPathsLeadToBlock(const Loop *CurLoop,
-                                             const BasicBlock *BB,
-                                             const DominatorTree *DT) const {
+void LoopSafetyInfo::collectTransitivePredecessors(
+    const Loop *CurLoop, const BasicBlock *BB,
+    SmallPtrSetImpl<const BasicBlock *> &Predecessors) const {
+  assert(Predecessors.empty() && "Garbage in predecessors set?");
   assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
-
-  // Fast path: header is always reached once the loop is entered.
   if (BB == CurLoop->getHeader())
-    return true;
-
-  // Collect all transitive predecessors of BB in the same loop. This set will
-  // be a subset of the blocks within the loop.
-  SmallPtrSet<const BasicBlock *, 4> Predecessors;
+    return;
   SmallVector<const BasicBlock *, 4> WorkList;
   for (auto *Pred : predecessors(BB)) {
     Predecessors.insert(Pred);
     WorkList.push_back(Pred);
   }
   while (!WorkList.empty()) {
     auto *Pred = WorkList.pop_back_val();
     assert(CurLoop->contains(Pred) && "Should only reach loop blocks!");
     // We are not interested in backedges and we don't want to leave loop.
     if (Pred == CurLoop->getHeader())
       continue;
     // TODO: If BB lies in an inner loop of CurLoop, this will traverse over all
     // blocks of this inner loop, even those that are always executed AFTER the
     // BB. It may make our analysis more conservative than it could be, see test
     // @nested and @nested_no_throw in test/Analysis/MustExecute/loop-header.ll.
     // We can ignore backedge of all loops containing BB to get a sligtly more
     // optimistic result.
     for (auto *PredPred : predecessors(Pred))
       if (Predecessors.insert(PredPred).second)
         WorkList.push_back(PredPred);
   }
+}
+
+bool LoopSafetyInfo::allLoopPathsLeadToBlock(const Loop *CurLoop,
+                                             const BasicBlock *BB,
+                                             const DominatorTree *DT) const {
+  assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
+
+  // Fast path: header is always reached once the loop is entered.
+  if (BB == CurLoop->getHeader())
+    return true;
+
+  // Collect all transitive predecessors of BB in the same loop. This set will
+  // be a subset of the blocks within the loop.
+  SmallPtrSet<const BasicBlock *, 4> Predecessors;
+  collectTransitivePredecessors(CurLoop, BB, Predecessors);
 
   // Make sure that all successors of all predecessors of BB are either:
   // 1) BB,
   // 2) Also predecessors of BB,
   // 3) Exit blocks which are not taken on 1st iteration.
   // Memoize blocks we've already checked.
   SmallPtrSet<const BasicBlock *, 4> CheckedSuccessors;
   for (auto *Pred : Predecessors) {