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
@@ -54,6 +54,7 @@
 #include <iterator>
 #include <limits>
 #include <memory>
+#include <queue>
 #include <utility>
 #include <vector>
 
@@ -1817,29 +1818,42 @@
   void CalculateSethiUllmanNumbers();
 };
 
-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());
+template <class SF>
+static SUnit *popFromQueueImpl(std::vector<SUnit *> &Q, SF &Picker,
+                               bool &IsHeap) {
+  if (!IsHeap && Q.size() > 100) {
+    std::make_heap(Q.begin(), Q.end(), Picker);
+    IsHeap = true;
+  }
+
+  SUnit *V = nullptr;
+  if (IsHeap) {
+    std::pop_heap(Q.begin(), Q.end(), Picker);
+    V = Q.back();
+  } else {
+    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;
+    V = *Best;
+    if (Best != std::prev(Q.end()))
+      std::swap(*Best, Q.back());
+  }
   Q.pop_back();
   return V;
 }
 
-template<class SF>
-SUnit *popFromQueue(std::vector<SUnit *> &Q, SF &Picker, ScheduleDAG *DAG) {
+template <class SF>
+SUnit *popFromQueue(std::vector<SUnit *> &Q, SF &Picker, ScheduleDAG *DAG,
+                    bool &IsHeap) {
 #ifndef NDEBUG
   if (DAG->StressSched) {
     reverse_sort<SF> RPicker(Picker);
-    return popFromQueueImpl(Q, RPicker);
+    return popFromQueueImpl(Q, RPicker, IsHeap);
   }
 #endif
   (void)DAG;
-  return popFromQueueImpl(Q, Picker);
+  return popFromQueueImpl(Q, Picker, IsHeap);
 }
 
 //===----------------------------------------------------------------------===//
@@ -1855,6 +1869,7 @@
 
   unsigned CurQueueId = 0;
   std::vector<SUnit *> Queue;
+  bool IsHeap = false;
 
 public:
   RegReductionPriorityQueue(MachineFunction &mf,
@@ -1876,7 +1891,7 @@
   SUnit *pop() override {
     if (Queue.empty()) return nullptr;
 
-    SUnit *V = popFromQueue(Queue, Picker, scheduleDAG);
+    SUnit *V = popFromQueue(Queue, Picker, scheduleDAG, IsHeap);
     V->NodeQueueId = 0;
     return V;
   }
@@ -1885,6 +1900,8 @@
     assert(!U->NodeQueueId && "Node in the queue already");
     U->NodeQueueId = ++CurQueueId;
     Queue.push_back(U);
+    if (IsHeap)
+      std::push_heap(Queue.begin(), Queue.end(), Picker);
   }
 
   void remove(SUnit *SU) override {
@@ -1895,6 +1912,7 @@
       std::swap(*I, Queue.back());
     Queue.pop_back();
     SU->NodeQueueId = 0;
+    IsHeap = false;
   }
 
   bool empty() const override { return Queue.empty(); }
@@ -1905,7 +1923,8 @@
     std::vector<SUnit *> DumpQueue = Queue;
     SF DumpPicker = Picker;
     while (!DumpQueue.empty()) {
-      SUnit *SU = popFromQueue(DumpQueue, DumpPicker, scheduleDAG);
+      bool IsHeap = IsHeap;
+      SUnit *SU = popFromQueue(DumpQueue, DumpPicker, scheduleDAG, IsHeap);
       dbgs() << "Height " << SU->getHeight() << ": ";
       DAG->dumpNode(*SU);
     }