LLVM  16.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(const LiveInterval &VirtReg, const LiveRange &Range);
92 
93  // Remove a live virtual register's segments from this union.
94  void extract(const 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  const 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  SmallVector<const LiveInterval *, 4> InterferingVRegs;
118  bool CheckedFirstInterference = false;
119  bool SeenAllInterferences = false;
120  unsigned Tag = 0;
121  unsigned UserTag = 0;
122 
123  // Count the virtual registers in this union that interfere with this
124  // query's live virtual register, up to maxInterferingRegs.
125  unsigned collectInterferingVRegs(unsigned MaxInterferingRegs);
126 
127  // Was this virtual register visited during collectInterferingVRegs?
128  bool isSeenInterference(const LiveInterval *VirtReg) const;
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 reset(unsigned NewUserTag, const LiveRange &NewLR,
138  const LiveIntervalUnion &NewLiveUnion) {
139  LiveUnion = &NewLiveUnion;
140  LR = &NewLR;
141  InterferingVRegs.clear();
142  CheckedFirstInterference = false;
143  SeenAllInterferences = false;
144  Tag = NewLiveUnion.getTag();
145  UserTag = NewUserTag;
146  }
147 
148  void init(unsigned NewUserTag, const LiveRange &NewLR,
149  const LiveIntervalUnion &NewLiveUnion) {
150  if (UserTag == NewUserTag && LR == &NewLR && LiveUnion == &NewLiveUnion &&
151  !NewLiveUnion.changedSince(Tag)) {
152  // Retain cached results, e.g. firstInterference.
153  return;
154  }
155  reset(NewUserTag, NewLR, NewLiveUnion);
156  }
157 
158  // Does this live virtual register interfere with the union?
159  bool checkInterference() { return collectInterferingVRegs(1); }
160 
161  // Vector generated by collectInterferingVRegs.
163  unsigned MaxInterferingRegs = std::numeric_limits<unsigned>::max()) {
164  if (!SeenAllInterferences || MaxInterferingRegs < InterferingVRegs.size())
165  collectInterferingVRegs(MaxInterferingRegs);
166  return InterferingVRegs;
167  }
168  };
169 
170  // Array of LiveIntervalUnions.
171  class Array {
172  unsigned Size = 0;
173  LiveIntervalUnion *LIUs = nullptr;
174 
175  public:
176  Array() = default;
177  ~Array() { clear(); }
178 
179  // Initialize the array to have Size entries.
180  // Reuse an existing allocation if the size matches.
181  void init(LiveIntervalUnion::Allocator&, unsigned Size);
182 
183  unsigned size() const { return Size; }
184 
185  void clear();
186 
187  LiveIntervalUnion& operator[](unsigned idx) {
188  assert(idx < Size && "idx out of bounds");
189  return LIUs[idx];
190  }
191 
192  const LiveIntervalUnion& operator[](unsigned Idx) const {
193  assert(Idx < Size && "Idx out of bounds");
194  return LIUs[Idx];
195  }
196  };
197 };
198 
199 } // end namespace llvm
200 
201 #endif // LLVM_CODEGEN_LIVEINTERVALUNION_H
llvm::LiveIntervalUnion::Query::operator=
Query & operator=(const Query &)=delete
llvm::LiveIntervalUnion::Array::size
unsigned size() const
Definition: LiveIntervalUnion.h:183
llvm::LiveIntervalUnion::Array
Definition: LiveIntervalUnion.h:171
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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:137
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
llvm::LiveIntervalUnion::Array::clear
void clear()
Definition: LiveIntervalUnion.cpp:207
llvm::LiveIntervalUnion::Query::Query
Query(const LiveRange &LR, const LiveIntervalUnion &LIU)
Definition: LiveIntervalUnion.h:132
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:236
llvm::LiveIntervalUnion::Query::init
void init(unsigned NewUserTag, const LiveRange &NewLR, const LiveIntervalUnion &NewLiveUnion)
Definition: LiveIntervalUnion.h:148
llvm::max
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
llvm::dwarf::Tag
Tag
Definition: Dwarf.h:105
llvm::LiveIntervalUnion::getOneVReg
const LiveInterval * getOneVReg() const
NDEBUG.
Definition: LiveIntervalUnion.cpp:104
llvm::LiveIntervalUnion::end
SegmentIter end()
Definition: LiveIntervalUnion.h:70
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1628
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:256
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:52
llvm::LiveInterval
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:686
llvm::IntervalMap< SlotIndex, const LiveInterval * >::iterator
friend class iterator
Definition: IntervalMap.h:1144
llvm::SlotIndex
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:82
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:84
llvm::IntervalMap< SlotIndex, const LiveInterval * >::Allocator
typename Sizer::Allocator Allocator
Definition: IntervalMap.h:962
llvm::LiveIntervalUnion::extract
void extract(const LiveInterval &VirtReg, const LiveRange &Range)
Definition: LiveIntervalUnion.cpp:57
llvm::LiveIntervalUnion::find
ConstSegmentIter find(SlotIndex x) const
Definition: LiveIntervalUnion.h:74
llvm::LiveIntervalUnion::Array::operator[]
LiveIntervalUnion & operator[](unsigned idx)
Definition: LiveIntervalUnion.h:187
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< const LiveInterval * > & interferingVRegs(unsigned MaxInterferingRegs=std::numeric_limits< unsigned >::max())
Definition: LiveIntervalUnion.h:162
llvm::LiveIntervalUnion::Array::Array
Array()=default
llvm::LiveIntervalUnion::Query::Query
Query()=default
llvm::LiveIntervalUnion::Array::~Array
~Array()
Definition: LiveIntervalUnion.h:177
llvm::LiveIntervalUnion::Query::checkInterference
bool checkInterference()
Definition: LiveIntervalUnion.h:159
x
TODO unsigned x
Definition: README.txt:10
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:614
llvm::LiveIntervalUnion::Array::operator[]
const LiveIntervalUnion & operator[](unsigned Idx) const
Definition: LiveIntervalUnion.h:192
LiveInterval.h
llvm::LiveIntervalUnion::verify
void verify(LiveVirtRegBitSet &VisitedVRegs)
Definition: LiveIntervalUnion.cpp:98
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::LiveIntervalUnion::unify
void unify(const LiveInterval &VirtReg, const LiveRange &Range)
Definition: LiveIntervalUnion.cpp:29
llvm::IntervalMap< SlotIndex, const LiveInterval * >
llvm::IntervalMap< SlotIndex, const LiveInterval * >::const_iterator
friend class const_iterator
Definition: IntervalMap.h:1142
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
SlotIndexes.h