Index: include/llvm/CodeGen/SelectionDAGNodes.h
===================================================================
--- include/llvm/CodeGen/SelectionDAGNodes.h
+++ include/llvm/CodeGen/SelectionDAGNodes.h
@@ -797,6 +797,31 @@
   /// NOTE: This is an expensive method. Use it carefully.
   bool hasPredecessor(const SDNode *N) const;
 
+  /// Return a value to use in the MaxSteps of hasPredecessorHelper
+  /// This value helps to enforce the assumption that SmallPtrSet is small
+  /// When SmallPtrSet is large, rehashing Visited is the performace
+  /// bottleneck of the compiler.
+  static unsigned int hasPredecessorHelperMaxSteps(unsigned int OptimizationLevel = 2) {
+    //
+    // From reviewing the final Visited size while building llvm+clang,
+    // the mean was 12.45 and the standard deviation was 11.73.
+    // For SmallPtrSet, SmallSize max is 32.
+    unsigned int ret = 32;
+    // The maximum MaxSteps currently in use is 8192
+    // Do not go higher.
+    unsigned int max = 8192;
+    if (OptimizationLevel > 9) {
+      ret = max;
+    } else {
+      ret <<= OptimizationLevel;
+    }
+    // SmallPtrSet rehashes on powers of two.
+    // Reduce the MaxSteps by a bit to stop the last rehash.
+    unsigned int abit = 4;
+    ret -= abit;
+    return ret;
+  }
+
   /// Returns true if N is a predecessor of any node in Worklist. This
   /// helper keeps Visited and Worklist sets externally to allow unions
   /// searches to be performed in parallel, caching of results across
Index: lib/CodeGen/SelectionDAG/DAGCombiner.cpp
===================================================================
--- lib/CodeGen/SelectionDAG/DAGCombiner.cpp
+++ lib/CodeGen/SelectionDAG/DAGCombiner.cpp
@@ -13251,7 +13251,6 @@
 
   SmallPtrSet<const SDNode *, 16> Visited;
   SmallVector<const SDNode *, 8> Worklist;
-  unsigned int Max = 8192;
   // Search Ops of store candidates.
   for (unsigned i = 0; i < NumStores; ++i) {
     SDNode *n = StoreNodes[i].MemNode;
@@ -13262,7 +13261,7 @@
   // Search through DAG. We can stop early if we find a store node.
   for (unsigned i = 0; i < NumStores; ++i)
     if (SDNode::hasPredecessorHelper(StoreNodes[i].MemNode, Visited, Worklist,
-                                     Max))
+                                     SDNode::hasPredecessorHelperMaxSteps()))
       return false;
   return true;
 }