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