LLVM API Documentation
00001 //===-- Support/FoldingSet.cpp - Uniquing Hash Set --------------*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements a hash set that can be used to remove duplication of 00011 // nodes in a graph. This code was originally created by Chris Lattner for use 00012 // with SelectionDAGCSEMap, but was isolated to provide use across the llvm code 00013 // set. 00014 // 00015 //===----------------------------------------------------------------------===// 00016 00017 #include "llvm/ADT/FoldingSet.h" 00018 #include "llvm/Support/ErrorHandling.h" 00019 #include "llvm/Support/MathExtras.h" 00020 #include <cassert> 00021 #include <cstring> 00022 using namespace llvm; 00023 00024 //===----------------------------------------------------------------------===// 00025 // FoldingSetNodeID Implementation 00026 00027 /// Add* - Add various data types to Bit data. 00028 /// 00029 void FoldingSetNodeID::AddPointer(const void *Ptr) { 00030 // Note: this adds pointers to the hash using sizes and endianness that 00031 // depend on the host. It doesn't matter however, because hashing on 00032 // pointer values in inherently unstable. Nothing should depend on the 00033 // ordering of nodes in the folding set. 00034 intptr_t PtrI = (intptr_t)Ptr; 00035 Bits.push_back(unsigned(PtrI)); 00036 if (sizeof(intptr_t) > sizeof(unsigned)) 00037 Bits.push_back(unsigned(uint64_t(PtrI) >> 32)); 00038 } 00039 void FoldingSetNodeID::AddInteger(signed I) { 00040 Bits.push_back(I); 00041 } 00042 void FoldingSetNodeID::AddInteger(unsigned I) { 00043 Bits.push_back(I); 00044 } 00045 void FoldingSetNodeID::AddInteger(long I) { 00046 AddInteger((unsigned long)I); 00047 } 00048 void FoldingSetNodeID::AddInteger(unsigned long I) { 00049 if (sizeof(long) == sizeof(int)) 00050 AddInteger(unsigned(I)); 00051 else if (sizeof(long) == sizeof(long long)) { 00052 AddInteger((unsigned long long)I); 00053 } else { 00054 llvm_unreachable("unexpected sizeof(long)"); 00055 } 00056 } 00057 void FoldingSetNodeID::AddInteger(long long I) { 00058 AddInteger((unsigned long long)I); 00059 } 00060 void FoldingSetNodeID::AddInteger(unsigned long long I) { 00061 AddInteger(unsigned(I)); 00062 if ((uint64_t)(int)I != I) 00063 Bits.push_back(unsigned(I >> 32)); 00064 } 00065 00066 void FoldingSetNodeID::AddString(const char *String, const char *End) { 00067 unsigned Size = static_cast<unsigned>(End - String); 00068 Bits.push_back(Size); 00069 if (!Size) return; 00070 00071 unsigned Units = Size / 4; 00072 unsigned Pos = 0; 00073 const unsigned *Base = (const unsigned *)String; 00074 00075 // If the string is aligned do a bulk transfer. 00076 if (!((intptr_t)Base & 3)) { 00077 Bits.append(Base, Base + Units); 00078 Pos = (Units + 1) * 4; 00079 } else { 00080 // Otherwise do it the hard way. 00081 for (Pos += 4; Pos <= Size; Pos += 4) { 00082 unsigned V = ((unsigned char)String[Pos - 4] << 24) | 00083 ((unsigned char)String[Pos - 3] << 16) | 00084 ((unsigned char)String[Pos - 2] << 8) | 00085 (unsigned char)String[Pos - 1]; 00086 Bits.push_back(V); 00087 } 00088 } 00089 00090 // With the leftover bits. 00091 unsigned V = 0; 00092 // Pos will have overshot size by 4 - #bytes left over. 00093 switch (Pos - Size) { 00094 case 1: V = (V << 8) | (unsigned char)String[Size - 3]; // Fall thru. 00095 case 2: V = (V << 8) | (unsigned char)String[Size - 2]; // Fall thru. 00096 case 3: V = (V << 8) | (unsigned char)String[Size - 1]; break; 00097 default: return; // Nothing left. 00098 } 00099 00100 Bits.push_back(V); 00101 } 00102 00103 void FoldingSetNodeID::AddString(const char *String) { 00104 AddString(String, String + strlen(String)); 00105 } 00106 00107 void FoldingSetNodeID::AddString(const std::string &String) { 00108 AddString(&*String.begin(), &*String.end()); 00109 } 00110 00111 /// ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used to 00112 /// lookup the node in the FoldingSetImpl. 00113 unsigned FoldingSetNodeID::ComputeHash() const { 00114 // This is adapted from SuperFastHash by Paul Hsieh. 00115 unsigned Hash = static_cast<unsigned>(Bits.size()); 00116 for (const unsigned *BP = &Bits[0], *E = BP+Bits.size(); BP != E; ++BP) { 00117 unsigned Data = *BP; 00118 Hash += Data & 0xFFFF; 00119 unsigned Tmp = ((Data >> 16) << 11) ^ Hash; 00120 Hash = (Hash << 16) ^ Tmp; 00121 Hash += Hash >> 11; 00122 } 00123 00124 // Force "avalanching" of final 127 bits. 00125 Hash ^= Hash << 3; 00126 Hash += Hash >> 5; 00127 Hash ^= Hash << 4; 00128 Hash += Hash >> 17; 00129 Hash ^= Hash << 25; 00130 Hash += Hash >> 6; 00131 return Hash; 00132 } 00133 00134 /// operator== - Used to compare two nodes to each other. 00135 /// 00136 bool FoldingSetNodeID::operator==(const FoldingSetNodeID &RHS)const{ 00137 if (Bits.size() != RHS.Bits.size()) return false; 00138 return memcmp(&Bits[0], &RHS.Bits[0], Bits.size()*sizeof(Bits[0])) == 0; 00139 } 00140 00141 00142 //===----------------------------------------------------------------------===// 00143 /// Helper functions for FoldingSetImpl. 00144 00145 /// GetNextPtr - In order to save space, each bucket is a 00146 /// singly-linked-list. In order to make deletion more efficient, we make 00147 /// the list circular, so we can delete a node without computing its hash. 00148 /// The problem with this is that the start of the hash buckets are not 00149 /// Nodes. If NextInBucketPtr is a bucket pointer, this method returns null: 00150 /// use GetBucketPtr when this happens. 00151 static FoldingSetImpl::Node *GetNextPtr(void *NextInBucketPtr) { 00152 // The low bit is set if this is the pointer back to the bucket. 00153 if (reinterpret_cast<intptr_t>(NextInBucketPtr) & 1) 00154 return 0; 00155 00156 return static_cast<FoldingSetImpl::Node*>(NextInBucketPtr); 00157 } 00158 00159 00160 /// testing. 00161 static void **GetBucketPtr(void *NextInBucketPtr) { 00162 intptr_t Ptr = reinterpret_cast<intptr_t>(NextInBucketPtr); 00163 assert((Ptr & 1) && "Not a bucket pointer"); 00164 return reinterpret_cast<void**>(Ptr & ~intptr_t(1)); 00165 } 00166 00167 /// GetBucketFor - Hash the specified node ID and return the hash bucket for 00168 /// the specified ID. 00169 static void **GetBucketFor(const FoldingSetNodeID &ID, 00170 void **Buckets, unsigned NumBuckets) { 00171 // NumBuckets is always a power of 2. 00172 unsigned BucketNum = ID.ComputeHash() & (NumBuckets-1); 00173 return Buckets + BucketNum; 00174 } 00175 00176 //===----------------------------------------------------------------------===// 00177 // FoldingSetImpl Implementation 00178 00179 FoldingSetImpl::FoldingSetImpl(unsigned Log2InitSize) { 00180 assert(5 < Log2InitSize && Log2InitSize < 32 && 00181 "Initial hash table size out of range"); 00182 NumBuckets = 1 << Log2InitSize; 00183 Buckets = new void*[NumBuckets+1]; 00184 clear(); 00185 } 00186 FoldingSetImpl::~FoldingSetImpl() { 00187 delete [] Buckets; 00188 } 00189 void FoldingSetImpl::clear() { 00190 // Set all but the last bucket to null pointers. 00191 memset(Buckets, 0, NumBuckets*sizeof(void*)); 00192 00193 // Set the very last bucket to be a non-null "pointer". 00194 Buckets[NumBuckets] = reinterpret_cast<void*>(-1); 00195 00196 // Reset the node count to zero. 00197 NumNodes = 0; 00198 } 00199 00200 /// GrowHashTable - Double the size of the hash table and rehash everything. 00201 /// 00202 void FoldingSetImpl::GrowHashTable() { 00203 void **OldBuckets = Buckets; 00204 unsigned OldNumBuckets = NumBuckets; 00205 NumBuckets <<= 1; 00206 00207 // Clear out new buckets. 00208 Buckets = new void*[NumBuckets+1]; 00209 clear(); 00210 00211 // Walk the old buckets, rehashing nodes into their new place. 00212 FoldingSetNodeID ID; 00213 for (unsigned i = 0; i != OldNumBuckets; ++i) { 00214 void *Probe = OldBuckets[i]; 00215 if (!Probe) continue; 00216 while (Node *NodeInBucket = GetNextPtr(Probe)) { 00217 // Figure out the next link, remove NodeInBucket from the old link. 00218 Probe = NodeInBucket->getNextInBucket(); 00219 NodeInBucket->SetNextInBucket(0); 00220 00221 // Insert the node into the new bucket, after recomputing the hash. 00222 GetNodeProfile(ID, NodeInBucket); 00223 InsertNode(NodeInBucket, GetBucketFor(ID, Buckets, NumBuckets)); 00224 ID.clear(); 00225 } 00226 } 00227 00228 delete[] OldBuckets; 00229 } 00230 00231 /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists, 00232 /// return it. If not, return the insertion token that will make insertion 00233 /// faster. 00234 FoldingSetImpl::Node 00235 *FoldingSetImpl::FindNodeOrInsertPos(const FoldingSetNodeID &ID, 00236 void *&InsertPos) { 00237 00238 void **Bucket = GetBucketFor(ID, Buckets, NumBuckets); 00239 void *Probe = *Bucket; 00240 00241 InsertPos = 0; 00242 00243 FoldingSetNodeID OtherID; 00244 while (Node *NodeInBucket = GetNextPtr(Probe)) { 00245 GetNodeProfile(OtherID, NodeInBucket); 00246 if (OtherID == ID) 00247 return NodeInBucket; 00248 00249 Probe = NodeInBucket->getNextInBucket(); 00250 OtherID.clear(); 00251 } 00252 00253 // Didn't find the node, return null with the bucket as the InsertPos. 00254 InsertPos = Bucket; 00255 return 0; 00256 } 00257 00258 /// InsertNode - Insert the specified node into the folding set, knowing that it 00259 /// is not already in the map. InsertPos must be obtained from 00260 /// FindNodeOrInsertPos. 00261 void FoldingSetImpl::InsertNode(Node *N, void *InsertPos) { 00262 assert(N->getNextInBucket() == 0); 00263 // Do we need to grow the hashtable? 00264 if (NumNodes+1 > NumBuckets*2) { 00265 GrowHashTable(); 00266 FoldingSetNodeID ID; 00267 GetNodeProfile(ID, N); 00268 InsertPos = GetBucketFor(ID, Buckets, NumBuckets); 00269 } 00270 00271 ++NumNodes; 00272 00273 /// The insert position is actually a bucket pointer. 00274 void **Bucket = static_cast<void**>(InsertPos); 00275 00276 void *Next = *Bucket; 00277 00278 // If this is the first insertion into this bucket, its next pointer will be 00279 // null. Pretend as if it pointed to itself, setting the low bit to indicate 00280 // that it is a pointer to the bucket. 00281 if (Next == 0) 00282 Next = reinterpret_cast<void*>(reinterpret_cast<intptr_t>(Bucket)|1); 00283 00284 // Set the node's next pointer, and make the bucket point to the node. 00285 N->SetNextInBucket(Next); 00286 *Bucket = N; 00287 } 00288 00289 /// RemoveNode - Remove a node from the folding set, returning true if one was 00290 /// removed or false if the node was not in the folding set. 00291 bool FoldingSetImpl::RemoveNode(Node *N) { 00292 // Because each bucket is a circular list, we don't need to compute N's hash 00293 // to remove it. 00294 void *Ptr = N->getNextInBucket(); 00295 if (Ptr == 0) return false; // Not in folding set. 00296 00297 --NumNodes; 00298 N->SetNextInBucket(0); 00299 00300 // Remember what N originally pointed to, either a bucket or another node. 00301 void *NodeNextPtr = Ptr; 00302 00303 // Chase around the list until we find the node (or bucket) which points to N. 00304 while (true) { 00305 if (Node *NodeInBucket = GetNextPtr(Ptr)) { 00306 // Advance pointer. 00307 Ptr = NodeInBucket->getNextInBucket(); 00308 00309 // We found a node that points to N, change it to point to N's next node, 00310 // removing N from the list. 00311 if (Ptr == N) { 00312 NodeInBucket->SetNextInBucket(NodeNextPtr); 00313 return true; 00314 } 00315 } else { 00316 void **Bucket = GetBucketPtr(Ptr); 00317 Ptr = *Bucket; 00318 00319 // If we found that the bucket points to N, update the bucket to point to 00320 // whatever is next. 00321 if (Ptr == N) { 00322 *Bucket = NodeNextPtr; 00323 return true; 00324 } 00325 } 00326 } 00327 } 00328 00329 /// GetOrInsertNode - If there is an existing simple Node exactly 00330 /// equal to the specified node, return it. Otherwise, insert 'N' and it 00331 /// instead. 00332 FoldingSetImpl::Node *FoldingSetImpl::GetOrInsertNode(FoldingSetImpl::Node *N) { 00333 FoldingSetNodeID ID; 00334 GetNodeProfile(ID, N); 00335 void *IP; 00336 if (Node *E = FindNodeOrInsertPos(ID, IP)) 00337 return E; 00338 InsertNode(N, IP); 00339 return N; 00340 } 00341 00342 //===----------------------------------------------------------------------===// 00343 // FoldingSetIteratorImpl Implementation 00344 00345 FoldingSetIteratorImpl::FoldingSetIteratorImpl(void **Bucket) { 00346 // Skip to the first non-null non-self-cycle bucket. 00347 while (*Bucket != reinterpret_cast<void*>(-1) && 00348 (*Bucket == 0 || GetNextPtr(*Bucket) == 0)) 00349 ++Bucket; 00350 00351 NodePtr = static_cast<FoldingSetNode*>(*Bucket); 00352 } 00353 00354 void FoldingSetIteratorImpl::advance() { 00355 // If there is another link within this bucket, go to it. 00356 void *Probe = NodePtr->getNextInBucket(); 00357 00358 if (FoldingSetNode *NextNodeInBucket = GetNextPtr(Probe)) 00359 NodePtr = NextNodeInBucket; 00360 else { 00361 // Otherwise, this is the last link in this bucket. 00362 void **Bucket = GetBucketPtr(Probe); 00363 00364 // Skip to the next non-null non-self-cycle bucket. 00365 do { 00366 ++Bucket; 00367 } while (*Bucket != reinterpret_cast<void*>(-1) && 00368 (*Bucket == 0 || GetNextPtr(*Bucket) == 0)); 00369 00370 NodePtr = static_cast<FoldingSetNode*>(*Bucket); 00371 } 00372 } 00373 00374 //===----------------------------------------------------------------------===// 00375 // FoldingSetBucketIteratorImpl Implementation 00376 00377 FoldingSetBucketIteratorImpl::FoldingSetBucketIteratorImpl(void **Bucket) { 00378 Ptr = (*Bucket == 0 || GetNextPtr(*Bucket) == 0) ? (void*) Bucket : *Bucket; 00379 }