LLVM: include/llvm/ADT/FoldingSet.h Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16#ifndef LLVM_ADT_FOLDINGSET_H
17#define LLVM_ADT_FOLDINGSET_H
18
26#include
27#include
28#include
29#include <type_traits>
30#include
31
32namespace llvm {
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
110
111
112
113
114
115
116
117
119protected:
120
122
123
125
126
127
129
134
135public:
136
137
138
140 private:
141
142 void *NextInFoldingSetBucket = nullptr;
143
144 public:
146
147
150 };
151
152
154
155
157
158
160
161
162
168
169protected:
170
171
172
174
175
178
179
180
184
185
186
189 };
190
191private:
192
194
195
196
197
198 void GrowBucketCount(unsigned NewBucketCount, const FoldingSetInfo &Info);
199
200protected:
201
202
203
204
205
206
208
209
210
212
213
214
215
217
218
219
220
222 void *&InsertPos,
224
225
226
227
230};
231
232
233
234
235
243
244
245
246
247
250
251
252
253
254
255
257};
258
259
260
261
262
263
264
265template <typename T, typename Enable = void>
267
268
269
270template<typename T, typename Ctx>
274 }
275
279 Ctx Context);
280};
281
282
283
286
287
288
289
290
291
292
294 const unsigned *Data = nullptr;
295 size_t Size = 0;
296
297public:
300
301
302
306
307
308
311 reinterpret_cast<const uint8_t *>(Data), sizeof(unsigned) * Size)));
312 }
313
315
317
318
319
321
322 const unsigned *getData() const { return Data; }
323 size_t getSize() const { return Size; }
324};
325
326
327
328
329
331
332
334
335 template void AddIntegerImpl(T I) {
336 static_assert(std::is_integral_v && sizeof(T) <= sizeof(unsigned) * 2,
337 "T must be an integer type no wider than 64 bits");
338 Bits.push_back(static_cast<unsigned>(I));
339 if constexpr (sizeof(unsigned) < sizeof(T))
340 Bits.push_back(static_cast<unsigned long long>(I) >> 32);
341 }
342
343public:
345
348
349
351
352
353
354
355 static_assert(sizeof(uintptr_t) <= sizeof(unsigned long long),
356 "unexpected pointer size");
357 AddInteger(reinterpret_cast<uintptr_t>(Ptr));
358 }
364 void AddInteger(unsigned long long I) { AddIntegerImpl(I); }
368
369 template
371
372
373
374 inline void clear() { Bits.clear(); }
375
376
377
378
382
383
384
388
389
392
395
396
397
400
401
402
403
405};
406
407
411
412
413
414template
415inline bool
417 unsigned ,
420 return TempID == ID;
421}
422template
423inline unsigned
428template<typename T, typename Ctx>
429inline bool
432 unsigned ,
434 Ctx Context) {
436 return TempID == ID;
437}
438template<typename T, typename Ctx>
439inline unsigned
446
447
448
449
451protected:
454
458
459public:
461
464
466
469
471
475
479
480
481
482
486
487
488
492
493
494
495
497 return static_cast<T *>(
499 }
500
501
502
503
506 ID, InsertPos, Derived::getFoldingSetInfo()));
507 }
508
509
510
511
515
516
517
520 (void)Inserted;
521 assert(Inserted == N && "Node already inserted!");
522 }
523};
524
525
526
527
528
529
530
531
532
533
534template
538
539
540
541 static void GetNodeProfile(const FoldingSetBase *, Node *N,
543 T *TN = static_cast<T *>(N);
545 }
546
547
548
552 T *TN = static_cast<T *>(N);
554 }
555
556
557
558 static unsigned ComputeNodeHash(const FoldingSetBase *, Node *N,
560 T *TN = static_cast<T *>(N);
562 }
563
566 GetNodeProfile, NodeEquals, ComputeNodeHash};
568 }
569 friend Super;
570
571public:
572 explicit FoldingSet(unsigned Log2InitSize = 6) : Super(Log2InitSize) {}
575};
576
577
578
579
580
581
582
583
584
585
586template <class T, class Ctx>
588 : public FoldingSetImpl<ContextualFoldingSet<T, Ctx>, T> {
589
590
591
592
593
596
597 Ctx Context;
598
601 }
602
603
604
607 T *TN = static_cast<T *>(N);
609 }
610
614 T *TN = static_cast<T *>(N);
617 }
618
621 T *TN = static_cast<T *>(N);
624 }
625
628 GetNodeProfile, NodeEquals, ComputeNodeHash};
630 }
631 friend Super;
632
633public:
635 : Super(Log2InitSize), Context(Context) {}
636
638};
639
640
641
642
643
644
645template <class T, class VectorT = SmallVector<T*, 8>>
648 VectorT Vector;
649
650public:
651 explicit FoldingSetVector(unsigned Log2InitSize = 6) : Set(Log2InitSize) {}
652
654
657
659
662
663
664 void clear() { Set.clear(); Vector.clear(); }
665
666
667
668
670 return Set.FindNodeOrInsertPos(ID, InsertPos);
671 }
672
673
674
675
677 T *Result = Set.GetOrInsertNode(N);
678 if (Result == N) Vector.push_back(N);
679 return Result;
680 }
681
682
683
684
686 Set.InsertNode(N, InsertPos);
687 Vector.push_back(N);
688 }
689
690
691
693 Set.InsertNode(N);
694 Vector.push_back(N);
695 }
696
697
698 unsigned size() const { return Set.size(); }
699
700
701 bool empty() const { return Set.empty(); }
702};
703
704
705
706
708protected:
710
712
714
715public:
722};
723
725public:
727
729 return *static_cast<T*>(NodePtr);
730 }
731
733 return static_cast<T*>(NodePtr);
734 }
735
743};
744
745
746
747
748
750protected:
752
754
756
758 void *Probe = static_cast<FoldingSetNode*>(Ptr)->getNextInBucket();
759 uintptr_t x = reinterpret_cast<uintptr_t>(Probe) & ~0x1;
760 Ptr = reinterpret_cast<void*>(x);
761 }
762
763public:
766 }
769 }
770};
771
772template
774public:
777
780
783
791};
792
793
794
795
796template
798 T data;
799
800public:
801 template <typename... Ts>
803 : data(std::forward(Args)...) {}
804
806
809
810 operator T&() { return data; }
811 operator const T&() const { return data; }
812};
813
814
815
816
817
818
819
822
823protected:
825
826public:
828};
829
830
831
832
836 }
837};
838template <typename T1, typename T2>
840 static inline void Profile(const std::pair<T1, T2> &P,
844 }
845};
846
847template
853
854}
855
856#endif
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file defines the BumpPtrAllocator interface.
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
Analysis containing CSE Info
This file contains library features backported from future STL versions.
This file defines the SmallVector class.
static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")
static unsigned getSize(unsigned Kind)
Ctx getContext() const
Definition FoldingSet.h:637
ContextualFoldingSet(Ctx Context, unsigned Log2InitSize=6)
Definition FoldingSet.h:634
FastFoldingSetNode(const FoldingSetNodeID &ID)
Definition FoldingSet.h:824
void Profile(FoldingSetNodeID &ID) const
Definition FoldingSet.h:827
Node - This class is used to maintain the singly linked bucket list in a folding set.
Definition FoldingSet.h:139
void * getNextInBucket() const
Definition FoldingSet.h:148
void SetNextInBucket(void *N)
Definition FoldingSet.h:149
FoldingSetBase - Implements the folding set functionality.
Definition FoldingSet.h:118
LLVM_ABI FoldingSetBase(unsigned Log2InitSize=6)
void ** Buckets
Buckets - Array of bucket chains.
Definition FoldingSet.h:121
unsigned size() const
size - Returns the number of nodes in the folding set.
Definition FoldingSet.h:156
LLVM_ABI 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...
LLVM_ABI bool RemoveNode(Node *N)
RemoveNode - Remove a node from the folding set, returning true if one was removed or false if the no...
LLVM_ABI FoldingSetBase & operator=(FoldingSetBase &&RHS)
LLVM_ABI ~FoldingSetBase()
unsigned NumBuckets
NumBuckets - Length of the Buckets array. Always a power of 2.
Definition FoldingSet.h:124
unsigned NumNodes
NumNodes - Number of nodes in the folding set.
Definition FoldingSet.h:128
unsigned capacity()
capacity - Returns the number of nodes permitted in the folding set before a rebucket operation is pe...
Definition FoldingSet.h:163
LLVM_ABI Node * GetOrInsertNode(Node *N, const FoldingSetInfo &Info)
GetOrInsertNode - If there is an existing simple Node exactly equal to the specified node,...
bool empty() const
empty - Returns true if there are no nodes in the folding set.
Definition FoldingSet.h:159
LLVM_ABI 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...
LLVM_ABI void clear()
clear - Remove all nodes from the folding set.
LLVM_ABI Node * FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos, const FoldingSetInfo &Info)
FindNodeOrInsertPos - Look up the node specified by ID.
void * Ptr
Definition FoldingSet.h:751
LLVM_ABI FoldingSetBucketIteratorImpl(void **Bucket)
FoldingSetBucketIteratorImpl(void **Bucket, bool)
Definition FoldingSet.h:755
bool operator!=(const FoldingSetBucketIteratorImpl &RHS) const
Definition FoldingSet.h:767
void advance()
Definition FoldingSet.h:757
bool operator==(const FoldingSetBucketIteratorImpl &RHS) const
Definition FoldingSet.h:764
Definition FoldingSet.h:773
T * operator->() const
Definition FoldingSet.h:782
FoldingSetBucketIterator(void **Bucket, bool)
Definition FoldingSet.h:778
FoldingSetBucketIterator(void **Bucket)
Definition FoldingSet.h:775
FoldingSetBucketIterator operator++(int)
Definition FoldingSet.h:788
T & operator*() const
Definition FoldingSet.h:781
FoldingSetBucketIterator & operator++()
Definition FoldingSet.h:784
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:483
FoldingSetIterator< T > iterator
Definition FoldingSet.h:460
const_iterator end() const
Definition FoldingSet.h:468
bucket_iterator bucket_begin(unsigned hash)
Definition FoldingSet.h:472
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:489
~FoldingSetImpl()=default
FoldingSetImpl(FoldingSetImpl &&Arg)=default
iterator begin()
Definition FoldingSet.h:462
FoldingSetBucketIterator< T > bucket_iterator
Definition FoldingSet.h:470
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:518
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:512
T * FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos)
FindNodeOrInsertPos - Look up the node specified by ID.
Definition FoldingSet.h:504
const_iterator begin() const
Definition FoldingSet.h:467
FoldingSetIterator< const T > const_iterator
Definition FoldingSet.h:465
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:496
FoldingSetImpl(unsigned Log2InitSize)
Definition FoldingSet.h:452
iterator end()
Definition FoldingSet.h:463
bucket_iterator bucket_end(unsigned hash)
Definition FoldingSet.h:476
FoldingSetNode * NodePtr
Definition FoldingSet.h:709
LLVM_ABI FoldingSetIteratorImpl(void **Bucket)
bool operator==(const FoldingSetIteratorImpl &RHS) const
Definition FoldingSet.h:716
bool operator!=(const FoldingSetIteratorImpl &RHS) const
Definition FoldingSet.h:719
Definition FoldingSet.h:724
T * operator->() const
Definition FoldingSet.h:732
T & operator*() const
Definition FoldingSet.h:728
FoldingSetIterator(void **Bucket)
Definition FoldingSet.h:726
FoldingSetIterator operator++(int)
Definition FoldingSet.h:740
FoldingSetIterator & operator++()
Definition FoldingSet.h:736
FoldingSetNodeIDRef - This class describes a reference to an interned FoldingSetNodeID,...
Definition FoldingSet.h:293
unsigned computeStableHash() const
Definition FoldingSet.h:309
LLVM_ABI bool operator==(FoldingSetNodeIDRef) const
FoldingSetNodeIDRef(const unsigned *D, size_t S)
Definition FoldingSet.h:299
LLVM_ABI bool operator<(FoldingSetNodeIDRef) const
Used to compare the "ordering" of two nodes as defined by the profiled bits and their ordering define...
bool operator!=(FoldingSetNodeIDRef RHS) const
Definition FoldingSet.h:316
unsigned ComputeHash() const
Definition FoldingSet.h:303
FoldingSetNodeIDRef()=default
size_t getSize() const
Definition FoldingSet.h:323
const unsigned * getData() const
Definition FoldingSet.h:322
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
Definition FoldingSet.h:330
LLVM_ABI FoldingSetNodeIDRef Intern(BumpPtrAllocator &Allocator) const
Intern - Copy this node's data to a memory region allocated from the given allocator and return a Fol...
void AddInteger(signed I)
Definition FoldingSet.h:359
void AddInteger(unsigned long I)
Definition FoldingSet.h:362
FoldingSetNodeID(FoldingSetNodeIDRef Ref)
Definition FoldingSet.h:346
unsigned computeStableHash() const
Definition FoldingSet.h:385
void AddPointer(const void *Ptr)
Add* - Add various data types to Bit data.
Definition FoldingSet.h:350
bool operator!=(const FoldingSetNodeIDRef RHS) const
Definition FoldingSet.h:394
void clear()
clear - Clear the accumulated profile, allowing this FoldingSetNodeID object to be used to compute a ...
Definition FoldingSet.h:374
void AddInteger(unsigned I)
Definition FoldingSet.h:360
FoldingSetNodeID()=default
void AddInteger(long I)
Definition FoldingSet.h:361
void AddBoolean(bool B)
Definition FoldingSet.h:365
LLVM_ABI bool operator==(const FoldingSetNodeID &RHS) const
operator== - Used to compare two nodes to each other.
bool operator!=(const FoldingSetNodeID &RHS) const
Definition FoldingSet.h:393
void AddInteger(unsigned long long I)
Definition FoldingSet.h:364
void AddInteger(long long I)
Definition FoldingSet.h:363
unsigned ComputeHash() const
Definition FoldingSet.h:379
LLVM_ABI bool operator<(const FoldingSetNodeID &RHS) const
Used to compare the "ordering" of two nodes as defined by the profiled bits and their ordering define...
LLVM_ABI void AddNodeID(const FoldingSetNodeID &ID)
void Add(const T &x)
Definition FoldingSet.h:370
LLVM_ABI void AddString(StringRef String)
Add* - Add various data types to Bit data.
FoldingSetNodeWrapper(Ts &&... Args)
Definition FoldingSet.h:802
T & getValue()
Definition FoldingSet.h:807
const T & getValue() const
Definition FoldingSet.h:808
void Profile(FoldingSetNodeID &ID)
Definition FoldingSet.h:805
iterator begin()
Definition FoldingSet.h:655
iterator end()
Definition FoldingSet.h:656
T * GetOrInsertNode(T *N)
GetOrInsertNode - If there is an existing simple Node exactly equal to the specified node,...
Definition FoldingSet.h:676
const_iterator end() const
Definition FoldingSet.h:661
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:692
T * FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos)
FindNodeOrInsertPos - Look up the node specified by ID.
Definition FoldingSet.h:669
unsigned size() const
size - Returns the number of nodes in the folding set.
Definition FoldingSet.h:698
pointee_iterator< typename VectorT::const_iterator > const_iterator
Definition FoldingSet.h:658
pointee_iterator< typename VectorT::iterator > iterator
Definition FoldingSet.h:653
void clear()
clear - Remove all nodes from the folding set.
Definition FoldingSet.h:664
bool empty() const
empty - Returns true if there are no nodes in the folding set.
Definition FoldingSet.h:701
FoldingSetVector(unsigned Log2InitSize=6)
Definition FoldingSet.h:651
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:685
const_iterator begin() const
Definition FoldingSet.h:660
FoldingSet - This template class is used to instantiate a specialized implementation of the folding s...
Definition FoldingSet.h:535
FoldingSet(FoldingSet &&Arg)=default
FoldingSet(unsigned Log2InitSize=6)
Definition FoldingSet.h:572
FoldingSet & operator=(FoldingSet &&RHS)=default
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef - Represent a constant reference to a string, i.e.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
This is an optimization pass for GlobalISel generic memory operations.
LLVM_ABI uint64_t xxh3_64bits(ArrayRef< uint8_t > data)
FoldingSetBase::Node FoldingSetNode
Definition FoldingSet.h:408
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.
ArrayRef(const T &OneElt) -> ArrayRef< T >
BumpPtrAllocatorImpl<> BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
Implement std::hash so that hash_code can be used in STL containers.
ContextualFoldingSetTrait - Like FoldingSetTrait, but for ContextualFoldingSets.
Definition FoldingSet.h:285
DefaultContextualFoldingSetTrait - Like DefaultFoldingSetTrait, but for ContextualFoldingSets.
Definition FoldingSet.h:271
static bool Equals(T &X, const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID, Ctx Context)
Definition FoldingSet.h:430
static void Profile(T &X, FoldingSetNodeID &ID, Ctx Context)
Definition FoldingSet.h:272
static unsigned ComputeHash(T &X, FoldingSetNodeID &TempID, Ctx Context)
Definition FoldingSet.h:440
DefaultFoldingSetTrait - This class provides default implementations for FoldingSetTrait implementati...
Definition FoldingSet.h:236
static void Profile(const T &X, FoldingSetNodeID &ID)
Definition FoldingSet.h:237
static unsigned ComputeHash(T &X, FoldingSetNodeID &TempID)
Definition FoldingSet.h:424
static bool Equals(T &X, const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID)
Definition FoldingSet.h:416
static void Profile(T &X, FoldingSetNodeID &ID)
Definition FoldingSet.h:240
Functions provided by the derived class to compute folding properties.
Definition FoldingSet.h:173
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:187
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:181
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:176
static void Profile(const T &X, FoldingSetNodeID &ID)
Definition FoldingSet.h:849
static void Profile(T *X, FoldingSetNodeID &ID)
Definition FoldingSet.h:834
static void Profile(const std::pair< T1, T2 > &P, FoldingSetNodeID &ID)
Definition FoldingSet.h:840
FoldingSetTrait - This trait class is used to define behavior of how to "profile" (in the FoldingSet ...
Definition FoldingSet.h:266
An iterator type that allows iterating over the pointees via some other iterator.