Split merge sections early

[• espindola]

Summary

Now that getSectionPiece is fast (uses a hash) it is probably OK to split merge sections early.

The reason I want to do this is to split eh_frame sections in the same place.

This does mean that we have to decompress early. Given that the only compressed sections are debug info, I don't think we are missing much.

It is a small improvement: 0.5% geometric mean.

[grimar]

I think it is probably OK. What about adding an assert checking that we do decompress only for non-alloc sections?

[• espindola]

In D46169#1080780, @grimar wrote:

I think it is probably OK. What about adding an assert checking that we do decompress only for non-alloc sections?

I don't think an assert is appropriate as we would still do the right thing. If we do get to a point where we are decompressing too much we can revisit this.

[ruiu]

LGTM

ELF/InputSection.h

226–227

I'd remove this function and inline it.

[grimar]

In D46169#1081164, @espindola wrote:

In D46169#1080780, @grimar wrote:

I think it is probably OK. What about adding an assert checking that we do decompress only for non-alloc sections?

I don't think an assert is appropriate as we would still do the right thing. If we do get to a point where we are decompressing too much we can revisit this.

Ok. We would hit this probably if would have compilers that implement the DWARF5 features about multiple debug sections like .debug_info linked with multiple text sections I think.
If those were compressed, calling decompress before marking live sections and dropping unused would be waste.
But there are no such compilers and everybody waiting for new standard afaik.

[• espindola]

r331058

ELF/Driver.cpp

template <class ELFT> void LinkerDriver::link(opt::InputArgList &Args) {
   // This adds a .comment section containing a version string. We have to add it
   // before decompressAndMergeSections because the .comment section is a
   // mergeable section.
   if (!Config->Relocatable)
     InputSections.push_back(createCommentSection());
 
   // Do size optimizations: garbage collection, merging of SHF_MERGE sections
   // and identical code folding.
+  decompressSections();
+  splitSections();
   markLive<ELFT>();
   demoteSymbols<ELFT>();
-  decompressSections();
   mergeSections();
   if (Config->ICF)
     doIcf<ELFT>();
 
   // Read the callgraph now that we know what was gced or icfed
   if (auto *Arg = Args.getLastArg(OPT_call_graph_ordering_file))
     if (Optional<MemoryBufferRef> Buffer = readFile(Arg->getValue()))
       readCallGraph(*Buffer);
 
   // Write the result to the file.
   writeResult<ELFT>();
 }

ELF/InputSection.h

public:
   MergeInputSection(ObjFile<ELFT> &F, const typename ELFT::Shdr &Header,
                     StringRef Name);
   MergeInputSection(uint64_t Flags, uint32_t Type, uint64_t Entsize,
                     ArrayRef<uint8_t> Data, StringRef Name);
 
   static bool classof(const SectionBase *S) { return S->kind() == Merge; }
   void splitIntoPieces();
 
   // Mark the piece at a given offset live. Used by GC.
-  void markLiveAt(uint64_t Offset) {
-    if (this->Flags & llvm::ELF::SHF_ALLOC)
-      LiveOffsets.insert(Offset);
-  }
+  void markLiveAt(uint64_t Offset);
 
   // Translate an offset in the input section to an offset in the parent
   // MergeSyntheticSection.
   uint64_t getParentOffset(uint64_t Offset) const;
 
   // Splittable sections are handled as a sequence of data
   // rather than a single large blob of data.
   std::vector<SectionPiece> Pieces;
const SectionPiece *getSectionPiece(uint64_t Offset) const {
     return const_cast<MergeInputSection *>(this)->getSectionPiece(Offset);
   }
 
   SyntheticSection *getParent() const;
 
 private:
   void splitStrings(ArrayRef<uint8_t> A, size_t Size);
   void splitNonStrings(ArrayRef<uint8_t> A, size_t Size);
-
-  llvm::DenseSet<uint32_t> LiveOffsets;
 };
 
 struct EhSectionPiece {
   EhSectionPiece(size_t Off, InputSectionBase *Sec, uint32_t Size,
                  unsigned FirstRelocation)
       : InputOff(Off), Sec(Sec), Size(Size), FirstRelocation(FirstRelocation) {}
 
   ArrayRef<uint8_t> data() { return {Sec->Data.data() + this->InputOff, Size}; }

ELF/InputSection.cpp

MergeInputSection::MergeInputSection(ObjFile<ELFT> &F,
     : InputSectionBase(F, Header, Name, InputSectionBase::Merge) {}
 
 MergeInputSection::MergeInputSection(uint64_t Flags, uint32_t Type,
                                      uint64_t Entsize, ArrayRef<uint8_t> Data,
                                      StringRef Name)
     : InputSectionBase(nullptr, Flags, Type, Entsize, /*Link*/ 0, /*Info*/ 0,
                        /*Alignment*/ Entsize, Data, Name, SectionBase::Merge) {}
 
+void MergeInputSection::markLiveAt(uint64_t Offset) {
+  getSectionPiece(Offset)->Live = true;
+}
+
 // This function is called after we obtain a complete list of input sections
 // that need to be linked. This is responsible to split section contents
 // into small chunks for further processing.
 //
 // Note that this function is called from parallelForEach. This must be
 // thread-safe (i.e. no memory allocation from the pools).
 void MergeInputSection::splitIntoPieces() {
   assert(Pieces.empty());
 
   if (Flags & SHF_STRINGS)
     splitStrings(Data, Entsize);
   else
     splitNonStrings(Data, Entsize);
 
   OffsetMap.reserve(Pieces.size());
   for (size_t I = 0, E = Pieces.size(); I != E; ++I)
     OffsetMap[Pieces[I].InputOff] = I;
-
-  if (Config->GcSections && (Flags & SHF_ALLOC))
-    for (uint32_t Off : LiveOffsets)
-      getSectionPiece(Off)->Live = true;
 }
 
 template <class It, class T, class Compare>
 static It fastUpperBound(It First, It Last, const T &Value, Compare Comp) {
   size_t Size = std::distance(First, Last);
   assert(Size != 0);
   while (Size != 1) {
     size_t H = Size / 2;

ELF/SyntheticSections.h

 private:
   std::vector<Thunk *> Thunks;
   size_t Size = 0;
 };
 
 InputSection *createInterpSection();
 MergeInputSection *createCommentSection();
 void decompressSections();
+void splitSections();
 void mergeSections();
 
 Defined *addSyntheticLocal(StringRef Name, uint8_t Type, uint64_t Value,
                            uint64_t Size, InputSectionBase &Section);
 
 // Linker generated sections which can be used as inputs.
 struct InX {
   static InputSection *ARMAttributes;

ELF/SyntheticSections.cpp

static MergeSyntheticSection *createMergeSynthetic(StringRef Name,
   bool ShouldTailMerge = (Flags & SHF_STRINGS) && Config->Optimize >= 2;
   if (ShouldTailMerge)
     return make<MergeTailSection>(Name, Type, Flags, Alignment);
   return make<MergeNoTailSection>(Name, Type, Flags, Alignment);
 }
 
 // Debug sections may be compressed by zlib. Decompress if exists.
 void elf::decompressSections() {
+  parallelForEach(InputSections,
+                  [](InputSectionBase *Sec) { Sec->maybeDecompress(); });
+}
+
+void elf::splitSections() {
+  // splitIntoPieces needs to be called on each MergeInputSection
+  // before calling finalizeContents().
   parallelForEach(InputSections, [](InputSectionBase *Sec) {
-    if (Sec->Live)
-      Sec->maybeDecompress();
+    if (auto *S = dyn_cast<MergeInputSection>(Sec))
+      S->splitIntoPieces();
   });
 }
 
 // This function scans over the inputsections to create mergeable
 // synthetic sections.
 //
 // It removes MergeInputSections from the input section array and adds
 // new synthetic sections at the location of the first input section
 // that it replaces. It then finalizes each synthetic section in order
 // to compute an output offset for each piece of each input section.
 void elf::mergeSections() {
-  // splitIntoPieces needs to be called on each MergeInputSection
-  // before calling finalizeContents(). Do that first.
-  parallelForEach(InputSections, [](InputSectionBase *Sec) {
-    if (auto *S = dyn_cast<MergeInputSection>(Sec))
-      S->splitIntoPieces();
-  });
-
   std::vector<MergeSyntheticSection *> MergeSections;
   for (InputSectionBase *&S : InputSections) {
     MergeInputSection *MS = dyn_cast<MergeInputSection>(S);
     if (!MS)
       continue;
 
     // We do not want to handle sections that are not alive, so just remove
     // them instead of trying to merge.