[Verifier] enable and limit llvm.experimental.noalias.scope.decl dominance checking

[jeroen.dobbelaere]

Summary

Checking the llvm.experimental.noalias.scope.decl dominance can be worstcase O(N^2).
Limit the dominance check to N=32.

[jeroen.dobbelaere]

For what it's worth, the number '1000' comes from experiments triggering the worst case behavior. With 1000 basic blocks and scope declarations, the time for parsing and checking on my testmachine was roughly 0.1 seconds. (Going to approx 1 second for 4000 blocks and declarations).

[jeroen.dobbelaere]

For a stage2 release build and the test-suite, the largest amount of noalias scope decls for a function is 1075 (triggered by llvm/unittests/ADT/SmallVectorTest.cpp). Everything else is <1000. The largest amount of same scope declarations seen was 5.

[nikic]

llvm/lib/IR/Verifier.cpp

5588

I wouldn't bother with the EXPENSIVE_CHECKS part and add a hardcoded limit of ItNext - ItCurrent < 32 or so here (only the case where there are many declares for the same scope is problematic).

It would be better to instead sort by DomTree DFS In number here and thus avoid a quadratic number of checks, but I don't think it's really worthwhile (the concern is a purely theoretical one).

[fhahn]

llvm/lib/IR/Verifier.cpp

5588

I wouldn't bother with the EXPENSIVE_CHECKS part and add a hardcoded limit of ItNext - ItCurrent < 32 or so here (only the case where there are many declares for the same scope is problematic).

SGTM

It would be better to instead sort by DomTree DFS In number here and thus avoid a quadratic number of checks, but I don't think it's really worthwhile (the concern is a purely theoretical one).

I was thinking about suggesting this was well, but it's probably more trouble than it is worth.

[jeroen.dobbelaere]

Adapted to comments.

[fhahn]

LGTM, thanks!

[jeroen.dobbelaere]

I disabled the dominance check by default in rG3b5d36ece21f. Several buildbots show examples where this triggers, indicating there are still passes not taking care of proper handling the noalias scopes.

See:

• http://lab.llvm.org:8011/#/builders/98/builds/4105/steps/9/logs/stdio
• http://lab.llvm.org:8011/#/builders/74/builds/2331/steps/8/logs/stdio

[jeroen.dobbelaere]

There seems to be a problem with bad duplication in the MemorySanitizerLegacyPass.

[jeroen.dobbelaere]

In D95335#2522370, @jeroen.dobbelaere wrote:

There seems to be a problem with bad duplication in the MemorySanitizerLegacyPass.

After having reduced at least one issue, the problem originates from LoopPeel.cpp not taking care of the scopes after cloning.
I'll create a fix + testcase.

@jdoerfert I also noticed that LoopPeel.cpp is not doing anything for assumptions.

llvm/lib/IR/Verifier.cpp

 #include <cstdint>
 #include <memory>
 #include <string>
 #include <utility>
 
 using namespace llvm;
 
 static cl::opt<bool> VerifyNoAliasScopeDomination(
-    "verify-noalias-scope-decl-dom", cl::Hidden, cl::init(false),
+    "verify-noalias-scope-decl-dom", cl::Hidden, cl::init(true),
     cl::desc("Ensure that llvm.experimental.noalias.scope.decl for identical "
              "scopes are not dominating"));
 
 namespace llvm {
 
 struct VerifierSupport {
   raw_ostream *OS;
   const Module &M;
void Verifier::verifyNoAliasScopeDecl() {
   // dominating each other.
   auto ItCurrent = NoAliasScopeDecls.begin();
   while (ItCurrent != NoAliasScopeDecls.end()) {
     auto CurScope = GetScope(*ItCurrent);
     auto ItNext = ItCurrent;
     do {
       ++ItNext;
     } while (ItNext != NoAliasScopeDecls.end() &&
              GetScope(*ItNext) == CurScope);
 
-    // [ItCurrent, ItNext[ represents the declarations for the same scope.
-    // Ensure they are not dominating each other
-    for (auto *I : llvm::make_range(ItCurrent, ItNext)) {
-      for (auto *J : llvm::make_range(ItCurrent, ItNext)) {
-        if (I != J) {
+    // [ItCurrent, ItNext) represents the declarations for the same scope.
+    // Ensure they are not dominating each other.. but only if it is not too
+    // expensive.
+    if (ItNext - ItCurrent < 32)
+      for (auto *I : llvm::make_range(ItCurrent, ItNext))
+        for (auto *J : llvm::make_range(ItCurrent, ItNext))
+          if (I != J)
             Assert(!DT.dominates(I, J),
                    "llvm.experimental.noalias.scope.decl dominates another one "
                    "with the same scope",
                    I);
-        }
-      }
-    }
     ItCurrent = ItNext;
   }
 }
 
 //===----------------------------------------------------------------------===//
 //  Implement the public interfaces to this file...
 //===----------------------------------------------------------------------===//