diff options
Diffstat (limited to 'clang/lib')
| -rw-r--r-- | clang/lib/Frontend/CompilerInstance.cpp | 4 | ||||
| -rw-r--r-- | clang/lib/Serialization/ASTReader.cpp | 77 | ||||
| -rw-r--r-- | clang/lib/Serialization/GlobalModuleIndex.cpp | 404 | ||||
| -rw-r--r-- | clang/lib/Serialization/ModuleManager.cpp | 5 |
4 files changed, 462 insertions, 28 deletions
diff --git a/clang/lib/Frontend/CompilerInstance.cpp b/clang/lib/Frontend/CompilerInstance.cpp index 0e60c399220..a7f0770ec7b 100644 --- a/clang/lib/Frontend/CompilerInstance.cpp +++ b/clang/lib/Frontend/CompilerInstance.cpp @@ -61,7 +61,9 @@ void CompilerInstance::setInvocation(CompilerInvocation *Value) { } bool CompilerInstance::shouldBuildGlobalModuleIndex() const { - return BuildGlobalModuleIndex && !ModuleBuildFailed; + return (BuildGlobalModuleIndex || + (ModuleManager && ModuleManager->isGlobalIndexUnavailable())) && + !ModuleBuildFailed; } void CompilerInstance::setDiagnostics(DiagnosticsEngine *Value) { diff --git a/clang/lib/Serialization/ASTReader.cpp b/clang/lib/Serialization/ASTReader.cpp index e24fddfd348..38ff3002bdb 100644 --- a/clang/lib/Serialization/ASTReader.cpp +++ b/clang/lib/Serialization/ASTReader.cpp @@ -40,6 +40,7 @@ #include "clang/Sema/Scope.h" #include "clang/Sema/Sema.h" #include "clang/Serialization/ASTDeserializationListener.h" +#include "clang/Serialization/GlobalModuleIndex.h" #include "clang/Serialization/ModuleManager.h" #include "clang/Serialization/SerializationDiagnostic.h" #include "llvm/ADT/StringExtras.h" @@ -1377,15 +1378,17 @@ namespace { class IdentifierLookupVisitor { StringRef Name; unsigned PriorGeneration; + GlobalModuleIndex::SkipSet &SkipSet; unsigned &NumIdentifierLookups; unsigned &NumIdentifierLookupHits; IdentifierInfo *Found; public: IdentifierLookupVisitor(StringRef Name, unsigned PriorGeneration, + GlobalModuleIndex::SkipSet &SkipSet, unsigned &NumIdentifierLookups, unsigned &NumIdentifierLookupHits) - : Name(Name), PriorGeneration(PriorGeneration), + : Name(Name), PriorGeneration(PriorGeneration), SkipSet(SkipSet), NumIdentifierLookups(NumIdentifierLookups), NumIdentifierLookupHits(NumIdentifierLookupHits), Found() @@ -1399,7 +1402,11 @@ namespace { // If we've already searched this module file, skip it now. if (M.Generation <= This->PriorGeneration) return true; - + + // If this module file is in the skip set, don't bother looking in it. + if (This->SkipSet.count(M.File)) + return false; + ASTIdentifierLookupTable *IdTable = (ASTIdentifierLookupTable *)M.IdentifierLookupTable; if (!IdTable) @@ -1433,8 +1440,18 @@ void ASTReader::updateOutOfDateIdentifier(IdentifierInfo &II) { unsigned PriorGeneration = 0; if (getContext().getLangOpts().Modules) PriorGeneration = IdentifierGeneration[&II]; - - IdentifierLookupVisitor Visitor(II.getName(), PriorGeneration, + + // If there is a global index, look there first to determine which modules + // provably do not have any results for this identifier. + GlobalModuleIndex::SkipSet SkipSet; + if (!loadGlobalIndex()) { + SmallVector<const FileEntry *, 4> ModuleFiles; + if (GlobalIndex->lookupIdentifier(II.getName(), ModuleFiles)) { + SkipSet = GlobalIndex->computeSkipSet(ModuleFiles); + } + } + + IdentifierLookupVisitor Visitor(II.getName(), PriorGeneration, SkipSet, NumIdentifierLookups, NumIdentifierLookupHits); ModuleMgr.visit(IdentifierLookupVisitor::visit, &Visitor); @@ -2660,6 +2677,32 @@ void ASTReader::makeModuleVisible(Module *Mod, } } +bool ASTReader::loadGlobalIndex() { + if (GlobalIndex) + return false; + + if (TriedLoadingGlobalIndex || !UseGlobalIndex || + !Context.getLangOpts().Modules) + return true; + + // Try to load the global index. + TriedLoadingGlobalIndex = true; + StringRef ModuleCachePath + = getPreprocessor().getHeaderSearchInfo().getModuleCachePath(); + std::pair<GlobalModuleIndex *, GlobalModuleIndex::ErrorCode> Result + = GlobalModuleIndex::readIndex(FileMgr, ModuleCachePath); + if (!Result.first) + return true; + + GlobalIndex.reset(Result.first); + return false; +} + +bool ASTReader::isGlobalIndexUnavailable() const { + return Context.getLangOpts().Modules && UseGlobalIndex && + !hasGlobalIndex() && TriedLoadingGlobalIndex; +} + ASTReader::ASTReadResult ASTReader::ReadAST(const std::string &FileName, ModuleKind Type, SourceLocation ImportLoc, @@ -2678,6 +2721,10 @@ ASTReader::ASTReadResult ASTReader::ReadAST(const std::string &FileName, case ConfigurationMismatch: case HadErrors: ModuleMgr.removeModules(ModuleMgr.begin() + NumModules, ModuleMgr.end()); + + // If we find that any modules are unusable, the global index is going + // to be out-of-date. Just remove it. + GlobalIndex.reset(); return ReadResult; case Success: @@ -2779,7 +2826,7 @@ ASTReader::ASTReadResult ASTReader::ReadAST(const std::string &FileName, ObjCClassesLoaded[I], PreviousGeneration); } - + return Success; } @@ -5605,6 +5652,11 @@ void ASTReader::PrintStats() { (double)NumIdentifierLookupHits*100.0/NumIdentifierLookups); } + if (GlobalIndex) { + std::fprintf(stderr, "\n"); + GlobalIndex->printStats(); + } + std::fprintf(stderr, "\n"); dump(); std::fprintf(stderr, "\n"); @@ -5705,9 +5757,18 @@ void ASTReader::InitializeSema(Sema &S) { IdentifierInfo* ASTReader::get(const char *NameStart, const char *NameEnd) { // Note that we are loading an identifier. Deserializing AnIdentifier(this); - - IdentifierLookupVisitor Visitor(StringRef(NameStart, NameEnd - NameStart), - /*PriorGeneration=*/0, + StringRef Name(NameStart, NameEnd - NameStart); + + // If there is a global index, look there first to determine which modules + // provably do not have any results for this identifier. + GlobalModuleIndex::SkipSet SkipSet; + if (!loadGlobalIndex()) { + SmallVector<const FileEntry *, 4> ModuleFiles; + if (GlobalIndex->lookupIdentifier(Name, ModuleFiles)) { + SkipSet = GlobalIndex->computeSkipSet(ModuleFiles); + } + } + IdentifierLookupVisitor Visitor(Name, /*PriorGeneration=*/0, SkipSet, NumIdentifierLookups, NumIdentifierLookupHits); ModuleMgr.visit(IdentifierLookupVisitor::visit, &Visitor); diff --git a/clang/lib/Serialization/GlobalModuleIndex.cpp b/clang/lib/Serialization/GlobalModuleIndex.cpp index 1600e357dda..bdd33642eb4 100644 --- a/clang/lib/Serialization/GlobalModuleIndex.cpp +++ b/clang/lib/Serialization/GlobalModuleIndex.cpp @@ -42,7 +42,7 @@ namespace { enum IndexRecordTypes { /// \brief Contains version information and potentially other metadata, /// used to determine if we can read this global index file. - METADATA, + INDEX_METADATA, /// \brief Describes a module, including its file name and dependencies. MODULE, /// \brief The index for identifiers. @@ -57,6 +57,378 @@ static const char * const IndexFileName = "modules.idx"; static const unsigned CurrentVersion = 1; //----------------------------------------------------------------------------// +// Global module index reader. +//----------------------------------------------------------------------------// + +namespace { + +/// \brief Trait used to read the identifier index from the on-disk hash +/// table. +class IdentifierIndexReaderTrait { +public: + typedef StringRef external_key_type; + typedef StringRef internal_key_type; + typedef SmallVector<unsigned, 2> data_type; + + static bool EqualKey(const internal_key_type& a, const internal_key_type& b) { + return a == b; + } + + static unsigned ComputeHash(const internal_key_type& a) { + return llvm::HashString(a); + } + + static std::pair<unsigned, unsigned> + ReadKeyDataLength(const unsigned char*& d) { + using namespace clang::io; + unsigned KeyLen = ReadUnalignedLE16(d); + unsigned DataLen = ReadUnalignedLE16(d); + return std::make_pair(KeyLen, DataLen); + } + + static const internal_key_type& + GetInternalKey(const external_key_type& x) { return x; } + + static const external_key_type& + GetExternalKey(const internal_key_type& x) { return x; } + + static internal_key_type ReadKey(const unsigned char* d, unsigned n) { + return StringRef((const char *)d, n); + } + + static data_type ReadData(const internal_key_type& k, + const unsigned char* d, + unsigned DataLen) { + using namespace clang::io; + + data_type Result; + while (DataLen > 0) { + unsigned ID = ReadUnalignedLE32(d); + Result.push_back(ID); + DataLen -= 4; + } + + return Result; + } +}; + +typedef OnDiskChainedHashTable<IdentifierIndexReaderTrait> IdentifierIndexTable; + +/// \brief Module information as it was loaded from the index file. +struct LoadedModuleInfo { + const FileEntry *File; + SmallVector<unsigned, 2> Dependencies; + SmallVector<unsigned, 2> ImportedBy; +}; + +} + +GlobalModuleIndex::GlobalModuleIndex(FileManager &FileMgr, + llvm::MemoryBuffer *Buffer, + llvm::BitstreamCursor Cursor) + : Buffer(Buffer), IdentifierIndex() +{ + typedef llvm::DenseMap<unsigned, LoadedModuleInfo> LoadedModulesMap; + LoadedModulesMap LoadedModules; + + // Read the global index. + unsigned LargestID = 0; + bool InGlobalIndexBlock = false; + bool Done = false; + bool AnyOutOfDate = false; + while (!Done) { + llvm::BitstreamEntry Entry = Cursor.advance(); + + switch (Entry.Kind) { + case llvm::BitstreamEntry::Error: + return; + + case llvm::BitstreamEntry::EndBlock: + if (InGlobalIndexBlock) { + InGlobalIndexBlock = false; + Done = true; + continue; + } + return; + + + case llvm::BitstreamEntry::Record: + // Entries in the global index block are handled below. + if (InGlobalIndexBlock) + break; + + return; + + case llvm::BitstreamEntry::SubBlock: + if (!InGlobalIndexBlock && Entry.ID == GLOBAL_INDEX_BLOCK_ID) { + if (Cursor.EnterSubBlock(GLOBAL_INDEX_BLOCK_ID)) + return; + + InGlobalIndexBlock = true; + } else if (Cursor.SkipBlock()) { + return; + } + continue; + } + + SmallVector<uint64_t, 64> Record; + StringRef Blob; + switch ((IndexRecordTypes)Cursor.readRecord(Entry.ID, Record, &Blob)) { + case INDEX_METADATA: + // Make sure that the version matches. + if (Record.size() < 1 || Record[0] != CurrentVersion) + return; + break; + + case MODULE: { + unsigned Idx = 0; + unsigned ID = Record[Idx++]; + if (ID > LargestID) + LargestID = ID; + + off_t Size = Record[Idx++]; + time_t ModTime = Record[Idx++]; + + // File name. + unsigned NameLen = Record[Idx++]; + llvm::SmallString<64> FileName(Record.begin() + Idx, + Record.begin() + Idx + NameLen); + Idx += NameLen; + + // Dependencies + unsigned NumDeps = Record[Idx++]; + llvm::SmallVector<unsigned, 2> + Dependencies(Record.begin() + Idx, Record.begin() + Idx + NumDeps); + + // Find the file. If we can't find it, ignore it. + const FileEntry *File = FileMgr.getFile(FileName); + if (!File) { + AnyOutOfDate = true; + break; + } + + // If the module file is newer than the index, ignore it. + if (File->getSize() != Size || File->getModificationTime() != ModTime) { + AnyOutOfDate = true; + break; + } + + // Record this module. The dependencies will be resolved later. + LoadedModuleInfo &Info = LoadedModules[ID]; + Info.File = File; + Info.Dependencies.swap(Dependencies); + break; + } + + case IDENTIFIER_INDEX: + // Wire up the identifier index. + if (Record[0]) { + IdentifierIndex = IdentifierIndexTable::Create( + (const unsigned char *)Blob.data() + Record[0], + (const unsigned char *)Blob.data(), + IdentifierIndexReaderTrait()); + } + break; + } + } + + // If there are any modules that have gone out-of-date, prune out any modules + // that depend on them. + if (AnyOutOfDate) { + // First, build back links in the module dependency graph. + SmallVector<unsigned, 4> Stack; + for (LoadedModulesMap::iterator LM = LoadedModules.begin(), + LMEnd = LoadedModules.end(); + LM != LMEnd; ++LM) { + unsigned ID = LM->first; + + // If this module is out-of-date, push it onto the stack. + if (LM->second.File == 0) + Stack.push_back(ID); + + for (unsigned I = 0, N = LM->second.Dependencies.size(); I != N; ++I) { + unsigned DepID = LM->second.Dependencies[I]; + LoadedModulesMap::iterator Known = LoadedModules.find(DepID); + if (Known == LoadedModules.end() || !Known->second.File) { + // The dependency was out-of-date, so mark us as out of date. + // This is just an optimization. + if (LM->second.File) + Stack.push_back(ID); + + LM->second.File = 0; + continue; + } + + // Record this reverse dependency. + Known->second.ImportedBy.push_back(ID); + } + } + + // Second, walk the back links from out-of-date modules to those modules + // that depend on them, making those modules out-of-date as well. + while (!Stack.empty()) { + unsigned ID = Stack.back(); + Stack.pop_back(); + + LoadedModuleInfo &Info = LoadedModules[ID]; + for (unsigned I = 0, N = Info.ImportedBy.size(); I != N; ++I) { + unsigned FromID = Info.ImportedBy[I]; + if (LoadedModules[FromID].File) { + LoadedModules[FromID].File = 0; + Stack.push_back(FromID); + } + } + } + } + + // Allocate the vector containing information about all of the modules. + Modules.resize(LargestID + 1); + for (LoadedModulesMap::iterator LM = LoadedModules.begin(), + LMEnd = LoadedModules.end(); + LM != LMEnd; ++LM) { + if (!LM->second.File) + continue; + + Modules[LM->first].File = LM->second.File; + + // Resolve dependencies. Drop any we can't resolve due to out-of-date + // module files. + for (unsigned I = 0, N = LM->second.Dependencies.size(); I != N; ++I) { + unsigned DepID = LM->second.Dependencies[I]; + LoadedModulesMap::iterator Known = LoadedModules.find(DepID); + if (Known == LoadedModules.end() || !Known->second.File) + continue; + + Modules[LM->first].Dependencies.push_back(Known->second.File); + } + } +} + +GlobalModuleIndex::~GlobalModuleIndex() { } + +std::pair<GlobalModuleIndex *, GlobalModuleIndex::ErrorCode> +GlobalModuleIndex::readIndex(FileManager &FileMgr, StringRef Path) { + // Load the index file, if it's there. + llvm::SmallString<128> IndexPath; + IndexPath += Path; + llvm::sys::path::append(IndexPath, IndexFileName); + + llvm::OwningPtr<llvm::MemoryBuffer> Buffer( + FileMgr.getBufferForFile(IndexPath)); + if (!Buffer) + return std::make_pair((GlobalModuleIndex *)0, EC_NotFound); + + /// \brief The bitstream reader from which we'll read the AST file. + llvm::BitstreamReader Reader((const unsigned char *)Buffer->getBufferStart(), + (const unsigned char *)Buffer->getBufferEnd()); + + /// \brief The main bitstream cursor for the main block. + llvm::BitstreamCursor Cursor(Reader); + + // Sniff for the signature. + if (Cursor.Read(8) != 'B' || + Cursor.Read(8) != 'C' || + Cursor.Read(8) != 'G' || + Cursor.Read(8) != 'I') { + return std::make_pair((GlobalModuleIndex *)0, EC_IOError); + } + + return std::make_pair(new GlobalModuleIndex(FileMgr, Buffer.take(), Cursor), + EC_None); +} + +void GlobalModuleIndex::getKnownModules( + SmallVectorImpl<const FileEntry *> &ModuleFiles) { + ModuleFiles.clear(); + for (unsigned I = 0, N = Modules.size(); I != N; ++I) { + if (Modules[I].File) + ModuleFiles.push_back(Modules[I].File); + } +} + +void GlobalModuleIndex::getModuleDependencies( + const clang::FileEntry *ModuleFile, + SmallVectorImpl<const clang::FileEntry *> &Dependencies) { + // If the file -> index mapping is empty, populate it now. + if (ModulesByFile.empty()) { + for (unsigned I = 0, N = Modules.size(); I != N; ++I) { + if (Modules[I].File) + ModulesByFile[Modules[I].File] = I; + } + } + + // Look for information about this module file. + llvm::DenseMap<const FileEntry *, unsigned>::iterator Known + = ModulesByFile.find(ModuleFile); + if (Known == ModulesByFile.end()) + return; + + // Record dependencies. + Dependencies = Modules[Known->second].Dependencies; +} + +bool GlobalModuleIndex::lookupIdentifier( + StringRef Name, + SmallVectorImpl<const FileEntry *> &ModuleFiles) { + ModuleFiles.clear(); + + // If there's no identifier index, there is nothing we can do. + if (!IdentifierIndex) + return false; + + // Look into the identifier index. + ++NumIdentifierLookups; + IdentifierIndexTable &Table + = *static_cast<IdentifierIndexTable *>(IdentifierIndex); + IdentifierIndexTable::iterator Known = Table.find(Name); + if (Known == Table.end()) { + return true; + } + + SmallVector<unsigned, 2> ModuleIDs = *Known; + for (unsigned I = 0, N = ModuleIDs.size(); I != N; ++I) { + unsigned ID = ModuleIDs[I]; + if (ID >= Modules.size() || !Modules[ID].File) + continue; + + ModuleFiles.push_back(Modules[ID].File); + } + + ++NumIdentifierLookupHits; + return true; +} + +GlobalModuleIndex::SkipSet +GlobalModuleIndex::computeSkipSet( + const SmallVectorImpl<const FileEntry *> &ModuleFiles) { + llvm::SmallPtrSet<const FileEntry *, 8> Found(ModuleFiles.begin(), + ModuleFiles.end()); + + SkipSet Result; + for (unsigned I = 0, N = Modules.size(); I != N; ++I) { + if (Modules[I].File && !Found.count(Modules[I].File)) + Result.insert(Modules[I].File); + } + + NumIdentifierModulesSkipped += Result.size(); + return Result; +} + +void GlobalModuleIndex::printStats() { + std::fprintf(stderr, "*** Global Module Index Statistics:\n"); + if (NumIdentifierLookups) { + fprintf(stderr, " %u / %u identifier lookups succeeded (%f%%)\n", + NumIdentifierLookupHits, NumIdentifierLookups, + (double)NumIdentifierLookupHits*100.0/NumIdentifierLookups); + } + if (NumIdentifierLookups && NumIdentifierModulesSkipped) { + fprintf(stderr, " %f modules skipped per lookup (on average)\n", + (double)NumIdentifierModulesSkipped/NumIdentifierLookups); + } + std::fprintf(stderr, "\n"); +} + +//----------------------------------------------------------------------------// // Global module index writer. //----------------------------------------------------------------------------// @@ -151,7 +523,7 @@ GlobalModuleIndexBuilder::emitBlockInfoBlock(llvm::BitstreamWriter &Stream) { #define BLOCK(X) emitBlockID(X ## _ID, #X, Stream, Record) #define RECORD(X) emitRecordID(X, #X, Stream, Record) BLOCK(GLOBAL_INDEX_BLOCK); - RECORD(METADATA); + RECORD(INDEX_METADATA); RECORD(MODULE); RECORD(IDENTIFIER_INDEX); #undef RECORD @@ -160,7 +532,7 @@ GlobalModuleIndexBuilder::emitBlockInfoBlock(llvm::BitstreamWriter &Stream) { Stream.ExitBlock(); } -namespace clang { +namespace { class InterestingASTIdentifierLookupTrait : public serialization::reader::ASTIdentifierLookupTraitBase { @@ -209,18 +581,18 @@ bool GlobalModuleIndexBuilder::loadModuleFile(const FileEntry *File) { unsigned ID = getModuleFileInfo(File).ID; // Search for the blocks and records we care about. - enum { Outer, ControlBlock, ASTBlock } State = Outer; + enum { Other, ControlBlock, ASTBlock } State = Other; bool Done = false; while (!Done) { - const unsigned Flags = llvm::BitstreamCursor::AF_DontPopBlockAtEnd; - llvm::BitstreamEntry Entry = InStream.advance(Flags); + llvm::BitstreamEntry Entry = InStream.advance(); switch (Entry.Kind) { case llvm::BitstreamEntry::Error: - return true; + Done = true; + continue; case llvm::BitstreamEntry::Record: - // In the outer state, just skip the record. We don't care. - if (State == Outer) { + // In the 'other' state, just skip the record. We don't care. + if (State == Other) { InStream.skipRecord(Entry.ID); continue; } @@ -229,7 +601,7 @@ bool GlobalModuleIndexBuilder::loadModuleFile(const FileEntry *File) { break; case llvm::BitstreamEntry::SubBlock: - if (State == Outer && Entry.ID == CONTROL_BLOCK_ID) { + if (Entry.ID == CONTROL_BLOCK_ID) { if (InStream.EnterSubBlock(CONTROL_BLOCK_ID)) return true; @@ -238,14 +610,13 @@ bool GlobalModuleIndexBuilder::loadModuleFile(const FileEntry *File) { continue; } - if (State == Outer && Entry.ID == AST_BLOCK_ID) { + if (Entry.ID == AST_BLOCK_ID) { if (InStream.EnterSubBlock(AST_BLOCK_ID)) return true; // Found the AST block. State = ASTBlock; continue; - } if (InStream.SkipBlock()) @@ -254,10 +625,7 @@ bool GlobalModuleIndexBuilder::loadModuleFile(const FileEntry *File) { continue; case llvm::BitstreamEntry::EndBlock: - if (State == Outer) { - Done = true; - } - State = Outer; + State = Other; continue; } @@ -312,6 +680,8 @@ bool GlobalModuleIndexBuilder::loadModuleFile(const FileEntry *File) { std::pair<StringRef, bool> Ident = *D; if (Ident.second) InterestingIdentifiers[Ident.first].push_back(ID); + else + (void)InterestingIdentifiers[Ident.first]; } } @@ -378,7 +748,7 @@ void GlobalModuleIndexBuilder::writeIndex(llvm::BitstreamWriter &Stream) { // Write the metadata. SmallVector<uint64_t, 2> Record; Record.push_back(CurrentVersion); - Stream.EmitRecord(METADATA, Record); + Stream.EmitRecord(INDEX_METADATA, Record); // Write the set of known module files. for (ModuleFilesMap::iterator M = ModuleFiles.begin(), diff --git a/clang/lib/Serialization/ModuleManager.cpp b/clang/lib/Serialization/ModuleManager.cpp index 7cc1544259f..c600c053b5f 100644 --- a/clang/lib/Serialization/ModuleManager.cpp +++ b/clang/lib/Serialization/ModuleManager.cpp @@ -180,8 +180,7 @@ void ModuleManager::visit(bool (*Visitor)(ModuleFile &M, void *UserData), if (Visitor(*CurrentModule, UserData)) { // The visitor has requested that cut off visitation of any // module that the current module depends on. To indicate this - // behavior, we mark all of the reachable modules as having N - // incoming edges (which is impossible otherwise). + // behavior, we mark all of the reachable modules as "skipped". SmallVector<ModuleFile *, 4> Stack; Stack.push_back(CurrentModule); Skipped[CurrentModule->Index] = true; @@ -210,6 +209,8 @@ void ModuleManager::visit(bool (*Visitor)(ModuleFile &M, void *UserData), M = CurrentModule->Imports.begin(), MEnd = CurrentModule->Imports.end(); M != MEnd; ++M) { + if (Skipped[(*M)->Index]) + continue; // Remove our current module as an impediment to visiting the // module we depend on. If we were the last unvisited module |
