LiveInterval.cpp revision b64f669b666098b8494660fbd08a18610be228d4
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 33// CompEnd - Compare LiveRange ends. 34namespace { 35struct CompEnd { 36 bool operator()(SlotIndex A, const LiveRange &B) const { 37 return A < B.end; 38 } 39 bool operator()(const LiveRange &A, SlotIndex B) const { 40 return A.end < B; 41 } 42}; 43} 44 45LiveInterval::iterator LiveInterval::find(SlotIndex Pos) { 46 assert(Pos.isValid() && "Cannot search for an invalid index"); 47 return std::upper_bound(begin(), end(), Pos, CompEnd()); 48} 49 50/// killedInRange - Return true if the interval has kills in [Start,End). 51bool LiveInterval::killedInRange(SlotIndex Start, SlotIndex End) const { 52 Ranges::const_iterator r = 53 std::lower_bound(ranges.begin(), ranges.end(), End); 54 55 // Now r points to the first interval with start >= End, or ranges.end(). 56 if (r == ranges.begin()) 57 return false; 58 59 --r; 60 // Now r points to the last interval with end <= End. 61 // r->end is the kill point. 62 return r->end >= Start && r->end < End; 63} 64 65// overlaps - Return true if the intersection of the two live intervals is 66// not empty. 67// 68// An example for overlaps(): 69// 70// 0: A = ... 71// 4: B = ... 72// 8: C = A + B ;; last use of A 73// 74// The live intervals should look like: 75// 76// A = [3, 11) 77// B = [7, x) 78// C = [11, y) 79// 80// A->overlaps(C) should return false since we want to be able to join 81// A and C. 82// 83bool LiveInterval::overlapsFrom(const LiveInterval& other, 84 const_iterator StartPos) const { 85 assert(!empty() && "empty interval"); 86 const_iterator i = begin(); 87 const_iterator ie = end(); 88 const_iterator j = StartPos; 89 const_iterator je = other.end(); 90 91 assert((StartPos->start <= i->start || StartPos == other.begin()) && 92 StartPos != other.end() && "Bogus start position hint!"); 93 94 if (i->start < j->start) { 95 i = std::upper_bound(i, ie, j->start); 96 if (i != ranges.begin()) --i; 97 } else if (j->start < i->start) { 98 ++StartPos; 99 if (StartPos != other.end() && StartPos->start <= i->start) { 100 assert(StartPos < other.end() && i < end()); 101 j = std::upper_bound(j, je, i->start); 102 if (j != other.ranges.begin()) --j; 103 } 104 } else { 105 return true; 106 } 107 108 if (j == je) return false; 109 110 while (i != ie) { 111 if (i->start > j->start) { 112 std::swap(i, j); 113 std::swap(ie, je); 114 } 115 116 if (i->end > j->start) 117 return true; 118 ++i; 119 } 120 121 return false; 122} 123 124/// overlaps - Return true if the live interval overlaps a range specified 125/// by [Start, End). 126bool LiveInterval::overlaps(SlotIndex Start, SlotIndex End) const { 127 assert(Start < End && "Invalid range"); 128 const_iterator I = std::lower_bound(begin(), end(), End); 129 return I != begin() && (--I)->end > Start; 130} 131 132 133/// ValNo is dead, remove it. If it is the largest value number, just nuke it 134/// (and any other deleted values neighboring it), otherwise mark it as ~1U so 135/// it can be nuked later. 136void LiveInterval::markValNoForDeletion(VNInfo *ValNo) { 137 if (ValNo->id == getNumValNums()-1) { 138 do { 139 valnos.pop_back(); 140 } while (!valnos.empty() && valnos.back()->isUnused()); 141 } else { 142 ValNo->setIsUnused(true); 143 } 144} 145 146/// RenumberValues - Renumber all values in order of appearance and delete the 147/// remaining unused values. 148void LiveInterval::RenumberValues(LiveIntervals &lis) { 149 SmallPtrSet<VNInfo*, 8> Seen; 150 bool seenPHIDef = false; 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 VNI->setHasPHIKill(false); 160 if (VNI->isPHIDef()) 161 seenPHIDef = true; 162 } 163 164 // Recompute phi kill flags. 165 if (!seenPHIDef) 166 return; 167 for (const_vni_iterator I = vni_begin(), E = vni_end(); I != E; ++I) { 168 VNInfo *VNI = *I; 169 if (!VNI->isPHIDef()) 170 continue; 171 const MachineBasicBlock *PHIBB = lis.getMBBFromIndex(VNI->def); 172 assert(PHIBB && "No basic block for phi-def"); 173 for (MachineBasicBlock::const_pred_iterator PI = PHIBB->pred_begin(), 174 PE = PHIBB->pred_end(); PI != PE; ++PI) { 175 VNInfo *KVNI = getVNInfoAt(lis.getMBBEndIdx(*PI).getPrevSlot()); 176 if (KVNI) 177 KVNI->setHasPHIKill(true); 178 } 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 // Erase any dead ranges. 200 ranges.erase(llvm::next(I), MergeTo); 201 202 // If the newly formed range now touches the range after it and if they have 203 // the same value number, merge the two ranges into one range. 204 Ranges::iterator Next = llvm::next(I); 205 if (Next != ranges.end() && Next->start <= I->end && Next->valno == ValNo) { 206 I->end = Next->end; 207 ranges.erase(Next); 208 } 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 UseIdx in the basic 297/// block that starts at StartIdx, extend it to be live at UseIdx and return 298/// the value. If there is no live range before UseIdx, return NULL. 299VNInfo *LiveInterval::extendInBlock(SlotIndex StartIdx, SlotIndex UseIdx) { 300 if (empty()) 301 return 0; 302 iterator I = std::upper_bound(begin(), end(), UseIdx); 303 if (I == begin()) 304 return 0; 305 --I; 306 if (I->end <= StartIdx) 307 return 0; 308 if (I->end <= UseIdx) 309 extendIntervalEndTo(I, UseIdx.getNextSlot()); 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/// findDefinedVNInfo - Find the VNInfo defined by the specified 377/// index (register interval). 378VNInfo *LiveInterval::findDefinedVNInfoForRegInt(SlotIndex Idx) const { 379 for (LiveInterval::const_vni_iterator i = vni_begin(), e = vni_end(); 380 i != e; ++i) { 381 if ((*i)->def == Idx) 382 return *i; 383 } 384 385 return 0; 386} 387 388/// join - Join two live intervals (this, and other) together. This applies 389/// mappings to the value numbers in the LHS/RHS intervals as specified. If 390/// the intervals are not joinable, this aborts. 391void LiveInterval::join(LiveInterval &Other, 392 const int *LHSValNoAssignments, 393 const int *RHSValNoAssignments, 394 SmallVector<VNInfo*, 16> &NewVNInfo, 395 MachineRegisterInfo *MRI) { 396 // Determine if any of our live range values are mapped. This is uncommon, so 397 // we want to avoid the interval scan if not. 398 bool MustMapCurValNos = false; 399 unsigned NumVals = getNumValNums(); 400 unsigned NumNewVals = NewVNInfo.size(); 401 for (unsigned i = 0; i != NumVals; ++i) { 402 unsigned LHSValID = LHSValNoAssignments[i]; 403 if (i != LHSValID || 404 (NewVNInfo[LHSValID] && NewVNInfo[LHSValID] != getValNumInfo(i))) 405 MustMapCurValNos = true; 406 } 407 408 // If we have to apply a mapping to our base interval assignment, rewrite it 409 // now. 410 if (MustMapCurValNos) { 411 // Map the first live range. 412 iterator OutIt = begin(); 413 OutIt->valno = NewVNInfo[LHSValNoAssignments[OutIt->valno->id]]; 414 ++OutIt; 415 for (iterator I = OutIt, E = end(); I != E; ++I) { 416 OutIt->valno = NewVNInfo[LHSValNoAssignments[I->valno->id]]; 417 418 // If this live range has the same value # as its immediate predecessor, 419 // and if they are neighbors, remove one LiveRange. This happens when we 420 // have [0,3:0)[4,7:1) and map 0/1 onto the same value #. 421 if (OutIt->valno == (OutIt-1)->valno && (OutIt-1)->end == OutIt->start) { 422 (OutIt-1)->end = OutIt->end; 423 } else { 424 if (I != OutIt) { 425 OutIt->start = I->start; 426 OutIt->end = I->end; 427 } 428 429 // Didn't merge, on to the next one. 430 ++OutIt; 431 } 432 } 433 434 // If we merge some live ranges, chop off the end. 435 ranges.erase(OutIt, end()); 436 } 437 438 // Remember assignements because val# ids are changing. 439 SmallVector<unsigned, 16> OtherAssignments; 440 for (iterator I = Other.begin(), E = Other.end(); I != E; ++I) 441 OtherAssignments.push_back(RHSValNoAssignments[I->valno->id]); 442 443 // Update val# info. Renumber them and make sure they all belong to this 444 // LiveInterval now. Also remove dead val#'s. 445 unsigned NumValNos = 0; 446 for (unsigned i = 0; i < NumNewVals; ++i) { 447 VNInfo *VNI = NewVNInfo[i]; 448 if (VNI) { 449 if (NumValNos >= NumVals) 450 valnos.push_back(VNI); 451 else 452 valnos[NumValNos] = VNI; 453 VNI->id = NumValNos++; // Renumber val#. 454 } 455 } 456 if (NumNewVals < NumVals) 457 valnos.resize(NumNewVals); // shrinkify 458 459 // Okay, now insert the RHS live ranges into the LHS. 460 iterator InsertPos = begin(); 461 unsigned RangeNo = 0; 462 for (iterator I = Other.begin(), E = Other.end(); I != E; ++I, ++RangeNo) { 463 // Map the valno in the other live range to the current live range. 464 I->valno = NewVNInfo[OtherAssignments[RangeNo]]; 465 assert(I->valno && "Adding a dead range?"); 466 InsertPos = addRangeFrom(*I, InsertPos); 467 } 468 469 ComputeJoinedWeight(Other); 470} 471 472/// MergeRangesInAsValue - Merge all of the intervals in RHS into this live 473/// interval as the specified value number. The LiveRanges in RHS are 474/// allowed to overlap with LiveRanges in the current interval, but only if 475/// the overlapping LiveRanges have the specified value number. 476void LiveInterval::MergeRangesInAsValue(const LiveInterval &RHS, 477 VNInfo *LHSValNo) { 478 // TODO: Make this more efficient. 479 iterator InsertPos = begin(); 480 for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) { 481 // Map the valno in the other live range to the current live range. 482 LiveRange Tmp = *I; 483 Tmp.valno = LHSValNo; 484 InsertPos = addRangeFrom(Tmp, InsertPos); 485 } 486} 487 488 489/// MergeValueInAsValue - Merge all of the live ranges of a specific val# 490/// in RHS into this live interval as the specified value number. 491/// The LiveRanges in RHS are allowed to overlap with LiveRanges in the 492/// current interval, it will replace the value numbers of the overlaped 493/// live ranges with the specified value number. 494void LiveInterval::MergeValueInAsValue( 495 const LiveInterval &RHS, 496 const VNInfo *RHSValNo, VNInfo *LHSValNo) { 497 SmallVector<VNInfo*, 4> ReplacedValNos; 498 iterator IP = begin(); 499 for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) { 500 assert(I->valno == RHS.getValNumInfo(I->valno->id) && "Bad VNInfo"); 501 if (I->valno != RHSValNo) 502 continue; 503 SlotIndex Start = I->start, End = I->end; 504 IP = std::upper_bound(IP, end(), Start); 505 // If the start of this range overlaps with an existing liverange, trim it. 506 if (IP != begin() && IP[-1].end > Start) { 507 if (IP[-1].valno != LHSValNo) { 508 ReplacedValNos.push_back(IP[-1].valno); 509 IP[-1].valno = LHSValNo; // Update val#. 510 } 511 Start = IP[-1].end; 512 // Trimmed away the whole range? 513 if (Start >= End) continue; 514 } 515 // If the end of this range overlaps with an existing liverange, trim it. 516 if (IP != end() && End > IP->start) { 517 if (IP->valno != LHSValNo) { 518 ReplacedValNos.push_back(IP->valno); 519 IP->valno = LHSValNo; // Update val#. 520 } 521 End = IP->start; 522 // If this trimmed away the whole range, ignore it. 523 if (Start == End) continue; 524 } 525 526 // Map the valno in the other live range to the current live range. 527 IP = addRangeFrom(LiveRange(Start, End, LHSValNo), IP); 528 } 529 530 531 SmallSet<VNInfo*, 4> Seen; 532 for (unsigned i = 0, e = ReplacedValNos.size(); i != e; ++i) { 533 VNInfo *V1 = ReplacedValNos[i]; 534 if (Seen.insert(V1)) { 535 bool isDead = true; 536 for (const_iterator I = begin(), E = end(); I != E; ++I) 537 if (I->valno == V1) { 538 isDead = false; 539 break; 540 } 541 if (isDead) { 542 // Now that V1 is dead, remove it. 543 markValNoForDeletion(V1); 544 } 545 } 546 } 547} 548 549 550 551/// MergeValueNumberInto - This method is called when two value nubmers 552/// are found to be equivalent. This eliminates V1, replacing all 553/// LiveRanges with the V1 value number with the V2 value number. This can 554/// cause merging of V1/V2 values numbers and compaction of the value space. 555VNInfo* LiveInterval::MergeValueNumberInto(VNInfo *V1, VNInfo *V2) { 556 assert(V1 != V2 && "Identical value#'s are always equivalent!"); 557 558 // This code actually merges the (numerically) larger value number into the 559 // smaller value number, which is likely to allow us to compactify the value 560 // space. The only thing we have to be careful of is to preserve the 561 // instruction that defines the result value. 562 563 // Make sure V2 is smaller than V1. 564 if (V1->id < V2->id) { 565 V1->copyFrom(*V2); 566 std::swap(V1, V2); 567 } 568 569 // Merge V1 live ranges into V2. 570 for (iterator I = begin(); I != end(); ) { 571 iterator LR = I++; 572 if (LR->valno != V1) continue; // Not a V1 LiveRange. 573 574 // Okay, we found a V1 live range. If it had a previous, touching, V2 live 575 // range, extend it. 576 if (LR != begin()) { 577 iterator Prev = LR-1; 578 if (Prev->valno == V2 && Prev->end == LR->start) { 579 Prev->end = LR->end; 580 581 // Erase this live-range. 582 ranges.erase(LR); 583 I = Prev+1; 584 LR = Prev; 585 } 586 } 587 588 // Okay, now we have a V1 or V2 live range that is maximally merged forward. 589 // Ensure that it is a V2 live-range. 590 LR->valno = V2; 591 592 // If we can merge it into later V2 live ranges, do so now. We ignore any 593 // following V1 live ranges, as they will be merged in subsequent iterations 594 // of the loop. 595 if (I != end()) { 596 if (I->start == LR->end && I->valno == V2) { 597 LR->end = I->end; 598 ranges.erase(I); 599 I = LR+1; 600 } 601 } 602 } 603 604 // Merge the relevant flags. 605 V2->mergeFlags(V1); 606 607 // Now that V1 is dead, remove it. 608 markValNoForDeletion(V1); 609 610 return V2; 611} 612 613void LiveInterval::Copy(const LiveInterval &RHS, 614 MachineRegisterInfo *MRI, 615 VNInfo::Allocator &VNInfoAllocator) { 616 ranges.clear(); 617 valnos.clear(); 618 std::pair<unsigned, unsigned> Hint = MRI->getRegAllocationHint(RHS.reg); 619 MRI->setRegAllocationHint(reg, Hint.first, Hint.second); 620 621 weight = RHS.weight; 622 for (unsigned i = 0, e = RHS.getNumValNums(); i != e; ++i) { 623 const VNInfo *VNI = RHS.getValNumInfo(i); 624 createValueCopy(VNI, VNInfoAllocator); 625 } 626 for (unsigned i = 0, e = RHS.ranges.size(); i != e; ++i) { 627 const LiveRange &LR = RHS.ranges[i]; 628 addRange(LiveRange(LR.start, LR.end, getValNumInfo(LR.valno->id))); 629 } 630} 631 632unsigned LiveInterval::getSize() const { 633 unsigned Sum = 0; 634 for (const_iterator I = begin(), E = end(); I != E; ++I) 635 Sum += I->start.distance(I->end); 636 return Sum; 637} 638 639/// ComputeJoinedWeight - Set the weight of a live interval Joined 640/// after Other has been merged into it. 641void LiveInterval::ComputeJoinedWeight(const LiveInterval &Other) { 642 // If either of these intervals was spilled, the weight is the 643 // weight of the non-spilled interval. This can only happen with 644 // iterative coalescers. 645 646 if (Other.weight != HUGE_VALF) { 647 weight += Other.weight; 648 } 649 else if (weight == HUGE_VALF && 650 !TargetRegisterInfo::isPhysicalRegister(reg)) { 651 // Remove this assert if you have an iterative coalescer 652 assert(0 && "Joining to spilled interval"); 653 weight = Other.weight; 654 } 655 else { 656 // Otherwise the weight stays the same 657 // Remove this assert if you have an iterative coalescer 658 assert(0 && "Joining from spilled interval"); 659 } 660} 661 662raw_ostream& llvm::operator<<(raw_ostream& os, const LiveRange &LR) { 663 return os << '[' << LR.start << ',' << LR.end << ':' << LR.valno->id << ")"; 664} 665 666void LiveRange::dump() const { 667 dbgs() << *this << "\n"; 668} 669 670void LiveInterval::print(raw_ostream &OS, const TargetRegisterInfo *TRI) const { 671 OS << PrintReg(reg, TRI); 672 if (weight != 0) 673 OS << ',' << weight; 674 675 if (empty()) 676 OS << " EMPTY"; 677 else { 678 OS << " = "; 679 for (LiveInterval::Ranges::const_iterator I = ranges.begin(), 680 E = ranges.end(); I != E; ++I) { 681 OS << *I; 682 assert(I->valno == getValNumInfo(I->valno->id) && "Bad VNInfo"); 683 } 684 } 685 686 // Print value number info. 687 if (getNumValNums()) { 688 OS << " "; 689 unsigned vnum = 0; 690 for (const_vni_iterator i = vni_begin(), e = vni_end(); i != e; 691 ++i, ++vnum) { 692 const VNInfo *vni = *i; 693 if (vnum) OS << " "; 694 OS << vnum << "@"; 695 if (vni->isUnused()) { 696 OS << "x"; 697 } else { 698 OS << vni->def; 699 if (vni->isPHIDef()) 700 OS << "-phidef"; 701 if (vni->hasPHIKill()) 702 OS << "-phikill"; 703 if (vni->hasRedefByEC()) 704 OS << "-ec"; 705 } 706 } 707 } 708} 709 710void LiveInterval::dump() const { 711 dbgs() << *this << "\n"; 712} 713 714 715void LiveRange::print(raw_ostream &os) const { 716 os << *this; 717} 718 719unsigned ConnectedVNInfoEqClasses::Classify(const LiveInterval *LI) { 720 // Create initial equivalence classes. 721 eqClass_.clear(); 722 eqClass_.grow(LI->getNumValNums()); 723 724 const VNInfo *used = 0, *unused = 0; 725 726 // Determine connections. 727 for (LiveInterval::const_vni_iterator I = LI->vni_begin(), E = LI->vni_end(); 728 I != E; ++I) { 729 const VNInfo *VNI = *I; 730 // Group all unused values into one class. 731 if (VNI->isUnused()) { 732 if (unused) 733 eqClass_.join(unused->id, VNI->id); 734 unused = VNI; 735 continue; 736 } 737 used = VNI; 738 if (VNI->isPHIDef()) { 739 const MachineBasicBlock *MBB = lis_.getMBBFromIndex(VNI->def); 740 assert(MBB && "Phi-def has no defining MBB"); 741 // Connect to values live out of predecessors. 742 for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 743 PE = MBB->pred_end(); PI != PE; ++PI) 744 if (const VNInfo *PVNI = 745 LI->getVNInfoAt(lis_.getMBBEndIdx(*PI).getPrevSlot())) 746 eqClass_.join(VNI->id, PVNI->id); 747 } else { 748 // Normal value defined by an instruction. Check for two-addr redef. 749 // FIXME: This could be coincidental. Should we really check for a tied 750 // operand constraint? 751 // Note that VNI->def may be a use slot for an early clobber def. 752 if (const VNInfo *UVNI = LI->getVNInfoAt(VNI->def.getPrevSlot())) 753 eqClass_.join(VNI->id, UVNI->id); 754 } 755 } 756 757 // Lump all the unused values in with the last used value. 758 if (used && unused) 759 eqClass_.join(used->id, unused->id); 760 761 eqClass_.compress(); 762 return eqClass_.getNumClasses(); 763} 764 765void ConnectedVNInfoEqClasses::Distribute(LiveInterval *LIV[]) { 766 assert(LIV[0] && "LIV[0] must be set"); 767 LiveInterval &LI = *LIV[0]; 768 769 // First move runs to new intervals. 770 LiveInterval::iterator J = LI.begin(), E = LI.end(); 771 while (J != E && eqClass_[J->valno->id] == 0) 772 ++J; 773 for (LiveInterval::iterator I = J; I != E; ++I) { 774 if (unsigned eq = eqClass_[I->valno->id]) { 775 assert((LIV[eq]->empty() || LIV[eq]->expiredAt(I->start)) && 776 "New intervals should be empty"); 777 LIV[eq]->ranges.push_back(*I); 778 } else 779 *J++ = *I; 780 } 781 LI.ranges.erase(J, E); 782 783 // Transfer VNInfos to their new owners and renumber them. 784 unsigned j = 0, e = LI.getNumValNums(); 785 while (j != e && eqClass_[j] == 0) 786 ++j; 787 for (unsigned i = j; i != e; ++i) { 788 VNInfo *VNI = LI.getValNumInfo(i); 789 if (unsigned eq = eqClass_[i]) { 790 VNI->id = LIV[eq]->getNumValNums(); 791 LIV[eq]->valnos.push_back(VNI); 792 } else { 793 VNI->id = j; 794 LI.valnos[j++] = VNI; 795 } 796 } 797 LI.valnos.resize(j); 798} 799