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,8 +1818,9 @@
   void CalculateSethiUllmanNumbers();
 };
 
-template<class SF>
-static SUnit *popFromQueueImpl(std::vector<SUnit *> &Q, SF &Picker) {
+template <class SF>
+static SUnit *popFromQueueImpl(std::vector<SUnit *> &Q, SF &Picker,
+                               bool &IsHeap) {
   std::vector<SUnit *>::iterator Best = Q.begin();
   for (auto I = std::next(Q.begin()), E = Q.end(); I != E; ++I)
     if (Picker(*Best, *I))
@@ -1830,16 +1832,56 @@
   return V;
 }
 
-template<class SF>
-SUnit *popFromQueue(std::vector<SUnit *> &Q, SF &Picker, ScheduleDAG *DAG) {
+template <class SF>
+static void assertIsHeap(std::vector<SUnit *> &Q, SF &Picker) {
+#ifdef EXPENSIVE_CHECKS
+  // Verify that Q is a valid heap.
+  std::vector<SUnit *> Copy(Q.begin(), Q.end());
+  std::make_heap(Copy.begin(), Copy.end(), Picker);
+  for (unsigned i = 0; i < Copy.size(); i++)
+    assert(Copy[i] == Q[i]);
+#endif
+}
+
+// Specialization for src_ls_rr_sort that uses a heap to maintain the queue for
+// faster accesses. This is limited to src_ls_rr_sort because other comperators
+// may change the score after a node is removed from the queue.
+static SUnit *popFromQueueImpl(std::vector<SUnit *> &Q, src_ls_rr_sort &Picker,
+                               bool &IsHeap) {
+  if (!IsHeap) {
+    std::make_heap(Q.begin(), Q.end(), Picker);
+    IsHeap = true;
+  }
+
+  assertIsHeap(Q, Picker);
+
+  std::pop_heap(Q.begin(), Q.end(), Picker);
+  SUnit *V = Q.back();
+
+#ifdef EXPENSIVE_CHECKS
+  SUnit *Best = *Q.begin();
+  for (auto I = std::next(Q.begin()), E = Q.end(); I != E; ++I)
+    if (Picker(Best, *I))
+      Best = *I;
+  assert(V == Best &&
+         "candidates found on heap and through linear scan differ!");
+#endif
+
+  Q.pop_back();
+  return V;
+}
+
+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 +1897,7 @@
 
   unsigned CurQueueId = 0;
   std::vector<SUnit *> Queue;
+  bool IsHeap = false;
 
 public:
   RegReductionPriorityQueue(MachineFunction &mf,
@@ -1876,7 +1919,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;
   }
@@ -1884,7 +1927,14 @@
   void push(SUnit *U) override {
     assert(!U->NodeQueueId && "Node in the queue already");
     U->NodeQueueId = ++CurQueueId;
+    if (std::is_same<SF, src_ls_rr_sort>::value && IsHeap)
+      assertIsHeap(Queue, Picker);
+
     Queue.push_back(U);
+    if (std::is_same<SF, src_ls_rr_sort>::value && IsHeap) {
+      std::push_heap(Queue.begin(), Queue.end(), Picker);
+      assertIsHeap(Queue, Picker);
+    }
   }
 
   void remove(SUnit *SU) override {
@@ -1895,6 +1945,7 @@
       std::swap(*I, Queue.back());
     Queue.pop_back();
     SU->NodeQueueId = 0;
+    IsHeap = false;
   }
 
   bool empty() const override { return Queue.empty(); }
@@ -1905,7 +1956,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);
     }