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