File: | lib/CodeGen/LiveInterval.cpp |
Location: | line 1014, column 19 |
Description: | The left operand of '==' is a garbage value |
1 | //===-- LiveInterval.cpp - Live Interval Representation -------------------===// | |||
2 | // | |||
3 | // The LLVM Compiler Infrastructure | |||
4 | // | |||
5 | // This file is distributed under the University of Illinois Open Source | |||
6 | // License. See LICENSE.TXT for details. | |||
7 | // | |||
8 | //===----------------------------------------------------------------------===// | |||
9 | // | |||
10 | // This file implements the LiveRange and LiveInterval classes. Given some | |||
11 | // numbering of each the machine instructions an interval [i, j) is said to be a | |||
12 | // live range for register v if there is no instruction with number j' >= j | |||
13 | // such that v is live at j' and there is no instruction with number i' < i such | |||
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. | |||
18 | // | |||
19 | //===----------------------------------------------------------------------===// | |||
20 | ||||
21 | #include "llvm/CodeGen/LiveInterval.h" | |||
22 | ||||
23 | #include "PHIEliminationUtils.h" | |||
24 | #include "RegisterCoalescer.h" | |||
25 | #include "llvm/ADT/STLExtras.h" | |||
26 | #include "llvm/ADT/SmallSet.h" | |||
27 | #include "llvm/CodeGen/LiveIntervalAnalysis.h" | |||
28 | #include "llvm/CodeGen/MachineInstrBuilder.h" | |||
29 | #include "llvm/CodeGen/MachineRegisterInfo.h" | |||
30 | #include "llvm/Support/Debug.h" | |||
31 | #include "llvm/Support/raw_ostream.h" | |||
32 | #include "llvm/Target/TargetInstrInfo.h" | |||
33 | #include "llvm/Target/TargetRegisterInfo.h" | |||
34 | #include <algorithm> | |||
35 | using namespace llvm; | |||
36 | ||||
37 | namespace { | |||
38 | //===----------------------------------------------------------------------===// | |||
39 | // Implementation of various methods necessary for calculation of live ranges. | |||
40 | // The implementation of the methods abstracts from the concrete type of the | |||
41 | // segment collection. | |||
42 | // | |||
43 | // Implementation of the class follows the Template design pattern. The base | |||
44 | // class contains generic algorithms that call collection-specific methods, | |||
45 | // which are provided in concrete subclasses. In order to avoid virtual calls | |||
46 | // these methods are provided by means of C++ template instantiation. | |||
47 | // The base class calls the methods of the subclass through method impl(), | |||
48 | // which casts 'this' pointer to the type of the subclass. | |||
49 | // | |||
50 | //===----------------------------------------------------------------------===// | |||
51 | ||||
52 | template <typename ImplT, typename IteratorT, typename CollectionT> | |||
53 | class CalcLiveRangeUtilBase { | |||
54 | protected: | |||
55 | LiveRange *LR; | |||
56 | ||||
57 | protected: | |||
58 | CalcLiveRangeUtilBase(LiveRange *LR) : LR(LR) {} | |||
59 | ||||
60 | public: | |||
61 | typedef LiveRange::Segment Segment; | |||
62 | typedef IteratorT iterator; | |||
63 | ||||
64 | VNInfo *createDeadDef(SlotIndex Def, VNInfo::Allocator &VNInfoAllocator) { | |||
65 | assert(!Def.isDead() && "Cannot define a value at the dead slot")((!Def.isDead() && "Cannot define a value at the dead slot" ) ? static_cast<void> (0) : __assert_fail ("!Def.isDead() && \"Cannot define a value at the dead slot\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 65, __PRETTY_FUNCTION__)); | |||
66 | ||||
67 | iterator I = impl().find(Def); | |||
68 | if (I == segments().end()) { | |||
69 | VNInfo *VNI = LR->getNextValue(Def, VNInfoAllocator); | |||
70 | impl().insertAtEnd(Segment(Def, Def.getDeadSlot(), VNI)); | |||
71 | return VNI; | |||
72 | } | |||
73 | ||||
74 | Segment *S = segmentAt(I); | |||
75 | if (SlotIndex::isSameInstr(Def, S->start)) { | |||
76 | assert(S->valno->def == S->start && "Inconsistent existing value def")((S->valno->def == S->start && "Inconsistent existing value def" ) ? static_cast<void> (0) : __assert_fail ("S->valno->def == S->start && \"Inconsistent existing value def\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 76, __PRETTY_FUNCTION__)); | |||
77 | ||||
78 | // It is possible to have both normal and early-clobber defs of the same | |||
79 | // register on an instruction. It doesn't make a lot of sense, but it is | |||
80 | // possible to specify in inline assembly. | |||
81 | // | |||
82 | // Just convert everything to early-clobber. | |||
83 | Def = std::min(Def, S->start); | |||
84 | if (Def != S->start) | |||
85 | S->start = S->valno->def = Def; | |||
86 | return S->valno; | |||
87 | } | |||
88 | assert(SlotIndex::isEarlierInstr(Def, S->start) && "Already live at def")((SlotIndex::isEarlierInstr(Def, S->start) && "Already live at def" ) ? static_cast<void> (0) : __assert_fail ("SlotIndex::isEarlierInstr(Def, S->start) && \"Already live at def\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 88, __PRETTY_FUNCTION__)); | |||
89 | VNInfo *VNI = LR->getNextValue(Def, VNInfoAllocator); | |||
90 | segments().insert(I, Segment(Def, Def.getDeadSlot(), VNI)); | |||
91 | return VNI; | |||
92 | } | |||
93 | ||||
94 | VNInfo *extendInBlock(SlotIndex StartIdx, SlotIndex Use) { | |||
95 | if (segments().empty()) | |||
96 | return nullptr; | |||
97 | iterator I = | |||
98 | impl().findInsertPos(Segment(Use.getPrevSlot(), Use, nullptr)); | |||
99 | if (I == segments().begin()) | |||
100 | return nullptr; | |||
101 | --I; | |||
102 | if (I->end <= StartIdx) | |||
103 | return nullptr; | |||
104 | if (I->end < Use) | |||
105 | extendSegmentEndTo(I, Use); | |||
106 | return I->valno; | |||
107 | } | |||
108 | ||||
109 | /// This method is used when we want to extend the segment specified | |||
110 | /// by I to end at the specified endpoint. To do this, we should | |||
111 | /// merge and eliminate all segments that this will overlap | |||
112 | /// with. The iterator is not invalidated. | |||
113 | void extendSegmentEndTo(iterator I, SlotIndex NewEnd) { | |||
114 | assert(I != segments().end() && "Not a valid segment!")((I != segments().end() && "Not a valid segment!") ? static_cast <void> (0) : __assert_fail ("I != segments().end() && \"Not a valid segment!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 114, __PRETTY_FUNCTION__)); | |||
115 | Segment *S = segmentAt(I); | |||
116 | VNInfo *ValNo = I->valno; | |||
117 | ||||
118 | // Search for the first segment that we can't merge with. | |||
119 | iterator MergeTo = std::next(I); | |||
120 | for (; MergeTo != segments().end() && NewEnd >= MergeTo->end; ++MergeTo) | |||
121 | assert(MergeTo->valno == ValNo && "Cannot merge with differing values!")((MergeTo->valno == ValNo && "Cannot merge with differing values!" ) ? static_cast<void> (0) : __assert_fail ("MergeTo->valno == ValNo && \"Cannot merge with differing values!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 121, __PRETTY_FUNCTION__)); | |||
122 | ||||
123 | // If NewEnd was in the middle of a segment, make sure to get its endpoint. | |||
124 | S->end = std::max(NewEnd, std::prev(MergeTo)->end); | |||
125 | ||||
126 | // If the newly formed segment now touches the segment after it and if they | |||
127 | // have the same value number, merge the two segments into one segment. | |||
128 | if (MergeTo != segments().end() && MergeTo->start <= I->end && | |||
129 | MergeTo->valno == ValNo) { | |||
130 | S->end = MergeTo->end; | |||
131 | ++MergeTo; | |||
132 | } | |||
133 | ||||
134 | // Erase any dead segments. | |||
135 | segments().erase(std::next(I), MergeTo); | |||
136 | } | |||
137 | ||||
138 | /// This method is used when we want to extend the segment specified | |||
139 | /// by I to start at the specified endpoint. To do this, we should | |||
140 | /// merge and eliminate all segments that this will overlap with. | |||
141 | iterator extendSegmentStartTo(iterator I, SlotIndex NewStart) { | |||
142 | assert(I != segments().end() && "Not a valid segment!")((I != segments().end() && "Not a valid segment!") ? static_cast <void> (0) : __assert_fail ("I != segments().end() && \"Not a valid segment!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 142, __PRETTY_FUNCTION__)); | |||
143 | Segment *S = segmentAt(I); | |||
144 | VNInfo *ValNo = I->valno; | |||
145 | ||||
146 | // Search for the first segment that we can't merge with. | |||
147 | iterator MergeTo = I; | |||
148 | do { | |||
149 | if (MergeTo == segments().begin()) { | |||
150 | S->start = NewStart; | |||
151 | segments().erase(MergeTo, I); | |||
152 | return I; | |||
153 | } | |||
154 | assert(MergeTo->valno == ValNo && "Cannot merge with differing values!")((MergeTo->valno == ValNo && "Cannot merge with differing values!" ) ? static_cast<void> (0) : __assert_fail ("MergeTo->valno == ValNo && \"Cannot merge with differing values!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 154, __PRETTY_FUNCTION__)); | |||
155 | --MergeTo; | |||
156 | } while (NewStart <= MergeTo->start); | |||
157 | ||||
158 | // If we start in the middle of another segment, just delete a range and | |||
159 | // extend that segment. | |||
160 | if (MergeTo->end >= NewStart && MergeTo->valno == ValNo) { | |||
161 | segmentAt(MergeTo)->end = S->end; | |||
162 | } else { | |||
163 | // Otherwise, extend the segment right after. | |||
164 | ++MergeTo; | |||
165 | Segment *MergeToSeg = segmentAt(MergeTo); | |||
166 | MergeToSeg->start = NewStart; | |||
167 | MergeToSeg->end = S->end; | |||
168 | } | |||
169 | ||||
170 | segments().erase(std::next(MergeTo), std::next(I)); | |||
171 | return MergeTo; | |||
172 | } | |||
173 | ||||
174 | iterator addSegment(Segment S) { | |||
175 | SlotIndex Start = S.start, End = S.end; | |||
176 | iterator I = impl().findInsertPos(S); | |||
177 | ||||
178 | // If the inserted segment starts in the middle or right at the end of | |||
179 | // another segment, just extend that segment to contain the segment of S. | |||
180 | if (I != segments().begin()) { | |||
181 | iterator B = std::prev(I); | |||
182 | if (S.valno == B->valno) { | |||
183 | if (B->start <= Start && B->end >= Start) { | |||
184 | extendSegmentEndTo(B, End); | |||
185 | return B; | |||
186 | } | |||
187 | } else { | |||
188 | // Check to make sure that we are not overlapping two live segments with | |||
189 | // different valno's. | |||
190 | assert(B->end <= Start &&((B->end <= Start && "Cannot overlap two segments with differing ValID's" " (did you def the same reg twice in a MachineInstr?)") ? static_cast <void> (0) : __assert_fail ("B->end <= Start && \"Cannot overlap two segments with differing ValID's\" \" (did you def the same reg twice in a MachineInstr?)\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 192, __PRETTY_FUNCTION__)) | |||
191 | "Cannot overlap two segments with differing ValID's"((B->end <= Start && "Cannot overlap two segments with differing ValID's" " (did you def the same reg twice in a MachineInstr?)") ? static_cast <void> (0) : __assert_fail ("B->end <= Start && \"Cannot overlap two segments with differing ValID's\" \" (did you def the same reg twice in a MachineInstr?)\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 192, __PRETTY_FUNCTION__)) | |||
192 | " (did you def the same reg twice in a MachineInstr?)")((B->end <= Start && "Cannot overlap two segments with differing ValID's" " (did you def the same reg twice in a MachineInstr?)") ? static_cast <void> (0) : __assert_fail ("B->end <= Start && \"Cannot overlap two segments with differing ValID's\" \" (did you def the same reg twice in a MachineInstr?)\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 192, __PRETTY_FUNCTION__)); | |||
193 | } | |||
194 | } | |||
195 | ||||
196 | // Otherwise, if this segment ends in the middle of, or right next | |||
197 | // to, another segment, merge it into that segment. | |||
198 | if (I != segments().end()) { | |||
199 | if (S.valno == I->valno) { | |||
200 | if (I->start <= End) { | |||
201 | I = extendSegmentStartTo(I, Start); | |||
202 | ||||
203 | // If S is a complete superset of a segment, we may need to grow its | |||
204 | // endpoint as well. | |||
205 | if (End > I->end) | |||
206 | extendSegmentEndTo(I, End); | |||
207 | return I; | |||
208 | } | |||
209 | } else { | |||
210 | // Check to make sure that we are not overlapping two live segments with | |||
211 | // different valno's. | |||
212 | assert(I->start >= End &&((I->start >= End && "Cannot overlap two segments with differing ValID's" ) ? static_cast<void> (0) : __assert_fail ("I->start >= End && \"Cannot overlap two segments with differing ValID's\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 213, __PRETTY_FUNCTION__)) | |||
213 | "Cannot overlap two segments with differing ValID's")((I->start >= End && "Cannot overlap two segments with differing ValID's" ) ? static_cast<void> (0) : __assert_fail ("I->start >= End && \"Cannot overlap two segments with differing ValID's\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 213, __PRETTY_FUNCTION__)); | |||
214 | } | |||
215 | } | |||
216 | ||||
217 | // Otherwise, this is just a new segment that doesn't interact with | |||
218 | // anything. | |||
219 | // Insert it. | |||
220 | return segments().insert(I, S); | |||
221 | } | |||
222 | ||||
223 | private: | |||
224 | ImplT &impl() { return *static_cast<ImplT *>(this); } | |||
225 | ||||
226 | CollectionT &segments() { return impl().segmentsColl(); } | |||
227 | ||||
228 | Segment *segmentAt(iterator I) { return const_cast<Segment *>(&(*I)); } | |||
229 | }; | |||
230 | ||||
231 | //===----------------------------------------------------------------------===// | |||
232 | // Instantiation of the methods for calculation of live ranges | |||
233 | // based on a segment vector. | |||
234 | //===----------------------------------------------------------------------===// | |||
235 | ||||
236 | class CalcLiveRangeUtilVector; | |||
237 | typedef CalcLiveRangeUtilBase<CalcLiveRangeUtilVector, LiveRange::iterator, | |||
238 | LiveRange::Segments> CalcLiveRangeUtilVectorBase; | |||
239 | ||||
240 | class CalcLiveRangeUtilVector : public CalcLiveRangeUtilVectorBase { | |||
241 | public: | |||
242 | CalcLiveRangeUtilVector(LiveRange *LR) : CalcLiveRangeUtilVectorBase(LR) {} | |||
243 | ||||
244 | private: | |||
245 | friend CalcLiveRangeUtilVectorBase; | |||
246 | ||||
247 | LiveRange::Segments &segmentsColl() { return LR->segments; } | |||
248 | ||||
249 | void insertAtEnd(const Segment &S) { LR->segments.push_back(S); } | |||
250 | ||||
251 | iterator find(SlotIndex Pos) { return LR->find(Pos); } | |||
252 | ||||
253 | iterator findInsertPos(Segment S) { | |||
254 | return std::upper_bound(LR->begin(), LR->end(), S.start); | |||
255 | } | |||
256 | }; | |||
257 | ||||
258 | //===----------------------------------------------------------------------===// | |||
259 | // Instantiation of the methods for calculation of live ranges | |||
260 | // based on a segment set. | |||
261 | //===----------------------------------------------------------------------===// | |||
262 | ||||
263 | class CalcLiveRangeUtilSet; | |||
264 | typedef CalcLiveRangeUtilBase<CalcLiveRangeUtilSet, | |||
265 | LiveRange::SegmentSet::iterator, | |||
266 | LiveRange::SegmentSet> CalcLiveRangeUtilSetBase; | |||
267 | ||||
268 | class CalcLiveRangeUtilSet : public CalcLiveRangeUtilSetBase { | |||
269 | public: | |||
270 | CalcLiveRangeUtilSet(LiveRange *LR) : CalcLiveRangeUtilSetBase(LR) {} | |||
271 | ||||
272 | private: | |||
273 | friend CalcLiveRangeUtilSetBase; | |||
274 | ||||
275 | LiveRange::SegmentSet &segmentsColl() { return *LR->segmentSet; } | |||
276 | ||||
277 | void insertAtEnd(const Segment &S) { | |||
278 | LR->segmentSet->insert(LR->segmentSet->end(), S); | |||
279 | } | |||
280 | ||||
281 | iterator find(SlotIndex Pos) { | |||
282 | iterator I = | |||
283 | LR->segmentSet->upper_bound(Segment(Pos, Pos.getNextSlot(), nullptr)); | |||
284 | if (I == LR->segmentSet->begin()) | |||
285 | return I; | |||
286 | iterator PrevI = std::prev(I); | |||
287 | if (Pos < (*PrevI).end) | |||
288 | return PrevI; | |||
289 | return I; | |||
290 | } | |||
291 | ||||
292 | iterator findInsertPos(Segment S) { | |||
293 | iterator I = LR->segmentSet->upper_bound(S); | |||
294 | if (I != LR->segmentSet->end() && !(S.start < *I)) | |||
295 | ++I; | |||
296 | return I; | |||
297 | } | |||
298 | }; | |||
299 | } // namespace | |||
300 | ||||
301 | //===----------------------------------------------------------------------===// | |||
302 | // LiveRange methods | |||
303 | //===----------------------------------------------------------------------===// | |||
304 | ||||
305 | LiveRange::iterator LiveRange::find(SlotIndex Pos) { | |||
306 | // This algorithm is basically std::upper_bound. | |||
307 | // Unfortunately, std::upper_bound cannot be used with mixed types until we | |||
308 | // adopt C++0x. Many libraries can do it, but not all. | |||
309 | if (empty() || Pos >= endIndex()) | |||
310 | return end(); | |||
311 | iterator I = begin(); | |||
312 | size_t Len = size(); | |||
313 | do { | |||
314 | size_t Mid = Len >> 1; | |||
315 | if (Pos < I[Mid].end) { | |||
316 | Len = Mid; | |||
317 | } else { | |||
318 | I += Mid + 1; | |||
319 | Len -= Mid + 1; | |||
320 | } | |||
321 | } while (Len); | |||
322 | return I; | |||
323 | } | |||
324 | ||||
325 | VNInfo *LiveRange::createDeadDef(SlotIndex Def, | |||
326 | VNInfo::Allocator &VNInfoAllocator) { | |||
327 | // Use the segment set, if it is available. | |||
328 | if (segmentSet != nullptr) | |||
329 | return CalcLiveRangeUtilSet(this).createDeadDef(Def, VNInfoAllocator); | |||
330 | // Otherwise use the segment vector. | |||
331 | return CalcLiveRangeUtilVector(this).createDeadDef(Def, VNInfoAllocator); | |||
332 | } | |||
333 | ||||
334 | // overlaps - Return true if the intersection of the two live ranges is | |||
335 | // not empty. | |||
336 | // | |||
337 | // An example for overlaps(): | |||
338 | // | |||
339 | // 0: A = ... | |||
340 | // 4: B = ... | |||
341 | // 8: C = A + B ;; last use of A | |||
342 | // | |||
343 | // The live ranges should look like: | |||
344 | // | |||
345 | // A = [3, 11) | |||
346 | // B = [7, x) | |||
347 | // C = [11, y) | |||
348 | // | |||
349 | // A->overlaps(C) should return false since we want to be able to join | |||
350 | // A and C. | |||
351 | // | |||
352 | bool LiveRange::overlapsFrom(const LiveRange& other, | |||
353 | const_iterator StartPos) const { | |||
354 | assert(!empty() && "empty range")((!empty() && "empty range") ? static_cast<void> (0) : __assert_fail ("!empty() && \"empty range\"", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 354, __PRETTY_FUNCTION__)); | |||
355 | const_iterator i = begin(); | |||
356 | const_iterator ie = end(); | |||
357 | const_iterator j = StartPos; | |||
358 | const_iterator je = other.end(); | |||
359 | ||||
360 | assert((StartPos->start <= i->start || StartPos == other.begin()) &&(((StartPos->start <= i->start || StartPos == other. begin()) && StartPos != other.end() && "Bogus start position hint!" ) ? static_cast<void> (0) : __assert_fail ("(StartPos->start <= i->start || StartPos == other.begin()) && StartPos != other.end() && \"Bogus start position hint!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 361, __PRETTY_FUNCTION__)) | |||
361 | StartPos != other.end() && "Bogus start position hint!")(((StartPos->start <= i->start || StartPos == other. begin()) && StartPos != other.end() && "Bogus start position hint!" ) ? static_cast<void> (0) : __assert_fail ("(StartPos->start <= i->start || StartPos == other.begin()) && StartPos != other.end() && \"Bogus start position hint!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 361, __PRETTY_FUNCTION__)); | |||
362 | ||||
363 | if (i->start < j->start) { | |||
364 | i = std::upper_bound(i, ie, j->start); | |||
365 | if (i != begin()) --i; | |||
366 | } else if (j->start < i->start) { | |||
367 | ++StartPos; | |||
368 | if (StartPos != other.end() && StartPos->start <= i->start) { | |||
369 | assert(StartPos < other.end() && i < end())((StartPos < other.end() && i < end()) ? static_cast <void> (0) : __assert_fail ("StartPos < other.end() && i < end()" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 369, __PRETTY_FUNCTION__)); | |||
370 | j = std::upper_bound(j, je, i->start); | |||
371 | if (j != other.begin()) --j; | |||
372 | } | |||
373 | } else { | |||
374 | return true; | |||
375 | } | |||
376 | ||||
377 | if (j == je) return false; | |||
378 | ||||
379 | while (i != ie) { | |||
380 | if (i->start > j->start) { | |||
381 | std::swap(i, j); | |||
382 | std::swap(ie, je); | |||
383 | } | |||
384 | ||||
385 | if (i->end > j->start) | |||
386 | return true; | |||
387 | ++i; | |||
388 | } | |||
389 | ||||
390 | return false; | |||
391 | } | |||
392 | ||||
393 | bool LiveRange::overlaps(const LiveRange &Other, const CoalescerPair &CP, | |||
394 | const SlotIndexes &Indexes) const { | |||
395 | assert(!empty() && "empty range")((!empty() && "empty range") ? static_cast<void> (0) : __assert_fail ("!empty() && \"empty range\"", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 395, __PRETTY_FUNCTION__)); | |||
396 | if (Other.empty()) | |||
397 | return false; | |||
398 | ||||
399 | // Use binary searches to find initial positions. | |||
400 | const_iterator I = find(Other.beginIndex()); | |||
401 | const_iterator IE = end(); | |||
402 | if (I == IE) | |||
403 | return false; | |||
404 | const_iterator J = Other.find(I->start); | |||
405 | const_iterator JE = Other.end(); | |||
406 | if (J == JE) | |||
407 | return false; | |||
408 | ||||
409 | for (;;) { | |||
410 | // J has just been advanced to satisfy: | |||
411 | assert(J->end >= I->start)((J->end >= I->start) ? static_cast<void> (0) : __assert_fail ("J->end >= I->start", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 411, __PRETTY_FUNCTION__)); | |||
412 | // Check for an overlap. | |||
413 | if (J->start < I->end) { | |||
414 | // I and J are overlapping. Find the later start. | |||
415 | SlotIndex Def = std::max(I->start, J->start); | |||
416 | // Allow the overlap if Def is a coalescable copy. | |||
417 | if (Def.isBlock() || | |||
418 | !CP.isCoalescable(Indexes.getInstructionFromIndex(Def))) | |||
419 | return true; | |||
420 | } | |||
421 | // Advance the iterator that ends first to check for more overlaps. | |||
422 | if (J->end > I->end) { | |||
423 | std::swap(I, J); | |||
424 | std::swap(IE, JE); | |||
425 | } | |||
426 | // Advance J until J->end >= I->start. | |||
427 | do | |||
428 | if (++J == JE) | |||
429 | return false; | |||
430 | while (J->end < I->start); | |||
431 | } | |||
432 | } | |||
433 | ||||
434 | /// overlaps - Return true if the live range overlaps an interval specified | |||
435 | /// by [Start, End). | |||
436 | bool LiveRange::overlaps(SlotIndex Start, SlotIndex End) const { | |||
437 | assert(Start < End && "Invalid range")((Start < End && "Invalid range") ? static_cast< void> (0) : __assert_fail ("Start < End && \"Invalid range\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 437, __PRETTY_FUNCTION__)); | |||
438 | const_iterator I = std::lower_bound(begin(), end(), End); | |||
439 | return I != begin() && (--I)->end > Start; | |||
440 | } | |||
441 | ||||
442 | bool LiveRange::covers(const LiveRange &Other) const { | |||
443 | if (empty()) | |||
444 | return Other.empty(); | |||
445 | ||||
446 | const_iterator I = begin(); | |||
447 | for (const Segment &O : Other.segments) { | |||
448 | I = advanceTo(I, O.start); | |||
449 | if (I == end() || I->start > O.start) | |||
450 | return false; | |||
451 | ||||
452 | // Check adjacent live segments and see if we can get behind O.end. | |||
453 | while (I->end < O.end) { | |||
454 | const_iterator Last = I; | |||
455 | // Get next segment and abort if it was not adjacent. | |||
456 | ++I; | |||
457 | if (I == end() || Last->end != I->start) | |||
458 | return false; | |||
459 | } | |||
460 | } | |||
461 | return true; | |||
462 | } | |||
463 | ||||
464 | /// ValNo is dead, remove it. If it is the largest value number, just nuke it | |||
465 | /// (and any other deleted values neighboring it), otherwise mark it as ~1U so | |||
466 | /// it can be nuked later. | |||
467 | void LiveRange::markValNoForDeletion(VNInfo *ValNo) { | |||
468 | if (ValNo->id == getNumValNums()-1) { | |||
469 | do { | |||
470 | valnos.pop_back(); | |||
471 | } while (!valnos.empty() && valnos.back()->isUnused()); | |||
472 | } else { | |||
473 | ValNo->markUnused(); | |||
474 | } | |||
475 | } | |||
476 | ||||
477 | /// RenumberValues - Renumber all values in order of appearance and delete the | |||
478 | /// remaining unused values. | |||
479 | void LiveRange::RenumberValues() { | |||
480 | SmallPtrSet<VNInfo*, 8> Seen; | |||
481 | valnos.clear(); | |||
482 | for (const Segment &S : segments) { | |||
483 | VNInfo *VNI = S.valno; | |||
484 | if (!Seen.insert(VNI).second) | |||
485 | continue; | |||
486 | assert(!VNI->isUnused() && "Unused valno used by live segment")((!VNI->isUnused() && "Unused valno used by live segment" ) ? static_cast<void> (0) : __assert_fail ("!VNI->isUnused() && \"Unused valno used by live segment\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 486, __PRETTY_FUNCTION__)); | |||
487 | VNI->id = (unsigned)valnos.size(); | |||
488 | valnos.push_back(VNI); | |||
489 | } | |||
490 | } | |||
491 | ||||
492 | void LiveRange::addSegmentToSet(Segment S) { | |||
493 | CalcLiveRangeUtilSet(this).addSegment(S); | |||
494 | } | |||
495 | ||||
496 | LiveRange::iterator LiveRange::addSegment(Segment S) { | |||
497 | // Use the segment set, if it is available. | |||
498 | if (segmentSet != nullptr) { | |||
499 | addSegmentToSet(S); | |||
500 | return end(); | |||
501 | } | |||
502 | // Otherwise use the segment vector. | |||
503 | return CalcLiveRangeUtilVector(this).addSegment(S); | |||
504 | } | |||
505 | ||||
506 | void LiveRange::append(const Segment S) { | |||
507 | // Check that the segment belongs to the back of the list. | |||
508 | assert(segments.empty() || segments.back().end <= S.start)((segments.empty() || segments.back().end <= S.start) ? static_cast <void> (0) : __assert_fail ("segments.empty() || segments.back().end <= S.start" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 508, __PRETTY_FUNCTION__)); | |||
509 | segments.push_back(S); | |||
510 | } | |||
511 | ||||
512 | /// extendInBlock - If this range is live before Kill in the basic | |||
513 | /// block that starts at StartIdx, extend it to be live up to Kill and return | |||
514 | /// the value. If there is no live range before Kill, return NULL. | |||
515 | VNInfo *LiveRange::extendInBlock(SlotIndex StartIdx, SlotIndex Kill) { | |||
516 | // Use the segment set, if it is available. | |||
517 | if (segmentSet != nullptr) | |||
518 | return CalcLiveRangeUtilSet(this).extendInBlock(StartIdx, Kill); | |||
519 | // Otherwise use the segment vector. | |||
520 | return CalcLiveRangeUtilVector(this).extendInBlock(StartIdx, Kill); | |||
521 | } | |||
522 | ||||
523 | /// Remove the specified segment from this range. Note that the segment must | |||
524 | /// be in a single Segment in its entirety. | |||
525 | void LiveRange::removeSegment(SlotIndex Start, SlotIndex End, | |||
526 | bool RemoveDeadValNo) { | |||
527 | // Find the Segment containing this span. | |||
528 | iterator I = find(Start); | |||
529 | assert(I != end() && "Segment is not in range!")((I != end() && "Segment is not in range!") ? static_cast <void> (0) : __assert_fail ("I != end() && \"Segment is not in range!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 529, __PRETTY_FUNCTION__)); | |||
530 | assert(I->containsInterval(Start, End)((I->containsInterval(Start, End) && "Segment is not entirely in range!" ) ? static_cast<void> (0) : __assert_fail ("I->containsInterval(Start, End) && \"Segment is not entirely in range!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 531, __PRETTY_FUNCTION__)) | |||
531 | && "Segment is not entirely in range!")((I->containsInterval(Start, End) && "Segment is not entirely in range!" ) ? static_cast<void> (0) : __assert_fail ("I->containsInterval(Start, End) && \"Segment is not entirely in range!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 531, __PRETTY_FUNCTION__)); | |||
532 | ||||
533 | // If the span we are removing is at the start of the Segment, adjust it. | |||
534 | VNInfo *ValNo = I->valno; | |||
535 | if (I->start == Start) { | |||
536 | if (I->end == End) { | |||
537 | if (RemoveDeadValNo) { | |||
538 | // Check if val# is dead. | |||
539 | bool isDead = true; | |||
540 | for (const_iterator II = begin(), EE = end(); II != EE; ++II) | |||
541 | if (II != I && II->valno == ValNo) { | |||
542 | isDead = false; | |||
543 | break; | |||
544 | } | |||
545 | if (isDead) { | |||
546 | // Now that ValNo is dead, remove it. | |||
547 | markValNoForDeletion(ValNo); | |||
548 | } | |||
549 | } | |||
550 | ||||
551 | segments.erase(I); // Removed the whole Segment. | |||
552 | } else | |||
553 | I->start = End; | |||
554 | return; | |||
555 | } | |||
556 | ||||
557 | // Otherwise if the span we are removing is at the end of the Segment, | |||
558 | // adjust the other way. | |||
559 | if (I->end == End) { | |||
560 | I->end = Start; | |||
561 | return; | |||
562 | } | |||
563 | ||||
564 | // Otherwise, we are splitting the Segment into two pieces. | |||
565 | SlotIndex OldEnd = I->end; | |||
566 | I->end = Start; // Trim the old segment. | |||
567 | ||||
568 | // Insert the new one. | |||
569 | segments.insert(std::next(I), Segment(End, OldEnd, ValNo)); | |||
570 | } | |||
571 | ||||
572 | /// removeValNo - Remove all the segments defined by the specified value#. | |||
573 | /// Also remove the value# from value# list. | |||
574 | void LiveRange::removeValNo(VNInfo *ValNo) { | |||
575 | if (empty()) return; | |||
576 | segments.erase(std::remove_if(begin(), end(), [ValNo](const Segment &S) { | |||
577 | return S.valno == ValNo; | |||
578 | }), end()); | |||
579 | // Now that ValNo is dead, remove it. | |||
580 | markValNoForDeletion(ValNo); | |||
581 | } | |||
582 | ||||
583 | void LiveRange::join(LiveRange &Other, | |||
584 | const int *LHSValNoAssignments, | |||
585 | const int *RHSValNoAssignments, | |||
586 | SmallVectorImpl<VNInfo *> &NewVNInfo) { | |||
587 | verify(); | |||
588 | ||||
589 | // Determine if any of our values are mapped. This is uncommon, so we want | |||
590 | // to avoid the range scan if not. | |||
591 | bool MustMapCurValNos = false; | |||
592 | unsigned NumVals = getNumValNums(); | |||
593 | unsigned NumNewVals = NewVNInfo.size(); | |||
594 | for (unsigned i = 0; i != NumVals; ++i) { | |||
595 | unsigned LHSValID = LHSValNoAssignments[i]; | |||
596 | if (i != LHSValID || | |||
597 | (NewVNInfo[LHSValID] && NewVNInfo[LHSValID] != getValNumInfo(i))) { | |||
598 | MustMapCurValNos = true; | |||
599 | break; | |||
600 | } | |||
601 | } | |||
602 | ||||
603 | // If we have to apply a mapping to our base range assignment, rewrite it now. | |||
604 | if (MustMapCurValNos && !empty()) { | |||
605 | // Map the first live range. | |||
606 | ||||
607 | iterator OutIt = begin(); | |||
608 | OutIt->valno = NewVNInfo[LHSValNoAssignments[OutIt->valno->id]]; | |||
609 | for (iterator I = std::next(OutIt), E = end(); I != E; ++I) { | |||
610 | VNInfo* nextValNo = NewVNInfo[LHSValNoAssignments[I->valno->id]]; | |||
611 | assert(nextValNo && "Huh?")((nextValNo && "Huh?") ? static_cast<void> (0) : __assert_fail ("nextValNo && \"Huh?\"", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 611, __PRETTY_FUNCTION__)); | |||
612 | ||||
613 | // If this live range has the same value # as its immediate predecessor, | |||
614 | // and if they are neighbors, remove one Segment. This happens when we | |||
615 | // have [0,4:0)[4,7:1) and map 0/1 onto the same value #. | |||
616 | if (OutIt->valno == nextValNo && OutIt->end == I->start) { | |||
617 | OutIt->end = I->end; | |||
618 | } else { | |||
619 | // Didn't merge. Move OutIt to the next segment, | |||
620 | ++OutIt; | |||
621 | OutIt->valno = nextValNo; | |||
622 | if (OutIt != I) { | |||
623 | OutIt->start = I->start; | |||
624 | OutIt->end = I->end; | |||
625 | } | |||
626 | } | |||
627 | } | |||
628 | // If we merge some segments, chop off the end. | |||
629 | ++OutIt; | |||
630 | segments.erase(OutIt, end()); | |||
631 | } | |||
632 | ||||
633 | // Rewrite Other values before changing the VNInfo ids. | |||
634 | // This can leave Other in an invalid state because we're not coalescing | |||
635 | // touching segments that now have identical values. That's OK since Other is | |||
636 | // not supposed to be valid after calling join(); | |||
637 | for (Segment &S : Other.segments) | |||
638 | S.valno = NewVNInfo[RHSValNoAssignments[S.valno->id]]; | |||
639 | ||||
640 | // Update val# info. Renumber them and make sure they all belong to this | |||
641 | // LiveRange now. Also remove dead val#'s. | |||
642 | unsigned NumValNos = 0; | |||
643 | for (unsigned i = 0; i < NumNewVals; ++i) { | |||
644 | VNInfo *VNI = NewVNInfo[i]; | |||
645 | if (VNI) { | |||
646 | if (NumValNos >= NumVals) | |||
647 | valnos.push_back(VNI); | |||
648 | else | |||
649 | valnos[NumValNos] = VNI; | |||
650 | VNI->id = NumValNos++; // Renumber val#. | |||
651 | } | |||
652 | } | |||
653 | if (NumNewVals < NumVals) | |||
654 | valnos.resize(NumNewVals); // shrinkify | |||
655 | ||||
656 | // Okay, now insert the RHS live segments into the LHS. | |||
657 | LiveRangeUpdater Updater(this); | |||
658 | for (Segment &S : Other.segments) | |||
659 | Updater.add(S); | |||
660 | } | |||
661 | ||||
662 | /// Merge all of the segments in RHS into this live range as the specified | |||
663 | /// value number. The segments in RHS are allowed to overlap with segments in | |||
664 | /// the current range, but only if the overlapping segments have the | |||
665 | /// specified value number. | |||
666 | void LiveRange::MergeSegmentsInAsValue(const LiveRange &RHS, | |||
667 | VNInfo *LHSValNo) { | |||
668 | LiveRangeUpdater Updater(this); | |||
669 | for (const Segment &S : RHS.segments) | |||
670 | Updater.add(S.start, S.end, LHSValNo); | |||
671 | } | |||
672 | ||||
673 | /// MergeValueInAsValue - Merge all of the live segments of a specific val# | |||
674 | /// in RHS into this live range as the specified value number. | |||
675 | /// The segments in RHS are allowed to overlap with segments in the | |||
676 | /// current range, it will replace the value numbers of the overlaped | |||
677 | /// segments with the specified value number. | |||
678 | void LiveRange::MergeValueInAsValue(const LiveRange &RHS, | |||
679 | const VNInfo *RHSValNo, | |||
680 | VNInfo *LHSValNo) { | |||
681 | LiveRangeUpdater Updater(this); | |||
682 | for (const Segment &S : RHS.segments) | |||
683 | if (S.valno == RHSValNo) | |||
684 | Updater.add(S.start, S.end, LHSValNo); | |||
685 | } | |||
686 | ||||
687 | /// MergeValueNumberInto - This method is called when two value nubmers | |||
688 | /// are found to be equivalent. This eliminates V1, replacing all | |||
689 | /// segments with the V1 value number with the V2 value number. This can | |||
690 | /// cause merging of V1/V2 values numbers and compaction of the value space. | |||
691 | VNInfo *LiveRange::MergeValueNumberInto(VNInfo *V1, VNInfo *V2) { | |||
692 | assert(V1 != V2 && "Identical value#'s are always equivalent!")((V1 != V2 && "Identical value#'s are always equivalent!" ) ? static_cast<void> (0) : __assert_fail ("V1 != V2 && \"Identical value#'s are always equivalent!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 692, __PRETTY_FUNCTION__)); | |||
693 | ||||
694 | // This code actually merges the (numerically) larger value number into the | |||
695 | // smaller value number, which is likely to allow us to compactify the value | |||
696 | // space. The only thing we have to be careful of is to preserve the | |||
697 | // instruction that defines the result value. | |||
698 | ||||
699 | // Make sure V2 is smaller than V1. | |||
700 | if (V1->id < V2->id) { | |||
701 | V1->copyFrom(*V2); | |||
702 | std::swap(V1, V2); | |||
703 | } | |||
704 | ||||
705 | // Merge V1 segments into V2. | |||
706 | for (iterator I = begin(); I != end(); ) { | |||
707 | iterator S = I++; | |||
708 | if (S->valno != V1) continue; // Not a V1 Segment. | |||
709 | ||||
710 | // Okay, we found a V1 live range. If it had a previous, touching, V2 live | |||
711 | // range, extend it. | |||
712 | if (S != begin()) { | |||
713 | iterator Prev = S-1; | |||
714 | if (Prev->valno == V2 && Prev->end == S->start) { | |||
715 | Prev->end = S->end; | |||
716 | ||||
717 | // Erase this live-range. | |||
718 | segments.erase(S); | |||
719 | I = Prev+1; | |||
720 | S = Prev; | |||
721 | } | |||
722 | } | |||
723 | ||||
724 | // Okay, now we have a V1 or V2 live range that is maximally merged forward. | |||
725 | // Ensure that it is a V2 live-range. | |||
726 | S->valno = V2; | |||
727 | ||||
728 | // If we can merge it into later V2 segments, do so now. We ignore any | |||
729 | // following V1 segments, as they will be merged in subsequent iterations | |||
730 | // of the loop. | |||
731 | if (I != end()) { | |||
732 | if (I->start == S->end && I->valno == V2) { | |||
733 | S->end = I->end; | |||
734 | segments.erase(I); | |||
735 | I = S+1; | |||
736 | } | |||
737 | } | |||
738 | } | |||
739 | ||||
740 | // Now that V1 is dead, remove it. | |||
741 | markValNoForDeletion(V1); | |||
742 | ||||
743 | return V2; | |||
744 | } | |||
745 | ||||
746 | void LiveRange::flushSegmentSet() { | |||
747 | assert(segmentSet != nullptr && "segment set must have been created")((segmentSet != nullptr && "segment set must have been created" ) ? static_cast<void> (0) : __assert_fail ("segmentSet != nullptr && \"segment set must have been created\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 747, __PRETTY_FUNCTION__)); | |||
748 | assert(((segments.empty() && "segment set can be used only initially before switching to the array" ) ? static_cast<void> (0) : __assert_fail ("segments.empty() && \"segment set can be used only initially before switching to the array\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 750, __PRETTY_FUNCTION__)) | |||
749 | segments.empty() &&((segments.empty() && "segment set can be used only initially before switching to the array" ) ? static_cast<void> (0) : __assert_fail ("segments.empty() && \"segment set can be used only initially before switching to the array\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 750, __PRETTY_FUNCTION__)) | |||
750 | "segment set can be used only initially before switching to the array")((segments.empty() && "segment set can be used only initially before switching to the array" ) ? static_cast<void> (0) : __assert_fail ("segments.empty() && \"segment set can be used only initially before switching to the array\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 750, __PRETTY_FUNCTION__)); | |||
751 | segments.append(segmentSet->begin(), segmentSet->end()); | |||
752 | segmentSet = nullptr; | |||
753 | verify(); | |||
754 | } | |||
755 | ||||
756 | bool LiveRange::isLiveAtIndexes(ArrayRef<SlotIndex> Slots) const { | |||
757 | ArrayRef<SlotIndex>::iterator SlotI = Slots.begin(); | |||
758 | ArrayRef<SlotIndex>::iterator SlotE = Slots.end(); | |||
759 | ||||
760 | // If there are no regmask slots, we have nothing to search. | |||
761 | if (SlotI == SlotE) | |||
762 | return false; | |||
763 | ||||
764 | // Start our search at the first segment that ends after the first slot. | |||
765 | const_iterator SegmentI = find(*SlotI); | |||
766 | const_iterator SegmentE = end(); | |||
767 | ||||
768 | // If there are no segments that end after the first slot, we're done. | |||
769 | if (SegmentI == SegmentE) | |||
770 | return false; | |||
771 | ||||
772 | // Look for each slot in the live range. | |||
773 | for ( ; SlotI != SlotE; ++SlotI) { | |||
774 | // Go to the next segment that ends after the current slot. | |||
775 | // The slot may be within a hole in the range. | |||
776 | SegmentI = advanceTo(SegmentI, *SlotI); | |||
777 | if (SegmentI == SegmentE) | |||
778 | return false; | |||
779 | ||||
780 | // If this segment contains the slot, we're done. | |||
781 | if (SegmentI->contains(*SlotI)) | |||
782 | return true; | |||
783 | // Otherwise, look for the next slot. | |||
784 | } | |||
785 | ||||
786 | // We didn't find a segment containing any of the slots. | |||
787 | return false; | |||
788 | } | |||
789 | ||||
790 | void LiveInterval::freeSubRange(SubRange *S) { | |||
791 | S->~SubRange(); | |||
792 | // Memory was allocated with BumpPtr allocator and is not freed here. | |||
793 | } | |||
794 | ||||
795 | void LiveInterval::removeEmptySubRanges() { | |||
796 | SubRange **NextPtr = &SubRanges; | |||
797 | SubRange *I = *NextPtr; | |||
798 | while (I != nullptr) { | |||
799 | if (!I->empty()) { | |||
800 | NextPtr = &I->Next; | |||
801 | I = *NextPtr; | |||
802 | continue; | |||
803 | } | |||
804 | // Skip empty subranges until we find the first nonempty one. | |||
805 | do { | |||
806 | SubRange *Next = I->Next; | |||
807 | freeSubRange(I); | |||
808 | I = Next; | |||
809 | } while (I != nullptr && I->empty()); | |||
810 | *NextPtr = I; | |||
811 | } | |||
812 | } | |||
813 | ||||
814 | void LiveInterval::clearSubRanges() { | |||
815 | for (SubRange *I = SubRanges, *Next; I != nullptr; I = Next) { | |||
816 | Next = I->Next; | |||
817 | freeSubRange(I); | |||
818 | } | |||
819 | SubRanges = nullptr; | |||
820 | } | |||
821 | ||||
822 | /// Helper function for constructMainRangeFromSubranges(): Search the CFG | |||
823 | /// backwards until we find a place covered by a LiveRange segment that actually | |||
824 | /// has a valno set. | |||
825 | static VNInfo *searchForVNI(const SlotIndexes &Indexes, LiveRange &LR, | |||
826 | const MachineBasicBlock *MBB, | |||
827 | SmallPtrSetImpl<const MachineBasicBlock*> &Visited) { | |||
828 | // We start the search at the end of MBB. | |||
829 | SlotIndex EndIdx = Indexes.getMBBEndIdx(MBB); | |||
830 | // In our use case we can't live the area covered by the live segments without | |||
831 | // finding an actual VNI def. | |||
832 | LiveRange::iterator I = LR.find(EndIdx.getPrevSlot()); | |||
833 | assert(I != LR.end())((I != LR.end()) ? static_cast<void> (0) : __assert_fail ("I != LR.end()", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 833, __PRETTY_FUNCTION__)); | |||
834 | LiveRange::Segment &S = *I; | |||
835 | if (S.valno != nullptr) | |||
836 | return S.valno; | |||
837 | ||||
838 | VNInfo *VNI = nullptr; | |||
839 | // Continue at predecessors (we could even go to idom with domtree available). | |||
840 | for (const MachineBasicBlock *Pred : MBB->predecessors()) { | |||
841 | // Avoid going in circles. | |||
842 | if (!Visited.insert(Pred).second) | |||
843 | continue; | |||
844 | ||||
845 | VNI = searchForVNI(Indexes, LR, Pred, Visited); | |||
846 | if (VNI != nullptr) { | |||
847 | S.valno = VNI; | |||
848 | break; | |||
849 | } | |||
850 | } | |||
851 | ||||
852 | return VNI; | |||
853 | } | |||
854 | ||||
855 | static void determineMissingVNIs(const SlotIndexes &Indexes, LiveInterval &LI) { | |||
856 | SmallPtrSet<const MachineBasicBlock*, 5> Visited; | |||
857 | ||||
858 | LiveRange::iterator OutIt; | |||
859 | VNInfo *PrevValNo = nullptr; | |||
860 | for (LiveRange::iterator I = LI.begin(), E = LI.end(); I != E; ++I) { | |||
861 | LiveRange::Segment &S = *I; | |||
862 | // Determine final VNI if necessary. | |||
863 | if (S.valno == nullptr) { | |||
864 | // This can only happen at the begin of a basic block. | |||
865 | assert(S.start.isBlock() && "valno should only be missing at block begin")((S.start.isBlock() && "valno should only be missing at block begin" ) ? static_cast<void> (0) : __assert_fail ("S.start.isBlock() && \"valno should only be missing at block begin\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 865, __PRETTY_FUNCTION__)); | |||
866 | ||||
867 | Visited.clear(); | |||
868 | const MachineBasicBlock *MBB = Indexes.getMBBFromIndex(S.start); | |||
869 | for (const MachineBasicBlock *Pred : MBB->predecessors()) { | |||
870 | VNInfo *VNI = searchForVNI(Indexes, LI, Pred, Visited); | |||
871 | if (VNI != nullptr) { | |||
872 | S.valno = VNI; | |||
873 | break; | |||
874 | } | |||
875 | } | |||
876 | assert(S.valno != nullptr && "could not determine valno")((S.valno != nullptr && "could not determine valno") ? static_cast<void> (0) : __assert_fail ("S.valno != nullptr && \"could not determine valno\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 876, __PRETTY_FUNCTION__)); | |||
877 | } | |||
878 | // Merge with previous segment if it has the same VNI. | |||
879 | if (PrevValNo == S.valno && OutIt->end == S.start) { | |||
880 | OutIt->end = S.end; | |||
881 | } else { | |||
882 | // Didn't merge. Move OutIt to next segment. | |||
883 | if (PrevValNo == nullptr) | |||
884 | OutIt = LI.begin(); | |||
885 | else | |||
886 | ++OutIt; | |||
887 | ||||
888 | if (OutIt != I) | |||
889 | *OutIt = *I; | |||
890 | PrevValNo = S.valno; | |||
891 | } | |||
892 | } | |||
893 | // If we merged some segments chop off the end. | |||
894 | ++OutIt; | |||
895 | LI.segments.erase(OutIt, LI.end()); | |||
896 | } | |||
897 | ||||
898 | void LiveInterval::constructMainRangeFromSubranges( | |||
899 | const SlotIndexes &Indexes, VNInfo::Allocator &VNIAllocator) { | |||
900 | // The basic observations on which this algorithm is based: | |||
901 | // - Each Def/ValNo in a subrange must have a corresponding def on the main | |||
902 | // range, but not further defs/valnos are necessary. | |||
903 | // - If any of the subranges is live at a point the main liverange has to be | |||
904 | // live too, conversily if no subrange is live the main range mustn't be | |||
905 | // live either. | |||
906 | // We do this by scanning through all the subranges simultaneously creating new | |||
907 | // segments in the main range as segments start/ends come up in the subranges. | |||
908 | assert(hasSubRanges() && "expected subranges to be present")((hasSubRanges() && "expected subranges to be present" ) ? static_cast<void> (0) : __assert_fail ("hasSubRanges() && \"expected subranges to be present\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 908, __PRETTY_FUNCTION__)); | |||
909 | assert(segments.empty() && valnos.empty() && "expected empty main range")((segments.empty() && valnos.empty() && "expected empty main range" ) ? static_cast<void> (0) : __assert_fail ("segments.empty() && valnos.empty() && \"expected empty main range\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 909, __PRETTY_FUNCTION__)); | |||
910 | ||||
911 | // Collect subrange, iterator pairs for the walk and determine first and last | |||
912 | // SlotIndex involved. | |||
913 | SmallVector<std::pair<const SubRange*, const_iterator>, 4> SRs; | |||
914 | SlotIndex First; | |||
915 | SlotIndex Last; | |||
916 | for (const SubRange &SR : subranges()) { | |||
917 | if (SR.empty()) | |||
| ||||
918 | continue; | |||
919 | SRs.push_back(std::make_pair(&SR, SR.begin())); | |||
920 | if (!First.isValid() || SR.segments.front().start < First) | |||
921 | First = SR.segments.front().start; | |||
922 | if (!Last.isValid() || SR.segments.back().end > Last) | |||
923 | Last = SR.segments.back().end; | |||
924 | } | |||
925 | ||||
926 | // Walk over all subranges simultaneously. | |||
927 | Segment CurrentSegment; | |||
928 | bool ConstructingSegment = false; | |||
929 | bool NeedVNIFixup = false; | |||
930 | LaneBitmask ActiveMask = 0; | |||
931 | SlotIndex Pos = First; | |||
932 | while (true) { | |||
933 | SlotIndex NextPos = Last; | |||
934 | enum { | |||
935 | NOTHING, | |||
936 | BEGIN_SEGMENT, | |||
937 | END_SEGMENT, | |||
938 | } Event = NOTHING; | |||
939 | // Which subregister lanes are affected by the current event. | |||
940 | LaneBitmask EventMask = 0; | |||
941 | // Whether a BEGIN_SEGMENT is also a valno definition point. | |||
942 | bool IsDef = false; | |||
943 | // Find the next begin or end of a subrange segment. Combine masks if we | |||
944 | // have multiple begins/ends at the same position. Ends take precedence over | |||
945 | // Begins. | |||
946 | for (auto &SRP : SRs) { | |||
947 | const SubRange &SR = *SRP.first; | |||
948 | const_iterator &I = SRP.second; | |||
949 | // Advance iterator of subrange to a segment involving Pos; the earlier | |||
950 | // segments are already merged at this point. | |||
951 | while (I != SR.end() && | |||
952 | (I->end < Pos || | |||
953 | (I->end == Pos && (ActiveMask & SR.LaneMask) == 0))) | |||
954 | ++I; | |||
955 | if (I == SR.end()) | |||
956 | continue; | |||
957 | if ((ActiveMask & SR.LaneMask) == 0 && | |||
958 | Pos <= I->start && I->start <= NextPos) { | |||
959 | // Merge multiple begins at the same position. | |||
960 | if (I->start == NextPos && Event == BEGIN_SEGMENT) { | |||
961 | EventMask |= SR.LaneMask; | |||
962 | IsDef |= I->valno->def == I->start; | |||
963 | } else if (I->start < NextPos || Event != END_SEGMENT) { | |||
964 | Event = BEGIN_SEGMENT; | |||
965 | NextPos = I->start; | |||
966 | EventMask = SR.LaneMask; | |||
967 | IsDef = I->valno->def == I->start; | |||
968 | } | |||
969 | } | |||
970 | if ((ActiveMask & SR.LaneMask) != 0 && | |||
971 | Pos <= I->end && I->end <= NextPos) { | |||
972 | // Merge multiple ends at the same position. | |||
973 | if (I->end == NextPos && Event == END_SEGMENT) | |||
974 | EventMask |= SR.LaneMask; | |||
975 | else { | |||
976 | Event = END_SEGMENT; | |||
977 | NextPos = I->end; | |||
978 | EventMask = SR.LaneMask; | |||
979 | } | |||
980 | } | |||
981 | } | |||
982 | ||||
983 | // Advance scan position. | |||
984 | Pos = NextPos; | |||
985 | if (Event == BEGIN_SEGMENT) { | |||
986 | if (ConstructingSegment && IsDef) { | |||
987 | // Finish previous segment because we have to start a new one. | |||
988 | CurrentSegment.end = Pos; | |||
989 | append(CurrentSegment); | |||
990 | ConstructingSegment = false; | |||
991 | } | |||
992 | ||||
993 | // Start a new segment if necessary. | |||
994 | if (!ConstructingSegment) { | |||
995 | // Determine value number for the segment. | |||
996 | VNInfo *VNI; | |||
997 | if (IsDef) { | |||
998 | VNI = getNextValue(Pos, VNIAllocator); | |||
999 | } else { | |||
1000 | // We have to reuse an existing value number, if we are lucky | |||
1001 | // then we already passed one of the predecessor blocks and determined | |||
1002 | // its value number (with blocks in reverse postorder this would be | |||
1003 | // always true but we have no such guarantee). | |||
1004 | assert(Pos.isBlock())((Pos.isBlock()) ? static_cast<void> (0) : __assert_fail ("Pos.isBlock()", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 1004, __PRETTY_FUNCTION__)); | |||
1005 | const MachineBasicBlock *MBB = Indexes.getMBBFromIndex(Pos); | |||
1006 | // See if any of the predecessor blocks has a lower number and a VNI | |||
1007 | for (const MachineBasicBlock *Pred : MBB->predecessors()) { | |||
1008 | SlotIndex PredEnd = Indexes.getMBBEndIdx(Pred); | |||
1009 | VNI = getVNInfoBefore(PredEnd); | |||
1010 | if (VNI != nullptr) | |||
1011 | break; | |||
1012 | } | |||
1013 | // Def will come later: We have to do an extra fixup pass. | |||
1014 | if (VNI == nullptr) | |||
| ||||
1015 | NeedVNIFixup = true; | |||
1016 | } | |||
1017 | ||||
1018 | // In rare cases we can produce adjacent segments with the same value | |||
1019 | // number (if they come from different subranges, but happen to have | |||
1020 | // the same defining instruction). VNIFixup will fix those cases. | |||
1021 | if (!empty() && segments.back().end == Pos && | |||
1022 | segments.back().valno == VNI) | |||
1023 | NeedVNIFixup = true; | |||
1024 | CurrentSegment.start = Pos; | |||
1025 | CurrentSegment.valno = VNI; | |||
1026 | ConstructingSegment = true; | |||
1027 | } | |||
1028 | ActiveMask |= EventMask; | |||
1029 | } else if (Event == END_SEGMENT) { | |||
1030 | assert(ConstructingSegment)((ConstructingSegment) ? static_cast<void> (0) : __assert_fail ("ConstructingSegment", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 1030, __PRETTY_FUNCTION__)); | |||
1031 | // Finish segment if no lane is active anymore. | |||
1032 | ActiveMask &= ~EventMask; | |||
1033 | if (ActiveMask == 0) { | |||
1034 | CurrentSegment.end = Pos; | |||
1035 | append(CurrentSegment); | |||
1036 | ConstructingSegment = false; | |||
1037 | } | |||
1038 | } else { | |||
1039 | // We reached the end of the last subranges and can stop. | |||
1040 | assert(Event == NOTHING)((Event == NOTHING) ? static_cast<void> (0) : __assert_fail ("Event == NOTHING", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 1040, __PRETTY_FUNCTION__)); | |||
1041 | break; | |||
1042 | } | |||
1043 | } | |||
1044 | ||||
1045 | // We might not be able to assign new valnos for all segments if the basic | |||
1046 | // block containing the definition comes after a segment using the valno. | |||
1047 | // Do a fixup pass for this uncommon case. | |||
1048 | if (NeedVNIFixup) | |||
1049 | determineMissingVNIs(Indexes, *this); | |||
1050 | ||||
1051 | assert(ActiveMask == 0 && !ConstructingSegment && "all segments ended")((ActiveMask == 0 && !ConstructingSegment && "all segments ended" ) ? static_cast<void> (0) : __assert_fail ("ActiveMask == 0 && !ConstructingSegment && \"all segments ended\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 1051, __PRETTY_FUNCTION__)); | |||
1052 | verify(); | |||
1053 | } | |||
1054 | ||||
1055 | unsigned LiveInterval::getSize() const { | |||
1056 | unsigned Sum = 0; | |||
1057 | for (const Segment &S : segments) | |||
1058 | Sum += S.start.distance(S.end); | |||
1059 | return Sum; | |||
1060 | } | |||
1061 | ||||
1062 | raw_ostream& llvm::operator<<(raw_ostream& os, const LiveRange::Segment &S) { | |||
1063 | return os << '[' << S.start << ',' << S.end << ':' << S.valno->id << ")"; | |||
1064 | } | |||
1065 | ||||
1066 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) | |||
1067 | LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void LiveRange::Segment::dump() const { | |||
1068 | dbgs() << *this << "\n"; | |||
1069 | } | |||
1070 | #endif | |||
1071 | ||||
1072 | void LiveRange::print(raw_ostream &OS) const { | |||
1073 | if (empty()) | |||
1074 | OS << "EMPTY"; | |||
1075 | else { | |||
1076 | for (const Segment &S : segments) { | |||
1077 | OS << S; | |||
1078 | assert(S.valno == getValNumInfo(S.valno->id) && "Bad VNInfo")((S.valno == getValNumInfo(S.valno->id) && "Bad VNInfo" ) ? static_cast<void> (0) : __assert_fail ("S.valno == getValNumInfo(S.valno->id) && \"Bad VNInfo\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 1078, __PRETTY_FUNCTION__)); | |||
1079 | } | |||
1080 | } | |||
1081 | ||||
1082 | // Print value number info. | |||
1083 | if (getNumValNums()) { | |||
1084 | OS << " "; | |||
1085 | unsigned vnum = 0; | |||
1086 | for (const_vni_iterator i = vni_begin(), e = vni_end(); i != e; | |||
1087 | ++i, ++vnum) { | |||
1088 | const VNInfo *vni = *i; | |||
1089 | if (vnum) OS << " "; | |||
1090 | OS << vnum << "@"; | |||
1091 | if (vni->isUnused()) { | |||
1092 | OS << "x"; | |||
1093 | } else { | |||
1094 | OS << vni->def; | |||
1095 | if (vni->isPHIDef()) | |||
1096 | OS << "-phi"; | |||
1097 | } | |||
1098 | } | |||
1099 | } | |||
1100 | } | |||
1101 | ||||
1102 | void LiveInterval::print(raw_ostream &OS) const { | |||
1103 | OS << PrintReg(reg) << ' '; | |||
1104 | super::print(OS); | |||
1105 | // Print subranges | |||
1106 | for (const SubRange &SR : subranges()) { | |||
1107 | OS << " L" << PrintLaneMask(SR.LaneMask) << ' ' << SR; | |||
1108 | } | |||
1109 | } | |||
1110 | ||||
1111 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) | |||
1112 | LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void LiveRange::dump() const { | |||
1113 | dbgs() << *this << "\n"; | |||
1114 | } | |||
1115 | ||||
1116 | LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void LiveInterval::dump() const { | |||
1117 | dbgs() << *this << "\n"; | |||
1118 | } | |||
1119 | #endif | |||
1120 | ||||
1121 | #ifndef NDEBUG | |||
1122 | void LiveRange::verify() const { | |||
1123 | for (const_iterator I = begin(), E = end(); I != E; ++I) { | |||
1124 | assert(I->start.isValid())((I->start.isValid()) ? static_cast<void> (0) : __assert_fail ("I->start.isValid()", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 1124, __PRETTY_FUNCTION__)); | |||
1125 | assert(I->end.isValid())((I->end.isValid()) ? static_cast<void> (0) : __assert_fail ("I->end.isValid()", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 1125, __PRETTY_FUNCTION__)); | |||
1126 | assert(I->start < I->end)((I->start < I->end) ? static_cast<void> (0) : __assert_fail ("I->start < I->end", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 1126, __PRETTY_FUNCTION__)); | |||
1127 | assert(I->valno != nullptr)((I->valno != nullptr) ? static_cast<void> (0) : __assert_fail ("I->valno != nullptr", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 1127, __PRETTY_FUNCTION__)); | |||
1128 | assert(I->valno->id < valnos.size())((I->valno->id < valnos.size()) ? static_cast<void > (0) : __assert_fail ("I->valno->id < valnos.size()" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 1128, __PRETTY_FUNCTION__)); | |||
1129 | assert(I->valno == valnos[I->valno->id])((I->valno == valnos[I->valno->id]) ? static_cast< void> (0) : __assert_fail ("I->valno == valnos[I->valno->id]" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 1129, __PRETTY_FUNCTION__)); | |||
1130 | if (std::next(I) != E) { | |||
1131 | assert(I->end <= std::next(I)->start)((I->end <= std::next(I)->start) ? static_cast<void > (0) : __assert_fail ("I->end <= std::next(I)->start" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 1131, __PRETTY_FUNCTION__)); | |||
1132 | if (I->end == std::next(I)->start) | |||
1133 | assert(I->valno != std::next(I)->valno)((I->valno != std::next(I)->valno) ? static_cast<void > (0) : __assert_fail ("I->valno != std::next(I)->valno" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 1133, __PRETTY_FUNCTION__)); | |||
1134 | } | |||
1135 | } | |||
1136 | } | |||
1137 | ||||
1138 | void LiveInterval::verify(const MachineRegisterInfo *MRI) const { | |||
1139 | super::verify(); | |||
1140 | ||||
1141 | // Make sure SubRanges are fine and LaneMasks are disjunct. | |||
1142 | LaneBitmask Mask = 0; | |||
1143 | LaneBitmask MaxMask = MRI != nullptr ? MRI->getMaxLaneMaskForVReg(reg) : ~0u; | |||
1144 | for (const SubRange &SR : subranges()) { | |||
1145 | // Subrange lanemask should be disjunct to any previous subrange masks. | |||
1146 | assert((Mask & SR.LaneMask) == 0)(((Mask & SR.LaneMask) == 0) ? static_cast<void> (0 ) : __assert_fail ("(Mask & SR.LaneMask) == 0", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 1146, __PRETTY_FUNCTION__)); | |||
1147 | Mask |= SR.LaneMask; | |||
1148 | ||||
1149 | // subrange mask should not contained in maximum lane mask for the vreg. | |||
1150 | assert((Mask & ~MaxMask) == 0)(((Mask & ~MaxMask) == 0) ? static_cast<void> (0) : __assert_fail ("(Mask & ~MaxMask) == 0", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 1150, __PRETTY_FUNCTION__)); | |||
1151 | // empty subranges must be removed. | |||
1152 | assert(!SR.empty())((!SR.empty()) ? static_cast<void> (0) : __assert_fail ( "!SR.empty()", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 1152, __PRETTY_FUNCTION__)); | |||
1153 | ||||
1154 | SR.verify(); | |||
1155 | // Main liverange should cover subrange. | |||
1156 | assert(covers(SR))((covers(SR)) ? static_cast<void> (0) : __assert_fail ( "covers(SR)", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 1156, __PRETTY_FUNCTION__)); | |||
1157 | } | |||
1158 | } | |||
1159 | #endif | |||
1160 | ||||
1161 | ||||
1162 | //===----------------------------------------------------------------------===// | |||
1163 | // LiveRangeUpdater class | |||
1164 | //===----------------------------------------------------------------------===// | |||
1165 | // | |||
1166 | // The LiveRangeUpdater class always maintains these invariants: | |||
1167 | // | |||
1168 | // - When LastStart is invalid, Spills is empty and the iterators are invalid. | |||
1169 | // This is the initial state, and the state created by flush(). | |||
1170 | // In this state, isDirty() returns false. | |||
1171 | // | |||
1172 | // Otherwise, segments are kept in three separate areas: | |||
1173 | // | |||
1174 | // 1. [begin; WriteI) at the front of LR. | |||
1175 | // 2. [ReadI; end) at the back of LR. | |||
1176 | // 3. Spills. | |||
1177 | // | |||
1178 | // - LR.begin() <= WriteI <= ReadI <= LR.end(). | |||
1179 | // - Segments in all three areas are fully ordered and coalesced. | |||
1180 | // - Segments in area 1 precede and can't coalesce with segments in area 2. | |||
1181 | // - Segments in Spills precede and can't coalesce with segments in area 2. | |||
1182 | // - No coalescing is possible between segments in Spills and segments in area | |||
1183 | // 1, and there are no overlapping segments. | |||
1184 | // | |||
1185 | // The segments in Spills are not ordered with respect to the segments in area | |||
1186 | // 1. They need to be merged. | |||
1187 | // | |||
1188 | // When they exist, Spills.back().start <= LastStart, | |||
1189 | // and WriteI[-1].start <= LastStart. | |||
1190 | ||||
1191 | void LiveRangeUpdater::print(raw_ostream &OS) const { | |||
1192 | if (!isDirty()) { | |||
1193 | if (LR) | |||
1194 | OS << "Clean updater: " << *LR << '\n'; | |||
1195 | else | |||
1196 | OS << "Null updater.\n"; | |||
1197 | return; | |||
1198 | } | |||
1199 | assert(LR && "Can't have null LR in dirty updater.")((LR && "Can't have null LR in dirty updater.") ? static_cast <void> (0) : __assert_fail ("LR && \"Can't have null LR in dirty updater.\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 1199, __PRETTY_FUNCTION__)); | |||
1200 | OS << " updater with gap = " << (ReadI - WriteI) | |||
1201 | << ", last start = " << LastStart | |||
1202 | << ":\n Area 1:"; | |||
1203 | for (const auto &S : make_range(LR->begin(), WriteI)) | |||
1204 | OS << ' ' << S; | |||
1205 | OS << "\n Spills:"; | |||
1206 | for (unsigned I = 0, E = Spills.size(); I != E; ++I) | |||
1207 | OS << ' ' << Spills[I]; | |||
1208 | OS << "\n Area 2:"; | |||
1209 | for (const auto &S : make_range(ReadI, LR->end())) | |||
1210 | OS << ' ' << S; | |||
1211 | OS << '\n'; | |||
1212 | } | |||
1213 | ||||
1214 | LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void LiveRangeUpdater::dump() const { | |||
1215 | print(errs()); | |||
1216 | } | |||
1217 | ||||
1218 | // Determine if A and B should be coalesced. | |||
1219 | static inline bool coalescable(const LiveRange::Segment &A, | |||
1220 | const LiveRange::Segment &B) { | |||
1221 | assert(A.start <= B.start && "Unordered live segments.")((A.start <= B.start && "Unordered live segments." ) ? static_cast<void> (0) : __assert_fail ("A.start <= B.start && \"Unordered live segments.\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 1221, __PRETTY_FUNCTION__)); | |||
1222 | if (A.end == B.start) | |||
1223 | return A.valno == B.valno; | |||
1224 | if (A.end < B.start) | |||
1225 | return false; | |||
1226 | assert(A.valno == B.valno && "Cannot overlap different values")((A.valno == B.valno && "Cannot overlap different values" ) ? static_cast<void> (0) : __assert_fail ("A.valno == B.valno && \"Cannot overlap different values\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 1226, __PRETTY_FUNCTION__)); | |||
1227 | return true; | |||
1228 | } | |||
1229 | ||||
1230 | void LiveRangeUpdater::add(LiveRange::Segment Seg) { | |||
1231 | assert(LR && "Cannot add to a null destination")((LR && "Cannot add to a null destination") ? static_cast <void> (0) : __assert_fail ("LR && \"Cannot add to a null destination\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 1231, __PRETTY_FUNCTION__)); | |||
1232 | ||||
1233 | // Fall back to the regular add method if the live range | |||
1234 | // is using the segment set instead of the segment vector. | |||
1235 | if (LR->segmentSet != nullptr) { | |||
1236 | LR->addSegmentToSet(Seg); | |||
1237 | return; | |||
1238 | } | |||
1239 | ||||
1240 | // Flush the state if Start moves backwards. | |||
1241 | if (!LastStart.isValid() || LastStart > Seg.start) { | |||
1242 | if (isDirty()) | |||
1243 | flush(); | |||
1244 | // This brings us to an uninitialized state. Reinitialize. | |||
1245 | assert(Spills.empty() && "Leftover spilled segments")((Spills.empty() && "Leftover spilled segments") ? static_cast <void> (0) : __assert_fail ("Spills.empty() && \"Leftover spilled segments\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 1245, __PRETTY_FUNCTION__)); | |||
1246 | WriteI = ReadI = LR->begin(); | |||
1247 | } | |||
1248 | ||||
1249 | // Remember start for next time. | |||
1250 | LastStart = Seg.start; | |||
1251 | ||||
1252 | // Advance ReadI until it ends after Seg.start. | |||
1253 | LiveRange::iterator E = LR->end(); | |||
1254 | if (ReadI != E && ReadI->end <= Seg.start) { | |||
1255 | // First try to close the gap between WriteI and ReadI with spills. | |||
1256 | if (ReadI != WriteI) | |||
1257 | mergeSpills(); | |||
1258 | // Then advance ReadI. | |||
1259 | if (ReadI == WriteI) | |||
1260 | ReadI = WriteI = LR->find(Seg.start); | |||
1261 | else | |||
1262 | while (ReadI != E && ReadI->end <= Seg.start) | |||
1263 | *WriteI++ = *ReadI++; | |||
1264 | } | |||
1265 | ||||
1266 | assert(ReadI == E || ReadI->end > Seg.start)((ReadI == E || ReadI->end > Seg.start) ? static_cast< void> (0) : __assert_fail ("ReadI == E || ReadI->end > Seg.start" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 1266, __PRETTY_FUNCTION__)); | |||
1267 | ||||
1268 | // Check if the ReadI segment begins early. | |||
1269 | if (ReadI != E && ReadI->start <= Seg.start) { | |||
1270 | assert(ReadI->valno == Seg.valno && "Cannot overlap different values")((ReadI->valno == Seg.valno && "Cannot overlap different values" ) ? static_cast<void> (0) : __assert_fail ("ReadI->valno == Seg.valno && \"Cannot overlap different values\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 1270, __PRETTY_FUNCTION__)); | |||
1271 | // Bail if Seg is completely contained in ReadI. | |||
1272 | if (ReadI->end >= Seg.end) | |||
1273 | return; | |||
1274 | // Coalesce into Seg. | |||
1275 | Seg.start = ReadI->start; | |||
1276 | ++ReadI; | |||
1277 | } | |||
1278 | ||||
1279 | // Coalesce as much as possible from ReadI into Seg. | |||
1280 | while (ReadI != E && coalescable(Seg, *ReadI)) { | |||
1281 | Seg.end = std::max(Seg.end, ReadI->end); | |||
1282 | ++ReadI; | |||
1283 | } | |||
1284 | ||||
1285 | // Try coalescing Spills.back() into Seg. | |||
1286 | if (!Spills.empty() && coalescable(Spills.back(), Seg)) { | |||
1287 | Seg.start = Spills.back().start; | |||
1288 | Seg.end = std::max(Spills.back().end, Seg.end); | |||
1289 | Spills.pop_back(); | |||
1290 | } | |||
1291 | ||||
1292 | // Try coalescing Seg into WriteI[-1]. | |||
1293 | if (WriteI != LR->begin() && coalescable(WriteI[-1], Seg)) { | |||
1294 | WriteI[-1].end = std::max(WriteI[-1].end, Seg.end); | |||
1295 | return; | |||
1296 | } | |||
1297 | ||||
1298 | // Seg doesn't coalesce with anything, and needs to be inserted somewhere. | |||
1299 | if (WriteI != ReadI) { | |||
1300 | *WriteI++ = Seg; | |||
1301 | return; | |||
1302 | } | |||
1303 | ||||
1304 | // Finally, append to LR or Spills. | |||
1305 | if (WriteI == E) { | |||
1306 | LR->segments.push_back(Seg); | |||
1307 | WriteI = ReadI = LR->end(); | |||
1308 | } else | |||
1309 | Spills.push_back(Seg); | |||
1310 | } | |||
1311 | ||||
1312 | // Merge as many spilled segments as possible into the gap between WriteI | |||
1313 | // and ReadI. Advance WriteI to reflect the inserted instructions. | |||
1314 | void LiveRangeUpdater::mergeSpills() { | |||
1315 | // Perform a backwards merge of Spills and [SpillI;WriteI). | |||
1316 | size_t GapSize = ReadI - WriteI; | |||
1317 | size_t NumMoved = std::min(Spills.size(), GapSize); | |||
1318 | LiveRange::iterator Src = WriteI; | |||
1319 | LiveRange::iterator Dst = Src + NumMoved; | |||
1320 | LiveRange::iterator SpillSrc = Spills.end(); | |||
1321 | LiveRange::iterator B = LR->begin(); | |||
1322 | ||||
1323 | // This is the new WriteI position after merging spills. | |||
1324 | WriteI = Dst; | |||
1325 | ||||
1326 | // Now merge Src and Spills backwards. | |||
1327 | while (Src != Dst) { | |||
1328 | if (Src != B && Src[-1].start > SpillSrc[-1].start) | |||
1329 | *--Dst = *--Src; | |||
1330 | else | |||
1331 | *--Dst = *--SpillSrc; | |||
1332 | } | |||
1333 | assert(NumMoved == size_t(Spills.end() - SpillSrc))((NumMoved == size_t(Spills.end() - SpillSrc)) ? static_cast< void> (0) : __assert_fail ("NumMoved == size_t(Spills.end() - SpillSrc)" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 1333, __PRETTY_FUNCTION__)); | |||
1334 | Spills.erase(SpillSrc, Spills.end()); | |||
1335 | } | |||
1336 | ||||
1337 | void LiveRangeUpdater::flush() { | |||
1338 | if (!isDirty()) | |||
1339 | return; | |||
1340 | // Clear the dirty state. | |||
1341 | LastStart = SlotIndex(); | |||
1342 | ||||
1343 | assert(LR && "Cannot add to a null destination")((LR && "Cannot add to a null destination") ? static_cast <void> (0) : __assert_fail ("LR && \"Cannot add to a null destination\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 1343, __PRETTY_FUNCTION__)); | |||
1344 | ||||
1345 | // Nothing to merge? | |||
1346 | if (Spills.empty()) { | |||
1347 | LR->segments.erase(WriteI, ReadI); | |||
1348 | LR->verify(); | |||
1349 | return; | |||
1350 | } | |||
1351 | ||||
1352 | // Resize the WriteI - ReadI gap to match Spills. | |||
1353 | size_t GapSize = ReadI - WriteI; | |||
1354 | if (GapSize < Spills.size()) { | |||
1355 | // The gap is too small. Make some room. | |||
1356 | size_t WritePos = WriteI - LR->begin(); | |||
1357 | LR->segments.insert(ReadI, Spills.size() - GapSize, LiveRange::Segment()); | |||
1358 | // This also invalidated ReadI, but it is recomputed below. | |||
1359 | WriteI = LR->begin() + WritePos; | |||
1360 | } else { | |||
1361 | // Shrink the gap if necessary. | |||
1362 | LR->segments.erase(WriteI + Spills.size(), ReadI); | |||
1363 | } | |||
1364 | ReadI = WriteI + Spills.size(); | |||
1365 | mergeSpills(); | |||
1366 | LR->verify(); | |||
1367 | } | |||
1368 | ||||
1369 | unsigned ConnectedVNInfoEqClasses::Classify(const LiveRange &LR) { | |||
1370 | // Create initial equivalence classes. | |||
1371 | EqClass.clear(); | |||
1372 | EqClass.grow(LR.getNumValNums()); | |||
1373 | ||||
1374 | const VNInfo *used = nullptr, *unused = nullptr; | |||
1375 | ||||
1376 | // Determine connections. | |||
1377 | for (const VNInfo *VNI : LR.valnos) { | |||
1378 | // Group all unused values into one class. | |||
1379 | if (VNI->isUnused()) { | |||
1380 | if (unused) | |||
1381 | EqClass.join(unused->id, VNI->id); | |||
1382 | unused = VNI; | |||
1383 | continue; | |||
1384 | } | |||
1385 | used = VNI; | |||
1386 | if (VNI->isPHIDef()) { | |||
1387 | const MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def); | |||
1388 | assert(MBB && "Phi-def has no defining MBB")((MBB && "Phi-def has no defining MBB") ? static_cast <void> (0) : __assert_fail ("MBB && \"Phi-def has no defining MBB\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 1388, __PRETTY_FUNCTION__)); | |||
1389 | // Connect to values live out of predecessors. | |||
1390 | for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), | |||
1391 | PE = MBB->pred_end(); PI != PE; ++PI) | |||
1392 | if (const VNInfo *PVNI = LR.getVNInfoBefore(LIS.getMBBEndIdx(*PI))) | |||
1393 | EqClass.join(VNI->id, PVNI->id); | |||
1394 | } else { | |||
1395 | // Normal value defined by an instruction. Check for two-addr redef. | |||
1396 | // FIXME: This could be coincidental. Should we really check for a tied | |||
1397 | // operand constraint? | |||
1398 | // Note that VNI->def may be a use slot for an early clobber def. | |||
1399 | if (const VNInfo *UVNI = LR.getVNInfoBefore(VNI->def)) | |||
1400 | EqClass.join(VNI->id, UVNI->id); | |||
1401 | } | |||
1402 | } | |||
1403 | ||||
1404 | // Lump all the unused values in with the last used value. | |||
1405 | if (used && unused) | |||
1406 | EqClass.join(used->id, unused->id); | |||
1407 | ||||
1408 | EqClass.compress(); | |||
1409 | return EqClass.getNumClasses(); | |||
1410 | } | |||
1411 | ||||
1412 | template<typename LiveRangeT, typename EqClassesT> | |||
1413 | static void DistributeRange(LiveRangeT &LR, LiveRangeT *SplitLRs[], | |||
1414 | EqClassesT VNIClasses) { | |||
1415 | // Move segments to new intervals. | |||
1416 | LiveRange::iterator J = LR.begin(), E = LR.end(); | |||
1417 | while (J != E && VNIClasses[J->valno->id] == 0) | |||
1418 | ++J; | |||
1419 | for (LiveRange::iterator I = J; I != E; ++I) { | |||
1420 | if (unsigned eq = VNIClasses[I->valno->id]) { | |||
1421 | assert((SplitLRs[eq-1]->empty() || SplitLRs[eq-1]->expiredAt(I->start)) &&(((SplitLRs[eq-1]->empty() || SplitLRs[eq-1]->expiredAt (I->start)) && "New intervals should be empty") ? static_cast <void> (0) : __assert_fail ("(SplitLRs[eq-1]->empty() || SplitLRs[eq-1]->expiredAt(I->start)) && \"New intervals should be empty\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 1422, __PRETTY_FUNCTION__)) | |||
1422 | "New intervals should be empty")(((SplitLRs[eq-1]->empty() || SplitLRs[eq-1]->expiredAt (I->start)) && "New intervals should be empty") ? static_cast <void> (0) : __assert_fail ("(SplitLRs[eq-1]->empty() || SplitLRs[eq-1]->expiredAt(I->start)) && \"New intervals should be empty\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 1422, __PRETTY_FUNCTION__)); | |||
1423 | SplitLRs[eq-1]->segments.push_back(*I); | |||
1424 | } else | |||
1425 | *J++ = *I; | |||
1426 | } | |||
1427 | LR.segments.erase(J, E); | |||
1428 | ||||
1429 | // Transfer VNInfos to their new owners and renumber them. | |||
1430 | unsigned j = 0, e = LR.getNumValNums(); | |||
1431 | while (j != e && VNIClasses[j] == 0) | |||
1432 | ++j; | |||
1433 | for (unsigned i = j; i != e; ++i) { | |||
1434 | VNInfo *VNI = LR.getValNumInfo(i); | |||
1435 | if (unsigned eq = VNIClasses[i]) { | |||
1436 | VNI->id = SplitLRs[eq-1]->getNumValNums(); | |||
1437 | SplitLRs[eq-1]->valnos.push_back(VNI); | |||
1438 | } else { | |||
1439 | VNI->id = j; | |||
1440 | LR.valnos[j++] = VNI; | |||
1441 | } | |||
1442 | } | |||
1443 | LR.valnos.resize(j); | |||
1444 | } | |||
1445 | ||||
1446 | void ConnectedVNInfoEqClasses::Distribute(LiveInterval &LI, LiveInterval *LIV[], | |||
1447 | MachineRegisterInfo &MRI) { | |||
1448 | // Rewrite instructions. | |||
1449 | for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(LI.reg), | |||
1450 | RE = MRI.reg_end(); RI != RE;) { | |||
1451 | MachineOperand &MO = *RI; | |||
1452 | MachineInstr *MI = RI->getParent(); | |||
1453 | ++RI; | |||
1454 | // DBG_VALUE instructions don't have slot indexes, so get the index of the | |||
1455 | // instruction before them. | |||
1456 | // Normally, DBG_VALUE instructions are removed before this function is | |||
1457 | // called, but it is not a requirement. | |||
1458 | SlotIndex Idx; | |||
1459 | if (MI->isDebugValue()) | |||
1460 | Idx = LIS.getSlotIndexes()->getIndexBefore(*MI); | |||
1461 | else | |||
1462 | Idx = LIS.getInstructionIndex(*MI); | |||
1463 | LiveQueryResult LRQ = LI.Query(Idx); | |||
1464 | const VNInfo *VNI = MO.readsReg() ? LRQ.valueIn() : LRQ.valueDefined(); | |||
1465 | // In the case of an <undef> use that isn't tied to any def, VNI will be | |||
1466 | // NULL. If the use is tied to a def, VNI will be the defined value. | |||
1467 | if (!VNI) | |||
1468 | continue; | |||
1469 | if (unsigned EqClass = getEqClass(VNI)) | |||
1470 | MO.setReg(LIV[EqClass-1]->reg); | |||
1471 | } | |||
1472 | ||||
1473 | // Distribute subregister liveranges. | |||
1474 | if (LI.hasSubRanges()) { | |||
1475 | unsigned NumComponents = EqClass.getNumClasses(); | |||
1476 | SmallVector<unsigned, 8> VNIMapping; | |||
1477 | SmallVector<LiveInterval::SubRange*, 8> SubRanges; | |||
1478 | BumpPtrAllocator &Allocator = LIS.getVNInfoAllocator(); | |||
1479 | for (LiveInterval::SubRange &SR : LI.subranges()) { | |||
1480 | // Create new subranges in the split intervals and construct a mapping | |||
1481 | // for the VNInfos in the subrange. | |||
1482 | unsigned NumValNos = SR.valnos.size(); | |||
1483 | VNIMapping.clear(); | |||
1484 | VNIMapping.reserve(NumValNos); | |||
1485 | SubRanges.clear(); | |||
1486 | SubRanges.resize(NumComponents-1, nullptr); | |||
1487 | for (unsigned I = 0; I < NumValNos; ++I) { | |||
1488 | const VNInfo &VNI = *SR.valnos[I]; | |||
1489 | unsigned ComponentNum; | |||
1490 | if (VNI.isUnused()) { | |||
1491 | ComponentNum = 0; | |||
1492 | } else { | |||
1493 | const VNInfo *MainRangeVNI = LI.getVNInfoAt(VNI.def); | |||
1494 | assert(MainRangeVNI != nullptr((MainRangeVNI != nullptr && "SubRange def must have corresponding main range def" ) ? static_cast<void> (0) : __assert_fail ("MainRangeVNI != nullptr && \"SubRange def must have corresponding main range def\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 1495, __PRETTY_FUNCTION__)) | |||
1495 | && "SubRange def must have corresponding main range def")((MainRangeVNI != nullptr && "SubRange def must have corresponding main range def" ) ? static_cast<void> (0) : __assert_fail ("MainRangeVNI != nullptr && \"SubRange def must have corresponding main range def\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270290/lib/CodeGen/LiveInterval.cpp" , 1495, __PRETTY_FUNCTION__)); | |||
1496 | ComponentNum = getEqClass(MainRangeVNI); | |||
1497 | if (ComponentNum > 0 && SubRanges[ComponentNum-1] == nullptr) { | |||
1498 | SubRanges[ComponentNum-1] | |||
1499 | = LIV[ComponentNum-1]->createSubRange(Allocator, SR.LaneMask); | |||
1500 | } | |||
1501 | } | |||
1502 | VNIMapping.push_back(ComponentNum); | |||
1503 | } | |||
1504 | DistributeRange(SR, SubRanges.data(), VNIMapping); | |||
1505 | } | |||
1506 | LI.removeEmptySubRanges(); | |||
1507 | } | |||
1508 | ||||
1509 | // Distribute main liverange. | |||
1510 | DistributeRange(LI, LIV, EqClass); | |||
1511 | } | |||
1512 | ||||
1513 | void ConnectedSubRegClasses::renameComponents(LiveInterval &LI) const { | |||
1514 | // Shortcut: We cannot have split components with a single definition. | |||
1515 | if (LI.valnos.size() < 2) | |||
1516 | return; | |||
1517 | ||||
1518 | SmallVector<SubRangeInfo, 4> SubRangeInfos; | |||
1519 | IntEqClasses Classes; | |||
1520 | if (!findComponents(Classes, SubRangeInfos, LI)) | |||
1521 | return; | |||
1522 | ||||
1523 | // Create a new VReg for each class. | |||
1524 | unsigned Reg = LI.reg; | |||
1525 | const TargetRegisterClass *RegClass = MRI.getRegClass(Reg); | |||
1526 | SmallVector<LiveInterval*, 4> Intervals; | |||
1527 | Intervals.push_back(&LI); | |||
1528 | for (unsigned I = 1, NumClasses = Classes.getNumClasses(); I < NumClasses; | |||
1529 | ++I) { | |||
1530 | unsigned NewVReg = MRI.createVirtualRegister(RegClass); | |||
1531 | LiveInterval &NewLI = LIS.createEmptyInterval(NewVReg); | |||
1532 | Intervals.push_back(&NewLI); | |||
1533 | } | |||
1534 | ||||
1535 | rewriteOperands(Classes, SubRangeInfos, Intervals); | |||
1536 | distribute(Classes, SubRangeInfos, Intervals); | |||
1537 | computeMainRangesFixFlags(Classes, SubRangeInfos, Intervals); | |||
1538 | } | |||
1539 | ||||
1540 | bool ConnectedSubRegClasses::findComponents(IntEqClasses &Classes, | |||
1541 | SmallVectorImpl<ConnectedSubRegClasses::SubRangeInfo> &SubRangeInfos, | |||
1542 | LiveInterval &LI) const { | |||
1543 | // First step: Create connected components for the VNInfos inside the | |||
1544 | // subranges and count the global number of such components. | |||
1545 | unsigned NumComponents = 0; | |||
1546 | for (LiveInterval::SubRange &SR : LI.subranges()) { | |||
1547 | SubRangeInfos.push_back(SubRangeInfo(LIS, SR, NumComponents)); | |||
1548 | ConnectedVNInfoEqClasses &ConEQ = SubRangeInfos.back().ConEQ; | |||
1549 | ||||
1550 | unsigned NumSubComponents = ConEQ.Classify(SR); | |||
1551 | NumComponents += NumSubComponents; | |||
1552 | } | |||
1553 | // Shortcut: With only 1 subrange, the normal separate component tests are | |||
1554 | // enough and we do not need to perform the union-find on the subregister | |||
1555 | // segments. | |||
1556 | if (SubRangeInfos.size() < 2) | |||
1557 | return false; | |||
1558 | ||||
1559 | // Next step: Build union-find structure over all subranges and merge classes | |||
1560 | // across subranges when they are affected by the same MachineOperand. | |||
1561 | const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo(); | |||
1562 | Classes.grow(NumComponents); | |||
1563 | unsigned Reg = LI.reg; | |||
1564 | for (const MachineOperand &MO : MRI.reg_nodbg_operands(Reg)) { | |||
1565 | if (!MO.isDef() && !MO.readsReg()) | |||
1566 | continue; | |||
1567 | unsigned SubRegIdx = MO.getSubReg(); | |||
1568 | LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubRegIdx); | |||
1569 | unsigned MergedID = ~0u; | |||
1570 | for (ConnectedSubRegClasses::SubRangeInfo &SRInfo : SubRangeInfos) { | |||
1571 | const LiveInterval::SubRange &SR = *SRInfo.SR; | |||
1572 | if ((SR.LaneMask & LaneMask) == 0) | |||
1573 | continue; | |||
1574 | SlotIndex Pos = LIS.getInstructionIndex(*MO.getParent()); | |||
1575 | Pos = MO.isDef() ? Pos.getRegSlot(MO.isEarlyClobber()) | |||
1576 | : Pos.getBaseIndex(); | |||
1577 | const VNInfo *VNI = SR.getVNInfoAt(Pos); | |||
1578 | if (VNI == nullptr) | |||
1579 | continue; | |||
1580 | ||||
1581 | // Map to local representant ID. | |||
1582 | unsigned LocalID = SRInfo.ConEQ.getEqClass(VNI); | |||
1583 | // Global ID | |||
1584 | unsigned ID = LocalID + SRInfo.Index; | |||
1585 | // Merge other sets | |||
1586 | MergedID = MergedID == ~0u ? ID : Classes.join(MergedID, ID); | |||
1587 | } | |||
1588 | } | |||
1589 | ||||
1590 | // Early exit if we ended up with a single equivalence class. | |||
1591 | Classes.compress(); | |||
1592 | unsigned NumClasses = Classes.getNumClasses(); | |||
1593 | return NumClasses > 1; | |||
1594 | } | |||
1595 | ||||
1596 | void ConnectedSubRegClasses::rewriteOperands(const IntEqClasses &Classes, | |||
1597 | const SmallVectorImpl<SubRangeInfo> &SubRangeInfos, | |||
1598 | const SmallVectorImpl<LiveInterval*> &Intervals) const { | |||
1599 | const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo(); | |||
1600 | unsigned Reg = Intervals[0]->reg;; | |||
1601 | for (MachineRegisterInfo::reg_nodbg_iterator I = MRI.reg_nodbg_begin(Reg), | |||
1602 | E = MRI.reg_nodbg_end(); I != E; ) { | |||
1603 | MachineOperand &MO = *I++; | |||
1604 | if (!MO.isDef() && !MO.readsReg()) | |||
1605 | continue; | |||
1606 | ||||
1607 | MachineInstr &MI = *MO.getParent(); | |||
1608 | ||||
1609 | SlotIndex Pos = LIS.getInstructionIndex(MI); | |||
1610 | unsigned SubRegIdx = MO.getSubReg(); | |||
1611 | LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubRegIdx); | |||
1612 | ||||
1613 | unsigned ID = ~0u; | |||
1614 | for (const SubRangeInfo &SRInfo : SubRangeInfos) { | |||
1615 | const LiveInterval::SubRange &SR = *SRInfo.SR; | |||
1616 | if ((SR.LaneMask & LaneMask) == 0) | |||
1617 | continue; | |||
1618 | LiveRange::const_iterator I = SR.find(Pos); | |||
1619 | if (I == SR.end()) | |||
1620 | continue; | |||
1621 | ||||
1622 | const VNInfo &VNI = *I->valno; | |||
1623 | // Map to local representant ID. | |||
1624 | unsigned LocalID = SRInfo.ConEQ.getEqClass(&VNI); | |||
1625 | // Global ID | |||
1626 | ID = Classes[LocalID + SRInfo.Index]; | |||
1627 | break; | |||
1628 | } | |||
1629 | ||||
1630 | unsigned VReg = Intervals[ID]->reg; | |||
1631 | MO.setReg(VReg); | |||
1632 | } | |||
1633 | } | |||
1634 | ||||
1635 | void ConnectedSubRegClasses::distribute(const IntEqClasses &Classes, | |||
1636 | const SmallVectorImpl<SubRangeInfo> &SubRangeInfos, | |||
1637 | const SmallVectorImpl<LiveInterval*> &Intervals) const { | |||
1638 | unsigned NumClasses = Classes.getNumClasses(); | |||
1639 | SmallVector<unsigned, 8> VNIMapping; | |||
1640 | SmallVector<LiveInterval::SubRange*, 8> SubRanges; | |||
1641 | BumpPtrAllocator &Allocator = LIS.getVNInfoAllocator(); | |||
1642 | for (const SubRangeInfo &SRInfo : SubRangeInfos) { | |||
1643 | LiveInterval::SubRange &SR = *SRInfo.SR; | |||
1644 | unsigned NumValNos = SR.valnos.size(); | |||
1645 | VNIMapping.clear(); | |||
1646 | VNIMapping.reserve(NumValNos); | |||
1647 | SubRanges.clear(); | |||
1648 | SubRanges.resize(NumClasses-1, nullptr); | |||
1649 | for (unsigned I = 0; I < NumValNos; ++I) { | |||
1650 | const VNInfo &VNI = *SR.valnos[I]; | |||
1651 | unsigned LocalID = SRInfo.ConEQ.getEqClass(&VNI); | |||
1652 | unsigned ID = Classes[LocalID + SRInfo.Index]; | |||
1653 | VNIMapping.push_back(ID); | |||
1654 | if (ID > 0 && SubRanges[ID-1] == nullptr) | |||
1655 | SubRanges[ID-1] = Intervals[ID]->createSubRange(Allocator, SR.LaneMask); | |||
1656 | } | |||
1657 | DistributeRange(SR, SubRanges.data(), VNIMapping); | |||
1658 | } | |||
1659 | } | |||
1660 | ||||
1661 | static bool subRangeLiveAt(const LiveInterval &LI, SlotIndex Pos) { | |||
1662 | for (const LiveInterval::SubRange &SR : LI.subranges()) { | |||
1663 | if (SR.liveAt(Pos)) | |||
1664 | return true; | |||
1665 | } | |||
1666 | return false; | |||
1667 | } | |||
1668 | ||||
1669 | void ConnectedSubRegClasses::computeMainRangesFixFlags( | |||
1670 | const IntEqClasses &Classes, | |||
1671 | const SmallVectorImpl<SubRangeInfo> &SubRangeInfos, | |||
1672 | const SmallVectorImpl<LiveInterval*> &Intervals) const { | |||
1673 | BumpPtrAllocator &Allocator = LIS.getVNInfoAllocator(); | |||
1674 | const SlotIndexes &Indexes = *LIS.getSlotIndexes(); | |||
1675 | for (size_t I = 0, E = Intervals.size(); I < E; ++I) { | |||
1676 | LiveInterval &LI = *Intervals[I]; | |||
1677 | unsigned Reg = LI.reg; | |||
1678 | ||||
1679 | // There must be a def (or live-in) before every use. Splitting vregs may | |||
1680 | // violate this principle as the splitted vreg may not have a definition on | |||
1681 | // every path. Fix this by creating IMPLICIT_DEF instruction as necessary. | |||
1682 | VNInfo::Allocator &VNInfoAllocator = LIS.getVNInfoAllocator(); | |||
1683 | for (const LiveInterval::SubRange &SR : LI.subranges()) { | |||
1684 | // Search for "PHI" value numbers in the subranges. We must find a live | |||
1685 | // value in each predecessor block, add an IMPLICIT_DEF where it is | |||
1686 | // missing. | |||
1687 | for (unsigned I = 0; I < SR.valnos.size(); ++I) { | |||
1688 | const VNInfo &VNI = *SR.valnos[I]; | |||
1689 | if (VNI.isUnused() || !VNI.isPHIDef()) | |||
1690 | continue; | |||
1691 | ||||
1692 | SlotIndex Def = VNI.def; | |||
1693 | MachineBasicBlock &MBB = *Indexes.getMBBFromIndex(Def); | |||
1694 | for (MachineBasicBlock *PredMBB : MBB.predecessors()) { | |||
1695 | SlotIndex PredEnd = Indexes.getMBBEndIdx(PredMBB); | |||
1696 | if (subRangeLiveAt(LI, PredEnd.getPrevSlot())) | |||
1697 | continue; | |||
1698 | ||||
1699 | MachineBasicBlock::iterator InsertPos = | |||
1700 | llvm::findPHICopyInsertPoint(PredMBB, &MBB, Reg); | |||
1701 | const MCInstrDesc &MCDesc = TII.get(TargetOpcode::IMPLICIT_DEF); | |||
1702 | MachineInstrBuilder ImpDef = BuildMI(*PredMBB, InsertPos, | |||
1703 | DebugLoc(), MCDesc, Reg); | |||
1704 | SlotIndex DefIdx = LIS.InsertMachineInstrInMaps(*ImpDef); | |||
1705 | SlotIndex RegDefIdx = DefIdx.getRegSlot(); | |||
1706 | for (LiveInterval::SubRange &SR : LI.subranges()) { | |||
1707 | VNInfo *SRVNI = SR.getNextValue(RegDefIdx, VNInfoAllocator); | |||
1708 | SR.addSegment(LiveRange::Segment(RegDefIdx, PredEnd, SRVNI)); | |||
1709 | } | |||
1710 | } | |||
1711 | } | |||
1712 | } | |||
1713 | ||||
1714 | LI.removeEmptySubRanges(); | |||
1715 | if (I == 0) | |||
1716 | LI.clear(); | |||
1717 | LI.constructMainRangeFromSubranges(*LIS.getSlotIndexes(), Allocator); | |||
1718 | ||||
1719 | for (MachineOperand &MO : MRI.reg_nodbg_operands(Reg)) { | |||
1720 | if (!MO.isDef()) | |||
1721 | continue; | |||
1722 | unsigned SubRegIdx = MO.getSubReg(); | |||
1723 | if (SubRegIdx == 0) | |||
1724 | continue; | |||
1725 | // After assigning the new vreg we may not have any other sublanes living | |||
1726 | // in and out of the instruction anymore. We need to add new dead and kill | |||
1727 | // flags in these cases. | |||
1728 | if (!MO.isUndef()) { | |||
1729 | SlotIndex Pos = LIS.getInstructionIndex(*MO.getParent()); | |||
1730 | if (!LI.liveAt(Pos.getBaseIndex())) | |||
1731 | MO.setIsUndef(); | |||
1732 | } | |||
1733 | if (!MO.isDead()) { | |||
1734 | SlotIndex Pos = LIS.getInstructionIndex(*MO.getParent()); | |||
1735 | if (!LI.liveAt(Pos.getDeadSlot())) | |||
1736 | MO.setIsDead(); | |||
1737 | } | |||
1738 | } | |||
1739 | } | |||
1740 | } |