From 6518f5fcbfc24e53ae453da0b080adf5448327be Mon Sep 17 00:00:00 2001
From: Ted Kremenek <kremenek@apple.com>
Date: Mon, 21 Jan 2008 22:33:30 +0000
Subject: [PATCH] Replaced (FoldingSet) profiling of ImutAVLTree with a hashing
 based scheme. The problem was that we previously hashed based on the pointers
 of the left and right children, but this is bogus: we can easily have
 different trees that represent the same set. Now we use a hashing based
 scheme that compares the *contents* of the trees, but not without having to
 do a full scan of a tree. The only caveat is that with hashing is that we may
 have collisions, which result in two different trees being falsely labeled as
 equivalent. If this becomes a problem, we can add extra data to the profile
 to hopefully resolve most collisions.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@46224 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/llvm/ADT/ImmutableSet.h | 29 +++++++++++++++++++++++------
 1 file changed, 23 insertions(+), 6 deletions(-)

diff --git a/include/llvm/ADT/ImmutableSet.h b/include/llvm/ADT/ImmutableSet.h
index e77deeb51eb..5118b0d3369 100644
--- a/include/llvm/ADT/ImmutableSet.h
+++ b/include/llvm/ADT/ImmutableSet.h
@@ -198,6 +198,7 @@ private:
   ImutAVLTree*     Right;
   unsigned         Height;
   value_type       Value;
+  unsigned         Hash;
   
   //===----------------------------------------------------===//  
   // Profiling or FoldingSet.
@@ -205,22 +206,38 @@ private:
 
 private:
 
+  static inline
+  unsigned ComputeHash(ImutAVLTree* L, ImutAVLTree* R, value_type_ref V) {
+    FoldingSetNodeID ID;
+    
+    ID.AddInteger(L ? L->ComputeHash() : 0);
+    ImutInfo::Profile(ID,V);
+    ID.AddInteger(R ? R->ComputeHash() : 0);
+    
+    return ID.ComputeHash();    
+  }
+  
+  inline unsigned ComputeHash() {
+    if (!isMutable() && Hash) return Hash;
+    Hash = ComputeHash(getSafeLeft(), getRight(), getValue());
+    return Hash;
+  }    
+  
   /// Profile - Generates a FoldingSet profile for a tree node before it is
   ///   created.  This is used by the ImutAVLFactory when creating
   ///   trees.
   static inline
   void Profile(FoldingSetNodeID& ID, ImutAVLTree* L, ImutAVLTree* R,
-               value_type_ref V) {    
-    ID.AddPointer(L);
-    ID.AddPointer(R);
-    ImutInfo::Profile(ID,V);
+               value_type_ref V) {
+    
+    ID.AddInteger(ComputeHash(L, R, V));
   }
   
 public:
 
   /// Profile - Generates a FoldingSet profile for an existing tree node.
   void Profile(FoldingSetNodeID& ID) {
-    Profile(ID,getSafeLeft(),getRight(),getValue());    
+    ID.AddInteger(ComputeHash());
   }
   
   //===----------------------------------------------------===//    
@@ -235,7 +252,7 @@ private:
   ///   ImutAVLFactory.
   ImutAVLTree(ImutAVLTree* l, ImutAVLTree* r, value_type_ref v, unsigned height)
   : Left(reinterpret_cast<uintptr_t>(l) | Mutable),
-  Right(r), Height(height), Value(v) {}
+    Right(r), Height(height), Value(v), Hash(0) {}
   
   
   /// isMutable - Returns true if the left and right subtree references
-- 
2.34.1