[LLD][ELF] Implement --discard-* for cases when -r or --emit-relocs are used.

[ikudrin]

Summary

When discarding local symbols with --discard-all or --discard-locals, the ones which are used in relocations should be preserved. LLD used the simplest approach and just ignored those switches when -r or --emit-relocs was specified.

The patch implements handling the --discard-* switches for the cases when relocations are kept by identifying used local symbols and allowing removing only unused ones. This makes the behavior of LLD compatible with GNU linkers.

[MaskRay]

This makes the behavior of LLD compatible with GNU linkers.

I have verified the patch seems to match the behavior, but can you describe a bit why you need such a behavior?

For -shared --discard-locals --emit-relocs, the patch strips .Lunused . However, .L temporary symbols are usually already discarded by the assembler.

For -shared --discard-all --emit-relocs, this patch appears to be a bug fix. Previously we discard all local symbols.

lld/test/ELF/dont-discard-used-locals.s

1 ↗

(On Diff #256312)

Rename this to discard-locals-* to improve discoverability.

8 ↗

(On Diff #256312)

For the option name, prefer the double-dash form unless the single dash form is prevailing (e.g. -pie -shared )

13 ↗

(On Diff #256312)

No need to use --just-symbol-name. FileCheck allows you to omit the leading t T

33 ↗

(On Diff #256312)

Add -NEXT: if applicable

[MaskRay]

lld/test/ELF/dont-discard-used-locals.s

6 ↗

(On Diff #256312)

llvm-mc -filetype=obj -triple=x86_64 -save-temp-labels %s -o %t.o

54 ↗

(On Diff #256312)

Delete trailing empty line

[ikudrin]

Thank you @MaskRay for reviewing this!

• Renamed the test to discard-locals-preserve-used.s
• Reformulated the description of the test.
• Updated the test according to the review comments.

[ikudrin]

In D77807#1973831, @MaskRay wrote:

This makes the behavior of LLD compatible with GNU linkers.

I have verified the patch seems to match the behavior, but can you describe a bit why you need such a behavior?

Our customers noticed the difference when tried to switch from ld.bfd to lld. They use --discard-all -r and want only useful symbols to survive.

For -shared --discard-all --emit-relocs, this patch appears to be a bug fix. Previously we discard all local symbols.

Thanks. I forgot about that because that was not my direct intention. Maybe it is worth mentioning in the patch's description.

[grimar]

lld/ELF/Writer.cpp

565

Perhaps move it inside copyLocalSymbols()?

At least because this work can be avoided when !in.symTab:

template <class ELFT> void Writer<ELFT>::copyLocalSymbols() {
  if (!in.symTab)
    return;
...

649

I think it is better to update the comment, not remove it.

657

Symbol::used is initialized to something in the constructor of the Symbol:

Symbol(Kind k, InputFile *file, StringRefZ name, uint8_t binding,
       uint8_t stOther, uint8_t type)
    :  .... used(!config->gcSections), ....

LLD usually tries to initialize variables to a proper value from the begining.
Given all above I think more consistent would to change the initializer condition right there.
Then you should be able to remove this loop.

lld/test/ELF/discard-locals-preserve-used.s

5

Usually REQURES is placed on the first line.

9

DISCARD_NONE -> DISCARD-NONE here and below.
(We don't use underbars in check prefixes in LLD tests)

[ikudrin]

• Addressed comments by @grimar. Thanks!

[grimar]

I'd suggest to wait to hear what other reviewers think about the latest changes and my suggestions in general before continuing.

lld/ELF/Symbols.h

241 ↗

(On Diff #256544)

So, when !gcSections and the symbol is local, it bow sets used to false,
though the previous code set it to true in this case.

Seems this doesn't break anything in the current implementation,
though I wonder if we might want to have config->copyRelocs involved in the condition.
It perhaps would be a bit cleaner way to work with this flag.

Also, perhaps it can be initialized in the constructor body now, since the condition is not trivial.

nit: You can probably use isLocal() instead of checking the binding field directly.

261 ↗

(On Diff #256544)

The comment needs an update.

[ikudrin]

• Extended the comment for Symbol::used.

lld/ELF/Symbols.h

241 ↗

(On Diff #256544)

Seems this doesn't break anything in the current implementation, though I wonder if we might want to have config->copyRelocs involved in the condition. It perhaps would be a bit cleaner way to work with this flag.

If we add config->copyRelocs we will also have to add config->discard and the expression will easily become overcomplicated. Long complex expressions are usually hard to understand, so I would prefer this to be as short and simple as possible.

Also, perhaps it can be initialized in the constructor body now, since the condition is not trivial.

As used is a bit field, moving the initialization into the body might confuse the optimizer.

nit: You can probably use isLocal() instead of checking the binding field directly.

Using a method that depends on the state of a class in the member initializer list makes the constructor fragile. Better to avoid.

[MaskRay]

In D77807#1974123, @grimar wrote:

I'd suggest to wait to hear what other reviewers think about the latest changes and my suggestions in general before continuing.

Honestly I am wondering whether a relocation scanning is justified. The only problem I can think of with the current conservative choice for --discard-locals + (-r | --emit-relocs) is that the output is larger. The output contains some otherwise unneeded STB_LOCAL symbols. Note, STB_LOCAL symbols not used by a relocation don't interfere with linking.

For -shared --discard-locals --emit-relocs, the patch strips .Lunused . However, .L temporary symbols are usually already discarded by the assembler.

.L in object files is uncommon so we probably should not worry much about the additional symbols lld retains but GNU linkers discard.

For -shared --discard-all --emit-relocs, this patch appears to be a bug fix. Previously we discard all local symbols.

This discards local symbols as well. My question is why we have these unreferenced local symbols in object files and why we need to save .symtab space for them.

An assembler can convert a local symbol reference to a relocation referencing a STT_SECTION symbol, or resolve the fixup at assembly time. If the intention is to discard the unreferenced local symbols, a better way may be to not generate the local symbols in the object files. Alternatively, generate .L temporary labels which are a special kind of local symbols which usually don't survive in the object file.

At the minimum, the --discard-all --emit-relocs bug fix is still useful. For the additional test, I think we should just replace the existing discard-locals.s with the contents from discard-locals-preserve-used.s

[ikudrin]

In D77807#1974679, @MaskRay wrote:

Honestly I am wondering whether a relocation scanning is justified. The only problem I can think of with the current conservative choice for --discard-locals + (-r | --emit-relocs) is that the output is larger. The output contains some otherwise unneeded STB_LOCAL symbols. Note, STB_LOCAL symbols not used by a relocation don't interfere with linking.

In our case, the output is analyzed with additional tools and these unneeded symbols slow down the process significantly.

This discards local symbols as well. My question is why we have these unreferenced local symbols in object files and why we need to save .symtab space for them.

An assembler can convert a local symbol reference to a relocation referencing a STT_SECTION symbol, or resolve the fixup at assembly time. If the intention is to discard the unreferenced local symbols, a better way may be to not generate the local symbols in the object files. Alternatively, generate .L temporary labels which are a special kind of local symbols which usually don't survive in the object file.

Here is a reduced example of the initial problem I am solving in this patch:

$ cat a.c
static int foo = 0;
int bar() { return foo; }
$ clang -c a.c
$ readelf -rs a.o
Relocation section '.rela.text' at offset 0x150 contains 1 entry:
  Offset          Info           Type           Sym. Value    Sym. Name + Addend
000000000007  00040000000b R_X86_64_32S      0000000000000000 .bss + 0
...
Symbol table '.symtab' contains 6 entries:
   Num:    Value          Size Type    Bind   Vis      Ndx Name
...
     2: 0000000000000000     4 OBJECT  LOCAL  DEFAULT    4 foo
...
$ ld.bfd -r a.o --discard-all -o ar.o && nm ar.o
0000000000000000 T bar
$ ld.lld -r a.o --discard-all -o ar.o && nm ar.o
0000000000000000 T bar
0000000000000000 b foo

[ikudrin]

Ping.

[MaskRay]

Implement --discard-* for cases when -r or --emit-relocs are used.

The behavior difference should only be about --discard-all + {-r,--emit-relocs}.

For --discard-locals + {-r,--emit-relocs} (.Lunused is stripped in GNU ld), I am not sure we want to adapt GNU ld's rule.

For --discard-all + {-r,--emit-relocs} (the main purpose of this patch, I think. .Lunused and unused are stripped in GNU ld), I am still uncomfortable with the following change:

- used(!config->gcSections),
+ used(!config->gcSections && binding != llvm::ELF::STB_LOCAL),

and the relocation scanning behavior guarded by the subtle condition:

if (config->copyRelocs && config->discard != DiscardPolicy::None)
  markUsedLocalSymbols<ELFT>();

The --emit-relocs --discard-all bugfix is correct and we should fix that. I took this opportunity to improve test coverage a bit. Created D78389.

[ikudrin]

In D77807#1989361, @MaskRay wrote:

Implement --discard-* for cases when -r or --emit-relocs are used.

The behavior difference should only be about --discard-all + {-r,--emit-relocs}.

For --discard-locals + {-r,--emit-relocs} (.Lunused is stripped in GNU ld), I am not sure we want to adapt GNU ld's rule.

And what should we do instead? Note that without -r or --emit-relocs our behavior matches GNU linkers'.

For --discard-all + {-r,--emit-relocs} (the main purpose of this patch, I think. .Lunused and unused are stripped in GNU ld), I am still uncomfortable with the following change:

- used(!config->gcSections),
+ used(!config->gcSections && binding != llvm::ELF::STB_LOCAL),

Do you suggest to extend the expression and include config->copyRelocs into it, or revert this change and stick with my initial version, which was more localized?

and the relocation scanning behavior guarded by the subtle condition:

if (config->copyRelocs && config->discard != DiscardPolicy::None)
  markUsedLocalSymbols<ELFT>();

The condition is here just to avoid unneeded work. Any suggestions on how to improve that?

[MaskRay]

Can you rebase after D78389? The improved test coverage should help us understand the impact of the used change now.

For tests, you can just modify emit-relocs-discard-locals.s

[MaskRay]

lld/test/ELF/discard-locals-preserve-used.s

40

NOT patterns rely on the symbol order. If the symbol order is disrupted, NOT patterns may get stale and don't actually test the (in)existence.

The --check-prefixes approach requires update when the symbol order is changed, but at least it will not miss such updates.

[ikudrin]

• Rebased to the tip.
• Moved the initialization of the field used back to markUsedLocalSymbols(). This makes the handling more local. Made a corresponding note in the comment for that field.
• Dropped the own test in favor of updating tests from D78389.

[MaskRay]

Thanks for the update. The member initializer of used which I was not comfortable is now removed. The code looks pretty good now.

lld/ELF/Writer.cpp

653

Add a comment that when --gc-sections is not specified, this function is needed to set the used bits

674

referenced by relocations from live sections.

728

We can also add && !config->gcSections here to avoid work.

Now it is clear why we need --gc-sections tests in *-discard-locals. Symbol::used is always true when --no-gc-sections. When --gc-sections is specified, MarkLive sets used correctly, another relocation scanning (markUsedLocalSymbols) will be unnecessary.

[ikudrin]

• Added/improved comments.
• Added a condition to not execute the scanning if --gc-sections is specified.
• Added testing of the --emit-relocs --discard-all --gc-sections case.

[MaskRay]

lld/test/ELF/emit-relocs-discard-locals.s

27 ↗

(On Diff #259502)

I think you can still combine the two chunks of CHECK lines.

DICARD-LOCALS-NEXT: for the common part.
DISCARD-LOCALS-NOGC for the additional lines by --no-gc-sections.

It makes the diff stand out.

[ikudrin]

• Combined GC/NOGC checks in the test.

lld/ELF/Writer.cpp

728

I've added the check and the comment to markUsedLocalSymbols<ELFT>().

lld/test/ELF/emit-relocs-discard-locals.s

27 ↗

(On Diff #259502)

OK, combining gc/nogc variants together looks acceptable. Firstly, I tried to combine all four variants and the result was unreadable, that is why I split them.

[MaskRay]

Thanks!

lld/ELF/Driver.cpp

static bool isOutputFormatBinary(opt::InputArgList &args) {
   if (s == "binary")
     return true;
   if (!s.startswith("elf"))
     error("unknown --oformat value: " + s);
   return false;
 }
 
 static DiscardPolicy getDiscard(opt::InputArgList &args) {
-  if (args.hasArg(OPT_relocatable))
-    return DiscardPolicy::None;
-
   auto *arg =
       args.getLastArg(OPT_discard_all, OPT_discard_locals, OPT_discard_none);
   if (!arg)
     return DiscardPolicy::Default;
   if (arg->getOption().getID() == OPT_discard_all)
     return DiscardPolicy::All;
   if (arg->getOption().getID() == OPT_discard_locals)
     return DiscardPolicy::Locals;

lld/ELF/Writer.cpp

public:
   Writer() : buffer(errorHandler().outputBuffer) {}
   using Elf_Shdr = typename ELFT::Shdr;
   using Elf_Ehdr = typename ELFT::Ehdr;
   using Elf_Phdr = typename ELFT::Phdr;
 
   void run();
 
 private:
+  void markUsedLocalSymbols();
   void copyLocalSymbols();
   void addSectionSymbols();
   void forEachRelSec(llvm::function_ref<void(InputSectionBase &)> fn);
   void sortSections();
   void resolveShfLinkOrder();
   void finalizeAddressDependentContent();
   void optimizeBasicBlockJumps();
   void sortInputSections();
if (in.symTabShndx)
     add(in.symTabShndx);
   add(in.shStrTab);
   if (in.strTab)
     add(in.strTab);
 }
 
 // The main function of the writer.
 template <class ELFT> void Writer<ELFT>::run() {
-  if (config->discard != DiscardPolicy::All)
-    copyLocalSymbols();
+  if (config->copyRelocs && config->discard != DiscardPolicy::None)
+    markUsedLocalSymbols();
 
   if (config->copyRelocs)
     addSectionSymbols();
 
   // Now that we have a complete set of output sections. This function
   // completes section contents. For example, we need to add strings
   // to the string table, and add entries to .got and .plt.
   // finalizeSections does that.
template <class ELFT> void Writer<ELFT>::run() {
   writeBuildId();
   if (errorCount())
     return;
 
   if (auto e = buffer->commit())
     error("failed to write to the output file: " + toString(std::move(e)));
 }
 
+template <class ELFT, class RelTy>
+static void markUsedLocalSymbolsImpl(ObjFile<ELFT> *file,
+                                     llvm::ArrayRef<RelTy> rels) {
+  for (const RelTy &rel : rels) {
+    Symbol &sym = file->getRelocTargetSym(rel);
+    if (sym.isLocal())
+      sym.used = true;
+  }
+}
+
+template <class ELFT> void Writer<ELFT>::markUsedLocalSymbols() {
+  for (InputFile *file : objectFiles) {
+    ObjFile<ELFT> *f = cast<ObjFile<ELFT>>(file);
+    for (Symbol *b : f->getLocalSymbols())
+      b->used = false;
+    for (InputSectionBase *s : f->getSections()) {
+      InputSection *isec = dyn_cast_or_null<InputSection>(s);
+      if (!isec)
+        continue;
+      if (isec->type == SHT_REL)
+        markUsedLocalSymbolsImpl(f, isec->getDataAs<typename ELFT::Rel>());
+      else if (isec->type == SHT_RELA)
+        markUsedLocalSymbolsImpl(f, isec->getDataAs<typename ELFT::Rela>());
+    }
+  }
+}
+
 static bool shouldKeepInSymtab(const Defined &sym) {
   if (sym.isSection())
     return false;
 
   if (config->discard == DiscardPolicy::None)
     return true;
 
-  // If -emit-reloc is given, all symbols including local ones need to be
-  // copied because they may be referenced by relocations.
-  if (config->emitRelocs)
+  if (config->copyRelocs && sym.used)
     return true;
 
+  if (config->discard == DiscardPolicy::All)
+    return false;
+
   // In ELF assembly .L symbols are normally discarded by the assembler.
   // If the assembler fails to do so, the linker discards them if
   // * --discard-locals is used.
   // * The symbol is in a SHF_MERGE section, which is normally the reason for
   //   the assembler keeping the .L symbol.
   StringRef name = sym.getName();
   bool isLocal = name.startswith(".L") || name.empty();
   if (!isLocal)
static bool includeInSymtab(const Symbol &b) {
   return b.used;
 }
 
 // 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 (!in.symTab)
     return;
   for (InputFile *file : objectFiles) {
     ObjFile<ELFT> *f = cast<ObjFile<ELFT>>(file);
     for (Symbol *b : f->getLocalSymbols()) {
       if (!b->isLocal())
         fatal(toString(f) +
               ": broken object: getLocalSymbols returns a non-local symbol");
       auto *dr = dyn_cast<Defined>(b);
 
       // No reason to keep local undefined symbol in symtab.

lld/test/ELF/discard-locals-preserve-used.s

+## This test checks that --discard-all and --discard-locals, when used with -r
+## or --emit-relocs, preserve local symbols which are used in relocations and
+## remove only unreferenced ones.
+
+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64 -save-temp-labels %s -o %t
+
+# RUN: ld.lld --discard-none -shared --emit-relocs %t -o - | \
+# RUN:   llvm-nm - | FileCheck %s --check-prefix=DISCARD_NONE
+
+# RUN: ld.lld --discard-locals -shared --emit-relocs %t -o - | \
+# RUN:   llvm-nm - | FileCheck %s --check-prefix=DISCARD_LOCALS
+
+# RUN: ld.lld --discard-all -shared --emit-relocs %t -o - | \
+# RUN:   llvm-nm - | FileCheck %s --check-prefix=DISCARD_ALL
+
+# RUN: ld.lld --discard-none -r %t -o - | \
+# RUN:   llvm-nm - | FileCheck %s --check-prefix=DISCARD_NONE
+
+# RUN: ld.lld --discard-locals -r %t -o - | \
+# RUN:   llvm-nm - | FileCheck %s --check-prefix=DISCARD_LOCALS
+
+# RUN: ld.lld --discard-all -r %t -o - | \
+# RUN:   llvm-nm - | FileCheck %s --check-prefix=DISCARD_ALL
+
+# DISCARD_NONE:      .LUnused
+# DISCARD_NONE-NEXT: .LUsed
+# DISCARD_NONE-NEXT: Unused
+# DISCARD_NONE-NEXT: Used
+
+# DISCARD_LOCALS-NOT:  .LUnused
+# DISCARD_LOCALS:      .LUsed
+# DISCARD_LOCALS-NEXT: Unused
+# DISCARD_LOCALS-NEXT: Used
+
+# DISCARD_ALL-NOT:  .LUnused
+# DISCARD_ALL:      .LUsed
+# DISCARD_ALL-NOT:  Unused
+# DISCARD_ALL-NEXT: Used
+
+.text
+    jmp .LUsed@PLT
+    call Used@PLT
+.LUnused:
+Unused:
+.LUsed:
+Used: