Author: Nico Weber Date: 2026-09-29T00:14:07-07:00 New Revision: e8c09d19de8212bfb2d5c760c43a21e27729f660
URL: https://github.com/llvm/llvm-project/commit/e8c09d19de8212bfb2d5c760c43a21e27729f660 DIFF: https://github.com/llvm/llvm-project/commit/e8c09d19de8212bfb2d5c760c43a21e27729f660.diff LOG: [clang] Cache normalized constraints by expression instead of by declaration (#226620) Sema::NormalizationCache was 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. When compiling Chromium, 48% (chrome/browser/glic/...contents_manager.cc) to 72% (chrome/browser/ui/views/frame/browser_view.cc) of all NormalizationCache misses were for expressions that were normalized before for a different declaration, and normalization is 4.5% of all compile time in a sampling profile. Instead, key the cache by (expression, pack index). Each associated constraint is cached separately, and we form the conjunction of a declaration's associated constraints on every call. That's cheap, and getNormalizedAssociatedConstraints() is only called on SatisfactionCache misses and for subsumption checks. Failures are cached as nullptr, like before. 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 on the non-error case. (If several declarations share a constraint expression that fails to normalize (e.g. the members of different specializations of a class template), we now diagnose the failure once instead of once per declaration.) Added: Modified: clang/docs/InternalsManual.md clang/include/clang/Sema/Sema.h clang/lib/Sema/SemaConcept.cpp Removed: ################################################################################ diff --git a/clang/docs/InternalsManual.md b/clang/docs/InternalsManual.md index 8d5549cb168be..58d1819b0a947 100644 --- a/clang/docs/InternalsManual.md +++ b/clang/docs/InternalsManual.md @@ -2871,8 +2871,9 @@ Clang preserves in the normalized form intermediate concept-ids (`ConceptIdConstraint`) This is used for diagnostics only and no substitution happens in a ConceptIdConstraint if its expression is satisfied. -The normal form of the associated constraints of a declaration is cached in -Sema::NormalizationCache such that it is only computed once. +The normal form of each associated constraint expression is cached in +`Sema::NormalizedConstraintExprCache`, so that it is only computed once even if +several declarations share it (e.g. members of class template specializations). A `NormalizedConstraint` is a recursive data structure, where each node contains a parameter mapping, represented by the indexes of all parameter diff --git a/clang/include/clang/Sema/Sema.h b/clang/include/clang/Sema/Sema.h index eb3b908351448..e33073c652dba 100644 --- a/clang/include/clang/Sema/Sema.h +++ b/clang/include/clang/Sema/Sema.h @@ -15180,12 +15180,12 @@ 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. If an error occurred while + /// normalizing an expression, nullptr will be cached here. + 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..9ef76b758d5fe 100644 --- a/clang/lib/Sema/SemaConcept.cpp +++ b/clang/lib/Sema/SemaConcept.cpp @@ -2528,19 +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()) { - auto *Normalized = NormalizedConstraint::fromAssociatedConstraints( - *this, ND, AssociatedConstraints); - // substitute() can invalidate iterators of NormalizationCache. - if (Normalized && - SubstituteParameterMappings(*this).substitute(*Normalized)) - Normalized = nullptr; - CacheEntry = - NormalizationCache.try_emplace(ConstrainedDeclOrNestedReq, Normalized) - .first; + // 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 (!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
