Line data Source code
1 : //===- llvm/CodeGen/LiveInterval.h - Interval representation ----*- C++ -*-===//
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 : #ifndef LLVM_CODEGEN_LIVEINTERVAL_H
22 : #define LLVM_CODEGEN_LIVEINTERVAL_H
23 :
24 : #include "llvm/ADT/ArrayRef.h"
25 : #include "llvm/ADT/IntEqClasses.h"
26 : #include "llvm/ADT/STLExtras.h"
27 : #include "llvm/ADT/SmallVector.h"
28 : #include "llvm/ADT/iterator_range.h"
29 : #include "llvm/CodeGen/SlotIndexes.h"
30 : #include "llvm/MC/LaneBitmask.h"
31 : #include "llvm/Support/Allocator.h"
32 : #include "llvm/Support/MathExtras.h"
33 : #include <algorithm>
34 : #include <cassert>
35 : #include <cstddef>
36 : #include <functional>
37 : #include <memory>
38 : #include <set>
39 : #include <tuple>
40 : #include <utility>
41 :
42 : namespace llvm {
43 :
44 : class CoalescerPair;
45 : class LiveIntervals;
46 : class MachineRegisterInfo;
47 : class raw_ostream;
48 :
49 : /// VNInfo - Value Number Information.
50 : /// This class holds information about a machine level values, including
51 : /// definition and use points.
52 : ///
53 : class VNInfo {
54 : public:
55 : using Allocator = BumpPtrAllocator;
56 :
57 : /// The ID number of this value.
58 : unsigned id;
59 :
60 : /// The index of the defining instruction.
61 : SlotIndex def;
62 :
63 : /// VNInfo constructor.
64 6088826 : VNInfo(unsigned i, SlotIndex d) : id(i), def(d) {}
65 :
66 : /// VNInfo constructor, copies values from orig, except for the value number.
67 0 : VNInfo(unsigned i, const VNInfo &orig) : id(i), def(orig.def) {}
68 :
69 : /// Copy from the parameter into this VNInfo.
70 0 : void copyFrom(VNInfo &src) {
71 4 : def = src.def;
72 0 : }
73 :
74 : /// Returns true if this value is defined by a PHI instruction (or was,
75 : /// PHI instructions may have been eliminated).
76 : /// PHI-defs begin at a block boundary, all other defs begin at register or
77 : /// EC slots.
78 : bool isPHIDef() const { return def.isBlock(); }
79 :
80 : /// Returns true if this value is unused.
81 : bool isUnused() const { return !def.isValid(); }
82 :
83 : /// Mark this value as unused.
84 9898 : void markUnused() { def = SlotIndex(); }
85 : };
86 :
87 : /// Result of a LiveRange query. This class hides the implementation details
88 : /// of live ranges, and it should be used as the primary interface for
89 : /// examining live ranges around instructions.
90 : class LiveQueryResult {
91 : VNInfo *const EarlyVal;
92 : VNInfo *const LateVal;
93 : const SlotIndex EndPoint;
94 : const bool Kill;
95 :
96 : public:
97 : LiveQueryResult(VNInfo *EarlyVal, VNInfo *LateVal, SlotIndex EndPoint,
98 : bool Kill)
99 1442878 : : EarlyVal(EarlyVal), LateVal(LateVal), EndPoint(EndPoint), Kill(Kill)
100 : {}
101 :
102 : /// Return the value that is live-in to the instruction. This is the value
103 : /// that will be read by the instruction's use operands. Return NULL if no
104 : /// value is live-in.
105 0 : VNInfo *valueIn() const {
106 0 : return EarlyVal;
107 : }
108 :
109 : /// Return true if the live-in value is killed by this instruction. This
110 : /// means that either the live range ends at the instruction, or it changes
111 : /// value.
112 0 : bool isKill() const {
113 0 : return Kill;
114 : }
115 :
116 : /// Return true if this instruction has a dead def.
117 : bool isDeadDef() const {
118 : return EndPoint.isDead();
119 : }
120 :
121 : /// Return the value leaving the instruction, if any. This can be a
122 : /// live-through value, or a live def. A dead def returns NULL.
123 : VNInfo *valueOut() const {
124 16 : return isDeadDef() ? nullptr : LateVal;
125 : }
126 :
127 : /// Returns the value alive at the end of the instruction, if any. This can
128 : /// be a live-through value, a live def or a dead def.
129 0 : VNInfo *valueOutOrDead() const {
130 0 : return LateVal;
131 : }
132 :
133 : /// Return the value defined by this instruction, if any. This includes
134 : /// dead defs, it is the value created by the instruction's def operands.
135 0 : VNInfo *valueDefined() const {
136 5480087 : return EarlyVal == LateVal ? nullptr : LateVal;
137 : }
138 :
139 : /// Return the end point of the last live range segment to interact with
140 : /// the instruction, if any.
141 : ///
142 : /// The end point is an invalid SlotIndex only if the live range doesn't
143 : /// intersect the instruction at all.
144 : ///
145 : /// The end point may be at or past the end of the instruction's basic
146 : /// block. That means the value was live out of the block.
147 0 : SlotIndex endPoint() const {
148 0 : return EndPoint;
149 : }
150 : };
151 :
152 : /// This class represents the liveness of a register, stack slot, etc.
153 : /// It manages an ordered list of Segment objects.
154 : /// The Segments are organized in a static single assignment form: At places
155 : /// where a new value is defined or different values reach a CFG join a new
156 : /// segment with a new value number is used.
157 : class LiveRange {
158 : public:
159 : /// This represents a simple continuous liveness interval for a value.
160 : /// The start point is inclusive, the end point exclusive. These intervals
161 : /// are rendered as [start,end).
162 : struct Segment {
163 : SlotIndex start; // Start point of the interval (inclusive)
164 : SlotIndex end; // End point of the interval (exclusive)
165 : VNInfo *valno = nullptr; // identifier for the value contained in this
166 : // segment.
167 :
168 : Segment() = default;
169 :
170 : Segment(SlotIndex S, SlotIndex E, VNInfo *V)
171 8650495 : : start(S), end(E), valno(V) {
172 : assert(S < E && "Cannot create empty or backwards segment");
173 : }
174 :
175 : /// Return true if the index is covered by this segment.
176 11055385 : bool contains(SlotIndex I) const {
177 11055385 : return start <= I && I < end;
178 : }
179 :
180 : /// Return true if the given interval, [S, E), is covered by this segment.
181 : bool containsInterval(SlotIndex S, SlotIndex E) const {
182 : assert((S < E) && "Backwards interval?");
183 : return (start <= S && S < end) && (start < E && E <= end);
184 : }
185 :
186 : bool operator<(const Segment &Other) const {
187 8322944 : return std::tie(start, end) < std::tie(Other.start, Other.end);
188 : }
189 : bool operator==(const Segment &Other) const {
190 : return start == Other.start && end == Other.end;
191 : }
192 :
193 : void dump() const;
194 : };
195 :
196 : using Segments = SmallVector<Segment, 2>;
197 : using VNInfoList = SmallVector<VNInfo *, 2>;
198 :
199 : Segments segments; // the liveness segments
200 : VNInfoList valnos; // value#'s
201 :
202 : // The segment set is used temporarily to accelerate initial computation
203 : // of live ranges of physical registers in computeRegUnitRange.
204 : // After that the set is flushed to the segment vector and deleted.
205 : using SegmentSet = std::set<Segment>;
206 : std::unique_ptr<SegmentSet> segmentSet;
207 :
208 : using iterator = Segments::iterator;
209 : using const_iterator = Segments::const_iterator;
210 :
211 : iterator begin() { return segments.begin(); }
212 : iterator end() { return segments.end(); }
213 :
214 : const_iterator begin() const { return segments.begin(); }
215 : const_iterator end() const { return segments.end(); }
216 :
217 : using vni_iterator = VNInfoList::iterator;
218 : using const_vni_iterator = VNInfoList::const_iterator;
219 :
220 : vni_iterator vni_begin() { return valnos.begin(); }
221 : vni_iterator vni_end() { return valnos.end(); }
222 :
223 : const_vni_iterator vni_begin() const { return valnos.begin(); }
224 : const_vni_iterator vni_end() const { return valnos.end(); }
225 :
226 : /// Constructs a new LiveRange object.
227 4451327 : LiveRange(bool UseSegmentSet = false)
228 4451327 : : segmentSet(UseSegmentSet ? llvm::make_unique<SegmentSet>()
229 4451327 : : nullptr) {}
230 :
231 : /// Constructs a new LiveRange object by copying segments and valnos from
232 : /// another LiveRange.
233 189974 : LiveRange(const LiveRange &Other, BumpPtrAllocator &Allocator) {
234 : assert(Other.segmentSet == nullptr &&
235 : "Copying of LiveRanges with active SegmentSets is not supported");
236 189974 : assign(Other, Allocator);
237 : }
238 :
239 : /// Copies values numbers and live segments from \p Other into this range.
240 389621 : void assign(const LiveRange &Other, BumpPtrAllocator &Allocator) {
241 389621 : if (this == &Other)
242 : return;
243 :
244 : assert(Other.segmentSet == nullptr &&
245 : "Copying of LiveRanges with active SegmentSets is not supported");
246 : // Duplicate valnos.
247 808914 : for (const VNInfo *VNI : Other.valnos)
248 419293 : createValueCopy(VNI, Allocator);
249 : // Now we can copy segments and remap their valnos.
250 834121 : for (const Segment &S : Other.segments)
251 889000 : segments.push_back(Segment(S.start, S.end, valnos[S.valno->id]));
252 : }
253 :
254 : /// advanceTo - Advance the specified iterator to point to the Segment
255 : /// containing the specified position, or end() if the position is past the
256 : /// end of the range. If no Segment contains this position, but the
257 : /// position is in a hole, this method returns an iterator pointing to the
258 : /// Segment immediately after the hole.
259 1958541 : iterator advanceTo(iterator I, SlotIndex Pos) {
260 : assert(I != end());
261 1958541 : if (Pos >= endIndex())
262 521583 : return end();
263 5041245 : while (I->end <= Pos) ++I;
264 : return I;
265 : }
266 :
267 18690634 : const_iterator advanceTo(const_iterator I, SlotIndex Pos) const {
268 : assert(I != end());
269 18690634 : if (Pos >= endIndex())
270 1237497 : return end();
271 23278112 : while (I->end <= Pos) ++I;
272 : return I;
273 : }
274 :
275 : /// find - Return an iterator pointing to the first segment that ends after
276 : /// Pos, or end(). This is the same as advanceTo(begin(), Pos), but faster
277 : /// when searching large ranges.
278 : ///
279 : /// If Pos is contained in a Segment, that segment is returned.
280 : /// If Pos is in a hole, the following Segment is returned.
281 : /// If Pos is beyond endIndex, end() is returned.
282 : iterator find(SlotIndex Pos);
283 :
284 : const_iterator find(SlotIndex Pos) const {
285 34521282 : return const_cast<LiveRange*>(this)->find(Pos);
286 : }
287 :
288 : void clear() {
289 : valnos.clear();
290 : segments.clear();
291 : }
292 :
293 : size_t size() const {
294 628487 : return segments.size();
295 : }
296 :
297 54 : bool hasAtLeastOneValue() const { return !valnos.empty(); }
298 :
299 0 : bool containsOneValue() const { return valnos.size() == 1; }
300 :
301 17445520 : unsigned getNumValNums() const { return (unsigned)valnos.size(); }
302 :
303 : /// getValNumInfo - Returns pointer to the specified val#.
304 : ///
305 : inline VNInfo *getValNumInfo(unsigned ValNo) {
306 31615639 : return valnos[ValNo];
307 : }
308 : inline const VNInfo *getValNumInfo(unsigned ValNo) const {
309 7951700 : return valnos[ValNo];
310 : }
311 :
312 : /// containsValue - Returns true if VNI belongs to this range.
313 : bool containsValue(const VNInfo *VNI) const {
314 : return VNI && VNI->id < getNumValNums() && VNI == getValNumInfo(VNI->id);
315 : }
316 :
317 : /// getNextValue - Create a new value number and return it. MIIdx specifies
318 : /// the instruction that defines the value number.
319 6074870 : VNInfo *getNextValue(SlotIndex def, VNInfo::Allocator &VNInfoAllocator) {
320 : VNInfo *VNI =
321 6074870 : new (VNInfoAllocator) VNInfo((unsigned)valnos.size(), def);
322 6074870 : valnos.push_back(VNI);
323 6074870 : return VNI;
324 : }
325 :
326 : /// createDeadDef - Make sure the range has a value defined at Def.
327 : /// If one already exists, return it. Otherwise allocate a new value and
328 : /// add liveness for a dead def.
329 : VNInfo *createDeadDef(SlotIndex Def, VNInfo::Allocator &VNIAlloc);
330 :
331 : /// Create a def of value @p VNI. Return @p VNI. If there already exists
332 : /// a definition at VNI->def, the value defined there must be @p VNI.
333 : VNInfo *createDeadDef(VNInfo *VNI);
334 :
335 : /// Create a copy of the given value. The new value will be identical except
336 : /// for the Value number.
337 0 : VNInfo *createValueCopy(const VNInfo *orig,
338 : VNInfo::Allocator &VNInfoAllocator) {
339 : VNInfo *VNI =
340 0 : new (VNInfoAllocator) VNInfo((unsigned)valnos.size(), *orig);
341 0 : valnos.push_back(VNI);
342 0 : return VNI;
343 : }
344 :
345 : /// RenumberValues - Renumber all values in order of appearance and remove
346 : /// unused values.
347 : void RenumberValues();
348 :
349 : /// MergeValueNumberInto - This method is called when two value numbers
350 : /// are found to be equivalent. This eliminates V1, replacing all
351 : /// segments with the V1 value number with the V2 value number. This can
352 : /// cause merging of V1/V2 values numbers and compaction of the value space.
353 : VNInfo* MergeValueNumberInto(VNInfo *V1, VNInfo *V2);
354 :
355 : /// Merge all of the live segments of a specific val# in RHS into this live
356 : /// range as the specified value number. The segments in RHS are allowed
357 : /// to overlap with segments in the current range, it will replace the
358 : /// value numbers of the overlaped live segments with the specified value
359 : /// number.
360 : void MergeSegmentsInAsValue(const LiveRange &RHS, VNInfo *LHSValNo);
361 :
362 : /// MergeValueInAsValue - Merge all of the segments of a specific val#
363 : /// in RHS into this live range as the specified value number.
364 : /// The segments in RHS are allowed to overlap with segments in the
365 : /// current range, but only if the overlapping segments have the
366 : /// specified value number.
367 : void MergeValueInAsValue(const LiveRange &RHS,
368 : const VNInfo *RHSValNo, VNInfo *LHSValNo);
369 :
370 143896074 : bool empty() const { return segments.empty(); }
371 :
372 : /// beginIndex - Return the lowest numbered slot covered.
373 : SlotIndex beginIndex() const {
374 : assert(!empty() && "Call to beginIndex() on empty range.");
375 10693499 : return segments.front().start;
376 : }
377 :
378 : /// endNumber - return the maximum point of the range of the whole,
379 : /// exclusive.
380 : SlotIndex endIndex() const {
381 : assert(!empty() && "Call to endIndex() on empty range.");
382 105897788 : return segments.back().end;
383 : }
384 :
385 : bool expiredAt(SlotIndex index) const {
386 : return index >= endIndex();
387 : }
388 :
389 32296289 : bool liveAt(SlotIndex index) const {
390 32296289 : const_iterator r = find(index);
391 32296289 : return r != end() && r->start <= index;
392 : }
393 :
394 : /// Return the segment that contains the specified index, or null if there
395 : /// is none.
396 : const Segment *getSegmentContaining(SlotIndex Idx) const {
397 : const_iterator I = FindSegmentContaining(Idx);
398 : return I == end() ? nullptr : &*I;
399 : }
400 :
401 : /// Return the live segment that contains the specified index, or null if
402 : /// there is none.
403 : Segment *getSegmentContaining(SlotIndex Idx) {
404 66786 : iterator I = FindSegmentContaining(Idx);
405 66786 : return I == end() ? nullptr : &*I;
406 : }
407 :
408 : /// getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
409 : VNInfo *getVNInfoAt(SlotIndex Idx) const {
410 7961376 : const_iterator I = FindSegmentContaining(Idx);
411 7961376 : return I == end() ? nullptr : I->valno;
412 : }
413 :
414 : /// getVNInfoBefore - Return the VNInfo that is live up to but not
415 : /// necessarilly including Idx, or NULL. Use this to find the reaching def
416 : /// used by an instruction at this SlotIndex position.
417 3061636 : VNInfo *getVNInfoBefore(SlotIndex Idx) const {
418 3061636 : const_iterator I = FindSegmentContaining(Idx.getPrevSlot());
419 3061636 : return I == end() ? nullptr : I->valno;
420 : }
421 :
422 : /// Return an iterator to the segment that contains the specified index, or
423 : /// end() if there is none.
424 3625322 : iterator FindSegmentContaining(SlotIndex Idx) {
425 3625322 : iterator I = find(Idx);
426 3625322 : return I != end() && I->start <= Idx ? I : end();
427 : }
428 :
429 15030684 : const_iterator FindSegmentContaining(SlotIndex Idx) const {
430 15030684 : const_iterator I = find(Idx);
431 15030684 : return I != end() && I->start <= Idx ? I : end();
432 : }
433 :
434 : /// overlaps - Return true if the intersection of the two live ranges is
435 : /// not empty.
436 : bool overlaps(const LiveRange &other) const {
437 519135 : if (other.empty())
438 : return false;
439 514916 : return overlapsFrom(other, other.begin());
440 : }
441 :
442 : /// overlaps - Return true if the two ranges have overlapping segments
443 : /// that are not coalescable according to CP.
444 : ///
445 : /// Overlapping segments where one range is defined by a coalescable
446 : /// copy are allowed.
447 : bool overlaps(const LiveRange &Other, const CoalescerPair &CP,
448 : const SlotIndexes&) const;
449 :
450 : /// overlaps - Return true if the live range overlaps an interval specified
451 : /// by [Start, End).
452 : bool overlaps(SlotIndex Start, SlotIndex End) const;
453 :
454 : /// overlapsFrom - Return true if the intersection of the two live ranges
455 : /// is not empty. The specified iterator is a hint that we can begin
456 : /// scanning the Other range starting at I.
457 : bool overlapsFrom(const LiveRange &Other, const_iterator StartPos) const;
458 :
459 : /// Returns true if all segments of the @p Other live range are completely
460 : /// covered by this live range.
461 : /// Adjacent live ranges do not affect the covering:the liverange
462 : /// [1,5](5,10] covers (3,7].
463 : bool covers(const LiveRange &Other) const;
464 :
465 : /// Add the specified Segment to this range, merging segments as
466 : /// appropriate. This returns an iterator to the inserted segment (which
467 : /// may have grown since it was inserted).
468 : iterator addSegment(Segment S);
469 :
470 : /// Attempt to extend a value defined after @p StartIdx to include @p Use.
471 : /// Both @p StartIdx and @p Use should be in the same basic block. In case
472 : /// of subranges, an extension could be prevented by an explicit "undef"
473 : /// caused by a <def,read-undef> on a non-overlapping lane. The list of
474 : /// location of such "undefs" should be provided in @p Undefs.
475 : /// The return value is a pair: the first element is VNInfo of the value
476 : /// that was extended (possibly nullptr), the second is a boolean value
477 : /// indicating whether an "undef" was encountered.
478 : /// If this range is live before @p Use in the basic block that starts at
479 : /// @p StartIdx, and there is no intervening "undef", extend it to be live
480 : /// up to @p Use, and return the pair {value, false}. If there is no
481 : /// segment before @p Use and there is no "undef" between @p StartIdx and
482 : /// @p Use, return {nullptr, false}. If there is an "undef" before @p Use,
483 : /// return {nullptr, true}.
484 : std::pair<VNInfo*,bool> extendInBlock(ArrayRef<SlotIndex> Undefs,
485 : SlotIndex StartIdx, SlotIndex Kill);
486 :
487 : /// Simplified version of the above "extendInBlock", which assumes that
488 : /// no register lanes are undefined by <def,read-undef> operands.
489 : /// If this range is live before @p Use in the basic block that starts
490 : /// at @p StartIdx, extend it to be live up to @p Use, and return the
491 : /// value. If there is no segment before @p Use, return nullptr.
492 : VNInfo *extendInBlock(SlotIndex StartIdx, SlotIndex Kill);
493 :
494 : /// join - Join two live ranges (this, and other) together. This applies
495 : /// mappings to the value numbers in the LHS/RHS ranges as specified. If
496 : /// the ranges are not joinable, this aborts.
497 : void join(LiveRange &Other,
498 : const int *ValNoAssignments,
499 : const int *RHSValNoAssignments,
500 : SmallVectorImpl<VNInfo *> &NewVNInfo);
501 :
502 : /// True iff this segment is a single segment that lies between the
503 : /// specified boundaries, exclusively. Vregs live across a backedge are not
504 : /// considered local. The boundaries are expected to lie within an extended
505 : /// basic block, so vregs that are not live out should contain no holes.
506 61391 : bool isLocal(SlotIndex Start, SlotIndex End) const {
507 61391 : return beginIndex() > Start.getBaseIndex() &&
508 61391 : endIndex() < End.getBoundaryIndex();
509 : }
510 :
511 : /// Remove the specified segment from this range. Note that the segment
512 : /// must be a single Segment in its entirety.
513 : void removeSegment(SlotIndex Start, SlotIndex End,
514 : bool RemoveDeadValNo = false);
515 :
516 : void removeSegment(Segment S, bool RemoveDeadValNo = false) {
517 445 : removeSegment(S.start, S.end, RemoveDeadValNo);
518 : }
519 :
520 : /// Remove segment pointed to by iterator @p I from this range. This does
521 : /// not remove dead value numbers.
522 : iterator removeSegment(iterator I) {
523 : return segments.erase(I);
524 : }
525 :
526 : /// Query Liveness at Idx.
527 : /// The sub-instruction slot of Idx doesn't matter, only the instruction
528 : /// it refers to is considered.
529 17680264 : LiveQueryResult Query(SlotIndex Idx) const {
530 : // Find the segment that enters the instruction.
531 17680264 : const_iterator I = find(Idx.getBaseIndex());
532 : const_iterator E = end();
533 17680264 : if (I == E)
534 : return LiveQueryResult(nullptr, nullptr, SlotIndex(), false);
535 :
536 : // Is this an instruction live-in segment?
537 : // If Idx is the start index of a basic block, include live-in segments
538 : // that start at Idx.getBaseIndex().
539 : VNInfo *EarlyVal = nullptr;
540 : VNInfo *LateVal = nullptr;
541 : SlotIndex EndPoint;
542 : bool Kill = false;
543 16237386 : if (I->start <= Idx.getBaseIndex()) {
544 12578697 : EarlyVal = I->valno;
545 12578697 : EndPoint = I->end;
546 : // Move to the potentially live-out segment.
547 12578697 : if (SlotIndex::isSameInstr(Idx, I->end)) {
548 : Kill = true;
549 8536086 : if (++I == E)
550 6362835 : return LiveQueryResult(EarlyVal, LateVal, EndPoint, Kill);
551 : }
552 : // Special case: A PHIDef value can have its def in the middle of a
553 : // segment if the value happens to be live out of the layout
554 : // predecessor.
555 : // Such a value is not live-in.
556 6215862 : if (EarlyVal->def == Idx.getBaseIndex())
557 : EarlyVal = nullptr;
558 : }
559 : // I now points to the segment that may be live-through, or defined by
560 : // this instr. Ignore segments starting after the current instr.
561 9874551 : if (!SlotIndex::isEarlierInstr(Idx, I->start)) {
562 6891008 : LateVal = I->valno;
563 6891008 : EndPoint = I->end;
564 : }
565 9874551 : return LiveQueryResult(EarlyVal, LateVal, EndPoint, Kill);
566 : }
567 :
568 : /// removeValNo - Remove all the segments defined by the specified value#.
569 : /// Also remove the value# from value# list.
570 : void removeValNo(VNInfo *ValNo);
571 :
572 : /// Returns true if the live range is zero length, i.e. no live segments
573 : /// span instructions. It doesn't pay to spill such a range.
574 1473232 : bool isZeroLength(SlotIndexes *Indexes) const {
575 2245152 : for (const Segment &S : segments)
576 1656763 : if (Indexes->getNextNonNullIndex(S.start).getBaseIndex() <
577 : S.end.getBaseIndex())
578 : return false;
579 : return true;
580 : }
581 :
582 : // Returns true if any segment in the live range contains any of the
583 : // provided slot indexes. Slots which occur in holes between
584 : // segments will not cause the function to return true.
585 : bool isLiveAtIndexes(ArrayRef<SlotIndex> Slots) const;
586 :
587 : bool operator<(const LiveRange& other) const {
588 : const SlotIndex &thisIndex = beginIndex();
589 : const SlotIndex &otherIndex = other.beginIndex();
590 : return thisIndex < otherIndex;
591 : }
592 :
593 : /// Returns true if there is an explicit "undef" between @p Begin
594 : /// @p End.
595 0 : bool isUndefIn(ArrayRef<SlotIndex> Undefs, SlotIndex Begin,
596 : SlotIndex End) const {
597 0 : return std::any_of(Undefs.begin(), Undefs.end(),
598 : [Begin,End] (SlotIndex Idx) -> bool {
599 : return Begin <= Idx && Idx < End;
600 0 : });
601 : }
602 :
603 : /// Flush segment set into the regular segment vector.
604 : /// The method is to be called after the live range
605 : /// has been created, if use of the segment set was
606 : /// activated in the constructor of the live range.
607 : void flushSegmentSet();
608 :
609 : void print(raw_ostream &OS) const;
610 : void dump() const;
611 :
612 : /// Walk the range and assert if any invariants fail to hold.
613 : ///
614 : /// Note that this is a no-op when asserts are disabled.
615 : #ifdef NDEBUG
616 0 : void verify() const {}
617 : #else
618 : void verify() const;
619 : #endif
620 :
621 : protected:
622 : /// Append a segment to the list of segments.
623 : void append(const LiveRange::Segment S);
624 :
625 : private:
626 : friend class LiveRangeUpdater;
627 : void addSegmentToSet(Segment S);
628 : void markValNoForDeletion(VNInfo *V);
629 : };
630 :
631 : inline raw_ostream &operator<<(raw_ostream &OS, const LiveRange &LR) {
632 4 : LR.print(OS);
633 : return OS;
634 : }
635 :
636 : /// LiveInterval - This class represents the liveness of a register,
637 : /// or stack slot.
638 : class LiveInterval : public LiveRange {
639 : public:
640 : using super = LiveRange;
641 :
642 : /// A live range for subregisters. The LaneMask specifies which parts of the
643 : /// super register are covered by the interval.
644 : /// (@sa TargetRegisterInfo::getSubRegIndexLaneMask()).
645 343282 : class SubRange : public LiveRange {
646 : public:
647 : SubRange *Next = nullptr;
648 : LaneBitmask LaneMask;
649 :
650 : /// Constructs a new SubRange object.
651 153312 : SubRange(LaneBitmask LaneMask) : LaneMask(LaneMask) {}
652 :
653 : /// Constructs a new SubRange object by copying liveness from @p Other.
654 : SubRange(LaneBitmask LaneMask, const LiveRange &Other,
655 : BumpPtrAllocator &Allocator)
656 189974 : : LiveRange(Other, Allocator), LaneMask(LaneMask) {}
657 :
658 : void print(raw_ostream &OS) const;
659 : void dump() const;
660 : };
661 :
662 : private:
663 : SubRange *SubRanges = nullptr; ///< Single linked list of subregister live
664 : /// ranges.
665 :
666 : public:
667 : const unsigned reg; // the register or stack slot of this interval.
668 : float weight; // weight of this interval
669 :
670 2887712 : LiveInterval(unsigned Reg, float Weight) : reg(Reg), weight(Weight) {}
671 :
672 2866773 : ~LiveInterval() {
673 2866773 : clearSubRanges();
674 : }
675 :
676 : template<typename T>
677 : class SingleLinkedListIterator {
678 : T *P;
679 :
680 : public:
681 : SingleLinkedListIterator<T>(T *P) : P(P) {}
682 :
683 : SingleLinkedListIterator<T> &operator++() {
684 35303608 : P = P->Next;
685 : return *this;
686 : }
687 : SingleLinkedListIterator<T> operator++(int) {
688 : SingleLinkedListIterator res = *this;
689 : ++*this;
690 : return res;
691 : }
692 0 : bool operator!=(const SingleLinkedListIterator<T> &Other) {
693 0 : return P != Other.operator->();
694 : }
695 0 : bool operator==(const SingleLinkedListIterator<T> &Other) {
696 0 : return P == Other.operator->();
697 : }
698 0 : T &operator*() const {
699 0 : return *P;
700 : }
701 0 : T *operator->() const {
702 0 : return P;
703 : }
704 0 : };
705 0 :
706 : using subrange_iterator = SingleLinkedListIterator<SubRange>;
707 0 : using const_subrange_iterator = SingleLinkedListIterator<const SubRange>;
708 0 :
709 0 : subrange_iterator subrange_begin() {
710 0 : return subrange_iterator(SubRanges);
711 0 : }
712 0 : subrange_iterator subrange_end() {
713 0 : return subrange_iterator(nullptr);
714 0 : }
715 :
716 0 : const_subrange_iterator subrange_begin() const {
717 0 : return const_subrange_iterator(SubRanges);
718 : }
719 0 : const_subrange_iterator subrange_end() const {
720 0 : return const_subrange_iterator(nullptr);
721 : }
722 :
723 : iterator_range<subrange_iterator> subranges() {
724 3982794 : return make_range(subrange_begin(), subrange_end());
725 : }
726 :
727 0 : iterator_range<const_subrange_iterator> subranges() const {
728 3187643 : return make_range(subrange_begin(), subrange_end());
729 : }
730 0 :
731 0 : /// Creates a new empty subregister live range. The range is added at the
732 : /// beginning of the subrange list; subrange iterators stay valid.
733 : SubRange *createSubRange(BumpPtrAllocator &Allocator,
734 0 : LaneBitmask LaneMask) {
735 0 : SubRange *Range = new (Allocator) SubRange(LaneMask);
736 : appendSubRange(Range);
737 0 : return Range;
738 0 : }
739 :
740 : /// Like createSubRange() but the new range is filled with a copy of the
741 : /// liveness information in @p CopyFrom.
742 1182572 : SubRange *createSubRangeFrom(BumpPtrAllocator &Allocator,
743 : LaneBitmask LaneMask,
744 : const LiveRange &CopyFrom) {
745 64229 : SubRange *Range = new (Allocator) SubRange(LaneMask, CopyFrom, Allocator);
746 267890 : appendSubRange(Range);
747 64229 : return Range;
748 : }
749 :
750 : /// Returns true if subregister liveness information is available.
751 153312 : bool hasSubRanges() const {
752 108744 : return SubRanges != nullptr;
753 153312 : }
754 :
755 153312 : /// Removes all subregister liveness information.
756 : void clearSubRanges();
757 :
758 : /// Removes all subranges without any segments (subranges without segments
759 : /// are not considered valid and should only exist temporarily).
760 125745 : void removeEmptySubRanges();
761 :
762 : /// getSize - Returns the sum of sizes of all the LiveRange's.
763 125745 : ///
764 : unsigned getSize() const;
765 125745 :
766 : /// isSpillable - Can this interval be spilled?
767 0 : bool isSpillable() const {
768 2347894 : return weight != huge_valf;
769 0 : }
770 0 :
771 : /// markNotSpillable - Mark interval as not spillable
772 0 : void markNotSpillable() {
773 588383 : weight = huge_valf;
774 0 : }
775 :
776 : /// For a given lane mask @p LaneMask, compute indexes at which the
777 : /// lane is marked undefined by subregister <def,read-undef> definitions.
778 : void computeSubRangeUndefs(SmallVectorImpl<SlotIndex> &Undefs,
779 : LaneBitmask LaneMask,
780 : const MachineRegisterInfo &MRI,
781 : const SlotIndexes &Indexes) const;
782 :
783 : /// Refines the subranges to support \p LaneMask. This may only be called
784 : /// for LI.hasSubrange()==true. Subregister ranges are split or created
785 0 : /// until \p LaneMask can be matched exactly. \p Mod is executed on the
786 108206 : /// matching subranges.
787 : ///
788 : /// Example:
789 : /// Given an interval with subranges with lanemasks L0F00, L00F0 and
790 0 : /// L000F, refining for mask L0018. Will split the L00F0 lane into
791 2 : /// L00E0 and L0010 and the L000F lane into L0007 and L0008. The Mod
792 0 : /// function will be applied to the L0010 and L0008 subranges.
793 : void refineSubRanges(BumpPtrAllocator &Allocator, LaneBitmask LaneMask,
794 : std::function<void(LiveInterval::SubRange&)> Apply);
795 :
796 10162 : bool operator<(const LiveInterval& other) const {
797 10162 : const SlotIndex &thisIndex = beginIndex();
798 10162 : const SlotIndex &otherIndex = other.beginIndex();
799 30486 : return std::tie(thisIndex, reg) < std::tie(otherIndex, other.reg);
800 : }
801 :
802 : void print(raw_ostream &OS) const;
803 : void dump() const;
804 :
805 : /// Walks the interval and assert if any invariants fail to hold.
806 : ///
807 : /// Note that this is a no-op when asserts are disabled.
808 : #ifdef NDEBUG
809 0 : void verify(const MachineRegisterInfo *MRI = nullptr) const {}
810 : #else
811 : void verify(const MachineRegisterInfo *MRI = nullptr) const;
812 : #endif
813 :
814 : private:
815 : /// Appends @p Range to SubRanges list.
816 0 : void appendSubRange(SubRange *Range) {
817 64229 : Range->Next = SubRanges;
818 64229 : SubRanges = Range;
819 0 : }
820 :
821 : /// Free memory held by SubRange.
822 : void freeSubRange(SubRange *S);
823 : };
824 :
825 : inline raw_ostream &operator<<(raw_ostream &OS,
826 : const LiveInterval::SubRange &SR) {
827 : SR.print(OS);
828 : return OS;
829 : }
830 :
831 : inline raw_ostream &operator<<(raw_ostream &OS, const LiveInterval &LI) {
832 0 : LI.print(OS);
833 : return OS;
834 0 : }
835 279057 :
836 279057 : raw_ostream &operator<<(raw_ostream &OS, const LiveRange::Segment &S);
837 0 :
838 : inline bool operator<(SlotIndex V, const LiveRange::Segment &S) {
839 : return V < S.start;
840 : }
841 :
842 : inline bool operator<(const LiveRange::Segment &S, SlotIndex V) {
843 : return S.start < V;
844 : }
845 4 :
846 : /// Helper class for performant LiveRange bulk updates.
847 : ///
848 : /// Calling LiveRange::addSegment() repeatedly can be expensive on large
849 : /// live ranges because segments after the insertion point may need to be
850 6 : /// shifted. The LiveRangeUpdater class can defer the shifting when adding
851 : /// many segments in order.
852 : ///
853 : /// The LiveRange will be in an invalid state until flush() is called.
854 : class LiveRangeUpdater {
855 : LiveRange *LR;
856 : SlotIndex LastStart;
857 : LiveRange::iterator WriteI;
858 : LiveRange::iterator ReadI;
859 : SmallVector<LiveRange::Segment, 16> Spills;
860 : void mergeSpills();
861 :
862 : public:
863 : /// Create a LiveRangeUpdater for adding segments to LR.
864 : /// LR will temporarily be in an invalid state until flush() is called.
865 441227 : LiveRangeUpdater(LiveRange *lr = nullptr) : LR(lr) {}
866 :
867 441227 : ~LiveRangeUpdater() { flush(); }
868 :
869 : /// Add a segment to LR and coalesce when possible, just like
870 : /// LR.addSegment(). Segments should be added in increasing start order for
871 : /// best performance.
872 : void add(LiveRange::Segment);
873 :
874 : void add(SlotIndex Start, SlotIndex End, VNInfo *VNI) {
875 1741503 : add(LiveRange::Segment(Start, End, VNI));
876 : }
877 :
878 : /// Return true if the LR is currently in an invalid state, and flush()
879 : /// needs to be called.
880 : bool isDirty() const { return LastStart.isValid(); }
881 :
882 : /// Flush the updater state to LR so it is valid and contains all added
883 1035323 : /// segments.
884 : void flush();
885 1035323 :
886 : /// Select a different destination live range.
887 : void setDest(LiveRange *lr) {
888 79689 : if (LR != lr && isDirty())
889 123 : flush();
890 79689 : LR = lr;
891 : }
892 :
893 96748 : /// Get the current destination live range.
894 : LiveRange *getDest() const { return LR; }
895 :
896 : void dump() const;
897 : void print(raw_ostream&) const;
898 : };
899 :
900 : inline raw_ostream &operator<<(raw_ostream &OS, const LiveRangeUpdater &X) {
901 : X.print(OS);
902 : return OS;
903 : }
904 :
905 : /// ConnectedVNInfoEqClasses - Helper class that can divide VNInfos in a
906 : /// LiveInterval into equivalence clases of connected components. A
907 : /// LiveInterval that has multiple connected components can be broken into
908 : /// multiple LiveIntervals.
909 : ///
910 : /// Given a LiveInterval that may have multiple connected components, run:
911 : ///
912 : /// unsigned numComps = ConEQ.Classify(LI);
913 : /// if (numComps > 1) {
914 : /// // allocate numComps-1 new LiveIntervals into LIS[1..]
915 : /// ConEQ.Distribute(LIS);
916 : /// }
917 :
918 : class ConnectedVNInfoEqClasses {
919 : LiveIntervals &LIS;
920 : IntEqClasses EqClass;
921 :
922 : public:
923 1658116 : explicit ConnectedVNInfoEqClasses(LiveIntervals &lis) : LIS(lis) {}
924 :
925 : /// Classify the values in \p LR into connected components.
926 : /// Returns the number of connected components.
927 : unsigned Classify(const LiveRange &LR);
928 :
929 : /// getEqClass - Classify creates equivalence classes numbered 0..N. Return
930 : /// the equivalence class assigned the VNI.
931 0 : unsigned getEqClass(const VNInfo *VNI) const { return EqClass[VNI->id]; }
932 :
933 : /// Distribute values in \p LI into a separate LiveIntervals
934 : /// for each connected component. LIV must have an empty LiveInterval for
935 : /// each additional connected component. The first connected component is
936 : /// left in \p LI.
937 : void Distribute(LiveInterval &LI, LiveInterval *LIV[],
938 : MachineRegisterInfo &MRI);
939 : };
940 :
941 79904 : } // end namespace llvm
942 :
943 : #endif // LLVM_CODEGEN_LIVEINTERVAL_H
|
