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

5 files changed, 52 insertions, 9 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
   //