LLVM  14.0.0git
SmallPtrSet.h
Go to the documentation of this file.
1 //===- llvm/ADT/SmallPtrSet.h - 'Normally small' pointer set ----*- 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 defines the SmallPtrSet class. See the doxygen comment for
10 // SmallPtrSetImplBase for more details on the algorithm used.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_ADT_SMALLPTRSET_H
15 #define LLVM_ADT_SMALLPTRSET_H
16 
17 #include "llvm/ADT/EpochTracker.h"
18 #include "llvm/Support/Compiler.h"
21 #include <cassert>
22 #include <cstddef>
23 #include <cstdlib>
24 #include <cstring>
25 #include <initializer_list>
26 #include <iterator>
27 #include <utility>
28 
29 namespace llvm {
30 
31 /// SmallPtrSetImplBase - This is the common code shared among all the
32 /// SmallPtrSet<>'s, which is almost everything. SmallPtrSet has two modes, one
33 /// for small and one for large sets.
34 ///
35 /// Small sets use an array of pointers allocated in the SmallPtrSet object,
36 /// which is treated as a simple array of pointers. When a pointer is added to
37 /// the set, the array is scanned to see if the element already exists, if not
38 /// the element is 'pushed back' onto the array. If we run out of space in the
39 /// array, we grow into the 'large set' case. SmallSet should be used when the
40 /// sets are often small. In this case, no memory allocation is used, and only
41 /// light-weight and cache-efficient scanning is used.
42 ///
43 /// Large sets use a classic exponentially-probed hash table. Empty buckets are
44 /// represented with an illegal pointer value (-1) to allow null pointers to be
45 /// inserted. Tombstones are represented with another illegal pointer value
46 /// (-2), to allow deletion. The hash table is resized when the table is 3/4 or
47 /// more. When this happens, the table is doubled in size.
48 ///
51 
52 protected:
53  /// SmallArray - Points to a fixed size set of buckets, used in 'small mode'.
54  const void **SmallArray;
55  /// CurArray - This is the current set of buckets. If equal to SmallArray,
56  /// then the set is in 'small mode'.
57  const void **CurArray;
58  /// CurArraySize - The allocated size of CurArray, always a power of two.
59  unsigned CurArraySize;
60 
61  /// Number of elements in CurArray that contain a value or are a tombstone.
62  /// If small, all these elements are at the beginning of CurArray and the rest
63  /// is uninitialized.
64  unsigned NumNonEmpty;
65  /// Number of tombstones in CurArray.
66  unsigned NumTombstones;
67 
68  // Helpers to copy and move construct a SmallPtrSet.
69  SmallPtrSetImplBase(const void **SmallStorage,
70  const SmallPtrSetImplBase &that);
71  SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize,
73 
74  explicit SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize)
75  : SmallArray(SmallStorage), CurArray(SmallStorage),
76  CurArraySize(SmallSize), NumNonEmpty(0), NumTombstones(0) {
77  assert(SmallSize && (SmallSize & (SmallSize-1)) == 0 &&
78  "Initial size must be a power of two!");
79  }
80 
82  if (!isSmall())
83  free(CurArray);
84  }
85 
86 public:
87  using size_type = unsigned;
88 
90 
91  LLVM_NODISCARD bool empty() const { return size() == 0; }
92  size_type size() const { return NumNonEmpty - NumTombstones; }
93 
94  void clear() {
96  // If the capacity of the array is huge, and the # elements used is small,
97  // shrink the array.
98  if (!isSmall()) {
99  if (size() * 4 < CurArraySize && CurArraySize > 32)
100  return shrink_and_clear();
101  // Fill the array with empty markers.
102  memset(CurArray, -1, CurArraySize * sizeof(void *));
103  }
104 
105  NumNonEmpty = 0;
106  NumTombstones = 0;
107  }
108 
109 protected:
110  static void *getTombstoneMarker() { return reinterpret_cast<void*>(-2); }
111 
112  static void *getEmptyMarker() {
113  // Note that -1 is chosen to make clear() efficiently implementable with
114  // memset and because it's not a valid pointer value.
115  return reinterpret_cast<void*>(-1);
116  }
117 
118  const void **EndPointer() const {
119  return isSmall() ? CurArray + NumNonEmpty : CurArray + CurArraySize;
120  }
121 
122  /// insert_imp - This returns true if the pointer was new to the set, false if
123  /// it was already in the set. This is hidden from the client so that the
124  /// derived class can check that the right type of pointer is passed in.
125  std::pair<const void *const *, bool> insert_imp(const void *Ptr) {
126  if (isSmall()) {
127  // Check to see if it is already in the set.
128  const void **LastTombstone = nullptr;
129  for (const void **APtr = SmallArray, **E = SmallArray + NumNonEmpty;
130  APtr != E; ++APtr) {
131  const void *Value = *APtr;
132  if (Value == Ptr)
133  return std::make_pair(APtr, false);
134  if (Value == getTombstoneMarker())
135  LastTombstone = APtr;
136  }
137 
138  // Did we find any tombstone marker?
139  if (LastTombstone != nullptr) {
140  *LastTombstone = Ptr;
141  --NumTombstones;
142  incrementEpoch();
143  return std::make_pair(LastTombstone, true);
144  }
145 
146  // Nope, there isn't. If we stay small, just 'pushback' now.
147  if (NumNonEmpty < CurArraySize) {
148  SmallArray[NumNonEmpty++] = Ptr;
149  incrementEpoch();
150  return std::make_pair(SmallArray + (NumNonEmpty - 1), true);
151  }
152  // Otherwise, hit the big set case, which will call grow.
153  }
154  return insert_imp_big(Ptr);
155  }
156 
157  /// erase_imp - If the set contains the specified pointer, remove it and
158  /// return true, otherwise return false. This is hidden from the client so
159  /// that the derived class can check that the right type of pointer is passed
160  /// in.
161  bool erase_imp(const void * Ptr) {
162  const void *const *P = find_imp(Ptr);
163  if (P == EndPointer())
164  return false;
165 
166  const void **Loc = const_cast<const void **>(P);
167  assert(*Loc == Ptr && "broken find!");
168  *Loc = getTombstoneMarker();
169  NumTombstones++;
170  return true;
171  }
172 
173  /// Returns the raw pointer needed to construct an iterator. If element not
174  /// found, this will be EndPointer. Otherwise, it will be a pointer to the
175  /// slot which stores Ptr;
176  const void *const * find_imp(const void * Ptr) const {
177  if (isSmall()) {
178  // Linear search for the item.
179  for (const void *const *APtr = SmallArray,
180  *const *E = SmallArray + NumNonEmpty; APtr != E; ++APtr)
181  if (*APtr == Ptr)
182  return APtr;
183  return EndPointer();
184  }
185 
186  // Big set case.
187  auto *Bucket = FindBucketFor(Ptr);
188  if (*Bucket == Ptr)
189  return Bucket;
190  return EndPointer();
191  }
192 
193 private:
194  bool isSmall() const { return CurArray == SmallArray; }
195 
196  std::pair<const void *const *, bool> insert_imp_big(const void *Ptr);
197 
198  const void * const *FindBucketFor(const void *Ptr) const;
199  void shrink_and_clear();
200 
201  /// Grow - Allocate a larger backing store for the buckets and move it over.
202  void Grow(unsigned NewSize);
203 
204 protected:
205  /// swap - Swaps the elements of two sets.
206  /// Note: This method assumes that both sets have the same small size.
207  void swap(SmallPtrSetImplBase &RHS);
208 
209  void CopyFrom(const SmallPtrSetImplBase &RHS);
210  void MoveFrom(unsigned SmallSize, SmallPtrSetImplBase &&RHS);
211 
212 private:
213  /// Code shared by MoveFrom() and move constructor.
214  void MoveHelper(unsigned SmallSize, SmallPtrSetImplBase &&RHS);
215  /// Code shared by CopyFrom() and copy constructor.
216  void CopyHelper(const SmallPtrSetImplBase &RHS);
217 };
218 
219 /// SmallPtrSetIteratorImpl - This is the common base class shared between all
220 /// instances of SmallPtrSetIterator.
222 protected:
223  const void *const *Bucket;
224  const void *const *End;
225 
226 public:
227  explicit SmallPtrSetIteratorImpl(const void *const *BP, const void*const *E)
228  : Bucket(BP), End(E) {
229  if (shouldReverseIterate()) {
231  return;
232  }
234  }
235 
236  bool operator==(const SmallPtrSetIteratorImpl &RHS) const {
237  return Bucket == RHS.Bucket;
238  }
239  bool operator!=(const SmallPtrSetIteratorImpl &RHS) const {
240  return Bucket != RHS.Bucket;
241  }
242 
243 protected:
244  /// AdvanceIfNotValid - If the current bucket isn't valid, advance to a bucket
245  /// that is. This is guaranteed to stop because the end() bucket is marked
246  /// valid.
248  assert(Bucket <= End);
249  while (Bucket != End &&
252  ++Bucket;
253  }
255  assert(Bucket >= End);
256  while (Bucket != End &&
259  --Bucket;
260  }
261  }
262 };
263 
264 /// SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet.
265 template <typename PtrTy>
269 
270 public:
271  using value_type = PtrTy;
272  using reference = PtrTy;
273  using pointer = PtrTy;
274  using difference_type = std::ptrdiff_t;
275  using iterator_category = std::forward_iterator_tag;
276 
277  explicit SmallPtrSetIterator(const void *const *BP, const void *const *E,
278  const DebugEpochBase &Epoch)
280 
281  // Most methods are provided by the base class.
282 
283  const PtrTy operator*() const {
284  assert(isHandleInSync() && "invalid iterator access!");
285  if (shouldReverseIterate()) {
286  assert(Bucket > End);
287  return PtrTraits::getFromVoidPointer(const_cast<void *>(Bucket[-1]));
288  }
289  assert(Bucket < End);
290  return PtrTraits::getFromVoidPointer(const_cast<void*>(*Bucket));
291  }
292 
293  inline SmallPtrSetIterator& operator++() { // Preincrement
294  assert(isHandleInSync() && "invalid iterator access!");
295  if (shouldReverseIterate()) {
296  --Bucket;
298  return *this;
299  }
300  ++Bucket;
302  return *this;
303  }
304 
305  SmallPtrSetIterator operator++(int) { // Postincrement
306  SmallPtrSetIterator tmp = *this;
307  ++*this;
308  return tmp;
309  }
310 };
311 
312 /// RoundUpToPowerOfTwo - This is a helper template that rounds N up to the next
313 /// power of two (which means N itself if N is already a power of two).
314 template<unsigned N>
316 
317 /// RoundUpToPowerOfTwoH - If N is not a power of two, increase it. This is a
318 /// helper template used to implement RoundUpToPowerOfTwo.
319 template<unsigned N, bool isPowerTwo>
321  enum { Val = N };
322 };
323 template<unsigned N>
325  enum {
326  // We could just use NextVal = N+1, but this converges faster. N|(N-1) sets
327  // the right-most zero bits to one all at once, e.g. 0b0011000 -> 0b0011111.
329  };
330 };
331 
332 template<unsigned N>
333 struct RoundUpToPowerOfTwo {
334  enum { Val = RoundUpToPowerOfTwoH<N, (N&(N-1)) == 0>::Val };
335 };
336 
337 /// A templated base class for \c SmallPtrSet which provides the
338 /// typesafe interface that is common across all small sizes.
339 ///
340 /// This is particularly useful for passing around between interface boundaries
341 /// to avoid encoding a particular small size in the interface boundary.
342 template <typename PtrType>
344  using ConstPtrType = typename add_const_past_pointer<PtrType>::type;
347 
348 protected:
349  // Forward constructors to the base.
351 
352 public:
355  using key_type = ConstPtrType;
356  using value_type = PtrType;
357 
358  SmallPtrSetImpl(const SmallPtrSetImpl &) = delete;
359 
360  /// Inserts Ptr if and only if there is no element in the container equal to
361  /// Ptr. The bool component of the returned pair is true if and only if the
362  /// insertion takes place, and the iterator component of the pair points to
363  /// the element equal to Ptr.
364  std::pair<iterator, bool> insert(PtrType Ptr) {
365  auto p = insert_imp(PtrTraits::getAsVoidPointer(Ptr));
366  return std::make_pair(makeIterator(p.first), p.second);
367  }
368 
369  /// Insert the given pointer with an iterator hint that is ignored. This is
370  /// identical to calling insert(Ptr), but allows SmallPtrSet to be used by
371  /// std::insert_iterator and std::inserter().
372  iterator insert(iterator, PtrType Ptr) {
373  return insert(Ptr).first;
374  }
375 
376  /// erase - If the set contains the specified pointer, remove it and return
377  /// true, otherwise return false.
378  bool erase(PtrType Ptr) {
379  return erase_imp(PtrTraits::getAsVoidPointer(Ptr));
380  }
381  /// count - Return 1 if the specified pointer is in the set, 0 otherwise.
382  size_type count(ConstPtrType Ptr) const {
383  return find_imp(ConstPtrTraits::getAsVoidPointer(Ptr)) != EndPointer();
384  }
385  iterator find(ConstPtrType Ptr) const {
386  return makeIterator(find_imp(ConstPtrTraits::getAsVoidPointer(Ptr)));
387  }
388  bool contains(ConstPtrType Ptr) const {
389  return find_imp(ConstPtrTraits::getAsVoidPointer(Ptr)) != EndPointer();
390  }
391 
392  template <typename IterT>
393  void insert(IterT I, IterT E) {
394  for (; I != E; ++I)
395  insert(*I);
396  }
397 
398  void insert(std::initializer_list<PtrType> IL) {
399  insert(IL.begin(), IL.end());
400  }
401 
402  iterator begin() const {
403  if (shouldReverseIterate())
404  return makeIterator(EndPointer() - 1);
405  return makeIterator(CurArray);
406  }
407  iterator end() const { return makeIterator(EndPointer()); }
408 
409 private:
410  /// Create an iterator that dereferences to same place as the given pointer.
411  iterator makeIterator(const void *const *P) const {
412  if (shouldReverseIterate())
413  return iterator(P == EndPointer() ? CurArray : P + 1, CurArray, *this);
414  return iterator(P, EndPointer(), *this);
415  }
416 };
417 
418 /// Equality comparison for SmallPtrSet.
419 ///
420 /// Iterates over elements of LHS confirming that each value from LHS is also in
421 /// RHS, and that no additional values are in RHS.
422 template <typename PtrType>
424  const SmallPtrSetImpl<PtrType> &RHS) {
425  if (LHS.size() != RHS.size())
426  return false;
427 
428  for (const auto *KV : LHS)
429  if (!RHS.count(KV))
430  return false;
431 
432  return true;
433 }
434 
435 /// Inequality comparison for SmallPtrSet.
436 ///
437 /// Equivalent to !(LHS == RHS).
438 template <typename PtrType>
440  const SmallPtrSetImpl<PtrType> &RHS) {
441  return !(LHS == RHS);
442 }
443 
444 /// SmallPtrSet - This class implements a set which is optimized for holding
445 /// SmallSize or less elements. This internally rounds up SmallSize to the next
446 /// power of two if it is not already a power of two. See the comments above
447 /// SmallPtrSetImplBase for details of the algorithm.
448 template<class PtrType, unsigned SmallSize>
449 class SmallPtrSet : public SmallPtrSetImpl<PtrType> {
450  // In small mode SmallPtrSet uses linear search for the elements, so it is
451  // not a good idea to choose this value too high. You may consider using a
452  // DenseSet<> instead if you expect many elements in the set.
453  static_assert(SmallSize <= 32, "SmallSize should be small");
454 
456 
457  // Make sure that SmallSize is a power of two, round up if not.
458  enum { SmallSizePowTwo = RoundUpToPowerOfTwo<SmallSize>::Val };
459  /// SmallStorage - Fixed size storage used in 'small mode'.
460  const void *SmallStorage[SmallSizePowTwo];
461 
462 public:
463  SmallPtrSet() : BaseT(SmallStorage, SmallSizePowTwo) {}
464  SmallPtrSet(const SmallPtrSet &that) : BaseT(SmallStorage, that) {}
466  : BaseT(SmallStorage, SmallSizePowTwo, std::move(that)) {}
467 
468  template<typename It>
469  SmallPtrSet(It I, It E) : BaseT(SmallStorage, SmallSizePowTwo) {
470  this->insert(I, E);
471  }
472 
473  SmallPtrSet(std::initializer_list<PtrType> IL)
474  : BaseT(SmallStorage, SmallSizePowTwo) {
475  this->insert(IL.begin(), IL.end());
476  }
477 
480  if (&RHS != this)
481  this->CopyFrom(RHS);
482  return *this;
483  }
484 
487  if (&RHS != this)
488  this->MoveFrom(SmallSizePowTwo, std::move(RHS));
489  return *this;
490  }
491 
493  operator=(std::initializer_list<PtrType> IL) {
494  this->clear();
495  this->insert(IL.begin(), IL.end());
496  return *this;
497  }
498 
499  /// swap - Swaps the elements of two sets.
502  }
503 };
504 
505 } // end namespace llvm
506 
507 namespace std {
508 
509  /// Implement std::swap in terms of SmallPtrSet swap.
510  template<class T, unsigned N>
512  LHS.swap(RHS);
513  }
514 
515 } // end namespace std
516 
517 #endif // LLVM_ADT_SMALLPTRSET_H
llvm::SmallPtrSetImplBase::insert_imp
std::pair< const void *const *, bool > insert_imp(const void *Ptr)
insert_imp - This returns true if the pointer was new to the set, false if it was already in the set.
Definition: SmallPtrSet.h:125
llvm::SmallPtrSetImplBase::operator=
SmallPtrSetImplBase & operator=(const SmallPtrSetImplBase &)=delete
llvm::SmallPtrSetImplBase::swap
void swap(SmallPtrSetImplBase &RHS)
swap - Swaps the elements of two sets.
Definition: SmallPtrSet.cpp:214
llvm::SmallPtrSetImpl< CallBase * >::key_type
ConstPtrType key_type
Definition: SmallPtrSet.h:355
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::SmallPtrSet::operator=
SmallPtrSet< PtrType, SmallSize > & operator=(const SmallPtrSet< PtrType, SmallSize > &RHS)
Definition: SmallPtrSet.h:479
llvm::SmallPtrSetImpl::erase
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
Definition: SmallPtrSet.h:378
llvm::SmallPtrSetImplBase::NumNonEmpty
unsigned NumNonEmpty
Number of elements in CurArray that contain a value or are a tombstone.
Definition: SmallPtrSet.h:64
llvm::SmallPtrSetIteratorImpl
SmallPtrSetIteratorImpl - This is the common base class shared between all instances of SmallPtrSetIt...
Definition: SmallPtrSet.h:221
llvm::SmallPtrSetImplBase
SmallPtrSetImplBase - This is the common code shared among all the SmallPtrSet<>'s,...
Definition: SmallPtrSet.h:49
llvm::SmallPtrSet::swap
void swap(SmallPtrSet< PtrType, SmallSize > &RHS)
swap - Swaps the elements of two sets.
Definition: SmallPtrSet.h:500
ReverseIteration.h
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::SmallPtrSetImplBase::~SmallPtrSetImplBase
~SmallPtrSetImplBase()
Definition: SmallPtrSet.h:81
llvm::SmallPtrSet::SmallPtrSet
SmallPtrSet(std::initializer_list< PtrType > IL)
Definition: SmallPtrSet.h:473
llvm::shouldReverseIterate
bool shouldReverseIterate()
Definition: ReverseIteration.h:10
llvm::SmallPtrSetIteratorImpl::operator==
bool operator==(const SmallPtrSetIteratorImpl &RHS) const
Definition: SmallPtrSet.h:236
llvm::SmallPtrSetImplBase::erase_imp
bool erase_imp(const void *Ptr)
erase_imp - If the set contains the specified pointer, remove it and return true, otherwise return fa...
Definition: SmallPtrSet.h:161
llvm::SmallPtrSetIterator::value_type
PtrTy value_type
Definition: SmallPtrSet.h:271
llvm::SmallPtrSetIterator
SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet.
Definition: SmallPtrSet.h:266
llvm::operator!=
bool operator!=(uint64_t V1, const APInt &V2)
Definition: APInt.h:1972
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
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
tmp
alloca< 16 x float >, align 16 %tmp2=alloca< 16 x float >, align 16 store< 16 x float > %A,< 16 x float > *%tmp %s=bitcast< 16 x float > *%tmp to i8 *%s2=bitcast< 16 x float > *%tmp2 to i8 *call void @llvm.memcpy.i64(i8 *%s, i8 *%s2, i64 64, i32 16) %R=load< 16 x float > *%tmp2 ret< 16 x float > %R } declare void @llvm.memcpy.i64(i8 *nocapture, i8 *nocapture, i64, i32) nounwind which compiles to:_foo:subl $140, %esp movaps %xmm3, 112(%esp) movaps %xmm2, 96(%esp) movaps %xmm1, 80(%esp) movaps %xmm0, 64(%esp) movl 60(%esp), %eax movl %eax, 124(%esp) movl 56(%esp), %eax movl %eax, 120(%esp) movl 52(%esp), %eax< many many more 32-bit copies > movaps(%esp), %xmm0 movaps 16(%esp), %xmm1 movaps 32(%esp), %xmm2 movaps 48(%esp), %xmm3 addl $140, %esp ret On Nehalem, it may even be cheaper to just use movups when unaligned than to fall back to lower-granularity chunks. Implement processor-specific optimizations for parity with GCC on these processors. GCC does two optimizations:1. ix86_pad_returns inserts a noop before ret instructions if immediately preceded by a conditional branch or is the target of a jump. 2. ix86_avoid_jump_misspredicts inserts noops in cases where a 16-byte block of code contains more than 3 branches. The first one is done for all AMDs, Core2, and "Generic" The second one is done for:Atom, Pentium Pro, all AMDs, Pentium 4, Nocona, Core 2, and "Generic" Testcase:int x(int a) { return(a &0xf0)> >4 tmp
Definition: README.txt:1347
p
the resulting code requires compare and branches when and if * p
Definition: README.txt:396
llvm::RoundUpToPowerOfTwo
RoundUpToPowerOfTwo - This is a helper template that rounds N up to the next power of two (which mean...
Definition: SmallPtrSet.h:315
llvm::SmallPtrSetImplBase::CurArraySize
unsigned CurArraySize
CurArraySize - The allocated size of CurArray, always a power of two.
Definition: SmallPtrSet.h:59
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::DebugEpochBase::HandleBase::HandleBase
HandleBase()=default
llvm::SmallPtrSet::SmallPtrSet
SmallPtrSet()
Definition: SmallPtrSet.h:463
llvm::SmallPtrSetIterator::operator*
const PtrTy operator*() const
Definition: SmallPtrSet.h:283
false
Definition: StackSlotColoring.cpp:142
llvm::SmallPtrSetImplBase::size_type
unsigned size_type
Definition: SmallPtrSet.h:87
llvm::SmallPtrSetIterator::SmallPtrSetIterator
SmallPtrSetIterator(const void *const *BP, const void *const *E, const DebugEpochBase &Epoch)
Definition: SmallPtrSet.h:277
llvm::SmallPtrSetIterator::reference
PtrTy reference
Definition: SmallPtrSet.h:272
llvm::SmallPtrSetImplBase::NumTombstones
unsigned NumTombstones
Number of tombstones in CurArray.
Definition: SmallPtrSet.h:66
llvm::SmallPtrSetImplBase::EndPointer
const void ** EndPointer() const
Definition: SmallPtrSet.h:118
llvm::SmallPtrSetImpl::iterator
SmallPtrSetIterator< PtrType > iterator
Definition: SmallPtrSet.h:353
llvm::SmallPtrSetIteratorImpl::Bucket
const void *const * Bucket
Definition: SmallPtrSet.h:223
llvm::SmallPtrSetImpl::find
iterator find(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:385
llvm::SmallPtrSetIteratorImpl::AdvanceIfNotValid
void AdvanceIfNotValid()
AdvanceIfNotValid - If the current bucket isn't valid, advance to a bucket that is.
Definition: SmallPtrSet.h:247
llvm::SmallPtrSetIterator::operator++
SmallPtrSetIterator & operator++()
Definition: SmallPtrSet.h:293
llvm::SmallPtrSetImpl::end
iterator end() const
Definition: SmallPtrSet.h:407
llvm::SmallPtrSetIterator::difference_type
std::ptrdiff_t difference_type
Definition: SmallPtrSet.h:274
llvm::DebugEpochBase::HandleBase::isHandleInSync
bool isHandleInSync() const
Definition: EpochTracker.h:89
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::SmallPtrSetImplBase::CurArray
const void ** CurArray
CurArray - This is the current set of buckets.
Definition: SmallPtrSet.h:57
llvm::SmallPtrSetIteratorImpl::operator!=
bool operator!=(const SmallPtrSetIteratorImpl &RHS) const
Definition: SmallPtrSet.h:239
llvm::SmallPtrSetImpl::begin
iterator begin() const
Definition: SmallPtrSet.h:402
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:1609
llvm::SmallPtrSetImplBase::getTombstoneMarker
static void * getTombstoneMarker()
Definition: SmallPtrSet.h:110
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:840
llvm::operator==
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1970
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
llvm::SmallPtrSetImplBase::getEmptyMarker
static void * getEmptyMarker()
Definition: SmallPtrSet.h:112
llvm::SmallPtrSetImpl::insert
void insert(std::initializer_list< PtrType > IL)
Definition: SmallPtrSet.h:398
llvm::SmallPtrSetImplBase::clear
void clear()
Definition: SmallPtrSet.h:94
llvm::SmallPtrSetIterator::pointer
PtrTy pointer
Definition: SmallPtrSet.h:273
llvm::SmallPtrSetIterator::operator++
SmallPtrSetIterator operator++(int)
Definition: SmallPtrSet.h:305
llvm::RoundUpToPowerOfTwoH::Val
@ Val
Definition: SmallPtrSet.h:321
Compiler.h
llvm::SmallPtrSet::operator=
SmallPtrSet< PtrType, SmallSize > & operator=(std::initializer_list< PtrType > IL)
Definition: SmallPtrSet.h:493
llvm::SmallPtrSet::SmallPtrSet
SmallPtrSet(const SmallPtrSet &that)
Definition: SmallPtrSet.h:464
llvm::SmallPtrSetImplBase::size
size_type size() const
Definition: SmallPtrSet.h:92
llvm::add_const_past_pointer::type
const T type
Definition: type_traits.h:55
llvm::SmallPtrSetIteratorImpl::End
const void *const * End
Definition: SmallPtrSet.h:224
llvm::SmallPtrSetImpl::SmallPtrSetImpl
SmallPtrSetImpl(const SmallPtrSetImpl &)=delete
std
Definition: BitVector.h:838
type_traits.h
llvm::SmallPtrSet::operator=
SmallPtrSet< PtrType, SmallSize > & operator=(SmallPtrSet< PtrType, SmallSize > &&RHS)
Definition: SmallPtrSet.h:486
llvm::DebugEpochBase
Definition: EpochTracker.h:81
LLVM_NODISCARD
#define LLVM_NODISCARD
LLVM_NODISCARD - Warn if a type or return value is discarded.
Definition: Compiler.h:161
llvm::DebugEpochBase::incrementEpoch
void incrementEpoch()
Definition: EpochTracker.h:83
llvm::SmallPtrSetImplBase::SmallArray
const void ** SmallArray
SmallArray - Points to a fixed size set of buckets, used in 'small mode'.
Definition: SmallPtrSet.h:54
llvm::SmallPtrSet::SmallPtrSet
SmallPtrSet(SmallPtrSet &&that)
Definition: SmallPtrSet.h:465
llvm::PointerLikeTypeTraits
A traits type that is used to handle pointer types and things that are just wrappers for pointers as ...
Definition: PointerLikeTypeTraits.h:25
llvm::SmallPtrSetImplBase::MoveFrom
void MoveFrom(unsigned SmallSize, SmallPtrSetImplBase &&RHS)
Definition: SmallPtrSet.cpp:182
llvm::RoundUpToPowerOfTwo::Val
@ Val
Definition: SmallPtrSet.h:334
llvm::SmallPtrSetIteratorImpl::RetreatIfNotValid
void RetreatIfNotValid()
Definition: SmallPtrSet.h:254
llvm::SmallPtrSetImplBase::empty
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:91
N
#define N
llvm::SmallPtrSetImpl::insert
void insert(IterT I, IterT E)
Definition: SmallPtrSet.h:393
llvm::SmallPtrSetIterator::iterator_category
std::forward_iterator_tag iterator_category
Definition: SmallPtrSet.h:275
llvm::SmallPtrSetImpl::insert
iterator insert(iterator, PtrType Ptr)
Insert the given pointer with an iterator hint that is ignored.
Definition: SmallPtrSet.h:372
llvm::DebugEpochBase::HandleBase
Definition: EpochTracker.h:85
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1161
EpochTracker.h
llvm::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
llvm::SmallPtrSetImplBase::find_imp
const void *const * find_imp(const void *Ptr) const
Returns the raw pointer needed to construct an iterator.
Definition: SmallPtrSet.h:176
llvm::SmallPtrSetImplBase::SmallPtrSetImplBase
SmallPtrSetImplBase(const void **SmallStorage, const SmallPtrSetImplBase &that)
Definition: SmallPtrSet.cpp:122
llvm::SmallPtrSetImpl::contains
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:388
llvm::RoundUpToPowerOfTwoH
RoundUpToPowerOfTwoH - If N is not a power of two, increase it.
Definition: SmallPtrSet.h:320
llvm::SmallPtrSetIteratorImpl::SmallPtrSetIteratorImpl
SmallPtrSetIteratorImpl(const void *const *BP, const void *const *E)
Definition: SmallPtrSet.h:227
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::SmallPtrSetImplBase::CopyFrom
void CopyFrom(const SmallPtrSetImplBase &RHS)
Definition: SmallPtrSet.cpp:145
llvm::SmallPtrSet::SmallPtrSet
SmallPtrSet(It I, It E)
Definition: SmallPtrSet.h:469
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:364