[LoopSimplifyCFG] Suppress expensive DomTree verification in LoopSimplifyCFG

[yrouban]

Summary

This patch makes verification level lower for builds with inexpensive checks.

[dmgreen]

Hello. I think it's fine to always use DominatorTree::VerificationLevel::Fast, the others are more about checking that the DomTree construction code was correct. Fast will compare against a new tree, so for updates will check the the tree is correct.

[yrouban]

In D61055#1481627, @dmgreen wrote:

Hello. I think it's fine to always use DominatorTree::VerificationLevel::Fast, the others are more about checking that the DomTree construction code was correct. Fast will compare against a new tree, so for updates will check the the tree is correct.

may be we have to set Fast by default instead of Full?

bool DominatorTreeBase<>::verify(VerificationLevel VL = VerificationLevel::Full) const {

[dmgreen]

Yeah, sounds like a good idea to me. I almost sugested the same thing. There are a load of tests that should still be using Full (i.e. the domtree construction still needs to be checked with basic/full).

@kuhar what do you think?

[kuhar]

In D61055#1481740, @yrouban wrote:

In D61055#1481627, @dmgreen wrote:

Hello. I think it's fine to always use DominatorTree::VerificationLevel::Fast, the others are more about checking that the DomTree construction code was correct. Fast will compare against a new tree, so for updates will check the the tree is correct.

may be we have to set Fast by default instead of Full?

bool DominatorTreeBase<>::verify(VerificationLevel VL = VerificationLevel::Full) const {

In D61055#1481754, @dmgreen wrote:

Yeah, sounds like a good idea to me. I almost sugested the same thing. There are a load of tests that should still be using Full (i.e. the domtree construction still needs to be checked with basic/full).

@kuhar what do you think?

It's not entirely true that the Basic/Full level is only ensuring DT construction/updates are correct. The big downside of the Fast mode is that it assumes not only that construction is correct, but also uses custom logic to traverse CFG. We hit an issue with these assumptions recently with a change to Clang CFG that caused it to return nullptrs from children(node), which broke domtree construction.

That being said, I don't think that people should asserting correctness of domtree within transforms, unless there's a strong need. This is generally not cheap, even at the Fast level, and because of that I think that if someone really wants to have a fast domtree verification in an assertion, they should make it explicit. Historically, Fast had been the default, and the running time penalty started to pile up, as many places assumed it's very cheap to perform. It's much easier to realize these assertions are fishy if they are not usually-cheap-but-not-quite by default.

[dmgreen]

That being said, I don't think that people should asserting correctness of domtree within transforms, unless there's a strong need. This is generally not cheap, even at the Fast level, and because of that I think that if someone really wants to have a fast domtree verification in an assertion, they should make it explicit. Historically, Fast had been the default, and the running time penalty started to pile up, as many places assumed it's very cheap to perform. It's much easier to realize these assertions are fishy if they are not usually-cheap-but-not-quite by default.

My understanding of the problem is that many people (who quite possibly do not know the ins and outs of dominators) update passes to preserve the domtree. They need to verify that what they have done is correct, so they add an assert(DT.verify()); This is a good thing and it catches problems that are often easy to make with DT updating, like missing edge inserts/removals. They often don't realise that the default is very heavy-weight though, and expect it to work more like LI->verify or isRecursivelyLCSSAForm.

So the argument for fast being the default would be that the users who don't necessarily know better get a good default option. And the people who do know better can use Basic/Full.

But I was not aware that Fast used to be the default, and was still quite slow. I was under the impression that the problems in the past were to do with it using Full under expensive checks, and that Fast was fairly quick (quick enough for an asserts build).

[kuhar]

In D61055#1481841, @dmgreen wrote:

But I was not aware that Fast used to be the default, and was still quite slow. I was under the impression that the problems in the past were to do with it using Full under expensive checks, and that Fast was fairly quick (quick enough for an asserts build).

It of course depends on exactly location, but we found that Fast is generally not quick enough to be run during a typical loop pass (on large files, or loopy code from non-clang frontends). I claim that it's better to make it obvious that these checks are slow, and make developers either guard them with EXEPNSIVE_CHECKS or opt-in with Fast.

[yrouban]

In D61055#1481863, @kuhar wrote:

It of course depends on exactly location, but we found that Fast is generally not quick enough to be run during a typical loop pass (on large files, or loopy code from non-clang frontends). I claim that it's better to make it obvious that these checks are slow, and make developers either guard them with EXEPNSIVE_CHECKS or opt-in with Fast.

Does it mean that you lgtm if I will remove the else part of the change (lines 604-606).

[kuhar]

Yes, I think expensive checks are sufficient. If you think there's a strong need to assert in debug builds, maybe try the Fast level for now and remove it after a few weeks, once you gain confidence in the code or someone complains the check is too slow?

[dmgreen]

I claim that it's better to make it obvious that these checks are slow, and make developers either guard them with EXPENSIVE_CHECKS or opt-in with Fast.

Do you mean removing the default entirely? To makes it explicit.

Whatever we do in the long run needn't be done here, and making this Fast and behind expensive checks is a definite improvement. (I think Full is still more expensive than necessary, even for an expensive checks build).

[yrouban]

changed verification level from Basic to Fast.

[kuhar]

In D61055#1481983, @dmgreen wrote:

I claim that it's better to make it obvious that these checks are slow, and make developers either guard them with EXPENSIVE_CHECKS or opt-in with Fast.

Do you mean removing the default entirely? To makes it explicit.

Whatever we do in the long run needn't be done here, and making this Fast and behind expensive checks is a definite improvement. (I think Full is still more expensive than necessary, even for an expensive checks build).

I'm fairly happy with the current slow and thorough as default and fast as opt-in, but can be convinced to switch something else, if there's a better compromise.

llvm/lib/Transforms/Scalar/LoopSimplifyCFG.cpp

if (!DeadLoopBlocks.empty()) {
       DTUpdates.clear();
     }
 
     if (MSSAU && VerifyMemorySSA)
       MSSAU->getMemorySSA()->verifyMemorySSA();
 
 #ifndef NDEBUG
     // Make sure that we have preserved all data structures after the transform.
-    assert(DT.verify() && "DT broken after transform!");
+#if defined(EXPENSIVE_CHECKS)
+    assert(DT.verify(DominatorTree::VerificationLevel::Full) &&
+           "DT broken after transform!");
+#else
+    assert(DT.verify(DominatorTree::VerificationLevel::Basic) &&
+           "DT broken after transform!");
+#endif
     assert(DT.isReachableFromEntry(Header));
     LI.verify(DT);
 #endif
 
     return true;
   }
 
   bool foldingBreaksCurrentLoop() const {