Index: include/llvm/IR/Dominators.h
===================================================================
--- include/llvm/IR/Dominators.h
+++ include/llvm/IR/Dominators.h
@@ -42,6 +42,11 @@
     DominatorTreeBaseByGraphTraits<GraphTraits<Inverse<BasicBlock *>>> &DT,
     Function &F);
 
+extern template bool Verify<BasicBlock *>(
+    const DominatorTreeBaseByGraphTraits<GraphTraits<BasicBlock *>> &DT);
+extern template bool Verify<Inverse<BasicBlock *>>(
+    const DominatorTreeBaseByGraphTraits<GraphTraits<Inverse<BasicBlock *>>> &DT);
+
 using DomTreeNode = DomTreeNodeBase<BasicBlock>;
 
 class BasicBlockEdge {
Index: include/llvm/Support/GenericDomTree.h
===================================================================
--- include/llvm/Support/GenericDomTree.h
+++ include/llvm/Support/GenericDomTree.h
@@ -205,6 +205,9 @@
 template <class FuncT, class N>
 void Calculate(DominatorTreeBaseByGraphTraits<GraphTraits<N>> &DT, FuncT &F);
 
+template <class N>
+bool Verify(const DominatorTreeBaseByGraphTraits<GraphTraits<N>> &DT);
+
 /// \brief Core dominator tree base class.
 ///
 /// This class is a generic template over graph nodes. It is instantiated for
@@ -255,10 +258,10 @@
   DenseMap<NodeT *, NodeT *> IDoms;
 
   // Vertex - Map the DFS number to the NodeT*
-  std::vector<NodeT *> Vertex;
+  mutable std::vector<NodeT *> Vertex;
 
   // Info - Collection of information used during the computation of idoms.
-  DenseMap<NodeT *, InfoRec> Info;
+  mutable DenseMap<NodeT *, InfoRec> Info;
 
   void reset() {
     DomTreeNodes.clear();
@@ -329,6 +332,7 @@
   }
 
 public:
+  using NodePtr = DomTreeNodeBase<NodeT> *;
   explicit DominatorTreeBase(bool isPostDom)
       : DominatorBase<NodeT>(isPostDom) {}
 
@@ -680,17 +684,32 @@
        unsigned LastLinked);
 
   template <class GraphT>
-  friend unsigned ReverseDFSPass(DominatorTreeBaseByGraphTraits<GraphT> &DT,
+  friend unsigned ReverseDFSPass(const DominatorTreeBaseByGraphTraits<GraphT> &DT,
                                  typename GraphT::NodeRef V, unsigned N);
 
   template <class GraphT>
-  friend unsigned DFSPass(DominatorTreeBaseByGraphTraits<GraphT> &DT,
+  friend unsigned DFSPass(const DominatorTreeBaseByGraphTraits<GraphT> &DT,
                           typename GraphT::NodeRef V, unsigned N);
 
   template <class FuncT, class N>
   friend void Calculate(DominatorTreeBaseByGraphTraits<GraphTraits<N>> &DT,
                         FuncT &F);
 
+  template <class GraphT>
+  friend void RunDFS(const DominatorTreeBaseByGraphTraits<GraphT> &DT);
+
+  template <class GraphT>
+  friend bool VerifyReachability(const DominatorTreeBaseByGraphTraits<GraphT> &DT);
+
+  template <class GraphT>
+  friend bool VerifyParentProperty(const DominatorTreeBaseByGraphTraits<GraphT> &DT);
+
+  template <class GraphT>
+  friend bool VerifySiblingProperty(const DominatorTreeBaseByGraphTraits<GraphT> &DT);
+
+  template <class N>
+  friend bool Verify(const DominatorTreeBaseByGraphTraits<GraphTraits<N>> &DT);
+
   DomTreeNodeBase<NodeT> *getNodeForBlock(NodeT *BB) {
     if (DomTreeNodeBase<NodeT> *Node = getNode(BB))
       return Node;
@@ -763,6 +782,12 @@
     DFSInfoValid = true;
   }
 
+  /// verify - checks parent and sibling property
+  bool verify() const {
+    return this->isPostDominator() ? Verify<Inverse<NodeT *>>(*this)
+                                   : Verify<NodeT *>(*this);
+  }
+
   /// recalculate - compute a dominator tree for the given function
   template <class FT> void recalculate(FT &F) {
     using TraitsTy = GraphTraits<FT *>;
@@ -775,6 +800,7 @@
       addRoot(entry);
 
       Calculate<FT, NodeT *>(*this, F);
+      Verify<NodeT *>(*this);
     } else {
       // Initialize the roots list
       for (auto *Node : nodes(&F))
@@ -782,6 +808,7 @@
           addRoot(Node);
 
       Calculate<FT, Inverse<NodeT *>>(*this, F);
+      Verify<Inverse<NodeT *>>(*this);
     }
   }
 };
Index: include/llvm/Support/GenericDomTreeConstruction.h
===================================================================
--- include/llvm/Support/GenericDomTreeConstruction.h
+++ include/llvm/Support/GenericDomTreeConstruction.h
@@ -27,6 +27,7 @@
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Support/GenericDomTree.h"
+#include "llvm/Support/raw_ostream.h"
 
 namespace llvm {
 
@@ -49,7 +50,7 @@
 };
 
 template <class GraphT>
-unsigned ReverseDFSPass(DominatorTreeBaseByGraphTraits<GraphT> &DT,
+unsigned ReverseDFSPass(const DominatorTreeBaseByGraphTraits<GraphT> &DT,
                         typename GraphT::NodeRef V, unsigned N) {
   df_iterator_dom_storage<
       typename GraphT::NodeRef,
@@ -76,7 +77,7 @@
   return N;
 }
 template <class GraphT>
-unsigned DFSPass(DominatorTreeBaseByGraphTraits<GraphT> &DT,
+unsigned DFSPass(const DominatorTreeBaseByGraphTraits<GraphT> &DT,
                  typename GraphT::NodeRef V, unsigned N) {
   df_iterator_dom_storage<
       typename GraphT::NodeRef,
@@ -279,6 +280,123 @@
 
   DT.updateDFSNumbers();
 }
+
+
+template <class GraphT>
+void RunDFS(const DominatorTreeBaseByGraphTraits<GraphT> &DT) {
+  unsigned Num = 0;
+  for (auto *Root : DT.Roots)
+    if (!DT.isPostDominator())
+      Num = DFSPass<GraphT>(DT, Root, Num);
+    else
+      Num = ReverseDFSPass<GraphT>(DT, Root, Num);
+
+  DT.Vertex.clear();
+}
+
+template <class GraphT>
+bool VerifyReachability(const DominatorTreeBaseByGraphTraits<GraphT> &DT) {
+  using BlockPtr = typename GraphT::NodeRef;
+  using NodePtr =
+  DomTreeNodeBase<typename std::remove_pointer<BlockPtr>::type> *;
+
+  DT.Info.clear();
+  RunDFS<GraphT>(DT);
+
+  for (auto &NodeToTN : DT.DomTreeNodes) {
+    const NodePtr TN = NodeToTN.second.get();
+    const BlockPtr BB = TN->getBlock();
+    if (!BB)
+      continue;
+
+    if (DT.Info.count(BB) == 0) {
+      errs() << "DomTree node not found by DFS walk!\n";
+      errs().flush();
+      DT.Info.clear();
+      return false;
+    }
+  }
+
+  DT.Info.clear();
+  return true;
+}
+
+template <class GraphT>
+bool VerifyParentProperty(const DominatorTreeBaseByGraphTraits<GraphT> &DT) {
+  using BlockPtr = typename GraphT::NodeRef;
+  using NodePtr =
+                DomTreeNodeBase<typename std::remove_pointer<BlockPtr>::type> *;
+  for (auto &NodeToTN : DT.DomTreeNodes) {
+    const NodePtr TN = NodeToTN.second.get();
+    const BlockPtr BB = TN->getBlock();
+    if (!BB || TN->getChildren().empty())
+      continue;
+
+    DT.Info.clear();
+    DT.Info.insert({BB, {}});
+    RunDFS<GraphT>(DT);
+
+    for (NodePtr Child : TN->getChildren())
+      if (DT.Info.count(Child->getBlock()) != 0) {
+        errs() << "Child reachable after its parent is removed!\n";
+        errs().flush();
+        DT.Info.clear();
+        return false;
+      }
+  }
+
+  DT.Info.clear();
+  return true;
+}
+
+template <class GraphT>
+bool VerifySiblingProperty(const DominatorTreeBaseByGraphTraits<GraphT> &DT) {
+  using BlockPtr = typename GraphT::NodeRef;
+  using NodePtr =
+  DomTreeNodeBase<typename std::remove_pointer<BlockPtr>::type> *;
+
+  for (auto &NodeToTN : DT.DomTreeNodes) {
+    const NodePtr TN = NodeToTN.second.get();
+    const BlockPtr BB = TN->getBlock();
+    if (!BB || TN->getChildren().empty())
+      continue;
+
+    const auto& Siblings = TN->getChildren();
+    for (const NodePtr N : Siblings) {
+      for (const NodePtr S : Siblings) {
+        if (S == N)
+          continue;
+
+        DT.Info.clear();
+        DT.Info.insert({S->getBlock(), {}});
+        RunDFS<GraphT>(DT);
+
+        if (DT.Info.count(N->getBlock()) == 0) {
+          errs() << "Node not reachable when its sibling is removed!\n";
+          errs().flush();
+          DT.Info.clear();
+          return false;
+        }
+      }
+    }
+  }
+
+  DT.Info.clear();
+  return true;
+}
+
+template <class NodeT>
+bool Verify(const DominatorTreeBaseByGraphTraits<GraphTraits<NodeT>> &DT) {
+  bool Correct = VerifyReachability<GraphTraits<NodeT>>(DT) &&
+                 VerifyParentProperty<GraphTraits<NodeT>>(DT) &&
+                 VerifySiblingProperty<GraphTraits<NodeT>>(DT);
+  if (Correct)
+    return true;
+
+  errs() << "\n~~~~~~~~~~~~~~~~~~\n\t\tIncorrect DomTree!\n~~~~~~~~~~~~~~~~\n";
+  return false;
+}
+
 }
 
 #endif
Index: lib/IR/Dominators.cpp
===================================================================
--- lib/IR/Dominators.cpp
+++ lib/IR/Dominators.cpp
@@ -73,6 +73,14 @@
         GraphTraits<Inverse<BasicBlock *>>::NodeRef>::type> &DT,
     Function &F);
 
+template bool llvm::Verify<BasicBlock *>(
+    const DominatorTreeBase<
+        typename std::remove_pointer<GraphTraits<BasicBlock *>::NodeRef>::type>
+    &DT);
+template bool llvm::Verify<Inverse<BasicBlock *>>(
+    const DominatorTreeBase<typename std::remove_pointer<
+        GraphTraits<Inverse<BasicBlock *>>::NodeRef>::type> &DT);
+
 bool DominatorTree::invalidate(Function &F, const PreservedAnalyses &PA,
                                FunctionAnalysisManager::Invalidator &) {
   // Check whether the analysis, all analyses on functions, or the function's
@@ -285,6 +293,9 @@
 }
 
 void DominatorTree::verifyDomTree() const {
+  if (!verify())
+    abort();
+
   Function &F = *getRoot()->getParent();
 
   DominatorTree OtherDT;