diff --git a/lib/CodeGen/RegAllocBase.h b/lib/CodeGen/RegAllocBase.h
index 7f38c9b..65bec06 100644
--- a/lib/CodeGen/RegAllocBase.h
+++ b/lib/CodeGen/RegAllocBase.h
@@ -39,6 +39,7 @@
 
 #include "llvm/ADT/OwningPtr.h"
 #include "LiveIntervalUnion.h"
+#include <queue>
 
 namespace llvm {
 
@@ -48,16 +49,6 @@
 class LiveIntervals;
 class Spiller;
 
-// Heuristic that determines the priority of assigning virtual to physical
-// registers. The main impact of the heuristic is expected to be compile time.
-// The default is to simply compare spill weights.
-struct LessSpillWeightPriority
-  : public std::binary_function<LiveInterval,LiveInterval, bool> {
-  bool operator()(const LiveInterval *Left, const LiveInterval *Right) const {
-    return Left->weight < Right->weight;
-  }
-};
-
 // Forward declare a priority queue of live virtual registers. If an
 // implementation needs to prioritize by anything other than spill weight, then
 // this will become an abstract base class with virtual calls to push/get.
@@ -128,6 +119,10 @@
   // Get a temporary reference to a Spiller instance.
   virtual Spiller &spiller() = 0;
 
+  // getPriority - Calculate the allocation priority for VirtReg.
+  // Virtual registers with higher priorities are allocated first.
+  virtual float getPriority(LiveInterval *LI) = 0;
+
   // A RegAlloc pass should override this to provide the allocation heuristics.
   // Each call must guarantee forward progess by returning an available PhysReg
   // or new set of split live virtual registers. It is up to the splitter to
@@ -158,7 +153,7 @@
 #endif
 
 private:
-  void seedLiveVirtRegs(LiveVirtRegQueue &VirtRegQ);
+  void seedLiveVirtRegs(std::priority_queue<std::pair<float, unsigned> >&);
 
   void spillReg(LiveInterval &VirtReg, unsigned PhysReg,
                 SmallVectorImpl<LiveInterval*> &SplitVRegs);
diff --git a/lib/CodeGen/RegAllocBasic.cpp b/lib/CodeGen/RegAllocBasic.cpp
index d0e6355..88446aa 100644
--- a/lib/CodeGen/RegAllocBasic.cpp
+++ b/lib/CodeGen/RegAllocBasic.cpp
@@ -43,8 +43,6 @@
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
 
-#include <vector>
-#include <queue>
 #include <cstdlib>
 
 using namespace llvm;
@@ -103,6 +101,8 @@
 
   virtual Spiller &spiller() { return *SpillerInstance; }
 
+  virtual float getPriority(LiveInterval *LI) { return LI->weight; }
+
   virtual unsigned selectOrSplit(LiveInterval &VirtReg,
                                  SmallVectorImpl<LiveInterval*> &SplitVRegs);
 
@@ -230,49 +230,18 @@
   PhysReg2LiveUnion.clear();
 }
 
-namespace llvm {
-/// This class defines a queue of live virtual registers prioritized by spill
-/// weight. The heaviest vreg is popped first.
-///
-/// Currently, this is trivial wrapper that gives us an opaque type in the
-/// header, but we may later give it a virtual interface for register allocators
-/// to override the priority queue comparator.
-class LiveVirtRegQueue {
-  typedef std::priority_queue
-    <LiveInterval*, std::vector<LiveInterval*>, LessSpillWeightPriority>
-    PriorityQ;
-  PriorityQ PQ;
-
-public:
-  // Is the queue empty?
-  bool empty() { return PQ.empty(); }
-
-  // Get the highest priority lvr (top + pop)
-  LiveInterval *get() {
-    LiveInterval *VirtReg = PQ.top();
-    PQ.pop();
-    return VirtReg;
-  }
-  // Add this lvr to the queue
-  void push(LiveInterval *VirtReg) {
-    PQ.push(VirtReg);
-  }
-};
-} // end namespace llvm
-
 // Visit all the live virtual registers. If they are already assigned to a
 // physical register, unify them with the corresponding LiveIntervalUnion,
 // otherwise push them on the priority queue for later assignment.
-void RegAllocBase::seedLiveVirtRegs(LiveVirtRegQueue &VirtRegQ) {
+void RegAllocBase::
+seedLiveVirtRegs(std::priority_queue<std::pair<float, unsigned> > &VirtRegQ) {
   for (LiveIntervals::iterator I = LIS->begin(), E = LIS->end(); I != E; ++I) {
     unsigned RegNum = I->first;
     LiveInterval &VirtReg = *I->second;
-    if (TargetRegisterInfo::isPhysicalRegister(RegNum)) {
+    if (TargetRegisterInfo::isPhysicalRegister(RegNum))
       PhysReg2LiveUnion[RegNum].unify(VirtReg);
-    }
-    else {
-      VirtRegQ.push(&VirtReg);
-    }
+    else
+      VirtRegQ.push(std::make_pair(getPriority(&VirtReg), RegNum));
   }
 }
 
@@ -281,27 +250,28 @@
 void RegAllocBase::allocatePhysRegs() {
 
   // Push each vreg onto a queue or "precolor" by adding it to a physreg union.
-  LiveVirtRegQueue VirtRegQ;
+  std::priority_queue<std::pair<float, unsigned> > VirtRegQ;
   seedLiveVirtRegs(VirtRegQ);
 
   // Continue assigning vregs one at a time to available physical registers.
   while (!VirtRegQ.empty()) {
     // Pop the highest priority vreg.
-    LiveInterval *VirtReg = VirtRegQ.get();
+    LiveInterval &VirtReg = LIS->getInterval(VirtRegQ.top().second);
+    VirtRegQ.pop();
 
     // selectOrSplit requests the allocator to return an available physical
     // register if possible and populate a list of new live intervals that
     // result from splitting.
     typedef SmallVector<LiveInterval*, 4> VirtRegVec;
     VirtRegVec SplitVRegs;
-    unsigned AvailablePhysReg = selectOrSplit(*VirtReg, SplitVRegs);
+    unsigned AvailablePhysReg = selectOrSplit(VirtReg, SplitVRegs);
 
     if (AvailablePhysReg) {
       DEBUG(dbgs() << "allocating: " << TRI->getName(AvailablePhysReg) <<
-            " " << *VirtReg << '\n');
-      assert(!VRM->hasPhys(VirtReg->reg) && "duplicate vreg in union");
-      VRM->assignVirt2Phys(VirtReg->reg, AvailablePhysReg);
-      PhysReg2LiveUnion[AvailablePhysReg].unify(*VirtReg);
+            " " << VirtReg << '\n');
+      assert(!VRM->hasPhys(VirtReg.reg) && "duplicate vreg in union");
+      VRM->assignVirt2Phys(VirtReg.reg, AvailablePhysReg);
+      PhysReg2LiveUnion[AvailablePhysReg].unify(VirtReg);
     }
     for (VirtRegVec::iterator I = SplitVRegs.begin(), E = SplitVRegs.end();
          I != E; ++I) {
@@ -310,7 +280,8 @@
       DEBUG(dbgs() << "queuing new interval: " << *SplitVirtReg << "\n");
       assert(TargetRegisterInfo::isVirtualRegister(SplitVirtReg->reg) &&
              "expect split value in virtual register");
-      VirtRegQ.push(SplitVirtReg);
+      VirtRegQ.push(std::make_pair(getPriority(SplitVirtReg),
+                                   SplitVirtReg->reg));
     }
   }
 }
diff --git a/lib/CodeGen/RegAllocGreedy.cpp b/lib/CodeGen/RegAllocGreedy.cpp
index 96e5531..5f2be81 100644
--- a/lib/CodeGen/RegAllocGreedy.cpp
+++ b/lib/CodeGen/RegAllocGreedy.cpp
@@ -70,6 +70,8 @@
 
   virtual Spiller &spiller() { return *SpillerInstance; }
 
+  virtual float getPriority(LiveInterval *LI) { return LI->weight; }
+
   virtual unsigned selectOrSplit(LiveInterval &VirtReg,
                                  SmallVectorImpl<LiveInterval*> &SplitVRegs);