[llvm-link] fix linker behavior when linking archives with --only-needed option

[sdmitriev]

Summary

This patch fixes linker behavior when archive is linked with other inputs
as a library (i.e. when --only-needed option is specified). In this case library
is expected to be normally linked first into a separate module and only after
that linker should import required symbols from the linked library module.

[sdmitriev]

I have realized that this patch is not NFC, and it corrects llvm-link behavior when archive is linked with other inputs as a library (with --only-needed option). I have updated description and added LIT test to the patch.

[sdmitriev]

Do you have any comments for this patch?

[tra]

The patch description describes what the patch does, but does not tell us much about the problem is is supposed to fix.
Could you give us more details on why the patch is needed?

[sdmitriev]

In D92535#2440317, @tra wrote:

The patch description describes what the patch does, but does not tell us much about the problem is is supposed to fix.
Could you give us more details on why the patch is needed?

Sure. I believe llvm-link works incorrectly when linking --only-needed symbols from archives with bitcode files. As it is implemented now, llvm-link, when dealing with archives, first links archive modules together into an intermediate module and then tries to link required symbols from that intermediate module into the result. The problem is that archive modules are linked together with --only-needed flag as well, so we always end up with getting empty intermediate module because archive linking starts from scratch (i.e. nothing gets imported into archive module because there are no dependencies).

The problem can be demonstrated using the following simple steps. Suppose we have a bitcode archive defining foo. If we try to link --only-needed symbols from this archive with another file that depends on foo, we’ll get incorrect result - foo will not be imported into the result:

-bash-4.2$ cat foo.ll
define void @foo() {
  ret void
}
-bash-4.2$ cat bar.ll
define void @bar() {
  call void @foo()
  ret void
}
declare void @foo()
-bash-4.2$ llvm-as foo.ll -o foo.bc
-bash-4.2$ llvm-ar cr libfoo.a foo.bc
-bash-4.2$ llvm-link bar.ll --only-needed libfoo.a -o out.bc
-bash-4.2$ llvm-nm out.bc
-------- T bar
         U foo
-bash-4.2$

This patch fixes this problem by changing llvm-link to link archive modules together in a normal way, so the intermediate archive module includes all defined symbols from the archive. And then only required symbols will be imported from the archive module into the result if --only-needed option is specified. This patch also includes few NFC cleanup changes, maybe it makes sense to move these changes into a separate patch.

[sdmitriev]

I have prepared a separate patch for NFC changes D92918. Will update this patch once D92918 is approved.

[tra]

In D92535#2441741, @sdmitriev wrote:

Sure. I believe llvm-link works incorrectly when linking --only-needed symbols from archives with bitcode files. As it is implemented now, llvm-link, when dealing with archives, first links archive modules together into an intermediate module and then tries to link required symbols from that intermediate module into the result. The problem is that archive modules are linked together with --only-needed flag as well, so we always end up with getting empty intermediate module because archive linking starts from scratch (i.e. nothing gets imported into archive module because there are no dependencies).

Thank you for the explanation.

...
This patch fixes this problem by changing llvm-link to link archive modules together in a normal way, so the intermediate archive module includes all defined symbols from the archive. And then only required symbols will be imported from the archive module into the result if --only-needed option is specified. This patch also includes few NFC cleanup changes, maybe it makes sense to move these changes into a separate patch.

I wonder if we want to go even further and bring archive linking closer to how static linking works with normal object files?
Instead of linking all files in the archive together (that may have its own set of issues) and returning a single module, perhaps we should just load individual files, return them as a vector and link each of them in order with --only-needed.

llvm/tools/llvm-link/llvm-link.cpp

144–147

You are assuming that none of the flags currently passed to LoadArFile are needed.
Functionality-wise you only need to disable LinkOnlyNeeded.

I think we may still need to pass linker options here and then explicitly clear --only-needed when we link everything together. the options we have *now* don't matter approach relies on the implementation details.

You also seem to alter the current linker behavior which for some reason treats the first file in the archive differently.
TBH I don't understand why the current code does that. @jsjodin -- could you tell us what's going on? I don't think we can usefully rely on particular order of the files in the archive.

[sdmitriev]

I wonder if we want to go even further and bring archive linking closer to how static linking works with normal object files?
Instead of linking all files in the archive together (that may have its own set of issues) and returning a single module, perhaps we should just load individual files, return them as a vector and link each of them in order with --only-needed.

If we change it that way the output will depend on the order of linking archive members due to the cross dependencies between them, which I assume is wrong. Suppose we have an archive with two modules defining foo and bar respectively, where bar depends on foo, and we are linking --only-needed symbols from this archive to a module which needs bar. If we first link bar module from the archive and then foo we'll get both foo and bar defined in the output. But if we change the order foo will be undefined in the output.

I think llvm-link behavior with this patch will be quite close to what normal object linkers do when static linking archives. It probably needs some command line interface changes to support more usage scenarios (f.e. you cannot link more than one bitcode file in a normal way and then link --only-needed symbols from the libraries in one llvm-link invocation), but that is a different topic.

llvm/tools/llvm-link/llvm-link.cpp

144–147

You are assuming that none of the flags currently passed to LoadArFile are needed.
Functionality-wise you only need to disable LinkOnlyNeeded.

I think we may still need to pass linker options here and then explicitly clear --only-needed when we link everything together. the options we have *now* don't matter approach relies on the implementation details.

I believe no flags are needed at this step when archive module is only being prepared. All necessary flags will be applied when the archive module will be linked to the result.

You also seem to alter the current linker behavior which for some reason treats the first file in the archive differently.
TBH I don't understand why the current code does that. @jsjodin -- could you tell us what's going on? I don't think we can usefully rely on particular order of the files in the archive.

This logic was probably copy pasted from the linkFiles function where it indeed makes sense, but here I do not see why the first archive member should be treated differently.

[sdmitriev]

Updated diff after committing NFC changes (D92918).

[sdmitriev]

ping

[tra]

The change look OK. But we should still wait for @jsjodin to confirm that the first-file-is-different for archive files is unintentional.

llvm/tools/llvm-link/llvm-link.cpp

144–147

This logic was probably copy pasted from the linkFiles function where it indeed makes sense, but here I do not see why the first archive member should be treated differently.

Possibly. Still, before we remove this, it would be prudent to verify that the guess is correct. People do use things in unexpected ways.

@jsjodin -- I'd appreciate if you could tell us why the current code wants to treat the first file in the archive differently.

[tra]

@jdoerfert -- do you happen to know how archives with bitcode are used by OpenMP? Does OpenMP ever link just the archive alone w/o any other bitcode files?

[sdmitriev]

llvm/tools/llvm-link/llvm-link.cpp

144–147

@saiislam, maybe you can comment on this? Based on your comments from D80816 you have taken over tasks that @jsjodin was working on.

[sdmitriev]

Well, it looks like nobody is going to respond.

[saiislam]

In D92535#2469246, @sdmitriev wrote:

Well, it looks like nobody is going to respond.

@sdmitriev Apology for the delay. I will reply by end of the day.

[saiislam]

In D92535#2455987, @tra wrote:

The change look OK. But we should still wait for @jsjodin to confirm that the first-file-is-different for archive files is unintentional.

AFAIK and could test on our internal branch, first-file-is-different for archives is unintentional. So, its removal shouldn't be a problem.
Looks good to me. Please wait for @tra to accept it.

[sdmitriev]

In D92535#2471222, @saiislam wrote:

Looks good to me. Please wait for @tra to accept it.

@tra, if you do not have additional comments can you please accept this patch?

[tra]

LGTM.

llvm/test/tools/llvm-link/Inputs/i.ll

+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @i() {
+  call void @f()
+  ret void
+}
+
+declare void @f()

llvm/test/tools/llvm-link/archive-only-needed.ll

+; RUN: llvm-as %S/Inputs/f.ll -o %t.f.bc
+; RUN: llvm-as %S/Inputs/g.ll -o %t.g.bc
+; RUN: llvm-as %S/Inputs/i.ll -o %t.i.bc
+; RUN: rm -f %t.lib
+; RUN: llvm-ar cr %t.lib %t.f.bc %t.g.bc %t.i.bc
+; RUN: llvm-link %s %t.lib -o %t.linked.bc --only-needed
+; RUN: llvm-nm %t.linked.bc | FileCheck %s
+
+; CHECK: -------- T f
+; CHECK: -------- T i
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+@i = external global i8*
[e-mail] = appending global [1 x i8*] [i8* bitcast (i8** @i to i8*)], section "llvm.metadata"

llvm/tools/llvm-link/llvm-link.cpp

static std::unique_ptr<Module> loadFile(const char *argv0,
 
   if (MaterializeMetadata) {
     ExitOnErr(Result->materializeMetadata());
     UpgradeDebugInfo(*Result);
   }
 
   return Result;
 }
 
-static std::unique_ptr<Module>
-loadArFile(const char *Argv0, std::unique_ptr<MemoryBuffer> Buffer,
-           LLVMContext &Context, unsigned OrigFlags, unsigned ApplicableFlags) {
+static std::unique_ptr<Module> loadArFile(const char *Argv0,
+                                          std::unique_ptr<MemoryBuffer> Buffer,
+                                          LLVMContext &Context) {
   std::unique_ptr<Module> Result(new Module("ArchiveModule", Context));
   StringRef ArchiveName = Buffer->getBufferIdentifier();
   if (Verbose)
     errs() << "Reading library archive file '" << ArchiveName
            << "' to memory\n";
   Error Err = Error::success();
   object::Archive Archive(*Buffer, Err);
   ExitOnErr(std::move(Err));
if (!M.get()) {
       errs() << Argv0 << ": ";
       WithColor::error() << " parsing member '" << ChildName
                          << "' of archive library failed'" << ArchiveName
                          << "'\n";
       return nullptr;
     }
     if (Verbose)
       errs() << "Linking member '" << ChildName << "' of archive library.\n";
-    if (Linker::linkModules(*Result, std::move(M), ApplicableFlags))
+    if (Linker::linkModules(*Result, std::move(M)))
       return nullptr;
-    ApplicableFlags = OrigFlags;
   } // end for each child
   ExitOnErr(std::move(Err));
   return Result;
 }
 
 namespace {
 
 /// Helper to load on demand a Module from file and cache it for subsequent
static bool linkFiles(const char *argv0, LLVMContext &Context, Linker &L,
   // Similar to some flags, internalization doesn't apply to the first file.
   bool InternalizeLinkedSymbols = false;
   for (const auto &File : Files) {
     std::unique_ptr<MemoryBuffer> Buffer =
         ExitOnErr(errorOrToExpected(MemoryBuffer::getFileOrSTDIN(File)));
 
     std::unique_ptr<Module> M =
         identify_magic(Buffer->getBuffer()) == file_magic::archive
-            ? loadArFile(argv0, std::move(Buffer), Context, Flags,
-                         ApplicableFlags)
+            ? loadArFile(argv0, std::move(Buffer), Context)
             : loadFile(argv0, std::move(Buffer), Context);
     if (!M.get()) {
       errs() << argv0 << ": ";
       WithColor::error() << " loading file '" << File << "'\n";
       return false;
     }
 
     // Note that when ODR merging types cannot verify input files in here When