[Dominators] Improve reachability verification

[kuhar]

Summary

This patch improves verification by making verifyReachablility look for CFG not found in the DomTree.
It also makes the verification work with postdominators by handling virtual root.

[• dberlin]

include/llvm/Support/GenericDomTreeConstruction.h

302

It's more accurate to state that the virtual root *is* a cfg node. Or at least it was.
At least as used previously, the virtual root was not really a dom tree root, it was really the thing that contained the edges to the blocks.

The virtual dom tree root was then the dom tree node that got built for the virtual cfg root.

I don't know if this is still the case.

305

When is it possible to have !BB but it's not a virtual root?
If it's really possible, please document this condition.

[kuhar]

include/llvm/Support/GenericDomTreeConstruction.h

302

I mean, if you ask a virtual root for its (CFG) block, it returns a nullptr. Do you consider this nullptr block a virtual CFG exit node?

302

(Or in the future, a virtual entry block for dominators?)

305

It's just an oversight when cherry-picking changes :)

[• dberlin]

include/llvm/Support/GenericDomTreeConstruction.h

302

The fact that we don't hand the virtual CFG block to people is fine (but possibly annoying):

Remember the dominator tree does not have predecessor edges, etc.

So either you are hard coding the logic for it being a CFG block, or it's really got a virtual CFG block :P

Right now I believe it's the case we hard-code the logic during post-dom construction.

[kuhar]

include/llvm/Support/GenericDomTreeConstruction.h

302

Is it better now?

include/llvm/Support/GenericDomTree.h

#endif
   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));
   }
 
+  bool isVirtualRoot(const DomTreeNodeBase<NodeT> *A) const {
+    return isPostDominator() && !A->getBlock();
+  }
+
   //===--------------------------------------------------------------------===//
   // API to update (Post)DominatorTree information based on modifications to
   // the CFG...
 
   /// Add a new node to the dominator tree information.
   ///
   /// This creates a new node as a child of DomBB dominator node, linking it
   /// into the children list of the immediate dominator.

include/llvm/Support/GenericDomTreeConstruction.h

struct SemiNCAInfo {
   // Checks if the tree contains all reachable nodes in the input graph.
   bool verifyReachability(const DomTreeT &DT) {
     clear();
     doFullDFSWalk(DT, AlwaysDescend);
 
     for (auto &NodeToTN : DT.DomTreeNodes) {
       const TreeNodePtr TN = NodeToTN.second.get();
       const NodePtr BB = TN->getBlock();
-      if (!BB) continue;
 
-      if (NodeToInfo.count(BB) == 0) {
+      // Virtual root doesn't have a corresponding CFG node.
+      if (DT.isVirtualRoot(TN)) continue;
+
+      if (!BB || NodeToInfo.count(BB) == 0) {
         errs() << "DomTree node ";
         PrintBlockOrNullptr(errs(), BB);
         errs() << " not found by DFS walk!\n";
         errs().flush();
 
         return false;
       }
     }
 
+    for (const NodePtr N : NumToNode) {
+      if (N && !DT.getNode(N)) {
+        errs() << "CFG node ";
+        PrintBlockOrNullptr(errs(), N);
+        errs() << " not found in the DomTree!\n";
+        errs().flush();
+
+        return false;
+      }
+    }
+
     return true;
   }
 
   // Check if for every parent with a level L in the tree all of its children
   // have level L + 1.
   static bool VerifyLevels(const DomTreeT &DT) {
     for (auto &NodeToTN : DT.DomTreeNodes) {
       const TreeNodePtr TN = NodeToTN.second.get();
for (auto &BlockToInfo : NodeToInfo) {
       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 NCDTN = DT.getNode(NCD);
       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);