[ELF] --icf: do not fold preemptible symbols

[MaskRay]

Summary

Fixes PR44124.

A preemptible symbol may refer to a different definition at runtime.
When comparing a pair of relocations, if they refer to different
symbols, and either symbol is preemptible, the two containing sections
should be considered different.

gold has a similar rule https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;a=commit;h=ce97fa81e0c46d216b80b143ad8c02fff6906fef

[MaskRay]

lld/ELF/ICF.cpp

262

I may place a comment that replicates the patch summary here

When comparing a pair of relocations, if they refer to different symbols, and either symbol is preemptible, the containing sections should be considered different.

If you have a wording suggestion, please tell me:)

[grimar]

Generally LG.

lld/ELF/Symbols.h

557

use sym for consistency with the definition of maybeWarnUnorderableSymbol?

lld/test/ELF/icf-preemptible.s

20

Not sure LEAF and NONLEAF are clear to me.
I have no suggestions about how to name them better though.
It seems a bit hard to invent good names when checks are mixed.
If they were separated you could use just "DSO" and "EXE" probably.
May be others will have any ideas.

[peter.smith]

lld/ELF/ICF.cpp

262

Only addition I'd make is a brief comment on why they should be different.

When comparing a pair of relocations, if they refer to different symbols, and either symbol is preemptible, the containing sections should be considered different. This is because even if the sections are identical in this DSO, they may not be after preemption.

lld/test/ELF/icf-preemptible.s

20

I'm clear about the meaning of LEAF and NONLEAF, although I suppose we could add a comment to make it clearer. Having said that it would be worth exploring George's suggestion to have a DSO and EXE case, it would be easier to map to the definitions of f and g as well.

[MaskRay]

Address review comments

[grimar]

LGTM

[ruiu]

lld/ELF/Driver.cpp

1992–1996

This seems like a logic that should belong to ICF, so maybe you can move this to doICF, so that this logic is hidden from others?

lld/ELF/Driver.cpp

for (BaseCommand *base : script->sectionCommands)
     if (auto *sec = dyn_cast<OutputSection>(base))
       sec->finalizeInputSections();
   llvm::erase_if(inputSections,
                  [](InputSectionBase *s) { return isa<MergeInputSection>(s); });
 
   // Two input sections with different output sections should not be folded.
   // ICF runs after processSectionCommands() so that we know the output sections.
   if (config->icf != ICFLevel::None) {
+    // Compute isPreemptible early to be used by ICF. We may add more symbols
+    // later, so this loop cannot be merged with the later computeIsPreemptible
+    // pass which is used by scanRelocations().
+    for (Symbol *sym : symtab->symbols())
+      sym->isPreemptible = computeIsPreemptible(*sym);
     findKeepUniqueSections<ELFT>(args);
     doIcf<ELFT>();
   }
 
   // Read the callgraph now that we know what was gced or icfed
   if (config->callGraphProfileSort) {
     if (auto *arg = args.getLastArg(OPT_call_graph_ordering_file))
       if (Optional<MemoryBufferRef> buffer = readFile(arg->getValue()))

lld/ELF/ICF.cpp

for (size_t i = 0; i < ra.size(); ++i) {
     auto *da = dyn_cast<Defined>(&sa);
     auto *db = dyn_cast<Defined>(&sb);
 
     // Placeholder symbols generated by linker scripts look the same now but
     // may have different values later.
     if (!da || !db || da->scriptDefined || db->scriptDefined)
       return false;
 
+    // When comparing a pair of relocations, if they refer to different symbols,
+    // and either symbol is preemptible, the containing sections should be
+    // considered different. This is because even if the sections are identical
+    // in this DSO, they may not be after preemption.
+    if (da->isPreemptible || db->isPreemptible)
+      return false;
+
     // Relocations referring to absolute symbols are constant-equal if their
     // values are equal.
     if (!da->section && !db->section && da->value + addA == db->value + addB)
       continue;
     if (!da->section || !db->section)
       return false;
 
     if (da->section->kind() != db->section->kind())

lld/ELF/Symbols.h

void Symbol::replace(const Symbol &newSym) {
 
   // Print out a log message if --trace-symbol was specified.
   // This is for debugging.
   if (traced)
     printTraceSymbol(this);
 }
 
 void maybeWarnUnorderableSymbol(const Symbol *sym);
+bool computeIsPreemptible(const Symbol &sym);
+
 } // namespace elf
 } // namespace lld
 
 #endif

lld/ELF/Symbols.cpp

void maybeWarnUnorderableSymbol(const Symbol *sym) {
   else if (d && !d->section)
     report(": unable to order absolute symbol: ");
   else if (d && isa<OutputSection>(d->section))
     report(": unable to order synthetic symbol: ");
   else if (d && !d->section->repl->isLive())
     report(": unable to order discarded symbol: ");
 }
 
+// Returns true if a symbol can be replaced at load-time by a symbol
+// with the same name defined in other ELF executable or DSO.
+bool computeIsPreemptible(const Symbol &sym) {
+  assert(!sym.isLocal());
+
+  // Only symbols with default visibility that appear in dynsym can be
+  // preempted. Symbols with protected visibility cannot be preempted.
+  if (!sym.includeInDynsym() || sym.visibility != STV_DEFAULT)
+    return false;
+
+  // At this point copy relocations have not been created yet, so any
+  // symbol that is not defined locally is preemptible.
+  if (!sym.isDefined())
+    return true;
+
+  if (!config->shared)
+    return false;
+
+  // If the dynamic list is present, it specifies preemptable symbols in a DSO.
+  if (config->hasDynamicList)
+    return sym.inDynamicList;
+
+  // -Bsymbolic means that definitions are not preempted.
+  if (config->bsymbolic || (config->bsymbolicFunctions && sym.isFunc()))
+    return false;
+  return true;
+}
+
 static uint8_t getMinVisibility(uint8_t va, uint8_t vb) {
   if (va == STV_DEFAULT)
     return vb;
   if (vb == STV_DEFAULT)
     return va;
   return std::min(va, vb);
 }
 

lld/ELF/Writer.cpp

for (InputSectionBase *s : llvm::reverse(inputSections)) {
     // remove it from corresponding input section description of output section.
     for (BaseCommand *b : os->sectionCommands)
       if (auto *isd = dyn_cast<InputSectionDescription>(b))
         llvm::erase_if(isd->sections,
                        [=](InputSection *isec) { return isec == ss; });
   }
 }
 
-// Returns true if a symbol can be replaced at load-time by a symbol
-// with the same name defined in other ELF executable or DSO.
-static bool computeIsPreemptible(const Symbol &b) {
-  assert(!b.isLocal());
-
-  // Only symbols that appear in dynsym can be preempted.
-  if (!b.includeInDynsym())
-    return false;
-
-  // Only default visibility symbols can be preempted.
-  if (b.visibility != STV_DEFAULT)
-    return false;
-
-  // At this point copy relocations have not been created yet, so any
-  // symbol that is not defined locally is preemptible.
-  if (!b.isDefined())
-    return true;
-
-  if (!config->shared)
-    return false;
-
-  // If the dynamic list is present, it specifies preemptable symbols in a DSO.
-  if (config->hasDynamicList)
-    return b.inDynamicList;
-
-  // -Bsymbolic means that definitions are not preempted.
-  if (config->bsymbolic || (config->bsymbolicFunctions && b.isFunc()))
-    return false;
-  return true;
-}
-
 // Create output section objects and add them to OutputSections.
 template <class ELFT> void Writer<ELFT>::finalizeSections() {
   Out::preinitArray = findSection(".preinit_array");
   Out::initArray = findSection(".init_array");
   Out::finiArray = findSection(".fini_array");
 
   // The linker needs to define SECNAME_start, SECNAME_end and SECNAME_stop
   // symbols for sections, so that the runtime can get the start and end

lld/test/ELF/icf-preemptible.s

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64 %s -o %t.o
+# RUN: ld.lld -pie %t.o --icf=all --print-icf-sections -o /dev/null | \
+# RUN:   FileCheck --check-prefixes=EXE %s
+
+# RUN: ld.lld -shared %t.o --icf=all --print-icf-sections -o /dev/null | \
+# RUN:   FileCheck --check-prefix=DSO %s --implicit-check-not=removing
+
+## Definitions are non-preemptible in an executable.
+# EXE:      selected section {{.*}}:(.text.h1)
+# EXE-NEXT:   removing identical section {{.*}}:(.text.h2)
+# EXE-NEXT:   removing identical section {{.*}}:(.text.h3)
+# EXE:      selected section {{.*}}:(.text.f1)
+# EXE-NEXT:   removing identical section {{.*}}:(.text.f2)
+# EXE-NEXT: selected section {{.*}}:(.text.g1)
+# EXE:        removing identical section {{.*}}:(.text.g2)
+# EXE-NEXT:   removing identical section {{.*}}:(.text.g3)
+
+## Definitions are preemptible in a DSO. Only leaf functions can be folded.
+# DSO:      selected section {{.*}}:(.text.f1)
+# DSO-NEXT:   removing identical section {{.*}}:(.text.f2)
+# DSO-NEXT: selected section {{.*}}:(.text.g1)
+# DSO-NEXT:   removing identical section {{.*}}:(.text.g3)
+
+.globl f1, f2, g1, g2, g3
+
+.section .text.f1
+f1: ret
+.section .text.f2
+f2: ret
+
+## In -shared mode, .text.g1 and .text.g2 cannot be folded because f1 and f2 are
+## preemptible and may refer to different functions at runtime.
+.section .text.g1
+g1: jmp f1@plt
+.section .text.g2
+g2: jmp f2@plt
+.section .text.g3
+g3: jmp f1@plt
+
+## In -shared mode, the sections below cannot be folded because g1, g2 and g3
+## are preemptible and may refer to different functions at runtime.
+.section .text.h1
+jmp g1@plt
+.section .text.h2
+jmp g2@plt
+.section .text.h3
+jmp g3@plt