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