Chris Lattner | 78f62e3 | 2004-07-23 17:49:16 +0000 | [diff] [blame] | 1 | //===-- LiveInterval.cpp - Live Interval Representation -------------------===// |
| 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
Chris Lattner | f3ebc3f | 2007-12-29 20:36:04 +0000 | [diff] [blame] | 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
Chris Lattner | 78f62e3 | 2004-07-23 17:49:16 +0000 | [diff] [blame] | 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 10 | // This file implements the LiveRange and LiveInterval classes. Given some |
Chris Lattner | 78f62e3 | 2004-07-23 17:49:16 +0000 | [diff] [blame] | 11 | // numbering of each the machine instructions an interval [i, j) is said to be a |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 12 | // live range for register v if there is no instruction with number j' >= j |
Bob Wilson | 5b56290 | 2010-01-12 22:18:56 +0000 | [diff] [blame] | 13 | // such that v is live at j' and there is no instruction with number i' < i such |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 14 | // that v is live at i'. In this implementation ranges can have holes, |
| 15 | // i.e. a range might look like [1,20), [50,65), [1000,1001). Each |
| 16 | // individual segment is represented as an instance of LiveRange::Segment, |
| 17 | // and the whole range is represented as an instance of LiveRange. |
Chris Lattner | 78f62e3 | 2004-07-23 17:49:16 +0000 | [diff] [blame] | 18 | // |
| 19 | //===----------------------------------------------------------------------===// |
| 20 | |
Bill Wendling | 3f6f0fd | 2006-11-28 02:08:17 +0000 | [diff] [blame] | 21 | #include "llvm/CodeGen/LiveInterval.h" |
Chandler Carruth | ed0881b | 2012-12-03 16:50:05 +0000 | [diff] [blame] | 22 | #include "RegisterCoalescer.h" |
| 23 | #include "llvm/ADT/DenseMap.h" |
| 24 | #include "llvm/ADT/STLExtras.h" |
| 25 | #include "llvm/ADT/SmallSet.h" |
Lang Hames | 05fb963 | 2009-11-03 23:52:08 +0000 | [diff] [blame] | 26 | #include "llvm/CodeGen/LiveIntervalAnalysis.h" |
Evan Cheng | 085caf1 | 2009-06-14 20:22:55 +0000 | [diff] [blame] | 27 | #include "llvm/CodeGen/MachineRegisterInfo.h" |
David Greene | c215532 | 2010-01-04 22:41:43 +0000 | [diff] [blame] | 28 | #include "llvm/Support/Debug.h" |
Daniel Dunbar | f26e740 | 2009-07-24 10:47:20 +0000 | [diff] [blame] | 29 | #include "llvm/Support/raw_ostream.h" |
Dan Gohman | 3a4be0f | 2008-02-10 18:45:23 +0000 | [diff] [blame] | 30 | #include "llvm/Target/TargetRegisterInfo.h" |
Alkis Evlogimenos | fc59e0e | 2004-09-28 02:38:58 +0000 | [diff] [blame] | 31 | #include <algorithm> |
Chris Lattner | 78f62e3 | 2004-07-23 17:49:16 +0000 | [diff] [blame] | 32 | using namespace llvm; |
| 33 | |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 34 | LiveRange::iterator LiveRange::find(SlotIndex Pos) { |
Jakob Stoklund Olesen | dae1dc1 | 2011-03-12 01:50:35 +0000 | [diff] [blame] | 35 | // This algorithm is basically std::upper_bound. |
| 36 | // Unfortunately, std::upper_bound cannot be used with mixed types until we |
| 37 | // adopt C++0x. Many libraries can do it, but not all. |
| 38 | if (empty() || Pos >= endIndex()) |
| 39 | return end(); |
| 40 | iterator I = begin(); |
Matthias Braun | 305ef7f | 2013-09-06 16:44:32 +0000 | [diff] [blame] | 41 | size_t Len = size(); |
Jakob Stoklund Olesen | dae1dc1 | 2011-03-12 01:50:35 +0000 | [diff] [blame] | 42 | do { |
| 43 | size_t Mid = Len >> 1; |
| 44 | if (Pos < I[Mid].end) |
| 45 | Len = Mid; |
| 46 | else |
| 47 | I += Mid + 1, Len -= Mid + 1; |
| 48 | } while (Len); |
| 49 | return I; |
Jakob Stoklund Olesen | 55d738e2 | 2010-06-25 22:53:05 +0000 | [diff] [blame] | 50 | } |
| 51 | |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 52 | VNInfo *LiveRange::createDeadDef(SlotIndex Def, |
| 53 | VNInfo::Allocator &VNInfoAllocator) { |
Jakob Stoklund Olesen | 989b3b1 | 2012-06-05 21:54:09 +0000 | [diff] [blame] | 54 | assert(!Def.isDead() && "Cannot define a value at the dead slot"); |
| 55 | iterator I = find(Def); |
| 56 | if (I == end()) { |
| 57 | VNInfo *VNI = getNextValue(Def, VNInfoAllocator); |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 58 | segments.push_back(Segment(Def, Def.getDeadSlot(), VNI)); |
Jakob Stoklund Olesen | 989b3b1 | 2012-06-05 21:54:09 +0000 | [diff] [blame] | 59 | return VNI; |
| 60 | } |
| 61 | if (SlotIndex::isSameInstr(Def, I->start)) { |
Jakob Stoklund Olesen | 31ebe55 | 2012-11-19 19:31:10 +0000 | [diff] [blame] | 62 | assert(I->valno->def == I->start && "Inconsistent existing value def"); |
| 63 | |
| 64 | // It is possible to have both normal and early-clobber defs of the same |
| 65 | // register on an instruction. It doesn't make a lot of sense, but it is |
| 66 | // possible to specify in inline assembly. |
| 67 | // |
| 68 | // Just convert everything to early-clobber. |
| 69 | Def = std::min(Def, I->start); |
| 70 | if (Def != I->start) |
| 71 | I->start = I->valno->def = Def; |
Jakob Stoklund Olesen | 989b3b1 | 2012-06-05 21:54:09 +0000 | [diff] [blame] | 72 | return I->valno; |
| 73 | } |
| 74 | assert(SlotIndex::isEarlierInstr(Def, I->start) && "Already live at def"); |
| 75 | VNInfo *VNI = getNextValue(Def, VNInfoAllocator); |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 76 | segments.insert(I, Segment(Def, Def.getDeadSlot(), VNI)); |
Jakob Stoklund Olesen | 989b3b1 | 2012-06-05 21:54:09 +0000 | [diff] [blame] | 77 | return VNI; |
| 78 | } |
| 79 | |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 80 | // overlaps - Return true if the intersection of the two live ranges is |
Chris Lattner | cb0c965 | 2004-11-18 03:47:34 +0000 | [diff] [blame] | 81 | // not empty. |
| 82 | // |
Chris Lattner | 78f62e3 | 2004-07-23 17:49:16 +0000 | [diff] [blame] | 83 | // An example for overlaps(): |
| 84 | // |
| 85 | // 0: A = ... |
| 86 | // 4: B = ... |
| 87 | // 8: C = A + B ;; last use of A |
| 88 | // |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 89 | // The live ranges should look like: |
Chris Lattner | 78f62e3 | 2004-07-23 17:49:16 +0000 | [diff] [blame] | 90 | // |
| 91 | // A = [3, 11) |
| 92 | // B = [7, x) |
| 93 | // C = [11, y) |
| 94 | // |
| 95 | // A->overlaps(C) should return false since we want to be able to join |
| 96 | // A and C. |
Chris Lattner | cb0c965 | 2004-11-18 03:47:34 +0000 | [diff] [blame] | 97 | // |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 98 | bool LiveRange::overlapsFrom(const LiveRange& other, |
| 99 | const_iterator StartPos) const { |
| 100 | assert(!empty() && "empty range"); |
Chris Lattner | cb0c965 | 2004-11-18 03:47:34 +0000 | [diff] [blame] | 101 | const_iterator i = begin(); |
| 102 | const_iterator ie = end(); |
| 103 | const_iterator j = StartPos; |
| 104 | const_iterator je = other.end(); |
| 105 | |
| 106 | assert((StartPos->start <= i->start || StartPos == other.begin()) && |
Chris Lattner | 7598c31 | 2004-11-18 04:02:11 +0000 | [diff] [blame] | 107 | StartPos != other.end() && "Bogus start position hint!"); |
Chris Lattner | ccc75d4f | 2004-07-25 07:11:19 +0000 | [diff] [blame] | 108 | |
Chris Lattner | 78f62e3 | 2004-07-23 17:49:16 +0000 | [diff] [blame] | 109 | if (i->start < j->start) { |
Chris Lattner | 2fcc5e4 | 2004-07-23 18:40:00 +0000 | [diff] [blame] | 110 | i = std::upper_bound(i, ie, j->start); |
Matthias Braun | 305ef7f | 2013-09-06 16:44:32 +0000 | [diff] [blame] | 111 | if (i != begin()) --i; |
Chris Lattner | 2fcc5e4 | 2004-07-23 18:40:00 +0000 | [diff] [blame] | 112 | } else if (j->start < i->start) { |
Chris Lattner | 5684f48 | 2004-12-04 01:22:09 +0000 | [diff] [blame] | 113 | ++StartPos; |
| 114 | if (StartPos != other.end() && StartPos->start <= i->start) { |
| 115 | assert(StartPos < other.end() && i < end()); |
Chris Lattner | 7598c31 | 2004-11-18 04:02:11 +0000 | [diff] [blame] | 116 | j = std::upper_bound(j, je, i->start); |
Matthias Braun | 305ef7f | 2013-09-06 16:44:32 +0000 | [diff] [blame] | 117 | if (j != other.begin()) --j; |
Chris Lattner | 7598c31 | 2004-11-18 04:02:11 +0000 | [diff] [blame] | 118 | } |
Chris Lattner | 2fcc5e4 | 2004-07-23 18:40:00 +0000 | [diff] [blame] | 119 | } else { |
| 120 | return true; |
Chris Lattner | 78f62e3 | 2004-07-23 17:49:16 +0000 | [diff] [blame] | 121 | } |
| 122 | |
Chris Lattner | e3b9cb9 | 2004-11-18 05:28:21 +0000 | [diff] [blame] | 123 | if (j == je) return false; |
| 124 | |
| 125 | while (i != ie) { |
Chris Lattner | 78f62e3 | 2004-07-23 17:49:16 +0000 | [diff] [blame] | 126 | if (i->start > j->start) { |
Alkis Evlogimenos | cf72e7f | 2004-07-24 11:44:15 +0000 | [diff] [blame] | 127 | std::swap(i, j); |
| 128 | std::swap(ie, je); |
Chris Lattner | 78f62e3 | 2004-07-23 17:49:16 +0000 | [diff] [blame] | 129 | } |
Chris Lattner | 78f62e3 | 2004-07-23 17:49:16 +0000 | [diff] [blame] | 130 | |
| 131 | if (i->end > j->start) |
| 132 | return true; |
| 133 | ++i; |
| 134 | } |
| 135 | |
| 136 | return false; |
| 137 | } |
| 138 | |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 139 | bool LiveRange::overlaps(const LiveRange &Other, const CoalescerPair &CP, |
| 140 | const SlotIndexes &Indexes) const { |
| 141 | assert(!empty() && "empty range"); |
Jakob Stoklund Olesen | 866908c | 2012-09-06 18:15:23 +0000 | [diff] [blame] | 142 | if (Other.empty()) |
| 143 | return false; |
| 144 | |
| 145 | // Use binary searches to find initial positions. |
| 146 | const_iterator I = find(Other.beginIndex()); |
| 147 | const_iterator IE = end(); |
| 148 | if (I == IE) |
| 149 | return false; |
| 150 | const_iterator J = Other.find(I->start); |
| 151 | const_iterator JE = Other.end(); |
| 152 | if (J == JE) |
| 153 | return false; |
| 154 | |
| 155 | for (;;) { |
| 156 | // J has just been advanced to satisfy: |
| 157 | assert(J->end >= I->start); |
| 158 | // Check for an overlap. |
| 159 | if (J->start < I->end) { |
| 160 | // I and J are overlapping. Find the later start. |
| 161 | SlotIndex Def = std::max(I->start, J->start); |
| 162 | // Allow the overlap if Def is a coalescable copy. |
| 163 | if (Def.isBlock() || |
| 164 | !CP.isCoalescable(Indexes.getInstructionFromIndex(Def))) |
| 165 | return true; |
| 166 | } |
| 167 | // Advance the iterator that ends first to check for more overlaps. |
| 168 | if (J->end > I->end) { |
| 169 | std::swap(I, J); |
| 170 | std::swap(IE, JE); |
| 171 | } |
| 172 | // Advance J until J->end >= I->start. |
| 173 | do |
| 174 | if (++J == JE) |
| 175 | return false; |
| 176 | while (J->end < I->start); |
| 177 | } |
| 178 | } |
| 179 | |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 180 | /// overlaps - Return true if the live range overlaps an interval specified |
Evan Cheng | b685be0 | 2009-04-18 08:52:15 +0000 | [diff] [blame] | 181 | /// by [Start, End). |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 182 | bool LiveRange::overlaps(SlotIndex Start, SlotIndex End) const { |
Evan Cheng | b685be0 | 2009-04-18 08:52:15 +0000 | [diff] [blame] | 183 | assert(Start < End && "Invalid range"); |
Jakob Stoklund Olesen | b43455f | 2010-07-13 19:42:20 +0000 | [diff] [blame] | 184 | const_iterator I = std::lower_bound(begin(), end(), End); |
| 185 | return I != begin() && (--I)->end > Start; |
Evan Cheng | b685be0 | 2009-04-18 08:52:15 +0000 | [diff] [blame] | 186 | } |
| 187 | |
Matthias Braun | e62c207 | 2014-12-10 01:12:06 +0000 | [diff] [blame^] | 188 | bool LiveRange::covers(const LiveRange &Other) const { |
| 189 | if (empty()) |
| 190 | return Other.empty(); |
| 191 | |
| 192 | const_iterator I = begin(); |
| 193 | for (const_iterator O = Other.begin(), OE = Other.end(); O != OE; ++O) { |
| 194 | I = advanceTo(I, O->start); |
| 195 | if (I == end() || I->start > O->start) |
| 196 | return false; |
| 197 | |
| 198 | // Check adjacent live segments and see if we can get behind O->end. |
| 199 | while (I->end < O->end) { |
| 200 | const_iterator Last = I; |
| 201 | // Get next segment and abort if it was not adjacent. |
| 202 | ++I; |
| 203 | if (I == end() || Last->end != I->start) |
| 204 | return false; |
| 205 | } |
| 206 | } |
| 207 | return true; |
| 208 | } |
Lang Hames | 2e3f20b | 2010-07-26 01:49:41 +0000 | [diff] [blame] | 209 | |
| 210 | /// ValNo is dead, remove it. If it is the largest value number, just nuke it |
| 211 | /// (and any other deleted values neighboring it), otherwise mark it as ~1U so |
| 212 | /// it can be nuked later. |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 213 | void LiveRange::markValNoForDeletion(VNInfo *ValNo) { |
Lang Hames | 2e3f20b | 2010-07-26 01:49:41 +0000 | [diff] [blame] | 214 | if (ValNo->id == getNumValNums()-1) { |
| 215 | do { |
| 216 | valnos.pop_back(); |
| 217 | } while (!valnos.empty() && valnos.back()->isUnused()); |
| 218 | } else { |
Jakob Stoklund Olesen | daae19f | 2012-08-03 20:59:32 +0000 | [diff] [blame] | 219 | ValNo->markUnused(); |
Lang Hames | 2e3f20b | 2010-07-26 01:49:41 +0000 | [diff] [blame] | 220 | } |
| 221 | } |
| 222 | |
Jakob Stoklund Olesen | 8c0f693 | 2010-08-06 18:46:59 +0000 | [diff] [blame] | 223 | /// RenumberValues - Renumber all values in order of appearance and delete the |
| 224 | /// remaining unused values. |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 225 | void LiveRange::RenumberValues() { |
Jakob Stoklund Olesen | 8c0f693 | 2010-08-06 18:46:59 +0000 | [diff] [blame] | 226 | SmallPtrSet<VNInfo*, 8> Seen; |
| 227 | valnos.clear(); |
| 228 | for (const_iterator I = begin(), E = end(); I != E; ++I) { |
| 229 | VNInfo *VNI = I->valno; |
David Blaikie | 70573dc | 2014-11-19 07:49:26 +0000 | [diff] [blame] | 230 | if (!Seen.insert(VNI).second) |
Jakob Stoklund Olesen | 8c0f693 | 2010-08-06 18:46:59 +0000 | [diff] [blame] | 231 | continue; |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 232 | assert(!VNI->isUnused() && "Unused valno used by live segment"); |
Jakob Stoklund Olesen | 8c0f693 | 2010-08-06 18:46:59 +0000 | [diff] [blame] | 233 | VNI->id = (unsigned)valnos.size(); |
| 234 | valnos.push_back(VNI); |
| 235 | } |
| 236 | } |
| 237 | |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 238 | /// This method is used when we want to extend the segment specified by I to end |
| 239 | /// at the specified endpoint. To do this, we should merge and eliminate all |
| 240 | /// segments that this will overlap with. The iterator is not invalidated. |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 241 | void LiveRange::extendSegmentEndTo(iterator I, SlotIndex NewEnd) { |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 242 | assert(I != end() && "Not a valid segment!"); |
Evan Cheng | 1ad4a61 | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 243 | VNInfo *ValNo = I->valno; |
Chris Lattner | 78f62e3 | 2004-07-23 17:49:16 +0000 | [diff] [blame] | 244 | |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 245 | // Search for the first segment that we can't merge with. |
Benjamin Kramer | b6d0bd4 | 2014-03-02 12:27:27 +0000 | [diff] [blame] | 246 | iterator MergeTo = std::next(I); |
Matthias Braun | 305ef7f | 2013-09-06 16:44:32 +0000 | [diff] [blame] | 247 | for (; MergeTo != end() && NewEnd >= MergeTo->end; ++MergeTo) { |
Evan Cheng | 1ad4a61 | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 248 | assert(MergeTo->valno == ValNo && "Cannot merge with differing values!"); |
Chris Lattner | 038747f | 2004-07-24 02:52:23 +0000 | [diff] [blame] | 249 | } |
Chris Lattner | b4acba4 | 2004-07-23 19:38:44 +0000 | [diff] [blame] | 250 | |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 251 | // If NewEnd was in the middle of a segment, make sure to get its endpoint. |
Benjamin Kramer | b6d0bd4 | 2014-03-02 12:27:27 +0000 | [diff] [blame] | 252 | I->end = std::max(NewEnd, std::prev(MergeTo)->end); |
Chris Lattner | b4acba4 | 2004-07-23 19:38:44 +0000 | [diff] [blame] | 253 | |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 254 | // If the newly formed segment now touches the segment after it and if they |
| 255 | // have the same value number, merge the two segments into one segment. |
Matthias Braun | 305ef7f | 2013-09-06 16:44:32 +0000 | [diff] [blame] | 256 | if (MergeTo != end() && MergeTo->start <= I->end && |
Chandler Carruth | 1088676 | 2012-07-05 12:40:45 +0000 | [diff] [blame] | 257 | MergeTo->valno == ValNo) { |
| 258 | I->end = MergeTo->end; |
| 259 | ++MergeTo; |
Chris Lattner | 3cf4079 | 2005-10-20 07:39:25 +0000 | [diff] [blame] | 260 | } |
Chandler Carruth | 1088676 | 2012-07-05 12:40:45 +0000 | [diff] [blame] | 261 | |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 262 | // Erase any dead segments. |
Benjamin Kramer | b6d0bd4 | 2014-03-02 12:27:27 +0000 | [diff] [blame] | 263 | segments.erase(std::next(I), MergeTo); |
Chris Lattner | b4acba4 | 2004-07-23 19:38:44 +0000 | [diff] [blame] | 264 | } |
| 265 | |
| 266 | |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 267 | /// This method is used when we want to extend the segment specified by I to |
| 268 | /// start at the specified endpoint. To do this, we should merge and eliminate |
| 269 | /// all segments that this will overlap with. |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 270 | LiveRange::iterator |
| 271 | LiveRange::extendSegmentStartTo(iterator I, SlotIndex NewStart) { |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 272 | assert(I != end() && "Not a valid segment!"); |
Evan Cheng | 1ad4a61 | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 273 | VNInfo *ValNo = I->valno; |
Chris Lattner | b4acba4 | 2004-07-23 19:38:44 +0000 | [diff] [blame] | 274 | |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 275 | // Search for the first segment that we can't merge with. |
Matthias Braun | 305ef7f | 2013-09-06 16:44:32 +0000 | [diff] [blame] | 276 | iterator MergeTo = I; |
Chris Lattner | b4acba4 | 2004-07-23 19:38:44 +0000 | [diff] [blame] | 277 | do { |
Matthias Braun | 305ef7f | 2013-09-06 16:44:32 +0000 | [diff] [blame] | 278 | if (MergeTo == begin()) { |
Chris Lattner | b4acba4 | 2004-07-23 19:38:44 +0000 | [diff] [blame] | 279 | I->start = NewStart; |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 280 | segments.erase(MergeTo, I); |
Chris Lattner | b4acba4 | 2004-07-23 19:38:44 +0000 | [diff] [blame] | 281 | return I; |
| 282 | } |
Evan Cheng | 1ad4a61 | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 283 | assert(MergeTo->valno == ValNo && "Cannot merge with differing values!"); |
Chris Lattner | b4acba4 | 2004-07-23 19:38:44 +0000 | [diff] [blame] | 284 | --MergeTo; |
| 285 | } while (NewStart <= MergeTo->start); |
| 286 | |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 287 | // If we start in the middle of another segment, just delete a range and |
| 288 | // extend that segment. |
Evan Cheng | 1ad4a61 | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 289 | if (MergeTo->end >= NewStart && MergeTo->valno == ValNo) { |
Chris Lattner | b4acba4 | 2004-07-23 19:38:44 +0000 | [diff] [blame] | 290 | MergeTo->end = I->end; |
| 291 | } else { |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 292 | // Otherwise, extend the segment right after. |
Chris Lattner | b4acba4 | 2004-07-23 19:38:44 +0000 | [diff] [blame] | 293 | ++MergeTo; |
| 294 | MergeTo->start = NewStart; |
| 295 | MergeTo->end = I->end; |
| 296 | } |
| 297 | |
Benjamin Kramer | b6d0bd4 | 2014-03-02 12:27:27 +0000 | [diff] [blame] | 298 | segments.erase(std::next(MergeTo), std::next(I)); |
Chris Lattner | b4acba4 | 2004-07-23 19:38:44 +0000 | [diff] [blame] | 299 | return MergeTo; |
| 300 | } |
| 301 | |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 302 | LiveRange::iterator LiveRange::addSegmentFrom(Segment S, iterator From) { |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 303 | SlotIndex Start = S.start, End = S.end; |
Matthias Braun | 305ef7f | 2013-09-06 16:44:32 +0000 | [diff] [blame] | 304 | iterator it = std::upper_bound(From, end(), Start); |
Chris Lattner | b4acba4 | 2004-07-23 19:38:44 +0000 | [diff] [blame] | 305 | |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 306 | // If the inserted segment starts in the middle or right at the end of |
| 307 | // another segment, just extend that segment to contain the segment of S. |
Matthias Braun | 305ef7f | 2013-09-06 16:44:32 +0000 | [diff] [blame] | 308 | if (it != begin()) { |
Benjamin Kramer | b6d0bd4 | 2014-03-02 12:27:27 +0000 | [diff] [blame] | 309 | iterator B = std::prev(it); |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 310 | if (S.valno == B->valno) { |
Chris Lattner | 038747f | 2004-07-24 02:52:23 +0000 | [diff] [blame] | 311 | if (B->start <= Start && B->end >= Start) { |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 312 | extendSegmentEndTo(B, End); |
Chris Lattner | 038747f | 2004-07-24 02:52:23 +0000 | [diff] [blame] | 313 | return B; |
| 314 | } |
| 315 | } else { |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 316 | // Check to make sure that we are not overlapping two live segments with |
Evan Cheng | 1ad4a61 | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 317 | // different valno's. |
Chris Lattner | 038747f | 2004-07-24 02:52:23 +0000 | [diff] [blame] | 318 | assert(B->end <= Start && |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 319 | "Cannot overlap two segments with differing ValID's" |
Brian Gaeke | a057cd2 | 2004-11-16 06:52:35 +0000 | [diff] [blame] | 320 | " (did you def the same reg twice in a MachineInstr?)"); |
Chris Lattner | b4acba4 | 2004-07-23 19:38:44 +0000 | [diff] [blame] | 321 | } |
| 322 | } |
| 323 | |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 324 | // Otherwise, if this segment ends in the middle of, or right next to, another |
| 325 | // segment, merge it into that segment. |
Matthias Braun | 305ef7f | 2013-09-06 16:44:32 +0000 | [diff] [blame] | 326 | if (it != end()) { |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 327 | if (S.valno == it->valno) { |
Chris Lattner | 038747f | 2004-07-24 02:52:23 +0000 | [diff] [blame] | 328 | if (it->start <= End) { |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 329 | it = extendSegmentStartTo(it, Start); |
Chris Lattner | 038747f | 2004-07-24 02:52:23 +0000 | [diff] [blame] | 330 | |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 331 | // If S is a complete superset of a segment, we may need to grow its |
Chris Lattner | 038747f | 2004-07-24 02:52:23 +0000 | [diff] [blame] | 332 | // endpoint as well. |
| 333 | if (End > it->end) |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 334 | extendSegmentEndTo(it, End); |
Chris Lattner | 038747f | 2004-07-24 02:52:23 +0000 | [diff] [blame] | 335 | return it; |
| 336 | } |
| 337 | } else { |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 338 | // Check to make sure that we are not overlapping two live segments with |
Evan Cheng | 1ad4a61 | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 339 | // different valno's. |
Chris Lattner | 038747f | 2004-07-24 02:52:23 +0000 | [diff] [blame] | 340 | assert(it->start >= End && |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 341 | "Cannot overlap two segments with differing ValID's"); |
Chris Lattner | 038747f | 2004-07-24 02:52:23 +0000 | [diff] [blame] | 342 | } |
Anton Korobeynikov | 035eaac | 2008-02-20 11:10:28 +0000 | [diff] [blame] | 343 | } |
Chris Lattner | b4acba4 | 2004-07-23 19:38:44 +0000 | [diff] [blame] | 344 | |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 345 | // Otherwise, this is just a new segment that doesn't interact with anything. |
Chris Lattner | b4acba4 | 2004-07-23 19:38:44 +0000 | [diff] [blame] | 346 | // Insert it. |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 347 | return segments.insert(it, S); |
Chris Lattner | 78f62e3 | 2004-07-23 17:49:16 +0000 | [diff] [blame] | 348 | } |
| 349 | |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 350 | /// extendInBlock - If this range is live before Kill in the basic |
Jakob Stoklund Olesen | 0494c5c | 2011-09-13 16:47:56 +0000 | [diff] [blame] | 351 | /// block that starts at StartIdx, extend it to be live up to Kill and return |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 352 | /// the value. If there is no live range before Kill, return NULL. |
| 353 | VNInfo *LiveRange::extendInBlock(SlotIndex StartIdx, SlotIndex Kill) { |
Jakob Stoklund Olesen | 9e326a8 | 2011-03-02 00:06:15 +0000 | [diff] [blame] | 354 | if (empty()) |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 355 | return nullptr; |
Jakob Stoklund Olesen | 0494c5c | 2011-09-13 16:47:56 +0000 | [diff] [blame] | 356 | iterator I = std::upper_bound(begin(), end(), Kill.getPrevSlot()); |
Jakob Stoklund Olesen | 9e326a8 | 2011-03-02 00:06:15 +0000 | [diff] [blame] | 357 | if (I == begin()) |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 358 | return nullptr; |
Jakob Stoklund Olesen | 9e326a8 | 2011-03-02 00:06:15 +0000 | [diff] [blame] | 359 | --I; |
| 360 | if (I->end <= StartIdx) |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 361 | return nullptr; |
Jakob Stoklund Olesen | 0494c5c | 2011-09-13 16:47:56 +0000 | [diff] [blame] | 362 | if (I->end < Kill) |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 363 | extendSegmentEndTo(I, Kill); |
Jakob Stoklund Olesen | 9e326a8 | 2011-03-02 00:06:15 +0000 | [diff] [blame] | 364 | return I->valno; |
| 365 | } |
Chris Lattner | 038747f | 2004-07-24 02:52:23 +0000 | [diff] [blame] | 366 | |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 367 | /// Remove the specified segment from this range. Note that the segment must |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 368 | /// be in a single Segment in its entirety. |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 369 | void LiveRange::removeSegment(SlotIndex Start, SlotIndex End, |
| 370 | bool RemoveDeadValNo) { |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 371 | // Find the Segment containing this span. |
Matthias Braun | 305ef7f | 2013-09-06 16:44:32 +0000 | [diff] [blame] | 372 | iterator I = find(Start); |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 373 | assert(I != end() && "Segment is not in range!"); |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 374 | assert(I->containsInterval(Start, End) |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 375 | && "Segment is not entirely in range!"); |
Chris Lattner | 038747f | 2004-07-24 02:52:23 +0000 | [diff] [blame] | 376 | |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 377 | // If the span we are removing is at the start of the Segment, adjust it. |
Evan Cheng | 47f462a | 2008-02-13 02:48:26 +0000 | [diff] [blame] | 378 | VNInfo *ValNo = I->valno; |
Chris Lattner | 038747f | 2004-07-24 02:52:23 +0000 | [diff] [blame] | 379 | if (I->start == Start) { |
Evan Cheng | 05cc486 | 2007-08-11 00:59:19 +0000 | [diff] [blame] | 380 | if (I->end == End) { |
Evan Cheng | 47f462a | 2008-02-13 02:48:26 +0000 | [diff] [blame] | 381 | if (RemoveDeadValNo) { |
| 382 | // Check if val# is dead. |
| 383 | bool isDead = true; |
| 384 | for (const_iterator II = begin(), EE = end(); II != EE; ++II) |
| 385 | if (II != I && II->valno == ValNo) { |
| 386 | isDead = false; |
| 387 | break; |
Jakob Stoklund Olesen | 55d738e2 | 2010-06-25 22:53:05 +0000 | [diff] [blame] | 388 | } |
Evan Cheng | 47f462a | 2008-02-13 02:48:26 +0000 | [diff] [blame] | 389 | if (isDead) { |
Lang Hames | 2e3f20b | 2010-07-26 01:49:41 +0000 | [diff] [blame] | 390 | // Now that ValNo is dead, remove it. |
| 391 | markValNoForDeletion(ValNo); |
Evan Cheng | 47f462a | 2008-02-13 02:48:26 +0000 | [diff] [blame] | 392 | } |
| 393 | } |
| 394 | |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 395 | segments.erase(I); // Removed the whole Segment. |
Evan Cheng | 05cc486 | 2007-08-11 00:59:19 +0000 | [diff] [blame] | 396 | } else |
Chris Lattner | 038747f | 2004-07-24 02:52:23 +0000 | [diff] [blame] | 397 | I->start = End; |
| 398 | return; |
| 399 | } |
| 400 | |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 401 | // Otherwise if the span we are removing is at the end of the Segment, |
Chris Lattner | 038747f | 2004-07-24 02:52:23 +0000 | [diff] [blame] | 402 | // adjust the other way. |
| 403 | if (I->end == End) { |
Chris Lattner | af7e898 | 2004-07-25 05:43:53 +0000 | [diff] [blame] | 404 | I->end = Start; |
Chris Lattner | 038747f | 2004-07-24 02:52:23 +0000 | [diff] [blame] | 405 | return; |
| 406 | } |
| 407 | |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 408 | // Otherwise, we are splitting the Segment into two pieces. |
Lang Hames | 05fb963 | 2009-11-03 23:52:08 +0000 | [diff] [blame] | 409 | SlotIndex OldEnd = I->end; |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 410 | I->end = Start; // Trim the old segment. |
Chris Lattner | 038747f | 2004-07-24 02:52:23 +0000 | [diff] [blame] | 411 | |
| 412 | // Insert the new one. |
Benjamin Kramer | b6d0bd4 | 2014-03-02 12:27:27 +0000 | [diff] [blame] | 413 | segments.insert(std::next(I), Segment(End, OldEnd, ValNo)); |
Chris Lattner | 038747f | 2004-07-24 02:52:23 +0000 | [diff] [blame] | 414 | } |
| 415 | |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 416 | /// removeValNo - Remove all the segments defined by the specified value#. |
Evan Cheng | 47f462a | 2008-02-13 02:48:26 +0000 | [diff] [blame] | 417 | /// Also remove the value# from value# list. |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 418 | void LiveRange::removeValNo(VNInfo *ValNo) { |
Evan Cheng | 47f462a | 2008-02-13 02:48:26 +0000 | [diff] [blame] | 419 | if (empty()) return; |
Matthias Braun | 305ef7f | 2013-09-06 16:44:32 +0000 | [diff] [blame] | 420 | iterator I = end(); |
| 421 | iterator E = begin(); |
Evan Cheng | 47f462a | 2008-02-13 02:48:26 +0000 | [diff] [blame] | 422 | do { |
| 423 | --I; |
| 424 | if (I->valno == ValNo) |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 425 | segments.erase(I); |
Evan Cheng | 47f462a | 2008-02-13 02:48:26 +0000 | [diff] [blame] | 426 | } while (I != E); |
Lang Hames | 2e3f20b | 2010-07-26 01:49:41 +0000 | [diff] [blame] | 427 | // Now that ValNo is dead, remove it. |
| 428 | markValNoForDeletion(ValNo); |
Evan Cheng | 47f462a | 2008-02-13 02:48:26 +0000 | [diff] [blame] | 429 | } |
Lang Hames | 3fffe62 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 430 | |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 431 | void LiveRange::join(LiveRange &Other, |
| 432 | const int *LHSValNoAssignments, |
| 433 | const int *RHSValNoAssignments, |
| 434 | SmallVectorImpl<VNInfo *> &NewVNInfo) { |
Chandler Carruth | ac766b9 | 2012-07-10 05:06:03 +0000 | [diff] [blame] | 435 | verify(); |
| 436 | |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 437 | // Determine if any of our values are mapped. This is uncommon, so we want |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 438 | // to avoid the range scan if not. |
Chris Lattner | 34434e9 | 2006-08-29 23:18:15 +0000 | [diff] [blame] | 439 | bool MustMapCurValNos = false; |
Evan Cheng | 2089a21 | 2007-09-01 02:03:17 +0000 | [diff] [blame] | 440 | unsigned NumVals = getNumValNums(); |
| 441 | unsigned NumNewVals = NewVNInfo.size(); |
| 442 | for (unsigned i = 0; i != NumVals; ++i) { |
| 443 | unsigned LHSValID = LHSValNoAssignments[i]; |
| 444 | if (i != LHSValID || |
Lang Hames | 4d04f75 | 2012-02-02 06:55:45 +0000 | [diff] [blame] | 445 | (NewVNInfo[LHSValID] && NewVNInfo[LHSValID] != getValNumInfo(i))) { |
Chris Lattner | 34434e9 | 2006-08-29 23:18:15 +0000 | [diff] [blame] | 446 | MustMapCurValNos = true; |
Lang Hames | 4d04f75 | 2012-02-02 06:55:45 +0000 | [diff] [blame] | 447 | break; |
| 448 | } |
Chris Lattner | d9bbbb8 | 2004-07-24 03:41:50 +0000 | [diff] [blame] | 449 | } |
Evan Cheng | 1ad4a61 | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 450 | |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 451 | // If we have to apply a mapping to our base range assignment, rewrite it now. |
Jakob Stoklund Olesen | 4976d0d | 2012-09-27 21:05:59 +0000 | [diff] [blame] | 452 | if (MustMapCurValNos && !empty()) { |
Chris Lattner | 34434e9 | 2006-08-29 23:18:15 +0000 | [diff] [blame] | 453 | // Map the first live range. |
Lang Hames | 3a20bc3 | 2012-02-02 05:37:34 +0000 | [diff] [blame] | 454 | |
Chris Lattner | 34434e9 | 2006-08-29 23:18:15 +0000 | [diff] [blame] | 455 | iterator OutIt = begin(); |
Evan Cheng | 1ad4a61 | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 456 | OutIt->valno = NewVNInfo[LHSValNoAssignments[OutIt->valno->id]]; |
Benjamin Kramer | b6d0bd4 | 2014-03-02 12:27:27 +0000 | [diff] [blame] | 457 | for (iterator I = std::next(OutIt), E = end(); I != E; ++I) { |
Lang Hames | 3a20bc3 | 2012-02-02 05:37:34 +0000 | [diff] [blame] | 458 | VNInfo* nextValNo = NewVNInfo[LHSValNoAssignments[I->valno->id]]; |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 459 | assert(nextValNo && "Huh?"); |
Jakob Stoklund Olesen | 073cd80 | 2010-08-12 20:01:23 +0000 | [diff] [blame] | 460 | |
Chris Lattner | 34434e9 | 2006-08-29 23:18:15 +0000 | [diff] [blame] | 461 | // If this live range has the same value # as its immediate predecessor, |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 462 | // and if they are neighbors, remove one Segment. This happens when we |
Lang Hames | 3a20bc3 | 2012-02-02 05:37:34 +0000 | [diff] [blame] | 463 | // have [0,4:0)[4,7:1) and map 0/1 onto the same value #. |
| 464 | if (OutIt->valno == nextValNo && OutIt->end == I->start) { |
| 465 | OutIt->end = I->end; |
Chris Lattner | 34434e9 | 2006-08-29 23:18:15 +0000 | [diff] [blame] | 466 | } else { |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 467 | // Didn't merge. Move OutIt to the next segment, |
Lang Hames | 3a20bc3 | 2012-02-02 05:37:34 +0000 | [diff] [blame] | 468 | ++OutIt; |
| 469 | OutIt->valno = nextValNo; |
| 470 | if (OutIt != I) { |
Chris Lattner | 34434e9 | 2006-08-29 23:18:15 +0000 | [diff] [blame] | 471 | OutIt->start = I->start; |
| 472 | OutIt->end = I->end; |
| 473 | } |
Chris Lattner | 34434e9 | 2006-08-29 23:18:15 +0000 | [diff] [blame] | 474 | } |
| 475 | } |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 476 | // If we merge some segments, chop off the end. |
Lang Hames | 3a20bc3 | 2012-02-02 05:37:34 +0000 | [diff] [blame] | 477 | ++OutIt; |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 478 | segments.erase(OutIt, end()); |
Chris Lattner | 34434e9 | 2006-08-29 23:18:15 +0000 | [diff] [blame] | 479 | } |
Evan Cheng | 05cc486 | 2007-08-11 00:59:19 +0000 | [diff] [blame] | 480 | |
Jakob Stoklund Olesen | 1744fd8 | 2013-02-20 23:51:10 +0000 | [diff] [blame] | 481 | // Rewrite Other values before changing the VNInfo ids. |
| 482 | // This can leave Other in an invalid state because we're not coalescing |
| 483 | // touching segments that now have identical values. That's OK since Other is |
| 484 | // not supposed to be valid after calling join(); |
Evan Cheng | 1ad4a61 | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 485 | for (iterator I = Other.begin(), E = Other.end(); I != E; ++I) |
Jakob Stoklund Olesen | 1744fd8 | 2013-02-20 23:51:10 +0000 | [diff] [blame] | 486 | I->valno = NewVNInfo[RHSValNoAssignments[I->valno->id]]; |
Evan Cheng | 1ad4a61 | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 487 | |
| 488 | // Update val# info. Renumber them and make sure they all belong to this |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 489 | // LiveRange now. Also remove dead val#'s. |
Evan Cheng | db53aef | 2007-09-05 21:46:51 +0000 | [diff] [blame] | 490 | unsigned NumValNos = 0; |
| 491 | for (unsigned i = 0; i < NumNewVals; ++i) { |
Evan Cheng | 1ad4a61 | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 492 | VNInfo *VNI = NewVNInfo[i]; |
Evan Cheng | db53aef | 2007-09-05 21:46:51 +0000 | [diff] [blame] | 493 | if (VNI) { |
Evan Cheng | 7e09994 | 2009-04-28 06:24:09 +0000 | [diff] [blame] | 494 | if (NumValNos >= NumVals) |
Evan Cheng | db53aef | 2007-09-05 21:46:51 +0000 | [diff] [blame] | 495 | valnos.push_back(VNI); |
Jakob Stoklund Olesen | 073cd80 | 2010-08-12 20:01:23 +0000 | [diff] [blame] | 496 | else |
Evan Cheng | db53aef | 2007-09-05 21:46:51 +0000 | [diff] [blame] | 497 | valnos[NumValNos] = VNI; |
| 498 | VNI->id = NumValNos++; // Renumber val#. |
Evan Cheng | 2089a21 | 2007-09-01 02:03:17 +0000 | [diff] [blame] | 499 | } |
| 500 | } |
Evan Cheng | 2089a21 | 2007-09-01 02:03:17 +0000 | [diff] [blame] | 501 | if (NumNewVals < NumVals) |
| 502 | valnos.resize(NumNewVals); // shrinkify |
Evan Cheng | 05cc486 | 2007-08-11 00:59:19 +0000 | [diff] [blame] | 503 | |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 504 | // Okay, now insert the RHS live segments into the LHS. |
Jakob Stoklund Olesen | 623d832 | 2013-02-20 18:18:15 +0000 | [diff] [blame] | 505 | LiveRangeUpdater Updater(this); |
Jakob Stoklund Olesen | 1744fd8 | 2013-02-20 23:51:10 +0000 | [diff] [blame] | 506 | for (iterator I = Other.begin(), E = Other.end(); I != E; ++I) |
| 507 | Updater.add(*I); |
Chandler Carruth | e18614d | 2012-07-10 05:16:17 +0000 | [diff] [blame] | 508 | } |
| 509 | |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 510 | /// Merge all of the segments in RHS into this live range as the specified |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 511 | /// value number. The segments in RHS are allowed to overlap with segments in |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 512 | /// the current range, but only if the overlapping segments have the |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 513 | /// specified value number. |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 514 | void LiveRange::MergeSegmentsInAsValue(const LiveRange &RHS, |
| 515 | VNInfo *LHSValNo) { |
Jakob Stoklund Olesen | 623d832 | 2013-02-20 18:18:15 +0000 | [diff] [blame] | 516 | LiveRangeUpdater Updater(this); |
| 517 | for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) |
| 518 | Updater.add(I->start, I->end, LHSValNo); |
Chris Lattner | 5a56d30 | 2006-09-02 05:26:59 +0000 | [diff] [blame] | 519 | } |
| 520 | |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 521 | /// MergeValueInAsValue - Merge all of the live segments of a specific val# |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 522 | /// in RHS into this live range as the specified value number. |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 523 | /// The segments in RHS are allowed to overlap with segments in the |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 524 | /// current range, it will replace the value numbers of the overlaped |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 525 | /// segments with the specified value number. |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 526 | void LiveRange::MergeValueInAsValue(const LiveRange &RHS, |
| 527 | const VNInfo *RHSValNo, |
| 528 | VNInfo *LHSValNo) { |
Jakob Stoklund Olesen | 623d832 | 2013-02-20 18:18:15 +0000 | [diff] [blame] | 529 | LiveRangeUpdater Updater(this); |
| 530 | for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) |
| 531 | if (I->valno == RHSValNo) |
| 532 | Updater.add(I->start, I->end, LHSValNo); |
Evan Cheng | aa2d6ef | 2007-10-12 08:50:34 +0000 | [diff] [blame] | 533 | } |
| 534 | |
Chris Lattner | bdf1210 | 2006-08-24 22:43:55 +0000 | [diff] [blame] | 535 | /// MergeValueNumberInto - This method is called when two value nubmers |
| 536 | /// are found to be equivalent. This eliminates V1, replacing all |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 537 | /// segments with the V1 value number with the V2 value number. This can |
Chris Lattner | bdf1210 | 2006-08-24 22:43:55 +0000 | [diff] [blame] | 538 | /// cause merging of V1/V2 values numbers and compaction of the value space. |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 539 | VNInfo *LiveRange::MergeValueNumberInto(VNInfo *V1, VNInfo *V2) { |
Chris Lattner | bdf1210 | 2006-08-24 22:43:55 +0000 | [diff] [blame] | 540 | assert(V1 != V2 && "Identical value#'s are always equivalent!"); |
| 541 | |
| 542 | // This code actually merges the (numerically) larger value number into the |
| 543 | // smaller value number, which is likely to allow us to compactify the value |
| 544 | // space. The only thing we have to be careful of is to preserve the |
| 545 | // instruction that defines the result value. |
| 546 | |
| 547 | // Make sure V2 is smaller than V1. |
Evan Cheng | 1ad4a61 | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 548 | if (V1->id < V2->id) { |
Lang Hames | 3b90d97 | 2009-08-10 23:43:28 +0000 | [diff] [blame] | 549 | V1->copyFrom(*V2); |
Chris Lattner | bdf1210 | 2006-08-24 22:43:55 +0000 | [diff] [blame] | 550 | std::swap(V1, V2); |
| 551 | } |
| 552 | |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 553 | // Merge V1 segments into V2. |
Chris Lattner | bdf1210 | 2006-08-24 22:43:55 +0000 | [diff] [blame] | 554 | for (iterator I = begin(); I != end(); ) { |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 555 | iterator S = I++; |
| 556 | if (S->valno != V1) continue; // Not a V1 Segment. |
Jakob Stoklund Olesen | 073cd80 | 2010-08-12 20:01:23 +0000 | [diff] [blame] | 557 | |
Chris Lattner | bdf1210 | 2006-08-24 22:43:55 +0000 | [diff] [blame] | 558 | // Okay, we found a V1 live range. If it had a previous, touching, V2 live |
| 559 | // range, extend it. |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 560 | if (S != begin()) { |
| 561 | iterator Prev = S-1; |
| 562 | if (Prev->valno == V2 && Prev->end == S->start) { |
| 563 | Prev->end = S->end; |
Chris Lattner | bdf1210 | 2006-08-24 22:43:55 +0000 | [diff] [blame] | 564 | |
| 565 | // Erase this live-range. |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 566 | segments.erase(S); |
Chris Lattner | bdf1210 | 2006-08-24 22:43:55 +0000 | [diff] [blame] | 567 | I = Prev+1; |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 568 | S = Prev; |
Chris Lattner | bdf1210 | 2006-08-24 22:43:55 +0000 | [diff] [blame] | 569 | } |
| 570 | } |
Jakob Stoklund Olesen | 073cd80 | 2010-08-12 20:01:23 +0000 | [diff] [blame] | 571 | |
Chris Lattner | bdf1210 | 2006-08-24 22:43:55 +0000 | [diff] [blame] | 572 | // Okay, now we have a V1 or V2 live range that is maximally merged forward. |
| 573 | // Ensure that it is a V2 live-range. |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 574 | S->valno = V2; |
Jakob Stoklund Olesen | 073cd80 | 2010-08-12 20:01:23 +0000 | [diff] [blame] | 575 | |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 576 | // If we can merge it into later V2 segments, do so now. We ignore any |
| 577 | // following V1 segments, as they will be merged in subsequent iterations |
Chris Lattner | bdf1210 | 2006-08-24 22:43:55 +0000 | [diff] [blame] | 578 | // of the loop. |
| 579 | if (I != end()) { |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 580 | if (I->start == S->end && I->valno == V2) { |
| 581 | S->end = I->end; |
| 582 | segments.erase(I); |
| 583 | I = S+1; |
Chris Lattner | bdf1210 | 2006-08-24 22:43:55 +0000 | [diff] [blame] | 584 | } |
| 585 | } |
| 586 | } |
Jakob Stoklund Olesen | 073cd80 | 2010-08-12 20:01:23 +0000 | [diff] [blame] | 587 | |
Lang Hames | 2e3f20b | 2010-07-26 01:49:41 +0000 | [diff] [blame] | 588 | // Now that V1 is dead, remove it. |
| 589 | markValNoForDeletion(V1); |
Jakob Stoklund Olesen | 073cd80 | 2010-08-12 20:01:23 +0000 | [diff] [blame] | 590 | |
Owen Anderson | 4eda2cb | 2009-02-02 22:42:01 +0000 | [diff] [blame] | 591 | return V2; |
Chris Lattner | bdf1210 | 2006-08-24 22:43:55 +0000 | [diff] [blame] | 592 | } |
| 593 | |
Evan Cheng | 57b5214 | 2007-04-17 20:25:11 +0000 | [diff] [blame] | 594 | unsigned LiveInterval::getSize() const { |
| 595 | unsigned Sum = 0; |
| 596 | for (const_iterator I = begin(), E = end(); I != E; ++I) |
Lang Hames | 3fffe62 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 597 | Sum += I->start.distance(I->end); |
Evan Cheng | 57b5214 | 2007-04-17 20:25:11 +0000 | [diff] [blame] | 598 | return Sum; |
| 599 | } |
| 600 | |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 601 | raw_ostream& llvm::operator<<(raw_ostream& os, const LiveRange::Segment &S) { |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 602 | return os << '[' << S.start << ',' << S.end << ':' << S.valno->id << ")"; |
Daniel Dunbar | 796e43e | 2009-07-24 10:36:58 +0000 | [diff] [blame] | 603 | } |
Chris Lattner | 78f62e3 | 2004-07-23 17:49:16 +0000 | [diff] [blame] | 604 | |
Manman Ren | 19f49ac | 2012-09-11 22:23:19 +0000 | [diff] [blame] | 605 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 606 | void LiveRange::Segment::dump() const { |
David Greene | c215532 | 2010-01-04 22:41:43 +0000 | [diff] [blame] | 607 | dbgs() << *this << "\n"; |
Chris Lattner | 038747f | 2004-07-24 02:52:23 +0000 | [diff] [blame] | 608 | } |
Manman Ren | 742534c | 2012-09-06 19:06:06 +0000 | [diff] [blame] | 609 | #endif |
Chris Lattner | 038747f | 2004-07-24 02:52:23 +0000 | [diff] [blame] | 610 | |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 611 | void LiveRange::print(raw_ostream &OS) const { |
Chris Lattner | c08d786 | 2005-05-14 05:34:15 +0000 | [diff] [blame] | 612 | if (empty()) |
Jakob Stoklund Olesen | f3f7d6f | 2012-06-05 22:51:54 +0000 | [diff] [blame] | 613 | OS << "EMPTY"; |
Chris Lattner | c08d786 | 2005-05-14 05:34:15 +0000 | [diff] [blame] | 614 | else { |
Matthias Braun | 305ef7f | 2013-09-06 16:44:32 +0000 | [diff] [blame] | 615 | for (const_iterator I = begin(), E = end(); I != E; ++I) { |
Jakob Stoklund Olesen | 731ea71 | 2010-06-23 15:34:36 +0000 | [diff] [blame] | 616 | OS << *I; |
| 617 | assert(I->valno == getValNumInfo(I->valno->id) && "Bad VNInfo"); |
| 618 | } |
Chris Lattner | c08d786 | 2005-05-14 05:34:15 +0000 | [diff] [blame] | 619 | } |
Jakob Stoklund Olesen | 55d738e2 | 2010-06-25 22:53:05 +0000 | [diff] [blame] | 620 | |
Chris Lattner | 2e9f1bc | 2006-08-22 18:19:46 +0000 | [diff] [blame] | 621 | // Print value number info. |
Chris Lattner | 34434e9 | 2006-08-29 23:18:15 +0000 | [diff] [blame] | 622 | if (getNumValNums()) { |
Chris Lattner | 2e9f1bc | 2006-08-22 18:19:46 +0000 | [diff] [blame] | 623 | OS << " "; |
Evan Cheng | a5b10b3 | 2007-08-28 08:28:51 +0000 | [diff] [blame] | 624 | unsigned vnum = 0; |
| 625 | for (const_vni_iterator i = vni_begin(), e = vni_end(); i != e; |
| 626 | ++i, ++vnum) { |
Evan Cheng | 1ad4a61 | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 627 | const VNInfo *vni = *i; |
Evan Cheng | a5b10b3 | 2007-08-28 08:28:51 +0000 | [diff] [blame] | 628 | if (vnum) OS << " "; |
| 629 | OS << vnum << "@"; |
Lang Hames | 16cab19 | 2009-06-17 21:01:20 +0000 | [diff] [blame] | 630 | if (vni->isUnused()) { |
Evan Cheng | a8c2f38 | 2007-08-08 03:00:28 +0000 | [diff] [blame] | 631 | OS << "x"; |
Chris Lattner | 2e9f1bc | 2006-08-22 18:19:46 +0000 | [diff] [blame] | 632 | } else { |
Lang Hames | 5649568 | 2010-09-25 12:04:16 +0000 | [diff] [blame] | 633 | OS << vni->def; |
Jakob Stoklund Olesen | 9a41490 | 2010-10-05 18:48:57 +0000 | [diff] [blame] | 634 | if (vni->isPHIDef()) |
Jakob Stoklund Olesen | 9f565e1 | 2012-08-03 20:19:44 +0000 | [diff] [blame] | 635 | OS << "-phi"; |
Evan Cheng | 0d0fee2 | 2007-08-07 23:49:57 +0000 | [diff] [blame] | 636 | } |
Chris Lattner | 2e9f1bc | 2006-08-22 18:19:46 +0000 | [diff] [blame] | 637 | } |
| 638 | } |
Chris Lattner | 78f62e3 | 2004-07-23 17:49:16 +0000 | [diff] [blame] | 639 | } |
Chris Lattner | 038747f | 2004-07-24 02:52:23 +0000 | [diff] [blame] | 640 | |
Matthias Braun | f6fe6bf | 2013-10-10 21:29:05 +0000 | [diff] [blame] | 641 | void LiveInterval::print(raw_ostream &OS) const { |
| 642 | OS << PrintReg(reg) << ' '; |
| 643 | super::print(OS); |
| 644 | } |
| 645 | |
Manman Ren | 19f49ac | 2012-09-11 22:23:19 +0000 | [diff] [blame] | 646 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 647 | void LiveRange::dump() const { |
David Greene | c215532 | 2010-01-04 22:41:43 +0000 | [diff] [blame] | 648 | dbgs() << *this << "\n"; |
Chris Lattner | 038747f | 2004-07-24 02:52:23 +0000 | [diff] [blame] | 649 | } |
Matthias Braun | f6fe6bf | 2013-10-10 21:29:05 +0000 | [diff] [blame] | 650 | |
| 651 | void LiveInterval::dump() const { |
| 652 | dbgs() << *this << "\n"; |
| 653 | } |
Manman Ren | 742534c | 2012-09-06 19:06:06 +0000 | [diff] [blame] | 654 | #endif |
Jeff Cohen | b82309f | 2006-12-15 22:57:14 +0000 | [diff] [blame] | 655 | |
Chandler Carruth | ac766b9 | 2012-07-10 05:06:03 +0000 | [diff] [blame] | 656 | #ifndef NDEBUG |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 657 | void LiveRange::verify() const { |
Chandler Carruth | ac766b9 | 2012-07-10 05:06:03 +0000 | [diff] [blame] | 658 | for (const_iterator I = begin(), E = end(); I != E; ++I) { |
| 659 | assert(I->start.isValid()); |
| 660 | assert(I->end.isValid()); |
| 661 | assert(I->start < I->end); |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 662 | assert(I->valno != nullptr); |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 663 | assert(I->valno->id < valnos.size()); |
Chandler Carruth | ac766b9 | 2012-07-10 05:06:03 +0000 | [diff] [blame] | 664 | assert(I->valno == valnos[I->valno->id]); |
Benjamin Kramer | b6d0bd4 | 2014-03-02 12:27:27 +0000 | [diff] [blame] | 665 | if (std::next(I) != E) { |
| 666 | assert(I->end <= std::next(I)->start); |
| 667 | if (I->end == std::next(I)->start) |
| 668 | assert(I->valno != std::next(I)->valno); |
Chandler Carruth | ac766b9 | 2012-07-10 05:06:03 +0000 | [diff] [blame] | 669 | } |
| 670 | } |
| 671 | } |
| 672 | #endif |
| 673 | |
Jeff Cohen | b82309f | 2006-12-15 22:57:14 +0000 | [diff] [blame] | 674 | |
Jakob Stoklund Olesen | 521c708 | 2013-02-20 18:18:12 +0000 | [diff] [blame] | 675 | //===----------------------------------------------------------------------===// |
| 676 | // LiveRangeUpdater class |
| 677 | //===----------------------------------------------------------------------===// |
| 678 | // |
| 679 | // The LiveRangeUpdater class always maintains these invariants: |
| 680 | // |
| 681 | // - When LastStart is invalid, Spills is empty and the iterators are invalid. |
| 682 | // This is the initial state, and the state created by flush(). |
| 683 | // In this state, isDirty() returns false. |
| 684 | // |
| 685 | // Otherwise, segments are kept in three separate areas: |
| 686 | // |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 687 | // 1. [begin; WriteI) at the front of LR. |
| 688 | // 2. [ReadI; end) at the back of LR. |
Jakob Stoklund Olesen | 521c708 | 2013-02-20 18:18:12 +0000 | [diff] [blame] | 689 | // 3. Spills. |
| 690 | // |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 691 | // - LR.begin() <= WriteI <= ReadI <= LR.end(). |
Jakob Stoklund Olesen | 521c708 | 2013-02-20 18:18:12 +0000 | [diff] [blame] | 692 | // - Segments in all three areas are fully ordered and coalesced. |
| 693 | // - Segments in area 1 precede and can't coalesce with segments in area 2. |
| 694 | // - Segments in Spills precede and can't coalesce with segments in area 2. |
| 695 | // - No coalescing is possible between segments in Spills and segments in area |
| 696 | // 1, and there are no overlapping segments. |
| 697 | // |
| 698 | // The segments in Spills are not ordered with respect to the segments in area |
| 699 | // 1. They need to be merged. |
| 700 | // |
| 701 | // When they exist, Spills.back().start <= LastStart, |
| 702 | // and WriteI[-1].start <= LastStart. |
| 703 | |
| 704 | void LiveRangeUpdater::print(raw_ostream &OS) const { |
| 705 | if (!isDirty()) { |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 706 | if (LR) |
| 707 | OS << "Clean updater: " << *LR << '\n'; |
Jakob Stoklund Olesen | 521c708 | 2013-02-20 18:18:12 +0000 | [diff] [blame] | 708 | else |
| 709 | OS << "Null updater.\n"; |
| 710 | return; |
| 711 | } |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 712 | assert(LR && "Can't have null LR in dirty updater."); |
| 713 | OS << " updater with gap = " << (ReadI - WriteI) |
Jakob Stoklund Olesen | 521c708 | 2013-02-20 18:18:12 +0000 | [diff] [blame] | 714 | << ", last start = " << LastStart |
| 715 | << ":\n Area 1:"; |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 716 | for (LiveRange::const_iterator I = LR->begin(); I != WriteI; ++I) |
Jakob Stoklund Olesen | 521c708 | 2013-02-20 18:18:12 +0000 | [diff] [blame] | 717 | OS << ' ' << *I; |
| 718 | OS << "\n Spills:"; |
| 719 | for (unsigned I = 0, E = Spills.size(); I != E; ++I) |
| 720 | OS << ' ' << Spills[I]; |
| 721 | OS << "\n Area 2:"; |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 722 | for (LiveRange::const_iterator I = ReadI, E = LR->end(); I != E; ++I) |
Jakob Stoklund Olesen | 521c708 | 2013-02-20 18:18:12 +0000 | [diff] [blame] | 723 | OS << ' ' << *I; |
| 724 | OS << '\n'; |
| 725 | } |
| 726 | |
| 727 | void LiveRangeUpdater::dump() const |
| 728 | { |
| 729 | print(errs()); |
| 730 | } |
| 731 | |
| 732 | // Determine if A and B should be coalesced. |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 733 | static inline bool coalescable(const LiveRange::Segment &A, |
| 734 | const LiveRange::Segment &B) { |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 735 | assert(A.start <= B.start && "Unordered live segments."); |
Jakob Stoklund Olesen | 521c708 | 2013-02-20 18:18:12 +0000 | [diff] [blame] | 736 | if (A.end == B.start) |
| 737 | return A.valno == B.valno; |
| 738 | if (A.end < B.start) |
| 739 | return false; |
| 740 | assert(A.valno == B.valno && "Cannot overlap different values"); |
| 741 | return true; |
| 742 | } |
| 743 | |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 744 | void LiveRangeUpdater::add(LiveRange::Segment Seg) { |
| 745 | assert(LR && "Cannot add to a null destination"); |
Jakob Stoklund Olesen | 521c708 | 2013-02-20 18:18:12 +0000 | [diff] [blame] | 746 | |
| 747 | // Flush the state if Start moves backwards. |
| 748 | if (!LastStart.isValid() || LastStart > Seg.start) { |
| 749 | if (isDirty()) |
| 750 | flush(); |
| 751 | // This brings us to an uninitialized state. Reinitialize. |
| 752 | assert(Spills.empty() && "Leftover spilled segments"); |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 753 | WriteI = ReadI = LR->begin(); |
Jakob Stoklund Olesen | 521c708 | 2013-02-20 18:18:12 +0000 | [diff] [blame] | 754 | } |
| 755 | |
| 756 | // Remember start for next time. |
| 757 | LastStart = Seg.start; |
| 758 | |
| 759 | // Advance ReadI until it ends after Seg.start. |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 760 | LiveRange::iterator E = LR->end(); |
Jakob Stoklund Olesen | 521c708 | 2013-02-20 18:18:12 +0000 | [diff] [blame] | 761 | if (ReadI != E && ReadI->end <= Seg.start) { |
| 762 | // First try to close the gap between WriteI and ReadI with spills. |
| 763 | if (ReadI != WriteI) |
| 764 | mergeSpills(); |
| 765 | // Then advance ReadI. |
| 766 | if (ReadI == WriteI) |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 767 | ReadI = WriteI = LR->find(Seg.start); |
Jakob Stoklund Olesen | 521c708 | 2013-02-20 18:18:12 +0000 | [diff] [blame] | 768 | else |
| 769 | while (ReadI != E && ReadI->end <= Seg.start) |
| 770 | *WriteI++ = *ReadI++; |
| 771 | } |
| 772 | |
| 773 | assert(ReadI == E || ReadI->end > Seg.start); |
| 774 | |
| 775 | // Check if the ReadI segment begins early. |
| 776 | if (ReadI != E && ReadI->start <= Seg.start) { |
| 777 | assert(ReadI->valno == Seg.valno && "Cannot overlap different values"); |
| 778 | // Bail if Seg is completely contained in ReadI. |
| 779 | if (ReadI->end >= Seg.end) |
| 780 | return; |
| 781 | // Coalesce into Seg. |
| 782 | Seg.start = ReadI->start; |
| 783 | ++ReadI; |
| 784 | } |
| 785 | |
| 786 | // Coalesce as much as possible from ReadI into Seg. |
| 787 | while (ReadI != E && coalescable(Seg, *ReadI)) { |
| 788 | Seg.end = std::max(Seg.end, ReadI->end); |
| 789 | ++ReadI; |
| 790 | } |
| 791 | |
| 792 | // Try coalescing Spills.back() into Seg. |
| 793 | if (!Spills.empty() && coalescable(Spills.back(), Seg)) { |
| 794 | Seg.start = Spills.back().start; |
| 795 | Seg.end = std::max(Spills.back().end, Seg.end); |
| 796 | Spills.pop_back(); |
| 797 | } |
| 798 | |
| 799 | // Try coalescing Seg into WriteI[-1]. |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 800 | if (WriteI != LR->begin() && coalescable(WriteI[-1], Seg)) { |
Jakob Stoklund Olesen | 521c708 | 2013-02-20 18:18:12 +0000 | [diff] [blame] | 801 | WriteI[-1].end = std::max(WriteI[-1].end, Seg.end); |
| 802 | return; |
| 803 | } |
| 804 | |
| 805 | // Seg doesn't coalesce with anything, and needs to be inserted somewhere. |
| 806 | if (WriteI != ReadI) { |
| 807 | *WriteI++ = Seg; |
| 808 | return; |
| 809 | } |
| 810 | |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 811 | // Finally, append to LR or Spills. |
Jakob Stoklund Olesen | 521c708 | 2013-02-20 18:18:12 +0000 | [diff] [blame] | 812 | if (WriteI == E) { |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 813 | LR->segments.push_back(Seg); |
| 814 | WriteI = ReadI = LR->end(); |
Jakob Stoklund Olesen | 521c708 | 2013-02-20 18:18:12 +0000 | [diff] [blame] | 815 | } else |
| 816 | Spills.push_back(Seg); |
| 817 | } |
| 818 | |
| 819 | // Merge as many spilled segments as possible into the gap between WriteI |
| 820 | // and ReadI. Advance WriteI to reflect the inserted instructions. |
| 821 | void LiveRangeUpdater::mergeSpills() { |
| 822 | // Perform a backwards merge of Spills and [SpillI;WriteI). |
| 823 | size_t GapSize = ReadI - WriteI; |
| 824 | size_t NumMoved = std::min(Spills.size(), GapSize); |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 825 | LiveRange::iterator Src = WriteI; |
| 826 | LiveRange::iterator Dst = Src + NumMoved; |
| 827 | LiveRange::iterator SpillSrc = Spills.end(); |
| 828 | LiveRange::iterator B = LR->begin(); |
Jakob Stoklund Olesen | 521c708 | 2013-02-20 18:18:12 +0000 | [diff] [blame] | 829 | |
| 830 | // This is the new WriteI position after merging spills. |
| 831 | WriteI = Dst; |
| 832 | |
| 833 | // Now merge Src and Spills backwards. |
| 834 | while (Src != Dst) { |
| 835 | if (Src != B && Src[-1].start > SpillSrc[-1].start) |
| 836 | *--Dst = *--Src; |
| 837 | else |
| 838 | *--Dst = *--SpillSrc; |
| 839 | } |
| 840 | assert(NumMoved == size_t(Spills.end() - SpillSrc)); |
| 841 | Spills.erase(SpillSrc, Spills.end()); |
| 842 | } |
| 843 | |
| 844 | void LiveRangeUpdater::flush() { |
| 845 | if (!isDirty()) |
| 846 | return; |
| 847 | // Clear the dirty state. |
| 848 | LastStart = SlotIndex(); |
| 849 | |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 850 | assert(LR && "Cannot add to a null destination"); |
Jakob Stoklund Olesen | 521c708 | 2013-02-20 18:18:12 +0000 | [diff] [blame] | 851 | |
| 852 | // Nothing to merge? |
| 853 | if (Spills.empty()) { |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 854 | LR->segments.erase(WriteI, ReadI); |
| 855 | LR->verify(); |
Jakob Stoklund Olesen | 521c708 | 2013-02-20 18:18:12 +0000 | [diff] [blame] | 856 | return; |
| 857 | } |
| 858 | |
| 859 | // Resize the WriteI - ReadI gap to match Spills. |
| 860 | size_t GapSize = ReadI - WriteI; |
| 861 | if (GapSize < Spills.size()) { |
| 862 | // The gap is too small. Make some room. |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 863 | size_t WritePos = WriteI - LR->begin(); |
| 864 | LR->segments.insert(ReadI, Spills.size() - GapSize, LiveRange::Segment()); |
Jakob Stoklund Olesen | 521c708 | 2013-02-20 18:18:12 +0000 | [diff] [blame] | 865 | // This also invalidated ReadI, but it is recomputed below. |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 866 | WriteI = LR->begin() + WritePos; |
Jakob Stoklund Olesen | 521c708 | 2013-02-20 18:18:12 +0000 | [diff] [blame] | 867 | } else { |
| 868 | // Shrink the gap if necessary. |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 869 | LR->segments.erase(WriteI + Spills.size(), ReadI); |
Jakob Stoklund Olesen | 521c708 | 2013-02-20 18:18:12 +0000 | [diff] [blame] | 870 | } |
| 871 | ReadI = WriteI + Spills.size(); |
| 872 | mergeSpills(); |
Matthias Braun | d7df935 | 2013-10-10 21:28:47 +0000 | [diff] [blame] | 873 | LR->verify(); |
Jakob Stoklund Olesen | 521c708 | 2013-02-20 18:18:12 +0000 | [diff] [blame] | 874 | } |
| 875 | |
Jakob Stoklund Olesen | 0f1677e | 2010-10-07 23:34:34 +0000 | [diff] [blame] | 876 | unsigned ConnectedVNInfoEqClasses::Classify(const LiveInterval *LI) { |
Jakob Stoklund Olesen | 05cae83 | 2010-10-08 21:19:28 +0000 | [diff] [blame] | 877 | // Create initial equivalence classes. |
Jakob Stoklund Olesen | 315b42c | 2011-03-17 00:23:45 +0000 | [diff] [blame] | 878 | EqClass.clear(); |
| 879 | EqClass.grow(LI->getNumValNums()); |
Jakob Stoklund Olesen | 05cae83 | 2010-10-08 21:19:28 +0000 | [diff] [blame] | 880 | |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 881 | const VNInfo *used = nullptr, *unused = nullptr; |
Jakob Stoklund Olesen | dff6a6e | 2010-10-29 17:37:29 +0000 | [diff] [blame] | 882 | |
Jakob Stoklund Olesen | 05cae83 | 2010-10-08 21:19:28 +0000 | [diff] [blame] | 883 | // Determine connections. |
Jakob Stoklund Olesen | 0f1677e | 2010-10-07 23:34:34 +0000 | [diff] [blame] | 884 | for (LiveInterval::const_vni_iterator I = LI->vni_begin(), E = LI->vni_end(); |
| 885 | I != E; ++I) { |
| 886 | const VNInfo *VNI = *I; |
Jakob Stoklund Olesen | dff6a6e | 2010-10-29 17:37:29 +0000 | [diff] [blame] | 887 | // Group all unused values into one class. |
| 888 | if (VNI->isUnused()) { |
| 889 | if (unused) |
Jakob Stoklund Olesen | 315b42c | 2011-03-17 00:23:45 +0000 | [diff] [blame] | 890 | EqClass.join(unused->id, VNI->id); |
Jakob Stoklund Olesen | dff6a6e | 2010-10-29 17:37:29 +0000 | [diff] [blame] | 891 | unused = VNI; |
| 892 | continue; |
| 893 | } |
| 894 | used = VNI; |
Jakob Stoklund Olesen | 0f1677e | 2010-10-07 23:34:34 +0000 | [diff] [blame] | 895 | if (VNI->isPHIDef()) { |
Jakob Stoklund Olesen | 315b42c | 2011-03-17 00:23:45 +0000 | [diff] [blame] | 896 | const MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def); |
Jakob Stoklund Olesen | 0f1677e | 2010-10-07 23:34:34 +0000 | [diff] [blame] | 897 | assert(MBB && "Phi-def has no defining MBB"); |
| 898 | // Connect to values live out of predecessors. |
| 899 | for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), |
| 900 | PE = MBB->pred_end(); PI != PE; ++PI) |
Jakob Stoklund Olesen | d7bcf43 | 2011-11-14 01:39:36 +0000 | [diff] [blame] | 901 | if (const VNInfo *PVNI = LI->getVNInfoBefore(LIS.getMBBEndIdx(*PI))) |
Jakob Stoklund Olesen | 315b42c | 2011-03-17 00:23:45 +0000 | [diff] [blame] | 902 | EqClass.join(VNI->id, PVNI->id); |
Jakob Stoklund Olesen | 0f1677e | 2010-10-07 23:34:34 +0000 | [diff] [blame] | 903 | } else { |
| 904 | // Normal value defined by an instruction. Check for two-addr redef. |
| 905 | // FIXME: This could be coincidental. Should we really check for a tied |
| 906 | // operand constraint? |
Jakob Stoklund Olesen | 4c278f8 | 2010-12-21 00:48:17 +0000 | [diff] [blame] | 907 | // Note that VNI->def may be a use slot for an early clobber def. |
Jakob Stoklund Olesen | d7bcf43 | 2011-11-14 01:39:36 +0000 | [diff] [blame] | 908 | if (const VNInfo *UVNI = LI->getVNInfoBefore(VNI->def)) |
Jakob Stoklund Olesen | 315b42c | 2011-03-17 00:23:45 +0000 | [diff] [blame] | 909 | EqClass.join(VNI->id, UVNI->id); |
Jakob Stoklund Olesen | 0f1677e | 2010-10-07 23:34:34 +0000 | [diff] [blame] | 910 | } |
| 911 | } |
Jakob Stoklund Olesen | dff6a6e | 2010-10-29 17:37:29 +0000 | [diff] [blame] | 912 | |
| 913 | // Lump all the unused values in with the last used value. |
| 914 | if (used && unused) |
Jakob Stoklund Olesen | 315b42c | 2011-03-17 00:23:45 +0000 | [diff] [blame] | 915 | EqClass.join(used->id, unused->id); |
Jakob Stoklund Olesen | dff6a6e | 2010-10-29 17:37:29 +0000 | [diff] [blame] | 916 | |
Jakob Stoklund Olesen | 315b42c | 2011-03-17 00:23:45 +0000 | [diff] [blame] | 917 | EqClass.compress(); |
| 918 | return EqClass.getNumClasses(); |
Jakob Stoklund Olesen | 0f1677e | 2010-10-07 23:34:34 +0000 | [diff] [blame] | 919 | } |
| 920 | |
Jakob Stoklund Olesen | 315b42c | 2011-03-17 00:23:45 +0000 | [diff] [blame] | 921 | void ConnectedVNInfoEqClasses::Distribute(LiveInterval *LIV[], |
| 922 | MachineRegisterInfo &MRI) { |
Jakob Stoklund Olesen | 0f1677e | 2010-10-07 23:34:34 +0000 | [diff] [blame] | 923 | assert(LIV[0] && "LIV[0] must be set"); |
| 924 | LiveInterval &LI = *LIV[0]; |
Jakob Stoklund Olesen | 0f1677e | 2010-10-07 23:34:34 +0000 | [diff] [blame] | 925 | |
Jakob Stoklund Olesen | 315b42c | 2011-03-17 00:23:45 +0000 | [diff] [blame] | 926 | // Rewrite instructions. |
| 927 | for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(LI.reg), |
| 928 | RE = MRI.reg_end(); RI != RE;) { |
Owen Anderson | 16c6bf4 | 2014-03-13 23:12:04 +0000 | [diff] [blame] | 929 | MachineOperand &MO = *RI; |
| 930 | MachineInstr *MI = RI->getParent(); |
Jakob Stoklund Olesen | 315b42c | 2011-03-17 00:23:45 +0000 | [diff] [blame] | 931 | ++RI; |
Jakob Stoklund Olesen | 43711c5 | 2013-05-23 17:02:23 +0000 | [diff] [blame] | 932 | // DBG_VALUE instructions don't have slot indexes, so get the index of the |
| 933 | // instruction before them. |
| 934 | // Normally, DBG_VALUE instructions are removed before this function is |
| 935 | // called, but it is not a requirement. |
| 936 | SlotIndex Idx; |
| 937 | if (MI->isDebugValue()) |
| 938 | Idx = LIS.getSlotIndexes()->getIndexBefore(MI); |
| 939 | else |
| 940 | Idx = LIS.getInstructionIndex(MI); |
Matthias Braun | 88dd0ab | 2013-10-10 21:28:52 +0000 | [diff] [blame] | 941 | LiveQueryResult LRQ = LI.Query(Idx); |
Jakob Stoklund Olesen | cef9a61 | 2012-07-25 17:15:15 +0000 | [diff] [blame] | 942 | const VNInfo *VNI = MO.readsReg() ? LRQ.valueIn() : LRQ.valueDefined(); |
| 943 | // In the case of an <undef> use that isn't tied to any def, VNI will be |
| 944 | // NULL. If the use is tied to a def, VNI will be the defined value. |
Jakob Stoklund Olesen | 82d77e8 | 2012-05-19 05:25:50 +0000 | [diff] [blame] | 945 | if (!VNI) |
| 946 | continue; |
Jakob Stoklund Olesen | 315b42c | 2011-03-17 00:23:45 +0000 | [diff] [blame] | 947 | MO.setReg(LIV[getEqClass(VNI)]->reg); |
| 948 | } |
| 949 | |
| 950 | // Move runs to new intervals. |
Jakob Stoklund Olesen | 0f1677e | 2010-10-07 23:34:34 +0000 | [diff] [blame] | 951 | LiveInterval::iterator J = LI.begin(), E = LI.end(); |
Jakob Stoklund Olesen | 315b42c | 2011-03-17 00:23:45 +0000 | [diff] [blame] | 952 | while (J != E && EqClass[J->valno->id] == 0) |
Jakob Stoklund Olesen | 0f1677e | 2010-10-07 23:34:34 +0000 | [diff] [blame] | 953 | ++J; |
| 954 | for (LiveInterval::iterator I = J; I != E; ++I) { |
Jakob Stoklund Olesen | 315b42c | 2011-03-17 00:23:45 +0000 | [diff] [blame] | 955 | if (unsigned eq = EqClass[I->valno->id]) { |
Benjamin Kramer | d84bb16 | 2010-10-09 16:36:44 +0000 | [diff] [blame] | 956 | assert((LIV[eq]->empty() || LIV[eq]->expiredAt(I->start)) && |
Jakob Stoklund Olesen | 0f1677e | 2010-10-07 23:34:34 +0000 | [diff] [blame] | 957 | "New intervals should be empty"); |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 958 | LIV[eq]->segments.push_back(*I); |
Jakob Stoklund Olesen | 0f1677e | 2010-10-07 23:34:34 +0000 | [diff] [blame] | 959 | } else |
| 960 | *J++ = *I; |
| 961 | } |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 962 | LI.segments.erase(J, E); |
Jakob Stoklund Olesen | 0f1677e | 2010-10-07 23:34:34 +0000 | [diff] [blame] | 963 | |
| 964 | // Transfer VNInfos to their new owners and renumber them. |
| 965 | unsigned j = 0, e = LI.getNumValNums(); |
Jakob Stoklund Olesen | 315b42c | 2011-03-17 00:23:45 +0000 | [diff] [blame] | 966 | while (j != e && EqClass[j] == 0) |
Jakob Stoklund Olesen | 0f1677e | 2010-10-07 23:34:34 +0000 | [diff] [blame] | 967 | ++j; |
| 968 | for (unsigned i = j; i != e; ++i) { |
| 969 | VNInfo *VNI = LI.getValNumInfo(i); |
Jakob Stoklund Olesen | 315b42c | 2011-03-17 00:23:45 +0000 | [diff] [blame] | 970 | if (unsigned eq = EqClass[i]) { |
Jakob Stoklund Olesen | 0f1677e | 2010-10-07 23:34:34 +0000 | [diff] [blame] | 971 | VNI->id = LIV[eq]->getNumValNums(); |
| 972 | LIV[eq]->valnos.push_back(VNI); |
| 973 | } else { |
| 974 | VNI->id = j; |
| 975 | LI.valnos[j++] = VNI; |
| 976 | } |
| 977 | } |
| 978 | LI.valnos.resize(j); |
| 979 | } |