RegScavenging: Add scavengeRegisterBackwards()

[MatzeB]

Summary

This is a rebased version of r276044 / http://reviews.llvm.org/D21885 to current trunk. I had to initially revert, because the commit triggered failures on powerpc (http://lab.llvm.org:8011/builders/clang-ppc64le-linux-lnt/builds/3648).

I need help debugging this! The failing tests are

MultiSource/Benchmarks/mediabench/gsm/toast
SingleSource/Benchmarks/Adobe-C++/loop_unroll.cpp

in the test-suite. Given that scavenging happens on all targets in many situations and those two tests on powerpc is the only thing that breaks, I suspect that it is a problem with the commit itself but some pre-existing problem getting triggered, I have no idea what though.
I checked my commit multiple times and dived into assembly diffs with/without this patch without seeing the problem. I need someone with actual access to a Power system to debug this (at least to the point where he can tell me which instructions are generated wrong and why they are wrong).

Original commit message:

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.

[uweigand]

I haven't looked at the PowerPC failures. However, the changes you're doing to the SystemZ test cases seem already incorrect.

Those tests all verify an instruction sequence that originally looks like:

spill REGISTER to the stack
def REGISTER
use REGISTER
restore REGISTER from stack

You change them to do instead:

spill REGISTER to the stack
def REGISTER
restore REGISTER from stack
use REGISTER

which means of course that the use now gets the wrong register contents ...

Am I missing something here?

[kbarton]

Do you still have problems on PPC?
Did you get access to a Power system so you can debug?

[nemanjai]

Is this patch dead in the water now? Is there a replacement? Should this be abandoned/closed?

[MatzeB]

In D23097#722041, @nemanjai wrote:

Is this patch dead in the water now? Is there a replacement? Should this be abandoned/closed?

I'd really like to move forward with this, but am still stuck debugging the ppc bot issues. I tried with the login I was provided with but couldn't reproduce the bot problem there. I did not find the time to dig into why I couldn't reproduce, and still feel extremely uncomfortable debugging for a platform I am not familiar with.

[MatzeB]

In D23097#722642, @MatzeB wrote:

In D23097#722041, @nemanjai wrote:

Is this patch dead in the water now? Is there a replacement? Should this be abandoned/closed?

I'd really like to move forward with this, but am still stuck debugging the ppc bot issues. I tried with the login I was provided with but couldn't reproduce the bot problem there. I did not find the time to dig into why I couldn't reproduce, and still feel extremely uncomfortable debugging for a platform I am not familiar with.

Of course given the fact that this is just improving our infrastructure but not adding any new features or fixing bugs, I can't really find the time lately to work on it and there is zero progress...

[MatzeB]

This landed a while ago in r305625 (as part of D21885)

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 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);
+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;
 
-  // Exclude all the registers being used by the instruction.
+    // Remove any candidates touched by instruction.
+    bool FoundVReg = false;
     for (const MachineOperand &MO : MI.operands()) {
-    if (MO.isReg() && MO.getReg() != 0 && !(MO.isUse() && MO.isUndef()) &&
-        !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
-      Candidates.reset(MO.getReg());
+      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);
+      }
     }
 
-  // Try to find a register that's unused if there is one, as then we won't
-  // have to spill.
-  BitVector Available = getRegsAvailable(RC);
+    if (I == To) {
+      // If one of the available registers survived this long take it.
       Available &= Candidates;
-  if (Available.any())
-    Candidates = Available;
+      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;
+  }
 
-  // Find the register whose use is furthest away.
-  MachineBasicBlock::iterator UseMI;
-  unsigned SReg = findSurvivorReg(I, Candidates, 25, UseMI);
+  return std::make_pair(Survivor, Pos);
+}
 
-  // 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;
-  }
+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;
 
+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];
+}
 
-  Scavenged[SI].Restore = &*std::prev(UseMI);
+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);
 
-  // Doing this here leads to infinite regress.
-  // Scavenged[SI].Reg = SReg;
+  // 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;
+  }
+
+  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
+; Check that register scavenging spill slot is close to $fp.
+target triple="mipsel--"
 
-; CHECK: sw ${{.*}}, 8($sp)
-; CHECK: lw ${{.*}}, 8($sp)
+@var = external global i32
+@ptrvar = external global i8*
 
-define i32 @main(i32 signext %argc, i8** %argv) #0 {
-entry:
-  %retval = alloca i32, align 4
-  %argc.addr = alloca i32, align 4
-  %argv.addr = alloca i8**, align 4
-  %v0 = alloca <16 x i8>, align 16
-  %.compoundliteral = alloca <16 x i8>, align 16
-  %v1 = alloca <16 x i8>, align 16
-  %.compoundliteral1 = alloca <16 x i8>, align 16
-  %unused_variable = alloca [16384 x i32], align 4
-  %result = alloca <16 x i8>, align 16
-  store i32 0, i32* %retval
-  store i32 %argc, i32* %argc.addr, align 4
-  store i8** %argv, i8*** %argv.addr, align 4
-  store <16 x i8> <i8 1, i8 2, i8 3, i8 4, i8 5, i8 6, i8 7, i8 8, i8 9, i8 10, i8 11, i8 12, i8 13, i8 14, i8 15, i8 16>, <16 x i8>* %.compoundliteral
-  %0 = load <16 x i8>, <16 x i8>* %.compoundliteral
-  store <16 x i8> %0, <16 x i8>* %v0, align 16
-  store <16 x i8> zeroinitializer, <16 x i8>* %.compoundliteral1
-  %1 = load <16 x i8>, <16 x i8>* %.compoundliteral1
-  store <16 x i8> %1, <16 x i8>* %v1, align 16
-  %2 = load <16 x i8>, <16 x i8>* %v0, align 16
-  %3 = load <16 x i8>, <16 x i8>* %v1, align 16
-  %mul = mul <16 x i8> %2, %3
-  store <16 x i8> %mul, <16 x i8>* %result, align 16
-  ret i32 0
-}
+; CHECK-LABEL: func:
+define void @func() {
+  %space = alloca i32, align 4
+  %stackspace = alloca[16384 x i32], align 4
+
+  ; ensure stackspace is not optimized out
+  %stackspace_casted = bitcast [16384 x i32]* %stackspace to i8*
+  store volatile i8* %stackspace_casted, i8** @ptrvar
 
-attributes #0 = { noinline "no-frame-pointer-elim"="true" }
+  ; Load values to increase register pressure.
+  %v0 = load volatile i32, i32* @var
+  %v1 = load volatile i32, i32* @var
+  %v2 = load volatile i32, i32* @var
+  %v3 = load volatile i32, i32* @var
+  %v4 = load volatile i32, i32* @var
+  %v5 = load volatile i32, i32* @var
+  %v6 = load volatile i32, i32* @var
+  %v7 = load volatile i32, i32* @var
+  %v8 = load volatile i32, i32* @var
+  %v9 = load volatile i32, i32* @var
+  %v10 = load volatile i32, i32* @var
+  %v11 = load volatile i32, i32* @var
+  %v12 = load volatile i32, i32* @var
+  %v13 = load volatile i32, i32* @var
+  %v14 = load volatile i32, i32* @var
+  %v15 = load volatile i32, i32* @var
+  %v16 = load volatile i32, i32* @var
+
+  ; Computing a stack-relative values needs an additional register.
+  ; We should get an emergency spill/reload for this.
+  ; CHECK: sw ${{.*}}, 0($sp)
+  ; CHECK: lw ${{.*}}, 0($sp)
+  store volatile i32 %v0, i32* %space
+
+  ; store values so they are used.
+  store volatile i32 %v0, i32* @var
+  store volatile i32 %v1, i32* @var
+  store volatile i32 %v2, i32* @var
+  store volatile i32 %v3, i32* @var
+  store volatile i32 %v4, i32* @var
+  store volatile i32 %v5, i32* @var
+  store volatile i32 %v6, i32* @var
+  store volatile i32 %v7, i32* @var
+  store volatile i32 %v8, i32* @var
+  store volatile i32 %v9, i32* @var
+  store volatile i32 %v10, i32* @var
+  store volatile i32 %v11, i32* @var
+  store volatile i32 %v12, i32* @var
+  store volatile i32 %v13, i32* @var
+  store volatile i32 %v14, i32* @var
+  store volatile i32 %v15, i32* @var
+  store volatile i32 %v16, i32* @var
+
+  ret void
+}

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