LiveInterval.cpp revision c4d3b918165461bc6f5d395bca8d9d9d8a84413d
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 "LiveInterval.h" 22#include "llvm/ADT/STLExtras.h" 23#include <algorithm> 24#include <iostream> 25#include <map> 26using namespace llvm; 27 28// An example for liveAt(): 29// 30// this = [1,4), liveAt(0) will return false. The instruction defining this 31// spans slots [0,3]. The interval belongs to an spilled definition of the 32// variable it represents. This is because slot 1 is used (def slot) and spans 33// up to slot 3 (store slot). 34// 35bool LiveInterval::liveAt(unsigned I) const { 36 Ranges::const_iterator r = std::upper_bound(ranges.begin(), ranges.end(), I); 37 38 if (r == ranges.begin()) 39 return false; 40 41 --r; 42 return r->contains(I); 43} 44 45// An example for overlaps(): 46// 47// 0: A = ... 48// 4: B = ... 49// 8: C = A + B ;; last use of A 50// 51// The live intervals should look like: 52// 53// A = [3, 11) 54// B = [7, x) 55// C = [11, y) 56// 57// A->overlaps(C) should return false since we want to be able to join 58// A and C. 59bool LiveInterval::overlaps(const LiveInterval& other) const { 60 Ranges::const_iterator i = ranges.begin(); 61 Ranges::const_iterator ie = ranges.end(); 62 Ranges::const_iterator j = other.ranges.begin(); 63 Ranges::const_iterator je = other.ranges.end(); 64 65 if (i->start < j->start) { 66 i = std::upper_bound(i, ie, j->start); 67 if (i != ranges.begin()) --i; 68 } else if (j->start < i->start) { 69 j = std::upper_bound(j, je, i->start); 70 if (j != other.ranges.begin()) --j; 71 } else { 72 return true; 73 } 74 75 while (i != ie && j != je) { 76 if (i->start == j->start) 77 return true; 78 79 if (i->start > j->start) { 80 std::swap(i, j); 81 std::swap(ie, je); 82 } 83 assert(i->start < j->start); 84 85 if (i->end > j->start) 86 return true; 87 ++i; 88 } 89 90 return false; 91} 92 93/// joinable - Two intervals are joinable if the either don't overlap at all 94/// or if the destination of the copy is a single assignment value, and it 95/// only overlaps with one value in the source interval. 96bool LiveInterval::joinable(const LiveInterval &other, unsigned CopyIdx) const { 97 const LiveRange *SourceLR = other.getLiveRangeContaining(CopyIdx-1); 98 const LiveRange *DestLR = getLiveRangeContaining(CopyIdx); 99 assert(SourceLR && DestLR && "Not joining due to a copy?"); 100 unsigned OtherValIdx = SourceLR->ValId; 101 unsigned ThisValIdx = DestLR->ValId; 102 103 Ranges::const_iterator i = ranges.begin(); 104 Ranges::const_iterator ie = ranges.end(); 105 Ranges::const_iterator j = other.ranges.begin(); 106 Ranges::const_iterator je = other.ranges.end(); 107 108 if (i->start < j->start) { 109 i = std::upper_bound(i, ie, j->start); 110 if (i != ranges.begin()) --i; 111 } else if (j->start < i->start) { 112 j = std::upper_bound(j, je, i->start); 113 if (j != other.ranges.begin()) --j; 114 } 115 116 while (i != ie && j != je) { 117 if (i->start == j->start) { 118 // If this is not the allowed value merge, we cannot join. 119 if (i->ValId != ThisValIdx || j->ValId != OtherValIdx) 120 return false; 121 } else if (i->start < j->start) { 122 if (i->end > j->start) { 123 if (i->ValId != ThisValIdx || j->ValId != OtherValIdx) 124 return false; 125 } 126 } else { 127 if (j->end > i->start) { 128 if (i->ValId != ThisValIdx || j->ValId != OtherValIdx) 129 return false; 130 } 131 } 132 if (i->end < j->end) 133 ++i; 134 else 135 ++j; 136 } 137 138 return true; 139} 140 141 142/// extendIntervalEndTo - This method is used when we want to extend the range 143/// specified by I to end at the specified endpoint. To do this, we should 144/// merge and eliminate all ranges that this will overlap with. The iterator is 145/// not invalidated. 146void LiveInterval::extendIntervalEndTo(Ranges::iterator I, unsigned NewEnd) { 147 assert(I != ranges.end() && "Not a valid interval!"); 148 unsigned ValId = I->ValId; 149 150 // Search for the first interval that we can't merge with. 151 Ranges::iterator MergeTo = next(I); 152 for (; MergeTo != ranges.end() && NewEnd >= MergeTo->end; ++MergeTo) { 153 assert(MergeTo->ValId == ValId && "Cannot merge with differing values!"); 154 } 155 156 // If NewEnd was in the middle of an interval, make sure to get its endpoint. 157 I->end = std::max(NewEnd, prior(MergeTo)->end); 158 159 // Erase any dead ranges 160 ranges.erase(next(I), MergeTo); 161} 162 163 164/// extendIntervalStartTo - This method is used when we want to extend the range 165/// specified by I to start at the specified endpoint. To do this, we should 166/// merge and eliminate all ranges that this will overlap with. 167LiveInterval::Ranges::iterator 168LiveInterval::extendIntervalStartTo(Ranges::iterator I, unsigned NewStart) { 169 assert(I != ranges.end() && "Not a valid interval!"); 170 unsigned ValId = I->ValId; 171 172 // Search for the first interval that we can't merge with. 173 Ranges::iterator MergeTo = I; 174 do { 175 if (MergeTo == ranges.begin()) { 176 I->start = NewStart; 177 ranges.erase(MergeTo, I); 178 return I; 179 } 180 assert(MergeTo->ValId == ValId && "Cannot merge with differing values!"); 181 --MergeTo; 182 } while (NewStart <= MergeTo->start); 183 184 // If we start in the middle of another interval, just delete a range and 185 // extend that interval. 186 if (MergeTo->end >= NewStart && MergeTo->ValId == ValId) { 187 MergeTo->end = I->end; 188 } else { 189 // Otherwise, extend the interval right after. 190 ++MergeTo; 191 MergeTo->start = NewStart; 192 MergeTo->end = I->end; 193 } 194 195 ranges.erase(next(MergeTo), next(I)); 196 return MergeTo; 197} 198 199LiveInterval::Ranges::iterator 200LiveInterval::addRangeFrom(LiveRange LR, Ranges::iterator From) { 201 unsigned Start = LR.start, End = LR.end; 202 Ranges::iterator it = std::upper_bound(From, ranges.end(), Start); 203 204 // If the inserted interval starts in the middle or right at the end of 205 // another interval, just extend that interval to contain the range of LR. 206 if (it != ranges.begin()) { 207 Ranges::iterator B = prior(it); 208 if (LR.ValId == B->ValId) { 209 if (B->start <= Start && B->end >= Start) { 210 extendIntervalEndTo(B, End); 211 return B; 212 } 213 } else { 214 // Check to make sure that we are not overlapping two live ranges with 215 // different ValId's. 216 assert(B->end <= Start && 217 "Cannot overlap two LiveRanges with differing ValID's"); 218 } 219 } 220 221 // Otherwise, if this range ends in the middle of, or right next to, another 222 // interval, merge it into that interval. 223 if (it != ranges.end()) 224 if (LR.ValId == it->ValId) { 225 if (it->start <= End) { 226 it = extendIntervalStartTo(it, Start); 227 228 // If LR is a complete superset of an interval, we may need to grow its 229 // endpoint as well. 230 if (End > it->end) 231 extendIntervalEndTo(it, End); 232 return it; 233 } 234 } else { 235 // Check to make sure that we are not overlapping two live ranges with 236 // different ValId's. 237 assert(it->start >= End && 238 "Cannot overlap two LiveRanges with differing ValID's"); 239 } 240 241 // Otherwise, this is just a new range that doesn't interact with anything. 242 // Insert it. 243 return ranges.insert(it, LR); 244} 245 246 247/// removeRange - Remove the specified range from this interval. Note that 248/// the range must already be in this interval in its entirety. 249void LiveInterval::removeRange(unsigned Start, unsigned End) { 250 // Find the LiveRange containing this span. 251 Ranges::iterator I = std::upper_bound(ranges.begin(), ranges.end(), Start); 252 assert(I != ranges.begin() && "Range is not in interval!"); 253 --I; 254 assert(I->contains(Start) && I->contains(End-1) && 255 "Range is not entirely in interval!"); 256 257 // If the span we are removing is at the start of the LiveRange, adjust it. 258 if (I->start == Start) { 259 if (I->end == End) 260 ranges.erase(I); // Removed the whole LiveRange. 261 else 262 I->start = End; 263 return; 264 } 265 266 // Otherwise if the span we are removing is at the end of the LiveRange, 267 // adjust the other way. 268 if (I->end == End) { 269 I->end = Start; 270 return; 271 } 272 273 // Otherwise, we are splitting the LiveRange into two pieces. 274 unsigned OldEnd = I->end; 275 I->end = Start; // Trim the old interval. 276 277 // Insert the new one. 278 ranges.insert(next(I), LiveRange(End, OldEnd, I->ValId)); 279} 280 281/// getLiveRangeContaining - Return the live range that contains the 282/// specified index, or null if there is none. 283const LiveRange *LiveInterval::getLiveRangeContaining(unsigned Idx) const { 284 Ranges::const_iterator It = std::upper_bound(ranges.begin(),ranges.end(),Idx); 285 if (It != ranges.begin()) { 286 const LiveRange &LR = *prior(It); 287 if (LR.contains(Idx)) 288 return &LR; 289 } 290 291 return 0; 292} 293 294 295 296/// join - Join two live intervals (this, and other) together. This operation 297/// is the result of a copy instruction in the source program, that occurs at 298/// index 'CopyIdx' that copies from 'Other' to 'this'. 299void LiveInterval::join(LiveInterval &Other, unsigned CopyIdx) { 300 const LiveRange *SourceLR = Other.getLiveRangeContaining(CopyIdx-1); 301 const LiveRange *DestLR = getLiveRangeContaining(CopyIdx); 302 assert(SourceLR && DestLR && "Not joining due to a copy?"); 303 unsigned MergedSrcValIdx = SourceLR->ValId; 304 unsigned MergedDstValIdx = DestLR->ValId; 305 306 // Try to do the least amount of work possible. In particular, if there are 307 // more liverange chunks in the other set than there are in the 'this' set, 308 // swap sets to merge the fewest chunks in possible. 309 if (Other.ranges.size() > ranges.size()) { 310 std::swap(MergedSrcValIdx, MergedDstValIdx); 311 std::swap(ranges, Other.ranges); 312 std::swap(NumValues, Other.NumValues); 313 } 314 315 // Join the ranges of other into the ranges of this interval. 316 Ranges::iterator InsertPos = ranges.begin(); 317 std::map<unsigned, unsigned> Dst2SrcIdxMap; 318 for (Ranges::iterator I = Other.ranges.begin(), 319 E = Other.ranges.end(); I != E; ++I) { 320 // Map the ValId in the other live range to the current live range. 321 if (I->ValId == MergedSrcValIdx) 322 I->ValId = MergedDstValIdx; 323 else { 324 unsigned &NV = Dst2SrcIdxMap[I->ValId]; 325 if (NV == 0) NV = getNextValue(); 326 I->ValId = NV; 327 } 328 329 InsertPos = addRangeFrom(*I, InsertPos); 330 } 331 332 weight += Other.weight; 333} 334 335std::ostream& llvm::operator<<(std::ostream& os, const LiveRange &LR) { 336 return os << '[' << LR.start << ',' << LR.end << ':' << LR.ValId << ")"; 337} 338 339void LiveRange::dump() const { 340 std::cerr << *this << "\n"; 341} 342 343 344std::ostream& llvm::operator<<(std::ostream& os, const LiveInterval& li) { 345 os << "%reg" << li.reg << ',' << li.weight; 346 if (li.empty()) 347 return os << "EMPTY"; 348 349 os << " = "; 350 for (LiveInterval::Ranges::const_iterator i = li.ranges.begin(), 351 e = li.ranges.end(); i != e; ++i) 352 os << *i; 353 return os; 354} 355 356void LiveInterval::dump() const { 357 std::cerr << *this << "\n"; 358} 359