IR: Simplify uniquing for MDNode

Change uniquing from a `FoldingSet` to a `DenseSet` with custom
`DenseMapInfo`.  Unfortunately, this doesn't save any memory, since
`DenseSet<T>` is a simple wrapper for `DenseMap<T, char>`, but I'll come
back to fix that later.

I used the name `GenericDenseMapInfo` to the custom `DenseMapInfo` since
I'll be splitting `MDNode` into two classes soon: `MDNodeFwdDecl` for
temporaries, and `GenericMDNode` for everything else.

I also added a non-debug-info reduced version of a type-uniquing test
that started failing on an earlier draft of this patch.

Part of PR21532.

llvm-svn: 222191

6 files changed, 97 insertions, 77 deletions

diff --git a/llvm/include/llvm/IR/Metadata.h b/llvm/include/llvm/IR/Metadata.h
index 6f38013b877..3acf6c216bb 100644
--- a/llvm/include/llvm/IR/Metadata.h
+++ b/llvm/include/llvm/IR/Metadata.h
@@ -138,12 +138,11 @@ class MDNodeOperand;
 
 //===----------------------------------------------------------------------===//
 /// \brief Generic tuple of metadata.
-class MDNode : public Metadata, public FoldingSetNode {
+class MDNode : public Metadata {
   MDNode(const MDNode &) LLVM_DELETED_FUNCTION;
   void operator=(const MDNode &) LLVM_DELETED_FUNCTION;
   friend class MDNodeOperand;
   friend class LLVMContextImpl;
-  friend struct FoldingSetTrait<MDNode>;
 
   /// \brief If the MDNode is uniqued cache the hash to speed up lookup.
   unsigned Hash;
@@ -224,8 +223,8 @@ public:
   /// code because it recursively visits all the MDNode's operands.
   const Function *getFunction() const;
 
-  /// \brief Calculate a unique identifier for this MDNode.
-  void Profile(FoldingSetNodeID &ID) const;
+  /// \brief Get the hash, if any.
+  unsigned getHash() const { return Hash; }
 
   /// \brief Methods for support type inquiry through isa, cast, and dyn_cast:
   static bool classof(const Value *V) {
diff --git a/llvm/lib/IR/LLVMContextImpl.cpp b/llvm/lib/IR/LLVMContextImpl.cpp
index df3449d12c8..cd9da0d0e08 100644
--- a/llvm/lib/IR/LLVMContextImpl.cpp
+++ b/llvm/lib/IR/LLVMContextImpl.cpp
@@ -124,9 +124,7 @@ LLVMContextImpl::~LLVMContextImpl() {
   // and the NonUniquedMDNodes sets, so copy the values out first.
   SmallVector<MDNode*, 8> MDNodes;
   MDNodes.reserve(MDNodeSet.size() + NonUniquedMDNodes.size());
-  for (FoldingSetIterator<MDNode> I = MDNodeSet.begin(), E = MDNodeSet.end();
-       I != E; ++I)
-    MDNodes.push_back(&*I);
+  MDNodes.append(MDNodeSet.begin(), MDNodeSet.end());
   MDNodes.append(NonUniquedMDNodes.begin(), NonUniquedMDNodes.end());
   for (SmallVectorImpl<MDNode *>::iterator I = MDNodes.begin(),
          E = MDNodes.end(); I != E; ++I)
diff --git a/llvm/lib/IR/LLVMContextImpl.h b/llvm/lib/IR/LLVMContextImpl.h
index 3190c22fceb..48343b2989e 100644
--- a/llvm/lib/IR/LLVMContextImpl.h
+++ b/llvm/lib/IR/LLVMContextImpl.h
@@ -22,6 +22,7 @@
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/SmallPtrSet.h"
@@ -190,23 +191,52 @@ struct FunctionTypeKeyInfo {
   }
 };
 
-// Provide a FoldingSetTrait::Equals specialization for MDNode that can use a
-// shortcut to avoid comparing all operands.
-template<> struct FoldingSetTrait<MDNode> : DefaultFoldingSetTrait<MDNode> {
-  static bool Equals(const MDNode &X, const FoldingSetNodeID &ID,
-                     unsigned IDHash, FoldingSetNodeID &TempID) {
-    assert(!X.isNotUniqued() && "Non-uniqued MDNode in FoldingSet?");
-    // First, check if the cached hashes match.  If they don't we can skip the
-    // expensive operand walk.
-    if (X.Hash != IDHash)
-      return false;
+/// \brief DenseMapInfo for MDNode.
+///
+/// Note that we don't need the is-function-local bit, since that's implicit in
+/// the operands.
+struct GenericMDNodeInfo {
+  struct KeyTy {
+    ArrayRef<Value *> Ops;
+    unsigned Hash;
+
+    KeyTy(ArrayRef<Value *> Ops)
+        : Ops(Ops), Hash(hash_combine_range(Ops.begin(), Ops.end())) {}
+
+    KeyTy(MDNode *N, SmallVectorImpl<Value *> &Storage) {
+      Storage.resize(N->getNumOperands());
+      for (unsigned I = 0, E = N->getNumOperands(); I != E; ++I)
+        Storage[I] = N->getOperand(I);
+      Ops = Storage;
+      Hash = hash_combine_range(Ops.begin(), Ops.end());
+    }
 
-    // If they match we have to compare the operands.
-    X.Profile(TempID);
-    return TempID == ID;
+    bool operator==(const MDNode *RHS) const {
+      if (RHS == getEmptyKey() || RHS == getTombstoneKey())
+        return false;
+      if (Hash != RHS->getHash() || Ops.size() != RHS->getNumOperands())
+        return false;
+      for (unsigned I = 0, E = Ops.size(); I != E; ++I)
+        if (Ops[I] != RHS->getOperand(I))
+          return false;
+      return true;
+    }
+  };
+  static inline MDNode *getEmptyKey() {
+    return DenseMapInfo<MDNode *>::getEmptyKey();
+  }
+  static inline MDNode *getTombstoneKey() {
+    return DenseMapInfo<MDNode *>::getTombstoneKey();
+  }
+  static unsigned getHashValue(const KeyTy &Key) { return Key.Hash; }
+  static unsigned getHashValue(const MDNode *U) {
+    return U->getHash();
   }
-  static unsigned ComputeHash(const MDNode &X, FoldingSetNodeID &) {
-    return X.Hash; // Return cached hash.
+  static bool isEqual(const KeyTy &LHS, const MDNode *RHS) {
+    return LHS == RHS;
+  }
+  static bool isEqual(const MDNode *LHS, const MDNode *RHS) {
+    return LHS == RHS;
   }
 };
 
@@ -263,7 +293,7 @@ public:
 
   StringMap<MDString> MDStringCache;
 
-  FoldingSet<MDNode> MDNodeSet;
+  DenseSet<MDNode *, GenericMDNodeInfo> MDNodeSet;
 
   // MDNodes may be uniqued or not uniqued.  When they're not uniqued, they
   // aren't in the MDNodeSet, but they're still shared between objects, so no
diff --git a/llvm/lib/IR/Metadata.cpp b/llvm/lib/IR/Metadata.cpp
index cdd106033f8..e15317445f9 100644
--- a/llvm/lib/IR/Metadata.cpp
+++ b/llvm/lib/IR/Metadata.cpp
@@ -119,7 +119,7 @@ void MDNode::replaceOperandWith(unsigned i, Value *Val) {
 }
 
 MDNode::MDNode(LLVMContext &C, ArrayRef<Value *> Vals, bool isFunctionLocal)
-    : Metadata(C, Value::MDNodeVal) {
+    : Metadata(C, Value::MDNodeVal), Hash(0) {
   NumOperands = Vals.size();
 
   if (isFunctionLocal)
@@ -145,7 +145,7 @@ MDNode::~MDNode() {
   if (isNotUniqued()) {
     pImpl->NonUniquedMDNodes.erase(this);
   } else {
-    pImpl->MDNodeSet.RemoveNode(this);
+    pImpl->MDNodeSet.erase(this);
   }
 
   // Destroy the operands.
@@ -224,21 +224,14 @@ static bool isFunctionLocalValue(Value *V) {
 
 MDNode *MDNode::getMDNode(LLVMContext &Context, ArrayRef<Value*> Vals,
                           FunctionLocalness FL, bool Insert) {
-  LLVMContextImpl *pImpl = Context.pImpl;
+  auto &Store = Context.pImpl->MDNodeSet;
 
-  // Add all the operand pointers. Note that we don't have to add the
-  // isFunctionLocal bit because that's implied by the operands.
-  // Note that if the operands are later nulled out, the node will be
-  // removed from the uniquing map.
-  FoldingSetNodeID ID;
-  for (Value *V : Vals)
-    ID.AddPointer(V);
-
-  void *InsertPoint;
-  MDNode *N = pImpl->MDNodeSet.FindNodeOrInsertPos(ID, InsertPoint);
-
-  if (N || !Insert)
-    return N;
+  GenericMDNodeInfo::KeyTy Key(Vals);
+  auto I = Store.find_as(Key);
+  if (I != Store.end())
+    return *I;
+  if (!Insert)
+    return nullptr;
 
   bool isFunctionLocal = false;
   switch (FL) {
@@ -261,14 +254,10 @@ MDNode *MDNode::getMDNode(LLVMContext &Context, ArrayRef<Value*> Vals,
 
   // Coallocate space for the node and Operands together, then placement new.
   void *Ptr = malloc(sizeof(MDNode) + Vals.size() * sizeof(MDNodeOperand));
-  N = new (Ptr) MDNode(Context, Vals, isFunctionLocal);
-
-  // Cache the operand hash.
-  N->Hash = ID.ComputeHash();
-
-  // InsertPoint will have been set by the FindNodeOrInsertPos call.
-  pImpl->MDNodeSet.InsertNode(N, InsertPoint);
+  MDNode *N = new (Ptr) MDNode(Context, Vals, isFunctionLocal);
 
+  N->Hash = Key.Hash;
+  Store.insert(N);
   return N;
 }
 
@@ -298,7 +287,7 @@ MDNode *MDNode::getTemporary(LLVMContext &Context, ArrayRef<Value*> Vals) {
 
 void MDNode::deleteTemporary(MDNode *N) {
   assert(N->use_empty() && "Temporary MDNode has uses!");
-  assert(!N->getContext().pImpl->MDNodeSet.RemoveNode(N) &&
+  assert(!N->getContext().pImpl->MDNodeSet.erase(N) &&
          "Deleting a non-temporary uniqued node!");
   assert(!N->getContext().pImpl->NonUniquedMDNodes.erase(N) &&
          "Deleting a non-temporary non-uniqued node!");
@@ -316,18 +305,10 @@ Value *MDNode::getOperand(unsigned i) const {
   return *getOperandPtr(const_cast<MDNode*>(this), i);
 }
 
-void MDNode::Profile(FoldingSetNodeID &ID) const {
-  // Add all the operand pointers. Note that we don't have to add the
-  // isFunctionLocal bit because that's implied by the operands.
-  // Note that if the operands are later nulled out, the node will be
-  // removed from the uniquing map.
-  for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
-    ID.AddPointer(getOperand(i));
-}
-
 void MDNode::setIsNotUniqued() {
   setValueSubclassData(getSubclassDataFromValue() | NotUniquedBit);
   LLVMContextImpl *pImpl = getType()->getContext().pImpl;
+  Hash = 0;
   pImpl->NonUniquedMDNodes.insert(this);
 }
 
@@ -356,44 +337,44 @@ void MDNode::replaceOperand(MDNodeOperand *Op, Value *To) {
   if (From == To)
     return;
 
-  // Update the operand.
-  Op->set(To);
-
   // If this node is already not being uniqued (because one of the operands
   // already went to null), then there is nothing else to do here.
-  if (isNotUniqued()) return;
+  if (isNotUniqued()) {
+    Op->set(To);
+    return;
+  }
 
-  LLVMContextImpl *pImpl = getType()->getContext().pImpl;
+  auto &Store = getContext().pImpl->MDNodeSet;
+
+  // Remove "this" from the context map.
+  Store.erase(this);
 
-  // Remove "this" from the context map.  FoldingSet doesn't have to reprofile
-  // this node to remove it, so we don't care what state the operands are in.
-  pImpl->MDNodeSet.RemoveNode(this);
+  // Update the operand.
+  Op->set(To);
 
   // If we are dropping an argument to null, we choose to not unique the MDNode
   // anymore.  This commonly occurs during destruction, and uniquing these
   // brings little reuse.  Also, this means we don't need to include
-  // isFunctionLocal bits in FoldingSetNodeIDs for MDNodes.
+  // isFunctionLocal bits in the hash for MDNodes.
   if (!To) {
     setIsNotUniqued();
     return;
   }
 
-  // Now that the node is out of the folding set, get ready to reinsert it.
-  // First, check to see if another node with the same operands already exists
-  // in the set.  If so, then this node is redundant.
-  FoldingSetNodeID ID;
-  Profile(ID);
-  void *InsertPoint;
-  if (MDNode *N = pImpl->MDNodeSet.FindNodeOrInsertPos(ID, InsertPoint)) {
-    replaceAllUsesWith(N);
+  // Now that the node is out of the table, get ready to reinsert it.  First,
+  // check to see if another node with the same operands already exists in the
+  // set.  If so, then this node is redundant.
+  SmallVector<Value *, 8> Vals;
+  GenericMDNodeInfo::KeyTy Key(this, Vals);
+  auto I = Store.find_as(Key);
+  if (I != Store.end()) {
+    replaceAllUsesWith(*I);
     destroy();
     return;
   }
 
-  // Cache the operand hash.
-  Hash = ID.ComputeHash();
-  // InsertPoint will have been set by the FindNodeOrInsertPos call.
-  pImpl->MDNodeSet.InsertNode(this, InsertPoint);
+  this->Hash = Key.Hash;
+  Store.insert(this);
 
   // If this MDValue was previously function-local but no longer is, clear
   // its function-local flag.
diff --git a/llvm/test/Linker/Inputs/unique-fwd-decl-b.ll b/llvm/test/Linker/Inputs/unique-fwd-decl-b.ll
new file mode 100644
index 00000000000..240fbeea34b
--- /dev/null
+++ b/llvm/test/Linker/Inputs/unique-fwd-decl-b.ll
@@ -0,0 +1,3 @@
+!b = !{!0}
+!0 = metadata !{metadata !1}
+!1 = metadata !{}
diff --git a/llvm/test/Linker/unique-fwd-decl-a.ll b/llvm/test/Linker/unique-fwd-decl-a.ll
new file mode 100644
index 00000000000..b9c7b2faac5
--- /dev/null
+++ b/llvm/test/Linker/unique-fwd-decl-a.ll
@@ -0,0 +1,9 @@
+; RUN: llvm-link %s %S/Inputs/unique-fwd-decl-b.ll -S -o - | FileCheck %s
+
+; Test that the arguments of !a and !b get uniqued.
+; CHECK: !a = !{!0}
+; CHECK: !b = !{!0}
+
+!a = !{!0}
+!0 = metadata !{metadata !1}
+!1 = metadata !{}