Index: include/llvm/IR/Dominators.h
===================================================================
--- include/llvm/IR/Dominators.h
+++ include/llvm/IR/Dominators.h
@@ -66,6 +66,7 @@
     return End;
   }
 
+  /// Check if this is the only edge between Start and End.
   bool isSingleEdge() const;
 };
 
Index: lib/IR/Dominators.cpp
===================================================================
--- lib/IR/Dominators.cpp
+++ lib/IR/Dominators.cpp
@@ -120,6 +120,21 @@
   return &*I == Def;
 }
 
+/// \brief A cheaper version of linear BasicBlockEdge::isSingleEdge that may
+/// report a single edge for a SwitchInst even though there are actually
+/// multiple edges.
+static bool maybeSingleEdge(const BasicBlockEdge &BBE) {
+#ifdef EXPENSIVE_CHECKS
+  bool CheckSingleEdge = true;
+#else
+  // This removes a noticeable quadratic behavior with asserts enabled when GVN
+  // propagates equality for a switch statement with a large number of cases.
+  bool CheckSingleEdge =
+      BBE.getStart()->getTerminator()->getNumSuccessors() < 50;
+#endif
+  return !CheckSingleEdge || BBE.isSingleEdge();
+}
+
 // true if Def would dominate a use in any instruction in UseBB.
 // note that dominates(Def, Def->getParent()) is false.
 bool DominatorTree::dominates(const Instruction *Def,
@@ -153,7 +168,7 @@
   // Assert that we have a single edge. We could handle them by simply
   // returning false, but since isSingleEdge is linear on the number of
   // edges, the callers can normally handle them more efficiently.
-  assert(BBE.isSingleEdge() &&
+  assert(maybeSingleEdge(BBE) &&
          "This function is not efficient in handling multiple edges");
 
   // If the BB the edge ends in doesn't dominate the use BB, then the
@@ -204,7 +219,7 @@
   // Assert that we have a single edge. We could handle them by simply
   // returning false, but since isSingleEdge is linear on the number of
   // edges, the callers can normally handle them more efficiently.
-  assert(BBE.isSingleEdge() &&
+  assert(maybeSingleEdge(BBE) &&
          "This function is not efficient in handling multiple edges");
 
   Instruction *UserInst = cast<Instruction>(U.getUser());