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