https://github.com/nico updated https://github.com/llvm/llvm-project/pull/226620
>From 8f0d879c2b83001ea339b1473c921a658b70eea1 Mon Sep 17 00:00:00 2001 From: Nico Weber <[email protected]> Date: Sun, 20 Sep 2026 09:50:30 -0400 Subject: [PATCH 1/2] [clang] Share normalized constraints between decls with same constraint expressions Sema::NormalizationCache is keyed by the constrained declaration. The members of a class template specialization are distinct declarations for every specialization, but they all share the uninstantiated constraint expressions of the member of the primary template they were instantiated from. So the constraints of e.g. the constrained constructors of std::optional, std::span, std::pair or of the members of range adaptors were normalized from scratch for every single specialization of those classes that a TU uses. Normalization is expensive: it expands the whole concept tree below the expression and substitutes the parameter mapping at every level. The normal form of a constraint expression depends on the expression (and the pack substitution index) only; the declaration is only used to detect recursion while normalizing. So add a second cache that is keyed by (expression, pack index) and that is consulted when a declaration is normalized for the first time. It caches each associated constraint separately; the conjunction of several is cheap to form. When compiling Chromium, 48% (chrome/browser/glic/...contents_manager.cc) to 72% (chrome/browser/ui/views/frame/browser_view.cc) of all NormalizationCache misses are for expressions that were normalized before for a different declaration, and normalization is 4.5% of all compile time in a sampling profile. Failures are not cached by expression, and substitution stops after the first failing constraint, so that errors are diagnosed like before for every declaration. Build time for 120 random Chromium TUs drawn with probability proportional to their compile time: CPU time: 470.0 s => 451.1 s, -4.0% instructions: 4948.9e9 => 4702.7e9, -5.0% mean max RSS: 779 MB => 710 MB, -8.9% (To check noise level, running this with the same binary twice: +-0.04% CPU time and +-0.01% instructions.) Recovers some more of the time lost to #161671 and contributes to improving issue #172266. No behavior change. --- clang/include/clang/Sema/Sema.h | 5 +++++ clang/lib/Sema/SemaConcept.cpp | 40 ++++++++++++++++++++++++++++----- 2 files changed, 40 insertions(+), 5 deletions(-) diff --git a/clang/include/clang/Sema/Sema.h b/clang/include/clang/Sema/Sema.h index eb3b908351448..f10a8af16d841 100644 --- a/clang/include/clang/Sema/Sema.h +++ b/clang/include/clang/Sema/Sema.h @@ -15186,6 +15186,11 @@ class Sema final : public SemaBase { /// here. llvm::DenseMap<ConstrainedDeclOrNestedRequirement, NormalizedConstraint *> NormalizationCache; + /// Caches the normal form of constraint expressions (and their pack + /// substitution index). These are shared by e.g. the members of all + /// specializations of a class template. Used to fill NormalizationCache. + llvm::DenseMap<std::pair<const Expr *, unsigned>, NormalizedConstraint *> + NormalizedConstraintExprCache; /// Cache whether the associated constraint of a declaration /// is satisfied. diff --git a/clang/lib/Sema/SemaConcept.cpp b/clang/lib/Sema/SemaConcept.cpp index da5e6f3f4dc75..30120e6528484 100644 --- a/clang/lib/Sema/SemaConcept.cpp +++ b/clang/lib/Sema/SemaConcept.cpp @@ -2530,11 +2530,41 @@ const NormalizedConstraint *Sema::getNormalizedAssociatedConstraints( const NamedDecl *ND = dyn_cast<const NamedDecl *>(ConstrainedDeclOrNestedReq); auto CacheEntry = NormalizationCache.find(ConstrainedDeclOrNestedReq); if (CacheEntry == NormalizationCache.end()) { - auto *Normalized = NormalizedConstraint::fromAssociatedConstraints( - *this, ND, AssociatedConstraints); - // substitute() can invalidate iterators of NormalizationCache. - if (Normalized && - SubstituteParameterMappings(*this).substitute(*Normalized)) + // The normal form only depends on the constraint expressions, and the + // members of all specializations of a class template share the + // (uninstantiated) constraint expressions of the member they were + // instantiated from. Look the expressions up in a second cache to not + // normalize the same expression once per class template specialization. + NormalizedConstraint *Normalized = nullptr; + bool Failed = false; + for (const AssociatedConstraint &AC : AssociatedConstraints) { + std::pair<const Expr *, unsigned> Key( + AC.ConstraintExpr, AC.ArgPackSubstIndex.toInternalRepresentation()); + NormalizedConstraint *Next; + if (auto It = NormalizedConstraintExprCache.find(Key); + It != NormalizedConstraintExprCache.end()) { + Next = It->second; + } else { + Next = NormalizedConstraint::fromAssociatedConstraints(*this, ND, AC); + // Stop substituting after the first failure, and don't cache + // failures, so that they behave the same for every declaration. + // Note that substitute() can invalidate iterators of both caches. + if (Next && !Failed) { + Failed = SubstituteParameterMappings(*this).substitute(*Next); + if (!Failed) + NormalizedConstraintExprCache.try_emplace(Key, Next); + } + } + if (!Next) { + NormalizationCache.try_emplace(ConstrainedDeclOrNestedReq, nullptr); + return nullptr; + } + Normalized = + Normalized + ? CompoundConstraint::CreateConjunction(Context, Normalized, Next) + : Next; + } + if (Failed) Normalized = nullptr; CacheEntry = NormalizationCache.try_emplace(ConstrainedDeclOrNestedReq, Normalized) >From 1b8b3ad2e61f42ef474cbb212446d271fb74a648 Mon Sep 17 00:00:00 2001 From: Nico Weber <[email protected]> Date: Mon, 28 Sep 2026 12:12:11 -0700 Subject: [PATCH 2/2] remove Sema::NormalizationCache (no perf change) --- clang/include/clang/Sema/Sema.h | 9 +---- clang/lib/Sema/SemaConcept.cpp | 67 +++++++++++++-------------------- 2 files changed, 28 insertions(+), 48 deletions(-) diff --git a/clang/include/clang/Sema/Sema.h b/clang/include/clang/Sema/Sema.h index f10a8af16d841..e33073c652dba 100644 --- a/clang/include/clang/Sema/Sema.h +++ b/clang/include/clang/Sema/Sema.h @@ -15180,15 +15180,10 @@ class Sema final : public SemaBase { /// fact subsume the second's. llvm::DenseMap<std::pair<const NamedDecl *, const NamedDecl *>, bool> SubsumptionCache; - /// Caches the normalized associated constraints of declarations (concepts or - /// constrained declarations). If an error occurred while normalizing the - /// associated constraints of the template or concept, nullptr will be cached - /// here. - llvm::DenseMap<ConstrainedDeclOrNestedRequirement, NormalizedConstraint *> - NormalizationCache; /// Caches the normal form of constraint expressions (and their pack /// substitution index). These are shared by e.g. the members of all - /// specializations of a class template. Used to fill NormalizationCache. + /// specializations of a class template. If an error occurred while + /// normalizing an expression, nullptr will be cached here. llvm::DenseMap<std::pair<const Expr *, unsigned>, NormalizedConstraint *> NormalizedConstraintExprCache; diff --git a/clang/lib/Sema/SemaConcept.cpp b/clang/lib/Sema/SemaConcept.cpp index 30120e6528484..9ef76b758d5fe 100644 --- a/clang/lib/Sema/SemaConcept.cpp +++ b/clang/lib/Sema/SemaConcept.cpp @@ -2528,49 +2528,34 @@ const NormalizedConstraint *Sema::getNormalizedAssociatedConstraints( // FIXME: ConstrainedDeclOrNestedReq is never a NestedRequirement! const NamedDecl *ND = dyn_cast<const NamedDecl *>(ConstrainedDeclOrNestedReq); - auto CacheEntry = NormalizationCache.find(ConstrainedDeclOrNestedReq); - if (CacheEntry == NormalizationCache.end()) { - // The normal form only depends on the constraint expressions, and the - // members of all specializations of a class template share the - // (uninstantiated) constraint expressions of the member they were - // instantiated from. Look the expressions up in a second cache to not - // normalize the same expression once per class template specialization. - NormalizedConstraint *Normalized = nullptr; - bool Failed = false; - for (const AssociatedConstraint &AC : AssociatedConstraints) { - std::pair<const Expr *, unsigned> Key( - AC.ConstraintExpr, AC.ArgPackSubstIndex.toInternalRepresentation()); - NormalizedConstraint *Next; - if (auto It = NormalizedConstraintExprCache.find(Key); - It != NormalizedConstraintExprCache.end()) { - Next = It->second; - } else { - Next = NormalizedConstraint::fromAssociatedConstraints(*this, ND, AC); - // Stop substituting after the first failure, and don't cache - // failures, so that they behave the same for every declaration. - // Note that substitute() can invalidate iterators of both caches. - if (Next && !Failed) { - Failed = SubstituteParameterMappings(*this).substitute(*Next); - if (!Failed) - NormalizedConstraintExprCache.try_emplace(Key, Next); - } - } - if (!Next) { - NormalizationCache.try_emplace(ConstrainedDeclOrNestedReq, nullptr); - return nullptr; - } - Normalized = - Normalized - ? CompoundConstraint::CreateConjunction(Context, Normalized, Next) - : Next; + // The normal form only depends on the constraint expressions, and the + // members of all specializations of a class template share the + // (uninstantiated) constraint expressions of the member they were + // instantiated from. Cache the normal form of each expression to not + // normalize the same expression once per class template specialization. + NormalizedConstraint *Normalized = nullptr; + for (const AssociatedConstraint &AC : AssociatedConstraints) { + std::pair<const Expr *, unsigned> Key( + AC.ConstraintExpr, AC.ArgPackSubstIndex.toInternalRepresentation()); + NormalizedConstraint *Next; + if (auto It = NormalizedConstraintExprCache.find(Key); + It != NormalizedConstraintExprCache.end()) { + Next = It->second; + } else { + Next = NormalizedConstraint::fromAssociatedConstraints(*this, ND, AC); + // substitute() can invalidate iterators of NormalizedConstraintExprCache. + if (Next && SubstituteParameterMappings(*this).substitute(*Next)) + Next = nullptr; + NormalizedConstraintExprCache.try_emplace(Key, Next); } - if (Failed) - Normalized = nullptr; - CacheEntry = - NormalizationCache.try_emplace(ConstrainedDeclOrNestedReq, Normalized) - .first; + if (!Next) + return nullptr; + Normalized = + Normalized + ? CompoundConstraint::CreateConjunction(Context, Normalized, Next) + : Next; } - return CacheEntry->second; + return Normalized; } bool FoldExpandedConstraint::AreCompatibleForSubsumption( _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
