ThinLTO: special handling for LinkOnce functions

[mehdi_amini]

Summary

These function can be dropped by the compiler if they are no longer
referenced in the current module. However there is a change that
another module is still referencing them because of the import.

Multiple solutions can be used:

• Always import LinkOnce when a caller is imported. This ensure that every module with a call to a LinkOnce has the definition and will be able to emit it if it emits the call.
• Turn the LinkOnce into Weak, so that it is always emitted.
• Turn all LinkOnce into available_externally and come back after all modules are codegen'ed to emit only one copy of the linkonce, when there is still a reference to it.

This patch implement the second option, with am optimization that
only *one* module will turn the LinkOnce into Weak, while the others
will turn it into available_externally, so that there is exactly one
copy emitted for the whole compilation.

[tejohnson]

Always import LinkOnce when a caller is imported. This ensure that every module with a call to a LinkOnce has the definition and will be able to emit it if it emits the call.

Note that this first approach already happens when using the ModuleLinker (as the function import pass does): referenced linkonce are added to the ValuesToLink via a callback. Which is required for correctness if we end up with any linkonce. But this is an optimization to avoid needing to force import those referenced linkonce.

And this patch also reduces the amount of weak functions kept through codegen (summary should probably reflect that it is modifying weak as well).

lib/LTO/ThinLTOCodeGenerator.cpp

121

Routine is handling more than just linkonce but also weak. Name of this routine and the following one needs to change to reflect broader scope. How about something like "ResolveWeakAndLinkOnce"?

161

This block is almost identical to above, fold the cases together and just select the right Weak linkage?

185

Ditto here, this block can be folded with the above, it is identical.

198

Not really for correctness, as the IRMover will pull in any referenced linkonce defs. This is an optimization to reduce required importing though.

Also, they aren't all being converted to weak ODR, only one and the others are available_externally.

208

Yes I think so

306

More explanatory comment needed.

307

Specify in what way.

[mehdi_amini]

lib/LTO/ThinLTOCodeGenerator.cpp

208

I'm just not sure how to handled them...

307

Yeah, this was mostly a "note to myself".
This is discussed in the caching patch D18494. I'll remove it from here.

[tejohnson]

Couple more comments:

• needs test
• can this be moved out of LTOCodeGenerator so that it can be invoked from other paths (e.g. gold)? Maybe into FunctionImportUtils.cpp?

[mehdi_amini]

I'm surprised you want to use this from the gold plugin, the linker already did the resolution for you. Here I'm using the summary because we don't have an API to interact with the inker.

[tejohnson]

In D18346#386449, @joker.eph wrote:

I'm surprised you want to use this from the gold plugin, the linker already did the resolution for you. Here I'm using the summary because we don't have an API to interact with the inker.

Right, I forgot about the fact that when the backend threads are launched through the gold plugin that it will already make it weak. Gold isn't marking the others available externally, but that should be a simple change.

Where I will want to do something like this is in the distributed build case, where we don't go through the symbol resolution in gold. However, there I will need to mark the change in the combined index and have the backend actually change the symbol linkage based on what is in the index. In that case I would need to refactor this anyway since we don't have an actual GlobalValue, just the summary entries. I can do that myself when I am ready to leverage it.

[tejohnson]

In D18346#387322, @tejohnson wrote:

Right, I forgot about the fact that when the backend threads are launched through the gold plugin that it will already make it weak.

I didn't write this very clearly. It will already mark the *prevailing copy* weak if it is linkonce.

[tejohnson]

lib/LTO/ThinLTOCodeGenerator.cpp

182

Thinking more about this - I don't think it is correct for WeakAny or LinkOnceAny to be converted to AvailableExternally. This could change the program result. The reason is that the selected copy is allowed to have different behavior than the unselected version. This is why WeakAny and LinkOnceAny return true from GlobalValue::mayBeOverridden(), which prevents optimizations such as inlining and therefore ensures that the linker-selected copy is executed. Changing their linkage to AvailableExternally enables the unselected versions to be inlined, and therefore the selected body is not executed at runtime, which can result in different program behavior.

[mehdi_amini]

lib/LTO/ThinLTOCodeGenerator.cpp

182

Yeah that's a very good catch.

It lead me to a more interesting point: if we know which copy the linker will select, we should turn it into a strong definition and *eliminate* all the other. This way the strong one will be imported and could be inlined where it usually can't. I imagine gold is already doing that in LTO.

182

Maybe we can't turn a weak into a strong, because the dynamic loader can override it with another symbol in another library?

[tejohnson]

lib/LTO/ThinLTOCodeGenerator.cpp

182

In LTO mode gold will simply internalize the prevailing copy and the rest get dropped during merging.

What you can do in the non-ODR case is to keep (via weak linkage as you are here) the first copy, and drop the definitions for the other copies (instead of converting them to avail externally). That way the remaining weak copy can still be overridden if necessary by a strong def in another library.

[tejohnson]

See D18674 for related gold changes.

[mehdi_amini]

lib/LTO/ThinLTOCodeGenerator.cpp

182

Makes me think: Is there any interest in importing a weak def somewhere else?
If it is the prevailing copy and we can turn it to a strong def, then yes, otherwise there is not much interest.

[tejohnson]

lib/LTO/ThinLTOCodeGenerator.cpp

182

I'm not sure how common or hot non-overridden weak symbols are in practice. But yes, if we knew it was prevailing (as gold does) then I believe this could be done. But you need the linker to tell you it is the prevailing copy (not just select the first one seen as here).

[mehdi_amini]

lib/LTO/ThinLTOCodeGenerator.cpp

182

I don't know the exact definition of a "prevailing copy"?
If it is only the copy that the linker will put in the final binary, then I don't think it is enough for a weak, because you also need to be sure it can't be overridden by a strong definition by the dynamic loader.

[tejohnson]

lib/LTO/ThinLTOCodeGenerator.cpp

182

I'm not a gold expert, however, given the fact that for LTO the gold-plugin is internalizing the prevailing copy, I would assume that is a guarantee that it will not be overridden elsewhere.

[mehdi_amini]

Address comment, add a test.

[tejohnson]

In D18346#389223, @joker.eph wrote:

Address comment, add a test.

I don't see test, can you try to add again?

lib/LTO/ThinLTOCodeGenerator.cpp

174

Clang format

306

and WeakODR

[tejohnson]

Submitted comments too early - here is the other one...

lib/LTO/ThinLTOCodeGenerator.cpp

217

Alias cannot be available_externally (see GlobalAlias::isValidLinkage), so I think for those you while you should do the change of the first copy to weak, the rest need to be left as-is.

Also, it just occurred to me that this is going to be an issue for the aliasee - since aliases must point to a definition, an aliasee cannot become available_externally either. You might have to do some analysis first to see which GV are aliasees and skip the available_externally part for those too.

You can include these cases in your test.

[mehdi_amini]

Update disable the optimization for aliases

[tejohnson]

I still don't see the test, can you update a new patch with that included?

lib/LTO/ThinLTOCodeGenerator.cpp

176

s/in a/into a/

190

You can still do the conversion of linkonceodr -> weakodr for the first definition, including for aliases themselves. So you could instead continue to call ResolveODR but pass in the new set and just skip the available externally resetting (you'd have to add the aliases themselves to the set as well).

[mehdi_amini]

"git add test/" before commit

[mehdi_amini]

lib/LTO/ThinLTOCodeGenerator.cpp

190

Yeah, but I'd prefer to have the "real" solution we discussed instead of an intermediate one, keeping a limited/conservative behavior in presence of aliases for now.

[mehdi_amini]

Fix Typo

[tejohnson]

lib/LTO/ThinLTOCodeGenerator.cpp

190

Ok, that's fine. Note as an aside that the gold plugin is already doing the linkonce->weak transformation for the prevailing copy, but was motivated by correctness reasons (see D16173 - the preempted copies will get dropped, and since this isn't full LTO the backend doesn't see all references and may otherwise drop the prevailing linkonce copy). Note also that in the future you could do linkonce(any)->weak(any), just not the avail externally part for the non-odr.

[mehdi_amini]

r265190

lib/LTO/ThinLTOCodeGenerator.cpp

static void saveTempBitcode(const Module &TheModule, StringRef TempDir,
   std::error_code EC;
   raw_fd_ostream OS(SaveTempPath.str(), EC, sys::fs::F_None);
   if (EC)
     report_fatal_error(Twine("Failed to open ") + SaveTempPath +
                        " to save optimized bitcode\n");
   WriteBitcodeToFile(&TheModule, OS, true, false);
 }
 
+bool IsFirstDefinitionForLinker(const GlobalValueInfoList &GVInfo,
+                                const ModuleSummaryIndex &Index,
+                                StringRef ModulePath) {
+  // Get the first *linker visible* definition for this global in the summary
+  // list.
+  auto FirstDefForLinker = llvm::find_if(
+      GVInfo, [](const std::unique_ptr<GlobalValueInfo> &FuncInfo) {
+        auto Linkage = FuncInfo->summary()->linkage();
+        return !GlobalValue::isAvailableExternallyLinkage(Linkage);
+      });
+  // If \p GV is not the first definition, give up...
+  if ((*FirstDefForLinker)->summary()->modulePath() != ModulePath)
+    return false;
+  // If there is any strong definition anywhere, do not bother emitting this.
+  if (llvm::any_of(
+          GVInfo, [](const std::unique_ptr<GlobalValueInfo> &FuncInfo) {
+            auto Linkage = FuncInfo->summary()->linkage();
+            return !GlobalValue::isAvailableExternallyLinkage(Linkage) &&
+                   !GlobalValue::isWeakForLinker(Linkage);
+          }))
+    return false;
+  return true;
+};
+
+static void ResolveODR(GlobalValue &GV, const ModuleSummaryIndex &Index,
+                             StringRef ModulePath) {
+  if (GV.isDeclaration())
+    return;
+
+  auto HasMultipleCopies =
+      [&](const GlobalValueInfoList &GVInfo) { return GVInfo.size() > 1; };
+
+  auto getGVInfo = [&](GlobalValue &GV) -> const GlobalValueInfoList *{
+    auto GUID = Function::getGlobalIdentifier(GV.getName(), GV.getLinkage(),
+                                              ModulePath);
+    auto It = Index.findGlobalValueInfoList(GV.getName());
+    if (It == Index.end())
+      return nullptr;
+    return &It->second;
+  };
+
+  switch (GV.getLinkage()) {
+  case GlobalValue::ExternalLinkage:
+  case GlobalValue::AvailableExternallyLinkage:
+  case GlobalValue::AppendingLinkage:
+  case GlobalValue::InternalLinkage:
+  case GlobalValue::PrivateLinkage:
+  case GlobalValue::ExternalWeakLinkage:
+  case GlobalValue::CommonLinkage:
+  case GlobalValue::LinkOnceAnyLinkage:
+  case GlobalValue::WeakAnyLinkage:
+    break;
+  case GlobalValue::LinkOnceODRLinkage:
+  case GlobalValue::WeakODRLinkage: {
+    auto *GVInfo = getGVInfo(GV);
+    if (!GVInfo)
+      break;
+    // We need to emit only one of these, the first module will keep
+    // it, but turned into a weak while the others will drop it.
+    if (!HasMultipleCopies(*GVInfo))
+      break;
+    if (IsFirstDefinitionForLinker(*GVInfo, Index, ModulePath))
+      GV.setLinkage(GlobalValue::WeakODRLinkage);
+    else
+      GV.setLinkage(GlobalValue::AvailableExternallyLinkage);
+    break;
+  }
+  }
+}
+
+/// Resolve LinkOnceODR and WeakODR.
+///
+/// We'd like to drop these function if they are no longer referenced in the
+/// current module. However there is a chance that another module is still
+/// referencing them because of the import. We make sure we always emit at least
+/// one copy.
+static void ResolveODR(Module &TheModule,
+                             const ModuleSummaryIndex &Index) {
+  // We won't optimize the globals that are referenced by an alias for now
+  // Ideally we should turn the alias into a global and duplicate the definition
+  // when needed.
+  DenseSet<GlobalValue *> GlobalInvolvedWithAlias;
+  for (auto &GA : TheModule.aliases()) {
+    auto *GO = GA.getBaseObject();
+    if (auto *GV = dyn_cast<GlobalValue>(GO))
+      GlobalInvolvedWithAlias.insert(GV);
+  }
+  // Process functions and global now
+  for (auto &GV : TheModule) {
+    if (!GlobalInvolvedWithAlias.count(&GV))
+      ResolveODR(GV, Index, TheModule.getModuleIdentifier());
+  }
+  for (auto &GV : TheModule.globals()) {
+    if (!GlobalInvolvedWithAlias.count(&GV))
+      ResolveODR(GV, Index, TheModule.getModuleIdentifier());
+  }
+}
+
 static StringMap<MemoryBufferRef>
 generateModuleMap(const std::vector<MemoryBufferRef> &Modules) {
   StringMap<MemoryBufferRef> ModuleMap;
   for (auto &ModuleBuffer : Modules) {
     assert(ModuleMap.find(ModuleBuffer.getBufferIdentifier()) ==
                ModuleMap.end() &&
            "Expect unique Buffer Identifier");
     ModuleMap[ModuleBuffer.getBufferIdentifier()] = ModuleBuffer;
   }
   return ModuleMap;
 }
 
 /// Provide a "loader" for the FunctionImporter to access function from other
 /// modules.
 class ModuleLoader {
   /// The context that will be used for importing.
   LLVMContext &Context;
 
   /// Map from Module identifier to MemoryBuffer. Used by clients like the
   /// FunctionImported to request loading a Module.
   StringMap<MemoryBufferRef> &ModuleMap;
 
 public:
   ModuleLoader(LLVMContext &Context, StringMap<MemoryBufferRef> &ModuleMap)
       : Context(Context), ModuleMap(ModuleMap) {}
 
   /// Load a module on demand.
   std::unique_ptr<Module> operator()(StringRef Identifier) {
     return loadModuleFromBuffer(ModuleMap[Identifier], Context, /*Lazy*/ true);
   }
 };
ProcessThinLTOModule(Module &TheModule, const ModuleSummaryIndex &Index,
   saveTempBitcode(TheModule, SaveTempsDir, count, ".1.IPO.bc");
 
   // "Benchmark"-like optimization: single-source case
   bool SingleModule = (ModuleMap.size() == 1);
 
   if (!SingleModule) {
     promoteModule(TheModule, Index);
 
+    // Resolve the LinkOnce/Weak ODR, trying to turn them into
+    // "available_externally" when possible.
+    // This is a compile-time optimization.
+    ResolveODR(TheModule, Index);
+
     // Save temps: after promotion.
     saveTempBitcode(TheModule, SaveTempsDir, count, ".2.promoted.bc");
 
     crossImportIntoModule(TheModule, Index, ModuleMap, ImportList);
 
     // Save temps: after cross-module import.
     saveTempBitcode(TheModule, SaveTempsDir, count, ".3.imported.bc");
   }
std::unique_ptr<ModuleSummaryIndex> ThinLTOCodeGenerator::linkCombinedIndex() {
   return CombinedIndex;
 }
 
 /**
  * Perform promotion and renaming of exported internal functions.
  */
 void ThinLTOCodeGenerator::promote(Module &TheModule,
                                    ModuleSummaryIndex &Index) {
+
+  // Resolve the LinkOnceODR, trying to turn them into "available_externally"
+  // where possible.
+  ResolveODR(TheModule, Index);
+
   promoteModule(TheModule, Index);
 }
 
 /**
  * Perform cross-module importing for the module identified by ModuleIdentifier.
  */
 void ThinLTOCodeGenerator::crossModuleImport(Module &TheModule,
                                              ModuleSummaryIndex &Index) {

test/ThinLTO/X86/Inputs/odr_resolution.ll

+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.11.0"
+
+; Alias are not optimized
+@linkoncealias = linkonce_odr alias void (), void ()* @linkonceodrfuncwithalias
+
+; Function with an alias are not optimized
+define linkonce_odr void @linkonceodrfuncwithalias() #0 {
+entry:
+  ret void
+}
+
+define linkonce_odr void @linkonceodrfunc() #0 {
+entry:
+  ret void
+}
+define linkonce void @linkoncefunc() #0 {
+entry:
+  ret void
+}
+define weak_odr void @weakodrfunc() #0 {
+entry:
+  ret void
+}
+define weak void @weakfunc() #0 {
+entry:
+  ret void
+}
+

test/ThinLTO/X86/odr_resolution.ll

+; Do setup work for all below tests: generate bitcode and combined index
+; RUN: llvm-as -module-summary %s -o %t.bc
+; RUN: llvm-as -module-summary %p/Inputs/odr_resolution.ll -o %t2.bc
+; RUN: llvm-lto -thinlto-action=thinlink -o %t3.bc %t.bc %t2.bc
+
+; Verify that only one ODR is selected across modules, but non ODR are not affected.
+; RUN: llvm-lto -thinlto-action=promote %t.bc -thinlto-index=%t3.bc -o - | llvm-dis -o - | FileCheck %s --check-prefix=MOD1
+; RUN: llvm-lto -thinlto-action=promote %t2.bc -thinlto-index=%t3.bc -o - | llvm-dis -o - | FileCheck %s --check-prefix=MOD2
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.11.0"
+
+; Alias are not optimized
+; MOD1: @linkoncealias = linkonce_odr alias void (), void ()* @linkonceodrfuncwithalias
+; MOD2: @linkoncealias = linkonce_odr alias void (), void ()* @linkonceodrfuncwithalias
+@linkoncealias = linkonce_odr alias void (), void ()* @linkonceodrfuncwithalias
+
+; Function with an alias are not optimized
+; MOD1: define linkonce_odr void @linkonceodrfuncwithalias()
+; MOD2: define linkonce_odr void @linkonceodrfuncwithalias()
+define linkonce_odr void @linkonceodrfuncwithalias() #0 {
+entry:
+  ret void
+}
+
+; MOD1: define weak_odr void @linkonceodrfunc()
+; MOD2: define available_externally void @linkonceodrfunc()
+define linkonce_odr void @linkonceodrfunc() #0 {
+entry:
+  ret void
+}
+; MOD1: define linkonce void @linkoncefunc()
+; MOD2: define linkonce void @linkoncefunc()
+define linkonce void @linkoncefunc() #0 {
+entry:
+  ret void
+}
+; MOD1: define weak_odr void @weakodrfunc()
+; MOD2: define available_externally void @weakodrfunc()
+define weak_odr void @weakodrfunc() #0 {
+entry:
+  ret void
+}
+; MOD1: define weak void @weakfunc()
+; MOD2: define weak void @weakfunc()
+define weak void @weakfunc() #0 {
+entry:
+  ret void
+}
+