"optimize" the offset computation for SHF_MERGE

[• espindola]

Summary

This uses an extra array so that we only have to do a hash lookup per entry.

Unfortunately, this actually slows down a clang link a bit (from 0.497803521 to 0.499284172 seconds). It looks like at least in clang there are not that many references to SHF_MERGE entries for the extra memory allocation to be beneficial.

We could try allocating the offsets in the end of MergeInputSection, but that seems a bit much for now.

My suggestion would be to revisit this once SHF_STRINGS is implemented.

[ruiu]

It's interesting that this patch does not have any performance improvement (or even very slightly negative.) If that's the case, we don't need this patch now.

ELF/InputSection.h

 // This corresponds to a SHF_MERGE section of an input file.
 template <class ELFT> class MergeInputSection : public InputSectionBase<ELFT> {
   typedef InputSectionBase<ELFT> Base;
   typedef typename llvm::object::ELFFile<ELFT>::uintX_t uintX_t;
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Sym Elf_Sym;
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Shdr Elf_Shdr;
 
 public:
+  std::unique_ptr<uintX_t> Offsets;
   MergeInputSection(ObjectFile<ELFT> *F, const Elf_Shdr *Header);
   static bool classof(const InputSectionBase<ELFT> *S);
   uintX_t getOffset(uintX_t Offset) const;
 };
 
 // This corresponds to a non SHF_MERGE section of an input file.
 template <class ELFT> class InputSection : public InputSectionBase<ELFT> {
   typedef InputSectionBase<ELFT> Base;

ELF/InputSection.cpp

MergeInputSection<ELFT>::MergeInputSection(ObjectFile<ELFT> *F,
                                            const Elf_Shdr *Header)
     : InputSectionBase<ELFT>(F, Header, Base::Merge) {}
 
 template <class ELFT>
 bool MergeInputSection<ELFT>::classof(const InputSectionBase<ELFT> *S) {
   return S->SectionKind == Base::Merge;
 }
 
-// FIXME: Optimize this by keeping an offset for each element.
 template <class ELFT>
 typename MergeInputSection<ELFT>::uintX_t
 MergeInputSection<ELFT>::getOffset(uintX_t Offset) const {
   ArrayRef<uint8_t> Data = this->getSectionData();
   uintX_t EntSize = this->Header->sh_entsize;
   if (Offset + EntSize > Data.size())
     error("Entry is past the end of the section");
-  Data = Data.slice(Offset, EntSize);
-  return static_cast<MergeOutputSection<ELFT> *>(this->OutSec)->getOffset(Data);
+  assert(Offset % EntSize == 0);
+  uintX_t Index = Offset / EntSize;
+  return Offsets.get()[Index];
 }
 
 namespace lld {
 namespace elf2 {
 template class InputSectionBase<object::ELF32LE>;
 template class InputSectionBase<object::ELF32BE>;
 template class InputSectionBase<object::ELF64LE>;
 template class InputSectionBase<object::ELF64BE>;

ELF/OutputSections.h

 class MergeOutputSection final : public OutputSectionBase<ELFT> {
   typedef typename OutputSectionBase<ELFT>::uintX_t uintX_t;
 
 public:
   MergeOutputSection(StringRef Name, uint32_t sh_type, uintX_t sh_flags);
   void addSection(MergeInputSection<ELFT> *S);
   void writeTo(uint8_t *Buf) override;
 
-  unsigned getOffset(ArrayRef<uint8_t> Val);
-
 private:
   // This map is used to find if we already have an entry for a given value and,
   // if so, at what offset it is.
   llvm::MapVector<ArrayRef<uint8_t>, uintX_t> Offsets;
 };
 
 template <class ELFT>
 class InterpSection final : public OutputSectionBase<ELFT> {

ELF/OutputSections.cpp

void MergeOutputSection<ELFT>::addSection(MergeInputSection<ELFT> *S) {
   if (Align > this->Header.sh_addralign)
     this->Header.sh_addralign = Align;
 
   uintX_t Off = this->Header.sh_size;
   ArrayRef<uint8_t> Data = S->getSectionData();
   uintX_t EntSize = S->getSectionHdr()->sh_entsize;
   if (Data.size() % EntSize)
     error("SHF_MERGE section size must be a multiple of sh_entsize");
-  for (unsigned I = 0, N = Data.size(); I != N; I += EntSize) {
+  S->Offsets.reset(new uintX_t[Data.size() / EntSize]);
+  for (unsigned I = 0, N = Data.size(), J = 0; I != N; I += EntSize, ++J) {
     auto P = Offsets.insert(std::make_pair(Data.slice(I, EntSize), Off));
+    S->Offsets.get()[J] = P.first->second;
     if (P.second)
       Off += EntSize;
   }
   this->Header.sh_size = Off;
 }
 
 template <class ELFT>
-unsigned MergeOutputSection<ELFT>::getOffset(ArrayRef<uint8_t> Val) {
-  return Offsets.find(Val)->second;
-}
-
-template <class ELFT>
 StringTableSection<ELFT>::StringTableSection(bool Dynamic)
     : OutputSectionBase<ELFT>(Dynamic ? ".dynstr" : ".strtab",
                               llvm::ELF::SHT_STRTAB,
                               Dynamic ? (uintX_t)llvm::ELF::SHF_ALLOC : 0),
       Dynamic(Dynamic) {
   this->Header.sh_addralign = 1;
 }