LLVM API Documentation
00001 //===-- llvm/ADT/FoldingSet.h - 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 defines a hash set that can be used to remove duplication of nodes 00011 // in a graph. This code was originally created by Chris Lattner for use with 00012 // SelectionDAGCSEMap, but was isolated to provide use across the llvm code set. 00013 // 00014 //===----------------------------------------------------------------------===// 00015 00016 #ifndef LLVM_ADT_FOLDINGSET_H 00017 #define LLVM_ADT_FOLDINGSET_H 00018 00019 #include "llvm/Support/DataTypes.h" 00020 #include "llvm/ADT/SmallVector.h" 00021 #include <string> 00022 #include <iterator> 00023 00024 namespace llvm { 00025 class APFloat; 00026 class APInt; 00027 00028 /// This folding set used for two purposes: 00029 /// 1. Given information about a node we want to create, look up the unique 00030 /// instance of the node in the set. If the node already exists, return 00031 /// it, otherwise return the bucket it should be inserted into. 00032 /// 2. Given a node that has already been created, remove it from the set. 00033 /// 00034 /// This class is implemented as a single-link chained hash table, where the 00035 /// "buckets" are actually the nodes themselves (the next pointer is in the 00036 /// node). The last node points back to the bucket to simplify node removal. 00037 /// 00038 /// Any node that is to be included in the folding set must be a subclass of 00039 /// FoldingSetNode. The node class must also define a Profile method used to 00040 /// establish the unique bits of data for the node. The Profile method is 00041 /// passed a FoldingSetNodeID object which is used to gather the bits. Just 00042 /// call one of the Add* functions defined in the FoldingSetImpl::NodeID class. 00043 /// NOTE: That the folding set does not own the nodes and it is the 00044 /// responsibility of the user to dispose of the nodes. 00045 /// 00046 /// Eg. 00047 /// class MyNode : public FoldingSetNode { 00048 /// private: 00049 /// std::string Name; 00050 /// unsigned Value; 00051 /// public: 00052 /// MyNode(const char *N, unsigned V) : Name(N), Value(V) {} 00053 /// ... 00054 /// void Profile(FoldingSetNodeID &ID) const { 00055 /// ID.AddString(Name); 00056 /// ID.AddInteger(Value); 00057 /// } 00058 /// ... 00059 /// }; 00060 /// 00061 /// To define the folding set itself use the FoldingSet template; 00062 /// 00063 /// Eg. 00064 /// FoldingSet<MyNode> MyFoldingSet; 00065 /// 00066 /// Four public methods are available to manipulate the folding set; 00067 /// 00068 /// 1) If you have an existing node that you want add to the set but unsure 00069 /// that the node might already exist then call; 00070 /// 00071 /// MyNode *M = MyFoldingSet.GetOrInsertNode(N); 00072 /// 00073 /// If The result is equal to the input then the node has been inserted. 00074 /// Otherwise, the result is the node existing in the folding set, and the 00075 /// input can be discarded (use the result instead.) 00076 /// 00077 /// 2) If you are ready to construct a node but want to check if it already 00078 /// exists, then call FindNodeOrInsertPos with a FoldingSetNodeID of the bits to 00079 /// check; 00080 /// 00081 /// FoldingSetNodeID ID; 00082 /// ID.AddString(Name); 00083 /// ID.AddInteger(Value); 00084 /// void *InsertPoint; 00085 /// 00086 /// MyNode *M = MyFoldingSet.FindNodeOrInsertPos(ID, InsertPoint); 00087 /// 00088 /// If found then M with be non-NULL, else InsertPoint will point to where it 00089 /// should be inserted using InsertNode. 00090 /// 00091 /// 3) If you get a NULL result from FindNodeOrInsertPos then you can as a new 00092 /// node with FindNodeOrInsertPos; 00093 /// 00094 /// InsertNode(N, InsertPoint); 00095 /// 00096 /// 4) Finally, if you want to remove a node from the folding set call; 00097 /// 00098 /// bool WasRemoved = RemoveNode(N); 00099 /// 00100 /// The result indicates whether the node existed in the folding set. 00101 00102 class FoldingSetNodeID; 00103 00104 //===----------------------------------------------------------------------===// 00105 /// FoldingSetImpl - Implements the folding set functionality. The main 00106 /// structure is an array of buckets. Each bucket is indexed by the hash of 00107 /// the nodes it contains. The bucket itself points to the nodes contained 00108 /// in the bucket via a singly linked list. The last node in the list points 00109 /// back to the bucket to facilitate node removal. 00110 /// 00111 class FoldingSetImpl { 00112 protected: 00113 /// Buckets - Array of bucket chains. 00114 /// 00115 void **Buckets; 00116 00117 /// NumBuckets - Length of the Buckets array. Always a power of 2. 00118 /// 00119 unsigned NumBuckets; 00120 00121 /// NumNodes - Number of nodes in the folding set. Growth occurs when NumNodes 00122 /// is greater than twice the number of buckets. 00123 unsigned NumNodes; 00124 00125 public: 00126 explicit FoldingSetImpl(unsigned Log2InitSize = 6); 00127 virtual ~FoldingSetImpl(); 00128 00129 //===--------------------------------------------------------------------===// 00130 /// Node - This class is used to maintain the singly linked bucket list in 00131 /// a folding set. 00132 /// 00133 class Node { 00134 private: 00135 // NextInFoldingSetBucket - next link in the bucket list. 00136 void *NextInFoldingSetBucket; 00137 00138 public: 00139 00140 Node() : NextInFoldingSetBucket(0) {} 00141 00142 // Accessors 00143 void *getNextInBucket() const { return NextInFoldingSetBucket; } 00144 void SetNextInBucket(void *N) { NextInFoldingSetBucket = N; } 00145 }; 00146 00147 /// clear - Remove all nodes from the folding set. 00148 void clear(); 00149 00150 /// RemoveNode - Remove a node from the folding set, returning true if one 00151 /// was removed or false if the node was not in the folding set. 00152 bool RemoveNode(Node *N); 00153 00154 /// GetOrInsertNode - If there is an existing simple Node exactly 00155 /// equal to the specified node, return it. Otherwise, insert 'N' and return 00156 /// it instead. 00157 Node *GetOrInsertNode(Node *N); 00158 00159 /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists, 00160 /// return it. If not, return the insertion token that will make insertion 00161 /// faster. 00162 Node *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos); 00163 00164 /// InsertNode - Insert the specified node into the folding set, knowing that 00165 /// it is not already in the folding set. InsertPos must be obtained from 00166 /// FindNodeOrInsertPos. 00167 void InsertNode(Node *N, void *InsertPos); 00168 00169 /// size - Returns the number of nodes in the folding set. 00170 unsigned size() const { return NumNodes; } 00171 00172 /// empty - Returns true if there are no nodes in the folding set. 00173 bool empty() const { return NumNodes == 0; } 00174 00175 private: 00176 00177 /// GrowHashTable - Double the size of the hash table and rehash everything. 00178 /// 00179 void GrowHashTable(); 00180 00181 protected: 00182 00183 /// GetNodeProfile - Instantiations of the FoldingSet template implement 00184 /// this function to gather data bits for the given node. 00185 virtual void GetNodeProfile(FoldingSetNodeID &ID, Node *N) const = 0; 00186 }; 00187 00188 //===----------------------------------------------------------------------===// 00189 /// FoldingSetTrait - This trait class is used to define behavior of how 00190 /// to "profile" (in the FoldingSet parlance) an object of a given type. 00191 /// The default behavior is to invoke a 'Profile' method on an object, but 00192 /// through template specialization the behavior can be tailored for specific 00193 /// types. Combined with the FoldingSetNodeWrapper classs, one can add objects 00194 /// to FoldingSets that were not originally designed to have that behavior. 00195 /// 00196 template<typename T> struct FoldingSetTrait { 00197 static inline void Profile(const T& X, FoldingSetNodeID& ID) { X.Profile(ID);} 00198 static inline void Profile(T& X, FoldingSetNodeID& ID) { X.Profile(ID); } 00199 }; 00200 00201 //===--------------------------------------------------------------------===// 00202 /// FoldingSetNodeID - This class is used to gather all the unique data bits of 00203 /// a node. When all the bits are gathered this class is used to produce a 00204 /// hash value for the node. 00205 /// 00206 class FoldingSetNodeID { 00207 /// Bits - Vector of all the data bits that make the node unique. 00208 /// Use a SmallVector to avoid a heap allocation in the common case. 00209 SmallVector<unsigned, 32> Bits; 00210 00211 public: 00212 FoldingSetNodeID() {} 00213 00214 /// getRawData - Return the ith entry in the Bits data. 00215 /// 00216 unsigned getRawData(unsigned i) const { 00217 return Bits[i]; 00218 } 00219 00220 /// Add* - Add various data types to Bit data. 00221 /// 00222 void AddPointer(const void *Ptr); 00223 void AddInteger(signed I); 00224 void AddInteger(unsigned I); 00225 void AddInteger(long I); 00226 void AddInteger(unsigned long I); 00227 void AddInteger(long long I); 00228 void AddInteger(unsigned long long I); 00229 void AddBoolean(bool B) { AddInteger(B ? 1U : 0U); } 00230 void AddString(const char* String, const char* End); 00231 void AddString(const std::string &String); 00232 void AddString(const char* String); 00233 00234 template <typename T> 00235 inline void Add(const T& x) { FoldingSetTrait<T>::Profile(x, *this); } 00236 00237 /// clear - Clear the accumulated profile, allowing this FoldingSetNodeID 00238 /// object to be used to compute a new profile. 00239 inline void clear() { Bits.clear(); } 00240 00241 /// ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used 00242 /// to lookup the node in the FoldingSetImpl. 00243 unsigned ComputeHash() const; 00244 00245 /// operator== - Used to compare two nodes to each other. 00246 /// 00247 bool operator==(const FoldingSetNodeID &RHS) const; 00248 }; 00249 00250 // Convenience type to hide the implementation of the folding set. 00251 typedef FoldingSetImpl::Node FoldingSetNode; 00252 template<class T> class FoldingSetIterator; 00253 template<class T> class FoldingSetBucketIterator; 00254 00255 //===----------------------------------------------------------------------===// 00256 /// FoldingSet - This template class is used to instantiate a specialized 00257 /// implementation of the folding set to the node class T. T must be a 00258 /// subclass of FoldingSetNode and implement a Profile function. 00259 /// 00260 template<class T> class FoldingSet : public FoldingSetImpl { 00261 private: 00262 /// GetNodeProfile - Each instantiatation of the FoldingSet needs to provide a 00263 /// way to convert nodes into a unique specifier. 00264 virtual void GetNodeProfile(FoldingSetNodeID &ID, Node *N) const { 00265 T *TN = static_cast<T *>(N); 00266 FoldingSetTrait<T>::Profile(*TN,ID); 00267 } 00268 00269 public: 00270 explicit FoldingSet(unsigned Log2InitSize = 6) 00271 : FoldingSetImpl(Log2InitSize) 00272 {} 00273 00274 typedef FoldingSetIterator<T> iterator; 00275 iterator begin() { return iterator(Buckets); } 00276 iterator end() { return iterator(Buckets+NumBuckets); } 00277 00278 typedef FoldingSetIterator<const T> const_iterator; 00279 const_iterator begin() const { return const_iterator(Buckets); } 00280 const_iterator end() const { return const_iterator(Buckets+NumBuckets); } 00281 00282 typedef FoldingSetBucketIterator<T> bucket_iterator; 00283 00284 bucket_iterator bucket_begin(unsigned hash) { 00285 return bucket_iterator(Buckets + (hash & (NumBuckets-1))); 00286 } 00287 00288 bucket_iterator bucket_end(unsigned hash) { 00289 return bucket_iterator(Buckets + (hash & (NumBuckets-1)), true); 00290 } 00291 00292 /// GetOrInsertNode - If there is an existing simple Node exactly 00293 /// equal to the specified node, return it. Otherwise, insert 'N' and 00294 /// return it instead. 00295 T *GetOrInsertNode(Node *N) { 00296 return static_cast<T *>(FoldingSetImpl::GetOrInsertNode(N)); 00297 } 00298 00299 /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists, 00300 /// return it. If not, return the insertion token that will make insertion 00301 /// faster. 00302 T *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos) { 00303 return static_cast<T *>(FoldingSetImpl::FindNodeOrInsertPos(ID, InsertPos)); 00304 } 00305 }; 00306 00307 //===----------------------------------------------------------------------===// 00308 /// FoldingSetIteratorImpl - This is the common iterator support shared by all 00309 /// folding sets, which knows how to walk the folding set hash table. 00310 class FoldingSetIteratorImpl { 00311 protected: 00312 FoldingSetNode *NodePtr; 00313 FoldingSetIteratorImpl(void **Bucket); 00314 void advance(); 00315 00316 public: 00317 bool operator==(const FoldingSetIteratorImpl &RHS) const { 00318 return NodePtr == RHS.NodePtr; 00319 } 00320 bool operator!=(const FoldingSetIteratorImpl &RHS) const { 00321 return NodePtr != RHS.NodePtr; 00322 } 00323 }; 00324 00325 00326 template<class T> 00327 class FoldingSetIterator : public FoldingSetIteratorImpl { 00328 public: 00329 explicit FoldingSetIterator(void **Bucket) : FoldingSetIteratorImpl(Bucket) {} 00330 00331 T &operator*() const { 00332 return *static_cast<T*>(NodePtr); 00333 } 00334 00335 T *operator->() const { 00336 return static_cast<T*>(NodePtr); 00337 } 00338 00339 inline FoldingSetIterator& operator++() { // Preincrement 00340 advance(); 00341 return *this; 00342 } 00343 FoldingSetIterator operator++(int) { // Postincrement 00344 FoldingSetIterator tmp = *this; ++*this; return tmp; 00345 } 00346 }; 00347 00348 //===----------------------------------------------------------------------===// 00349 /// FoldingSetBucketIteratorImpl - This is the common bucket iterator support 00350 /// shared by all folding sets, which knows how to walk a particular bucket 00351 /// of a folding set hash table. 00352 00353 class FoldingSetBucketIteratorImpl { 00354 protected: 00355 void *Ptr; 00356 00357 explicit FoldingSetBucketIteratorImpl(void **Bucket); 00358 00359 FoldingSetBucketIteratorImpl(void **Bucket, bool) 00360 : Ptr(Bucket) {} 00361 00362 void advance() { 00363 void *Probe = static_cast<FoldingSetNode*>(Ptr)->getNextInBucket(); 00364 uintptr_t x = reinterpret_cast<uintptr_t>(Probe) & ~0x1; 00365 Ptr = reinterpret_cast<void*>(x); 00366 } 00367 00368 public: 00369 bool operator==(const FoldingSetBucketIteratorImpl &RHS) const { 00370 return Ptr == RHS.Ptr; 00371 } 00372 bool operator!=(const FoldingSetBucketIteratorImpl &RHS) const { 00373 return Ptr != RHS.Ptr; 00374 } 00375 }; 00376 00377 00378 template<class T> 00379 class FoldingSetBucketIterator : public FoldingSetBucketIteratorImpl { 00380 public: 00381 explicit FoldingSetBucketIterator(void **Bucket) : 00382 FoldingSetBucketIteratorImpl(Bucket) {} 00383 00384 FoldingSetBucketIterator(void **Bucket, bool) : 00385 FoldingSetBucketIteratorImpl(Bucket, true) {} 00386 00387 T& operator*() const { return *static_cast<T*>(Ptr); } 00388 T* operator->() const { return static_cast<T*>(Ptr); } 00389 00390 inline FoldingSetBucketIterator& operator++() { // Preincrement 00391 advance(); 00392 return *this; 00393 } 00394 FoldingSetBucketIterator operator++(int) { // Postincrement 00395 FoldingSetBucketIterator tmp = *this; ++*this; return tmp; 00396 } 00397 }; 00398 00399 //===----------------------------------------------------------------------===// 00400 /// FoldingSetNodeWrapper - This template class is used to "wrap" arbitrary 00401 /// types in an enclosing object so that they can be inserted into FoldingSets. 00402 template <typename T> 00403 class FoldingSetNodeWrapper : public FoldingSetNode { 00404 T data; 00405 public: 00406 explicit FoldingSetNodeWrapper(const T& x) : data(x) {} 00407 virtual ~FoldingSetNodeWrapper() {} 00408 00409 template<typename A1> 00410 explicit FoldingSetNodeWrapper(const A1& a1) 00411 : data(a1) {} 00412 00413 template <typename A1, typename A2> 00414 explicit FoldingSetNodeWrapper(const A1& a1, const A2& a2) 00415 : data(a1,a2) {} 00416 00417 template <typename A1, typename A2, typename A3> 00418 explicit FoldingSetNodeWrapper(const A1& a1, const A2& a2, const A3& a3) 00419 : data(a1,a2,a3) {} 00420 00421 template <typename A1, typename A2, typename A3, typename A4> 00422 explicit FoldingSetNodeWrapper(const A1& a1, const A2& a2, const A3& a3, 00423 const A4& a4) 00424 : data(a1,a2,a3,a4) {} 00425 00426 template <typename A1, typename A2, typename A3, typename A4, typename A5> 00427 explicit FoldingSetNodeWrapper(const A1& a1, const A2& a2, const A3& a3, 00428 const A4& a4, const A5& a5) 00429 : data(a1,a2,a3,a4,a5) {} 00430 00431 00432 void Profile(FoldingSetNodeID& ID) { FoldingSetTrait<T>::Profile(data, ID); } 00433 00434 T& getValue() { return data; } 00435 const T& getValue() const { return data; } 00436 00437 operator T&() { return data; } 00438 operator const T&() const { return data; } 00439 }; 00440 00441 //===----------------------------------------------------------------------===// 00442 /// FastFoldingSetNode - This is a subclass of FoldingSetNode which stores 00443 /// a FoldingSetNodeID value rather than requiring the node to recompute it 00444 /// each time it is needed. This trades space for speed (which can be 00445 /// significant if the ID is long), and it also permits nodes to drop 00446 /// information that would otherwise only be required for recomputing an ID. 00447 class FastFoldingSetNode : public FoldingSetNode { 00448 FoldingSetNodeID FastID; 00449 protected: 00450 explicit FastFoldingSetNode(const FoldingSetNodeID &ID) : FastID(ID) {} 00451 public: 00452 void Profile(FoldingSetNodeID& ID) { ID = FastID; } 00453 }; 00454 00455 //===----------------------------------------------------------------------===// 00456 // Partial specializations of FoldingSetTrait. 00457 00458 template<typename T> struct FoldingSetTrait<T*> { 00459 static inline void Profile(const T* X, FoldingSetNodeID& ID) { 00460 ID.AddPointer(X); 00461 } 00462 static inline void Profile(T* X, FoldingSetNodeID& ID) { 00463 ID.AddPointer(X); 00464 } 00465 }; 00466 00467 template<typename T> struct FoldingSetTrait<const T*> { 00468 static inline void Profile(const T* X, FoldingSetNodeID& ID) { 00469 ID.AddPointer(X); 00470 } 00471 }; 00472 00473 } // End of namespace llvm. 00474 00475 #endif