1193323Sed//===-- llvm/CodeGen/LiveInterval.h - Interval representation ---*- C++ -*-===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file implements the LiveRange and LiveInterval classes. Given some 11193323Sed// numbering of each the machine instructions an interval [i, j) is said to be a 12263508Sdim// live range for register v if there is no instruction with number j' >= j 13193323Sed// such that v is live at j' and there is no instruction with number i' < i such 14263508Sdim// that v is live at i'. In this implementation ranges can have holes, 15263508Sdim// i.e. a range might look like [1,20), [50,65), [1000,1001). Each 16263508Sdim// individual segment is represented as an instance of LiveRange::Segment, 17263508Sdim// and the whole range is represented as an instance of LiveRange. 18193323Sed// 19193323Sed//===----------------------------------------------------------------------===// 20193323Sed 21193323Sed#ifndef LLVM_CODEGEN_LIVEINTERVAL_H 22193323Sed#define LLVM_CODEGEN_LIVEINTERVAL_H 23193323Sed 24218893Sdim#include "llvm/ADT/IntEqClasses.h" 25249423Sdim#include "llvm/CodeGen/SlotIndexes.h" 26249423Sdim#include "llvm/Support/AlignOf.h" 27193323Sed#include "llvm/Support/Allocator.h" 28193323Sed#include <cassert> 29193323Sed#include <climits> 30193323Sed 31193323Sednamespace llvm { 32243830Sdim class CoalescerPair; 33198892Srdivacky class LiveIntervals; 34193323Sed class MachineInstr; 35194612Sed class MachineRegisterInfo; 36193323Sed class TargetRegisterInfo; 37198090Srdivacky class raw_ostream; 38263508Sdim template <typename T, unsigned Small> class SmallPtrSet; 39193323Sed 40194612Sed /// VNInfo - Value Number Information. 41194612Sed /// This class holds information about a machine level values, including 42194612Sed /// definition and use points. 43194612Sed /// 44194612Sed class VNInfo { 45194612Sed public: 46210299Sed typedef BumpPtrAllocator Allocator; 47198090Srdivacky 48194612Sed /// The ID number of this value. 49193323Sed unsigned id; 50210299Sed 51234353Sdim /// The index of the defining instruction. 52198892Srdivacky SlotIndex def; 53194612Sed 54194612Sed /// VNInfo constructor. 55234353Sdim VNInfo(unsigned i, SlotIndex d) 56239462Sdim : id(i), def(d) 57218893Sdim { } 58194612Sed 59194612Sed /// VNInfo construtor, copies values from orig, except for the value number. 60194612Sed VNInfo(unsigned i, const VNInfo &orig) 61239462Sdim : id(i), def(orig.def) 62198090Srdivacky { } 63194612Sed 64198090Srdivacky /// Copy from the parameter into this VNInfo. 65198090Srdivacky void copyFrom(VNInfo &src) { 66198090Srdivacky def = src.def; 67198090Srdivacky } 68198090Srdivacky 69194612Sed /// Returns true if this value is defined by a PHI instruction (or was, 70263508Sdim /// PHI instructions may have been eliminated). 71239462Sdim /// PHI-defs begin at a block boundary, all other defs begin at register or 72239462Sdim /// EC slots. 73239462Sdim bool isPHIDef() const { return def.isBlock(); } 74194612Sed 75194612Sed /// Returns true if this value is unused. 76239462Sdim bool isUnused() const { return !def.isValid(); } 77239462Sdim 78239462Sdim /// Mark this value as unused. 79239462Sdim void markUnused() { def = SlotIndex(); } 80193323Sed }; 81193323Sed 82263508Sdim /// Result of a LiveRange query. This class hides the implementation details 83263508Sdim /// of live ranges, and it should be used as the primary interface for 84263508Sdim /// examining live ranges around instructions. 85263508Sdim class LiveQueryResult { 86263508Sdim VNInfo *const EarlyVal; 87263508Sdim VNInfo *const LateVal; 88263508Sdim const SlotIndex EndPoint; 89263508Sdim const bool Kill; 90193323Sed 91263508Sdim public: 92263508Sdim LiveQueryResult(VNInfo *EarlyVal, VNInfo *LateVal, SlotIndex EndPoint, 93263508Sdim bool Kill) 94263508Sdim : EarlyVal(EarlyVal), LateVal(LateVal), EndPoint(EndPoint), Kill(Kill) 95263508Sdim {} 96249423Sdim 97263508Sdim /// Return the value that is live-in to the instruction. This is the value 98263508Sdim /// that will be read by the instruction's use operands. Return NULL if no 99263508Sdim /// value is live-in. 100263508Sdim VNInfo *valueIn() const { 101263508Sdim return EarlyVal; 102193323Sed } 103193323Sed 104263508Sdim /// Return true if the live-in value is killed by this instruction. This 105263508Sdim /// means that either the live range ends at the instruction, or it changes 106263508Sdim /// value. 107263508Sdim bool isKill() const { 108263508Sdim return Kill; 109193323Sed } 110193323Sed 111263508Sdim /// Return true if this instruction has a dead def. 112263508Sdim bool isDeadDef() const { 113263508Sdim return EndPoint.isDead(); 114198090Srdivacky } 115198090Srdivacky 116263508Sdim /// Return the value leaving the instruction, if any. This can be a 117263508Sdim /// live-through value, or a live def. A dead def returns NULL. 118263508Sdim VNInfo *valueOut() const { 119263508Sdim return isDeadDef() ? 0 : LateVal; 120193323Sed } 121263508Sdim 122263508Sdim /// Return the value defined by this instruction, if any. This includes 123263508Sdim /// dead defs, it is the value created by the instruction's def operands. 124263508Sdim VNInfo *valueDefined() const { 125263508Sdim return EarlyVal == LateVal ? 0 : LateVal; 126193323Sed } 127193323Sed 128263508Sdim /// Return the end point of the last live range segment to interact with 129263508Sdim /// the instruction, if any. 130263508Sdim /// 131263508Sdim /// The end point is an invalid SlotIndex only if the live range doesn't 132263508Sdim /// intersect the instruction at all. 133263508Sdim /// 134263508Sdim /// The end point may be at or past the end of the instruction's basic 135263508Sdim /// block. That means the value was live out of the block. 136263508Sdim SlotIndex endPoint() const { 137263508Sdim return EndPoint; 138263508Sdim } 139193323Sed }; 140193323Sed 141263508Sdim /// This class represents the liveness of a register, stack slot, etc. 142263508Sdim /// It manages an ordered list of Segment objects. 143263508Sdim /// The Segments are organized in a static single assignment form: At places 144263508Sdim /// where a new value is defined or different values reach a CFG join a new 145263508Sdim /// segment with a new value number is used. 146263508Sdim class LiveRange { 147263508Sdim public: 148210299Sed 149263508Sdim /// This represents a simple continuous liveness interval for a value. 150263508Sdim /// The start point is inclusive, the end point exclusive. These intervals 151263508Sdim /// are rendered as [start,end). 152263508Sdim struct Segment { 153263508Sdim SlotIndex start; // Start point of the interval (inclusive) 154263508Sdim SlotIndex end; // End point of the interval (exclusive) 155263508Sdim VNInfo *valno; // identifier for the value contained in this segment. 156193323Sed 157263508Sdim Segment() : valno(0) {} 158193323Sed 159263508Sdim Segment(SlotIndex S, SlotIndex E, VNInfo *V) 160263508Sdim : start(S), end(E), valno(V) { 161263508Sdim assert(S < E && "Cannot create empty or backwards segment"); 162263508Sdim } 163193323Sed 164263508Sdim /// Return true if the index is covered by this segment. 165263508Sdim bool contains(SlotIndex I) const { 166263508Sdim return start <= I && I < end; 167263508Sdim } 168193323Sed 169263508Sdim /// Return true if the given interval, [S, E), is covered by this segment. 170263508Sdim bool containsInterval(SlotIndex S, SlotIndex E) const { 171263508Sdim assert((S < E) && "Backwards interval?"); 172263508Sdim return (start <= S && S < end) && (start < E && E <= end); 173263508Sdim } 174198090Srdivacky 175263508Sdim bool operator<(const Segment &Other) const { 176263508Sdim return start < Other.start || (start == Other.start && end < Other.end); 177263508Sdim } 178263508Sdim bool operator==(const Segment &Other) const { 179263508Sdim return start == Other.start && end == Other.end; 180263508Sdim } 181263508Sdim 182263508Sdim void dump() const; 183263508Sdim }; 184263508Sdim 185263508Sdim typedef SmallVector<Segment,4> Segments; 186193323Sed typedef SmallVector<VNInfo*,4> VNInfoList; 187193323Sed 188263508Sdim Segments segments; // the liveness segments 189193323Sed VNInfoList valnos; // value#'s 190212904Sdim 191263508Sdim typedef Segments::iterator iterator; 192263508Sdim iterator begin() { return segments.begin(); } 193263508Sdim iterator end() { return segments.end(); } 194193323Sed 195263508Sdim typedef Segments::const_iterator const_iterator; 196263508Sdim const_iterator begin() const { return segments.begin(); } 197263508Sdim const_iterator end() const { return segments.end(); } 198193323Sed 199193323Sed typedef VNInfoList::iterator vni_iterator; 200193323Sed vni_iterator vni_begin() { return valnos.begin(); } 201263508Sdim vni_iterator vni_end() { return valnos.end(); } 202193323Sed 203193323Sed typedef VNInfoList::const_iterator const_vni_iterator; 204193323Sed const_vni_iterator vni_begin() const { return valnos.begin(); } 205263508Sdim const_vni_iterator vni_end() const { return valnos.end(); } 206193323Sed 207263508Sdim /// advanceTo - Advance the specified iterator to point to the Segment 208193323Sed /// containing the specified position, or end() if the position is past the 209263508Sdim /// end of the range. If no Segment contains this position, but the 210203954Srdivacky /// position is in a hole, this method returns an iterator pointing to the 211263508Sdim /// Segment immediately after the hole. 212198892Srdivacky iterator advanceTo(iterator I, SlotIndex Pos) { 213218893Sdim assert(I != end()); 214198090Srdivacky if (Pos >= endIndex()) 215193323Sed return end(); 216193323Sed while (I->end <= Pos) ++I; 217193323Sed return I; 218193323Sed } 219212904Sdim 220263508Sdim /// find - Return an iterator pointing to the first segment that ends after 221218893Sdim /// Pos, or end(). This is the same as advanceTo(begin(), Pos), but faster 222263508Sdim /// when searching large ranges. 223218893Sdim /// 224263508Sdim /// If Pos is contained in a Segment, that segment is returned. 225263508Sdim /// If Pos is in a hole, the following Segment is returned. 226218893Sdim /// If Pos is beyond endIndex, end() is returned. 227218893Sdim iterator find(SlotIndex Pos); 228218893Sdim 229218893Sdim const_iterator find(SlotIndex Pos) const { 230263508Sdim return const_cast<LiveRange*>(this)->find(Pos); 231218893Sdim } 232218893Sdim 233193323Sed void clear() { 234206083Srdivacky valnos.clear(); 235263508Sdim segments.clear(); 236193323Sed } 237193323Sed 238263508Sdim size_t size() const { 239263508Sdim return segments.size(); 240263508Sdim } 241263508Sdim 242193323Sed bool hasAtLeastOneValue() const { return !valnos.empty(); } 243193323Sed 244193323Sed bool containsOneValue() const { return valnos.size() == 1; } 245193323Sed 246193323Sed unsigned getNumValNums() const { return (unsigned)valnos.size(); } 247212904Sdim 248193323Sed /// getValNumInfo - Returns pointer to the specified val#. 249193323Sed /// 250193323Sed inline VNInfo *getValNumInfo(unsigned ValNo) { 251193323Sed return valnos[ValNo]; 252193323Sed } 253193323Sed inline const VNInfo *getValNumInfo(unsigned ValNo) const { 254193323Sed return valnos[ValNo]; 255193323Sed } 256193323Sed 257263508Sdim /// containsValue - Returns true if VNI belongs to this range. 258221345Sdim bool containsValue(const VNInfo *VNI) const { 259221345Sdim return VNI && VNI->id < getNumValNums() && VNI == getValNumInfo(VNI->id); 260221345Sdim } 261221345Sdim 262193323Sed /// getNextValue - Create a new value number and return it. MIIdx specifies 263193323Sed /// the instruction that defines the value number. 264234353Sdim VNInfo *getNextValue(SlotIndex def, VNInfo::Allocator &VNInfoAllocator) { 265210299Sed VNInfo *VNI = 266234353Sdim new (VNInfoAllocator) VNInfo((unsigned)valnos.size(), def); 267193323Sed valnos.push_back(VNI); 268193323Sed return VNI; 269193323Sed } 270193323Sed 271263508Sdim /// createDeadDef - Make sure the range has a value defined at Def. 272239462Sdim /// If one already exists, return it. Otherwise allocate a new value and 273239462Sdim /// add liveness for a dead def. 274239462Sdim VNInfo *createDeadDef(SlotIndex Def, VNInfo::Allocator &VNInfoAllocator); 275239462Sdim 276194612Sed /// Create a copy of the given value. The new value will be identical except 277194612Sed /// for the Value number. 278198090Srdivacky VNInfo *createValueCopy(const VNInfo *orig, 279206083Srdivacky VNInfo::Allocator &VNInfoAllocator) { 280210299Sed VNInfo *VNI = 281210299Sed new (VNInfoAllocator) VNInfo((unsigned)valnos.size(), *orig); 282194612Sed valnos.push_back(VNI); 283194612Sed return VNI; 284194612Sed } 285194612Sed 286212904Sdim /// RenumberValues - Renumber all values in order of appearance and remove 287212904Sdim /// unused values. 288263508Sdim void RenumberValues(); 289212904Sdim 290263508Sdim /// MergeValueNumberInto - This method is called when two value numbers 291193323Sed /// are found to be equivalent. This eliminates V1, replacing all 292263508Sdim /// segments with the V1 value number with the V2 value number. This can 293193323Sed /// cause merging of V1/V2 values numbers and compaction of the value space. 294193323Sed VNInfo* MergeValueNumberInto(VNInfo *V1, VNInfo *V2); 295193323Sed 296263508Sdim /// Merge all of the live segments of a specific val# in RHS into this live 297263508Sdim /// range as the specified value number. The segments in RHS are allowed 298263508Sdim /// to overlap with segments in the current range, it will replace the 299263508Sdim /// value numbers of the overlaped live segments with the specified value 300263508Sdim /// number. 301263508Sdim void MergeSegmentsInAsValue(const LiveRange &RHS, VNInfo *LHSValNo); 302193323Sed 303263508Sdim /// MergeValueInAsValue - Merge all of the segments of a specific val# 304263508Sdim /// in RHS into this live range as the specified value number. 305263508Sdim /// The segments in RHS are allowed to overlap with segments in the 306263508Sdim /// current range, but only if the overlapping segments have the 307193323Sed /// specified value number. 308263508Sdim void MergeValueInAsValue(const LiveRange &RHS, 309193323Sed const VNInfo *RHSValNo, VNInfo *LHSValNo); 310193323Sed 311263508Sdim bool empty() const { return segments.empty(); } 312193323Sed 313263508Sdim /// beginIndex - Return the lowest numbered slot covered. 314198892Srdivacky SlotIndex beginIndex() const { 315263508Sdim assert(!empty() && "Call to beginIndex() on empty range."); 316263508Sdim return segments.front().start; 317193323Sed } 318193323Sed 319263508Sdim /// endNumber - return the maximum point of the range of the whole, 320193323Sed /// exclusive. 321198892Srdivacky SlotIndex endIndex() const { 322263508Sdim assert(!empty() && "Call to endIndex() on empty range."); 323263508Sdim return segments.back().end; 324193323Sed } 325193323Sed 326198892Srdivacky bool expiredAt(SlotIndex index) const { 327198090Srdivacky return index >= endIndex(); 328193323Sed } 329193323Sed 330218893Sdim bool liveAt(SlotIndex index) const { 331218893Sdim const_iterator r = find(index); 332218893Sdim return r != end() && r->start <= index; 333218893Sdim } 334193323Sed 335263508Sdim /// Return the segment that contains the specified index, or null if there 336263508Sdim /// is none. 337263508Sdim const Segment *getSegmentContaining(SlotIndex Idx) const { 338263508Sdim const_iterator I = FindSegmentContaining(Idx); 339193323Sed return I == end() ? 0 : &*I; 340193323Sed } 341193323Sed 342263508Sdim /// Return the live segment that contains the specified index, or null if 343263508Sdim /// there is none. 344263508Sdim Segment *getSegmentContaining(SlotIndex Idx) { 345263508Sdim iterator I = FindSegmentContaining(Idx); 346198090Srdivacky return I == end() ? 0 : &*I; 347198090Srdivacky } 348198090Srdivacky 349210299Sed /// getVNInfoAt - Return the VNInfo that is live at Idx, or NULL. 350210299Sed VNInfo *getVNInfoAt(SlotIndex Idx) const { 351263508Sdim const_iterator I = FindSegmentContaining(Idx); 352210299Sed return I == end() ? 0 : I->valno; 353210299Sed } 354210299Sed 355226633Sdim /// getVNInfoBefore - Return the VNInfo that is live up to but not 356226633Sdim /// necessarilly including Idx, or NULL. Use this to find the reaching def 357226633Sdim /// used by an instruction at this SlotIndex position. 358226633Sdim VNInfo *getVNInfoBefore(SlotIndex Idx) const { 359263508Sdim const_iterator I = FindSegmentContaining(Idx.getPrevSlot()); 360226633Sdim return I == end() ? 0 : I->valno; 361226633Sdim } 362226633Sdim 363263508Sdim /// Return an iterator to the segment that contains the specified index, or 364263508Sdim /// end() if there is none. 365263508Sdim iterator FindSegmentContaining(SlotIndex Idx) { 366218893Sdim iterator I = find(Idx); 367218893Sdim return I != end() && I->start <= Idx ? I : end(); 368218893Sdim } 369193323Sed 370263508Sdim const_iterator FindSegmentContaining(SlotIndex Idx) const { 371218893Sdim const_iterator I = find(Idx); 372218893Sdim return I != end() && I->start <= Idx ? I : end(); 373218893Sdim } 374193323Sed 375263508Sdim /// overlaps - Return true if the intersection of the two live ranges is 376193323Sed /// not empty. 377263508Sdim bool overlaps(const LiveRange &other) const { 378212904Sdim if (other.empty()) 379212904Sdim return false; 380193323Sed return overlapsFrom(other, other.begin()); 381193323Sed } 382193323Sed 383263508Sdim /// overlaps - Return true if the two ranges have overlapping segments 384243830Sdim /// that are not coalescable according to CP. 385243830Sdim /// 386263508Sdim /// Overlapping segments where one range is defined by a coalescable 387243830Sdim /// copy are allowed. 388263508Sdim bool overlaps(const LiveRange &Other, const CoalescerPair &CP, 389243830Sdim const SlotIndexes&) const; 390243830Sdim 391263508Sdim /// overlaps - Return true if the live range overlaps an interval specified 392193323Sed /// by [Start, End). 393198892Srdivacky bool overlaps(SlotIndex Start, SlotIndex End) const; 394193323Sed 395263508Sdim /// overlapsFrom - Return true if the intersection of the two live ranges 396193323Sed /// is not empty. The specified iterator is a hint that we can begin 397263508Sdim /// scanning the Other range starting at I. 398263508Sdim bool overlapsFrom(const LiveRange &Other, const_iterator I) const; 399193323Sed 400263508Sdim /// Add the specified Segment to this range, merging segments as 401263508Sdim /// appropriate. This returns an iterator to the inserted segment (which 402263508Sdim /// may have grown since it was inserted). 403263508Sdim iterator addSegment(Segment S) { 404263508Sdim return addSegmentFrom(S, segments.begin()); 405193323Sed } 406193323Sed 407263508Sdim /// extendInBlock - If this range is live before Kill in the basic block 408226633Sdim /// that starts at StartIdx, extend it to be live up to Kill, and return 409263508Sdim /// the value. If there is no segment before Kill, return NULL. 410226633Sdim VNInfo *extendInBlock(SlotIndex StartIdx, SlotIndex Kill); 411221345Sdim 412263508Sdim /// join - Join two live ranges (this, and other) together. This applies 413263508Sdim /// mappings to the value numbers in the LHS/RHS ranges as specified. If 414263508Sdim /// the ranges are not joinable, this aborts. 415263508Sdim void join(LiveRange &Other, 416198892Srdivacky const int *ValNoAssignments, 417193323Sed const int *RHSValNoAssignments, 418263508Sdim SmallVectorImpl<VNInfo *> &NewVNInfo); 419193323Sed 420263508Sdim /// True iff this segment is a single segment that lies between the 421251662Sdim /// specified boundaries, exclusively. Vregs live across a backedge are not 422251662Sdim /// considered local. The boundaries are expected to lie within an extended 423251662Sdim /// basic block, so vregs that are not live out should contain no holes. 424251662Sdim bool isLocal(SlotIndex Start, SlotIndex End) const { 425251662Sdim return beginIndex() > Start.getBaseIndex() && 426251662Sdim endIndex() < End.getBoundaryIndex(); 427251662Sdim } 428251662Sdim 429263508Sdim /// Remove the specified segment from this range. Note that the segment 430263508Sdim /// must be a single Segment in its entirety. 431263508Sdim void removeSegment(SlotIndex Start, SlotIndex End, 432263508Sdim bool RemoveDeadValNo = false); 433193323Sed 434263508Sdim void removeSegment(Segment S, bool RemoveDeadValNo = false) { 435263508Sdim removeSegment(S.start, S.end, RemoveDeadValNo); 436193323Sed } 437193323Sed 438263508Sdim /// Query Liveness at Idx. 439263508Sdim /// The sub-instruction slot of Idx doesn't matter, only the instruction 440263508Sdim /// it refers to is considered. 441263508Sdim LiveQueryResult Query(SlotIndex Idx) const { 442263508Sdim // Find the segment that enters the instruction. 443263508Sdim const_iterator I = find(Idx.getBaseIndex()); 444263508Sdim const_iterator E = end(); 445263508Sdim if (I == E) 446263508Sdim return LiveQueryResult(0, 0, SlotIndex(), false); 447263508Sdim 448263508Sdim // Is this an instruction live-in segment? 449263508Sdim // If Idx is the start index of a basic block, include live-in segments 450263508Sdim // that start at Idx.getBaseIndex(). 451263508Sdim VNInfo *EarlyVal = 0; 452263508Sdim VNInfo *LateVal = 0; 453263508Sdim SlotIndex EndPoint; 454263508Sdim bool Kill = false; 455263508Sdim if (I->start <= Idx.getBaseIndex()) { 456263508Sdim EarlyVal = I->valno; 457263508Sdim EndPoint = I->end; 458263508Sdim // Move to the potentially live-out segment. 459263508Sdim if (SlotIndex::isSameInstr(Idx, I->end)) { 460263508Sdim Kill = true; 461263508Sdim if (++I == E) 462263508Sdim return LiveQueryResult(EarlyVal, LateVal, EndPoint, Kill); 463263508Sdim } 464263508Sdim // Special case: A PHIDef value can have its def in the middle of a 465263508Sdim // segment if the value happens to be live out of the layout 466263508Sdim // predecessor. 467263508Sdim // Such a value is not live-in. 468263508Sdim if (EarlyVal->def == Idx.getBaseIndex()) 469263508Sdim EarlyVal = 0; 470263508Sdim } 471263508Sdim // I now points to the segment that may be live-through, or defined by 472263508Sdim // this instr. Ignore segments starting after the current instr. 473263508Sdim if (!SlotIndex::isEarlierInstr(Idx, I->start)) { 474263508Sdim LateVal = I->valno; 475263508Sdim EndPoint = I->end; 476263508Sdim } 477263508Sdim return LiveQueryResult(EarlyVal, LateVal, EndPoint, Kill); 478263508Sdim } 479263508Sdim 480263508Sdim /// removeValNo - Remove all the segments defined by the specified value#. 481193323Sed /// Also remove the value# from value# list. 482193323Sed void removeValNo(VNInfo *ValNo); 483193323Sed 484263508Sdim /// Returns true if the live range is zero length, i.e. no live segments 485263508Sdim /// span instructions. It doesn't pay to spill such a range. 486223017Sdim bool isZeroLength(SlotIndexes *Indexes) const { 487212904Sdim for (const_iterator i = begin(), e = end(); i != e; ++i) 488223017Sdim if (Indexes->getNextNonNullIndex(i->start).getBaseIndex() < 489223017Sdim i->end.getBaseIndex()) 490212904Sdim return false; 491212904Sdim return true; 492212904Sdim } 493212904Sdim 494263508Sdim bool operator<(const LiveRange& other) const { 495198892Srdivacky const SlotIndex &thisIndex = beginIndex(); 496198892Srdivacky const SlotIndex &otherIndex = other.beginIndex(); 497263508Sdim return thisIndex < otherIndex; 498193323Sed } 499193323Sed 500239462Sdim void print(raw_ostream &OS) const; 501193323Sed void dump() const; 502193323Sed 503263508Sdim /// \brief Walk the range and assert if any invariants fail to hold. 504239462Sdim /// 505239462Sdim /// Note that this is a no-op when asserts are disabled. 506239462Sdim#ifdef NDEBUG 507239462Sdim void verify() const {} 508239462Sdim#else 509239462Sdim void verify() const; 510239462Sdim#endif 511239462Sdim 512193323Sed private: 513198090Srdivacky 514263508Sdim iterator addSegmentFrom(Segment S, iterator From); 515263508Sdim void extendSegmentEndTo(iterator I, SlotIndex NewEnd); 516263508Sdim iterator extendSegmentStartTo(iterator I, SlotIndex NewStr); 517212904Sdim void markValNoForDeletion(VNInfo *V); 518198892Srdivacky 519263508Sdim }; 520263508Sdim 521263508Sdim inline raw_ostream &operator<<(raw_ostream &OS, const LiveRange &LR) { 522263508Sdim LR.print(OS); 523263508Sdim return OS; 524263508Sdim } 525263508Sdim 526263508Sdim /// LiveInterval - This class represents the liveness of a register, 527263508Sdim /// or stack slot. 528263508Sdim class LiveInterval : public LiveRange { 529263508Sdim public: 530263508Sdim typedef LiveRange super; 531263508Sdim 532263508Sdim const unsigned reg; // the register or stack slot of this interval. 533263508Sdim float weight; // weight of this interval 534263508Sdim 535263508Sdim LiveInterval(unsigned Reg, float Weight) 536263508Sdim : reg(Reg), weight(Weight) {} 537263508Sdim 538263508Sdim /// getSize - Returns the sum of sizes of all the LiveRange's. 539263508Sdim /// 540263508Sdim unsigned getSize() const; 541263508Sdim 542263508Sdim /// isSpillable - Can this interval be spilled? 543263508Sdim bool isSpillable() const { 544263508Sdim return weight != llvm::huge_valf; 545263508Sdim } 546263508Sdim 547263508Sdim /// markNotSpillable - Mark interval as not spillable 548263508Sdim void markNotSpillable() { 549263508Sdim weight = llvm::huge_valf; 550263508Sdim } 551263508Sdim 552263508Sdim bool operator<(const LiveInterval& other) const { 553263508Sdim const SlotIndex &thisIndex = beginIndex(); 554263508Sdim const SlotIndex &otherIndex = other.beginIndex(); 555263508Sdim return thisIndex < otherIndex || 556263508Sdim (thisIndex == otherIndex && reg < other.reg); 557263508Sdim } 558263508Sdim 559263508Sdim void print(raw_ostream &OS) const; 560263508Sdim void dump() const; 561263508Sdim 562263508Sdim private: 563243830Sdim LiveInterval& operator=(const LiveInterval& rhs) LLVM_DELETED_FUNCTION; 564198090Srdivacky 565193323Sed }; 566193323Sed 567198090Srdivacky inline raw_ostream &operator<<(raw_ostream &OS, const LiveInterval &LI) { 568193323Sed LI.print(OS); 569193323Sed return OS; 570193323Sed } 571218893Sdim 572263508Sdim raw_ostream &operator<<(raw_ostream &OS, const LiveRange::Segment &S); 573263508Sdim 574263508Sdim inline bool operator<(SlotIndex V, const LiveRange::Segment &S) { 575263508Sdim return V < S.start; 576263508Sdim } 577263508Sdim 578263508Sdim inline bool operator<(const LiveRange::Segment &S, SlotIndex V) { 579263508Sdim return S.start < V; 580263508Sdim } 581263508Sdim 582263508Sdim /// Helper class for performant LiveRange bulk updates. 583249423Sdim /// 584263508Sdim /// Calling LiveRange::addSegment() repeatedly can be expensive on large 585249423Sdim /// live ranges because segments after the insertion point may need to be 586249423Sdim /// shifted. The LiveRangeUpdater class can defer the shifting when adding 587249423Sdim /// many segments in order. 588249423Sdim /// 589263508Sdim /// The LiveRange will be in an invalid state until flush() is called. 590249423Sdim class LiveRangeUpdater { 591263508Sdim LiveRange *LR; 592249423Sdim SlotIndex LastStart; 593263508Sdim LiveRange::iterator WriteI; 594263508Sdim LiveRange::iterator ReadI; 595263508Sdim SmallVector<LiveRange::Segment, 16> Spills; 596249423Sdim void mergeSpills(); 597249423Sdim 598249423Sdim public: 599263508Sdim /// Create a LiveRangeUpdater for adding segments to LR. 600263508Sdim /// LR will temporarily be in an invalid state until flush() is called. 601263508Sdim LiveRangeUpdater(LiveRange *lr = 0) : LR(lr) {} 602249423Sdim 603249423Sdim ~LiveRangeUpdater() { flush(); } 604249423Sdim 605263508Sdim /// Add a segment to LR and coalesce when possible, just like 606263508Sdim /// LR.addSegment(). Segments should be added in increasing start order for 607263508Sdim /// best performance. 608263508Sdim void add(LiveRange::Segment); 609249423Sdim 610249423Sdim void add(SlotIndex Start, SlotIndex End, VNInfo *VNI) { 611263508Sdim add(LiveRange::Segment(Start, End, VNI)); 612249423Sdim } 613249423Sdim 614263508Sdim /// Return true if the LR is currently in an invalid state, and flush() 615249423Sdim /// needs to be called. 616249423Sdim bool isDirty() const { return LastStart.isValid(); } 617249423Sdim 618263508Sdim /// Flush the updater state to LR so it is valid and contains all added 619249423Sdim /// segments. 620249423Sdim void flush(); 621249423Sdim 622249423Sdim /// Select a different destination live range. 623263508Sdim void setDest(LiveRange *lr) { 624263508Sdim if (LR != lr && isDirty()) 625249423Sdim flush(); 626263508Sdim LR = lr; 627249423Sdim } 628249423Sdim 629249423Sdim /// Get the current destination live range. 630263508Sdim LiveRange *getDest() const { return LR; } 631249423Sdim 632249423Sdim void dump() const; 633249423Sdim void print(raw_ostream&) const; 634249423Sdim }; 635249423Sdim 636249423Sdim inline raw_ostream &operator<<(raw_ostream &OS, const LiveRangeUpdater &X) { 637249423Sdim X.print(OS); 638249423Sdim return OS; 639249423Sdim } 640249423Sdim 641218893Sdim /// ConnectedVNInfoEqClasses - Helper class that can divide VNInfos in a 642218893Sdim /// LiveInterval into equivalence clases of connected components. A 643218893Sdim /// LiveInterval that has multiple connected components can be broken into 644218893Sdim /// multiple LiveIntervals. 645218893Sdim /// 646218893Sdim /// Given a LiveInterval that may have multiple connected components, run: 647218893Sdim /// 648218893Sdim /// unsigned numComps = ConEQ.Classify(LI); 649218893Sdim /// if (numComps > 1) { 650218893Sdim /// // allocate numComps-1 new LiveIntervals into LIS[1..] 651218893Sdim /// ConEQ.Distribute(LIS); 652218893Sdim /// } 653218893Sdim 654218893Sdim class ConnectedVNInfoEqClasses { 655221345Sdim LiveIntervals &LIS; 656221345Sdim IntEqClasses EqClass; 657218893Sdim 658218893Sdim // Note that values a and b are connected. 659218893Sdim void Connect(unsigned a, unsigned b); 660218893Sdim 661218893Sdim unsigned Renumber(); 662218893Sdim 663218893Sdim public: 664221345Sdim explicit ConnectedVNInfoEqClasses(LiveIntervals &lis) : LIS(lis) {} 665218893Sdim 666218893Sdim /// Classify - Classify the values in LI into connected components. 667218893Sdim /// Return the number of connected components. 668218893Sdim unsigned Classify(const LiveInterval *LI); 669218893Sdim 670218893Sdim /// getEqClass - Classify creates equivalence classes numbered 0..N. Return 671218893Sdim /// the equivalence class assigned the VNI. 672221345Sdim unsigned getEqClass(const VNInfo *VNI) const { return EqClass[VNI->id]; } 673218893Sdim 674218893Sdim /// Distribute - Distribute values in LIV[0] into a separate LiveInterval 675218893Sdim /// for each connected component. LIV must have a LiveInterval for each 676218893Sdim /// connected component. The LiveIntervals in Liv[1..] must be empty. 677221345Sdim /// Instructions using LIV[0] are rewritten. 678221345Sdim void Distribute(LiveInterval *LIV[], MachineRegisterInfo &MRI); 679218893Sdim 680218893Sdim }; 681218893Sdim 682193323Sed} 683193323Sed#endif 684