LLVM  9.0.0svn
LiveIntervalUnion.h
Go to the documentation of this file.
1 //===- LiveIntervalUnion.h - Live interval union data struct ---*- C++ -*--===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // LiveIntervalUnion is a union of live segments across multiple live virtual
10 // registers. This may be used during coalescing to represent a congruence
11 // class, or during register allocation to model liveness of a physical
12 // register.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #ifndef LLVM_CODEGEN_LIVEINTERVALUNION_H
17 #define LLVM_CODEGEN_LIVEINTERVALUNION_H
18 
19 #include "llvm/ADT/IntervalMap.h"
20 #include "llvm/ADT/SmallVector.h"
23 #include <cassert>
24 #include <limits>
25 
26 namespace llvm {
27 
28 class raw_ostream;
29 class TargetRegisterInfo;
30 
31 #ifndef NDEBUG
32 // forward declaration
33 template <unsigned Element> class SparseBitVector;
34 
36 #endif
37 
38 /// Union of live intervals that are strong candidates for coalescing into a
39 /// single register (either physical or virtual depending on the context). We
40 /// expect the constituent live intervals to be disjoint, although we may
41 /// eventually make exceptions to handle value-based interference.
43  // A set of live virtual register segments that supports fast insertion,
44  // intersection, and removal.
45  // Mapping SlotIndex intervals to virtual register numbers.
47 
48 public:
49  // SegmentIter can advance to the next segment ordered by starting position
50  // which may belong to a different live virtual register. We also must be able
51  // to reach the current segment's containing virtual register.
53 
54  /// Const version of SegmentIter.
56 
57  // LiveIntervalUnions share an external allocator.
59 
60 private:
61  unsigned Tag = 0; // unique tag for current contents.
62  LiveSegments Segments; // union of virtual reg segments
63 
64 public:
65  explicit LiveIntervalUnion(Allocator &a) : Segments(a) {}
66 
67  // Iterate over all segments in the union of live virtual registers ordered
68  // by their starting position.
69  SegmentIter begin() { return Segments.begin(); }
70  SegmentIter end() { return Segments.end(); }
71  SegmentIter find(SlotIndex x) { return Segments.find(x); }
72  ConstSegmentIter begin() const { return Segments.begin(); }
73  ConstSegmentIter end() const { return Segments.end(); }
74  ConstSegmentIter find(SlotIndex x) const { return Segments.find(x); }
75 
76  bool empty() const { return Segments.empty(); }
77  SlotIndex startIndex() const { return Segments.start(); }
78 
79  // Provide public access to the underlying map to allow overlap iteration.
80  using Map = LiveSegments;
81  const Map &getMap() const { return Segments; }
82 
83  /// getTag - Return an opaque tag representing the current state of the union.
84  unsigned getTag() const { return Tag; }
85 
86  /// changedSince - Return true if the union change since getTag returned tag.
87  bool changedSince(unsigned tag) const { return tag != Tag; }
88 
89  // Add a live virtual register to this union and merge its segments.
90  void unify(LiveInterval &VirtReg, const LiveRange &Range);
91 
92  // Remove a live virtual register's segments from this union.
93  void extract(LiveInterval &VirtReg, const LiveRange &Range);
94 
95  // Remove all inserted virtual registers.
96  void clear() { Segments.clear(); ++Tag; }
97 
98  // Print union, using TRI to translate register names
99  void print(raw_ostream &OS, const TargetRegisterInfo *TRI) const;
100 
101 #ifndef NDEBUG
102  // Verify the live intervals in this union and add them to the visited set.
103  void verify(LiveVirtRegBitSet& VisitedVRegs);
104 #endif
105 
106  /// Query interferences between a single live virtual register and a live
107  /// interval union.
108  class Query {
109  const LiveIntervalUnion *LiveUnion = nullptr;
110  const LiveRange *LR = nullptr;
111  LiveRange::const_iterator LRI; ///< current position in LR
112  ConstSegmentIter LiveUnionI; ///< current position in LiveUnion
113  SmallVector<LiveInterval*,4> InterferingVRegs;
114  bool CheckedFirstInterference = false;
115  bool SeenAllInterferences = false;
116  unsigned Tag = 0;
117  unsigned UserTag = 0;
118 
119  void reset(unsigned NewUserTag, const LiveRange &NewLR,
120  const LiveIntervalUnion &NewLiveUnion) {
121  LiveUnion = &NewLiveUnion;
122  LR = &NewLR;
123  InterferingVRegs.clear();
124  CheckedFirstInterference = false;
125  SeenAllInterferences = false;
126  Tag = NewLiveUnion.getTag();
127  UserTag = NewUserTag;
128  }
129 
130  public:
131  Query() = default;
132  Query(const LiveRange &LR, const LiveIntervalUnion &LIU):
133  LiveUnion(&LIU), LR(&LR) {}
134  Query(const Query &) = delete;
135  Query &operator=(const Query &) = delete;
136 
137  void init(unsigned NewUserTag, const LiveRange &NewLR,
138  const LiveIntervalUnion &NewLiveUnion) {
139  if (UserTag == NewUserTag && LR == &NewLR && LiveUnion == &NewLiveUnion &&
140  !NewLiveUnion.changedSince(Tag)) {
141  // Retain cached results, e.g. firstInterference.
142  return;
143  }
144  reset(NewUserTag, NewLR, NewLiveUnion);
145  }
146 
147  // Does this live virtual register interfere with the union?
149 
150  // Count the virtual registers in this union that interfere with this
151  // query's live virtual register, up to maxInterferingRegs.
152  unsigned collectInterferingVRegs(
153  unsigned MaxInterferingRegs = std::numeric_limits<unsigned>::max());
154 
155  // Was this virtual register visited during collectInterferingVRegs?
156  bool isSeenInterference(LiveInterval *VirtReg) const;
157 
158  // Did collectInterferingVRegs collect all interferences?
159  bool seenAllInterferences() const { return SeenAllInterferences; }
160 
161  // Vector generated by collectInterferingVRegs.
163  return InterferingVRegs;
164  }
165  };
166 
167  // Array of LiveIntervalUnions.
168  class Array {
169  unsigned Size = 0;
170  LiveIntervalUnion *LIUs = nullptr;
171 
172  public:
173  Array() = default;
174  ~Array() { clear(); }
175 
176  // Initialize the array to have Size entries.
177  // Reuse an existing allocation if the size matches.
178  void init(LiveIntervalUnion::Allocator&, unsigned Size);
179 
180  unsigned size() const { return Size; }
181 
182  void clear();
183 
184  LiveIntervalUnion& operator[](unsigned idx) {
185  assert(idx < Size && "idx out of bounds");
186  return LIUs[idx];
187  }
188 
189  const LiveIntervalUnion& operator[](unsigned Idx) const {
190  assert(Idx < Size && "Idx out of bounds");
191  return LIUs[Idx];
192  }
193  };
194 };
195 
196 } // end namespace llvm
197 
198 #endif // LLVM_CODEGEN_LIVEINTERVALUNION_H
friend class iterator
Definition: IntervalMap.h:1097
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
LiveIntervalUnion(Allocator &a)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:637
ConstSegmentIter end() const
unsigned const TargetRegisterInfo * TRI
friend class const_iterator
Definition: IntervalMap.h:1095
const_iterator begin() const
Definition: IntervalMap.h:1099
This class represents the liveness of a register, stack slot, etc.
Definition: LiveInterval.h:156
const Map & getMap() const
Query interferences between a single live virtual register and a live interval union.
Query(const LiveRange &LR, const LiveIntervalUnion &LIU)
Query & operator=(const Query &)=delete
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
KeyT start() const
start - Return the smallest mapped key in a non-empty map.
Definition: IntervalMap.h:1059
const SmallVectorImpl< LiveInterval * > & interferingVRegs() const
void init(unsigned NewUserTag, const LiveRange &NewLR, const LiveIntervalUnion &NewLiveUnion)
void clear()
clear - Remove all entries.
Definition: IntervalMap.h:1283
const_iterator find(KeyT x) const
find - Return an iterator pointing to the first interval ending at or after x, or end()...
Definition: IntervalMap.h:1125
unsigned collectInterferingVRegs(unsigned MaxInterferingRegs=std::numeric_limits< unsigned >::max())
bool changedSince(unsigned tag) const
changedSince - Return true if the union change since getTag returned tag.
typename Sizer::Allocator Allocator
Definition: IntervalMap.h:959
SegmentIter find(SlotIndex x)
const_iterator end() const
Definition: IntervalMap.h:1111
Union of live intervals that are strong candidates for coalescing into a single register (either phys...
SlotIndex startIndex() const
unsigned getTag() const
getTag - Return an opaque tag representing the current state of the union.
LiveSegments::Allocator Allocator
LiveIntervalUnion & operator[](unsigned idx)
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
ConstSegmentIter find(SlotIndex x) const
void unify(LiveInterval &VirtReg, const LiveRange &Range)
void print(raw_ostream &OS, const TargetRegisterInfo *TRI) const
Segments::const_iterator const_iterator
Definition: LiveInterval.h:208
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:841
bool empty() const
empty - Return true when no intervals are mapped.
Definition: IntervalMap.h:1054
ConstSegmentIter begin() const
void verify(LiveVirtRegBitSet &VisitedVRegs)
uint32_t Size
Definition: Profile.cpp:46
void extract(LiveInterval &VirtReg, const LiveRange &Range)
bool isSeenInterference(LiveInterval *VirtReg) const
NDEBUG.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
const LiveIntervalUnion & operator[](unsigned Idx) const
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:83