Load the selector table lazily from the PCH file.
This results in a 10% speedup on the Cocoa-prefixed "Hello, World!",
all of which is (not surprisingly) user time. There was a tiny
reduction in the size of the PCH file for Cocoa.h, because certain
selectors aren't being written twice.
I'm using two new tricks here that I'd like to replicate elsewhere:
(1) The selectors not used in the global method pool are packed into
the blob after the global method pool's on-disk hash table and
stored as keys, so that all selectors are in the same blob.
(2) We record the offsets of each selector key when we write it into
the global method pool (or after it, in the same blob). The offset
table is written as a blob, so that we don't need to pack/unpack a
SmallVector with its contents.
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@70055 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Frontend/PCHReader.cpp b/lib/Frontend/PCHReader.cpp
index edb17c7..3e612be 100644
--- a/lib/Frontend/PCHReader.cpp
+++ b/lib/Frontend/PCHReader.cpp
@@ -1141,7 +1141,7 @@
return std::make_pair(KeyLen, DataLen);
}
- internal_key_type ReadKey(const unsigned char* d, unsigned n) {
+ internal_key_type ReadKey(const unsigned char* d, unsigned) {
using namespace clang::io;
SelectorTable &SelTable = Reader.getContext().Selectors;
unsigned N = ReadUnalignedLE16(d);
@@ -1725,70 +1725,8 @@
}
}
-bool PCHReader::ReadSelectorBlock() {
- if (Stream.EnterSubBlock(pch::SELECTOR_BLOCK_ID))
- return Error("Malformed selector block record");
-
- RecordData Record;
- while (true) {
- unsigned Code = Stream.ReadCode();
- switch (Code) {
- case llvm::bitc::END_BLOCK:
- if (Stream.ReadBlockEnd())
- return Error("Error at end of preprocessor block");
- return false;
-
- case llvm::bitc::ENTER_SUBBLOCK:
- // No known subblocks, always skip them.
- Stream.ReadSubBlockID();
- if (Stream.SkipBlock())
- return Error("Malformed block record");
- continue;
-
- case llvm::bitc::DEFINE_ABBREV:
- Stream.ReadAbbrevRecord();
- continue;
- default: break;
- }
-
- // Read a record.
- Record.clear();
- pch::PCHRecordTypes RecType =
- (pch::PCHRecordTypes)Stream.ReadRecord(Code, Record);
- switch (RecType) {
- default: // Default behavior: ignore unknown records.
- break;
- case pch::SELECTOR_TABLE:
- unsigned Idx = 1; // Record[0] == pch::SELECTOR_TABLE.
- unsigned NumSels = Record[Idx++];
-
- llvm::SmallVector<IdentifierInfo *, 8> KeyIdents;
- for (unsigned SelIdx = 0; SelIdx < NumSels; SelIdx++) {
- unsigned NumArgs = Record[Idx++];
- KeyIdents.clear();
- if (NumArgs == 0) {
- // If the number of arguments is 0, we must have an Identifier.
- IdentifierInfo *II = DecodeIdentifierInfo(Record[Idx++]);
- assert(II && "DecodeIdentifierInfo returned 0");
- KeyIdents.push_back(II);
- } else {
- // For keyword selectors, the Identifier is optional (::: is legal!).
- for (unsigned ArgIdx = 0; ArgIdx < NumArgs; ++ArgIdx) {
- IdentifierInfo *II = DecodeIdentifierInfo(Record[Idx++]);
- KeyIdents.push_back(II);
- }
- }
- Selector Sel = PP.getSelectorTable().getSelector(NumArgs,&KeyIdents[0]);
- SelectorData.push_back(Sel);
- }
- }
- }
- return false;
-}
-
PCHReader::PCHReadResult
-PCHReader::ReadPCHBlock(uint64_t &PreprocessorBlockOffset,
- uint64_t &SelectorBlockOffset) {
+PCHReader::ReadPCHBlock(uint64_t &PreprocessorBlockOffset) {
if (Stream.EnterSubBlock(pch::PCH_BLOCK_ID)) {
Error("Malformed block record");
return Failure;
@@ -1832,20 +1770,6 @@
}
break;
- case pch::SELECTOR_BLOCK_ID:
- // Skip the selector block for now, but remember where it is. We
- // want to read it in after the identifier table.
- if (SelectorBlockOffset) {
- Error("Multiple selector blocks found.");
- return Failure;
- }
- SelectorBlockOffset = Stream.GetCurrentBitNo();
- if (Stream.SkipBlock()) {
- Error("Malformed block record");
- return Failure;
- }
- break;
-
case pch::SOURCE_MANAGER_BLOCK_ID:
switch (ReadSourceManagerBlock()) {
case Success:
@@ -1971,12 +1895,21 @@
LocallyScopedExternalDecls.swap(Record);
break;
+ case pch::SELECTOR_OFFSETS:
+ SelectorOffsets = (const uint32_t *)BlobStart;
+ TotalNumSelectors = Record[0];
+ SelectorsLoaded.resize(TotalNumSelectors);
+ break;
+
case pch::METHOD_POOL:
- MethodPoolLookupTable
- = PCHMethodPoolLookupTable::Create(
- (const unsigned char *)BlobStart + Record[0],
- (const unsigned char *)BlobStart,
+ MethodPoolLookupTableData = (const unsigned char *)BlobStart;
+ if (Record[0])
+ MethodPoolLookupTable
+ = PCHMethodPoolLookupTable::Create(
+ MethodPoolLookupTableData + Record[0],
+ MethodPoolLookupTableData,
PCHMethodPoolLookupTrait(*this));
+ TotalSelectorsInMethodPool = Record[1];
break;
}
}
@@ -2012,7 +1945,6 @@
// We expect a number of well-defined blocks, though we don't necessarily
// need to understand them all.
uint64_t PreprocessorBlockOffset = 0;
- uint64_t SelectorBlockOffset = 0;
while (!Stream.AtEndOfStream()) {
unsigned Code = Stream.ReadCode();
@@ -2033,7 +1965,7 @@
}
break;
case pch::PCH_BLOCK_ID:
- switch (ReadPCHBlock(PreprocessorBlockOffset, SelectorBlockOffset)) {
+ switch (ReadPCHBlock(PreprocessorBlockOffset)) {
case Success:
break;
@@ -2117,14 +2049,6 @@
return Failure;
}
}
- if (SelectorBlockOffset) {
- SavedStreamPosition SavedPos(Stream);
- Stream.JumpToBit(SelectorBlockOffset);
- if (ReadSelectorBlock()) {
- Error("Malformed preprocessor block");
- return Failure;
- }
- }
return Success;
}
@@ -2799,30 +2723,53 @@
if ((IdentifierData[I] & 0x01) == 0)
++NumIdentifiersLoaded;
}
+ unsigned NumSelectorsLoaded = 0;
+ for (unsigned I = 0; I < SelectorsLoaded.size(); ++I) {
+ if (SelectorsLoaded[I].getAsOpaquePtr())
+ ++NumSelectorsLoaded;
+ }
- std::fprintf(stderr, " %u/%u types read (%f%%)\n",
- NumTypesLoaded, (unsigned)TypeAlreadyLoaded.size(),
- ((float)NumTypesLoaded/TypeAlreadyLoaded.size() * 100));
- std::fprintf(stderr, " %u/%u declarations read (%f%%)\n",
- NumDeclsLoaded, (unsigned)DeclAlreadyLoaded.size(),
- ((float)NumDeclsLoaded/DeclAlreadyLoaded.size() * 100));
- std::fprintf(stderr, " %u/%u identifiers read (%f%%)\n",
- NumIdentifiersLoaded, (unsigned)IdentifierData.size(),
- ((float)NumIdentifiersLoaded/IdentifierData.size() * 100));
- std::fprintf(stderr, " %u/%u statements read (%f%%)\n",
- NumStatementsRead, TotalNumStatements,
- ((float)NumStatementsRead/TotalNumStatements * 100));
- std::fprintf(stderr, " %u/%u macros read (%f%%)\n",
- NumMacrosRead, TotalNumMacros,
- ((float)NumMacrosRead/TotalNumMacros * 100));
- std::fprintf(stderr, " %u/%u lexical declcontexts read (%f%%)\n",
- NumLexicalDeclContextsRead, TotalLexicalDeclContexts,
- ((float)NumLexicalDeclContextsRead/TotalLexicalDeclContexts
- * 100));
- std::fprintf(stderr, " %u/%u visible declcontexts read (%f%%)\n",
- NumVisibleDeclContextsRead, TotalVisibleDeclContexts,
- ((float)NumVisibleDeclContextsRead/TotalVisibleDeclContexts
- * 100));
+ if (!TypeAlreadyLoaded.empty())
+ std::fprintf(stderr, " %u/%u types read (%f%%)\n",
+ NumTypesLoaded, (unsigned)TypeAlreadyLoaded.size(),
+ ((float)NumTypesLoaded/TypeAlreadyLoaded.size() * 100));
+ if (!DeclAlreadyLoaded.empty())
+ std::fprintf(stderr, " %u/%u declarations read (%f%%)\n",
+ NumDeclsLoaded, (unsigned)DeclAlreadyLoaded.size(),
+ ((float)NumDeclsLoaded/DeclAlreadyLoaded.size() * 100));
+ if (!IdentifierData.empty())
+ std::fprintf(stderr, " %u/%u identifiers read (%f%%)\n",
+ NumIdentifiersLoaded, (unsigned)IdentifierData.size(),
+ ((float)NumIdentifiersLoaded/IdentifierData.size() * 100));
+ if (TotalNumSelectors)
+ std::fprintf(stderr, " %u/%u selectors read (%f%%)\n",
+ NumSelectorsLoaded, TotalNumSelectors,
+ ((float)NumSelectorsLoaded/TotalNumSelectors * 100));
+ if (TotalNumStatements)
+ std::fprintf(stderr, " %u/%u statements read (%f%%)\n",
+ NumStatementsRead, TotalNumStatements,
+ ((float)NumStatementsRead/TotalNumStatements * 100));
+ if (TotalNumMacros)
+ std::fprintf(stderr, " %u/%u macros read (%f%%)\n",
+ NumMacrosRead, TotalNumMacros,
+ ((float)NumMacrosRead/TotalNumMacros * 100));
+ if (TotalLexicalDeclContexts)
+ std::fprintf(stderr, " %u/%u lexical declcontexts read (%f%%)\n",
+ NumLexicalDeclContextsRead, TotalLexicalDeclContexts,
+ ((float)NumLexicalDeclContextsRead/TotalLexicalDeclContexts
+ * 100));
+ if (TotalVisibleDeclContexts)
+ std::fprintf(stderr, " %u/%u visible declcontexts read (%f%%)\n",
+ NumVisibleDeclContextsRead, TotalVisibleDeclContexts,
+ ((float)NumVisibleDeclContextsRead/TotalVisibleDeclContexts
+ * 100));
+ if (TotalSelectorsInMethodPool) {
+ std::fprintf(stderr, " %u/%u method pool entries read (%f%%)\n",
+ NumMethodPoolSelectorsRead, TotalSelectorsInMethodPool,
+ ((float)NumMethodPoolSelectorsRead/TotalSelectorsInMethodPool
+ * 100));
+ std::fprintf(stderr, " %u method pool misses\n", NumMethodPoolMisses);
+ }
std::fprintf(stderr, "\n");
}
@@ -2878,9 +2825,12 @@
PCHMethodPoolLookupTable *PoolTable
= (PCHMethodPoolLookupTable*)MethodPoolLookupTable;
PCHMethodPoolLookupTable::iterator Pos = PoolTable->find(Sel);
- if (Pos == PoolTable->end())
+ if (Pos == PoolTable->end()) {
+ ++NumMethodPoolMisses;
return std::pair<ObjCMethodList, ObjCMethodList>();;
+ }
+ ++NumMethodPoolSelectorsRead;
return *Pos;
}
@@ -2911,16 +2861,26 @@
if (ID == 0)
return Selector();
- if (SelectorData.empty()) {
+ if (!MethodPoolLookupTableData) {
Error("No selector table in PCH file");
return Selector();
}
-
- if (ID > SelectorData.size()) {
+
+ if (ID > TotalNumSelectors) {
Error("Selector ID out of range");
return Selector();
}
- return SelectorData[ID-1];
+
+ unsigned Index = ID - 1;
+ if (SelectorsLoaded[Index].getAsOpaquePtr() == 0) {
+ // Load this selector from the selector table.
+ // FIXME: endianness portability issues with SelectorOffsets table
+ PCHMethodPoolLookupTrait Trait(*this);
+ SelectorsLoaded[Index]
+ = Trait.ReadKey(MethodPoolLookupTableData + SelectorOffsets[Index], 0);
+ }
+
+ return SelectorsLoaded[Index];
}
DeclarationName
diff --git a/lib/Frontend/PCHWriter.cpp b/lib/Frontend/PCHWriter.cpp
index f8c4a77..56c8296 100644
--- a/lib/Frontend/PCHWriter.cpp
+++ b/lib/Frontend/PCHWriter.cpp
@@ -1832,11 +1832,10 @@
return std::make_pair(KeyLen, DataLen);
}
- void EmitKey(llvm::raw_ostream& Out, Selector Sel, unsigned KeyLen) {
- // FIXME: Keep track of the location of the key data (the
- // selector), so we can fold the selector table's storage into
- // this hash table.
- uint64_t Start = Out.tell(); (void)Start;
+ void EmitKey(llvm::raw_ostream& Out, Selector Sel, unsigned) {
+ uint64_t Start = Out.tell();
+ assert((Start >> 32) == 0 && "Selector key offset too large");
+ Writer.SetSelectorOffset(Sel, Start);
unsigned N = Sel.getNumArgs();
clang::io::Emit16(Out, N);
if (N == 0)
@@ -1844,8 +1843,6 @@
for (unsigned I = 0; I != N; ++I)
clang::io::Emit32(Out,
Writer.getIdentifierRef(Sel.getIdentifierInfoForSlot(I)));
-
- assert(Out.tell() - Start == KeyLen && "Key length is wrong");
}
void EmitData(llvm::raw_ostream& Out, key_type_ref,
@@ -1895,6 +1892,7 @@
// Create the on-disk hash table representation. Start by
// iterating through the instance method pool.
PCHMethodPoolTrait::key_type Key;
+ unsigned NumSelectorsInMethodPool = 0;
for (llvm::DenseMap<Selector, ObjCMethodList>::iterator
Instance = SemaRef.InstanceMethodPool.begin(),
InstanceEnd = SemaRef.InstanceMethodPool.end();
@@ -1912,6 +1910,7 @@
Generator.insert(Instance->first,
std::make_pair(Instance->second, Factory->second));
+ ++NumSelectorsInMethodPool;
Empty = false;
}
@@ -1926,41 +1925,68 @@
llvm::DenseMap<Selector, ObjCMethodList>::iterator Instance
= SemaRef.InstanceMethodPool.find(Factory->first);
- if (Instance == SemaRef.InstanceMethodPool.end())
+ if (Instance == SemaRef.InstanceMethodPool.end()) {
Generator.insert(Factory->first,
std::make_pair(ObjCMethodList(), Factory->second));
+ ++NumSelectorsInMethodPool;
+ }
Empty = false;
}
- if (Empty)
+ if (Empty && SelectorOffsets.empty())
return;
// Create the on-disk hash table in a buffer.
llvm::SmallVector<char, 4096> MethodPool;
uint32_t BucketOffset;
+ SelectorOffsets.resize(SelVector.size());
{
PCHMethodPoolTrait Trait(*this);
llvm::raw_svector_ostream Out(MethodPool);
// Make sure that no bucket is at offset 0
clang::io::Emit32(Out, 0);
BucketOffset = Generator.Emit(Out, Trait);
+
+ // For every selector that we have seen but which was not
+ // written into the hash table, write the selector itself and
+ // record it's offset.
+ for (unsigned I = 0, N = SelVector.size(); I != N; ++I)
+ if (SelectorOffsets[I] == 0)
+ Trait.EmitKey(Out, SelVector[I], 0);
}
// Create a blob abbreviation
BitCodeAbbrev *Abbrev = new BitCodeAbbrev();
Abbrev->Add(BitCodeAbbrevOp(pch::METHOD_POOL));
Abbrev->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 32));
+ Abbrev->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 32));
Abbrev->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Blob));
unsigned MethodPoolAbbrev = Stream.EmitAbbrev(Abbrev);
- // Write the identifier table
+ // Write the method pool
RecordData Record;
Record.push_back(pch::METHOD_POOL);
Record.push_back(BucketOffset);
+ Record.push_back(NumSelectorsInMethodPool);
Stream.EmitRecordWithBlob(MethodPoolAbbrev, Record,
&MethodPool.front(),
MethodPool.size());
+
+ // Create a blob abbreviation for the selector table offsets.
+ Abbrev = new BitCodeAbbrev();
+ Abbrev->Add(BitCodeAbbrevOp(pch::SELECTOR_OFFSETS));
+ Abbrev->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 32)); // index
+ Abbrev->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Blob));
+ unsigned SelectorOffsetAbbrev = Stream.EmitAbbrev(Abbrev);
+
+ // Write the selector offsets table.
+ Record.clear();
+ Record.push_back(pch::SELECTOR_OFFSETS);
+ Record.push_back(SelectorOffsets.size());
+ Stream.EmitRecordWithBlob(SelectorOffsetAbbrev, Record,
+ (const char *)&SelectorOffsets.front(),
+ SelectorOffsets.size() * 4);
}
}
@@ -2096,26 +2122,6 @@
Stream.EmitRecord(pch::IDENTIFIER_OFFSET, IdentifierOffsets);
}
-void PCHWriter::WriteSelectorTable() {
- Stream.EnterSubblock(pch::SELECTOR_BLOCK_ID, 2);
- RecordData Record;
- Record.push_back(pch::SELECTOR_TABLE);
- Record.push_back(SelectorIDs.size());
-
- // Create the on-disk representation.
- for (unsigned selIdx = 0; selIdx < SelVector.size(); selIdx++) {
- assert(SelVector[selIdx].getAsOpaquePtr() && "NULL Selector found");
- Record.push_back(SelVector[selIdx].getNumArgs());
- if (SelVector[selIdx].getNumArgs())
- for (unsigned i = 0; i < SelVector[selIdx].getNumArgs(); i++)
- AddIdentifierRef(SelVector[selIdx].getIdentifierInfoForSlot(i), Record);
- else
- AddIdentifierRef(SelVector[selIdx].getIdentifierInfoForSlot(0), Record);
- }
- Stream.EmitRecord(pch::SELECTOR_TABLE, Record);
- Stream.ExitBlock();
-}
-
/// \brief Write a record containing the given attributes.
void PCHWriter::WriteAttributeRecord(const Attr *Attr) {
RecordData Record;
@@ -2250,6 +2256,14 @@
IdentifierOffsets[IdentifierIDs[II] - 1] = (Offset << 1) | 0x01;
}
+/// \brief Note that the selector Sel occurs at the given offset
+/// within the method pool/selector table.
+void PCHWriter::SetSelectorOffset(Selector Sel, uint32_t Offset) {
+ unsigned ID = SelectorIDs[Sel];
+ assert(ID && "Unknown selector");
+ SelectorOffsets[ID - 1] = Offset;
+}
+
PCHWriter::PCHWriter(llvm::BitstreamWriter &Stream)
: Stream(Stream), NextTypeID(pch::NUM_PREDEF_TYPE_IDS),
NumStatements(0), NumMacros(0), NumLexicalDeclContexts(0),
@@ -2309,7 +2323,6 @@
WriteTypesBlock(Context);
WriteDeclsBlock(Context);
WriteMethodPool(SemaRef);
- WriteSelectorTable();
WriteIdentifierTable(PP);
Stream.EmitRecord(pch::TYPE_OFFSET, TypeOffsets);
Stream.EmitRecord(pch::DECL_OFFSET, DeclOffsets);