1 //===- LiveInterval.cpp - Live Interval Representation --------------------===// 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 #include "llvm/CodeGen/LiveInterval.h" 21 #include "LiveRangeUtils.h" 22 #include "RegisterCoalescer.h" 23 #include "llvm/ADT/ArrayRef.h" 24 #include "llvm/ADT/STLExtras.h" 25 #include "llvm/ADT/SmallPtrSet.h" 26 #include "llvm/ADT/SmallVector.h" 27 #include "llvm/ADT/iterator_range.h" 28 #include "llvm/CodeGen/LiveIntervals.h" 29 #include "llvm/CodeGen/MachineBasicBlock.h" 30 #include "llvm/CodeGen/MachineInstr.h" 31 #include "llvm/CodeGen/MachineOperand.h" 32 #include "llvm/CodeGen/MachineRegisterInfo.h" 33 #include "llvm/CodeGen/SlotIndexes.h" 34 #include "llvm/CodeGen/TargetRegisterInfo.h" 35 #include "llvm/Config/llvm-config.h" 36 #include "llvm/MC/LaneBitmask.h" 37 #include "llvm/Support/Compiler.h" 38 #include "llvm/Support/Debug.h" 39 #include "llvm/Support/raw_ostream.h" 40 #include <algorithm> 41 #include <cassert> 42 #include <cstddef> 43 #include <iterator> 44 #include <utility> 45 46 using namespace llvm; 47 48 namespace { 49 50 //===----------------------------------------------------------------------===// 51 // Implementation of various methods necessary for calculation of live ranges. 52 // The implementation of the methods abstracts from the concrete type of the 53 // segment collection. 54 // 55 // Implementation of the class follows the Template design pattern. The base 56 // class contains generic algorithms that call collection-specific methods, 57 // which are provided in concrete subclasses. In order to avoid virtual calls 58 // these methods are provided by means of C++ template instantiation. 59 // The base class calls the methods of the subclass through method impl(), 60 // which casts 'this' pointer to the type of the subclass. 61 // 62 //===----------------------------------------------------------------------===// 63 64 template <typename ImplT, typename IteratorT, typename CollectionT> 65 class CalcLiveRangeUtilBase { 66 protected: 67 LiveRange *LR; 68 69 protected: 70 CalcLiveRangeUtilBase(LiveRange *LR) : LR(LR) {} 71 72 public: 73 using Segment = LiveRange::Segment; 74 using iterator = IteratorT; 75 76 /// A counterpart of LiveRange::createDeadDef: Make sure the range has a 77 /// value defined at @p Def. 78 /// If @p ForVNI is null, and there is no value defined at @p Def, a new 79 /// value will be allocated using @p VNInfoAllocator. 80 /// If @p ForVNI is null, the return value is the value defined at @p Def, 81 /// either a pre-existing one, or the one newly created. 82 /// If @p ForVNI is not null, then @p Def should be the location where 83 /// @p ForVNI is defined. If the range does not have a value defined at 84 /// @p Def, the value @p ForVNI will be used instead of allocating a new 85 /// one. If the range already has a value defined at @p Def, it must be 86 /// same as @p ForVNI. In either case, @p ForVNI will be the return value. 87 VNInfo *createDeadDef(SlotIndex Def, VNInfo::Allocator *VNInfoAllocator, 88 VNInfo *ForVNI) { 89 assert(!Def.isDead() && "Cannot define a value at the dead slot"); 90 assert((!ForVNI || ForVNI->def == Def) && 91 "If ForVNI is specified, it must match Def"); 92 iterator I = impl().find(Def); 93 if (I == segments().end()) { 94 VNInfo *VNI = ForVNI ? ForVNI : LR->getNextValue(Def, *VNInfoAllocator); 95 impl().insertAtEnd(Segment(Def, Def.getDeadSlot(), VNI)); 96 return VNI; 97 } 98 99 Segment *S = segmentAt(I); 100 if (SlotIndex::isSameInstr(Def, S->start)) { 101 assert((!ForVNI || ForVNI == S->valno) && "Value number mismatch"); 102 assert(S->valno->def == S->start && "Inconsistent existing value def"); 103 104 // It is possible to have both normal and early-clobber defs of the same 105 // register on an instruction. It doesn't make a lot of sense, but it is 106 // possible to specify in inline assembly. 107 // 108 // Just convert everything to early-clobber. 109 Def = std::min(Def, S->start); 110 if (Def != S->start) 111 S->start = S->valno->def = Def; 112 return S->valno; 113 } 114 assert(SlotIndex::isEarlierInstr(Def, S->start) && "Already live at def"); 115 VNInfo *VNI = ForVNI ? ForVNI : LR->getNextValue(Def, *VNInfoAllocator); 116 segments().insert(I, Segment(Def, Def.getDeadSlot(), VNI)); 117 return VNI; 118 } 119 120 VNInfo *extendInBlock(SlotIndex StartIdx, SlotIndex Use) { 121 if (segments().empty()) 122 return nullptr; 123 iterator I = 124 impl().findInsertPos(Segment(Use.getPrevSlot(), Use, nullptr)); 125 if (I == segments().begin()) 126 return nullptr; 127 --I; 128 if (I->end <= StartIdx) 129 return nullptr; 130 if (I->end < Use) 131 extendSegmentEndTo(I, Use); 132 return I->valno; 133 } 134 135 std::pair<VNInfo*,bool> extendInBlock(ArrayRef<SlotIndex> Undefs, 136 SlotIndex StartIdx, SlotIndex Use) { 137 if (segments().empty()) 138 return std::make_pair(nullptr, false); 139 SlotIndex BeforeUse = Use.getPrevSlot(); 140 iterator I = impl().findInsertPos(Segment(BeforeUse, Use, nullptr)); 141 if (I == segments().begin()) 142 return std::make_pair(nullptr, LR->isUndefIn(Undefs, StartIdx, BeforeUse)); 143 --I; 144 if (I->end <= StartIdx) 145 return std::make_pair(nullptr, LR->isUndefIn(Undefs, StartIdx, BeforeUse)); 146 if (I->end < Use) { 147 if (LR->isUndefIn(Undefs, I->end, BeforeUse)) 148 return std::make_pair(nullptr, true); 149 extendSegmentEndTo(I, Use); 150 } 151 return std::make_pair(I->valno, false); 152 } 153 154 /// This method is used when we want to extend the segment specified 155 /// by I to end at the specified endpoint. To do this, we should 156 /// merge and eliminate all segments that this will overlap 157 /// with. The iterator is not invalidated. 158 void extendSegmentEndTo(iterator I, SlotIndex NewEnd) { 159 assert(I != segments().end() && "Not a valid segment!"); 160 Segment *S = segmentAt(I); 161 VNInfo *ValNo = I->valno; 162 163 // Search for the first segment that we can't merge with. 164 iterator MergeTo = std::next(I); 165 for (; MergeTo != segments().end() && NewEnd >= MergeTo->end; ++MergeTo) 166 assert(MergeTo->valno == ValNo && "Cannot merge with differing values!"); 167 168 // If NewEnd was in the middle of a segment, make sure to get its endpoint. 169 S->end = std::max(NewEnd, std::prev(MergeTo)->end); 170 171 // If the newly formed segment now touches the segment after it and if they 172 // have the same value number, merge the two segments into one segment. 173 if (MergeTo != segments().end() && MergeTo->start <= I->end && 174 MergeTo->valno == ValNo) { 175 S->end = MergeTo->end; 176 ++MergeTo; 177 } 178 179 // Erase any dead segments. 180 segments().erase(std::next(I), MergeTo); 181 } 182 183 /// This method is used when we want to extend the segment specified 184 /// by I to start at the specified endpoint. To do this, we should 185 /// merge and eliminate all segments that this will overlap with. 186 iterator extendSegmentStartTo(iterator I, SlotIndex NewStart) { 187 assert(I != segments().end() && "Not a valid segment!"); 188 Segment *S = segmentAt(I); 189 VNInfo *ValNo = I->valno; 190 191 // Search for the first segment that we can't merge with. 192 iterator MergeTo = I; 193 do { 194 if (MergeTo == segments().begin()) { 195 S->start = NewStart; 196 segments().erase(MergeTo, I); 197 return I; 198 } 199 assert(MergeTo->valno == ValNo && "Cannot merge with differing values!"); 200 --MergeTo; 201 } while (NewStart <= MergeTo->start); 202 203 // If we start in the middle of another segment, just delete a range and 204 // extend that segment. 205 if (MergeTo->end >= NewStart && MergeTo->valno == ValNo) { 206 segmentAt(MergeTo)->end = S->end; 207 } else { 208 // Otherwise, extend the segment right after. 209 ++MergeTo; 210 Segment *MergeToSeg = segmentAt(MergeTo); 211 MergeToSeg->start = NewStart; 212 MergeToSeg->end = S->end; 213 } 214 215 segments().erase(std::next(MergeTo), std::next(I)); 216 return MergeTo; 217 } 218 219 iterator addSegment(Segment S) { 220 SlotIndex Start = S.start, End = S.end; 221 iterator I = impl().findInsertPos(S); 222 223 // If the inserted segment starts in the middle or right at the end of 224 // another segment, just extend that segment to contain the segment of S. 225 if (I != segments().begin()) { 226 iterator B = std::prev(I); 227 if (S.valno == B->valno) { 228 if (B->start <= Start && B->end >= Start) { 229 extendSegmentEndTo(B, End); 230 return B; 231 } 232 } else { 233 // Check to make sure that we are not overlapping two live segments with 234 // different valno's. 235 assert(B->end <= Start && 236 "Cannot overlap two segments with differing ValID's" 237 " (did you def the same reg twice in a MachineInstr?)"); 238 } 239 } 240 241 // Otherwise, if this segment ends in the middle of, or right next 242 // to, another segment, merge it into that segment. 243 if (I != segments().end()) { 244 if (S.valno == I->valno) { 245 if (I->start <= End) { 246 I = extendSegmentStartTo(I, Start); 247 248 // If S is a complete superset of a segment, we may need to grow its 249 // endpoint as well. 250 if (End > I->end) 251 extendSegmentEndTo(I, End); 252 return I; 253 } 254 } else { 255 // Check to make sure that we are not overlapping two live segments with 256 // different valno's. 257 assert(I->start >= End && 258 "Cannot overlap two segments with differing ValID's"); 259 } 260 } 261 262 // Otherwise, this is just a new segment that doesn't interact with 263 // anything. 264 // Insert it. 265 return segments().insert(I, S); 266 } 267 268 private: 269 ImplT &impl() { return *static_cast<ImplT *>(this); } 270 271 CollectionT &segments() { return impl().segmentsColl(); } 272 273 Segment *segmentAt(iterator I) { return const_cast<Segment *>(&(*I)); } 274 }; 275 276 //===----------------------------------------------------------------------===// 277 // Instantiation of the methods for calculation of live ranges 278 // based on a segment vector. 279 //===----------------------------------------------------------------------===// 280 281 class CalcLiveRangeUtilVector; 282 using CalcLiveRangeUtilVectorBase = 283 CalcLiveRangeUtilBase<CalcLiveRangeUtilVector, LiveRange::iterator, 284 LiveRange::Segments>; 285 286 class CalcLiveRangeUtilVector : public CalcLiveRangeUtilVectorBase { 287 public: 288 CalcLiveRangeUtilVector(LiveRange *LR) : CalcLiveRangeUtilVectorBase(LR) {} 289 290 private: 291 friend CalcLiveRangeUtilVectorBase; 292 293 LiveRange::Segments &segmentsColl() { return LR->segments; } 294 295 void insertAtEnd(const Segment &S) { LR->segments.push_back(S); } 296 297 iterator find(SlotIndex Pos) { return LR->find(Pos); } 298 299 iterator findInsertPos(Segment S) { return llvm::upper_bound(*LR, S.start); } 300 }; 301 302 //===----------------------------------------------------------------------===// 303 // Instantiation of the methods for calculation of live ranges 304 // based on a segment set. 305 //===----------------------------------------------------------------------===// 306 307 class CalcLiveRangeUtilSet; 308 using CalcLiveRangeUtilSetBase = 309 CalcLiveRangeUtilBase<CalcLiveRangeUtilSet, LiveRange::SegmentSet::iterator, 310 LiveRange::SegmentSet>; 311 312 class CalcLiveRangeUtilSet : public CalcLiveRangeUtilSetBase { 313 public: 314 CalcLiveRangeUtilSet(LiveRange *LR) : CalcLiveRangeUtilSetBase(LR) {} 315 316 private: 317 friend CalcLiveRangeUtilSetBase; 318 319 LiveRange::SegmentSet &segmentsColl() { return *LR->segmentSet; } 320 321 void insertAtEnd(const Segment &S) { 322 LR->segmentSet->insert(LR->segmentSet->end(), S); 323 } 324 325 iterator find(SlotIndex Pos) { 326 iterator I = 327 LR->segmentSet->upper_bound(Segment(Pos, Pos.getNextSlot(), nullptr)); 328 if (I == LR->segmentSet->begin()) 329 return I; 330 iterator PrevI = std::prev(I); 331 if (Pos < (*PrevI).end) 332 return PrevI; 333 return I; 334 } 335 336 iterator findInsertPos(Segment S) { 337 iterator I = LR->segmentSet->upper_bound(S); 338 if (I != LR->segmentSet->end() && !(S.start < *I)) 339 ++I; 340 return I; 341 } 342 }; 343 344 } // end anonymous namespace 345 346 //===----------------------------------------------------------------------===// 347 // LiveRange methods 348 //===----------------------------------------------------------------------===// 349 350 LiveRange::iterator LiveRange::find(SlotIndex Pos) { 351 // This algorithm is basically std::upper_bound. 352 // Unfortunately, std::upper_bound cannot be used with mixed types until we 353 // adopt C++0x. Many libraries can do it, but not all. 354 if (empty() || Pos >= endIndex()) 355 return end(); 356 iterator I = begin(); 357 size_t Len = size(); 358 do { 359 size_t Mid = Len >> 1; 360 if (Pos < I[Mid].end) { 361 Len = Mid; 362 } else { 363 I += Mid + 1; 364 Len -= Mid + 1; 365 } 366 } while (Len); 367 return I; 368 } 369 370 VNInfo *LiveRange::createDeadDef(SlotIndex Def, VNInfo::Allocator &VNIAlloc) { 371 // Use the segment set, if it is available. 372 if (segmentSet != nullptr) 373 return CalcLiveRangeUtilSet(this).createDeadDef(Def, &VNIAlloc, nullptr); 374 // Otherwise use the segment vector. 375 return CalcLiveRangeUtilVector(this).createDeadDef(Def, &VNIAlloc, nullptr); 376 } 377 378 VNInfo *LiveRange::createDeadDef(VNInfo *VNI) { 379 // Use the segment set, if it is available. 380 if (segmentSet != nullptr) 381 return CalcLiveRangeUtilSet(this).createDeadDef(VNI->def, nullptr, VNI); 382 // Otherwise use the segment vector. 383 return CalcLiveRangeUtilVector(this).createDeadDef(VNI->def, nullptr, VNI); 384 } 385 386 // overlaps - Return true if the intersection of the two live ranges is 387 // not empty. 388 // 389 // An example for overlaps(): 390 // 391 // 0: A = ... 392 // 4: B = ... 393 // 8: C = A + B ;; last use of A 394 // 395 // The live ranges should look like: 396 // 397 // A = [3, 11) 398 // B = [7, x) 399 // C = [11, y) 400 // 401 // A->overlaps(C) should return false since we want to be able to join 402 // A and C. 403 // 404 bool LiveRange::overlapsFrom(const LiveRange& other, 405 const_iterator StartPos) const { 406 assert(!empty() && "empty range"); 407 const_iterator i = begin(); 408 const_iterator ie = end(); 409 const_iterator j = StartPos; 410 const_iterator je = other.end(); 411 412 assert((StartPos->start <= i->start || StartPos == other.begin()) && 413 StartPos != other.end() && "Bogus start position hint!"); 414 415 if (i->start < j->start) { 416 i = std::upper_bound(i, ie, j->start); 417 if (i != begin()) --i; 418 } else if (j->start < i->start) { 419 ++StartPos; 420 if (StartPos != other.end() && StartPos->start <= i->start) { 421 assert(StartPos < other.end() && i < end()); 422 j = std::upper_bound(j, je, i->start); 423 if (j != other.begin()) --j; 424 } 425 } else { 426 return true; 427 } 428 429 if (j == je) return false; 430 431 while (i != ie) { 432 if (i->start > j->start) { 433 std::swap(i, j); 434 std::swap(ie, je); 435 } 436 437 if (i->end > j->start) 438 return true; 439 ++i; 440 } 441 442 return false; 443 } 444 445 bool LiveRange::overlaps(const LiveRange &Other, const CoalescerPair &CP, 446 const SlotIndexes &Indexes) const { 447 assert(!empty() && "empty range"); 448 if (Other.empty()) 449 return false; 450 451 // Use binary searches to find initial positions. 452 const_iterator I = find(Other.beginIndex()); 453 const_iterator IE = end(); 454 if (I == IE) 455 return false; 456 const_iterator J = Other.find(I->start); 457 const_iterator JE = Other.end(); 458 if (J == JE) 459 return false; 460 461 while (true) { 462 // J has just been advanced to satisfy: 463 assert(J->end >= I->start); 464 // Check for an overlap. 465 if (J->start < I->end) { 466 // I and J are overlapping. Find the later start. 467 SlotIndex Def = std::max(I->start, J->start); 468 // Allow the overlap if Def is a coalescable copy. 469 if (Def.isBlock() || 470 !CP.isCoalescable(Indexes.getInstructionFromIndex(Def))) 471 return true; 472 } 473 // Advance the iterator that ends first to check for more overlaps. 474 if (J->end > I->end) { 475 std::swap(I, J); 476 std::swap(IE, JE); 477 } 478 // Advance J until J->end >= I->start. 479 do 480 if (++J == JE) 481 return false; 482 while (J->end < I->start); 483 } 484 } 485 486 /// overlaps - Return true if the live range overlaps an interval specified 487 /// by [Start, End). 488 bool LiveRange::overlaps(SlotIndex Start, SlotIndex End) const { 489 assert(Start < End && "Invalid range"); 490 const_iterator I = std::lower_bound(begin(), end(), End); 491 return I != begin() && (--I)->end > Start; 492 } 493 494 bool LiveRange::covers(const LiveRange &Other) const { 495 if (empty()) 496 return Other.empty(); 497 498 const_iterator I = begin(); 499 for (const Segment &O : Other.segments) { 500 I = advanceTo(I, O.start); 501 if (I == end() || I->start > O.start) 502 return false; 503 504 // Check adjacent live segments and see if we can get behind O.end. 505 while (I->end < O.end) { 506 const_iterator Last = I; 507 // Get next segment and abort if it was not adjacent. 508 ++I; 509 if (I == end() || Last->end != I->start) 510 return false; 511 } 512 } 513 return true; 514 } 515 516 /// ValNo is dead, remove it. If it is the largest value number, just nuke it 517 /// (and any other deleted values neighboring it), otherwise mark it as ~1U so 518 /// it can be nuked later. 519 void LiveRange::markValNoForDeletion(VNInfo *ValNo) { 520 if (ValNo->id == getNumValNums()-1) { 521 do { 522 valnos.pop_back(); 523 } while (!valnos.empty() && valnos.back()->isUnused()); 524 } else { 525 ValNo->markUnused(); 526 } 527 } 528 529 /// RenumberValues - Renumber all values in order of appearance and delete the 530 /// remaining unused values. 531 void LiveRange::RenumberValues() { 532 SmallPtrSet<VNInfo*, 8> Seen; 533 valnos.clear(); 534 for (const Segment &S : segments) { 535 VNInfo *VNI = S.valno; 536 if (!Seen.insert(VNI).second) 537 continue; 538 assert(!VNI->isUnused() && "Unused valno used by live segment"); 539 VNI->id = (unsigned)valnos.size(); 540 valnos.push_back(VNI); 541 } 542 } 543 544 void LiveRange::addSegmentToSet(Segment S) { 545 CalcLiveRangeUtilSet(this).addSegment(S); 546 } 547 548 LiveRange::iterator LiveRange::addSegment(Segment S) { 549 // Use the segment set, if it is available. 550 if (segmentSet != nullptr) { 551 addSegmentToSet(S); 552 return end(); 553 } 554 // Otherwise use the segment vector. 555 return CalcLiveRangeUtilVector(this).addSegment(S); 556 } 557 558 void LiveRange::append(const Segment S) { 559 // Check that the segment belongs to the back of the list. 560 assert(segments.empty() || segments.back().end <= S.start); 561 segments.push_back(S); 562 } 563 564 std::pair<VNInfo*,bool> LiveRange::extendInBlock(ArrayRef<SlotIndex> Undefs, 565 SlotIndex StartIdx, SlotIndex Kill) { 566 // Use the segment set, if it is available. 567 if (segmentSet != nullptr) 568 return CalcLiveRangeUtilSet(this).extendInBlock(Undefs, StartIdx, Kill); 569 // Otherwise use the segment vector. 570 return CalcLiveRangeUtilVector(this).extendInBlock(Undefs, StartIdx, Kill); 571 } 572 573 VNInfo *LiveRange::extendInBlock(SlotIndex StartIdx, SlotIndex Kill) { 574 // Use the segment set, if it is available. 575 if (segmentSet != nullptr) 576 return CalcLiveRangeUtilSet(this).extendInBlock(StartIdx, Kill); 577 // Otherwise use the segment vector. 578 return CalcLiveRangeUtilVector(this).extendInBlock(StartIdx, Kill); 579 } 580 581 /// Remove the specified segment from this range. Note that the segment must 582 /// be in a single Segment in its entirety. 583 void LiveRange::removeSegment(SlotIndex Start, SlotIndex End, 584 bool RemoveDeadValNo) { 585 // Find the Segment containing this span. 586 iterator I = find(Start); 587 assert(I != end() && "Segment is not in range!"); 588 assert(I->containsInterval(Start, End) 589 && "Segment is not entirely in range!"); 590 591 // If the span we are removing is at the start of the Segment, adjust it. 592 VNInfo *ValNo = I->valno; 593 if (I->start == Start) { 594 if (I->end == End) { 595 if (RemoveDeadValNo) { 596 // Check if val# is dead. 597 bool isDead = true; 598 for (const_iterator II = begin(), EE = end(); II != EE; ++II) 599 if (II != I && II->valno == ValNo) { 600 isDead = false; 601 break; 602 } 603 if (isDead) { 604 // Now that ValNo is dead, remove it. 605 markValNoForDeletion(ValNo); 606 } 607 } 608 609 segments.erase(I); // Removed the whole Segment. 610 } else 611 I->start = End; 612 return; 613 } 614 615 // Otherwise if the span we are removing is at the end of the Segment, 616 // adjust the other way. 617 if (I->end == End) { 618 I->end = Start; 619 return; 620 } 621 622 // Otherwise, we are splitting the Segment into two pieces. 623 SlotIndex OldEnd = I->end; 624 I->end = Start; // Trim the old segment. 625 626 // Insert the new one. 627 segments.insert(std::next(I), Segment(End, OldEnd, ValNo)); 628 } 629 630 /// removeValNo - Remove all the segments defined by the specified value#. 631 /// Also remove the value# from value# list. 632 void LiveRange::removeValNo(VNInfo *ValNo) { 633 if (empty()) return; 634 segments.erase(remove_if(*this, [ValNo](const Segment &S) { 635 return S.valno == ValNo; 636 }), end()); 637 // Now that ValNo is dead, remove it. 638 markValNoForDeletion(ValNo); 639 } 640 641 void LiveRange::join(LiveRange &Other, 642 const int *LHSValNoAssignments, 643 const int *RHSValNoAssignments, 644 SmallVectorImpl<VNInfo *> &NewVNInfo) { 645 verify(); 646 647 // Determine if any of our values are mapped. This is uncommon, so we want 648 // to avoid the range scan if not. 649 bool MustMapCurValNos = false; 650 unsigned NumVals = getNumValNums(); 651 unsigned NumNewVals = NewVNInfo.size(); 652 for (unsigned i = 0; i != NumVals; ++i) { 653 unsigned LHSValID = LHSValNoAssignments[i]; 654 if (i != LHSValID || 655 (NewVNInfo[LHSValID] && NewVNInfo[LHSValID] != getValNumInfo(i))) { 656 MustMapCurValNos = true; 657 break; 658 } 659 } 660 661 // If we have to apply a mapping to our base range assignment, rewrite it now. 662 if (MustMapCurValNos && !empty()) { 663 // Map the first live range. 664 665 iterator OutIt = begin(); 666 OutIt->valno = NewVNInfo[LHSValNoAssignments[OutIt->valno->id]]; 667 for (iterator I = std::next(OutIt), E = end(); I != E; ++I) { 668 VNInfo* nextValNo = NewVNInfo[LHSValNoAssignments[I->valno->id]]; 669 assert(nextValNo && "Huh?"); 670 671 // If this live range has the same value # as its immediate predecessor, 672 // and if they are neighbors, remove one Segment. This happens when we 673 // have [0,4:0)[4,7:1) and map 0/1 onto the same value #. 674 if (OutIt->valno == nextValNo && OutIt->end == I->start) { 675 OutIt->end = I->end; 676 } else { 677 // Didn't merge. Move OutIt to the next segment, 678 ++OutIt; 679 OutIt->valno = nextValNo; 680 if (OutIt != I) { 681 OutIt->start = I->start; 682 OutIt->end = I->end; 683 } 684 } 685 } 686 // If we merge some segments, chop off the end. 687 ++OutIt; 688 segments.erase(OutIt, end()); 689 } 690 691 // Rewrite Other values before changing the VNInfo ids. 692 // This can leave Other in an invalid state because we're not coalescing 693 // touching segments that now have identical values. That's OK since Other is 694 // not supposed to be valid after calling join(); 695 for (Segment &S : Other.segments) 696 S.valno = NewVNInfo[RHSValNoAssignments[S.valno->id]]; 697 698 // Update val# info. Renumber them and make sure they all belong to this 699 // LiveRange now. Also remove dead val#'s. 700 unsigned NumValNos = 0; 701 for (unsigned i = 0; i < NumNewVals; ++i) { 702 VNInfo *VNI = NewVNInfo[i]; 703 if (VNI) { 704 if (NumValNos >= NumVals) 705 valnos.push_back(VNI); 706 else 707 valnos[NumValNos] = VNI; 708 VNI->id = NumValNos++; // Renumber val#. 709 } 710 } 711 if (NumNewVals < NumVals) 712 valnos.resize(NumNewVals); // shrinkify 713 714 // Okay, now insert the RHS live segments into the LHS. 715 LiveRangeUpdater Updater(this); 716 for (Segment &S : Other.segments) 717 Updater.add(S); 718 } 719 720 /// Merge all of the segments in RHS into this live range as the specified 721 /// value number. The segments in RHS are allowed to overlap with segments in 722 /// the current range, but only if the overlapping segments have the 723 /// specified value number. 724 void LiveRange::MergeSegmentsInAsValue(const LiveRange &RHS, 725 VNInfo *LHSValNo) { 726 LiveRangeUpdater Updater(this); 727 for (const Segment &S : RHS.segments) 728 Updater.add(S.start, S.end, LHSValNo); 729 } 730 731 /// MergeValueInAsValue - Merge all of the live segments of a specific val# 732 /// in RHS into this live range as the specified value number. 733 /// The segments in RHS are allowed to overlap with segments in the 734 /// current range, it will replace the value numbers of the overlaped 735 /// segments with the specified value number. 736 void LiveRange::MergeValueInAsValue(const LiveRange &RHS, 737 const VNInfo *RHSValNo, 738 VNInfo *LHSValNo) { 739 LiveRangeUpdater Updater(this); 740 for (const Segment &S : RHS.segments) 741 if (S.valno == RHSValNo) 742 Updater.add(S.start, S.end, LHSValNo); 743 } 744 745 /// MergeValueNumberInto - This method is called when two value nubmers 746 /// are found to be equivalent. This eliminates V1, replacing all 747 /// segments with the V1 value number with the V2 value number. This can 748 /// cause merging of V1/V2 values numbers and compaction of the value space. 749 VNInfo *LiveRange::MergeValueNumberInto(VNInfo *V1, VNInfo *V2) { 750 assert(V1 != V2 && "Identical value#'s are always equivalent!"); 751 752 // This code actually merges the (numerically) larger value number into the 753 // smaller value number, which is likely to allow us to compactify the value 754 // space. The only thing we have to be careful of is to preserve the 755 // instruction that defines the result value. 756 757 // Make sure V2 is smaller than V1. 758 if (V1->id < V2->id) { 759 V1->copyFrom(*V2); 760 std::swap(V1, V2); 761 } 762 763 // Merge V1 segments into V2. 764 for (iterator I = begin(); I != end(); ) { 765 iterator S = I++; 766 if (S->valno != V1) continue; // Not a V1 Segment. 767 768 // Okay, we found a V1 live range. If it had a previous, touching, V2 live 769 // range, extend it. 770 if (S != begin()) { 771 iterator Prev = S-1; 772 if (Prev->valno == V2 && Prev->end == S->start) { 773 Prev->end = S->end; 774 775 // Erase this live-range. 776 segments.erase(S); 777 I = Prev+1; 778 S = Prev; 779 } 780 } 781 782 // Okay, now we have a V1 or V2 live range that is maximally merged forward. 783 // Ensure that it is a V2 live-range. 784 S->valno = V2; 785 786 // If we can merge it into later V2 segments, do so now. We ignore any 787 // following V1 segments, as they will be merged in subsequent iterations 788 // of the loop. 789 if (I != end()) { 790 if (I->start == S->end && I->valno == V2) { 791 S->end = I->end; 792 segments.erase(I); 793 I = S+1; 794 } 795 } 796 } 797 798 // Now that V1 is dead, remove it. 799 markValNoForDeletion(V1); 800 801 return V2; 802 } 803 804 void LiveRange::flushSegmentSet() { 805 assert(segmentSet != nullptr && "segment set must have been created"); 806 assert( 807 segments.empty() && 808 "segment set can be used only initially before switching to the array"); 809 segments.append(segmentSet->begin(), segmentSet->end()); 810 segmentSet = nullptr; 811 verify(); 812 } 813 814 bool LiveRange::isLiveAtIndexes(ArrayRef<SlotIndex> Slots) const { 815 ArrayRef<SlotIndex>::iterator SlotI = Slots.begin(); 816 ArrayRef<SlotIndex>::iterator SlotE = Slots.end(); 817 818 // If there are no regmask slots, we have nothing to search. 819 if (SlotI == SlotE) 820 return false; 821 822 // Start our search at the first segment that ends after the first slot. 823 const_iterator SegmentI = find(*SlotI); 824 const_iterator SegmentE = end(); 825 826 // If there are no segments that end after the first slot, we're done. 827 if (SegmentI == SegmentE) 828 return false; 829 830 // Look for each slot in the live range. 831 for ( ; SlotI != SlotE; ++SlotI) { 832 // Go to the next segment that ends after the current slot. 833 // The slot may be within a hole in the range. 834 SegmentI = advanceTo(SegmentI, *SlotI); 835 if (SegmentI == SegmentE) 836 return false; 837 838 // If this segment contains the slot, we're done. 839 if (SegmentI->contains(*SlotI)) 840 return true; 841 // Otherwise, look for the next slot. 842 } 843 844 // We didn't find a segment containing any of the slots. 845 return false; 846 } 847 848 void LiveInterval::freeSubRange(SubRange *S) { 849 S->~SubRange(); 850 // Memory was allocated with BumpPtr allocator and is not freed here. 851 } 852 853 void LiveInterval::removeEmptySubRanges() { 854 SubRange **NextPtr = &SubRanges; 855 SubRange *I = *NextPtr; 856 while (I != nullptr) { 857 if (!I->empty()) { 858 NextPtr = &I->Next; 859 I = *NextPtr; 860 continue; 861 } 862 // Skip empty subranges until we find the first nonempty one. 863 do { 864 SubRange *Next = I->Next; 865 freeSubRange(I); 866 I = Next; 867 } while (I != nullptr && I->empty()); 868 *NextPtr = I; 869 } 870 } 871 872 void LiveInterval::clearSubRanges() { 873 for (SubRange *I = SubRanges, *Next; I != nullptr; I = Next) { 874 Next = I->Next; 875 freeSubRange(I); 876 } 877 SubRanges = nullptr; 878 } 879 880 /// For each VNI in \p SR, check whether or not that value defines part 881 /// of the mask describe by \p LaneMask and if not, remove that value 882 /// from \p SR. 883 static void stripValuesNotDefiningMask(unsigned Reg, LiveInterval::SubRange &SR, 884 LaneBitmask LaneMask, 885 const SlotIndexes &Indexes, 886 const TargetRegisterInfo &TRI) { 887 // Phys reg should not be tracked at subreg level. 888 // Same for noreg (Reg == 0). 889 if (!Register::isVirtualRegister(Reg) || !Reg) 890 return; 891 // Remove the values that don't define those lanes. 892 SmallVector<VNInfo *, 8> ToBeRemoved; 893 for (VNInfo *VNI : SR.valnos) { 894 if (VNI->isUnused()) 895 continue; 896 // PHI definitions don't have MI attached, so there is nothing 897 // we can use to strip the VNI. 898 if (VNI->isPHIDef()) 899 continue; 900 const MachineInstr *MI = Indexes.getInstructionFromIndex(VNI->def); 901 assert(MI && "Cannot find the definition of a value"); 902 bool hasDef = false; 903 for (ConstMIBundleOperands MOI(*MI); MOI.isValid(); ++MOI) { 904 if (!MOI->isReg() || !MOI->isDef()) 905 continue; 906 if (MOI->getReg() != Reg) 907 continue; 908 if ((TRI.getSubRegIndexLaneMask(MOI->getSubReg()) & LaneMask).none()) 909 continue; 910 hasDef = true; 911 break; 912 } 913 914 if (!hasDef) 915 ToBeRemoved.push_back(VNI); 916 } 917 for (VNInfo *VNI : ToBeRemoved) 918 SR.removeValNo(VNI); 919 920 // If the subrange is empty at this point, the MIR is invalid. Do not assert 921 // and let the verifier catch this case. 922 } 923 924 void LiveInterval::refineSubRanges( 925 BumpPtrAllocator &Allocator, LaneBitmask LaneMask, 926 std::function<void(LiveInterval::SubRange &)> Apply, 927 const SlotIndexes &Indexes, const TargetRegisterInfo &TRI) { 928 LaneBitmask ToApply = LaneMask; 929 for (SubRange &SR : subranges()) { 930 LaneBitmask SRMask = SR.LaneMask; 931 LaneBitmask Matching = SRMask & LaneMask; 932 if (Matching.none()) 933 continue; 934 935 SubRange *MatchingRange; 936 if (SRMask == Matching) { 937 // The subrange fits (it does not cover bits outside \p LaneMask). 938 MatchingRange = &SR; 939 } else { 940 // We have to split the subrange into a matching and non-matching part. 941 // Reduce lanemask of existing lane to non-matching part. 942 SR.LaneMask = SRMask & ~Matching; 943 // Create a new subrange for the matching part 944 MatchingRange = createSubRangeFrom(Allocator, Matching, SR); 945 // Now that the subrange is split in half, make sure we 946 // only keep in the subranges the VNIs that touch the related half. 947 stripValuesNotDefiningMask(reg, *MatchingRange, Matching, Indexes, TRI); 948 stripValuesNotDefiningMask(reg, SR, SR.LaneMask, Indexes, TRI); 949 } 950 Apply(*MatchingRange); 951 ToApply &= ~Matching; 952 } 953 // Create a new subrange if there are uncovered bits left. 954 if (ToApply.any()) { 955 SubRange *NewRange = createSubRange(Allocator, ToApply); 956 Apply(*NewRange); 957 } 958 } 959 960 unsigned LiveInterval::getSize() const { 961 unsigned Sum = 0; 962 for (const Segment &S : segments) 963 Sum += S.start.distance(S.end); 964 return Sum; 965 } 966 967 void LiveInterval::computeSubRangeUndefs(SmallVectorImpl<SlotIndex> &Undefs, 968 LaneBitmask LaneMask, 969 const MachineRegisterInfo &MRI, 970 const SlotIndexes &Indexes) const { 971 assert(Register::isVirtualRegister(reg)); 972 LaneBitmask VRegMask = MRI.getMaxLaneMaskForVReg(reg); 973 assert((VRegMask & LaneMask).any()); 974 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo(); 975 for (const MachineOperand &MO : MRI.def_operands(reg)) { 976 if (!MO.isUndef()) 977 continue; 978 unsigned SubReg = MO.getSubReg(); 979 assert(SubReg != 0 && "Undef should only be set on subreg defs"); 980 LaneBitmask DefMask = TRI.getSubRegIndexLaneMask(SubReg); 981 LaneBitmask UndefMask = VRegMask & ~DefMask; 982 if ((UndefMask & LaneMask).any()) { 983 const MachineInstr &MI = *MO.getParent(); 984 bool EarlyClobber = MO.isEarlyClobber(); 985 SlotIndex Pos = Indexes.getInstructionIndex(MI).getRegSlot(EarlyClobber); 986 Undefs.push_back(Pos); 987 } 988 } 989 } 990 991 raw_ostream& llvm::operator<<(raw_ostream& OS, const LiveRange::Segment &S) { 992 return OS << '[' << S.start << ',' << S.end << ':' << S.valno->id << ')'; 993 } 994 995 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 996 LLVM_DUMP_METHOD void LiveRange::Segment::dump() const { 997 dbgs() << *this << '\n'; 998 } 999 #endif 1000 1001 void LiveRange::print(raw_ostream &OS) const { 1002 if (empty()) 1003 OS << "EMPTY"; 1004 else { 1005 for (const Segment &S : segments) { 1006 OS << S; 1007 assert(S.valno == getValNumInfo(S.valno->id) && "Bad VNInfo"); 1008 } 1009 } 1010 1011 // Print value number info. 1012 if (getNumValNums()) { 1013 OS << " "; 1014 unsigned vnum = 0; 1015 for (const_vni_iterator i = vni_begin(), e = vni_end(); i != e; 1016 ++i, ++vnum) { 1017 const VNInfo *vni = *i; 1018 if (vnum) OS << ' '; 1019 OS << vnum << '@'; 1020 if (vni->isUnused()) { 1021 OS << 'x'; 1022 } else { 1023 OS << vni->def; 1024 if (vni->isPHIDef()) 1025 OS << "-phi"; 1026 } 1027 } 1028 } 1029 } 1030 1031 void LiveInterval::SubRange::print(raw_ostream &OS) const { 1032 OS << " L" << PrintLaneMask(LaneMask) << ' ' 1033 << static_cast<const LiveRange&>(*this); 1034 } 1035 1036 void LiveInterval::print(raw_ostream &OS) const { 1037 OS << printReg(reg) << ' '; 1038 super::print(OS); 1039 // Print subranges 1040 for (const SubRange &SR : subranges()) 1041 OS << SR; 1042 OS << " weight:" << weight; 1043 } 1044 1045 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 1046 LLVM_DUMP_METHOD void LiveRange::dump() const { 1047 dbgs() << *this << '\n'; 1048 } 1049 1050 LLVM_DUMP_METHOD void LiveInterval::SubRange::dump() const { 1051 dbgs() << *this << '\n'; 1052 } 1053 1054 LLVM_DUMP_METHOD void LiveInterval::dump() const { 1055 dbgs() << *this << '\n'; 1056 } 1057 #endif 1058 1059 #ifndef NDEBUG 1060 void LiveRange::verify() const { 1061 for (const_iterator I = begin(), E = end(); I != E; ++I) { 1062 assert(I->start.isValid()); 1063 assert(I->end.isValid()); 1064 assert(I->start < I->end); 1065 assert(I->valno != nullptr); 1066 assert(I->valno->id < valnos.size()); 1067 assert(I->valno == valnos[I->valno->id]); 1068 if (std::next(I) != E) { 1069 assert(I->end <= std::next(I)->start); 1070 if (I->end == std::next(I)->start) 1071 assert(I->valno != std::next(I)->valno); 1072 } 1073 } 1074 } 1075 1076 void LiveInterval::verify(const MachineRegisterInfo *MRI) const { 1077 super::verify(); 1078 1079 // Make sure SubRanges are fine and LaneMasks are disjunct. 1080 LaneBitmask Mask; 1081 LaneBitmask MaxMask = MRI != nullptr ? MRI->getMaxLaneMaskForVReg(reg) 1082 : LaneBitmask::getAll(); 1083 for (const SubRange &SR : subranges()) { 1084 // Subrange lanemask should be disjunct to any previous subrange masks. 1085 assert((Mask & SR.LaneMask).none()); 1086 Mask |= SR.LaneMask; 1087 1088 // subrange mask should not contained in maximum lane mask for the vreg. 1089 assert((Mask & ~MaxMask).none()); 1090 // empty subranges must be removed. 1091 assert(!SR.empty()); 1092 1093 SR.verify(); 1094 // Main liverange should cover subrange. 1095 assert(covers(SR)); 1096 } 1097 } 1098 #endif 1099 1100 //===----------------------------------------------------------------------===// 1101 // LiveRangeUpdater class 1102 //===----------------------------------------------------------------------===// 1103 // 1104 // The LiveRangeUpdater class always maintains these invariants: 1105 // 1106 // - When LastStart is invalid, Spills is empty and the iterators are invalid. 1107 // This is the initial state, and the state created by flush(). 1108 // In this state, isDirty() returns false. 1109 // 1110 // Otherwise, segments are kept in three separate areas: 1111 // 1112 // 1. [begin; WriteI) at the front of LR. 1113 // 2. [ReadI; end) at the back of LR. 1114 // 3. Spills. 1115 // 1116 // - LR.begin() <= WriteI <= ReadI <= LR.end(). 1117 // - Segments in all three areas are fully ordered and coalesced. 1118 // - Segments in area 1 precede and can't coalesce with segments in area 2. 1119 // - Segments in Spills precede and can't coalesce with segments in area 2. 1120 // - No coalescing is possible between segments in Spills and segments in area 1121 // 1, and there are no overlapping segments. 1122 // 1123 // The segments in Spills are not ordered with respect to the segments in area 1124 // 1. They need to be merged. 1125 // 1126 // When they exist, Spills.back().start <= LastStart, 1127 // and WriteI[-1].start <= LastStart. 1128 1129 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 1130 void LiveRangeUpdater::print(raw_ostream &OS) const { 1131 if (!isDirty()) { 1132 if (LR) 1133 OS << "Clean updater: " << *LR << '\n'; 1134 else 1135 OS << "Null updater.\n"; 1136 return; 1137 } 1138 assert(LR && "Can't have null LR in dirty updater."); 1139 OS << " updater with gap = " << (ReadI - WriteI) 1140 << ", last start = " << LastStart 1141 << ":\n Area 1:"; 1142 for (const auto &S : make_range(LR->begin(), WriteI)) 1143 OS << ' ' << S; 1144 OS << "\n Spills:"; 1145 for (unsigned I = 0, E = Spills.size(); I != E; ++I) 1146 OS << ' ' << Spills[I]; 1147 OS << "\n Area 2:"; 1148 for (const auto &S : make_range(ReadI, LR->end())) 1149 OS << ' ' << S; 1150 OS << '\n'; 1151 } 1152 1153 LLVM_DUMP_METHOD void LiveRangeUpdater::dump() const { 1154 print(errs()); 1155 } 1156 #endif 1157 1158 // Determine if A and B should be coalesced. 1159 static inline bool coalescable(const LiveRange::Segment &A, 1160 const LiveRange::Segment &B) { 1161 assert(A.start <= B.start && "Unordered live segments."); 1162 if (A.end == B.start) 1163 return A.valno == B.valno; 1164 if (A.end < B.start) 1165 return false; 1166 assert(A.valno == B.valno && "Cannot overlap different values"); 1167 return true; 1168 } 1169 1170 void LiveRangeUpdater::add(LiveRange::Segment Seg) { 1171 assert(LR && "Cannot add to a null destination"); 1172 1173 // Fall back to the regular add method if the live range 1174 // is using the segment set instead of the segment vector. 1175 if (LR->segmentSet != nullptr) { 1176 LR->addSegmentToSet(Seg); 1177 return; 1178 } 1179 1180 // Flush the state if Start moves backwards. 1181 if (!LastStart.isValid() || LastStart > Seg.start) { 1182 if (isDirty()) 1183 flush(); 1184 // This brings us to an uninitialized state. Reinitialize. 1185 assert(Spills.empty() && "Leftover spilled segments"); 1186 WriteI = ReadI = LR->begin(); 1187 } 1188 1189 // Remember start for next time. 1190 LastStart = Seg.start; 1191 1192 // Advance ReadI until it ends after Seg.start. 1193 LiveRange::iterator E = LR->end(); 1194 if (ReadI != E && ReadI->end <= Seg.start) { 1195 // First try to close the gap between WriteI and ReadI with spills. 1196 if (ReadI != WriteI) 1197 mergeSpills(); 1198 // Then advance ReadI. 1199 if (ReadI == WriteI) 1200 ReadI = WriteI = LR->find(Seg.start); 1201 else 1202 while (ReadI != E && ReadI->end <= Seg.start) 1203 *WriteI++ = *ReadI++; 1204 } 1205 1206 assert(ReadI == E || ReadI->end > Seg.start); 1207 1208 // Check if the ReadI segment begins early. 1209 if (ReadI != E && ReadI->start <= Seg.start) { 1210 assert(ReadI->valno == Seg.valno && "Cannot overlap different values"); 1211 // Bail if Seg is completely contained in ReadI. 1212 if (ReadI->end >= Seg.end) 1213 return; 1214 // Coalesce into Seg. 1215 Seg.start = ReadI->start; 1216 ++ReadI; 1217 } 1218 1219 // Coalesce as much as possible from ReadI into Seg. 1220 while (ReadI != E && coalescable(Seg, *ReadI)) { 1221 Seg.end = std::max(Seg.end, ReadI->end); 1222 ++ReadI; 1223 } 1224 1225 // Try coalescing Spills.back() into Seg. 1226 if (!Spills.empty() && coalescable(Spills.back(), Seg)) { 1227 Seg.start = Spills.back().start; 1228 Seg.end = std::max(Spills.back().end, Seg.end); 1229 Spills.pop_back(); 1230 } 1231 1232 // Try coalescing Seg into WriteI[-1]. 1233 if (WriteI != LR->begin() && coalescable(WriteI[-1], Seg)) { 1234 WriteI[-1].end = std::max(WriteI[-1].end, Seg.end); 1235 return; 1236 } 1237 1238 // Seg doesn't coalesce with anything, and needs to be inserted somewhere. 1239 if (WriteI != ReadI) { 1240 *WriteI++ = Seg; 1241 return; 1242 } 1243 1244 // Finally, append to LR or Spills. 1245 if (WriteI == E) { 1246 LR->segments.push_back(Seg); 1247 WriteI = ReadI = LR->end(); 1248 } else 1249 Spills.push_back(Seg); 1250 } 1251 1252 // Merge as many spilled segments as possible into the gap between WriteI 1253 // and ReadI. Advance WriteI to reflect the inserted instructions. 1254 void LiveRangeUpdater::mergeSpills() { 1255 // Perform a backwards merge of Spills and [SpillI;WriteI). 1256 size_t GapSize = ReadI - WriteI; 1257 size_t NumMoved = std::min(Spills.size(), GapSize); 1258 LiveRange::iterator Src = WriteI; 1259 LiveRange::iterator Dst = Src + NumMoved; 1260 LiveRange::iterator SpillSrc = Spills.end(); 1261 LiveRange::iterator B = LR->begin(); 1262 1263 // This is the new WriteI position after merging spills. 1264 WriteI = Dst; 1265 1266 // Now merge Src and Spills backwards. 1267 while (Src != Dst) { 1268 if (Src != B && Src[-1].start > SpillSrc[-1].start) 1269 *--Dst = *--Src; 1270 else 1271 *--Dst = *--SpillSrc; 1272 } 1273 assert(NumMoved == size_t(Spills.end() - SpillSrc)); 1274 Spills.erase(SpillSrc, Spills.end()); 1275 } 1276 1277 void LiveRangeUpdater::flush() { 1278 if (!isDirty()) 1279 return; 1280 // Clear the dirty state. 1281 LastStart = SlotIndex(); 1282 1283 assert(LR && "Cannot add to a null destination"); 1284 1285 // Nothing to merge? 1286 if (Spills.empty()) { 1287 LR->segments.erase(WriteI, ReadI); 1288 LR->verify(); 1289 return; 1290 } 1291 1292 // Resize the WriteI - ReadI gap to match Spills. 1293 size_t GapSize = ReadI - WriteI; 1294 if (GapSize < Spills.size()) { 1295 // The gap is too small. Make some room. 1296 size_t WritePos = WriteI - LR->begin(); 1297 LR->segments.insert(ReadI, Spills.size() - GapSize, LiveRange::Segment()); 1298 // This also invalidated ReadI, but it is recomputed below. 1299 WriteI = LR->begin() + WritePos; 1300 } else { 1301 // Shrink the gap if necessary. 1302 LR->segments.erase(WriteI + Spills.size(), ReadI); 1303 } 1304 ReadI = WriteI + Spills.size(); 1305 mergeSpills(); 1306 LR->verify(); 1307 } 1308 1309 unsigned ConnectedVNInfoEqClasses::Classify(const LiveRange &LR) { 1310 // Create initial equivalence classes. 1311 EqClass.clear(); 1312 EqClass.grow(LR.getNumValNums()); 1313 1314 const VNInfo *used = nullptr, *unused = nullptr; 1315 1316 // Determine connections. 1317 for (const VNInfo *VNI : LR.valnos) { 1318 // Group all unused values into one class. 1319 if (VNI->isUnused()) { 1320 if (unused) 1321 EqClass.join(unused->id, VNI->id); 1322 unused = VNI; 1323 continue; 1324 } 1325 used = VNI; 1326 if (VNI->isPHIDef()) { 1327 const MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def); 1328 assert(MBB && "Phi-def has no defining MBB"); 1329 // Connect to values live out of predecessors. 1330 for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 1331 PE = MBB->pred_end(); PI != PE; ++PI) 1332 if (const VNInfo *PVNI = LR.getVNInfoBefore(LIS.getMBBEndIdx(*PI))) 1333 EqClass.join(VNI->id, PVNI->id); 1334 } else { 1335 // Normal value defined by an instruction. Check for two-addr redef. 1336 // FIXME: This could be coincidental. Should we really check for a tied 1337 // operand constraint? 1338 // Note that VNI->def may be a use slot for an early clobber def. 1339 if (const VNInfo *UVNI = LR.getVNInfoBefore(VNI->def)) 1340 EqClass.join(VNI->id, UVNI->id); 1341 } 1342 } 1343 1344 // Lump all the unused values in with the last used value. 1345 if (used && unused) 1346 EqClass.join(used->id, unused->id); 1347 1348 EqClass.compress(); 1349 return EqClass.getNumClasses(); 1350 } 1351 1352 void ConnectedVNInfoEqClasses::Distribute(LiveInterval &LI, LiveInterval *LIV[], 1353 MachineRegisterInfo &MRI) { 1354 // Rewrite instructions. 1355 for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(LI.reg), 1356 RE = MRI.reg_end(); RI != RE;) { 1357 MachineOperand &MO = *RI; 1358 MachineInstr *MI = RI->getParent(); 1359 ++RI; 1360 const VNInfo *VNI; 1361 if (MI->isDebugValue()) { 1362 // DBG_VALUE instructions don't have slot indexes, so get the index of 1363 // the instruction before them. The value is defined there too. 1364 SlotIndex Idx = LIS.getSlotIndexes()->getIndexBefore(*MI); 1365 VNI = LI.Query(Idx).valueOut(); 1366 } else { 1367 SlotIndex Idx = LIS.getInstructionIndex(*MI); 1368 LiveQueryResult LRQ = LI.Query(Idx); 1369 VNI = MO.readsReg() ? LRQ.valueIn() : LRQ.valueDefined(); 1370 } 1371 // In the case of an <undef> use that isn't tied to any def, VNI will be 1372 // NULL. If the use is tied to a def, VNI will be the defined value. 1373 if (!VNI) 1374 continue; 1375 if (unsigned EqClass = getEqClass(VNI)) 1376 MO.setReg(LIV[EqClass-1]->reg); 1377 } 1378 1379 // Distribute subregister liveranges. 1380 if (LI.hasSubRanges()) { 1381 unsigned NumComponents = EqClass.getNumClasses(); 1382 SmallVector<unsigned, 8> VNIMapping; 1383 SmallVector<LiveInterval::SubRange*, 8> SubRanges; 1384 BumpPtrAllocator &Allocator = LIS.getVNInfoAllocator(); 1385 for (LiveInterval::SubRange &SR : LI.subranges()) { 1386 // Create new subranges in the split intervals and construct a mapping 1387 // for the VNInfos in the subrange. 1388 unsigned NumValNos = SR.valnos.size(); 1389 VNIMapping.clear(); 1390 VNIMapping.reserve(NumValNos); 1391 SubRanges.clear(); 1392 SubRanges.resize(NumComponents-1, nullptr); 1393 for (unsigned I = 0; I < NumValNos; ++I) { 1394 const VNInfo &VNI = *SR.valnos[I]; 1395 unsigned ComponentNum; 1396 if (VNI.isUnused()) { 1397 ComponentNum = 0; 1398 } else { 1399 const VNInfo *MainRangeVNI = LI.getVNInfoAt(VNI.def); 1400 assert(MainRangeVNI != nullptr 1401 && "SubRange def must have corresponding main range def"); 1402 ComponentNum = getEqClass(MainRangeVNI); 1403 if (ComponentNum > 0 && SubRanges[ComponentNum-1] == nullptr) { 1404 SubRanges[ComponentNum-1] 1405 = LIV[ComponentNum-1]->createSubRange(Allocator, SR.LaneMask); 1406 } 1407 } 1408 VNIMapping.push_back(ComponentNum); 1409 } 1410 DistributeRange(SR, SubRanges.data(), VNIMapping); 1411 } 1412 LI.removeEmptySubRanges(); 1413 } 1414 1415 // Distribute main liverange. 1416 DistributeRange(LI, LIV, EqClass); 1417 } 1418