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