LCOV - code coverage report
Current view: top level - include/llvm/ADT - FoldingSet.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 77 83 92.8 %
Date: 2018-05-20 00:06:23 Functions: 215 373 57.6 %
Legend: Lines: hit not hit

          Line data    Source code
       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             :   void **Buckets;
     119             : 
     120             :   /// NumBuckets - Length of the Buckets array.  Always a power of 2.
     121             :   unsigned NumBuckets;
     122             : 
     123             :   /// NumNodes - Number of nodes in the folding set. Growth occurs when NumNodes
     124             :   /// is greater than twice the number of buckets.
     125             :   unsigned NumNodes;
     126             : 
     127             :   explicit FoldingSetBase(unsigned Log2InitSize = 6);
     128             :   FoldingSetBase(FoldingSetBase &&Arg);
     129             :   FoldingSetBase &operator=(FoldingSetBase &&RHS);
     130             :   ~FoldingSetBase();
     131             : 
     132             : public:
     133             :   //===--------------------------------------------------------------------===//
     134             :   /// Node - This class is used to maintain the singly linked bucket list in
     135             :   /// a folding set.
     136             :   class Node {
     137             :   private:
     138             :     // NextInFoldingSetBucket - next link in the bucket list.
     139             :     void *NextInFoldingSetBucket = nullptr;
     140             : 
     141             :   public:
     142    72282781 :     Node() = default;
     143             : 
     144             :     // Accessors
     145   179966625 :     void *getNextInBucket() const { return NextInFoldingSetBucket; }
     146   157500857 :     void SetNextInBucket(void *N) { NextInFoldingSetBucket = N; }
     147             :   };
     148             : 
     149             :   /// clear - Remove all nodes from the folding set.
     150             :   void clear();
     151             : 
     152             :   /// size - Returns the number of nodes in the folding set.
     153             :   unsigned size() const { return NumNodes; }
     154             : 
     155             :   /// empty - Returns true if there are no nodes in the folding set.
     156           3 :   bool empty() const { return NumNodes == 0; }
     157             : 
     158             :   /// reserve - Increase the number of buckets such that adding the
     159             :   /// EltCount-th node won't cause a rebucket operation. reserve is permitted
     160             :   /// to allocate more space than requested by EltCount.
     161             :   void reserve(unsigned EltCount);
     162             : 
     163             :   /// capacity - Returns the number of nodes permitted in the folding set
     164             :   /// before a rebucket operation is performed.
     165             :   unsigned capacity() {
     166             :     // We allow a load factor of up to 2.0,
     167             :     // so that means our capacity is NumBuckets * 2
     168    98574206 :     return NumBuckets * 2;
     169             :   }
     170             : 
     171             : private:
     172             :   /// GrowHashTable - Double the size of the hash table and rehash everything.
     173             :   void GrowHashTable();
     174             : 
     175             :   /// GrowBucketCount - resize the hash table and rehash everything.
     176             :   /// NewBucketCount must be a power of two, and must be greater than the old
     177             :   /// bucket count.
     178             :   void GrowBucketCount(unsigned NewBucketCount);
     179             : 
     180             : protected:
     181             :   /// GetNodeProfile - Instantiations of the FoldingSet template implement
     182             :   /// this function to gather data bits for the given node.
     183             :   virtual void GetNodeProfile(Node *N, FoldingSetNodeID &ID) const = 0;
     184             : 
     185             :   /// NodeEquals - Instantiations of the FoldingSet template implement
     186             :   /// this function to compare the given node with the given ID.
     187             :   virtual bool NodeEquals(Node *N, const FoldingSetNodeID &ID, unsigned IDHash,
     188             :                           FoldingSetNodeID &TempID) const=0;
     189             : 
     190             :   /// ComputeNodeHash - Instantiations of the FoldingSet template implement
     191             :   /// this function to compute a hash value for the given node.
     192             :   virtual unsigned ComputeNodeHash(Node *N, FoldingSetNodeID &TempID) const = 0;
     193             : 
     194             :   // The below methods are protected to encourage subclasses to provide a more
     195             :   // type-safe API.
     196             : 
     197             :   /// RemoveNode - Remove a node from the folding set, returning true if one
     198             :   /// was removed or false if the node was not in the folding set.
     199             :   bool RemoveNode(Node *N);
     200             : 
     201             :   /// GetOrInsertNode - If there is an existing simple Node exactly
     202             :   /// equal to the specified node, return it.  Otherwise, insert 'N' and return
     203             :   /// it instead.
     204             :   Node *GetOrInsertNode(Node *N);
     205             : 
     206             :   /// FindNodeOrInsertPos - Look up the node specified by ID.  If it exists,
     207             :   /// return it.  If not, return the insertion token that will make insertion
     208             :   /// faster.
     209             :   Node *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos);
     210             : 
     211             :   /// InsertNode - Insert the specified node into the folding set, knowing that
     212             :   /// it is not already in the folding set.  InsertPos must be obtained from
     213             :   /// FindNodeOrInsertPos.
     214             :   void InsertNode(Node *N, void *InsertPos);
     215             : };
     216             : 
     217             : //===----------------------------------------------------------------------===//
     218             : 
     219             : /// DefaultFoldingSetTrait - This class provides default implementations
     220             : /// for FoldingSetTrait implementations.
     221             : template<typename T> struct DefaultFoldingSetTrait {
     222             :   static void Profile(const T &X, FoldingSetNodeID &ID) {
     223     2946343 :     X.Profile(ID);
     224             :   }
     225             :   static void Profile(T &X, FoldingSetNodeID &ID) {
     226   184093358 :     X.Profile(ID);
     227             :   }
     228             : 
     229             :   // Equals - Test if the profile for X would match ID, using TempID
     230             :   // to compute a temporary ID if necessary. The default implementation
     231             :   // just calls Profile and does a regular comparison. Implementations
     232             :   // can override this to provide more efficient implementations.
     233             :   static inline bool Equals(T &X, const FoldingSetNodeID &ID, unsigned IDHash,
     234             :                             FoldingSetNodeID &TempID);
     235             : 
     236             :   // ComputeHash - Compute a hash value for X, using TempID to
     237             :   // compute a temporary ID if necessary. The default implementation
     238             :   // just calls Profile and does a regular hash computation.
     239             :   // Implementations can override this to provide more efficient
     240             :   // implementations.
     241             :   static inline unsigned ComputeHash(T &X, FoldingSetNodeID &TempID);
     242             : };
     243             : 
     244             : /// FoldingSetTrait - This trait class is used to define behavior of how
     245             : /// to "profile" (in the FoldingSet parlance) an object of a given type.
     246             : /// The default behavior is to invoke a 'Profile' method on an object, but
     247             : /// through template specialization the behavior can be tailored for specific
     248             : /// types.  Combined with the FoldingSetNodeWrapper class, one can add objects
     249             : /// to FoldingSets that were not originally designed to have that behavior.
     250             : template<typename T> struct FoldingSetTrait
     251             :   : public DefaultFoldingSetTrait<T> {};
     252             : 
     253             : /// DefaultContextualFoldingSetTrait - Like DefaultFoldingSetTrait, but
     254             : /// for ContextualFoldingSets.
     255             : template<typename T, typename Ctx>
     256             : struct DefaultContextualFoldingSetTrait {
     257             :   static void Profile(T &X, FoldingSetNodeID &ID, Ctx Context) {
     258    25834023 :     X.Profile(ID, Context);
     259             :   }
     260             : 
     261             :   static inline bool Equals(T &X, const FoldingSetNodeID &ID, unsigned IDHash,
     262             :                             FoldingSetNodeID &TempID, Ctx Context);
     263             :   static inline unsigned ComputeHash(T &X, FoldingSetNodeID &TempID,
     264             :                                      Ctx Context);
     265             : };
     266             : 
     267             : /// ContextualFoldingSetTrait - Like FoldingSetTrait, but for
     268             : /// ContextualFoldingSets.
     269             : template<typename T, typename Ctx> struct ContextualFoldingSetTrait
     270             :   : public DefaultContextualFoldingSetTrait<T, Ctx> {};
     271             : 
     272             : //===--------------------------------------------------------------------===//
     273             : /// FoldingSetNodeIDRef - This class describes a reference to an interned
     274             : /// FoldingSetNodeID, which can be a useful to store node id data rather
     275             : /// than using plain FoldingSetNodeIDs, since the 32-element SmallVector
     276             : /// is often much larger than necessary, and the possibility of heap
     277             : /// allocation means it requires a non-trivial destructor call.
     278             : class FoldingSetNodeIDRef {
     279             :   const unsigned *Data = nullptr;
     280             :   size_t Size = 0;
     281             : 
     282             : public:
     283             :   FoldingSetNodeIDRef() = default;
     284   724460306 :   FoldingSetNodeIDRef(const unsigned *D, size_t S) : Data(D), Size(S) {}
     285             : 
     286             :   /// ComputeHash - Compute a strong hash value for this FoldingSetNodeIDRef,
     287             :   /// used to lookup the node in the FoldingSetBase.
     288             :   unsigned ComputeHash() const;
     289             : 
     290             :   bool operator==(FoldingSetNodeIDRef) const;
     291             : 
     292             :   bool operator!=(FoldingSetNodeIDRef RHS) const { return !(*this == RHS); }
     293             : 
     294             :   /// Used to compare the "ordering" of two nodes as defined by the
     295             :   /// profiled bits and their ordering defined by memcmp().
     296             :   bool operator<(FoldingSetNodeIDRef) const;
     297             : 
     298             :   const unsigned *getData() const { return Data; }
     299             :   size_t getSize() const { return Size; }
     300             : };
     301             : 
     302             : //===--------------------------------------------------------------------===//
     303             : /// FoldingSetNodeID - This class is used to gather all the unique data bits of
     304             : /// a node.  When all the bits are gathered this class is used to produce a
     305             : /// hash value for the node.
     306     8911127 : class FoldingSetNodeID {
     307             :   /// Bits - Vector of all the data bits that make the node unique.
     308             :   /// Use a SmallVector to avoid a heap allocation in the common case.
     309             :   SmallVector<unsigned, 32> Bits;
     310             : 
     311             : public:
     312             :   FoldingSetNodeID() = default;
     313             : 
     314             :   FoldingSetNodeID(FoldingSetNodeIDRef Ref)
     315           0 :     : Bits(Ref.getData(), Ref.getData() + Ref.getSize()) {}
     316             : 
     317             :   /// Add* - Add various data types to Bit data.
     318             :   void AddPointer(const void *Ptr);
     319             :   void AddInteger(signed I);
     320             :   void AddInteger(unsigned I);
     321             :   void AddInteger(long I);
     322             :   void AddInteger(unsigned long I);
     323             :   void AddInteger(long long I);
     324             :   void AddInteger(unsigned long long I);
     325   139575544 :   void AddBoolean(bool B) { AddInteger(B ? 1U : 0U); }
     326             :   void AddString(StringRef String);
     327             :   void AddNodeID(const FoldingSetNodeID &ID);
     328             : 
     329             :   template <typename T>
     330             :   inline void Add(const T &x) { FoldingSetTrait<T>::Profile(x, *this); }
     331             : 
     332             :   /// clear - Clear the accumulated profile, allowing this FoldingSetNodeID
     333             :   /// object to be used to compute a new profile.
     334             :   inline void clear() { Bits.clear(); }
     335             : 
     336             :   /// ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used
     337             :   /// to lookup the node in the FoldingSetBase.
     338             :   unsigned ComputeHash() const;
     339             : 
     340             :   /// operator== - Used to compare two nodes to each other.
     341             :   bool operator==(const FoldingSetNodeID &RHS) const;
     342             :   bool operator==(const FoldingSetNodeIDRef RHS) const;
     343             : 
     344         169 :   bool operator!=(const FoldingSetNodeID &RHS) const { return !(*this == RHS); }
     345             :   bool operator!=(const FoldingSetNodeIDRef RHS) const { return !(*this ==RHS);}
     346             : 
     347             :   /// Used to compare the "ordering" of two nodes as defined by the
     348             :   /// profiled bits and their ordering defined by memcmp().
     349             :   bool operator<(const FoldingSetNodeID &RHS) const;
     350             :   bool operator<(const FoldingSetNodeIDRef RHS) const;
     351             : 
     352             :   /// Intern - Copy this node's data to a memory region allocated from the
     353             :   /// given allocator and return a FoldingSetNodeIDRef describing the
     354             :   /// interned data.
     355             :   FoldingSetNodeIDRef Intern(BumpPtrAllocator &Allocator) const;
     356             : };
     357             : 
     358             : // Convenience type to hide the implementation of the folding set.
     359             : using FoldingSetNode = FoldingSetBase::Node;
     360             : template<class T> class FoldingSetIterator;
     361             : template<class T> class FoldingSetBucketIterator;
     362             : 
     363             : // Definitions of FoldingSetTrait and ContextualFoldingSetTrait functions, which
     364             : // require the definition of FoldingSetNodeID.
     365             : template<typename T>
     366             : inline bool
     367    27914013 : DefaultFoldingSetTrait<T>::Equals(T &X, const FoldingSetNodeID &ID,
     368             :                                   unsigned /*IDHash*/,
     369             :                                   FoldingSetNodeID &TempID) {
     370             :   FoldingSetTrait<T>::Profile(X, TempID);
     371   212411295 :   return TempID == ID;
     372             : }
     373             : template<typename T>
     374             : inline unsigned
     375     9714943 : DefaultFoldingSetTrait<T>::ComputeHash(T &X, FoldingSetNodeID &TempID) {
     376             :   FoldingSetTrait<T>::Profile(X, TempID);
     377    29247392 :   return TempID.ComputeHash();
     378             : }
     379             : template<typename T, typename Ctx>
     380             : inline bool
     381             : DefaultContextualFoldingSetTrait<T, Ctx>::Equals(T &X,
     382             :                                                  const FoldingSetNodeID &ID,
     383             :                                                  unsigned /*IDHash*/,
     384             :                                                  FoldingSetNodeID &TempID,
     385             :                                                  Ctx Context) {
     386             :   ContextualFoldingSetTrait<T, Ctx>::Profile(X, TempID, Context);
     387    18799815 :   return TempID == ID;
     388             : }
     389             : template<typename T, typename Ctx>
     390             : inline unsigned
     391             : DefaultContextualFoldingSetTrait<T, Ctx>::ComputeHash(T &X,
     392             :                                                       FoldingSetNodeID &TempID,
     393             :                                                       Ctx Context) {
     394             :   ContextualFoldingSetTrait<T, Ctx>::Profile(X, TempID, Context);
     395     7034208 :   return TempID.ComputeHash();
     396             : }
     397             : 
     398             : //===----------------------------------------------------------------------===//
     399             : /// FoldingSetImpl - An implementation detail that lets us share code between
     400             : /// FoldingSet and ContextualFoldingSet.
     401             : template <class T> class FoldingSetImpl : public FoldingSetBase {
     402             : protected:
     403     3773099 :   explicit FoldingSetImpl(unsigned Log2InitSize)
     404     3773099 :       : FoldingSetBase(Log2InitSize) {}
     405             : 
     406        3008 :   FoldingSetImpl(FoldingSetImpl &&Arg) = default;
     407             :   FoldingSetImpl &operator=(FoldingSetImpl &&RHS) = default;
     408     2932114 :   ~FoldingSetImpl() = default;
     409             : 
     410             : public:
     411             :   using iterator = FoldingSetIterator<T>;
     412             : 
     413      158591 :   iterator begin() { return iterator(Buckets); }
     414      317694 :   iterator end() { return iterator(Buckets+NumBuckets); }
     415             : 
     416             :   using const_iterator = FoldingSetIterator<const T>;
     417             : 
     418        1314 :   const_iterator begin() const { return const_iterator(Buckets); }
     419        2628 :   const_iterator end() const { return const_iterator(Buckets+NumBuckets); }
     420             : 
     421             :   using bucket_iterator = FoldingSetBucketIterator<T>;
     422             : 
     423             :   bucket_iterator bucket_begin(unsigned hash) {
     424             :     return bucket_iterator(Buckets + (hash & (NumBuckets-1)));
     425             :   }
     426             : 
     427             :   bucket_iterator bucket_end(unsigned hash) {
     428             :     return bucket_iterator(Buckets + (hash & (NumBuckets-1)), true);
     429             :   }
     430             : 
     431             :   /// RemoveNode - Remove a node from the folding set, returning true if one
     432             :   /// was removed or false if the node was not in the folding set.
     433    20844192 :   bool RemoveNode(T *N) { return FoldingSetBase::RemoveNode(N); }
     434             : 
     435             :   /// GetOrInsertNode - If there is an existing simple Node exactly
     436             :   /// equal to the specified node, return it.  Otherwise, insert 'N' and
     437             :   /// return it instead.
     438             :   T *GetOrInsertNode(T *N) {
     439     5970880 :     return static_cast<T *>(FoldingSetBase::GetOrInsertNode(N));
     440             :   }
     441             : 
     442             :   /// FindNodeOrInsertPos - Look up the node specified by ID.  If it exists,
     443             :   /// return it.  If not, return the insertion token that will make insertion
     444             :   /// faster.
     445             :   T *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos) {
     446   199350335 :     return static_cast<T *>(FoldingSetBase::FindNodeOrInsertPos(ID, InsertPos));
     447             :   }
     448             : 
     449             :   /// InsertNode - Insert the specified node into the folding set, knowing that
     450             :   /// it is not already in the folding set.  InsertPos must be obtained from
     451             :   /// FindNodeOrInsertPos.
     452             :   void InsertNode(T *N, void *InsertPos) {
     453    55986690 :     FoldingSetBase::InsertNode(N, InsertPos);
     454             :   }
     455             : 
     456             :   /// InsertNode - Insert the specified node into the folding set, knowing that
     457             :   /// it is not already in the folding set.
     458             :   void InsertNode(T *N) {
     459             :     T *Inserted = GetOrInsertNode(N);
     460             :     (void)Inserted;
     461             :     assert(Inserted == N && "Node already inserted!");
     462             :   }
     463             : };
     464             : 
     465             : //===----------------------------------------------------------------------===//
     466             : /// FoldingSet - This template class is used to instantiate a specialized
     467             : /// implementation of the folding set to the node class T.  T must be a
     468             : /// subclass of FoldingSetNode and implement a Profile function.
     469             : ///
     470             : /// Note that this set type is movable and move-assignable. However, its
     471             : /// moved-from state is not a valid state for anything other than
     472             : /// move-assigning and destroying. This is primarily to enable movable APIs
     473             : /// that incorporate these objects.
     474     2536857 : template <class T> class FoldingSet final : public FoldingSetImpl<T> {
     475             :   using Super = FoldingSetImpl<T>;
     476             :   using Node = typename Super::Node;
     477             : 
     478             :   /// GetNodeProfile - Each instantiatation of the FoldingSet needs to provide a
     479             :   /// way to convert nodes into a unique specifier.
     480     5970881 :   void GetNodeProfile(Node *N, FoldingSetNodeID &ID) const override {
     481        7840 :     T *TN = static_cast<T *>(N);
     482           0 :     FoldingSetTrait<T>::Profile(*TN, ID);
     483     5970881 :   }
     484             : 
     485             :   /// NodeEquals - Instantiations may optionally provide a way to compare a
     486             :   /// node with a specified ID.
     487   227651157 :   bool NodeEquals(Node *N, const FoldingSetNodeID &ID, unsigned IDHash,
     488             :                   FoldingSetNodeID &TempID) const override {
     489   159008114 :     T *TN = static_cast<T *>(N);
     490   227651160 :     return FoldingSetTrait<T>::Equals(*TN, ID, IDHash, TempID);
     491             :   }
     492             : 
     493             :   /// ComputeNodeHash - Instantiations may optionally provide a way to compute a
     494             :   /// hash value directly from a node.
     495    29634810 :   unsigned ComputeNodeHash(Node *N, FoldingSetNodeID &TempID) const override {
     496    23871180 :     T *TN = static_cast<T *>(N);
     497    29634810 :     return FoldingSetTrait<T>::ComputeHash(*TN, TempID);
     498             :   }
     499             : 
     500             : public:
     501     3646264 :   explicit FoldingSet(unsigned Log2InitSize = 6) : Super(Log2InitSize) {}
     502        3008 :   FoldingSet(FoldingSet &&Arg) = default;
     503             :   FoldingSet &operator=(FoldingSet &&RHS) = default;
     504             : };
     505             : 
     506             : //===----------------------------------------------------------------------===//
     507             : /// ContextualFoldingSet - This template class is a further refinement
     508             : /// of FoldingSet which provides a context argument when calling
     509             : /// Profile on its nodes.  Currently, that argument is fixed at
     510             : /// initialization time.
     511             : ///
     512             : /// T must be a subclass of FoldingSetNode and implement a Profile
     513             : /// function with signature
     514             : ///   void Profile(FoldingSetNodeID &, Ctx);
     515             : template <class T, class Ctx>
     516      115564 : class ContextualFoldingSet final : public FoldingSetImpl<T> {
     517             :   // Unfortunately, this can't derive from FoldingSet<T> because the
     518             :   // construction of the vtable for FoldingSet<T> requires
     519             :   // FoldingSet<T>::GetNodeProfile to be instantiated, which in turn
     520             :   // requires a single-argument T::Profile().
     521             : 
     522             :   using Super = FoldingSetImpl<T>;
     523             :   using Node = typename Super::Node;
     524             : 
     525             :   Ctx Context;
     526             : 
     527             :   /// GetNodeProfile - Each instantiatation of the FoldingSet needs to provide a
     528             :   /// way to convert nodes into a unique specifier.
     529           0 :   void GetNodeProfile(Node *N, FoldingSetNodeID &ID) const override {
     530           0 :     T *TN = static_cast<T *>(N);
     531           0 :     ContextualFoldingSetTrait<T, Ctx>::Profile(*TN, ID, Context);
     532           0 :   }
     533             : 
     534    18799815 :   bool NodeEquals(Node *N, const FoldingSetNodeID &ID, unsigned IDHash,
     535             :                   FoldingSetNodeID &TempID) const override {
     536    18799815 :     T *TN = static_cast<T *>(N);
     537    18799815 :     return ContextualFoldingSetTrait<T, Ctx>::Equals(*TN, ID, IDHash, TempID,
     538    18799815 :                                                      Context);
     539             :   }
     540             : 
     541     7034208 :   unsigned ComputeNodeHash(Node *N, FoldingSetNodeID &TempID) const override {
     542     7034208 :     T *TN = static_cast<T *>(N);
     543    14068416 :     return ContextualFoldingSetTrait<T, Ctx>::ComputeHash(*TN, TempID, Context);
     544             :   }
     545             : 
     546             : public:
     547      126836 :   explicit ContextualFoldingSet(Ctx Context, unsigned Log2InitSize = 6)
     548      126836 :       : Super(Log2InitSize), Context(Context) {}
     549             : 
     550             :   Ctx getContext() const { return Context; }
     551             : };
     552             : 
     553             : //===----------------------------------------------------------------------===//
     554             : /// FoldingSetVector - This template class combines a FoldingSet and a vector
     555             : /// to provide the interface of FoldingSet but with deterministic iteration
     556             : /// order based on the insertion order. T must be a subclass of FoldingSetNode
     557             : /// and implement a Profile function.
     558             : template <class T, class VectorT = SmallVector<T*, 8>>
     559      111480 : class FoldingSetVector {
     560             :   FoldingSet<T> Set;
     561             :   VectorT Vector;
     562             : 
     563             : public:
     564      749776 :   explicit FoldingSetVector(unsigned Log2InitSize = 6) : Set(Log2InitSize) {}
     565             : 
     566             :   using iterator = pointee_iterator<typename VectorT::iterator>;
     567             : 
     568             :   iterator begin() { return Vector.begin(); }
     569             :   iterator end()   { return Vector.end(); }
     570             : 
     571             :   using const_iterator = pointee_iterator<typename VectorT::const_iterator>;
     572             : 
     573             :   const_iterator begin() const { return Vector.begin(); }
     574             :   const_iterator end()   const { return Vector.end(); }
     575             : 
     576             :   /// clear - Remove all nodes from the folding set.
     577             :   void clear() { Set.clear(); Vector.clear(); }
     578             : 
     579             :   /// FindNodeOrInsertPos - Look up the node specified by ID.  If it exists,
     580             :   /// return it.  If not, return the insertion token that will make insertion
     581             :   /// faster.
     582             :   T *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos) {
     583             :     return Set.FindNodeOrInsertPos(ID, InsertPos);
     584             :   }
     585             : 
     586             :   /// GetOrInsertNode - If there is an existing simple Node exactly
     587             :   /// equal to the specified node, return it.  Otherwise, insert 'N' and
     588             :   /// return it instead.
     589      203864 :   T *GetOrInsertNode(T *N) {
     590      203864 :     T *Result = Set.GetOrInsertNode(N);
     591      203864 :     if (Result == N) Vector.push_back(N);
     592      203864 :     return Result;
     593             :   }
     594             : 
     595             :   /// InsertNode - Insert the specified node into the folding set, knowing that
     596             :   /// it is not already in the folding set.  InsertPos must be obtained from
     597             :   /// FindNodeOrInsertPos.
     598     1000527 :   void InsertNode(T *N, void *InsertPos) {
     599     1000527 :     Set.InsertNode(N, InsertPos);
     600     1001528 :     Vector.push_back(N);
     601     1000527 :   }
     602             : 
     603             :   /// InsertNode - Insert the specified node into the folding set, knowing that
     604             :   /// it is not already in the folding set.
     605             :   void InsertNode(T *N) {
     606             :     Set.InsertNode(N);
     607             :     Vector.push_back(N);
     608             :   }
     609             : 
     610             :   /// size - Returns the number of nodes in the folding set.
     611      747382 :   unsigned size() const { return Set.size(); }
     612             : 
     613             :   /// empty - Returns true if there are no nodes in the folding set.
     614             :   bool empty() const { return Set.empty(); }
     615             : };
     616             : 
     617             : //===----------------------------------------------------------------------===//
     618             : /// FoldingSetIteratorImpl - This is the common iterator support shared by all
     619             : /// folding sets, which knows how to walk the folding set hash table.
     620             : class FoldingSetIteratorImpl {
     621             : protected:
     622             :   FoldingSetNode *NodePtr;
     623             : 
     624             :   FoldingSetIteratorImpl(void **Bucket);
     625             : 
     626             :   void advance();
     627             : 
     628             : public:
     629             :   bool operator==(const FoldingSetIteratorImpl &RHS) const {
     630             :     return NodePtr == RHS.NodePtr;
     631             :   }
     632             :   bool operator!=(const FoldingSetIteratorImpl &RHS) const {
     633      977870 :     return NodePtr != RHS.NodePtr;
     634             :   }
     635             : };
     636             : 
     637             : template <class T> class FoldingSetIterator : public FoldingSetIteratorImpl {
     638             : public:
     639      320066 :   explicit FoldingSetIterator(void **Bucket) : FoldingSetIteratorImpl(Bucket) {}
     640             : 
     641             :   T &operator*() const {
     642      243896 :     return *static_cast<T*>(NodePtr);
     643             :   }
     644             : 
     645             :   T *operator->() const {
     646             :     return static_cast<T*>(NodePtr);
     647             :   }
     648             : 
     649             :   inline FoldingSetIterator &operator++() {          // Preincrement
     650      817965 :     advance();
     651             :     return *this;
     652             :   }
     653             :   FoldingSetIterator operator++(int) {        // Postincrement
     654             :     FoldingSetIterator tmp = *this; ++*this; return tmp;
     655             :   }
     656             : };
     657             : 
     658             : //===----------------------------------------------------------------------===//
     659             : /// FoldingSetBucketIteratorImpl - This is the common bucket iterator support
     660             : /// shared by all folding sets, which knows how to walk a particular bucket
     661             : /// of a folding set hash table.
     662             : class FoldingSetBucketIteratorImpl {
     663             : protected:
     664             :   void *Ptr;
     665             : 
     666             :   explicit FoldingSetBucketIteratorImpl(void **Bucket);
     667             : 
     668             :   FoldingSetBucketIteratorImpl(void **Bucket, bool) : Ptr(Bucket) {}
     669             : 
     670             :   void advance() {
     671             :     void *Probe = static_cast<FoldingSetNode*>(Ptr)->getNextInBucket();
     672             :     uintptr_t x = reinterpret_cast<uintptr_t>(Probe) & ~0x1;
     673             :     Ptr = reinterpret_cast<void*>(x);
     674             :   }
     675             : 
     676             : public:
     677             :   bool operator==(const FoldingSetBucketIteratorImpl &RHS) const {
     678             :     return Ptr == RHS.Ptr;
     679             :   }
     680             :   bool operator!=(const FoldingSetBucketIteratorImpl &RHS) const {
     681             :     return Ptr != RHS.Ptr;
     682             :   }
     683             : };
     684             : 
     685             : template <class T>
     686             : class FoldingSetBucketIterator : public FoldingSetBucketIteratorImpl {
     687             : public:
     688             :   explicit FoldingSetBucketIterator(void **Bucket) :
     689             :     FoldingSetBucketIteratorImpl(Bucket) {}
     690             : 
     691             :   FoldingSetBucketIterator(void **Bucket, bool) :
     692             :     FoldingSetBucketIteratorImpl(Bucket, true) {}
     693             : 
     694             :   T &operator*() const { return *static_cast<T*>(Ptr); }
     695             :   T *operator->() const { return static_cast<T*>(Ptr); }
     696             : 
     697             :   inline FoldingSetBucketIterator &operator++() { // Preincrement
     698             :     advance();
     699             :     return *this;
     700             :   }
     701             :   FoldingSetBucketIterator operator++(int) {      // Postincrement
     702             :     FoldingSetBucketIterator tmp = *this; ++*this; return tmp;
     703             :   }
     704             : };
     705             : 
     706             : //===----------------------------------------------------------------------===//
     707             : /// FoldingSetNodeWrapper - This template class is used to "wrap" arbitrary
     708             : /// types in an enclosing object so that they can be inserted into FoldingSets.
     709             : template <typename T>
     710             : class FoldingSetNodeWrapper : public FoldingSetNode {
     711             :   T data;
     712             : 
     713             : public:
     714             :   template <typename... Ts>
     715       70017 :   explicit FoldingSetNodeWrapper(Ts &&... Args)
     716          99 :       : data(std::forward<Ts>(Args)...) {}
     717             : 
     718     1169020 :   void Profile(FoldingSetNodeID &ID) { FoldingSetTrait<T>::Profile(data, ID); }
     719             : 
     720        4269 :   T &getValue() { return data; }
     721             :   const T &getValue() const { return data; }
     722             : 
     723     1122435 :   operator T&() { return data; }
     724             :   operator const T&() const { return data; }
     725             : };
     726             : 
     727             : //===----------------------------------------------------------------------===//
     728             : /// FastFoldingSetNode - This is a subclass of FoldingSetNode which stores
     729             : /// a FoldingSetNodeID value rather than requiring the node to recompute it
     730             : /// each time it is needed. This trades space for speed (which can be
     731             : /// significant if the ID is long), and it also permits nodes to drop
     732             : /// information that would otherwise only be required for recomputing an ID.
     733             : class FastFoldingSetNode : public FoldingSetNode {
     734             :   FoldingSetNodeID FastID;
     735             : 
     736             : protected:
     737      188955 :   explicit FastFoldingSetNode(const FoldingSetNodeID &ID) : FastID(ID) {}
     738             : 
     739             : public:
     740      992226 :   void Profile(FoldingSetNodeID &ID) const { ID.AddNodeID(FastID); }
     741             : };
     742             : 
     743             : //===----------------------------------------------------------------------===//
     744             : // Partial specializations of FoldingSetTrait.
     745             : 
     746             : template<typename T> struct FoldingSetTrait<T*> {
     747             :   static inline void Profile(T *X, FoldingSetNodeID &ID) {
     748      115776 :     ID.AddPointer(X);
     749             :   }
     750             : };
     751             : template <typename T1, typename T2>
     752             : struct FoldingSetTrait<std::pair<T1, T2>> {
     753             :   static inline void Profile(const std::pair<T1, T2> &P,
     754             :                              FoldingSetNodeID &ID) {
     755        1767 :     ID.Add(P.first);
     756        1767 :     ID.Add(P.second);
     757             :   }
     758             : };
     759             : 
     760             : } // end namespace llvm
     761             : 
     762             : #endif // LLVM_ADT_FOLDINGSET_H

Generated by: LCOV version 1.13