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