LLVM  14.0.0git
SetVector.h
Go to the documentation of this file.
1 //===- llvm/ADT/SetVector.h - Set with insert order iteration ---*- 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 // This file implements a set that has insertion order iteration
10 // characteristics. This is useful for keeping a set of things that need to be
11 // visited later but in a deterministic order (insertion order). The interface
12 // is purposefully minimal.
13 //
14 // This file defines SetVector and SmallSetVector, which performs no allocations
15 // if the SetVector has less than a certain number of elements.
16 //
17 //===----------------------------------------------------------------------===//
18 
19 #ifndef LLVM_ADT_SETVECTOR_H
20 #define LLVM_ADT_SETVECTOR_H
21 
22 #include "llvm/ADT/ArrayRef.h"
23 #include "llvm/ADT/DenseSet.h"
24 #include "llvm/ADT/STLExtras.h"
25 #include "llvm/Support/Compiler.h"
26 #include <algorithm>
27 #include <cassert>
28 #include <iterator>
29 #include <vector>
30 
31 namespace llvm {
32 
33 /// A vector that has set insertion semantics.
34 ///
35 /// This adapter class provides a way to keep a set of things that also has the
36 /// property of a deterministic iteration order. The order of iteration is the
37 /// order of insertion.
38 template <typename T, typename Vector = std::vector<T>,
39  typename Set = DenseSet<T>>
40 class SetVector {
41 public:
42  using value_type = T;
43  using key_type = T;
44  using reference = T&;
45  using const_reference = const T&;
46  using set_type = Set;
50  using reverse_iterator = typename vector_type::const_reverse_iterator;
51  using const_reverse_iterator = typename vector_type::const_reverse_iterator;
53 
54  /// Construct an empty SetVector
55  SetVector() = default;
56 
57  /// Initialize a SetVector with a range of elements
58  template<typename It>
59  SetVector(It Start, It End) {
60  insert(Start, End);
61  }
62 
63  ArrayRef<T> getArrayRef() const { return vector_; }
64 
65  /// Clear the SetVector and return the underlying vector.
67  set_.clear();
68  return std::move(vector_);
69  }
70 
71  /// Determine if the SetVector is empty or not.
72  bool empty() const {
73  return vector_.empty();
74  }
75 
76  /// Determine the number of elements in the SetVector.
77  size_type size() const {
78  return vector_.size();
79  }
80 
81  /// Get an iterator to the beginning of the SetVector.
83  return vector_.begin();
84  }
85 
86  /// Get a const_iterator to the beginning of the SetVector.
88  return vector_.begin();
89  }
90 
91  /// Get an iterator to the end of the SetVector.
93  return vector_.end();
94  }
95 
96  /// Get a const_iterator to the end of the SetVector.
97  const_iterator end() const {
98  return vector_.end();
99  }
100 
101  /// Get an reverse_iterator to the end of the SetVector.
103  return vector_.rbegin();
104  }
105 
106  /// Get a const_reverse_iterator to the end of the SetVector.
108  return vector_.rbegin();
109  }
110 
111  /// Get a reverse_iterator to the beginning of the SetVector.
113  return vector_.rend();
114  }
115 
116  /// Get a const_reverse_iterator to the beginning of the SetVector.
118  return vector_.rend();
119  }
120 
121  /// Return the first element of the SetVector.
122  const T &front() const {
123  assert(!empty() && "Cannot call front() on empty SetVector!");
124  return vector_.front();
125  }
126 
127  /// Return the last element of the SetVector.
128  const T &back() const {
129  assert(!empty() && "Cannot call back() on empty SetVector!");
130  return vector_.back();
131  }
132 
133  /// Index into the SetVector.
135  assert(n < vector_.size() && "SetVector access out of range!");
136  return vector_[n];
137  }
138 
139  /// Insert a new element into the SetVector.
140  /// \returns true if the element was inserted into the SetVector.
141  bool insert(const value_type &X) {
142  bool result = set_.insert(X).second;
143  if (result)
144  vector_.push_back(X);
145  return result;
146  }
147 
148  /// Insert a range of elements into the SetVector.
149  template<typename It>
150  void insert(It Start, It End) {
151  for (; Start != End; ++Start)
152  if (set_.insert(*Start).second)
153  vector_.push_back(*Start);
154  }
155 
156  /// Remove an item from the set vector.
157  bool remove(const value_type& X) {
158  if (set_.erase(X)) {
159  typename vector_type::iterator I = find(vector_, X);
160  assert(I != vector_.end() && "Corrupted SetVector instances!");
161  vector_.erase(I);
162  return true;
163  }
164  return false;
165  }
166 
167  /// Erase a single element from the set vector.
168  /// \returns an iterator pointing to the next element that followed the
169  /// element erased. This is the end of the SetVector if the last element is
170  /// erased.
172  const key_type &V = *I;
173  assert(set_.count(V) && "Corrupted SetVector instances!");
174  set_.erase(V);
175 
176  // FIXME: No need to use the non-const iterator when built with
177  // std::vector.erase(const_iterator) as defined in C++11. This is for
178  // compatibility with non-standard libstdc++ up to 4.8 (fixed in 4.9).
179  auto NI = vector_.begin();
180  std::advance(NI, std::distance<iterator>(NI, I));
181 
182  return vector_.erase(NI);
183  }
184 
185  /// Remove items from the set vector based on a predicate function.
186  ///
187  /// This is intended to be equivalent to the following code, if we could
188  /// write it:
189  ///
190  /// \code
191  /// V.erase(remove_if(V, P), V.end());
192  /// \endcode
193  ///
194  /// However, SetVector doesn't expose non-const iterators, making any
195  /// algorithm like remove_if impossible to use.
196  ///
197  /// \returns true if any element is removed.
198  template <typename UnaryPredicate>
199  bool remove_if(UnaryPredicate P) {
200  typename vector_type::iterator I =
201  llvm::remove_if(vector_, TestAndEraseFromSet<UnaryPredicate>(P, set_));
202  if (I == vector_.end())
203  return false;
204  vector_.erase(I, vector_.end());
205  return true;
206  }
207 
208  /// Check if the SetVector contains the given key.
209  bool contains(const key_type &key) const {
210  return set_.find(key) != set_.end();
211  }
212 
213  /// Count the number of elements of a given key in the SetVector.
214  /// \returns 0 if the element is not in the SetVector, 1 if it is.
215  size_type count(const key_type &key) const {
216  return set_.count(key);
217  }
218 
219  /// Completely clear the SetVector
220  void clear() {
221  set_.clear();
222  vector_.clear();
223  }
224 
225  /// Remove the last element of the SetVector.
226  void pop_back() {
227  assert(!empty() && "Cannot remove an element from an empty SetVector!");
228  set_.erase(back());
229  vector_.pop_back();
230  }
231 
233  T Ret = back();
234  pop_back();
235  return Ret;
236  }
237 
238  bool operator==(const SetVector &that) const {
239  return vector_ == that.vector_;
240  }
241 
242  bool operator!=(const SetVector &that) const {
243  return vector_ != that.vector_;
244  }
245 
246  /// Compute This := This u S, return whether 'This' changed.
247  /// TODO: We should be able to use set_union from SetOperations.h, but
248  /// SetVector interface is inconsistent with DenseSet.
249  template <class STy>
250  bool set_union(const STy &S) {
251  bool Changed = false;
252 
253  for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE;
254  ++SI)
255  if (insert(*SI))
256  Changed = true;
257 
258  return Changed;
259  }
260 
261  /// Compute This := This - B
262  /// TODO: We should be able to use set_subtract from SetOperations.h, but
263  /// SetVector interface is inconsistent with DenseSet.
264  template <class STy>
265  void set_subtract(const STy &S) {
266  for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE;
267  ++SI)
268  remove(*SI);
269  }
270 
272  set_.swap(RHS.set_);
273  vector_.swap(RHS.vector_);
274  }
275 
276 private:
277  /// A wrapper predicate designed for use with std::remove_if.
278  ///
279  /// This predicate wraps a predicate suitable for use with std::remove_if to
280  /// call set_.erase(x) on each element which is slated for removal.
281  template <typename UnaryPredicate>
282  class TestAndEraseFromSet {
283  UnaryPredicate P;
284  set_type &set_;
285 
286  public:
287  TestAndEraseFromSet(UnaryPredicate P, set_type &set_)
288  : P(std::move(P)), set_(set_) {}
289 
290  template <typename ArgumentT>
291  bool operator()(const ArgumentT &Arg) {
292  if (P(Arg)) {
293  set_.erase(Arg);
294  return true;
295  }
296  return false;
297  }
298  };
299 
300  set_type set_; ///< The set.
301  vector_type vector_; ///< The vector.
302 };
303 
304 /// A SetVector that performs no allocations if smaller than
305 /// a certain size.
306 template <typename T, unsigned N>
308  : public SetVector<T, SmallVector<T, N>, SmallDenseSet<T, N>> {
309 public:
310  SmallSetVector() = default;
311 
312  /// Initialize a SmallSetVector with a range of elements
313  template<typename It>
314  SmallSetVector(It Start, It End) {
315  this->insert(Start, End);
316  }
317 };
318 
319 } // end namespace llvm
320 
321 namespace std {
322 
323 /// Implement std::swap in terms of SetVector swap.
324 template<typename T, typename V, typename S>
325 inline void
327  LHS.swap(RHS);
328 }
329 
330 /// Implement std::swap in terms of SmallSetVector swap.
331 template<typename T, unsigned N>
332 inline void
334  LHS.swap(RHS);
335 }
336 
337 } // end namespace std
338 
339 #endif // LLVM_ADT_SETVECTOR_H
llvm::SetVector::insert
void insert(It Start, It End)
Insert a range of elements into the SetVector.
Definition: SetVector.h:150
llvm::SetVector< llvm::ElementCount, SmallVector< llvm::ElementCount, N >, SmallDenseSet< llvm::ElementCount, N > >::size_type
typename vector_type::size_type size_type
Definition: SetVector.h:52
llvm::SmallSetVector::SmallSetVector
SmallSetVector()=default
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::ElementCount
Definition: TypeSize.h:386
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::SetVector::size
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:77
llvm::SetVector::rend
const_reverse_iterator rend() const
Get a const_reverse_iterator to the beginning of the SetVector.
Definition: SetVector.h:117
llvm::SetVector::pop_back
void pop_back()
Remove the last element of the SetVector.
Definition: SetVector.h:226
llvm::SmallVector< llvm::ElementCount, N >
llvm::SmallDenseSet< llvm::ElementCount, N >
llvm::SetVector::SetVector
SetVector(It Start, It End)
Initialize a SetVector with a range of elements.
Definition: SetVector.h:59
llvm::SetVector< llvm::ElementCount, SmallVector< llvm::ElementCount, N >, SmallDenseSet< llvm::ElementCount, N > >::iterator
typename vector_type::const_iterator iterator
Definition: SetVector.h:48
llvm::SetVector< llvm::ElementCount, SmallVector< llvm::ElementCount, N >, SmallDenseSet< llvm::ElementCount, N > >::const_iterator
typename vector_type::const_iterator const_iterator
Definition: SetVector.h:49
llvm::SetVector::getArrayRef
ArrayRef< T > getArrayRef() const
Definition: SetVector.h:63
llvm::SetVector::SetVector
SetVector()=default
Construct an empty SetVector.
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::SetVector::vector_type
Vector vector_type
Definition: SetVector.h:47
llvm::MipsISD::Ret
@ Ret
Definition: MipsISelLowering.h:116
STLExtras.h
that
we should consider alternate ways to model stack dependencies Lots of things could be done in WebAssemblyTargetTransformInfo cpp there are numerous optimization related hooks that can be overridden in WebAssemblyTargetLowering Instead of the OptimizeReturned which should consider preserving the returned attribute through to MachineInstrs and extending the MemIntrinsicResults pass to do this optimization on calls too That would also let the WebAssemblyPeephole pass clean up dead defs for such as it does for stores Consider implementing and or getMachineCombinerPatterns Find a clean way to fix the problem which leads to the Shrink Wrapping pass being run after the WebAssembly PEI pass When setting multiple variables to the same we currently get code like const It could be done with a smaller encoding like local tee $pop5 local $pop6 WebAssembly registers are implicitly initialized to zero Explicit zeroing is therefore often redundant and could be optimized away Small indices may use smaller encodings than large indices WebAssemblyRegColoring and or WebAssemblyRegRenumbering should sort registers according to their usage frequency to maximize the usage of smaller encodings Many cases of irreducible control flow could be transformed more optimally than via the transform in WebAssemblyFixIrreducibleControlFlow cpp It may also be worthwhile to do transforms before register particularly when duplicating to allow register coloring to be aware of the duplication WebAssemblyRegStackify could use AliasAnalysis to reorder loads and stores more aggressively WebAssemblyRegStackify is currently a greedy algorithm This means that
Definition: README.txt:130
llvm::SetVector::remove_if
bool remove_if(UnaryPredicate P)
Remove items from the set vector based on a predicate function.
Definition: SetVector.h:199
llvm::SetVector::operator!=
bool operator!=(const SetVector &that) const
Definition: SetVector.h:242
llvm::SetVector::rend
reverse_iterator rend()
Get a reverse_iterator to the beginning of the SetVector.
Definition: SetVector.h:112
result
It looks like we only need to define PPCfmarto for these because according to these instructions perform RTO on fma s result
Definition: README_P9.txt:256
llvm::SetVector::rbegin
const_reverse_iterator rbegin() const
Get a const_reverse_iterator to the end of the SetVector.
Definition: SetVector.h:107
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:206
llvm::remove_if
auto remove_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::remove_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1586
llvm::SetVector::swap
void swap(SetVector< T, Vector, Set > &RHS)
Definition: SetVector.h:271
llvm::SetVector::remove
bool remove(const value_type &X)
Remove an item from the set vector.
Definition: SetVector.h:157
llvm::SetVector::begin
iterator begin()
Get an iterator to the beginning of the SetVector.
Definition: SetVector.h:82
llvm::SetVector::set_type
Set set_type
Definition: SetVector.h:46
DenseSet.h
llvm::SmallSetVector::SmallSetVector
SmallSetVector(It Start, It End)
Initialize a SmallSetVector with a range of elements.
Definition: SetVector.h:314
llvm::SetVector::end
const_iterator end() const
Get a const_iterator to the end of the SetVector.
Definition: SetVector.h:97
llvm::SetVector::empty
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:72
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::SetVector::set_union
bool set_union(const STy &S)
Compute This := This u S, return whether 'This' changed.
Definition: SetVector.h:250
llvm::SetVector< llvm::ElementCount, SmallVector< llvm::ElementCount, N >, SmallDenseSet< llvm::ElementCount, N > >::reverse_iterator
typename vector_type::const_reverse_iterator reverse_iterator
Definition: SetVector.h:50
llvm::SetVector< llvm::ElementCount, SmallVector< llvm::ElementCount, N >, SmallDenseSet< llvm::ElementCount, N > >::const_reverse_iterator
typename vector_type::const_reverse_iterator const_reverse_iterator
Definition: SetVector.h:51
llvm::SetVector::contains
bool contains(const key_type &key) const
Check if the SetVector contains the given key.
Definition: SetVector.h:209
llvm::find
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1567
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::SetVector::set_subtract
void set_subtract(const STy &S)
Compute This := This - B TODO: We should be able to use set_subtract from SetOperations....
Definition: SetVector.h:265
ArrayRef.h
llvm::SmallVectorImpl< llvm::ElementCount >::const_iterator
typename SuperClass::const_iterator const_iterator
Definition: SmallVector.h:563
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::move
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1605
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:840
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::SetVector::insert
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
llvm::SetVector::rbegin
reverse_iterator rbegin()
Get an reverse_iterator to the end of the SetVector.
Definition: SetVector.h:102
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
Compiler.h
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::SetVector::clear
void clear()
Completely clear the SetVector.
Definition: SetVector.h:220
llvm::SetVector::operator[]
const_reference operator[](size_type n) const
Index into the SetVector.
Definition: SetVector.h:134
llvm::SetVector::operator==
bool operator==(const SetVector &that) const
Definition: SetVector.h:238
std
Definition: BitVector.h:838
LLVM_NODISCARD
#define LLVM_NODISCARD
LLVM_NODISCARD - Warn if a type or return value is discarded.
Definition: Compiler.h:161
llvm::SetVector::count
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:215
llvm::SetVector::front
const T & front() const
Return the first element of the SetVector.
Definition: SetVector.h:122
Vector
So we should use XX3Form_Rcr to implement instrinsic Convert DP outs ins xscvdpsp No builtin are required Round &Convert QP DP(dword[1] is set to zero) No builtin are required Round to Quad Precision because you need to assign rounding mode in instruction Provide builtin(set f128:$vT,(int_ppc_vsx_xsrqpi f128:$vB))(set f128 yields< n x< ty > >< result > yields< ty >< result > No builtin are required Load Store Vector
Definition: README_P9.txt:497
llvm::SetVector::end
iterator end()
Get an iterator to the end of the SetVector.
Definition: SetVector.h:92
llvm::SmallVectorImpl< llvm::ElementCount >::iterator
typename SuperClass::iterator iterator
Definition: SmallVector.h:562
llvm::SmallVectorImpl< llvm::ElementCount >::size_type
typename SuperClass::size_type size_type
Definition: SmallVector.h:565
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
llvm::SetVector::back
const T & back() const
Return the last element of the SetVector.
Definition: SetVector.h:128
llvm::SetVector::takeVector
Vector takeVector()
Clear the SetVector and return the underlying vector.
Definition: SetVector.h:66
n
The same transformation can work with an even modulo with the addition of a and shrink the compare RHS by the same amount Unless the target supports that transformation probably isn t worthwhile The transformation can also easily be made to work with non zero equality for n
Definition: README.txt:685
llvm::SetVector
A vector that has set insertion semantics.
Definition: SetVector.h:40
llvm::SetVector::erase
iterator erase(iterator I)
Erase a single element from the set vector.
Definition: SetVector.h:171
llvm::SetVector::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SetVector.h:232
llvm::SetVector::begin
const_iterator begin() const
Get a const_iterator to the beginning of the SetVector.
Definition: SetVector.h:87