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-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements Function import based on summaries.
10//
11//===----------------------------------------------------------------------===//
12
13#include "llvm/Transforms/IPO/FunctionImport.h"
14#include "IPOOptions.h"
15#include "llvm/ADT/ArrayRef.h"
16#include "llvm/ADT/DenseMap.h"
17#include "llvm/ADT/STLExtras.h"
18#include "llvm/ADT/SetVector.h"
19#include "llvm/ADT/SmallVector.h"
20#include "llvm/ADT/Statistic.h"
21#include "llvm/ADT/StringRef.h"
22#include "llvm/Bitcode/BitcodeReader.h"
23#include "llvm/IR/AutoUpgrade.h"
24#include "llvm/IR/Constants.h"
25#include "llvm/IR/Function.h"
26#include "llvm/IR/GlobalAlias.h"
27#include "llvm/IR/GlobalObject.h"
28#include "llvm/IR/GlobalValue.h"
29#include "llvm/IR/GlobalVariable.h"
30#include "llvm/IR/LLVMContext.h"
31#include "llvm/IR/Metadata.h"
32#include "llvm/IR/Module.h"
33#include "llvm/IR/ModuleSummaryIndex.h"
34#include "llvm/IRReader/IRReader.h"
35#include "llvm/Linker/IRMover.h"
36#include "llvm/ProfileData/PGOCtxProfReader.h"
37#include "llvm/Support/Casting.h"
38#include "llvm/Support/CommandLine.h"
39#include "llvm/Support/Debug.h"
40#include "llvm/Support/Errc.h"
41#include "llvm/Support/Error.h"
42#include "llvm/Support/ErrorHandling.h"
43#include "llvm/Support/FileSystem.h"
44#include "llvm/Support/JSON.h"
45#include "llvm/Support/Path.h"
46#include "llvm/Support/SourceMgr.h"
47#include "llvm/Support/TimeProfiler.h"
48#include "llvm/Support/raw_ostream.h"
49#include "llvm/Transforms/IPO/Internalize.h"
50#include "llvm/Transforms/Utils/Cloning.h"
51#include "llvm/Transforms/Utils/FunctionImportUtils.h"
52#include "llvm/Transforms/Utils/ModuleUtils.h"
53#include "llvm/Transforms/Utils/ValueMapper.h"
54#include <cassert>
55#include <memory>
56#include <string>
57#include <system_error>
58#include <tuple>
59#include <utility>
60
61using namespace llvm;
62
63#define DEBUG_TYPE "function-import"
64
65STATISTIC(NumImportedFunctionsThinLink,
66 "Number of functions thin link decided to import");
67STATISTIC(NumImportedHotFunctionsThinLink,
68 "Number of hot functions thin link decided to import");
69STATISTIC(NumImportedCriticalFunctionsThinLink,
70 "Number of critical functions thin link decided to import");
71STATISTIC(NumImportedGlobalVarsThinLink,
72 "Number of global variables thin link decided to import");
73STATISTIC(NumImportedFunctions, "Number of functions imported in backend");
74STATISTIC(NumRequiredDeclsThinLink,
75 "Number of function declarations thin link decided to import because "
76 "the callee is required in the caller's module (e.g. for MemProf "
77 "ICP)");
78STATISTIC(NumImportedFunctionDecls,
79 "Number of function declarations imported in backend");
80STATISTIC(NumImportedGlobalVars,
81 "Number of global variables imported in backend");
82STATISTIC(NumImportedModules, "Number of modules imported from");
83STATISTIC(NumDeadSymbols, "Number of dead stripped symbols in index");
84STATISTIC(NumLiveSymbols, "Number of live symbols in index");
85
86namespace llvm {
87extern cl::opt<bool> AlwaysRenamePromotedLocals;
88
89cl::opt<bool>
90 ForceImportAll("force-import-all", cl::init(Val: false), cl::Hidden,
91 cl::desc("Import functions with noinline attribute"));
92
93/// Limit on instruction count of imported functions.
94static cl::opt<unsigned> ImportInstrLimit(
95 "import-instr-limit", cl::init(Val: 100), cl::Hidden, cl::value_desc("N"),
96 cl::desc("Only import functions with less than N instructions"));
97
98static cl::opt<int> ImportCutoff(
99 "import-cutoff", cl::init(Val: -1), cl::Hidden, cl::value_desc("N"),
100 cl::desc("Only import first N functions if N>=0 (default -1)"));
101
102static cl::opt<float>
103 ImportInstrFactor("import-instr-evolution-factor", cl::init(Val: 0.7),
104 cl::Hidden, cl::value_desc("x"),
105 cl::desc("As we import functions, multiply the "
106 "`import-instr-limit` threshold by this factor "
107 "before processing newly imported functions"));
108
109static cl::opt<float> ImportHotInstrFactor(
110 "import-hot-evolution-factor", cl::init(Val: 1.0), cl::Hidden,
111 cl::value_desc("x"),
112 cl::desc("As we import functions called from hot callsite, multiply the "
113 "`import-instr-limit` threshold by this factor "
114 "before processing newly imported functions"));
115
116static cl::opt<float> ImportHotMultiplier(
117 "import-hot-multiplier", cl::init(Val: 10.0), cl::Hidden, cl::value_desc("x"),
118 cl::desc("Multiply the `import-instr-limit` threshold for hot callsites"));
119
120static cl::opt<float> ImportCriticalMultiplier(
121 "import-critical-multiplier", cl::init(Val: 100.0), cl::Hidden,
122 cl::value_desc("x"),
123 cl::desc(
124 "Multiply the `import-instr-limit` threshold for critical callsites"));
125
126// FIXME: This multiplier was not really tuned up.
127static cl::opt<float> ImportColdMultiplier(
128 "import-cold-multiplier", cl::init(Val: 0), cl::Hidden, cl::value_desc("N"),
129 cl::desc("Multiply the `import-instr-limit` threshold for cold callsites"));
130
131static cl::opt<bool> PrintImportFailures(
132 "print-import-failures", cl::init(Val: false), cl::Hidden,
133 cl::desc("Print information for functions rejected for importing"));
134
135static cl::opt<bool> ComputeDead("compute-dead", cl::init(Val: true), cl::Hidden,
136 cl::desc("Compute dead symbols"));
137
138/// This is a test-only option.
139/// If this option is enabled, the ThinLTO indexing step will import each
140/// function declaration as a fallback. In a real build this may increase ram
141/// usage of the indexing step unnecessarily.
142/// TODO: Implement selective import (based on combined summary analysis) to
143/// ensure the imported function has a use case in the postlink pipeline.
144static cl::opt<bool> ImportDeclaration(
145 "import-declaration", cl::init(Val: false), cl::Hidden,
146 cl::desc("If true, import function declaration as fallback if the function "
147 "definition is not imported."));
148
149/// Narrower form of -import-declaration for indirect call promotion: when the
150/// definition of a profiled indirect call target is not imported, import its
151/// declaration and export it from its defining module, so that the backend can
152/// promote the indirect call to it (see -icp-allow-decls).
153static cl::opt<bool> ImportDeclarationForIndirectCalls(
154 "import-declaration-for-indirect-calls", cl::init(Val: false), cl::Hidden,
155 cl::desc("If true, import a declaration of the target of an indirect call "
156 "edge (and export it from its defining module) when its "
157 "definition is not imported."));
158
159static cl::opt<CalleeInfo::HotnessType>
160 ImportDeclarationForIndirectCallsMinHotness(
161 "import-declaration-for-indirect-calls-min-hotness",
162 cl::init(Val: CalleeInfo::HotnessType::Hot), cl::Hidden,
163 cl::desc("Minimum hotness of an indirect call edge for "
164 "-import-declaration-for-indirect-calls to import a "
165 "declaration of its target."),
166 cl::values(clEnumValN(CalleeInfo::HotnessType::Unknown, "unknown",
167 "Any edge, including ones without profile"),
168 clEnumValN(CalleeInfo::HotnessType::Cold, "cold",
169 "Cold or hotter edges"),
170 clEnumValN(CalleeInfo::HotnessType::None, "none",
171 "Edges that are not cold"),
172 clEnumValN(CalleeInfo::HotnessType::Hot, "hot",
173 "Hot or critical edges"),
174 clEnumValN(CalleeInfo::HotnessType::Critical, "critical",
175 "Critical edges only")));
176
177/// Pass a workload description file - an example of workload would be the
178/// functions executed to satisfy a RPC request. A workload is defined by a root
179/// function and the list of functions that are (frequently) needed to satisfy
180/// it. The module that defines the root will have all those functions imported.
181/// The file contains a JSON dictionary. The keys are root functions, the values
182/// are lists of functions to import in the module defining the root. It is
183/// assumed -funique-internal-linkage-names was used, thus ensuring function
184/// names are unique even for local linkage ones.
185static cl::opt<std::string> WorkloadDefinitions(
186 "thinlto-workload-def",
187 cl::desc("Pass a workload definition. This is a file containing a JSON "
188 "dictionary. The keys are root functions, the values are lists of "
189 "functions to import in the module defining the root. It is "
190 "assumed -funique-internal-linkage-names was used, to ensure "
191 "local linkage functions have unique names. For example: \n"
192 "{\n"
193 " \"rootFunction_1\": [\"function_to_import_1\", "
194 "\"function_to_import_2\"], \n"
195 " \"rootFunction_2\": [\"function_to_import_3\", "
196 "\"function_to_import_4\"] \n"
197 "}"),
198 cl::Hidden);
199
200extern cl::opt<std::string> UseCtxProfile;
201
202static cl::opt<bool> CtxprofMoveRootsToOwnModule(
203 "thinlto-move-ctxprof-trees",
204 cl::desc("Move contextual profiling roots and the graphs under them in "
205 "their own module."),
206 cl::Hidden, cl::init(Val: false));
207
208extern cl::list<GlobalValue::GUID> MoveSymbolGUID;
209
210extern cl::opt<bool> EnableMemProfContextDisambiguation;
211} // end namespace llvm
212
213// Load lazily a module from \p FileName in \p Context.
214static std::unique_ptr<Module> loadFile(const std::string &FileName,
215 LLVMContext &Context) {
216 SMDiagnostic Err;
217 LLVM_DEBUG(dbgs() << "Loading '" << FileName << "'\n");
218 // Metadata isn't loaded until functions are imported, to minimize
219 // the memory overhead.
220 std::unique_ptr<Module> Result =
221 getLazyIRFileModule(Filename: FileName, Err, Context,
222 /* ShouldLazyLoadMetadata = */ true);
223 if (!Result) {
224 Err.print(ProgName: "function-import", S&: errs());
225 report_fatal_error(reason: "Abort");
226 }
227
228 return Result;
229}
230
231static bool shouldSkipLocalInAnotherModule(const GlobalValueSummary *RefSummary,
232 size_t NumDefs,
233 StringRef ImporterModule) {
234 // We can import a local when there is one definition.
235 if (NumDefs == 1)
236 return false;
237 // In other cases, make sure we import the copy in the caller's module if the
238 // referenced value has local linkage. The only time a local variable can
239 // share an entry in the index is if there is a local with the same name in
240 // another module that had the same source file name (in a different
241 // directory), where each was compiled in their own directory so there was not
242 // distinguishing path.
243 return GlobalValue::isLocalLinkage(Linkage: RefSummary->linkage()) &&
244 RefSummary->modulePath() != ImporterModule;
245}
246
247/// Given a list of possible callee implementation for a call site, qualify the
248/// legality of importing each. The return is a range of pairs. Each pair
249/// corresponds to a candidate. The first value is the ImportFailureReason for
250/// that candidate, the second is the candidate.
251static auto qualifyCalleeCandidates(
252 const ModuleSummaryIndex &Index,
253 ArrayRef<std::unique_ptr<GlobalValueSummary>> CalleeSummaryList,
254 StringRef CallerModulePath) {
255 return llvm::map_range(
256 C&: CalleeSummaryList,
257 F: [&Index, CalleeSummaryList,
258 CallerModulePath](const std::unique_ptr<GlobalValueSummary> &SummaryPtr)
259 -> std::pair<FunctionImporter::ImportFailureReason,
260 const GlobalValueSummary *> {
261 auto *GVSummary = SummaryPtr.get();
262 if (!Index.isGlobalValueLive(GVS: GVSummary))
263 return {FunctionImporter::ImportFailureReason::NotLive, GVSummary};
264
265 if (GlobalValue::isInterposableLinkage(Linkage: GVSummary->linkage()))
266 return {FunctionImporter::ImportFailureReason::InterposableLinkage,
267 GVSummary};
268
269 auto *Summary = dyn_cast<FunctionSummary>(Val: GVSummary->getBaseObject());
270
271 // Ignore any callees that aren't actually functions. This could happen
272 // in the case of GUID hash collisions. It could also happen in theory
273 // for SamplePGO profiles collected on old versions of the code after
274 // renaming, since we synthesize edges to any inlined callees appearing
275 // in the profile.
276 if (!Summary)
277 return {FunctionImporter::ImportFailureReason::GlobalVar, GVSummary};
278
279 // If this is a local function, make sure we import the copy in the
280 // caller's module. The only time a local function can share an entry in
281 // the index is if there is a local with the same name in another module
282 // that had the same source file name (in a different directory), where
283 // each was compiled in their own directory so there was not
284 // distinguishing path.
285 // If the local function is from another module, it must be a reference
286 // due to indirect call profile data since a function pointer can point
287 // to a local in another module. Do the import from another module if
288 // there is only one entry in the list or when all files in the program
289 // are compiled with full path - in both cases the local function has
290 // unique PGO name and GUID.
291 if (shouldSkipLocalInAnotherModule(RefSummary: Summary, NumDefs: CalleeSummaryList.size(),
292 ImporterModule: CallerModulePath))
293 return {
294 FunctionImporter::ImportFailureReason::LocalLinkageNotInModule,
295 GVSummary};
296
297 // Skip if it isn't legal to import (e.g. may reference unpromotable
298 // locals).
299 if (Summary->notEligibleToImport())
300 return {FunctionImporter::ImportFailureReason::NotEligible,
301 GVSummary};
302
303 return {FunctionImporter::ImportFailureReason::None, GVSummary};
304 });
305}
306
307/// Given a list of possible callee implementation for a call site, select one
308/// that fits the \p Threshold for function definition import. If none are
309/// found, the Reason will give the last reason for the failure (last, in the
310/// order of CalleeSummaryList entries). While looking for a callee definition,
311/// sets \p TooLargeOrNoInlineSummary to the last seen too-large or noinline
312/// candidate; other modules may want to know the function summary or
313/// declaration even if a definition is not needed.
314///
315/// FIXME: select "best" instead of first that fits. But what is "best"?
316/// - The smallest: more likely to be inlined.
317/// - The one with the least outgoing edges (already well optimized).
318/// - One from a module already being imported from in order to reduce the
319/// number of source modules parsed/linked.
320/// - One that has PGO data attached.
321/// - [insert you fancy metric here]
322static const GlobalValueSummary *
323selectCallee(const ModuleSummaryIndex &Index,
324 ArrayRef<std::unique_ptr<GlobalValueSummary>> CalleeSummaryList,
325 unsigned Threshold, StringRef CallerModulePath,
326 const GlobalValueSummary *&TooLargeOrNoInlineSummary,
327 FunctionImporter::ImportFailureReason &Reason) {
328 // Records the last summary with reason noinline or too-large.
329 TooLargeOrNoInlineSummary = nullptr;
330 auto QualifiedCandidates =
331 qualifyCalleeCandidates(Index, CalleeSummaryList, CallerModulePath);
332 for (auto QualifiedValue : QualifiedCandidates) {
333 Reason = QualifiedValue.first;
334 // Skip a summary if its import is not (proved to be) legal.
335 if (Reason != FunctionImporter::ImportFailureReason::None)
336 continue;
337 auto *Summary =
338 cast<FunctionSummary>(Val: QualifiedValue.second->getBaseObject());
339
340 // Don't bother importing the definition if the chance of inlining it is
341 // not high enough (except under `--force-import-all`).
342 if ((Summary->instCount() > Threshold) && !Summary->fflags().AlwaysInline &&
343 !ForceImportAll) {
344 TooLargeOrNoInlineSummary = Summary;
345 Reason = FunctionImporter::ImportFailureReason::TooLarge;
346 continue;
347 }
348
349 // Don't bother importing the definition if we can't inline it anyway.
350 if (Summary->fflags().NoInline && !ForceImportAll) {
351 TooLargeOrNoInlineSummary = Summary;
352 Reason = FunctionImporter::ImportFailureReason::NoInline;
353 continue;
354 }
355
356 return Summary;
357 }
358 return nullptr;
359}
360
361namespace {
362
363using EdgeInfo = std::tuple<const FunctionSummary *, unsigned /* Threshold */>;
364
365} // anonymous namespace
366
367FunctionImporter::ImportMapTy::AddDefinitionStatus
368FunctionImporter::ImportMapTy::addDefinition(StringRef FromModule,
369 GlobalValue::GUID GUID) {
370 auto [Def, Decl] = IDs.createImportIDs(FromModule, GUID);
371 if (!Imports.insert(V: Def).second)
372 // Already there.
373 return AddDefinitionStatus::NoChange;
374
375 // Remove Decl in case it's there. Note that a definition takes precedence
376 // over a declaration for a given GUID.
377 return Imports.erase(V: Decl) ? AddDefinitionStatus::ChangedToDefinition
378 : AddDefinitionStatus::Inserted;
379}
380
381void FunctionImporter::ImportMapTy::maybeAddDeclaration(
382 StringRef FromModule, GlobalValue::GUID GUID) {
383 auto [Def, Decl] = IDs.createImportIDs(FromModule, GUID);
384 // Insert Decl only if Def is not present. Note that a definition takes
385 // precedence over a declaration for a given GUID.
386 if (!Imports.contains(V: Def))
387 Imports.insert(V: Decl);
388}
389
390SmallVector<StringRef, 0>
391FunctionImporter::ImportMapTy::getSourceModules() const {
392 SetVector<StringRef> ModuleSet;
393 for (const auto &[SrcMod, GUID, ImportType] : *this)
394 ModuleSet.insert(X: SrcMod);
395 SmallVector<StringRef, 0> Modules = ModuleSet.takeVector();
396 llvm::sort(C&: Modules);
397 return Modules;
398}
399
400std::optional<GlobalValueSummary::ImportKind>
401FunctionImporter::ImportMapTy::getImportType(StringRef FromModule,
402 GlobalValue::GUID GUID) const {
403 if (auto IDPair = IDs.getImportIDs(FromModule, GUID)) {
404 auto [Def, Decl] = *IDPair;
405 if (Imports.contains(V: Def))
406 return GlobalValueSummary::Definition;
407 if (Imports.contains(V: Decl))
408 return GlobalValueSummary::Declaration;
409 }
410 return std::nullopt;
411}
412
413/// Import globals referenced by a function or other globals that are being
414/// imported, if importing such global is possible.
415class GlobalsImporter final {
416 const ModuleSummaryIndex &Index;
417 const GVSummaryMapTy &DefinedGVSummaries;
418 function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
419 IsPrevailing;
420 FunctionImporter::ImportMapTy &ImportList;
421 DenseMap<StringRef, FunctionImporter::ExportSetTy> *const ExportLists;
422
423 bool shouldImportGlobal(const ValueInfo &VI, StringRef ReferencingModule) {
424 const auto &GVS = DefinedGVSummaries.find(Val: VI.getGUID());
425 if (GVS == DefinedGVSummaries.end())
426 return true;
427 // A local definition in the destination module cannot satisfy a reference
428 // from a different module.
429 if (shouldSkipLocalInAnotherModule(RefSummary: GVS->second, NumDefs: VI.getSummaryList().size(),
430 ImporterModule: ReferencingModule))
431 return true;
432 // We should not skip import if the module contains a non-prevailing
433 // definition with interposable linkage type. This is required for
434 // correctness in the situation where there is a prevailing def available
435 // for import and marked read-only. In this case, the non-prevailing def
436 // will be converted to a declaration, while the prevailing one becomes
437 // internal, thus no definitions will be available for linking. In order to
438 // prevent undefined symbol link error, the prevailing definition must be
439 // imported.
440 // FIXME: Consider adding a check that the suitable prevailing definition
441 // exists and marked read-only.
442 if (VI.getSummaryList().size() > 1 &&
443 GlobalValue::isInterposableLinkage(Linkage: GVS->second->linkage()) &&
444 !IsPrevailing(VI.getGUID(), GVS->second))
445 return true;
446
447 return false;
448 }
449
450 void
451 onImportingSummaryImpl(const GlobalValueSummary &Summary,
452 SmallVectorImpl<const GlobalVarSummary *> &Worklist) {
453 for (const auto &VI : Summary.refs()) {
454 if (!shouldImportGlobal(VI, ReferencingModule: Summary.modulePath())) {
455 LLVM_DEBUG(
456 dbgs() << "Ref ignored! Target already in destination module.\n");
457 continue;
458 }
459
460 LLVM_DEBUG(dbgs() << " ref -> " << VI << "\n");
461
462 for (const auto &RefSummary : VI.getSummaryList()) {
463 const auto *GVS = dyn_cast<GlobalVarSummary>(Val: RefSummary.get());
464 // Stop looking if this is not a global variable, e.g. a function.
465 // Functions could be referenced by global vars - e.g. a vtable; but we
466 // don't currently imagine a reason those would be imported here, rather
467 // than as part of the logic deciding which functions to import (i.e.
468 // based on profile information). Should we decide to handle them here,
469 // we can refactor accordingly at that time.
470 // Note that it is safe to stop looking because the one case where we
471 // might have to import (a read/write-only global variable) cannot occur
472 // if this GUID has a non-variable summary. The only case where we even
473 // might find another summary in the list that is a variable is in the
474 // case of same-named locals in different modules not compiled with
475 // enough path, and during attribute propagation we will mark all
476 // summaries for a GUID (ValueInfo) as non read/write-only if any is not
477 // a global variable.
478 if (!GVS)
479 break;
480 bool CanImportDecl = false;
481 if (shouldSkipLocalInAnotherModule(RefSummary: GVS, NumDefs: VI.getSummaryList().size(),
482 ImporterModule: Summary.modulePath()) ||
483 !Index.canImportGlobalVar(S: GVS, /* AnalyzeRefs */ true,
484 CanImportDecl)) {
485 if (ImportDeclaration && CanImportDecl)
486 ImportList.maybeAddDeclaration(FromModule: RefSummary->modulePath(),
487 GUID: VI.getGUID());
488
489 continue;
490 }
491
492 // If there isn't an entry for GUID, insert <GUID, Definition> pair.
493 // Otherwise, definition should take precedence over declaration.
494 if (ImportList.addDefinition(FromModule: RefSummary->modulePath(), GUID: VI.getGUID()) !=
495 FunctionImporter::ImportMapTy::AddDefinitionStatus::Inserted)
496 break;
497
498 // Only update stat and exports if we haven't already imported this
499 // variable.
500 NumImportedGlobalVarsThinLink++;
501 // Any references made by this variable will be marked exported
502 // later, in ComputeCrossModuleImport, after import decisions are
503 // complete, which is more efficient than adding them here.
504 if (ExportLists)
505 (*ExportLists)[RefSummary->modulePath()].insert(V: VI);
506
507 // If variable is not writeonly we attempt to recursively analyze
508 // its references in order to import referenced constants.
509 if (!Index.isWriteOnly(GVS))
510 Worklist.emplace_back(Args&: GVS);
511 break;
512 }
513 }
514 }
515
516public:
517 GlobalsImporter(
518 const ModuleSummaryIndex &Index, const GVSummaryMapTy &DefinedGVSummaries,
519 function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
520 IsPrevailing,
521 FunctionImporter::ImportMapTy &ImportList,
522 DenseMap<StringRef, FunctionImporter::ExportSetTy> *ExportLists)
523 : Index(Index), DefinedGVSummaries(DefinedGVSummaries),
524 IsPrevailing(IsPrevailing), ImportList(ImportList),
525 ExportLists(ExportLists) {}
526
527 void onImportingSummary(const GlobalValueSummary &Summary) {
528 SmallVector<const GlobalVarSummary *, 128> Worklist;
529 onImportingSummaryImpl(Summary, Worklist);
530 while (!Worklist.empty())
531 onImportingSummaryImpl(Summary: *Worklist.pop_back_val(), Worklist);
532 }
533};
534
535static const char *getFailureName(FunctionImporter::ImportFailureReason Reason);
536
537/// Determine the list of imports and exports for each module.
538class ModuleImportsManager {
539 void computeImportForFunction(
540 const FunctionSummary &Summary, unsigned Threshold,
541 const GVSummaryMapTy &DefinedGVSummaries,
542 SmallVectorImpl<EdgeInfo> &Worklist, GlobalsImporter &GVImporter,
543 FunctionImporter::ImportMapTy &ImportList,
544 FunctionImporter::ImportThresholdsTy &ImportThresholds);
545
546protected:
547 function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
548 IsPrevailing;
549 const ModuleSummaryIndex &Index;
550 DenseMap<StringRef, FunctionImporter::ExportSetTy> *const ExportLists;
551 // Values exported because a declaration of them is required in an importing
552 // module (see RequiresDeclImport in computeImportForFunction). These are
553 // tracked separately from ExportLists, as unlike values exported because of
554 // an imported definition, their own references and calls should not be
555 // exported.
556 DenseMap<StringRef, FunctionImporter::ExportSetTy> RequiredDeclExports;
557
558 ModuleImportsManager(
559 function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
560 IsPrevailing,
561 const ModuleSummaryIndex &Index,
562 DenseMap<StringRef, FunctionImporter::ExportSetTy> *ExportLists = nullptr)
563 : IsPrevailing(IsPrevailing), Index(Index), ExportLists(ExportLists) {}
564 virtual bool canImport(ValueInfo VI) { return true; }
565
566 /// Import a declaration of the callee \p VI of a call edge requiring a
567 /// declaration import (see RequiresDeclImport in computeImportForFunction),
568 /// from a function in \p CallerModulePath that is defined in or being
569 /// imported into the current module, and isn't already defined in the
570 /// current module. This is called when the callee definition is not being
571 /// imported via that edge, and the callee summaries have not already been
572 /// qualified by selectCallee (see addRequiredDeclaration). If the
573 /// definition is (or is subsequently) imported via another edge, it takes
574 /// precedence over the declaration.
575 void importRequiredDeclaration(ValueInfo VI, StringRef CallerModulePath,
576 FunctionImporter::ImportMapTy &ImportList);
577
578 /// Import a declaration of the callee \p VI from the module containing
579 /// \p DeclSummary, which must be a candidate that is legal to import (i.e.
580 /// for which qualifyCalleeCandidates returned ImportFailureReason::None, as
581 /// is the case for the SummaryForDeclImport returned by selectCallee), and
582 /// mark it exported from that module. Does nothing if the callee definition
583 /// was already imported.
584 void addRequiredDeclaration(ValueInfo VI,
585 const GlobalValueSummary *DeclSummary,
586 FunctionImporter::ImportMapTy &ImportList);
587
588public:
589 virtual ~ModuleImportsManager() = default;
590
591 /// Values that must be exported from their defining modules because
592 /// declarations of them are required in importing modules.
593 DenseMap<StringRef, FunctionImporter::ExportSetTy> &requiredDeclExports() {
594 return RequiredDeclExports;
595 }
596
597 /// Given the list of globals defined in a module, compute the list of imports
598 /// as well as the list of "exports", i.e. the list of symbols referenced from
599 /// another module (that may require promotion).
600 virtual void
601 computeImportForModule(const GVSummaryMapTy &DefinedGVSummaries,
602 StringRef ModName,
603 FunctionImporter::ImportMapTy &ImportList);
604
605 static std::unique_ptr<ModuleImportsManager>
606 create(function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
607 IsPrevailing,
608 const ModuleSummaryIndex &Index,
609 DenseMap<StringRef, FunctionImporter::ExportSetTy> *ExportLists =
610 nullptr);
611};
612
613/// A ModuleImportsManager that operates based on a workload definition (see
614/// -thinlto-workload-def). For modules that do not define workload roots, it
615/// applies the base ModuleImportsManager import policy.
616class WorkloadImportsManager : public ModuleImportsManager {
617 // Keep a module name -> value infos to import association. We use it to
618 // determine if a module's import list should be done by the base
619 // ModuleImportsManager or by us.
620 StringMap<DenseSet<ValueInfo>> Workloads;
621 // Track the roots to avoid importing them due to other callers. We want there
622 // to be only one variant), for which we optimize according to the contextual
623 // profile. "Variants" refers to copies due to importing - we want there to be
624 // just one instance of this function.
625 DenseSet<ValueInfo> Roots;
626
627 void
628 computeImportForModule(const GVSummaryMapTy &DefinedGVSummaries,
629 StringRef ModName,
630 FunctionImporter::ImportMapTy &ImportList) override {
631 StringRef Filename = ModName;
632 if (CtxprofMoveRootsToOwnModule) {
633 Filename = sys::path::filename(path: ModName);
634 // Drop the file extension.
635 Filename = Filename.substr(Start: 0, N: Filename.find_last_of(C: '.'));
636 }
637 auto SetIter = Workloads.find(Key: Filename);
638
639 if (SetIter == Workloads.end()) {
640 LLVM_DEBUG(dbgs() << "[Workload] " << ModName
641 << " does not contain the root of any context.\n");
642 return ModuleImportsManager::computeImportForModule(DefinedGVSummaries,
643 ModName, ImportList);
644 }
645 LLVM_DEBUG(dbgs() << "[Workload] " << ModName
646 << " contains the root(s) of context(s).\n");
647
648 GlobalsImporter GVI(Index, DefinedGVSummaries, IsPrevailing, ImportList,
649 ExportLists);
650 auto &ValueInfos = SetIter->second;
651 for (auto &VI : llvm::make_early_inc_range(Range&: ValueInfos)) {
652 auto It = DefinedGVSummaries.find(Val: VI.getGUID());
653 if (It != DefinedGVSummaries.end() &&
654 IsPrevailing(VI.getGUID(), It->second)) {
655 LLVM_DEBUG(
656 dbgs() << "[Workload] " << VI.name()
657 << " has the prevailing variant already in the module "
658 << ModName << ". No need to import\n");
659 continue;
660 }
661 auto Candidates =
662 qualifyCalleeCandidates(Index, CalleeSummaryList: VI.getSummaryList(), CallerModulePath: ModName);
663
664 const GlobalValueSummary *GVS = nullptr;
665 auto PotentialCandidates = llvm::map_range(
666 C: llvm::make_filter_range(
667 Range&: Candidates,
668 Pred: [&](const auto &Candidate) {
669 LLVM_DEBUG(dbgs() << "[Workflow] Candidate for " << VI.name()
670 << " from " << Candidate.second->modulePath()
671 << " ImportFailureReason: "
672 << getFailureName(Candidate.first) << "\n");
673 return Candidate.first ==
674 FunctionImporter::ImportFailureReason::None;
675 }),
676 F: [](const auto &Candidate) { return Candidate.second; });
677 if (PotentialCandidates.empty()) {
678 LLVM_DEBUG(dbgs() << "[Workload] Not importing " << VI.name()
679 << " because can't find eligible Callee. Guid is: "
680 << VI.getGUID() << "\n");
681 continue;
682 }
683 /// We will prefer importing the prevailing candidate, if not, we'll
684 /// still pick the first available candidate. The reason we want to make
685 /// sure we do import the prevailing candidate is because the goal of
686 /// workload-awareness is to enable optimizations specializing the call
687 /// graph of that workload. Suppose a function is already defined in the
688 /// module, but it's not the prevailing variant. Suppose also we do not
689 /// inline it (in fact, if it were interposable, we can't inline it),
690 /// but we could specialize it to the workload in other ways. However,
691 /// the linker would drop it in the favor of the prevailing copy.
692 /// Instead, by importing the prevailing variant (assuming also the use
693 /// of `-avail-extern-to-local`), we keep the specialization. We could
694 /// alteranatively make the non-prevailing variant local, but the
695 /// prevailing one is also the one for which we would have previously
696 /// collected profiles, making it preferrable.
697 auto PrevailingCandidates = llvm::make_filter_range(
698 Range&: PotentialCandidates, Pred: [&](const auto *Candidate) {
699 return IsPrevailing(VI.getGUID(), Candidate);
700 });
701 if (PrevailingCandidates.empty()) {
702 GVS = *PotentialCandidates.begin();
703 if (!llvm::hasSingleElement(C&: PotentialCandidates) &&
704 GlobalValue::isLocalLinkage(Linkage: GVS->linkage()))
705 LLVM_DEBUG(
706 dbgs()
707 << "[Workload] Found multiple non-prevailing candidates for "
708 << VI.name()
709 << ". This is unexpected. Are module paths passed to the "
710 "compiler unique for the modules passed to the linker?");
711 // We could in theory have multiple (interposable) copies of a symbol
712 // when there is no prevailing candidate, if say the prevailing copy was
713 // in a native object being linked in. However, we should in theory be
714 // marking all of these non-prevailing IR copies dead in that case, in
715 // which case they won't be candidates.
716 assert(GVS->isLive());
717 } else {
718 assert(llvm::hasSingleElement(PrevailingCandidates));
719 GVS = *PrevailingCandidates.begin();
720 }
721
722 auto ExportingModule = GVS->modulePath();
723 // We checked that for the prevailing case, but if we happen to have for
724 // example an internal that's defined in this module, it'd have no
725 // PrevailingCandidates.
726 if (ExportingModule == ModName) {
727 LLVM_DEBUG(dbgs() << "[Workload] Not importing " << VI.name()
728 << " because its defining module is the same as the "
729 "current module\n");
730 continue;
731 }
732 LLVM_DEBUG(dbgs() << "[Workload][Including]" << VI.name() << " from "
733 << ExportingModule << " : " << VI.getGUID() << "\n");
734 ImportList.addDefinition(FromModule: ExportingModule, GUID: VI.getGUID());
735 GVI.onImportingSummary(Summary: *GVS);
736 if (ExportLists)
737 (*ExportLists)[ExportingModule].insert(V: VI);
738 }
739 LLVM_DEBUG(dbgs() << "[Workload] Done\n");
740 }
741
742 void loadFromJson() {
743 // Since the workload def uses names, we need a quick lookup
744 // name->ValueInfo.
745 StringMap<ValueInfo> NameToValueInfo;
746 [[maybe_unused]] StringSet<> AmbiguousNames;
747 for (auto &I : Index) {
748 ValueInfo VI = Index.getValueInfo(R: I);
749 if (!NameToValueInfo.insert(KV: std::make_pair(x: VI.name(), y&: VI)).second)
750 LLVM_DEBUG(AmbiguousNames.insert(VI.name()));
751 }
752 auto DbgReportIfAmbiguous = [&](StringRef Name) {
753 LLVM_DEBUG(if (AmbiguousNames.count(Name) > 0) {
754 dbgs() << "[Workload] Function name " << Name
755 << " present in the workload definition is ambiguous. Consider "
756 "compiling with -funique-internal-linkage-names.";
757 });
758 };
759 std::error_code EC;
760 auto BufferOrErr = MemoryBuffer::getFileOrSTDIN(Filename: WorkloadDefinitions);
761 if (std::error_code EC = BufferOrErr.getError()) {
762 report_fatal_error(reason: "Failed to open context file");
763 return;
764 }
765 auto Buffer = std::move(BufferOrErr.get());
766 std::map<std::string, std::vector<std::string>> WorkloadDefs;
767 json::Path::Root NullRoot;
768 // The JSON is supposed to contain a dictionary matching the type of
769 // WorkloadDefs. For example:
770 // {
771 // "rootFunction_1": ["function_to_import_1", "function_to_import_2"],
772 // "rootFunction_2": ["function_to_import_3", "function_to_import_4"]
773 // }
774 auto Parsed = json::parse(JSON: Buffer->getBuffer());
775 if (!Parsed)
776 report_fatal_error(Err: Parsed.takeError());
777 if (!json::fromJSON(E: *Parsed, Out&: WorkloadDefs, P: NullRoot))
778 report_fatal_error(reason: "Invalid thinlto contextual profile format.");
779 for (const auto &Workload : WorkloadDefs) {
780 const auto &Root = Workload.first;
781 DbgReportIfAmbiguous(Root);
782 LLVM_DEBUG(dbgs() << "[Workload] Root: " << Root << "\n");
783 const auto &AllCallees = Workload.second;
784 auto RootIt = NameToValueInfo.find(Key: Root);
785 if (RootIt == NameToValueInfo.end()) {
786 LLVM_DEBUG(dbgs() << "[Workload] Root " << Root
787 << " not found in this linkage unit.\n");
788 continue;
789 }
790 auto RootVI = RootIt->second;
791 if (RootVI.getSummaryList().size() != 1) {
792 LLVM_DEBUG(dbgs() << "[Workload] Root " << Root
793 << " should have exactly one summary, but has "
794 << RootVI.getSummaryList().size() << ". Skipping.\n");
795 continue;
796 }
797 StringRef RootDefiningModule =
798 RootVI.getSummaryList().front()->modulePath();
799 LLVM_DEBUG(dbgs() << "[Workload] Root defining module for " << Root
800 << " is : " << RootDefiningModule << "\n");
801 auto &Set = Workloads[RootDefiningModule];
802 for (const auto &Callee : AllCallees) {
803 LLVM_DEBUG(dbgs() << "[Workload] " << Callee << "\n");
804 DbgReportIfAmbiguous(Callee);
805 auto ElemIt = NameToValueInfo.find(Key: Callee);
806 if (ElemIt == NameToValueInfo.end()) {
807 LLVM_DEBUG(dbgs() << "[Workload] " << Callee << " not found\n");
808 continue;
809 }
810 Set.insert(V: ElemIt->second);
811 }
812 }
813 }
814
815 void loadFromCtxProf() {
816 std::error_code EC;
817 auto BufferOrErr = MemoryBuffer::getFileOrSTDIN(Filename: UseCtxProfile);
818 if (std::error_code EC = BufferOrErr.getError()) {
819 report_fatal_error(reason: "Failed to open contextual profile file");
820 return;
821 }
822 auto Buffer = std::move(BufferOrErr.get());
823
824 PGOCtxProfileReader Reader(Buffer->getBuffer());
825 auto Ctx = Reader.loadProfiles();
826 if (!Ctx) {
827 report_fatal_error(reason: "Failed to parse contextual profiles");
828 return;
829 }
830 const auto &CtxMap = Ctx->Contexts;
831 SetVector<GlobalValue::GUID> ContainedGUIDs;
832 for (const auto &[RootGuid, Root] : CtxMap) {
833 // Avoid ContainedGUIDs to get in/out of scope. Reuse its memory for
834 // subsequent roots, but clear its contents.
835 ContainedGUIDs.clear();
836
837 auto RootVI = Index.getValueInfo(GUID: RootGuid);
838 if (!RootVI) {
839 LLVM_DEBUG(dbgs() << "[Workload] Root " << RootGuid
840 << " not found in this linkage unit.\n");
841 continue;
842 }
843 if (RootVI.getSummaryList().size() != 1) {
844 LLVM_DEBUG(dbgs() << "[Workload] Root " << RootGuid
845 << " should have exactly one summary, but has "
846 << RootVI.getSummaryList().size() << ". Skipping.\n");
847 continue;
848 }
849 std::string RootDefiningModule =
850 RootVI.getSummaryList().front()->modulePath().str();
851 if (CtxprofMoveRootsToOwnModule) {
852 RootDefiningModule = std::to_string(val: RootGuid);
853 LLVM_DEBUG(
854 dbgs() << "[Workload] Moving " << RootGuid
855 << " to a module with the filename without extension : "
856 << RootDefiningModule << "\n");
857 } else {
858 LLVM_DEBUG(dbgs() << "[Workload] Root defining module for " << RootGuid
859 << " is : " << RootDefiningModule << "\n");
860 }
861 auto &Set = Workloads[RootDefiningModule];
862 Root.getContainedGuids(Guids&: ContainedGUIDs);
863 Roots.insert(V: RootVI);
864 for (auto Guid : ContainedGUIDs)
865 if (auto VI = Index.getValueInfo(GUID: Guid))
866 Set.insert(V: VI);
867 }
868 }
869
870 bool canImport(ValueInfo VI) override { return !Roots.contains(V: VI); }
871
872public:
873 WorkloadImportsManager(
874 function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
875 IsPrevailing,
876 const ModuleSummaryIndex &Index,
877 DenseMap<StringRef, FunctionImporter::ExportSetTy> *ExportLists)
878 : ModuleImportsManager(IsPrevailing, Index, ExportLists) {
879 if (UseCtxProfile.empty() == WorkloadDefinitions.empty()) {
880 report_fatal_error(
881 reason: "Pass only one of: -thinlto-pgo-ctx-prof or -thinlto-workload-def");
882 return;
883 }
884 if (!UseCtxProfile.empty())
885 loadFromCtxProf();
886 else
887 loadFromJson();
888 LLVM_DEBUG({
889 for (const auto &[Root, Set] : Workloads) {
890 dbgs() << "[Workload] Root: " << Root << " we have " << Set.size()
891 << " distinct callees.\n";
892 for (const auto &VI : Set) {
893 dbgs() << "[Workload] Root: " << Root
894 << " Would include: " << VI.getGUID() << "\n";
895 }
896 }
897 });
898 }
899};
900
901std::unique_ptr<ModuleImportsManager> ModuleImportsManager::create(
902 function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
903 IsPrevailing,
904 const ModuleSummaryIndex &Index,
905 DenseMap<StringRef, FunctionImporter::ExportSetTy> *ExportLists) {
906 if (WorkloadDefinitions.empty() && UseCtxProfile.empty()) {
907 LLVM_DEBUG(dbgs() << "[Workload] Using the regular imports manager.\n");
908 return std::unique_ptr<ModuleImportsManager>(
909 new ModuleImportsManager(IsPrevailing, Index, ExportLists));
910 }
911 LLVM_DEBUG(dbgs() << "[Workload] Using the contextual imports manager.\n");
912 return std::make_unique<WorkloadImportsManager>(args&: IsPrevailing, args: Index,
913 args&: ExportLists);
914}
915
916static const char *
917getFailureName(FunctionImporter::ImportFailureReason Reason) {
918 switch (Reason) {
919 case FunctionImporter::ImportFailureReason::None:
920 return "None";
921 case FunctionImporter::ImportFailureReason::GlobalVar:
922 return "GlobalVar";
923 case FunctionImporter::ImportFailureReason::NotLive:
924 return "NotLive";
925 case FunctionImporter::ImportFailureReason::TooLarge:
926 return "TooLarge";
927 case FunctionImporter::ImportFailureReason::InterposableLinkage:
928 return "InterposableLinkage";
929 case FunctionImporter::ImportFailureReason::LocalLinkageNotInModule:
930 return "LocalLinkageNotInModule";
931 case FunctionImporter::ImportFailureReason::NotEligible:
932 return "NotEligible";
933 case FunctionImporter::ImportFailureReason::NoInline:
934 return "NoInline";
935 }
936 llvm_unreachable("invalid reason");
937}
938
939/// Compute the list of functions to import for a given caller. Mark these
940/// imported functions and the symbols they reference in their source module as
941/// exported from their source module.
942void ModuleImportsManager::computeImportForFunction(
943 const FunctionSummary &Summary, const unsigned Threshold,
944 const GVSummaryMapTy &DefinedGVSummaries,
945 SmallVectorImpl<EdgeInfo> &Worklist, GlobalsImporter &GVImporter,
946 FunctionImporter::ImportMapTy &ImportList,
947 FunctionImporter::ImportThresholdsTy &ImportThresholds) {
948 GVImporter.onImportingSummary(Summary);
949 static int ImportCount = 0;
950 for (const auto &Edge : Summary.calls()) {
951 ValueInfo VI = Edge.first;
952 LLVM_DEBUG(dbgs() << " edge -> " << VI << " Threshold:" << Threshold
953 << "\n");
954
955 // Whether at least a declaration of the callee must be imported (and the
956 // callee exported from its defining module) if its definition is not
957 // imported. This is the case when the edge was marked as requiring a
958 // declaration import (e.g. for MemProf ICP), or when declaration imports
959 // are enabled for an indirect call edge (via -import-declaration, or via
960 // -import-declaration-for-indirect-calls for edges at least as hot as
961 // -import-declaration-for-indirect-calls-min-hotness), since the backend
962 // may then promote the indirect call to the imported declaration (e.g.
963 // regular ICP under -icp-allow-decls), which requires that the callee not
964 // be internalized. Callees of direct calls don't need to be exported here,
965 // since they are either referenced directly from the destination module,
966 // in which case they are already treated as visible outside their
967 // defining module, or from an imported definition, in which case they are
968 // marked exported in ComputeCrossModuleImport.
969 const bool RequiresDeclImport =
970 Edge.second.requiresDeclImport() ||
971 (Edge.second.hasIndirectCall() &&
972 (ImportDeclaration ||
973 (ImportDeclarationForIndirectCalls &&
974 Edge.second.getHotness() >=
975 ImportDeclarationForIndirectCallsMinHotness)));
976
977 if (ImportCutoff >= 0 && ImportCount >= ImportCutoff) {
978 LLVM_DEBUG(dbgs() << "ignored! import-cutoff value of " << ImportCutoff
979 << " reached.\n");
980 // Still import a declaration if one is required, as that doesn't
981 // affect the import cutoff count.
982 if (RequiresDeclImport && !DefinedGVSummaries.count(Val: VI.getGUID()))
983 importRequiredDeclaration(VI, CallerModulePath: Summary.modulePath(), ImportList);
984 continue;
985 }
986
987 if (DefinedGVSummaries.count(Val: VI.getGUID())) {
988 // FIXME: Consider not skipping import if the module contains
989 // a non-prevailing def with interposable linkage. The prevailing copy
990 // can safely be imported (see shouldImportGlobal()).
991 LLVM_DEBUG(dbgs() << "ignored! Target already in destination module.\n");
992 continue;
993 }
994
995 if (!canImport(VI)) {
996 LLVM_DEBUG(
997 dbgs() << "Skipping over " << VI.getGUID()
998 << " because its import is handled in a different module.");
999 assert(VI.getSummaryList().size() == 1 &&
1000 "The root was expected to be an external symbol");
1001 continue;
1002 }
1003
1004 auto GetBonusMultiplier = [](CalleeInfo::HotnessType Hotness) -> float {
1005 if (Hotness == CalleeInfo::HotnessType::Hot)
1006 return ImportHotMultiplier;
1007 if (Hotness == CalleeInfo::HotnessType::Cold)
1008 return ImportColdMultiplier;
1009 if (Hotness == CalleeInfo::HotnessType::Critical)
1010 return ImportCriticalMultiplier;
1011 return 1.0;
1012 };
1013
1014 const auto NewThreshold =
1015 Threshold * GetBonusMultiplier(Edge.second.getHotness());
1016
1017 auto IT = ImportThresholds.insert(KV: std::make_pair(
1018 x: VI.getGUID(), y: std::make_tuple(args: NewThreshold, args: nullptr, args: nullptr)));
1019 bool PreviouslyVisited = !IT.second;
1020 auto &ProcessedThreshold = std::get<0>(t&: IT.first->second);
1021 auto &CalleeSummary = std::get<1>(t&: IT.first->second);
1022 auto &FailureInfo = std::get<2>(t&: IT.first->second);
1023
1024 bool IsHotCallsite =
1025 Edge.second.getHotness() == CalleeInfo::HotnessType::Hot;
1026 bool IsCriticalCallsite =
1027 Edge.second.getHotness() == CalleeInfo::HotnessType::Critical;
1028
1029 const FunctionSummary *ResolvedCalleeSummary = nullptr;
1030 if (CalleeSummary) {
1031 assert(PreviouslyVisited);
1032 // Since the traversal of the call graph is DFS, we can revisit a function
1033 // a second time with a higher threshold. In this case, it is added back
1034 // to the worklist with the new threshold (so that its own callee chains
1035 // can be considered with the higher threshold).
1036 if (NewThreshold <= ProcessedThreshold) {
1037 LLVM_DEBUG(
1038 dbgs() << "ignored! Target was already imported with Threshold "
1039 << ProcessedThreshold << "\n");
1040 continue;
1041 }
1042 // Update with new larger threshold.
1043 ProcessedThreshold = NewThreshold;
1044 ResolvedCalleeSummary = cast<FunctionSummary>(Val: CalleeSummary);
1045 } else {
1046 // If we already rejected importing a callee at the same or higher
1047 // threshold, don't waste time calling selectCallee.
1048 if (PreviouslyVisited && NewThreshold <= ProcessedThreshold) {
1049 LLVM_DEBUG(
1050 dbgs() << "ignored! Target was already rejected with Threshold "
1051 << ProcessedThreshold << "\n");
1052 if (PrintImportFailures) {
1053 assert(FailureInfo &&
1054 "Expected FailureInfo for previously rejected candidate");
1055 FailureInfo->Attempts++;
1056 }
1057 // The callee definition was rejected when reached via a different
1058 // edge, but this edge may require that a declaration be imported and
1059 // exported.
1060 if (RequiresDeclImport)
1061 importRequiredDeclaration(VI, CallerModulePath: Summary.modulePath(), ImportList);
1062 continue;
1063 }
1064
1065 FunctionImporter::ImportFailureReason Reason{};
1066
1067 // `SummaryForDeclImport` is an summary eligible for declaration import.
1068 const GlobalValueSummary *SummaryForDeclImport = nullptr;
1069 CalleeSummary =
1070 selectCallee(Index, CalleeSummaryList: VI.getSummaryList(), Threshold: NewThreshold,
1071 CallerModulePath: Summary.modulePath(), TooLargeOrNoInlineSummary&: SummaryForDeclImport, Reason);
1072 if (!CalleeSummary) {
1073 // There isn't a callee for definition import but one for declaration
1074 // import.
1075 if (SummaryForDeclImport) {
1076 if (RequiresDeclImport)
1077 // This also marks the callee exported.
1078 addRequiredDeclaration(VI, DeclSummary: SummaryForDeclImport, ImportList);
1079 else if (ImportDeclaration)
1080 // Not exported, see the comments where RequiresDeclImport is set.
1081 ImportList.maybeAddDeclaration(FromModule: SummaryForDeclImport->modulePath(),
1082 GUID: VI.getGUID());
1083 }
1084 // Update with new larger threshold if this was a retry (otherwise
1085 // we would have already inserted with NewThreshold above). Also
1086 // update failure info if requested.
1087 if (PreviouslyVisited) {
1088 ProcessedThreshold = NewThreshold;
1089 if (PrintImportFailures) {
1090 assert(FailureInfo &&
1091 "Expected FailureInfo for previously rejected candidate");
1092 FailureInfo->Reason = Reason;
1093 FailureInfo->Attempts++;
1094 FailureInfo->MaxHotness =
1095 std::max(a: FailureInfo->MaxHotness, b: Edge.second.getHotness());
1096 }
1097 } else if (PrintImportFailures) {
1098 assert(!FailureInfo &&
1099 "Expected no FailureInfo for newly rejected candidate");
1100 FailureInfo = std::make_unique<FunctionImporter::ImportFailureInfo>(
1101 args&: VI, args: Edge.second.getHotness(), args&: Reason, args: 1);
1102 }
1103 if (ForceImportAll) {
1104 std::string Msg = std::string("Failed to import function ") +
1105 VI.name().str() + " due to " +
1106 getFailureName(Reason);
1107 auto Error = make_error<StringError>(
1108 Args&: Msg, Args: make_error_code(E: errc::not_supported));
1109 logAllUnhandledErrors(E: std::move(Error), OS&: errs(),
1110 ErrorBanner: "Error importing module: ");
1111 break;
1112 } else {
1113 LLVM_DEBUG(dbgs()
1114 << "ignored! No qualifying callee with summary found.\n");
1115 continue;
1116 }
1117 }
1118
1119 // "Resolve" the summary
1120 CalleeSummary = CalleeSummary->getBaseObject();
1121 ResolvedCalleeSummary = cast<FunctionSummary>(Val: CalleeSummary);
1122
1123 assert((ResolvedCalleeSummary->fflags().AlwaysInline || ForceImportAll ||
1124 (ResolvedCalleeSummary->instCount() <= NewThreshold)) &&
1125 "selectCallee() didn't honor the threshold");
1126
1127 auto ExportModulePath = ResolvedCalleeSummary->modulePath();
1128
1129 // Try emplace the definition entry, and update stats based on insertion
1130 // status.
1131 if (ImportList.addDefinition(FromModule: ExportModulePath, GUID: VI.getGUID()) !=
1132 FunctionImporter::ImportMapTy::AddDefinitionStatus::NoChange) {
1133 NumImportedFunctionsThinLink++;
1134 if (IsHotCallsite)
1135 NumImportedHotFunctionsThinLink++;
1136 if (IsCriticalCallsite)
1137 NumImportedCriticalFunctionsThinLink++;
1138 }
1139
1140 // Any calls/references made by this function will be marked exported
1141 // later, in ComputeCrossModuleImport, after import decisions are
1142 // complete, which is more efficient than adding them here.
1143 if (ExportLists)
1144 (*ExportLists)[ExportModulePath].insert(V: VI);
1145 }
1146
1147 auto GetAdjustedThreshold = [](unsigned Threshold, bool IsHotCallsite) {
1148 // Adjust the threshold for next level of imported functions.
1149 // The threshold is different for hot callsites because we can then
1150 // inline chains of hot calls.
1151 if (IsHotCallsite)
1152 return Threshold * ImportHotInstrFactor;
1153 return Threshold * ImportInstrFactor;
1154 };
1155
1156 const auto AdjThreshold = GetAdjustedThreshold(Threshold, IsHotCallsite);
1157
1158 ImportCount++;
1159
1160 // Insert the newly imported function to the worklist.
1161 Worklist.emplace_back(Args&: ResolvedCalleeSummary, Args: AdjThreshold);
1162 }
1163}
1164
1165void ModuleImportsManager::computeImportForModule(
1166 const GVSummaryMapTy &DefinedGVSummaries, StringRef ModName,
1167 FunctionImporter::ImportMapTy &ImportList) {
1168 // Worklist contains the list of function imported in this module, for which
1169 // we will analyse the callees and may import further down the callgraph.
1170 SmallVector<EdgeInfo, 128> Worklist;
1171 GlobalsImporter GVI(Index, DefinedGVSummaries, IsPrevailing, ImportList,
1172 ExportLists);
1173 FunctionImporter::ImportThresholdsTy ImportThresholds;
1174
1175 // Populate the worklist with the import for the functions in the current
1176 // module
1177 for (const auto &GVSummary : DefinedGVSummaries) {
1178#ifndef NDEBUG
1179 // FIXME: Change the GVSummaryMapTy to hold ValueInfo instead of GUID
1180 // so this map look up (and possibly others) can be avoided.
1181 auto VI = Index.getValueInfo(GVSummary.first);
1182#endif
1183 if (!Index.isGlobalValueLive(GVS: GVSummary.second)) {
1184 LLVM_DEBUG(dbgs() << "Ignores Dead GUID: " << VI << "\n");
1185 continue;
1186 }
1187 auto *FuncSummary =
1188 dyn_cast<FunctionSummary>(Val: GVSummary.second->getBaseObject());
1189 if (!FuncSummary)
1190 // Skip import for global variables
1191 continue;
1192 LLVM_DEBUG(dbgs() << "Initialize import for " << VI << "\n");
1193 computeImportForFunction(Summary: *FuncSummary, Threshold: ImportInstrLimit, DefinedGVSummaries,
1194 Worklist, GVImporter&: GVI, ImportList, ImportThresholds);
1195 }
1196
1197 // Process the newly imported functions and add callees to the worklist.
1198 while (!Worklist.empty()) {
1199 auto GVInfo = Worklist.pop_back_val();
1200 auto *Summary = std::get<0>(t&: GVInfo);
1201 auto Threshold = std::get<1>(t&: GVInfo);
1202
1203 computeImportForFunction(Summary: *Summary, Threshold, DefinedGVSummaries, Worklist,
1204 GVImporter&: GVI, ImportList, ImportThresholds);
1205 }
1206
1207 // Print stats about functions considered but rejected for importing
1208 // when requested.
1209 if (PrintImportFailures) {
1210 dbgs() << "Missed imports into module " << ModName << "\n";
1211 for (auto &I : ImportThresholds) {
1212 auto &ProcessedThreshold = std::get<0>(t&: I.second);
1213 auto &CalleeSummary = std::get<1>(t&: I.second);
1214 auto &FailureInfo = std::get<2>(t&: I.second);
1215 if (CalleeSummary)
1216 continue; // We are going to import.
1217 assert(FailureInfo);
1218 FunctionSummary *FS = nullptr;
1219 if (!FailureInfo->VI.getSummaryList().empty())
1220 FS = dyn_cast<FunctionSummary>(
1221 Val: FailureInfo->VI.getSummaryList()[0]->getBaseObject());
1222 dbgs() << FailureInfo->VI
1223 << ": Reason = " << getFailureName(Reason: FailureInfo->Reason)
1224 << ", Threshold = " << ProcessedThreshold
1225 << ", Size = " << (FS ? (int)FS->instCount() : -1)
1226 << ", MaxHotness = " << getHotnessName(HT: FailureInfo->MaxHotness)
1227 << ", Attempts = " << FailureInfo->Attempts << "\n";
1228 }
1229 }
1230}
1231
1232void ModuleImportsManager::importRequiredDeclaration(
1233 ValueInfo VI, StringRef CallerModulePath,
1234 FunctionImporter::ImportMapTy &ImportList) {
1235 // Find a callee summary that we can legally import a declaration of. Note
1236 // that qualifyCalleeCandidates only checks the legality of importing each
1237 // candidate (returning ImportFailureReason::None if legal). The additional
1238 // size and noinline checks that determine whether it is worth importing a
1239 // definition (TooLarge/NoInline) are applied separately by selectCallee, and
1240 // are not relevant for a declaration import.
1241 for (auto [Reason, CandidateSummary] :
1242 qualifyCalleeCandidates(Index, CalleeSummaryList: VI.getSummaryList(), CallerModulePath)) {
1243 assert(Reason != FunctionImporter::ImportFailureReason::TooLarge &&
1244 Reason != FunctionImporter::ImportFailureReason::NoInline &&
1245 "Expected only legality checks in qualifyCalleeCandidates");
1246 if (Reason == FunctionImporter::ImportFailureReason::None) {
1247 addRequiredDeclaration(VI, DeclSummary: CandidateSummary, ImportList);
1248 return;
1249 }
1250 }
1251}
1252
1253void ModuleImportsManager::addRequiredDeclaration(
1254 ValueInfo VI, const GlobalValueSummary *DeclSummary,
1255 FunctionImporter::ImportMapTy &ImportList) {
1256 StringRef SrcModule = DeclSummary->modulePath();
1257 auto ExistingImportType = ImportList.getImportType(FromModule: SrcModule, GUID: VI.getGUID());
1258 // Nothing to do if we already decided to import the definition, which is
1259 // also exported.
1260 if (ExistingImportType == GlobalValueSummary::Definition)
1261 return;
1262 if (!ExistingImportType) {
1263 ImportList.maybeAddDeclaration(FromModule: SrcModule, GUID: VI.getGUID());
1264 NumRequiredDeclsThinLink++;
1265 }
1266 // The declaration needs to be exported so that the callee is not
1267 // internalized, and so that locals are promoted. Note this is needed even if
1268 // we already decided to import the declaration for another reason (i.e.
1269 // -import-declaration for a direct call edge), as those declaration imports
1270 // are not exported.
1271 if (ExportLists)
1272 RequiredDeclExports[SrcModule].insert(V: VI);
1273}
1274
1275#ifndef NDEBUG
1276static bool isGlobalVarSummary(const ModuleSummaryIndex &Index, ValueInfo VI) {
1277 auto SL = VI.getSummaryList();
1278 return SL.empty()
1279 ? false
1280 : SL[0]->getSummaryKind() == GlobalValueSummary::GlobalVarKind;
1281}
1282
1283static bool isGlobalVarSummary(const ModuleSummaryIndex &Index,
1284 GlobalValue::GUID G) {
1285 if (const auto &VI = Index.getValueInfo(G))
1286 return isGlobalVarSummary(Index, VI);
1287 return false;
1288}
1289
1290// Return the number of global variable summaries in ExportSet.
1291static unsigned
1292numGlobalVarSummaries(const ModuleSummaryIndex &Index,
1293 FunctionImporter::ExportSetTy &ExportSet) {
1294 unsigned NumGVS = 0;
1295 for (auto &VI : ExportSet)
1296 if (isGlobalVarSummary(Index, VI.getGUID()))
1297 ++NumGVS;
1298 return NumGVS;
1299}
1300
1301struct ImportStatistics {
1302 unsigned NumGVS = 0;
1303 unsigned DefinedFS = 0;
1304 unsigned Count = 0;
1305};
1306
1307// Compute import statistics for each source module in ImportList.
1308static DenseMap<StringRef, ImportStatistics>
1309collectImportStatistics(const ModuleSummaryIndex &Index,
1310 const FunctionImporter::ImportMapTy &ImportList) {
1311 DenseMap<StringRef, ImportStatistics> Histogram;
1312
1313 for (const auto &[FromModule, GUID, Type] : ImportList) {
1314 ImportStatistics &Entry = Histogram[FromModule];
1315 ++Entry.Count;
1316 if (isGlobalVarSummary(Index, GUID))
1317 ++Entry.NumGVS;
1318 else if (Type == GlobalValueSummary::Definition)
1319 ++Entry.DefinedFS;
1320 }
1321 return Histogram;
1322}
1323#endif
1324
1325#ifndef NDEBUG
1326static bool checkVariableImport(
1327 const ModuleSummaryIndex &Index,
1328 FunctionImporter::ImportListsTy &ImportLists,
1329 DenseMap<StringRef, FunctionImporter::ExportSetTy> &ExportLists) {
1330 DenseSet<GlobalValue::GUID> FlattenedImports;
1331
1332 for (const auto &ImportPerModule : ImportLists)
1333 for (const auto &[FromModule, GUID, ImportType] : ImportPerModule.second)
1334 FlattenedImports.insert(GUID);
1335
1336 // Checks that all GUIDs of read/writeonly vars we see in export lists
1337 // are also in the import lists. Otherwise we my face linker undefs,
1338 // because readonly and writeonly vars are internalized in their
1339 // source modules. The exception would be if it has a linkage type indicating
1340 // that there may have been a copy existing in the importing module (e.g.
1341 // linkonce_odr). In that case we cannot accurately do this checking.
1342 auto IsReadOrWriteOnlyVarNeedingImporting = [&](StringRef ModulePath,
1343 const ValueInfo &VI) {
1344 auto *GVS = dyn_cast_or_null<GlobalVarSummary>(
1345 Index.findSummaryInModule(VI, ModulePath));
1346 return GVS && (Index.isReadOnly(GVS) || Index.isWriteOnly(GVS)) &&
1347 !(GVS->linkage() == GlobalValue::AvailableExternallyLinkage ||
1348 GVS->linkage() == GlobalValue::WeakODRLinkage ||
1349 GVS->linkage() == GlobalValue::LinkOnceODRLinkage);
1350 };
1351
1352 for (auto &ExportPerModule : ExportLists)
1353 for (auto &VI : ExportPerModule.second)
1354 if (!FlattenedImports.count(VI.getGUID()) &&
1355 IsReadOrWriteOnlyVarNeedingImporting(ExportPerModule.first, VI))
1356 return false;
1357
1358 return true;
1359}
1360#endif
1361
1362/// Compute all the import and export for every module using the Index.
1363void llvm::ComputeCrossModuleImport(
1364 const ModuleSummaryIndex &Index,
1365 const DenseMap<StringRef, GVSummaryMapTy> &ModuleToDefinedGVSummaries,
1366 function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
1367 isPrevailing,
1368 FunctionImporter::ImportListsTy &ImportLists,
1369 DenseMap<StringRef, FunctionImporter::ExportSetTy> &ExportLists) {
1370 auto MIS = ModuleImportsManager::create(IsPrevailing: isPrevailing, Index, ExportLists: &ExportLists);
1371 // For each module that has function defined, compute the import/export lists.
1372 for (const auto &DefinedGVSummaries : ModuleToDefinedGVSummaries) {
1373 auto &ImportList = ImportLists[DefinedGVSummaries.first];
1374 LLVM_DEBUG(dbgs() << "Computing import for Module '"
1375 << DefinedGVSummaries.first << "'\n");
1376 MIS->computeImportForModule(DefinedGVSummaries: DefinedGVSummaries.second,
1377 ModName: DefinedGVSummaries.first, ImportList);
1378 }
1379
1380 // When computing imports we only added the variables and functions being
1381 // imported to the export list. We also need to mark any references and calls
1382 // they make as exported as well. We do this here, as it is more efficient
1383 // since we may import the same values multiple times into different modules
1384 // during the import computation.
1385 for (auto &ELI : ExportLists) {
1386 // `NewExports` tracks the VI that gets exported because the full definition
1387 // of its user/referencer gets exported.
1388 FunctionImporter::ExportSetTy NewExports;
1389 const auto &DefinedGVSummaries =
1390 ModuleToDefinedGVSummaries.lookup(Val: ELI.first);
1391 for (auto &EI : ELI.second) {
1392 // Find the copy defined in the exporting module so that we can mark the
1393 // values it references in that specific definition as exported.
1394 // Below we will add all references and called values, without regard to
1395 // whether they are also defined in this module. We subsequently prune the
1396 // list to only include those defined in the exporting module, see comment
1397 // there as to why.
1398 auto DS = DefinedGVSummaries.find(Val: EI.getGUID());
1399 // Anything marked exported during the import computation must have been
1400 // defined in the exporting module.
1401 assert(DS != DefinedGVSummaries.end());
1402 auto *S = DS->getSecond();
1403 S = S->getBaseObject();
1404 if (auto *GVS = dyn_cast<GlobalVarSummary>(Val: S)) {
1405 // Export referenced functions and variables. We don't export/promote
1406 // objects referenced by writeonly variable initializer, because
1407 // we convert such variables initializers to "zeroinitializer".
1408 // See processGlobalForThinLTO.
1409 if (!Index.isWriteOnly(GVS))
1410 NewExports.insert_range(R: GVS->refs());
1411 } else {
1412 auto *FS = cast<FunctionSummary>(Val: S);
1413 NewExports.insert_range(R: llvm::make_first_range(c: FS->calls()));
1414 NewExports.insert_range(R: FS->refs());
1415 }
1416 }
1417 // Prune list computed above to only include values defined in the
1418 // exporting module. We do this after the above insertion since we may hit
1419 // the same ref/call target multiple times in above loop, and it is more
1420 // efficient to avoid a set lookup each time.
1421 NewExports.remove_if(
1422 Pred: [&](ValueInfo VI) { return !DefinedGVSummaries.count(Val: VI.getGUID()); });
1423 ELI.second.insert_range(R&: NewExports);
1424 }
1425
1426 // Now add the values exported because declarations of them are required in
1427 // importing modules. We do this after the above loop since their own
1428 // references and calls should not be exported.
1429 for (auto &[ModPath, RequiredExports] : MIS->requiredDeclExports())
1430 ExportLists[ModPath].insert_range(R&: RequiredExports);
1431
1432 assert(checkVariableImport(Index, ImportLists, ExportLists));
1433#ifndef NDEBUG
1434 LLVM_DEBUG(dbgs() << "Import/Export lists for " << ImportLists.size()
1435 << " modules:\n");
1436 for (const auto &ModuleImports : ImportLists) {
1437 auto ModName = ModuleImports.first;
1438 auto &Exports = ExportLists[ModName];
1439 unsigned NumGVS = numGlobalVarSummaries(Index, Exports);
1440 DenseMap<StringRef, ImportStatistics> Histogram =
1441 collectImportStatistics(Index, ModuleImports.second);
1442 LLVM_DEBUG(dbgs() << "* Module " << ModName << " exports "
1443 << Exports.size() - NumGVS << " functions and " << NumGVS
1444 << " vars. Imports from " << Histogram.size()
1445 << " modules.\n");
1446 for (const auto &[SrcModName, Stats] : Histogram) {
1447 LLVM_DEBUG(dbgs() << " - " << Stats.DefinedFS
1448 << " function definitions and "
1449 << Stats.Count - Stats.NumGVS - Stats.DefinedFS
1450 << " function declarations imported from " << SrcModName
1451 << "\n");
1452 LLVM_DEBUG(dbgs() << " - " << Stats.NumGVS
1453 << " global vars imported from " << SrcModName << "\n");
1454 }
1455 }
1456#endif
1457}
1458
1459#ifndef NDEBUG
1460static void dumpImportListForModule(const ModuleSummaryIndex &Index,
1461 StringRef ModulePath,
1462 FunctionImporter::ImportMapTy &ImportList) {
1463 DenseMap<StringRef, ImportStatistics> Histogram =
1464 collectImportStatistics(Index, ImportList);
1465 LLVM_DEBUG(dbgs() << "* Module " << ModulePath << " imports from "
1466 << Histogram.size() << " modules.\n");
1467 for (const auto &[SrcModName, Stats] : Histogram) {
1468 LLVM_DEBUG(dbgs() << " - " << Stats.DefinedFS
1469 << " function definitions and "
1470 << Stats.Count - Stats.DefinedFS - Stats.NumGVS
1471 << " function declarations imported from " << SrcModName
1472 << "\n");
1473 LLVM_DEBUG(dbgs() << " - " << Stats.NumGVS << " vars imported from "
1474 << SrcModName << "\n");
1475 }
1476}
1477#endif
1478
1479/// Compute all the imports for the given module using the Index.
1480///
1481/// \p isPrevailing is a callback that will be called with a global value's GUID
1482/// and summary and should return whether the module corresponding to the
1483/// summary contains the linker-prevailing copy of that value.
1484///
1485/// \p ImportList will be populated with a map that can be passed to
1486/// FunctionImporter::importFunctions() above (see description there).
1487static void ComputeCrossModuleImportForModuleForTest(
1488 StringRef ModulePath,
1489 function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
1490 isPrevailing,
1491 const ModuleSummaryIndex &Index,
1492 FunctionImporter::ImportMapTy &ImportList) {
1493 // Collect the list of functions this module defines.
1494 // GUID -> Summary
1495 GVSummaryMapTy FunctionSummaryMap;
1496 Index.collectDefinedFunctionsForModule(ModulePath, GVSummaryMap&: FunctionSummaryMap);
1497
1498 // Compute the import list for this module.
1499 LLVM_DEBUG(dbgs() << "Computing import for Module '" << ModulePath << "'\n");
1500 auto MIS = ModuleImportsManager::create(IsPrevailing: isPrevailing, Index);
1501 MIS->computeImportForModule(DefinedGVSummaries: FunctionSummaryMap, ModName: ModulePath, ImportList);
1502
1503#ifndef NDEBUG
1504 dumpImportListForModule(Index, ModulePath, ImportList);
1505#endif
1506}
1507
1508/// Mark all external summaries in \p Index for import into the given module.
1509/// Used for testing the case of distributed builds using a distributed index.
1510///
1511/// \p ImportList will be populated with a map that can be passed to
1512/// FunctionImporter::importFunctions() above (see description there).
1513static void ComputeCrossModuleImportForModuleFromIndexForTest(
1514 StringRef ModulePath, const ModuleSummaryIndex &Index,
1515 FunctionImporter::ImportMapTy &ImportList) {
1516 for (const auto &GlobalList : Index) {
1517 // Ignore entries for undefined references.
1518 if (GlobalList.second.getSummaryList().empty())
1519 continue;
1520
1521 auto GUID = GlobalList.first;
1522 assert(GlobalList.second.getSummaryList().size() == 1 &&
1523 "Expected individual combined index to have one summary per GUID");
1524 auto &Summary = GlobalList.second.getSummaryList()[0];
1525 // Skip the summaries for the importing module. These are included to
1526 // e.g. record required linkage changes.
1527 if (Summary->modulePath() == ModulePath)
1528 continue;
1529 // Add an entry to provoke importing by thinBackend.
1530 ImportList.addGUID(FromModule: Summary->modulePath(), GUID, ImportKind: Summary->importType());
1531 }
1532#ifndef NDEBUG
1533 dumpImportListForModule(Index, ModulePath, ImportList);
1534#endif
1535}
1536
1537// For SamplePGO, the indirect call targets for local functions will
1538// have its original name annotated in profile. We try to find the
1539// corresponding PGOFuncName as the GUID, and fix up the edges
1540// accordingly.
1541void updateValueInfoForIndirectCalls(ModuleSummaryIndex &Index,
1542 FunctionSummary *FS) {
1543 // Returns the ValueInfo that should be used in place of \p CalleeVI, or an
1544 // empty ValueInfo if no update is needed.
1545 auto GetUpdatedCallee = [&](ValueInfo CalleeVI) -> ValueInfo {
1546 if (!CalleeVI || !CalleeVI.getSummaryList().empty())
1547 return ValueInfo();
1548 auto GUID = Index.getGUIDFromOriginalID(OriginalID: CalleeVI.getGUID());
1549 if (GUID == 0)
1550 return ValueInfo();
1551 auto VI = Index.getValueInfo(GUID);
1552 if (llvm::any_of(
1553 Range: VI.getSummaryList(),
1554 P: [&](const std::unique_ptr<GlobalValueSummary> &SummaryPtr) {
1555 // The mapping from OriginalId to GUID may return a GUID
1556 // that corresponds to a static variable. Filter it out here.
1557 // This can happen when
1558 // 1) There is a call to a library function which is not defined
1559 // in the index.
1560 // 2) There is a static variable with the OriginalGUID identical
1561 // to the GUID of the library function in 1);
1562 // When this happens the static variable in 2) will be found,
1563 // which needs to be filtered out.
1564 return SummaryPtr->getSummaryKind() ==
1565 GlobalValueSummary::GlobalVarKind;
1566 }))
1567 return ValueInfo();
1568 return VI;
1569 };
1570
1571 for (auto &EI : FS->mutableCalls()) {
1572 // Update the edge to point directly to the correct GUID.
1573 if (auto VI = GetUpdatedCallee(EI.first))
1574 EI.first = VI;
1575 }
1576
1577 // MemProf summarizes indirect callsites by synthesizing a CallsiteInfo
1578 // record for each profiled target, using the same GUIDs found in the VP
1579 // metadata (which, for local targets, may be the original name GUID when
1580 // e.g. synthesized from the MemProf profile or from a SamplePGO profile).
1581 // Update those callees as well so that they are consistent with the call
1582 // edges above, and so that the thin link's MemProf context disambiguation
1583 // can correlate the callsite with the summary for the target function.
1584 if (FS->callsites().empty())
1585 return;
1586 for (auto &CI : FS->mutableCallsites()) {
1587 if (auto VI = GetUpdatedCallee(CI.Callee))
1588 CI.Callee = VI;
1589 }
1590}
1591
1592void llvm::updateIndirectCalls(ModuleSummaryIndex &Index) {
1593 for (const auto &Entry : Index) {
1594 for (const auto &S : Entry.second.getSummaryList()) {
1595 if (auto *FS = dyn_cast<FunctionSummary>(Val: S.get()))
1596 updateValueInfoForIndirectCalls(Index, FS);
1597 }
1598 }
1599}
1600
1601void llvm::computeDeadSymbolsAndUpdateIndirectCalls(
1602 ModuleSummaryIndex &Index,
1603 const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols,
1604 function_ref<PrevailingType(GlobalValue::GUID)> isPrevailing) {
1605 assert(!Index.withGlobalValueDeadStripping());
1606 if (!ComputeDead ||
1607 // Don't do anything when nothing is live, this is friendly with tests.
1608 GUIDPreservedSymbols.empty()) {
1609 // Still need to update indirect calls.
1610 updateIndirectCalls(Index);
1611 return;
1612 }
1613 unsigned LiveSymbols = 0;
1614 SmallVector<ValueInfo, 128> Worklist;
1615 Worklist.reserve(N: GUIDPreservedSymbols.size() * 2);
1616 for (auto GUID : GUIDPreservedSymbols) {
1617 ValueInfo VI = Index.getValueInfo(GUID);
1618 if (!VI)
1619 continue;
1620 for (const auto &S : VI.getSummaryList())
1621 S->setLive(true);
1622 }
1623
1624 // Add values flagged in the index as live roots to the worklist.
1625 for (const auto &Entry : Index) {
1626 auto VI = Index.getValueInfo(R: Entry);
1627 for (const auto &S : Entry.second.getSummaryList()) {
1628 if (auto *FS = dyn_cast<FunctionSummary>(Val: S.get()))
1629 updateValueInfoForIndirectCalls(Index, FS);
1630 if (S->isLive()) {
1631 LLVM_DEBUG(dbgs() << "Live root: " << VI << "\n");
1632 Worklist.push_back(Elt: VI);
1633 ++LiveSymbols;
1634 break;
1635 }
1636 }
1637 }
1638
1639 // Make value live and add it to the worklist if it was not live before.
1640 auto visit = [&](ValueInfo VI, bool IsAliasee) {
1641 // FIXME: If we knew which edges were created for indirect call profiles,
1642 // we could skip them here. Any that are live should be reached via
1643 // other edges, e.g. reference edges. Otherwise, using a profile collected
1644 // on a slightly different binary might provoke preserving, importing
1645 // and ultimately promoting calls to functions not linked into this
1646 // binary, which increases the binary size unnecessarily. Note that
1647 // if this code changes, the importer needs to change so that edges
1648 // to functions marked dead are skipped.
1649
1650 if (llvm::any_of(Range: VI.getSummaryList(),
1651 P: [](const std::unique_ptr<llvm::GlobalValueSummary> &S) {
1652 return S->isLive();
1653 }))
1654 return;
1655
1656 // We only keep live symbols that are known to be non-prevailing if any are
1657 // available_externally, linkonceodr, weakodr. Those symbols are discarded
1658 // later in the EliminateAvailableExternally pass and setting them to
1659 // not-live could break downstreams users of liveness information (PR36483)
1660 // or limit optimization opportunities.
1661 if (isPrevailing(VI.getGUID()) == PrevailingType::No) {
1662 bool KeepAliveLinkage = false;
1663 bool Interposable = false;
1664 for (const auto &S : VI.getSummaryList()) {
1665 if (S->linkage() == GlobalValue::AvailableExternallyLinkage ||
1666 S->linkage() == GlobalValue::WeakODRLinkage ||
1667 S->linkage() == GlobalValue::LinkOnceODRLinkage)
1668 KeepAliveLinkage = true;
1669 else if (GlobalValue::isInterposableLinkage(Linkage: S->linkage()))
1670 Interposable = true;
1671 }
1672
1673 if (!IsAliasee) {
1674 if (!KeepAliveLinkage)
1675 return;
1676
1677 if (Interposable)
1678 report_fatal_error(
1679 reason: "Interposable and available_externally/linkonce_odr/weak_odr "
1680 "symbol");
1681 }
1682 }
1683
1684 for (const auto &S : VI.getSummaryList())
1685 S->setLive(true);
1686 ++LiveSymbols;
1687 Worklist.push_back(Elt: VI);
1688 };
1689
1690 while (!Worklist.empty()) {
1691 auto VI = Worklist.pop_back_val();
1692 for (const auto &Summary : VI.getSummaryList()) {
1693 if (auto *AS = dyn_cast<AliasSummary>(Val: Summary.get())) {
1694 // If this is an alias, visit the aliasee VI to ensure that all copies
1695 // are marked live and it is added to the worklist for further
1696 // processing of its references.
1697 visit(AS->getAliaseeVI(), true);
1698 continue;
1699 }
1700 for (auto Ref : Summary->refs())
1701 visit(Ref, false);
1702 if (auto *FS = dyn_cast<FunctionSummary>(Val: Summary.get()))
1703 for (auto Call : FS->calls())
1704 visit(Call.first, false);
1705 }
1706 }
1707 Index.setWithGlobalValueDeadStripping();
1708
1709 unsigned DeadSymbols = Index.size() - LiveSymbols;
1710 LLVM_DEBUG(dbgs() << LiveSymbols << " symbols Live, and " << DeadSymbols
1711 << " symbols Dead \n");
1712 NumDeadSymbols += DeadSymbols;
1713 NumLiveSymbols += LiveSymbols;
1714}
1715
1716// Compute dead symbols and propagate constants in combined index.
1717void llvm::computeDeadSymbolsWithConstProp(
1718 ModuleSummaryIndex &Index,
1719 const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols,
1720 function_ref<PrevailingType(GlobalValue::GUID)> isPrevailing,
1721 bool ImportEnabled) {
1722 llvm::TimeTraceScope timeScope("Drop dead symbols and propagate attributes");
1723 computeDeadSymbolsAndUpdateIndirectCalls(Index, GUIDPreservedSymbols,
1724 isPrevailing);
1725 if (ImportEnabled)
1726 Index.propagateAttributes(PreservedSymbols: GUIDPreservedSymbols);
1727}
1728
1729/// Compute the set of summaries needed for a ThinLTO backend compilation of
1730/// \p ModulePath.
1731void llvm::gatherImportedSummariesForModule(
1732 StringRef ModulePath,
1733 const DenseMap<StringRef, GVSummaryMapTy> &ModuleToDefinedGVSummaries,
1734 const FunctionImporter::ImportMapTy &ImportList,
1735 ModuleToSummariesForIndexTy &ModuleToSummariesForIndex,
1736 GVSummaryPtrSet &DecSummaries) {
1737 // Include all summaries from the importing module.
1738 ModuleToSummariesForIndex[std::string(ModulePath)] =
1739 ModuleToDefinedGVSummaries.lookup(Val: ModulePath);
1740
1741 // Forward port the heterogeneous std::map::operator[]() from C++26, which
1742 // lets us look up the map without allocating an instance of std::string when
1743 // the key-value pair exists in the map.
1744 // TODO: Remove this in favor of the heterogenous std::map::operator[]() from
1745 // C++26 when it becomes available for our codebase.
1746 auto LookupOrCreate = [](ModuleToSummariesForIndexTy &Map,
1747 StringRef Key) -> GVSummaryMapTy & {
1748 auto It = Map.find(x: Key);
1749 if (It == Map.end())
1750 std::tie(args&: It, args: std::ignore) =
1751 Map.try_emplace(k: std::string(Key), args: GVSummaryMapTy());
1752 return It->second;
1753 };
1754
1755 // Include summaries for imports.
1756 for (const auto &[FromModule, GUID, ImportType] : ImportList) {
1757 auto &SummariesForIndex =
1758 LookupOrCreate(ModuleToSummariesForIndex, FromModule);
1759
1760 const auto &DefinedGVSummaries = ModuleToDefinedGVSummaries.at(Val: FromModule);
1761 const auto &DS = DefinedGVSummaries.find(Val: GUID);
1762 assert(DS != DefinedGVSummaries.end() &&
1763 "Expected a defined summary for imported global value");
1764 if (ImportType == GlobalValueSummary::Declaration)
1765 DecSummaries.insert(Ptr: DS->second);
1766
1767 SummariesForIndex[GUID] = DS->second;
1768 }
1769
1770 // When AlwaysRenamePromotedLocals is false, for each source module we import
1771 // from, also include summaries for local functions that have
1772 // NoRenameOnPromotion set. This is needed for distributed ThinLTO. Otherwise,
1773 // the local function of the source module will keep its origin name, e.g.,
1774 // foo() while the function in destination module will have name
1775 // foo.llvm.<...>() and this will cause a link failure.
1776 //
1777 // Note: this imports a superset of the necessary declarations — all locals
1778 // with NoRenameOnPromotion in each source module, not just those referenced
1779 // by the importing module. Computing the precise set would require walking
1780 // the summary reference graph from each imported function, which is more
1781 // expensive than the simple scan here.
1782 if (!AlwaysRenamePromotedLocals) {
1783 for (auto &[ModPath, SummariesForIndex] : ModuleToSummariesForIndex) {
1784 if (ModPath == ModulePath)
1785 continue;
1786 auto It = ModuleToDefinedGVSummaries.find(Val: ModPath);
1787 if (It == ModuleToDefinedGVSummaries.end())
1788 continue;
1789 for (const auto &[GUID, Summary] : It->second) {
1790 if (Summary->noRenameOnPromotion()) {
1791 DecSummaries.insert(Ptr: Summary);
1792 SummariesForIndex.try_emplace(Key: GUID, Args: Summary);
1793 }
1794 }
1795 }
1796 }
1797}
1798
1799/// Emit the files \p ModulePath will import from into \p OutputFilename.
1800Error llvm::EmitImportsFiles(
1801 StringRef ModulePath, StringRef OutputFilename,
1802 const ModuleToSummariesForIndexTy &ModuleToSummariesForIndex) {
1803 std::error_code EC;
1804 raw_fd_ostream ImportsOS(OutputFilename, EC, sys::fs::OpenFlags::OF_Text);
1805 if (EC)
1806 return createFileError(F: "cannot open " + OutputFilename,
1807 E: errorCodeToError(EC));
1808 processImportsFiles(ModulePath, ModuleToSummariesForIndex,
1809 F: [&](StringRef M) { ImportsOS << M << "\n"; });
1810 return Error::success();
1811}
1812
1813/// Invoke callback \p F on the file paths from which \p ModulePath
1814/// will import.
1815void llvm::processImportsFiles(
1816 StringRef ModulePath,
1817 const ModuleToSummariesForIndexTy &ModuleToSummariesForIndex,
1818 function_ref<void(const std::string &)> F) {
1819 for (const auto &ILI : ModuleToSummariesForIndex)
1820 // The ModuleToSummariesForIndex map includes an entry for the current
1821 // Module (needed for writing out the index files). We don't want to
1822 // include it in the imports file, however, so filter it out.
1823 if (ILI.first != ModulePath)
1824 F(ILI.first);
1825}
1826
1827bool llvm::convertToDeclaration(GlobalValue &GV) {
1828 LLVM_DEBUG(dbgs() << "Converting to a declaration: `" << GV.getName()
1829 << "\n");
1830 MDNode *UniqueID = nullptr;
1831 if (auto *GO = dyn_cast<GlobalObject>(Val: &GV))
1832 UniqueID = GO->getMetadata(KindID: LLVMContext::MD_guid);
1833
1834 if (Function *F = dyn_cast<Function>(Val: &GV)) {
1835 F->deleteBody();
1836 F->clearMetadata();
1837 if (UniqueID)
1838 F->setMetadata(KindID: LLVMContext::MD_guid, Node: UniqueID);
1839 F->setComdat(nullptr);
1840 } else if (GlobalVariable *V = dyn_cast<GlobalVariable>(Val: &GV)) {
1841 V->setInitializer(nullptr);
1842 V->setLinkage(GlobalValue::ExternalLinkage);
1843 V->clearMetadata();
1844 if (UniqueID)
1845 V->setMetadata(KindID: LLVMContext::MD_guid, Node: UniqueID);
1846 V->setComdat(nullptr);
1847 } else {
1848 GlobalValue *NewGV;
1849 if (GV.getValueType()->isFunctionTy())
1850 NewGV =
1851 Function::Create(Ty: cast<FunctionType>(Val: GV.getValueType()),
1852 Linkage: GlobalValue::ExternalLinkage, AddrSpace: GV.getAddressSpace(),
1853 N: "", M: GV.getParent());
1854 else
1855 NewGV =
1856 new GlobalVariable(*GV.getParent(), GV.getValueType(),
1857 /*isConstant*/ false, GlobalValue::ExternalLinkage,
1858 /*init*/ nullptr, "",
1859 /*insertbefore*/ nullptr, GV.getThreadLocalMode(),
1860 GV.getType()->getAddressSpace());
1861 NewGV->takeName(V: &GV);
1862 GV.replaceAllUsesWith(V: NewGV);
1863 return false;
1864 }
1865 if (!GV.isImplicitDSOLocal())
1866 GV.setDSOLocal(false);
1867 return true;
1868}
1869
1870void llvm::thinLTOFinalizeInModule(Module &TheModule,
1871 const GVSummaryMapTy &DefinedGlobals,
1872 bool PropagateAttrs) {
1873 llvm::TimeTraceScope timeScope("ThinLTO finalize in module");
1874 DenseSet<Comdat *> NonPrevailingComdats;
1875 auto FinalizeInModule = [&](GlobalValue &GV, bool Propagate = false) {
1876 // See if the global summary analysis computed a new resolved linkage.
1877 const auto &GS = DefinedGlobals.find(Val: GV.getGUIDOrFallback());
1878 if (GS == DefinedGlobals.end())
1879 return;
1880
1881 if (Propagate)
1882 if (FunctionSummary *FS = dyn_cast<FunctionSummary>(Val: GS->second)) {
1883 if (Function *F = dyn_cast<Function>(Val: &GV)) {
1884 // TODO: propagate ReadNone and ReadOnly.
1885 if (FS->fflags().ReadNone && !F->doesNotAccessMemory())
1886 F->setDoesNotAccessMemory();
1887
1888 if (FS->fflags().ReadOnly && !F->onlyReadsMemory())
1889 F->setOnlyReadsMemory();
1890
1891 if (FS->fflags().NoRecurse && !F->doesNotRecurse())
1892 F->setDoesNotRecurse();
1893
1894 if (FS->fflags().NoUnwind && !F->doesNotThrow())
1895 F->setDoesNotThrow();
1896 }
1897 }
1898
1899 auto NewLinkage = GS->second->linkage();
1900 if (GlobalValue::isLocalLinkage(Linkage: GV.getLinkage()) ||
1901 // Don't internalize anything here, because the code below
1902 // lacks necessary correctness checks. Leave this job to
1903 // LLVM 'internalize' pass.
1904 GlobalValue::isLocalLinkage(Linkage: NewLinkage) ||
1905 // In case it was dead and already converted to declaration.
1906 GV.isDeclaration())
1907 return;
1908
1909 // Set the potentially more constraining visibility computed from summaries.
1910 // The DefaultVisibility condition is because older GlobalValueSummary does
1911 // not record DefaultVisibility and we don't want to change protected/hidden
1912 // to default.
1913 if (GS->second->getVisibility() != GlobalValue::DefaultVisibility)
1914 GV.setVisibility(GS->second->getVisibility());
1915
1916 if (NewLinkage == GV.getLinkage())
1917 return;
1918
1919 // Check for a non-prevailing def that has interposable linkage
1920 // (e.g. non-odr weak or linkonce). In that case we can't simply
1921 // convert to available_externally, since it would lose the
1922 // interposable property and possibly get inlined. Simply drop
1923 // the definition in that case.
1924 if (GlobalValue::isAvailableExternallyLinkage(Linkage: NewLinkage) &&
1925 GlobalValue::isInterposableLinkage(Linkage: GV.getLinkage())) {
1926 if (!convertToDeclaration(GV))
1927 // FIXME: Change this to collect replaced GVs and later erase
1928 // them from the parent module once thinLTOResolvePrevailingGUID is
1929 // changed to enable this for aliases.
1930 llvm_unreachable("Expected GV to be converted");
1931 } else {
1932 // If all copies of the original symbol had global unnamed addr and
1933 // linkonce_odr linkage, or if all of them had local unnamed addr linkage
1934 // and are constants, then it should be an auto hide symbol. In that case
1935 // the thin link would have marked it as CanAutoHide. Add hidden
1936 // visibility to the symbol to preserve the property.
1937 if (NewLinkage == GlobalValue::WeakODRLinkage &&
1938 GS->second->canAutoHide()) {
1939 assert(GV.canBeOmittedFromSymbolTable());
1940 GV.setVisibility(GlobalValue::HiddenVisibility);
1941 }
1942
1943 LLVM_DEBUG(dbgs() << "ODR fixing up linkage for `" << GV.getName()
1944 << "` from " << GV.getLinkage() << " to " << NewLinkage
1945 << "\n");
1946 GV.setLinkage(NewLinkage);
1947 }
1948 // Remove declarations from comdats, including available_externally
1949 // as this is a declaration for the linker, and will be dropped eventually.
1950 // It is illegal for comdats to contain declarations.
1951 auto *GO = dyn_cast_or_null<GlobalObject>(Val: &GV);
1952 if (GO && GO->isDeclarationForLinker() && GO->hasComdat()) {
1953 if (GO->getComdat()->getName() == GO->getName())
1954 NonPrevailingComdats.insert(V: GO->getComdat());
1955 GO->setComdat(nullptr);
1956 }
1957 };
1958
1959 // Process functions and global now
1960 for (auto &GV : TheModule)
1961 FinalizeInModule(GV, PropagateAttrs);
1962 for (auto &GV : TheModule.globals())
1963 FinalizeInModule(GV);
1964 for (auto &GV : TheModule.aliases())
1965 FinalizeInModule(GV);
1966
1967 // For a non-prevailing comdat, all its members must be available_externally.
1968 // FinalizeInModule has handled non-local-linkage GlobalValues. Here we handle
1969 // local linkage GlobalValues.
1970 if (NonPrevailingComdats.empty())
1971 return;
1972 for (auto &GO : TheModule.global_objects()) {
1973 if (auto *C = GO.getComdat(); C && NonPrevailingComdats.count(V: C)) {
1974 GO.setComdat(nullptr);
1975 GO.setLinkage(GlobalValue::AvailableExternallyLinkage);
1976 }
1977 }
1978 bool Changed;
1979 do {
1980 Changed = false;
1981 // If an alias references a GlobalValue in a non-prevailing comdat, change
1982 // it to available_externally. For simplicity we only handle GlobalValue and
1983 // ConstantExpr with a base object. ConstantExpr without a base object is
1984 // unlikely used in a COMDAT.
1985 for (auto &GA : TheModule.aliases()) {
1986 if (GA.hasAvailableExternallyLinkage())
1987 continue;
1988 GlobalObject *Obj = GA.getAliaseeObject();
1989 assert(Obj && "aliasee without an base object is unimplemented");
1990 if (Obj->hasAvailableExternallyLinkage()) {
1991 GA.setLinkage(GlobalValue::AvailableExternallyLinkage);
1992 Changed = true;
1993 }
1994 }
1995 } while (Changed);
1996}
1997
1998/// Run internalization on \p TheModule based on symmary analysis.
1999void llvm::thinLTOInternalizeModule(Module &TheModule,
2000 const GVSummaryMapTy &DefinedGlobals) {
2001 llvm::TimeTraceScope timeScope("ThinLTO internalize module");
2002 // Declare a callback for the internalize pass that will ask for every
2003 // candidate GlobalValue if it can be internalized or not.
2004 auto MustPreserveGV = [&](const GlobalValue &GV) -> bool {
2005 // It may be the case that GV is on a chain of an ifunc, its alias and
2006 // subsequent aliases. In this case, the summary for the value is not
2007 // available.
2008 if (isa<GlobalIFunc>(Val: &GV) ||
2009 (isa<GlobalAlias>(Val: &GV) &&
2010 isa<GlobalIFunc>(Val: cast<GlobalAlias>(Val: &GV)->getAliaseeObject())))
2011 return true;
2012
2013 // Lookup the linkage recorded in the summaries during global analysis.
2014 auto GS = DefinedGlobals.find(Val: GV.getGUIDOrFallback());
2015 if (GS == DefinedGlobals.end()) {
2016 // Must have been promoted (possibly conservatively). Find original
2017 // name so that we can access the correct summary and see if it can
2018 // be internalized again.
2019 // FIXME: Eventually we should control promotion instead of promoting
2020 // and internalizing again.
2021 StringRef OrigName =
2022 ModuleSummaryIndex::getOriginalNameBeforePromote(Name: GV.getName());
2023 std::string OrigId = GlobalValue::getGlobalIdentifier(
2024 Name: OrigName, Linkage: GlobalValue::InternalLinkage,
2025 FileName: TheModule.getSourceFileName());
2026 GS = DefinedGlobals.find(
2027 Val: GlobalValue::getGUIDAssumingExternalLinkage(GlobalName: OrigId));
2028 if (GS == DefinedGlobals.end()) {
2029 // Also check the original non-promoted non-globalized name. In some
2030 // cases a preempted weak value is linked in as a local copy because
2031 // it is referenced by an alias (IRLinker::linkGlobalValueProto).
2032 // In that case, since it was originally not a local value, it was
2033 // recorded in the index using the original name.
2034 // FIXME: This may not be needed once PR27866 is fixed.
2035 GS = DefinedGlobals.find(
2036 Val: GlobalValue::getGUIDAssumingExternalLinkage(GlobalName: OrigName));
2037 assert(GS != DefinedGlobals.end());
2038 }
2039 }
2040 return !GlobalValue::isLocalLinkage(Linkage: GS->second->linkage());
2041 };
2042
2043 // FIXME: See if we can just internalize directly here via linkage changes
2044 // based on the index, rather than invoking internalizeModule.
2045 internalizeModule(TheModule, MustPreserveGV);
2046}
2047
2048/// Make alias a clone of its aliasee.
2049static Function *replaceAliasWithAliasee(Module *SrcModule, GlobalAlias *GA) {
2050 Function *Fn = cast<Function>(Val: GA->getAliaseeObject());
2051
2052 ValueToValueMapTy VMap;
2053 Function *NewFn = CloneFunction(F: Fn, VMap);
2054 // Clone should use the original alias's linkage, visibility and name, and we
2055 // ensure all uses of alias instead use the new clone (casted if necessary).
2056 NewFn->setLinkage(GA->getLinkage());
2057 NewFn->setVisibility(GA->getVisibility());
2058 GA->replaceAllUsesWith(V: NewFn);
2059 NewFn->takeName(V: GA);
2060 return NewFn;
2061}
2062
2063// Internalize values that we marked with specific attribute
2064// in processGlobalForThinLTO.
2065static void internalizeGVsAfterImport(Module &M) {
2066 for (auto &GV : M.globals())
2067 // Skip GVs which have been converted to declarations
2068 // by dropDeadSymbols.
2069 if (!GV.isDeclaration() && GV.hasAttribute(Kind: "thinlto-internalize")) {
2070 GV.setLinkage(GlobalValue::InternalLinkage);
2071 GV.setVisibility(GlobalValue::DefaultVisibility);
2072 }
2073}
2074
2075/// When a function carrying !implicit.ref is imported via ThinLTO, the
2076/// referenced global arrives as available_externally. This string can be dead
2077/// code eliminated since it has no IR uses -- only metadata references. Adding
2078/// it to llvm.compiler.used prevents elimination.
2079static void protectImplicitRefGlobals(Module &M) {
2080 SmallPtrSet<GlobalValue *, 4> Seen;
2081 SmallVector<GlobalValue *, 4> ToProtect;
2082 for (Function &F : M) {
2083 if (!F.hasAvailableExternallyLinkage() ||
2084 !F.hasMetadata(KindID: LLVMContext::MD_implicit_ref))
2085 continue;
2086 SmallVector<MDNode *> MDs;
2087 F.getMetadata(KindID: LLVMContext::MD_implicit_ref, MDs);
2088 for (MDNode *MD : MDs) {
2089 auto *Op = MD->getOperand(I: 0).get();
2090 if (!Op)
2091 continue;
2092 if (auto *VAM = dyn_cast<ValueAsMetadata>(Val: Op))
2093 if (auto *GV = dyn_cast<GlobalVariable>(Val: VAM->getValue()))
2094 if (GV->hasAvailableExternallyLinkage() && Seen.insert(Ptr: GV).second)
2095 ToProtect.push_back(Elt: GV);
2096 }
2097 }
2098 if (!ToProtect.empty())
2099 appendToCompilerUsed(M, Values: ToProtect);
2100}
2101
2102// Automatically import functions in Module \p DestModule based on the summaries
2103// index.
2104Expected<bool> FunctionImporter::importFunctions(
2105 Module &DestModule, const FunctionImporter::ImportMapTy &ImportList) {
2106 const IPOOptions &Opts = getIPOOptions(M: DestModule);
2107 LLVM_DEBUG(dbgs() << "Starting import for Module "
2108 << DestModule.getModuleIdentifier() << "\n");
2109 unsigned ImportedCount = 0, ImportedGVCount = 0;
2110 // Before carrying out any imports, see if this module defines functions in
2111 // MoveSymbolGUID. If it does, delete them here (but leave the declaration).
2112 // The function will be imported elsewhere, as extenal linkage, and the
2113 // destination doesn't yet have its definition.
2114 DenseSet<GlobalValue::GUID> MoveSymbolGUIDSet;
2115 MoveSymbolGUIDSet.insert_range(R&: MoveSymbolGUID);
2116 for (auto &F : DestModule)
2117 if (!F.isDeclaration() && MoveSymbolGUIDSet.contains(V: F.getGUIDOrFallback()))
2118 F.deleteBody();
2119
2120 IRMover Mover(DestModule);
2121
2122 // Import from the source modules in module hash order. The IRMover appends
2123 // imported globals and named metadata (e.g. llvm.linker.options) in import
2124 // order, so this must not depend on the module paths, which the ThinLTO
2125 // cache key (see computeLTOCacheKey) leaves out. Modules with the same hash
2126 // keep the alphabetical order.
2127 SmallVector<std::pair<ModuleHash, StringRef>, 0> SourceModules;
2128 for (StringRef ModName : ImportList.getSourceModules())
2129 SourceModules.emplace_back(Args: Index.getModuleHash(ModPath: ModName), Args&: ModName);
2130 llvm::sort(C&: SourceModules);
2131
2132 // Do the actual import of functions now, one Module at a time
2133 for (const auto &[ModHash, ModName] : SourceModules) {
2134 llvm::TimeTraceScope timeScope("Import", ModName);
2135 // Get the module for the import
2136 Expected<std::unique_ptr<Module>> SrcModuleOrErr = ModuleLoader(ModName);
2137 if (!SrcModuleOrErr)
2138 return SrcModuleOrErr.takeError();
2139 std::unique_ptr<Module> SrcModule = std::move(*SrcModuleOrErr);
2140 assert(&DestModule.getContext() == &SrcModule->getContext() &&
2141 "Context mismatch");
2142
2143 // If modules were created with lazy metadata loading, materialize it
2144 // now, before linking it (otherwise this will be a noop).
2145 if (Error Err = SrcModule->materializeMetadata())
2146 return std::move(Err);
2147
2148 // Find the globals to import
2149 SetVector<GlobalValue *> GlobalsToImport;
2150 // Functions (or aliases of functions) to import as declarations, along
2151 // with their GUIDs.
2152 SmallVector<std::pair<GlobalValue *, GlobalValue::GUID>> DeclsToImport;
2153 {
2154 llvm::TimeTraceScope functionsScope("Functions");
2155 for (Function &F : *SrcModule) {
2156 if (!F.hasName())
2157 continue;
2158 auto GUID = F.getGUIDOrFallback();
2159 auto MaybeImportType = ImportList.getImportType(FromModule: ModName, GUID);
2160 bool ImportDefinition =
2161 MaybeImportType == GlobalValueSummary::Definition;
2162
2163 LLVM_DEBUG(dbgs() << (MaybeImportType ? "Is" : "Not")
2164 << " importing function"
2165 << (ImportDefinition
2166 ? " definition "
2167 : (MaybeImportType ? " declaration " : " "))
2168 << GUID << " " << F.getName() << " from "
2169 << SrcModule->getSourceFileName() << "\n");
2170 if (ImportDefinition) {
2171 if (Error Err = F.materialize())
2172 return std::move(Err);
2173 // MemProf should match function's definition and summary,
2174 // 'thinlto_src_module' is needed.
2175 if (Opts.enable_import_metadata ||
2176 EnableMemProfContextDisambiguation) {
2177 // Add 'thinlto_src_module' and 'thinlto_src_file' metadata for
2178 // statistics and debugging.
2179 F.setMetadata(
2180 Kind: "thinlto_src_module",
2181 Node: MDNode::get(Context&: DestModule.getContext(),
2182 MDs: {MDString::get(Context&: DestModule.getContext(),
2183 Str: SrcModule->getModuleIdentifier())}));
2184 F.setMetadata(
2185 Kind: "thinlto_src_file",
2186 Node: MDNode::get(Context&: DestModule.getContext(),
2187 MDs: {MDString::get(Context&: DestModule.getContext(),
2188 Str: SrcModule->getSourceFileName())}));
2189 }
2190 GlobalsToImport.insert(X: &F);
2191 } else if (MaybeImportType) {
2192 assert(*MaybeImportType == GlobalValueSummary::Declaration);
2193 DeclsToImport.push_back(Elt: {&F, GUID});
2194 }
2195 }
2196 }
2197 {
2198 llvm::TimeTraceScope globalsScope("Globals");
2199 for (GlobalVariable &GV : SrcModule->globals()) {
2200 if (!GV.hasName())
2201 continue;
2202 auto GUID = GV.getGUIDOrFallback();
2203 auto MaybeImportType = ImportList.getImportType(FromModule: ModName, GUID);
2204 bool ImportDefinition =
2205 MaybeImportType == GlobalValueSummary::Definition;
2206
2207 LLVM_DEBUG(dbgs() << (MaybeImportType ? "Is" : "Not")
2208 << " importing global"
2209 << (ImportDefinition
2210 ? " definition "
2211 : (MaybeImportType ? " declaration " : " "))
2212 << GUID << " " << GV.getName() << " from "
2213 << SrcModule->getSourceFileName() << "\n");
2214 if (ImportDefinition) {
2215 if (Error Err = GV.materialize())
2216 return std::move(Err);
2217 ImportedGVCount += GlobalsToImport.insert(X: &GV);
2218 }
2219 }
2220 }
2221 {
2222 llvm::TimeTraceScope aliasesScope("Aliases");
2223 for (GlobalAlias &GA : SrcModule->aliases()) {
2224 if (!GA.hasName() || isa<GlobalIFunc>(Val: GA.getAliaseeObject()))
2225 continue;
2226 auto GUID = GA.getGUIDOrFallback();
2227 auto MaybeImportType = ImportList.getImportType(FromModule: ModName, GUID);
2228 bool ImportDefinition =
2229 MaybeImportType == GlobalValueSummary::Definition;
2230
2231 LLVM_DEBUG(dbgs() << (MaybeImportType ? "Is" : "Not")
2232 << " importing alias"
2233 << (ImportDefinition
2234 ? " definition "
2235 : (MaybeImportType ? " declaration " : " "))
2236 << GUID << " " << GA.getName() << " from "
2237 << SrcModule->getSourceFileName() << "\n");
2238 if (ImportDefinition) {
2239 if (Error Err = GA.materialize())
2240 return std::move(Err);
2241 // Import alias as a copy of its aliasee.
2242 GlobalObject *GO = GA.getAliaseeObject();
2243 if (Error Err = GO->materialize())
2244 return std::move(Err);
2245 auto *Fn = replaceAliasWithAliasee(SrcModule: SrcModule.get(), GA: &GA);
2246 assert(Fn);
2247 (void)Fn;
2248 LLVM_DEBUG(dbgs()
2249 << "Is importing aliasee fn " << GO->getGUIDOrFallback()
2250 << " " << GO->getName() << " from "
2251 << SrcModule->getSourceFileName() << "\n");
2252 if (Opts.enable_import_metadata ||
2253 EnableMemProfContextDisambiguation) {
2254 // Add 'thinlto_src_module', 'thinlto_src_file', and
2255 // 'thinlto_alias_guid' metadata for statistics, debugging, and
2256 // summary lookup (since Fn retains the aliasee's !guid metadata).
2257 LLVMContext &Ctx = DestModule.getContext();
2258 Fn->setMetadata(
2259 Kind: "thinlto_src_module",
2260 Node: MDNode::get(Context&: Ctx, MDs: {MDString::get(
2261 Context&: Ctx, Str: SrcModule->getModuleIdentifier())}));
2262 Fn->setMetadata(
2263 Kind: "thinlto_src_file",
2264 Node: MDNode::get(
2265 Context&: Ctx, MDs: {MDString::get(Context&: Ctx, Str: SrcModule->getSourceFileName())}));
2266 Fn->setMetadata(
2267 Kind: "thinlto_alias_guid",
2268 Node: MDNode::get(Context&: Ctx, MDs: {ConstantAsMetadata::get(C: ConstantInt::get(
2269 Ty: Type::getInt64Ty(C&: Ctx), V: GUID))}));
2270 }
2271 GlobalsToImport.insert(X: Fn);
2272 } else if (MaybeImportType) {
2273 assert(*MaybeImportType == GlobalValueSummary::Declaration);
2274 if (isa<FunctionType>(Val: GA.getValueType()))
2275 DeclsToImport.push_back(Elt: {&GA, GUID});
2276 }
2277 }
2278 }
2279
2280 // Upgrade debug info after we're done materializing all the globals and we
2281 // have loaded all the required metadata!
2282 UpgradeDebugInfo(M&: *SrcModule);
2283
2284 // Set the partial sample profile ratio in the profile summary module flag
2285 // of the imported source module, if applicable, so that the profile summary
2286 // module flag will match with that of the destination module when it's
2287 // imported.
2288 SrcModule->setPartialSampleProfileRatio(Index);
2289
2290 // Link in the specified functions.
2291 renameModuleForThinLTO(M&: *SrcModule, Index, ClearDSOLocalOnDeclarations,
2292 GlobalsToImport: &GlobalsToImport);
2293
2294 // Record the information needed to create the declarations to import,
2295 // after any promotion and renaming above, since the source module is
2296 // consumed by the IRMover below.
2297 struct DeclInfo {
2298 std::string Name;
2299 FunctionType *Ty;
2300 unsigned AddrSpace;
2301 CallingConv::ID CC;
2302 AttributeList Attrs;
2303 GlobalValue::VisibilityTypes Visibility;
2304 bool DSOLocal;
2305 GlobalValue::GUID GUID;
2306 };
2307 SmallVector<DeclInfo> DeclInfos;
2308 for (auto [GV, GUID] : DeclsToImport) {
2309 assert(!GV->hasLocalLinkage() &&
2310 "Expected imported declaration to be promoted");
2311 const Function *F = dyn_cast<Function>(Val: GV);
2312 if (!F)
2313 F = dyn_cast_or_null<Function>(
2314 Val: cast<GlobalAlias>(Val: GV)->getAliaseeObject());
2315 if (!F)
2316 continue;
2317 DeclInfos.push_back(Elt: {.Name: GV->getName().str(), .Ty: F->getFunctionType(),
2318 .AddrSpace: F->getAddressSpace(), .CC: F->getCallingConv(),
2319 .Attrs: F->getAttributes(), .Visibility: GV->getVisibility(),
2320 .DSOLocal: GV->isDSOLocal(), .GUID: GUID});
2321 }
2322
2323 if (Opts.print_imports) {
2324 for (const auto *GV : GlobalsToImport)
2325 dbgs() << DestModule.getSourceFileName() << ": Import " << GV->getName()
2326 << " from " << SrcModule->getSourceFileName() << "\n";
2327 }
2328
2329 if (Error Err = Mover.move(Src: std::move(SrcModule),
2330 ValuesToLink: GlobalsToImport.getArrayRef(), AddLazyFor: nullptr,
2331 /*IsPerformingImport=*/true))
2332 return createStringError(EC: errc::invalid_argument,
2333 S: Twine("Function Import: link error: ") +
2334 toString(E: std::move(Err)));
2335
2336 ImportedCount += GlobalsToImport.size();
2337 NumImportedModules++;
2338
2339 // Now create the declarations to import, if they don't already exist in
2340 // the destination module. Declarations of direct callees will typically
2341 // already exist, either because the call is in the destination module or
2342 // because the IRMover created them when linking an imported definition
2343 // that references them. Callees reached only via indirect calls (e.g.
2344 // from value profile or MemProf call edges in the summary) have no such IR
2345 // reference, so this is mainly where declarations of those are created.
2346 //
2347 // We create these declarations by hand rather than via the IRMover: the
2348 // IRMover only creates declarations as a side effect of mapping references
2349 // from linked IR, it creates attribute-less declarations for aliases, and
2350 // it does not copy metadata from source definitions.
2351 for (auto &DI : DeclInfos) {
2352 // Record the GUID of the original value, which may differ from the GUID
2353 // computed from the current name if it was a promoted local. This allows
2354 // the declaration to be located via the GUID, e.g. by MemProf ICP.
2355 auto SetGUID = [&](Function *F) {
2356 F->setMetadata(
2357 KindID: LLVMContext::MD_guid,
2358 Node: MDNode::get(
2359 Context&: DestModule.getContext(),
2360 MDs: {ConstantAsMetadata::get(C: ConstantInt::get(
2361 Ty: Type::getInt64Ty(C&: DestModule.getContext()), V: DI.GUID))}));
2362 };
2363 if (GlobalValue *Existing = DestModule.getNamedValue(Name: DI.Name)) {
2364 // A declaration created by the IRMover as a side effect of importing a
2365 // definition that references it (e.g. a vtable initializer) does not
2366 // carry the original GUID, so attach it here.
2367 // TODO: Consider having IRMover propagate !guid metadata onto
2368 // declarations it creates for referenced values (including functions
2369 // and global variables not in DeclInfos), especially if we move toward
2370 // attaching !guid uniformly to all declarations.
2371 if (auto *ExistingF = dyn_cast<Function>(Val: Existing);
2372 ExistingF && ExistingF->isDeclaration() &&
2373 !ExistingF->getMetadata(KindID: LLVMContext::MD_guid))
2374 SetGUID(ExistingF);
2375 continue;
2376 }
2377 Function *F = Function::Create(Ty: DI.Ty, Linkage: GlobalValue::ExternalLinkage,
2378 AddrSpace: DI.AddrSpace, N: DI.Name, M: &DestModule);
2379 F->setCallingConv(DI.CC);
2380 F->setAttributes(DI.Attrs);
2381 // Note that the visibility must be set before dso_local, since
2382 // setDSOLocal(false) is not allowed on an implicitly dso_local value.
2383 F->setVisibility(DI.Visibility);
2384 F->setDSOLocal(DI.DSOLocal);
2385 SetGUID(F);
2386 NumImportedFunctionDecls++;
2387 }
2388 }
2389
2390 internalizeGVsAfterImport(M&: DestModule);
2391
2392 // Protect !implicit.ref-referenced globals imported as available_externally
2393 // from DCE'd. Only needed when globals were actually imported.
2394 if (ImportedGVCount > 0)
2395 protectImplicitRefGlobals(M&: DestModule);
2396
2397 NumImportedFunctions += (ImportedCount - ImportedGVCount);
2398 NumImportedGlobalVars += ImportedGVCount;
2399
2400 // TODO: Print counters for definitions and declarations in the debugging log.
2401 LLVM_DEBUG(dbgs() << "Imported " << ImportedCount - ImportedGVCount
2402 << " functions for Module "
2403 << DestModule.getModuleIdentifier() << "\n");
2404 LLVM_DEBUG(dbgs() << "Imported " << ImportedGVCount
2405 << " global variables for Module "
2406 << DestModule.getModuleIdentifier() << "\n");
2407 return ImportedCount;
2408}
2409
2410static bool doImportingForModuleForTest(
2411 Module &M, function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
2412 isPrevailing) {
2413 const IPOOptions &Opts = getIPOOptions(M);
2414 if (Opts.summary_file.empty())
2415 report_fatal_error(reason: "error: -function-import requires -summary-file\n");
2416 Expected<std::unique_ptr<ModuleSummaryIndex>> IndexPtrOrErr =
2417 getModuleSummaryIndexForFile(Path: Opts.summary_file);
2418 if (!IndexPtrOrErr) {
2419 logAllUnhandledErrors(E: IndexPtrOrErr.takeError(), OS&: errs(),
2420 ErrorBanner: "Error loading file '" + Opts.summary_file + "': ");
2421 return false;
2422 }
2423 std::unique_ptr<ModuleSummaryIndex> Index = std::move(*IndexPtrOrErr);
2424
2425 // First step is collecting the import list.
2426 FunctionImporter::ImportIDTable ImportIDs;
2427 FunctionImporter::ImportMapTy ImportList(ImportIDs);
2428 // If requested, simply import all functions in the index. This is used
2429 // when testing distributed backend handling via the opt tool, when
2430 // we have distributed indexes containing exactly the summaries to import.
2431 if (Opts.import_all_index)
2432 ComputeCrossModuleImportForModuleFromIndexForTest(ModulePath: M.getModuleIdentifier(),
2433 Index: *Index, ImportList);
2434 else
2435 ComputeCrossModuleImportForModuleForTest(ModulePath: M.getModuleIdentifier(),
2436 isPrevailing, Index: *Index, ImportList);
2437
2438 // Conservatively mark all internal values as promoted. This interface is
2439 // only used when doing importing via the function importing pass. The pass
2440 // is only enabled when testing importing via the 'opt' tool, which does
2441 // not do the ThinLink that would normally determine what values to promote.
2442 for (auto &I : *Index) {
2443 for (auto &S : I.second.getSummaryList()) {
2444 if (GlobalValue::isLocalLinkage(Linkage: S->linkage()))
2445 S->setExternalLinkageForTest();
2446 }
2447 }
2448
2449 // Next we need to promote to global scope and rename any local values that
2450 // are potentially exported to other modules.
2451 renameModuleForThinLTO(M, Index: *Index, /*ClearDSOLocalOnDeclarations=*/false,
2452 /*GlobalsToImport=*/nullptr);
2453
2454 // Perform the import now.
2455 auto ModuleLoader = [&M](StringRef Identifier) {
2456 return loadFile(FileName: std::string(Identifier), Context&: M.getContext());
2457 };
2458 FunctionImporter Importer(*Index, ModuleLoader,
2459 /*ClearDSOLocalOnDeclarations=*/false);
2460 Expected<bool> Result = Importer.importFunctions(DestModule&: M, ImportList);
2461
2462 // FIXME: Probably need to propagate Errors through the pass manager.
2463 if (!Result) {
2464 logAllUnhandledErrors(E: Result.takeError(), OS&: errs(),
2465 ErrorBanner: "Error importing module: ");
2466 return true;
2467 }
2468
2469 return true;
2470}
2471
2472PreservedAnalyses FunctionImportPass::run(Module &M,
2473 ModuleAnalysisManager &AM) {
2474 // This is only used for testing the function import pass via opt, where we
2475 // don't have prevailing information from the LTO context available, so just
2476 // conservatively assume everything is prevailing (which is fine for the very
2477 // limited use of prevailing checking in this pass).
2478 auto isPrevailing = [](GlobalValue::GUID, const GlobalValueSummary *) {
2479 return true;
2480 };
2481 if (!doImportingForModuleForTest(M, isPrevailing))
2482 return PreservedAnalyses::all();
2483
2484 return PreservedAnalyses::none();
2485}
2486