142418abaSMehdi Amini //===- FunctionImport.cpp - ThinLTO Summary-based Function Import ---------===//
242418abaSMehdi Amini //
342418abaSMehdi Amini //                     The LLVM Compiler Infrastructure
442418abaSMehdi Amini //
542418abaSMehdi Amini // This file is distributed under the University of Illinois Open Source
642418abaSMehdi Amini // License. See LICENSE.TXT for details.
742418abaSMehdi Amini //
842418abaSMehdi Amini //===----------------------------------------------------------------------===//
942418abaSMehdi Amini //
1042418abaSMehdi Amini // This file implements Function import based on summaries.
1142418abaSMehdi Amini //
1242418abaSMehdi Amini //===----------------------------------------------------------------------===//
1342418abaSMehdi Amini 
1442418abaSMehdi Amini #include "llvm/Transforms/IPO/FunctionImport.h"
1542418abaSMehdi Amini 
1601e32130SMehdi Amini #include "llvm/ADT/SmallVector.h"
17d29478f7STeresa Johnson #include "llvm/ADT/Statistic.h"
1842418abaSMehdi Amini #include "llvm/ADT/StringSet.h"
1942418abaSMehdi Amini #include "llvm/IR/AutoUpgrade.h"
2042418abaSMehdi Amini #include "llvm/IR/DiagnosticPrinter.h"
2142418abaSMehdi Amini #include "llvm/IR/IntrinsicInst.h"
2242418abaSMehdi Amini #include "llvm/IR/Module.h"
2342418abaSMehdi Amini #include "llvm/IRReader/IRReader.h"
2442418abaSMehdi Amini #include "llvm/Linker/Linker.h"
2526ab5772STeresa Johnson #include "llvm/Object/ModuleSummaryIndexObjectFile.h"
2642418abaSMehdi Amini #include "llvm/Support/CommandLine.h"
2742418abaSMehdi Amini #include "llvm/Support/Debug.h"
2842418abaSMehdi Amini #include "llvm/Support/SourceMgr.h"
29488a800aSTeresa Johnson #include "llvm/Transforms/Utils/FunctionImportUtils.h"
307e88d0daSMehdi Amini 
3101e32130SMehdi Amini #define DEBUG_TYPE "function-import"
327e88d0daSMehdi Amini 
3342418abaSMehdi Amini using namespace llvm;
3442418abaSMehdi Amini 
35d29478f7STeresa Johnson STATISTIC(NumImported, "Number of functions imported");
36d29478f7STeresa Johnson 
3739303619STeresa Johnson /// Limit on instruction count of imported functions.
3839303619STeresa Johnson static cl::opt<unsigned> ImportInstrLimit(
3939303619STeresa Johnson     "import-instr-limit", cl::init(100), cl::Hidden, cl::value_desc("N"),
4039303619STeresa Johnson     cl::desc("Only import functions with less than N instructions"));
4139303619STeresa Johnson 
4240641748SMehdi Amini static cl::opt<float>
4340641748SMehdi Amini     ImportInstrFactor("import-instr-evolution-factor", cl::init(0.7),
4440641748SMehdi Amini                       cl::Hidden, cl::value_desc("x"),
4540641748SMehdi Amini                       cl::desc("As we import functions, multiply the "
4640641748SMehdi Amini                                "`import-instr-limit` threshold by this factor "
4740641748SMehdi Amini                                "before processing newly imported functions"));
4840641748SMehdi Amini 
49d29478f7STeresa Johnson static cl::opt<bool> PrintImports("print-imports", cl::init(false), cl::Hidden,
50d29478f7STeresa Johnson                                   cl::desc("Print imported functions"));
51d29478f7STeresa Johnson 
52bda3c97cSMehdi Amini // Temporary allows the function import pass to disable always linking
53bda3c97cSMehdi Amini // referenced discardable symbols.
54bda3c97cSMehdi Amini static cl::opt<bool>
55bda3c97cSMehdi Amini     DontForceImportReferencedDiscardableSymbols("disable-force-link-odr",
56bda3c97cSMehdi Amini                                                 cl::init(false), cl::Hidden);
57bda3c97cSMehdi Amini 
5842418abaSMehdi Amini // Load lazily a module from \p FileName in \p Context.
5942418abaSMehdi Amini static std::unique_ptr<Module> loadFile(const std::string &FileName,
6042418abaSMehdi Amini                                         LLVMContext &Context) {
6142418abaSMehdi Amini   SMDiagnostic Err;
6242418abaSMehdi Amini   DEBUG(dbgs() << "Loading '" << FileName << "'\n");
636cba37ceSTeresa Johnson   // Metadata isn't loaded until functions are imported, to minimize
646cba37ceSTeresa Johnson   // the memory overhead.
65a1080ee6STeresa Johnson   std::unique_ptr<Module> Result =
66a1080ee6STeresa Johnson       getLazyIRFileModule(FileName, Err, Context,
67a1080ee6STeresa Johnson                           /* ShouldLazyLoadMetadata = */ true);
6842418abaSMehdi Amini   if (!Result) {
6942418abaSMehdi Amini     Err.print("function-import", errs());
70d7ad221cSMehdi Amini     report_fatal_error("Abort");
7142418abaSMehdi Amini   }
7242418abaSMehdi Amini 
7342418abaSMehdi Amini   return Result;
7442418abaSMehdi Amini }
7542418abaSMehdi Amini 
767e88d0daSMehdi Amini namespace {
7740641748SMehdi Amini 
78*b4e1e829SMehdi Amini // Return true if the Summary describes a GlobalValue that can be externally
79*b4e1e829SMehdi Amini // referenced, i.e. it does not need renaming (linkage is not local) or renaming
80*b4e1e829SMehdi Amini // is possible (does not have a section for instance).
81*b4e1e829SMehdi Amini static bool canBeExternallyReferenced(const GlobalValueSummary &Summary) {
82*b4e1e829SMehdi Amini   if (!Summary.needsRenaming())
83*b4e1e829SMehdi Amini     return true;
84*b4e1e829SMehdi Amini 
85*b4e1e829SMehdi Amini   if (Summary.hasSection())
86*b4e1e829SMehdi Amini     // Can't rename a global that needs renaming if has a section.
87*b4e1e829SMehdi Amini     return false;
88*b4e1e829SMehdi Amini 
89*b4e1e829SMehdi Amini   return true;
90*b4e1e829SMehdi Amini }
91*b4e1e829SMehdi Amini 
92*b4e1e829SMehdi Amini // Return true if \p GUID describes a GlobalValue that can be externally
93*b4e1e829SMehdi Amini // referenced, i.e. it does not need renaming (linkage is not local) or
94*b4e1e829SMehdi Amini // renaming is possible (does not have a section for instance).
95*b4e1e829SMehdi Amini static bool canBeExternallyReferenced(const ModuleSummaryIndex &Index,
96*b4e1e829SMehdi Amini                                       GlobalValue::GUID GUID) {
97*b4e1e829SMehdi Amini   auto Summaries = Index.findGlobalValueSummaryList(GUID);
98*b4e1e829SMehdi Amini   if (Summaries == Index.end())
99*b4e1e829SMehdi Amini     return true;
100*b4e1e829SMehdi Amini   if (Summaries->second.size() != 1)
101*b4e1e829SMehdi Amini     // If there are multiple globals with this GUID, then we know it is
102*b4e1e829SMehdi Amini     // not a local symbol, and it is necessarily externally referenced.
103*b4e1e829SMehdi Amini     return true;
104*b4e1e829SMehdi Amini 
105*b4e1e829SMehdi Amini   // We don't need to check for the module path, because if it can't be
106*b4e1e829SMehdi Amini   // externally referenced and we call it, it is necessarilly in the same
107*b4e1e829SMehdi Amini   // module
108*b4e1e829SMehdi Amini   return canBeExternallyReferenced(**Summaries->second.begin());
109*b4e1e829SMehdi Amini }
110*b4e1e829SMehdi Amini 
111*b4e1e829SMehdi Amini // Return true if the global described by \p Summary can be imported in another
112*b4e1e829SMehdi Amini // module.
113*b4e1e829SMehdi Amini static bool eligibleForImport(const ModuleSummaryIndex &Index,
114*b4e1e829SMehdi Amini                               const GlobalValueSummary &Summary) {
115*b4e1e829SMehdi Amini   if (!canBeExternallyReferenced(Summary))
116*b4e1e829SMehdi Amini     // Can't import a global that needs renaming if has a section for instance.
117*b4e1e829SMehdi Amini     // FIXME: we may be able to import it by copying it without promotion.
118*b4e1e829SMehdi Amini     return false;
119*b4e1e829SMehdi Amini 
120*b4e1e829SMehdi Amini   // Check references (and potential calls) in the same module. If the current
121*b4e1e829SMehdi Amini   // value references a global that can't be externally referenced it is not
122*b4e1e829SMehdi Amini   // eligible for import.
123*b4e1e829SMehdi Amini   bool AllRefsCanBeExternallyReferenced =
124*b4e1e829SMehdi Amini       llvm::all_of(Summary.refs(), [&](const ValueInfo &VI) {
125*b4e1e829SMehdi Amini         return canBeExternallyReferenced(Index, VI.getGUID());
126*b4e1e829SMehdi Amini       });
127*b4e1e829SMehdi Amini   if (!AllRefsCanBeExternallyReferenced)
128*b4e1e829SMehdi Amini     return false;
129*b4e1e829SMehdi Amini 
130*b4e1e829SMehdi Amini   if (auto *FuncSummary = dyn_cast<FunctionSummary>(&Summary)) {
131*b4e1e829SMehdi Amini     bool AllCallsCanBeExternallyReferenced = llvm::all_of(
132*b4e1e829SMehdi Amini         FuncSummary->calls(), [&](const FunctionSummary::EdgeTy &Edge) {
133*b4e1e829SMehdi Amini           return canBeExternallyReferenced(Index, Edge.first.getGUID());
134*b4e1e829SMehdi Amini         });
135*b4e1e829SMehdi Amini     if (!AllCallsCanBeExternallyReferenced)
136*b4e1e829SMehdi Amini       return false;
137*b4e1e829SMehdi Amini   }
138*b4e1e829SMehdi Amini   return true;
139*b4e1e829SMehdi Amini }
140*b4e1e829SMehdi Amini 
14101e32130SMehdi Amini /// Given a list of possible callee implementation for a call site, select one
14201e32130SMehdi Amini /// that fits the \p Threshold.
14301e32130SMehdi Amini ///
14401e32130SMehdi Amini /// FIXME: select "best" instead of first that fits. But what is "best"?
14501e32130SMehdi Amini /// - The smallest: more likely to be inlined.
14601e32130SMehdi Amini /// - The one with the least outgoing edges (already well optimized).
14701e32130SMehdi Amini /// - One from a module already being imported from in order to reduce the
14801e32130SMehdi Amini ///   number of source modules parsed/linked.
14901e32130SMehdi Amini /// - One that has PGO data attached.
15001e32130SMehdi Amini /// - [insert you fancy metric here]
1512d28f7aaSMehdi Amini static const GlobalValueSummary *
152*b4e1e829SMehdi Amini selectCallee(const ModuleSummaryIndex &Index,
153*b4e1e829SMehdi Amini              const GlobalValueSummaryList &CalleeSummaryList,
15428e457bcSTeresa Johnson              unsigned Threshold) {
15501e32130SMehdi Amini   auto It = llvm::find_if(
15628e457bcSTeresa Johnson       CalleeSummaryList,
15728e457bcSTeresa Johnson       [&](const std::unique_ptr<GlobalValueSummary> &SummaryPtr) {
15828e457bcSTeresa Johnson         auto *GVSummary = SummaryPtr.get();
1592c719cc1SMehdi Amini         if (GlobalValue::isWeakAnyLinkage(GVSummary->linkage()))
1602c719cc1SMehdi Amini           // There is no point in importing weak symbols, we can't inline them
16101e32130SMehdi Amini           return false;
1622c719cc1SMehdi Amini         if (auto *AS = dyn_cast<AliasSummary>(GVSummary)) {
1632c719cc1SMehdi Amini           GVSummary = &AS->getAliasee();
1642c719cc1SMehdi Amini           // Alias can't point to "available_externally". However when we import
1652c719cc1SMehdi Amini           // linkOnceODR the linkage does not change. So we import the alias
1662c719cc1SMehdi Amini           // and aliasee only in this case.
1672c719cc1SMehdi Amini           // FIXME: we should import alias as available_externally *function*,
1682c719cc1SMehdi Amini           // the destination module does need to know it is an alias.
1692c719cc1SMehdi Amini           if (!GlobalValue::isLinkOnceODRLinkage(GVSummary->linkage()))
1702c719cc1SMehdi Amini             return false;
1712c719cc1SMehdi Amini         }
1722c719cc1SMehdi Amini 
1732c719cc1SMehdi Amini         auto *Summary = cast<FunctionSummary>(GVSummary);
1747e88d0daSMehdi Amini 
17501e32130SMehdi Amini         if (Summary->instCount() > Threshold)
17601e32130SMehdi Amini           return false;
1777e88d0daSMehdi Amini 
178*b4e1e829SMehdi Amini         if (!eligibleForImport(Index, *Summary))
179*b4e1e829SMehdi Amini           return false;
180*b4e1e829SMehdi Amini 
18101e32130SMehdi Amini         return true;
18201e32130SMehdi Amini       });
18328e457bcSTeresa Johnson   if (It == CalleeSummaryList.end())
18401e32130SMehdi Amini     return nullptr;
1857e88d0daSMehdi Amini 
18628e457bcSTeresa Johnson   return cast<GlobalValueSummary>(It->get());
187434e9561SRafael Espindola }
1887e88d0daSMehdi Amini 
18901e32130SMehdi Amini /// Return the summary for the function \p GUID that fits the \p Threshold, or
19001e32130SMehdi Amini /// null if there's no match.
1912d28f7aaSMehdi Amini static const GlobalValueSummary *selectCallee(GlobalValue::GUID GUID,
192ad5741b0SMehdi Amini                                               unsigned Threshold,
19301e32130SMehdi Amini                                               const ModuleSummaryIndex &Index) {
19428e457bcSTeresa Johnson   auto CalleeSummaryList = Index.findGlobalValueSummaryList(GUID);
195*b4e1e829SMehdi Amini   if (CalleeSummaryList == Index.end())
19601e32130SMehdi Amini     return nullptr; // This function does not have a summary
197*b4e1e829SMehdi Amini   return selectCallee(Index, CalleeSummaryList->second, Threshold);
19801e32130SMehdi Amini }
1997e88d0daSMehdi Amini 
200cb87494fSMehdi Amini /// Mark the global \p GUID as export by module \p ExportModulePath if found in
201cb87494fSMehdi Amini /// this module. If it is a GlobalVariable, we also mark any referenced global
202cb87494fSMehdi Amini /// in the current module as exported.
203cb87494fSMehdi Amini static void exportGlobalInModule(const ModuleSummaryIndex &Index,
204ad5741b0SMehdi Amini                                  StringRef ExportModulePath,
205cb87494fSMehdi Amini                                  GlobalValue::GUID GUID,
206cb87494fSMehdi Amini                                  FunctionImporter::ExportSetTy &ExportList) {
20728e457bcSTeresa Johnson   auto FindGlobalSummaryInModule =
20828e457bcSTeresa Johnson       [&](GlobalValue::GUID GUID) -> GlobalValueSummary *{
20928e457bcSTeresa Johnson         auto SummaryList = Index.findGlobalValueSummaryList(GUID);
21028e457bcSTeresa Johnson         if (SummaryList == Index.end())
21101e32130SMehdi Amini           // This global does not have a summary, it is not part of the ThinLTO
21201e32130SMehdi Amini           // process
213cb87494fSMehdi Amini           return nullptr;
21428e457bcSTeresa Johnson         auto SummaryIter = llvm::find_if(
21528e457bcSTeresa Johnson             SummaryList->second,
21628e457bcSTeresa Johnson             [&](const std::unique_ptr<GlobalValueSummary> &Summary) {
21701e32130SMehdi Amini               return Summary->modulePath() == ExportModulePath;
21801e32130SMehdi Amini             });
21928e457bcSTeresa Johnson         if (SummaryIter == SummaryList->second.end())
220cb87494fSMehdi Amini           return nullptr;
22128e457bcSTeresa Johnson         return SummaryIter->get();
222cb87494fSMehdi Amini       };
223cb87494fSMehdi Amini 
22428e457bcSTeresa Johnson   auto *Summary = FindGlobalSummaryInModule(GUID);
22528e457bcSTeresa Johnson   if (!Summary)
226cb87494fSMehdi Amini     return;
227cb87494fSMehdi Amini   // We found it in the current module, mark as exported
228cb87494fSMehdi Amini   ExportList.insert(GUID);
229cb87494fSMehdi Amini 
230cb87494fSMehdi Amini   auto GVS = dyn_cast<GlobalVarSummary>(Summary);
231cb87494fSMehdi Amini   if (!GVS)
232cb87494fSMehdi Amini     return;
233cb87494fSMehdi Amini   // FunctionImportGlobalProcessing::doPromoteLocalToGlobal() will always
234cb87494fSMehdi Amini   // trigger importing  the initializer for `constant unnamed addr` globals that
235cb87494fSMehdi Amini   // are referenced. We conservatively export all the referenced symbols for
236cb87494fSMehdi Amini   // every global to workaround this, so that the ExportList is accurate.
237cb87494fSMehdi Amini   // FIXME: with a "isConstant" flag in the summary we could be more targetted.
238cb87494fSMehdi Amini   for (auto &Ref : GVS->refs()) {
239cb87494fSMehdi Amini     auto GUID = Ref.getGUID();
24028e457bcSTeresa Johnson     auto *RefSummary = FindGlobalSummaryInModule(GUID);
24128e457bcSTeresa Johnson     if (RefSummary)
242cb87494fSMehdi Amini       // Found a ref in the current module, mark it as exported
243cb87494fSMehdi Amini       ExportList.insert(GUID);
244cb87494fSMehdi Amini   }
24501e32130SMehdi Amini }
2467e88d0daSMehdi Amini 
24701e32130SMehdi Amini using EdgeInfo = std::pair<const FunctionSummary *, unsigned /* Threshold */>;
24801e32130SMehdi Amini 
24901e32130SMehdi Amini /// Compute the list of functions to import for a given caller. Mark these
25001e32130SMehdi Amini /// imported functions and the symbols they reference in their source module as
25101e32130SMehdi Amini /// exported from their source module.
25201e32130SMehdi Amini static void computeImportForFunction(
2533255eec1STeresa Johnson     const FunctionSummary &Summary, const ModuleSummaryIndex &Index,
254c851d216STeresa Johnson     unsigned Threshold, const GVSummaryMapTy &DefinedGVSummaries,
25501e32130SMehdi Amini     SmallVectorImpl<EdgeInfo> &Worklist,
25601e32130SMehdi Amini     FunctionImporter::ImportMapTy &ImportsForModule,
257c86af334STeresa Johnson     StringMap<FunctionImporter::ExportSetTy> *ExportLists = nullptr) {
25801e32130SMehdi Amini   for (auto &Edge : Summary.calls()) {
2592d5487cfSTeresa Johnson     auto GUID = Edge.first.getGUID();
26001e32130SMehdi Amini     DEBUG(dbgs() << " edge -> " << GUID << " Threshold:" << Threshold << "\n");
26101e32130SMehdi Amini 
2621aafabf7SMehdi Amini     if (DefinedGVSummaries.count(GUID)) {
26301e32130SMehdi Amini       DEBUG(dbgs() << "ignored! Target already in destination module.\n");
2647e88d0daSMehdi Amini       continue;
265d450da32STeresa Johnson     }
26640641748SMehdi Amini 
26701e32130SMehdi Amini     auto *CalleeSummary = selectCallee(GUID, Threshold, Index);
26801e32130SMehdi Amini     if (!CalleeSummary) {
26901e32130SMehdi Amini       DEBUG(dbgs() << "ignored! No qualifying callee with summary found.\n");
2707e88d0daSMehdi Amini       continue;
2717e88d0daSMehdi Amini     }
2722d28f7aaSMehdi Amini     // "Resolve" the summary, traversing alias,
2732d28f7aaSMehdi Amini     const FunctionSummary *ResolvedCalleeSummary;
2746968ef77SMehdi Amini     if (isa<AliasSummary>(CalleeSummary)) {
2752d28f7aaSMehdi Amini       ResolvedCalleeSummary = cast<FunctionSummary>(
2762d28f7aaSMehdi Amini           &cast<AliasSummary>(CalleeSummary)->getAliasee());
2772c719cc1SMehdi Amini       assert(
2782c719cc1SMehdi Amini           GlobalValue::isLinkOnceODRLinkage(ResolvedCalleeSummary->linkage()) &&
2792c719cc1SMehdi Amini           "Unexpected alias to a non-linkonceODR in import list");
2806968ef77SMehdi Amini     } else
2812d28f7aaSMehdi Amini       ResolvedCalleeSummary = cast<FunctionSummary>(CalleeSummary);
2822d28f7aaSMehdi Amini 
2832d28f7aaSMehdi Amini     assert(ResolvedCalleeSummary->instCount() <= Threshold &&
28401e32130SMehdi Amini            "selectCallee() didn't honor the threshold");
28501e32130SMehdi Amini 
2862d28f7aaSMehdi Amini     auto ExportModulePath = ResolvedCalleeSummary->modulePath();
2872d28f7aaSMehdi Amini     auto &ProcessedThreshold = ImportsForModule[ExportModulePath][GUID];
28801e32130SMehdi Amini     /// Since the traversal of the call graph is DFS, we can revisit a function
28901e32130SMehdi Amini     /// a second time with a higher threshold. In this case, it is added back to
29001e32130SMehdi Amini     /// the worklist with the new threshold.
29101e32130SMehdi Amini     if (ProcessedThreshold && ProcessedThreshold > Threshold) {
29201e32130SMehdi Amini       DEBUG(dbgs() << "ignored! Target was already seen with Threshold "
29301e32130SMehdi Amini                    << ProcessedThreshold << "\n");
29401e32130SMehdi Amini       continue;
29501e32130SMehdi Amini     }
29601e32130SMehdi Amini     // Mark this function as imported in this module, with the current Threshold
29701e32130SMehdi Amini     ProcessedThreshold = Threshold;
29801e32130SMehdi Amini 
29901e32130SMehdi Amini     // Make exports in the source module.
300c86af334STeresa Johnson     if (ExportLists) {
301ef7555fbSMehdi Amini       auto &ExportList = (*ExportLists)[ExportModulePath];
30201e32130SMehdi Amini       ExportList.insert(GUID);
303c86af334STeresa Johnson       // Mark all functions and globals referenced by this function as exported
304c86af334STeresa Johnson       // to the outside if they are defined in the same source module.
3052d28f7aaSMehdi Amini       for (auto &Edge : ResolvedCalleeSummary->calls()) {
3062d5487cfSTeresa Johnson         auto CalleeGUID = Edge.first.getGUID();
307cb87494fSMehdi Amini         exportGlobalInModule(Index, ExportModulePath, CalleeGUID, ExportList);
30801e32130SMehdi Amini       }
3092d28f7aaSMehdi Amini       for (auto &Ref : ResolvedCalleeSummary->refs()) {
3102d5487cfSTeresa Johnson         auto GUID = Ref.getGUID();
311cb87494fSMehdi Amini         exportGlobalInModule(Index, ExportModulePath, GUID, ExportList);
3127e88d0daSMehdi Amini       }
313c86af334STeresa Johnson     }
3147e88d0daSMehdi Amini 
31501e32130SMehdi Amini     // Insert the newly imported function to the worklist.
3162d28f7aaSMehdi Amini     Worklist.push_back(std::make_pair(ResolvedCalleeSummary, Threshold));
317d450da32STeresa Johnson   }
318d450da32STeresa Johnson }
319d450da32STeresa Johnson 
32001e32130SMehdi Amini /// Given the list of globals defined in a module, compute the list of imports
32101e32130SMehdi Amini /// as well as the list of "exports", i.e. the list of symbols referenced from
32201e32130SMehdi Amini /// another module (that may require promotion).
32301e32130SMehdi Amini static void ComputeImportForModule(
324c851d216STeresa Johnson     const GVSummaryMapTy &DefinedGVSummaries, const ModuleSummaryIndex &Index,
32501e32130SMehdi Amini     FunctionImporter::ImportMapTy &ImportsForModule,
326c86af334STeresa Johnson     StringMap<FunctionImporter::ExportSetTy> *ExportLists = nullptr) {
32701e32130SMehdi Amini   // Worklist contains the list of function imported in this module, for which
32801e32130SMehdi Amini   // we will analyse the callees and may import further down the callgraph.
32901e32130SMehdi Amini   SmallVector<EdgeInfo, 128> Worklist;
33001e32130SMehdi Amini 
33101e32130SMehdi Amini   // Populate the worklist with the import for the functions in the current
33201e32130SMehdi Amini   // module
33328e457bcSTeresa Johnson   for (auto &GVSummary : DefinedGVSummaries) {
33428e457bcSTeresa Johnson     auto *Summary = GVSummary.second;
3352d28f7aaSMehdi Amini     if (auto *AS = dyn_cast<AliasSummary>(Summary))
3362d28f7aaSMehdi Amini       Summary = &AS->getAliasee();
3371aafabf7SMehdi Amini     auto *FuncSummary = dyn_cast<FunctionSummary>(Summary);
3381aafabf7SMehdi Amini     if (!FuncSummary)
3391aafabf7SMehdi Amini       // Skip import for global variables
3401aafabf7SMehdi Amini       continue;
34128e457bcSTeresa Johnson     DEBUG(dbgs() << "Initalize import for " << GVSummary.first << "\n");
3422d28f7aaSMehdi Amini     computeImportForFunction(*FuncSummary, Index, ImportInstrLimit,
3431aafabf7SMehdi Amini                              DefinedGVSummaries, Worklist, ImportsForModule,
34401e32130SMehdi Amini                              ExportLists);
34501e32130SMehdi Amini   }
34601e32130SMehdi Amini 
34742418abaSMehdi Amini   while (!Worklist.empty()) {
34801e32130SMehdi Amini     auto FuncInfo = Worklist.pop_back_val();
34901e32130SMehdi Amini     auto *Summary = FuncInfo.first;
35001e32130SMehdi Amini     auto Threshold = FuncInfo.second;
35142418abaSMehdi Amini 
3527e88d0daSMehdi Amini     // Process the newly imported functions and add callees to the worklist.
35340641748SMehdi Amini     // Adjust the threshold
35440641748SMehdi Amini     Threshold = Threshold * ImportInstrFactor;
35501e32130SMehdi Amini 
3561aafabf7SMehdi Amini     computeImportForFunction(*Summary, Index, Threshold, DefinedGVSummaries,
3573255eec1STeresa Johnson                              Worklist, ImportsForModule, ExportLists);
358c8c55170SMehdi Amini   }
35942418abaSMehdi Amini }
360ffe2e4aaSMehdi Amini 
36101e32130SMehdi Amini } // anonymous namespace
36201e32130SMehdi Amini 
363c86af334STeresa Johnson /// Compute all the import and export for every module using the Index.
36401e32130SMehdi Amini void llvm::ComputeCrossModuleImport(
36501e32130SMehdi Amini     const ModuleSummaryIndex &Index,
366c851d216STeresa Johnson     const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
36701e32130SMehdi Amini     StringMap<FunctionImporter::ImportMapTy> &ImportLists,
36801e32130SMehdi Amini     StringMap<FunctionImporter::ExportSetTy> &ExportLists) {
36901e32130SMehdi Amini   // For each module that has function defined, compute the import/export lists.
3701aafabf7SMehdi Amini   for (auto &DefinedGVSummaries : ModuleToDefinedGVSummaries) {
3711aafabf7SMehdi Amini     auto &ImportsForModule = ImportLists[DefinedGVSummaries.first()];
3721aafabf7SMehdi Amini     DEBUG(dbgs() << "Computing import for Module '"
3731aafabf7SMehdi Amini                  << DefinedGVSummaries.first() << "'\n");
3741aafabf7SMehdi Amini     ComputeImportForModule(DefinedGVSummaries.second, Index, ImportsForModule,
375c86af334STeresa Johnson                            &ExportLists);
37601e32130SMehdi Amini   }
37701e32130SMehdi Amini 
37801e32130SMehdi Amini #ifndef NDEBUG
37901e32130SMehdi Amini   DEBUG(dbgs() << "Import/Export lists for " << ImportLists.size()
38001e32130SMehdi Amini                << " modules:\n");
38101e32130SMehdi Amini   for (auto &ModuleImports : ImportLists) {
38201e32130SMehdi Amini     auto ModName = ModuleImports.first();
38301e32130SMehdi Amini     auto &Exports = ExportLists[ModName];
38401e32130SMehdi Amini     DEBUG(dbgs() << "* Module " << ModName << " exports " << Exports.size()
38501e32130SMehdi Amini                  << " functions. Imports from " << ModuleImports.second.size()
38601e32130SMehdi Amini                  << " modules.\n");
38701e32130SMehdi Amini     for (auto &Src : ModuleImports.second) {
38801e32130SMehdi Amini       auto SrcModName = Src.first();
38901e32130SMehdi Amini       DEBUG(dbgs() << " - " << Src.second.size() << " functions imported from "
39001e32130SMehdi Amini                    << SrcModName << "\n");
39101e32130SMehdi Amini     }
39201e32130SMehdi Amini   }
39301e32130SMehdi Amini #endif
39401e32130SMehdi Amini }
39501e32130SMehdi Amini 
396c86af334STeresa Johnson /// Compute all the imports for the given module in the Index.
397c86af334STeresa Johnson void llvm::ComputeCrossModuleImportForModule(
398c86af334STeresa Johnson     StringRef ModulePath, const ModuleSummaryIndex &Index,
399c86af334STeresa Johnson     FunctionImporter::ImportMapTy &ImportList) {
400c86af334STeresa Johnson 
401c86af334STeresa Johnson   // Collect the list of functions this module defines.
402c86af334STeresa Johnson   // GUID -> Summary
403c851d216STeresa Johnson   GVSummaryMapTy FunctionSummaryMap;
40428e457bcSTeresa Johnson   Index.collectDefinedFunctionsForModule(ModulePath, FunctionSummaryMap);
405c86af334STeresa Johnson 
406c86af334STeresa Johnson   // Compute the import list for this module.
407c86af334STeresa Johnson   DEBUG(dbgs() << "Computing import for Module '" << ModulePath << "'\n");
40828e457bcSTeresa Johnson   ComputeImportForModule(FunctionSummaryMap, Index, ImportList);
409c86af334STeresa Johnson 
410c86af334STeresa Johnson #ifndef NDEBUG
411c86af334STeresa Johnson   DEBUG(dbgs() << "* Module " << ModulePath << " imports from "
412c86af334STeresa Johnson                << ImportList.size() << " modules.\n");
413c86af334STeresa Johnson   for (auto &Src : ImportList) {
414c86af334STeresa Johnson     auto SrcModName = Src.first();
415c86af334STeresa Johnson     DEBUG(dbgs() << " - " << Src.second.size() << " functions imported from "
416c86af334STeresa Johnson                  << SrcModName << "\n");
417c86af334STeresa Johnson   }
418c86af334STeresa Johnson #endif
419c86af334STeresa Johnson }
420c86af334STeresa Johnson 
421c8c55170SMehdi Amini // Automatically import functions in Module \p DestModule based on the summaries
422c8c55170SMehdi Amini // index.
423c8c55170SMehdi Amini //
42401e32130SMehdi Amini bool FunctionImporter::importFunctions(
425bda3c97cSMehdi Amini     Module &DestModule, const FunctionImporter::ImportMapTy &ImportList,
426bda3c97cSMehdi Amini     bool ForceImportReferencedDiscardableSymbols) {
4275411d051SMehdi Amini   DEBUG(dbgs() << "Starting import for Module "
428311fef6eSMehdi Amini                << DestModule.getModuleIdentifier() << "\n");
429c8c55170SMehdi Amini   unsigned ImportedCount = 0;
430c8c55170SMehdi Amini 
431c8c55170SMehdi Amini   // Linker that will be used for importing function
4329d2bfc48SRafael Espindola   Linker TheLinker(DestModule);
4337e88d0daSMehdi Amini   // Do the actual import of functions now, one Module at a time
43401e32130SMehdi Amini   std::set<StringRef> ModuleNameOrderedList;
43501e32130SMehdi Amini   for (auto &FunctionsToImportPerModule : ImportList) {
43601e32130SMehdi Amini     ModuleNameOrderedList.insert(FunctionsToImportPerModule.first());
43701e32130SMehdi Amini   }
43801e32130SMehdi Amini   for (auto &Name : ModuleNameOrderedList) {
4397e88d0daSMehdi Amini     // Get the module for the import
44001e32130SMehdi Amini     const auto &FunctionsToImportPerModule = ImportList.find(Name);
44101e32130SMehdi Amini     assert(FunctionsToImportPerModule != ImportList.end());
44201e32130SMehdi Amini     std::unique_ptr<Module> SrcModule = ModuleLoader(Name);
4437e88d0daSMehdi Amini     assert(&DestModule.getContext() == &SrcModule->getContext() &&
4447e88d0daSMehdi Amini            "Context mismatch");
4457e88d0daSMehdi Amini 
4466cba37ceSTeresa Johnson     // If modules were created with lazy metadata loading, materialize it
4476cba37ceSTeresa Johnson     // now, before linking it (otherwise this will be a noop).
4486cba37ceSTeresa Johnson     SrcModule->materializeMetadata();
4496cba37ceSTeresa Johnson     UpgradeDebugInfo(*SrcModule);
450e5a61917STeresa Johnson 
45101e32130SMehdi Amini     auto &ImportGUIDs = FunctionsToImportPerModule->second;
45201e32130SMehdi Amini     // Find the globals to import
45301e32130SMehdi Amini     DenseSet<const GlobalValue *> GlobalsToImport;
45401e32130SMehdi Amini     for (auto &GV : *SrcModule) {
4550beb858eSTeresa Johnson       if (!GV.hasName())
4560beb858eSTeresa Johnson         continue;
4570beb858eSTeresa Johnson       auto GUID = GV.getGUID();
4580beb858eSTeresa Johnson       auto Import = ImportGUIDs.count(GUID);
459aeb1e59bSMehdi Amini       DEBUG(dbgs() << (Import ? "Is" : "Not") << " importing function " << GUID
460aeb1e59bSMehdi Amini                    << " " << GV.getName() << " from "
461aeb1e59bSMehdi Amini                    << SrcModule->getSourceFileName() << "\n");
4620beb858eSTeresa Johnson       if (Import) {
46301e32130SMehdi Amini         GV.materialize();
46401e32130SMehdi Amini         GlobalsToImport.insert(&GV);
46501e32130SMehdi Amini       }
46601e32130SMehdi Amini     }
4672d28f7aaSMehdi Amini     for (auto &GV : SrcModule->globals()) {
4682d28f7aaSMehdi Amini       if (!GV.hasName())
4692d28f7aaSMehdi Amini         continue;
4702d28f7aaSMehdi Amini       auto GUID = GV.getGUID();
4712d28f7aaSMehdi Amini       auto Import = ImportGUIDs.count(GUID);
472aeb1e59bSMehdi Amini       DEBUG(dbgs() << (Import ? "Is" : "Not") << " importing global " << GUID
473aeb1e59bSMehdi Amini                    << " " << GV.getName() << " from "
474aeb1e59bSMehdi Amini                    << SrcModule->getSourceFileName() << "\n");
4752d28f7aaSMehdi Amini       if (Import) {
4762d28f7aaSMehdi Amini         GV.materialize();
4772d28f7aaSMehdi Amini         GlobalsToImport.insert(&GV);
4782d28f7aaSMehdi Amini       }
4792d28f7aaSMehdi Amini     }
48001e32130SMehdi Amini     for (auto &GV : SrcModule->aliases()) {
48101e32130SMehdi Amini       if (!GV.hasName())
48201e32130SMehdi Amini         continue;
48301e32130SMehdi Amini       auto GUID = GV.getGUID();
4840beb858eSTeresa Johnson       auto Import = ImportGUIDs.count(GUID);
485aeb1e59bSMehdi Amini       DEBUG(dbgs() << (Import ? "Is" : "Not") << " importing alias " << GUID
486aeb1e59bSMehdi Amini                    << " " << GV.getName() << " from "
487aeb1e59bSMehdi Amini                    << SrcModule->getSourceFileName() << "\n");
4880beb858eSTeresa Johnson       if (Import) {
48901e32130SMehdi Amini         // Alias can't point to "available_externally". However when we import
4909aae395fSTeresa Johnson         // linkOnceODR the linkage does not change. So we import the alias
4916968ef77SMehdi Amini         // and aliasee only in this case. This has been handled by
4926968ef77SMehdi Amini         // computeImportForFunction()
4932d28f7aaSMehdi Amini         GlobalObject *GO = GV.getBaseObject();
4946968ef77SMehdi Amini         assert(GO->hasLinkOnceODRLinkage() &&
4956968ef77SMehdi Amini                "Unexpected alias to a non-linkonceODR in import list");
4962d28f7aaSMehdi Amini #ifndef NDEBUG
4972d28f7aaSMehdi Amini         if (!GlobalsToImport.count(GO))
4982d28f7aaSMehdi Amini           DEBUG(dbgs() << " alias triggers importing aliasee " << GO->getGUID()
4992d28f7aaSMehdi Amini                        << " " << GO->getName() << " from "
5002d28f7aaSMehdi Amini                        << SrcModule->getSourceFileName() << "\n");
5012d28f7aaSMehdi Amini #endif
5022d28f7aaSMehdi Amini         GO->materialize();
50301e32130SMehdi Amini         GlobalsToImport.insert(GO);
50401e32130SMehdi Amini         GV.materialize();
50501e32130SMehdi Amini         GlobalsToImport.insert(&GV);
50601e32130SMehdi Amini       }
50701e32130SMehdi Amini     }
50801e32130SMehdi Amini 
5097e88d0daSMehdi Amini     // Link in the specified functions.
51001e32130SMehdi Amini     if (renameModuleForThinLTO(*SrcModule, Index, &GlobalsToImport))
5118d05185aSMehdi Amini       return true;
5128d05185aSMehdi Amini 
513d29478f7STeresa Johnson     if (PrintImports) {
514d29478f7STeresa Johnson       for (const auto *GV : GlobalsToImport)
515d29478f7STeresa Johnson         dbgs() << DestModule.getSourceFileName() << ": Import " << GV->getName()
516d29478f7STeresa Johnson                << " from " << SrcModule->getSourceFileName() << "\n";
517d29478f7STeresa Johnson     }
518d29478f7STeresa Johnson 
519bda3c97cSMehdi Amini     // Instruct the linker that the client will take care of linkonce resolution
520bda3c97cSMehdi Amini     unsigned Flags = Linker::Flags::None;
521bda3c97cSMehdi Amini     if (!ForceImportReferencedDiscardableSymbols)
522bda3c97cSMehdi Amini       Flags |= Linker::Flags::DontForceLinkLinkonceODR;
523bda3c97cSMehdi Amini 
524bda3c97cSMehdi Amini     if (TheLinker.linkInModule(std::move(SrcModule), Flags, &GlobalsToImport))
5257e88d0daSMehdi Amini       report_fatal_error("Function Import: link error");
5267e88d0daSMehdi Amini 
52701e32130SMehdi Amini     ImportedCount += GlobalsToImport.size();
5287e88d0daSMehdi Amini   }
529e5a61917STeresa Johnson 
530d29478f7STeresa Johnson   NumImported += ImportedCount;
531d29478f7STeresa Johnson 
5327e88d0daSMehdi Amini   DEBUG(dbgs() << "Imported " << ImportedCount << " functions for Module "
533c8c55170SMehdi Amini                << DestModule.getModuleIdentifier() << "\n");
534c8c55170SMehdi Amini   return ImportedCount;
53542418abaSMehdi Amini }
53642418abaSMehdi Amini 
53742418abaSMehdi Amini /// Summary file to use for function importing when using -function-import from
53842418abaSMehdi Amini /// the command line.
53942418abaSMehdi Amini static cl::opt<std::string>
54042418abaSMehdi Amini     SummaryFile("summary-file",
54142418abaSMehdi Amini                 cl::desc("The summary file to use for function importing."));
54242418abaSMehdi Amini 
54342418abaSMehdi Amini static void diagnosticHandler(const DiagnosticInfo &DI) {
54442418abaSMehdi Amini   raw_ostream &OS = errs();
54542418abaSMehdi Amini   DiagnosticPrinterRawOStream DP(OS);
54642418abaSMehdi Amini   DI.print(DP);
54742418abaSMehdi Amini   OS << '\n';
54842418abaSMehdi Amini }
54942418abaSMehdi Amini 
55026ab5772STeresa Johnson /// Parse the summary index out of an IR file and return the summary
55142418abaSMehdi Amini /// index object if found, or nullptr if not.
55226ab5772STeresa Johnson static std::unique_ptr<ModuleSummaryIndex>
55326ab5772STeresa Johnson getModuleSummaryIndexForFile(StringRef Path, std::string &Error,
55442418abaSMehdi Amini                              DiagnosticHandlerFunction DiagnosticHandler) {
55542418abaSMehdi Amini   std::unique_ptr<MemoryBuffer> Buffer;
55642418abaSMehdi Amini   ErrorOr<std::unique_ptr<MemoryBuffer>> BufferOrErr =
55742418abaSMehdi Amini       MemoryBuffer::getFile(Path);
55842418abaSMehdi Amini   if (std::error_code EC = BufferOrErr.getError()) {
55942418abaSMehdi Amini     Error = EC.message();
56042418abaSMehdi Amini     return nullptr;
56142418abaSMehdi Amini   }
56242418abaSMehdi Amini   Buffer = std::move(BufferOrErr.get());
56326ab5772STeresa Johnson   ErrorOr<std::unique_ptr<object::ModuleSummaryIndexObjectFile>> ObjOrErr =
56426ab5772STeresa Johnson       object::ModuleSummaryIndexObjectFile::create(Buffer->getMemBufferRef(),
56542418abaSMehdi Amini                                                    DiagnosticHandler);
56642418abaSMehdi Amini   if (std::error_code EC = ObjOrErr.getError()) {
56742418abaSMehdi Amini     Error = EC.message();
56842418abaSMehdi Amini     return nullptr;
56942418abaSMehdi Amini   }
57042418abaSMehdi Amini   return (*ObjOrErr)->takeIndex();
57142418abaSMehdi Amini }
57242418abaSMehdi Amini 
573fe2b5415SBenjamin Kramer namespace {
57442418abaSMehdi Amini /// Pass that performs cross-module function import provided a summary file.
57542418abaSMehdi Amini class FunctionImportPass : public ModulePass {
57626ab5772STeresa Johnson   /// Optional module summary index to use for importing, otherwise
5775fcbdb71STeresa Johnson   /// the summary-file option must be specified.
57826ab5772STeresa Johnson   const ModuleSummaryIndex *Index;
57942418abaSMehdi Amini 
58042418abaSMehdi Amini public:
58142418abaSMehdi Amini   /// Pass identification, replacement for typeid
58242418abaSMehdi Amini   static char ID;
58342418abaSMehdi Amini 
5845fcbdb71STeresa Johnson   /// Specify pass name for debug output
5852d28f7aaSMehdi Amini   const char *getPassName() const override { return "Function Importing"; }
5865fcbdb71STeresa Johnson 
58726ab5772STeresa Johnson   explicit FunctionImportPass(const ModuleSummaryIndex *Index = nullptr)
5885fcbdb71STeresa Johnson       : ModulePass(ID), Index(Index) {}
58942418abaSMehdi Amini 
59042418abaSMehdi Amini   bool runOnModule(Module &M) override {
591aa641a51SAndrew Kaylor     if (skipModule(M))
592aa641a51SAndrew Kaylor       return false;
593aa641a51SAndrew Kaylor 
5945fcbdb71STeresa Johnson     if (SummaryFile.empty() && !Index)
5955fcbdb71STeresa Johnson       report_fatal_error("error: -function-import requires -summary-file or "
5965fcbdb71STeresa Johnson                          "file from frontend\n");
59726ab5772STeresa Johnson     std::unique_ptr<ModuleSummaryIndex> IndexPtr;
5985fcbdb71STeresa Johnson     if (!SummaryFile.empty()) {
5995fcbdb71STeresa Johnson       if (Index)
6005fcbdb71STeresa Johnson         report_fatal_error("error: -summary-file and index from frontend\n");
60142418abaSMehdi Amini       std::string Error;
60226ab5772STeresa Johnson       IndexPtr =
60326ab5772STeresa Johnson           getModuleSummaryIndexForFile(SummaryFile, Error, diagnosticHandler);
6045fcbdb71STeresa Johnson       if (!IndexPtr) {
6055fcbdb71STeresa Johnson         errs() << "Error loading file '" << SummaryFile << "': " << Error
6065fcbdb71STeresa Johnson                << "\n";
60742418abaSMehdi Amini         return false;
60842418abaSMehdi Amini       }
6095fcbdb71STeresa Johnson       Index = IndexPtr.get();
6105fcbdb71STeresa Johnson     }
61142418abaSMehdi Amini 
612c86af334STeresa Johnson     // First step is collecting the import list.
613c86af334STeresa Johnson     FunctionImporter::ImportMapTy ImportList;
614c86af334STeresa Johnson     ComputeCrossModuleImportForModule(M.getModuleIdentifier(), *Index,
615c86af334STeresa Johnson                                       ImportList);
61601e32130SMehdi Amini 
61701e32130SMehdi Amini     // Next we need to promote to global scope and rename any local values that
6181b00f2d9STeresa Johnson     // are potentially exported to other modules.
61901e32130SMehdi Amini     if (renameModuleForThinLTO(M, *Index, nullptr)) {
6201b00f2d9STeresa Johnson       errs() << "Error renaming module\n";
6211b00f2d9STeresa Johnson       return false;
6221b00f2d9STeresa Johnson     }
6231b00f2d9STeresa Johnson 
62442418abaSMehdi Amini     // Perform the import now.
625d16c8065SMehdi Amini     auto ModuleLoader = [&M](StringRef Identifier) {
626d16c8065SMehdi Amini       return loadFile(Identifier, M.getContext());
627d16c8065SMehdi Amini     };
6289d2bfc48SRafael Espindola     FunctionImporter Importer(*Index, ModuleLoader);
629bda3c97cSMehdi Amini     return Importer.importFunctions(
630bda3c97cSMehdi Amini         M, ImportList, !DontForceImportReferencedDiscardableSymbols);
63142418abaSMehdi Amini   }
63242418abaSMehdi Amini };
633fe2b5415SBenjamin Kramer } // anonymous namespace
63442418abaSMehdi Amini 
63542418abaSMehdi Amini char FunctionImportPass::ID = 0;
63642418abaSMehdi Amini INITIALIZE_PASS_BEGIN(FunctionImportPass, "function-import",
63742418abaSMehdi Amini                       "Summary Based Function Import", false, false)
63842418abaSMehdi Amini INITIALIZE_PASS_END(FunctionImportPass, "function-import",
63942418abaSMehdi Amini                     "Summary Based Function Import", false, false)
64042418abaSMehdi Amini 
64142418abaSMehdi Amini namespace llvm {
64226ab5772STeresa Johnson Pass *createFunctionImportPass(const ModuleSummaryIndex *Index = nullptr) {
6435fcbdb71STeresa Johnson   return new FunctionImportPass(Index);
6445fcbdb71STeresa Johnson }
64542418abaSMehdi Amini }
646