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 "llvm/ADT/ArrayRef.h"
15	#include "llvm/ADT/STLExtras.h"
16	#include "llvm/ADT/SetVector.h"
17	#include "llvm/ADT/SmallVector.h"
18	#include "llvm/ADT/Statistic.h"
19	#include "llvm/ADT/StringRef.h"
20	#include "llvm/Bitcode/BitcodeReader.h"
21	#include "llvm/IR/AutoUpgrade.h"
22	#include "llvm/IR/Constants.h"
23	#include "llvm/IR/Function.h"
24	#include "llvm/IR/GlobalAlias.h"
25	#include "llvm/IR/GlobalObject.h"
26	#include "llvm/IR/GlobalValue.h"
27	#include "llvm/IR/GlobalVariable.h"
28	#include "llvm/IR/Metadata.h"
29	#include "llvm/IR/Module.h"
30	#include "llvm/IR/ModuleSummaryIndex.h"
31	#include "llvm/IRReader/IRReader.h"
32	#include "llvm/Linker/IRMover.h"
33	#include "llvm/Support/Casting.h"
34	#include "llvm/Support/CommandLine.h"
35	#include "llvm/Support/Debug.h"
36	#include "llvm/Support/Errc.h"
37	#include "llvm/Support/Error.h"
38	#include "llvm/Support/ErrorHandling.h"
39	#include "llvm/Support/FileSystem.h"
40	#include "llvm/Support/JSON.h"
41	#include "llvm/Support/SourceMgr.h"
42	#include "llvm/Support/raw_ostream.h"
43	#include "llvm/Transforms/IPO/Internalize.h"
44	#include "llvm/Transforms/Utils/Cloning.h"
45	#include "llvm/Transforms/Utils/FunctionImportUtils.h"
46	#include "llvm/Transforms/Utils/ValueMapper.h"
47	#include <cassert>
48	#include <memory>
49	#include <set>
50	#include <string>
51	#include <system_error>
52	#include <tuple>
53	#include <utility>
54
55	using namespace llvm;
56
57	#define DEBUG_TYPE "function-import"
58
59	STATISTIC(NumImportedFunctionsThinLink,
60	"Number of functions thin link decided to import");
61	STATISTIC(NumImportedHotFunctionsThinLink,
62	"Number of hot functions thin link decided to import");
63	STATISTIC(NumImportedCriticalFunctionsThinLink,
64	"Number of critical functions thin link decided to import");
65	STATISTIC(NumImportedGlobalVarsThinLink,
66	"Number of global variables thin link decided to import");
67	STATISTIC(NumImportedFunctions, "Number of functions imported in backend");
68	STATISTIC(NumImportedGlobalVars,
69	"Number of global variables imported in backend");
70	STATISTIC(NumImportedModules, "Number of modules imported from");
71	STATISTIC(NumDeadSymbols, "Number of dead stripped symbols in index");
72	STATISTIC(NumLiveSymbols, "Number of live symbols in index");
73
74	/// Limit on instruction count of imported functions.
75	static cl::opt<unsigned> ImportInstrLimit(
76	"import-instr-limit", cl::init(Val: 100), cl::Hidden, cl::value_desc("N"),
77	cl::desc("Only import functions with less than N instructions"));
78
79	static cl::opt<int> ImportCutoff(
80	"import-cutoff", cl::init(Val: -1), cl::Hidden, cl::value_desc("N"),
81	cl::desc("Only import first N functions if N>=0 (default -1)"));
82
83	static cl::opt<bool>
84	ForceImportAll("force-import-all", cl::init(Val: false), cl::Hidden,
85	cl::desc("Import functions with noinline attribute"));
86
87	static cl::opt<float>
88	ImportInstrFactor("import-instr-evolution-factor", cl::init(Val: 0.7),
89	cl::Hidden, cl::value_desc("x"),
90	cl::desc("As we import functions, multiply the "
91	"`import-instr-limit` threshold by this factor "
92	"before processing newly imported functions"));
93
94	static cl::opt<float> ImportHotInstrFactor(
95	"import-hot-evolution-factor", cl::init(Val: 1.0), cl::Hidden,
96	cl::value_desc("x"),
97	cl::desc("As we import functions called from hot callsite, multiply the "
98	"`import-instr-limit` threshold by this factor "
99	"before processing newly imported functions"));
100
101	static cl::opt<float> ImportHotMultiplier(
102	"import-hot-multiplier", cl::init(Val: 10.0), cl::Hidden, cl::value_desc("x"),
103	cl::desc("Multiply the `import-instr-limit` threshold for hot callsites"));
104
105	static cl::opt<float> ImportCriticalMultiplier(
106	"import-critical-multiplier", cl::init(Val: 100.0), cl::Hidden,
107	cl::value_desc("x"),
108	cl::desc(
109	"Multiply the `import-instr-limit` threshold for critical callsites"));
110
111	// FIXME: This multiplier was not really tuned up.
112	static cl::opt<float> ImportColdMultiplier(
113	"import-cold-multiplier", cl::init(Val: 0), cl::Hidden, cl::value_desc("N"),
114	cl::desc("Multiply the `import-instr-limit` threshold for cold callsites"));
115
116	static cl::opt<bool> PrintImports("print-imports", cl::init(Val: false), cl::Hidden,
117	cl::desc("Print imported functions"));
118
119	static cl::opt<bool> PrintImportFailures(
120	"print-import-failures", cl::init(Val: false), cl::Hidden,
121	cl::desc("Print information for functions rejected for importing"));
122
123	static cl::opt<bool> ComputeDead("compute-dead", cl::init(Val: true), cl::Hidden,
124	cl::desc("Compute dead symbols"));
125
126	static cl::opt<bool> EnableImportMetadata(
127	"enable-import-metadata", cl::init(Val: false), cl::Hidden,
128	cl::desc("Enable import metadata like 'thinlto_src_module' and "
129	"'thinlto_src_file'"));
130
131	/// Summary file to use for function importing when using -function-import from
132	/// the command line.
133	static cl::opt<std::string>
134	SummaryFile("summary-file",
135	cl::desc("The summary file to use for function importing."));
136
137	/// Used when testing importing from distributed indexes via opt
138	// -function-import.
139	static cl::opt<bool>
140	ImportAllIndex("import-all-index",
141	cl::desc("Import all external functions in index."));
142
143	/// Pass a workload description file - an example of workload would be the
144	/// functions executed to satisfy a RPC request. A workload is defined by a root
145	/// function and the list of functions that are (frequently) needed to satisfy
146	/// it. The module that defines the root will have all those functions imported.
147	/// The file contains a JSON dictionary. The keys are root functions, the values
148	/// are lists of functions to import in the module defining the root. It is
149	/// assumed -funique-internal-linkage-names was used, thus ensuring function
150	/// names are unique even for local linkage ones.
151	static cl::opt<std::string> WorkloadDefinitions(
152	"thinlto-workload-def",
153	cl::desc("Pass a workload definition. This is a file containing a JSON "
154	"dictionary. The keys are root functions, the values are lists of "
155	"functions to import in the module defining the root. It is "
156	"assumed -funique-internal-linkage-names was used, to ensure "
157	"local linkage functions have unique names. For example: \n"
158	"{\n"
159	" \"rootFunction_1\": [\"function_to_import_1\", "
160	"\"function_to_import_2\"], \n"
161	" \"rootFunction_2\": [\"function_to_import_3\", "
162	"\"function_to_import_4\"] \n"
163	"}"),
164	cl::Hidden);
165
166	namespace llvm {
167	extern cl::opt<bool> EnableMemProfContextDisambiguation;
168	}
169
170	// Load lazily a module from \p FileName in \p Context.
171	static std::unique_ptr<Module> loadFile(const std::string &FileName,
172	LLVMContext &Context) {
173	SMDiagnostic Err;
174	LLVM_DEBUG(dbgs() << "Loading '" << FileName << "'\n");
175	// Metadata isn't loaded until functions are imported, to minimize
176	// the memory overhead.
177	std::unique_ptr<Module> Result =
178	getLazyIRFileModule(Filename: FileName, Err, Context,
179	/* ShouldLazyLoadMetadata = */ true);
180	if (!Result) {
181	Err.print(ProgName: "function-import", S&: errs());
182	report_fatal_error(reason: "Abort");
183	}
184
185	return Result;
186	}
187
188	/// Given a list of possible callee implementation for a call site, qualify the
189	/// legality of importing each. The return is a range of pairs. Each pair
190	/// corresponds to a candidate. The first value is the ImportFailureReason for
191	/// that candidate, the second is the candidate.
192	static auto qualifyCalleeCandidates(
193	const ModuleSummaryIndex &Index,
194	ArrayRef<std::unique_ptr<GlobalValueSummary>> CalleeSummaryList,
195	StringRef CallerModulePath) {
196	return llvm::map_range(
197	C&: CalleeSummaryList,
198	F: [&Index, CalleeSummaryList,
199	CallerModulePath](const std::unique_ptr<GlobalValueSummary> &SummaryPtr)
200	-> std::pair<FunctionImporter::ImportFailureReason,
201	const GlobalValueSummary *> {
202	auto *GVSummary = SummaryPtr.get();
203	if (!Index.isGlobalValueLive(GVS: GVSummary))
204	return {FunctionImporter::ImportFailureReason::NotLive, GVSummary};
205
206	if (GlobalValue::isInterposableLinkage(Linkage: GVSummary->linkage()))
207	return {FunctionImporter::ImportFailureReason::InterposableLinkage,
208	GVSummary};
209
210	auto *Summary = dyn_cast<FunctionSummary>(Val: GVSummary->getBaseObject());
211
212	// Ignore any callees that aren't actually functions. This could happen
213	// in the case of GUID hash collisions. It could also happen in theory
214	// for SamplePGO profiles collected on old versions of the code after
215	// renaming, since we synthesize edges to any inlined callees appearing
216	// in the profile.
217	if (!Summary)
218	return {FunctionImporter::ImportFailureReason::GlobalVar, GVSummary};
219
220	// If this is a local function, make sure we import the copy
221	// in the caller's module. The only time a local function can
222	// share an entry in the index is if there is a local with the same name
223	// in another module that had the same source file name (in a different
224	// directory), where each was compiled in their own directory so there
225	// was not distinguishing path.
226	// However, do the import from another module if there is only one
227	// entry in the list - in that case this must be a reference due
228	// to indirect call profile data, since a function pointer can point to
229	// a local in another module.
230	if (GlobalValue::isLocalLinkage(Linkage: Summary->linkage()) &&
231	CalleeSummaryList.size() > 1 &&
232	Summary->modulePath() != CallerModulePath)
233	return {
234	FunctionImporter::ImportFailureReason::LocalLinkageNotInModule,
235	GVSummary};
236
237	// Skip if it isn't legal to import (e.g. may reference unpromotable
238	// locals).
239	if (Summary->notEligibleToImport())
240	return {FunctionImporter::ImportFailureReason::NotEligible,
241	GVSummary};
242
243	return {FunctionImporter::ImportFailureReason::None, GVSummary};
244	});
245	}
246
247	/// Given a list of possible callee implementation for a call site, select one
248	/// that fits the \p Threshold. If none are found, the Reason will give the last
249	/// reason for the failure (last, in the order of CalleeSummaryList entries).
250	///
251	/// FIXME: select "best" instead of first that fits. But what is "best"?
252	/// - The smallest: more likely to be inlined.
253	/// - The one with the least outgoing edges (already well optimized).
254	/// - One from a module already being imported from in order to reduce the
255	/// number of source modules parsed/linked.
256	/// - One that has PGO data attached.
257	/// - [insert you fancy metric here]
258	static const GlobalValueSummary *
259	selectCallee(const ModuleSummaryIndex &Index,
260	ArrayRef<std::unique_ptr<GlobalValueSummary>> CalleeSummaryList,
261	unsigned Threshold, StringRef CallerModulePath,
262	FunctionImporter::ImportFailureReason &Reason) {
263	auto QualifiedCandidates =
264	qualifyCalleeCandidates(Index, CalleeSummaryList, CallerModulePath);
265	for (auto QualifiedValue : QualifiedCandidates) {
266	Reason = QualifiedValue.first;
267	if (Reason != FunctionImporter::ImportFailureReason::None)
268	continue;
269	auto *Summary =
270	cast<FunctionSummary>(Val: QualifiedValue.second->getBaseObject());
271
272	if ((Summary->instCount() > Threshold) && !Summary->fflags().AlwaysInline &&
273	!ForceImportAll) {
274	Reason = FunctionImporter::ImportFailureReason::TooLarge;
275	continue;
276	}
277
278	// Don't bother importing if we can't inline it anyway.
279	if (Summary->fflags().NoInline && !ForceImportAll) {
280	Reason = FunctionImporter::ImportFailureReason::NoInline;
281	continue;
282	}
283
284	return Summary;
285	}
286	return nullptr;
287	}
288
289	namespace {
290
291	using EdgeInfo = std::tuple<const FunctionSummary *, unsigned /* Threshold */>;
292
293	} // anonymous namespace
294
295	/// Import globals referenced by a function or other globals that are being
296	/// imported, if importing such global is possible.
297	class GlobalsImporter final {
298	const ModuleSummaryIndex &Index;
299	const GVSummaryMapTy &DefinedGVSummaries;
300	function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
301	IsPrevailing;
302	FunctionImporter::ImportMapTy &ImportList;
303	DenseMap<StringRef, FunctionImporter::ExportSetTy> *const ExportLists;
304
305	bool shouldImportGlobal(const ValueInfo &VI) {
306	const auto &GVS = DefinedGVSummaries.find(Val: VI.getGUID());
307	if (GVS == DefinedGVSummaries.end())
308	return true;
309	// We should not skip import if the module contains a non-prevailing
310	// definition with interposable linkage type. This is required for
311	// correctness in the situation where there is a prevailing def available
312	// for import and marked read-only. In this case, the non-prevailing def
313	// will be converted to a declaration, while the prevailing one becomes
314	// internal, thus no definitions will be available for linking. In order to
315	// prevent undefined symbol link error, the prevailing definition must be
316	// imported.
317	// FIXME: Consider adding a check that the suitable prevailing definition
318	// exists and marked read-only.
319	if (VI.getSummaryList().size() > 1 &&
320	GlobalValue::isInterposableLinkage(Linkage: GVS->second->linkage()) &&
321	!IsPrevailing(VI.getGUID(), GVS->second))
322	return true;
323
324	return false;
325	}
326
327	void
328	onImportingSummaryImpl(const GlobalValueSummary &Summary,
329	SmallVectorImpl<const GlobalVarSummary *> &Worklist) {
330	for (const auto &VI : Summary.refs()) {
331	if (!shouldImportGlobal(VI)) {
332	LLVM_DEBUG(
333	dbgs() << "Ref ignored! Target already in destination module.\n");
334	continue;
335	}
336
337	LLVM_DEBUG(dbgs() << " ref -> " << VI << "\n");
338
339	// If this is a local variable, make sure we import the copy
340	// in the caller's module. The only time a local variable can
341	// share an entry in the index is if there is a local with the same name
342	// in another module that had the same source file name (in a different
343	// directory), where each was compiled in their own directory so there
344	// was not distinguishing path.
345	auto LocalNotInModule =
346	[&](const GlobalValueSummary *RefSummary) -> bool {
347	return GlobalValue::isLocalLinkage(Linkage: RefSummary->linkage()) &&
348	RefSummary->modulePath() != Summary.modulePath();
349	};
350
351	for (const auto &RefSummary : VI.getSummaryList()) {
352	const auto *GVS = dyn_cast<GlobalVarSummary>(Val: RefSummary.get());
353	// Functions could be referenced by global vars - e.g. a vtable; but we
354	// don't currently imagine a reason those would be imported here, rather
355	// than as part of the logic deciding which functions to import (i.e.
356	// based on profile information). Should we decide to handle them here,
357	// we can refactor accordingly at that time.
358	if (!GVS || !Index.canImportGlobalVar(S: GVS, /* AnalyzeRefs */ true) ||
359	LocalNotInModule(GVS))
360	continue;
361	auto ILI = ImportList[RefSummary->modulePath()].insert(x: VI.getGUID());
362	// Only update stat and exports if we haven't already imported this
363	// variable.
364	if (!ILI.second)
365	break;
366	NumImportedGlobalVarsThinLink++;
367	// Any references made by this variable will be marked exported
368	// later, in ComputeCrossModuleImport, after import decisions are
369	// complete, which is more efficient than adding them here.
370	if (ExportLists)
371	(*ExportLists)[RefSummary->modulePath()].insert(V: VI);
372
373	// If variable is not writeonly we attempt to recursively analyze
374	// its references in order to import referenced constants.
375	if (!Index.isWriteOnly(GVS))
376	Worklist.emplace_back(Args&: GVS);
377	break;
378	}
379	}
380	}
381
382	public:
383	GlobalsImporter(
384	const ModuleSummaryIndex &Index, const GVSummaryMapTy &DefinedGVSummaries,
385	function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
386	IsPrevailing,
387	FunctionImporter::ImportMapTy &ImportList,
388	DenseMap<StringRef, FunctionImporter::ExportSetTy> *ExportLists)
389	: Index(Index), DefinedGVSummaries(DefinedGVSummaries),
390	IsPrevailing(IsPrevailing), ImportList(ImportList),
391	ExportLists(ExportLists) {}
392
393	void onImportingSummary(const GlobalValueSummary &Summary) {
394	SmallVector<const GlobalVarSummary *, 128> Worklist;
395	onImportingSummaryImpl(Summary, Worklist);
396	while (!Worklist.empty())
397	onImportingSummaryImpl(Summary: *Worklist.pop_back_val(), Worklist);
398	}
399	};
400
401	static const char *getFailureName(FunctionImporter::ImportFailureReason Reason);
402
403	/// Determine the list of imports and exports for each module.
404	class ModuleImportsManager {
405	protected:
406	function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
407	IsPrevailing;
408	const ModuleSummaryIndex &Index;
409	DenseMap<StringRef, FunctionImporter::ExportSetTy> *const ExportLists;
410
411	ModuleImportsManager(
412	function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
413	IsPrevailing,
414	const ModuleSummaryIndex &Index,
415	DenseMap<StringRef, FunctionImporter::ExportSetTy> *ExportLists = nullptr)
416	: IsPrevailing(IsPrevailing), Index(Index), ExportLists(ExportLists) {}
417
418	public:
419	virtual ~ModuleImportsManager() = default;
420
421	/// Given the list of globals defined in a module, compute the list of imports
422	/// as well as the list of "exports", i.e. the list of symbols referenced from
423	/// another module (that may require promotion).
424	virtual void
425	computeImportForModule(const GVSummaryMapTy &DefinedGVSummaries,
426	StringRef ModName,
427	FunctionImporter::ImportMapTy &ImportList);
428
429	static std::unique_ptr<ModuleImportsManager>
430	create(function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
431	IsPrevailing,
432	const ModuleSummaryIndex &Index,
433	DenseMap<StringRef, FunctionImporter::ExportSetTy> *ExportLists =
434	nullptr);
435	};
436
437	/// A ModuleImportsManager that operates based on a workload definition (see
438	/// -thinlto-workload-def). For modules that do not define workload roots, it
439	/// applies the base ModuleImportsManager import policy.
440	class WorkloadImportsManager : public ModuleImportsManager {
441	// Keep a module name -> value infos to import association. We use it to
442	// determine if a module's import list should be done by the base
443	// ModuleImportsManager or by us.
444	StringMap<DenseSet<ValueInfo>> Workloads;
445
446	void
447	computeImportForModule(const GVSummaryMapTy &DefinedGVSummaries,
448	StringRef ModName,
449	FunctionImporter::ImportMapTy &ImportList) override {
450	auto SetIter = Workloads.find(Key: ModName);
451	if (SetIter == Workloads.end()) {
452	LLVM_DEBUG(dbgs() << "[Workload] " << ModName
453	<< " does not contain the root of any context.\n");
454	return ModuleImportsManager::computeImportForModule(DefinedGVSummaries,
455	ModName, ImportList);
456	}
457	LLVM_DEBUG(dbgs() << "[Workload] " << ModName
458	<< " contains the root(s) of context(s).\n");
459
460	GlobalsImporter GVI(Index, DefinedGVSummaries, IsPrevailing, ImportList,
461	ExportLists);
462	auto &ValueInfos = SetIter->second;
463	SmallVector<EdgeInfo, 128> GlobWorklist;
464	for (auto &VI : llvm::make_early_inc_range(Range&: ValueInfos)) {
465	auto It = DefinedGVSummaries.find(Val: VI.getGUID());
466	if (It != DefinedGVSummaries.end() &&
467	IsPrevailing(VI.getGUID(), It->second)) {
468	LLVM_DEBUG(
469	dbgs() << "[Workload] " << VI.name()
470	<< " has the prevailing variant already in the module "
471	<< ModName << ". No need to import\n");
472	continue;
473	}
474	auto Candidates =
475	qualifyCalleeCandidates(Index, CalleeSummaryList: VI.getSummaryList(), CallerModulePath: ModName);
476
477	const GlobalValueSummary *GVS = nullptr;
478	auto PotentialCandidates = llvm::map_range(
479	C: llvm::make_filter_range(
480	Range&: Candidates,
481	Pred: [&](const auto &Candidate) {
482	LLVM_DEBUG(dbgs() << "[Workflow] Candidate for " << VI.name()
483	<< " from " << Candidate.second->modulePath()
484	<< " ImportFailureReason: "
485	<< getFailureName(Candidate.first) << "\n");
486	return Candidate.first ==
487	FunctionImporter::ImportFailureReason::None;
488	}),
489	F: [](const auto &Candidate) { return Candidate.second; });
490	if (PotentialCandidates.empty()) {
491	LLVM_DEBUG(dbgs() << "[Workload] Not importing " << VI.name()
492	<< " because can't find eligible Callee. Guid is: "
493	<< Function::getGUID(VI.name()) << "\n");
494	continue;
495	}
496	/// We will prefer importing the prevailing candidate, if not, we'll
497	/// still pick the first available candidate. The reason we want to make
498	/// sure we do import the prevailing candidate is because the goal of
499	/// workload-awareness is to enable optimizations specializing the call
500	/// graph of that workload. Suppose a function is already defined in the
501	/// module, but it's not the prevailing variant. Suppose also we do not
502	/// inline it (in fact, if it were interposable, we can't inline it),
503	/// but we could specialize it to the workload in other ways. However,
504	/// the linker would drop it in the favor of the prevailing copy.
505	/// Instead, by importing the prevailing variant (assuming also the use
506	/// of `-avail-extern-to-local`), we keep the specialization. We could
507	/// alteranatively make the non-prevailing variant local, but the
508	/// prevailing one is also the one for which we would have previously
509	/// collected profiles, making it preferrable.
510	auto PrevailingCandidates = llvm::make_filter_range(
511	Range&: PotentialCandidates, Pred: [&](const auto *Candidate) {
512	return IsPrevailing(VI.getGUID(), Candidate);
513	});
514	if (PrevailingCandidates.empty()) {
515	GVS = *PotentialCandidates.begin();
516	if (!llvm::hasSingleElement(C&: PotentialCandidates) &&
517	GlobalValue::isLocalLinkage(Linkage: GVS->linkage()))
518	LLVM_DEBUG(
519	dbgs()
520	<< "[Workload] Found multiple non-prevailing candidates for "
521	<< VI.name()
522	<< ". This is unexpected. Are module paths passed to the "
523	"compiler unique for the modules passed to the linker?");
524	// We could in theory have multiple (interposable) copies of a symbol
525	// when there is no prevailing candidate, if say the prevailing copy was
526	// in a native object being linked in. However, we should in theory be
527	// marking all of these non-prevailing IR copies dead in that case, in
528	// which case they won't be candidates.
529	assert(GVS->isLive());
530	} else {
531	assert(llvm::hasSingleElement(PrevailingCandidates));
532	GVS = *PrevailingCandidates.begin();
533	}
534
535	auto ExportingModule = GVS->modulePath();
536	// We checked that for the prevailing case, but if we happen to have for
537	// example an internal that's defined in this module, it'd have no
538	// PrevailingCandidates.
539	if (ExportingModule == ModName) {
540	LLVM_DEBUG(dbgs() << "[Workload] Not importing " << VI.name()
541	<< " because its defining module is the same as the "
542	"current module\n");
543	continue;
544	}
545	LLVM_DEBUG(dbgs() << "[Workload][Including]" << VI.name() << " from "
546	<< ExportingModule << " : "
547	<< Function::getGUID(VI.name()) << "\n");
548	ImportList[ExportingModule].insert(x: VI.getGUID());
549	GVI.onImportingSummary(Summary: *GVS);
550	if (ExportLists)
551	(*ExportLists)[ExportingModule].insert(V: VI);
552	}
553	LLVM_DEBUG(dbgs() << "[Workload] Done\n");
554	}
555
556	public:
557	WorkloadImportsManager(
558	function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
559	IsPrevailing,
560	const ModuleSummaryIndex &Index,
561	DenseMap<StringRef, FunctionImporter::ExportSetTy> *ExportLists)
562	: ModuleImportsManager(IsPrevailing, Index, ExportLists) {
563	// Since the workload def uses names, we need a quick lookup
564	// name->ValueInfo.
565	StringMap<ValueInfo> NameToValueInfo;
566	StringSet<> AmbiguousNames;
567	for (auto &I : Index) {
568	ValueInfo VI = Index.getValueInfo(R: I);
569	if (!NameToValueInfo.insert(KV: std::make_pair(x: VI.name(), y&: VI)).second)
570	LLVM_DEBUG(AmbiguousNames.insert(VI.name()));
571	}
572	auto DbgReportIfAmbiguous = [&](StringRef Name) {
573	LLVM_DEBUG(if (AmbiguousNames.count(Name) > 0) {
574	dbgs() << "[Workload] Function name " << Name
575	<< " present in the workload definition is ambiguous. Consider "
576	"compiling with -funique-internal-linkage-names.";
577	});
578	};
579	std::error_code EC;
580	auto BufferOrErr = MemoryBuffer::getFileOrSTDIN(Filename: WorkloadDefinitions);
581	if (std::error_code EC = BufferOrErr.getError()) {
582	report_fatal_error(reason: "Failed to open context file");
583	return;
584	}
585	auto Buffer = std::move(BufferOrErr.get());
586	std::map<std::string, std::vector<std::string>> WorkloadDefs;
587	json::Path::Root NullRoot;
588	// The JSON is supposed to contain a dictionary matching the type of
589	// WorkloadDefs. For example:
590	// {
591	// "rootFunction_1": ["function_to_import_1", "function_to_import_2"],
592	// "rootFunction_2": ["function_to_import_3", "function_to_import_4"]
593	// }
594	auto Parsed = json::parse(JSON: Buffer->getBuffer());
595	if (!Parsed)
596	report_fatal_error(Err: Parsed.takeError());
597	if (!json::fromJSON(E: *Parsed, Out&: WorkloadDefs, P: NullRoot))
598	report_fatal_error(reason: "Invalid thinlto contextual profile format.");
599	for (const auto &Workload : WorkloadDefs) {
600	const auto &Root = Workload.first;
601	DbgReportIfAmbiguous(Root);
602	LLVM_DEBUG(dbgs() << "[Workload] Root: " << Root << "\n");
603	const auto &AllCallees = Workload.second;
604	auto RootIt = NameToValueInfo.find(Key: Root);
605	if (RootIt == NameToValueInfo.end()) {
606	LLVM_DEBUG(dbgs() << "[Workload] Root " << Root
607	<< " not found in this linkage unit.\n");
608	continue;
609	}
610	auto RootVI = RootIt->second;
611	if (RootVI.getSummaryList().size() != 1) {
612	LLVM_DEBUG(dbgs() << "[Workload] Root " << Root
613	<< " should have exactly one summary, but has "
614	<< RootVI.getSummaryList().size() << ". Skipping.\n");
615	continue;
616	}
617	StringRef RootDefiningModule =
618	RootVI.getSummaryList().front()->modulePath();
619	LLVM_DEBUG(dbgs() << "[Workload] Root defining module for " << Root
620	<< " is : " << RootDefiningModule << "\n");
621	auto &Set = Workloads[RootDefiningModule];
622	for (const auto &Callee : AllCallees) {
623	LLVM_DEBUG(dbgs() << "[Workload] " << Callee << "\n");
624	DbgReportIfAmbiguous(Callee);
625	auto ElemIt = NameToValueInfo.find(Key: Callee);
626	if (ElemIt == NameToValueInfo.end()) {
627	LLVM_DEBUG(dbgs() << "[Workload] " << Callee << " not found\n");
628	continue;
629	}
630	Set.insert(V: ElemIt->second);
631	}
632	LLVM_DEBUG({
633	dbgs() << "[Workload] Root: " << Root << " we have " << Set.size()
634	<< " distinct callees.\n";
635	for (const auto &VI : Set) {
636	dbgs() << "[Workload] Root: " << Root
637	<< " Would include: " << VI.getGUID() << "\n";
638	}
639	});
640	}
641	}
642	};
643
644	std::unique_ptr<ModuleImportsManager> ModuleImportsManager::create(
645	function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
646	IsPrevailing,
647	const ModuleSummaryIndex &Index,
648	DenseMap<StringRef, FunctionImporter::ExportSetTy> *ExportLists) {
649	if (WorkloadDefinitions.empty()) {
650	LLVM_DEBUG(dbgs() << "[Workload] Using the regular imports manager.\n");
651	return std::unique_ptr<ModuleImportsManager>(
652	new ModuleImportsManager(IsPrevailing, Index, ExportLists));
653	}
654	LLVM_DEBUG(dbgs() << "[Workload] Using the contextual imports manager.\n");
655	return std::make_unique<WorkloadImportsManager>(args&: IsPrevailing, args: Index,
656	args&: ExportLists);
657	}
658
659	static const char *
660	getFailureName(FunctionImporter::ImportFailureReason Reason) {
661	switch (Reason) {
662	case FunctionImporter::ImportFailureReason::None:
663	return "None";
664	case FunctionImporter::ImportFailureReason::GlobalVar:
665	return "GlobalVar";
666	case FunctionImporter::ImportFailureReason::NotLive:
667	return "NotLive";
668	case FunctionImporter::ImportFailureReason::TooLarge:
669	return "TooLarge";
670	case FunctionImporter::ImportFailureReason::InterposableLinkage:
671	return "InterposableLinkage";
672	case FunctionImporter::ImportFailureReason::LocalLinkageNotInModule:
673	return "LocalLinkageNotInModule";
674	case FunctionImporter::ImportFailureReason::NotEligible:
675	return "NotEligible";
676	case FunctionImporter::ImportFailureReason::NoInline:
677	return "NoInline";
678	}
679	llvm_unreachable("invalid reason");
680	}
681
682	/// Compute the list of functions to import for a given caller. Mark these
683	/// imported functions and the symbols they reference in their source module as
684	/// exported from their source module.
685	static void computeImportForFunction(
686	const FunctionSummary &Summary, const ModuleSummaryIndex &Index,
687	const unsigned Threshold, const GVSummaryMapTy &DefinedGVSummaries,
688	function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
689	isPrevailing,
690	SmallVectorImpl<EdgeInfo> &Worklist, GlobalsImporter &GVImporter,
691	FunctionImporter::ImportMapTy &ImportList,
692	DenseMap<StringRef, FunctionImporter::ExportSetTy> *ExportLists,
693	FunctionImporter::ImportThresholdsTy &ImportThresholds) {
694	GVImporter.onImportingSummary(Summary);
695	static int ImportCount = 0;
696	for (const auto &Edge : Summary.calls()) {
697	ValueInfo VI = Edge.first;
698	LLVM_DEBUG(dbgs() << " edge -> " << VI << " Threshold:" << Threshold
699	<< "\n");
700
701	if (ImportCutoff >= 0 && ImportCount >= ImportCutoff) {
702	LLVM_DEBUG(dbgs() << "ignored! import-cutoff value of " << ImportCutoff
703	<< " reached.\n");
704	continue;
705	}
706
707	if (DefinedGVSummaries.count(Val: VI.getGUID())) {
708	// FIXME: Consider not skipping import if the module contains
709	// a non-prevailing def with interposable linkage. The prevailing copy
710	// can safely be imported (see shouldImportGlobal()).
711	LLVM_DEBUG(dbgs() << "ignored! Target already in destination module.\n");
712	continue;
713	}
714
715	auto GetBonusMultiplier = [](CalleeInfo::HotnessType Hotness) -> float {
716	if (Hotness == CalleeInfo::HotnessType::Hot)
717	return ImportHotMultiplier;
718	if (Hotness == CalleeInfo::HotnessType::Cold)
719	return ImportColdMultiplier;
720	if (Hotness == CalleeInfo::HotnessType::Critical)
721	return ImportCriticalMultiplier;
722	return 1.0;
723	};
724
725	const auto NewThreshold =
726	Threshold * GetBonusMultiplier(Edge.second.getHotness());
727
728	auto IT = ImportThresholds.insert(KV: std::make_pair(
729	x: VI.getGUID(), y: std::make_tuple(args: NewThreshold, args: nullptr, args: nullptr)));
730	bool PreviouslyVisited = !IT.second;
731	auto &ProcessedThreshold = std::get<0>(t&: IT.first->second);
732	auto &CalleeSummary = std::get<1>(t&: IT.first->second);
733	auto &FailureInfo = std::get<2>(t&: IT.first->second);
734
735	bool IsHotCallsite =
736	Edge.second.getHotness() == CalleeInfo::HotnessType::Hot;
737	bool IsCriticalCallsite =
738	Edge.second.getHotness() == CalleeInfo::HotnessType::Critical;
739
740	const FunctionSummary *ResolvedCalleeSummary = nullptr;
741	if (CalleeSummary) {
742	assert(PreviouslyVisited);
743	// Since the traversal of the call graph is DFS, we can revisit a function
744	// a second time with a higher threshold. In this case, it is added back
745	// to the worklist with the new threshold (so that its own callee chains
746	// can be considered with the higher threshold).
747	if (NewThreshold <= ProcessedThreshold) {
748	LLVM_DEBUG(
749	dbgs() << "ignored! Target was already imported with Threshold "
750	<< ProcessedThreshold << "\n");
751	continue;
752	}
753	// Update with new larger threshold.
754	ProcessedThreshold = NewThreshold;
755	ResolvedCalleeSummary = cast<FunctionSummary>(Val: CalleeSummary);
756	} else {
757	// If we already rejected importing a callee at the same or higher
758	// threshold, don't waste time calling selectCallee.
759	if (PreviouslyVisited && NewThreshold <= ProcessedThreshold) {
760	LLVM_DEBUG(
761	dbgs() << "ignored! Target was already rejected with Threshold "
762	<< ProcessedThreshold << "\n");
763	if (PrintImportFailures) {
764	assert(FailureInfo &&
765	"Expected FailureInfo for previously rejected candidate");
766	FailureInfo->Attempts++;
767	}
768	continue;
769	}
770
771	FunctionImporter::ImportFailureReason Reason{};
772	CalleeSummary = selectCallee(Index, CalleeSummaryList: VI.getSummaryList(), Threshold: NewThreshold,
773	CallerModulePath: Summary.modulePath(), Reason);
774	if (!CalleeSummary) {
775	// Update with new larger threshold if this was a retry (otherwise
776	// we would have already inserted with NewThreshold above). Also
777	// update failure info if requested.
778	if (PreviouslyVisited) {
779	ProcessedThreshold = NewThreshold;
780	if (PrintImportFailures) {
781	assert(FailureInfo &&
782	"Expected FailureInfo for previously rejected candidate");
783	FailureInfo->Reason = Reason;
784	FailureInfo->Attempts++;
785	FailureInfo->MaxHotness =
786	std::max(a: FailureInfo->MaxHotness, b: Edge.second.getHotness());
787	}
788	} else if (PrintImportFailures) {
789	assert(!FailureInfo &&
790	"Expected no FailureInfo for newly rejected candidate");
791	FailureInfo = std::make_unique<FunctionImporter::ImportFailureInfo>(
792	args&: VI, args: Edge.second.getHotness(), args&: Reason, args: 1);
793	}
794	if (ForceImportAll) {
795	std::string Msg = std::string("Failed to import function ") +
796	VI.name().str() + " due to " +
797	getFailureName(Reason);
798	auto Error = make_error<StringError>(
799	Args&: Msg, Args: make_error_code(E: errc::not_supported));
800	logAllUnhandledErrors(E: std::move(Error), OS&: errs(),
801	ErrorBanner: "Error importing module: ");
802	break;
803	} else {
804	LLVM_DEBUG(dbgs()
805	<< "ignored! No qualifying callee with summary found.\n");
806	continue;
807	}
808	}
809
810	// "Resolve" the summary
811	CalleeSummary = CalleeSummary->getBaseObject();
812	ResolvedCalleeSummary = cast<FunctionSummary>(Val: CalleeSummary);
813
814	assert((ResolvedCalleeSummary->fflags().AlwaysInline || ForceImportAll ||
815	(ResolvedCalleeSummary->instCount() <= NewThreshold)) &&
816	"selectCallee() didn't honor the threshold");
817
818	auto ExportModulePath = ResolvedCalleeSummary->modulePath();
819	auto ILI = ImportList[ExportModulePath].insert(x: VI.getGUID());
820	// We previously decided to import this GUID definition if it was already
821	// inserted in the set of imports from the exporting module.
822	bool PreviouslyImported = !ILI.second;
823	if (!PreviouslyImported) {
824	NumImportedFunctionsThinLink++;
825	if (IsHotCallsite)
826	NumImportedHotFunctionsThinLink++;
827	if (IsCriticalCallsite)
828	NumImportedCriticalFunctionsThinLink++;
829	}
830
831	// Any calls/references made by this function will be marked exported
832	// later, in ComputeCrossModuleImport, after import decisions are
833	// complete, which is more efficient than adding them here.
834	if (ExportLists)
835	(*ExportLists)[ExportModulePath].insert(V: VI);
836	}
837
838	auto GetAdjustedThreshold = [](unsigned Threshold, bool IsHotCallsite) {
839	// Adjust the threshold for next level of imported functions.
840	// The threshold is different for hot callsites because we can then
841	// inline chains of hot calls.
842	if (IsHotCallsite)
843	return Threshold * ImportHotInstrFactor;
844	return Threshold * ImportInstrFactor;
845	};
846
847	const auto AdjThreshold = GetAdjustedThreshold(Threshold, IsHotCallsite);
848
849	ImportCount++;
850
851	// Insert the newly imported function to the worklist.
852	Worklist.emplace_back(Args&: ResolvedCalleeSummary, Args: AdjThreshold);
853	}
854	}
855
856	void ModuleImportsManager::computeImportForModule(
857	const GVSummaryMapTy &DefinedGVSummaries, StringRef ModName,
858	FunctionImporter::ImportMapTy &ImportList) {
859	// Worklist contains the list of function imported in this module, for which
860	// we will analyse the callees and may import further down the callgraph.
861	SmallVector<EdgeInfo, 128> Worklist;
862	GlobalsImporter GVI(Index, DefinedGVSummaries, IsPrevailing, ImportList,
863	ExportLists);
864	FunctionImporter::ImportThresholdsTy ImportThresholds;
865
866	// Populate the worklist with the import for the functions in the current
867	// module
868	for (const auto &GVSummary : DefinedGVSummaries) {
869	#ifndef NDEBUG
870	// FIXME: Change the GVSummaryMapTy to hold ValueInfo instead of GUID
871	// so this map look up (and possibly others) can be avoided.
872	auto VI = Index.getValueInfo(GUID: GVSummary.first);
873	#endif
874	if (!Index.isGlobalValueLive(GVS: GVSummary.second)) {
875	LLVM_DEBUG(dbgs() << "Ignores Dead GUID: " << VI << "\n");
876	continue;
877	}
878	auto *FuncSummary =
879	dyn_cast<FunctionSummary>(Val: GVSummary.second->getBaseObject());
880	if (!FuncSummary)
881	// Skip import for global variables
882	continue;
883	LLVM_DEBUG(dbgs() << "Initialize import for " << VI << "\n");
884	computeImportForFunction(Summary: *FuncSummary, Index, Threshold: ImportInstrLimit,
885	DefinedGVSummaries, isPrevailing: IsPrevailing, Worklist, GVImporter&: GVI,
886	ImportList, ExportLists, ImportThresholds);
887	}
888
889	// Process the newly imported functions and add callees to the worklist.
890	while (!Worklist.empty()) {
891	auto GVInfo = Worklist.pop_back_val();
892	auto *Summary = std::get<0>(t&: GVInfo);
893	auto Threshold = std::get<1>(t&: GVInfo);
894
895	if (auto *FS = dyn_cast<FunctionSummary>(Val: Summary))
896	computeImportForFunction(Summary: *FS, Index, Threshold, DefinedGVSummaries,
897	isPrevailing: IsPrevailing, Worklist, GVImporter&: GVI, ImportList,
898	ExportLists, ImportThresholds);
899	}
900
901	// Print stats about functions considered but rejected for importing
902	// when requested.
903	if (PrintImportFailures) {
904	dbgs() << "Missed imports into module " << ModName << "\n";
905	for (auto &I : ImportThresholds) {
906	auto &ProcessedThreshold = std::get<0>(t&: I.second);
907	auto &CalleeSummary = std::get<1>(t&: I.second);
908	auto &FailureInfo = std::get<2>(t&: I.second);
909	if (CalleeSummary)
910	continue; // We are going to import.
911	assert(FailureInfo);
912	FunctionSummary *FS = nullptr;
913	if (!FailureInfo->VI.getSummaryList().empty())
914	FS = dyn_cast<FunctionSummary>(
915	Val: FailureInfo->VI.getSummaryList()[0]->getBaseObject());
916	dbgs() << FailureInfo->VI
917	<< ": Reason = " << getFailureName(Reason: FailureInfo->Reason)
918	<< ", Threshold = " << ProcessedThreshold
919	<< ", Size = " << (FS ? (int)FS->instCount() : -1)
920	<< ", MaxHotness = " << getHotnessName(HT: FailureInfo->MaxHotness)
921	<< ", Attempts = " << FailureInfo->Attempts << "\n";
922	}
923	}
924	}
925
926	#ifndef NDEBUG
927	static bool isGlobalVarSummary(const ModuleSummaryIndex &Index, ValueInfo VI) {
928	auto SL = VI.getSummaryList();
929	return SL.empty()
930	? false
931	: SL[0]->getSummaryKind() == GlobalValueSummary::GlobalVarKind;
932	}
933
934	static bool isGlobalVarSummary(const ModuleSummaryIndex &Index,
935	GlobalValue::GUID G) {
936	if (const auto &VI = Index.getValueInfo(GUID: G))
937	return isGlobalVarSummary(Index, VI);
938	return false;
939	}
940
941	template <class T>
942	static unsigned numGlobalVarSummaries(const ModuleSummaryIndex &Index,
943	T &Cont) {
944	unsigned NumGVS = 0;
945	for (auto &V : Cont)
946	if (isGlobalVarSummary(Index, V))
947	++NumGVS;
948	return NumGVS;
949	}
950	#endif
951
952	#ifndef NDEBUG
953	static bool checkVariableImport(
954	const ModuleSummaryIndex &Index,
955	DenseMap<StringRef, FunctionImporter::ImportMapTy> &ImportLists,
956	DenseMap<StringRef, FunctionImporter::ExportSetTy> &ExportLists) {
957
958	DenseSet<GlobalValue::GUID> FlattenedImports;
959
960	for (auto &ImportPerModule : ImportLists)
961	for (auto &ExportPerModule : ImportPerModule.second)
962	FlattenedImports.insert(I: ExportPerModule.second.begin(),
963	E: ExportPerModule.second.end());
964
965	// Checks that all GUIDs of read/writeonly vars we see in export lists
966	// are also in the import lists. Otherwise we my face linker undefs,
967	// because readonly and writeonly vars are internalized in their
968	// source modules. The exception would be if it has a linkage type indicating
969	// that there may have been a copy existing in the importing module (e.g.
970	// linkonce_odr). In that case we cannot accurately do this checking.
971	auto IsReadOrWriteOnlyVarNeedingImporting = [&](StringRef ModulePath,
972	const ValueInfo &VI) {
973	auto *GVS = dyn_cast_or_null<GlobalVarSummary>(
974	Val: Index.findSummaryInModule(VI, ModuleId: ModulePath));
975	return GVS && (Index.isReadOnly(GVS) || Index.isWriteOnly(GVS)) &&
976	!(GVS->linkage() == GlobalValue::AvailableExternallyLinkage ||
977	GVS->linkage() == GlobalValue::WeakODRLinkage ||
978	GVS->linkage() == GlobalValue::LinkOnceODRLinkage);
979	};
980
981	for (auto &ExportPerModule : ExportLists)
982	for (auto &VI : ExportPerModule.second)
983	if (!FlattenedImports.count(V: VI.getGUID()) &&
984	IsReadOrWriteOnlyVarNeedingImporting(ExportPerModule.first, VI))
985	return false;
986
987	return true;
988	}
989	#endif
990
991	/// Compute all the import and export for every module using the Index.
992	void llvm::ComputeCrossModuleImport(
993	const ModuleSummaryIndex &Index,
994	const DenseMap<StringRef, GVSummaryMapTy> &ModuleToDefinedGVSummaries,
995	function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
996	isPrevailing,
997	DenseMap<StringRef, FunctionImporter::ImportMapTy> &ImportLists,
998	DenseMap<StringRef, FunctionImporter::ExportSetTy> &ExportLists) {
999	auto MIS = ModuleImportsManager::create(IsPrevailing: isPrevailing, Index, ExportLists: &ExportLists);
1000	// For each module that has function defined, compute the import/export lists.
1001	for (const auto &DefinedGVSummaries : ModuleToDefinedGVSummaries) {
1002	auto &ImportList = ImportLists[DefinedGVSummaries.first];
1003	LLVM_DEBUG(dbgs() << "Computing import for Module '"
1004	<< DefinedGVSummaries.first << "'\n");
1005	MIS->computeImportForModule(DefinedGVSummaries: DefinedGVSummaries.second,
1006	ModName: DefinedGVSummaries.first, ImportList);
1007	}
1008
1009	// When computing imports we only added the variables and functions being
1010	// imported to the export list. We also need to mark any references and calls
1011	// they make as exported as well. We do this here, as it is more efficient
1012	// since we may import the same values multiple times into different modules
1013	// during the import computation.
1014	for (auto &ELI : ExportLists) {
1015	FunctionImporter::ExportSetTy NewExports;
1016	const auto &DefinedGVSummaries =
1017	ModuleToDefinedGVSummaries.lookup(Val: ELI.first);
1018	for (auto &EI : ELI.second) {
1019	// Find the copy defined in the exporting module so that we can mark the
1020	// values it references in that specific definition as exported.
1021	// Below we will add all references and called values, without regard to
1022	// whether they are also defined in this module. We subsequently prune the
1023	// list to only include those defined in the exporting module, see comment
1024	// there as to why.
1025	auto DS = DefinedGVSummaries.find(Val: EI.getGUID());
1026	// Anything marked exported during the import computation must have been
1027	// defined in the exporting module.
1028	assert(DS != DefinedGVSummaries.end());
1029	auto *S = DS->getSecond();
1030	S = S->getBaseObject();
1031	if (auto *GVS = dyn_cast<GlobalVarSummary>(Val: S)) {
1032	// Export referenced functions and variables. We don't export/promote
1033	// objects referenced by writeonly variable initializer, because
1034	// we convert such variables initializers to "zeroinitializer".
1035	// See processGlobalForThinLTO.
1036	if (!Index.isWriteOnly(GVS))
1037	for (const auto &VI : GVS->refs())
1038	NewExports.insert(V: VI);
1039	} else {
1040	auto *FS = cast<FunctionSummary>(Val: S);
1041	for (const auto &Edge : FS->calls())
1042	NewExports.insert(V: Edge.first);
1043	for (const auto &Ref : FS->refs())
1044	NewExports.insert(V: Ref);
1045	}
1046	}
1047	// Prune list computed above to only include values defined in the exporting
1048	// module. We do this after the above insertion since we may hit the same
1049	// ref/call target multiple times in above loop, and it is more efficient to
1050	// avoid a set lookup each time.
1051	for (auto EI = NewExports.begin(); EI != NewExports.end();) {
1052	if (!DefinedGVSummaries.count(Val: EI->getGUID()))
1053	NewExports.erase(I: EI++);
1054	else
1055	++EI;
1056	}
1057	ELI.second.insert(I: NewExports.begin(), E: NewExports.end());
1058	}
1059
1060	assert(checkVariableImport(Index, ImportLists, ExportLists));
1061	#ifndef NDEBUG
1062	LLVM_DEBUG(dbgs() << "Import/Export lists for " << ImportLists.size()
1063	<< " modules:\n");
1064	for (auto &ModuleImports : ImportLists) {
1065	auto ModName = ModuleImports.first;
1066	auto &Exports = ExportLists[ModName];
1067	unsigned NumGVS = numGlobalVarSummaries(Index, Cont&: Exports);
1068	LLVM_DEBUG(dbgs() << "* Module " << ModName << " exports "
1069	<< Exports.size() - NumGVS << " functions and " << NumGVS
1070	<< " vars. Imports from " << ModuleImports.second.size()
1071	<< " modules.\n");
1072	for (auto &Src : ModuleImports.second) {
1073	auto SrcModName = Src.first;
1074	unsigned NumGVSPerMod = numGlobalVarSummaries(Index, Cont&: Src.second);
1075	LLVM_DEBUG(dbgs() << " - " << Src.second.size() - NumGVSPerMod
1076	<< " functions imported from " << SrcModName << "\n");
1077	LLVM_DEBUG(dbgs() << " - " << NumGVSPerMod
1078	<< " global vars imported from " << SrcModName << "\n");
1079	}
1080	}
1081	#endif
1082	}
1083
1084	#ifndef NDEBUG
1085	static void dumpImportListForModule(const ModuleSummaryIndex &Index,
1086	StringRef ModulePath,
1087	FunctionImporter::ImportMapTy &ImportList) {
1088	LLVM_DEBUG(dbgs() << "* Module " << ModulePath << " imports from "
1089	<< ImportList.size() << " modules.\n");
1090	for (auto &Src : ImportList) {
1091	auto SrcModName = Src.first;
1092	unsigned NumGVSPerMod = numGlobalVarSummaries(Index, Cont&: Src.second);
1093	LLVM_DEBUG(dbgs() << " - " << Src.second.size() - NumGVSPerMod
1094	<< " functions imported from " << SrcModName << "\n");
1095	LLVM_DEBUG(dbgs() << " - " << NumGVSPerMod << " vars imported from "
1096	<< SrcModName << "\n");
1097	}
1098	}
1099	#endif
1100
1101	/// Compute all the imports for the given module using the Index.
1102	///
1103	/// \p isPrevailing is a callback that will be called with a global value's GUID
1104	/// and summary and should return whether the module corresponding to the
1105	/// summary contains the linker-prevailing copy of that value.
1106	///
1107	/// \p ImportList will be populated with a map that can be passed to
1108	/// FunctionImporter::importFunctions() above (see description there).
1109	static void ComputeCrossModuleImportForModuleForTest(
1110	StringRef ModulePath,
1111	function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
1112	isPrevailing,
1113	const ModuleSummaryIndex &Index,
1114	FunctionImporter::ImportMapTy &ImportList) {
1115	// Collect the list of functions this module defines.
1116	// GUID -> Summary
1117	GVSummaryMapTy FunctionSummaryMap;
1118	Index.collectDefinedFunctionsForModule(ModulePath, GVSummaryMap&: FunctionSummaryMap);
1119
1120	// Compute the import list for this module.
1121	LLVM_DEBUG(dbgs() << "Computing import for Module '" << ModulePath << "'\n");
1122	auto MIS = ModuleImportsManager::create(IsPrevailing: isPrevailing, Index);
1123	MIS->computeImportForModule(DefinedGVSummaries: FunctionSummaryMap, ModName: ModulePath, ImportList);
1124
1125	#ifndef NDEBUG
1126	dumpImportListForModule(Index, ModulePath, ImportList);
1127	#endif
1128	}
1129
1130	/// Mark all external summaries in \p Index for import into the given module.
1131	/// Used for testing the case of distributed builds using a distributed index.
1132	///
1133	/// \p ImportList will be populated with a map that can be passed to
1134	/// FunctionImporter::importFunctions() above (see description there).
1135	static void ComputeCrossModuleImportForModuleFromIndexForTest(
1136	StringRef ModulePath, const ModuleSummaryIndex &Index,
1137	FunctionImporter::ImportMapTy &ImportList) {
1138	for (const auto &GlobalList : Index) {
1139	// Ignore entries for undefined references.
1140	if (GlobalList.second.SummaryList.empty())
1141	continue;
1142
1143	auto GUID = GlobalList.first;
1144	assert(GlobalList.second.SummaryList.size() == 1 &&
1145	"Expected individual combined index to have one summary per GUID");
1146	auto &Summary = GlobalList.second.SummaryList[0];
1147	// Skip the summaries for the importing module. These are included to
1148	// e.g. record required linkage changes.
1149	if (Summary->modulePath() == ModulePath)
1150	continue;
1151	// Add an entry to provoke importing by thinBackend.
1152	ImportList[Summary->modulePath()].insert(x: GUID);
1153	}
1154	#ifndef NDEBUG
1155	dumpImportListForModule(Index, ModulePath, ImportList);
1156	#endif
1157	}
1158
1159	// For SamplePGO, the indirect call targets for local functions will
1160	// have its original name annotated in profile. We try to find the
1161	// corresponding PGOFuncName as the GUID, and fix up the edges
1162	// accordingly.
1163	void updateValueInfoForIndirectCalls(ModuleSummaryIndex &Index,
1164	FunctionSummary *FS) {
1165	for (auto &EI : FS->mutableCalls()) {
1166	if (!EI.first.getSummaryList().empty())
1167	continue;
1168	auto GUID = Index.getGUIDFromOriginalID(OriginalID: EI.first.getGUID());
1169	if (GUID == 0)
1170	continue;
1171	// Update the edge to point directly to the correct GUID.
1172	auto VI = Index.getValueInfo(GUID);
1173	if (llvm::any_of(
1174	Range: VI.getSummaryList(),
1175	P: [&](const std::unique_ptr<GlobalValueSummary> &SummaryPtr) {
1176	// The mapping from OriginalId to GUID may return a GUID
1177	// that corresponds to a static variable. Filter it out here.
1178	// This can happen when
1179	// 1) There is a call to a library function which is not defined
1180	// in the index.
1181	// 2) There is a static variable with the OriginalGUID identical
1182	// to the GUID of the library function in 1);
1183	// When this happens the static variable in 2) will be found,
1184	// which needs to be filtered out.
1185	return SummaryPtr->getSummaryKind() ==
1186	GlobalValueSummary::GlobalVarKind;
1187	}))
1188	continue;
1189	EI.first = VI;
1190	}
1191	}
1192
1193	void llvm::updateIndirectCalls(ModuleSummaryIndex &Index) {
1194	for (const auto &Entry : Index) {
1195	for (const auto &S : Entry.second.SummaryList) {
1196	if (auto *FS = dyn_cast<FunctionSummary>(Val: S.get()))
1197	updateValueInfoForIndirectCalls(Index, FS);
1198	}
1199	}
1200	}
1201
1202	void llvm::computeDeadSymbolsAndUpdateIndirectCalls(
1203	ModuleSummaryIndex &Index,
1204	const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols,
1205	function_ref<PrevailingType(GlobalValue::GUID)> isPrevailing) {
1206	assert(!Index.withGlobalValueDeadStripping());
1207	if (!ComputeDead ||
1208	// Don't do anything when nothing is live, this is friendly with tests.
1209	GUIDPreservedSymbols.empty()) {
1210	// Still need to update indirect calls.
1211	updateIndirectCalls(Index);
1212	return;
1213	}
1214	unsigned LiveSymbols = 0;
1215	SmallVector<ValueInfo, 128> Worklist;
1216	Worklist.reserve(N: GUIDPreservedSymbols.size() * 2);
1217	for (auto GUID : GUIDPreservedSymbols) {
1218	ValueInfo VI = Index.getValueInfo(GUID);
1219	if (!VI)
1220	continue;
1221	for (const auto &S : VI.getSummaryList())
1222	S->setLive(true);
1223	}
1224
1225	// Add values flagged in the index as live roots to the worklist.
1226	for (const auto &Entry : Index) {
1227	auto VI = Index.getValueInfo(R: Entry);
1228	for (const auto &S : Entry.second.SummaryList) {
1229	if (auto *FS = dyn_cast<FunctionSummary>(Val: S.get()))
1230	updateValueInfoForIndirectCalls(Index, FS);
1231	if (S->isLive()) {
1232	LLVM_DEBUG(dbgs() << "Live root: " << VI << "\n");
1233	Worklist.push_back(Elt: VI);
1234	++LiveSymbols;
1235	break;
1236	}
1237	}
1238	}
1239
1240	// Make value live and add it to the worklist if it was not live before.
1241	auto visit = [&](ValueInfo VI, bool IsAliasee) {
1242	// FIXME: If we knew which edges were created for indirect call profiles,
1243	// we could skip them here. Any that are live should be reached via
1244	// other edges, e.g. reference edges. Otherwise, using a profile collected
1245	// on a slightly different binary might provoke preserving, importing
1246	// and ultimately promoting calls to functions not linked into this
1247	// binary, which increases the binary size unnecessarily. Note that
1248	// if this code changes, the importer needs to change so that edges
1249	// to functions marked dead are skipped.
1250
1251	if (llvm::any_of(Range: VI.getSummaryList(),
1252	P: [](const std::unique_ptr<llvm::GlobalValueSummary> &S) {
1253	return S->isLive();
1254	}))
1255	return;
1256
1257	// We only keep live symbols that are known to be non-prevailing if any are
1258	// available_externally, linkonceodr, weakodr. Those symbols are discarded
1259	// later in the EliminateAvailableExternally pass and setting them to
1260	// not-live could break downstreams users of liveness information (PR36483)
1261	// or limit optimization opportunities.
1262	if (isPrevailing(VI.getGUID()) == PrevailingType::No) {
1263	bool KeepAliveLinkage = false;
1264	bool Interposable = false;
1265	for (const auto &S : VI.getSummaryList()) {
1266	if (S->linkage() == GlobalValue::AvailableExternallyLinkage ||
1267	S->linkage() == GlobalValue::WeakODRLinkage ||
1268	S->linkage() == GlobalValue::LinkOnceODRLinkage)
1269	KeepAliveLinkage = true;
1270	else if (GlobalValue::isInterposableLinkage(Linkage: S->linkage()))
1271	Interposable = true;
1272	}
1273
1274	if (!IsAliasee) {
1275	if (!KeepAliveLinkage)
1276	return;
1277
1278	if (Interposable)
1279	report_fatal_error(
1280	reason: "Interposable and available_externally/linkonce_odr/weak_odr "
1281	"symbol");
1282	}
1283	}
1284
1285	for (const auto &S : VI.getSummaryList())
1286	S->setLive(true);
1287	++LiveSymbols;
1288	Worklist.push_back(Elt: VI);
1289	};
1290
1291	while (!Worklist.empty()) {
1292	auto VI = Worklist.pop_back_val();
1293	for (const auto &Summary : VI.getSummaryList()) {
1294	if (auto *AS = dyn_cast<AliasSummary>(Val: Summary.get())) {
1295	// If this is an alias, visit the aliasee VI to ensure that all copies
1296	// are marked live and it is added to the worklist for further
1297	// processing of its references.
1298	visit(AS->getAliaseeVI(), true);
1299	continue;
1300	}
1301	for (auto Ref : Summary->refs())
1302	visit(Ref, false);
1303	if (auto *FS = dyn_cast<FunctionSummary>(Val: Summary.get()))
1304	for (auto Call : FS->calls())
1305	visit(Call.first, false);
1306	}
1307	}
1308	Index.setWithGlobalValueDeadStripping();
1309
1310	unsigned DeadSymbols = Index.size() - LiveSymbols;
1311	LLVM_DEBUG(dbgs() << LiveSymbols << " symbols Live, and " << DeadSymbols
1312	<< " symbols Dead \n");
1313	NumDeadSymbols += DeadSymbols;
1314	NumLiveSymbols += LiveSymbols;
1315	}
1316
1317	// Compute dead symbols and propagate constants in combined index.
1318	void llvm::computeDeadSymbolsWithConstProp(
1319	ModuleSummaryIndex &Index,
1320	const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols,
1321	function_ref<PrevailingType(GlobalValue::GUID)> isPrevailing,
1322	bool ImportEnabled) {
1323	computeDeadSymbolsAndUpdateIndirectCalls(Index, GUIDPreservedSymbols,
1324	isPrevailing);
1325	if (ImportEnabled)
1326	Index.propagateAttributes(PreservedSymbols: GUIDPreservedSymbols);
1327	}
1328
1329	/// Compute the set of summaries needed for a ThinLTO backend compilation of
1330	/// \p ModulePath.
1331	void llvm::gatherImportedSummariesForModule(
1332	StringRef ModulePath,
1333	const DenseMap<StringRef, GVSummaryMapTy> &ModuleToDefinedGVSummaries,
1334	const FunctionImporter::ImportMapTy &ImportList,
1335	std::map<std::string, GVSummaryMapTy> &ModuleToSummariesForIndex) {
1336	// Include all summaries from the importing module.
1337	ModuleToSummariesForIndex[std::string(ModulePath)] =
1338	ModuleToDefinedGVSummaries.lookup(Val: ModulePath);
1339	// Include summaries for imports.
1340	for (const auto &ILI : ImportList) {
1341	auto &SummariesForIndex = ModuleToSummariesForIndex[std::string(ILI.first)];
1342	const auto &DefinedGVSummaries =
1343	ModuleToDefinedGVSummaries.lookup(Val: ILI.first);
1344	for (const auto &GI : ILI.second) {
1345	const auto &DS = DefinedGVSummaries.find(Val: GI);
1346	assert(DS != DefinedGVSummaries.end() &&
1347	"Expected a defined summary for imported global value");
1348	SummariesForIndex[GI] = DS->second;
1349	}
1350	}
1351	}
1352
1353	/// Emit the files \p ModulePath will import from into \p OutputFilename.
1354	std::error_code llvm::EmitImportsFiles(
1355	StringRef ModulePath, StringRef OutputFilename,
1356	const std::map<std::string, GVSummaryMapTy> &ModuleToSummariesForIndex) {
1357	std::error_code EC;
1358	raw_fd_ostream ImportsOS(OutputFilename, EC, sys::fs::OpenFlags::OF_None);
1359	if (EC)
1360	return EC;
1361	for (const auto &ILI : ModuleToSummariesForIndex)
1362	// The ModuleToSummariesForIndex map includes an entry for the current
1363	// Module (needed for writing out the index files). We don't want to
1364	// include it in the imports file, however, so filter it out.
1365	if (ILI.first != ModulePath)
1366	ImportsOS << ILI.first << "\n";
1367	return std::error_code();
1368	}
1369
1370	bool llvm::convertToDeclaration(GlobalValue &GV) {
1371	LLVM_DEBUG(dbgs() << "Converting to a declaration: `" << GV.getName()
1372	<< "\n");
1373	if (Function *F = dyn_cast<Function>(Val: &GV)) {
1374	F->deleteBody();
1375	F->clearMetadata();
1376	F->setComdat(nullptr);
1377	} else if (GlobalVariable *V = dyn_cast<GlobalVariable>(Val: &GV)) {
1378	V->setInitializer(nullptr);
1379	V->setLinkage(GlobalValue::ExternalLinkage);
1380	V->clearMetadata();
1381	V->setComdat(nullptr);
1382	} else {
1383	GlobalValue *NewGV;
1384	if (GV.getValueType()->isFunctionTy())
1385	NewGV =
1386	Function::Create(Ty: cast<FunctionType>(Val: GV.getValueType()),
1387	Linkage: GlobalValue::ExternalLinkage, AddrSpace: GV.getAddressSpace(),
1388	N: "", M: GV.getParent());
1389	else
1390	NewGV =
1391	new GlobalVariable(*GV.getParent(), GV.getValueType(),
1392	/*isConstant*/ false, GlobalValue::ExternalLinkage,
1393	/*init*/ nullptr, "",
1394	/*insertbefore*/ nullptr, GV.getThreadLocalMode(),
1395	GV.getType()->getAddressSpace());
1396	NewGV->takeName(V: &GV);
1397	GV.replaceAllUsesWith(V: NewGV);
1398	return false;
1399	}
1400	if (!GV.isImplicitDSOLocal())
1401	GV.setDSOLocal(false);
1402	return true;
1403	}
1404
1405	void llvm::thinLTOFinalizeInModule(Module &TheModule,
1406	const GVSummaryMapTy &DefinedGlobals,
1407	bool PropagateAttrs) {
1408	DenseSet<Comdat *> NonPrevailingComdats;
1409	auto FinalizeInModule = [&](GlobalValue &GV, bool Propagate = false) {
1410	// See if the global summary analysis computed a new resolved linkage.
1411	const auto &GS = DefinedGlobals.find(Val: GV.getGUID());
1412	if (GS == DefinedGlobals.end())
1413	return;
1414
1415	if (Propagate)
1416	if (FunctionSummary *FS = dyn_cast<FunctionSummary>(Val: GS->second)) {
1417	if (Function *F = dyn_cast<Function>(Val: &GV)) {
1418	// TODO: propagate ReadNone and ReadOnly.
1419	if (FS->fflags().ReadNone && !F->doesNotAccessMemory())
1420	F->setDoesNotAccessMemory();
1421
1422	if (FS->fflags().ReadOnly && !F->onlyReadsMemory())
1423	F->setOnlyReadsMemory();
1424
1425	if (FS->fflags().NoRecurse && !F->doesNotRecurse())
1426	F->setDoesNotRecurse();
1427
1428	if (FS->fflags().NoUnwind && !F->doesNotThrow())
1429	F->setDoesNotThrow();
1430	}
1431	}
1432
1433	auto NewLinkage = GS->second->linkage();
1434	if (GlobalValue::isLocalLinkage(Linkage: GV.getLinkage()) ||
1435	// Don't internalize anything here, because the code below
1436	// lacks necessary correctness checks. Leave this job to
1437	// LLVM 'internalize' pass.
1438	GlobalValue::isLocalLinkage(Linkage: NewLinkage) ||
1439	// In case it was dead and already converted to declaration.
1440	GV.isDeclaration())
1441	return;
1442
1443	// Set the potentially more constraining visibility computed from summaries.
1444	// The DefaultVisibility condition is because older GlobalValueSummary does
1445	// not record DefaultVisibility and we don't want to change protected/hidden
1446	// to default.
1447	if (GS->second->getVisibility() != GlobalValue::DefaultVisibility)
1448	GV.setVisibility(GS->second->getVisibility());
1449
1450	if (NewLinkage == GV.getLinkage())
1451	return;
1452
1453	// Check for a non-prevailing def that has interposable linkage
1454	// (e.g. non-odr weak or linkonce). In that case we can't simply
1455	// convert to available_externally, since it would lose the
1456	// interposable property and possibly get inlined. Simply drop
1457	// the definition in that case.
1458	if (GlobalValue::isAvailableExternallyLinkage(Linkage: NewLinkage) &&
1459	GlobalValue::isInterposableLinkage(Linkage: GV.getLinkage())) {
1460	if (!convertToDeclaration(GV))
1461	// FIXME: Change this to collect replaced GVs and later erase
1462	// them from the parent module once thinLTOResolvePrevailingGUID is
1463	// changed to enable this for aliases.
1464	llvm_unreachable("Expected GV to be converted");
1465	} else {
1466	// If all copies of the original symbol had global unnamed addr and
1467	// linkonce_odr linkage, or if all of them had local unnamed addr linkage
1468	// and are constants, then it should be an auto hide symbol. In that case
1469	// the thin link would have marked it as CanAutoHide. Add hidden
1470	// visibility to the symbol to preserve the property.
1471	if (NewLinkage == GlobalValue::WeakODRLinkage &&
1472	GS->second->canAutoHide()) {
1473	assert(GV.canBeOmittedFromSymbolTable());
1474	GV.setVisibility(GlobalValue::HiddenVisibility);
1475	}
1476
1477	LLVM_DEBUG(dbgs() << "ODR fixing up linkage for `" << GV.getName()
1478	<< "` from " << GV.getLinkage() << " to " << NewLinkage
1479	<< "\n");
1480	GV.setLinkage(NewLinkage);
1481	}
1482	// Remove declarations from comdats, including available_externally
1483	// as this is a declaration for the linker, and will be dropped eventually.
1484	// It is illegal for comdats to contain declarations.
1485	auto *GO = dyn_cast_or_null<GlobalObject>(Val: &GV);
1486	if (GO && GO->isDeclarationForLinker() && GO->hasComdat()) {
1487	if (GO->getComdat()->getName() == GO->getName())
1488	NonPrevailingComdats.insert(V: GO->getComdat());
1489	GO->setComdat(nullptr);
1490	}
1491	};
1492
1493	// Process functions and global now
1494	for (auto &GV : TheModule)
1495	FinalizeInModule(GV, PropagateAttrs);
1496	for (auto &GV : TheModule.globals())
1497	FinalizeInModule(GV);
1498	for (auto &GV : TheModule.aliases())
1499	FinalizeInModule(GV);
1500
1501	// For a non-prevailing comdat, all its members must be available_externally.
1502	// FinalizeInModule has handled non-local-linkage GlobalValues. Here we handle
1503	// local linkage GlobalValues.
1504	if (NonPrevailingComdats.empty())
1505	return;
1506	for (auto &GO : TheModule.global_objects()) {
1507	if (auto *C = GO.getComdat(); C && NonPrevailingComdats.count(V: C)) {
1508	GO.setComdat(nullptr);
1509	GO.setLinkage(GlobalValue::AvailableExternallyLinkage);
1510	}
1511	}
1512	bool Changed;
1513	do {
1514	Changed = false;
1515	// If an alias references a GlobalValue in a non-prevailing comdat, change
1516	// it to available_externally. For simplicity we only handle GlobalValue and
1517	// ConstantExpr with a base object. ConstantExpr without a base object is
1518	// unlikely used in a COMDAT.
1519	for (auto &GA : TheModule.aliases()) {
1520	if (GA.hasAvailableExternallyLinkage())
1521	continue;
1522	GlobalObject *Obj = GA.getAliaseeObject();
1523	assert(Obj && "aliasee without an base object is unimplemented");
1524	if (Obj->hasAvailableExternallyLinkage()) {
1525	GA.setLinkage(GlobalValue::AvailableExternallyLinkage);
1526	Changed = true;
1527	}
1528	}
1529	} while (Changed);
1530	}
1531
1532	/// Run internalization on \p TheModule based on symmary analysis.
1533	void llvm::thinLTOInternalizeModule(Module &TheModule,
1534	const GVSummaryMapTy &DefinedGlobals) {
1535	// Declare a callback for the internalize pass that will ask for every
1536	// candidate GlobalValue if it can be internalized or not.
1537	auto MustPreserveGV = [&](const GlobalValue &GV) -> bool {
1538	// It may be the case that GV is on a chain of an ifunc, its alias and
1539	// subsequent aliases. In this case, the summary for the value is not
1540	// available.
1541	if (isa<GlobalIFunc>(Val: &GV) ||
1542	(isa<GlobalAlias>(Val: &GV) &&
1543	isa<GlobalIFunc>(Val: cast<GlobalAlias>(Val: &GV)->getAliaseeObject())))
1544	return true;
1545
1546	// Lookup the linkage recorded in the summaries during global analysis.
1547	auto GS = DefinedGlobals.find(Val: GV.getGUID());
1548	if (GS == DefinedGlobals.end()) {
1549	// Must have been promoted (possibly conservatively). Find original
1550	// name so that we can access the correct summary and see if it can
1551	// be internalized again.
1552	// FIXME: Eventually we should control promotion instead of promoting
1553	// and internalizing again.
1554	StringRef OrigName =
1555	ModuleSummaryIndex::getOriginalNameBeforePromote(Name: GV.getName());
1556	std::string OrigId = GlobalValue::getGlobalIdentifier(
1557	Name: OrigName, Linkage: GlobalValue::InternalLinkage,
1558	FileName: TheModule.getSourceFileName());
1559	GS = DefinedGlobals.find(Val: GlobalValue::getGUID(GlobalName: OrigId));
1560	if (GS == DefinedGlobals.end()) {
1561	// Also check the original non-promoted non-globalized name. In some
1562	// cases a preempted weak value is linked in as a local copy because
1563	// it is referenced by an alias (IRLinker::linkGlobalValueProto).
1564	// In that case, since it was originally not a local value, it was
1565	// recorded in the index using the original name.
1566	// FIXME: This may not be needed once PR27866 is fixed.
1567	GS = DefinedGlobals.find(Val: GlobalValue::getGUID(GlobalName: OrigName));
1568	assert(GS != DefinedGlobals.end());
1569	}
1570	}
1571	return !GlobalValue::isLocalLinkage(Linkage: GS->second->linkage());
1572	};
1573
1574	// FIXME: See if we can just internalize directly here via linkage changes
1575	// based on the index, rather than invoking internalizeModule.
1576	internalizeModule(TheModule, MustPreserveGV);
1577	}
1578
1579	/// Make alias a clone of its aliasee.
1580	static Function *replaceAliasWithAliasee(Module *SrcModule, GlobalAlias *GA) {
1581	Function *Fn = cast<Function>(Val: GA->getAliaseeObject());
1582
1583	ValueToValueMapTy VMap;
1584	Function *NewFn = CloneFunction(F: Fn, VMap);
1585	// Clone should use the original alias's linkage, visibility and name, and we
1586	// ensure all uses of alias instead use the new clone (casted if necessary).
1587	NewFn->setLinkage(GA->getLinkage());
1588	NewFn->setVisibility(GA->getVisibility());
1589	GA->replaceAllUsesWith(V: NewFn);
1590	NewFn->takeName(V: GA);
1591	return NewFn;
1592	}
1593
1594	// Internalize values that we marked with specific attribute
1595	// in processGlobalForThinLTO.
1596	static void internalizeGVsAfterImport(Module &M) {
1597	for (auto &GV : M.globals())
1598	// Skip GVs which have been converted to declarations
1599	// by dropDeadSymbols.
1600	if (!GV.isDeclaration() && GV.hasAttribute(Kind: "thinlto-internalize")) {
1601	GV.setLinkage(GlobalValue::InternalLinkage);
1602	GV.setVisibility(GlobalValue::DefaultVisibility);
1603	}
1604	}
1605
1606	// Automatically import functions in Module \p DestModule based on the summaries
1607	// index.
1608	Expected<bool> FunctionImporter::importFunctions(
1609	Module &DestModule, const FunctionImporter::ImportMapTy &ImportList) {
1610	LLVM_DEBUG(dbgs() << "Starting import for Module "
1611	<< DestModule.getModuleIdentifier() << "\n");
1612	unsigned ImportedCount = 0, ImportedGVCount = 0;
1613
1614	IRMover Mover(DestModule);
1615	// Do the actual import of functions now, one Module at a time
1616	std::set<StringRef> ModuleNameOrderedList;
1617	for (const auto &FunctionsToImportPerModule : ImportList) {
1618	ModuleNameOrderedList.insert(x: FunctionsToImportPerModule.first);
1619	}
1620	for (const auto &Name : ModuleNameOrderedList) {
1621	// Get the module for the import
1622	const auto &FunctionsToImportPerModule = ImportList.find(Val: Name);
1623	assert(FunctionsToImportPerModule != ImportList.end());
1624	Expected<std::unique_ptr<Module>> SrcModuleOrErr = ModuleLoader(Name);
1625	if (!SrcModuleOrErr)
1626	return SrcModuleOrErr.takeError();
1627	std::unique_ptr<Module> SrcModule = std::move(*SrcModuleOrErr);
1628	assert(&DestModule.getContext() == &SrcModule->getContext() &&
1629	"Context mismatch");
1630
1631	// If modules were created with lazy metadata loading, materialize it
1632	// now, before linking it (otherwise this will be a noop).
1633	if (Error Err = SrcModule->materializeMetadata())
1634	return std::move(Err);
1635
1636	auto &ImportGUIDs = FunctionsToImportPerModule->second;
1637	// Find the globals to import
1638	SetVector<GlobalValue *> GlobalsToImport;
1639	for (Function &F : *SrcModule) {
1640	if (!F.hasName())
1641	continue;
1642	auto GUID = F.getGUID();
1643	auto Import = ImportGUIDs.count(x: GUID);
1644	LLVM_DEBUG(dbgs() << (Import ? "Is" : "Not") << " importing function "
1645	<< GUID << " " << F.getName() << " from "
1646	<< SrcModule->getSourceFileName() << "\n");
1647	if (Import) {
1648	if (Error Err = F.materialize())
1649	return std::move(Err);
1650	// MemProf should match function's definition and summary,
1651	// 'thinlto_src_module' is needed.
1652	if (EnableImportMetadata || EnableMemProfContextDisambiguation) {
1653	// Add 'thinlto_src_module' and 'thinlto_src_file' metadata for
1654	// statistics and debugging.
1655	F.setMetadata(
1656	Kind: "thinlto_src_module",
1657	Node: MDNode::get(Context&: DestModule.getContext(),
1658	MDs: {MDString::get(Context&: DestModule.getContext(),
1659	Str: SrcModule->getModuleIdentifier())}));
1660	F.setMetadata(
1661	Kind: "thinlto_src_file",
1662	Node: MDNode::get(Context&: DestModule.getContext(),
1663	MDs: {MDString::get(Context&: DestModule.getContext(),
1664	Str: SrcModule->getSourceFileName())}));
1665	}
1666	GlobalsToImport.insert(X: &F);
1667	}
1668	}
1669	for (GlobalVariable &GV : SrcModule->globals()) {
1670	if (!GV.hasName())
1671	continue;
1672	auto GUID = GV.getGUID();
1673	auto Import = ImportGUIDs.count(x: GUID);
1674	LLVM_DEBUG(dbgs() << (Import ? "Is" : "Not") << " importing global "
1675	<< GUID << " " << GV.getName() << " from "
1676	<< SrcModule->getSourceFileName() << "\n");
1677	if (Import) {
1678	if (Error Err = GV.materialize())
1679	return std::move(Err);
1680	ImportedGVCount += GlobalsToImport.insert(X: &GV);
1681	}
1682	}
1683	for (GlobalAlias &GA : SrcModule->aliases()) {
1684	if (!GA.hasName() || isa<GlobalIFunc>(Val: GA.getAliaseeObject()))
1685	continue;
1686	auto GUID = GA.getGUID();
1687	auto Import = ImportGUIDs.count(x: GUID);
1688	LLVM_DEBUG(dbgs() << (Import ? "Is" : "Not") << " importing alias "
1689	<< GUID << " " << GA.getName() << " from "
1690	<< SrcModule->getSourceFileName() << "\n");
1691	if (Import) {
1692	if (Error Err = GA.materialize())
1693	return std::move(Err);
1694	// Import alias as a copy of its aliasee.
1695	GlobalObject *GO = GA.getAliaseeObject();
1696	if (Error Err = GO->materialize())
1697	return std::move(Err);
1698	auto *Fn = replaceAliasWithAliasee(SrcModule: SrcModule.get(), GA: &GA);
1699	LLVM_DEBUG(dbgs() << "Is importing aliasee fn " << GO->getGUID() << " "
1700	<< GO->getName() << " from "
1701	<< SrcModule->getSourceFileName() << "\n");
1702	if (EnableImportMetadata || EnableMemProfContextDisambiguation) {
1703	// Add 'thinlto_src_module' and 'thinlto_src_file' metadata for
1704	// statistics and debugging.
1705	Fn->setMetadata(
1706	Kind: "thinlto_src_module",
1707	Node: MDNode::get(Context&: DestModule.getContext(),
1708	MDs: {MDString::get(Context&: DestModule.getContext(),
1709	Str: SrcModule->getModuleIdentifier())}));
1710	Fn->setMetadata(
1711	Kind: "thinlto_src_file",
1712	Node: MDNode::get(Context&: DestModule.getContext(),
1713	MDs: {MDString::get(Context&: DestModule.getContext(),
1714	Str: SrcModule->getSourceFileName())}));
1715	}
1716	GlobalsToImport.insert(X: Fn);
1717	}
1718	}
1719
1720	// Upgrade debug info after we're done materializing all the globals and we
1721	// have loaded all the required metadata!
1722	UpgradeDebugInfo(M&: *SrcModule);
1723
1724	// Set the partial sample profile ratio in the profile summary module flag
1725	// of the imported source module, if applicable, so that the profile summary
1726	// module flag will match with that of the destination module when it's
1727	// imported.
1728	SrcModule->setPartialSampleProfileRatio(Index);
1729
1730	// Link in the specified functions.
1731	if (renameModuleForThinLTO(M&: *SrcModule, Index, ClearDSOLocalOnDeclarations,
1732	GlobalsToImport: &GlobalsToImport))
1733	return true;
1734
1735	if (PrintImports) {
1736	for (const auto *GV : GlobalsToImport)
1737	dbgs() << DestModule.getSourceFileName() << ": Import " << GV->getName()
1738	<< " from " << SrcModule->getSourceFileName() << "\n";
1739	}
1740
1741	if (Error Err = Mover.move(Src: std::move(SrcModule),
1742	ValuesToLink: GlobalsToImport.getArrayRef(), AddLazyFor: nullptr,
1743	/*IsPerformingImport=*/true))
1744	return createStringError(EC: errc::invalid_argument,
1745	S: Twine("Function Import: link error: ") +
1746	toString(E: std::move(Err)));
1747
1748	ImportedCount += GlobalsToImport.size();
1749	NumImportedModules++;
1750	}
1751
1752	internalizeGVsAfterImport(M&: DestModule);
1753
1754	NumImportedFunctions += (ImportedCount - ImportedGVCount);
1755	NumImportedGlobalVars += ImportedGVCount;
1756
1757	LLVM_DEBUG(dbgs() << "Imported " << ImportedCount - ImportedGVCount
1758	<< " functions for Module "
1759	<< DestModule.getModuleIdentifier() << "\n");
1760	LLVM_DEBUG(dbgs() << "Imported " << ImportedGVCount
1761	<< " global variables for Module "
1762	<< DestModule.getModuleIdentifier() << "\n");
1763	return ImportedCount;
1764	}
1765
1766	static bool doImportingForModuleForTest(
1767	Module &M, function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
1768	isPrevailing) {
1769	if (SummaryFile.empty())
1770	report_fatal_error(reason: "error: -function-import requires -summary-file\n");
1771	Expected<std::unique_ptr<ModuleSummaryIndex>> IndexPtrOrErr =
1772	getModuleSummaryIndexForFile(Path: SummaryFile);
1773	if (!IndexPtrOrErr) {
1774	logAllUnhandledErrors(E: IndexPtrOrErr.takeError(), OS&: errs(),
1775	ErrorBanner: "Error loading file '" + SummaryFile + "': ");
1776	return false;
1777	}
1778	std::unique_ptr<ModuleSummaryIndex> Index = std::move(*IndexPtrOrErr);
1779
1780	// First step is collecting the import list.
1781	FunctionImporter::ImportMapTy ImportList;
1782	// If requested, simply import all functions in the index. This is used
1783	// when testing distributed backend handling via the opt tool, when
1784	// we have distributed indexes containing exactly the summaries to import.
1785	if (ImportAllIndex)
1786	ComputeCrossModuleImportForModuleFromIndexForTest(ModulePath: M.getModuleIdentifier(),
1787	Index: *Index, ImportList);
1788	else
1789	ComputeCrossModuleImportForModuleForTest(ModulePath: M.getModuleIdentifier(),
1790	isPrevailing, Index: *Index, ImportList);
1791
1792	// Conservatively mark all internal values as promoted. This interface is
1793	// only used when doing importing via the function importing pass. The pass
1794	// is only enabled when testing importing via the 'opt' tool, which does
1795	// not do the ThinLink that would normally determine what values to promote.
1796	for (auto &I : *Index) {
1797	for (auto &S : I.second.SummaryList) {
1798	if (GlobalValue::isLocalLinkage(Linkage: S->linkage()))
1799	S->setLinkage(GlobalValue::ExternalLinkage);
1800	}
1801	}
1802
1803	// Next we need to promote to global scope and rename any local values that
1804	// are potentially exported to other modules.
1805	if (renameModuleForThinLTO(M, Index: *Index, /*ClearDSOLocalOnDeclarations=*/false,
1806	/*GlobalsToImport=*/nullptr)) {
1807	errs() << "Error renaming module\n";
1808	return true;
1809	}
1810
1811	// Perform the import now.
1812	auto ModuleLoader = [&M](StringRef Identifier) {
1813	return loadFile(FileName: std::string(Identifier), Context&: M.getContext());
1814	};
1815	FunctionImporter Importer(*Index, ModuleLoader,
1816	/*ClearDSOLocalOnDeclarations=*/false);
1817	Expected<bool> Result = Importer.importFunctions(DestModule&: M, ImportList);
1818
1819	// FIXME: Probably need to propagate Errors through the pass manager.
1820	if (!Result) {
1821	logAllUnhandledErrors(E: Result.takeError(), OS&: errs(),
1822	ErrorBanner: "Error importing module: ");
1823	return true;
1824	}
1825
1826	return true;
1827	}
1828
1829	PreservedAnalyses FunctionImportPass::run(Module &M,
1830	ModuleAnalysisManager &AM) {
1831	// This is only used for testing the function import pass via opt, where we
1832	// don't have prevailing information from the LTO context available, so just
1833	// conservatively assume everything is prevailing (which is fine for the very
1834	// limited use of prevailing checking in this pass).
1835	auto isPrevailing = [](GlobalValue::GUID, const GlobalValueSummary *) {
1836	return true;
1837	};
1838	if (!doImportingForModuleForTest(M, isPrevailing))
1839	return PreservedAnalyses::all();
1840
1841	return PreservedAnalyses::none();
1842	}
1843