[modules] Rework merging of redeclaration chains on module import.

We used to save out and eagerly load a (potentially huge) table of merged
formerly-canonical declarations when we loaded each module. This was extremely
inefficient in the presence of large amounts of merging, and didn't actually
save any merging lookup work, because we still needed to perform name lookup to
check that our merged declaration lists were complete. This also resulted in a
loss of laziness -- even if we only needed an early declaration of an entity, we
would eagerly pull in all declarations that had been merged into it regardless.

We now store the relevant fragments of the table within the declarations
themselves. In detail:

 * The first declaration of each entity within a module stores a list of first
   declarations from imported modules that are merged into it.
 * Loading that declaration pre-loads those other entities, so that they appear
   earlier within the redeclaration chain.
 * The name lookup tables list the most recent local lookup result, if there
   is one, or all directly-imported lookup results if not.

llvm-svn: 231424

4 files changed, 120 insertions, 152 deletions

diff --git a/clang/lib/Serialization/ASTReader.cpp b/clang/lib/Serialization/ASTReader.cpp
index 78c44d17887..930b651f9ef 100644
--- a/clang/lib/Serialization/ASTReader.cpp
+++ b/clang/lib/Serialization/ASTReader.cpp
@@ -3316,16 +3316,6 @@ ASTReader::ReadASTBlock(ModuleFile &F, unsigned ClientLoadCapabilities) {
       break;
     }
         
-    case MERGED_DECLARATIONS: {
-      for (unsigned Idx = 0; Idx < Record.size(); /* increment in loop */) {
-        GlobalDeclID CanonID = getGlobalDeclID(F, Record[Idx++]);
-        SmallVectorImpl<GlobalDeclID> &Decls = StoredMergedDecls[CanonID];
-        for (unsigned N = Record[Idx++]; N > 0; --N)
-          Decls.push_back(getGlobalDeclID(F, Record[Idx++]));
-      }
-      break;
-    }
-
     case MACRO_OFFSET: {
       if (F.LocalNumMacros != 0) {
         Error("duplicate MACRO_OFFSET record in AST file");
@@ -6227,6 +6217,10 @@ ASTReader::getGlobalDeclID(ModuleFile &F, LocalDeclID LocalID) const {
 
 bool ASTReader::isDeclIDFromModule(serialization::GlobalDeclID ID,
                                    ModuleFile &M) const {
+  // Predefined decls aren't from any module.
+  if (ID < NUM_PREDEF_DECL_IDS)
+    return false;
+
   GlobalDeclMapType::const_iterator I = GlobalDeclMap.find(ID);
   assert(I != GlobalDeclMap.end() && "Corrupted global declaration map");
   return &M == I->second;
@@ -6259,39 +6253,51 @@ SourceLocation ASTReader::getSourceLocationForDeclID(GlobalDeclID ID) {
   return ReadSourceLocation(*Rec.F, RawLocation);
 }
 
-Decl *ASTReader::GetExistingDecl(DeclID ID) {
-  if (ID < NUM_PREDEF_DECL_IDS) {
-    switch ((PredefinedDeclIDs)ID) {
-    case PREDEF_DECL_NULL_ID:
-      return nullptr;
+static Decl *getPredefinedDecl(ASTContext &Context, PredefinedDeclIDs ID) {
+  switch (ID) {
+  case PREDEF_DECL_NULL_ID:
+    return nullptr;
 
-    case PREDEF_DECL_TRANSLATION_UNIT_ID:
-      return Context.getTranslationUnitDecl();
+  case PREDEF_DECL_TRANSLATION_UNIT_ID:
+    return Context.getTranslationUnitDecl();
 
-    case PREDEF_DECL_OBJC_ID_ID:
-      return Context.getObjCIdDecl();
+  case PREDEF_DECL_OBJC_ID_ID:
+    return Context.getObjCIdDecl();
 
-    case PREDEF_DECL_OBJC_SEL_ID:
-      return Context.getObjCSelDecl();
+  case PREDEF_DECL_OBJC_SEL_ID:
+    return Context.getObjCSelDecl();
 
-    case PREDEF_DECL_OBJC_CLASS_ID:
-      return Context.getObjCClassDecl();
+  case PREDEF_DECL_OBJC_CLASS_ID:
+    return Context.getObjCClassDecl();
 
-    case PREDEF_DECL_OBJC_PROTOCOL_ID:
-      return Context.getObjCProtocolDecl();
+  case PREDEF_DECL_OBJC_PROTOCOL_ID:
+    return Context.getObjCProtocolDecl();
 
-    case PREDEF_DECL_INT_128_ID:
-      return Context.getInt128Decl();
+  case PREDEF_DECL_INT_128_ID:
+    return Context.getInt128Decl();
 
-    case PREDEF_DECL_UNSIGNED_INT_128_ID:
-      return Context.getUInt128Decl();
+  case PREDEF_DECL_UNSIGNED_INT_128_ID:
+    return Context.getUInt128Decl();
 
-    case PREDEF_DECL_OBJC_INSTANCETYPE_ID:
-      return Context.getObjCInstanceTypeDecl();
+  case PREDEF_DECL_OBJC_INSTANCETYPE_ID:
+    return Context.getObjCInstanceTypeDecl();
+
+  case PREDEF_DECL_BUILTIN_VA_LIST_ID:
+    return Context.getBuiltinVaListDecl();
+  }
+}
 
-    case PREDEF_DECL_BUILTIN_VA_LIST_ID:
-      return Context.getBuiltinVaListDecl();
+Decl *ASTReader::GetExistingDecl(DeclID ID) {
+  if (ID < NUM_PREDEF_DECL_IDS) {
+    Decl *D = getPredefinedDecl(Context, (PredefinedDeclIDs)ID);
+    if (D) {
+      // Track that we have merged the declaration with ID \p ID into the
+      // pre-existing predefined declaration \p D.
+      auto &Merged = MergedDecls[D->getCanonicalDecl()];
+      if (Merged.empty())
+        Merged.push_back(ID);
     }
+    return D;
   }
 
   unsigned Index = ID - NUM_PREDEF_DECL_IDS;
@@ -8302,9 +8308,11 @@ void ASTReader::finishPendingActions() {
     PendingIncompleteDeclChains.clear();
 
     // Load pending declaration chains.
-    for (unsigned I = 0; I != PendingDeclChains.size(); ++I)
+    for (unsigned I = 0; I != PendingDeclChains.size(); ++I) {
       loadPendingDeclChain(PendingDeclChains[I]);
-    PendingDeclChainsKnown.clear();
+      PendingDeclChainsKnown.erase(PendingDeclChains[I]);
+    }
+    assert(PendingDeclChainsKnown.empty());
     PendingDeclChains.clear();
 
     // Make the most recent of the top-level declarations visible.
diff --git a/clang/lib/Serialization/ASTReaderDecl.cpp b/clang/lib/Serialization/ASTReaderDecl.cpp
index 375bdfb392e..5aeb3d1e517 100644
--- a/clang/lib/Serialization/ASTReaderDecl.cpp
+++ b/clang/lib/Serialization/ASTReaderDecl.cpp
@@ -123,9 +123,6 @@ namespace clang {
     /// \brief RAII class used to capture the first ID within a redeclaration
     /// chain and to introduce it into the list of pending redeclaration chains
     /// on destruction.
-    ///
-    /// The caller can choose not to introduce this ID into the list of pending
-    /// redeclaration chains by calling \c suppress().
     class RedeclarableResult {
       ASTReader &Reader;
       GlobalDeclID FirstID;
@@ -149,9 +146,11 @@ namespace clang {
       }
 
       ~RedeclarableResult() {
-        if (FirstID && Owning && isRedeclarableDeclKind(DeclKind) &&
-            Reader.PendingDeclChainsKnown.insert(FirstID).second)
-          Reader.PendingDeclChains.push_back(FirstID);
+        if (FirstID && Owning && isRedeclarableDeclKind(DeclKind)) {
+          auto Canon = Reader.GetDecl(FirstID)->getCanonicalDecl();
+          if (Reader.PendingDeclChainsKnown.insert(Canon).second)
+            Reader.PendingDeclChains.push_back(Canon);
+        }
       }
 
       /// \brief Retrieve the first ID.
@@ -160,12 +159,6 @@ namespace clang {
       /// \brief Get a known declaration that this should be merged with, if
       /// any.
       Decl *getKnownMergeTarget() const { return MergeWith; }
-
-      /// \brief Do not introduce this declaration ID into the set of pending
-      /// declaration chains.
-      void suppress() {
-        Owning = false;
-      }
     };
 
     /// \brief Class used to capture the result of searching for an existing
@@ -2076,12 +2069,14 @@ ASTDeclReader::VisitRedeclarable(Redeclarable<T> *D) {
   // and is used for space optimization.
   if (FirstDeclID == 0)
     FirstDeclID = ThisDeclID;
-  else if (Record[Idx++]) {
-    // We need to merge with FirstDeclID. Read it now to ensure that it is
-    // before us in the redecl chain, then forget we saw it so that we will
-    // merge with it.
-    MergeWith = Reader.GetDecl(FirstDeclID);
-    FirstDeclID = ThisDeclID;
+  else if (unsigned N = Record[Idx++]) {
+    // We have some declarations that must be before us in our redeclaration
+    // chain. Read them now, and remember that we ought to merge with one of
+    // them.
+    // FIXME: Provide a known merge target to the second and subsequent such
+    // declaration.
+    for (unsigned I = 0; I != N; ++I)
+      MergeWith = ReadDecl(Record, Idx/*, MergeWith*/);
   }
 
   T *FirstDecl = cast_or_null<T>(Reader.GetDecl(FirstDeclID));
@@ -2109,17 +2104,6 @@ void ASTDeclReader::mergeRedeclarable(Redeclarable<T> *DBase,
                                       RedeclarableResult &Redecl,
                                       DeclID TemplatePatternID) {
   T *D = static_cast<T*>(DBase);
-  T *DCanon = D->getCanonicalDecl();
-  if (D != DCanon &&
-      // IDs < NUM_PREDEF_DECL_IDS are not loaded from an AST file.
-      Redecl.getFirstID() >= NUM_PREDEF_DECL_IDS &&
-      (!Reader.getContext().getLangOpts().Modules ||
-       Reader.getOwningModuleFile(DCanon) == Reader.getOwningModuleFile(D))) {
-    // All redeclarations between this declaration and its originally-canonical
-    // declaration get pulled in when we load DCanon; we don't need to
-    // perform any more merging now.
-    Redecl.suppress();
-  }
 
   // If modules are not available, there is no reason to perform this merge.
   if (!Reader.getContext().getLangOpts().Modules)
@@ -2215,10 +2199,9 @@ void ASTDeclReader::mergeRedeclarable(Redeclarable<T> *DBase, T *Existing,
     // that. We accept the linear algorithm here because the number of
     // unique canonical declarations of an entity should always be tiny.
     if (DCanon == D) {
-      SmallVectorImpl<DeclID> &Merged = Reader.MergedDecls[ExistingCanon];
-      if (std::find(Merged.begin(), Merged.end(), Redecl.getFirstID())
-            == Merged.end())
-        Merged.push_back(Redecl.getFirstID());
+      Reader.MergedDecls[ExistingCanon].push_back(Redecl.getFirstID());
+      if (Reader.PendingDeclChainsKnown.insert(ExistingCanon).second)
+        Reader.PendingDeclChains.push_back(ExistingCanon);
     }
   }
 }
@@ -2697,8 +2680,6 @@ ASTDeclReader::FindExistingResult ASTDeclReader::findExisting(NamedDecl *D) {
     // unmergeable contexts.
     FindExistingResult Result(Reader, D, /*Existing=*/nullptr,
                               AnonymousDeclNumber, TypedefNameForLinkage);
-    // FIXME: We may still need to pull in the redeclaration chain; there can
-    // be redeclarations via 'decltype'.
     Result.suppress();
     return Result;
   }
@@ -2930,29 +2911,6 @@ void ASTReader::markIncompleteDeclChain(Decl *D) {
   }
 }
 
-ASTReader::MergedDeclsMap::iterator
-ASTReader::combineStoredMergedDecls(Decl *Canon, GlobalDeclID CanonID) {
-  // If we don't have any stored merged declarations, just look in the
-  // merged declarations set.
-  StoredMergedDeclsMap::iterator StoredPos = StoredMergedDecls.find(CanonID);
-  if (StoredPos == StoredMergedDecls.end())
-    return MergedDecls.find(Canon);
-
-  // Append the stored merged declarations to the merged declarations set.
-  MergedDeclsMap::iterator Pos = MergedDecls.find(Canon);
-  if (Pos == MergedDecls.end())
-    Pos = MergedDecls.insert(std::make_pair(Canon,
-                                            SmallVector<DeclID, 2>())).first;
-  Pos->second.append(StoredPos->second.begin(), StoredPos->second.end());
-  StoredMergedDecls.erase(StoredPos);
-
-  // Sort and uniquify the set of merged declarations.
-  llvm::array_pod_sort(Pos->second.begin(), Pos->second.end());
-  Pos->second.erase(std::unique(Pos->second.begin(), Pos->second.end()),
-                    Pos->second.end());
-  return Pos;
-}
-
 /// \brief Read the declaration at the given offset from the AST file.
 Decl *ASTReader::ReadDeclRecord(DeclID ID) {
   unsigned Index = ID - NUM_PREDEF_DECL_IDS;
@@ -3362,25 +3320,25 @@ namespace {
   };
 }
 
-void ASTReader::loadPendingDeclChain(serialization::GlobalDeclID ID) {
-  Decl *D = GetDecl(ID);  
-  Decl *CanonDecl = D->getCanonicalDecl();
-  
+void ASTReader::loadPendingDeclChain(Decl *CanonDecl) {
+  // The decl might have been merged into something else after being added to
+  // our list. If it was, just skip it.
+  if (!CanonDecl->isCanonicalDecl())
+    return;
+
   // Determine the set of declaration IDs we'll be searching for.
-  SmallVector<DeclID, 1> SearchDecls;
-  GlobalDeclID CanonID = 0;
-  if (D == CanonDecl) {
-    SearchDecls.push_back(ID); // Always first.
-    CanonID = ID;
-  }
-  MergedDeclsMap::iterator MergedPos = combineStoredMergedDecls(CanonDecl, ID);
+  SmallVector<DeclID, 16> SearchDecls;
+  GlobalDeclID CanonID = CanonDecl->getGlobalID();
+  if (CanonID)
+    SearchDecls.push_back(CanonDecl->getGlobalID()); // Always first.
+  MergedDeclsMap::iterator MergedPos = MergedDecls.find(CanonDecl);
   if (MergedPos != MergedDecls.end())
     SearchDecls.append(MergedPos->second.begin(), MergedPos->second.end());
-  
+
   // Build up the list of redeclarations.
   RedeclChainVisitor Visitor(*this, SearchDecls, RedeclsDeserialized, CanonID);
   ModuleMgr.visitDepthFirst(&RedeclChainVisitor::visit, &Visitor);
-  
+
   // Retrieve the chains.
   ArrayRef<Decl *> Chain = Visitor.getChain();
   if (Chain.empty())
diff --git a/clang/lib/Serialization/ASTWriter.cpp b/clang/lib/Serialization/ASTWriter.cpp
index e04c46ed982..29ed5c366cd 100644
--- a/clang/lib/Serialization/ASTWriter.cpp
+++ b/clang/lib/Serialization/ASTWriter.cpp
@@ -924,7 +924,6 @@ void ASTWriter::WriteBlockInfoBlock() {
   RECORD(OBJC_CATEGORIES_MAP);
   RECORD(FILE_SORTED_DECLS);
   RECORD(IMPORTED_MODULES);
-  RECORD(MERGED_DECLARATIONS);
   RECORD(LOCAL_REDECLARATIONS);
   RECORD(OBJC_CATEGORIES);
   RECORD(MACRO_OFFSET);
@@ -3115,7 +3114,7 @@ static NamedDecl *getDeclForLocalLookup(const LangOptions &LangOpts,
     for (; Redecl; Redecl = Redecl->getPreviousDecl()) {
       if (!Redecl->isFromASTFile())
         return cast<NamedDecl>(Redecl);
-      // If we come up a decl from a (chained-)PCH stop since we won't find a
+      // If we find a decl from a (chained-)PCH stop since we won't find a
       // local one.
       if (D->getOwningModuleID() == 0)
         break;
@@ -3671,14 +3670,24 @@ void ASTWriter::visitLocalLookupResults(const DeclContext *ConstDC,
 
   SmallVector<DeclarationName, 16> ExternalNames;
   for (auto &Lookup : *DC->buildLookup()) {
-    // If there are no local declarations in our lookup result, we don't
-    // need to write an entry for the name at all unless we're rewriting
-    // the decl context.
-    if (!Lookup.second.hasLocalDecls() && !isRewritten(cast<Decl>(DC)))
-      continue;
-
     if (Lookup.second.hasExternalDecls() ||
         DC->NeedToReconcileExternalVisibleStorage) {
+      // If there are no local declarations in our lookup result, we don't
+      // need to write an entry for the name at all unless we're rewriting
+      // the decl context. If we can't write out a lookup set without
+      // performing more deserialization, just skip this entry.
+      if (!isRewritten(cast<Decl>(DC))) {
+        bool AllFromASTFile = true;
+        for (auto *D : Lookup.second.getLookupResult()) {
+          AllFromASTFile &=
+              getDeclForLocalLookup(getLangOpts(), D)->isFromASTFile();
+          if (!AllFromASTFile)
+            break;
+        }
+        if (AllFromASTFile)
+          continue;
+      }
+
       // We don't know for sure what declarations are found by this name,
       // because the external source might have a different set from the set
       // that are in the lookup map, and we can't update it now without
@@ -3898,10 +3907,6 @@ void ASTWriter::WriteRedeclarations() {
         if (Prev->isFromASTFile())
           FirstFromAST = Prev;
       }
-
-      // FIXME: Do we need to do this for the first declaration from each
-      // redeclaration chain that was merged into this one?
-      Chain->MergedDecls[FirstFromAST].push_back(getDeclID(First));
     }
 
     LocalRedeclChains[Offset] = Size;
@@ -3998,25 +4003,6 @@ void ASTWriter::WriteObjCCategories() {
   Stream.EmitRecord(OBJC_CATEGORIES, Categories);
 }
 
-void ASTWriter::WriteMergedDecls() {
-  if (!Chain || Chain->MergedDecls.empty())
-    return;
-  
-  RecordData Record;
-  for (ASTReader::MergedDeclsMap::iterator I = Chain->MergedDecls.begin(),
-                                        IEnd = Chain->MergedDecls.end();
-       I != IEnd; ++I) {
-    DeclID CanonID = I->first->isFromASTFile()? I->first->getGlobalID()
-                                              : GetDeclRef(I->first);
-    assert(CanonID && "Merged declaration not known?");
-    
-    Record.push_back(CanonID);
-    Record.push_back(I->second.size());
-    Record.append(I->second.begin(), I->second.end());
-  }
-  Stream.EmitRecord(MERGED_DECLARATIONS, Record);
-}
-
 void ASTWriter::WriteLateParsedTemplates(Sema &SemaRef) {
   Sema::LateParsedTemplateMapT &LPTMap = SemaRef.LateParsedTemplateMap;
 
@@ -4699,7 +4685,6 @@ void ASTWriter::WriteASTCore(Sema &SemaRef,
 
   WriteDeclReplacementsBlock();
   WriteRedeclarations();
-  WriteMergedDecls();
   WriteObjCCategories();
   WriteLateParsedTemplates(SemaRef);
   if(!WritingModule)
diff --git a/clang/lib/Serialization/ASTWriterDecl.cpp b/clang/lib/Serialization/ASTWriterDecl.cpp
index e4353cd41d0..723f4caea80 100644
--- a/clang/lib/Serialization/ASTWriterDecl.cpp
+++ b/clang/lib/Serialization/ASTWriterDecl.cpp
@@ -1461,24 +1461,41 @@ void ASTDeclWriter::VisitRedeclarable(Redeclarable<T> *D) {
     assert(isRedeclarableDeclKind(static_cast<T *>(D)->getKind()) &&
            "Not considered redeclarable?");
 
+    // There is more than one declaration of this entity, so we will need to
+    // write a redeclaration chain.
+    Writer.AddDeclRef(First, Record);
+    Writer.Redeclarations.insert(First);
+
     auto *Previous = D->getPreviousDecl();
-    auto *FirstToEmit = First;
-    if (Context.getLangOpts().Modules && Writer.Chain && !Previous) {
-      // In a modules build, we can have imported declarations after a local
-      // canonical declaration. If we do, we want to treat the first imported
-      // declaration as our canonical declaration on reload, in order to
-      // rebuild the redecl chain in the right order.
+
+    // In a modules build, we can have imported declarations after a local
+    // canonical declaration. If this is the first local declaration, emit
+    // a list of all such imported declarations so that we can ensure they
+    // are loaded before we are. This allows us to rebuild the redecl chain
+    // in the right order on reload (all declarations imported by a module
+    // should be before all declarations provided by that module).
+    bool EmitImportedMergedCanonicalDecls = false;
+    if (Context.getLangOpts().Modules && Writer.Chain) {
+      auto *PreviousLocal = Previous;
+      while (PreviousLocal && PreviousLocal->isFromASTFile())
+        PreviousLocal = PreviousLocal->getPreviousDecl();
+      if (!PreviousLocal)
+        EmitImportedMergedCanonicalDecls = true;
+    }
+    if (EmitImportedMergedCanonicalDecls) {
+      llvm::SmallMapVector<ModuleFile*, Decl*, 16> FirstInModule;
       for (auto *Redecl = MostRecent; Redecl;
            Redecl = Redecl->getPreviousDecl())
         if (Redecl->isFromASTFile())
-          FirstToEmit = Redecl;
-    }
-
-    // There is more than one declaration of this entity, so we will need to
-    // write a redeclaration chain.
-    Writer.AddDeclRef(FirstToEmit, Record);
-    Record.push_back(FirstToEmit != First);
-    Writer.Redeclarations.insert(First);
+          FirstInModule[Writer.Chain->getOwningModuleFile(Redecl)] = Redecl;
+      // FIXME: If FirstInModule has entries for modules A and B, and B imports
+      // A (directly or indirectly), we don't need to write the entry for A.
+      Record.push_back(FirstInModule.size());
+      for (auto I = FirstInModule.rbegin(), E = FirstInModule.rend();
+           I != E; ++I)
+        Writer.AddDeclRef(I->second, Record);
+    } else
+      Record.push_back(0);
 
     // Make sure that we serialize both the previous and the most-recent 
     // declarations, which (transitively) ensures that all declarations in the