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

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.

Differential Revision: http://reviews.llvm.org/D20516

llvm-svn: 270455

4 files changed, 36 insertions, 7 deletions

diff --git a/lld/ELF/Driver.cpp b/lld/ELF/Driver.cpp
index f9e609ac19d..ac06dd81485 100644
--- a/lld/ELF/Driver.cpp
+++ b/lld/ELF/Driver.cpp
@@ -12,6 +12,7 @@
 #include "Error.h"
 #include "ICF.h"
 #include "InputFiles.h"
+#include "InputSection.h"
 #include "LinkerScript.h"
 #include "SymbolListFile.h"
 #include "SymbolTable.h"
@@ -507,5 +508,15 @@ template <class ELFT> void LinkerDriver::link(opt::InputArgList &Args) {
     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);
 }
diff --git a/lld/ELF/InputSection.cpp b/lld/ELF/InputSection.cpp
index c3378432187..fd69502bcf5 100644
--- a/lld/ELF/InputSection.cpp
+++ b/lld/ELF/InputSection.cpp
@@ -501,13 +501,19 @@ static std::vector<SectionPiece> splitNonStrings(ArrayRef<uint8_t> Data,
 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>
diff --git a/lld/ELF/InputSection.h b/lld/ELF/InputSection.h
index bb089d55aeb..cd122cf7029 100644
--- a/lld/ELF/InputSection.h
+++ b/lld/ELF/InputSection.h
@@ -12,6 +12,7 @@
 
 #include "Config.h"
 #include "lld/Core/LLVM.h"
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/TinyPtrVector.h"
 #include "llvm/Object/ELF.h"
 
@@ -171,9 +172,17 @@ template <class ELFT> class MergeInputSection : public SplitInputSection<ELFT> {
 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.
diff --git a/lld/ELF/MarkLive.cpp b/lld/ELF/MarkLive.cpp
index 87ff847041e..54de064161d 100644
--- a/lld/ELF/MarkLive.cpp
+++ b/lld/ELF/MarkLive.cpp
@@ -141,10 +141,13 @@ template <class ELFT> void elf::markLive() {
   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;