From 113860b9aec24d8bf16314013e4ef9a693479562 Mon Sep 17 00:00:00 2001 From: Rafael Espindola Date: Thu, 20 Oct 2016 10:55:58 +0000 Subject: [PATCH] Compact SectionPiece. We allocate a lot of these when linking debug info. This speeds up the link of debug programs by 1% to 2%. llvm-svn: 284716 --- lld/ELF/InputSection.cpp | 33 ++++++++++++++++++++++----------- lld/ELF/InputSection.h | 36 +++++++++++++++--------------------- lld/ELF/OutputSections.cpp | 12 ++++++++---- lld/ELF/Relocations.cpp | 2 +- 4 files changed, 46 insertions(+), 37 deletions(-) diff --git a/lld/ELF/InputSection.cpp b/lld/ELF/InputSection.cpp index 43b05e4..21bbfa9 100644 --- a/lld/ELF/InputSection.cpp +++ b/lld/ELF/InputSection.cpp @@ -29,10 +29,6 @@ using namespace llvm::support::endian; using namespace lld; using namespace lld::elf; -ArrayRef InputSectionData::getData(const SectionPiece &P) const { - return Data.slice(P.InputOff, P.size()); -} - template static ArrayRef getSectionContents(elf::ObjectFile *File, const typename ELFT::Shdr *Hdr) { @@ -598,13 +594,22 @@ MergeInputSection::splitStrings(ArrayRef Data, size_t EntSize) { if (End == StringRef::npos) fatal(getName(this) + ": string is not null terminated"); size_t Size = End + EntSize; - V.emplace_back(Off, Data.slice(0, Size), !IsAlloca); + V.emplace_back(Off, !IsAlloca); + Hashes.push_back(hash_value(toStringRef(Data.slice(0, Size)))); Data = Data.slice(Size); Off += Size; } return V; } +template +ArrayRef MergeInputSection::getData( + std::vector::const_iterator I) const { + auto Next = I + 1; + size_t End = Next == Pieces.end() ? this->Data.size() : Next->InputOff; + return this->Data.slice(I->InputOff, End - I->InputOff); +} + // Split non-SHF_STRINGS section. Such section is a sequence of // fixed size records. template @@ -615,8 +620,10 @@ MergeInputSection::splitNonStrings(ArrayRef Data, size_t Size = Data.size(); assert((Size % EntSize) == 0); bool IsAlloca = this->getSectionHdr()->sh_flags & SHF_ALLOC; - for (unsigned I = 0, N = Size; I != N; I += EntSize) - V.emplace_back(I, Data.slice(I, EntSize), !IsAlloca); + for (unsigned I = 0, N = Size; I != N; I += EntSize) { + Hashes.push_back(hash_value(toStringRef(Data.slice(I, EntSize)))); + V.emplace_back(I, !IsAlloca); + } return V; } @@ -705,15 +712,19 @@ typename ELFT::uint MergeInputSection::getOffset(uintX_t Offset) const { // It is called after finalize(). template void MergeInputSection::finalizePieces() { OffsetMap.reserve(this->Pieces.size()); - for (SectionPiece &Piece : this->Pieces) { + auto HashI = Hashes.begin(); + for (auto I = Pieces.begin(), E = Pieces.end(); I != E; ++I) { + uint32_t Hash = *HashI; + ++HashI; + SectionPiece &Piece = *I; if (!Piece.Live) continue; - if (Piece.OutputOff == size_t(-1)) { + if (Piece.OutputOff == -1) { // Offsets of tail-merged strings are computed lazily. auto *OutSec = static_cast *>(this->OutSec); - ArrayRef D = this->getData(Piece); + ArrayRef D = this->getData(I); StringRef S((const char *)D.data(), D.size()); - CachedHashStringRef V(S, Piece.Hash); + CachedHashStringRef V(S, Hash); Piece.OutputOff = OutSec->getOffset(V); } OffsetMap[Piece.InputOff] = Piece.OutputOff; diff --git a/lld/ELF/InputSection.h b/lld/ELF/InputSection.h index 0708c2b..fdbe537 100644 --- a/lld/ELF/InputSection.h +++ b/lld/ELF/InputSection.h @@ -59,7 +59,6 @@ public: uint32_t Alignment; StringRef Name; ArrayRef Data; - ArrayRef getData(const SectionPiece &P) const; // If a section is compressed, this has the uncompressed section data. std::unique_ptr UncompressedData; @@ -125,29 +124,19 @@ private: template InputSectionBase InputSectionBase::Discarded; // SectionPiece represents a piece of splittable section contents. +// We allocate a lot of these and binary search on them. This means that they +// have to be as compact as possible, which is why we don't store the size (can +// be found by looking at the next one) and put the hash in a side table. struct SectionPiece { - SectionPiece(size_t Off, ArrayRef Data, uint32_t Hash, bool Live) - : InputOff(Off), Hash(Hash), Size(Data.size()), - Live(Live || !Config->GcSections) {} - SectionPiece(size_t Off, ArrayRef Data, bool Live = false) - : SectionPiece(Off, Data, hash_value(Data), Live) {} - - size_t size() const { return Size; } + SectionPiece(size_t Off, bool Live = false) + : InputOff(Off), OutputOff(-1), Live(Live || !Config->GcSections) {} size_t InputOff; - size_t OutputOff = -1; - - uint32_t Hash; - -private: - // We use bitfields because SplitInputSection is accessed by - // std::upper_bound very often. - // We want to save bits to make it cache friendly. - uint32_t Size : 31; - -public: + ssize_t OutputOff : 8 * sizeof(ssize_t) - 1; uint32_t Live : 1; }; +static_assert(sizeof(SectionPiece) == 2 * sizeof(size_t), + "SectionPiece is too big"); // This corresponds to a SHF_MERGE section of an input file. template class MergeInputSection : public InputSectionBase { @@ -176,6 +165,8 @@ public: // Splittable sections are handled as a sequence of data // rather than a single large blob of data. std::vector Pieces; + ArrayRef getData(std::vector::const_iterator I) const; + std::vector Hashes; // Returns the SectionPiece at a given input section offset. SectionPiece *getSectionPiece(uintX_t Offset); @@ -191,10 +182,13 @@ private: struct EhSectionPiece : public SectionPiece { EhSectionPiece(size_t Off, ArrayRef Data, unsigned FirstRelocation) - : SectionPiece(Off, Data, 0, false), Data(Data.data()), + : SectionPiece(Off, false), Data(Data.data()), Size(Data.size()), FirstRelocation(FirstRelocation) {} const uint8_t *Data; - ArrayRef data() { return {Data, size()}; } + uint32_t Size; + uint32_t size() const { return Size; } + + ArrayRef data() { return {Data, Size}; } unsigned FirstRelocation; }; diff --git a/lld/ELF/OutputSections.cpp b/lld/ELF/OutputSections.cpp index ffa8240..360d652 100644 --- a/lld/ELF/OutputSections.cpp +++ b/lld/ELF/OutputSections.cpp @@ -1188,7 +1188,7 @@ template void EhOutputSection::finalize() { Cie->Piece->OutputOff = Off; Off += alignTo(Cie->Piece->size(), sizeof(uintX_t)); - for (SectionPiece *Fde : Cie->FdePieces) { + for (EhSectionPiece *Fde : Cie->FdePieces) { Fde->OutputOff = Off; Off += alignTo(Fde->size(), sizeof(uintX_t)); } @@ -1281,11 +1281,15 @@ void MergeOutputSection::addSection(InputSectionBase *C) { this->Header.sh_entsize = Sec->getSectionHdr()->sh_entsize; Sections.push_back(Sec); - for (SectionPiece &Piece : Sec->Pieces) { + auto HashI = Sec->Hashes.begin(); + for (auto I = Sec->Pieces.begin(), E = Sec->Pieces.end(); I != E; ++I) { + SectionPiece &Piece = *I; + uint32_t Hash = *HashI; + ++HashI; if (!Piece.Live) continue; - StringRef Data = toStringRef(Sec->getData(Piece)); - CachedHashStringRef V(Data, Piece.Hash); + StringRef Data = toStringRef(Sec->getData(I)); + CachedHashStringRef V(Data, Hash); uintX_t OutputOffset = Builder.add(V); if (!shouldTailMerge()) Piece.OutputOff = OutputOffset; diff --git a/lld/ELF/Relocations.cpp b/lld/ELF/Relocations.cpp index d7228f5..2f7757a 100644 --- a/lld/ELF/Relocations.cpp +++ b/lld/ELF/Relocations.cpp @@ -601,7 +601,7 @@ static void scanRelocs(InputSectionBase &C, ArrayRef Rels) { uintX_t Offset; if (PieceI != PieceE) { assert(PieceI->InputOff <= RI.r_offset && "Relocation not in any piece"); - if (PieceI->OutputOff == (size_t)-1) + if (PieceI->OutputOff == -1) continue; Offset = PieceI->OutputOff + RI.r_offset - PieceI->InputOff; } else { -- 2.7.4