[LTO] Remove values from non-prevailing comdats

[tejohnson]

Summary

When linking a regular LTO module, if it has any non-prevailing values
(dropped to available_externally) in comdats, we need to do more than
just remove those values from their comdat. We also remove all values
from that comdat, so as to avoid leaving an incomplete comdat.

This is necessary in case we are compiling in mixed regular and ThinLTO
mode, since the resulting regularLTO native object is always linked into
the final binary first. We need to prevent the linker from selecting an
incomplete comdat that was not the prevailing copy.

Fixes PR32980.

[chandlerc]

Really sorry if I'm just missing context with a drive by comment ... but is this correct? What if two symbols in a comdat are actually required to be treated as a single comdat for correctness?

[tejohnson]

In D34803#794815, @chandlerc wrote:

Really sorry if I'm just missing context with a drive by comment ... but is this correct? What if two symbols in a comdat are actually required to be treated as a single comdat for correctness?

Not sure what scenario you are referring to, but this is invoked if we have already decided, based on linker info, that the comdat contains a non-prevailing copy of a linkonce or weak symbol. So we would already have removed that non-prevailing symbol from the comdat, leaving it incomplete. Presumably if the linker did not select that copy of the linkonce or weak as prevailing, then it has not selected this coppy of the comdat, and so we remove everything else from the comdat so as to not leave behind an incomplete comdat. Since the regular LTO native object is passed to the final link before any native objects from ThinLTO backends, leaving an incomplete comdat there could cause it to be incorrectly selected in the final link, when it wasn't originally (which is what was happening in the associated bug).

[ychen]

llvm/trunk/test/LTO/Resolution/X86/comdat-mixed-lto.ll

11

It seems PR49009 failed due to this patch.

Here both C@t1.o and testglobfunc@t2.o prevail however they are from COMDATs of the same key, I think this resolution is not possible from the linker's point of view?

[tejohnson]

llvm/trunk/test/LTO/Resolution/X86/comdat-mixed-lto.ll

11

Reading through the bug this was fixing (PR32980) again, I think this is trying to simulate the scenario that occurred there. It sounds like it was a ThinLTO build where LTO splitting was in effect, so we also had a regular LTO module. When we are done with the LTO backends the regular LTO module is handed back to the linker first. The problem occurred because the comdat added to the regular LTO module was initially not prevailing, but since the regular LTO native object was handed back to the linker for the final native linker first, its (then incomplete) comdat and symbols were subsequently selected as prevailing, leading to the incomplete comdat issue. We avoided this by removing the comdat from the non-prevailing copies. I think the below test is trying to simulate that effect since here we only have a single link. I can add a comment to the test.

I looked at PR49009 but it isn't clear from what is written in the bug how this patch caused that failure. Can you elaborate as to what is happening to that symbol with and without this patch?

[ychen]

llvm/trunk/test/LTO/Resolution/X86/comdat-mixed-lto.ll

11

Thanks for taking a look, Teresa. I reduced PR49009 to a test case like this. D2 was dropped due to non-prevailing [e-mail], hence the D1 to D2 aliasing caused the assertion failure.

---- a.ll  (D2,px D0,)
$D5 = comdat any

@D1 = weak_odr unnamed_addr alias void (%"X"*), void (%"Y"*)* @D2

define weak_odr void @D2(%"Y"* %this) unnamed_addr #0 comdat($D5) align 2 {
entry:
  ret void
}

define weak_odr void @D0(%"Y"* %this) unnamed_addr #0 comdat($D5) align 2 {
entry:
  tail call void @llvm.trap()
  unreachable
}


---- b.ll  (D0,px)
$D0 = comdat any

define linkonce_odr void @D0(%"Y"* %this) unnamed_addr #0 comdat align 2 {
entry:
  tail call void @llvm.trap()
  unreachable
}

[ychen]

llvm/trunk/test/LTO/Resolution/X86/comdat-mixed-lto.ll

11

Maybe we should not drop the COMDAT when there are prevailing symbols in it which means the COMDAT has been chosen.

[tejohnson]

llvm/trunk/test/LTO/Resolution/X86/comdat-mixed-lto.ll

11

@MaskRay for input from the linker side

My understanding is that symbols in the same comdat should be kept or discarded as a group. In this case the linker has apparently decided that the copy of D0 from comdat $D5 in a.ll is not prevailing, despite the other symbol in that copy of the comdat D2 being selected as prevailing. Which breaks my understanding that the comdat should be kept or discarded as a whole. And the symbol D0 from comdat $D0 in b.ll is instead selected as the prevailing copy of D0. Part of the issue is that symbol D0 is in differently named comdats in a.ll and b.ll with different grouping of symbols, which seems unusual.

The problem in your test case presumably relates to the following bit of code from when we remove symbols from the comdat:

// Additionally need to drop externally visible global values from the comdat
// to available_externally, so that there aren't multiply defined linker
// errors.
if (!GV.hasLocalLinkage())
  GV.setLinkage(GlobalValue::AvailableExternallyLinkage);

I'm not 100% sure why I added that handling, since in the original bug PR32980 the other symbol in the comdat was already internal. Ah, ok I looked for and found the original review, which was off-phab since it was @respindola who didn't use phab for reviews. In fact here was his first reply:

From https://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20170626/465766.html:

I am probably missing something.

But if a symbol in a comdat is prevailing and another one is not, that is a bug in the linker, no?

Cheers,
Rafael

Note the comment about it being a bug in the linker if one symbol in the comdat is prevailing and one is not, which seems to be what is happening here.

In my reply (https://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20170626/465779.html) I pointed out that I am fixing an issue where the other symbol in the comdat is internal, so it isn't an issue with the linker:

This is just handling the rest of the symbols in the comdat (e.g. internals) that were being left in the comdat resulting in an incomplete comdat.

But I go on to say:

I suppose I could change this to simply removal all non-prevailing symbols from comdats in addRegularLTO (rather than just keeping track of which had a weak/linkonce removed from the comdat and fixing them up later).

And I'm not sure from the rest of what I wrote what triggered my thinking on that. But regardless, I think the idea per Rafael and my own understanding is that the comdat selection should result in all or nothing selection of prevailingness of externally visible symbols in a comdat, which seems to be what is not the case in the bug you are looking at. If that is expected, then I think removing the few lines I show above about dropping those to available_externally would fix this. But I do believe we still need to remove from the comdat, since that comdat would be incomplete.

[MaskRay]

llvm/trunk/test/LTO/Resolution/X86/comdat-mixed-lto.ll

11

I agree that comdat members should be retained or discarded as a unit.
The object files should ensure that the situation (one member is prevailing while another is not) does not happen.
I'll consider such cases erroneous input.

In the b.ll (D0,px) example, the issue is that @D0 should not be in two comdats ($D5 and $D0).
I can understand D0/D1/D5 (-mconstructor-aliaes) in $D5 is justified, but why is only D0 in $D0 in b.ll?

[ychen]

llvm/trunk/test/LTO/Resolution/X86/comdat-mixed-lto.ll

11

@MaskRay Thanks for chiming in.

I agree that comdat members should be retained or discarded as a unit.

Agreed. I wonder how does this works with symbol resolution?

The object files should ensure that the situation (one member is prevailing while another is not) does not happen.

This is kinda surprising to me. Does this imply that COMDAT choosing decides symbol resolution?

@respindola mentioned here (https://bugs.llvm.org/show_bug.cgi?id=27866#c18) that, COMDAT choosing happens before symbol resolution which, from my limited linker knowledge, suggests that COMDAT choosing is independent of symbol resolution? I think I misunderstand something here.

I'll consider such cases erroneous input.

In the b.ll (D0,px) example, the issue is that @D0 should not be in two comdats ($D5 and $D0).
I can understand D0/D1/D5 (-mconstructor-aliaes) in $D5 is justified, but why is only D0 in $D0 in b.ll?

D5 comdat is produced from explicit instantiation (https://github.com/weidai11/cryptopp/blob/1124a3d1fe8ac0c59acaf75f087ee4bd44a8b0bf/iterhash.cpp#L193).
D0 comdat is produced from implicit instantiation (SHA512 in a different TU: https://github.com/weidai11/cryptopp/blob/1124a3d1fe8ac0c59acaf75f087ee4bd44a8b0bf/donna_64.cpp#L845 ) triggered vtable emission which refers to the D0. I'm not sure if it correct to put D0 in its own comdat though.

llvm/trunk/lib/LTO/LTO.cpp

Error LTO::addModule(InputFile &Input, unsigned ModI,
   // Regular LTO module summaries are added to a dummy module that represents
   // the combined regular LTO module.
   if (Error Err = BM.readSummary(ThinLTO.CombinedIndex, "", -1ull))
     return Err;
   RegularLTO.ModsWithSummaries.push_back(std::move(*ModOrErr));
   return Error::success();
 }
 
+// Checks whether the given global value is in a non-prevailing comdat
+// (comdat containing values the linker indicated were not prevailing,
+// which we then dropped to available_externally), and if so, removes
+// it from the comdat. This is called for all global values to ensure the
+// comdat is empty rather than leaving an incomplete comdat. It is needed for
+// regular LTO modules, in case we are in a mixed-LTO mode (both regular
+// and thin LTO modules) compilation. Since the regular LTO module will be
+// linked first in the final native link, we want to make sure the linker
+// doesn't select any of these incomplete comdats that would be left
+// in the regular LTO module without this cleanup.
+static void
+handleNonPrevailingComdat(GlobalValue &GV,
+                          std::set<const Comdat *> &NonPrevailingComdats) {
+  Comdat *C = GV.getComdat();
+  if (!C)
+    return;
+
+  if (!NonPrevailingComdats.count(C))
+    return;
+
+  // Additionally need to drop externally visible global values from the comdat
+  // to available_externally, so that there aren't multiply defined linker
+  // errors.
+  if (!GV.hasLocalLinkage())
+    GV.setLinkage(GlobalValue::AvailableExternallyLinkage);
+
+  if (auto GO = dyn_cast<GlobalObject>(&GV))
+    GO->setComdat(nullptr);
+}
+
 // Add a regular LTO object to the link.
 // The resulting module needs to be linked into the combined LTO module with
 // linkRegularLTO.
 Expected<LTO::RegularLTOState::AddedModule>
 LTO::addRegularLTO(BitcodeModule BM, ArrayRef<InputFile::Symbol> Syms,
                    const SymbolResolution *&ResI,
                    const SymbolResolution *ResE) {
   RegularLTOState::AddedModule Mod;
while (MsymI != MsymE) {
       if ((Flags & object::BasicSymbolRef::SF_Global) &&
           !(Flags & object::BasicSymbolRef::SF_FormatSpecific))
         return;
       ++MsymI;
     }
   };
   Skip();
 
+  std::set<const Comdat *> NonPrevailingComdats;
   for (const InputFile::Symbol &Sym : Syms) {
     assert(ResI != ResE);
     SymbolResolution Res = *ResI++;
 
     assert(MsymI != MsymE);
     ModuleSymbolTable::Symbol Msym = *MsymI++;
     Skip();
 
if (GlobalValue *GV = Msym.dyn_cast<GlobalValue *>()) {
                  !AliasedGlobals.count(cast<GlobalObject>(GV))) {
         // Any of the above three types of linkage indicates that the
         // chosen prevailing symbol will have the same semantics as this copy of
         // the symbol, so we may be able to link it with available_externally
         // linkage. We will decide later whether to do that when we link this
         // module (in linkRegularLTO), based on whether it is undefined.
         Mod.Keep.push_back(GV);
         GV->setLinkage(GlobalValue::AvailableExternallyLinkage);
+        if (GV->hasComdat())
+          NonPrevailingComdats.insert(GV->getComdat());
         cast<GlobalObject>(GV)->setComdat(nullptr);
       }
     }
     // Common resolution: collect the maximum size/alignment over all commons.
     // We also record if we see an instance of a common as prevailing, so that
     // if none is prevailing we can ignore it later.
     if (Sym.isCommon()) {
       // FIXME: We should figure out what to do about commons defined by asm.
       // For now they aren't reported correctly by ModuleSymbolTable.
       auto &CommonRes = RegularLTO.Commons[Sym.getIRName()];
       CommonRes.Size = std::max(CommonRes.Size, Sym.getCommonSize());
       CommonRes.Align = std::max(CommonRes.Align, Sym.getCommonAlignment());
       CommonRes.Prevailing |= Res.Prevailing;
     }
 
     // FIXME: use proposed local attribute for FinalDefinitionInLinkageUnit.
   }
+  if (!M.getComdatSymbolTable().empty())
+    for (GlobalValue &GV : M.global_values())
+      handleNonPrevailingComdat(GV, NonPrevailingComdats);
   assert(MsymI == MsymE);
   return std::move(Mod);
 }
 
 Error LTO::linkRegularLTO(RegularLTOState::AddedModule Mod,
                           bool LivenessFromIndex) {
   if (!RegularLTO.CombinedModule) {
     RegularLTO.CombinedModule =

llvm/trunk/test/LTO/Resolution/X86/Inputs/comdat-mixed-lto.ll

+; ModuleID = 'comdat-mixed-lto1.o'
+source_filename = "comdat-mixed-lto1.cpp"
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+%"class.Test::ptr" = type { i32 }
+
+$C = comdat any
+
+@C = linkonce_odr global %"class.Test::ptr" zeroinitializer, comdat, align 4
[e-mail]_ctors = appending global [1 x { i32, void ()*, i8* }] [{ i32, void ()*, i8* } { i32 65535, void ()* @__cxx_global_var_init, i8* bitcast (%"class.Test::ptr"* @C to i8*) }]
+
+define void @testglobfunc() #1 section ".text.startup" comdat($C) {
+entry:
+  ret void
+}
+
+; Function Attrs: noinline uwtable
+define internal void @__cxx_global_var_init() #1 section ".text.startup" comdat($C) {
+entry:
+  store i32 0, i32* getelementptr inbounds (%"class.Test::ptr", %"class.Test::ptr"* @C, i32 0, i32 0), align 4
+  ret void
+}

llvm/trunk/test/LTO/Resolution/X86/comdat-mixed-lto.ll

+; Test of comdat handling with mixed thinlto and regular lto compilation.
+
+; This module is compiled with ThinLTO
+; RUN: opt -module-summary -o %t1.o %s
+; Input module compiled for regular LTO
+; RUN: opt -o %t2.o %p/Inputs/comdat-mixed-lto.ll
+
+; The copy of C from this module is prevailing. The copy of C from the
+; regular LTO module is not prevailing, and will be dropped to
+; available_externally.
+; RUN: llvm-lto2 run -r=%t1.o,C,pl -r=%t2.o,C,l -r=%t2.o,testglobfunc,lxp -r=%t1.o,testglobfunc,lx -o %t3 %t1.o %t2.o -save-temps
+
+; The Input module (regular LTO) is %t3.0. Check to make sure that we removed
+; __cxx_global_var_init and testglobfunc from comdat. Also check to ensure
+; that testglobfunc was dropped to available_externally. Otherwise we would
+; have linker multiply defined errors as it is no longer in a comdat and
+; would clash with the copy from this module.
+; RUN: llvm-dis %t3.0.0.preopt.bc -o - | FileCheck %s
+; CHECK: define internal void @__cxx_global_var_init() section ".text.startup" {
+; CHECK: define available_externally void @testglobfunc() section ".text.startup" {
+
+; ModuleID = 'comdat-mixed-lto.o'
+source_filename = "comdat-mixed-lto.cpp"
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+%"class.Test::ptr" = type { i32 }
+
+$C = comdat any
+
+@C = linkonce_odr global %"class.Test::ptr" zeroinitializer, comdat, align 4
[e-mail]_ctors = appending global [1 x { i32, void ()*, i8* }] [{ i32, void ()*, i8* } { i32 65535, void ()* @__cxx_global_var_init, i8* bitcast (%"class.Test::ptr"* @C to i8*) }]
+define void @testglobfunc() #1 section ".text.startup" comdat($C) {
+entry:
+  ret void
+}
+
+; Function Attrs: noinline uwtable
+define internal void @__cxx_global_var_init() #1 section ".text.startup" comdat($C) {
+entry:
+  ret void
+}