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