Index: llvm/lib/Analysis/CFG.cpp
===================================================================
--- llvm/lib/Analysis/CFG.cpp
+++ llvm/lib/Analysis/CFG.cpp
@@ -130,17 +130,52 @@
 
   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)) {
@@ -152,8 +187,6 @@
       DTN = DT.getNode(Outer->getHeader());
     }
 
-    Visited.insert(DTN);
-
     if (DT.dominates(DTN, StopNode))
       return true;