saar.raz created this revision.
saar.raz added a reviewer: rsmith.
Herald added a project: clang.
Herald added a subscriber: cfe-commits.
Add a simple cache for constraint satisfaction results. This results in a
major speedup (cjdb measured x2 faster than gcc with this caching, compared
to being 'unbearably slow' without caching) and is conformant with gcc's
implementation.
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D72552
Files:
clang/include/clang/AST/ASTConcept.h
clang/include/clang/Sema/Sema.h
clang/include/clang/Sema/TemplateDeduction.h
clang/lib/AST/ASTConcept.cpp
clang/lib/Sema/Sema.cpp
clang/lib/Sema/SemaConcept.cpp
clang/test/SemaTemplate/cxx2a-constraint-caching.cpp
Index: clang/test/SemaTemplate/cxx2a-constraint-caching.cpp
===================================================================
--- /dev/null
+++ clang/test/SemaTemplate/cxx2a-constraint-caching.cpp
@@ -0,0 +1,25 @@
+// RUN: %clang_cc1 -std=c++2a -fconcepts-ts -verify %s
+// expected-no-diagnostics
+
+template<typename T>
+concept C = (f(T()), true);
+
+template<typename T>
+ requires (f(T()), true)
+constexpr bool foo() requires (f(T()), true) { return true; }
+
+namespace a {
+ struct A {};
+ void f(A a);
+}
+
+static_assert(C<a::A>);
+static_assert(foo<a::A>());
+
+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);
+}
+static_assert(C<a::A>);
+static_assert(foo<a::A>());
\ No newline at end of file
Index: clang/lib/Sema/SemaConcept.cpp
===================================================================
--- clang/lib/Sema/SemaConcept.cpp
+++ clang/lib/Sema/SemaConcept.cpp
@@ -269,36 +269,49 @@
return false;
}
-bool Sema::CheckConstraintSatisfaction(TemplateDecl *Template,
- ArrayRef<const Expr *> ConstraintExprs,
- ArrayRef<TemplateArgument> TemplateArgs,
- SourceRange TemplateIDRange,
- ConstraintSatisfaction &Satisfaction) {
- return ::CheckConstraintSatisfaction(*this, Template, ConstraintExprs,
- TemplateArgs, TemplateIDRange,
- Satisfaction);
-}
+bool Sema::CheckConstraintSatisfaction(
+ NamedDecl *Template, ArrayRef<const Expr *> ConstraintExprs,
+ ArrayRef<TemplateArgument> TemplateArgs, SourceRange TemplateIDRange,
+ ConstraintSatisfaction &Satisfaction) {
+ if (ConstraintExprs.empty()) {
+ Satisfaction.IsSatisfied = true;
+ return false;
+ }
-bool
-Sema::CheckConstraintSatisfaction(ClassTemplatePartialSpecializationDecl* Part,
- ArrayRef<const Expr *> ConstraintExprs,
- ArrayRef<TemplateArgument> TemplateArgs,
- SourceRange TemplateIDRange,
- ConstraintSatisfaction &Satisfaction) {
- return ::CheckConstraintSatisfaction(*this, Part, ConstraintExprs,
- TemplateArgs, TemplateIDRange,
- Satisfaction);
-}
+ llvm::FoldingSetNodeID ID;
+ void *InsertPos;
+ ConstraintSatisfaction::Profile(ID, Context, Template, TemplateArgs);
+ ConstraintSatisfaction *Cached =
+ SatisfactionCache.FindNodeOrInsertPos(ID, InsertPos);
+ if (!Cached) {
+ Cached = new ConstraintSatisfaction(Template, TemplateArgs);
+
+ bool Failed;
+ if (auto *T = dyn_cast<TemplateDecl>(Template))
+ Failed = ::CheckConstraintSatisfaction(*this, T, ConstraintExprs,
+ TemplateArgs, TemplateIDRange,
+ *Cached);
+ else if (auto *P =
+ dyn_cast<ClassTemplatePartialSpecializationDecl>(Template))
+ Failed = ::CheckConstraintSatisfaction(*this, P, ConstraintExprs,
+ TemplateArgs, TemplateIDRange,
+ *Cached);
+ else
+ Failed = ::CheckConstraintSatisfaction(
+ *this, cast<VarTemplatePartialSpecializationDecl>(Template),
+ ConstraintExprs, TemplateArgs, TemplateIDRange, *Cached);
+ if (Failed) {
+ delete Cached;
+ return true;
+ }
-bool
-Sema::CheckConstraintSatisfaction(VarTemplatePartialSpecializationDecl* Partial,
- ArrayRef<const Expr *> ConstraintExprs,
- ArrayRef<TemplateArgument> TemplateArgs,
- SourceRange TemplateIDRange,
- ConstraintSatisfaction &Satisfaction) {
- return ::CheckConstraintSatisfaction(*this, Partial, ConstraintExprs,
- TemplateArgs, TemplateIDRange,
- Satisfaction);
+ // We cannot use InsertNode here because CheckConstraintSatisfaction might
+ // have invalidated it.
+ SatisfactionCache.InsertNode(Cached);
+ }
+
+ Satisfaction = *Cached;
+ return false;
}
bool Sema::CheckConstraintSatisfaction(const Expr *ConstraintExpr,
Index: clang/lib/Sema/Sema.cpp
===================================================================
--- clang/lib/Sema/Sema.cpp
+++ clang/lib/Sema/Sema.cpp
@@ -153,10 +153,10 @@
TUKind(TUKind), NumSFINAEErrors(0),
FullyCheckedComparisonCategories(
static_cast<unsigned>(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;
@@ -379,6 +379,14 @@
if (isMultiplexExternalSource)
delete ExternalSource;
+ // Delete cached satisfactions.
+ std::vector<ConstraintSatisfaction *> 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
Index: clang/lib/AST/ASTConcept.cpp
===================================================================
--- clang/lib/AST/ASTConcept.cpp
+++ 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<TemplateArgument> TemplateArgs) {
+ ID.AddPointer(ConstraintOwner);
+ ID.AddInteger(TemplateArgs.size());
+ for (auto &Arg : TemplateArgs)
+ Arg.Profile(ID, C);
+}
Index: clang/include/clang/Sema/TemplateDeduction.h
===================================================================
--- clang/include/clang/Sema/TemplateDeduction.h
+++ 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"
Index: clang/include/clang/Sema/Sema.h
===================================================================
--- clang/include/clang/Sema/Sema.h
+++ clang/include/clang/Sema/Sema.h
@@ -6197,6 +6197,9 @@
llvm::DenseMap<NamedDecl *, NormalizedConstraint *>
NormalizationCache;
+ llvm::ContextualFoldingSet<ConstraintSatisfaction, const ASTContext &>
+ SatisfactionCache;
+
public:
const NormalizedConstraint *
getNormalizedAssociatedConstraints(
@@ -6223,6 +6226,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
@@ -6234,23 +6239,10 @@
/// expression.
/// \returns true if an error occurred and satisfaction could not be checked,
/// false otherwise.
- bool CheckConstraintSatisfaction(TemplateDecl *Template,
- ArrayRef<const Expr *> ConstraintExprs,
- ArrayRef<TemplateArgument> TemplateArgs,
- SourceRange TemplateIDRange,
- ConstraintSatisfaction &Satisfaction);
-
- bool CheckConstraintSatisfaction(ClassTemplatePartialSpecializationDecl *TD,
- ArrayRef<const Expr *> ConstraintExprs,
- ArrayRef<TemplateArgument> TemplateArgs,
- SourceRange TemplateIDRange,
- ConstraintSatisfaction &Satisfaction);
-
- bool CheckConstraintSatisfaction(VarTemplatePartialSpecializationDecl *TD,
- ArrayRef<const Expr *> ConstraintExprs,
- ArrayRef<TemplateArgument> TemplateArgs,
- SourceRange TemplateIDRange,
- ConstraintSatisfaction &Satisfaction);
+ bool CheckConstraintSatisfaction(
+ NamedDecl *Template, ArrayRef<const Expr *> ConstraintExprs,
+ ArrayRef<TemplateArgument> TemplateArgs,
+ SourceRange TemplateIDRange, ConstraintSatisfaction &Satisfaction);
/// \brief Check whether the given non-dependent constraint expression is
/// satisfied. Returns false and updates Satisfaction with the satisfaction
Index: clang/include/clang/AST/ASTConcept.h
===================================================================
--- clang/include/clang/AST/ASTConcept.h
+++ clang/include/clang/AST/ASTConcept.h
@@ -22,9 +22,23 @@
#include <utility>
namespace clang {
-/// \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<TemplateArgument, 4> TemplateArgs;
+
+public:
+
+ ConstraintSatisfaction() = default;
+
+ ConstraintSatisfaction(NamedDecl *ConstraintOwner,
+ ArrayRef<TemplateArgument> TemplateArgs) :
+ ConstraintOwner(ConstraintOwner), TemplateArgs(TemplateArgs.begin(),
+ TemplateArgs.end()) { }
+
using SubstitutionDiagnostic = std::pair<SourceLocation, StringRef>;
using Detail = llvm::PointerUnion<Expr *, SubstitutionDiagnostic *>;
@@ -36,9 +50,13 @@
/// invalid expression.
llvm::SmallVector<std::pair<const Expr *, Detail>, 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<TemplateArgument> TemplateArgs);
};
/// Pairs of unsatisfied atomic constraint expressions along with the
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
