[ELF] - Implemented GC for common symbols.

[grimar]

Summary

This is PR33887, previously unused common symbols
were not collected.

[ruiu]

I think this patch needs rewriting because it uses a callback function where you don't actually have to and uses Offset as a different meaning than it should be. I'll send you an updated one.

[grimar]

In D36520#837109, @ruiu wrote:

I think this patch needs rewriting because it uses a callback function where you don't actually have to and uses Offset as a different meaning than it should be. I'll send you an updated one.

Live bit is the first thing I was thinking of honestly. Then decided to reuse Offset, supposed that new field will became a problem during review :)
Abandoning in favor of D36546.

ELF/MarkLive.cpp

 using namespace lld::elf;
 
 namespace {
 // A resolved relocation. The Sec and Offset fields are set if the relocation
 // was resolved to an offset within a section.
 struct ResolvedReloc {
   InputSectionBase *Sec;
   uint64_t Offset;
+  SymbolBody *Symbol;
 };
 } // end anonymous namespace
 
 template <class ELFT>
 static typename ELFT::uint getAddend(InputSectionBase &Sec,
                                      const typename ELFT::Rel &Rel) {
   return Target->getImplicitAddend(Sec.Data.begin() + Rel.r_offset,
                                    Rel.getType(Config->IsMips64EL));
static void resolveReloc(InputSectionBase &Sec, RelT &Rel,
                          std::function<void(ResolvedReloc)> Fn) {
   SymbolBody &B = Sec.getFile<ELFT>()->getRelocTargetSym(Rel);
   if (auto *D = dyn_cast<DefinedRegular>(&B)) {
     if (!D->Section)
       return;
     typename ELFT::uint Offset = D->Value;
     if (D->isSection())
       Offset += getAddend<ELFT>(Sec, Rel);
-    Fn({cast<InputSectionBase>(D->Section), Offset});
+    Fn({cast<InputSectionBase>(D->Section), Offset, nullptr});
   } else if (auto *U = dyn_cast<Undefined>(&B)) {
     for (InputSectionBase *Sec : CNamedSections.lookup(U->getName()))
-      Fn({Sec, 0});
+      Fn({Sec, 0, nullptr});
+  } else if (auto *C = dyn_cast<DefinedCommon>(&B)) {
+    // We create synthetic sections later, so InX::Common is null here,
+    // fortunately we do not need it.
+    Fn({nullptr, 0, &B});
   }
 }
 
 // Calls Fn for each section that Sec refers to via relocations.
 template <class ELFT>
 static void forEachSuccessor(InputSection &Sec,
                              std::function<void(ResolvedReloc)> Fn) {
   if (Sec.AreRelocsRela) {
for (unsigned I2 = FirstRelI, N2 = Rels.size(); I2 < N2; ++I2) {
       const RelTy &Rel = Rels[I2];
       if (Rel.r_offset >= PieceEnd)
         break;
       resolveReloc<ELFT>(EH, Rels[I2], [&](ResolvedReloc R) {
         if (!R.Sec || R.Sec == &InputSection::Discarded)
           return;
         if (R.Sec->Flags & SHF_EXECINSTR)
           return;
-        Enqueue({R.Sec, 0});
+        Enqueue({R.Sec, 0, nullptr});
       });
     }
   }
 }
 
 template <class ELFT>
 static void scanEhFrameSection(EhInputSection &EH,
                                std::function<void(ResolvedReloc)> Enqueue) {
template <class ELFT> void elf::markLive() {
   auto Enqueue = [&](ResolvedReloc R) {
     // 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 (R.Sec == &InputSection::Discarded)
       return;
 
+    // Handle common symbols. We put zero as offset to
+    // drop 'symbol unused' flag mark set earlier. We will
+    // check it in createCommonSection() later.
+    if (!R.Sec) {
+      cast<DefinedCommon>(R.Symbol)->Offset = 0;
+      return;
+    }
+
     // We don't gc non alloc sections.
     if (!(R.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>(R.Sec))
       MS->markLiveAt(R.Offset);
 
     if (R.Sec->Live)
       return;
     R.Sec->Live = true;
     // Add input section to the queue.
     if (InputSection *S = dyn_cast<InputSection>(R.Sec))
       Q.push_back(S);
   };
 
-  auto MarkSymbol = [&](const SymbolBody *Sym) {
-    if (auto *D = dyn_cast_or_null<DefinedRegular>(Sym))
+  auto MarkSymbol = [&](SymbolBody *Sym) {
+    if (auto *D = dyn_cast_or_null<DefinedRegular>(Sym)) {
       if (auto *IS = cast_or_null<InputSectionBase>(D->Section))
-        Enqueue({IS, D->Value});
+        Enqueue({IS, D->Value, nullptr});
+    } else if (auto *C = dyn_cast_or_null<DefinedCommon>(Sym)) {
+      Enqueue({nullptr, 0, Sym});
+    }
   };
 
   // Add GC root symbols.
   MarkSymbol(Symtab->find(Config->Entry));
   MarkSymbol(Symtab->find(Config->Init));
   MarkSymbol(Symtab->find(Config->Fini));
   for (StringRef S : Config->Undefined)
     MarkSymbol(Symtab->find(S));
   for (StringRef S : Script->Opt.ReferencedSymbols)
     MarkSymbol(Symtab->find(S));
 
   // Preserve externally-visible symbols if the symbols defined by this
   // file can interrupt other ELF file's symbols at runtime.
-  for (const Symbol *S : Symtab->getSymbols())
+  for (Symbol *S : Symtab->getSymbols())
     if (S->includeInDynsym())
       MarkSymbol(S->body());
 
   // Preserve special sections and those which are specified in linker
   // script KEEP command.
   for (InputSectionBase *Sec : InputSections) {
     // .eh_frame is always marked as live now, but also it can reference to
     // sections that contain personality. We preserve all non-text sections
     // referred by .eh_frame here.
     if (auto *EH = dyn_cast_or_null<EhInputSection>(Sec))
       scanEhFrameSection<ELFT>(*EH, Enqueue);
     if (Sec->Flags & SHF_LINK_ORDER)
       continue;
     if (isReserved<ELFT>(Sec) || Script->shouldKeep(Sec))
-      Enqueue({Sec, 0});
+      Enqueue({Sec, 0, nullptr});
     else if (isValidCIdentifier(Sec->Name)) {
       CNamedSections[Saver.save("__start_" + Sec->Name)].push_back(Sec);
       CNamedSections[Saver.save("__stop_" + Sec->Name)].push_back(Sec);
     }
   }
 
   // Mark all reachable sections.
   while (!Q.empty())
     forEachSuccessor<ELFT>(*Q.pop_back_val(), Enqueue);
 }
 
 template void elf::markLive<ELF32LE>();
 template void elf::markLive<ELF32BE>();
 template void elf::markLive<ELF64LE>();
 template void elf::markLive<ELF64BE>();

ELF/Symbols.cpp

 Undefined::Undefined(StringRefZ Name, bool IsLocal, uint8_t StOther,
                      uint8_t Type)
     : SymbolBody(SymbolBody::UndefinedKind, Name, IsLocal, StOther, Type) {}
 
 DefinedCommon::DefinedCommon(StringRef Name, uint64_t Size, uint32_t Alignment,
                              uint8_t StOther, uint8_t Type)
     : Defined(SymbolBody::DefinedCommonKind, Name, /*IsLocal=*/false, StOther,
               Type),
-      Alignment(Alignment), Size(Size) {}
+      Alignment(Alignment), Size(Size), Offset(Config->GcSections ? -1ULL : 0) {
+}
 
 // If a shared symbol is referred via a copy relocation, its alignment
 // becomes part of the ABI. This function returns a symbol alignment.
 // Because symbols don't have alignment attributes, we need to infer that.
 template <class ELFT> uint32_t SharedSymbol::getAlignment() const {
   SharedFile<ELFT> *File = getFile<ELFT>();
   uint32_t SecAlign = File->getSection(getSym<ELFT>())->sh_addralign;
   uint64_t SymValue = getSym<ELFT>().st_value;

ELF/SyntheticSections.cpp

template <class ELFT> InputSection *elf::createCommonSection() {
   if (Syms.empty())
     return nullptr;
 
   std::stable_sort(Syms.begin(), Syms.end(),
                    [](const DefinedCommon *A, const DefinedCommon *B) {
                      return A->Alignment > B->Alignment;
                    });
 
+  // Allocate space for used common symbols.
   BssSection *Sec = make<BssSection>("COMMON");
   for (DefinedCommon *Sym : Syms)
+    if (Sym->Offset != -1ULL)
       Sym->Offset = Sec->reserveSpace(Sym->Size, Sym->Alignment);
   return Sec;
 }
 
 // Returns an LLD version string.
 static ArrayRef<uint8_t> getVersion() {
   // Check LLD_VERSION first for ease of testing.
   // You can get consitent output by using the environment variable.
   // This is only for testing.

ELF/Writer.cpp

if (auto *IS = dyn_cast<InputSectionBase>(Sec)) {
       IS = cast<InputSectionBase>(Sec);
       // Exclude symbols pointing to garbage-collected sections.
       if (!IS->Live)
         return false;
     }
     if (auto *S = dyn_cast<MergeInputSection>(Sec))
       if (!S->getSectionPiece(D->Value)->Live)
         return false;
+  } else if (auto *D = dyn_cast<DefinedCommon>(&B)) {
+    return D->Offset != -1ULL;
   }
   return true;
 }
 
 // Local symbols are not in the linker's symbol table. This function scans
 // each object file's symbol table to copy local symbols to the output.
 template <class ELFT> void Writer<ELFT>::copyLocalSymbols() {
   if (!InX::SymTab)

test/ELF/common-gc.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %s -o %t
+
+# RUN: ld.lld %t -o %t2
+# RUN: llvm-readobj -sections -symbols %t2 | FileCheck %s --check-prefix=NOGC
+# NOGC: Section {
+# NOGC:   Index:
+# NOGC:   Name: .bss
+# NOGC-NEXT:   Type: SHT_NOBITS
+# NOGC-NEXT:   Flags [
+# NOGC-NEXT:     SHF_ALLOC
+# NOGC-NEXT:     SHF_WRITE
+# NOGC-NEXT:   ]
+# NOGC-NEXT:   Address:
+# NOGC-NEXT:   Offset:
+# NOGC-NEXT:   Size: 8
+# NOGC-NEXT:   Link:
+# NOGC-NEXT:   Info:
+# NOGC-NEXT:   AddressAlignment:
+# NOGC-NEXT:   EntrySize:
+# NOGC-NEXT: }
+# NOGC:     Symbols [
+# NOGC:       Name: bar
+# NOGC:       Name: foo
+
+# RUN: ld.lld -gc-sections %t -o %t1
+# RUN: llvm-readobj -sections -symbols %t1 | FileCheck %s --check-prefix=GC
+# GC: Section {
+# GC:   Index:
+# GC:   Name: .bss
+# GC-NEXT:   Type: SHT_NOBITS
+# GC-NEXT:   Flags [
+# GC-NEXT:     SHF_ALLOC
+# GC-NEXT:     SHF_WRITE
+# GC-NEXT:   ]
+# GC-NEXT:   Address:
+# GC-NEXT:   Offset:
+# GC-NEXT:   Size: 4
+# GC-NEXT:   Link:
+# GC-NEXT:   Info:
+# GC-NEXT:   AddressAlignment:
+# GC-NEXT:   EntrySize:
+# GC-NEXT: }
+# GC:     Symbols [
+# GC-NOT:   Name: bar
+
+.comm foo,4,4
+.comm bar,4,4
+
+.text
+.globl _start
+_start:
+ .quad foo

test/ELF/common-gc2.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %s -o %t
+# RUN: ld.lld -gc-sections --export-dynamic %t -o %t1
+# RUN: llvm-readobj --dyn-symbols %t1 | FileCheck %s
+
+# CHECK:   Name: bar@
+# CHECK:   Name: foo@
+
+.comm foo,4,4
+.comm bar,4,4
+
+.text
+.globl _start
+_start:
+ .quad foo

test/ELF/linkerscript/commons-gc.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+# RUN: echo "SECTIONS { . = SIZEOF_HEADERS; foo = 1; }" > %t.script
+# RUN: ld.lld %t --gc-sections --script %t.script -o %t1
+# RUN: llvm-readobj -symbols %t1 | FileCheck %s
+
+# CHECK:     foo
+# CHECK-NOT: bar
+
+.comm foo,4,4
+.comm bar,4,4