LLVM  13.0.0git
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  SlotIndex endIndex() const { return Segments.stop(); }
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  // Get any virtual register that is assign to this physical unit
108  LiveInterval *getOneVReg() const;
109 
110  /// Query interferences between a single live virtual register and a live
111  /// interval union.
112  class Query {
113  const LiveIntervalUnion *LiveUnion = nullptr;
114  const LiveRange *LR = nullptr;
115  LiveRange::const_iterator LRI; ///< current position in LR
116  ConstSegmentIter LiveUnionI; ///< current position in LiveUnion
117  Optional<SmallVector<LiveInterval *, 4>> InterferingVRegs;
118  bool CheckedFirstInterference = false;
119  bool SeenAllInterferences = false;
120  unsigned Tag = 0;
121  unsigned UserTag = 0;
122 
123  public:
124  Query() = default;
125  Query(const LiveRange &LR, const LiveIntervalUnion &LIU)
126  : LiveUnion(&LIU), LR(&LR) {}
127  Query(const Query &) = delete;
128  Query &operator=(const Query &) = delete;
129 
130  void reset(unsigned NewUserTag, const LiveRange &NewLR,
131  const LiveIntervalUnion &NewLiveUnion) {
132  LiveUnion = &NewLiveUnion;
133  LR = &NewLR;
134  InterferingVRegs = None;
135  CheckedFirstInterference = false;
136  SeenAllInterferences = false;
137  Tag = NewLiveUnion.getTag();
138  UserTag = NewUserTag;
139  }
140 
141  void init(unsigned NewUserTag, const LiveRange &NewLR,
142  const LiveIntervalUnion &NewLiveUnion) {
143  if (UserTag == NewUserTag && LR == &NewLR && LiveUnion == &NewLiveUnion &&
144  !NewLiveUnion.changedSince(Tag)) {
145  // Retain cached results, e.g. firstInterference.
146  return;
147  }
148  reset(NewUserTag, NewLR, NewLiveUnion);
149  }
150 
151  // Does this live virtual register interfere with the union?
153 
154  // Count the virtual registers in this union that interfere with this
155  // query's live virtual register, up to maxInterferingRegs.
156  unsigned collectInterferingVRegs(
157  unsigned MaxInterferingRegs = std::numeric_limits<unsigned>::max());
158 
159  // Was this virtual register visited during collectInterferingVRegs?
160  bool isSeenInterference(LiveInterval *VirtReg) const;
161 
162  // Did collectInterferingVRegs collect all interferences?
163  bool seenAllInterferences() const { return SeenAllInterferences; }
164 
165  // Vector generated by collectInterferingVRegs.
167  return *InterferingVRegs;
168  }
169  };
170 
171  // Array of LiveIntervalUnions.
172  class Array {
173  unsigned Size = 0;
174  LiveIntervalUnion *LIUs = nullptr;
175 
176  public:
177  Array() = default;
178  ~Array() { clear(); }
179 
180  // Initialize the array to have Size entries.
181  // Reuse an existing allocation if the size matches.
182  void init(LiveIntervalUnion::Allocator&, unsigned Size);
183 
184  unsigned size() const { return Size; }
185 
186  void clear();
187 
188  LiveIntervalUnion& operator[](unsigned idx) {
189  assert(idx < Size && "idx out of bounds");
190  return LIUs[idx];
191  }
192 
193  const LiveIntervalUnion& operator[](unsigned Idx) const {
194  assert(Idx < Size && "Idx out of bounds");
195  return LIUs[Idx];
196  }
197  };
198 };
199 
200 } // end namespace llvm
201 
202 #endif // LLVM_CODEGEN_LIVEINTERVALUNION_H
llvm::LiveIntervalUnion::Query::operator=
Query & operator=(const Query &)=delete
llvm::LiveIntervalUnion::getOneVReg
LiveInterval * getOneVReg() const
NDEBUG.
Definition: LiveIntervalUnion.cpp:102
llvm::LiveIntervalUnion::Array::size
unsigned size() const
Definition: LiveIntervalUnion.h:184
llvm::LiveIntervalUnion::Array
Definition: LiveIntervalUnion.h:172
llvm
Definition: AllocatorList.h:23
llvm::LiveIntervalUnion::Query::isSeenInterference
bool isSeenInterference(LiveInterval *VirtReg) const
Definition: LiveIntervalUnion.cpp:114
llvm::LiveIntervalUnion::LiveIntervalUnion
LiveIntervalUnion(Allocator &a)
Definition: LiveIntervalUnion.h:65
llvm::LiveIntervalUnion::begin
SegmentIter begin()
Definition: LiveIntervalUnion.h:69
llvm::LiveIntervalUnion::Query::reset
void reset(unsigned NewUserTag, const LiveRange &NewLR, const LiveIntervalUnion &NewLiveUnion)
Definition: LiveIntervalUnion.h:130
llvm::LiveIntervalUnion::Array::clear
void clear()
Definition: LiveIntervalUnion.cpp:207
llvm::LiveIntervalUnion::Query::Query
Query(const LiveRange &LR, const LiveIntervalUnion &LIU)
Definition: LiveIntervalUnion.h:125
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:231
llvm::LiveIntervalUnion::Query::init
void init(unsigned NewUserTag, const LiveRange &NewLR, const LiveIntervalUnion &NewLiveUnion)
Definition: LiveIntervalUnion.h:141
llvm::Optional
Definition: APInt.h:33
llvm::LiveIntervalUnion::end
SegmentIter end()
Definition: LiveIntervalUnion.h:70
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1567
llvm::LiveIntervalUnion::Allocator
LiveSegments::Allocator Allocator
Definition: LiveIntervalUnion.h:58
llvm::LiveIntervalUnion::end
ConstSegmentIter end() const
Definition: LiveIntervalUnion.h:73
a
=0.0 ? 0.0 :(a > 0.0 ? 1.0 :-1.0) a
Definition: README.txt:489
llvm::SparseBitVector
Definition: SparseBitVector.h:255
llvm::LiveIntervalUnion::startIndex
SlotIndex startIndex() const
Definition: LiveIntervalUnion.h:77
llvm::LiveIntervalUnion::ConstSegmentIter
LiveSegments::const_iterator ConstSegmentIter
Const version of SegmentIter.
Definition: LiveIntervalUnion.h:55
llvm::LiveIntervalUnion::getTag
unsigned getTag() const
getTag - Return an opaque tag representing the current state of the union.
Definition: LiveIntervalUnion.h:85
llvm::LiveRange::const_iterator
Segments::const_iterator const_iterator
Definition: LiveInterval.h:213
llvm::LiveIntervalUnion::getMap
const Map & getMap() const
Definition: LiveIntervalUnion.h:82
llvm::LiveIntervalUnion::changedSince
bool changedSince(unsigned tag) const
changedSince - Return true if the union change since getTag returned tag.
Definition: LiveIntervalUnion.h:88
llvm::LiveIntervalUnion::begin
ConstSegmentIter begin() const
Definition: LiveIntervalUnion.h:72
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:50
llvm::LiveInterval
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:680
llvm::IntervalMap< SlotIndex, LiveInterval * >::iterator
friend class iterator
Definition: IntervalMap.h:1098
llvm::SlotIndex
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:83
llvm::None
const NoneType None
Definition: None.h:23
llvm::LiveIntervalUnion::endIndex
SlotIndex endIndex() const
Definition: LiveIntervalUnion.h:78
llvm::LiveIntervalUnion::find
SegmentIter find(SlotIndex x)
Definition: LiveIntervalUnion.h:71
llvm::LiveIntervalUnion::print
void print(raw_ostream &OS, const TargetRegisterInfo *TRI) const
Definition: LiveIntervalUnion.cpp:82
llvm::IntervalMap< SlotIndex, LiveInterval * >::Allocator
typename Sizer::Allocator Allocator
Definition: IntervalMap.h:964
llvm::LiveIntervalUnion::find
ConstSegmentIter find(SlotIndex x) const
Definition: LiveIntervalUnion.h:74
llvm::LiveIntervalUnion::Array::operator[]
LiveIntervalUnion & operator[](unsigned idx)
Definition: LiveIntervalUnion.h:188
llvm::LiveRange
This class represents the liveness of a register, stack slot, etc.
Definition: LiveInterval.h:157
llvm::LiveIntervalUnion
Union of live intervals that are strong candidates for coalescing into a single register (either phys...
Definition: LiveIntervalUnion.h:42
llvm::LiveIntervalUnion::empty
bool empty() const
Definition: LiveIntervalUnion.h:76
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::LiveIntervalUnion::SegmentIter
LiveSegments::iterator SegmentIter
Definition: LiveIntervalUnion.h:52
llvm::LiveIntervalUnion::Array::init
void init(LiveIntervalUnion::Allocator &, unsigned Size)
Definition: LiveIntervalUnion.cpp:194
llvm::LiveIntervalUnion::Query::interferingVRegs
const SmallVectorImpl< LiveInterval * > & interferingVRegs() const
Definition: LiveIntervalUnion.h:166
llvm::LiveIntervalUnion::extract
void extract(LiveInterval &VirtReg, const LiveRange &Range)
Definition: LiveIntervalUnion.cpp:56
llvm::LiveIntervalUnion::Array::Array
Array()=default
llvm::LiveIntervalUnion::Query::seenAllInterferences
bool seenAllInterferences() const
Definition: LiveIntervalUnion.h:163
llvm::LiveIntervalUnion::Query::Query
Query()=default
llvm::LiveIntervalUnion::Array::~Array
~Array()
Definition: LiveIntervalUnion.h:178
llvm::LiveIntervalUnion::Query::checkInterference
bool checkInterference()
Definition: LiveIntervalUnion.h:152
x
TODO unsigned x
Definition: README.txt:10
llvm::LiveIntervalUnion::Query::collectInterferingVRegs
unsigned collectInterferingVRegs(unsigned MaxInterferingRegs=std::numeric_limits< unsigned >::max())
Definition: LiveIntervalUnion.cpp:128
llvm::LiveIntervalUnion::Array::operator[]
const LiveIntervalUnion & operator[](unsigned Idx) const
Definition: LiveIntervalUnion.h:193
llvm::LiveIntervalUnion::unify
void unify(LiveInterval &VirtReg, const LiveRange &Range)
Definition: LiveIntervalUnion.cpp:29
LiveInterval.h
llvm::LiveIntervalUnion::verify
void verify(LiveVirtRegBitSet &VisitedVRegs)
Definition: LiveIntervalUnion.cpp:96
SmallVector.h
llvm::LiveIntervalUnion::Query
Query interferences between a single live virtual register and a live interval union.
Definition: LiveIntervalUnion.h:112
IntervalMap.h
llvm::LiveIntervalUnion::clear
void clear()
Definition: LiveIntervalUnion.h:97
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
llvm::IntervalMap< SlotIndex, LiveInterval * >
llvm::IntervalMap< SlotIndex, LiveInterval * >::const_iterator
friend class const_iterator
Definition: IntervalMap.h:1096
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
SlotIndexes.h