lib/CodeGen/LiveInterval.cpp

   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 "RegisterCoalescer.h"
  31 #include <algorithm>
  32 using namespace llvm;
  33
  34 LiveInterval::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 = ranges.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
  52 VNInfo *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     ranges.push_back(LiveRange(Def, Def.getDeadSlot(), VNI));
  59     return VNI;
  60   }
  61   if (SlotIndex::isSameInstr(Def, I->start)) {
  62     assert(I->start == Def && "Cannot insert def, already live");
  63     assert(I->valno->def == Def && "Inconsistent existing value def");
  64     return I->valno;
  65   }
  66   assert(SlotIndex::isEarlierInstr(Def, I->start) && "Already live at def");
  67   VNInfo *VNI = getNextValue(Def, VNInfoAllocator);
  68   ranges.insert(I, LiveRange(Def, Def.getDeadSlot(), VNI));
  69   return VNI;
  70 }
  71
  72 /// killedInRange - Return true if the interval has kills in [Start,End).
  73 bool LiveInterval::killedInRange(SlotIndex Start, SlotIndex End) const {
  74   Ranges::const_iterator r =
  75     std::lower_bound(ranges.begin(), ranges.end(), End);
  76
  77   // Now r points to the first interval with start >= End, or ranges.end().
  78   if (r == ranges.begin())
  79     return false;
  80
  81   --r;
  82   // Now r points to the last interval with end <= End.
  83   // r->end is the kill point.
  84   return r->end >= Start && r->end < End;
  85 }
  86
  87 // overlaps - Return true if the intersection of the two live intervals is
  88 // not empty.
  89 //
  90 // An example for overlaps():
  91 //
  92 // 0: A = ...
  93 // 4: B = ...
  94 // 8: C = A + B ;; last use of A
  95 //
  96 // The live intervals should look like:
  97 //
  98 // A = [3, 11)
  99 // B = [7, x)
 100 // C = [11, y)
 101 //
 102 // A->overlaps(C) should return false since we want to be able to join
 103 // A and C.
 104 //
 105 bool LiveInterval::overlapsFrom(const LiveInterval& other,
 106                                 const_iterator StartPos) const {
 107   assert(!empty() && "empty interval");
 108   const_iterator i = begin();
 109   const_iterator ie = end();
 110   const_iterator j = StartPos;
 111   const_iterator je = other.end();
 112
 113   assert((StartPos->start <= i->start || StartPos == other.begin()) &&
 114          StartPos != other.end() && "Bogus start position hint!");
 115
 116   if (i->start < j->start) {
 117     i = std::upper_bound(i, ie, j->start);
 118     if (i != ranges.begin()) --i;
 119   } else if (j->start < i->start) {
 120     ++StartPos;
 121     if (StartPos != other.end() && StartPos->start <= i->start) {
 122       assert(StartPos < other.end() && i < end());
 123       j = std::upper_bound(j, je, i->start);
 124       if (j != other.ranges.begin()) --j;
 125     }
 126   } else {
 127     return true;
 128   }
 129
 130   if (j == je) return false;
 131
 132   while (i != ie) {
 133     if (i->start > j->start) {
 134       std::swap(i, j);
 135       std::swap(ie, je);
 136     }
 137
 138     if (i->end > j->start)
 139       return true;
 140     ++i;
 141   }
 142
 143   return false;
 144 }
 145
 146 bool LiveInterval::overlaps(const LiveInterval &Other,
 147                             const CoalescerPair &CP,
 148                             const SlotIndexes &Indexes) const {
 149   assert(!empty() && "empty interval");
 150   if (Other.empty())
 151     return false;
 152
 153   // Use binary searches to find initial positions.
 154   const_iterator I = find(Other.beginIndex());
 155   const_iterator IE = end();
 156   if (I == IE)
 157     return false;
 158   const_iterator J = Other.find(I->start);
 159   const_iterator JE = Other.end();
 160   if (J == JE)
 161     return false;
 162
 163   for (;;) {
 164     // J has just been advanced to satisfy:
 165     assert(J->end >= I->start);
 166     // Check for an overlap.
 167     if (J->start < I->end) {
 168       // I and J are overlapping. Find the later start.
 169       SlotIndex Def = std::max(I->start, J->start);
 170       // Allow the overlap if Def is a coalescable copy.
 171       if (Def.isBlock() ||
 172           !CP.isCoalescable(Indexes.getInstructionFromIndex(Def)))
 173         return true;
 174     }
 175     // Advance the iterator that ends first to check for more overlaps.
 176     if (J->end > I->end) {
 177       std::swap(I, J);
 178       std::swap(IE, JE);
 179     }
 180     // Advance J until J->end >= I->start.
 181     do
 182       if (++J == JE)
 183         return false;
 184     while (J->end < I->start);
 185   }
 186 }
 187
 188 /// overlaps - Return true if the live interval overlaps a range specified
 189 /// by [Start, End).
 190 bool LiveInterval::overlaps(SlotIndex Start, SlotIndex End) const {
 191   assert(Start < End && "Invalid range");
 192   const_iterator I = std::lower_bound(begin(), end(), End);
 193   return I != begin() && (--I)->end > Start;
 194 }
 195
 196
 197 /// ValNo is dead, remove it.  If it is the largest value number, just nuke it
 198 /// (and any other deleted values neighboring it), otherwise mark it as ~1U so
 199 /// it can be nuked later.
 200 void LiveInterval::markValNoForDeletion(VNInfo *ValNo) {
 201   if (ValNo->id == getNumValNums()-1) {
 202     do {
 203       valnos.pop_back();
 204     } while (!valnos.empty() && valnos.back()->isUnused());
 205   } else {
 206     ValNo->markUnused();
 207   }
 208 }
 209
 210 /// RenumberValues - Renumber all values in order of appearance and delete the
 211 /// remaining unused values.
 212 void LiveInterval::RenumberValues(LiveIntervals &lis) {
 213   SmallPtrSet<VNInfo*, 8> Seen;
 214   valnos.clear();
 215   for (const_iterator I = begin(), E = end(); I != E; ++I) {
 216     VNInfo *VNI = I->valno;
 217     if (!Seen.insert(VNI))
 218       continue;
 219     assert(!VNI->isUnused() && "Unused valno used by live range");
 220     VNI->id = (unsigned)valnos.size();
 221     valnos.push_back(VNI);
 222   }
 223 }
 224
 225 /// extendIntervalEndTo - This method is used when we want to extend the range
 226 /// specified by I to end at the specified endpoint.  To do this, we should
 227 /// merge and eliminate all ranges that this will overlap with.  The iterator is
 228 /// not invalidated.
 229 void LiveInterval::extendIntervalEndTo(Ranges::iterator I, SlotIndex NewEnd) {
 230   assert(I != ranges.end() && "Not a valid interval!");
 231   VNInfo *ValNo = I->valno;
 232
 233   // Search for the first interval that we can't merge with.
 234   Ranges::iterator MergeTo = llvm::next(I);
 235   for (; MergeTo != ranges.end() && NewEnd >= MergeTo->end; ++MergeTo) {
 236     assert(MergeTo->valno == ValNo && "Cannot merge with differing values!");
 237   }
 238
 239   // If NewEnd was in the middle of an interval, make sure to get its endpoint.
 240   I->end = std::max(NewEnd, prior(MergeTo)->end);
 241
 242   // If the newly formed range now touches the range after it and if they have
 243   // the same value number, merge the two ranges into one range.
 244   if (MergeTo != ranges.end() && MergeTo->start <= I->end &&
 245       MergeTo->valno == ValNo) {
 246     I->end = MergeTo->end;
 247     ++MergeTo;
 248   }
 249
 250   // Erase any dead ranges.
 251   ranges.erase(llvm::next(I), MergeTo);
 252 }
 253
 254
 255 /// extendIntervalStartTo - This method is used when we want to extend the range
 256 /// specified by I to start at the specified endpoint.  To do this, we should
 257 /// merge and eliminate all ranges that this will overlap with.
 258 LiveInterval::Ranges::iterator
 259 LiveInterval::extendIntervalStartTo(Ranges::iterator I, SlotIndex NewStart) {
 260   assert(I != ranges.end() && "Not a valid interval!");
 261   VNInfo *ValNo = I->valno;
 262
 263   // Search for the first interval that we can't merge with.
 264   Ranges::iterator MergeTo = I;
 265   do {
 266     if (MergeTo == ranges.begin()) {
 267       I->start = NewStart;
 268       ranges.erase(MergeTo, I);
 269       return I;
 270     }
 271     assert(MergeTo->valno == ValNo && "Cannot merge with differing values!");
 272     --MergeTo;
 273   } while (NewStart <= MergeTo->start);
 274
 275   // If we start in the middle of another interval, just delete a range and
 276   // extend that interval.
 277   if (MergeTo->end >= NewStart && MergeTo->valno == ValNo) {
 278     MergeTo->end = I->end;
 279   } else {
 280     // Otherwise, extend the interval right after.
 281     ++MergeTo;
 282     MergeTo->start = NewStart;
 283     MergeTo->end = I->end;
 284   }
 285
 286   ranges.erase(llvm::next(MergeTo), llvm::next(I));
 287   return MergeTo;
 288 }
 289
 290 LiveInterval::iterator
 291 LiveInterval::addRangeFrom(LiveRange LR, iterator From) {
 292   SlotIndex Start = LR.start, End = LR.end;
 293   iterator it = std::upper_bound(From, ranges.end(), Start);
 294
 295   // If the inserted interval starts in the middle or right at the end of
 296   // another interval, just extend that interval to contain the range of LR.
 297   if (it != ranges.begin()) {
 298     iterator B = prior(it);
 299     if (LR.valno == B->valno) {
 300       if (B->start <= Start && B->end >= Start) {
 301         extendIntervalEndTo(B, End);
 302         return B;
 303       }
 304     } else {
 305       // Check to make sure that we are not overlapping two live ranges with
 306       // different valno's.
 307       assert(B->end <= Start &&
 308              "Cannot overlap two LiveRanges with differing ValID's"
 309              " (did you def the same reg twice in a MachineInstr?)");
 310     }
 311   }
 312
 313   // Otherwise, if this range ends in the middle of, or right next to, another
 314   // interval, merge it into that interval.
 315   if (it != ranges.end()) {
 316     if (LR.valno == it->valno) {
 317       if (it->start <= End) {
 318         it = extendIntervalStartTo(it, Start);
 319
 320         // If LR is a complete superset of an interval, we may need to grow its
 321         // endpoint as well.
 322         if (End > it->end)
 323           extendIntervalEndTo(it, End);
 324         return it;
 325       }
 326     } else {
 327       // Check to make sure that we are not overlapping two live ranges with
 328       // different valno's.
 329       assert(it->start >= End &&
 330              "Cannot overlap two LiveRanges with differing ValID's");
 331     }
 332   }
 333
 334   // Otherwise, this is just a new range that doesn't interact with anything.
 335   // Insert it.
 336   return ranges.insert(it, LR);
 337 }
 338
 339 /// extendInBlock - If this interval is live before Kill in the basic
 340 /// block that starts at StartIdx, extend it to be live up to Kill and return
 341 /// the value. If there is no live range before Kill, return NULL.
 342 VNInfo *LiveInterval::extendInBlock(SlotIndex StartIdx, SlotIndex Kill) {
 343   if (empty())
 344     return 0;
 345   iterator I = std::upper_bound(begin(), end(), Kill.getPrevSlot());
 346   if (I == begin())
 347     return 0;
 348   --I;
 349   if (I->end <= StartIdx)
 350     return 0;
 351   if (I->end < Kill)
 352     extendIntervalEndTo(I, Kill);
 353   return I->valno;
 354 }
 355
 356 /// removeRange - Remove the specified range from this interval.  Note that
 357 /// the range must be in a single LiveRange in its entirety.
 358 void LiveInterval::removeRange(SlotIndex Start, SlotIndex End,
 359                                bool RemoveDeadValNo) {
 360   // Find the LiveRange containing this span.
 361   Ranges::iterator I = find(Start);
 362   assert(I != ranges.end() && "Range is not in interval!");
 363   assert(I->containsRange(Start, End) && "Range is not entirely in interval!");
 364
 365   // If the span we are removing is at the start of the LiveRange, adjust it.
 366   VNInfo *ValNo = I->valno;
 367   if (I->start == Start) {
 368     if (I->end == End) {
 369       if (RemoveDeadValNo) {
 370         // Check if val# is dead.
 371         bool isDead = true;
 372         for (const_iterator II = begin(), EE = end(); II != EE; ++II)
 373           if (II != I && II->valno == ValNo) {
 374             isDead = false;
 375             break;
 376           }
 377         if (isDead) {
 378           // Now that ValNo is dead, remove it.
 379           markValNoForDeletion(ValNo);
 380         }
 381       }
 382
 383       ranges.erase(I);  // Removed the whole LiveRange.
 384     } else
 385       I->start = End;
 386     return;
 387   }
 388
 389   // Otherwise if the span we are removing is at the end of the LiveRange,
 390   // adjust the other way.
 391   if (I->end == End) {
 392     I->end = Start;
 393     return;
 394   }
 395
 396   // Otherwise, we are splitting the LiveRange into two pieces.
 397   SlotIndex OldEnd = I->end;
 398   I->end = Start;   // Trim the old interval.
 399
 400   // Insert the new one.
 401   ranges.insert(llvm::next(I), LiveRange(End, OldEnd, ValNo));
 402 }
 403
 404 /// removeValNo - Remove all the ranges defined by the specified value#.
 405 /// Also remove the value# from value# list.
 406 void LiveInterval::removeValNo(VNInfo *ValNo) {
 407   if (empty()) return;
 408   Ranges::iterator I = ranges.end();
 409   Ranges::iterator E = ranges.begin();
 410   do {
 411     --I;
 412     if (I->valno == ValNo)
 413       ranges.erase(I);
 414   } while (I != E);
 415   // Now that ValNo is dead, remove it.
 416   markValNoForDeletion(ValNo);
 417 }
 418
 419 /// join - Join two live intervals (this, and other) together.  This applies
 420 /// mappings to the value numbers in the LHS/RHS intervals as specified.  If
 421 /// the intervals are not joinable, this aborts.
 422 void LiveInterval::join(LiveInterval &Other,
 423                         const int *LHSValNoAssignments,
 424                         const int *RHSValNoAssignments,
 425                         SmallVector<VNInfo*, 16> &NewVNInfo,
 426                         MachineRegisterInfo *MRI) {
 427   verify();
 428
 429   // Determine if any of our live range values are mapped.  This is uncommon, so
 430   // we want to avoid the interval scan if not.
 431   bool MustMapCurValNos = false;
 432   unsigned NumVals = getNumValNums();
 433   unsigned NumNewVals = NewVNInfo.size();
 434   for (unsigned i = 0; i != NumVals; ++i) {
 435     unsigned LHSValID = LHSValNoAssignments[i];
 436     if (i != LHSValID ||
 437         (NewVNInfo[LHSValID] && NewVNInfo[LHSValID] != getValNumInfo(i))) {
 438       MustMapCurValNos = true;
 439       break;
 440     }
 441   }
 442
 443   // If we have to apply a mapping to our base interval assignment, rewrite it
 444   // now.
 445   if (MustMapCurValNos) {
 446     // Map the first live range.
 447
 448     iterator OutIt = begin();
 449     OutIt->valno = NewVNInfo[LHSValNoAssignments[OutIt->valno->id]];
 450     for (iterator I = next(OutIt), E = end(); I != E; ++I) {
 451       VNInfo* nextValNo = NewVNInfo[LHSValNoAssignments[I->valno->id]];
 452       assert(nextValNo != 0 && "Huh?");
 453
 454       // If this live range has the same value # as its immediate predecessor,
 455       // and if they are neighbors, remove one LiveRange.  This happens when we
 456       // have [0,4:0)[4,7:1) and map 0/1 onto the same value #.
 457       if (OutIt->valno == nextValNo && OutIt->end == I->start) {
 458         OutIt->end = I->end;
 459       } else {
 460         // Didn't merge. Move OutIt to the next interval,
 461         ++OutIt;
 462         OutIt->valno = nextValNo;
 463         if (OutIt != I) {
 464           OutIt->start = I->start;
 465           OutIt->end = I->end;
 466         }
 467       }
 468     }
 469     // If we merge some live ranges, chop off the end.
 470     ++OutIt;
 471     ranges.erase(OutIt, end());
 472   }
 473
 474   // Remember assignements because val# ids are changing.
 475   SmallVector<unsigned, 16> OtherAssignments;
 476   for (iterator I = Other.begin(), E = Other.end(); I != E; ++I)
 477     OtherAssignments.push_back(RHSValNoAssignments[I->valno->id]);
 478
 479   // Update val# info. Renumber them and make sure they all belong to this
 480   // LiveInterval now. Also remove dead val#'s.
 481   unsigned NumValNos = 0;
 482   for (unsigned i = 0; i < NumNewVals; ++i) {
 483     VNInfo *VNI = NewVNInfo[i];
 484     if (VNI) {
 485       if (NumValNos >= NumVals)
 486         valnos.push_back(VNI);
 487       else
 488         valnos[NumValNos] = VNI;
 489       VNI->id = NumValNos++;  // Renumber val#.
 490     }
 491   }
 492   if (NumNewVals < NumVals)
 493     valnos.resize(NumNewVals);  // shrinkify
 494
 495   // Okay, now insert the RHS live ranges into the LHS.
 496   unsigned RangeNo = 0;
 497   for (iterator I = Other.begin(), E = Other.end(); I != E; ++I, ++RangeNo) {
 498     // Map the valno in the other live range to the current live range.
 499     I->valno = NewVNInfo[OtherAssignments[RangeNo]];
 500     assert(I->valno && "Adding a dead range?");
 501   }
 502   mergeIntervalRanges(Other);
 503
 504   verify();
 505 }
 506
 507 /// \brief Helper function for merging in another LiveInterval's ranges.
 508 ///
 509 /// This is a helper routine implementing an efficient merge of another
 510 /// LiveIntervals ranges into the current interval.
 511 ///
 512 /// \param LHSValNo If non-NULL, set as the new value number for every range
 513 ///                 from RHS which is merged into the LHS.
 514 /// \param RHSValNo If non-NULL, then only ranges in RHS whose original value
 515 ///                 number maches this value number will be merged into LHS.
 516 void LiveInterval::mergeIntervalRanges(const LiveInterval &RHS,
 517                                        VNInfo *LHSValNo,
 518                                        const VNInfo *RHSValNo) {
 519   if (RHS.empty())
 520     return;
 521
 522   // Ensure we're starting with a valid range. Note that we don't verify RHS
 523   // because it may have had its value numbers adjusted in preparation for
 524   // merging.
 525   verify();
 526
 527   // The strategy for merging these efficiently is as follows:
 528   //
 529   // 1) Find the beginning of the impacted ranges in the LHS.
 530   // 2) Create a new, merged sub-squence of ranges merging from the position in
 531   //    #1 until either LHS or RHS is exhausted. Any part of LHS between RHS
 532   //    entries being merged will be copied into this new range.
 533   // 3) Replace the relevant section in LHS with these newly merged ranges.
 534   // 4) Append any remaning ranges from RHS if LHS is exhausted in #2.
 535   //
 536   // We don't follow the typical in-place merge strategy for sorted ranges of
 537   // appending the new ranges to the back and then using std::inplace_merge
 538   // because one step of the merge can both mutate the original elements and
 539   // remove elements from the original. Essentially, because the merge includes
 540   // collapsing overlapping ranges, a more complex approach is required.
 541
 542   // We do an initial binary search to optimize for a common pattern: a large
 543   // LHS, and a very small RHS.
 544   const_iterator RI = RHS.begin(), RE = RHS.end();
 545   iterator LE = end(), LI = std::upper_bound(begin(), LE, *RI);
 546
 547   // Merge into NewRanges until one of the ranges is exhausted.
 548   SmallVector<LiveRange, 4> NewRanges;
 549
 550   // Keep track of where to begin the replacement.
 551   iterator ReplaceI = LI;
 552
 553   // If there are preceding ranges in the LHS, put the last one into NewRanges
 554   // so we can optionally extend it. Adjust the replacement point accordingly.
 555   if (LI != begin()) {
 556     ReplaceI = llvm::prior(LI);
 557     NewRanges.push_back(*ReplaceI);
 558   }
 559
 560   // Now loop over the mergable portions of both LHS and RHS, merging into
 561   // NewRanges.
 562   while (LI != LE && RI != RE) {
 563     // Skip incoming ranges with the wrong value.
 564     if (RHSValNo && RI->valno != RHSValNo) {
 565       ++RI;
 566       continue;
 567     }
 568
 569     // Select the first range. We pick the earliest start point, and then the
 570     // largest range.
 571     LiveRange R = *LI;
 572     if (*RI < R) {
 573       R = *RI;
 574       ++RI;
 575       if (LHSValNo)
 576         R.valno = LHSValNo;
 577     } else {
 578       ++LI;
 579     }
 580
 581     if (NewRanges.empty()) {
 582       NewRanges.push_back(R);
 583       continue;
 584     }
 585
 586     LiveRange &LastR = NewRanges.back();
 587     if (R.valno == LastR.valno) {
 588       // Try to merge this range into the last one.
 589       if (R.start <= LastR.end) {
 590         LastR.end = std::max(LastR.end, R.end);
 591         continue;
 592       }
 593     } else {
 594       // We can't merge ranges across a value number.
 595       assert(R.start >= LastR.end &&
 596              "Cannot overlap two LiveRanges with differing ValID's");
 597     }
 598
 599     // If all else fails, just append the range.
 600     NewRanges.push_back(R);
 601   }
 602   assert(RI == RE || LI == LE);
 603
 604   // Check for being able to merge into the trailing sequence of ranges on the LHS.
 605   if (!NewRanges.empty())
 606     for (; LI != LE && (LI->valno == NewRanges.back().valno &&
 607                         LI->start <= NewRanges.back().end);
 608          ++LI)
 609       NewRanges.back().end = std::max(NewRanges.back().end, LI->end);
 610
 611   // Replace the ranges in the LHS with the newly merged ones. It would be
 612   // really nice if there were a move-supporting 'replace' directly in
 613   // SmallVector, but as there is not, we pay the price of copies to avoid
 614   // wasted memory allocations.
 615   SmallVectorImpl<LiveRange>::iterator NRI = NewRanges.begin(),
 616                                        NRE = NewRanges.end();
 617   for (; ReplaceI != LI && NRI != NRE; ++ReplaceI, ++NRI)
 618     *ReplaceI = *NRI;
 619   if (NRI == NRE)
 620     ranges.erase(ReplaceI, LI);
 621   else
 622     ranges.insert(LI, NRI, NRE);
 623
 624   // And finally insert any trailing end of RHS (if we have one).
 625   for (; RI != RE; ++RI) {
 626     LiveRange R = *RI;
 627     if (LHSValNo)
 628       R.valno = LHSValNo;
 629     if (!ranges.empty() &&
 630         ranges.back().valno == R.valno && R.start <= ranges.back().end)
 631       ranges.back().end = std::max(ranges.back().end, R.end);
 632     else
 633       ranges.push_back(R);
 634   }
 635
 636   // Ensure we finished with a valid new sequence of ranges.
 637   verify();
 638 }
 639
 640 /// MergeRangesInAsValue - Merge all of the intervals in RHS into this live
 641 /// interval as the specified value number.  The LiveRanges in RHS are
 642 /// allowed to overlap with LiveRanges in the current interval, but only if
 643 /// the overlapping LiveRanges have the specified value number.
 644 void LiveInterval::MergeRangesInAsValue(const LiveInterval &RHS,
 645                                         VNInfo *LHSValNo) {
 646   mergeIntervalRanges(RHS, LHSValNo);
 647 }
 648
 649 /// MergeValueInAsValue - Merge all of the live ranges of a specific val#
 650 /// in RHS into this live interval as the specified value number.
 651 /// The LiveRanges in RHS are allowed to overlap with LiveRanges in the
 652 /// current interval, it will replace the value numbers of the overlaped
 653 /// live ranges with the specified value number.
 654 void LiveInterval::MergeValueInAsValue(const LiveInterval &RHS,
 655                                        const VNInfo *RHSValNo,
 656                                        VNInfo *LHSValNo) {
 657   mergeIntervalRanges(RHS, LHSValNo, RHSValNo);
 658 }
 659
 660 /// MergeValueNumberInto - This method is called when two value nubmers
 661 /// are found to be equivalent.  This eliminates V1, replacing all
 662 /// LiveRanges with the V1 value number with the V2 value number.  This can
 663 /// cause merging of V1/V2 values numbers and compaction of the value space.
 664 VNInfo* LiveInterval::MergeValueNumberInto(VNInfo *V1, VNInfo *V2) {
 665   assert(V1 != V2 && "Identical value#'s are always equivalent!");
 666
 667   // This code actually merges the (numerically) larger value number into the
 668   // smaller value number, which is likely to allow us to compactify the value
 669   // space.  The only thing we have to be careful of is to preserve the
 670   // instruction that defines the result value.
 671
 672   // Make sure V2 is smaller than V1.
 673   if (V1->id < V2->id) {
 674     V1->copyFrom(*V2);
 675     std::swap(V1, V2);
 676   }
 677
 678   // Merge V1 live ranges into V2.
 679   for (iterator I = begin(); I != end(); ) {
 680     iterator LR = I++;
 681     if (LR->valno != V1) continue;  // Not a V1 LiveRange.
 682
 683     // Okay, we found a V1 live range.  If it had a previous, touching, V2 live
 684     // range, extend it.
 685     if (LR != begin()) {
 686       iterator Prev = LR-1;
 687       if (Prev->valno == V2 && Prev->end == LR->start) {
 688         Prev->end = LR->end;
 689
 690         // Erase this live-range.
 691         ranges.erase(LR);
 692         I = Prev+1;
 693         LR = Prev;
 694       }
 695     }
 696
 697     // Okay, now we have a V1 or V2 live range that is maximally merged forward.
 698     // Ensure that it is a V2 live-range.
 699     LR->valno = V2;
 700
 701     // If we can merge it into later V2 live ranges, do so now.  We ignore any
 702     // following V1 live ranges, as they will be merged in subsequent iterations
 703     // of the loop.
 704     if (I != end()) {
 705       if (I->start == LR->end && I->valno == V2) {
 706         LR->end = I->end;
 707         ranges.erase(I);
 708         I = LR+1;
 709       }
 710     }
 711   }
 712
 713   // Now that V1 is dead, remove it.
 714   markValNoForDeletion(V1);
 715
 716   return V2;
 717 }
 718
 719 void LiveInterval::Copy(const LiveInterval &RHS,
 720                         MachineRegisterInfo *MRI,
 721                         VNInfo::Allocator &VNInfoAllocator) {
 722   ranges.clear();
 723   valnos.clear();
 724   std::pair<unsigned, unsigned> Hint = MRI->getRegAllocationHint(RHS.reg);
 725   MRI->setRegAllocationHint(reg, Hint.first, Hint.second);
 726
 727   weight = RHS.weight;
 728   for (unsigned i = 0, e = RHS.getNumValNums(); i != e; ++i) {
 729     const VNInfo *VNI = RHS.getValNumInfo(i);
 730     createValueCopy(VNI, VNInfoAllocator);
 731   }
 732   for (unsigned i = 0, e = RHS.ranges.size(); i != e; ++i) {
 733     const LiveRange &LR = RHS.ranges[i];
 734     addRange(LiveRange(LR.start, LR.end, getValNumInfo(LR.valno->id)));
 735   }
 736
 737   verify();
 738 }
 739
 740 unsigned LiveInterval::getSize() const {
 741   unsigned Sum = 0;
 742   for (const_iterator I = begin(), E = end(); I != E; ++I)
 743     Sum += I->start.distance(I->end);
 744   return Sum;
 745 }
 746
 747 raw_ostream& llvm::operator<<(raw_ostream& os, const LiveRange &LR) {
 748   return os << '[' << LR.start << ',' << LR.end << ':' << LR.valno->id << ")";
 749 }
 750
 751 void LiveRange::dump() const {
 752   dbgs() << *this << "\n";
 753 }
 754
 755 void LiveInterval::print(raw_ostream &OS) const {
 756   if (empty())
 757     OS << "EMPTY";
 758   else {
 759     for (LiveInterval::Ranges::const_iterator I = ranges.begin(),
 760            E = ranges.end(); I != E; ++I) {
 761       OS << *I;
 762       assert(I->valno == getValNumInfo(I->valno->id) && "Bad VNInfo");
 763     }
 764   }
 765
 766   // Print value number info.
 767   if (getNumValNums()) {
 768     OS << "  ";
 769     unsigned vnum = 0;
 770     for (const_vni_iterator i = vni_begin(), e = vni_end(); i != e;
 771          ++i, ++vnum) {
 772       const VNInfo *vni = *i;
 773       if (vnum) OS << " ";
 774       OS << vnum << "@";
 775       if (vni->isUnused()) {
 776         OS << "x";
 777       } else {
 778         OS << vni->def;
 779         if (vni->isPHIDef())
 780           OS << "-phi";
 781       }
 782     }
 783   }
 784 }
 785
 786 void LiveInterval::dump() const {
 787   dbgs() << *this << "\n";
 788 }
 789
 790 #ifndef NDEBUG
 791 void LiveInterval::verify() const {
 792   for (const_iterator I = begin(), E = end(); I != E; ++I) {
 793     assert(I->start.isValid());
 794     assert(I->end.isValid());
 795     assert(I->start < I->end);
 796     assert(I->valno != 0);
 797     assert(I->valno == valnos[I->valno->id]);
 798     if (llvm::next(I) != E) {
 799       assert(I->end <= llvm::next(I)->start);
 800       if (I->end == llvm::next(I)->start)
 801         assert(I->valno != llvm::next(I)->valno);
 802     }
 803   }
 804 }
 805 #endif
 806
 807
 808 void LiveRange::print(raw_ostream &os) const {
 809   os << *this;
 810 }
 811
 812 unsigned ConnectedVNInfoEqClasses::Classify(const LiveInterval *LI) {
 813   // Create initial equivalence classes.
 814   EqClass.clear();
 815   EqClass.grow(LI->getNumValNums());
 816
 817   const VNInfo *used = 0, *unused = 0;
 818
 819   // Determine connections.
 820   for (LiveInterval::const_vni_iterator I = LI->vni_begin(), E = LI->vni_end();
 821        I != E; ++I) {
 822     const VNInfo *VNI = *I;
 823     // Group all unused values into one class.
 824     if (VNI->isUnused()) {
 825       if (unused)
 826         EqClass.join(unused->id, VNI->id);
 827       unused = VNI;
 828       continue;
 829     }
 830     used = VNI;
 831     if (VNI->isPHIDef()) {
 832       const MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def);
 833       assert(MBB && "Phi-def has no defining MBB");
 834       // Connect to values live out of predecessors.
 835       for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
 836            PE = MBB->pred_end(); PI != PE; ++PI)
 837         if (const VNInfo *PVNI = LI->getVNInfoBefore(LIS.getMBBEndIdx(*PI)))
 838           EqClass.join(VNI->id, PVNI->id);
 839     } else {
 840       // Normal value defined by an instruction. Check for two-addr redef.
 841       // FIXME: This could be coincidental. Should we really check for a tied
 842       // operand constraint?
 843       // Note that VNI->def may be a use slot for an early clobber def.
 844       if (const VNInfo *UVNI = LI->getVNInfoBefore(VNI->def))
 845         EqClass.join(VNI->id, UVNI->id);
 846     }
 847   }
 848
 849   // Lump all the unused values in with the last used value.
 850   if (used && unused)
 851     EqClass.join(used->id, unused->id);
 852
 853   EqClass.compress();
 854   return EqClass.getNumClasses();
 855 }
 856
 857 void ConnectedVNInfoEqClasses::Distribute(LiveInterval *LIV[],
 858                                           MachineRegisterInfo &MRI) {
 859   assert(LIV[0] && "LIV[0] must be set");
 860   LiveInterval &LI = *LIV[0];
 861
 862   // Rewrite instructions.
 863   for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(LI.reg),
 864        RE = MRI.reg_end(); RI != RE;) {
 865     MachineOperand &MO = RI.getOperand();
 866     MachineInstr *MI = MO.getParent();
 867     ++RI;
 868     // DBG_VALUE instructions should have been eliminated earlier.
 869     LiveRangeQuery LRQ(LI, LIS.getInstructionIndex(MI));
 870     const VNInfo *VNI = MO.readsReg() ? LRQ.valueIn() : LRQ.valueDefined();
 871     // In the case of an <undef> use that isn't tied to any def, VNI will be
 872     // NULL. If the use is tied to a def, VNI will be the defined value.
 873     if (!VNI)
 874       continue;
 875     MO.setReg(LIV[getEqClass(VNI)]->reg);
 876   }
 877
 878   // Move runs to new intervals.
 879   LiveInterval::iterator J = LI.begin(), E = LI.end();
 880   while (J != E && EqClass[J->valno->id] == 0)
 881     ++J;
 882   for (LiveInterval::iterator I = J; I != E; ++I) {
 883     if (unsigned eq = EqClass[I->valno->id]) {
 884       assert((LIV[eq]->empty() || LIV[eq]->expiredAt(I->start)) &&
 885              "New intervals should be empty");
 886       LIV[eq]->ranges.push_back(*I);
 887     } else
 888       *J++ = *I;
 889   }
 890   LI.ranges.erase(J, E);
 891
 892   // Transfer VNInfos to their new owners and renumber them.
 893   unsigned j = 0, e = LI.getNumValNums();
 894   while (j != e && EqClass[j] == 0)
 895     ++j;
 896   for (unsigned i = j; i != e; ++i) {
 897     VNInfo *VNI = LI.getValNumInfo(i);
 898     if (unsigned eq = EqClass[i]) {
 899       VNI->id = LIV[eq]->getNumValNums();
 900       LIV[eq]->valnos.push_back(VNI);
 901     } else {
 902       VNI->id = j;
 903       LI.valnos[j++] = VNI;
 904     }
 905   }
 906   LI.valnos.resize(j);
 907 }