Speed up modules compilation.

[klimek]

Summary

Allow skipping children in the module visitor and use that to speed up
decl-chain loading.

[silvas]

Numbers on the speedup?

[klimek]

In D9498#167143, @silvas wrote:

Numbers on the speedup?

On my tests this is a 40% speedup for a TU using ~1000 transitive modules. I didn't include the number in the description because it is misleading; we are still merging too much, and we have merging-heavy TUs.

[klimek]

Ping

[rsmith]

Essentially this seems fine. It'd be better if visitDepthFirst didn't actually walk the the entire module graph in the case where it's been told to SkipChildren, but we can leave that improvement for a later change.

include/clang/Serialization/ModuleManager.h

297–300

These parameters seem backwards to me (on each node, we'll call the preorder visitor before the postorder one, so it would seem more natural for the preorder one to be written first in a call to this function).

lib/Serialization/ASTReaderDecl.cpp

3374

Children here is ambiguous, and entirely backwards from the way I think of the imports graph (where the roots import nothing and the leaves are not imported by anything). Calling this Imports would remove the ambiguity (likewise in the DFSPreorderControl enum).

3387–3389

A comment explaining what's going on here ("we don't need to visit a module or any of its imports if we've already deserialized the redecls from this module") would help.

[klimek]

Review comments.

[klimek]

In D9498#175201, @rsmith wrote:

Essentially this seems fine. It'd be better if visitDepthFirst didn't actually walk the the entire module graph in the case where it's been told to SkipChildren, but we can leave that improvement for a later change.

I'm not sure how that would be possible due to imports building a DAG.
The trade-off seems to be: either we remember the knowledge that all transitive deps do not need to be visited, or we might have to re-calculate that information when we come in via a different edge. My experiments indicate that the latter is common enough to offset the cost of the former.

include/clang/Serialization/ModuleManager.h

297–300

... says the person whose trees grow upside-down ;) Done.

lib/Serialization/ASTReaderDecl.cpp

3374

Note that there is precedence in the ModuleManager.h of calling the imports "children" :P
Your trees grow the wrong way (granted, this isn't *really* a tree).
On the other hand, "imports" is clearly the better name, so Done :D

3387–3389

Done.

include/clang/Serialization/ModuleManager.h

 
 namespace serialization {
 
 /// \brief Manages the set of modules loaded by an AST reader.
 class ModuleManager {
   /// \brief The chain of AST files. The first entry is the one named by the
   /// user, the last one is the one that doesn't depend on anything further.
   SmallVector<ModuleFile *, 2> Chain;
-  
+  // \brief The roots of the dependency DAG of AST files. This is used
+  // to implement short-circuiting logic when running DFS over the dependencies.
+  SmallVector<ModuleFile *, 2> Roots;
+  
   /// \brief All loaded modules, indexed by name.
   llvm::DenseMap<const FileEntry *, ModuleFile *> Modules;
 
   typedef llvm::SetVector<const FileEntry *> AdditionalKnownModuleFileSet;
 
   /// \brief Additional module files that are known but not loaded. Tracked
   /// here so that we can re-export them if necessary.
   AdditionalKnownModuleFileSet AdditionalKnownModuleFiles;
public:
   /// will be passed along to the visitor.
   ///
   /// \param ModuleFilesHit If non-NULL, contains the set of module files
   /// that we know we need to visit because the global module index told us to.
   /// Any module that is known to both the global module index and the module
   /// manager that is *not* in this set can be skipped.
   void visit(bool (*Visitor)(ModuleFile &M, void *UserData), void *UserData,
              llvm::SmallPtrSetImpl<ModuleFile *> *ModuleFilesHit = nullptr);
-  
+  /// \brief Control DFS behavior during preorder visitation.
+  enum DFSPreorderControl {
+    Continue,    /// Continue visiting all nodes.
+    Abort,       /// Stop the visitation immediately.
+    SkipImports, /// Do not visit imports of the current node.
+  };
+
   /// \brief Visit each of the modules with a depth-first traversal.
   ///
   /// This routine visits each of the modules known to the module
   /// manager using a depth-first search, starting with the first
-  /// loaded module. The traversal invokes the callback both before
-  /// traversing the children (preorder traversal) and after
-  /// traversing the children (postorder traversal).
-  ///
-  /// \param Visitor A visitor function that will be invoked with each
-  /// module and given a \c Preorder flag that indicates whether we're
-  /// visiting the module before or after visiting its children.  The
-  /// visitor may return true at any time to abort the depth-first
-  /// visitation.
+  /// loaded module. The traversal invokes one callback before
+  /// traversing the imports (preorder traversal) and one after
+  /// traversing the imports (postorder traversal).
+  ///
+  /// \param PreorderVisitor A visitor function that will be invoked with each
+  /// module before visiting its imports. The visitor can control how to
+  /// continue the visitation through its return value.
+  ///
+  /// \param PostorderVisitor A visitor function taht will be invoked with each
+  /// module after visiting its imports. The visitor may return true at any time
+  /// to abort the depth-first visitation.
   ///
   /// \param UserData User data ssociated with the visitor object,
   /// which will be passed along to the user.
-  void visitDepthFirst(bool (*Visitor)(ModuleFile &M, bool Preorder, 
-                                       void *UserData), 
+  void visitDepthFirst(DFSPreorderControl (*PreorderVisitor)(ModuleFile &M,
+                                                             void *UserData),
+                       bool (*PostorderVisitor)(ModuleFile &M, void *UserData),
                        void *UserData);
 
   /// \brief Attempt to resolve the given module file name to a file entry.
   ///
   /// \param FileName The name of the module file.
   ///
   /// \param ExpectedSize The size that the module file is expected to have.
   /// If the actual size differs, the resolver should return \c true.
   ///

lib/Serialization/ASTReader.cpp

FindExternalLexicalDeclsVisitor(ASTReader &Reader, const DeclContext *DC,
                                     bool (*isKindWeWant)(Decl::Kind),
                                     SmallVectorImpl<Decl*> &Decls)
       : Reader(Reader), DC(DC), isKindWeWant(isKindWeWant), Decls(Decls) 
     {
       for (unsigned I = 0; I != NUM_PREDEF_DECL_IDS; ++I)
         PredefsVisited[I] = false;
     }
 
-    static bool visit(ModuleFile &M, bool Preorder, void *UserData) {
-      if (Preorder)
-        return false;
-
+    static bool visitPostorder(ModuleFile &M, void *UserData) {
       FindExternalLexicalDeclsVisitor *This
         = static_cast<FindExternalLexicalDeclsVisitor *>(UserData);
 
       ModuleFile::DeclContextInfosMap::iterator Info
         = M.DeclContextInfos.find(This->DC);
       if (Info == M.DeclContextInfos.end() || !Info->second.LexicalDecls)
         return false;
 

 }
 
 ExternalLoadResult ASTReader::FindExternalLexicalDecls(const DeclContext *DC,
                                          bool (*isKindWeWant)(Decl::Kind),
                                          SmallVectorImpl<Decl*> &Decls) {
   // There might be lexical decls in multiple modules, for the TU at
   // least. Walk all of the modules in the order they were loaded.
   FindExternalLexicalDeclsVisitor Visitor(*this, DC, isKindWeWant, Decls);
-  ModuleMgr.visitDepthFirst(&FindExternalLexicalDeclsVisitor::visit, &Visitor);
+  ModuleMgr.visitDepthFirst(
+      nullptr, &FindExternalLexicalDeclsVisitor::visitPostorder, &Visitor);
   ++NumLexicalDeclContextsRead;
   return ELR_Success;
 }
 
 namespace {
 
 class DeclIDComp {
   ASTReader &Reader;

lib/Serialization/ASTReaderDecl.cpp

RedeclChainVisitor(ASTReader &Reader, SmallVectorImpl<DeclID> &SearchDecls,
                        llvm::SmallPtrSetImpl<Decl *> &Deserialized,
                        GlobalDeclID CanonID)
       : Reader(Reader), SearchDecls(SearchDecls), Deserialized(Deserialized),
         CanonID(CanonID) {
       // Ensure that the canonical ID goes at the start of the chain.
       addToChain(Reader.GetDecl(CanonID));
     }
 
-    static bool visit(ModuleFile &M, bool Preorder, void *UserData) {
-      if (Preorder)
-        return false;
+    static ModuleManager::DFSPreorderControl
+    visitPreorder(ModuleFile &M, void *UserData) {
+      return static_cast<RedeclChainVisitor *>(UserData)->visitPreorder(M);
+    }
 
-      return static_cast<RedeclChainVisitor *>(UserData)->visit(M);
+    static bool visitPostorder(ModuleFile &M, void *UserData) {
+      return static_cast<RedeclChainVisitor *>(UserData)->visitPostorder(M);
     }
 
     void addToChain(Decl *D) {
       if (!D)
         return;
 
       if (Deserialized.erase(D))
         Chain.push_back(D);
void searchForID(ModuleFile &M, GlobalDeclID GlobalID) {
       
       // Dig out all of the redeclarations.
       unsigned Offset = Result->Offset;
       unsigned N = M.RedeclarationChains[Offset];
       M.RedeclarationChains[Offset++] = 0; // Don't try to deserialize again
       for (unsigned I = 0; I != N; ++I)
         addToChain(Reader.GetLocalDecl(M, M.RedeclarationChains[Offset++]));
     }
-    
-    bool visit(ModuleFile &M) {
+    bool needsToVisitImports(ModuleFile &M, GlobalDeclID GlobalID) {
+      DeclID ID = Reader.mapGlobalIDToModuleFileGlobalID(M, GlobalID);
+      if (!ID)
+        return false;
+
+      const LocalRedeclarationsInfo Compare = {ID, 0};
+      const LocalRedeclarationsInfo *Result = std::lower_bound(
+          M.RedeclarationsMap,
+          M.RedeclarationsMap + M.LocalNumRedeclarationsInMap, Compare);
+      if (Result == M.RedeclarationsMap + M.LocalNumRedeclarationsInMap ||
+          Result->FirstID != ID) {
+        return true;
+      }
+      unsigned Offset = Result->Offset;
+      unsigned N = M.RedeclarationChains[Offset];
+      // We don't need to visit a module or any of its imports if we've already
+      // deserialized the redecls from this module.
+      return N != 0;
+    }
+
+    ModuleManager::DFSPreorderControl visitPreorder(ModuleFile &M) {
+      for (unsigned I = 0, N = SearchDecls.size(); I != N; ++I) {
+        if (needsToVisitImports(M, SearchDecls[I]))
+          return ModuleManager::Continue;
+      }
+      return ModuleManager::SkipImports;
+    }
+
+    bool visitPostorder(ModuleFile &M) {
       // Visit each of the declarations.
       for (unsigned I = 0, N = SearchDecls.size(); I != N; ++I)
         searchForID(M, SearchDecls[I]);
       // FIXME: If none of the SearchDecls had local IDs in this module, can
       // we avoid searching any ancestor module files?
       return false;
     }
     
void ASTReader::loadPendingDeclChain(Decl *CanonDecl) {
   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);
+  ModuleMgr.visitDepthFirst(&RedeclChainVisitor::visitPreorder,
+                            &RedeclChainVisitor::visitPostorder, &Visitor);
 
   // Retrieve the chains.
   ArrayRef<Decl *> Chain = Visitor.getChain();
-  if (Chain.empty())
+  if (Chain.empty() || (Chain.size() == 1 && Chain[0] == CanonDecl))
     return;
 
   // Hook up the chains.
   //
   // FIXME: We have three different dispatches on decl kind here; maybe
   // we should instead generate one loop per kind and dispatch up-front?
   Decl *MostRecent = ASTDeclReader::getMostRecentDecl(CanonDecl);
   if (!MostRecent)

lib/Serialization/ModuleManager.cpp

ModuleManager::addModule(StringRef FileName, ModuleKind Type,
   if (!ModuleEntry) {
     // Allocate a new module.
     ModuleFile *New = new ModuleFile(Type, Generation);
     New->Index = Chain.size();
     New->FileName = FileName.str();
     New->File = Entry;
     New->ImportLoc = ImportLoc;
     Chain.push_back(New);
+    if (!ImportedBy)
+      Roots.push_back(New);
     NewModule = true;
     ModuleEntry = New;
 
     New->InputFilesValidationTimestamp = 0;
     if (New->Kind == MK_ImplicitModule) {
       std::string TimestampFilename = New->getTimestampFilename();
       vfs::Status Status;
       // A cached stat value would be fine as well.
if (ModuleEntry->Signature != ExpectedSignature) {
       ErrorStr = ModuleEntry->Signature ? "signature mismatch"
                                         : "could not read module signature";
 
       if (NewModule) {
         // Remove the module file immediately, since removeModules might try to
         // invalidate the file cache for Entry, and that is not safe if this
         // module is *itself* up to date, but has an out-of-date importer.
         Modules.erase(Entry);
+        assert(Chain.back() == ModuleEntry);
         Chain.pop_back();
+        if (Roots.back() == ModuleEntry)
+          Roots.pop_back();
+        else
+          assert(ImportedBy);
         delete ModuleEntry;
       }
       return OutOfDate;
     }
   }
   
   if (ImportedBy) {
     ModuleEntry->ImportedBy.insert(ImportedBy);
void ModuleManager::removeModules(
     llvm::SmallPtrSetImpl<ModuleFile *> &LoadedSuccessfully,
     ModuleMap *modMap) {
   if (first == last)
     return;
 
   // Collect the set of module file pointers that we'll be removing.
   llvm::SmallPtrSet<ModuleFile *, 4> victimSet(first, last);
 
+  auto IsVictim = [&](ModuleFile *MF) {
+    return victimSet.count(MF);
+  };
   // Remove any references to the now-destroyed modules.
   for (unsigned i = 0, n = Chain.size(); i != n; ++i) {
-    Chain[i]->ImportedBy.remove_if([&](ModuleFile *MF) {
-      return victimSet.count(MF);
-    });
+    Chain[i]->ImportedBy.remove_if(IsVictim);
   }
+  Roots.erase(std::remove_if(Roots.begin(), Roots.end(), IsVictim),
+              Roots.end());
 
   // Delete the modules and erase them from the various structures.
   for (ModuleIterator victim = first; victim != last; ++victim) {
     Modules.erase((*victim)->File);
 
     if (modMap) {
       StringRef ModuleName = (*victim)->ModuleName;
       if (Module *mod = modMap->findModule(ModuleName)) {
do {
       // Pop the next module off the stack.
       NextModule = State->Stack.pop_back_val();
     } while (true);
   }
 
   returnVisitState(State);
 }
 
+static void markVisitedDepthFirst(ModuleFile &M,
+                                  SmallVectorImpl<bool> &Visited) {
+  for (llvm::SetVector<ModuleFile *>::iterator IM = M.Imports.begin(),
+                                               IMEnd = M.Imports.end();
+       IM != IMEnd; ++IM) {
+    if (Visited[(*IM)->Index])
+      continue;
+    Visited[(*IM)->Index] = true;
+    if (!M.DirectlyImported)
+      markVisitedDepthFirst(**IM, Visited);
+  }
+}
+
 /// \brief Perform a depth-first visit of the current module.
-static bool visitDepthFirst(ModuleFile &M, 
-                            bool (*Visitor)(ModuleFile &M, bool Preorder, 
-                                            void *UserData), 
-                            void *UserData,
-                            SmallVectorImpl<bool> &Visited) {
-  // Preorder visitation
-  if (Visitor(M, /*Preorder=*/true, UserData))
+static bool visitDepthFirst(
+    ModuleFile &M,
+    ModuleManager::DFSPreorderControl (*PreorderVisitor)(ModuleFile &M,
+                                                         void *UserData),
+    bool (*PostorderVisitor)(ModuleFile &M, void *UserData), void *UserData,
+  if (PreorderVisitor) {
+    switch (PreorderVisitor(M, UserData)) {
+    case ModuleManager::Abort:
       return true;
-  
+    case ModuleManager::SkipImports:
+      markVisitedDepthFirst(M, Visited);
+      return false;
+    case ModuleManager::Continue:
+      break;
+    }
+  }
   // Visit children
   for (llvm::SetVector<ModuleFile *>::iterator IM = M.Imports.begin(),
                                             IMEnd = M.Imports.end();
        IM != IMEnd; ++IM) {
     if (Visited[(*IM)->Index])
       continue;
     Visited[(*IM)->Index] = true;
 
-    if (visitDepthFirst(**IM, Visitor, UserData, Visited))
+    if (visitDepthFirst(**IM, PreorderVisitor, PostorderVisitor, UserData, Visited))
       return true;
   }  
   
-  // Postorder visitation
-  return Visitor(M, /*Preorder=*/false, UserData);
+  if (PostorderVisitor)
+    return PostorderVisitor(M, UserData);
+
+  return false;
 }
 
-void ModuleManager::visitDepthFirst(bool (*Visitor)(ModuleFile &M, bool Preorder, 
-                                                    void *UserData), 
-                                    void *UserData) {
+void ModuleManager::visitDepthFirst(
+    ModuleManager::DFSPreorderControl (*PreorderVisitor)(ModuleFile &M,
+                                                         void *UserData),
+    bool (*PostorderVisitor)(ModuleFile &M, void *UserData), void *UserData) {
   SmallVector<bool, 16> Visited(size(), false);
-  for (unsigned I = 0, N = Chain.size(); I != N; ++I) {
-    if (Visited[Chain[I]->Index])
+  for (unsigned I = 0, N = Roots.size(); I != N; ++I) {
+    if (Visited[Roots[I]->Index])
       continue;
-    Visited[Chain[I]->Index] = true;
+    Visited[Roots[I]->Index] = true;
 
-    if (::visitDepthFirst(*Chain[I], Visitor, UserData, Visited))
+    if (::visitDepthFirst(*Roots[I], PreorderVisitor, PostorderVisitor, UserData, Visited))
       return;
   }
 }
 
 bool ModuleManager::lookupModuleFile(StringRef FileName,
                                      off_t ExpectedSize,
                                      time_t ExpectedModTime,
                                      const FileEntry *&File) {