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