https://github.com/Xazax-hun updated https://github.com/llvm/llvm-project/pull/209300
From 3345c5cb50484328df66741144296d0da6ecbfae Mon Sep 17 00:00:00 2001 From: Gabor Horvath <[email protected]> Date: Mon, 13 Jul 2026 21:45:40 +0100 Subject: [PATCH] [ADT] Make canonicalization a compile-time parameter of ImmutableSet/Map ImmutableSet and ImmutableMap always carried the machinery needed for tree canonicalization -- a per-node `prev`/`next` cache chain and cached `digest`, plus the factory-side cache and a runtime `canonicalize` flag -- even for the many clients that disable it (the Clang dataflow analyses, e.g. lifetime safety and LiveVariables, for which canonicalization is a large performance loss). Those clients paid for state and code paths they never used. Add a `bool Canonicalize` template parameter (defaulting to true, so existing users are unaffected) that moves the decision to compile time: * When disabled, the `prev`/`next` links (empty base) and `digest` (LLVM_NO_UNIQUE_ADDRESS member) vanish, shrinking a set node from 56 to 40 bytes and a map node from 64 to 40 on 64-bit; `getCanonicalTree`, the factory cache, and the `destroy()` unlink branch are `if constexpr`-ed away. Node fields are ordered so the traversal-hot members come first. * When enabled, the node layout is unchanged, and `operator==`/`!=` become O(1) pointer comparisons (equal canonical trees share a root, as with ImmutableList) instead of a structural walk. The runtime `canonicalize` factory argument is now redundant and removed; the in-tree non-canonicalizing users are switched to the template argument. Node microbenchmark (ImmutableSetBuildBM, non-canonicalizing, -O2): | Benchmark | Before | After | Speedup | |--------------------|---------:|---------:|:-------:| | Build/256 | 20.3 us | 18.3 us | 1.11x | | Build/4096 | 790 us | 731 us | 1.08x | | Build/65536 | 18.8 ms | 18.4 ms | 1.02x | | BuildRemove/256 | 40.7 us | 35.0 us | 1.16x | | BuildRemove/4096 | 1.46 ms | 1.39 ms | 1.05x | | BuildRemove/65536 | 34.6 ms | 33.8 ms | 1.02x | End to end, the smaller node cuts the lifetime-safety analysis peak RSS by up to ~23% on allocation-dense inputs with neutral-to-positive run time, and the O(1) equality speeds up a Clang static analyzer run on llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp by ~1.3% (95.1s -> 93.9s). Assisted by: Claude Opus 4.8 --- .../Analyses/LifetimeSafety/LifetimeSafety.h | 8 +- .../Analyses/LifetimeSafety/LiveOrigins.h | 4 +- .../Analyses/LifetimeSafety/LoanPropagation.h | 7 +- .../Analyses/LifetimeSafety/MovedLoans.h | 3 +- .../Analysis/Analyses/LifetimeSafety/Utils.h | 37 ++-- .../clang/Analysis/Analyses/LiveVariables.h | 18 +- clang/lib/Analysis/LiveVariables.cpp | 34 ++-- llvm/benchmarks/ImmutableSetBuildBM.cpp | 12 +- llvm/benchmarks/ImmutableSetIteratorBM.cpp | 14 +- llvm/include/llvm/ADT/ImmutableMap.h | 38 ++-- llvm/include/llvm/ADT/ImmutableSet.h | 181 ++++++++++++------ llvm/unittests/ADT/ImmutableSetTest.cpp | 63 +++--- 12 files changed, 261 insertions(+), 158 deletions(-) diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety/LifetimeSafety.h b/clang/include/clang/Analysis/Analyses/LifetimeSafety/LifetimeSafety.h index 80a23f18baebd..d2827dbca3111 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/LifetimeSafety.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/LifetimeSafety.h @@ -171,10 +171,10 @@ void collectLifetimeStats(AnalysisDeclContext &AC, OriginManager &OM, /// An object to hold the factories for immutable collections, ensuring /// that all created states share the same underlying memory management. struct LifetimeFactory { - OriginLoanMap::Factory OriginMapFactory{/*canonicalize=*/false}; - LoanSet::Factory LoanSetFactory{/*canonicalize=*/false}; - MovedLoansMap::Factory MovedLoansMapFactory{/*canonicalize=*/false}; - LivenessMap::Factory LivenessMapFactory{/*canonicalize=*/false}; + OriginLoanMap::Factory OriginMapFactory; + LoanSet::Factory LoanSetFactory; + MovedLoansMap::Factory MovedLoansMapFactory; + LivenessMap::Factory LivenessMapFactory; }; /// Running the lifetime safety analysis and querying its results. It diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety/LiveOrigins.h b/clang/include/clang/Analysis/Analyses/LifetimeSafety/LiveOrigins.h index 35b4224883cce..8f998fa83fbf5 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/LiveOrigins.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/LiveOrigins.h @@ -23,10 +23,10 @@ #include "clang/Analysis/Analyses/LifetimeSafety/Facts.h" #include "clang/Analysis/Analyses/LifetimeSafety/Origins.h" +#include "clang/Analysis/Analyses/LifetimeSafety/Utils.h" #include "clang/Analysis/AnalysisDeclContext.h" #include "clang/Analysis/CFG.h" #include "llvm/ADT/FoldingSet.h" -#include "llvm/ADT/ImmutableMap.h" #include "llvm/Support/Debug.h" namespace clang::lifetimes::internal { @@ -73,7 +73,7 @@ struct LivenessInfo { } }; -using LivenessMap = llvm::ImmutableMap<OriginID, LivenessInfo>; +using LivenessMap = utils::MapTy<OriginID, LivenessInfo>; class LiveOriginsAnalysis { public: diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety/LoanPropagation.h b/clang/include/clang/Analysis/Analyses/LifetimeSafety/LoanPropagation.h index 838daa024c953..e13442facd82d 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/LoanPropagation.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/LoanPropagation.h @@ -16,18 +16,17 @@ #define LLVM_CLANG_ANALYSIS_ANALYSES_LIFETIMESAFETY_LOAN_PROPAGATION_H #include "clang/Analysis/Analyses/LifetimeSafety/Facts.h" +#include "clang/Analysis/Analyses/LifetimeSafety/Utils.h" #include "clang/Analysis/AnalysisDeclContext.h" #include "clang/Analysis/CFG.h" -#include "llvm/ADT/ImmutableMap.h" -#include "llvm/ADT/ImmutableSet.h" namespace clang::lifetimes::internal { // Using LLVM's immutable collections is efficient for dataflow analysis // as it avoids deep copies during state transitions. // TODO(opt): Consider using a bitset to represent the set of loans. -using LoanSet = llvm::ImmutableSet<LoanID>; -using OriginLoanMap = llvm::ImmutableMap<OriginID, LoanSet>; +using LoanSet = utils::SetTy<LoanID>; +using OriginLoanMap = utils::MapTy<OriginID, LoanSet>; class LoanPropagationAnalysis { public: diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety/MovedLoans.h b/clang/include/clang/Analysis/Analyses/LifetimeSafety/MovedLoans.h index a83f40c8855b6..133aa02fa9a45 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/MovedLoans.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/MovedLoans.h @@ -17,13 +17,14 @@ #include "clang/Analysis/Analyses/LifetimeSafety/Facts.h" #include "clang/Analysis/Analyses/LifetimeSafety/LiveOrigins.h" #include "clang/Analysis/Analyses/LifetimeSafety/LoanPropagation.h" +#include "clang/Analysis/Analyses/LifetimeSafety/Utils.h" #include "clang/Analysis/AnalysisDeclContext.h" #include "clang/Analysis/CFG.h" namespace clang::lifetimes::internal { // Map from a loan to an expression responsible for moving the borrowed storage. -using MovedLoansMap = llvm::ImmutableMap<LoanID, const Expr *>; +using MovedLoansMap = utils::MapTy<LoanID, const Expr *>; class MovedLoansAnalysis { public: diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety/Utils.h b/clang/include/clang/Analysis/Analyses/LifetimeSafety/Utils.h index 543bbd045593c..76feec9e62c5a 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/Utils.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/Utils.h @@ -34,15 +34,24 @@ template <typename Tag> struct ID { } }; -/// Computes the union of two ImmutableSets. +/// The lifetime analyses do not benefit from canonicalizing their immutable +/// collections, so they opt out of it via these aliases. template <typename T> -llvm::ImmutableSet<T> join(llvm::ImmutableSet<T> A, llvm::ImmutableSet<T> B, - typename llvm::ImmutableSet<T>::Factory &F) { +using SetTy = + llvm::ImmutableSet<T, llvm::ImutContainerInfo<T>, /*Canonicalize=*/false>; + +template <typename KeyT, typename ValT> +using MapTy = llvm::ImmutableMap<KeyT, ValT, llvm::ImutKeyValueInfo<KeyT, ValT>, + /*Canonicalize=*/false>; + +/// Computes the union of two ImmutableSets. +template <typename SetT> +SetT join(SetT A, SetT B, typename SetT::Factory &F) { if (A.getRootWithoutRetain() == B.getRootWithoutRetain()) return A; if (A.getHeight() < B.getHeight()) std::swap(A, B); - for (const T &E : B) + for (const auto &E : B) A = F.add(A, E); return A; } @@ -67,11 +76,9 @@ enum class JoinKind { // TODO(opt): This key-wise join is a performance bottleneck. A more // efficient merge could be implemented using a Patricia Trie or HAMT // instead of the current AVL-tree-based ImmutableMap. -template <typename K, typename V, typename Joiner> -llvm::ImmutableMap<K, V> join(const llvm::ImmutableMap<K, V> &A, - const llvm::ImmutableMap<K, V> &B, - typename llvm::ImmutableMap<K, V>::Factory &F, - Joiner JoinValues, JoinKind Kind) { +template <typename MapT, typename Joiner> +MapT join(const MapT &A, const MapT &B, typename MapT::Factory &F, + Joiner JoinValues, JoinKind Kind) { if (A.getRootWithoutRetain() == B.getRootWithoutRetain()) return A; if (A.getHeight() < B.getHeight()) @@ -79,19 +86,13 @@ llvm::ImmutableMap<K, V> join(const llvm::ImmutableMap<K, V> &A, // For each element in B, join it with the corresponding element in A // (or with an empty value if it doesn't exist in A). - llvm::ImmutableMap<K, V> Res = A; - for (const auto &Entry : B) { - const K &Key = Entry.first; - const V &ValB = Entry.second; + MapT Res = A; + for (const auto &[Key, ValB] : B) Res = F.add(Res, Key, JoinValues(A.lookup(Key), &ValB)); - } if (Kind == JoinKind::Symmetric) { - for (const auto &Entry : A) { - const K &Key = Entry.first; - const V &ValA = Entry.second; + for (const auto &[Key, ValA] : A) if (!B.contains(Key)) Res = F.add(Res, Key, JoinValues(&ValA, nullptr)); - } } return Res; } diff --git a/clang/include/clang/Analysis/Analyses/LiveVariables.h b/clang/include/clang/Analysis/Analyses/LiveVariables.h index 90a0f0f7dc86d..ff3fbb4b43ef7 100644 --- a/clang/include/clang/Analysis/Analyses/LiveVariables.h +++ b/clang/include/clang/Analysis/Analyses/LiveVariables.h @@ -27,21 +27,27 @@ class SourceManager; class LiveVariables : public ManagedAnalysis { public: + // Canonicalization of these sets is a major performance loss here, so the + // non-canonicalizing form is selected at compile time. + template <typename T> + using SetTy = + llvm::ImmutableSet<T, llvm::ImutContainerInfo<T>, /*Canonicalize=*/false>; + class LivenessValues { public: - llvm::ImmutableSet<const Expr *> liveExprs; - llvm::ImmutableSet<const VarDecl *> liveDecls; - llvm::ImmutableSet<const BindingDecl *> liveBindings; + SetTy<const Expr *> liveExprs; + SetTy<const VarDecl *> liveDecls; + SetTy<const BindingDecl *> liveBindings; bool operator==(const LivenessValues &V) const; LivenessValues() : liveExprs(nullptr), liveDecls(nullptr), liveBindings(nullptr) {} - LivenessValues(llvm::ImmutableSet<const Expr *> liveExprs, - llvm::ImmutableSet<const VarDecl *> LiveDecls, - llvm::ImmutableSet<const BindingDecl *> LiveBindings) + LivenessValues(SetTy<const Expr *> liveExprs, + SetTy<const VarDecl *> LiveDecls, + SetTy<const BindingDecl *> LiveBindings) : liveExprs(liveExprs), liveDecls(LiveDecls), liveBindings(LiveBindings) {} diff --git a/clang/lib/Analysis/LiveVariables.cpp b/clang/lib/Analysis/LiveVariables.cpp index af3055c3d5f8d..04d78d9ef8924 100644 --- a/clang/lib/Analysis/LiveVariables.cpp +++ b/clang/lib/Analysis/LiveVariables.cpp @@ -29,10 +29,15 @@ using namespace clang; namespace { class LiveVariablesImpl { public: + template <typename T> using SetTy = LiveVariables::SetTy<T>; + template <typename T> + using SetRefTy = llvm::ImmutableSetRef<T, llvm::ImutContainerInfo<T>, + /*Canonicalize=*/false>; + AnalysisDeclContext &analysisContext; - llvm::ImmutableSet<const Expr *>::Factory ESetFact; - llvm::ImmutableSet<const VarDecl *>::Factory DSetFact; - llvm::ImmutableSet<const BindingDecl *>::Factory BSetFact; + SetTy<const Expr *>::Factory ESetFact; + SetTy<const VarDecl *>::Factory DSetFact; + SetTy<const BindingDecl *>::Factory BSetFact; llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksEndToLiveness; llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksBeginToLiveness; llvm::DenseMap<const Stmt *, LiveVariables::LivenessValues> stmtsToLiveness; @@ -51,10 +56,7 @@ class LiveVariablesImpl { void dumpExprLiveness(const SourceManager& M); LiveVariablesImpl(AnalysisDeclContext &ac, bool KillAtAssign) - : analysisContext(ac), - ESetFact(false), // Do not canonicalize ImmutableSets by default. - DSetFact(false), // This is a *major* performance win. - BSetFact(false), killAtAssign(KillAtAssign) {} + : analysisContext(ac), killAtAssign(KillAtAssign) {} }; } // namespace @@ -106,16 +108,16 @@ LiveVariables::LivenessValues LiveVariablesImpl::merge(LiveVariables::LivenessValues valsA, LiveVariables::LivenessValues valsB) { - llvm::ImmutableSetRef<const Expr *> SSetRefA( + SetRefTy<const Expr *> SSetRefA( valsA.liveExprs.getRootWithoutRetain(), ESetFact.getTreeFactory()), SSetRefB(valsB.liveExprs.getRootWithoutRetain(), ESetFact.getTreeFactory()); - llvm::ImmutableSetRef<const VarDecl *> + SetRefTy<const VarDecl *> DSetRefA(valsA.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()), DSetRefB(valsB.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()); - llvm::ImmutableSetRef<const BindingDecl *> + SetRefTy<const BindingDecl *> BSetRefA(valsA.liveBindings.getRootWithoutRetain(), BSetFact.getTreeFactory()), BSetRefB(valsB.liveBindings.getRootWithoutRetain(), BSetFact.getTreeFactory()); @@ -123,8 +125,8 @@ LiveVariablesImpl::merge(LiveVariables::LivenessValues valsA, DSetRefA = mergeSets(DSetRefA, DSetRefB); BSetRefA = mergeSets(BSetRefA, BSetRefB); - // asImmutableSet() canonicalizes the tree, allowing us to do an easy - // comparison afterwards. + // Finalize the merged builder refs into immutable sets. These are not + // canonicalized; LivenessValues::operator== compares them structurally. return LiveVariables::LivenessValues(SSetRefA.asImmutableSet(), DSetRefA.asImmutableSet(), BSetRefA.asImmutableSet()); @@ -211,8 +213,8 @@ static const Expr *LookThroughExpr(const Expr *E) { return E; } -static void AddLiveExpr(llvm::ImmutableSet<const Expr *> &Set, - llvm::ImmutableSet<const Expr *>::Factory &F, +static void AddLiveExpr(LiveVariables::SetTy<const Expr *> &Set, + LiveVariables::SetTy<const Expr *>::Factory &F, const Expr *E) { Set = F.add(Set, LookThroughExpr(E)); } @@ -222,8 +224,8 @@ static void AddLiveExpr(llvm::ImmutableSet<const Expr *> &Set, /// "(a < b) || (c && d && ((e || f) != (g && h)))" /// the following expressions will be added as live: /// "a < b", "c", "d", "((e || f) != (g && h))" -static void AddAllConditionalTerms(llvm::ImmutableSet<const Expr *> &Set, - llvm::ImmutableSet<const Expr *>::Factory &F, +static void AddAllConditionalTerms(LiveVariables::SetTy<const Expr *> &Set, + LiveVariables::SetTy<const Expr *>::Factory &F, const Expr *Cond) { AddLiveExpr(Set, F, Cond); if (auto const *BO = dyn_cast<BinaryOperator>(Cond->IgnoreParens()); diff --git a/llvm/benchmarks/ImmutableSetBuildBM.cpp b/llvm/benchmarks/ImmutableSetBuildBM.cpp index 8e88f31a9a4af..9ffe6750c9693 100644 --- a/llvm/benchmarks/ImmutableSetBuildBM.cpp +++ b/llvm/benchmarks/ImmutableSetBuildBM.cpp @@ -28,6 +28,10 @@ using namespace llvm; namespace { +// Non-canonicalizing set (matches the dataflow analyses' usage). +using IntSet = + ImmutableSet<int, ImutContainerInfo<int>, /*Canonicalize=*/false>; + // A shuffled [0, N) key sequence, so the tree is built in random order. static std::vector<int> shuffledKeys(size_t N) { std::vector<int> Vals(N); @@ -41,8 +45,8 @@ static void BM_Build(benchmark::State &State) { const size_t N = State.range(0); std::vector<int> Vals = shuffledKeys(N); for (auto _ : State) { - ImmutableSet<int>::Factory F(/*canonicalize=*/false); - ImmutableSet<int> S = F.getEmptySet(); + IntSet::Factory F; + IntSet S = F.getEmptySet(); for (int V : Vals) S = F.add(S, V); benchmark::DoNotOptimize(S.getRootWithoutRetain()); @@ -54,8 +58,8 @@ static void BM_BuildRemove(benchmark::State &State) { const size_t N = State.range(0); std::vector<int> Vals = shuffledKeys(N); for (auto _ : State) { - ImmutableSet<int>::Factory F(/*canonicalize=*/false); - ImmutableSet<int> S = F.getEmptySet(); + IntSet::Factory F; + IntSet S = F.getEmptySet(); for (int V : Vals) S = F.add(S, V); for (int V : Vals) diff --git a/llvm/benchmarks/ImmutableSetIteratorBM.cpp b/llvm/benchmarks/ImmutableSetIteratorBM.cpp index bb68e0154c6ea..44f574c907ff5 100644 --- a/llvm/benchmarks/ImmutableSetIteratorBM.cpp +++ b/llvm/benchmarks/ImmutableSetIteratorBM.cpp @@ -41,13 +41,16 @@ using namespace llvm; namespace { -using Tree = ImmutableSet<int>::TreeTy; +// Non-canonicalizing set (matches the dataflow analyses' usage). +using IntSet = + ImmutableSet<int, ImutContainerInfo<int>, /*Canonicalize=*/false>; +using Tree = IntSet::TreeTy; // Holds a factory plus a built set so the (non-trivial) tree construction is // kept out of the timed region. The factory must outlive the tree. struct Fixture { - ImmutableSet<int>::Factory F{/*canonicalize=*/false}; - ImmutableSet<int> Set = F.getEmptySet(); + IntSet::Factory F; + IntSet Set = F.getEmptySet(); explicit Fixture(size_t N) { std::vector<int> Vals(N); @@ -63,7 +66,7 @@ struct Fixture { static void BM_Iterate(benchmark::State &State) { const size_t N = State.range(0); Fixture Fix(N); - const ImmutableSet<int> &S = Fix.Set; + const IntSet &S = Fix.Set; benchmark::DoNotOptimize(S.getRootWithoutRetain()); for (auto _ : State) { @@ -128,7 +131,8 @@ static void BM_CompareSamePosition(benchmark::State &State) { // matters. static void BM_CanonicalizeSharedEqual(benchmark::State &State) { const size_t N = State.range(0); - ImmutableSet<int>::Factory F(/*canonicalize=*/true); + // This case exercises canonicalization, so it uses a canonicalizing factory. + ImmutableSet<int>::Factory F; ImmutableSet<int> Base = F.getEmptySet(); std::vector<int> Vals(N); std::iota(Vals.begin(), Vals.end(), 0); diff --git a/llvm/include/llvm/ADT/ImmutableMap.h b/llvm/include/llvm/ADT/ImmutableMap.h index 04740bbdd954b..89ac42be2f0c2 100644 --- a/llvm/include/llvm/ADT/ImmutableMap.h +++ b/llvm/include/llvm/ADT/ImmutableMap.h @@ -59,7 +59,8 @@ struct ImutKeyValueInfo { }; template <typename KeyT, typename ValT, - typename ValInfo = ImutKeyValueInfo<KeyT,ValT>> + typename ValInfo = ImutKeyValueInfo<KeyT,ValT>, + bool Canonicalize = true> class ImmutableMap { public: using value_type = typename ValInfo::value_type; @@ -68,7 +69,7 @@ class ImmutableMap { using key_type_ref = typename ValInfo::key_type_ref; using data_type = typename ValInfo::data_type; using data_type_ref = typename ValInfo::data_type_ref; - using TreeTy = ImutAVLTree<ValInfo>; + using TreeTy = ImutAVLTree<ValInfo, Canonicalize>; protected: IntrusiveRefCntPtr<TreeTy> Root; @@ -82,13 +83,11 @@ class ImmutableMap { class Factory { typename TreeTy::Factory F; - const bool Canonicalize; public: - Factory(bool canonicalize = true) : Canonicalize(canonicalize) {} + Factory() = default; - Factory(BumpPtrAllocator &Alloc, bool canonicalize = true) - : F(Alloc), Canonicalize(canonicalize) {} + Factory(BumpPtrAllocator &Alloc) : F(Alloc) {} Factory(const Factory &) = delete; Factory &operator=(const Factory &) = delete; @@ -98,12 +97,18 @@ class ImmutableMap { [[nodiscard]] ImmutableMap add(ImmutableMap Old, key_type_ref K, data_type_ref D) { TreeTy *T = F.add(Old.Root.get(), std::pair<key_type, data_type>(K, D)); - return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T); + if constexpr (Canonicalize) + return ImmutableMap(F.getCanonicalTree(T)); + else + return ImmutableMap(T); } [[nodiscard]] ImmutableMap remove(ImmutableMap Old, key_type_ref K) { TreeTy *T = F.remove(Old.Root.get(), K); - return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T); + if constexpr (Canonicalize) + return ImmutableMap(F.getCanonicalTree(T)); + else + return ImmutableMap(T); } typename TreeTy::Factory *getTreeFactory() const { @@ -115,13 +120,24 @@ class ImmutableMap { return Root ? Root->contains(K) : false; } + /// Compares two maps for equality. For a canonicalizing factory, maps with + /// equal contents share the same tree, so this is an O(1) pointer comparison + /// (like ImmutableList); only maps created by the same factory may be + /// compared. Otherwise it is a structural comparison. [[nodiscard]] bool operator==(const ImmutableMap &RHS) const { - return Root && RHS.Root ? Root->isEqual(*RHS.Root.get()) : Root == RHS.Root; + if constexpr (Canonicalize) + return Root == RHS.Root; + else + return Root && RHS.Root ? Root->isEqual(*RHS.Root.get()) + : Root == RHS.Root; } [[nodiscard]] bool operator!=(const ImmutableMap &RHS) const { - return Root && RHS.Root ? Root->isNotEqual(*RHS.Root.get()) - : Root != RHS.Root; + if constexpr (Canonicalize) + return Root != RHS.Root; + else + return Root && RHS.Root ? Root->isNotEqual(*RHS.Root.get()) + : Root != RHS.Root; } [[nodiscard]] TreeTy *getRoot() const { diff --git a/llvm/include/llvm/ADT/ImmutableSet.h b/llvm/include/llvm/ADT/ImmutableSet.h index ae8b1103238aa..98aeb2147fb85 100644 --- a/llvm/include/llvm/ADT/ImmutableSet.h +++ b/llvm/include/llvm/ADT/ImmutableSet.h @@ -38,22 +38,57 @@ namespace llvm { // Immutable AVL-Tree Definition. //===----------------------------------------------------------------------===// -template <typename ImutInfo> class ImutAVLFactory; +template <typename ImutInfo, bool Canonicalize = true> class ImutAVLFactory; template <typename ImutInfo> class ImutIntervalAVLFactory; -template <typename ImutInfo> class ImutAVLTreeInOrderIterator; +template <typename ImutInfo, bool Canonicalize = true> +class ImutAVLTreeInOrderIterator; + +namespace ImutAVLDetail { +/// The intrusive doubly-linked chain of same-digest trees in the factory's +/// canonicalization cache. Held as an (empty) base so that, when canonicalization +/// is disabled, the empty base optimization removes it entirely. Kept separate +/// from the cached digest below so that the two pointers pack without the tail +/// padding that grouping a trailing 32-bit field with them would introduce. +template <typename Tree, bool Canonicalize> struct CanonicalLinks { + Tree *Prev = nullptr; + Tree *Next = nullptr; +}; +template <typename Tree> struct CanonicalLinks<Tree, false> {}; + +/// The cached structural digest, used only for canonicalization. Stored as an +/// LLVM_NO_UNIQUE_ADDRESS member so it occupies no space when disabled and packs +/// alongside the adjacent 32-bit fields when enabled. +template <bool Canonicalize> struct CanonicalDigest { + uint32_t Digest = 0; +}; +template <> struct CanonicalDigest<false> {}; -template <typename ImutInfo > -class ImutAVLTree { +/// The factory-side canonicalization cache: digest -> tree chain. +/// Empty when canonicalization is disabled. +template <typename Tree, bool Canonicalize> struct CanonicalCache { + DenseMap<unsigned, Tree *> Cache; +}; +template <typename Tree> struct CanonicalCache<Tree, false> {}; +} // namespace ImutAVLDetail + +template <typename ImutInfo, bool Canonicalize = true> +class ImutAVLTree + : private ImutAVLDetail::CanonicalLinks<ImutAVLTree<ImutInfo, Canonicalize>, + Canonicalize> { public: using key_type_ref = typename ImutInfo::key_type_ref; using value_type = typename ImutInfo::value_type; using value_type_ref = typename ImutInfo::value_type_ref; - using Factory = ImutAVLFactory<ImutInfo>; - using iterator = ImutAVLTreeInOrderIterator<ImutInfo>; + using Factory = ImutAVLFactory<ImutInfo, Canonicalize>; + using iterator = ImutAVLTreeInOrderIterator<ImutInfo, Canonicalize>; - friend class ImutAVLFactory<ImutInfo>; + friend class ImutAVLFactory<ImutInfo, Canonicalize>; friend class ImutIntervalAVLFactory<ImutInfo>; +private: + using CanonLinks = ImutAVLDetail::CanonicalLinks<ImutAVLTree, Canonicalize>; + +public: //===----------------------------------------------------===// // Public Interface. //===----------------------------------------------------===// @@ -205,11 +240,11 @@ class ImutAVLTree { //===----------------------------------------------------===// private: - Factory *factory; + // Field order places the traversal-hot fields (left, right, value) first so + // that in a node that straddles a cache line they land in the earlier line; + // the cold factory back-pointer (only touched on create/destroy) goes last. ImutAVLTree *left; ImutAVLTree *right; - ImutAVLTree *prev = nullptr; - ImutAVLTree *next = nullptr; unsigned height : 28; LLVM_PREFERRED_TYPE(bool) @@ -220,8 +255,9 @@ class ImutAVLTree { unsigned IsCanonicalized : 1; value_type value; - uint32_t digest = 0; uint32_t refCount = 0; + LLVM_NO_UNIQUE_ADDRESS ImutAVLDetail::CanonicalDigest<Canonicalize> digest; + Factory *factory; //===----------------------------------------------------===// // Internal methods (node manipulation; used by Factory). @@ -231,8 +267,8 @@ class ImutAVLTree { /// Internal constructor that is only called by ImutAVLFactory. ImutAVLTree(Factory *f, ImutAVLTree* l, ImutAVLTree* r, value_type_ref v, unsigned height) - : factory(f), left(l), right(r), height(height), IsMutable(true), - IsDigestCached(false), IsCanonicalized(false), value(v) + : left(l), right(r), height(height), IsMutable(true), + IsDigestCached(false), IsCanonicalized(false), value(v), factory(f) { if (left) left->retain(); if (right) right->retain(); @@ -302,10 +338,10 @@ class ImutAVLTree { // Check the lowest bit to determine if digest has actually been // pre-computed. if (hasCachedDigest()) - return digest; + return digest.Digest; uint32_t X = computeDigest(getLeft(), getRight(), getValue()); - digest = X; + digest.Digest = X; markedCachedDigest(); return X; } @@ -323,19 +359,21 @@ class ImutAVLTree { destroy(); } - void destroy() { + LLVM_ATTRIBUTE_NOINLINE void destroy() { if (left) left->release(); if (right) right->release(); - if (IsCanonicalized) { - if (next) - next->prev = prev; - - if (prev) - prev->next = next; - else - factory->Cache[factory->maskCacheIndex(computeDigest())] = next; + if constexpr (Canonicalize) { + if (IsCanonicalized) { + if (this->Next) + this->Next->Prev = this->Prev; + + if (this->Prev) + this->Prev->Next = this->Next; + else + factory->Cache[factory->maskCacheIndex(computeDigest())] = this->Next; + } } // We need to clear the mutability bit in case we are @@ -345,26 +383,30 @@ class ImutAVLTree { } }; -template <typename ImutInfo> -struct IntrusiveRefCntPtrInfo<ImutAVLTree<ImutInfo>> { - static void retain(ImutAVLTree<ImutInfo> *Tree) { Tree->retain(); } - static void release(ImutAVLTree<ImutInfo> *Tree) { Tree->release(); } +template <typename ImutInfo, bool Canonicalize> +struct IntrusiveRefCntPtrInfo<ImutAVLTree<ImutInfo, Canonicalize>> { + static void retain(ImutAVLTree<ImutInfo, Canonicalize> *Tree) { + Tree->retain(); + } + static void release(ImutAVLTree<ImutInfo, Canonicalize> *Tree) { + Tree->release(); + } }; //===----------------------------------------------------------------------===// // Immutable AVL-Tree Factory class. //===----------------------------------------------------------------------===// -template <typename ImutInfo > -class ImutAVLFactory { - friend class ImutAVLTree<ImutInfo>; +template <typename ImutInfo, bool Canonicalize> +class ImutAVLFactory + : private ImutAVLDetail::CanonicalCache< + ImutAVLTree<ImutInfo, Canonicalize>, Canonicalize> { + friend class ImutAVLTree<ImutInfo, Canonicalize>; - using TreeTy = ImutAVLTree<ImutInfo>; + using TreeTy = ImutAVLTree<ImutInfo, Canonicalize>; using value_type_ref = typename TreeTy::value_type_ref; using key_type_ref = typename TreeTy::key_type_ref; - using CacheTy = DenseMap<unsigned, TreeTy*>; - CacheTy Cache; uintptr_t Allocator; std::vector<TreeTy*> createdNodes; std::vector<TreeTy*> freeNodes; @@ -604,6 +646,8 @@ class ImutAVLFactory { public: TreeTy *getCanonicalTree(TreeTy *TNew) { + static_assert(Canonicalize, + "getCanonicalTree requires a canonicalizing factory"); if (!TNew) return nullptr; @@ -613,9 +657,9 @@ class ImutAVLFactory { // Search the hashtable for another tree with the same digest, and // if find a collision compare those trees by their contents. unsigned digest = TNew->computeDigest(); - TreeTy *&entry = Cache[maskCacheIndex(digest)]; + TreeTy *&entry = this->Cache[maskCacheIndex(digest)]; if (entry) { - for (TreeTy *T = entry ; T != nullptr; T = T->next) { + for (TreeTy *T = entry ; T != nullptr; T = T->Next) { // Compare the contents of 'T' with 'TNew'. isEqual skips subtrees that // are shared by pointer, so for structurally-shared persistent trees // (the common case, e.g. one derived from the other) this is linear in @@ -627,8 +671,8 @@ class ImutAVLFactory { TNew->destroy(); return T; } - entry->prev = TNew; - TNew->next = entry; + entry->Prev = TNew; + TNew->Next = entry; } entry = TNew; @@ -655,15 +699,16 @@ class ImutAVLFactory { /// persistent and structurally shared: a single node may appear as the child of /// different parents across different tree versions. The ancestor stack is /// therefore the per-traversal parent chain. -template <typename ImutInfo> class ImutAVLTreeInOrderIterator { +template <typename ImutInfo, bool Canonicalize> +class ImutAVLTreeInOrderIterator { public: using iterator_category = std::bidirectional_iterator_tag; - using value_type = ImutAVLTree<ImutInfo>; + using value_type = ImutAVLTree<ImutInfo, Canonicalize>; using difference_type = std::ptrdiff_t; using pointer = value_type *; using reference = value_type &; - using TreeTy = ImutAVLTree<ImutInfo>; + using TreeTy = ImutAVLTree<ImutInfo, Canonicalize>; private: // Path[0] is the root and Path.back() is the current node. An empty path is @@ -900,12 +945,13 @@ template <typename T> struct ImutContainerInfo<T *> : ImutProfileInfo<T *> { // Immutable Set //===----------------------------------------------------------------------===// -template <typename ValT, typename ValInfo = ImutContainerInfo<ValT>> +template <typename ValT, typename ValInfo = ImutContainerInfo<ValT>, + bool Canonicalize = true> class ImmutableSet { public: using value_type = typename ValInfo::value_type; using value_type_ref = typename ValInfo::value_type_ref; - using TreeTy = ImutAVLTree<ValInfo>; + using TreeTy = ImutAVLTree<ValInfo, Canonicalize>; private: IntrusiveRefCntPtr<TreeTy> Root; @@ -919,14 +965,12 @@ class ImmutableSet { class Factory { typename TreeTy::Factory F; - const bool Canonicalize; public: - Factory(bool canonicalize = true) - : Canonicalize(canonicalize) {} + Factory() = default; - Factory(BumpPtrAllocator& Alloc, bool canonicalize = true) - : F(Alloc), Canonicalize(canonicalize) {} + Factory(BumpPtrAllocator& Alloc) + : F(Alloc) {} Factory(const Factory& RHS) = delete; void operator=(const Factory& RHS) = delete; @@ -945,7 +989,10 @@ class ImmutableSet { /// factory object that created the set is destroyed. [[nodiscard]] ImmutableSet add(ImmutableSet Old, value_type_ref V) { TreeTy *NewT = F.add(Old.Root.get(), V); - return ImmutableSet(Canonicalize ? F.getCanonicalTree(NewT) : NewT); + if constexpr (Canonicalize) + return ImmutableSet(F.getCanonicalTree(NewT)); + else + return ImmutableSet(NewT); } /// Creates a new immutable set that contains all of the values @@ -957,7 +1004,10 @@ class ImmutableSet { /// factory object that created the set is destroyed. [[nodiscard]] ImmutableSet remove(ImmutableSet Old, value_type_ref V) { TreeTy *NewT = F.remove(Old.Root.get(), V); - return ImmutableSet(Canonicalize ? F.getCanonicalTree(NewT) : NewT); + if constexpr (Canonicalize) + return ImmutableSet(F.getCanonicalTree(NewT)); + else + return ImmutableSet(NewT); } BumpPtrAllocator& getAllocator() { return F.getAllocator(); } @@ -974,13 +1024,24 @@ class ImmutableSet { return Root ? Root->contains(V) : false; } + /// Compares two sets for equality. For a canonicalizing factory, sets with + /// equal contents share the same tree, so this is an O(1) pointer comparison + /// (like ImmutableList); only sets created by the same factory may be + /// compared. Otherwise it is a structural comparison. bool operator==(const ImmutableSet &RHS) const { - return Root && RHS.Root ? Root->isEqual(*RHS.Root.get()) : Root == RHS.Root; + if constexpr (Canonicalize) + return Root == RHS.Root; + else + return Root && RHS.Root ? Root->isEqual(*RHS.Root.get()) + : Root == RHS.Root; } bool operator!=(const ImmutableSet &RHS) const { - return Root && RHS.Root ? Root->isNotEqual(*RHS.Root.get()) - : Root != RHS.Root; + if constexpr (Canonicalize) + return Root != RHS.Root; + else + return Root && RHS.Root ? Root->isNotEqual(*RHS.Root.get()) + : Root != RHS.Root; } TreeTy *getRoot() { @@ -1026,12 +1087,13 @@ class ImmutableSet { }; // NOTE: This may some day replace the current ImmutableSet. -template <typename ValT, typename ValInfo = ImutContainerInfo<ValT>> +template <typename ValT, typename ValInfo = ImutContainerInfo<ValT>, + bool Canonicalize = true> class ImmutableSetRef { public: using value_type = typename ValInfo::value_type; using value_type_ref = typename ValInfo::value_type_ref; - using TreeTy = ImutAVLTree<ValInfo>; + using TreeTy = ImutAVLTree<ValInfo, Canonicalize>; using FactoryTy = typename TreeTy::Factory; private: @@ -1062,9 +1124,12 @@ class ImmutableSetRef { return Root ? Root->contains(V) : false; } - ImmutableSet<ValT> asImmutableSet(bool canonicalize = true) const { - return ImmutableSet<ValT>( - canonicalize ? Factory->getCanonicalTree(Root.get()) : Root.get()); + ImmutableSet<ValT, ValInfo, Canonicalize> asImmutableSet() const { + using SetTy = ImmutableSet<ValT, ValInfo, Canonicalize>; + if constexpr (Canonicalize) + return SetTy(Factory->getCanonicalTree(Root.get())); + else + return SetTy(Root.get()); } TreeTy *getRootWithoutRetain() const { return Root.get(); } diff --git a/llvm/unittests/ADT/ImmutableSetTest.cpp b/llvm/unittests/ADT/ImmutableSetTest.cpp index b3d7e03089675..abcbec7658e80 100644 --- a/llvm/unittests/ADT/ImmutableSetTest.cpp +++ b/llvm/unittests/ADT/ImmutableSetTest.cpp @@ -16,6 +16,11 @@ using namespace llvm; +// Non-canonicalizing set, used by tests that specifically exercise the +// structural (isEqual) / iterator paths on distinct, non-deduplicated trees. +template <typename T> +using NCSet = ImmutableSet<T, ImutContainerInfo<T>, /*Canonicalize=*/false>; + namespace { class ImmutableSetTest : public testing::Test { protected: @@ -170,34 +175,34 @@ TEST_F(ImmutableSetTest, IterLongSetTest) { } TEST_F(ImmutableSetTest, AddIfNotFoundTest) { - ImmutableSet<long>::Factory f(/*canonicalize=*/false); - ImmutableSet<long> S = f.getEmptySet(); + NCSet<long>::Factory f; + NCSet<long> S = f.getEmptySet(); S = f.add(S, 1); S = f.add(S, 2); S = f.add(S, 3); - ImmutableSet<long> T1 = f.add(S, 1); - ImmutableSet<long> T2 = f.add(S, 2); - ImmutableSet<long> T3 = f.add(S, 3); + NCSet<long> T1 = f.add(S, 1); + NCSet<long> T2 = f.add(S, 2); + NCSet<long> T3 = f.add(S, 3); EXPECT_EQ(S.getRoot(), T1.getRoot()); EXPECT_EQ(S.getRoot(), T2.getRoot()); EXPECT_EQ(S.getRoot(), T3.getRoot()); - ImmutableSet<long> U = f.add(S, 4); + NCSet<long> U = f.add(S, 4); EXPECT_NE(S.getRoot(), U.getRoot()); } TEST_F(ImmutableSetTest, RemoveIfNotFoundTest) { - ImmutableSet<long>::Factory f(/*canonicalize=*/false); - ImmutableSet<long> S = f.getEmptySet(); + NCSet<long>::Factory f; + NCSet<long> S = f.getEmptySet(); S = f.add(S, 1); S = f.add(S, 2); S = f.add(S, 3); - ImmutableSet<long> T = f.remove(S, 4); + NCSet<long> T = f.remove(S, 4); EXPECT_EQ(S.getRoot(), T.getRoot()); - ImmutableSet<long> U = f.remove(S, 3); + NCSet<long> U = f.remove(S, 3); EXPECT_NE(S.getRoot(), U.getRoot()); } @@ -212,14 +217,14 @@ TEST_F(ImmutableSetTest, RemoveIfNotFoundTest) { namespace { using Info = ImutContainerInfo<int>; -using Tree = ImutAVLTree<Info>; +using Tree = ImutAVLTree<Info, /*Canonicalize=*/false>; using TreeIter = Tree::iterator; // ImutAVLTreeInOrderIterator // Build an ImmutableSet from the given values (in the given insertion order), // optionally removing some afterwards, so trees of varied shape are produced. -ImmutableSet<int> buildSet(ImmutableSet<int>::Factory &F, ArrayRef<int> ToAdd, +NCSet<int> buildSet(NCSet<int>::Factory &F, ArrayRef<int> ToAdd, ArrayRef<int> ToRemove = {}) { - ImmutableSet<int> S = F.getEmptySet(); + NCSet<int> S = F.getEmptySet(); for (int V : ToAdd) S = F.add(S, V); for (int V : ToRemove) @@ -229,8 +234,8 @@ ImmutableSet<int> buildSet(ImmutableSet<int>::Factory &F, ArrayRef<int> ToAdd, // A representative collection of trees: degenerate, hand-picked small shapes, // a large balanced one, and many pseudo-random insert/remove mixes. -std::vector<ImmutableSet<int>> makeTestSets(ImmutableSet<int>::Factory &F) { - std::vector<ImmutableSet<int>> Sets; +std::vector<NCSet<int>> makeTestSets(NCSet<int>::Factory &F) { + std::vector<NCSet<int>> Sets; Sets.push_back(F.getEmptySet()); Sets.push_back(buildSet(F, {42})); Sets.push_back(buildSet(F, {1, 2, 3})); @@ -256,14 +261,14 @@ std::vector<ImmutableSet<int>> makeTestSets(ImmutableSet<int>::Factory &F) { // Forward iteration must visit keys in ascending order, exactly matching an // independent std::set holding the same elements. TEST_F(ImmutableSetTest, IteratorInOrderMatchesStdSet) { - ImmutableSet<int>::Factory F(/*canonicalize=*/false); - for (const ImmutableSet<int> &S : makeTestSets(F)) { + NCSet<int>::Factory F; + for (const NCSet<int> &S : makeTestSets(F)) { std::set<int> Oracle; - for (ImmutableSet<int>::iterator I = S.begin(), E = S.end(); I != E; ++I) + for (NCSet<int>::iterator I = S.begin(), E = S.end(); I != E; ++I) Oracle.insert(*I); std::vector<int> Forward; - for (ImmutableSet<int>::iterator I = S.begin(), E = S.end(); I != E; ++I) + for (NCSet<int>::iterator I = S.begin(), E = S.end(); I != E; ++I) Forward.push_back(*I); EXPECT_TRUE(std::is_sorted(Forward.begin(), Forward.end())); @@ -277,8 +282,8 @@ TEST_F(ImmutableSetTest, IteratorInOrderMatchesStdSet) { // Walking backwards with operator-- from the last element must reproduce the // reverse of the forward traversal. TEST_F(ImmutableSetTest, IteratorReverseMatchesForward) { - ImmutableSet<int>::Factory F(/*canonicalize=*/false); - for (const ImmutableSet<int> &S : makeTestSets(F)) { + NCSet<int>::Factory F; + for (const NCSet<int> &S : makeTestSets(F)) { const Tree *Root = S.getRootWithoutRetain(); std::vector<const Tree *> Forward; @@ -308,8 +313,8 @@ TEST_F(ImmutableSetTest, IteratorReverseMatchesForward) { // contiguous run, the destination index is computable independently from the // node's right-subtree size. TEST_F(ImmutableSetTest, IteratorSkipSubTree) { - ImmutableSet<int>::Factory F(/*canonicalize=*/false); - for (const ImmutableSet<int> &S : makeTestSets(F)) { + NCSet<int>::Factory F; + for (const NCSet<int> &S : makeTestSets(F)) { const Tree *Root = S.getRootWithoutRetain(); std::vector<const Tree *> Order; @@ -339,10 +344,10 @@ TEST_F(ImmutableSetTest, IteratorSkipSubTree) { // comparison of the in-order sequences. This exercises ++ and skipSubTree on // the shared-subtree fast path inside ImutAVLTree::isEqual. TEST_F(ImmutableSetTest, StructuralEqualityMatchesContents) { - ImmutableSet<int>::Factory F(/*canonicalize=*/false); - std::vector<ImmutableSet<int>> Sets = makeTestSets(F); - for (const ImmutableSet<int> &A : Sets) { - for (const ImmutableSet<int> &B : Sets) { + NCSet<int>::Factory F; + std::vector<NCSet<int>> Sets = makeTestSets(F); + for (const NCSet<int> &A : Sets) { + for (const NCSet<int> &B : Sets) { std::vector<int> VA(A.begin(), A.end()); std::vector<int> VB(B.begin(), B.end()); EXPECT_EQ(VA == VB, A == B); @@ -353,8 +358,8 @@ TEST_F(ImmutableSetTest, StructuralEqualityMatchesContents) { // Two independent iterators compare equal iff they sit on the same node, and // equal-to-end iff both are at end. Exercises the node-identity operator==. TEST_F(ImmutableSetTest, IteratorEquality) { - ImmutableSet<int>::Factory F(/*canonicalize=*/false); - for (const ImmutableSet<int> &S : makeTestSets(F)) { + NCSet<int>::Factory F; + for (const NCSet<int> &S : makeTestSets(F)) { const Tree *Root = S.getRootWithoutRetain(); size_t N = std::distance(TreeIter(Root), TreeIter()); _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
