RegScavenging: Add scavengeRegisterBackwards()

[MatzeB]

Summary

This is a variant of scavengeRegister() that works for
enterBasicBlockEnd()/backward(). The benefit of the backward mode is
that it is not affected by incomplete kill flags.

This patch also changes
PrologEpilogInserter::doScavengeFrameVirtualRegs() to use the register
scavenger in backwards mode.

This patch is a big step towards being independent of kill flags.

[t.p.northover]

include/llvm/CodeGen/RegisterScavenging.h

168–169

Could you be explicit about what the range is here?

I'm guessing To is before this->MBBI and that "inclusive" only applies to both, so the range would be [To, this->MBBI] (i.e. neither To nor this->MBBI may clobber the register).

lib/CodeGen/PrologEpilogInserter.cpp

1172–1174

I don't follow this 2-address exception. It looks like for something like

1: %v0 = INST %v0, ...
[...]
2: %v0 = INST
[...]
3: INST %v0<kill>

we'd find DefMI is instruction 2 and look for a register that's free between 2 & 3, but then set %v0 to this register everywhere. What happens if that register is defined between 1 & 2?

It seems unlikely that the first Def will be an instruction like 1 (though not impossible and w0, w0, #0 or something could exist), but then again the whole exception is pointless if it can't happen.

[MatzeB]

include/llvm/CodeGen/RegisterScavenging.h

168–169

Yes you guessed correctly; I'll change the wording to be clearer.

lib/CodeGen/PrologEpilogInserter.cpp

1172–1174

The idea here is that ideally we would only want 1 definition for each virtual register. However this would not work with two-address instructions as something like:

`
%v0 = XXX
%v1 = INST %v0<tied-0>
`
would give you no guarantees that v1 receives the same register as v0. So instead of just allowing a single definition I also allow additional definitions for instructions that read and write the register at the same time.

The example you presented would be invalid in this scheme as the first definition is not allowed: The first definition is not allowed to read the register while subsequent definitions are only allowed if the instruction reads the register at the same time. Also note that this is not a new requirement, this just documents the status-quo.

I can try to reword the comment, the code may be slightly confusing because the MachineRegisterInfo::def_iterator gives no ordering guarantees so I cannot enforce the rules/abort when they are broken.

[t.p.northover]

lib/CodeGen/PrologEpilogInserter.cpp

1172–1174

Ah, I see. So we're actually searching through an annoyingly randomized list for the topmost definition. I understand the comment too now.

So why do we stop the search one before the end (middle clause of for)? Is it an over-zealous attempt to make sure FirstDef is valid on exit?

Without that std::find_if may (or may not, depending on taste) be a little clearer:

auto FirstDef = std::find_if(MRI.def_begin(VReg), MRI.def_end(), [](MachineRegisterInfo::def_iterator I) {
  return !I->getParent()->readsRegister(VReg, TRI);
});
assert(FirstMI != MRI.def_end() && "cannot find first definition");

[t.p.northover]

lib/CodeGen/PrologEpilogInserter.cpp

1172–1174

Ah no, the extra weirdness is harmless: when it changes behaviour we must be on the canonical definition anyway.

[MatzeB]

Thanks for the review. I improved the comments and used std:find_if which does indeed improve code clarity.

[t.p.northover]

test/CodeGen/Mips/emergency-spill-slot-near-fp.ll

3–5

Don't we need to come up with an alternative that does need a spill slot then? Not that I actually have any idea how to do that on MIPS, but XFAILing the test probably means it'll just be forgotten forever.

[dsanders]

test/CodeGen/Mips/emergency-spill-slot-near-fp.ll

3–5

I'd prefer not to xfail unless we have to.

Not that I actually have any idea how to do that on MIPS

I think this test is relying on a stack frame that exceeds 16-bits and is using the '%unused_variable = alloca [16384 x i32], align 4' to make sure that happens. I'd guess that the change has made the stack frame smaller somehow and all the offsets fit in a 16-bit integer. Have some of the alloca's been optimized out?

The other causes of an emergency spill slot involve DSP accumulators and double-precision floats but they aren't used in this test.

[MatzeB]

Daniel, I reworked test/CodeGen/Mips/emergency-spill-slot-near-fp.ll. Can you take a look if the test looks okay? In it's current form it forces the RegisterScavenger to spill 1 register and I check that it ends up in 0($sp) to make sure it did not end up on the other side of the big "%stackspace" object.

[MatzeB]

In D21885#480463, @MatzeB wrote:

Daniel, I reworked test/CodeGen/Mips/emergency-spill-slot-near-fp.ll. Can you take a look if the test looks okay? In it's current form it forces the RegisterScavenger to spill 1 register and I check that it ends up in 0($sp) to make sure it did not end up on the other side of the big "%stackspace" object.

Daniel: ping!

[qcolombet]

LGTM as well.

@Daniel, leaving you the final approval for the MIPS test case.

[dsanders]

The MIPS test LGTM, it's a lot clearer about how it's going about the test too. Thanks, and sorry for the delay.

include/llvm/CodeGen/RegisterScavenging.h

for (SmallVectorImpl<ScavengedInfo>::const_iterator I = Scavenged.begin(),
       if (I->FrameIndex >= 0)
         A.push_back(I->FrameIndex);
   }
 
   /// Make a register of the specific register class
   /// available and do the appropriate bookkeeping. SPAdj is the stack
   /// adjustment due to call frame, it's passed along to eliminateFrameIndex().
   /// Returns the scavenged register.
+  /// This function performs worse if kill flags are incomplete, consider using
+  /// scavengeRegisterBackwards() instead!
   unsigned scavengeRegister(const TargetRegisterClass *RegClass,
                             MachineBasicBlock::iterator I, int SPAdj);
   unsigned scavengeRegister(const TargetRegisterClass *RegClass, int SPAdj) {
     return scavengeRegister(RegClass, MBBI, SPAdj);
   }
 
+  /// Make a register of the specific register class available from the current
+  /// position backwards to the place before \p To. If \p RestoreAfter is true
+  /// this includes the instruction at the current position.
+  /// SPAdj is the stack adjustment due to call frame, it's passed along to
+  /// eliminateFrameIndex().
+  /// Returns the scavenged register.
+  unsigned scavengeRegisterBackwards(const TargetRegisterClass &RC,
+                                     MachineBasicBlock::iterator To,
+                                     bool RestoreAfter, int SPAdj);
+
   /// Tell the scavenger a register is used.
   void setRegUsed(unsigned Reg, LaneBitmask LaneMask = ~0u);
 private:
   /// Returns true if a register is reserved. It is never "unused".
   bool isReserved(unsigned Reg) const { return MRI->isReserved(Reg); }
 
   /// setUsed / setUnused - Mark the state of one or a number of register units.
   ///
unsigned findSurvivorReg(MachineBasicBlock::iterator StartMI,
                            unsigned InstrLimit,
                            MachineBasicBlock::iterator &UseMI);
 
   /// Initialize RegisterScavenger.
   void init(MachineBasicBlock &MBB);
 
   /// Mark live-in registers of basic block as used.
   void setLiveInsUsed(const MachineBasicBlock &MBB);
+
+  /// Spill a register after position \p After and reload it before position
+  /// \p UseMI.
+  ScavengedInfo &spill(unsigned Reg, const TargetRegisterClass &RC, int SPAdj,
+                       MachineBasicBlock::iterator After,
+                       MachineBasicBlock::iterator &UseMI);
 };
 
 } // End llvm namespace
 
 #endif

lib/CodeGen/PrologEpilogInserter.cpp

 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetFrameLowering.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetRegisterInfo.h"
 #include "llvm/Target/TargetSubtargetInfo.h"
+#include <algorithm>
 #include <climits>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "pei"
 
 typedef SmallVector<MachineBasicBlock *, 4> MBBVector;
 static void doSpillCalleeSavedRegs(MachineFunction &MF, RegScavenger *RS,
for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ) {
     if (DoIncr && I != BB->end()) ++I;
 
     // Update register states.
     if (RS && !FrameIndexVirtualScavenging && DidFinishLoop)
       RS->forward(MI);
   }
 }
 
+/// Allocate a register for the virtual register \p VReg. The last use of
+/// \p VReg is around the current position of the register scavenger \p RS.
+/// \p ReserveAfter controls whether the scavenged register needs to be reserved
+/// after the current instruction, otherwise it will only be reserved before the
+/// current instruction.
+static unsigned scavengeVReg(MachineRegisterInfo &MRI, RegScavenger &RS,
+                             unsigned VReg, bool ReserveAfter) {
+#ifndef NDEBUG
+  // Verify that all definitions and uses are in the same basic block.
+  const MachineBasicBlock *CommonMBB = nullptr;
+  bool HadDef = false;
+  for (MachineOperand &MO : MRI.reg_nodbg_operands(VReg)) {
+    MachineBasicBlock *MBB = MO.getParent()->getParent();
+    if (CommonMBB == nullptr)
+      CommonMBB = MBB;
+    assert(MBB == CommonMBB && "All defs+uses must be in the same basic block");
+    if (MO.isDef())
+      HadDef = true;
+  }
+  assert(HadDef && "Must have at least 1 Def");
+#endif
+
+  // We should only have one definition of the register. However to accomodate
+  // the requirements of two address code we also allow definitions in
+  // subsequent instructions provided they also read the register. That way
+  // we get a single contiguous lifetime.
+  //
+  // Definitions in MRI.def_begin() are unordered, search for the first.
+  const TargetRegisterInfo *TRI = MRI.getTargetRegisterInfo();
+  MachineRegisterInfo::def_iterator FirstDef =
+    std::find_if(MRI.def_begin(VReg), MRI.def_end(),
+                 [VReg, TRI](const MachineOperand &MO) {
+      return !MO.getParent()->readsRegister(VReg, TRI);
+    });
+  assert(FirstDef != MRI.def_end() &&
+         "Must have one definition that does not redefine vreg");
+  MachineInstr &DefMI = *FirstDef->getParent();
+
+  // The register scavenger will report a free register inserting an emergency
+  // spill/reload if necessary.
+  int SPAdj = 0;
+  const TargetRegisterClass &RC = *MRI.getRegClass(VReg);
+  unsigned SReg = RS.scavengeRegisterBackwards(RC, DefMI.getIterator(),
+                                               ReserveAfter, SPAdj);
+  MRI.replaceRegWith(VReg, SReg);
+  ++NumScavengedRegs;
+  return SReg;
+}
+
 /// doScavengeFrameVirtualRegs - Replace all frame index virtual registers
 /// with physical registers. Use the register scavenger to find an
 /// appropriate register to use.
 ///
 /// FIXME: Iterating over the instruction stream is unnecessary. We can simply
 /// iterate over the vreg use list, which at this point only contains machine
 /// operands for which eliminateFrameIndex need a new scratch reg.
 static void
 doScavengeFrameVirtualRegs(MachineFunction &MF, RegScavenger *RS) {
   // Run through the instructions and find any virtual registers.
   MachineRegisterInfo &MRI = MF.getRegInfo();
   for (MachineBasicBlock &MBB : MF) {
-    RS->enterBasicBlock(MBB);
-
-    int SPAdj = 0;
+    RS->enterBasicBlockEnd(MBB);
 
-    // The instruction stream may change in the loop, so check MBB.end()
-    // directly.
-    for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ) {
-      // We might end up here again with a NULL iterator if we scavenged a
-      // register for which we inserted spill code for definition by what was
-      // originally the first instruction in MBB.
-      if (I == MachineBasicBlock::iterator(nullptr))
-        I = MBB.begin();
+    bool LastIterationHadVRegUses = false;
+    for (MachineBasicBlock::iterator I = MBB.end(); I != MBB.begin(); ) {
+      --I;
+      // Move RegScavenger to the position between *I and *std::next(I).
+      RS->backward(I);
+
+      // Look for unassigned vregs in the uses of *std::next(I).
+      MachineBasicBlock::iterator N = std::next(I);
+      if (LastIterationHadVRegUses) {
+        const MachineInstr &NMI = *N;
+        for (const MachineOperand &MO : NMI.operands()) {
+          if (!MO.isReg() || !MO.readsReg())
+            continue;
+          unsigned Reg = MO.getReg();
+          if (TargetRegisterInfo::isVirtualRegister(Reg)) {
+            unsigned SReg = scavengeVReg(MRI, *RS, Reg, true);
+            RS->setRegUsed(SReg);
+          }
+        }
+      }
 
+      // Look for unassigned vregs in the defs of *I.
+      LastIterationHadVRegUses = false;
       const MachineInstr &MI = *I;
-      MachineBasicBlock::iterator J = std::next(I);
-      MachineBasicBlock::iterator P =
-                         I == MBB.begin() ? MachineBasicBlock::iterator(nullptr)
-                                          : std::prev(I);
-
-      // RS should process this instruction before we might scavenge at this
-      // location. This is because we might be replacing a virtual register
-      // defined by this instruction, and if so, registers killed by this
-      // instruction are available, and defined registers are not.
-      RS->forward(I);
-
       for (const MachineOperand &MO : MI.operands()) {
         if (!MO.isReg())
           continue;
         unsigned Reg = MO.getReg();
         if (!TargetRegisterInfo::isVirtualRegister(Reg))
           continue;
-
-        // When we first encounter a new virtual register, it
-        // must be a definition.
-        assert(MO.isDef() && "frame index virtual missing def!");
-        // Scavenge a new scratch register
-        const TargetRegisterClass *RC = MRI.getRegClass(Reg);
-        unsigned ScratchReg = RS->scavengeRegister(RC, J, SPAdj);
-
-        ++NumScavengedRegs;
-
-        // Replace this reference to the virtual register with the
-        // scratch register.
-        assert(ScratchReg && "Missing scratch register!");
-        MRI.replaceRegWith(Reg, ScratchReg);
-
-        // Because this instruction was processed by the RS before this
-        // register was allocated, make sure that the RS now records the
-        // register as being used.
-        RS->setRegUsed(ScratchReg);
-      }
-
-      // If the scavenger needed to use one of its spill slots, the
-      // spill code will have been inserted in between I and J. This is a
-      // problem because we need the spill code before I: Move I to just
-      // prior to J.
-      if (I != std::prev(J)) {
-        MBB.splice(J, &MBB, I);
-
-        // Before we move I, we need to prepare the RS to visit I again.
-        // Specifically, RS will assert if it sees uses of registers that
-        // it believes are undefined. Because we have already processed
-        // register kills in I, when it visits I again, it will believe that
-        // those registers are undefined. To avoid this situation, unprocess
-        // the instruction I.
-        assert(RS->getCurrentPosition() == I &&
-          "The register scavenger has an unexpected position");
-        I = P;
-        RS->unprocess(P);
-      } else
-        ++I;
+        // We have to look at all operands anyway so we can precalculate here
+        // whether there is a reading operand. This allows use to skip the use
+        // step in the next iteration if there was none.
+        if (MO.readsReg())
+          LastIterationHadVRegUses = true;
+        if (MO.isDef())
+          scavengeVReg(MRI, *RS, Reg, false);
+      }
     }
   }
 }

lib/CodeGen/RegisterScavenging.cpp

if (MO.isReg() && MO.readsReg()) {
       unsigned Reg = MO.getReg();
       if (!Reg || TargetRegisterInfo::isVirtualRegister(Reg) ||
           isReserved(Reg))
         continue;
       removeRegUnits(RegUnitsAvailable, Reg);
     }
   }
 
+  // Expire scavenge spill frameindex uses.
+  for (ScavengedInfo &I : Scavenged) {
+    if (I.Restore == &MI) {
+      I.Reg = 0;
+      I.Restore = nullptr;
+    }
+  }
+
   if (MBBI == MBB->begin()) {
     MBBI = MachineBasicBlock::iterator(nullptr);
     Tracking = false;
   } else
     --MBBI;
 }
 
 bool RegScavenger::isRegUsed(unsigned Reg, bool includeReserved) const {
unsigned RegScavenger::findSurvivorReg(MachineBasicBlock::iterator StartMI,
   assert(RestorePointMI != StartMI &&
          "No available scavenger restore location!");
 
   // We ran out of candidates, so stop the search.
   UseMI = RestorePointMI;
   return Survivor;
 }
 
+static std::pair<unsigned, MachineBasicBlock::iterator>
+findSurvivorBackwards(const TargetRegisterInfo &TRI,
+    MachineBasicBlock::iterator From, MachineBasicBlock::iterator To,
+    BitVector &Available, BitVector &Candidates) {
+  bool FoundTo = false;
+  unsigned Survivor = 0;
+  MachineBasicBlock::iterator Pos;
+  MachineBasicBlock &MBB = *From->getParent();
+  MachineBasicBlock::iterator I = From;
+  unsigned InstrLimit = 25;
+  unsigned InstrCountDown = InstrLimit;
+  for (;;) {
+    const MachineInstr &MI = *I;
+    if (MI.isDebugValue())
+      continue;
+
+    // Remove any candidates touched by instruction.
+    bool FoundVReg = false;
+    for (const MachineOperand &MO : MI.operands()) {
+      if (MO.isRegMask()) {
+        Candidates.clearBitsNotInMask(MO.getRegMask());
+        continue;
+      }
+      if (!MO.isReg() || MO.isUndef())
+        continue;
+      unsigned Reg = MO.getReg();
+      if (TargetRegisterInfo::isVirtualRegister(Reg)) {
+        FoundVReg = true;
+      } else if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
+        for (MCRegAliasIterator AI(Reg, &TRI, true); AI.isValid(); ++AI)
+          Candidates.reset(*AI);
+      }
+    }
+
+    if (I == To) {
+      // If one of the available registers survived this long take it.
+      Available &= Candidates;
+      int Reg = Available.find_first();
+      if (Reg != -1)
+        return std::make_pair(Reg, MBB.end());
+      // Otherwise we will continue up to InstrLimit instructions to fine
+      // the register which is not defined/used for the longest time.
+      FoundTo = true;
+      Pos = To;
+    }
+    if (FoundTo) {
+      if (Survivor == 0 || !Candidates.test(Survivor)) {
+        int Reg = Candidates.find_first();
+        if (Reg == -1)
+          break;
+        Survivor = Reg;
+      }
+      if (--InstrCountDown == 0 || I == MBB.begin())
+        break;
+      if (FoundVReg) {
+        // We found a vreg, reset the InstrLimit counter.
+        InstrCountDown = InstrLimit;
+        Pos = I;
+      }
+    }
+    --I;
+  }
+
+  return std::make_pair(Survivor, Pos);
+}
+
 static unsigned getFrameIndexOperandNum(MachineInstr *MI) {
   unsigned i = 0;
   while (!MI->getOperand(i).isFI()) {
     ++i;
     assert(i < MI->getNumOperands() &&
            "Instr doesn't have FrameIndex operand!");
   }
   return i;
 }
 
-unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC,
-                                        MachineBasicBlock::iterator I,
-                                        int SPAdj) {
-  MachineInstr &MI = *I;
-  const MachineFunction &MF = *MI.getParent()->getParent();
-  // Consider all allocatable registers in the register class initially
-  BitVector Candidates = TRI->getAllocatableSet(MF, RC);
-
-  // Exclude all the registers being used by the instruction.
-  for (const MachineOperand &MO : MI.operands()) {
-    if (MO.isReg() && MO.getReg() != 0 && !(MO.isUse() && MO.isUndef()) &&
-        !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
-      Candidates.reset(MO.getReg());
-  }
-
-  // Try to find a register that's unused if there is one, as then we won't
-  // have to spill.
-  BitVector Available = getRegsAvailable(RC);
-  Available &= Candidates;
-  if (Available.any())
-    Candidates = Available;
-
-  // Find the register whose use is furthest away.
-  MachineBasicBlock::iterator UseMI;
-  unsigned SReg = findSurvivorReg(I, Candidates, 25, UseMI);
-
-  // If we found an unused register there is no reason to spill it.
-  if (!isRegUsed(SReg)) {
-    DEBUG(dbgs() << "Scavenged register: " << TRI->getName(SReg) << "\n");
-    return SReg;
-  }
-
+RegScavenger::ScavengedInfo &
+RegScavenger::spill(unsigned Reg, const TargetRegisterClass &RC, int SPAdj,
+                    MachineBasicBlock::iterator Before,
+                    MachineBasicBlock::iterator &UseMI) {
   // Find an available scavenging slot with size and alignment matching
   // the requirements of the class RC.
+  const MachineFunction &MF = *Before->getParent()->getParent();
   const MachineFrameInfo &MFI = *MF.getFrameInfo();
-  unsigned NeedSize = RC->getSize();
-  unsigned NeedAlign = RC->getAlignment();
+  unsigned NeedSize = RC.getSize();
+  unsigned NeedAlign = RC.getAlignment();
 
   unsigned SI = Scavenged.size(), Diff = UINT_MAX;
   int FIB = MFI.getObjectIndexBegin(), FIE = MFI.getObjectIndexEnd();
   for (unsigned I = 0; I < Scavenged.size(); ++I) {
     if (Scavenged[I].Reg != 0)
       continue;
     // Verify that this slot is valid for this register.
     int FI = Scavenged[I].FrameIndex;
RegScavenger::spill(unsigned Reg, const TargetRegisterClass &RC, int SPAdj,
 
   if (SI == Scavenged.size()) {
     // We need to scavenge a register but have no spill slot, the target
     // must know how to do it (if not, we'll assert below).
     Scavenged.push_back(ScavengedInfo(FIE));
   }
 
   // Avoid infinite regress
-  Scavenged[SI].Reg = SReg;
+  Scavenged[SI].Reg = Reg;
 
   // If the target knows how to save/restore the register, let it do so;
   // otherwise, use the emergency stack spill slot.
-  if (!TRI->saveScavengerRegister(*MBB, I, UseMI, RC, SReg)) {
-    // Spill the scavenged register before I.
+  if (!TRI->saveScavengerRegister(*MBB, Before, UseMI, &RC, Reg)) {
+    // Spill the scavenged register before \p Before.
     int FI = Scavenged[SI].FrameIndex;
     if (FI < FIB || FI >= FIE) {
       std::string Msg = std::string("Error while trying to spill ") +
-          TRI->getName(SReg) + " from class " + TRI->getRegClassName(RC) +
+          TRI->getName(Reg) + " from class " + TRI->getRegClassName(&RC) +
           ": Cannot scavenge register without an emergency spill slot!";
       report_fatal_error(Msg.c_str());
     }
-    TII->storeRegToStackSlot(*MBB, I, SReg, true, Scavenged[SI].FrameIndex,
-                             RC, TRI);
-    MachineBasicBlock::iterator II = std::prev(I);
+    TII->storeRegToStackSlot(*MBB, Before, Reg, true, Scavenged[SI].FrameIndex,
+                             &RC, TRI);
+    MachineBasicBlock::iterator II = std::prev(Before);
 
     unsigned FIOperandNum = getFrameIndexOperandNum(II);
     TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this);
 
     // Restore the scavenged register before its use (or first terminator).
-    TII->loadRegFromStackSlot(*MBB, UseMI, SReg, Scavenged[SI].FrameIndex,
-                              RC, TRI);
+    TII->loadRegFromStackSlot(*MBB, UseMI, Reg, Scavenged[SI].FrameIndex,
+                              &RC, TRI);
     II = std::prev(UseMI);
 
     FIOperandNum = getFrameIndexOperandNum(II);
     TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this);
   }
+  return Scavenged[SI];
+}
+
+unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC,
+                                        MachineBasicBlock::iterator I,
+                                        int SPAdj) {
+  MachineInstr &MI = *I;
+  const MachineFunction &MF = *MI.getParent()->getParent();
+  // Consider all allocatable registers in the register class initially
+  BitVector Candidates = TRI->getAllocatableSet(MF, RC);
+
+  // Exclude all the registers being used by the instruction.
+  for (const MachineOperand &MO : MI.operands()) {
+    if (MO.isReg() && MO.getReg() != 0 && !(MO.isUse() && MO.isUndef()) &&
+        !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
+      Candidates.reset(MO.getReg());
+  }
+
+  // Try to find a register that's unused if there is one, as then we won't
+  // have to spill.
+  BitVector Available = getRegsAvailable(RC);
+  Available &= Candidates;
+  if (Available.any())
+    Candidates = Available;
 
-  Scavenged[SI].Restore = std::prev(UseMI);
+  // Find the register whose use is furthest away.
+  MachineBasicBlock::iterator UseMI;
+  unsigned SReg = findSurvivorReg(I, Candidates, 25, UseMI);
+
+  // If we found an unused register there is no reason to spill it.
+  if (!isRegUsed(SReg)) {
+    DEBUG(dbgs() << "Scavenged register: " << TRI->getName(SReg) << "\n");
+    return SReg;
+  }
 
-  // Doing this here leads to infinite regress.
-  // Scavenged[SI].Reg = SReg;
+  ScavengedInfo &Scavenged = spill(SReg, *RC, SPAdj, I, UseMI);
+  Scavenged.Restore = std::prev(UseMI);
 
   DEBUG(dbgs() << "Scavenged register (with spill): " << TRI->getName(SReg) <<
         "\n");
 
   return SReg;
 }
+
+unsigned RegScavenger::scavengeRegisterBackwards(const TargetRegisterClass &RC,
+                                                 MachineBasicBlock::iterator To,
+                                                 bool RestoreAfter, int SPAdj) {
+  const MachineBasicBlock &MBB = *To->getParent();
+  const MachineFunction &MF = *MBB.getParent();
+  // Consider all allocatable registers in the register class initially
+  BitVector Candidates = TRI->getAllocatableSet(MF, &RC);
+
+  // Try to find a register that's unused if there is one, as then we won't
+  // have to spill.
+  BitVector Available = getRegsAvailable(&RC);
+
+  // Find the register whose use is furthest away.
+  MachineBasicBlock::iterator UseMI;
+  std::pair<unsigned, MachineBasicBlock::iterator> P =
+      findSurvivorBackwards(*TRI, MBBI, To, Available, Candidates);
+  unsigned Reg = P.first;
+  assert(Reg != 0 && "No register left to scavenge!");
+  // Found an available register?
+  if (!Available.test(Reg)) {
+    MachineBasicBlock::iterator ReloadBefore =
+      RestoreAfter ? std::next(MBBI) : MBBI;
+    DEBUG(dbgs() << "Reload before: " << *ReloadBefore << '\n');
+    ScavengedInfo &Scavenged = spill(Reg, RC, SPAdj, P.second, ReloadBefore);
+    Scavenged.Restore = std::prev(P.second);
+    addRegUnits(RegUnitsAvailable, Reg);
+    DEBUG(dbgs() << "Scavenged register with spill: " << PrintReg(Reg, TRI)
+          << " until " << *P.second);
+  } else {
+    DEBUG(dbgs() << "Scavenged free register: " << PrintReg(Reg, TRI) << '\n');
+  }
+  return Reg;
+}

test/CodeGen/AMDGPU/captured-frame-index.ll

define void @stored_fi_to_global_2_small_objects(float* addrspace(1)* %ptr) #0 {
   store volatile float 0.0, float *%tmp1
   store volatile float 0.0, float *%tmp2
   store volatile float* %tmp1, float* addrspace(1)* %ptr
   store volatile float* %tmp2, float* addrspace(1)* %ptr
   ret void
 }
 
 ; GCN-LABEL: {{^}}stored_fi_to_global_huge_frame_offset:
-; GCN: s_add_i32 [[BASE_1_OFF_0:s[0-9]+]], 0, 0x3ffc
-; GCN: v_mov_b32_e32 [[BASE_0:v[0-9]+]], 0{{$}}
+; GCN-DAG: s_add_i32 [[BASE_1_OFF_0:s[0-9]+]], 0, 0x3ffc
+; GCN-DAG: v_mov_b32_e32 [[BASE_0:v[0-9]+]], 0{{$}}
 ; GCN: buffer_store_dword [[BASE_0]], v{{[0-9]+}}, s{{\[[0-9]+:[0-9]+\]}}, s{{[0-9]+}} offen
 
 ; GCN: v_mov_b32_e32 [[V_BASE_1_OFF_0:v[0-9]+]], [[BASE_1_OFF_0]]
 ; GCN: v_mov_b32_e32 [[K:v[0-9]+]], 0x3e7{{$}}
 ; GCN: s_add_i32 [[BASE_1_OFF_1:s[0-9]+]], 0, 56
 ; GCN: buffer_store_dword [[K]], [[V_BASE_1_OFF_0]], s{{\[[0-9]+:[0-9]+\]}}, s{{[0-9]+}} offen{{$}}
 
 ; GCN: v_mov_b32_e32 [[V_BASE_1_OFF_1:v[0-9]+]], [[BASE_1_OFF_1]]

test/CodeGen/Mips/emergency-spill-slot-near-fp.ll

 ; Check that register scavenging spill slot is close to $fp.
 ; RUN: llc -march=mipsel -O0 -relocation-model=pic < %s | FileCheck %s
+; Disabled. Looks like the new register scavenging code can generate code
+; without an emergency spillslot here.
+; XFAIL: *
 
 ; CHECK: sw ${{.*}}, 8($sp)
 ; CHECK: lw ${{.*}}, 8($sp)
 
 define i32 @main(i32 signext %argc, i8** %argv) #0 {
 entry:
   %retval = alloca i32, align 4
   %argc.addr = alloca i32, align 4

test/CodeGen/PowerPC/dyn-alloca-aligned.ll

entry:
   store i32 %2, i32* %arrayidx3, align 4
   call void @bar(i32* %vla1, i32* %vla) #0
   ret void
 
 ; CHECK-LABEL: @goo
 
 ; CHECK-DAG: li [[REG1:[0-9]+]], -128
 ; CHECK-DAG: neg [[REG2:[0-9]+]],
-; CHECK: and [[REG1]], [[REG2]], [[REG1]]
-; CHECK: stdux {{[0-9]+}}, 1, [[REG1]]
+; CHECK: and [[REG3:[0-9]+]], [[REG2]], [[REG1]]
+; CHECK: stdux {{[0-9]+}}, 1, [[REG3]]
 
 ; CHECK: blr
 
 }
 
 attributes #0 = { nounwind }

test/CodeGen/SystemZ/frame-13.ll

 
 ; Repeat f2 in a case that needs the emergency spill slots (because all
 ; call-clobbered registers are live and no call-saved ones have been
 ; allocated).
 define void @f10(i32 *%vptr) {
 ; CHECK-NOFP-LABEL: f10:
 ; CHECK-NOFP: stg [[REGISTER:%r[1-9][0-4]?]], [[OFFSET:160|168]](%r15)
 ; CHECK-NOFP: lay [[REGISTER]], 4096(%r15)
-; CHECK-NOFP: mvhi 0([[REGISTER]]), 42
 ; CHECK-NOFP: lg [[REGISTER]], [[OFFSET]](%r15)
+; CHECK-NOFP: mvhi 0([[REGISTER]]), 42
 ; CHECK-NOFP: br %r14
 ;
 ; CHECK-FP-LABEL: f10:
 ; CHECK-FP: stg [[REGISTER:%r[1-9][0-4]?]], [[OFFSET:160|168]](%r11)
 ; CHECK-FP: lay [[REGISTER]], 4096(%r11)
-; CHECK-FP: mvhi 0([[REGISTER]]), 42
 ; CHECK-FP: lg [[REGISTER]], [[OFFSET]](%r11)
+; CHECK-FP: mvhi 0([[REGISTER]]), 42
 ; CHECK-FP: br %r14
   %i0 = load volatile i32 , i32 *%vptr
   %i1 = load volatile i32 , i32 *%vptr
   %i3 = load volatile i32 , i32 *%vptr
   %i4 = load volatile i32 , i32 *%vptr
   %i5 = load volatile i32 , i32 *%vptr
   %region1 = alloca [978 x i32], align 8
   %region2 = alloca [978 x i32], align 8

 ; NOFP case needs are the emergency ones, so the offsets are the same as for f2.
 ; The FP case needs to spill an extra register and is too dependent on
 ; register allocation heuristics for a stable test.
 define void @f11(i32 *%vptr) {
 ; CHECK-NOFP-LABEL: f11:
 ; CHECK-NOFP: stmg %r6, %r15,
 ; CHECK-NOFP: stg [[REGISTER:%r[1-9][0-4]?]], [[OFFSET:160|168]](%r15)
 ; CHECK-NOFP: lay [[REGISTER]], 4096(%r15)
-; CHECK-NOFP: mvhi 0([[REGISTER]]), 42
 ; CHECK-NOFP: lg [[REGISTER]], [[OFFSET]](%r15)
+; CHECK-NOFP: mvhi 0([[REGISTER]]), 42
 ; CHECK-NOFP: lmg %r6, %r15,
 ; CHECK-NOFP: br %r14
   %i0 = load volatile i32 , i32 *%vptr
   %i1 = load volatile i32 , i32 *%vptr
   %i3 = load volatile i32 , i32 *%vptr
   %i4 = load volatile i32 , i32 *%vptr
   %i5 = load volatile i32 , i32 *%vptr
   %i6 = load volatile i32 , i32 *%vptr

test/CodeGen/SystemZ/frame-14.ll

 ; Repeat f4 in a case that needs the emergency spill slots (because all
 ; call-clobbered registers are live and no call-saved ones have been
 ; allocated).
 define void @f10(i32 *%vptr) {
 ; CHECK-NOFP-LABEL: f10:
 ; CHECK-NOFP: stg [[REGISTER:%r[1-9][0-4]?]], [[OFFSET:160|168]](%r15)
 ; CHECK-NOFP: llilh [[REGISTER]], 8
 ; CHECK-NOFP: agr [[REGISTER]], %r15
-; CHECK-NOFP: mvi 0([[REGISTER]]), 42
 ; CHECK-NOFP: lg [[REGISTER]], [[OFFSET]](%r15)
+; CHECK-NOFP: mvi 0([[REGISTER]]), 42
 ; CHECK-NOFP: br %r14
 ;
 ; CHECK-FP-LABEL: f10:
 ; CHECK-FP: stg [[REGISTER:%r[1-9][0-4]?]], [[OFFSET:160|168]](%r11)
 ; CHECK-FP: llilh [[REGISTER]], 8
 ; CHECK-FP: agr [[REGISTER]], %r11
-; CHECK-FP: mvi 0([[REGISTER]]), 42
 ; CHECK-FP: lg [[REGISTER]], [[OFFSET]](%r11)
+; CHECK-FP: mvi 0([[REGISTER]]), 42
 ; CHECK-FP: br %r14
   %i0 = load volatile i32 , i32 *%vptr
   %i1 = load volatile i32 , i32 *%vptr
   %i3 = load volatile i32 , i32 *%vptr
   %i4 = load volatile i32 , i32 *%vptr
   %i5 = load volatile i32 , i32 *%vptr
   %region1 = alloca [524104 x i8], align 8
   %region2 = alloca [524104 x i8], align 8

 ; The FP case needs to spill an extra register and is too dependent on
 ; register allocation heuristics for a stable test.
 define void @f11(i32 *%vptr) {
 ; CHECK-NOFP-LABEL: f11:
 ; CHECK-NOFP: stmg %r6, %r15,
 ; CHECK-NOFP: stg [[REGISTER:%r[1-9][0-4]?]], [[OFFSET:160|168]](%r15)
 ; CHECK-NOFP: llilh [[REGISTER]], 8
 ; CHECK-NOFP: agr [[REGISTER]], %r15
-; CHECK-NOFP: mvi 0([[REGISTER]]), 42
 ; CHECK-NOFP: lg [[REGISTER]], [[OFFSET]](%r15)
+; CHECK-NOFP: mvi 0([[REGISTER]]), 42
 ; CHECK-NOFP: lmg %r6, %r15,
 ; CHECK-NOFP: br %r14
   %i0 = load volatile i32 , i32 *%vptr
   %i1 = load volatile i32 , i32 *%vptr
   %i3 = load volatile i32 , i32 *%vptr
   %i4 = load volatile i32 , i32 *%vptr
   %i5 = load volatile i32 , i32 *%vptr
   %i6 = load volatile i32 , i32 *%vptr

test/CodeGen/SystemZ/frame-15.ll

 ; Repeat f2 in a case that needs the emergency spill slots, because all
 ; call-clobbered and allocated call-saved registers are live.  Note that
 ; %vptr and %dst are copied to call-saved registers, freeing up %r2 and
 ; %r3 during the main test.
 define void @f10(i32 *%vptr, double *%dst) {
 ; CHECK-NOFP-LABEL: f10:
 ; CHECK-NOFP: stg [[REGISTER:%r[1-9][0-4]?]], [[OFFSET:160|168]](%r15)
 ; CHECK-NOFP: lghi [[REGISTER]], 4096
-; CHECK-NOFP: ldeb {{%f[0-7]}}, 0([[REGISTER]],%r15)
 ; CHECK-NOFP: lg [[REGISTER]], [[OFFSET]](%r15)
+; CHECK-NOFP: ldeb {{%f[0-7]}}, 0([[REGISTER]],%r15)
 ; CHECK-NOFP: br %r14
 ;
 ; CHECK-FP-LABEL: f10:
 ; CHECK-FP: stg [[REGISTER:%r[1-9][0-4]?]], [[OFFSET:160|168]](%r11)
 ; CHECK-FP: lghi [[REGISTER]], 4096
-; CHECK-FP: ldeb {{%f[0-7]}}, 0([[REGISTER]],%r11)
 ; CHECK-FP: lg [[REGISTER]], [[OFFSET]](%r11)
+; CHECK-FP: ldeb {{%f[0-7]}}, 0([[REGISTER]],%r11)
 ; CHECK-FP: br %r14
   %region1 = alloca [978 x float], align 8
   %region2 = alloca [978 x float], align 8
   %start1 = getelementptr inbounds [978 x float], [978 x float]* %region1, i64 0, i64 0
   %start2 = getelementptr inbounds [978 x float], [978 x float]* %region2, i64 0, i64 0
   call void @foo(float *%start1, float *%start2)
   %ptr1 = getelementptr inbounds [978 x float], [978 x float]* %region1, i64 0, i64 2
   %ptr2 = getelementptr inbounds [978 x float], [978 x float]* %region2, i64 0, i64 2

test/CodeGen/SystemZ/frame-16.ll

 
 ; Repeat f4 in a case that needs the emergency spill slots (because all
 ; call-clobbered registers are live and no call-saved ones have been
 ; allocated).
 define void @f10(i32 *%vptr, i8 %byte) {
 ; CHECK-NOFP-LABEL: f10:
 ; CHECK-NOFP: stg [[REGISTER:%r[1-9][0-4]?]], [[OFFSET:160|168]](%r15)
 ; CHECK-NOFP: llilh [[REGISTER]], 8
-; CHECK-NOFP: stc %r3, 0([[REGISTER]],%r15)
 ; CHECK-NOFP: lg [[REGISTER]], [[OFFSET]](%r15)
+; CHECK-NOFP: stc %r3, 0([[REGISTER]],%r15)
 ; CHECK-NOFP: br %r14
 ;
 ; CHECK-FP-LABEL: f10:
 ; CHECK-FP: stg [[REGISTER:%r[1-9][0-4]?]], [[OFFSET:160|168]](%r11)
 ; CHECK-FP: llilh [[REGISTER]], 8
-; CHECK-FP: stc %r3, 0([[REGISTER]],%r11)
 ; CHECK-FP: lg [[REGISTER]], [[OFFSET]](%r11)
+; CHECK-FP: stc %r3, 0([[REGISTER]],%r11)
 ; CHECK-FP: br %r14
   %i0 = load volatile i32 , i32 *%vptr
   %i1 = load volatile i32 , i32 *%vptr
   %i4 = load volatile i32 , i32 *%vptr
   %i5 = load volatile i32 , i32 *%vptr
   %region1 = alloca [524104 x i8], align 8
   %region2 = alloca [524104 x i8], align 8
   %ptr1 = getelementptr inbounds [524104 x i8], [524104 x i8]* %region1, i64 0, i64 8

 ; NOFP case needs are the emergency ones, so the offsets are the same as for f4.
 ; However, the FP case uses %r11 as the frame pointer and must therefore
 ; spill a second register.  This leads to an extra displacement of 8.
 define void @f11(i32 *%vptr, i8 %byte) {
 ; CHECK-NOFP-LABEL: f11:
 ; CHECK-NOFP: stmg %r6, %r15,
 ; CHECK-NOFP: stg [[REGISTER:%r[1-9][0-4]?]], [[OFFSET:160|168]](%r15)
 ; CHECK-NOFP: llilh [[REGISTER]], 8
-; CHECK-NOFP: stc %r3, 0([[REGISTER]],%r15)
 ; CHECK-NOFP: lg [[REGISTER]], [[OFFSET]](%r15)
+; CHECK-NOFP: stc %r3, 0([[REGISTER]],%r15)
 ; CHECK-NOFP: lmg %r6, %r15,
 ; CHECK-NOFP: br %r14
 ;
 ; CHECK-FP-LABEL: f11:
 ; CHECK-FP: stmg %r6, %r15,
 ; CHECK-FP: stg [[REGISTER:%r[1-9][0-4]?]], [[OFFSET:160|168]](%r11)
 ; CHECK-FP: llilh [[REGISTER]], 8
-; CHECK-FP: stc %r3, 8([[REGISTER]],%r11)
 ; CHECK-FP: lg [[REGISTER]], [[OFFSET]](%r11)
+; CHECK-FP: stc %r3, 8([[REGISTER]],%r11)
 ; CHECK-FP: lmg %r6, %r15,
 ; CHECK-FP: br %r14
   %i0 = load volatile i32 , i32 *%vptr
   %i1 = load volatile i32 , i32 *%vptr
   %i4 = load volatile i32 , i32 *%vptr
   %i5 = load volatile i32 , i32 *%vptr
   %i6 = load volatile i32 , i32 *%vptr
   %i7 = load volatile i32 , i32 *%vptr

test/CodeGen/Thumb/large-stack.ll

; IOS: mov sp, r4
     %tmp = alloca [ 1528 x i8 ] , align 4
     ret void
 }
 
 define i32 @test3() {
 ; CHECK-LABEL: test3:
 ; CHECK: ldr [[TEMP:r[0-7]]],
 ; CHECK: add sp, [[TEMP]]
-; CHECK: ldr [[TEMP]],
-; CHECK: add [[TEMP]], sp
+; CHECK: ldr [[TEMP2:r[0-7]]],
+; CHECK: add [[TEMP2]], sp
 ; EABI: ldr [[TEMP:r[0-7]]],
 ; EABI: add sp, [[TEMP]]
 ; IOS: subs r4, r7, #4
 ; IOS: mov sp, r4
     %retval = alloca i32, align 4
     %tmp = alloca i32, align 4
     %a = alloca [805306369 x i8], align 16
     store i32 0, i32* %tmp