[ThinLTO] Fix import of multiply defined global variables

[krisb]

Summary

Currently, if there is a module that contains a strong definition of
a global variable and a module that has both a weak definition for
the same global and a reference to it, it may result in an undefined symbol error
while linking with ThinLTO.

It happens because:

• the strong definition got internalized because it is read-only and can be imported;
• the weak definition got replaced by a declaration because it's non-prevailing;
• the strong definition failed to be imported because the destination module already contains another definition of the global yet this def is non-prevailing.

The patch adds a check to computeImportForReferencedGlobals() that allows
considering a global variable for being imported even if the module contains
a definition of it in the case this def has an interposable linkage type.

Note that currently the check is based only on the linkage type
(and this seems to be enough), but it might be worth to account the information
whether the def is prevailing or not.

[tejohnson]

Thanks. AFAICT this is a reasonable fix. Suggestion below for a better comment and FIXME to add.

llvm/lib/Transforms/IPO/FunctionImport.cpp

314

Can you add a comment here about how this is required for correctness?
Also, add a FIXME that we can refine this further if we pass down the prevailing symbol information, and only need to allow imports if this is not the prevailing copy, and further if the prevailing copy is marked read only?

[krisb]

Add the comment and FIXME.

[tejohnson]

llvm/lib/Transforms/IPO/FunctionImport.cpp

320

Can you add that this only affects interposable symbols since they are converted to declarations.

321

I think we would still want to check linkage type, since it is only interposable that are converted to declarations. The prevailing information would be useful to refine the extra importing further. Hmm, actually I think there might be a correctness issue with this fix as is. I notice in your test below that the imported symbol becomes internalized. I believe this will need to stay interposable. Normally interposable symbols are blocked from inlining and other IPO since they can be overridden at link time. By making the imported copy internalized, it can now be inlined and no longer overridden at link time. If we did ensure that we imported the prevailing copy this might be ok. However, there are going to be cases where that is not possible (e.g. doing ThinLTO on a shared library link, or if the prevailing copy is in an ELF object/shared library and therefore not available for importing). So I think the best thing here is to ensure that when it gets imported it retains the weak linkage type. I'm not sure if is being internalized in this particular test case because the imported copy is read only - can you confirm where/how that is happening?

[tejohnson]

llvm/lib/Transforms/IPO/FunctionImport.cpp

321

(ignore the comment about inlining, since we're dealing with variables, but other IPO applies)

[krisb]

Thanks, @tejohnson, for reviewing this!
I'll make the comment more accurate.

I think we would still want to check linkage type, since it is only interposable that are converted to declarations. The prevailing information would be useful to refine the extra importing further. Hmm, actually I think there might be a correctness issue with this fix as is. I notice in your test below that the imported symbol becomes internalized. I believe this will need to stay interposable. Normally interposable symbols are blocked from inlining and other IPO since they can be overridden at link time. By making the imported copy internalized, it can now be inlined and no longer overridden at link time. If we did ensure that we imported the prevailing copy this might be ok. However, there are going to be cases where that is not possible (e.g. doing ThinLTO on a shared library link, or if the prevailing copy is in an ELF object/shared library and therefore not available for importing). So I think the best thing here is to ensure that when it gets imported it retains the weak linkage type. I'm not sure if is being internalized in this particular test case because the imported copy is read only - can you confirm where/how that is happening?

The imported copy becomes internal because the source def is read-only indeed (the imported copy inherits 'thinlto-internalize' attribute from the source one thus it got internalized in internalizeGVsAfterImport()). This seems okay since access from an ELF object/shared library prevents the source copy to be marked ReadOnly and at that time we already have attributes propagated.
In general, allow importing here we let it follow the normal importing rules as if the destination module doesn't contain a def at all. So that we will not import another copy with interposable linkage (it doesn't pass the check from canImportGlobalVar()). For other cases, the final linkage type will be whatever FunctionImportGlobalProcessing::getLinkage() returns for the source copy. Unless I'm missing something, this seems to be safe.

[tejohnson]

In D95943#2548382, @krisb wrote:

Thanks, @tejohnson, for reviewing this!
I'll make the comment more accurate.

I think we would still want to check linkage type, since it is only interposable that are converted to declarations. The prevailing information would be useful to refine the extra importing further. Hmm, actually I think there might be a correctness issue with this fix as is. I notice in your test below that the imported symbol becomes internalized. I believe this will need to stay interposable. Normally interposable symbols are blocked from inlining and other IPO since they can be overridden at link time. By making the imported copy internalized, it can now be inlined and no longer overridden at link time. If we did ensure that we imported the prevailing copy this might be ok. However, there are going to be cases where that is not possible (e.g. doing ThinLTO on a shared library link, or if the prevailing copy is in an ELF object/shared library and therefore not available for importing). So I think the best thing here is to ensure that when it gets imported it retains the weak linkage type. I'm not sure if is being internalized in this particular test case because the imported copy is read only - can you confirm where/how that is happening?

The imported copy becomes internal because the source def is read-only indeed (the imported copy inherits 'thinlto-internalize' attribute from the source one thus it got internalized in internalizeGVsAfterImport()). This seems okay since access from an ELF object/shared library prevents the source copy to be marked ReadOnly and at that time we already have attributes propagated.
In general, allow importing here we let it follow the normal importing rules as if the destination module doesn't contain a def at all. So that we will not import another copy with interposable linkage (it doesn't pass the check from canImportGlobalVar()). For other cases, the final linkage type will be whatever FunctionImportGlobalProcessing::getLinkage() returns for the source copy. Unless I'm missing something, this seems to be safe.

Ok I think I have convinced myself that this is correct:

1. If the prevailing copy is not available for import (e.g. in an ELF object), these IR copies would have been marked dead and therefore we would not have marked them as read only.
2. Any copy available for import, i.e. not interposable, would have to be a linkage type that cannot be overridden. So it would have to either be the prevailing copy, or one odr equivalent.

Hmm, it seems like we could do something similar for function importing, to allow importing and inlining of the prevailing copy when the copy in the module is interposable. Can you add a FIXME where we check "if (DefinedGVSummaries.count(VI.getGUID()))" in computeImportForFunction?

[krisb]

Made comments more detailed and acccurate.

[tejohnson]

lgtm with some comment tweaks suggested below for clarity. Thanks!

llvm/lib/Transforms/IPO/FunctionImport.cpp

318

Since the next two points (about the non-prevailing interposable becoming a decl, and then the read-only prevailing being internalized) are both about the correctness and need to go together to create the failure, can you reorder this to:
"This is required for the correctness purpose: First of all, if this copy is non-prevailing...."
Then reorder the second point slightly:
"On the other side, if the prevailing copy is read-only and suitable for import, it will be later internalized and thus not available for linking, and therefore must be imported to satisfy any references."

405

Nit: For clarity, add: "The prevailing copy can safely be imported."

[MaskRay]

llvm/lib/Transforms/IPO/FunctionImport.cpp

314

Nit: flip the condition so that the "then" branch can be deleted, and the comment can be dedented by one level.

[MaskRay]

llvm/test/ThinLTO/X86/weak_globals_import.ll

2

Option: you may consider the split-file utility to keep the auxiliary file in this file. It may help readers in some cases as they don't need to open another file.

[krisb]

Applied review comments, reduced the test.

llvm/lib/Transforms/IPO/FunctionImport.cpp

314

Extracted the check into a separate function. Hope it can be reused for computeImportForFunction() as well.

318

Thank you for the suggestion! I rephrased the comment and hope it's more clear now.

llvm/test/ThinLTO/X86/weak_globals_import.ll

2

Thank you! I haven't heard about split-file.

[tejohnson]

lgtm - thanks!

llvm/lib/Transforms/IPO/FunctionImport.cpp

updateValueInfoForIndirectCalls(const ModuleSummaryIndex &Index, ValueInfo VI) {
   // FIXME: Consider updating the edges in the graph after building
   // it, rather than needing to perform this mapping on each walk.
   auto GUID = Index.getGUIDFromOriginalID(VI.getGUID());
   if (GUID == 0)
     return ValueInfo();
   return Index.getValueInfo(GUID);
 }
 
+static bool shouldImportGlobal(const ValueInfo &VI,
+                               const GVSummaryMapTy &DefinedGVSummaries) {
+  const auto &GVS = DefinedGVSummaries.find(VI.getGUID());
+  if (GVS == DefinedGVSummaries.end())
+    return true;
+  // We should not skip import if the module contains a definition with
+  // interposable linkage type. This is required for correctness in
+  // the situation with two following conditions:
+  // * the def with interposable linkage is non-prevailing,
+  // * there is a prevailing def available for import and marked read-only.
+  // In this case, the non-prevailing def will be converted to a declaration,
+  // while the prevailing one becomes internal, thus no definitions will be
+  // available for linking. In order to prevent undefined symbol link error,
+  // the prevailing definition must be imported.
+  // FIXME: Consider adding a check that the suitable prevailing definition
+  // exists and marked read-only.
+  if (VI.getSummaryList().size() > 1 &&
+      GlobalValue::isInterposableLinkage(GVS->second->linkage()))
+    return true;
+
+  return false;
+}
+
 static void computeImportForReferencedGlobals(
     const GlobalValueSummary &Summary, const ModuleSummaryIndex &Index,
     const GVSummaryMapTy &DefinedGVSummaries,
     SmallVectorImpl<EdgeInfo> &Worklist,
     FunctionImporter::ImportMapTy &ImportList,
     StringMap<FunctionImporter::ExportSetTy> *ExportLists) {
   for (auto &VI : Summary.refs()) {
-    if (DefinedGVSummaries.count(VI.getGUID())) {
+    if (!shouldImportGlobal(VI, DefinedGVSummaries)) {
       LLVM_DEBUG(
           dbgs() << "Ref ignored! Target already in destination module.\n");
       continue;
     }
 
     LLVM_DEBUG(dbgs() << " ref -> " << VI << "\n");
 
     // If this is a local variable, make sure we import the copy
     // in the caller's module. The only time a local variable can
     // share an entry in the index is if there is a local with the same name
     // in another module that had the same source file name (in a different
     // directory), where each was compiled in their own directory so there
     // was not distinguishing path.
     auto LocalNotInModule = [&](const GlobalValueSummary *RefSummary) -> bool {
       return GlobalValue::isLocalLinkage(RefSummary->linkage()) &&
              RefSummary->modulePath() != Summary.modulePath();
     };
 
     for (auto &RefSummary : VI.getSummaryList())
       if (isa<GlobalVarSummary>(RefSummary.get()) &&
           Index.canImportGlobalVar(RefSummary.get(), /* AnalyzeRefs */ true) &&
if (ImportCutoff >= 0 && ImportCount >= ImportCutoff) {
       continue;
     }
 
     VI = updateValueInfoForIndirectCalls(Index, VI);
     if (!VI)
       continue;
 
     if (DefinedGVSummaries.count(VI.getGUID())) {
+      // FIXME: Consider not skipping import if the module contains
+      // a non-prevailing def with interposable linkage. The prevailing copy
+      // can safely be imported (see shouldImportGlobal()).
       LLVM_DEBUG(dbgs() << "ignored! Target already in destination module.\n");
       continue;
     }
 
     auto GetBonusMultiplier = [](CalleeInfo::HotnessType Hotness) -> float {
       if (Hotness == CalleeInfo::HotnessType::Hot)
         return ImportHotMultiplier;
       if (Hotness == CalleeInfo::HotnessType::Cold)

llvm/test/ThinLTO/X86/weak_globals_import.ll

+; RUN: split-file %s %t.dir
+
+; RUN: opt -module-summary %t.dir/1.ll -o %t1.bc
+; RUN: opt -module-summary %t.dir/2.ll -o %t2.bc
+
+; RUN: llvm-lto2 run -save-temps %t1.bc %t2.bc -o %t.out \
+; RUN:               -r=%t1.bc,main,plx \
+; RUN:               -r=%t1.bc,G \
+; RUN:               -r=%t2.bc,G,pl
+; RUN: llvm-dis %t.out.1.3.import.bc -o -  | FileCheck %s
+; RUN: llvm-dis %t.out.2.3.import.bc -o -  | FileCheck %s
+
+; Test that a non-prevailing def with interposable linkage doesn't prevent
+; importing a suitable definition from a prevailing module.
+
+; CHECK: @G = internal local_unnamed_addr global i32 42
+
+;--- 1.ll
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@G = weak dso_local local_unnamed_addr global i32 0, align 4
+
+define dso_local i32 @main() local_unnamed_addr {
+  %1 = load i32, i32* @G, align 4
+  ret i32 %1
+}
+
+;--- 2.ll
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@G = dso_local local_unnamed_addr global i32 42, align 4