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