Use the AST on-disk hash table for name lookup inside a DeclContext.
*Huge* improvement over the amount of deserializing that we do for C++ lookup.
e.g, if he have the Carbon header precompiled and include it on a file containing this:
int x;
these are the before/after stats:
BEFORE:
*** AST File Statistics:
578 stat cache hits
4 stat cache misses
548/30654 source location entries read (1.787695%)
15907/16501 types read (96.400223%)
53525/59955 declarations read (89.275291%)
33993/43525 identifiers read (78.099945%)
41516/51891 statements read (80.006165%)
77/5317 macros read (1.448185%)
0/6335 lexical declcontexts read (0.000000%)
1/5424 visible declcontexts read (0.018437%)
AFTER using the on-disk table:
*** AST File Statistics:
578 stat cache hits
4 stat cache misses
548/30654 source location entries read (1.787695%)
10/16501 types read (0.060602%)
9/59955 declarations read (0.015011%)
161/43525 identifiers read (0.369902%)
20/51891 statements read (0.038542%)
6/5317 macros read (0.112846%)
0/6335 lexical declcontexts read (0.000000%)
2/5424 visible declcontexts read (0.036873%)
There's only one issue affecting mostly the precompiled preambles which I will address soon.
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@111636 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/AST/DeclBase.cpp b/lib/AST/DeclBase.cpp
index 74cc1c2..30d540a 100644
--- a/lib/AST/DeclBase.cpp
+++ b/lib/AST/DeclBase.cpp
@@ -648,19 +648,6 @@
DeclContext::lookup_result
ExternalASTSource::SetExternalVisibleDeclsForName(const DeclContext *DC,
- const VisibleDeclaration &VD) {
- ASTContext &Context = DC->getParentASTContext();
- StoredDeclsMap *Map;
- if (!(Map = DC->LookupPtr))
- Map = DC->CreateStoredDeclsMap(Context);
-
- StoredDeclsList &List = (*Map)[VD.Name];
- List.setFromDeclIDs(VD.Declarations);
- return List.getLookupResult(Context);
-}
-
-DeclContext::lookup_result
-ExternalASTSource::SetExternalVisibleDeclsForName(const DeclContext *DC,
DeclarationName Name,
llvm::SmallVectorImpl<NamedDecl*> &Decls) {
ASTContext &Context = DC->getParentASTContext();;
@@ -677,35 +664,7 @@
List.AddSubsequentDecl(Decls[I]);
}
- return List.getLookupResult(Context);
-}
-
-void ExternalASTSource::SetExternalVisibleDecls(const DeclContext *DC,
- const llvm::SmallVectorImpl<VisibleDeclaration> &Decls) {
- // There is no longer any visible storage in this context.
- DC->ExternalVisibleStorage = false;
-
- assert(!DC->LookupPtr && "Have a lookup map before de-serialization?");
- StoredDeclsMap *Map = DC->CreateStoredDeclsMap(DC->getParentASTContext());
- for (unsigned I = 0, N = Decls.size(); I != N; ++I) {
- (*Map)[Decls[I].Name].setFromDeclIDs(Decls[I].Declarations);
- }
-}
-
-void ExternalASTSource::SetExternalVisibleDecls(const DeclContext *DC,
- const llvm::SmallVectorImpl<NamedDecl*> &Decls) {
- // There is no longer any visible storage in this context.
- DC->ExternalVisibleStorage = false;
-
- assert(!DC->LookupPtr && "Have a lookup map before de-serialization?");
- StoredDeclsMap &Map = *DC->CreateStoredDeclsMap(DC->getParentASTContext());
- for (unsigned I = 0, N = Decls.size(); I != N; ++I) {
- StoredDeclsList &List = Map[Decls[I]->getDeclName()];
- if (List.isNull())
- List.setOnlyValue(Decls[I]);
- else
- List.AddSubsequentDecl(Decls[I]);
- }
+ return List.getLookupResult();
}
DeclContext::decl_iterator DeclContext::noload_decls_begin() const {
@@ -841,7 +800,7 @@
if (LookupPtr) {
StoredDeclsMap::iterator I = LookupPtr->find(Name);
if (I != LookupPtr->end())
- return I->second.getLookupResult(getParentASTContext());
+ return I->second.getLookupResult();
}
ExternalASTSource *Source = getParentASTContext().getExternalSource();
@@ -861,7 +820,7 @@
StoredDeclsMap::iterator Pos = LookupPtr->find(Name);
if (Pos == LookupPtr->end())
return lookup_result(lookup_iterator(0), lookup_iterator(0));
- return Pos->second.getLookupResult(getParentASTContext());
+ return Pos->second.getLookupResult();
}
DeclContext::lookup_const_result
@@ -925,18 +884,21 @@
if (isa<ClassTemplateSpecializationDecl>(D))
return;
- // If there is an external AST source, load any declarations it knows about
- // with this declaration's name.
- if (ExternalASTSource *Source = getParentASTContext().getExternalSource())
- if (hasExternalVisibleStorage())
- Source->FindExternalVisibleDeclsByName(this, D->getDeclName());
-
ASTContext *C = 0;
if (!LookupPtr) {
C = &getParentASTContext();
CreateStoredDeclsMap(*C);
}
+ // If there is an external AST source, load any declarations it knows about
+ // with this declaration's name.
+ // If the lookup table contains an entry about this name it means that we
+ // have already checked the external source.
+ if (ExternalASTSource *Source = getParentASTContext().getExternalSource())
+ if (hasExternalVisibleStorage() &&
+ LookupPtr->find(D->getDeclName()) == LookupPtr->end())
+ Source->FindExternalVisibleDeclsByName(this, D->getDeclName());
+
// Insert this declaration into the map.
StoredDeclsList &DeclNameEntries = (*LookupPtr)[D->getDeclName()];
if (DeclNameEntries.isNull()) {
@@ -947,10 +909,7 @@
// If it is possible that this is a redeclaration, check to see if there is
// already a decl for which declarationReplaces returns true. If there is
// one, just replace it and return.
- if (!C)
- C = &getParentASTContext();
-
- if (DeclNameEntries.HandleRedeclaration(*C, D))
+ if (DeclNameEntries.HandleRedeclaration(D))
return;
// Put this declaration into the appropriate slot.
@@ -966,43 +925,6 @@
reinterpret_cast<udir_iterator>(Result.second));
}
-void StoredDeclsList::materializeDecls(ASTContext &Context) {
- if (isNull())
- return;
-
- switch ((DataKind)(Data & 0x03)) {
- case DK_Decl:
- case DK_Decl_Vector:
- break;
-
- case DK_DeclID: {
- // Resolve this declaration ID to an actual declaration by
- // querying the external AST source.
- unsigned DeclID = Data >> 2;
-
- ExternalASTSource *Source = Context.getExternalSource();
- assert(Source && "No external AST source available!");
-
- Data = reinterpret_cast<uintptr_t>(Source->GetExternalDecl(DeclID));
- break;
- }
-
- case DK_ID_Vector: {
- // We have a vector of declaration IDs. Resolve all of them to
- // actual declarations.
- VectorTy &Vector = *getAsVector();
- ExternalASTSource *Source = Context.getExternalSource();
- assert(Source && "No external AST source available!");
-
- for (unsigned I = 0, N = Vector.size(); I != N; ++I)
- Vector[I] = reinterpret_cast<uintptr_t>(Source->GetExternalDecl(Vector[I]));
-
- Data = (Data & ~0x03) | DK_Decl_Vector;
- break;
- }
- }
-}
-
//===----------------------------------------------------------------------===//
// Creation and Destruction of StoredDeclsMaps. //
//===----------------------------------------------------------------------===//
diff --git a/lib/Serialization/ASTReader.cpp b/lib/Serialization/ASTReader.cpp
index 05fa7cd..b24b353 100644
--- a/lib/Serialization/ASTReader.cpp
+++ b/lib/Serialization/ASTReader.cpp
@@ -846,6 +846,54 @@
typedef OnDiskChainedHashTable<ASTDeclContextNameLookupTrait>
ASTDeclContextNameLookupTable;
+bool ASTReader::ReadDeclContextStorage(llvm::BitstreamCursor &Cursor,
+ const std::pair<uint64_t, uint64_t> &Offsets,
+ DeclContextInfo &Info) {
+ SavedStreamPosition SavedPosition(Cursor);
+ // First the lexical decls.
+ if (Offsets.first != 0) {
+ Cursor.JumpToBit(Offsets.first);
+
+ RecordData Record;
+ const char *Blob;
+ unsigned BlobLen;
+ unsigned Code = Cursor.ReadCode();
+ unsigned RecCode = Cursor.ReadRecord(Code, Record, &Blob, &BlobLen);
+ if (RecCode != DECL_CONTEXT_LEXICAL) {
+ Error("Expected lexical block");
+ return true;
+ }
+
+ Info.LexicalDecls = reinterpret_cast<const DeclID*>(Blob);
+ Info.NumLexicalDecls = BlobLen / sizeof(DeclID);
+ } else {
+ Info.LexicalDecls = 0;
+ Info.NumLexicalDecls = 0;
+ }
+
+ // Now the lookup table.
+ if (Offsets.second != 0) {
+ Cursor.JumpToBit(Offsets.second);
+
+ RecordData Record;
+ const char *Blob;
+ unsigned BlobLen;
+ unsigned Code = Cursor.ReadCode();
+ unsigned RecCode = Cursor.ReadRecord(Code, Record, &Blob, &BlobLen);
+ if (RecCode != DECL_CONTEXT_VISIBLE) {
+ Error("Expected visible lookup table block");
+ return true;
+ }
+ Info.NameLookupTableData
+ = ASTDeclContextNameLookupTable::Create(
+ (const unsigned char *)Blob + Record[0],
+ (const unsigned char *)Blob,
+ ASTDeclContextNameLookupTrait(*this));
+ }
+
+ return false;
+}
+
void ASTReader::Error(const char *Msg) {
Diag(diag::err_fe_pch_malformed) << Msg;
}
@@ -1674,7 +1722,7 @@
case TU_UPDATE_LEXICAL: {
DeclContextInfo Info = {
- /* No visible information */ 0, 0,
+ /* No visible information */ 0,
reinterpret_cast<const DeclID *>(BlobStart),
BlobLen / sizeof(DeclID)
};
@@ -3119,54 +3167,33 @@
DeclarationName Name) {
assert(DC->hasExternalVisibleStorage() &&
"DeclContext has no visible decls in storage");
+ if (!Name)
+ return DeclContext::lookup_result(DeclContext::lookup_iterator(0),
+ DeclContext::lookup_iterator(0));
- llvm::SmallVector<VisibleDeclaration, 64> Decls;
+ llvm::SmallVector<NamedDecl *, 64> Decls;
// There might be lexical decls in multiple parts of the chain, for the TU
// and namespaces.
DeclContextInfos &Infos = DeclContextOffsets[DC];
for (DeclContextInfos::iterator I = Infos.begin(), E = Infos.end();
I != E; ++I) {
- uint64_t Offset = I->OffsetToVisibleDecls;
- if (Offset == 0)
+ if (!I->NameLookupTableData)
continue;
- llvm::BitstreamCursor &DeclsCursor = *I->Stream;
-
- // Keep track of where we are in the stream, then jump back there
- // after reading this context.
- SavedStreamPosition SavedPosition(DeclsCursor);
-
- // Load the record containing all of the declarations visible in
- // this context.
- DeclsCursor.JumpToBit(Offset);
- RecordData Record;
- unsigned Code = DeclsCursor.ReadCode();
- unsigned RecCode = DeclsCursor.ReadRecord(Code, Record);
- if (RecCode != DECL_CONTEXT_VISIBLE) {
- Error("Expected visible block");
- return DeclContext::lookup_result(DeclContext::lookup_iterator(),
- DeclContext::lookup_iterator());
- }
-
- if (Record.empty())
+ ASTDeclContextNameLookupTable *LookupTable =
+ (ASTDeclContextNameLookupTable*)I->NameLookupTableData;
+ ASTDeclContextNameLookupTable::iterator Pos = LookupTable->find(Name);
+ if (Pos == LookupTable->end())
continue;
- unsigned Idx = 0;
- while (Idx < Record.size()) {
- Decls.push_back(VisibleDeclaration());
- Decls.back().Name = ReadDeclarationName(Record, Idx);
-
- unsigned Size = Record[Idx++];
- llvm::SmallVector<unsigned, 4> &LoadedDecls = Decls.back().Declarations;
- LoadedDecls.reserve(Size);
- for (unsigned J = 0; J < Size; ++J)
- LoadedDecls.push_back(Record[Idx++]);
- }
+ ASTDeclContextNameLookupTrait::data_type Data = *Pos;
+ for (; Data.first != Data.second; ++Data.first)
+ Decls.push_back(cast<NamedDecl>(GetDecl(*Data.first)));
}
++NumVisibleDeclContextsRead;
- SetExternalVisibleDecls(DC, Decls);
+ SetExternalVisibleDeclsForName(DC, Name, Decls);
return const_cast<DeclContext*>(DC)->lookup(Name);
}
diff --git a/lib/Serialization/ASTReaderDecl.cpp b/lib/Serialization/ASTReaderDecl.cpp
index 9094281..bc68e91 100644
--- a/lib/Serialization/ASTReaderDecl.cpp
+++ b/lib/Serialization/ASTReaderDecl.cpp
@@ -1413,35 +1413,3 @@
return D;
}
-
-bool ASTReader::ReadDeclContextStorage(llvm::BitstreamCursor &Cursor,
- const std::pair<uint64_t, uint64_t> &Offsets,
- DeclContextInfo &Info) {
- SavedStreamPosition SavedPosition(Cursor);
- // First the lexical decls.
- if (Offsets.first != 0) {
- Cursor.JumpToBit(Offsets.first);
-
- RecordData Record;
- const char *Blob;
- unsigned BlobLen;
- unsigned Code = Cursor.ReadCode();
- unsigned RecCode = Cursor.ReadRecord(Code, Record, &Blob, &BlobLen);
- if (RecCode != DECL_CONTEXT_LEXICAL) {
- Error("Expected lexical block");
- return true;
- }
-
- Info.LexicalDecls = reinterpret_cast<const DeclID*>(Blob);
- Info.NumLexicalDecls = BlobLen / sizeof(DeclID);
- } else {
- Info.LexicalDecls = 0;
- Info.NumLexicalDecls = 0;
- }
-
- // Now the visible decls.
- Info.Stream = &Cursor;
- Info.OffsetToVisibleDecls = Offsets.second;
-
- return false;
-}
diff --git a/lib/Serialization/ASTWriter.cpp b/lib/Serialization/ASTWriter.cpp
index 94be24a..5deaf3d 100644
--- a/lib/Serialization/ASTWriter.cpp
+++ b/lib/Serialization/ASTWriter.cpp
@@ -1466,59 +1466,6 @@
return Offset;
}
-/// \brief Write the block containing all of the declaration IDs
-/// visible from the given DeclContext.
-///
-/// \returns the offset of the DECL_CONTEXT_VISIBLE block within the
-/// bistream, or 0 if no block was written.
-uint64_t ASTWriter::WriteDeclContextVisibleBlock(ASTContext &Context,
- DeclContext *DC) {
- if (DC->getPrimaryContext() != DC)
- return 0;
-
- // Since there is no name lookup into functions or methods, don't bother to
- // build a visible-declarations table for these entities.
- if (DC->isFunctionOrMethod())
- return 0;
-
- // If not in C++, we perform name lookup for the translation unit via the
- // IdentifierInfo chains, don't bother to build a visible-declarations table.
- // FIXME: In C++ we need the visible declarations in order to "see" the
- // friend declarations, is there a way to do this without writing the table ?
- if (DC->isTranslationUnit() && !Context.getLangOptions().CPlusPlus)
- return 0;
-
- // Force the DeclContext to build a its name-lookup table.
- DC->lookup(DeclarationName());
-
- // Serialize the contents of the mapping used for lookup. Note that,
- // although we have two very different code paths, the serialized
- // representation is the same for both cases: a declaration name,
- // followed by a size, followed by references to the visible
- // declarations that have that name.
- uint64_t Offset = Stream.GetCurrentBitNo();
- RecordData Record;
- StoredDeclsMap *Map = static_cast<StoredDeclsMap*>(DC->getLookupPtr());
- if (!Map)
- return 0;
-
- for (StoredDeclsMap::iterator D = Map->begin(), DEnd = Map->end();
- D != DEnd; ++D) {
- AddDeclarationName(D->first, Record);
- DeclContext::lookup_result Result = D->second.getLookupResult(Context);
- Record.push_back(Result.second - Result.first);
- for (; Result.first != Result.second; ++Result.first)
- AddDeclRef(*Result.first, Record);
- }
-
- if (Record.size() == 0)
- return 0;
-
- Stream.EmitRecord(DECL_CONTEXT_VISIBLE, Record);
- ++NumVisibleDeclContexts;
- return Offset;
-}
-
void ASTWriter::WriteTypeDeclOffsets() {
using namespace llvm;
RecordData Record;
@@ -2062,6 +2009,74 @@
};
} // end anonymous namespace
+/// \brief Write the block containing all of the declaration IDs
+/// visible from the given DeclContext.
+///
+/// \returns the offset of the DECL_CONTEXT_VISIBLE block within the
+/// bistream, or 0 if no block was written.
+uint64_t ASTWriter::WriteDeclContextVisibleBlock(ASTContext &Context,
+ DeclContext *DC) {
+ if (DC->getPrimaryContext() != DC)
+ return 0;
+
+ // Since there is no name lookup into functions or methods, don't bother to
+ // build a visible-declarations table for these entities.
+ if (DC->isFunctionOrMethod())
+ return 0;
+
+ // If not in C++, we perform name lookup for the translation unit via the
+ // IdentifierInfo chains, don't bother to build a visible-declarations table.
+ // FIXME: In C++ we need the visible declarations in order to "see" the
+ // friend declarations, is there a way to do this without writing the table ?
+ if (DC->isTranslationUnit() && !Context.getLangOptions().CPlusPlus)
+ return 0;
+
+ // Force the DeclContext to build a its name-lookup table.
+ DC->lookup(DeclarationName());
+
+ // Serialize the contents of the mapping used for lookup. Note that,
+ // although we have two very different code paths, the serialized
+ // representation is the same for both cases: a declaration name,
+ // followed by a size, followed by references to the visible
+ // declarations that have that name.
+ uint64_t Offset = Stream.GetCurrentBitNo();
+ StoredDeclsMap *Map = static_cast<StoredDeclsMap*>(DC->getLookupPtr());
+ if (!Map || Map->empty())
+ return 0;
+
+ OnDiskChainedHashTableGenerator<ASTDeclContextNameLookupTrait> Generator;
+ ASTDeclContextNameLookupTrait Trait(*this);
+
+ // Create the on-disk hash table representation.
+ for (StoredDeclsMap::iterator D = Map->begin(), DEnd = Map->end();
+ D != DEnd; ++D) {
+ DeclarationName Name = D->first;
+ DeclContext::lookup_result Result = D->second.getLookupResult();
+ Generator.insert(Name, Result, Trait);
+ }
+
+ // Create the on-disk hash table in a buffer.
+ llvm::SmallString<4096> LookupTable;
+ uint32_t BucketOffset;
+ {
+ llvm::raw_svector_ostream Out(LookupTable);
+ // Make sure that no bucket is at offset 0
+ clang::io::Emit32(Out, 0);
+ BucketOffset = Generator.Emit(Out, Trait);
+ }
+
+ // Write the lookup table
+ RecordData Record;
+ Record.push_back(DECL_CONTEXT_VISIBLE);
+ Record.push_back(BucketOffset);
+ Stream.EmitRecordWithBlob(DeclContextVisibleLookupAbbrev, Record,
+ LookupTable.str());
+
+ Stream.EmitRecord(DECL_CONTEXT_VISIBLE, Record);
+ ++NumVisibleDeclContexts;
+ return Offset;
+}
+
//===----------------------------------------------------------------------===//
// General Serialization Routines
//===----------------------------------------------------------------------===//
diff --git a/lib/Serialization/ASTWriterDecl.cpp b/lib/Serialization/ASTWriterDecl.cpp
index 016f4d3..a5d2ce2 100644
--- a/lib/Serialization/ASTWriterDecl.cpp
+++ b/lib/Serialization/ASTWriterDecl.cpp
@@ -1086,6 +1086,12 @@
Abv->Add(BitCodeAbbrevOp(serialization::DECL_CONTEXT_LEXICAL));
Abv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Blob));
DeclContextLexicalAbbrev = Stream.EmitAbbrev(Abv);
+
+ Abv = new BitCodeAbbrev();
+ Abv->Add(BitCodeAbbrevOp(serialization::DECL_CONTEXT_VISIBLE));
+ Abv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 32));
+ Abv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Blob));
+ DeclContextVisibleLookupAbbrev = Stream.EmitAbbrev(Abv);
}
/// isRequiredDecl - Check if this is a "required" Decl, which must be seen by