[Dominators] Add parent and sibling property verification (non-hacky)

Summary:
This patch adds an additional level of verification - it checks parent and sibling properties of a tree. By definition, every tree with these two properties is a dominator tree.

It is possible to run those check by running llvm with `-verify-dom-info=1`.

Bootstrapping clang and building the llvm test suite with this option enabled doesn't yield any errors.

Reviewers: dberlin, sanjoy, chandlerc

Reviewed By: dberlin

Subscribers: llvm-commits

Differential Revision: https://reviews.llvm.org/D34482

llvm-svn: 306711

1 files changed, 15 insertions, 2 deletions

diff --git a/llvm/lib/IR/Dominators.cpp b/llvm/lib/IR/Dominators.cpp
index 37e735251fd..6ac3c5e4632 100644
--- a/llvm/lib/IR/Dominators.cpp
+++ b/llvm/lib/IR/Dominators.cpp
@@ -63,15 +63,22 @@ bool BasicBlockEdge::isSingleEdge() const {
 template class llvm::DomTreeNodeBase<BasicBlock>;
 template class llvm::DominatorTreeBase<BasicBlock>;
 
-template void llvm::Calculate<Function, BasicBlock *>(
+template void llvm::DomTreeBuilder::Calculate<Function, BasicBlock *>(
     DominatorTreeBase<
         typename std::remove_pointer<GraphTraits<BasicBlock *>::NodeRef>::type>
         &DT,
     Function &F);
-template void llvm::Calculate<Function, Inverse<BasicBlock *>>(
+template void llvm::DomTreeBuilder::Calculate<Function, Inverse<BasicBlock *>>(
     DominatorTreeBase<typename std::remove_pointer<
         GraphTraits<Inverse<BasicBlock *>>::NodeRef>::type> &DT,
     Function &F);
+template bool llvm::DomTreeBuilder::Verify<BasicBlock *>(
+    const DominatorTreeBase<
+        typename std::remove_pointer<GraphTraits<BasicBlock *>::NodeRef>::type>
+        &DT);
+template bool llvm::DomTreeBuilder::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 &) {
@@ -285,6 +292,12 @@ bool DominatorTree::isReachableFromEntry(const Use &U) const {
 }
 
 void DominatorTree::verifyDomTree() const {
+  if (!verify()) {
+    errs() << "\n~~~~~~~~~~~\n\t\tDomTree verification failed!\n~~~~~~~~~~~\n";
+    print(errs());
+    abort();
+  }
+
   Function &F = *getRoot()->getParent();
 
   DominatorTree OtherDT;