[ELF] - Simplify how GC works with MergeInputSection.

[grimar]

Summary

This change do a cleanup of handling MergeInputSection when doing GC.
Previously additional checks leaked to MarkLive.cpp, patch eliminates this leaks.

Should be useful for D38724.

[grimar]

ELF/InputSection.h

274

I wonder if shouldGCPieces would be better name.

[ruiu]

ELF/InputSection.h

275

Why don't you garbage-collect non-allocated strings?

[grimar]

ELF/InputSection.h

275

Honestly not sure I got the question right, because my patch does not change this logic and
we do that really long time (if not from begining).

Reason behind not-collecting non-allocated string sections I believe is following. Usually
such sections are debug ones. For example .debug_str section is non-allocatable and contains
strings(It has "MS" flags normally).

We can apply string merging optimization to such section, but we should not collect it.
.debug_info section has references to .debug_str via DW_FORM_strp, so it
has relocation that calculates an offset in .debug_str. .
.debug_info itself is also debug non-allocatable section
which should not be collected, otherwise we would lose all debug information.
And there is nothing else that can keep .debug_str alive as there are normally no references to .debug_str from
allocatable sections I think. Does this answer your question ?

[grimar]

Abandoning per D38724's comments.

ELF/InputSection.h

 };
 
 // SectionPiece represents a piece of splittable section contents.
 // We allocate a lot of these and binary search on them. This means that they
 // have to be as compact as possible, which is why we don't store the size (can
 // be found by looking at the next one) and put the hash in a side table.
 struct SectionPiece {
   SectionPiece(size_t Off, bool Live)
-      : InputOff(Off), Live(Live || !Config->GcSections), OutputOff(-1) {}
+      : InputOff(Off), Live(Live), OutputOff(-1) {}
 
   size_t InputOff : 8 * sizeof(ssize_t) - 1;
   size_t Live : 1;
   ssize_t OutputOff;
 };
 static_assert(sizeof(SectionPiece) == 2 * sizeof(size_t),
               "SectionPiece is too big");
 
 // This corresponds to a SHF_MERGE section of an input file.
 class MergeInputSection : public InputSectionBase {
 public:
   template <class ELFT>
   MergeInputSection(ObjFile<ELFT> *F, const typename ELFT::Shdr *Header,
                     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) {
-    assert(this->Flags & llvm::ELF::SHF_ALLOC);
+    if (!arePiecesLiveByDefault())
       LiveOffsets.insert(Offset);
   }
 
   // Translate an offset in the input section to an offset
   // in the output section.
   uint64_t getOffset(uint64_t Offset) const;
 
   // Splittable sections are handled as a sequence of data
   // rather than a single large blob of data.
public:
 
   // Returns the SectionPiece at a given input section offset.
   SectionPiece *getSectionPiece(uint64_t Offset);
   const SectionPiece *getSectionPiece(uint64_t Offset) const;
 
   SyntheticSection *getParent() const;
 
 private:
+  // We do not GC pieces of non-allocatable sections which are usually
+  // debug ones. Function returns true if pieces should be live by default.
+  bool arePiecesLiveByDefault() {
+    return !Config->GcSections || !(this->Flags & llvm::ELF::SHF_ALLOC);
+  }
+
   void splitStrings(ArrayRef<uint8_t> A, size_t Size);
   void splitNonStrings(ArrayRef<uint8_t> A, size_t Size);
 
   std::vector<uint32_t> Hashes;
 
   mutable llvm::DenseMap<uint64_t, uint64_t> OffsetMap;
   mutable llvm::once_flag InitOffsetMap;
 

ELF/InputSection.cpp

 SyntheticSection *MergeInputSection::getParent() const {
   return cast_or_null<SyntheticSection>(Parent);
 }
 
 // Split SHF_STRINGS section. Such section is a sequence of
 // null-terminated strings.
 void MergeInputSection::splitStrings(ArrayRef<uint8_t> Data, size_t EntSize) {
   size_t Off = 0;
-  bool IsAlloc = this->Flags & SHF_ALLOC;
   while (!Data.empty()) {
     size_t End = findNull(Data, EntSize);
     if (End == StringRef::npos)
       fatal(toString(this) + ": string is not null terminated");
     size_t Size = End + EntSize;
-    Pieces.emplace_back(Off, !IsAlloc);
+    Pieces.emplace_back(Off, arePiecesLiveByDefault());
     Hashes.push_back(xxHash64(toStringRef(Data.slice(0, Size))));
     Data = Data.slice(Size);
     Off += Size;
   }
 }
 
 // Split non-SHF_STRINGS section. Such section is a sequence of
 // fixed size records.
 void MergeInputSection::splitNonStrings(ArrayRef<uint8_t> Data,
                                         size_t EntSize) {
   size_t Size = Data.size();
   assert((Size % EntSize) == 0);
-  bool IsAlloc = this->Flags & SHF_ALLOC;
   for (unsigned I = 0, N = Size; I != N; I += EntSize) {
     Hashes.push_back(xxHash64(toStringRef(Data.slice(I, EntSize))));
-    Pieces.emplace_back(I, !IsAlloc);
+    Pieces.emplace_back(I, arePiecesLiveByDefault());
   }
 }
 
 template <class ELFT>
 MergeInputSection::MergeInputSection(ObjFile<ELFT> *F,
                                      const typename ELFT::Shdr *Header,
                                      StringRef Name)
     : InputSectionBase(F, Header, Name, InputSectionBase::Merge) {}
 
 // 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());
   ArrayRef<uint8_t> Data = this->Data;
   uint64_t EntSize = this->Entsize;
   if (this->Flags & SHF_STRINGS)
     splitStrings(Data, EntSize);
   else
     splitNonStrings(Data, EntSize);
 
-  if (Config->GcSections && (this->Flags & SHF_ALLOC))
+  if (!arePiecesLiveByDefault())
     for (uint64_t Off : LiveOffsets)
       this->getSectionPiece(Off)->Live = true;
 }
 
 // Do binary search to get a section piece at a given input offset.
 SectionPiece *MergeInputSection::getSectionPiece(uint64_t Offset) {
   auto *This = static_cast<const MergeInputSection *>(this);
   return const_cast<SectionPiece *>(This->getSectionPiece(Offset));

ELF/MarkLive.cpp

scanEhFrameSection(EhInputSection &EH,
   EH.split<ELFT>();
 
   if (EH.AreRelocsRela)
     scanEhFrameSection<ELFT>(EH, EH.template relas<ELFT>(), Fn);
   else
     scanEhFrameSection<ELFT>(EH, EH.template rels<ELFT>(), Fn);
 }
 
-// We do not garbage-collect two types of sections:
-// 1) Sections used by the loader (.init, .fini, .ctors, .dtors or .jcr)
-// 2) Non-allocatable sections which typically contain debugging information
+// Some sections are used directly by the loader, so they should never be
+// garbage-collected. This function returns true if a given section is such
+// section.
 template <class ELFT> static bool isReserved(InputSectionBase *Sec) {
   switch (Sec->Type) {
   case SHT_FINI_ARRAY:
   case SHT_INIT_ARRAY:
   case SHT_NOTE:
   case SHT_PREINIT_ARRAY:
     return true;
   default:
-    if (!(Sec->Flags & SHF_ALLOC))
-      return true;
-
     StringRef S = Sec->Name;
     return S.startswith(".ctors") || S.startswith(".dtors") ||
            S.startswith(".init") || S.startswith(".fini") ||
            S.startswith(".jcr");
   }
 }
 
 // This is the main function of the garbage collector.
 // Starting from GC-root sections, this function visits all reachable
 // sections to set their "Live" bits.
 template <class ELFT> static void doGcSections() {
   SmallVector<InputSection *, 256> Q;
   CNamedSections.clear();
 
   auto Enqueue = [&](InputSectionBase *Sec, uint64_t Offset) {
     // Skip over discarded sections. This in theory shouldn't happen, because
     // the ELF spec doesn't allow a relocation to point to a deduplicated
     // COMDAT section directly. Unfortunately this happens in practice (e.g.
     // .eh_frame) so we need to add a check.
     if (Sec == &InputSection::Discarded)
       return;
 
-    // We don't gc non alloc sections.
-    if (!(Sec->Flags & SHF_ALLOC))
-      return;
-
     // 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>(Sec))
       MS->markLiveAt(Offset);
 
     if (Sec->Live)
       return;