ELF: Add libcall symbols to the link when LTO is being used.

[pcc]

Summary

If any of our inputs are bitcode files, the LTO code generator may create
references to certain library functions that might not be explicit in the
bitcode file's symbol table. If any of those library functions are defined
in a bitcode file in an archive member, we need to arrange to use LTO to
compile those archive members by adding them to the link beforehand.

Depends on D50016

[ruiu]

It might be a silly question, but are these functions (e.g. udivhi3 or mulxf3) are functions in static archives? It seems like calling such small functions have relatively large overhead, which appears contrary to the aim of LTO. I'm wondering why LTO creates new function calls to them. Don't you want to inline these functions using LTO?

[pcc]

In D50017#1181200, @ruiu wrote:

It might be a silly question, but are these functions (e.g. udivhi3 or mulxf3) are functions in static archives?

Yes, they're typically in something like libgcc.a or libcompiler-rt.a, and in principle that archive could have been compiled with LTO. Something that's more likely to happen is illustrated by my test case: a program defines a function that's intended to be defined by the user, such as __cyg_profile_func_enter_bare, compiles it with LTO (as with the rest of the program) and links it using an archive.

It seems like calling such small functions have relatively large overhead, which appears contrary to the aim of LTO. I'm wondering why LTO creates new function calls to them. Don't you want to inline these functions using LTO?

In this case we cannot inline the functions because the IR does not reference them explicitly. The code generator creates the references to them very late (i.e. after inlining) to compile certain mathematical operations (such operations may themselves have been created as a result of inlining followed by other optimizations).

[ruiu]

I'm wondering if we have to keep the list of symbols that could be added as undefined symbols by LTO. If LTO adds new undefined symbol, we always have to resolve them whatever they are, no?

[pcc]

In D50017#1181305, @ruiu wrote:

I'm wondering if we have to keep the list of symbols that could be added as undefined symbols by LTO. If LTO adds new undefined symbol, we always have to resolve them whatever they are, no?

The code generator should, in principle, never be adding a new undefined symbol during LTO that the linker doesn't already know about either via the bitcode symbol table or the list of libcall functions. It is a bug for it to add any other undefined symbols. We need the list of undefined symbols from libcalls for the same reason why we need the list of undefined symbols from bitcode symbol tables: to make sure that we've added everything we need to the link before starting LTO. To do otherwise creates the possibility of needing to do LTO multiple times (once for the initial set of bitcode files and again (possibly multiple times) for the expanded set of bitcode files after discovering the undefined references), which could lead to subtle bugs if not done correctly, complicates the implementation of LTO and could make it (even) slower.

[ruiu]

Ah, I misunderstood that the new code was added after addCombinedLTOObject, but the new code is actually before the call of that function. Now the code makes more sense.

Have you considered always adding these symbols as undefined symbols to bitcode files, if -flto is given to clang?

[pcc]

I thought about that but decided against it for a few reasons:

1. It seemed best to express what we want to happen directly. Putting the symbols in the object files seemed like a more round-about way of fixing the bug.
2. The set of libcall symbols is a property of the code generator linked into lld, not the one that was used to create the bitcode file. That means that if we see an old bitcode file it would not be correct to use its libcall symbols.
3. It would bloat every bitcode file with the same (potentially incorrect due to 2) content when that can be easily avoided.

[ruiu]

LGTM

2. The set of libcall symbols is a property of the code generator linked into lld, not the one that was used to create the bitcode file. That means that if we see an old bitcode file it would not be correct to use its libcall symbols.

I'm convinced. A concern I had was that the symbol names are not a property of lld but LTO, but lld and LTO are a single program, and by its nature the symbol name list we have here in lld cannot be out of sync with LTO.

[alexcrichton]

Hello! We've discovered a regression in the Rust project from this commit, and I've opened a dedicated LLVM bug for that as well, and figured it'd be good to mention here as well!

lld/trunk/ELF/Driver.cpp

if (Obj->AddrsigSec) {
       // If an object file does not have an address-significance table,
       // conservatively mark all of its symbols as address-significant.
       for (Symbol *S : Syms)
         markAddrsig(S);
     }
   }
 }
 
+static const char *LibcallRoutineNames[] = {
+#define HANDLE_LIBCALL(code, name) name,
+#include "llvm/IR/RuntimeLibcalls.def"
+#undef HANDLE_LIBCALL
+};
+
 // Do actual linking. Note that when this function is called,
 // all linker scripts have already been parsed.
 template <class ELFT> void LinkerDriver::link(opt::InputArgList &Args) {
   Target = getTarget();
 
   Config->MaxPageSize = getMaxPageSize(Args);
   Config->ImageBase = getImageBase(Args);
 
template <class ELFT> void LinkerDriver::link(opt::InputArgList &Args) {
   // are undefined symbols for them, so we add these to trigger that logic.
   for (StringRef Sym : Script->ReferencedSymbols)
     Symtab->addUndefined<ELFT>(Sym);
 
   // Handle the `--undefined <sym>` options.
   for (StringRef S : Config->Undefined)
     handleUndefined<ELFT>(S);
 
-  // If an entry symbol is in a static archive, pull out that file now
-  // to complete the symbol table. After this, no new names except a
-  // few linker-synthesized ones will be added to the symbol table.
+  // If an entry symbol is in a static archive, pull out that file now.
   handleUndefined<ELFT>(Config->Entry);
 
+  // If any of our inputs are bitcode files, the LTO code generator may create
+  // references to certain library functions that might not be explicit in the
+  // bitcode file's symbol table. If any of those library functions are defined
+  // in a bitcode file in an archive member, we need to arrange to use LTO to
+  // compile those archive members by adding them to the link beforehand.
+  //
+  // With this the symbol table should be complete. After this, no new names
+  // except a few linker-synthesized ones will be added to the symbol table.
+  if (!BitcodeFiles.empty())
+    for (const char *S : LibcallRoutineNames)
+      handleUndefined<ELFT>(S);
+
   // Return if there were name resolution errors.
   if (errorCount())
     return;
 
   // Now when we read all script files, we want to finalize order of linker
   // script commands, which can be not yet final because of INSERT commands.
   Script->processInsertCommands();
 

lld/trunk/test/ELF/lto/Inputs/libcall-archive.ll

+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @memcpy() {
+  ret void
+}

lld/trunk/test/ELF/lto/libcall-archive.ll

+; RUN: rm -f %t.a
+; RUN: llvm-as -o %t.o %s
+; RUN: llvm-as -o %t2.o %S/Inputs/libcall-archive.ll
+; RUN: llvm-ar rcs %t.a %t2.o
+; RUN: ld.lld -o %t %t.o %t.a
+; RUN: llvm-nm %t | FileCheck %s
+
+; CHECK: T _start
+; CHECK: T memcpy
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @_start(i8* %a, i8* %b) {
+entry:
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %a, i8* %b, i64 1024, i1 false)
+  ret void
+}
+
+declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture, i8* nocapture, i64, i1)