Index: include/clang/Serialization/ModuleManager.h =================================================================== --- include/clang/Serialization/ModuleManager.h +++ include/clang/Serialization/ModuleManager.h @@ -32,6 +32,10 @@ /// \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 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 Roots; /// \brief All loaded modules, indexed by name. llvm::DenseMap Modules; @@ -264,25 +268,35 @@ /// manager that is *not* in this set can be skipped. void visit(bool (*Visitor)(ModuleFile &M, void *UserData), void *UserData, llvm::SmallPtrSetImpl *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). + /// loaded module. The traversal invokes one callback before + /// traversing the imports (preorder traversal) and one after + /// traversing the imports (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. + /// \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. Index: lib/Serialization/ASTReader.cpp =================================================================== --- lib/Serialization/ASTReader.cpp +++ lib/Serialization/ASTReader.cpp @@ -6157,10 +6157,7 @@ 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(UserData); @@ -6202,7 +6199,8 @@ // 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; } Index: lib/Serialization/ASTReaderDecl.cpp =================================================================== --- lib/Serialization/ASTReaderDecl.cpp +++ lib/Serialization/ASTReaderDecl.cpp @@ -3311,11 +3311,13 @@ 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(UserData)->visitPreorder(M); + } - return static_cast(UserData)->visit(M); + static bool visitPostorder(ModuleFile &M, void *UserData) { + return static_cast(UserData)->visitPostorder(M); } void addToChain(Decl *D) { @@ -3368,8 +3370,36 @@ 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]); @@ -3401,11 +3431,12 @@ // 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 Chain = Visitor.getChain(); - if (Chain.empty()) + if (Chain.empty() || (Chain.size() == 1 && Chain[0] == CanonDecl)) return; // Hook up the chains. Index: lib/Serialization/ModuleManager.cpp =================================================================== --- lib/Serialization/ModuleManager.cpp +++ lib/Serialization/ModuleManager.cpp @@ -94,6 +94,8 @@ New->File = Entry; New->ImportLoc = ImportLoc; Chain.push_back(New); + if (!ImportedBy) + Roots.push_back(New); NewModule = true; ModuleEntry = New; @@ -155,7 +157,12 @@ // 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; @@ -186,12 +193,15 @@ // Collect the set of module file pointers that we'll be removing. llvm::SmallPtrSet 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) { @@ -398,16 +408,38 @@ returnVisitState(State); } +static void markVisitedDepthFirst(ModuleFile &M, + SmallVectorImpl &Visited) { + for (llvm::SetVector::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 &Visited) { - // Preorder visitation - if (Visitor(M, /*Preorder=*/true, UserData)) - return true; - +static bool visitDepthFirst( + ModuleFile &M, + ModuleManager::DFSPreorderControl (*PreorderVisitor)(ModuleFile &M, + void *UserData), + bool (*PostorderVisitor)(ModuleFile &M, void *UserData), void *UserData, + SmallVectorImpl &Visited) { + 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::iterator IM = M.Imports.begin(), IMEnd = M.Imports.end(); @@ -416,24 +448,27 @@ 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 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; } }