Remove vptr dispatch from FoldingSet.

[rsmith]

Summary

Instead of storing a vptr in each FoldingSet instance, form an
equivalent struct and pass it implicitly from FoldingSet into the
various FoldingSetBase methods.

This has three benefits:

• FoldingSet becomes one pointer smaller.
• Under LTO, the "virtual" functions are much easier to inline.
• The element type no longer needs to be complete when instantiating FoldingSet<T>, only when instantiating an insert / lookup member.

[rsmith]

Remove unused changes to function_ref.

[rnk]

lgtm

llvm/include/llvm/ADT/FoldingSet.h

493

final seems a bit superfluous now that it is not dynamic.

llvm/include/llvm/ADT/FoldingSet.h

 //===----------------------------------------------------------------------===//
 /// FoldingSetBase - Implements the folding set functionality.  The main
 /// structure is an array of buckets.  Each bucket is indexed by the hash of
 /// the nodes it contains.  The bucket itself points to the nodes contained
 /// in the bucket via a singly linked list.  The last node in the list points
 /// back to the bucket to facilitate node removal.
 ///
 class FoldingSetBase {
-  virtual void anchor(); // Out of line virtual method.
-
 protected:
   /// Buckets - Array of bucket chains.
   void **Buckets;
 
   /// NumBuckets - Length of the Buckets array.  Always a power of 2.
   unsigned NumBuckets;
 
   /// NumNodes - Number of nodes in the folding set. Growth occurs when NumNodes
public:
   void clear();
 
   /// size - Returns the number of nodes in the folding set.
   unsigned size() const { return NumNodes; }
 
   /// empty - Returns true if there are no nodes in the folding set.
   bool empty() const { return NumNodes == 0; }
 
-  /// reserve - Increase the number of buckets such that adding the
-  /// EltCount-th node won't cause a rebucket operation. reserve is permitted
-  /// to allocate more space than requested by EltCount.
-  void reserve(unsigned EltCount);
-
   /// capacity - Returns the number of nodes permitted in the folding set
   /// before a rebucket operation is performed.
   unsigned capacity() {
     // We allow a load factor of up to 2.0,
     // so that means our capacity is NumBuckets * 2
     return NumBuckets * 2;
   }
 
-private:
-  /// GrowHashTable - Double the size of the hash table and rehash everything.
-  void GrowHashTable();
-
-  /// GrowBucketCount - resize the hash table and rehash everything.
-  /// NewBucketCount must be a power of two, and must be greater than the old
-  /// bucket count.
-  void GrowBucketCount(unsigned NewBucketCount);
-
 protected:
+  /// Functions provided by the derived class to compute folding properties.
+  /// This is effectively a vtable for FoldingSetBase, except that we don't
+  /// actually store a pointer to it in the object.
+  struct FoldingSetInfo {
     /// GetNodeProfile - Instantiations of the FoldingSet template implement
     /// this function to gather data bits for the given node.
-  virtual void GetNodeProfile(Node *N, FoldingSetNodeID &ID) const = 0;
+    void (*GetNodeProfile)(const FoldingSetBase *Self, Node *N,
+                           FoldingSetNodeID &ID);
 
     /// NodeEquals - Instantiations of the FoldingSet template implement
     /// this function to compare the given node with the given ID.
-  virtual bool NodeEquals(Node *N, const FoldingSetNodeID &ID, unsigned IDHash,
-                          FoldingSetNodeID &TempID) const=0;
+    bool (*NodeEquals)(const FoldingSetBase *Self, Node *N,
+                       const FoldingSetNodeID &ID, unsigned IDHash,
+                       FoldingSetNodeID &TempID);
 
     /// ComputeNodeHash - Instantiations of the FoldingSet template implement
     /// this function to compute a hash value for the given node.
-  virtual unsigned ComputeNodeHash(Node *N, FoldingSetNodeID &TempID) const = 0;
+    unsigned (*ComputeNodeHash)(const FoldingSetBase *Self, Node *N,
+                                FoldingSetNodeID &TempID);
+  };
+
+private:
+  /// GrowHashTable - Double the size of the hash table and rehash everything.
+  void GrowHashTable(const FoldingSetInfo &Info);
 
+  /// GrowBucketCount - resize the hash table and rehash everything.
+  /// NewBucketCount must be a power of two, and must be greater than the old
+  /// bucket count.
+  void GrowBucketCount(unsigned NewBucketCount, const FoldingSetInfo &Info);
+
+protected:
   // The below methods are protected to encourage subclasses to provide a more
   // type-safe API.
 
+  /// reserve - Increase the number of buckets such that adding the
+  /// EltCount-th node won't cause a rebucket operation. reserve is permitted
+  /// to allocate more space than requested by EltCount.
+  void reserve(unsigned EltCount, const FoldingSetInfo &Info);
+
   /// RemoveNode - Remove a node from the folding set, returning true if one
   /// was removed or false if the node was not in the folding set.
   bool RemoveNode(Node *N);
 
   /// GetOrInsertNode - If there is an existing simple Node exactly
   /// equal to the specified node, return it.  Otherwise, insert 'N' and return
   /// it instead.
-  Node *GetOrInsertNode(Node *N);
+  Node *GetOrInsertNode(Node *N, const FoldingSetInfo &Info);
 
   /// FindNodeOrInsertPos - Look up the node specified by ID.  If it exists,
   /// return it.  If not, return the insertion token that will make insertion
   /// faster.
-  Node *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos);
+  Node *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos,
+                            const FoldingSetInfo &Info);
 
   /// InsertNode - Insert the specified node into the folding set, knowing that
   /// it is not already in the folding set.  InsertPos must be obtained from
   /// FindNodeOrInsertPos.
-  void InsertNode(Node *N, void *InsertPos);
+  void InsertNode(Node *N, void *InsertPos, const FoldingSetInfo &Info);
 };
 
 //===----------------------------------------------------------------------===//
 
 /// DefaultFoldingSetTrait - This class provides default implementations
 /// for FoldingSetTrait implementations.
 template<typename T> struct DefaultFoldingSetTrait {
   static void Profile(const T &X, FoldingSetNodeID &ID) {
DefaultContextualFoldingSetTrait<T, Ctx>::ComputeHash(T &X,
                                                       Ctx Context) {
   ContextualFoldingSetTrait<T, Ctx>::Profile(X, TempID, Context);
   return TempID.ComputeHash();
 }
 
 //===----------------------------------------------------------------------===//
 /// FoldingSetImpl - An implementation detail that lets us share code between
 /// FoldingSet and ContextualFoldingSet.
-template <class T> class FoldingSetImpl : public FoldingSetBase {
+template <class Derived, class T> class FoldingSetImpl : public FoldingSetBase {
 protected:
   explicit FoldingSetImpl(unsigned Log2InitSize)
       : FoldingSetBase(Log2InitSize) {}
 
   FoldingSetImpl(FoldingSetImpl &&Arg) = default;
   FoldingSetImpl &operator=(FoldingSetImpl &&RHS) = default;
   ~FoldingSetImpl() = default;
 
public:
   bucket_iterator bucket_begin(unsigned hash) {
     return bucket_iterator(Buckets + (hash & (NumBuckets-1)));
   }
 
   bucket_iterator bucket_end(unsigned hash) {
     return bucket_iterator(Buckets + (hash & (NumBuckets-1)), true);
   }
 
+  /// reserve - Increase the number of buckets such that adding the
+  /// EltCount-th node won't cause a rebucket operation. reserve is permitted
+  /// to allocate more space than requested by EltCount.
+  void reserve(unsigned EltCount) {
+    return FoldingSetBase::reserve(EltCount, Derived::getFoldingSetInfo());
+  }
+
   /// RemoveNode - Remove a node from the folding set, returning true if one
   /// was removed or false if the node was not in the folding set.
-  bool RemoveNode(T *N) { return FoldingSetBase::RemoveNode(N); }
+  bool RemoveNode(T *N) {
+    return FoldingSetBase::RemoveNode(N);
+  }
 
   /// GetOrInsertNode - If there is an existing simple Node exactly
   /// equal to the specified node, return it.  Otherwise, insert 'N' and
   /// return it instead.
   T *GetOrInsertNode(T *N) {
-    return static_cast<T *>(FoldingSetBase::GetOrInsertNode(N));
+    return static_cast<T *>(
+        FoldingSetBase::GetOrInsertNode(N, Derived::getFoldingSetInfo()));
   }
 
   /// FindNodeOrInsertPos - Look up the node specified by ID.  If it exists,
   /// return it.  If not, return the insertion token that will make insertion
   /// faster.
   T *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos) {
-    return static_cast<T *>(FoldingSetBase::FindNodeOrInsertPos(ID, InsertPos));
+    return static_cast<T *>(FoldingSetBase::FindNodeOrInsertPos(
+        ID, InsertPos, Derived::getFoldingSetInfo()));
   }
 
   /// InsertNode - Insert the specified node into the folding set, knowing that
   /// it is not already in the folding set.  InsertPos must be obtained from
   /// FindNodeOrInsertPos.
   void InsertNode(T *N, void *InsertPos) {
-    FoldingSetBase::InsertNode(N, InsertPos);
+    FoldingSetBase::InsertNode(N, InsertPos, Derived::getFoldingSetInfo());
   }
 
   /// InsertNode - Insert the specified node into the folding set, knowing that
   /// it is not already in the folding set.
   void InsertNode(T *N) {
     T *Inserted = GetOrInsertNode(N);
     (void)Inserted;
     assert(Inserted == N && "Node already inserted!");
   }
 };
 
 //===----------------------------------------------------------------------===//
 /// FoldingSet - This template class is used to instantiate a specialized
 /// implementation of the folding set to the node class T.  T must be a
 /// subclass of FoldingSetNode and implement a Profile function.
 ///
 /// Note that this set type is movable and move-assignable. However, its
 /// moved-from state is not a valid state for anything other than
 /// move-assigning and destroying. This is primarily to enable movable APIs
 /// that incorporate these objects.
-template <class T> class FoldingSet final : public FoldingSetImpl<T> {
-  using Super = FoldingSetImpl<T>;
+template <class T>
+class FoldingSet final : public FoldingSetImpl<FoldingSet<T>, T> {
+  using Super = FoldingSetImpl<FoldingSet, T>;
   using Node = typename Super::Node;
 
   /// GetNodeProfile - Each instantiatation of the FoldingSet needs to provide a
   /// way to convert nodes into a unique specifier.
-  void GetNodeProfile(Node *N, FoldingSetNodeID &ID) const override {
+  static void GetNodeProfile(const FoldingSetBase *, Node *N,
+                             FoldingSetNodeID &ID) {
     T *TN = static_cast<T *>(N);
     FoldingSetTrait<T>::Profile(*TN, ID);
   }
 
   /// NodeEquals - Instantiations may optionally provide a way to compare a
   /// node with a specified ID.
-  bool NodeEquals(Node *N, const FoldingSetNodeID &ID, unsigned IDHash,
-                  FoldingSetNodeID &TempID) const override {
+  static bool NodeEquals(const FoldingSetBase *, Node *N,
+                         const FoldingSetNodeID &ID, unsigned IDHash,
+                         FoldingSetNodeID &TempID) {
     T *TN = static_cast<T *>(N);
     return FoldingSetTrait<T>::Equals(*TN, ID, IDHash, TempID);
   }
 
   /// ComputeNodeHash - Instantiations may optionally provide a way to compute a
   /// hash value directly from a node.
-  unsigned ComputeNodeHash(Node *N, FoldingSetNodeID &TempID) const override {
+  static unsigned ComputeNodeHash(const FoldingSetBase *, Node *N,
+                                  FoldingSetNodeID &TempID) {
     T *TN = static_cast<T *>(N);
     return FoldingSetTrait<T>::ComputeHash(*TN, TempID);
   }
 
+  static const FoldingSetBase::FoldingSetInfo &getFoldingSetInfo() {
+    static constexpr FoldingSetBase::FoldingSetInfo Info = {
+        GetNodeProfile, NodeEquals, ComputeNodeHash};
+    return Info;
+  }
+  friend Super;
+
 public:
   explicit FoldingSet(unsigned Log2InitSize = 6) : Super(Log2InitSize) {}
   FoldingSet(FoldingSet &&Arg) = default;
   FoldingSet &operator=(FoldingSet &&RHS) = default;
 };
 
 //===----------------------------------------------------------------------===//
 /// ContextualFoldingSet - This template class is a further refinement
 /// of FoldingSet which provides a context argument when calling
 /// Profile on its nodes.  Currently, that argument is fixed at
 /// initialization time.
 ///
 /// T must be a subclass of FoldingSetNode and implement a Profile
 /// function with signature
 ///   void Profile(FoldingSetNodeID &, Ctx);
 template <class T, class Ctx>
-class ContextualFoldingSet final : public FoldingSetImpl<T> {
+class ContextualFoldingSet final
+    : public FoldingSetImpl<ContextualFoldingSet<T, Ctx>, T> {
   // Unfortunately, this can't derive from FoldingSet<T> because the
   // construction of the vtable for FoldingSet<T> requires
   // FoldingSet<T>::GetNodeProfile to be instantiated, which in turn
   // requires a single-argument T::Profile().
 
-  using Super = FoldingSetImpl<T>;
+  using Super = FoldingSetImpl<ContextualFoldingSet, T>;
   using Node = typename Super::Node;
 
   Ctx Context;
 
+  static const Ctx &getContext(const FoldingSetBase *Base) {
+    return static_cast<const ContextualFoldingSet*>(Base)->Context;
+  }
+
   /// GetNodeProfile - Each instantiatation of the FoldingSet needs to provide a
   /// way to convert nodes into a unique specifier.
-  void GetNodeProfile(Node *N, FoldingSetNodeID &ID) const override {
+  static void GetNodeProfile(const FoldingSetBase *Base, Node *N,
+                             FoldingSetNodeID &ID) {
     T *TN = static_cast<T *>(N);
-    ContextualFoldingSetTrait<T, Ctx>::Profile(*TN, ID, Context);
+    ContextualFoldingSetTrait<T, Ctx>::Profile(*TN, ID, getContext(Base));
   }
 
-  bool NodeEquals(Node *N, const FoldingSetNodeID &ID, unsigned IDHash,
-                  FoldingSetNodeID &TempID) const override {
+  static bool NodeEquals(const FoldingSetBase *Base, Node *N,
+                         const FoldingSetNodeID &ID, unsigned IDHash,
+                         FoldingSetNodeID &TempID) {
     T *TN = static_cast<T *>(N);
     return ContextualFoldingSetTrait<T, Ctx>::Equals(*TN, ID, IDHash, TempID,
-                                                     Context);
+                                                     getContext(Base));
   }
 
-  unsigned ComputeNodeHash(Node *N, FoldingSetNodeID &TempID) const override {
+  static unsigned ComputeNodeHash(const FoldingSetBase *Base, Node *N,
+                                  FoldingSetNodeID &TempID) {
     T *TN = static_cast<T *>(N);
-    return ContextualFoldingSetTrait<T, Ctx>::ComputeHash(*TN, TempID, Context);
+    return ContextualFoldingSetTrait<T, Ctx>::ComputeHash(*TN, TempID,
+                                                          getContext(Base));
+  }
+
+  static const FoldingSetBase::FoldingSetInfo &getFoldingSetInfo() {
+    static constexpr FoldingSetBase::FoldingSetInfo Info = {
+        GetNodeProfile, NodeEquals, ComputeNodeHash};
+    return Info;
   }
+  friend Super;
 
 public:
   explicit ContextualFoldingSet(Ctx Context, unsigned Log2InitSize = 6)
       : Super(Log2InitSize), Context(Context) {}
 
   Ctx getContext() const { return Context; }
 };
 

llvm/lib/Support/FoldingSet.cpp

static void **AllocateBuckets(unsigned NumBuckets) {
   // Set the very last bucket to be a non-null "pointer".
   Buckets[NumBuckets] = reinterpret_cast<void*>(-1);
   return Buckets;
 }
 
 //===----------------------------------------------------------------------===//
 // FoldingSetBase Implementation
 
-void FoldingSetBase::anchor() {}
-
 FoldingSetBase::FoldingSetBase(unsigned Log2InitSize) {
   assert(5 < Log2InitSize && Log2InitSize < 32 &&
          "Initial hash table size out of range");
   NumBuckets = 1 << Log2InitSize;
   Buckets = AllocateBuckets(NumBuckets);
   NumNodes = 0;
 }
 
void FoldingSetBase::clear() {
 
   // Set the very last bucket to be a non-null "pointer".
   Buckets[NumBuckets] = reinterpret_cast<void*>(-1);
 
   // Reset the node count to zero.
   NumNodes = 0;
 }
 
-void FoldingSetBase::GrowBucketCount(unsigned NewBucketCount) {
-  assert((NewBucketCount > NumBuckets) && "Can't shrink a folding set with GrowBucketCount");
+void FoldingSetBase::GrowBucketCount(unsigned NewBucketCount,
+                                     const FoldingSetInfo &Info) {
+  assert((NewBucketCount > NumBuckets) &&
+         "Can't shrink a folding set with GrowBucketCount");
   assert(isPowerOf2_32(NewBucketCount) && "Bad bucket count!");
   void **OldBuckets = Buckets;
   unsigned OldNumBuckets = NumBuckets;
 
   // Clear out new buckets.
   Buckets = AllocateBuckets(NewBucketCount);
   // Set NumBuckets only if allocation of new buckets was successful.
   NumBuckets = NewBucketCount;
   NumNodes = 0;
 
   // Walk the old buckets, rehashing nodes into their new place.
   FoldingSetNodeID TempID;
   for (unsigned i = 0; i != OldNumBuckets; ++i) {
     void *Probe = OldBuckets[i];
     if (!Probe) continue;
     while (Node *NodeInBucket = GetNextPtr(Probe)) {
       // Figure out the next link, remove NodeInBucket from the old link.
       Probe = NodeInBucket->getNextInBucket();
       NodeInBucket->SetNextInBucket(nullptr);
 
       // Insert the node into the new bucket, after recomputing the hash.
       InsertNode(NodeInBucket,
-                 GetBucketFor(ComputeNodeHash(NodeInBucket, TempID),
-                              Buckets, NumBuckets));
+                 GetBucketFor(Info.ComputeNodeHash(this, NodeInBucket, TempID),
+                              Buckets, NumBuckets),
+                 Info);
       TempID.clear();
     }
   }
 
   free(OldBuckets);
 }
 
 /// GrowHashTable - Double the size of the hash table and rehash everything.
 ///
-void FoldingSetBase::GrowHashTable() {
-  GrowBucketCount(NumBuckets * 2);
+void FoldingSetBase::GrowHashTable(const FoldingSetInfo &Info) {
+  GrowBucketCount(NumBuckets * 2, Info);
 }
 
-void FoldingSetBase::reserve(unsigned EltCount) {
+void FoldingSetBase::reserve(unsigned EltCount, const FoldingSetInfo &Info) {
   // This will give us somewhere between EltCount / 2 and
   // EltCount buckets.  This puts us in the load factor
   // range of 1.0 - 2.0.
   if(EltCount < capacity())
     return;
-  GrowBucketCount(PowerOf2Floor(EltCount));
+  GrowBucketCount(PowerOf2Floor(EltCount), Info);
 }
 
 /// FindNodeOrInsertPos - Look up the node specified by ID.  If it exists,
 /// return it.  If not, return the insertion token that will make insertion
 /// faster.
-FoldingSetBase::Node *
-FoldingSetBase::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
-                                    void *&InsertPos) {
+FoldingSetBase::Node *FoldingSetBase::FindNodeOrInsertPos(
+    const FoldingSetNodeID &ID, void *&InsertPos, const FoldingSetInfo &Info) {
   unsigned IDHash = ID.ComputeHash();
   void **Bucket = GetBucketFor(IDHash, Buckets, NumBuckets);
   void *Probe = *Bucket;
 
   InsertPos = nullptr;
 
   FoldingSetNodeID TempID;
   while (Node *NodeInBucket = GetNextPtr(Probe)) {
-    if (NodeEquals(NodeInBucket, ID, IDHash, TempID))
+    if (Info.NodeEquals(this, NodeInBucket, ID, IDHash, TempID))
       return NodeInBucket;
     TempID.clear();
 
     Probe = NodeInBucket->getNextInBucket();
   }
 
   // Didn't find the node, return null with the bucket as the InsertPos.
   InsertPos = Bucket;
   return nullptr;
 }
 
 /// InsertNode - Insert the specified node into the folding set, knowing that it
 /// is not already in the map.  InsertPos must be obtained from
 /// FindNodeOrInsertPos.
-void FoldingSetBase::InsertNode(Node *N, void *InsertPos) {
+void FoldingSetBase::InsertNode(Node *N, void *InsertPos,
+                                const FoldingSetInfo &Info) {
   assert(!N->getNextInBucket());
   // Do we need to grow the hashtable?
   if (NumNodes+1 > capacity()) {
-    GrowHashTable();
+    GrowHashTable(Info);
     FoldingSetNodeID TempID;
-    InsertPos = GetBucketFor(ComputeNodeHash(N, TempID), Buckets, NumBuckets);
+    InsertPos = GetBucketFor(Info.ComputeNodeHash(this, N, TempID), Buckets,
+                             NumBuckets);
   }
 
   ++NumNodes;
 
   /// The insert position is actually a bucket pointer.
   void **Bucket = static_cast<void**>(InsertPos);
 
   void *Next = *Bucket;
if (Node *NodeInBucket = GetNextPtr(Ptr)) {
       }
     }
   }
 }
 
 /// GetOrInsertNode - If there is an existing simple Node exactly
 /// equal to the specified node, return it.  Otherwise, insert 'N' and it
 /// instead.
-FoldingSetBase::Node *FoldingSetBase::GetOrInsertNode(FoldingSetBase::Node *N) {
+FoldingSetBase::Node *
+FoldingSetBase::GetOrInsertNode(FoldingSetBase::Node *N,
+                                const FoldingSetInfo &Info) {
   FoldingSetNodeID ID;
-  GetNodeProfile(N, ID);
+  Info.GetNodeProfile(this, N, ID);
   void *IP;
-  if (Node *E = FindNodeOrInsertPos(ID, IP))
+  if (Node *E = FindNodeOrInsertPos(ID, IP, Info))
     return E;
-  InsertNode(N, IP);
+  InsertNode(N, IP, Info);
   return N;
 }
 
 //===----------------------------------------------------------------------===//
 // FoldingSetIteratorImpl Implementation
 
 FoldingSetIteratorImpl::FoldingSetIteratorImpl(void **Bucket) {
   // Skip to the first non-null non-self-cycle bucket.