LLVM  16.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"
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 ///
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);
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,
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.
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>
262 
263 /// DefaultContextualFoldingSetTrait - Like DefaultFoldingSetTrait, but
264 /// for ContextualFoldingSets.
265 template<typename T, typename Ctx>
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.
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(Data, 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.
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.
322 
323 public:
324  FoldingSetNodeID() = default;
325 
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(reinterpret_cast<uintptr_t>(Ptr));
338  }
339  void AddInteger(signed I) { Bits.push_back(I); }
340  void AddInteger(unsigned I) { Bits.push_back(I); }
341  void AddInteger(long I) { AddInteger((unsigned long)I); }
342  void AddInteger(unsigned long I) {
343  if (sizeof(long) == sizeof(int))
344  AddInteger(unsigned(I));
345  else if (sizeof(long) == sizeof(long long)) {
346  AddInteger((unsigned long long)I);
347  } else {
348  llvm_unreachable("unexpected sizeof(long)");
349  }
350  }
351  void AddInteger(long long I) { AddInteger((unsigned long long)I); }
352  void AddInteger(unsigned long long I) {
353  AddInteger(unsigned(I));
354  AddInteger(unsigned(I >> 32));
355  }
356 
357  void AddBoolean(bool B) { AddInteger(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.
390 };
391 
392 // Convenience type to hide the implementation of the folding set.
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
402  unsigned /*IDHash*/,
403  FoldingSetNodeID &TempID) {
405  return TempID == ID;
406 }
407 template<typename T>
408 inline unsigned
411  return TempID.ComputeHash();
412 }
413 template<typename T, typename Ctx>
414 inline bool
416  const FoldingSetNodeID &ID,
417  unsigned /*IDHash*/,
418  FoldingSetNodeID &TempID,
419  Ctx Context) {
421  return TempID == ID;
422 }
423 template<typename T, typename Ctx>
424 inline unsigned
426  FoldingSetNodeID &TempID,
427  Ctx 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;
442  ~FoldingSetImpl() = default;
443 
444 public:
446 
449 
451 
454 
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, 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) {
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.
482  return static_cast<T *>(
483  FoldingSetBase::GetOrInsertNode(N, 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, 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, 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> {
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);
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>
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 
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);
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);
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>>
632  FoldingSet<T> Set;
633  VectorT Vector;
634 
635 public:
636  explicit FoldingSetVector(unsigned Log2InitSize = 6) : Set(Log2InitSize) {}
637 
639 
640  iterator begin() { return Vector.begin(); }
641  iterator end() { return Vector.end(); }
642 
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.
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.
693 protected:
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.
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:
750  return Ptr == RHS.Ptr;
751  }
753  return Ptr != RHS.Ptr;
754  }
755 };
756 
757 template <class T>
758 class FoldingSetBucketIterator : public FoldingSetBucketIteratorImpl {
759 public:
760  explicit FoldingSetBucketIterator(void **Bucket) :
762 
763  FoldingSetBucketIterator(void **Bucket, bool) :
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>
783  T data;
784 
785 public:
786  template <typename... Ts>
787  explicit FoldingSetNodeWrapper(Ts &&... Args)
788  : data(std::forward<Ts>(Args)...) {}
789 
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.
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(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(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
llvm::FoldingSetVector::InsertNode
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:670
llvm::FoldingSetImpl::operator=
FoldingSetImpl & operator=(FoldingSetImpl &&RHS)=default
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::FoldingSetBase::~FoldingSetBase
~FoldingSetBase()
Definition: FoldingSet.cpp:209
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:818
llvm::FoldingSetBase::Buckets
void ** Buckets
Buckets - Array of bucket chains.
Definition: FoldingSet.h:118
llvm::FoldingSetBucketIteratorImpl::FoldingSetBucketIteratorImpl
FoldingSetBucketIteratorImpl(void **Bucket)
Definition: FoldingSet.cpp:422
llvm::FoldingSetImpl::GetOrInsertNode
T * GetOrInsertNode(T *N)
GetOrInsertNode - If there is an existing simple Node exactly equal to the specified node,...
Definition: FoldingSet.h:481
llvm::FoldingSetNodeID::operator<
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
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::FoldingSetImpl::~FoldingSetImpl
~FoldingSetImpl()=default
llvm::FoldingSetImpl
FoldingSetImpl - An implementation detail that lets us share code between FoldingSet and ContextualFo...
Definition: FoldingSet.h:435
llvm::FoldingSetBucketIteratorImpl::operator==
bool operator==(const FoldingSetBucketIteratorImpl &RHS) const
Definition: FoldingSet.h:749
llvm::FoldingSetBase::FoldingSetInfo::NodeEquals
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:178
llvm::FoldingSetImpl::InsertNode
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:497
llvm::SmallVector< unsigned, 32 >
llvm::FoldingSetNodeID::AddInteger
void AddInteger(long long I)
Definition: FoldingSet.h:351
llvm::FoldingSetBase::FoldingSetInfo::GetNodeProfile
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:173
llvm::DefaultContextualFoldingSetTrait::Profile
static void Profile(T &X, FoldingSetNodeID &ID, Ctx Context)
Definition: FoldingSet.h:267
Allocator.h
llvm::FoldingSetImpl::bucket_iterator
FoldingSetBucketIterator< T > bucket_iterator
Definition: FoldingSet.h:455
llvm::FoldingSetNodeID::AddInteger
void AddInteger(long I)
Definition: FoldingSet.h:341
llvm::FoldingSetNodeID::AddInteger
void AddInteger(unsigned long long I)
Definition: FoldingSet.h:352
llvm::ContextualFoldingSet::ContextualFoldingSet
ContextualFoldingSet(Ctx Context, unsigned Log2InitSize=6)
Definition: FoldingSet.h:619
llvm::FoldingSetImpl::FindNodeOrInsertPos
T * FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos)
FindNodeOrInsertPos - Look up the node specified by ID.
Definition: FoldingSet.h:489
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1793
llvm::FoldingSetVector::FindNodeOrInsertPos
T * FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos)
FindNodeOrInsertPos - Look up the node specified by ID.
Definition: FoldingSet.h:654
llvm::FoldingSetImpl::iterator
FoldingSetIterator< T > iterator
Definition: FoldingSet.h:445
llvm::FoldingSetNodeWrapper::FoldingSetNodeWrapper
FoldingSetNodeWrapper(Ts &&... Args)
Definition: FoldingSet.h:787
llvm::FoldingSetNodeIDRef::operator<
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
Vector
So we should use XX3Form_Rcr to implement intrinsic Convert DP outs ins xscvdpsp No builtin are required Round &Convert QP DP(dword[1] is set to zero) No builtin are required Round to Quad Precision because you need to assign rounding mode in instruction Provide builtin(set f128:$vT,(int_ppc_vsx_xsrqpi f128:$vB))(set f128 yields< n x< ty > >< result > yields< ty >< result > No builtin are required Load Store Vector
Definition: README_P9.txt:497
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::FoldingSetNodeIDRef::operator==
bool operator==(FoldingSetNodeIDRef) const
Definition: FoldingSet.cpp:27
Hashing.h
llvm::FoldingSetBase::NumNodes
unsigned NumNodes
NumNodes - Number of nodes in the folding set.
Definition: FoldingSet.h:125
llvm::FoldingSetBase::FoldingSetInfo
Functions provided by the derived class to compute folding properties.
Definition: FoldingSet.h:170
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::FoldingSetNodeID::operator==
bool operator==(const FoldingSetNodeID &RHS) const
operator== - Used to compare two nodes to each other.
Definition: FoldingSet.cpp:108
tmp
alloca< 16 x float >, align 16 %tmp2=alloca< 16 x float >, align 16 store< 16 x float > %A,< 16 x float > *%tmp %s=bitcast< 16 x float > *%tmp to i8 *%s2=bitcast< 16 x float > *%tmp2 to i8 *call void @llvm.memcpy.i64(i8 *%s, i8 *%s2, i64 64, i32 16) %R=load< 16 x float > *%tmp2 ret< 16 x float > %R } declare void @llvm.memcpy.i64(i8 *nocapture, i8 *nocapture, i64, i32) nounwind which compiles to:_foo:subl $140, %esp movaps %xmm3, 112(%esp) movaps %xmm2, 96(%esp) movaps %xmm1, 80(%esp) movaps %xmm0, 64(%esp) movl 60(%esp), %eax movl %eax, 124(%esp) movl 56(%esp), %eax movl %eax, 120(%esp) movl 52(%esp), %eax< many many more 32-bit copies > movaps(%esp), %xmm0 movaps 16(%esp), %xmm1 movaps 32(%esp), %xmm2 movaps 48(%esp), %xmm3 addl $140, %esp ret On Nehalem, it may even be cheaper to just use movups when unaligned than to fall back to lower-granularity chunks. Implement processor-specific optimizations for parity with GCC on these processors. GCC does two optimizations:1. ix86_pad_returns inserts a noop before ret instructions if immediately preceded by a conditional branch or is the target of a jump. 2. ix86_avoid_jump_misspredicts inserts noops in cases where a 16-byte block of code contains more than 3 branches. The first one is done for all AMDs, Core2, and "Generic" The second one is done for:Atom, Pentium Pro, all AMDs, Pentium 4, Nocona, Core 2, and "Generic" Testcase:int x(int a) { return(a &0xf0)> >4 tmp
Definition: README.txt:1347
llvm::FoldingSetBase::FoldingSetBase
FoldingSetBase(unsigned Log2InitSize=6)
Definition: FoldingSet.cpp:183
llvm::FoldingSetImpl::reserve
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:468
llvm::FoldingSetIterator::operator*
T & operator*() const
Definition: FoldingSet.h:713
llvm::Data
@ Data
Definition: SIMachineScheduler.h:55
llvm::FoldingSetNodeID::AddString
void AddString(StringRef String)
Add* - Add various data types to Bit data.
Definition: FoldingSet.cpp:45
llvm::FoldingSetBucketIterator::operator++
FoldingSetBucketIterator operator++(int)
Definition: FoldingSet.h:773
llvm::FoldingSetImpl::begin
iterator begin()
Definition: FoldingSet.h:447
Context
LLVMContext & Context
Definition: NVVMIntrRange.cpp:66
llvm::FoldingSetBucketIterator::operator++
FoldingSetBucketIterator & operator++()
Definition: FoldingSet.h:769
llvm::FoldingSetIteratorImpl::operator!=
bool operator!=(const FoldingSetIteratorImpl &RHS) const
Definition: FoldingSet.h:704
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:187
llvm::ModRefInfo::Ref
@ Ref
The access may reference the value stored in memory.
llvm::DefaultContextualFoldingSetTrait::ComputeHash
static unsigned ComputeHash(T &X, FoldingSetNodeID &TempID, Ctx Context)
Definition: FoldingSet.h:425
llvm::FoldingSetIterator
Definition: FoldingSet.h:394
llvm::FoldingSetVector::InsertNode
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:677
llvm::FoldingSetBase
FoldingSetBase - Implements the folding set functionality.
Definition: FoldingSet.h:115
llvm::FoldingSetBucketIteratorImpl::FoldingSetBucketIteratorImpl
FoldingSetBucketIteratorImpl(void **Bucket, bool)
Definition: FoldingSet.h:740
llvm::FoldingSetImpl::RemoveNode
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:474
llvm::FoldingSetBase::Node::SetNextInBucket
void SetNextInBucket(void *N)
Definition: FoldingSet.h:146
llvm::FoldingSetNodeIDRef::ComputeHash
unsigned ComputeHash() const
ComputeHash - Compute a strong hash value for this FoldingSetNodeIDRef, used to lookup the node in th...
Definition: FoldingSet.h:298
llvm::FoldingSetNodeID::clear
void clear()
clear - Clear the accumulated profile, allowing this FoldingSetNodeID object to be used to compute a ...
Definition: FoldingSet.h:366
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::FoldingSetBase::clear
void clear()
clear - Remove all nodes from the folding set.
Definition: FoldingSet.cpp:213
llvm::FoldingSetTrait< std::pair< T1, T2 > >::Profile
static void Profile(const std::pair< T1, T2 > &P, FoldingSetNodeID &ID)
Definition: FoldingSet.h:825
llvm::FoldingSetBase::Node::getNextInBucket
void * getNextInBucket() const
Definition: FoldingSet.h:145
llvm::FoldingSetNodeID::AddInteger
void AddInteger(signed I)
Definition: FoldingSet.h:339
llvm::FoldingSetIteratorImpl::FoldingSetIteratorImpl
FoldingSetIteratorImpl(void **Bucket)
Definition: FoldingSet.cpp:390
Info
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
llvm::FoldingSetBase::NumBuckets
unsigned NumBuckets
NumBuckets - Length of the Buckets array. Always a power of 2.
Definition: FoldingSet.h:121
llvm::FoldingSetBucketIterator::FoldingSetBucketIterator
FoldingSetBucketIterator(void **Bucket)
Definition: FoldingSet.h:760
llvm::FoldingSetBase::operator=
FoldingSetBase & operator=(FoldingSetBase &&RHS)
Definition: FoldingSet.cpp:198
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::FoldingSetBucketIterator::operator->
T * operator->() const
Definition: FoldingSet.h:767
llvm::FoldingSetBucketIteratorImpl::operator!=
bool operator!=(const FoldingSetBucketIteratorImpl &RHS) const
Definition: FoldingSet.h:752
llvm::FoldingSetBase::empty
bool empty() const
empty - Returns true if there are no nodes in the folding set.
Definition: FoldingSet.h:156
llvm::FoldingSetNodeID::FoldingSetNodeID
FoldingSetNodeID(FoldingSetNodeIDRef Ref)
Definition: FoldingSet.h:326
llvm::FoldingSetBase::RemoveNode
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
llvm::FoldingSetTrait< T * >::Profile
static void Profile(T *X, FoldingSetNodeID &ID)
Definition: FoldingSet.h:819
llvm::DefaultFoldingSetTrait::ComputeHash
static unsigned ComputeHash(T &X, FoldingSetNodeID &TempID)
Definition: FoldingSet.h:409
llvm::FoldingSetImpl::InsertNode
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:503
llvm::FoldingSetImpl::end
const_iterator end() const
Definition: FoldingSet.h:453
llvm::ContextualFoldingSet
ContextualFoldingSet - This template class is a further refinement of FoldingSet which provides a con...
Definition: FoldingSet.h:572
llvm::FoldingSetTrait
FoldingSetTrait - This trait class is used to define behavior of how to "profile" (in the FoldingSet ...
Definition: FoldingSet.h:261
llvm::FoldingSetImpl::FoldingSetImpl
FoldingSetImpl(unsigned Log2InitSize)
Definition: FoldingSet.h:437
llvm::FoldingSetNodeWrapper::getValue
T & getValue()
Definition: FoldingSet.h:792
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::FoldingSetBase::FindNodeOrInsertPos
Node * FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos, const FoldingSetInfo &Info)
FindNodeOrInsertPos - Look up the node specified by ID.
Definition: FoldingSet.cpp:278
llvm::FoldingSetNodeID::Intern
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
llvm::FoldingSetBucketIteratorImpl::Ptr
void * Ptr
Definition: FoldingSet.h:736
llvm::BumpPtrAllocatorImpl
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:63
llvm::FoldingSetVector::empty
bool empty() const
empty - Returns true if there are no nodes in the folding set.
Definition: FoldingSet.h:686
iterator.h
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::FoldingSetNodeWrapper::Profile
void Profile(FoldingSetNodeID &ID)
Definition: FoldingSet.h:790
llvm::FoldingSetVector::begin
iterator begin()
Definition: FoldingSet.h:640
llvm::FoldingSetNodeWrapper
FoldingSetNodeWrapper - This template class is used to "wrap" arbitrary types in an enclosing object ...
Definition: FoldingSet.h:782
llvm::FoldingSetNodeID::operator!=
bool operator!=(const FoldingSetNodeIDRef RHS) const
Definition: FoldingSet.h:379
llvm::FastFoldingSetNode::Profile
void Profile(FoldingSetNodeID &ID) const
Definition: FoldingSet.h:812
llvm::FoldingSet::FoldingSet
FoldingSet(unsigned Log2InitSize=6)
Definition: FoldingSet.h:557
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::FoldingSetBase::FoldingSetInfo::ComputeNodeHash
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:184
llvm::FoldingSetNodeID::AddPointer
void AddPointer(const void *Ptr)
Add* - Add various data types to Bit data.
Definition: FoldingSet.h:330
llvm::FoldingSetBucketIterator::operator*
T & operator*() const
Definition: FoldingSet.h:766
llvm::FoldingSetVector
FoldingSetVector - This template class combines a FoldingSet and a vector to provide the interface of...
Definition: FoldingSet.h:631
llvm::FoldingSetBase::reserve
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
Ptr
@ Ptr
Definition: TargetLibraryInfo.cpp:60
llvm::FoldingSetTrait< T, std::enable_if_t< std::is_enum< T >::value > >::Profile
static void Profile(const T &X, FoldingSetNodeID &ID)
Definition: FoldingSet.h:834
llvm::FoldingSetIteratorImpl
FoldingSetIteratorImpl - This is the common iterator support shared by all folding sets,...
Definition: FoldingSet.h:692
llvm::FoldingSetVector::GetOrInsertNode
T * GetOrInsertNode(T *N)
GetOrInsertNode - If there is an existing simple Node exactly equal to the specified node,...
Definition: FoldingSet.h:661
llvm::FoldingSetBase::InsertNode
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
llvm::FoldingSetIterator::operator++
FoldingSetIterator & operator++()
Definition: FoldingSet.h:721
llvm::FoldingSetBase::size
unsigned size() const
size - Returns the number of nodes in the folding set.
Definition: FoldingSet.h:153
llvm::FoldingSetImpl::bucket_begin
bucket_iterator bucket_begin(unsigned hash)
Definition: FoldingSet.h:457
llvm::FoldingSet
FoldingSet - This template class is used to instantiate a specialized implementation of the folding s...
Definition: FoldingSet.h:520
llvm::DefaultFoldingSetTrait::Profile
static void Profile(const T &X, FoldingSetNodeID &ID)
Definition: FoldingSet.h:232
llvm::FoldingSetBucketIterator::FoldingSetBucketIterator
FoldingSetBucketIterator(void **Bucket, bool)
Definition: FoldingSet.h:763
llvm::FoldingSetImpl::end
iterator end()
Definition: FoldingSet.h:448
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
llvm::FoldingSetBase::Node
Node - This class is used to maintain the singly linked bucket list in a folding set.
Definition: FoldingSet.h:136
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::FoldingSetImpl::begin
const_iterator begin() const
Definition: FoldingSet.h:452
llvm::FoldingSetNodeID::AddBoolean
void AddBoolean(bool B)
Definition: FoldingSet.h:357
llvm::FoldingSetNodeID
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
Definition: FoldingSet.h:318
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::FoldingSetNodeID::ComputeHash
unsigned ComputeHash() const
ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used to lookup the node in the F...
Definition: FoldingSet.h:370
llvm::FoldingSetIterator::operator++
FoldingSetIterator operator++(int)
Definition: FoldingSet.h:725
Node
Definition: ItaniumDemangle.h:156
llvm::FoldingSetBucketIterator
Definition: FoldingSet.h:395
llvm::FoldingSetVector::end
iterator end()
Definition: FoldingSet.h:641
llvm::FoldingSetBucketIteratorImpl
FoldingSetBucketIteratorImpl - This is the common bucket iterator support shared by all folding sets,...
Definition: FoldingSet.h:734
llvm::FoldingSetNodeIDRef::getSize
size_t getSize() const
Definition: FoldingSet.h:311
std
Definition: BitVector.h:851
llvm::DefaultContextualFoldingSetTrait::Equals
static bool Equals(T &X, const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID, Ctx Context)
Definition: FoldingSet.h:415
llvm::FoldingSetImpl::const_iterator
FoldingSetIterator< const T > const_iterator
Definition: FoldingSet.h:450
llvm::DefaultFoldingSetTrait
DefaultFoldingSetTrait - This class provides default implementations for FoldingSetTrait implementati...
Definition: FoldingSet.h:231
x
TODO unsigned x
Definition: README.txt:10
llvm::FoldingSetNodeID::AddNodeID
void AddNodeID(const FoldingSetNodeID &ID)
Definition: FoldingSet.cpp:102
llvm::FoldingSetNodeIDRef::FoldingSetNodeIDRef
FoldingSetNodeIDRef()=default
llvm::FoldingSetNodeID::AddInteger
void AddInteger(unsigned long I)
Definition: FoldingSet.h:342
llvm::FastFoldingSetNode
FastFoldingSetNode - This is a subclass of FoldingSetNode which stores a FoldingSetNodeID value rathe...
Definition: FoldingSet.h:805
llvm::FoldingSetNodeIDRef::getData
const unsigned * getData() const
Definition: FoldingSet.h:310
llvm::FoldingSetNodeIDRef
FoldingSetNodeIDRef - This class describes a reference to an interned FoldingSetNodeID,...
Definition: FoldingSet.h:288
llvm::FoldingSetVector::end
const_iterator end() const
Definition: FoldingSet.h:646
llvm::FoldingSetIterator::FoldingSetIterator
FoldingSetIterator(void **Bucket)
Definition: FoldingSet.h:711
llvm::FoldingSetBucketIteratorImpl::advance
void advance()
Definition: FoldingSet.h:742
llvm::FoldingSetNodeIDRef::FoldingSetNodeIDRef
FoldingSetNodeIDRef(const unsigned *D, size_t S)
Definition: FoldingSet.h:294
SmallVector.h
llvm::FoldingSetVector::FoldingSetVector
FoldingSetVector(unsigned Log2InitSize=6)
Definition: FoldingSet.h:636
llvm::ContextualFoldingSetTrait
ContextualFoldingSetTrait - Like FoldingSetTrait, but for ContextualFoldingSets.
Definition: FoldingSet.h:279
llvm::DefaultFoldingSetTrait::Equals
static bool Equals(T &X, const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID)
Definition: FoldingSet.h:401
Allocator
Basic Register Allocator
Definition: RegAllocBasic.cpp:143
llvm::FoldingSetBase::capacity
unsigned capacity()
capacity - Returns the number of nodes permitted in the folding set before a rebucket operation is pe...
Definition: FoldingSet.h:160
N
#define N
llvm::hash_combine_range
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
Definition: Hashing.h:483
llvm::FoldingSetNodeIDRef::operator!=
bool operator!=(FoldingSetNodeIDRef RHS) const
Definition: FoldingSet.h:304
llvm::FoldingSetNodeWrapper::getValue
const T & getValue() const
Definition: FoldingSet.h:793
llvm::FoldingSetVector::size
unsigned size() const
size - Returns the number of nodes in the folding set.
Definition: FoldingSet.h:683
llvm::FoldingSetBase::GetOrInsertNode
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
llvm::FoldingSetNodeID::AddInteger
void AddInteger(unsigned I)
Definition: FoldingSet.h:340
llvm::FoldingSetIteratorImpl::NodePtr
FoldingSetNode * NodePtr
Definition: FoldingSet.h:694
llvm::FoldingSetIteratorImpl::operator==
bool operator==(const FoldingSetIteratorImpl &RHS) const
Definition: FoldingSet.h:701
llvm::FoldingSetImpl::bucket_end
bucket_iterator bucket_end(unsigned hash)
Definition: FoldingSet.h:461
llvm::FoldingSetNodeID::FoldingSetNodeID
FoldingSetNodeID()=default
llvm::pointee_iterator
An iterator type that allows iterating over the pointees via some other iterator.
Definition: iterator.h:320
llvm::AMDGPU::HSAMD::Kernel::Key::Args
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
Definition: AMDGPUMetadata.h:394
llvm::FoldingSet::operator=
FoldingSet & operator=(FoldingSet &&RHS)=default
llvm::FoldingSetNodeID::operator!=
bool operator!=(const FoldingSetNodeID &RHS) const
Definition: FoldingSet.h:378
llvm::FoldingSetIteratorImpl::advance
void advance()
Definition: FoldingSet.cpp:399
llvm::DefaultFoldingSetTrait::Profile
static void Profile(T &X, FoldingSetNodeID &ID)
Definition: FoldingSet.h:235
llvm::DefaultContextualFoldingSetTrait
DefaultContextualFoldingSetTrait - Like DefaultFoldingSetTrait, but for ContextualFoldingSets.
Definition: FoldingSet.h:266
llvm::FoldingSetBase::Node::Node
Node()=default
llvm::FastFoldingSetNode::FastFoldingSetNode
FastFoldingSetNode(const FoldingSetNodeID &ID)
Definition: FoldingSet.h:809
llvm::FoldingSetVector::begin
const_iterator begin() const
Definition: FoldingSet.h:645
llvm::sampleprof::Base
@ Base
Definition: Discriminator.h:58
llvm::FoldingSetNodeID::Add
void Add(const T &x)
Definition: FoldingSet.h:362
llvm::ContextualFoldingSet::getContext
Ctx getContext() const
Definition: FoldingSet.h:622
llvm::FoldingSetVector::clear
void clear()
clear - Remove all nodes from the folding set.
Definition: FoldingSet.h:649
llvm::FoldingSetIterator::operator->
T * operator->() const
Definition: FoldingSet.h:717