[ELF, Bug 26360] - allows undefines that are referenced from garbage collected sections.

[grimar]

Summary

This fixes the https://llvm.org/bugs/show_bug.cgi?id=26360.

If code is unreferenced and is about to be pruned away by --gc-sections, it is allowed to contain references to undefined symbols.

[• rafael]

Is this really desirable?

It looks like an optimization option changing the semantics. What do
you get with gold?

Cheers,
Rafael

[grimar]

In D17252#352805, @rafael wrote:

Is this really desirable?

It looks like an optimization option changing the semantics. What do
you get with gold?

Cheers,
Rafael

Hi Rafael,

gold and ld has the same behavior and allows such undefines, I checked that first before started to implement the patch and it seems logical to me: if section is excluded it is no need to error the undefines from it.
Below is the how I got the sample for test cases and the results of linkage using 3 linkers:

main.cpp:

void undefined_function();

void unreferenced_function() {
  undefined_function();
}

int main(int argc, char **argv) {
  return 0;
}

clang -ffunction-sections main.cpp -S -o main.s
llvm-mc -filetype=obj -triple=x86_64-pc-linux main.s -o main.o

ld -e main --gc-sections main.o -o test
(ok)

gold -e main --gc-sections main.o -o test
(ok)

ld.lld -e main --gc-sections main.o -o test
undefined symbol: _Z18undefined_functionv in main.o

[• rafael]

ELF/Symbols.h

258

Are the semantics the same as CanKeepUndefined? Could you use a single bool?

ELF/Writer.cpp

295

Name is not used.

test/ELF/gc-sections-unref-undef.s

4

Should there be an undefined symbol in the output?

Check one way or the other.

[ruiu]

I think that we don't want it until it is proved that this "feature" is really needed.

It is not hard to imagine that this is _not_ a feature of gold's or GNU ld's. Depending on your internal data structure, this behavior could naturally arise. If the same behavior naturally occurred in our linker, it'd be okay, but this patch intentionally mimic the obscure behavior of the other linkers. I think it needs more justification than "because GNU gold/ld do that" to add this code.

[grimar]

In D17252#353691, @ruiu wrote:

I think that we don't want it until it is proved that this "feature" is really needed.

It is not hard to imagine that this is _not_ a feature of gold's or GNU ld's. Depending on your internal data structure, this behavior could naturally arise. If the same behavior naturally occurred in our linker, it'd be okay, but this patch intentionally mimic the obscure behavior of the other linkers. I think it needs more justification than "because GNU gold/ld do that" to add this code.

It was hard to imagine for me though, I was and still thinking about it as about feature. It is not logical for me to keep dependency on code that is dead itself. Keep errors because of undefines that are actually no longer exist because whole section is GCollected.
Also I found that "It is ok for dead code to reference undefined symbols..." (http://lists.llvm.org/pipermail/llvm-dev/2015-June/086571.html). From my POV it was mentionaed as a expected and desired feature.

[grimar]

Lets see if anyone really needs that first then.

[ed]

• Removed comment --

Sorry! I commented on the wrong code review. Never mind!

ELF/Symbols.h

public:
 
   uintX_t Value;
   const OutputSectionBase<ELFT> &Section;
 };
 
 // Undefined symbol.
 class Undefined : public SymbolBody {
   typedef SymbolBody::Kind Kind;
-  bool CanKeepUndefined;
+  bool Optional;
+  // If it was ever seen in live sections.
+  bool Live = false;
 
 protected:
   Undefined(Kind K, StringRef N, bool IsWeak, uint8_t Visibility, bool IsTls);
 
 public:
-  Undefined(StringRef N, bool IsWeak, uint8_t Visibility,
-            bool CanKeepUndefined);
+  Undefined(StringRef N, bool IsWeak, uint8_t Visibility, bool Opt);
 
   static bool classof(const SymbolBody *S) { return S->isUndefined(); }
 
-  bool canKeepUndefined() const { return CanKeepUndefined; }
+  bool canKeepUndefined() const {
+    return Optional || (Config->GcSections && !Live);
+  }
+  void setLive() { Live = true; }
 };
 
 template <class ELFT> class UndefinedElf : public Undefined {
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Sym Elf_Sym;
 
 public:
   UndefinedElf(StringRef N, const Elf_Sym &Sym);
   const Elf_Sym &Sym;

ELF/Symbols.cpp

 
 bool DefinedBitcode::classof(const SymbolBody *S) {
   return S->kind() == DefinedBitcodeKind;
 }
 
 Undefined::Undefined(SymbolBody::Kind K, StringRef N, bool IsWeak,
                      uint8_t Visibility, bool IsTls)
     : SymbolBody(K, N, IsWeak, Visibility, IsTls, /*IsFunction*/ false),
-      CanKeepUndefined(false) {}
+      Optional(false) {}
 
-Undefined::Undefined(StringRef N, bool IsWeak, uint8_t Visibility,
-                     bool CanKeepUndefined)
+Undefined::Undefined(StringRef N, bool IsWeak, uint8_t Visibility, bool Opt)
     : Undefined(SymbolBody::UndefinedKind, N, IsWeak, Visibility,
                 /*IsTls*/ false) {
-  this->CanKeepUndefined = CanKeepUndefined;
+  this->Optional = Opt;
 }
 
 template <typename ELFT>
 UndefinedElf<ELFT>::UndefinedElf(StringRef N, const Elf_Sym &Sym)
     : Undefined(SymbolBody::UndefinedElfKind, N,
                 Sym.getBinding() == llvm::ELF::STB_WEAK, Sym.getVisibility(),
                 Sym.getType() == llvm::ELF::STT_TLS),
       Sym(Sym) {}

ELF/Writer.cpp

void Writer<ELFT>::scanRelocs(
     iterator_range<const Elf_Rel_Impl<ELFT, isRela> *> Rels) {
   typedef Elf_Rel_Impl<ELFT, isRela> RelType;
   const ObjectFile<ELFT> &File = *C.getFile();
   for (const RelType &RI : Rels) {
     uint32_t SymIndex = RI.getSymbol(Config->Mips64EL);
     SymbolBody *Body = File.getSymbolBody(SymIndex);
     uint32_t Type = RI.getType(Config->Mips64EL);
 
+    auto Name = C.getSectionName();
+    if (Body && Body->isUndefined()) {
+      if (auto *U = dyn_cast<Undefined>(Body->repl()))
+        U->setLive();
+
+      // Set "used" bit for --as-needed.
+      if (!Body->isWeak())
+        if (auto *S = dyn_cast<SharedSymbol<ELFT>>(Body->repl()))
+          S->File->IsUsed = true;
+    }
+
     // Ignore "hint" relocation because it is for optional code optimization.
     if (Target->isHintRel(Type))
       continue;
 
     if (Target->isGotRelative(Type))
       HasGotOffRel = true;
 
-    // Set "used" bit for --as-needed.
-    if (Body && Body->isUndefined() && !Body->isWeak())
-      if (auto *S = dyn_cast<SharedSymbol<ELFT>>(Body->repl()))
-        S->File->IsUsed = true;
-
     if (Body)
       Body = Body->repl();
 
     if (handleTlsRelocation<ELFT>(Type, Body, C, RI))
       continue;
 
     if (Target->needsDynRelative(Type))
       Out<ELFT>::RelaDyn->addReloc({Target->RelativeRel, &C, RI.r_offset, true,

test/ELF/gc-sections-unref-undef.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+# RUN: ld.lld %t -o %t.out -e main --gc-sections
+# RUN: llvm-readobj %t.out > /dev/null
+
+## Don't allow undefines if GC is not enabled
+# RUN: not ld.lld %t -o %t.out -e main 2>&1 | FileCheck %s
+# CHECK: undefined symbol: _UNDEFINED
+
+.text
+.section .text._unreferenced_function,"ax",@progbits
+.globl _unreferenced_function
+.type  _unreferenced_function,@function
+_unreferenced_function:
+ callq _UNDEFINED
+
+.section .text._function,"ax",@progbits
+.globl _function
+.type  _function,@function
+_function:
+
+.section .text.main,"ax",@progbits
+.globl main
+.type  main,@function
+main:  
+ callq _function

test/ELF/gc-sections-unref-undef2.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+# RUN: not ld.lld %t -o %t.out -e main --gc-sections 2>&1 | FileCheck %s
+# CHECK: undefined symbol: _UNDEFINED
+
+## This checks that if there are section with unreferenced
+## undefined and the section where it is used, then
+## we still can see the error.
+.text
+.section .text._unreferenced_function,"ax",@progbits
+.globl _unreferenced_function
+.type  _unreferenced_function,@function
+_unreferenced_function:
+ callq _UNDEFINED
+
+.section .text._function,"ax",@progbits
+.globl _function
+.type  _function,@function
+_function:
+ callq _UNDEFINED
+
+.section .text.main,"ax",@progbits
+.globl main
+.type  main,@function
+main:  
+ callq _function