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 range 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 ranges can have holes,
  15 // i.e. a range might look like [1,20), [50,65), [1000,1001).  Each
  16 // individual segment is represented as an instance of LiveRange::Segment,
  17 // and the whole range is represented as an instance of LiveRange.
  18 //
  19 //===----------------------------------------------------------------------===//
  20
  21 #ifndef LLVM_CODEGEN_LIVEINTERVAL_H
  22 #define LLVM_CODEGEN_LIVEINTERVAL_H
  23
  24 #include "llvm/ADT/IntEqClasses.h"
  25 #include "llvm/CodeGen/SlotIndexes.h"
  26 #include "llvm/Support/AlignOf.h"
  27 #include "llvm/Support/Allocator.h"
  28 #include <cassert>
  29 #include <climits>
  30
  31 namespace llvm {
  32   class CoalescerPair;
  33   class LiveIntervals;
  34   class MachineInstr;
  35   class MachineRegisterInfo;
  36   class TargetRegisterInfo;
  37   class raw_ostream;
  38   template <typename T, unsigned Small> class SmallPtrSet;
  39
  40   /// VNInfo - Value Number Information.
  41   /// This class holds information about a machine level values, including
  42   /// definition and use points.
  43   ///
  44   class VNInfo {
  45   public:
  46     typedef BumpPtrAllocator Allocator;
  47
  48     /// The ID number of this value.
  49     unsigned id;
  50
  51     /// The index of the defining instruction.
  52     SlotIndex def;
  53
  54     /// VNInfo constructor.
  55     VNInfo(unsigned i, SlotIndex d)
  56       : id(i), def(d)
  57     { }
  58
  59     /// VNInfo construtor, copies values from orig, except for the value number.
  60     VNInfo(unsigned i, const VNInfo &orig)
  61       : id(i), def(orig.def)
  62     { }
  63
  64     /// Copy from the parameter into this VNInfo.
  65     void copyFrom(VNInfo &src) {
  66       def = src.def;
  67     }
  68
  69     /// Returns true if this value is defined by a PHI instruction (or was,
  70     /// PHI instructions may have been eliminated).
  71     /// PHI-defs begin at a block boundary, all other defs begin at register or
  72     /// EC slots.
  73     bool isPHIDef() const { return def.isBlock(); }
  74
  75     /// Returns true if this value is unused.
  76     bool isUnused() const { return !def.isValid(); }
  77
  78     /// Mark this value as unused.
  79     void markUnused() { def = SlotIndex(); }
  80   };
  81
  82   /// This class represents the liveness of a register, stack slot, etc.
  83   /// It manages an ordered list of Segment objects.
  84   /// The Segments are organized in a static single assignment form: At places
  85   /// where a new value is defined or different values reach a CFG join a new
  86   /// segment with a new value number is used.
  87   class LiveRange {
  88   public:
  89
  90     /// This represents a simple continuous liveness interval for a value.
  91     /// The start point is inclusive, the end point exclusive. These intervals
  92     /// are rendered as [start,end).
  93     struct Segment {
  94       SlotIndex start;  // Start point of the interval (inclusive)
  95       SlotIndex end;    // End point of the interval (exclusive)
  96       VNInfo *valno;    // identifier for the value contained in this segment.
  97
  98       Segment() : valno(0) {}
  99
 100       Segment(SlotIndex S, SlotIndex E, VNInfo *V)
 101         : start(S), end(E), valno(V) {
 102         assert(S < E && "Cannot create empty or backwards segment");
 103       }
 104
 105       /// Return true if the index is covered by this segment.
 106       bool contains(SlotIndex I) const {
 107         return start <= I && I < end;
 108       }
 109
 110       /// Return true if the given interval, [S, E), is covered by this segment.
 111       bool containsInterval(SlotIndex S, SlotIndex E) const {
 112         assert((S < E) && "Backwards interval?");
 113         return (start <= S && S < end) && (start < E && E <= end);
 114       }
 115
 116       bool operator<(const Segment &Other) const {
 117         return start < Other.start || (start == Other.start && end < Other.end);
 118       }
 119       bool operator==(const Segment &Other) const {
 120         return start == Other.start && end == Other.end;
 121       }
 122
 123       void dump() const;
 124     };
 125
 126     typedef SmallVector<Segment,4> Segments;
 127     typedef SmallVector<VNInfo*,4> VNInfoList;
 128
 129     Segments segments;   // the liveness segments
 130     VNInfoList valnos;   // value#'s
 131
 132     typedef Segments::iterator iterator;
 133     iterator begin() { return segments.begin(); }
 134     iterator end()   { return segments.end(); }
 135
 136     typedef Segments::const_iterator const_iterator;
 137     const_iterator begin() const { return segments.begin(); }
 138     const_iterator end() const  { return segments.end(); }
 139
 140     typedef VNInfoList::iterator vni_iterator;
 141     vni_iterator vni_begin() { return valnos.begin(); }
 142     vni_iterator vni_end()   { return valnos.end(); }
 143
 144     typedef VNInfoList::const_iterator const_vni_iterator;
 145     const_vni_iterator vni_begin() const { return valnos.begin(); }
 146     const_vni_iterator vni_end() const   { return valnos.end(); }
 147
 148     /// advanceTo - Advance the specified iterator to point to the Segment
 149     /// containing the specified position, or end() if the position is past the
 150     /// end of the range.  If no Segment contains this position, but the
 151     /// position is in a hole, this method returns an iterator pointing to the
 152     /// Segment immediately after the hole.
 153     iterator advanceTo(iterator I, SlotIndex Pos) {
 154       assert(I != end());
 155       if (Pos >= endIndex())
 156         return end();
 157       while (I->end <= Pos) ++I;
 158       return I;
 159     }
 160
 161     /// find - Return an iterator pointing to the first segment that ends after
 162     /// Pos, or end(). This is the same as advanceTo(begin(), Pos), but faster
 163     /// when searching large ranges.
 164     ///
 165     /// If Pos is contained in a Segment, that segment is returned.
 166     /// If Pos is in a hole, the following Segment is returned.
 167     /// If Pos is beyond endIndex, end() is returned.
 168     iterator find(SlotIndex Pos);
 169
 170     const_iterator find(SlotIndex Pos) const {
 171       return const_cast<LiveRange*>(this)->find(Pos);
 172     }
 173
 174     void clear() {
 175       valnos.clear();
 176       segments.clear();
 177     }
 178
 179     size_t size() const {
 180       return segments.size();
 181     }
 182
 183     bool hasAtLeastOneValue() const { return !valnos.empty(); }
 184
 185     bool containsOneValue() const { return valnos.size() == 1; }
 186
 187     unsigned getNumValNums() const { return (unsigned)valnos.size(); }
 188
 189     /// getValNumInfo - Returns pointer to the specified val#.
 190     ///
 191     inline VNInfo *getValNumInfo(unsigned ValNo) {
 192       return valnos[ValNo];
 193     }
 194     inline const VNInfo *getValNumInfo(unsigned ValNo) const {
 195       return valnos[ValNo];
 196     }
 197
 198     /// containsValue - Returns true if VNI belongs to this range.
 199     bool containsValue(const VNInfo *VNI) const {
 200       return VNI && VNI->id < getNumValNums() && VNI == getValNumInfo(VNI->id);
 201     }
 202
 203     /// getNextValue - Create a new value number and return it.  MIIdx specifies
 204     /// the instruction that defines the value number.
 205     VNInfo *getNextValue(SlotIndex def, VNInfo::Allocator &VNInfoAllocator) {
 206       VNInfo *VNI =
 207         new (VNInfoAllocator) VNInfo((unsigned)valnos.size(), def);
 208       valnos.push_back(VNI);
 209       return VNI;
 210     }
 211
 212     /// createDeadDef - Make sure the range has a value defined at Def.
 213     /// If one already exists, return it. Otherwise allocate a new value and
 214     /// add liveness for a dead def.
 215     VNInfo *createDeadDef(SlotIndex Def, VNInfo::Allocator &VNInfoAllocator);
 216
 217     /// Create a copy of the given value. The new value will be identical except
 218     /// for the Value number.
 219     VNInfo *createValueCopy(const VNInfo *orig,
 220                             VNInfo::Allocator &VNInfoAllocator) {
 221       VNInfo *VNI =
 222         new (VNInfoAllocator) VNInfo((unsigned)valnos.size(), *orig);
 223       valnos.push_back(VNI);
 224       return VNI;
 225     }
 226
 227     /// RenumberValues - Renumber all values in order of appearance and remove
 228     /// unused values.
 229     void RenumberValues();
 230
 231     /// MergeValueNumberInto - This method is called when two value numbers
 232     /// are found to be equivalent.  This eliminates V1, replacing all
 233     /// segments with the V1 value number with the V2 value number.  This can
 234     /// cause merging of V1/V2 values numbers and compaction of the value space.
 235     VNInfo* MergeValueNumberInto(VNInfo *V1, VNInfo *V2);
 236
 237     /// Merge all of the live segments of a specific val# in RHS into this live
 238     /// range as the specified value number. The segments in RHS are allowed
 239     /// to overlap with segments in the current range, it will replace the
 240     /// value numbers of the overlaped live segments with the specified value
 241     /// number.
 242     void MergeSegmentsInAsValue(const LiveRange &RHS, VNInfo *LHSValNo);
 243
 244     /// MergeValueInAsValue - Merge all of the segments of a specific val#
 245     /// in RHS into this live range as the specified value number.
 246     /// The segments in RHS are allowed to overlap with segments in the
 247     /// current range, but only if the overlapping segments have the
 248     /// specified value number.
 249     void MergeValueInAsValue(const LiveRange &RHS,
 250                              const VNInfo *RHSValNo, VNInfo *LHSValNo);
 251
 252     bool empty() const { return segments.empty(); }
 253
 254     /// beginIndex - Return the lowest numbered slot covered.
 255     SlotIndex beginIndex() const {
 256       assert(!empty() && "Call to beginIndex() on empty range.");
 257       return segments.front().start;
 258     }
 259
 260     /// endNumber - return the maximum point of the range of the whole,
 261     /// exclusive.
 262     SlotIndex endIndex() const {
 263       assert(!empty() && "Call to endIndex() on empty range.");
 264       return segments.back().end;
 265     }
 266
 267     bool expiredAt(SlotIndex index) const {
 268       return index >= endIndex();
 269     }
 270
 271     bool liveAt(SlotIndex index) const {
 272       const_iterator r = find(index);
 273       return r != end() && r->start <= index;
 274     }
 275
 276     /// Return the segment that contains the specified index, or null if there
 277     /// is none.
 278     const Segment *getSegmentContaining(SlotIndex Idx) const {
 279       const_iterator I = FindSegmentContaining(Idx);
 280       return I == end() ? 0 : &*I;
 281     }
 282
 283     /// Return the live segment that contains the specified index, or null if
 284     /// there is none.
 285     Segment *getSegmentContaining(SlotIndex Idx) {
 286       iterator I = FindSegmentContaining(Idx);
 287       return I == end() ? 0 : &*I;
 288     }
 289
 290     /// getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
 291     VNInfo *getVNInfoAt(SlotIndex Idx) const {
 292       const_iterator I = FindSegmentContaining(Idx);
 293       return I == end() ? 0 : I->valno;
 294     }
 295
 296     /// getVNInfoBefore - Return the VNInfo that is live up to but not
 297     /// necessarilly including Idx, or NULL. Use this to find the reaching def
 298     /// used by an instruction at this SlotIndex position.
 299     VNInfo *getVNInfoBefore(SlotIndex Idx) const {
 300       const_iterator I = FindSegmentContaining(Idx.getPrevSlot());
 301       return I == end() ? 0 : I->valno;
 302     }
 303
 304     /// Return an iterator to the segment that contains the specified index, or
 305     /// end() if there is none.
 306     iterator FindSegmentContaining(SlotIndex Idx) {
 307       iterator I = find(Idx);
 308       return I != end() && I->start <= Idx ? I : end();
 309     }
 310
 311     const_iterator FindSegmentContaining(SlotIndex Idx) const {
 312       const_iterator I = find(Idx);
 313       return I != end() && I->start <= Idx ? I : end();
 314     }
 315
 316     /// overlaps - Return true if the intersection of the two live ranges is
 317     /// not empty.
 318     bool overlaps(const LiveRange &other) const {
 319       if (other.empty())
 320         return false;
 321       return overlapsFrom(other, other.begin());
 322     }
 323
 324     /// overlaps - Return true if the two ranges have overlapping segments
 325     /// that are not coalescable according to CP.
 326     ///
 327     /// Overlapping segments where one range is defined by a coalescable
 328     /// copy are allowed.
 329     bool overlaps(const LiveRange &Other, const CoalescerPair &CP,
 330                   const SlotIndexes&) const;
 331
 332     /// overlaps - Return true if the live range overlaps an interval specified
 333     /// by [Start, End).
 334     bool overlaps(SlotIndex Start, SlotIndex End) const;
 335
 336     /// overlapsFrom - Return true if the intersection of the two live ranges
 337     /// is not empty.  The specified iterator is a hint that we can begin
 338     /// scanning the Other range starting at I.
 339     bool overlapsFrom(const LiveRange &Other, const_iterator I) const;
 340
 341     /// Add the specified Segment to this range, merging segments as
 342     /// appropriate.  This returns an iterator to the inserted segment (which
 343     /// may have grown since it was inserted).
 344     iterator addSegment(Segment S) {
 345       return addSegmentFrom(S, segments.begin());
 346     }
 347
 348     /// extendInBlock - If this range is live before Kill in the basic block
 349     /// that starts at StartIdx, extend it to be live up to Kill, and return
 350     /// the value. If there is no segment before Kill, return NULL.
 351     VNInfo *extendInBlock(SlotIndex StartIdx, SlotIndex Kill);
 352
 353     /// join - Join two live ranges (this, and other) together.  This applies
 354     /// mappings to the value numbers in the LHS/RHS ranges as specified.  If
 355     /// the ranges are not joinable, this aborts.
 356     void join(LiveRange &Other,
 357               const int *ValNoAssignments,
 358               const int *RHSValNoAssignments,
 359               SmallVectorImpl<VNInfo *> &NewVNInfo);
 360
 361     /// True iff this segment is a single segment that lies between the
 362     /// specified boundaries, exclusively. Vregs live across a backedge are not
 363     /// considered local. The boundaries are expected to lie within an extended
 364     /// basic block, so vregs that are not live out should contain no holes.
 365     bool isLocal(SlotIndex Start, SlotIndex End) const {
 366       return beginIndex() > Start.getBaseIndex() &&
 367         endIndex() < End.getBoundaryIndex();
 368     }
 369
 370     /// Remove the specified segment from this range.  Note that the segment
 371     /// must be a single Segment in its entirety.
 372     void removeSegment(SlotIndex Start, SlotIndex End,
 373                        bool RemoveDeadValNo = false);
 374
 375     void removeSegment(Segment S, bool RemoveDeadValNo = false) {
 376       removeSegment(S.start, S.end, RemoveDeadValNo);
 377     }
 378
 379     /// removeValNo - Remove all the segments defined by the specified value#.
 380     /// Also remove the value# from value# list.
 381     void removeValNo(VNInfo *ValNo);
 382
 383     /// Returns true if the live range is zero length, i.e. no live segments
 384     /// span instructions. It doesn't pay to spill such a range.
 385     bool isZeroLength(SlotIndexes *Indexes) const {
 386       for (const_iterator i = begin(), e = end(); i != e; ++i)
 387         if (Indexes->getNextNonNullIndex(i->start).getBaseIndex() <
 388             i->end.getBaseIndex())
 389           return false;
 390       return true;
 391     }
 392
 393     bool operator<(const LiveRange& other) const {
 394       const SlotIndex &thisIndex = beginIndex();
 395       const SlotIndex &otherIndex = other.beginIndex();
 396       return thisIndex < otherIndex;
 397     }
 398
 399     void print(raw_ostream &OS) const;
 400     void dump() const;
 401
 402     /// \brief Walk the range and assert if any invariants fail to hold.
 403     ///
 404     /// Note that this is a no-op when asserts are disabled.
 405 #ifdef NDEBUG
 406     void verify() const {}
 407 #else
 408     void verify() const;
 409 #endif
 410
 411   private:
 412
 413     iterator addSegmentFrom(Segment S, iterator From);
 414     void extendSegmentEndTo(iterator I, SlotIndex NewEnd);
 415     iterator extendSegmentStartTo(iterator I, SlotIndex NewStr);
 416     void markValNoForDeletion(VNInfo *V);
 417
 418   };
 419
 420   inline raw_ostream &operator<<(raw_ostream &OS, const LiveRange &LR) {
 421     LR.print(OS);
 422     return OS;
 423   }
 424
 425   /// LiveInterval - This class represents the liveness of a register,
 426   /// or stack slot.
 427   class LiveInterval : public LiveRange {
 428   public:
 429     const unsigned reg;  // the register or stack slot of this interval.
 430     float weight;        // weight of this interval
 431
 432     LiveInterval(unsigned Reg, float Weight)
 433       : reg(Reg), weight(Weight) {}
 434
 435     /// getSize - Returns the sum of sizes of all the LiveRange's.
 436     ///
 437     unsigned getSize() const;
 438
 439     /// isSpillable - Can this interval be spilled?
 440     bool isSpillable() const {
 441       return weight != HUGE_VALF;
 442     }
 443
 444     /// markNotSpillable - Mark interval as not spillable
 445     void markNotSpillable() {
 446       weight = HUGE_VALF;
 447     }
 448
 449     bool operator<(const LiveInterval& other) const {
 450       const SlotIndex &thisIndex = beginIndex();
 451       const SlotIndex &otherIndex = other.beginIndex();
 452       return thisIndex < otherIndex ||
 453               (thisIndex == otherIndex && reg < other.reg);
 454     }
 455
 456   private:
 457     LiveInterval& operator=(const LiveInterval& rhs) LLVM_DELETED_FUNCTION;
 458
 459   };
 460
 461   inline raw_ostream &operator<<(raw_ostream &OS, const LiveInterval &LI) {
 462     LI.print(OS);
 463     return OS;
 464   }
 465
 466   raw_ostream &operator<<(raw_ostream &OS, const LiveRange::Segment &S);
 467
 468   inline bool operator<(SlotIndex V, const LiveRange::Segment &S) {
 469     return V < S.start;
 470   }
 471
 472   inline bool operator<(const LiveRange::Segment &S, SlotIndex V) {
 473     return S.start < V;
 474   }
 475
 476   /// Helper class for performant LiveRange bulk updates.
 477   ///
 478   /// Calling LiveRange::addSegment() repeatedly can be expensive on large
 479   /// live ranges because segments after the insertion point may need to be
 480   /// shifted. The LiveRangeUpdater class can defer the shifting when adding
 481   /// many segments in order.
 482   ///
 483   /// The LiveRange will be in an invalid state until flush() is called.
 484   class LiveRangeUpdater {
 485     LiveRange *LR;
 486     SlotIndex LastStart;
 487     LiveRange::iterator WriteI;
 488     LiveRange::iterator ReadI;
 489     SmallVector<LiveRange::Segment, 16> Spills;
 490     void mergeSpills();
 491
 492   public:
 493     /// Create a LiveRangeUpdater for adding segments to LR.
 494     /// LR will temporarily be in an invalid state until flush() is called.
 495     LiveRangeUpdater(LiveRange *lr = 0) : LR(lr) {}
 496
 497     ~LiveRangeUpdater() { flush(); }
 498
 499     /// Add a segment to LR and coalesce when possible, just like
 500     /// LR.addSegment(). Segments should be added in increasing start order for
 501     /// best performance.
 502     void add(LiveRange::Segment);
 503
 504     void add(SlotIndex Start, SlotIndex End, VNInfo *VNI) {
 505       add(LiveRange::Segment(Start, End, VNI));
 506     }
 507
 508     /// Return true if the LR is currently in an invalid state, and flush()
 509     /// needs to be called.
 510     bool isDirty() const { return LastStart.isValid(); }
 511
 512     /// Flush the updater state to LR so it is valid and contains all added
 513     /// segments.
 514     void flush();
 515
 516     /// Select a different destination live range.
 517     void setDest(LiveRange *lr) {
 518       if (LR != lr && isDirty())
 519         flush();
 520       LR = lr;
 521     }
 522
 523     /// Get the current destination live range.
 524     LiveRange *getDest() const { return LR; }
 525
 526     void dump() const;
 527     void print(raw_ostream&) const;
 528   };
 529
 530   inline raw_ostream &operator<<(raw_ostream &OS, const LiveRangeUpdater &X) {
 531     X.print(OS);
 532     return OS;
 533   }
 534
 535   /// LiveRangeQuery - Query information about a live range around a given
 536   /// instruction. This class hides the implementation details of live ranges,
 537   /// and it should be used as the primary interface for examining live ranges
 538   /// around instructions.
 539   ///
 540   class LiveRangeQuery {
 541     VNInfo *EarlyVal;
 542     VNInfo *LateVal;
 543     SlotIndex EndPoint;
 544     bool Kill;
 545
 546     void init(const LiveRange &LR, SlotIndex Idx) {
 547     }
 548
 549   public:
 550     /// Create a LiveRangeQuery for the given live range and instruction index.
 551     /// The sub-instruction slot of Idx doesn't matter, only the instruction it
 552     /// refers to is considered.
 553     LiveRangeQuery(const LiveRange &LR, SlotIndex Idx)
 554       : EarlyVal(0), LateVal(0), Kill(false) {
 555       // Find the segment that enters the instruction.
 556       LiveRange::const_iterator I = LR.find(Idx.getBaseIndex());
 557       LiveRange::const_iterator E = LR.end();
 558       if (I == E)
 559         return;
 560       // Is this an instruction live-in segment?
 561       // If Idx is the start index of a basic block, include live-in segments
 562       // that start at Idx.getBaseIndex().
 563       if (I->start <= Idx.getBaseIndex()) {
 564         EarlyVal = I->valno;
 565         EndPoint = I->end;
 566         // Move to the potentially live-out segment.
 567         if (SlotIndex::isSameInstr(Idx, I->end)) {
 568           Kill = true;
 569           if (++I == E)
 570             return;
 571         }
 572         // Special case: A PHIDef value can have its def in the middle of a
 573         // segment if the value happens to be live out of the layout
 574         // predecessor.
 575         // Such a value is not live-in.
 576         if (EarlyVal->def == Idx.getBaseIndex())
 577           EarlyVal = 0;
 578       }
 579       // I now points to the segment that may be live-through, or defined by
 580       // this instr. Ignore segments starting after the current instr.
 581       if (SlotIndex::isEarlierInstr(Idx, I->start))
 582         return;
 583       LateVal = I->valno;
 584       EndPoint = I->end;
 585     }
 586
 587     /// Return the value that is live-in to the instruction. This is the value
 588     /// that will be read by the instruction's use operands. Return NULL if no
 589     /// value is live-in.
 590     VNInfo *valueIn() const {
 591       return EarlyVal;
 592     }
 593
 594     /// Return true if the live-in value is killed by this instruction. This
 595     /// means that either the live range ends at the instruction, or it changes
 596     /// value.
 597     bool isKill() const {
 598       return Kill;
 599     }
 600
 601     /// Return true if this instruction has a dead def.
 602     bool isDeadDef() const {
 603       return EndPoint.isDead();
 604     }
 605
 606     /// Return the value leaving the instruction, if any. This can be a
 607     /// live-through value, or a live def. A dead def returns NULL.
 608     VNInfo *valueOut() const {
 609       return isDeadDef() ? 0 : LateVal;
 610     }
 611
 612     /// Return the value defined by this instruction, if any. This includes
 613     /// dead defs, it is the value created by the instruction's def operands.
 614     VNInfo *valueDefined() const {
 615       return EarlyVal == LateVal ? 0 : LateVal;
 616     }
 617
 618     /// Return the end point of the last live range segment to interact with
 619     /// the instruction, if any.
 620     ///
 621     /// The end point is an invalid SlotIndex only if the live range doesn't
 622     /// intersect the instruction at all.
 623     ///
 624     /// The end point may be at or past the end of the instruction's basic
 625     /// block. That means the value was live out of the block.
 626     SlotIndex endPoint() const {
 627       return EndPoint;
 628     }
 629   };
 630
 631   /// ConnectedVNInfoEqClasses - Helper class that can divide VNInfos in a
 632   /// LiveInterval into equivalence clases of connected components. A
 633   /// LiveInterval that has multiple connected components can be broken into
 634   /// multiple LiveIntervals.
 635   ///
 636   /// Given a LiveInterval that may have multiple connected components, run:
 637   ///
 638   ///   unsigned numComps = ConEQ.Classify(LI);
 639   ///   if (numComps > 1) {
 640   ///     // allocate numComps-1 new LiveIntervals into LIS[1..]
 641   ///     ConEQ.Distribute(LIS);
 642   /// }
 643
 644   class ConnectedVNInfoEqClasses {
 645     LiveIntervals &LIS;
 646     IntEqClasses EqClass;
 647
 648     // Note that values a and b are connected.
 649     void Connect(unsigned a, unsigned b);
 650
 651     unsigned Renumber();
 652
 653   public:
 654     explicit ConnectedVNInfoEqClasses(LiveIntervals &lis) : LIS(lis) {}
 655
 656     /// Classify - Classify the values in LI into connected components.
 657     /// Return the number of connected components.
 658     unsigned Classify(const LiveInterval *LI);
 659
 660     /// getEqClass - Classify creates equivalence classes numbered 0..N. Return
 661     /// the equivalence class assigned the VNI.
 662     unsigned getEqClass(const VNInfo *VNI) const { return EqClass[VNI->id]; }
 663
 664     /// Distribute - Distribute values in LIV[0] into a separate LiveInterval
 665     /// for each connected component. LIV must have a LiveInterval for each
 666     /// connected component. The LiveIntervals in Liv[1..] must be empty.
 667     /// Instructions using LIV[0] are rewritten.
 668     void Distribute(LiveInterval *LIV[], MachineRegisterInfo &MRI);
 669
 670   };
 671
 672 }
 673 #endif