Re-apply my liveintervalanalysis changes. Now with PR1207 fixes.

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

23 files changed, 334 insertions, 104 deletions

diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h
index 362b3545fb..ef48453b10 100644
--- a/include/llvm/CodeGen/LiveIntervalAnalysis.h
+++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h
@@ -118,6 +118,11 @@ namespace llvm {
       return I->second;
     }
 
+    bool hasInterval(unsigned reg) const {
+      Reg2IntervalMap::const_iterator I = r2iMap_.find(reg);
+      return I != r2iMap_.end();
+    }
+
     /// getMBBStartIdx - Return the base index of the first instruction in the
     /// specified MachineBasicBlock.
     unsigned getMBBStartIdx(MachineBasicBlock *MBB) const {
@@ -189,6 +194,7 @@ namespace llvm {
     /// copies that cannot yet be coallesced into the "TryAgain" list.
     void CopyCoallesceInMBB(MachineBasicBlock *MBB,
                             std::vector<CopyRec> &TryAgain);
+
     /// JoinCopy - Attempt to join intervals corresponding to SrcReg/DstReg,
     /// which are the src/dst of the copy instruction CopyMI.  This returns true
     /// if the copy was successfully coallesced away, or if it is never possible
@@ -233,6 +239,9 @@ namespace llvm {
                                    LiveInterval &interval,
                                    unsigned SrcReg);
 
+    /// handleLiveInRegister - Create interval for a livein register.
+    void handleLiveInRegister(MachineBasicBlock* mbb, LiveInterval &interval);
+
     /// Return true if the two specified registers belong to different
     /// register classes.  The registers may be either phys or virt regs.
     bool differingRegisterClasses(unsigned RegA, unsigned RegB) const;
@@ -241,11 +250,16 @@ namespace llvm {
     bool AdjustCopiesBackFrom(LiveInterval &IntA, LiveInterval &IntB,
                               MachineInstr *CopyMI);
 
-    bool overlapsAliases(const LiveInterval *lhs,
-                         const LiveInterval *rhs) const;
+    /// hasRegisterUse - Returns true if there is any use of the specific
+    /// reg between indexes Start and End.
+    bool hasRegisterUse(unsigned Reg, unsigned Start, unsigned End);
 
     static LiveInterval createInterval(unsigned Reg);
 
+    void removeInterval(unsigned Reg) {
+      r2iMap_.erase(Reg);
+    }
+
     LiveInterval &getOrCreateInterval(unsigned reg) {
       Reg2IntervalMap::iterator I = r2iMap_.find(reg);
       if (I == r2iMap_.end())
diff --git a/include/llvm/CodeGen/LiveVariables.h b/include/llvm/CodeGen/LiveVariables.h
index 6e7e23d495..786a1fdc70 100644
--- a/include/llvm/CodeGen/LiveVariables.h
+++ b/include/llvm/CodeGen/LiveVariables.h
@@ -36,6 +36,7 @@
 namespace llvm {
 
 class MRegisterInfo;
+class BitVector;
 
 class LiveVariables : public MachineFunctionPass {
 public:
@@ -108,11 +109,11 @@ private:
   ///
   std::vector<VarInfo> VirtRegInfo;
 
-  /// AllocatablePhysicalRegisters - This vector keeps track of which registers
-  /// are actually register allocatable by the target machine.  We can not track
-  /// liveness for values that are not in this set.
+  /// ReservedRegisters - This vector keeps track of which registers
+  /// are reserved register which are not allocatable by the target machine.
+  /// We can not track liveness for values that are in this set.
   ///
-  BitVector AllocatablePhysicalRegisters;
+  BitVector ReservedRegisters;
 
 private:   // Intermediate data structures
   const MRegisterInfo *RegInfo;
diff --git a/include/llvm/CodeGen/MachineBasicBlock.h b/include/llvm/CodeGen/MachineBasicBlock.h
index 142f8d8fa6..661430c480 100644
--- a/include/llvm/CodeGen/MachineBasicBlock.h
+++ b/include/llvm/CodeGen/MachineBasicBlock.h
@@ -138,11 +138,18 @@ public:
   /// is an error to add the same register to the same set more than once.
   void addLiveIn(unsigned Reg)  { LiveIns.push_back(Reg); }
 
+  /// removeLiveIn - Remove the specified register from the live in set.
+  ///
+  void removeLiveIn(unsigned Reg);
+
   // Iteration support for live in sets.  These sets are kept in sorted
   // order by their register number.
-  typedef std::vector<unsigned>::const_iterator livein_iterator;
-  livein_iterator livein_begin() const { return LiveIns.begin(); }
-  livein_iterator livein_end()   const { return LiveIns.end(); }
+  typedef std::vector<unsigned>::iterator       livein_iterator;
+  typedef std::vector<unsigned>::const_iterator const_livein_iterator;
+  livein_iterator       livein_begin()       { return LiveIns.begin(); }
+  const_livein_iterator livein_begin() const { return LiveIns.begin(); }
+  livein_iterator       livein_end()         { return LiveIns.end(); }
+  const_livein_iterator livein_end()   const { return LiveIns.end(); }
   bool            livein_empty() const { return LiveIns.empty(); }
 
   // Code Layout methods.
diff --git a/include/llvm/CodeGen/MachineInstr.h b/include/llvm/CodeGen/MachineInstr.h
index ad2ccdf8ca..9cefe7bf20 100644
--- a/include/llvm/CodeGen/MachineInstr.h
+++ b/include/llvm/CodeGen/MachineInstr.h
@@ -393,6 +393,10 @@ public:
   /// the specific register or NULL if it is not found.
   MachineOperand *findRegisterUseOperand(unsigned Reg);
   
+  /// findRegisterDefOperand() - Returns the MachineOperand that is a def of
+  /// the specific register or NULL if it is not found.
+  MachineOperand *findRegisterDefOperand(unsigned Reg);
+  
   /// copyKillDeadInfo - Copies kill / dead operand properties from MI.
   ///
   void copyKillDeadInfo(const MachineInstr *MI);
diff --git a/include/llvm/Target/MRegisterInfo.h b/include/llvm/Target/MRegisterInfo.h
index 6d53d51456..da111e6ce6 100644
--- a/include/llvm/Target/MRegisterInfo.h
+++ b/include/llvm/Target/MRegisterInfo.h
@@ -284,6 +284,17 @@ public:
     return false;
   }
 
+  /// regsOverlap - Returns true if the two registers are equal or alias
+  /// each other. The registers may be virtual register.
+  bool regsOverlap(unsigned regA, unsigned regB) const {
+    if (regA == regB)
+      return true;
+
+    if (isVirtualRegister(regA) || isVirtualRegister(regB))
+      return false;
+    return areAliases(regA, regB);
+  }
+
   /// getCalleeSavedRegs - Return a null-terminated list of all of the
   /// callee saved registers on this target. The register should be in the
   /// order of desired callee-save stack frame offset. The first register is
@@ -295,6 +306,12 @@ public:
   /// length of this list match the getCalleeSaveRegs() list.
   virtual const TargetRegisterClass* const *getCalleeSavedRegClasses() const =0;
 
+  /// getReservedRegs - Returns a bitset indexed by physical register number
+  /// indicating if a register is a special register that has particular uses and
+  /// should be considered unavailable at all times, e.g. SP, RA. This is used by
+  /// register scavenger to determine what registers are free.
+  virtual BitVector getReservedRegs(const MachineFunction &MF) const = 0;
+
   //===--------------------------------------------------------------------===//
   // Register Class Information
   //
diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp
index 57a73d2642..1a598e8ea9 100644
--- a/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -98,28 +98,6 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
     // Set the MBB2IdxMap entry for this MBB.
     MBB2IdxMap[MBB->getNumber()] = MIIndex;
 
-    // If this BB has any live ins, insert a dummy instruction at the
-    // beginning of the function that we will pretend "defines" the values. This
-    // is to make the interval analysis simpler by providing a number.
-    if (MBB->livein_begin() != MBB->livein_end()) {
-      unsigned FirstLiveIn = *MBB->livein_begin();
-
-      // Find a reg class that contains this live in.
-      const TargetRegisterClass *RC = 0;
-      for (MRegisterInfo::regclass_iterator RCI = mri_->regclass_begin(),
-             RCE = mri_->regclass_end(); RCI != RCE; ++RCI)
-        if ((*RCI)->contains(FirstLiveIn)) {
-          RC = *RCI;
-          break;
-        }
-
-      MachineInstr *OldFirstMI = MBB->begin();
-      mri_->copyRegToReg(*MBB, MBB->begin(),
-                         FirstLiveIn, FirstLiveIn, RC);
-      assert(OldFirstMI != MBB->begin() &&
-             "copyRetToReg didn't insert anything!");
-    }
-    
     for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
          I != E; ++I) {
       bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second;
@@ -161,7 +139,17 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
       if (tii_->isMoveInstr(*mii, srcReg, dstReg) &&
           (RegRep = rep(srcReg)) == rep(dstReg)) {
         // remove from def list
-        getOrCreateInterval(RegRep);
+        LiveInterval &RegInt = getOrCreateInterval(RegRep);
+        MachineOperand *MO = mii->findRegisterDefOperand(dstReg);
+        // If def of this move instruction is dead, remove its live range from
+        // the dstination register's live interval.
+        if (MO->isDead()) {
+          unsigned MoveIdx = getDefIndex(getInstructionIndex(mii));
+          LiveInterval::iterator MLR = RegInt.FindLiveRangeContaining(MoveIdx);
+          RegInt.removeRange(MLR->start, MoveIdx+1);
+          if (RegInt.empty())
+            removeInterval(RegRep);
+        }
         RemoveMachineInstrFromMaps(mii);
         mii = mbbi->erase(mii);
         ++numPeep;
@@ -185,7 +173,6 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
     }
   }
 
-  
   for (iterator I = begin(), E = end(); I != E; ++I) {
     LiveInterval &LI = I->second;
     if (MRegisterInfo::isVirtualRegister(LI.reg)) {
@@ -670,6 +657,43 @@ void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB,
   }
 }
 
+void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB,
+                                         LiveInterval &interval) {
+  DOUT << "\t\tlivein register: "; DEBUG(printRegName(interval.reg));
+
+  // Look for kills, if it reaches a def before it's killed, then it shouldn't
+  // be considered a livein.
+  MachineBasicBlock::iterator mi = MBB->begin();
+  unsigned baseIndex = 0;
+  unsigned start = 0;
+  unsigned end = start;
+  while (mi != MBB->end()) {
+    if (lv_->KillsRegister(mi, interval.reg)) {
+      DOUT << " killed";
+      end = getUseIndex(baseIndex) + 1;
+      goto exit;
+    } else if (lv_->ModifiesRegister(mi, interval.reg)) {
+      // Another instruction redefines the register before it is ever read.
+      // Then the register is essentially dead at the instruction that defines
+      // it. Hence its interval is:
+      // [defSlot(def), defSlot(def)+1)
+      DOUT << " dead";
+      end = getDefIndex(start) + 1;
+      goto exit;
+    }
+
+    baseIndex += InstrSlots::NUM;
+    ++mi;
+  }
+
+exit:
+  assert(start < end && "did not find end of interval?");
+
+  LiveRange LR(start, end, interval.getNextValue(~0U, 0));
+  interval.addRange(LR);
+  DOUT << " +" << LR << '\n';
+}
+
 /// computeIntervals - computes the live intervals for virtual
 /// registers. for some ordering of the machine instructions [1,N] a
 /// live interval is an interval [i, j) where 1 <= i <= j < N for
@@ -688,17 +712,13 @@ void LiveIntervals::computeIntervals() {
     MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end();
 
     if (MBB->livein_begin() != MBB->livein_end()) {
-      // Process live-ins to this BB first.
-      for (MachineBasicBlock::livein_iterator LI = MBB->livein_begin(),
+      // Create intervals for live-ins to this BB first.
+      for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(),
              LE = MBB->livein_end(); LI != LE; ++LI) {
-        handlePhysicalRegisterDef(MBB, MBB->begin(), MIIndex,
-                                  getOrCreateInterval(*LI), 0);
+        handleLiveInRegister(MBB, getOrCreateInterval(*LI));
         for (const unsigned* AS = mri_->getAliasSet(*LI); *AS; ++AS)
-          handlePhysicalRegisterDef(MBB, MBB->begin(), MIIndex,
-                                    getOrCreateInterval(*AS), 0);
+          handleLiveInRegister(MBB, getOrCreateInterval(*AS));
       }
-      ++MI;
-      MIIndex += InstrSlots::NUM;
     }
     
     for (; MI != miEnd; ++MI) {
@@ -815,7 +835,6 @@ bool LiveIntervals::AdjustCopiesBackFrom(LiveInterval &IntA, LiveInterval &IntB,
   return true;
 }
 
-
 /// JoinCopy - Attempt to join intervals corresponding to SrcReg/DstReg,
 /// which are the src/dst of the copy instruction CopyMI.  This returns true
 /// if the copy was successfully coallesced away, or if it is never possible
@@ -825,54 +844,93 @@ bool LiveIntervals::AdjustCopiesBackFrom(LiveInterval &IntA, LiveInterval &IntB,
 bool LiveIntervals::JoinCopy(MachineInstr *CopyMI,
                              unsigned SrcReg, unsigned DstReg) {
   DOUT << getInstructionIndex(CopyMI) << '\t' << *CopyMI;
-  
+
   // Get representative registers.
-  SrcReg = rep(SrcReg);
-  DstReg = rep(DstReg);
+  unsigned repSrcReg = rep(SrcReg);
+  unsigned repDstReg = rep(DstReg);
   
   // If they are already joined we continue.
-  if (SrcReg == DstReg) {
+  if (repSrcReg == repDstReg) {
     DOUT << "\tCopy already coallesced.\n";
     return true;  // Not coallescable.
   }
   
   // If they are both physical registers, we cannot join them.
-  if (MRegisterInfo::isPhysicalRegister(SrcReg) &&
-      MRegisterInfo::isPhysicalRegister(DstReg)) {
+  if (MRegisterInfo::isPhysicalRegister(repSrcReg) &&
+      MRegisterInfo::isPhysicalRegister(repDstReg)) {
     DOUT << "\tCan not coallesce physregs.\n";
     return true;  // Not coallescable.
   }
   
   // We only join virtual registers with allocatable physical registers.
-  if (MRegisterInfo::isPhysicalRegister(SrcReg) && !allocatableRegs_[SrcReg]){
+  if (MRegisterInfo::isPhysicalRegister(repSrcReg) &&
+      !allocatableRegs_[repSrcReg]) {
     DOUT << "\tSrc reg is unallocatable physreg.\n";
     return true;  // Not coallescable.
   }
-  if (MRegisterInfo::isPhysicalRegister(DstReg) && !allocatableRegs_[DstReg]){
+  if (MRegisterInfo::isPhysicalRegister(repDstReg) &&
+      !allocatableRegs_[repDstReg]) {
     DOUT << "\tDst reg is unallocatable physreg.\n";
     return true;  // Not coallescable.
   }
   
   // If they are not of the same register class, we cannot join them.
-  if (differingRegisterClasses(SrcReg, DstReg)) {
+  if (differingRegisterClasses(repSrcReg, repDstReg)) {
     DOUT << "\tSrc/Dest are different register classes.\n";
     return true;  // Not coallescable.
   }
   
-  LiveInterval &SrcInt = getInterval(SrcReg);
-  LiveInterval &DestInt = getInterval(DstReg);
-  assert(SrcInt.reg == SrcReg && DestInt.reg == DstReg &&
+  LiveInterval &SrcInt = getInterval(repSrcReg);
+  LiveInterval &DestInt = getInterval(repDstReg);
+  assert(SrcInt.reg == repSrcReg && DestInt.reg == repDstReg &&
          "Register mapping is horribly broken!");
   
   DOUT << "\t\tInspecting "; SrcInt.print(DOUT, mri_);
   DOUT << " and "; DestInt.print(DOUT, mri_);
   DOUT << ": ";
-    
+
+  // Check if it is necessary to propagate "isDead" property before intervals
+  // are joined.
+  MachineOperand *mopd = CopyMI->findRegisterDefOperand(DstReg);
+  bool isDead = mopd->isDead();
+  unsigned SrcStart = 0;
+  unsigned SrcEnd = 0;
+  if (isDead) {
+    unsigned CopyIdx = getDefIndex(getInstructionIndex(CopyMI));
+    LiveInterval::iterator SrcLR = SrcInt.FindLiveRangeContaining(CopyIdx-1);
+    SrcStart = SrcLR->start;
+    SrcEnd   = SrcLR->end;
+    if (hasRegisterUse(repSrcReg, SrcStart, SrcEnd))
+      isDead = false;
+  }
+
   // Okay, attempt to join these two intervals.  On failure, this returns false.
   // Otherwise, if one of the intervals being joined is a physreg, this method
   // always canonicalizes DestInt to be it.  The output "SrcInt" will not have
   // been modified, so we can use this information below to update aliases.
-  if (!JoinIntervals(DestInt, SrcInt)) {
+  if (JoinIntervals(DestInt, SrcInt)) {
+    if (isDead) {
+      // Result of the copy is dead. Propagate this property.
+      if (SrcStart == 0) {
+        // Live-in to the function but dead. Remove it from MBB live-in set.
+        // JoinIntervals may end up swapping the two intervals.
+        LiveInterval &LiveInInt = (repSrcReg == DestInt.reg) ? DestInt:SrcInt;
+        LiveInInt.removeRange(SrcStart, SrcEnd);
+        MachineBasicBlock *MBB = CopyMI->getParent();
+        MBB->removeLiveIn(SrcReg);
+      } else {
+        MachineInstr *SrcMI = getInstructionFromIndex(SrcStart);
+        if (SrcMI) {
+          // FIXME: SrcMI == NULL means the register is livein to a non-entry
+          // MBB. Remove the range from its live interval?
+          MachineOperand *mops = SrcMI->findRegisterDefOperand(SrcReg);
+          if (mops)
+            // FIXME: mops == NULL means SrcMI defines a subregister?
+            mops->setIsDead();
+        }
+      }
+    }
+  } else {
     // Coallescing failed.
     
     // If we can eliminate the copy without merging the live ranges, do so now.
@@ -884,17 +942,17 @@ bool LiveIntervals::JoinCopy(MachineInstr *CopyMI,
     return false;
   }
 
-  bool Swapped = SrcReg == DestInt.reg;
+  bool Swapped = repSrcReg == DestInt.reg;
   if (Swapped)
-    std::swap(SrcReg, DstReg);
-  assert(MRegisterInfo::isVirtualRegister(SrcReg) &&
+    std::swap(repSrcReg, repDstReg);
+  assert(MRegisterInfo::isVirtualRegister(repSrcReg) &&
          "LiveInterval::join didn't work right!");
                                
   // If we're about to merge live ranges into a physical register live range,
   // we have to update any aliased register's live ranges to indicate that they
   // have clobbered values for this range.
-  if (MRegisterInfo::isPhysicalRegister(DstReg)) {
-    for (const unsigned *AS = mri_->getAliasSet(DstReg); *AS; ++AS)
+  if (MRegisterInfo::isPhysicalRegister(repDstReg)) {
+    for (const unsigned *AS = mri_->getAliasSet(repDstReg); *AS; ++AS)
       getInterval(*AS).MergeInClobberRanges(SrcInt);
   }
 
@@ -904,8 +962,8 @@ bool LiveIntervals::JoinCopy(MachineInstr *CopyMI,
   // If the intervals were swapped by Join, swap them back so that the register
   // mapping (in the r2i map) is correct.
   if (Swapped) SrcInt.swap(DestInt);
-  r2iMap_.erase(SrcReg);
-  r2rMap_[SrcReg] = DstReg;
+  removeInterval(repSrcReg);
+  r2rMap_[repSrcReg] = repDstReg;
 
   // Finally, delete the copy instruction.
   RemoveMachineInstrFromMaps(CopyMI);
@@ -1389,6 +1447,29 @@ bool LiveIntervals::differingRegisterClasses(unsigned RegA,
     return !RegClass->contains(RegB);
 }
 
+/// hasRegisterUse - Returns true if there is any use of the specific
+/// reg between indexes Start and End.
+bool
+LiveIntervals::hasRegisterUse(unsigned Reg, unsigned Start, unsigned End) {
+  for (unsigned Index = Start+InstrSlots::NUM; Index != End;
+       Index += InstrSlots::NUM) {
+    // Skip deleted instructions
+    while (Index != End && !getInstructionFromIndex(Index))
+      Index += InstrSlots::NUM;
+    if (Index >= End) break;
+
+    MachineInstr *MI = getInstructionFromIndex(Index);
+    for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
+      MachineOperand &MO = MI->getOperand(i);
+      if (MO.isReg() && MO.isUse() && MO.getReg() &&
+          mri_->regsOverlap(rep(MO.getReg()), Reg))
+        return true;
+    }
+  }
+
+  return false;
+}
+
 LiveInterval LiveIntervals::createInterval(unsigned reg) {
   float Weight = MRegisterInfo::isPhysicalRegister(reg) ?
                        HUGE_VALF : 0.0F;
diff --git a/lib/CodeGen/LiveVariables.cpp b/lib/CodeGen/LiveVariables.cpp
index c0da92c658..a976626b78 100644
--- a/lib/CodeGen/LiveVariables.cpp
+++ b/lib/CodeGen/LiveVariables.cpp
@@ -71,31 +71,11 @@ LiveVariables::VarInfo &LiveVariables::getVarInfo(unsigned RegIdx) {
   return VirtRegInfo[RegIdx];
 }
 
-/// registerOverlap - Returns true if register 1 is equal to register 2
-/// or if register 1 is equal to any of alias of register 2.
-static bool registerOverlap(unsigned Reg1, unsigned Reg2,
-                             const MRegisterInfo *RegInfo) {
-  bool isVirt1 = MRegisterInfo::isVirtualRegister(Reg1);
-  bool isVirt2 = MRegisterInfo::isVirtualRegister(Reg2);
-  if (isVirt1 != isVirt2)
-    return false;
-  if (Reg1 == Reg2)
-    return true;
-  else if (isVirt1)
-    return false;
-  for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg2);
-       unsigned Alias = *AliasSet; ++AliasSet) {
-    if (Reg1 == Alias)
-      return true;
-  }
-  return false;
-}
-
 bool LiveVariables::KillsRegister(MachineInstr *MI, unsigned Reg) const {
   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
     MachineOperand &MO = MI->getOperand(i);
     if (MO.isReg() && MO.isKill()) {
-      if (registerOverlap(Reg, MO.getReg(), RegInfo))
+      if (RegInfo->regsOverlap(Reg, MO.getReg()))
         return true;
     }
   }
@@ -106,7 +86,7 @@ bool LiveVariables::RegisterDefIsDead(MachineInstr *MI, unsigned Reg) const {
   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
     MachineOperand &MO = MI->getOperand(i);
     if (MO.isReg() && MO.isDead())
-      if (registerOverlap(Reg, MO.getReg(), RegInfo))
+      if (RegInfo->regsOverlap(Reg, MO.getReg()))
         return true;
   }
   return false;
@@ -116,7 +96,7 @@ bool LiveVariables::ModifiesRegister(MachineInstr *MI, unsigned Reg) const {
   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
     MachineOperand &MO = MI->getOperand(i);
     if (MO.isReg() && MO.isDef()) {
-      if (registerOverlap(Reg, MO.getReg(), RegInfo))
+      if (RegInfo->regsOverlap(Reg, MO.getReg()))
         return true;
     }
   }
@@ -240,7 +220,7 @@ bool LiveVariables::runOnMachineFunction(MachineFunction &MF) {
   RegInfo = MF.getTarget().getRegisterInfo();
   assert(RegInfo && "Target doesn't have register information?");
 
-  AllocatablePhysicalRegisters = RegInfo->getAllocatableSet(MF);
+  ReservedRegisters = RegInfo->getReservedRegs(MF);
 
   // PhysRegInfo - Keep track of which instruction was the last use of a
   // physical register.  This is a purely local property, because all physical
@@ -267,8 +247,8 @@ bool LiveVariables::runOnMachineFunction(MachineFunction &MF) {
          E = df_ext_end(Entry, Visited); DFI != E; ++DFI) {
     MachineBasicBlock *MBB = *DFI;
 
-  // Mark live-in registers as live-in.
-    for (MachineBasicBlock::livein_iterator II = MBB->livein_begin(),
+    // Mark live-in registers as live-in.
+    for (MachineBasicBlock::const_livein_iterator II = MBB->livein_begin(),
            EE = MBB->livein_end(); II != EE; ++II) {
       assert(MRegisterInfo::isPhysicalRegister(*II) &&
              "Cannot have a live-in virtual register!");
@@ -295,7 +275,7 @@ bool LiveVariables::runOnMachineFunction(MachineFunction &MF) {
           if (MRegisterInfo::isVirtualRegister(MO.getReg())){
             HandleVirtRegUse(getVarInfo(MO.getReg()), MBB, MI);
           } else if (MRegisterInfo::isPhysicalRegister(MO.getReg()) &&
-                     AllocatablePhysicalRegisters[MO.getReg()]) {
+                     !ReservedRegisters[MO.getReg()]) {
             HandlePhysRegUse(MO.getReg(), MI);
           }
         }
@@ -313,7 +293,7 @@ bool LiveVariables::runOnMachineFunction(MachineFunction &MF) {
             // Defaults to dead
             VRInfo.Kills.push_back(MI);
           } else if (MRegisterInfo::isPhysicalRegister(MO.getReg()) &&
-                     AllocatablePhysicalRegisters[MO.getReg()]) {
+                     !ReservedRegisters[MO.getReg()]) {
             HandlePhysRegDef(MO.getReg(), MI);
           }
         }
diff --git a/lib/CodeGen/MachineBasicBlock.cpp b/lib/CodeGen/MachineBasicBlock.cpp
index d67159d61e..bef2502089 100644
--- a/lib/CodeGen/MachineBasicBlock.cpp
+++ b/lib/CodeGen/MachineBasicBlock.cpp
@@ -118,7 +118,7 @@ void MachineBasicBlock::print(std::ostream &OS) const {
   const MRegisterInfo *MRI = MF->getTarget().getRegisterInfo();  
   if (livein_begin() != livein_end()) {
     OS << "Live Ins:";
-    for (livein_iterator I = livein_begin(), E = livein_end(); I != E; ++I)
+    for (const_livein_iterator I = livein_begin(),E = livein_end(); I != E; ++I)
       OutputReg(OS, *I, MRI);
     OS << "\n";
   }
@@ -144,6 +144,12 @@ void MachineBasicBlock::print(std::ostream &OS) const {
   }
 }
 
+void MachineBasicBlock::removeLiveIn(unsigned Reg) {
+  livein_iterator I = std::find(livein_begin(), livein_end(), Reg);
+  assert(I != livein_end() && "Not a live in!");
+  LiveIns.erase(I);
+}
+
 void MachineBasicBlock::moveBefore(MachineBasicBlock *NewAfter) {
   MachineFunction::BasicBlockListType &BBList =getParent()->getBasicBlockList();
   getParent()->getBasicBlockList().splice(NewAfter, BBList, this);
diff --git a/lib/CodeGen/MachineInstr.cpp b/lib/CodeGen/MachineInstr.cpp
index a39313310c..01a3e3ee38 100644
--- a/lib/CodeGen/MachineInstr.cpp
+++ b/lib/CodeGen/MachineInstr.cpp
@@ -180,6 +180,17 @@ MachineOperand *MachineInstr::findRegisterUseOperand(unsigned Reg) {
   return NULL;
 }
   
+/// findRegisterDefOperand() - Returns the MachineOperand that is a def of
+/// the specific register or NULL if it is not found.
+MachineOperand *MachineInstr::findRegisterDefOperand(unsigned Reg) {
+  for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
+    MachineOperand &MO = getOperand(i);
+    if (MO.isReg() && MO.isDef() && MO.getReg() == Reg)
+      return &MO;
+  }
+  return NULL;
+}
+  
 /// copyKillDeadInfo - Copies kill / dead operand properties from MI.
 ///
 void MachineInstr::copyKillDeadInfo(const MachineInstr *MI) {
diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp
index bd44e81244..3a1bfc25fe 100644
--- a/lib/CodeGen/RegAllocLinearScan.cpp
+++ b/lib/CodeGen/RegAllocLinearScan.cpp
@@ -292,8 +292,9 @@ void RA::linearScan()
   }
 
   // A brute force way of adding live-ins to every BB.
-  for (MachineFunction::iterator MBB = mf_->begin(), E = mf_->end();
-       MBB != E; ++MBB) {
+  MachineFunction::iterator MBB = mf_->begin();
+  ++MBB; // Skip entry MBB.
+  for (MachineFunction::iterator E = mf_->end(); MBB != E; ++MBB) {
     unsigned StartIdx = li_->getMBBStartIdx(MBB->getNumber());
     for (IntervalPtrs::iterator i = fixed_.begin(), e = fixed_.end();
          i != e; ++i)
diff --git a/lib/Target/ARM/ARMRegisterInfo.cpp b/lib/Target/ARM/ARMRegisterInfo.cpp
index a96be56384..41f5e46104 100644
--- a/lib/Target/ARM/ARMRegisterInfo.cpp
+++ b/lib/Target/ARM/ARMRegisterInfo.cpp
@@ -28,6 +28,7 @@
 #include "llvm/Target/TargetFrameInfo.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetOptions.h"
+#include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/STLExtras.h"
 #include <algorithm>
@@ -297,6 +298,20 @@ ARMRegisterInfo::getCalleeSavedRegClasses() const {
   return CalleeSavedRegClasses;
 }
 
+BitVector ARMRegisterInfo::getReservedRegs(const MachineFunction &MF) const {
+  BitVector Reserved(getNumRegs());
+  Reserved.set(ARM::SP);
+  if (STI.isTargetDarwin() || hasFP(MF))
+    Reserved.set(FramePtr);
+  // Some targets reserve R9.
+  if (STI.isR9Reserved())
+    Reserved.set(ARM::R9);
+  // At PEI time, if LR is used, it will be spilled upon entry.
+  if (MF.getUsedPhysregs() && !MF.isPhysRegUsed((unsigned)ARM::LR))
+    Reserved.set(ARM::LR);
+  return Reserved;
+}
+
 /// hasFP - Return true if the specified function should have a dedicated frame
 /// pointer register.  This is true if the function has variable sized allocas
 /// or if frame pointer elimination is disabled.
diff --git a/lib/Target/ARM/ARMRegisterInfo.h b/lib/Target/ARM/ARMRegisterInfo.h
index e46da07b00..d5c8021e7a 100644
--- a/lib/Target/ARM/ARMRegisterInfo.h
+++ b/lib/Target/ARM/ARMRegisterInfo.h
@@ -67,6 +67,8 @@ public:
 
   const TargetRegisterClass* const* getCalleeSavedRegClasses() const;
 
+  BitVector getReservedRegs(const MachineFunction &MF) const;
+
   bool hasFP(const MachineFunction &MF) const;
 
   void eliminateCallFramePseudoInstr(MachineFunction &MF,
diff --git a/lib/Target/Alpha/AlphaRegisterInfo.cpp b/lib/Target/Alpha/AlphaRegisterInfo.cpp
index bee76a2146..f08195e8be 100644
--- a/lib/Target/Alpha/AlphaRegisterInfo.cpp
+++ b/lib/Target/Alpha/AlphaRegisterInfo.cpp
@@ -28,6 +28,7 @@
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
+#include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/STLExtras.h"
 #include <cstdlib>
 using namespace llvm;
@@ -178,6 +179,14 @@ AlphaRegisterInfo::getCalleeSavedRegClasses() const {
   return CalleeSavedRegClasses;
 }
 
+BitVector AlphaRegisterInfo::getReservedRegs(const MachineFunction &MF) const {
+  BitVector Reserved(getNumRegs());
+  Reserved.set(Alpha::R15);
+  Reserved.set(Alpha::R30);
+  Reserved.set(Alpha::R31);
+  return Reserved;
+}
+
 //===----------------------------------------------------------------------===//
 // Stack Frame Processing methods
 //===----------------------------------------------------------------------===//
diff --git a/lib/Target/Alpha/AlphaRegisterInfo.h b/lib/Target/Alpha/AlphaRegisterInfo.h
index 5c3f8ecbf6..4629aaa9ae 100644
--- a/lib/Target/Alpha/AlphaRegisterInfo.h
+++ b/lib/Target/Alpha/AlphaRegisterInfo.h
@@ -49,6 +49,8 @@ struct AlphaRegisterInfo : public AlphaGenRegisterInfo {
 
   const TargetRegisterClass* const* getCalleeSavedRegClasses() const;
 
+  BitVector getReservedRegs(const MachineFunction &MF) const;
+
   bool hasFP(const MachineFunction &MF) const;
 
   void eliminateCallFramePseudoInstr(MachineFunction &MF,
diff --git a/lib/Target/IA64/IA64RegisterInfo.cpp b/lib/Target/IA64/IA64RegisterInfo.cpp
index cb9918fcb2..f5f8226686 100644
--- a/lib/Target/IA64/IA64RegisterInfo.cpp
+++ b/lib/Target/IA64/IA64RegisterInfo.cpp
@@ -28,6 +28,7 @@
 #include "llvm/Target/TargetOptions.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Support/CommandLine.h"
+#include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/STLExtras.h"
 using namespace llvm;
 
@@ -106,6 +107,19 @@ IA64RegisterInfo::getCalleeSavedRegClasses() const {
   return CalleeSavedRegClasses;
 }
 
+BitVector IA64RegisterInfo::getReservedRegs(const MachineFunction &MF) const {
+  BitVector Reserved(getNumRegs());
+  Reserved.set(IA64::r0);
+  Reserved.set(IA64::r1);
+  Reserved.set(IA64::r2);
+  Reserved.set(IA64::r5);
+  Reserved.set(IA64::r12);
+  Reserved.set(IA64::r13);
+  Reserved.set(IA64::r22);
+  Reserved.set(IA64::rp);
+  return Reserved;
+}
+
 //===----------------------------------------------------------------------===//
 // Stack Frame Processing methods
 //===----------------------------------------------------------------------===//
diff --git a/lib/Target/IA64/IA64RegisterInfo.h b/lib/Target/IA64/IA64RegisterInfo.h
index 42a2567bfa..9a97712230 100644
--- a/lib/Target/IA64/IA64RegisterInfo.h
+++ b/lib/Target/IA64/IA64RegisterInfo.h
@@ -48,6 +48,8 @@ struct IA64RegisterInfo : public IA64GenRegisterInfo {
 
   const TargetRegisterClass* const* getCalleeSavedRegClasses() const;
 
+  BitVector getReservedRegs(const MachineFunction &MF) const;
+
   bool hasFP(const MachineFunction &MF) const;
 
   void eliminateCallFramePseudoInstr(MachineFunction &MF,
diff --git a/lib/Target/MRegisterInfo.cpp b/lib/Target/MRegisterInfo.cpp
index 7caaae9d4f..08039208fe 100644
--- a/lib/Target/MRegisterInfo.cpp
+++ b/lib/Target/MRegisterInfo.cpp
@@ -41,7 +41,7 @@ BitVector MRegisterInfo::getAllocatableSet(MachineFunction &MF) const {
     const TargetRegisterClass *RC = *I;
     for (TargetRegisterClass::iterator I = RC->allocation_order_begin(MF),
            E = RC->allocation_order_end(MF); I != E; ++I)
-      Allocatable[*I] = true;
+      Allocatable.set(*I);
   }
   return Allocatable;
 }
diff --git a/lib/Target/PowerPC/PPCRegisterInfo.cpp b/lib/Target/PowerPC/PPCRegisterInfo.cpp
index 3370c362f9..7553634066 100644
--- a/lib/Target/PowerPC/PPCRegisterInfo.cpp
+++ b/lib/Target/PowerPC/PPCRegisterInfo.cpp
@@ -34,6 +34,7 @@
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/MathExtras.h"
+#include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/STLExtras.h"
 #include <cstdlib>
 using namespace llvm;
@@ -338,6 +339,35 @@ PPCRegisterInfo::getCalleeSavedRegClasses() const {
                                Darwin32_CalleeSavedRegClasses;
 }
 
+// needsFP - Return true if the specified function should have a dedicated frame
+// pointer register.  This is true if the function has variable sized allocas or
+// if frame pointer elimination is disabled.
+//
+static bool needsFP(const MachineFunction &MF) {
+  const MachineFrameInfo *MFI = MF.getFrameInfo();
+  return NoFramePointerElim || MFI->hasVarSizedObjects();
+}
+
+BitVector PPCRegisterInfo::getReservedRegs(const MachineFunction &MF) const {
+  BitVector Reserved(getNumRegs());
+  Reserved.set(PPC::R0);
+  Reserved.set(PPC::R1);
+  Reserved.set(PPC::LR);
+  // In Linux, r2 is reserved for the OS.
+  if (!Subtarget.isDarwin())
+    Reserved.set(PPC::R2);
+  // On PPC64, r13 is the thread pointer.  Never allocate this register.
+  // Note that this is overconservative, as it also prevents allocation of
+  // R31 when the FP is not needed.
+  if (Subtarget.isPPC64()) {
+    Reserved.set(PPC::R13);
+    Reserved.set(PPC::R31);
+  }
+  if (needsFP(MF))
+    Reserved.set(PPC::R31);
+  return Reserved;
+}
+
 /// foldMemoryOperand - PowerPC (like most RISC's) can only fold spills into
 /// copy instructions, turning them into load/store instructions.
 MachineInstr *PPCRegisterInfo::foldMemoryOperand(MachineInstr *MI,
@@ -398,15 +428,6 @@ MachineInstr *PPCRegisterInfo::foldMemoryOperand(MachineInstr *MI,
 // Stack Frame Processing methods
 //===----------------------------------------------------------------------===//
 
-// needsFP - Return true if the specified function should have a dedicated frame
-// pointer register.  This is true if the function has variable sized allocas or
-// if frame pointer elimination is disabled.
-//
-static bool needsFP(const MachineFunction &MF) {
-  const MachineFrameInfo *MFI = MF.getFrameInfo();
-  return NoFramePointerElim || MFI->hasVarSizedObjects();
-}
-
 // hasFP - Return true if the specified function actually has a dedicated frame
 // pointer register.  This is true if the function needs a frame pointer and has
 // a non-zero stack size.
diff --git a/lib/Target/PowerPC/PPCRegisterInfo.h b/lib/Target/PowerPC/PPCRegisterInfo.h
index f8344de6ac..6c30f6b2a5 100644
--- a/lib/Target/PowerPC/PPCRegisterInfo.h
+++ b/lib/Target/PowerPC/PPCRegisterInfo.h
@@ -58,6 +58,8 @@ public:
 
   const TargetRegisterClass* const* getCalleeSavedRegClasses() const;
 
+  BitVector getReservedRegs(const MachineFunction &MF) const;
+
   /// targetHandlesStackFrameRounding - Returns true if the target is
   /// responsible for rounding up the stack frame (probably at emitPrologue
   /// time).
diff --git a/lib/Target/Sparc/SparcRegisterInfo.cpp b/lib/Target/Sparc/SparcRegisterInfo.cpp
index 3cb5e502f9..dab0b1037d 100644
--- a/lib/Target/Sparc/SparcRegisterInfo.cpp
+++ b/lib/Target/Sparc/SparcRegisterInfo.cpp
@@ -20,6 +20,7 @@
 #include "llvm/CodeGen/MachineLocation.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Type.h"
+#include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/STLExtras.h"
 using namespace llvm;
 
@@ -116,6 +117,22 @@ const unsigned* SparcRegisterInfo::getCalleeSavedRegs() const {
   return CalleeSavedRegs;
 }
 
+BitVector SparcRegisterInfo::getReservedRegs(const MachineFunction &MF) const {
+  BitVector Reserved(getNumRegs());
+  Reserved.set(SP::G2);
+  Reserved.set(SP::G3);
+  Reserved.set(SP::G4);
+  Reserved.set(SP::O6);
+  Reserved.set(SP::I6);
+  Reserved.set(SP::I7);
+  Reserved.set(SP::G0);
+  Reserved.set(SP::G5);
+  Reserved.set(SP::G6);
+  Reserved.set(SP::G7);
+  return Reserved;
+}
+
+
 const TargetRegisterClass* const*
 SparcRegisterInfo::getCalleeSavedRegClasses() const {
   static const TargetRegisterClass * const CalleeSavedRegClasses[] = { 0 };
diff --git a/lib/Target/Sparc/SparcRegisterInfo.h b/lib/Target/Sparc/SparcRegisterInfo.h
index 6f80339c01..763156a70c 100644
--- a/lib/Target/Sparc/SparcRegisterInfo.h
+++ b/lib/Target/Sparc/SparcRegisterInfo.h
@@ -52,6 +52,8 @@ struct SparcRegisterInfo : public SparcGenRegisterInfo {
 
   const TargetRegisterClass* const* getCalleeSavedRegClasses() const;
 
+  BitVector getReservedRegs(const MachineFunction &MF) const;
+
   bool hasFP(const MachineFunction &MF) const;
 
   void eliminateCallFramePseudoInstr(MachineFunction &MF,
diff --git a/lib/Target/X86/X86RegisterInfo.cpp b/lib/Target/X86/X86RegisterInfo.cpp
index 50fb091727..65e847e0db 100644
--- a/lib/Target/X86/X86RegisterInfo.cpp
+++ b/lib/Target/X86/X86RegisterInfo.cpp
@@ -31,6 +31,7 @@
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetOptions.h"
 #include "llvm/Support/CommandLine.h"
+#include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/STLExtras.h"
 using namespace llvm;
 
@@ -883,6 +884,21 @@ X86RegisterInfo::getCalleeSavedRegClasses() const {
   return Is64Bit ? CalleeSavedRegClasses64Bit : CalleeSavedRegClasses32Bit;
 }
 
+BitVector X86RegisterInfo::getReservedRegs(const MachineFunction &MF) const {
+  BitVector Reserved(getNumRegs());
+  Reserved.set(X86::RSP);
+  Reserved.set(X86::ESP);
+  Reserved.set(X86::SP);
+  Reserved.set(X86::SPL);
+  if (hasFP(MF)) {
+    Reserved.set(X86::RBP);
+    Reserved.set(X86::EBP);
+    Reserved.set(X86::BP);
+    Reserved.set(X86::BPL);
+  }
+  return Reserved;
+}
+
 //===----------------------------------------------------------------------===//
 // Stack Frame Processing methods
 //===----------------------------------------------------------------------===//
diff --git a/lib/Target/X86/X86RegisterInfo.h b/lib/Target/X86/X86RegisterInfo.h
index 0066fb6e1e..d504675b05 100644
--- a/lib/Target/X86/X86RegisterInfo.h
+++ b/lib/Target/X86/X86RegisterInfo.h
@@ -78,6 +78,12 @@ public:
   /// length of this list match the getCalleeSavedRegs() list.
   const TargetRegisterClass* const* getCalleeSavedRegClasses() const;
 
+  /// getReservedRegs - Returns a bitset indexed by physical register number
+  /// indicating if a register is a special register that has particular uses and
+  /// should be considered unavailable at all times, e.g. SP, RA. This is used by
+  /// register scavenger to determine what registers are free.
+  BitVector getReservedRegs(const MachineFunction &MF) const;
+
   bool hasFP(const MachineFunction &MF) const;
 
   void eliminateCallFramePseudoInstr(MachineFunction &MF,