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,7 +268,14 @@ /// 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. + SkipChildren, /// Do not visit children 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 @@ -281,8 +292,8 @@ /// /// \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(bool (*PostorderVisitor)(ModuleFile &M, void *UserData), + DFSPreorderControl (*PreorderVisitor)(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 @@ -6142,10 +6142,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); @@ -6187,7 +6184,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(&FindExternalLexicalDeclsVisitor::visitPostorder, + nullptr, &Visitor); ++NumLexicalDeclContextsRead; return ELR_Success; } Index: lib/Serialization/ASTReaderDecl.cpp =================================================================== --- lib/Serialization/ASTReaderDecl.cpp +++ lib/Serialization/ASTReaderDecl.cpp @@ -3300,11 +3300,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) { @@ -3357,8 +3359,34 @@ for (unsigned I = 0; I != N; ++I) addToChain(Reader.GetLocalDecl(M, M.RedeclarationChains[Offset++])); } - - bool visit(ModuleFile &M) { + + bool needsToVisitChildren(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]; + return N != 0; + } + + ModuleManager::DFSPreorderControl visitPreorder(ModuleFile &M) { + for (unsigned I = 0, N = SearchDecls.size(); I != N; ++I) { + if (needsToVisitChildren(M, SearchDecls[I])) + return ModuleManager::Continue; + } + return ModuleManager::SkipChildren; + } + + bool visitPostorder(ModuleFile &M) { // Visit each of the declarations. for (unsigned I = 0, N = SearchDecls.size(); I != N; ++I) searchForID(M, SearchDecls[I]); @@ -3390,11 +3418,12 @@ // Build up the list of redeclarations. RedeclChainVisitor Visitor(*this, SearchDecls, RedeclsDeserialized, CanonID); - ModuleMgr.visitDepthFirst(&RedeclChainVisitor::visit, &Visitor); + ModuleMgr.visitDepthFirst(&RedeclChainVisitor::visitPostorder, + &RedeclChainVisitor::visitPreorder, &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,37 @@ 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, bool (*PostorderVisitor)(ModuleFile &M, void *UserData), + ModuleManager::DFSPreorderControl (*PreorderVisitor)(ModuleFile &M, + void *UserData), + void *UserData, SmallVectorImpl &Visited) { + if (PreorderVisitor) { + switch (PreorderVisitor(M, UserData)) { + case ModuleManager::Abort: + return true; + case ModuleManager::SkipChildren: + 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 +447,28 @@ continue; Visited[(*IM)->Index] = true; - if (visitDepthFirst(**IM, Visitor, UserData, Visited)) + if (visitDepthFirst(**IM, PostorderVisitor, PreorderVisitor, 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( + bool (*PostorderVisitor)(ModuleFile &M, void *UserData), + ModuleManager::DFSPreorderControl (*PreorderVisitor)(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], PostorderVisitor, PreorderVisitor, UserData, Visited)) return; } }