Revert "RegScavenging: Add scavengeRegisterBackwards()"

The ppc64 multistage bot fails on this.

This reverts commit r279124.

Also Revert "CodeGen: Add/Factor out LiveRegUnits class; NFCI" because it depends on the previous change
This reverts commit r279171.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@279199 91177308-0d34-0410-b5e6-96231b3b80d8

10 files changed, 209 insertions, 551 deletions

diff --git a/include/llvm/CodeGen/LiveRegUnits.h b/include/llvm/CodeGen/LiveRegUnits.h
deleted file mode 100644
index b6bb8c69d1e..00000000000
--- a/include/llvm/CodeGen/LiveRegUnits.h
+++ /dev/null
@@ -1,116 +0,0 @@
-//===- llvm/CodeGen/LiveRegUnits.h - Register Unit Set ----------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-/// \file
-/// A set of register units. It is intended for register liveness tracking.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_CODEGEN_LIVEREGUNITS_H
-#define LLVM_CODEGEN_LIVEREGUNITS_H
-
-#include "llvm/ADT/BitVector.h"
-#include "llvm/Target/TargetRegisterInfo.h"
-
-namespace llvm {
-
-class MachineInstr;
-class MachineBasicBlock;
-
-/// A set of register units used to track register liveness.
-class LiveRegUnits {
-  const TargetRegisterInfo *TRI;
-  BitVector Units;
-
-public:
-  /// Constructs a new empty LiveRegUnits set.
-  LiveRegUnits() : TRI(nullptr) {}
-
-  /// Constructs and initialize an empty LiveRegUnits set.
-  LiveRegUnits(const TargetRegisterInfo &TRI) {
-    init(TRI);
-  }
-
-  /// Initialize and clear the set.
-  void init(const TargetRegisterInfo &TRI) {
-    this->TRI = &TRI;
-    Units.reset();
-    Units.resize(TRI.getNumRegUnits());
-  }
-
-  /// Clears the set.
-  void clear() { Units.reset(); }
-
-  /// Returns true if the set is empty.
-  bool empty() const { return Units.empty(); }
-
-  /// Adds register units covered by physical register \p Reg.
-  void addReg(unsigned Reg) {
-    for (MCRegUnitIterator Unit(Reg, TRI); Unit.isValid(); ++Unit)
-      Units.set(*Unit);
-  }
-
-  /// \brief Adds register units covered by physical register \p Reg that are
-  /// part of the lanemask \p Mask.
-  void addRegMasked(unsigned Reg, LaneBitmask Mask) {
-    for (MCRegUnitMaskIterator Unit(Reg, TRI); Unit.isValid(); ++Unit) {
-      LaneBitmask UnitMask = (*Unit).second;
-      if (UnitMask == 0 || (UnitMask & Mask) != 0)
-        Units.set((*Unit).first);
-    }
-  }
-
-  /// Removes all register units covered by physical register \p Reg.
-  void removeReg(unsigned Reg) {
-    for (MCRegUnitIterator Unit(Reg, TRI); Unit.isValid(); ++Unit)
-      Units.reset(*Unit);
-  }
-
-  /// Removes register units not preserved by the regmask \p RegMask.
-  /// The regmask has the same format as the one in the RegMask machine operand.
-  void removeRegsNotPreserved(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) {
-      if (Units.test(*Unit))
-        return false;
-    }
-    return true;
-  }
-
-  /// Updates liveness when stepping backwards over the instruction \p MI.
-  void stepBackward(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
-  /// callee saved registers.
-  void addLiveOuts(const MachineBasicBlock &MBB);
-
-  /// Adds registers living into block \p MBB.
-  void addLiveIns(const MachineBasicBlock &MBB);
-
-  /// Adds all register units marked in the bitvector \p RegUnits.
-  void addUnits(const BitVector &RegUnits) {
-    Units |= RegUnits;
-  }
-  /// Removes all register units marked in the bitvector \p RegUnits.
-  void removeUnits(const BitVector &RegUnits) {
-    Units.reset(RegUnits);
-  }
-  /// Return the internal bitvector representation of the set.
-  const BitVector &getBitVector() const {
-    return Units;
-  }
-};
-
-} // namespace llvm
-
-#endif
diff --git a/include/llvm/CodeGen/RegisterScavenging.h b/include/llvm/CodeGen/RegisterScavenging.h
index 0b131a4acd7..efaba1757b5 100644
--- a/include/llvm/CodeGen/RegisterScavenging.h
+++ b/include/llvm/CodeGen/RegisterScavenging.h
@@ -19,7 +19,6 @@
 #define LLVM_CODEGEN_REGISTERSCAVENGING_H
 
 #include "llvm/ADT/BitVector.h"
-#include "llvm/CodeGen/LiveRegUnits.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 
@@ -59,7 +58,10 @@ class RegScavenger {
   /// A vector of information on scavenged registers.
   SmallVector<ScavengedInfo, 2> Scavenged;
 
-  LiveRegUnits LiveUnits;
+  /// The current state of each reg unit immediately before MBBI.
+  /// One bit per register unit. If bit is not set it means any
+  /// register containing that register unit is currently being used.
+  BitVector RegUnitsAvailable;
 
   // These BitVectors are only used internally to forward(). They are members
   // to avoid frequent reallocations.
@@ -155,24 +157,12 @@ public:
   /// 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 following 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:
@@ -181,11 +171,11 @@ private:
 
   /// setUsed / setUnused - Mark the state of one or a number of register units.
   ///
-  void setUsed(const BitVector &RegUnits) {
-    LiveUnits.addUnits(RegUnits);
+  void setUsed(BitVector &RegUnits) {
+    RegUnitsAvailable.reset(RegUnits);
   }
-  void setUnused(const BitVector &RegUnits) {
-    LiveUnits.removeUnits(RegUnits);
+  void setUnused(BitVector &RegUnits) {
+    RegUnitsAvailable |= RegUnits;
   }
 
   /// Processes the current instruction and fill the KillRegUnits and
@@ -212,12 +202,6 @@ private:
 
   /// 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
diff --git a/lib/CodeGen/CMakeLists.txt b/lib/CodeGen/CMakeLists.txt
index 7d390d8c938..f5224350c08 100644
--- a/lib/CodeGen/CMakeLists.txt
+++ b/lib/CodeGen/CMakeLists.txt
@@ -44,7 +44,6 @@ add_llvm_library(LLVMCodeGen
   LiveRangeCalc.cpp
   LiveRangeEdit.cpp
   LiveRegMatrix.cpp
-  LiveRegUnits.cpp
   LiveStackAnalysis.cpp
   LiveVariables.cpp
   LLVMTargetMachine.cpp
diff --git a/lib/CodeGen/LiveRegUnits.cpp b/lib/CodeGen/LiveRegUnits.cpp
deleted file mode 100644
index 14da799a63f..00000000000
--- a/lib/CodeGen/LiveRegUnits.cpp
+++ /dev/null
@@ -1,97 +0,0 @@
-//===--- LiveRegUnits.cpp - Register Unit Set -----------------------------===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-/// \file This file imlements the LiveRegUnits set.
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/CodeGen/LiveRegUnits.h"
-#include "llvm/CodeGen/MachineFrameInfo.h"
-#include "llvm/CodeGen/MachineFunction.h"
-#include "llvm/CodeGen/MachineInstrBundle.h"
-using namespace llvm;
-
-void LiveRegUnits::removeRegsNotPreserved(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.reset(U);
-    }
-  }
-}
-
-void LiveRegUnits::stepBackward(const MachineInstr &MI) {
-  // Remove defined registers and regmask kills from the set.
-  for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
-    if (O->isReg()) {
-      if (!O->isDef())
-        continue;
-      unsigned Reg = O->getReg();
-      if (!TargetRegisterInfo::isPhysicalRegister(Reg))
-        continue;
-      removeReg(Reg);
-    } else if (O->isRegMask())
-      removeRegsNotPreserved(O->getRegMask());
-  }
-
-  // Add uses to the set.
-  for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
-    if (!O->isReg() || !O->readsReg())
-      continue;
-    unsigned Reg = O->getReg();
-    if (!TargetRegisterInfo::isPhysicalRegister(Reg))
-      continue;
-    addReg(Reg);
-  }
-}
-
-/// 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())
-    LiveUnits.addRegMasked(LI.PhysReg, LI.LaneMask);
-}
-
-static void addLiveOuts(LiveRegUnits &LiveUnits, const MachineBasicBlock &MBB) {
-  // To get the live-outs we simply merge the live-ins of all successors.
-  for (const MachineBasicBlock *Succ : MBB.successors())
-    addLiveIns(LiveUnits, *Succ);
-}
-
-/// Add pristine registers to the given \p LiveUnits. This function removes
-/// actually saved callee save registers when \p InPrologueEpilogue is false.
-static void removeSavedRegs(LiveRegUnits &LiveUnits, const MachineFunction &MF,
-                            const MachineFrameInfo &MFI,
-                            const TargetRegisterInfo &TRI) {
-  for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
-    LiveUnits.removeReg(Info.getReg());
-}
-
-void LiveRegUnits::addLiveOuts(const MachineBasicBlock &MBB) {
-  const MachineFunction &MF = *MBB.getParent();
-  const MachineFrameInfo &MFI = MF.getFrameInfo();
-  if (MFI.isCalleeSavedInfoValid()) {
-    for (const MCPhysReg *I = TRI->getCalleeSavedRegs(&MF); *I; ++I)
-      addReg(*I);
-    if (!MBB.isReturnBlock())
-      removeSavedRegs(*this, MF, MFI, *TRI);
-  }
-  ::addLiveOuts(*this, MBB);
-}
-
-void LiveRegUnits::addLiveIns(const MachineBasicBlock &MBB) {
-  const MachineFunction &MF = *MBB.getParent();
-  const MachineFrameInfo &MFI = MF.getFrameInfo();
-  if (MFI.isCalleeSavedInfoValid()) {
-    for (const MCPhysReg *I = TRI->getCalleeSavedRegs(&MF); *I; ++I)
-      addReg(*I);
-    if (&MBB != &MF.front())
-      removeSavedRegs(*this, MF, MFI, *TRI);
-  }
-  ::addLiveIns(*this, MBB);
-}
diff --git a/lib/CodeGen/PrologEpilogInserter.cpp b/lib/CodeGen/PrologEpilogInserter.cpp
index 7faf245e20f..a167b3d1c91 100644
--- a/lib/CodeGen/PrologEpilogInserter.cpp
+++ b/lib/CodeGen/PrologEpilogInserter.cpp
@@ -41,7 +41,6 @@
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetRegisterInfo.h"
 #include "llvm/Target/TargetSubtargetInfo.h"
-#include <algorithm>
 #include <climits>
 
 using namespace llvm;
@@ -1146,55 +1145,6 @@ void PEI::replaceFrameIndices(MachineBasicBlock *BB, MachineFunction &Fn,
   }
 }
 
-/// 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.
@@ -1206,51 +1156,78 @@ static void
 doScavengeFrameVirtualRegs(MachineFunction &MF, RegScavenger *RS) {
   // Run through the instructions and find any virtual registers.
   MachineRegisterInfo &MRI = MF.getRegInfo();
-  const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
   for (MachineBasicBlock &MBB : MF) {
-    RS->enterBasicBlockEnd(MBB);
-
-    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).
-      if (LastIterationHadVRegUses) {
-        MachineBasicBlock::iterator N = std::next(I);
-        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);
-            N->addRegisterKilled(SReg, &TRI, false);
-            RS->setRegUsed(SReg);
-          }
-        }
-      }
+    RS->enterBasicBlock(MBB);
+
+    int SPAdj = 0;
+
+    // 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();
 
-      // 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;
-        // 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()) {
-          unsigned SReg = scavengeVReg(MRI, *RS, Reg, false);
-          I->addRegisterDead(SReg, &TRI, false);
-        }
+
+        // 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;
     }
   }
 }
diff --git a/lib/CodeGen/RegisterScavenging.cpp b/lib/CodeGen/RegisterScavenging.cpp
index cd088c78b49..953e5353df1 100644
--- a/lib/CodeGen/RegisterScavenging.cpp
+++ b/lib/CodeGen/RegisterScavenging.cpp
@@ -32,7 +32,11 @@ using namespace llvm;
 #define DEBUG_TYPE "reg-scavenging"
 
 void RegScavenger::setRegUsed(unsigned Reg, LaneBitmask LaneMask) {
-  LiveUnits.addRegMasked(Reg, LaneMask);
+  for (MCRegUnitMaskIterator RUI(Reg, TRI); RUI.isValid(); ++RUI) {
+    LaneBitmask UnitMask = (*RUI).second;
+    if (UnitMask == 0 || (LaneMask & UnitMask) != 0)
+      RegUnitsAvailable.reset((*RUI).first);
+  }
 }
 
 void RegScavenger::init(MachineBasicBlock &MBB) {
@@ -40,7 +44,6 @@ void RegScavenger::init(MachineBasicBlock &MBB) {
   TII = MF.getSubtarget().getInstrInfo();
   TRI = MF.getSubtarget().getRegisterInfo();
   MRI = &MF.getRegInfo();
-  LiveUnits.init(*TRI);
 
   assert((NumRegUnits == 0 || NumRegUnits == TRI->getNumRegUnits()) &&
          "Target changed?");
@@ -53,6 +56,7 @@ void RegScavenger::init(MachineBasicBlock &MBB) {
   // Self-initialize.
   if (!this->MBB) {
     NumRegUnits = TRI->getNumRegUnits();
+    RegUnitsAvailable.resize(NumRegUnits);
     KillRegUnits.resize(NumRegUnits);
     DefRegUnits.resize(NumRegUnits);
     TmpRegUnits.resize(NumRegUnits);
@@ -65,17 +69,32 @@ void RegScavenger::init(MachineBasicBlock &MBB) {
     I->Restore = nullptr;
   }
 
+  // All register units start out unused.
+  RegUnitsAvailable.set();
+
+  // Pristine CSRs are not available.
+  BitVector PR = MF.getFrameInfo().getPristineRegs(MF);
+  for (int I = PR.find_first(); I>0; I = PR.find_next(I))
+    setRegUsed(I);
+
   Tracking = false;
 }
 
+void RegScavenger::setLiveInsUsed(const MachineBasicBlock &MBB) {
+  for (const auto &LI : MBB.liveins())
+    setRegUsed(LI.PhysReg, LI.LaneMask);
+}
+
 void RegScavenger::enterBasicBlock(MachineBasicBlock &MBB) {
   init(MBB);
-  LiveUnits.addLiveIns(MBB);
+  setLiveInsUsed(MBB);
 }
 
 void RegScavenger::enterBasicBlockEnd(MachineBasicBlock &MBB) {
   init(MBB);
-  LiveUnits.addLiveOuts(MBB);
+  // Merge live-ins of successors to get live-outs.
+  for (const MachineBasicBlock *Succ : MBB.successors())
+    setLiveInsUsed(*Succ);
 
   // Move internal iterator at the last instruction of the block.
   if (MBB.begin() != MBB.end()) {
@@ -249,13 +268,34 @@ void RegScavenger::backward() {
   assert(Tracking && "Must be tracking to determine kills and defs");
 
   const MachineInstr &MI = *MBBI;
-  LiveUnits.stepBackward(MI);
-
-  // Expire scavenge spill frameindex uses.
-  for (ScavengedInfo &I : Scavenged) {
-    if (I.Restore == &MI) {
-      I.Reg = 0;
-      I.Restore = nullptr;
+  // Defined or clobbered registers are available now.
+  for (const MachineOperand &MO : MI.operands()) {
+    if (MO.isRegMask()) {
+      for (unsigned RU = 0, RUEnd = TRI->getNumRegUnits(); RU != RUEnd;
+           ++RU) {
+        for (MCRegUnitRootIterator RURI(RU, TRI); RURI.isValid(); ++RURI) {
+          if (MO.clobbersPhysReg(*RURI)) {
+            RegUnitsAvailable.set(RU);
+            break;
+          }
+        }
+      }
+    } else if (MO.isReg() && MO.isDef()) {
+      unsigned Reg = MO.getReg();
+      if (!Reg || TargetRegisterInfo::isVirtualRegister(Reg) ||
+          isReserved(Reg))
+        continue;
+      addRegUnits(RegUnitsAvailable, Reg);
+    }
+  }
+  // Mark read registers as unavailable.
+  for (const MachineOperand &MO : MI.uses()) {
+    if (MO.isReg() && MO.readsReg()) {
+      unsigned Reg = MO.getReg();
+      if (!Reg || TargetRegisterInfo::isVirtualRegister(Reg) ||
+          isReserved(Reg))
+        continue;
+      removeRegUnits(RegUnitsAvailable, Reg);
     }
   }
 
@@ -267,9 +307,12 @@ void RegScavenger::backward() {
 }
 
 bool RegScavenger::isRegUsed(unsigned Reg, bool includeReserved) const {
-  if (isReserved(Reg))
-    return includeReserved;
-  return !LiveUnits.available(Reg);
+  if (includeReserved && isReserved(Reg))
+    return true;
+  for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI)
+    if (!RegUnitsAvailable.test(*RUI))
+      return true;
+  return false;
 }
 
 unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RC) const {
@@ -355,69 +398,6 @@ unsigned RegScavenger::findSurvivorReg(MachineBasicBlock::iterator StartMI,
   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();
-  unsigned InstrLimit = 25;
-  unsigned InstrCountDown = InstrLimit;
-  for (MachineBasicBlock::iterator I = From;; --I) {
-    const MachineInstr &MI = *I;
-
-    // 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() || MO.isDebug())
-        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 find
-      // 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) {
-        // Keep searching when we find a vreg since the spilled register will
-        // be usefull for this other vreg as well later.
-        InstrCountDown = InstrLimit;
-        Pos = I;
-      }
-    }
-  }
-
-  return std::make_pair(Survivor, Pos);
-}
-
 static unsigned getFrameIndexOperandNum(MachineInstr &MI) {
   unsigned i = 0;
   while (!MI.getOperand(i).isFI()) {
@@ -427,16 +407,43 @@ static unsigned getFrameIndexOperandNum(MachineInstr &MI) {
   return i;
 }
 
-RegScavenger::ScavengedInfo &
-RegScavenger::spill(unsigned Reg, const TargetRegisterClass &RC, int SPAdj,
-                    MachineBasicBlock::iterator Before,
-                    MachineBasicBlock::iterator &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);
+
+  // 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;
+  }
+
   // 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();
@@ -471,110 +478,42 @@ RegScavenger::spill(unsigned Reg, const TargetRegisterClass &RC, int SPAdj,
   }
 
   // Avoid infinite regress
-  Scavenged[SI].Reg = Reg;
+  Scavenged[SI].Reg = SReg;
 
   // 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, Before, UseMI, &RC, Reg)) {
-    // Spill the scavenged register before \p Before.
+  if (!TRI->saveScavengerRegister(*MBB, I, UseMI, RC, SReg)) {
+    // Spill the scavenged register before I.
     int FI = Scavenged[SI].FrameIndex;
     if (FI < FIB || FI >= FIE) {
       std::string Msg = std::string("Error while trying to spill ") +
-          TRI->getName(Reg) + " from class " + TRI->getRegClassName(&RC) +
+          TRI->getName(SReg) + " from class " + TRI->getRegClassName(RC) +
           ": Cannot scavenge register without an emergency spill slot!";
       report_fatal_error(Msg.c_str());
     }
-    TII->storeRegToStackSlot(*MBB, Before, Reg, true, Scavenged[SI].FrameIndex,
-                             &RC, TRI);
-    MachineBasicBlock::iterator II = std::prev(Before);
+    TII->storeRegToStackSlot(*MBB, I, SReg, true, Scavenged[SI].FrameIndex,
+                             RC, TRI);
+    MachineBasicBlock::iterator II = std::prev(I);
 
     unsigned FIOperandNum = getFrameIndexOperandNum(*II);
     TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this);
 
     // Restore the scavenged register before its use (or first terminator).
-    TII->loadRegFromStackSlot(*MBB, UseMI, Reg, Scavenged[SI].FrameIndex,
-                              &RC, TRI);
+    TII->loadRegFromStackSlot(*MBB, UseMI, SReg, 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);
+  Scavenged[SI].Restore = &*std::prev(UseMI);
 
-  // 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);
+  // Doing this here leads to infinite regress.
+  // Scavenged[SI].Reg = SReg;
 
   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 ReloadAfter =
-      RestoreAfter ? std::next(MBBI) : MBBI;
-    MachineBasicBlock::iterator ReloadBefore = std::next(ReloadAfter);
-    DEBUG(dbgs() << "Reload before: " << *ReloadBefore << '\n');
-    MachineBasicBlock::iterator SpillBefore = P.second;
-    ScavengedInfo &Scavenged = spill(Reg, RC, SPAdj, SpillBefore, ReloadBefore);
-    Scavenged.Restore = &*std::prev(SpillBefore);
-    LiveUnits.removeReg(Reg);
-    DEBUG(dbgs() << "Scavenged register with spill: " << PrintReg(Reg, TRI)
-          << " until " << *SpillBefore);
-  } else {
-    DEBUG(dbgs() << "Scavenged free register: " << PrintReg(Reg, TRI) << '\n');
-  }
-  return Reg;
-}
diff --git a/test/CodeGen/AMDGPU/captured-frame-index.ll b/test/CodeGen/AMDGPU/captured-frame-index.ll
index bf6e48d89ca..161c46b486e 100644
--- a/test/CodeGen/AMDGPU/captured-frame-index.ll
+++ b/test/CodeGen/AMDGPU/captured-frame-index.ll
@@ -140,8 +140,8 @@ define void @stored_fi_to_global_2_small_objects(float* addrspace(1)* %ptr) #0 {
 }
 
 ; GCN-LABEL: {{^}}stored_fi_to_global_huge_frame_offset:
-; 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: s_add_i32 [[BASE_1_OFF_0:s[0-9]+]], 0, 0x3ffc
+; GCN: 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]]
diff --git a/test/CodeGen/Mips/emergency-spill-slot-near-fp.ll b/test/CodeGen/Mips/emergency-spill-slot-near-fp.ll
index 625abc1a7e0..a08b68149a7 100644
--- a/test/CodeGen/Mips/emergency-spill-slot-near-fp.ll
+++ b/test/CodeGen/Mips/emergency-spill-slot-near-fp.ll
@@ -1,62 +1,34 @@
-; RUN: llc -march=mipsel -O0 -relocation-model=pic < %s | FileCheck %s
 ; Check that register scavenging spill slot is close to $fp.
-target triple="mipsel--"
-
-@var = external global i32
-@ptrvar = external global i8*
-
-; 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
-
-  ; 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
+; RUN: llc -march=mipsel -O0 -relocation-model=pic < %s | FileCheck %s
 
-  ; 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
+; CHECK: sw ${{.*}}, 8($sp)
+; CHECK: lw ${{.*}}, 8($sp)
 
-  ret void
+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
 }
+
+attributes #0 = { noinline "no-frame-pointer-elim"="true" }
diff --git a/test/CodeGen/PowerPC/dyn-alloca-aligned.ll b/test/CodeGen/PowerPC/dyn-alloca-aligned.ll
index e0f28475d8f..0de2e220c2c 100644
--- a/test/CodeGen/PowerPC/dyn-alloca-aligned.ll
+++ b/test/CodeGen/PowerPC/dyn-alloca-aligned.ll
@@ -25,8 +25,8 @@ entry:
 
 ; CHECK-DAG: li [[REG1:[0-9]+]], -128
 ; CHECK-DAG: neg [[REG2:[0-9]+]],
-; CHECK: and [[REG3:[0-9]+]], [[REG2]], [[REG1]]
-; CHECK: stdux {{[0-9]+}}, 1, [[REG3]]
+; CHECK: and [[REG1]], [[REG2]], [[REG1]]
+; CHECK: stdux {{[0-9]+}}, 1, [[REG1]]
 
 ; CHECK: blr
 
diff --git a/test/CodeGen/Thumb/large-stack.ll b/test/CodeGen/Thumb/large-stack.ll
index c72a67cd8ea..c5d1044e9d6 100644
--- a/test/CodeGen/Thumb/large-stack.ll
+++ b/test/CodeGen/Thumb/large-stack.ll
@@ -46,8 +46,8 @@ define i32 @test3() {
 ; CHECK-LABEL: test3:
 ; CHECK: ldr [[TEMP:r[0-7]]],
 ; CHECK: add sp, [[TEMP]]
-; CHECK: ldr [[TEMP2:r[0-7]]],
-; CHECK: add [[TEMP2]], sp
+; CHECK: ldr [[TEMP]],
+; CHECK: add [[TEMP]], sp
 ; EABI: ldr [[TEMP:r[0-7]]],
 ; EABI: add sp, [[TEMP]]
 ; IOS: subs r4, r7, #4