LiveInterval.cpp revision bd6f44a3a2a1404721bcbb67edf92b8480a3e655
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 51/// killedInRange - Return true if the interval has kills in [Start,End). 52bool LiveInterval::killedInRange(SlotIndex Start, SlotIndex End) const { 53 Ranges::const_iterator r = 54 std::lower_bound(ranges.begin(), ranges.end(), End); 55 56 // Now r points to the first interval with start >= End, or ranges.end(). 57 if (r == ranges.begin()) 58 return false; 59 60 --r; 61 // Now r points to the last interval with end <= End. 62 // r->end is the kill point. 63 return r->end >= Start && r->end < End; 64} 65 66// overlaps - Return true if the intersection of the two live intervals is 67// not empty. 68// 69// An example for overlaps(): 70// 71// 0: A = ... 72// 4: B = ... 73// 8: C = A + B ;; last use of A 74// 75// The live intervals should look like: 76// 77// A = [3, 11) 78// B = [7, x) 79// C = [11, y) 80// 81// A->overlaps(C) should return false since we want to be able to join 82// A and C. 83// 84bool LiveInterval::overlapsFrom(const LiveInterval& other, 85 const_iterator StartPos) const { 86 assert(!empty() && "empty interval"); 87 const_iterator i = begin(); 88 const_iterator ie = end(); 89 const_iterator j = StartPos; 90 const_iterator je = other.end(); 91 92 assert((StartPos->start <= i->start || StartPos == other.begin()) && 93 StartPos != other.end() && "Bogus start position hint!"); 94 95 if (i->start < j->start) { 96 i = std::upper_bound(i, ie, j->start); 97 if (i != ranges.begin()) --i; 98 } else if (j->start < i->start) { 99 ++StartPos; 100 if (StartPos != other.end() && StartPos->start <= i->start) { 101 assert(StartPos < other.end() && i < end()); 102 j = std::upper_bound(j, je, i->start); 103 if (j != other.ranges.begin()) --j; 104 } 105 } else { 106 return true; 107 } 108 109 if (j == je) return false; 110 111 while (i != ie) { 112 if (i->start > j->start) { 113 std::swap(i, j); 114 std::swap(ie, je); 115 } 116 117 if (i->end > j->start) 118 return true; 119 ++i; 120 } 121 122 return false; 123} 124 125/// overlaps - Return true if the live interval overlaps a range specified 126/// by [Start, End). 127bool LiveInterval::overlaps(SlotIndex Start, SlotIndex End) const { 128 assert(Start < End && "Invalid range"); 129 const_iterator I = std::lower_bound(begin(), end(), End); 130 return I != begin() && (--I)->end > Start; 131} 132 133 134/// ValNo is dead, remove it. If it is the largest value number, just nuke it 135/// (and any other deleted values neighboring it), otherwise mark it as ~1U so 136/// it can be nuked later. 137void LiveInterval::markValNoForDeletion(VNInfo *ValNo) { 138 if (ValNo->id == getNumValNums()-1) { 139 do { 140 valnos.pop_back(); 141 } while (!valnos.empty() && valnos.back()->isUnused()); 142 } else { 143 ValNo->setIsUnused(true); 144 } 145} 146 147/// RenumberValues - Renumber all values in order of appearance and delete the 148/// remaining unused values. 149void LiveInterval::RenumberValues(LiveIntervals &lis) { 150 SmallPtrSet<VNInfo*, 8> Seen; 151 valnos.clear(); 152 for (const_iterator I = begin(), E = end(); I != E; ++I) { 153 VNInfo *VNI = I->valno; 154 if (!Seen.insert(VNI)) 155 continue; 156 assert(!VNI->isUnused() && "Unused valno used by live range"); 157 VNI->id = (unsigned)valnos.size(); 158 valnos.push_back(VNI); 159 } 160} 161 162/// extendIntervalEndTo - This method is used when we want to extend the range 163/// specified by I to end at the specified endpoint. To do this, we should 164/// merge and eliminate all ranges that this will overlap with. The iterator is 165/// not invalidated. 166void LiveInterval::extendIntervalEndTo(Ranges::iterator I, SlotIndex NewEnd) { 167 assert(I != ranges.end() && "Not a valid interval!"); 168 VNInfo *ValNo = I->valno; 169 170 // Search for the first interval that we can't merge with. 171 Ranges::iterator MergeTo = llvm::next(I); 172 for (; MergeTo != ranges.end() && NewEnd >= MergeTo->end; ++MergeTo) { 173 assert(MergeTo->valno == ValNo && "Cannot merge with differing values!"); 174 } 175 176 // If NewEnd was in the middle of an interval, make sure to get its endpoint. 177 I->end = std::max(NewEnd, prior(MergeTo)->end); 178 179 // Erase any dead ranges. 180 ranges.erase(llvm::next(I), MergeTo); 181 182 // If the newly formed range now touches the range after it and if they have 183 // the same value number, merge the two ranges into one range. 184 Ranges::iterator Next = llvm::next(I); 185 if (Next != ranges.end() && Next->start <= I->end && Next->valno == ValNo) { 186 I->end = Next->end; 187 ranges.erase(Next); 188 } 189} 190 191 192/// extendIntervalStartTo - This method is used when we want to extend the range 193/// specified by I to start at the specified endpoint. To do this, we should 194/// merge and eliminate all ranges that this will overlap with. 195LiveInterval::Ranges::iterator 196LiveInterval::extendIntervalStartTo(Ranges::iterator I, SlotIndex NewStart) { 197 assert(I != ranges.end() && "Not a valid interval!"); 198 VNInfo *ValNo = I->valno; 199 200 // Search for the first interval that we can't merge with. 201 Ranges::iterator MergeTo = I; 202 do { 203 if (MergeTo == ranges.begin()) { 204 I->start = NewStart; 205 ranges.erase(MergeTo, I); 206 return I; 207 } 208 assert(MergeTo->valno == ValNo && "Cannot merge with differing values!"); 209 --MergeTo; 210 } while (NewStart <= MergeTo->start); 211 212 // If we start in the middle of another interval, just delete a range and 213 // extend that interval. 214 if (MergeTo->end >= NewStart && MergeTo->valno == ValNo) { 215 MergeTo->end = I->end; 216 } else { 217 // Otherwise, extend the interval right after. 218 ++MergeTo; 219 MergeTo->start = NewStart; 220 MergeTo->end = I->end; 221 } 222 223 ranges.erase(llvm::next(MergeTo), llvm::next(I)); 224 return MergeTo; 225} 226 227LiveInterval::iterator 228LiveInterval::addRangeFrom(LiveRange LR, iterator From) { 229 SlotIndex Start = LR.start, End = LR.end; 230 iterator it = std::upper_bound(From, ranges.end(), Start); 231 232 // If the inserted interval starts in the middle or right at the end of 233 // another interval, just extend that interval to contain the range of LR. 234 if (it != ranges.begin()) { 235 iterator B = prior(it); 236 if (LR.valno == B->valno) { 237 if (B->start <= Start && B->end >= Start) { 238 extendIntervalEndTo(B, End); 239 return B; 240 } 241 } else { 242 // Check to make sure that we are not overlapping two live ranges with 243 // different valno's. 244 assert(B->end <= Start && 245 "Cannot overlap two LiveRanges with differing ValID's" 246 " (did you def the same reg twice in a MachineInstr?)"); 247 } 248 } 249 250 // Otherwise, if this range ends in the middle of, or right next to, another 251 // interval, merge it into that interval. 252 if (it != ranges.end()) { 253 if (LR.valno == it->valno) { 254 if (it->start <= End) { 255 it = extendIntervalStartTo(it, Start); 256 257 // If LR is a complete superset of an interval, we may need to grow its 258 // endpoint as well. 259 if (End > it->end) 260 extendIntervalEndTo(it, End); 261 return it; 262 } 263 } else { 264 // Check to make sure that we are not overlapping two live ranges with 265 // different valno's. 266 assert(it->start >= End && 267 "Cannot overlap two LiveRanges with differing ValID's"); 268 } 269 } 270 271 // Otherwise, this is just a new range that doesn't interact with anything. 272 // Insert it. 273 return ranges.insert(it, LR); 274} 275 276/// extendInBlock - If this interval is live before Kill in the basic 277/// block that starts at StartIdx, extend it to be live up to Kill and return 278/// the value. If there is no live range before Kill, return NULL. 279VNInfo *LiveInterval::extendInBlock(SlotIndex StartIdx, SlotIndex Kill) { 280 if (empty()) 281 return 0; 282 iterator I = std::upper_bound(begin(), end(), Kill.getPrevSlot()); 283 if (I == begin()) 284 return 0; 285 --I; 286 if (I->end <= StartIdx) 287 return 0; 288 if (I->end < Kill) 289 extendIntervalEndTo(I, Kill); 290 return I->valno; 291} 292 293/// removeRange - Remove the specified range from this interval. Note that 294/// the range must be in a single LiveRange in its entirety. 295void LiveInterval::removeRange(SlotIndex Start, SlotIndex End, 296 bool RemoveDeadValNo) { 297 // Find the LiveRange containing this span. 298 Ranges::iterator I = find(Start); 299 assert(I != ranges.end() && "Range is not in interval!"); 300 assert(I->containsRange(Start, End) && "Range is not entirely in interval!"); 301 302 // If the span we are removing is at the start of the LiveRange, adjust it. 303 VNInfo *ValNo = I->valno; 304 if (I->start == Start) { 305 if (I->end == End) { 306 if (RemoveDeadValNo) { 307 // Check if val# is dead. 308 bool isDead = true; 309 for (const_iterator II = begin(), EE = end(); II != EE; ++II) 310 if (II != I && II->valno == ValNo) { 311 isDead = false; 312 break; 313 } 314 if (isDead) { 315 // Now that ValNo is dead, remove it. 316 markValNoForDeletion(ValNo); 317 } 318 } 319 320 ranges.erase(I); // Removed the whole LiveRange. 321 } else 322 I->start = End; 323 return; 324 } 325 326 // Otherwise if the span we are removing is at the end of the LiveRange, 327 // adjust the other way. 328 if (I->end == End) { 329 I->end = Start; 330 return; 331 } 332 333 // Otherwise, we are splitting the LiveRange into two pieces. 334 SlotIndex OldEnd = I->end; 335 I->end = Start; // Trim the old interval. 336 337 // Insert the new one. 338 ranges.insert(llvm::next(I), LiveRange(End, OldEnd, ValNo)); 339} 340 341/// removeValNo - Remove all the ranges defined by the specified value#. 342/// Also remove the value# from value# list. 343void LiveInterval::removeValNo(VNInfo *ValNo) { 344 if (empty()) return; 345 Ranges::iterator I = ranges.end(); 346 Ranges::iterator E = ranges.begin(); 347 do { 348 --I; 349 if (I->valno == ValNo) 350 ranges.erase(I); 351 } while (I != E); 352 // Now that ValNo is dead, remove it. 353 markValNoForDeletion(ValNo); 354} 355 356/// join - Join two live intervals (this, and other) together. This applies 357/// mappings to the value numbers in the LHS/RHS intervals as specified. If 358/// the intervals are not joinable, this aborts. 359void LiveInterval::join(LiveInterval &Other, 360 const int *LHSValNoAssignments, 361 const int *RHSValNoAssignments, 362 SmallVector<VNInfo*, 16> &NewVNInfo, 363 MachineRegisterInfo *MRI) { 364 // Determine if any of our live range values are mapped. This is uncommon, so 365 // we want to avoid the interval scan if not. 366 bool MustMapCurValNos = false; 367 unsigned NumVals = getNumValNums(); 368 unsigned NumNewVals = NewVNInfo.size(); 369 for (unsigned i = 0; i != NumVals; ++i) { 370 unsigned LHSValID = LHSValNoAssignments[i]; 371 if (i != LHSValID || 372 (NewVNInfo[LHSValID] && NewVNInfo[LHSValID] != getValNumInfo(i))) { 373 MustMapCurValNos = true; 374 break; 375 } 376 } 377 378 // If we have to apply a mapping to our base interval assignment, rewrite it 379 // now. 380 if (MustMapCurValNos) { 381 // Map the first live range. 382 383 iterator OutIt = begin(); 384 OutIt->valno = NewVNInfo[LHSValNoAssignments[OutIt->valno->id]]; 385 for (iterator I = next(OutIt), E = end(); I != E; ++I) { 386 VNInfo* nextValNo = NewVNInfo[LHSValNoAssignments[I->valno->id]]; 387 assert(nextValNo != 0 && "Huh?"); 388 389 // If this live range has the same value # as its immediate predecessor, 390 // and if they are neighbors, remove one LiveRange. This happens when we 391 // have [0,4:0)[4,7:1) and map 0/1 onto the same value #. 392 if (OutIt->valno == nextValNo && OutIt->end == I->start) { 393 OutIt->end = I->end; 394 } else { 395 // Didn't merge. Move OutIt to the next interval, 396 ++OutIt; 397 OutIt->valno = nextValNo; 398 if (OutIt != I) { 399 OutIt->start = I->start; 400 OutIt->end = I->end; 401 } 402 } 403 } 404 // If we merge some live ranges, chop off the end. 405 ++OutIt; 406 ranges.erase(OutIt, end()); 407 } 408 409 // Remember assignements because val# ids are changing. 410 SmallVector<unsigned, 16> OtherAssignments; 411 for (iterator I = Other.begin(), E = Other.end(); I != E; ++I) 412 OtherAssignments.push_back(RHSValNoAssignments[I->valno->id]); 413 414 // Update val# info. Renumber them and make sure they all belong to this 415 // LiveInterval now. Also remove dead val#'s. 416 unsigned NumValNos = 0; 417 for (unsigned i = 0; i < NumNewVals; ++i) { 418 VNInfo *VNI = NewVNInfo[i]; 419 if (VNI) { 420 if (NumValNos >= NumVals) 421 valnos.push_back(VNI); 422 else 423 valnos[NumValNos] = VNI; 424 VNI->id = NumValNos++; // Renumber val#. 425 } 426 } 427 if (NumNewVals < NumVals) 428 valnos.resize(NumNewVals); // shrinkify 429 430 // Okay, now insert the RHS live ranges into the LHS. 431 iterator InsertPos = begin(); 432 unsigned RangeNo = 0; 433 for (iterator I = Other.begin(), E = Other.end(); I != E; ++I, ++RangeNo) { 434 // Map the valno in the other live range to the current live range. 435 I->valno = NewVNInfo[OtherAssignments[RangeNo]]; 436 assert(I->valno && "Adding a dead range?"); 437 InsertPos = addRangeFrom(*I, InsertPos); 438 } 439} 440 441/// MergeRangesInAsValue - Merge all of the intervals in RHS into this live 442/// interval as the specified value number. The LiveRanges in RHS are 443/// allowed to overlap with LiveRanges in the current interval, but only if 444/// the overlapping LiveRanges have the specified value number. 445void LiveInterval::MergeRangesInAsValue(const LiveInterval &RHS, 446 VNInfo *LHSValNo) { 447 // TODO: Make this more efficient. 448 iterator InsertPos = begin(); 449 for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) { 450 // Map the valno in the other live range to the current live range. 451 LiveRange Tmp = *I; 452 Tmp.valno = LHSValNo; 453 InsertPos = addRangeFrom(Tmp, InsertPos); 454 } 455} 456 457 458/// MergeValueInAsValue - Merge all of the live ranges of a specific val# 459/// in RHS into this live interval as the specified value number. 460/// The LiveRanges in RHS are allowed to overlap with LiveRanges in the 461/// current interval, it will replace the value numbers of the overlaped 462/// live ranges with the specified value number. 463void LiveInterval::MergeValueInAsValue( 464 const LiveInterval &RHS, 465 const VNInfo *RHSValNo, VNInfo *LHSValNo) { 466 // TODO: Make this more efficient. 467 iterator InsertPos = begin(); 468 for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) { 469 if (I->valno != RHSValNo) 470 continue; 471 // Map the valno in the other live range to the current live range. 472 LiveRange Tmp = *I; 473 Tmp.valno = LHSValNo; 474 InsertPos = addRangeFrom(Tmp, InsertPos); 475 } 476} 477 478 479/// MergeValueNumberInto - This method is called when two value nubmers 480/// are found to be equivalent. This eliminates V1, replacing all 481/// LiveRanges with the V1 value number with the V2 value number. This can 482/// cause merging of V1/V2 values numbers and compaction of the value space. 483VNInfo* LiveInterval::MergeValueNumberInto(VNInfo *V1, VNInfo *V2) { 484 assert(V1 != V2 && "Identical value#'s are always equivalent!"); 485 486 // This code actually merges the (numerically) larger value number into the 487 // smaller value number, which is likely to allow us to compactify the value 488 // space. The only thing we have to be careful of is to preserve the 489 // instruction that defines the result value. 490 491 // Make sure V2 is smaller than V1. 492 if (V1->id < V2->id) { 493 V1->copyFrom(*V2); 494 std::swap(V1, V2); 495 } 496 497 // Merge V1 live ranges into V2. 498 for (iterator I = begin(); I != end(); ) { 499 iterator LR = I++; 500 if (LR->valno != V1) continue; // Not a V1 LiveRange. 501 502 // Okay, we found a V1 live range. If it had a previous, touching, V2 live 503 // range, extend it. 504 if (LR != begin()) { 505 iterator Prev = LR-1; 506 if (Prev->valno == V2 && Prev->end == LR->start) { 507 Prev->end = LR->end; 508 509 // Erase this live-range. 510 ranges.erase(LR); 511 I = Prev+1; 512 LR = Prev; 513 } 514 } 515 516 // Okay, now we have a V1 or V2 live range that is maximally merged forward. 517 // Ensure that it is a V2 live-range. 518 LR->valno = V2; 519 520 // If we can merge it into later V2 live ranges, do so now. We ignore any 521 // following V1 live ranges, as they will be merged in subsequent iterations 522 // of the loop. 523 if (I != end()) { 524 if (I->start == LR->end && I->valno == V2) { 525 LR->end = I->end; 526 ranges.erase(I); 527 I = LR+1; 528 } 529 } 530 } 531 532 // Merge the relevant flags. 533 V2->mergeFlags(V1); 534 535 // Now that V1 is dead, remove it. 536 markValNoForDeletion(V1); 537 538 return V2; 539} 540 541void LiveInterval::Copy(const LiveInterval &RHS, 542 MachineRegisterInfo *MRI, 543 VNInfo::Allocator &VNInfoAllocator) { 544 ranges.clear(); 545 valnos.clear(); 546 std::pair<unsigned, unsigned> Hint = MRI->getRegAllocationHint(RHS.reg); 547 MRI->setRegAllocationHint(reg, Hint.first, Hint.second); 548 549 weight = RHS.weight; 550 for (unsigned i = 0, e = RHS.getNumValNums(); i != e; ++i) { 551 const VNInfo *VNI = RHS.getValNumInfo(i); 552 createValueCopy(VNI, VNInfoAllocator); 553 } 554 for (unsigned i = 0, e = RHS.ranges.size(); i != e; ++i) { 555 const LiveRange &LR = RHS.ranges[i]; 556 addRange(LiveRange(LR.start, LR.end, getValNumInfo(LR.valno->id))); 557 } 558} 559 560unsigned LiveInterval::getSize() const { 561 unsigned Sum = 0; 562 for (const_iterator I = begin(), E = end(); I != E; ++I) 563 Sum += I->start.distance(I->end); 564 return Sum; 565} 566 567raw_ostream& llvm::operator<<(raw_ostream& os, const LiveRange &LR) { 568 return os << '[' << LR.start << ',' << LR.end << ':' << LR.valno->id << ")"; 569} 570 571void LiveRange::dump() const { 572 dbgs() << *this << "\n"; 573} 574 575void LiveInterval::print(raw_ostream &OS, const TargetRegisterInfo *TRI) const { 576 OS << PrintReg(reg, TRI); 577 if (weight != 0) 578 OS << ',' << weight; 579 580 if (empty()) 581 OS << " EMPTY"; 582 else { 583 OS << " = "; 584 for (LiveInterval::Ranges::const_iterator I = ranges.begin(), 585 E = ranges.end(); I != E; ++I) { 586 OS << *I; 587 assert(I->valno == getValNumInfo(I->valno->id) && "Bad VNInfo"); 588 } 589 } 590 591 // Print value number info. 592 if (getNumValNums()) { 593 OS << " "; 594 unsigned vnum = 0; 595 for (const_vni_iterator i = vni_begin(), e = vni_end(); i != e; 596 ++i, ++vnum) { 597 const VNInfo *vni = *i; 598 if (vnum) OS << " "; 599 OS << vnum << "@"; 600 if (vni->isUnused()) { 601 OS << "x"; 602 } else { 603 OS << vni->def; 604 if (vni->isPHIDef()) 605 OS << "-phidef"; 606 if (vni->hasPHIKill()) 607 OS << "-phikill"; 608 } 609 } 610 } 611} 612 613void LiveInterval::dump() const { 614 dbgs() << *this << "\n"; 615} 616 617 618void LiveRange::print(raw_ostream &os) const { 619 os << *this; 620} 621 622unsigned ConnectedVNInfoEqClasses::Classify(const LiveInterval *LI) { 623 // Create initial equivalence classes. 624 EqClass.clear(); 625 EqClass.grow(LI->getNumValNums()); 626 627 const VNInfo *used = 0, *unused = 0; 628 629 // Determine connections. 630 for (LiveInterval::const_vni_iterator I = LI->vni_begin(), E = LI->vni_end(); 631 I != E; ++I) { 632 const VNInfo *VNI = *I; 633 // Group all unused values into one class. 634 if (VNI->isUnused()) { 635 if (unused) 636 EqClass.join(unused->id, VNI->id); 637 unused = VNI; 638 continue; 639 } 640 used = VNI; 641 if (VNI->isPHIDef()) { 642 const MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def); 643 assert(MBB && "Phi-def has no defining MBB"); 644 // Connect to values live out of predecessors. 645 for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 646 PE = MBB->pred_end(); PI != PE; ++PI) 647 if (const VNInfo *PVNI = LI->getVNInfoBefore(LIS.getMBBEndIdx(*PI))) 648 EqClass.join(VNI->id, PVNI->id); 649 } else { 650 // Normal value defined by an instruction. Check for two-addr redef. 651 // FIXME: This could be coincidental. Should we really check for a tied 652 // operand constraint? 653 // Note that VNI->def may be a use slot for an early clobber def. 654 if (const VNInfo *UVNI = LI->getVNInfoBefore(VNI->def)) 655 EqClass.join(VNI->id, UVNI->id); 656 } 657 } 658 659 // Lump all the unused values in with the last used value. 660 if (used && unused) 661 EqClass.join(used->id, unused->id); 662 663 EqClass.compress(); 664 return EqClass.getNumClasses(); 665} 666 667void ConnectedVNInfoEqClasses::Distribute(LiveInterval *LIV[], 668 MachineRegisterInfo &MRI) { 669 assert(LIV[0] && "LIV[0] must be set"); 670 LiveInterval &LI = *LIV[0]; 671 672 // Rewrite instructions. 673 for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(LI.reg), 674 RE = MRI.reg_end(); RI != RE;) { 675 MachineOperand &MO = RI.getOperand(); 676 MachineInstr *MI = MO.getParent(); 677 ++RI; 678 if (MO.isUse() && MO.isUndef()) 679 continue; 680 // DBG_VALUE instructions should have been eliminated earlier. 681 SlotIndex Idx = LIS.getInstructionIndex(MI); 682 Idx = Idx.getRegSlot(MO.isUse()); 683 const VNInfo *VNI = LI.getVNInfoAt(Idx); 684 // FIXME: We should be able to assert(VNI) here, but the coalescer leaves 685 // dangling defs around. 686 if (!VNI) 687 continue; 688 MO.setReg(LIV[getEqClass(VNI)]->reg); 689 } 690 691 // Move runs to new intervals. 692 LiveInterval::iterator J = LI.begin(), E = LI.end(); 693 while (J != E && EqClass[J->valno->id] == 0) 694 ++J; 695 for (LiveInterval::iterator I = J; I != E; ++I) { 696 if (unsigned eq = EqClass[I->valno->id]) { 697 assert((LIV[eq]->empty() || LIV[eq]->expiredAt(I->start)) && 698 "New intervals should be empty"); 699 LIV[eq]->ranges.push_back(*I); 700 } else 701 *J++ = *I; 702 } 703 LI.ranges.erase(J, E); 704 705 // Transfer VNInfos to their new owners and renumber them. 706 unsigned j = 0, e = LI.getNumValNums(); 707 while (j != e && EqClass[j] == 0) 708 ++j; 709 for (unsigned i = j; i != e; ++i) { 710 VNInfo *VNI = LI.getValNumInfo(i); 711 if (unsigned eq = EqClass[i]) { 712 VNI->id = LIV[eq]->getNumValNums(); 713 LIV[eq]->valnos.push_back(VNI); 714 } else { 715 VNI->id = j; 716 LI.valnos[j++] = VNI; 717 } 718 } 719 LI.valnos.resize(j); 720} 721