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/Error.h"
43 #include "llvm/Support/ErrorHandling.h"
44 #include "llvm/Support/FileSystem.h"
45 #include "llvm/Support/SourceMgr.h"
46 #include "llvm/Support/raw_ostream.h"
47 #include "llvm/Transforms/IPO/Internalize.h"
48 #include "llvm/Transforms/Utils/Cloning.h"
49 #include "llvm/Transforms/Utils/FunctionImportUtils.h"
50 #include "llvm/Transforms/Utils/ValueMapper.h"
51 #include <cassert>
52 #include <memory>
53 #include <set>
54 #include <string>
55 #include <system_error>
56 #include <tuple>
57 #include <utility>
58
59 using namespace llvm;
60
61 #define DEBUG_TYPE "function-import"
62
63 STATISTIC(NumImportedFunctionsThinLink,
64 "Number of functions thin link decided to import");
65 STATISTIC(NumImportedHotFunctionsThinLink,
66 "Number of hot functions thin link decided to import");
67 STATISTIC(NumImportedCriticalFunctionsThinLink,
68 "Number of critical functions thin link decided to import");
69 STATISTIC(NumImportedGlobalVarsThinLink,
70 "Number of global variables thin link decided to import");
71 STATISTIC(NumImportedFunctions, "Number of functions imported in backend");
72 STATISTIC(NumImportedGlobalVars,
73 "Number of global variables imported in backend");
74 STATISTIC(NumImportedModules, "Number of modules imported from");
75 STATISTIC(NumDeadSymbols, "Number of dead stripped symbols in index");
76 STATISTIC(NumLiveSymbols, "Number of live symbols in index");
77
78 /// Limit on instruction count of imported functions.
79 static cl::opt<unsigned> ImportInstrLimit(
80 "import-instr-limit", cl::init(100), cl::Hidden, cl::value_desc("N"),
81 cl::desc("Only import functions with less than N instructions"));
82
83 static cl::opt<int> ImportCutoff(
84 "import-cutoff", cl::init(-1), cl::Hidden, cl::value_desc("N"),
85 cl::desc("Only import first N functions if N>=0 (default -1)"));
86
87 static cl::opt<float>
88 ImportInstrFactor("import-instr-evolution-factor", cl::init(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(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(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(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(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(false), cl::Hidden,
117 cl::desc("Print imported functions"));
118
119 static cl::opt<bool> PrintImportFailures(
120 "print-import-failures", cl::init(false), cl::Hidden,
121 cl::desc("Print information for functions rejected for importing"));
122
123 static cl::opt<bool> ComputeDead("compute-dead", cl::init(true), cl::Hidden,
124 cl::desc("Compute dead symbols"));
125
126 static cl::opt<bool> EnableImportMetadata(
127 "enable-import-metadata", cl::init(
128 #if !defined(NDEBUG)
129 true /*Enabled with asserts.*/
130 #else
131 false
132 #endif
133 ),
134 cl::Hidden, cl::desc("Enable import metadata like 'thinlto_src_module'"));
135
136 /// Summary file to use for function importing when using -function-import from
137 /// the command line.
138 static cl::opt<std::string>
139 SummaryFile("summary-file",
140 cl::desc("The summary file to use for function importing."));
141
142 /// Used when testing importing from distributed indexes via opt
143 // -function-import.
144 static cl::opt<bool>
145 ImportAllIndex("import-all-index",
146 cl::desc("Import all external functions in index."));
147
148 // Load lazily a module from \p FileName in \p Context.
loadFile(const std::string & FileName,LLVMContext & Context)149 static std::unique_ptr<Module> loadFile(const std::string &FileName,
150 LLVMContext &Context) {
151 SMDiagnostic Err;
152 LLVM_DEBUG(dbgs() << "Loading '" << FileName << "'\n");
153 // Metadata isn't loaded until functions are imported, to minimize
154 // the memory overhead.
155 std::unique_ptr<Module> Result =
156 getLazyIRFileModule(FileName, Err, Context,
157 /* ShouldLazyLoadMetadata = */ true);
158 if (!Result) {
159 Err.print("function-import", errs());
160 report_fatal_error("Abort");
161 }
162
163 return Result;
164 }
165
166 /// Given a list of possible callee implementation for a call site, select one
167 /// that fits the \p Threshold.
168 ///
169 /// FIXME: select "best" instead of first that fits. But what is "best"?
170 /// - The smallest: more likely to be inlined.
171 /// - The one with the least outgoing edges (already well optimized).
172 /// - One from a module already being imported from in order to reduce the
173 /// number of source modules parsed/linked.
174 /// - One that has PGO data attached.
175 /// - [insert you fancy metric here]
176 static const GlobalValueSummary *
selectCallee(const ModuleSummaryIndex & Index,ArrayRef<std::unique_ptr<GlobalValueSummary>> CalleeSummaryList,unsigned Threshold,StringRef CallerModulePath,FunctionImporter::ImportFailureReason & Reason,GlobalValue::GUID GUID)177 selectCallee(const ModuleSummaryIndex &Index,
178 ArrayRef<std::unique_ptr<GlobalValueSummary>> CalleeSummaryList,
179 unsigned Threshold, StringRef CallerModulePath,
180 FunctionImporter::ImportFailureReason &Reason,
181 GlobalValue::GUID GUID) {
182 Reason = FunctionImporter::ImportFailureReason::None;
183 auto It = llvm::find_if(
184 CalleeSummaryList,
185 [&](const std::unique_ptr<GlobalValueSummary> &SummaryPtr) {
186 auto *GVSummary = SummaryPtr.get();
187 if (!Index.isGlobalValueLive(GVSummary)) {
188 Reason = FunctionImporter::ImportFailureReason::NotLive;
189 return false;
190 }
191
192 // For SamplePGO, in computeImportForFunction the OriginalId
193 // may have been used to locate the callee summary list (See
194 // comment there).
195 // The mapping from OriginalId to GUID may return a GUID
196 // that corresponds to a static variable. Filter it out here.
197 // This can happen when
198 // 1) There is a call to a library function which is not defined
199 // in the index.
200 // 2) There is a static variable with the OriginalGUID identical
201 // to the GUID of the library function in 1);
202 // When this happens, the logic for SamplePGO kicks in and
203 // the static variable in 2) will be found, which needs to be
204 // filtered out.
205 if (GVSummary->getSummaryKind() == GlobalValueSummary::GlobalVarKind) {
206 Reason = FunctionImporter::ImportFailureReason::GlobalVar;
207 return false;
208 }
209 if (GlobalValue::isInterposableLinkage(GVSummary->linkage())) {
210 Reason = FunctionImporter::ImportFailureReason::InterposableLinkage;
211 // There is no point in importing these, we can't inline them
212 return false;
213 }
214
215 auto *Summary = cast<FunctionSummary>(GVSummary->getBaseObject());
216
217 // If this is a local function, make sure we import the copy
218 // in the caller's module. The only time a local function can
219 // share an entry in the index is if there is a local with the same name
220 // in another module that had the same source file name (in a different
221 // directory), where each was compiled in their own directory so there
222 // was not distinguishing path.
223 // However, do the import from another module if there is only one
224 // entry in the list - in that case this must be a reference due
225 // to indirect call profile data, since a function pointer can point to
226 // a local in another module.
227 if (GlobalValue::isLocalLinkage(Summary->linkage()) &&
228 CalleeSummaryList.size() > 1 &&
229 Summary->modulePath() != CallerModulePath) {
230 Reason =
231 FunctionImporter::ImportFailureReason::LocalLinkageNotInModule;
232 return false;
233 }
234
235 if ((Summary->instCount() > Threshold) &&
236 !Summary->fflags().AlwaysInline) {
237 Reason = FunctionImporter::ImportFailureReason::TooLarge;
238 return false;
239 }
240
241 // Skip if it isn't legal to import (e.g. may reference unpromotable
242 // locals).
243 if (Summary->notEligibleToImport()) {
244 Reason = FunctionImporter::ImportFailureReason::NotEligible;
245 return false;
246 }
247
248 // Don't bother importing if we can't inline it anyway.
249 if (Summary->fflags().NoInline) {
250 Reason = FunctionImporter::ImportFailureReason::NoInline;
251 return false;
252 }
253
254 return true;
255 });
256 if (It == CalleeSummaryList.end())
257 return nullptr;
258
259 return cast<GlobalValueSummary>(It->get());
260 }
261
262 namespace {
263
264 using EdgeInfo =
265 std::tuple<const GlobalValueSummary *, unsigned /* Threshold */>;
266
267 } // anonymous namespace
268
269 static ValueInfo
updateValueInfoForIndirectCalls(const ModuleSummaryIndex & Index,ValueInfo VI)270 updateValueInfoForIndirectCalls(const ModuleSummaryIndex &Index, ValueInfo VI) {
271 if (!VI.getSummaryList().empty())
272 return VI;
273 // For SamplePGO, the indirect call targets for local functions will
274 // have its original name annotated in profile. We try to find the
275 // corresponding PGOFuncName as the GUID.
276 // FIXME: Consider updating the edges in the graph after building
277 // it, rather than needing to perform this mapping on each walk.
278 auto GUID = Index.getGUIDFromOriginalID(VI.getGUID());
279 if (GUID == 0)
280 return ValueInfo();
281 return Index.getValueInfo(GUID);
282 }
283
computeImportForReferencedGlobals(const GlobalValueSummary & Summary,const ModuleSummaryIndex & Index,const GVSummaryMapTy & DefinedGVSummaries,SmallVectorImpl<EdgeInfo> & Worklist,FunctionImporter::ImportMapTy & ImportList,StringMap<FunctionImporter::ExportSetTy> * ExportLists)284 static void computeImportForReferencedGlobals(
285 const GlobalValueSummary &Summary, const ModuleSummaryIndex &Index,
286 const GVSummaryMapTy &DefinedGVSummaries,
287 SmallVectorImpl<EdgeInfo> &Worklist,
288 FunctionImporter::ImportMapTy &ImportList,
289 StringMap<FunctionImporter::ExportSetTy> *ExportLists) {
290 for (auto &VI : Summary.refs()) {
291 if (DefinedGVSummaries.count(VI.getGUID())) {
292 LLVM_DEBUG(
293 dbgs() << "Ref ignored! Target already in destination module.\n");
294 continue;
295 }
296
297 LLVM_DEBUG(dbgs() << " ref -> " << VI << "\n");
298
299 // If this is a local variable, make sure we import the copy
300 // in the caller's module. The only time a local variable can
301 // share an entry in the index is if there is a local with the same name
302 // in another module that had the same source file name (in a different
303 // directory), where each was compiled in their own directory so there
304 // was not distinguishing path.
305 auto LocalNotInModule = [&](const GlobalValueSummary *RefSummary) -> bool {
306 return GlobalValue::isLocalLinkage(RefSummary->linkage()) &&
307 RefSummary->modulePath() != Summary.modulePath();
308 };
309
310 for (auto &RefSummary : VI.getSummaryList())
311 if (isa<GlobalVarSummary>(RefSummary.get()) &&
312 Index.canImportGlobalVar(RefSummary.get(), /* AnalyzeRefs */ true) &&
313 !LocalNotInModule(RefSummary.get())) {
314 auto ILI = ImportList[RefSummary->modulePath()].insert(VI.getGUID());
315 // Only update stat and exports if we haven't already imported this
316 // variable.
317 if (!ILI.second)
318 break;
319 NumImportedGlobalVarsThinLink++;
320 // Any references made by this variable will be marked exported later,
321 // in ComputeCrossModuleImport, after import decisions are complete,
322 // which is more efficient than adding them here.
323 if (ExportLists)
324 (*ExportLists)[RefSummary->modulePath()].insert(VI);
325
326 // If variable is not writeonly we attempt to recursively analyze
327 // its references in order to import referenced constants.
328 if (!Index.isWriteOnly(cast<GlobalVarSummary>(RefSummary.get())))
329 Worklist.emplace_back(RefSummary.get(), 0);
330 break;
331 }
332 }
333 }
334
335 static const char *
getFailureName(FunctionImporter::ImportFailureReason Reason)336 getFailureName(FunctionImporter::ImportFailureReason Reason) {
337 switch (Reason) {
338 case FunctionImporter::ImportFailureReason::None:
339 return "None";
340 case FunctionImporter::ImportFailureReason::GlobalVar:
341 return "GlobalVar";
342 case FunctionImporter::ImportFailureReason::NotLive:
343 return "NotLive";
344 case FunctionImporter::ImportFailureReason::TooLarge:
345 return "TooLarge";
346 case FunctionImporter::ImportFailureReason::InterposableLinkage:
347 return "InterposableLinkage";
348 case FunctionImporter::ImportFailureReason::LocalLinkageNotInModule:
349 return "LocalLinkageNotInModule";
350 case FunctionImporter::ImportFailureReason::NotEligible:
351 return "NotEligible";
352 case FunctionImporter::ImportFailureReason::NoInline:
353 return "NoInline";
354 }
355 llvm_unreachable("invalid reason");
356 }
357
358 /// Compute the list of functions to import for a given caller. Mark these
359 /// imported functions and the symbols they reference in their source module as
360 /// 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)361 static void computeImportForFunction(
362 const FunctionSummary &Summary, const ModuleSummaryIndex &Index,
363 const unsigned Threshold, const GVSummaryMapTy &DefinedGVSummaries,
364 SmallVectorImpl<EdgeInfo> &Worklist,
365 FunctionImporter::ImportMapTy &ImportList,
366 StringMap<FunctionImporter::ExportSetTy> *ExportLists,
367 FunctionImporter::ImportThresholdsTy &ImportThresholds) {
368 computeImportForReferencedGlobals(Summary, Index, DefinedGVSummaries,
369 Worklist, ImportList, ExportLists);
370 static int ImportCount = 0;
371 for (auto &Edge : Summary.calls()) {
372 ValueInfo VI = Edge.first;
373 LLVM_DEBUG(dbgs() << " edge -> " << VI << " Threshold:" << Threshold
374 << "\n");
375
376 if (ImportCutoff >= 0 && ImportCount >= ImportCutoff) {
377 LLVM_DEBUG(dbgs() << "ignored! import-cutoff value of " << ImportCutoff
378 << " reached.\n");
379 continue;
380 }
381
382 VI = updateValueInfoForIndirectCalls(Index, VI);
383 if (!VI)
384 continue;
385
386 if (DefinedGVSummaries.count(VI.getGUID())) {
387 LLVM_DEBUG(dbgs() << "ignored! Target already in destination module.\n");
388 continue;
389 }
390
391 auto GetBonusMultiplier = [](CalleeInfo::HotnessType Hotness) -> float {
392 if (Hotness == CalleeInfo::HotnessType::Hot)
393 return ImportHotMultiplier;
394 if (Hotness == CalleeInfo::HotnessType::Cold)
395 return ImportColdMultiplier;
396 if (Hotness == CalleeInfo::HotnessType::Critical)
397 return ImportCriticalMultiplier;
398 return 1.0;
399 };
400
401 const auto NewThreshold =
402 Threshold * GetBonusMultiplier(Edge.second.getHotness());
403
404 auto IT = ImportThresholds.insert(std::make_pair(
405 VI.getGUID(), std::make_tuple(NewThreshold, nullptr, nullptr)));
406 bool PreviouslyVisited = !IT.second;
407 auto &ProcessedThreshold = std::get<0>(IT.first->second);
408 auto &CalleeSummary = std::get<1>(IT.first->second);
409 auto &FailureInfo = std::get<2>(IT.first->second);
410
411 bool IsHotCallsite =
412 Edge.second.getHotness() == CalleeInfo::HotnessType::Hot;
413 bool IsCriticalCallsite =
414 Edge.second.getHotness() == CalleeInfo::HotnessType::Critical;
415
416 const FunctionSummary *ResolvedCalleeSummary = nullptr;
417 if (CalleeSummary) {
418 assert(PreviouslyVisited);
419 // Since the traversal of the call graph is DFS, we can revisit a function
420 // a second time with a higher threshold. In this case, it is added back
421 // to the worklist with the new threshold (so that its own callee chains
422 // can be considered with the higher threshold).
423 if (NewThreshold <= ProcessedThreshold) {
424 LLVM_DEBUG(
425 dbgs() << "ignored! Target was already imported with Threshold "
426 << ProcessedThreshold << "\n");
427 continue;
428 }
429 // Update with new larger threshold.
430 ProcessedThreshold = NewThreshold;
431 ResolvedCalleeSummary = cast<FunctionSummary>(CalleeSummary);
432 } else {
433 // If we already rejected importing a callee at the same or higher
434 // threshold, don't waste time calling selectCallee.
435 if (PreviouslyVisited && NewThreshold <= ProcessedThreshold) {
436 LLVM_DEBUG(
437 dbgs() << "ignored! Target was already rejected with Threshold "
438 << ProcessedThreshold << "\n");
439 if (PrintImportFailures) {
440 assert(FailureInfo &&
441 "Expected FailureInfo for previously rejected candidate");
442 FailureInfo->Attempts++;
443 }
444 continue;
445 }
446
447 FunctionImporter::ImportFailureReason Reason;
448 CalleeSummary = selectCallee(Index, VI.getSummaryList(), NewThreshold,
449 Summary.modulePath(), Reason, VI.getGUID());
450 if (!CalleeSummary) {
451 // Update with new larger threshold if this was a retry (otherwise
452 // we would have already inserted with NewThreshold above). Also
453 // update failure info if requested.
454 if (PreviouslyVisited) {
455 ProcessedThreshold = NewThreshold;
456 if (PrintImportFailures) {
457 assert(FailureInfo &&
458 "Expected FailureInfo for previously rejected candidate");
459 FailureInfo->Reason = Reason;
460 FailureInfo->Attempts++;
461 FailureInfo->MaxHotness =
462 std::max(FailureInfo->MaxHotness, Edge.second.getHotness());
463 }
464 } else if (PrintImportFailures) {
465 assert(!FailureInfo &&
466 "Expected no FailureInfo for newly rejected candidate");
467 FailureInfo = std::make_unique<FunctionImporter::ImportFailureInfo>(
468 VI, Edge.second.getHotness(), Reason, 1);
469 }
470 LLVM_DEBUG(
471 dbgs() << "ignored! No qualifying callee with summary found.\n");
472 continue;
473 }
474
475 // "Resolve" the summary
476 CalleeSummary = CalleeSummary->getBaseObject();
477 ResolvedCalleeSummary = cast<FunctionSummary>(CalleeSummary);
478
479 assert((ResolvedCalleeSummary->fflags().AlwaysInline ||
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
computeDeadSymbols(ModuleSummaryIndex & Index,const DenseSet<GlobalValue::GUID> & GUIDPreservedSymbols,function_ref<PrevailingType (GlobalValue::GUID)> isPrevailing)807 void llvm::computeDeadSymbols(
808 ModuleSummaryIndex &Index,
809 const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols,
810 function_ref<PrevailingType(GlobalValue::GUID)> isPrevailing) {
811 assert(!Index.withGlobalValueDeadStripping());
812 if (!ComputeDead)
813 return;
814 if (GUIDPreservedSymbols.empty())
815 // Don't do anything when nothing is live, this is friendly with tests.
816 return;
817 unsigned LiveSymbols = 0;
818 SmallVector<ValueInfo, 128> Worklist;
819 Worklist.reserve(GUIDPreservedSymbols.size() * 2);
820 for (auto GUID : GUIDPreservedSymbols) {
821 ValueInfo VI = Index.getValueInfo(GUID);
822 if (!VI)
823 continue;
824 for (auto &S : VI.getSummaryList())
825 S->setLive(true);
826 }
827
828 // Add values flagged in the index as live roots to the worklist.
829 for (const auto &Entry : Index) {
830 auto VI = Index.getValueInfo(Entry);
831 for (auto &S : Entry.second.SummaryList)
832 if (S->isLive()) {
833 LLVM_DEBUG(dbgs() << "Live root: " << VI << "\n");
834 Worklist.push_back(VI);
835 ++LiveSymbols;
836 break;
837 }
838 }
839
840 // Make value live and add it to the worklist if it was not live before.
841 auto visit = [&](ValueInfo VI, bool IsAliasee) {
842 // FIXME: If we knew which edges were created for indirect call profiles,
843 // we could skip them here. Any that are live should be reached via
844 // other edges, e.g. reference edges. Otherwise, using a profile collected
845 // on a slightly different binary might provoke preserving, importing
846 // and ultimately promoting calls to functions not linked into this
847 // binary, which increases the binary size unnecessarily. Note that
848 // if this code changes, the importer needs to change so that edges
849 // to functions marked dead are skipped.
850 VI = updateValueInfoForIndirectCalls(Index, VI);
851 if (!VI)
852 return;
853
854 if (llvm::any_of(VI.getSummaryList(),
855 [](const std::unique_ptr<llvm::GlobalValueSummary> &S) {
856 return S->isLive();
857 }))
858 return;
859
860 // We only keep live symbols that are known to be non-prevailing if any are
861 // available_externally, linkonceodr, weakodr. Those symbols are discarded
862 // later in the EliminateAvailableExternally pass and setting them to
863 // not-live could break downstreams users of liveness information (PR36483)
864 // or limit optimization opportunities.
865 if (isPrevailing(VI.getGUID()) == PrevailingType::No) {
866 bool KeepAliveLinkage = false;
867 bool Interposable = false;
868 for (auto &S : VI.getSummaryList()) {
869 if (S->linkage() == GlobalValue::AvailableExternallyLinkage ||
870 S->linkage() == GlobalValue::WeakODRLinkage ||
871 S->linkage() == GlobalValue::LinkOnceODRLinkage)
872 KeepAliveLinkage = true;
873 else if (GlobalValue::isInterposableLinkage(S->linkage()))
874 Interposable = true;
875 }
876
877 if (!IsAliasee) {
878 if (!KeepAliveLinkage)
879 return;
880
881 if (Interposable)
882 report_fatal_error(
883 "Interposable and available_externally/linkonce_odr/weak_odr "
884 "symbol");
885 }
886 }
887
888 for (auto &S : VI.getSummaryList())
889 S->setLive(true);
890 ++LiveSymbols;
891 Worklist.push_back(VI);
892 };
893
894 while (!Worklist.empty()) {
895 auto VI = Worklist.pop_back_val();
896 for (auto &Summary : VI.getSummaryList()) {
897 Summary->setLive(true);
898 if (auto *AS = dyn_cast<AliasSummary>(Summary.get())) {
899 // If this is an alias, visit the aliasee VI to ensure that all copies
900 // are marked live and it is added to the worklist for further
901 // processing of its references.
902 visit(AS->getAliaseeVI(), true);
903 continue;
904 }
905 for (auto Ref : Summary->refs())
906 visit(Ref, false);
907 if (auto *FS = dyn_cast<FunctionSummary>(Summary.get()))
908 for (auto Call : FS->calls())
909 visit(Call.first, false);
910 }
911 }
912 Index.setWithGlobalValueDeadStripping();
913
914 unsigned DeadSymbols = Index.size() - LiveSymbols;
915 LLVM_DEBUG(dbgs() << LiveSymbols << " symbols Live, and " << DeadSymbols
916 << " symbols Dead \n");
917 NumDeadSymbols += DeadSymbols;
918 NumLiveSymbols += LiveSymbols;
919 }
920
921 // 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)922 void llvm::computeDeadSymbolsWithConstProp(
923 ModuleSummaryIndex &Index,
924 const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols,
925 function_ref<PrevailingType(GlobalValue::GUID)> isPrevailing,
926 bool ImportEnabled) {
927 computeDeadSymbols(Index, GUIDPreservedSymbols, isPrevailing);
928 if (ImportEnabled)
929 Index.propagateAttributes(GUIDPreservedSymbols);
930 }
931
932 /// Compute the set of summaries needed for a ThinLTO backend compilation of
933 /// \p ModulePath.
gatherImportedSummariesForModule(StringRef ModulePath,const StringMap<GVSummaryMapTy> & ModuleToDefinedGVSummaries,const FunctionImporter::ImportMapTy & ImportList,std::map<std::string,GVSummaryMapTy> & ModuleToSummariesForIndex)934 void llvm::gatherImportedSummariesForModule(
935 StringRef ModulePath,
936 const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
937 const FunctionImporter::ImportMapTy &ImportList,
938 std::map<std::string, GVSummaryMapTy> &ModuleToSummariesForIndex) {
939 // Include all summaries from the importing module.
940 ModuleToSummariesForIndex[std::string(ModulePath)] =
941 ModuleToDefinedGVSummaries.lookup(ModulePath);
942 // Include summaries for imports.
943 for (auto &ILI : ImportList) {
944 auto &SummariesForIndex =
945 ModuleToSummariesForIndex[std::string(ILI.first())];
946 const auto &DefinedGVSummaries =
947 ModuleToDefinedGVSummaries.lookup(ILI.first());
948 for (auto &GI : ILI.second) {
949 const auto &DS = DefinedGVSummaries.find(GI);
950 assert(DS != DefinedGVSummaries.end() &&
951 "Expected a defined summary for imported global value");
952 SummariesForIndex[GI] = DS->second;
953 }
954 }
955 }
956
957 /// Emit the files \p ModulePath will import from into \p OutputFilename.
EmitImportsFiles(StringRef ModulePath,StringRef OutputFilename,const std::map<std::string,GVSummaryMapTy> & ModuleToSummariesForIndex)958 std::error_code llvm::EmitImportsFiles(
959 StringRef ModulePath, StringRef OutputFilename,
960 const std::map<std::string, GVSummaryMapTy> &ModuleToSummariesForIndex) {
961 std::error_code EC;
962 raw_fd_ostream ImportsOS(OutputFilename, EC, sys::fs::OpenFlags::OF_None);
963 if (EC)
964 return EC;
965 for (auto &ILI : ModuleToSummariesForIndex)
966 // The ModuleToSummariesForIndex map includes an entry for the current
967 // Module (needed for writing out the index files). We don't want to
968 // include it in the imports file, however, so filter it out.
969 if (ILI.first != ModulePath)
970 ImportsOS << ILI.first << "\n";
971 return std::error_code();
972 }
973
convertToDeclaration(GlobalValue & GV)974 bool llvm::convertToDeclaration(GlobalValue &GV) {
975 LLVM_DEBUG(dbgs() << "Converting to a declaration: `" << GV.getName()
976 << "\n");
977 if (Function *F = dyn_cast<Function>(&GV)) {
978 F->deleteBody();
979 F->clearMetadata();
980 F->setComdat(nullptr);
981 } else if (GlobalVariable *V = dyn_cast<GlobalVariable>(&GV)) {
982 V->setInitializer(nullptr);
983 V->setLinkage(GlobalValue::ExternalLinkage);
984 V->clearMetadata();
985 V->setComdat(nullptr);
986 } else {
987 GlobalValue *NewGV;
988 if (GV.getValueType()->isFunctionTy())
989 NewGV =
990 Function::Create(cast<FunctionType>(GV.getValueType()),
991 GlobalValue::ExternalLinkage, GV.getAddressSpace(),
992 "", GV.getParent());
993 else
994 NewGV =
995 new GlobalVariable(*GV.getParent(), GV.getValueType(),
996 /*isConstant*/ false, GlobalValue::ExternalLinkage,
997 /*init*/ nullptr, "",
998 /*insertbefore*/ nullptr, GV.getThreadLocalMode(),
999 GV.getType()->getAddressSpace());
1000 NewGV->takeName(&GV);
1001 GV.replaceAllUsesWith(NewGV);
1002 return false;
1003 }
1004 if (!GV.isImplicitDSOLocal())
1005 GV.setDSOLocal(false);
1006 return true;
1007 }
1008
1009 /// Fixup prevailing symbol linkages in \p TheModule based on summary analysis.
thinLTOResolvePrevailingInModule(Module & TheModule,const GVSummaryMapTy & DefinedGlobals)1010 void llvm::thinLTOResolvePrevailingInModule(
1011 Module &TheModule, const GVSummaryMapTy &DefinedGlobals) {
1012 auto updateLinkage = [&](GlobalValue &GV) {
1013 // See if the global summary analysis computed a new resolved linkage.
1014 const auto &GS = DefinedGlobals.find(GV.getGUID());
1015 if (GS == DefinedGlobals.end())
1016 return;
1017 auto NewLinkage = GS->second->linkage();
1018 if (NewLinkage == GV.getLinkage())
1019 return;
1020 if (GlobalValue::isLocalLinkage(GV.getLinkage()) ||
1021 // Don't internalize anything here, because the code below
1022 // lacks necessary correctness checks. Leave this job to
1023 // LLVM 'internalize' pass.
1024 GlobalValue::isLocalLinkage(NewLinkage) ||
1025 // In case it was dead and already converted to declaration.
1026 GV.isDeclaration())
1027 return;
1028
1029 // Check for a non-prevailing def that has interposable linkage
1030 // (e.g. non-odr weak or linkonce). In that case we can't simply
1031 // convert to available_externally, since it would lose the
1032 // interposable property and possibly get inlined. Simply drop
1033 // the definition in that case.
1034 if (GlobalValue::isAvailableExternallyLinkage(NewLinkage) &&
1035 GlobalValue::isInterposableLinkage(GV.getLinkage())) {
1036 if (!convertToDeclaration(GV))
1037 // FIXME: Change this to collect replaced GVs and later erase
1038 // them from the parent module once thinLTOResolvePrevailingGUID is
1039 // changed to enable this for aliases.
1040 llvm_unreachable("Expected GV to be converted");
1041 } else {
1042 // If all copies of the original symbol had global unnamed addr and
1043 // linkonce_odr linkage, it should be an auto hide symbol. In that case
1044 // the thin link would have marked it as CanAutoHide. Add hidden visibility
1045 // to the symbol to preserve the property.
1046 if (NewLinkage == GlobalValue::WeakODRLinkage &&
1047 GS->second->canAutoHide()) {
1048 assert(GV.hasLinkOnceODRLinkage() && GV.hasGlobalUnnamedAddr());
1049 GV.setVisibility(GlobalValue::HiddenVisibility);
1050 }
1051
1052 LLVM_DEBUG(dbgs() << "ODR fixing up linkage for `" << GV.getName()
1053 << "` from " << GV.getLinkage() << " to " << NewLinkage
1054 << "\n");
1055 GV.setLinkage(NewLinkage);
1056 }
1057 // Remove declarations from comdats, including available_externally
1058 // as this is a declaration for the linker, and will be dropped eventually.
1059 // It is illegal for comdats to contain declarations.
1060 auto *GO = dyn_cast_or_null<GlobalObject>(&GV);
1061 if (GO && GO->isDeclarationForLinker() && GO->hasComdat())
1062 GO->setComdat(nullptr);
1063 };
1064
1065 // Process functions and global now
1066 for (auto &GV : TheModule)
1067 updateLinkage(GV);
1068 for (auto &GV : TheModule.globals())
1069 updateLinkage(GV);
1070 for (auto &GV : TheModule.aliases())
1071 updateLinkage(GV);
1072 }
1073
1074 /// Run internalization on \p TheModule based on symmary analysis.
thinLTOInternalizeModule(Module & TheModule,const GVSummaryMapTy & DefinedGlobals)1075 void llvm::thinLTOInternalizeModule(Module &TheModule,
1076 const GVSummaryMapTy &DefinedGlobals) {
1077 // Declare a callback for the internalize pass that will ask for every
1078 // candidate GlobalValue if it can be internalized or not.
1079 auto MustPreserveGV = [&](const GlobalValue &GV) -> bool {
1080 // Lookup the linkage recorded in the summaries during global analysis.
1081 auto GS = DefinedGlobals.find(GV.getGUID());
1082 if (GS == DefinedGlobals.end()) {
1083 // Must have been promoted (possibly conservatively). Find original
1084 // name so that we can access the correct summary and see if it can
1085 // be internalized again.
1086 // FIXME: Eventually we should control promotion instead of promoting
1087 // and internalizing again.
1088 StringRef OrigName =
1089 ModuleSummaryIndex::getOriginalNameBeforePromote(GV.getName());
1090 std::string OrigId = GlobalValue::getGlobalIdentifier(
1091 OrigName, GlobalValue::InternalLinkage,
1092 TheModule.getSourceFileName());
1093 GS = DefinedGlobals.find(GlobalValue::getGUID(OrigId));
1094 if (GS == DefinedGlobals.end()) {
1095 // Also check the original non-promoted non-globalized name. In some
1096 // cases a preempted weak value is linked in as a local copy because
1097 // it is referenced by an alias (IRLinker::linkGlobalValueProto).
1098 // In that case, since it was originally not a local value, it was
1099 // recorded in the index using the original name.
1100 // FIXME: This may not be needed once PR27866 is fixed.
1101 GS = DefinedGlobals.find(GlobalValue::getGUID(OrigName));
1102 assert(GS != DefinedGlobals.end());
1103 }
1104 }
1105 return !GlobalValue::isLocalLinkage(GS->second->linkage());
1106 };
1107
1108 // FIXME: See if we can just internalize directly here via linkage changes
1109 // based on the index, rather than invoking internalizeModule.
1110 internalizeModule(TheModule, MustPreserveGV);
1111 }
1112
1113 /// Make alias a clone of its aliasee.
replaceAliasWithAliasee(Module * SrcModule,GlobalAlias * GA)1114 static Function *replaceAliasWithAliasee(Module *SrcModule, GlobalAlias *GA) {
1115 Function *Fn = cast<Function>(GA->getBaseObject());
1116
1117 ValueToValueMapTy VMap;
1118 Function *NewFn = CloneFunction(Fn, VMap);
1119 // Clone should use the original alias's linkage, visibility and name, and we
1120 // ensure all uses of alias instead use the new clone (casted if necessary).
1121 NewFn->setLinkage(GA->getLinkage());
1122 NewFn->setVisibility(GA->getVisibility());
1123 GA->replaceAllUsesWith(ConstantExpr::getBitCast(NewFn, GA->getType()));
1124 NewFn->takeName(GA);
1125 return NewFn;
1126 }
1127
1128 // Internalize values that we marked with specific attribute
1129 // in processGlobalForThinLTO.
internalizeGVsAfterImport(Module & M)1130 static void internalizeGVsAfterImport(Module &M) {
1131 for (auto &GV : M.globals())
1132 // Skip GVs which have been converted to declarations
1133 // by dropDeadSymbols.
1134 if (!GV.isDeclaration() && GV.hasAttribute("thinlto-internalize")) {
1135 GV.setLinkage(GlobalValue::InternalLinkage);
1136 GV.setVisibility(GlobalValue::DefaultVisibility);
1137 }
1138 }
1139
1140 // Automatically import functions in Module \p DestModule based on the summaries
1141 // index.
importFunctions(Module & DestModule,const FunctionImporter::ImportMapTy & ImportList)1142 Expected<bool> FunctionImporter::importFunctions(
1143 Module &DestModule, const FunctionImporter::ImportMapTy &ImportList) {
1144 LLVM_DEBUG(dbgs() << "Starting import for Module "
1145 << DestModule.getModuleIdentifier() << "\n");
1146 unsigned ImportedCount = 0, ImportedGVCount = 0;
1147
1148 IRMover Mover(DestModule);
1149 // Do the actual import of functions now, one Module at a time
1150 std::set<StringRef> ModuleNameOrderedList;
1151 for (auto &FunctionsToImportPerModule : ImportList) {
1152 ModuleNameOrderedList.insert(FunctionsToImportPerModule.first());
1153 }
1154 for (auto &Name : ModuleNameOrderedList) {
1155 // Get the module for the import
1156 const auto &FunctionsToImportPerModule = ImportList.find(Name);
1157 assert(FunctionsToImportPerModule != ImportList.end());
1158 Expected<std::unique_ptr<Module>> SrcModuleOrErr = ModuleLoader(Name);
1159 if (!SrcModuleOrErr)
1160 return SrcModuleOrErr.takeError();
1161 std::unique_ptr<Module> SrcModule = std::move(*SrcModuleOrErr);
1162 assert(&DestModule.getContext() == &SrcModule->getContext() &&
1163 "Context mismatch");
1164
1165 // If modules were created with lazy metadata loading, materialize it
1166 // now, before linking it (otherwise this will be a noop).
1167 if (Error Err = SrcModule->materializeMetadata())
1168 return std::move(Err);
1169
1170 auto &ImportGUIDs = FunctionsToImportPerModule->second;
1171 // Find the globals to import
1172 SetVector<GlobalValue *> GlobalsToImport;
1173 for (Function &F : *SrcModule) {
1174 if (!F.hasName())
1175 continue;
1176 auto GUID = F.getGUID();
1177 auto Import = ImportGUIDs.count(GUID);
1178 LLVM_DEBUG(dbgs() << (Import ? "Is" : "Not") << " importing function "
1179 << GUID << " " << F.getName() << " from "
1180 << SrcModule->getSourceFileName() << "\n");
1181 if (Import) {
1182 if (Error Err = F.materialize())
1183 return std::move(Err);
1184 if (EnableImportMetadata) {
1185 // Add 'thinlto_src_module' metadata for statistics and debugging.
1186 F.setMetadata(
1187 "thinlto_src_module",
1188 MDNode::get(DestModule.getContext(),
1189 {MDString::get(DestModule.getContext(),
1190 SrcModule->getSourceFileName())}));
1191 }
1192 GlobalsToImport.insert(&F);
1193 }
1194 }
1195 for (GlobalVariable &GV : SrcModule->globals()) {
1196 if (!GV.hasName())
1197 continue;
1198 auto GUID = GV.getGUID();
1199 auto Import = ImportGUIDs.count(GUID);
1200 LLVM_DEBUG(dbgs() << (Import ? "Is" : "Not") << " importing global "
1201 << GUID << " " << GV.getName() << " from "
1202 << SrcModule->getSourceFileName() << "\n");
1203 if (Import) {
1204 if (Error Err = GV.materialize())
1205 return std::move(Err);
1206 ImportedGVCount += GlobalsToImport.insert(&GV);
1207 }
1208 }
1209 for (GlobalAlias &GA : SrcModule->aliases()) {
1210 if (!GA.hasName())
1211 continue;
1212 auto GUID = GA.getGUID();
1213 auto Import = ImportGUIDs.count(GUID);
1214 LLVM_DEBUG(dbgs() << (Import ? "Is" : "Not") << " importing alias "
1215 << GUID << " " << GA.getName() << " from "
1216 << SrcModule->getSourceFileName() << "\n");
1217 if (Import) {
1218 if (Error Err = GA.materialize())
1219 return std::move(Err);
1220 // Import alias as a copy of its aliasee.
1221 GlobalObject *Base = GA.getBaseObject();
1222 if (Error Err = Base->materialize())
1223 return std::move(Err);
1224 auto *Fn = replaceAliasWithAliasee(SrcModule.get(), &GA);
1225 LLVM_DEBUG(dbgs() << "Is importing aliasee fn " << Base->getGUID()
1226 << " " << Base->getName() << " from "
1227 << SrcModule->getSourceFileName() << "\n");
1228 if (EnableImportMetadata) {
1229 // Add 'thinlto_src_module' metadata for statistics and debugging.
1230 Fn->setMetadata(
1231 "thinlto_src_module",
1232 MDNode::get(DestModule.getContext(),
1233 {MDString::get(DestModule.getContext(),
1234 SrcModule->getSourceFileName())}));
1235 }
1236 GlobalsToImport.insert(Fn);
1237 }
1238 }
1239
1240 // Upgrade debug info after we're done materializing all the globals and we
1241 // have loaded all the required metadata!
1242 UpgradeDebugInfo(*SrcModule);
1243
1244 // Set the partial sample profile ratio in the profile summary module flag
1245 // of the imported source module, if applicable, so that the profile summary
1246 // module flag will match with that of the destination module when it's
1247 // imported.
1248 SrcModule->setPartialSampleProfileRatio(Index);
1249
1250 // Link in the specified functions.
1251 if (renameModuleForThinLTO(*SrcModule, Index, ClearDSOLocalOnDeclarations,
1252 &GlobalsToImport))
1253 return true;
1254
1255 if (PrintImports) {
1256 for (const auto *GV : GlobalsToImport)
1257 dbgs() << DestModule.getSourceFileName() << ": Import " << GV->getName()
1258 << " from " << SrcModule->getSourceFileName() << "\n";
1259 }
1260
1261 if (Error Err = Mover.move(
1262 std::move(SrcModule), GlobalsToImport.getArrayRef(),
1263 [](GlobalValue &, IRMover::ValueAdder) {},
1264 /*IsPerformingImport=*/true))
1265 report_fatal_error("Function Import: link error: " +
1266 toString(std::move(Err)));
1267
1268 ImportedCount += GlobalsToImport.size();
1269 NumImportedModules++;
1270 }
1271
1272 internalizeGVsAfterImport(DestModule);
1273
1274 NumImportedFunctions += (ImportedCount - ImportedGVCount);
1275 NumImportedGlobalVars += ImportedGVCount;
1276
1277 LLVM_DEBUG(dbgs() << "Imported " << ImportedCount - ImportedGVCount
1278 << " functions for Module "
1279 << DestModule.getModuleIdentifier() << "\n");
1280 LLVM_DEBUG(dbgs() << "Imported " << ImportedGVCount
1281 << " global variables for Module "
1282 << DestModule.getModuleIdentifier() << "\n");
1283 return ImportedCount;
1284 }
1285
doImportingForModule(Module & M)1286 static bool doImportingForModule(Module &M) {
1287 if (SummaryFile.empty())
1288 report_fatal_error("error: -function-import requires -summary-file\n");
1289 Expected<std::unique_ptr<ModuleSummaryIndex>> IndexPtrOrErr =
1290 getModuleSummaryIndexForFile(SummaryFile);
1291 if (!IndexPtrOrErr) {
1292 logAllUnhandledErrors(IndexPtrOrErr.takeError(), errs(),
1293 "Error loading file '" + SummaryFile + "': ");
1294 return false;
1295 }
1296 std::unique_ptr<ModuleSummaryIndex> Index = std::move(*IndexPtrOrErr);
1297
1298 // First step is collecting the import list.
1299 FunctionImporter::ImportMapTy ImportList;
1300 // If requested, simply import all functions in the index. This is used
1301 // when testing distributed backend handling via the opt tool, when
1302 // we have distributed indexes containing exactly the summaries to import.
1303 if (ImportAllIndex)
1304 ComputeCrossModuleImportForModuleFromIndex(M.getModuleIdentifier(), *Index,
1305 ImportList);
1306 else
1307 ComputeCrossModuleImportForModule(M.getModuleIdentifier(), *Index,
1308 ImportList);
1309
1310 // Conservatively mark all internal values as promoted. This interface is
1311 // only used when doing importing via the function importing pass. The pass
1312 // is only enabled when testing importing via the 'opt' tool, which does
1313 // not do the ThinLink that would normally determine what values to promote.
1314 for (auto &I : *Index) {
1315 for (auto &S : I.second.SummaryList) {
1316 if (GlobalValue::isLocalLinkage(S->linkage()))
1317 S->setLinkage(GlobalValue::ExternalLinkage);
1318 }
1319 }
1320
1321 // Next we need to promote to global scope and rename any local values that
1322 // are potentially exported to other modules.
1323 if (renameModuleForThinLTO(M, *Index, /*ClearDSOLocalOnDeclarations=*/false,
1324 /*GlobalsToImport=*/nullptr)) {
1325 errs() << "Error renaming module\n";
1326 return false;
1327 }
1328
1329 // Perform the import now.
1330 auto ModuleLoader = [&M](StringRef Identifier) {
1331 return loadFile(std::string(Identifier), M.getContext());
1332 };
1333 FunctionImporter Importer(*Index, ModuleLoader,
1334 /*ClearDSOLocalOnDeclarations=*/false);
1335 Expected<bool> Result = Importer.importFunctions(M, ImportList);
1336
1337 // FIXME: Probably need to propagate Errors through the pass manager.
1338 if (!Result) {
1339 logAllUnhandledErrors(Result.takeError(), errs(),
1340 "Error importing module: ");
1341 return false;
1342 }
1343
1344 return *Result;
1345 }
1346
1347 namespace {
1348
1349 /// Pass that performs cross-module function import provided a summary file.
1350 class FunctionImportLegacyPass : public ModulePass {
1351 public:
1352 /// Pass identification, replacement for typeid
1353 static char ID;
1354
FunctionImportLegacyPass()1355 explicit FunctionImportLegacyPass() : ModulePass(ID) {}
1356
1357 /// Specify pass name for debug output
getPassName() const1358 StringRef getPassName() const override { return "Function Importing"; }
1359
runOnModule(Module & M)1360 bool runOnModule(Module &M) override {
1361 if (skipModule(M))
1362 return false;
1363
1364 return doImportingForModule(M);
1365 }
1366 };
1367
1368 } // end anonymous namespace
1369
run(Module & M,ModuleAnalysisManager & AM)1370 PreservedAnalyses FunctionImportPass::run(Module &M,
1371 ModuleAnalysisManager &AM) {
1372 if (!doImportingForModule(M))
1373 return PreservedAnalyses::all();
1374
1375 return PreservedAnalyses::none();
1376 }
1377
1378 char FunctionImportLegacyPass::ID = 0;
1379 INITIALIZE_PASS(FunctionImportLegacyPass, "function-import",
1380 "Summary Based Function Import", false, false)
1381
1382 namespace llvm {
1383
createFunctionImportPass()1384 Pass *createFunctionImportPass() {
1385 return new FunctionImportLegacyPass();
1386 }
1387
1388 } // end namespace llvm
1389