LiveInterval.cpp revision 3c3fe462f7978b429ecdd71750c26be25c3d1335
18c888b10fdd2846885e8582b131fa076ce1b77b1Jordan Rose//===-- LiveInterval.cpp - Live Interval Representation -------------------===// 28c888b10fdd2846885e8582b131fa076ce1b77b1Jordan Rose// 38c888b10fdd2846885e8582b131fa076ce1b77b1Jordan Rose// The LLVM Compiler Infrastructure 48c888b10fdd2846885e8582b131fa076ce1b77b1Jordan Rose// 58c888b10fdd2846885e8582b131fa076ce1b77b1Jordan Rose// This file was developed by the LLVM research group and is distributed under 6eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks// the University of Illinois Open Source License. See LICENSE.TXT for details. 7eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks// 8262e0d41e49c6b823d62743535e2accb117a6ea9Jordan Rose//===----------------------------------------------------------------------===// 9262e0d41e49c6b823d62743535e2accb117a6ea9Jordan Rose// 10262e0d41e49c6b823d62743535e2accb117a6ea9Jordan Rose// This file implements the LiveRange and LiveInterval classes. Given some 11262e0d41e49c6b823d62743535e2accb117a6ea9Jordan Rose// numbering of each the machine instructions an interval [i, j) is said to be a 12eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks// live interval for register v if there is no instruction with number j' > j 13eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks// such that v is live at j' abd there is no instruction with number i' < i such 14ca23eb212c78ac5bc62d0881635579dbe7095639Anna Zaks// that v is live at i'. In this implementation intervals can have holes, 15ca23eb212c78ac5bc62d0881635579dbe7095639Anna Zaks// i.e. an interval might look like [1,20), [50,65), [1000,1001). Each 16ca23eb212c78ac5bc62d0881635579dbe7095639Anna Zaks// individual range is represented as an instance of LiveRange, and the whole 17ca23eb212c78ac5bc62d0881635579dbe7095639Anna Zaks// interval is represented as an instance of LiveInterval. 18ca23eb212c78ac5bc62d0881635579dbe7095639Anna Zaks// 19ca23eb212c78ac5bc62d0881635579dbe7095639Anna Zaks//===----------------------------------------------------------------------===// 20ca23eb212c78ac5bc62d0881635579dbe7095639Anna Zaks 219a0b3c2f7c440c53b65bd1b085a7471d9f7ed490Jordan Rose#include "llvm/CodeGen/LiveInterval.h" 22ca23eb212c78ac5bc62d0881635579dbe7095639Anna Zaks#include "llvm/ADT/STLExtras.h" 239a0b3c2f7c440c53b65bd1b085a7471d9f7ed490Jordan Rose#include "llvm/Target/MRegisterInfo.h" 249a0b3c2f7c440c53b65bd1b085a7471d9f7ed490Jordan Rose#include <algorithm> 259a0b3c2f7c440c53b65bd1b085a7471d9f7ed490Jordan Rose#include <iostream> 26eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks#include <map> 27eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaksusing namespace llvm; 28eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks 29eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks// An example for liveAt(): 309620aa8c6726330c0357799706aa51f64cc449daNAKAMURA Takumi// 319620aa8c6726330c0357799706aa51f64cc449daNAKAMURA Takumi// this = [1,4), liveAt(0) will return false. The instruction defining this 329620aa8c6726330c0357799706aa51f64cc449daNAKAMURA Takumi// spans slots [0,3]. The interval belongs to an spilled definition of the 3315d0ae170c2037815b6383c532253585fcd3d04eAnna Zaks// variable it represents. This is because slot 1 is used (def slot) and spans 34ca23eb212c78ac5bc62d0881635579dbe7095639Anna Zaks// up to slot 3 (store slot). 3515d0ae170c2037815b6383c532253585fcd3d04eAnna Zaks// 360d389b819c33bdf0375694a8f141c8f02e002b18Anna Zaksbool LiveInterval::liveAt(unsigned I) const { 370d389b819c33bdf0375694a8f141c8f02e002b18Anna Zaks Ranges::const_iterator r = std::upper_bound(ranges.begin(), ranges.end(), I); 38ca23eb212c78ac5bc62d0881635579dbe7095639Anna Zaks 39ca23eb212c78ac5bc62d0881635579dbe7095639Anna Zaks if (r == ranges.begin()) 40ca23eb212c78ac5bc62d0881635579dbe7095639Anna Zaks return false; 41ca23eb212c78ac5bc62d0881635579dbe7095639Anna Zaks 42ca23eb212c78ac5bc62d0881635579dbe7095639Anna Zaks --r; 43ca23eb212c78ac5bc62d0881635579dbe7095639Anna Zaks return r->contains(I); 44ca23eb212c78ac5bc62d0881635579dbe7095639Anna Zaks} 45ca23eb212c78ac5bc62d0881635579dbe7095639Anna Zaks 46ca23eb212c78ac5bc62d0881635579dbe7095639Anna Zaks// overlaps - Return true if the intersection of the two live intervals is 479a0b3c2f7c440c53b65bd1b085a7471d9f7ed490Jordan Rose// not empty. 489a0b3c2f7c440c53b65bd1b085a7471d9f7ed490Jordan Rose// 49ca23eb212c78ac5bc62d0881635579dbe7095639Anna Zaks// An example for overlaps(): 50ca23eb212c78ac5bc62d0881635579dbe7095639Anna Zaks// 51ca23eb212c78ac5bc62d0881635579dbe7095639Anna Zaks// 0: A = ... 52ca23eb212c78ac5bc62d0881635579dbe7095639Anna Zaks// 4: B = ... 53ca23eb212c78ac5bc62d0881635579dbe7095639Anna Zaks// 8: C = A + B ;; last use of A 54ca23eb212c78ac5bc62d0881635579dbe7095639Anna Zaks// 55aca0ac58d2ae80d764e3832456667d7322445e0cAnna Zaks// The live intervals should look like: 56b79d862af66d8dd9d059863813b9a27d744bd990Anna Zaks// 57b79d862af66d8dd9d059863813b9a27d744bd990Anna Zaks// A = [3, 11) 58b79d862af66d8dd9d059863813b9a27d744bd990Anna Zaks// B = [7, x) 59b79d862af66d8dd9d059863813b9a27d744bd990Anna Zaks// C = [11, y) 60b79d862af66d8dd9d059863813b9a27d744bd990Anna Zaks// 61b79d862af66d8dd9d059863813b9a27d744bd990Anna Zaks// A->overlaps(C) should return false since we want to be able to join 62b79d862af66d8dd9d059863813b9a27d744bd990Anna Zaks// A and C. 63b79d862af66d8dd9d059863813b9a27d744bd990Anna Zaks// 64b79d862af66d8dd9d059863813b9a27d744bd990Anna Zaksbool LiveInterval::overlapsFrom(const LiveInterval& other, 651bf908df57cc43f3bc7296f4e51f5708bd323c6bJordan Rose const_iterator StartPos) const { 661bf908df57cc43f3bc7296f4e51f5708bd323c6bJordan Rose const_iterator i = begin(); 671bf908df57cc43f3bc7296f4e51f5708bd323c6bJordan Rose const_iterator ie = end(); 681bf908df57cc43f3bc7296f4e51f5708bd323c6bJordan Rose const_iterator j = StartPos; 691bf908df57cc43f3bc7296f4e51f5708bd323c6bJordan Rose const_iterator je = other.end(); 701bf908df57cc43f3bc7296f4e51f5708bd323c6bJordan Rose 711bf908df57cc43f3bc7296f4e51f5708bd323c6bJordan Rose assert((StartPos->start <= i->start || StartPos == other.begin()) && 7252a04812e5767dab68efb33ad044760b5b168941Anna Zaks StartPos != other.end() && "Bogus start position hint!"); 7352a04812e5767dab68efb33ad044760b5b168941Anna Zaks 7452a04812e5767dab68efb33ad044760b5b168941Anna Zaks if (i->start < j->start) { 7552a04812e5767dab68efb33ad044760b5b168941Anna Zaks i = std::upper_bound(i, ie, j->start); 7652a04812e5767dab68efb33ad044760b5b168941Anna Zaks if (i != ranges.begin()) --i; 7752a04812e5767dab68efb33ad044760b5b168941Anna Zaks } else if (j->start < i->start) { 7852a04812e5767dab68efb33ad044760b5b168941Anna Zaks ++StartPos; 79233e26acc0ff2a1098f4c813f69286fce840a422Anna Zaks if (StartPos != other.end() && StartPos->start <= i->start) { 80374ae320b87c15b0262c40e5c46e8990111df5caJordan Rose assert(StartPos < other.end() && i < end()); 81233e26acc0ff2a1098f4c813f69286fce840a422Anna Zaks j = std::upper_bound(j, je, i->start); 82374ae320b87c15b0262c40e5c46e8990111df5caJordan Rose if (j != other.ranges.begin()) --j; 83233e26acc0ff2a1098f4c813f69286fce840a422Anna Zaks } 84233e26acc0ff2a1098f4c813f69286fce840a422Anna Zaks } else { 85233e26acc0ff2a1098f4c813f69286fce840a422Anna Zaks return true; 86233e26acc0ff2a1098f4c813f69286fce840a422Anna Zaks } 87233e26acc0ff2a1098f4c813f69286fce840a422Anna Zaks 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