vendor/llvm/llvm-trunk-r306956

7 files changed, 764 insertions, 537 deletions

diff --git a/include/llvm/Support/CMakeLists.txt b/include/llvm/Support/CMakeLists.txt
index c58ccf216303c..95752cf018567 100644
--- a/include/llvm/Support/CMakeLists.txt
+++ b/include/llvm/Support/CMakeLists.txt
@@ -9,25 +9,27 @@ function(find_first_existing_file out_var)
 endfunction()
 
 macro(find_first_existing_vc_file out_var path)
-  find_program(git_executable NAMES git git.exe git.cmd)
-  # Run from a subdirectory to force git to print an absolute path.
-  execute_process(COMMAND ${git_executable} rev-parse --git-dir
-    WORKING_DIRECTORY ${path}/cmake
-    RESULT_VARIABLE git_result
-    OUTPUT_VARIABLE git_dir
-    ERROR_QUIET)
-  if(git_result EQUAL 0)
-    string(STRIP "${git_dir}" git_dir)
-    set(${out_var} "${git_dir}/logs/HEAD")
-    # some branchless cases (e.g. 'repo') may not yet have .git/logs/HEAD
-    if (NOT EXISTS "${git_dir}/logs/HEAD")
-      file(WRITE "${git_dir}/logs/HEAD" "")
+  if ( LLVM_APPEND_VC_REV )
+    find_program(git_executable NAMES git git.exe git.cmd)
+    # Run from a subdirectory to force git to print an absolute path.
+    execute_process(COMMAND ${git_executable} rev-parse --git-dir
+      WORKING_DIRECTORY ${path}/cmake
+      RESULT_VARIABLE git_result
+      OUTPUT_VARIABLE git_dir
+      ERROR_QUIET)
+    if(git_result EQUAL 0)
+      string(STRIP "${git_dir}" git_dir)
+      set(${out_var} "${git_dir}/logs/HEAD")
+      # some branchless cases (e.g. 'repo') may not yet have .git/logs/HEAD
+      if (NOT EXISTS "${git_dir}/logs/HEAD")
+        file(WRITE "${git_dir}/logs/HEAD" "")
+      endif()
+    else()
+      find_first_existing_file(${out_var}
+        "${path}/.svn/wc.db"   # SVN 1.7
+        "${path}/.svn/entries" # SVN 1.6
+      )
     endif()
-  else()
-    find_first_existing_file(${out_var}
-      "${path}/.svn/wc.db"   # SVN 1.7
-      "${path}/.svn/entries" # SVN 1.6
-    )
   endif()
 endmacro()
 
diff --git a/include/llvm/Support/Errno.h b/include/llvm/Support/Errno.h
index 4ce65e7dc83c5..35dc1ea7cf84f 100644
--- a/include/llvm/Support/Errno.h
+++ b/include/llvm/Support/Errno.h
@@ -16,6 +16,7 @@
 
 #include <cerrno>
 #include <string>
+#include <type_traits>
 
 namespace llvm {
 namespace sys {
@@ -29,6 +30,16 @@ std::string StrError();
 /// Like the no-argument version above, but uses \p errnum instead of errno.
 std::string StrError(int errnum);
 
+template <typename FailT, typename Fun, typename... Args>
+inline auto RetryAfterSignal(const FailT &Fail, const Fun &F,
+                             const Args &... As) -> decltype(F(As...)) {
+  decltype(F(As...)) Res;
+  do
+    Res = F(As...);
+  while (Res == Fail && errno == EINTR);
+  return Res;
+}
+
 }  // namespace sys
 }  // namespace llvm
 
diff --git a/include/llvm/Support/GenericDomTree.h b/include/llvm/Support/GenericDomTree.h
index 601633d41cff5..394a45387d8ac 100644
--- a/include/llvm/Support/GenericDomTree.h
+++ b/include/llvm/Support/GenericDomTree.h
@@ -58,40 +58,6 @@ template <typename GT>
 using DominatorTreeBaseByGraphTraits =
     typename detail::DominatorTreeBaseTraits<GT>::type;
 
-/// \brief Base class that other, more interesting dominator analyses
-/// inherit from.
-template <class NodeT> class DominatorBase {
-protected:
-  std::vector<NodeT *> Roots;
-  bool IsPostDominators;
-
-  explicit DominatorBase(bool isPostDom)
-      : Roots(), IsPostDominators(isPostDom) {}
-
-  DominatorBase(DominatorBase &&Arg)
-      : Roots(std::move(Arg.Roots)), IsPostDominators(Arg.IsPostDominators) {
-    Arg.Roots.clear();
-  }
-
-  DominatorBase &operator=(DominatorBase &&RHS) {
-    Roots = std::move(RHS.Roots);
-    IsPostDominators = RHS.IsPostDominators;
-    RHS.Roots.clear();
-    return *this;
-  }
-
-public:
-  /// getRoots - Return the root blocks of the current CFG.  This may include
-  /// multiple blocks if we are computing post dominators.  For forward
-  /// dominators, this will always be a single block (the entry node).
-  ///
-  const std::vector<NodeT *> &getRoots() const { return Roots; }
-
-  /// isPostDominator - Returns true if analysis based of postdoms
-  ///
-  bool isPostDominator() const { return IsPostDominators; }
-};
-
 /// \brief Base class for the actual dominator tree node.
 template <class NodeT> class DomTreeNodeBase {
   friend struct PostDominatorTree;
@@ -99,12 +65,14 @@ template <class NodeT> class DomTreeNodeBase {
 
   NodeT *TheBB;
   DomTreeNodeBase *IDom;
+  unsigned Level;
   std::vector<DomTreeNodeBase *> Children;
   mutable unsigned DFSNumIn = ~0;
   mutable unsigned DFSNumOut = ~0;
 
  public:
-  DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *iDom) : TheBB(BB), IDom(iDom) {}
+  DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *iDom)
+      : TheBB(BB), IDom(iDom), Level(IDom ? IDom->Level + 1 : 0) {}
 
   using iterator = typename std::vector<DomTreeNodeBase *>::iterator;
   using const_iterator =
@@ -117,6 +85,7 @@ template <class NodeT> class DomTreeNodeBase {
 
   NodeT *getBlock() const { return TheBB; }
   DomTreeNodeBase *getIDom() const { return IDom; }
+  unsigned getLevel() const { return Level; }
 
   const std::vector<DomTreeNodeBase *> &getChildren() const { return Children; }
 
@@ -134,6 +103,8 @@ template <class NodeT> class DomTreeNodeBase {
     if (getNumChildren() != Other->getNumChildren())
       return true;
 
+    if (Level != Other->Level) return true;
+
     SmallPtrSet<const NodeT *, 4> OtherChildren;
     for (const DomTreeNodeBase *I : *Other) {
       const NodeT *Nd = I->getBlock();
@@ -150,18 +121,19 @@ template <class NodeT> class DomTreeNodeBase {
 
   void setIDom(DomTreeNodeBase *NewIDom) {
     assert(IDom && "No immediate dominator?");
-    if (IDom != NewIDom) {
-      typename std::vector<DomTreeNodeBase *>::iterator I =
-          find(IDom->Children, this);
-      assert(I != IDom->Children.end() &&
-             "Not in immediate dominator children set!");
-      // I am no longer your child...
-      IDom->Children.erase(I);
+    if (IDom == NewIDom) return;
 
-      // Switch to new dominator
-      IDom = NewIDom;
-      IDom->Children.push_back(this);
-    }
+    auto I = find(IDom->Children, this);
+    assert(I != IDom->Children.end() &&
+           "Not in immediate dominator children set!");
+    // I am no longer your child...
+    IDom->Children.erase(I);
+
+    // Switch to new dominator
+    IDom = NewIDom;
+    IDom->Children.push_back(this);
+
+    UpdateLevel();
   }
 
   /// getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes
@@ -177,6 +149,23 @@ private:
     return this->DFSNumIn >= other->DFSNumIn &&
            this->DFSNumOut <= other->DFSNumOut;
   }
+
+  void UpdateLevel() {
+    assert(IDom);
+    if (Level == IDom->Level + 1) return;
+
+    SmallVector<DomTreeNodeBase *, 64> WorkStack = {this};
+
+    while (!WorkStack.empty()) {
+      DomTreeNodeBase *Current = WorkStack.pop_back_val();
+      Current->Level = Current->IDom->Level + 1;
+
+      for (DomTreeNodeBase *C : *Current) {
+        assert(C->IDom);
+        if (C->Level != C->IDom->Level + 1) WorkStack.push_back(C);
+      }
+    }
+  }
 };
 
 template <class NodeT>
@@ -186,9 +175,10 @@ raw_ostream &operator<<(raw_ostream &O, const DomTreeNodeBase<NodeT> *Node) {
   else
     O << " <<exit node>>";
 
-  O << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "}";
+  O << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "} ["
+    << Node->getLevel() << "]\n";
 
-  return O << "\n";
+  return O;
 }
 
 template <class NodeT>
@@ -201,40 +191,28 @@ void PrintDomTree(const DomTreeNodeBase<NodeT> *N, raw_ostream &O,
     PrintDomTree<NodeT>(*I, O, Lev + 1);
 }
 
+namespace DomTreeBuilder {
+template <class NodeT>
+struct SemiNCAInfo;
+
 // 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);
 
+// The verify function is provided in a separate header but referenced here.
+template <class N>
+bool Verify(const DominatorTreeBaseByGraphTraits<GraphTraits<N>> &DT);
+}  // namespace DomTreeBuilder
+
 /// \brief Core dominator tree base class.
 ///
 /// This class is a generic template over graph nodes. It is instantiated for
 /// various graphs in the LLVM IR or in the code generator.
-template <class NodeT> class DominatorTreeBase : public DominatorBase<NodeT> {
-  bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A,
-                               const DomTreeNodeBase<NodeT> *B) const {
-    assert(A != B);
-    assert(isReachableFromEntry(B));
-    assert(isReachableFromEntry(A));
-
-    const DomTreeNodeBase<NodeT> *IDom;
-    while ((IDom = B->getIDom()) != nullptr && IDom != A && IDom != B)
-      B = IDom; // Walk up the tree
-    return IDom != nullptr;
-  }
-
-  /// \brief Wipe this tree's state without releasing any resources.
-  ///
-  /// This is essentially a post-move helper only. It leaves the object in an
-  /// assignable and destroyable state, but otherwise invalid.
-  void wipe() {
-    DomTreeNodes.clear();
-    IDoms.clear();
-    Vertex.clear();
-    Info.clear();
-    RootNode = nullptr;
-  }
+template <class NodeT> class DominatorTreeBase {
+ protected:
+  std::vector<NodeT *> Roots;
+  bool IsPostDominators;
 
-protected:
   using DomTreeNodeMapType =
      DenseMap<NodeT *, std::unique_ptr<DomTreeNodeBase<NodeT>>>;
   DomTreeNodeMapType DomTreeNodes;
@@ -242,117 +220,30 @@ protected:
 
   mutable bool DFSInfoValid = false;
   mutable unsigned int SlowQueries = 0;
-  // Information record used during immediate dominators computation.
-  struct InfoRec {
-    unsigned DFSNum = 0;
-    unsigned Parent = 0;
-    unsigned Semi = 0;
-    NodeT *Label = nullptr;
-
-    InfoRec() = default;
-  };
 
-  DenseMap<NodeT *, NodeT *> IDoms;
+  friend struct DomTreeBuilder::SemiNCAInfo<NodeT>;
+  using SNCAInfoTy = DomTreeBuilder::SemiNCAInfo<NodeT>;
 
-  // Vertex - Map the DFS number to the NodeT*
-  std::vector<NodeT *> Vertex;
-
-  // Info - Collection of information used during the computation of idoms.
-  DenseMap<NodeT *, InfoRec> Info;
-
-  void reset() {
-    DomTreeNodes.clear();
-    IDoms.clear();
-    this->Roots.clear();
-    Vertex.clear();
-    RootNode = nullptr;
-    DFSInfoValid = false;
-    SlowQueries = 0;
-  }
-
-  // NewBB is split and now it has one successor. Update dominator tree to
-  // reflect this change.
-  template <class N>
-  void Split(typename GraphTraits<N>::NodeRef NewBB) {
-    using GraphT = GraphTraits<N>;
-    using NodeRef = typename GraphT::NodeRef;
-    assert(std::distance(GraphT::child_begin(NewBB),
-                         GraphT::child_end(NewBB)) == 1 &&
-           "NewBB should have a single successor!");
-    NodeRef NewBBSucc = *GraphT::child_begin(NewBB);
-
-    std::vector<NodeRef> PredBlocks;
-    for (const auto &Pred : children<Inverse<N>>(NewBB))
-      PredBlocks.push_back(Pred);
-
-    assert(!PredBlocks.empty() && "No predblocks?");
-
-    bool NewBBDominatesNewBBSucc = true;
-    for (const auto &Pred : children<Inverse<N>>(NewBBSucc)) {
-      if (Pred != NewBB && !dominates(NewBBSucc, Pred) &&
-          isReachableFromEntry(Pred)) {
-        NewBBDominatesNewBBSucc = false;
-        break;
-      }
-    }
-
-    // Find NewBB's immediate dominator and create new dominator tree node for
-    // NewBB.
-    NodeT *NewBBIDom = nullptr;
-    unsigned i = 0;
-    for (i = 0; i < PredBlocks.size(); ++i)
-      if (isReachableFromEntry(PredBlocks[i])) {
-        NewBBIDom = PredBlocks[i];
-        break;
-      }
-
-    // It's possible that none of the predecessors of NewBB are reachable;
-    // in that case, NewBB itself is unreachable, so nothing needs to be
-    // changed.
-    if (!NewBBIDom)
-      return;
-
-    for (i = i + 1; i < PredBlocks.size(); ++i) {
-      if (isReachableFromEntry(PredBlocks[i]))
-        NewBBIDom = findNearestCommonDominator(NewBBIDom, PredBlocks[i]);
-    }
-
-    // Create the new dominator tree node... and set the idom of NewBB.
-    DomTreeNodeBase<NodeT> *NewBBNode = addNewBlock(NewBB, NewBBIDom);
-
-    // If NewBB strictly dominates other blocks, then it is now the immediate
-    // dominator of NewBBSucc.  Update the dominator tree as appropriate.
-    if (NewBBDominatesNewBBSucc) {
-      DomTreeNodeBase<NodeT> *NewBBSuccNode = getNode(NewBBSucc);
-      changeImmediateDominator(NewBBSuccNode, NewBBNode);
-    }
-  }
-
-public:
-  explicit DominatorTreeBase(bool isPostDom)
-      : DominatorBase<NodeT>(isPostDom) {}
+ public:
+  explicit DominatorTreeBase(bool isPostDom) : IsPostDominators(isPostDom) {}
 
   DominatorTreeBase(DominatorTreeBase &&Arg)
-      : DominatorBase<NodeT>(
-            std::move(static_cast<DominatorBase<NodeT> &>(Arg))),
+      : Roots(std::move(Arg.Roots)),
+        IsPostDominators(Arg.IsPostDominators),
         DomTreeNodes(std::move(Arg.DomTreeNodes)),
         RootNode(std::move(Arg.RootNode)),
         DFSInfoValid(std::move(Arg.DFSInfoValid)),
-        SlowQueries(std::move(Arg.SlowQueries)), IDoms(std::move(Arg.IDoms)),
-        Vertex(std::move(Arg.Vertex)), Info(std::move(Arg.Info)) {
+        SlowQueries(std::move(Arg.SlowQueries)) {
     Arg.wipe();
   }
 
   DominatorTreeBase &operator=(DominatorTreeBase &&RHS) {
-    DominatorBase<NodeT>::operator=(
-        std::move(static_cast<DominatorBase<NodeT> &>(RHS)));
+    Roots = std::move(RHS.Roots);
+    IsPostDominators = RHS.IsPostDominators;
     DomTreeNodes = std::move(RHS.DomTreeNodes);
     RootNode = std::move(RHS.RootNode);
     DFSInfoValid = std::move(RHS.DFSInfoValid);
     SlowQueries = std::move(RHS.SlowQueries);
-    IDoms = std::move(RHS.IDoms);
-    Vertex = std::move(RHS.Vertex);
-    Info = std::move(RHS.Info);
     RHS.wipe();
     return *this;
   }
@@ -360,6 +251,16 @@ public:
   DominatorTreeBase(const DominatorTreeBase &) = delete;
   DominatorTreeBase &operator=(const DominatorTreeBase &) = delete;
 
+  /// getRoots - Return the root blocks of the current CFG.  This may include
+  /// multiple blocks if we are computing post dominators.  For forward
+  /// dominators, this will always be a single block (the entry node).
+  ///
+  const std::vector<NodeT *> &getRoots() const { return Roots; }
+
+  /// isPostDominator - Returns true if analysis based of postdoms
+  ///
+  bool isPostDominator() const { return IsPostDominators; }
+
   /// compare - Return false if the other dominator tree base matches this
   /// dominator tree base. Otherwise return true.
   bool compare(const DominatorTreeBase &Other) const {
@@ -468,6 +369,13 @@ public:
     if (!isReachableFromEntry(A))
       return false;
 
+    if (B->getIDom() == A) return true;
+
+    if (A->getIDom() == B) return false;
+
+    // A can only dominate B if it is higher in the tree.
+    if (A->getLevel() >= B->getLevel()) return false;
+
     // Compare the result of the tree walk and the dfs numbers, if expensive
     // checks are enabled.
 #ifdef EXPENSIVE_CHECKS
@@ -499,7 +407,7 @@ public:
 
   /// findNearestCommonDominator - Find nearest common dominator basic block
   /// for basic block A and B. If there is no such block then return NULL.
-  NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) {
+  NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) const {
     assert(A->getParent() == B->getParent() &&
            "Two blocks are not in same function");
 
@@ -511,54 +419,24 @@ public:
         return &Entry;
     }
 
-    // If B dominates A then B is nearest common dominator.
-    if (dominates(B, A))
-      return B;
-
-    // If A dominates B then A is nearest common dominator.
-    if (dominates(A, B))
-      return A;
-
     DomTreeNodeBase<NodeT> *NodeA = getNode(A);
     DomTreeNodeBase<NodeT> *NodeB = getNode(B);
 
-    // If we have DFS info, then we can avoid all allocations by just querying
-    // it from each IDom. Note that because we call 'dominates' twice above, we
-    // expect to call through this code at most 16 times in a row without
-    // building valid DFS information. This is important as below is a *very*
-    // slow tree walk.
-    if (DFSInfoValid) {
-      DomTreeNodeBase<NodeT> *IDomA = NodeA->getIDom();
-      while (IDomA) {
-        if (NodeB->DominatedBy(IDomA))
-          return IDomA->getBlock();
-        IDomA = IDomA->getIDom();
-      }
-      return nullptr;
-    }
-
-    // Collect NodeA dominators set.
-    SmallPtrSet<DomTreeNodeBase<NodeT> *, 16> NodeADoms;
-    NodeADoms.insert(NodeA);
-    DomTreeNodeBase<NodeT> *IDomA = NodeA->getIDom();
-    while (IDomA) {
-      NodeADoms.insert(IDomA);
-      IDomA = IDomA->getIDom();
-    }
+    if (!NodeA || !NodeB) return nullptr;
 
-    // Walk NodeB immediate dominators chain and find common dominator node.
-    DomTreeNodeBase<NodeT> *IDomB = NodeB->getIDom();
-    while (IDomB) {
-      if (NodeADoms.count(IDomB) != 0)
-        return IDomB->getBlock();
+    // Use level information to go up the tree until the levels match. Then
+    // continue going up til we arrive at the same node.
+    while (NodeA && NodeA != NodeB) {
+      if (NodeA->getLevel() < NodeB->getLevel()) std::swap(NodeA, NodeB);
 
-      IDomB = IDomB->getIDom();
+      NodeA = NodeA->IDom;
     }
 
-    return nullptr;
+    return NodeA ? NodeA->getBlock() : nullptr;
   }
 
-  const NodeT *findNearestCommonDominator(const NodeT *A, const NodeT *B) {
+  const NodeT *findNearestCommonDominator(const NodeT *A,
+                                          const NodeT *B) const {
     // Cast away the const qualifiers here. This is ok since
     // const is re-introduced on the return type.
     return findNearestCommonDominator(const_cast<NodeT *>(A),
@@ -597,7 +475,6 @@ public:
     assert(!this->isPostDominator() &&
            "Cannot change root of post-dominator tree");
     DFSInfoValid = false;
-    auto &Roots = DominatorBase<NodeT>::Roots;
     DomTreeNodeBase<NodeT> *NewNode = (DomTreeNodes[BB] =
       llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, nullptr)).get();
     if (Roots.empty()) {
@@ -605,8 +482,10 @@ public:
     } else {
       assert(Roots.size() == 1);
       NodeT *OldRoot = Roots.front();
-      DomTreeNodes[OldRoot] =
-        NewNode->addChild(std::move(DomTreeNodes[OldRoot]));
+      auto &OldNode = DomTreeNodes[OldRoot];
+      OldNode = NewNode->addChild(std::move(DomTreeNodes[OldRoot]));
+      OldNode->IDom = NewNode;
+      OldNode->UpdateLevel();
       Roots[0] = BB;
     }
     return RootNode = NewNode;
@@ -673,45 +552,6 @@ public:
     if (getRootNode()) PrintDomTree<NodeT>(getRootNode(), O, 1);
   }
 
-protected:
-  template <class GraphT>
-  friend typename GraphT::NodeRef
-  Eval(DominatorTreeBaseByGraphTraits<GraphT> &DT, typename GraphT::NodeRef V,
-       unsigned LastLinked);
-
-  template <class GraphT>
-  friend unsigned ReverseDFSPass(DominatorTreeBaseByGraphTraits<GraphT> &DT,
-                                 typename GraphT::NodeRef V, unsigned N);
-
-  template <class GraphT>
-  friend unsigned DFSPass(DominatorTreeBaseByGraphTraits<GraphT> &DT,
-                          typename GraphT::NodeRef V, unsigned N);
-
-  template <class FuncT, class N>
-  friend void Calculate(DominatorTreeBaseByGraphTraits<GraphTraits<N>> &DT,
-                        FuncT &F);
-
-  DomTreeNodeBase<NodeT> *getNodeForBlock(NodeT *BB) {
-    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 = getIDom(BB);
-
-    assert(IDom || DomTreeNodes[nullptr]);
-    DomTreeNodeBase<NodeT> *IDomNode = getNodeForBlock(IDom);
-
-    // 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();
-  }
-
-  NodeT *getIDom(NodeT *BB) const { return IDoms.lookup(BB); }
-
-  void addRoot(NodeT *BB) { this->Roots.push_back(BB); }
-
 public:
   /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking
   /// dominator tree in dfs order.
@@ -767,23 +607,119 @@ public:
   template <class FT> void recalculate(FT &F) {
     using TraitsTy = GraphTraits<FT *>;
     reset();
-    Vertex.push_back(nullptr);
 
     if (!this->IsPostDominators) {
       // Initialize root
       NodeT *entry = TraitsTy::getEntryNode(&F);
       addRoot(entry);
 
-      Calculate<FT, NodeT *>(*this, F);
+      DomTreeBuilder::Calculate<FT, NodeT *>(*this, F);
     } else {
       // Initialize the roots list
       for (auto *Node : nodes(&F))
         if (TraitsTy::child_begin(Node) == TraitsTy::child_end(Node))
           addRoot(Node);
 
-      Calculate<FT, Inverse<NodeT *>>(*this, F);
+      DomTreeBuilder::Calculate<FT, Inverse<NodeT *>>(*this, F);
     }
   }
+
+  /// verify - check parent and sibling property
+  bool verify() const {
+    return this->isPostDominator()
+           ? DomTreeBuilder::Verify<Inverse<NodeT *>>(*this)
+           : DomTreeBuilder::Verify<NodeT *>(*this);
+  }
+
+ protected:
+  void addRoot(NodeT *BB) { this->Roots.push_back(BB); }
+
+  void reset() {
+    DomTreeNodes.clear();
+    this->Roots.clear();
+    RootNode = nullptr;
+    DFSInfoValid = false;
+    SlowQueries = 0;
+  }
+
+  // NewBB is split and now it has one successor. Update dominator tree to
+  // reflect this change.
+  template <class N>
+  void Split(typename GraphTraits<N>::NodeRef NewBB) {
+    using GraphT = GraphTraits<N>;
+    using NodeRef = typename GraphT::NodeRef;
+    assert(std::distance(GraphT::child_begin(NewBB),
+                         GraphT::child_end(NewBB)) == 1 &&
+           "NewBB should have a single successor!");
+    NodeRef NewBBSucc = *GraphT::child_begin(NewBB);
+
+    std::vector<NodeRef> PredBlocks;
+    for (const auto &Pred : children<Inverse<N>>(NewBB))
+      PredBlocks.push_back(Pred);
+
+    assert(!PredBlocks.empty() && "No predblocks?");
+
+    bool NewBBDominatesNewBBSucc = true;
+    for (const auto &Pred : children<Inverse<N>>(NewBBSucc)) {
+      if (Pred != NewBB && !dominates(NewBBSucc, Pred) &&
+          isReachableFromEntry(Pred)) {
+        NewBBDominatesNewBBSucc = false;
+        break;
+      }
+    }
+
+    // Find NewBB's immediate dominator and create new dominator tree node for
+    // NewBB.
+    NodeT *NewBBIDom = nullptr;
+    unsigned i = 0;
+    for (i = 0; i < PredBlocks.size(); ++i)
+      if (isReachableFromEntry(PredBlocks[i])) {
+        NewBBIDom = PredBlocks[i];
+        break;
+      }
+
+    // It's possible that none of the predecessors of NewBB are reachable;
+    // in that case, NewBB itself is unreachable, so nothing needs to be
+    // changed.
+    if (!NewBBIDom) return;
+
+    for (i = i + 1; i < PredBlocks.size(); ++i) {
+      if (isReachableFromEntry(PredBlocks[i]))
+        NewBBIDom = findNearestCommonDominator(NewBBIDom, PredBlocks[i]);
+    }
+
+    // Create the new dominator tree node... and set the idom of NewBB.
+    DomTreeNodeBase<NodeT> *NewBBNode = addNewBlock(NewBB, NewBBIDom);
+
+    // If NewBB strictly dominates other blocks, then it is now the immediate
+    // dominator of NewBBSucc.  Update the dominator tree as appropriate.
+    if (NewBBDominatesNewBBSucc) {
+      DomTreeNodeBase<NodeT> *NewBBSuccNode = getNode(NewBBSucc);
+      changeImmediateDominator(NewBBSuccNode, NewBBNode);
+    }
+  }
+
+ private:
+  bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A,
+                               const DomTreeNodeBase<NodeT> *B) const {
+    assert(A != B);
+    assert(isReachableFromEntry(B));
+    assert(isReachableFromEntry(A));
+
+    const DomTreeNodeBase<NodeT> *IDom;
+    while ((IDom = B->getIDom()) != nullptr && IDom != A && IDom != B)
+      B = IDom;  // Walk up the tree
+    return IDom != nullptr;
+  }
+
+  /// \brief Wipe this tree's state without releasing any resources.
+  ///
+  /// This is essentially a post-move helper only. It leaves the object in an
+  /// assignable and destroyable state, but otherwise invalid.
+  void wipe() {
+    DomTreeNodes.clear();
+    RootNode = nullptr;
+  }
 };
 
 // These two functions are declared out of line as a workaround for building
diff --git a/include/llvm/Support/GenericDomTreeConstruction.h b/include/llvm/Support/GenericDomTreeConstruction.h
index 449c385bc86a0..9edf03aa36210 100644
--- a/include/llvm/Support/GenericDomTreeConstruction.h
+++ b/include/llvm/Support/GenericDomTreeConstruction.h
@@ -10,10 +10,11 @@
 ///
 /// Generic dominator tree construction - This file provides routines to
 /// construct immediate dominator information for a flow-graph based on the
-/// algorithm described in this document:
+/// Semi-NCA algorithm described in this dissertation:
 ///
-///   A Fast Algorithm for Finding Dominators in a Flowgraph
-///   T. Lengauer & R. Tarjan, ACM TOPLAS July 1979, pgs 121-141.
+///   Linear-Time Algorithms for Dominators and Related Problems
+///   Loukas Georgiadis, Princeton University, November 2005, pp. 21-23:
+///   ftp://ftp.cs.princeton.edu/reports/2005/737.pdf
 ///
 /// This implements the O(n*log(n)) versions of EVAL and LINK, because it turns
 /// out that the theoretically slower O(n*log(n)) implementation is actually
@@ -29,256 +30,496 @@
 #include "llvm/Support/GenericDomTree.h"
 
 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;
+  };
+
+  std::vector<NodePtr> NumToNode;
+  DenseMap<NodePtr, InfoRec> NodeToInfo;
+
+  void clear() {
+    NumToNode.clear();
+    NodeToInfo.clear();
+  }
+
+  NodePtr getIDom(NodePtr BB) const {
+    auto InfoIt = NodeToInfo.find(BB);
+    if (InfoIt == NodeToInfo.end()) return nullptr;
 
-// 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.
-template <class NodeRef, class InfoType> struct df_iterator_dom_storage {
-public:
-  using BaseSet = DenseMap<NodeRef, InfoType>;
-  df_iterator_dom_storage(BaseSet &Storage) : Storage(Storage) {}
-
-  using iterator = typename BaseSet::iterator;
-  std::pair<iterator, bool> insert(NodeRef N) {
-    return Storage.insert({N, InfoType()});
+    return InfoIt->second.IDom;
   }
-  void completed(NodeRef) {}
 
-private:
-  BaseSet &Storage;
-};
+  TreeNodePtr getNodeForBlock(NodePtr BB, DomTreeT &DT) {
+    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, DT);
 
-template <class GraphT>
-unsigned ReverseDFSPass(DominatorTreeBaseByGraphTraits<GraphT> &DT,
-                        typename GraphT::NodeRef V, unsigned N) {
-  df_iterator_dom_storage<
-      typename GraphT::NodeRef,
-      typename DominatorTreeBaseByGraphTraits<GraphT>::InfoRec>
-      DFStorage(DT.Info);
-  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;
-    auto &BBInfo = DT.Info[BB];
-    BBInfo.DFSNum = BBInfo.Semi = ++N;
-    BBInfo.Label = BB;
-    // Set the parent to the top of the visited stack.  The stack includes us,
-    // and is 1 based, so we subtract to account for both of these.
-    if (I.getPathLength() > 1)
-      BBInfo.Parent = DT.Info[I.getPath(I.getPathLength() - 2)].DFSNum;
-    DT.Vertex.push_back(BB); // Vertex[n] = V;
-
-    if (IsChildOfArtificialExit)
-      BBInfo.Parent = 1;
-
-    IsChildOfArtificialExit = false;
+    // 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();
   }
-  return N;
-}
-template <class GraphT>
-unsigned DFSPass(DominatorTreeBaseByGraphTraits<GraphT> &DT,
-                 typename GraphT::NodeRef V, unsigned N) {
-  df_iterator_dom_storage<
-      typename GraphT::NodeRef,
-      typename DominatorTreeBaseByGraphTraits<GraphT>::InfoRec>
-      DFStorage(DT.Info);
-  for (auto I = df_ext_begin(V, DFStorage), E = df_ext_end(V, DFStorage);
-       I != E; ++I) {
-    typename GraphT::NodeRef BB = *I;
-    auto &BBInfo = DT.Info[BB];
-    BBInfo.DFSNum = BBInfo.Semi = ++N;
-    BBInfo.Label = BB;
-    // Set the parent to the top of the visited stack.  The stack includes us,
-    // and is 1 based, so we subtract to account for both of these.
-    if (I.getPathLength() > 1)
-      BBInfo.Parent = DT.Info[I.getPath(I.getPathLength() - 2)].DFSNum;
-    DT.Vertex.push_back(BB); // Vertex[n] = V;
+
+  // External storage for depth first iterator that reuses the info lookup map
+  // SemiNCAInfo already has. We don't have a set, but a map instead, so we are
+  // converting the one argument insert calls.
+  struct df_iterator_dom_storage {
+   public:
+    using BaseSet = decltype(NodeToInfo);
+    df_iterator_dom_storage(BaseSet &Storage) : Storage(Storage) {}
+
+    using iterator = typename BaseSet::iterator;
+    std::pair<iterator, bool> insert(NodePtr N) {
+      return Storage.insert({N, InfoRec()});
+    }
+    void completed(NodePtr) {}
+
+   private:
+    BaseSet &Storage;
+  };
+
+  df_iterator_dom_storage getStorage() { return {NodeToInfo}; }
+
+  unsigned runReverseDFS(NodePtr V, unsigned N) {
+    auto DFStorage = getStorage();
+
+    bool IsChildOfArtificialExit = (N != 0);
+    for (auto I = idf_ext_begin(V, DFStorage), E = idf_ext_end(V, DFStorage);
+         I != E; ++I) {
+      NodePtr BB = *I;
+      auto &BBInfo = NodeToInfo[BB];
+      BBInfo.DFSNum = BBInfo.Semi = ++N;
+      BBInfo.Label = BB;
+      // Set the parent to the top of the visited stack.  The stack includes us,
+      // and is 1 based, so we subtract to account for both of these.
+      if (I.getPathLength() > 1)
+        BBInfo.Parent = NodeToInfo[I.getPath(I.getPathLength() - 2)].DFSNum;
+      NumToNode.push_back(BB);  // NumToNode[n] = V;
+
+      if (IsChildOfArtificialExit)
+        BBInfo.Parent = 1;
+
+      IsChildOfArtificialExit = false;
+    }
+    return N;
   }
-  return N;
-}
 
-template <class GraphT>
-typename GraphT::NodeRef Eval(DominatorTreeBaseByGraphTraits<GraphT> &DT,
-                              typename GraphT::NodeRef VIn,
-                              unsigned LastLinked) {
-  using NodePtr = typename GraphT::NodeRef;
+  unsigned runForwardDFS(NodePtr V, unsigned N) {
+    auto DFStorage = getStorage();
+
+    for (auto I = df_ext_begin(V, DFStorage), E = df_ext_end(V, DFStorage);
+         I != E; ++I) {
+      NodePtr BB = *I;
+      auto &BBInfo = NodeToInfo[BB];
+      BBInfo.DFSNum = BBInfo.Semi = ++N;
+      BBInfo.Label = BB;
+      // Set the parent to the top of the visited stack.  The stack includes us,
+      // and is 1 based, so we subtract to account for both of these.
+      if (I.getPathLength() > 1)
+        BBInfo.Parent = NodeToInfo[I.getPath(I.getPathLength() - 2)].DFSNum;
+      NumToNode.push_back(BB);  // NumToNode[n] = V;
+    }
+    return N;
+  }
 
-  auto &VInInfo = DT.Info[VIn];
-  if (VInInfo.DFSNum < LastLinked)
-    return VIn;
+  NodePtr eval(NodePtr VIn, unsigned LastLinked) {
+    auto &VInInfo = NodeToInfo[VIn];
+    if (VInInfo.DFSNum < LastLinked)
+      return VIn;
 
-  SmallVector<NodePtr, 32> Work;
-  SmallPtrSet<NodePtr, 32> Visited;
+    SmallVector<NodePtr, 32> Work;
+    SmallPtrSet<NodePtr, 32> Visited;
 
-  if (VInInfo.Parent >= LastLinked)
-    Work.push_back(VIn);
+    if (VInInfo.Parent >= LastLinked)
+      Work.push_back(VIn);
 
-  while (!Work.empty()) {
-    NodePtr V = Work.back();
-    auto &VInfo = DT.Info[V];
-    NodePtr VAncestor = DT.Vertex[VInfo.Parent];
+    while (!Work.empty()) {
+      NodePtr V = Work.back();
+      auto &VInfo = NodeToInfo[V];
+      NodePtr VAncestor = NumToNode[VInfo.Parent];
 
-    // Process Ancestor first
-    if (Visited.insert(VAncestor).second && VInfo.Parent >= LastLinked) {
-      Work.push_back(VAncestor);
-      continue;
+      // Process Ancestor first
+      if (Visited.insert(VAncestor).second && VInfo.Parent >= LastLinked) {
+        Work.push_back(VAncestor);
+        continue;
+      }
+      Work.pop_back();
+
+      // Update VInfo based on Ancestor info
+      if (VInfo.Parent < LastLinked)
+        continue;
+
+      auto &VAInfo = NodeToInfo[VAncestor];
+      NodePtr VAncestorLabel = VAInfo.Label;
+      NodePtr VLabel = VInfo.Label;
+      if (NodeToInfo[VAncestorLabel].Semi < NodeToInfo[VLabel].Semi)
+        VInfo.Label = VAncestorLabel;
+      VInfo.Parent = VAInfo.Parent;
     }
-    Work.pop_back();
-
-    // Update VInfo based on Ancestor info
-    if (VInfo.Parent < LastLinked)
-      continue;
-
-    auto &VAInfo = DT.Info[VAncestor];
-    NodePtr VAncestorLabel = VAInfo.Label;
-    NodePtr VLabel = VInfo.Label;
-    if (DT.Info[VAncestorLabel].Semi < DT.Info[VLabel].Semi)
-      VInfo.Label = VAncestorLabel;
-    VInfo.Parent = VAInfo.Parent;
+
+    return VInInfo.Label;
   }
 
-  return VInInfo.Label;
-}
+  template <typename NodeType>
+  void runSemiNCA(DomTreeT &DT, unsigned NumBlocks) {
+    unsigned N = 0;
+    NumToNode.push_back(nullptr);
 
-template <class FuncT, class NodeT>
-void Calculate(DominatorTreeBaseByGraphTraits<GraphTraits<NodeT>> &DT,
-               FuncT &F) {
-  using GraphT = GraphTraits<NodeT>;
-  using NodePtr = typename GraphT::NodeRef;
-  static_assert(std::is_pointer<NodePtr>::value,
-                "NodeRef should be pointer type");
-  using NodeType = typename std::remove_pointer<NodePtr>::type;
+    bool MultipleRoots = (DT.Roots.size() > 1);
+    if (MultipleRoots) {
+      auto &BBInfo = NodeToInfo[nullptr];
+      BBInfo.DFSNum = BBInfo.Semi = ++N;
+      BBInfo.Label = nullptr;
 
-  unsigned N = 0;
-  bool MultipleRoots = (DT.Roots.size() > 1);
-  if (MultipleRoots) {
-    auto &BBInfo = DT.Info[nullptr];
-    BBInfo.DFSNum = BBInfo.Semi = ++N;
-    BBInfo.Label = nullptr;
+      NumToNode.push_back(nullptr); // NumToNode[n] = V;
+    }
 
-    DT.Vertex.push_back(nullptr);       // Vertex[n] = V;
-  }
+    // Step #1: Number blocks in depth-first order and initialize variables used
+    // in later stages of the algorithm.
+    if (DT.isPostDominator()){
+      for (unsigned i = 0, e = static_cast<unsigned>(DT.Roots.size());
+           i != e; ++i)
+        N = runReverseDFS(DT.Roots[i], N);
+    } else {
+      N = runForwardDFS(DT.Roots[0], N);
+    }
 
-  // Step #1: Number blocks in depth-first order and initialize variables used
-  // in later stages of the algorithm.
-  if (DT.isPostDominator()){
-    for (unsigned i = 0, e = static_cast<unsigned>(DT.Roots.size());
-         i != e; ++i)
-      N = ReverseDFSPass<GraphT>(DT, DT.Roots[i], N);
-  } else {
-    N = DFSPass<GraphT>(DT, DT.Roots[0], N);
-  }
+    // 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.
+    MultipleRoots |= (DT.isPostDominator() && N != NumBlocks);
 
-  // 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.
-  MultipleRoots |= (DT.isPostDominator() && N != GraphTraits<FuncT*>::size(&F));
+    // Initialize IDoms to spanning tree parents.
+    for (unsigned i = 1; i <= N; ++i) {
+      const NodePtr V = NumToNode[i];
+      auto &VInfo = NodeToInfo[V];
+      VInfo.IDom = NumToNode[VInfo.Parent];
+    }
 
-  // When naively implemented, the Lengauer-Tarjan algorithm requires a separate
-  // bucket for each vertex. However, this is unnecessary, because each vertex
-  // is only placed into a single bucket (that of its semidominator), and each
-  // vertex's bucket is processed before it is added to any bucket itself.
-  //
-  // Instead of using a bucket per vertex, we use a single array Buckets that
-  // has two purposes. Before the vertex V with preorder number i is processed,
-  // Buckets[i] stores the index of the first element in V's bucket. After V's
-  // bucket is processed, Buckets[i] stores the index of the next element in the
-  // bucket containing V, if any.
-  SmallVector<unsigned, 32> Buckets;
-  Buckets.resize(N + 1);
-  for (unsigned i = 1; i <= N; ++i)
-    Buckets[i] = i;
-
-  for (unsigned i = N; i >= 2; --i) {
-    NodePtr W = DT.Vertex[i];
-    auto &WInfo = DT.Info[W];
-
-    // Step #2: Implicitly define the immediate dominator of vertices
-    for (unsigned j = i; Buckets[j] != i; j = Buckets[j]) {
-      NodePtr V = DT.Vertex[Buckets[j]];
-      NodePtr U = Eval<GraphT>(DT, V, i + 1);
-      DT.IDoms[V] = DT.Info[U].Semi < i ? U : W;
+    // Step #2: Calculate the semidominators of all vertices.
+    for (unsigned i = N; 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 : inverse_children<NodeType>(W))
+        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;
+        }
     }
 
-    // Step #3: Calculate the semidominators of all vertices
+    // Step #3: 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) {
+      const NodePtr W = NumToNode[i];
+      auto &WInfo = NodeToInfo[W];
+      const unsigned SDomNum = NodeToInfo[NumToNode[WInfo.Semi]].DFSNum;
+      NodePtr WIDomCandidate = WInfo.IDom;
+      while (NodeToInfo[WIDomCandidate].DFSNum > SDomNum)
+        WIDomCandidate = NodeToInfo[WIDomCandidate].IDom;
+
+      WInfo.IDom = WIDomCandidate;
+    }
 
-    // initialize the semi dominator to point to the parent node
-    WInfo.Semi = WInfo.Parent;
-    for (const auto &N : inverse_children<NodeT>(W))
-      if (DT.Info.count(N)) { // Only if this predecessor is reachable!
-        unsigned SemiU = DT.Info[Eval<GraphT>(DT, N, i + 1)].Semi;
-        if (SemiU < WInfo.Semi)
-          WInfo.Semi = SemiU;
-      }
+    if (DT.Roots.empty()) return;
 
-    // If V is a non-root vertex and sdom(V) = parent(V), then idom(V) is
-    // necessarily parent(V). In this case, set idom(V) here and avoid placing
-    // V into a bucket.
-    if (WInfo.Semi == WInfo.Parent) {
-      DT.IDoms[W] = DT.Vertex[WInfo.Parent];
-    } else {
-      Buckets[i] = Buckets[WInfo.Semi];
-      Buckets[WInfo.Semi] = i;
+    // Add a node for the root.  This node might be the actual root, if there is
+    // 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.
+    NodePtr Root = !MultipleRoots ? DT.Roots[0] : nullptr;
+
+    DT.RootNode =
+        (DT.DomTreeNodes[Root] =
+             llvm::make_unique<DomTreeNodeBase<NodeT>>(Root, nullptr))
+            .get();
+
+    // Loop over all of the reachable blocks in the function...
+    for (unsigned i = 2; i <= N; ++i) {
+      NodePtr W = NumToNode[i];
+
+      // Don't replace this with 'count', the insertion side effect is important
+      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);
+
+      // Add a new tree node for this BasicBlock, and link it as a child of
+      // IDomNode
+      DT.DomTreeNodes[W] = IDomNode->addChild(
+          llvm::make_unique<DomTreeNodeBase<NodeT>>(W, IDomNode));
     }
   }
 
-  if (N >= 1) {
-    NodePtr Root = DT.Vertex[1];
-    for (unsigned j = 1; Buckets[j] != 1; j = Buckets[j]) {
-      NodePtr V = DT.Vertex[Buckets[j]];
-      DT.IDoms[V] = Root;
-    }
+  void doFullDFSWalk(const DomTreeT &DT) {
+    NumToNode.push_back(nullptr);
+    unsigned Num = 0;
+    for (auto *Root : DT.Roots)
+      if (!DT.isPostDominator())
+        Num = runForwardDFS(Root, Num);
+      else
+        Num = runReverseDFS(Root, Num);
   }
 
-  // Step #4: Explicitly define the immediate dominator of each vertex
-  for (unsigned i = 2; i <= N; ++i) {
-    NodePtr W = DT.Vertex[i];
-    NodePtr &WIDom = DT.IDoms[W];
-    if (WIDom != DT.Vertex[DT.Info[W].Semi])
-      WIDom = DT.IDoms[WIDom];
+  static void PrintBlockOrNullptr(raw_ostream &O, NodePtr Obj) {
+    if (!Obj)
+      O << "nullptr";
+    else
+      Obj->printAsOperand(O, false);
   }
 
-  if (DT.Roots.empty()) return;
+  // Checks if the tree contains all reachable nodes in the input graph.
+  bool verifyReachability(const DomTreeT &DT) {
+    clear();
+    doFullDFSWalk(DT);
 
-  // Add a node for the root.  This node might be the actual root, if there is
-  // 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.
-  NodePtr Root = !MultipleRoots ? DT.Roots[0] : nullptr;
+    for (auto &NodeToTN : DT.DomTreeNodes) {
+      const TreeNodePtr TN = NodeToTN.second.get();
+      const NodePtr BB = TN->getBlock();
+      if (!BB) continue;
 
-  DT.RootNode =
-      (DT.DomTreeNodes[Root] =
-           llvm::make_unique<DomTreeNodeBase<NodeType>>(Root, nullptr))
-          .get();
+      if (NodeToInfo.count(BB) == 0) {
+        errs() << "DomTree node ";
+        PrintBlockOrNullptr(errs(), BB);
+        errs() << " not found by DFS walk!\n";
+        errs().flush();
 
-  // Loop over all of the reachable blocks in the function...
-  for (unsigned i = 2; i <= N; ++i) {
-    NodePtr W = DT.Vertex[i];
+        return false;
+      }
+    }
 
-    // Don't replace this with 'count', the insertion side effect is important
-    if (DT.DomTreeNodes[W])
-      continue; // Haven't calculated this node yet?
+    return true;
+  }
 
-    NodePtr ImmDom = DT.getIDom(W);
+  // Check if for every parent with a level L in the tree all of its children
+  // have level L + 1.
+  static bool VerifyLevels(const DomTreeT &DT) {
+    for (auto &NodeToTN : DT.DomTreeNodes) {
+      const TreeNodePtr TN = NodeToTN.second.get();
+      const NodePtr BB = TN->getBlock();
+      if (!BB) continue;
+
+      const TreeNodePtr IDom = TN->getIDom();
+      if (!IDom && TN->getLevel() != 0) {
+        errs() << "Node without an IDom ";
+        PrintBlockOrNullptr(errs(), BB);
+        errs() << " has a nonzero level " << TN->getLevel() << "!\n";
+        errs().flush();
+
+        return false;
+      }
 
-    assert(ImmDom || DT.DomTreeNodes[nullptr]);
+      if (IDom && TN->getLevel() != IDom->getLevel() + 1) {
+        errs() << "Node ";
+        PrintBlockOrNullptr(errs(), BB);
+        errs() << " has level " << TN->getLevel() << " while it's IDom ";
+        PrintBlockOrNullptr(errs(), IDom->getBlock());
+        errs() << " has level " << IDom->getLevel() << "!\n";
+        errs().flush();
 
-    // Get or calculate the node for the immediate dominator
-    DomTreeNodeBase<NodeType> *IDomNode = DT.getNodeForBlock(ImmDom);
+        return false;
+      }
+    }
 
-    // Add a new tree node for this BasicBlock, and link it as a child of
-    // IDomNode
-    DT.DomTreeNodes[W] = IDomNode->addChild(
-        llvm::make_unique<DomTreeNodeBase<NodeType>>(W, IDomNode));
+    return true;
+  }
+
+  // Checks if for every edge From -> To in the graph
+  //     NCD(From, To) == IDom(To) or To.
+  bool verifyNCD(const DomTreeT &DT) {
+    clear();
+    doFullDFSWalk(DT);
+
+    for (auto &BlockToInfo : NodeToInfo) {
+      auto &Info = BlockToInfo.second;
+
+      const NodePtr From = NumToNode[Info.Parent];
+      if (!From) continue;
+
+      const NodePtr To = BlockToInfo.first;
+      const TreeNodePtr ToTN = DT.getNode(To);
+      assert(ToTN);
+
+      const NodePtr NCD = DT.findNearestCommonDominator(From, To);
+      const TreeNodePtr NCDTN = NCD ? DT.getNode(NCD) : nullptr;
+      const TreeNodePtr ToIDom = ToTN->getIDom();
+      if (NCDTN != ToTN && NCDTN != ToIDom) {
+        errs() << "NearestCommonDominator verification failed:\n\tNCD(From:";
+        PrintBlockOrNullptr(errs(), From);
+        errs() << ", To:";
+        PrintBlockOrNullptr(errs(), To);
+        errs() << ") = ";
+        PrintBlockOrNullptr(errs(), NCD);
+        errs() << ",\t (should be To or IDom[To]: ";
+        PrintBlockOrNullptr(errs(), ToIDom ? ToIDom->getBlock() : nullptr);
+        errs() << ")\n";
+        errs().flush();
+
+        return false;
+      }
+    }
+
+    return true;
+  }
+
+  // The below routines verify the correctness of the dominator tree relative to
+  // the CFG it's coming from.  A tree is a dominator tree iff it has two
+  // properties, called the parent property and the sibling property.  Tarjan
+  // and Lengauer prove (but don't explicitly name) the properties as part of
+  // the proofs in their 1972 paper, but the proofs are mostly part of proving
+  // things about semidominators and idoms, and some of them are simply asserted
+  // based on even earlier papers (see, e.g., lemma 2).  Some papers refer to
+  // these properties as "valid" and "co-valid".  See, e.g., "Dominators,
+  // directed bipolar orders, and independent spanning trees" by Loukas
+  // Georgiadis and Robert E. Tarjan, as well as "Dominator Tree Verification
+  // and Vertex-Disjoint Paths " by the same authors.
+
+  // A very simple and direct explanation of these properties can be found in
+  // "An Experimental Study of Dynamic Dominators", found at
+  // https://arxiv.org/abs/1604.02711
+
+  // The easiest way to think of the parent property is that it's a requirement
+  // of being a dominator.  Let's just take immediate dominators.  For PARENT to
+  // be an immediate dominator of CHILD, all paths in the CFG must go through
+  // PARENT before they hit CHILD.  This implies that if you were to cut PARENT
+  // out of the CFG, there should be no paths to CHILD that are reachable.  If
+  // there are, then you now have a path from PARENT to CHILD that goes around
+  // PARENT and still reaches CHILD, which by definition, means PARENT can't be
+  // a dominator of CHILD (let alone an immediate one).
+
+  // The sibling property is similar.  It says that for each pair of sibling
+  // nodes in the dominator tree (LEFT and RIGHT) , they must not dominate each
+  // other.  If sibling LEFT dominated sibling RIGHT, it means there are no
+  // paths in the CFG from sibling LEFT to sibling RIGHT that do not go through
+  // LEFT, and thus, LEFT is really an ancestor (in the dominator tree) of
+  // RIGHT, not a sibling.
+
+  // It is possible to verify the parent and sibling properties in
+  // linear time, but the algorithms are complex. Instead, we do it in a
+  // straightforward N^2 and N^3 way below, using direct path reachability.
+
+
+  // Checks if the tree has the parent property: if for all edges from V to W in
+  // the input graph, such that V is reachable, the parent of W in the tree is
+  // an ancestor of V in the tree.
+  //
+  // This means that if a node gets disconnected from the graph, then all of
+  // the nodes it dominated previously will now become unreachable.
+  bool verifyParentProperty(const DomTreeT &DT) {
+    for (auto &NodeToTN : DT.DomTreeNodes) {
+      const TreeNodePtr TN = NodeToTN.second.get();
+      const NodePtr BB = TN->getBlock();
+      if (!BB || TN->getChildren().empty()) continue;
+
+      clear();
+      NodeToInfo.insert({BB, {}});
+      doFullDFSWalk(DT);
+
+      for (TreeNodePtr Child : TN->getChildren())
+        if (NodeToInfo.count(Child->getBlock()) != 0) {
+          errs() << "Child ";
+          PrintBlockOrNullptr(errs(), Child->getBlock());
+          errs() << " reachable after its parent ";
+          PrintBlockOrNullptr(errs(), BB);
+          errs() << " is removed!\n";
+          errs().flush();
+
+          return false;
+        }
+    }
+
+    return true;
   }
 
-  // Free temporary memory used to construct idom's
-  DT.IDoms.clear();
-  DT.Info.clear();
-  DT.Vertex.clear();
-  DT.Vertex.shrink_to_fit();
+  // Check if the tree has sibling property: if a node V does not dominate a
+  // node W for all siblings V and W in the tree.
+  //
+  // This means that if a node gets disconnected from the graph, then all of its
+  // siblings will now still be reachable.
+  bool verifySiblingProperty(const DomTreeT &DT) {
+    for (auto &NodeToTN : DT.DomTreeNodes) {
+      const TreeNodePtr TN = NodeToTN.second.get();
+      const NodePtr BB = TN->getBlock();
+      if (!BB || TN->getChildren().empty()) continue;
+
+      const auto &Siblings = TN->getChildren();
+      for (const TreeNodePtr N : Siblings) {
+        clear();
+        NodeToInfo.insert({N->getBlock(), {}});
+        doFullDFSWalk(DT);
+
+        for (const TreeNodePtr S : Siblings) {
+          if (S == N) continue;
+
+          if (NodeToInfo.count(S->getBlock()) == 0) {
+            errs() << "Node ";
+            PrintBlockOrNullptr(errs(), S->getBlock());
+            errs() << " not reachable when its sibling ";
+            PrintBlockOrNullptr(errs(), N->getBlock());
+            errs() << " is removed!\n";
+            errs().flush();
+
+            return false;
+          }
+        }
+      }
+    }
+
+    return true;
+  }
+};
 
-  DT.updateDFSNumbers();
+template <class FuncT, class NodeT>
+void Calculate(DominatorTreeBaseByGraphTraits<GraphTraits<NodeT>> &DT,
+               FuncT &F) {
+  using NodePtr = typename GraphTraits<NodeT>::NodeRef;
+  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));
 }
+
+template <class NodeT>
+bool Verify(const DominatorTreeBaseByGraphTraits<GraphTraits<NodeT>> &DT) {
+  using NodePtr = typename GraphTraits<NodeT>::NodeRef;
+  static_assert(std::is_pointer<NodePtr>::value,
+                "NodePtr should be a pointer type");
+  SemiNCAInfo<typename std::remove_pointer<NodePtr>::type> SNCA;
+
+  return SNCA.verifyReachability(DT) && SNCA.VerifyLevels(DT) &&
+         SNCA.verifyNCD(DT) && SNCA.verifyParentProperty(DT) &&
+         SNCA.verifySiblingProperty(DT);
 }
 
+}  // namespace DomTreeBuilder
+}  // namespace llvm
+
 #endif
diff --git a/include/llvm/Support/TargetParser.h b/include/llvm/Support/TargetParser.h
index f29cc40ffdd55..72c28865ac575 100644
--- a/include/llvm/Support/TargetParser.h
+++ b/include/llvm/Support/TargetParser.h
@@ -17,6 +17,7 @@
 
 // FIXME: vector is used because that's what clang uses for subtarget feature
 // lists, but SmallVector would probably be better
+#include "llvm/ADT/Triple.h"
 #include <vector>
 
 namespace llvm {
@@ -140,6 +141,8 @@ unsigned parseArchEndian(StringRef Arch);
 unsigned parseArchProfile(StringRef Arch);
 unsigned parseArchVersion(StringRef Arch);
 
+StringRef computeDefaultTargetABI(const Triple &TT, StringRef CPU);
+
 } // namespace ARM
 
 // FIXME:This should be made into class design,to avoid dupplication.
diff --git a/include/llvm/Support/YAMLParser.h b/include/llvm/Support/YAMLParser.h
index c196dd6c1ddc9..549da3ccad51f 100644
--- a/include/llvm/Support/YAMLParser.h
+++ b/include/llvm/Support/YAMLParser.h
@@ -188,7 +188,7 @@ public:
   NullNode(std::unique_ptr<Document> &D)
       : Node(NK_Null, D, StringRef(), StringRef()) {}
 
-  static inline bool classof(const Node *N) { return N->getType() == NK_Null; }
+  static bool classof(const Node *N) { return N->getType() == NK_Null; }
 };
 
 /// \brief A scalar node is an opaque datum that can be presented as a
@@ -220,7 +220,7 @@ public:
   ///        This happens with escaped characters and multi-line literals.
   StringRef getValue(SmallVectorImpl<char> &Storage) const;
 
-  static inline bool classof(const Node *N) {
+  static bool classof(const Node *N) {
     return N->getType() == NK_Scalar;
   }
 
@@ -254,7 +254,7 @@ public:
   /// \brief Gets the value of this node as a StringRef.
   StringRef getValue() const { return Value; }
 
-  static inline bool classof(const Node *N) {
+  static bool classof(const Node *N) {
     return N->getType() == NK_BlockScalar;
   }
 
@@ -296,7 +296,7 @@ public:
       Val->skip();
   }
 
-  static inline bool classof(const Node *N) {
+  static bool classof(const Node *N) {
     return N->getType() == NK_KeyValue;
   }
 
@@ -419,7 +419,7 @@ public:
 
   void skip() override { yaml::skip(*this); }
 
-  static inline bool classof(const Node *N) {
+  static bool classof(const Node *N) {
     return N->getType() == NK_Mapping;
   }
 
@@ -476,7 +476,7 @@ public:
 
   void skip() override { yaml::skip(*this); }
 
-  static inline bool classof(const Node *N) {
+  static bool classof(const Node *N) {
     return N->getType() == NK_Sequence;
   }
 
@@ -502,7 +502,7 @@ public:
   StringRef getName() const { return Name; }
   Node *getTarget();
 
-  static inline bool classof(const Node *N) { return N->getType() == NK_Alias; }
+  static bool classof(const Node *N) { return N->getType() == NK_Alias; }
 
 private:
   StringRef Name;
diff --git a/include/llvm/Support/YAMLTraits.h b/include/llvm/Support/YAMLTraits.h
index 53618a56f853e..15b3b11db0451 100644
--- a/include/llvm/Support/YAMLTraits.h
+++ b/include/llvm/Support/YAMLTraits.h
@@ -180,17 +180,17 @@ struct BlockScalarTraits {
 /// to/from a YAML sequence.  For example:
 ///
 ///    template<>
-///    struct SequenceTraits< std::vector<MyType>> {
-///      static size_t size(IO &io, std::vector<MyType> &seq) {
+///    struct SequenceTraits<MyContainer> {
+///      static size_t size(IO &io, MyContainer &seq) {
 ///        return seq.size();
 ///      }
-///      static MyType& element(IO &, std::vector<MyType> &seq, size_t index) {
+///      static MyType& element(IO &, MyContainer &seq, size_t index) {
 ///        if ( index >= seq.size() )
 ///          seq.resize(index+1);
 ///        return seq[index];
 ///      }
 ///    };
-template<typename T>
+template<typename T, typename EnableIf = void>
 struct SequenceTraits {
   // Must provide:
   // static size_t size(IO &io, T &seq);
@@ -201,6 +201,14 @@ struct SequenceTraits {
   // static const bool flow = true;
 };
 
+/// This class should be specialized by any type for which vectors of that
+/// type need to be converted to/from a YAML sequence.
+template<typename T, typename EnableIf = void>
+struct SequenceElementTraits {
+  // Must provide:
+  // static const bool flow;
+};
+
 /// This class should be specialized by any type that needs to be converted
 /// to/from a list of YAML documents.
 template<typename T>
@@ -1148,7 +1156,7 @@ private:
     HNode(Node *n) : _node(n) { }
     virtual ~HNode() = default;
 
-    static inline bool classof(const HNode *) { return true; }
+    static bool classof(const HNode *) { return true; }
 
     Node *_node;
   };
@@ -1159,11 +1167,9 @@ private:
   public:
     EmptyHNode(Node *n) : HNode(n) { }
 
-    static inline bool classof(const HNode *n) {
-      return NullNode::classof(n->_node);
-    }
+    static bool classof(const HNode *n) { return NullNode::classof(n->_node); }
 
-    static inline bool classof(const EmptyHNode *) { return true; }
+    static bool classof(const EmptyHNode *) { return true; }
   };
 
   class ScalarHNode : public HNode {
@@ -1174,12 +1180,12 @@ private:
 
     StringRef value() const { return _value; }
 
-    static inline bool classof(const HNode *n) {
+    static bool classof(const HNode *n) {
       return ScalarNode::classof(n->_node) ||
              BlockScalarNode::classof(n->_node);
     }
 
-    static inline bool classof(const ScalarHNode *) { return true; }
+    static bool classof(const ScalarHNode *) { return true; }
 
   protected:
     StringRef _value;
@@ -1191,11 +1197,11 @@ private:
   public:
     MapHNode(Node *n) : HNode(n) { }
 
-    static inline bool classof(const HNode *n) {
+    static bool classof(const HNode *n) {
       return MappingNode::classof(n->_node);
     }
 
-    static inline bool classof(const MapHNode *) { return true; }
+    static bool classof(const MapHNode *) { return true; }
 
     using NameToNode = StringMap<std::unique_ptr<HNode>>;
 
@@ -1209,11 +1215,11 @@ private:
   public:
     SequenceHNode(Node *n) : HNode(n) { }
 
-    static inline bool classof(const HNode *n) {
+    static bool classof(const HNode *n) {
       return SequenceNode::classof(n->_node);
     }
 
-    static inline bool classof(const SequenceHNode *) { return true; }
+    static bool classof(const SequenceHNode *) { return true; }
 
     std::vector<std::unique_ptr<HNode>> Entries;
   };
@@ -1544,18 +1550,59 @@ operator<<(Output &yout, T &seq) {
   return yout;
 }
 
-template <typename T> struct SequenceTraitsImpl {
-  using _type = typename T::value_type;
+template <bool B> struct IsFlowSequenceBase {};
+template <> struct IsFlowSequenceBase<true> { static const bool flow = true; };
+
+template <typename T, bool Flow>
+struct SequenceTraitsImpl : IsFlowSequenceBase<Flow> {
+private:
+  using type = typename T::value_type;
 
+public:
   static size_t size(IO &io, T &seq) { return seq.size(); }
 
-  static _type &element(IO &io, T &seq, size_t index) {
+  static type &element(IO &io, T &seq, size_t index) {
     if (index >= seq.size())
       seq.resize(index + 1);
     return seq[index];
   }
 };
 
+// Simple helper to check an expression can be used as a bool-valued template
+// argument.
+template <bool> struct CheckIsBool { static const bool value = true; };
+
+// If T has SequenceElementTraits, then vector<T> and SmallVector<T, N> have
+// SequenceTraits that do the obvious thing.
+template <typename T>
+struct SequenceTraits<std::vector<T>,
+                      typename std::enable_if<CheckIsBool<
+                          SequenceElementTraits<T>::flow>::value>::type>
+    : SequenceTraitsImpl<std::vector<T>, SequenceElementTraits<T>::flow> {};
+template <typename T, unsigned N>
+struct SequenceTraits<SmallVector<T, N>,
+                      typename std::enable_if<CheckIsBool<
+                          SequenceElementTraits<T>::flow>::value>::type>
+    : SequenceTraitsImpl<SmallVector<T, N>, SequenceElementTraits<T>::flow> {};
+
+// Sequences of fundamental types use flow formatting.
+template <typename T>
+struct SequenceElementTraits<
+    T, typename std::enable_if<std::is_fundamental<T>::value>::type> {
+  static const bool flow = true;
+};
+
+// Sequences of strings use block formatting.
+template<> struct SequenceElementTraits<std::string> {
+  static const bool flow = false;
+};
+template<> struct SequenceElementTraits<StringRef> {
+  static const bool flow = false;
+};
+template<> struct SequenceElementTraits<std::pair<std::string, std::string>> {
+  static const bool flow = false;
+};
+
 /// Implementation of CustomMappingTraits for std::map<std::string, T>.
 template <typename T> struct StdMapStringCustomMappingTraitsImpl {
   using map_type = std::map<std::string, T>;
@@ -1573,42 +1620,29 @@ template <typename T> struct StdMapStringCustomMappingTraitsImpl {
 } // end namespace yaml
 } // end namespace llvm
 
-/// Utility for declaring that a std::vector of a particular type
-/// should be considered a YAML sequence.
-#define LLVM_YAML_IS_SEQUENCE_VECTOR(_type)                                    \
+#define LLVM_YAML_IS_SEQUENCE_VECTOR_IMPL(TYPE, FLOW)                          \
   namespace llvm {                                                             \
   namespace yaml {                                                             \
-  template <>                                                                  \
-  struct SequenceTraits<std::vector<_type>>                                    \
-      : public SequenceTraitsImpl<std::vector<_type>> {};                      \
-  template <unsigned N>                                                        \
-  struct SequenceTraits<SmallVector<_type, N>>                                 \
-      : public SequenceTraitsImpl<SmallVector<_type, N>> {};                   \
+  static_assert(                                                               \
+      !std::is_fundamental<TYPE>::value &&                                     \
+      !std::is_same<TYPE, std::string>::value &&                               \
+      !std::is_same<TYPE, llvm::StringRef>::value,                             \
+      "only use LLVM_YAML_IS_SEQUENCE_VECTOR for types you control");          \
+  template <> struct SequenceElementTraits<TYPE> {                             \
+    static const bool flow = FLOW;                                             \
+  };                                                                           \
   }                                                                            \
   }
 
 /// Utility for declaring that a std::vector of a particular type
+/// should be considered a YAML sequence.
+#define LLVM_YAML_IS_SEQUENCE_VECTOR(type)                                     \
+  LLVM_YAML_IS_SEQUENCE_VECTOR_IMPL(type, false)
+
+/// Utility for declaring that a std::vector of a particular type
 /// should be considered a YAML flow sequence.
-/// We need to do a partial specialization on the vector version, not a full.
-/// If this is a full specialization, the compiler is a bit too "smart" and
-/// decides to warn on -Wunused-const-variable.  This workaround can be
-/// removed and we can do a full specialization on std::vector<T> once
-/// PR28878 is fixed.
-#define LLVM_YAML_IS_FLOW_SEQUENCE_VECTOR(_type)                               \
-  namespace llvm {                                                             \
-  namespace yaml {                                                             \
-  template <unsigned N>                                                        \
-  struct SequenceTraits<SmallVector<_type, N>>                                 \
-      : public SequenceTraitsImpl<SmallVector<_type, N>> {                     \
-    static const bool flow = true;                                             \
-  };                                                                           \
-  template <typename Allocator>                                                \
-  struct SequenceTraits<std::vector<_type, Allocator>>                         \
-      : public SequenceTraitsImpl<std::vector<_type, Allocator>> {             \
-    static const bool flow = true;                                             \
-  };                                                                           \
-  }                                                                            \
-  }
+#define LLVM_YAML_IS_FLOW_SEQUENCE_VECTOR(type)                                \
+  LLVM_YAML_IS_SEQUENCE_VECTOR_IMPL(type, true)
 
 #define LLVM_YAML_DECLARE_MAPPING_TRAITS(Type)                                 \
   namespace llvm {                                                             \
@@ -1655,10 +1689,10 @@ template <typename T> struct StdMapStringCustomMappingTraitsImpl {
   namespace yaml {                                                             \
   template <unsigned N>                                                        \
   struct DocumentListTraits<SmallVector<_type, N>>                             \
-      : public SequenceTraitsImpl<SmallVector<_type, N>> {};                   \
+      : public SequenceTraitsImpl<SmallVector<_type, N>, false> {};            \
   template <>                                                                  \
   struct DocumentListTraits<std::vector<_type>>                                \
-      : public SequenceTraitsImpl<std::vector<_type>> {};                      \
+      : public SequenceTraitsImpl<std::vector<_type>, false> {};               \
   }                                                                            \
   }