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