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