[ELF] - Stop using SectionKey for creating output sections.

[grimar]

Summary

Stop using SectionKey for creating output sections.

Initially SectionKey was designed because we merged section with
use of Flags and Alignment fields. Currently LLD merges them by name only,
except the case when -relocatable output is produced. In that case
we still merge sections only with the same flags and alignment.
There is probably no issue at all to stop using Flags and Alignment for -r and
just disable the merging in that case.

After doing that change we can get rid of using SectionKey. That is not only
simplifies the code, but also gives perfomance boost.
I tried to link chrome (used set of objects from lld-speed-test archive shared
by Rafael earlier) and results are next:

• Without patch: 1,666750355 seconds time elapsed ( +-0,10% )
• With patch: 1,551585364 seconds time elapsed ( +-0,12% )

That looks to be 7% difference..

[ruiu]

LGTM

This is very nice improvement. The 7% improvement you observed feels a bit too good, and I'm not sure if it is applicable to other test cases, but this patch itself is pretty nice.

[grimar]

In D39594#915573, @ruiu wrote:

LGTM

This is very nice improvement. The 7% improvement you observed feels a bit too good, and I'm not sure if it is applicable to other test cases, but this patch itself is pretty nice.

Yeah I have the same feelings. 7% is too good to be true for general case, I tried to link mozilla today and time goes
from 3,210261947 seconds ( +- 0,06% ) to 3,153782940 seconds ( +- 0,06% ) for me, it is about 2%, still a nice time bonus for cleanup change.

lld/trunk/ELF/OutputSections.h

struct Out {
   static OutputSection *DebugInfo;
   static OutputSection *ElfHeader;
   static OutputSection *ProgramHeaders;
   static OutputSection *PreinitArray;
   static OutputSection *InitArray;
   static OutputSection *FiniArray;
 };
 
-struct SectionKey {
-  StringRef Name;
-  uint64_t Flags;
-  uint32_t Alignment;
-};
 } // namespace elf
 } // namespace lld
 
-namespace llvm {
-template <> struct DenseMapInfo<lld::elf::SectionKey> {
-  static lld::elf::SectionKey getEmptyKey();
-  static lld::elf::SectionKey getTombstoneKey();
-  static unsigned getHashValue(const lld::elf::SectionKey &Val);
-  static bool isEqual(const lld::elf::SectionKey &LHS,
-                      const lld::elf::SectionKey &RHS);
-};
-} // namespace llvm
-
 namespace lld {
 namespace elf {
 // This class knows how to create an output section for a given
 // input section. Output section type is determined by various
 // factors, including input section's sh_flags, sh_type and
 // linker scripts.
 class OutputSectionFactory {
 public:
   OutputSectionFactory();
   ~OutputSectionFactory();
 
   OutputSection *addInputSec(InputSectionBase *IS, StringRef OutsecName);
 
 private:
-  llvm::SmallDenseMap<SectionKey, OutputSection *> Map;
+  llvm::StringMap<OutputSection *> Map;
 };
 
 uint64_t getHeaderSize();
 void sortByOrder(llvm::MutableArrayRef<InputSection *> In,
                  std::function<int(InputSectionBase *S)> Order);
 
 extern std::vector<OutputSection *> OutputSections;
 } // namespace elf
 } // namespace lld
 
 #endif

lld/trunk/ELF/OutputSections.cpp

if (!IS->Assigned) {
     if (SectionCommands.empty() ||
         !isa<InputSectionDescription>(SectionCommands.back()))
       SectionCommands.push_back(make<InputSectionDescription>(""));
     auto *ISD = cast<InputSectionDescription>(SectionCommands.back());
     ISD->Sections.push_back(IS);
   }
 }
 
-static SectionKey createKey(InputSectionBase *IS, StringRef OutsecName) {
-  // When control reaches here, mergeable sections have already been
-  // merged except the -r case. If that's the case, we want to combine
-  // mergeable sections by sh_entsize and sh_flags.
-  if (Config->Relocatable && (IS->Flags & SHF_MERGE)) {
-    uint64_t Flags = IS->Flags & (SHF_MERGE | SHF_STRINGS);
-    uint32_t Alignment = std::max<uint32_t>(IS->Alignment, IS->Entsize);
-    return SectionKey{OutsecName, Flags, Alignment};
-  }
-
-  //  The ELF spec just says
-  // ----------------------------------------------------------------
-  // In the first phase, input sections that match in name, type and
-  // attribute flags should be concatenated into single sections.
-  // ----------------------------------------------------------------
-  //
-  // However, it is clear that at least some flags have to be ignored for
-  // section merging. At the very least SHF_GROUP and SHF_COMPRESSED have to be
-  // ignored. We should not have two output .text sections just because one was
-  // in a group and another was not for example.
-  //
-  // It also seems that that wording was a late addition and didn't get the
-  // necessary scrutiny.
-  //
-  // Merging sections with different flags is expected by some users. One
-  // reason is that if one file has
-  //
-  // int *const bar __attribute__((section(".foo"))) = (int *)0;
-  //
-  // gcc with -fPIC will produce a read only .foo section. But if another
-  // file has
-  //
-  // int zed;
-  // int *const bar __attribute__((section(".foo"))) = (int *)&zed;
-  //
-  // gcc with -fPIC will produce a read write section.
-  //
-  // Last but not least, when using linker script the merge rules are forced by
-  // the script. Unfortunately, linker scripts are name based. This means that
-  // expressions like *(.foo*) can refer to multiple input sections with
-  // different flags. We cannot put them in different output sections or we
-  // would produce wrong results for
-  //
-  // start = .; *(.foo.*) end = .; *(.bar)
-  //
-  // and a mapping of .foo1 and .bar1 to one section and .foo2 and .bar2 to
-  // another. The problem is that there is no way to layout those output
-  // sections such that the .foo sections are the only thing between the start
-  // and end symbols.
-  //
-  // Given the above issues, we instead merge sections by name and error on
-  // incompatible types and flags.
-  return SectionKey{OutsecName, 0, 0};
-}
-
 OutputSectionFactory::OutputSectionFactory() {}
 
 void elf::sortByOrder(MutableArrayRef<InputSection *> In,
                       std::function<int(InputSectionBase *S)> Order) {
   typedef std::pair<int, InputSection *> Pair;
   auto Comp = [](const Pair &A, const Pair &B) { return A.first < B.first; };
 
   std::vector<Pair> V;
if (Out->RelocationSection) {
       Out->RelocationSection->addSection(Sec);
       return nullptr;
     }
 
     Out->RelocationSection = createSection(IS, OutsecName);
     return Out->RelocationSection;
   }
 
-  SectionKey Key = createKey(IS, OutsecName);
-  OutputSection *&Sec = Map[Key];
+  // When control reaches here, mergeable sections have already been
+  // merged except the -r case. If that's the case, we do not combine them
+  // and let final link to handle this optimization.
+  if (Config->Relocatable && (IS->Flags & SHF_MERGE))
+    return createSection(IS, OutsecName);
+
+  //  The ELF spec just says
+  // ----------------------------------------------------------------
+  // In the first phase, input sections that match in name, type and
+  // attribute flags should be concatenated into single sections.
+  // ----------------------------------------------------------------
+  //
+  // However, it is clear that at least some flags have to be ignored for
+  // section merging. At the very least SHF_GROUP and SHF_COMPRESSED have to be
+  // ignored. We should not have two output .text sections just because one was
+  // in a group and another was not for example.
+  //
+  // It also seems that that wording was a late addition and didn't get the
+  // necessary scrutiny.
+  //
+  // Merging sections with different flags is expected by some users. One
+  // reason is that if one file has
+  //
+  // int *const bar __attribute__((section(".foo"))) = (int *)0;
+  //
+  // gcc with -fPIC will produce a read only .foo section. But if another
+  // file has
+  //
+  // int zed;
+  // int *const bar __attribute__((section(".foo"))) = (int *)&zed;
+  //
+  // gcc with -fPIC will produce a read write section.
+  //
+  // Last but not least, when using linker script the merge rules are forced by
+  // the script. Unfortunately, linker scripts are name based. This means that
+  // expressions like *(.foo*) can refer to multiple input sections with
+  // different flags. We cannot put them in different output sections or we
+  // would produce wrong results for
+  //
+  // start = .; *(.foo.*) end = .; *(.bar)
+  //
+  // and a mapping of .foo1 and .bar1 to one section and .foo2 and .bar2 to
+  // another. The problem is that there is no way to layout those output
+  // sections such that the .foo sections are the only thing between the start
+  // and end symbols.
+  //
+  // Given the above issues, we instead merge sections by name and error on
+  // incompatible types and flags.
+  OutputSection *&Sec = Map[OutsecName];
   if (Sec) {
     Sec->addSection(cast<InputSection>(IS));
     return nullptr;
   }
 
   Sec = createSection(IS, OutsecName);
   return Sec;
 }
 
 OutputSectionFactory::~OutputSectionFactory() {}
 
-SectionKey DenseMapInfo<SectionKey>::getEmptyKey() {
-  return SectionKey{DenseMapInfo<StringRef>::getEmptyKey(), 0, 0};
-}
-
-SectionKey DenseMapInfo<SectionKey>::getTombstoneKey() {
-  return SectionKey{DenseMapInfo<StringRef>::getTombstoneKey(), 0, 0};
-}
-
-unsigned DenseMapInfo<SectionKey>::getHashValue(const SectionKey &Val) {
-  return hash_combine(Val.Name, Val.Flags, Val.Alignment);
-}
-
-bool DenseMapInfo<SectionKey>::isEqual(const SectionKey &LHS,
-                                       const SectionKey &RHS) {
-  return DenseMapInfo<StringRef>::isEqual(LHS.Name, RHS.Name) &&
-         LHS.Flags == RHS.Flags && LHS.Alignment == RHS.Alignment;
-}
-
 uint64_t elf::getHeaderSize() {
   if (Config->OFormatBinary)
     return 0;
   return Out::ElfHeader->Size + Out::ProgramHeaders->Size;
 }
 
 bool OutputSection::classof(const BaseCommand *C) {
   return C->Kind == OutputSectionKind;