[ThinLTO] Remove functions resolved to available_externally from comdats

[tejohnson]

Summary

thinLTOResolveWeakForLinkerModule needs to drop any preempted weak symbols
that were converted to available_externally from comdats, otherwise we
will get a verification failure (since available_externally is a
declaration for the linker, and no declarations can be in a comdat).

[mehdi_amini]

Do we need gold for the test here or could it be written with an LLVM tool?

[twoh]

BTW, it seems that the original assertion failure (PR28760) doesn't happen even with r274523. Originally IRLinker::linkGlobalValueProto created a new GlobalValue with ".%d" appended to its name, but for the given example code the function returns nullptr because DoneLinkBodies is already true. Could you please double check?

[tejohnson]

In D23015#502330, @mehdi_amini wrote:

Do we need gold for the test here or could it be written with an LLVM tool?

Let me see if I can trigger without gold's symbol resolution

In D23015#502688, @twoh wrote:

BTW, it seems that the original assertion failure (PR28760) doesn't happen even with r274523. Originally IRLinker::linkGlobalValueProto created a new GlobalValue with ".%d" appended to its name, but for the given example code the function returns nullptr because DoneLinkBodies is already true. Could you please double check?

I haven't tried at r274523, only at head as of yesterday. The test case included here definitely creates a GV with .%d appended (it wouldn't pass if it didn't), and it fails with the assertion if I restore that. Are you saying that the test case included here is not working when the patch is applied to r274523, or that it doesn't provoke the problem at that older revision? Or you cannot reproduce your original failure at r274523? If your original failure is reproducible at a recent revision, is it fixed by the current patch?

[twoh]

@tejohnson The test code surely generates GV with ".%d" appended, but it doesn't trigger the assertion failure even without this patch, both for r274523 and r277147. Let me try again with more recent version.

My original failure cannot be reproduced by the recent version(r277147) because other issue hides the original failure. However, once I apply this patch to r274523 then it works (linking fails with another error but it definitely makes more progress). I'm just concerning the test code may target wrong.

[tejohnson]

In D23015#502735, @twoh wrote:

@tejohnson The test code surely generates GV with ".%d" appended, but it doesn't trigger the assertion failure even without this patch, both for r274523 and r277147. Let me try again with more recent version.

Hmm, it does for me and I am at r277267. If I put the assert back it fails with that assert.

My original failure cannot be reproduced by the recent version(r277147) because other issue hides the original failure.

Is this the -g failure? Can you try without -g?

However, once I apply this patch to r274523 then it works (linking fails with another error but it definitely makes more progress). I'm just concerning the test code may target wrong.

[twoh]

@tejohnson Sorry, it was my bad. I wrote the makefile by myself and swapped the position of t.o and t2.o. Once I position them right the assertion fails.

If I try it without -g, it fails with the same error with r274523.

[tejohnson]

In D23015#502773, @twoh wrote:

@tejohnson Sorry, it was my bad. I wrote the makefile by myself and swapped the position of t.o and t2.o. Once I position them right the assertion fails.

If I try it without -g, it fails with the same error with r274523.

Ok, great. Let me know if the link succeeds with this patch and with -g removed.

[tejohnson]

In D23015#502700, @tejohnson wrote:

In D23015#502330, @mehdi_amini wrote:

Do we need gold for the test here or could it be written with an LLVM tool?

Let me see if I can trigger without gold's symbol resolution

Can't trigger with llvm-lto. The gold-plugin uses the IRLinker to move the module being compiled (in that ThinLTO backend) into an empty module, indicating the ValuesToLink based on its symbol resolution decisions. Which is why we get f1 linked in only as a declaration for %t2.o, which means we need to create a local copy of it for the use via the alias, resulting in the naming conflict with the declaration. In llvm-lto, we simply use the module being compiled with a thinlto-action as is.

[mehdi_amini]

OK, let me backtrack, is the original issue coming from the fact that gold is starting with an empty module?
Then why not changing this?

[tejohnson]

In D23015#502970, @mehdi_amini wrote:

OK, let me backtrack, is the original issue coming from the fact that gold is starting with an empty module?
Then why not changing this?

We use gold's symbol resolution to determine which values to link in. So in the example, it knows that f1 is a preempted symbol in %t2.o and doesn't need to include its definition. I don't think we should need to change that.

[mehdi_amini]

In D23015#503013, @tejohnson wrote:

In D23015#502970, @mehdi_amini wrote:

OK, let me backtrack, is the original issue coming from the fact that gold is starting with an empty module?
Then why not changing this?

We use gold's symbol resolution to determine which values to link in. So in the example, it knows that f1 is a preempted symbol in %t2.o and doesn't need to include its definition. I don't think we should need to change that.

I see...
I still does not think that's a great thing: using the IRMover just to get a module where some symbols are pruned seems quite sketchy to me.

Here we accept that the module can have renamed symbols from what is in the index, but that should be an invariant or we'll run in trouble at some point. So I'm not convinced the fix is right at this point.

I dug a bit more, I'm still trying to follow how the bug happens: the IRMover is forcing @f1 (in Inputs/thinlto_alias2.ll) to be linked to satisfy the alias @a2. And since there is already a declaration for @f1 when it does so, it is supposed to create a local copy (i.e. it will be an *internal* function), IRMover.cpp ~line 930.

Now the code you are patching is a callback for the internalize utility, and IIUC it is not called on internal function (which I expect to be the case here), as I read InternalizePass::shouldPreserveGV.

[tejohnson]

In D23015#503045, @mehdi_amini wrote:

In D23015#503013, @tejohnson wrote:

In D23015#502970, @mehdi_amini wrote:

OK, let me backtrack, is the original issue coming from the fact that gold is starting with an empty module?
Then why not changing this?

We use gold's symbol resolution to determine which values to link in. So in the example, it knows that f1 is a preempted symbol in %t2.o and doesn't need to include its definition. I don't think we should need to change that.

I see...
I still does not think that's a great thing: using the IRMover just to get a module where some symbols are pruned seems quite sketchy to me.

Here we accept that the module can have renamed symbols from what is in the index, but that should be an invariant or we'll run in trouble at some point. So I'm not convinced the fix is right at this point.

I decided I agree, see below.

I dug a bit more, I'm still trying to follow how the bug happens: the IRMover is forcing @f1 (in Inputs/thinlto_alias2.ll) to be linked to satisfy the alias @a2. And since there is already a declaration for @f1 when it does so, it is supposed to create a local copy (i.e. it will be an *internal* function), IRMover.cpp ~line 930.

Correct.

Now the code you are patching is a callback for the internalize utility, and IIUC it is not called on internal function (which I expect to be the case here), as I read InternalizePass::shouldPreserveGV.

It has been promoted though (by renameModuleForThinLTO), so it is not internal at this point (which is why the CHECK in the new test case looks like "CHECK: define hidden i32 @f1.1.llvm.0"

But after I sent this last night I realized that we probably should not have the gold-plugin drop any preempted symbols at this point. The reason is that we are losing optimization opportunities:

1. Loss of inlining opportunity for the dropped preempted linkonce_odr: In this case the weak_odr can't be inlined anyway, but if it was linkonce_odr, we wouldn't be able to inline it if it was preempted (we would have to import it back in, but the import decisions will be made when we still have the linkonce_odr definition and the calls wouldn't be external, but in any case there isn't any point in dropping only to import for inlining later).
2. Loss of internalization for the local copy - in this case we are checking to see if we can internalize the promoted symbol, which we would be able to do in this case if we could locate its summary. So we lose this opportunity.

I have made a change to the gold-plugin to keep the preempted symbols as well. However, this exposed another issue: when we keep the preempted linkonce in the comdat, thinLTOResolveWeakForLinkerModule comes along and changes it to available_externally. We then get a verification failure about a declaration in a comdat.

Interestingly, we have a fix for this in renameModuleForThinLTO, which drops any available_externally from comdats. It is meant to clean up after importing, but if I reorder renameModuleForThinLTO and thinLTOResolveWeakForLinkerModule in gold-plugin, it fixes this particular issue. I managed to reproduce this issue with an llvm-lto test case, since ProcessThinLTOModule() in ThinLTOCodeGenerator.cpp has the same ordering. It is also fixed by flipping the ordering between these two. Interestingly, and probably completely accidentally, ThinLTOCodeGenerator::promote() already has the desirable ordering. However, I don't like the subtle ordering requirement between these two calls. Perhaps it is better to explicitly strip any new available_externally symbols from comdats in thinLTOResolveWeakForLinkerModule. Hmm, I think I like that approach better. WDYT? Let me do that, will do so and clean up and add the new test cases to the patches later today.

[tejohnson]

Change to avoid dropping preempted symbols early.

[tejohnson]

Ping.

[mehdi_amini]

Sorry missed the update, will try to get to it today.

[mehdi_amini]

LGTM, Thanks!

[tejohnson]

I discovered while merging this patch with head on Friday that the Resolution-based LTO API I committed for pcc at r278338 already fixes this issue in the same way.

However, the following aspect is still an issue:

---

In D23015#503394, @tejohnson wrote:

I have made a change to the gold-plugin to keep the preempted symbols as well. However, this exposed another issue: when we keep the preempted linkonce in the comdat, thinLTOResolveWeakForLinkerModule comes along and changes it to available_externally. We then get a verification failure about a declaration in a comdat.

Interestingly, we have a fix for this in renameModuleForThinLTO, which drops any available_externally from comdats. It is meant to clean up after importing, but if I reorder renameModuleForThinLTO and thinLTOResolveWeakForLinkerModule in gold-plugin, it fixes this particular issue. I managed to reproduce this issue with an llvm-lto test case, since ProcessThinLTOModule() in ThinLTOCodeGenerator.cpp has the same ordering. It is also fixed by flipping the ordering between these two. Interestingly, and probably completely accidentally, ThinLTOCodeGenerator::promote() already has the desirable ordering. However, I don't like the subtle ordering requirement between these two calls. Perhaps it is better to explicitly strip any new available_externally symbols from comdats in thinLTOResolveWeakForLinkerModule. Hmm, I think I like that approach better. WDYT? Let me do that, will do so and clean up and add the new test cases to the patches later today.

---

It turns out that with pcc's changes we get the fortuitous ordering of renameModuleForThinLTO after thinLTOResolveWeakForLinkerModule in the new lto::thinBackend, so the issue is not exposed via the gold-plugin. It is however, still an issue in llvm-lto (and I realized in looking into this that I had forgotten to add my new llvm-lto based test case to this patch).

I am going to change this patch to only include this particular fix, along with the llvm-lto based test, and submit it.

[tejohnson]

Update to only include fix and test case for dropping available_externally
from comdats.

[mehdi_amini]

LGTM.

[tejohnson]

Rename test to something more appropriate before committing.

lib/Transforms/IPO/FunctionImport.cpp

auto updateLinkage = [&](GlobalValue &GV) {
     if (GS == DefinedGlobals.end())
       return;
     auto NewLinkage = GS->second->linkage();
     if (NewLinkage == GV.getLinkage())
       return;
     DEBUG(dbgs() << "ODR fixing up linkage for `" << GV.getName() << "` from "
                  << GV.getLinkage() << " to " << NewLinkage << "\n");
     GV.setLinkage(NewLinkage);
+    // Remove functions imported as available externally defs from comdats,
+    // as this is a declaration for the linker, and will be dropped eventually.
+    // It is illegal for comdats to contain declarations.
+    auto *GO = dyn_cast_or_null<GlobalObject>(&GV);
+    if (GO && GO->isDeclarationForLinker() && GO->hasComdat()) {
+      assert(GO->hasAvailableExternallyLinkage() &&
+             "Expected comdat on definition (possibly available external)");
+      GO->setComdat(nullptr);
+    }
   };
 
   // Process functions and global now
   for (auto &GV : TheModule)
     updateLinkage(GV);
   for (auto &GV : TheModule.globals())
     updateLinkage(GV);
   for (auto &GV : TheModule.aliases())

test/tools/gold/X86/Inputs/thinlto_alias.ll

-target triple = "x86_64-unknown-linux-gnu"
-define weak void @weakfunc() {
-entry:
-  ret void
+$c2 = comdat any
+
+define weak_odr i32 @f1(i8*) unnamed_addr comdat($c2) {
+  ret i32 40
+}
+
+define linkonce_odr i32 @f2(i8*) unnamed_addr comdat($c2) {
+  ret i32 41
+}
+
+@r2 = global i32(i8*)* @f1
+@a2 = alias i32(i8*), i32(i8*)* @f1
+define i32 @g() {
+  %i = call i32 @f2(i8* null)
+  ret i32 %i
 }

test/tools/gold/X86/thinlto_alias.ll

 ; RUN: opt -module-summary %s -o %t.o
 ; RUN: opt -module-summary %p/Inputs/thinlto_alias.ll -o %t2.o
 
-; Ensure that a preempted weak symbol that is linked in as a local
-; copy is handled properly. Specifically, the local copy will be promoted,
-; and internalization should be able to use the original non-promoted
-; name to locate the summary (otherwise internalization will abort because
-; it expects to locate summaries for all definitions).
-; Note that gold picks the first copy of weakfunc() as the prevailing one,
-; so listing %t2.o first is sufficient to ensure that this copy is
-; preempted.
 ; RUN: %gold -m elf_x86_64 -plugin %llvmshlibdir/LLVMgold.so \
+; RUN:     -shared \
 ; RUN:     --plugin-opt=thinlto \
+; RUN:     --plugin-opt=-import-instr-limit=0 \
 ; RUN:     --plugin-opt=save-temps \
-; RUN:     -o %t3.o %t2.o %t.o
+; RUN:     -o %t3.o %t.o %t2.o
+
+; Check that we have weak f1/f2 symbols
 ; RUN: llvm-nm %t3.o | FileCheck %s
+; CHECK-DAG: W f1
+; CHECK-DAG: W f2
+
+; The %t.o copies are prevailing, and should both now be weak_odr.
 ; RUN: llvm-dis %t.o.opt.bc -o - | FileCheck --check-prefix=OPT %s
+; OPT: define weak_odr i32 @f1(i8*) unnamed_addr #0 comdat($c1) {
+; OPT: define weak_odr i32 @f2(i8*) unnamed_addr #0 comdat($c1) {
+
+; The %t2.o copies are preempted, but we have to keep the weak_odr f1 since
+; it is referenced by an alias. The linkonce_odr f2 should be inlined and
+; eliminated.
 ; RUN: llvm-dis %t2.o.opt.bc -o - | FileCheck --check-prefix=OPT2 %s
+; OPT2-NOT: @f2
+; OPT2: define weak_odr i32 @f1(i8*) unnamed_addr #0 comdat($c2) {
+
+$c1 = comdat any
 
-; CHECK-NOT: U f
-; OPT: define hidden void @weakfunc.llvm.0()
-; OPT2: define weak void @weakfunc()
-
-target triple = "x86_64-unknown-linux-gnu"
-
-@weakfuncAlias = alias void (...), bitcast (void ()* @weakfunc to void (...)*)
-define weak void @weakfunc() {
-entry:
-  ret void
+define weak_odr i32 @f1(i8*) unnamed_addr comdat($c1) {
+  ret i32 42
 }
+
+define linkonce_odr i32 @f2(i8*) unnamed_addr comdat($c1) {
+  ret i32 43
+}
+
+@a1 = alias i32 (i8*), i32 (i8*)* @f1

test/tools/gold/X86/thinlto_linkonceresolution.ll

 ; RUN: opt -module-summary %s -o %t.o
 ; RUN: opt -module-summary %p/Inputs/thinlto_linkonceresolution.ll -o %t2.o
 
-; Ensure the plugin ensures that for ThinLTO the prevailing copy of a
-; linkonce symbol is changed to weak to ensure it is not eliminated.
+; Ensure that for ThinLTO the prevailing copy of a linkonce symbol is
+; changed to weak so that it is not eliminated.
 ; Note that gold picks the first copy of f() as the prevailing one,
 ; so listing %t2.o first is sufficient to ensure that this copy is
 ; preempted. Also, set the import-instr-limit to 0 to prevent f() from
 ; being imported from %t2.o which hides the problem.
 ; RUN: %gold -m elf_x86_64 -plugin %llvmshlibdir/LLVMgold.so \
 ; RUN:     --plugin-opt=thinlto \
 ; RUN:     --plugin-opt=-import-instr-limit=0 \
 ; RUN:     --plugin-opt=save-temps \
 ; RUN:     -shared \
 ; RUN:     -o %t3.o %t2.o %t.o
 ; RUN: llvm-nm %t3.o | FileCheck %s
 ; RUN: llvm-dis %t.o.opt.bc -o - | FileCheck --check-prefix=OPT %s
 ; RUN: llvm-dis %t2.o.opt.bc -o - | FileCheck --check-prefix=OPT2 %s
 
 ; Ensure that f() is defined in resulting object file, and also
-; confirm the weak linkage directly in the saved opt bitcode files.
+; confirm the weak linkage directly in the saved opt bitcode file.
 ; CHECK-NOT: U f
-; OPT: declare hidden void @f()
 ; OPT2: define weak_odr hidden void @f()
+; The preempted copy of f() should be dropped after inlining into g(),
+; as it would have been changed to available_externally.
+; OPT-NOT: @f()
 
 target triple = "x86_64-unknown-linux-gnu"
 define i32 @g() {
   call void @f()
   ret i32 0
 }
 define linkonce_odr hidden void @f() {
   ret void
 }

test/tools/gold/X86/thinlto_weak_resolution.ll

 ; RUN: opt -module-summary %s -o %t.o
 ; RUN: opt -module-summary %p/Inputs/thinlto_weak_resolution.ll -o %t2.o
 
 ; Verify that prevailing weak for linker symbol is kept.
 ; Note that gold picks the first copy of a function as the prevailing one,
 ; so listing %t.o first is sufficient to ensure that its copies are prevailing.
 ; RUN: %gold -m elf_x86_64 -plugin %llvmshlibdir/LLVMgold.so \
 ; RUN:     --plugin-opt=thinlto \
 ; RUN:     --plugin-opt=save-temps \
 ; RUN:     -shared \
 ; RUN:     -o %t3.o %t.o %t2.o
 
 ; RUN: llvm-nm %t3.o | FileCheck %s
 ; CHECK: weakfunc
 
-; All of the preempted functions should have been eliminated (the plugin will
-; not link them in).
-; RUN: llvm-dis %t2.o.opt.bc -o - | FileCheck --check-prefix=OPT2 %s
-; OPT2-NOT: @
-
 ; RUN: llvm-dis %t.o.opt.bc -o - | FileCheck --check-prefix=OPT %s
 
 target triple = "x86_64-unknown-linux-gnu"
 
 
 define i32 @main() #0 {
 entry:
   call void @linkonceodralias()

tools/gold/gold-plugin.cpp

getModuleSummaryIndexForFile(claimed_file &F) {
 
   return Obj.takeIndex();
 }
 
 static std::unique_ptr<Module>
 getModuleForFile(LLVMContext &Context, claimed_file &F, const void *View,
                  StringRef Name, raw_fd_ostream *ApiFile,
                  StringSet<> &Internalize, std::vector<GlobalValue *> &Keep,
-                 StringMap<unsigned> &Realign) {
+                 StringMap<unsigned> &Realign,
+                 bool KeepPreempted = false) {
   MemoryBufferRef BufferRef(StringRef((const char *)View, F.filesize), Name);
   ErrorOr<std::unique_ptr<object::IRObjectFile>> ObjOrErr =
       object::IRObjectFile::create(BufferRef, Context);
 
   if (std::error_code EC = ObjOrErr.getError())
     message(LDPL_FATAL, "Could not read bitcode from file : %s",
             EC.message().c_str());
 
for (auto &ObjSym : Obj.symbols()) {
 
     switch (Resolution) {
     case LDPR_UNKNOWN:
       llvm_unreachable("Unexpected resolution");
 
     case LDPR_RESOLVED_IR:
     case LDPR_RESOLVED_EXEC:
     case LDPR_RESOLVED_DYN:
+      break;
+
     case LDPR_PREEMPTED_IR:
     case LDPR_PREEMPTED_REG:
+      if (KeepPreempted)
+        Keep.push_back(GV);
       break;
 
     case LDPR_UNDEF:
       if (!GV->isDeclarationForLinker())
         assert(GV->hasComdat());
       break;
 
     case LDPR_PREVAILING_DEF_IRONLY: {
else
     runSplitCodeGen(OptFilename);
 }
 
 /// Links the module in \p View from file \p F into the combined module
 /// saved in the IRMover \p L.
 static void linkInModule(LLVMContext &Context, IRMover &L, claimed_file &F,
                          const void *View, StringRef Name,
                          raw_fd_ostream *ApiFile, StringSet<> &Internalize,
-                         bool SetName = false) {
+                         bool SetName = false, bool KeepPreempted = false) {
   std::vector<GlobalValue *> Keep;
   StringMap<unsigned> Realign;
   std::unique_ptr<Module> M = getModuleForFile(Context, F, View, Name, ApiFile,
-                                               Internalize, Keep, Realign);
+                                               Internalize, Keep, Realign,
+                                               KeepPreempted);
   if (!M.get())
     return;
   if (!options::triple.empty())
     M->setTargetTriple(options::triple.c_str());
   else if (M->getTargetTriple().empty()) {
     M->setTargetTriple(DefaultTriple);
   }
 
Context.setDiscardValueNames(options::TheOutputType !=
                                options::OT_SAVE_TEMPS);
   Context.enableDebugTypeODRUniquing(); // Merge debug info types.
   Context.setDiagnosticHandler(diagnosticHandlerForContext, nullptr, true);
 
   std::unique_ptr<llvm::Module> NewModule(new llvm::Module(Name, Context));
   IRMover L(*NewModule.get());
 
   StringSet<> Dummy;
-  linkInModule(Context, L, F, View, Name, ApiFile, Dummy, true);
+  // Keep preempted symbols to enable linkonce_odr inlining within this
+  // module, and to ensure that the module matches the index summaries
+  // generated earlier for correct internalization, etc. Preempted symbols
+  // will be dropped as possible during thinLTOResolveWeakForLinkerModule.
+  linkInModule(Context, L, F, View, Name, ApiFile, Dummy, true,
+               /* KeepPreempted = */ true);
   if (renameModuleForThinLTO(*NewModule, CombinedIndex))
     message(LDPL_FATAL, "Failed to rename module for ThinLTO");
 
   CodeGen codeGen(std::move(NewModule), OS, TaskID, &CombinedIndex, Name,
                   &ModuleMap, &ImportList, &DefinedGlobals);
   codeGen.runAll();
 }