[Dominators] Always recalculate postdominators when update yields different roots

[kuhar]

Summary

This patch makes postdominators always recalculate the tree when an update causes to change the tree roots.
As @dmgreen noticed in D41298, the previous implementation was not conservative enough and it was possible to end up with a PostDomTree that was different than a freshly computed one.
The patch also compares postdominators with a freshly computed tree at the end of full verification to make sure we don't hit similar issues in the future.

This should (ideally) be also backported to 6.0 before the release, although I don't have any reports of this causing an observable error. It should be safe to do it even if it's late in the release, as the change only makes the current behavior more conservative.

[dmgreen]

Thanks for this! I obviously think this looks fine, but I will let someone who knows more about this to check it's OK too.

But any idea why verifyRoots did not catch this case already? If the newly calculated roots are different from what is in the PDT.

[grosser]

That's a good improvement. Thanks for adding it.

include/llvm/Support/GenericDomTreeConstruction.h

706 ↗

(On Diff #133678)

which NODE within (without the 's')

[kuhar]

In D43140#1004849, @dmgreen wrote:

But any idea why verifyRoots did not catch this case already? If the newly calculated roots are different from what is in the PDT.

The reasoning behind the original implementation was that there are multiple correct postdominator trees for some CFG-s (in particular, when there are infinite loops), but we wanted to have just one canonical postdomtree that we end up with, no matter if we get it as a result of an update or by fresh construction. I though that it would be sufficient to check whether the new set of roots if also a root for the current CFG, but your example with InsertReachable2 showed there are cases were it's not enough and we have to look deeper. And I think that your previous patch to the root selection made some cases like this that crashed the original implementation to silently continue instead, which is how we ended up in the current situation.

[brzycki]

LGTM. Out of curiosity does this change impact compile time?

[kuhar]

In D43140#1005098, @brzycki wrote:

LGTM. Out of curiosity does this change impact compile time?

I haven't checked, but from my previous experiments I doubt it does -- forming or to infinite loops are very rare, and this piece of code was only executed a few times when compiling clang or sqlite. I don't have numbers for it, but could get them later this week if someone's really interested.

[brzycki]

I haven't checked, but from my previous experiments I doubt it does -- forming or to infinite loops are very rare, and this piece of code was only executed a few times when compiling clang or sqlite. I don't have numbers for it, but could get them later this week if someone's really interested.

Don't spend too much time on it if you're confident it's not an issue. I was just curious in case you had already run the numbers. PDT is used less than DT all around the middle end which is also why I suspect you haven't seen this issue in 6.0.

[dmgreen]

But any idea why verifyRoots did not catch this case already?

Ah, I see. The roots were the same as newly calculated roots, but roots and the tree didn't match up. What do you think about adding a check for that to verifyRoots? (Not in this commit, I'm just throwing around ideas here). Or do you think a check against the recalculated tree is good enough? Something like:

for each node in tree:
  if node in roots:
    check node->idom == virtual root
  else
    check node->idom != virtual root

[kuhar]

In D43140#1005362, @dmgreen wrote:

But any idea why verifyRoots did not catch this case already?

Ah, I see. The roots were the same as newly calculated roots, but roots and the tree didn't match up. What do you think about adding a check for that to verifyRoots? (Not in this commit, I'm just throwing around ideas here). Or do you think a check against the recalculated tree is good enough? Something like:

for each node in tree:
  if node in roots:
    check node->idom == virtual root
  else
    check node->idom != virtual root

Yes, I think that is missing from the current implementation.

[kuhar]

In D43140#1005376, @kuhar wrote:

In D43140#1005362, @dmgreen wrote:

But any idea why verifyRoots did not catch this case already?

Ah, I see. The roots were the same as newly calculated roots, but roots and the tree didn't match up. What do you think about adding a check for that to verifyRoots? (Not in this commit, I'm just throwing around ideas here). Or do you think a check against the recalculated tree is good enough? Something like:

for each node in tree:
  if node in roots:
    check node->idom == virtual root
  else
    check node->idom != virtual root

Yes, I think that is missing from the current implementation.

Forgot to mention: your pseudocode is not entirely correct -- there can be nodes connected to the virtual root that are not tree roots (e.g. diamond: entry, if then, else, exit) . But all roots have to be connected to the virtual root.

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

static void UpdateRootsAfterUpdate(DomTreeT &DT, const BatchUpdatePtr BUI) {
 
     // The tree has only trivial roots -- nothing to update.
     if (std::none_of(DT.Roots.begin(), DT.Roots.end(), [BUI](const NodePtr N) {
           return HasForwardSuccessors(N, BUI);
         }))
       return;
 
     // Recalculate the set of roots.
-    DT.Roots = FindRoots(DT, BUI);
-    for (const NodePtr R : DT.Roots) {
-      const TreeNodePtr TN = DT.getNode(R);
-      // A CFG node was selected as a tree root, but the corresponding tree node
-      // is not connected to the virtual root. This is because the incremental
-      // algorithm does not really know or use the set of roots and can make a
-      // different (implicit) decision about which nodes within an infinite loop
-      // becomes a root.
-      if (TN && !DT.isVirtualRoot(TN->getIDom())) {
-        DEBUG(dbgs() << "Root " << BlockNamePrinter(R)
-                     << " is not virtual root's child\n"
-                     << "The entire tree needs to be rebuilt\n");
-        // It should be possible to rotate the subtree instead of recalculating
-        // the whole tree, but this situation happens extremely rarely in
-        // practice.
-        CalculateFromScratch(DT, BUI);
-        return;
-      }
-    }
-  }
+    auto Roots = FindRoots(DT, BUI);
+    if (DT.Roots.size() != Roots.size() ||
+        !std::is_permutation(DT.Roots.begin(), DT.Roots.end(), Roots.begin())) {
+      // The roots chosen in the CFG have changed. This is because the
+      // incremental algorithm does not really know or use the set of roots and
+      // can make a different (implicit) decision about which node within an
+      // infinite loop becomes a root.
+
+      DEBUG(dbgs() << "Roots are different in updated trees\n"
+      // It may be possible to update the tree without recalculating it, but
+      // we do not know yet how to do it, and it happens rarely in practise.
 
   // Handles insertion to a node already in the dominator tree.
   static void InsertReachable(DomTreeT &DT, const BatchUpdatePtr BUI,
                               const TreeNodePtr From, const TreeNodePtr To) {
     DEBUG(dbgs() << "\tReachable " << BlockNamePrinter(From->getBlock())
                  << " -> " << BlockNamePrinter(To->getBlock()) << "\n");
     if (IsPostDom && UpdateRootsBeforeInsertion(DT, BUI, From, To)) return;
     // DT.findNCD expects both pointers to be valid. When From is a virtual
bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL) {
 
   switch (VL) {
   case DomTreeT::VerificationLevel::Fast:
     return SNCA.IsSameAsFreshTree(DT);
 
   case DomTreeT::VerificationLevel::Basic:
     return SNCA.verifyParentProperty(DT) && SNCA.IsSameAsFreshTree(DT);
 
-  case DomTreeT::VerificationLevel::Full:
-    return SNCA.verifyParentProperty(DT) && SNCA.verifySiblingProperty(DT);
+  case DomTreeT::VerificationLevel::Full: {
+    bool FullRes
+        = SNCA.verifyParentProperty(DT) && SNCA.verifySiblingProperty(DT);
+
+    // Postdominators depend on root selection, make sure that a fresh tree
+    // looks the same.
+    if (DT.isPostDominator())
+      FullRes &= SNCA.IsSameAsFreshTree(DT);
+
+    return FullRes;
+  }
   }
 
   llvm_unreachable("Unhandled DomTree VerificationLevel");
 }
 
 }  // namespace DomTreeBuilder
 }  // namespace llvm
 
 #undef DEBUG_TYPE
 
 #endif