LLVM API Documentation
00001 //===-- LiveInterval.cpp - Live Interval Representation -------------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements the LiveRange and LiveInterval classes. Given some 00011 // numbering of each the machine instructions an interval [i, j) is said to be a 00012 // live interval for register v if there is no instruction with number j' > j 00013 // such that v is live at j' abd there is no instruction with number i' < i such 00014 // that v is live at i'. In this implementation intervals can have holes, 00015 // i.e. an interval might look like [1,20), [50,65), [1000,1001). Each 00016 // individual range is represented as an instance of LiveRange, and the whole 00017 // interval is represented as an instance of LiveInterval. 00018 // 00019 //===----------------------------------------------------------------------===// 00020 00021 #include "llvm/CodeGen/LiveInterval.h" 00022 #include "llvm/CodeGen/MachineRegisterInfo.h" 00023 #include "llvm/ADT/DenseMap.h" 00024 #include "llvm/ADT/SmallSet.h" 00025 #include "llvm/ADT/STLExtras.h" 00026 #include "llvm/Support/raw_ostream.h" 00027 #include "llvm/Support/raw_ostream.h" 00028 #include "llvm/Target/TargetRegisterInfo.h" 00029 #include <algorithm> 00030 using namespace llvm; 00031 00032 // An example for liveAt(): 00033 // 00034 // this = [1,4), liveAt(0) will return false. The instruction defining this 00035 // spans slots [0,3]. The interval belongs to an spilled definition of the 00036 // variable it represents. This is because slot 1 is used (def slot) and spans 00037 // up to slot 3 (store slot). 00038 // 00039 bool LiveInterval::liveAt(unsigned I) const { 00040 Ranges::const_iterator r = std::upper_bound(ranges.begin(), ranges.end(), I); 00041 00042 if (r == ranges.begin()) 00043 return false; 00044 00045 --r; 00046 return r->contains(I); 00047 } 00048 00049 // liveBeforeAndAt - Check if the interval is live at the index and the index 00050 // just before it. If index is liveAt, check if it starts a new live range. 00051 // If it does, then check if the previous live range ends at index-1. 00052 bool LiveInterval::liveBeforeAndAt(unsigned I) const { 00053 Ranges::const_iterator r = std::upper_bound(ranges.begin(), ranges.end(), I); 00054 00055 if (r == ranges.begin()) 00056 return false; 00057 00058 --r; 00059 if (!r->contains(I)) 00060 return false; 00061 if (I != r->start) 00062 return true; 00063 // I is the start of a live range. Check if the previous live range ends 00064 // at I-1. 00065 if (r == ranges.begin()) 00066 return false; 00067 return r->end == I; 00068 } 00069 00070 // overlaps - Return true if the intersection of the two live intervals is 00071 // not empty. 00072 // 00073 // An example for overlaps(): 00074 // 00075 // 0: A = ... 00076 // 4: B = ... 00077 // 8: C = A + B ;; last use of A 00078 // 00079 // The live intervals should look like: 00080 // 00081 // A = [3, 11) 00082 // B = [7, x) 00083 // C = [11, y) 00084 // 00085 // A->overlaps(C) should return false since we want to be able to join 00086 // A and C. 00087 // 00088 bool LiveInterval::overlapsFrom(const LiveInterval& other, 00089 const_iterator StartPos) const { 00090 const_iterator i = begin(); 00091 const_iterator ie = end(); 00092 const_iterator j = StartPos; 00093 const_iterator je = other.end(); 00094 00095 assert((StartPos->start <= i->start || StartPos == other.begin()) && 00096 StartPos != other.end() && "Bogus start position hint!"); 00097 00098 if (i->start < j->start) { 00099 i = std::upper_bound(i, ie, j->start); 00100 if (i != ranges.begin()) --i; 00101 } else if (j->start < i->start) { 00102 ++StartPos; 00103 if (StartPos != other.end() && StartPos->start <= i->start) { 00104 assert(StartPos < other.end() && i < end()); 00105 j = std::upper_bound(j, je, i->start); 00106 if (j != other.ranges.begin()) --j; 00107 } 00108 } else { 00109 return true; 00110 } 00111 00112 if (j == je) return false; 00113 00114 while (i != ie) { 00115 if (i->start > j->start) { 00116 std::swap(i, j); 00117 std::swap(ie, je); 00118 } 00119 00120 if (i->end > j->start) 00121 return true; 00122 ++i; 00123 } 00124 00125 return false; 00126 } 00127 00128 /// overlaps - Return true if the live interval overlaps a range specified 00129 /// by [Start, End). 00130 bool LiveInterval::overlaps(unsigned Start, unsigned End) const { 00131 assert(Start < End && "Invalid range"); 00132 const_iterator I = begin(); 00133 const_iterator E = end(); 00134 const_iterator si = std::upper_bound(I, E, Start); 00135 const_iterator ei = std::upper_bound(I, E, End); 00136 if (si != ei) 00137 return true; 00138 if (si == I) 00139 return false; 00140 --si; 00141 return si->contains(Start); 00142 } 00143 00144 /// extendIntervalEndTo - This method is used when we want to extend the range 00145 /// specified by I to end at the specified endpoint. To do this, we should 00146 /// merge and eliminate all ranges that this will overlap with. The iterator is 00147 /// not invalidated. 00148 void LiveInterval::extendIntervalEndTo(Ranges::iterator I, unsigned NewEnd) { 00149 assert(I != ranges.end() && "Not a valid interval!"); 00150 VNInfo *ValNo = I->valno; 00151 unsigned OldEnd = I->end; 00152 00153 // Search for the first interval that we can't merge with. 00154 Ranges::iterator MergeTo = next(I); 00155 for (; MergeTo != ranges.end() && NewEnd >= MergeTo->end; ++MergeTo) { 00156 assert(MergeTo->valno == ValNo && "Cannot merge with differing values!"); 00157 } 00158 00159 // If NewEnd was in the middle of an interval, make sure to get its endpoint. 00160 I->end = std::max(NewEnd, prior(MergeTo)->end); 00161 00162 // Erase any dead ranges. 00163 ranges.erase(next(I), MergeTo); 00164 00165 // Update kill info. 00166 removeKills(ValNo, OldEnd, I->end-1); 00167 00168 // If the newly formed range now touches the range after it and if they have 00169 // the same value number, merge the two ranges into one range. 00170 Ranges::iterator Next = next(I); 00171 if (Next != ranges.end() && Next->start <= I->end && Next->valno == ValNo) { 00172 I->end = Next->end; 00173 ranges.erase(Next); 00174 } 00175 } 00176 00177 00178 /// extendIntervalStartTo - This method is used when we want to extend the range 00179 /// specified by I to start at the specified endpoint. To do this, we should 00180 /// merge and eliminate all ranges that this will overlap with. 00181 LiveInterval::Ranges::iterator 00182 LiveInterval::extendIntervalStartTo(Ranges::iterator I, unsigned NewStart) { 00183 assert(I != ranges.end() && "Not a valid interval!"); 00184 VNInfo *ValNo = I->valno; 00185 00186 // Search for the first interval that we can't merge with. 00187 Ranges::iterator MergeTo = I; 00188 do { 00189 if (MergeTo == ranges.begin()) { 00190 I->start = NewStart; 00191 ranges.erase(MergeTo, I); 00192 return I; 00193 } 00194 assert(MergeTo->valno == ValNo && "Cannot merge with differing values!"); 00195 --MergeTo; 00196 } while (NewStart <= MergeTo->start); 00197 00198 // If we start in the middle of another interval, just delete a range and 00199 // extend that interval. 00200 if (MergeTo->end >= NewStart && MergeTo->valno == ValNo) { 00201 MergeTo->end = I->end; 00202 } else { 00203 // Otherwise, extend the interval right after. 00204 ++MergeTo; 00205 MergeTo->start = NewStart; 00206 MergeTo->end = I->end; 00207 } 00208 00209 ranges.erase(next(MergeTo), next(I)); 00210 return MergeTo; 00211 } 00212 00213 LiveInterval::iterator 00214 LiveInterval::addRangeFrom(LiveRange LR, iterator From) { 00215 unsigned Start = LR.start, End = LR.end; 00216 iterator it = std::upper_bound(From, ranges.end(), Start); 00217 00218 // If the inserted interval starts in the middle or right at the end of 00219 // another interval, just extend that interval to contain the range of LR. 00220 if (it != ranges.begin()) { 00221 iterator B = prior(it); 00222 if (LR.valno == B->valno) { 00223 if (B->start <= Start && B->end >= Start) { 00224 extendIntervalEndTo(B, End); 00225 return B; 00226 } 00227 } else { 00228 // Check to make sure that we are not overlapping two live ranges with 00229 // different valno's. 00230 assert(B->end <= Start && 00231 "Cannot overlap two LiveRanges with differing ValID's" 00232 " (did you def the same reg twice in a MachineInstr?)"); 00233 } 00234 } 00235 00236 // Otherwise, if this range ends in the middle of, or right next to, another 00237 // interval, merge it into that interval. 00238 if (it != ranges.end()) { 00239 if (LR.valno == it->valno) { 00240 if (it->start <= End) { 00241 it = extendIntervalStartTo(it, Start); 00242 00243 // If LR is a complete superset of an interval, we may need to grow its 00244 // endpoint as well. 00245 if (End > it->end) 00246 extendIntervalEndTo(it, End); 00247 else if (End < it->end) 00248 // Overlapping intervals, there might have been a kill here. 00249 removeKill(it->valno, End); 00250 return it; 00251 } 00252 } else { 00253 // Check to make sure that we are not overlapping two live ranges with 00254 // different valno's. 00255 assert(it->start >= End && 00256 "Cannot overlap two LiveRanges with differing ValID's"); 00257 } 00258 } 00259 00260 // Otherwise, this is just a new range that doesn't interact with anything. 00261 // Insert it. 00262 return ranges.insert(it, LR); 00263 } 00264 00265 /// isInOneLiveRange - Return true if the range specified is entirely in the 00266 /// a single LiveRange of the live interval. 00267 bool LiveInterval::isInOneLiveRange(unsigned Start, unsigned End) { 00268 Ranges::iterator I = std::upper_bound(ranges.begin(), ranges.end(), Start); 00269 if (I == ranges.begin()) 00270 return false; 00271 --I; 00272 return I->contains(Start) && I->contains(End-1); 00273 } 00274 00275 00276 /// removeRange - Remove the specified range from this interval. Note that 00277 /// the range must be in a single LiveRange in its entirety. 00278 void LiveInterval::removeRange(unsigned Start, unsigned End, 00279 bool RemoveDeadValNo) { 00280 // Find the LiveRange containing this span. 00281 Ranges::iterator I = std::upper_bound(ranges.begin(), ranges.end(), Start); 00282 assert(I != ranges.begin() && "Range is not in interval!"); 00283 --I; 00284 assert(I->contains(Start) && I->contains(End-1) && 00285 "Range is not entirely in interval!"); 00286 00287 // If the span we are removing is at the start of the LiveRange, adjust it. 00288 VNInfo *ValNo = I->valno; 00289 if (I->start == Start) { 00290 if (I->end == End) { 00291 removeKills(I->valno, Start, End); 00292 if (RemoveDeadValNo) { 00293 // Check if val# is dead. 00294 bool isDead = true; 00295 for (const_iterator II = begin(), EE = end(); II != EE; ++II) 00296 if (II != I && II->valno == ValNo) { 00297 isDead = false; 00298 break; 00299 } 00300 if (isDead) { 00301 // Now that ValNo is dead, remove it. If it is the largest value 00302 // number, just nuke it (and any other deleted values neighboring it), 00303 // otherwise mark it as ~1U so it can be nuked later. 00304 if (ValNo->id == getNumValNums()-1) { 00305 do { 00306 VNInfo *VNI = valnos.back(); 00307 valnos.pop_back(); 00308 VNI->~VNInfo(); 00309 } while (!valnos.empty() && valnos.back()->isUnused()); 00310 } else { 00311 ValNo->setIsUnused(true); 00312 } 00313 } 00314 } 00315 00316 ranges.erase(I); // Removed the whole LiveRange. 00317 } else 00318 I->start = End; 00319 return; 00320 } 00321 00322 // Otherwise if the span we are removing is at the end of the LiveRange, 00323 // adjust the other way. 00324 if (I->end == End) { 00325 removeKills(ValNo, Start, End); 00326 I->end = Start; 00327 return; 00328 } 00329 00330 // Otherwise, we are splitting the LiveRange into two pieces. 00331 unsigned OldEnd = I->end; 00332 I->end = Start; // Trim the old interval. 00333 00334 // Insert the new one. 00335 ranges.insert(next(I), LiveRange(End, OldEnd, ValNo)); 00336 } 00337 00338 /// removeValNo - Remove all the ranges defined by the specified value#. 00339 /// Also remove the value# from value# list. 00340 void LiveInterval::removeValNo(VNInfo *ValNo) { 00341 if (empty()) return; 00342 Ranges::iterator I = ranges.end(); 00343 Ranges::iterator E = ranges.begin(); 00344 do { 00345 --I; 00346 if (I->valno == ValNo) 00347 ranges.erase(I); 00348 } while (I != E); 00349 // Now that ValNo is dead, remove it. If it is the largest value 00350 // number, just nuke it (and any other deleted values neighboring it), 00351 // otherwise mark it as ~1U so it can be nuked later. 00352 if (ValNo->id == getNumValNums()-1) { 00353 do { 00354 VNInfo *VNI = valnos.back(); 00355 valnos.pop_back(); 00356 VNI->~VNInfo(); 00357 } while (!valnos.empty() && valnos.back()->isUnused()); 00358 } else { 00359 ValNo->setIsUnused(true); 00360 } 00361 } 00362 00363 /// scaleNumbering - Renumber VNI and ranges to provide gaps for new 00364 /// instructions. 00365 void LiveInterval::scaleNumbering(unsigned factor) { 00366 // Scale ranges. 00367 for (iterator RI = begin(), RE = end(); RI != RE; ++RI) { 00368 RI->start = InstrSlots::scale(RI->start, factor); 00369 RI->end = InstrSlots::scale(RI->end, factor); 00370 } 00371 00372 // Scale VNI info. 00373 for (vni_iterator VNI = vni_begin(), VNIE = vni_end(); VNI != VNIE; ++VNI) { 00374 VNInfo *vni = *VNI; 00375 00376 if (vni->isDefAccurate()) 00377 vni->def = InstrSlots::scale(vni->def, factor); 00378 00379 for (unsigned i = 0; i < vni->kills.size(); ++i) { 00380 if (!vni->kills[i].isPHIKill) 00381 vni->kills[i].killIdx = 00382 InstrSlots::scale(vni->kills[i].killIdx, factor); 00383 } 00384 } 00385 } 00386 00387 /// getLiveRangeContaining - Return the live range that contains the 00388 /// specified index, or null if there is none. 00389 LiveInterval::const_iterator 00390 LiveInterval::FindLiveRangeContaining(unsigned Idx) const { 00391 const_iterator It = std::upper_bound(begin(), end(), Idx); 00392 if (It != ranges.begin()) { 00393 --It; 00394 if (It->contains(Idx)) 00395 return It; 00396 } 00397 00398 return end(); 00399 } 00400 00401 LiveInterval::iterator 00402 LiveInterval::FindLiveRangeContaining(unsigned Idx) { 00403 iterator It = std::upper_bound(begin(), end(), Idx); 00404 if (It != begin()) { 00405 --It; 00406 if (It->contains(Idx)) 00407 return It; 00408 } 00409 00410 return end(); 00411 } 00412 00413 /// findDefinedVNInfo - Find the VNInfo that's defined at the specified index 00414 /// (register interval) or defined by the specified register (stack inteval). 00415 VNInfo *LiveInterval::findDefinedVNInfo(unsigned DefIdxOrReg) const { 00416 VNInfo *VNI = NULL; 00417 for (LiveInterval::const_vni_iterator i = vni_begin(), e = vni_end(); 00418 i != e; ++i) 00419 if ((*i)->def == DefIdxOrReg) { 00420 VNI = *i; 00421 break; 00422 } 00423 return VNI; 00424 } 00425 00426 /// join - Join two live intervals (this, and other) together. This applies 00427 /// mappings to the value numbers in the LHS/RHS intervals as specified. If 00428 /// the intervals are not joinable, this aborts. 00429 void LiveInterval::join(LiveInterval &Other, const int *LHSValNoAssignments, 00430 const int *RHSValNoAssignments, 00431 SmallVector<VNInfo*, 16> &NewVNInfo, 00432 MachineRegisterInfo *MRI) { 00433 // Determine if any of our live range values are mapped. This is uncommon, so 00434 // we want to avoid the interval scan if not. 00435 bool MustMapCurValNos = false; 00436 unsigned NumVals = getNumValNums(); 00437 unsigned NumNewVals = NewVNInfo.size(); 00438 for (unsigned i = 0; i != NumVals; ++i) { 00439 unsigned LHSValID = LHSValNoAssignments[i]; 00440 if (i != LHSValID || 00441 (NewVNInfo[LHSValID] && NewVNInfo[LHSValID] != getValNumInfo(i))) 00442 MustMapCurValNos = true; 00443 } 00444 00445 // If we have to apply a mapping to our base interval assignment, rewrite it 00446 // now. 00447 if (MustMapCurValNos) { 00448 // Map the first live range. 00449 iterator OutIt = begin(); 00450 OutIt->valno = NewVNInfo[LHSValNoAssignments[OutIt->valno->id]]; 00451 ++OutIt; 00452 for (iterator I = OutIt, E = end(); I != E; ++I) { 00453 OutIt->valno = NewVNInfo[LHSValNoAssignments[I->valno->id]]; 00454 00455 // If this live range has the same value # as its immediate predecessor, 00456 // and if they are neighbors, remove one LiveRange. This happens when we 00457 // have [0,3:0)[4,7:1) and map 0/1 onto the same value #. 00458 if (OutIt->valno == (OutIt-1)->valno && (OutIt-1)->end == OutIt->start) { 00459 (OutIt-1)->end = OutIt->end; 00460 } else { 00461 if (I != OutIt) { 00462 OutIt->start = I->start; 00463 OutIt->end = I->end; 00464 } 00465 00466 // Didn't merge, on to the next one. 00467 ++OutIt; 00468 } 00469 } 00470 00471 // If we merge some live ranges, chop off the end. 00472 ranges.erase(OutIt, end()); 00473 } 00474 00475 // Remember assignements because val# ids are changing. 00476 SmallVector<unsigned, 16> OtherAssignments; 00477 for (iterator I = Other.begin(), E = Other.end(); I != E; ++I) 00478 OtherAssignments.push_back(RHSValNoAssignments[I->valno->id]); 00479 00480 // Update val# info. Renumber them and make sure they all belong to this 00481 // LiveInterval now. Also remove dead val#'s. 00482 unsigned NumValNos = 0; 00483 for (unsigned i = 0; i < NumNewVals; ++i) { 00484 VNInfo *VNI = NewVNInfo[i]; 00485 if (VNI) { 00486 if (NumValNos >= NumVals) 00487 valnos.push_back(VNI); 00488 else 00489 valnos[NumValNos] = VNI; 00490 VNI->id = NumValNos++; // Renumber val#. 00491 } 00492 } 00493 if (NumNewVals < NumVals) 00494 valnos.resize(NumNewVals); // shrinkify 00495 00496 // Okay, now insert the RHS live ranges into the LHS. 00497 iterator InsertPos = begin(); 00498 unsigned RangeNo = 0; 00499 for (iterator I = Other.begin(), E = Other.end(); I != E; ++I, ++RangeNo) { 00500 // Map the valno in the other live range to the current live range. 00501 I->valno = NewVNInfo[OtherAssignments[RangeNo]]; 00502 assert(I->valno && "Adding a dead range?"); 00503 InsertPos = addRangeFrom(*I, InsertPos); 00504 } 00505 00506 ComputeJoinedWeight(Other); 00507 00508 // Update regalloc hint if currently there isn't one. 00509 if (TargetRegisterInfo::isVirtualRegister(reg) && 00510 TargetRegisterInfo::isVirtualRegister(Other.reg)) { 00511 std::pair<unsigned, unsigned> Hint = MRI->getRegAllocationHint(reg); 00512 if (Hint.first == 0 && Hint.second == 0) { 00513 std::pair<unsigned, unsigned> OtherHint = 00514 MRI->getRegAllocationHint(Other.reg); 00515 if (OtherHint.first || OtherHint.second) 00516 MRI->setRegAllocationHint(reg, OtherHint.first, OtherHint.second); 00517 } 00518 } 00519 } 00520 00521 /// MergeRangesInAsValue - Merge all of the intervals in RHS into this live 00522 /// interval as the specified value number. The LiveRanges in RHS are 00523 /// allowed to overlap with LiveRanges in the current interval, but only if 00524 /// the overlapping LiveRanges have the specified value number. 00525 void LiveInterval::MergeRangesInAsValue(const LiveInterval &RHS, 00526 VNInfo *LHSValNo) { 00527 // TODO: Make this more efficient. 00528 iterator InsertPos = begin(); 00529 for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) { 00530 // Map the valno in the other live range to the current live range. 00531 LiveRange Tmp = *I; 00532 Tmp.valno = LHSValNo; 00533 InsertPos = addRangeFrom(Tmp, InsertPos); 00534 } 00535 } 00536 00537 00538 /// MergeValueInAsValue - Merge all of the live ranges of a specific val# 00539 /// in RHS into this live interval as the specified value number. 00540 /// The LiveRanges in RHS are allowed to overlap with LiveRanges in the 00541 /// current interval, it will replace the value numbers of the overlaped 00542 /// live ranges with the specified value number. 00543 void LiveInterval::MergeValueInAsValue(const LiveInterval &RHS, 00544 const VNInfo *RHSValNo, VNInfo *LHSValNo) { 00545 SmallVector<VNInfo*, 4> ReplacedValNos; 00546 iterator IP = begin(); 00547 for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) { 00548 if (I->valno != RHSValNo) 00549 continue; 00550 unsigned Start = I->start, End = I->end; 00551 IP = std::upper_bound(IP, end(), Start); 00552 // If the start of this range overlaps with an existing liverange, trim it. 00553 if (IP != begin() && IP[-1].end > Start) { 00554 if (IP[-1].valno != LHSValNo) { 00555 ReplacedValNos.push_back(IP[-1].valno); 00556 IP[-1].valno = LHSValNo; // Update val#. 00557 } 00558 Start = IP[-1].end; 00559 // Trimmed away the whole range? 00560 if (Start >= End) continue; 00561 } 00562 // If the end of this range overlaps with an existing liverange, trim it. 00563 if (IP != end() && End > IP->start) { 00564 if (IP->valno != LHSValNo) { 00565 ReplacedValNos.push_back(IP->valno); 00566 IP->valno = LHSValNo; // Update val#. 00567 } 00568 End = IP->start; 00569 // If this trimmed away the whole range, ignore it. 00570 if (Start == End) continue; 00571 } 00572 00573 // Map the valno in the other live range to the current live range. 00574 IP = addRangeFrom(LiveRange(Start, End, LHSValNo), IP); 00575 } 00576 00577 00578 SmallSet<VNInfo*, 4> Seen; 00579 for (unsigned i = 0, e = ReplacedValNos.size(); i != e; ++i) { 00580 VNInfo *V1 = ReplacedValNos[i]; 00581 if (Seen.insert(V1)) { 00582 bool isDead = true; 00583 for (const_iterator I = begin(), E = end(); I != E; ++I) 00584 if (I->valno == V1) { 00585 isDead = false; 00586 break; 00587 } 00588 if (isDead) { 00589 // Now that V1 is dead, remove it. If it is the largest value number, 00590 // just nuke it (and any other deleted values neighboring it), otherwise 00591 // mark it as ~1U so it can be nuked later. 00592 if (V1->id == getNumValNums()-1) { 00593 do { 00594 VNInfo *VNI = valnos.back(); 00595 valnos.pop_back(); 00596 VNI->~VNInfo(); 00597 } while (!valnos.empty() && valnos.back()->isUnused()); 00598 } else { 00599 V1->setIsUnused(true); 00600 } 00601 } 00602 } 00603 } 00604 } 00605 00606 00607 /// MergeInClobberRanges - For any live ranges that are not defined in the 00608 /// current interval, but are defined in the Clobbers interval, mark them 00609 /// used with an unknown definition value. 00610 void LiveInterval::MergeInClobberRanges(const LiveInterval &Clobbers, 00611 BumpPtrAllocator &VNInfoAllocator) { 00612 if (Clobbers.empty()) return; 00613 00614 DenseMap<VNInfo*, VNInfo*> ValNoMaps; 00615 VNInfo *UnusedValNo = 0; 00616 iterator IP = begin(); 00617 for (const_iterator I = Clobbers.begin(), E = Clobbers.end(); I != E; ++I) { 00618 // For every val# in the Clobbers interval, create a new "unknown" val#. 00619 VNInfo *ClobberValNo = 0; 00620 DenseMap<VNInfo*, VNInfo*>::iterator VI = ValNoMaps.find(I->valno); 00621 if (VI != ValNoMaps.end()) 00622 ClobberValNo = VI->second; 00623 else if (UnusedValNo) 00624 ClobberValNo = UnusedValNo; 00625 else { 00626 UnusedValNo = ClobberValNo = getNextValue(0, 0, false, VNInfoAllocator); 00627 ValNoMaps.insert(std::make_pair(I->valno, ClobberValNo)); 00628 } 00629 00630 bool Done = false; 00631 unsigned Start = I->start, End = I->end; 00632 // If a clobber range starts before an existing range and ends after 00633 // it, the clobber range will need to be split into multiple ranges. 00634 // Loop until the entire clobber range is handled. 00635 while (!Done) { 00636 Done = true; 00637 IP = std::upper_bound(IP, end(), Start); 00638 unsigned SubRangeStart = Start; 00639 unsigned SubRangeEnd = End; 00640 00641 // If the start of this range overlaps with an existing liverange, trim it. 00642 if (IP != begin() && IP[-1].end > SubRangeStart) { 00643 SubRangeStart = IP[-1].end; 00644 // Trimmed away the whole range? 00645 if (SubRangeStart >= SubRangeEnd) continue; 00646 } 00647 // If the end of this range overlaps with an existing liverange, trim it. 00648 if (IP != end() && SubRangeEnd > IP->start) { 00649 // If the clobber live range extends beyond the existing live range, 00650 // it'll need at least another live range, so set the flag to keep 00651 // iterating. 00652 if (SubRangeEnd > IP->end) { 00653 Start = IP->end; 00654 Done = false; 00655 } 00656 SubRangeEnd = IP->start; 00657 // If this trimmed away the whole range, ignore it. 00658 if (SubRangeStart == SubRangeEnd) continue; 00659 } 00660 00661 // Insert the clobber interval. 00662 IP = addRangeFrom(LiveRange(SubRangeStart, SubRangeEnd, ClobberValNo), 00663 IP); 00664 UnusedValNo = 0; 00665 } 00666 } 00667 00668 if (UnusedValNo) { 00669 // Delete the last unused val#. 00670 valnos.pop_back(); 00671 UnusedValNo->~VNInfo(); 00672 } 00673 } 00674 00675 void LiveInterval::MergeInClobberRange(unsigned Start, unsigned End, 00676 BumpPtrAllocator &VNInfoAllocator) { 00677 // Find a value # to use for the clobber ranges. If there is already a value# 00678 // for unknown values, use it. 00679 VNInfo *ClobberValNo = getNextValue(0, 0, false, VNInfoAllocator); 00680 00681 iterator IP = begin(); 00682 IP = std::upper_bound(IP, end(), Start); 00683 00684 // If the start of this range overlaps with an existing liverange, trim it. 00685 if (IP != begin() && IP[-1].end > Start) { 00686 Start = IP[-1].end; 00687 // Trimmed away the whole range? 00688 if (Start >= End) return; 00689 } 00690 // If the end of this range overlaps with an existing liverange, trim it. 00691 if (IP != end() && End > IP->start) { 00692 End = IP->start; 00693 // If this trimmed away the whole range, ignore it. 00694 if (Start == End) return; 00695 } 00696 00697 // Insert the clobber interval. 00698 addRangeFrom(LiveRange(Start, End, ClobberValNo), IP); 00699 } 00700 00701 /// MergeValueNumberInto - This method is called when two value nubmers 00702 /// are found to be equivalent. This eliminates V1, replacing all 00703 /// LiveRanges with the V1 value number with the V2 value number. This can 00704 /// cause merging of V1/V2 values numbers and compaction of the value space. 00705 VNInfo* LiveInterval::MergeValueNumberInto(VNInfo *V1, VNInfo *V2) { 00706 assert(V1 != V2 && "Identical value#'s are always equivalent!"); 00707 00708 // This code actually merges the (numerically) larger value number into the 00709 // smaller value number, which is likely to allow us to compactify the value 00710 // space. The only thing we have to be careful of is to preserve the 00711 // instruction that defines the result value. 00712 00713 // Make sure V2 is smaller than V1. 00714 if (V1->id < V2->id) { 00715 V1->copyFrom(*V2); 00716 std::swap(V1, V2); 00717 } 00718 00719 // Merge V1 live ranges into V2. 00720 for (iterator I = begin(); I != end(); ) { 00721 iterator LR = I++; 00722 if (LR->valno != V1) continue; // Not a V1 LiveRange. 00723 00724 // Okay, we found a V1 live range. If it had a previous, touching, V2 live 00725 // range, extend it. 00726 if (LR != begin()) { 00727 iterator Prev = LR-1; 00728 if (Prev->valno == V2 && Prev->end == LR->start) { 00729 Prev->end = LR->end; 00730 00731 // Erase this live-range. 00732 ranges.erase(LR); 00733 I = Prev+1; 00734 LR = Prev; 00735 } 00736 } 00737 00738 // Okay, now we have a V1 or V2 live range that is maximally merged forward. 00739 // Ensure that it is a V2 live-range. 00740 LR->valno = V2; 00741 00742 // If we can merge it into later V2 live ranges, do so now. We ignore any 00743 // following V1 live ranges, as they will be merged in subsequent iterations 00744 // of the loop. 00745 if (I != end()) { 00746 if (I->start == LR->end && I->valno == V2) { 00747 LR->end = I->end; 00748 ranges.erase(I); 00749 I = LR+1; 00750 } 00751 } 00752 } 00753 00754 // Now that V1 is dead, remove it. If it is the largest value number, just 00755 // nuke it (and any other deleted values neighboring it), otherwise mark it as 00756 // ~1U so it can be nuked later. 00757 if (V1->id == getNumValNums()-1) { 00758 do { 00759 VNInfo *VNI = valnos.back(); 00760 valnos.pop_back(); 00761 VNI->~VNInfo(); 00762 } while (valnos.back()->isUnused()); 00763 } else { 00764 V1->setIsUnused(true); 00765 } 00766 00767 return V2; 00768 } 00769 00770 void LiveInterval::Copy(const LiveInterval &RHS, 00771 MachineRegisterInfo *MRI, 00772 BumpPtrAllocator &VNInfoAllocator) { 00773 ranges.clear(); 00774 valnos.clear(); 00775 std::pair<unsigned, unsigned> Hint = MRI->getRegAllocationHint(RHS.reg); 00776 MRI->setRegAllocationHint(reg, Hint.first, Hint.second); 00777 00778 weight = RHS.weight; 00779 for (unsigned i = 0, e = RHS.getNumValNums(); i != e; ++i) { 00780 const VNInfo *VNI = RHS.getValNumInfo(i); 00781 createValueCopy(VNI, VNInfoAllocator); 00782 } 00783 for (unsigned i = 0, e = RHS.ranges.size(); i != e; ++i) { 00784 const LiveRange &LR = RHS.ranges[i]; 00785 addRange(LiveRange(LR.start, LR.end, getValNumInfo(LR.valno->id))); 00786 } 00787 } 00788 00789 unsigned LiveInterval::getSize() const { 00790 unsigned Sum = 0; 00791 for (const_iterator I = begin(), E = end(); I != E; ++I) 00792 Sum += I->end - I->start; 00793 return Sum; 00794 } 00795 00796 /// ComputeJoinedWeight - Set the weight of a live interval Joined 00797 /// after Other has been merged into it. 00798 void LiveInterval::ComputeJoinedWeight(const LiveInterval &Other) { 00799 // If either of these intervals was spilled, the weight is the 00800 // weight of the non-spilled interval. This can only happen with 00801 // iterative coalescers. 00802 00803 if (Other.weight != HUGE_VALF) { 00804 weight += Other.weight; 00805 } 00806 else if (weight == HUGE_VALF && 00807 !TargetRegisterInfo::isPhysicalRegister(reg)) { 00808 // Remove this assert if you have an iterative coalescer 00809 assert(0 && "Joining to spilled interval"); 00810 weight = Other.weight; 00811 } 00812 else { 00813 // Otherwise the weight stays the same 00814 // Remove this assert if you have an iterative coalescer 00815 assert(0 && "Joining from spilled interval"); 00816 } 00817 } 00818 00819 std::ostream& llvm::operator<<(std::ostream& os, const LiveRange &LR) { 00820 return os << '[' << LR.start << ',' << LR.end << ':' << LR.valno->id << ")"; 00821 } 00822 raw_ostream& llvm::operator<<(raw_ostream& os, const LiveRange &LR) { 00823 return os << '[' << LR.start << ',' << LR.end << ':' << LR.valno->id << ")"; 00824 } 00825 00826 void LiveRange::dump() const { 00827 errs() << *this << "\n"; 00828 } 00829 00830 void LiveInterval::print(std::ostream &OS, 00831 const TargetRegisterInfo *TRI) const { 00832 raw_os_ostream RawOS(OS); 00833 print(RawOS, TRI); 00834 } 00835 00836 void LiveInterval::print(raw_ostream &OS, 00837 const TargetRegisterInfo *TRI) const { 00838 if (isStackSlot()) 00839 OS << "SS#" << getStackSlotIndex(); 00840 else if (TRI && TargetRegisterInfo::isPhysicalRegister(reg)) 00841 OS << TRI->getName(reg); 00842 else 00843 OS << "%reg" << reg; 00844 00845 OS << ',' << weight; 00846 00847 if (empty()) 00848 OS << " EMPTY"; 00849 else { 00850 OS << " = "; 00851 for (LiveInterval::Ranges::const_iterator I = ranges.begin(), 00852 E = ranges.end(); I != E; ++I) 00853 OS << *I; 00854 } 00855 00856 // Print value number info. 00857 if (getNumValNums()) { 00858 OS << " "; 00859 unsigned vnum = 0; 00860 for (const_vni_iterator i = vni_begin(), e = vni_end(); i != e; 00861 ++i, ++vnum) { 00862 const VNInfo *vni = *i; 00863 if (vnum) OS << " "; 00864 OS << vnum << "@"; 00865 if (vni->isUnused()) { 00866 OS << "x"; 00867 } else { 00868 if (!vni->isDefAccurate()) 00869 OS << "?"; 00870 else 00871 OS << vni->def; 00872 unsigned ee = vni->kills.size(); 00873 if (ee || vni->hasPHIKill()) { 00874 OS << "-("; 00875 for (unsigned j = 0; j != ee; ++j) { 00876 OS << vni->kills[j].killIdx; 00877 if (vni->kills[j].isPHIKill) 00878 OS << "*"; 00879 if (j != ee-1) 00880 OS << " "; 00881 } 00882 if (vni->hasPHIKill()) { 00883 if (ee) 00884 OS << " "; 00885 OS << "phi"; 00886 } 00887 OS << ")"; 00888 } 00889 } 00890 } 00891 } 00892 } 00893 00894 void LiveInterval::dump() const { 00895 errs() << *this << "\n"; 00896 } 00897 00898 00899 void LiveRange::print(std::ostream &os) const { 00900 os << *this; 00901 } 00902 void LiveRange::print(raw_ostream &os) const { 00903 os << *this; 00904 }