Cache the hash value of the operands in the MDNode.

FoldingSet is implemented as a chained hash table. When there is a hash
collision during insertion, which is common as we fill the table until a
load factor of 2.0 is hit, we walk the chained elements, comparing every
operand with the new element's operands. This can be very expensive if the
MDNode has many operands.

We sacrifice a word of space in MDNode to cache the full hash value, reducing
compares on collision to a minimum. MDNode grows from 28 to 32 bytes + operands
on x86. On x86_64 the new bits fit nicely into existing padding, not growing
the struct at all.

The actual speedup depends a lot on the test case and is typically between
1% and 2% for C++ code with clang -c -O0 -g.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@154497 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/include/llvm/Metadata.h b/include/llvm/Metadata.h
index 0d438522ab1f659c15cfb5e68b18aa14cf4e79ab..7f232a3c98629c6e5ecdc7c358892c7ff4d6be51 100644 (file)
--- a/include/llvm/Metadata.h
+++ b/include/llvm/Metadata.h
@@ -75,6 +75,10 @@ class MDNode : public Value, public FoldingSetNode {
   void operator=(const MDNode &);        // DO NOT IMPLEMENT
   friend class MDNodeOperand;
   friend class LLVMContextImpl;
+  friend struct FoldingSetTrait<MDNode>;
+
+  /// NumOperands - If the MDNode is uniqued cache the hash to speed up lookup.
+  unsigned Hash;
 
   /// NumOperands - This many 'MDNodeOperand' items are co-allocated onto the
   /// end of this MDNode.

diff --git a/lib/VMCore/LLVMContextImpl.h b/lib/VMCore/LLVMContextImpl.h
index 1a4bf6d7b44b645ca22b8336855c64e6227234e3..2252028b156916f5456ce4f873cc166f73d37dc2 100644 (file)
--- a/lib/VMCore/LLVMContextImpl.h
+++ b/lib/VMCore/LLVMContextImpl.h
@@ -194,6 +194,26 @@ 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;
+
+    // If they match we have to compare the operands.
+    X.Profile(TempID);
+    return TempID == ID;
+  }
+  static unsigned ComputeHash(const MDNode &X, FoldingSetNodeID &) {
+    return X.Hash; // Return cached hash.
+  }
+};
+
 /// DebugRecVH - This is a CallbackVH used to keep the Scope -> index maps
 /// up to date as MDNodes mutate.  This class is implemented in DebugLoc.cpp.
 class DebugRecVH : public CallbackVH {

diff --git a/lib/VMCore/Metadata.cpp b/lib/VMCore/Metadata.cpp
index 55de0dc6515de9958cacd0ce2f74e4aac9fb0220..090b09a4ccd7bb6d874ae146c1a46d95e894d271 100644 (file)
--- a/lib/VMCore/Metadata.cpp
+++ b/lib/VMCore/Metadata.cpp
@@ -250,6 +250,9 @@ MDNode *MDNode::getMDNode(LLVMContext &Context, ArrayRef<Value*> Vals,
   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);
 
@@ -373,6 +376,8 @@ void MDNode::replaceOperand(MDNodeOperand *Op, Value *To) {
     return;
   }
 
+  // Cache the operand hash.
+  Hash = ID.ComputeHash();
   // InsertPoint will have been set by the FindNodeOrInsertPos call.
   pImpl->MDNodeSet.InsertNode(this, InsertPoint);