From 8f3cfb4c657f0094e8bf1e67de4ee776d57a751e Mon Sep 17 00:00:00 2001
From: Ted Kremenek <kremenek@apple.com>
Date: Fri, 10 Jul 2009 00:33:43 +0000
Subject: [PATCH] ImmutableMap/ImmutableSet: Allow caching of ImutAVLTree
 digests while the tree is still mutable. My experiments show this reduces the
 amount of times we compute a full tree digest by over 50% on very small
 cases, and potentially much larger on others.

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

diff --git a/include/llvm/ADT/ImmutableSet.h b/include/llvm/ADT/ImmutableSet.h
index 38816c77867..ef048a94782 100644
--- a/include/llvm/ADT/ImmutableSet.h
+++ b/include/llvm/ADT/ImmutableSet.h
@@ -283,25 +283,25 @@ private:
   void setLeft(ImutAVLTree* NewLeft) {
     assert(isMutable() &&
            "Only a mutable tree can have its left subtree changed.");
-    assert(!hasCachedDigest() &&
-           "A mutable tree cannot have a cached digest.");
-
     Left = reinterpret_cast<uintptr_t>(NewLeft) | LeftFlags;
   }
 
   /// setRight - Changes the reference of the right subtree.  Used internally
   ///  by ImutAVLFactory.
   void setRight(ImutAVLTree* NewRight) {
-    assert (isMutable() &&
-            "Only a mutable tree can have its right subtree changed.");
+    assert(isMutable() &&
+           "Only a mutable tree can have its right subtree changed.");
 
     Right = NewRight;
+    // Set the NoCachedDigest flag.
+    Left = Left | NoCachedDigest;
+
   }
 
   /// setHeight - Changes the height of the tree.  Used internally by
   ///  ImutAVLFactory.
   void setHeight(unsigned h) {
-    assert (isMutable() && "Only a mutable tree can have its height changed.");
+    assert(isMutable() && "Only a mutable tree can have its height changed.");
     Height = h;
   }
 
@@ -330,12 +330,7 @@ private:
       return Digest;
 
     uint32_t X = ComputeDigest(getLeft(), getRight(), getValue());
-
-    if (!isMutable()) {
-      Digest = X;
-      MarkedCachedDigest();
-    }
-
+    Digest = X;
     return X;
   }
 };
@@ -412,7 +407,6 @@ private:
     return ( hl > hr ? hl : hr ) + 1;
   }
 
-
   static bool CompareTreeWithSection(TreeTy* T,
                                      typename TreeTy::iterator& TI,
                                      typename TreeTy::iterator& TE) {
@@ -454,7 +448,6 @@ private:
 
       // We found a collision.  Perform a comparison of Contents('T')
       // with Contents('L')+'V'+Contents('R').
-
       typename TreeTy::iterator TI = T->begin(), TE = T->end();
 
       // First compare Contents('L') with the (initial) contents of T.
@@ -471,17 +464,15 @@ private:
       if (!CompareTreeWithSection(R, TI, TE))
         continue;
 
-      if (TI != TE) // Contents('R') did not match suffix of 'T'.
-        continue;
+      if (TI != TE)
+        continue; // Contents('R') did not match suffix of 'T'.
 
       // Trees did match!  Return 'T'.
       return T;
     }
 
     // No tree with the contents: Contents('L')+'V'+Contents('R').
-    // Create it.
-
-    // Allocate the new tree node and insert it into the cache.
+    // Create it.  Allocate the new tree node and insert it into the cache.
     BumpPtrAllocator& A = getAllocator();
     TreeTy* T = (TreeTy*) A.Allocate<TreeTy>();
     new (T) TreeTy(L,R,V,IncrementHeight(L,R));
@@ -491,7 +482,6 @@ private:
     // Because our digest is associative and based on the contents of
     // the set, this should hopefully not cause any strange bugs.
     // 'T' is inserted by 'MarkImmutable'.
-
     return T;
   }
 
@@ -504,7 +494,8 @@ private:
       OldTree->setHeight(IncrementHeight(L,R));
       return OldTree;
     }
-    else return CreateNode(L, Value(OldTree), R);
+    else
+      return CreateNode(L, Value(OldTree), R);
   }
 
   /// Balance - Used by Add_internal and Remove_internal to
-- 
2.34.1