Load lazily the template specialization in multi-module setups.

[v.g.vassilev]

Summary

Currently, we load all template specialization if we have more than one module attached and we touch anything around the template definition.

This patch registers the template specializations as a lazily-loadable entities. This reduces the amount of deserializations by 1%.

[aprantl]

lib/Serialization/ASTReaderDecl.cpp

3916

llvm_unreachable()

[v.g.vassilev]

Reduce code duplication. Use llvm_unreachable.

[rsmith]

lib/Serialization/ASTReaderDecl.cpp

213–215

Can this ever fail at runtime? I'd expect the below code to not compile if D isn't one of these types.

3893–3895

This will end up being quadratic time and using quadratic storage if a module adds N specializations to a template; instead, please move the SmallVector out of the loop and call AddLazySpecializations once after reading all the update records for the declaration. (It's probably best to move it all the way out to loadDeclUpdateRecords, in case we have a large number of modules each adding some specializations -- eg, if module A imports std::vector and declares A, module B declares B and uses vector<A>, module C declares C and uses vector<B>, ..., we again should avoid quadratic behavior.)

[v.g.vassilev]

Reduce the amount of calls to AddLazySpecializations. Remove assert.

In order to create a reasonable test I need to use -error-on-deserialized-decl and I hit a bug: https://bugs.llvm.org/show_bug.cgi?id=32988

Richard, could you help me out with the test? Maybe we could trigger this avoiding the abovementioned bug...

[rsmith]

include/clang/Serialization/ASTReader.h

551

I'm not sure we can safely use global state for this: loading update records can trigger the import of a declaration and *its* update records, which would mean we'd attach the pending lazy specializations to the wrong declaration. Can you keep this list locally in ASTReader::loadDeclUpdateRecords instead, and pass it into UpdateDecl?

1293–1295

Make this a static member of ASTDeclReader to avoid this hack.

[rsmith]

In D29951#750885, @v.g.vassilev wrote:

In order to create a reasonable test I need to use -error-on-deserialized-decl and I hit a bug: https://bugs.llvm.org/show_bug.cgi?id=32988

Richard, could you help me out with the test? Maybe we could trigger this avoiding the abovementioned bug...

You could try to test this using -dump-deserialized-decls instead, but it'd be good to figure out what's going wrong in the above bug :) Nothing in the backtrace looks at all related to -dump-deserialized-decls, but maybe we're messing up our internal state by calling into the DeserializationListeners at an unsafe point during deserialization?

[v.g.vassilev]

Address comments.

[rsmith]

Looks great, thanks!

[v.g.vassilev]

r305120.

[v.g.vassilev]

Reverted in r305460 because broke libcxx modules builds.

[v.g.vassilev]

For the record: relanded in r306903.

include/clang/Serialization/ASTReader.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_SERIALIZATION_ASTREADER_H
 #define LLVM_CLANG_SERIALIZATION_ASTREADER_H
 
 #include "clang/AST/DeclObjC.h"
 #include "clang/AST/DeclarationName.h"
+#include "clang/AST/DeclTemplate.h"
 #include "clang/AST/TemplateBase.h"
 #include "clang/Basic/Diagnostic.h"
 #include "clang/Basic/FileSystemOptions.h"
 #include "clang/Basic/IdentifierTable.h"
 #include "clang/Basic/Version.h"
 #include "clang/Lex/ExternalPreprocessorSource.h"
 #include "clang/Lex/HeaderSearch.h"
 #include "clang/Lex/PreprocessingRecord.h"
private:
   };
   typedef SmallVector<PendingVisibleUpdate, 1> DeclContextVisibleUpdates;
 
   /// \brief Updates to the visible declarations of declaration contexts that
   /// haven't been loaded yet.
   llvm::DenseMap<serialization::DeclID, DeclContextVisibleUpdates>
       PendingVisibleUpdates;
 
+  llvm::SmallVector<serialization::DeclID, 8> PendingLazySpecializationIDs;
+
+
   /// \brief The set of C++ or Objective-C classes that have forward 
   /// declarations that have not yet been linked to their definitions.
   llvm::SmallPtrSet<Decl *, 4> PendingDefinitions;
 
   typedef llvm::MapVector<Decl *, uint64_t,
                           llvm::SmallDenseMap<Decl *, unsigned, 4>,
                           SmallVector<std::pair<Decl *, uint64_t>, 4> >
     PendingBodiesMap;
private:
   /// \brief Returns the most recent declaration of a declaration (which must be
   /// of a redeclarable kind) that is either local or has already been loaded
   /// merged into its redecl chain.
   Decl *getMostRecentExistingDecl(Decl *D);
 
   RecordLocation DeclCursorForID(serialization::DeclID ID,
                                  SourceLocation &Location);
   void loadDeclUpdateRecords(serialization::DeclID ID, Decl *D);
+  template <typename T>
+  void AddLazySpecializations(T *D,
+                              SmallVectorImpl<serialization::DeclID>& IDs) {
+    if (IDs.empty())
+      return;
+
+    // FIXME: A hack to access the protected getCommonPtr. This is because
+    // AddLazySpecializations should be called in the ASTReader which is not a
+    // friend of Class,Function,VarTemplateDecl.
+    struct CommonPtrAccessor : public T {
+      static uint32_t *&getLazySpecializations(T *D) {
+        return ((CommonPtrAccessor*)D)->getCommonPtr()->LazySpecializations;
+      }
+    };
+    ASTContext &C = getContext();
+
+    auto *&LazySpecializations = CommonPtrAccessor::getLazySpecializations(D);
+
+    if (auto &Old = LazySpecializations) {
+      IDs.insert(IDs.end(), Old + 1, Old + 1 + Old[0]);
+      std::sort(IDs.begin(), IDs.end());
+      IDs.erase(std::unique(IDs.begin(), IDs.end()), IDs.end());
+    }
+
+    auto *Result = new (C) serialization::DeclID[1 + IDs.size()];
+    *Result = IDs.size();
+    std::copy(IDs.begin(), IDs.end(), Result + 1);
+
+    LazySpecializations = Result;
+  }
+
   void loadPendingDeclChain(Decl *D, uint64_t LocalOffset);
   void loadObjCCategories(serialization::GlobalDeclID ID, ObjCInterfaceDecl *D,
                           unsigned PreviousGeneration = 0);
 
   RecordLocation getLocalBitOffset(uint64_t GlobalOffset);
   uint64_t getGlobalBitOffset(ModuleFile &M, uint32_t LocalOffset);
 
   /// \brief Returns the first preprocessed entity ID that begins or ends after

lib/Serialization/ASTReaderDecl.cpp

class ASTDeclReader : public DeclVisitor<ASTDeclReader, void> {
     static DeclContext *getPrimaryContextForMerging(ASTReader &Reader,
                                                     DeclContext *DC);
     FindExistingResult findExisting(NamedDecl *D);
 
   public:
     ASTDeclReader(ASTReader &Reader, ASTRecordReader &Record,
                   ASTReader::RecordLocation Loc,
                   DeclID thisDeclID, SourceLocation ThisDeclLoc)
         : Reader(Reader), Record(Record), Loc(Loc),
           ThisDeclID(thisDeclID), ThisDeclLoc(ThisDeclLoc),
           TypeIDForTypeDecl(0), NamedDeclForTagDecl(0),
           TypedefNameForLinkage(nullptr), HasPendingBody(false),
           IsDeclMarkedUsed(false) {}
 
     template <typename DeclT>
     static Decl *getMostRecentDeclImpl(Redeclarable<DeclT> *D);
     static Decl *getMostRecentDeclImpl(...);
     static Decl *getMostRecentDecl(Decl *D);
 
ASTDeclReader::VisitRedeclarableTemplateDecl(RedeclarableTemplateDecl *D) {
   // If we merged the template with a prior declaration chain, merge the common
   // pointer.
   // FIXME: Actually merge here, don't just overwrite.
   D->Common = D->getCanonicalDecl()->Common;
 
   return Redecl;
 }
 
-static DeclID *newDeclIDList(ASTContext &Context, DeclID *Old,
-                             SmallVectorImpl<DeclID> &IDs) {
-  assert(!IDs.empty() && "no IDs to add to list");
-  if (Old) {
-    IDs.insert(IDs.end(), Old + 1, Old + 1 + Old[0]);
-    std::sort(IDs.begin(), IDs.end());
-    IDs.erase(std::unique(IDs.begin(), IDs.end()), IDs.end());
-  }
-
-  auto *Result = new (Context) DeclID[1 + IDs.size()];
-  *Result = IDs.size();
-  std::copy(IDs.begin(), IDs.end(), Result + 1);
-  return Result;
-}
-
 void ASTDeclReader::VisitClassTemplateDecl(ClassTemplateDecl *D) {
   RedeclarableResult Redecl = VisitRedeclarableTemplateDecl(D);
 
   if (ThisDeclID == Redecl.getFirstID()) {
     // This ClassTemplateDecl owns a CommonPtr; read it to keep track of all of
     // the specializations.
     SmallVector<serialization::DeclID, 32> SpecIDs;
     ReadDeclIDList(SpecIDs);
-
-    if (!SpecIDs.empty()) {
-      auto *CommonPtr = D->getCommonPtr();
-      CommonPtr->LazySpecializations = newDeclIDList(
-          Reader.getContext(), CommonPtr->LazySpecializations, SpecIDs);
-    }
+    Reader.AddLazySpecializations(D, SpecIDs);
   }
 
   if (D->getTemplatedDecl()->TemplateOrInstantiation) {
     // We were loaded before our templated declaration was. We've not set up
     // its corresponding type yet (see VisitCXXRecordDeclImpl), so reconstruct
     // it now.
     Reader.Context.getInjectedClassNameType(
         D->getTemplatedDecl(), D->getInjectedClassNameSpecialization());

 void ASTDeclReader::VisitVarTemplateDecl(VarTemplateDecl *D) {
   RedeclarableResult Redecl = VisitRedeclarableTemplateDecl(D);
 
   if (ThisDeclID == Redecl.getFirstID()) {
     // This VarTemplateDecl owns a CommonPtr; read it to keep track of all of
     // the specializations.
     SmallVector<serialization::DeclID, 32> SpecIDs;
     ReadDeclIDList(SpecIDs);
-
-    if (!SpecIDs.empty()) {
-      auto *CommonPtr = D->getCommonPtr();
-      CommonPtr->LazySpecializations = newDeclIDList(
-          Reader.getContext(), CommonPtr->LazySpecializations, SpecIDs);
-    }
+    Reader.AddLazySpecializations(D, SpecIDs);
   }
 }
 
 ASTDeclReader::RedeclarableResult
 ASTDeclReader::VisitClassTemplateSpecializationDeclImpl(
     ClassTemplateSpecializationDecl *D) {
   RedeclarableResult Redecl = VisitCXXRecordDeclImpl(D);
 

 
 void ASTDeclReader::VisitFunctionTemplateDecl(FunctionTemplateDecl *D) {
   RedeclarableResult Redecl = VisitRedeclarableTemplateDecl(D);
 
   if (ThisDeclID == Redecl.getFirstID()) {
     // This FunctionTemplateDecl owns a CommonPtr; read it.
     SmallVector<serialization::DeclID, 32> SpecIDs;
     ReadDeclIDList(SpecIDs);
-
-    if (!SpecIDs.empty()) {
-      auto *CommonPtr = D->getCommonPtr();
-      CommonPtr->LazySpecializations = newDeclIDList(
-          Reader.getContext(), CommonPtr->LazySpecializations, SpecIDs);
-    }
+    Reader.AddLazySpecializations(D, SpecIDs);
   }
 }
 
 /// TODO: Unify with ClassTemplateSpecializationDecl version?
 ///       May require unifying ClassTemplate(Partial)SpecializationDecl and
 ///        VarTemplate(Partial)SpecializationDecl with a new data
 ///        structure Template(Partial)SpecializationDecl, and
 ///        using Template(Partial)SpecializationDecl as input type.
for (auto &FileAndOffset : UpdateOffsets) {
       if (!WasInteresting &&
           isConsumerInterestedIn(Context, D, Reader.hasPendingBody())) {
         PotentiallyInterestingDecls.push_back(
             InterestingDecl(D, Reader.hasPendingBody()));
         WasInteresting = true;
       }
     }
   }
+  // Add the lazy specializations to the template.
+  assert((PendingLazySpecializationIDs.empty() || isa<ClassTemplateDecl>(D) ||
+          isa<FunctionTemplateDecl>(D) || isa<VarTemplateDecl>(D)) &&
+         "Must not have pending specializations");
+  if (auto *CTD = dyn_cast<ClassTemplateDecl>(D))
+    AddLazySpecializations(CTD, PendingLazySpecializationIDs);
+  else if (auto *FTD = dyn_cast<FunctionTemplateDecl>(D))
+    AddLazySpecializations(FTD, PendingLazySpecializationIDs);
+  else if (auto *VTD = dyn_cast<VarTemplateDecl>(D))
+    AddLazySpecializations(VTD, PendingLazySpecializationIDs);
+  PendingLazySpecializationIDs.clear();
 
   // Load the pending visible updates for this decl context, if it has any.
   auto I = PendingVisibleUpdates.find(ID);
   if (I != PendingVisibleUpdates.end()) {
     auto VisibleUpdates = std::move(I->second);
     PendingVisibleUpdates.erase(I);
 
     auto *DC = cast<DeclContext>(D)->getPrimaryContext();
case UPD_CXX_ADDED_IMPLICIT_MEMBER: {
       assert(MD && "couldn't read decl from update record");
       // FIXME: We should call addHiddenDecl instead, to add the member
       // to its DeclContext.
       RD->addedMember(MD);
       break;
     }
 
     case UPD_CXX_ADDED_TEMPLATE_SPECIALIZATION:
-      // It will be added to the template's specializations set when loaded.
-      (void)Record.readDecl();
+      // It will be added to the template's lazy specialization set.
+      Reader.PendingLazySpecializationIDs.push_back(ReadDeclID());
       break;
 
     case UPD_CXX_ADDED_ANONYMOUS_NAMESPACE: {
       NamespaceDecl *Anon = ReadDeclAs<NamespaceDecl>();
 
       // Each module has its own anonymous namespace, which is disjoint from
       // any other module's anonymous namespaces, so don't attach the anonymous
       // namespace at all.
       if (!Record.isModule()) {
         if (TranslationUnitDecl *TU = dyn_cast<TranslationUnitDecl>(D))
           TU->setAnonymousNamespace(Anon);
         else
           cast<NamespaceDecl>(D)->setAnonymousNamespace(Anon);
       }
       break;
     }
 
     case UPD_CXX_INSTANTIATED_STATIC_DATA_MEMBER:
       cast<VarDecl>(D)->getMemberSpecializationInfo()->setPointOfInstantiation(
           ReadSourceLocation());
       break;
 
     case UPD_CXX_INSTANTIATED_DEFAULT_ARGUMENT: {
       auto Param = cast<ParmVarDecl>(D);
 
       // We have to read the default argument regardless of whether we use it
       // so that hypothetical further update records aren't messed up.
       // TODO: Add a function to skip over the next expr record.
       auto DefaultArg = Record.readExpr();
 

test/Modules/Inputs/lazy-template-specializations/A.h

+#include "B.h"
+int i;
+

test/Modules/Inputs/lazy-template-specializations/B.h

+namespace N {
+  template <typename T> struct S { int a; };
+  template <> struct S<int> { double b; };
+}

test/Modules/Inputs/lazy-template-specializations/module.modulemap

+module A {
+  header "A.h"
+  export *
+}
+
+module B {
+  header "B.h"
+  export *
+}

test/Modules/lazy-template-specializations.cpp

+// RUN: rm -fr %t
+// RUN: %clang_cc1 -fmodules -fimplicit-module-maps -fmodules-cache-path=%t \
+// RUN:             -I %S/Inputs/lazy-template-specializations -std=c++11      \
+// RUN:             -error-on-deserialized-decl S -Rmodule-build %s
+
+
+#include "A.h"
+
+namespace N {
+}