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/StringMap.h"
20 #include "llvm/ADT/StringRef.h"
21 #include "llvm/ADT/StringSet.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/Metadata.h"
31 #include "llvm/IR/Module.h"
32 #include "llvm/IR/ModuleSummaryIndex.h"
33 #include "llvm/IRReader/IRReader.h"
34 #include "llvm/InitializePasses.h"
35 #include "llvm/Linker/IRMover.h"
36 #include "llvm/Object/ModuleSymbolTable.h"
37 #include "llvm/Object/SymbolicFile.h"
38 #include "llvm/Pass.h"
39 #include "llvm/Support/Casting.h"
40 #include "llvm/Support/CommandLine.h"
41 #include "llvm/Support/Debug.h"
42 #include "llvm/Support/Errc.h"
43 #include "llvm/Support/Error.h"
44 #include "llvm/Support/ErrorHandling.h"
45 #include "llvm/Support/FileSystem.h"
46 #include "llvm/Support/SourceMgr.h"
47 #include "llvm/Support/raw_ostream.h"
48 #include "llvm/Transforms/IPO/Internalize.h"
49 #include "llvm/Transforms/Utils/Cloning.h"
50 #include "llvm/Transforms/Utils/FunctionImportUtils.h"
51 #include "llvm/Transforms/Utils/ValueMapper.h"
52 #include <cassert>
53 #include <memory>
54 #include <set>
55 #include <string>
56 #include <system_error>
57 #include <tuple>
58 #include <utility>
59
60 using namespace llvm;
61
62 #define DEBUG_TYPE "function-import"
63
64 STATISTIC(NumImportedFunctionsThinLink,
65 "Number of functions thin link decided to import");
66 STATISTIC(NumImportedHotFunctionsThinLink,
67 "Number of hot functions thin link decided to import");
68 STATISTIC(NumImportedCriticalFunctionsThinLink,
69 "Number of critical functions thin link decided to import");
70 STATISTIC(NumImportedGlobalVarsThinLink,
71 "Number of global variables thin link decided to import");
72 STATISTIC(NumImportedFunctions, "Number of functions imported in backend");
73 STATISTIC(NumImportedGlobalVars,
74 "Number of global variables imported in backend");
75 STATISTIC(NumImportedModules, "Number of modules imported from");
76 STATISTIC(NumDeadSymbols, "Number of dead stripped symbols in index");
77 STATISTIC(NumLiveSymbols, "Number of live symbols in index");
78
79 /// Limit on instruction count of imported functions.
80 static cl::opt<unsigned> ImportInstrLimit(
81 "import-instr-limit", cl::init(100), cl::Hidden, cl::value_desc("N"),
82 cl::desc("Only import functions with less than N instructions"));
83
84 static cl::opt<int> ImportCutoff(
85 "import-cutoff", cl::init(-1), cl::Hidden, cl::value_desc("N"),
86 cl::desc("Only import first N functions if N>=0 (default -1)"));
87
88 static cl::opt<bool>
89 ForceImportAll("force-import-all", cl::init(false), cl::Hidden,
90 cl::desc("Import functions with noinline attribute"));
91
92 static cl::opt<float>
93 ImportInstrFactor("import-instr-evolution-factor", cl::init(0.7),
94 cl::Hidden, cl::value_desc("x"),
95 cl::desc("As we import functions, multiply the "
96 "`import-instr-limit` threshold by this factor "
97 "before processing newly imported functions"));
98
99 static cl::opt<float> ImportHotInstrFactor(
100 "import-hot-evolution-factor", cl::init(1.0), cl::Hidden,
101 cl::value_desc("x"),
102 cl::desc("As we import functions called from hot callsite, multiply the "
103 "`import-instr-limit` threshold by this factor "
104 "before processing newly imported functions"));
105
106 static cl::opt<float> ImportHotMultiplier(
107 "import-hot-multiplier", cl::init(10.0), cl::Hidden, cl::value_desc("x"),
108 cl::desc("Multiply the `import-instr-limit` threshold for hot callsites"));
109
110 static cl::opt<float> ImportCriticalMultiplier(
111 "import-critical-multiplier", cl::init(100.0), cl::Hidden,
112 cl::value_desc("x"),
113 cl::desc(
114 "Multiply the `import-instr-limit` threshold for critical callsites"));
115
116 // FIXME: This multiplier was not really tuned up.
117 static cl::opt<float> ImportColdMultiplier(
118 "import-cold-multiplier", cl::init(0), cl::Hidden, cl::value_desc("N"),
119 cl::desc("Multiply the `import-instr-limit` threshold for cold callsites"));
120
121 static cl::opt<bool> PrintImports("print-imports", cl::init(false), cl::Hidden,
122 cl::desc("Print imported functions"));
123
124 static cl::opt<bool> PrintImportFailures(
125 "print-import-failures", cl::init(false), cl::Hidden,
126 cl::desc("Print information for functions rejected for importing"));
127
128 static cl::opt<bool> ComputeDead("compute-dead", cl::init(true), cl::Hidden,
129 cl::desc("Compute dead symbols"));
130
131 static cl::opt<bool> EnableImportMetadata(
132 "enable-import-metadata", cl::init(false), cl::Hidden,
133 cl::desc("Enable import metadata like 'thinlto_src_module'"));
134
135 /// Summary file to use for function importing when using -function-import from
136 /// the command line.
137 static cl::opt<std::string>
138 SummaryFile("summary-file",
139 cl::desc("The summary file to use for function importing."));
140
141 /// Used when testing importing from distributed indexes via opt
142 // -function-import.
143 static cl::opt<bool>
144 ImportAllIndex("import-all-index",
145 cl::desc("Import all external functions in index."));
146
147 // Load lazily a module from \p FileName in \p Context.
loadFile(const std::string & FileName,LLVMContext & Context)148 static std::unique_ptr<Module> loadFile(const std::string &FileName,
149 LLVMContext &Context) {
150 SMDiagnostic Err;
151 LLVM_DEBUG(dbgs() << "Loading '" << FileName << "'\n");
152 // Metadata isn't loaded until functions are imported, to minimize
153 // the memory overhead.
154 std::unique_ptr<Module> Result =
155 getLazyIRFileModule(FileName, Err, Context,
156 /* ShouldLazyLoadMetadata = */ true);
157 if (!Result) {
158 Err.print("function-import", errs());
159 report_fatal_error("Abort");
160 }
161
162 return Result;
163 }
164
165 /// Given a list of possible callee implementation for a call site, select one
166 /// that fits the \p Threshold.
167 ///
168 /// FIXME: select "best" instead of first that fits. But what is "best"?
169 /// - The smallest: more likely to be inlined.
170 /// - The one with the least outgoing edges (already well optimized).
171 /// - One from a module already being imported from in order to reduce the
172 /// number of source modules parsed/linked.
173 /// - One that has PGO data attached.
174 /// - [insert you fancy metric here]
175 static const GlobalValueSummary *
selectCallee(const ModuleSummaryIndex & Index,ArrayRef<std::unique_ptr<GlobalValueSummary>> CalleeSummaryList,unsigned Threshold,StringRef CallerModulePath,FunctionImporter::ImportFailureReason & Reason,GlobalValue::GUID GUID)176 selectCallee(const ModuleSummaryIndex &Index,
177 ArrayRef<std::unique_ptr<GlobalValueSummary>> CalleeSummaryList,
178 unsigned Threshold, StringRef CallerModulePath,
179 FunctionImporter::ImportFailureReason &Reason,
180 GlobalValue::GUID GUID) {
181 Reason = FunctionImporter::ImportFailureReason::None;
182 auto It = llvm::find_if(
183 CalleeSummaryList,
184 [&](const std::unique_ptr<GlobalValueSummary> &SummaryPtr) {
185 auto *GVSummary = SummaryPtr.get();
186 if (!Index.isGlobalValueLive(GVSummary)) {
187 Reason = FunctionImporter::ImportFailureReason::NotLive;
188 return false;
189 }
190
191 if (GlobalValue::isInterposableLinkage(GVSummary->linkage())) {
192 Reason = FunctionImporter::ImportFailureReason::InterposableLinkage;
193 // There is no point in importing these, we can't inline them
194 return false;
195 }
196
197 auto *Summary = cast<FunctionSummary>(GVSummary->getBaseObject());
198
199 // If this is a local function, make sure we import the copy
200 // in the caller's module. The only time a local function can
201 // share an entry in the index is if there is a local with the same name
202 // in another module that had the same source file name (in a different
203 // directory), where each was compiled in their own directory so there
204 // was not distinguishing path.
205 // However, do the import from another module if there is only one
206 // entry in the list - in that case this must be a reference due
207 // to indirect call profile data, since a function pointer can point to
208 // a local in another module.
209 if (GlobalValue::isLocalLinkage(Summary->linkage()) &&
210 CalleeSummaryList.size() > 1 &&
211 Summary->modulePath() != CallerModulePath) {
212 Reason =
213 FunctionImporter::ImportFailureReason::LocalLinkageNotInModule;
214 return false;
215 }
216
217 if ((Summary->instCount() > Threshold) &&
218 !Summary->fflags().AlwaysInline && !ForceImportAll) {
219 Reason = FunctionImporter::ImportFailureReason::TooLarge;
220 return false;
221 }
222
223 // Skip if it isn't legal to import (e.g. may reference unpromotable
224 // locals).
225 if (Summary->notEligibleToImport()) {
226 Reason = FunctionImporter::ImportFailureReason::NotEligible;
227 return false;
228 }
229
230 // Don't bother importing if we can't inline it anyway.
231 if (Summary->fflags().NoInline && !ForceImportAll) {
232 Reason = FunctionImporter::ImportFailureReason::NoInline;
233 return false;
234 }
235
236 return true;
237 });
238 if (It == CalleeSummaryList.end())
239 return nullptr;
240
241 return cast<GlobalValueSummary>(It->get());
242 }
243
244 namespace {
245
246 using EdgeInfo =
247 std::tuple<const GlobalValueSummary *, unsigned /* Threshold */>;
248
249 } // anonymous namespace
250
shouldImportGlobal(const ValueInfo & VI,const GVSummaryMapTy & DefinedGVSummaries)251 static bool shouldImportGlobal(const ValueInfo &VI,
252 const GVSummaryMapTy &DefinedGVSummaries) {
253 const auto &GVS = DefinedGVSummaries.find(VI.getGUID());
254 if (GVS == DefinedGVSummaries.end())
255 return true;
256 // We should not skip import if the module contains a definition with
257 // interposable linkage type. This is required for correctness in
258 // the situation with two following conditions:
259 // * the def with interposable linkage is non-prevailing,
260 // * there is a prevailing def available for import and marked read-only.
261 // In this case, the non-prevailing def will be converted to a declaration,
262 // while the prevailing one becomes internal, thus no definitions will be
263 // available for linking. In order to prevent undefined symbol link error,
264 // the prevailing definition must be imported.
265 // FIXME: Consider adding a check that the suitable prevailing definition
266 // exists and marked read-only.
267 if (VI.getSummaryList().size() > 1 &&
268 GlobalValue::isInterposableLinkage(GVS->second->linkage()))
269 return true;
270
271 return false;
272 }
273
computeImportForReferencedGlobals(const GlobalValueSummary & Summary,const ModuleSummaryIndex & Index,const GVSummaryMapTy & DefinedGVSummaries,SmallVectorImpl<EdgeInfo> & Worklist,FunctionImporter::ImportMapTy & ImportList,StringMap<FunctionImporter::ExportSetTy> * ExportLists)274 static void computeImportForReferencedGlobals(
275 const GlobalValueSummary &Summary, const ModuleSummaryIndex &Index,
276 const GVSummaryMapTy &DefinedGVSummaries,
277 SmallVectorImpl<EdgeInfo> &Worklist,
278 FunctionImporter::ImportMapTy &ImportList,
279 StringMap<FunctionImporter::ExportSetTy> *ExportLists) {
280 for (auto &VI : Summary.refs()) {
281 if (!shouldImportGlobal(VI, DefinedGVSummaries)) {
282 LLVM_DEBUG(
283 dbgs() << "Ref ignored! Target already in destination module.\n");
284 continue;
285 }
286
287 LLVM_DEBUG(dbgs() << " ref -> " << VI << "\n");
288
289 // If this is a local variable, make sure we import the copy
290 // in the caller's module. The only time a local variable can
291 // share an entry in the index is if there is a local with the same name
292 // in another module that had the same source file name (in a different
293 // directory), where each was compiled in their own directory so there
294 // was not distinguishing path.
295 auto LocalNotInModule = [&](const GlobalValueSummary *RefSummary) -> bool {
296 return GlobalValue::isLocalLinkage(RefSummary->linkage()) &&
297 RefSummary->modulePath() != Summary.modulePath();
298 };
299
300 for (auto &RefSummary : VI.getSummaryList())
301 if (isa<GlobalVarSummary>(RefSummary.get()) &&
302 Index.canImportGlobalVar(RefSummary.get(), /* AnalyzeRefs */ true) &&
303 !LocalNotInModule(RefSummary.get())) {
304 auto ILI = ImportList[RefSummary->modulePath()].insert(VI.getGUID());
305 // Only update stat and exports if we haven't already imported this
306 // variable.
307 if (!ILI.second)
308 break;
309 NumImportedGlobalVarsThinLink++;
310 // Any references made by this variable will be marked exported later,
311 // in ComputeCrossModuleImport, after import decisions are complete,
312 // which is more efficient than adding them here.
313 if (ExportLists)
314 (*ExportLists)[RefSummary->modulePath()].insert(VI);
315
316 // If variable is not writeonly we attempt to recursively analyze
317 // its references in order to import referenced constants.
318 if (!Index.isWriteOnly(cast<GlobalVarSummary>(RefSummary.get())))
319 Worklist.emplace_back(RefSummary.get(), 0);
320 break;
321 }
322 }
323 }
324
325 static const char *
getFailureName(FunctionImporter::ImportFailureReason Reason)326 getFailureName(FunctionImporter::ImportFailureReason Reason) {
327 switch (Reason) {
328 case FunctionImporter::ImportFailureReason::None:
329 return "None";
330 case FunctionImporter::ImportFailureReason::GlobalVar:
331 return "GlobalVar";
332 case FunctionImporter::ImportFailureReason::NotLive:
333 return "NotLive";
334 case FunctionImporter::ImportFailureReason::TooLarge:
335 return "TooLarge";
336 case FunctionImporter::ImportFailureReason::InterposableLinkage:
337 return "InterposableLinkage";
338 case FunctionImporter::ImportFailureReason::LocalLinkageNotInModule:
339 return "LocalLinkageNotInModule";
340 case FunctionImporter::ImportFailureReason::NotEligible:
341 return "NotEligible";
342 case FunctionImporter::ImportFailureReason::NoInline:
343 return "NoInline";
344 }
345 llvm_unreachable("invalid reason");
346 }
347
348 /// Compute the list of functions to import for a given caller. Mark these
349 /// imported functions and the symbols they reference in their source module as
350 /// exported from their source module.
computeImportForFunction(const FunctionSummary & Summary,const ModuleSummaryIndex & Index,const unsigned Threshold,const GVSummaryMapTy & DefinedGVSummaries,SmallVectorImpl<EdgeInfo> & Worklist,FunctionImporter::ImportMapTy & ImportList,StringMap<FunctionImporter::ExportSetTy> * ExportLists,FunctionImporter::ImportThresholdsTy & ImportThresholds)351 static void computeImportForFunction(
352 const FunctionSummary &Summary, const ModuleSummaryIndex &Index,
353 const unsigned Threshold, const GVSummaryMapTy &DefinedGVSummaries,
354 SmallVectorImpl<EdgeInfo> &Worklist,
355 FunctionImporter::ImportMapTy &ImportList,
356 StringMap<FunctionImporter::ExportSetTy> *ExportLists,
357 FunctionImporter::ImportThresholdsTy &ImportThresholds) {
358 computeImportForReferencedGlobals(Summary, Index, DefinedGVSummaries,
359 Worklist, ImportList, ExportLists);
360 static int ImportCount = 0;
361 for (auto &Edge : Summary.calls()) {
362 ValueInfo VI = Edge.first;
363 LLVM_DEBUG(dbgs() << " edge -> " << VI << " Threshold:" << Threshold
364 << "\n");
365
366 if (ImportCutoff >= 0 && ImportCount >= ImportCutoff) {
367 LLVM_DEBUG(dbgs() << "ignored! import-cutoff value of " << ImportCutoff
368 << " reached.\n");
369 continue;
370 }
371
372 if (DefinedGVSummaries.count(VI.getGUID())) {
373 // FIXME: Consider not skipping import if the module contains
374 // a non-prevailing def with interposable linkage. The prevailing copy
375 // can safely be imported (see shouldImportGlobal()).
376 LLVM_DEBUG(dbgs() << "ignored! Target already in destination module.\n");
377 continue;
378 }
379
380 auto GetBonusMultiplier = [](CalleeInfo::HotnessType Hotness) -> float {
381 if (Hotness == CalleeInfo::HotnessType::Hot)
382 return ImportHotMultiplier;
383 if (Hotness == CalleeInfo::HotnessType::Cold)
384 return ImportColdMultiplier;
385 if (Hotness == CalleeInfo::HotnessType::Critical)
386 return ImportCriticalMultiplier;
387 return 1.0;
388 };
389
390 const auto NewThreshold =
391 Threshold * GetBonusMultiplier(Edge.second.getHotness());
392
393 auto IT = ImportThresholds.insert(std::make_pair(
394 VI.getGUID(), std::make_tuple(NewThreshold, nullptr, nullptr)));
395 bool PreviouslyVisited = !IT.second;
396 auto &ProcessedThreshold = std::get<0>(IT.first->second);
397 auto &CalleeSummary = std::get<1>(IT.first->second);
398 auto &FailureInfo = std::get<2>(IT.first->second);
399
400 bool IsHotCallsite =
401 Edge.second.getHotness() == CalleeInfo::HotnessType::Hot;
402 bool IsCriticalCallsite =
403 Edge.second.getHotness() == CalleeInfo::HotnessType::Critical;
404
405 const FunctionSummary *ResolvedCalleeSummary = nullptr;
406 if (CalleeSummary) {
407 assert(PreviouslyVisited);
408 // Since the traversal of the call graph is DFS, we can revisit a function
409 // a second time with a higher threshold. In this case, it is added back
410 // to the worklist with the new threshold (so that its own callee chains
411 // can be considered with the higher threshold).
412 if (NewThreshold <= ProcessedThreshold) {
413 LLVM_DEBUG(
414 dbgs() << "ignored! Target was already imported with Threshold "
415 << ProcessedThreshold << "\n");
416 continue;
417 }
418 // Update with new larger threshold.
419 ProcessedThreshold = NewThreshold;
420 ResolvedCalleeSummary = cast<FunctionSummary>(CalleeSummary);
421 } else {
422 // If we already rejected importing a callee at the same or higher
423 // threshold, don't waste time calling selectCallee.
424 if (PreviouslyVisited && NewThreshold <= ProcessedThreshold) {
425 LLVM_DEBUG(
426 dbgs() << "ignored! Target was already rejected with Threshold "
427 << ProcessedThreshold << "\n");
428 if (PrintImportFailures) {
429 assert(FailureInfo &&
430 "Expected FailureInfo for previously rejected candidate");
431 FailureInfo->Attempts++;
432 }
433 continue;
434 }
435
436 FunctionImporter::ImportFailureReason Reason;
437 CalleeSummary = selectCallee(Index, VI.getSummaryList(), NewThreshold,
438 Summary.modulePath(), Reason, VI.getGUID());
439 if (!CalleeSummary) {
440 // Update with new larger threshold if this was a retry (otherwise
441 // we would have already inserted with NewThreshold above). Also
442 // update failure info if requested.
443 if (PreviouslyVisited) {
444 ProcessedThreshold = NewThreshold;
445 if (PrintImportFailures) {
446 assert(FailureInfo &&
447 "Expected FailureInfo for previously rejected candidate");
448 FailureInfo->Reason = Reason;
449 FailureInfo->Attempts++;
450 FailureInfo->MaxHotness =
451 std::max(FailureInfo->MaxHotness, Edge.second.getHotness());
452 }
453 } else if (PrintImportFailures) {
454 assert(!FailureInfo &&
455 "Expected no FailureInfo for newly rejected candidate");
456 FailureInfo = std::make_unique<FunctionImporter::ImportFailureInfo>(
457 VI, Edge.second.getHotness(), Reason, 1);
458 }
459 if (ForceImportAll) {
460 std::string Msg = std::string("Failed to import function ") +
461 VI.name().str() + " due to " +
462 getFailureName(Reason);
463 auto Error = make_error<StringError>(
464 Msg, make_error_code(errc::not_supported));
465 logAllUnhandledErrors(std::move(Error), errs(),
466 "Error importing module: ");
467 break;
468 } else {
469 LLVM_DEBUG(dbgs()
470 << "ignored! No qualifying callee with summary found.\n");
471 continue;
472 }
473 }
474
475 // "Resolve" the summary
476 CalleeSummary = CalleeSummary->getBaseObject();
477 ResolvedCalleeSummary = cast<FunctionSummary>(CalleeSummary);
478
479 assert((ResolvedCalleeSummary->fflags().AlwaysInline || ForceImportAll ||
480 (ResolvedCalleeSummary->instCount() <= NewThreshold)) &&
481 "selectCallee() didn't honor the threshold");
482
483 auto ExportModulePath = ResolvedCalleeSummary->modulePath();
484 auto ILI = ImportList[ExportModulePath].insert(VI.getGUID());
485 // We previously decided to import this GUID definition if it was already
486 // inserted in the set of imports from the exporting module.
487 bool PreviouslyImported = !ILI.second;
488 if (!PreviouslyImported) {
489 NumImportedFunctionsThinLink++;
490 if (IsHotCallsite)
491 NumImportedHotFunctionsThinLink++;
492 if (IsCriticalCallsite)
493 NumImportedCriticalFunctionsThinLink++;
494 }
495
496 // Any calls/references made by this function will be marked exported
497 // later, in ComputeCrossModuleImport, after import decisions are
498 // complete, which is more efficient than adding them here.
499 if (ExportLists)
500 (*ExportLists)[ExportModulePath].insert(VI);
501 }
502
503 auto GetAdjustedThreshold = [](unsigned Threshold, bool IsHotCallsite) {
504 // Adjust the threshold for next level of imported functions.
505 // The threshold is different for hot callsites because we can then
506 // inline chains of hot calls.
507 if (IsHotCallsite)
508 return Threshold * ImportHotInstrFactor;
509 return Threshold * ImportInstrFactor;
510 };
511
512 const auto AdjThreshold = GetAdjustedThreshold(Threshold, IsHotCallsite);
513
514 ImportCount++;
515
516 // Insert the newly imported function to the worklist.
517 Worklist.emplace_back(ResolvedCalleeSummary, AdjThreshold);
518 }
519 }
520
521 /// Given the list of globals defined in a module, compute the list of imports
522 /// as well as the list of "exports", i.e. the list of symbols referenced from
523 /// another module (that may require promotion).
ComputeImportForModule(const GVSummaryMapTy & DefinedGVSummaries,const ModuleSummaryIndex & Index,StringRef ModName,FunctionImporter::ImportMapTy & ImportList,StringMap<FunctionImporter::ExportSetTy> * ExportLists=nullptr)524 static void ComputeImportForModule(
525 const GVSummaryMapTy &DefinedGVSummaries, const ModuleSummaryIndex &Index,
526 StringRef ModName, FunctionImporter::ImportMapTy &ImportList,
527 StringMap<FunctionImporter::ExportSetTy> *ExportLists = nullptr) {
528 // Worklist contains the list of function imported in this module, for which
529 // we will analyse the callees and may import further down the callgraph.
530 SmallVector<EdgeInfo, 128> Worklist;
531 FunctionImporter::ImportThresholdsTy ImportThresholds;
532
533 // Populate the worklist with the import for the functions in the current
534 // module
535 for (auto &GVSummary : DefinedGVSummaries) {
536 #ifndef NDEBUG
537 // FIXME: Change the GVSummaryMapTy to hold ValueInfo instead of GUID
538 // so this map look up (and possibly others) can be avoided.
539 auto VI = Index.getValueInfo(GVSummary.first);
540 #endif
541 if (!Index.isGlobalValueLive(GVSummary.second)) {
542 LLVM_DEBUG(dbgs() << "Ignores Dead GUID: " << VI << "\n");
543 continue;
544 }
545 auto *FuncSummary =
546 dyn_cast<FunctionSummary>(GVSummary.second->getBaseObject());
547 if (!FuncSummary)
548 // Skip import for global variables
549 continue;
550 LLVM_DEBUG(dbgs() << "Initialize import for " << VI << "\n");
551 computeImportForFunction(*FuncSummary, Index, ImportInstrLimit,
552 DefinedGVSummaries, Worklist, ImportList,
553 ExportLists, ImportThresholds);
554 }
555
556 // Process the newly imported functions and add callees to the worklist.
557 while (!Worklist.empty()) {
558 auto GVInfo = Worklist.pop_back_val();
559 auto *Summary = std::get<0>(GVInfo);
560 auto Threshold = std::get<1>(GVInfo);
561
562 if (auto *FS = dyn_cast<FunctionSummary>(Summary))
563 computeImportForFunction(*FS, Index, Threshold, DefinedGVSummaries,
564 Worklist, ImportList, ExportLists,
565 ImportThresholds);
566 else
567 computeImportForReferencedGlobals(*Summary, Index, DefinedGVSummaries,
568 Worklist, ImportList, ExportLists);
569 }
570
571 // Print stats about functions considered but rejected for importing
572 // when requested.
573 if (PrintImportFailures) {
574 dbgs() << "Missed imports into module " << ModName << "\n";
575 for (auto &I : ImportThresholds) {
576 auto &ProcessedThreshold = std::get<0>(I.second);
577 auto &CalleeSummary = std::get<1>(I.second);
578 auto &FailureInfo = std::get<2>(I.second);
579 if (CalleeSummary)
580 continue; // We are going to import.
581 assert(FailureInfo);
582 FunctionSummary *FS = nullptr;
583 if (!FailureInfo->VI.getSummaryList().empty())
584 FS = dyn_cast<FunctionSummary>(
585 FailureInfo->VI.getSummaryList()[0]->getBaseObject());
586 dbgs() << FailureInfo->VI
587 << ": Reason = " << getFailureName(FailureInfo->Reason)
588 << ", Threshold = " << ProcessedThreshold
589 << ", Size = " << (FS ? (int)FS->instCount() : -1)
590 << ", MaxHotness = " << getHotnessName(FailureInfo->MaxHotness)
591 << ", Attempts = " << FailureInfo->Attempts << "\n";
592 }
593 }
594 }
595
596 #ifndef NDEBUG
isGlobalVarSummary(const ModuleSummaryIndex & Index,ValueInfo VI)597 static bool isGlobalVarSummary(const ModuleSummaryIndex &Index, ValueInfo VI) {
598 auto SL = VI.getSummaryList();
599 return SL.empty()
600 ? false
601 : SL[0]->getSummaryKind() == GlobalValueSummary::GlobalVarKind;
602 }
603
isGlobalVarSummary(const ModuleSummaryIndex & Index,GlobalValue::GUID G)604 static bool isGlobalVarSummary(const ModuleSummaryIndex &Index,
605 GlobalValue::GUID G) {
606 if (const auto &VI = Index.getValueInfo(G))
607 return isGlobalVarSummary(Index, VI);
608 return false;
609 }
610
611 template <class T>
numGlobalVarSummaries(const ModuleSummaryIndex & Index,T & Cont)612 static unsigned numGlobalVarSummaries(const ModuleSummaryIndex &Index,
613 T &Cont) {
614 unsigned NumGVS = 0;
615 for (auto &V : Cont)
616 if (isGlobalVarSummary(Index, V))
617 ++NumGVS;
618 return NumGVS;
619 }
620 #endif
621
622 #ifndef NDEBUG
623 static bool
checkVariableImport(const ModuleSummaryIndex & Index,StringMap<FunctionImporter::ImportMapTy> & ImportLists,StringMap<FunctionImporter::ExportSetTy> & ExportLists)624 checkVariableImport(const ModuleSummaryIndex &Index,
625 StringMap<FunctionImporter::ImportMapTy> &ImportLists,
626 StringMap<FunctionImporter::ExportSetTy> &ExportLists) {
627
628 DenseSet<GlobalValue::GUID> FlattenedImports;
629
630 for (auto &ImportPerModule : ImportLists)
631 for (auto &ExportPerModule : ImportPerModule.second)
632 FlattenedImports.insert(ExportPerModule.second.begin(),
633 ExportPerModule.second.end());
634
635 // Checks that all GUIDs of read/writeonly vars we see in export lists
636 // are also in the import lists. Otherwise we my face linker undefs,
637 // because readonly and writeonly vars are internalized in their
638 // source modules.
639 auto IsReadOrWriteOnlyVar = [&](StringRef ModulePath, const ValueInfo &VI) {
640 auto *GVS = dyn_cast_or_null<GlobalVarSummary>(
641 Index.findSummaryInModule(VI, ModulePath));
642 return GVS && (Index.isReadOnly(GVS) || Index.isWriteOnly(GVS));
643 };
644
645 for (auto &ExportPerModule : ExportLists)
646 for (auto &VI : ExportPerModule.second)
647 if (!FlattenedImports.count(VI.getGUID()) &&
648 IsReadOrWriteOnlyVar(ExportPerModule.first(), VI))
649 return false;
650
651 return true;
652 }
653 #endif
654
655 /// Compute all the import and export for every module using the Index.
ComputeCrossModuleImport(const ModuleSummaryIndex & Index,const StringMap<GVSummaryMapTy> & ModuleToDefinedGVSummaries,StringMap<FunctionImporter::ImportMapTy> & ImportLists,StringMap<FunctionImporter::ExportSetTy> & ExportLists)656 void llvm::ComputeCrossModuleImport(
657 const ModuleSummaryIndex &Index,
658 const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
659 StringMap<FunctionImporter::ImportMapTy> &ImportLists,
660 StringMap<FunctionImporter::ExportSetTy> &ExportLists) {
661 // For each module that has function defined, compute the import/export lists.
662 for (auto &DefinedGVSummaries : ModuleToDefinedGVSummaries) {
663 auto &ImportList = ImportLists[DefinedGVSummaries.first()];
664 LLVM_DEBUG(dbgs() << "Computing import for Module '"
665 << DefinedGVSummaries.first() << "'\n");
666 ComputeImportForModule(DefinedGVSummaries.second, Index,
667 DefinedGVSummaries.first(), ImportList,
668 &ExportLists);
669 }
670
671 // When computing imports we only added the variables and functions being
672 // imported to the export list. We also need to mark any references and calls
673 // they make as exported as well. We do this here, as it is more efficient
674 // since we may import the same values multiple times into different modules
675 // during the import computation.
676 for (auto &ELI : ExportLists) {
677 FunctionImporter::ExportSetTy NewExports;
678 const auto &DefinedGVSummaries =
679 ModuleToDefinedGVSummaries.lookup(ELI.first());
680 for (auto &EI : ELI.second) {
681 // Find the copy defined in the exporting module so that we can mark the
682 // values it references in that specific definition as exported.
683 // Below we will add all references and called values, without regard to
684 // whether they are also defined in this module. We subsequently prune the
685 // list to only include those defined in the exporting module, see comment
686 // there as to why.
687 auto DS = DefinedGVSummaries.find(EI.getGUID());
688 // Anything marked exported during the import computation must have been
689 // defined in the exporting module.
690 assert(DS != DefinedGVSummaries.end());
691 auto *S = DS->getSecond();
692 S = S->getBaseObject();
693 if (auto *GVS = dyn_cast<GlobalVarSummary>(S)) {
694 // Export referenced functions and variables. We don't export/promote
695 // objects referenced by writeonly variable initializer, because
696 // we convert such variables initializers to "zeroinitializer".
697 // See processGlobalForThinLTO.
698 if (!Index.isWriteOnly(GVS))
699 for (const auto &VI : GVS->refs())
700 NewExports.insert(VI);
701 } else {
702 auto *FS = cast<FunctionSummary>(S);
703 for (auto &Edge : FS->calls())
704 NewExports.insert(Edge.first);
705 for (auto &Ref : FS->refs())
706 NewExports.insert(Ref);
707 }
708 }
709 // Prune list computed above to only include values defined in the exporting
710 // module. We do this after the above insertion since we may hit the same
711 // ref/call target multiple times in above loop, and it is more efficient to
712 // avoid a set lookup each time.
713 for (auto EI = NewExports.begin(); EI != NewExports.end();) {
714 if (!DefinedGVSummaries.count(EI->getGUID()))
715 NewExports.erase(EI++);
716 else
717 ++EI;
718 }
719 ELI.second.insert(NewExports.begin(), NewExports.end());
720 }
721
722 assert(checkVariableImport(Index, ImportLists, ExportLists));
723 #ifndef NDEBUG
724 LLVM_DEBUG(dbgs() << "Import/Export lists for " << ImportLists.size()
725 << " modules:\n");
726 for (auto &ModuleImports : ImportLists) {
727 auto ModName = ModuleImports.first();
728 auto &Exports = ExportLists[ModName];
729 unsigned NumGVS = numGlobalVarSummaries(Index, Exports);
730 LLVM_DEBUG(dbgs() << "* Module " << ModName << " exports "
731 << Exports.size() - NumGVS << " functions and " << NumGVS
732 << " vars. Imports from " << ModuleImports.second.size()
733 << " modules.\n");
734 for (auto &Src : ModuleImports.second) {
735 auto SrcModName = Src.first();
736 unsigned NumGVSPerMod = numGlobalVarSummaries(Index, Src.second);
737 LLVM_DEBUG(dbgs() << " - " << Src.second.size() - NumGVSPerMod
738 << " functions imported from " << SrcModName << "\n");
739 LLVM_DEBUG(dbgs() << " - " << NumGVSPerMod
740 << " global vars imported from " << SrcModName << "\n");
741 }
742 }
743 #endif
744 }
745
746 #ifndef NDEBUG
dumpImportListForModule(const ModuleSummaryIndex & Index,StringRef ModulePath,FunctionImporter::ImportMapTy & ImportList)747 static void dumpImportListForModule(const ModuleSummaryIndex &Index,
748 StringRef ModulePath,
749 FunctionImporter::ImportMapTy &ImportList) {
750 LLVM_DEBUG(dbgs() << "* Module " << ModulePath << " imports from "
751 << ImportList.size() << " modules.\n");
752 for (auto &Src : ImportList) {
753 auto SrcModName = Src.first();
754 unsigned NumGVSPerMod = numGlobalVarSummaries(Index, Src.second);
755 LLVM_DEBUG(dbgs() << " - " << Src.second.size() - NumGVSPerMod
756 << " functions imported from " << SrcModName << "\n");
757 LLVM_DEBUG(dbgs() << " - " << NumGVSPerMod << " vars imported from "
758 << SrcModName << "\n");
759 }
760 }
761 #endif
762
763 /// Compute all the imports for the given module in the Index.
ComputeCrossModuleImportForModule(StringRef ModulePath,const ModuleSummaryIndex & Index,FunctionImporter::ImportMapTy & ImportList)764 void llvm::ComputeCrossModuleImportForModule(
765 StringRef ModulePath, const ModuleSummaryIndex &Index,
766 FunctionImporter::ImportMapTy &ImportList) {
767 // Collect the list of functions this module defines.
768 // GUID -> Summary
769 GVSummaryMapTy FunctionSummaryMap;
770 Index.collectDefinedFunctionsForModule(ModulePath, FunctionSummaryMap);
771
772 // Compute the import list for this module.
773 LLVM_DEBUG(dbgs() << "Computing import for Module '" << ModulePath << "'\n");
774 ComputeImportForModule(FunctionSummaryMap, Index, ModulePath, ImportList);
775
776 #ifndef NDEBUG
777 dumpImportListForModule(Index, ModulePath, ImportList);
778 #endif
779 }
780
781 // Mark all external summaries in Index for import into the given module.
782 // Used for distributed builds using a distributed index.
ComputeCrossModuleImportForModuleFromIndex(StringRef ModulePath,const ModuleSummaryIndex & Index,FunctionImporter::ImportMapTy & ImportList)783 void llvm::ComputeCrossModuleImportForModuleFromIndex(
784 StringRef ModulePath, const ModuleSummaryIndex &Index,
785 FunctionImporter::ImportMapTy &ImportList) {
786 for (auto &GlobalList : Index) {
787 // Ignore entries for undefined references.
788 if (GlobalList.second.SummaryList.empty())
789 continue;
790
791 auto GUID = GlobalList.first;
792 assert(GlobalList.second.SummaryList.size() == 1 &&
793 "Expected individual combined index to have one summary per GUID");
794 auto &Summary = GlobalList.second.SummaryList[0];
795 // Skip the summaries for the importing module. These are included to
796 // e.g. record required linkage changes.
797 if (Summary->modulePath() == ModulePath)
798 continue;
799 // Add an entry to provoke importing by thinBackend.
800 ImportList[Summary->modulePath()].insert(GUID);
801 }
802 #ifndef NDEBUG
803 dumpImportListForModule(Index, ModulePath, ImportList);
804 #endif
805 }
806
807 // For SamplePGO, the indirect call targets for local functions will
808 // have its original name annotated in profile. We try to find the
809 // corresponding PGOFuncName as the GUID, and fix up the edges
810 // accordingly.
updateValueInfoForIndirectCalls(ModuleSummaryIndex & Index,FunctionSummary * FS)811 void updateValueInfoForIndirectCalls(ModuleSummaryIndex &Index,
812 FunctionSummary *FS) {
813 for (auto &EI : FS->mutableCalls()) {
814 if (!EI.first.getSummaryList().empty())
815 continue;
816 auto GUID = Index.getGUIDFromOriginalID(EI.first.getGUID());
817 if (GUID == 0)
818 continue;
819 // Update the edge to point directly to the correct GUID.
820 auto VI = Index.getValueInfo(GUID);
821 if (llvm::any_of(
822 VI.getSummaryList(),
823 [&](const std::unique_ptr<GlobalValueSummary> &SummaryPtr) {
824 // The mapping from OriginalId to GUID may return a GUID
825 // that corresponds to a static variable. Filter it out here.
826 // This can happen when
827 // 1) There is a call to a library function which is not defined
828 // in the index.
829 // 2) There is a static variable with the OriginalGUID identical
830 // to the GUID of the library function in 1);
831 // When this happens the static variable in 2) will be found,
832 // which needs to be filtered out.
833 return SummaryPtr->getSummaryKind() ==
834 GlobalValueSummary::GlobalVarKind;
835 }))
836 continue;
837 EI.first = VI;
838 }
839 }
840
updateIndirectCalls(ModuleSummaryIndex & Index)841 void llvm::updateIndirectCalls(ModuleSummaryIndex &Index) {
842 for (const auto &Entry : Index) {
843 for (auto &S : Entry.second.SummaryList) {
844 if (auto *FS = dyn_cast<FunctionSummary>(S.get()))
845 updateValueInfoForIndirectCalls(Index, FS);
846 }
847 }
848 }
849
computeDeadSymbolsAndUpdateIndirectCalls(ModuleSummaryIndex & Index,const DenseSet<GlobalValue::GUID> & GUIDPreservedSymbols,function_ref<PrevailingType (GlobalValue::GUID)> isPrevailing)850 void llvm::computeDeadSymbolsAndUpdateIndirectCalls(
851 ModuleSummaryIndex &Index,
852 const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols,
853 function_ref<PrevailingType(GlobalValue::GUID)> isPrevailing) {
854 assert(!Index.withGlobalValueDeadStripping());
855 if (!ComputeDead ||
856 // Don't do anything when nothing is live, this is friendly with tests.
857 GUIDPreservedSymbols.empty()) {
858 // Still need to update indirect calls.
859 updateIndirectCalls(Index);
860 return;
861 }
862 unsigned LiveSymbols = 0;
863 SmallVector<ValueInfo, 128> Worklist;
864 Worklist.reserve(GUIDPreservedSymbols.size() * 2);
865 for (auto GUID : GUIDPreservedSymbols) {
866 ValueInfo VI = Index.getValueInfo(GUID);
867 if (!VI)
868 continue;
869 for (auto &S : VI.getSummaryList())
870 S->setLive(true);
871 }
872
873 // Add values flagged in the index as live roots to the worklist.
874 for (const auto &Entry : Index) {
875 auto VI = Index.getValueInfo(Entry);
876 for (auto &S : Entry.second.SummaryList) {
877 if (auto *FS = dyn_cast<FunctionSummary>(S.get()))
878 updateValueInfoForIndirectCalls(Index, FS);
879 if (S->isLive()) {
880 LLVM_DEBUG(dbgs() << "Live root: " << VI << "\n");
881 Worklist.push_back(VI);
882 ++LiveSymbols;
883 break;
884 }
885 }
886 }
887
888 // Make value live and add it to the worklist if it was not live before.
889 auto visit = [&](ValueInfo VI, bool IsAliasee) {
890 // FIXME: If we knew which edges were created for indirect call profiles,
891 // we could skip them here. Any that are live should be reached via
892 // other edges, e.g. reference edges. Otherwise, using a profile collected
893 // on a slightly different binary might provoke preserving, importing
894 // and ultimately promoting calls to functions not linked into this
895 // binary, which increases the binary size unnecessarily. Note that
896 // if this code changes, the importer needs to change so that edges
897 // to functions marked dead are skipped.
898
899 if (llvm::any_of(VI.getSummaryList(),
900 [](const std::unique_ptr<llvm::GlobalValueSummary> &S) {
901 return S->isLive();
902 }))
903 return;
904
905 // We only keep live symbols that are known to be non-prevailing if any are
906 // available_externally, linkonceodr, weakodr. Those symbols are discarded
907 // later in the EliminateAvailableExternally pass and setting them to
908 // not-live could break downstreams users of liveness information (PR36483)
909 // or limit optimization opportunities.
910 if (isPrevailing(VI.getGUID()) == PrevailingType::No) {
911 bool KeepAliveLinkage = false;
912 bool Interposable = false;
913 for (auto &S : VI.getSummaryList()) {
914 if (S->linkage() == GlobalValue::AvailableExternallyLinkage ||
915 S->linkage() == GlobalValue::WeakODRLinkage ||
916 S->linkage() == GlobalValue::LinkOnceODRLinkage)
917 KeepAliveLinkage = true;
918 else if (GlobalValue::isInterposableLinkage(S->linkage()))
919 Interposable = true;
920 }
921
922 if (!IsAliasee) {
923 if (!KeepAliveLinkage)
924 return;
925
926 if (Interposable)
927 report_fatal_error(
928 "Interposable and available_externally/linkonce_odr/weak_odr "
929 "symbol");
930 }
931 }
932
933 for (auto &S : VI.getSummaryList())
934 S->setLive(true);
935 ++LiveSymbols;
936 Worklist.push_back(VI);
937 };
938
939 while (!Worklist.empty()) {
940 auto VI = Worklist.pop_back_val();
941 for (auto &Summary : VI.getSummaryList()) {
942 if (auto *AS = dyn_cast<AliasSummary>(Summary.get())) {
943 // If this is an alias, visit the aliasee VI to ensure that all copies
944 // are marked live and it is added to the worklist for further
945 // processing of its references.
946 visit(AS->getAliaseeVI(), true);
947 continue;
948 }
949 for (auto Ref : Summary->refs())
950 visit(Ref, false);
951 if (auto *FS = dyn_cast<FunctionSummary>(Summary.get()))
952 for (auto Call : FS->calls())
953 visit(Call.first, false);
954 }
955 }
956 Index.setWithGlobalValueDeadStripping();
957
958 unsigned DeadSymbols = Index.size() - LiveSymbols;
959 LLVM_DEBUG(dbgs() << LiveSymbols << " symbols Live, and " << DeadSymbols
960 << " symbols Dead \n");
961 NumDeadSymbols += DeadSymbols;
962 NumLiveSymbols += LiveSymbols;
963 }
964
965 // Compute dead symbols and propagate constants in combined index.
computeDeadSymbolsWithConstProp(ModuleSummaryIndex & Index,const DenseSet<GlobalValue::GUID> & GUIDPreservedSymbols,function_ref<PrevailingType (GlobalValue::GUID)> isPrevailing,bool ImportEnabled)966 void llvm::computeDeadSymbolsWithConstProp(
967 ModuleSummaryIndex &Index,
968 const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols,
969 function_ref<PrevailingType(GlobalValue::GUID)> isPrevailing,
970 bool ImportEnabled) {
971 computeDeadSymbolsAndUpdateIndirectCalls(Index, GUIDPreservedSymbols,
972 isPrevailing);
973 if (ImportEnabled)
974 Index.propagateAttributes(GUIDPreservedSymbols);
975 }
976
977 /// Compute the set of summaries needed for a ThinLTO backend compilation of
978 /// \p ModulePath.
gatherImportedSummariesForModule(StringRef ModulePath,const StringMap<GVSummaryMapTy> & ModuleToDefinedGVSummaries,const FunctionImporter::ImportMapTy & ImportList,std::map<std::string,GVSummaryMapTy> & ModuleToSummariesForIndex)979 void llvm::gatherImportedSummariesForModule(
980 StringRef ModulePath,
981 const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
982 const FunctionImporter::ImportMapTy &ImportList,
983 std::map<std::string, GVSummaryMapTy> &ModuleToSummariesForIndex) {
984 // Include all summaries from the importing module.
985 ModuleToSummariesForIndex[std::string(ModulePath)] =
986 ModuleToDefinedGVSummaries.lookup(ModulePath);
987 // Include summaries for imports.
988 for (auto &ILI : ImportList) {
989 auto &SummariesForIndex =
990 ModuleToSummariesForIndex[std::string(ILI.first())];
991 const auto &DefinedGVSummaries =
992 ModuleToDefinedGVSummaries.lookup(ILI.first());
993 for (auto &GI : ILI.second) {
994 const auto &DS = DefinedGVSummaries.find(GI);
995 assert(DS != DefinedGVSummaries.end() &&
996 "Expected a defined summary for imported global value");
997 SummariesForIndex[GI] = DS->second;
998 }
999 }
1000 }
1001
1002 /// Emit the files \p ModulePath will import from into \p OutputFilename.
EmitImportsFiles(StringRef ModulePath,StringRef OutputFilename,const std::map<std::string,GVSummaryMapTy> & ModuleToSummariesForIndex)1003 std::error_code llvm::EmitImportsFiles(
1004 StringRef ModulePath, StringRef OutputFilename,
1005 const std::map<std::string, GVSummaryMapTy> &ModuleToSummariesForIndex) {
1006 std::error_code EC;
1007 raw_fd_ostream ImportsOS(OutputFilename, EC, sys::fs::OpenFlags::OF_None);
1008 if (EC)
1009 return EC;
1010 for (auto &ILI : ModuleToSummariesForIndex)
1011 // The ModuleToSummariesForIndex map includes an entry for the current
1012 // Module (needed for writing out the index files). We don't want to
1013 // include it in the imports file, however, so filter it out.
1014 if (ILI.first != ModulePath)
1015 ImportsOS << ILI.first << "\n";
1016 return std::error_code();
1017 }
1018
convertToDeclaration(GlobalValue & GV)1019 bool llvm::convertToDeclaration(GlobalValue &GV) {
1020 LLVM_DEBUG(dbgs() << "Converting to a declaration: `" << GV.getName()
1021 << "\n");
1022 if (Function *F = dyn_cast<Function>(&GV)) {
1023 F->deleteBody();
1024 F->clearMetadata();
1025 F->setComdat(nullptr);
1026 } else if (GlobalVariable *V = dyn_cast<GlobalVariable>(&GV)) {
1027 V->setInitializer(nullptr);
1028 V->setLinkage(GlobalValue::ExternalLinkage);
1029 V->clearMetadata();
1030 V->setComdat(nullptr);
1031 } else {
1032 GlobalValue *NewGV;
1033 if (GV.getValueType()->isFunctionTy())
1034 NewGV =
1035 Function::Create(cast<FunctionType>(GV.getValueType()),
1036 GlobalValue::ExternalLinkage, GV.getAddressSpace(),
1037 "", GV.getParent());
1038 else
1039 NewGV =
1040 new GlobalVariable(*GV.getParent(), GV.getValueType(),
1041 /*isConstant*/ false, GlobalValue::ExternalLinkage,
1042 /*init*/ nullptr, "",
1043 /*insertbefore*/ nullptr, GV.getThreadLocalMode(),
1044 GV.getType()->getAddressSpace());
1045 NewGV->takeName(&GV);
1046 GV.replaceAllUsesWith(NewGV);
1047 return false;
1048 }
1049 if (!GV.isImplicitDSOLocal())
1050 GV.setDSOLocal(false);
1051 return true;
1052 }
1053
thinLTOFinalizeInModule(Module & TheModule,const GVSummaryMapTy & DefinedGlobals,bool PropagateAttrs)1054 void llvm::thinLTOFinalizeInModule(Module &TheModule,
1055 const GVSummaryMapTy &DefinedGlobals,
1056 bool PropagateAttrs) {
1057 auto FinalizeInModule = [&](GlobalValue &GV, bool Propagate = false) {
1058 // See if the global summary analysis computed a new resolved linkage.
1059 const auto &GS = DefinedGlobals.find(GV.getGUID());
1060 if (GS == DefinedGlobals.end())
1061 return;
1062
1063 if (Propagate)
1064 if (FunctionSummary *FS = dyn_cast<FunctionSummary>(GS->second)) {
1065 if (Function *F = dyn_cast<Function>(&GV)) {
1066 // TODO: propagate ReadNone and ReadOnly.
1067 if (FS->fflags().ReadNone && !F->doesNotAccessMemory())
1068 F->setDoesNotAccessMemory();
1069
1070 if (FS->fflags().ReadOnly && !F->onlyReadsMemory())
1071 F->setOnlyReadsMemory();
1072
1073 if (FS->fflags().NoRecurse && !F->doesNotRecurse())
1074 F->setDoesNotRecurse();
1075
1076 if (FS->fflags().NoUnwind && !F->doesNotThrow())
1077 F->setDoesNotThrow();
1078 }
1079 }
1080
1081 auto NewLinkage = GS->second->linkage();
1082 if (GlobalValue::isLocalLinkage(GV.getLinkage()) ||
1083 // Don't internalize anything here, because the code below
1084 // lacks necessary correctness checks. Leave this job to
1085 // LLVM 'internalize' pass.
1086 GlobalValue::isLocalLinkage(NewLinkage) ||
1087 // In case it was dead and already converted to declaration.
1088 GV.isDeclaration())
1089 return;
1090
1091 // Set the potentially more constraining visibility computed from summaries.
1092 // The DefaultVisibility condition is because older GlobalValueSummary does
1093 // not record DefaultVisibility and we don't want to change protected/hidden
1094 // to default.
1095 if (GS->second->getVisibility() != GlobalValue::DefaultVisibility)
1096 GV.setVisibility(GS->second->getVisibility());
1097
1098 if (NewLinkage == GV.getLinkage())
1099 return;
1100
1101 // Check for a non-prevailing def that has interposable linkage
1102 // (e.g. non-odr weak or linkonce). In that case we can't simply
1103 // convert to available_externally, since it would lose the
1104 // interposable property and possibly get inlined. Simply drop
1105 // the definition in that case.
1106 if (GlobalValue::isAvailableExternallyLinkage(NewLinkage) &&
1107 GlobalValue::isInterposableLinkage(GV.getLinkage())) {
1108 if (!convertToDeclaration(GV))
1109 // FIXME: Change this to collect replaced GVs and later erase
1110 // them from the parent module once thinLTOResolvePrevailingGUID is
1111 // changed to enable this for aliases.
1112 llvm_unreachable("Expected GV to be converted");
1113 } else {
1114 // If all copies of the original symbol had global unnamed addr and
1115 // linkonce_odr linkage, it should be an auto hide symbol. In that case
1116 // the thin link would have marked it as CanAutoHide. Add hidden visibility
1117 // to the symbol to preserve the property.
1118 if (NewLinkage == GlobalValue::WeakODRLinkage &&
1119 GS->second->canAutoHide()) {
1120 assert(GV.hasLinkOnceODRLinkage() && GV.hasGlobalUnnamedAddr());
1121 GV.setVisibility(GlobalValue::HiddenVisibility);
1122 }
1123
1124 LLVM_DEBUG(dbgs() << "ODR fixing up linkage for `" << GV.getName()
1125 << "` from " << GV.getLinkage() << " to " << NewLinkage
1126 << "\n");
1127 GV.setLinkage(NewLinkage);
1128 }
1129 // Remove declarations from comdats, including available_externally
1130 // as this is a declaration for the linker, and will be dropped eventually.
1131 // It is illegal for comdats to contain declarations.
1132 auto *GO = dyn_cast_or_null<GlobalObject>(&GV);
1133 if (GO && GO->isDeclarationForLinker() && GO->hasComdat())
1134 GO->setComdat(nullptr);
1135 };
1136
1137 // Process functions and global now
1138 for (auto &GV : TheModule)
1139 FinalizeInModule(GV, PropagateAttrs);
1140 for (auto &GV : TheModule.globals())
1141 FinalizeInModule(GV);
1142 for (auto &GV : TheModule.aliases())
1143 FinalizeInModule(GV);
1144 }
1145
1146 /// Run internalization on \p TheModule based on symmary analysis.
thinLTOInternalizeModule(Module & TheModule,const GVSummaryMapTy & DefinedGlobals)1147 void llvm::thinLTOInternalizeModule(Module &TheModule,
1148 const GVSummaryMapTy &DefinedGlobals) {
1149 // Declare a callback for the internalize pass that will ask for every
1150 // candidate GlobalValue if it can be internalized or not.
1151 auto MustPreserveGV = [&](const GlobalValue &GV) -> bool {
1152 // Lookup the linkage recorded in the summaries during global analysis.
1153 auto GS = DefinedGlobals.find(GV.getGUID());
1154 if (GS == DefinedGlobals.end()) {
1155 // Must have been promoted (possibly conservatively). Find original
1156 // name so that we can access the correct summary and see if it can
1157 // be internalized again.
1158 // FIXME: Eventually we should control promotion instead of promoting
1159 // and internalizing again.
1160 StringRef OrigName =
1161 ModuleSummaryIndex::getOriginalNameBeforePromote(GV.getName());
1162 std::string OrigId = GlobalValue::getGlobalIdentifier(
1163 OrigName, GlobalValue::InternalLinkage,
1164 TheModule.getSourceFileName());
1165 GS = DefinedGlobals.find(GlobalValue::getGUID(OrigId));
1166 if (GS == DefinedGlobals.end()) {
1167 // Also check the original non-promoted non-globalized name. In some
1168 // cases a preempted weak value is linked in as a local copy because
1169 // it is referenced by an alias (IRLinker::linkGlobalValueProto).
1170 // In that case, since it was originally not a local value, it was
1171 // recorded in the index using the original name.
1172 // FIXME: This may not be needed once PR27866 is fixed.
1173 GS = DefinedGlobals.find(GlobalValue::getGUID(OrigName));
1174 assert(GS != DefinedGlobals.end());
1175 }
1176 }
1177 return !GlobalValue::isLocalLinkage(GS->second->linkage());
1178 };
1179
1180 // FIXME: See if we can just internalize directly here via linkage changes
1181 // based on the index, rather than invoking internalizeModule.
1182 internalizeModule(TheModule, MustPreserveGV);
1183 }
1184
1185 /// Make alias a clone of its aliasee.
replaceAliasWithAliasee(Module * SrcModule,GlobalAlias * GA)1186 static Function *replaceAliasWithAliasee(Module *SrcModule, GlobalAlias *GA) {
1187 Function *Fn = cast<Function>(GA->getAliaseeObject());
1188
1189 ValueToValueMapTy VMap;
1190 Function *NewFn = CloneFunction(Fn, VMap);
1191 // Clone should use the original alias's linkage, visibility and name, and we
1192 // ensure all uses of alias instead use the new clone (casted if necessary).
1193 NewFn->setLinkage(GA->getLinkage());
1194 NewFn->setVisibility(GA->getVisibility());
1195 GA->replaceAllUsesWith(ConstantExpr::getBitCast(NewFn, GA->getType()));
1196 NewFn->takeName(GA);
1197 return NewFn;
1198 }
1199
1200 // Internalize values that we marked with specific attribute
1201 // in processGlobalForThinLTO.
internalizeGVsAfterImport(Module & M)1202 static void internalizeGVsAfterImport(Module &M) {
1203 for (auto &GV : M.globals())
1204 // Skip GVs which have been converted to declarations
1205 // by dropDeadSymbols.
1206 if (!GV.isDeclaration() && GV.hasAttribute("thinlto-internalize")) {
1207 GV.setLinkage(GlobalValue::InternalLinkage);
1208 GV.setVisibility(GlobalValue::DefaultVisibility);
1209 }
1210 }
1211
1212 // Automatically import functions in Module \p DestModule based on the summaries
1213 // index.
importFunctions(Module & DestModule,const FunctionImporter::ImportMapTy & ImportList)1214 Expected<bool> FunctionImporter::importFunctions(
1215 Module &DestModule, const FunctionImporter::ImportMapTy &ImportList) {
1216 LLVM_DEBUG(dbgs() << "Starting import for Module "
1217 << DestModule.getModuleIdentifier() << "\n");
1218 unsigned ImportedCount = 0, ImportedGVCount = 0;
1219
1220 IRMover Mover(DestModule);
1221 // Do the actual import of functions now, one Module at a time
1222 std::set<StringRef> ModuleNameOrderedList;
1223 for (auto &FunctionsToImportPerModule : ImportList) {
1224 ModuleNameOrderedList.insert(FunctionsToImportPerModule.first());
1225 }
1226 for (auto &Name : ModuleNameOrderedList) {
1227 // Get the module for the import
1228 const auto &FunctionsToImportPerModule = ImportList.find(Name);
1229 assert(FunctionsToImportPerModule != ImportList.end());
1230 Expected<std::unique_ptr<Module>> SrcModuleOrErr = ModuleLoader(Name);
1231 if (!SrcModuleOrErr)
1232 return SrcModuleOrErr.takeError();
1233 std::unique_ptr<Module> SrcModule = std::move(*SrcModuleOrErr);
1234 assert(&DestModule.getContext() == &SrcModule->getContext() &&
1235 "Context mismatch");
1236
1237 // If modules were created with lazy metadata loading, materialize it
1238 // now, before linking it (otherwise this will be a noop).
1239 if (Error Err = SrcModule->materializeMetadata())
1240 return std::move(Err);
1241
1242 auto &ImportGUIDs = FunctionsToImportPerModule->second;
1243 // Find the globals to import
1244 SetVector<GlobalValue *> GlobalsToImport;
1245 for (Function &F : *SrcModule) {
1246 if (!F.hasName())
1247 continue;
1248 auto GUID = F.getGUID();
1249 auto Import = ImportGUIDs.count(GUID);
1250 LLVM_DEBUG(dbgs() << (Import ? "Is" : "Not") << " importing function "
1251 << GUID << " " << F.getName() << " from "
1252 << SrcModule->getSourceFileName() << "\n");
1253 if (Import) {
1254 if (Error Err = F.materialize())
1255 return std::move(Err);
1256 if (EnableImportMetadata) {
1257 // Add 'thinlto_src_module' metadata for statistics and debugging.
1258 F.setMetadata(
1259 "thinlto_src_module",
1260 MDNode::get(DestModule.getContext(),
1261 {MDString::get(DestModule.getContext(),
1262 SrcModule->getSourceFileName())}));
1263 }
1264 GlobalsToImport.insert(&F);
1265 }
1266 }
1267 for (GlobalVariable &GV : SrcModule->globals()) {
1268 if (!GV.hasName())
1269 continue;
1270 auto GUID = GV.getGUID();
1271 auto Import = ImportGUIDs.count(GUID);
1272 LLVM_DEBUG(dbgs() << (Import ? "Is" : "Not") << " importing global "
1273 << GUID << " " << GV.getName() << " from "
1274 << SrcModule->getSourceFileName() << "\n");
1275 if (Import) {
1276 if (Error Err = GV.materialize())
1277 return std::move(Err);
1278 ImportedGVCount += GlobalsToImport.insert(&GV);
1279 }
1280 }
1281 for (GlobalAlias &GA : SrcModule->aliases()) {
1282 if (!GA.hasName())
1283 continue;
1284 auto GUID = GA.getGUID();
1285 auto Import = ImportGUIDs.count(GUID);
1286 LLVM_DEBUG(dbgs() << (Import ? "Is" : "Not") << " importing alias "
1287 << GUID << " " << GA.getName() << " from "
1288 << SrcModule->getSourceFileName() << "\n");
1289 if (Import) {
1290 if (Error Err = GA.materialize())
1291 return std::move(Err);
1292 // Import alias as a copy of its aliasee.
1293 GlobalObject *GO = GA.getAliaseeObject();
1294 if (Error Err = GO->materialize())
1295 return std::move(Err);
1296 auto *Fn = replaceAliasWithAliasee(SrcModule.get(), &GA);
1297 LLVM_DEBUG(dbgs() << "Is importing aliasee fn " << GO->getGUID() << " "
1298 << GO->getName() << " from "
1299 << SrcModule->getSourceFileName() << "\n");
1300 if (EnableImportMetadata) {
1301 // Add 'thinlto_src_module' metadata for statistics and debugging.
1302 Fn->setMetadata(
1303 "thinlto_src_module",
1304 MDNode::get(DestModule.getContext(),
1305 {MDString::get(DestModule.getContext(),
1306 SrcModule->getSourceFileName())}));
1307 }
1308 GlobalsToImport.insert(Fn);
1309 }
1310 }
1311
1312 // Upgrade debug info after we're done materializing all the globals and we
1313 // have loaded all the required metadata!
1314 UpgradeDebugInfo(*SrcModule);
1315
1316 // Set the partial sample profile ratio in the profile summary module flag
1317 // of the imported source module, if applicable, so that the profile summary
1318 // module flag will match with that of the destination module when it's
1319 // imported.
1320 SrcModule->setPartialSampleProfileRatio(Index);
1321
1322 // Link in the specified functions.
1323 if (renameModuleForThinLTO(*SrcModule, Index, ClearDSOLocalOnDeclarations,
1324 &GlobalsToImport))
1325 return true;
1326
1327 if (PrintImports) {
1328 for (const auto *GV : GlobalsToImport)
1329 dbgs() << DestModule.getSourceFileName() << ": Import " << GV->getName()
1330 << " from " << SrcModule->getSourceFileName() << "\n";
1331 }
1332
1333 if (Error Err = Mover.move(
1334 std::move(SrcModule), GlobalsToImport.getArrayRef(),
1335 [](GlobalValue &, IRMover::ValueAdder) {},
1336 /*IsPerformingImport=*/true))
1337 report_fatal_error(Twine("Function Import: link error: ") +
1338 toString(std::move(Err)));
1339
1340 ImportedCount += GlobalsToImport.size();
1341 NumImportedModules++;
1342 }
1343
1344 internalizeGVsAfterImport(DestModule);
1345
1346 NumImportedFunctions += (ImportedCount - ImportedGVCount);
1347 NumImportedGlobalVars += ImportedGVCount;
1348
1349 LLVM_DEBUG(dbgs() << "Imported " << ImportedCount - ImportedGVCount
1350 << " functions for Module "
1351 << DestModule.getModuleIdentifier() << "\n");
1352 LLVM_DEBUG(dbgs() << "Imported " << ImportedGVCount
1353 << " global variables for Module "
1354 << DestModule.getModuleIdentifier() << "\n");
1355 return ImportedCount;
1356 }
1357
doImportingForModule(Module & M)1358 static bool doImportingForModule(Module &M) {
1359 if (SummaryFile.empty())
1360 report_fatal_error("error: -function-import requires -summary-file\n");
1361 Expected<std::unique_ptr<ModuleSummaryIndex>> IndexPtrOrErr =
1362 getModuleSummaryIndexForFile(SummaryFile);
1363 if (!IndexPtrOrErr) {
1364 logAllUnhandledErrors(IndexPtrOrErr.takeError(), errs(),
1365 "Error loading file '" + SummaryFile + "': ");
1366 return false;
1367 }
1368 std::unique_ptr<ModuleSummaryIndex> Index = std::move(*IndexPtrOrErr);
1369
1370 // First step is collecting the import list.
1371 FunctionImporter::ImportMapTy ImportList;
1372 // If requested, simply import all functions in the index. This is used
1373 // when testing distributed backend handling via the opt tool, when
1374 // we have distributed indexes containing exactly the summaries to import.
1375 if (ImportAllIndex)
1376 ComputeCrossModuleImportForModuleFromIndex(M.getModuleIdentifier(), *Index,
1377 ImportList);
1378 else
1379 ComputeCrossModuleImportForModule(M.getModuleIdentifier(), *Index,
1380 ImportList);
1381
1382 // Conservatively mark all internal values as promoted. This interface is
1383 // only used when doing importing via the function importing pass. The pass
1384 // is only enabled when testing importing via the 'opt' tool, which does
1385 // not do the ThinLink that would normally determine what values to promote.
1386 for (auto &I : *Index) {
1387 for (auto &S : I.second.SummaryList) {
1388 if (GlobalValue::isLocalLinkage(S->linkage()))
1389 S->setLinkage(GlobalValue::ExternalLinkage);
1390 }
1391 }
1392
1393 // Next we need to promote to global scope and rename any local values that
1394 // are potentially exported to other modules.
1395 if (renameModuleForThinLTO(M, *Index, /*ClearDSOLocalOnDeclarations=*/false,
1396 /*GlobalsToImport=*/nullptr)) {
1397 errs() << "Error renaming module\n";
1398 return false;
1399 }
1400
1401 // Perform the import now.
1402 auto ModuleLoader = [&M](StringRef Identifier) {
1403 return loadFile(std::string(Identifier), M.getContext());
1404 };
1405 FunctionImporter Importer(*Index, ModuleLoader,
1406 /*ClearDSOLocalOnDeclarations=*/false);
1407 Expected<bool> Result = Importer.importFunctions(M, ImportList);
1408
1409 // FIXME: Probably need to propagate Errors through the pass manager.
1410 if (!Result) {
1411 logAllUnhandledErrors(Result.takeError(), errs(),
1412 "Error importing module: ");
1413 return false;
1414 }
1415
1416 return *Result;
1417 }
1418
1419 namespace {
1420
1421 /// Pass that performs cross-module function import provided a summary file.
1422 class FunctionImportLegacyPass : public ModulePass {
1423 public:
1424 /// Pass identification, replacement for typeid
1425 static char ID;
1426
FunctionImportLegacyPass()1427 explicit FunctionImportLegacyPass() : ModulePass(ID) {}
1428
1429 /// Specify pass name for debug output
getPassName() const1430 StringRef getPassName() const override { return "Function Importing"; }
1431
runOnModule(Module & M)1432 bool runOnModule(Module &M) override {
1433 if (skipModule(M))
1434 return false;
1435
1436 return doImportingForModule(M);
1437 }
1438 };
1439
1440 } // end anonymous namespace
1441
run(Module & M,ModuleAnalysisManager & AM)1442 PreservedAnalyses FunctionImportPass::run(Module &M,
1443 ModuleAnalysisManager &AM) {
1444 if (!doImportingForModule(M))
1445 return PreservedAnalyses::all();
1446
1447 return PreservedAnalyses::none();
1448 }
1449
1450 char FunctionImportLegacyPass::ID = 0;
1451 INITIALIZE_PASS(FunctionImportLegacyPass, "function-import",
1452 "Summary Based Function Import", false, false)
1453
1454 namespace llvm {
1455
createFunctionImportPass()1456 Pass *createFunctionImportPass() {
1457 return new FunctionImportLegacyPass();
1458 }
1459
1460 } // end namespace llvm
1461