Index: include/llvm/CodeGen/LivePhysRegs.h
===================================================================
--- include/llvm/CodeGen/LivePhysRegs.h
+++ include/llvm/CodeGen/LivePhysRegs.h
@@ -93,10 +93,15 @@
         SmallVectorImpl<std::pair<unsigned, const MachineOperand*>> *Clobbers);
 
   /// \brief Returns true if register @p Reg is contained in the set. This also
-  /// works if only the super register of @p Reg has been defined, because we
-  /// always add also all sub-registers to the set.
+  /// works if only the super register of @p Reg has been defined, because
+  /// addReg() always adds all sub-registers to the set as well.
+  /// Note: Returns false if just some sub registers are live, use available()
+  /// when searching a free register.
   bool contains(unsigned Reg) const { return LiveRegs.count(Reg); }
 
+  /// Returns true if register \p Reg and no aliasing register is in the set.
+  bool available(const MachineRegisterInfo &MRI, unsigned Reg) const;
+
   /// \brief Simulates liveness when stepping backwards over an
   /// instruction(bundle): Remove Defs, add uses. This is the recommended way of
   /// calculating liveness.
Index: lib/CodeGen/LivePhysRegs.cpp
===================================================================
--- lib/CodeGen/LivePhysRegs.cpp
+++ lib/CodeGen/LivePhysRegs.cpp
@@ -17,6 +17,7 @@
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineInstrBundle.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 using namespace llvm;
@@ -126,6 +127,19 @@
 #endif
 }
 
+bool LivePhysRegs::available(const MachineRegisterInfo &MRI,
+                             unsigned Reg) const {
+  if (LiveRegs.count(Reg))
+    return false;
+  if (MRI.isReserved(Reg))
+    return false;
+  for (MCRegAliasIterator R(Reg, TRI, false); R.isValid(); ++R) {
+    if (LiveRegs.count(*R))
+      return false;
+  }
+  return true;
+}
+
 /// Add live-in registers of basic block \p MBB to \p LiveRegs.
 static void addLiveIns(LivePhysRegs &LiveRegs, const MachineBasicBlock &MBB) {
   for (const auto &LI : MBB.liveins())
Index: lib/Target/AArch64/AArch64FrameLowering.cpp
===================================================================
--- lib/Target/AArch64/AArch64FrameLowering.cpp
+++ lib/Target/AArch64/AArch64FrameLowering.cpp
@@ -93,6 +93,7 @@
 #include "AArch64Subtarget.h"
 #include "AArch64TargetMachine.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/CodeGen/LivePhysRegs.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
@@ -244,27 +245,26 @@
   if (&MF->front() == MBB)
     return AArch64::X9;
 
-  RegScavenger RS;
-  RS.enterBasicBlock(*MBB);
+  const TargetRegisterInfo &TRI = *MF->getSubtarget().getRegisterInfo();
+  LivePhysRegs LiveRegs(&TRI);
+  LiveRegs.addLiveIns(*MBB);
 
-  // Prefer X9 since it was historically used for the prologue scratch reg.
-  if (!RS.isRegUsed(AArch64::X9))
-    return AArch64::X9;
-
-  // Find a free non callee-save reg.
+  // Mark callee saved registers as used so we will not choose them.
   const AArch64Subtarget &Subtarget = MF->getSubtarget<AArch64Subtarget>();
   const AArch64RegisterInfo *RegInfo = Subtarget.getRegisterInfo();
   const MCPhysReg *CSRegs = RegInfo->getCalleeSavedRegs(MF);
-  BitVector CalleeSaveRegs(RegInfo->getNumRegs());
   for (unsigned i = 0; CSRegs[i]; ++i)
-    CalleeSaveRegs.set(CSRegs[i]);
+    LiveRegs.addReg(CSRegs[i]);
 
-  BitVector Available = RS.getRegsAvailable(&AArch64::GPR64RegClass);
-  for (int AvailReg = Available.find_first(); AvailReg != -1;
-       AvailReg = Available.find_next(AvailReg))
-    if (!CalleeSaveRegs.test(AvailReg))
-      return AvailReg;
+  // Prefer X9 since it was historically used for the prologue scratch reg.
+  const MachineRegisterInfo &MRI = MF->getRegInfo();
+  if (LiveRegs.available(MRI, AArch64::X9))
+    return AArch64::X9;
 
+  for (unsigned Reg : AArch64::GPR64RegClass) {
+    if (LiveRegs.available(MRI, Reg))
+      return Reg;
+  }
   return AArch64::NoRegister;
 }