Make ImmutableMap/ImmutableSet quicker by only canonicalizing the tree after an

Add or Remove operation complete, and not while building the intermediate tree.
This trades a little bit more memory usage for less accesses to the FoldingSet.  On a benchmark for the clang static analyzer, this shaves off another 13% of execution time when using field/array sensitivity.


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

1 files changed, 4 insertions, 3 deletions

diff --git a/include/llvm/ADT/ImmutableMap.h b/include/llvm/ADT/ImmutableMap.h
index 52708bc..96bf012 100644
--- a/include/llvm/ADT/ImmutableMap.h
+++ b/include/llvm/ADT/ImmutableMap.h
@@ -90,12 +90,13 @@ public:
     ImmutableMap GetEmptyMap() { return ImmutableMap(F.GetEmptyTree()); }
 
     ImmutableMap Add(ImmutableMap Old, key_type_ref K, data_type_ref D) {
-      return ImmutableMap(F.Add(Old.Root,
-                                std::make_pair<key_type,data_type>(K,D)));
+      TreeTy *T = F.Add(Old.Root, std::make_pair<key_type,data_type>(K,D));
+      return ImmutableMap(F.GetCanonicalTree(T));
     }
 
     ImmutableMap Remove(ImmutableMap Old, key_type_ref K) {
-      return ImmutableMap(F.Remove(Old.Root,K));
+      TreeTy *T = F.Remove(Old.Root,K);
+      return ImmutableMap(F.GetCanonicalTree(T));
     }
 
   private: