Index: include/llvm/Support/GenericDomTreeConstruction.h
===================================================================
--- include/llvm/Support/GenericDomTreeConstruction.h
+++ include/llvm/Support/GenericDomTreeConstruction.h
@@ -27,8 +27,12 @@
 
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/Support/Debug.h"
 #include "llvm/Support/GenericDomTree.h"
 
+#define DTB_DEBUG_TYPE "dom-tree-builder"
+#define DTB_DEBUG(Arg) DEBUG_WITH_TYPE(DTB_DEBUG_TYPE, Arg)
+
 namespace llvm {
 namespace DomTreeBuilder {
 
@@ -62,11 +66,11 @@
     SmallVector<NodePtr, 2> ReverseChildren;
   };
 
-  std::vector<NodePtr> NumToNode;
+  std::vector<NodePtr> NumToNode = {nullptr};
   DenseMap<NodePtr, InfoRec> NodeToInfo;
 
   void clear() {
-    NumToNode.clear();
+    NumToNode = {nullptr};
     NodeToInfo.clear();
   }
 
@@ -177,44 +181,40 @@
     return VInInfo.Label;
   }
 
-  template <typename NodeType>
-  void runSemiNCA(DomTreeT &DT, unsigned NumBlocks) {
-    // Step #1: Number blocks in depth-first order and initialize variables used
-    // in later stages of the algorithm.
-    const unsigned N = doFullDFSWalk(DT, AlwaysDescend);
-
-    // It might be that some blocks did not get a DFS number (e.g., blocks of
-    // infinite loops). In these cases an artificial exit node is required.
-    const bool MultipleRoots =
-        DT.Roots.size() > 1 || (DT.isPostDominator() && N != NumBlocks);
-
+  void runSemiNCA(DomTreeT &DT, const unsigned MinLevel = 0) {
+    const unsigned NextDFSNum(NumToNode.size());
     // Initialize IDoms to spanning tree parents.
-    for (unsigned i = 1; i <= N; ++i) {
+    for (unsigned i = 1; i < NextDFSNum; ++i) {
       const NodePtr V = NumToNode[i];
       auto &VInfo = NodeToInfo[V];
       VInfo.IDom = NumToNode[VInfo.Parent];
     }
 
-    // Step #2: Calculate the semidominators of all vertices.
-    for (unsigned i = N; i >= 2; --i) {
+    // Step #1: Calculate the semidominators of all vertices.
+    for (unsigned i = NextDFSNum - 1; i >= 2; --i) {
       NodePtr W = NumToNode[i];
       auto &WInfo = NodeToInfo[W];
 
       // Initialize the semi dominator to point to the parent node.
       WInfo.Semi = WInfo.Parent;
-      for (const auto &N : WInfo.ReverseChildren)
-        if (NodeToInfo.count(N)) {  // Only if this predecessor is reachable!
-          unsigned SemiU = NodeToInfo[eval(N, i + 1)].Semi;
-          if (SemiU < WInfo.Semi)
-            WInfo.Semi = SemiU;
-        }
+      for (const auto &N : WInfo.ReverseChildren) {
+        if (NodeToInfo.count(N) == 0)  // Skip unreachable predecessors.
+          continue;
+
+        const TreeNodePtr TN = DT.getNode(N);
+        if (TN && TN->getLevel() < MinLevel)  // Skip too shallow predecessors.
+          continue;
+
+        unsigned SemiU = NodeToInfo[eval(N, i + 1)].Semi;
+        if (SemiU < WInfo.Semi) WInfo.Semi = SemiU;
+      }
     }
 
-    // Step #3: Explicitly define the immediate dominator of each vertex.
+    // Step #2: Explicitly define the immediate dominator of each vertex.
     //          IDom[i] = NCA(SDom[i], SpanningTreeParent(i)).
     // Note that the parents were stored in IDoms and later got invalidated
     // during path compression in Eval.
-    for (unsigned i = 2; i <= N; ++i) {
+    for (unsigned i = 2; i < NextDFSNum; ++i) {
       const NodePtr W = NumToNode[i];
       auto &WInfo = NodeToInfo[W];
       const unsigned SDomNum = NodeToInfo[NumToNode[WInfo.Semi]].DFSNum;
@@ -224,6 +224,36 @@
 
       WInfo.IDom = WIDomCandidate;
     }
+  }
+
+  template <typename DescendCondition>
+  unsigned doFullDFSWalk(const DomTreeT &DT, DescendCondition DC) {
+    unsigned Num = 0;
+
+    if (DT.Roots.size() > 1) {
+      auto &BBInfo = NodeToInfo[nullptr];
+      BBInfo.DFSNum = BBInfo.Semi = ++Num;
+      BBInfo.Label = nullptr;
+
+      NumToNode.push_back(nullptr);  // NumToNode[n] = V;
+    }
+
+    if (DT.isPostDominator()) {
+      for (auto *Root : DT.Roots) Num = runDFS<true>(Root, Num, DC, 1);
+    } else {
+      assert(DT.Roots.size() == 1);
+      Num = runDFS<false>(DT.Roots[0], Num, DC, Num);
+    }
+
+    return Num;
+  }
+
+  void calculateFromScratch(DomTreeT &DT, const unsigned NumBlocks) {
+    // Step #0: Number blocks in depth-first order and initialize variables used
+    // in later stages of the algorithm.
+    const unsigned LastDFSNum = doFullDFSWalk(DT, AlwaysDescend);
+
+    runSemiNCA(DT);
 
     if (DT.Roots.empty()) return;
 
@@ -231,25 +261,33 @@
     // one exit block, or it may be the virtual exit (denoted by
     // (BasicBlock *)0) which postdominates all real exits if there are multiple
     // exit blocks, or an infinite loop.
+    // It might be that some blocks did not get a DFS number (e.g., blocks of
+    // infinite loops). In these cases an artificial exit node is required.
+    const bool MultipleRoots = DT.Roots.size() > 1 || (DT.isPostDominator() &&
+                                                       LastDFSNum != NumBlocks);
     NodePtr Root = !MultipleRoots ? DT.Roots[0] : nullptr;
 
-    DT.RootNode =
-        (DT.DomTreeNodes[Root] =
-             llvm::make_unique<DomTreeNodeBase<NodeT>>(Root, nullptr))
-            .get();
+    DT.RootNode = (DT.DomTreeNodes[Root] =
+                       llvm::make_unique<DomTreeNodeBase<NodeT>>(Root, nullptr))
+        .get();
+    attachNewSubtree(DT, DT.RootNode);
+  }
 
-    // Loop over all of the reachable blocks in the function...
-    for (unsigned i = 2; i <= N; ++i) {
+  void attachNewSubtree(DomTreeT& DT, const TreeNodePtr AttachTo) {
+    // Attach the first unreachable block to AttachTo.
+    NodeToInfo[NumToNode[1]].IDom = AttachTo->getBlock();
+    // Loop over all of the discovered blocks in the function...
+    for (size_t i = 1, e = NumToNode.size(); i != e; ++i) {
       NodePtr W = NumToNode[i];
+      DTB_DEBUG(dbgs() << "\tdiscovereed a new reachable node ");
+      DTB_DEBUG(PrintBlockOrNullptr(dbgs(), W));
+      DTB_DEBUG(dbgs() << "\n");
 
       // Don't replace this with 'count', the insertion side effect is important
-      if (DT.DomTreeNodes[W])
-        continue; // Haven't calculated this node yet?
+      if (DT.DomTreeNodes[W]) continue;  // Haven't calculated this node yet?
 
       NodePtr ImmDom = getIDom(W);
 
-      assert(ImmDom || DT.DomTreeNodes[nullptr]);
-
       // Get or calculate the node for the immediate dominator
       TreeNodePtr IDomNode = getNodeForBlock(ImmDom, DT);
 
@@ -260,29 +298,6 @@
     }
   }
 
-  template <typename DescendCondition>
-  unsigned doFullDFSWalk(const DomTreeT &DT, DescendCondition DC) {
-    unsigned Num = 0;
-    NumToNode.push_back(nullptr);
-
-    if (DT.Roots.size() > 1) {
-      auto &BBInfo = NodeToInfo[nullptr];
-      BBInfo.DFSNum = BBInfo.Semi = ++Num;
-      BBInfo.Label = nullptr;
-
-      NumToNode.push_back(nullptr);  // NumToNode[n] = V;
-    }
-
-    if (DT.isPostDominator()) {
-      for (auto *Root : DT.Roots) Num = runDFS<true>(Root, Num, DC, 1);
-    } else {
-      assert(DT.Roots.size() == 1);
-      Num = runDFS<false>(DT.Roots[0], Num, DC, Num);
-    }
-
-    return Num;
-  }
-
   static void PrintBlockOrNullptr(raw_ostream &O, NodePtr Obj) {
     if (!Obj)
       O << "nullptr";
@@ -514,7 +529,7 @@
   static_assert(std::is_pointer<NodePtr>::value,
                 "NodePtr should be a pointer type");
   SemiNCAInfo<typename std::remove_pointer<NodePtr>::type> SNCA;
-  SNCA.template runSemiNCA<NodeT>(DT, GraphTraits<FuncT *>::size(&F));
+  SNCA.calculateFromScratch(DT, GraphTraits<FuncT *>::size(&F));
 }
 
 template <class NodeT>