[ThinLTO] - Stop internalizing and drop non-prevailing symbols.

[grimar]

Summary

Implementation marks non-prevailing symbols as not live in the summary.
Then them are dropped in backends.

[evgeny777]

@grimar Can't internalization be skipped during backend processing rather than changing linkage in summary index?. At the very first glance it is possible to check if def is prevailing or not in MustPreserveGV (see thinLTOInternalizeModule)

[grimar]

In D42107#977115, @evgeny777 wrote:

@grimar Can't internalization be skipped during backend processing rather than changing linkage in summary index?. At the very first glance it is possible to check if def is prevailing or not in MustPreserveGV (see thinLTOInternalizeModule)

Investigating this. Hope to update patch tomorrow.

[tejohnson]

In D42107#977115, @evgeny777 wrote:

@grimar Can't internalization be skipped during backend processing rather than changing linkage in summary index?. At the very first glance it is possible to check if def is prevailing or not in MustPreserveGV (see thinLTOInternalizeModule)

We don't have linker info in the backends, so that code is just looking at what was recorded in the index during the thin link (where we have the linker info).

lib/LTO/LTO.cpp

333

We also need to change importing to not allow import of a non-prevailing symbol. Then this patch should be changed to assert if it was non-prevailing but exported.

[evgeny777]

@tejohnson Can't we use ThinLTO.PrevailingModuleForGUID in the backend?

[tejohnson]

In D42107#979102, @evgeny777 wrote:

@tejohnson Can't we use ThinLTO.PrevailingModuleForGUID in the backend?

No - we communicate via the index to support distributed ThinLTO backends.

To drop non-prevailing symbols completely in the backends, as discussed in D41988, we will need to either add a bit to the summary flags, or possibly we can utilize the isLive flag (which currently is only used to communicate from the compile step through the thin link (to perform whole program DCE). Right now we mark dead symbols in the index with internal linkage and rely on the back end to update the linkage (in the code you were looking at) and then GlobalDCE to remove them. We can handle the dropping of non-prevailing and globally dead symbols the same way perhaps - mark as not live in the summary and have a mechanism to just drop them without going through internalization etc.

[grimar]

In D42107#979118, @tejohnson wrote:

To drop non-prevailing symbols completely in the backends, as discussed in D41988, we will need to either add a bit to the summary flags, or possibly we can utilize the isLive flag (which currently is only used to communicate from the compile step through the thin link (to perform whole program DCE). Right now we mark dead symbols in the index with internal linkage and rely on the back end to update the linkage (in the code you were looking at) and then GlobalDCE to remove them. We can handle the dropping of non-prevailing and globally dead symbols the same way perhaps - mark as not live in the summary and have a mechanism to just drop them without going through internalization etc.

I am trying to implement this (hope I am doing right thing).
This approach looks better atm, though patch is not yet finished, I have 3 testcases failing atm, working on them:

LLVM :: LTO/Resolution/X86/comdat-mixed-lto.ll
LLVM :: LTO/Resolution/X86/lowertypetests.ll
LLVM :: LTO/Resolution/X86/setting-dso-local.ll

Going to upload current WIP version I have in a few minutes and continue tomorrow.

[grimar]

• WIP version that tries to leave non-prevealing symbols as dead and then drop them in backend.

[grimar]

Not finished, so planning update after fixing tests.

[grimar]

• Finished implementation. Now all LLD\LTO and llvm\test\LTO tests pass.

Implementation marks non-prevailing symbols as "dead" in the summary.
And then drops them in backend.

[tejohnson]

include/llvm/Transforms/IPO/FunctionImport.h

113

s/isPrevaling/isPrevailing/

113

Clarify that non-prevailing means that the prevailing copy is not anywhere in IR. I.e as opposed to the non-prevailing copy which has a prevailing copy in another bitcode module. In that case we won't drop, which is fine for the purposes of this bug.

116

s/isPrevaling/isPrevailing/

lib/LTO/ThinLTOCodeGenerator.cpp

626

I guess this is because we don't have linker resolution info. Not sure what ld64 does if it has the same situation. Maybe add a comment that this interface can't do any better in the case where the prevailing symbol is in a native object because it doesn't provide linker info?

652

suggest keeping the original name, which should be fine since it will just get overloaded. it matches the comment and the behavior better.

lib/Transforms/IPO/FunctionImport.cpp

501

s/isPrevaling/isPrevailing/

501

Add comment about what bool represents.

549

s/isPrevaling/isPrevailing/

549

Unclear to me what is going on here and why IsLiveRoot needs to be tracked and passed down (its more like "is this reached via a live root", so maybe ReachedByLiveRoot?). What does it mean for something to be a live root but not prevailing, which seems to be the case requiring these changes?

579

Interesting - is this a bug that was there before? It seems like an oversight not to have done this before. Or is it necessitated by your changes? If a separate bug, would be better to commit this separately.

580

Don't even need to check if Summary is an alias. Just set Base live unconditionally - either it is the aliasee or equal to Summary.

645

I think this is a hole. I.e. if the non-prevailing symbol is an alias, we can still do the incorrect internalization/inlining, right? Ok to fix in a follow-on patch though.

[grimar]

• Addressed review comments.

lib/LTO/ThinLTOCodeGenerator.cpp

626

Yes, we do not have resolution info. It is consistent with:
https://github.com/llvm-mirror/llvm/blob/master/lib/LTO/ThinLTOCodeGenerator.cpp#L500
code, which also do assumptions about resolution.

Updated the comment.

652

It needs either defining new static helper in llvm namespace too (where main computeDeadSymbols lives),
so it would overload it, or using ::computeDeadSymbols syntax for calls.
I did latter in this diff, though I am not sure it looks nice/consistent with usual LLVM code.

May be we could rename the helper to something like stripDeadSymbols or doSummaryBasedGC
or computeDeadSymbolsInSummary instead ?

lib/Transforms/IPO/FunctionImport.cpp

501

Updated comment for computeDeadSymbols with description of isPrevailing return value.

549

Yes, ReachedByLiveRoot describes the intention better. I did it for comdat-mixed-lto.ll case:
https://github.com/llvm-mirror/llvm/blob/master/test/LTO/Resolution/X86/comdat-mixed-lto.ll

Otherwise it would drop __cxx_global_var_init which is @llvm.global_ctors.
Linker does not know about these symbols and I had to preserve them somehow.
It seems simple solution which should work for now, what do you think ?

579

Bug was before, currently Aliasee does not get Live flag, while Alias does.
But does not seem there is some logic broken because of that.

For example following code used to compute imports:
https://github.com/llvm-mirror/llvm/blob/master/lib/Transforms/IPO/FunctionImport.cpp#L354
And I can observe for example how isGlobalValueLive skips GV which should be live,
but anyways it proccessed because it's alias is in the list too.
At the same time isGlobalValueLive checks Live flag of alias GVS, find it was set and then use getBaseObject to
continue work with aliasee right below.
I tried to create some test case to show where current logic is broken, but had no success.

I was need this change because introduced dropDeadSymbols which iterates over DefinedGlobals and can drop aliasee
which was not marked as live. It happens in lowertypetests.ll testcase.

645

I'll investigate this case separatelly.

[tejohnson]

LGTM. Just a few minor suggestions below.

include/llvm/Transforms/IPO/FunctionImport.h

112–120

s/anywere/anywhere/

114

s/has no any/has no/

lib/LTO/ThinLTOCodeGenerator.cpp

652

I see. Maybe computeDeadSymbolsInIndex then.

lib/Transforms/IPO/FunctionImport.cpp

501

I meant on the declaration of Worklist (the bool in the pair). It would be good to have a comment there indicating what the bool represents (i.e. whether it was reached by a value marked as a live root in the summary).

549

Ok, just add a comment that values already marked as live roots in the summary are typically llvm internal global values that the linker doesn't know about, therefore we can't look at whether the linker decided it was prevailing.

579

Ok, I think I can see why that wouldn't manifest as an issue before.

[grimar]

Thanks for your comments, Teresa !
I am sorry, unfortunately I was not aware that ThinLTO has testcases in llvm/test/ThinLTO,
and not only in llvm/test/LTO. After running check-llvm I see few more testcases
failtures and going to investigate them now.

[grimar]

• Addressed comments.
• Updated patch to fix previously broken tests.

Now both check-llvm, and check-llvm-tools-gold pass.

Main change to fix testcases was following.
I had to check isDSOLocal in computeDeadSymbols and keep DSOLocal
symbols to be live. An example where it needed:
\test\ThinLTO\X86\deadstrip.ll
(https://github.com/llvm-mirror/llvm/blob/master/test/ThinLTO/X86/deadstrip.ll#L116)
it has bar_internal which is reachable but not prevailing. Linker does not see them.

Comments on other testcases changes:

1. \test\ThinLTO\X86\deadstrip.ll: define was changed to declare because dead_func is dead, was dropped and converted to declaration.
2. \test\ThinLTO\X86\internalize.ll: bar and linkonce_func were unreachable and were dropped. Made them be reachable.
3. test\tools\gold\X86\global_with_section.ll: changes caused by converting dead dropped things to declarations.

[grimar]

• Changed implementation as suggested (introduced enum for prevailing status).

[grimar]

• Fixed broken comment.

[tejohnson]

LGTM with minor comment nit and missing change noted below.
Thanks - this looks cleaner using the enum!

include/llvm/Transforms/IPO/FunctionImport.h

111–112

Suggest changing "that are not anywhere in IR are normally dead" to something like "are symbols without a prevailing copy anywhere in IR and are normally dead". I.e. a non-prevailing symbol here can have a def in IR, it is just not prevailing.

lib/Transforms/IPO/FunctionImport.cpp

501

I think you lost the corresponding change to the header declaration in this version of the patch.

[grimar]

Thanks, Teresa !

Addressed last comments, rebased after rL323444,
and going to commit this in my tomorrow
(want to watch for bots to ensure all of them are happy).

include/llvm/Transforms/IPO/FunctionImport.h

111–112

Done.

lib/Transforms/IPO/FunctionImport.cpp

501

I think it is still there, right below text change you suggested :)

/// Compute all the symbols that are "dead": i.e these that can't be reached
/// in the graph from any of the given symbols listed in
/// \p GUIDPreservedSymbols. Non-prevailing symbols are symbols without a
/// prevailing copy anywhere in IR and are normally dead, \p isPrevailing
/// predicate returns status of symbol.

I removed comment done on the declaration of Worklist though, because after introducing enum
that part of code was reverted to original and there is no more pair with bool.

[tejohnson]

(Note that the change to the declaration of computeDeadSymbols in ModuleSummaryIndex.h is still missing from the uploaded version of the patch)

[grimar]

In D42107#988184, @tejohnson wrote:

(Note that the change to the declaration of computeDeadSymbols in ModuleSummaryIndex.h is still missing from the uploaded version of the patch)

Ah, now I see what you mean. It was eliminated earlier in rL323415.

[grimar]

• Fixed issue with symbols from "module asm" blocks.

[tejohnson]

No worries - I have done the same thing myself (broken lld bots with LTO changes since I don't always run them before commit).

lib/LTO/LTO.cpp

430

This assumes that the non-prevailing asm symbol with the name is seen here before the prevailing symbol without a name (which does always seem to currently be the case). Otherwise, the non-prevailing symbol would come along and fill in the name since it will be empty. Suggest moving this block up above the previous one that sets the Prevailing flag, then add an assert that if !Sym.getIRName.empty() that Res.Prevailing is not already true. I.e. that we don't overwrite the IRName when we already set it from the Prevailing copy.

[grimar]

lib/LTO/LTO.cpp

430

Yes, currently in a single module asm symbols looks always placed before IR ones seems.
But unfortunately asserting would also be not enough for case when we have multiple modules.

If we have 2 modules, where

• Module A has both asm and IR symbol foo:
  1. Prevailing, IRName="" (asm)
  2. Non-prevailing, IRName="foo" (IR)
• Module B with non-prevailing, IRName="foo".

it would not work, because handing of resolution from module B would trigger assertion failture.
I extended LLD testcase to catch this case too in rL323584.

Seems what we can do is never update IRName if symbol is already known to be prevailing (so always prefer IR name of prevailing symbol).
Will update patch with such change.

[grimar]

• Updated in according to latest comments.

[tejohnson]

LGTM with 2 minor suggestions.

lib/LTO/LTO.cpp

431

add something like "Otherwise, if we haven't seen a prevailing symbol, set the name so that we can later use it to check if there is any prevailing copy in IR."

432

merge this into the else if condition

include/llvm/IR/ModuleSummaryIndex.h

public:
 
   /// If this is an alias summary, returns the summary of the aliased object (a
   /// global variable or function), otherwise returns itself.
   GlobalValueSummary *getBaseObject();
   const GlobalValueSummary *getBaseObject() const;
 
   friend class ModuleSummaryIndex;
   friend void computeDeadSymbols(class ModuleSummaryIndex &,
-                                 const DenseSet<GlobalValue::GUID> &);
+                                 const DenseSet<GlobalValue::GUID> &,
+                                 function_ref<bool(GlobalValue::GUID)>);
 };
 
 /// \brief Alias summary information.
 class AliasSummary : public GlobalValueSummary {
   GlobalValueSummary *AliaseeSummary;
   // AliaseeGUID is only set and accessed when we are building a combined index
   // via the BitcodeReader.
   GlobalValue::GUID AliaseeGUID;

include/llvm/Transforms/IPO/FunctionImport.h

 ///
 /// \p ImportList will be populated with a map that can be passed to
 /// FunctionImporter::importFunctions() above (see description there).
 void ComputeCrossModuleImportForModuleFromIndex(
     StringRef ModulePath, const ModuleSummaryIndex &Index,
     FunctionImporter::ImportMapTy &ImportList);
 
 /// Compute all the symbols that are "dead": i.e these that can't be reached
 /// in the graph from any of the given symbols listed in
-/// \p GUIDPreservedSymbols.
-void computeDeadSymbols(
-    ModuleSummaryIndex &Index,
-    const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols);
+/// \p GUIDPreservedSymbols. Non-prevailing symbols that are not anywhere in IR
+/// are normally "dead", \p isPrevailing predicate returns true if symbol
+/// with GUID provided has no prevailing copies.
+void computeDeadSymbols(ModuleSummaryIndex &Index,
+                        const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols,
+                        function_ref<bool(GlobalValue::GUID)> isPrevailing);
+
+/// Converts value \p GV to declaration.
+void convertToDeclaration(GlobalValue &GV);
 
 /// Compute the set of summaries needed for a ThinLTO backend compilation of
 /// \p ModulePath.
 //
 /// This includes summaries from that module (in case any global summary based
 /// optimizations were recorded) and from any definitions in other modules that
 /// should be imported.
 //

lib/LTO/LTO.cpp

thinLTOResolveWeakForLinkerGUID(I.second.SummaryList, I.first,
                                     GlobalInvolvedWithAlias, isPrevailing,
                                     recordNewLinkage);
 }
 
 static void thinLTOInternalizeAndPromoteGUID(
     GlobalValueSummaryList &GVSummaryList, GlobalValue::GUID GUID,
     function_ref<bool(StringRef, GlobalValue::GUID)> isExported) {
   for (auto &S : GVSummaryList) {
     if (isExported(S->modulePath(), GUID)) {
       if (GlobalValue::isLocalLinkage(S->linkage()))
         S->setLinkage(GlobalValue::ExternalLinkage);
     } else if (!GlobalValue::isLocalLinkage(S->linkage()))
       S->setLinkage(GlobalValue::InternalLinkage);
   }
 }
 
 // Update the linkages in the given \p Index to mark exported values
if (Res.Prevailing) {
       assert(GlobalRes.IRName.empty() &&
              "Multiple prevailing defs are not allowed");
       GlobalRes.IRName = Sym.getIRName();
     }
 
     // Set the partition to external if we know it is re-defined by the linker
     // with -defsym or -wrap options, used elsewhere, e.g. it is visible to a
     // regular object, is referenced from llvm.compiler_used, or was already
     // recorded as being referenced from a different partition.
     if (Res.LinkerRedefined || Res.VisibleToRegularObj || Sym.isUsed() ||
         (GlobalRes.Partition != GlobalResolution::Unknown &&
          GlobalRes.Partition != Partition)) {
       GlobalRes.Partition = GlobalResolution::External;
     } else
       // First recorded reference, save the current partition.
       GlobalRes.Partition = Partition;
 
     // Flag as visible outside of summary if visible from a regular object or
     // from a module that does not have a summary.

 unsigned LTO::getMaxTasks() const {
   CalledGetMaxTasks = true;
   return RegularLTO.ParallelCodeGenParallelismLevel + ThinLTO.ModuleMap.size();
 }
 
 Error LTO::run(AddStreamFn AddStream, NativeObjectCache Cache) {
   // Compute "dead" symbols, we don't want to import/export these!
   DenseSet<GlobalValue::GUID> GUIDPreservedSymbols;
+  DenseSet<GlobalValue::GUID> GUIDPrevailingSymbols;
   for (auto &Res : GlobalResolutions) {
-    if (Res.second.VisibleOutsideSummary &&
-        // IRName will be defined if we have seen the prevailing copy of
-        // this value. If not, no need to preserve any ThinLTO copies.
-        !Res.second.IRName.empty())
-      GUIDPreservedSymbols.insert(GlobalValue::getGUID(
-          GlobalValue::dropLLVMManglingEscape(Res.second.IRName)));
+    if (Res.second.IRName.empty())
+      continue;
+
+    GlobalValue::GUID G = GlobalValue::getGUID(
+        GlobalValue::dropLLVMManglingEscape(Res.second.IRName));
+    GUIDPrevailingSymbols.insert(G);
+    if (Res.second.VisibleOutsideSummary)
+      GUIDPreservedSymbols.insert(G);
   }
 
-  computeDeadSymbols(ThinLTO.CombinedIndex, GUIDPreservedSymbols);
+  auto isPrevailing = [&](GlobalValue::GUID G) {
+    return GUIDPrevailingSymbols.count(G);
+  };
+  computeDeadSymbols(ThinLTO.CombinedIndex, GUIDPreservedSymbols, isPrevailing);
 
   if (auto E = runRegularLTO(AddStream))
     return E;
   return runThinLTO(AddStream, Cache);
 }
 
 Error LTO::runRegularLTO(AddStreamFn AddStream) {
   for (auto &M : RegularLTO.ModsWithSummaries)

lib/LTO/LTOBackend.cpp

Error lto::backend(Config &C, AddStreamFn AddStream,
   } else {
     splitCodeGen(C, TM.get(), AddStream, ParallelCodeGenParallelismLevel,
                  std::move(Mod));
   }
   finalizeOptimizationRemarks(std::move(DiagnosticOutputFile));
   return Error::success();
 }
 
+static void dropDeadSymbols(Module &Mod, const GVSummaryMapTy &DefinedGlobals,
+                            const ModuleSummaryIndex &Index) {
+  for (auto &GV : Mod) {
+    auto It = DefinedGlobals.find(GV.getGUID());
+    if (It == DefinedGlobals.end())
+      continue;
+    if (!Index.isGlobalValueLive(It->second))
+      convertToDeclaration(GV);
+  }
+}
+
 Error lto::thinBackend(Config &Conf, unsigned Task, AddStreamFn AddStream,
                        Module &Mod, const ModuleSummaryIndex &CombinedIndex,
                        const FunctionImporter::ImportMapTy &ImportList,
                        const GVSummaryMapTy &DefinedGlobals,
                        MapVector<StringRef, BitcodeModule> &ModuleMap) {
   Expected<const Target *> TOrErr = initAndLookupTarget(Conf, Mod);
   if (!TOrErr)
     return TOrErr.takeError();
 
   std::unique_ptr<TargetMachine> TM = createTargetMachine(Conf, *TOrErr, Mod);
 
   if (Conf.CodeGenOnly) {
     codegen(Conf, TM.get(), AddStream, Task, Mod);
     return Error::success();
   }
 
   if (Conf.PreOptModuleHook && !Conf.PreOptModuleHook(Task, Mod))
     return Error::success();
 
   renameModuleForThinLTO(Mod, CombinedIndex);
 
+  dropDeadSymbols(Mod, DefinedGlobals, CombinedIndex);
+
   thinLTOResolveWeakForLinkerModule(Mod, DefinedGlobals);
 
   if (Conf.PostPromoteModuleHook && !Conf.PostPromoteModuleHook(Task, Mod))
     return Error::success();
 
   if (!DefinedGlobals.empty())
     thinLTOInternalizeModule(Mod, DefinedGlobals);
 

lib/LTO/ThinLTOCodeGenerator.cpp

auto isExported = [&](StringRef ModuleIdentifier, GlobalValue::GUID GUID) {
     return (ExportList != ExportLists.end() &&
             ExportList->second.count(GUID)) ||
            GUIDPreservedSymbols.count(GUID);
   };
 
   thinLTOInternalizeAndPromoteInIndex(Index, isExported);
 }
 
+static void computeDeadSymbolsInIndex(
+    ModuleSummaryIndex &Index,
+    const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols) {
+  // If there is at least one symbol, it is assumed it is prevailing. We can't
+  // do any better now in the case where the prevailing symbol is in a native
+  // object. It can be refined with linker information in the future.
+  auto isPrevailing = [&](GlobalValue::GUID G) { return true; };
+  computeDeadSymbols(Index, GUIDPreservedSymbols, isPrevailing);
+}
+
 /**
  * Perform promotion and renaming of exported internal functions.
  * Index is updated to reflect linkage changes from weak resolution.
  */
 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<GVSummaryMapTy> ModuleToDefinedGVSummaries;
   Index.collectDefinedGVSummariesPerModule(ModuleToDefinedGVSummaries);
 
   // Convert the preserved symbols set from string to GUID
   auto GUIDPreservedSymbols = computeGUIDPreservedSymbols(
       PreservedSymbols, Triple(TheModule.getTargetTriple()));
 
   // Compute "dead" symbols, we don't want to import/export these!
-  computeDeadSymbols(Index, GUIDPreservedSymbols);
+  computeDeadSymbolsInIndex(Index, GUIDPreservedSymbols);
 
   // Generate import/export list
   StringMap<FunctionImporter::ImportMapTy> ImportLists(ModuleCount);
   StringMap<FunctionImporter::ExportSetTy> ExportLists(ModuleCount);
   ComputeCrossModuleImport(Index, ModuleToDefinedGVSummaries, ImportLists,
                            ExportLists);
 
   // Resolve LinkOnce/Weak symbols.
void ThinLTOCodeGenerator::crossModuleImport(Module &TheModule,
   StringMap<GVSummaryMapTy> ModuleToDefinedGVSummaries(ModuleCount);
   Index.collectDefinedGVSummariesPerModule(ModuleToDefinedGVSummaries);
 
   // Convert the preserved symbols set from string to GUID
   auto GUIDPreservedSymbols = computeGUIDPreservedSymbols(
       PreservedSymbols, Triple(TheModule.getTargetTriple()));
 
   // Compute "dead" symbols, we don't want to import/export these!
-  computeDeadSymbols(Index, GUIDPreservedSymbols);
+  computeDeadSymbolsInIndex(Index, GUIDPreservedSymbols);
 
   // Generate import/export list
   StringMap<FunctionImporter::ImportMapTy> ImportLists(ModuleCount);
   StringMap<FunctionImporter::ExportSetTy> ExportLists(ModuleCount);
   ComputeCrossModuleImport(Index, ModuleToDefinedGVSummaries, ImportLists,
                            ExportLists);
   auto &ImportList = ImportLists[TheModule.getModuleIdentifier()];
 
void ThinLTOCodeGenerator::internalize(Module &TheModule,
   auto GUIDPreservedSymbols =
       computeGUIDPreservedSymbols(PreservedSymbols, TMBuilder.TheTriple);
 
   // Collect for each module the list of function it defines (GUID -> Summary).
   StringMap<GVSummaryMapTy> ModuleToDefinedGVSummaries(ModuleCount);
   Index.collectDefinedGVSummariesPerModule(ModuleToDefinedGVSummaries);
 
   // Compute "dead" symbols, we don't want to import/export these!
-  computeDeadSymbols(Index, GUIDPreservedSymbols);
+  computeDeadSymbolsInIndex(Index, GUIDPreservedSymbols);
 
   // Generate import/export list
   StringMap<FunctionImporter::ImportMapTy> ImportLists(ModuleCount);
   StringMap<FunctionImporter::ExportSetTy> ExportLists(ModuleCount);
   ComputeCrossModuleImport(Index, ModuleToDefinedGVSummaries, ImportLists,
                            ExportLists);
   auto &ExportList = ExportLists[ModuleIdentifier];
 
void ThinLTOCodeGenerator::run() {
   Index->collectDefinedGVSummariesPerModule(ModuleToDefinedGVSummaries);
 
   // Convert the preserved symbols set from string to GUID, this is needed for
   // computing the caching hash and the internalization.
   auto GUIDPreservedSymbols =
       computeGUIDPreservedSymbols(PreservedSymbols, TMBuilder.TheTriple);
 
   // Compute "dead" symbols, we don't want to import/export these!
-  computeDeadSymbols(*Index, GUIDPreservedSymbols);
+  computeDeadSymbolsInIndex(*Index, GUIDPreservedSymbols);
 
   // Collect the import/export lists for all modules from the call-graph in the
   // combined index.
   StringMap<FunctionImporter::ImportMapTy> ImportLists(ModuleCount);
   StringMap<FunctionImporter::ExportSetTy> ExportLists(ModuleCount);
   ComputeCrossModuleImport(*Index, ModuleToDefinedGVSummaries, ImportLists,
                            ExportLists);
 

lib/Transforms/IPO/FunctionImport.cpp

auto It = llvm::find_if(
         // in the index.
         // 2) There is a static variable with the  OriginalGUID identical
         // to the GUID of the library function in 1);
         // When this happens, the logic for SamplePGO kicks in and
         // the static variable in 2) will be found, which needs to be
         // filtered out.
         if (GVSummary->getSummaryKind() == GlobalValueSummary::GlobalVarKind)
           return false;
-        if (GlobalValue::isInterposableLinkage(GVSummary->linkage()))
-          // There is no point in importing these, we can't inline them
+
+        if (GlobalValue::isInterposableLinkage(GVSummary->linkage()))
+          return false;
+        if (!Index.isGlobalValueLive(GVSummary))
           return false;
 
         auto *Summary = cast<FunctionSummary>(GVSummary->getBaseObject());
 
         // If this is a local function, make sure we import the copy
         // in the caller's module. The only time a local function 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
void llvm::ComputeCrossModuleImportForModuleFromIndex(
   }
 #ifndef NDEBUG
   dumpImportListForModule(ModulePath, ImportList);
 #endif
 }
 
 void llvm::computeDeadSymbols(
     ModuleSummaryIndex &Index,
-    const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols) {
+    const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols,
+    function_ref<bool(GlobalValue::GUID)> isPrevailing) {
   assert(!Index.withGlobalValueDeadStripping());
   if (!ComputeDead)
     return;
   if (GUIDPreservedSymbols.empty())
     // Don't do anything when nothing is live, this is friendly with tests.
     return;
   unsigned LiveSymbols = 0;
-  SmallVector<ValueInfo, 128> Worklist;
+
+  // Worklist contains pair of <Value, ReachedByLiveRoot> and used to visit
+  // all reachable values to mark them live. ReachedByLiveRoot flag indicates
+  // that value can be reached by live root.
+  SmallVector<std::pair<ValueInfo, bool>, 128> Worklist;
   Worklist.reserve(GUIDPreservedSymbols.size() * 2);
-  for (auto GUID : GUIDPreservedSymbols) {
-    ValueInfo VI = Index.getValueInfo(GUID);
-    if (!VI)
-      continue;
-    for (auto &S : VI.getSummaryList())
-      S->setLive(true);
-  }
 
   // Add values flagged in the index as live roots to the worklist.
   for (const auto &Entry : Index)
     for (auto &S : Entry.second.SummaryList)
       if (S->isLive()) {
         DEBUG(dbgs() << "Live root: " << Entry.first << "\n");
-        Worklist.push_back(ValueInfo(/*IsAnalysis=*/false, &Entry));
+        Worklist.push_back({ValueInfo(/*IsAnalysis=*/false, &Entry), true});
         ++LiveSymbols;
         break;
       }
 
+  for (auto GUID : GUIDPreservedSymbols) {
+    ValueInfo VI = Index.getValueInfo(GUID);
+    if (!VI)
+      continue;
+    for (const std::unique_ptr<GlobalValueSummary> &S : VI.getSummaryList())
+      S->setLive(true);
+    ++LiveSymbols;
+    Worklist.push_back({VI, false});
+  }
+
   // Make value live and add it to the worklist if it was not live before.
-  // FIXME: we should only make the prevailing copy live here
-  auto visit = [&](ValueInfo VI) {
+  auto Visit = [&](ValueInfo VI, bool ReachedByLiveRoot) {
     // FIXME: If we knew which edges were created for indirect call profiles,
     // we could skip them here. Any that are live should be reached via
     // other edges, e.g. reference edges. Otherwise, using a profile collected
     // on a slightly different binary might provoke preserving, importing
     // and ultimately promoting calls to functions not linked into this
     // binary, which increases the binary size unnecessarily. Note that
     // if this code changes, the importer needs to change so that edges
     // to functions marked dead are skipped.
     VI = updateValueInfoForIndirectCalls(Index, VI);
     if (!VI)
       return;
     for (auto &S : VI.getSummaryList())
       if (S->isLive())
         return;
+
+    // Values already marked as live roots in the summary are typically llvm
+    // internal global values that linker doesn't know about, therefore we can't
+    // look at whether the linker decided it was prevailing.
+    GlobalValue::GUID GUID = VI.getGUID();
+    if (!ReachedByLiveRoot && !isPrevailing(GUID)) {
+      GlobalValueSummary *GVS =
+          Index.getGlobalValueSummary(GUID, false /* PerModuleIndex */);
+      // This is last resort. If symbol known to be resolved to a definition
+      // from within the same linkage unit, mark it live.
+      if (!GVS->isDSOLocal())
+        return;
+    }
+
     for (auto &S : VI.getSummaryList())
       S->setLive(true);
     ++LiveSymbols;
-    Worklist.push_back(VI);
+    Worklist.push_back({VI, ReachedByLiveRoot});
   };
 
   while (!Worklist.empty()) {
-    auto VI = Worklist.pop_back_val();
+    ValueInfo VI;
+    bool ReachedByLiveRoot;
+    std::tie(VI, ReachedByLiveRoot) = Worklist.pop_back_val();
+
     for (auto &Summary : VI.getSummaryList()) {
       GlobalValueSummary *Base = Summary->getBaseObject();
+      // Set base value live in case it is an alias.
+      Base->setLive(true);
+
       for (auto Ref : Base->refs())
-        visit(Ref);
+        Visit(Ref, ReachedByLiveRoot);
       if (auto *FS = dyn_cast<FunctionSummary>(Base))
         for (auto Call : FS->calls())
-          visit(Call.first);
+          Visit(Call.first, ReachedByLiveRoot);
     }
   }
   Index.setWithGlobalValueDeadStripping();
 
   unsigned DeadSymbols = Index.size() - LiveSymbols;
   DEBUG(dbgs() << LiveSymbols << " symbols Live, and " << DeadSymbols
                << " symbols Dead \n");
   NumDeadSymbols += DeadSymbols;
llvm::EmitImportsFiles(StringRef ModulePath, StringRef OutputFilename,
   raw_fd_ostream ImportsOS(OutputFilename, EC, sys::fs::OpenFlags::F_None);
   if (EC)
     return EC;
   for (auto &ILI : ModuleImports)
     ImportsOS << ILI.first() << "\n";
   return std::error_code();
 }
 
-/// Fixup WeakForLinker linkages in \p TheModule based on summary analysis.
-void llvm::thinLTOResolveWeakForLinkerModule(
-    Module &TheModule, const GVSummaryMapTy &DefinedGlobals) {
-  auto ConvertToDeclaration = [](GlobalValue &GV) {
-    DEBUG(dbgs() << "Converting to a declaration: `" << GV.getName() << "\n");
-    if (Function *F = dyn_cast<Function>(&GV)) {
-      F->deleteBody();
-      F->clearMetadata();
-    } else if (GlobalVariable *V = dyn_cast<GlobalVariable>(&GV)) {
-      V->setInitializer(nullptr);
-      V->setLinkage(GlobalValue::ExternalLinkage);
-      V->clearMetadata();
-    } else
-      // For now we don't resolve or drop aliases. Once we do we'll
-      // need to add support here for creating either a function or
-      // variable declaration, and return the new GlobalValue* for
-      // the caller to use.
-      llvm_unreachable("Expected function or variable");
-  };
+void llvm::convertToDeclaration(GlobalValue &GV) {
+}
 
+/// Fixup WeakForLinker linkages in \p TheModule based on summary analysis.
+void llvm::thinLTOResolveWeakForLinkerModule(
+    Module &TheModule, const GVSummaryMapTy &DefinedGlobals) {
   auto updateLinkage = [&](GlobalValue &GV) {
     // See if the global summary analysis computed a new resolved linkage.
     const auto &GS = DefinedGlobals.find(GV.getGUID());
     if (GS == DefinedGlobals.end())
       return;
     auto NewLinkage = GS->second->linkage();
     if (NewLinkage == GV.getLinkage())
       return;
if (!GlobalValue::isWeakForLinker(GV.getLinkage()))
       return;
     // Check for a non-prevailing def that has interposable linkage
     // (e.g. non-odr weak or linkonce). In that case we can't simply
     // convert to available_externally, since it would lose the
     // interposable property and possibly get inlined. Simply drop
     // the definition in that case.
     if (GlobalValue::isAvailableExternallyLinkage(NewLinkage) &&
         GlobalValue::isInterposableLinkage(GV.getLinkage()))
-      ConvertToDeclaration(GV);
+      convertToDeclaration(GV);
     else {
       DEBUG(dbgs() << "ODR fixing up linkage for `" << GV.getName() << "` from "
                    << GV.getLinkage() << " to " << NewLinkage << "\n");
       GV.setLinkage(NewLinkage);
     }
     // Remove declarations from comdats, including available_externally
     // as this is a declaration for the linker, and will be dropped eventually.
     // It is illegal for comdats to contain declarations.

test/LTO/Resolution/X86/Inputs/not-prevailing.ll

+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @bar() {
+  ret void
+}

test/LTO/Resolution/X86/not-prevailing.ll

+; RUN: opt -module-summary %s -o %t1.o
+; RUN: opt -module-summary -o %t2.o %S/Inputs/not-prevailing.ll
+; RUN: llvm-lto2 run -o %t3.o %t1.o %t2.o -r %t1.o,foo,x -r %t1.o,zed,px -r %t1.o,bar,x \
+; RUN:   -r %t2.o,bar,x -save-temps
+
+; Check that 'foo' and 'bar' were not inlined.
+; CHECK:      zed:
+; CHECK-NEXT:  {{.*}}  pushq   %rbx
+; CHECK-NEXT:  {{.*}}  callq   0 <zed+0x6>
+; CHECK-NEXT:  {{.*}}  movl    %eax, %ebx
+; CHECK-NEXT:  {{.*}}  callq   0 <zed+0xd>
+; CHECK-NEXT:  {{.*}}  movl    %ebx, %eax
+; CHECK-NEXT:  {{.*}}  popq    %rbx
+; CHECK-NEXT:  {{.*}}  retq
+
+; RUN: llvm-objdump -d %t3.o.1 | FileCheck %s
+; RUN: llvm-readelf --symbols %t3.o.1 | FileCheck %s --check-prefix=SYMBOLS
+
+; Check that 'foo' and 'bar' produced as undefined.
+; SYMBOLS: NOTYPE  GLOBAL DEFAULT  UND bar
+; SYMBOLS: NOTYPE  GLOBAL DEFAULT  UND foo
+; SYMBOLS: FUNC    GLOBAL DEFAULT    2 zed
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define weak i32 @foo() {
+  ret i32 65
+}
+
+declare void @bar()
+
+define i32 @zed() {
+  %1 = tail call i32 @foo()
+  call void @bar()
+  ret i32 %1
+}

test/ThinLTO/X86/deadstrip.ll

 ; CHECK: define internal void @bar_internal()
 ; CHECK: define internal void @dead_func() {
 ; CHECK-NOT: available_externally {{.*}} @baz()
 ; LTO2-NOT: available_externally {{.*}} @baz()
 ; LTO2: @llvm.global_ctors =
 ; LTO2: define internal void @_GLOBAL__I_a()
 ; LTO2: define internal void @bar() {
 ; LTO2: define internal void @bar_internal()
-; LTO2: define internal void @dead_func() {
+; LTO2: declare dso_local void @dead_func()
 ; LTO2-NOT: available_externally {{.*}} @baz()
 
 ; Make sure we didn't internalize @boo, which is reachable via
 ; llvm.global_ctors
 ; CHECK2: define void @boo()
 ; LTO2-CHECK2: define dso_local void @boo()
 ; We should have eventually removed @baz since it was internalized and unused
 ; CHECK2-NM-NOT: _baz

test/ThinLTO/X86/internalize.ll

 ; INTERNALIZE2: define dso_local void @foo
 ; INTERNALIZE2: define internal void @bar
 ; INTERNALIZE2: define internal void @linkonce_func()
 
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx10.11.0"
 
 define void @foo() {
+    call void @bar()
     ret void
 }
 define void @bar() {
     call void @linkonce_func()
   ret void
 }
 define linkonce void @linkonce_func() {
     ret void
 }

test/tools/gold/X86/global_with_section.ll

 ; RUN: opt -module-summary %s -o %t.o
 ; RUN: llvm-lto2 dump-symtab %t.o | FileCheck %s --check-prefix=SYMTAB
 ; RUN: opt -module-summary %p/Inputs/global_with_section.ll -o %t2.o
 ; RUN: %gold -m elf_x86_64 -plugin %llvmshlibdir/LLVMgold%shlibext \
 ; RUN:     --plugin-opt=thinlto \
 ; RUN:     --plugin-opt=save-temps \
 ; RUN:     -o %t3.o %t.o %t2.o
 ; Check results of internalization
-; RUN: llvm-dis %t.o.2.internalize.bc -o - | FileCheck %s
+; RUN: llvm-dis %t.o.2.internalize.bc -o - | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-THINLTO
 ; RUN: llvm-dis %t2.o.2.internalize.bc -o - | FileCheck %s --check-prefix=CHECK2-THINLTO
 
 ; SYMTAB: deadfunc_with_section
 ; SYMTAB-NEXT: section some_other_section
 ; SYMTAB-NEXT: deadfunc_with_nonC_section
 ; SYMTAB-NEXT: section .nonCsection
 ; SYMTAB-NEXT: deadfunc2_called_from_section
 ; SYMTAB-NEXT: deadfunc2_called_from_nonC_section

 ; CHECK-DAG: define dso_local void @deadfunc_with_section() section "some_other_section"
 define void @deadfunc_with_section() section "some_other_section" {
   call void @deadfunc2_called_from_section()
   ret void
 }
 
 ; Confirm via a function with a non-C identifier section that we are getting
 ; the expected internalization.
-; CHECK-DAG: define internal void @deadfunc_with_nonC_section() section ".nonCsection"
+; CHECK2-REGULARLTO-DAG: define internal void @deadfunc_with_nonC_section() section ".nonCsection"
+; Check dead function converted to declaration.
+; CHECK-THINLTO-DAG: declare dso_local void @deadfunc_with_nonC_section() section ".nonCsection"
 define void @deadfunc_with_nonC_section() section ".nonCsection" {
   call void @deadfunc2_called_from_nonC_section()
   ret void
 }
 
 ; In RegularLTO mode, where we have combined all the IR,
 ; @deadfunc2_called_from_section can be internalized.
 ; CHECK2-REGULARLTO: define internal void @deadfunc2_called_from_section
 ; In ThinLTO mode, we can't internalize it as it needs to be preserved
 ; (due to the access from @deadfunc_with_section which must be preserved), and
 ; can't be internalized since the reference is from a different module.
 ; CHECK2-THINLTO: define dso_local void @deadfunc2_called_from_section
 declare void @deadfunc2_called_from_section()
 
 ; Confirm when called from a function with a non-C identifier section that we
 ; are getting the expected internalization.
 ; CHECK2-REGULARLTO: define internal void @deadfunc2_called_from_nonC_section
-; CHECK2-THINLTO: define internal void @deadfunc2_called_from_nonC_section
+; Check dead function converted to declaration.
+; CHECK2-THINLTO: declare dso_local void @deadfunc2_called_from_nonC_section
 declare void @deadfunc2_called_from_nonC_section()