Move comdat setup after global value body linking in ModuleLinker

[tejohnson]

Summary

The verifier complains if a declaration is in a comdat. However,
the module linker speculatively adds linked global values that are
in comdats in the source module into comdats in the destination module,
which assumes their bodies will also be linked.

For ThinLTO we may not link the body if it isn't an imported function.
Also, with currently reverted patch r251926 (D14195: Move metadata
linking after lazy global materialization/linking), during an LTO build
a function referenced only from metadata will not have its definition
linked and will become a declaration. If it was in a comdat it will also
hit the verifier error.

To handle this, delay setting up comdats on the Dest module until after
all global value bodies have been linked, so that we know which are
definitions vs declarations in Dest.

This change is an enabler for resubmitting r251926, and also for some
follow-on fixes for ThinLTO comdat handling I discovered in the process
of working on these changes.

[dexonsmith]

This seems reasonable to me, but we don't have comdats in Mach-O (I know they're similar to linkonce/etc., but don't really understand the full semantics) so I'm not sure I'm the best person to review this.

Rafael, maybe you could have a look?

[mehdi_amini]

lib/Linker/LinkModules.cpp

2007

Is is possible to just iterate over ComdatsChosen?

[tejohnson]

lib/Linker/LinkModules.cpp

2007

I don't think that is straightforward since AFAIK there is no way to get directly from the comdat to all the global values that are in the comdat.

[tobiasvk]

lib/Linker/LinkModules.cpp

2007

Purely stylistic.. omit braces on the single-statement for loops. Otherwise, makes sense!

[• rafael]

It has been awhile since I looked at lib/Linker, but correct if I am wrong, it has pretty much two modes

• "real" linker semantics. This handles comdats, weaks, etc.
• A mode where we only copy a user specified list of GVs and internal dependencies.

The second mode is used by thin lto. It could also be used with a few modifications by the gold plugin since gold did the "real linker" work already.

It looks like both modes are somewhat mixed. Could the linker be split in two? The low level one gets a list of globals. The high level one is not used by thinlto. What it does is decide based on comdats and linkages what a real linker would do and pass that list to the lower level class.

[tejohnson]

Following up after discussing with Rafael on IRC.

Splitting the linker will require quite a bit of work since LTO discovers what symbols it needs as it copies in function bodies.

As an alternative to this patch:

1. For ThinLTO we can strip decls from comdats if we aren't importing that comdat group (note that the importer eventually needs to import the entire comdat group to get correct linker behavior).
2. For LTO (and llvm-lto -only-needed) this situation only arises with my currently reverted patch D14195 to move metadata linking after all global value body linking when there is metadata that references a non-materialized global. At HEAD, a metadata reference causes the def to be linked in, which is unnecessary. With D14195 it was just leaving a decl. This caused LTO bootstrapping issues for global values in comdats which can't be decls (and aliases - which requires a separate fix to turn those into non-alias decls). The question is what to do about these metadata references - I assume they need to reference something in the dest module. Eventually with a follow on patch I have support for not linking in DISubprogram metadata that isn't needed. We would need to do the same for references to unmaterialized variables from DIVariable (any other metadata that can reference GVs?). These would have to be done along with the patch to move the metadata linking. For now, maybe just strip the decls from comdats in this case as well, but this assumes that the unreferenced global values and associated metadata will be removed by a later pass. Any other suggestions?

[tejohnson]

Based on discussions with Rafael and Duncan, I am going to abandon this change. See the new fix for the LTO bootstrapping issue suggested by Duncan included with D14447. I will fix the ThinLTO comdat issue in a separate patch that has some other fixes for comdats.

lib/Linker/LinkModules.cpp

 namespace {
 class ModuleLinker;
 
 /// Creates prototypes for functions that are lazily linked on the fly. This
 /// speeds up linking for modules with many/ lazily linked functions of which
 /// few get used.
 class ValueMaterializerTy final : public ValueMaterializer {
   TypeMapTy &TypeMap;
-  Module *DstM;
   std::vector<GlobalValue *> &LazilyLinkGlobalValues;
   ModuleLinker *ModLinker;
 
 public:
-  ValueMaterializerTy(TypeMapTy &TypeMap, Module *DstM,
+  ValueMaterializerTy(TypeMapTy &TypeMap,
                       std::vector<GlobalValue *> &LazilyLinkGlobalValues,
                       ModuleLinker *ModLinker)
-      : ValueMaterializer(), TypeMap(TypeMap), DstM(DstM),
+      : ValueMaterializer(), TypeMap(TypeMap),
         LazilyLinkGlobalValues(LazilyLinkGlobalValues), ModLinker(ModLinker) {}
 
   Value *materializeValueFor(Value *V) override;
 };
 
 class LinkDiagnosticInfo : public DiagnosticInfo {
   const Twine &Msg;
 
class ModuleLinker {
   bool HasExportedFunctions;
 
 public:
   ModuleLinker(Module *dstM, Linker::IdentifiedStructTypeSet &Set, Module *srcM,
                DiagnosticHandlerFunction DiagnosticHandler, unsigned Flags,
                FunctionInfoIndex *Index = nullptr,
                Function *FuncToImport = nullptr)
       : DstM(dstM), SrcM(srcM), TypeMap(Set),
-        ValMaterializer(TypeMap, DstM, LazilyLinkGlobalValues, this),
+        ValMaterializer(TypeMap, LazilyLinkGlobalValues, this),
         DiagnosticHandler(DiagnosticHandler), Flags(Flags), ImportIndex(Index),
         ImportFunction(FuncToImport), HasExportedFunctions(false) {
     assert((ImportIndex || !ImportFunction) &&
            "Expect a FunctionInfoIndex when importing");
     // If we have a FunctionInfoIndex but no function to import,
     // then this is the primary module being compiled in a ThinLTO
     // backend compilation, and we need to see if it has functions that
     // may be exported to another backend compilation.
private:
 
   void linkAppendingVarInit(const AppendingVarInfo &AVI);
 
   void linkGlobalInit(GlobalVariable &Dst, GlobalVariable &Src);
   bool linkFunctionBody(Function &Dst, Function &Src);
   void linkAliasBody(GlobalAlias &Dst, GlobalAlias &Src);
   bool linkGlobalValueBody(GlobalValue &Src);
 
+  void copyComdat(GlobalValue &SGV);
+
   /// Functions that take care of cloning a specific global value type
   /// into the destination module.
   GlobalVariable *copyGlobalVariableProto(TypeMapTy &TypeMap,
                                           const GlobalVariable *SGVar);
   Function *copyFunctionProto(TypeMapTy &TypeMap, const Function *SF);
   GlobalValue *copyGlobalAliasProto(TypeMapTy &TypeMap, const GlobalAlias *SGA);
 
   /// Helper methods to check if we are importing from or potentially

 
 Value *ValueMaterializerTy::materializeValueFor(Value *V) {
   auto *SGV = dyn_cast<GlobalValue>(V);
   if (!SGV)
     return nullptr;
 
   GlobalValue *DGV = ModLinker->copyGlobalValueProto(TypeMap, SGV);
 
-  if (Comdat *SC = SGV->getComdat()) {
-    if (auto *DGO = dyn_cast<GlobalObject>(DGV)) {
-      Comdat *DC = DstM->getOrInsertComdat(SC->getName());
-      DGO->setComdat(DC);
-    }
-  }
-
   LazilyLinkGlobalValues.push_back(SGV);
   return DGV;
 }
 
 bool ModuleLinker::getComdatLeader(Module *M, StringRef ComdatName,
                                    const GlobalVariable *&GVar) {
   const GlobalValue *GVal = M->getNamedValue(ComdatName);
   if (const auto *GA = dyn_cast_or_null<GlobalAlias>(GVal)) {
if (SGV->hasAppendingLinkage() && isPerformingImport()) {
     DoNotLinkFromSource.insert(SGV);
     return false;
   }
   if (DGV && DGV->hasAppendingLinkage())
     return linkAppendingVarProto(cast<GlobalVariable>(DGV),
                                  cast<GlobalVariable>(SGV));
 
   bool LinkFromSrc = true;
-  Comdat *C = nullptr;
   bool HasUnnamedAddr = SGV->hasUnnamedAddr();
 
   if (const Comdat *SC = SGV->getComdat()) {
     Comdat::SelectionKind SK;
     std::tie(SK, LinkFromSrc) = ComdatsChosen[SC];
-    C = DstM->getOrInsertComdat(SC->getName());
-    C->setSelectionKind(SK);
   } else if (DGV) {
     if (shouldLinkFromSource(LinkFromSrc, *DGV, *SGV))
       return true;
   }
 
   if (!LinkFromSrc) {
     // Track the source global so that we don't attempt to copy it over when
     // processing global initializers.
if (!LinkFromSrc) {
     if (DGV && isa<Function>(DGV))
       if (auto *NewF = dyn_cast<Function>(NewGV))
         OverridingFunctions.insert(NewF);
   }
 
   NewGV->setUnnamedAddr(HasUnnamedAddr);
 
   if (auto *NewGO = dyn_cast<GlobalObject>(NewGV)) {
-    if (C)
-      NewGO->setComdat(C);
 
     if (DGV && DGV->hasCommonLinkage() && SGV->hasCommonLinkage())
       NewGO->setAlignment(std::max(DGV->getAlignment(), SGV->getAlignment()));
   }
 
   if (auto *NewGVar = dyn_cast<GlobalVariable>(NewGV)) {
     auto *DGVar = dyn_cast_or_null<GlobalVariable>(DGV);
     auto *SGVar = dyn_cast<GlobalVariable>(SGV);
bool ModuleLinker::linkGlobalValueBody(GlobalValue &Src) {
   if (auto *GVar = dyn_cast<GlobalVariable>(&Src)) {
     linkGlobalInit(cast<GlobalVariable>(*Dst), *GVar);
     return false;
   }
   linkAliasBody(cast<GlobalAlias>(*Dst), cast<GlobalAlias>(Src));
   return false;
 }
 
+/// For any Src comdats with an associated definition in the Dest module,
+/// setup the corresponding comdat in Dest.
+void ModuleLinker::copyComdat(GlobalValue &SGV) {
+  const Comdat *SC = SGV.getComdat();
+  if (!SC)
+    return;
+  // See if there is an associated definition now in the Dest module.
+  // If so, make sure Dest copy is also in a comdat.
+  GlobalValue *DGV = DstM->getNamedValue(getName(&SGV));
+  auto *GO = dyn_cast_or_null<GlobalObject>(DGV);
+  if (!GO || GO->isDeclaration())
+    return;
+  Comdat::SelectionKind SK;
+  bool LinkFromSrc = true;
+  std::tie(SK, LinkFromSrc) = ComdatsChosen[SC];
+  Comdat *C = DstM->getOrInsertComdat(SC->getName());
+  C->setSelectionKind(SK);
+  assert(!GO->hasComdat() || GO->getComdat() == C);
+  GO->setComdat(C);
+}
+
 /// Insert all of the named MDNodes in Src into the Dest module.
 void ModuleLinker::linkNamedMDNodes() {
   const NamedMDNode *SrcModFlags = SrcM->getModuleFlagsMetadata();
   for (const NamedMDNode &NMD : SrcM->named_metadata()) {
     // Don't link module flags here. Do them separately.
     if (&NMD == SrcModFlags)
       continue;
     NamedMDNode *DestNMD = DstM->getOrInsertNamedMetadata(NMD.getName());
bool ModuleLinker::run() {
   // If there were any aliases, link them now.
   for (GlobalAlias &GA : SrcM->aliases())
     if (linkGlobalValueProto(&GA))
       return true;
 
   for (const AppendingVarInfo &AppendingVar : AppendingVars)
     linkAppendingVarInit(AppendingVar);
 
-  for (const auto &Entry : DstM->getComdatSymbolTable()) {
+
+  // Ensure values from comdats with specific selection critera
+  // are mapped, and therefore materialized/lazy linked in Dest.
+  for (const auto &Entry : SrcM->getComdatSymbolTable()) {
     const Comdat &C = Entry.getValue();
-    if (C.getSelectionKind() == Comdat::Any)
+    bool LinkFromSrc = true;
+    Comdat::SelectionKind SK;
+    std::tie(SK, LinkFromSrc) = ComdatsChosen[&C];
+    if (SK == Comdat::Any)
       continue;
     const GlobalValue *GV = SrcM->getNamedValue(C.getName());
-    if (GV)
-      MapValue(GV, ValueMap, RF_MoveDistinctMDs, &TypeMap, &ValMaterializer);
+    assert(GV);
   }
 
   // Strip replaced subprograms before mapping any metadata -- so that we're
   // not changing metadata from the source module (note that
   // linkGlobalValueBody() eventually calls RemapInstruction() and therefore
   // MapMetadata()) -- but after linking global value protocols -- so that
   // OverridingFunctions has been built.
   stripReplacedSubprograms();
while (!LazilyLinkGlobalValues.empty()) {
     if (shouldLinkOnlyNeeded() && SGV->isDeclaration())
       continue;
 
     assert(!SGV->isDeclaration() && "users should not pass down decls");
     if (linkGlobalValueBody(*SGV))
       return true;
   }
 
+  // Now that we have linked in all needed global value bodies from Src,
+  // ensure that comdat information is copied for definitions in the Dest
+  // module.
+  for (GlobalVariable &SGV : SrcM->globals()) {
+    copyComdat(SGV);
+  }
+  for (Function &SF : *SrcM) {
+    copyComdat(SF);
+  }
+  for (GlobalAlias &SGA : SrcM->aliases()) {
+    copyComdat(SGA);
+  }
+
   return false;
 }
 
 Linker::StructTypeKeyInfo::KeyTy::KeyTy(ArrayRef<Type *> E, bool P)
     : ETypes(E), IsPacked(P) {}
 
 Linker::StructTypeKeyInfo::KeyTy::KeyTy(const StructType *ST)
     : ETypes(ST->elements()), IsPacked(ST->isPacked()) {}

test/Linker/funcimport.ll

 ; Do setup work for all below tests: generate bitcode and combined index
 ; RUN: llvm-as -function-summary %s -o %t.bc
 ; RUN: llvm-as -function-summary %p/Inputs/funcimport.ll -o %t2.bc
 ; RUN: llvm-lto -thinlto -o %t3 %t.bc %t2.bc
 
 ; Ensure statics are promoted/renamed correctly from this file (all but
 ; constant variable need promotion).
 ; RUN: llvm-link %t.bc -functionindex=%t3.thinlto.bc -S | FileCheck %s --check-prefix=EXPORTSTATIC
 ; EXPORTSTATIC: @staticvar.llvm.1 = hidden global
 ; EXPORTSTATIC: @staticconstvar = internal unnamed_addr constant
 ; EXPORTSTATIC: @P.llvm.1 = hidden global void ()* null
 ; EXPORTSTATIC: define hidden i32 @staticfunc.llvm.1
 ; EXPORTSTATIC: define hidden void @staticfunc2.llvm.1
 
+; Ensure linking of linkonce functions and alias in a comdat works.
+; RUN: llvm-link %t2.bc -functionindex=%t3.thinlto.bc -import=linkoncecomdatfunc:%t.bc -S | FileCheck %s --check-prefix=IMPORTLINKONCECOMDAT
+; IMPORTLINKONCECOMDAT: @linkoncecomdatalias = alias void (...), bitcast (void ()* @linkoncecomdatfunc
+; IMPORTLINKONCECOMDAT: define linkonce_odr void @linkoncecomdatfunc() comdat
+
+; Ensure linking of linkonce functions and alias in a comdat works as a
+; second pass import.
+; RUN: llvm-link %t2.bc -functionindex=%t3.thinlto.bc -import=globalfunc1:%t.bc -import=linkoncecomdatfunc:%t.bc -S | FileCheck %s --check-prefix=IMPORTLINKONCECOMDAT2
+; IMPORTLINKONCECOMDAT2: @linkoncecomdatalias = alias void (...), bitcast (void ()* @linkoncecomdatfunc
+; IMPORTLINKONCECOMDAT2: define linkonce_odr void @linkoncecomdatfunc() comdat
+
 ; Ensure that both weak alias to an imported function and strong alias to a
 ; non-imported function are correctly turned into declarations.
-; Also ensures that alias to a linkonce function is turned into a declaration
-; and that the associated linkonce function is not in the output, as it is
-; lazily linked and never referenced/materialized.
+; Also ensures that aliases to linkonce functions are turned into non-comdat
+; declarations and that the associated linkonce functions are not in the output,
+; as they are lazily linked and never referenced/materialized.
 ; RUN: llvm-link %t2.bc -functionindex=%t3.thinlto.bc -import=globalfunc1:%t.bc -S | FileCheck %s --check-prefix=IMPORTGLOB1
 ; IMPORTGLOB1: define available_externally void @globalfunc1
 ; IMPORTGLOB1: declare void @globalfunc2
 ; IMPORTGLOB1: declare extern_weak void @weakalias
 ; IMPORTGLOB1: declare void @analias
 ; IMPORTGLOB1: declare void @linkoncealias
+; IMPORTGLOB1: declare void @linkoncecomdatalias
 ; IMPORTGLOB1-NOT: @linkoncefunc
+; IMPORTGLOB1-NOT: @linkoncecomdatfunc
 
 ; Ensure that weak alias to a non-imported function is correctly
 ; turned into a declaration, but that strong alias to an imported function
 ; is imported as alias.
 ; RUN: llvm-link %t2.bc -functionindex=%t3.thinlto.bc -import=globalfunc2:%t.bc -S | FileCheck %s --check-prefix=IMPORTGLOB2
 ; IMPORTGLOB2: @analias = alias void (...), bitcast (void ()* @globalfunc2
 ; IMPORTGLOB2: declare void @globalfunc1
 ; IMPORTGLOB2: define available_externally void @globalfunc2

 @staticvar = internal global i32 1, align 4
 @staticconstvar = internal unnamed_addr constant [2 x i32] [i32 10, i32 20], align 4
 @commonvar = common global i32 0, align 4
 @P = internal global void ()* null, align 8
 
 @weakalias = weak alias void (...), bitcast (void ()* @globalfunc1 to void (...)*)
 @analias = alias void (...), bitcast (void ()* @globalfunc2 to void (...)*)
 @linkoncealias = alias void (...), bitcast (void ()* @linkoncefunc to void (...)*)
+@linkoncecomdatalias = alias void (...), bitcast (void ()* @linkoncecomdatfunc to void (...)*)
 
 define void @globalfunc1() #0 {
 entry:
   ret void
 }
 
 define void @globalfunc2() #0 {
 entry:
   ret void
 }
 
 define linkonce_odr void @linkoncefunc() #0 {
 entry:
   ret void
 }
 
+$linkoncecomdatfunc = comdat any
+define linkonce_odr void @linkoncecomdatfunc() #0 comdat {
+entry:
+  ret void
+}
+
 define i32 @referencestatics(i32 %i) #0 {
 entry:
   %i.addr = alloca i32, align 4
   store i32 %i, i32* %i.addr, align 4
   %call = call i32 @staticfunc()
   %0 = load i32, i32* @staticvar, align 4
   %add = add nsw i32 %call, %0
   %1 = load i32, i32* %i.addr, align 4