LCOV - code coverage report
Current view: top level - include/llvm/ADT - FoldingSet.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 91 96 94.8 %
Date: 2017-09-14 15:23:50 Functions: 200 350 57.1 %
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             :   ///
     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    46730255 :     Node() : NextInFoldingSetBucket(nullptr) {}
     146             : 
     147             :     // Accessors
     148   112437902 :     void *getNextInBucket() const { return NextInFoldingSetBucket; }
     149   101907388 :     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           3 :   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    61987184 :     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    10155571 :     X.Profile(ID);
     228             :   }
     229             :   static void Profile(T &X, FoldingSetNodeID &ID) {
     230   147269937 :     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     8890464 :     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   417031647 :   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   494060446 : 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   496065248 :   FoldingSetNodeID() = default;
     318             : 
     319             :   FoldingSetNodeID(FoldingSetNodeIDRef Ref)
     320           0 :     : 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    76951277 :   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     3663413 :   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   167764416 :   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         172 :   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    10700852 : DefaultFoldingSetTrait<T>::Equals(T &X, const FoldingSetNodeID &ID,
     375             :                                   unsigned /*IDHash*/,
     376             :                                   FoldingSetNodeID &TempID) {
     377   122467800 :   FoldingSetTrait<T>::Profile(X, TempID);
     378   122467800 :   return TempID == ID;
     379             : }
     380             : template<typename T>
     381             : inline unsigned
     382     2839819 : DefaultFoldingSetTrait<T>::ComputeHash(T &X, FoldingSetNodeID &TempID) {
     383    17017763 :   FoldingSetTrait<T>::Profile(X, TempID);
     384    17017763 :   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     6737905 :   ContextualFoldingSetTrait<T, Ctx>::Profile(X, TempID, Context);
     394     6737905 :   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     2152559 :   ContextualFoldingSetTrait<T, Ctx>::Profile(X, TempID, Context);
     402     2152559 :   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     2411770 :   explicit FoldingSetImpl(unsigned Log2InitSize)
     411     2411770 :       : FoldingSetBase(Log2InitSize) {}
     412             : 
     413        2260 :   FoldingSetImpl(FoldingSetImpl &&Arg) = default;
     414             :   FoldingSetImpl &operator=(FoldingSetImpl &&RHS) = default;
     415     2229293 :   ~FoldingSetImpl() = default;
     416             : 
     417             : public:
     418             :   typedef FoldingSetIterator<T> iterator;
     419      250149 :   iterator begin() { return iterator(Buckets); }
     420      250280 :   iterator end() { return iterator(Buckets+NumBuckets); }
     421             : 
     422             :   typedef FoldingSetIterator<const T> const_iterator;
     423        2366 :   const_iterator begin() const { return const_iterator(Buckets); }
     424        2366 :   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    19254575 :   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     5385822 :     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   117713889 :     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    37229953 :     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        7253 :     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     4286050 : 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     5385822 :   void GetNodeProfile(Node *N, FoldingSetNodeID &ID) const override {
     486     5385822 :     T *TN = static_cast<T *>(N);
     487     5385822 :     FoldingSetTrait<T>::Profile(*TN, ID);
     488     5385822 :   }
     489             : 
     490             :   /// NodeEquals - Instantiations may optionally provide a way to compare a
     491             :   /// node with a specified ID.
     492   134578746 :   bool NodeEquals(Node *N, const FoldingSetNodeID &ID, unsigned IDHash,
     493             :                   FoldingSetNodeID &TempID) const override {
     494   134578746 :     T *TN = static_cast<T *>(N);
     495   258456643 :     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    17245190 :   unsigned ComputeNodeHash(Node *N, FoldingSetNodeID &TempID) const override {
     501    17245190 :     T *TN = static_cast<T *>(N);
     502    17471589 :     return FoldingSetTrait<T>::ComputeHash(*TN, TempID);
     503             :   }
     504             : 
     505             : public:
     506             :   explicit FoldingSet(unsigned Log2InitSize = 6)
     507     4646405 :       : Super(Log2InitSize) {}
     508             : 
     509        4520 :   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      172536 : 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           0 :   void GetNodeProfile(Node *N, FoldingSetNodeID &ID) const override {
     537           0 :     T *TN = static_cast<T *>(N);
     538           0 :     ContextualFoldingSetTrait<T, Ctx>::Profile(*TN, ID, Context);
     539           0 :   }
     540             : 
     541     6737905 :   bool NodeEquals(Node *N, const FoldingSetNodeID &ID, unsigned IDHash,
     542             :                   FoldingSetNodeID &TempID) const override {
     543     6737905 :     T *TN = static_cast<T *>(N);
     544     6737905 :     return ContextualFoldingSetTrait<T, Ctx>::Equals(*TN, ID, IDHash, TempID,
     545    13475810 :                                                      Context);
     546             :   }
     547             : 
     548     2152559 :   unsigned ComputeNodeHash(Node *N, FoldingSetNodeID &TempID) const override {
     549     2152559 :     T *TN = static_cast<T *>(N);
     550     4305118 :     return ContextualFoldingSetTrait<T, Ctx>::ComputeHash(*TN, TempID, Context);
     551             :   }
     552             : 
     553             : public:
     554       88568 :   explicit ContextualFoldingSet(Ctx Context, unsigned Log2InitSize = 6)
     555      177136 :   : 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      128661 : class FoldingSetVector {
     568             :   FoldingSet<T> Set;
     569             :   VectorT Vector;
     570             : 
     571             : public:
     572      196269 :   explicit FoldingSetVector(unsigned Log2InitSize = 6)
     573      588807 :       : Set(Log2InitSize) {
     574             :   }
     575             : 
     576             :   typedef pointee_iterator<typename VectorT::iterator> iterator;
     577      600828 :   iterator begin() { return Vector.begin(); }
     578      600822 :   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     1139293 :     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       70718 :   T *GetOrInsertNode(T *N) {
     598      141436 :     T *Result = Set.GetOrInsertNode(N);
     599       70718 :     if (Result == N) Vector.push_back(N);
     600       70718 :     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      247299 :   void InsertNode(T *N, void *InsertPos) {
     607      495410 :     Set.InsertNode(N, InsertPos);
     608      247705 :     Vector.push_back(N);
     609      247299 :   }
     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      193298 :   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      636679 :     return NodePtr != RHS.NodePtr;
     642             :   }
     643             : };
     644             : 
     645             : template <class T> class FoldingSetIterator : public FoldingSetIteratorImpl {
     646             : public:
     647      252580 :   explicit FoldingSetIterator(void **Bucket) : FoldingSetIteratorImpl(Bucket) {}
     648             : 
     649             :   T &operator*() const {
     650      161851 :     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      510421 :     advance();
     659             :     return *this;
     660             :   }
     661             :   FoldingSetIterator operator++(int) {        // Postincrement
     662      873986 :     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       50785 :   explicit FoldingSetNodeWrapper(Ts &&... Args)
     726      152278 :       : data(std::forward<Ts>(Args)...) {}
     727             : 
     728     2415829 :   void Profile(FoldingSetNodeID &ID) { FoldingSetTrait<T>::Profile(data, ID); }
     729             : 
     730        4183 :   T &getValue() { return data; }
     731             :   const T &getValue() const { return data; }
     732             : 
     733      945973 :   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      205437 :   explicit FastFoldingSetNode(const FoldingSetNodeID &ID) : FastID(ID) {}
     748             : 
     749             : public:
     750      370947 :   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      144373 :     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         284 :     ID.Add(P.first);
     766         284 :     ID.Add(P.second);
     767             :   }
     768             : };
     769             : 
     770             : } // end namespace llvm
     771             : 
     772             : #endif // LLVM_ADT_FOLDINGSET_H

Generated by: LCOV version 1.13