LiveInterval.cpp revision 331de11a0acc6a095b98914b5f05ff242c9d7819
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 LiveInterval class. 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 segment is represented as an instance of Segment, and the whole 17// range is represented as an instance of LiveInterval. 18// 19//===----------------------------------------------------------------------===// 20 21#include "llvm/CodeGen/LiveInterval.h" 22#include "RegisterCoalescer.h" 23#include "llvm/ADT/DenseMap.h" 24#include "llvm/ADT/STLExtras.h" 25#include "llvm/ADT/SmallSet.h" 26#include "llvm/CodeGen/LiveIntervalAnalysis.h" 27#include "llvm/CodeGen/MachineRegisterInfo.h" 28#include "llvm/Support/Debug.h" 29#include "llvm/Support/raw_ostream.h" 30#include "llvm/Target/TargetRegisterInfo.h" 31#include <algorithm> 32using namespace llvm; 33 34LiveInterval::iterator LiveInterval::find(SlotIndex Pos) { 35 // This algorithm is basically std::upper_bound. 36 // Unfortunately, std::upper_bound cannot be used with mixed types until we 37 // adopt C++0x. Many libraries can do it, but not all. 38 if (empty() || Pos >= endIndex()) 39 return end(); 40 iterator I = begin(); 41 size_t Len = size(); 42 do { 43 size_t Mid = Len >> 1; 44 if (Pos < I[Mid].end) 45 Len = Mid; 46 else 47 I += Mid + 1, Len -= Mid + 1; 48 } while (Len); 49 return I; 50} 51 52VNInfo *LiveInterval::createDeadDef(SlotIndex Def, 53 VNInfo::Allocator &VNInfoAllocator) { 54 assert(!Def.isDead() && "Cannot define a value at the dead slot"); 55 iterator I = find(Def); 56 if (I == end()) { 57 VNInfo *VNI = getNextValue(Def, VNInfoAllocator); 58 segments.push_back(Segment(Def, Def.getDeadSlot(), VNI)); 59 return VNI; 60 } 61 if (SlotIndex::isSameInstr(Def, I->start)) { 62 assert(I->valno->def == I->start && "Inconsistent existing value def"); 63 64 // It is possible to have both normal and early-clobber defs of the same 65 // register on an instruction. It doesn't make a lot of sense, but it is 66 // possible to specify in inline assembly. 67 // 68 // Just convert everything to early-clobber. 69 Def = std::min(Def, I->start); 70 if (Def != I->start) 71 I->start = I->valno->def = Def; 72 return I->valno; 73 } 74 assert(SlotIndex::isEarlierInstr(Def, I->start) && "Already live at def"); 75 VNInfo *VNI = getNextValue(Def, VNInfoAllocator); 76 segments.insert(I, Segment(Def, Def.getDeadSlot(), VNI)); 77 return VNI; 78} 79 80// overlaps - Return true if the intersection of the two live intervals is 81// not empty. 82// 83// An example for overlaps(): 84// 85// 0: A = ... 86// 4: B = ... 87// 8: C = A + B ;; last use of A 88// 89// The live intervals should look like: 90// 91// A = [3, 11) 92// B = [7, x) 93// C = [11, y) 94// 95// A->overlaps(C) should return false since we want to be able to join 96// A and C. 97// 98bool LiveInterval::overlapsFrom(const LiveInterval& other, 99 const_iterator StartPos) const { 100 assert(!empty() && "empty interval"); 101 const_iterator i = begin(); 102 const_iterator ie = end(); 103 const_iterator j = StartPos; 104 const_iterator je = other.end(); 105 106 assert((StartPos->start <= i->start || StartPos == other.begin()) && 107 StartPos != other.end() && "Bogus start position hint!"); 108 109 if (i->start < j->start) { 110 i = std::upper_bound(i, ie, j->start); 111 if (i != begin()) --i; 112 } else if (j->start < i->start) { 113 ++StartPos; 114 if (StartPos != other.end() && StartPos->start <= i->start) { 115 assert(StartPos < other.end() && i < end()); 116 j = std::upper_bound(j, je, i->start); 117 if (j != other.begin()) --j; 118 } 119 } else { 120 return true; 121 } 122 123 if (j == je) return false; 124 125 while (i != ie) { 126 if (i->start > j->start) { 127 std::swap(i, j); 128 std::swap(ie, je); 129 } 130 131 if (i->end > j->start) 132 return true; 133 ++i; 134 } 135 136 return false; 137} 138 139bool LiveInterval::overlaps(const LiveInterval &Other, 140 const CoalescerPair &CP, 141 const SlotIndexes &Indexes) const { 142 assert(!empty() && "empty interval"); 143 if (Other.empty()) 144 return false; 145 146 // Use binary searches to find initial positions. 147 const_iterator I = find(Other.beginIndex()); 148 const_iterator IE = end(); 149 if (I == IE) 150 return false; 151 const_iterator J = Other.find(I->start); 152 const_iterator JE = Other.end(); 153 if (J == JE) 154 return false; 155 156 for (;;) { 157 // J has just been advanced to satisfy: 158 assert(J->end >= I->start); 159 // Check for an overlap. 160 if (J->start < I->end) { 161 // I and J are overlapping. Find the later start. 162 SlotIndex Def = std::max(I->start, J->start); 163 // Allow the overlap if Def is a coalescable copy. 164 if (Def.isBlock() || 165 !CP.isCoalescable(Indexes.getInstructionFromIndex(Def))) 166 return true; 167 } 168 // Advance the iterator that ends first to check for more overlaps. 169 if (J->end > I->end) { 170 std::swap(I, J); 171 std::swap(IE, JE); 172 } 173 // Advance J until J->end >= I->start. 174 do 175 if (++J == JE) 176 return false; 177 while (J->end < I->start); 178 } 179} 180 181/// overlaps - Return true if the live interval overlaps a segment specified 182/// by [Start, End). 183bool LiveInterval::overlaps(SlotIndex Start, SlotIndex End) const { 184 assert(Start < End && "Invalid range"); 185 const_iterator I = std::lower_bound(begin(), end(), End); 186 return I != begin() && (--I)->end > Start; 187} 188 189 190/// ValNo is dead, remove it. If it is the largest value number, just nuke it 191/// (and any other deleted values neighboring it), otherwise mark it as ~1U so 192/// it can be nuked later. 193void LiveInterval::markValNoForDeletion(VNInfo *ValNo) { 194 if (ValNo->id == getNumValNums()-1) { 195 do { 196 valnos.pop_back(); 197 } while (!valnos.empty() && valnos.back()->isUnused()); 198 } else { 199 ValNo->markUnused(); 200 } 201} 202 203/// RenumberValues - Renumber all values in order of appearance and delete the 204/// remaining unused values. 205void LiveInterval::RenumberValues() { 206 SmallPtrSet<VNInfo*, 8> Seen; 207 valnos.clear(); 208 for (const_iterator I = begin(), E = end(); I != E; ++I) { 209 VNInfo *VNI = I->valno; 210 if (!Seen.insert(VNI)) 211 continue; 212 assert(!VNI->isUnused() && "Unused valno used by live segment"); 213 VNI->id = (unsigned)valnos.size(); 214 valnos.push_back(VNI); 215 } 216} 217 218/// This method is used when we want to extend the segment specified by I to end 219/// at the specified endpoint. To do this, we should merge and eliminate all 220/// segments that this will overlap with. The iterator is not invalidated. 221void LiveInterval::extendSegmentEndTo(iterator I, SlotIndex NewEnd) { 222 assert(I != end() && "Not a valid segment!"); 223 VNInfo *ValNo = I->valno; 224 225 // Search for the first segment that we can't merge with. 226 iterator MergeTo = llvm::next(I); 227 for (; MergeTo != end() && NewEnd >= MergeTo->end; ++MergeTo) { 228 assert(MergeTo->valno == ValNo && "Cannot merge with differing values!"); 229 } 230 231 // If NewEnd was in the middle of an segment, make sure to get its endpoint. 232 I->end = std::max(NewEnd, prior(MergeTo)->end); 233 234 // If the newly formed segment now touches the segment after it and if they 235 // have the same value number, merge the two segments into one segment. 236 if (MergeTo != end() && MergeTo->start <= I->end && 237 MergeTo->valno == ValNo) { 238 I->end = MergeTo->end; 239 ++MergeTo; 240 } 241 242 // Erase any dead segments. 243 segments.erase(llvm::next(I), MergeTo); 244} 245 246 247/// This method is used when we want to extend the segment specified by I to 248/// start at the specified endpoint. To do this, we should merge and eliminate 249/// all segments that this will overlap with. 250LiveInterval::iterator 251LiveInterval::extendSegmentStartTo(iterator I, SlotIndex NewStart) { 252 assert(I != end() && "Not a valid segment!"); 253 VNInfo *ValNo = I->valno; 254 255 // Search for the first segment that we can't merge with. 256 iterator MergeTo = I; 257 do { 258 if (MergeTo == begin()) { 259 I->start = NewStart; 260 segments.erase(MergeTo, I); 261 return I; 262 } 263 assert(MergeTo->valno == ValNo && "Cannot merge with differing values!"); 264 --MergeTo; 265 } while (NewStart <= MergeTo->start); 266 267 // If we start in the middle of another segment, just delete a range and 268 // extend that segment. 269 if (MergeTo->end >= NewStart && MergeTo->valno == ValNo) { 270 MergeTo->end = I->end; 271 } else { 272 // Otherwise, extend the segment right after. 273 ++MergeTo; 274 MergeTo->start = NewStart; 275 MergeTo->end = I->end; 276 } 277 278 segments.erase(llvm::next(MergeTo), llvm::next(I)); 279 return MergeTo; 280} 281 282LiveInterval::iterator 283LiveInterval::addSegmentFrom(Segment S, iterator From) { 284 SlotIndex Start = S.start, End = S.end; 285 iterator it = std::upper_bound(From, end(), Start); 286 287 // If the inserted segment starts in the middle or right at the end of 288 // another segment, just extend that segment to contain the segment of S. 289 if (it != begin()) { 290 iterator B = prior(it); 291 if (S.valno == B->valno) { 292 if (B->start <= Start && B->end >= Start) { 293 extendSegmentEndTo(B, End); 294 return B; 295 } 296 } else { 297 // Check to make sure that we are not overlapping two live segments with 298 // different valno's. 299 assert(B->end <= Start && 300 "Cannot overlap two segments with differing ValID's" 301 " (did you def the same reg twice in a MachineInstr?)"); 302 } 303 } 304 305 // Otherwise, if this segment ends in the middle of, or right next to, another 306 // segment, merge it into that segment. 307 if (it != end()) { 308 if (S.valno == it->valno) { 309 if (it->start <= End) { 310 it = extendSegmentStartTo(it, Start); 311 312 // If S is a complete superset of a segment, we may need to grow its 313 // endpoint as well. 314 if (End > it->end) 315 extendSegmentEndTo(it, End); 316 return it; 317 } 318 } else { 319 // Check to make sure that we are not overlapping two live segments with 320 // different valno's. 321 assert(it->start >= End && 322 "Cannot overlap two segments with differing ValID's"); 323 } 324 } 325 326 // Otherwise, this is just a new segment that doesn't interact with anything. 327 // Insert it. 328 return segments.insert(it, S); 329} 330 331/// extendInBlock - If this interval is live before Kill in the basic 332/// block that starts at StartIdx, extend it to be live up to Kill and return 333/// the value. If there is no segment before Kill, return NULL. 334VNInfo *LiveInterval::extendInBlock(SlotIndex StartIdx, SlotIndex Kill) { 335 if (empty()) 336 return 0; 337 iterator I = std::upper_bound(begin(), end(), Kill.getPrevSlot()); 338 if (I == begin()) 339 return 0; 340 --I; 341 if (I->end <= StartIdx) 342 return 0; 343 if (I->end < Kill) 344 extendSegmentEndTo(I, Kill); 345 return I->valno; 346} 347 348/// Remove the specified segment from this interval. Note that the segment must 349/// be in a single Segment in its entirety. 350void LiveInterval::removeSegment(SlotIndex Start, SlotIndex End, 351 bool RemoveDeadValNo) { 352 // Find the Segment containing this span. 353 iterator I = find(Start); 354 assert(I != end() && "Segment is not in interval!"); 355 assert(I->containsInterval(Start, End) 356 && "Segment is not entirely in interval!"); 357 358 // If the span we are removing is at the start of the Segment, adjust it. 359 VNInfo *ValNo = I->valno; 360 if (I->start == Start) { 361 if (I->end == End) { 362 if (RemoveDeadValNo) { 363 // Check if val# is dead. 364 bool isDead = true; 365 for (const_iterator II = begin(), EE = end(); II != EE; ++II) 366 if (II != I && II->valno == ValNo) { 367 isDead = false; 368 break; 369 } 370 if (isDead) { 371 // Now that ValNo is dead, remove it. 372 markValNoForDeletion(ValNo); 373 } 374 } 375 376 segments.erase(I); // Removed the whole Segment. 377 } else 378 I->start = End; 379 return; 380 } 381 382 // Otherwise if the span we are removing is at the end of the Segment, 383 // adjust the other way. 384 if (I->end == End) { 385 I->end = Start; 386 return; 387 } 388 389 // Otherwise, we are splitting the Segment into two pieces. 390 SlotIndex OldEnd = I->end; 391 I->end = Start; // Trim the old interval. 392 393 // Insert the new one. 394 segments.insert(llvm::next(I), Segment(End, OldEnd, ValNo)); 395} 396 397/// removeValNo - Remove all the segments defined by the specified value#. 398/// Also remove the value# from value# list. 399void LiveInterval::removeValNo(VNInfo *ValNo) { 400 if (empty()) return; 401 iterator I = end(); 402 iterator E = begin(); 403 do { 404 --I; 405 if (I->valno == ValNo) 406 segments.erase(I); 407 } while (I != E); 408 // Now that ValNo is dead, remove it. 409 markValNoForDeletion(ValNo); 410} 411 412/// join - Join two live intervals (this, and other) together. This applies 413/// mappings to the value numbers in the LHS/RHS intervals as specified. If 414/// the intervals are not joinable, this aborts. 415void LiveInterval::join(LiveInterval &Other, 416 const int *LHSValNoAssignments, 417 const int *RHSValNoAssignments, 418 SmallVectorImpl<VNInfo *> &NewVNInfo) { 419 verify(); 420 421 // Determine if any of our values are mapped. This is uncommon, so we want 422 // to avoid the interval scan if not. 423 bool MustMapCurValNos = false; 424 unsigned NumVals = getNumValNums(); 425 unsigned NumNewVals = NewVNInfo.size(); 426 for (unsigned i = 0; i != NumVals; ++i) { 427 unsigned LHSValID = LHSValNoAssignments[i]; 428 if (i != LHSValID || 429 (NewVNInfo[LHSValID] && NewVNInfo[LHSValID] != getValNumInfo(i))) { 430 MustMapCurValNos = true; 431 break; 432 } 433 } 434 435 // If we have to apply a mapping to our base interval assignment, rewrite it 436 // now. 437 if (MustMapCurValNos && !empty()) { 438 // Map the first live range. 439 440 iterator OutIt = begin(); 441 OutIt->valno = NewVNInfo[LHSValNoAssignments[OutIt->valno->id]]; 442 for (iterator I = llvm::next(OutIt), E = end(); I != E; ++I) { 443 VNInfo* nextValNo = NewVNInfo[LHSValNoAssignments[I->valno->id]]; 444 assert(nextValNo != 0 && "Huh?"); 445 446 // If this live range has the same value # as its immediate predecessor, 447 // and if they are neighbors, remove one Segment. This happens when we 448 // have [0,4:0)[4,7:1) and map 0/1 onto the same value #. 449 if (OutIt->valno == nextValNo && OutIt->end == I->start) { 450 OutIt->end = I->end; 451 } else { 452 // Didn't merge. Move OutIt to the next interval, 453 ++OutIt; 454 OutIt->valno = nextValNo; 455 if (OutIt != I) { 456 OutIt->start = I->start; 457 OutIt->end = I->end; 458 } 459 } 460 } 461 // If we merge some segments, chop off the end. 462 ++OutIt; 463 segments.erase(OutIt, end()); 464 } 465 466 // Rewrite Other values before changing the VNInfo ids. 467 // This can leave Other in an invalid state because we're not coalescing 468 // touching segments that now have identical values. That's OK since Other is 469 // not supposed to be valid after calling join(); 470 for (iterator I = Other.begin(), E = Other.end(); I != E; ++I) 471 I->valno = NewVNInfo[RHSValNoAssignments[I->valno->id]]; 472 473 // Update val# info. Renumber them and make sure they all belong to this 474 // LiveInterval now. Also remove dead val#'s. 475 unsigned NumValNos = 0; 476 for (unsigned i = 0; i < NumNewVals; ++i) { 477 VNInfo *VNI = NewVNInfo[i]; 478 if (VNI) { 479 if (NumValNos >= NumVals) 480 valnos.push_back(VNI); 481 else 482 valnos[NumValNos] = VNI; 483 VNI->id = NumValNos++; // Renumber val#. 484 } 485 } 486 if (NumNewVals < NumVals) 487 valnos.resize(NumNewVals); // shrinkify 488 489 // Okay, now insert the RHS live segments into the LHS. 490 LiveRangeUpdater Updater(this); 491 for (iterator I = Other.begin(), E = Other.end(); I != E; ++I) 492 Updater.add(*I); 493} 494 495/// Merge all of the segments in RHS into this live interval as the specified 496/// value number. The segments in RHS are allowed to overlap with segments in 497/// the current interval, but only if the overlapping segments have the 498/// specified value number. 499void LiveInterval::MergeSegmentsInAsValue(const LiveInterval &RHS, 500 VNInfo *LHSValNo) { 501 LiveRangeUpdater Updater(this); 502 for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) 503 Updater.add(I->start, I->end, LHSValNo); 504} 505 506/// MergeValueInAsValue - Merge all of the live segments of a specific val# 507/// in RHS into this live interval as the specified value number. 508/// The segments in RHS are allowed to overlap with segments in the 509/// current interval, it will replace the value numbers of the overlaped 510/// segments with the specified value number. 511void LiveInterval::MergeValueInAsValue(const LiveInterval &RHS, 512 const VNInfo *RHSValNo, 513 VNInfo *LHSValNo) { 514 LiveRangeUpdater Updater(this); 515 for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) 516 if (I->valno == RHSValNo) 517 Updater.add(I->start, I->end, LHSValNo); 518} 519 520/// MergeValueNumberInto - This method is called when two value nubmers 521/// are found to be equivalent. This eliminates V1, replacing all 522/// segments with the V1 value number with the V2 value number. This can 523/// cause merging of V1/V2 values numbers and compaction of the value space. 524VNInfo* LiveInterval::MergeValueNumberInto(VNInfo *V1, VNInfo *V2) { 525 assert(V1 != V2 && "Identical value#'s are always equivalent!"); 526 527 // This code actually merges the (numerically) larger value number into the 528 // smaller value number, which is likely to allow us to compactify the value 529 // space. The only thing we have to be careful of is to preserve the 530 // instruction that defines the result value. 531 532 // Make sure V2 is smaller than V1. 533 if (V1->id < V2->id) { 534 V1->copyFrom(*V2); 535 std::swap(V1, V2); 536 } 537 538 // Merge V1 segments into V2. 539 for (iterator I = begin(); I != end(); ) { 540 iterator S = I++; 541 if (S->valno != V1) continue; // Not a V1 Segment. 542 543 // Okay, we found a V1 live range. If it had a previous, touching, V2 live 544 // range, extend it. 545 if (S != begin()) { 546 iterator Prev = S-1; 547 if (Prev->valno == V2 && Prev->end == S->start) { 548 Prev->end = S->end; 549 550 // Erase this live-range. 551 segments.erase(S); 552 I = Prev+1; 553 S = Prev; 554 } 555 } 556 557 // Okay, now we have a V1 or V2 live range that is maximally merged forward. 558 // Ensure that it is a V2 live-range. 559 S->valno = V2; 560 561 // If we can merge it into later V2 segments, do so now. We ignore any 562 // following V1 segments, as they will be merged in subsequent iterations 563 // of the loop. 564 if (I != end()) { 565 if (I->start == S->end && I->valno == V2) { 566 S->end = I->end; 567 segments.erase(I); 568 I = S+1; 569 } 570 } 571 } 572 573 // Now that V1 is dead, remove it. 574 markValNoForDeletion(V1); 575 576 return V2; 577} 578 579unsigned LiveInterval::getSize() const { 580 unsigned Sum = 0; 581 for (const_iterator I = begin(), E = end(); I != E; ++I) 582 Sum += I->start.distance(I->end); 583 return Sum; 584} 585 586raw_ostream& llvm::operator<<(raw_ostream& os, const LiveInterval::Segment &S) { 587 return os << '[' << S.start << ',' << S.end << ':' << S.valno->id << ")"; 588} 589 590#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 591void LiveInterval::Segment::dump() const { 592 dbgs() << *this << "\n"; 593} 594#endif 595 596void LiveInterval::print(raw_ostream &OS) const { 597 if (empty()) 598 OS << "EMPTY"; 599 else { 600 for (const_iterator I = begin(), E = end(); I != E; ++I) { 601 OS << *I; 602 assert(I->valno == getValNumInfo(I->valno->id) && "Bad VNInfo"); 603 } 604 } 605 606 // Print value number info. 607 if (getNumValNums()) { 608 OS << " "; 609 unsigned vnum = 0; 610 for (const_vni_iterator i = vni_begin(), e = vni_end(); i != e; 611 ++i, ++vnum) { 612 const VNInfo *vni = *i; 613 if (vnum) OS << " "; 614 OS << vnum << "@"; 615 if (vni->isUnused()) { 616 OS << "x"; 617 } else { 618 OS << vni->def; 619 if (vni->isPHIDef()) 620 OS << "-phi"; 621 } 622 } 623 } 624} 625 626#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 627void LiveInterval::dump() const { 628 dbgs() << *this << "\n"; 629} 630#endif 631 632#ifndef NDEBUG 633void LiveInterval::verify() const { 634 for (const_iterator I = begin(), E = end(); I != E; ++I) { 635 assert(I->start.isValid()); 636 assert(I->end.isValid()); 637 assert(I->start < I->end); 638 assert(I->valno != 0); 639 assert(I->valno == valnos[I->valno->id]); 640 if (llvm::next(I) != E) { 641 assert(I->end <= llvm::next(I)->start); 642 if (I->end == llvm::next(I)->start) 643 assert(I->valno != llvm::next(I)->valno); 644 } 645 } 646} 647#endif 648 649 650//===----------------------------------------------------------------------===// 651// LiveRangeUpdater class 652//===----------------------------------------------------------------------===// 653// 654// The LiveRangeUpdater class always maintains these invariants: 655// 656// - When LastStart is invalid, Spills is empty and the iterators are invalid. 657// This is the initial state, and the state created by flush(). 658// In this state, isDirty() returns false. 659// 660// Otherwise, segments are kept in three separate areas: 661// 662// 1. [begin; WriteI) at the front of LI. 663// 2. [ReadI; end) at the back of LI. 664// 3. Spills. 665// 666// - LI.begin() <= WriteI <= ReadI <= LI.end(). 667// - Segments in all three areas are fully ordered and coalesced. 668// - Segments in area 1 precede and can't coalesce with segments in area 2. 669// - Segments in Spills precede and can't coalesce with segments in area 2. 670// - No coalescing is possible between segments in Spills and segments in area 671// 1, and there are no overlapping segments. 672// 673// The segments in Spills are not ordered with respect to the segments in area 674// 1. They need to be merged. 675// 676// When they exist, Spills.back().start <= LastStart, 677// and WriteI[-1].start <= LastStart. 678 679void LiveRangeUpdater::print(raw_ostream &OS) const { 680 if (!isDirty()) { 681 if (LI) 682 OS << "Clean " << PrintReg(LI->reg) << " updater: " << *LI << '\n'; 683 else 684 OS << "Null updater.\n"; 685 return; 686 } 687 assert(LI && "Can't have null LI in dirty updater."); 688 OS << PrintReg(LI->reg) << " updater with gap = " << (ReadI - WriteI) 689 << ", last start = " << LastStart 690 << ":\n Area 1:"; 691 for (LiveInterval::const_iterator I = LI->begin(); I != WriteI; ++I) 692 OS << ' ' << *I; 693 OS << "\n Spills:"; 694 for (unsigned I = 0, E = Spills.size(); I != E; ++I) 695 OS << ' ' << Spills[I]; 696 OS << "\n Area 2:"; 697 for (LiveInterval::const_iterator I = ReadI, E = LI->end(); I != E; ++I) 698 OS << ' ' << *I; 699 OS << '\n'; 700} 701 702void LiveRangeUpdater::dump() const 703{ 704 print(errs()); 705} 706 707// Determine if A and B should be coalesced. 708static inline bool coalescable(const LiveInterval::Segment &A, 709 const LiveInterval::Segment &B) { 710 assert(A.start <= B.start && "Unordered live segments."); 711 if (A.end == B.start) 712 return A.valno == B.valno; 713 if (A.end < B.start) 714 return false; 715 assert(A.valno == B.valno && "Cannot overlap different values"); 716 return true; 717} 718 719void LiveRangeUpdater::add(LiveInterval::Segment Seg) { 720 assert(LI && "Cannot add to a null destination"); 721 722 // Flush the state if Start moves backwards. 723 if (!LastStart.isValid() || LastStart > Seg.start) { 724 if (isDirty()) 725 flush(); 726 // This brings us to an uninitialized state. Reinitialize. 727 assert(Spills.empty() && "Leftover spilled segments"); 728 WriteI = ReadI = LI->begin(); 729 } 730 731 // Remember start for next time. 732 LastStart = Seg.start; 733 734 // Advance ReadI until it ends after Seg.start. 735 LiveInterval::iterator E = LI->end(); 736 if (ReadI != E && ReadI->end <= Seg.start) { 737 // First try to close the gap between WriteI and ReadI with spills. 738 if (ReadI != WriteI) 739 mergeSpills(); 740 // Then advance ReadI. 741 if (ReadI == WriteI) 742 ReadI = WriteI = LI->find(Seg.start); 743 else 744 while (ReadI != E && ReadI->end <= Seg.start) 745 *WriteI++ = *ReadI++; 746 } 747 748 assert(ReadI == E || ReadI->end > Seg.start); 749 750 // Check if the ReadI segment begins early. 751 if (ReadI != E && ReadI->start <= Seg.start) { 752 assert(ReadI->valno == Seg.valno && "Cannot overlap different values"); 753 // Bail if Seg is completely contained in ReadI. 754 if (ReadI->end >= Seg.end) 755 return; 756 // Coalesce into Seg. 757 Seg.start = ReadI->start; 758 ++ReadI; 759 } 760 761 // Coalesce as much as possible from ReadI into Seg. 762 while (ReadI != E && coalescable(Seg, *ReadI)) { 763 Seg.end = std::max(Seg.end, ReadI->end); 764 ++ReadI; 765 } 766 767 // Try coalescing Spills.back() into Seg. 768 if (!Spills.empty() && coalescable(Spills.back(), Seg)) { 769 Seg.start = Spills.back().start; 770 Seg.end = std::max(Spills.back().end, Seg.end); 771 Spills.pop_back(); 772 } 773 774 // Try coalescing Seg into WriteI[-1]. 775 if (WriteI != LI->begin() && coalescable(WriteI[-1], Seg)) { 776 WriteI[-1].end = std::max(WriteI[-1].end, Seg.end); 777 return; 778 } 779 780 // Seg doesn't coalesce with anything, and needs to be inserted somewhere. 781 if (WriteI != ReadI) { 782 *WriteI++ = Seg; 783 return; 784 } 785 786 // Finally, append to LI or Spills. 787 if (WriteI == E) { 788 LI->segments.push_back(Seg); 789 WriteI = ReadI = LI->end(); 790 } else 791 Spills.push_back(Seg); 792} 793 794// Merge as many spilled segments as possible into the gap between WriteI 795// and ReadI. Advance WriteI to reflect the inserted instructions. 796void LiveRangeUpdater::mergeSpills() { 797 // Perform a backwards merge of Spills and [SpillI;WriteI). 798 size_t GapSize = ReadI - WriteI; 799 size_t NumMoved = std::min(Spills.size(), GapSize); 800 LiveInterval::iterator Src = WriteI; 801 LiveInterval::iterator Dst = Src + NumMoved; 802 LiveInterval::iterator SpillSrc = Spills.end(); 803 LiveInterval::iterator B = LI->begin(); 804 805 // This is the new WriteI position after merging spills. 806 WriteI = Dst; 807 808 // Now merge Src and Spills backwards. 809 while (Src != Dst) { 810 if (Src != B && Src[-1].start > SpillSrc[-1].start) 811 *--Dst = *--Src; 812 else 813 *--Dst = *--SpillSrc; 814 } 815 assert(NumMoved == size_t(Spills.end() - SpillSrc)); 816 Spills.erase(SpillSrc, Spills.end()); 817} 818 819void LiveRangeUpdater::flush() { 820 if (!isDirty()) 821 return; 822 // Clear the dirty state. 823 LastStart = SlotIndex(); 824 825 assert(LI && "Cannot add to a null destination"); 826 827 // Nothing to merge? 828 if (Spills.empty()) { 829 LI->segments.erase(WriteI, ReadI); 830 LI->verify(); 831 return; 832 } 833 834 // Resize the WriteI - ReadI gap to match Spills. 835 size_t GapSize = ReadI - WriteI; 836 if (GapSize < Spills.size()) { 837 // The gap is too small. Make some room. 838 size_t WritePos = WriteI - LI->begin(); 839 LI->segments.insert(ReadI, Spills.size() - GapSize, 840 LiveInterval::Segment()); 841 // This also invalidated ReadI, but it is recomputed below. 842 WriteI = LI->begin() + WritePos; 843 } else { 844 // Shrink the gap if necessary. 845 LI->segments.erase(WriteI + Spills.size(), ReadI); 846 } 847 ReadI = WriteI + Spills.size(); 848 mergeSpills(); 849 LI->verify(); 850} 851 852unsigned ConnectedVNInfoEqClasses::Classify(const LiveInterval *LI) { 853 // Create initial equivalence classes. 854 EqClass.clear(); 855 EqClass.grow(LI->getNumValNums()); 856 857 const VNInfo *used = 0, *unused = 0; 858 859 // Determine connections. 860 for (LiveInterval::const_vni_iterator I = LI->vni_begin(), E = LI->vni_end(); 861 I != E; ++I) { 862 const VNInfo *VNI = *I; 863 // Group all unused values into one class. 864 if (VNI->isUnused()) { 865 if (unused) 866 EqClass.join(unused->id, VNI->id); 867 unused = VNI; 868 continue; 869 } 870 used = VNI; 871 if (VNI->isPHIDef()) { 872 const MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def); 873 assert(MBB && "Phi-def has no defining MBB"); 874 // Connect to values live out of predecessors. 875 for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 876 PE = MBB->pred_end(); PI != PE; ++PI) 877 if (const VNInfo *PVNI = LI->getVNInfoBefore(LIS.getMBBEndIdx(*PI))) 878 EqClass.join(VNI->id, PVNI->id); 879 } else { 880 // Normal value defined by an instruction. Check for two-addr redef. 881 // FIXME: This could be coincidental. Should we really check for a tied 882 // operand constraint? 883 // Note that VNI->def may be a use slot for an early clobber def. 884 if (const VNInfo *UVNI = LI->getVNInfoBefore(VNI->def)) 885 EqClass.join(VNI->id, UVNI->id); 886 } 887 } 888 889 // Lump all the unused values in with the last used value. 890 if (used && unused) 891 EqClass.join(used->id, unused->id); 892 893 EqClass.compress(); 894 return EqClass.getNumClasses(); 895} 896 897void ConnectedVNInfoEqClasses::Distribute(LiveInterval *LIV[], 898 MachineRegisterInfo &MRI) { 899 assert(LIV[0] && "LIV[0] must be set"); 900 LiveInterval &LI = *LIV[0]; 901 902 // Rewrite instructions. 903 for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(LI.reg), 904 RE = MRI.reg_end(); RI != RE;) { 905 MachineOperand &MO = RI.getOperand(); 906 MachineInstr *MI = MO.getParent(); 907 ++RI; 908 // DBG_VALUE instructions don't have slot indexes, so get the index of the 909 // instruction before them. 910 // Normally, DBG_VALUE instructions are removed before this function is 911 // called, but it is not a requirement. 912 SlotIndex Idx; 913 if (MI->isDebugValue()) 914 Idx = LIS.getSlotIndexes()->getIndexBefore(MI); 915 else 916 Idx = LIS.getInstructionIndex(MI); 917 LiveRangeQuery LRQ(LI, Idx); 918 const VNInfo *VNI = MO.readsReg() ? LRQ.valueIn() : LRQ.valueDefined(); 919 // In the case of an <undef> use that isn't tied to any def, VNI will be 920 // NULL. If the use is tied to a def, VNI will be the defined value. 921 if (!VNI) 922 continue; 923 MO.setReg(LIV[getEqClass(VNI)]->reg); 924 } 925 926 // Move runs to new intervals. 927 LiveInterval::iterator J = LI.begin(), E = LI.end(); 928 while (J != E && EqClass[J->valno->id] == 0) 929 ++J; 930 for (LiveInterval::iterator I = J; I != E; ++I) { 931 if (unsigned eq = EqClass[I->valno->id]) { 932 assert((LIV[eq]->empty() || LIV[eq]->expiredAt(I->start)) && 933 "New intervals should be empty"); 934 LIV[eq]->segments.push_back(*I); 935 } else 936 *J++ = *I; 937 } 938 LI.segments.erase(J, E); 939 940 // Transfer VNInfos to their new owners and renumber them. 941 unsigned j = 0, e = LI.getNumValNums(); 942 while (j != e && EqClass[j] == 0) 943 ++j; 944 for (unsigned i = j; i != e; ++i) { 945 VNInfo *VNI = LI.getValNumInfo(i); 946 if (unsigned eq = EqClass[i]) { 947 VNI->id = LIV[eq]->getNumValNums(); 948 LIV[eq]->valnos.push_back(VNI); 949 } else { 950 VNI->id = j; 951 LI.valnos[j++] = VNI; 952 } 953 } 954 LI.valnos.resize(j); 955} 956