LiveInterval.cpp revision 38b0e7bbf2590f99122a2535d16f34bd12c3bb24
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 21d9fd2acc1f172e4b8c33c3562667102f9af4d28dBill Wendling#include "llvm/CodeGen/LiveInterval.h" 2238b0e7bbf2590f99122a2535d16f34bd12c3bb24Bill Wendling#include "llvm/ADT/STLExtras.h" 23d9fd2acc1f172e4b8c33c3562667102f9af4d28dBill Wendling#include "llvm/Support/Streams.h" 2438135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner#include "llvm/Target/MRegisterInfo.h" 25c4d3b918165461bc6f5d395bca8d9d9d8a84413dAlkis Evlogimenos#include <algorithm> 26abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner#include <iostream> 27abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner#include <map> 28fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattnerusing namespace llvm; 29fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 30fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// An example for liveAt(): 31fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 32aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner// this = [1,4), liveAt(0) will return false. The instruction defining this 33aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner// spans slots [0,3]. The interval belongs to an spilled definition of the 34aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner// variable it represents. This is because slot 1 is used (def slot) and spans 35aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner// up to slot 3 (store slot). 36fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 37ebd7e6c54dce754a88d8f38df4ac2f388f35435eChris Lattnerbool LiveInterval::liveAt(unsigned I) const { 38ebd7e6c54dce754a88d8f38df4ac2f388f35435eChris Lattner Ranges::const_iterator r = std::upper_bound(ranges.begin(), ranges.end(), I); 39edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman 40fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (r == ranges.begin()) 41fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return false; 42fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 43fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner --r; 44aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner return r->contains(I); 45fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 46fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 47bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner// overlaps - Return true if the intersection of the two live intervals is 48bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner// not empty. 49bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner// 50fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// An example for overlaps(): 51fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 52fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 0: A = ... 53fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 4: B = ... 54fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 8: C = A + B ;; last use of A 55fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 56fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// The live intervals should look like: 57fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 58fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// A = [3, 11) 59fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// B = [7, x) 60fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// C = [11, y) 61fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 62fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// A->overlaps(C) should return false since we want to be able to join 63fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// A and C. 64bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner// 65bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattnerbool LiveInterval::overlapsFrom(const LiveInterval& other, 66bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner const_iterator StartPos) const { 67bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner const_iterator i = begin(); 68bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner const_iterator ie = end(); 69bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner const_iterator j = StartPos; 70bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner const_iterator je = other.end(); 71bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner 72bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner assert((StartPos->start <= i->start || StartPos == other.begin()) && 738c68b6a226ce46b35eafda972e04bf53128c2615Chris Lattner StartPos != other.end() && "Bogus start position hint!"); 74f542649f1b374b1bae845e4e4f6d1e82f90a9e31Chris Lattner 75fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (i->start < j->start) { 76aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner i = std::upper_bound(i, ie, j->start); 77fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (i != ranges.begin()) --i; 78aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner } else if (j->start < i->start) { 79ead1b3f0bb70cd9c1ba7a853a79070cb47db9344Chris Lattner ++StartPos; 80ead1b3f0bb70cd9c1ba7a853a79070cb47db9344Chris Lattner if (StartPos != other.end() && StartPos->start <= i->start) { 81ead1b3f0bb70cd9c1ba7a853a79070cb47db9344Chris Lattner assert(StartPos < other.end() && i < end()); 828c68b6a226ce46b35eafda972e04bf53128c2615Chris Lattner j = std::upper_bound(j, je, i->start); 838c68b6a226ce46b35eafda972e04bf53128c2615Chris Lattner if (j != other.ranges.begin()) --j; 848c68b6a226ce46b35eafda972e04bf53128c2615Chris Lattner } 85aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner } else { 86aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner return true; 87fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 88fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 899fddc12c9b16a5526b0ee2e6f1da252f7974d7d0Chris Lattner if (j == je) return false; 909fddc12c9b16a5526b0ee2e6f1da252f7974d7d0Chris Lattner 919fddc12c9b16a5526b0ee2e6f1da252f7974d7d0Chris Lattner while (i != ie) { 92fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (i->start > j->start) { 93a1613db62fec94845aa8306232fb665273615badAlkis Evlogimenos std::swap(i, j); 94a1613db62fec94845aa8306232fb665273615badAlkis Evlogimenos std::swap(ie, je); 95fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 96fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 97fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (i->end > j->start) 98fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return true; 99fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner ++i; 100fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 101fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 102fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return false; 103fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 104fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 105b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// extendIntervalEndTo - This method is used when we want to extend the range 106b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// specified by I to end at the specified endpoint. To do this, we should 107b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// merge and eliminate all ranges that this will overlap with. The iterator is 108b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// not invalidated. 109b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattnervoid LiveInterval::extendIntervalEndTo(Ranges::iterator I, unsigned NewEnd) { 110b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner assert(I != ranges.end() && "Not a valid interval!"); 111abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner unsigned ValId = I->ValId; 112b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 113b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // Search for the first interval that we can't merge with. 114b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner Ranges::iterator MergeTo = next(I); 115abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner for (; MergeTo != ranges.end() && NewEnd >= MergeTo->end; ++MergeTo) { 116abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner assert(MergeTo->ValId == ValId && "Cannot merge with differing values!"); 117abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 118b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 119b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // If NewEnd was in the middle of an interval, make sure to get its endpoint. 120b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner I->end = std::max(NewEnd, prior(MergeTo)->end); 121b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 122b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner // Erase any dead ranges. 123b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner ranges.erase(next(I), MergeTo); 124b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner 125b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner // If the newly formed range now touches the range after it and if they have 126b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner // the same value number, merge the two ranges into one range. 127cef6010c64bc56fa2a8f1e7e9e28b8821adeceacChris Lattner Ranges::iterator Next = next(I); 1289e20d352c2fec5731857313014107a586387d242Chris Lattner if (Next != ranges.end() && Next->start <= I->end && Next->ValId == ValId) { 129cef6010c64bc56fa2a8f1e7e9e28b8821adeceacChris Lattner I->end = Next->end; 130cef6010c64bc56fa2a8f1e7e9e28b8821adeceacChris Lattner ranges.erase(Next); 131b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner } 132fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 133fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 134fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 135b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// extendIntervalStartTo - This method is used when we want to extend the range 136b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// specified by I to start at the specified endpoint. To do this, we should 137b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// merge and eliminate all ranges that this will overlap with. 138edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha BrukmanLiveInterval::Ranges::iterator 139b26c215c059d4674bd6a9a8b94da86e497e64844Chris LattnerLiveInterval::extendIntervalStartTo(Ranges::iterator I, unsigned NewStart) { 140b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner assert(I != ranges.end() && "Not a valid interval!"); 141abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner unsigned ValId = I->ValId; 142b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 143b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // Search for the first interval that we can't merge with. 144b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner Ranges::iterator MergeTo = I; 145b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner do { 146b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner if (MergeTo == ranges.begin()) { 147b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner I->start = NewStart; 148abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner ranges.erase(MergeTo, I); 149b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner return I; 150b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner } 151abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner assert(MergeTo->ValId == ValId && "Cannot merge with differing values!"); 152b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner --MergeTo; 153b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner } while (NewStart <= MergeTo->start); 154b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 155b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // If we start in the middle of another interval, just delete a range and 156b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // extend that interval. 157abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (MergeTo->end >= NewStart && MergeTo->ValId == ValId) { 158b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner MergeTo->end = I->end; 159b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner } else { 160b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // Otherwise, extend the interval right after. 161b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner ++MergeTo; 162b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner MergeTo->start = NewStart; 163b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner MergeTo->end = I->end; 164fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 165b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 166b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner ranges.erase(next(MergeTo), next(I)); 167b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner return MergeTo; 168fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 169fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 170c114b2cad7293d98686d380273085f5c32966b52Chris LattnerLiveInterval::iterator 171c114b2cad7293d98686d380273085f5c32966b52Chris LattnerLiveInterval::addRangeFrom(LiveRange LR, iterator From) { 172b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner unsigned Start = LR.start, End = LR.end; 173c114b2cad7293d98686d380273085f5c32966b52Chris Lattner iterator it = std::upper_bound(From, ranges.end(), Start); 174b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 175b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // If the inserted interval starts in the middle or right at the end of 176b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // another interval, just extend that interval to contain the range of LR. 177b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner if (it != ranges.begin()) { 178c114b2cad7293d98686d380273085f5c32966b52Chris Lattner iterator B = prior(it); 179abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (LR.ValId == B->ValId) { 180abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (B->start <= Start && B->end >= Start) { 181abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner extendIntervalEndTo(B, End); 182abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner return B; 183abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 184abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } else { 185abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // Check to make sure that we are not overlapping two live ranges with 186abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // different ValId's. 187abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner assert(B->end <= Start && 1888311befb6968a581a3abdce1e13b5d63922662f7Brian Gaeke "Cannot overlap two LiveRanges with differing ValID's" 1898311befb6968a581a3abdce1e13b5d63922662f7Brian Gaeke " (did you def the same reg twice in a MachineInstr?)"); 190b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner } 191fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 192b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 193b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // Otherwise, if this range ends in the middle of, or right next to, another 194b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // interval, merge it into that interval. 195abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (it != ranges.end()) 196abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (LR.ValId == it->ValId) { 197abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (it->start <= End) { 198abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner it = extendIntervalStartTo(it, Start); 199abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 200abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // If LR is a complete superset of an interval, we may need to grow its 201abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // endpoint as well. 202abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (End > it->end) 203abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner extendIntervalEndTo(it, End); 204abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner return it; 205abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 206abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } else { 207abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // Check to make sure that we are not overlapping two live ranges with 208abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // different ValId's. 209abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner assert(it->start >= End && 210abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner "Cannot overlap two LiveRanges with differing ValID's"); 211abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 212b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 213b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // Otherwise, this is just a new range that doesn't interact with anything. 214b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // Insert it. 215b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner return ranges.insert(it, LR); 216fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 217fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 218abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 219abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner/// removeRange - Remove the specified range from this interval. Note that 220abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner/// the range must already be in this interval in its entirety. 221abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattnervoid LiveInterval::removeRange(unsigned Start, unsigned End) { 222abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // Find the LiveRange containing this span. 223abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner Ranges::iterator I = std::upper_bound(ranges.begin(), ranges.end(), Start); 224abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner assert(I != ranges.begin() && "Range is not in interval!"); 225abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner --I; 226abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner assert(I->contains(Start) && I->contains(End-1) && 227abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner "Range is not entirely in interval!"); 228abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 229abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // If the span we are removing is at the start of the LiveRange, adjust it. 230abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (I->start == Start) { 231abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (I->end == End) 232abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner ranges.erase(I); // Removed the whole LiveRange. 233abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner else 234abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner I->start = End; 235abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner return; 236abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 237abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 238abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // Otherwise if the span we are removing is at the end of the LiveRange, 239abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // adjust the other way. 240abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (I->end == End) { 2416925a9f9cc0b9d34cfbc19d9208c416e293ca516Chris Lattner I->end = Start; 242abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner return; 243abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 244abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 245abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // Otherwise, we are splitting the LiveRange into two pieces. 246abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner unsigned OldEnd = I->end; 247abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner I->end = Start; // Trim the old interval. 248abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 249abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // Insert the new one. 250abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner ranges.insert(next(I), LiveRange(End, OldEnd, I->ValId)); 251abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner} 252abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 253abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner/// getLiveRangeContaining - Return the live range that contains the 254abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner/// specified index, or null if there is none. 255f7da2c7b0c6293c268881628fc351bed7763f1f4Chris LattnerLiveInterval::const_iterator 256f7da2c7b0c6293c268881628fc351bed7763f1f4Chris LattnerLiveInterval::FindLiveRangeContaining(unsigned Idx) const { 257f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner const_iterator It = std::upper_bound(begin(), end(), Idx); 258abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (It != ranges.begin()) { 259f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner --It; 260f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner if (It->contains(Idx)) 261f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner return It; 262abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 263abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 264f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner return end(); 265abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner} 266abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 267f7da2c7b0c6293c268881628fc351bed7763f1f4Chris LattnerLiveInterval::iterator 268f7da2c7b0c6293c268881628fc351bed7763f1f4Chris LattnerLiveInterval::FindLiveRangeContaining(unsigned Idx) { 269f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner iterator It = std::upper_bound(begin(), end(), Idx); 2706d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner if (It != begin()) { 271f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner --It; 272f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner if (It->contains(Idx)) 273f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner return It; 274f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 275f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 276f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner return end(); 277f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner} 278abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 2796d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner/// join - Join two live intervals (this, and other) together. This applies 2806d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner/// mappings to the value numbers in the LHS/RHS intervals as specified. If 2816d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner/// the intervals are not joinable, this aborts. 2826d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattnervoid LiveInterval::join(LiveInterval &Other, int *LHSValNoAssignments, 2836d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner int *RHSValNoAssignments, 28491725b75852443923b419fd23215194cfc65dd88Chris Lattner SmallVector<std::pair<unsigned, 28591725b75852443923b419fd23215194cfc65dd88Chris Lattner unsigned>, 16> &NewValueNumberInfo) { 2866d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner 287deb9971061cfb9c57930724fcf8d62fb26dc2213Chris Lattner // Try to do the least amount of work possible. In particular, if there are 288deb9971061cfb9c57930724fcf8d62fb26dc2213Chris Lattner // more liverange chunks in the other set than there are in the 'this' set, 289deb9971061cfb9c57930724fcf8d62fb26dc2213Chris Lattner // swap sets to merge the fewest chunks in possible. 290e7f729b42b54fa751ba3524e1c597aad6d3ec3d7Chris Lattner // 291e7f729b42b54fa751ba3524e1c597aad6d3ec3d7Chris Lattner // Also, if one range is a physreg and one is a vreg, we always merge from the 292e7f729b42b54fa751ba3524e1c597aad6d3ec3d7Chris Lattner // vreg into the physreg, which leaves the vreg intervals pristine. 293e7f729b42b54fa751ba3524e1c597aad6d3ec3d7Chris Lattner if ((Other.ranges.size() > ranges.size() && 294e7f729b42b54fa751ba3524e1c597aad6d3ec3d7Chris Lattner MRegisterInfo::isVirtualRegister(reg)) || 295e7f729b42b54fa751ba3524e1c597aad6d3ec3d7Chris Lattner MRegisterInfo::isPhysicalRegister(Other.reg)) { 296e7f729b42b54fa751ba3524e1c597aad6d3ec3d7Chris Lattner swap(Other); 2976d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner std::swap(LHSValNoAssignments, RHSValNoAssignments); 2986d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } 2996d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner 3006d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // Determine if any of our live range values are mapped. This is uncommon, so 3016d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // we want to avoid the interval scan if not. 3026d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner bool MustMapCurValNos = false; 3036d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner for (unsigned i = 0, e = getNumValNums(); i != e; ++i) { 30491725b75852443923b419fd23215194cfc65dd88Chris Lattner if (ValueNumberInfo[i].first == ~2U) continue; // tombstone value # 3056d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner if (i != (unsigned)LHSValNoAssignments[i]) { 3066d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner MustMapCurValNos = true; 3076d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner break; 3086d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } 3096d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } 3106d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner 3116d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // If we have to apply a mapping to our base interval assignment, rewrite it 3126d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // now. 3136d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner if (MustMapCurValNos) { 3146d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // Map the first live range. 3156d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner iterator OutIt = begin(); 3166d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner OutIt->ValId = LHSValNoAssignments[OutIt->ValId]; 3176d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner ++OutIt; 3186d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner for (iterator I = OutIt, E = end(); I != E; ++I) { 3196d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner OutIt->ValId = LHSValNoAssignments[I->ValId]; 3206d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner 3216d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // If this live range has the same value # as its immediate predecessor, 3226d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // and if they are neighbors, remove one LiveRange. This happens when we 3236d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // have [0,3:0)[4,7:1) and map 0/1 onto the same value #. 3246d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner if (OutIt->ValId == (OutIt-1)->ValId && (OutIt-1)->end == OutIt->start) { 3256d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner (OutIt-1)->end = OutIt->end; 3266d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } else { 3276d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner if (I != OutIt) { 3286d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner OutIt->start = I->start; 3296d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner OutIt->end = I->end; 3306d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } 3316d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner 3326d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // Didn't merge, on to the next one. 3336d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner ++OutIt; 3346d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } 3356d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } 3366d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner 3376d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // If we merge some live ranges, chop off the end. 3386d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner ranges.erase(OutIt, end()); 339deb9971061cfb9c57930724fcf8d62fb26dc2213Chris Lattner } 340e7f729b42b54fa751ba3524e1c597aad6d3ec3d7Chris Lattner 3416d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // Okay, now insert the RHS live ranges into the LHS. 342c114b2cad7293d98686d380273085f5c32966b52Chris Lattner iterator InsertPos = begin(); 343c114b2cad7293d98686d380273085f5c32966b52Chris Lattner for (iterator I = Other.begin(), E = Other.end(); I != E; ++I) { 344abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // Map the ValId in the other live range to the current live range. 3456d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner I->ValId = RHSValNoAssignments[I->ValId]; 346abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner InsertPos = addRangeFrom(*I, InsertPos); 347abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 3486d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner 34991725b75852443923b419fd23215194cfc65dd88Chris Lattner ValueNumberInfo.clear(); 35091725b75852443923b419fd23215194cfc65dd88Chris Lattner ValueNumberInfo.append(NewValueNumberInfo.begin(), NewValueNumberInfo.end()); 351abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner weight += Other.weight; 352fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 353fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 354f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner/// MergeRangesInAsValue - Merge all of the intervals in RHS into this live 355f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner/// interval as the specified value number. The LiveRanges in RHS are 356f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner/// allowed to overlap with LiveRanges in the current interval, but only if 357f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner/// the overlapping LiveRanges have the specified value number. 358f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattnervoid LiveInterval::MergeRangesInAsValue(const LiveInterval &RHS, 359f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner unsigned LHSValNo) { 360f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // TODO: Make this more efficient. 361f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner iterator InsertPos = begin(); 362f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) { 363f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // Map the ValId in the other live range to the current live range. 364f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner LiveRange Tmp = *I; 365f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner Tmp.ValId = LHSValNo; 366f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner InsertPos = addRangeFrom(Tmp, InsertPos); 367f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner } 368f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner} 369f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner 370f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner 371c114b2cad7293d98686d380273085f5c32966b52Chris Lattner/// MergeInClobberRanges - For any live ranges that are not defined in the 372c114b2cad7293d98686d380273085f5c32966b52Chris Lattner/// current interval, but are defined in the Clobbers interval, mark them 373c114b2cad7293d98686d380273085f5c32966b52Chris Lattner/// used with an unknown definition value. 374c114b2cad7293d98686d380273085f5c32966b52Chris Lattnervoid LiveInterval::MergeInClobberRanges(const LiveInterval &Clobbers) { 375c114b2cad7293d98686d380273085f5c32966b52Chris Lattner if (Clobbers.begin() == Clobbers.end()) return; 376c114b2cad7293d98686d380273085f5c32966b52Chris Lattner 377c114b2cad7293d98686d380273085f5c32966b52Chris Lattner // Find a value # to use for the clobber ranges. If there is already a value# 378c114b2cad7293d98686d380273085f5c32966b52Chris Lattner // for unknown values, use it. 379c114b2cad7293d98686d380273085f5c32966b52Chris Lattner // FIXME: Use a single sentinal number for these! 38091725b75852443923b419fd23215194cfc65dd88Chris Lattner unsigned ClobberValNo = getNextValue(~0U, 0); 381c114b2cad7293d98686d380273085f5c32966b52Chris Lattner 382c114b2cad7293d98686d380273085f5c32966b52Chris Lattner iterator IP = begin(); 383c114b2cad7293d98686d380273085f5c32966b52Chris Lattner for (const_iterator I = Clobbers.begin(), E = Clobbers.end(); I != E; ++I) { 384c114b2cad7293d98686d380273085f5c32966b52Chris Lattner unsigned Start = I->start, End = I->end; 385c114b2cad7293d98686d380273085f5c32966b52Chris Lattner IP = std::upper_bound(IP, end(), Start); 386c114b2cad7293d98686d380273085f5c32966b52Chris Lattner 387c114b2cad7293d98686d380273085f5c32966b52Chris Lattner // If the start of this range overlaps with an existing liverange, trim it. 388c114b2cad7293d98686d380273085f5c32966b52Chris Lattner if (IP != begin() && IP[-1].end > Start) { 389c114b2cad7293d98686d380273085f5c32966b52Chris Lattner Start = IP[-1].end; 390c114b2cad7293d98686d380273085f5c32966b52Chris Lattner // Trimmed away the whole range? 391c114b2cad7293d98686d380273085f5c32966b52Chris Lattner if (Start >= End) continue; 392c114b2cad7293d98686d380273085f5c32966b52Chris Lattner } 393c114b2cad7293d98686d380273085f5c32966b52Chris Lattner // If the end of this range overlaps with an existing liverange, trim it. 394c114b2cad7293d98686d380273085f5c32966b52Chris Lattner if (IP != end() && End > IP->start) { 395c114b2cad7293d98686d380273085f5c32966b52Chris Lattner End = IP->start; 396c114b2cad7293d98686d380273085f5c32966b52Chris Lattner // If this trimmed away the whole range, ignore it. 397c114b2cad7293d98686d380273085f5c32966b52Chris Lattner if (Start == End) continue; 398c114b2cad7293d98686d380273085f5c32966b52Chris Lattner } 399c114b2cad7293d98686d380273085f5c32966b52Chris Lattner 400c114b2cad7293d98686d380273085f5c32966b52Chris Lattner // Insert the clobber interval. 401c114b2cad7293d98686d380273085f5c32966b52Chris Lattner IP = addRangeFrom(LiveRange(Start, End, ClobberValNo), IP); 402c114b2cad7293d98686d380273085f5c32966b52Chris Lattner } 403c114b2cad7293d98686d380273085f5c32966b52Chris Lattner} 404c114b2cad7293d98686d380273085f5c32966b52Chris Lattner 405f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// MergeValueNumberInto - This method is called when two value nubmers 406f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// are found to be equivalent. This eliminates V1, replacing all 407f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// LiveRanges with the V1 value number with the V2 value number. This can 408f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// cause merging of V1/V2 values numbers and compaction of the value space. 409f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveInterval::MergeValueNumberInto(unsigned V1, unsigned V2) { 410f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner assert(V1 != V2 && "Identical value#'s are always equivalent!"); 411f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 412f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // This code actually merges the (numerically) larger value number into the 413f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // smaller value number, which is likely to allow us to compactify the value 414f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // space. The only thing we have to be careful of is to preserve the 415f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // instruction that defines the result value. 416f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 417f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Make sure V2 is smaller than V1. 418f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner if (V1 < V2) { 41991725b75852443923b419fd23215194cfc65dd88Chris Lattner setValueNumberInfo(V1, getValNumInfo(V2)); 420f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner std::swap(V1, V2); 421f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 422f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 423f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Merge V1 live ranges into V2. 424f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner for (iterator I = begin(); I != end(); ) { 425f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner iterator LR = I++; 426f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner if (LR->ValId != V1) continue; // Not a V1 LiveRange. 427f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 428f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Okay, we found a V1 live range. If it had a previous, touching, V2 live 429f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // range, extend it. 430f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner if (LR != begin()) { 431f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner iterator Prev = LR-1; 432f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner if (Prev->ValId == V2 && Prev->end == LR->start) { 433f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner Prev->end = LR->end; 434f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 435f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Erase this live-range. 436f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner ranges.erase(LR); 437f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner I = Prev+1; 438f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner LR = Prev; 439f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 440f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 441f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 442f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Okay, now we have a V1 or V2 live range that is maximally merged forward. 443f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Ensure that it is a V2 live-range. 444f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner LR->ValId = V2; 445f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 446f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // If we can merge it into later V2 live ranges, do so now. We ignore any 447f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // following V1 live ranges, as they will be merged in subsequent iterations 448f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // of the loop. 449f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner if (I != end()) { 450f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner if (I->start == LR->end && I->ValId == V2) { 451f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner LR->end = I->end; 452f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner ranges.erase(I); 453f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner I = LR+1; 454f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 455f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 456f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 457c82b3aab6502a9766ddf42b45faeca3d6fa0ad65Chris Lattner 458c82b3aab6502a9766ddf42b45faeca3d6fa0ad65Chris Lattner // Now that V1 is dead, remove it. If it is the largest value number, just 459c82b3aab6502a9766ddf42b45faeca3d6fa0ad65Chris Lattner // nuke it (and any other deleted values neighboring it), otherwise mark it as 460c82b3aab6502a9766ddf42b45faeca3d6fa0ad65Chris Lattner // ~1U so it can be nuked later. 4616d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner if (V1 == getNumValNums()-1) { 462c82b3aab6502a9766ddf42b45faeca3d6fa0ad65Chris Lattner do { 46391725b75852443923b419fd23215194cfc65dd88Chris Lattner ValueNumberInfo.pop_back(); 46491725b75852443923b419fd23215194cfc65dd88Chris Lattner } while (ValueNumberInfo.back().first == ~1U); 465c82b3aab6502a9766ddf42b45faeca3d6fa0ad65Chris Lattner } else { 46691725b75852443923b419fd23215194cfc65dd88Chris Lattner ValueNumberInfo[V1].first = ~1U; 467c82b3aab6502a9766ddf42b45faeca3d6fa0ad65Chris Lattner } 468f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner} 469f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 470fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattnerstd::ostream& llvm::operator<<(std::ostream& os, const LiveRange &LR) { 471abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner return os << '[' << LR.start << ',' << LR.end << ':' << LR.ValId << ")"; 472abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner} 473abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 474abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattnervoid LiveRange::dump() const { 475d9fd2acc1f172e4b8c33c3562667102f9af4d28dBill Wendling llvm_cerr << *this << "\n"; 476fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 477fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 478d9fd2acc1f172e4b8c33c3562667102f9af4d28dBill Wendlingvoid LiveInterval::print(llvm_ostream &OS, const MRegisterInfo *MRI) const { 47938135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner if (MRI && MRegisterInfo::isPhysicalRegister(reg)) 48038135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner OS << MRI->getName(reg); 48138135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner else 48238135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner OS << "%reg" << reg; 48338135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner 48438135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner OS << ',' << weight; 48538135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner 48638135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner if (empty()) 48738135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner OS << "EMPTY"; 48838135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner else { 48938135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner OS << " = "; 49038135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner for (LiveInterval::Ranges::const_iterator I = ranges.begin(), 49138135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner E = ranges.end(); I != E; ++I) 49238135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner OS << *I; 49338135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner } 494be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner 495be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Print value number info. 4966d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner if (getNumValNums()) { 497be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner OS << " "; 4986d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner for (unsigned i = 0; i != getNumValNums(); ++i) { 499be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner if (i) OS << " "; 500be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner OS << i << "@"; 50191725b75852443923b419fd23215194cfc65dd88Chris Lattner if (ValueNumberInfo[i].first == ~0U) { 502be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner OS << "?"; 503be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner } else { 50491725b75852443923b419fd23215194cfc65dd88Chris Lattner OS << ValueNumberInfo[i].first; 505be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner } 506be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner } 507be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner } 508fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 509abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 510abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattnervoid LiveInterval::dump() const { 511d9fd2acc1f172e4b8c33c3562667102f9af4d28dBill Wendling llvm_cerr << *this << "\n"; 512abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner} 513