LiveInterval.cpp revision a717b7be8886c4c6ae261ee553c5cbcae29c1e52
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 13fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// such that v is live at j' abd there is no instruction with number i' < i such 14fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// that v is live at i'. In this implementation intervals can have holes, 15fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// i.e. an interval might look like [1,20), [50,65), [1000,1001). Each 16fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// individual range is represented as an instance of LiveRange, and the whole 17fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// interval is represented as an instance of LiveInterval. 18fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 19fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner//===----------------------------------------------------------------------===// 20fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 21d9fd2acc1f172e4b8c33c3562667102f9af4d28dBill Wendling#include "llvm/CodeGen/LiveInterval.h" 2290f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng#include "llvm/CodeGen/MachineRegisterInfo.h" 230adb527d169e1f557676fda35bc9abb735e5c912Evan Cheng#include "llvm/ADT/DenseMap.h" 243c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng#include "llvm/ADT/SmallSet.h" 2538b0e7bbf2590f99122a2535d16f34bd12c3bb24Bill Wendling#include "llvm/ADT/STLExtras.h" 26a717b7be8886c4c6ae261ee553c5cbcae29c1e52Daniel Dunbar#include "llvm/Support/raw_ostream.h" 271cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar#include "llvm/Support/raw_ostream.h" 286f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman#include "llvm/Target/TargetRegisterInfo.h" 29c4d3b918165461bc6f5d395bca8d9d9d8a84413dAlkis Evlogimenos#include <algorithm> 30fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattnerusing namespace llvm; 31fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 32fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// An example for liveAt(): 33fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 34aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner// this = [1,4), liveAt(0) will return false. The instruction defining this 35aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner// spans slots [0,3]. The interval belongs to an spilled definition of the 36aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner// variable it represents. This is because slot 1 is used (def slot) and spans 37aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner// up to slot 3 (store slot). 38fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 39ebd7e6c54dce754a88d8f38df4ac2f388f35435eChris Lattnerbool LiveInterval::liveAt(unsigned I) const { 40ebd7e6c54dce754a88d8f38df4ac2f388f35435eChris Lattner Ranges::const_iterator r = std::upper_bound(ranges.begin(), ranges.end(), I); 41edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman 42fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (r == ranges.begin()) 43fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return false; 44fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 45fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner --r; 46aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner return r->contains(I); 47c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng} 48c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng 49c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng// liveBeforeAndAt - Check if the interval is live at the index and the index 50c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng// just before it. If index is liveAt, check if it starts a new live range. 51c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng// If it does, then check if the previous live range ends at index-1. 52c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Chengbool LiveInterval::liveBeforeAndAt(unsigned I) const { 53c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng Ranges::const_iterator r = std::upper_bound(ranges.begin(), ranges.end(), I); 54c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng 55c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (r == ranges.begin()) 56c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return false; 57c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng 58c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng --r; 59c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (!r->contains(I)) 60c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return false; 61c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (I != r->start) 62c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return true; 63c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng // I is the start of a live range. Check if the previous live range ends 64c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng // at I-1. 65c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (r == ranges.begin()) 66c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return false; 67c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return r->end == I; 68fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 69fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 70bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner// overlaps - Return true if the intersection of the two live intervals is 71bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner// not empty. 72bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner// 73fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// An example for overlaps(): 74fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 75fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 0: A = ... 76fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 4: B = ... 77fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 8: C = A + B ;; last use of A 78fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 79fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// The live intervals should look like: 80fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 81fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// A = [3, 11) 82fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// B = [7, x) 83fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// C = [11, y) 84fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 85fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// A->overlaps(C) should return false since we want to be able to join 86fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// A and C. 87bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner// 88bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattnerbool LiveInterval::overlapsFrom(const LiveInterval& other, 89bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner const_iterator StartPos) const { 90bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner const_iterator i = begin(); 91bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner const_iterator ie = end(); 92bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner const_iterator j = StartPos; 93bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner const_iterator je = other.end(); 94bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner 95bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner assert((StartPos->start <= i->start || StartPos == other.begin()) && 968c68b6a226ce46b35eafda972e04bf53128c2615Chris Lattner StartPos != other.end() && "Bogus start position hint!"); 97f542649f1b374b1bae845e4e4f6d1e82f90a9e31Chris Lattner 98fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (i->start < j->start) { 99aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner i = std::upper_bound(i, ie, j->start); 100fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (i != ranges.begin()) --i; 101aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner } else if (j->start < i->start) { 102ead1b3f0bb70cd9c1ba7a853a79070cb47db9344Chris Lattner ++StartPos; 103ead1b3f0bb70cd9c1ba7a853a79070cb47db9344Chris Lattner if (StartPos != other.end() && StartPos->start <= i->start) { 104ead1b3f0bb70cd9c1ba7a853a79070cb47db9344Chris Lattner assert(StartPos < other.end() && i < end()); 1058c68b6a226ce46b35eafda972e04bf53128c2615Chris Lattner j = std::upper_bound(j, je, i->start); 1068c68b6a226ce46b35eafda972e04bf53128c2615Chris Lattner if (j != other.ranges.begin()) --j; 1078c68b6a226ce46b35eafda972e04bf53128c2615Chris Lattner } 108aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner } else { 109aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner return true; 110fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 111fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 1129fddc12c9b16a5526b0ee2e6f1da252f7974d7d0Chris Lattner if (j == je) return false; 1139fddc12c9b16a5526b0ee2e6f1da252f7974d7d0Chris Lattner 1149fddc12c9b16a5526b0ee2e6f1da252f7974d7d0Chris Lattner while (i != ie) { 115fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (i->start > j->start) { 116a1613db62fec94845aa8306232fb665273615badAlkis Evlogimenos std::swap(i, j); 117a1613db62fec94845aa8306232fb665273615badAlkis Evlogimenos std::swap(ie, je); 118fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 119fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 120fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (i->end > j->start) 121fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return true; 122fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner ++i; 123fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 124fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 125fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return false; 126fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 127fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 128cccdb2b602cf421d8890130308945163620ebc68Evan Cheng/// overlaps - Return true if the live interval overlaps a range specified 129cccdb2b602cf421d8890130308945163620ebc68Evan Cheng/// by [Start, End). 130cccdb2b602cf421d8890130308945163620ebc68Evan Chengbool LiveInterval::overlaps(unsigned Start, unsigned End) const { 131cccdb2b602cf421d8890130308945163620ebc68Evan Cheng assert(Start < End && "Invalid range"); 132cccdb2b602cf421d8890130308945163620ebc68Evan Cheng const_iterator I = begin(); 133cccdb2b602cf421d8890130308945163620ebc68Evan Cheng const_iterator E = end(); 134cccdb2b602cf421d8890130308945163620ebc68Evan Cheng const_iterator si = std::upper_bound(I, E, Start); 135cccdb2b602cf421d8890130308945163620ebc68Evan Cheng const_iterator ei = std::upper_bound(I, E, End); 136cccdb2b602cf421d8890130308945163620ebc68Evan Cheng if (si != ei) 137cccdb2b602cf421d8890130308945163620ebc68Evan Cheng return true; 138cccdb2b602cf421d8890130308945163620ebc68Evan Cheng if (si == I) 139cccdb2b602cf421d8890130308945163620ebc68Evan Cheng return false; 140cccdb2b602cf421d8890130308945163620ebc68Evan Cheng --si; 141cccdb2b602cf421d8890130308945163620ebc68Evan Cheng return si->contains(Start); 142cccdb2b602cf421d8890130308945163620ebc68Evan Cheng} 143cccdb2b602cf421d8890130308945163620ebc68Evan Cheng 144b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// extendIntervalEndTo - This method is used when we want to extend the range 145b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// specified by I to end at the specified endpoint. To do this, we should 146b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// merge and eliminate all ranges that this will overlap with. The iterator is 147b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// not invalidated. 148b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattnervoid LiveInterval::extendIntervalEndTo(Ranges::iterator I, unsigned NewEnd) { 149b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner assert(I != ranges.end() && "Not a valid interval!"); 1507ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *ValNo = I->valno; 151430a7b0c94bf9b505aedd9c7d977b43010d6c8f1Evan Cheng unsigned OldEnd = I->end; 152b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 153b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // Search for the first interval that we can't merge with. 154b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner Ranges::iterator MergeTo = next(I); 155abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner for (; MergeTo != ranges.end() && NewEnd >= MergeTo->end; ++MergeTo) { 1567ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng assert(MergeTo->valno == ValNo && "Cannot merge with differing values!"); 157abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 158b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 159b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // If NewEnd was in the middle of an interval, make sure to get its endpoint. 160b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner I->end = std::max(NewEnd, prior(MergeTo)->end); 161b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 162b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner // Erase any dead ranges. 163b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner ranges.erase(next(I), MergeTo); 1644f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng 1654f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng // Update kill info. 166f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng removeKills(ValNo, OldEnd, I->end-1); 1674f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng 168b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner // If the newly formed range now touches the range after it and if they have 169b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner // the same value number, merge the two ranges into one range. 170cef6010c64bc56fa2a8f1e7e9e28b8821adeceacChris Lattner Ranges::iterator Next = next(I); 1717ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (Next != ranges.end() && Next->start <= I->end && Next->valno == ValNo) { 172cef6010c64bc56fa2a8f1e7e9e28b8821adeceacChris Lattner I->end = Next->end; 173cef6010c64bc56fa2a8f1e7e9e28b8821adeceacChris Lattner ranges.erase(Next); 174b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner } 175fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 176fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 177fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 178b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// extendIntervalStartTo - This method is used when we want to extend the range 179b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// specified by I to start at the specified endpoint. To do this, we should 180b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// merge and eliminate all ranges that this will overlap with. 181edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha BrukmanLiveInterval::Ranges::iterator 182b26c215c059d4674bd6a9a8b94da86e497e64844Chris LattnerLiveInterval::extendIntervalStartTo(Ranges::iterator I, unsigned NewStart) { 183b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner assert(I != ranges.end() && "Not a valid interval!"); 1847ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *ValNo = I->valno; 185b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 186b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // Search for the first interval that we can't merge with. 187b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner Ranges::iterator MergeTo = I; 188b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner do { 189b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner if (MergeTo == ranges.begin()) { 190b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner I->start = NewStart; 191abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner ranges.erase(MergeTo, I); 192b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner return I; 193b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner } 1947ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng assert(MergeTo->valno == ValNo && "Cannot merge with differing values!"); 195b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner --MergeTo; 196b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner } while (NewStart <= MergeTo->start); 197b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 198b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // If we start in the middle of another interval, just delete a range and 199b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // extend that interval. 2007ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (MergeTo->end >= NewStart && MergeTo->valno == ValNo) { 201b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner MergeTo->end = I->end; 202b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner } else { 203b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // Otherwise, extend the interval right after. 204b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner ++MergeTo; 205b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner MergeTo->start = NewStart; 206b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner MergeTo->end = I->end; 207fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 208b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 209b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner ranges.erase(next(MergeTo), next(I)); 210b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner return MergeTo; 211fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 212fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 213c114b2cad7293d98686d380273085f5c32966b52Chris LattnerLiveInterval::iterator 214c114b2cad7293d98686d380273085f5c32966b52Chris LattnerLiveInterval::addRangeFrom(LiveRange LR, iterator From) { 215b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner unsigned Start = LR.start, End = LR.end; 216c114b2cad7293d98686d380273085f5c32966b52Chris Lattner iterator it = std::upper_bound(From, ranges.end(), Start); 217b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 218b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // If the inserted interval starts in the middle or right at the end of 219b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // another interval, just extend that interval to contain the range of LR. 220b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner if (it != ranges.begin()) { 221c114b2cad7293d98686d380273085f5c32966b52Chris Lattner iterator B = prior(it); 2227ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (LR.valno == B->valno) { 223abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (B->start <= Start && B->end >= Start) { 224abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner extendIntervalEndTo(B, End); 225abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner return B; 226abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 227abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } else { 228abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // Check to make sure that we are not overlapping two live ranges with 2297ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng // different valno's. 230abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner assert(B->end <= Start && 2318311befb6968a581a3abdce1e13b5d63922662f7Brian Gaeke "Cannot overlap two LiveRanges with differing ValID's" 2328311befb6968a581a3abdce1e13b5d63922662f7Brian Gaeke " (did you def the same reg twice in a MachineInstr?)"); 233b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner } 234fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 235b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 236b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // Otherwise, if this range ends in the middle of, or right next to, another 237b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // interval, merge it into that interval. 2384c71dfe356716e6bc1993ef5efdced08b68fe612Anton Korobeynikov if (it != ranges.end()) { 2397ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (LR.valno == it->valno) { 240abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (it->start <= End) { 241abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner it = extendIntervalStartTo(it, Start); 242abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 243abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // If LR is a complete superset of an interval, we may need to grow its 244abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // endpoint as well. 245abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (End > it->end) 246abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner extendIntervalEndTo(it, End); 247c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng else if (End < it->end) 248c3868e04bf90d55f2599245ee7f3358d7b2a93adEvan Cheng // Overlapping intervals, there might have been a kill here. 249c3868e04bf90d55f2599245ee7f3358d7b2a93adEvan Cheng removeKill(it->valno, End); 250abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner return it; 251abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 252abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } else { 253abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // Check to make sure that we are not overlapping two live ranges with 2547ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng // different valno's. 255abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner assert(it->start >= End && 256abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner "Cannot overlap two LiveRanges with differing ValID's"); 257abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 2584c71dfe356716e6bc1993ef5efdced08b68fe612Anton Korobeynikov } 259b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 260b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // Otherwise, this is just a new range that doesn't interact with anything. 261b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // Insert it. 262b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner return ranges.insert(it, LR); 263fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 264fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 2655a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng/// isInOneLiveRange - Return true if the range specified is entirely in the 2665a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng/// a single LiveRange of the live interval. 2675a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Chengbool LiveInterval::isInOneLiveRange(unsigned Start, unsigned End) { 2685a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng Ranges::iterator I = std::upper_bound(ranges.begin(), ranges.end(), Start); 2695a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng if (I == ranges.begin()) 2705a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng return false; 2715a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng --I; 2725a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng return I->contains(Start) && I->contains(End-1); 2735a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng} 2745a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng 275abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 276abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner/// removeRange - Remove the specified range from this interval. Note that 27742cc6e33ec0f63560c31f1928c56b4b0465d537cEvan Cheng/// the range must be in a single LiveRange in its entirety. 278d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Chengvoid LiveInterval::removeRange(unsigned Start, unsigned End, 279d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng bool RemoveDeadValNo) { 280abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // Find the LiveRange containing this span. 281abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner Ranges::iterator I = std::upper_bound(ranges.begin(), ranges.end(), Start); 282abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner assert(I != ranges.begin() && "Range is not in interval!"); 283abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner --I; 284abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner assert(I->contains(Start) && I->contains(End-1) && 285abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner "Range is not entirely in interval!"); 286abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 287abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // If the span we are removing is at the start of the LiveRange, adjust it. 288d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng VNInfo *ValNo = I->valno; 289abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (I->start == Start) { 2904f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng if (I->end == End) { 291f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng removeKills(I->valno, Start, End); 292d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng if (RemoveDeadValNo) { 293d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng // Check if val# is dead. 294d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng bool isDead = true; 295d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng for (const_iterator II = begin(), EE = end(); II != EE; ++II) 296d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng if (II != I && II->valno == ValNo) { 297d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng isDead = false; 298d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng break; 299d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng } 300d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng if (isDead) { 301d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng // Now that ValNo is dead, remove it. If it is the largest value 302d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng // number, just nuke it (and any other deleted values neighboring it), 303d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng // otherwise mark it as ~1U so it can be nuked later. 304d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng if (ValNo->id == getNumValNums()-1) { 305d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng do { 306d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng VNInfo *VNI = valnos.back(); 307d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng valnos.pop_back(); 308d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng VNI->~VNInfo(); 309857c4e01f85601cf2084adb860616256ee47c177Lang Hames } while (!valnos.empty() && valnos.back()->isUnused()); 310d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng } else { 311857c4e01f85601cf2084adb860616256ee47c177Lang Hames ValNo->setIsUnused(true); 312d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng } 313d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng } 314d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng } 315d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng 316abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner ranges.erase(I); // Removed the whole LiveRange. 3174f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng } else 318abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner I->start = End; 319abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner return; 320abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 321abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 322abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // Otherwise if the span we are removing is at the end of the LiveRange, 323abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // adjust the other way. 324abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (I->end == End) { 325d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng removeKills(ValNo, Start, End); 3266925a9f9cc0b9d34cfbc19d9208c416e293ca516Chris Lattner I->end = Start; 327abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner return; 328abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 329abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 330abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // Otherwise, we are splitting the LiveRange into two pieces. 331abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner unsigned OldEnd = I->end; 332abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner I->end = Start; // Trim the old interval. 333abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 334abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // Insert the new one. 335d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng ranges.insert(next(I), LiveRange(End, OldEnd, ValNo)); 336abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner} 337abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 338d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng/// removeValNo - Remove all the ranges defined by the specified value#. 339d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng/// Also remove the value# from value# list. 340d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Chengvoid LiveInterval::removeValNo(VNInfo *ValNo) { 341d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng if (empty()) return; 342d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng Ranges::iterator I = ranges.end(); 343d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng Ranges::iterator E = ranges.begin(); 344d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng do { 345d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng --I; 346d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng if (I->valno == ValNo) 347d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng ranges.erase(I); 348d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng } while (I != E); 349d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng // Now that ValNo is dead, remove it. If it is the largest value 350d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng // number, just nuke it (and any other deleted values neighboring it), 351d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng // otherwise mark it as ~1U so it can be nuked later. 352d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng if (ValNo->id == getNumValNums()-1) { 353d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng do { 354d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng VNInfo *VNI = valnos.back(); 355d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng valnos.pop_back(); 356d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng VNI->~VNInfo(); 357857c4e01f85601cf2084adb860616256ee47c177Lang Hames } while (!valnos.empty() && valnos.back()->isUnused()); 358d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng } else { 359857c4e01f85601cf2084adb860616256ee47c177Lang Hames ValNo->setIsUnused(true); 360d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng } 361d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng} 362d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng 363f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames/// scaleNumbering - Renumber VNI and ranges to provide gaps for new 364f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames/// instructions. 365f41538d1b54f55e8900394929b50f7ce3e61125fLang Hamesvoid LiveInterval::scaleNumbering(unsigned factor) { 366f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames // Scale ranges. 367f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames for (iterator RI = begin(), RE = end(); RI != RE; ++RI) { 368f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames RI->start = InstrSlots::scale(RI->start, factor); 369f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames RI->end = InstrSlots::scale(RI->end, factor); 370f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames } 371f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames 372f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames // Scale VNI info. 373f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames for (vni_iterator VNI = vni_begin(), VNIE = vni_end(); VNI != VNIE; ++VNI) { 374f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames VNInfo *vni = *VNI; 375857c4e01f85601cf2084adb860616256ee47c177Lang Hames 37698d5982e0020e0c18d2847798ba2f40c4711af5aLang Hames if (vni->isDefAccurate()) 37798d5982e0020e0c18d2847798ba2f40c4711af5aLang Hames vni->def = InstrSlots::scale(vni->def, factor); 378f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames 379f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames for (unsigned i = 0; i < vni->kills.size(); ++i) { 380ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames if (!vni->kills[i].isPHIKill) 381ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames vni->kills[i].killIdx = 382ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames InstrSlots::scale(vni->kills[i].killIdx, factor); 383f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames } 384f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames } 385f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames} 386f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames 387abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner/// getLiveRangeContaining - Return the live range that contains the 388abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner/// specified index, or null if there is none. 389f7da2c7b0c6293c268881628fc351bed7763f1f4Chris LattnerLiveInterval::const_iterator 390f7da2c7b0c6293c268881628fc351bed7763f1f4Chris LattnerLiveInterval::FindLiveRangeContaining(unsigned Idx) const { 391f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner const_iterator It = std::upper_bound(begin(), end(), Idx); 392abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (It != ranges.begin()) { 393f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner --It; 394f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner if (It->contains(Idx)) 395f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner return It; 396abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 397abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 398f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner return end(); 399abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner} 400abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 401f7da2c7b0c6293c268881628fc351bed7763f1f4Chris LattnerLiveInterval::iterator 402f7da2c7b0c6293c268881628fc351bed7763f1f4Chris LattnerLiveInterval::FindLiveRangeContaining(unsigned Idx) { 403f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner iterator It = std::upper_bound(begin(), end(), Idx); 4046d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner if (It != begin()) { 405f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner --It; 406f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner if (It->contains(Idx)) 407f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner return It; 408f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 409f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 410f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner return end(); 411f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner} 412abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 4133f32d65912b4da23793dab618d981be2ce11c331Evan Cheng/// findDefinedVNInfo - Find the VNInfo that's defined at the specified index 4143f32d65912b4da23793dab618d981be2ce11c331Evan Cheng/// (register interval) or defined by the specified register (stack inteval). 4153f32d65912b4da23793dab618d981be2ce11c331Evan ChengVNInfo *LiveInterval::findDefinedVNInfo(unsigned DefIdxOrReg) const { 4163f32d65912b4da23793dab618d981be2ce11c331Evan Cheng VNInfo *VNI = NULL; 4173f32d65912b4da23793dab618d981be2ce11c331Evan Cheng for (LiveInterval::const_vni_iterator i = vni_begin(), e = vni_end(); 4183f32d65912b4da23793dab618d981be2ce11c331Evan Cheng i != e; ++i) 4193f32d65912b4da23793dab618d981be2ce11c331Evan Cheng if ((*i)->def == DefIdxOrReg) { 4203f32d65912b4da23793dab618d981be2ce11c331Evan Cheng VNI = *i; 4213f32d65912b4da23793dab618d981be2ce11c331Evan Cheng break; 4223f32d65912b4da23793dab618d981be2ce11c331Evan Cheng } 4233f32d65912b4da23793dab618d981be2ce11c331Evan Cheng return VNI; 4243f32d65912b4da23793dab618d981be2ce11c331Evan Cheng} 4253f32d65912b4da23793dab618d981be2ce11c331Evan Cheng 4266d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner/// join - Join two live intervals (this, and other) together. This applies 4276d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner/// mappings to the value numbers in the LHS/RHS intervals as specified. If 4286d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner/// the intervals are not joinable, this aborts. 429af992f782fb2cac8d00b352c3dd73f6e782b5758David Greenevoid LiveInterval::join(LiveInterval &Other, const int *LHSValNoAssignments, 430af992f782fb2cac8d00b352c3dd73f6e782b5758David Greene const int *RHSValNoAssignments, 43190f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng SmallVector<VNInfo*, 16> &NewVNInfo, 43290f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng MachineRegisterInfo *MRI) { 4336d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // Determine if any of our live range values are mapped. This is uncommon, so 434343013538f72f2202338f57161c0bd92344ca407Evan Cheng // we want to avoid the interval scan if not. 4356d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner bool MustMapCurValNos = false; 436343013538f72f2202338f57161c0bd92344ca407Evan Cheng unsigned NumVals = getNumValNums(); 437343013538f72f2202338f57161c0bd92344ca407Evan Cheng unsigned NumNewVals = NewVNInfo.size(); 438343013538f72f2202338f57161c0bd92344ca407Evan Cheng for (unsigned i = 0; i != NumVals; ++i) { 439343013538f72f2202338f57161c0bd92344ca407Evan Cheng unsigned LHSValID = LHSValNoAssignments[i]; 440343013538f72f2202338f57161c0bd92344ca407Evan Cheng if (i != LHSValID || 441f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng (NewVNInfo[LHSValID] && NewVNInfo[LHSValID] != getValNumInfo(i))) 4426d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner MustMapCurValNos = true; 4436d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } 4447ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng 4456d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // If we have to apply a mapping to our base interval assignment, rewrite it 4466d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // now. 4476d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner if (MustMapCurValNos) { 4486d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // Map the first live range. 4496d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner iterator OutIt = begin(); 4507ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng OutIt->valno = NewVNInfo[LHSValNoAssignments[OutIt->valno->id]]; 4516d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner ++OutIt; 4526d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner for (iterator I = OutIt, E = end(); I != E; ++I) { 4537ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng OutIt->valno = NewVNInfo[LHSValNoAssignments[I->valno->id]]; 4546d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner 4556d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // If this live range has the same value # as its immediate predecessor, 4566d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // and if they are neighbors, remove one LiveRange. This happens when we 4576d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // have [0,3:0)[4,7:1) and map 0/1 onto the same value #. 4587ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (OutIt->valno == (OutIt-1)->valno && (OutIt-1)->end == OutIt->start) { 4596d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner (OutIt-1)->end = OutIt->end; 4606d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } else { 4616d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner if (I != OutIt) { 4626d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner OutIt->start = I->start; 4636d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner OutIt->end = I->end; 4646d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } 4656d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner 4666d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // Didn't merge, on to the next one. 4676d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner ++OutIt; 4686d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } 4696d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } 4706d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner 4716d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // If we merge some live ranges, chop off the end. 4726d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner ranges.erase(OutIt, end()); 473deb9971061cfb9c57930724fcf8d62fb26dc2213Chris Lattner } 4744f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng 4757ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng // Remember assignements because val# ids are changing. 476343013538f72f2202338f57161c0bd92344ca407Evan Cheng SmallVector<unsigned, 16> OtherAssignments; 4777ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng for (iterator I = Other.begin(), E = Other.end(); I != E; ++I) 4787ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng OtherAssignments.push_back(RHSValNoAssignments[I->valno->id]); 4797ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng 4807ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng // Update val# info. Renumber them and make sure they all belong to this 481f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng // LiveInterval now. Also remove dead val#'s. 482f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng unsigned NumValNos = 0; 483f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng for (unsigned i = 0; i < NumNewVals; ++i) { 484343013538f72f2202338f57161c0bd92344ca407Evan Cheng VNInfo *VNI = NewVNInfo[i]; 485f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng if (VNI) { 48630590f502325321958b35bec7295159e3948291aEvan Cheng if (NumValNos >= NumVals) 487f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng valnos.push_back(VNI); 488f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng else 489f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng valnos[NumValNos] = VNI; 490f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng VNI->id = NumValNos++; // Renumber val#. 491343013538f72f2202338f57161c0bd92344ca407Evan Cheng } 4927ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng } 493343013538f72f2202338f57161c0bd92344ca407Evan Cheng if (NumNewVals < NumVals) 494343013538f72f2202338f57161c0bd92344ca407Evan Cheng valnos.resize(NumNewVals); // shrinkify 4954f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng 4966d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // Okay, now insert the RHS live ranges into the LHS. 497c114b2cad7293d98686d380273085f5c32966b52Chris Lattner iterator InsertPos = begin(); 4987ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng unsigned RangeNo = 0; 4997ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng for (iterator I = Other.begin(), E = Other.end(); I != E; ++I, ++RangeNo) { 5007ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng // Map the valno in the other live range to the current live range. 5017ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng I->valno = NewVNInfo[OtherAssignments[RangeNo]]; 502f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng assert(I->valno && "Adding a dead range?"); 503abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner InsertPos = addRangeFrom(*I, InsertPos); 504abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 5056d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner 50629ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene ComputeJoinedWeight(Other); 50790f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng 50890f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng // Update regalloc hint if currently there isn't one. 50990f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng if (TargetRegisterInfo::isVirtualRegister(reg) && 51090f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng TargetRegisterInfo::isVirtualRegister(Other.reg)) { 511358dec51804ee52e47ea3a47c9248086e458ad7cEvan Cheng std::pair<unsigned, unsigned> Hint = MRI->getRegAllocationHint(reg); 512358dec51804ee52e47ea3a47c9248086e458ad7cEvan Cheng if (Hint.first == 0 && Hint.second == 0) { 513358dec51804ee52e47ea3a47c9248086e458ad7cEvan Cheng std::pair<unsigned, unsigned> OtherHint = 51490f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng MRI->getRegAllocationHint(Other.reg); 515358dec51804ee52e47ea3a47c9248086e458ad7cEvan Cheng if (OtherHint.first || OtherHint.second) 51690f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng MRI->setRegAllocationHint(reg, OtherHint.first, OtherHint.second); 51790f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng } 51890f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng } 519fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 520fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 521f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner/// MergeRangesInAsValue - Merge all of the intervals in RHS into this live 522f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner/// interval as the specified value number. The LiveRanges in RHS are 523f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner/// allowed to overlap with LiveRanges in the current interval, but only if 524f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner/// the overlapping LiveRanges have the specified value number. 525f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattnervoid LiveInterval::MergeRangesInAsValue(const LiveInterval &RHS, 5267ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *LHSValNo) { 527f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // TODO: Make this more efficient. 528f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner iterator InsertPos = begin(); 529f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) { 5307ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng // Map the valno in the other live range to the current live range. 531f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner LiveRange Tmp = *I; 5327ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng Tmp.valno = LHSValNo; 533f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner InsertPos = addRangeFrom(Tmp, InsertPos); 534f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner } 535f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner} 536f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner 537f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner 53832dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng/// MergeValueInAsValue - Merge all of the live ranges of a specific val# 53932dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng/// in RHS into this live interval as the specified value number. 54032dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng/// The LiveRanges in RHS are allowed to overlap with LiveRanges in the 5413c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng/// current interval, it will replace the value numbers of the overlaped 5423c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng/// live ranges with the specified value number. 54332dfbeada7292167bb488f36a71a5a6a519ddaffEvan Chengvoid LiveInterval::MergeValueInAsValue(const LiveInterval &RHS, 54434729256e8058d4106706e9feb2dfad7893502d1Evan Cheng const VNInfo *RHSValNo, VNInfo *LHSValNo) { 5453c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng SmallVector<VNInfo*, 4> ReplacedValNos; 5463c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng iterator IP = begin(); 54732dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) { 54832dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (I->valno != RHSValNo) 54932dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng continue; 5503c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng unsigned Start = I->start, End = I->end; 5513c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng IP = std::upper_bound(IP, end(), Start); 5523c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng // If the start of this range overlaps with an existing liverange, trim it. 5533c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng if (IP != begin() && IP[-1].end > Start) { 554294e6524916aecd874dddeede4cc074d31f5f59fEvan Cheng if (IP[-1].valno != LHSValNo) { 555294e6524916aecd874dddeede4cc074d31f5f59fEvan Cheng ReplacedValNos.push_back(IP[-1].valno); 556294e6524916aecd874dddeede4cc074d31f5f59fEvan Cheng IP[-1].valno = LHSValNo; // Update val#. 5573c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng } 5583c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng Start = IP[-1].end; 5593c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng // Trimmed away the whole range? 5603c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng if (Start >= End) continue; 5613c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng } 5623c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng // If the end of this range overlaps with an existing liverange, trim it. 5633c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng if (IP != end() && End > IP->start) { 5643c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng if (IP->valno != LHSValNo) { 5653c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng ReplacedValNos.push_back(IP->valno); 5663c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng IP->valno = LHSValNo; // Update val#. 5673c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng } 5683c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng End = IP->start; 5693c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng // If this trimmed away the whole range, ignore it. 5703c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng if (Start == End) continue; 5713c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng } 5723c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng 57332dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // Map the valno in the other live range to the current live range. 5743c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng IP = addRangeFrom(LiveRange(Start, End, LHSValNo), IP); 5753c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng } 5763c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng 5773c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng 5783c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng SmallSet<VNInfo*, 4> Seen; 5793c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng for (unsigned i = 0, e = ReplacedValNos.size(); i != e; ++i) { 5803c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng VNInfo *V1 = ReplacedValNos[i]; 5813c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng if (Seen.insert(V1)) { 5823c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng bool isDead = true; 5833c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng for (const_iterator I = begin(), E = end(); I != E; ++I) 5843c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng if (I->valno == V1) { 5853c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng isDead = false; 5863c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng break; 5873c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng } 5883c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng if (isDead) { 5893c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng // Now that V1 is dead, remove it. If it is the largest value number, 5903c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng // just nuke it (and any other deleted values neighboring it), otherwise 5913c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng // mark it as ~1U so it can be nuked later. 5923c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng if (V1->id == getNumValNums()-1) { 5933c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng do { 5943c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng VNInfo *VNI = valnos.back(); 5953c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng valnos.pop_back(); 5963c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng VNI->~VNInfo(); 597857c4e01f85601cf2084adb860616256ee47c177Lang Hames } while (!valnos.empty() && valnos.back()->isUnused()); 5983c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng } else { 599857c4e01f85601cf2084adb860616256ee47c177Lang Hames V1->setIsUnused(true); 6003c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng } 6013c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng } 6023c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng } 60332dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng } 60432dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng} 60532dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng 60632dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng 607c114b2cad7293d98686d380273085f5c32966b52Chris Lattner/// MergeInClobberRanges - For any live ranges that are not defined in the 608c114b2cad7293d98686d380273085f5c32966b52Chris Lattner/// current interval, but are defined in the Clobbers interval, mark them 609c114b2cad7293d98686d380273085f5c32966b52Chris Lattner/// used with an unknown definition value. 610f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Chengvoid LiveInterval::MergeInClobberRanges(const LiveInterval &Clobbers, 611f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng BumpPtrAllocator &VNInfoAllocator) { 612a8c763b3071ae1a58ee8baeb282331245527e004Dan Gohman if (Clobbers.empty()) return; 613c114b2cad7293d98686d380273085f5c32966b52Chris Lattner 6140adb527d169e1f557676fda35bc9abb735e5c912Evan Cheng DenseMap<VNInfo*, VNInfo*> ValNoMaps; 615a4b2bab23313b1d45e1f3e6c9610a1e83fce4005Evan Cheng VNInfo *UnusedValNo = 0; 616c114b2cad7293d98686d380273085f5c32966b52Chris Lattner iterator IP = begin(); 617c114b2cad7293d98686d380273085f5c32966b52Chris Lattner for (const_iterator I = Clobbers.begin(), E = Clobbers.end(); I != E; ++I) { 6180adb527d169e1f557676fda35bc9abb735e5c912Evan Cheng // For every val# in the Clobbers interval, create a new "unknown" val#. 6190adb527d169e1f557676fda35bc9abb735e5c912Evan Cheng VNInfo *ClobberValNo = 0; 6200adb527d169e1f557676fda35bc9abb735e5c912Evan Cheng DenseMap<VNInfo*, VNInfo*>::iterator VI = ValNoMaps.find(I->valno); 6210adb527d169e1f557676fda35bc9abb735e5c912Evan Cheng if (VI != ValNoMaps.end()) 6220adb527d169e1f557676fda35bc9abb735e5c912Evan Cheng ClobberValNo = VI->second; 623a4b2bab23313b1d45e1f3e6c9610a1e83fce4005Evan Cheng else if (UnusedValNo) 624a4b2bab23313b1d45e1f3e6c9610a1e83fce4005Evan Cheng ClobberValNo = UnusedValNo; 6250adb527d169e1f557676fda35bc9abb735e5c912Evan Cheng else { 626857c4e01f85601cf2084adb860616256ee47c177Lang Hames UnusedValNo = ClobberValNo = getNextValue(0, 0, false, VNInfoAllocator); 6270adb527d169e1f557676fda35bc9abb735e5c912Evan Cheng ValNoMaps.insert(std::make_pair(I->valno, ClobberValNo)); 6280adb527d169e1f557676fda35bc9abb735e5c912Evan Cheng } 6290adb527d169e1f557676fda35bc9abb735e5c912Evan Cheng 63097121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman bool Done = false; 631c114b2cad7293d98686d380273085f5c32966b52Chris Lattner unsigned Start = I->start, End = I->end; 63297121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman // If a clobber range starts before an existing range and ends after 63397121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman // it, the clobber range will need to be split into multiple ranges. 63497121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman // Loop until the entire clobber range is handled. 63597121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman while (!Done) { 63697121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman Done = true; 63797121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman IP = std::upper_bound(IP, end(), Start); 63897121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman unsigned SubRangeStart = Start; 63997121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman unsigned SubRangeEnd = End; 64097121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman 64197121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman // If the start of this range overlaps with an existing liverange, trim it. 64297121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman if (IP != begin() && IP[-1].end > SubRangeStart) { 64397121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman SubRangeStart = IP[-1].end; 64497121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman // Trimmed away the whole range? 64597121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman if (SubRangeStart >= SubRangeEnd) continue; 64697121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman } 64797121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman // If the end of this range overlaps with an existing liverange, trim it. 64897121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman if (IP != end() && SubRangeEnd > IP->start) { 64997121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman // If the clobber live range extends beyond the existing live range, 65097121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman // it'll need at least another live range, so set the flag to keep 65197121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman // iterating. 65297121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman if (SubRangeEnd > IP->end) { 65397121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman Start = IP->end; 65497121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman Done = false; 65597121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman } 65697121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman SubRangeEnd = IP->start; 65797121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman // If this trimmed away the whole range, ignore it. 65897121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman if (SubRangeStart == SubRangeEnd) continue; 65997121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman } 66097121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman 66197121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman // Insert the clobber interval. 66297121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman IP = addRangeFrom(LiveRange(SubRangeStart, SubRangeEnd, ClobberValNo), 66397121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman IP); 664a4b2bab23313b1d45e1f3e6c9610a1e83fce4005Evan Cheng UnusedValNo = 0; 665c114b2cad7293d98686d380273085f5c32966b52Chris Lattner } 666c114b2cad7293d98686d380273085f5c32966b52Chris Lattner } 66727e4666c20650f2b10d93b98b7a0625a363df9dfEvan Cheng 66827e4666c20650f2b10d93b98b7a0625a363df9dfEvan Cheng if (UnusedValNo) { 66927e4666c20650f2b10d93b98b7a0625a363df9dfEvan Cheng // Delete the last unused val#. 67027e4666c20650f2b10d93b98b7a0625a363df9dfEvan Cheng valnos.pop_back(); 67127e4666c20650f2b10d93b98b7a0625a363df9dfEvan Cheng UnusedValNo->~VNInfo(); 67227e4666c20650f2b10d93b98b7a0625a363df9dfEvan Cheng } 673c114b2cad7293d98686d380273085f5c32966b52Chris Lattner} 674c114b2cad7293d98686d380273085f5c32966b52Chris Lattner 675a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Chengvoid LiveInterval::MergeInClobberRange(unsigned Start, unsigned End, 676a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng BumpPtrAllocator &VNInfoAllocator) { 677a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng // Find a value # to use for the clobber ranges. If there is already a value# 678a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng // for unknown values, use it. 679857c4e01f85601cf2084adb860616256ee47c177Lang Hames VNInfo *ClobberValNo = getNextValue(0, 0, false, VNInfoAllocator); 680a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng 681a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng iterator IP = begin(); 682a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng IP = std::upper_bound(IP, end(), Start); 683a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng 684a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng // If the start of this range overlaps with an existing liverange, trim it. 685a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng if (IP != begin() && IP[-1].end > Start) { 686a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng Start = IP[-1].end; 687a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng // Trimmed away the whole range? 688a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng if (Start >= End) return; 689a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng } 690a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng // If the end of this range overlaps with an existing liverange, trim it. 691a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng if (IP != end() && End > IP->start) { 692a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng End = IP->start; 693a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng // If this trimmed away the whole range, ignore it. 694a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng if (Start == End) return; 695a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng } 696a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng 697a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng // Insert the clobber interval. 698a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng addRangeFrom(LiveRange(Start, End, ClobberValNo), IP); 699a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng} 700a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng 701f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// MergeValueNumberInto - This method is called when two value nubmers 702f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// are found to be equivalent. This eliminates V1, replacing all 703f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// LiveRanges with the V1 value number with the V2 value number. This can 704f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// cause merging of V1/V2 values numbers and compaction of the value space. 7055b93f6fa82e33b17d618b3e24da513f547861481Owen AndersonVNInfo* LiveInterval::MergeValueNumberInto(VNInfo *V1, VNInfo *V2) { 706f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner assert(V1 != V2 && "Identical value#'s are always equivalent!"); 707f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 708f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // This code actually merges the (numerically) larger value number into the 709f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // smaller value number, which is likely to allow us to compactify the value 710f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // space. The only thing we have to be careful of is to preserve the 711f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // instruction that defines the result value. 712f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 713f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Make sure V2 is smaller than V1. 7147ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (V1->id < V2->id) { 715f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng copyValNumInfo(V1, V2); 716f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner std::swap(V1, V2); 717f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 718f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 719f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Merge V1 live ranges into V2. 720f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner for (iterator I = begin(); I != end(); ) { 721f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner iterator LR = I++; 7227ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (LR->valno != V1) continue; // Not a V1 LiveRange. 723f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 724f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Okay, we found a V1 live range. If it had a previous, touching, V2 live 725f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // range, extend it. 726f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner if (LR != begin()) { 727f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner iterator Prev = LR-1; 7287ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (Prev->valno == V2 && Prev->end == LR->start) { 729f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner Prev->end = LR->end; 730f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 731f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Erase this live-range. 732f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner ranges.erase(LR); 733f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner I = Prev+1; 734f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner LR = Prev; 735f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 736f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 737f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 738f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Okay, now we have a V1 or V2 live range that is maximally merged forward. 739f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Ensure that it is a V2 live-range. 7407ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LR->valno = V2; 741f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 742f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // If we can merge it into later V2 live ranges, do so now. We ignore any 743f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // following V1 live ranges, as they will be merged in subsequent iterations 744f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // of the loop. 745f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner if (I != end()) { 7467ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (I->start == LR->end && I->valno == V2) { 747f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner LR->end = I->end; 748f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner ranges.erase(I); 749f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner I = LR+1; 750f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 751f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 752f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 753c82b3aab6502a9766ddf42b45faeca3d6fa0ad65Chris Lattner 754c82b3aab6502a9766ddf42b45faeca3d6fa0ad65Chris Lattner // Now that V1 is dead, remove it. If it is the largest value number, just 755c82b3aab6502a9766ddf42b45faeca3d6fa0ad65Chris Lattner // nuke it (and any other deleted values neighboring it), otherwise mark it as 756c82b3aab6502a9766ddf42b45faeca3d6fa0ad65Chris Lattner // ~1U so it can be nuked later. 7577ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (V1->id == getNumValNums()-1) { 758c82b3aab6502a9766ddf42b45faeca3d6fa0ad65Chris Lattner do { 759dd199d29b781bc713462f1255b63d3f153bfd9e9Evan Cheng VNInfo *VNI = valnos.back(); 7607ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng valnos.pop_back(); 761dd199d29b781bc713462f1255b63d3f153bfd9e9Evan Cheng VNI->~VNInfo(); 762857c4e01f85601cf2084adb860616256ee47c177Lang Hames } while (valnos.back()->isUnused()); 763c82b3aab6502a9766ddf42b45faeca3d6fa0ad65Chris Lattner } else { 764857c4e01f85601cf2084adb860616256ee47c177Lang Hames V1->setIsUnused(true); 765c82b3aab6502a9766ddf42b45faeca3d6fa0ad65Chris Lattner } 7665b93f6fa82e33b17d618b3e24da513f547861481Owen Anderson 7675b93f6fa82e33b17d618b3e24da513f547861481Owen Anderson return V2; 768f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner} 769f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 77032dfbeada7292167bb488f36a71a5a6a519ddaffEvan Chengvoid LiveInterval::Copy(const LiveInterval &RHS, 77190f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng MachineRegisterInfo *MRI, 77232dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng BumpPtrAllocator &VNInfoAllocator) { 77332dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng ranges.clear(); 77432dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng valnos.clear(); 775358dec51804ee52e47ea3a47c9248086e458ad7cEvan Cheng std::pair<unsigned, unsigned> Hint = MRI->getRegAllocationHint(RHS.reg); 77690f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng MRI->setRegAllocationHint(reg, Hint.first, Hint.second); 77790f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng 77832dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng weight = RHS.weight; 77932dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng for (unsigned i = 0, e = RHS.getNumValNums(); i != e; ++i) { 78032dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng const VNInfo *VNI = RHS.getValNumInfo(i); 781857c4e01f85601cf2084adb860616256ee47c177Lang Hames createValueCopy(VNI, VNInfoAllocator); 78232dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng } 78332dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng for (unsigned i = 0, e = RHS.ranges.size(); i != e; ++i) { 78432dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng const LiveRange &LR = RHS.ranges[i]; 78532dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng addRange(LiveRange(LR.start, LR.end, getValNumInfo(LR.valno->id))); 78632dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng } 78732dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng} 78832dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng 789e52eef8e9a10ada9efc1fed115e5b6eefb22b1daEvan Chengunsigned LiveInterval::getSize() const { 790e52eef8e9a10ada9efc1fed115e5b6eefb22b1daEvan Cheng unsigned Sum = 0; 791e52eef8e9a10ada9efc1fed115e5b6eefb22b1daEvan Cheng for (const_iterator I = begin(), E = end(); I != E; ++I) 792e52eef8e9a10ada9efc1fed115e5b6eefb22b1daEvan Cheng Sum += I->end - I->start; 793e52eef8e9a10ada9efc1fed115e5b6eefb22b1daEvan Cheng return Sum; 794e52eef8e9a10ada9efc1fed115e5b6eefb22b1daEvan Cheng} 795e52eef8e9a10ada9efc1fed115e5b6eefb22b1daEvan Cheng 79629ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene/// ComputeJoinedWeight - Set the weight of a live interval Joined 79729ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene/// after Other has been merged into it. 79829ff37f39c305455752941fbf8a426b1f4d877fcDavid Greenevoid LiveInterval::ComputeJoinedWeight(const LiveInterval &Other) { 79929ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene // If either of these intervals was spilled, the weight is the 80029ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene // weight of the non-spilled interval. This can only happen with 80129ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene // iterative coalescers. 80229ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene 80392b78bbc7f2ee919a2d09ed00fd35d1eb7f5f548David Greene if (Other.weight != HUGE_VALF) { 80492b78bbc7f2ee919a2d09ed00fd35d1eb7f5f548David Greene weight += Other.weight; 80592b78bbc7f2ee919a2d09ed00fd35d1eb7f5f548David Greene } 80692b78bbc7f2ee919a2d09ed00fd35d1eb7f5f548David Greene else if (weight == HUGE_VALF && 80729ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene !TargetRegisterInfo::isPhysicalRegister(reg)) { 80829ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene // Remove this assert if you have an iterative coalescer 80929ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene assert(0 && "Joining to spilled interval"); 81029ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene weight = Other.weight; 81129ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene } 81229ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene else { 81329ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene // Otherwise the weight stays the same 81429ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene // Remove this assert if you have an iterative coalescer 81529ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene assert(0 && "Joining from spilled interval"); 81629ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene } 81729ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene} 81829ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene 819fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattnerstd::ostream& llvm::operator<<(std::ostream& os, const LiveRange &LR) { 8207ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng return os << '[' << LR.start << ',' << LR.end << ':' << LR.valno->id << ")"; 821abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner} 8221cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbarraw_ostream& llvm::operator<<(raw_ostream& os, const LiveRange &LR) { 8231cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar return os << '[' << LR.start << ',' << LR.end << ':' << LR.valno->id << ")"; 8241cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar} 825abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 826abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattnervoid LiveRange::dump() const { 827a717b7be8886c4c6ae261ee553c5cbcae29c1e52Daniel Dunbar errs() << *this << "\n"; 828fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 829fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 8306f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohmanvoid LiveInterval::print(std::ostream &OS, 8316f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman const TargetRegisterInfo *TRI) const { 8321cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar raw_os_ostream RawOS(OS); 8331cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar print(RawOS, TRI); 8341cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar} 8351cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar 8361cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbarvoid LiveInterval::print(raw_ostream &OS, 8371cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar const TargetRegisterInfo *TRI) const { 83899ec779a93cf7a09ac336b63d2d67818960343a1Evan Cheng if (isStackSlot()) 83999ec779a93cf7a09ac336b63d2d67818960343a1Evan Cheng OS << "SS#" << getStackSlotIndex(); 8403f32d65912b4da23793dab618d981be2ce11c331Evan Cheng else if (TRI && TargetRegisterInfo::isPhysicalRegister(reg)) 841e6d088acc90e422451e098555d383d4d65b6ce6bBill Wendling OS << TRI->getName(reg); 84238135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner else 84338135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner OS << "%reg" << reg; 84438135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner 84538135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner OS << ',' << weight; 84638135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner 84738135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner if (empty()) 8483f32d65912b4da23793dab618d981be2ce11c331Evan Cheng OS << " EMPTY"; 84938135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner else { 85038135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner OS << " = "; 85138135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner for (LiveInterval::Ranges::const_iterator I = ranges.begin(), 85238135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner E = ranges.end(); I != E; ++I) 85338135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner OS << *I; 85438135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner } 855be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner 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 { 868857c4e01f85601cf2084adb860616256ee47c177Lang Hames if (!vni->isDefAccurate()) 8694f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng OS << "?"; 8704f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng else 8717ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng OS << vni->def; 8727ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng unsigned ee = vni->kills.size(); 873857c4e01f85601cf2084adb860616256ee47c177Lang Hames if (ee || vni->hasPHIKill()) { 8744f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng OS << "-("; 8751a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng for (unsigned j = 0; j != ee; ++j) { 876ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames OS << vni->kills[j].killIdx; 877ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames if (vni->kills[j].isPHIKill) 878ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames OS << "*"; 8791a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng if (j != ee-1) 8804f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng OS << " "; 8814f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng } 882857c4e01f85601cf2084adb860616256ee47c177Lang Hames if (vni->hasPHIKill()) { 883d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng if (ee) 884d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng OS << " "; 885d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng OS << "phi"; 886d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng } 8874f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng OS << ")"; 8884f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng } 889a8d94f1315f722de056af03763664b77a5baac26Evan Cheng } 890be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner } 891be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner } 892fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 893abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 894abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattnervoid LiveInterval::dump() const { 895a717b7be8886c4c6ae261ee553c5cbcae29c1e52Daniel Dunbar errs() << *this << "\n"; 896abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner} 897c21c5eeb4f56f160e79522df2d3aab5cfe73c05dJeff Cohen 898c21c5eeb4f56f160e79522df2d3aab5cfe73c05dJeff Cohen 8994b607748d86b44cc59e5cf3eee194dfd9b0fcd86Jeff Cohenvoid LiveRange::print(std::ostream &os) const { 9004b607748d86b44cc59e5cf3eee194dfd9b0fcd86Jeff Cohen os << *this; 901c21c5eeb4f56f160e79522df2d3aab5cfe73c05dJeff Cohen} 9021cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbarvoid LiveRange::print(raw_ostream &os) const { 9031cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar os << *this; 9041cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar} 905