Drop comdats from the dst module if they are not selected

[• rafael]

Summary

A really unfortunate design of llvm-link and related libraries is that they operate one module at a time.

This means they can copy a GV to the destination module that should not be there in the final result because a later bitcode file takes precedence.

We already handled cases like a strong GV replacing a weak for example.

One case that is not currently handled is a comdat replacing another. This doesn't happen in ELF, but with COFF largest selection kind it is possible.

In "llvm-link a.ll b.ll" if the selected comdat was from a.ll, everything will work and we will not copy the comdat from b.ll.

But if we run "llvm-link b.ll a.ll", we fail to delete the already copied comdat from b.ll. This patch fixes that.

[mehdi_amini]

llvm/lib/Linker/LinkModules.cpp

476 ↗

(On Diff #50972)

doc

503 ↗

(On Diff #50972)

What's happening here is not super nice in the alias case, since you're creating a new GlobalVariable to trash it right after.
Can't this be done before the if with an early return like below?

if (!ReplacedDstComdats.count(C))
    return;
if (Declaration->use_empty()) {
    Declaration->eraseFromParent();
    return;
}
  if (auto *F = dyn_cast<Function>(&GV))
    F->deleteBody();
 else if (auto *Var = dyn_cast<GlobalVariable>(&GV)) 
    Var->setInitializer(nullptr);
 else { // alias case
       auto &Alias = cast<GlobalAlias>(GV);
    Module &M = *Alias.getParent();
    PointerType &Ty = *cast<PointerType>(Alias.getType());
    GlobalValue::LinkageTypes L = Alias.getLinkage();
    auto Declaration =
        new GlobalVariable(M, Ty.getElementType(), /*isConstant*/ false, L,
                           /*Initializer*/ nullptr);
    Declaration->takeName(&Alias);
    Alias.replaceAllUsesWith(Declaration);
    Alias.eraseFromParent();
}

[• rafael]

Address review comments.

[tejohnson]

lib/Linker/LinkModules.cpp

105

Needs doxygen comment

479

nit: just invoke Alias.getLinkage() in below constructor call and remove local L.

Also is it even correct to use the original linkage as-is in all cases? Should it be ExternalLinkage?

Finally, what if this is ThinLTO and the alias was defined in the original module we are importing into? Won't we have an undef at link time? Ditto for full LTO - where would this new declaration be defined? I'm not even sure what the right behavior is in that case.

481

What if this was a function alias not variable alias?

541

Why not combine this into the above loop? I.e. when the ComdatsChosen array is initialized for C, you already have its LinkFromSrc. And that step is done exactly once for each comdat due to the earlier check that continues if C is already in ComdatsChosen.

546

Just invoke C->getName() and remove ComdatName local?

test/Linker/comdat-rm-dst.ll

13

s/ailas/alias/ to get desired check

[tejohnson]

lib/Linker/LinkModules.cpp

479

Finally, what if this is ThinLTO and the alias was defined in the original module we are importing into? Won't we have an undef at link time? Ditto for full LTO - where would this new declaration be defined? I'm not even sure what the right behavior is in that case.

Should the original dest aliasee simply be removed from the comdat, renamed if necessary, and the alias still use it?

Otherwise it isn't clear to me where these are being defined.

[• rafael]

Also is it even correct to use the original linkage as-is in all cases? Should it be ExternalLinkage?

Good catch. I was expecting the verifier to catch out of comdat
references to locals, but it doesn't.

Finally, what if this is ThinLTO and the alias was defined in the original module we are importing into? Won't we have an undef at link time? Ditto for full LTO - where would this new declaration be defined? I'm not even sure what the right behavior is in that case.

With comdats the same symbols have to be defined in the comdat group
we selected. If that is not the case, an undefined error is the
correct result. The ELF wording is:

---

A symbol table entry with STB_GLOBAL or STB_WEAK binding that is
defined relative to one of a group's sections, and that is contained
in a symbol table section that is not part of the group, must be
converted to an undefined symbol (its section index must be changed to
SHN_UNDEF) if the group members are discarded. References to this

symbol table entry from outside the group are allowed.

Comment at: lib/Linker/LinkModules.cpp:479
@@ +478,3 @@
+ GlobalValue *Declaration =
+ new GlobalVariable(M, Ty.getElementType(), /*isConstant*/ false, L,

+ /*Initializer*/ nullptr);

What if this was a function alias not variable alias?

That is fine. It is a bit odd that we have declaration versions of 2
of the 3 GlobalObjects (there should be only 1 IMHO), but the linker
can handle a mismatch.

Comment at: lib/Linker/LinkModules.cpp:504
@@ +503,3 @@
+ bool LinkFromSource = P.second.second;
+ if (!LinkFromSource)

+ continue;

Why not combine this into the above loop? I.e. when the ComdatsChosen array is initialized for C, you already have its LinkFromSrc. And that step is done exactly once for each comdat due to the earlier check that continues if C is already in ComdatsChosen.

Excellent suggestion. Thanks!

I will upload a new patch in a sec.

[tejohnson]

LGTM with a couple small nits.

lib/Linker/LinkModules.cpp

519

s/no able/not able/

test/Linker/comdat-rm-dst.ll

3

Why can't these two FileCheck invocations be combined? They are scanning the same output file.

[mehdi_amini]

llvm/lib/Linker/LinkModules.cpp

503 ↗

(On Diff #50972)

ping?

[mehdi_amini]

I have to learn how to use phabricator, wasn't looking at the right diff...

lib/Linker/LinkModules.cpp

GlobalValue *getLinkedToGlobal(const GlobalValue *SrcGV) {
     // internal linkage, we are really not doing any linkage here.
     if (DGV->hasLocalLinkage())
       return nullptr;
 
     // Otherwise, we do in fact link to the destination global.
     return DGV;
   }
 
+  /// Drop GV if it is a member of a comdat that we are dropping.
+  /// This can happen with COFF's largest selection kind.
+  void dropReplacedComdat(GlobalValue &GV,
+                          const DenseSet<const Comdat *> &ReplacedDstComdats);
+
   bool linkIfNeeded(GlobalValue &GV);
 
   /// Helper method to check if we are importing from the current source
   /// module.
   bool isPerformingImport() const { return GlobalsToImport != nullptr; }
 
   /// If we are importing from the source module, checks if we should
   /// import SGV as a definition, otherwise import as a declaration.
if (!SC)
     return;
   for (GlobalValue *GV2 : ComdatMembers[SC]) {
     if (!GV2->hasLocalLinkage() && shouldInternalizeLinkedSymbols())
       Internalize.insert(GV2->getName());
     Add(*GV2);
   }
 }
 
+void ModuleLinker::dropReplacedComdat(
+    GlobalValue &GV, const DenseSet<const Comdat *> &ReplacedDstComdats) {
+  Comdat *C = GV.getComdat();
+  if (!C)
+    return;
+  if (!ReplacedDstComdats.count(C))
+    return;
+  if (GV.use_empty()) {
+    GV.eraseFromParent();
+    return;
+  }
+
+  if (auto *F = dyn_cast<Function>(&GV)) {
+    F->deleteBody();
+  } else if (auto *Var = dyn_cast<GlobalVariable>(&GV)) {
+    Var->setInitializer(nullptr);
+  } else {
+    auto &Alias = cast<GlobalAlias>(GV);
+    Module &M = *Alias.getParent();
+    PointerType &Ty = *cast<PointerType>(Alias.getType());
+    GlobalValue *Declaration;
+    if (auto *FTy = dyn_cast<FunctionType>(Alias.getValueType())) {
+      Declaration = Function::Create(FTy, GlobalValue::ExternalLinkage, "", &M);
+    } else {
+      Declaration =
+          new GlobalVariable(M, Ty.getElementType(), /*isConstant*/ false,
+                             GlobalValue::ExternalLinkage,
+                             /*Initializer*/ nullptr);
+    }
+    Declaration->takeName(&Alias);
+    Alias.replaceAllUsesWith(Declaration);
+    Alias.eraseFromParent();
+  }
+}
+
 bool ModuleLinker::run() {
+  Module &DstM = Mover.getModule();
+  DenseSet<const Comdat *> ReplacedDstComdats;
+
   for (const auto &SMEC : SrcM->getComdatSymbolTable()) {
     const Comdat &C = SMEC.getValue();
     if (ComdatsChosen.count(&C))
       continue;
     Comdat::SelectionKind SK;
     bool LinkFromSrc;
     if (getComdatResult(&C, SK, LinkFromSrc))
       return true;
     ComdatsChosen[&C] = std::make_pair(SK, LinkFromSrc);
+
+    if (!LinkFromSrc)
+      continue;
+
+    Module::ComdatSymTabType &ComdatSymTab = DstM.getComdatSymbolTable();
+    Module::ComdatSymTabType::iterator DstCI = ComdatSymTab.find(C.getName());
+    if (DstCI == ComdatSymTab.end())
+      continue;
+
+    // The source comdat is replacing the dest one.
+    const Comdat *DstC = &DstCI->second;
+    ReplacedDstComdats.insert(DstC);
+  }
+
+  // Alias have to go first, since we are no able to find their comdats
+  // otherwise.
+  for (auto I = DstM.alias_begin(), E = DstM.alias_end(); I != E;) {
+    GlobalAlias &GV = *I++;
+    dropReplacedComdat(GV, ReplacedDstComdats);
+  }
+
+  for (auto I = DstM.global_begin(), E = DstM.global_end(); I != E;) {
+    GlobalVariable &GV = *I++;
+    dropReplacedComdat(GV, ReplacedDstComdats);
+  }
+
+  for (auto I = DstM.begin(), E = DstM.end(); I != E;) {
+    Function &GV = *I++;
+    dropReplacedComdat(GV, ReplacedDstComdats);
   }
 
   for (GlobalVariable &GV : SrcM->globals())
     if (const Comdat *SC = GV.getComdat())
       ComdatMembers[SC].push_back(&GV);
 
   for (Function &SF : *SrcM)
     if (const Comdat *SC = SF.getComdat())
       ComdatMembers[SC].push_back(&SF);
 
   for (GlobalAlias &GA : SrcM->aliases())
     if (const Comdat *SC = GA.getComdat())
       ComdatMembers[SC].push_back(&GA);
 
   // Insert all of the globals in src into the DstM module... without linking
   // initializers (which could refer to functions not yet mapped over).
   for (GlobalVariable &GV : SrcM->globals())
     if (linkIfNeeded(GV))
       return true;
 
   for (Function &SF : *SrcM)
bool ModuleLinker::run() {
   }
 
   if (Mover.move(std::move(SrcM), ValuesToLink.getArrayRef(),
                  [this](GlobalValue &GV, IRMover::ValueAdder Add) {
                    addLazyFor(GV, Add);
                  },
                  ValIDToTempMDMap, false))
     return true;
-  Module &DstM = Mover.getModule();
   for (auto &P : Internalize) {
     GlobalValue *GV = DstM.getNamedValue(P.first());
     GV->setLinkage(GlobalValue::InternalLinkage);
   }
 
   return false;
 }
 

test/Linker/Inputs/comdat-rm-dst.ll

+target datalayout = "e-m:w-p:32:32-i64:64-f80:32-n8:16:32-S32"
+target triple = "i686-pc-windows-msvc"
+
+$foo = comdat largest
+@foo = global i64 43, comdat

test/Linker/comdat-rm-dst.ll

+; RUN: llvm-link -S -o %t %s %p/Inputs/comdat-rm-dst.ll
+; RUN: FileCheck %s < %t
+; RUN: FileCheck --check-prefix=RM %s < %t
+
+target datalayout = "e-m:w-p:32:32-i64:64-f80:32-n8:16:32-S32"
+target triple = "i686-pc-windows-msvc"
+
+$foo = comdat largest
+@foo = global i32 42, comdat
+; CHECK-DAG: @foo = global i64 43, comdat
+
+; RM-NOT: @alias =
+@alias = alias i32, i32* @foo
+
+; We should arguably reject an out of comdat reference to int_alias. Given that
+; the verifier accepts it, test that we at least produce an output that passes
+; the verifier.
+; CHECK-DAG: @int_alias = external global i32
+@int_alias = internal alias i32, i32* @foo
+@bar = global i32* @int_alias
+
+@func_alias = alias void (), void ()* @func
+@zed = global void()* @func_alias
+; CHECK-DAG: @zed = global void ()* @func_alias
+; CHECK-DAG: declare void @func_alias()
+
+; RM-NOT: @func()
+define void @func() comdat($foo) {
+  ret void
+}
+
+; RM-NOT: var
+@var = global i32 42, comdat($foo)