[Dominators] Add NearestCommonDominator verification

[kuhar]

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.

[• dberlin]

include/llvm/Support/GenericDomTreeConstruction.h

378

probably should say what the IDOM and To are :)

[kuhar]

Update the diff. Improve the error message and documentation.

include/llvm/Support/GenericDomTree.h

 
   /// 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");
 

     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),

include/llvm/Support/GenericDomTreeConstruction.h

   }
 
   void doFullDFSWalk(const DomTreeT &DT) {
+    NumToNode.push_back(nullptr);
     unsigned Num = 0;
     for (auto *Root : DT.Roots)
       if (!DT.isPostDominator())

     return true;
   }
 
+  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);
+
+      NodePtr NCD = DT.findNearestCommonDominator(From, To);
+      TreeNodePtr NCDTN = NCD ? DT.getNode(NCD) : nullptr;
+
+      // For every edge From -> To in the graph, NCD(From, To) = IDom(To) or To.
+      if (NCDTN != ToTN && NCDTN != ToTN->getIDom()) {
+        errs() << "NearestCommonDominator verification failed:\n\tNCD(";
+        PrintBlockOrNullptr(errs(), From);
+        errs() << ", ";
+        PrintBlockOrNullptr(errs(), To);
+        errs() << ") = ";
+        PrintBlockOrNullptr(errs(), NCD);
+        errs() << "\n";
+        errs().flush();
+
+        return false;
+      }
+    }
+
+    return true;
+  }
+
   bool verifyParentProperty(const DomTreeT &DT) {
     for (auto &NodeToTN : DT.DomTreeNodes) {
       const TreeNodePtr TN = NodeToTN.second.get();

   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 detail