From 8b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550 Mon Sep 17 00:00:00 2001 From: Ted Kremenek Date: Thu, 3 Sep 2009 22:07:30 +0000 Subject: [PATCH] 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 --- include/llvm/ADT/ImmutableMap.h | 7 +- include/llvm/ADT/ImmutableSet.h | 116 ++++++++++++++++---------------- 2 files changed, 61 insertions(+), 62 deletions(-) diff --git a/include/llvm/ADT/ImmutableMap.h b/include/llvm/ADT/ImmutableMap.h index 52708bc8a10..96bf0122539 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(K,D))); + TreeTy *T = F.Add(Old.Root, std::make_pair(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: diff --git a/include/llvm/ADT/ImmutableSet.h b/include/llvm/ADT/ImmutableSet.h index 70fc1a69145..5aa1943de13 100644 --- a/include/llvm/ADT/ImmutableSet.h +++ b/include/llvm/ADT/ImmutableSet.h @@ -431,58 +431,10 @@ private: // returned to the caller. //===--------------------------------------------------===// - TreeTy* CreateNode(TreeTy* L, value_type_ref V, TreeTy* R) { - // Search the FoldingSet bucket for a Tree with the same digest. - FoldingSetNodeID ID; - unsigned digest = TreeTy::ComputeDigest(L, R, V); - ID.AddInteger(digest); - unsigned hash = ID.ComputeHash(); - - typename CacheTy::bucket_iterator I = Cache.bucket_begin(hash); - typename CacheTy::bucket_iterator E = Cache.bucket_end(hash); - - for (; I != E; ++I) { - TreeTy* T = &*I; - - if (T->ComputeDigest() != digest) - continue; - - // 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. - if (!CompareTreeWithSection(L, TI, TE)) - continue; - - // Now compare the new data element. - if (TI == TE || !TI->ElementEqual(V)) - continue; - - ++TI; - - // Now compare the remainder of 'T' with 'R'. - if (!CompareTreeWithSection(R, TI, TE)) - 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. + TreeTy* CreateNode(TreeTy* L, value_type_ref V, TreeTy* R) { BumpPtrAllocator& A = getAllocator(); TreeTy* T = (TreeTy*) A.Allocate(); new (T) TreeTy(L,R,V,IncrementHeight(L,R)); - - // We do not insert 'T' into the FoldingSet here. This is because - // this tree is still mutable and things may get rebalanced. - // 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; } @@ -615,12 +567,56 @@ private: T->MarkImmutable(); MarkImmutable(Left(T)); MarkImmutable(Right(T)); + } + +public: + TreeTy *GetCanonicalTree(TreeTy *TNew) { + if (!TNew) + return NULL; + + // Search the FoldingSet bucket for a Tree with the same digest. + FoldingSetNodeID ID; + unsigned digest = TNew->ComputeDigest(); + ID.AddInteger(digest); + unsigned hash = ID.ComputeHash(); + + typename CacheTy::bucket_iterator I = Cache.bucket_begin(hash); + typename CacheTy::bucket_iterator E = Cache.bucket_end(hash); + + for (; I != E; ++I) { + TreeTy *T = &*I; + + if (T->ComputeDigest() != digest) + continue; + + // 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. + if (!CompareTreeWithSection(TNew->getLeft(), TI, TE)) + continue; + + // Now compare the new data element. + if (TI == TE || !TI->ElementEqual(TNew->getValue())) + continue; + + ++TI; + + // Now compare the remainder of 'T' with 'R'. + if (!CompareTreeWithSection(TNew->getRight(), TI, TE)) + continue; + + if (TI != TE) + continue; // Contents('R') did not match suffix of 'T'. + + // Trees did match! Return 'T'. + return T; + } - // Now that the node is immutable it can safely be inserted - // into the node cache. - llvm::FoldingSetNodeID ID; - ID.AddInteger(T->ComputeDigest()); - Cache.InsertNode(T, (void*) &*Cache.bucket_end(ID.ComputeHash())); + // 'TNew' is the only tree of its kind. Return it. + Cache.InsertNode(TNew, (void*) &*Cache.bucket_end(hash)); + return TNew; } }; @@ -940,8 +936,8 @@ public: typedef ImutAVLTree TreeTy; private: - TreeTy* Root; - + TreeTy *Root; + public: /// Constructs a set from a pointer to a tree root. In general one /// should use a Factory object to create sets instead of directly @@ -969,7 +965,7 @@ public: /// The memory allocated to represent the set is released when the /// factory object that created the set is destroyed. ImmutableSet Add(ImmutableSet Old, value_type_ref V) { - return ImmutableSet(F.Add(Old.Root,V)); + return ImmutableSet(F.GetCanonicalTree(F.Add(Old.Root,V))); } /// Remove - Creates a new immutable set that contains all of the values @@ -980,7 +976,7 @@ public: /// The memory allocated to represent the set is released when the /// factory object that created the set is destroyed. ImmutableSet Remove(ImmutableSet Old, value_type_ref V) { - return ImmutableSet(F.Remove(Old.Root,V)); + return ImmutableSet(F.GetCanonicalTree(F.Remove(Old.Root,V))); } BumpPtrAllocator& getAllocator() { return F.getAllocator(); } @@ -1005,7 +1001,9 @@ public: return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root; } - TreeTy* getRoot() const { return Root; } + TreeTy *getRoot() { + return Root; + } /// isEmpty - Return true if the set contains no elements. bool isEmpty() const { return !Root; } -- 2.34.1