[Dominators] Ensure that every PostDomTree root is connected to the virtual node

[kuhar]

Summary

This patch teaches .verifyRoots to check if all roots are connected to the virtual root.

[brzycki]

Hi @kuhar , is there a testcase that causes this to fail?

[kuhar]

In D43216#1005844, @brzycki wrote:

Hi @kuhar , is there a testcase that causes this to fail?

I was only able to make it fail by manually updating the tree; this doesn't catch the recent update error reported by @dmgreen. It just made me notice that we are missing this check.
This is actually quite annoying, because with postdominators there can be multiple correct tree and the checks that we currently have are not able to ensure that after the sequence we always arrive to the same tree. For now, the other patch (D43140) makes the verifier do the comparison with a fresh tree at the end.

Let me know if you know how to ensure the PDT is in canonical form after updates, I don't have any more ideas for it :(

[dmgreen]

Ah. Ok. Common forward dominators are not roots - of course they are not. That makes this harder.

After spending a day thinking about it, I have not come up with a sensible way to check this, that doesn't devolve into recalculating the tree (or worse). Especially as in this case we can't really trust the domtree to be "correct", with respects to the roots.

I was trying to come up with something where non-roots have non-virtual idoms or are reachable from 2+ roots. I'm not sure that can work though (or how slow it could be). I guess it may be simpler to just compare against a new tree, like we have already.

include/llvm/Support/GenericDomTreeConstruction.h

         return false;
       }
 
       if (DT.getRoot() != GetEntryNode(DT)) {
         errs() << "Tree's root is not its parent's entry node!\n";
         errs().flush();
         return false;
       }
+
+      return true;
     }
 
-    RootsT ComputedRoots = FindRoots(DT, nullptr);
+    // Check PostDomTree roots.
+    const RootsT ComputedRoots = FindRoots(DT, nullptr);
     if (DT.Roots.size() != ComputedRoots.size() ||
         !std::is_permutation(DT.Roots.begin(), DT.Roots.end(),
                              ComputedRoots.begin())) {
       errs() << "Tree has different roots than freshly computed ones!\n";
       errs() << "\tPDT roots: ";
       for (const NodePtr N : DT.Roots) errs() << BlockNamePrinter(N) << ", ";
       errs() << "\n\tComputed roots: ";
       for (const NodePtr N : ComputedRoots)
         errs() << BlockNamePrinter(N) << ", ";
       errs() << "\n";
       errs().flush();
       return false;
     }
 
+    for (const NodePtr Root : ComputedRoots) {
+      const TreeNodePtr TN = DT.getNode(Root);
+      if (!TN) {
+        errs() << "Computed root: " << BlockNamePrinter(Root)
+               << " not found in the PostDomTree!\n";
+        return false;
+      }
+
+      if (!DT.isVirtualRoot(TN->getIDom())) {
+        errs() << "Computed root: " << BlockNamePrinter(TN)
+               << " is not connected to the virtual root!\n";
+        return false;
+      }
+    }
+
     return true;
   }
 
   // Checks if the tree contains all reachable nodes in the input graph.
   // Running time: O(N).
   bool verifyReachability(const DomTreeT &DT) {
     clear();
     doFullDFSWalk(DT, AlwaysDescend);