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/DenseMapInfo.h"
  25 #include "llvm/ADT/SmallVector.h"
  26 #include "llvm/Support/Allocator.h"
  27 #include "llvm/Support/AlignOf.h"
  28 #include <cassert>
  29 #include <climits>
  30
  31 namespace llvm {
  32   class MachineInstr;
  33   class MachineRegisterInfo;
  34   class TargetRegisterInfo;
  35   class raw_ostream;
  36
  37   /// MachineInstrIndex - An opaque wrapper around machine indexes.
  38   class MachineInstrIndex {
  39     friend class VNInfo;
  40     friend class LiveInterval;
  41     friend class LiveIntervals;
  42     friend struct DenseMapInfo<MachineInstrIndex>;
  43
  44   public:
  45
  46     enum Slot { LOAD, USE, DEF, STORE, NUM };
  47
  48   private:
  49
  50     unsigned index;
  51
  52     static const unsigned PHI_BIT = 1 << 31;
  53
  54   public:
  55
  56     /// Construct a default MachineInstrIndex pointing to a reserved index.
  57     MachineInstrIndex() : index(0) {}
  58
  59     /// Construct an index from the given index, pointing to the given slot.
  60     MachineInstrIndex(MachineInstrIndex m, Slot s)
  61       : index((m.index / NUM) * NUM + s) {}
  62
  63     /// Print this index to the given raw_ostream.
  64     void print(raw_ostream &os) const;
  65
  66     /// Print this index to the given std::ostream.
  67     void print(std::ostream &os) const;
  68
  69     /// Compare two MachineInstrIndex objects for equality.
  70     bool operator==(MachineInstrIndex other) const {
  71       return ((index & ~PHI_BIT) == (other.index & ~PHI_BIT));
  72     }
  73     /// Compare two MachineInstrIndex objects for inequality.
  74     bool operator!=(MachineInstrIndex other) const {
  75       return ((index & ~PHI_BIT) != (other.index & ~PHI_BIT));
  76     }
  77
  78     /// Compare two MachineInstrIndex objects. Return true if the first index
  79     /// is strictly lower than the second.
  80     bool operator<(MachineInstrIndex other) const {
  81       return ((index & ~PHI_BIT) < (other.index & ~PHI_BIT));
  82     }
  83     /// Compare two MachineInstrIndex objects. Return true if the first index
  84     /// is lower than, or equal to, the second.
  85     bool operator<=(MachineInstrIndex other) const {
  86       return ((index & ~PHI_BIT) <= (other.index & ~PHI_BIT));
  87     }
  88
  89     /// Compare two MachineInstrIndex objects. Return true if the first index
  90     /// is greater than the second.
  91     bool operator>(MachineInstrIndex other) const {
  92       return ((index & ~PHI_BIT) > (other.index & ~PHI_BIT));
  93     }
  94
  95     /// Compare two MachineInstrIndex objects. Return true if the first index
  96     /// is greater than, or equal to, the second.
  97     bool operator>=(MachineInstrIndex other) const {
  98       return ((index & ~PHI_BIT) >= (other.index & ~PHI_BIT));
  99     }
 100
 101     /// Returns true if this index represents a load.
 102     bool isLoad() const {
 103       return ((index % NUM) == LOAD);
 104     }
 105
 106     /// Returns true if this index represents a use.
 107     bool isUse() const {
 108       return ((index % NUM) == USE);
 109     }
 110
 111     /// Returns true if this index represents a def.
 112     bool isDef() const {
 113       return ((index % NUM) == DEF);
 114     }
 115
 116     /// Returns true if this index represents a store.
 117     bool isStore() const {
 118       return ((index % NUM) == STORE);
 119     }
 120
 121     /// Returns the slot for this MachineInstrIndex.
 122     Slot getSlot() const {
 123       return static_cast<Slot>(index % NUM);
 124     }
 125
 126     /// Returns true if this index represents a non-PHI use/def.
 127     bool isNonPHIIndex() const {
 128       return ((index & PHI_BIT) == 0);
 129     }
 130
 131     /// Returns true if this index represents a PHI use/def.
 132     bool isPHIIndex() const {
 133       return ((index & PHI_BIT) == PHI_BIT);
 134     }
 135
 136   private:
 137
 138     /// Construct an index from the given index, with its PHI kill marker set.
 139     MachineInstrIndex(bool phi, MachineInstrIndex o) : index(o.index) {
 140       if (phi)
 141         index |= PHI_BIT;
 142       else
 143         index &= ~PHI_BIT;
 144     }
 145
 146     explicit MachineInstrIndex(unsigned idx)
 147       : index(idx & ~PHI_BIT) {}
 148
 149     MachineInstrIndex(bool phi, unsigned idx)
 150       : index(idx & ~PHI_BIT) {
 151       if (phi)
 152         index |= PHI_BIT;
 153     }
 154
 155     MachineInstrIndex(bool phi, unsigned idx, Slot slot)
 156       : index(((idx / NUM) * NUM + slot) & ~PHI_BIT) {
 157       if (phi)
 158         index |= PHI_BIT;
 159     }
 160
 161     MachineInstrIndex nextSlot() const {
 162       assert((index & PHI_BIT) == ((index + 1) & PHI_BIT) &&
 163              "Index out of bounds.");
 164       return MachineInstrIndex(index + 1);
 165     }
 166
 167     MachineInstrIndex nextIndex() const {
 168       assert((index & PHI_BIT) == ((index + NUM) & PHI_BIT) &&
 169              "Index out of bounds.");
 170       return MachineInstrIndex(index + NUM);
 171     }
 172
 173     MachineInstrIndex prevSlot() const {
 174       assert((index & PHI_BIT) == ((index - 1) & PHI_BIT) &&
 175              "Index out of bounds.");
 176       return MachineInstrIndex(index - 1);
 177     }
 178
 179     MachineInstrIndex prevIndex() const {
 180       assert((index & PHI_BIT) == ((index - NUM) & PHI_BIT) &&
 181              "Index out of bounds.");
 182       return MachineInstrIndex(index - NUM);
 183     }
 184
 185     int distance(MachineInstrIndex other) const {
 186       return (other.index & ~PHI_BIT) - (index & ~PHI_BIT);
 187     }
 188
 189     /// Returns an unsigned number suitable as an index into a
 190     /// vector over all instructions.
 191     unsigned getVecIndex() const {
 192       return (index & ~PHI_BIT) / NUM;
 193     }
 194
 195     /// Scale this index by the given factor.
 196     MachineInstrIndex scale(unsigned factor) const {
 197       unsigned i = (index & ~PHI_BIT) / NUM,
 198                o = (index % ~PHI_BIT) % NUM;
 199       assert(index <= (~0U & ~PHI_BIT) / (factor * NUM) &&
 200              "Rescaled interval would overflow");
 201       return MachineInstrIndex(i * NUM * factor, o);
 202     }
 203
 204     static MachineInstrIndex emptyKey() {
 205       return MachineInstrIndex(true, 0x7fffffff);
 206     }
 207
 208     static MachineInstrIndex tombstoneKey() {
 209       return MachineInstrIndex(true, 0x7ffffffe);
 210     }
 211
 212     static unsigned getHashValue(const MachineInstrIndex &v) {
 213       return v.index * 37;
 214     }
 215
 216   };
 217
 218   inline raw_ostream& operator<<(raw_ostream &os, MachineInstrIndex mi) {
 219     mi.print(os);
 220     return os;
 221   }
 222
 223   /// Densemap specialization for MachineInstrIndex.
 224   template <>
 225   struct DenseMapInfo<MachineInstrIndex> {
 226     static inline MachineInstrIndex getEmptyKey() {
 227       return MachineInstrIndex::emptyKey();
 228     }
 229     static inline MachineInstrIndex getTombstoneKey() {
 230       return MachineInstrIndex::tombstoneKey();
 231     }
 232     static inline unsigned getHashValue(const MachineInstrIndex &v) {
 233       return MachineInstrIndex::getHashValue(v);
 234     }
 235     static inline bool isEqual(const MachineInstrIndex &LHS,
 236                                const MachineInstrIndex &RHS) {
 237       return (LHS == RHS);
 238     }
 239     static inline bool isPod() { return true; }
 240   };
 241
 242
 243   /// VNInfo - Value Number Information.
 244   /// This class holds information about a machine level values, including
 245   /// definition and use points.
 246   ///
 247   /// Care must be taken in interpreting the def index of the value. The
 248   /// following rules apply:
 249   ///
 250   /// If the isDefAccurate() method returns false then def does not contain the
 251   /// index of the defining MachineInstr, or even (necessarily) to a
 252   /// MachineInstr at all. In general such a def index is not meaningful
 253   /// and should not be used. The exception is that, for values originally
 254   /// defined by PHI instructions, after PHI elimination def will contain the
 255   /// index of the MBB in which the PHI originally existed. This can be used
 256   /// to insert code (spills or copies) which deals with the value, which will
 257   /// be live in to the block.
 258   class VNInfo {
 259   private:
 260     enum {
 261       HAS_PHI_KILL    = 1,
 262       REDEF_BY_EC     = 1 << 1,
 263       IS_PHI_DEF      = 1 << 2,
 264       IS_UNUSED       = 1 << 3,
 265       IS_DEF_ACCURATE = 1 << 4
 266     };
 267
 268     unsigned char flags;
 269     union {
 270       MachineInstr *copy;
 271       unsigned reg;
 272     } cr;
 273
 274   public:
 275
 276     typedef SmallVector<MachineInstrIndex, 4> KillSet;
 277
 278     /// The ID number of this value.
 279     unsigned id;
 280
 281     /// The index of the defining instruction (if isDefAccurate() returns true).
 282     MachineInstrIndex def;
 283
 284     KillSet kills;
 285
 286     VNInfo()
 287       : flags(IS_UNUSED), id(~1U) { cr.copy = 0; }
 288
 289     /// VNInfo constructor.
 290     /// d is presumed to point to the actual defining instr. If it doesn't
 291     /// setIsDefAccurate(false) should be called after construction.
 292     VNInfo(unsigned i, MachineInstrIndex d, MachineInstr *c)
 293       : flags(IS_DEF_ACCURATE), id(i), def(d) { cr.copy = c; }
 294
 295     /// VNInfo construtor, copies values from orig, except for the value number.
 296     VNInfo(unsigned i, const VNInfo &orig)
 297       : flags(orig.flags), cr(orig.cr), id(i), def(orig.def), kills(orig.kills)
 298     { }
 299
 300     /// Copy from the parameter into this VNInfo.
 301     void copyFrom(VNInfo &src) {
 302       flags = src.flags;
 303       cr = src.cr;
 304       def = src.def;
 305       kills = src.kills;
 306     }
 307
 308     /// Used for copying value number info.
 309     unsigned getFlags() const { return flags; }
 310     void setFlags(unsigned flags) { this->flags = flags; }
 311
 312     /// For a register interval, if this VN was definied by a copy instr
 313     /// getCopy() returns a pointer to it, otherwise returns 0.
 314     /// For a stack interval the behaviour of this method is undefined.
 315     MachineInstr* getCopy() const { return cr.copy; }
 316     /// For a register interval, set the copy member.
 317     /// This method should not be called on stack intervals as it may lead to
 318     /// undefined behavior.
 319     void setCopy(MachineInstr *c) { cr.copy = c; }
 320
 321     /// For a stack interval, returns the reg which this stack interval was
 322     /// defined from.
 323     /// For a register interval the behaviour of this method is undefined.
 324     unsigned getReg() const { return cr.reg; }
 325     /// For a stack interval, set the defining register.
 326     /// This method should not be called on register intervals as it may lead
 327     /// to undefined behaviour.
 328     void setReg(unsigned reg) { cr.reg = reg; }
 329
 330     /// Returns true if one or more kills are PHI nodes.
 331     bool hasPHIKill() const { return flags & HAS_PHI_KILL; }
 332     /// Set the PHI kill flag on this value.
 333     void setHasPHIKill(bool hasKill) {
 334       if (hasKill)
 335         flags |= HAS_PHI_KILL;
 336       else
 337         flags &= ~HAS_PHI_KILL;
 338     }
 339
 340     /// Returns true if this value is re-defined by an early clobber somewhere
 341     /// during the live range.
 342     bool hasRedefByEC() const { return flags & REDEF_BY_EC; }
 343     /// Set the "redef by early clobber" flag on this value.
 344     void setHasRedefByEC(bool hasRedef) {
 345       if (hasRedef)
 346         flags |= REDEF_BY_EC;
 347       else
 348         flags &= ~REDEF_BY_EC;
 349     }
 350
 351     /// Returns true if this value is defined by a PHI instruction (or was,
 352     /// PHI instrucions may have been eliminated).
 353     bool isPHIDef() const { return flags & IS_PHI_DEF; }
 354     /// Set the "phi def" flag on this value.
 355     void setIsPHIDef(bool phiDef) {
 356       if (phiDef)
 357         flags |= IS_PHI_DEF;
 358       else
 359         flags &= ~IS_PHI_DEF;
 360     }
 361
 362     /// Returns true if this value is unused.
 363     bool isUnused() const { return flags & IS_UNUSED; }
 364     /// Set the "is unused" flag on this value.
 365     void setIsUnused(bool unused) {
 366       if (unused)
 367         flags |= IS_UNUSED;
 368       else
 369         flags &= ~IS_UNUSED;
 370     }
 371
 372     /// Returns true if the def is accurate.
 373     bool isDefAccurate() const { return flags & IS_DEF_ACCURATE; }
 374     /// Set the "is def accurate" flag on this value.
 375     void setIsDefAccurate(bool defAccurate) {
 376       if (defAccurate)
 377         flags |= IS_DEF_ACCURATE;
 378       else
 379         flags &= ~IS_DEF_ACCURATE;
 380     }
 381
 382     /// Returns true if the given index is a kill of this value.
 383     bool isKill(MachineInstrIndex k) const {
 384       KillSet::const_iterator
 385         i = std::lower_bound(kills.begin(), kills.end(), k);
 386       return (i != kills.end() && *i == k);
 387     }
 388
 389     /// addKill - Add a kill instruction index to the specified value
 390     /// number.
 391     void addKill(MachineInstrIndex k) {
 392       if (kills.empty()) {
 393         kills.push_back(k);
 394       } else {
 395         KillSet::iterator
 396           i = std::lower_bound(kills.begin(), kills.end(), k);
 397         kills.insert(i, k);
 398       }
 399     }
 400
 401     /// Remove the specified kill index from this value's kills list.
 402     /// Returns true if the value was present, otherwise returns false.
 403     bool removeKill(MachineInstrIndex k) {
 404       KillSet::iterator i = std::lower_bound(kills.begin(), kills.end(), k);
 405       if (i != kills.end() && *i == k) {
 406         kills.erase(i);
 407         return true;
 408       }
 409       return false;
 410     }
 411
 412     /// Remove all kills in the range [s, e).
 413     void removeKills(MachineInstrIndex s, MachineInstrIndex e) {
 414       KillSet::iterator
 415         si = std::lower_bound(kills.begin(), kills.end(), s),
 416         se = std::upper_bound(kills.begin(), kills.end(), e);
 417
 418       kills.erase(si, se);
 419     }
 420
 421   };
 422
 423   /// LiveRange structure - This represents a simple register range in the
 424   /// program, with an inclusive start point and an exclusive end point.
 425   /// These ranges are rendered as [start,end).
 426   struct LiveRange {
 427     MachineInstrIndex start;  // Start point of the interval (inclusive)
 428     MachineInstrIndex end;    // End point of the interval (exclusive)
 429     VNInfo *valno;   // identifier for the value contained in this interval.
 430
 431     LiveRange(MachineInstrIndex S, MachineInstrIndex E, VNInfo *V)
 432       : start(S), end(E), valno(V) {
 433
 434       assert(S < E && "Cannot create empty or backwards range");
 435     }
 436
 437     /// contains - Return true if the index is covered by this range.
 438     ///
 439     bool contains(MachineInstrIndex I) const {
 440       return start <= I && I < end;
 441     }
 442
 443     /// containsRange - Return true if the given range, [S, E), is covered by
 444     /// this range.
 445     bool containsRange(MachineInstrIndex S, MachineInstrIndex E) const {
 446       assert((S < E) && "Backwards interval?");
 447       return (start <= S && S < end) && (start < E && E <= end);
 448     }
 449
 450     bool operator<(const LiveRange &LR) const {
 451       return start < LR.start || (start == LR.start && end < LR.end);
 452     }
 453     bool operator==(const LiveRange &LR) const {
 454       return start == LR.start && end == LR.end;
 455     }
 456
 457     void dump() const;
 458     void print(raw_ostream &os) const;
 459
 460   private:
 461     LiveRange(); // DO NOT IMPLEMENT
 462   };
 463
 464   raw_ostream& operator<<(raw_ostream& os, const LiveRange &LR);
 465
 466
 467   inline bool operator<(MachineInstrIndex V, const LiveRange &LR) {
 468     return V < LR.start;
 469   }
 470
 471   inline bool operator<(const LiveRange &LR, MachineInstrIndex V) {
 472     return LR.start < V;
 473   }
 474
 475   /// LiveInterval - This class represents some number of live ranges for a
 476   /// register or value.  This class also contains a bit of register allocator
 477   /// state.
 478   class LiveInterval {
 479   public:
 480
 481     typedef SmallVector<LiveRange,4> Ranges;
 482     typedef SmallVector<VNInfo*,4> VNInfoList;
 483
 484     unsigned reg;        // the register or stack slot of this interval
 485                          // if the top bits is set, it represents a stack slot.
 486     float weight;        // weight of this interval
 487     Ranges ranges;       // the ranges in which this register is live
 488     VNInfoList valnos;   // value#'s
 489
 490     struct InstrSlots {
 491       enum {
 492         LOAD  = 0,
 493         USE   = 1,
 494         DEF   = 2,
 495         STORE = 3,
 496         NUM   = 4
 497       };
 498
 499     };
 500
 501     LiveInterval(unsigned Reg, float Weight, bool IsSS = false)
 502       : reg(Reg), weight(Weight) {
 503       if (IsSS)
 504         reg = reg | (1U << (sizeof(unsigned)*CHAR_BIT-1));
 505     }
 506
 507     typedef Ranges::iterator iterator;
 508     iterator begin() { return ranges.begin(); }
 509     iterator end()   { return ranges.end(); }
 510
 511     typedef Ranges::const_iterator const_iterator;
 512     const_iterator begin() const { return ranges.begin(); }
 513     const_iterator end() const  { return ranges.end(); }
 514
 515     typedef VNInfoList::iterator vni_iterator;
 516     vni_iterator vni_begin() { return valnos.begin(); }
 517     vni_iterator vni_end() { return valnos.end(); }
 518
 519     typedef VNInfoList::const_iterator const_vni_iterator;
 520     const_vni_iterator vni_begin() const { return valnos.begin(); }
 521     const_vni_iterator vni_end() const { return valnos.end(); }
 522
 523     /// advanceTo - Advance the specified iterator to point to the LiveRange
 524     /// containing the specified position, or end() if the position is past the
 525     /// end of the interval.  If no LiveRange contains this position, but the
 526     /// position is in a hole, this method returns an iterator pointing the the
 527     /// LiveRange immediately after the hole.
 528     iterator advanceTo(iterator I, MachineInstrIndex Pos) {
 529       if (Pos >= endIndex())
 530         return end();
 531       while (I->end <= Pos) ++I;
 532       return I;
 533     }
 534
 535     void clear() {
 536       while (!valnos.empty()) {
 537         VNInfo *VNI = valnos.back();
 538         valnos.pop_back();
 539         VNI->~VNInfo();
 540       }
 541
 542       ranges.clear();
 543     }
 544
 545     /// isStackSlot - Return true if this is a stack slot interval.
 546     ///
 547     bool isStackSlot() const {
 548       return reg & (1U << (sizeof(unsigned)*CHAR_BIT-1));
 549     }
 550
 551     /// getStackSlotIndex - Return stack slot index if this is a stack slot
 552     /// interval.
 553     int getStackSlotIndex() const {
 554       assert(isStackSlot() && "Interval is not a stack slot interval!");
 555       return reg & ~(1U << (sizeof(unsigned)*CHAR_BIT-1));
 556     }
 557
 558     bool hasAtLeastOneValue() const { return !valnos.empty(); }
 559
 560     bool containsOneValue() const { return valnos.size() == 1; }
 561
 562     unsigned getNumValNums() const { return (unsigned)valnos.size(); }
 563
 564     /// getValNumInfo - Returns pointer to the specified val#.
 565     ///
 566     inline VNInfo *getValNumInfo(unsigned ValNo) {
 567       return valnos[ValNo];
 568     }
 569     inline const VNInfo *getValNumInfo(unsigned ValNo) const {
 570       return valnos[ValNo];
 571     }
 572
 573     /// getNextValue - Create a new value number and return it.  MIIdx specifies
 574     /// the instruction that defines the value number.
 575     VNInfo *getNextValue(MachineInstrIndex def, MachineInstr *CopyMI,
 576                          bool isDefAccurate, BumpPtrAllocator &VNInfoAllocator){
 577       VNInfo *VNI =
 578         static_cast<VNInfo*>(VNInfoAllocator.Allocate((unsigned)sizeof(VNInfo),
 579                                                       alignof<VNInfo>()));
 580       new (VNI) VNInfo((unsigned)valnos.size(), def, CopyMI);
 581       VNI->setIsDefAccurate(isDefAccurate);
 582       valnos.push_back(VNI);
 583       return VNI;
 584     }
 585
 586     /// Create a copy of the given value. The new value will be identical except
 587     /// for the Value number.
 588     VNInfo *createValueCopy(const VNInfo *orig,
 589                             BumpPtrAllocator &VNInfoAllocator) {
 590
 591       VNInfo *VNI =
 592         static_cast<VNInfo*>(VNInfoAllocator.Allocate((unsigned)sizeof(VNInfo),
 593                                                       alignof<VNInfo>()));
 594
 595       new (VNI) VNInfo((unsigned)valnos.size(), *orig);
 596       valnos.push_back(VNI);
 597       return VNI;
 598     }
 599
 600     /// addKills - Add a number of kills into the VNInfo kill vector. If this
 601     /// interval is live at a kill point, then the kill is not added.
 602     void addKills(VNInfo *VNI, const VNInfo::KillSet &kills) {
 603       for (unsigned i = 0, e = static_cast<unsigned>(kills.size());
 604            i != e; ++i) {
 605         if (!liveBeforeAndAt(kills[i])) {
 606           VNI->addKill(kills[i]);
 607         }
 608       }
 609     }
 610
 611     /// isOnlyLROfValNo - Return true if the specified live range is the only
 612     /// one defined by the its val#.
 613     bool isOnlyLROfValNo(const LiveRange *LR) {
 614       for (const_iterator I = begin(), E = end(); I != E; ++I) {
 615         const LiveRange *Tmp = I;
 616         if (Tmp != LR && Tmp->valno == LR->valno)
 617           return false;
 618       }
 619       return true;
 620     }
 621
 622     /// MergeValueNumberInto - This method is called when two value nubmers
 623     /// are found to be equivalent.  This eliminates V1, replacing all
 624     /// LiveRanges with the V1 value number with the V2 value number.  This can
 625     /// cause merging of V1/V2 values numbers and compaction of the value space.
 626     VNInfo* MergeValueNumberInto(VNInfo *V1, VNInfo *V2);
 627
 628     /// MergeInClobberRanges - For any live ranges that are not defined in the
 629     /// current interval, but are defined in the Clobbers interval, mark them
 630     /// used with an unknown definition value. Caller must pass in reference to
 631     /// VNInfoAllocator since it will create a new val#.
 632     void MergeInClobberRanges(const LiveInterval &Clobbers,
 633                               BumpPtrAllocator &VNInfoAllocator);
 634
 635     /// MergeInClobberRange - Same as MergeInClobberRanges except it merge in a
 636     /// single LiveRange only.
 637     void MergeInClobberRange(MachineInstrIndex Start,
 638                              MachineInstrIndex End,
 639                              BumpPtrAllocator &VNInfoAllocator);
 640
 641     /// MergeValueInAsValue - Merge all of the live ranges of a specific val#
 642     /// in RHS into this live interval as the specified value number.
 643     /// The LiveRanges in RHS are allowed to overlap with LiveRanges in the
 644     /// current interval, it will replace the value numbers of the overlaped
 645     /// live ranges with the specified value number.
 646     void MergeRangesInAsValue(const LiveInterval &RHS, VNInfo *LHSValNo);
 647
 648     /// MergeValueInAsValue - Merge all of the live ranges of a specific val#
 649     /// in RHS into this live interval as the specified value number.
 650     /// The LiveRanges in RHS are allowed to overlap with LiveRanges in the
 651     /// current interval, but only if the overlapping LiveRanges have the
 652     /// specified value number.
 653     void MergeValueInAsValue(const LiveInterval &RHS,
 654                              const VNInfo *RHSValNo, VNInfo *LHSValNo);
 655
 656     /// Copy - Copy the specified live interval. This copies all the fields
 657     /// except for the register of the interval.
 658     void Copy(const LiveInterval &RHS, MachineRegisterInfo *MRI,
 659               BumpPtrAllocator &VNInfoAllocator);
 660
 661     bool empty() const { return ranges.empty(); }
 662
 663     /// beginIndex - Return the lowest numbered slot covered by interval.
 664     MachineInstrIndex beginIndex() const {
 665       if (empty())
 666         return MachineInstrIndex();
 667       return ranges.front().start;
 668     }
 669
 670     /// endNumber - return the maximum point of the interval of the whole,
 671     /// exclusive.
 672     MachineInstrIndex endIndex() const {
 673       if (empty())
 674         return MachineInstrIndex();
 675       return ranges.back().end;
 676     }
 677
 678     bool expiredAt(MachineInstrIndex index) const {
 679       return index >= endIndex();
 680     }
 681
 682     bool liveAt(MachineInstrIndex index) const;
 683
 684     // liveBeforeAndAt - Check if the interval is live at the index and the
 685     // index just before it. If index is liveAt, check if it starts a new live
 686     // range.If it does, then check if the previous live range ends at index-1.
 687     bool liveBeforeAndAt(MachineInstrIndex index) const;
 688
 689     /// getLiveRangeContaining - Return the live range that contains the
 690     /// specified index, or null if there is none.
 691     const LiveRange *getLiveRangeContaining(MachineInstrIndex Idx) const {
 692       const_iterator I = FindLiveRangeContaining(Idx);
 693       return I == end() ? 0 : &*I;
 694     }
 695
 696     /// getLiveRangeContaining - Return the live range that contains the
 697     /// specified index, or null if there is none.
 698     LiveRange *getLiveRangeContaining(MachineInstrIndex Idx) {
 699       iterator I = FindLiveRangeContaining(Idx);
 700       return I == end() ? 0 : &*I;
 701     }
 702
 703     /// FindLiveRangeContaining - Return an iterator to the live range that
 704     /// contains the specified index, or end() if there is none.
 705     const_iterator FindLiveRangeContaining(MachineInstrIndex Idx) const;
 706
 707     /// FindLiveRangeContaining - Return an iterator to the live range that
 708     /// contains the specified index, or end() if there is none.
 709     iterator FindLiveRangeContaining(MachineInstrIndex Idx);
 710
 711     /// findDefinedVNInfo - Find the by the specified
 712     /// index (register interval) or defined
 713     VNInfo *findDefinedVNInfoForRegInt(MachineInstrIndex Idx) const;
 714
 715     /// findDefinedVNInfo - Find the VNInfo that's defined by the specified
 716     /// register (stack inteval only).
 717     VNInfo *findDefinedVNInfoForStackInt(unsigned Reg) const;
 718
 719
 720     /// overlaps - Return true if the intersection of the two live intervals is
 721     /// not empty.
 722     bool overlaps(const LiveInterval& other) const {
 723       return overlapsFrom(other, other.begin());
 724     }
 725
 726     /// overlaps - Return true if the live interval overlaps a range specified
 727     /// by [Start, End).
 728     bool overlaps(MachineInstrIndex Start, MachineInstrIndex End) const;
 729
 730     /// overlapsFrom - Return true if the intersection of the two live intervals
 731     /// is not empty.  The specified iterator is a hint that we can begin
 732     /// scanning the Other interval starting at I.
 733     bool overlapsFrom(const LiveInterval& other, const_iterator I) const;
 734
 735     /// addRange - Add the specified LiveRange to this interval, merging
 736     /// intervals as appropriate.  This returns an iterator to the inserted live
 737     /// range (which may have grown since it was inserted.
 738     void addRange(LiveRange LR) {
 739       addRangeFrom(LR, ranges.begin());
 740     }
 741
 742     /// join - Join two live intervals (this, and other) together.  This applies
 743     /// mappings to the value numbers in the LHS/RHS intervals as specified.  If
 744     /// the intervals are not joinable, this aborts.
 745     void join(LiveInterval &Other, const int *ValNoAssignments,
 746               const int *RHSValNoAssignments,
 747               SmallVector<VNInfo*, 16> &NewVNInfo,
 748               MachineRegisterInfo *MRI);
 749
 750     /// isInOneLiveRange - Return true if the range specified is entirely in the
 751     /// a single LiveRange of the live interval.
 752     bool isInOneLiveRange(MachineInstrIndex Start, MachineInstrIndex End);
 753
 754     /// removeRange - Remove the specified range from this interval.  Note that
 755     /// the range must be a single LiveRange in its entirety.
 756     void removeRange(MachineInstrIndex Start, MachineInstrIndex End,
 757                      bool RemoveDeadValNo = false);
 758
 759     void removeRange(LiveRange LR, bool RemoveDeadValNo = false) {
 760       removeRange(LR.start, LR.end, RemoveDeadValNo);
 761     }
 762
 763     /// removeValNo - Remove all the ranges defined by the specified value#.
 764     /// Also remove the value# from value# list.
 765     void removeValNo(VNInfo *ValNo);
 766
 767     /// scaleNumbering - Renumber VNI and ranges to provide gaps for new
 768     /// instructions.
 769     void scaleNumbering(unsigned factor);
 770
 771     /// getSize - Returns the sum of sizes of all the LiveRange's.
 772     ///
 773     unsigned getSize() const;
 774
 775     /// ComputeJoinedWeight - Set the weight of a live interval after
 776     /// Other has been merged into it.
 777     void ComputeJoinedWeight(const LiveInterval &Other);
 778
 779     bool operator<(const LiveInterval& other) const {
 780       return beginIndex() < other.beginIndex();
 781     }
 782
 783     void print(raw_ostream &OS, const TargetRegisterInfo *TRI = 0) const;
 784     void dump() const;
 785
 786   private:
 787
 788     Ranges::iterator addRangeFrom(LiveRange LR, Ranges::iterator From);
 789     void extendIntervalEndTo(Ranges::iterator I, MachineInstrIndex NewEnd);
 790     Ranges::iterator extendIntervalStartTo(Ranges::iterator I, MachineInstrIndex NewStr);
 791     LiveInterval& operator=(const LiveInterval& rhs); // DO NOT IMPLEMENT
 792
 793   };
 794
 795   inline raw_ostream &operator<<(raw_ostream &OS, const LiveInterval &LI) {
 796     LI.print(OS);
 797     return OS;
 798   }
 799 }
 800
 801 #endif