diff --git a/llvm/lib/CodeGen/RegAllocFast.cpp b/llvm/lib/CodeGen/RegAllocFast.cpp
--- a/llvm/lib/CodeGen/RegAllocFast.cpp
+++ b/llvm/lib/CodeGen/RegAllocFast.cpp
@@ -133,6 +133,7 @@
     RegUnitSet UsedInInstr;
 
     void setPhysRegState(MCPhysReg PhysReg, unsigned NewState);
+    bool isPhysRegFree(MCPhysReg PhysReg) const;
 
     /// Mark a physreg as used in this instruction.
     void markRegUsedInInstr(MCPhysReg PhysReg) {
@@ -207,6 +208,11 @@
       return LiveVirtRegs.find(Register::virtReg2Index(VirtReg));
     }
 
+    MCPhysReg getBestRegForAllocation(const TargetRegisterClass &Class,
+                                      Register Hint0, Register Hint1) const;
+    MCPhysReg getFreeRegForAllocation(MachineInstr &MI,
+                                      const TargetRegisterClass &Class,
+                                      Register Hint0, Register Hint1);
     void allocVirtReg(MachineInstr &MI, LiveReg &LR, Register Hint);
     void allocVirtRegUndef(MachineOperand &MO);
     MCPhysReg defineVirtReg(MachineInstr &MI, unsigned OpNum, Register VirtReg,
@@ -243,6 +249,14 @@
     RegUnitStates[*UI] = NewState;
 }
 
+bool RegAllocFast::isPhysRegFree(MCPhysReg PhysReg) const {
+  for (MCRegUnitIterator UI(PhysReg, TRI); UI.isValid(); ++UI) {
+    if (RegUnitStates[*UI] != regFree)
+      return false;
+  }
+  return true;
+}
+
 /// This allocates space for the specified virtual register to be held on the
 /// stack.
 int RegAllocFast::getStackSpaceFor(Register VirtReg) {
@@ -507,7 +521,6 @@
     }
   }
 
-  markRegUsedInInstr(PhysReg);
   setPhysRegState(PhysReg, NewState);
 }
 
@@ -552,6 +565,7 @@
   assert(PhysReg != 0 && "Trying to assign no register");
   LR.PhysReg = PhysReg;
   setPhysRegState(PhysReg, VirtReg);
+  markRegUsedInInstr(PhysReg);
 }
 
 static bool isCoalescable(const MachineInstr &MI) {
@@ -594,95 +608,75 @@
   return Register();
 }
 
-/// Allocates a physical register for VirtReg.
-void RegAllocFast::allocVirtReg(MachineInstr &MI, LiveReg &LR, Register Hint0) {
-  const Register VirtReg = LR.VirtReg;
-
-  assert(Register::isVirtualRegister(VirtReg) &&
-         "Can only allocate virtual registers");
-
-  const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
-  LLVM_DEBUG(dbgs() << "Search register for " << printReg(VirtReg)
-                    << " in class " << TRI->getRegClassName(&RC)
-                    << " with hint " << printReg(Hint0, TRI) << '\n');
-
-  // Take hint when possible.
+/// Finds out which is the best register available to allocate a virtual
+/// register of the specified class, taking the hints whenever possible.
+MCPhysReg
+RegAllocFast::getBestRegForAllocation(const TargetRegisterClass &Class,
+                                      Register Hint0, Register Hint1) const {
+  // Try hints first
   if (Hint0.isPhysical() && MRI->isAllocatable(Hint0) &&
-      RC.contains(Hint0)) {
-    // Ignore the hint if we would have to spill a dirty register.
-    unsigned Cost = calcSpillCost(Hint0);
-    if (Cost < spillDirty) {
-      LLVM_DEBUG(dbgs() << "\tPreferred Register 1: " << printReg(Hint0, TRI)
-                        << '\n');
-      if (Cost)
-        definePhysReg(MI, Hint0, regFree);
-      assignVirtToPhysReg(LR, Hint0);
-      return;
-    } else {
-      LLVM_DEBUG(dbgs() << "\tPreferred Register 1: " << printReg(Hint0, TRI)
-                        << "occupied\n");
-    }
-  } else {
-    Hint0 = Register();
-  }
-
-  // Try other hint.
-  Register Hint1 = traceCopies(VirtReg);
+      Class.contains(Hint0) && (calcSpillCost(Hint0) < spillDirty))
+    return Hint0;
   if (Hint1.isPhysical() && MRI->isAllocatable(Hint1) &&
-      RC.contains(Hint1) && !isRegUsedInInstr(Hint1)) {
-    // Ignore the hint if we would have to spill a dirty register.
-    unsigned Cost = calcSpillCost(Hint1);
-    if (Cost < spillDirty) {
-      LLVM_DEBUG(dbgs() << "\tPreferred Register 0: " << printReg(Hint1, TRI)
-                        << '\n');
-      if (Cost)
-        definePhysReg(MI, Hint1, regFree);
-      assignVirtToPhysReg(LR, Hint1);
-      return;
-    } else {
-      LLVM_DEBUG(dbgs() << "\tPreferred Register 0: " << printReg(Hint1, TRI)
-                        << "occupied\n");
-    }
-  } else {
-    Hint1 = Register();
-  }
+      Class.contains(Hint1) && (calcSpillCost(Hint1) < spillDirty))
+    return Hint1;
 
+  // Otherwise, get reg with best cost following allocation order
   MCPhysReg BestReg = 0;
   unsigned BestCost = spillImpossible;
-  ArrayRef<MCPhysReg> AllocationOrder = RegClassInfo.getOrder(&RC);
+  auto AllocationOrder = RegClassInfo.getOrder(&Class);
   for (MCPhysReg PhysReg : AllocationOrder) {
-    LLVM_DEBUG(dbgs() << "\tRegister: " << printReg(PhysReg, TRI) << ' ');
     unsigned Cost = calcSpillCost(PhysReg);
-    LLVM_DEBUG(dbgs() << "Cost: " << Cost << " BestCost: " << BestCost << '\n');
-    // Immediate take a register with cost 0.
-    if (Cost == 0) {
-      assignVirtToPhysReg(LR, PhysReg);
-      return;
-    }
-
-    if (PhysReg == Hint1 || PhysReg == Hint0)
+    if (PhysReg == Hint0 || PhysReg == Hint1)
       Cost -= spillPrefBonus;
-
     if (Cost < BestCost) {
       BestReg = PhysReg;
       BestCost = Cost;
     }
+    if (Cost == 0)
+      break;
   }
+  return BestReg;
+}
 
-  if (!BestReg) {
-    // Nothing we can do: Report an error and keep going with an invalid
-    // allocation.
+/// Gets an avaliable register of the specified class for allocation, making
+/// sure it is free and ready to be used and spilling when necessary.
+MCPhysReg
+RegAllocFast::getFreeRegForAllocation(MachineInstr &MI,
+                                      const TargetRegisterClass &Class,
+                                      Register Hint0, Register Hint1) {
+  MCPhysReg PhysReg = getBestRegForAllocation(Class, Hint0, Hint1);
+
+  if (!PhysReg) {
+    // No register available
+    // Report an error and keep going with an invalid allocation
     if (MI.isInlineAsm())
       MI.emitError("inline assembly requires more registers than available");
     else
       MI.emitError("ran out of registers during register allocation");
-    definePhysReg(MI, *AllocationOrder.begin(), regFree);
-    assignVirtToPhysReg(LR, *AllocationOrder.begin());
-    return;
+    PhysReg = RegClassInfo.getOrder(&Class).front();
   }
 
-  definePhysReg(MI, BestReg, regFree);
-  assignVirtToPhysReg(LR, BestReg);
+  if (!isPhysRegFree(PhysReg))
+    definePhysReg(MI, PhysReg, regFree);
+  return PhysReg;
+}
+
+/// Allocates a physical register for VirtReg.
+void RegAllocFast::allocVirtReg(MachineInstr &MI, LiveReg &LR, Register Hint0) {
+  const Register VirtReg = LR.VirtReg;
+
+  assert(Register::isVirtualRegister(VirtReg) &&
+         "Can only allocate virtual registers");
+
+  const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
+  LLVM_DEBUG(dbgs() << "Search register for " << printReg(VirtReg)
+                    << " in class " << TRI->getRegClassName(&RC)
+                    << " with hint " << printReg(Hint0, TRI) << '\n');
+
+  Register Hint1 = traceCopies(VirtReg);
+  MCPhysReg PhysReg = getFreeRegForAllocation(MI, RC, Hint0, Hint1);
+  assignVirtToPhysReg(LR, PhysReg);
 }
 
 void RegAllocFast::allocVirtRegUndef(MachineOperand &MO) {
@@ -1012,6 +1006,7 @@
     } else if (MO.isEarlyClobber()) {
       definePhysReg(MI, Reg,
                     (MO.isImplicit() || MO.isDead()) ? regFree : regReserved);
+      markRegUsedInInstr(Reg);
       hasEarlyClobbers = true;
     } else
       hasPhysDefs = true;
@@ -1118,6 +1113,7 @@
 
     if (!Reg || !Reg.isPhysical() || !MRI->isAllocatable(Reg))
       continue;
+    markRegUsedInInstr(Reg);
     definePhysReg(MI, Reg, MO.isDead() ? regFree : regReserved);
   }