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