Garbage-collect common symbols.

[ruiu]

Summary

Liveness is usually a notion of input sections, but this patch adds
"liveness" bit to common symbols because they don't belong to any
input section.

This patch is based on https://reviews.llvm.org/D36520

[ruiu]

• Address review comment.

[grimar]

LGTM, thanks !

lld/ELF/Symbols.h

165

Should it be unsigned isLive: 1 ? (for consistency with flags in SymbolBody)

[ruiu]

lld/ELF/Symbols.h

165

No, you don't want to use bitfields unless it is necessary. bool is the standard type to represent a true/false variable.

lld/ELF/MarkLive.cpp

 // There are normally few input sections whose names are valid C
 // identifiers, so we just store a std::vector instead of a multimap.
 static DenseMap<StringRef, std::vector<InputSectionBase *>> CNamedSections;
 
 template <class ELFT, class RelT>
 static void resolveReloc(InputSectionBase &Sec, RelT &Rel,
                          std::function<void(ResolvedReloc)> Fn) {
   SymbolBody &B = Sec.getFile<ELFT>()->getRelocTargetSym(Rel);
+
+  if (auto *Sym = dyn_cast<DefinedCommon>(&B)) {
+    Sym->Live = true;
+    return;
+  }
+
   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});
-  } else if (auto *U = dyn_cast<Undefined>(&B)) {
+    return;
+  }
+
+  if (auto *U = dyn_cast<Undefined>(&B))
     for (InputSectionBase *Sec : CNamedSections.lookup(U->getName()))
       Fn({Sec, 0});
-  }
-}
 
 // 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 (const typename ELFT::Rela &Rel : Sec.template relas<ELFT>())
       resolveReloc<ELFT>(Sec, Rel, Fn);
auto Enqueue = [&](ResolvedReloc R) {
     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});
+      return;
+    }
+    if (auto *S = dyn_cast_or_null<DefinedCommon>(Sym))
+      S->Live = true;
   };
 
   // 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

lld/ELF/Symbols.h

 public:
   DefinedCommon(StringRef N, uint64_t Size, uint32_t Alignment, uint8_t StOther,
                 uint8_t Type);
 
   static bool classof(const SymbolBody *S) {
     return S->kind() == SymbolBody::DefinedCommonKind;
   }
 
-  // The output offset of this common symbol in the output bss. Computed by the
-  // writer.
-  uint64_t Offset;
+  // True if this symbol is not GC'ed. Liveness is usually a notion of
+  // input sections and not of symbols, but since common symbols don't
+  // belong to any input section, their liveness is managed by this bit.
+  bool Live;
 
   // The maximum alignment we have seen for this symbol.
   uint32_t Alignment;
 
+  // The output offset of this common symbol in the output bss.
+  // Computed by the writer.
+  uint64_t Offset;
   uint64_t Size;
 };
 
 // Regular defined symbols read from object file symbol tables.
 class DefinedRegular : public Defined {
 public:
   DefinedRegular(StringRefZ Name, bool IsLocal, uint8_t StOther, uint8_t Type,
                  uint64_t Value, uint64_t Size, SectionBase *Section)

lld/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) {}
+      Live(!Config->GcSections), Alignment(Alignment), Size(Size) {}
 
 // 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;

lld/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 common symbols.
   BssSection *Sec = make<BssSection>("COMMON");
   for (DefinedCommon *Sym : Syms)
+    if (Sym->Live)
       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.

lld/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;
+    return true;
   }
+
+  if (auto *Sym = dyn_cast<DefinedCommon>(&B))
+    return Sym->Live;
   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)
     return;

lld/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: 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-NOT: Name: bar
+
+.comm foo,4,4
+.comm bar,4,4
+
+.text
+.globl _start
+_start:
+ .quad foo

lld/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