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