1 //===- llvm/CodeGen/LiveInterval.h - Interval representation ----*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file implements the LiveRange and LiveInterval classes. Given some 10 // numbering of each the machine instructions an interval [i, j) is said to be a 11 // live range for register v if there is no instruction with number j' >= j 12 // such that v is live at j' and there is no instruction with number i' < i such 13 // that v is live at i'. In this implementation ranges can have holes, 14 // i.e. a range might look like [1,20), [50,65), [1000,1001). Each 15 // individual segment is represented as an instance of LiveRange::Segment, 16 // and the whole range is represented as an instance of LiveRange. 17 // 18 //===----------------------------------------------------------------------===// 19 20 #ifndef LLVM_CODEGEN_LIVEINTERVAL_H 21 #define LLVM_CODEGEN_LIVEINTERVAL_H 22 23 #include "llvm/ADT/ArrayRef.h" 24 #include "llvm/ADT/IntEqClasses.h" 25 #include "llvm/ADT/STLExtras.h" 26 #include "llvm/ADT/SmallVector.h" 27 #include "llvm/ADT/iterator_range.h" 28 #include "llvm/CodeGen/SlotIndexes.h" 29 #include "llvm/MC/LaneBitmask.h" 30 #include "llvm/Support/Allocator.h" 31 #include "llvm/Support/MathExtras.h" 32 #include <algorithm> 33 #include <cassert> 34 #include <cstddef> 35 #include <functional> 36 #include <memory> 37 #include <set> 38 #include <tuple> 39 #include <utility> 40 41 namespace llvm { 42 43 class CoalescerPair; 44 class LiveIntervals; 45 class MachineRegisterInfo; 46 class raw_ostream; 47 48 /// VNInfo - Value Number Information. 49 /// This class holds information about a machine level values, including 50 /// definition and use points. 51 /// 52 class VNInfo { 53 public: 54 using Allocator = BumpPtrAllocator; 55 56 /// The ID number of this value. 57 unsigned id; 58 59 /// The index of the defining instruction. 60 SlotIndex def; 61 62 /// VNInfo constructor. VNInfo(unsigned i,SlotIndex d)63 VNInfo(unsigned i, SlotIndex d) : id(i), def(d) {} 64 65 /// VNInfo constructor, copies values from orig, except for the value number. VNInfo(unsigned i,const VNInfo & orig)66 VNInfo(unsigned i, const VNInfo &orig) : id(i), def(orig.def) {} 67 68 /// Copy from the parameter into this VNInfo. copyFrom(VNInfo & src)69 void copyFrom(VNInfo &src) { 70 def = src.def; 71 } 72 73 /// Returns true if this value is defined by a PHI instruction (or was, 74 /// PHI instructions may have been eliminated). 75 /// PHI-defs begin at a block boundary, all other defs begin at register or 76 /// EC slots. isPHIDef()77 bool isPHIDef() const { return def.isBlock(); } 78 79 /// Returns true if this value is unused. isUnused()80 bool isUnused() const { return !def.isValid(); } 81 82 /// Mark this value as unused. markUnused()83 void markUnused() { def = SlotIndex(); } 84 }; 85 86 /// Result of a LiveRange query. This class hides the implementation details 87 /// of live ranges, and it should be used as the primary interface for 88 /// examining live ranges around instructions. 89 class LiveQueryResult { 90 VNInfo *const EarlyVal; 91 VNInfo *const LateVal; 92 const SlotIndex EndPoint; 93 const bool Kill; 94 95 public: LiveQueryResult(VNInfo * EarlyVal,VNInfo * LateVal,SlotIndex EndPoint,bool Kill)96 LiveQueryResult(VNInfo *EarlyVal, VNInfo *LateVal, SlotIndex EndPoint, 97 bool Kill) 98 : EarlyVal(EarlyVal), LateVal(LateVal), EndPoint(EndPoint), Kill(Kill) 99 {} 100 101 /// Return the value that is live-in to the instruction. This is the value 102 /// that will be read by the instruction's use operands. Return NULL if no 103 /// value is live-in. valueIn()104 VNInfo *valueIn() const { 105 return EarlyVal; 106 } 107 108 /// Return true if the live-in value is killed by this instruction. This 109 /// means that either the live range ends at the instruction, or it changes 110 /// value. isKill()111 bool isKill() const { 112 return Kill; 113 } 114 115 /// Return true if this instruction has a dead def. isDeadDef()116 bool isDeadDef() const { 117 return EndPoint.isDead(); 118 } 119 120 /// Return the value leaving the instruction, if any. This can be a 121 /// live-through value, or a live def. A dead def returns NULL. valueOut()122 VNInfo *valueOut() const { 123 return isDeadDef() ? nullptr : LateVal; 124 } 125 126 /// Returns the value alive at the end of the instruction, if any. This can 127 /// be a live-through value, a live def or a dead def. valueOutOrDead()128 VNInfo *valueOutOrDead() const { 129 return LateVal; 130 } 131 132 /// Return the value defined by this instruction, if any. This includes 133 /// dead defs, it is the value created by the instruction's def operands. valueDefined()134 VNInfo *valueDefined() const { 135 return EarlyVal == LateVal ? nullptr : LateVal; 136 } 137 138 /// Return the end point of the last live range segment to interact with 139 /// the instruction, if any. 140 /// 141 /// The end point is an invalid SlotIndex only if the live range doesn't 142 /// intersect the instruction at all. 143 /// 144 /// The end point may be at or past the end of the instruction's basic 145 /// block. That means the value was live out of the block. endPoint()146 SlotIndex endPoint() const { 147 return EndPoint; 148 } 149 }; 150 151 /// This class represents the liveness of a register, stack slot, etc. 152 /// It manages an ordered list of Segment objects. 153 /// The Segments are organized in a static single assignment form: At places 154 /// where a new value is defined or different values reach a CFG join a new 155 /// segment with a new value number is used. 156 class LiveRange { 157 public: 158 /// This represents a simple continuous liveness interval for a value. 159 /// The start point is inclusive, the end point exclusive. These intervals 160 /// are rendered as [start,end). 161 struct Segment { 162 SlotIndex start; // Start point of the interval (inclusive) 163 SlotIndex end; // End point of the interval (exclusive) 164 VNInfo *valno = nullptr; // identifier for the value contained in this 165 // segment. 166 167 Segment() = default; 168 SegmentSegment169 Segment(SlotIndex S, SlotIndex E, VNInfo *V) 170 : start(S), end(E), valno(V) { 171 assert(S < E && "Cannot create empty or backwards segment"); 172 } 173 174 /// Return true if the index is covered by this segment. containsSegment175 bool contains(SlotIndex I) const { 176 return start <= I && I < end; 177 } 178 179 /// Return true if the given interval, [S, E), is covered by this segment. containsIntervalSegment180 bool containsInterval(SlotIndex S, SlotIndex E) const { 181 assert((S < E) && "Backwards interval?"); 182 return (start <= S && S < end) && (start < E && E <= end); 183 } 184 185 bool operator<(const Segment &Other) const { 186 return std::tie(start, end) < std::tie(Other.start, Other.end); 187 } 188 bool operator==(const Segment &Other) const { 189 return start == Other.start && end == Other.end; 190 } 191 192 bool operator!=(const Segment &Other) const { 193 return !(*this == Other); 194 } 195 196 void dump() const; 197 }; 198 199 using Segments = SmallVector<Segment, 2>; 200 using VNInfoList = SmallVector<VNInfo *, 2>; 201 202 Segments segments; // the liveness segments 203 VNInfoList valnos; // value#'s 204 205 // The segment set is used temporarily to accelerate initial computation 206 // of live ranges of physical registers in computeRegUnitRange. 207 // After that the set is flushed to the segment vector and deleted. 208 using SegmentSet = std::set<Segment>; 209 std::unique_ptr<SegmentSet> segmentSet; 210 211 using iterator = Segments::iterator; 212 using const_iterator = Segments::const_iterator; 213 begin()214 iterator begin() { return segments.begin(); } end()215 iterator end() { return segments.end(); } 216 begin()217 const_iterator begin() const { return segments.begin(); } end()218 const_iterator end() const { return segments.end(); } 219 220 using vni_iterator = VNInfoList::iterator; 221 using const_vni_iterator = VNInfoList::const_iterator; 222 vni_begin()223 vni_iterator vni_begin() { return valnos.begin(); } vni_end()224 vni_iterator vni_end() { return valnos.end(); } 225 vni_begin()226 const_vni_iterator vni_begin() const { return valnos.begin(); } vni_end()227 const_vni_iterator vni_end() const { return valnos.end(); } 228 229 /// Constructs a new LiveRange object. 230 LiveRange(bool UseSegmentSet = false) 231 : segmentSet(UseSegmentSet ? std::make_unique<SegmentSet>() 232 : nullptr) {} 233 234 /// Constructs a new LiveRange object by copying segments and valnos from 235 /// another LiveRange. LiveRange(const LiveRange & Other,BumpPtrAllocator & Allocator)236 LiveRange(const LiveRange &Other, BumpPtrAllocator &Allocator) { 237 assert(Other.segmentSet == nullptr && 238 "Copying of LiveRanges with active SegmentSets is not supported"); 239 assign(Other, Allocator); 240 } 241 242 /// Copies values numbers and live segments from \p Other into this range. assign(const LiveRange & Other,BumpPtrAllocator & Allocator)243 void assign(const LiveRange &Other, BumpPtrAllocator &Allocator) { 244 if (this == &Other) 245 return; 246 247 assert(Other.segmentSet == nullptr && 248 "Copying of LiveRanges with active SegmentSets is not supported"); 249 // Duplicate valnos. 250 for (const VNInfo *VNI : Other.valnos) 251 createValueCopy(VNI, Allocator); 252 // Now we can copy segments and remap their valnos. 253 for (const Segment &S : Other.segments) 254 segments.push_back(Segment(S.start, S.end, valnos[S.valno->id])); 255 } 256 257 /// advanceTo - Advance the specified iterator to point to the Segment 258 /// containing the specified position, or end() if the position is past the 259 /// end of the range. If no Segment contains this position, but the 260 /// position is in a hole, this method returns an iterator pointing to the 261 /// Segment immediately after the hole. advanceTo(iterator I,SlotIndex Pos)262 iterator advanceTo(iterator I, SlotIndex Pos) { 263 assert(I != end()); 264 if (Pos >= endIndex()) 265 return end(); 266 while (I->end <= Pos) ++I; 267 return I; 268 } 269 advanceTo(const_iterator I,SlotIndex Pos)270 const_iterator advanceTo(const_iterator I, SlotIndex Pos) const { 271 assert(I != end()); 272 if (Pos >= endIndex()) 273 return end(); 274 while (I->end <= Pos) ++I; 275 return I; 276 } 277 278 /// find - Return an iterator pointing to the first segment that ends after 279 /// Pos, or end(). This is the same as advanceTo(begin(), Pos), but faster 280 /// when searching large ranges. 281 /// 282 /// If Pos is contained in a Segment, that segment is returned. 283 /// If Pos is in a hole, the following Segment is returned. 284 /// If Pos is beyond endIndex, end() is returned. 285 iterator find(SlotIndex Pos); 286 find(SlotIndex Pos)287 const_iterator find(SlotIndex Pos) const { 288 return const_cast<LiveRange*>(this)->find(Pos); 289 } 290 clear()291 void clear() { 292 valnos.clear(); 293 segments.clear(); 294 } 295 size()296 size_t size() const { 297 return segments.size(); 298 } 299 hasAtLeastOneValue()300 bool hasAtLeastOneValue() const { return !valnos.empty(); } 301 containsOneValue()302 bool containsOneValue() const { return valnos.size() == 1; } 303 getNumValNums()304 unsigned getNumValNums() const { return (unsigned)valnos.size(); } 305 306 /// getValNumInfo - Returns pointer to the specified val#. 307 /// getValNumInfo(unsigned ValNo)308 inline VNInfo *getValNumInfo(unsigned ValNo) { 309 return valnos[ValNo]; 310 } getValNumInfo(unsigned ValNo)311 inline const VNInfo *getValNumInfo(unsigned ValNo) const { 312 return valnos[ValNo]; 313 } 314 315 /// containsValue - Returns true if VNI belongs to this range. containsValue(const VNInfo * VNI)316 bool containsValue(const VNInfo *VNI) const { 317 return VNI && VNI->id < getNumValNums() && VNI == getValNumInfo(VNI->id); 318 } 319 320 /// getNextValue - Create a new value number and return it. MIIdx specifies 321 /// the instruction that defines the value number. getNextValue(SlotIndex def,VNInfo::Allocator & VNInfoAllocator)322 VNInfo *getNextValue(SlotIndex def, VNInfo::Allocator &VNInfoAllocator) { 323 VNInfo *VNI = 324 new (VNInfoAllocator) VNInfo((unsigned)valnos.size(), def); 325 valnos.push_back(VNI); 326 return VNI; 327 } 328 329 /// createDeadDef - Make sure the range has a value defined at Def. 330 /// If one already exists, return it. Otherwise allocate a new value and 331 /// add liveness for a dead def. 332 VNInfo *createDeadDef(SlotIndex Def, VNInfo::Allocator &VNIAlloc); 333 334 /// Create a def of value @p VNI. Return @p VNI. If there already exists 335 /// a definition at VNI->def, the value defined there must be @p VNI. 336 VNInfo *createDeadDef(VNInfo *VNI); 337 338 /// Create a copy of the given value. The new value will be identical except 339 /// for the Value number. createValueCopy(const VNInfo * orig,VNInfo::Allocator & VNInfoAllocator)340 VNInfo *createValueCopy(const VNInfo *orig, 341 VNInfo::Allocator &VNInfoAllocator) { 342 VNInfo *VNI = 343 new (VNInfoAllocator) VNInfo((unsigned)valnos.size(), *orig); 344 valnos.push_back(VNI); 345 return VNI; 346 } 347 348 /// RenumberValues - Renumber all values in order of appearance and remove 349 /// unused values. 350 void RenumberValues(); 351 352 /// MergeValueNumberInto - This method is called when two value numbers 353 /// are found to be equivalent. This eliminates V1, replacing all 354 /// segments with the V1 value number with the V2 value number. This can 355 /// cause merging of V1/V2 values numbers and compaction of the value space. 356 VNInfo* MergeValueNumberInto(VNInfo *V1, VNInfo *V2); 357 358 /// Merge all of the live segments of a specific val# in RHS into this live 359 /// range as the specified value number. The segments in RHS are allowed 360 /// to overlap with segments in the current range, it will replace the 361 /// value numbers of the overlaped live segments with the specified value 362 /// number. 363 void MergeSegmentsInAsValue(const LiveRange &RHS, VNInfo *LHSValNo); 364 365 /// MergeValueInAsValue - Merge all of the segments of a specific val# 366 /// in RHS into this live range as the specified value number. 367 /// The segments in RHS are allowed to overlap with segments in the 368 /// current range, but only if the overlapping segments have the 369 /// specified value number. 370 void MergeValueInAsValue(const LiveRange &RHS, 371 const VNInfo *RHSValNo, VNInfo *LHSValNo); 372 empty()373 bool empty() const { return segments.empty(); } 374 375 /// beginIndex - Return the lowest numbered slot covered. beginIndex()376 SlotIndex beginIndex() const { 377 assert(!empty() && "Call to beginIndex() on empty range."); 378 return segments.front().start; 379 } 380 381 /// endNumber - return the maximum point of the range of the whole, 382 /// exclusive. endIndex()383 SlotIndex endIndex() const { 384 assert(!empty() && "Call to endIndex() on empty range."); 385 return segments.back().end; 386 } 387 expiredAt(SlotIndex index)388 bool expiredAt(SlotIndex index) const { 389 return index >= endIndex(); 390 } 391 liveAt(SlotIndex index)392 bool liveAt(SlotIndex index) const { 393 const_iterator r = find(index); 394 return r != end() && r->start <= index; 395 } 396 397 /// Return the segment that contains the specified index, or null if there 398 /// is none. getSegmentContaining(SlotIndex Idx)399 const Segment *getSegmentContaining(SlotIndex Idx) const { 400 const_iterator I = FindSegmentContaining(Idx); 401 return I == end() ? nullptr : &*I; 402 } 403 404 /// Return the live segment that contains the specified index, or null if 405 /// there is none. getSegmentContaining(SlotIndex Idx)406 Segment *getSegmentContaining(SlotIndex Idx) { 407 iterator I = FindSegmentContaining(Idx); 408 return I == end() ? nullptr : &*I; 409 } 410 411 /// getVNInfoAt - Return the VNInfo that is live at Idx, or NULL. getVNInfoAt(SlotIndex Idx)412 VNInfo *getVNInfoAt(SlotIndex Idx) const { 413 const_iterator I = FindSegmentContaining(Idx); 414 return I == end() ? nullptr : I->valno; 415 } 416 417 /// getVNInfoBefore - Return the VNInfo that is live up to but not 418 /// necessarilly including Idx, or NULL. Use this to find the reaching def 419 /// used by an instruction at this SlotIndex position. getVNInfoBefore(SlotIndex Idx)420 VNInfo *getVNInfoBefore(SlotIndex Idx) const { 421 const_iterator I = FindSegmentContaining(Idx.getPrevSlot()); 422 return I == end() ? nullptr : I->valno; 423 } 424 425 /// Return an iterator to the segment that contains the specified index, or 426 /// end() if there is none. FindSegmentContaining(SlotIndex Idx)427 iterator FindSegmentContaining(SlotIndex Idx) { 428 iterator I = find(Idx); 429 return I != end() && I->start <= Idx ? I : end(); 430 } 431 FindSegmentContaining(SlotIndex Idx)432 const_iterator FindSegmentContaining(SlotIndex Idx) const { 433 const_iterator I = find(Idx); 434 return I != end() && I->start <= Idx ? I : end(); 435 } 436 437 /// overlaps - Return true if the intersection of the two live ranges is 438 /// not empty. overlaps(const LiveRange & other)439 bool overlaps(const LiveRange &other) const { 440 if (other.empty()) 441 return false; 442 return overlapsFrom(other, other.begin()); 443 } 444 445 /// overlaps - Return true if the two ranges have overlapping segments 446 /// that are not coalescable according to CP. 447 /// 448 /// Overlapping segments where one range is defined by a coalescable 449 /// copy are allowed. 450 bool overlaps(const LiveRange &Other, const CoalescerPair &CP, 451 const SlotIndexes&) const; 452 453 /// overlaps - Return true if the live range overlaps an interval specified 454 /// by [Start, End). 455 bool overlaps(SlotIndex Start, SlotIndex End) const; 456 457 /// overlapsFrom - Return true if the intersection of the two live ranges 458 /// is not empty. The specified iterator is a hint that we can begin 459 /// scanning the Other range starting at I. 460 bool overlapsFrom(const LiveRange &Other, const_iterator StartPos) const; 461 462 /// Returns true if all segments of the @p Other live range are completely 463 /// covered by this live range. 464 /// Adjacent live ranges do not affect the covering:the liverange 465 /// [1,5](5,10] covers (3,7]. 466 bool covers(const LiveRange &Other) const; 467 468 /// Add the specified Segment to this range, merging segments as 469 /// appropriate. This returns an iterator to the inserted segment (which 470 /// may have grown since it was inserted). 471 iterator addSegment(Segment S); 472 473 /// Attempt to extend a value defined after @p StartIdx to include @p Use. 474 /// Both @p StartIdx and @p Use should be in the same basic block. In case 475 /// of subranges, an extension could be prevented by an explicit "undef" 476 /// caused by a <def,read-undef> on a non-overlapping lane. The list of 477 /// location of such "undefs" should be provided in @p Undefs. 478 /// The return value is a pair: the first element is VNInfo of the value 479 /// that was extended (possibly nullptr), the second is a boolean value 480 /// indicating whether an "undef" was encountered. 481 /// If this range is live before @p Use in the basic block that starts at 482 /// @p StartIdx, and there is no intervening "undef", extend it to be live 483 /// up to @p Use, and return the pair {value, false}. If there is no 484 /// segment before @p Use and there is no "undef" between @p StartIdx and 485 /// @p Use, return {nullptr, false}. If there is an "undef" before @p Use, 486 /// return {nullptr, true}. 487 std::pair<VNInfo*,bool> extendInBlock(ArrayRef<SlotIndex> Undefs, 488 SlotIndex StartIdx, SlotIndex Kill); 489 490 /// Simplified version of the above "extendInBlock", which assumes that 491 /// no register lanes are undefined by <def,read-undef> operands. 492 /// If this range is live before @p Use in the basic block that starts 493 /// at @p StartIdx, extend it to be live up to @p Use, and return the 494 /// value. If there is no segment before @p Use, return nullptr. 495 VNInfo *extendInBlock(SlotIndex StartIdx, SlotIndex Kill); 496 497 /// join - Join two live ranges (this, and other) together. This applies 498 /// mappings to the value numbers in the LHS/RHS ranges as specified. If 499 /// the ranges are not joinable, this aborts. 500 void join(LiveRange &Other, 501 const int *ValNoAssignments, 502 const int *RHSValNoAssignments, 503 SmallVectorImpl<VNInfo *> &NewVNInfo); 504 505 /// True iff this segment is a single segment that lies between the 506 /// specified boundaries, exclusively. Vregs live across a backedge are not 507 /// considered local. The boundaries are expected to lie within an extended 508 /// basic block, so vregs that are not live out should contain no holes. isLocal(SlotIndex Start,SlotIndex End)509 bool isLocal(SlotIndex Start, SlotIndex End) const { 510 return beginIndex() > Start.getBaseIndex() && 511 endIndex() < End.getBoundaryIndex(); 512 } 513 514 /// Remove the specified segment from this range. Note that the segment 515 /// must be a single Segment in its entirety. 516 void removeSegment(SlotIndex Start, SlotIndex End, 517 bool RemoveDeadValNo = false); 518 519 void removeSegment(Segment S, bool RemoveDeadValNo = false) { 520 removeSegment(S.start, S.end, RemoveDeadValNo); 521 } 522 523 /// Remove segment pointed to by iterator @p I from this range. This does 524 /// not remove dead value numbers. removeSegment(iterator I)525 iterator removeSegment(iterator I) { 526 return segments.erase(I); 527 } 528 529 /// Query Liveness at Idx. 530 /// The sub-instruction slot of Idx doesn't matter, only the instruction 531 /// it refers to is considered. Query(SlotIndex Idx)532 LiveQueryResult Query(SlotIndex Idx) const { 533 // Find the segment that enters the instruction. 534 const_iterator I = find(Idx.getBaseIndex()); 535 const_iterator E = end(); 536 if (I == E) 537 return LiveQueryResult(nullptr, nullptr, SlotIndex(), false); 538 539 // Is this an instruction live-in segment? 540 // If Idx is the start index of a basic block, include live-in segments 541 // that start at Idx.getBaseIndex(). 542 VNInfo *EarlyVal = nullptr; 543 VNInfo *LateVal = nullptr; 544 SlotIndex EndPoint; 545 bool Kill = false; 546 if (I->start <= Idx.getBaseIndex()) { 547 EarlyVal = I->valno; 548 EndPoint = I->end; 549 // Move to the potentially live-out segment. 550 if (SlotIndex::isSameInstr(Idx, I->end)) { 551 Kill = true; 552 if (++I == E) 553 return LiveQueryResult(EarlyVal, LateVal, EndPoint, Kill); 554 } 555 // Special case: A PHIDef value can have its def in the middle of a 556 // segment if the value happens to be live out of the layout 557 // predecessor. 558 // Such a value is not live-in. 559 if (EarlyVal->def == Idx.getBaseIndex()) 560 EarlyVal = nullptr; 561 } 562 // I now points to the segment that may be live-through, or defined by 563 // this instr. Ignore segments starting after the current instr. 564 if (!SlotIndex::isEarlierInstr(Idx, I->start)) { 565 LateVal = I->valno; 566 EndPoint = I->end; 567 } 568 return LiveQueryResult(EarlyVal, LateVal, EndPoint, Kill); 569 } 570 571 /// removeValNo - Remove all the segments defined by the specified value#. 572 /// Also remove the value# from value# list. 573 void removeValNo(VNInfo *ValNo); 574 575 /// Returns true if the live range is zero length, i.e. no live segments 576 /// span instructions. It doesn't pay to spill such a range. isZeroLength(SlotIndexes * Indexes)577 bool isZeroLength(SlotIndexes *Indexes) const { 578 for (const Segment &S : segments) 579 if (Indexes->getNextNonNullIndex(S.start).getBaseIndex() < 580 S.end.getBaseIndex()) 581 return false; 582 return true; 583 } 584 585 // Returns true if any segment in the live range contains any of the 586 // provided slot indexes. Slots which occur in holes between 587 // segments will not cause the function to return true. 588 bool isLiveAtIndexes(ArrayRef<SlotIndex> Slots) const; 589 590 bool operator<(const LiveRange& other) const { 591 const SlotIndex &thisIndex = beginIndex(); 592 const SlotIndex &otherIndex = other.beginIndex(); 593 return thisIndex < otherIndex; 594 } 595 596 /// Returns true if there is an explicit "undef" between @p Begin 597 /// @p End. isUndefIn(ArrayRef<SlotIndex> Undefs,SlotIndex Begin,SlotIndex End)598 bool isUndefIn(ArrayRef<SlotIndex> Undefs, SlotIndex Begin, 599 SlotIndex End) const { 600 return std::any_of(Undefs.begin(), Undefs.end(), 601 [Begin,End] (SlotIndex Idx) -> bool { 602 return Begin <= Idx && Idx < End; 603 }); 604 } 605 606 /// Flush segment set into the regular segment vector. 607 /// The method is to be called after the live range 608 /// has been created, if use of the segment set was 609 /// activated in the constructor of the live range. 610 void flushSegmentSet(); 611 612 /// Stores indexes from the input index sequence R at which this LiveRange 613 /// is live to the output O iterator. 614 /// R is a range of _ascending sorted_ _random_ access iterators 615 /// to the input indexes. Indexes stored at O are ascending sorted so it 616 /// can be used directly in the subsequent search (for example for 617 /// subranges). Returns true if found at least one index. 618 template <typename Range, typename OutputIt> findIndexesLiveAt(Range && R,OutputIt O)619 bool findIndexesLiveAt(Range &&R, OutputIt O) const { 620 assert(llvm::is_sorted(R)); 621 auto Idx = R.begin(), EndIdx = R.end(); 622 auto Seg = segments.begin(), EndSeg = segments.end(); 623 bool Found = false; 624 while (Idx != EndIdx && Seg != EndSeg) { 625 // if the Seg is lower find first segment that is above Idx using binary 626 // search 627 if (Seg->end <= *Idx) { 628 Seg = std::upper_bound( 629 ++Seg, EndSeg, *Idx, 630 [=](std::remove_reference_t<decltype(*Idx)> V, 631 const std::remove_reference_t<decltype(*Seg)> &S) { 632 return V < S.end; 633 }); 634 if (Seg == EndSeg) 635 break; 636 } 637 auto NotLessStart = std::lower_bound(Idx, EndIdx, Seg->start); 638 if (NotLessStart == EndIdx) 639 break; 640 auto NotLessEnd = std::lower_bound(NotLessStart, EndIdx, Seg->end); 641 if (NotLessEnd != NotLessStart) { 642 Found = true; 643 O = std::copy(NotLessStart, NotLessEnd, O); 644 } 645 Idx = NotLessEnd; 646 ++Seg; 647 } 648 return Found; 649 } 650 651 void print(raw_ostream &OS) const; 652 void dump() const; 653 654 /// Walk the range and assert if any invariants fail to hold. 655 /// 656 /// Note that this is a no-op when asserts are disabled. 657 #ifdef NDEBUG verify()658 void verify() const {} 659 #else 660 void verify() const; 661 #endif 662 663 protected: 664 /// Append a segment to the list of segments. 665 void append(const LiveRange::Segment S); 666 667 private: 668 friend class LiveRangeUpdater; 669 void addSegmentToSet(Segment S); 670 void markValNoForDeletion(VNInfo *V); 671 }; 672 673 inline raw_ostream &operator<<(raw_ostream &OS, const LiveRange &LR) { 674 LR.print(OS); 675 return OS; 676 } 677 678 /// LiveInterval - This class represents the liveness of a register, 679 /// or stack slot. 680 class LiveInterval : public LiveRange { 681 public: 682 using super = LiveRange; 683 684 /// A live range for subregisters. The LaneMask specifies which parts of the 685 /// super register are covered by the interval. 686 /// (@sa TargetRegisterInfo::getSubRegIndexLaneMask()). 687 class SubRange : public LiveRange { 688 public: 689 SubRange *Next = nullptr; 690 LaneBitmask LaneMask; 691 692 /// Constructs a new SubRange object. SubRange(LaneBitmask LaneMask)693 SubRange(LaneBitmask LaneMask) : LaneMask(LaneMask) {} 694 695 /// Constructs a new SubRange object by copying liveness from @p Other. SubRange(LaneBitmask LaneMask,const LiveRange & Other,BumpPtrAllocator & Allocator)696 SubRange(LaneBitmask LaneMask, const LiveRange &Other, 697 BumpPtrAllocator &Allocator) 698 : LiveRange(Other, Allocator), LaneMask(LaneMask) {} 699 700 void print(raw_ostream &OS) const; 701 void dump() const; 702 }; 703 704 private: 705 SubRange *SubRanges = nullptr; ///< Single linked list of subregister live 706 /// ranges. 707 708 public: 709 const unsigned reg; // the register or stack slot of this interval. 710 float weight; // weight of this interval 711 LiveInterval(unsigned Reg,float Weight)712 LiveInterval(unsigned Reg, float Weight) : reg(Reg), weight(Weight) {} 713 ~LiveInterval()714 ~LiveInterval() { 715 clearSubRanges(); 716 } 717 718 template<typename T> 719 class SingleLinkedListIterator { 720 T *P; 721 722 public: P(P)723 SingleLinkedListIterator<T>(T *P) : P(P) {} 724 725 SingleLinkedListIterator<T> &operator++() { 726 P = P->Next; 727 return *this; 728 } 729 SingleLinkedListIterator<T> operator++(int) { 730 SingleLinkedListIterator res = *this; 731 ++*this; 732 return res; 733 } 734 bool operator!=(const SingleLinkedListIterator<T> &Other) { 735 return P != Other.operator->(); 736 } 737 bool operator==(const SingleLinkedListIterator<T> &Other) { 738 return P == Other.operator->(); 739 } 740 T &operator*() const { 741 return *P; 742 } 743 T *operator->() const { 744 return P; 745 } 746 }; 747 748 using subrange_iterator = SingleLinkedListIterator<SubRange>; 749 using const_subrange_iterator = SingleLinkedListIterator<const SubRange>; 750 subrange_begin()751 subrange_iterator subrange_begin() { 752 return subrange_iterator(SubRanges); 753 } subrange_end()754 subrange_iterator subrange_end() { 755 return subrange_iterator(nullptr); 756 } 757 subrange_begin()758 const_subrange_iterator subrange_begin() const { 759 return const_subrange_iterator(SubRanges); 760 } subrange_end()761 const_subrange_iterator subrange_end() const { 762 return const_subrange_iterator(nullptr); 763 } 764 subranges()765 iterator_range<subrange_iterator> subranges() { 766 return make_range(subrange_begin(), subrange_end()); 767 } 768 subranges()769 iterator_range<const_subrange_iterator> subranges() const { 770 return make_range(subrange_begin(), subrange_end()); 771 } 772 773 /// Creates a new empty subregister live range. The range is added at the 774 /// beginning of the subrange list; subrange iterators stay valid. createSubRange(BumpPtrAllocator & Allocator,LaneBitmask LaneMask)775 SubRange *createSubRange(BumpPtrAllocator &Allocator, 776 LaneBitmask LaneMask) { 777 SubRange *Range = new (Allocator) SubRange(LaneMask); 778 appendSubRange(Range); 779 return Range; 780 } 781 782 /// Like createSubRange() but the new range is filled with a copy of the 783 /// liveness information in @p CopyFrom. createSubRangeFrom(BumpPtrAllocator & Allocator,LaneBitmask LaneMask,const LiveRange & CopyFrom)784 SubRange *createSubRangeFrom(BumpPtrAllocator &Allocator, 785 LaneBitmask LaneMask, 786 const LiveRange &CopyFrom) { 787 SubRange *Range = new (Allocator) SubRange(LaneMask, CopyFrom, Allocator); 788 appendSubRange(Range); 789 return Range; 790 } 791 792 /// Returns true if subregister liveness information is available. hasSubRanges()793 bool hasSubRanges() const { 794 return SubRanges != nullptr; 795 } 796 797 /// Removes all subregister liveness information. 798 void clearSubRanges(); 799 800 /// Removes all subranges without any segments (subranges without segments 801 /// are not considered valid and should only exist temporarily). 802 void removeEmptySubRanges(); 803 804 /// getSize - Returns the sum of sizes of all the LiveRange's. 805 /// 806 unsigned getSize() const; 807 808 /// isSpillable - Can this interval be spilled? isSpillable()809 bool isSpillable() const { 810 return weight != huge_valf; 811 } 812 813 /// markNotSpillable - Mark interval as not spillable markNotSpillable()814 void markNotSpillable() { 815 weight = huge_valf; 816 } 817 818 /// For a given lane mask @p LaneMask, compute indexes at which the 819 /// lane is marked undefined by subregister <def,read-undef> definitions. 820 void computeSubRangeUndefs(SmallVectorImpl<SlotIndex> &Undefs, 821 LaneBitmask LaneMask, 822 const MachineRegisterInfo &MRI, 823 const SlotIndexes &Indexes) const; 824 825 /// Refines the subranges to support \p LaneMask. This may only be called 826 /// for LI.hasSubrange()==true. Subregister ranges are split or created 827 /// until \p LaneMask can be matched exactly. \p Mod is executed on the 828 /// matching subranges. 829 /// 830 /// Example: 831 /// Given an interval with subranges with lanemasks L0F00, L00F0 and 832 /// L000F, refining for mask L0018. Will split the L00F0 lane into 833 /// L00E0 and L0010 and the L000F lane into L0007 and L0008. The Mod 834 /// function will be applied to the L0010 and L0008 subranges. 835 /// 836 /// \p Indexes and \p TRI are required to clean up the VNIs that 837 /// don't defne the related lane masks after they get shrunk. E.g., 838 /// when L000F gets split into L0007 and L0008 maybe only a subset 839 /// of the VNIs that defined L000F defines L0007. 840 /// 841 /// The clean up of the VNIs need to look at the actual instructions 842 /// to decide what is or is not live at a definition point. If the 843 /// update of the subranges occurs while the IR does not reflect these 844 /// changes, \p ComposeSubRegIdx can be used to specify how the 845 /// definition are going to be rewritten. 846 /// E.g., let say we want to merge: 847 /// V1.sub1:<2 x s32> = COPY V2.sub3:<4 x s32> 848 /// We do that by choosing a class where sub1:<2 x s32> and sub3:<4 x s32> 849 /// overlap, i.e., by choosing a class where we can find "offset + 1 == 3". 850 /// Put differently we align V2's sub3 with V1's sub1: 851 /// V2: sub0 sub1 sub2 sub3 852 /// V1: <offset> sub0 sub1 853 /// 854 /// This offset will look like a composed subregidx in the the class: 855 /// V1.(composed sub2 with sub1):<4 x s32> = COPY V2.sub3:<4 x s32> 856 /// => V1.(composed sub2 with sub1):<4 x s32> = COPY V2.sub3:<4 x s32> 857 /// 858 /// Now if we didn't rewrite the uses and def of V1, all the checks for V1 859 /// need to account for this offset. 860 /// This happens during coalescing where we update the live-ranges while 861 /// still having the old IR around because updating the IR on-the-fly 862 /// would actually clobber some information on how the live-ranges that 863 /// are being updated look like. 864 void refineSubRanges(BumpPtrAllocator &Allocator, LaneBitmask LaneMask, 865 std::function<void(LiveInterval::SubRange &)> Apply, 866 const SlotIndexes &Indexes, 867 const TargetRegisterInfo &TRI, 868 unsigned ComposeSubRegIdx = 0); 869 870 bool operator<(const LiveInterval& other) const { 871 const SlotIndex &thisIndex = beginIndex(); 872 const SlotIndex &otherIndex = other.beginIndex(); 873 return std::tie(thisIndex, reg) < std::tie(otherIndex, other.reg); 874 } 875 876 void print(raw_ostream &OS) const; 877 void dump() const; 878 879 /// Walks the interval and assert if any invariants fail to hold. 880 /// 881 /// Note that this is a no-op when asserts are disabled. 882 #ifdef NDEBUG 883 void verify(const MachineRegisterInfo *MRI = nullptr) const {} 884 #else 885 void verify(const MachineRegisterInfo *MRI = nullptr) const; 886 #endif 887 888 private: 889 /// Appends @p Range to SubRanges list. appendSubRange(SubRange * Range)890 void appendSubRange(SubRange *Range) { 891 Range->Next = SubRanges; 892 SubRanges = Range; 893 } 894 895 /// Free memory held by SubRange. 896 void freeSubRange(SubRange *S); 897 }; 898 899 inline raw_ostream &operator<<(raw_ostream &OS, 900 const LiveInterval::SubRange &SR) { 901 SR.print(OS); 902 return OS; 903 } 904 905 inline raw_ostream &operator<<(raw_ostream &OS, const LiveInterval &LI) { 906 LI.print(OS); 907 return OS; 908 } 909 910 raw_ostream &operator<<(raw_ostream &OS, const LiveRange::Segment &S); 911 912 inline bool operator<(SlotIndex V, const LiveRange::Segment &S) { 913 return V < S.start; 914 } 915 916 inline bool operator<(const LiveRange::Segment &S, SlotIndex V) { 917 return S.start < V; 918 } 919 920 /// Helper class for performant LiveRange bulk updates. 921 /// 922 /// Calling LiveRange::addSegment() repeatedly can be expensive on large 923 /// live ranges because segments after the insertion point may need to be 924 /// shifted. The LiveRangeUpdater class can defer the shifting when adding 925 /// many segments in order. 926 /// 927 /// The LiveRange will be in an invalid state until flush() is called. 928 class LiveRangeUpdater { 929 LiveRange *LR; 930 SlotIndex LastStart; 931 LiveRange::iterator WriteI; 932 LiveRange::iterator ReadI; 933 SmallVector<LiveRange::Segment, 16> Spills; 934 void mergeSpills(); 935 936 public: 937 /// Create a LiveRangeUpdater for adding segments to LR. 938 /// LR will temporarily be in an invalid state until flush() is called. LR(lr)939 LiveRangeUpdater(LiveRange *lr = nullptr) : LR(lr) {} 940 ~LiveRangeUpdater()941 ~LiveRangeUpdater() { flush(); } 942 943 /// Add a segment to LR and coalesce when possible, just like 944 /// LR.addSegment(). Segments should be added in increasing start order for 945 /// best performance. 946 void add(LiveRange::Segment); 947 add(SlotIndex Start,SlotIndex End,VNInfo * VNI)948 void add(SlotIndex Start, SlotIndex End, VNInfo *VNI) { 949 add(LiveRange::Segment(Start, End, VNI)); 950 } 951 952 /// Return true if the LR is currently in an invalid state, and flush() 953 /// needs to be called. isDirty()954 bool isDirty() const { return LastStart.isValid(); } 955 956 /// Flush the updater state to LR so it is valid and contains all added 957 /// segments. 958 void flush(); 959 960 /// Select a different destination live range. setDest(LiveRange * lr)961 void setDest(LiveRange *lr) { 962 if (LR != lr && isDirty()) 963 flush(); 964 LR = lr; 965 } 966 967 /// Get the current destination live range. getDest()968 LiveRange *getDest() const { return LR; } 969 970 void dump() const; 971 void print(raw_ostream&) const; 972 }; 973 974 inline raw_ostream &operator<<(raw_ostream &OS, const LiveRangeUpdater &X) { 975 X.print(OS); 976 return OS; 977 } 978 979 /// ConnectedVNInfoEqClasses - Helper class that can divide VNInfos in a 980 /// LiveInterval into equivalence clases of connected components. A 981 /// LiveInterval that has multiple connected components can be broken into 982 /// multiple LiveIntervals. 983 /// 984 /// Given a LiveInterval that may have multiple connected components, run: 985 /// 986 /// unsigned numComps = ConEQ.Classify(LI); 987 /// if (numComps > 1) { 988 /// // allocate numComps-1 new LiveIntervals into LIS[1..] 989 /// ConEQ.Distribute(LIS); 990 /// } 991 992 class ConnectedVNInfoEqClasses { 993 LiveIntervals &LIS; 994 IntEqClasses EqClass; 995 996 public: ConnectedVNInfoEqClasses(LiveIntervals & lis)997 explicit ConnectedVNInfoEqClasses(LiveIntervals &lis) : LIS(lis) {} 998 999 /// Classify the values in \p LR into connected components. 1000 /// Returns the number of connected components. 1001 unsigned Classify(const LiveRange &LR); 1002 1003 /// getEqClass - Classify creates equivalence classes numbered 0..N. Return 1004 /// the equivalence class assigned the VNI. getEqClass(const VNInfo * VNI)1005 unsigned getEqClass(const VNInfo *VNI) const { return EqClass[VNI->id]; } 1006 1007 /// Distribute values in \p LI into a separate LiveIntervals 1008 /// for each connected component. LIV must have an empty LiveInterval for 1009 /// each additional connected component. The first connected component is 1010 /// left in \p LI. 1011 void Distribute(LiveInterval &LI, LiveInterval *LIV[], 1012 MachineRegisterInfo &MRI); 1013 }; 1014 1015 } // end namespace llvm 1016 1017 #endif // LLVM_CODEGEN_LIVEINTERVAL_H 1018