[Dominators] Remove verifyDomTree and add some verifying for Post Dom Trees
ClosedPublic

Authored by dmgreen on Dec 15 2017, 9:22 AM.

Details

Summary

Removes verifyDomTree, using assert(verify()) everywhere instead. Also changes verify a little to always run IsSameAsFreshTree first, in order to print good output when we find errors. Then add verifyAnalysis for PostDomTrees. This will allow checking of PostDomTrees it the same way we check DomTrees and MachineDomTrees.

Diff Detail

Repository
rL LLVM
dmgreen created this revision.Dec 15 2017, 9:22 AM
davide added a subscriber: davide.Dec 15 2017, 11:12 AM

should this be guarded by another flag temporarily?

Thanks!

Davide

lib/Analysis/PostDominators.cpp
42 ↗(On Diff #127141)

verifyPostDomTree?

45 ↗(On Diff #127141)

PostDomTree verification failed?

dmgreen updated this revision to Diff 130639.Jan 19 2018, 9:50 AM
dmgreen marked an inline comment as done.
dmgreen added a subscriber: kuhar.

Hello. Sorry for the delay.

I have left this as verifyDomTree and using VerifyDomInfo to keep things consistent between the two dom trees. I can change this if you think it is best, but personally like the idea of treating the two trees similarly. Let me know what you think.

My impression was that DT.verifyDomTree() was mostly there for legacy reasons, as it doesn't verify that the tree is correct or that it's even constructed correctly. It has historically been quite cheap, so some passes thought they can use it in asserts, and because of this we cannot replace it with DT.verify(), as it can blow up in pathological cases (O(N^3)).

I am more and more convinced that verifyDomTree() should be replaced altogether with two or three checks:

  • full verification as it is today in .verify(), used when -verify-dom-info is passes.
  • partial verification: reachability, roots, parent property, dfs numbers, and comparison with a freshly build tree. This would be O(N^2), just like verifyDomTree() now, but probably a bit slower in practise. This would be used with EXPENSIVE_CHECKS and in verifyAnalysis.
  • 'light' version: reachability, roots, dfs numbers, and comparison with a freshly build tree. This would be used with asserts in passes, instead of verifyDomTree(). This is should take about the same time ass the current implementation.

If we moved forward in this direction, all what DomTree and PostDomTree would have to implement would be essentially:

PostDominatorTree::verifyDomTree() const { assert(verify(CheckLevel::Light)); }
kuhar added a reviewer: kuhar.Jan 20 2018, 1:12 PM
kuhar added a comment.Jan 20 2018, 4:14 PM

I went ahead and made a patch for having different levels of verification: D42337

Nice. Like it. I'll rebase this on that, once it's in.

kuhar added a comment.Jan 23 2018, 6:43 PM

The verification levels are landed as of r323298.

kuhar added inline comments.Jan 24 2018, 6:30 AM
include/llvm/Analysis/PostDominators.h
40 ↗(On Diff #131248)

I don't think it's a good idea to expose it externally. For debugging, you can just do assert(PDT.verify()).
The problem I see is that people will call it not realizing that it doesn't perform full verification and does not check each property individually, resulting in worse errors than plain PDT.verify().

I think we should just keep it internal and only use in verifyAnalysis, or just inline it there.

include/llvm/IR/Dominators.h
180 ↗(On Diff #131248)

Here, I think we should change the docs to say that this is a legacy debugging function, and point users to DT.verify instead. When we first introduced the new verifiers, I completely replaced verifyDomTree with verify, but then realized that people use it in regular passes in debug builds and expect it to be fast.

With the new verification levels, I think it would be better to either completely replace all uses with DT.verify(Fast), or just keep it as a wrapper around .verify() that only prints CFG upon failure and asserts.
(This doesn't mean it propose to do all of it in one patch.)

dmgreen added inline comments.Jan 24 2018, 11:20 AM
include/llvm/Analysis/PostDominators.h
40 ↗(On Diff #131248)

Interesting. I think there is value in keeping dom/postdom trees equivalent, whatever we end up doing.

My understanding is that there are two different usecases for checking the dom tree. There's the case for people like yourself who are writing the domtree construction code. This need good quality checks that are hard to do, and that check various properties of the tree are correct.

Then there's guys who are just trying to use the domtree updater to preserve the tree across passes. Here you can almost always presume that a newly calculated tree is correct. In my experience, the best error message says "The tree should look like -this-, but you made it look like -this!-". Messages like "node %x is not reachable when it's sibling %y is removed", whilst I can see the value in being more succinct (and better tests of the tree), they are often not as useful as being able to eyeball the difference between two trees and notice that y is in the wrong place.

So this may just be a difference in what we use these for. And may just be my two cents :) I found the error messages coming out of verifyDomTree often quite useful. That said, I have not used it it any code anywhere, just whilst debugging. And like you say, perhaps assert(DT.verify(Fast)) is a better option for this (the CFG output can be a bit noisy :) )

So having said all that.. (comment below)

include/llvm/IR/Dominators.h
180 ↗(On Diff #131248)

Yeah, I think this sounds best. Removing verifyDomTree entirely and just using verify everywhere we need it. I can probably do that pretty quickly, it's just a fairly mechanical change of replacing one function call with another.

kuhar added inline comments.Jan 24 2018, 1:21 PM
include/llvm/Analysis/PostDominators.h
40 ↗(On Diff #131248)

So instead, we could just add a fresh domtree printing upon error to verify(). I mean, this is what people usually do manually when they debug these things. The current error messages coming from verify() are usually quite concise, so I think it makes sense to just make it print a freshly constructed tree below in addition to that.

dmgreen updated this revision to Diff 131605.Jan 26 2018, 10:06 AM
dmgreen retitled this revision from [PDT] Add verifyDomTree and verifyAnalysis for Post Dom Trees to [Dominators] Remove verifyDomTree add some verifing for Post Dom Trees.
dmgreen edited the summary of this revision. (Show Details)

Updates. What do you think?

This exposes a bug in the DominatorTree.InsertReachable2 test that we need to sort. We may need something like this, I'm not 100%:

diff --git a/include/llvm/Support/GenericDomTreeConstruction.h b/include/llvm/Support/GenericDomTreeConstruction.h
index 172efb5..53387db 100644
--- a/include/llvm/Support/GenericDomTreeConstruction.h
+++ b/include/llvm/Support/GenericDomTreeConstruction.h
@@ -697,25 +697,22 @@ struct SemiNCAInfo {
         }))
       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
+    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 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;
-      }
+      DEBUG(dbgs() << "Roots are different in updated trees\n"
+                   << "The entire tree needs to be rebuilt\n");
+      // It may be possible to rotate the subtree instead of recalculating
+      // the whole tree, but this situation happens extremely rarely in
+      // practice.
+      CalculateFromScratch(DT, BUI);
     }
   }
dmgreen retitled this revision from [Dominators] Remove verifyDomTree add some verifing for Post Dom Trees to [Dominators] Remove verifyDomTree and add some verifying for Post Dom Trees.Jan 26 2018, 10:08 AM
kuhar added a comment.Feb 2 2018, 9:39 AM

This is blocked by the incorrect postdominators roots after insertion bug you discovered, right?

Hello

Sorry, other stuff has been keeping me busy :) From what I understand, both the old and the new code was wrong for when we force a recalc of the postdomtree, based on when the roots change.

This InsertReachable2 test, if I remember correctly, has three roots before the update:
"6" - a normal exit/no successor node
"9" - an infinite loop
"2" - the common descendant of both.
After the insert, the infinite loop becomes (reverse-)reachable from 6, so the 9 and 2 nodes are no longer roots. But the tree was updated with the implicit assumption that they were connected to the virtual root, so the tree is wrong and needs a recalc.

We update the roots to just "6", check that it has a virtual base (it does) so decide not to recalc. The old code would check and do the recalc if it _did_ have a virtual root. I don't think that's what was intended - correct me if I'm wrong. Changing that fixed cases where the tree only had infinite loops as roots, and the root gets changed during the update.

So I think we may need to do the recalc "if the roots have changed". Or scan though the nodes in the tree and recalc if there is a node that has a virtual base, but is not a root. Not 100% sure. My cryptic code in the comment above was a suggestion for the "recalc if the roots have changed" option.

kuhar added a comment.Feb 9 2018, 1:24 PM

Hi @dmgreen,

Sorry it took me a while, but I looked at what at the problem with InstertReachable2 and I wasn't able to figure out any other way to end up with correct postdomtree other than recalculating it. I went ahead and used your patch to create a separate revision and put it here: D43140.

kuhar added a comment.Feb 12 2018, 4:34 PM

This should be unblocked now.

dmgreen updated this revision to Diff 134874.Feb 19 2018, 2:56 AM
dmgreen edited the summary of this revision. (Show Details)

Rebase and a couple of minor edits.

dmgreen added inline comments.Feb 19 2018, 2:58 AM
include/llvm/Support/GenericDomTree.h
322 ↗(On Diff #134874)

Can you check this is correct. This function, unusually, returns false on same, true on different.

kuhar added inline comments.Feb 19 2018, 4:40 AM
include/llvm/Support/GenericDomTree.h
322 ↗(On Diff #134874)

Good catch! Feel free to fix it -- I think you can change this and the next one in a separate commit without review.

dmgreen added inline comments.Feb 19 2018, 8:40 AM
include/llvm/Support/GenericDomTree.h
322 ↗(On Diff #134874)

Thanks. I'll count that as a review :) https://reviews.llvm.org/rL325517

kuhar accepted this revision.Feb 22 2018, 10:49 AM

LGTM

This revision is now accepted and ready to land.Feb 22 2018, 10:49 AM
brzycki accepted this revision.Feb 26 2018, 8:04 AM

+1 LGTM as well.

dmgreen updated this revision to Diff 136061.Feb 27 2018, 5:11 AM

Updated with one last fix for release tests. DominatorTreeVerifierPass::run now requests a DomTree, even if asserts are disabled.

This revision was automatically updated to reflect the committed changes.