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