1 //===- llvm/ADT/FoldingSet.h - Uniquing Hash Set ----------------*- C++ -*-===// 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 /// \file 10 /// This file defines a hash set that can be used to remove duplication of nodes 11 /// in a graph. This code was originally created by Chris Lattner for use with 12 /// SelectionDAGCSEMap, but was isolated to provide use across the llvm code 13 /// set. 14 //===----------------------------------------------------------------------===// 15 16 #ifndef LLVM_ADT_FOLDINGSET_H 17 #define LLVM_ADT_FOLDINGSET_H 18 19 #include "llvm/ADT/Hashing.h" 20 #include "llvm/ADT/SmallVector.h" 21 #include "llvm/ADT/iterator.h" 22 #include "llvm/Support/Allocator.h" 23 #include <cassert> 24 #include <cstddef> 25 #include <cstdint> 26 #include <type_traits> 27 #include <utility> 28 29 namespace llvm { 30 31 /// This folding set used for two purposes: 32 /// 1. Given information about a node we want to create, look up the unique 33 /// instance of the node in the set. If the node already exists, return 34 /// it, otherwise return the bucket it should be inserted into. 35 /// 2. Given a node that has already been created, remove it from the set. 36 /// 37 /// This class is implemented as a single-link chained hash table, where the 38 /// "buckets" are actually the nodes themselves (the next pointer is in the 39 /// node). The last node points back to the bucket to simplify node removal. 40 /// 41 /// Any node that is to be included in the folding set must be a subclass of 42 /// FoldingSetNode. The node class must also define a Profile method used to 43 /// establish the unique bits of data for the node. The Profile method is 44 /// passed a FoldingSetNodeID object which is used to gather the bits. Just 45 /// call one of the Add* functions defined in the FoldingSetBase::NodeID class. 46 /// NOTE: That the folding set does not own the nodes and it is the 47 /// responsibility of the user to dispose of the nodes. 48 /// 49 /// Eg. 50 /// class MyNode : public FoldingSetNode { 51 /// private: 52 /// std::string Name; 53 /// unsigned Value; 54 /// public: 55 /// MyNode(const char *N, unsigned V) : Name(N), Value(V) {} 56 /// ... 57 /// void Profile(FoldingSetNodeID &ID) const { 58 /// ID.AddString(Name); 59 /// ID.AddInteger(Value); 60 /// } 61 /// ... 62 /// }; 63 /// 64 /// To define the folding set itself use the FoldingSet template; 65 /// 66 /// Eg. 67 /// FoldingSet<MyNode> MyFoldingSet; 68 /// 69 /// Four public methods are available to manipulate the folding set; 70 /// 71 /// 1) If you have an existing node that you want add to the set but unsure 72 /// that the node might already exist then call; 73 /// 74 /// MyNode *M = MyFoldingSet.GetOrInsertNode(N); 75 /// 76 /// If The result is equal to the input then the node has been inserted. 77 /// Otherwise, the result is the node existing in the folding set, and the 78 /// input can be discarded (use the result instead.) 79 /// 80 /// 2) If you are ready to construct a node but want to check if it already 81 /// exists, then call FindNodeOrInsertPos with a FoldingSetNodeID of the bits to 82 /// check; 83 /// 84 /// FoldingSetNodeID ID; 85 /// ID.AddString(Name); 86 /// ID.AddInteger(Value); 87 /// void *InsertPoint; 88 /// 89 /// MyNode *M = MyFoldingSet.FindNodeOrInsertPos(ID, InsertPoint); 90 /// 91 /// If found then M will be non-NULL, else InsertPoint will point to where it 92 /// should be inserted using InsertNode. 93 /// 94 /// 3) If you get a NULL result from FindNodeOrInsertPos then you can insert a 95 /// new node with InsertNode; 96 /// 97 /// MyFoldingSet.InsertNode(M, InsertPoint); 98 /// 99 /// 4) Finally, if you want to remove a node from the folding set call; 100 /// 101 /// bool WasRemoved = MyFoldingSet.RemoveNode(M); 102 /// 103 /// The result indicates whether the node existed in the folding set. 104 105 class FoldingSetNodeID; 106 class StringRef; 107 108 //===----------------------------------------------------------------------===// 109 /// FoldingSetBase - Implements the folding set functionality. The main 110 /// structure is an array of buckets. Each bucket is indexed by the hash of 111 /// the nodes it contains. The bucket itself points to the nodes contained 112 /// in the bucket via a singly linked list. The last node in the list points 113 /// back to the bucket to facilitate node removal. 114 /// 115 class FoldingSetBase { 116 protected: 117 /// Buckets - Array of bucket chains. 118 void **Buckets; 119 120 /// NumBuckets - Length of the Buckets array. Always a power of 2. 121 unsigned NumBuckets; 122 123 /// NumNodes - Number of nodes in the folding set. Growth occurs when NumNodes 124 /// is greater than twice the number of buckets. 125 unsigned NumNodes; 126 127 explicit FoldingSetBase(unsigned Log2InitSize = 6); 128 FoldingSetBase(FoldingSetBase &&Arg); 129 FoldingSetBase &operator=(FoldingSetBase &&RHS); 130 ~FoldingSetBase(); 131 132 public: 133 //===--------------------------------------------------------------------===// 134 /// Node - This class is used to maintain the singly linked bucket list in 135 /// a folding set. 136 class Node { 137 private: 138 // NextInFoldingSetBucket - next link in the bucket list. 139 void *NextInFoldingSetBucket = nullptr; 140 141 public: 142 Node() = default; 143 144 // Accessors 145 void *getNextInBucket() const { return NextInFoldingSetBucket; } 146 void SetNextInBucket(void *N) { NextInFoldingSetBucket = N; } 147 }; 148 149 /// clear - Remove all nodes from the folding set. 150 void clear(); 151 152 /// size - Returns the number of nodes in the folding set. 153 unsigned size() const { return NumNodes; } 154 155 /// empty - Returns true if there are no nodes in the folding set. 156 bool empty() const { return NumNodes == 0; } 157 158 /// capacity - Returns the number of nodes permitted in the folding set 159 /// before a rebucket operation is performed. 160 unsigned capacity() { 161 // We allow a load factor of up to 2.0, 162 // so that means our capacity is NumBuckets * 2 163 return NumBuckets * 2; 164 } 165 166 protected: 167 /// Functions provided by the derived class to compute folding properties. 168 /// This is effectively a vtable for FoldingSetBase, except that we don't 169 /// actually store a pointer to it in the object. 170 struct FoldingSetInfo { 171 /// GetNodeProfile - Instantiations of the FoldingSet template implement 172 /// this function to gather data bits for the given node. 173 void (*GetNodeProfile)(const FoldingSetBase *Self, Node *N, 174 FoldingSetNodeID &ID); 175 176 /// NodeEquals - Instantiations of the FoldingSet template implement 177 /// this function to compare the given node with the given ID. 178 bool (*NodeEquals)(const FoldingSetBase *Self, Node *N, 179 const FoldingSetNodeID &ID, unsigned IDHash, 180 FoldingSetNodeID &TempID); 181 182 /// ComputeNodeHash - Instantiations of the FoldingSet template implement 183 /// this function to compute a hash value for the given node. 184 unsigned (*ComputeNodeHash)(const FoldingSetBase *Self, Node *N, 185 FoldingSetNodeID &TempID); 186 }; 187 188 private: 189 /// GrowHashTable - Double the size of the hash table and rehash everything. 190 void GrowHashTable(const FoldingSetInfo &Info); 191 192 /// GrowBucketCount - resize the hash table and rehash everything. 193 /// NewBucketCount must be a power of two, and must be greater than the old 194 /// bucket count. 195 void GrowBucketCount(unsigned NewBucketCount, const FoldingSetInfo &Info); 196 197 protected: 198 // The below methods are protected to encourage subclasses to provide a more 199 // type-safe API. 200 201 /// reserve - Increase the number of buckets such that adding the 202 /// EltCount-th node won't cause a rebucket operation. reserve is permitted 203 /// to allocate more space than requested by EltCount. 204 void reserve(unsigned EltCount, const FoldingSetInfo &Info); 205 206 /// RemoveNode - Remove a node from the folding set, returning true if one 207 /// was removed or false if the node was not in the folding set. 208 bool RemoveNode(Node *N); 209 210 /// GetOrInsertNode - If there is an existing simple Node exactly 211 /// equal to the specified node, return it. Otherwise, insert 'N' and return 212 /// it instead. 213 Node *GetOrInsertNode(Node *N, const FoldingSetInfo &Info); 214 215 /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists, 216 /// return it. If not, return the insertion token that will make insertion 217 /// faster. 218 Node *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos, 219 const FoldingSetInfo &Info); 220 221 /// InsertNode - Insert the specified node into the folding set, knowing that 222 /// it is not already in the folding set. InsertPos must be obtained from 223 /// FindNodeOrInsertPos. 224 void InsertNode(Node *N, void *InsertPos, const FoldingSetInfo &Info); 225 }; 226 227 //===----------------------------------------------------------------------===// 228 229 /// DefaultFoldingSetTrait - This class provides default implementations 230 /// for FoldingSetTrait implementations. 231 template<typename T> struct DefaultFoldingSetTrait { 232 static void Profile(const T &X, FoldingSetNodeID &ID) { 233 X.Profile(ID); 234 } 235 static void Profile(T &X, FoldingSetNodeID &ID) { 236 X.Profile(ID); 237 } 238 239 // Equals - Test if the profile for X would match ID, using TempID 240 // to compute a temporary ID if necessary. The default implementation 241 // just calls Profile and does a regular comparison. Implementations 242 // can override this to provide more efficient implementations. 243 static inline bool Equals(T &X, const FoldingSetNodeID &ID, unsigned IDHash, 244 FoldingSetNodeID &TempID); 245 246 // ComputeHash - Compute a hash value for X, using TempID to 247 // compute a temporary ID if necessary. The default implementation 248 // just calls Profile and does a regular hash computation. 249 // Implementations can override this to provide more efficient 250 // implementations. 251 static inline unsigned ComputeHash(T &X, FoldingSetNodeID &TempID); 252 }; 253 254 /// FoldingSetTrait - This trait class is used to define behavior of how 255 /// to "profile" (in the FoldingSet parlance) an object of a given type. 256 /// The default behavior is to invoke a 'Profile' method on an object, but 257 /// through template specialization the behavior can be tailored for specific 258 /// types. Combined with the FoldingSetNodeWrapper class, one can add objects 259 /// to FoldingSets that were not originally designed to have that behavior. 260 template <typename T, typename Enable = void> 261 struct FoldingSetTrait : public DefaultFoldingSetTrait<T> {}; 262 263 /// DefaultContextualFoldingSetTrait - Like DefaultFoldingSetTrait, but 264 /// for ContextualFoldingSets. 265 template<typename T, typename Ctx> 266 struct DefaultContextualFoldingSetTrait { 267 static void Profile(T &X, FoldingSetNodeID &ID, Ctx Context) { 268 X.Profile(ID, Context); 269 } 270 271 static inline bool Equals(T &X, const FoldingSetNodeID &ID, unsigned IDHash, 272 FoldingSetNodeID &TempID, Ctx Context); 273 static inline unsigned ComputeHash(T &X, FoldingSetNodeID &TempID, 274 Ctx Context); 275 }; 276 277 /// ContextualFoldingSetTrait - Like FoldingSetTrait, but for 278 /// ContextualFoldingSets. 279 template<typename T, typename Ctx> struct ContextualFoldingSetTrait 280 : public DefaultContextualFoldingSetTrait<T, Ctx> {}; 281 282 //===--------------------------------------------------------------------===// 283 /// FoldingSetNodeIDRef - This class describes a reference to an interned 284 /// FoldingSetNodeID, which can be a useful to store node id data rather 285 /// than using plain FoldingSetNodeIDs, since the 32-element SmallVector 286 /// is often much larger than necessary, and the possibility of heap 287 /// allocation means it requires a non-trivial destructor call. 288 class FoldingSetNodeIDRef { 289 const unsigned *Data = nullptr; 290 size_t Size = 0; 291 292 public: 293 FoldingSetNodeIDRef() = default; 294 FoldingSetNodeIDRef(const unsigned *D, size_t S) : Data(D), Size(S) {} 295 296 /// ComputeHash - Compute a strong hash value for this FoldingSetNodeIDRef, 297 /// used to lookup the node in the FoldingSetBase. 298 unsigned ComputeHash() const { 299 return static_cast<unsigned>(hash_combine_range(Data, Data + Size)); 300 } 301 302 bool operator==(FoldingSetNodeIDRef) const; 303 304 bool operator!=(FoldingSetNodeIDRef RHS) const { return !(*this == RHS); } 305 306 /// Used to compare the "ordering" of two nodes as defined by the 307 /// profiled bits and their ordering defined by memcmp(). 308 bool operator<(FoldingSetNodeIDRef) const; 309 310 const unsigned *getData() const { return Data; } 311 size_t getSize() const { return Size; } 312 }; 313 314 //===--------------------------------------------------------------------===// 315 /// FoldingSetNodeID - This class is used to gather all the unique data bits of 316 /// a node. When all the bits are gathered this class is used to produce a 317 /// hash value for the node. 318 class FoldingSetNodeID { 319 /// Bits - Vector of all the data bits that make the node unique. 320 /// Use a SmallVector to avoid a heap allocation in the common case. 321 SmallVector<unsigned, 32> Bits; 322 323 public: 324 FoldingSetNodeID() = default; 325 326 FoldingSetNodeID(FoldingSetNodeIDRef Ref) 327 : Bits(Ref.getData(), Ref.getData() + Ref.getSize()) {} 328 329 /// Add* - Add various data types to Bit data. 330 void AddPointer(const void *Ptr) { 331 // Note: this adds pointers to the hash using sizes and endianness that 332 // depend on the host. It doesn't matter, however, because hashing on 333 // pointer values is inherently unstable. Nothing should depend on the 334 // ordering of nodes in the folding set. 335 static_assert(sizeof(uintptr_t) <= sizeof(unsigned long long), 336 "unexpected pointer size"); 337 AddInteger(reinterpret_cast<uintptr_t>(Ptr)); 338 } 339 void AddInteger(signed I) { Bits.push_back(I); } 340 void AddInteger(unsigned I) { Bits.push_back(I); } 341 void AddInteger(long I) { AddInteger((unsigned long)I); } 342 void AddInteger(unsigned long I) { 343 if (sizeof(long) == sizeof(int)) 344 AddInteger(unsigned(I)); 345 else if (sizeof(long) == sizeof(long long)) { 346 AddInteger((unsigned long long)I); 347 } else { 348 llvm_unreachable("unexpected sizeof(long)"); 349 } 350 } 351 void AddInteger(long long I) { AddInteger((unsigned long long)I); } 352 void AddInteger(unsigned long long I) { 353 AddInteger(unsigned(I)); 354 AddInteger(unsigned(I >> 32)); 355 } 356 357 void AddBoolean(bool B) { AddInteger(B ? 1U : 0U); } 358 void AddString(StringRef String); 359 void AddNodeID(const FoldingSetNodeID &ID); 360 361 template <typename T> 362 inline void Add(const T &x) { FoldingSetTrait<T>::Profile(x, *this); } 363 364 /// clear - Clear the accumulated profile, allowing this FoldingSetNodeID 365 /// object to be used to compute a new profile. 366 inline void clear() { Bits.clear(); } 367 368 /// ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used 369 /// to lookup the node in the FoldingSetBase. 370 unsigned ComputeHash() const { 371 return FoldingSetNodeIDRef(Bits.data(), Bits.size()).ComputeHash(); 372 } 373 374 /// operator== - Used to compare two nodes to each other. 375 bool operator==(const FoldingSetNodeID &RHS) const; 376 bool operator==(const FoldingSetNodeIDRef RHS) const; 377 378 bool operator!=(const FoldingSetNodeID &RHS) const { return !(*this == RHS); } 379 bool operator!=(const FoldingSetNodeIDRef RHS) const { return !(*this ==RHS);} 380 381 /// Used to compare the "ordering" of two nodes as defined by the 382 /// profiled bits and their ordering defined by memcmp(). 383 bool operator<(const FoldingSetNodeID &RHS) const; 384 bool operator<(const FoldingSetNodeIDRef RHS) const; 385 386 /// Intern - Copy this node's data to a memory region allocated from the 387 /// given allocator and return a FoldingSetNodeIDRef describing the 388 /// interned data. 389 FoldingSetNodeIDRef Intern(BumpPtrAllocator &Allocator) const; 390 }; 391 392 // Convenience type to hide the implementation of the folding set. 393 using FoldingSetNode = FoldingSetBase::Node; 394 template<class T> class FoldingSetIterator; 395 template<class T> class FoldingSetBucketIterator; 396 397 // Definitions of FoldingSetTrait and ContextualFoldingSetTrait functions, which 398 // require the definition of FoldingSetNodeID. 399 template<typename T> 400 inline bool 401 DefaultFoldingSetTrait<T>::Equals(T &X, const FoldingSetNodeID &ID, 402 unsigned /*IDHash*/, 403 FoldingSetNodeID &TempID) { 404 FoldingSetTrait<T>::Profile(X, TempID); 405 return TempID == ID; 406 } 407 template<typename T> 408 inline unsigned 409 DefaultFoldingSetTrait<T>::ComputeHash(T &X, FoldingSetNodeID &TempID) { 410 FoldingSetTrait<T>::Profile(X, TempID); 411 return TempID.ComputeHash(); 412 } 413 template<typename T, typename Ctx> 414 inline bool 415 DefaultContextualFoldingSetTrait<T, Ctx>::Equals(T &X, 416 const FoldingSetNodeID &ID, 417 unsigned /*IDHash*/, 418 FoldingSetNodeID &TempID, 419 Ctx Context) { 420 ContextualFoldingSetTrait<T, Ctx>::Profile(X, TempID, Context); 421 return TempID == ID; 422 } 423 template<typename T, typename Ctx> 424 inline unsigned 425 DefaultContextualFoldingSetTrait<T, Ctx>::ComputeHash(T &X, 426 FoldingSetNodeID &TempID, 427 Ctx Context) { 428 ContextualFoldingSetTrait<T, Ctx>::Profile(X, TempID, Context); 429 return TempID.ComputeHash(); 430 } 431 432 //===----------------------------------------------------------------------===// 433 /// FoldingSetImpl - An implementation detail that lets us share code between 434 /// FoldingSet and ContextualFoldingSet. 435 template <class Derived, class T> class FoldingSetImpl : public FoldingSetBase { 436 protected: 437 explicit FoldingSetImpl(unsigned Log2InitSize) 438 : FoldingSetBase(Log2InitSize) {} 439 440 FoldingSetImpl(FoldingSetImpl &&Arg) = default; 441 FoldingSetImpl &operator=(FoldingSetImpl &&RHS) = default; 442 ~FoldingSetImpl() = default; 443 444 public: 445 using iterator = FoldingSetIterator<T>; 446 447 iterator begin() { return iterator(Buckets); } 448 iterator end() { return iterator(Buckets+NumBuckets); } 449 450 using const_iterator = FoldingSetIterator<const T>; 451 452 const_iterator begin() const { return const_iterator(Buckets); } 453 const_iterator end() const { return const_iterator(Buckets+NumBuckets); } 454 455 using bucket_iterator = FoldingSetBucketIterator<T>; 456 457 bucket_iterator bucket_begin(unsigned hash) { 458 return bucket_iterator(Buckets + (hash & (NumBuckets-1))); 459 } 460 461 bucket_iterator bucket_end(unsigned hash) { 462 return bucket_iterator(Buckets + (hash & (NumBuckets-1)), true); 463 } 464 465 /// reserve - Increase the number of buckets such that adding the 466 /// EltCount-th node won't cause a rebucket operation. reserve is permitted 467 /// to allocate more space than requested by EltCount. 468 void reserve(unsigned EltCount) { 469 return FoldingSetBase::reserve(EltCount, Derived::getFoldingSetInfo()); 470 } 471 472 /// RemoveNode - Remove a node from the folding set, returning true if one 473 /// was removed or false if the node was not in the folding set. 474 bool RemoveNode(T *N) { 475 return FoldingSetBase::RemoveNode(N); 476 } 477 478 /// GetOrInsertNode - If there is an existing simple Node exactly 479 /// equal to the specified node, return it. Otherwise, insert 'N' and 480 /// return it instead. 481 T *GetOrInsertNode(T *N) { 482 return static_cast<T *>( 483 FoldingSetBase::GetOrInsertNode(N, Derived::getFoldingSetInfo())); 484 } 485 486 /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists, 487 /// return it. If not, return the insertion token that will make insertion 488 /// faster. 489 T *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos) { 490 return static_cast<T *>(FoldingSetBase::FindNodeOrInsertPos( 491 ID, InsertPos, Derived::getFoldingSetInfo())); 492 } 493 494 /// InsertNode - Insert the specified node into the folding set, knowing that 495 /// it is not already in the folding set. InsertPos must be obtained from 496 /// FindNodeOrInsertPos. 497 void InsertNode(T *N, void *InsertPos) { 498 FoldingSetBase::InsertNode(N, InsertPos, Derived::getFoldingSetInfo()); 499 } 500 501 /// InsertNode - Insert the specified node into the folding set, knowing that 502 /// it is not already in the folding set. 503 void InsertNode(T *N) { 504 T *Inserted = GetOrInsertNode(N); 505 (void)Inserted; 506 assert(Inserted == N && "Node already inserted!"); 507 } 508 }; 509 510 //===----------------------------------------------------------------------===// 511 /// FoldingSet - This template class is used to instantiate a specialized 512 /// implementation of the folding set to the node class T. T must be a 513 /// subclass of FoldingSetNode and implement a Profile function. 514 /// 515 /// Note that this set type is movable and move-assignable. However, its 516 /// moved-from state is not a valid state for anything other than 517 /// move-assigning and destroying. This is primarily to enable movable APIs 518 /// that incorporate these objects. 519 template <class T> 520 class FoldingSet : public FoldingSetImpl<FoldingSet<T>, T> { 521 using Super = FoldingSetImpl<FoldingSet, T>; 522 using Node = typename Super::Node; 523 524 /// GetNodeProfile - Each instantiation of the FoldingSet needs to provide a 525 /// way to convert nodes into a unique specifier. 526 static void GetNodeProfile(const FoldingSetBase *, Node *N, 527 FoldingSetNodeID &ID) { 528 T *TN = static_cast<T *>(N); 529 FoldingSetTrait<T>::Profile(*TN, ID); 530 } 531 532 /// NodeEquals - Instantiations may optionally provide a way to compare a 533 /// node with a specified ID. 534 static bool NodeEquals(const FoldingSetBase *, Node *N, 535 const FoldingSetNodeID &ID, unsigned IDHash, 536 FoldingSetNodeID &TempID) { 537 T *TN = static_cast<T *>(N); 538 return FoldingSetTrait<T>::Equals(*TN, ID, IDHash, TempID); 539 } 540 541 /// ComputeNodeHash - Instantiations may optionally provide a way to compute a 542 /// hash value directly from a node. 543 static unsigned ComputeNodeHash(const FoldingSetBase *, Node *N, 544 FoldingSetNodeID &TempID) { 545 T *TN = static_cast<T *>(N); 546 return FoldingSetTrait<T>::ComputeHash(*TN, TempID); 547 } 548 549 static const FoldingSetBase::FoldingSetInfo &getFoldingSetInfo() { 550 static constexpr FoldingSetBase::FoldingSetInfo Info = { 551 GetNodeProfile, NodeEquals, ComputeNodeHash}; 552 return Info; 553 } 554 friend Super; 555 556 public: 557 explicit FoldingSet(unsigned Log2InitSize = 6) : Super(Log2InitSize) {} 558 FoldingSet(FoldingSet &&Arg) = default; 559 FoldingSet &operator=(FoldingSet &&RHS) = default; 560 }; 561 562 //===----------------------------------------------------------------------===// 563 /// ContextualFoldingSet - This template class is a further refinement 564 /// of FoldingSet which provides a context argument when calling 565 /// Profile on its nodes. Currently, that argument is fixed at 566 /// initialization time. 567 /// 568 /// T must be a subclass of FoldingSetNode and implement a Profile 569 /// function with signature 570 /// void Profile(FoldingSetNodeID &, Ctx); 571 template <class T, class Ctx> 572 class ContextualFoldingSet 573 : public FoldingSetImpl<ContextualFoldingSet<T, Ctx>, T> { 574 // Unfortunately, this can't derive from FoldingSet<T> because the 575 // construction of the vtable for FoldingSet<T> requires 576 // FoldingSet<T>::GetNodeProfile to be instantiated, which in turn 577 // requires a single-argument T::Profile(). 578 579 using Super = FoldingSetImpl<ContextualFoldingSet, T>; 580 using Node = typename Super::Node; 581 582 Ctx Context; 583 584 static const Ctx &getContext(const FoldingSetBase *Base) { 585 return static_cast<const ContextualFoldingSet*>(Base)->Context; 586 } 587 588 /// GetNodeProfile - Each instantiatation of the FoldingSet needs to provide a 589 /// way to convert nodes into a unique specifier. 590 static void GetNodeProfile(const FoldingSetBase *Base, Node *N, 591 FoldingSetNodeID &ID) { 592 T *TN = static_cast<T *>(N); 593 ContextualFoldingSetTrait<T, Ctx>::Profile(*TN, ID, getContext(Base)); 594 } 595 596 static bool NodeEquals(const FoldingSetBase *Base, Node *N, 597 const FoldingSetNodeID &ID, unsigned IDHash, 598 FoldingSetNodeID &TempID) { 599 T *TN = static_cast<T *>(N); 600 return ContextualFoldingSetTrait<T, Ctx>::Equals(*TN, ID, IDHash, TempID, 601 getContext(Base)); 602 } 603 604 static unsigned ComputeNodeHash(const FoldingSetBase *Base, Node *N, 605 FoldingSetNodeID &TempID) { 606 T *TN = static_cast<T *>(N); 607 return ContextualFoldingSetTrait<T, Ctx>::ComputeHash(*TN, TempID, 608 getContext(Base)); 609 } 610 611 static const FoldingSetBase::FoldingSetInfo &getFoldingSetInfo() { 612 static constexpr FoldingSetBase::FoldingSetInfo Info = { 613 GetNodeProfile, NodeEquals, ComputeNodeHash}; 614 return Info; 615 } 616 friend Super; 617 618 public: 619 explicit ContextualFoldingSet(Ctx Context, unsigned Log2InitSize = 6) 620 : Super(Log2InitSize), Context(Context) {} 621 622 Ctx getContext() const { return Context; } 623 }; 624 625 //===----------------------------------------------------------------------===// 626 /// FoldingSetVector - This template class combines a FoldingSet and a vector 627 /// to provide the interface of FoldingSet but with deterministic iteration 628 /// order based on the insertion order. T must be a subclass of FoldingSetNode 629 /// and implement a Profile function. 630 template <class T, class VectorT = SmallVector<T*, 8>> 631 class FoldingSetVector { 632 FoldingSet<T> Set; 633 VectorT Vector; 634 635 public: 636 explicit FoldingSetVector(unsigned Log2InitSize = 6) : Set(Log2InitSize) {} 637 638 using iterator = pointee_iterator<typename VectorT::iterator>; 639 640 iterator begin() { return Vector.begin(); } 641 iterator end() { return Vector.end(); } 642 643 using const_iterator = pointee_iterator<typename VectorT::const_iterator>; 644 645 const_iterator begin() const { return Vector.begin(); } 646 const_iterator end() const { return Vector.end(); } 647 648 /// clear - Remove all nodes from the folding set. 649 void clear() { Set.clear(); Vector.clear(); } 650 651 /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists, 652 /// return it. If not, return the insertion token that will make insertion 653 /// faster. 654 T *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos) { 655 return Set.FindNodeOrInsertPos(ID, InsertPos); 656 } 657 658 /// GetOrInsertNode - If there is an existing simple Node exactly 659 /// equal to the specified node, return it. Otherwise, insert 'N' and 660 /// return it instead. 661 T *GetOrInsertNode(T *N) { 662 T *Result = Set.GetOrInsertNode(N); 663 if (Result == N) Vector.push_back(N); 664 return Result; 665 } 666 667 /// InsertNode - Insert the specified node into the folding set, knowing that 668 /// it is not already in the folding set. InsertPos must be obtained from 669 /// FindNodeOrInsertPos. 670 void InsertNode(T *N, void *InsertPos) { 671 Set.InsertNode(N, InsertPos); 672 Vector.push_back(N); 673 } 674 675 /// InsertNode - Insert the specified node into the folding set, knowing that 676 /// it is not already in the folding set. 677 void InsertNode(T *N) { 678 Set.InsertNode(N); 679 Vector.push_back(N); 680 } 681 682 /// size - Returns the number of nodes in the folding set. 683 unsigned size() const { return Set.size(); } 684 685 /// empty - Returns true if there are no nodes in the folding set. 686 bool empty() const { return Set.empty(); } 687 }; 688 689 //===----------------------------------------------------------------------===// 690 /// FoldingSetIteratorImpl - This is the common iterator support shared by all 691 /// folding sets, which knows how to walk the folding set hash table. 692 class FoldingSetIteratorImpl { 693 protected: 694 FoldingSetNode *NodePtr; 695 696 FoldingSetIteratorImpl(void **Bucket); 697 698 void advance(); 699 700 public: 701 bool operator==(const FoldingSetIteratorImpl &RHS) const { 702 return NodePtr == RHS.NodePtr; 703 } 704 bool operator!=(const FoldingSetIteratorImpl &RHS) const { 705 return NodePtr != RHS.NodePtr; 706 } 707 }; 708 709 template <class T> class FoldingSetIterator : public FoldingSetIteratorImpl { 710 public: 711 explicit FoldingSetIterator(void **Bucket) : FoldingSetIteratorImpl(Bucket) {} 712 713 T &operator*() const { 714 return *static_cast<T*>(NodePtr); 715 } 716 717 T *operator->() const { 718 return static_cast<T*>(NodePtr); 719 } 720 721 inline FoldingSetIterator &operator++() { // Preincrement 722 advance(); 723 return *this; 724 } 725 FoldingSetIterator operator++(int) { // Postincrement 726 FoldingSetIterator tmp = *this; ++*this; return tmp; 727 } 728 }; 729 730 //===----------------------------------------------------------------------===// 731 /// FoldingSetBucketIteratorImpl - This is the common bucket iterator support 732 /// shared by all folding sets, which knows how to walk a particular bucket 733 /// of a folding set hash table. 734 class FoldingSetBucketIteratorImpl { 735 protected: 736 void *Ptr; 737 738 explicit FoldingSetBucketIteratorImpl(void **Bucket); 739 740 FoldingSetBucketIteratorImpl(void **Bucket, bool) : Ptr(Bucket) {} 741 742 void advance() { 743 void *Probe = static_cast<FoldingSetNode*>(Ptr)->getNextInBucket(); 744 uintptr_t x = reinterpret_cast<uintptr_t>(Probe) & ~0x1; 745 Ptr = reinterpret_cast<void*>(x); 746 } 747 748 public: 749 bool operator==(const FoldingSetBucketIteratorImpl &RHS) const { 750 return Ptr == RHS.Ptr; 751 } 752 bool operator!=(const FoldingSetBucketIteratorImpl &RHS) const { 753 return Ptr != RHS.Ptr; 754 } 755 }; 756 757 template <class T> 758 class FoldingSetBucketIterator : public FoldingSetBucketIteratorImpl { 759 public: 760 explicit FoldingSetBucketIterator(void **Bucket) : 761 FoldingSetBucketIteratorImpl(Bucket) {} 762 763 FoldingSetBucketIterator(void **Bucket, bool) : 764 FoldingSetBucketIteratorImpl(Bucket, true) {} 765 766 T &operator*() const { return *static_cast<T*>(Ptr); } 767 T *operator->() const { return static_cast<T*>(Ptr); } 768 769 inline FoldingSetBucketIterator &operator++() { // Preincrement 770 advance(); 771 return *this; 772 } 773 FoldingSetBucketIterator operator++(int) { // Postincrement 774 FoldingSetBucketIterator tmp = *this; ++*this; return tmp; 775 } 776 }; 777 778 //===----------------------------------------------------------------------===// 779 /// FoldingSetNodeWrapper - This template class is used to "wrap" arbitrary 780 /// types in an enclosing object so that they can be inserted into FoldingSets. 781 template <typename T> 782 class FoldingSetNodeWrapper : public FoldingSetNode { 783 T data; 784 785 public: 786 template <typename... Ts> 787 explicit FoldingSetNodeWrapper(Ts &&... Args) 788 : data(std::forward<Ts>(Args)...) {} 789 790 void Profile(FoldingSetNodeID &ID) { FoldingSetTrait<T>::Profile(data, ID); } 791 792 T &getValue() { return data; } 793 const T &getValue() const { return data; } 794 795 operator T&() { return data; } 796 operator const T&() const { return data; } 797 }; 798 799 //===----------------------------------------------------------------------===// 800 /// FastFoldingSetNode - This is a subclass of FoldingSetNode which stores 801 /// a FoldingSetNodeID value rather than requiring the node to recompute it 802 /// each time it is needed. This trades space for speed (which can be 803 /// significant if the ID is long), and it also permits nodes to drop 804 /// information that would otherwise only be required for recomputing an ID. 805 class FastFoldingSetNode : public FoldingSetNode { 806 FoldingSetNodeID FastID; 807 808 protected: 809 explicit FastFoldingSetNode(const FoldingSetNodeID &ID) : FastID(ID) {} 810 811 public: 812 void Profile(FoldingSetNodeID &ID) const { ID.AddNodeID(FastID); } 813 }; 814 815 //===----------------------------------------------------------------------===// 816 // Partial specializations of FoldingSetTrait. 817 818 template<typename T> struct FoldingSetTrait<T*> { 819 static inline void Profile(T *X, FoldingSetNodeID &ID) { 820 ID.AddPointer(X); 821 } 822 }; 823 template <typename T1, typename T2> 824 struct FoldingSetTrait<std::pair<T1, T2>> { 825 static inline void Profile(const std::pair<T1, T2> &P, 826 FoldingSetNodeID &ID) { 827 ID.Add(P.first); 828 ID.Add(P.second); 829 } 830 }; 831 832 template <typename T> 833 struct FoldingSetTrait<T, typename std::enable_if_t<std::is_enum<T>::value>> { 834 static void Profile(const T &X, FoldingSetNodeID &ID) { 835 ID.AddInteger(static_cast<typename std::underlying_type_t<T>>(X)); 836 } 837 }; 838 839 } // end namespace llvm 840 841 #endif // LLVM_ADT_FOLDINGSET_H 842