1321369Sdim//===- llvm/CodeGen/LiveInterval.h - Interval representation ----*- C++ -*-===// 2193323Sed// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6193323Sed// 7193323Sed//===----------------------------------------------------------------------===// 8193323Sed// 9193323Sed// This file implements the LiveRange and LiveInterval classes. Given some 10193323Sed// numbering of each the machine instructions an interval [i, j) is said to be a 11261991Sdim// live range for register v if there is no instruction with number j' >= j 12193323Sed// such that v is live at j' and there is no instruction with number i' < i such 13261991Sdim// that v is live at i'. In this implementation ranges can have holes, 14261991Sdim// i.e. a range might look like [1,20), [50,65), [1000,1001). Each 15261991Sdim// individual segment is represented as an instance of LiveRange::Segment, 16261991Sdim// and the whole range is represented as an instance of LiveRange. 17193323Sed// 18193323Sed//===----------------------------------------------------------------------===// 19193323Sed 20193323Sed#ifndef LLVM_CODEGEN_LIVEINTERVAL_H 21193323Sed#define LLVM_CODEGEN_LIVEINTERVAL_H 22193323Sed 23321369Sdim#include "llvm/ADT/ArrayRef.h" 24218893Sdim#include "llvm/ADT/IntEqClasses.h" 25321369Sdim#include "llvm/ADT/STLExtras.h" 26321369Sdim#include "llvm/ADT/SmallVector.h" 27321369Sdim#include "llvm/ADT/iterator_range.h" 28249423Sdim#include "llvm/CodeGen/SlotIndexes.h" 29321369Sdim#include "llvm/MC/LaneBitmask.h" 30193323Sed#include "llvm/Support/Allocator.h" 31321369Sdim#include "llvm/Support/MathExtras.h" 32321369Sdim#include <algorithm> 33193323Sed#include <cassert> 34321369Sdim#include <cstddef> 35321369Sdim#include <functional> 36321369Sdim#include <memory> 37288943Sdim#include <set> 38321369Sdim#include <tuple> 39321369Sdim#include <utility> 40193323Sed 41193323Sednamespace llvm { 42321369Sdim 43243830Sdim class CoalescerPair; 44198892Srdivacky class LiveIntervals; 45194612Sed class MachineRegisterInfo; 46198090Srdivacky class raw_ostream; 47193323Sed 48194612Sed /// VNInfo - Value Number Information. 49194612Sed /// This class holds information about a machine level values, including 50194612Sed /// definition and use points. 51194612Sed /// 52194612Sed class VNInfo { 53194612Sed public: 54321369Sdim using Allocator = BumpPtrAllocator; 55198090Srdivacky 56194612Sed /// The ID number of this value. 57193323Sed unsigned id; 58210299Sed 59234353Sdim /// The index of the defining instruction. 60198892Srdivacky SlotIndex def; 61194612Sed 62194612Sed /// VNInfo constructor. 63321369Sdim VNInfo(unsigned i, SlotIndex d) : id(i), def(d) {} 64194612Sed 65314564Sdim /// VNInfo constructor, copies values from orig, except for the value number. 66321369Sdim VNInfo(unsigned i, const VNInfo &orig) : id(i), def(orig.def) {} 67194612Sed 68198090Srdivacky /// Copy from the parameter into this VNInfo. 69198090Srdivacky void copyFrom(VNInfo &src) { 70198090Srdivacky def = src.def; 71198090Srdivacky } 72198090Srdivacky 73194612Sed /// Returns true if this value is defined by a PHI instruction (or was, 74261991Sdim /// PHI instructions may have been eliminated). 75239462Sdim /// PHI-defs begin at a block boundary, all other defs begin at register or 76239462Sdim /// EC slots. 77239462Sdim bool isPHIDef() const { return def.isBlock(); } 78194612Sed 79194612Sed /// Returns true if this value is unused. 80239462Sdim bool isUnused() const { return !def.isValid(); } 81239462Sdim 82239462Sdim /// Mark this value as unused. 83239462Sdim void markUnused() { def = SlotIndex(); } 84193323Sed }; 85193323Sed 86261991Sdim /// Result of a LiveRange query. This class hides the implementation details 87261991Sdim /// of live ranges, and it should be used as the primary interface for 88261991Sdim /// examining live ranges around instructions. 89261991Sdim class LiveQueryResult { 90261991Sdim VNInfo *const EarlyVal; 91261991Sdim VNInfo *const LateVal; 92261991Sdim const SlotIndex EndPoint; 93261991Sdim const bool Kill; 94193323Sed 95261991Sdim public: 96261991Sdim LiveQueryResult(VNInfo *EarlyVal, VNInfo *LateVal, SlotIndex EndPoint, 97261991Sdim bool Kill) 98261991Sdim : EarlyVal(EarlyVal), LateVal(LateVal), EndPoint(EndPoint), Kill(Kill) 99261991Sdim {} 100249423Sdim 101261991Sdim /// Return the value that is live-in to the instruction. This is the value 102261991Sdim /// that will be read by the instruction's use operands. Return NULL if no 103261991Sdim /// value is live-in. 104261991Sdim VNInfo *valueIn() const { 105261991Sdim return EarlyVal; 106193323Sed } 107193323Sed 108261991Sdim /// Return true if the live-in value is killed by this instruction. This 109261991Sdim /// means that either the live range ends at the instruction, or it changes 110261991Sdim /// value. 111261991Sdim bool isKill() const { 112261991Sdim return Kill; 113193323Sed } 114193323Sed 115261991Sdim /// Return true if this instruction has a dead def. 116261991Sdim bool isDeadDef() const { 117261991Sdim return EndPoint.isDead(); 118198090Srdivacky } 119198090Srdivacky 120261991Sdim /// Return the value leaving the instruction, if any. This can be a 121261991Sdim /// live-through value, or a live def. A dead def returns NULL. 122261991Sdim VNInfo *valueOut() const { 123276479Sdim return isDeadDef() ? nullptr : LateVal; 124193323Sed } 125261991Sdim 126280031Sdim /// Returns the value alive at the end of the instruction, if any. This can 127280031Sdim /// be a live-through value, a live def or a dead def. 128280031Sdim VNInfo *valueOutOrDead() const { 129280031Sdim return LateVal; 130280031Sdim } 131280031Sdim 132261991Sdim /// Return the value defined by this instruction, if any. This includes 133261991Sdim /// dead defs, it is the value created by the instruction's def operands. 134261991Sdim VNInfo *valueDefined() const { 135276479Sdim return EarlyVal == LateVal ? nullptr : LateVal; 136193323Sed } 137193323Sed 138261991Sdim /// Return the end point of the last live range segment to interact with 139261991Sdim /// the instruction, if any. 140261991Sdim /// 141261991Sdim /// The end point is an invalid SlotIndex only if the live range doesn't 142261991Sdim /// intersect the instruction at all. 143261991Sdim /// 144261991Sdim /// The end point may be at or past the end of the instruction's basic 145261991Sdim /// block. That means the value was live out of the block. 146261991Sdim SlotIndex endPoint() const { 147261991Sdim return EndPoint; 148261991Sdim } 149193323Sed }; 150193323Sed 151261991Sdim /// This class represents the liveness of a register, stack slot, etc. 152261991Sdim /// It manages an ordered list of Segment objects. 153261991Sdim /// The Segments are organized in a static single assignment form: At places 154261991Sdim /// where a new value is defined or different values reach a CFG join a new 155261991Sdim /// segment with a new value number is used. 156261991Sdim class LiveRange { 157261991Sdim public: 158261991Sdim /// This represents a simple continuous liveness interval for a value. 159261991Sdim /// The start point is inclusive, the end point exclusive. These intervals 160261991Sdim /// are rendered as [start,end). 161261991Sdim struct Segment { 162261991Sdim SlotIndex start; // Start point of the interval (inclusive) 163261991Sdim SlotIndex end; // End point of the interval (exclusive) 164321369Sdim VNInfo *valno = nullptr; // identifier for the value contained in this 165321369Sdim // segment. 166193323Sed 167321369Sdim Segment() = default; 168193323Sed 169261991Sdim Segment(SlotIndex S, SlotIndex E, VNInfo *V) 170261991Sdim : start(S), end(E), valno(V) { 171261991Sdim assert(S < E && "Cannot create empty or backwards segment"); 172261991Sdim } 173193323Sed 174261991Sdim /// Return true if the index is covered by this segment. 175261991Sdim bool contains(SlotIndex I) const { 176261991Sdim return start <= I && I < end; 177261991Sdim } 178193323Sed 179261991Sdim /// Return true if the given interval, [S, E), is covered by this segment. 180261991Sdim bool containsInterval(SlotIndex S, SlotIndex E) const { 181261991Sdim assert((S < E) && "Backwards interval?"); 182261991Sdim return (start <= S && S < end) && (start < E && E <= end); 183261991Sdim } 184198090Srdivacky 185261991Sdim bool operator<(const Segment &Other) const { 186276479Sdim return std::tie(start, end) < std::tie(Other.start, Other.end); 187261991Sdim } 188261991Sdim bool operator==(const Segment &Other) const { 189261991Sdim return start == Other.start && end == Other.end; 190261991Sdim } 191261991Sdim 192360784Sdim bool operator!=(const Segment &Other) const { 193360784Sdim return !(*this == Other); 194360784Sdim } 195360784Sdim 196261991Sdim void dump() const; 197261991Sdim }; 198261991Sdim 199321369Sdim using Segments = SmallVector<Segment, 2>; 200321369Sdim using VNInfoList = SmallVector<VNInfo *, 2>; 201193323Sed 202261991Sdim Segments segments; // the liveness segments 203193323Sed VNInfoList valnos; // value#'s 204212904Sdim 205288943Sdim // The segment set is used temporarily to accelerate initial computation 206288943Sdim // of live ranges of physical registers in computeRegUnitRange. 207288943Sdim // After that the set is flushed to the segment vector and deleted. 208321369Sdim using SegmentSet = std::set<Segment>; 209288943Sdim std::unique_ptr<SegmentSet> segmentSet; 210288943Sdim 211321369Sdim using iterator = Segments::iterator; 212321369Sdim using const_iterator = Segments::const_iterator; 213321369Sdim 214261991Sdim iterator begin() { return segments.begin(); } 215261991Sdim iterator end() { return segments.end(); } 216193323Sed 217261991Sdim const_iterator begin() const { return segments.begin(); } 218261991Sdim const_iterator end() const { return segments.end(); } 219193323Sed 220321369Sdim using vni_iterator = VNInfoList::iterator; 221321369Sdim using const_vni_iterator = VNInfoList::const_iterator; 222321369Sdim 223193323Sed vni_iterator vni_begin() { return valnos.begin(); } 224261991Sdim vni_iterator vni_end() { return valnos.end(); } 225193323Sed 226193323Sed const_vni_iterator vni_begin() const { return valnos.begin(); } 227261991Sdim const_vni_iterator vni_end() const { return valnos.end(); } 228193323Sed 229280031Sdim /// Constructs a new LiveRange object. 230288943Sdim LiveRange(bool UseSegmentSet = false) 231360784Sdim : segmentSet(UseSegmentSet ? std::make_unique<SegmentSet>() 232288943Sdim : nullptr) {} 233280031Sdim 234280031Sdim /// Constructs a new LiveRange object by copying segments and valnos from 235280031Sdim /// another LiveRange. 236280031Sdim LiveRange(const LiveRange &Other, BumpPtrAllocator &Allocator) { 237288943Sdim assert(Other.segmentSet == nullptr && 238288943Sdim "Copying of LiveRanges with active SegmentSets is not supported"); 239321369Sdim assign(Other, Allocator); 240321369Sdim } 241288943Sdim 242321369Sdim /// Copies values numbers and live segments from \p Other into this range. 243321369Sdim void assign(const LiveRange &Other, BumpPtrAllocator &Allocator) { 244321369Sdim if (this == &Other) 245321369Sdim return; 246321369Sdim 247321369Sdim assert(Other.segmentSet == nullptr && 248321369Sdim "Copying of LiveRanges with active SegmentSets is not supported"); 249280031Sdim // Duplicate valnos. 250321369Sdim for (const VNInfo *VNI : Other.valnos) 251280031Sdim createValueCopy(VNI, Allocator); 252280031Sdim // Now we can copy segments and remap their valnos. 253321369Sdim for (const Segment &S : Other.segments) 254280031Sdim segments.push_back(Segment(S.start, S.end, valnos[S.valno->id])); 255280031Sdim } 256280031Sdim 257261991Sdim /// advanceTo - Advance the specified iterator to point to the Segment 258193323Sed /// containing the specified position, or end() if the position is past the 259261991Sdim /// end of the range. If no Segment contains this position, but the 260203954Srdivacky /// position is in a hole, this method returns an iterator pointing to the 261261991Sdim /// Segment immediately after the hole. 262198892Srdivacky iterator advanceTo(iterator I, SlotIndex Pos) { 263218893Sdim assert(I != end()); 264198090Srdivacky if (Pos >= endIndex()) 265193323Sed return end(); 266193323Sed while (I->end <= Pos) ++I; 267193323Sed return I; 268193323Sed } 269212904Sdim 270280031Sdim const_iterator advanceTo(const_iterator I, SlotIndex Pos) const { 271280031Sdim assert(I != end()); 272280031Sdim if (Pos >= endIndex()) 273280031Sdim return end(); 274280031Sdim while (I->end <= Pos) ++I; 275280031Sdim return I; 276280031Sdim } 277280031Sdim 278261991Sdim /// find - Return an iterator pointing to the first segment that ends after 279218893Sdim /// Pos, or end(). This is the same as advanceTo(begin(), Pos), but faster 280261991Sdim /// when searching large ranges. 281218893Sdim /// 282261991Sdim /// If Pos is contained in a Segment, that segment is returned. 283261991Sdim /// If Pos is in a hole, the following Segment is returned. 284218893Sdim /// If Pos is beyond endIndex, end() is returned. 285218893Sdim iterator find(SlotIndex Pos); 286218893Sdim 287218893Sdim const_iterator find(SlotIndex Pos) const { 288261991Sdim return const_cast<LiveRange*>(this)->find(Pos); 289218893Sdim } 290218893Sdim 291193323Sed void clear() { 292206083Srdivacky valnos.clear(); 293261991Sdim segments.clear(); 294193323Sed } 295193323Sed 296261991Sdim size_t size() const { 297261991Sdim return segments.size(); 298261991Sdim } 299261991Sdim 300193323Sed bool hasAtLeastOneValue() const { return !valnos.empty(); } 301193323Sed 302193323Sed bool containsOneValue() const { return valnos.size() == 1; } 303193323Sed 304193323Sed unsigned getNumValNums() const { return (unsigned)valnos.size(); } 305212904Sdim 306193323Sed /// getValNumInfo - Returns pointer to the specified val#. 307193323Sed /// 308193323Sed inline VNInfo *getValNumInfo(unsigned ValNo) { 309193323Sed return valnos[ValNo]; 310193323Sed } 311193323Sed inline const VNInfo *getValNumInfo(unsigned ValNo) const { 312193323Sed return valnos[ValNo]; 313193323Sed } 314193323Sed 315261991Sdim /// containsValue - Returns true if VNI belongs to this range. 316221345Sdim bool containsValue(const VNInfo *VNI) const { 317221345Sdim return VNI && VNI->id < getNumValNums() && VNI == getValNumInfo(VNI->id); 318221345Sdim } 319221345Sdim 320193323Sed /// getNextValue - Create a new value number and return it. MIIdx specifies 321193323Sed /// the instruction that defines the value number. 322234353Sdim VNInfo *getNextValue(SlotIndex def, VNInfo::Allocator &VNInfoAllocator) { 323210299Sed VNInfo *VNI = 324234353Sdim new (VNInfoAllocator) VNInfo((unsigned)valnos.size(), def); 325193323Sed valnos.push_back(VNI); 326193323Sed return VNI; 327193323Sed } 328193323Sed 329261991Sdim /// createDeadDef - Make sure the range has a value defined at Def. 330239462Sdim /// If one already exists, return it. Otherwise allocate a new value and 331239462Sdim /// add liveness for a dead def. 332341825Sdim VNInfo *createDeadDef(SlotIndex Def, VNInfo::Allocator &VNIAlloc); 333239462Sdim 334314564Sdim /// Create a def of value @p VNI. Return @p VNI. If there already exists 335314564Sdim /// a definition at VNI->def, the value defined there must be @p VNI. 336314564Sdim VNInfo *createDeadDef(VNInfo *VNI); 337314564Sdim 338194612Sed /// Create a copy of the given value. The new value will be identical except 339194612Sed /// for the Value number. 340198090Srdivacky VNInfo *createValueCopy(const VNInfo *orig, 341206083Srdivacky VNInfo::Allocator &VNInfoAllocator) { 342210299Sed VNInfo *VNI = 343210299Sed new (VNInfoAllocator) VNInfo((unsigned)valnos.size(), *orig); 344194612Sed valnos.push_back(VNI); 345194612Sed return VNI; 346194612Sed } 347194612Sed 348212904Sdim /// RenumberValues - Renumber all values in order of appearance and remove 349212904Sdim /// unused values. 350261991Sdim void RenumberValues(); 351212904Sdim 352261991Sdim /// MergeValueNumberInto - This method is called when two value numbers 353193323Sed /// are found to be equivalent. This eliminates V1, replacing all 354261991Sdim /// segments with the V1 value number with the V2 value number. This can 355193323Sed /// cause merging of V1/V2 values numbers and compaction of the value space. 356193323Sed VNInfo* MergeValueNumberInto(VNInfo *V1, VNInfo *V2); 357193323Sed 358261991Sdim /// Merge all of the live segments of a specific val# in RHS into this live 359261991Sdim /// range as the specified value number. The segments in RHS are allowed 360261991Sdim /// to overlap with segments in the current range, it will replace the 361261991Sdim /// value numbers of the overlaped live segments with the specified value 362261991Sdim /// number. 363261991Sdim void MergeSegmentsInAsValue(const LiveRange &RHS, VNInfo *LHSValNo); 364193323Sed 365261991Sdim /// MergeValueInAsValue - Merge all of the segments of a specific val# 366261991Sdim /// in RHS into this live range as the specified value number. 367261991Sdim /// The segments in RHS are allowed to overlap with segments in the 368261991Sdim /// current range, but only if the overlapping segments have the 369193323Sed /// specified value number. 370261991Sdim void MergeValueInAsValue(const LiveRange &RHS, 371193323Sed const VNInfo *RHSValNo, VNInfo *LHSValNo); 372193323Sed 373261991Sdim bool empty() const { return segments.empty(); } 374193323Sed 375261991Sdim /// beginIndex - Return the lowest numbered slot covered. 376198892Srdivacky SlotIndex beginIndex() const { 377261991Sdim assert(!empty() && "Call to beginIndex() on empty range."); 378261991Sdim return segments.front().start; 379193323Sed } 380193323Sed 381261991Sdim /// endNumber - return the maximum point of the range of the whole, 382193323Sed /// exclusive. 383198892Srdivacky SlotIndex endIndex() const { 384261991Sdim assert(!empty() && "Call to endIndex() on empty range."); 385261991Sdim return segments.back().end; 386193323Sed } 387193323Sed 388198892Srdivacky bool expiredAt(SlotIndex index) const { 389198090Srdivacky return index >= endIndex(); 390193323Sed } 391193323Sed 392218893Sdim bool liveAt(SlotIndex index) const { 393218893Sdim const_iterator r = find(index); 394218893Sdim return r != end() && r->start <= index; 395218893Sdim } 396193323Sed 397261991Sdim /// Return the segment that contains the specified index, or null if there 398261991Sdim /// is none. 399261991Sdim const Segment *getSegmentContaining(SlotIndex Idx) const { 400261991Sdim const_iterator I = FindSegmentContaining(Idx); 401276479Sdim return I == end() ? nullptr : &*I; 402193323Sed } 403193323Sed 404261991Sdim /// Return the live segment that contains the specified index, or null if 405261991Sdim /// there is none. 406261991Sdim Segment *getSegmentContaining(SlotIndex Idx) { 407261991Sdim iterator I = FindSegmentContaining(Idx); 408276479Sdim return I == end() ? nullptr : &*I; 409198090Srdivacky } 410198090Srdivacky 411210299Sed /// getVNInfoAt - Return the VNInfo that is live at Idx, or NULL. 412210299Sed VNInfo *getVNInfoAt(SlotIndex Idx) const { 413261991Sdim const_iterator I = FindSegmentContaining(Idx); 414276479Sdim return I == end() ? nullptr : I->valno; 415210299Sed } 416210299Sed 417226633Sdim /// getVNInfoBefore - Return the VNInfo that is live up to but not 418226633Sdim /// necessarilly including Idx, or NULL. Use this to find the reaching def 419226633Sdim /// used by an instruction at this SlotIndex position. 420226633Sdim VNInfo *getVNInfoBefore(SlotIndex Idx) const { 421261991Sdim const_iterator I = FindSegmentContaining(Idx.getPrevSlot()); 422276479Sdim return I == end() ? nullptr : I->valno; 423226633Sdim } 424226633Sdim 425261991Sdim /// Return an iterator to the segment that contains the specified index, or 426261991Sdim /// end() if there is none. 427261991Sdim iterator FindSegmentContaining(SlotIndex Idx) { 428218893Sdim iterator I = find(Idx); 429218893Sdim return I != end() && I->start <= Idx ? I : end(); 430218893Sdim } 431193323Sed 432261991Sdim const_iterator FindSegmentContaining(SlotIndex Idx) const { 433218893Sdim const_iterator I = find(Idx); 434218893Sdim return I != end() && I->start <= Idx ? I : end(); 435218893Sdim } 436193323Sed 437261991Sdim /// overlaps - Return true if the intersection of the two live ranges is 438193323Sed /// not empty. 439261991Sdim bool overlaps(const LiveRange &other) const { 440212904Sdim if (other.empty()) 441212904Sdim return false; 442193323Sed return overlapsFrom(other, other.begin()); 443193323Sed } 444193323Sed 445261991Sdim /// overlaps - Return true if the two ranges have overlapping segments 446243830Sdim /// that are not coalescable according to CP. 447243830Sdim /// 448261991Sdim /// Overlapping segments where one range is defined by a coalescable 449243830Sdim /// copy are allowed. 450261991Sdim bool overlaps(const LiveRange &Other, const CoalescerPair &CP, 451243830Sdim const SlotIndexes&) const; 452243830Sdim 453261991Sdim /// overlaps - Return true if the live range overlaps an interval specified 454193323Sed /// by [Start, End). 455198892Srdivacky bool overlaps(SlotIndex Start, SlotIndex End) const; 456193323Sed 457261991Sdim /// overlapsFrom - Return true if the intersection of the two live ranges 458193323Sed /// is not empty. The specified iterator is a hint that we can begin 459261991Sdim /// scanning the Other range starting at I. 460341825Sdim bool overlapsFrom(const LiveRange &Other, const_iterator StartPos) const; 461193323Sed 462280031Sdim /// Returns true if all segments of the @p Other live range are completely 463280031Sdim /// covered by this live range. 464280031Sdim /// Adjacent live ranges do not affect the covering:the liverange 465280031Sdim /// [1,5](5,10] covers (3,7]. 466280031Sdim bool covers(const LiveRange &Other) const; 467280031Sdim 468261991Sdim /// Add the specified Segment to this range, merging segments as 469261991Sdim /// appropriate. This returns an iterator to the inserted segment (which 470261991Sdim /// may have grown since it was inserted). 471288943Sdim iterator addSegment(Segment S); 472193323Sed 473314564Sdim /// Attempt to extend a value defined after @p StartIdx to include @p Use. 474314564Sdim /// Both @p StartIdx and @p Use should be in the same basic block. In case 475314564Sdim /// of subranges, an extension could be prevented by an explicit "undef" 476314564Sdim /// caused by a <def,read-undef> on a non-overlapping lane. The list of 477314564Sdim /// location of such "undefs" should be provided in @p Undefs. 478314564Sdim /// The return value is a pair: the first element is VNInfo of the value 479314564Sdim /// that was extended (possibly nullptr), the second is a boolean value 480314564Sdim /// indicating whether an "undef" was encountered. 481288943Sdim /// If this range is live before @p Use in the basic block that starts at 482314564Sdim /// @p StartIdx, and there is no intervening "undef", extend it to be live 483314564Sdim /// up to @p Use, and return the pair {value, false}. If there is no 484314564Sdim /// segment before @p Use and there is no "undef" between @p StartIdx and 485314564Sdim /// @p Use, return {nullptr, false}. If there is an "undef" before @p Use, 486314564Sdim /// return {nullptr, true}. 487314564Sdim std::pair<VNInfo*,bool> extendInBlock(ArrayRef<SlotIndex> Undefs, 488341825Sdim SlotIndex StartIdx, SlotIndex Kill); 489221345Sdim 490314564Sdim /// Simplified version of the above "extendInBlock", which assumes that 491314564Sdim /// no register lanes are undefined by <def,read-undef> operands. 492314564Sdim /// If this range is live before @p Use in the basic block that starts 493314564Sdim /// at @p StartIdx, extend it to be live up to @p Use, and return the 494314564Sdim /// value. If there is no segment before @p Use, return nullptr. 495314564Sdim VNInfo *extendInBlock(SlotIndex StartIdx, SlotIndex Kill); 496314564Sdim 497261991Sdim /// join - Join two live ranges (this, and other) together. This applies 498261991Sdim /// mappings to the value numbers in the LHS/RHS ranges as specified. If 499261991Sdim /// the ranges are not joinable, this aborts. 500261991Sdim void join(LiveRange &Other, 501198892Srdivacky const int *ValNoAssignments, 502193323Sed const int *RHSValNoAssignments, 503261991Sdim SmallVectorImpl<VNInfo *> &NewVNInfo); 504193323Sed 505261991Sdim /// True iff this segment is a single segment that lies between the 506251662Sdim /// specified boundaries, exclusively. Vregs live across a backedge are not 507251662Sdim /// considered local. The boundaries are expected to lie within an extended 508251662Sdim /// basic block, so vregs that are not live out should contain no holes. 509251662Sdim bool isLocal(SlotIndex Start, SlotIndex End) const { 510251662Sdim return beginIndex() > Start.getBaseIndex() && 511251662Sdim endIndex() < End.getBoundaryIndex(); 512251662Sdim } 513251662Sdim 514261991Sdim /// Remove the specified segment from this range. Note that the segment 515261991Sdim /// must be a single Segment in its entirety. 516261991Sdim void removeSegment(SlotIndex Start, SlotIndex End, 517261991Sdim bool RemoveDeadValNo = false); 518193323Sed 519261991Sdim void removeSegment(Segment S, bool RemoveDeadValNo = false) { 520261991Sdim removeSegment(S.start, S.end, RemoveDeadValNo); 521193323Sed } 522193323Sed 523280031Sdim /// Remove segment pointed to by iterator @p I from this range. This does 524280031Sdim /// not remove dead value numbers. 525280031Sdim iterator removeSegment(iterator I) { 526280031Sdim return segments.erase(I); 527280031Sdim } 528280031Sdim 529261991Sdim /// Query Liveness at Idx. 530261991Sdim /// The sub-instruction slot of Idx doesn't matter, only the instruction 531261991Sdim /// it refers to is considered. 532261991Sdim LiveQueryResult Query(SlotIndex Idx) const { 533261991Sdim // Find the segment that enters the instruction. 534261991Sdim const_iterator I = find(Idx.getBaseIndex()); 535261991Sdim const_iterator E = end(); 536261991Sdim if (I == E) 537276479Sdim return LiveQueryResult(nullptr, nullptr, SlotIndex(), false); 538261991Sdim 539261991Sdim // Is this an instruction live-in segment? 540261991Sdim // If Idx is the start index of a basic block, include live-in segments 541261991Sdim // that start at Idx.getBaseIndex(). 542276479Sdim VNInfo *EarlyVal = nullptr; 543276479Sdim VNInfo *LateVal = nullptr; 544261991Sdim SlotIndex EndPoint; 545261991Sdim bool Kill = false; 546261991Sdim if (I->start <= Idx.getBaseIndex()) { 547261991Sdim EarlyVal = I->valno; 548261991Sdim EndPoint = I->end; 549261991Sdim // Move to the potentially live-out segment. 550261991Sdim if (SlotIndex::isSameInstr(Idx, I->end)) { 551261991Sdim Kill = true; 552261991Sdim if (++I == E) 553261991Sdim return LiveQueryResult(EarlyVal, LateVal, EndPoint, Kill); 554261991Sdim } 555261991Sdim // Special case: A PHIDef value can have its def in the middle of a 556261991Sdim // segment if the value happens to be live out of the layout 557261991Sdim // predecessor. 558261991Sdim // Such a value is not live-in. 559261991Sdim if (EarlyVal->def == Idx.getBaseIndex()) 560276479Sdim EarlyVal = nullptr; 561261991Sdim } 562261991Sdim // I now points to the segment that may be live-through, or defined by 563261991Sdim // this instr. Ignore segments starting after the current instr. 564261991Sdim if (!SlotIndex::isEarlierInstr(Idx, I->start)) { 565261991Sdim LateVal = I->valno; 566261991Sdim EndPoint = I->end; 567261991Sdim } 568261991Sdim return LiveQueryResult(EarlyVal, LateVal, EndPoint, Kill); 569261991Sdim } 570261991Sdim 571261991Sdim /// removeValNo - Remove all the segments defined by the specified value#. 572193323Sed /// Also remove the value# from value# list. 573193323Sed void removeValNo(VNInfo *ValNo); 574193323Sed 575261991Sdim /// Returns true if the live range is zero length, i.e. no live segments 576261991Sdim /// span instructions. It doesn't pay to spill such a range. 577223017Sdim bool isZeroLength(SlotIndexes *Indexes) const { 578280031Sdim for (const Segment &S : segments) 579280031Sdim if (Indexes->getNextNonNullIndex(S.start).getBaseIndex() < 580280031Sdim S.end.getBaseIndex()) 581212904Sdim return false; 582212904Sdim return true; 583212904Sdim } 584212904Sdim 585296417Sdim // Returns true if any segment in the live range contains any of the 586296417Sdim // provided slot indexes. Slots which occur in holes between 587296417Sdim // segments will not cause the function to return true. 588296417Sdim bool isLiveAtIndexes(ArrayRef<SlotIndex> Slots) const; 589296417Sdim 590261991Sdim bool operator<(const LiveRange& other) const { 591198892Srdivacky const SlotIndex &thisIndex = beginIndex(); 592198892Srdivacky const SlotIndex &otherIndex = other.beginIndex(); 593261991Sdim return thisIndex < otherIndex; 594193323Sed } 595193323Sed 596314564Sdim /// Returns true if there is an explicit "undef" between @p Begin 597314564Sdim /// @p End. 598314564Sdim bool isUndefIn(ArrayRef<SlotIndex> Undefs, SlotIndex Begin, 599314564Sdim SlotIndex End) const { 600314564Sdim return std::any_of(Undefs.begin(), Undefs.end(), 601314564Sdim [Begin,End] (SlotIndex Idx) -> bool { 602314564Sdim return Begin <= Idx && Idx < End; 603314564Sdim }); 604314564Sdim } 605314564Sdim 606288943Sdim /// Flush segment set into the regular segment vector. 607288943Sdim /// The method is to be called after the live range 608288943Sdim /// has been created, if use of the segment set was 609288943Sdim /// activated in the constructor of the live range. 610288943Sdim void flushSegmentSet(); 611288943Sdim 612353358Sdim /// Stores indexes from the input index sequence R at which this LiveRange 613353358Sdim /// is live to the output O iterator. 614353358Sdim /// R is a range of _ascending sorted_ _random_ access iterators 615353358Sdim /// to the input indexes. Indexes stored at O are ascending sorted so it 616353358Sdim /// can be used directly in the subsequent search (for example for 617353358Sdim /// subranges). Returns true if found at least one index. 618353358Sdim template <typename Range, typename OutputIt> 619353358Sdim bool findIndexesLiveAt(Range &&R, OutputIt O) const { 620353358Sdim assert(std::is_sorted(R.begin(), R.end())); 621353358Sdim auto Idx = R.begin(), EndIdx = R.end(); 622353358Sdim auto Seg = segments.begin(), EndSeg = segments.end(); 623353358Sdim bool Found = false; 624353358Sdim while (Idx != EndIdx && Seg != EndSeg) { 625353358Sdim // if the Seg is lower find first segment that is above Idx using binary 626353358Sdim // search 627353358Sdim if (Seg->end <= *Idx) { 628353358Sdim Seg = std::upper_bound(++Seg, EndSeg, *Idx, 629353358Sdim [=](typename std::remove_reference<decltype(*Idx)>::type V, 630353358Sdim const typename std::remove_reference<decltype(*Seg)>::type &S) { 631353358Sdim return V < S.end; 632353358Sdim }); 633353358Sdim if (Seg == EndSeg) 634353358Sdim break; 635353358Sdim } 636353358Sdim auto NotLessStart = std::lower_bound(Idx, EndIdx, Seg->start); 637353358Sdim if (NotLessStart == EndIdx) 638353358Sdim break; 639353358Sdim auto NotLessEnd = std::lower_bound(NotLessStart, EndIdx, Seg->end); 640353358Sdim if (NotLessEnd != NotLessStart) { 641353358Sdim Found = true; 642353358Sdim O = std::copy(NotLessStart, NotLessEnd, O); 643353358Sdim } 644353358Sdim Idx = NotLessEnd; 645353358Sdim ++Seg; 646353358Sdim } 647353358Sdim return Found; 648353358Sdim } 649353358Sdim 650239462Sdim void print(raw_ostream &OS) const; 651193323Sed void dump() const; 652193323Sed 653341825Sdim /// Walk the range and assert if any invariants fail to hold. 654239462Sdim /// 655239462Sdim /// Note that this is a no-op when asserts are disabled. 656239462Sdim#ifdef NDEBUG 657239462Sdim void verify() const {} 658239462Sdim#else 659239462Sdim void verify() const; 660239462Sdim#endif 661239462Sdim 662280031Sdim protected: 663280031Sdim /// Append a segment to the list of segments. 664280031Sdim void append(const LiveRange::Segment S); 665280031Sdim 666193323Sed private: 667288943Sdim friend class LiveRangeUpdater; 668288943Sdim void addSegmentToSet(Segment S); 669212904Sdim void markValNoForDeletion(VNInfo *V); 670261991Sdim }; 671261991Sdim 672261991Sdim inline raw_ostream &operator<<(raw_ostream &OS, const LiveRange &LR) { 673261991Sdim LR.print(OS); 674261991Sdim return OS; 675261991Sdim } 676261991Sdim 677261991Sdim /// LiveInterval - This class represents the liveness of a register, 678261991Sdim /// or stack slot. 679261991Sdim class LiveInterval : public LiveRange { 680261991Sdim public: 681321369Sdim using super = LiveRange; 682261991Sdim 683280031Sdim /// A live range for subregisters. The LaneMask specifies which parts of the 684280031Sdim /// super register are covered by the interval. 685280031Sdim /// (@sa TargetRegisterInfo::getSubRegIndexLaneMask()). 686280031Sdim class SubRange : public LiveRange { 687280031Sdim public: 688321369Sdim SubRange *Next = nullptr; 689296417Sdim LaneBitmask LaneMask; 690280031Sdim 691280031Sdim /// Constructs a new SubRange object. 692321369Sdim SubRange(LaneBitmask LaneMask) : LaneMask(LaneMask) {} 693280031Sdim 694280031Sdim /// Constructs a new SubRange object by copying liveness from @p Other. 695296417Sdim SubRange(LaneBitmask LaneMask, const LiveRange &Other, 696280031Sdim BumpPtrAllocator &Allocator) 697321369Sdim : LiveRange(Other, Allocator), LaneMask(LaneMask) {} 698309124Sdim 699309124Sdim void print(raw_ostream &OS) const; 700309124Sdim void dump() const; 701280031Sdim }; 702280031Sdim 703280031Sdim private: 704321369Sdim SubRange *SubRanges = nullptr; ///< Single linked list of subregister live 705321369Sdim /// ranges. 706280031Sdim 707280031Sdim public: 708261991Sdim const unsigned reg; // the register or stack slot of this interval. 709261991Sdim float weight; // weight of this interval 710261991Sdim 711321369Sdim LiveInterval(unsigned Reg, float Weight) : reg(Reg), weight(Weight) {} 712261991Sdim 713288943Sdim ~LiveInterval() { 714288943Sdim clearSubRanges(); 715288943Sdim } 716288943Sdim 717280031Sdim template<typename T> 718280031Sdim class SingleLinkedListIterator { 719280031Sdim T *P; 720321369Sdim 721280031Sdim public: 722280031Sdim SingleLinkedListIterator<T>(T *P) : P(P) {} 723321369Sdim 724280031Sdim SingleLinkedListIterator<T> &operator++() { 725280031Sdim P = P->Next; 726280031Sdim return *this; 727280031Sdim } 728314564Sdim SingleLinkedListIterator<T> operator++(int) { 729280031Sdim SingleLinkedListIterator res = *this; 730280031Sdim ++*this; 731280031Sdim return res; 732280031Sdim } 733280031Sdim bool operator!=(const SingleLinkedListIterator<T> &Other) { 734280031Sdim return P != Other.operator->(); 735280031Sdim } 736280031Sdim bool operator==(const SingleLinkedListIterator<T> &Other) { 737280031Sdim return P == Other.operator->(); 738280031Sdim } 739280031Sdim T &operator*() const { 740280031Sdim return *P; 741280031Sdim } 742280031Sdim T *operator->() const { 743280031Sdim return P; 744280031Sdim } 745280031Sdim }; 746280031Sdim 747321369Sdim using subrange_iterator = SingleLinkedListIterator<SubRange>; 748321369Sdim using const_subrange_iterator = SingleLinkedListIterator<const SubRange>; 749321369Sdim 750280031Sdim subrange_iterator subrange_begin() { 751280031Sdim return subrange_iterator(SubRanges); 752280031Sdim } 753280031Sdim subrange_iterator subrange_end() { 754280031Sdim return subrange_iterator(nullptr); 755280031Sdim } 756280031Sdim 757280031Sdim const_subrange_iterator subrange_begin() const { 758280031Sdim return const_subrange_iterator(SubRanges); 759280031Sdim } 760280031Sdim const_subrange_iterator subrange_end() const { 761280031Sdim return const_subrange_iterator(nullptr); 762280031Sdim } 763280031Sdim 764280031Sdim iterator_range<subrange_iterator> subranges() { 765280031Sdim return make_range(subrange_begin(), subrange_end()); 766280031Sdim } 767280031Sdim 768280031Sdim iterator_range<const_subrange_iterator> subranges() const { 769280031Sdim return make_range(subrange_begin(), subrange_end()); 770280031Sdim } 771280031Sdim 772280031Sdim /// Creates a new empty subregister live range. The range is added at the 773280031Sdim /// beginning of the subrange list; subrange iterators stay valid. 774296417Sdim SubRange *createSubRange(BumpPtrAllocator &Allocator, 775296417Sdim LaneBitmask LaneMask) { 776280031Sdim SubRange *Range = new (Allocator) SubRange(LaneMask); 777280031Sdim appendSubRange(Range); 778280031Sdim return Range; 779280031Sdim } 780280031Sdim 781280031Sdim /// Like createSubRange() but the new range is filled with a copy of the 782280031Sdim /// liveness information in @p CopyFrom. 783296417Sdim SubRange *createSubRangeFrom(BumpPtrAllocator &Allocator, 784296417Sdim LaneBitmask LaneMask, 785280031Sdim const LiveRange &CopyFrom) { 786280031Sdim SubRange *Range = new (Allocator) SubRange(LaneMask, CopyFrom, Allocator); 787280031Sdim appendSubRange(Range); 788280031Sdim return Range; 789280031Sdim } 790280031Sdim 791280031Sdim /// Returns true if subregister liveness information is available. 792280031Sdim bool hasSubRanges() const { 793280031Sdim return SubRanges != nullptr; 794280031Sdim } 795280031Sdim 796280031Sdim /// Removes all subregister liveness information. 797288943Sdim void clearSubRanges(); 798280031Sdim 799280031Sdim /// Removes all subranges without any segments (subranges without segments 800280031Sdim /// are not considered valid and should only exist temporarily). 801280031Sdim void removeEmptySubRanges(); 802280031Sdim 803261991Sdim /// getSize - Returns the sum of sizes of all the LiveRange's. 804261991Sdim /// 805261991Sdim unsigned getSize() const; 806261991Sdim 807261991Sdim /// isSpillable - Can this interval be spilled? 808261991Sdim bool isSpillable() const { 809321369Sdim return weight != huge_valf; 810261991Sdim } 811261991Sdim 812261991Sdim /// markNotSpillable - Mark interval as not spillable 813261991Sdim void markNotSpillable() { 814321369Sdim weight = huge_valf; 815261991Sdim } 816261991Sdim 817314564Sdim /// For a given lane mask @p LaneMask, compute indexes at which the 818314564Sdim /// lane is marked undefined by subregister <def,read-undef> definitions. 819314564Sdim void computeSubRangeUndefs(SmallVectorImpl<SlotIndex> &Undefs, 820314564Sdim LaneBitmask LaneMask, 821314564Sdim const MachineRegisterInfo &MRI, 822314564Sdim const SlotIndexes &Indexes) const; 823314564Sdim 824321369Sdim /// Refines the subranges to support \p LaneMask. This may only be called 825321369Sdim /// for LI.hasSubrange()==true. Subregister ranges are split or created 826321369Sdim /// until \p LaneMask can be matched exactly. \p Mod is executed on the 827321369Sdim /// matching subranges. 828321369Sdim /// 829321369Sdim /// Example: 830321369Sdim /// Given an interval with subranges with lanemasks L0F00, L00F0 and 831321369Sdim /// L000F, refining for mask L0018. Will split the L00F0 lane into 832321369Sdim /// L00E0 and L0010 and the L000F lane into L0007 and L0008. The Mod 833321369Sdim /// function will be applied to the L0010 and L0008 subranges. 834353358Sdim /// 835353358Sdim /// \p Indexes and \p TRI are required to clean up the VNIs that 836353358Sdim /// don't defne the related lane masks after they get shrunk. E.g., 837353358Sdim /// when L000F gets split into L0007 and L0008 maybe only a subset 838353358Sdim /// of the VNIs that defined L000F defines L0007. 839360784Sdim /// 840360784Sdim /// The clean up of the VNIs need to look at the actual instructions 841360784Sdim /// to decide what is or is not live at a definition point. If the 842360784Sdim /// update of the subranges occurs while the IR does not reflect these 843360784Sdim /// changes, \p ComposeSubRegIdx can be used to specify how the 844360784Sdim /// definition are going to be rewritten. 845360784Sdim /// E.g., let say we want to merge: 846360784Sdim /// V1.sub1:<2 x s32> = COPY V2.sub3:<4 x s32> 847360784Sdim /// We do that by choosing a class where sub1:<2 x s32> and sub3:<4 x s32> 848360784Sdim /// overlap, i.e., by choosing a class where we can find "offset + 1 == 3". 849360784Sdim /// Put differently we align V2's sub3 with V1's sub1: 850360784Sdim /// V2: sub0 sub1 sub2 sub3 851360784Sdim /// V1: <offset> sub0 sub1 852360784Sdim /// 853360784Sdim /// This offset will look like a composed subregidx in the the class: 854360784Sdim /// V1.(composed sub2 with sub1):<4 x s32> = COPY V2.sub3:<4 x s32> 855360784Sdim /// => V1.(composed sub2 with sub1):<4 x s32> = COPY V2.sub3:<4 x s32> 856360784Sdim /// 857360784Sdim /// Now if we didn't rewrite the uses and def of V1, all the checks for V1 858360784Sdim /// need to account for this offset. 859360784Sdim /// This happens during coalescing where we update the live-ranges while 860360784Sdim /// still having the old IR around because updating the IR on-the-fly 861360784Sdim /// would actually clobber some information on how the live-ranges that 862360784Sdim /// are being updated look like. 863321369Sdim void refineSubRanges(BumpPtrAllocator &Allocator, LaneBitmask LaneMask, 864353358Sdim std::function<void(LiveInterval::SubRange &)> Apply, 865353358Sdim const SlotIndexes &Indexes, 866360784Sdim const TargetRegisterInfo &TRI, 867360784Sdim unsigned ComposeSubRegIdx = 0); 868321369Sdim 869261991Sdim bool operator<(const LiveInterval& other) const { 870261991Sdim const SlotIndex &thisIndex = beginIndex(); 871261991Sdim const SlotIndex &otherIndex = other.beginIndex(); 872276479Sdim return std::tie(thisIndex, reg) < std::tie(otherIndex, other.reg); 873261991Sdim } 874261991Sdim 875261991Sdim void print(raw_ostream &OS) const; 876261991Sdim void dump() const; 877261991Sdim 878341825Sdim /// Walks the interval and assert if any invariants fail to hold. 879280031Sdim /// 880280031Sdim /// Note that this is a no-op when asserts are disabled. 881280031Sdim#ifdef NDEBUG 882280031Sdim void verify(const MachineRegisterInfo *MRI = nullptr) const {} 883280031Sdim#else 884280031Sdim void verify(const MachineRegisterInfo *MRI = nullptr) const; 885280031Sdim#endif 886280031Sdim 887261991Sdim private: 888280031Sdim /// Appends @p Range to SubRanges list. 889280031Sdim void appendSubRange(SubRange *Range) { 890280031Sdim Range->Next = SubRanges; 891280031Sdim SubRanges = Range; 892280031Sdim } 893288943Sdim 894288943Sdim /// Free memory held by SubRange. 895288943Sdim void freeSubRange(SubRange *S); 896193323Sed }; 897193323Sed 898309124Sdim inline raw_ostream &operator<<(raw_ostream &OS, 899309124Sdim const LiveInterval::SubRange &SR) { 900309124Sdim SR.print(OS); 901309124Sdim return OS; 902309124Sdim } 903309124Sdim 904198090Srdivacky inline raw_ostream &operator<<(raw_ostream &OS, const LiveInterval &LI) { 905193323Sed LI.print(OS); 906193323Sed return OS; 907193323Sed } 908218893Sdim 909261991Sdim raw_ostream &operator<<(raw_ostream &OS, const LiveRange::Segment &S); 910261991Sdim 911261991Sdim inline bool operator<(SlotIndex V, const LiveRange::Segment &S) { 912261991Sdim return V < S.start; 913261991Sdim } 914261991Sdim 915261991Sdim inline bool operator<(const LiveRange::Segment &S, SlotIndex V) { 916261991Sdim return S.start < V; 917261991Sdim } 918261991Sdim 919261991Sdim /// Helper class for performant LiveRange bulk updates. 920249423Sdim /// 921261991Sdim /// Calling LiveRange::addSegment() repeatedly can be expensive on large 922249423Sdim /// live ranges because segments after the insertion point may need to be 923249423Sdim /// shifted. The LiveRangeUpdater class can defer the shifting when adding 924249423Sdim /// many segments in order. 925249423Sdim /// 926261991Sdim /// The LiveRange will be in an invalid state until flush() is called. 927249423Sdim class LiveRangeUpdater { 928261991Sdim LiveRange *LR; 929249423Sdim SlotIndex LastStart; 930261991Sdim LiveRange::iterator WriteI; 931261991Sdim LiveRange::iterator ReadI; 932261991Sdim SmallVector<LiveRange::Segment, 16> Spills; 933249423Sdim void mergeSpills(); 934249423Sdim 935249423Sdim public: 936261991Sdim /// Create a LiveRangeUpdater for adding segments to LR. 937261991Sdim /// LR will temporarily be in an invalid state until flush() is called. 938276479Sdim LiveRangeUpdater(LiveRange *lr = nullptr) : LR(lr) {} 939249423Sdim 940249423Sdim ~LiveRangeUpdater() { flush(); } 941249423Sdim 942261991Sdim /// Add a segment to LR and coalesce when possible, just like 943261991Sdim /// LR.addSegment(). Segments should be added in increasing start order for 944261991Sdim /// best performance. 945261991Sdim void add(LiveRange::Segment); 946249423Sdim 947249423Sdim void add(SlotIndex Start, SlotIndex End, VNInfo *VNI) { 948261991Sdim add(LiveRange::Segment(Start, End, VNI)); 949249423Sdim } 950249423Sdim 951261991Sdim /// Return true if the LR is currently in an invalid state, and flush() 952249423Sdim /// needs to be called. 953249423Sdim bool isDirty() const { return LastStart.isValid(); } 954249423Sdim 955261991Sdim /// Flush the updater state to LR so it is valid and contains all added 956249423Sdim /// segments. 957249423Sdim void flush(); 958249423Sdim 959249423Sdim /// Select a different destination live range. 960261991Sdim void setDest(LiveRange *lr) { 961261991Sdim if (LR != lr && isDirty()) 962249423Sdim flush(); 963261991Sdim LR = lr; 964249423Sdim } 965249423Sdim 966249423Sdim /// Get the current destination live range. 967261991Sdim LiveRange *getDest() const { return LR; } 968249423Sdim 969249423Sdim void dump() const; 970249423Sdim void print(raw_ostream&) const; 971249423Sdim }; 972249423Sdim 973249423Sdim inline raw_ostream &operator<<(raw_ostream &OS, const LiveRangeUpdater &X) { 974249423Sdim X.print(OS); 975249423Sdim return OS; 976249423Sdim } 977249423Sdim 978218893Sdim /// ConnectedVNInfoEqClasses - Helper class that can divide VNInfos in a 979218893Sdim /// LiveInterval into equivalence clases of connected components. A 980218893Sdim /// LiveInterval that has multiple connected components can be broken into 981218893Sdim /// multiple LiveIntervals. 982218893Sdim /// 983218893Sdim /// Given a LiveInterval that may have multiple connected components, run: 984218893Sdim /// 985218893Sdim /// unsigned numComps = ConEQ.Classify(LI); 986218893Sdim /// if (numComps > 1) { 987218893Sdim /// // allocate numComps-1 new LiveIntervals into LIS[1..] 988218893Sdim /// ConEQ.Distribute(LIS); 989218893Sdim /// } 990218893Sdim 991218893Sdim class ConnectedVNInfoEqClasses { 992221345Sdim LiveIntervals &LIS; 993221345Sdim IntEqClasses EqClass; 994218893Sdim 995218893Sdim public: 996221345Sdim explicit ConnectedVNInfoEqClasses(LiveIntervals &lis) : LIS(lis) {} 997218893Sdim 998296417Sdim /// Classify the values in \p LR into connected components. 999296417Sdim /// Returns the number of connected components. 1000296417Sdim unsigned Classify(const LiveRange &LR); 1001218893Sdim 1002218893Sdim /// getEqClass - Classify creates equivalence classes numbered 0..N. Return 1003218893Sdim /// the equivalence class assigned the VNI. 1004221345Sdim unsigned getEqClass(const VNInfo *VNI) const { return EqClass[VNI->id]; } 1005218893Sdim 1006296417Sdim /// Distribute values in \p LI into a separate LiveIntervals 1007296417Sdim /// for each connected component. LIV must have an empty LiveInterval for 1008296417Sdim /// each additional connected component. The first connected component is 1009296417Sdim /// left in \p LI. 1010296417Sdim void Distribute(LiveInterval &LI, LiveInterval *LIV[], 1011296417Sdim MachineRegisterInfo &MRI); 1012218893Sdim }; 1013321369Sdim 1014321369Sdim} // end namespace llvm 1015321369Sdim 1016321369Sdim#endif // LLVM_CODEGEN_LIVEINTERVAL_H 1017