[Dominators] Add NearestCommonDominator verification

Summary:
This patch adds another verification function for checking correctness of findNearestCommonDominator.
For every edge from U to V in the input graph, `NCD(U, V) == IDom(V) or V` -- the new function checks this condition.

Reviewers: dberlin, sanjoy, chandlerc

Reviewed By: dberlin

Subscribers: llvm-commits

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

llvm-svn: 306893

2 files changed, 44 insertions, 3 deletions

diff --git a/llvm/include/llvm/Support/GenericDomTree.h b/llvm/include/llvm/Support/GenericDomTree.h
index 290515f7776..61d9c8d1b6c 100644
--- a/llvm/include/llvm/Support/GenericDomTree.h
+++ b/llvm/include/llvm/Support/GenericDomTree.h
@@ -407,7 +407,7 @@ template <class NodeT> class DominatorTreeBase {
 
   /// 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");
 
@@ -433,7 +433,8 @@ template <class NodeT> class DominatorTreeBase {
     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),
diff --git a/llvm/include/llvm/Support/GenericDomTreeConstruction.h b/llvm/include/llvm/Support/GenericDomTreeConstruction.h
index 679469ec42b..912925fecff 100644
--- a/llvm/include/llvm/Support/GenericDomTreeConstruction.h
+++ b/llvm/include/llvm/Support/GenericDomTreeConstruction.h
@@ -280,6 +280,7 @@ struct SemiNCAInfo {
   }
 
   void doFullDFSWalk(const DomTreeT &DT) {
+    NumToNode.push_back(nullptr);
     unsigned Num = 0;
     for (auto *Root : DT.Roots)
       if (!DT.isPostDominator())
@@ -351,6 +352,44 @@ struct SemiNCAInfo {
     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;
+  }
+
   // 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.
@@ -439,7 +478,8 @@ bool Verify(const DominatorTreeBaseByGraphTraits<GraphTraits<NodeT>> &DT) {
   SemiNCAInfo<typename std::remove_pointer<NodePtr>::type> SNCA;
 
   return SNCA.verifyReachability(DT) && SNCA.VerifyLevels(DT) &&
-         SNCA.verifyParentProperty(DT) && SNCA.verifySiblingProperty(DT);
+         SNCA.verifyNCD(DT) && SNCA.verifyParentProperty(DT) &&
+         SNCA.verifySiblingProperty(DT);
 }
 
 }  // namespace DomTreeBuilder