diff --git a/lib/CodeGen/RegAllocBase.h b/lib/CodeGen/RegAllocBase.h
index a0416d2..8c7e5f5 100644
--- a/lib/CodeGen/RegAllocBase.h
+++ b/lib/CodeGen/RegAllocBase.h
@@ -139,6 +139,15 @@
   // exists, return the interfering register, which may be preg or an alias.
   unsigned checkPhysRegInterference(LiveInterval& VirtReg, unsigned PhysReg);
 
+  /// assign - Assign VirtReg to PhysReg.
+  /// This should not be called from selectOrSplit for the current register.
+  void assign(LiveInterval &VirtReg, unsigned PhysReg);
+
+  /// unassign - Undo a previous assignment of VirtReg to PhysReg.
+  /// This can be invoked from selectOrSplit, but be careful to guarantee that
+  /// allocation is making progress.
+  void unassign(LiveInterval &VirtReg, unsigned PhysReg);
+
   // Helper for spilling all live virtual registers currently unified under preg
   // that interfere with the most recently queried lvr.  Return true if spilling
   // was successful, and append any new spilled/split intervals to splitLVRs.
diff --git a/lib/CodeGen/RegAllocBasic.cpp b/lib/CodeGen/RegAllocBasic.cpp
index 1175923..7fbb035e 100644
--- a/lib/CodeGen/RegAllocBasic.cpp
+++ b/lib/CodeGen/RegAllocBasic.cpp
@@ -238,6 +238,18 @@
   }
 }
 
+void RegAllocBase::assign(LiveInterval &VirtReg, unsigned PhysReg) {
+  assert(!VRM->hasPhys(VirtReg.reg) && "Duplicate VirtReg assignment");
+  VRM->assignVirt2Phys(VirtReg.reg, PhysReg);
+  PhysReg2LiveUnion[PhysReg].unify(VirtReg);
+}
+
+void RegAllocBase::unassign(LiveInterval &VirtReg, unsigned PhysReg) {
+  assert(VRM->getPhys(VirtReg.reg) == PhysReg && "Inconsistent unassign");
+  PhysReg2LiveUnion[PhysReg].extract(VirtReg);
+  VRM->clearVirt(VirtReg.reg);
+}
+
 // Top-level driver to manage the queue of unassigned VirtRegs and call the
 // selectOrSplit implementation.
 void RegAllocBase::allocatePhysRegs() {
@@ -264,9 +276,7 @@
     if (AvailablePhysReg) {
       DEBUG(dbgs() << "allocating: " << TRI->getName(AvailablePhysReg)
                    << " for " << VirtReg << '\n');
-      assert(!VRM->hasPhys(VirtReg.reg) && "duplicate vreg in union");
-      VRM->assignVirt2Phys(VirtReg.reg, AvailablePhysReg);
-      PhysReg2LiveUnion[AvailablePhysReg].unify(VirtReg);
+      assign(VirtReg, AvailablePhysReg);
     }
     for (VirtRegVec::iterator I = SplitVRegs.begin(), E = SplitVRegs.end();
          I != E; ++I) {
@@ -308,10 +318,7 @@
 
     // Deallocate the interfering vreg by removing it from the union.
     // A LiveInterval instance may not be in a union during modification!
-    PhysReg2LiveUnion[PhysReg].extract(SpilledVReg);
-
-    // Clear the vreg assignment.
-    VRM->clearVirt(SpilledVReg.reg);
+    unassign(SpilledVReg, PhysReg);
 
     // Spill the extracted interval.
     spiller().spill(&SpilledVReg, SplitVRegs, PendingSpills);
diff --git a/lib/CodeGen/RegAllocGreedy.cpp b/lib/CodeGen/RegAllocGreedy.cpp
index cfef95e..a0f129a 100644
--- a/lib/CodeGen/RegAllocGreedy.cpp
+++ b/lib/CodeGen/RegAllocGreedy.cpp
@@ -133,7 +133,6 @@
   bool checkUncachedInterference(LiveInterval&, unsigned);
   LiveInterval *getSingleInterference(LiveInterval&, unsigned);
   bool reassignVReg(LiveInterval &InterferingVReg, unsigned OldPhysReg);
-  bool reassignInterferences(LiveInterval &VirtReg, unsigned PhysReg);
   float calcInterferenceWeight(LiveInterval&, unsigned);
   void calcLiveBlockInfo(LiveInterval&);
   float calcInterferenceInfo(LiveInterval&, unsigned);
@@ -141,7 +140,8 @@
   void splitAroundRegion(LiveInterval&, unsigned, const BitVector&,
                          SmallVectorImpl<LiveInterval*>&);
 
-  unsigned tryReassign(LiveInterval&, AllocationOrder&);
+  unsigned tryReassignOrEvict(LiveInterval&, AllocationOrder&,
+                              SmallVectorImpl<LiveInterval*>&);
   unsigned tryRegionSplit(LiveInterval&, AllocationOrder&,
                           SmallVectorImpl<LiveInterval*>&);
   unsigned trySplit(LiveInterval&, AllocationOrder&,
@@ -286,41 +286,54 @@
     unsigned OldAssign = VRM->getPhys(InterferingVReg.reg);
     DEBUG(dbgs() << "reassigning: " << InterferingVReg << " from " <<
           TRI->getName(OldAssign) << " to " << TRI->getName(PhysReg) << '\n');
-    PhysReg2LiveUnion[OldAssign].extract(InterferingVReg);
-    VRM->clearVirt(InterferingVReg.reg);
-    VRM->assignVirt2Phys(InterferingVReg.reg, PhysReg);
-    PhysReg2LiveUnion[PhysReg].unify(InterferingVReg);
-
+    unassign(InterferingVReg, OldAssign);
+    assign(InterferingVReg, PhysReg);
     return true;
   }
   return false;
 }
 
-/// reassignInterferences - Reassign all interferences to different physical
-/// registers such that Virtreg can be assigned to PhysReg.
-/// Currently this only works with a single interference.
-/// @param  VirtReg Currently unassigned virtual register.
-/// @param  PhysReg Physical register to be cleared.
-/// @return True on success, false if nothing was changed.
-bool RAGreedy::reassignInterferences(LiveInterval &VirtReg, unsigned PhysReg) {
-  LiveInterval *InterferingVReg = getSingleInterference(VirtReg, PhysReg);
-  if (!InterferingVReg)
-    return false;
-  if (TargetRegisterInfo::isPhysicalRegister(InterferingVReg->reg))
-    return false;
-  return reassignVReg(*InterferingVReg, PhysReg);
-}
-
-/// tryReassign - Try to reassign interferences to different physregs.
+/// tryReassignOrEvict - Try to reassign a single interferences to a different
+/// physreg, or evict a single interference with a lower spill weight.
 /// @param  VirtReg Currently unassigned virtual register.
 /// @param  Order   Physregs to try.
 /// @return         Physreg to assign VirtReg, or 0.
-unsigned RAGreedy::tryReassign(LiveInterval &VirtReg, AllocationOrder &Order) {
+unsigned RAGreedy::tryReassignOrEvict(LiveInterval &VirtReg,
+                                      AllocationOrder &Order,
+                                      SmallVectorImpl<LiveInterval*> &NewVRegs){
   NamedRegionTimer T("Reassign", TimerGroupName, TimePassesIsEnabled);
+
+  // Keep track of the lightest single interference seen so far.
+  float BestWeight = VirtReg.weight;
+  LiveInterval *BestVirt = 0;
+  unsigned BestPhys = 0;
+
   Order.rewind();
-  while (unsigned PhysReg = Order.next())
-    if (reassignInterferences(VirtReg, PhysReg))
+  while (unsigned PhysReg = Order.next()) {
+    LiveInterval *InterferingVReg = getSingleInterference(VirtReg, PhysReg);
+    if (!InterferingVReg)
+      continue;
+    if (TargetRegisterInfo::isPhysicalRegister(InterferingVReg->reg))
+      continue;
+    if (reassignVReg(*InterferingVReg, PhysReg))
       return PhysReg;
+
+    // Cannot reassign, is this an eviction candidate?
+    if (InterferingVReg->weight < BestWeight) {
+      BestVirt = InterferingVReg;
+      BestPhys = PhysReg;
+      BestWeight = InterferingVReg->weight;
+    }
+  }
+
+  // Nothing reassigned, can we evict a lighter single interference?
+  if (BestVirt) {
+    DEBUG(dbgs() << "evicting lighter " << *BestVirt << '\n');
+    unassign(*BestVirt, VRM->getPhys(BestVirt->reg));
+    NewVRegs.push_back(BestVirt);
+    return BestPhys;
+  }
+
   return 0;
 }
 
@@ -1029,8 +1042,7 @@
     Spills.append(Q.interferingVRegs().begin(), Q.interferingVRegs().end());
     for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i) {
       LiveInterval *VReg = Q.interferingVRegs()[i];
-      PhysReg2LiveUnion[*AI].extract(*VReg);
-      VRM->clearVirt(VReg->reg);
+      unassign(*VReg, *AI);
     }
   }
 
@@ -1057,7 +1069,7 @@
   }
 
   // Try to reassign interferences.
-  if (unsigned PhysReg = tryReassign(VirtReg, Order))
+  if (unsigned PhysReg = tryReassignOrEvict(VirtReg, Order, NewVRegs))
     return PhysReg;
 
   assert(NewVRegs.empty() && "Cannot append to existing NewVRegs");