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