Line data Source code
1 : //===- llvm/ADT/FoldingSet.h - Uniquing Hash Set ----------------*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
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 set.
13 : //
14 : //===----------------------------------------------------------------------===//
15 :
16 : #ifndef LLVM_ADT_FOLDINGSET_H
17 : #define LLVM_ADT_FOLDINGSET_H
18 :
19 : #include "llvm/ADT/SmallVector.h"
20 : #include "llvm/ADT/iterator.h"
21 : #include "llvm/Support/Allocator.h"
22 : #include <cassert>
23 : #include <cstddef>
24 : #include <cstdint>
25 : #include <utility>
26 :
27 : namespace llvm {
28 :
29 : /// This folding set used for two purposes:
30 : /// 1. Given information about a node we want to create, look up the unique
31 : /// instance of the node in the set. If the node already exists, return
32 : /// it, otherwise return the bucket it should be inserted into.
33 : /// 2. Given a node that has already been created, remove it from the set.
34 : ///
35 : /// This class is implemented as a single-link chained hash table, where the
36 : /// "buckets" are actually the nodes themselves (the next pointer is in the
37 : /// node). The last node points back to the bucket to simplify node removal.
38 : ///
39 : /// Any node that is to be included in the folding set must be a subclass of
40 : /// FoldingSetNode. The node class must also define a Profile method used to
41 : /// establish the unique bits of data for the node. The Profile method is
42 : /// passed a FoldingSetNodeID object which is used to gather the bits. Just
43 : /// call one of the Add* functions defined in the FoldingSetBase::NodeID class.
44 : /// NOTE: That the folding set does not own the nodes and it is the
45 : /// responsibility of the user to dispose of the nodes.
46 : ///
47 : /// Eg.
48 : /// class MyNode : public FoldingSetNode {
49 : /// private:
50 : /// std::string Name;
51 : /// unsigned Value;
52 : /// public:
53 : /// MyNode(const char *N, unsigned V) : Name(N), Value(V) {}
54 : /// ...
55 : /// void Profile(FoldingSetNodeID &ID) const {
56 : /// ID.AddString(Name);
57 : /// ID.AddInteger(Value);
58 : /// }
59 : /// ...
60 : /// };
61 : ///
62 : /// To define the folding set itself use the FoldingSet template;
63 : ///
64 : /// Eg.
65 : /// FoldingSet<MyNode> MyFoldingSet;
66 : ///
67 : /// Four public methods are available to manipulate the folding set;
68 : ///
69 : /// 1) If you have an existing node that you want add to the set but unsure
70 : /// that the node might already exist then call;
71 : ///
72 : /// MyNode *M = MyFoldingSet.GetOrInsertNode(N);
73 : ///
74 : /// If The result is equal to the input then the node has been inserted.
75 : /// Otherwise, the result is the node existing in the folding set, and the
76 : /// input can be discarded (use the result instead.)
77 : ///
78 : /// 2) If you are ready to construct a node but want to check if it already
79 : /// exists, then call FindNodeOrInsertPos with a FoldingSetNodeID of the bits to
80 : /// check;
81 : ///
82 : /// FoldingSetNodeID ID;
83 : /// ID.AddString(Name);
84 : /// ID.AddInteger(Value);
85 : /// void *InsertPoint;
86 : ///
87 : /// MyNode *M = MyFoldingSet.FindNodeOrInsertPos(ID, InsertPoint);
88 : ///
89 : /// If found then M with be non-NULL, else InsertPoint will point to where it
90 : /// should be inserted using InsertNode.
91 : ///
92 : /// 3) If you get a NULL result from FindNodeOrInsertPos then you can as a new
93 : /// node with FindNodeOrInsertPos;
94 : ///
95 : /// InsertNode(N, InsertPoint);
96 : ///
97 : /// 4) Finally, if you want to remove a node from the folding set call;
98 : ///
99 : /// bool WasRemoved = RemoveNode(N);
100 : ///
101 : /// The result indicates whether the node existed in the folding set.
102 :
103 : class FoldingSetNodeID;
104 : class StringRef;
105 :
106 : //===----------------------------------------------------------------------===//
107 : /// FoldingSetBase - Implements the folding set functionality. The main
108 : /// structure is an array of buckets. Each bucket is indexed by the hash of
109 : /// the nodes it contains. The bucket itself points to the nodes contained
110 : /// in the bucket via a singly linked list. The last node in the list points
111 : /// back to the bucket to facilitate node removal.
112 : ///
113 : class FoldingSetBase {
114 : virtual void anchor(); // Out of line virtual method.
115 :
116 : protected:
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);
128 : FoldingSetBase(FoldingSetBase &&Arg);
129 : FoldingSetBase &operator=(FoldingSetBase &&RHS);
130 : ~FoldingSetBase();
131 :
132 : public:
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 401195130 : Node() = default;
143 :
144 : // Accessors
145 0 : void *getNextInBucket() const { return NextInFoldingSetBucket; }
146 344842606 : 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 0 : unsigned size() const { return NumNodes; }
154 :
155 : /// empty - Returns true if there are no nodes in the folding set.
156 3 : bool empty() const { return NumNodes == 0; }
157 :
158 : /// reserve - Increase the number of buckets such that adding the
159 : /// EltCount-th node won't cause a rebucket operation. reserve is permitted
160 : /// to allocate more space than requested by EltCount.
161 : void reserve(unsigned EltCount);
162 :
163 : /// capacity - Returns the number of nodes permitted in the folding set
164 : /// before a rebucket operation is performed.
165 0 : unsigned capacity() {
166 : // We allow a load factor of up to 2.0,
167 : // so that means our capacity is NumBuckets * 2
168 605421065 : return NumBuckets * 2;
169 : }
170 :
171 : private:
172 : /// GrowHashTable - Double the size of the hash table and rehash everything.
173 : void GrowHashTable();
174 :
175 : /// GrowBucketCount - resize the hash table and rehash everything.
176 : /// NewBucketCount must be a power of two, and must be greater than the old
177 : /// bucket count.
178 : void GrowBucketCount(unsigned NewBucketCount);
179 :
180 : protected:
181 : /// GetNodeProfile - Instantiations of the FoldingSet template implement
182 : /// this function to gather data bits for the given node.
183 : virtual void GetNodeProfile(Node *N, FoldingSetNodeID &ID) const = 0;
184 :
185 : /// NodeEquals - Instantiations of the FoldingSet template implement
186 : /// this function to compare the given node with the given ID.
187 : virtual bool NodeEquals(Node *N, const FoldingSetNodeID &ID, unsigned IDHash,
188 : FoldingSetNodeID &TempID) const=0;
189 :
190 : /// ComputeNodeHash - Instantiations of the FoldingSet template implement
191 : /// this function to compute a hash value for the given node.
192 : virtual unsigned ComputeNodeHash(Node *N, FoldingSetNodeID &TempID) const = 0;
193 :
194 : // The below methods are protected to encourage subclasses to provide a more
195 : // type-safe API.
196 :
197 : /// RemoveNode - Remove a node from the folding set, returning true if one
198 : /// was removed or false if the node was not in the folding set.
199 : bool RemoveNode(Node *N);
200 :
201 : /// GetOrInsertNode - If there is an existing simple Node exactly
202 : /// equal to the specified node, return it. Otherwise, insert 'N' and return
203 : /// it instead.
204 : Node *GetOrInsertNode(Node *N);
205 :
206 : /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists,
207 : /// return it. If not, return the insertion token that will make insertion
208 : /// faster.
209 : Node *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos);
210 :
211 : /// InsertNode - Insert the specified node into the folding set, knowing that
212 : /// it is not already in the folding set. InsertPos must be obtained from
213 : /// FindNodeOrInsertPos.
214 : void InsertNode(Node *N, void *InsertPos);
215 : };
216 :
217 : //===----------------------------------------------------------------------===//
218 :
219 : /// DefaultFoldingSetTrait - This class provides default implementations
220 : /// for FoldingSetTrait implementations.
221 : template<typename T> struct DefaultFoldingSetTrait {
222 : static void Profile(const T &X, FoldingSetNodeID &ID) {
223 3799799 : X.Profile(ID);
224 : }
225 : static void Profile(T &X, FoldingSetNodeID &ID) {
226 655601795 : X.Profile(ID);
227 : }
228 :
229 : // Equals - Test if the profile for X would match ID, using TempID
230 : // to compute a temporary ID if necessary. The default implementation
231 : // just calls Profile and does a regular comparison. Implementations
232 : // can override this to provide more efficient implementations.
233 : static inline bool Equals(T &X, const FoldingSetNodeID &ID, unsigned IDHash,
234 : FoldingSetNodeID &TempID);
235 :
236 : // ComputeHash - Compute a hash value for X, using TempID to
237 : // compute a temporary ID if necessary. The default implementation
238 : // just calls Profile and does a regular hash computation.
239 : // Implementations can override this to provide more efficient
240 : // implementations.
241 : static inline unsigned ComputeHash(T &X, FoldingSetNodeID &TempID);
242 : };
243 :
244 : /// FoldingSetTrait - This trait class is used to define behavior of how
245 : /// to "profile" (in the FoldingSet parlance) an object of a given type.
246 : /// The default behavior is to invoke a 'Profile' method on an object, but
247 : /// through template specialization the behavior can be tailored for specific
248 : /// types. Combined with the FoldingSetNodeWrapper class, one can add objects
249 : /// to FoldingSets that were not originally designed to have that behavior.
250 : template<typename T> struct FoldingSetTrait
251 : : public DefaultFoldingSetTrait<T> {};
252 :
253 : /// DefaultContextualFoldingSetTrait - Like DefaultFoldingSetTrait, but
254 : /// for ContextualFoldingSets.
255 : template<typename T, typename Ctx>
256 : struct DefaultContextualFoldingSetTrait {
257 : static void Profile(T &X, FoldingSetNodeID &ID, Ctx Context) {
258 254549254 : X.Profile(ID, Context);
259 : }
260 :
261 : static inline bool Equals(T &X, const FoldingSetNodeID &ID, unsigned IDHash,
262 : FoldingSetNodeID &TempID, Ctx Context);
263 : static inline unsigned ComputeHash(T &X, FoldingSetNodeID &TempID,
264 : Ctx Context);
265 : };
266 :
267 : /// ContextualFoldingSetTrait - Like FoldingSetTrait, but for
268 : /// ContextualFoldingSets.
269 : template<typename T, typename Ctx> struct ContextualFoldingSetTrait
270 : : public DefaultContextualFoldingSetTrait<T, Ctx> {};
271 :
272 : //===--------------------------------------------------------------------===//
273 : /// FoldingSetNodeIDRef - This class describes a reference to an interned
274 : /// FoldingSetNodeID, which can be a useful to store node id data rather
275 : /// than using plain FoldingSetNodeIDs, since the 32-element SmallVector
276 : /// is often much larger than necessary, and the possibility of heap
277 : /// allocation means it requires a non-trivial destructor call.
278 : class FoldingSetNodeIDRef {
279 : const unsigned *Data = nullptr;
280 : size_t Size = 0;
281 :
282 : public:
283 : FoldingSetNodeIDRef() = default;
284 3876123963 : FoldingSetNodeIDRef(const unsigned *D, size_t S) : Data(D), Size(S) {}
285 :
286 : /// ComputeHash - Compute a strong hash value for this FoldingSetNodeIDRef,
287 : /// used to lookup the node in the FoldingSetBase.
288 : unsigned ComputeHash() const;
289 :
290 : bool operator==(FoldingSetNodeIDRef) const;
291 :
292 : bool operator!=(FoldingSetNodeIDRef RHS) const { return !(*this == RHS); }
293 :
294 : /// Used to compare the "ordering" of two nodes as defined by the
295 : /// profiled bits and their ordering defined by memcmp().
296 : bool operator<(FoldingSetNodeIDRef) const;
297 :
298 0 : const unsigned *getData() const { return Data; }
299 0 : size_t getSize() const { return Size; }
300 : };
301 :
302 : //===--------------------------------------------------------------------===//
303 : /// FoldingSetNodeID - This class is used to gather all the unique data bits of
304 : /// a node. When all the bits are gathered this class is used to produce a
305 : /// hash value for the node.
306 60574181 : class FoldingSetNodeID {
307 : /// Bits - Vector of all the data bits that make the node unique.
308 : /// Use a SmallVector to avoid a heap allocation in the common case.
309 : SmallVector<unsigned, 32> Bits;
310 :
311 : public:
312 : FoldingSetNodeID() = default;
313 :
314 : FoldingSetNodeID(FoldingSetNodeIDRef Ref)
315 0 : : Bits(Ref.getData(), Ref.getData() + Ref.getSize()) {}
316 :
317 : /// Add* - Add various data types to Bit data.
318 : void AddPointer(const void *Ptr);
319 : void AddInteger(signed I);
320 : void AddInteger(unsigned I);
321 : void AddInteger(long I);
322 : void AddInteger(unsigned long I);
323 : void AddInteger(long long I);
324 : void AddInteger(unsigned long long I);
325 1604180432 : void AddBoolean(bool B) { AddInteger(B ? 1U : 0U); }
326 : void AddString(StringRef String);
327 : void AddNodeID(const FoldingSetNodeID &ID);
328 :
329 : template <typename T>
330 0 : inline void Add(const T &x) { FoldingSetTrait<T>::Profile(x, *this); }
331 :
332 : /// clear - Clear the accumulated profile, allowing this FoldingSetNodeID
333 : /// object to be used to compute a new profile.
334 : inline void clear() { Bits.clear(); }
335 :
336 : /// ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used
337 : /// to lookup the node in the FoldingSetBase.
338 : unsigned ComputeHash() const;
339 :
340 : /// operator== - Used to compare two nodes to each other.
341 : bool operator==(const FoldingSetNodeID &RHS) const;
342 : bool operator==(const FoldingSetNodeIDRef RHS) const;
343 :
344 179 : bool operator!=(const FoldingSetNodeID &RHS) const { return !(*this == RHS); }
345 : bool operator!=(const FoldingSetNodeIDRef RHS) const { return !(*this ==RHS);}
346 :
347 : /// Used to compare the "ordering" of two nodes as defined by the
348 : /// profiled bits and their ordering defined by memcmp().
349 : bool operator<(const FoldingSetNodeID &RHS) const;
350 : bool operator<(const FoldingSetNodeIDRef RHS) const;
351 :
352 : /// Intern - Copy this node's data to a memory region allocated from the
353 : /// given allocator and return a FoldingSetNodeIDRef describing the
354 : /// interned data.
355 : FoldingSetNodeIDRef Intern(BumpPtrAllocator &Allocator) const;
356 : };
357 :
358 : // Convenience type to hide the implementation of the folding set.
359 : using FoldingSetNode = FoldingSetBase::Node;
360 : template<class T> class FoldingSetIterator;
361 : template<class T> class FoldingSetBucketIterator;
362 :
363 : // Definitions of FoldingSetTrait and ContextualFoldingSetTrait functions, which
364 : // require the definition of FoldingSetNodeID.
365 : template<typename T>
366 : inline bool
367 0 : DefaultFoldingSetTrait<T>::Equals(T &X, const FoldingSetNodeID &ID,
368 : unsigned /*IDHash*/,
369 : FoldingSetNodeID &TempID) {
370 : FoldingSetTrait<T>::Profile(X, TempID);
371 803108476 : return TempID == ID;
372 : }
373 0 : template<typename T>
374 : inline unsigned
375 555815 : DefaultFoldingSetTrait<T>::ComputeHash(T &X, FoldingSetNodeID &TempID) {
376 : FoldingSetTrait<T>::Profile(X, TempID);
377 5011075 : return TempID.ComputeHash();
378 : }
379 0 : template<typename T, typename Ctx>
380 : inline bool
381 : DefaultContextualFoldingSetTrait<T, Ctx>::Equals(T &X,
382 : const FoldingSetNodeID &ID,
383 0 : unsigned /*IDHash*/,
384 : FoldingSetNodeID &TempID,
385 0 : Ctx Context) {
386 : ContextualFoldingSetTrait<T, Ctx>::Profile(X, TempID, Context);
387 0 : return TempID == ID;
388 : }
389 1933 : template<typename T, typename Ctx>
390 : inline unsigned
391 0 : DefaultContextualFoldingSetTrait<T, Ctx>::ComputeHash(T &X,
392 : FoldingSetNodeID &TempID,
393 0 : Ctx Context) {
394 : ContextualFoldingSetTrait<T, Ctx>::Profile(X, TempID, Context);
395 20446926 : return TempID.ComputeHash();
396 : }
397 0 :
398 : //===----------------------------------------------------------------------===//
399 : /// FoldingSetImpl - An implementation detail that lets us share code between
400 : /// FoldingSet and ContextualFoldingSet.
401 0 : template <class T> class FoldingSetImpl : public FoldingSetBase {
402 : protected:
403 1517016 : explicit FoldingSetImpl(unsigned Log2InitSize)
404 929789 : : FoldingSetBase(Log2InitSize) {}
405 0 :
406 1826 : FoldingSetImpl(FoldingSetImpl &&Arg) = default;
407 979571 : FoldingSetImpl &operator=(FoldingSetImpl &&RHS) = default;
408 936852 : ~FoldingSetImpl() = default;
409 0 :
410 : public:
411 0 : using iterator = FoldingSetIterator<T>;
412 :
413 16067 : iterator begin() { return iterator(Buckets); }
414 16324 : iterator end() { return iterator(Buckets+NumBuckets); }
415 27160 :
416 27160 : using const_iterator = FoldingSetIterator<const T>;
417 0 :
418 1406 : const_iterator begin() const { return const_iterator(Buckets); }
419 1406 : const_iterator end() const { return const_iterator(Buckets+NumBuckets); }
420 47179 :
421 455010 : using bucket_iterator = FoldingSetBucketIterator<T>;
422 164040 :
423 14 : bucket_iterator bucket_begin(unsigned hash) {
424 14 : return bucket_iterator(Buckets + (hash & (NumBuckets-1)));
425 9587 : }
426 85279 :
427 0 : bucket_iterator bucket_end(unsigned hash) {
428 14 : return bucket_iterator(Buckets + (hash & (NumBuckets-1)), true);
429 0 : }
430 :
431 10441039 : /// RemoveNode - Remove a node from the folding set, returning true if one
432 248340 : /// was removed or false if the node was not in the folding set.
433 51757482 : bool RemoveNode(T *N) { return FoldingSetBase::RemoveNode(N); }
434 7451285 :
435 0 : /// GetOrInsertNode - If there is an existing simple Node exactly
436 : /// equal to the specified node, return it. Otherwise, insert 'N' and
437 0 : /// return it instead.
438 : T *GetOrInsertNode(T *N) {
439 9014880 : return static_cast<T *>(FoldingSetBase::GetOrInsertNode(N));
440 : }
441 :
442 : /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists,
443 0 : /// return it. If not, return the insertion token that will make insertion
444 : /// faster.
445 2 : T *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos) {
446 384739016 : return static_cast<T *>(FoldingSetBase::FindNodeOrInsertPos(ID, InsertPos));
447 : }
448 :
449 0 : /// InsertNode - Insert the specified node into the folding set, knowing that
450 : /// it is not already in the folding set. InsertPos must be obtained from
451 10434 : /// FindNodeOrInsertPos.
452 : void InsertNode(T *N, void *InsertPos) {
453 114327979 : FoldingSetBase::InsertNode(N, InsertPos);
454 8 : }
455 0 :
456 : /// InsertNode - Insert the specified node into the folding set, knowing that
457 2032 : /// it is not already in the folding set.
458 66982 : void InsertNode(T *N) {
459 8 : T *Inserted = GetOrInsertNode(N);
460 : (void)Inserted;
461 0 : assert(Inserted == N && "Node already inserted!");
462 : }
463 78165 : };
464 45452881 :
465 10370 : //===----------------------------------------------------------------------===//
466 3 : /// FoldingSet - This template class is used to instantiate a specialized
467 0 : /// implementation of the folding set to the node class T. T must be a
468 39129 : /// subclass of FoldingSetNode and implement a Profile function.
469 27958 : ///
470 : /// Note that this set type is movable and move-assignable. However, its
471 15271399 : /// moved-from state is not a valid state for anything other than
472 : /// move-assigning and destroying. This is primarily to enable movable APIs
473 9760 : /// that incorporate these objects.
474 841384 : template <class T> class FoldingSet final : public FoldingSetImpl<T> {
475 0 : using Super = FoldingSetImpl<T>;
476 26977740 : using Node = typename Super::Node;
477 :
478 : /// GetNodeProfile - Each instantiatation of the FoldingSet needs to provide a
479 0 : /// way to convert nodes into a unique specifier.
480 9010876 : void GetNodeProfile(Node *N, FoldingSetNodeID &ID) const override {
481 0 : T *TN = static_cast<T *>(N);
482 0 : FoldingSetTrait<T>::Profile(*TN, ID);
483 20088216 : }
484 9010866 :
485 0 : /// NodeEquals - Instantiations may optionally provide a way to compare a
486 45985 : /// node with a specified ID.
487 42121526 : bool NodeEquals(Node *N, const FoldingSetNodeID &ID, unsigned IDHash,
488 0 : FoldingSetNodeID &TempID) const override {
489 5943991 : T *TN = static_cast<T *>(N);
490 33110666 : return FoldingSetTrait<T>::Equals(*TN, ID, IDHash, TempID);
491 0 : }
492 93204 :
493 0 : /// ComputeNodeHash - Instantiations may optionally provide a way to compute a
494 : /// hash value directly from a node.
495 128007663 : unsigned ComputeNodeHash(Node *N, FoldingSetNodeID &TempID) const override {
496 91423 : T *TN = static_cast<T *>(N);
497 4086746 : return FoldingSetTrait<T>::ComputeHash(*TN, TempID);
498 123910680 : }
499 10424 :
500 140704473 : public:
501 342563 : explicit FoldingSet(unsigned Log2InitSize = 6) : Super(Log2InitSize) {}
502 0 : FoldingSet(FoldingSet &&Arg) = default;
503 100908085 : FoldingSet &operator=(FoldingSet &&RHS) = default;
504 2 : };
505 23002629 :
506 1388847 : //===----------------------------------------------------------------------===//
507 7720448 : /// ContextualFoldingSet - This template class is a further refinement
508 23002637 : /// of FoldingSet which provides a context argument when calling
509 0 : /// Profile on its nodes. Currently, that argument is fixed at
510 1929219 : /// initialization time.
511 31980 : ///
512 10318 : /// T must be a subclass of FoldingSetNode and implement a Profile
513 3368126 : /// function with signature
514 1884370 : /// void Profile(FoldingSetNodeID &, Ctx);
515 1380788 : template <class T, class Ctx>
516 : class ContextualFoldingSet final : public FoldingSetImpl<T> {
517 205200546 : // Unfortunately, this can't derive from FoldingSet<T> because the
518 3828 : // construction of the vtable for FoldingSet<T> requires
519 119410074 : // FoldingSet<T>::GetNodeProfile to be instantiated, which in turn
520 201946736 : // requires a single-argument T::Profile().
521 4854 :
522 173910119 : using Super = FoldingSetImpl<T>;
523 29086 : using Node = typename Super::Node;
524 117784111 :
525 173912054 : Ctx Context;
526 42 :
527 14507186 : /// GetNodeProfile - Each instantiatation of the FoldingSet needs to provide a
528 1828 : /// way to convert nodes into a unique specifier.
529 141667 : void GetNodeProfile(Node *N, FoldingSetNodeID &ID) const override {
530 13918030 : T *TN = static_cast<T *>(N);
531 1979 : ContextualFoldingSetTrait<T, Ctx>::Profile(*TN, ID, Context);
532 14144132 : }
533 46 :
534 122857 : bool NodeEquals(Node *N, const FoldingSetNodeID &ID, unsigned IDHash,
535 14144132 : FoldingSetNodeID &TempID) const override {
536 : T *TN = static_cast<T *>(N);
537 18675314 : return ContextualFoldingSetTrait<T, Ctx>::Equals(*TN, ID, IDHash, TempID,
538 0 : Context);
539 15299342 : }
540 39122240 :
541 516 : unsigned ComputeNodeHash(Node *N, FoldingSetNodeID &TempID) const override {
542 23824961 : T *TN = static_cast<T *>(N);
543 0 : return ContextualFoldingSetTrait<T, Ctx>::ComputeHash(*TN, TempID, Context);
544 19823384 : }
545 3378551 :
546 19823384 : public:
547 15183366 : explicit ContextualFoldingSet(Ctx Context, unsigned Log2InitSize = 6)
548 622125 : : Super(Log2InitSize), Context(Context) {}
549 15183352 :
550 15805477 : Ctx getContext() const { return Context; }
551 0 : };
552 84486 :
553 0 : //===----------------------------------------------------------------------===//
554 84486 : /// FoldingSetVector - This template class combines a FoldingSet and a vector
555 83069 : /// to provide the interface of FoldingSet but with deterministic iteration
556 0 : /// order based on the insertion order. T must be a subclass of FoldingSetNode
557 30808 : /// and implement a Profile function.
558 126930 : template <class T, class VectorT = SmallVector<T*, 8>>
559 30804 : class FoldingSetVector {
560 30808 : FoldingSet<T> Set;
561 0 : VectorT Vector;
562 56 :
563 0 : public:
564 54 : explicit FoldingSetVector(unsigned Log2InitSize = 6) : Set(Log2InitSize) {}
565 56 :
566 0 : using iterator = pointee_iterator<typename VectorT::iterator>;
567 0 :
568 0 : iterator begin() { return Vector.begin(); }
569 0 : iterator end() { return Vector.end(); }
570 979571 :
571 847903 : using const_iterator = pointee_iterator<typename VectorT::const_iterator>;
572 979573 :
573 0 : const_iterator begin() const { return Vector.begin(); }
574 131668 : const_iterator end() const { return Vector.end(); }
575 2 :
576 131668 : /// clear - Remove all nodes from the folding set.
577 55505592 : void clear() { Set.clear(); Vector.clear(); }
578 847130 :
579 59190974 : /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists,
580 56352722 : /// return it. If not, return the insertion token that will make insertion
581 1382131 : /// faster.
582 16119709 : T *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos) {
583 0 : return Set.FindNodeOrInsertPos(ID, InsertPos);
584 13945755 : }
585 13281457 :
586 665071 : /// GetOrInsertNode - If there is an existing simple Node exactly
587 10734260 : /// equal to the specified node, return it. Otherwise, insert 'N' and
588 773 : /// return it instead.
589 11494236 : T *GetOrInsertNode(T *N) {
590 10073203 : T *Result = Set.GetOrInsertNode(N);
591 4014 : if (Result == N) Vector.push_back(N);
592 6945005 : return Result;
593 0 : }
594 5520283 :
595 5520000 : /// InsertNode - Insert the specified node into the folding set, knowing that
596 4824153 : /// it is not already in the folding set. InsertPos must be obtained from
597 14347216 : /// FindNodeOrInsertPos.
598 0 : void InsertNode(T *N, void *InsertPos) {
599 14346908 : Set.InsertNode(N, InsertPos);
600 14346901 : Vector.push_back(N);
601 10 : }
602 2031464 :
603 : /// InsertNode - Insert the specified node into the folding set, knowing that
604 2035398 : /// it is not already in the folding set.
605 2035273 : void InsertNode(T *N) {
606 3826 : Set.InsertNode(N);
607 333532 : Vector.push_back(N);
608 0 : }
609 364378 :
610 329717 : /// size - Returns the number of nodes in the folding set.
611 136 : unsigned size() const { return Set.size(); }
612 858724 :
613 0 : /// empty - Returns true if there are no nodes in the folding set.
614 823939 : bool empty() const { return Set.empty(); }
615 823927 : };
616 8 :
617 4025325 : //===----------------------------------------------------------------------===//
618 : /// FoldingSetIteratorImpl - This is the common iterator support shared by all
619 4743146 : /// folding sets, which knows how to walk the folding set hash table.
620 4026325 : class FoldingSetIteratorImpl {
621 717833 : protected:
622 5795662 : FoldingSetNode *NodePtr;
623 0 :
624 5077829 : FoldingSetIteratorImpl(void **Bucket);
625 5077829 :
626 : void advance();
627 99881419 :
628 6057 : public:
629 185853393 : bool operator==(const FoldingSetIteratorImpl &RHS) const {
630 10192699 : return NodePtr == RHS.NodePtr;
631 10227994 : }
632 10195791 : bool operator!=(const FoldingSetIteratorImpl &RHS) const {
633 35295 : return NodePtr != RHS.NodePtr;
634 1045522 : }
635 1046038 : };
636 1045522 :
637 516 : template <class T> class FoldingSetIterator : public FoldingSetIteratorImpl {
638 1640707 : public:
639 1661399 : explicit FoldingSetIterator(void **Bucket) : FoldingSetIteratorImpl(Bucket) {}
640 1640707 :
641 2958 : T &operator*() const {
642 641396 : return *static_cast<T*>(NodePtr);
643 1043027 : }
644 629518 :
645 413509 : T *operator->() const {
646 3754427 : return static_cast<T*>(NodePtr);
647 3754685 : }
648 3754427 :
649 258 : inline FoldingSetIterator &operator++() { // Preincrement
650 964068 : advance();
651 277638 : return *this;
652 277123 : }
653 515 : FoldingSetIterator operator++(int) { // Postincrement
654 28623 : FoldingSetIterator tmp = *this; ++*this; return tmp;
655 28623 : }
656 28623 : };
657 0 :
658 0 : //===----------------------------------------------------------------------===//
659 4843258 : /// FoldingSetBucketIteratorImpl - This is the common bucket iterator support
660 2965 : /// shared by all folding sets, which knows how to walk a particular bucket
661 19147 : /// of a folding set hash table.
662 390558 : class FoldingSetBucketIteratorImpl {
663 390558 : protected:
664 390558 : void *Ptr;
665 29370 :
666 2426221 : explicit FoldingSetBucketIteratorImpl(void **Bucket);
667 2426221 :
668 2426221 : FoldingSetBucketIteratorImpl(void **Bucket, bool) : Ptr(Bucket) {}
669 0 :
670 0 : void advance() {
671 17519445 : void *Probe = static_cast<FoldingSetNode*>(Ptr)->getNextInBucket();
672 2032 : uintptr_t x = reinterpret_cast<uintptr_t>(Probe) & ~0x1;
673 17519445 : Ptr = reinterpret_cast<void*>(x);
674 : }
675 18471327 :
676 : public:
677 18473826 : bool operator==(const FoldingSetBucketIteratorImpl &RHS) const {
678 : return Ptr == RHS.Ptr;
679 0 : }
680 0 : bool operator!=(const FoldingSetBucketIteratorImpl &RHS) const {
681 0 : return Ptr != RHS.Ptr;
682 0 : }
683 903 : };
684 1912328 :
685 1913231 : template <class T>
686 1912328 : class FoldingSetBucketIterator : public FoldingSetBucketIteratorImpl {
687 2002960 : public:
688 : explicit FoldingSetBucketIterator(void **Bucket) :
689 90632 : FoldingSetBucketIteratorImpl(Bucket) {}
690 0 :
691 63326914 : FoldingSetBucketIterator(void **Bucket, bool) :
692 0 : FoldingSetBucketIteratorImpl(Bucket, true) {}
693 63326914 :
694 10509 : T &operator*() const { return *static_cast<T*>(Ptr); }
695 0 : T *operator->() const { return static_cast<T*>(Ptr); }
696 248340 :
697 0 : inline FoldingSetBucketIterator &operator++() { // Preincrement
698 0 : advance();
699 2139435 : return *this;
700 1884370 : }
701 1884370 : FoldingSetBucketIterator operator++(int) { // Postincrement
702 1884370 : FoldingSetBucketIterator tmp = *this; ++*this; return tmp;
703 178255963 : }
704 36 : };
705 36 :
706 36 : //===----------------------------------------------------------------------===//
707 36 : /// FoldingSetNodeWrapper - This template class is used to "wrap" arbitrary
708 0 : /// types in an enclosing object so that they can be inserted into FoldingSets.
709 27922 : template <typename T>
710 27922 : class FoldingSetNodeWrapper : public FoldingSetNode {
711 27922 : T data;
712 27922 :
713 0 : public:
714 : template <typename... Ts>
715 2391 : explicit FoldingSetNodeWrapper(Ts &&... Args)
716 665107 : : data(std::forward<Ts>(Args)...) {}
717 :
718 11077340 : void Profile(FoldingSetNodeID &ID) { FoldingSetTrait<T>::Profile(data, ID); }
719 11077340 :
720 11081391 : T &getValue() { return data; }
721 11077340 : const T &getValue() const { return data; }
722 18340 :
723 18340 : operator T&() { return data; }
724 18340 : operator const T&() const { return data; }
725 18340 : };
726 9232257 :
727 9232257 : //===----------------------------------------------------------------------===//
728 9232257 : /// FastFoldingSetNode - This is a subclass of FoldingSetNode which stores
729 9232257 : /// a FoldingSetNodeID value rather than requiring the node to recompute it
730 182 : /// each time it is needed. This trades space for speed (which can be
731 182 : /// significant if the ID is long), and it also permits nodes to drop
732 182 : /// information that would otherwise only be required for recomputing an ID.
733 182 : class FastFoldingSetNode : public FoldingSetNode {
734 1826561 : FoldingSetNodeID FastID;
735 1826561 :
736 1826561 : protected:
737 3697539 : explicit FastFoldingSetNode(const FoldingSetNodeID &ID) : FastID(ID) {}
738 :
739 : public:
740 11649675 : void Profile(FoldingSetNodeID &ID) const { ID.AddNodeID(FastID); }
741 : };
742 :
743 76293291 : //===----------------------------------------------------------------------===//
744 : // Partial specializations of FoldingSetTrait.
745 :
746 : template<typename T> struct FoldingSetTrait<T*> {
747 8394424 : static inline void Profile(T *X, FoldingSetNodeID &ID) {
748 200046 : ID.AddPointer(X);
749 : }
750 : };
751 1595730 : template <typename T1, typename T2>
752 111330 : struct FoldingSetTrait<std::pair<T1, T2>> {
753 : static inline void Profile(const std::pair<T1, T2> &P,
754 : FoldingSetNodeID &ID) {
755 : ID.Add(P.first);
756 152000 : ID.Add(P.second);
757 : }
758 : };
759 :
760 : } // end namespace llvm
761 :
762 : #endif // LLVM_ADT_FOLDINGSET_H
|
