Reapply r99881 with some fixes: only call destructor in releaseMemory!
[oota-llvm.git] / include / llvm / CodeGen / LiveInterval.h
index d6f5c8484e423fae15f280f9992e23df21d35ea6..1f198e6325263712bf4490ac42c490d15fb22390 100644 (file)
 
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/Allocator.h"
-#include <iosfwd>
+#include "llvm/Support/AlignOf.h"
+#include "llvm/CodeGen/SlotIndexes.h"
 #include <cassert>
 #include <climits>
 
 namespace llvm {
+  class LiveIntervals;
   class MachineInstr;
+  class MachineRegisterInfo;
   class TargetRegisterInfo;
-  struct LiveInterval;
-
-  /// VNInfo - If the value number definition is undefined (e.g. phi
-  /// merge point), it contains ~0u,x. If the value number is not in use, it
-  /// contains ~1u,x to indicate that the value # is not used. 
-  ///   def   - Instruction # of the definition.
-  ///         - or reg # of the definition if it's a stack slot liveinterval.
-  ///   copy  - Copy iff val# is defined by a copy; zero otherwise.
-  ///   hasPHIKill - One or more of the kills are PHI nodes.
-  ///   redefByEC - Re-defined by early clobber somewhere during the live range.
-  ///   kills - Instruction # of the kills.
-  struct VNInfo {
+  class raw_ostream;
+
+  /// VNInfo - Value Number Information.
+  /// This class holds information about a machine level values, including
+  /// definition and use points.
+  ///
+  /// Care must be taken in interpreting the def index of the value. The 
+  /// following rules apply:
+  ///
+  /// If the isDefAccurate() method returns false then def does not contain the
+  /// index of the defining MachineInstr, or even (necessarily) to a
+  /// MachineInstr at all. In general such a def index is not meaningful
+  /// and should not be used. The exception is that, for values originally
+  /// defined by PHI instructions, after PHI elimination def will contain the
+  /// index of the MBB in which the PHI originally existed. This can be used
+  /// to insert code (spills or copies) which deals with the value, which will
+  /// be live in to the block.
+  class VNInfo {
+  private:
+    enum {
+      HAS_PHI_KILL    = 1,                         
+      REDEF_BY_EC     = 1 << 1,
+      IS_PHI_DEF      = 1 << 2,
+      IS_UNUSED       = 1 << 3,
+      IS_DEF_ACCURATE = 1 << 4
+    };
+
+    unsigned char flags;
+    union {
+      MachineInstr *copy;
+      unsigned reg;
+    } cr;
+
+  public:
+
+    typedef SmallVector<SlotIndex, 4> KillSet;
+
+    /// The ID number of this value.
     unsigned id;
-    unsigned def;
-    MachineInstr *copy;
-    bool hasPHIKill : 1;
-    bool redefByEC : 1;
-    SmallVector<unsigned, 4> kills;
-    VNInfo()
-      : id(~1U), def(~1U), copy(0), hasPHIKill(false), redefByEC(false) {}
-    VNInfo(unsigned i, unsigned d, MachineInstr *c)
-      : id(i), def(d), copy(c), hasPHIKill(false), redefByEC(false) {}
+    
+    /// The index of the defining instruction (if isDefAccurate() returns true).
+    SlotIndex def;
+
+    KillSet kills;
+
+    /*
+    VNInfo(LiveIntervals &li_)
+      : defflags(IS_UNUSED), id(~1U) { cr.copy = 0; }
+    */
+
+    /// VNInfo constructor.
+    /// d is presumed to point to the actual defining instr. If it doesn't
+    /// setIsDefAccurate(false) should be called after construction.
+    VNInfo(unsigned i, SlotIndex d, MachineInstr *c)
+      : flags(IS_DEF_ACCURATE), id(i), def(d) { cr.copy = c; }
+
+    /// VNInfo construtor, copies values from orig, except for the value number.
+    VNInfo(unsigned i, const VNInfo &orig)
+      : flags(orig.flags), cr(orig.cr), id(i), def(orig.def), kills(orig.kills)
+    { }
+
+    /// Copy from the parameter into this VNInfo.
+    void copyFrom(VNInfo &src) {
+      flags = src.flags;
+      cr = src.cr;
+      def = src.def;
+      kills = src.kills;
+    }
+
+    /// Used for copying value number info.
+    unsigned getFlags() const { return flags; }
+    void setFlags(unsigned flags) { this->flags = flags; }
+
+    /// For a register interval, if this VN was definied by a copy instr
+    /// getCopy() returns a pointer to it, otherwise returns 0.
+    /// For a stack interval the behaviour of this method is undefined.
+    MachineInstr* getCopy() const { return cr.copy; }
+    /// For a register interval, set the copy member.
+    /// This method should not be called on stack intervals as it may lead to
+    /// undefined behavior.
+    void setCopy(MachineInstr *c) { cr.copy = c; }
+    
+    /// For a stack interval, returns the reg which this stack interval was
+    /// defined from.
+    /// For a register interval the behaviour of this method is undefined. 
+    unsigned getReg() const { return cr.reg; }
+    /// For a stack interval, set the defining register.
+    /// This method should not be called on register intervals as it may lead
+    /// to undefined behaviour.
+    void setReg(unsigned reg) { cr.reg = reg; }
+
+    /// Returns true if one or more kills are PHI nodes.
+    bool hasPHIKill() const { return flags & HAS_PHI_KILL; }
+    /// Set the PHI kill flag on this value.
+    void setHasPHIKill(bool hasKill) {
+      if (hasKill)
+        flags |= HAS_PHI_KILL;
+      else
+        flags &= ~HAS_PHI_KILL;
+    }
+
+    /// Returns true if this value is re-defined by an early clobber somewhere
+    /// during the live range.
+    bool hasRedefByEC() const { return flags & REDEF_BY_EC; }
+    /// Set the "redef by early clobber" flag on this value.
+    void setHasRedefByEC(bool hasRedef) {
+      if (hasRedef)
+        flags |= REDEF_BY_EC;
+      else
+        flags &= ~REDEF_BY_EC;
+    }
+   
+    /// Returns true if this value is defined by a PHI instruction (or was,
+    /// PHI instrucions may have been eliminated).
+    bool isPHIDef() const { return flags & IS_PHI_DEF; }
+    /// Set the "phi def" flag on this value.
+    void setIsPHIDef(bool phiDef) {
+      if (phiDef)
+        flags |= IS_PHI_DEF;
+      else
+        flags &= ~IS_PHI_DEF;
+    }
+
+    /// Returns true if this value is unused.
+    bool isUnused() const { return flags & IS_UNUSED; }
+    /// Set the "is unused" flag on this value.
+    void setIsUnused(bool unused) {
+      if (unused)
+        flags |= IS_UNUSED;
+      else
+        flags &= ~IS_UNUSED;
+    }
+
+    /// Returns true if the def is accurate.
+    bool isDefAccurate() const { return flags & IS_DEF_ACCURATE; }
+    /// Set the "is def accurate" flag on this value.
+    void setIsDefAccurate(bool defAccurate) {
+      if (defAccurate)
+        flags |= IS_DEF_ACCURATE;
+      else 
+        flags &= ~IS_DEF_ACCURATE;
+    }
+
+    /// Returns true if the given index is a kill of this value.
+    bool isKill(SlotIndex k) const {
+      KillSet::const_iterator
+        i = std::lower_bound(kills.begin(), kills.end(), k);
+      return (i != kills.end() && *i == k);
+    }
+
+    /// addKill - Add a kill instruction index to the specified value
+    /// number.
+    void addKill(SlotIndex k) {
+      if (kills.empty()) {
+        kills.push_back(k);
+      } else {
+        KillSet::iterator
+          i = std::lower_bound(kills.begin(), kills.end(), k);
+        kills.insert(i, k);
+      }
+    }
+
+    /// Remove the specified kill index from this value's kills list.
+    /// Returns true if the value was present, otherwise returns false.
+    bool removeKill(SlotIndex k) {
+      KillSet::iterator i = std::lower_bound(kills.begin(), kills.end(), k);
+      if (i != kills.end() && *i == k) {
+        kills.erase(i);
+        return true;
+      }
+      return false;
+    }
+
+    /// Remove all kills in the range [s, e).
+    void removeKills(SlotIndex s, SlotIndex e) {
+      KillSet::iterator
+        si = std::lower_bound(kills.begin(), kills.end(), s),
+        se = std::upper_bound(kills.begin(), kills.end(), e);
+
+      kills.erase(si, se);
+    }
+
   };
 
   /// LiveRange structure - This represents a simple register range in the
   /// program, with an inclusive start point and an exclusive end point.
   /// These ranges are rendered as [start,end).
   struct LiveRange {
-    unsigned start;  // Start point of the interval (inclusive)
-    unsigned end;    // End point of the interval (exclusive)
+    SlotIndex start;  // Start point of the interval (inclusive)
+    SlotIndex end;    // End point of the interval (exclusive)
     VNInfo *valno;   // identifier for the value contained in this interval.
 
-    LiveRange(unsigned S, unsigned E, VNInfo *V) : start(S), end(E), valno(V) {
+    LiveRange(SlotIndex S, SlotIndex E, VNInfo *V)
+      : start(S), end(E), valno(V) {
+
       assert(S < E && "Cannot create empty or backwards range");
     }
 
     /// contains - Return true if the index is covered by this range.
     ///
-    bool contains(unsigned I) const {
+    bool contains(SlotIndex I) const {
       return start <= I && I < end;
     }
 
+    /// containsRange - Return true if the given range, [S, E), is covered by
+    /// this range. 
+    bool containsRange(SlotIndex S, SlotIndex E) const {
+      assert((S < E) && "Backwards interval?");
+      return (start <= S && S < end) && (start < E && E <= end);
+    }
+
     bool operator<(const LiveRange &LR) const {
       return start < LR.start || (start == LR.start && end < LR.end);
     }
@@ -80,41 +252,51 @@ namespace llvm {
     }
 
     void dump() const;
-    void print(std::ostream &os) const;
-    void print(std::ostream *os) const { if (os) print(*os); }
+    void print(raw_ostream &os) const;
 
   private:
     LiveRange(); // DO NOT IMPLEMENT
   };
 
-  std::ostream& operator<<(std::ostream& os, const LiveRange &LR);
+  raw_ostream& operator<<(raw_ostream& os, const LiveRange &LR);
 
 
-  inline bool operator<(unsigned V, const LiveRange &LR) {
+  inline bool operator<(SlotIndex V, const LiveRange &LR) {
     return V < LR.start;
   }
 
-  inline bool operator<(const LiveRange &LR, unsigned V) {
+  inline bool operator<(const LiveRange &LR, SlotIndex V) {
     return LR.start < V;
   }
 
   /// LiveInterval - This class represents some number of live ranges for a
   /// register or value.  This class also contains a bit of register allocator
   /// state.
-  struct LiveInterval {
+  class LiveInterval {
+  public:
+
     typedef SmallVector<LiveRange,4> Ranges;
     typedef SmallVector<VNInfo*,4> VNInfoList;
 
     unsigned reg;        // the register or stack slot of this interval
                          // if the top bits is set, it represents a stack slot.
     float weight;        // weight of this interval
-    unsigned short preference; // preferred register for this interval
     Ranges ranges;       // the ranges in which this register is live
     VNInfoList valnos;   // value#'s
+    
+    struct InstrSlots {
+      enum {
+        LOAD  = 0,
+        USE   = 1,
+        DEF   = 2,
+        STORE = 3,
+        NUM   = 4
+      };
+
+    };
 
-  public:
     LiveInterval(unsigned Reg, float Weight, bool IsSS = false)
-      : reg(Reg), weight(Weight), preference(0)  {
+      : reg(Reg), weight(Weight) {
       if (IsSS)
         reg = reg | (1U << (sizeof(unsigned)*CHAR_BIT-1));
     }
@@ -138,22 +320,17 @@ namespace llvm {
     /// advanceTo - Advance the specified iterator to point to the LiveRange
     /// containing the specified position, or end() if the position is past the
     /// end of the interval.  If no LiveRange contains this position, but the
-    /// position is in a hole, this method returns an iterator pointing the the
+    /// position is in a hole, this method returns an iterator pointing to the
     /// LiveRange immediately after the hole.
-    iterator advanceTo(iterator I, unsigned Pos) {
-      if (Pos >= endNumber())
+    iterator advanceTo(iterator I, SlotIndex Pos) {
+      if (Pos >= endIndex())
         return end();
       while (I->end <= Pos) ++I;
       return I;
     }
     
     void clear() {
-      while (!valnos.empty()) {
-        VNInfo *VNI = valnos.back();
-        valnos.pop_back();
-        VNI->~VNInfo();
-      }
-      
+      valnos.clear();
       ranges.clear();
     }
 
@@ -184,98 +361,47 @@ namespace llvm {
     inline const VNInfo *getValNumInfo(unsigned ValNo) const {
       return valnos[ValNo];
     }
-    
-    /// copyValNumInfo - Copy the value number info for one value number to
-    /// another.
-    void copyValNumInfo(VNInfo *DstValNo, const VNInfo *SrcValNo) {
-      DstValNo->def = SrcValNo->def;
-      DstValNo->copy = SrcValNo->copy;
-      DstValNo->hasPHIKill = SrcValNo->hasPHIKill;
-      DstValNo->redefByEC = SrcValNo->redefByEC;
-      DstValNo->kills = SrcValNo->kills;
-    }
 
     /// getNextValue - Create a new value number and return it.  MIIdx specifies
     /// the instruction that defines the value number.
-    VNInfo *getNextValue(unsigned MIIdx, MachineInstr *CopyMI,
-                         BumpPtrAllocator &VNInfoAllocator) {
-#ifdef __GNUC__
-      unsigned Alignment = (unsigned)__alignof__(VNInfo);
-#else
-      // FIXME: ugly.
-      unsigned Alignment = 8;
-#endif
+    VNInfo *getNextValue(SlotIndex def, MachineInstr *CopyMI,
+                         bool isDefAccurate, BumpPtrAllocator &VNInfoAllocator){
       VNInfo *VNI =
         static_cast<VNInfo*>(VNInfoAllocator.Allocate((unsigned)sizeof(VNInfo),
-                                                      Alignment));
-      new (VNI) VNInfo((unsigned)valnos.size(), MIIdx, CopyMI);
+                                                      alignof<VNInfo>()));
+      new (VNI) VNInfo((unsigned)valnos.size(), def, CopyMI);
+      VNI->setIsDefAccurate(isDefAccurate);
       valnos.push_back(VNI);
       return VNI;
     }
 
-    /// addKill - Add a kill instruction index to the specified value
-    /// number.
-    static void addKill(VNInfo *VNI, unsigned KillIdx) {
-      SmallVector<unsigned, 4> &kills = VNI->kills;
-      if (kills.empty()) {
-        kills.push_back(KillIdx);
-      } else {
-        SmallVector<unsigned, 4>::iterator
-          I = std::lower_bound(kills.begin(), kills.end(), KillIdx);
-        kills.insert(I, KillIdx);
-      }
+    /// Create a copy of the given value. The new value will be identical except
+    /// for the Value number.
+    VNInfo *createValueCopy(const VNInfo *orig,
+                            BumpPtrAllocator &VNInfoAllocator) {
+      VNInfo *VNI =
+        static_cast<VNInfo*>(VNInfoAllocator.Allocate((unsigned)sizeof(VNInfo),
+                                                      alignof<VNInfo>()));
+    
+      new (VNI) VNInfo((unsigned)valnos.size(), *orig);
+      valnos.push_back(VNI);
+      return VNI;
     }
 
     /// addKills - Add a number of kills into the VNInfo kill vector. If this
     /// interval is live at a kill point, then the kill is not added.
-    void addKills(VNInfo *VNI, const SmallVector<unsigned, 4> &kills) {
+    void addKills(VNInfo *VNI, const VNInfo::KillSet &kills) {
       for (unsigned i = 0, e = static_cast<unsigned>(kills.size());
            i != e; ++i) {
-        unsigned KillIdx = kills[i];
-        if (!liveBeforeAndAt(KillIdx)) {
-          SmallVector<unsigned, 4>::iterator
-            I = std::lower_bound(VNI->kills.begin(), VNI->kills.end(), KillIdx);
-          VNI->kills.insert(I, KillIdx);
+        if (!liveBeforeAndAt(kills[i])) {
+          VNI->addKill(kills[i]);
         }
       }
     }
 
-    /// removeKill - Remove the specified kill from the list of kills of
-    /// the specified val#.
-    static bool removeKill(VNInfo *VNI, unsigned KillIdx) {
-      SmallVector<unsigned, 4> &kills = VNI->kills;
-      SmallVector<unsigned, 4>::iterator
-        I = std::lower_bound(kills.begin(), kills.end(), KillIdx);
-      if (I != kills.end() && *I == KillIdx) {
-        kills.erase(I);
-        return true;
-      }
-      return false;
-    }
-
-    /// removeKills - Remove all the kills in specified range
-    /// [Start, End] of the specified val#.
-    static void removeKills(VNInfo *VNI, unsigned Start, unsigned End) {
-      SmallVector<unsigned, 4> &kills = VNI->kills;
-      SmallVector<unsigned, 4>::iterator
-        I = std::lower_bound(kills.begin(), kills.end(), Start);
-      SmallVector<unsigned, 4>::iterator
-        E = std::upper_bound(kills.begin(), kills.end(), End);
-      kills.erase(I, E);
-    }
-
-    /// isKill - Return true if the specified index is a kill of the
-    /// specified val#.
-    static bool isKill(const VNInfo *VNI, unsigned KillIdx) {
-      const SmallVector<unsigned, 4> &kills = VNI->kills;
-      SmallVector<unsigned, 4>::const_iterator
-        I = std::lower_bound(kills.begin(), kills.end(), KillIdx);
-      return I != kills.end() && *I == KillIdx;
-    }
-
     /// isOnlyLROfValNo - Return true if the specified live range is the only
     /// one defined by the its val#.
-    bool isOnlyLROfValNo( const LiveRange *LR) {
+    bool isOnlyLROfValNo(const LiveRange *LR) {
       for (const_iterator I = begin(), E = end(); I != E; ++I) {
         const LiveRange *Tmp = I;
         if (Tmp != LR && Tmp->valno == LR->valno)
@@ -294,12 +420,15 @@ namespace llvm {
     /// current interval, but are defined in the Clobbers interval, mark them
     /// used with an unknown definition value. Caller must pass in reference to
     /// VNInfoAllocator since it will create a new val#.
-    void MergeInClobberRanges(const LiveInterval &Clobbers,
+    void MergeInClobberRanges(LiveIntervals &li_,
+                              const LiveInterval &Clobbers,
                               BumpPtrAllocator &VNInfoAllocator);
 
     /// MergeInClobberRange - Same as MergeInClobberRanges except it merge in a
     /// single LiveRange only.
-    void MergeInClobberRange(unsigned Start, unsigned End,
+    void MergeInClobberRange(LiveIntervals &li_,
+                             SlotIndex Start,
+                             SlotIndex End,
                              BumpPtrAllocator &VNInfoAllocator);
 
     /// MergeValueInAsValue - Merge all of the live ranges of a specific val#
@@ -319,55 +448,65 @@ namespace llvm {
 
     /// Copy - Copy the specified live interval. This copies all the fields
     /// except for the register of the interval.
-    void Copy(const LiveInterval &RHS, BumpPtrAllocator &VNInfoAllocator);
+    void Copy(const LiveInterval &RHS, MachineRegisterInfo *MRI,
+              BumpPtrAllocator &VNInfoAllocator);
     
     bool empty() const { return ranges.empty(); }
 
-    /// beginNumber - Return the lowest numbered slot covered by interval.
-    unsigned beginNumber() const {
-      if (empty())
-        return 0;
+    /// beginIndex - Return the lowest numbered slot covered by interval.
+    SlotIndex beginIndex() const {
+      assert(!empty() && "Call to beginIndex() on empty interval.");
       return ranges.front().start;
     }
 
     /// endNumber - return the maximum point of the interval of the whole,
     /// exclusive.
-    unsigned endNumber() const {
-      if (empty())
-        return 0;
+    SlotIndex endIndex() const {
+      assert(!empty() && "Call to endIndex() on empty interval.");
       return ranges.back().end;
     }
 
-    bool expiredAt(unsigned index) const {
-      return index >= endNumber();
+    bool expiredAt(SlotIndex index) const {
+      return index >= endIndex();
     }
 
-    bool liveAt(unsigned index) const;
+    bool liveAt(SlotIndex index) const;
 
     // liveBeforeAndAt - Check if the interval is live at the index and the
     // index just before it. If index is liveAt, check if it starts a new live
     // range.If it does, then check if the previous live range ends at index-1.
-    bool liveBeforeAndAt(unsigned index) const;
+    bool liveBeforeAndAt(SlotIndex index) const;
 
     /// getLiveRangeContaining - Return the live range that contains the
     /// specified index, or null if there is none.
-    const LiveRange *getLiveRangeContaining(unsigned Idx) const {
+    const LiveRange *getLiveRangeContaining(SlotIndex Idx) const {
       const_iterator I = FindLiveRangeContaining(Idx);
       return I == end() ? 0 : &*I;
     }
 
+    /// getLiveRangeContaining - Return the live range that contains the
+    /// specified index, or null if there is none.
+    LiveRange *getLiveRangeContaining(SlotIndex Idx) {
+      iterator I = FindLiveRangeContaining(Idx);
+      return I == end() ? 0 : &*I;
+    }
+
     /// FindLiveRangeContaining - Return an iterator to the live range that
     /// contains the specified index, or end() if there is none.
-    const_iterator FindLiveRangeContaining(unsigned Idx) const;
+    const_iterator FindLiveRangeContaining(SlotIndex Idx) const;
 
     /// FindLiveRangeContaining - Return an iterator to the live range that
     /// contains the specified index, or end() if there is none.
-    iterator FindLiveRangeContaining(unsigned Idx);
+    iterator FindLiveRangeContaining(SlotIndex Idx);
+
+    /// findDefinedVNInfo - Find the by the specified
+    /// index (register interval) or defined 
+    VNInfo *findDefinedVNInfoForRegInt(SlotIndex Idx) const;
+
+    /// findDefinedVNInfo - Find the VNInfo that's defined by the specified
+    /// register (stack inteval only).
+    VNInfo *findDefinedVNInfoForStackInt(unsigned Reg) const;
 
-    /// findDefinedVNInfo - Find the VNInfo that's defined at the specified
-    /// index (register interval) or defined by the specified register (stack
-    /// inteval).
-    VNInfo *findDefinedVNInfo(unsigned DefIdxOrReg) const;
     
     /// overlaps - Return true if the intersection of the two live intervals is
     /// not empty.
@@ -377,7 +516,7 @@ namespace llvm {
 
     /// overlaps - Return true if the live interval overlaps a range specified
     /// by [Start, End).
-    bool overlaps(unsigned Start, unsigned End) const;
+    bool overlaps(SlotIndex Start, SlotIndex End) const;
 
     /// overlapsFrom - Return true if the intersection of the two live intervals
     /// is not empty.  The specified iterator is a hint that we can begin
@@ -394,17 +533,20 @@ namespace llvm {
     /// join - Join two live intervals (this, and other) together.  This applies
     /// mappings to the value numbers in the LHS/RHS intervals as specified.  If
     /// the intervals are not joinable, this aborts.
-    void join(LiveInterval &Other, const int *ValNoAssignments,
+    void join(LiveInterval &Other,
+              const int *ValNoAssignments,
               const int *RHSValNoAssignments,
-              SmallVector<VNInfo*, 16> &NewVNInfo);
+              SmallVector<VNInfo*, 16> &NewVNInfo,
+              MachineRegisterInfo *MRI);
 
     /// isInOneLiveRange - Return true if the range specified is entirely in the
     /// a single LiveRange of the live interval.
-    bool isInOneLiveRange(unsigned Start, unsigned End);
+    bool isInOneLiveRange(SlotIndex Start, SlotIndex End);
 
     /// removeRange - Remove the specified range from this interval.  Note that
     /// the range must be a single LiveRange in its entirety.
-    void removeRange(unsigned Start, unsigned End, bool RemoveDeadValNo = false);
+    void removeRange(SlotIndex Start, SlotIndex End,
+                     bool RemoveDeadValNo = false);
 
     void removeRange(LiveRange LR, bool RemoveDeadValNo = false) {
       removeRange(LR.start, LR.end, RemoveDeadValNo);
@@ -414,28 +556,49 @@ namespace llvm {
     /// Also remove the value# from value# list.
     void removeValNo(VNInfo *ValNo);
 
+    /// scaleNumbering - Renumber VNI and ranges to provide gaps for new
+    /// instructions.
+    void scaleNumbering(unsigned factor);
+
     /// getSize - Returns the sum of sizes of all the LiveRange's.
     ///
     unsigned getSize() const;
 
-    bool operator<(const LiveInterval& other) const {
-      return beginNumber() < other.beginNumber();
+    /// isSpillable - Can this interval be spilled?
+    bool isSpillable() const {
+      return weight != HUGE_VALF;
     }
 
-    void print(std::ostream &OS, const TargetRegisterInfo *TRI = 0) const;
-    void print(std::ostream *OS, const TargetRegisterInfo *TRI = 0) const {
-      if (OS) print(*OS, TRI);
+    /// markNotSpillable - Mark interval as not spillable
+    void markNotSpillable() {
+      weight = HUGE_VALF;
+    }
+
+    /// ComputeJoinedWeight - Set the weight of a live interval after
+    /// Other has been merged into it.
+    void ComputeJoinedWeight(const LiveInterval &Other);
+
+    bool operator<(const LiveInterval& other) const {
+      const SlotIndex &thisIndex = beginIndex();
+      const SlotIndex &otherIndex = other.beginIndex();
+      return (thisIndex < otherIndex ||
+              (thisIndex == otherIndex && reg < other.reg));
     }
+
+    void print(raw_ostream &OS, const TargetRegisterInfo *TRI = 0) const;
     void dump() const;
 
   private:
+
     Ranges::iterator addRangeFrom(LiveRange LR, Ranges::iterator From);
-    void extendIntervalEndTo(Ranges::iterator I, unsigned NewEnd);
-    Ranges::iterator extendIntervalStartTo(Ranges::iterator I, unsigned NewStr);
+    void extendIntervalEndTo(Ranges::iterator I, SlotIndex NewEnd);
+    Ranges::iterator extendIntervalStartTo(Ranges::iterator I, SlotIndex NewStr);
+
     LiveInterval& operator=(const LiveInterval& rhs); // DO NOT IMPLEMENT
+
   };
 
-  inline std::ostream &operator<<(std::ostream &OS, const LiveInterval &LI) {
+  inline raw_ostream &operator<<(raw_ostream &OS, const LiveInterval &LI) {
     LI.print(OS);
     return OS;
   }