1193323Sed//===-- LiveInterval.cpp - Live Interval Representation -------------------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file implements the LiveRange and LiveInterval classes. Given some 11193323Sed// numbering of each the machine instructions an interval [i, j) is said to be a 12263508Sdim// live range for register v if there is no instruction with number j' >= j 13202375Srdivacky// such that v is live at j' and there is no instruction with number i' < i such 14263508Sdim// that v is live at i'. In this implementation ranges can have holes, 15263508Sdim// i.e. a range might look like [1,20), [50,65), [1000,1001). Each 16263508Sdim// individual segment is represented as an instance of LiveRange::Segment, 17263508Sdim// and the whole range is represented as an instance of LiveRange. 18193323Sed// 19193323Sed//===----------------------------------------------------------------------===// 20193323Sed 21193323Sed#include "llvm/CodeGen/LiveInterval.h" 22249423Sdim#include "RegisterCoalescer.h" 23249423Sdim#include "llvm/ADT/DenseMap.h" 24249423Sdim#include "llvm/ADT/STLExtras.h" 25249423Sdim#include "llvm/ADT/SmallSet.h" 26198892Srdivacky#include "llvm/CodeGen/LiveIntervalAnalysis.h" 27194612Sed#include "llvm/CodeGen/MachineRegisterInfo.h" 28202375Srdivacky#include "llvm/Support/Debug.h" 29198090Srdivacky#include "llvm/Support/raw_ostream.h" 30193323Sed#include "llvm/Target/TargetRegisterInfo.h" 31193323Sed#include <algorithm> 32193323Sedusing namespace llvm; 33193323Sed 34263508SdimLiveRange::iterator LiveRange::find(SlotIndex Pos) { 35221345Sdim // This algorithm is basically std::upper_bound. 36221345Sdim // Unfortunately, std::upper_bound cannot be used with mixed types until we 37221345Sdim // adopt C++0x. Many libraries can do it, but not all. 38221345Sdim if (empty() || Pos >= endIndex()) 39221345Sdim return end(); 40221345Sdim iterator I = begin(); 41263508Sdim size_t Len = size(); 42221345Sdim do { 43221345Sdim size_t Mid = Len >> 1; 44221345Sdim if (Pos < I[Mid].end) 45221345Sdim Len = Mid; 46221345Sdim else 47221345Sdim I += Mid + 1, Len -= Mid + 1; 48221345Sdim } while (Len); 49221345Sdim return I; 50193323Sed} 51193323Sed 52263508SdimVNInfo *LiveRange::createDeadDef(SlotIndex Def, 53263508Sdim VNInfo::Allocator &VNInfoAllocator) { 54239462Sdim assert(!Def.isDead() && "Cannot define a value at the dead slot"); 55239462Sdim iterator I = find(Def); 56239462Sdim if (I == end()) { 57239462Sdim VNInfo *VNI = getNextValue(Def, VNInfoAllocator); 58263508Sdim segments.push_back(Segment(Def, Def.getDeadSlot(), VNI)); 59239462Sdim return VNI; 60239462Sdim } 61239462Sdim if (SlotIndex::isSameInstr(Def, I->start)) { 62243830Sdim assert(I->valno->def == I->start && "Inconsistent existing value def"); 63243830Sdim 64243830Sdim // It is possible to have both normal and early-clobber defs of the same 65243830Sdim // register on an instruction. It doesn't make a lot of sense, but it is 66243830Sdim // possible to specify in inline assembly. 67243830Sdim // 68243830Sdim // Just convert everything to early-clobber. 69243830Sdim Def = std::min(Def, I->start); 70243830Sdim if (Def != I->start) 71243830Sdim I->start = I->valno->def = Def; 72239462Sdim return I->valno; 73239462Sdim } 74239462Sdim assert(SlotIndex::isEarlierInstr(Def, I->start) && "Already live at def"); 75239462Sdim VNInfo *VNI = getNextValue(Def, VNInfoAllocator); 76263508Sdim segments.insert(I, Segment(Def, Def.getDeadSlot(), VNI)); 77239462Sdim return VNI; 78239462Sdim} 79239462Sdim 80263508Sdim// overlaps - Return true if the intersection of the two live ranges is 81193323Sed// not empty. 82193323Sed// 83193323Sed// An example for overlaps(): 84193323Sed// 85193323Sed// 0: A = ... 86193323Sed// 4: B = ... 87193323Sed// 8: C = A + B ;; last use of A 88193323Sed// 89263508Sdim// The live ranges should look like: 90193323Sed// 91193323Sed// A = [3, 11) 92193323Sed// B = [7, x) 93193323Sed// C = [11, y) 94193323Sed// 95193323Sed// A->overlaps(C) should return false since we want to be able to join 96193323Sed// A and C. 97193323Sed// 98263508Sdimbool LiveRange::overlapsFrom(const LiveRange& other, 99263508Sdim const_iterator StartPos) const { 100263508Sdim assert(!empty() && "empty range"); 101193323Sed const_iterator i = begin(); 102193323Sed const_iterator ie = end(); 103193323Sed const_iterator j = StartPos; 104193323Sed const_iterator je = other.end(); 105193323Sed 106193323Sed assert((StartPos->start <= i->start || StartPos == other.begin()) && 107193323Sed StartPos != other.end() && "Bogus start position hint!"); 108193323Sed 109193323Sed if (i->start < j->start) { 110193323Sed i = std::upper_bound(i, ie, j->start); 111263508Sdim if (i != begin()) --i; 112193323Sed } else if (j->start < i->start) { 113193323Sed ++StartPos; 114193323Sed if (StartPos != other.end() && StartPos->start <= i->start) { 115193323Sed assert(StartPos < other.end() && i < end()); 116193323Sed j = std::upper_bound(j, je, i->start); 117263508Sdim if (j != other.begin()) --j; 118193323Sed } 119193323Sed } else { 120193323Sed return true; 121193323Sed } 122193323Sed 123193323Sed if (j == je) return false; 124193323Sed 125193323Sed while (i != ie) { 126193323Sed if (i->start > j->start) { 127193323Sed std::swap(i, j); 128193323Sed std::swap(ie, je); 129193323Sed } 130193323Sed 131193323Sed if (i->end > j->start) 132193323Sed return true; 133193323Sed ++i; 134193323Sed } 135193323Sed 136193323Sed return false; 137193323Sed} 138193323Sed 139263508Sdimbool LiveRange::overlaps(const LiveRange &Other, const CoalescerPair &CP, 140263508Sdim const SlotIndexes &Indexes) const { 141263508Sdim assert(!empty() && "empty range"); 142243830Sdim if (Other.empty()) 143243830Sdim return false; 144243830Sdim 145243830Sdim // Use binary searches to find initial positions. 146243830Sdim const_iterator I = find(Other.beginIndex()); 147243830Sdim const_iterator IE = end(); 148243830Sdim if (I == IE) 149243830Sdim return false; 150243830Sdim const_iterator J = Other.find(I->start); 151243830Sdim const_iterator JE = Other.end(); 152243830Sdim if (J == JE) 153243830Sdim return false; 154243830Sdim 155243830Sdim for (;;) { 156243830Sdim // J has just been advanced to satisfy: 157243830Sdim assert(J->end >= I->start); 158243830Sdim // Check for an overlap. 159243830Sdim if (J->start < I->end) { 160243830Sdim // I and J are overlapping. Find the later start. 161243830Sdim SlotIndex Def = std::max(I->start, J->start); 162243830Sdim // Allow the overlap if Def is a coalescable copy. 163243830Sdim if (Def.isBlock() || 164243830Sdim !CP.isCoalescable(Indexes.getInstructionFromIndex(Def))) 165243830Sdim return true; 166243830Sdim } 167243830Sdim // Advance the iterator that ends first to check for more overlaps. 168243830Sdim if (J->end > I->end) { 169243830Sdim std::swap(I, J); 170243830Sdim std::swap(IE, JE); 171243830Sdim } 172243830Sdim // Advance J until J->end >= I->start. 173243830Sdim do 174243830Sdim if (++J == JE) 175243830Sdim return false; 176243830Sdim while (J->end < I->start); 177243830Sdim } 178243830Sdim} 179243830Sdim 180263508Sdim/// overlaps - Return true if the live range overlaps an interval specified 181193323Sed/// by [Start, End). 182263508Sdimbool LiveRange::overlaps(SlotIndex Start, SlotIndex End) const { 183193323Sed assert(Start < End && "Invalid range"); 184210299Sed const_iterator I = std::lower_bound(begin(), end(), End); 185210299Sed return I != begin() && (--I)->end > Start; 186193323Sed} 187193323Sed 188212904Sdim 189212904Sdim/// ValNo is dead, remove it. If it is the largest value number, just nuke it 190212904Sdim/// (and any other deleted values neighboring it), otherwise mark it as ~1U so 191212904Sdim/// it can be nuked later. 192263508Sdimvoid LiveRange::markValNoForDeletion(VNInfo *ValNo) { 193212904Sdim if (ValNo->id == getNumValNums()-1) { 194212904Sdim do { 195212904Sdim valnos.pop_back(); 196212904Sdim } while (!valnos.empty() && valnos.back()->isUnused()); 197212904Sdim } else { 198239462Sdim ValNo->markUnused(); 199212904Sdim } 200212904Sdim} 201212904Sdim 202212904Sdim/// RenumberValues - Renumber all values in order of appearance and delete the 203212904Sdim/// remaining unused values. 204263508Sdimvoid LiveRange::RenumberValues() { 205212904Sdim SmallPtrSet<VNInfo*, 8> Seen; 206212904Sdim valnos.clear(); 207212904Sdim for (const_iterator I = begin(), E = end(); I != E; ++I) { 208212904Sdim VNInfo *VNI = I->valno; 209212904Sdim if (!Seen.insert(VNI)) 210212904Sdim continue; 211263508Sdim assert(!VNI->isUnused() && "Unused valno used by live segment"); 212212904Sdim VNI->id = (unsigned)valnos.size(); 213212904Sdim valnos.push_back(VNI); 214212904Sdim } 215212904Sdim} 216212904Sdim 217263508Sdim/// This method is used when we want to extend the segment specified by I to end 218263508Sdim/// at the specified endpoint. To do this, we should merge and eliminate all 219263508Sdim/// segments that this will overlap with. The iterator is not invalidated. 220263508Sdimvoid LiveRange::extendSegmentEndTo(iterator I, SlotIndex NewEnd) { 221263508Sdim assert(I != end() && "Not a valid segment!"); 222193323Sed VNInfo *ValNo = I->valno; 223193323Sed 224263508Sdim // Search for the first segment that we can't merge with. 225263508Sdim iterator MergeTo = llvm::next(I); 226263508Sdim for (; MergeTo != end() && NewEnd >= MergeTo->end; ++MergeTo) { 227193323Sed assert(MergeTo->valno == ValNo && "Cannot merge with differing values!"); 228193323Sed } 229193323Sed 230263508Sdim // If NewEnd was in the middle of a segment, make sure to get its endpoint. 231193323Sed I->end = std::max(NewEnd, prior(MergeTo)->end); 232193323Sed 233263508Sdim // If the newly formed segment now touches the segment after it and if they 234263508Sdim // have the same value number, merge the two segments into one segment. 235263508Sdim if (MergeTo != end() && MergeTo->start <= I->end && 236239462Sdim MergeTo->valno == ValNo) { 237239462Sdim I->end = MergeTo->end; 238239462Sdim ++MergeTo; 239193323Sed } 240239462Sdim 241263508Sdim // Erase any dead segments. 242263508Sdim segments.erase(llvm::next(I), MergeTo); 243193323Sed} 244193323Sed 245193323Sed 246263508Sdim/// This method is used when we want to extend the segment specified by I to 247263508Sdim/// start at the specified endpoint. To do this, we should merge and eliminate 248263508Sdim/// all segments that this will overlap with. 249263508SdimLiveRange::iterator 250263508SdimLiveRange::extendSegmentStartTo(iterator I, SlotIndex NewStart) { 251263508Sdim assert(I != end() && "Not a valid segment!"); 252193323Sed VNInfo *ValNo = I->valno; 253193323Sed 254263508Sdim // Search for the first segment that we can't merge with. 255263508Sdim iterator MergeTo = I; 256193323Sed do { 257263508Sdim if (MergeTo == begin()) { 258193323Sed I->start = NewStart; 259263508Sdim segments.erase(MergeTo, I); 260193323Sed return I; 261193323Sed } 262193323Sed assert(MergeTo->valno == ValNo && "Cannot merge with differing values!"); 263193323Sed --MergeTo; 264193323Sed } while (NewStart <= MergeTo->start); 265193323Sed 266263508Sdim // If we start in the middle of another segment, just delete a range and 267263508Sdim // extend that segment. 268193323Sed if (MergeTo->end >= NewStart && MergeTo->valno == ValNo) { 269193323Sed MergeTo->end = I->end; 270193323Sed } else { 271263508Sdim // Otherwise, extend the segment right after. 272193323Sed ++MergeTo; 273193323Sed MergeTo->start = NewStart; 274193323Sed MergeTo->end = I->end; 275193323Sed } 276193323Sed 277263508Sdim segments.erase(llvm::next(MergeTo), llvm::next(I)); 278193323Sed return MergeTo; 279193323Sed} 280193323Sed 281263508SdimLiveRange::iterator LiveRange::addSegmentFrom(Segment S, iterator From) { 282263508Sdim SlotIndex Start = S.start, End = S.end; 283263508Sdim iterator it = std::upper_bound(From, end(), Start); 284193323Sed 285263508Sdim // If the inserted segment starts in the middle or right at the end of 286263508Sdim // another segment, just extend that segment to contain the segment of S. 287263508Sdim if (it != begin()) { 288193323Sed iterator B = prior(it); 289263508Sdim if (S.valno == B->valno) { 290193323Sed if (B->start <= Start && B->end >= Start) { 291263508Sdim extendSegmentEndTo(B, End); 292193323Sed return B; 293193323Sed } 294193323Sed } else { 295263508Sdim // Check to make sure that we are not overlapping two live segments with 296193323Sed // different valno's. 297193323Sed assert(B->end <= Start && 298263508Sdim "Cannot overlap two segments with differing ValID's" 299193323Sed " (did you def the same reg twice in a MachineInstr?)"); 300193323Sed } 301193323Sed } 302193323Sed 303263508Sdim // Otherwise, if this segment ends in the middle of, or right next to, another 304263508Sdim // segment, merge it into that segment. 305263508Sdim if (it != end()) { 306263508Sdim if (S.valno == it->valno) { 307193323Sed if (it->start <= End) { 308263508Sdim it = extendSegmentStartTo(it, Start); 309193323Sed 310263508Sdim // If S is a complete superset of a segment, we may need to grow its 311193323Sed // endpoint as well. 312193323Sed if (End > it->end) 313263508Sdim extendSegmentEndTo(it, End); 314193323Sed return it; 315193323Sed } 316193323Sed } else { 317263508Sdim // Check to make sure that we are not overlapping two live segments with 318193323Sed // different valno's. 319193323Sed assert(it->start >= End && 320263508Sdim "Cannot overlap two segments with differing ValID's"); 321193323Sed } 322193323Sed } 323193323Sed 324263508Sdim // Otherwise, this is just a new segment that doesn't interact with anything. 325193323Sed // Insert it. 326263508Sdim return segments.insert(it, S); 327193323Sed} 328193323Sed 329263508Sdim/// extendInBlock - If this range is live before Kill in the basic 330226633Sdim/// block that starts at StartIdx, extend it to be live up to Kill and return 331226633Sdim/// the value. If there is no live range before Kill, return NULL. 332263508SdimVNInfo *LiveRange::extendInBlock(SlotIndex StartIdx, SlotIndex Kill) { 333221345Sdim if (empty()) 334221345Sdim return 0; 335226633Sdim iterator I = std::upper_bound(begin(), end(), Kill.getPrevSlot()); 336221345Sdim if (I == begin()) 337221345Sdim return 0; 338221345Sdim --I; 339221345Sdim if (I->end <= StartIdx) 340221345Sdim return 0; 341226633Sdim if (I->end < Kill) 342263508Sdim extendSegmentEndTo(I, Kill); 343221345Sdim return I->valno; 344221345Sdim} 345193323Sed 346263508Sdim/// Remove the specified segment from this range. Note that the segment must 347263508Sdim/// be in a single Segment in its entirety. 348263508Sdimvoid LiveRange::removeSegment(SlotIndex Start, SlotIndex End, 349263508Sdim bool RemoveDeadValNo) { 350263508Sdim // Find the Segment containing this span. 351263508Sdim iterator I = find(Start); 352263508Sdim assert(I != end() && "Segment is not in range!"); 353263508Sdim assert(I->containsInterval(Start, End) 354263508Sdim && "Segment is not entirely in range!"); 355193323Sed 356263508Sdim // If the span we are removing is at the start of the Segment, adjust it. 357193323Sed VNInfo *ValNo = I->valno; 358193323Sed if (I->start == Start) { 359193323Sed if (I->end == End) { 360193323Sed if (RemoveDeadValNo) { 361193323Sed // Check if val# is dead. 362193323Sed bool isDead = true; 363193323Sed for (const_iterator II = begin(), EE = end(); II != EE; ++II) 364193323Sed if (II != I && II->valno == ValNo) { 365193323Sed isDead = false; 366193323Sed break; 367210299Sed } 368193323Sed if (isDead) { 369212904Sdim // Now that ValNo is dead, remove it. 370212904Sdim markValNoForDeletion(ValNo); 371193323Sed } 372193323Sed } 373193323Sed 374263508Sdim segments.erase(I); // Removed the whole Segment. 375193323Sed } else 376193323Sed I->start = End; 377193323Sed return; 378193323Sed } 379193323Sed 380263508Sdim // Otherwise if the span we are removing is at the end of the Segment, 381193323Sed // adjust the other way. 382193323Sed if (I->end == End) { 383193323Sed I->end = Start; 384193323Sed return; 385193323Sed } 386193323Sed 387263508Sdim // Otherwise, we are splitting the Segment into two pieces. 388198892Srdivacky SlotIndex OldEnd = I->end; 389263508Sdim I->end = Start; // Trim the old segment. 390193323Sed 391193323Sed // Insert the new one. 392263508Sdim segments.insert(llvm::next(I), Segment(End, OldEnd, ValNo)); 393193323Sed} 394193323Sed 395263508Sdim/// removeValNo - Remove all the segments defined by the specified value#. 396193323Sed/// Also remove the value# from value# list. 397263508Sdimvoid LiveRange::removeValNo(VNInfo *ValNo) { 398193323Sed if (empty()) return; 399263508Sdim iterator I = end(); 400263508Sdim iterator E = begin(); 401193323Sed do { 402193323Sed --I; 403193323Sed if (I->valno == ValNo) 404263508Sdim segments.erase(I); 405193323Sed } while (I != E); 406212904Sdim // Now that ValNo is dead, remove it. 407212904Sdim markValNoForDeletion(ValNo); 408193323Sed} 409198090Srdivacky 410263508Sdimvoid LiveRange::join(LiveRange &Other, 411263508Sdim const int *LHSValNoAssignments, 412263508Sdim const int *RHSValNoAssignments, 413263508Sdim SmallVectorImpl<VNInfo *> &NewVNInfo) { 414239462Sdim verify(); 415239462Sdim 416263508Sdim // Determine if any of our values are mapped. This is uncommon, so we want 417263508Sdim // to avoid the range scan if not. 418193323Sed bool MustMapCurValNos = false; 419193323Sed unsigned NumVals = getNumValNums(); 420193323Sed unsigned NumNewVals = NewVNInfo.size(); 421193323Sed for (unsigned i = 0; i != NumVals; ++i) { 422193323Sed unsigned LHSValID = LHSValNoAssignments[i]; 423193323Sed if (i != LHSValID || 424234353Sdim (NewVNInfo[LHSValID] && NewVNInfo[LHSValID] != getValNumInfo(i))) { 425193323Sed MustMapCurValNos = true; 426234353Sdim break; 427234353Sdim } 428193323Sed } 429193323Sed 430263508Sdim // If we have to apply a mapping to our base range assignment, rewrite it now. 431243830Sdim if (MustMapCurValNos && !empty()) { 432193323Sed // Map the first live range. 433234353Sdim 434193323Sed iterator OutIt = begin(); 435193323Sed OutIt->valno = NewVNInfo[LHSValNoAssignments[OutIt->valno->id]]; 436249423Sdim for (iterator I = llvm::next(OutIt), E = end(); I != E; ++I) { 437234353Sdim VNInfo* nextValNo = NewVNInfo[LHSValNoAssignments[I->valno->id]]; 438234353Sdim assert(nextValNo != 0 && "Huh?"); 439212904Sdim 440193323Sed // If this live range has the same value # as its immediate predecessor, 441263508Sdim // and if they are neighbors, remove one Segment. This happens when we 442234353Sdim // have [0,4:0)[4,7:1) and map 0/1 onto the same value #. 443234353Sdim if (OutIt->valno == nextValNo && OutIt->end == I->start) { 444234353Sdim OutIt->end = I->end; 445193323Sed } else { 446263508Sdim // Didn't merge. Move OutIt to the next segment, 447234353Sdim ++OutIt; 448234353Sdim OutIt->valno = nextValNo; 449234353Sdim if (OutIt != I) { 450193323Sed OutIt->start = I->start; 451193323Sed OutIt->end = I->end; 452193323Sed } 453193323Sed } 454193323Sed } 455263508Sdim // If we merge some segments, chop off the end. 456234353Sdim ++OutIt; 457263508Sdim segments.erase(OutIt, end()); 458193323Sed } 459193323Sed 460249423Sdim // Rewrite Other values before changing the VNInfo ids. 461249423Sdim // This can leave Other in an invalid state because we're not coalescing 462249423Sdim // touching segments that now have identical values. That's OK since Other is 463249423Sdim // not supposed to be valid after calling join(); 464193323Sed for (iterator I = Other.begin(), E = Other.end(); I != E; ++I) 465249423Sdim I->valno = NewVNInfo[RHSValNoAssignments[I->valno->id]]; 466193323Sed 467193323Sed // Update val# info. Renumber them and make sure they all belong to this 468263508Sdim // LiveRange now. Also remove dead val#'s. 469193323Sed unsigned NumValNos = 0; 470193323Sed for (unsigned i = 0; i < NumNewVals; ++i) { 471193323Sed VNInfo *VNI = NewVNInfo[i]; 472193323Sed if (VNI) { 473193323Sed if (NumValNos >= NumVals) 474193323Sed valnos.push_back(VNI); 475212904Sdim else 476193323Sed valnos[NumValNos] = VNI; 477193323Sed VNI->id = NumValNos++; // Renumber val#. 478193323Sed } 479193323Sed } 480193323Sed if (NumNewVals < NumVals) 481193323Sed valnos.resize(NumNewVals); // shrinkify 482193323Sed 483263508Sdim // Okay, now insert the RHS live segments into the LHS. 484249423Sdim LiveRangeUpdater Updater(this); 485249423Sdim for (iterator I = Other.begin(), E = Other.end(); I != E; ++I) 486249423Sdim Updater.add(*I); 487193323Sed} 488193323Sed 489263508Sdim/// Merge all of the segments in RHS into this live range as the specified 490263508Sdim/// value number. The segments in RHS are allowed to overlap with segments in 491263508Sdim/// the current range, but only if the overlapping segments have the 492263508Sdim/// specified value number. 493263508Sdimvoid LiveRange::MergeSegmentsInAsValue(const LiveRange &RHS, 494263508Sdim VNInfo *LHSValNo) { 495249423Sdim LiveRangeUpdater Updater(this); 496249423Sdim for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) 497249423Sdim Updater.add(I->start, I->end, LHSValNo); 498193323Sed} 499193323Sed 500263508Sdim/// MergeValueInAsValue - Merge all of the live segments of a specific val# 501263508Sdim/// in RHS into this live range as the specified value number. 502263508Sdim/// The segments in RHS are allowed to overlap with segments in the 503263508Sdim/// current range, it will replace the value numbers of the overlaped 504263508Sdim/// segments with the specified value number. 505263508Sdimvoid LiveRange::MergeValueInAsValue(const LiveRange &RHS, 506263508Sdim const VNInfo *RHSValNo, 507263508Sdim VNInfo *LHSValNo) { 508249423Sdim LiveRangeUpdater Updater(this); 509249423Sdim for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) 510249423Sdim if (I->valno == RHSValNo) 511249423Sdim Updater.add(I->start, I->end, LHSValNo); 512193323Sed} 513193323Sed 514193323Sed/// MergeValueNumberInto - This method is called when two value nubmers 515193323Sed/// are found to be equivalent. This eliminates V1, replacing all 516263508Sdim/// segments with the V1 value number with the V2 value number. This can 517193323Sed/// cause merging of V1/V2 values numbers and compaction of the value space. 518263508SdimVNInfo *LiveRange::MergeValueNumberInto(VNInfo *V1, VNInfo *V2) { 519193323Sed assert(V1 != V2 && "Identical value#'s are always equivalent!"); 520193323Sed 521193323Sed // This code actually merges the (numerically) larger value number into the 522193323Sed // smaller value number, which is likely to allow us to compactify the value 523193323Sed // space. The only thing we have to be careful of is to preserve the 524193323Sed // instruction that defines the result value. 525193323Sed 526193323Sed // Make sure V2 is smaller than V1. 527193323Sed if (V1->id < V2->id) { 528198090Srdivacky V1->copyFrom(*V2); 529193323Sed std::swap(V1, V2); 530193323Sed } 531193323Sed 532263508Sdim // Merge V1 segments into V2. 533193323Sed for (iterator I = begin(); I != end(); ) { 534263508Sdim iterator S = I++; 535263508Sdim if (S->valno != V1) continue; // Not a V1 Segment. 536212904Sdim 537193323Sed // Okay, we found a V1 live range. If it had a previous, touching, V2 live 538193323Sed // range, extend it. 539263508Sdim if (S != begin()) { 540263508Sdim iterator Prev = S-1; 541263508Sdim if (Prev->valno == V2 && Prev->end == S->start) { 542263508Sdim Prev->end = S->end; 543193323Sed 544193323Sed // Erase this live-range. 545263508Sdim segments.erase(S); 546193323Sed I = Prev+1; 547263508Sdim S = Prev; 548193323Sed } 549193323Sed } 550212904Sdim 551193323Sed // Okay, now we have a V1 or V2 live range that is maximally merged forward. 552193323Sed // Ensure that it is a V2 live-range. 553263508Sdim S->valno = V2; 554212904Sdim 555263508Sdim // If we can merge it into later V2 segments, do so now. We ignore any 556263508Sdim // following V1 segments, as they will be merged in subsequent iterations 557193323Sed // of the loop. 558193323Sed if (I != end()) { 559263508Sdim if (I->start == S->end && I->valno == V2) { 560263508Sdim S->end = I->end; 561263508Sdim segments.erase(I); 562263508Sdim I = S+1; 563193323Sed } 564193323Sed } 565193323Sed } 566212904Sdim 567212904Sdim // Now that V1 is dead, remove it. 568212904Sdim markValNoForDeletion(V1); 569212904Sdim 570193323Sed return V2; 571193323Sed} 572193323Sed 573193323Sedunsigned LiveInterval::getSize() const { 574193323Sed unsigned Sum = 0; 575193323Sed for (const_iterator I = begin(), E = end(); I != E; ++I) 576198090Srdivacky Sum += I->start.distance(I->end); 577193323Sed return Sum; 578193323Sed} 579193323Sed 580263508Sdimraw_ostream& llvm::operator<<(raw_ostream& os, const LiveRange::Segment &S) { 581263508Sdim return os << '[' << S.start << ',' << S.end << ':' << S.valno->id << ")"; 582193323Sed} 583193323Sed 584243830Sdim#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 585263508Sdimvoid LiveRange::Segment::dump() const { 586202375Srdivacky dbgs() << *this << "\n"; 587193323Sed} 588243830Sdim#endif 589193323Sed 590263508Sdimvoid LiveRange::print(raw_ostream &OS) const { 591193323Sed if (empty()) 592239462Sdim OS << "EMPTY"; 593193323Sed else { 594263508Sdim for (const_iterator I = begin(), E = end(); I != E; ++I) { 595210299Sed OS << *I; 596210299Sed assert(I->valno == getValNumInfo(I->valno->id) && "Bad VNInfo"); 597210299Sed } 598193323Sed } 599210299Sed 600193323Sed // Print value number info. 601193323Sed if (getNumValNums()) { 602193323Sed OS << " "; 603193323Sed unsigned vnum = 0; 604193323Sed for (const_vni_iterator i = vni_begin(), e = vni_end(); i != e; 605193323Sed ++i, ++vnum) { 606193323Sed const VNInfo *vni = *i; 607193323Sed if (vnum) OS << " "; 608193323Sed OS << vnum << "@"; 609194612Sed if (vni->isUnused()) { 610193323Sed OS << "x"; 611193323Sed } else { 612218893Sdim OS << vni->def; 613218893Sdim if (vni->isPHIDef()) 614239462Sdim OS << "-phi"; 615193323Sed } 616193323Sed } 617193323Sed } 618193323Sed} 619193323Sed 620263508Sdimvoid LiveInterval::print(raw_ostream &OS) const { 621263508Sdim OS << PrintReg(reg) << ' '; 622263508Sdim super::print(OS); 623263508Sdim} 624263508Sdim 625243830Sdim#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 626263508Sdimvoid LiveRange::dump() const { 627263508Sdim dbgs() << *this << "\n"; 628263508Sdim} 629263508Sdim 630193323Sedvoid LiveInterval::dump() const { 631202375Srdivacky dbgs() << *this << "\n"; 632193323Sed} 633243830Sdim#endif 634193323Sed 635239462Sdim#ifndef NDEBUG 636263508Sdimvoid LiveRange::verify() const { 637239462Sdim for (const_iterator I = begin(), E = end(); I != E; ++I) { 638239462Sdim assert(I->start.isValid()); 639239462Sdim assert(I->end.isValid()); 640239462Sdim assert(I->start < I->end); 641239462Sdim assert(I->valno != 0); 642263508Sdim assert(I->valno->id < valnos.size()); 643239462Sdim assert(I->valno == valnos[I->valno->id]); 644239462Sdim if (llvm::next(I) != E) { 645239462Sdim assert(I->end <= llvm::next(I)->start); 646239462Sdim if (I->end == llvm::next(I)->start) 647239462Sdim assert(I->valno != llvm::next(I)->valno); 648239462Sdim } 649239462Sdim } 650239462Sdim} 651239462Sdim#endif 652193323Sed 653239462Sdim 654249423Sdim//===----------------------------------------------------------------------===// 655249423Sdim// LiveRangeUpdater class 656249423Sdim//===----------------------------------------------------------------------===// 657249423Sdim// 658249423Sdim// The LiveRangeUpdater class always maintains these invariants: 659249423Sdim// 660249423Sdim// - When LastStart is invalid, Spills is empty and the iterators are invalid. 661249423Sdim// This is the initial state, and the state created by flush(). 662249423Sdim// In this state, isDirty() returns false. 663249423Sdim// 664249423Sdim// Otherwise, segments are kept in three separate areas: 665249423Sdim// 666263508Sdim// 1. [begin; WriteI) at the front of LR. 667263508Sdim// 2. [ReadI; end) at the back of LR. 668249423Sdim// 3. Spills. 669249423Sdim// 670263508Sdim// - LR.begin() <= WriteI <= ReadI <= LR.end(). 671249423Sdim// - Segments in all three areas are fully ordered and coalesced. 672249423Sdim// - Segments in area 1 precede and can't coalesce with segments in area 2. 673249423Sdim// - Segments in Spills precede and can't coalesce with segments in area 2. 674249423Sdim// - No coalescing is possible between segments in Spills and segments in area 675249423Sdim// 1, and there are no overlapping segments. 676249423Sdim// 677249423Sdim// The segments in Spills are not ordered with respect to the segments in area 678249423Sdim// 1. They need to be merged. 679249423Sdim// 680249423Sdim// When they exist, Spills.back().start <= LastStart, 681249423Sdim// and WriteI[-1].start <= LastStart. 682249423Sdim 683249423Sdimvoid LiveRangeUpdater::print(raw_ostream &OS) const { 684249423Sdim if (!isDirty()) { 685263508Sdim if (LR) 686263508Sdim OS << "Clean updater: " << *LR << '\n'; 687249423Sdim else 688249423Sdim OS << "Null updater.\n"; 689249423Sdim return; 690249423Sdim } 691263508Sdim assert(LR && "Can't have null LR in dirty updater."); 692263508Sdim OS << " updater with gap = " << (ReadI - WriteI) 693249423Sdim << ", last start = " << LastStart 694249423Sdim << ":\n Area 1:"; 695263508Sdim for (LiveRange::const_iterator I = LR->begin(); I != WriteI; ++I) 696249423Sdim OS << ' ' << *I; 697249423Sdim OS << "\n Spills:"; 698249423Sdim for (unsigned I = 0, E = Spills.size(); I != E; ++I) 699249423Sdim OS << ' ' << Spills[I]; 700249423Sdim OS << "\n Area 2:"; 701263508Sdim for (LiveRange::const_iterator I = ReadI, E = LR->end(); I != E; ++I) 702249423Sdim OS << ' ' << *I; 703249423Sdim OS << '\n'; 704249423Sdim} 705249423Sdim 706249423Sdimvoid LiveRangeUpdater::dump() const 707249423Sdim{ 708249423Sdim print(errs()); 709249423Sdim} 710249423Sdim 711249423Sdim// Determine if A and B should be coalesced. 712263508Sdimstatic inline bool coalescable(const LiveRange::Segment &A, 713263508Sdim const LiveRange::Segment &B) { 714263508Sdim assert(A.start <= B.start && "Unordered live segments."); 715249423Sdim if (A.end == B.start) 716249423Sdim return A.valno == B.valno; 717249423Sdim if (A.end < B.start) 718249423Sdim return false; 719249423Sdim assert(A.valno == B.valno && "Cannot overlap different values"); 720249423Sdim return true; 721249423Sdim} 722249423Sdim 723263508Sdimvoid LiveRangeUpdater::add(LiveRange::Segment Seg) { 724263508Sdim assert(LR && "Cannot add to a null destination"); 725249423Sdim 726249423Sdim // Flush the state if Start moves backwards. 727249423Sdim if (!LastStart.isValid() || LastStart > Seg.start) { 728249423Sdim if (isDirty()) 729249423Sdim flush(); 730249423Sdim // This brings us to an uninitialized state. Reinitialize. 731249423Sdim assert(Spills.empty() && "Leftover spilled segments"); 732263508Sdim WriteI = ReadI = LR->begin(); 733249423Sdim } 734249423Sdim 735249423Sdim // Remember start for next time. 736249423Sdim LastStart = Seg.start; 737249423Sdim 738249423Sdim // Advance ReadI until it ends after Seg.start. 739263508Sdim LiveRange::iterator E = LR->end(); 740249423Sdim if (ReadI != E && ReadI->end <= Seg.start) { 741249423Sdim // First try to close the gap between WriteI and ReadI with spills. 742249423Sdim if (ReadI != WriteI) 743249423Sdim mergeSpills(); 744249423Sdim // Then advance ReadI. 745249423Sdim if (ReadI == WriteI) 746263508Sdim ReadI = WriteI = LR->find(Seg.start); 747249423Sdim else 748249423Sdim while (ReadI != E && ReadI->end <= Seg.start) 749249423Sdim *WriteI++ = *ReadI++; 750249423Sdim } 751249423Sdim 752249423Sdim assert(ReadI == E || ReadI->end > Seg.start); 753249423Sdim 754249423Sdim // Check if the ReadI segment begins early. 755249423Sdim if (ReadI != E && ReadI->start <= Seg.start) { 756249423Sdim assert(ReadI->valno == Seg.valno && "Cannot overlap different values"); 757249423Sdim // Bail if Seg is completely contained in ReadI. 758249423Sdim if (ReadI->end >= Seg.end) 759249423Sdim return; 760249423Sdim // Coalesce into Seg. 761249423Sdim Seg.start = ReadI->start; 762249423Sdim ++ReadI; 763249423Sdim } 764249423Sdim 765249423Sdim // Coalesce as much as possible from ReadI into Seg. 766249423Sdim while (ReadI != E && coalescable(Seg, *ReadI)) { 767249423Sdim Seg.end = std::max(Seg.end, ReadI->end); 768249423Sdim ++ReadI; 769249423Sdim } 770249423Sdim 771249423Sdim // Try coalescing Spills.back() into Seg. 772249423Sdim if (!Spills.empty() && coalescable(Spills.back(), Seg)) { 773249423Sdim Seg.start = Spills.back().start; 774249423Sdim Seg.end = std::max(Spills.back().end, Seg.end); 775249423Sdim Spills.pop_back(); 776249423Sdim } 777249423Sdim 778249423Sdim // Try coalescing Seg into WriteI[-1]. 779263508Sdim if (WriteI != LR->begin() && coalescable(WriteI[-1], Seg)) { 780249423Sdim WriteI[-1].end = std::max(WriteI[-1].end, Seg.end); 781249423Sdim return; 782249423Sdim } 783249423Sdim 784249423Sdim // Seg doesn't coalesce with anything, and needs to be inserted somewhere. 785249423Sdim if (WriteI != ReadI) { 786249423Sdim *WriteI++ = Seg; 787249423Sdim return; 788249423Sdim } 789249423Sdim 790263508Sdim // Finally, append to LR or Spills. 791249423Sdim if (WriteI == E) { 792263508Sdim LR->segments.push_back(Seg); 793263508Sdim WriteI = ReadI = LR->end(); 794249423Sdim } else 795249423Sdim Spills.push_back(Seg); 796249423Sdim} 797249423Sdim 798249423Sdim// Merge as many spilled segments as possible into the gap between WriteI 799249423Sdim// and ReadI. Advance WriteI to reflect the inserted instructions. 800249423Sdimvoid LiveRangeUpdater::mergeSpills() { 801249423Sdim // Perform a backwards merge of Spills and [SpillI;WriteI). 802249423Sdim size_t GapSize = ReadI - WriteI; 803249423Sdim size_t NumMoved = std::min(Spills.size(), GapSize); 804263508Sdim LiveRange::iterator Src = WriteI; 805263508Sdim LiveRange::iterator Dst = Src + NumMoved; 806263508Sdim LiveRange::iterator SpillSrc = Spills.end(); 807263508Sdim LiveRange::iterator B = LR->begin(); 808249423Sdim 809249423Sdim // This is the new WriteI position after merging spills. 810249423Sdim WriteI = Dst; 811249423Sdim 812249423Sdim // Now merge Src and Spills backwards. 813249423Sdim while (Src != Dst) { 814249423Sdim if (Src != B && Src[-1].start > SpillSrc[-1].start) 815249423Sdim *--Dst = *--Src; 816249423Sdim else 817249423Sdim *--Dst = *--SpillSrc; 818249423Sdim } 819249423Sdim assert(NumMoved == size_t(Spills.end() - SpillSrc)); 820249423Sdim Spills.erase(SpillSrc, Spills.end()); 821249423Sdim} 822249423Sdim 823249423Sdimvoid LiveRangeUpdater::flush() { 824249423Sdim if (!isDirty()) 825249423Sdim return; 826249423Sdim // Clear the dirty state. 827249423Sdim LastStart = SlotIndex(); 828249423Sdim 829263508Sdim assert(LR && "Cannot add to a null destination"); 830249423Sdim 831249423Sdim // Nothing to merge? 832249423Sdim if (Spills.empty()) { 833263508Sdim LR->segments.erase(WriteI, ReadI); 834263508Sdim LR->verify(); 835249423Sdim return; 836249423Sdim } 837249423Sdim 838249423Sdim // Resize the WriteI - ReadI gap to match Spills. 839249423Sdim size_t GapSize = ReadI - WriteI; 840249423Sdim if (GapSize < Spills.size()) { 841249423Sdim // The gap is too small. Make some room. 842263508Sdim size_t WritePos = WriteI - LR->begin(); 843263508Sdim LR->segments.insert(ReadI, Spills.size() - GapSize, LiveRange::Segment()); 844249423Sdim // This also invalidated ReadI, but it is recomputed below. 845263508Sdim WriteI = LR->begin() + WritePos; 846249423Sdim } else { 847249423Sdim // Shrink the gap if necessary. 848263508Sdim LR->segments.erase(WriteI + Spills.size(), ReadI); 849249423Sdim } 850249423Sdim ReadI = WriteI + Spills.size(); 851249423Sdim mergeSpills(); 852263508Sdim LR->verify(); 853249423Sdim} 854249423Sdim 855218893Sdimunsigned ConnectedVNInfoEqClasses::Classify(const LiveInterval *LI) { 856218893Sdim // Create initial equivalence classes. 857221345Sdim EqClass.clear(); 858221345Sdim EqClass.grow(LI->getNumValNums()); 859218893Sdim 860218893Sdim const VNInfo *used = 0, *unused = 0; 861218893Sdim 862218893Sdim // Determine connections. 863218893Sdim for (LiveInterval::const_vni_iterator I = LI->vni_begin(), E = LI->vni_end(); 864218893Sdim I != E; ++I) { 865218893Sdim const VNInfo *VNI = *I; 866218893Sdim // Group all unused values into one class. 867218893Sdim if (VNI->isUnused()) { 868218893Sdim if (unused) 869221345Sdim EqClass.join(unused->id, VNI->id); 870218893Sdim unused = VNI; 871218893Sdim continue; 872218893Sdim } 873218893Sdim used = VNI; 874218893Sdim if (VNI->isPHIDef()) { 875221345Sdim const MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def); 876218893Sdim assert(MBB && "Phi-def has no defining MBB"); 877218893Sdim // Connect to values live out of predecessors. 878218893Sdim for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 879218893Sdim PE = MBB->pred_end(); PI != PE; ++PI) 880234353Sdim if (const VNInfo *PVNI = LI->getVNInfoBefore(LIS.getMBBEndIdx(*PI))) 881221345Sdim EqClass.join(VNI->id, PVNI->id); 882218893Sdim } else { 883218893Sdim // Normal value defined by an instruction. Check for two-addr redef. 884218893Sdim // FIXME: This could be coincidental. Should we really check for a tied 885218893Sdim // operand constraint? 886218893Sdim // Note that VNI->def may be a use slot for an early clobber def. 887234353Sdim if (const VNInfo *UVNI = LI->getVNInfoBefore(VNI->def)) 888221345Sdim EqClass.join(VNI->id, UVNI->id); 889218893Sdim } 890218893Sdim } 891218893Sdim 892218893Sdim // Lump all the unused values in with the last used value. 893218893Sdim if (used && unused) 894221345Sdim EqClass.join(used->id, unused->id); 895218893Sdim 896221345Sdim EqClass.compress(); 897221345Sdim return EqClass.getNumClasses(); 898218893Sdim} 899218893Sdim 900221345Sdimvoid ConnectedVNInfoEqClasses::Distribute(LiveInterval *LIV[], 901221345Sdim MachineRegisterInfo &MRI) { 902218893Sdim assert(LIV[0] && "LIV[0] must be set"); 903218893Sdim LiveInterval &LI = *LIV[0]; 904218893Sdim 905221345Sdim // Rewrite instructions. 906221345Sdim for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(LI.reg), 907221345Sdim RE = MRI.reg_end(); RI != RE;) { 908221345Sdim MachineOperand &MO = RI.getOperand(); 909221345Sdim MachineInstr *MI = MO.getParent(); 910221345Sdim ++RI; 911263508Sdim // DBG_VALUE instructions don't have slot indexes, so get the index of the 912263508Sdim // instruction before them. 913263508Sdim // Normally, DBG_VALUE instructions are removed before this function is 914263508Sdim // called, but it is not a requirement. 915263508Sdim SlotIndex Idx; 916263508Sdim if (MI->isDebugValue()) 917263508Sdim Idx = LIS.getSlotIndexes()->getIndexBefore(MI); 918263508Sdim else 919263508Sdim Idx = LIS.getInstructionIndex(MI); 920263508Sdim LiveQueryResult LRQ = LI.Query(Idx); 921239462Sdim const VNInfo *VNI = MO.readsReg() ? LRQ.valueIn() : LRQ.valueDefined(); 922239462Sdim // In the case of an <undef> use that isn't tied to any def, VNI will be 923239462Sdim // NULL. If the use is tied to a def, VNI will be the defined value. 924239462Sdim if (!VNI) 925221345Sdim continue; 926221345Sdim MO.setReg(LIV[getEqClass(VNI)]->reg); 927221345Sdim } 928221345Sdim 929221345Sdim // Move runs to new intervals. 930218893Sdim LiveInterval::iterator J = LI.begin(), E = LI.end(); 931221345Sdim while (J != E && EqClass[J->valno->id] == 0) 932218893Sdim ++J; 933218893Sdim for (LiveInterval::iterator I = J; I != E; ++I) { 934221345Sdim if (unsigned eq = EqClass[I->valno->id]) { 935218893Sdim assert((LIV[eq]->empty() || LIV[eq]->expiredAt(I->start)) && 936218893Sdim "New intervals should be empty"); 937263508Sdim LIV[eq]->segments.push_back(*I); 938218893Sdim } else 939218893Sdim *J++ = *I; 940218893Sdim } 941263508Sdim LI.segments.erase(J, E); 942218893Sdim 943218893Sdim // Transfer VNInfos to their new owners and renumber them. 944218893Sdim unsigned j = 0, e = LI.getNumValNums(); 945221345Sdim while (j != e && EqClass[j] == 0) 946218893Sdim ++j; 947218893Sdim for (unsigned i = j; i != e; ++i) { 948218893Sdim VNInfo *VNI = LI.getValNumInfo(i); 949221345Sdim if (unsigned eq = EqClass[i]) { 950218893Sdim VNI->id = LIV[eq]->getNumValNums(); 951218893Sdim LIV[eq]->valnos.push_back(VNI); 952218893Sdim } else { 953218893Sdim VNI->id = j; 954218893Sdim LI.valnos[j++] = VNI; 955218893Sdim } 956218893Sdim } 957218893Sdim LI.valnos.resize(j); 958218893Sdim} 959