[NFCI] Split isPotentiallyReachable into two implementations.

[nicholas]

Summary

The new implementations are one "fast path" implementation using the DominatorTree and not supporting ExcludedBlocks, and a "slow path" that walks BasicBlocks and supports ExcludedBlocks. Both take advantage of LoopInfo if available.

llvm/lib/Analysis/CFG.cpp

static const Loop *getOutermostLoop(const LoopInfo *LI, const BasicBlock *BB) {
   const Loop *L = LI->getLoopFor(BB);
   if (L) {
     while (const Loop *Parent = L->getParentLoop())
       L = Parent;
   }
   return L;
 }
 
-bool llvm::isPotentiallyReachableFromMany(
-    SmallVectorImpl<BasicBlock *> &Worklist, BasicBlock *StopBB,
-    const SmallPtrSetImpl<BasicBlock *> *ExclusionSet, const DominatorTree *DT,
-    const LoopInfo *LI) {
-  // When the stop block is unreachable, it's dominated from everywhere,
-  // regardless of whether there's a path between the two blocks.
-  if (DT && !DT->isReachableFromEntry(StopBB))
-    DT = nullptr;
+static bool isPotentiallyReachableFromManyDomTree(
+    SmallVectorImpl<DomTreeNode *> &Worklist, DomTreeNode *StopNode,
+    const DominatorTree &DT, const LoopInfo *LI) {
+
+  auto NodeToBlock = [&](const DomTreeNode *Node) {
+    return LI ? getOutermostLoop(LI, Node->getBlock()) : nullptr;
+  };
+
+  const Loop *StopLoop = NodeToBlock(StopNode);
+
+  // Limit the number of blocks we visit. The goal is to avoid run-away compile
+  // times on large CFGs without hampering sensible code. Arbitrarily chosen.
+  unsigned Limit = 32;
+  SmallPtrSet<const DomTreeNode *, 32> Visited;
+
+  do {
+    DomTreeNode *DTN = Worklist.pop_back_val();
+
+    if (any_of(Visited, [&](const DomTreeNode *VisitedNode) {
+            return DT.dominates(VisitedNode, DTN);
+        }))
+      continue;
+
+    if (const Loop *Outer = NodeToBlock(DTN)) {
+      // All blocks in a loop are reachable from all other blocks in the loop.
+      if (Outer == StopLoop)
+        return true;
+
+      // The loop header dominates all blocks in the loop.
+      DTN = DT.getNode(Outer->getHeader());
+    }
+
+    Visited.insert(DTN);
 
-  // We can't skip directly from a block that dominates the stop block if the
-  // exclusion block is potentially in between.
-  if (ExclusionSet && !ExclusionSet->empty())
-    DT = nullptr;
+    if (DT.dominates(DTN, StopNode))
+      return true;
+
+    if (!--Limit) {
+      // We haven't been able to prove it one way or the other. Conservatively
+      // answer true -- that there is potentially a path.
+      return true;
+    }
 
+    // The dominance check effectively visits all blocks dominated by BB. Skip
+    // over the domtree-descendants of the block to visit their successors.
+    for (auto I = df_begin(DTN), E = df_end(DTN); I != E; ++I) {
+      for (auto Succ : successors(I->getBlock())) {
+        DomTreeNode *DTSucc = DT.getNode(Succ);
+        if (!DT.dominates(DTN, DTSucc))
+          Worklist.push_back(DTSucc);
+      }
+    }
+  } while (!Worklist.empty());
+
+  // We have exhausted all possible paths and are certain that 'To' can not be
+  // reached from 'From'.
+  return false;
+}
+
+static bool isPotentiallyReachableFromManyBasicBlock(
+    SmallVectorImpl<BasicBlock *> &Worklist, BasicBlock *StopBB,
+    const SmallPtrSetImpl<BasicBlock *> *ExclusionSet,
+    const LoopInfo *LI) {
   // Normally any block in a loop is reachable from any other block in a loop,
   // however excluded blocks might partition the body of a loop to make that
   // untrue.
   SmallPtrSet<const Loop *, 8> LoopsWithHoles;
   if (LI && ExclusionSet) {
     for (auto BB : *ExclusionSet) {
       if (const Loop *L = getOutermostLoop(LI, BB))
         LoopsWithHoles.insert(L);
     }
   }
 
   const Loop *StopLoop = LI ? getOutermostLoop(LI, StopBB) : nullptr;
 
-  const DomTreeNode *StopNode = DT ? DT->getNode(StopBB) : nullptr;
-
   // Limit the number of blocks we visit. The goal is to avoid run-away compile
   // times on large CFGs without hampering sensible code. Arbitrarily chosen.
   unsigned Limit = 32;
-  SmallPtrSet<const BasicBlock*, 32> Visited;
-  SmallPtrSet<const Loop*, 32> VisitedLoops;
+  SmallPtrSet<const BasicBlock *, 32> Visited;
+  SmallPtrSet<const Loop *, 32> VisitedLoops;
+
   do {
     BasicBlock *BB = Worklist.pop_back_val();
     if (!Visited.insert(BB).second)
       continue;
     if (BB == StopBB)
       return true;
     if (ExclusionSet && ExclusionSet->count(BB))
       continue;
 
-    DomTreeNode *DTN = StopNode ? DT->getNode(BB) : nullptr;
-    if (StopNode && DTN && DT->dominates(DTN, StopNode))
-      return true;
-
     const Loop *Outer = nullptr;
     if (LI) {
       Outer = getOutermostLoop(LI, BB);
 
       // If we're in a loop with a hole, not all blocks in the loop are
       // reachable from all other blocks. That implies we can't simply jump to
       // the loop's exit blocks, as that exit might need to pass through an
       // excluded block. Clear Outer so we process BB's successors.
if (!--Limit) {
       return true;
     }
 
     if (Outer) {
       // All blocks in a single loop are reachable from all other blocks. From
       // any of these blocks, we can skip directly to the exits of the loop,
       // ignoring any other blocks inside the loop body.
       Outer->getExitBlocks(Worklist);
-    } else if (DTN) {
-      // The dominance check effectively visits all blocks dominated by BB. Skip
-      // over the domtree-descendants of the block to visit their successors.
-      for (auto I = df_begin(DTN), E = df_end(DTN); I != E;) {
-        for (auto Succ : successors(I->getBlock())) {
-          if (!DT->dominates(DTN, DT->getNode(Succ)))
-            Worklist.push_back(Succ);
-        }
-        ++I;
-        while (I != E && !Visited.insert(I->getBlock()).second) {
-          // Don't enqueue any domtree-descendants of a visited block. We've
-          // already either visited its descendants or enqueued them.
-          // I.skipChildren() implicitly performs ++I.
-          I.skipChildren();
-        }
-      }
     } else {
       Worklist.append(succ_begin(BB), succ_end(BB));
     }
   } while (!Worklist.empty());
 
   // We have exhausted all possible paths and are certain that 'To' can not be
   // reached from 'From'.
   return false;
 }
 
+bool llvm::isPotentiallyReachableFromMany(
+    SmallVectorImpl<BasicBlock *> &Worklist, BasicBlock *StopBB,
+    const SmallPtrSetImpl<BasicBlock *> *ExclusionSet, const DominatorTree *DT,
+    const LoopInfo *LI) {
+
+  auto BlockPath = [&]() {
+    return isPotentiallyReachableFromManyBasicBlock(Worklist, StopBB, ExclusionSet, LI);
+  };
+
+  if (!DT || (ExclusionSet && !ExclusionSet->empty()))
+    return BlockPath();
+
+  // When the stop block is unreachable, it's dominated from everywhere,
+  // regardless of whether there's a path between the two blocks.
+  DomTreeNode *StopNode = DT->getNode(StopBB);
+  if (!StopNode)
+    return BlockPath();
+
+  SmallVector<DomTreeNode *, 32> DTWorklist;
+  for (auto BB : Worklist) {
+    if (DTWorklist.emplace_back(DT->getNode(BB)) == nullptr)
+      return BlockPath();
+  }
+  return isPotentiallyReachableFromManyDomTree(DTWorklist, StopNode, *DT, LI);
+}
+
 bool llvm::isPotentiallyReachable(const BasicBlock *A, const BasicBlock *B,
                                   const DominatorTree *DT, const LoopInfo *LI) {
   assert(A->getParent() == B->getParent() &&
          "This analysis is function-local!");
 
   SmallVector<BasicBlock*, 32> Worklist;
   Worklist.push_back(const_cast<BasicBlock*>(A));