Index: llvm/trunk/include/llvm/CodeGen/LiveRegUnits.h
===================================================================
--- llvm/trunk/include/llvm/CodeGen/LiveRegUnits.h
+++ llvm/trunk/include/llvm/CodeGen/LiveRegUnits.h
@@ -76,6 +76,10 @@
   /// The regmask has the same format as the one in the RegMask machine operand.
   void removeRegsNotPreserved(const uint32_t *RegMask);
 
+  /// Adds register units not preserved by the regmask \p RegMask.
+  /// The regmask has the same format as the one in the RegMask machine operand.
+  void addRegsInMask(const uint32_t *RegMask);
+
   /// Returns true if no part of physical register \p Reg is live.
   bool available(unsigned Reg) const {
     for (MCRegUnitIterator Unit(Reg, TRI); Unit.isValid(); ++Unit) {
@@ -88,6 +92,11 @@
   /// Updates liveness when stepping backwards over the instruction \p MI.
   void stepBackward(const MachineInstr &MI);
 
+  /// Mark all register units live during instruction \p MI.
+  /// This can be used to accumulate live/unoccupied registers over a range of
+  /// instructions.
+  void accumulateBackward(const MachineInstr &MI);
+
   /// Adds registers living out of block \p MBB.
   /// Live out registers are the union of the live-in registers of the successor
   /// blocks and pristine registers. Live out registers of the end block are the
Index: llvm/trunk/lib/CodeGen/LiveRegUnits.cpp
===================================================================
--- llvm/trunk/lib/CodeGen/LiveRegUnits.cpp
+++ llvm/trunk/lib/CodeGen/LiveRegUnits.cpp
@@ -26,6 +26,15 @@
   }
 }
 
+void LiveRegUnits::addRegsInMask(const uint32_t *RegMask) {
+  for (unsigned U = 0, E = TRI->getNumRegUnits(); U != E; ++U) {
+    for (MCRegUnitRootIterator RootReg(U, TRI); RootReg.isValid(); ++RootReg) {
+      if (MachineOperand::clobbersPhysReg(RegMask, *RootReg))
+        Units.set(U);
+    }
+  }
+}
+
 void LiveRegUnits::stepBackward(const MachineInstr &MI) {
   // Remove defined registers and regmask kills from the set.
   for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
@@ -51,6 +60,21 @@
   }
 }
 
+void LiveRegUnits::accumulateBackward(const MachineInstr &MI) {
+  // Add defs, uses and regmask clobbers to the set.
+  for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
+    if (O->isReg()) {
+      unsigned Reg = O->getReg();
+      if (!TargetRegisterInfo::isPhysicalRegister(Reg))
+        continue;
+      if (!O->isDef() && !O->readsReg())
+        continue;
+      addReg(Reg);
+    } else if (O->isRegMask())
+      addRegsInMask(O->getRegMask());
+  }
+}
+
 /// Add live-in registers of basic block \p MBB to \p LiveUnits.
 static void addLiveIns(LiveRegUnits &LiveUnits, const MachineBasicBlock &MBB) {
   for (const auto &LI : MBB.liveins())
Index: llvm/trunk/lib/Target/AArch64/AArch64A57FPLoadBalancing.cpp
===================================================================
--- llvm/trunk/lib/Target/AArch64/AArch64A57FPLoadBalancing.cpp
+++ llvm/trunk/lib/Target/AArch64/AArch64A57FPLoadBalancing.cpp
@@ -493,43 +493,29 @@
 
 int AArch64A57FPLoadBalancing::scavengeRegister(Chain *G, Color C,
                                                 MachineBasicBlock &MBB) {
-  RegScavenger RS;
-  RS.enterBasicBlock(MBB);
-  RS.forward(MachineBasicBlock::iterator(G->getStart()));
-
   // Can we find an appropriate register that is available throughout the life
-  // of the chain?
-  unsigned RegClassID = G->getStart()->getDesc().OpInfo[0].RegClass;
-  BitVector AvailableRegs = RS.getRegsAvailable(TRI->getRegClass(RegClassID));
-  for (MachineBasicBlock::iterator I = G->begin(), E = G->end(); I != E; ++I) {
-    RS.forward(I);
-    AvailableRegs &= RS.getRegsAvailable(TRI->getRegClass(RegClassID));
-
-    // Remove any registers clobbered by a regmask or any def register that is
-    // immediately dead.
-    for (auto J : I->operands()) {
-      if (J.isRegMask())
-        AvailableRegs.clearBitsNotInMask(J.getRegMask());
-
-      if (J.isReg() && J.isDef()) {
-        MCRegAliasIterator AI(J.getReg(), TRI, /*IncludeSelf=*/true);
-        if (J.isDead())
-          for (; AI.isValid(); ++AI)
-            AvailableRegs.reset(*AI);
-#ifndef NDEBUG
-        else
-          for (; AI.isValid(); ++AI)
-            assert(!AvailableRegs[*AI] &&
-                   "Non-dead def should have been removed by now!");
-#endif
-      }
-    }
-  }
+  // of the chain? Simulate liveness backwards until the end of the chain.
+  LiveRegUnits Units(*TRI);
+  Units.addLiveOuts(MBB);
+  MachineBasicBlock::iterator I = MBB.end(), ChainEnd = G->end();
+  do {
+    --I;
+    Units.stepBackward(*I);
+  } while (I != ChainEnd);
+
+  // Check which register units are alive throughout the chain.
+  MachineBasicBlock::iterator ChainBegin = G->begin();
+  assert(ChainBegin != ChainEnd && "Chain should contain instructions");
+  do {
+    --I;
+    Units.accumulateBackward(*I);
+  } while (I != ChainBegin);
 
   // Make sure we allocate in-order, to get the cheapest registers first.
+  unsigned RegClassID = ChainBegin->getDesc().OpInfo[0].RegClass;
   auto Ord = RCI.getOrder(TRI->getRegClass(RegClassID));
   for (auto Reg : Ord) {
-    if (!AvailableRegs[Reg])
+    if (!Units.available(Reg))
       continue;
     if (C == getColor(Reg))
       return Reg;