LLVM  14.0.0git
SmallPtrSet.cpp
Go to the documentation of this file.
1 //===- llvm/ADT/SmallPtrSet.cpp - 'Normally small' pointer set ------------===//
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 the SmallPtrSet class. See SmallPtrSet.h for an
10 // overview of the algorithm.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "llvm/ADT/SmallPtrSet.h"
15 #include "llvm/ADT/DenseMapInfo.h"
18 #include "llvm/Support/MemAlloc.h"
19 #include <algorithm>
20 #include <cassert>
21 #include <cstdlib>
22 
23 using namespace llvm;
24 
25 void SmallPtrSetImplBase::shrink_and_clear() {
26  assert(!isSmall() && "Can't shrink a small set!");
27  free(CurArray);
28 
29  // Reduce the number of buckets.
30  unsigned Size = size();
31  CurArraySize = Size > 16 ? 1 << (Log2_32_Ceil(Size) + 1) : 32;
33 
34  // Install the new array. Clear all the buckets to empty.
35  CurArray = (const void**)safe_malloc(sizeof(void*) * CurArraySize);
36 
37  memset(CurArray, -1, CurArraySize*sizeof(void*));
38 }
39 
40 std::pair<const void *const *, bool>
41 SmallPtrSetImplBase::insert_imp_big(const void *Ptr) {
42  if (LLVM_UNLIKELY(size() * 4 >= CurArraySize * 3)) {
43  // If more than 3/4 of the array is full, grow.
44  Grow(CurArraySize < 64 ? 128 : CurArraySize * 2);
45  } else if (LLVM_UNLIKELY(CurArraySize - NumNonEmpty < CurArraySize / 8)) {
46  // If fewer of 1/8 of the array is empty (meaning that many are filled with
47  // tombstones), rehash.
48  Grow(CurArraySize);
49  }
50 
51  // Okay, we know we have space. Find a hash bucket.
52  const void **Bucket = const_cast<const void**>(FindBucketFor(Ptr));
53  if (*Bucket == Ptr)
54  return std::make_pair(Bucket, false); // Already inserted, good.
55 
56  // Otherwise, insert it!
57  if (*Bucket == getTombstoneMarker())
58  --NumTombstones;
59  else
60  ++NumNonEmpty; // Track density.
61  *Bucket = Ptr;
63  return std::make_pair(Bucket, true);
64 }
65 
66 const void * const *SmallPtrSetImplBase::FindBucketFor(const void *Ptr) const {
67  unsigned Bucket = DenseMapInfo<void *>::getHashValue(Ptr) & (CurArraySize-1);
68  unsigned ArraySize = CurArraySize;
69  unsigned ProbeAmt = 1;
70  const void *const *Array = CurArray;
71  const void *const *Tombstone = nullptr;
72  while (true) {
73  // If we found an empty bucket, the pointer doesn't exist in the set.
74  // Return a tombstone if we've seen one so far, or the empty bucket if
75  // not.
76  if (LLVM_LIKELY(Array[Bucket] == getEmptyMarker()))
77  return Tombstone ? Tombstone : Array+Bucket;
78 
79  // Found Ptr's bucket?
80  if (LLVM_LIKELY(Array[Bucket] == Ptr))
81  return Array+Bucket;
82 
83  // If this is a tombstone, remember it. If Ptr ends up not in the set, we
84  // prefer to return it than something that would require more probing.
85  if (Array[Bucket] == getTombstoneMarker() && !Tombstone)
86  Tombstone = Array+Bucket; // Remember the first tombstone found.
87 
88  // It's a hash collision or a tombstone. Reprobe.
89  Bucket = (Bucket + ProbeAmt++) & (ArraySize-1);
90  }
91 }
92 
93 /// Grow - Allocate a larger backing store for the buckets and move it over.
94 ///
95 void SmallPtrSetImplBase::Grow(unsigned NewSize) {
96  const void **OldBuckets = CurArray;
97  const void **OldEnd = EndPointer();
98  bool WasSmall = isSmall();
99 
100  // Install the new array. Clear all the buckets to empty.
101  const void **NewBuckets = (const void**) safe_malloc(sizeof(void*) * NewSize);
102 
103  // Reset member only if memory was allocated successfully
104  CurArray = NewBuckets;
105  CurArraySize = NewSize;
106  memset(CurArray, -1, NewSize*sizeof(void*));
107 
108  // Copy over all valid entries.
109  for (const void **BucketPtr = OldBuckets; BucketPtr != OldEnd; ++BucketPtr) {
110  // Copy over the element if it is valid.
111  const void *Elt = *BucketPtr;
112  if (Elt != getTombstoneMarker() && Elt != getEmptyMarker())
113  *const_cast<void**>(FindBucketFor(Elt)) = const_cast<void*>(Elt);
114  }
115 
116  if (!WasSmall)
117  free(OldBuckets);
119  NumTombstones = 0;
120 }
121 
123  const SmallPtrSetImplBase &that) {
124  SmallArray = SmallStorage;
125 
126  // If we're becoming small, prepare to insert into our stack space
127  if (that.isSmall()) {
129  // Otherwise, allocate new heap space (unless we were the same size)
130  } else {
131  CurArray = (const void**)safe_malloc(sizeof(void*) * that.CurArraySize);
132  }
133 
134  // Copy over the that array.
135  CopyHelper(that);
136 }
137 
139  unsigned SmallSize,
141  SmallArray = SmallStorage;
142  MoveHelper(SmallSize, std::move(that));
143 }
144 
146  assert(&RHS != this && "Self-copy should be handled by the caller.");
147 
148  if (isSmall() && RHS.isSmall())
150  "Cannot assign sets with different small sizes");
151 
152  // If we're becoming small, prepare to insert into our stack space
153  if (RHS.isSmall()) {
154  if (!isSmall())
155  free(CurArray);
157  // Otherwise, allocate new heap space (unless we were the same size)
158  } else if (CurArraySize != RHS.CurArraySize) {
159  if (isSmall())
160  CurArray = (const void**)safe_malloc(sizeof(void*) * RHS.CurArraySize);
161  else {
162  const void **T = (const void**)safe_realloc(CurArray,
163  sizeof(void*) * RHS.CurArraySize);
164  CurArray = T;
165  }
166  }
167 
168  CopyHelper(RHS);
169 }
170 
171 void SmallPtrSetImplBase::CopyHelper(const SmallPtrSetImplBase &RHS) {
172  // Copy over the new array size
174 
175  // Copy over the contents from the other set
176  std::copy(RHS.CurArray, RHS.EndPointer(), CurArray);
177 
178  NumNonEmpty = RHS.NumNonEmpty;
180 }
181 
182 void SmallPtrSetImplBase::MoveFrom(unsigned SmallSize,
183  SmallPtrSetImplBase &&RHS) {
184  if (!isSmall())
185  free(CurArray);
186  MoveHelper(SmallSize, std::move(RHS));
187 }
188 
189 void SmallPtrSetImplBase::MoveHelper(unsigned SmallSize,
190  SmallPtrSetImplBase &&RHS) {
191  assert(&RHS != this && "Self-move should be handled by the caller.");
192 
193  if (RHS.isSmall()) {
194  // Copy a small RHS rather than moving.
196  std::copy(RHS.CurArray, RHS.CurArray + RHS.NumNonEmpty, CurArray);
197  } else {
198  CurArray = RHS.CurArray;
199  RHS.CurArray = RHS.SmallArray;
200  }
201 
202  // Copy the rest of the trivial members.
203  CurArraySize = RHS.CurArraySize;
204  NumNonEmpty = RHS.NumNonEmpty;
205  NumTombstones = RHS.NumTombstones;
206 
207  // Make the RHS small and empty.
208  RHS.CurArraySize = SmallSize;
209  assert(RHS.CurArray == RHS.SmallArray);
210  RHS.NumNonEmpty = 0;
211  RHS.NumTombstones = 0;
212 }
213 
215  if (this == &RHS) return;
216 
217  // We can only avoid copying elements if neither set is small.
218  if (!this->isSmall() && !RHS.isSmall()) {
219  std::swap(this->CurArray, RHS.CurArray);
220  std::swap(this->CurArraySize, RHS.CurArraySize);
221  std::swap(this->NumNonEmpty, RHS.NumNonEmpty);
223  return;
224  }
225 
226  // FIXME: From here on we assume that both sets have the same small size.
227 
228  // If only RHS is small, copy the small elements into LHS and move the pointer
229  // from LHS to RHS.
230  if (!this->isSmall() && RHS.isSmall()) {
231  assert(RHS.CurArray == RHS.SmallArray);
232  std::copy(RHS.CurArray, RHS.CurArray + RHS.NumNonEmpty, this->SmallArray);
233  std::swap(RHS.CurArraySize, this->CurArraySize);
234  std::swap(this->NumNonEmpty, RHS.NumNonEmpty);
236  RHS.CurArray = this->CurArray;
237  this->CurArray = this->SmallArray;
238  return;
239  }
240 
241  // If only LHS is small, copy the small elements into RHS and move the pointer
242  // from RHS to LHS.
243  if (this->isSmall() && !RHS.isSmall()) {
244  assert(this->CurArray == this->SmallArray);
245  std::copy(this->CurArray, this->CurArray + this->NumNonEmpty,
246  RHS.SmallArray);
247  std::swap(RHS.CurArraySize, this->CurArraySize);
248  std::swap(RHS.NumNonEmpty, this->NumNonEmpty);
249  std::swap(RHS.NumTombstones, this->NumTombstones);
250  this->CurArray = RHS.CurArray;
251  RHS.CurArray = RHS.SmallArray;
252  return;
253  }
254 
255  // Both a small, just swap the small elements.
256  assert(this->isSmall() && RHS.isSmall());
257  unsigned MinNonEmpty = std::min(this->NumNonEmpty, RHS.NumNonEmpty);
258  std::swap_ranges(this->SmallArray, this->SmallArray + MinNonEmpty,
259  RHS.SmallArray);
260  if (this->NumNonEmpty > MinNonEmpty) {
261  std::copy(this->SmallArray + MinNonEmpty,
262  this->SmallArray + this->NumNonEmpty,
263  RHS.SmallArray + MinNonEmpty);
264  } else {
265  std::copy(RHS.SmallArray + MinNonEmpty, RHS.SmallArray + RHS.NumNonEmpty,
266  this->SmallArray + MinNonEmpty);
267  }
268  assert(this->CurArraySize == RHS.CurArraySize);
269  std::swap(this->NumNonEmpty, RHS.NumNonEmpty);
271 }
llvm::Check::Size
@ Size
Definition: FileCheck.h:73
llvm::SmallPtrSetImplBase::swap
void swap(SmallPtrSetImplBase &RHS)
swap - Swaps the elements of two sets.
Definition: SmallPtrSet.cpp:214
MathExtras.h
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::SmallPtrSetImplBase::NumNonEmpty
unsigned NumNonEmpty
Number of elements in CurArray that contain a value or are a tombstone.
Definition: SmallPtrSet.h:64
llvm::SmallPtrSetImplBase
SmallPtrSetImplBase - This is the common code shared among all the SmallPtrSet<>'s,...
Definition: SmallPtrSet.h:49
ErrorHandling.h
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::msgpack::Type::Array
@ Array
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::SmallPtrSetImplBase::CurArraySize
unsigned CurArraySize
CurArraySize - The allocated size of CurArray, always a power of two.
Definition: SmallPtrSet.h:59
llvm::DenseMapInfo
Definition: APInt.h:34
SmallPtrSet.h
MemAlloc.h
llvm::Log2_32_Ceil
unsigned Log2_32_Ceil(uint32_t Value)
Return the ceil log base 2 of the specified value, 32 if the value is zero.
Definition: MathExtras.h:609
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
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
llvm::SmallPtrSetImplBase::CurArray
const void ** CurArray
CurArray - This is the current set of buckets.
Definition: SmallPtrSet.h:57
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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::SmallPtrSetImplBase::getEmptyMarker
static void * getEmptyMarker()
Definition: SmallPtrSet.h:112
llvm::min
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:357
this
Analysis the ScalarEvolution expression for r is this
Definition: README.txt:8
llvm::SmallPtrSetImplBase::size
size_type size() const
Definition: SmallPtrSet.h:92
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::safe_realloc
LLVM_ATTRIBUTE_RETURNS_NONNULL void * safe_realloc(void *Ptr, size_t Sz)
Definition: MemAlloc.h:52
llvm::SmallPtrSetImplBase::MoveFrom
void MoveFrom(unsigned SmallSize, SmallPtrSetImplBase &&RHS)
Definition: SmallPtrSet.cpp:182
LLVM_LIKELY
#define LLVM_LIKELY(EXPR)
Definition: Compiler.h:219
DenseMapInfo.h
llvm::SmallPtrSetImplBase::SmallPtrSetImplBase
SmallPtrSetImplBase(const void **SmallStorage, const SmallPtrSetImplBase &that)
Definition: SmallPtrSet.cpp:122
LLVM_UNLIKELY
#define LLVM_UNLIKELY(EXPR)
Definition: Compiler.h:220
copy
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 copy
Definition: README.txt:101
llvm::safe_malloc
LLVM_ATTRIBUTE_RETURNS_NONNULL void * safe_malloc(size_t Sz)
Definition: MemAlloc.h:25
llvm::SmallPtrSetImplBase::CopyFrom
void CopyFrom(const SmallPtrSetImplBase &RHS)
Definition: SmallPtrSet.cpp:145