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