[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

337 ↗

(On Diff #129955)

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 ↗

(On Diff #130612)

s/isPrevaling/isPrevailing/

113 ↗

(On Diff #130612)

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 ↗

(On Diff #130612)

s/isPrevaling/isPrevailing/

lib/LTO/ThinLTOCodeGenerator.cpp

626 ↗

(On Diff #130612)

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?

649 ↗

(On Diff #130612)

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 ↗

(On Diff #130612)

s/isPrevaling/isPrevailing/

501 ↗

(On Diff #130612)

Add comment about what bool represents.

546 ↗

(On Diff #130612)

s/isPrevaling/isPrevailing/

546 ↗

(On Diff #130612)

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?

564 ↗

(On Diff #130612)

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.

565 ↗

(On Diff #130612)

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.

631 ↗

(On Diff #130612)

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 ↗

(On Diff #130612)

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.

649 ↗

(On Diff #130612)

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 ↗

(On Diff #130612)

Updated comment for computeDeadSymbols with description of isPrevailing return value.

546 ↗

(On Diff #130612)

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 ?

564 ↗

(On Diff #130612)

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.

631 ↗

(On Diff #130612)

I'll investigate this case separatelly.

[tejohnson]

LGTM. Just a few minor suggestions below.

include/llvm/Transforms/IPO/FunctionImport.h

112 ↗

(On Diff #130915)

s/anywere/anywhere/

114 ↗

(On Diff #130915)

s/has no any/has no/

lib/LTO/ThinLTOCodeGenerator.cpp

649 ↗

(On Diff #130612)

I see. Maybe computeDeadSymbolsInIndex then.

lib/Transforms/IPO/FunctionImport.cpp

501 ↗

(On Diff #130612)

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

546 ↗

(On Diff #130612)

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.

564 ↗

(On Diff #130612)

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

117 ↗

(On Diff #131447)

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 ↗

(On Diff #131447)

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

117 ↗

(On Diff #131447)

Done.

lib/Transforms/IPO/FunctionImport.cpp

501 ↗

(On Diff #131447)

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 ↗

(On Diff #131584)

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 ↗

(On Diff #131584)

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

432 ↗

(On Diff #131680)

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

433 ↗

(On Diff #131680)

merge this into the else if condition

llvm/trunk/include/llvm/LTO/LTO.h

struct GlobalResolution {
 
     /// Keep track if the symbol is visible outside of a module with a summary
     /// (i.e. in either a regular object or a regular LTO module without a
     /// summary).
     bool VisibleOutsideSummary = false;
 
     bool UnnamedAddr = true;
 
-    /// True if IR contains the prevailing definition.
+    /// True if module contains the prevailing definition.
     bool Prevailing = false;
 
+    /// Returns true if module contains the prevailing definition and symbol is
+    /// an IR symbol. For example when module-level inline asm block is used,
+    /// symbol can be prevailing in module but have no IR name.
+    bool isPrevailingIRSymbol() const { return Prevailing && !IRName.empty(); }
+
     /// This field keeps track of the partition number of this global. The
     /// regular LTO object is partition 0, while each ThinLTO object has its own
     /// partition number from 1 onwards.
     ///
     /// Any global that is defined or used by more than one partition, or that
     /// is referenced externally, may not be internalized.
     ///
     /// Partitions generally have a one-to-one correspondence with tasks, except

llvm/trunk/include/llvm/Transforms/IPO/FunctionImport.h

 /// Used for distributed builds using a distributed index.
 ///
 /// \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);
 
+/// PrevailingType enum used as a return type of callback passed
+/// to computeDeadSymbols. Yes and No values used when status explicitly
+/// set by symbols resolution, otherwise status is Unknown.
+enum class PrevailingType { Yes, No, Unknown };
+
 /// 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.
+/// \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.
 void computeDeadSymbols(
     ModuleSummaryIndex &Index,
-    const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols);
+    const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols,
+    function_ref<PrevailingType(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.
 //

llvm/trunk/lib/LTO/LTO.cpp

for (const InputFile::Symbol &Sym : Syms) {
 
     auto &GlobalRes = GlobalResolutions[Sym.getName()];
     GlobalRes.UnnamedAddr &= Sym.isUnnamedAddr();
     if (Res.Prevailing) {
       assert(!GlobalRes.Prevailing &&
              "Multiple prevailing defs are not allowed");
       GlobalRes.Prevailing = true;
       GlobalRes.IRName = Sym.getIRName();
+    } else if (!GlobalRes.Prevailing && GlobalRes.IRName.empty()) {
+      // Sometimes it can be two copies of symbol in a module and prevailing
+      // symbol can have no IR name. That might happen if symbol is defined in
+      // module level inline asm block. In case we have multiple modules with
+      // the same symbol we want to use IR name of the prevailing symbol.
+      // 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.
+      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 &&

 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;
-  for (auto &Res : GlobalResolutions)
+  DenseMap<GlobalValue::GUID, PrevailingType> GUIDPrevailingResolutions;
+  for (auto &Res : GlobalResolutions) {
+    // Normally resolution have IR name of symbol. We can do nothing here
+    // otherwise. See comments in GlobalResolution struct for more details.
+    if (Res.second.IRName.empty())
+      continue;
+
+    GlobalValue::GUID GUID = GlobalValue::getGUID(
+        GlobalValue::dropLLVMManglingEscape(Res.second.IRName));
+
     if (Res.second.VisibleOutsideSummary && Res.second.Prevailing)
       GUIDPreservedSymbols.insert(GlobalValue::getGUID(
           GlobalValue::dropLLVMManglingEscape(Res.second.IRName)));
 
-  computeDeadSymbols(ThinLTO.CombinedIndex, GUIDPreservedSymbols);
+    GUIDPrevailingResolutions[GUID] =
+        Res.second.Prevailing ? PrevailingType::Yes : PrevailingType::No;
+  }
+
+  auto isPrevailing = [&](GlobalValue::GUID G) {
+    auto It = GUIDPrevailingResolutions.find(G);
+    if (It == GUIDPrevailingResolutions.end())
+      return PrevailingType::Unknown;
+    return It->second;
+  };
+  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)
Error LTO::runRegularLTO(AddStreamFn AddStream) {
   }
 
   if (Conf.PreOptModuleHook &&
       !Conf.PreOptModuleHook(0, *RegularLTO.CombinedModule))
     return Error::success();
 
   if (!Conf.CodeGenOnly) {
     for (const auto &R : GlobalResolutions) {
-      if (!R.second.Prevailing)
+      if (!R.second.isPrevailingIRSymbol())
         continue;
       if (R.second.Partition != 0 &&
           R.second.Partition != GlobalResolution::External)
         continue;
 
       GlobalValue *GV =
           RegularLTO.CombinedModule->getNamedValue(R.second.IRName);
       // Ignore symbols defined in other partitions.
Error LTO::runThinLTO(AddStreamFn AddStream, NativeObjectCache Cache) {
   // at -O0 because summary-based DCE is implemented using internalization, and
   // we must apply DCE consistently with the full LTO module in order to avoid
   // undefined references during the final link.
   std::set<GlobalValue::GUID> ExportedGUIDs;
   for (auto &Res : GlobalResolutions) {
     // If the symbol does not have external references or it is not prevailing,
     // then not need to mark it as exported from a ThinLTO partition.
     if (Res.second.Partition != GlobalResolution::External ||
-        !Res.second.Prevailing)
+        !Res.second.isPrevailingIRSymbol())
       continue;
     auto GUID = GlobalValue::getGUID(
         GlobalValue::dropLLVMManglingEscape(Res.second.IRName));
     // Mark exported unless index-based analysis determined it to be dead.
     if (ThinLTO.CombinedIndex.isGUIDLive(GUID))
       ExportedGUIDs.insert(GUID);
   }
 

llvm/trunk/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);
 

llvm/trunk/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) {
+  // We have no symbols resolution available. And 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 PrevailingType::Unknown;
+  };
+  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);
 

llvm/trunk/lib/Transforms/IPO/FunctionImport.cpp

 static const GlobalValueSummary *
 selectCallee(const ModuleSummaryIndex &Index,
              ArrayRef<std::unique_ptr<GlobalValueSummary>> CalleeSummaryList,
              unsigned Threshold, StringRef CallerModulePath) {
   auto It = llvm::find_if(
       CalleeSummaryList,
       [&](const std::unique_ptr<GlobalValueSummary> &SummaryPtr) {
         auto *GVSummary = SummaryPtr.get();
+        if (!Index.isGlobalValueLive(GVSummary))
+          return false;
+
         // For SamplePGO, in computeImportForFunction the OriginalId
         // may have been used to locate the callee summary list (See
         // comment there).
         // The mapping from OriginalId to GUID may return a GUID
         // that corresponds to a static variable. Filter it out here.
         // This can happen when
         // 1) There is a call to a library function which is not defined
         // in the index.
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<PrevailingType(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;
for (auto &S : Entry.second.SummaryList)
       if (S->isLive()) {
         DEBUG(dbgs() << "Live root: " << Entry.first << "\n");
         Worklist.push_back(ValueInfo(/*IsAnalysis=*/false, &Entry));
         ++LiveSymbols;
         break;
       }
 
   // 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) {
     // 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;
+
+    // We do not keep live symbols that are known to be non-prevailing.
+    if (isPrevailing(VI.getGUID()) == PrevailingType::No)
+      return;
+
     for (auto &S : VI.getSummaryList())
       S->setLive(true);
     ++LiveSymbols;
     Worklist.push_back(VI);
   };
 
   while (!Worklist.empty()) {
     auto VI = 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);
       if (auto *FS = dyn_cast<FunctionSummary>(Base))
         for (auto Call : FS->calls())
           visit(Call.first);
     }
   }
   Index.setWithGlobalValueDeadStripping();
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.

llvm/trunk/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
+}

llvm/trunk/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
+}

llvm/trunk/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

llvm/trunk/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
 }

llvm/trunk/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()