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