Index: llvm/trunk/include/llvm/CodeGen/LiveRegUnits.h
===================================================================
--- llvm/trunk/include/llvm/CodeGen/LiveRegUnits.h
+++ llvm/trunk/include/llvm/CodeGen/LiveRegUnits.h
@@ -0,0 +1,116 @@
+//===- 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
Index: llvm/trunk/include/llvm/CodeGen/RegisterScavenging.h
===================================================================
--- llvm/trunk/include/llvm/CodeGen/RegisterScavenging.h
+++ llvm/trunk/include/llvm/CodeGen/RegisterScavenging.h
@@ -19,6 +19,7 @@
 #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"
 
@@ -58,10 +59,7 @@
   /// A vector of information on scavenged registers.
   SmallVector<ScavengedInfo, 2> Scavenged;
 
-  /// 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;
+  LiveRegUnits LiveUnits;
 
   // These BitVectors are only used internally to forward(). They are members
   // to avoid frequent reallocations.
@@ -183,11 +181,11 @@
 
   /// setUsed / setUnused - Mark the state of one or a number of register units.
   ///
-  void setUsed(BitVector &RegUnits) {
-    RegUnitsAvailable.reset(RegUnits);
+  void setUsed(const BitVector &RegUnits) {
+    LiveUnits.addUnits(RegUnits);
   }
-  void setUnused(BitVector &RegUnits) {
-    RegUnitsAvailable |= RegUnits;
+  void setUnused(const BitVector &RegUnits) {
+    LiveUnits.removeUnits(RegUnits);
   }
 
   /// Processes the current instruction and fill the KillRegUnits and
Index: llvm/trunk/lib/CodeGen/CMakeLists.txt
===================================================================
--- llvm/trunk/lib/CodeGen/CMakeLists.txt
+++ llvm/trunk/lib/CodeGen/CMakeLists.txt
@@ -44,6 +44,7 @@
   LiveRangeCalc.cpp
   LiveRangeEdit.cpp
   LiveRegMatrix.cpp
+  LiveRegUnits.cpp
   LiveStackAnalysis.cpp
   LiveVariables.cpp
   LLVMTargetMachine.cpp
Index: llvm/trunk/lib/CodeGen/LiveRegUnits.cpp
===================================================================
--- llvm/trunk/lib/CodeGen/LiveRegUnits.cpp
+++ llvm/trunk/lib/CodeGen/LiveRegUnits.cpp
@@ -0,0 +1,97 @@
+//===--- 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);
+}
Index: llvm/trunk/lib/CodeGen/RegisterScavenging.cpp
===================================================================
--- llvm/trunk/lib/CodeGen/RegisterScavenging.cpp
+++ llvm/trunk/lib/CodeGen/RegisterScavenging.cpp
@@ -32,11 +32,7 @@
 #define DEBUG_TYPE "reg-scavenging"
 
 void RegScavenger::setRegUsed(unsigned Reg, LaneBitmask LaneMask) {
-  for (MCRegUnitMaskIterator RUI(Reg, TRI); RUI.isValid(); ++RUI) {
-    LaneBitmask UnitMask = (*RUI).second;
-    if (UnitMask == 0 || (LaneMask & UnitMask) != 0)
-      RegUnitsAvailable.reset((*RUI).first);
-  }
+  LiveUnits.addRegMasked(Reg, LaneMask);
 }
 
 void RegScavenger::init(MachineBasicBlock &MBB) {
@@ -44,6 +40,7 @@
   TII = MF.getSubtarget().getInstrInfo();
   TRI = MF.getSubtarget().getRegisterInfo();
   MRI = &MF.getRegInfo();
+  LiveUnits.init(*TRI);
 
   assert((NumRegUnits == 0 || NumRegUnits == TRI->getNumRegUnits()) &&
          "Target changed?");
@@ -56,7 +53,6 @@
   // Self-initialize.
   if (!this->MBB) {
     NumRegUnits = TRI->getNumRegUnits();
-    RegUnitsAvailable.resize(NumRegUnits);
     KillRegUnits.resize(NumRegUnits);
     DefRegUnits.resize(NumRegUnits);
     TmpRegUnits.resize(NumRegUnits);
@@ -69,32 +65,17 @@
     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);
-  setLiveInsUsed(MBB);
+  LiveUnits.addLiveIns(MBB);
 }
 
 void RegScavenger::enterBasicBlockEnd(MachineBasicBlock &MBB) {
   init(MBB);
-  // Merge live-ins of successors to get live-outs.
-  for (const MachineBasicBlock *Succ : MBB.successors())
-    setLiveInsUsed(*Succ);
+  LiveUnits.addLiveOuts(MBB);
 
   // Move internal iterator at the last instruction of the block.
   if (MBB.begin() != MBB.end()) {
@@ -268,36 +249,7 @@
   assert(Tracking && "Must be tracking to determine kills and defs");
 
   const MachineInstr &MI = *MBBI;
-  // 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);
-    }
-  }
+  LiveUnits.stepBackward(MI);
 
   // Expire scavenge spill frameindex uses.
   for (ScavengedInfo &I : Scavenged) {
@@ -315,12 +267,9 @@
 }
 
 bool RegScavenger::isRegUsed(unsigned Reg, bool includeReserved) const {
-  if (includeReserved && isReserved(Reg))
-    return true;
-  for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI)
-    if (!RegUnitsAvailable.test(*RUI))
-      return true;
-  return false;
+  if (isReserved(Reg))
+    return includeReserved;
+  return !LiveUnits.available(Reg);
 }
 
 unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RC) const {
@@ -621,7 +570,7 @@
     MachineBasicBlock::iterator SpillBefore = P.second;
     ScavengedInfo &Scavenged = spill(Reg, RC, SPAdj, SpillBefore, ReloadBefore);
     Scavenged.Restore = &*std::prev(SpillBefore);
-    addRegUnits(RegUnitsAvailable, Reg);
+    LiveUnits.removeReg(Reg);
     DEBUG(dbgs() << "Scavenged register with spill: " << PrintReg(Reg, TRI)
           << " until " << *SpillBefore);
   } else {