LiveInterval.cpp revision 6194569d22003fddaf1a33acdbb84d5efe76e7d7
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' abd 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/raw_ostream.h" 28#include "llvm/Target/TargetRegisterInfo.h" 29#include <algorithm> 30using namespace llvm; 31 32// An example for liveAt(): 33// 34// this = [1,4), liveAt(0) will return false. The instruction defining this 35// spans slots [0,3]. The interval belongs to an spilled definition of the 36// variable it represents. This is because slot 1 is used (def slot) and spans 37// up to slot 3 (store slot). 38// 39bool LiveInterval::liveAt(SlotIndex I) const { 40 Ranges::const_iterator r = std::upper_bound(ranges.begin(), ranges.end(), I); 41 42 if (r == ranges.begin()) 43 return false; 44 45 --r; 46 return r->contains(I); 47} 48 49// liveBeforeAndAt - Check if the interval is live at the index and the index 50// just before it. If index is liveAt, check if it starts a new live range. 51// If it does, then check if the previous live range ends at index-1. 52bool LiveInterval::liveBeforeAndAt(SlotIndex I) const { 53 Ranges::const_iterator r = std::upper_bound(ranges.begin(), ranges.end(), I); 54 55 if (r == ranges.begin()) 56 return false; 57 58 --r; 59 if (!r->contains(I)) 60 return false; 61 if (I != r->start) 62 return true; 63 // I is the start of a live range. Check if the previous live range ends 64 // at I-1. 65 if (r == ranges.begin()) 66 return false; 67 return r->end == I; 68} 69 70// overlaps - Return true if the intersection of the two live intervals is 71// not empty. 72// 73// An example for overlaps(): 74// 75// 0: A = ... 76// 4: B = ... 77// 8: C = A + B ;; last use of A 78// 79// The live intervals should look like: 80// 81// A = [3, 11) 82// B = [7, x) 83// C = [11, y) 84// 85// A->overlaps(C) should return false since we want to be able to join 86// A and C. 87// 88bool LiveInterval::overlapsFrom(const LiveInterval& other, 89 const_iterator StartPos) const { 90 const_iterator i = begin(); 91 const_iterator ie = end(); 92 const_iterator j = StartPos; 93 const_iterator je = other.end(); 94 95 assert((StartPos->start <= i->start || StartPos == other.begin()) && 96 StartPos != other.end() && "Bogus start position hint!"); 97 98 if (i->start < j->start) { 99 i = std::upper_bound(i, ie, j->start); 100 if (i != ranges.begin()) --i; 101 } else if (j->start < i->start) { 102 ++StartPos; 103 if (StartPos != other.end() && StartPos->start <= i->start) { 104 assert(StartPos < other.end() && i < end()); 105 j = std::upper_bound(j, je, i->start); 106 if (j != other.ranges.begin()) --j; 107 } 108 } else { 109 return true; 110 } 111 112 if (j == je) return false; 113 114 while (i != ie) { 115 if (i->start > j->start) { 116 std::swap(i, j); 117 std::swap(ie, je); 118 } 119 120 if (i->end > j->start) 121 return true; 122 ++i; 123 } 124 125 return false; 126} 127 128/// overlaps - Return true if the live interval overlaps a range specified 129/// by [Start, End). 130bool LiveInterval::overlaps(SlotIndex Start, SlotIndex End) const { 131 assert(Start < End && "Invalid range"); 132 const_iterator I = begin(); 133 const_iterator E = end(); 134 const_iterator si = std::upper_bound(I, E, Start); 135 const_iterator ei = std::upper_bound(I, E, End); 136 if (si != ei) 137 return true; 138 if (si == I) 139 return false; 140 --si; 141 return si->contains(Start); 142} 143 144/// extendIntervalEndTo - This method is used when we want to extend the range 145/// specified by I to end at the specified endpoint. To do this, we should 146/// merge and eliminate all ranges that this will overlap with. The iterator is 147/// not invalidated. 148void LiveInterval::extendIntervalEndTo(Ranges::iterator I, SlotIndex NewEnd) { 149 assert(I != ranges.end() && "Not a valid interval!"); 150 VNInfo *ValNo = I->valno; 151 SlotIndex OldEnd = I->end; 152 153 // Search for the first interval that we can't merge with. 154 Ranges::iterator MergeTo = next(I); 155 for (; MergeTo != ranges.end() && NewEnd >= MergeTo->end; ++MergeTo) { 156 assert(MergeTo->valno == ValNo && "Cannot merge with differing values!"); 157 } 158 159 // If NewEnd was in the middle of an interval, make sure to get its endpoint. 160 I->end = std::max(NewEnd, prior(MergeTo)->end); 161 162 // Erase any dead ranges. 163 ranges.erase(next(I), MergeTo); 164 165 // Update kill info. 166 ValNo->removeKills(OldEnd, I->end.getPrevSlot()); 167 168 // If the newly formed range now touches the range after it and if they have 169 // the same value number, merge the two ranges into one range. 170 Ranges::iterator Next = next(I); 171 if (Next != ranges.end() && Next->start <= I->end && Next->valno == ValNo) { 172 I->end = Next->end; 173 ranges.erase(Next); 174 } 175} 176 177 178/// extendIntervalStartTo - This method is used when we want to extend the range 179/// specified by I to start at the specified endpoint. To do this, we should 180/// merge and eliminate all ranges that this will overlap with. 181LiveInterval::Ranges::iterator 182LiveInterval::extendIntervalStartTo(Ranges::iterator I, SlotIndex NewStart) { 183 assert(I != ranges.end() && "Not a valid interval!"); 184 VNInfo *ValNo = I->valno; 185 186 // Search for the first interval that we can't merge with. 187 Ranges::iterator MergeTo = I; 188 do { 189 if (MergeTo == ranges.begin()) { 190 I->start = NewStart; 191 ranges.erase(MergeTo, I); 192 return I; 193 } 194 assert(MergeTo->valno == ValNo && "Cannot merge with differing values!"); 195 --MergeTo; 196 } while (NewStart <= MergeTo->start); 197 198 // If we start in the middle of another interval, just delete a range and 199 // extend that interval. 200 if (MergeTo->end >= NewStart && MergeTo->valno == ValNo) { 201 MergeTo->end = I->end; 202 } else { 203 // Otherwise, extend the interval right after. 204 ++MergeTo; 205 MergeTo->start = NewStart; 206 MergeTo->end = I->end; 207 } 208 209 ranges.erase(next(MergeTo), next(I)); 210 return MergeTo; 211} 212 213LiveInterval::iterator 214LiveInterval::addRangeFrom(LiveRange LR, iterator From) { 215 SlotIndex Start = LR.start, End = LR.end; 216 iterator it = std::upper_bound(From, ranges.end(), Start); 217 218 // If the inserted interval starts in the middle or right at the end of 219 // another interval, just extend that interval to contain the range of LR. 220 if (it != ranges.begin()) { 221 iterator B = prior(it); 222 if (LR.valno == B->valno) { 223 if (B->start <= Start && B->end >= Start) { 224 extendIntervalEndTo(B, End); 225 return B; 226 } 227 } else { 228 // Check to make sure that we are not overlapping two live ranges with 229 // different valno's. 230 assert(B->end <= Start && 231 "Cannot overlap two LiveRanges with differing ValID's" 232 " (did you def the same reg twice in a MachineInstr?)"); 233 } 234 } 235 236 // Otherwise, if this range ends in the middle of, or right next to, another 237 // interval, merge it into that interval. 238 if (it != ranges.end()) { 239 if (LR.valno == it->valno) { 240 if (it->start <= End) { 241 it = extendIntervalStartTo(it, Start); 242 243 // If LR is a complete superset of an interval, we may need to grow its 244 // endpoint as well. 245 if (End > it->end) 246 extendIntervalEndTo(it, End); 247 else if (End < it->end) 248 // Overlapping intervals, there might have been a kill here. 249 it->valno->removeKill(End); 250 return it; 251 } 252 } else { 253 // Check to make sure that we are not overlapping two live ranges with 254 // different valno's. 255 assert(it->start >= End && 256 "Cannot overlap two LiveRanges with differing ValID's"); 257 } 258 } 259 260 // Otherwise, this is just a new range that doesn't interact with anything. 261 // Insert it. 262 return ranges.insert(it, LR); 263} 264 265/// isInOneLiveRange - Return true if the range specified is entirely in 266/// a single LiveRange of the live interval. 267bool LiveInterval::isInOneLiveRange(SlotIndex Start, SlotIndex End) { 268 Ranges::iterator I = std::upper_bound(ranges.begin(), ranges.end(), Start); 269 if (I == ranges.begin()) 270 return false; 271 --I; 272 return I->containsRange(Start, End); 273} 274 275 276/// removeRange - Remove the specified range from this interval. Note that 277/// the range must be in a single LiveRange in its entirety. 278void LiveInterval::removeRange(SlotIndex Start, SlotIndex End, 279 bool RemoveDeadValNo) { 280 // Find the LiveRange containing this span. 281 Ranges::iterator I = std::upper_bound(ranges.begin(), ranges.end(), Start); 282 assert(I != ranges.begin() && "Range is not in interval!"); 283 --I; 284 assert(I->containsRange(Start, End) && "Range is not entirely in interval!"); 285 286 // If the span we are removing is at the start of the LiveRange, adjust it. 287 VNInfo *ValNo = I->valno; 288 if (I->start == Start) { 289 if (I->end == End) { 290 ValNo->removeKills(Start, End); 291 if (RemoveDeadValNo) { 292 // Check if val# is dead. 293 bool isDead = true; 294 for (const_iterator II = begin(), EE = end(); II != EE; ++II) 295 if (II != I && II->valno == ValNo) { 296 isDead = false; 297 break; 298 } 299 if (isDead) { 300 // Now that ValNo is dead, remove it. If it is the largest value 301 // number, just nuke it (and any other deleted values neighboring it), 302 // otherwise mark it as ~1U so it can be nuked later. 303 if (ValNo->id == getNumValNums()-1) { 304 do { 305 VNInfo *VNI = valnos.back(); 306 valnos.pop_back(); 307 VNI->~VNInfo(); 308 } while (!valnos.empty() && valnos.back()->isUnused()); 309 } else { 310 ValNo->setIsUnused(true); 311 } 312 } 313 } 314 315 ranges.erase(I); // Removed the whole LiveRange. 316 } else 317 I->start = End; 318 return; 319 } 320 321 // Otherwise if the span we are removing is at the end of the LiveRange, 322 // adjust the other way. 323 if (I->end == End) { 324 ValNo->removeKills(Start, End); 325 I->end = Start; 326 return; 327 } 328 329 // Otherwise, we are splitting the LiveRange into two pieces. 330 SlotIndex OldEnd = I->end; 331 I->end = Start; // Trim the old interval. 332 333 // Insert the new one. 334 ranges.insert(next(I), LiveRange(End, OldEnd, ValNo)); 335} 336 337/// removeValNo - Remove all the ranges defined by the specified value#. 338/// Also remove the value# from value# list. 339void LiveInterval::removeValNo(VNInfo *ValNo) { 340 if (empty()) return; 341 Ranges::iterator I = ranges.end(); 342 Ranges::iterator E = ranges.begin(); 343 do { 344 --I; 345 if (I->valno == ValNo) 346 ranges.erase(I); 347 } while (I != E); 348 // Now that ValNo is dead, remove it. If it is the largest value 349 // number, just nuke it (and any other deleted values neighboring it), 350 // otherwise mark it as ~1U so it can be nuked later. 351 if (ValNo->id == getNumValNums()-1) { 352 do { 353 VNInfo *VNI = valnos.back(); 354 valnos.pop_back(); 355 VNI->~VNInfo(); 356 } while (!valnos.empty() && valnos.back()->isUnused()); 357 } else { 358 ValNo->setIsUnused(true); 359 } 360} 361 362/// getLiveRangeContaining - Return the live range that contains the 363/// specified index, or null if there is none. 364LiveInterval::const_iterator 365LiveInterval::FindLiveRangeContaining(SlotIndex Idx) const { 366 const_iterator It = std::upper_bound(begin(), end(), Idx); 367 if (It != ranges.begin()) { 368 --It; 369 if (It->contains(Idx)) 370 return It; 371 } 372 373 return end(); 374} 375 376LiveInterval::iterator 377LiveInterval::FindLiveRangeContaining(SlotIndex Idx) { 378 iterator It = std::upper_bound(begin(), end(), Idx); 379 if (It != begin()) { 380 --It; 381 if (It->contains(Idx)) 382 return It; 383 } 384 385 return end(); 386} 387 388/// findDefinedVNInfo - Find the VNInfo defined by the specified 389/// index (register interval). 390VNInfo *LiveInterval::findDefinedVNInfoForRegInt(SlotIndex Idx) const { 391 for (LiveInterval::const_vni_iterator i = vni_begin(), e = vni_end(); 392 i != e; ++i) { 393 if ((*i)->def == Idx) 394 return *i; 395 } 396 397 return 0; 398} 399 400/// findDefinedVNInfo - Find the VNInfo defined by the specified 401/// register (stack inteval). 402VNInfo *LiveInterval::findDefinedVNInfoForStackInt(unsigned reg) const { 403 for (LiveInterval::const_vni_iterator i = vni_begin(), e = vni_end(); 404 i != e; ++i) { 405 if ((*i)->getReg() == reg) 406 return *i; 407 } 408 return 0; 409} 410 411/// join - Join two live intervals (this, and other) together. This applies 412/// mappings to the value numbers in the LHS/RHS intervals as specified. If 413/// the intervals are not joinable, this aborts. 414void LiveInterval::join(LiveInterval &Other, 415 const int *LHSValNoAssignments, 416 const int *RHSValNoAssignments, 417 SmallVector<VNInfo*, 16> &NewVNInfo, 418 MachineRegisterInfo *MRI) { 419 // Determine if any of our live range values are mapped. This is uncommon, so 420 // we want to avoid the interval scan if not. 421 bool MustMapCurValNos = false; 422 unsigned NumVals = getNumValNums(); 423 unsigned NumNewVals = NewVNInfo.size(); 424 for (unsigned i = 0; i != NumVals; ++i) { 425 unsigned LHSValID = LHSValNoAssignments[i]; 426 if (i != LHSValID || 427 (NewVNInfo[LHSValID] && NewVNInfo[LHSValID] != getValNumInfo(i))) 428 MustMapCurValNos = true; 429 } 430 431 // If we have to apply a mapping to our base interval assignment, rewrite it 432 // now. 433 if (MustMapCurValNos) { 434 // Map the first live range. 435 iterator OutIt = begin(); 436 OutIt->valno = NewVNInfo[LHSValNoAssignments[OutIt->valno->id]]; 437 ++OutIt; 438 for (iterator I = OutIt, E = end(); I != E; ++I) { 439 OutIt->valno = NewVNInfo[LHSValNoAssignments[I->valno->id]]; 440 441 // If this live range has the same value # as its immediate predecessor, 442 // and if they are neighbors, remove one LiveRange. This happens when we 443 // have [0,3:0)[4,7:1) and map 0/1 onto the same value #. 444 if (OutIt->valno == (OutIt-1)->valno && (OutIt-1)->end == OutIt->start) { 445 (OutIt-1)->end = OutIt->end; 446 } else { 447 if (I != OutIt) { 448 OutIt->start = I->start; 449 OutIt->end = I->end; 450 } 451 452 // Didn't merge, on to the next one. 453 ++OutIt; 454 } 455 } 456 457 // If we merge some live ranges, chop off the end. 458 ranges.erase(OutIt, end()); 459 } 460 461 // Remember assignements because val# ids are changing. 462 SmallVector<unsigned, 16> OtherAssignments; 463 for (iterator I = Other.begin(), E = Other.end(); I != E; ++I) 464 OtherAssignments.push_back(RHSValNoAssignments[I->valno->id]); 465 466 // Update val# info. Renumber them and make sure they all belong to this 467 // LiveInterval now. Also remove dead val#'s. 468 unsigned NumValNos = 0; 469 for (unsigned i = 0; i < NumNewVals; ++i) { 470 VNInfo *VNI = NewVNInfo[i]; 471 if (VNI) { 472 if (NumValNos >= NumVals) 473 valnos.push_back(VNI); 474 else 475 valnos[NumValNos] = VNI; 476 VNI->id = NumValNos++; // Renumber val#. 477 } 478 } 479 if (NumNewVals < NumVals) 480 valnos.resize(NumNewVals); // shrinkify 481 482 // Okay, now insert the RHS live ranges into the LHS. 483 iterator InsertPos = begin(); 484 unsigned RangeNo = 0; 485 for (iterator I = Other.begin(), E = Other.end(); I != E; ++I, ++RangeNo) { 486 // Map the valno in the other live range to the current live range. 487 I->valno = NewVNInfo[OtherAssignments[RangeNo]]; 488 assert(I->valno && "Adding a dead range?"); 489 InsertPos = addRangeFrom(*I, InsertPos); 490 } 491 492 ComputeJoinedWeight(Other); 493 494 // Update regalloc hint if currently there isn't one. 495 if (TargetRegisterInfo::isVirtualRegister(reg) && 496 TargetRegisterInfo::isVirtualRegister(Other.reg)) { 497 std::pair<unsigned, unsigned> Hint = MRI->getRegAllocationHint(reg); 498 if (Hint.first == 0 && Hint.second == 0) { 499 std::pair<unsigned, unsigned> OtherHint = 500 MRI->getRegAllocationHint(Other.reg); 501 if (OtherHint.first || OtherHint.second) 502 MRI->setRegAllocationHint(reg, OtherHint.first, OtherHint.second); 503 } 504 } 505} 506 507/// MergeRangesInAsValue - Merge all of the intervals in RHS into this live 508/// interval as the specified value number. The LiveRanges in RHS are 509/// allowed to overlap with LiveRanges in the current interval, but only if 510/// the overlapping LiveRanges have the specified value number. 511void LiveInterval::MergeRangesInAsValue(const LiveInterval &RHS, 512 VNInfo *LHSValNo) { 513 // TODO: Make this more efficient. 514 iterator InsertPos = begin(); 515 for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) { 516 // Map the valno in the other live range to the current live range. 517 LiveRange Tmp = *I; 518 Tmp.valno = LHSValNo; 519 InsertPos = addRangeFrom(Tmp, InsertPos); 520 } 521} 522 523 524/// MergeValueInAsValue - Merge all of the live ranges of a specific val# 525/// in RHS into this live interval as the specified value number. 526/// The LiveRanges in RHS are allowed to overlap with LiveRanges in the 527/// current interval, it will replace the value numbers of the overlaped 528/// live ranges with the specified value number. 529void LiveInterval::MergeValueInAsValue( 530 const LiveInterval &RHS, 531 const VNInfo *RHSValNo, VNInfo *LHSValNo) { 532 SmallVector<VNInfo*, 4> ReplacedValNos; 533 iterator IP = begin(); 534 for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) { 535 if (I->valno != RHSValNo) 536 continue; 537 SlotIndex Start = I->start, End = I->end; 538 IP = std::upper_bound(IP, end(), Start); 539 // If the start of this range overlaps with an existing liverange, trim it. 540 if (IP != begin() && IP[-1].end > Start) { 541 if (IP[-1].valno != LHSValNo) { 542 ReplacedValNos.push_back(IP[-1].valno); 543 IP[-1].valno = LHSValNo; // Update val#. 544 } 545 Start = IP[-1].end; 546 // Trimmed away the whole range? 547 if (Start >= End) continue; 548 } 549 // If the end of this range overlaps with an existing liverange, trim it. 550 if (IP != end() && End > IP->start) { 551 if (IP->valno != LHSValNo) { 552 ReplacedValNos.push_back(IP->valno); 553 IP->valno = LHSValNo; // Update val#. 554 } 555 End = IP->start; 556 // If this trimmed away the whole range, ignore it. 557 if (Start == End) continue; 558 } 559 560 // Map the valno in the other live range to the current live range. 561 IP = addRangeFrom(LiveRange(Start, End, LHSValNo), IP); 562 } 563 564 565 SmallSet<VNInfo*, 4> Seen; 566 for (unsigned i = 0, e = ReplacedValNos.size(); i != e; ++i) { 567 VNInfo *V1 = ReplacedValNos[i]; 568 if (Seen.insert(V1)) { 569 bool isDead = true; 570 for (const_iterator I = begin(), E = end(); I != E; ++I) 571 if (I->valno == V1) { 572 isDead = false; 573 break; 574 } 575 if (isDead) { 576 // Now that V1 is dead, remove it. If it is the largest value number, 577 // just nuke it (and any other deleted values neighboring it), otherwise 578 // mark it as ~1U so it can be nuked later. 579 if (V1->id == getNumValNums()-1) { 580 do { 581 VNInfo *VNI = valnos.back(); 582 valnos.pop_back(); 583 VNI->~VNInfo(); 584 } while (!valnos.empty() && valnos.back()->isUnused()); 585 } else { 586 V1->setIsUnused(true); 587 } 588 } 589 } 590 } 591} 592 593 594/// MergeInClobberRanges - For any live ranges that are not defined in the 595/// current interval, but are defined in the Clobbers interval, mark them 596/// used with an unknown definition value. 597void LiveInterval::MergeInClobberRanges(LiveIntervals &li_, 598 const LiveInterval &Clobbers, 599 BumpPtrAllocator &VNInfoAllocator) { 600 if (Clobbers.empty()) return; 601 602 DenseMap<VNInfo*, VNInfo*> ValNoMaps; 603 VNInfo *UnusedValNo = 0; 604 iterator IP = begin(); 605 for (const_iterator I = Clobbers.begin(), E = Clobbers.end(); I != E; ++I) { 606 // For every val# in the Clobbers interval, create a new "unknown" val#. 607 VNInfo *ClobberValNo = 0; 608 DenseMap<VNInfo*, VNInfo*>::iterator VI = ValNoMaps.find(I->valno); 609 if (VI != ValNoMaps.end()) 610 ClobberValNo = VI->second; 611 else if (UnusedValNo) 612 ClobberValNo = UnusedValNo; 613 else { 614 UnusedValNo = ClobberValNo = 615 getNextValue(li_.getInvalidIndex(), 0, false, VNInfoAllocator); 616 ValNoMaps.insert(std::make_pair(I->valno, ClobberValNo)); 617 } 618 619 bool Done = false; 620 SlotIndex Start = I->start, End = I->end; 621 // If a clobber range starts before an existing range and ends after 622 // it, the clobber range will need to be split into multiple ranges. 623 // Loop until the entire clobber range is handled. 624 while (!Done) { 625 Done = true; 626 IP = std::upper_bound(IP, end(), Start); 627 SlotIndex SubRangeStart = Start; 628 SlotIndex SubRangeEnd = End; 629 630 // If the start of this range overlaps with an existing liverange, trim it. 631 if (IP != begin() && IP[-1].end > SubRangeStart) { 632 SubRangeStart = IP[-1].end; 633 // Trimmed away the whole range? 634 if (SubRangeStart >= SubRangeEnd) continue; 635 } 636 // If the end of this range overlaps with an existing liverange, trim it. 637 if (IP != end() && SubRangeEnd > IP->start) { 638 // If the clobber live range extends beyond the existing live range, 639 // it'll need at least another live range, so set the flag to keep 640 // iterating. 641 if (SubRangeEnd > IP->end) { 642 Start = IP->end; 643 Done = false; 644 } 645 SubRangeEnd = IP->start; 646 // If this trimmed away the whole range, ignore it. 647 if (SubRangeStart == SubRangeEnd) continue; 648 } 649 650 // Insert the clobber interval. 651 IP = addRangeFrom(LiveRange(SubRangeStart, SubRangeEnd, ClobberValNo), 652 IP); 653 UnusedValNo = 0; 654 } 655 } 656 657 if (UnusedValNo) { 658 // Delete the last unused val#. 659 valnos.pop_back(); 660 UnusedValNo->~VNInfo(); 661 } 662} 663 664void LiveInterval::MergeInClobberRange(LiveIntervals &li_, 665 SlotIndex Start, 666 SlotIndex End, 667 BumpPtrAllocator &VNInfoAllocator) { 668 // Find a value # to use for the clobber ranges. If there is already a value# 669 // for unknown values, use it. 670 VNInfo *ClobberValNo = 671 getNextValue(li_.getInvalidIndex(), 0, false, VNInfoAllocator); 672 673 iterator IP = begin(); 674 IP = std::upper_bound(IP, end(), Start); 675 676 // If the start of this range overlaps with an existing liverange, trim it. 677 if (IP != begin() && IP[-1].end > Start) { 678 Start = IP[-1].end; 679 // Trimmed away the whole range? 680 if (Start >= End) return; 681 } 682 // If the end of this range overlaps with an existing liverange, trim it. 683 if (IP != end() && End > IP->start) { 684 End = IP->start; 685 // If this trimmed away the whole range, ignore it. 686 if (Start == End) return; 687 } 688 689 // Insert the clobber interval. 690 addRangeFrom(LiveRange(Start, End, ClobberValNo), IP); 691} 692 693/// MergeValueNumberInto - This method is called when two value nubmers 694/// are found to be equivalent. This eliminates V1, replacing all 695/// LiveRanges with the V1 value number with the V2 value number. This can 696/// cause merging of V1/V2 values numbers and compaction of the value space. 697VNInfo* LiveInterval::MergeValueNumberInto(VNInfo *V1, VNInfo *V2) { 698 assert(V1 != V2 && "Identical value#'s are always equivalent!"); 699 700 // This code actually merges the (numerically) larger value number into the 701 // smaller value number, which is likely to allow us to compactify the value 702 // space. The only thing we have to be careful of is to preserve the 703 // instruction that defines the result value. 704 705 // Make sure V2 is smaller than V1. 706 if (V1->id < V2->id) { 707 V1->copyFrom(*V2); 708 std::swap(V1, V2); 709 } 710 711 // Merge V1 live ranges into V2. 712 for (iterator I = begin(); I != end(); ) { 713 iterator LR = I++; 714 if (LR->valno != V1) continue; // Not a V1 LiveRange. 715 716 // Okay, we found a V1 live range. If it had a previous, touching, V2 live 717 // range, extend it. 718 if (LR != begin()) { 719 iterator Prev = LR-1; 720 if (Prev->valno == V2 && Prev->end == LR->start) { 721 Prev->end = LR->end; 722 723 // Erase this live-range. 724 ranges.erase(LR); 725 I = Prev+1; 726 LR = Prev; 727 } 728 } 729 730 // Okay, now we have a V1 or V2 live range that is maximally merged forward. 731 // Ensure that it is a V2 live-range. 732 LR->valno = V2; 733 734 // If we can merge it into later V2 live ranges, do so now. We ignore any 735 // following V1 live ranges, as they will be merged in subsequent iterations 736 // of the loop. 737 if (I != end()) { 738 if (I->start == LR->end && I->valno == V2) { 739 LR->end = I->end; 740 ranges.erase(I); 741 I = LR+1; 742 } 743 } 744 } 745 746 // Now that V1 is dead, remove it. If it is the largest value number, just 747 // nuke it (and any other deleted values neighboring it), otherwise mark it as 748 // ~1U so it can be nuked later. 749 if (V1->id == getNumValNums()-1) { 750 do { 751 VNInfo *VNI = valnos.back(); 752 valnos.pop_back(); 753 VNI->~VNInfo(); 754 } while (valnos.back()->isUnused()); 755 } else { 756 V1->setIsUnused(true); 757 } 758 759 return V2; 760} 761 762void LiveInterval::Copy(const LiveInterval &RHS, 763 MachineRegisterInfo *MRI, 764 BumpPtrAllocator &VNInfoAllocator) { 765 ranges.clear(); 766 valnos.clear(); 767 std::pair<unsigned, unsigned> Hint = MRI->getRegAllocationHint(RHS.reg); 768 MRI->setRegAllocationHint(reg, Hint.first, Hint.second); 769 770 weight = RHS.weight; 771 for (unsigned i = 0, e = RHS.getNumValNums(); i != e; ++i) { 772 const VNInfo *VNI = RHS.getValNumInfo(i); 773 createValueCopy(VNI, VNInfoAllocator); 774 } 775 for (unsigned i = 0, e = RHS.ranges.size(); i != e; ++i) { 776 const LiveRange &LR = RHS.ranges[i]; 777 addRange(LiveRange(LR.start, LR.end, getValNumInfo(LR.valno->id))); 778 } 779} 780 781unsigned LiveInterval::getSize() const { 782 unsigned Sum = 0; 783 for (const_iterator I = begin(), E = end(); I != E; ++I) 784 Sum += I->start.distance(I->end); 785 return Sum; 786} 787 788/// ComputeJoinedWeight - Set the weight of a live interval Joined 789/// after Other has been merged into it. 790void LiveInterval::ComputeJoinedWeight(const LiveInterval &Other) { 791 // If either of these intervals was spilled, the weight is the 792 // weight of the non-spilled interval. This can only happen with 793 // iterative coalescers. 794 795 if (Other.weight != HUGE_VALF) { 796 weight += Other.weight; 797 } 798 else if (weight == HUGE_VALF && 799 !TargetRegisterInfo::isPhysicalRegister(reg)) { 800 // Remove this assert if you have an iterative coalescer 801 assert(0 && "Joining to spilled interval"); 802 weight = Other.weight; 803 } 804 else { 805 // Otherwise the weight stays the same 806 // Remove this assert if you have an iterative coalescer 807 assert(0 && "Joining from spilled interval"); 808 } 809} 810 811raw_ostream& llvm::operator<<(raw_ostream& os, const LiveRange &LR) { 812 return os << '[' << LR.start << ',' << LR.end << ':' << LR.valno->id << ")"; 813} 814 815void LiveRange::dump() const { 816 errs() << *this << "\n"; 817} 818 819void LiveInterval::print(raw_ostream &OS, const TargetRegisterInfo *TRI) const { 820 if (isStackSlot()) 821 OS << "SS#" << getStackSlotIndex(); 822 else if (TRI && TargetRegisterInfo::isPhysicalRegister(reg)) 823 OS << TRI->getName(reg); 824 else 825 OS << "%reg" << reg; 826 827 OS << ',' << weight; 828 829 if (empty()) 830 OS << " EMPTY"; 831 else { 832 OS << " = "; 833 for (LiveInterval::Ranges::const_iterator I = ranges.begin(), 834 E = ranges.end(); I != E; ++I) 835 OS << *I; 836 } 837 838 // Print value number info. 839 if (getNumValNums()) { 840 OS << " "; 841 unsigned vnum = 0; 842 for (const_vni_iterator i = vni_begin(), e = vni_end(); i != e; 843 ++i, ++vnum) { 844 const VNInfo *vni = *i; 845 if (vnum) OS << " "; 846 OS << vnum << "@"; 847 if (vni->isUnused()) { 848 OS << "x"; 849 } else { 850 if (!vni->isDefAccurate() && !vni->isPHIDef()) 851 OS << "?"; 852 else 853 OS << vni->def; 854 unsigned ee = vni->kills.size(); 855 if (ee || vni->hasPHIKill()) { 856 OS << "-("; 857 for (unsigned j = 0; j != ee; ++j) { 858 OS << vni->kills[j]; 859 if (j != ee-1) 860 OS << " "; 861 } 862 if (vni->hasPHIKill()) { 863 if (ee) 864 OS << " "; 865 OS << "phi"; 866 } 867 OS << ")"; 868 } 869 } 870 } 871 } 872} 873 874void LiveInterval::dump() const { 875 errs() << *this << "\n"; 876} 877 878 879void LiveRange::print(raw_ostream &os) const { 880 os << *this; 881} 882