Index: llvm/trunk/include/llvm/Support/GenericDomTree.h
===================================================================
--- llvm/trunk/include/llvm/Support/GenericDomTree.h
+++ llvm/trunk/include/llvm/Support/GenericDomTree.h
@@ -201,6 +201,11 @@
     PrintDomTree<NodeT>(*I, O, Lev + 1);
 }
 
+namespace DomTreeBuilder {
+template <class NodeT>
+struct SemiNCAInfo;
+}  // namespace DomTreeBuilder
+
 // The calculate routine is provided in a separate header but referenced here.
 template <class FuncT, class N>
 void Calculate(DominatorTreeBaseByGraphTraits<GraphTraits<N>> &DT, FuncT &F);
@@ -648,69 +653,14 @@
   }
 
 protected:
-  // Information record used by Semi-NCA during tree construction.
-  struct SemiNCAInfo {
-    using NodePtr = NodeT *;
-    struct InfoRec {
-      unsigned DFSNum = 0;
-      unsigned Parent = 0;
-      unsigned Semi = 0;
-      NodePtr Label = nullptr;
-      NodePtr IDom = nullptr;
-    };
-
-    std::vector<NodePtr> NumToNode;
-    DenseMap<NodePtr, InfoRec> NodeToInfo;
-
-    NodeT *getIDom(NodeT *BB) const {
-      auto InfoIt = NodeToInfo.find(BB);
-      if (InfoIt == NodeToInfo.end()) return nullptr;
-
-      return InfoIt->second.IDom;
-    }
-  };
-
-  template <class GraphT>
-  friend typename GraphT::NodeRef Eval(
-      DominatorTreeBaseByGraphTraits<GraphT> &DT, typename GraphT::NodeRef V,
-      typename DominatorTreeBaseByGraphTraits<GraphT>::SemiNCAInfo &Info,
-      unsigned LastLinked);
-
-  template <class GraphT>
-  friend unsigned ReverseDFSPass(
-      DominatorTreeBaseByGraphTraits<GraphT> &DT, typename GraphT::NodeRef V,
-      typename DominatorTreeBaseByGraphTraits<GraphT>::SemiNCAInfo &Info,
-      unsigned N);
-
-  template <class GraphT>
-  friend unsigned DFSPass(
-      DominatorTreeBaseByGraphTraits<GraphT> &DT, typename GraphT::NodeRef V,
-      typename DominatorTreeBaseByGraphTraits<GraphT>::SemiNCAInfo &Info,
-      unsigned N);
-
-  template <class FuncT, class N>
-  friend void Calculate(DominatorTreeBaseByGraphTraits<GraphTraits<N>> &DT,
-  FuncT &F);
-
-  DomTreeNodeBase<NodeT> *getNodeForBlock(NodeT *BB,
-                                          const SemiNCAInfo& SNCAInfo) {
-    if (DomTreeNodeBase<NodeT> *Node = getNode(BB))
-      return Node;
-
-    // Haven't calculated this node yet?  Get or calculate the node for the
-    // immediate dominator.
-    NodeT *IDom = SNCAInfo.getIDom(BB);
-
-    assert(IDom || DomTreeNodes[nullptr]);
-    DomTreeNodeBase<NodeT> *IDomNode = getNodeForBlock(IDom, SNCAInfo);
+ friend struct DomTreeBuilder::SemiNCAInfo<NodeT>;
+ using SNCAInfoTy = DomTreeBuilder::SemiNCAInfo<NodeT>;
 
-    // Add a new tree node for this NodeT, and link it as a child of
-    // IDomNode
-    return (DomTreeNodes[BB] = IDomNode->addChild(
-                llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode))).get();
-  }
+ template <class FuncT, class NodeTy>
+ friend void Calculate(DominatorTreeBaseByGraphTraits<GraphTraits<NodeTy>> &DT,
+                       FuncT &F);
 
-  void addRoot(NodeT *BB) { this->Roots.push_back(BB); }
+ void addRoot(NodeT *BB) { this->Roots.push_back(BB); }
 
 public:
   /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking
Index: llvm/trunk/include/llvm/Support/GenericDomTreeConstruction.h
===================================================================
--- llvm/trunk/include/llvm/Support/GenericDomTreeConstruction.h
+++ llvm/trunk/include/llvm/Support/GenericDomTreeConstruction.h
@@ -31,6 +31,54 @@
 
 namespace llvm {
 
+namespace DomTreeBuilder {
+// Information record used by Semi-NCA during tree construction.
+template <typename NodeT>
+struct SemiNCAInfo {
+  using NodePtr = NodeT *;
+  using DomTreeT = DominatorTreeBase<NodeT>;
+  using TreeNodePtr = DomTreeNodeBase<NodeT> *;
+
+  struct InfoRec {
+    unsigned DFSNum = 0;
+    unsigned Parent = 0;
+    unsigned Semi = 0;
+    NodePtr Label = nullptr;
+    NodePtr IDom = nullptr;
+  };
+
+  DomTreeT &DT;
+  std::vector<NodePtr> NumToNode;
+  DenseMap<NodePtr, InfoRec> NodeToInfo;
+
+  SemiNCAInfo(DomTreeT &DT) : DT(DT) {}
+
+  NodePtr getIDom(NodePtr BB) const {
+    auto InfoIt = NodeToInfo.find(BB);
+    if (InfoIt == NodeToInfo.end()) return nullptr;
+
+    return InfoIt->second.IDom;
+  }
+
+  TreeNodePtr getNodeForBlock(NodePtr BB) {
+    if (TreeNodePtr Node = DT.getNode(BB)) return Node;
+
+    // Haven't calculated this node yet?  Get or calculate the node for the
+    // immediate dominator.
+    NodePtr IDom = getIDom(BB);
+
+    assert(IDom || DT.DomTreeNodes[nullptr]);
+    TreeNodePtr IDomNode = getNodeForBlock(IDom);
+
+    // Add a new tree node for this NodeT, and link it as a child of
+    // IDomNode
+    return (DT.DomTreeNodes[BB] = IDomNode->addChild(
+                llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode)))
+        .get();
+  }
+};
+}  // namespace DomTreeBuilder
+
 // External storage for depth first iterator that reuses the info lookup map
 // domtree already has.  We don't have a set, but a map instead, so we are
 // converting the one argument insert calls.
@@ -49,20 +97,18 @@
   BaseSet &Storage;
 };
 
-template <class GraphT>
-unsigned ReverseDFSPass(
-    DominatorTreeBaseByGraphTraits<GraphT> &DT, typename GraphT::NodeRef V,
-    typename DominatorTreeBaseByGraphTraits<GraphT>::SemiNCAInfo &SNCA,
-    unsigned N) {
-  using SNCAInfoTy = typename std::remove_reference<decltype(SNCA)>::type;
-  df_iterator_dom_storage<typename SNCAInfoTy::NodePtr,
-      typename SNCAInfoTy::InfoRec>
-      DFStorage(SNCA.NodeToInfo);
+template <class NodePtr,
+          class NodeT = typename std::remove_pointer<NodePtr>::type>
+unsigned ReverseDFSPass(NodePtr V, DomTreeBuilder::SemiNCAInfo<NodeT> &SNCA,
+                        unsigned N) {
+  using SNCAInfoTy = DomTreeBuilder::SemiNCAInfo<NodeT>;
+  df_iterator_dom_storage<NodePtr, typename SNCAInfoTy::InfoRec> DFStorage(
+      SNCA.NodeToInfo);
 
   bool IsChildOfArtificialExit = (N != 0);
   for (auto I = idf_ext_begin(V, DFStorage), E = idf_ext_end(V, DFStorage);
        I != E; ++I) {
-    typename GraphT::NodeRef BB = *I;
+    NodePtr BB = *I;
     auto &BBInfo = SNCA.NodeToInfo[BB];
     BBInfo.DFSNum = BBInfo.Semi = ++N;
     BBInfo.Label = BB;
@@ -79,18 +125,17 @@
   }
   return N;
 }
-template <class GraphT>
-unsigned DFSPass(
-    DominatorTreeBaseByGraphTraits<GraphT> &DT, typename GraphT::NodeRef V,
-    typename DominatorTreeBaseByGraphTraits<GraphT>::SemiNCAInfo &SNCA,
-    unsigned N) {
-  using SNCAInfoTy = typename std::remove_reference<decltype(SNCA)>::type;
-  df_iterator_dom_storage<typename SNCAInfoTy::NodePtr,
-      typename SNCAInfoTy::InfoRec>
-      DFStorage(SNCA.NodeToInfo);
+
+template <class NodePtr,
+          class NodeT = typename std::remove_pointer<NodePtr>::type>
+unsigned DFSPass(NodePtr V, DomTreeBuilder::SemiNCAInfo<NodeT> &SNCA, unsigned N) {
+  using SNCAInfoTy = DomTreeBuilder::SemiNCAInfo<NodeT>;
+  df_iterator_dom_storage<NodePtr, typename SNCAInfoTy::InfoRec> DFStorage(
+      SNCA.NodeToInfo);
+
   for (auto I = df_ext_begin(V, DFStorage), E = df_ext_end(V, DFStorage);
        I != E; ++I) {
-    typename GraphT::NodeRef BB = *I;
+    NodePtr BB = *I;
     auto &BBInfo = SNCA.NodeToInfo[BB];
     BBInfo.DFSNum = BBInfo.Semi = ++N;
     BBInfo.Label = BB;
@@ -103,13 +148,10 @@
   return N;
 }
 
-template <class GraphT>
-typename GraphT::NodeRef Eval(
-    DominatorTreeBaseByGraphTraits<GraphT> &DT, typename GraphT::NodeRef VIn,
-    typename DominatorTreeBaseByGraphTraits<GraphT>::SemiNCAInfo &SNCA,
-    unsigned LastLinked) {
-  using NodePtr = typename GraphT::NodeRef;
-
+template <class NodePtr,
+          class NodeT = typename std::remove_pointer<NodePtr>::type>
+NodePtr Eval(NodePtr VIn, DomTreeBuilder::SemiNCAInfo<NodeT> &SNCA,
+             unsigned LastLinked) {
   auto &VInInfo = SNCA.NodeToInfo[VIn];
   if (VInInfo.DFSNum < LastLinked)
     return VIn;
@@ -153,11 +195,11 @@
   using GraphT = GraphTraits<NodeT>;
   using NodePtr = typename GraphT::NodeRef;
   static_assert(std::is_pointer<NodePtr>::value,
-                "NodeRef should be pointer type");
+                "NodePtr should be a pointer type");
   using NodeType = typename std::remove_pointer<NodePtr>::type;
 
   unsigned N = 0;
-  typename DominatorTreeBaseByGraphTraits<GraphT>::SemiNCAInfo SNCA;
+  DomTreeBuilder::SemiNCAInfo<NodeType> SNCA(DT);
   SNCA.NumToNode.push_back(nullptr);
 
   bool MultipleRoots = (DT.Roots.size() > 1);
@@ -174,9 +216,9 @@
   if (DT.isPostDominator()){
     for (unsigned i = 0, e = static_cast<unsigned>(DT.Roots.size());
          i != e; ++i)
-      N = ReverseDFSPass<GraphT>(DT, DT.Roots[i], SNCA, N);
+      N = ReverseDFSPass<NodePtr>(DT.Roots[i], SNCA, N);
   } else {
-    N = DFSPass<GraphT>(DT, DT.Roots[0], SNCA, N);
+    N = DFSPass<NodePtr>(DT.Roots[0], SNCA, N);
   }
 
   // It might be that some blocks did not get a DFS number (e.g., blocks of
@@ -199,7 +241,7 @@
     WInfo.Semi = WInfo.Parent;
     for (const auto &N : inverse_children<NodeT>(W))
       if (SNCA.NodeToInfo.count(N)) {  // Only if this predecessor is reachable!
-        unsigned SemiU = SNCA.NodeToInfo[Eval<GraphT>(DT, N, SNCA, i + 1)].Semi;
+        unsigned SemiU = SNCA.NodeToInfo[Eval<NodePtr>(N, SNCA, i + 1)].Semi;
         if (SemiU < WInfo.Semi)
           WInfo.Semi = SemiU;
       }
@@ -247,7 +289,7 @@
     assert(ImmDom || DT.DomTreeNodes[nullptr]);
 
     // Get or calculate the node for the immediate dominator
-    DomTreeNodeBase<NodeType> *IDomNode = DT.getNodeForBlock(ImmDom, SNCA);
+    DomTreeNodeBase<NodeType> *IDomNode = SNCA.getNodeForBlock(ImmDom);
 
     // Add a new tree node for this BasicBlock, and link it as a child of
     // IDomNode
@@ -257,6 +299,6 @@
 
   DT.updateDFSNumbers();
 }
-}
+} // namespace DomTreeBuilder
 
 #endif