Completely re-implement (de-)serialization of redeclaration
chains, again. The prior implementation was very linked-list oriented, and
the list-splicing logic was both fairly convoluted (when loading from
multiple modules) and failed to preserve a reasonable ordering for the
redeclaration chains.
This new implementation uses a simpler strategy, where we store the
ordered redeclaration chains in an array-like structure (indexed based
on the first declaration), and use that ordering to add individual
deserialized declarations to the end of the existing chain. That way,
the chain mimics the ordering from its modules, and a bug somewhere is
far less likely to result in a broken linked list.
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@148222 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Serialization/ASTReader.cpp b/lib/Serialization/ASTReader.cpp
index 2417845..7fc5a1d 100644
--- a/lib/Serialization/ASTReader.cpp
+++ b/lib/Serialization/ASTReader.cpp
@@ -2396,15 +2396,20 @@
}
break;
}
-
+
case LOCAL_REDECLARATIONS: {
- if (F.LocalNumRedeclarationsInfos != 0) {
- Error("duplicate LOCAL_REDECLARATIONS record in AST file");
+ F.RedeclarationChains.swap(Record);
+ break;
+ }
+
+ case LOCAL_REDECLARATIONS_MAP: {
+ if (F.LocalNumRedeclarationsInMap != 0) {
+ Error("duplicate LOCAL_REDECLARATIONS_MAP record in AST file");
return Failure;
}
- F.LocalNumRedeclarationsInfos = Record[0];
- F.RedeclarationsInfo = (const LocalRedeclarationsInfo *)BlobStart;
+ F.LocalNumRedeclarationsInMap = Record[0];
+ F.RedeclarationsMap = (const LocalRedeclarationsInfo *)BlobStart;
break;
}
@@ -6118,7 +6123,6 @@
void ASTReader::finishPendingActions() {
while (!PendingIdentifierInfos.empty() ||
- !PendingPreviousDecls.empty() ||
!PendingDeclChains.empty() ||
!PendingChainedObjCCategories.empty()) {
@@ -6130,13 +6134,6 @@
PendingIdentifierInfos.pop_front();
}
- // Ready to load previous declarations of Decls that were delayed.
- while (!PendingPreviousDecls.empty()) {
- loadAndAttachPreviousDecl(PendingPreviousDecls.front().first,
- PendingPreviousDecls.front().second);
- PendingPreviousDecls.pop_front();
- }
-
// Load pending declaration chains.
for (unsigned I = 0; I != PendingDeclChains.size(); ++I) {
loadPendingDeclChain(PendingDeclChains[I]);
diff --git a/lib/Serialization/ASTReaderDecl.cpp b/lib/Serialization/ASTReaderDecl.cpp
index d701d60..6788d9e 100644
--- a/lib/Serialization/ASTReaderDecl.cpp
+++ b/lib/Serialization/ASTReaderDecl.cpp
@@ -1463,41 +1463,26 @@
template <typename T>
ASTDeclReader::RedeclarableResult
ASTDeclReader::VisitRedeclarable(Redeclarable<T> *D) {
- enum RedeclKind { FirstDeclaration = 0, FirstInFile, PointsToPrevious };
- RedeclKind Kind = (RedeclKind)Record[Idx++];
+ DeclID FirstDeclID = ReadDeclID(Record, Idx);
- DeclID FirstDeclID = 0;
- switch (Kind) {
- case FirstDeclaration:
+ // 0 indicates that this declaration was the only declaration of its entity,
+ // and is used for space optimization.
+ if (FirstDeclID == 0)
FirstDeclID = ThisDeclID;
- break;
-
- case FirstInFile:
- case PointsToPrevious: {
- FirstDeclID = ReadDeclID(Record, Idx);
- DeclID PrevDeclID = ReadDeclID(Record, Idx);
-
- T *FirstDecl = cast_or_null<T>(Reader.GetDecl(FirstDeclID));
-
+
+ T *FirstDecl = cast_or_null<T>(Reader.GetDecl(FirstDeclID));
+ if (FirstDecl != D) {
// We delay loading of the redeclaration chain to avoid deeply nested calls.
// We temporarily set the first (canonical) declaration as the previous one
// which is the one that matters and mark the real previous DeclID to be
// loaded & attached later on.
D->RedeclLink = typename Redeclarable<T>::PreviousDeclLink(FirstDecl);
-
- if (Kind == PointsToPrevious) {
- // Make a note that we need to wire up this declaration to its
- // previous declaration, later. We don't need to do this for the first
- // declaration in any given module file, because those will be wired
- // together later.
- Reader.PendingPreviousDecls.push_back(std::make_pair(static_cast<T*>(D),
- PrevDeclID));
- }
- break;
- }
- }
-
- // The result structure takes care of note that we need to load the
+ }
+
+ // Note that this declaration has been deserialized.
+ Reader.RedeclsDeserialized.insert(static_cast<T *>(D));
+
+ // The result structure takes care to note that we need to load the
// other declaration chains for this ID.
return RedeclarableResult(Reader, FirstDeclID);
}
@@ -1529,6 +1514,8 @@
static_cast<NamespaceDecl *>(static_cast<void*>(ExistingCanon)));
}
+ // FIXME: Update common pointer for RedeclarableTemplateDecls?
+
// Don't introduce DCanon into the set of pending declaration chains.
Redecl.suppress();
@@ -1551,7 +1538,7 @@
Merged.push_back(Redecl.getFirstID());
// If ExistingCanon did not come from a module file, introduce the
- // first declaration that *does* come from a module file is in the
+ // first declaration that *does* come from a module file to the
// set of pending declaration chains, so that we merge this
// declaration.
if (!ExistingCanon->isFromASTFile() &&
@@ -2140,13 +2127,16 @@
class RedeclChainVisitor {
ASTReader &Reader;
SmallVectorImpl<DeclID> &SearchDecls;
+ llvm::SmallPtrSet<Decl *, 16> &Deserialized;
GlobalDeclID CanonID;
- llvm::SmallVector<std::pair<Decl *, Decl *>, 4> Chains;
+ llvm::SmallVector<Decl *, 4> Chain;
public:
RedeclChainVisitor(ASTReader &Reader, SmallVectorImpl<DeclID> &SearchDecls,
+ llvm::SmallPtrSet<Decl *, 16> &Deserialized,
GlobalDeclID CanonID)
- : Reader(Reader), SearchDecls(SearchDecls), CanonID(CanonID) { }
+ : Reader(Reader), SearchDecls(SearchDecls), Deserialized(Deserialized),
+ CanonID(CanonID) { }
static bool visit(ModuleFile &M, bool Preorder, void *UserData) {
if (Preorder)
@@ -2155,6 +2145,16 @@
return static_cast<RedeclChainVisitor *>(UserData)->visit(M);
}
+ void addToChain(Decl *D) {
+ if (!D)
+ return;
+
+ if (Deserialized.count(D)) {
+ Deserialized.erase(D);
+ Chain.push_back(D);
+ }
+ }
+
void searchForID(ModuleFile &M, GlobalDeclID GlobalID) {
// Map global ID of the first declaration down to the local ID
// used in this module file.
@@ -2165,10 +2165,10 @@
// Perform a binary search to find the local redeclarations for this
// declaration (if any).
const LocalRedeclarationsInfo *Result
- = std::lower_bound(M.RedeclarationsInfo,
- M.RedeclarationsInfo + M.LocalNumRedeclarationsInfos,
+ = std::lower_bound(M.RedeclarationsMap,
+ M.RedeclarationsMap + M.LocalNumRedeclarationsInMap,
ID, CompareLocalRedeclarationsInfoToID());
- if (Result == M.RedeclarationsInfo + M.LocalNumRedeclarationsInfos ||
+ if (Result == M.RedeclarationsMap + M.LocalNumRedeclarationsInMap ||
Result->FirstID != ID) {
// If we have a previously-canonical singleton declaration that was
// merged into another redeclaration chain, create a trivial chain
@@ -2177,21 +2177,18 @@
if (GlobalID != CanonID &&
GlobalID - NUM_PREDEF_DECL_IDS >= M.BaseDeclID &&
GlobalID - NUM_PREDEF_DECL_IDS < M.BaseDeclID + M.LocalNumDecls) {
- if (Decl *D = Reader.GetDecl(GlobalID))
- Chains.push_back(std::make_pair(D, D));
+ addToChain(Reader.GetDecl(GlobalID));
}
return;
}
// Dig out the starting/ending declarations.
- Decl *FirstLocalDecl = Reader.GetLocalDecl(M, Result->FirstLocalID);
- Decl *LastLocalDecl = Reader.GetLocalDecl(M, Result->LastLocalID);
- if (!FirstLocalDecl || !LastLocalDecl)
- return;
-
- // Append this redeclaration chain to the list.
- Chains.push_back(std::make_pair(FirstLocalDecl, LastLocalDecl));
+ unsigned Offset = Result->Offset;
+ unsigned N = M.RedeclarationChains[Offset];
+ M.RedeclarationChains[Offset++] = 0; // Don't try to deserialize again
+ for (unsigned I = 0; I != N; ++I)
+ addToChain(Reader.GetLocalDecl(M, M.RedeclarationChains[Offset++]));
}
bool visit(ModuleFile &M) {
@@ -2201,12 +2198,8 @@
return false;
}
- ArrayRef<std::pair<Decl *, Decl *> > getChains() const {
- return Chains;
- }
-
- void addParsed(Decl *FirstParsedDecl, Decl *LastParsedDecl) {
- Chains.push_back(std::make_pair(FirstParsedDecl, LastParsedDecl));
+ ArrayRef<Decl *> getChain() const {
+ return Chain;
}
};
}
@@ -2226,45 +2219,26 @@
if (MergedPos != MergedDecls.end())
SearchDecls.append(MergedPos->second.begin(), MergedPos->second.end());
- // Build up the list of redeclaration chains.
- RedeclChainVisitor Visitor(*this, SearchDecls, CanonID);
+ // Build up the list of redeclarations.
+ RedeclChainVisitor Visitor(*this, SearchDecls, RedeclsDeserialized, CanonID);
ModuleMgr.visitDepthFirst(&RedeclChainVisitor::visit, &Visitor);
// Retrieve the chains.
- ArrayRef<std::pair<Decl *, Decl *> > Chains = Visitor.getChains();
- if (Chains.empty())
+ ArrayRef<Decl *> Chain = Visitor.getChain();
+ if (Chain.empty())
return;
- // Capture all of the parsed declarations and put them at the end.
+ // Hook up the chains.
Decl *MostRecent = CanonDecl->getMostRecentDecl();
- Decl *FirstParsed = MostRecent;
- if (CanonDecl != MostRecent && !MostRecent->isFromASTFile()) {
- Decl *Current = MostRecent;
- while (Decl *Prev = Current->getPreviousDecl()) {
- if (Prev == CanonDecl)
- break;
-
- if (Prev->isFromASTFile()) {
- Current = Prev;
- continue;
- }
-
- // Chain all of the parsed declarations together.
- ASTDeclReader::attachPreviousDecl(FirstParsed, Prev);
- FirstParsed = Prev;
- Current = Prev;
- }
+ for (unsigned I = 0, N = Chain.size(); I != N; ++I) {
+ if (Chain[I] == CanonDecl)
+ continue;
- Visitor.addParsed(FirstParsed, MostRecent);
+ ASTDeclReader::attachPreviousDecl(Chain[I], MostRecent);
+ MostRecent = Chain[I];
}
-
- // Hook up the separate chains.
- Chains = Visitor.getChains();
- if (Chains[0].first != CanonDecl)
- ASTDeclReader::attachPreviousDecl(Chains[0].first, CanonDecl);
- for (unsigned I = 1, N = Chains.size(); I != N; ++I)
- ASTDeclReader::attachPreviousDecl(Chains[I].first, Chains[I-1].second);
- ASTDeclReader::attachLatestDecl(CanonDecl, Chains.back().second);
+
+ ASTDeclReader::attachLatestDecl(CanonDecl, MostRecent);
}
namespace {
diff --git a/lib/Serialization/ASTWriter.cpp b/lib/Serialization/ASTWriter.cpp
index 2afdc32..d49e711 100644
--- a/lib/Serialization/ASTWriter.cpp
+++ b/lib/Serialization/ASTWriter.cpp
@@ -778,7 +778,7 @@
RECORD(IMPORTS);
RECORD(REFERENCED_SELECTOR_POOL);
RECORD(TU_UPDATE_LEXICAL);
- RECORD(LOCAL_REDECLARATIONS);
+ RECORD(LOCAL_REDECLARATIONS_MAP);
RECORD(SEMA_DECL_REFS);
RECORD(WEAK_UNDECLARED_IDENTIFIERS);
RECORD(PENDING_IMPLICIT_INSTANTIATIONS);
@@ -801,7 +801,9 @@
RECORD(OBJC_CHAINED_CATEGORIES);
RECORD(FILE_SORTED_DECLS);
RECORD(IMPORTED_MODULES);
-
+ RECORD(MERGED_DECLARATIONS);
+ RECORD(LOCAL_REDECLARATIONS);
+
// SourceManager Block.
BLOCK(SOURCE_MANAGER_BLOCK);
RECORD(SM_SLOC_FILE_ENTRY);
@@ -2906,6 +2908,73 @@
Stream.EmitRecord(OPENCL_EXTENSIONS, Record);
}
+void ASTWriter::WriteRedeclarations() {
+ RecordData LocalRedeclChains;
+ SmallVector<serialization::LocalRedeclarationsInfo, 2> LocalRedeclsMap;
+
+ for (unsigned I = 0, N = Redeclarations.size(); I != N; ++I) {
+ Decl *First = Redeclarations[I];
+ assert(First->getPreviousDecl() == 0 && "Not the first declaration?");
+
+ Decl *MostRecent = First->getMostRecentDecl();
+
+ // If we only have a single declaration, there is no point in storing
+ // a redeclaration chain.
+ if (First == MostRecent)
+ continue;
+
+ unsigned Offset = LocalRedeclChains.size();
+ unsigned Size = 0;
+ LocalRedeclChains.push_back(0); // Placeholder for the size.
+
+ // Collect the set of local redeclarations of this declaration.
+ for (Decl *Prev = MostRecent; Prev != First;
+ Prev = Prev->getPreviousDecl()) {
+ if (!Prev->isFromASTFile()) {
+ AddDeclRef(Prev, LocalRedeclChains);
+ ++Size;
+ }
+ }
+ LocalRedeclChains[Offset] = Size;
+
+ // Reverse the set of local redeclarations, so that we store them in
+ // order (since we found them in reverse order).
+ std::reverse(LocalRedeclChains.end() - Size, LocalRedeclChains.end());
+
+ // Add the mapping from the first ID to the set of local declarations.
+ LocalRedeclarationsInfo Info = { getDeclID(First), Offset };
+ LocalRedeclsMap.push_back(Info);
+
+ assert(N == Redeclarations.size() &&
+ "Deserialized a declaration we shouldn't have");
+ }
+
+ if (LocalRedeclChains.empty())
+ return;
+
+ // Sort the local redeclarations map by the first declaration ID,
+ // since the reader will be performing binary searches on this information.
+ llvm::array_pod_sort(LocalRedeclsMap.begin(), LocalRedeclsMap.end());
+
+ // Emit the local redeclarations map.
+ using namespace llvm;
+ llvm::BitCodeAbbrev *Abbrev = new BitCodeAbbrev();
+ Abbrev->Add(BitCodeAbbrevOp(LOCAL_REDECLARATIONS_MAP));
+ Abbrev->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6)); // # of entries
+ Abbrev->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Blob));
+ unsigned AbbrevID = Stream.EmitAbbrev(Abbrev);
+
+ RecordData Record;
+ Record.push_back(LOCAL_REDECLARATIONS_MAP);
+ Record.push_back(LocalRedeclsMap.size());
+ Stream.EmitRecordWithBlob(AbbrevID, Record,
+ reinterpret_cast<char*>(LocalRedeclsMap.data()),
+ LocalRedeclsMap.size() * sizeof(LocalRedeclarationsInfo));
+
+ // Emit the redeclaration chains.
+ Stream.EmitRecord(LOCAL_REDECLARATIONS, LocalRedeclChains);
+}
+
void ASTWriter::WriteMergedDecls() {
if (!Chain || Chain->MergedDecls.empty())
return;
@@ -3424,25 +3493,7 @@
WriteDeclReplacementsBlock();
WriteChainedObjCCategories();
WriteMergedDecls();
-
- if (!LocalRedeclarations.empty()) {
- // Sort the local redeclarations info by the first declaration ID,
- // since the reader will be perforing binary searches on this information.
- llvm::array_pod_sort(LocalRedeclarations.begin(),LocalRedeclarations.end());
-
- llvm::BitCodeAbbrev *Abbrev = new BitCodeAbbrev();
- Abbrev->Add(BitCodeAbbrevOp(LOCAL_REDECLARATIONS));
- Abbrev->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6)); // # of entries
- Abbrev->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Blob));
- unsigned AbbrevID = Stream.EmitAbbrev(Abbrev);
-
- Record.clear();
- Record.push_back(LOCAL_REDECLARATIONS);
- Record.push_back(LocalRedeclarations.size());
- Stream.EmitRecordWithBlob(AbbrevID, Record,
- reinterpret_cast<char*>(LocalRedeclarations.data()),
- LocalRedeclarations.size() * sizeof(LocalRedeclarationsInfo));
- }
+ WriteRedeclarations();
// Some simple statistics
Record.clear();
diff --git a/lib/Serialization/ASTWriterDecl.cpp b/lib/Serialization/ASTWriterDecl.cpp
index 02d0c3c..0b55d73 100644
--- a/lib/Serialization/ASTWriterDecl.cpp
+++ b/lib/Serialization/ASTWriterDecl.cpp
@@ -186,7 +186,7 @@
if (!D->hasAttrs() &&
!D->isImplicit() &&
!D->isUsed(false) &&
- !D->getPreviousDecl() &&
+ D->getFirstDeclaration() == D->getMostRecentDecl() &&
!D->isInvalidDecl() &&
!D->isReferenced() &&
!D->isTopLevelDeclInObjCContainer() &&
@@ -236,7 +236,7 @@
!D->isImplicit() &&
!D->isUsed(false) &&
!D->hasExtInfo() &&
- !D->getPreviousDecl() &&
+ D->getFirstDeclaration() == D->getMostRecentDecl() &&
!D->isInvalidDecl() &&
!D->isReferenced() &&
!D->isTopLevelDeclInObjCContainer() &&
@@ -260,7 +260,7 @@
!D->isImplicit() &&
!D->isUsed(false) &&
!D->hasExtInfo() &&
- !D->getPreviousDecl() &&
+ D->getFirstDeclaration() == D->getMostRecentDecl() &&
!D->isInvalidDecl() &&
!D->isReferenced() &&
!D->isTopLevelDeclInObjCContainer() &&
@@ -692,7 +692,7 @@
!D->isModulePrivate() &&
D->getDeclName().getNameKind() == DeclarationName::Identifier &&
!D->hasExtInfo() &&
- !D->getPreviousDecl() &&
+ D->getFirstDeclaration() == D->getMostRecentDecl() &&
!D->hasCXXDirectInitializer() &&
D->getInit() == 0 &&
!isa<ParmVarDecl>(D) &&
@@ -1237,27 +1237,23 @@
template <typename T>
void ASTDeclWriter::VisitRedeclarable(Redeclarable<T> *D) {
- enum { FirstDeclaration = 0, FirstInFile, PointsToPrevious };
- T *Prev = D->getPreviousDecl();
T *First = D->getFirstDeclaration();
-
- if (!Prev) {
- Record.push_back(FirstDeclaration);
- } else {
- Record.push_back(Prev->isFromASTFile()? FirstInFile : PointsToPrevious);
+ if (First->getMostRecentDecl() != First) {
+ // There is more than one declaration of this entity, so we will need to
+ // write a redeclaration chain.
Writer.AddDeclRef(First, Record);
- Writer.AddDeclRef(D->getPreviousDecl(), Record);
+ Writer.Redeclarations.insert(First);
+
+ // Make sure that we serialize both the previous and the most-recent
+ // declarations, which (transitively) ensures that all declarations in the
+ // chain get serialized.
+ (void)Writer.GetDeclRef(D->getPreviousDecl());
+ (void)Writer.GetDeclRef(First->getMostRecentDecl());
+ } else {
+ // We use the sentinel value 0 to indicate an only declaration.
+ Record.push_back(0);
}
- if (D->RedeclLink.getPointer() != D && (!Prev || Prev->isFromASTFile())) {
- // Capture the set of redeclarations in this file.
- LocalRedeclarationsInfo LocalInfo = {
- Writer.GetDeclRef(First),
- Writer.GetDeclRef(static_cast<T*>(D)),
- Writer.GetDeclRef(D->getMostRecentDecl())
- };
- Writer.LocalRedeclarations.push_back(LocalInfo);
- }
}
//===----------------------------------------------------------------------===//
diff --git a/lib/Serialization/Module.cpp b/lib/Serialization/Module.cpp
index 7db3acc..cb8c9cc 100644
--- a/lib/Serialization/Module.cpp
+++ b/lib/Serialization/Module.cpp
@@ -35,7 +35,7 @@
SelectorLookupTableData(0), SelectorLookupTable(0), LocalNumDecls(0),
DeclOffsets(0), BaseDeclID(0),
LocalNumCXXBaseSpecifiers(0), CXXBaseSpecifiersOffsets(0),
- FileSortedDecls(0), RedeclarationsInfo(0), LocalNumRedeclarationsInfos(0),
+ FileSortedDecls(0), RedeclarationsMap(0), LocalNumRedeclarationsInMap(0),
LocalNumTypes(0), TypeOffsets(0), BaseTypeIndex(0), StatCache(0)
{}