LiveInterval.cpp revision c114b2cad7293d98686d380273085f5c32966b52
1fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner//===-- LiveInterval.cpp - Live Interval Representation -------------------===// 2fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 3fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// The LLVM Compiler Infrastructure 4fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 5fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// This file was developed by the LLVM research group and is distributed under 6fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// the University of Illinois Open Source License. See LICENSE.TXT for details. 7fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 8fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner//===----------------------------------------------------------------------===// 9fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 10fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// This file implements the LiveRange and LiveInterval classes. Given some 11fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// numbering of each the machine instructions an interval [i, j) is said to be a 12fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// live interval for register v if there is no instruction with number j' > j 13fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// such that v is live at j' abd there is no instruction with number i' < i such 14fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// that v is live at i'. In this implementation intervals can have holes, 15fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// i.e. an interval might look like [1,20), [50,65), [1000,1001). Each 16fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// individual range is represented as an instance of LiveRange, and the whole 17fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// interval is represented as an instance of LiveInterval. 18fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 19fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner//===----------------------------------------------------------------------===// 20fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 213c3fe462f7978b429ecdd71750c26be25c3d1335Chris Lattner#include "llvm/CodeGen/LiveInterval.h" 22551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/STLExtras.h" 2338135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner#include "llvm/Target/MRegisterInfo.h" 24c4d3b918165461bc6f5d395bca8d9d9d8a84413dAlkis Evlogimenos#include <algorithm> 25abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner#include <iostream> 26abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner#include <map> 27fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattnerusing namespace llvm; 28fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 29fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// An example for liveAt(): 30fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 31aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner// this = [1,4), liveAt(0) will return false. The instruction defining this 32aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner// spans slots [0,3]. The interval belongs to an spilled definition of the 33aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner// variable it represents. This is because slot 1 is used (def slot) and spans 34aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner// up to slot 3 (store slot). 35fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 36ebd7e6c54dce754a88d8f38df4ac2f388f35435eChris Lattnerbool LiveInterval::liveAt(unsigned I) const { 37ebd7e6c54dce754a88d8f38df4ac2f388f35435eChris Lattner Ranges::const_iterator r = std::upper_bound(ranges.begin(), ranges.end(), I); 38edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman 39fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (r == ranges.begin()) 40fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return false; 41fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 42fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner --r; 43aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner return r->contains(I); 44fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 45fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 46bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner// overlaps - Return true if the intersection of the two live intervals is 47bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner// not empty. 48bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner// 49fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// An example for overlaps(): 50fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 51fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 0: A = ... 52fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 4: B = ... 53fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 8: C = A + B ;; last use of A 54fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 55fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// The live intervals should look like: 56fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 57fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// A = [3, 11) 58fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// B = [7, x) 59fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// C = [11, y) 60fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 61fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// A->overlaps(C) should return false since we want to be able to join 62fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// A and C. 63bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner// 64bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattnerbool LiveInterval::overlapsFrom(const LiveInterval& other, 65bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner const_iterator StartPos) const { 66bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner const_iterator i = begin(); 67bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner const_iterator ie = end(); 68bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner const_iterator j = StartPos; 69bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner const_iterator je = other.end(); 70bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner 71bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner assert((StartPos->start <= i->start || StartPos == other.begin()) && 728c68b6a226ce46b35eafda972e04bf53128c2615Chris Lattner StartPos != other.end() && "Bogus start position hint!"); 73f542649f1b374b1bae845e4e4f6d1e82f90a9e31Chris Lattner 74fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (i->start < j->start) { 75aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner i = std::upper_bound(i, ie, j->start); 76fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (i != ranges.begin()) --i; 77aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner } else if (j->start < i->start) { 78ead1b3f0bb70cd9c1ba7a853a79070cb47db9344Chris Lattner ++StartPos; 79ead1b3f0bb70cd9c1ba7a853a79070cb47db9344Chris Lattner if (StartPos != other.end() && StartPos->start <= i->start) { 80ead1b3f0bb70cd9c1ba7a853a79070cb47db9344Chris Lattner assert(StartPos < other.end() && i < end()); 818c68b6a226ce46b35eafda972e04bf53128c2615Chris Lattner j = std::upper_bound(j, je, i->start); 828c68b6a226ce46b35eafda972e04bf53128c2615Chris Lattner if (j != other.ranges.begin()) --j; 838c68b6a226ce46b35eafda972e04bf53128c2615Chris Lattner } 84aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner } else { 85aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner return true; 86fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 87fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 889fddc12c9b16a5526b0ee2e6f1da252f7974d7d0Chris Lattner if (j == je) return false; 899fddc12c9b16a5526b0ee2e6f1da252f7974d7d0Chris Lattner 909fddc12c9b16a5526b0ee2e6f1da252f7974d7d0Chris Lattner while (i != ie) { 91fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (i->start > j->start) { 92a1613db62fec94845aa8306232fb665273615badAlkis Evlogimenos std::swap(i, j); 93a1613db62fec94845aa8306232fb665273615badAlkis Evlogimenos std::swap(ie, je); 94fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 95fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 96fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (i->end > j->start) 97fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return true; 98fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner ++i; 99fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 100fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 101fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return false; 102fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 103fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 104f5ce2678f63f5776fddcfc34ae63ecdec622938cChris Lattner/// NontrivialOverlap - Check to see if the two live ranges specified by i and j 105f5ce2678f63f5776fddcfc34ae63ecdec622938cChris Lattner/// overlap. If so, check to see if they have value numbers that are not 106f5ce2678f63f5776fddcfc34ae63ecdec622938cChris Lattner/// iIdx/jIdx respectively. If both conditions are true, return true. 107b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattnerstatic inline bool NontrivialOverlap(const LiveRange &I, const LiveRange &J, 108f5ce2678f63f5776fddcfc34ae63ecdec622938cChris Lattner unsigned iIdx, unsigned jIdx) { 109b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner if (I.start == J.start) { 110f5ce2678f63f5776fddcfc34ae63ecdec622938cChris Lattner // If this is not the allowed value merge, we cannot join. 111b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner if (I.ValId != iIdx || J.ValId != jIdx) 112f5ce2678f63f5776fddcfc34ae63ecdec622938cChris Lattner return true; 113b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner } else if (I.start < J.start) { 1148317e12cef9b16b948231a20f02b4dd4c3623dfcChris Lattner if (I.end > J.start && (I.ValId != iIdx || J.ValId != jIdx)) { 115f5ce2678f63f5776fddcfc34ae63ecdec622938cChris Lattner return true; 116f5ce2678f63f5776fddcfc34ae63ecdec622938cChris Lattner } 117f5ce2678f63f5776fddcfc34ae63ecdec622938cChris Lattner } else { 1188317e12cef9b16b948231a20f02b4dd4c3623dfcChris Lattner if (J.end > I.start && (I.ValId != iIdx || J.ValId != jIdx)) 119f5ce2678f63f5776fddcfc34ae63ecdec622938cChris Lattner return true; 120f5ce2678f63f5776fddcfc34ae63ecdec622938cChris Lattner } 121f5ce2678f63f5776fddcfc34ae63ecdec622938cChris Lattner 122f5ce2678f63f5776fddcfc34ae63ecdec622938cChris Lattner return false; 123f5ce2678f63f5776fddcfc34ae63ecdec622938cChris Lattner} 124f5ce2678f63f5776fddcfc34ae63ecdec622938cChris Lattner 125abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner/// joinable - Two intervals are joinable if the either don't overlap at all 126abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner/// or if the destination of the copy is a single assignment value, and it 127abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner/// only overlaps with one value in the source interval. 128abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattnerbool LiveInterval::joinable(const LiveInterval &other, unsigned CopyIdx) const { 129f542649f1b374b1bae845e4e4f6d1e82f90a9e31Chris Lattner const LiveRange *SourceLR = other.getLiveRangeContaining(CopyIdx-1); 130f542649f1b374b1bae845e4e4f6d1e82f90a9e31Chris Lattner const LiveRange *DestLR = getLiveRangeContaining(CopyIdx); 131f542649f1b374b1bae845e4e4f6d1e82f90a9e31Chris Lattner assert(SourceLR && DestLR && "Not joining due to a copy?"); 132f542649f1b374b1bae845e4e4f6d1e82f90a9e31Chris Lattner unsigned OtherValIdx = SourceLR->ValId; 133f542649f1b374b1bae845e4e4f6d1e82f90a9e31Chris Lattner unsigned ThisValIdx = DestLR->ValId; 134f542649f1b374b1bae845e4e4f6d1e82f90a9e31Chris Lattner 135f542649f1b374b1bae845e4e4f6d1e82f90a9e31Chris Lattner Ranges::const_iterator i = ranges.begin(); 136f542649f1b374b1bae845e4e4f6d1e82f90a9e31Chris Lattner Ranges::const_iterator ie = ranges.end(); 137f542649f1b374b1bae845e4e4f6d1e82f90a9e31Chris Lattner Ranges::const_iterator j = other.ranges.begin(); 138f542649f1b374b1bae845e4e4f6d1e82f90a9e31Chris Lattner Ranges::const_iterator je = other.ranges.end(); 139f542649f1b374b1bae845e4e4f6d1e82f90a9e31Chris Lattner 140f542649f1b374b1bae845e4e4f6d1e82f90a9e31Chris Lattner if (i->start < j->start) { 141f542649f1b374b1bae845e4e4f6d1e82f90a9e31Chris Lattner i = std::upper_bound(i, ie, j->start); 142f542649f1b374b1bae845e4e4f6d1e82f90a9e31Chris Lattner if (i != ranges.begin()) --i; 143f542649f1b374b1bae845e4e4f6d1e82f90a9e31Chris Lattner } else if (j->start < i->start) { 144f542649f1b374b1bae845e4e4f6d1e82f90a9e31Chris Lattner j = std::upper_bound(j, je, i->start); 145f542649f1b374b1bae845e4e4f6d1e82f90a9e31Chris Lattner if (j != other.ranges.begin()) --j; 146f542649f1b374b1bae845e4e4f6d1e82f90a9e31Chris Lattner } 147f542649f1b374b1bae845e4e4f6d1e82f90a9e31Chris Lattner 148f542649f1b374b1bae845e4e4f6d1e82f90a9e31Chris Lattner while (i != ie && j != je) { 149b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner if (NontrivialOverlap(*i, *j, ThisValIdx, OtherValIdx)) 150f5ce2678f63f5776fddcfc34ae63ecdec622938cChris Lattner return false; 151f5ce2678f63f5776fddcfc34ae63ecdec622938cChris Lattner 152f542649f1b374b1bae845e4e4f6d1e82f90a9e31Chris Lattner if (i->end < j->end) 153f542649f1b374b1bae845e4e4f6d1e82f90a9e31Chris Lattner ++i; 154f542649f1b374b1bae845e4e4f6d1e82f90a9e31Chris Lattner else 155f542649f1b374b1bae845e4e4f6d1e82f90a9e31Chris Lattner ++j; 156f542649f1b374b1bae845e4e4f6d1e82f90a9e31Chris Lattner } 157f542649f1b374b1bae845e4e4f6d1e82f90a9e31Chris Lattner 158c25b55a5b237772bbd7cc55988d3ca0ec569aedeChris Lattner return true; 159abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner} 160abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 161b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner/// getOverlapingRanges - Given another live interval which is defined as a 162b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner/// copy from this one, return a list of all of the live ranges where the 163b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner/// two overlap and have different value numbers. 164b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattnervoid LiveInterval::getOverlapingRanges(const LiveInterval &other, 165b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner unsigned CopyIdx, 166b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner std::vector<LiveRange*> &Ranges) { 1679e20d352c2fec5731857313014107a586387d242Chris Lattner const LiveRange *SourceLR = getLiveRangeContaining(CopyIdx-1); 1689e20d352c2fec5731857313014107a586387d242Chris Lattner const LiveRange *DestLR = other.getLiveRangeContaining(CopyIdx); 169b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner assert(SourceLR && DestLR && "Not joining due to a copy?"); 170b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner unsigned OtherValIdx = SourceLR->ValId; 171b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner unsigned ThisValIdx = DestLR->ValId; 172b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner 173b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner Ranges::iterator i = ranges.begin(); 174b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner Ranges::iterator ie = ranges.end(); 175b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner Ranges::const_iterator j = other.ranges.begin(); 176b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner Ranges::const_iterator je = other.ranges.end(); 177b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner 178b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner if (i->start < j->start) { 179b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner i = std::upper_bound(i, ie, j->start); 180b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner if (i != ranges.begin()) --i; 181b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner } else if (j->start < i->start) { 182b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner j = std::upper_bound(j, je, i->start); 183b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner if (j != other.ranges.begin()) --j; 184b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner } 185b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner 186b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner while (i != ie && j != je) { 187b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner if (NontrivialOverlap(*i, *j, ThisValIdx, OtherValIdx)) 188b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner Ranges.push_back(&*i); 189b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner 190b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner if (i->end < j->end) 191b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner ++i; 192b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner else 193b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner ++j; 194b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner } 195b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner} 196b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner 197b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner 198abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 199b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// extendIntervalEndTo - This method is used when we want to extend the range 200b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// specified by I to end at the specified endpoint. To do this, we should 201b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// merge and eliminate all ranges that this will overlap with. The iterator is 202b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// not invalidated. 203b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattnervoid LiveInterval::extendIntervalEndTo(Ranges::iterator I, unsigned NewEnd) { 204b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner assert(I != ranges.end() && "Not a valid interval!"); 205abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner unsigned ValId = I->ValId; 206b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 207b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // Search for the first interval that we can't merge with. 208b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner Ranges::iterator MergeTo = next(I); 209abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner for (; MergeTo != ranges.end() && NewEnd >= MergeTo->end; ++MergeTo) { 210abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner assert(MergeTo->ValId == ValId && "Cannot merge with differing values!"); 211abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 212b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 213b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // If NewEnd was in the middle of an interval, make sure to get its endpoint. 214b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner I->end = std::max(NewEnd, prior(MergeTo)->end); 215b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 216b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner // Erase any dead ranges. 217b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner ranges.erase(next(I), MergeTo); 218b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner 219b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner // If the newly formed range now touches the range after it and if they have 220b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner // the same value number, merge the two ranges into one range. 221cef6010c64bc56fa2a8f1e7e9e28b8821adeceacChris Lattner Ranges::iterator Next = next(I); 2229e20d352c2fec5731857313014107a586387d242Chris Lattner if (Next != ranges.end() && Next->start <= I->end && Next->ValId == ValId) { 223cef6010c64bc56fa2a8f1e7e9e28b8821adeceacChris Lattner I->end = Next->end; 224cef6010c64bc56fa2a8f1e7e9e28b8821adeceacChris Lattner ranges.erase(Next); 225b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner } 226fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 227fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 228fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 229b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// extendIntervalStartTo - This method is used when we want to extend the range 230b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// specified by I to start at the specified endpoint. To do this, we should 231b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// merge and eliminate all ranges that this will overlap with. 232edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha BrukmanLiveInterval::Ranges::iterator 233b26c215c059d4674bd6a9a8b94da86e497e64844Chris LattnerLiveInterval::extendIntervalStartTo(Ranges::iterator I, unsigned NewStart) { 234b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner assert(I != ranges.end() && "Not a valid interval!"); 235abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner unsigned ValId = I->ValId; 236b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 237b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // Search for the first interval that we can't merge with. 238b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner Ranges::iterator MergeTo = I; 239b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner do { 240b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner if (MergeTo == ranges.begin()) { 241b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner I->start = NewStart; 242abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner ranges.erase(MergeTo, I); 243b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner return I; 244b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner } 245abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner assert(MergeTo->ValId == ValId && "Cannot merge with differing values!"); 246b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner --MergeTo; 247b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner } while (NewStart <= MergeTo->start); 248b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 249b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // If we start in the middle of another interval, just delete a range and 250b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // extend that interval. 251abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (MergeTo->end >= NewStart && MergeTo->ValId == ValId) { 252b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner MergeTo->end = I->end; 253b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner } else { 254b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // Otherwise, extend the interval right after. 255b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner ++MergeTo; 256b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner MergeTo->start = NewStart; 257b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner MergeTo->end = I->end; 258fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 259b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 260b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner ranges.erase(next(MergeTo), next(I)); 261b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner return MergeTo; 262fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 263fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 264c114b2cad7293d98686d380273085f5c32966b52Chris LattnerLiveInterval::iterator 265c114b2cad7293d98686d380273085f5c32966b52Chris LattnerLiveInterval::addRangeFrom(LiveRange LR, iterator From) { 266b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner unsigned Start = LR.start, End = LR.end; 267c114b2cad7293d98686d380273085f5c32966b52Chris Lattner iterator it = std::upper_bound(From, ranges.end(), Start); 268b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 269b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // If the inserted interval starts in the middle or right at the end of 270b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // another interval, just extend that interval to contain the range of LR. 271b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner if (it != ranges.begin()) { 272c114b2cad7293d98686d380273085f5c32966b52Chris Lattner iterator B = prior(it); 273abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (LR.ValId == B->ValId) { 274abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (B->start <= Start && B->end >= Start) { 275abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner extendIntervalEndTo(B, End); 276abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner return B; 277abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 278abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } else { 279abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // Check to make sure that we are not overlapping two live ranges with 280abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // different ValId's. 281abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner assert(B->end <= Start && 2828311befb6968a581a3abdce1e13b5d63922662f7Brian Gaeke "Cannot overlap two LiveRanges with differing ValID's" 2838311befb6968a581a3abdce1e13b5d63922662f7Brian Gaeke " (did you def the same reg twice in a MachineInstr?)"); 284b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner } 285fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 286b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 287b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // Otherwise, if this range ends in the middle of, or right next to, another 288b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // interval, merge it into that interval. 289abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (it != ranges.end()) 290abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (LR.ValId == it->ValId) { 291abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (it->start <= End) { 292abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner it = extendIntervalStartTo(it, Start); 293abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 294abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // If LR is a complete superset of an interval, we may need to grow its 295abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // endpoint as well. 296abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (End > it->end) 297abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner extendIntervalEndTo(it, End); 298abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner return it; 299abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 300abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } else { 301abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // Check to make sure that we are not overlapping two live ranges with 302abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // different ValId's. 303abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner assert(it->start >= End && 304abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner "Cannot overlap two LiveRanges with differing ValID's"); 305abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 306b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 307b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // Otherwise, this is just a new range that doesn't interact with anything. 308b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // Insert it. 309b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner return ranges.insert(it, LR); 310fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 311fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 312abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 313abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner/// removeRange - Remove the specified range from this interval. Note that 314abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner/// the range must already be in this interval in its entirety. 315abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattnervoid LiveInterval::removeRange(unsigned Start, unsigned End) { 316abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // Find the LiveRange containing this span. 317abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner Ranges::iterator I = std::upper_bound(ranges.begin(), ranges.end(), Start); 318abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner assert(I != ranges.begin() && "Range is not in interval!"); 319abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner --I; 320abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner assert(I->contains(Start) && I->contains(End-1) && 321abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner "Range is not entirely in interval!"); 322abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 323abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // If the span we are removing is at the start of the LiveRange, adjust it. 324abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (I->start == Start) { 325abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (I->end == End) 326abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner ranges.erase(I); // Removed the whole LiveRange. 327abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner else 328abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner I->start = End; 329abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner return; 330abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 331abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 332abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // Otherwise if the span we are removing is at the end of the LiveRange, 333abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // adjust the other way. 334abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (I->end == End) { 3356925a9f9cc0b9d34cfbc19d9208c416e293ca516Chris Lattner I->end = Start; 336abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner return; 337abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 338abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 339abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // Otherwise, we are splitting the LiveRange into two pieces. 340abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner unsigned OldEnd = I->end; 341abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner I->end = Start; // Trim the old interval. 342abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 343abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // Insert the new one. 344abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner ranges.insert(next(I), LiveRange(End, OldEnd, I->ValId)); 345abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner} 346abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 347abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner/// getLiveRangeContaining - Return the live range that contains the 348abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner/// specified index, or null if there is none. 349f7da2c7b0c6293c268881628fc351bed7763f1f4Chris LattnerLiveInterval::const_iterator 350f7da2c7b0c6293c268881628fc351bed7763f1f4Chris LattnerLiveInterval::FindLiveRangeContaining(unsigned Idx) const { 351f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner const_iterator It = std::upper_bound(begin(), end(), Idx); 352abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (It != ranges.begin()) { 353f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner --It; 354f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner if (It->contains(Idx)) 355f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner return It; 356abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 357abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 358f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner return end(); 359abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner} 360abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 361f7da2c7b0c6293c268881628fc351bed7763f1f4Chris LattnerLiveInterval::iterator 362f7da2c7b0c6293c268881628fc351bed7763f1f4Chris LattnerLiveInterval::FindLiveRangeContaining(unsigned Idx) { 363f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner iterator It = std::upper_bound(begin(), end(), Idx); 364f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner if (It != ranges.begin()) { 365f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner --It; 366f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner if (It->contains(Idx)) 367f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner return It; 368f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 369f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 370f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner return end(); 371f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner} 372abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 373abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner/// join - Join two live intervals (this, and other) together. This operation 374abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner/// is the result of a copy instruction in the source program, that occurs at 375abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner/// index 'CopyIdx' that copies from 'Other' to 'this'. 376abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattnervoid LiveInterval::join(LiveInterval &Other, unsigned CopyIdx) { 377d3a205eab5761298ccfb320834b5f0ea0184ab27Chris Lattner const LiveRange *SourceLR = Other.getLiveRangeContaining(CopyIdx-1); 378d3a205eab5761298ccfb320834b5f0ea0184ab27Chris Lattner const LiveRange *DestLR = getLiveRangeContaining(CopyIdx); 379abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner assert(SourceLR && DestLR && "Not joining due to a copy?"); 380abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner unsigned MergedSrcValIdx = SourceLR->ValId; 381abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner unsigned MergedDstValIdx = DestLR->ValId; 382fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 383deb9971061cfb9c57930724fcf8d62fb26dc2213Chris Lattner // Try to do the least amount of work possible. In particular, if there are 384deb9971061cfb9c57930724fcf8d62fb26dc2213Chris Lattner // more liverange chunks in the other set than there are in the 'this' set, 385deb9971061cfb9c57930724fcf8d62fb26dc2213Chris Lattner // swap sets to merge the fewest chunks in possible. 386deb9971061cfb9c57930724fcf8d62fb26dc2213Chris Lattner if (Other.ranges.size() > ranges.size()) { 387deb9971061cfb9c57930724fcf8d62fb26dc2213Chris Lattner std::swap(MergedSrcValIdx, MergedDstValIdx); 388deb9971061cfb9c57930724fcf8d62fb26dc2213Chris Lattner std::swap(ranges, Other.ranges); 389deb9971061cfb9c57930724fcf8d62fb26dc2213Chris Lattner std::swap(NumValues, Other.NumValues); 390f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner std::swap(InstDefiningValue, Other.InstDefiningValue); 391deb9971061cfb9c57930724fcf8d62fb26dc2213Chris Lattner } 392deb9971061cfb9c57930724fcf8d62fb26dc2213Chris Lattner 393b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // Join the ranges of other into the ranges of this interval. 394abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner std::map<unsigned, unsigned> Dst2SrcIdxMap; 395c114b2cad7293d98686d380273085f5c32966b52Chris Lattner iterator InsertPos = begin(); 396c114b2cad7293d98686d380273085f5c32966b52Chris Lattner for (iterator I = Other.begin(), E = Other.end(); I != E; ++I) { 397abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // Map the ValId in the other live range to the current live range. 398abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (I->ValId == MergedSrcValIdx) 399abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner I->ValId = MergedDstValIdx; 400abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner else { 401abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner unsigned &NV = Dst2SrcIdxMap[I->ValId]; 402be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner if (NV == 0) NV = getNextValue(Other.getInstForValNum(I->ValId)); 403abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner I->ValId = NV; 404abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 405b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 406abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner InsertPos = addRangeFrom(*I, InsertPos); 407abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 408f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 409f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Update the value number information for the value number defined by the 410f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // copy. The copy is about to be removed, so ensure that the value is defined 411f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // by whatever the other value is defined by. 412f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner if (InstDefiningValue[MergedDstValIdx] == CopyIdx) { 413f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner InstDefiningValue[MergedDstValIdx] = 414f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner Other.InstDefiningValue[MergedSrcValIdx]; 415f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 416f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 417abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner weight += Other.weight; 418fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 419fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 420c114b2cad7293d98686d380273085f5c32966b52Chris Lattner/// MergeInClobberRanges - For any live ranges that are not defined in the 421c114b2cad7293d98686d380273085f5c32966b52Chris Lattner/// current interval, but are defined in the Clobbers interval, mark them 422c114b2cad7293d98686d380273085f5c32966b52Chris Lattner/// used with an unknown definition value. 423c114b2cad7293d98686d380273085f5c32966b52Chris Lattnervoid LiveInterval::MergeInClobberRanges(const LiveInterval &Clobbers) { 424c114b2cad7293d98686d380273085f5c32966b52Chris Lattner if (Clobbers.begin() == Clobbers.end()) return; 425c114b2cad7293d98686d380273085f5c32966b52Chris Lattner 426c114b2cad7293d98686d380273085f5c32966b52Chris Lattner // Find a value # to use for the clobber ranges. If there is already a value# 427c114b2cad7293d98686d380273085f5c32966b52Chris Lattner // for unknown values, use it. 428c114b2cad7293d98686d380273085f5c32966b52Chris Lattner // FIXME: Use a single sentinal number for these! 429c114b2cad7293d98686d380273085f5c32966b52Chris Lattner unsigned ClobberValNo = getNextValue(~0U); 430c114b2cad7293d98686d380273085f5c32966b52Chris Lattner 431c114b2cad7293d98686d380273085f5c32966b52Chris Lattner iterator IP = begin(); 432c114b2cad7293d98686d380273085f5c32966b52Chris Lattner for (const_iterator I = Clobbers.begin(), E = Clobbers.end(); I != E; ++I) { 433c114b2cad7293d98686d380273085f5c32966b52Chris Lattner unsigned Start = I->start, End = I->end; 434c114b2cad7293d98686d380273085f5c32966b52Chris Lattner IP = std::upper_bound(IP, end(), Start); 435c114b2cad7293d98686d380273085f5c32966b52Chris Lattner 436c114b2cad7293d98686d380273085f5c32966b52Chris Lattner // If the start of this range overlaps with an existing liverange, trim it. 437c114b2cad7293d98686d380273085f5c32966b52Chris Lattner if (IP != begin() && IP[-1].end > Start) { 438c114b2cad7293d98686d380273085f5c32966b52Chris Lattner Start = IP[-1].end; 439c114b2cad7293d98686d380273085f5c32966b52Chris Lattner // Trimmed away the whole range? 440c114b2cad7293d98686d380273085f5c32966b52Chris Lattner if (Start >= End) continue; 441c114b2cad7293d98686d380273085f5c32966b52Chris Lattner } 442c114b2cad7293d98686d380273085f5c32966b52Chris Lattner // If the end of this range overlaps with an existing liverange, trim it. 443c114b2cad7293d98686d380273085f5c32966b52Chris Lattner if (IP != end() && End > IP->start) { 444c114b2cad7293d98686d380273085f5c32966b52Chris Lattner End = IP->start; 445c114b2cad7293d98686d380273085f5c32966b52Chris Lattner // If this trimmed away the whole range, ignore it. 446c114b2cad7293d98686d380273085f5c32966b52Chris Lattner if (Start == End) continue; 447c114b2cad7293d98686d380273085f5c32966b52Chris Lattner } 448c114b2cad7293d98686d380273085f5c32966b52Chris Lattner 449c114b2cad7293d98686d380273085f5c32966b52Chris Lattner // Insert the clobber interval. 450c114b2cad7293d98686d380273085f5c32966b52Chris Lattner IP = addRangeFrom(LiveRange(Start, End, ClobberValNo), IP); 451c114b2cad7293d98686d380273085f5c32966b52Chris Lattner } 452c114b2cad7293d98686d380273085f5c32966b52Chris Lattner} 453c114b2cad7293d98686d380273085f5c32966b52Chris Lattner 454f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// MergeValueNumberInto - This method is called when two value nubmers 455f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// are found to be equivalent. This eliminates V1, replacing all 456f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// LiveRanges with the V1 value number with the V2 value number. This can 457f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// cause merging of V1/V2 values numbers and compaction of the value space. 458f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveInterval::MergeValueNumberInto(unsigned V1, unsigned V2) { 459f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner assert(V1 != V2 && "Identical value#'s are always equivalent!"); 460f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 461f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // This code actually merges the (numerically) larger value number into the 462f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // smaller value number, which is likely to allow us to compactify the value 463f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // space. The only thing we have to be careful of is to preserve the 464f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // instruction that defines the result value. 465f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 466f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Make sure V2 is smaller than V1. 467f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner if (V1 < V2) { 468f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner setInstDefiningValNum(V1, getInstForValNum(V2)); 469f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner std::swap(V1, V2); 470f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 471f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 472f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Merge V1 live ranges into V2. 473f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner for (iterator I = begin(); I != end(); ) { 474f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner iterator LR = I++; 475f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner if (LR->ValId != V1) continue; // Not a V1 LiveRange. 476f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 477f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Okay, we found a V1 live range. If it had a previous, touching, V2 live 478f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // range, extend it. 479f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner if (LR != begin()) { 480f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner iterator Prev = LR-1; 481f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner if (Prev->ValId == V2 && Prev->end == LR->start) { 482f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner Prev->end = LR->end; 483f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 484f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Erase this live-range. 485f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner ranges.erase(LR); 486f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner I = Prev+1; 487f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner LR = Prev; 488f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 489f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 490f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 491f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Okay, now we have a V1 or V2 live range that is maximally merged forward. 492f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Ensure that it is a V2 live-range. 493f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner LR->ValId = V2; 494f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 495f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // If we can merge it into later V2 live ranges, do so now. We ignore any 496f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // following V1 live ranges, as they will be merged in subsequent iterations 497f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // of the loop. 498f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner if (I != end()) { 499f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner if (I->start == LR->end && I->ValId == V2) { 500f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner LR->end = I->end; 501f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner ranges.erase(I); 502f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner I = LR+1; 503f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 504f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 505f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 506c82b3aab6502a9766ddf42b45faeca3d6fa0ad65Chris Lattner 507c82b3aab6502a9766ddf42b45faeca3d6fa0ad65Chris Lattner // Now that V1 is dead, remove it. If it is the largest value number, just 508c82b3aab6502a9766ddf42b45faeca3d6fa0ad65Chris Lattner // nuke it (and any other deleted values neighboring it), otherwise mark it as 509c82b3aab6502a9766ddf42b45faeca3d6fa0ad65Chris Lattner // ~1U so it can be nuked later. 510c82b3aab6502a9766ddf42b45faeca3d6fa0ad65Chris Lattner if (V1 == NumValues-1) { 511c82b3aab6502a9766ddf42b45faeca3d6fa0ad65Chris Lattner do { 512c82b3aab6502a9766ddf42b45faeca3d6fa0ad65Chris Lattner InstDefiningValue.pop_back(); 513c82b3aab6502a9766ddf42b45faeca3d6fa0ad65Chris Lattner --NumValues; 514c82b3aab6502a9766ddf42b45faeca3d6fa0ad65Chris Lattner } while (InstDefiningValue.back() == ~1U); 515c82b3aab6502a9766ddf42b45faeca3d6fa0ad65Chris Lattner } else { 516c82b3aab6502a9766ddf42b45faeca3d6fa0ad65Chris Lattner InstDefiningValue[V1] = ~1U; 517c82b3aab6502a9766ddf42b45faeca3d6fa0ad65Chris Lattner } 518f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner} 519f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 520f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 521fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattnerstd::ostream& llvm::operator<<(std::ostream& os, const LiveRange &LR) { 522abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner return os << '[' << LR.start << ',' << LR.end << ':' << LR.ValId << ")"; 523abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner} 524abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 525abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattnervoid LiveRange::dump() const { 526abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner std::cerr << *this << "\n"; 527fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 528fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 52938135af219c48a8626d6af34a92e7e8bb957c81fChris Lattnervoid LiveInterval::print(std::ostream &OS, const MRegisterInfo *MRI) const { 53038135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner if (MRI && MRegisterInfo::isPhysicalRegister(reg)) 53138135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner OS << MRI->getName(reg); 53238135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner else 53338135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner OS << "%reg" << reg; 53438135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner 53538135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner OS << ',' << weight; 53638135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner 53738135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner if (empty()) 53838135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner OS << "EMPTY"; 53938135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner else { 54038135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner OS << " = "; 54138135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner for (LiveInterval::Ranges::const_iterator I = ranges.begin(), 54238135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner E = ranges.end(); I != E; ++I) 54338135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner OS << *I; 54438135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner } 545be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner 546be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Print value number info. 547be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner if (NumValues) { 548be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner OS << " "; 549be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner for (unsigned i = 0; i != NumValues; ++i) { 550be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner if (i) OS << " "; 551be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner OS << i << "@"; 552be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner if (InstDefiningValue[i] == ~0U) { 553be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner OS << "?"; 554be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner } else { 555be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner OS << InstDefiningValue[i]; 556be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner } 557be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner } 558be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner } 559fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 560abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 561abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattnervoid LiveInterval::dump() const { 562abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner std::cerr << *this << "\n"; 563abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner} 564