LLVM  10.0.0svn
FoldingSet.h
Go to the documentation of this file.
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 with 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 as a new
92 /// node with FindNodeOrInsertPos;
93 ///
94 /// InsertNode(N, InsertPoint);
95 ///
96 /// 4) Finally, if you want to remove a node from the folding set call;
97 ///
98 /// bool WasRemoved = RemoveNode(N);
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 ///
113  virtual void anchor(); // Out of line virtual method.
114 
115 protected:
116  /// Buckets - Array of bucket chains.
117  void **Buckets;
118 
119  /// NumBuckets - Length of the Buckets array. Always a power of 2.
120  unsigned NumBuckets;
121 
122  /// NumNodes - Number of nodes in the folding set. Growth occurs when NumNodes
123  /// is greater than twice the number of buckets.
124  unsigned NumNodes;
125 
126  explicit FoldingSetBase(unsigned Log2InitSize = 6);
129  ~FoldingSetBase();
130 
131 public:
132  //===--------------------------------------------------------------------===//
133  /// Node - This class is used to maintain the singly linked bucket list in
134  /// a folding set.
135  class Node {
136  private:
137  // NextInFoldingSetBucket - next link in the bucket list.
138  void *NextInFoldingSetBucket = nullptr;
139 
140  public:
141  Node() = default;
142 
143  // Accessors
144  void *getNextInBucket() const { return NextInFoldingSetBucket; }
145  void SetNextInBucket(void *N) { NextInFoldingSetBucket = N; }
146  };
147 
148  /// clear - Remove all nodes from the folding set.
149  void clear();
150 
151  /// size - Returns the number of nodes in the folding set.
152  unsigned size() const { return NumNodes; }
153 
154  /// empty - Returns true if there are no nodes in the folding set.
155  bool empty() const { return NumNodes == 0; }
156 
157  /// reserve - Increase the number of buckets such that adding the
158  /// EltCount-th node won't cause a rebucket operation. reserve is permitted
159  /// to allocate more space than requested by EltCount.
160  void reserve(unsigned EltCount);
161 
162  /// capacity - Returns the number of nodes permitted in the folding set
163  /// before a rebucket operation is performed.
164  unsigned capacity() {
165  // We allow a load factor of up to 2.0,
166  // so that means our capacity is NumBuckets * 2
167  return NumBuckets * 2;
168  }
169 
170 private:
171  /// GrowHashTable - Double the size of the hash table and rehash everything.
172  void GrowHashTable();
173 
174  /// GrowBucketCount - resize the hash table and rehash everything.
175  /// NewBucketCount must be a power of two, and must be greater than the old
176  /// bucket count.
177  void GrowBucketCount(unsigned NewBucketCount);
178 
179 protected:
180  /// GetNodeProfile - Instantiations of the FoldingSet template implement
181  /// this function to gather data bits for the given node.
182  virtual void GetNodeProfile(Node *N, FoldingSetNodeID &ID) const = 0;
183 
184  /// NodeEquals - Instantiations of the FoldingSet template implement
185  /// this function to compare the given node with the given ID.
186  virtual bool NodeEquals(Node *N, const FoldingSetNodeID &ID, unsigned IDHash,
187  FoldingSetNodeID &TempID) const=0;
188 
189  /// ComputeNodeHash - Instantiations of the FoldingSet template implement
190  /// this function to compute a hash value for the given node.
191  virtual unsigned ComputeNodeHash(Node *N, FoldingSetNodeID &TempID) const = 0;
192 
193  // The below methods are protected to encourage subclasses to provide a more
194  // type-safe API.
195 
196  /// RemoveNode - Remove a node from the folding set, returning true if one
197  /// was removed or false if the node was not in the folding set.
198  bool RemoveNode(Node *N);
199 
200  /// GetOrInsertNode - If there is an existing simple Node exactly
201  /// equal to the specified node, return it. Otherwise, insert 'N' and return
202  /// it instead.
204 
205  /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists,
206  /// return it. If not, return the insertion token that will make insertion
207  /// faster.
208  Node *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos);
209 
210  /// InsertNode - Insert the specified node into the folding set, knowing that
211  /// it is not already in the folding set. InsertPos must be obtained from
212  /// FindNodeOrInsertPos.
213  void InsertNode(Node *N, void *InsertPos);
214 };
215 
216 //===----------------------------------------------------------------------===//
217 
218 /// DefaultFoldingSetTrait - This class provides default implementations
219 /// for FoldingSetTrait implementations.
220 template<typename T> struct DefaultFoldingSetTrait {
221  static void Profile(const T &X, FoldingSetNodeID &ID) {
222  X.Profile(ID);
223  }
224  static void Profile(T &X, FoldingSetNodeID &ID) {
225  X.Profile(ID);
226  }
227 
228  // Equals - Test if the profile for X would match ID, using TempID
229  // to compute a temporary ID if necessary. The default implementation
230  // just calls Profile and does a regular comparison. Implementations
231  // can override this to provide more efficient implementations.
232  static inline bool Equals(T &X, const FoldingSetNodeID &ID, unsigned IDHash,
233  FoldingSetNodeID &TempID);
234 
235  // ComputeHash - Compute a hash value for X, using TempID to
236  // compute a temporary ID if necessary. The default implementation
237  // just calls Profile and does a regular hash computation.
238  // Implementations can override this to provide more efficient
239  // implementations.
240  static inline unsigned ComputeHash(T &X, FoldingSetNodeID &TempID);
241 };
242 
243 /// FoldingSetTrait - This trait class is used to define behavior of how
244 /// to "profile" (in the FoldingSet parlance) an object of a given type.
245 /// The default behavior is to invoke a 'Profile' method on an object, but
246 /// through template specialization the behavior can be tailored for specific
247 /// types. Combined with the FoldingSetNodeWrapper class, one can add objects
248 /// to FoldingSets that were not originally designed to have that behavior.
249 template<typename T> struct FoldingSetTrait
250  : public DefaultFoldingSetTrait<T> {};
251 
252 /// DefaultContextualFoldingSetTrait - Like DefaultFoldingSetTrait, but
253 /// for ContextualFoldingSets.
254 template<typename T, typename Ctx>
256  static void Profile(T &X, FoldingSetNodeID &ID, Ctx Context) {
257  X.Profile(ID, Context);
258  }
259 
260  static inline bool Equals(T &X, const FoldingSetNodeID &ID, unsigned IDHash,
261  FoldingSetNodeID &TempID, Ctx Context);
262  static inline unsigned ComputeHash(T &X, FoldingSetNodeID &TempID,
263  Ctx Context);
264 };
265 
266 /// ContextualFoldingSetTrait - Like FoldingSetTrait, but for
267 /// ContextualFoldingSets.
268 template<typename T, typename Ctx> struct ContextualFoldingSetTrait
269  : public DefaultContextualFoldingSetTrait<T, Ctx> {};
270 
271 //===--------------------------------------------------------------------===//
272 /// FoldingSetNodeIDRef - This class describes a reference to an interned
273 /// FoldingSetNodeID, which can be a useful to store node id data rather
274 /// than using plain FoldingSetNodeIDs, since the 32-element SmallVector
275 /// is often much larger than necessary, and the possibility of heap
276 /// allocation means it requires a non-trivial destructor call.
278  const unsigned *Data = nullptr;
279  size_t Size = 0;
280 
281 public:
282  FoldingSetNodeIDRef() = default;
283  FoldingSetNodeIDRef(const unsigned *D, size_t S) : Data(D), Size(S) {}
284 
285  /// ComputeHash - Compute a strong hash value for this FoldingSetNodeIDRef,
286  /// used to lookup the node in the FoldingSetBase.
287  unsigned ComputeHash() const;
288 
289  bool operator==(FoldingSetNodeIDRef) const;
290 
291  bool operator!=(FoldingSetNodeIDRef RHS) const { return !(*this == RHS); }
292 
293  /// Used to compare the "ordering" of two nodes as defined by the
294  /// profiled bits and their ordering defined by memcmp().
295  bool operator<(FoldingSetNodeIDRef) const;
296 
297  const unsigned *getData() const { return Data; }
298  size_t getSize() const { return Size; }
299 };
300 
301 //===--------------------------------------------------------------------===//
302 /// FoldingSetNodeID - This class is used to gather all the unique data bits of
303 /// a node. When all the bits are gathered this class is used to produce a
304 /// hash value for the node.
306  /// Bits - Vector of all the data bits that make the node unique.
307  /// Use a SmallVector to avoid a heap allocation in the common case.
309 
310 public:
311  FoldingSetNodeID() = default;
312 
314  : Bits(Ref.getData(), Ref.getData() + Ref.getSize()) {}
315 
316  /// Add* - Add various data types to Bit data.
317  void AddPointer(const void *Ptr);
318  void AddInteger(signed I);
319  void AddInteger(unsigned I);
320  void AddInteger(long I);
321  void AddInteger(unsigned long I);
322  void AddInteger(long long I);
323  void AddInteger(unsigned long long I);
324  void AddBoolean(bool B) { AddInteger(B ? 1U : 0U); }
325  void AddString(StringRef String);
326  void AddNodeID(const FoldingSetNodeID &ID);
327 
328  template <typename T>
329  inline void Add(const T &x) { FoldingSetTrait<T>::Profile(x, *this); }
330 
331  /// clear - Clear the accumulated profile, allowing this FoldingSetNodeID
332  /// object to be used to compute a new profile.
333  inline void clear() { Bits.clear(); }
334 
335  /// ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used
336  /// to lookup the node in the FoldingSetBase.
337  unsigned ComputeHash() const;
338 
339  /// operator== - Used to compare two nodes to each other.
340  bool operator==(const FoldingSetNodeID &RHS) const;
341  bool operator==(const FoldingSetNodeIDRef RHS) const;
342 
343  bool operator!=(const FoldingSetNodeID &RHS) const { return !(*this == RHS); }
344  bool operator!=(const FoldingSetNodeIDRef RHS) const { return !(*this ==RHS);}
345 
346  /// Used to compare the "ordering" of two nodes as defined by the
347  /// profiled bits and their ordering defined by memcmp().
348  bool operator<(const FoldingSetNodeID &RHS) const;
349  bool operator<(const FoldingSetNodeIDRef RHS) const;
350 
351  /// Intern - Copy this node's data to a memory region allocated from the
352  /// given allocator and return a FoldingSetNodeIDRef describing the
353  /// interned data.
355 };
356 
357 // Convenience type to hide the implementation of the folding set.
359 template<class T> class FoldingSetIterator;
360 template<class T> class FoldingSetBucketIterator;
361 
362 // Definitions of FoldingSetTrait and ContextualFoldingSetTrait functions, which
363 // require the definition of FoldingSetNodeID.
364 template<typename T>
365 inline bool
367  unsigned /*IDHash*/,
368  FoldingSetNodeID &TempID) {
369  FoldingSetTrait<T>::Profile(X, TempID);
370  return TempID == ID;
371 }
372 template<typename T>
373 inline unsigned
375  FoldingSetTrait<T>::Profile(X, TempID);
376  return TempID.ComputeHash();
377 }
378 template<typename T, typename Ctx>
379 inline bool
381  const FoldingSetNodeID &ID,
382  unsigned /*IDHash*/,
383  FoldingSetNodeID &TempID,
384  Ctx Context) {
385  ContextualFoldingSetTrait<T, Ctx>::Profile(X, TempID, Context);
386  return TempID == ID;
387 }
388 template<typename T, typename Ctx>
389 inline unsigned
391  FoldingSetNodeID &TempID,
392  Ctx Context) {
393  ContextualFoldingSetTrait<T, Ctx>::Profile(X, TempID, Context);
394  return TempID.ComputeHash();
395 }
396 
397 //===----------------------------------------------------------------------===//
398 /// FoldingSetImpl - An implementation detail that lets us share code between
399 /// FoldingSet and ContextualFoldingSet.
400 template <class T> class FoldingSetImpl : public FoldingSetBase {
401 protected:
402  explicit FoldingSetImpl(unsigned Log2InitSize)
403  : FoldingSetBase(Log2InitSize) {}
404 
405  FoldingSetImpl(FoldingSetImpl &&Arg) = default;
406  FoldingSetImpl &operator=(FoldingSetImpl &&RHS) = default;
407  ~FoldingSetImpl() = default;
408 
409 public:
411 
414 
416 
419 
421 
422  bucket_iterator bucket_begin(unsigned hash) {
423  return bucket_iterator(Buckets + (hash & (NumBuckets-1)));
424  }
425 
426  bucket_iterator bucket_end(unsigned hash) {
427  return bucket_iterator(Buckets + (hash & (NumBuckets-1)), true);
428  }
429 
430  /// RemoveNode - Remove a node from the folding set, returning true if one
431  /// was removed or false if the node was not in the folding set.
432  bool RemoveNode(T *N) { return FoldingSetBase::RemoveNode(N); }
433 
434  /// GetOrInsertNode - If there is an existing simple Node exactly
435  /// equal to the specified node, return it. Otherwise, insert 'N' and
436  /// return it instead.
438  return static_cast<T *>(FoldingSetBase::GetOrInsertNode(N));
439  }
440 
441  /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists,
442  /// return it. If not, return the insertion token that will make insertion
443  /// faster.
444  T *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos) {
445  return static_cast<T *>(FoldingSetBase::FindNodeOrInsertPos(ID, InsertPos));
446  }
447 
448  /// InsertNode - Insert the specified node into the folding set, knowing that
449  /// it is not already in the folding set. InsertPos must be obtained from
450  /// FindNodeOrInsertPos.
451  void InsertNode(T *N, void *InsertPos) {
452  FoldingSetBase::InsertNode(N, InsertPos);
453  }
454 
455  /// InsertNode - Insert the specified node into the folding set, knowing that
456  /// it is not already in the folding set.
457  void InsertNode(T *N) {
458  T *Inserted = GetOrInsertNode(N);
459  (void)Inserted;
460  assert(Inserted == N && "Node already inserted!");
461  }
462 };
463 
464 //===----------------------------------------------------------------------===//
465 /// FoldingSet - This template class is used to instantiate a specialized
466 /// implementation of the folding set to the node class T. T must be a
467 /// subclass of FoldingSetNode and implement a Profile function.
468 ///
469 /// Note that this set type is movable and move-assignable. However, its
470 /// moved-from state is not a valid state for anything other than
471 /// move-assigning and destroying. This is primarily to enable movable APIs
472 /// that incorporate these objects.
473 template <class T> class FoldingSet final : public FoldingSetImpl<T> {
474  using Super = FoldingSetImpl<T>;
475  using Node = typename Super::Node;
476 
477  /// GetNodeProfile - Each instantiatation of the FoldingSet needs to provide a
478  /// way to convert nodes into a unique specifier.
479  void GetNodeProfile(Node *N, FoldingSetNodeID &ID) const override {
480  T *TN = static_cast<T *>(N);
482  }
483 
484  /// NodeEquals - Instantiations may optionally provide a way to compare a
485  /// node with a specified ID.
486  bool NodeEquals(Node *N, const FoldingSetNodeID &ID, unsigned IDHash,
487  FoldingSetNodeID &TempID) const override {
488  T *TN = static_cast<T *>(N);
489  return FoldingSetTrait<T>::Equals(*TN, ID, IDHash, TempID);
490  }
491 
492  /// ComputeNodeHash - Instantiations may optionally provide a way to compute a
493  /// hash value directly from a node.
494  unsigned ComputeNodeHash(Node *N, FoldingSetNodeID &TempID) const override {
495  T *TN = static_cast<T *>(N);
496  return FoldingSetTrait<T>::ComputeHash(*TN, TempID);
497  }
498 
499 public:
500  explicit FoldingSet(unsigned Log2InitSize = 6) : Super(Log2InitSize) {}
501  FoldingSet(FoldingSet &&Arg) = default;
502  FoldingSet &operator=(FoldingSet &&RHS) = default;
503 };
504 
505 //===----------------------------------------------------------------------===//
506 /// ContextualFoldingSet - This template class is a further refinement
507 /// of FoldingSet which provides a context argument when calling
508 /// Profile on its nodes. Currently, that argument is fixed at
509 /// initialization time.
510 ///
511 /// T must be a subclass of FoldingSetNode and implement a Profile
512 /// function with signature
513 /// void Profile(FoldingSetNodeID &, Ctx);
514 template <class T, class Ctx>
515 class ContextualFoldingSet final : public FoldingSetImpl<T> {
516  // Unfortunately, this can't derive from FoldingSet<T> because the
517  // construction of the vtable for FoldingSet<T> requires
518  // FoldingSet<T>::GetNodeProfile to be instantiated, which in turn
519  // requires a single-argument T::Profile().
520 
521  using Super = FoldingSetImpl<T>;
522  using Node = typename Super::Node;
523 
524  Ctx Context;
525 
526  /// GetNodeProfile - Each instantiatation of the FoldingSet needs to provide a
527  /// way to convert nodes into a unique specifier.
528  void GetNodeProfile(Node *N, FoldingSetNodeID &ID) const override {
529  T *TN = static_cast<T *>(N);
531  }
532 
533  bool NodeEquals(Node *N, const FoldingSetNodeID &ID, unsigned IDHash,
534  FoldingSetNodeID &TempID) const override {
535  T *TN = static_cast<T *>(N);
536  return ContextualFoldingSetTrait<T, Ctx>::Equals(*TN, ID, IDHash, TempID,
537  Context);
538  }
539 
540  unsigned ComputeNodeHash(Node *N, FoldingSetNodeID &TempID) const override {
541  T *TN = static_cast<T *>(N);
542  return ContextualFoldingSetTrait<T, Ctx>::ComputeHash(*TN, TempID, Context);
543  }
544 
545 public:
546  explicit ContextualFoldingSet(Ctx Context, unsigned Log2InitSize = 6)
547  : Super(Log2InitSize), Context(Context) {}
548 
549  Ctx getContext() const { return Context; }
550 };
551 
552 //===----------------------------------------------------------------------===//
553 /// FoldingSetVector - This template class combines a FoldingSet and a vector
554 /// to provide the interface of FoldingSet but with deterministic iteration
555 /// order based on the insertion order. T must be a subclass of FoldingSetNode
556 /// and implement a Profile function.
557 template <class T, class VectorT = SmallVector<T*, 8>>
559  FoldingSet<T> Set;
560  VectorT Vector;
561 
562 public:
563  explicit FoldingSetVector(unsigned Log2InitSize = 6) : Set(Log2InitSize) {}
564 
566 
567  iterator begin() { return Vector.begin(); }
568  iterator end() { return Vector.end(); }
569 
571 
572  const_iterator begin() const { return Vector.begin(); }
573  const_iterator end() const { return Vector.end(); }
574 
575  /// clear - Remove all nodes from the folding set.
576  void clear() { Set.clear(); Vector.clear(); }
577 
578  /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists,
579  /// return it. If not, return the insertion token that will make insertion
580  /// faster.
581  T *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos) {
582  return Set.FindNodeOrInsertPos(ID, InsertPos);
583  }
584 
585  /// GetOrInsertNode - If there is an existing simple Node exactly
586  /// equal to the specified node, return it. Otherwise, insert 'N' and
587  /// return it instead.
589  T *Result = Set.GetOrInsertNode(N);
590  if (Result == N) Vector.push_back(N);
591  return Result;
592  }
593 
594  /// InsertNode - Insert the specified node into the folding set, knowing that
595  /// it is not already in the folding set. InsertPos must be obtained from
596  /// FindNodeOrInsertPos.
597  void InsertNode(T *N, void *InsertPos) {
598  Set.InsertNode(N, InsertPos);
599  Vector.push_back(N);
600  }
601 
602  /// InsertNode - Insert the specified node into the folding set, knowing that
603  /// it is not already in the folding set.
604  void InsertNode(T *N) {
605  Set.InsertNode(N);
606  Vector.push_back(N);
607  }
608 
609  /// size - Returns the number of nodes in the folding set.
610  unsigned size() const { return Set.size(); }
611 
612  /// empty - Returns true if there are no nodes in the folding set.
613  bool empty() const { return Set.empty(); }
614 };
615 
616 //===----------------------------------------------------------------------===//
617 /// FoldingSetIteratorImpl - This is the common iterator support shared by all
618 /// folding sets, which knows how to walk the folding set hash table.
620 protected:
622 
623  FoldingSetIteratorImpl(void **Bucket);
624 
625  void advance();
626 
627 public:
628  bool operator==(const FoldingSetIteratorImpl &RHS) const {
629  return NodePtr == RHS.NodePtr;
630  }
631  bool operator!=(const FoldingSetIteratorImpl &RHS) const {
632  return NodePtr != RHS.NodePtr;
633  }
634 };
635 
636 template <class T> class FoldingSetIterator : public FoldingSetIteratorImpl {
637 public:
638  explicit FoldingSetIterator(void **Bucket) : FoldingSetIteratorImpl(Bucket) {}
639 
640  T &operator*() const {
641  return *static_cast<T*>(NodePtr);
642  }
643 
644  T *operator->() const {
645  return static_cast<T*>(NodePtr);
646  }
647 
648  inline FoldingSetIterator &operator++() { // Preincrement
649  advance();
650  return *this;
651  }
652  FoldingSetIterator operator++(int) { // Postincrement
653  FoldingSetIterator tmp = *this; ++*this; return tmp;
654  }
655 };
656 
657 //===----------------------------------------------------------------------===//
658 /// FoldingSetBucketIteratorImpl - This is the common bucket iterator support
659 /// shared by all folding sets, which knows how to walk a particular bucket
660 /// of a folding set hash table.
662 protected:
663  void *Ptr;
664 
665  explicit FoldingSetBucketIteratorImpl(void **Bucket);
666 
667  FoldingSetBucketIteratorImpl(void **Bucket, bool) : Ptr(Bucket) {}
668 
669  void advance() {
670  void *Probe = static_cast<FoldingSetNode*>(Ptr)->getNextInBucket();
671  uintptr_t x = reinterpret_cast<uintptr_t>(Probe) & ~0x1;
672  Ptr = reinterpret_cast<void*>(x);
673  }
674 
675 public:
676  bool operator==(const FoldingSetBucketIteratorImpl &RHS) const {
677  return Ptr == RHS.Ptr;
678  }
679  bool operator!=(const FoldingSetBucketIteratorImpl &RHS) const {
680  return Ptr != RHS.Ptr;
681  }
682 };
683 
684 template <class T>
686 public:
687  explicit FoldingSetBucketIterator(void **Bucket) :
689 
690  FoldingSetBucketIterator(void **Bucket, bool) :
692 
693  T &operator*() const { return *static_cast<T*>(Ptr); }
694  T *operator->() const { return static_cast<T*>(Ptr); }
695 
696  inline FoldingSetBucketIterator &operator++() { // Preincrement
697  advance();
698  return *this;
699  }
700  FoldingSetBucketIterator operator++(int) { // Postincrement
701  FoldingSetBucketIterator tmp = *this; ++*this; return tmp;
702  }
703 };
704 
705 //===----------------------------------------------------------------------===//
706 /// FoldingSetNodeWrapper - This template class is used to "wrap" arbitrary
707 /// types in an enclosing object so that they can be inserted into FoldingSets.
708 template <typename T>
710  T data;
711 
712 public:
713  template <typename... Ts>
714  explicit FoldingSetNodeWrapper(Ts &&... Args)
715  : data(std::forward<Ts>(Args)...) {}
716 
718 
719  T &getValue() { return data; }
720  const T &getValue() const { return data; }
721 
722  operator T&() { return data; }
723  operator const T&() const { return data; }
724 };
725 
726 //===----------------------------------------------------------------------===//
727 /// FastFoldingSetNode - This is a subclass of FoldingSetNode which stores
728 /// a FoldingSetNodeID value rather than requiring the node to recompute it
729 /// each time it is needed. This trades space for speed (which can be
730 /// significant if the ID is long), and it also permits nodes to drop
731 /// information that would otherwise only be required for recomputing an ID.
733  FoldingSetNodeID FastID;
734 
735 protected:
736  explicit FastFoldingSetNode(const FoldingSetNodeID &ID) : FastID(ID) {}
737 
738 public:
739  void Profile(FoldingSetNodeID &ID) const { ID.AddNodeID(FastID); }
740 };
741 
742 //===----------------------------------------------------------------------===//
743 // Partial specializations of FoldingSetTrait.
744 
745 template<typename T> struct FoldingSetTrait<T*> {
746  static inline void Profile(T *X, FoldingSetNodeID &ID) {
747  ID.AddPointer(X);
748  }
749 };
750 template <typename T1, typename T2>
751 struct FoldingSetTrait<std::pair<T1, T2>> {
752  static inline void Profile(const std::pair<T1, T2> &P,
753  FoldingSetNodeID &ID) {
754  ID.Add(P.first);
755  ID.Add(P.second);
756  }
757 };
758 
759 } // end namespace llvm
760 
761 #endif // LLVM_ADT_FOLDINGSET_H
size_t getSize() const
Definition: FoldingSet.h:298
FoldingSetVector - This template class combines a FoldingSet and a vector to provide the interface of...
Definition: FoldingSet.h:558
void AddPointer(const void *Ptr)
Add* - Add various data types to Bit data.
Definition: FoldingSet.cpp:51
FoldingSetNodeIDRef(const unsigned *D, size_t S)
Definition: FoldingSet.h:283
const T & getValue() const
Definition: FoldingSet.h:720
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
bool empty() const
empty - Returns true if there are no nodes in the folding set.
Definition: FoldingSet.h:155
LLVMContext & Context
void clear()
clear - Remove all nodes from the folding set.
Definition: FoldingSet.cpp:258
void reserve(unsigned EltCount)
reserve - Increase the number of buckets such that adding the EltCount-th node won&#39;t cause a rebucket...
Definition: FoldingSet.cpp:308
This class represents lattice values for constants.
Definition: AllocatorList.h:23
unsigned NumBuckets
NumBuckets - Length of the Buckets array. Always a power of 2.
Definition: FoldingSet.h:120
ContextualFoldingSet(Ctx Context, unsigned Log2InitSize=6)
Definition: FoldingSet.h:546
FastFoldingSetNode - This is a subclass of FoldingSetNode which stores a FoldingSetNodeID value rathe...
Definition: FoldingSet.h:732
T * FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos)
FindNodeOrInsertPos - Look up the node specified by ID.
Definition: FoldingSet.h:444
FastFoldingSetNode(const FoldingSetNodeID &ID)
Definition: FoldingSet.h:736
FoldingSetNodeWrapper(Ts &&... Args)
Definition: FoldingSet.h:714
const_iterator begin() const
Definition: FoldingSet.h:572
void Profile(FoldingSetNodeID &ID) const
Definition: FoldingSet.h:739
block Block Frequency true
unsigned capacity()
capacity - Returns the number of nodes permitted in the folding set before a rebucket operation is pe...
Definition: FoldingSet.h:164
static void Profile(const T &X, FoldingSetNodeID &ID)
Definition: FoldingSet.h:221
unsigned ComputeHash() const
ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used to lookup the node in the F...
Definition: FoldingSet.cpp:145
This file defines the MallocAllocator and BumpPtrAllocator interfaces.
const_iterator end() const
Definition: FoldingSet.h:418
FoldingSet(unsigned Log2InitSize=6)
Definition: FoldingSet.h:500
const_iterator begin() const
Definition: FoldingSet.h:417
virtual bool NodeEquals(Node *N, const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID) const =0
NodeEquals - Instantiations of the FoldingSet template implement this function to compare the given n...
bool operator!=(const FoldingSetIteratorImpl &RHS) const
Definition: FoldingSet.h:631
Definition: BitVector.h:937
bool operator!=(const FoldingSetBucketIteratorImpl &RHS) const
Definition: FoldingSet.h:679
static void Profile(T *X, FoldingSetNodeID &ID)
Definition: FoldingSet.h:746
ContextualFoldingSetTrait - Like FoldingSetTrait, but for ContextualFoldingSets.
Definition: FoldingSet.h:268
static unsigned ComputeHash(T &X, FoldingSetNodeID &TempID)
Definition: FoldingSet.h:374
The access may reference the value stored in memory.
FoldingSetIteratorImpl - This is the common iterator support shared by all folding sets...
Definition: FoldingSet.h:619
void InsertNode(T *N, void *InsertPos)
InsertNode - Insert the specified node into the folding set, knowing that it is not already in the fo...
Definition: FoldingSet.h:451
Node * GetOrInsertNode(Node *N)
GetOrInsertNode - If there is an existing simple Node exactly equal to the specified node...
Definition: FoldingSet.cpp:416
void InsertNode(Node *N, void *InsertPos)
InsertNode - Insert the specified node into the folding set, knowing that it is not already in the fo...
Definition: FoldingSet.cpp:346
void InsertNode(T *N)
InsertNode - Insert the specified node into the folding set, knowing that it is not already in the fo...
Definition: FoldingSet.h:457
void Profile(FoldingSetNodeID &ID)
Definition: FoldingSet.h:717
void clear()
clear - Remove all nodes from the folding set.
Definition: FoldingSet.h:576
FoldingSetImpl(unsigned Log2InitSize)
Definition: FoldingSet.h:402
bool operator!=(FoldingSetNodeIDRef RHS) const
Definition: FoldingSet.h:291
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
Definition: FoldingSet.h:305
#define P(N)
void SetNextInBucket(void *N)
Definition: FoldingSet.h:145
FoldingSetTrait - This trait class is used to define behavior of how to "profile" (in the FoldingSet ...
Definition: FoldingSet.h:249
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
void AddNodeID(const FoldingSetNodeID &ID)
Definition: FoldingSet.cpp:139
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:140
static unsigned ComputeHash(T &X, FoldingSetNodeID &TempID, Ctx Context)
Definition: FoldingSet.h:390
FoldingSetNode * NodePtr
Definition: FoldingSet.h:621
void AddBoolean(bool B)
Definition: FoldingSet.h:324
T * FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos)
FindNodeOrInsertPos - Look up the node specified by ID.
Definition: FoldingSet.h:581
FoldingSetBucketIterator operator++(int)
Definition: FoldingSet.h:700
void * getNextInBucket() const
Definition: FoldingSet.h:144
Node * FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos)
FindNodeOrInsertPos - Look up the node specified by ID.
Definition: FoldingSet.cpp:321
FoldingSetImpl - An implementation detail that lets us share code between FoldingSet and ContextualFo...
Definition: FoldingSet.h:400
T * GetOrInsertNode(T *N)
GetOrInsertNode - If there is an existing simple Node exactly equal to the specified node...
Definition: FoldingSet.h:437
FoldingSetIterator operator++(int)
Definition: FoldingSet.h:652
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
bool operator!=(const FoldingSetNodeIDRef RHS) const
Definition: FoldingSet.h:344
FoldingSetBucketIterator & operator++()
Definition: FoldingSet.h:696
void InsertNode(T *N, void *InsertPos)
InsertNode - Insert the specified node into the folding set, knowing that it is not already in the fo...
Definition: FoldingSet.h:597
uint64_t ComputeHash(StringRef K)
Definition: InstrProf.h:988
void ** Buckets
Buckets - Array of bucket chains.
Definition: FoldingSet.h:117
FoldingSetVector(unsigned Log2InitSize=6)
Definition: FoldingSet.h:563
FoldingSet - This template class is used to instantiate a specialized implementation of the folding s...
Definition: FoldingSet.h:473
unsigned NumNodes
NumNodes - Number of nodes in the folding set.
Definition: FoldingSet.h:124
static bool Equals(T &X, const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID)
Definition: FoldingSet.h:366
bucket_iterator bucket_end(unsigned hash)
Definition: FoldingSet.h:426
void Add(const T &x)
Definition: FoldingSet.h:329
FoldingSetNodeWrapper - This template class is used to "wrap" arbitrary types in an enclosing object ...
Definition: FoldingSet.h:709
void InsertNode(T *N)
InsertNode - Insert the specified node into the folding set, knowing that it is not already in the fo...
Definition: FoldingSet.h:604
Basic Register Allocator
FoldingSetNodeID(FoldingSetNodeIDRef Ref)
Definition: FoldingSet.h:313
FoldingSetBase(unsigned Log2InitSize=6)
Definition: FoldingSet.cpp:228
void clear()
clear - Clear the accumulated profile, allowing this FoldingSetNodeID object to be used to compute a ...
Definition: FoldingSet.h:333
virtual void GetNodeProfile(Node *N, FoldingSetNodeID &ID) const =0
GetNodeProfile - Instantiations of the FoldingSet template implement this function to gather data bit...
FoldingSetBucketIterator(void **Bucket)
Definition: FoldingSet.h:687
const_iterator end() const
Definition: FoldingSet.h:573
FoldingSetBucketIterator(void **Bucket, bool)
Definition: FoldingSet.h:690
An iterator type that allows iterating over the pointees via some other iterator. ...
Definition: iterator.h:286
ContextualFoldingSet - This template class is a further refinement of FoldingSet which provides a con...
Definition: FoldingSet.h:515
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
FoldingSetIterator & operator++()
Definition: FoldingSet.h:648
unsigned size() const
size - Returns the number of nodes in the folding set.
Definition: FoldingSet.h:610
FoldingSetBase - Implements the folding set functionality.
Definition: FoldingSet.h:112
static void Profile(T &X, FoldingSetNodeID &ID)
Definition: FoldingSet.h:224
T * GetOrInsertNode(T *N)
GetOrInsertNode - If there is an existing simple Node exactly equal to the specified node...
Definition: FoldingSet.h:588
FoldingSetNodeIDRef - This class describes a reference to an interned FoldingSetNodeID, which can be a useful to store node id data rather than using plain FoldingSetNodeIDs, since the 32-element SmallVector is often much larger than necessary, and the possibility of heap allocation means it requires a non-trivial destructor call.
Definition: FoldingSet.h:277
Node - This class is used to maintain the singly linked bucket list in a folding set.
Definition: FoldingSet.h:135
bool operator==(const FoldingSetBucketIteratorImpl &RHS) const
Definition: FoldingSet.h:676
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
bool operator!=(const FoldingSetNodeID &RHS) const
Definition: FoldingSet.h:343
uint32_t Size
Definition: Profile.cpp:46
bucket_iterator bucket_begin(unsigned hash)
Definition: FoldingSet.h:422
virtual unsigned ComputeNodeHash(Node *N, FoldingSetNodeID &TempID) const =0
ComputeNodeHash - Instantiations of the FoldingSet template implement this function to compute a hash...
bool empty() const
empty - Returns true if there are no nodes in the folding set.
Definition: FoldingSet.h:613
bool RemoveNode(Node *N)
RemoveNode - Remove a node from the folding set, returning true if one was removed or false if the no...
Definition: FoldingSet.cpp:375
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
DefaultContextualFoldingSetTrait - Like DefaultFoldingSetTrait, but for ContextualFoldingSets.
Definition: FoldingSet.h:255
bool operator<(int64_t V1, const APSInt &V2)
Definition: APSInt.h:343
bool RemoveNode(T *N)
RemoveNode - Remove a node from the folding set, returning true if one was removed or false if the no...
Definition: FoldingSet.h:432
DefaultFoldingSetTrait - This class provides default implementations for FoldingSetTrait implementati...
Definition: FoldingSet.h:220
FoldingSetIterator(void **Bucket)
Definition: FoldingSet.h:638
static void Profile(const std::pair< T1, T2 > &P, FoldingSetNodeID &ID)
Definition: FoldingSet.h:752
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1973
bool operator==(const FoldingSetIteratorImpl &RHS) const
Definition: FoldingSet.h:628
FoldingSetBase & operator=(FoldingSetBase &&RHS)
Definition: FoldingSet.cpp:243
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
FoldingSetBucketIteratorImpl(void **Bucket, bool)
Definition: FoldingSet.h:667
unsigned size() const
size - Returns the number of nodes in the folding set.
Definition: FoldingSet.h:152
FoldingSetBucketIteratorImpl - This is the common bucket iterator support shared by all folding sets...
Definition: FoldingSet.h:661
static void Profile(T &X, FoldingSetNodeID &ID, Ctx Context)
Definition: FoldingSet.h:256
static bool Equals(T &X, const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID, Ctx Context)
Definition: FoldingSet.h:380
const unsigned * getData() const
Definition: FoldingSet.h:297