diff options
author | dim <dim@FreeBSD.org> | 2016-12-26 20:36:37 +0000 |
---|---|---|
committer | dim <dim@FreeBSD.org> | 2016-12-26 20:36:37 +0000 |
commit | 06210ae42d418d50d8d9365d5c9419308ae9e7ee (patch) | |
tree | ab60b4cdd6e430dda1f292a46a77ddb744723f31 /contrib/llvm/lib/Transforms/IPO/FunctionImport.cpp | |
parent | 2dd166267f53df1c3748b4325d294b9b839de74b (diff) | |
download | FreeBSD-src-06210ae42d418d50d8d9365d5c9419308ae9e7ee.zip FreeBSD-src-06210ae42d418d50d8d9365d5c9419308ae9e7ee.tar.gz |
MFC r309124:
Upgrade our copies of clang, llvm, lldb, compiler-rt and libc++ to 3.9.0
release, and add lld 3.9.0. Also completely revamp the build system for
clang, llvm, lldb and their related tools.
Please note that from 3.5.0 onwards, clang, llvm and lldb require C++11
support to build; see UPDATING for more information.
Release notes for llvm, clang and lld are available here:
<http://llvm.org/releases/3.9.0/docs/ReleaseNotes.html>
<http://llvm.org/releases/3.9.0/tools/clang/docs/ReleaseNotes.html>
<http://llvm.org/releases/3.9.0/tools/lld/docs/ReleaseNotes.html>
Thanks to Ed Maste, Bryan Drewery, Andrew Turner, Antoine Brodin and Jan
Beich for their help.
Relnotes: yes
MFC r309147:
Pull in r282174 from upstream llvm trunk (by Krzysztof Parzyszek):
[PPC] Set SP after loading data from stack frame, if no red zone is
present
Follow-up to r280705: Make sure that the SP is only restored after
all data is loaded from the stack frame, if there is no red zone.
This completes the fix for
https://llvm.org/bugs/show_bug.cgi?id=26519.
Differential Revision: https://reviews.llvm.org/D24466
Reported by: Mark Millard
PR: 214433
MFC r309149:
Pull in r283060 from upstream llvm trunk (by Hal Finkel):
[PowerPC] Refactor soft-float support, and enable PPC64 soft float
This change enables soft-float for PowerPC64, and also makes
soft-float disable all vector instruction sets for both 32-bit and
64-bit modes. This latter part is necessary because the PPC backend
canonicalizes many Altivec vector types to floating-point types, and
so soft-float breaks scalarization support for many operations. Both
for embedded targets and for operating-system kernels desiring
soft-float support, it seems reasonable that disabling hardware
floating-point also disables vector instructions (embedded targets
without hardware floating point support are unlikely to have Altivec,
etc. and operating system kernels desiring not to use floating-point
registers to lower syscall cost are unlikely to want to use vector
registers either). If someone needs this to work, we'll need to
change the fact that we promote many Altivec operations to act on
v4f32. To make it possible to disable Altivec when soft-float is
enabled, hardware floating-point support needs to be expressed as a
positive feature, like the others, and not a negative feature,
because target features cannot have dependencies on the disabling of
some other feature. So +soft-float has now become -hard-float.
Fixes PR26970.
Pull in r283061 from upstream clang trunk (by Hal Finkel):
[PowerPC] Enable soft-float for PPC64, and +soft-float -> -hard-float
Enable soft-float support on PPC64, as the backend now supports it.
Also, the backend now uses -hard-float instead of +soft-float, so set
the target features accordingly.
Fixes PR26970.
Reported by: Mark Millard
PR: 214433
MFC r309212:
Add a few missed clang 3.9.0 files to OptionalObsoleteFiles.
MFC r309262:
Fix packaging for clang, lldb and lld 3.9.0
During the upgrade of clang/llvm etc to 3.9.0 in r309124, the PACKAGE
directive in the usr.bin/clang/*.mk files got dropped accidentally.
Restore it, with a few minor changes and additions:
* Correct license in clang.ucl to NCSA
* Add PACKAGE=clang for clang and most of the "ll" tools
* Put lldb in its own package
* Put lld in its own package
Reviewed by: gjb, jmallett
Differential Revision: https://reviews.freebsd.org/D8666
MFC r309656:
During the bootstrap phase, when building the minimal llvm library on
PowerPC, add lib/Support/Atomic.cpp. This is needed because upstream
llvm revision r271821 disabled the use of std::call_once, which causes
some fallback functions from Atomic.cpp to be used instead.
Reported by: Mark Millard
PR: 214902
MFC r309835:
Tentatively apply https://reviews.llvm.org/D18730 to work around gcc PR
70528 (bogus error: constructor required before non-static data member).
This should fix buildworld with the external gcc package.
Reported by: https://jenkins.freebsd.org/job/FreeBSD_HEAD_amd64_gcc/
MFC r310194:
Upgrade our copies of clang, llvm, lld, lldb, compiler-rt and libc++ to
3.9.1 release.
Please note that from 3.5.0 onwards, clang, llvm and lldb require C++11
support to build; see UPDATING for more information.
Release notes for llvm, clang and lld will be available here:
<http://releases.llvm.org/3.9.1/docs/ReleaseNotes.html>
<http://releases.llvm.org/3.9.1/tools/clang/docs/ReleaseNotes.html>
<http://releases.llvm.org/3.9.1/tools/lld/docs/ReleaseNotes.html>
Relnotes: yes
Diffstat (limited to 'contrib/llvm/lib/Transforms/IPO/FunctionImport.cpp')
-rw-r--r-- | contrib/llvm/lib/Transforms/IPO/FunctionImport.cpp | 871 |
1 files changed, 610 insertions, 261 deletions
diff --git a/contrib/llvm/lib/Transforms/IPO/FunctionImport.cpp b/contrib/llvm/lib/Transforms/IPO/FunctionImport.cpp index 5e0df95..c9d075e 100644 --- a/contrib/llvm/lib/Transforms/IPO/FunctionImport.cpp +++ b/contrib/llvm/lib/Transforms/IPO/FunctionImport.cpp @@ -13,329 +13,670 @@ #include "llvm/Transforms/IPO/FunctionImport.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/Statistic.h" #include "llvm/ADT/StringSet.h" +#include "llvm/ADT/Triple.h" #include "llvm/IR/AutoUpgrade.h" #include "llvm/IR/DiagnosticPrinter.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/Module.h" #include "llvm/IRReader/IRReader.h" #include "llvm/Linker/Linker.h" -#include "llvm/Object/FunctionIndexObjectFile.h" +#include "llvm/Object/IRObjectFile.h" +#include "llvm/Object/ModuleSummaryIndexObjectFile.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/SourceMgr.h" +#include "llvm/Transforms/IPO/Internalize.h" +#include "llvm/Transforms/Utils/FunctionImportUtils.h" -#include <map> +#define DEBUG_TYPE "function-import" using namespace llvm; -#define DEBUG_TYPE "function-import" +STATISTIC(NumImported, "Number of functions imported"); /// Limit on instruction count of imported functions. static cl::opt<unsigned> ImportInstrLimit( "import-instr-limit", cl::init(100), cl::Hidden, cl::value_desc("N"), cl::desc("Only import functions with less than N instructions")); +static cl::opt<float> + ImportInstrFactor("import-instr-evolution-factor", cl::init(0.7), + cl::Hidden, cl::value_desc("x"), + cl::desc("As we import functions, multiply the " + "`import-instr-limit` threshold by this factor " + "before processing newly imported functions")); + +static cl::opt<bool> PrintImports("print-imports", cl::init(false), cl::Hidden, + cl::desc("Print imported functions")); + +// Temporary allows the function import pass to disable always linking +// referenced discardable symbols. +static cl::opt<bool> + DontForceImportReferencedDiscardableSymbols("disable-force-link-odr", + cl::init(false), cl::Hidden); + +static cl::opt<bool> EnableImportMetadata( + "enable-import-metadata", cl::init( +#if !defined(NDEBUG) + true /*Enabled with asserts.*/ +#else + false +#endif + ), + cl::Hidden, cl::desc("Enable import metadata like 'thinlto_src_module'")); + // Load lazily a module from \p FileName in \p Context. static std::unique_ptr<Module> loadFile(const std::string &FileName, LLVMContext &Context) { SMDiagnostic Err; DEBUG(dbgs() << "Loading '" << FileName << "'\n"); - // Metadata isn't loaded or linked until after all functions are - // imported, after which it will be materialized and linked. + // Metadata isn't loaded until functions are imported, to minimize + // the memory overhead. std::unique_ptr<Module> Result = getLazyIRFileModule(FileName, Err, Context, /* ShouldLazyLoadMetadata = */ true); if (!Result) { Err.print("function-import", errs()); - return nullptr; + report_fatal_error("Abort"); } return Result; } namespace { -/// Helper to load on demand a Module from file and cache it for subsequent -/// queries. It can be used with the FunctionImporter. -class ModuleLazyLoaderCache { - /// Cache of lazily loaded module for import. - StringMap<std::unique_ptr<Module>> ModuleMap; - /// Retrieve a Module from the cache or lazily load it on demand. - std::function<std::unique_ptr<Module>(StringRef FileName)> createLazyModule; +// Return true if the Summary describes a GlobalValue that can be externally +// referenced, i.e. it does not need renaming (linkage is not local) or renaming +// is possible (does not have a section for instance). +static bool canBeExternallyReferenced(const GlobalValueSummary &Summary) { + if (!Summary.needsRenaming()) + return true; -public: - /// Create the loader, Module will be initialized in \p Context. - ModuleLazyLoaderCache(std::function< - std::unique_ptr<Module>(StringRef FileName)> createLazyModule) - : createLazyModule(createLazyModule) {} - - /// Retrieve a Module from the cache or lazily load it on demand. - Module &operator()(StringRef FileName); - - std::unique_ptr<Module> takeModule(StringRef FileName) { - auto I = ModuleMap.find(FileName); - assert(I != ModuleMap.end()); - std::unique_ptr<Module> Ret = std::move(I->second); - ModuleMap.erase(I); - return Ret; - } -}; + if (Summary.hasSection()) + // Can't rename a global that needs renaming if has a section. + return false; -// Get a Module for \p FileName from the cache, or load it lazily. -Module &ModuleLazyLoaderCache::operator()(StringRef Identifier) { - auto &Module = ModuleMap[Identifier]; - if (!Module) - Module = createLazyModule(Identifier); - return *Module; + return true; } -} // anonymous namespace -/// Walk through the instructions in \p F looking for external -/// calls not already in the \p CalledFunctions set. If any are -/// found they are added to the \p Worklist for importing. -static void findExternalCalls(const Module &DestModule, Function &F, - const FunctionInfoIndex &Index, - StringSet<> &CalledFunctions, - SmallVector<StringRef, 64> &Worklist) { - // We need to suffix internal function calls imported from other modules, - // prepare the suffix ahead of time. - std::string Suffix; - if (F.getParent() != &DestModule) - Suffix = - (Twine(".llvm.") + - Twine(Index.getModuleId(F.getParent()->getModuleIdentifier()))).str(); - - for (auto &BB : F) { - for (auto &I : BB) { - if (isa<CallInst>(I)) { - auto CalledFunction = cast<CallInst>(I).getCalledFunction(); - // Insert any new external calls that have not already been - // added to set/worklist. - if (!CalledFunction || !CalledFunction->hasName()) - continue; - // Ignore intrinsics early - if (CalledFunction->isIntrinsic()) { - assert(CalledFunction->getIntrinsicID() != 0); - continue; - } - auto ImportedName = CalledFunction->getName(); - auto Renamed = (ImportedName + Suffix).str(); - // Rename internal functions - if (CalledFunction->hasInternalLinkage()) { - ImportedName = Renamed; - } - auto It = CalledFunctions.insert(ImportedName); - if (!It.second) { - // This is a call to a function we already considered, skip. - continue; - } - // Ignore functions already present in the destination module - auto *SrcGV = DestModule.getNamedValue(ImportedName); - if (SrcGV) { - if (GlobalAlias *SGA = dyn_cast<GlobalAlias>(SrcGV)) - SrcGV = SGA->getBaseObject(); - assert(isa<Function>(SrcGV) && "Name collision during import"); - if (!cast<Function>(SrcGV)->isDeclaration()) { - DEBUG(dbgs() << DestModule.getModuleIdentifier() << ": Ignoring " - << ImportedName << " already in DestinationModule\n"); - continue; - } +// Return true if \p GUID describes a GlobalValue that can be externally +// referenced, i.e. it does not need renaming (linkage is not local) or +// renaming is possible (does not have a section for instance). +static bool canBeExternallyReferenced(const ModuleSummaryIndex &Index, + GlobalValue::GUID GUID) { + auto Summaries = Index.findGlobalValueSummaryList(GUID); + if (Summaries == Index.end()) + return true; + if (Summaries->second.size() != 1) + // If there are multiple globals with this GUID, then we know it is + // not a local symbol, and it is necessarily externally referenced. + return true; + + // We don't need to check for the module path, because if it can't be + // externally referenced and we call it, it is necessarilly in the same + // module + return canBeExternallyReferenced(**Summaries->second.begin()); +} + +// Return true if the global described by \p Summary can be imported in another +// module. +static bool eligibleForImport(const ModuleSummaryIndex &Index, + const GlobalValueSummary &Summary) { + if (!canBeExternallyReferenced(Summary)) + // Can't import a global that needs renaming if has a section for instance. + // FIXME: we may be able to import it by copying it without promotion. + return false; + + // Check references (and potential calls) in the same module. If the current + // value references a global that can't be externally referenced it is not + // eligible for import. + bool AllRefsCanBeExternallyReferenced = + llvm::all_of(Summary.refs(), [&](const ValueInfo &VI) { + return canBeExternallyReferenced(Index, VI.getGUID()); + }); + if (!AllRefsCanBeExternallyReferenced) + return false; + + if (auto *FuncSummary = dyn_cast<FunctionSummary>(&Summary)) { + bool AllCallsCanBeExternallyReferenced = llvm::all_of( + FuncSummary->calls(), [&](const FunctionSummary::EdgeTy &Edge) { + return canBeExternallyReferenced(Index, Edge.first.getGUID()); + }); + if (!AllCallsCanBeExternallyReferenced) + return false; + } + return true; +} + +/// Given a list of possible callee implementation for a call site, select one +/// that fits the \p Threshold. +/// +/// FIXME: select "best" instead of first that fits. But what is "best"? +/// - The smallest: more likely to be inlined. +/// - The one with the least outgoing edges (already well optimized). +/// - One from a module already being imported from in order to reduce the +/// number of source modules parsed/linked. +/// - One that has PGO data attached. +/// - [insert you fancy metric here] +static const GlobalValueSummary * +selectCallee(const ModuleSummaryIndex &Index, + const GlobalValueSummaryList &CalleeSummaryList, + unsigned Threshold) { + auto It = llvm::find_if( + CalleeSummaryList, + [&](const std::unique_ptr<GlobalValueSummary> &SummaryPtr) { + auto *GVSummary = SummaryPtr.get(); + if (GlobalValue::isInterposableLinkage(GVSummary->linkage())) + // There is no point in importing these, we can't inline them + return false; + if (auto *AS = dyn_cast<AliasSummary>(GVSummary)) { + GVSummary = &AS->getAliasee(); + // 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. + if (!GlobalValue::isLinkOnceODRLinkage(GVSummary->linkage())) + return false; } - Worklist.push_back(It.first->getKey()); - DEBUG(dbgs() << DestModule.getModuleIdentifier() - << ": Adding callee for : " << ImportedName << " : " - << F.getName() << "\n"); - } - } + auto *Summary = cast<FunctionSummary>(GVSummary); + + if (Summary->instCount() > Threshold) + return false; + + if (!eligibleForImport(Index, *Summary)) + return false; + + return true; + }); + if (It == CalleeSummaryList.end()) + return nullptr; + + return cast<GlobalValueSummary>(It->get()); +} + +/// Return the summary for the function \p GUID that fits the \p Threshold, or +/// null if there's no match. +static const GlobalValueSummary *selectCallee(GlobalValue::GUID GUID, + unsigned Threshold, + const ModuleSummaryIndex &Index) { + auto CalleeSummaryList = Index.findGlobalValueSummaryList(GUID); + if (CalleeSummaryList == Index.end()) + return nullptr; // This function does not have a summary + return selectCallee(Index, CalleeSummaryList->second, Threshold); +} + +/// Mark the global \p GUID as export by module \p ExportModulePath if found in +/// this module. If it is a GlobalVariable, we also mark any referenced global +/// in the current module as exported. +static void exportGlobalInModule(const ModuleSummaryIndex &Index, + StringRef ExportModulePath, + GlobalValue::GUID GUID, + FunctionImporter::ExportSetTy &ExportList) { + auto FindGlobalSummaryInModule = + [&](GlobalValue::GUID GUID) -> GlobalValueSummary *{ + auto SummaryList = Index.findGlobalValueSummaryList(GUID); + if (SummaryList == Index.end()) + // This global does not have a summary, it is not part of the ThinLTO + // process + return nullptr; + auto SummaryIter = llvm::find_if( + SummaryList->second, + [&](const std::unique_ptr<GlobalValueSummary> &Summary) { + return Summary->modulePath() == ExportModulePath; + }); + if (SummaryIter == SummaryList->second.end()) + return nullptr; + return SummaryIter->get(); + }; + + auto *Summary = FindGlobalSummaryInModule(GUID); + if (!Summary) + return; + // We found it in the current module, mark as exported + ExportList.insert(GUID); + + auto GVS = dyn_cast<GlobalVarSummary>(Summary); + if (!GVS) + return; + // FunctionImportGlobalProcessing::doPromoteLocalToGlobal() will always + // trigger importing the initializer for `constant unnamed addr` globals that + // are referenced. We conservatively export all the referenced symbols for + // every global to workaround this, so that the ExportList is accurate. + // FIXME: with a "isConstant" flag in the summary we could be more targetted. + for (auto &Ref : GVS->refs()) { + auto GUID = Ref.getGUID(); + auto *RefSummary = FindGlobalSummaryInModule(GUID); + if (RefSummary) + // Found a ref in the current module, mark it as exported + ExportList.insert(GUID); } } -// Helper function: given a worklist and an index, will process all the worklist -// and decide what to import based on the summary information. -// -// Nothing is actually imported, functions are materialized in their source -// module and analyzed there. -// -// \p ModuleToFunctionsToImportMap is filled with the set of Function to import -// per Module. -static void GetImportList(Module &DestModule, - SmallVector<StringRef, 64> &Worklist, - StringSet<> &CalledFunctions, - std::map<StringRef, DenseSet<const GlobalValue *>> - &ModuleToFunctionsToImportMap, - const FunctionInfoIndex &Index, - ModuleLazyLoaderCache &ModuleLoaderCache) { - while (!Worklist.empty()) { - auto CalledFunctionName = Worklist.pop_back_val(); - DEBUG(dbgs() << DestModule.getModuleIdentifier() << ": Process import for " - << CalledFunctionName << "\n"); - - // Try to get a summary for this function call. - auto InfoList = Index.findFunctionInfoList(CalledFunctionName); - if (InfoList == Index.end()) { - DEBUG(dbgs() << DestModule.getModuleIdentifier() << ": No summary for " - << CalledFunctionName << " Ignoring.\n"); +using EdgeInfo = std::pair<const FunctionSummary *, unsigned /* Threshold */>; + +/// Compute the list of functions to import for a given caller. Mark these +/// imported functions and the symbols they reference in their source module as +/// exported from their source module. +static void computeImportForFunction( + const FunctionSummary &Summary, const ModuleSummaryIndex &Index, + unsigned Threshold, const GVSummaryMapTy &DefinedGVSummaries, + SmallVectorImpl<EdgeInfo> &Worklist, + FunctionImporter::ImportMapTy &ImportsForModule, + StringMap<FunctionImporter::ExportSetTy> *ExportLists = nullptr) { + for (auto &Edge : Summary.calls()) { + auto GUID = Edge.first.getGUID(); + DEBUG(dbgs() << " edge -> " << GUID << " Threshold:" << Threshold << "\n"); + + if (DefinedGVSummaries.count(GUID)) { + DEBUG(dbgs() << "ignored! Target already in destination module.\n"); continue; } - assert(!InfoList->second.empty() && "No summary, error at import?"); - - // Comdat can have multiple entries, FIXME: what do we do with them? - auto &Info = InfoList->second[0]; - assert(Info && "Nullptr in list, error importing summaries?\n"); - - auto *Summary = Info->functionSummary(); - if (!Summary) { - // FIXME: in case we are lazyloading summaries, we can do it now. - DEBUG(dbgs() << DestModule.getModuleIdentifier() - << ": Missing summary for " << CalledFunctionName - << ", error at import?\n"); - llvm_unreachable("Missing summary"); - } - if (Summary->instCount() > ImportInstrLimit) { - DEBUG(dbgs() << DestModule.getModuleIdentifier() << ": Skip import of " - << CalledFunctionName << " with " << Summary->instCount() - << " instructions (limit " << ImportInstrLimit << ")\n"); + auto *CalleeSummary = selectCallee(GUID, Threshold, Index); + if (!CalleeSummary) { + DEBUG(dbgs() << "ignored! No qualifying callee with summary found.\n"); continue; } - - // Get the module path from the summary. - auto ModuleIdentifier = Summary->modulePath(); - DEBUG(dbgs() << DestModule.getModuleIdentifier() << ": Importing " - << CalledFunctionName << " from " << ModuleIdentifier << "\n"); - - auto &SrcModule = ModuleLoaderCache(ModuleIdentifier); - - // The function that we will import! - GlobalValue *SGV = SrcModule.getNamedValue(CalledFunctionName); - - if (!SGV) { - // The destination module is referencing function using their renamed name - // when importing a function that was originally local in the source - // module. The source module we have might not have been renamed so we try - // to remove the suffix added during the renaming to recover the original - // name in the source module. - std::pair<StringRef, StringRef> Split = - CalledFunctionName.split(".llvm."); - SGV = SrcModule.getNamedValue(Split.first); - assert(SGV && "Can't find function to import in source module"); + // "Resolve" the summary, traversing alias, + const FunctionSummary *ResolvedCalleeSummary; + if (isa<AliasSummary>(CalleeSummary)) { + ResolvedCalleeSummary = cast<FunctionSummary>( + &cast<AliasSummary>(CalleeSummary)->getAliasee()); + assert( + GlobalValue::isLinkOnceODRLinkage(ResolvedCalleeSummary->linkage()) && + "Unexpected alias to a non-linkonceODR in import list"); + } else + ResolvedCalleeSummary = cast<FunctionSummary>(CalleeSummary); + + assert(ResolvedCalleeSummary->instCount() <= Threshold && + "selectCallee() didn't honor the threshold"); + + auto ExportModulePath = ResolvedCalleeSummary->modulePath(); + auto &ProcessedThreshold = ImportsForModule[ExportModulePath][GUID]; + /// Since the traversal of the call graph is DFS, we can revisit a function + /// a second time with a higher threshold. In this case, it is added back to + /// the worklist with the new threshold. + if (ProcessedThreshold && ProcessedThreshold >= Threshold) { + DEBUG(dbgs() << "ignored! Target was already seen with Threshold " + << ProcessedThreshold << "\n"); + continue; } - if (!SGV) { - report_fatal_error(Twine("Can't load function '") + CalledFunctionName + - "' in Module '" + SrcModule.getModuleIdentifier() + - "', error in the summary?\n"); + // Mark this function as imported in this module, with the current Threshold + ProcessedThreshold = Threshold; + + // Make exports in the source module. + if (ExportLists) { + auto &ExportList = (*ExportLists)[ExportModulePath]; + ExportList.insert(GUID); + // Mark all functions and globals referenced by this function as exported + // to the outside if they are defined in the same source module. + for (auto &Edge : ResolvedCalleeSummary->calls()) { + auto CalleeGUID = Edge.first.getGUID(); + exportGlobalInModule(Index, ExportModulePath, CalleeGUID, ExportList); + } + for (auto &Ref : ResolvedCalleeSummary->refs()) { + auto GUID = Ref.getGUID(); + exportGlobalInModule(Index, ExportModulePath, GUID, ExportList); + } } - Function *F = dyn_cast<Function>(SGV); - if (!F && isa<GlobalAlias>(SGV)) { - auto *SGA = dyn_cast<GlobalAlias>(SGV); - F = dyn_cast<Function>(SGA->getBaseObject()); - CalledFunctionName = F->getName(); - } - assert(F && "Imported Function is ... not a Function"); - - // We cannot import weak_any functions/aliases without possibly affecting - // the order they are seen and selected by the linker, changing program - // semantics. - if (SGV->hasWeakAnyLinkage()) { - DEBUG(dbgs() << DestModule.getModuleIdentifier() - << ": Ignoring import request for weak-any " - << (isa<Function>(SGV) ? "function " : "alias ") - << CalledFunctionName << " from " - << SrcModule.getModuleIdentifier() << "\n"); + // Insert the newly imported function to the worklist. + Worklist.push_back(std::make_pair(ResolvedCalleeSummary, Threshold)); + } +} + +/// Given the list of globals defined in a module, compute the list of imports +/// as well as the list of "exports", i.e. the list of symbols referenced from +/// another module (that may require promotion). +static void ComputeImportForModule( + const GVSummaryMapTy &DefinedGVSummaries, const ModuleSummaryIndex &Index, + FunctionImporter::ImportMapTy &ImportsForModule, + StringMap<FunctionImporter::ExportSetTy> *ExportLists = nullptr) { + // Worklist contains the list of function imported in this module, for which + // we will analyse the callees and may import further down the callgraph. + SmallVector<EdgeInfo, 128> Worklist; + + // Populate the worklist with the import for the functions in the current + // module + for (auto &GVSummary : DefinedGVSummaries) { + auto *Summary = GVSummary.second; + if (auto *AS = dyn_cast<AliasSummary>(Summary)) + Summary = &AS->getAliasee(); + auto *FuncSummary = dyn_cast<FunctionSummary>(Summary); + if (!FuncSummary) + // Skip import for global variables continue; - } + DEBUG(dbgs() << "Initalize import for " << GVSummary.first << "\n"); + computeImportForFunction(*FuncSummary, Index, ImportInstrLimit, + DefinedGVSummaries, Worklist, ImportsForModule, + ExportLists); + } - // Add the function to the import list - auto &Entry = ModuleToFunctionsToImportMap[SrcModule.getModuleIdentifier()]; - Entry.insert(F); + while (!Worklist.empty()) { + auto FuncInfo = Worklist.pop_back_val(); + auto *Summary = FuncInfo.first; + auto Threshold = FuncInfo.second; // Process the newly imported functions and add callees to the worklist. - F->materialize(); - findExternalCalls(DestModule, *F, Index, CalledFunctions, Worklist); + // Adjust the threshold + Threshold = Threshold * ImportInstrFactor; + + computeImportForFunction(*Summary, Index, Threshold, DefinedGVSummaries, + Worklist, ImportsForModule, ExportLists); } } +} // anonymous namespace + +/// Compute all the import and export for every module using the Index. +void llvm::ComputeCrossModuleImport( + const ModuleSummaryIndex &Index, + const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries, + StringMap<FunctionImporter::ImportMapTy> &ImportLists, + StringMap<FunctionImporter::ExportSetTy> &ExportLists) { + // For each module that has function defined, compute the import/export lists. + for (auto &DefinedGVSummaries : ModuleToDefinedGVSummaries) { + auto &ImportsForModule = ImportLists[DefinedGVSummaries.first()]; + DEBUG(dbgs() << "Computing import for Module '" + << DefinedGVSummaries.first() << "'\n"); + ComputeImportForModule(DefinedGVSummaries.second, Index, ImportsForModule, + &ExportLists); + } + +#ifndef NDEBUG + DEBUG(dbgs() << "Import/Export lists for " << ImportLists.size() + << " modules:\n"); + for (auto &ModuleImports : ImportLists) { + auto ModName = ModuleImports.first(); + auto &Exports = ExportLists[ModName]; + DEBUG(dbgs() << "* Module " << ModName << " exports " << Exports.size() + << " functions. Imports from " << ModuleImports.second.size() + << " modules.\n"); + for (auto &Src : ModuleImports.second) { + auto SrcModName = Src.first(); + DEBUG(dbgs() << " - " << Src.second.size() << " functions imported from " + << SrcModName << "\n"); + } + } +#endif +} + +/// Compute all the imports for the given module in the Index. +void llvm::ComputeCrossModuleImportForModule( + StringRef ModulePath, const ModuleSummaryIndex &Index, + FunctionImporter::ImportMapTy &ImportList) { + + // Collect the list of functions this module defines. + // GUID -> Summary + GVSummaryMapTy FunctionSummaryMap; + Index.collectDefinedFunctionsForModule(ModulePath, FunctionSummaryMap); + + // Compute the import list for this module. + DEBUG(dbgs() << "Computing import for Module '" << ModulePath << "'\n"); + ComputeImportForModule(FunctionSummaryMap, Index, ImportList); + +#ifndef NDEBUG + DEBUG(dbgs() << "* Module " << ModulePath << " imports from " + << ImportList.size() << " modules.\n"); + for (auto &Src : ImportList) { + auto SrcModName = Src.first(); + DEBUG(dbgs() << " - " << Src.second.size() << " functions imported from " + << SrcModName << "\n"); + } +#endif +} + +/// Compute the set of summaries needed for a ThinLTO backend compilation of +/// \p ModulePath. +void llvm::gatherImportedSummariesForModule( + StringRef ModulePath, + const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries, + const StringMap<FunctionImporter::ImportMapTy> &ImportLists, + std::map<std::string, GVSummaryMapTy> &ModuleToSummariesForIndex) { + // Include all summaries from the importing module. + ModuleToSummariesForIndex[ModulePath] = + ModuleToDefinedGVSummaries.lookup(ModulePath); + auto ModuleImports = ImportLists.find(ModulePath); + if (ModuleImports != ImportLists.end()) { + // Include summaries for imports. + for (auto &ILI : ModuleImports->second) { + auto &SummariesForIndex = ModuleToSummariesForIndex[ILI.first()]; + const auto &DefinedGVSummaries = + ModuleToDefinedGVSummaries.lookup(ILI.first()); + for (auto &GI : ILI.second) { + const auto &DS = DefinedGVSummaries.find(GI.first); + assert(DS != DefinedGVSummaries.end() && + "Expected a defined summary for imported global value"); + SummariesForIndex[GI.first] = DS->second; + } + } + } +} + +/// Emit the files \p ModulePath will import from into \p OutputFilename. +std::error_code llvm::EmitImportsFiles( + StringRef ModulePath, StringRef OutputFilename, + const StringMap<FunctionImporter::ImportMapTy> &ImportLists) { + auto ModuleImports = ImportLists.find(ModulePath); + std::error_code EC; + raw_fd_ostream ImportsOS(OutputFilename, EC, sys::fs::OpenFlags::F_None); + if (EC) + return EC; + if (ModuleImports != ImportLists.end()) + for (auto &ILI : ModuleImports->second) + 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 updateLinkage = [&](GlobalValue &GV) { + if (!GlobalValue::isWeakForLinker(GV.getLinkage())) + return; + // 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; + DEBUG(dbgs() << "ODR fixing up linkage for `" << GV.getName() << "` from " + << GV.getLinkage() << " to " << NewLinkage << "\n"); + GV.setLinkage(NewLinkage); + }; + + // Process functions and global now + for (auto &GV : TheModule) + updateLinkage(GV); + for (auto &GV : TheModule.globals()) + updateLinkage(GV); + for (auto &GV : TheModule.aliases()) + updateLinkage(GV); +} + +/// Run internalization on \p TheModule based on symmary analysis. +void llvm::thinLTOInternalizeModule(Module &TheModule, + const GVSummaryMapTy &DefinedGlobals) { + // Parse inline ASM and collect the list of symbols that are not defined in + // the current module. + StringSet<> AsmUndefinedRefs; + object::IRObjectFile::CollectAsmUndefinedRefs( + Triple(TheModule.getTargetTriple()), TheModule.getModuleInlineAsm(), + [&AsmUndefinedRefs](StringRef Name, object::BasicSymbolRef::Flags Flags) { + if (Flags & object::BasicSymbolRef::SF_Undefined) + AsmUndefinedRefs.insert(Name); + }); + + // Declare a callback for the internalize pass that will ask for every + // candidate GlobalValue if it can be internalized or not. + auto MustPreserveGV = [&](const GlobalValue &GV) -> bool { + // Can't be internalized if referenced in inline asm. + if (AsmUndefinedRefs.count(GV.getName())) + return true; + + // Lookup the linkage recorded in the summaries during global analysis. + const auto &GS = DefinedGlobals.find(GV.getGUID()); + GlobalValue::LinkageTypes Linkage; + if (GS == DefinedGlobals.end()) { + // Must have been promoted (possibly conservatively). Find original + // name so that we can access the correct summary and see if it can + // be internalized again. + // FIXME: Eventually we should control promotion instead of promoting + // and internalizing again. + StringRef OrigName = + ModuleSummaryIndex::getOriginalNameBeforePromote(GV.getName()); + std::string OrigId = GlobalValue::getGlobalIdentifier( + OrigName, GlobalValue::InternalLinkage, + TheModule.getSourceFileName()); + const auto &GS = DefinedGlobals.find(GlobalValue::getGUID(OrigId)); + if (GS == DefinedGlobals.end()) { + // Also check the original non-promoted non-globalized name. In some + // cases a preempted weak value is linked in as a local copy because + // it is referenced by an alias (IRLinker::linkGlobalValueProto). + // In that case, since it was originally not a local value, it was + // recorded in the index using the original name. + // FIXME: This may not be needed once PR27866 is fixed. + const auto &GS = DefinedGlobals.find(GlobalValue::getGUID(OrigName)); + assert(GS != DefinedGlobals.end()); + Linkage = GS->second->linkage(); + } else { + Linkage = GS->second->linkage(); + } + } else + Linkage = GS->second->linkage(); + return !GlobalValue::isLocalLinkage(Linkage); + }; + + // FIXME: See if we can just internalize directly here via linkage changes + // based on the index, rather than invoking internalizeModule. + llvm::internalizeModule(TheModule, MustPreserveGV); +} + // Automatically import functions in Module \p DestModule based on the summaries // index. // -// The current implementation imports every called functions that exists in the -// summaries index. -bool FunctionImporter::importFunctions(Module &DestModule) { +bool FunctionImporter::importFunctions( + Module &DestModule, const FunctionImporter::ImportMapTy &ImportList, + bool ForceImportReferencedDiscardableSymbols) { DEBUG(dbgs() << "Starting import for Module " << DestModule.getModuleIdentifier() << "\n"); unsigned ImportedCount = 0; - /// First step is collecting the called external functions. - StringSet<> CalledFunctions; - SmallVector<StringRef, 64> Worklist; - for (auto &F : DestModule) { - if (F.isDeclaration() || F.hasFnAttribute(Attribute::OptimizeNone)) - continue; - findExternalCalls(DestModule, F, Index, CalledFunctions, Worklist); - } - if (Worklist.empty()) - return false; - - /// Second step: for every call to an external function, try to import it. - // Linker that will be used for importing function Linker TheLinker(DestModule); - - // Map of Module -> List of Function to import from the Module - std::map<StringRef, DenseSet<const GlobalValue *>> - ModuleToFunctionsToImportMap; - - // Analyze the summaries and get the list of functions to import by - // populating ModuleToFunctionsToImportMap - ModuleLazyLoaderCache ModuleLoaderCache(ModuleLoader); - GetImportList(DestModule, Worklist, CalledFunctions, - ModuleToFunctionsToImportMap, Index, ModuleLoaderCache); - assert(Worklist.empty() && "Worklist hasn't been flushed in GetImportList"); - - StringMap<std::unique_ptr<DenseMap<unsigned, MDNode *>>> - ModuleToTempMDValsMap; - // Do the actual import of functions now, one Module at a time - for (auto &FunctionsToImportPerModule : ModuleToFunctionsToImportMap) { + std::set<StringRef> ModuleNameOrderedList; + for (auto &FunctionsToImportPerModule : ImportList) { + ModuleNameOrderedList.insert(FunctionsToImportPerModule.first()); + } + for (auto &Name : ModuleNameOrderedList) { // Get the module for the import - auto &FunctionsToImport = FunctionsToImportPerModule.second; - std::unique_ptr<Module> SrcModule = - ModuleLoaderCache.takeModule(FunctionsToImportPerModule.first); + const auto &FunctionsToImportPerModule = ImportList.find(Name); + assert(FunctionsToImportPerModule != ImportList.end()); + std::unique_ptr<Module> SrcModule = ModuleLoader(Name); assert(&DestModule.getContext() == &SrcModule->getContext() && "Context mismatch"); - // Save the mapping of value ids to temporary metadata created when - // importing this function. If we have already imported from this module, - // add new temporary metadata to the existing mapping. - auto &TempMDVals = ModuleToTempMDValsMap[SrcModule->getModuleIdentifier()]; - if (!TempMDVals) - TempMDVals = llvm::make_unique<DenseMap<unsigned, MDNode *>>(); + // If modules were created with lazy metadata loading, materialize it + // now, before linking it (otherwise this will be a noop). + SrcModule->materializeMetadata(); + UpgradeDebugInfo(*SrcModule); + + auto &ImportGUIDs = FunctionsToImportPerModule->second; + // Find the globals to import + DenseSet<const GlobalValue *> GlobalsToImport; + for (Function &F : *SrcModule) { + if (!F.hasName()) + continue; + auto GUID = F.getGUID(); + auto Import = ImportGUIDs.count(GUID); + DEBUG(dbgs() << (Import ? "Is" : "Not") << " importing function " << GUID + << " " << F.getName() << " from " + << SrcModule->getSourceFileName() << "\n"); + if (Import) { + F.materialize(); + if (EnableImportMetadata) { + // Add 'thinlto_src_module' metadata for statistics and debugging. + F.setMetadata( + "thinlto_src_module", + llvm::MDNode::get( + DestModule.getContext(), + {llvm::MDString::get(DestModule.getContext(), + SrcModule->getSourceFileName())})); + } + GlobalsToImport.insert(&F); + } + } + for (GlobalVariable &GV : SrcModule->globals()) { + if (!GV.hasName()) + continue; + auto GUID = GV.getGUID(); + auto Import = ImportGUIDs.count(GUID); + DEBUG(dbgs() << (Import ? "Is" : "Not") << " importing global " << GUID + << " " << GV.getName() << " from " + << SrcModule->getSourceFileName() << "\n"); + if (Import) { + GV.materialize(); + GlobalsToImport.insert(&GV); + } + } + for (GlobalAlias &GA : SrcModule->aliases()) { + if (!GA.hasName()) + continue; + auto GUID = GA.getGUID(); + auto Import = ImportGUIDs.count(GUID); + DEBUG(dbgs() << (Import ? "Is" : "Not") << " importing alias " << GUID + << " " << GA.getName() << " from " + << SrcModule->getSourceFileName() << "\n"); + if (Import) { + // 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. This has been handled by + // computeImportForFunction() + GlobalObject *GO = GA.getBaseObject(); + assert(GO->hasLinkOnceODRLinkage() && + "Unexpected alias to a non-linkonceODR in import list"); +#ifndef NDEBUG + if (!GlobalsToImport.count(GO)) + DEBUG(dbgs() << " alias triggers importing aliasee " << GO->getGUID() + << " " << GO->getName() << " from " + << SrcModule->getSourceFileName() << "\n"); +#endif + GO->materialize(); + GlobalsToImport.insert(GO); + GA.materialize(); + GlobalsToImport.insert(&GA); + } + } // Link in the specified functions. - if (TheLinker.linkInModule(std::move(SrcModule), Linker::Flags::None, - &Index, &FunctionsToImport, TempMDVals.get())) + if (renameModuleForThinLTO(*SrcModule, Index, &GlobalsToImport)) + return true; + + if (PrintImports) { + for (const auto *GV : GlobalsToImport) + dbgs() << DestModule.getSourceFileName() << ": Import " << GV->getName() + << " from " << SrcModule->getSourceFileName() << "\n"; + } + + // Instruct the linker that the client will take care of linkonce resolution + unsigned Flags = Linker::Flags::None; + if (!ForceImportReferencedDiscardableSymbols) + Flags |= Linker::Flags::DontForceLinkLinkonceODR; + + if (TheLinker.linkInModule(std::move(SrcModule), Flags, &GlobalsToImport)) report_fatal_error("Function Import: link error"); - ImportedCount += FunctionsToImport.size(); + ImportedCount += GlobalsToImport.size(); } - // Now link in metadata for all modules from which we imported functions. - for (StringMapEntry<std::unique_ptr<DenseMap<unsigned, MDNode *>>> &SME : - ModuleToTempMDValsMap) { - // Load the specified source module. - auto &SrcModule = ModuleLoaderCache(SME.getKey()); - // The modules were created with lazy metadata loading. Materialize it - // now, before linking it. - SrcModule.materializeMetadata(); - UpgradeDebugInfo(SrcModule); - - // Link in all necessary metadata from this module. - if (TheLinker.linkInMetadata(SrcModule, SME.getValue().get())) - return false; - } + NumImported += ImportedCount; DEBUG(dbgs() << "Imported " << ImportedCount << " functions for Module " << DestModule.getModuleIdentifier() << "\n"); @@ -355,11 +696,11 @@ static void diagnosticHandler(const DiagnosticInfo &DI) { OS << '\n'; } -/// Parse the function index out of an IR file and return the function +/// Parse the summary index out of an IR file and return the summary /// index object if found, or nullptr if not. -static std::unique_ptr<FunctionInfoIndex> -getFunctionIndexForFile(StringRef Path, std::string &Error, - DiagnosticHandlerFunction DiagnosticHandler) { +static std::unique_ptr<ModuleSummaryIndex> getModuleSummaryIndexForFile( + StringRef Path, std::string &Error, + const DiagnosticHandlerFunction &DiagnosticHandler) { std::unique_ptr<MemoryBuffer> Buffer; ErrorOr<std::unique_ptr<MemoryBuffer>> BufferOrErr = MemoryBuffer::getFile(Path); @@ -368,9 +709,9 @@ getFunctionIndexForFile(StringRef Path, std::string &Error, return nullptr; } Buffer = std::move(BufferOrErr.get()); - ErrorOr<std::unique_ptr<object::FunctionIndexObjectFile>> ObjOrErr = - object::FunctionIndexObjectFile::create(Buffer->getMemBufferRef(), - DiagnosticHandler); + ErrorOr<std::unique_ptr<object::ModuleSummaryIndexObjectFile>> ObjOrErr = + object::ModuleSummaryIndexObjectFile::create(Buffer->getMemBufferRef(), + DiagnosticHandler); if (std::error_code EC = ObjOrErr.getError()) { Error = EC.message(); return nullptr; @@ -381,32 +722,34 @@ getFunctionIndexForFile(StringRef Path, std::string &Error, namespace { /// Pass that performs cross-module function import provided a summary file. class FunctionImportPass : public ModulePass { - /// Optional function summary index to use for importing, otherwise + /// Optional module summary index to use for importing, otherwise /// the summary-file option must be specified. - const FunctionInfoIndex *Index; + const ModuleSummaryIndex *Index; public: /// Pass identification, replacement for typeid static char ID; /// Specify pass name for debug output - const char *getPassName() const override { - return "Function Importing"; - } + const char *getPassName() const override { return "Function Importing"; } - explicit FunctionImportPass(const FunctionInfoIndex *Index = nullptr) + explicit FunctionImportPass(const ModuleSummaryIndex *Index = nullptr) : ModulePass(ID), Index(Index) {} bool runOnModule(Module &M) override { + if (skipModule(M)) + return false; + if (SummaryFile.empty() && !Index) report_fatal_error("error: -function-import requires -summary-file or " "file from frontend\n"); - std::unique_ptr<FunctionInfoIndex> IndexPtr; + std::unique_ptr<ModuleSummaryIndex> IndexPtr; if (!SummaryFile.empty()) { if (Index) report_fatal_error("error: -summary-file and index from frontend\n"); std::string Error; - IndexPtr = getFunctionIndexForFile(SummaryFile, Error, diagnosticHandler); + IndexPtr = + getModuleSummaryIndexForFile(SummaryFile, Error, diagnosticHandler); if (!IndexPtr) { errs() << "Error loading file '" << SummaryFile << "': " << Error << "\n"; @@ -415,9 +758,14 @@ public: Index = IndexPtr.get(); } - // First we need to promote to global scope and rename any local values that + // First step is collecting the import list. + FunctionImporter::ImportMapTy ImportList; + ComputeCrossModuleImportForModule(M.getModuleIdentifier(), *Index, + ImportList); + + // Next we need to promote to global scope and rename any local values that // are potentially exported to other modules. - if (renameModuleForThinLTO(M, Index)) { + if (renameModuleForThinLTO(M, *Index, nullptr)) { errs() << "Error renaming module\n"; return false; } @@ -427,7 +775,8 @@ public: return loadFile(Identifier, M.getContext()); }; FunctionImporter Importer(*Index, ModuleLoader); - return Importer.importFunctions(M); + return Importer.importFunctions( + M, ImportList, !DontForceImportReferencedDiscardableSymbols); } }; } // anonymous namespace @@ -439,7 +788,7 @@ INITIALIZE_PASS_END(FunctionImportPass, "function-import", "Summary Based Function Import", false, false) namespace llvm { -Pass *createFunctionImportPass(const FunctionInfoIndex *Index = nullptr) { +Pass *createFunctionImportPass(const ModuleSummaryIndex *Index = nullptr) { return new FunctionImportPass(Index); } } |