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