LLVM 17.0.0git
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/// \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"
21#include "llvm/ADT/iterator.h"
23#include <cassert>
24#include <cstddef>
25#include <cstdint>
26#include <type_traits>
27#include <utility>
28
29namespace 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
105class FoldingSetNodeID;
106class 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///
116protected:
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);
131
132public:
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
166protected:
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.
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,
175
176 /// NodeEquals - Instantiations of the FoldingSet template implement
177 /// this function to compare the given node with the given ID.
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.
185 FoldingSetNodeID &TempID);
186 };
187
188private:
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
197protected:
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.
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.
231template<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.
260template <typename T, typename Enable = void>
262
263/// DefaultContextualFoldingSetTrait - Like DefaultFoldingSetTrait, but
264/// for ContextualFoldingSets.
265template<typename T, typename Ctx>
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.
279template<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.
289 const unsigned *Data = nullptr;
290 size_t Size = 0;
291
292public:
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
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.
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.
322
323public:
324 FoldingSetNodeID() = default;
325
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); }
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.
390};
391
392// Convenience type to hide the implementation of the folding set.
394template<class T> class FoldingSetIterator;
395template<class T> class FoldingSetBucketIterator;
396
397// Definitions of FoldingSetTrait and ContextualFoldingSetTrait functions, which
398// require the definition of FoldingSetNodeID.
399template<typename T>
400inline bool
402 unsigned /*IDHash*/,
403 FoldingSetNodeID &TempID) {
405 return TempID == ID;
406}
407template<typename T>
408inline unsigned
411 return TempID.ComputeHash();
412}
413template<typename T, typename Ctx>
414inline bool
416 const FoldingSetNodeID &ID,
417 unsigned /*IDHash*/,
418 FoldingSetNodeID &TempID,
419 Ctx Context) {
421 return TempID == ID;
422}
423template<typename T, typename Ctx>
424inline unsigned
426 FoldingSetNodeID &TempID,
427 Ctx Context) {
429 return TempID.ComputeHash();
430}
431
432//===----------------------------------------------------------------------===//
433/// FoldingSetImpl - An implementation detail that lets us share code between
434/// FoldingSet and ContextualFoldingSet.
435template <class Derived, class T> class FoldingSetImpl : public FoldingSetBase {
436protected:
437 explicit FoldingSetImpl(unsigned Log2InitSize)
438 : FoldingSetBase(Log2InitSize) {}
439
442 ~FoldingSetImpl() = default;
443
444public:
446
449
451
454
456
458 return bucket_iterator(Buckets + (hash & (NumBuckets-1)));
459 }
460
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) {
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.
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.
519template <class T>
520class FoldingSet : public FoldingSetImpl<FoldingSet<T>, 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,
528 T *TN = static_cast<T *>(N);
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
556public:
557 explicit FoldingSet(unsigned Log2InitSize = 6) : Super(Log2InitSize) {}
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);
571template <class T, class Ctx>
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
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,
592 T *TN = static_cast<T *>(N);
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,
602 }
603
604 static unsigned ComputeNodeHash(const FoldingSetBase *Base, Node *N,
605 FoldingSetNodeID &TempID) {
606 T *TN = static_cast<T *>(N);
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
618public:
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.
630template <class T, class VectorT = SmallVector<T*, 8>>
632 FoldingSet<T> Set;
633 VectorT Vector;
634
635public:
636 explicit FoldingSetVector(unsigned Log2InitSize = 6) : Set(Log2InitSize) {}
637
639
640 iterator begin() { return Vector.begin(); }
641 iterator end() { return Vector.end(); }
642
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.
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.
693protected:
695
696 FoldingSetIteratorImpl(void **Bucket);
697
698 void advance();
699
700public:
702 return NodePtr == RHS.NodePtr;
703 }
705 return NodePtr != RHS.NodePtr;
706 }
707};
708
709template <class T> class FoldingSetIterator : public FoldingSetIteratorImpl {
710public:
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.
735protected:
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
748public:
750 return Ptr == RHS.Ptr;
751 }
753 return Ptr != RHS.Ptr;
754 }
755};
756
757template <class T>
759public:
760 explicit FoldingSetBucketIterator(void **Bucket) :
762
763 FoldingSetBucketIterator(void **Bucket, bool) :
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.
781template <typename T>
783 T data;
784
785public:
786 template <typename... Ts>
787 explicit FoldingSetNodeWrapper(Ts &&... Args)
788 : data(std::forward<Ts>(Args)...) {}
789
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.
806 FoldingSetNodeID FastID;
807
808protected:
809 explicit FastFoldingSetNode(const FoldingSetNodeID &ID) : FastID(ID) {}
810
811public:
812 void Profile(FoldingSetNodeID &ID) const { ID.AddNodeID(FastID); }
813};
814
815//===----------------------------------------------------------------------===//
816// Partial specializations of FoldingSetTrait.
817
818template<typename T> struct FoldingSetTrait<T*> {
819 static inline void Profile(T *X, FoldingSetNodeID &ID) {
820 ID.AddPointer(X);
821 }
822};
823template <typename T1, typename T2>
824struct FoldingSetTrait<std::pair<T1, T2>> {
825 static inline void Profile(const std::pair<T1, T2> &P,
827 ID.Add(P.first);
828 ID.Add(P.second);
829 }
830};
831
832template <typename T>
833struct FoldingSetTrait<T, std::enable_if_t<std::is_enum<T>::value>> {
834 static void Profile(const T &X, FoldingSetNodeID &ID) {
835 ID.AddInteger(static_cast<std::underlying_type_t<T>>(X));
836 }
837};
838
839} // end namespace llvm
840
841#endif // LLVM_ADT_FOLDINGSET_H
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
This file defines the BumpPtrAllocator interface.
basic Basic Alias true
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
#define I(x, y, z)
Definition: MD5.cpp:58
LLVMContext & Context
#define P(N)
Basic Register Allocator
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
Value * RHS
static unsigned getSize(unsigned Kind)
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:66
ContextualFoldingSet - This template class is a further refinement of FoldingSet which provides a con...
Definition: FoldingSet.h:573
ContextualFoldingSet(Ctx Context, unsigned Log2InitSize=6)
Definition: FoldingSet.h:619
FastFoldingSetNode - This is a subclass of FoldingSetNode which stores a FoldingSetNodeID value rathe...
Definition: FoldingSet.h:805
FastFoldingSetNode(const FoldingSetNodeID &ID)
Definition: FoldingSet.h:809
void Profile(FoldingSetNodeID &ID) const
Definition: FoldingSet.h:812
Node - This class is used to maintain the singly linked bucket list in a folding set.
Definition: FoldingSet.h:136
void * getNextInBucket() const
Definition: FoldingSet.h:145
void SetNextInBucket(void *N)
Definition: FoldingSet.h:146
FoldingSetBase - Implements the folding set functionality.
Definition: FoldingSet.h:115
void ** Buckets
Buckets - Array of bucket chains.
Definition: FoldingSet.h:118
unsigned size() const
size - Returns the number of nodes in the folding set.
Definition: FoldingSet.h:153
void reserve(unsigned EltCount, const FoldingSetInfo &Info)
reserve - Increase the number of buckets such that adding the EltCount-th node won't cause a rebucket...
Definition: FoldingSet.cpp:266
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:334
FoldingSetBase & operator=(FoldingSetBase &&RHS)
Definition: FoldingSet.cpp:198
unsigned NumBuckets
NumBuckets - Length of the Buckets array. Always a power of 2.
Definition: FoldingSet.h:121
unsigned NumNodes
NumNodes - Number of nodes in the folding set.
Definition: FoldingSet.h:125
unsigned capacity()
capacity - Returns the number of nodes permitted in the folding set before a rebucket operation is pe...
Definition: FoldingSet.h:160
Node * GetOrInsertNode(Node *N, const FoldingSetInfo &Info)
GetOrInsertNode - If there is an existing simple Node exactly equal to the specified node,...
Definition: FoldingSet.cpp:376
bool empty() const
empty - Returns true if there are no nodes in the folding set.
Definition: FoldingSet.h:156
void InsertNode(Node *N, void *InsertPos, const FoldingSetInfo &Info)
InsertNode - Insert the specified node into the folding set, knowing that it is not already in the fo...
Definition: FoldingSet.cpp:303
void clear()
clear - Remove all nodes from the folding set.
Definition: FoldingSet.cpp:213
Node * FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos, const FoldingSetInfo &Info)
FindNodeOrInsertPos - Look up the node specified by ID.
Definition: FoldingSet.cpp:278
FoldingSetBucketIteratorImpl - This is the common bucket iterator support shared by all folding sets,...
Definition: FoldingSet.h:734
FoldingSetBucketIteratorImpl(void **Bucket, bool)
Definition: FoldingSet.h:740
bool operator!=(const FoldingSetBucketIteratorImpl &RHS) const
Definition: FoldingSet.h:752
bool operator==(const FoldingSetBucketIteratorImpl &RHS) const
Definition: FoldingSet.h:749
FoldingSetBucketIterator(void **Bucket, bool)
Definition: FoldingSet.h:763
FoldingSetBucketIterator(void **Bucket)
Definition: FoldingSet.h:760
FoldingSetBucketIterator operator++(int)
Definition: FoldingSet.h:773
FoldingSetBucketIterator & operator++()
Definition: FoldingSet.h:769
FoldingSetImpl - An implementation detail that lets us share code between FoldingSet and ContextualFo...
Definition: FoldingSet.h:435
void reserve(unsigned EltCount)
reserve - Increase the number of buckets such that adding the EltCount-th node won't cause a rebucket...
Definition: FoldingSet.h:468
FoldingSetIterator< T > iterator
Definition: FoldingSet.h:445
const_iterator end() const
Definition: FoldingSet.h:453
bucket_iterator bucket_begin(unsigned hash)
Definition: FoldingSet.h:457
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:474
~FoldingSetImpl()=default
FoldingSetImpl(FoldingSetImpl &&Arg)=default
FoldingSetBucketIterator< T > bucket_iterator
Definition: FoldingSet.h:455
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:503
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:497
T * FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos)
FindNodeOrInsertPos - Look up the node specified by ID.
Definition: FoldingSet.h:489
const_iterator begin() const
Definition: FoldingSet.h:452
FoldingSetIterator< const T > const_iterator
Definition: FoldingSet.h:450
FoldingSetImpl & operator=(FoldingSetImpl &&RHS)=default
T * GetOrInsertNode(T *N)
GetOrInsertNode - If there is an existing simple Node exactly equal to the specified node,...
Definition: FoldingSet.h:481
FoldingSetImpl(unsigned Log2InitSize)
Definition: FoldingSet.h:437
bucket_iterator bucket_end(unsigned hash)
Definition: FoldingSet.h:461
FoldingSetIteratorImpl - This is the common iterator support shared by all folding sets,...
Definition: FoldingSet.h:692
FoldingSetNode * NodePtr
Definition: FoldingSet.h:694
bool operator==(const FoldingSetIteratorImpl &RHS) const
Definition: FoldingSet.h:701
bool operator!=(const FoldingSetIteratorImpl &RHS) const
Definition: FoldingSet.h:704
FoldingSetIterator(void **Bucket)
Definition: FoldingSet.h:711
FoldingSetIterator operator++(int)
Definition: FoldingSet.h:725
FoldingSetIterator & operator++()
Definition: FoldingSet.h:721
FoldingSetNodeIDRef - This class describes a reference to an interned FoldingSetNodeID,...
Definition: FoldingSet.h:288
bool operator==(FoldingSetNodeIDRef) const
Definition: FoldingSet.cpp:27
FoldingSetNodeIDRef(const unsigned *D, size_t S)
Definition: FoldingSet.h:294
bool operator<(FoldingSetNodeIDRef) const
Used to compare the "ordering" of two nodes as defined by the profiled bits and their ordering define...
Definition: FoldingSet.cpp:34
bool operator!=(FoldingSetNodeIDRef RHS) const
Definition: FoldingSet.h:304
unsigned ComputeHash() const
ComputeHash - Compute a strong hash value for this FoldingSetNodeIDRef, used to lookup the node in th...
Definition: FoldingSet.h:298
size_t getSize() const
Definition: FoldingSet.h:311
const unsigned * getData() const
Definition: FoldingSet.h:310
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
Definition: FoldingSet.h:318
FoldingSetNodeIDRef Intern(BumpPtrAllocator &Allocator) const
Intern - Copy this node's data to a memory region allocated from the given allocator and return a Fol...
Definition: FoldingSet.cpp:132
void AddInteger(signed I)
Definition: FoldingSet.h:339
void AddInteger(unsigned long I)
Definition: FoldingSet.h:342
FoldingSetNodeID(FoldingSetNodeIDRef Ref)
Definition: FoldingSet.h:326
void AddPointer(const void *Ptr)
Add* - Add various data types to Bit data.
Definition: FoldingSet.h:330
bool operator!=(const FoldingSetNodeIDRef RHS) const
Definition: FoldingSet.h:379
void clear()
clear - Clear the accumulated profile, allowing this FoldingSetNodeID object to be used to compute a ...
Definition: FoldingSet.h:366
void AddInteger(unsigned I)
Definition: FoldingSet.h:340
void AddInteger(long I)
Definition: FoldingSet.h:341
void AddBoolean(bool B)
Definition: FoldingSet.h:357
bool operator==(const FoldingSetNodeID &RHS) const
operator== - Used to compare two nodes to each other.
Definition: FoldingSet.cpp:108
bool operator!=(const FoldingSetNodeID &RHS) const
Definition: FoldingSet.h:378
void AddInteger(unsigned long long I)
Definition: FoldingSet.h:352
void AddInteger(long long I)
Definition: FoldingSet.h:351
unsigned ComputeHash() const
ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used to lookup the node in the F...
Definition: FoldingSet.h:370
bool operator<(const FoldingSetNodeID &RHS) const
Used to compare the "ordering" of two nodes as defined by the profiled bits and their ordering define...
Definition: FoldingSet.cpp:120
void AddNodeID(const FoldingSetNodeID &ID)
Definition: FoldingSet.cpp:102
void Add(const T &x)
Definition: FoldingSet.h:362
void AddString(StringRef String)
Add* - Add various data types to Bit data.
Definition: FoldingSet.cpp:45
FoldingSetNodeWrapper - This template class is used to "wrap" arbitrary types in an enclosing object ...
Definition: FoldingSet.h:782
FoldingSetNodeWrapper(Ts &&... Args)
Definition: FoldingSet.h:787
const T & getValue() const
Definition: FoldingSet.h:793
void Profile(FoldingSetNodeID &ID)
Definition: FoldingSet.h:790
FoldingSetVector - This template class combines a FoldingSet and a vector to provide the interface of...
Definition: FoldingSet.h:631
T * GetOrInsertNode(T *N)
GetOrInsertNode - If there is an existing simple Node exactly equal to the specified node,...
Definition: FoldingSet.h:661
const_iterator end() const
Definition: FoldingSet.h:646
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:677
T * FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos)
FindNodeOrInsertPos - Look up the node specified by ID.
Definition: FoldingSet.h:654
unsigned size() const
size - Returns the number of nodes in the folding set.
Definition: FoldingSet.h:683
void clear()
clear - Remove all nodes from the folding set.
Definition: FoldingSet.h:649
bool empty() const
empty - Returns true if there are no nodes in the folding set.
Definition: FoldingSet.h:686
FoldingSetVector(unsigned Log2InitSize=6)
Definition: FoldingSet.h:636
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:670
const_iterator begin() const
Definition: FoldingSet.h:645
FoldingSet - This template class is used to instantiate a specialized implementation of the folding s...
Definition: FoldingSet.h:520
FoldingSet(FoldingSet &&Arg)=default
FoldingSet(unsigned Log2InitSize=6)
Definition: FoldingSet.h:557
FoldingSet & operator=(FoldingSet &&RHS)=default
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Ref
The access may reference the value stored in memory.
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
Definition: Hashing.h:486
Definition: BitVector.h:851
#define N
ContextualFoldingSetTrait - Like FoldingSetTrait, but for ContextualFoldingSets.
Definition: FoldingSet.h:280
DefaultContextualFoldingSetTrait - Like DefaultFoldingSetTrait, but for ContextualFoldingSets.
Definition: FoldingSet.h:266
static bool Equals(T &X, const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID, Ctx Context)
Definition: FoldingSet.h:415
static void Profile(T &X, FoldingSetNodeID &ID, Ctx Context)
Definition: FoldingSet.h:267
static unsigned ComputeHash(T &X, FoldingSetNodeID &TempID, Ctx Context)
Definition: FoldingSet.h:425
DefaultFoldingSetTrait - This class provides default implementations for FoldingSetTrait implementati...
Definition: FoldingSet.h:231
static void Profile(const T &X, FoldingSetNodeID &ID)
Definition: FoldingSet.h:232
static unsigned ComputeHash(T &X, FoldingSetNodeID &TempID)
Definition: FoldingSet.h:409
static bool Equals(T &X, const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID)
Definition: FoldingSet.h:401
static void Profile(T &X, FoldingSetNodeID &ID)
Definition: FoldingSet.h:235
Functions provided by the derived class to compute folding properties.
Definition: FoldingSet.h:170
unsigned(* ComputeNodeHash)(const FoldingSetBase *Self, Node *N, FoldingSetNodeID &TempID)
ComputeNodeHash - Instantiations of the FoldingSet template implement this function to compute a hash...
Definition: FoldingSet.h:184
bool(* NodeEquals)(const FoldingSetBase *Self, Node *N, const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID)
NodeEquals - Instantiations of the FoldingSet template implement this function to compare the given n...
Definition: FoldingSet.h:178
void(* GetNodeProfile)(const FoldingSetBase *Self, Node *N, FoldingSetNodeID &ID)
GetNodeProfile - Instantiations of the FoldingSet template implement this function to gather data bit...
Definition: FoldingSet.h:173
static void Profile(const T &X, FoldingSetNodeID &ID)
Definition: FoldingSet.h:834
static void Profile(T *X, FoldingSetNodeID &ID)
Definition: FoldingSet.h:819
static void Profile(const std::pair< T1, T2 > &P, FoldingSetNodeID &ID)
Definition: FoldingSet.h:825
FoldingSetTrait - This trait class is used to define behavior of how to "profile" (in the FoldingSet ...
Definition: FoldingSet.h:261
An iterator type that allows iterating over the pointees via some other iterator.
Definition: iterator.h:324