ThinLTO: Resolve linkonce_odr aliases just like functions

[mehdi_amini]

Summary

D19096 has drifted too much, I'm trying to isolate smaller pieces.
Hopefully this one make sense in isolation.

This help to streamline the process of handling importing since
we don't need to special case alias everywhere: just like
linkonce_odr we are sure we will emit one copy.

[tejohnson]

lib/LTO/ThinLTOCodeGenerator.cpp

161

Since this is a variant of similar handling that used to be here for the aliasee in D19096 (since removed), I will copy over a variant of my suggestion from back then:

I think it would be helpful to add a comment here about how this works. I.e. something like "If a non-imported alias that remains linkonce is referenced by an imported function, the IRMover will create a corresponding ExternalLinkage declaration, which will be satisfied at link time with the copy that was resolved to WeakODR."

[mehdi_amini]

lib/LTO/ThinLTOCodeGenerator.cpp

161

Your sentence is not clear to me, I'm not sure if I misunderstand because it does not seems to apply. See also line 170 for the general explanation that seems to cover what happens here (nothing is really specific to alias for the resolution).

The only specificity here with alias is we can't turn them into available_externally.
We turn ODR functions (even if they have a callee remaining in the current module) into available externally to *force* dropping them.

[tejohnson]

Were you going to move your old test/ThinLTO/X86/alias_resolution.ll from D19096 to here?

lib/LTO/ThinLTOCodeGenerator.cpp

161

True, the same explanation is valid for why the available_externally works since it is discardable as well. I think the explanation at line 170 is sufficient.

[mehdi_amini]

Add back the test

[mehdi_amini]

Are we OK on this one as well?

[tejohnson]

Just a few suggestions on the test case comments.

test/ThinLTO/X86/alias_resolution.ll

8 ↗

(On Diff #54412)

maybe add ", since there is a single copy of each, and they are not exported and discardable" for clarity

35 ↗

(On Diff #54412)

Shouldn't this be:
"Only linkonce_odr alias is resolved in the case when there is a single copy"
I guess this depends on what it means to be "resolved". I took "resolved" to mean we decided which copy to select, which isn't the case for most aliases.

50 ↗

(On Diff #54412)

The word "resolved" here seems contradictory to how it is being used in the rest of the patch. Maybe change this to something like:
" Only import aliases that will not become available_externally, i.e. alias to a linkonce_odr."

[mehdi_amini]

test/ThinLTO/X86/alias_resolution.ll

8 ↗

(On Diff #54412)

The "since there is a single copy of each" part seems irrelevant: this is really about are they exported or not.
And we only import alias when they point to a linkonce_odr function, so these are not exported and won't need to be resolved (I'm not sure if this limitation has any other source than being inherited from the old ModuleLinker).

35 ↗

(On Diff #54412)

Resolved in the sense of the function ResolveODR:

/// 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.

So it is about the aliases being linkonce *and* being exported, that needs to be turned into weak(_odr).

Are we talking about the same "resolve"?

50 ↗

(On Diff #54412)

I should write "The current implementation is limited (for no real reasons) to aliases to linkonce_odr", unless there is something I missed...

[tejohnson]

test/ThinLTO/X86/alias_resolution.ll

8 ↗

(On Diff #54412)

The limitation is due to the linkage changes made when we do the importing, isn't it related to this comment in the function importer?:

+ Alias can't point to "available_externally". However when we import
+ linkOnceODR the linkage does not change. So we import the alias
+ and aliasee only in this case.
+ FIXME: we should import alias as available_externally *function*, the
+ // destination module does need to know it is an alias.

35 ↗

(On Diff #54412)

My point was that some of the above linkonce_odr aliases would also be "resolved" to weak_odr by ResolveODR if there were multiple copies, and they were the first definition for linker. I.e. in this test, the reason why we resolve the below linkonce_odr alias and not the earlier ones is due to the fact that there is a single copy (which is exported).

Also, we're not really resolving anything other than the ODR aliases - the rest are ignored by ResolveODR. So the non linkonce_odr/weak_odr aliases aren't really being resolved are they?

50 ↗

(On Diff #54412)

This is related to the comment I copied in earlier, it is due to the need to replace alias with copy when importing, due to needing to avoid an alias to available_externally, right? I was suggesting that the reason be documented more specifically in the test (we will want to change the test when we can import more aliases).

[mehdi_amini]

test/ThinLTO/X86/alias_resolution.ll

35 ↗

(On Diff #54412)

You're right!

It means I miss a test to check that with multiple aliases, even without import they are resolved. This is purely "resolve on import".

50 ↗

(On Diff #54412)

Yes

[mehdi_amini]

test/ThinLTO/X86/alias_resolution.ll

39 ↗

(On Diff #54412)

There is a bug I think, this one should be promoted right?

[tejohnson]

test/ThinLTO/X86/alias_resolution.ll

39 ↗

(On Diff #54412)

You mean resolved? The alias itself isn't ODR so I think it stays Linkonce(Any).

[mehdi_amini]

test/ThinLTO/X86/alias_resolution.ll

39 ↗

(On Diff #54412)

I think the current situation is murky. Let see if I can summarize it right:

• linkonce (ODR or not) can be discarded: if the symbol is referenced from another module, it needs to be "resolved" for *correctness*.
• weak (ODR or not) can't be discarded: we don't need to resolve them for *correctness*.
• linkonce/weak (the *non* ODR variant) can't be inlined, there is probably no interest in importing them, we should disable that in the importing decision.
• For all of them: we want to resolve when there is more than one definition for compile-time optimization purpose.

[tejohnson]

test/ThinLTO/X86/alias_resolution.ll

39 ↗

(On Diff #54412)

Yes, I think that is a correct summary. So the bug as you point out is in fact that we should be resolving linkonce(any) to weak(any) since it is discardable.

Otherwise if under some situation the call was removed in the original exporting module (not through inlining since that doesn't happen for non-ODR linkonce, but some other transformation), any imported reference that didn't pull in the def can get a linker undef.

So seems we need to do the resolving of linkonce(any) to weak(any) if it is exported. And could do it when there is more than one definition as a compile time optimization.

I remember that in an older version of the patch you were doing this resolution for the non-odr types as well, but I don't remember why you stopped doing that for the WeakAny and LinkOnceAny. Was there an issue that I am not remembering?

[mehdi_amini]

test/ThinLTO/X86/alias_resolution.ll

39 ↗

(On Diff #54412)

I don't remember the history unfortunately.

What I am gonna do is moving forward with this patch, leaving the bug as-is, since it is already existing I think.
I'll implement in a new patch (or a few patches) the proper handling of the 4 points above.

[tejohnson]

test/ThinLTO/X86/alias_resolution.ll

39 ↗

(On Diff #54412)

I don't remember the history unfortunately.

Just looked this up to refresh my memory. This was in the first version of D18346, and here is my comment as to why it wasn't legal to do the part that was converting weakany/linkonceany to available_externally in the multiple definition case:
http://reviews.llvm.org/D18346?id=51265#inline-155935

But as I pointed out later, you can still do the linkonceany->weakany conversion:
http://reviews.llvm.org/D18346?id=51265#inline-156013

I believe that is what is needed here when a linkonceany is exported, for correctness.

What I am gonna do is moving forward with this patch, leaving the bug as-is, since it is already
existing I think.

I don't believe there is a bug in the current upstream head, just in the libLTO case once D19096 goes in and prevents linkonce from being force imported.

I'll implement in a new patch (or a few patches) the proper handling of the 4 points above.

AFAICT the only place we are getting things wrong is with linkonce(any), due to your first point. And that should be easy to fix here - just do the conversion to weakany when the linkonceany is exported. (Then the name should probably be changed from ResolveODR to ResolveWeakLinkOnce or something more broad like that.)

The last point can't be done via available_externally for linkonceany/weakany due to the issue I pointed out in the old patch in the first link above. It could be done via dropping the unselected defs (they can't be inlined anyway), but that is a compile time optimization, not a correctness issue.

[mehdi_amini]

r266958

lib/LTO/ThinLTOCodeGenerator.cpp

if (llvm::any_of(
             auto Linkage = FuncInfo->summary()->linkage();
             return !GlobalValue::isAvailableExternallyLinkage(Linkage) &&
                    !GlobalValue::isWeakForLinker(Linkage);
           }))
     return false;
   return true;
 }
 
-static GlobalValue::LinkageTypes ResolveODR(const ModuleSummaryIndex &Index,
-                                            StringRef ModuleIdentifier,
-                                            GlobalValue::GUID GUID,
-                                            const GlobalValueSummary &GV) {
+static GlobalValue::LinkageTypes
+ResolveODR(const ModuleSummaryIndex &Index,
+           const FunctionImporter::ExportSetTy &ExportList,
+           StringRef ModuleIdentifier, GlobalValue::GUID GUID,
   auto HasMultipleCopies =
       [&](const GlobalValueInfoList &GVInfo) { return GVInfo.size() > 1; };
 
   auto OriginalLinkage = GV.linkage();
   switch (OriginalLinkage) {
   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 = Index.findGlobalValueInfoList(GUID)->second;
     // 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))
+    if (!HasMultipleCopies(GVInfo)) {
+      // Exported LinkonceODR needs to be promoted to not be discarded
+      if (GlobalValue::isDiscardableIfUnused(OriginalLinkage) &&
+          ExportList.count(GUID))
+        return GlobalValue::WeakODRLinkage;
       break;
+    }
     if (IsFirstDefinitionForLinker(GVInfo, Index, ModuleIdentifier))
       return GlobalValue::WeakODRLinkage;
-    else
-      return GlobalValue::AvailableExternallyLinkage;
-    break;
+    else if (isa<AliasSummary>(&GV))
+      // Alias can't be turned into available_externally.
+      return OriginalLinkage;
   }
   }
   return OriginalLinkage;
 }
 
 /// 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(
     const ModuleSummaryIndex &Index,
+    const FunctionImporter::ExportSetTy &ExportList,
     const std::map<GlobalValue::GUID, GlobalValueSummary *> &DefinedGlobals,
     StringRef ModuleIdentifier,
     DenseMap<GlobalValue::GUID, GlobalValue::LinkageTypes> &ResolvedODR) {
   if (Index.modulePaths().size() == 1)
     // Nothing to do if we don't have multiple modules
     return;
 
   // 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<GlobalValueSummary *> GlobalInvolvedWithAlias;
   for (auto &GA : DefinedGlobals) {
     if (auto AS = dyn_cast<AliasSummary>(GA.second))
       GlobalInvolvedWithAlias.insert(&AS->getAliasee());
   }
 
   for (auto &GV : DefinedGlobals) {
     if (GlobalInvolvedWithAlias.count(GV.second))
       continue;
-    auto NewLinkage = ResolveODR(Index, ModuleIdentifier, GV.first, *GV.second);
+    auto NewLinkage =
+        ResolveODR(Index, ExportList, ModuleIdentifier, GV.first, *GV.second);
     if (NewLinkage != GV.second->linkage()) {
       ResolvedODR[GV.first] = NewLinkage;
     }
   }
 }
 
 /// Fixup linkage, see ResolveODR() above.
 void fixupODR(
void fixupODR(
   for (auto &GV : TheModule.globals()) {
     auto NewLinkage = ResolvedODR.find(GV.getGUID());
     if (NewLinkage == ResolvedODR.end())
       continue;
     DEBUG(dbgs() << "ODR fixing up linkage for `" << GV.getName() << "` from "
                  << GV.getLinkage() << " to " << NewLinkage->second << "\n");
     GV.setLinkage(NewLinkage->second);
   }
+  for (auto &GV : TheModule.aliases()) {
+    auto NewLinkage = ResolvedODR.find(GV.getGUID());
+    if (NewLinkage == ResolvedODR.end())
+      continue;
+    DEBUG(dbgs() << "ODR fixing up linkage for `" << GV.getName() << "` from "
+                 << GV.getLinkage() << " to " << NewLinkage->second << "\n");
+    GV.setLinkage(NewLinkage->second);
+  }
 }
 
 static StringMap<MemoryBufferRef>
 generateModuleMap(const std::vector<MemoryBufferRef> &Modules) {
   StringMap<MemoryBufferRef> ModuleMap;
   for (auto &ModuleBuffer : Modules) {
     assert(ModuleMap.find(ModuleBuffer.getBufferIdentifier()) ==
                ModuleMap.end() &&
std::unique_ptr<ModuleSummaryIndex> ThinLTOCodeGenerator::linkCombinedIndex() {
   return CombinedIndex;
 }
 
 /**
  * Perform promotion and renaming of exported internal functions.
  */
 void ThinLTOCodeGenerator::promote(Module &TheModule,
                                    ModuleSummaryIndex &Index) {
+  auto ModuleCount = Index.modulePaths().size();
   auto ModuleIdentifier = TheModule.getModuleIdentifier();
   // Collect for each module the list of function it defines (GUID -> Summary).
   StringMap<std::map<GlobalValue::GUID, GlobalValueSummary *>>
       ModuleToDefinedGVSummaries;
   Index.collectDefinedGVSummariesPerModule(ModuleToDefinedGVSummaries);
 
+  // Generate import/export list
+  StringMap<FunctionImporter::ImportMapTy> ImportLists(ModuleCount);
+  StringMap<FunctionImporter::ExportSetTy> ExportLists(ModuleCount);
+  ComputeCrossModuleImport(Index, ModuleToDefinedGVSummaries, ImportLists,
+                           ExportLists);
+  auto &ExportList = ExportLists[ModuleIdentifier];
+
   // Resolve the LinkOnceODR, trying to turn them into "available_externally"
   // where possible.
   // This is a compile-time optimization.
   DenseMap<GlobalValue::GUID, GlobalValue::LinkageTypes> ResolvedODR;
-  ResolveODR(Index, ModuleToDefinedGVSummaries[ModuleIdentifier],
+  ResolveODR(Index, ExportList, ModuleToDefinedGVSummaries[ModuleIdentifier],
              ModuleIdentifier, ResolvedODR);
   fixupODR(TheModule, ResolvedODR);
 
   promoteModule(TheModule, Index);
 }
 
 /**
  * Perform cross-module importing for the module identified by ModuleIdentifier.
// Parallel optimizer + codegen
     ThreadPool Pool(ThreadCount);
     int count = 0;
     for (auto &ModuleBuffer : Modules) {
       Pool.async([&](int count) {
         LLVMContext Context;
         Context.setDiscardValueNames(LTODiscardValueNames);
         Context.enableDebugTypeODRUniquing();
         auto ModuleIdentifier = ModuleBuffer.getBufferIdentifier();
+        auto &ExportList = ExportLists[ModuleIdentifier];
 
         DenseMap<GlobalValue::GUID, GlobalValue::LinkageTypes> ResolvedODR;
-        ResolveODR(*Index, ModuleToDefinedGVSummaries[ModuleIdentifier],
+        ResolveODR(*Index, ExportList,
+                   ModuleToDefinedGVSummaries[ModuleIdentifier],
                    ModuleIdentifier, ResolvedODR);
 
         // Parse module now
         auto TheModule = loadModuleFromBuffer(ModuleBuffer, Context, false);
 
         // Save temps: original file.
         if (!SaveTempsDir.empty()) {
           saveTempBitcode(*TheModule, SaveTempsDir, count, ".0.original.bc");

test/ThinLTO/X86/odr_resolution.ll

 ; Do setup work for all below tests: generate bitcode and combined index
 ; RUN: opt -module-summary %s -o %t.bc
 ; RUN: opt -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
+; Alias are resolved like functions are: we select one "weak_odr".
+; MOD1: @linkoncealias = weak_odr alias void (), void ()* @linkonceodrfuncwithalias
+; This one wasn't selected, but aliases can't be turned into "available_externally"
 ; 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: