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