LLVM API Documentation

 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
FoldingSet.cpp
Go to the documentation of this file.
1 //===-- Support/FoldingSet.cpp - Uniquing Hash Set --------------*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements a hash set that can be used to remove duplication of
11 // nodes in a graph.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "llvm/ADT/FoldingSet.h"
16 #include "llvm/ADT/Hashing.h"
17 #include "llvm/Support/Allocator.h"
19 #include "llvm/Support/Host.h"
21 #include <cassert>
22 #include <cstring>
23 using namespace llvm;
24 
25 //===----------------------------------------------------------------------===//
26 // FoldingSetNodeIDRef Implementation
27 
28 /// ComputeHash - Compute a strong hash value for this FoldingSetNodeIDRef,
29 /// used to lookup the node in the FoldingSetImpl.
31  return static_cast<unsigned>(hash_combine_range(Data, Data+Size));
32 }
33 
35  if (Size != RHS.Size) return false;
36  return memcmp(Data, RHS.Data, Size*sizeof(*Data)) == 0;
37 }
38 
39 /// Used to compare the "ordering" of two nodes as defined by the
40 /// profiled bits and their ordering defined by memcmp().
42  if (Size != RHS.Size)
43  return Size < RHS.Size;
44  return memcmp(Data, RHS.Data, Size*sizeof(*Data)) < 0;
45 }
46 
47 //===----------------------------------------------------------------------===//
48 // FoldingSetNodeID Implementation
49 
50 /// Add* - Add various data types to Bit data.
51 ///
52 void FoldingSetNodeID::AddPointer(const void *Ptr) {
53  // Note: this adds pointers to the hash using sizes and endianness that
54  // depend on the host. It doesn't matter however, because hashing on
55  // pointer values in inherently unstable. Nothing should depend on the
56  // ordering of nodes in the folding set.
57  Bits.append(reinterpret_cast<unsigned *>(&Ptr),
58  reinterpret_cast<unsigned *>(&Ptr+1));
59 }
61  Bits.push_back(I);
62 }
64  Bits.push_back(I);
65 }
67  AddInteger((unsigned long)I);
68 }
69 void FoldingSetNodeID::AddInteger(unsigned long I) {
70  if (sizeof(long) == sizeof(int))
71  AddInteger(unsigned(I));
72  else if (sizeof(long) == sizeof(long long)) {
73  AddInteger((unsigned long long)I);
74  } else {
75  llvm_unreachable("unexpected sizeof(long)");
76  }
77 }
79  AddInteger((unsigned long long)I);
80 }
81 void FoldingSetNodeID::AddInteger(unsigned long long I) {
82  AddInteger(unsigned(I));
83  if ((uint64_t)(unsigned)I != I)
84  Bits.push_back(unsigned(I >> 32));
85 }
86 
88  unsigned Size = String.size();
89  Bits.push_back(Size);
90  if (!Size) return;
91 
92  unsigned Units = Size / 4;
93  unsigned Pos = 0;
94  const unsigned *Base = (const unsigned*) String.data();
95 
96  // If the string is aligned do a bulk transfer.
97  if (!((intptr_t)Base & 3)) {
98  Bits.append(Base, Base + Units);
99  Pos = (Units + 1) * 4;
100  } else {
101  // Otherwise do it the hard way.
102  // To be compatible with above bulk transfer, we need to take endianness
103  // into account.
104  if (sys::IsBigEndianHost) {
105  for (Pos += 4; Pos <= Size; Pos += 4) {
106  unsigned V = ((unsigned char)String[Pos - 4] << 24) |
107  ((unsigned char)String[Pos - 3] << 16) |
108  ((unsigned char)String[Pos - 2] << 8) |
109  (unsigned char)String[Pos - 1];
110  Bits.push_back(V);
111  }
112  } else {
113  assert(sys::IsLittleEndianHost && "Unexpected host endianness");
114  for (Pos += 4; Pos <= Size; Pos += 4) {
115  unsigned V = ((unsigned char)String[Pos - 1] << 24) |
116  ((unsigned char)String[Pos - 2] << 16) |
117  ((unsigned char)String[Pos - 3] << 8) |
118  (unsigned char)String[Pos - 4];
119  Bits.push_back(V);
120  }
121  }
122  }
123 
124  // With the leftover bits.
125  unsigned V = 0;
126  // Pos will have overshot size by 4 - #bytes left over.
127  // No need to take endianness into account here - this is always executed.
128  switch (Pos - Size) {
129  case 1: V = (V << 8) | (unsigned char)String[Size - 3]; // Fall thru.
130  case 2: V = (V << 8) | (unsigned char)String[Size - 2]; // Fall thru.
131  case 3: V = (V << 8) | (unsigned char)String[Size - 1]; break;
132  default: return; // Nothing left.
133  }
134 
135  Bits.push_back(V);
136 }
137 
138 // AddNodeID - Adds the Bit data of another ID to *this.
140  Bits.append(ID.Bits.begin(), ID.Bits.end());
141 }
142 
143 /// ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used to
144 /// lookup the node in the FoldingSetImpl.
146  return FoldingSetNodeIDRef(Bits.data(), Bits.size()).ComputeHash();
147 }
148 
149 /// operator== - Used to compare two nodes to each other.
150 ///
152  return *this == FoldingSetNodeIDRef(RHS.Bits.data(), RHS.Bits.size());
153 }
154 
155 /// operator== - Used to compare two nodes to each other.
156 ///
158  return FoldingSetNodeIDRef(Bits.data(), Bits.size()) == RHS;
159 }
160 
161 /// Used to compare the "ordering" of two nodes as defined by the
162 /// profiled bits and their ordering defined by memcmp().
164  return *this < FoldingSetNodeIDRef(RHS.Bits.data(), RHS.Bits.size());
165 }
166 
168  return FoldingSetNodeIDRef(Bits.data(), Bits.size()) < RHS;
169 }
170 
171 /// Intern - Copy this node's data to a memory region allocated from the
172 /// given allocator and return a FoldingSetNodeIDRef describing the
173 /// interned data.
176  unsigned *New = Allocator.Allocate<unsigned>(Bits.size());
177  std::uninitialized_copy(Bits.begin(), Bits.end(), New);
178  return FoldingSetNodeIDRef(New, Bits.size());
179 }
180 
181 //===----------------------------------------------------------------------===//
182 /// Helper functions for FoldingSetImpl.
183 
184 /// GetNextPtr - In order to save space, each bucket is a
185 /// singly-linked-list. In order to make deletion more efficient, we make
186 /// the list circular, so we can delete a node without computing its hash.
187 /// The problem with this is that the start of the hash buckets are not
188 /// Nodes. If NextInBucketPtr is a bucket pointer, this method returns null:
189 /// use GetBucketPtr when this happens.
190 static FoldingSetImpl::Node *GetNextPtr(void *NextInBucketPtr) {
191  // The low bit is set if this is the pointer back to the bucket.
192  if (reinterpret_cast<intptr_t>(NextInBucketPtr) & 1)
193  return 0;
194 
195  return static_cast<FoldingSetImpl::Node*>(NextInBucketPtr);
196 }
197 
198 
199 /// testing.
200 static void **GetBucketPtr(void *NextInBucketPtr) {
201  intptr_t Ptr = reinterpret_cast<intptr_t>(NextInBucketPtr);
202  assert((Ptr & 1) && "Not a bucket pointer");
203  return reinterpret_cast<void**>(Ptr & ~intptr_t(1));
204 }
205 
206 /// GetBucketFor - Hash the specified node ID and return the hash bucket for
207 /// the specified ID.
208 static void **GetBucketFor(unsigned Hash, void **Buckets, unsigned NumBuckets) {
209  // NumBuckets is always a power of 2.
210  unsigned BucketNum = Hash & (NumBuckets-1);
211  return Buckets + BucketNum;
212 }
213 
214 /// AllocateBuckets - Allocated initialized bucket memory.
215 static void **AllocateBuckets(unsigned NumBuckets) {
216  void **Buckets = static_cast<void**>(calloc(NumBuckets+1, sizeof(void*)));
217  // Set the very last bucket to be a non-null "pointer".
218  Buckets[NumBuckets] = reinterpret_cast<void*>(-1);
219  return Buckets;
220 }
221 
222 //===----------------------------------------------------------------------===//
223 // FoldingSetImpl Implementation
224 
225 FoldingSetImpl::FoldingSetImpl(unsigned Log2InitSize) {
226  assert(5 < Log2InitSize && Log2InitSize < 32 &&
227  "Initial hash table size out of range");
228  NumBuckets = 1 << Log2InitSize;
230  NumNodes = 0;
231 }
233  free(Buckets);
234 }
236  // Set all but the last bucket to null pointers.
237  memset(Buckets, 0, NumBuckets*sizeof(void*));
238 
239  // Set the very last bucket to be a non-null "pointer".
240  Buckets[NumBuckets] = reinterpret_cast<void*>(-1);
241 
242  // Reset the node count to zero.
243  NumNodes = 0;
244 }
245 
246 /// GrowHashTable - Double the size of the hash table and rehash everything.
247 ///
248 void FoldingSetImpl::GrowHashTable() {
249  void **OldBuckets = Buckets;
250  unsigned OldNumBuckets = NumBuckets;
251  NumBuckets <<= 1;
252 
253  // Clear out new buckets.
255  NumNodes = 0;
256 
257  // Walk the old buckets, rehashing nodes into their new place.
258  FoldingSetNodeID TempID;
259  for (unsigned i = 0; i != OldNumBuckets; ++i) {
260  void *Probe = OldBuckets[i];
261  if (!Probe) continue;
262  while (Node *NodeInBucket = GetNextPtr(Probe)) {
263  // Figure out the next link, remove NodeInBucket from the old link.
264  Probe = NodeInBucket->getNextInBucket();
265  NodeInBucket->SetNextInBucket(0);
266 
267  // Insert the node into the new bucket, after recomputing the hash.
268  InsertNode(NodeInBucket,
269  GetBucketFor(ComputeNodeHash(NodeInBucket, TempID),
270  Buckets, NumBuckets));
271  TempID.clear();
272  }
273  }
274 
275  free(OldBuckets);
276 }
277 
278 /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists,
279 /// return it. If not, return the insertion token that will make insertion
280 /// faster.
283  void *&InsertPos) {
284  unsigned IDHash = ID.ComputeHash();
285  void **Bucket = GetBucketFor(IDHash, Buckets, NumBuckets);
286  void *Probe = *Bucket;
287 
288  InsertPos = 0;
289 
290  FoldingSetNodeID TempID;
291  while (Node *NodeInBucket = GetNextPtr(Probe)) {
292  if (NodeEquals(NodeInBucket, ID, IDHash, TempID))
293  return NodeInBucket;
294  TempID.clear();
295 
296  Probe = NodeInBucket->getNextInBucket();
297  }
298 
299  // Didn't find the node, return null with the bucket as the InsertPos.
300  InsertPos = Bucket;
301  return 0;
302 }
303 
304 /// InsertNode - Insert the specified node into the folding set, knowing that it
305 /// is not already in the map. InsertPos must be obtained from
306 /// FindNodeOrInsertPos.
307 void FoldingSetImpl::InsertNode(Node *N, void *InsertPos) {
308  assert(N->getNextInBucket() == 0);
309  // Do we need to grow the hashtable?
310  if (NumNodes+1 > NumBuckets*2) {
311  GrowHashTable();
312  FoldingSetNodeID TempID;
313  InsertPos = GetBucketFor(ComputeNodeHash(N, TempID), Buckets, NumBuckets);
314  }
315 
316  ++NumNodes;
317 
318  /// The insert position is actually a bucket pointer.
319  void **Bucket = static_cast<void**>(InsertPos);
320 
321  void *Next = *Bucket;
322 
323  // If this is the first insertion into this bucket, its next pointer will be
324  // null. Pretend as if it pointed to itself, setting the low bit to indicate
325  // that it is a pointer to the bucket.
326  if (Next == 0)
327  Next = reinterpret_cast<void*>(reinterpret_cast<intptr_t>(Bucket)|1);
328 
329  // Set the node's next pointer, and make the bucket point to the node.
330  N->SetNextInBucket(Next);
331  *Bucket = N;
332 }
333 
334 /// RemoveNode - Remove a node from the folding set, returning true if one was
335 /// removed or false if the node was not in the folding set.
337  // Because each bucket is a circular list, we don't need to compute N's hash
338  // to remove it.
339  void *Ptr = N->getNextInBucket();
340  if (Ptr == 0) return false; // Not in folding set.
341 
342  --NumNodes;
343  N->SetNextInBucket(0);
344 
345  // Remember what N originally pointed to, either a bucket or another node.
346  void *NodeNextPtr = Ptr;
347 
348  // Chase around the list until we find the node (or bucket) which points to N.
349  while (true) {
350  if (Node *NodeInBucket = GetNextPtr(Ptr)) {
351  // Advance pointer.
352  Ptr = NodeInBucket->getNextInBucket();
353 
354  // We found a node that points to N, change it to point to N's next node,
355  // removing N from the list.
356  if (Ptr == N) {
357  NodeInBucket->SetNextInBucket(NodeNextPtr);
358  return true;
359  }
360  } else {
361  void **Bucket = GetBucketPtr(Ptr);
362  Ptr = *Bucket;
363 
364  // If we found that the bucket points to N, update the bucket to point to
365  // whatever is next.
366  if (Ptr == N) {
367  *Bucket = NodeNextPtr;
368  return true;
369  }
370  }
371  }
372 }
373 
374 /// GetOrInsertNode - If there is an existing simple Node exactly
375 /// equal to the specified node, return it. Otherwise, insert 'N' and it
376 /// instead.
379  GetNodeProfile(N, ID);
380  void *IP;
381  if (Node *E = FindNodeOrInsertPos(ID, IP))
382  return E;
383  InsertNode(N, IP);
384  return N;
385 }
386 
387 //===----------------------------------------------------------------------===//
388 // FoldingSetIteratorImpl Implementation
389 
391  // Skip to the first non-null non-self-cycle bucket.
392  while (*Bucket != reinterpret_cast<void*>(-1) &&
393  (*Bucket == 0 || GetNextPtr(*Bucket) == 0))
394  ++Bucket;
395 
396  NodePtr = static_cast<FoldingSetNode*>(*Bucket);
397 }
398 
400  // If there is another link within this bucket, go to it.
401  void *Probe = NodePtr->getNextInBucket();
402 
403  if (FoldingSetNode *NextNodeInBucket = GetNextPtr(Probe))
404  NodePtr = NextNodeInBucket;
405  else {
406  // Otherwise, this is the last link in this bucket.
407  void **Bucket = GetBucketPtr(Probe);
408 
409  // Skip to the next non-null non-self-cycle bucket.
410  do {
411  ++Bucket;
412  } while (*Bucket != reinterpret_cast<void*>(-1) &&
413  (*Bucket == 0 || GetNextPtr(*Bucket) == 0));
414 
415  NodePtr = static_cast<FoldingSetNode*>(*Bucket);
416  }
417 }
418 
419 //===----------------------------------------------------------------------===//
420 // FoldingSetBucketIteratorImpl Implementation
421 
423  Ptr = (*Bucket == 0 || GetNextPtr(*Bucket) == 0) ? (void*) Bucket : *Bucket;
424 }
Node * GetOrInsertNode(Node *N)
Definition: FoldingSet.cpp:377
void AddPointer(const void *Ptr)
Definition: FoldingSet.cpp:52
void push_back(const T &Elt)
Definition: SmallVector.h:236
static void ** AllocateBuckets(unsigned NumBuckets)
AllocateBuckets - Allocated initialized bucket memory.
Definition: FoldingSet.cpp:215
size_t size() const
size - Get the string size.
Definition: StringRef.h:113
void InsertNode(Node *N, void *InsertPos)
Definition: FoldingSet.cpp:307
static void ** GetBucketPtr(void *NextInBucketPtr)
testing.
Definition: FoldingSet.cpp:200
unsigned ComputeHash() const
Definition: FoldingSet.cpp:30
#define llvm_unreachable(msg)
virtual void GetNodeProfile(Node *N, FoldingSetNodeID &ID) const =0
void AddInteger(signed I)
Definition: FoldingSet.cpp:60
ID
LLVM Calling Convention Representation.
Definition: CallingConv.h:26
static const bool IsLittleEndianHost
Definition: Host.h:38
const char * data() const
Definition: StringRef.h:107
bool operator==(const FoldingSetNodeID &RHS) const
Definition: FoldingSet.cpp:151
int memcmp(const void *s1, const void *s2, size_t n);
virtual unsigned ComputeNodeHash(Node *N, FoldingSetNodeID &TempID) const =0
void AddNodeID(const FoldingSetNodeID &ID)
Definition: FoldingSet.cpp:139
void * getNextInBucket() const
Definition: FoldingSet.h:143
FoldingSetNode * NodePtr
Definition: FoldingSet.h:640
bool operator<(FoldingSetNodeIDRef) const
Definition: FoldingSet.cpp:41
void free(void *ptr);
static FoldingSetImpl::Node * GetNextPtr(void *NextInBucketPtr)
Helper functions for FoldingSetImpl.
Definition: FoldingSet.cpp:190
Node * FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos)
Definition: FoldingSet.cpp:282
static void ** GetBucketFor(unsigned Hash, void **Buckets, unsigned NumBuckets)
Definition: FoldingSet.cpp:208
FoldingSetImpl(unsigned Log2InitSize=6)
Definition: FoldingSet.cpp:225
void append(in_iter in_start, in_iter in_end)
Definition: SmallVector.h:445
bool RemoveNode(Node *N)
Definition: FoldingSet.cpp:336
bool operator<(const FoldingSetNodeID &RHS) const
Definition: FoldingSet.cpp:163
void SetNextInBucket(void *N)
Definition: FoldingSet.h:144
virtual ~FoldingSetImpl()
Definition: FoldingSet.cpp:232
void * Allocate(size_t Size, size_t Alignment)
Definition: Allocator.cpp:95
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
Definition: Hashing.h:487
pointer data()
data - Return a pointer to the vector's buffer, even if empty().
Definition: SmallVector.h:135
FoldingSetIteratorImpl(void **Bucket)
Definition: FoldingSet.cpp:390
unsigned ComputeHash() const
Definition: FoldingSet.cpp:145
static const bool IsBigEndianHost
Definition: Host.h:35
#define I(x, y, z)
Definition: MD5.cpp:54
#define N
void AddString(StringRef String)
Definition: FoldingSet.cpp:87
FoldingSetBucketIteratorImpl(void **Bucket)
Definition: FoldingSet.cpp:422
FoldingSetNodeIDRef Intern(BumpPtrAllocator &Allocator) const
Definition: FoldingSet.cpp:175
virtual bool NodeEquals(Node *N, const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID) const =0
void clear()
clear - Remove all nodes from the folding set.
Definition: FoldingSet.cpp:235
void *calloc(size_t count, size_t size);
bool operator==(FoldingSetNodeIDRef) const
Definition: FoldingSet.cpp:34