llvmorg-github-actions[bot] wrote:
<!--LLVM PR SUMMARY COMMENT--> @llvm/pr-subscribers-clang-analysis Author: Gábor Horváth (Xazax-hun) <details> <summary>Changes</summary> 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 --- Patch is 37.82 KiB, truncated to 20.00 KiB below, full version: https://github.com/llvm/llvm-project/pull/209300.diff 12 Files Affected: - (modified) clang/include/clang/Analysis/Analyses/LifetimeSafety/LifetimeSafety.h (+4-4) - (modified) clang/include/clang/Analysis/Analyses/LifetimeSafety/LiveOrigins.h (+3-1) - (modified) clang/include/clang/Analysis/Analyses/LifetimeSafety/LoanPropagation.h (+5-2) - (modified) clang/include/clang/Analysis/Analyses/LifetimeSafety/MovedLoans.h (+3-1) - (modified) clang/include/clang/Analysis/Analyses/LifetimeSafety/Utils.h (+16-16) - (modified) clang/include/clang/Analysis/Analyses/LiveVariables.h (+11-6) - (modified) clang/lib/Analysis/LiveVariables.cpp (+15-14) - (modified) llvm/benchmarks/ImmutableSetBuildBM.cpp (+7-4) - (modified) llvm/benchmarks/ImmutableSetIteratorBM.cpp (+8-5) - (modified) llvm/include/llvm/ADT/ImmutableMap.h (+27-11) - (modified) llvm/include/llvm/ADT/ImmutableSet.h (+125-58) - (modified) llvm/unittests/ADT/ImmutableSetTest.cpp (+34-29) ``````````diff 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..0fcac8bd57b35 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/LiveOrigins.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/LiveOrigins.h @@ -73,7 +73,9 @@ struct LivenessInfo { } }; -using LivenessMap = llvm::ImmutableMap<OriginID, LivenessInfo>; +using LivenessMap = + llvm::ImmutableMap<OriginID, LivenessInfo, + llvm::ImutKeyValueInfo<OriginID, LivenessInfo>, false>; 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..d488c8fadedcb 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/LoanPropagation.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/LoanPropagation.h @@ -26,8 +26,11 @@ 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 = + llvm::ImmutableSet<LoanID, llvm::ImutContainerInfo<LoanID>, false>; +using OriginLoanMap = + llvm::ImmutableMap<OriginID, LoanSet, + llvm::ImutKeyValueInfo<OriginID, LoanSet>, false>; 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..df918d409fe10 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/MovedLoans.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/MovedLoans.h @@ -23,7 +23,9 @@ 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 = + llvm::ImmutableMap<LoanID, const Expr *, + llvm::ImutKeyValueInfo<LoanID, const Expr *>, false>; 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..4cb79a32055d4 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/Utils.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/Utils.h @@ -34,15 +34,15 @@ template <typename Tag> struct ID { } }; -/// Computes the union of two ImmutableSets. -template <typename T> -llvm::ImmutableSet<T> join(llvm::ImmutableSet<T> A, llvm::ImmutableSet<T> B, - typename llvm::ImmutableSet<T>::Factory &F) { +/// Computes the union of two ImmutableSets. Templated on the set type so the +/// element, value-info and canonicalization parameters need not be spelled out. +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; } @@ -63,15 +63,15 @@ enum class JoinKind { Asymmetric, }; -/// Computes the key-wise union of two ImmutableMaps. +/// Computes the key-wise union of two ImmutableMaps. Templated on the map type +/// so the key, value, value-info and canonicalization parameters need not be +/// spelled out. // 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,16 +79,16 @@ 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; + MapT Res = A; for (const auto &Entry : B) { - const K &Key = Entry.first; - const V &ValB = Entry.second; + const auto &Key = Entry.first; + const auto &ValB = Entry.second; 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; + const auto &Key = Entry.first; + const auto &ValA = Entry.second; if (!B.contains(Key)) Res = F.add(Res, Key, JoinValues(&ValA, nullptr)); } diff --git a/clang/include/clang/Analysis/Analyses/LiveVariables.h b/clang/include/clang/Analysis/Analyses/LiveVariables.h index 90a0f0f7dc86d..d62dc8c73dea0 100644 --- a/clang/include/clang/Analysis/Analyses/LiveVariables.h +++ b/clang/include/clang/Analysis/Analyses/LiveVariables.h @@ -27,21 +27,26 @@ 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>, 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..6ffd99d68d14b 100644 --- a/clang/lib/Analysis/LiveVariables.cpp +++ b/clang/lib/Analysis/LiveVariables.cpp @@ -29,10 +29,14 @@ 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>, 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 +55,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 +107,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()); @@ -211,8 +212,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 +223,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..a68478313b885 100644 --- a/llvm/benchmarks/ImmutableSetBuildBM.cpp +++ b/llvm/benchmarks/ImmutableSetBuildBM.cpp @@ -28,6 +28,9 @@ using namespace llvm; namespace { +// Non-canonicalizing set (matches the dataflow analyses' usage). +using IntSet = ImmutableSet<int, ImutContainerInfo<int>, 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 +44,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 +57,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..43d26966b61c9 100644 --- a/llvm/benchmarks/ImmutableSetIteratorBM.cpp +++ b/llvm/benchmarks/ImmutableSetIteratorBM.cpp @@ -41,13 +41,15 @@ using namespace llvm; namespace { -using Tree = ImmutableSet<int>::TreeTy; +// Non-canonicalizing set (matches the dataflow analyses' usage). +using IntSet = ImmutableSet<int, ImutContainerInfo<int>, 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 +65,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 +130,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..1c646e81d9307 100644 --- a/llvm/include/llvm/ADT/ImmutableSet.h +++ b/llvm/include/llvm/ADT/ImmutableSet.h @@ -38,22 +38,59 @@ 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 = ty... [truncated] `````````` </details> https://github.com/llvm/llvm-project/pull/209300 _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
