diff --git a/llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp b/llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
--- a/llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
@@ -1838,13 +1838,15 @@
 
 template<class SF>
 static SUnit *popFromQueueImpl(std::vector<SUnit *> &Q, SF &Picker) {
-  std::vector<SUnit *>::iterator Best = Q.begin();
-  for (auto I = std::next(Q.begin()), E = Q.end(); I != E; ++I)
-    if (Picker(*Best, *I))
-      Best = I;
-  SUnit *V = *Best;
-  if (Best != std::prev(Q.end()))
-    std::swap(*Best, Q.back());
+  unsigned BestIdx = 0;
+  // Only compute the cost for the first 1000 items in the queue, to avoid
+  // excessive compile-times for very large queues.
+  for (unsigned I = 1, E = std::min(Q.size(), 1000ul); I != E; I++)
+    if (Picker(Q[BestIdx], Q[I]))
+      BestIdx = I;
+  SUnit *V = Q[BestIdx];
+  if (BestIdx + 1 != Q.size())
+    std::swap(Q[BestIdx], Q.back());
   Q.pop_back();
   return V;
 }
diff --git a/llvm/test/CodeGen/X86/stress-scheduledagrrlist.ll b/llvm/test/CodeGen/X86/stress-scheduledagrrlist.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/CodeGen/X86/stress-scheduledagrrlist.ll
@@ -0,0 +1,12 @@
+; RUN: llc -O0 -mtriple=x86_64-apple-macosx %s -o %t.s
+
+; Stress test for the list scheduler. The store will be expanded to a very
+; large number of stores during isel, stressing ScheduleDAGRRList. It should
+; compiles in a reasonable amount of time. Run with -O0, to disable most other
+; optimizations.
+
+define void @test(i1000000* %ptr) {
+entry:
+  store i1000000 0, i1000000* %ptr, align 4
+  ret void
+}