2140 lines · cpp
1//===- FunctionImport.cpp - ThinLTO Summary-based Function Import ---------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements Function import based on summaries.10//11//===----------------------------------------------------------------------===//12 13#include "llvm/Transforms/IPO/FunctionImport.h"14#include "llvm/ADT/ArrayRef.h"15#include "llvm/ADT/STLExtras.h"16#include "llvm/ADT/SetVector.h"17#include "llvm/ADT/SmallVector.h"18#include "llvm/ADT/Statistic.h"19#include "llvm/ADT/StringRef.h"20#include "llvm/Bitcode/BitcodeReader.h"21#include "llvm/IR/AutoUpgrade.h"22#include "llvm/IR/Function.h"23#include "llvm/IR/GlobalAlias.h"24#include "llvm/IR/GlobalObject.h"25#include "llvm/IR/GlobalValue.h"26#include "llvm/IR/GlobalVariable.h"27#include "llvm/IR/Metadata.h"28#include "llvm/IR/Module.h"29#include "llvm/IR/ModuleSummaryIndex.h"30#include "llvm/IRReader/IRReader.h"31#include "llvm/Linker/IRMover.h"32#include "llvm/ProfileData/PGOCtxProfReader.h"33#include "llvm/Support/Casting.h"34#include "llvm/Support/CommandLine.h"35#include "llvm/Support/Debug.h"36#include "llvm/Support/Errc.h"37#include "llvm/Support/Error.h"38#include "llvm/Support/ErrorHandling.h"39#include "llvm/Support/FileSystem.h"40#include "llvm/Support/JSON.h"41#include "llvm/Support/Path.h"42#include "llvm/Support/SourceMgr.h"43#include "llvm/Support/TimeProfiler.h"44#include "llvm/Support/raw_ostream.h"45#include "llvm/Transforms/IPO/Internalize.h"46#include "llvm/Transforms/Utils/Cloning.h"47#include "llvm/Transforms/Utils/FunctionImportUtils.h"48#include "llvm/Transforms/Utils/ValueMapper.h"49#include <cassert>50#include <memory>51#include <string>52#include <system_error>53#include <tuple>54#include <utility>55 56using namespace llvm;57 58#define DEBUG_TYPE "function-import"59 60STATISTIC(NumImportedFunctionsThinLink,61 "Number of functions thin link decided to import");62STATISTIC(NumImportedHotFunctionsThinLink,63 "Number of hot functions thin link decided to import");64STATISTIC(NumImportedCriticalFunctionsThinLink,65 "Number of critical functions thin link decided to import");66STATISTIC(NumImportedGlobalVarsThinLink,67 "Number of global variables thin link decided to import");68STATISTIC(NumImportedFunctions, "Number of functions imported in backend");69STATISTIC(NumImportedGlobalVars,70 "Number of global variables imported in backend");71STATISTIC(NumImportedModules, "Number of modules imported from");72STATISTIC(NumDeadSymbols, "Number of dead stripped symbols in index");73STATISTIC(NumLiveSymbols, "Number of live symbols in index");74 75namespace llvm {76cl::opt<bool>77 ForceImportAll("force-import-all", cl::init(false), cl::Hidden,78 cl::desc("Import functions with noinline attribute"));79 80/// Limit on instruction count of imported functions.81static cl::opt<unsigned> ImportInstrLimit(82 "import-instr-limit", cl::init(100), cl::Hidden, cl::value_desc("N"),83 cl::desc("Only import functions with less than N instructions"));84 85static cl::opt<int> ImportCutoff(86 "import-cutoff", cl::init(-1), cl::Hidden, cl::value_desc("N"),87 cl::desc("Only import first N functions if N>=0 (default -1)"));88 89static cl::opt<float>90 ImportInstrFactor("import-instr-evolution-factor", cl::init(0.7),91 cl::Hidden, cl::value_desc("x"),92 cl::desc("As we import functions, multiply the "93 "`import-instr-limit` threshold by this factor "94 "before processing newly imported functions"));95 96static cl::opt<float> ImportHotInstrFactor(97 "import-hot-evolution-factor", cl::init(1.0), cl::Hidden,98 cl::value_desc("x"),99 cl::desc("As we import functions called from hot callsite, multiply the "100 "`import-instr-limit` threshold by this factor "101 "before processing newly imported functions"));102 103static cl::opt<float> ImportHotMultiplier(104 "import-hot-multiplier", cl::init(10.0), cl::Hidden, cl::value_desc("x"),105 cl::desc("Multiply the `import-instr-limit` threshold for hot callsites"));106 107static cl::opt<float> ImportCriticalMultiplier(108 "import-critical-multiplier", cl::init(100.0), cl::Hidden,109 cl::value_desc("x"),110 cl::desc(111 "Multiply the `import-instr-limit` threshold for critical callsites"));112 113// FIXME: This multiplier was not really tuned up.114static cl::opt<float> ImportColdMultiplier(115 "import-cold-multiplier", cl::init(0), cl::Hidden, cl::value_desc("N"),116 cl::desc("Multiply the `import-instr-limit` threshold for cold callsites"));117 118static cl::opt<bool> PrintImports("print-imports", cl::init(false), cl::Hidden,119 cl::desc("Print imported functions"));120 121static cl::opt<bool> PrintImportFailures(122 "print-import-failures", cl::init(false), cl::Hidden,123 cl::desc("Print information for functions rejected for importing"));124 125static cl::opt<bool> ComputeDead("compute-dead", cl::init(true), cl::Hidden,126 cl::desc("Compute dead symbols"));127 128static cl::opt<bool> EnableImportMetadata(129 "enable-import-metadata", cl::init(false), cl::Hidden,130 cl::desc("Enable import metadata like 'thinlto_src_module' and "131 "'thinlto_src_file'"));132 133/// Summary file to use for function importing when using -function-import from134/// the command line.135static cl::opt<std::string>136 SummaryFile("summary-file",137 cl::desc("The summary file to use for function importing."));138 139/// Used when testing importing from distributed indexes via opt140// -function-import.141static cl::opt<bool>142 ImportAllIndex("import-all-index",143 cl::desc("Import all external functions in index."));144 145/// This is a test-only option.146/// If this option is enabled, the ThinLTO indexing step will import each147/// function declaration as a fallback. In a real build this may increase ram148/// usage of the indexing step unnecessarily.149/// TODO: Implement selective import (based on combined summary analysis) to150/// ensure the imported function has a use case in the postlink pipeline.151static cl::opt<bool> ImportDeclaration(152 "import-declaration", cl::init(false), cl::Hidden,153 cl::desc("If true, import function declaration as fallback if the function "154 "definition is not imported."));155 156/// Pass a workload description file - an example of workload would be the157/// functions executed to satisfy a RPC request. A workload is defined by a root158/// function and the list of functions that are (frequently) needed to satisfy159/// it. The module that defines the root will have all those functions imported.160/// The file contains a JSON dictionary. The keys are root functions, the values161/// are lists of functions to import in the module defining the root. It is162/// assumed -funique-internal-linkage-names was used, thus ensuring function163/// names are unique even for local linkage ones.164static cl::opt<std::string> WorkloadDefinitions(165 "thinlto-workload-def",166 cl::desc("Pass a workload definition. This is a file containing a JSON "167 "dictionary. The keys are root functions, the values are lists of "168 "functions to import in the module defining the root. It is "169 "assumed -funique-internal-linkage-names was used, to ensure "170 "local linkage functions have unique names. For example: \n"171 "{\n"172 " \"rootFunction_1\": [\"function_to_import_1\", "173 "\"function_to_import_2\"], \n"174 " \"rootFunction_2\": [\"function_to_import_3\", "175 "\"function_to_import_4\"] \n"176 "}"),177 cl::Hidden);178 179extern cl::opt<std::string> UseCtxProfile;180 181static cl::opt<bool> CtxprofMoveRootsToOwnModule(182 "thinlto-move-ctxprof-trees",183 cl::desc("Move contextual profiling roots and the graphs under them in "184 "their own module."),185 cl::Hidden, cl::init(false));186 187extern cl::list<GlobalValue::GUID> MoveSymbolGUID;188 189extern cl::opt<bool> EnableMemProfContextDisambiguation;190} // end namespace llvm191 192// Load lazily a module from \p FileName in \p Context.193static std::unique_ptr<Module> loadFile(const std::string &FileName,194 LLVMContext &Context) {195 SMDiagnostic Err;196 LLVM_DEBUG(dbgs() << "Loading '" << FileName << "'\n");197 // Metadata isn't loaded until functions are imported, to minimize198 // the memory overhead.199 std::unique_ptr<Module> Result =200 getLazyIRFileModule(FileName, Err, Context,201 /* ShouldLazyLoadMetadata = */ true);202 if (!Result) {203 Err.print("function-import", errs());204 report_fatal_error("Abort");205 }206 207 return Result;208}209 210static bool shouldSkipLocalInAnotherModule(const GlobalValueSummary *RefSummary,211 size_t NumDefs,212 StringRef ImporterModule) {213 // We can import a local when there is one definition.214 if (NumDefs == 1)215 return false;216 // In other cases, make sure we import the copy in the caller's module if the217 // referenced value has local linkage. The only time a local variable can218 // share an entry in the index is if there is a local with the same name in219 // another module that had the same source file name (in a different220 // directory), where each was compiled in their own directory so there was not221 // distinguishing path.222 return GlobalValue::isLocalLinkage(RefSummary->linkage()) &&223 RefSummary->modulePath() != ImporterModule;224}225 226/// Given a list of possible callee implementation for a call site, qualify the227/// legality of importing each. The return is a range of pairs. Each pair228/// corresponds to a candidate. The first value is the ImportFailureReason for229/// that candidate, the second is the candidate.230static auto qualifyCalleeCandidates(231 const ModuleSummaryIndex &Index,232 ArrayRef<std::unique_ptr<GlobalValueSummary>> CalleeSummaryList,233 StringRef CallerModulePath) {234 return llvm::map_range(235 CalleeSummaryList,236 [&Index, CalleeSummaryList,237 CallerModulePath](const std::unique_ptr<GlobalValueSummary> &SummaryPtr)238 -> std::pair<FunctionImporter::ImportFailureReason,239 const GlobalValueSummary *> {240 auto *GVSummary = SummaryPtr.get();241 if (!Index.isGlobalValueLive(GVSummary))242 return {FunctionImporter::ImportFailureReason::NotLive, GVSummary};243 244 if (GlobalValue::isInterposableLinkage(GVSummary->linkage()))245 return {FunctionImporter::ImportFailureReason::InterposableLinkage,246 GVSummary};247 248 auto *Summary = dyn_cast<FunctionSummary>(GVSummary->getBaseObject());249 250 // Ignore any callees that aren't actually functions. This could happen251 // in the case of GUID hash collisions. It could also happen in theory252 // for SamplePGO profiles collected on old versions of the code after253 // renaming, since we synthesize edges to any inlined callees appearing254 // in the profile.255 if (!Summary)256 return {FunctionImporter::ImportFailureReason::GlobalVar, GVSummary};257 258 // If this is a local function, make sure we import the copy in the259 // caller's module. The only time a local function can share an entry in260 // the index is if there is a local with the same name in another module261 // that had the same source file name (in a different directory), where262 // each was compiled in their own directory so there was not263 // distinguishing path.264 // If the local function is from another module, it must be a reference265 // due to indirect call profile data since a function pointer can point266 // to a local in another module. Do the import from another module if267 // there is only one entry in the list or when all files in the program268 // are compiled with full path - in both cases the local function has269 // unique PGO name and GUID.270 if (shouldSkipLocalInAnotherModule(Summary, CalleeSummaryList.size(),271 CallerModulePath))272 return {273 FunctionImporter::ImportFailureReason::LocalLinkageNotInModule,274 GVSummary};275 276 // Skip if it isn't legal to import (e.g. may reference unpromotable277 // locals).278 if (Summary->notEligibleToImport())279 return {FunctionImporter::ImportFailureReason::NotEligible,280 GVSummary};281 282 return {FunctionImporter::ImportFailureReason::None, GVSummary};283 });284}285 286/// Given a list of possible callee implementation for a call site, select one287/// that fits the \p Threshold for function definition import. If none are288/// found, the Reason will give the last reason for the failure (last, in the289/// order of CalleeSummaryList entries). While looking for a callee definition,290/// sets \p TooLargeOrNoInlineSummary to the last seen too-large or noinline291/// candidate; other modules may want to know the function summary or292/// declaration even if a definition is not needed.293///294/// FIXME: select "best" instead of first that fits. But what is "best"?295/// - The smallest: more likely to be inlined.296/// - The one with the least outgoing edges (already well optimized).297/// - One from a module already being imported from in order to reduce the298/// number of source modules parsed/linked.299/// - One that has PGO data attached.300/// - [insert you fancy metric here]301static const GlobalValueSummary *302selectCallee(const ModuleSummaryIndex &Index,303 ArrayRef<std::unique_ptr<GlobalValueSummary>> CalleeSummaryList,304 unsigned Threshold, StringRef CallerModulePath,305 const GlobalValueSummary *&TooLargeOrNoInlineSummary,306 FunctionImporter::ImportFailureReason &Reason) {307 // Records the last summary with reason noinline or too-large.308 TooLargeOrNoInlineSummary = nullptr;309 auto QualifiedCandidates =310 qualifyCalleeCandidates(Index, CalleeSummaryList, CallerModulePath);311 for (auto QualifiedValue : QualifiedCandidates) {312 Reason = QualifiedValue.first;313 // Skip a summary if its import is not (proved to be) legal.314 if (Reason != FunctionImporter::ImportFailureReason::None)315 continue;316 auto *Summary =317 cast<FunctionSummary>(QualifiedValue.second->getBaseObject());318 319 // Don't bother importing the definition if the chance of inlining it is320 // not high enough (except under `--force-import-all`).321 if ((Summary->instCount() > Threshold) && !Summary->fflags().AlwaysInline &&322 !ForceImportAll) {323 TooLargeOrNoInlineSummary = Summary;324 Reason = FunctionImporter::ImportFailureReason::TooLarge;325 continue;326 }327 328 // Don't bother importing the definition if we can't inline it anyway.329 if (Summary->fflags().NoInline && !ForceImportAll) {330 TooLargeOrNoInlineSummary = Summary;331 Reason = FunctionImporter::ImportFailureReason::NoInline;332 continue;333 }334 335 return Summary;336 }337 return nullptr;338}339 340namespace {341 342using EdgeInfo = std::tuple<const FunctionSummary *, unsigned /* Threshold */>;343 344} // anonymous namespace345 346FunctionImporter::ImportMapTy::AddDefinitionStatus347FunctionImporter::ImportMapTy::addDefinition(StringRef FromModule,348 GlobalValue::GUID GUID) {349 auto [Def, Decl] = IDs.createImportIDs(FromModule, GUID);350 if (!Imports.insert(Def).second)351 // Already there.352 return AddDefinitionStatus::NoChange;353 354 // Remove Decl in case it's there. Note that a definition takes precedence355 // over a declaration for a given GUID.356 return Imports.erase(Decl) ? AddDefinitionStatus::ChangedToDefinition357 : AddDefinitionStatus::Inserted;358}359 360void FunctionImporter::ImportMapTy::maybeAddDeclaration(361 StringRef FromModule, GlobalValue::GUID GUID) {362 auto [Def, Decl] = IDs.createImportIDs(FromModule, GUID);363 // Insert Decl only if Def is not present. Note that a definition takes364 // precedence over a declaration for a given GUID.365 if (!Imports.contains(Def))366 Imports.insert(Decl);367}368 369SmallVector<StringRef, 0>370FunctionImporter::ImportMapTy::getSourceModules() const {371 SetVector<StringRef> ModuleSet;372 for (const auto &[SrcMod, GUID, ImportType] : *this)373 ModuleSet.insert(SrcMod);374 SmallVector<StringRef, 0> Modules = ModuleSet.takeVector();375 llvm::sort(Modules);376 return Modules;377}378 379std::optional<GlobalValueSummary::ImportKind>380FunctionImporter::ImportMapTy::getImportType(StringRef FromModule,381 GlobalValue::GUID GUID) const {382 if (auto IDPair = IDs.getImportIDs(FromModule, GUID)) {383 auto [Def, Decl] = *IDPair;384 if (Imports.contains(Def))385 return GlobalValueSummary::Definition;386 if (Imports.contains(Decl))387 return GlobalValueSummary::Declaration;388 }389 return std::nullopt;390}391 392/// Import globals referenced by a function or other globals that are being393/// imported, if importing such global is possible.394class GlobalsImporter final {395 const ModuleSummaryIndex &Index;396 const GVSummaryMapTy &DefinedGVSummaries;397 function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>398 IsPrevailing;399 FunctionImporter::ImportMapTy &ImportList;400 DenseMap<StringRef, FunctionImporter::ExportSetTy> *const ExportLists;401 402 bool shouldImportGlobal(const ValueInfo &VI) {403 const auto &GVS = DefinedGVSummaries.find(VI.getGUID());404 if (GVS == DefinedGVSummaries.end())405 return true;406 // We should not skip import if the module contains a non-prevailing407 // definition with interposable linkage type. This is required for408 // correctness in the situation where there is a prevailing def available409 // for import and marked read-only. In this case, the non-prevailing def410 // will be converted to a declaration, while the prevailing one becomes411 // internal, thus no definitions will be available for linking. In order to412 // prevent undefined symbol link error, the prevailing definition must be413 // imported.414 // FIXME: Consider adding a check that the suitable prevailing definition415 // exists and marked read-only.416 if (VI.getSummaryList().size() > 1 &&417 GlobalValue::isInterposableLinkage(GVS->second->linkage()) &&418 !IsPrevailing(VI.getGUID(), GVS->second))419 return true;420 421 return false;422 }423 424 void425 onImportingSummaryImpl(const GlobalValueSummary &Summary,426 SmallVectorImpl<const GlobalVarSummary *> &Worklist) {427 for (const auto &VI : Summary.refs()) {428 if (!shouldImportGlobal(VI)) {429 LLVM_DEBUG(430 dbgs() << "Ref ignored! Target already in destination module.\n");431 continue;432 }433 434 LLVM_DEBUG(dbgs() << " ref -> " << VI << "\n");435 436 for (const auto &RefSummary : VI.getSummaryList()) {437 const auto *GVS = dyn_cast<GlobalVarSummary>(RefSummary.get());438 // Functions could be referenced by global vars - e.g. a vtable; but we439 // don't currently imagine a reason those would be imported here, rather440 // than as part of the logic deciding which functions to import (i.e.441 // based on profile information). Should we decide to handle them here,442 // we can refactor accordingly at that time.443 bool CanImportDecl = false;444 if (!GVS ||445 shouldSkipLocalInAnotherModule(GVS, VI.getSummaryList().size(),446 Summary.modulePath()) ||447 !Index.canImportGlobalVar(GVS, /* AnalyzeRefs */ true,448 CanImportDecl)) {449 if (ImportDeclaration && CanImportDecl)450 ImportList.maybeAddDeclaration(RefSummary->modulePath(),451 VI.getGUID());452 453 continue;454 }455 456 // If there isn't an entry for GUID, insert <GUID, Definition> pair.457 // Otherwise, definition should take precedence over declaration.458 if (ImportList.addDefinition(RefSummary->modulePath(), VI.getGUID()) !=459 FunctionImporter::ImportMapTy::AddDefinitionStatus::Inserted)460 break;461 462 // Only update stat and exports if we haven't already imported this463 // variable.464 NumImportedGlobalVarsThinLink++;465 // Any references made by this variable will be marked exported466 // later, in ComputeCrossModuleImport, after import decisions are467 // complete, which is more efficient than adding them here.468 if (ExportLists)469 (*ExportLists)[RefSummary->modulePath()].insert(VI);470 471 // If variable is not writeonly we attempt to recursively analyze472 // its references in order to import referenced constants.473 if (!Index.isWriteOnly(GVS))474 Worklist.emplace_back(GVS);475 break;476 }477 }478 }479 480public:481 GlobalsImporter(482 const ModuleSummaryIndex &Index, const GVSummaryMapTy &DefinedGVSummaries,483 function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>484 IsPrevailing,485 FunctionImporter::ImportMapTy &ImportList,486 DenseMap<StringRef, FunctionImporter::ExportSetTy> *ExportLists)487 : Index(Index), DefinedGVSummaries(DefinedGVSummaries),488 IsPrevailing(IsPrevailing), ImportList(ImportList),489 ExportLists(ExportLists) {}490 491 void onImportingSummary(const GlobalValueSummary &Summary) {492 SmallVector<const GlobalVarSummary *, 128> Worklist;493 onImportingSummaryImpl(Summary, Worklist);494 while (!Worklist.empty())495 onImportingSummaryImpl(*Worklist.pop_back_val(), Worklist);496 }497};498 499static const char *getFailureName(FunctionImporter::ImportFailureReason Reason);500 501/// Determine the list of imports and exports for each module.502class ModuleImportsManager {503 void computeImportForFunction(504 const FunctionSummary &Summary, unsigned Threshold,505 const GVSummaryMapTy &DefinedGVSummaries,506 SmallVectorImpl<EdgeInfo> &Worklist, GlobalsImporter &GVImporter,507 FunctionImporter::ImportMapTy &ImportList,508 FunctionImporter::ImportThresholdsTy &ImportThresholds);509 510protected:511 function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>512 IsPrevailing;513 const ModuleSummaryIndex &Index;514 DenseMap<StringRef, FunctionImporter::ExportSetTy> *const ExportLists;515 516 ModuleImportsManager(517 function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>518 IsPrevailing,519 const ModuleSummaryIndex &Index,520 DenseMap<StringRef, FunctionImporter::ExportSetTy> *ExportLists = nullptr)521 : IsPrevailing(IsPrevailing), Index(Index), ExportLists(ExportLists) {}522 virtual bool canImport(ValueInfo VI) { return true; }523 524public:525 virtual ~ModuleImportsManager() = default;526 527 /// Given the list of globals defined in a module, compute the list of imports528 /// as well as the list of "exports", i.e. the list of symbols referenced from529 /// another module (that may require promotion).530 virtual void531 computeImportForModule(const GVSummaryMapTy &DefinedGVSummaries,532 StringRef ModName,533 FunctionImporter::ImportMapTy &ImportList);534 535 static std::unique_ptr<ModuleImportsManager>536 create(function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>537 IsPrevailing,538 const ModuleSummaryIndex &Index,539 DenseMap<StringRef, FunctionImporter::ExportSetTy> *ExportLists =540 nullptr);541};542 543/// A ModuleImportsManager that operates based on a workload definition (see544/// -thinlto-workload-def). For modules that do not define workload roots, it545/// applies the base ModuleImportsManager import policy.546class WorkloadImportsManager : public ModuleImportsManager {547 // Keep a module name -> value infos to import association. We use it to548 // determine if a module's import list should be done by the base549 // ModuleImportsManager or by us.550 StringMap<DenseSet<ValueInfo>> Workloads;551 // Track the roots to avoid importing them due to other callers. We want there552 // to be only one variant), for which we optimize according to the contextual553 // profile. "Variants" refers to copies due to importing - we want there to be554 // just one instance of this function.555 DenseSet<ValueInfo> Roots;556 557 void558 computeImportForModule(const GVSummaryMapTy &DefinedGVSummaries,559 StringRef ModName,560 FunctionImporter::ImportMapTy &ImportList) override {561 StringRef Filename = ModName;562 if (CtxprofMoveRootsToOwnModule) {563 Filename = sys::path::filename(ModName);564 // Drop the file extension.565 Filename = Filename.substr(0, Filename.find_last_of('.'));566 }567 auto SetIter = Workloads.find(Filename);568 569 if (SetIter == Workloads.end()) {570 LLVM_DEBUG(dbgs() << "[Workload] " << ModName571 << " does not contain the root of any context.\n");572 return ModuleImportsManager::computeImportForModule(DefinedGVSummaries,573 ModName, ImportList);574 }575 LLVM_DEBUG(dbgs() << "[Workload] " << ModName576 << " contains the root(s) of context(s).\n");577 578 GlobalsImporter GVI(Index, DefinedGVSummaries, IsPrevailing, ImportList,579 ExportLists);580 auto &ValueInfos = SetIter->second;581 for (auto &VI : llvm::make_early_inc_range(ValueInfos)) {582 auto It = DefinedGVSummaries.find(VI.getGUID());583 if (It != DefinedGVSummaries.end() &&584 IsPrevailing(VI.getGUID(), It->second)) {585 LLVM_DEBUG(586 dbgs() << "[Workload] " << VI.name()587 << " has the prevailing variant already in the module "588 << ModName << ". No need to import\n");589 continue;590 }591 auto Candidates =592 qualifyCalleeCandidates(Index, VI.getSummaryList(), ModName);593 594 const GlobalValueSummary *GVS = nullptr;595 auto PotentialCandidates = llvm::map_range(596 llvm::make_filter_range(597 Candidates,598 [&](const auto &Candidate) {599 LLVM_DEBUG(dbgs() << "[Workflow] Candidate for " << VI.name()600 << " from " << Candidate.second->modulePath()601 << " ImportFailureReason: "602 << getFailureName(Candidate.first) << "\n");603 return Candidate.first ==604 FunctionImporter::ImportFailureReason::None;605 }),606 [](const auto &Candidate) { return Candidate.second; });607 if (PotentialCandidates.empty()) {608 LLVM_DEBUG(dbgs() << "[Workload] Not importing " << VI.name()609 << " because can't find eligible Callee. Guid is: "610 << VI.getGUID() << "\n");611 continue;612 }613 /// We will prefer importing the prevailing candidate, if not, we'll614 /// still pick the first available candidate. The reason we want to make615 /// sure we do import the prevailing candidate is because the goal of616 /// workload-awareness is to enable optimizations specializing the call617 /// graph of that workload. Suppose a function is already defined in the618 /// module, but it's not the prevailing variant. Suppose also we do not619 /// inline it (in fact, if it were interposable, we can't inline it),620 /// but we could specialize it to the workload in other ways. However,621 /// the linker would drop it in the favor of the prevailing copy.622 /// Instead, by importing the prevailing variant (assuming also the use623 /// of `-avail-extern-to-local`), we keep the specialization. We could624 /// alteranatively make the non-prevailing variant local, but the625 /// prevailing one is also the one for which we would have previously626 /// collected profiles, making it preferrable.627 auto PrevailingCandidates = llvm::make_filter_range(628 PotentialCandidates, [&](const auto *Candidate) {629 return IsPrevailing(VI.getGUID(), Candidate);630 });631 if (PrevailingCandidates.empty()) {632 GVS = *PotentialCandidates.begin();633 if (!llvm::hasSingleElement(PotentialCandidates) &&634 GlobalValue::isLocalLinkage(GVS->linkage()))635 LLVM_DEBUG(636 dbgs()637 << "[Workload] Found multiple non-prevailing candidates for "638 << VI.name()639 << ". This is unexpected. Are module paths passed to the "640 "compiler unique for the modules passed to the linker?");641 // We could in theory have multiple (interposable) copies of a symbol642 // when there is no prevailing candidate, if say the prevailing copy was643 // in a native object being linked in. However, we should in theory be644 // marking all of these non-prevailing IR copies dead in that case, in645 // which case they won't be candidates.646 assert(GVS->isLive());647 } else {648 assert(llvm::hasSingleElement(PrevailingCandidates));649 GVS = *PrevailingCandidates.begin();650 }651 652 auto ExportingModule = GVS->modulePath();653 // We checked that for the prevailing case, but if we happen to have for654 // example an internal that's defined in this module, it'd have no655 // PrevailingCandidates.656 if (ExportingModule == ModName) {657 LLVM_DEBUG(dbgs() << "[Workload] Not importing " << VI.name()658 << " because its defining module is the same as the "659 "current module\n");660 continue;661 }662 LLVM_DEBUG(dbgs() << "[Workload][Including]" << VI.name() << " from "663 << ExportingModule << " : " << VI.getGUID() << "\n");664 ImportList.addDefinition(ExportingModule, VI.getGUID());665 GVI.onImportingSummary(*GVS);666 if (ExportLists)667 (*ExportLists)[ExportingModule].insert(VI);668 }669 LLVM_DEBUG(dbgs() << "[Workload] Done\n");670 }671 672 void loadFromJson() {673 // Since the workload def uses names, we need a quick lookup674 // name->ValueInfo.675 StringMap<ValueInfo> NameToValueInfo;676 StringSet<> AmbiguousNames;677 for (auto &I : Index) {678 ValueInfo VI = Index.getValueInfo(I);679 if (!NameToValueInfo.insert(std::make_pair(VI.name(), VI)).second)680 LLVM_DEBUG(AmbiguousNames.insert(VI.name()));681 }682 auto DbgReportIfAmbiguous = [&](StringRef Name) {683 LLVM_DEBUG(if (AmbiguousNames.count(Name) > 0) {684 dbgs() << "[Workload] Function name " << Name685 << " present in the workload definition is ambiguous. Consider "686 "compiling with -funique-internal-linkage-names.";687 });688 };689 std::error_code EC;690 auto BufferOrErr = MemoryBuffer::getFileOrSTDIN(WorkloadDefinitions);691 if (std::error_code EC = BufferOrErr.getError()) {692 report_fatal_error("Failed to open context file");693 return;694 }695 auto Buffer = std::move(BufferOrErr.get());696 std::map<std::string, std::vector<std::string>> WorkloadDefs;697 json::Path::Root NullRoot;698 // The JSON is supposed to contain a dictionary matching the type of699 // WorkloadDefs. For example:700 // {701 // "rootFunction_1": ["function_to_import_1", "function_to_import_2"],702 // "rootFunction_2": ["function_to_import_3", "function_to_import_4"]703 // }704 auto Parsed = json::parse(Buffer->getBuffer());705 if (!Parsed)706 report_fatal_error(Parsed.takeError());707 if (!json::fromJSON(*Parsed, WorkloadDefs, NullRoot))708 report_fatal_error("Invalid thinlto contextual profile format.");709 for (const auto &Workload : WorkloadDefs) {710 const auto &Root = Workload.first;711 DbgReportIfAmbiguous(Root);712 LLVM_DEBUG(dbgs() << "[Workload] Root: " << Root << "\n");713 const auto &AllCallees = Workload.second;714 auto RootIt = NameToValueInfo.find(Root);715 if (RootIt == NameToValueInfo.end()) {716 LLVM_DEBUG(dbgs() << "[Workload] Root " << Root717 << " not found in this linkage unit.\n");718 continue;719 }720 auto RootVI = RootIt->second;721 if (RootVI.getSummaryList().size() != 1) {722 LLVM_DEBUG(dbgs() << "[Workload] Root " << Root723 << " should have exactly one summary, but has "724 << RootVI.getSummaryList().size() << ". Skipping.\n");725 continue;726 }727 StringRef RootDefiningModule =728 RootVI.getSummaryList().front()->modulePath();729 LLVM_DEBUG(dbgs() << "[Workload] Root defining module for " << Root730 << " is : " << RootDefiningModule << "\n");731 auto &Set = Workloads[RootDefiningModule];732 for (const auto &Callee : AllCallees) {733 LLVM_DEBUG(dbgs() << "[Workload] " << Callee << "\n");734 DbgReportIfAmbiguous(Callee);735 auto ElemIt = NameToValueInfo.find(Callee);736 if (ElemIt == NameToValueInfo.end()) {737 LLVM_DEBUG(dbgs() << "[Workload] " << Callee << " not found\n");738 continue;739 }740 Set.insert(ElemIt->second);741 }742 }743 }744 745 void loadFromCtxProf() {746 std::error_code EC;747 auto BufferOrErr = MemoryBuffer::getFileOrSTDIN(UseCtxProfile);748 if (std::error_code EC = BufferOrErr.getError()) {749 report_fatal_error("Failed to open contextual profile file");750 return;751 }752 auto Buffer = std::move(BufferOrErr.get());753 754 PGOCtxProfileReader Reader(Buffer->getBuffer());755 auto Ctx = Reader.loadProfiles();756 if (!Ctx) {757 report_fatal_error("Failed to parse contextual profiles");758 return;759 }760 const auto &CtxMap = Ctx->Contexts;761 SetVector<GlobalValue::GUID> ContainedGUIDs;762 for (const auto &[RootGuid, Root] : CtxMap) {763 // Avoid ContainedGUIDs to get in/out of scope. Reuse its memory for764 // subsequent roots, but clear its contents.765 ContainedGUIDs.clear();766 767 auto RootVI = Index.getValueInfo(RootGuid);768 if (!RootVI) {769 LLVM_DEBUG(dbgs() << "[Workload] Root " << RootGuid770 << " not found in this linkage unit.\n");771 continue;772 }773 if (RootVI.getSummaryList().size() != 1) {774 LLVM_DEBUG(dbgs() << "[Workload] Root " << RootGuid775 << " should have exactly one summary, but has "776 << RootVI.getSummaryList().size() << ". Skipping.\n");777 continue;778 }779 std::string RootDefiningModule =780 RootVI.getSummaryList().front()->modulePath().str();781 if (CtxprofMoveRootsToOwnModule) {782 RootDefiningModule = std::to_string(RootGuid);783 LLVM_DEBUG(784 dbgs() << "[Workload] Moving " << RootGuid785 << " to a module with the filename without extension : "786 << RootDefiningModule << "\n");787 } else {788 LLVM_DEBUG(dbgs() << "[Workload] Root defining module for " << RootGuid789 << " is : " << RootDefiningModule << "\n");790 }791 auto &Set = Workloads[RootDefiningModule];792 Root.getContainedGuids(ContainedGUIDs);793 Roots.insert(RootVI);794 for (auto Guid : ContainedGUIDs)795 if (auto VI = Index.getValueInfo(Guid))796 Set.insert(VI);797 }798 }799 800 bool canImport(ValueInfo VI) override { return !Roots.contains(VI); }801 802public:803 WorkloadImportsManager(804 function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>805 IsPrevailing,806 const ModuleSummaryIndex &Index,807 DenseMap<StringRef, FunctionImporter::ExportSetTy> *ExportLists)808 : ModuleImportsManager(IsPrevailing, Index, ExportLists) {809 if (UseCtxProfile.empty() == WorkloadDefinitions.empty()) {810 report_fatal_error(811 "Pass only one of: -thinlto-pgo-ctx-prof or -thinlto-workload-def");812 return;813 }814 if (!UseCtxProfile.empty())815 loadFromCtxProf();816 else817 loadFromJson();818 LLVM_DEBUG({819 for (const auto &[Root, Set] : Workloads) {820 dbgs() << "[Workload] Root: " << Root << " we have " << Set.size()821 << " distinct callees.\n";822 for (const auto &VI : Set) {823 dbgs() << "[Workload] Root: " << Root824 << " Would include: " << VI.getGUID() << "\n";825 }826 }827 });828 }829};830 831std::unique_ptr<ModuleImportsManager> ModuleImportsManager::create(832 function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>833 IsPrevailing,834 const ModuleSummaryIndex &Index,835 DenseMap<StringRef, FunctionImporter::ExportSetTy> *ExportLists) {836 if (WorkloadDefinitions.empty() && UseCtxProfile.empty()) {837 LLVM_DEBUG(dbgs() << "[Workload] Using the regular imports manager.\n");838 return std::unique_ptr<ModuleImportsManager>(839 new ModuleImportsManager(IsPrevailing, Index, ExportLists));840 }841 LLVM_DEBUG(dbgs() << "[Workload] Using the contextual imports manager.\n");842 return std::make_unique<WorkloadImportsManager>(IsPrevailing, Index,843 ExportLists);844}845 846static const char *847getFailureName(FunctionImporter::ImportFailureReason Reason) {848 switch (Reason) {849 case FunctionImporter::ImportFailureReason::None:850 return "None";851 case FunctionImporter::ImportFailureReason::GlobalVar:852 return "GlobalVar";853 case FunctionImporter::ImportFailureReason::NotLive:854 return "NotLive";855 case FunctionImporter::ImportFailureReason::TooLarge:856 return "TooLarge";857 case FunctionImporter::ImportFailureReason::InterposableLinkage:858 return "InterposableLinkage";859 case FunctionImporter::ImportFailureReason::LocalLinkageNotInModule:860 return "LocalLinkageNotInModule";861 case FunctionImporter::ImportFailureReason::NotEligible:862 return "NotEligible";863 case FunctionImporter::ImportFailureReason::NoInline:864 return "NoInline";865 }866 llvm_unreachable("invalid reason");867}868 869/// Compute the list of functions to import for a given caller. Mark these870/// imported functions and the symbols they reference in their source module as871/// exported from their source module.872void ModuleImportsManager::computeImportForFunction(873 const FunctionSummary &Summary, const unsigned Threshold,874 const GVSummaryMapTy &DefinedGVSummaries,875 SmallVectorImpl<EdgeInfo> &Worklist, GlobalsImporter &GVImporter,876 FunctionImporter::ImportMapTy &ImportList,877 FunctionImporter::ImportThresholdsTy &ImportThresholds) {878 GVImporter.onImportingSummary(Summary);879 static int ImportCount = 0;880 for (const auto &Edge : Summary.calls()) {881 ValueInfo VI = Edge.first;882 LLVM_DEBUG(dbgs() << " edge -> " << VI << " Threshold:" << Threshold883 << "\n");884 885 if (ImportCutoff >= 0 && ImportCount >= ImportCutoff) {886 LLVM_DEBUG(dbgs() << "ignored! import-cutoff value of " << ImportCutoff887 << " reached.\n");888 continue;889 }890 891 if (DefinedGVSummaries.count(VI.getGUID())) {892 // FIXME: Consider not skipping import if the module contains893 // a non-prevailing def with interposable linkage. The prevailing copy894 // can safely be imported (see shouldImportGlobal()).895 LLVM_DEBUG(dbgs() << "ignored! Target already in destination module.\n");896 continue;897 }898 899 if (!canImport(VI)) {900 LLVM_DEBUG(901 dbgs() << "Skipping over " << VI.getGUID()902 << " because its import is handled in a different module.");903 assert(VI.getSummaryList().size() == 1 &&904 "The root was expected to be an external symbol");905 continue;906 }907 908 auto GetBonusMultiplier = [](CalleeInfo::HotnessType Hotness) -> float {909 if (Hotness == CalleeInfo::HotnessType::Hot)910 return ImportHotMultiplier;911 if (Hotness == CalleeInfo::HotnessType::Cold)912 return ImportColdMultiplier;913 if (Hotness == CalleeInfo::HotnessType::Critical)914 return ImportCriticalMultiplier;915 return 1.0;916 };917 918 const auto NewThreshold =919 Threshold * GetBonusMultiplier(Edge.second.getHotness());920 921 auto IT = ImportThresholds.insert(std::make_pair(922 VI.getGUID(), std::make_tuple(NewThreshold, nullptr, nullptr)));923 bool PreviouslyVisited = !IT.second;924 auto &ProcessedThreshold = std::get<0>(IT.first->second);925 auto &CalleeSummary = std::get<1>(IT.first->second);926 auto &FailureInfo = std::get<2>(IT.first->second);927 928 bool IsHotCallsite =929 Edge.second.getHotness() == CalleeInfo::HotnessType::Hot;930 bool IsCriticalCallsite =931 Edge.second.getHotness() == CalleeInfo::HotnessType::Critical;932 933 const FunctionSummary *ResolvedCalleeSummary = nullptr;934 if (CalleeSummary) {935 assert(PreviouslyVisited);936 // Since the traversal of the call graph is DFS, we can revisit a function937 // a second time with a higher threshold. In this case, it is added back938 // to the worklist with the new threshold (so that its own callee chains939 // can be considered with the higher threshold).940 if (NewThreshold <= ProcessedThreshold) {941 LLVM_DEBUG(942 dbgs() << "ignored! Target was already imported with Threshold "943 << ProcessedThreshold << "\n");944 continue;945 }946 // Update with new larger threshold.947 ProcessedThreshold = NewThreshold;948 ResolvedCalleeSummary = cast<FunctionSummary>(CalleeSummary);949 } else {950 // If we already rejected importing a callee at the same or higher951 // threshold, don't waste time calling selectCallee.952 if (PreviouslyVisited && NewThreshold <= ProcessedThreshold) {953 LLVM_DEBUG(954 dbgs() << "ignored! Target was already rejected with Threshold "955 << ProcessedThreshold << "\n");956 if (PrintImportFailures) {957 assert(FailureInfo &&958 "Expected FailureInfo for previously rejected candidate");959 FailureInfo->Attempts++;960 }961 continue;962 }963 964 FunctionImporter::ImportFailureReason Reason{};965 966 // `SummaryForDeclImport` is an summary eligible for declaration import.967 const GlobalValueSummary *SummaryForDeclImport = nullptr;968 CalleeSummary =969 selectCallee(Index, VI.getSummaryList(), NewThreshold,970 Summary.modulePath(), SummaryForDeclImport, Reason);971 if (!CalleeSummary) {972 // There isn't a callee for definition import but one for declaration973 // import.974 if (ImportDeclaration && SummaryForDeclImport) {975 StringRef DeclSourceModule = SummaryForDeclImport->modulePath();976 977 // Note `ExportLists` only keeps track of exports due to imported978 // definitions.979 ImportList.maybeAddDeclaration(DeclSourceModule, VI.getGUID());980 }981 // Update with new larger threshold if this was a retry (otherwise982 // we would have already inserted with NewThreshold above). Also983 // update failure info if requested.984 if (PreviouslyVisited) {985 ProcessedThreshold = NewThreshold;986 if (PrintImportFailures) {987 assert(FailureInfo &&988 "Expected FailureInfo for previously rejected candidate");989 FailureInfo->Reason = Reason;990 FailureInfo->Attempts++;991 FailureInfo->MaxHotness =992 std::max(FailureInfo->MaxHotness, Edge.second.getHotness());993 }994 } else if (PrintImportFailures) {995 assert(!FailureInfo &&996 "Expected no FailureInfo for newly rejected candidate");997 FailureInfo = std::make_unique<FunctionImporter::ImportFailureInfo>(998 VI, Edge.second.getHotness(), Reason, 1);999 }1000 if (ForceImportAll) {1001 std::string Msg = std::string("Failed to import function ") +1002 VI.name().str() + " due to " +1003 getFailureName(Reason);1004 auto Error = make_error<StringError>(1005 Msg, make_error_code(errc::not_supported));1006 logAllUnhandledErrors(std::move(Error), errs(),1007 "Error importing module: ");1008 break;1009 } else {1010 LLVM_DEBUG(dbgs()1011 << "ignored! No qualifying callee with summary found.\n");1012 continue;1013 }1014 }1015 1016 // "Resolve" the summary1017 CalleeSummary = CalleeSummary->getBaseObject();1018 ResolvedCalleeSummary = cast<FunctionSummary>(CalleeSummary);1019 1020 assert((ResolvedCalleeSummary->fflags().AlwaysInline || ForceImportAll ||1021 (ResolvedCalleeSummary->instCount() <= NewThreshold)) &&1022 "selectCallee() didn't honor the threshold");1023 1024 auto ExportModulePath = ResolvedCalleeSummary->modulePath();1025 1026 // Try emplace the definition entry, and update stats based on insertion1027 // status.1028 if (ImportList.addDefinition(ExportModulePath, VI.getGUID()) !=1029 FunctionImporter::ImportMapTy::AddDefinitionStatus::NoChange) {1030 NumImportedFunctionsThinLink++;1031 if (IsHotCallsite)1032 NumImportedHotFunctionsThinLink++;1033 if (IsCriticalCallsite)1034 NumImportedCriticalFunctionsThinLink++;1035 }1036 1037 // Any calls/references made by this function will be marked exported1038 // later, in ComputeCrossModuleImport, after import decisions are1039 // complete, which is more efficient than adding them here.1040 if (ExportLists)1041 (*ExportLists)[ExportModulePath].insert(VI);1042 }1043 1044 auto GetAdjustedThreshold = [](unsigned Threshold, bool IsHotCallsite) {1045 // Adjust the threshold for next level of imported functions.1046 // The threshold is different for hot callsites because we can then1047 // inline chains of hot calls.1048 if (IsHotCallsite)1049 return Threshold * ImportHotInstrFactor;1050 return Threshold * ImportInstrFactor;1051 };1052 1053 const auto AdjThreshold = GetAdjustedThreshold(Threshold, IsHotCallsite);1054 1055 ImportCount++;1056 1057 // Insert the newly imported function to the worklist.1058 Worklist.emplace_back(ResolvedCalleeSummary, AdjThreshold);1059 }1060}1061 1062void ModuleImportsManager::computeImportForModule(1063 const GVSummaryMapTy &DefinedGVSummaries, StringRef ModName,1064 FunctionImporter::ImportMapTy &ImportList) {1065 // Worklist contains the list of function imported in this module, for which1066 // we will analyse the callees and may import further down the callgraph.1067 SmallVector<EdgeInfo, 128> Worklist;1068 GlobalsImporter GVI(Index, DefinedGVSummaries, IsPrevailing, ImportList,1069 ExportLists);1070 FunctionImporter::ImportThresholdsTy ImportThresholds;1071 1072 // Populate the worklist with the import for the functions in the current1073 // module1074 for (const auto &GVSummary : DefinedGVSummaries) {1075#ifndef NDEBUG1076 // FIXME: Change the GVSummaryMapTy to hold ValueInfo instead of GUID1077 // so this map look up (and possibly others) can be avoided.1078 auto VI = Index.getValueInfo(GVSummary.first);1079#endif1080 if (!Index.isGlobalValueLive(GVSummary.second)) {1081 LLVM_DEBUG(dbgs() << "Ignores Dead GUID: " << VI << "\n");1082 continue;1083 }1084 auto *FuncSummary =1085 dyn_cast<FunctionSummary>(GVSummary.second->getBaseObject());1086 if (!FuncSummary)1087 // Skip import for global variables1088 continue;1089 LLVM_DEBUG(dbgs() << "Initialize import for " << VI << "\n");1090 computeImportForFunction(*FuncSummary, ImportInstrLimit, DefinedGVSummaries,1091 Worklist, GVI, ImportList, ImportThresholds);1092 }1093 1094 // Process the newly imported functions and add callees to the worklist.1095 while (!Worklist.empty()) {1096 auto GVInfo = Worklist.pop_back_val();1097 auto *Summary = std::get<0>(GVInfo);1098 auto Threshold = std::get<1>(GVInfo);1099 1100 if (auto *FS = dyn_cast<FunctionSummary>(Summary))1101 computeImportForFunction(*FS, Threshold, DefinedGVSummaries, Worklist,1102 GVI, ImportList, ImportThresholds);1103 }1104 1105 // Print stats about functions considered but rejected for importing1106 // when requested.1107 if (PrintImportFailures) {1108 dbgs() << "Missed imports into module " << ModName << "\n";1109 for (auto &I : ImportThresholds) {1110 auto &ProcessedThreshold = std::get<0>(I.second);1111 auto &CalleeSummary = std::get<1>(I.second);1112 auto &FailureInfo = std::get<2>(I.second);1113 if (CalleeSummary)1114 continue; // We are going to import.1115 assert(FailureInfo);1116 FunctionSummary *FS = nullptr;1117 if (!FailureInfo->VI.getSummaryList().empty())1118 FS = dyn_cast<FunctionSummary>(1119 FailureInfo->VI.getSummaryList()[0]->getBaseObject());1120 dbgs() << FailureInfo->VI1121 << ": Reason = " << getFailureName(FailureInfo->Reason)1122 << ", Threshold = " << ProcessedThreshold1123 << ", Size = " << (FS ? (int)FS->instCount() : -1)1124 << ", MaxHotness = " << getHotnessName(FailureInfo->MaxHotness)1125 << ", Attempts = " << FailureInfo->Attempts << "\n";1126 }1127 }1128}1129 1130#ifndef NDEBUG1131static bool isGlobalVarSummary(const ModuleSummaryIndex &Index, ValueInfo VI) {1132 auto SL = VI.getSummaryList();1133 return SL.empty()1134 ? false1135 : SL[0]->getSummaryKind() == GlobalValueSummary::GlobalVarKind;1136}1137 1138static bool isGlobalVarSummary(const ModuleSummaryIndex &Index,1139 GlobalValue::GUID G) {1140 if (const auto &VI = Index.getValueInfo(G))1141 return isGlobalVarSummary(Index, VI);1142 return false;1143}1144 1145// Return the number of global variable summaries in ExportSet.1146static unsigned1147numGlobalVarSummaries(const ModuleSummaryIndex &Index,1148 FunctionImporter::ExportSetTy &ExportSet) {1149 unsigned NumGVS = 0;1150 for (auto &VI : ExportSet)1151 if (isGlobalVarSummary(Index, VI.getGUID()))1152 ++NumGVS;1153 return NumGVS;1154}1155 1156struct ImportStatistics {1157 unsigned NumGVS = 0;1158 unsigned DefinedFS = 0;1159 unsigned Count = 0;1160};1161 1162// Compute import statistics for each source module in ImportList.1163static DenseMap<StringRef, ImportStatistics>1164collectImportStatistics(const ModuleSummaryIndex &Index,1165 const FunctionImporter::ImportMapTy &ImportList) {1166 DenseMap<StringRef, ImportStatistics> Histogram;1167 1168 for (const auto &[FromModule, GUID, Type] : ImportList) {1169 ImportStatistics &Entry = Histogram[FromModule];1170 ++Entry.Count;1171 if (isGlobalVarSummary(Index, GUID))1172 ++Entry.NumGVS;1173 else if (Type == GlobalValueSummary::Definition)1174 ++Entry.DefinedFS;1175 }1176 return Histogram;1177}1178#endif1179 1180#ifndef NDEBUG1181static bool checkVariableImport(1182 const ModuleSummaryIndex &Index,1183 FunctionImporter::ImportListsTy &ImportLists,1184 DenseMap<StringRef, FunctionImporter::ExportSetTy> &ExportLists) {1185 DenseSet<GlobalValue::GUID> FlattenedImports;1186 1187 for (const auto &ImportPerModule : ImportLists)1188 for (const auto &[FromModule, GUID, ImportType] : ImportPerModule.second)1189 FlattenedImports.insert(GUID);1190 1191 // Checks that all GUIDs of read/writeonly vars we see in export lists1192 // are also in the import lists. Otherwise we my face linker undefs,1193 // because readonly and writeonly vars are internalized in their1194 // source modules. The exception would be if it has a linkage type indicating1195 // that there may have been a copy existing in the importing module (e.g.1196 // linkonce_odr). In that case we cannot accurately do this checking.1197 auto IsReadOrWriteOnlyVarNeedingImporting = [&](StringRef ModulePath,1198 const ValueInfo &VI) {1199 auto *GVS = dyn_cast_or_null<GlobalVarSummary>(1200 Index.findSummaryInModule(VI, ModulePath));1201 return GVS && (Index.isReadOnly(GVS) || Index.isWriteOnly(GVS)) &&1202 !(GVS->linkage() == GlobalValue::AvailableExternallyLinkage ||1203 GVS->linkage() == GlobalValue::WeakODRLinkage ||1204 GVS->linkage() == GlobalValue::LinkOnceODRLinkage);1205 };1206 1207 for (auto &ExportPerModule : ExportLists)1208 for (auto &VI : ExportPerModule.second)1209 if (!FlattenedImports.count(VI.getGUID()) &&1210 IsReadOrWriteOnlyVarNeedingImporting(ExportPerModule.first, VI))1211 return false;1212 1213 return true;1214}1215#endif1216 1217/// Compute all the import and export for every module using the Index.1218void llvm::ComputeCrossModuleImport(1219 const ModuleSummaryIndex &Index,1220 const DenseMap<StringRef, GVSummaryMapTy> &ModuleToDefinedGVSummaries,1221 function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>1222 isPrevailing,1223 FunctionImporter::ImportListsTy &ImportLists,1224 DenseMap<StringRef, FunctionImporter::ExportSetTy> &ExportLists) {1225 auto MIS = ModuleImportsManager::create(isPrevailing, Index, &ExportLists);1226 // For each module that has function defined, compute the import/export lists.1227 for (const auto &DefinedGVSummaries : ModuleToDefinedGVSummaries) {1228 auto &ImportList = ImportLists[DefinedGVSummaries.first];1229 LLVM_DEBUG(dbgs() << "Computing import for Module '"1230 << DefinedGVSummaries.first << "'\n");1231 MIS->computeImportForModule(DefinedGVSummaries.second,1232 DefinedGVSummaries.first, ImportList);1233 }1234 1235 // When computing imports we only added the variables and functions being1236 // imported to the export list. We also need to mark any references and calls1237 // they make as exported as well. We do this here, as it is more efficient1238 // since we may import the same values multiple times into different modules1239 // during the import computation.1240 for (auto &ELI : ExportLists) {1241 // `NewExports` tracks the VI that gets exported because the full definition1242 // of its user/referencer gets exported.1243 FunctionImporter::ExportSetTy NewExports;1244 const auto &DefinedGVSummaries =1245 ModuleToDefinedGVSummaries.lookup(ELI.first);1246 for (auto &EI : ELI.second) {1247 // Find the copy defined in the exporting module so that we can mark the1248 // values it references in that specific definition as exported.1249 // Below we will add all references and called values, without regard to1250 // whether they are also defined in this module. We subsequently prune the1251 // list to only include those defined in the exporting module, see comment1252 // there as to why.1253 auto DS = DefinedGVSummaries.find(EI.getGUID());1254 // Anything marked exported during the import computation must have been1255 // defined in the exporting module.1256 assert(DS != DefinedGVSummaries.end());1257 auto *S = DS->getSecond();1258 S = S->getBaseObject();1259 if (auto *GVS = dyn_cast<GlobalVarSummary>(S)) {1260 // Export referenced functions and variables. We don't export/promote1261 // objects referenced by writeonly variable initializer, because1262 // we convert such variables initializers to "zeroinitializer".1263 // See processGlobalForThinLTO.1264 if (!Index.isWriteOnly(GVS))1265 NewExports.insert_range(GVS->refs());1266 } else {1267 auto *FS = cast<FunctionSummary>(S);1268 NewExports.insert_range(llvm::make_first_range(FS->calls()));1269 NewExports.insert_range(FS->refs());1270 }1271 }1272 // Prune list computed above to only include values defined in the1273 // exporting module. We do this after the above insertion since we may hit1274 // the same ref/call target multiple times in above loop, and it is more1275 // efficient to avoid a set lookup each time.1276 for (auto EI = NewExports.begin(); EI != NewExports.end();) {1277 if (!DefinedGVSummaries.count(EI->getGUID()))1278 NewExports.erase(EI++);1279 else1280 ++EI;1281 }1282 ELI.second.insert_range(NewExports);1283 }1284 1285 assert(checkVariableImport(Index, ImportLists, ExportLists));1286#ifndef NDEBUG1287 LLVM_DEBUG(dbgs() << "Import/Export lists for " << ImportLists.size()1288 << " modules:\n");1289 for (const auto &ModuleImports : ImportLists) {1290 auto ModName = ModuleImports.first;1291 auto &Exports = ExportLists[ModName];1292 unsigned NumGVS = numGlobalVarSummaries(Index, Exports);1293 DenseMap<StringRef, ImportStatistics> Histogram =1294 collectImportStatistics(Index, ModuleImports.second);1295 LLVM_DEBUG(dbgs() << "* Module " << ModName << " exports "1296 << Exports.size() - NumGVS << " functions and " << NumGVS1297 << " vars. Imports from " << Histogram.size()1298 << " modules.\n");1299 for (const auto &[SrcModName, Stats] : Histogram) {1300 LLVM_DEBUG(dbgs() << " - " << Stats.DefinedFS1301 << " function definitions and "1302 << Stats.Count - Stats.NumGVS - Stats.DefinedFS1303 << " function declarations imported from " << SrcModName1304 << "\n");1305 LLVM_DEBUG(dbgs() << " - " << Stats.NumGVS1306 << " global vars imported from " << SrcModName << "\n");1307 }1308 }1309#endif1310}1311 1312#ifndef NDEBUG1313static void dumpImportListForModule(const ModuleSummaryIndex &Index,1314 StringRef ModulePath,1315 FunctionImporter::ImportMapTy &ImportList) {1316 DenseMap<StringRef, ImportStatistics> Histogram =1317 collectImportStatistics(Index, ImportList);1318 LLVM_DEBUG(dbgs() << "* Module " << ModulePath << " imports from "1319 << Histogram.size() << " modules.\n");1320 for (const auto &[SrcModName, Stats] : Histogram) {1321 LLVM_DEBUG(dbgs() << " - " << Stats.DefinedFS1322 << " function definitions and "1323 << Stats.Count - Stats.DefinedFS - Stats.NumGVS1324 << " function declarations imported from " << SrcModName1325 << "\n");1326 LLVM_DEBUG(dbgs() << " - " << Stats.NumGVS << " vars imported from "1327 << SrcModName << "\n");1328 }1329}1330#endif1331 1332/// Compute all the imports for the given module using the Index.1333///1334/// \p isPrevailing is a callback that will be called with a global value's GUID1335/// and summary and should return whether the module corresponding to the1336/// summary contains the linker-prevailing copy of that value.1337///1338/// \p ImportList will be populated with a map that can be passed to1339/// FunctionImporter::importFunctions() above (see description there).1340static void ComputeCrossModuleImportForModuleForTest(1341 StringRef ModulePath,1342 function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>1343 isPrevailing,1344 const ModuleSummaryIndex &Index,1345 FunctionImporter::ImportMapTy &ImportList) {1346 // Collect the list of functions this module defines.1347 // GUID -> Summary1348 GVSummaryMapTy FunctionSummaryMap;1349 Index.collectDefinedFunctionsForModule(ModulePath, FunctionSummaryMap);1350 1351 // Compute the import list for this module.1352 LLVM_DEBUG(dbgs() << "Computing import for Module '" << ModulePath << "'\n");1353 auto MIS = ModuleImportsManager::create(isPrevailing, Index);1354 MIS->computeImportForModule(FunctionSummaryMap, ModulePath, ImportList);1355 1356#ifndef NDEBUG1357 dumpImportListForModule(Index, ModulePath, ImportList);1358#endif1359}1360 1361/// Mark all external summaries in \p Index for import into the given module.1362/// Used for testing the case of distributed builds using a distributed index.1363///1364/// \p ImportList will be populated with a map that can be passed to1365/// FunctionImporter::importFunctions() above (see description there).1366static void ComputeCrossModuleImportForModuleFromIndexForTest(1367 StringRef ModulePath, const ModuleSummaryIndex &Index,1368 FunctionImporter::ImportMapTy &ImportList) {1369 for (const auto &GlobalList : Index) {1370 // Ignore entries for undefined references.1371 if (GlobalList.second.getSummaryList().empty())1372 continue;1373 1374 auto GUID = GlobalList.first;1375 assert(GlobalList.second.getSummaryList().size() == 1 &&1376 "Expected individual combined index to have one summary per GUID");1377 auto &Summary = GlobalList.second.getSummaryList()[0];1378 // Skip the summaries for the importing module. These are included to1379 // e.g. record required linkage changes.1380 if (Summary->modulePath() == ModulePath)1381 continue;1382 // Add an entry to provoke importing by thinBackend.1383 ImportList.addGUID(Summary->modulePath(), GUID, Summary->importType());1384 }1385#ifndef NDEBUG1386 dumpImportListForModule(Index, ModulePath, ImportList);1387#endif1388}1389 1390// For SamplePGO, the indirect call targets for local functions will1391// have its original name annotated in profile. We try to find the1392// corresponding PGOFuncName as the GUID, and fix up the edges1393// accordingly.1394void updateValueInfoForIndirectCalls(ModuleSummaryIndex &Index,1395 FunctionSummary *FS) {1396 for (auto &EI : FS->mutableCalls()) {1397 if (!EI.first.getSummaryList().empty())1398 continue;1399 auto GUID = Index.getGUIDFromOriginalID(EI.first.getGUID());1400 if (GUID == 0)1401 continue;1402 // Update the edge to point directly to the correct GUID.1403 auto VI = Index.getValueInfo(GUID);1404 if (llvm::any_of(1405 VI.getSummaryList(),1406 [&](const std::unique_ptr<GlobalValueSummary> &SummaryPtr) {1407 // The mapping from OriginalId to GUID may return a GUID1408 // that corresponds to a static variable. Filter it out here.1409 // This can happen when1410 // 1) There is a call to a library function which is not defined1411 // in the index.1412 // 2) There is a static variable with the OriginalGUID identical1413 // to the GUID of the library function in 1);1414 // When this happens the static variable in 2) will be found,1415 // which needs to be filtered out.1416 return SummaryPtr->getSummaryKind() ==1417 GlobalValueSummary::GlobalVarKind;1418 }))1419 continue;1420 EI.first = VI;1421 }1422}1423 1424void llvm::updateIndirectCalls(ModuleSummaryIndex &Index) {1425 for (const auto &Entry : Index) {1426 for (const auto &S : Entry.second.getSummaryList()) {1427 if (auto *FS = dyn_cast<FunctionSummary>(S.get()))1428 updateValueInfoForIndirectCalls(Index, FS);1429 }1430 }1431}1432 1433void llvm::computeDeadSymbolsAndUpdateIndirectCalls(1434 ModuleSummaryIndex &Index,1435 const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols,1436 function_ref<PrevailingType(GlobalValue::GUID)> isPrevailing) {1437 assert(!Index.withGlobalValueDeadStripping());1438 if (!ComputeDead ||1439 // Don't do anything when nothing is live, this is friendly with tests.1440 GUIDPreservedSymbols.empty()) {1441 // Still need to update indirect calls.1442 updateIndirectCalls(Index);1443 return;1444 }1445 unsigned LiveSymbols = 0;1446 SmallVector<ValueInfo, 128> Worklist;1447 Worklist.reserve(GUIDPreservedSymbols.size() * 2);1448 for (auto GUID : GUIDPreservedSymbols) {1449 ValueInfo VI = Index.getValueInfo(GUID);1450 if (!VI)1451 continue;1452 for (const auto &S : VI.getSummaryList())1453 S->setLive(true);1454 }1455 1456 // Add values flagged in the index as live roots to the worklist.1457 for (const auto &Entry : Index) {1458 auto VI = Index.getValueInfo(Entry);1459 for (const auto &S : Entry.second.getSummaryList()) {1460 if (auto *FS = dyn_cast<FunctionSummary>(S.get()))1461 updateValueInfoForIndirectCalls(Index, FS);1462 if (S->isLive()) {1463 LLVM_DEBUG(dbgs() << "Live root: " << VI << "\n");1464 Worklist.push_back(VI);1465 ++LiveSymbols;1466 break;1467 }1468 }1469 }1470 1471 // Make value live and add it to the worklist if it was not live before.1472 auto visit = [&](ValueInfo VI, bool IsAliasee) {1473 // FIXME: If we knew which edges were created for indirect call profiles,1474 // we could skip them here. Any that are live should be reached via1475 // other edges, e.g. reference edges. Otherwise, using a profile collected1476 // on a slightly different binary might provoke preserving, importing1477 // and ultimately promoting calls to functions not linked into this1478 // binary, which increases the binary size unnecessarily. Note that1479 // if this code changes, the importer needs to change so that edges1480 // to functions marked dead are skipped.1481 1482 if (llvm::any_of(VI.getSummaryList(),1483 [](const std::unique_ptr<llvm::GlobalValueSummary> &S) {1484 return S->isLive();1485 }))1486 return;1487 1488 // We only keep live symbols that are known to be non-prevailing if any are1489 // available_externally, linkonceodr, weakodr. Those symbols are discarded1490 // later in the EliminateAvailableExternally pass and setting them to1491 // not-live could break downstreams users of liveness information (PR36483)1492 // or limit optimization opportunities.1493 if (isPrevailing(VI.getGUID()) == PrevailingType::No) {1494 bool KeepAliveLinkage = false;1495 bool Interposable = false;1496 for (const auto &S : VI.getSummaryList()) {1497 if (S->linkage() == GlobalValue::AvailableExternallyLinkage ||1498 S->linkage() == GlobalValue::WeakODRLinkage ||1499 S->linkage() == GlobalValue::LinkOnceODRLinkage)1500 KeepAliveLinkage = true;1501 else if (GlobalValue::isInterposableLinkage(S->linkage()))1502 Interposable = true;1503 }1504 1505 if (!IsAliasee) {1506 if (!KeepAliveLinkage)1507 return;1508 1509 if (Interposable)1510 report_fatal_error(1511 "Interposable and available_externally/linkonce_odr/weak_odr "1512 "symbol");1513 }1514 }1515 1516 for (const auto &S : VI.getSummaryList())1517 S->setLive(true);1518 ++LiveSymbols;1519 Worklist.push_back(VI);1520 };1521 1522 while (!Worklist.empty()) {1523 auto VI = Worklist.pop_back_val();1524 for (const auto &Summary : VI.getSummaryList()) {1525 if (auto *AS = dyn_cast<AliasSummary>(Summary.get())) {1526 // If this is an alias, visit the aliasee VI to ensure that all copies1527 // are marked live and it is added to the worklist for further1528 // processing of its references.1529 visit(AS->getAliaseeVI(), true);1530 continue;1531 }1532 for (auto Ref : Summary->refs())1533 visit(Ref, false);1534 if (auto *FS = dyn_cast<FunctionSummary>(Summary.get()))1535 for (auto Call : FS->calls())1536 visit(Call.first, false);1537 }1538 }1539 Index.setWithGlobalValueDeadStripping();1540 1541 unsigned DeadSymbols = Index.size() - LiveSymbols;1542 LLVM_DEBUG(dbgs() << LiveSymbols << " symbols Live, and " << DeadSymbols1543 << " symbols Dead \n");1544 NumDeadSymbols += DeadSymbols;1545 NumLiveSymbols += LiveSymbols;1546}1547 1548// Compute dead symbols and propagate constants in combined index.1549void llvm::computeDeadSymbolsWithConstProp(1550 ModuleSummaryIndex &Index,1551 const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols,1552 function_ref<PrevailingType(GlobalValue::GUID)> isPrevailing,1553 bool ImportEnabled) {1554 llvm::TimeTraceScope timeScope("Drop dead symbols and propagate attributes");1555 computeDeadSymbolsAndUpdateIndirectCalls(Index, GUIDPreservedSymbols,1556 isPrevailing);1557 if (ImportEnabled)1558 Index.propagateAttributes(GUIDPreservedSymbols);1559}1560 1561/// Compute the set of summaries needed for a ThinLTO backend compilation of1562/// \p ModulePath.1563void llvm::gatherImportedSummariesForModule(1564 StringRef ModulePath,1565 const DenseMap<StringRef, GVSummaryMapTy> &ModuleToDefinedGVSummaries,1566 const FunctionImporter::ImportMapTy &ImportList,1567 ModuleToSummariesForIndexTy &ModuleToSummariesForIndex,1568 GVSummaryPtrSet &DecSummaries) {1569 // Include all summaries from the importing module.1570 ModuleToSummariesForIndex[std::string(ModulePath)] =1571 ModuleToDefinedGVSummaries.lookup(ModulePath);1572 1573 // Forward port the heterogeneous std::map::operator[]() from C++26, which1574 // lets us look up the map without allocating an instance of std::string when1575 // the key-value pair exists in the map.1576 // TODO: Remove this in favor of the heterogenous std::map::operator[]() from1577 // C++26 when it becomes available for our codebase.1578 auto LookupOrCreate = [](ModuleToSummariesForIndexTy &Map,1579 StringRef Key) -> GVSummaryMapTy & {1580 auto It = Map.find(Key);1581 if (It == Map.end())1582 std::tie(It, std::ignore) =1583 Map.try_emplace(std::string(Key), GVSummaryMapTy());1584 return It->second;1585 };1586 1587 // Include summaries for imports.1588 for (const auto &[FromModule, GUID, ImportType] : ImportList) {1589 auto &SummariesForIndex =1590 LookupOrCreate(ModuleToSummariesForIndex, FromModule);1591 1592 const auto &DefinedGVSummaries = ModuleToDefinedGVSummaries.at(FromModule);1593 const auto &DS = DefinedGVSummaries.find(GUID);1594 assert(DS != DefinedGVSummaries.end() &&1595 "Expected a defined summary for imported global value");1596 if (ImportType == GlobalValueSummary::Declaration)1597 DecSummaries.insert(DS->second);1598 1599 SummariesForIndex[GUID] = DS->second;1600 }1601}1602 1603/// Emit the files \p ModulePath will import from into \p OutputFilename.1604Error llvm::EmitImportsFiles(1605 StringRef ModulePath, StringRef OutputFilename,1606 const ModuleToSummariesForIndexTy &ModuleToSummariesForIndex) {1607 std::error_code EC;1608 raw_fd_ostream ImportsOS(OutputFilename, EC, sys::fs::OpenFlags::OF_Text);1609 if (EC)1610 return createFileError("cannot open " + OutputFilename,1611 errorCodeToError(EC));1612 processImportsFiles(ModulePath, ModuleToSummariesForIndex,1613 [&](StringRef M) { ImportsOS << M << "\n"; });1614 return Error::success();1615}1616 1617/// Invoke callback \p F on the file paths from which \p ModulePath1618/// will import.1619void llvm::processImportsFiles(1620 StringRef ModulePath,1621 const ModuleToSummariesForIndexTy &ModuleToSummariesForIndex,1622 function_ref<void(const std::string &)> F) {1623 for (const auto &ILI : ModuleToSummariesForIndex)1624 // The ModuleToSummariesForIndex map includes an entry for the current1625 // Module (needed for writing out the index files). We don't want to1626 // include it in the imports file, however, so filter it out.1627 if (ILI.first != ModulePath)1628 F(ILI.first);1629}1630 1631bool llvm::convertToDeclaration(GlobalValue &GV) {1632 LLVM_DEBUG(dbgs() << "Converting to a declaration: `" << GV.getName()1633 << "\n");1634 if (Function *F = dyn_cast<Function>(&GV)) {1635 F->deleteBody();1636 F->clearMetadata();1637 F->setComdat(nullptr);1638 } else if (GlobalVariable *V = dyn_cast<GlobalVariable>(&GV)) {1639 V->setInitializer(nullptr);1640 V->setLinkage(GlobalValue::ExternalLinkage);1641 V->clearMetadata();1642 V->setComdat(nullptr);1643 } else {1644 GlobalValue *NewGV;1645 if (GV.getValueType()->isFunctionTy())1646 NewGV =1647 Function::Create(cast<FunctionType>(GV.getValueType()),1648 GlobalValue::ExternalLinkage, GV.getAddressSpace(),1649 "", GV.getParent());1650 else1651 NewGV =1652 new GlobalVariable(*GV.getParent(), GV.getValueType(),1653 /*isConstant*/ false, GlobalValue::ExternalLinkage,1654 /*init*/ nullptr, "",1655 /*insertbefore*/ nullptr, GV.getThreadLocalMode(),1656 GV.getType()->getAddressSpace());1657 NewGV->takeName(&GV);1658 GV.replaceAllUsesWith(NewGV);1659 return false;1660 }1661 if (!GV.isImplicitDSOLocal())1662 GV.setDSOLocal(false);1663 return true;1664}1665 1666void llvm::thinLTOFinalizeInModule(Module &TheModule,1667 const GVSummaryMapTy &DefinedGlobals,1668 bool PropagateAttrs) {1669 llvm::TimeTraceScope timeScope("ThinLTO finalize in module");1670 DenseSet<Comdat *> NonPrevailingComdats;1671 auto FinalizeInModule = [&](GlobalValue &GV, bool Propagate = false) {1672 // See if the global summary analysis computed a new resolved linkage.1673 const auto &GS = DefinedGlobals.find(GV.getGUID());1674 if (GS == DefinedGlobals.end())1675 return;1676 1677 if (Propagate)1678 if (FunctionSummary *FS = dyn_cast<FunctionSummary>(GS->second)) {1679 if (Function *F = dyn_cast<Function>(&GV)) {1680 // TODO: propagate ReadNone and ReadOnly.1681 if (FS->fflags().ReadNone && !F->doesNotAccessMemory())1682 F->setDoesNotAccessMemory();1683 1684 if (FS->fflags().ReadOnly && !F->onlyReadsMemory())1685 F->setOnlyReadsMemory();1686 1687 if (FS->fflags().NoRecurse && !F->doesNotRecurse())1688 F->setDoesNotRecurse();1689 1690 if (FS->fflags().NoUnwind && !F->doesNotThrow())1691 F->setDoesNotThrow();1692 }1693 }1694 1695 auto NewLinkage = GS->second->linkage();1696 if (GlobalValue::isLocalLinkage(GV.getLinkage()) ||1697 // Don't internalize anything here, because the code below1698 // lacks necessary correctness checks. Leave this job to1699 // LLVM 'internalize' pass.1700 GlobalValue::isLocalLinkage(NewLinkage) ||1701 // In case it was dead and already converted to declaration.1702 GV.isDeclaration())1703 return;1704 1705 // Set the potentially more constraining visibility computed from summaries.1706 // The DefaultVisibility condition is because older GlobalValueSummary does1707 // not record DefaultVisibility and we don't want to change protected/hidden1708 // to default.1709 if (GS->second->getVisibility() != GlobalValue::DefaultVisibility)1710 GV.setVisibility(GS->second->getVisibility());1711 1712 if (NewLinkage == GV.getLinkage())1713 return;1714 1715 // Check for a non-prevailing def that has interposable linkage1716 // (e.g. non-odr weak or linkonce). In that case we can't simply1717 // convert to available_externally, since it would lose the1718 // interposable property and possibly get inlined. Simply drop1719 // the definition in that case.1720 if (GlobalValue::isAvailableExternallyLinkage(NewLinkage) &&1721 GlobalValue::isInterposableLinkage(GV.getLinkage())) {1722 if (!convertToDeclaration(GV))1723 // FIXME: Change this to collect replaced GVs and later erase1724 // them from the parent module once thinLTOResolvePrevailingGUID is1725 // changed to enable this for aliases.1726 llvm_unreachable("Expected GV to be converted");1727 } else {1728 // If all copies of the original symbol had global unnamed addr and1729 // linkonce_odr linkage, or if all of them had local unnamed addr linkage1730 // and are constants, then it should be an auto hide symbol. In that case1731 // the thin link would have marked it as CanAutoHide. Add hidden1732 // visibility to the symbol to preserve the property.1733 if (NewLinkage == GlobalValue::WeakODRLinkage &&1734 GS->second->canAutoHide()) {1735 assert(GV.canBeOmittedFromSymbolTable());1736 GV.setVisibility(GlobalValue::HiddenVisibility);1737 }1738 1739 LLVM_DEBUG(dbgs() << "ODR fixing up linkage for `" << GV.getName()1740 << "` from " << GV.getLinkage() << " to " << NewLinkage1741 << "\n");1742 GV.setLinkage(NewLinkage);1743 }1744 // Remove declarations from comdats, including available_externally1745 // as this is a declaration for the linker, and will be dropped eventually.1746 // It is illegal for comdats to contain declarations.1747 auto *GO = dyn_cast_or_null<GlobalObject>(&GV);1748 if (GO && GO->isDeclarationForLinker() && GO->hasComdat()) {1749 if (GO->getComdat()->getName() == GO->getName())1750 NonPrevailingComdats.insert(GO->getComdat());1751 GO->setComdat(nullptr);1752 }1753 };1754 1755 // Process functions and global now1756 for (auto &GV : TheModule)1757 FinalizeInModule(GV, PropagateAttrs);1758 for (auto &GV : TheModule.globals())1759 FinalizeInModule(GV);1760 for (auto &GV : TheModule.aliases())1761 FinalizeInModule(GV);1762 1763 // For a non-prevailing comdat, all its members must be available_externally.1764 // FinalizeInModule has handled non-local-linkage GlobalValues. Here we handle1765 // local linkage GlobalValues.1766 if (NonPrevailingComdats.empty())1767 return;1768 for (auto &GO : TheModule.global_objects()) {1769 if (auto *C = GO.getComdat(); C && NonPrevailingComdats.count(C)) {1770 GO.setComdat(nullptr);1771 GO.setLinkage(GlobalValue::AvailableExternallyLinkage);1772 }1773 }1774 bool Changed;1775 do {1776 Changed = false;1777 // If an alias references a GlobalValue in a non-prevailing comdat, change1778 // it to available_externally. For simplicity we only handle GlobalValue and1779 // ConstantExpr with a base object. ConstantExpr without a base object is1780 // unlikely used in a COMDAT.1781 for (auto &GA : TheModule.aliases()) {1782 if (GA.hasAvailableExternallyLinkage())1783 continue;1784 GlobalObject *Obj = GA.getAliaseeObject();1785 assert(Obj && "aliasee without an base object is unimplemented");1786 if (Obj->hasAvailableExternallyLinkage()) {1787 GA.setLinkage(GlobalValue::AvailableExternallyLinkage);1788 Changed = true;1789 }1790 }1791 } while (Changed);1792}1793 1794/// Run internalization on \p TheModule based on symmary analysis.1795void llvm::thinLTOInternalizeModule(Module &TheModule,1796 const GVSummaryMapTy &DefinedGlobals) {1797 llvm::TimeTraceScope timeScope("ThinLTO internalize module");1798 // Declare a callback for the internalize pass that will ask for every1799 // candidate GlobalValue if it can be internalized or not.1800 auto MustPreserveGV = [&](const GlobalValue &GV) -> bool {1801 // It may be the case that GV is on a chain of an ifunc, its alias and1802 // subsequent aliases. In this case, the summary for the value is not1803 // available.1804 if (isa<GlobalIFunc>(&GV) ||1805 (isa<GlobalAlias>(&GV) &&1806 isa<GlobalIFunc>(cast<GlobalAlias>(&GV)->getAliaseeObject())))1807 return true;1808 1809 // Lookup the linkage recorded in the summaries during global analysis.1810 auto GS = DefinedGlobals.find(GV.getGUID());1811 if (GS == DefinedGlobals.end()) {1812 // Must have been promoted (possibly conservatively). Find original1813 // name so that we can access the correct summary and see if it can1814 // be internalized again.1815 // FIXME: Eventually we should control promotion instead of promoting1816 // and internalizing again.1817 StringRef OrigName =1818 ModuleSummaryIndex::getOriginalNameBeforePromote(GV.getName());1819 std::string OrigId = GlobalValue::getGlobalIdentifier(1820 OrigName, GlobalValue::InternalLinkage,1821 TheModule.getSourceFileName());1822 GS = DefinedGlobals.find(1823 GlobalValue::getGUIDAssumingExternalLinkage(OrigId));1824 if (GS == DefinedGlobals.end()) {1825 // Also check the original non-promoted non-globalized name. In some1826 // cases a preempted weak value is linked in as a local copy because1827 // it is referenced by an alias (IRLinker::linkGlobalValueProto).1828 // In that case, since it was originally not a local value, it was1829 // recorded in the index using the original name.1830 // FIXME: This may not be needed once PR27866 is fixed.1831 GS = DefinedGlobals.find(1832 GlobalValue::getGUIDAssumingExternalLinkage(OrigName));1833 assert(GS != DefinedGlobals.end());1834 }1835 }1836 return !GlobalValue::isLocalLinkage(GS->second->linkage());1837 };1838 1839 // FIXME: See if we can just internalize directly here via linkage changes1840 // based on the index, rather than invoking internalizeModule.1841 internalizeModule(TheModule, MustPreserveGV);1842}1843 1844/// Make alias a clone of its aliasee.1845static Function *replaceAliasWithAliasee(Module *SrcModule, GlobalAlias *GA) {1846 Function *Fn = cast<Function>(GA->getAliaseeObject());1847 1848 ValueToValueMapTy VMap;1849 Function *NewFn = CloneFunction(Fn, VMap);1850 // Clone should use the original alias's linkage, visibility and name, and we1851 // ensure all uses of alias instead use the new clone (casted if necessary).1852 NewFn->setLinkage(GA->getLinkage());1853 NewFn->setVisibility(GA->getVisibility());1854 GA->replaceAllUsesWith(NewFn);1855 NewFn->takeName(GA);1856 return NewFn;1857}1858 1859// Internalize values that we marked with specific attribute1860// in processGlobalForThinLTO.1861static void internalizeGVsAfterImport(Module &M) {1862 for (auto &GV : M.globals())1863 // Skip GVs which have been converted to declarations1864 // by dropDeadSymbols.1865 if (!GV.isDeclaration() && GV.hasAttribute("thinlto-internalize")) {1866 GV.setLinkage(GlobalValue::InternalLinkage);1867 GV.setVisibility(GlobalValue::DefaultVisibility);1868 }1869}1870 1871// Automatically import functions in Module \p DestModule based on the summaries1872// index.1873Expected<bool> FunctionImporter::importFunctions(1874 Module &DestModule, const FunctionImporter::ImportMapTy &ImportList) {1875 LLVM_DEBUG(dbgs() << "Starting import for Module "1876 << DestModule.getModuleIdentifier() << "\n");1877 unsigned ImportedCount = 0, ImportedGVCount = 0;1878 // Before carrying out any imports, see if this module defines functions in1879 // MoveSymbolGUID. If it does, delete them here (but leave the declaration).1880 // The function will be imported elsewhere, as extenal linkage, and the1881 // destination doesn't yet have its definition.1882 DenseSet<GlobalValue::GUID> MoveSymbolGUIDSet;1883 MoveSymbolGUIDSet.insert_range(MoveSymbolGUID);1884 for (auto &F : DestModule)1885 if (!F.isDeclaration() && MoveSymbolGUIDSet.contains(F.getGUID()))1886 F.deleteBody();1887 1888 IRMover Mover(DestModule);1889 1890 // Do the actual import of functions now, one Module at a time1891 for (const auto &ModName : ImportList.getSourceModules()) {1892 llvm::TimeTraceScope timeScope("Import", ModName);1893 // Get the module for the import1894 Expected<std::unique_ptr<Module>> SrcModuleOrErr = ModuleLoader(ModName);1895 if (!SrcModuleOrErr)1896 return SrcModuleOrErr.takeError();1897 std::unique_ptr<Module> SrcModule = std::move(*SrcModuleOrErr);1898 assert(&DestModule.getContext() == &SrcModule->getContext() &&1899 "Context mismatch");1900 1901 // If modules were created with lazy metadata loading, materialize it1902 // now, before linking it (otherwise this will be a noop).1903 if (Error Err = SrcModule->materializeMetadata())1904 return std::move(Err);1905 1906 // Find the globals to import1907 SetVector<GlobalValue *> GlobalsToImport;1908 {1909 llvm::TimeTraceScope functionsScope("Functions");1910 for (Function &F : *SrcModule) {1911 if (!F.hasName())1912 continue;1913 auto GUID = F.getGUID();1914 auto MaybeImportType = ImportList.getImportType(ModName, GUID);1915 bool ImportDefinition =1916 MaybeImportType == GlobalValueSummary::Definition;1917 1918 LLVM_DEBUG(dbgs() << (MaybeImportType ? "Is" : "Not")1919 << " importing function"1920 << (ImportDefinition1921 ? " definition "1922 : (MaybeImportType ? " declaration " : " "))1923 << GUID << " " << F.getName() << " from "1924 << SrcModule->getSourceFileName() << "\n");1925 if (ImportDefinition) {1926 if (Error Err = F.materialize())1927 return std::move(Err);1928 // MemProf should match function's definition and summary,1929 // 'thinlto_src_module' is needed.1930 if (EnableImportMetadata || EnableMemProfContextDisambiguation) {1931 // Add 'thinlto_src_module' and 'thinlto_src_file' metadata for1932 // statistics and debugging.1933 F.setMetadata(1934 "thinlto_src_module",1935 MDNode::get(DestModule.getContext(),1936 {MDString::get(DestModule.getContext(),1937 SrcModule->getModuleIdentifier())}));1938 F.setMetadata(1939 "thinlto_src_file",1940 MDNode::get(DestModule.getContext(),1941 {MDString::get(DestModule.getContext(),1942 SrcModule->getSourceFileName())}));1943 }1944 GlobalsToImport.insert(&F);1945 }1946 }1947 }1948 {1949 llvm::TimeTraceScope globalsScope("Globals");1950 for (GlobalVariable &GV : SrcModule->globals()) {1951 if (!GV.hasName())1952 continue;1953 auto GUID = GV.getGUID();1954 auto MaybeImportType = ImportList.getImportType(ModName, GUID);1955 bool ImportDefinition =1956 MaybeImportType == GlobalValueSummary::Definition;1957 1958 LLVM_DEBUG(dbgs() << (MaybeImportType ? "Is" : "Not")1959 << " importing global"1960 << (ImportDefinition1961 ? " definition "1962 : (MaybeImportType ? " declaration " : " "))1963 << GUID << " " << GV.getName() << " from "1964 << SrcModule->getSourceFileName() << "\n");1965 if (ImportDefinition) {1966 if (Error Err = GV.materialize())1967 return std::move(Err);1968 ImportedGVCount += GlobalsToImport.insert(&GV);1969 }1970 }1971 }1972 {1973 llvm::TimeTraceScope aliasesScope("Aliases");1974 for (GlobalAlias &GA : SrcModule->aliases()) {1975 if (!GA.hasName() || isa<GlobalIFunc>(GA.getAliaseeObject()))1976 continue;1977 auto GUID = GA.getGUID();1978 auto MaybeImportType = ImportList.getImportType(ModName, GUID);1979 bool ImportDefinition =1980 MaybeImportType == GlobalValueSummary::Definition;1981 1982 LLVM_DEBUG(dbgs() << (MaybeImportType ? "Is" : "Not")1983 << " importing alias"1984 << (ImportDefinition1985 ? " definition "1986 : (MaybeImportType ? " declaration " : " "))1987 << GUID << " " << GA.getName() << " from "1988 << SrcModule->getSourceFileName() << "\n");1989 if (ImportDefinition) {1990 if (Error Err = GA.materialize())1991 return std::move(Err);1992 // Import alias as a copy of its aliasee.1993 GlobalObject *GO = GA.getAliaseeObject();1994 if (Error Err = GO->materialize())1995 return std::move(Err);1996 auto *Fn = replaceAliasWithAliasee(SrcModule.get(), &GA);1997 LLVM_DEBUG(dbgs() << "Is importing aliasee fn " << GO->getGUID()1998 << " " << GO->getName() << " from "1999 << SrcModule->getSourceFileName() << "\n");2000 if (EnableImportMetadata || EnableMemProfContextDisambiguation) {2001 // Add 'thinlto_src_module' and 'thinlto_src_file' metadata for2002 // statistics and debugging.2003 Fn->setMetadata(2004 "thinlto_src_module",2005 MDNode::get(DestModule.getContext(),2006 {MDString::get(DestModule.getContext(),2007 SrcModule->getModuleIdentifier())}));2008 Fn->setMetadata(2009 "thinlto_src_file",2010 MDNode::get(DestModule.getContext(),2011 {MDString::get(DestModule.getContext(),2012 SrcModule->getSourceFileName())}));2013 }2014 GlobalsToImport.insert(Fn);2015 }2016 }2017 }2018 2019 // Upgrade debug info after we're done materializing all the globals and we2020 // have loaded all the required metadata!2021 UpgradeDebugInfo(*SrcModule);2022 2023 // Set the partial sample profile ratio in the profile summary module flag2024 // of the imported source module, if applicable, so that the profile summary2025 // module flag will match with that of the destination module when it's2026 // imported.2027 SrcModule->setPartialSampleProfileRatio(Index);2028 2029 // Link in the specified functions.2030 renameModuleForThinLTO(*SrcModule, Index, ClearDSOLocalOnDeclarations,2031 &GlobalsToImport);2032 2033 if (PrintImports) {2034 for (const auto *GV : GlobalsToImport)2035 dbgs() << DestModule.getSourceFileName() << ": Import " << GV->getName()2036 << " from " << SrcModule->getSourceFileName() << "\n";2037 }2038 2039 if (Error Err = Mover.move(std::move(SrcModule),2040 GlobalsToImport.getArrayRef(), nullptr,2041 /*IsPerformingImport=*/true))2042 return createStringError(errc::invalid_argument,2043 Twine("Function Import: link error: ") +2044 toString(std::move(Err)));2045 2046 ImportedCount += GlobalsToImport.size();2047 NumImportedModules++;2048 }2049 2050 internalizeGVsAfterImport(DestModule);2051 2052 NumImportedFunctions += (ImportedCount - ImportedGVCount);2053 NumImportedGlobalVars += ImportedGVCount;2054 2055 // TODO: Print counters for definitions and declarations in the debugging log.2056 LLVM_DEBUG(dbgs() << "Imported " << ImportedCount - ImportedGVCount2057 << " functions for Module "2058 << DestModule.getModuleIdentifier() << "\n");2059 LLVM_DEBUG(dbgs() << "Imported " << ImportedGVCount2060 << " global variables for Module "2061 << DestModule.getModuleIdentifier() << "\n");2062 return ImportedCount;2063}2064 2065static bool doImportingForModuleForTest(2066 Module &M, function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>2067 isPrevailing) {2068 if (SummaryFile.empty())2069 report_fatal_error("error: -function-import requires -summary-file\n");2070 Expected<std::unique_ptr<ModuleSummaryIndex>> IndexPtrOrErr =2071 getModuleSummaryIndexForFile(SummaryFile);2072 if (!IndexPtrOrErr) {2073 logAllUnhandledErrors(IndexPtrOrErr.takeError(), errs(),2074 "Error loading file '" + SummaryFile + "': ");2075 return false;2076 }2077 std::unique_ptr<ModuleSummaryIndex> Index = std::move(*IndexPtrOrErr);2078 2079 // First step is collecting the import list.2080 FunctionImporter::ImportIDTable ImportIDs;2081 FunctionImporter::ImportMapTy ImportList(ImportIDs);2082 // If requested, simply import all functions in the index. This is used2083 // when testing distributed backend handling via the opt tool, when2084 // we have distributed indexes containing exactly the summaries to import.2085 if (ImportAllIndex)2086 ComputeCrossModuleImportForModuleFromIndexForTest(M.getModuleIdentifier(),2087 *Index, ImportList);2088 else2089 ComputeCrossModuleImportForModuleForTest(M.getModuleIdentifier(),2090 isPrevailing, *Index, ImportList);2091 2092 // Conservatively mark all internal values as promoted. This interface is2093 // only used when doing importing via the function importing pass. The pass2094 // is only enabled when testing importing via the 'opt' tool, which does2095 // not do the ThinLink that would normally determine what values to promote.2096 for (auto &I : *Index) {2097 for (auto &S : I.second.getSummaryList()) {2098 if (GlobalValue::isLocalLinkage(S->linkage()))2099 S->setLinkage(GlobalValue::ExternalLinkage);2100 }2101 }2102 2103 // Next we need to promote to global scope and rename any local values that2104 // are potentially exported to other modules.2105 renameModuleForThinLTO(M, *Index, /*ClearDSOLocalOnDeclarations=*/false,2106 /*GlobalsToImport=*/nullptr);2107 2108 // Perform the import now.2109 auto ModuleLoader = [&M](StringRef Identifier) {2110 return loadFile(std::string(Identifier), M.getContext());2111 };2112 FunctionImporter Importer(*Index, ModuleLoader,2113 /*ClearDSOLocalOnDeclarations=*/false);2114 Expected<bool> Result = Importer.importFunctions(M, ImportList);2115 2116 // FIXME: Probably need to propagate Errors through the pass manager.2117 if (!Result) {2118 logAllUnhandledErrors(Result.takeError(), errs(),2119 "Error importing module: ");2120 return true;2121 }2122 2123 return true;2124}2125 2126PreservedAnalyses FunctionImportPass::run(Module &M,2127 ModuleAnalysisManager &AM) {2128 // This is only used for testing the function import pass via opt, where we2129 // don't have prevailing information from the LTO context available, so just2130 // conservatively assume everything is prevailing (which is fine for the very2131 // limited use of prevailing checking in this pass).2132 auto isPrevailing = [](GlobalValue::GUID, const GlobalValueSummary *) {2133 return true;2134 };2135 if (!doImportingForModuleForTest(M, isPrevailing))2136 return PreservedAnalyses::all();2137 2138 return PreservedAnalyses::none();2139}2140