[NFCI] Replace linear scan with bisection.

[nicholas]

Summary

Instead of storing each DomTreeNode that we've visited and checking whether our next block is dominated by any of them, store only the blocks which aren't dominated by other blocks in the visited set, and use bisection on the dfs-in number to identify the only block in the set that might be dominating.

llvm/lib/Analysis/CFG.cpp

static bool isPotentiallyReachableFromManyDomTree(
     const DominatorTree &DT, const LoopInfo *LI) {
 
   auto NodeToBlock = [&](const DomTreeNode *Node) {
     return LI ? getOutermostLoop(LI, Node->getBlock()) : nullptr;
   };
 
   const Loop *StopLoop = NodeToBlock(StopNode);
 
+  DT.updateDFSNumbers();
+
   // 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;
+  SmallVector<const DomTreeNode *, 32> Visited;
+
+  // Insert a DomTreeNode into Visited. Coalesces redundant DomTreeNodes.
+  // Returns true iff the insertion modified Visited.
+  auto Insert = [&](const DomTreeNode *N) {
+    auto StartIt = lower_bound(
+        Visited, N, [](const DomTreeNode *LHS, const DomTreeNode *RHS) {
+          return LHS->getDFSNumIn() < RHS->getDFSNumIn();
+        });
+    if (StartIt != Visited.end() && DT.dominates(*StartIt, N))
+      return false;
+
+    // Can't be anything to coalesce if our dfs-in number is largest.
+    if (StartIt == Visited.end()) {
+      Visited.push_back(N);
+      return true;
+    }
+
+    // Linear scan to find ranges to coalesce into N.
+    ++StartIt;
+    auto EndIt = StartIt;
+    for (; EndIt != Visited.end(); ++EndIt)
+      if (!DT.dominates(N, *EndIt))
+        break;
+
+    // Nothing to coalesce, just add the new entry.
+    if (StartIt == EndIt) {
+      Visited.insert(StartIt, N);
+      return true;
+    }
+
+    // We have one or more to coalesce. Reuse one of the slots in the vector
+    // and erase the rest.
+    *StartIt = N;
+    Visited.erase(++StartIt, EndIt);
+    return true;
+  };
 
   do {
     DomTreeNode *DTN = Worklist.pop_back_val();
-
-    if (any_of(Visited, [&](const DomTreeNode *VisitedNode) {
-            return DT.dominates(VisitedNode, DTN);
-        }))
+    if (!Insert(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);
-
     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;
     }