LiveInterval.cpp revision 15a571436da812c7cecbc3f3423ead2edff50358
1fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner//===-- LiveInterval.cpp - Live Interval Representation -------------------===// 2fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 3fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// The LLVM Compiler Infrastructure 4fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// 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 1386af65552172c9149996600bc3f55bed6f949c8aBob Wilson// such that v is live at j' and 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" 22233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames#include "llvm/CodeGen/LiveIntervalAnalysis.h" 2390f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng#include "llvm/CodeGen/MachineRegisterInfo.h" 240adb527d169e1f557676fda35bc9abb735e5c912Evan Cheng#include "llvm/ADT/DenseMap.h" 253c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng#include "llvm/ADT/SmallSet.h" 2638b0e7bbf2590f99122a2535d16f34bd12c3bb24Bill Wendling#include "llvm/ADT/STLExtras.h" 275242154b558f0783830938f18153e0a7964fb4faDavid Greene#include "llvm/Support/Debug.h" 28a717b7be8886c4c6ae261ee553c5cbcae29c1e52Daniel Dunbar#include "llvm/Support/raw_ostream.h" 296f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman#include "llvm/Target/TargetRegisterInfo.h" 30c4d3b918165461bc6f5d395bca8d9d9d8a84413dAlkis Evlogimenos#include <algorithm> 31fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattnerusing namespace llvm; 32fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 33fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// An example for liveAt(): 34fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 35aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner// this = [1,4), liveAt(0) will return false. The instruction defining this 36aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner// spans slots [0,3]. The interval belongs to an spilled definition of the 37aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner// variable it represents. This is because slot 1 is used (def slot) and spans 38aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner// up to slot 3 (store slot). 39fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 40233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesbool LiveInterval::liveAt(SlotIndex I) const { 41ebd7e6c54dce754a88d8f38df4ac2f388f35435eChris Lattner Ranges::const_iterator r = std::upper_bound(ranges.begin(), ranges.end(), I); 42edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman 43fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (r == ranges.begin()) 44fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return false; 45fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 46fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner --r; 47aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner return r->contains(I); 48c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng} 49c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng 50c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng// liveBeforeAndAt - Check if the interval is live at the index and the index 51c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng// just before it. If index is liveAt, check if it starts a new live range. 52c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng// If it does, then check if the previous live range ends at index-1. 53233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesbool LiveInterval::liveBeforeAndAt(SlotIndex I) const { 54c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng Ranges::const_iterator r = std::upper_bound(ranges.begin(), ranges.end(), I); 55c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng 56c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (r == ranges.begin()) 57c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return false; 58c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng 59c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng --r; 60c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (!r->contains(I)) 61c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return false; 62c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (I != r->start) 63c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return true; 64c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng // I is the start of a live range. Check if the previous live range ends 65c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng // at I-1. 66c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (r == ranges.begin()) 67c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return false; 68c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return r->end == I; 69fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 70fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 7115a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen/// killedAt - Return true if a live range ends at index. Note that the kill 7215a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen/// point is not contained in the half-open live range. It is usually the 7315a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen/// getDefIndex() slot following its last use. 7415a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesenbool LiveInterval::killedAt(SlotIndex I) const { 7515a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen Ranges::const_iterator r = std::lower_bound(ranges.begin(), ranges.end(), I); 7615a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen 7715a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen // Now r points to the first interval with start >= I, or ranges.end(). 7815a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen if (r == ranges.begin()) 7915a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen return false; 8015a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen 8115a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen --r; 8215a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen // Now r points to the last interval with end <= I. 8315a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen // r->end is the kill point. 8415a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen return r->end == I; 8515a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen} 8615a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen 8715a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen/// killedInRange - Return true if the interval has kills in [Start,End). 8815a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesenbool LiveInterval::killedInRange(SlotIndex Start, SlotIndex End) const { 8915a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen Ranges::const_iterator r = 9015a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen std::lower_bound(ranges.begin(), ranges.end(), End); 9115a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen 9215a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen // Now r points to the first interval with start >= End, or ranges.end(). 9315a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen if (r == ranges.begin()) 9415a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen return false; 9515a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen 9615a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen --r; 9715a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen // Now r points to the last interval with end <= End. 9815a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen // r->end is the kill point. 9915a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen return r->end >= Start && r->end < End; 10015a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen} 10115a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen 102bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner// overlaps - Return true if the intersection of the two live intervals is 103bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner// not empty. 104bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner// 105fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// An example for overlaps(): 106fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 107fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 0: A = ... 108fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 4: B = ... 109fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 8: C = A + B ;; last use of A 110fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 111fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// The live intervals should look like: 112fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 113fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// A = [3, 11) 114fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// B = [7, x) 115fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// C = [11, y) 116fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 117fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// A->overlaps(C) should return false since we want to be able to join 118fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// A and C. 119bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner// 120bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattnerbool LiveInterval::overlapsFrom(const LiveInterval& other, 121bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner const_iterator StartPos) const { 122bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner const_iterator i = begin(); 123bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner const_iterator ie = end(); 124bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner const_iterator j = StartPos; 125bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner const_iterator je = other.end(); 126bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner 127bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner assert((StartPos->start <= i->start || StartPos == other.begin()) && 1288c68b6a226ce46b35eafda972e04bf53128c2615Chris Lattner StartPos != other.end() && "Bogus start position hint!"); 129f542649f1b374b1bae845e4e4f6d1e82f90a9e31Chris Lattner 130fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (i->start < j->start) { 131aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner i = std::upper_bound(i, ie, j->start); 132fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (i != ranges.begin()) --i; 133aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner } else if (j->start < i->start) { 134ead1b3f0bb70cd9c1ba7a853a79070cb47db9344Chris Lattner ++StartPos; 135ead1b3f0bb70cd9c1ba7a853a79070cb47db9344Chris Lattner if (StartPos != other.end() && StartPos->start <= i->start) { 136ead1b3f0bb70cd9c1ba7a853a79070cb47db9344Chris Lattner assert(StartPos < other.end() && i < end()); 1378c68b6a226ce46b35eafda972e04bf53128c2615Chris Lattner j = std::upper_bound(j, je, i->start); 1388c68b6a226ce46b35eafda972e04bf53128c2615Chris Lattner if (j != other.ranges.begin()) --j; 1398c68b6a226ce46b35eafda972e04bf53128c2615Chris Lattner } 140aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner } else { 141aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner return true; 142fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 143fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 1449fddc12c9b16a5526b0ee2e6f1da252f7974d7d0Chris Lattner if (j == je) return false; 1459fddc12c9b16a5526b0ee2e6f1da252f7974d7d0Chris Lattner 1469fddc12c9b16a5526b0ee2e6f1da252f7974d7d0Chris Lattner while (i != ie) { 147fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (i->start > j->start) { 148a1613db62fec94845aa8306232fb665273615badAlkis Evlogimenos std::swap(i, j); 149a1613db62fec94845aa8306232fb665273615badAlkis Evlogimenos std::swap(ie, je); 150fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 151fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 152fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (i->end > j->start) 153fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return true; 154fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner ++i; 155fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 156fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 157fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return false; 158fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 159fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 160cccdb2b602cf421d8890130308945163620ebc68Evan Cheng/// overlaps - Return true if the live interval overlaps a range specified 161cccdb2b602cf421d8890130308945163620ebc68Evan Cheng/// by [Start, End). 162233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesbool LiveInterval::overlaps(SlotIndex Start, SlotIndex End) const { 163cccdb2b602cf421d8890130308945163620ebc68Evan Cheng assert(Start < End && "Invalid range"); 164cccdb2b602cf421d8890130308945163620ebc68Evan Cheng const_iterator I = begin(); 165cccdb2b602cf421d8890130308945163620ebc68Evan Cheng const_iterator E = end(); 166cccdb2b602cf421d8890130308945163620ebc68Evan Cheng const_iterator si = std::upper_bound(I, E, Start); 167cccdb2b602cf421d8890130308945163620ebc68Evan Cheng const_iterator ei = std::upper_bound(I, E, End); 168cccdb2b602cf421d8890130308945163620ebc68Evan Cheng if (si != ei) 169cccdb2b602cf421d8890130308945163620ebc68Evan Cheng return true; 170cccdb2b602cf421d8890130308945163620ebc68Evan Cheng if (si == I) 171cccdb2b602cf421d8890130308945163620ebc68Evan Cheng return false; 172cccdb2b602cf421d8890130308945163620ebc68Evan Cheng --si; 173cccdb2b602cf421d8890130308945163620ebc68Evan Cheng return si->contains(Start); 174cccdb2b602cf421d8890130308945163620ebc68Evan Cheng} 175cccdb2b602cf421d8890130308945163620ebc68Evan Cheng 176b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// extendIntervalEndTo - This method is used when we want to extend the range 177b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// specified by I to end at the specified endpoint. To do this, we should 178b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// merge and eliminate all ranges that this will overlap with. The iterator is 179b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// not invalidated. 180233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesvoid LiveInterval::extendIntervalEndTo(Ranges::iterator I, SlotIndex NewEnd) { 181b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner assert(I != ranges.end() && "Not a valid interval!"); 1827ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *ValNo = I->valno; 183233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex OldEnd = I->end; 184b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 185b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // Search for the first interval that we can't merge with. 186b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner Ranges::iterator MergeTo = next(I); 187abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner for (; MergeTo != ranges.end() && NewEnd >= MergeTo->end; ++MergeTo) { 1887ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng assert(MergeTo->valno == ValNo && "Cannot merge with differing values!"); 189abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 190b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 191b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // If NewEnd was in the middle of an interval, make sure to get its endpoint. 192b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner I->end = std::max(NewEnd, prior(MergeTo)->end); 193b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 194b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner // Erase any dead ranges. 195b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner ranges.erase(next(I), MergeTo); 1964f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng 197b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner // If the newly formed range now touches the range after it and if they have 198b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner // the same value number, merge the two ranges into one range. 199cef6010c64bc56fa2a8f1e7e9e28b8821adeceacChris Lattner Ranges::iterator Next = next(I); 2007ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (Next != ranges.end() && Next->start <= I->end && Next->valno == ValNo) { 201cef6010c64bc56fa2a8f1e7e9e28b8821adeceacChris Lattner I->end = Next->end; 202cef6010c64bc56fa2a8f1e7e9e28b8821adeceacChris Lattner ranges.erase(Next); 203b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner } 204fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 205fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 206fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 207b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// extendIntervalStartTo - This method is used when we want to extend the range 208b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// specified by I to start at the specified endpoint. To do this, we should 209b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// merge and eliminate all ranges that this will overlap with. 210edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha BrukmanLiveInterval::Ranges::iterator 211233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang HamesLiveInterval::extendIntervalStartTo(Ranges::iterator I, SlotIndex NewStart) { 212b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner assert(I != ranges.end() && "Not a valid interval!"); 2137ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *ValNo = I->valno; 214b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 215b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // Search for the first interval that we can't merge with. 216b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner Ranges::iterator MergeTo = I; 217b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner do { 218b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner if (MergeTo == ranges.begin()) { 219b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner I->start = NewStart; 220abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner ranges.erase(MergeTo, I); 221b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner return I; 222b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner } 2237ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng assert(MergeTo->valno == ValNo && "Cannot merge with differing values!"); 224b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner --MergeTo; 225b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner } while (NewStart <= MergeTo->start); 226b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 227b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // If we start in the middle of another interval, just delete a range and 228b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // extend that interval. 2297ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (MergeTo->end >= NewStart && MergeTo->valno == ValNo) { 230b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner MergeTo->end = I->end; 231b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner } else { 232b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // Otherwise, extend the interval right after. 233b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner ++MergeTo; 234b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner MergeTo->start = NewStart; 235b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner MergeTo->end = I->end; 236fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 237b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 238b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner ranges.erase(next(MergeTo), next(I)); 239b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner return MergeTo; 240fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 241fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 242c114b2cad7293d98686d380273085f5c32966b52Chris LattnerLiveInterval::iterator 243c114b2cad7293d98686d380273085f5c32966b52Chris LattnerLiveInterval::addRangeFrom(LiveRange LR, iterator From) { 244233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex Start = LR.start, End = LR.end; 245c114b2cad7293d98686d380273085f5c32966b52Chris Lattner iterator it = std::upper_bound(From, ranges.end(), Start); 246b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 247b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // If the inserted interval starts in the middle or right at the end of 248b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // another interval, just extend that interval to contain the range of LR. 249b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner if (it != ranges.begin()) { 250c114b2cad7293d98686d380273085f5c32966b52Chris Lattner iterator B = prior(it); 2517ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (LR.valno == B->valno) { 252abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (B->start <= Start && B->end >= Start) { 253abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner extendIntervalEndTo(B, End); 254abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner return B; 255abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 256abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } else { 257abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // Check to make sure that we are not overlapping two live ranges with 2587ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng // different valno's. 259abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner assert(B->end <= Start && 2608311befb6968a581a3abdce1e13b5d63922662f7Brian Gaeke "Cannot overlap two LiveRanges with differing ValID's" 2618311befb6968a581a3abdce1e13b5d63922662f7Brian Gaeke " (did you def the same reg twice in a MachineInstr?)"); 262b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner } 263fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 264b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 265b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // Otherwise, if this range ends in the middle of, or right next to, another 266b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // interval, merge it into that interval. 2674c71dfe356716e6bc1993ef5efdced08b68fe612Anton Korobeynikov if (it != ranges.end()) { 2687ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (LR.valno == it->valno) { 269abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (it->start <= End) { 270abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner it = extendIntervalStartTo(it, Start); 271abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 272abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // If LR is a complete superset of an interval, we may need to grow its 273abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // endpoint as well. 274abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (End > it->end) 275abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner extendIntervalEndTo(it, End); 276abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner return it; 277abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 278abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } else { 279abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // Check to make sure that we are not overlapping two live ranges with 2807ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng // different valno's. 281abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner assert(it->start >= End && 282abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner "Cannot overlap two LiveRanges with differing ValID's"); 283abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 2844c71dfe356716e6bc1993ef5efdced08b68fe612Anton Korobeynikov } 285b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 286b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // Otherwise, this is just a new range that doesn't interact with anything. 287b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // Insert it. 288b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner return ranges.insert(it, LR); 289fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 290fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 2918651125d2885f74546b6e2a556082111d5b75da3Lang Hames/// isInOneLiveRange - Return true if the range specified is entirely in 2925a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng/// a single LiveRange of the live interval. 293233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesbool LiveInterval::isInOneLiveRange(SlotIndex Start, SlotIndex End) { 2945a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng Ranges::iterator I = std::upper_bound(ranges.begin(), ranges.end(), Start); 2955a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng if (I == ranges.begin()) 2965a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng return false; 2975a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng --I; 2988651125d2885f74546b6e2a556082111d5b75da3Lang Hames return I->containsRange(Start, End); 2995a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng} 3005a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng 301abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 302abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner/// removeRange - Remove the specified range from this interval. Note that 30342cc6e33ec0f63560c31f1928c56b4b0465d537cEvan Cheng/// the range must be in a single LiveRange in its entirety. 304233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesvoid LiveInterval::removeRange(SlotIndex Start, SlotIndex End, 305d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng bool RemoveDeadValNo) { 306abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // Find the LiveRange containing this span. 307abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner Ranges::iterator I = std::upper_bound(ranges.begin(), ranges.end(), Start); 308abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner assert(I != ranges.begin() && "Range is not in interval!"); 309abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner --I; 3108651125d2885f74546b6e2a556082111d5b75da3Lang Hames assert(I->containsRange(Start, End) && "Range is not entirely in interval!"); 311abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 312abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // If the span we are removing is at the start of the LiveRange, adjust it. 313d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng VNInfo *ValNo = I->valno; 314abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (I->start == Start) { 3154f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng if (I->end == End) { 316d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng if (RemoveDeadValNo) { 317d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng // Check if val# is dead. 318d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng bool isDead = true; 319d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng for (const_iterator II = begin(), EE = end(); II != EE; ++II) 320d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng if (II != I && II->valno == ValNo) { 321d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng isDead = false; 322d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng break; 32315a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen } 324d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng if (isDead) { 325d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng // Now that ValNo is dead, remove it. If it is the largest value 326d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng // number, just nuke it (and any other deleted values neighboring it), 327d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng // otherwise mark it as ~1U so it can be nuked later. 328d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng if (ValNo->id == getNumValNums()-1) { 329d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng do { 330d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng valnos.pop_back(); 331857c4e01f85601cf2084adb860616256ee47c177Lang Hames } while (!valnos.empty() && valnos.back()->isUnused()); 332d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng } else { 333857c4e01f85601cf2084adb860616256ee47c177Lang Hames ValNo->setIsUnused(true); 334d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng } 335d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng } 336d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng } 337d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng 338abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner ranges.erase(I); // Removed the whole LiveRange. 3394f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng } else 340abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner I->start = End; 341abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner return; 342abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 343abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 344abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // Otherwise if the span we are removing is at the end of the LiveRange, 345abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // adjust the other way. 346abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (I->end == End) { 3476925a9f9cc0b9d34cfbc19d9208c416e293ca516Chris Lattner I->end = Start; 348abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner return; 349abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 350abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 351abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // Otherwise, we are splitting the LiveRange into two pieces. 352233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex OldEnd = I->end; 353abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner I->end = Start; // Trim the old interval. 354abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 355abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // Insert the new one. 356d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng ranges.insert(next(I), LiveRange(End, OldEnd, ValNo)); 357abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner} 358abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 359d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng/// removeValNo - Remove all the ranges defined by the specified value#. 360d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng/// Also remove the value# from value# list. 361d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Chengvoid LiveInterval::removeValNo(VNInfo *ValNo) { 362d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng if (empty()) return; 363d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng Ranges::iterator I = ranges.end(); 364d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng Ranges::iterator E = ranges.begin(); 365d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng do { 366d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng --I; 367d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng if (I->valno == ValNo) 368d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng ranges.erase(I); 369d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng } while (I != E); 370d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng // Now that ValNo is dead, remove it. If it is the largest value 371d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng // number, just nuke it (and any other deleted values neighboring it), 372d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng // otherwise mark it as ~1U so it can be nuked later. 373d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng if (ValNo->id == getNumValNums()-1) { 374d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng do { 375d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng valnos.pop_back(); 376857c4e01f85601cf2084adb860616256ee47c177Lang Hames } while (!valnos.empty() && valnos.back()->isUnused()); 377d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng } else { 378857c4e01f85601cf2084adb860616256ee47c177Lang Hames ValNo->setIsUnused(true); 379d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng } 380d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng} 3818651125d2885f74546b6e2a556082111d5b75da3Lang Hames 382abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner/// getLiveRangeContaining - Return the live range that contains the 383abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner/// specified index, or null if there is none. 384f7da2c7b0c6293c268881628fc351bed7763f1f4Chris LattnerLiveInterval::const_iterator 385233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang HamesLiveInterval::FindLiveRangeContaining(SlotIndex Idx) const { 386f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner const_iterator It = std::upper_bound(begin(), end(), Idx); 387abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (It != ranges.begin()) { 388f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner --It; 389f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner if (It->contains(Idx)) 390f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner return It; 391abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 392abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 393f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner return end(); 394abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner} 395abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 396f7da2c7b0c6293c268881628fc351bed7763f1f4Chris LattnerLiveInterval::iterator 397233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang HamesLiveInterval::FindLiveRangeContaining(SlotIndex Idx) { 398f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner iterator It = std::upper_bound(begin(), end(), Idx); 3996d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner if (It != begin()) { 400f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner --It; 401f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner if (It->contains(Idx)) 402f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner return It; 403f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 404f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 405f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner return end(); 406f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner} 407abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 4088651125d2885f74546b6e2a556082111d5b75da3Lang Hames/// findDefinedVNInfo - Find the VNInfo defined by the specified 4098651125d2885f74546b6e2a556082111d5b75da3Lang Hames/// index (register interval). 410233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang HamesVNInfo *LiveInterval::findDefinedVNInfoForRegInt(SlotIndex Idx) const { 4113f32d65912b4da23793dab618d981be2ce11c331Evan Cheng for (LiveInterval::const_vni_iterator i = vni_begin(), e = vni_end(); 4128651125d2885f74546b6e2a556082111d5b75da3Lang Hames i != e; ++i) { 4138651125d2885f74546b6e2a556082111d5b75da3Lang Hames if ((*i)->def == Idx) 4148651125d2885f74546b6e2a556082111d5b75da3Lang Hames return *i; 4158651125d2885f74546b6e2a556082111d5b75da3Lang Hames } 4168651125d2885f74546b6e2a556082111d5b75da3Lang Hames 4178651125d2885f74546b6e2a556082111d5b75da3Lang Hames return 0; 4188651125d2885f74546b6e2a556082111d5b75da3Lang Hames} 4198651125d2885f74546b6e2a556082111d5b75da3Lang Hames 4208651125d2885f74546b6e2a556082111d5b75da3Lang Hames/// findDefinedVNInfo - Find the VNInfo defined by the specified 4218651125d2885f74546b6e2a556082111d5b75da3Lang Hames/// register (stack inteval). 4228651125d2885f74546b6e2a556082111d5b75da3Lang HamesVNInfo *LiveInterval::findDefinedVNInfoForStackInt(unsigned reg) const { 4238651125d2885f74546b6e2a556082111d5b75da3Lang Hames for (LiveInterval::const_vni_iterator i = vni_begin(), e = vni_end(); 4248651125d2885f74546b6e2a556082111d5b75da3Lang Hames i != e; ++i) { 4258651125d2885f74546b6e2a556082111d5b75da3Lang Hames if ((*i)->getReg() == reg) 4268651125d2885f74546b6e2a556082111d5b75da3Lang Hames return *i; 4278651125d2885f74546b6e2a556082111d5b75da3Lang Hames } 4288651125d2885f74546b6e2a556082111d5b75da3Lang Hames return 0; 4293f32d65912b4da23793dab618d981be2ce11c331Evan Cheng} 4303f32d65912b4da23793dab618d981be2ce11c331Evan Cheng 4316d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner/// join - Join two live intervals (this, and other) together. This applies 4326d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner/// mappings to the value numbers in the LHS/RHS intervals as specified. If 4336d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner/// the intervals are not joinable, this aborts. 434233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesvoid LiveInterval::join(LiveInterval &Other, 435233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames const int *LHSValNoAssignments, 436af992f782fb2cac8d00b352c3dd73f6e782b5758David Greene const int *RHSValNoAssignments, 43790f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng SmallVector<VNInfo*, 16> &NewVNInfo, 43890f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng MachineRegisterInfo *MRI) { 4396d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // Determine if any of our live range values are mapped. This is uncommon, so 440343013538f72f2202338f57161c0bd92344ca407Evan Cheng // we want to avoid the interval scan if not. 4416d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner bool MustMapCurValNos = false; 442343013538f72f2202338f57161c0bd92344ca407Evan Cheng unsigned NumVals = getNumValNums(); 443343013538f72f2202338f57161c0bd92344ca407Evan Cheng unsigned NumNewVals = NewVNInfo.size(); 444343013538f72f2202338f57161c0bd92344ca407Evan Cheng for (unsigned i = 0; i != NumVals; ++i) { 445343013538f72f2202338f57161c0bd92344ca407Evan Cheng unsigned LHSValID = LHSValNoAssignments[i]; 446343013538f72f2202338f57161c0bd92344ca407Evan Cheng if (i != LHSValID || 447f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng (NewVNInfo[LHSValID] && NewVNInfo[LHSValID] != getValNumInfo(i))) 4486d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner MustMapCurValNos = true; 4496d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } 4507ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng 4516d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // If we have to apply a mapping to our base interval assignment, rewrite it 4526d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // now. 4536d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner if (MustMapCurValNos) { 4546d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // Map the first live range. 4556d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner iterator OutIt = begin(); 4567ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng OutIt->valno = NewVNInfo[LHSValNoAssignments[OutIt->valno->id]]; 4576d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner ++OutIt; 4586d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner for (iterator I = OutIt, E = end(); I != E; ++I) { 4597ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng OutIt->valno = NewVNInfo[LHSValNoAssignments[I->valno->id]]; 4606d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner 4616d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // If this live range has the same value # as its immediate predecessor, 4626d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // and if they are neighbors, remove one LiveRange. This happens when we 4636d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // have [0,3:0)[4,7:1) and map 0/1 onto the same value #. 4647ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (OutIt->valno == (OutIt-1)->valno && (OutIt-1)->end == OutIt->start) { 4656d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner (OutIt-1)->end = OutIt->end; 4666d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } else { 4676d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner if (I != OutIt) { 4686d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner OutIt->start = I->start; 4696d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner OutIt->end = I->end; 4706d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } 4716d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner 4726d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // Didn't merge, on to the next one. 4736d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner ++OutIt; 4746d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } 4756d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } 4766d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner 4776d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // If we merge some live ranges, chop off the end. 4786d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner ranges.erase(OutIt, end()); 479deb9971061cfb9c57930724fcf8d62fb26dc2213Chris Lattner } 4804f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng 4817ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng // Remember assignements because val# ids are changing. 482343013538f72f2202338f57161c0bd92344ca407Evan Cheng SmallVector<unsigned, 16> OtherAssignments; 4837ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng for (iterator I = Other.begin(), E = Other.end(); I != E; ++I) 4847ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng OtherAssignments.push_back(RHSValNoAssignments[I->valno->id]); 4857ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng 4867ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng // Update val# info. Renumber them and make sure they all belong to this 487f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng // LiveInterval now. Also remove dead val#'s. 488f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng unsigned NumValNos = 0; 489f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng for (unsigned i = 0; i < NumNewVals; ++i) { 490343013538f72f2202338f57161c0bd92344ca407Evan Cheng VNInfo *VNI = NewVNInfo[i]; 491f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng if (VNI) { 49230590f502325321958b35bec7295159e3948291aEvan Cheng if (NumValNos >= NumVals) 493f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng valnos.push_back(VNI); 494f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng else 495f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng valnos[NumValNos] = VNI; 496f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng VNI->id = NumValNos++; // Renumber val#. 497343013538f72f2202338f57161c0bd92344ca407Evan Cheng } 4987ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng } 499343013538f72f2202338f57161c0bd92344ca407Evan Cheng if (NumNewVals < NumVals) 500343013538f72f2202338f57161c0bd92344ca407Evan Cheng valnos.resize(NumNewVals); // shrinkify 5014f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng 5026d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // Okay, now insert the RHS live ranges into the LHS. 503c114b2cad7293d98686d380273085f5c32966b52Chris Lattner iterator InsertPos = begin(); 5047ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng unsigned RangeNo = 0; 5057ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng for (iterator I = Other.begin(), E = Other.end(); I != E; ++I, ++RangeNo) { 5067ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng // Map the valno in the other live range to the current live range. 5077ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng I->valno = NewVNInfo[OtherAssignments[RangeNo]]; 508f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng assert(I->valno && "Adding a dead range?"); 509abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner InsertPos = addRangeFrom(*I, InsertPos); 510abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 5116d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner 51229ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene ComputeJoinedWeight(Other); 51390f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng 51490f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng // Update regalloc hint if currently there isn't one. 51590f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng if (TargetRegisterInfo::isVirtualRegister(reg) && 51690f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng TargetRegisterInfo::isVirtualRegister(Other.reg)) { 517358dec51804ee52e47ea3a47c9248086e458ad7cEvan Cheng std::pair<unsigned, unsigned> Hint = MRI->getRegAllocationHint(reg); 518358dec51804ee52e47ea3a47c9248086e458ad7cEvan Cheng if (Hint.first == 0 && Hint.second == 0) { 519358dec51804ee52e47ea3a47c9248086e458ad7cEvan Cheng std::pair<unsigned, unsigned> OtherHint = 52090f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng MRI->getRegAllocationHint(Other.reg); 521358dec51804ee52e47ea3a47c9248086e458ad7cEvan Cheng if (OtherHint.first || OtherHint.second) 52290f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng MRI->setRegAllocationHint(reg, OtherHint.first, OtherHint.second); 52390f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng } 52490f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng } 525fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 526fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 527f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner/// MergeRangesInAsValue - Merge all of the intervals in RHS into this live 528f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner/// interval as the specified value number. The LiveRanges in RHS are 529f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner/// allowed to overlap with LiveRanges in the current interval, but only if 530f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner/// the overlapping LiveRanges have the specified value number. 531f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattnervoid LiveInterval::MergeRangesInAsValue(const LiveInterval &RHS, 5327ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *LHSValNo) { 533f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // TODO: Make this more efficient. 534f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner iterator InsertPos = begin(); 535f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) { 5367ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng // Map the valno in the other live range to the current live range. 537f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner LiveRange Tmp = *I; 5387ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng Tmp.valno = LHSValNo; 539f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner InsertPos = addRangeFrom(Tmp, InsertPos); 540f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner } 541f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner} 542f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner 543f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner 54432dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng/// MergeValueInAsValue - Merge all of the live ranges of a specific val# 54532dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng/// in RHS into this live interval as the specified value number. 54632dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng/// The LiveRanges in RHS are allowed to overlap with LiveRanges in the 5473c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng/// current interval, it will replace the value numbers of the overlaped 5483c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng/// live ranges with the specified value number. 549233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesvoid LiveInterval::MergeValueInAsValue( 550233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames const LiveInterval &RHS, 551233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames const VNInfo *RHSValNo, VNInfo *LHSValNo) { 5523c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng SmallVector<VNInfo*, 4> ReplacedValNos; 5533c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng iterator IP = begin(); 55432dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) { 555014b8631c0df0c5a91ccee2485bcd408844ed377Jakob Stoklund Olesen assert(I->valno == RHS.getValNumInfo(I->valno->id) && "Bad VNInfo"); 55632dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (I->valno != RHSValNo) 55732dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng continue; 558233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex Start = I->start, End = I->end; 5593c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng IP = std::upper_bound(IP, end(), Start); 5603c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng // If the start of this range overlaps with an existing liverange, trim it. 5613c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng if (IP != begin() && IP[-1].end > Start) { 562294e6524916aecd874dddeede4cc074d31f5f59fEvan Cheng if (IP[-1].valno != LHSValNo) { 563294e6524916aecd874dddeede4cc074d31f5f59fEvan Cheng ReplacedValNos.push_back(IP[-1].valno); 564294e6524916aecd874dddeede4cc074d31f5f59fEvan Cheng IP[-1].valno = LHSValNo; // Update val#. 5653c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng } 5663c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng Start = IP[-1].end; 5673c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng // Trimmed away the whole range? 5683c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng if (Start >= End) continue; 5693c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng } 5703c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng // If the end of this range overlaps with an existing liverange, trim it. 5713c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng if (IP != end() && End > IP->start) { 5723c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng if (IP->valno != LHSValNo) { 5733c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng ReplacedValNos.push_back(IP->valno); 5743c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng IP->valno = LHSValNo; // Update val#. 5753c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng } 5763c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng End = IP->start; 5773c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng // If this trimmed away the whole range, ignore it. 5783c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng if (Start == End) continue; 5793c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng } 5803c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng 58132dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // Map the valno in the other live range to the current live range. 5823c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng IP = addRangeFrom(LiveRange(Start, End, LHSValNo), IP); 5833c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng } 5843c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng 5853c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng 5863c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng SmallSet<VNInfo*, 4> Seen; 5873c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng for (unsigned i = 0, e = ReplacedValNos.size(); i != e; ++i) { 5883c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng VNInfo *V1 = ReplacedValNos[i]; 5893c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng if (Seen.insert(V1)) { 5903c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng bool isDead = true; 5913c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng for (const_iterator I = begin(), E = end(); I != E; ++I) 5923c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng if (I->valno == V1) { 5933c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng isDead = false; 5943c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng break; 5953c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng } 5963c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng if (isDead) { 5973c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng // Now that V1 is dead, remove it. If it is the largest value number, 5983c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng // just nuke it (and any other deleted values neighboring it), otherwise 5993c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng // mark it as ~1U so it can be nuked later. 6003c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng if (V1->id == getNumValNums()-1) { 6013c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng do { 6023c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng valnos.pop_back(); 603857c4e01f85601cf2084adb860616256ee47c177Lang Hames } while (!valnos.empty() && valnos.back()->isUnused()); 6043c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng } else { 605857c4e01f85601cf2084adb860616256ee47c177Lang Hames V1->setIsUnused(true); 6063c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng } 6073c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng } 6083c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng } 60932dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng } 61032dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng} 61132dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng 61232dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng 613c114b2cad7293d98686d380273085f5c32966b52Chris Lattner/// MergeInClobberRanges - For any live ranges that are not defined in the 614c114b2cad7293d98686d380273085f5c32966b52Chris Lattner/// current interval, but are defined in the Clobbers interval, mark them 615c114b2cad7293d98686d380273085f5c32966b52Chris Lattner/// used with an unknown definition value. 616233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesvoid LiveInterval::MergeInClobberRanges(LiveIntervals &li_, 617233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames const LiveInterval &Clobbers, 618991de14dd62dcbab4b31357ae22dc5b053ba50a0Benjamin Kramer VNInfo::Allocator &VNInfoAllocator) { 619a8c763b3071ae1a58ee8baeb282331245527e004Dan Gohman if (Clobbers.empty()) return; 620c114b2cad7293d98686d380273085f5c32966b52Chris Lattner 6210adb527d169e1f557676fda35bc9abb735e5c912Evan Cheng DenseMap<VNInfo*, VNInfo*> ValNoMaps; 622a4b2bab23313b1d45e1f3e6c9610a1e83fce4005Evan Cheng VNInfo *UnusedValNo = 0; 623c114b2cad7293d98686d380273085f5c32966b52Chris Lattner iterator IP = begin(); 624c114b2cad7293d98686d380273085f5c32966b52Chris Lattner for (const_iterator I = Clobbers.begin(), E = Clobbers.end(); I != E; ++I) { 6250adb527d169e1f557676fda35bc9abb735e5c912Evan Cheng // For every val# in the Clobbers interval, create a new "unknown" val#. 6260adb527d169e1f557676fda35bc9abb735e5c912Evan Cheng VNInfo *ClobberValNo = 0; 6270adb527d169e1f557676fda35bc9abb735e5c912Evan Cheng DenseMap<VNInfo*, VNInfo*>::iterator VI = ValNoMaps.find(I->valno); 6280adb527d169e1f557676fda35bc9abb735e5c912Evan Cheng if (VI != ValNoMaps.end()) 6290adb527d169e1f557676fda35bc9abb735e5c912Evan Cheng ClobberValNo = VI->second; 630a4b2bab23313b1d45e1f3e6c9610a1e83fce4005Evan Cheng else if (UnusedValNo) 631a4b2bab23313b1d45e1f3e6c9610a1e83fce4005Evan Cheng ClobberValNo = UnusedValNo; 6320adb527d169e1f557676fda35bc9abb735e5c912Evan Cheng else { 6338651125d2885f74546b6e2a556082111d5b75da3Lang Hames UnusedValNo = ClobberValNo = 634233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames getNextValue(li_.getInvalidIndex(), 0, false, VNInfoAllocator); 6350adb527d169e1f557676fda35bc9abb735e5c912Evan Cheng ValNoMaps.insert(std::make_pair(I->valno, ClobberValNo)); 6360adb527d169e1f557676fda35bc9abb735e5c912Evan Cheng } 6370adb527d169e1f557676fda35bc9abb735e5c912Evan Cheng 63897121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman bool Done = false; 639233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex Start = I->start, End = I->end; 64097121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman // If a clobber range starts before an existing range and ends after 64197121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman // it, the clobber range will need to be split into multiple ranges. 64297121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman // Loop until the entire clobber range is handled. 64397121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman while (!Done) { 64497121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman Done = true; 64597121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman IP = std::upper_bound(IP, end(), Start); 646233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex SubRangeStart = Start; 647233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex SubRangeEnd = End; 64897121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman 64997121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman // If the start of this range overlaps with an existing liverange, trim it. 65097121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman if (IP != begin() && IP[-1].end > SubRangeStart) { 65197121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman SubRangeStart = IP[-1].end; 65297121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman // Trimmed away the whole range? 65397121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman if (SubRangeStart >= SubRangeEnd) continue; 65497121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman } 65597121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman // If the end of this range overlaps with an existing liverange, trim it. 65697121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman if (IP != end() && SubRangeEnd > IP->start) { 65797121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman // If the clobber live range extends beyond the existing live range, 65897121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman // it'll need at least another live range, so set the flag to keep 65997121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman // iterating. 66097121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman if (SubRangeEnd > IP->end) { 66197121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman Start = IP->end; 66297121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman Done = false; 66397121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman } 66497121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman SubRangeEnd = IP->start; 66597121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman // If this trimmed away the whole range, ignore it. 66697121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman if (SubRangeStart == SubRangeEnd) continue; 66797121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman } 66897121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman 66997121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman // Insert the clobber interval. 67097121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman IP = addRangeFrom(LiveRange(SubRangeStart, SubRangeEnd, ClobberValNo), 67197121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman IP); 672a4b2bab23313b1d45e1f3e6c9610a1e83fce4005Evan Cheng UnusedValNo = 0; 673c114b2cad7293d98686d380273085f5c32966b52Chris Lattner } 674c114b2cad7293d98686d380273085f5c32966b52Chris Lattner } 67527e4666c20650f2b10d93b98b7a0625a363df9dfEvan Cheng 67627e4666c20650f2b10d93b98b7a0625a363df9dfEvan Cheng if (UnusedValNo) { 67727e4666c20650f2b10d93b98b7a0625a363df9dfEvan Cheng // Delete the last unused val#. 67827e4666c20650f2b10d93b98b7a0625a363df9dfEvan Cheng valnos.pop_back(); 67927e4666c20650f2b10d93b98b7a0625a363df9dfEvan Cheng } 680c114b2cad7293d98686d380273085f5c32966b52Chris Lattner} 681c114b2cad7293d98686d380273085f5c32966b52Chris Lattner 682233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesvoid LiveInterval::MergeInClobberRange(LiveIntervals &li_, 683233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex Start, 684233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex End, 685991de14dd62dcbab4b31357ae22dc5b053ba50a0Benjamin Kramer VNInfo::Allocator &VNInfoAllocator) { 686a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng // Find a value # to use for the clobber ranges. If there is already a value# 687a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng // for unknown values, use it. 6888651125d2885f74546b6e2a556082111d5b75da3Lang Hames VNInfo *ClobberValNo = 689233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames getNextValue(li_.getInvalidIndex(), 0, false, VNInfoAllocator); 690a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng 691a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng iterator IP = begin(); 692a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng IP = std::upper_bound(IP, end(), Start); 693a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng 694a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng // If the start of this range overlaps with an existing liverange, trim it. 695a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng if (IP != begin() && IP[-1].end > Start) { 696a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng Start = IP[-1].end; 697a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng // Trimmed away the whole range? 698a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng if (Start >= End) return; 699a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng } 700a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng // If the end of this range overlaps with an existing liverange, trim it. 701a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng if (IP != end() && End > IP->start) { 702a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng End = IP->start; 703a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng // If this trimmed away the whole range, ignore it. 704a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng if (Start == End) return; 705a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng } 706a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng 707a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng // Insert the clobber interval. 708a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng addRangeFrom(LiveRange(Start, End, ClobberValNo), IP); 709a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng} 710a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng 711f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// MergeValueNumberInto - This method is called when two value nubmers 712f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// are found to be equivalent. This eliminates V1, replacing all 713f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// LiveRanges with the V1 value number with the V2 value number. This can 714f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// cause merging of V1/V2 values numbers and compaction of the value space. 7155b93f6fa82e33b17d618b3e24da513f547861481Owen AndersonVNInfo* LiveInterval::MergeValueNumberInto(VNInfo *V1, VNInfo *V2) { 716f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner assert(V1 != V2 && "Identical value#'s are always equivalent!"); 717f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 718f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // This code actually merges the (numerically) larger value number into the 719f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // smaller value number, which is likely to allow us to compactify the value 720f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // space. The only thing we have to be careful of is to preserve the 721f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // instruction that defines the result value. 722f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 723f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Make sure V2 is smaller than V1. 7247ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (V1->id < V2->id) { 72552c1afcaea61440950a11a4ccadac4354420d727Lang Hames V1->copyFrom(*V2); 726f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner std::swap(V1, V2); 727f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 728f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 729f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Merge V1 live ranges into V2. 730f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner for (iterator I = begin(); I != end(); ) { 731f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner iterator LR = I++; 7327ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (LR->valno != V1) continue; // Not a V1 LiveRange. 733f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 734f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Okay, we found a V1 live range. If it had a previous, touching, V2 live 735f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // range, extend it. 736f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner if (LR != begin()) { 737f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner iterator Prev = LR-1; 7387ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (Prev->valno == V2 && Prev->end == LR->start) { 739f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner Prev->end = LR->end; 740f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 741f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Erase this live-range. 742f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner ranges.erase(LR); 743f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner I = Prev+1; 744f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner LR = Prev; 745f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 746f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 747f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 748f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Okay, now we have a V1 or V2 live range that is maximally merged forward. 749f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Ensure that it is a V2 live-range. 7507ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LR->valno = V2; 751f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 752f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // If we can merge it into later V2 live ranges, do so now. We ignore any 753f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // following V1 live ranges, as they will be merged in subsequent iterations 754f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // of the loop. 755f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner if (I != end()) { 7567ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (I->start == LR->end && I->valno == V2) { 757f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner LR->end = I->end; 758f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner ranges.erase(I); 759f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner I = LR+1; 760f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 761f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 762f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 763c82b3aab6502a9766ddf42b45faeca3d6fa0ad65Chris Lattner 764c82b3aab6502a9766ddf42b45faeca3d6fa0ad65Chris Lattner // Now that V1 is dead, remove it. If it is the largest value number, just 765c82b3aab6502a9766ddf42b45faeca3d6fa0ad65Chris Lattner // nuke it (and any other deleted values neighboring it), otherwise mark it as 766c82b3aab6502a9766ddf42b45faeca3d6fa0ad65Chris Lattner // ~1U so it can be nuked later. 7677ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (V1->id == getNumValNums()-1) { 768c82b3aab6502a9766ddf42b45faeca3d6fa0ad65Chris Lattner do { 7697ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng valnos.pop_back(); 770857c4e01f85601cf2084adb860616256ee47c177Lang Hames } while (valnos.back()->isUnused()); 771c82b3aab6502a9766ddf42b45faeca3d6fa0ad65Chris Lattner } else { 772857c4e01f85601cf2084adb860616256ee47c177Lang Hames V1->setIsUnused(true); 773c82b3aab6502a9766ddf42b45faeca3d6fa0ad65Chris Lattner } 7745b93f6fa82e33b17d618b3e24da513f547861481Owen Anderson 7755b93f6fa82e33b17d618b3e24da513f547861481Owen Anderson return V2; 776f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner} 777f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 77832dfbeada7292167bb488f36a71a5a6a519ddaffEvan Chengvoid LiveInterval::Copy(const LiveInterval &RHS, 77990f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng MachineRegisterInfo *MRI, 780991de14dd62dcbab4b31357ae22dc5b053ba50a0Benjamin Kramer VNInfo::Allocator &VNInfoAllocator) { 78132dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng ranges.clear(); 78232dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng valnos.clear(); 783358dec51804ee52e47ea3a47c9248086e458ad7cEvan Cheng std::pair<unsigned, unsigned> Hint = MRI->getRegAllocationHint(RHS.reg); 78490f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng MRI->setRegAllocationHint(reg, Hint.first, Hint.second); 78590f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng 78632dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng weight = RHS.weight; 78732dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng for (unsigned i = 0, e = RHS.getNumValNums(); i != e; ++i) { 78832dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng const VNInfo *VNI = RHS.getValNumInfo(i); 789857c4e01f85601cf2084adb860616256ee47c177Lang Hames createValueCopy(VNI, VNInfoAllocator); 79032dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng } 79132dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng for (unsigned i = 0, e = RHS.ranges.size(); i != e; ++i) { 79232dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng const LiveRange &LR = RHS.ranges[i]; 79332dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng addRange(LiveRange(LR.start, LR.end, getValNumInfo(LR.valno->id))); 79432dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng } 79532dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng} 79632dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng 797e52eef8e9a10ada9efc1fed115e5b6eefb22b1daEvan Chengunsigned LiveInterval::getSize() const { 798e52eef8e9a10ada9efc1fed115e5b6eefb22b1daEvan Cheng unsigned Sum = 0; 799e52eef8e9a10ada9efc1fed115e5b6eefb22b1daEvan Cheng for (const_iterator I = begin(), E = end(); I != E; ++I) 8008651125d2885f74546b6e2a556082111d5b75da3Lang Hames Sum += I->start.distance(I->end); 801e52eef8e9a10ada9efc1fed115e5b6eefb22b1daEvan Cheng return Sum; 802e52eef8e9a10ada9efc1fed115e5b6eefb22b1daEvan Cheng} 803e52eef8e9a10ada9efc1fed115e5b6eefb22b1daEvan Cheng 80429ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene/// ComputeJoinedWeight - Set the weight of a live interval Joined 80529ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene/// after Other has been merged into it. 80629ff37f39c305455752941fbf8a426b1f4d877fcDavid Greenevoid LiveInterval::ComputeJoinedWeight(const LiveInterval &Other) { 80729ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene // If either of these intervals was spilled, the weight is the 80829ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene // weight of the non-spilled interval. This can only happen with 80929ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene // iterative coalescers. 81029ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene 81192b78bbc7f2ee919a2d09ed00fd35d1eb7f5f548David Greene if (Other.weight != HUGE_VALF) { 81292b78bbc7f2ee919a2d09ed00fd35d1eb7f5f548David Greene weight += Other.weight; 81392b78bbc7f2ee919a2d09ed00fd35d1eb7f5f548David Greene } 81492b78bbc7f2ee919a2d09ed00fd35d1eb7f5f548David Greene else if (weight == HUGE_VALF && 81529ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene !TargetRegisterInfo::isPhysicalRegister(reg)) { 81629ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene // Remove this assert if you have an iterative coalescer 81729ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene assert(0 && "Joining to spilled interval"); 81829ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene weight = Other.weight; 81929ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene } 82029ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene else { 82129ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene // Otherwise the weight stays the same 82229ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene // Remove this assert if you have an iterative coalescer 82329ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene assert(0 && "Joining from spilled interval"); 82429ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene } 82529ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene} 82629ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene 8271cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbarraw_ostream& llvm::operator<<(raw_ostream& os, const LiveRange &LR) { 8281cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar return os << '[' << LR.start << ',' << LR.end << ':' << LR.valno->id << ")"; 8291cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar} 830abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 831abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattnervoid LiveRange::dump() const { 8325242154b558f0783830938f18153e0a7964fb4faDavid Greene dbgs() << *this << "\n"; 833fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 834fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 835c02497f5bae87e71fd5617db5751cb0b3a14bbedChris Lattnervoid LiveInterval::print(raw_ostream &OS, const TargetRegisterInfo *TRI) const { 83699ec779a93cf7a09ac336b63d2d67818960343a1Evan Cheng if (isStackSlot()) 83799ec779a93cf7a09ac336b63d2d67818960343a1Evan Cheng OS << "SS#" << getStackSlotIndex(); 8383f32d65912b4da23793dab618d981be2ce11c331Evan Cheng else if (TRI && TargetRegisterInfo::isPhysicalRegister(reg)) 839e6d088acc90e422451e098555d383d4d65b6ce6bBill Wendling OS << TRI->getName(reg); 84038135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner else 84138135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner OS << "%reg" << reg; 84238135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner 84338135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner OS << ',' << weight; 84438135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner 84538135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner if (empty()) 8463f32d65912b4da23793dab618d981be2ce11c331Evan Cheng OS << " EMPTY"; 84738135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner else { 84838135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner OS << " = "; 84938135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner for (LiveInterval::Ranges::const_iterator I = ranges.begin(), 850014b8631c0df0c5a91ccee2485bcd408844ed377Jakob Stoklund Olesen E = ranges.end(); I != E; ++I) { 851014b8631c0df0c5a91ccee2485bcd408844ed377Jakob Stoklund Olesen OS << *I; 852014b8631c0df0c5a91ccee2485bcd408844ed377Jakob Stoklund Olesen assert(I->valno == getValNumInfo(I->valno->id) && "Bad VNInfo"); 853014b8631c0df0c5a91ccee2485bcd408844ed377Jakob Stoklund Olesen } 85438135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner } 85515a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen 856be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Print value number info. 8576d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner if (getNumValNums()) { 858be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner OS << " "; 8591a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng unsigned vnum = 0; 8601a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng for (const_vni_iterator i = vni_begin(), e = vni_end(); i != e; 8611a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng ++i, ++vnum) { 8627ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng const VNInfo *vni = *i; 8631a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng if (vnum) OS << " "; 8641a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng OS << vnum << "@"; 865857c4e01f85601cf2084adb860616256ee47c177Lang Hames if (vni->isUnused()) { 8668df786012dc6b875f31ba4152e09c6e0098082eeEvan Cheng OS << "x"; 867be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner } else { 8686194569d22003fddaf1a33acdbb84d5efe76e7d7Lang Hames if (!vni->isDefAccurate() && !vni->isPHIDef()) 8694f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng OS << "?"; 8704f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng else 8717ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng OS << vni->def; 872a8d94f1315f722de056af03763664b77a5baac26Evan Cheng } 873be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner } 874be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner } 875fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 876abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 877abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattnervoid LiveInterval::dump() const { 8785242154b558f0783830938f18153e0a7964fb4faDavid Greene dbgs() << *this << "\n"; 879abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner} 880c21c5eeb4f56f160e79522df2d3aab5cfe73c05dJeff Cohen 881c21c5eeb4f56f160e79522df2d3aab5cfe73c05dJeff Cohen 8821cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbarvoid LiveRange::print(raw_ostream &os) const { 8831cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar os << *this; 8841cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar} 885