[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 ↗

(On Diff #103781)

probably should say what the IDOM and To are :)

[kuhar]

Update the diff. Improve the error message and documentation.

llvm/trunk/include/llvm/Support/GenericDomTree.h

#endif
 
   NodeT *getRoot() const {
     assert(this->Roots.size() == 1 && "Should always have entry node!");
     return this->Roots[0];
   }
 
   /// 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");
 
     // If either A or B is a entry block then it is nearest common dominator
     // (for forward-dominators).
     if (!this->isPostDominator()) {
       NodeT &Entry = A->getParent()->front();
       if (A == &Entry || B == &Entry)
while (NodeA && NodeA != NodeB) {
       if (NodeA->getLevel() < NodeB->getLevel()) std::swap(NodeA, NodeB);
 
       NodeA = NodeA->IDom;
     }
 
     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),
                                       const_cast<NodeT *>(B));
   }
 
   //===--------------------------------------------------------------------===//
   // API to update (Post)DominatorTree information based on modifications to

llvm/trunk/include/llvm/Support/GenericDomTreeConstruction.h

for (unsigned i = 2; i <= N; ++i) {
       // 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));
     }
   }
 
   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);
   }
 
for (auto &NodeToTN : DT.DomTreeNodes) {
 
         return false;
       }
     }
 
     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.
   //
   // 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) {

 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.verifyParentProperty(DT) && SNCA.verifySiblingProperty(DT);
+         SNCA.verifyNCD(DT) && SNCA.verifyParentProperty(DT) &&
+         SNCA.verifySiblingProperty(DT);
 }
 
 }  // namespace DomTreeBuilder
 }  // namespace llvm
 
 #endif