Index: llvm/lib/IR/Verifier.cpp
===================================================================
--- llvm/lib/IR/Verifier.cpp
+++ llvm/lib/IR/Verifier.cpp
@@ -116,10 +116,23 @@
 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"));
 
+#ifdef EXPENSIVE_CHECKS
+#define VNASD_LIMIT 0
+#define VNASD_LIMIT_S "0"
+#else
+#define VNASD_LIMIT 1000
+#define VNASD_LIMIT_S "1000"
+#endif
+static cl::opt<unsigned> VerifyNoAliasScopeDominationLimit(
+    "verify-noalias-scope-decl-dom-limit", cl::Hidden, cl::init(VNASD_LIMIT),
+    cl::desc("Check the dominance relation only if there are at most N "
+             "llvm.experimental.noalias.scope.decl in the function. "
+             "(0 = always, default=" VNASD_LIMIT_S ")"));
+
 namespace llvm {
 
 struct VerifierSupport {
@@ -5560,6 +5573,11 @@
   if (!VerifyNoAliasScopeDomination)
     return;
 
+  // Avoid the worstcase O(N^2) behavior for large amounts of decls.
+  if (VerifyNoAliasScopeDominationLimit &&
+      NoAliasScopeDecls.size() > VerifyNoAliasScopeDominationLimit)
+    return;
+
   // Now sort the intrinsics based on the scope MDNode so that declarations of
   // the same scopes are next to each other.
   auto GetScope = [](IntrinsicInst *II) {
Index: llvm/test/Verifier/noalias_scope_decl.ll
===================================================================
--- llvm/test/Verifier/noalias_scope_decl.ll
+++ llvm/test/Verifier/noalias_scope_decl.ll
@@ -1,4 +1,7 @@
-; RUN: not llvm-as -disable-output --verify-noalias-scope-decl-dom < %s 2>&1 | FileCheck %s
+; RUN: not llvm-as -disable-output --verify-noalias-scope-decl-dom < %s 2>&1 | FileCheck %s --check-prefixes=CHECK,DOM
+; RUN: not llvm-as -disable-output --verify-noalias-scope-decl-dom --verify-noalias-scope-decl-dom-limit=100 < %s 2>&1 | FileCheck %s --check-prefixes=CHECK,DOM
+; RUN: not llvm-as -disable-output --verify-noalias-scope-decl-dom --verify-noalias-scope-decl-dom-limit=0 < %s 2>&1 | FileCheck %s --check-prefixes=CHECK,DOM
+; RUN: not llvm-as -disable-output --verify-noalias-scope-decl-dom --verify-noalias-scope-decl-dom-limit=1 < %s 2>&1 | FileCheck %s
 
 define void @test_single_scope01() nounwind ssp {
   tail call void @llvm.experimental.noalias.scope.decl(metadata !2)
@@ -30,16 +33,16 @@
   tail call void @llvm.experimental.noalias.scope.decl(metadata !6)
   ret void
 }
-; CHECK-NEXT: llvm.experimental.noalias.scope.decl dominates another one with the same scope
-; CHECK-NEXT:   tail call void @llvm.experimental.noalias.scope.decl(metadata !2)
+; DOM-NEXT: llvm.experimental.noalias.scope.decl dominates another one with the same scope
+; DOM-NEXT:   tail call void @llvm.experimental.noalias.scope.decl(metadata !2)
 
 define void @test_dom03() nounwind ssp {
   tail call void @llvm.experimental.noalias.scope.decl(metadata !2)
   tail call void @llvm.experimental.noalias.scope.decl(metadata !2)
   ret void
 }
-; CHECK-NEXT: llvm.experimental.noalias.scope.decl dominates another one with the same scope
-; CHECK-NEXT:   tail call void @llvm.experimental.noalias.scope.decl(metadata !2)
+; DOM-NEXT: llvm.experimental.noalias.scope.decl dominates another one with the same scope
+; DOM-NEXT:   tail call void @llvm.experimental.noalias.scope.decl(metadata !2)
 
 ; CHECK-NOT: llvm.experimental.noalias.scope.decl