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