include/llvm/CodeGen/LiveInterval.h

   1 //===-- llvm/CodeGen/LiveInterval.h - Interval representation ---*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the LiveRange and LiveInterval classes.  Given some
  11 // numbering of each the machine instructions an interval [i, j) is said to be a
  12 // live interval for register v if there is no instruction with number j' >= j
  13 // such that v is live at j' and there is no instruction with number i' < i such
  14 // that v is live at i'. In this implementation intervals can have holes,
  15 // i.e. an interval might look like [1,20), [50,65), [1000,1001).  Each
  16 // individual range is represented as an instance of LiveRange, and the whole
  17 // interval is represented as an instance of LiveInterval.
  18 //
  19 //===----------------------------------------------------------------------===//
  20
  21 #ifndef LLVM_CODEGEN_LIVEINTERVAL_H
  22 #define LLVM_CODEGEN_LIVEINTERVAL_H
  23
  24 #include "llvm/ADT/SmallVector.h"
  25 #include "llvm/Support/Allocator.h"
  26 #include "llvm/Support/AlignOf.h"
  27 #include <cassert>
  28 #include <climits>
  29
  30 namespace llvm {
  31   class MachineInstr;
  32   class MachineRegisterInfo;
  33   class TargetRegisterInfo;
  34   class raw_ostream;
  35
  36   /// VNInfo - Value Number Information.
  37   /// This class holds information about a machine level values, including
  38   /// definition and use points.
  39   ///
  40   /// Care must be taken in interpreting the def index of the value. The
  41   /// following rules apply:
  42   ///
  43   /// If the isDefAccurate() method returns false then def does not contain the
  44   /// index of the defining MachineInstr, or even (necessarily) to a
  45   /// MachineInstr at all. In general such a def index is not meaningful
  46   /// and should not be used. The exception is that, for values originally
  47   /// defined by PHI instructions, after PHI elimination def will contain the
  48   /// index of the MBB in which the PHI originally existed. This can be used
  49   /// to insert code (spills or copies) which deals with the value, which will
  50   /// be live in to the block.
  51   class VNInfo {
  52   private:
  53     enum {
  54       HAS_PHI_KILL    = 1,
  55       REDEF_BY_EC     = 1 << 1,
  56       IS_PHI_DEF      = 1 << 2,
  57       IS_UNUSED       = 1 << 3,
  58       IS_DEF_ACCURATE = 1 << 4
  59     };
  60
  61     unsigned char flags;
  62     union {
  63       MachineInstr *copy;
  64       unsigned reg;
  65     } cr;
  66
  67   public:
  68     /// Holds information about individual kills.
  69     struct KillInfo {
  70       bool isPHIKill : 1;
  71       unsigned killIdx : 31;
  72
  73       KillInfo(bool isPHIKill, unsigned killIdx)
  74         : isPHIKill(isPHIKill), killIdx(killIdx) {
  75
  76         assert(killIdx != 0 && "Zero kill indices are no longer permitted.");
  77       }
  78
  79     };
  80
  81     typedef SmallVector<KillInfo, 4> KillSet;
  82
  83     /// The ID number of this value.
  84     unsigned id;
  85
  86     /// The index of the defining instruction (if isDefAccurate() returns true).
  87     unsigned def;
  88
  89     KillSet kills;
  90
  91     VNInfo()
  92       : flags(IS_UNUSED), id(~1U), def(0) { cr.copy = 0; }
  93
  94     /// VNInfo constructor.
  95     /// d is presumed to point to the actual defining instr. If it doesn't
  96     /// setIsDefAccurate(false) should be called after construction.
  97     VNInfo(unsigned i, unsigned d, MachineInstr *c)
  98       : flags(IS_DEF_ACCURATE), id(i), def(d) { cr.copy = c; }
  99
 100     /// VNInfo construtor, copies values from orig, except for the value number.
 101     VNInfo(unsigned i, const VNInfo &orig)
 102       : flags(orig.flags), cr(orig.cr), id(i), def(orig.def), kills(orig.kills)
 103     { }
 104
 105     /// Copy from the parameter into this VNInfo.
 106     void copyFrom(VNInfo &src) {
 107       flags = src.flags;
 108       cr = src.cr;
 109       def = src.def;
 110       kills = src.kills;
 111     }
 112
 113     /// Used for copying value number info.
 114     unsigned getFlags() const { return flags; }
 115     void setFlags(unsigned flags) { this->flags = flags; }
 116
 117     /// For a register interval, if this VN was definied by a copy instr
 118     /// getCopy() returns a pointer to it, otherwise returns 0.
 119     /// For a stack interval the behaviour of this method is undefined.
 120     MachineInstr* getCopy() const { return cr.copy; }
 121     /// For a register interval, set the copy member.
 122     /// This method should not be called on stack intervals as it may lead to
 123     /// undefined behavior.
 124     void setCopy(MachineInstr *c) { cr.copy = c; }
 125
 126     /// For a stack interval, returns the reg which this stack interval was
 127     /// defined from.
 128     /// For a register interval the behaviour of this method is undefined.
 129     unsigned getReg() const { return cr.reg; }
 130     /// For a stack interval, set the defining register.
 131     /// This method should not be called on register intervals as it may lead
 132     /// to undefined behaviour.
 133     void setReg(unsigned reg) { cr.reg = reg; }
 134
 135     /// Returns true if one or more kills are PHI nodes.
 136     bool hasPHIKill() const { return flags & HAS_PHI_KILL; }
 137     void setHasPHIKill(bool hasKill) {
 138       if (hasKill)
 139         flags |= HAS_PHI_KILL;
 140       else
 141         flags &= ~HAS_PHI_KILL;
 142     }
 143
 144     /// Returns true if this value is re-defined by an early clobber somewhere
 145     /// during the live range.
 146     bool hasRedefByEC() const { return flags & REDEF_BY_EC; }
 147     void setHasRedefByEC(bool hasRedef) {
 148       if (hasRedef)
 149         flags |= REDEF_BY_EC;
 150       else
 151         flags &= ~REDEF_BY_EC;
 152     }
 153
 154     /// Returns true if this value is defined by a PHI instruction (or was,
 155     /// PHI instrucions may have been eliminated).
 156     bool isPHIDef() const { return flags & IS_PHI_DEF; }
 157     void setIsPHIDef(bool phiDef) {
 158       if (phiDef)
 159         flags |= IS_PHI_DEF;
 160       else
 161         flags &= ~IS_PHI_DEF;
 162     }
 163
 164     /// Returns true if this value is unused.
 165     bool isUnused() const { return flags & IS_UNUSED; }
 166     void setIsUnused(bool unused) {
 167       if (unused)
 168         flags |= IS_UNUSED;
 169       else
 170         flags &= ~IS_UNUSED;
 171     }
 172
 173     /// Returns true if the def is accurate.
 174     bool isDefAccurate() const { return flags & IS_DEF_ACCURATE; }
 175     void setIsDefAccurate(bool defAccurate) {
 176       if (defAccurate)
 177         flags |= IS_DEF_ACCURATE;
 178       else
 179         flags &= ~IS_DEF_ACCURATE;
 180     }
 181
 182   };
 183
 184   inline bool operator<(const VNInfo::KillInfo &k1, const VNInfo::KillInfo &k2){
 185     return k1.killIdx < k2.killIdx;
 186   }
 187
 188   inline bool operator<(const VNInfo::KillInfo &k, unsigned idx) {
 189     return k.killIdx < idx;
 190   }
 191
 192   inline bool operator<(unsigned idx, const VNInfo::KillInfo &k) {
 193     return idx < k.killIdx;
 194   }
 195
 196   /// LiveRange structure - This represents a simple register range in the
 197   /// program, with an inclusive start point and an exclusive end point.
 198   /// These ranges are rendered as [start,end).
 199   struct LiveRange {
 200     unsigned start;  // Start point of the interval (inclusive)
 201     unsigned end;    // End point of the interval (exclusive)
 202     VNInfo *valno;   // identifier for the value contained in this interval.
 203
 204     LiveRange(unsigned S, unsigned E, VNInfo *V) : start(S), end(E), valno(V) {
 205       assert(S < E && "Cannot create empty or backwards range");
 206     }
 207
 208     /// contains - Return true if the index is covered by this range.
 209     ///
 210     bool contains(unsigned I) const {
 211       return start <= I && I < end;
 212     }
 213
 214     bool operator<(const LiveRange &LR) const {
 215       return start < LR.start || (start == LR.start && end < LR.end);
 216     }
 217     bool operator==(const LiveRange &LR) const {
 218       return start == LR.start && end == LR.end;
 219     }
 220
 221     void dump() const;
 222     void print(raw_ostream &os) const;
 223
 224   private:
 225     LiveRange(); // DO NOT IMPLEMENT
 226   };
 227
 228   raw_ostream& operator<<(raw_ostream& os, const LiveRange &LR);
 229
 230
 231   inline bool operator<(unsigned V, const LiveRange &LR) {
 232     return V < LR.start;
 233   }
 234
 235   inline bool operator<(const LiveRange &LR, unsigned V) {
 236     return LR.start < V;
 237   }
 238
 239   /// LiveInterval - This class represents some number of live ranges for a
 240   /// register or value.  This class also contains a bit of register allocator
 241   /// state.
 242   class LiveInterval {
 243   public:
 244
 245     typedef SmallVector<LiveRange,4> Ranges;
 246     typedef SmallVector<VNInfo*,4> VNInfoList;
 247
 248     unsigned reg;        // the register or stack slot of this interval
 249                          // if the top bits is set, it represents a stack slot.
 250     float weight;        // weight of this interval
 251     Ranges ranges;       // the ranges in which this register is live
 252     VNInfoList valnos;   // value#'s
 253
 254     struct InstrSlots {
 255       enum {
 256         LOAD  = 0,
 257         USE   = 1,
 258         DEF   = 2,
 259         STORE = 3,
 260         NUM   = 4
 261       };
 262
 263       static unsigned scale(unsigned slot, unsigned factor) {
 264         unsigned index = slot / NUM,
 265                  offset = slot % NUM;
 266         assert(index <= ~0U / (factor * NUM) &&
 267                "Rescaled interval would overflow");
 268         return index * NUM * factor + offset;
 269       }
 270
 271     };
 272
 273     LiveInterval(unsigned Reg, float Weight, bool IsSS = false)
 274       : reg(Reg), weight(Weight) {
 275       if (IsSS)
 276         reg = reg | (1U << (sizeof(unsigned)*CHAR_BIT-1));
 277     }
 278
 279     typedef Ranges::iterator iterator;
 280     iterator begin() { return ranges.begin(); }
 281     iterator end()   { return ranges.end(); }
 282
 283     typedef Ranges::const_iterator const_iterator;
 284     const_iterator begin() const { return ranges.begin(); }
 285     const_iterator end() const  { return ranges.end(); }
 286
 287     typedef VNInfoList::iterator vni_iterator;
 288     vni_iterator vni_begin() { return valnos.begin(); }
 289     vni_iterator vni_end() { return valnos.end(); }
 290
 291     typedef VNInfoList::const_iterator const_vni_iterator;
 292     const_vni_iterator vni_begin() const { return valnos.begin(); }
 293     const_vni_iterator vni_end() const { return valnos.end(); }
 294
 295     /// advanceTo - Advance the specified iterator to point to the LiveRange
 296     /// containing the specified position, or end() if the position is past the
 297     /// end of the interval.  If no LiveRange contains this position, but the
 298     /// position is in a hole, this method returns an iterator pointing the the
 299     /// LiveRange immediately after the hole.
 300     iterator advanceTo(iterator I, unsigned Pos) {
 301       if (Pos >= endNumber())
 302         return end();
 303       while (I->end <= Pos) ++I;
 304       return I;
 305     }
 306
 307     void clear() {
 308       while (!valnos.empty()) {
 309         VNInfo *VNI = valnos.back();
 310         valnos.pop_back();
 311         VNI->~VNInfo();
 312       }
 313
 314       ranges.clear();
 315     }
 316
 317     /// isStackSlot - Return true if this is a stack slot interval.
 318     ///
 319     bool isStackSlot() const {
 320       return reg & (1U << (sizeof(unsigned)*CHAR_BIT-1));
 321     }
 322
 323     /// getStackSlotIndex - Return stack slot index if this is a stack slot
 324     /// interval.
 325     int getStackSlotIndex() const {
 326       assert(isStackSlot() && "Interval is not a stack slot interval!");
 327       return reg & ~(1U << (sizeof(unsigned)*CHAR_BIT-1));
 328     }
 329
 330     bool hasAtLeastOneValue() const { return !valnos.empty(); }
 331
 332     bool containsOneValue() const { return valnos.size() == 1; }
 333
 334     unsigned getNumValNums() const { return (unsigned)valnos.size(); }
 335
 336     /// getValNumInfo - Returns pointer to the specified val#.
 337     ///
 338     inline VNInfo *getValNumInfo(unsigned ValNo) {
 339       return valnos[ValNo];
 340     }
 341     inline const VNInfo *getValNumInfo(unsigned ValNo) const {
 342       return valnos[ValNo];
 343     }
 344
 345     /// getNextValue - Create a new value number and return it.  MIIdx specifies
 346     /// the instruction that defines the value number.
 347     VNInfo *getNextValue(unsigned MIIdx, MachineInstr *CopyMI,
 348                          bool isDefAccurate, BumpPtrAllocator &VNInfoAllocator){
 349
 350       assert(MIIdx != ~0u && MIIdx != ~1u &&
 351              "PHI def / unused flags should now be passed explicitly.");
 352       VNInfo *VNI =
 353         static_cast<VNInfo*>(VNInfoAllocator.Allocate((unsigned)sizeof(VNInfo),
 354                                                       alignof<VNInfo>()));
 355       new (VNI) VNInfo((unsigned)valnos.size(), MIIdx, CopyMI);
 356       VNI->setIsDefAccurate(isDefAccurate);
 357       valnos.push_back(VNI);
 358       return VNI;
 359     }
 360
 361     /// Create a copy of the given value. The new value will be identical except
 362     /// for the Value number.
 363     VNInfo *createValueCopy(const VNInfo *orig,
 364                             BumpPtrAllocator &VNInfoAllocator) {
 365
 366       VNInfo *VNI =
 367         static_cast<VNInfo*>(VNInfoAllocator.Allocate((unsigned)sizeof(VNInfo),
 368                                                       alignof<VNInfo>()));
 369
 370       new (VNI) VNInfo((unsigned)valnos.size(), *orig);
 371       valnos.push_back(VNI);
 372       return VNI;
 373     }
 374
 375     /// addKill - Add a kill instruction index to the specified value
 376     /// number.
 377     static void addKill(VNInfo *VNI, unsigned KillIdx, bool phiKill) {
 378       VNInfo::KillSet &kills = VNI->kills;
 379       VNInfo::KillInfo newKill(phiKill, KillIdx);
 380       if (kills.empty()) {
 381         kills.push_back(newKill);
 382       } else {
 383         VNInfo::KillSet::iterator
 384           I = std::lower_bound(kills.begin(), kills.end(), newKill);
 385         kills.insert(I, newKill);
 386       }
 387     }
 388
 389     /// addKills - Add a number of kills into the VNInfo kill vector. If this
 390     /// interval is live at a kill point, then the kill is not added.
 391     void addKills(VNInfo *VNI, const VNInfo::KillSet &kills) {
 392       for (unsigned i = 0, e = static_cast<unsigned>(kills.size());
 393            i != e; ++i) {
 394         const VNInfo::KillInfo &Kill = kills[i];
 395         if (!liveBeforeAndAt(Kill.killIdx)) {
 396           VNInfo::KillSet::iterator
 397             I = std::lower_bound(VNI->kills.begin(), VNI->kills.end(), Kill);
 398           VNI->kills.insert(I, Kill);
 399         }
 400       }
 401     }
 402
 403     /// removeKill - Remove the specified kill from the list of kills of
 404     /// the specified val#.
 405     static bool removeKill(VNInfo *VNI, unsigned KillIdx) {
 406       VNInfo::KillSet &kills = VNI->kills;
 407       VNInfo::KillSet::iterator
 408         I = std::lower_bound(kills.begin(), kills.end(), KillIdx);
 409       if (I != kills.end() && I->killIdx == KillIdx) {
 410         kills.erase(I);
 411         return true;
 412       }
 413       return false;
 414     }
 415
 416     /// removeKills - Remove all the kills in specified range
 417     /// [Start, End] of the specified val#.
 418     static void removeKills(VNInfo *VNI, unsigned Start, unsigned End) {
 419       VNInfo::KillSet &kills = VNI->kills;
 420
 421       VNInfo::KillSet::iterator
 422         I = std::lower_bound(kills.begin(), kills.end(), Start);
 423       VNInfo::KillSet::iterator
 424         E = std::upper_bound(kills.begin(), kills.end(), End);
 425       kills.erase(I, E);
 426     }
 427
 428     /// isKill - Return true if the specified index is a kill of the
 429     /// specified val#.
 430     static bool isKill(const VNInfo *VNI, unsigned KillIdx) {
 431       const VNInfo::KillSet &kills = VNI->kills;
 432       VNInfo::KillSet::const_iterator
 433         I = std::lower_bound(kills.begin(), kills.end(), KillIdx);
 434       return I != kills.end() && I->killIdx == KillIdx;
 435     }
 436
 437     /// isOnlyLROfValNo - Return true if the specified live range is the only
 438     /// one defined by the its val#.
 439     bool isOnlyLROfValNo(const LiveRange *LR) {
 440       for (const_iterator I = begin(), E = end(); I != E; ++I) {
 441         const LiveRange *Tmp = I;
 442         if (Tmp != LR && Tmp->valno == LR->valno)
 443           return false;
 444       }
 445       return true;
 446     }
 447
 448     /// MergeValueNumberInto - This method is called when two value nubmers
 449     /// are found to be equivalent.  This eliminates V1, replacing all
 450     /// LiveRanges with the V1 value number with the V2 value number.  This can
 451     /// cause merging of V1/V2 values numbers and compaction of the value space.
 452     VNInfo* MergeValueNumberInto(VNInfo *V1, VNInfo *V2);
 453
 454     /// MergeInClobberRanges - For any live ranges that are not defined in the
 455     /// current interval, but are defined in the Clobbers interval, mark them
 456     /// used with an unknown definition value. Caller must pass in reference to
 457     /// VNInfoAllocator since it will create a new val#.
 458     void MergeInClobberRanges(const LiveInterval &Clobbers,
 459                               BumpPtrAllocator &VNInfoAllocator);
 460
 461     /// MergeInClobberRange - Same as MergeInClobberRanges except it merge in a
 462     /// single LiveRange only.
 463     void MergeInClobberRange(unsigned Start, unsigned End,
 464                              BumpPtrAllocator &VNInfoAllocator);
 465
 466     /// MergeValueInAsValue - Merge all of the live ranges of a specific val#
 467     /// in RHS into this live interval as the specified value number.
 468     /// The LiveRanges in RHS are allowed to overlap with LiveRanges in the
 469     /// current interval, it will replace the value numbers of the overlaped
 470     /// live ranges with the specified value number.
 471     void MergeRangesInAsValue(const LiveInterval &RHS, VNInfo *LHSValNo);
 472
 473     /// MergeValueInAsValue - Merge all of the live ranges of a specific val#
 474     /// in RHS into this live interval as the specified value number.
 475     /// The LiveRanges in RHS are allowed to overlap with LiveRanges in the
 476     /// current interval, but only if the overlapping LiveRanges have the
 477     /// specified value number.
 478     void MergeValueInAsValue(const LiveInterval &RHS,
 479                              const VNInfo *RHSValNo, VNInfo *LHSValNo);
 480
 481     /// Copy - Copy the specified live interval. This copies all the fields
 482     /// except for the register of the interval.
 483     void Copy(const LiveInterval &RHS, MachineRegisterInfo *MRI,
 484               BumpPtrAllocator &VNInfoAllocator);
 485
 486     bool empty() const { return ranges.empty(); }
 487
 488     /// beginNumber - Return the lowest numbered slot covered by interval.
 489     unsigned beginNumber() const {
 490       if (empty())
 491         return 0;
 492       return ranges.front().start;
 493     }
 494
 495     /// endNumber - return the maximum point of the interval of the whole,
 496     /// exclusive.
 497     unsigned endNumber() const {
 498       if (empty())
 499         return 0;
 500       return ranges.back().end;
 501     }
 502
 503     bool expiredAt(unsigned index) const {
 504       return index >= endNumber();
 505     }
 506
 507     bool liveAt(unsigned index) const;
 508
 509     // liveBeforeAndAt - Check if the interval is live at the index and the
 510     // index just before it. If index is liveAt, check if it starts a new live
 511     // range.If it does, then check if the previous live range ends at index-1.
 512     bool liveBeforeAndAt(unsigned index) const;
 513
 514     /// getLiveRangeContaining - Return the live range that contains the
 515     /// specified index, or null if there is none.
 516     const LiveRange *getLiveRangeContaining(unsigned Idx) const {
 517       const_iterator I = FindLiveRangeContaining(Idx);
 518       return I == end() ? 0 : &*I;
 519     }
 520
 521     /// getLiveRangeContaining - Return the live range that contains the
 522     /// specified index, or null if there is none.
 523     LiveRange *getLiveRangeContaining(unsigned Idx) {
 524       iterator I = FindLiveRangeContaining(Idx);
 525       return I == end() ? 0 : &*I;
 526     }
 527
 528     /// FindLiveRangeContaining - Return an iterator to the live range that
 529     /// contains the specified index, or end() if there is none.
 530     const_iterator FindLiveRangeContaining(unsigned Idx) const;
 531
 532     /// FindLiveRangeContaining - Return an iterator to the live range that
 533     /// contains the specified index, or end() if there is none.
 534     iterator FindLiveRangeContaining(unsigned Idx);
 535
 536     /// findDefinedVNInfo - Find the VNInfo that's defined at the specified
 537     /// index (register interval) or defined by the specified register (stack
 538     /// inteval).
 539     VNInfo *findDefinedVNInfo(unsigned DefIdxOrReg) const;
 540
 541     /// overlaps - Return true if the intersection of the two live intervals is
 542     /// not empty.
 543     bool overlaps(const LiveInterval& other) const {
 544       return overlapsFrom(other, other.begin());
 545     }
 546
 547     /// overlaps - Return true if the live interval overlaps a range specified
 548     /// by [Start, End).
 549     bool overlaps(unsigned Start, unsigned End) const;
 550
 551     /// overlapsFrom - Return true if the intersection of the two live intervals
 552     /// is not empty.  The specified iterator is a hint that we can begin
 553     /// scanning the Other interval starting at I.
 554     bool overlapsFrom(const LiveInterval& other, const_iterator I) const;
 555
 556     /// addRange - Add the specified LiveRange to this interval, merging
 557     /// intervals as appropriate.  This returns an iterator to the inserted live
 558     /// range (which may have grown since it was inserted.
 559     void addRange(LiveRange LR) {
 560       addRangeFrom(LR, ranges.begin());
 561     }
 562
 563     /// join - Join two live intervals (this, and other) together.  This applies
 564     /// mappings to the value numbers in the LHS/RHS intervals as specified.  If
 565     /// the intervals are not joinable, this aborts.
 566     void join(LiveInterval &Other, const int *ValNoAssignments,
 567               const int *RHSValNoAssignments,
 568               SmallVector<VNInfo*, 16> &NewVNInfo,
 569               MachineRegisterInfo *MRI);
 570
 571     /// isInOneLiveRange - Return true if the range specified is entirely in the
 572     /// a single LiveRange of the live interval.
 573     bool isInOneLiveRange(unsigned Start, unsigned End);
 574
 575     /// removeRange - Remove the specified range from this interval.  Note that
 576     /// the range must be a single LiveRange in its entirety.
 577     void removeRange(unsigned Start, unsigned End, bool RemoveDeadValNo = false);
 578
 579     void removeRange(LiveRange LR, bool RemoveDeadValNo = false) {
 580       removeRange(LR.start, LR.end, RemoveDeadValNo);
 581     }
 582
 583     /// removeValNo - Remove all the ranges defined by the specified value#.
 584     /// Also remove the value# from value# list.
 585     void removeValNo(VNInfo *ValNo);
 586
 587     /// scaleNumbering - Renumber VNI and ranges to provide gaps for new
 588     /// instructions.
 589     void scaleNumbering(unsigned factor);
 590
 591     /// getSize - Returns the sum of sizes of all the LiveRange's.
 592     ///
 593     unsigned getSize() const;
 594
 595     /// ComputeJoinedWeight - Set the weight of a live interval after
 596     /// Other has been merged into it.
 597     void ComputeJoinedWeight(const LiveInterval &Other);
 598
 599     bool operator<(const LiveInterval& other) const {
 600       return beginNumber() < other.beginNumber();
 601     }
 602
 603     void print(raw_ostream &OS, const TargetRegisterInfo *TRI = 0) const;
 604     void dump() const;
 605
 606   private:
 607
 608     Ranges::iterator addRangeFrom(LiveRange LR, Ranges::iterator From);
 609     void extendIntervalEndTo(Ranges::iterator I, unsigned NewEnd);
 610     Ranges::iterator extendIntervalStartTo(Ranges::iterator I, unsigned NewStr);
 611     LiveInterval& operator=(const LiveInterval& rhs); // DO NOT IMPLEMENT
 612
 613   };
 614
 615   inline raw_ostream &operator<<(raw_ostream &OS, const LiveInterval &LI) {
 616     LI.print(OS);
 617     return OS;
 618   }
 619 }
 620
 621 #endif