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