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