LiveInterval.cpp revision e585e75612ef5fd32e2bb2c9f635496791a20f8b
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 interval 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 intervals can have holes, 15// i.e. an interval might look like [1,20), [50,65), [1000,1001). Each 16// individual range is represented as an instance of LiveRange, and the whole 17// interval is represented as an instance of LiveInterval. 18// 19//===----------------------------------------------------------------------===// 20 21#include "llvm/CodeGen/LiveInterval.h" 22#include "llvm/CodeGen/LiveIntervalAnalysis.h" 23#include "llvm/CodeGen/MachineRegisterInfo.h" 24#include "llvm/ADT/DenseMap.h" 25#include "llvm/ADT/SmallSet.h" 26#include "llvm/ADT/STLExtras.h" 27#include "llvm/Support/Debug.h" 28#include "llvm/Support/raw_ostream.h" 29#include "llvm/Target/TargetRegisterInfo.h" 30#include <algorithm> 31using namespace llvm; 32 33LiveInterval::iterator LiveInterval::find(SlotIndex Pos) { 34 // This algorithm is basically std::upper_bound. 35 // Unfortunately, std::upper_bound cannot be used with mixed types until we 36 // adopt C++0x. Many libraries can do it, but not all. 37 if (empty() || Pos >= endIndex()) 38 return end(); 39 iterator I = begin(); 40 size_t Len = ranges.size(); 41 do { 42 size_t Mid = Len >> 1; 43 if (Pos < I[Mid].end) 44 Len = Mid; 45 else 46 I += Mid + 1, Len -= Mid + 1; 47 } while (Len); 48 return I; 49} 50 51VNInfo *LiveInterval::createDeadDef(SlotIndex Def, 52 VNInfo::Allocator &VNInfoAllocator) { 53 assert(!Def.isDead() && "Cannot define a value at the dead slot"); 54 iterator I = find(Def); 55 if (I == end()) { 56 VNInfo *VNI = getNextValue(Def, VNInfoAllocator); 57 ranges.push_back(LiveRange(Def, Def.getDeadSlot(), VNI)); 58 return VNI; 59 } 60 if (SlotIndex::isSameInstr(Def, I->start)) { 61 assert(I->start == Def && "Cannot insert def, already live"); 62 assert(I->valno->def == Def && "Inconsistent existing value def"); 63 return I->valno; 64 } 65 assert(SlotIndex::isEarlierInstr(Def, I->start) && "Already live at def"); 66 VNInfo *VNI = getNextValue(Def, VNInfoAllocator); 67 ranges.insert(I, LiveRange(Def, Def.getDeadSlot(), VNI)); 68 return VNI; 69} 70 71/// killedInRange - Return true if the interval has kills in [Start,End). 72bool LiveInterval::killedInRange(SlotIndex Start, SlotIndex End) const { 73 Ranges::const_iterator r = 74 std::lower_bound(ranges.begin(), ranges.end(), End); 75 76 // Now r points to the first interval with start >= End, or ranges.end(). 77 if (r == ranges.begin()) 78 return false; 79 80 --r; 81 // Now r points to the last interval with end <= End. 82 // r->end is the kill point. 83 return r->end >= Start && r->end < End; 84} 85 86// overlaps - Return true if the intersection of the two live intervals is 87// not empty. 88// 89// An example for overlaps(): 90// 91// 0: A = ... 92// 4: B = ... 93// 8: C = A + B ;; last use of A 94// 95// The live intervals should look like: 96// 97// A = [3, 11) 98// B = [7, x) 99// C = [11, y) 100// 101// A->overlaps(C) should return false since we want to be able to join 102// A and C. 103// 104bool LiveInterval::overlapsFrom(const LiveInterval& other, 105 const_iterator StartPos) const { 106 assert(!empty() && "empty interval"); 107 const_iterator i = begin(); 108 const_iterator ie = end(); 109 const_iterator j = StartPos; 110 const_iterator je = other.end(); 111 112 assert((StartPos->start <= i->start || StartPos == other.begin()) && 113 StartPos != other.end() && "Bogus start position hint!"); 114 115 if (i->start < j->start) { 116 i = std::upper_bound(i, ie, j->start); 117 if (i != ranges.begin()) --i; 118 } else if (j->start < i->start) { 119 ++StartPos; 120 if (StartPos != other.end() && StartPos->start <= i->start) { 121 assert(StartPos < other.end() && i < end()); 122 j = std::upper_bound(j, je, i->start); 123 if (j != other.ranges.begin()) --j; 124 } 125 } else { 126 return true; 127 } 128 129 if (j == je) return false; 130 131 while (i != ie) { 132 if (i->start > j->start) { 133 std::swap(i, j); 134 std::swap(ie, je); 135 } 136 137 if (i->end > j->start) 138 return true; 139 ++i; 140 } 141 142 return false; 143} 144 145/// overlaps - Return true if the live interval overlaps a range specified 146/// by [Start, End). 147bool LiveInterval::overlaps(SlotIndex Start, SlotIndex End) const { 148 assert(Start < End && "Invalid range"); 149 const_iterator I = std::lower_bound(begin(), end(), End); 150 return I != begin() && (--I)->end > Start; 151} 152 153 154/// ValNo is dead, remove it. If it is the largest value number, just nuke it 155/// (and any other deleted values neighboring it), otherwise mark it as ~1U so 156/// it can be nuked later. 157void LiveInterval::markValNoForDeletion(VNInfo *ValNo) { 158 if (ValNo->id == getNumValNums()-1) { 159 do { 160 valnos.pop_back(); 161 } while (!valnos.empty() && valnos.back()->isUnused()); 162 } else { 163 ValNo->setIsUnused(true); 164 } 165} 166 167/// RenumberValues - Renumber all values in order of appearance and delete the 168/// remaining unused values. 169void LiveInterval::RenumberValues(LiveIntervals &lis) { 170 SmallPtrSet<VNInfo*, 8> Seen; 171 valnos.clear(); 172 for (const_iterator I = begin(), E = end(); I != E; ++I) { 173 VNInfo *VNI = I->valno; 174 if (!Seen.insert(VNI)) 175 continue; 176 assert(!VNI->isUnused() && "Unused valno used by live range"); 177 VNI->id = (unsigned)valnos.size(); 178 valnos.push_back(VNI); 179 } 180} 181 182/// extendIntervalEndTo - This method is used when we want to extend the range 183/// specified by I to end at the specified endpoint. To do this, we should 184/// merge and eliminate all ranges that this will overlap with. The iterator is 185/// not invalidated. 186void LiveInterval::extendIntervalEndTo(Ranges::iterator I, SlotIndex NewEnd) { 187 assert(I != ranges.end() && "Not a valid interval!"); 188 VNInfo *ValNo = I->valno; 189 190 // Search for the first interval that we can't merge with. 191 Ranges::iterator MergeTo = llvm::next(I); 192 for (; MergeTo != ranges.end() && NewEnd >= MergeTo->end; ++MergeTo) { 193 assert(MergeTo->valno == ValNo && "Cannot merge with differing values!"); 194 } 195 196 // If NewEnd was in the middle of an interval, make sure to get its endpoint. 197 I->end = std::max(NewEnd, prior(MergeTo)->end); 198 199 // If the newly formed range now touches the range after it and if they have 200 // the same value number, merge the two ranges into one range. 201 if (MergeTo != ranges.end() && MergeTo->start <= I->end && 202 MergeTo->valno == ValNo) { 203 I->end = MergeTo->end; 204 ++MergeTo; 205 } 206 207 // Erase any dead ranges. 208 ranges.erase(llvm::next(I), MergeTo); 209} 210 211 212/// extendIntervalStartTo - This method is used when we want to extend the range 213/// specified by I to start at the specified endpoint. To do this, we should 214/// merge and eliminate all ranges that this will overlap with. 215LiveInterval::Ranges::iterator 216LiveInterval::extendIntervalStartTo(Ranges::iterator I, SlotIndex NewStart) { 217 assert(I != ranges.end() && "Not a valid interval!"); 218 VNInfo *ValNo = I->valno; 219 220 // Search for the first interval that we can't merge with. 221 Ranges::iterator MergeTo = I; 222 do { 223 if (MergeTo == ranges.begin()) { 224 I->start = NewStart; 225 ranges.erase(MergeTo, I); 226 return I; 227 } 228 assert(MergeTo->valno == ValNo && "Cannot merge with differing values!"); 229 --MergeTo; 230 } while (NewStart <= MergeTo->start); 231 232 // If we start in the middle of another interval, just delete a range and 233 // extend that interval. 234 if (MergeTo->end >= NewStart && MergeTo->valno == ValNo) { 235 MergeTo->end = I->end; 236 } else { 237 // Otherwise, extend the interval right after. 238 ++MergeTo; 239 MergeTo->start = NewStart; 240 MergeTo->end = I->end; 241 } 242 243 ranges.erase(llvm::next(MergeTo), llvm::next(I)); 244 return MergeTo; 245} 246 247LiveInterval::iterator 248LiveInterval::addRangeFrom(LiveRange LR, iterator From) { 249 SlotIndex Start = LR.start, End = LR.end; 250 iterator it = std::upper_bound(From, ranges.end(), Start); 251 252 // If the inserted interval starts in the middle or right at the end of 253 // another interval, just extend that interval to contain the range of LR. 254 if (it != ranges.begin()) { 255 iterator B = prior(it); 256 if (LR.valno == B->valno) { 257 if (B->start <= Start && B->end >= Start) { 258 extendIntervalEndTo(B, End); 259 return B; 260 } 261 } else { 262 // Check to make sure that we are not overlapping two live ranges with 263 // different valno's. 264 assert(B->end <= Start && 265 "Cannot overlap two LiveRanges with differing ValID's" 266 " (did you def the same reg twice in a MachineInstr?)"); 267 } 268 } 269 270 // Otherwise, if this range ends in the middle of, or right next to, another 271 // interval, merge it into that interval. 272 if (it != ranges.end()) { 273 if (LR.valno == it->valno) { 274 if (it->start <= End) { 275 it = extendIntervalStartTo(it, Start); 276 277 // If LR is a complete superset of an interval, we may need to grow its 278 // endpoint as well. 279 if (End > it->end) 280 extendIntervalEndTo(it, End); 281 return it; 282 } 283 } else { 284 // Check to make sure that we are not overlapping two live ranges with 285 // different valno's. 286 assert(it->start >= End && 287 "Cannot overlap two LiveRanges with differing ValID's"); 288 } 289 } 290 291 // Otherwise, this is just a new range that doesn't interact with anything. 292 // Insert it. 293 return ranges.insert(it, LR); 294} 295 296/// extendInBlock - If this interval is live before Kill in the basic 297/// block that starts at StartIdx, extend it to be live up to Kill and return 298/// the value. If there is no live range before Kill, return NULL. 299VNInfo *LiveInterval::extendInBlock(SlotIndex StartIdx, SlotIndex Kill) { 300 if (empty()) 301 return 0; 302 iterator I = std::upper_bound(begin(), end(), Kill.getPrevSlot()); 303 if (I == begin()) 304 return 0; 305 --I; 306 if (I->end <= StartIdx) 307 return 0; 308 if (I->end < Kill) 309 extendIntervalEndTo(I, Kill); 310 return I->valno; 311} 312 313/// removeRange - Remove the specified range from this interval. Note that 314/// the range must be in a single LiveRange in its entirety. 315void LiveInterval::removeRange(SlotIndex Start, SlotIndex End, 316 bool RemoveDeadValNo) { 317 // Find the LiveRange containing this span. 318 Ranges::iterator I = find(Start); 319 assert(I != ranges.end() && "Range is not in interval!"); 320 assert(I->containsRange(Start, End) && "Range is not entirely in interval!"); 321 322 // If the span we are removing is at the start of the LiveRange, adjust it. 323 VNInfo *ValNo = I->valno; 324 if (I->start == Start) { 325 if (I->end == End) { 326 if (RemoveDeadValNo) { 327 // Check if val# is dead. 328 bool isDead = true; 329 for (const_iterator II = begin(), EE = end(); II != EE; ++II) 330 if (II != I && II->valno == ValNo) { 331 isDead = false; 332 break; 333 } 334 if (isDead) { 335 // Now that ValNo is dead, remove it. 336 markValNoForDeletion(ValNo); 337 } 338 } 339 340 ranges.erase(I); // Removed the whole LiveRange. 341 } else 342 I->start = End; 343 return; 344 } 345 346 // Otherwise if the span we are removing is at the end of the LiveRange, 347 // adjust the other way. 348 if (I->end == End) { 349 I->end = Start; 350 return; 351 } 352 353 // Otherwise, we are splitting the LiveRange into two pieces. 354 SlotIndex OldEnd = I->end; 355 I->end = Start; // Trim the old interval. 356 357 // Insert the new one. 358 ranges.insert(llvm::next(I), LiveRange(End, OldEnd, ValNo)); 359} 360 361/// removeValNo - Remove all the ranges defined by the specified value#. 362/// Also remove the value# from value# list. 363void LiveInterval::removeValNo(VNInfo *ValNo) { 364 if (empty()) return; 365 Ranges::iterator I = ranges.end(); 366 Ranges::iterator E = ranges.begin(); 367 do { 368 --I; 369 if (I->valno == ValNo) 370 ranges.erase(I); 371 } while (I != E); 372 // Now that ValNo is dead, remove it. 373 markValNoForDeletion(ValNo); 374} 375 376/// join - Join two live intervals (this, and other) together. This applies 377/// mappings to the value numbers in the LHS/RHS intervals as specified. If 378/// the intervals are not joinable, this aborts. 379void LiveInterval::join(LiveInterval &Other, 380 const int *LHSValNoAssignments, 381 const int *RHSValNoAssignments, 382 SmallVector<VNInfo*, 16> &NewVNInfo, 383 MachineRegisterInfo *MRI) { 384 verify(); 385 386 // Determine if any of our live range values are mapped. This is uncommon, so 387 // we want to avoid the interval scan if not. 388 bool MustMapCurValNos = false; 389 unsigned NumVals = getNumValNums(); 390 unsigned NumNewVals = NewVNInfo.size(); 391 for (unsigned i = 0; i != NumVals; ++i) { 392 unsigned LHSValID = LHSValNoAssignments[i]; 393 if (i != LHSValID || 394 (NewVNInfo[LHSValID] && NewVNInfo[LHSValID] != getValNumInfo(i))) { 395 MustMapCurValNos = true; 396 break; 397 } 398 } 399 400 // If we have to apply a mapping to our base interval assignment, rewrite it 401 // now. 402 if (MustMapCurValNos) { 403 // Map the first live range. 404 405 iterator OutIt = begin(); 406 OutIt->valno = NewVNInfo[LHSValNoAssignments[OutIt->valno->id]]; 407 for (iterator I = next(OutIt), E = end(); I != E; ++I) { 408 VNInfo* nextValNo = NewVNInfo[LHSValNoAssignments[I->valno->id]]; 409 assert(nextValNo != 0 && "Huh?"); 410 411 // If this live range has the same value # as its immediate predecessor, 412 // and if they are neighbors, remove one LiveRange. This happens when we 413 // have [0,4:0)[4,7:1) and map 0/1 onto the same value #. 414 if (OutIt->valno == nextValNo && OutIt->end == I->start) { 415 OutIt->end = I->end; 416 } else { 417 // Didn't merge. Move OutIt to the next interval, 418 ++OutIt; 419 OutIt->valno = nextValNo; 420 if (OutIt != I) { 421 OutIt->start = I->start; 422 OutIt->end = I->end; 423 } 424 } 425 } 426 // If we merge some live ranges, chop off the end. 427 ++OutIt; 428 ranges.erase(OutIt, end()); 429 } 430 431 // Remember assignements because val# ids are changing. 432 SmallVector<unsigned, 16> OtherAssignments; 433 for (iterator I = Other.begin(), E = Other.end(); I != E; ++I) 434 OtherAssignments.push_back(RHSValNoAssignments[I->valno->id]); 435 436 // Update val# info. Renumber them and make sure they all belong to this 437 // LiveInterval now. Also remove dead val#'s. 438 unsigned NumValNos = 0; 439 for (unsigned i = 0; i < NumNewVals; ++i) { 440 VNInfo *VNI = NewVNInfo[i]; 441 if (VNI) { 442 if (NumValNos >= NumVals) 443 valnos.push_back(VNI); 444 else 445 valnos[NumValNos] = VNI; 446 VNI->id = NumValNos++; // Renumber val#. 447 } 448 } 449 if (NumNewVals < NumVals) 450 valnos.resize(NumNewVals); // shrinkify 451 452 // Okay, now insert the RHS live ranges into the LHS. 453 iterator InsertPos = begin(); 454 unsigned RangeNo = 0; 455 for (iterator I = Other.begin(), E = Other.end(); I != E; ++I, ++RangeNo) { 456 // Map the valno in the other live range to the current live range. 457 I->valno = NewVNInfo[OtherAssignments[RangeNo]]; 458 assert(I->valno && "Adding a dead range?"); 459 InsertPos = addRangeFrom(*I, InsertPos); 460 } 461 462 verify(); 463} 464 465/// \brief Helper function for merging in another LiveInterval's ranges. 466/// 467/// This is a helper routine implementing an efficient merge of another 468/// LiveIntervals ranges into the current interval. 469/// 470/// \param LHSValNo Set as the new value number for every range from RHS which 471/// is merged into the LHS. 472/// \param RHSValNo If non-NULL, then only ranges in RHS whose original value 473/// number maches this value number will be merged into LHS. 474void LiveInterval::mergeIntervalRanges(const LiveInterval &RHS, 475 VNInfo *LHSValNo, 476 const VNInfo *RHSValNo) { 477 if (RHS.empty()) 478 return; 479 480 // Ensure we're starting with valid ranges. 481 verify(); 482 RHS.verify(); 483 484 // The strategy for merging these efficiently is as follows: 485 // 486 // 1) Find the beginning of the impacted ranges in the LHS. 487 // 2) Create a new, merged sub-squence of ranges merging from the position in 488 // #1 until either LHS or RHS is exhausted. Any part of LHS between RHS 489 // entries being merged will be copied into this new range. 490 // 3) Replace the relevant section in LHS with these newly merged ranges. 491 // 4) Append any remaning ranges from RHS if LHS is exhausted in #2. 492 // 493 // We don't follow the typical in-place merge strategy for sorted ranges of 494 // appending the new ranges to the back and then using std::inplace_merge 495 // because one step of the merge can both mutate the original elements and 496 // remove elements from the original. Essentially, because the merge includes 497 // collapsing overlapping ranges, a more complex approach is required. 498 499 // We do an initial binary search to optimize for a common pattern: a large 500 // LHS, and a very small RHS. 501 const_iterator RI = RHS.begin(), RE = RHS.end(); 502 iterator LE = end(), LI = std::upper_bound(begin(), LE, *RI); 503 504 // Merge into NewRanges until one of the ranges is exhausted. 505 SmallVector<LiveRange, 4> NewRanges; 506 507 // Keep track of where to begin the replacement. 508 iterator ReplaceI = LI; 509 510 // If there are preceding ranges in the LHS, put the last one into NewRanges 511 // so we can optionally extend it. Adjust the replacement point accordingly. 512 if (LI != begin()) { 513 ReplaceI = llvm::prior(LI); 514 NewRanges.push_back(*ReplaceI); 515 } 516 517 // Now loop over the mergable portions of both LHS and RHS, merging into 518 // NewRanges. 519 while (LI != LE && RI != RE) { 520 // Skip incoming ranges with the wrong value. 521 if (RHSValNo && RI->valno != RHSValNo) { 522 ++RI; 523 continue; 524 } 525 526 // Select the first range. We pick the earliest start point, and then the 527 // largest range. 528 LiveRange R = *LI; 529 if (*RI < R) { 530 R = *RI; 531 ++RI; 532 R.valno = LHSValNo; 533 } else { 534 ++LI; 535 } 536 537 if (NewRanges.empty()) { 538 NewRanges.push_back(R); 539 continue; 540 } 541 542 LiveRange &LastR = NewRanges.back(); 543 if (R.valno == LastR.valno) { 544 // Try to merge this range into the last one. 545 if (R.start <= LastR.end) { 546 LastR.end = std::max(LastR.end, R.end); 547 continue; 548 } 549 } else { 550 // We can't merge ranges across a value number. 551 assert(R.start >= LastR.end && 552 "Cannot overlap two LiveRanges with differing ValID's"); 553 } 554 555 // If all else fails, just append the range. 556 NewRanges.push_back(R); 557 } 558 assert(RI == RE || LI == LE); 559 560 // Check for being able to merge into the trailing sequence of ranges on the LHS. 561 if (!NewRanges.empty()) 562 for (; LI != LE && (LI->valno == NewRanges.back().valno && 563 LI->start <= NewRanges.back().end); 564 ++LI) 565 NewRanges.back().end = std::max(NewRanges.back().end, LI->end); 566 567 // Replace the ranges in the LHS with the newly merged ones. It would be 568 // really nice if there were a move-supporting 'replace' directly in 569 // SmallVector, but as there is not, we pay the price of copies to avoid 570 // wasted memory allocations. 571 SmallVectorImpl<LiveRange>::iterator NRI = NewRanges.begin(), 572 NRE = NewRanges.end(); 573 for (; ReplaceI != LI && NRI != NRE; ++ReplaceI, ++NRI) 574 *ReplaceI = *NRI; 575 if (NRI == NRE) 576 ranges.erase(ReplaceI, LI); 577 else 578 ranges.insert(LI, NRI, NRE); 579 580 // And finally insert any trailing end of RHS (if we have one). 581 for (; RI != RE; ++RI) 582 if (ranges.back().valno == LHSValNo && RI->start <= ranges.back().end) { 583 ranges.back().end = std::max(ranges.back().end, RI->end); 584 } else { 585 ranges.push_back(*RI); 586 ranges.back().valno = LHSValNo; 587 } 588 589 // Ensure we finished with a valid new sequence of ranges. 590 verify(); 591} 592 593/// MergeRangesInAsValue - Merge all of the intervals in RHS into this live 594/// interval as the specified value number. The LiveRanges in RHS are 595/// allowed to overlap with LiveRanges in the current interval, but only if 596/// the overlapping LiveRanges have the specified value number. 597void LiveInterval::MergeRangesInAsValue(const LiveInterval &RHS, 598 VNInfo *LHSValNo) { 599 mergeIntervalRanges(RHS, LHSValNo); 600} 601 602/// MergeValueInAsValue - Merge all of the live ranges of a specific val# 603/// in RHS into this live interval as the specified value number. 604/// The LiveRanges in RHS are allowed to overlap with LiveRanges in the 605/// current interval, it will replace the value numbers of the overlaped 606/// live ranges with the specified value number. 607void LiveInterval::MergeValueInAsValue(const LiveInterval &RHS, 608 const VNInfo *RHSValNo, 609 VNInfo *LHSValNo) { 610 mergeIntervalRanges(RHS, LHSValNo, RHSValNo); 611} 612 613/// MergeValueNumberInto - This method is called when two value nubmers 614/// are found to be equivalent. This eliminates V1, replacing all 615/// LiveRanges with the V1 value number with the V2 value number. This can 616/// cause merging of V1/V2 values numbers and compaction of the value space. 617VNInfo* LiveInterval::MergeValueNumberInto(VNInfo *V1, VNInfo *V2) { 618 assert(V1 != V2 && "Identical value#'s are always equivalent!"); 619 620 // This code actually merges the (numerically) larger value number into the 621 // smaller value number, which is likely to allow us to compactify the value 622 // space. The only thing we have to be careful of is to preserve the 623 // instruction that defines the result value. 624 625 // Make sure V2 is smaller than V1. 626 if (V1->id < V2->id) { 627 V1->copyFrom(*V2); 628 std::swap(V1, V2); 629 } 630 631 // Merge V1 live ranges into V2. 632 for (iterator I = begin(); I != end(); ) { 633 iterator LR = I++; 634 if (LR->valno != V1) continue; // Not a V1 LiveRange. 635 636 // Okay, we found a V1 live range. If it had a previous, touching, V2 live 637 // range, extend it. 638 if (LR != begin()) { 639 iterator Prev = LR-1; 640 if (Prev->valno == V2 && Prev->end == LR->start) { 641 Prev->end = LR->end; 642 643 // Erase this live-range. 644 ranges.erase(LR); 645 I = Prev+1; 646 LR = Prev; 647 } 648 } 649 650 // Okay, now we have a V1 or V2 live range that is maximally merged forward. 651 // Ensure that it is a V2 live-range. 652 LR->valno = V2; 653 654 // If we can merge it into later V2 live ranges, do so now. We ignore any 655 // following V1 live ranges, as they will be merged in subsequent iterations 656 // of the loop. 657 if (I != end()) { 658 if (I->start == LR->end && I->valno == V2) { 659 LR->end = I->end; 660 ranges.erase(I); 661 I = LR+1; 662 } 663 } 664 } 665 666 // Merge the relevant flags. 667 V2->mergeFlags(V1); 668 669 // Now that V1 is dead, remove it. 670 markValNoForDeletion(V1); 671 672 return V2; 673} 674 675void LiveInterval::Copy(const LiveInterval &RHS, 676 MachineRegisterInfo *MRI, 677 VNInfo::Allocator &VNInfoAllocator) { 678 ranges.clear(); 679 valnos.clear(); 680 std::pair<unsigned, unsigned> Hint = MRI->getRegAllocationHint(RHS.reg); 681 MRI->setRegAllocationHint(reg, Hint.first, Hint.second); 682 683 weight = RHS.weight; 684 for (unsigned i = 0, e = RHS.getNumValNums(); i != e; ++i) { 685 const VNInfo *VNI = RHS.getValNumInfo(i); 686 createValueCopy(VNI, VNInfoAllocator); 687 } 688 for (unsigned i = 0, e = RHS.ranges.size(); i != e; ++i) { 689 const LiveRange &LR = RHS.ranges[i]; 690 addRange(LiveRange(LR.start, LR.end, getValNumInfo(LR.valno->id))); 691 } 692 693 verify(); 694} 695 696unsigned LiveInterval::getSize() const { 697 unsigned Sum = 0; 698 for (const_iterator I = begin(), E = end(); I != E; ++I) 699 Sum += I->start.distance(I->end); 700 return Sum; 701} 702 703raw_ostream& llvm::operator<<(raw_ostream& os, const LiveRange &LR) { 704 return os << '[' << LR.start << ',' << LR.end << ':' << LR.valno->id << ")"; 705} 706 707void LiveRange::dump() const { 708 dbgs() << *this << "\n"; 709} 710 711void LiveInterval::print(raw_ostream &OS) const { 712 if (empty()) 713 OS << "EMPTY"; 714 else { 715 for (LiveInterval::Ranges::const_iterator I = ranges.begin(), 716 E = ranges.end(); I != E; ++I) { 717 OS << *I; 718 assert(I->valno == getValNumInfo(I->valno->id) && "Bad VNInfo"); 719 } 720 } 721 722 // Print value number info. 723 if (getNumValNums()) { 724 OS << " "; 725 unsigned vnum = 0; 726 for (const_vni_iterator i = vni_begin(), e = vni_end(); i != e; 727 ++i, ++vnum) { 728 const VNInfo *vni = *i; 729 if (vnum) OS << " "; 730 OS << vnum << "@"; 731 if (vni->isUnused()) { 732 OS << "x"; 733 } else { 734 OS << vni->def; 735 if (vni->isPHIDef()) 736 OS << "-phidef"; 737 if (vni->hasPHIKill()) 738 OS << "-phikill"; 739 } 740 } 741 } 742} 743 744void LiveInterval::dump() const { 745 dbgs() << *this << "\n"; 746} 747 748#ifndef NDEBUG 749void LiveInterval::verify() const { 750 for (const_iterator I = begin(), E = end(); I != E; ++I) { 751 assert(I->start.isValid()); 752 assert(I->end.isValid()); 753 assert(I->start < I->end); 754 assert(I->valno != 0); 755 assert(I->valno == valnos[I->valno->id]); 756 if (llvm::next(I) != E) { 757 assert(I->end <= llvm::next(I)->start); 758 if (I->end == llvm::next(I)->start) 759 assert(I->valno != llvm::next(I)->valno); 760 } 761 } 762} 763#endif 764 765 766void LiveRange::print(raw_ostream &os) const { 767 os << *this; 768} 769 770unsigned ConnectedVNInfoEqClasses::Classify(const LiveInterval *LI) { 771 // Create initial equivalence classes. 772 EqClass.clear(); 773 EqClass.grow(LI->getNumValNums()); 774 775 const VNInfo *used = 0, *unused = 0; 776 777 // Determine connections. 778 for (LiveInterval::const_vni_iterator I = LI->vni_begin(), E = LI->vni_end(); 779 I != E; ++I) { 780 const VNInfo *VNI = *I; 781 // Group all unused values into one class. 782 if (VNI->isUnused()) { 783 if (unused) 784 EqClass.join(unused->id, VNI->id); 785 unused = VNI; 786 continue; 787 } 788 used = VNI; 789 if (VNI->isPHIDef()) { 790 const MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def); 791 assert(MBB && "Phi-def has no defining MBB"); 792 // Connect to values live out of predecessors. 793 for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 794 PE = MBB->pred_end(); PI != PE; ++PI) 795 if (const VNInfo *PVNI = LI->getVNInfoBefore(LIS.getMBBEndIdx(*PI))) 796 EqClass.join(VNI->id, PVNI->id); 797 } else { 798 // Normal value defined by an instruction. Check for two-addr redef. 799 // FIXME: This could be coincidental. Should we really check for a tied 800 // operand constraint? 801 // Note that VNI->def may be a use slot for an early clobber def. 802 if (const VNInfo *UVNI = LI->getVNInfoBefore(VNI->def)) 803 EqClass.join(VNI->id, UVNI->id); 804 } 805 } 806 807 // Lump all the unused values in with the last used value. 808 if (used && unused) 809 EqClass.join(used->id, unused->id); 810 811 EqClass.compress(); 812 return EqClass.getNumClasses(); 813} 814 815void ConnectedVNInfoEqClasses::Distribute(LiveInterval *LIV[], 816 MachineRegisterInfo &MRI) { 817 assert(LIV[0] && "LIV[0] must be set"); 818 LiveInterval &LI = *LIV[0]; 819 820 // Rewrite instructions. 821 for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(LI.reg), 822 RE = MRI.reg_end(); RI != RE;) { 823 MachineOperand &MO = RI.getOperand(); 824 MachineInstr *MI = MO.getParent(); 825 ++RI; 826 if (MO.isUse() && MO.isUndef()) 827 continue; 828 // DBG_VALUE instructions should have been eliminated earlier. 829 SlotIndex Idx = LIS.getInstructionIndex(MI); 830 Idx = Idx.getRegSlot(MO.isUse()); 831 const VNInfo *VNI = LI.getVNInfoAt(Idx); 832 // FIXME: We should be able to assert(VNI) here, but the coalescer leaves 833 // dangling defs around. 834 if (!VNI) 835 continue; 836 MO.setReg(LIV[getEqClass(VNI)]->reg); 837 } 838 839 // Move runs to new intervals. 840 LiveInterval::iterator J = LI.begin(), E = LI.end(); 841 while (J != E && EqClass[J->valno->id] == 0) 842 ++J; 843 for (LiveInterval::iterator I = J; I != E; ++I) { 844 if (unsigned eq = EqClass[I->valno->id]) { 845 assert((LIV[eq]->empty() || LIV[eq]->expiredAt(I->start)) && 846 "New intervals should be empty"); 847 LIV[eq]->ranges.push_back(*I); 848 } else 849 *J++ = *I; 850 } 851 LI.ranges.erase(J, E); 852 853 // Transfer VNInfos to their new owners and renumber them. 854 unsigned j = 0, e = LI.getNumValNums(); 855 while (j != e && EqClass[j] == 0) 856 ++j; 857 for (unsigned i = j; i != e; ++i) { 858 VNInfo *VNI = LI.getValNumInfo(i); 859 if (unsigned eq = EqClass[i]) { 860 VNI->id = LIV[eq]->getNumValNums(); 861 LIV[eq]->valnos.push_back(VNI); 862 } else { 863 VNI->id = j; 864 LI.valnos[j++] = VNI; 865 } 866 } 867 LI.valnos.resize(j); 868} 869