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