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