LLVM API Documentation
00001 //===-- LiveInterval.cpp - Live Interval Representation -------------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source 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/ADT/STLExtras.h" 00023 #include "llvm/Target/MRegisterInfo.h" 00024 #include <algorithm> 00025 #include <iostream> 00026 #include <map> 00027 using namespace llvm; 00028 00029 // An example for liveAt(): 00030 // 00031 // this = [1,4), liveAt(0) will return false. The instruction defining this 00032 // spans slots [0,3]. The interval belongs to an spilled definition of the 00033 // variable it represents. This is because slot 1 is used (def slot) and spans 00034 // up to slot 3 (store slot). 00035 // 00036 bool LiveInterval::liveAt(unsigned I) const { 00037 Ranges::const_iterator r = std::upper_bound(ranges.begin(), ranges.end(), I); 00038 00039 if (r == ranges.begin()) 00040 return false; 00041 00042 --r; 00043 return r->contains(I); 00044 } 00045 00046 // overlaps - Return true if the intersection of the two live intervals is 00047 // not empty. 00048 // 00049 // An example for overlaps(): 00050 // 00051 // 0: A = ... 00052 // 4: B = ... 00053 // 8: C = A + B ;; last use of A 00054 // 00055 // The live intervals should look like: 00056 // 00057 // A = [3, 11) 00058 // B = [7, x) 00059 // C = [11, y) 00060 // 00061 // A->overlaps(C) should return false since we want to be able to join 00062 // A and C. 00063 // 00064 bool LiveInterval::overlapsFrom(const LiveInterval& other, 00065 const_iterator StartPos) const { 00066 const_iterator i = begin(); 00067 const_iterator ie = end(); 00068 const_iterator j = StartPos; 00069 const_iterator je = other.end(); 00070 00071 assert((StartPos->start <= i->start || StartPos == other.begin()) && 00072 StartPos != other.end() && "Bogus start position hint!"); 00073 00074 if (i->start < j->start) { 00075 i = std::upper_bound(i, ie, j->start); 00076 if (i != ranges.begin()) --i; 00077 } else if (j->start < i->start) { 00078 ++StartPos; 00079 if (StartPos != other.end() && StartPos->start <= i->start) { 00080 assert(StartPos < other.end() && i < end()); 00081 j = std::upper_bound(j, je, i->start); 00082 if (j != other.ranges.begin()) --j; 00083 } 00084 } else { 00085 return true; 00086 } 00087 00088 if (j == je) return false; 00089 00090 while (i != ie) { 00091 if (i->start > j->start) { 00092 std::swap(i, j); 00093 std::swap(ie, je); 00094 } 00095 00096 if (i->end > j->start) 00097 return true; 00098 ++i; 00099 } 00100 00101 return false; 00102 } 00103 00104 /// NontrivialOverlap - Check to see if the two live ranges specified by i and j 00105 /// overlap. If so, check to see if they have value numbers that are not 00106 /// iIdx/jIdx respectively. If both conditions are true, return true. 00107 static inline bool NontrivialOverlap(const LiveRange &I, const LiveRange &J, 00108 unsigned iIdx, unsigned jIdx) { 00109 if (I.start == J.start) { 00110 // If this is not the allowed value merge, we cannot join. 00111 if (I.ValId != iIdx || J.ValId != jIdx) 00112 return true; 00113 } else if (I.start < J.start) { 00114 if (I.end > J.start && (I.ValId != iIdx || J.ValId != jIdx)) { 00115 return true; 00116 } 00117 } else { 00118 if (J.end > I.start && (I.ValId != iIdx || J.ValId != jIdx)) 00119 return true; 00120 } 00121 00122 return false; 00123 } 00124 00125 /// joinable - Two intervals are joinable if the either don't overlap at all 00126 /// or if the destination of the copy is a single assignment value, and it 00127 /// only overlaps with one value in the source interval. 00128 bool LiveInterval::joinable(const LiveInterval &other, unsigned CopyIdx) const { 00129 const LiveRange *SourceLR = other.getLiveRangeContaining(CopyIdx-1); 00130 const LiveRange *DestLR = getLiveRangeContaining(CopyIdx); 00131 assert(SourceLR && DestLR && "Not joining due to a copy?"); 00132 unsigned OtherValIdx = SourceLR->ValId; 00133 unsigned ThisValIdx = DestLR->ValId; 00134 00135 Ranges::const_iterator i = ranges.begin(); 00136 Ranges::const_iterator ie = ranges.end(); 00137 Ranges::const_iterator j = other.ranges.begin(); 00138 Ranges::const_iterator je = other.ranges.end(); 00139 00140 if (i->start < j->start) { 00141 i = std::upper_bound(i, ie, j->start); 00142 if (i != ranges.begin()) --i; 00143 } else if (j->start < i->start) { 00144 j = std::upper_bound(j, je, i->start); 00145 if (j != other.ranges.begin()) --j; 00146 } 00147 00148 while (i != ie && j != je) { 00149 if (NontrivialOverlap(*i, *j, ThisValIdx, OtherValIdx)) 00150 return false; 00151 00152 if (i->end < j->end) 00153 ++i; 00154 else 00155 ++j; 00156 } 00157 00158 return true; 00159 } 00160 00161 /// getOverlapingRanges - Given another live interval which is defined as a 00162 /// copy from this one, return a list of all of the live ranges where the 00163 /// two overlap and have different value numbers. 00164 void LiveInterval::getOverlapingRanges(const LiveInterval &other, 00165 unsigned CopyIdx, 00166 std::vector<LiveRange*> &Ranges) { 00167 const LiveRange *SourceLR = getLiveRangeContaining(CopyIdx-1); 00168 const LiveRange *DestLR = other.getLiveRangeContaining(CopyIdx); 00169 assert(SourceLR && DestLR && "Not joining due to a copy?"); 00170 unsigned OtherValIdx = SourceLR->ValId; 00171 unsigned ThisValIdx = DestLR->ValId; 00172 00173 Ranges::iterator i = ranges.begin(); 00174 Ranges::iterator ie = ranges.end(); 00175 Ranges::const_iterator j = other.ranges.begin(); 00176 Ranges::const_iterator je = other.ranges.end(); 00177 00178 if (i->start < j->start) { 00179 i = std::upper_bound(i, ie, j->start); 00180 if (i != ranges.begin()) --i; 00181 } else if (j->start < i->start) { 00182 j = std::upper_bound(j, je, i->start); 00183 if (j != other.ranges.begin()) --j; 00184 } 00185 00186 while (i != ie && j != je) { 00187 if (NontrivialOverlap(*i, *j, ThisValIdx, OtherValIdx)) 00188 Ranges.push_back(&*i); 00189 00190 if (i->end < j->end) 00191 ++i; 00192 else 00193 ++j; 00194 } 00195 } 00196 00197 00198 00199 /// extendIntervalEndTo - This method is used when we want to extend the range 00200 /// specified by I to end at the specified endpoint. To do this, we should 00201 /// merge and eliminate all ranges that this will overlap with. The iterator is 00202 /// not invalidated. 00203 void LiveInterval::extendIntervalEndTo(Ranges::iterator I, unsigned NewEnd) { 00204 assert(I != ranges.end() && "Not a valid interval!"); 00205 unsigned ValId = I->ValId; 00206 00207 // Search for the first interval that we can't merge with. 00208 Ranges::iterator MergeTo = next(I); 00209 for (; MergeTo != ranges.end() && NewEnd >= MergeTo->end; ++MergeTo) { 00210 assert(MergeTo->ValId == ValId && "Cannot merge with differing values!"); 00211 } 00212 00213 // If NewEnd was in the middle of an interval, make sure to get its endpoint. 00214 I->end = std::max(NewEnd, prior(MergeTo)->end); 00215 00216 // Erase any dead ranges. 00217 ranges.erase(next(I), MergeTo); 00218 00219 // If the newly formed range now touches the range after it and if they have 00220 // the same value number, merge the two ranges into one range. 00221 Ranges::iterator Next = next(I); 00222 if (Next != ranges.end() && Next->start <= I->end && Next->ValId == ValId) { 00223 I->end = Next->end; 00224 ranges.erase(Next); 00225 } 00226 } 00227 00228 00229 /// extendIntervalStartTo - This method is used when we want to extend the range 00230 /// specified by I to start at the specified endpoint. To do this, we should 00231 /// merge and eliminate all ranges that this will overlap with. 00232 LiveInterval::Ranges::iterator 00233 LiveInterval::extendIntervalStartTo(Ranges::iterator I, unsigned NewStart) { 00234 assert(I != ranges.end() && "Not a valid interval!"); 00235 unsigned ValId = I->ValId; 00236 00237 // Search for the first interval that we can't merge with. 00238 Ranges::iterator MergeTo = I; 00239 do { 00240 if (MergeTo == ranges.begin()) { 00241 I->start = NewStart; 00242 ranges.erase(MergeTo, I); 00243 return I; 00244 } 00245 assert(MergeTo->ValId == ValId && "Cannot merge with differing values!"); 00246 --MergeTo; 00247 } while (NewStart <= MergeTo->start); 00248 00249 // If we start in the middle of another interval, just delete a range and 00250 // extend that interval. 00251 if (MergeTo->end >= NewStart && MergeTo->ValId == ValId) { 00252 MergeTo->end = I->end; 00253 } else { 00254 // Otherwise, extend the interval right after. 00255 ++MergeTo; 00256 MergeTo->start = NewStart; 00257 MergeTo->end = I->end; 00258 } 00259 00260 ranges.erase(next(MergeTo), next(I)); 00261 return MergeTo; 00262 } 00263 00264 LiveInterval::Ranges::iterator 00265 LiveInterval::addRangeFrom(LiveRange LR, Ranges::iterator From) { 00266 unsigned Start = LR.start, End = LR.end; 00267 Ranges::iterator it = std::upper_bound(From, ranges.end(), Start); 00268 00269 // If the inserted interval starts in the middle or right at the end of 00270 // another interval, just extend that interval to contain the range of LR. 00271 if (it != ranges.begin()) { 00272 Ranges::iterator B = prior(it); 00273 if (LR.ValId == B->ValId) { 00274 if (B->start <= Start && B->end >= Start) { 00275 extendIntervalEndTo(B, End); 00276 return B; 00277 } 00278 } else { 00279 // Check to make sure that we are not overlapping two live ranges with 00280 // different ValId's. 00281 assert(B->end <= Start && 00282 "Cannot overlap two LiveRanges with differing ValID's" 00283 " (did you def the same reg twice in a MachineInstr?)"); 00284 } 00285 } 00286 00287 // Otherwise, if this range ends in the middle of, or right next to, another 00288 // interval, merge it into that interval. 00289 if (it != ranges.end()) 00290 if (LR.ValId == it->ValId) { 00291 if (it->start <= End) { 00292 it = extendIntervalStartTo(it, Start); 00293 00294 // If LR is a complete superset of an interval, we may need to grow its 00295 // endpoint as well. 00296 if (End > it->end) 00297 extendIntervalEndTo(it, End); 00298 return it; 00299 } 00300 } else { 00301 // Check to make sure that we are not overlapping two live ranges with 00302 // different ValId's. 00303 assert(it->start >= End && 00304 "Cannot overlap two LiveRanges with differing ValID's"); 00305 } 00306 00307 // Otherwise, this is just a new range that doesn't interact with anything. 00308 // Insert it. 00309 return ranges.insert(it, LR); 00310 } 00311 00312 00313 /// removeRange - Remove the specified range from this interval. Note that 00314 /// the range must already be in this interval in its entirety. 00315 void LiveInterval::removeRange(unsigned Start, unsigned End) { 00316 // Find the LiveRange containing this span. 00317 Ranges::iterator I = std::upper_bound(ranges.begin(), ranges.end(), Start); 00318 assert(I != ranges.begin() && "Range is not in interval!"); 00319 --I; 00320 assert(I->contains(Start) && I->contains(End-1) && 00321 "Range is not entirely in interval!"); 00322 00323 // If the span we are removing is at the start of the LiveRange, adjust it. 00324 if (I->start == Start) { 00325 if (I->end == End) 00326 ranges.erase(I); // Removed the whole LiveRange. 00327 else 00328 I->start = End; 00329 return; 00330 } 00331 00332 // Otherwise if the span we are removing is at the end of the LiveRange, 00333 // adjust the other way. 00334 if (I->end == End) { 00335 I->end = Start; 00336 return; 00337 } 00338 00339 // Otherwise, we are splitting the LiveRange into two pieces. 00340 unsigned OldEnd = I->end; 00341 I->end = Start; // Trim the old interval. 00342 00343 // Insert the new one. 00344 ranges.insert(next(I), LiveRange(End, OldEnd, I->ValId)); 00345 } 00346 00347 /// getLiveRangeContaining - Return the live range that contains the 00348 /// specified index, or null if there is none. 00349 const LiveRange *LiveInterval::getLiveRangeContaining(unsigned Idx) const { 00350 Ranges::const_iterator It = std::upper_bound(ranges.begin(),ranges.end(),Idx); 00351 if (It != ranges.begin()) { 00352 const LiveRange &LR = *prior(It); 00353 if (LR.contains(Idx)) 00354 return &LR; 00355 } 00356 00357 return 0; 00358 } 00359 00360 00361 00362 /// join - Join two live intervals (this, and other) together. This operation 00363 /// is the result of a copy instruction in the source program, that occurs at 00364 /// index 'CopyIdx' that copies from 'Other' to 'this'. 00365 void LiveInterval::join(LiveInterval &Other, unsigned CopyIdx) { 00366 const LiveRange *SourceLR = Other.getLiveRangeContaining(CopyIdx-1); 00367 const LiveRange *DestLR = getLiveRangeContaining(CopyIdx); 00368 assert(SourceLR && DestLR && "Not joining due to a copy?"); 00369 unsigned MergedSrcValIdx = SourceLR->ValId; 00370 unsigned MergedDstValIdx = DestLR->ValId; 00371 00372 // Try to do the least amount of work possible. In particular, if there are 00373 // more liverange chunks in the other set than there are in the 'this' set, 00374 // swap sets to merge the fewest chunks in possible. 00375 if (Other.ranges.size() > ranges.size()) { 00376 std::swap(MergedSrcValIdx, MergedDstValIdx); 00377 std::swap(ranges, Other.ranges); 00378 std::swap(NumValues, Other.NumValues); 00379 } 00380 00381 // Join the ranges of other into the ranges of this interval. 00382 Ranges::iterator InsertPos = ranges.begin(); 00383 std::map<unsigned, unsigned> Dst2SrcIdxMap; 00384 for (Ranges::iterator I = Other.ranges.begin(), 00385 E = Other.ranges.end(); I != E; ++I) { 00386 // Map the ValId in the other live range to the current live range. 00387 if (I->ValId == MergedSrcValIdx) 00388 I->ValId = MergedDstValIdx; 00389 else { 00390 unsigned &NV = Dst2SrcIdxMap[I->ValId]; 00391 if (NV == 0) NV = getNextValue(); 00392 I->ValId = NV; 00393 } 00394 00395 InsertPos = addRangeFrom(*I, InsertPos); 00396 } 00397 00398 weight += Other.weight; 00399 } 00400 00401 std::ostream& llvm::operator<<(std::ostream& os, const LiveRange &LR) { 00402 return os << '[' << LR.start << ',' << LR.end << ':' << LR.ValId << ")"; 00403 } 00404 00405 void LiveRange::dump() const { 00406 std::cerr << *this << "\n"; 00407 } 00408 00409 void LiveInterval::print(std::ostream &OS, const MRegisterInfo *MRI) const { 00410 if (MRI && MRegisterInfo::isPhysicalRegister(reg)) 00411 OS << MRI->getName(reg); 00412 else 00413 OS << "%reg" << reg; 00414 00415 OS << ',' << weight; 00416 00417 if (empty()) 00418 OS << "EMPTY"; 00419 else { 00420 OS << " = "; 00421 for (LiveInterval::Ranges::const_iterator I = ranges.begin(), 00422 E = ranges.end(); I != E; ++I) 00423 OS << *I; 00424 } 00425 } 00426 00427 void LiveInterval::dump() const { 00428 std::cerr << *this << "\n"; 00429 }