contrib/llvm/include/llvm/ADT/FoldingSet.h

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