Index: llvm/lib/Analysis/CFG.cpp
===================================================================
--- llvm/lib/Analysis/CFG.cpp
+++ llvm/lib/Analysis/CFG.cpp
@@ -147,6 +147,8 @@
 
   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;
@@ -159,7 +161,9 @@
       return true;
     if (ExclusionSet && ExclusionSet->count(BB))
       continue;
-    if (DT && DT->dominates(BB, StopBB))
+
+    DomTreeNode *DTN = StopNode ? DT->getNode(BB) : nullptr;
+    if (StopNode && DTN && DT->dominates(DTN, StopNode))
       return true;
 
     const Loop *Outer = nullptr;
@@ -185,7 +189,24 @@
       // 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.
+      Visited.insert(Outer->block_begin(), Outer->block_end());
       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));
     }