Index: ELF/InputSection.h =================================================================== --- ELF/InputSection.h +++ ELF/InputSection.h @@ -145,7 +145,10 @@ // in the output section. uintX_t getOffset(uintX_t Offset); + void finalizePieces(); + private: + llvm::DenseMap OffsetMap; llvm::DenseSet LiveOffsets; }; Index: ELF/InputSection.cpp =================================================================== --- ELF/InputSection.cpp +++ ELF/InputSection.cpp @@ -508,6 +508,7 @@ return S->SectionKind == InputSectionBase::Merge; } +// Do binary search to get a section piece at a given input offset. template SectionPiece *SplitInputSection::getSectionPiece(uintX_t Offset) { ArrayRef D = this->getSectionData(); @@ -524,23 +525,46 @@ return &*I; } +// Returns the offset in an output section for a given input offset. +// Because contents of a mergeable section is not contiguous in output, +// it is not just an addition to a base output offset. template typename ELFT::uint MergeInputSection::getOffset(uintX_t Offset) { + auto It = OffsetMap.find(Offset); + if (It != OffsetMap.end()) + return It->second; + + // If Offset is not at beginning of a section piece, it is not in the map. + // In that case we need to search from the original section piece vector. + // It is a slow path because binary search is slower than hash table lookup + // due to CPU's branch misprediction. SectionPiece &Piece = *this->getSectionPiece(Offset); assert(Piece.Live); - - // Compute the Addend and if the Base is cached, return. uintX_t Addend = Offset - Piece.InputOff; - if (Piece.OutputOff != size_t(-1)) - return Piece.OutputOff + Addend; - - // Map the base to the offset in the output section and cache it. - ArrayRef D = this->getSectionData(); - StringRef Data((const char *)D.data(), D.size()); - StringRef Entry = Data.substr(Piece.InputOff, Piece.size()); - auto *MOS = static_cast *>(this->OutSec); - Piece.OutputOff = MOS->getOffset(Entry); - return Piece.OutputOff + Addend; + uintX_t Ret = Piece.OutputOff + Addend; + + // Cache the result if it's safe to do so. + if (!Config->Threads) + OffsetMap[Offset] = Ret; + return Ret; +} + +// Create a map from input offsets to output offsets for all section pieces. +// It is called after finalize(). +template void MergeInputSection::finalizePieces() { + OffsetMap.grow(this->Pieces.size()); + for (SectionPiece &Piece : this->Pieces) { + if (!Piece.Live) + continue; + if (Piece.OutputOff == size_t(-1)) { + // Offsets of tail-merged strings are computed lazily. + auto *OutSec = static_cast *>(this->OutSec); + ArrayRef D = Piece.data(); + StringRef S((const char *)D.data(), D.size()); + Piece.OutputOff = OutSec->getOffset(S); + } + OffsetMap[Piece.InputOff] = Piece.OutputOff; + } } template Index: ELF/OutputSections.h =================================================================== --- ELF/OutputSections.h +++ ELF/OutputSections.h @@ -93,6 +93,7 @@ bool PageAlign = false; virtual void finalize() {} + virtual void finalizePieces() {} virtual void forEachInputSection(std::function *)> F) {} virtual void writeTo(uint8_t *Buf) {} @@ -320,10 +321,12 @@ void writeTo(uint8_t *Buf) override; unsigned getOffset(StringRef Val); void finalize() override; + void finalizePieces() override; bool shouldTailMerge() const; private: llvm::StringTableBuilder Builder; + std::vector *> Sections; }; struct CieRecord { Index: ELF/OutputSections.cpp =================================================================== --- ELF/OutputSections.cpp +++ ELF/OutputSections.cpp @@ -1164,6 +1164,7 @@ Sec->OutSec = this; this->updateAlign(Sec->Align); this->Header.sh_entsize = Sec->getSectionHdr()->sh_entsize; + Sections.push_back(Sec); bool IsString = this->Header.sh_flags & SHF_STRINGS; @@ -1191,6 +1192,11 @@ this->Header.sh_size = Builder.getSize(); } +template void MergeOutputSection::finalizePieces() { + for (MergeInputSection *Sec : Sections) + Sec->finalizePieces(); +} + template StringTableSection::StringTableSection(StringRef Name, bool Dynamic) : OutputSectionBase(Name, SHT_STRTAB, Index: ELF/Writer.cpp =================================================================== --- ELF/Writer.cpp +++ ELF/Writer.cpp @@ -873,6 +873,11 @@ if (isOutputDynamic()) Out::Dynamic->finalize(); + + // Now that all output offsets are fixed. Finalize mergeable sections + // to fix their maps from input offsets to output offsets. + for (OutputSectionBase *Sec : OutputSections) + Sec->finalizePieces(); } template bool Writer::needsGot() {