diff --git a/clang/include/clang/AST/ASTConcept.h b/clang/include/clang/AST/ASTConcept.h --- a/clang/include/clang/AST/ASTConcept.h +++ b/clang/include/clang/AST/ASTConcept.h @@ -24,9 +24,23 @@ class ConceptDecl; class ConceptSpecializationExpr; -/// \brief The result of a constraint satisfaction check, containing the -/// necessary information to diagnose an unsatisfied constraint. -struct ConstraintSatisfaction { +/// The result of a constraint satisfaction check, containing the necessary +/// information to diagnose an unsatisfied constraint. +class ConstraintSatisfaction : public llvm::FoldingSetNode { + // The template-like entity that 'owns' the constraint checked here (can be a + // constrained entity or a concept). + NamedDecl *ConstraintOwner = nullptr; + llvm::SmallVector TemplateArgs; + +public: + + ConstraintSatisfaction() = default; + + ConstraintSatisfaction(NamedDecl *ConstraintOwner, + ArrayRef TemplateArgs) : + ConstraintOwner(ConstraintOwner), TemplateArgs(TemplateArgs.begin(), + TemplateArgs.end()) { } + using SubstitutionDiagnostic = std::pair; using Detail = llvm::PointerUnion; @@ -38,9 +52,13 @@ /// invalid expression. llvm::SmallVector, 4> Details; - // This can leak if used in an AST node, use ASTConstraintSatisfaction - // instead. - void *operator new(size_t bytes, ASTContext &C) = delete; + void Profile(llvm::FoldingSetNodeID &ID, const ASTContext &C) { + Profile(ID, C, ConstraintOwner, TemplateArgs); + } + + static void Profile(llvm::FoldingSetNodeID &ID, const ASTContext &C, + NamedDecl *ConstraintOwner, + ArrayRef TemplateArgs); }; /// Pairs of unsatisfied atomic constraint expressions along with the diff --git a/clang/include/clang/Basic/LangOptions.def b/clang/include/clang/Basic/LangOptions.def --- a/clang/include/clang/Basic/LangOptions.def +++ b/clang/include/clang/Basic/LangOptions.def @@ -238,6 +238,7 @@ LANGOPT(AlignedAllocationUnavailable, 1, 0, "aligned allocation functions are unavailable") LANGOPT(NewAlignOverride , 32, 0, "maximum alignment guaranteed by '::operator new(size_t)'") LANGOPT(ConceptsTS , 1, 0, "enable C++ Extensions for Concepts") +LANGOPT(ConceptSatisfactionCaching , 1, 1, "enable satisfaction caching for C++2a Concepts") BENIGN_LANGOPT(ModulesCodegen , 1, 0, "Modules code generation") BENIGN_LANGOPT(ModulesDebugInfo , 1, 0, "Modules debug info") BENIGN_LANGOPT(ElideConstructors , 1, 1, "C++ copy constructor elision") diff --git a/clang/include/clang/Driver/CC1Options.td b/clang/include/clang/Driver/CC1Options.td --- a/clang/include/clang/Driver/CC1Options.td +++ b/clang/include/clang/Driver/CC1Options.td @@ -557,6 +557,9 @@ "The argument is parsed as blockname:major:minor:hashed:user info">; def fconcepts_ts : Flag<["-"], "fconcepts-ts">, HelpText<"Enable C++ Extensions for Concepts.">; +def fno_concept_satisfaction_caching : Flag<["-"], + "fno-concept-satisfaction-caching">, + HelpText<"Disable satisfaction caching for C++2a Concepts.">; let Group = Action_Group in { diff --git a/clang/include/clang/Sema/Sema.h b/clang/include/clang/Sema/Sema.h --- a/clang/include/clang/Sema/Sema.h +++ b/clang/include/clang/Sema/Sema.h @@ -6232,6 +6232,9 @@ llvm::DenseMap NormalizationCache; + llvm::ContextualFoldingSet + SatisfactionCache; + public: const NormalizedConstraint * getNormalizedAssociatedConstraints( @@ -6258,6 +6261,8 @@ /// \brief Check whether the given list of constraint expressions are /// satisfied (as if in a 'conjunction') given template arguments. + /// \param Template the template-like entity that triggered the constraints + /// check (either a concept or a constrained entity). /// \param ConstraintExprs a list of constraint expressions, treated as if /// they were 'AND'ed together. /// \param TemplateArgs the list of template arguments to substitute into the @@ -6269,23 +6274,10 @@ /// expression. /// \returns true if an error occurred and satisfaction could not be checked, /// false otherwise. - bool CheckConstraintSatisfaction(TemplateDecl *Template, - ArrayRef ConstraintExprs, - ArrayRef TemplateArgs, - SourceRange TemplateIDRange, - ConstraintSatisfaction &Satisfaction); - - bool CheckConstraintSatisfaction(ClassTemplatePartialSpecializationDecl *TD, - ArrayRef ConstraintExprs, - ArrayRef TemplateArgs, - SourceRange TemplateIDRange, - ConstraintSatisfaction &Satisfaction); - - bool CheckConstraintSatisfaction(VarTemplatePartialSpecializationDecl *TD, - ArrayRef ConstraintExprs, - ArrayRef TemplateArgs, - SourceRange TemplateIDRange, - ConstraintSatisfaction &Satisfaction); + bool CheckConstraintSatisfaction( + NamedDecl *Template, ArrayRef ConstraintExprs, + ArrayRef TemplateArgs, + SourceRange TemplateIDRange, ConstraintSatisfaction &Satisfaction); /// \brief Check whether the given non-dependent constraint expression is /// satisfied. Returns false and updates Satisfaction with the satisfaction diff --git a/clang/include/clang/Sema/TemplateDeduction.h b/clang/include/clang/Sema/TemplateDeduction.h --- a/clang/include/clang/Sema/TemplateDeduction.h +++ b/clang/include/clang/Sema/TemplateDeduction.h @@ -15,6 +15,7 @@ #define LLVM_CLANG_SEMA_TEMPLATEDEDUCTION_H #include "clang/Sema/Ownership.h" +#include "clang/Sema/SemaConcept.h" #include "clang/AST/ASTConcept.h" #include "clang/AST/DeclAccessPair.h" #include "clang/AST/DeclTemplate.h" diff --git a/clang/lib/AST/ASTConcept.cpp b/clang/lib/AST/ASTConcept.cpp --- a/clang/lib/AST/ASTConcept.cpp +++ b/clang/lib/AST/ASTConcept.cpp @@ -14,6 +14,7 @@ #include "clang/AST/ASTConcept.h" #include "clang/AST/ASTContext.h" +#include "clang/Sema/SemaConcept.h" using namespace clang; ASTConstraintSatisfaction::ASTConstraintSatisfaction(const ASTContext &C, @@ -53,3 +54,12 @@ void *Mem = C.Allocate(size, alignof(ASTConstraintSatisfaction)); return new (Mem) ASTConstraintSatisfaction(C, Satisfaction); } + +void ConstraintSatisfaction::Profile( + llvm::FoldingSetNodeID &ID, const ASTContext &C, NamedDecl *ConstraintOwner, + ArrayRef TemplateArgs) { + ID.AddPointer(ConstraintOwner); + ID.AddInteger(TemplateArgs.size()); + for (auto &Arg : TemplateArgs) + Arg.Profile(ID, C); +} diff --git a/clang/lib/Frontend/CompilerInvocation.cpp b/clang/lib/Frontend/CompilerInvocation.cpp --- a/clang/lib/Frontend/CompilerInvocation.cpp +++ b/clang/lib/Frontend/CompilerInvocation.cpp @@ -2859,6 +2859,8 @@ Opts.NewAlignOverride = 0; } Opts.ConceptsTS = Args.hasArg(OPT_fconcepts_ts); + Opts.ConceptSatisfactionCaching = + !Args.hasArg(OPT_fno_concept_satisfaction_caching); Opts.HeinousExtensions = Args.hasArg(OPT_fheinous_gnu_extensions); Opts.AccessControl = !Args.hasArg(OPT_fno_access_control); Opts.ElideConstructors = !Args.hasArg(OPT_fno_elide_constructors); diff --git a/clang/lib/Sema/Sema.cpp b/clang/lib/Sema/Sema.cpp --- a/clang/lib/Sema/Sema.cpp +++ b/clang/lib/Sema/Sema.cpp @@ -168,10 +168,10 @@ TUKind(TUKind), NumSFINAEErrors(0), FullyCheckedComparisonCategories( static_cast(ComparisonCategoryType::Last) + 1), - AccessCheckingSFINAE(false), InNonInstantiationSFINAEContext(false), - NonInstantiationEntries(0), ArgumentPackSubstitutionIndex(-1), - CurrentInstantiationScope(nullptr), DisableTypoCorrection(false), - TyposCorrected(0), AnalysisWarnings(*this), + SatisfactionCache(Context), AccessCheckingSFINAE(false), + InNonInstantiationSFINAEContext(false), NonInstantiationEntries(0), + ArgumentPackSubstitutionIndex(-1), CurrentInstantiationScope(nullptr), + DisableTypoCorrection(false), TyposCorrected(0), AnalysisWarnings(*this), ThreadSafetyDeclCache(nullptr), VarDataSharingAttributesStack(nullptr), CurScope(nullptr), Ident_super(nullptr), Ident___float128(nullptr) { TUScope = nullptr; @@ -394,6 +394,14 @@ if (isMultiplexExternalSource) delete ExternalSource; + // Delete cached satisfactions. + std::vector Satisfactions; + Satisfactions.reserve(Satisfactions.size()); + for (auto &Node : SatisfactionCache) + Satisfactions.push_back(&Node); + for (auto *Node : Satisfactions) + delete Node; + threadSafety::threadSafetyCleanup(ThreadSafetyDeclCache); // Destroys data sharing attributes stack for OpenMP diff --git a/clang/lib/Sema/SemaConcept.cpp b/clang/lib/Sema/SemaConcept.cpp --- a/clang/lib/Sema/SemaConcept.cpp +++ b/clang/lib/Sema/SemaConcept.cpp @@ -272,36 +272,56 @@ return false; } -bool Sema::CheckConstraintSatisfaction(TemplateDecl *Template, - ArrayRef ConstraintExprs, - ArrayRef TemplateArgs, - SourceRange TemplateIDRange, - ConstraintSatisfaction &Satisfaction) { - return ::CheckConstraintSatisfaction(*this, Template, ConstraintExprs, - TemplateArgs, TemplateIDRange, - Satisfaction); -} +bool Sema::CheckConstraintSatisfaction( + NamedDecl *Template, ArrayRef ConstraintExprs, + ArrayRef TemplateArgs, SourceRange TemplateIDRange, + ConstraintSatisfaction &OutSatisfaction) { + if (ConstraintExprs.empty()) { + OutSatisfaction.IsSatisfied = true; + return false; + } -bool -Sema::CheckConstraintSatisfaction(ClassTemplatePartialSpecializationDecl* Part, - ArrayRef ConstraintExprs, - ArrayRef TemplateArgs, - SourceRange TemplateIDRange, - ConstraintSatisfaction &Satisfaction) { - return ::CheckConstraintSatisfaction(*this, Part, ConstraintExprs, - TemplateArgs, TemplateIDRange, - Satisfaction); -} + llvm::FoldingSetNodeID ID; + void *InsertPos; + ConstraintSatisfaction *Satisfaction = nullptr; + if (LangOpts.ConceptSatisfactionCaching) { + ConstraintSatisfaction::Profile(ID, Context, Template, TemplateArgs); + Satisfaction = SatisfactionCache.FindNodeOrInsertPos(ID, InsertPos); + if (Satisfaction) { + OutSatisfaction = *Satisfaction; + return false; + } + Satisfaction = new ConstraintSatisfaction(Template, TemplateArgs); + } else { + Satisfaction = &OutSatisfaction; + } + bool Failed; + if (auto *T = dyn_cast(Template)) + Failed = ::CheckConstraintSatisfaction(*this, T, ConstraintExprs, + TemplateArgs, TemplateIDRange, + *Satisfaction); + else if (auto *P = + dyn_cast(Template)) + Failed = ::CheckConstraintSatisfaction(*this, P, ConstraintExprs, + TemplateArgs, TemplateIDRange, + *Satisfaction); + else + Failed = ::CheckConstraintSatisfaction( + *this, cast(Template), + ConstraintExprs, TemplateArgs, TemplateIDRange, *Satisfaction); + if (Failed) { + if (LangOpts.ConceptSatisfactionCaching) + delete Satisfaction; + return true; + } -bool -Sema::CheckConstraintSatisfaction(VarTemplatePartialSpecializationDecl* Partial, - ArrayRef ConstraintExprs, - ArrayRef TemplateArgs, - SourceRange TemplateIDRange, - ConstraintSatisfaction &Satisfaction) { - return ::CheckConstraintSatisfaction(*this, Partial, ConstraintExprs, - TemplateArgs, TemplateIDRange, - Satisfaction); + if (LangOpts.ConceptSatisfactionCaching) { + // We cannot use InsertNode here because CheckConstraintSatisfaction might + // have invalidated it. + SatisfactionCache.InsertNode(Satisfaction); + OutSatisfaction = *Satisfaction; + } + return false; } bool Sema::CheckConstraintSatisfaction(const Expr *ConstraintExpr, diff --git a/clang/test/SemaTemplate/cxx2a-constraint-caching.cpp b/clang/test/SemaTemplate/cxx2a-constraint-caching.cpp new file mode 100644 --- /dev/null +++ b/clang/test/SemaTemplate/cxx2a-constraint-caching.cpp @@ -0,0 +1,34 @@ +// RUN: %clang_cc1 -std=c++2a -fconcepts-ts -verify %s +// RUN: %clang_cc1 -std=c++2a -fconcepts-ts -verify %s -fno-concept-satisfaction-caching -DNO_CACHE +// expected-no-diagnostics + +template +concept C = (f(T()), true); + +template +constexpr bool foo() { return false; } + +template + requires (f(T()), true) +constexpr bool foo() requires (f(T()), true) { return true; } + +namespace a { + struct A {}; + void f(A a); +} + +static_assert(C); +static_assert(foo()); + +namespace a { + // This makes calls to f ambiguous, but the second check will still succeed + // because the constraint satisfaction results are cached. + void f(A a, int = 2); +} +#ifdef NO_CACHE +static_assert(!C); +static_assert(!foo()); +#else +static_assert(C); +static_assert(foo()); +#endif \ No newline at end of file