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

1 files changed, 5 insertions, 0 deletions

diff --git a/lib/VMCore/Metadata.cpp b/lib/VMCore/Metadata.cpp
index 55de0dc..090b09a 100644
--- 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);