[Concepts] Constraint Satisfaction Caching

[saar.raz]

Summary

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.

[rsmith]

Mechanically, this looks fine.

There's an ongoing discussion in the committee as to whether this kind of caching is permissible. But if this is necessary for acceptable performance, let's take this for now and figure out how to invalidate the cache as necessary later. Perhaps a -f flag to turn this off would be useful, so we can demonstrate and measure the performance delta.

[david_stone]

In D72552#1832293, @rsmith wrote:

Mechanically, this looks fine.

There's an ongoing discussion in the committee as to whether this kind of caching is permissible. But if this is necessary for acceptable performance, let's take this for now and figure out how to invalidate the cache as necessary later. Perhaps a -f flag to turn this off would be useful, so we can demonstrate and measure the performance delta.

If there were a flag to turn this on and off, I would be happy to provide numbers for a real code base so we can understand how important of an optimization this is.

[rtrieu]

clang/lib/AST/ASTConcept.cpp

17

This causes a circular dependency between AST and Sema. It looks like you are including this header to get access to some classes, but you should include the direct header instead. These are the headers for the classes you are using in ConstraintSatisfaction::Profile:

NamedDecl -> clang/AST/Decl.h
TemplateArgument -> clang/AST/TemplateBase.h
ArrayRef -> llvm/ADT/ArrayRef.h
FoldingSetNodeID -> llvm/ADT/FoldingSet.h

Please update the header includes to resolve the circular dependency.

[JDevlieghere]

It looks like the concept changes broke the debugger (quite spectacularly actually):

http://lab.llvm.org:8011/builders/lldb-x86_64-debian/builds/3356
http://lab.llvm.org:8011/builders/lldb-x64-windows-ninja/builds/12872
http://green.lab.llvm.org/green/view/LLDB/job/lldb-cmake/6407/

I'm rebuilding locally to see if I can reproduce

[JDevlieghere]

In D72552#1832875, @JDevlieghere wrote:

It looks like the concept changes broke the debugger (quite spectacularly actually):

http://lab.llvm.org:8011/builders/lldb-x86_64-debian/builds/3356
http://lab.llvm.org:8011/builders/lldb-x64-windows-ninja/builds/12872
http://green.lab.llvm.org/green/view/LLDB/job/lldb-cmake/6407/

I'm rebuilding locally to see if I can reproduce

Most likely because of https://reviews.llvm.org/D65042 rather than this change, I see you made changes to the AST importer.

clang/include/clang/AST/ASTConcept.h

 #include "llvm/ADT/PointerUnion.h"
 #include "llvm/ADT/SmallVector.h"
 #include <string>
 #include <utility>
 namespace clang {
 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<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 *>;
 
   bool IsSatisfied = false;
 
   /// \brief Pairs of unsatisfied atomic constraint expressions along with the
   /// substituted constraint expr, if the template arguments could be
   /// substituted into them, or a diagnostic if substitution resulted in an
   /// 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
 /// substituted constraint expr, if the template arguments could be
 /// substituted into them, or a diagnostic if substitution resulted in
 /// an invalid expression.
 using UnsatisfiedConstraintRecord =
     std::pair<const Expr *,
public:
   }
 
   void print(llvm::raw_ostream &OS, PrintingPolicy Policy) const;
 };
 
 } // clang
 
 #endif // LLVM_CLANG_AST_ASTCONCEPT_H
 No newline at end of file

clang/include/clang/Basic/LangOptions.def

 
 LANGOPT(HIPUseNewLaunchAPI, 1, 0, "Use new kernel launching API for HIP")
 
 LANGOPT(SizedDeallocation , 1, 0, "sized deallocation")
 LANGOPT(AlignedAllocation , 1, 0, "aligned allocation")
 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")
 BENIGN_LANGOPT(DumpRecordLayouts , 1, 0, "dumping the layout of IRgen'd records")
 BENIGN_LANGOPT(DumpRecordLayoutsSimple , 1, 0, "dumping the layout of IRgen'd records in a simple form")
 BENIGN_LANGOPT(DumpVTableLayouts , 1, 0, "dumping the layouts of emitted vtables")
 LANGOPT(NoConstantCFStrings , 1, 0, "no constant CoreFoundation strings")
 BENIGN_LANGOPT(InlineVisibilityHidden , 1, 0, "hidden visibility for inline C++ methods")

clang/include/clang/Driver/CC1Options.td

def fmodule_format_EQ : Joined<["-"], "fmodule-format=">,
   HelpText<"Select the container format for clang modules and PCH. "
            "Supported options are 'raw' and 'obj'.">;
 def ftest_module_file_extension_EQ :
   Joined<["-"], "ftest-module-file-extension=">,
   HelpText<"introduce a module file extension for testing purposes. "
            "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 {
 
 def Eonly : Flag<["-"], "Eonly">,
   HelpText<"Just run preprocessor, no output (for timings)">;
 def dump_raw_tokens : Flag<["-"], "dump-raw-tokens">,
   HelpText<"Lex file in raw mode and dump raw tokens">;
 def analyze : Flag<["-"], "analyze">,

clang/include/clang/Sema/Sema.h

private:
   llvm::DenseMap<std::pair<NamedDecl *, 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<NamedDecl *, NormalizedConstraint *>
       NormalizationCache;
 
+  llvm::ContextualFoldingSet<ConstraintSatisfaction, const ASTContext &>
+      SatisfactionCache;
+
 public:
   const NormalizedConstraint *
   getNormalizedAssociatedConstraints(
       NamedDecl *ConstrainedDecl, ArrayRef<const Expr *> AssociatedConstraints);
 
   /// \brief Check whether the given declaration's associated constraints are
   /// at least as constrained than another declaration's according to the
   /// partial ordering of constraints.
public:
   /// of atomic constraints involved had been declared in a concept and not
   /// repeated in two separate places in code.
   /// \returns true if such a diagnostic was emitted, false otherwise.
   bool MaybeEmitAmbiguousAtomicConstraintsDiagnostic(NamedDecl *D1,
       ArrayRef<const Expr *> AC1, NamedDecl *D2, ArrayRef<const Expr *> AC2);
 
   /// \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
   /// constraint expression.
   /// \param TemplateIDRange The source range of the template id that
   /// caused the constraints check.
   /// \param Satisfaction if true is returned, will contain details of the
   /// satisfaction, with enough information to diagnose an unsatisfied
   /// 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,
+      SourceRange TemplateIDRange, ConstraintSatisfaction &Satisfaction);
 
   /// \brief Check whether the given non-dependent constraint expression is
   /// satisfied. Returns false and updates Satisfaction with the satisfaction
   /// verdict if successful, emits a diagnostic and returns true if an error
   /// occured and satisfaction could not be determined.
   ///
   /// \returns true if an error occurred, false otherwise.
   bool CheckConstraintSatisfaction(const Expr *ConstraintExpr,

clang/include/clang/Sema/TemplateDeduction.h

 // routines.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_SEMA_TEMPLATEDEDUCTION_H
 #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"
 #include "clang/AST/TemplateBase.h"
 #include "clang/Basic/PartialDiagnostic.h"
 #include "clang/Basic/SourceLocation.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/SmallVector.h"

clang/lib/AST/ASTConcept.cpp

 //===--- ASTConcept.cpp - Concepts Related AST Data Structures --*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
 /// \brief This file defines AST data structures related to concepts.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "clang/AST/ASTConcept.h"
 #include "clang/AST/ASTContext.h"
+#include "clang/Sema/SemaConcept.h"
 using namespace clang;
 
 ASTConstraintSatisfaction::ASTConstraintSatisfaction(const ASTContext &C,
     const ConstraintSatisfaction &Satisfaction):
     NumRecords{Satisfaction.Details.size()},
     IsSatisfied{Satisfaction.IsSatisfied} {
   for (unsigned I = 0; I < NumRecords; ++I) {
     auto &Detail = Satisfaction.Details[I];

 ASTConstraintSatisfaction::Create(const ASTContext &C,
                                   const ConstraintSatisfaction &Satisfaction) {
   std::size_t size =
       totalSizeToAlloc<UnsatisfiedConstraintRecord>(
           Satisfaction.Details.size());
   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);
+}

clang/lib/Frontend/CompilerInvocation.cpp

Opts.NewAlignOverride =
       getLastArgIntValue(Args, OPT_fnew_alignment_EQ, 0, Diags);
   if (Opts.NewAlignOverride && !llvm::isPowerOf2_32(Opts.NewAlignOverride)) {
     Arg *A = Args.getLastArg(OPT_fnew_alignment_EQ);
     Diags.Report(diag::err_fe_invalid_alignment) << A->getAsString(Args)
                                                  << A->getValue();
     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);
   Opts.MathErrno = !Opts.OpenCL && Args.hasArg(OPT_fmath_errno);
   Opts.InstantiationDepth =
       getLastArgIntValue(Args, OPT_ftemplate_depth, 1024, Diags);
   Opts.ArrowDepth =
       getLastArgIntValue(Args, OPT_foperator_arrow_depth, 256, Diags);

clang/lib/Sema/Sema.cpp

: ExternalSource(nullptr), isMultiplexExternalSource(false),
       MSVCGuidDecl(nullptr), NSNumberDecl(nullptr), NSValueDecl(nullptr),
       NSStringDecl(nullptr), StringWithUTF8StringMethod(nullptr),
       ValueWithBytesObjCTypeMethod(nullptr), NSArrayDecl(nullptr),
       ArrayWithObjectsMethod(nullptr), NSDictionaryDecl(nullptr),
       DictionaryWithObjectsMethod(nullptr), GlobalNewDeleteDeclared(false),
       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;
   isConstantEvaluatedOverride = false;
 
   LoadedExternalKnownNamespaces = false;
   for (unsigned I = 0; I != NSAPI::NumNSNumberLiteralMethods; ++I)
     NSNumberLiteralMethods[I] = nullptr;
Sema::~Sema() {
   if (ExternalSemaSource *ExternalSema
         = dyn_cast_or_null<ExternalSemaSource>(Context.getExternalSource()))
     ExternalSema->ForgetSema();
 
   // If Sema's ExternalSource is the multiplexer - we own it.
   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
   DestroyDataSharingAttributesStack();
 
   // Detach from the PP callback handler which outlives Sema since it's owned
   // by the preprocessor.
   SemaPPCallbackHandler->reset();

clang/lib/Sema/SemaConcept.cpp

if (!Satisfaction.IsSatisfied)
       //   [...] To determine if a conjunction is satisfied, the satisfaction
       //   of the first operand is checked. If that is not satisfied, the
       //   conjunction is not satisfied. [...]
       return false;
   }
   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 &OutSatisfaction) {
+  if (ConstraintExprs.empty()) {
+    OutSatisfaction.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,
+  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<TemplateDecl>(Template))
+    Failed = ::CheckConstraintSatisfaction(*this, T, ConstraintExprs,
                                            TemplateArgs, TemplateIDRange,
-                                       Satisfaction);
+                                           *Satisfaction);
+  else if (auto *P =
+               dyn_cast<ClassTemplatePartialSpecializationDecl>(Template))
+    Failed = ::CheckConstraintSatisfaction(*this, P, ConstraintExprs,
+                                           TemplateArgs, TemplateIDRange,
+                                           *Satisfaction);
+  else
+    Failed = ::CheckConstraintSatisfaction(
+        *this, cast<VarTemplatePartialSpecializationDecl>(Template),
+        ConstraintExprs, TemplateArgs, TemplateIDRange, *Satisfaction);
+  if (Failed) {
+    if (LangOpts.ConceptSatisfactionCaching)
+      delete Satisfaction;
+    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);
+  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,
                                        ConstraintSatisfaction &Satisfaction) {
   return calculateConstraintSatisfaction(
       *this, ConstraintExpr, Satisfaction,
       [](const Expr *AtomicExpr) -> ExprResult {
         return ExprResult(const_cast<Expr *>(AtomicExpr));

clang/test/SemaTemplate/cxx2a-constraint-caching.cpp

+// 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<typename T>
+concept C = (f(T()), true);
+
+template<typename T>
+constexpr bool foo() { return false; }
+
+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);
+}
+#ifdef NO_CACHE
+static_assert(!C<a::A>);
+static_assert(!foo<a::A>());
+#else
+static_assert(C<a::A>);
+static_assert(foo<a::A>());
+#endif
 No newline at end of file