Do not split mergeable sections if they are gc'ed.

[ruiu]

Summary

Previously, mergeable section's constructors did more than just
setting member variables; it split section contents into small
pieces. It is not always computationally cheap task because if
the section is a mergeable string section, it needs to scan the
entire section to split them by NUL characters.

If a section would be thrown away by GC, that cost ended up
being a waste of time. It is going to be larger problem if the
section is compressed -- the whole time to uncompress it and
split it up is going to be a waste.

Luckily, we can defer section splitting after GC. We just have
to remember which offsets are in use during GC and apply that later.
This patch implements it.

[ruiu]

Removed unrelated changes.

[grimar]

(for history)
my opinion about this was here: D20433

lld/trunk/ELF/Driver.cpp

 //===- Driver.cpp ---------------------------------------------------------===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "Driver.h"
 #include "Config.h"
 #include "Error.h"
 #include "ICF.h"
 #include "InputFiles.h"
+#include "InputSection.h"
 #include "LinkerScript.h"
 #include "SymbolListFile.h"
 #include "SymbolTable.h"
 #include "Target.h"
 #include "Writer.h"
 #include "lld/Driver/Driver.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Support/TargetSelect.h"
template <class ELFT> void LinkerDriver::link(opt::InputArgList &Args) {
   for (auto *Arg : Args.filtered(OPT_wrap))
     Symtab.wrap(Arg->getValue());
 
   // Write the result to the file.
   if (Config->GcSections)
     markLive<ELFT>();
   if (Config->ICF)
     doIcf<ELFT>();
+
+  // MergeInputSection::splitIntoPieces needs to be called before
+  // any call of MergeInputSection::getOffset. Do that.
+  for (const std::unique_ptr<elf::ObjectFile<ELFT>> &F :
+       Symtab.getObjectFiles())
+    for (InputSectionBase<ELFT> *S : F->getSections())
+      if (S && S != &InputSection<ELFT>::Discarded && S->Live)
+        if (auto *MS = dyn_cast<MergeInputSection<ELFT>>(S))
+          MS->splitIntoPieces();
+
   writeResult<ELFT>(&Symtab);
 }

lld/trunk/ELF/InputSection.h

 //===- InputSection.h -------------------------------------------*- C++ -*-===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_ELF_INPUT_SECTION_H
 #define LLD_ELF_INPUT_SECTION_H
 
 #include "Config.h"
 #include "lld/Core/LLVM.h"
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/TinyPtrVector.h"
 #include "llvm/Object/ELF.h"
 
 namespace lld {
 namespace elf {
 
 class SymbolBody;
 

 template <class ELFT> class MergeInputSection : public SplitInputSection<ELFT> {
   typedef typename ELFT::uint uintX_t;
   typedef typename ELFT::Sym Elf_Sym;
   typedef typename ELFT::Shdr Elf_Shdr;
 
 public:
   MergeInputSection(ObjectFile<ELFT> *F, const Elf_Shdr *Header);
   static bool classof(const InputSectionBase<ELFT> *S);
-  // Translate an offset in the input section to an offset in the output
-  // section.
+  void splitIntoPieces();
+
+  // Mark the piece at a given offset live. Used by GC.
+  void markLiveAt(uintX_t Offset) { LiveOffsets.insert(Offset); }
+
+  // Translate an offset in the input section to an offset
+  // in the output section.
   uintX_t getOffset(uintX_t Offset);
+
+private:
+  llvm::DenseSet<uintX_t> LiveOffsets;
 };
 
 // This corresponds to a .eh_frame section of an input file.
 template <class ELFT> class EHInputSection : public SplitInputSection<ELFT> {
 public:
   typedef typename ELFT::Shdr Elf_Shdr;
   typedef typename ELFT::uint uintX_t;
   EHInputSection(ObjectFile<ELFT> *F, const Elf_Shdr *Header);

lld/trunk/ELF/InputSection.cpp

static std::vector<SectionPiece> splitNonStrings(ArrayRef<uint8_t> Data,
   for (unsigned I = 0, N = Size; I != N; I += EntSize)
     V.emplace_back(I, Data.slice(I, EntSize));
   return V;
 }
 
 template <class ELFT>
 MergeInputSection<ELFT>::MergeInputSection(elf::ObjectFile<ELFT> *F,
                                            const Elf_Shdr *Header)
-    : SplitInputSection<ELFT>(F, Header, InputSectionBase<ELFT>::Merge) {
+    : SplitInputSection<ELFT>(F, Header, InputSectionBase<ELFT>::Merge) {}
+
+template <class ELFT> void MergeInputSection<ELFT>::splitIntoPieces() {
   ArrayRef<uint8_t> Data = this->getSectionData();
   uintX_t EntSize = this->Header->sh_entsize;
   if (this->Header->sh_flags & SHF_STRINGS)
     this->Pieces = splitStrings(Data, EntSize);
   else
     this->Pieces = splitNonStrings(Data, EntSize);
+
+  if (Config->GcSections)
+    for (uintX_t Off : LiveOffsets)
+      this->getSectionPiece(Off)->Live = true;
 }
 
 template <class ELFT>
 bool MergeInputSection<ELFT>::classof(const InputSectionBase<ELFT> *S) {
   return S->SectionKind == InputSectionBase<ELFT>::Merge;
 }
 
 template <class ELFT>

lld/trunk/ELF/MarkLive.cpp

 // Starting from GC-root sections, this function visits all reachable
 // sections to set their "Live" bits.
 template <class ELFT> void elf::markLive() {
   SmallVector<InputSection<ELFT> *, 256> Q;
 
   auto Enqueue = [&](ResolvedReloc<ELFT> R) {
     if (!R.Sec)
       return;
-    if (auto *MS = dyn_cast<MergeInputSection<ELFT>>(R.Sec)) {
-      SectionPiece *Piece = MS->getSectionPiece(R.Offset);
-      Piece->Live = true;
-    }
+
+    // Usually, a whole section is marked as live or dead, but in mergeable
+    // (splittable) sections, each piece of data has independent liveness bit.
+    // So we explicitly tell it which offset is in use.
+    if (auto *MS = dyn_cast<MergeInputSection<ELFT>>(R.Sec))
+      MS->markLiveAt(R.Offset);
+
     if (R.Sec->Live)
       return;
     R.Sec->Live = true;
     if (InputSection<ELFT> *S = dyn_cast<InputSection<ELFT>>(R.Sec))
       Q.push_back(S);
   };
 
   auto MarkSymbol = [&](const SymbolBody *Sym) {