Index: lib/CodeGen/RegAllocGreedy.cpp
===================================================================
--- lib/CodeGen/RegAllocGreedy.cpp
+++ lib/CodeGen/RegAllocGreedy.cpp
@@ -194,6 +194,8 @@
 
   IndexedMap<RegInfo, VirtReg2IndexFunctor> ExtraRegInfo;
 
+  BitVector UsedRegUnits;
+
   LiveRangeStage getStage(const LiveInterval &VirtReg) const {
     return ExtraRegInfo[VirtReg.reg].Stage;
   }
@@ -400,6 +402,9 @@
   typedef SmallVector<HintInfo, 4> HintsInfo;
   BlockFrequency getBrokenHintFreq(const HintsInfo &, unsigned);
   void collectHintInfo(unsigned, HintsInfo &);
+
+  void setRegUsed(unsigned PhysReg);
+  bool isUnusedCSR(unsigned PhysReg) const;
 };
 } // end anonymous namespace
 
@@ -513,6 +518,7 @@
   SpillerInstance.reset();
   ExtraRegInfo.clear();
   GlobalCand.clear();
+  UsedRegUnits.clear();
 }
 
 void RAGreedy::enqueue(LiveInterval *LI) { enqueue(Queue, LI); }
@@ -816,6 +822,20 @@
   }
 }
 
+/// Returns true if the given \p PhysReg is a callee saved register and has not
+/// been used for allocation yet.
+bool RAGreedy::isUnusedCSR(unsigned PhysReg) const {
+  unsigned CSR = RegClassInfo.getLastCalleeSavedAlias(PhysReg);
+  if (CSR == 0)
+    return false;
+
+  for (MCRegUnitIterator Unit(CSR, TRI); Unit.isValid(); ++Unit) {
+    if (UsedRegUnits.test(*Unit))
+      return false;
+  }
+  return true;
+}
+
 /// tryEvict - Try to evict all interferences for a physreg.
 /// @param  VirtReg Currently unassigned virtual register.
 /// @param  Order   Physregs to try.
@@ -861,13 +881,12 @@
       continue;
     // The first use of a callee-saved register in a function has cost 1.
     // Don't start using a CSR when the CostPerUseLimit is low.
-    if (CostPerUseLimit == 1)
-     if (unsigned CSR = RegClassInfo.getLastCalleeSavedAlias(PhysReg))
-       if (!MRI->isPhysRegUsed(CSR)) {
-         DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " would clobber CSR "
-                      << PrintReg(CSR, TRI) << '\n');
-         continue;
-       }
+    if (CostPerUseLimit == 1 && isUnusedCSR(PhysReg)) {
+      DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " would clobber CSR "
+            << PrintReg(RegClassInfo.getLastCalleeSavedAlias(PhysReg), TRI)
+            << '\n');
+      continue;
+    }
 
     if (!canEvictInterference(VirtReg, PhysReg, false, BestCost))
       continue;
@@ -1348,9 +1367,8 @@
   unsigned BestCand = NoCand;
   Order.rewind();
   while (unsigned PhysReg = Order.next()) {
-   if (unsigned CSR = RegClassInfo.getLastCalleeSavedAlias(PhysReg))
-     if (IgnoreCSR && !MRI->isPhysRegUsed(CSR))
-       continue;
+    if (IgnoreCSR && isUnusedCSR(PhysReg))
+      continue;
 
     // Discard bad candidates before we run out of interference cache cursors.
     // This will only affect register classes with a lot of registers (>32).
@@ -1996,6 +2014,12 @@
   return true;
 }
 
+void RAGreedy::setRegUsed(unsigned PhysReg) {
+  for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) {
+    UsedRegUnits.set(*Unit);
+  }
+}
+
 /// tryLastChanceRecoloring - Try to assign a color to \p VirtReg by recoloring
 /// its interferences.
 /// Last chance recoloring chooses a color for \p VirtReg and recolors every
@@ -2108,6 +2132,7 @@
     // recoloring has the right information about the interferes and
     // available colors.
     Matrix->assign(VirtReg, PhysReg);
+    setRegUsed(PhysReg);
 
     // Save the current recoloring state.
     // If we cannot recolor all the interferences, we will have to start again
@@ -2134,7 +2159,9 @@
       unsigned ItVirtReg = (*It)->reg;
       if (VRM->hasPhys(ItVirtReg))
         Matrix->unassign(**It);
-      Matrix->assign(**It, VirtRegToPhysReg[ItVirtReg]);
+      unsigned ItPhysReg = VirtRegToPhysReg[ItVirtReg];
+      Matrix->assign(**It, ItPhysReg);
+      setRegUsed(ItPhysReg);
     }
   }
 
@@ -2164,6 +2191,7 @@
     DEBUG(dbgs() << "Recoloring of " << *LI
                  << " succeeded with: " << PrintReg(PhysReg, TRI) << '\n');
     Matrix->assign(*LI, PhysReg);
+    setRegUsed(PhysReg);
     FixedRegisters.insert(LI->reg);
   }
   return true;
@@ -2194,6 +2222,8 @@
                     "depth for recoloring reached. Use "
                     "-fexhaustive-register-search to skip cutoffs");
   }
+  if (Reg != 0 && Reg != ~0U)
+    setRegUsed(Reg);
   return Reg;
 }
 
@@ -2375,6 +2405,7 @@
       // Recolor the live-range.
       Matrix->unassign(LI);
       Matrix->assign(LI, PhysReg);
+      setRegUsed(PhysReg);
     }
     // Push all copy-related live-ranges to keep reconciling the broken
     // hints.
@@ -2441,16 +2472,10 @@
   // First try assigning a free register.
   AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo);
   if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs)) {
-    // We check other options if we are using a CSR for the first time.
-    bool CSRFirstUse = false;
-    if (unsigned CSR = RegClassInfo.getLastCalleeSavedAlias(PhysReg))
-      if (!MRI->isPhysRegUsed(CSR))
-        CSRFirstUse = true;
-
     // When NewVRegs is not empty, we may have made decisions such as evicting
     // a virtual register, go with the earlier decisions and use the physical
     // register.
-    if (CSRCost.getFrequency() && CSRFirstUse && NewVRegs.empty()) {
+    if (CSRCost.getFrequency() && isUnusedCSR(PhysReg) && NewVRegs.empty()) {
       unsigned CSRReg = tryAssignCSRFirstTime(VirtReg, Order, PhysReg,
                                               CostPerUseLimit, NewVRegs);
       if (CSRReg || !NewVRegs.empty())
@@ -2528,6 +2553,8 @@
   TII = MF->getSubtarget().getInstrInfo();
   RCI.runOnMachineFunction(mf);
 
+  UsedRegUnits.resize(TRI->getNumRegUnits());
+
   EnableLocalReassign = EnableLocalReassignment ||
                         MF->getSubtarget().enableRALocalReassignment(
                             MF->getTarget().getOptLevel());