Improve coordination between the module manager and the global module
index, optimizing the operation that skips lookup in modules where we
know the identifier will not be found. This makes the global module
index optimization actually useful, providing an 8.5% speedup over
modules without the global module index for -fsyntax-only.
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@173529 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Serialization/ASTReader.cpp b/lib/Serialization/ASTReader.cpp
index d8d5e66..fd1b896 100644
--- a/lib/Serialization/ASTReader.cpp
+++ b/lib/Serialization/ASTReader.cpp
@@ -1378,17 +1378,15 @@
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), SkipSet(SkipSet),
+ : Name(Name), PriorGeneration(PriorGeneration),
NumIdentifierLookups(NumIdentifierLookups),
NumIdentifierLookupHits(NumIdentifierLookupHits),
Found()
@@ -1403,10 +1401,6 @@
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)
@@ -1443,18 +1437,18 @@
// 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;
+ GlobalModuleIndex::HitSet Hits;
+ GlobalModuleIndex::HitSet *HitsPtr = 0;
if (!loadGlobalIndex()) {
- SmallVector<const FileEntry *, 4> ModuleFiles;
- if (GlobalIndex->lookupIdentifier(II.getName(), ModuleFiles)) {
- SkipSet = GlobalIndex->computeSkipSet(ModuleFiles);
+ if (GlobalIndex->lookupIdentifier(II.getName(), Hits)) {
+ HitsPtr = &Hits;
}
}
- IdentifierLookupVisitor Visitor(II.getName(), PriorGeneration, SkipSet,
+ IdentifierLookupVisitor Visitor(II.getName(), PriorGeneration,
NumIdentifierLookups,
NumIdentifierLookupHits);
- ModuleMgr.visit(IdentifierLookupVisitor::visit, &Visitor);
+ ModuleMgr.visit(IdentifierLookupVisitor::visit, &Visitor, HitsPtr);
markIdentifierUpToDate(&II);
}
@@ -2695,6 +2689,7 @@
return true;
GlobalIndex.reset(Result.first);
+ ModuleMgr.setGlobalIndex(GlobalIndex.get());
return false;
}
@@ -2725,6 +2720,7 @@
// If we find that any modules are unusable, the global index is going
// to be out-of-date. Just remove it.
GlobalIndex.reset();
+ ModuleMgr.setGlobalIndex(0);
return ReadResult;
case Success:
@@ -5760,17 +5756,17 @@
// 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;
+ GlobalModuleIndex::HitSet Hits;
+ GlobalModuleIndex::HitSet *HitsPtr = 0;
if (!loadGlobalIndex()) {
- SmallVector<const FileEntry *, 4> ModuleFiles;
- if (GlobalIndex->lookupIdentifier(Name, ModuleFiles)) {
- SkipSet = GlobalIndex->computeSkipSet(ModuleFiles);
+ if (GlobalIndex->lookupIdentifier(Name, Hits)) {
+ HitsPtr = &Hits;
}
}
- IdentifierLookupVisitor Visitor(Name, /*PriorGeneration=*/0, SkipSet,
+ IdentifierLookupVisitor Visitor(Name, /*PriorGeneration=*/0,
NumIdentifierLookups,
NumIdentifierLookupHits);
- ModuleMgr.visit(IdentifierLookupVisitor::visit, &Visitor);
+ ModuleMgr.visit(IdentifierLookupVisitor::visit, &Visitor, HitsPtr);
IdentifierInfo *II = Visitor.getIdentifierInfo();
markIdentifierUpToDate(II);
return II;
diff --git a/lib/Serialization/GlobalModuleIndex.cpp b/lib/Serialization/GlobalModuleIndex.cpp
index b192398..b778a72 100644
--- a/lib/Serialization/GlobalModuleIndex.cpp
+++ b/lib/Serialization/GlobalModuleIndex.cpp
@@ -127,7 +127,8 @@
GlobalModuleIndex::GlobalModuleIndex(FileManager &FileMgr,
llvm::MemoryBuffer *Buffer,
llvm::BitstreamCursor Cursor)
- : Buffer(Buffer), IdentifierIndex()
+ : Buffer(Buffer), IdentifierIndex(),
+ NumIdentifierLookups(), NumIdentifierLookupHits()
{
typedef llvm::DenseMap<unsigned, LoadedModuleInfo> LoadedModulesMap;
LoadedModulesMap LoadedModules;
@@ -368,10 +369,8 @@
Dependencies = Modules[Known->second].Dependencies;
}
-bool GlobalModuleIndex::lookupIdentifier(
- StringRef Name,
- SmallVectorImpl<const FileEntry *> &ModuleFiles) {
- ModuleFiles.clear();
+bool GlobalModuleIndex::lookupIdentifier(StringRef Name, HitSet &Hits) {
+ Hits.clear();
// If there's no identifier index, there is nothing we can do.
if (!IdentifierIndex)
@@ -392,29 +391,13 @@
if (ID >= Modules.size() || !Modules[ID].File)
continue;
- ModuleFiles.push_back(Modules[ID].File);
+ Hits.insert(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) {
@@ -422,10 +405,6 @@
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");
}
diff --git a/lib/Serialization/ModuleManager.cpp b/lib/Serialization/ModuleManager.cpp
index f3fe2b9..97c86a7 100644
--- a/lib/Serialization/ModuleManager.cpp
+++ b/lib/Serialization/ModuleManager.cpp
@@ -12,6 +12,7 @@
//
//===----------------------------------------------------------------------===//
#include "clang/Serialization/ModuleManager.h"
+#include "clang/Serialization/GlobalModuleIndex.h"
#include "llvm/Support/MemoryBuffer.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Support/system_error.h"
@@ -140,17 +141,45 @@
InMemoryBuffers[Entry] = Buffer;
}
-ModuleManager::ModuleManager(FileManager &FileMgr) : FileMgr(FileMgr) { }
+void ModuleManager::updateModulesInCommonWithGlobalIndex() {
+ ModulesInCommonWithGlobalIndex.clear();
+
+ if (!GlobalIndex)
+ return;
+
+ // Collect the set of modules known to the global index.
+ SmallVector<const FileEntry *, 16> KnownModules;
+ GlobalIndex->getKnownModules(KnownModules);
+
+ // Map those modules to AST files known to the module manager.
+ for (unsigned I = 0, N = KnownModules.size(); I != N; ++I) {
+ llvm::DenseMap<const FileEntry *, ModuleFile *>::iterator Known
+ = Modules.find(KnownModules[I]);
+ if (Known == Modules.end())
+ continue;
+
+ ModulesInCommonWithGlobalIndex.push_back(Known->second);
+ }
+}
+
+void ModuleManager::setGlobalIndex(GlobalModuleIndex *Index) {
+ GlobalIndex = Index;
+ updateModulesInCommonWithGlobalIndex();
+}
+
+ModuleManager::ModuleManager(FileManager &FileMgr)
+ : FileMgr(FileMgr), GlobalIndex() { }
ModuleManager::~ModuleManager() {
for (unsigned i = 0, e = Chain.size(); i != e; ++i)
delete Chain[e - i - 1];
}
-void ModuleManager::visit(bool (*Visitor)(ModuleFile &M, void *UserData),
- void *UserData) {
- // If the visitation number array is the wrong size, resize it and recompute
- // an order.
+void
+ModuleManager::visit(bool (*Visitor)(ModuleFile &M, void *UserData),
+ void *UserData,
+ llvm::SmallPtrSet<const FileEntry *, 4> *ModuleFilesHit) {
+ // If the visitation order vector is the wrong size, recompute the order.
if (VisitOrder.size() != Chain.size()) {
unsigned N = size();
VisitOrder.clear();
@@ -196,11 +225,28 @@
}
assert(VisitOrder.size() == N && "Visitation order is wrong?");
+
+ // We may need to update the set of modules we have in common with the
+ // global module index, since modules could have been added to the module
+ // manager since we loaded the global module index.
+ updateModulesInCommonWithGlobalIndex();
}
SmallVector<ModuleFile *, 4> Stack;
SmallVector<bool, 4> Visited(size(), false);
+ // If the caller has provided us with a hit-set that came from the global
+ // module index, mark every module file in common with the global module
+ // index that is *not* in that set as 'visited'.
+ if (ModuleFilesHit && !ModulesInCommonWithGlobalIndex.empty()) {
+ for (unsigned I = 0, N = ModulesInCommonWithGlobalIndex.size(); I != N; ++I)
+ {
+ ModuleFile *M = ModulesInCommonWithGlobalIndex[I];
+ if (!ModuleFilesHit->count(M->File))
+ Visited[M->Index] = true;
+ }
+ }
+
for (unsigned I = 0, N = VisitOrder.size(); I != N; ++I) {
ModuleFile *CurrentModule = VisitOrder[I];
// Should we skip this module file?