lib/CodeGen/LiveInterval.cpp

   1 //===-- LiveInterval.cpp - Live Interval Representation -------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source 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/STLExtras.h"
  23 #include "llvm/Support/Streams.h"
  24 #include "llvm/Target/MRegisterInfo.h"
  25 #include <algorithm>
  26 #include <map>
  27 #include <ostream>
  28 using namespace llvm;
  29
  30 // An example for liveAt():
  31 //
  32 // this = [1,4), liveAt(0) will return false. The instruction defining this
  33 // spans slots [0,3]. The interval belongs to an spilled definition of the
  34 // variable it represents. This is because slot 1 is used (def slot) and spans
  35 // up to slot 3 (store slot).
  36 //
  37 bool LiveInterval::liveAt(unsigned I) const {
  38   Ranges::const_iterator r = std::upper_bound(ranges.begin(), ranges.end(), I);
  39
  40   if (r == ranges.begin())
  41     return false;
  42
  43   --r;
  44   return r->contains(I);
  45 }
  46
  47 // overlaps - Return true if the intersection of the two live intervals is
  48 // not empty.
  49 //
  50 // An example for overlaps():
  51 //
  52 // 0: A = ...
  53 // 4: B = ...
  54 // 8: C = A + B ;; last use of A
  55 //
  56 // The live intervals should look like:
  57 //
  58 // A = [3, 11)
  59 // B = [7, x)
  60 // C = [11, y)
  61 //
  62 // A->overlaps(C) should return false since we want to be able to join
  63 // A and C.
  64 //
  65 bool LiveInterval::overlapsFrom(const LiveInterval& other,
  66                                 const_iterator StartPos) const {
  67   const_iterator i = begin();
  68   const_iterator ie = end();
  69   const_iterator j = StartPos;
  70   const_iterator je = other.end();
  71
  72   assert((StartPos->start <= i->start || StartPos == other.begin()) &&
  73          StartPos != other.end() && "Bogus start position hint!");
  74
  75   if (i->start < j->start) {
  76     i = std::upper_bound(i, ie, j->start);
  77     if (i != ranges.begin()) --i;
  78   } else if (j->start < i->start) {
  79     ++StartPos;
  80     if (StartPos != other.end() && StartPos->start <= i->start) {
  81       assert(StartPos < other.end() && i < end());
  82       j = std::upper_bound(j, je, i->start);
  83       if (j != other.ranges.begin()) --j;
  84     }
  85   } else {
  86     return true;
  87   }
  88
  89   if (j == je) return false;
  90
  91   while (i != ie) {
  92     if (i->start > j->start) {
  93       std::swap(i, j);
  94       std::swap(ie, je);
  95     }
  96
  97     if (i->end > j->start)
  98       return true;
  99     ++i;
 100   }
 101
 102   return false;
 103 }
 104
 105 /// extendIntervalEndTo - This method is used when we want to extend the range
 106 /// specified by I to end at the specified endpoint.  To do this, we should
 107 /// merge and eliminate all ranges that this will overlap with.  The iterator is
 108 /// not invalidated.
 109 void LiveInterval::extendIntervalEndTo(Ranges::iterator I, unsigned NewEnd) {
 110   assert(I != ranges.end() && "Not a valid interval!");
 111   unsigned ValId = I->ValId;
 112
 113   // Search for the first interval that we can't merge with.
 114   Ranges::iterator MergeTo = next(I);
 115   for (; MergeTo != ranges.end() && NewEnd >= MergeTo->end; ++MergeTo) {
 116     assert(MergeTo->ValId == ValId && "Cannot merge with differing values!");
 117   }
 118
 119   // If NewEnd was in the middle of an interval, make sure to get its endpoint.
 120   I->end = std::max(NewEnd, prior(MergeTo)->end);
 121
 122   // Erase any dead ranges.
 123   ranges.erase(next(I), MergeTo);
 124
 125   // If the newly formed range now touches the range after it and if they have
 126   // the same value number, merge the two ranges into one range.
 127   Ranges::iterator Next = next(I);
 128   if (Next != ranges.end() && Next->start <= I->end && Next->ValId == ValId) {
 129     I->end = Next->end;
 130     ranges.erase(Next);
 131   }
 132 }
 133
 134
 135 /// extendIntervalStartTo - This method is used when we want to extend the range
 136 /// specified by I to start at the specified endpoint.  To do this, we should
 137 /// merge and eliminate all ranges that this will overlap with.
 138 LiveInterval::Ranges::iterator
 139 LiveInterval::extendIntervalStartTo(Ranges::iterator I, unsigned NewStart) {
 140   assert(I != ranges.end() && "Not a valid interval!");
 141   unsigned ValId = I->ValId;
 142
 143   // Search for the first interval that we can't merge with.
 144   Ranges::iterator MergeTo = I;
 145   do {
 146     if (MergeTo == ranges.begin()) {
 147       I->start = NewStart;
 148       ranges.erase(MergeTo, I);
 149       return I;
 150     }
 151     assert(MergeTo->ValId == ValId && "Cannot merge with differing values!");
 152     --MergeTo;
 153   } while (NewStart <= MergeTo->start);
 154
 155   // If we start in the middle of another interval, just delete a range and
 156   // extend that interval.
 157   if (MergeTo->end >= NewStart && MergeTo->ValId == ValId) {
 158     MergeTo->end = I->end;
 159   } else {
 160     // Otherwise, extend the interval right after.
 161     ++MergeTo;
 162     MergeTo->start = NewStart;
 163     MergeTo->end = I->end;
 164   }
 165
 166   ranges.erase(next(MergeTo), next(I));
 167   return MergeTo;
 168 }
 169
 170 LiveInterval::iterator
 171 LiveInterval::addRangeFrom(LiveRange LR, iterator From) {
 172   unsigned Start = LR.start, End = LR.end;
 173   iterator it = std::upper_bound(From, ranges.end(), Start);
 174
 175   // If the inserted interval starts in the middle or right at the end of
 176   // another interval, just extend that interval to contain the range of LR.
 177   if (it != ranges.begin()) {
 178     iterator B = prior(it);
 179     if (LR.ValId == B->ValId) {
 180       if (B->start <= Start && B->end >= Start) {
 181         extendIntervalEndTo(B, End);
 182         return B;
 183       }
 184     } else {
 185       // Check to make sure that we are not overlapping two live ranges with
 186       // different ValId's.
 187       assert(B->end <= Start &&
 188              "Cannot overlap two LiveRanges with differing ValID's"
 189              " (did you def the same reg twice in a MachineInstr?)");
 190     }
 191   }
 192
 193   // Otherwise, if this range ends in the middle of, or right next to, another
 194   // interval, merge it into that interval.
 195   if (it != ranges.end())
 196     if (LR.ValId == it->ValId) {
 197       if (it->start <= End) {
 198         it = extendIntervalStartTo(it, Start);
 199
 200         // If LR is a complete superset of an interval, we may need to grow its
 201         // endpoint as well.
 202         if (End > it->end)
 203           extendIntervalEndTo(it, End);
 204         return it;
 205       }
 206     } else {
 207       // Check to make sure that we are not overlapping two live ranges with
 208       // different ValId's.
 209       assert(it->start >= End &&
 210              "Cannot overlap two LiveRanges with differing ValID's");
 211     }
 212
 213   // Otherwise, this is just a new range that doesn't interact with anything.
 214   // Insert it.
 215   return ranges.insert(it, LR);
 216 }
 217
 218
 219 /// removeRange - Remove the specified range from this interval.  Note that
 220 /// the range must already be in this interval in its entirety.
 221 void LiveInterval::removeRange(unsigned Start, unsigned End) {
 222   // Find the LiveRange containing this span.
 223   Ranges::iterator I = std::upper_bound(ranges.begin(), ranges.end(), Start);
 224   assert(I != ranges.begin() && "Range is not in interval!");
 225   --I;
 226   assert(I->contains(Start) && I->contains(End-1) &&
 227          "Range is not entirely in interval!");
 228
 229   // If the span we are removing is at the start of the LiveRange, adjust it.
 230   if (I->start == Start) {
 231     if (I->end == End)
 232       ranges.erase(I);  // Removed the whole LiveRange.
 233     else
 234       I->start = End;
 235     return;
 236   }
 237
 238   // Otherwise if the span we are removing is at the end of the LiveRange,
 239   // adjust the other way.
 240   if (I->end == End) {
 241     I->end = Start;
 242     return;
 243   }
 244
 245   // Otherwise, we are splitting the LiveRange into two pieces.
 246   unsigned OldEnd = I->end;
 247   I->end = Start;   // Trim the old interval.
 248
 249   // Insert the new one.
 250   ranges.insert(next(I), LiveRange(End, OldEnd, I->ValId));
 251 }
 252
 253 /// getLiveRangeContaining - Return the live range that contains the
 254 /// specified index, or null if there is none.
 255 LiveInterval::const_iterator
 256 LiveInterval::FindLiveRangeContaining(unsigned Idx) const {
 257   const_iterator It = std::upper_bound(begin(), end(), Idx);
 258   if (It != ranges.begin()) {
 259     --It;
 260     if (It->contains(Idx))
 261       return It;
 262   }
 263
 264   return end();
 265 }
 266
 267 LiveInterval::iterator
 268 LiveInterval::FindLiveRangeContaining(unsigned Idx) {
 269   iterator It = std::upper_bound(begin(), end(), Idx);
 270   if (It != begin()) {
 271     --It;
 272     if (It->contains(Idx))
 273       return It;
 274   }
 275
 276   return end();
 277 }
 278
 279 /// join - Join two live intervals (this, and other) together.  This applies
 280 /// mappings to the value numbers in the LHS/RHS intervals as specified.  If
 281 /// the intervals are not joinable, this aborts.
 282 void LiveInterval::join(LiveInterval &Other, int *LHSValNoAssignments,
 283                         int *RHSValNoAssignments,
 284                         SmallVector<std::pair<unsigned,
 285                                            unsigned>, 16> &NewValueNumberInfo) {
 286
 287   // Try to do the least amount of work possible.  In particular, if there are
 288   // more liverange chunks in the other set than there are in the 'this' set,
 289   // swap sets to merge the fewest chunks in possible.
 290   //
 291   // Also, if one range is a physreg and one is a vreg, we always merge from the
 292   // vreg into the physreg, which leaves the vreg intervals pristine.
 293   if ((Other.ranges.size() > ranges.size() &&
 294       MRegisterInfo::isVirtualRegister(reg)) ||
 295       MRegisterInfo::isPhysicalRegister(Other.reg)) {
 296     swap(Other);
 297     std::swap(LHSValNoAssignments, RHSValNoAssignments);
 298   }
 299
 300   // Determine if any of our live range values are mapped.  This is uncommon, so
 301   // we want to avoid the interval scan if not.
 302   bool MustMapCurValNos = false;
 303   for (unsigned i = 0, e = getNumValNums(); i != e; ++i) {
 304     if (ValueNumberInfo[i].first == ~2U) continue;  // tombstone value #
 305     if (i != (unsigned)LHSValNoAssignments[i]) {
 306       MustMapCurValNos = true;
 307       break;
 308     }
 309   }
 310
 311   // If we have to apply a mapping to our base interval assignment, rewrite it
 312   // now.
 313   if (MustMapCurValNos) {
 314     // Map the first live range.
 315     iterator OutIt = begin();
 316     OutIt->ValId = LHSValNoAssignments[OutIt->ValId];
 317     ++OutIt;
 318     for (iterator I = OutIt, E = end(); I != E; ++I) {
 319       OutIt->ValId = LHSValNoAssignments[I->ValId];
 320
 321       // If this live range has the same value # as its immediate predecessor,
 322       // and if they are neighbors, remove one LiveRange.  This happens when we
 323       // have [0,3:0)[4,7:1) and map 0/1 onto the same value #.
 324       if (OutIt->ValId == (OutIt-1)->ValId && (OutIt-1)->end == OutIt->start) {
 325         (OutIt-1)->end = OutIt->end;
 326       } else {
 327         if (I != OutIt) {
 328           OutIt->start = I->start;
 329           OutIt->end = I->end;
 330         }
 331
 332         // Didn't merge, on to the next one.
 333         ++OutIt;
 334       }
 335     }
 336
 337     // If we merge some live ranges, chop off the end.
 338     ranges.erase(OutIt, end());
 339   }
 340
 341   // Okay, now insert the RHS live ranges into the LHS.
 342   iterator InsertPos = begin();
 343   for (iterator I = Other.begin(), E = Other.end(); I != E; ++I) {
 344     // Map the ValId in the other live range to the current live range.
 345     I->ValId = RHSValNoAssignments[I->ValId];
 346     InsertPos = addRangeFrom(*I, InsertPos);
 347   }
 348
 349   ValueNumberInfo.clear();
 350   ValueNumberInfo.append(NewValueNumberInfo.begin(), NewValueNumberInfo.end());
 351   weight += Other.weight;
 352   if (Other.preference && !preference)
 353     preference = Other.preference;
 354 }
 355
 356 /// MergeRangesInAsValue - Merge all of the intervals in RHS into this live
 357 /// interval as the specified value number.  The LiveRanges in RHS are
 358 /// allowed to overlap with LiveRanges in the current interval, but only if
 359 /// the overlapping LiveRanges have the specified value number.
 360 void LiveInterval::MergeRangesInAsValue(const LiveInterval &RHS,
 361                                         unsigned LHSValNo) {
 362   // TODO: Make this more efficient.
 363   iterator InsertPos = begin();
 364   for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) {
 365     // Map the ValId in the other live range to the current live range.
 366     LiveRange Tmp = *I;
 367     Tmp.ValId = LHSValNo;
 368     InsertPos = addRangeFrom(Tmp, InsertPos);
 369   }
 370 }
 371
 372
 373 /// MergeInClobberRanges - For any live ranges that are not defined in the
 374 /// current interval, but are defined in the Clobbers interval, mark them
 375 /// used with an unknown definition value.
 376 void LiveInterval::MergeInClobberRanges(const LiveInterval &Clobbers) {
 377   if (Clobbers.begin() == Clobbers.end()) return;
 378
 379   // Find a value # to use for the clobber ranges.  If there is already a value#
 380   // for unknown values, use it.
 381   // FIXME: Use a single sentinal number for these!
 382   unsigned ClobberValNo = getNextValue(~0U, 0);
 383
 384   iterator IP = begin();
 385   for (const_iterator I = Clobbers.begin(), E = Clobbers.end(); I != E; ++I) {
 386     unsigned Start = I->start, End = I->end;
 387     IP = std::upper_bound(IP, end(), Start);
 388
 389     // If the start of this range overlaps with an existing liverange, trim it.
 390     if (IP != begin() && IP[-1].end > Start) {
 391       Start = IP[-1].end;
 392       // Trimmed away the whole range?
 393       if (Start >= End) continue;
 394     }
 395     // If the end of this range overlaps with an existing liverange, trim it.
 396     if (IP != end() && End > IP->start) {
 397       End = IP->start;
 398       // If this trimmed away the whole range, ignore it.
 399       if (Start == End) continue;
 400     }
 401
 402     // Insert the clobber interval.
 403     IP = addRangeFrom(LiveRange(Start, End, ClobberValNo), IP);
 404   }
 405 }
 406
 407 /// MergeValueNumberInto - This method is called when two value nubmers
 408 /// are found to be equivalent.  This eliminates V1, replacing all
 409 /// LiveRanges with the V1 value number with the V2 value number.  This can
 410 /// cause merging of V1/V2 values numbers and compaction of the value space.
 411 void LiveInterval::MergeValueNumberInto(unsigned V1, unsigned V2) {
 412   assert(V1 != V2 && "Identical value#'s are always equivalent!");
 413
 414   // This code actually merges the (numerically) larger value number into the
 415   // smaller value number, which is likely to allow us to compactify the value
 416   // space.  The only thing we have to be careful of is to preserve the
 417   // instruction that defines the result value.
 418
 419   // Make sure V2 is smaller than V1.
 420   if (V1 < V2) {
 421     setValueNumberInfo(V1, getValNumInfo(V2));
 422     std::swap(V1, V2);
 423   }
 424
 425   // Merge V1 live ranges into V2.
 426   for (iterator I = begin(); I != end(); ) {
 427     iterator LR = I++;
 428     if (LR->ValId != V1) continue;  // Not a V1 LiveRange.
 429
 430     // Okay, we found a V1 live range.  If it had a previous, touching, V2 live
 431     // range, extend it.
 432     if (LR != begin()) {
 433       iterator Prev = LR-1;
 434       if (Prev->ValId == V2 && Prev->end == LR->start) {
 435         Prev->end = LR->end;
 436
 437         // Erase this live-range.
 438         ranges.erase(LR);
 439         I = Prev+1;
 440         LR = Prev;
 441       }
 442     }
 443
 444     // Okay, now we have a V1 or V2 live range that is maximally merged forward.
 445     // Ensure that it is a V2 live-range.
 446     LR->ValId = V2;
 447
 448     // If we can merge it into later V2 live ranges, do so now.  We ignore any
 449     // following V1 live ranges, as they will be merged in subsequent iterations
 450     // of the loop.
 451     if (I != end()) {
 452       if (I->start == LR->end && I->ValId == V2) {
 453         LR->end = I->end;
 454         ranges.erase(I);
 455         I = LR+1;
 456       }
 457     }
 458   }
 459
 460   // Now that V1 is dead, remove it.  If it is the largest value number, just
 461   // nuke it (and any other deleted values neighboring it), otherwise mark it as
 462   // ~1U so it can be nuked later.
 463   if (V1 == getNumValNums()-1) {
 464     do {
 465       ValueNumberInfo.pop_back();
 466     } while (ValueNumberInfo.back().first == ~1U);
 467   } else {
 468     ValueNumberInfo[V1].first = ~1U;
 469   }
 470 }
 471
 472 unsigned LiveInterval::getSize() const {
 473   unsigned Sum = 0;
 474   for (const_iterator I = begin(), E = end(); I != E; ++I)
 475     Sum += I->end - I->start;
 476   return Sum;
 477 }
 478
 479 std::ostream& llvm::operator<<(std::ostream& os, const LiveRange &LR) {
 480   return os << '[' << LR.start << ',' << LR.end << ':' << LR.ValId << ")";
 481 }
 482
 483 void LiveRange::dump() const {
 484   cerr << *this << "\n";
 485 }
 486
 487 void LiveInterval::print(std::ostream &OS, const MRegisterInfo *MRI) const {
 488   if (MRI && MRegisterInfo::isPhysicalRegister(reg))
 489     OS << MRI->getName(reg);
 490   else
 491     OS << "%reg" << reg;
 492
 493   OS << ',' << weight;
 494
 495   if (empty())
 496     OS << "EMPTY";
 497   else {
 498     OS << " = ";
 499     for (LiveInterval::Ranges::const_iterator I = ranges.begin(),
 500            E = ranges.end(); I != E; ++I)
 501     OS << *I;
 502   }
 503
 504   // Print value number info.
 505   if (getNumValNums()) {
 506     OS << "  ";
 507     for (unsigned i = 0; i != getNumValNums(); ++i) {
 508       if (i) OS << " ";
 509       OS << i << "@";
 510       if (ValueNumberInfo[i].first == ~0U) {
 511         OS << "?";
 512       } else {
 513         OS << ValueNumberInfo[i].first;
 514       }
 515     }
 516   }
 517 }
 518
 519 void LiveInterval::dump() const {
 520   cerr << *this << "\n";
 521 }
 522
 523
 524 void LiveRange::print(std::ostream &os) const {
 525   os << *this;
 526 }