LLVM  8.0.0svn
FunctionImport.cpp
Go to the documentation of this file.
1 //===- FunctionImport.cpp - ThinLTO Summary-based Function Import ---------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements Function import based on summaries.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 #include "llvm/ADT/ArrayRef.h"
16 #include "llvm/ADT/STLExtras.h"
17 #include "llvm/ADT/SetVector.h"
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/ADT/Statistic.h"
20 #include "llvm/ADT/StringMap.h"
21 #include "llvm/ADT/StringRef.h"
22 #include "llvm/ADT/StringSet.h"
24 #include "llvm/IR/AutoUpgrade.h"
25 #include "llvm/IR/Constants.h"
26 #include "llvm/IR/Function.h"
27 #include "llvm/IR/GlobalAlias.h"
28 #include "llvm/IR/GlobalObject.h"
29 #include "llvm/IR/GlobalValue.h"
30 #include "llvm/IR/GlobalVariable.h"
31 #include "llvm/IR/Metadata.h"
32 #include "llvm/IR/Module.h"
34 #include "llvm/IRReader/IRReader.h"
35 #include "llvm/Linker/IRMover.h"
38 #include "llvm/Pass.h"
39 #include "llvm/Support/Casting.h"
41 #include "llvm/Support/Debug.h"
42 #include "llvm/Support/Error.h"
45 #include "llvm/Support/SourceMgr.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.
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 
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),
90  cl::desc("As we import functions, multiply the "
91  "`import-instr-limit` threshold by this factor "
92  "before processing newly imported functions"));
93 
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 
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 
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.
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 
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 
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.
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.
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 *
178  ArrayRef<std::unique_ptr<GlobalValueSummary>> CalleeSummaryList,
179  unsigned Threshold, StringRef CallerModulePath,
181  GlobalValue::GUID GUID) {
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) {
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  Reason = FunctionImporter::ImportFailureReason::TooLarge;
237  return false;
238  }
239 
240  // Skip if it isn't legal to import (e.g. may reference unpromotable
241  // locals).
242  if (Summary->notEligibleToImport()) {
243  Reason = FunctionImporter::ImportFailureReason::NotEligible;
244  return false;
245  }
246 
247  // Don't bother importing if we can't inline it anyway.
248  if (Summary->fflags().NoInline) {
249  Reason = FunctionImporter::ImportFailureReason::NoInline;
250  return false;
251  }
252 
253  return true;
254  });
255  if (It == CalleeSummaryList.end())
256  return nullptr;
257 
258  return cast<GlobalValueSummary>(It->get());
259 }
260 
261 namespace {
262 
263 using EdgeInfo = std::tuple<const FunctionSummary *, unsigned /* Threshold */,
265 
266 } // anonymous namespace
267 
268 static ValueInfo
270  if (!VI.getSummaryList().empty())
271  return VI;
272  // For SamplePGO, the indirect call targets for local functions will
273  // have its original name annotated in profile. We try to find the
274  // corresponding PGOFuncName as the GUID.
275  // FIXME: Consider updating the edges in the graph after building
276  // it, rather than needing to perform this mapping on each walk.
277  auto GUID = Index.getGUIDFromOriginalID(VI.getGUID());
278  if (GUID == 0)
279  return ValueInfo();
280  return Index.getValueInfo(GUID);
281 }
282 
284  const FunctionSummary &Summary, const GVSummaryMapTy &DefinedGVSummaries,
285  FunctionImporter::ImportMapTy &ImportList,
287  for (auto &VI : Summary.refs()) {
288  if (DefinedGVSummaries.count(VI.getGUID())) {
289  LLVM_DEBUG(
290  dbgs() << "Ref ignored! Target already in destination module.\n");
291  continue;
292  }
293 
294  LLVM_DEBUG(dbgs() << " ref -> " << VI << "\n");
295 
296  // If this is a local variable, make sure we import the copy
297  // in the caller's module. The only time a local variable can
298  // share an entry in the index is if there is a local with the same name
299  // in another module that had the same source file name (in a different
300  // directory), where each was compiled in their own directory so there
301  // was not distinguishing path.
302  auto LocalNotInModule = [&](const GlobalValueSummary *RefSummary) -> bool {
303  return GlobalValue::isLocalLinkage(RefSummary->linkage()) &&
304  RefSummary->modulePath() != Summary.modulePath();
305  };
306 
307  for (auto &RefSummary : VI.getSummaryList())
308  if (isa<GlobalVarSummary>(RefSummary.get()) &&
309  canImportGlobalVar(RefSummary.get()) &&
310  !LocalNotInModule(RefSummary.get())) {
311  auto ILI = ImportList[RefSummary->modulePath()].insert(VI.getGUID());
312  // Only update stat if we haven't already imported this variable.
313  if (ILI.second)
314  NumImportedGlobalVarsThinLink++;
315  if (ExportLists)
316  (*ExportLists)[RefSummary->modulePath()].insert(VI.getGUID());
317  break;
318  }
319  }
320 }
321 
322 static const char *
324  switch (Reason) {
326  return "None";
328  return "GlobalVar";
329  case FunctionImporter::ImportFailureReason::NotLive:
330  return "NotLive";
331  case FunctionImporter::ImportFailureReason::TooLarge:
332  return "TooLarge";
333  case FunctionImporter::ImportFailureReason::InterposableLinkage:
334  return "InterposableLinkage";
335  case FunctionImporter::ImportFailureReason::LocalLinkageNotInModule:
336  return "LocalLinkageNotInModule";
337  case FunctionImporter::ImportFailureReason::NotEligible:
338  return "NotEligible";
339  case FunctionImporter::ImportFailureReason::NoInline:
340  return "NoInline";
341  }
342  llvm_unreachable("invalid reason");
343 }
344 
345 /// Compute the list of functions to import for a given caller. Mark these
346 /// imported functions and the symbols they reference in their source module as
347 /// exported from their source module.
349  const FunctionSummary &Summary, const ModuleSummaryIndex &Index,
350  const unsigned Threshold, const GVSummaryMapTy &DefinedGVSummaries,
351  SmallVectorImpl<EdgeInfo> &Worklist,
352  FunctionImporter::ImportMapTy &ImportList,
354  FunctionImporter::ImportThresholdsTy &ImportThresholds) {
355  computeImportForReferencedGlobals(Summary, DefinedGVSummaries, ImportList,
356  ExportLists);
357  static int ImportCount = 0;
358  for (auto &Edge : Summary.calls()) {
359  ValueInfo VI = Edge.first;
360  LLVM_DEBUG(dbgs() << " edge -> " << VI << " Threshold:" << Threshold
361  << "\n");
362 
363  if (ImportCutoff >= 0 && ImportCount >= ImportCutoff) {
364  LLVM_DEBUG(dbgs() << "ignored! import-cutoff value of " << ImportCutoff
365  << " reached.\n");
366  continue;
367  }
368 
369  VI = updateValueInfoForIndirectCalls(Index, VI);
370  if (!VI)
371  continue;
372 
373  if (DefinedGVSummaries.count(VI.getGUID())) {
374  LLVM_DEBUG(dbgs() << "ignored! Target already in destination module.\n");
375  continue;
376  }
377 
378  auto GetBonusMultiplier = [](CalleeInfo::HotnessType Hotness) -> float {
379  if (Hotness == CalleeInfo::HotnessType::Hot)
380  return ImportHotMultiplier;
381  if (Hotness == CalleeInfo::HotnessType::Cold)
382  return ImportColdMultiplier;
383  if (Hotness == CalleeInfo::HotnessType::Critical)
385  return 1.0;
386  };
387 
388  const auto NewThreshold =
389  Threshold * GetBonusMultiplier(Edge.second.getHotness());
390 
391  auto IT = ImportThresholds.insert(std::make_pair(
392  VI.getGUID(), std::make_tuple(NewThreshold, nullptr, nullptr)));
393  bool PreviouslyVisited = !IT.second;
394  auto &ProcessedThreshold = std::get<0>(IT.first->second);
395  auto &CalleeSummary = std::get<1>(IT.first->second);
396  auto &FailureInfo = std::get<2>(IT.first->second);
397 
398  bool IsHotCallsite =
399  Edge.second.getHotness() == CalleeInfo::HotnessType::Hot;
400  bool IsCriticalCallsite =
401  Edge.second.getHotness() == CalleeInfo::HotnessType::Critical;
402 
403  const FunctionSummary *ResolvedCalleeSummary = nullptr;
404  if (CalleeSummary) {
405  assert(PreviouslyVisited);
406  // Since the traversal of the call graph is DFS, we can revisit a function
407  // a second time with a higher threshold. In this case, it is added back
408  // to the worklist with the new threshold (so that its own callee chains
409  // can be considered with the higher threshold).
410  if (NewThreshold <= ProcessedThreshold) {
411  LLVM_DEBUG(
412  dbgs() << "ignored! Target was already imported with Threshold "
413  << ProcessedThreshold << "\n");
414  continue;
415  }
416  // Update with new larger threshold.
417  ProcessedThreshold = NewThreshold;
418  ResolvedCalleeSummary = cast<FunctionSummary>(CalleeSummary);
419  } else {
420  // If we already rejected importing a callee at the same or higher
421  // threshold, don't waste time calling selectCallee.
422  if (PreviouslyVisited && NewThreshold <= ProcessedThreshold) {
423  LLVM_DEBUG(
424  dbgs() << "ignored! Target was already rejected with Threshold "
425  << ProcessedThreshold << "\n");
426  if (PrintImportFailures) {
427  assert(FailureInfo &&
428  "Expected FailureInfo for previously rejected candidate");
429  FailureInfo->Attempts++;
430  }
431  continue;
432  }
433 
435  CalleeSummary = selectCallee(Index, VI.getSummaryList(), NewThreshold,
436  Summary.modulePath(), Reason, VI.getGUID());
437  if (!CalleeSummary) {
438  // Update with new larger threshold if this was a retry (otherwise
439  // we would have already inserted with NewThreshold above). Also
440  // update failure info if requested.
441  if (PreviouslyVisited) {
442  ProcessedThreshold = NewThreshold;
443  if (PrintImportFailures) {
444  assert(FailureInfo &&
445  "Expected FailureInfo for previously rejected candidate");
446  FailureInfo->Reason = Reason;
447  FailureInfo->Attempts++;
448  FailureInfo->MaxHotness =
449  std::max(FailureInfo->MaxHotness, Edge.second.getHotness());
450  }
451  } else if (PrintImportFailures) {
452  assert(!FailureInfo &&
453  "Expected no FailureInfo for newly rejected candidate");
454  FailureInfo = llvm::make_unique<FunctionImporter::ImportFailureInfo>(
455  VI, Edge.second.getHotness(), Reason, 1);
456  }
457  LLVM_DEBUG(
458  dbgs() << "ignored! No qualifying callee with summary found.\n");
459  continue;
460  }
461 
462  // "Resolve" the summary
463  CalleeSummary = CalleeSummary->getBaseObject();
464  ResolvedCalleeSummary = cast<FunctionSummary>(CalleeSummary);
465 
466  assert(ResolvedCalleeSummary->instCount() <= NewThreshold &&
467  "selectCallee() didn't honor the threshold");
468 
469  auto ExportModulePath = ResolvedCalleeSummary->modulePath();
470  auto ILI = ImportList[ExportModulePath].insert(VI.getGUID());
471  // We previously decided to import this GUID definition if it was already
472  // inserted in the set of imports from the exporting module.
473  bool PreviouslyImported = !ILI.second;
474  if (!PreviouslyImported) {
475  NumImportedFunctionsThinLink++;
476  if (IsHotCallsite)
477  NumImportedHotFunctionsThinLink++;
478  if (IsCriticalCallsite)
479  NumImportedCriticalFunctionsThinLink++;
480  }
481 
482  // Make exports in the source module.
483  if (ExportLists) {
484  auto &ExportList = (*ExportLists)[ExportModulePath];
485  ExportList.insert(VI.getGUID());
486  if (!PreviouslyImported) {
487  // This is the first time this function was exported from its source
488  // module, so mark all functions and globals it references as exported
489  // to the outside if they are defined in the same source module.
490  // For efficiency, we unconditionally add all the referenced GUIDs
491  // to the ExportList for this module, and will prune out any not
492  // defined in the module later in a single pass.
493  for (auto &Edge : ResolvedCalleeSummary->calls()) {
494  auto CalleeGUID = Edge.first.getGUID();
495  ExportList.insert(CalleeGUID);
496  }
497  for (auto &Ref : ResolvedCalleeSummary->refs()) {
498  auto GUID = Ref.getGUID();
499  ExportList.insert(GUID);
500  }
501  }
502  }
503  }
504 
505  auto GetAdjustedThreshold = [](unsigned Threshold, bool IsHotCallsite) {
506  // Adjust the threshold for next level of imported functions.
507  // The threshold is different for hot callsites because we can then
508  // inline chains of hot calls.
509  if (IsHotCallsite)
510  return Threshold * ImportHotInstrFactor;
511  return Threshold * ImportInstrFactor;
512  };
513 
514  const auto AdjThreshold = GetAdjustedThreshold(Threshold, IsHotCallsite);
515 
516  ImportCount++;
517 
518  // Insert the newly imported function to the worklist.
519  Worklist.emplace_back(ResolvedCalleeSummary, AdjThreshold, VI.getGUID());
520  }
521 }
522 
523 /// Given the list of globals defined in a module, compute the list of imports
524 /// as well as the list of "exports", i.e. the list of symbols referenced from
525 /// another module (that may require promotion).
527  const GVSummaryMapTy &DefinedGVSummaries, const ModuleSummaryIndex &Index,
528  StringRef ModName, FunctionImporter::ImportMapTy &ImportList,
529  StringMap<FunctionImporter::ExportSetTy> *ExportLists = nullptr) {
530  // Worklist contains the list of function imported in this module, for which
531  // we will analyse the callees and may import further down the callgraph.
533  FunctionImporter::ImportThresholdsTy ImportThresholds;
534 
535  // Populate the worklist with the import for the functions in the current
536  // module
537  for (auto &GVSummary : DefinedGVSummaries) {
538 #ifndef NDEBUG
539  // FIXME: Change the GVSummaryMapTy to hold ValueInfo instead of GUID
540  // so this map look up (and possibly others) can be avoided.
541  auto VI = Index.getValueInfo(GVSummary.first);
542 #endif
543  if (!Index.isGlobalValueLive(GVSummary.second)) {
544  LLVM_DEBUG(dbgs() << "Ignores Dead GUID: " << VI << "\n");
545  continue;
546  }
547  auto *FuncSummary =
548  dyn_cast<FunctionSummary>(GVSummary.second->getBaseObject());
549  if (!FuncSummary)
550  // Skip import for global variables
551  continue;
552  LLVM_DEBUG(dbgs() << "Initialize import for " << VI << "\n");
553  computeImportForFunction(*FuncSummary, Index, ImportInstrLimit,
554  DefinedGVSummaries, Worklist, ImportList,
555  ExportLists, ImportThresholds);
556  }
557 
558  // Process the newly imported functions and add callees to the worklist.
559  while (!Worklist.empty()) {
560  auto FuncInfo = Worklist.pop_back_val();
561  auto *Summary = std::get<0>(FuncInfo);
562  auto Threshold = std::get<1>(FuncInfo);
563 
564  computeImportForFunction(*Summary, Index, Threshold, DefinedGVSummaries,
565  Worklist, ImportList, ExportLists,
566  ImportThresholds);
567  }
568 
569  // Print stats about functions considered but rejected for importing
570  // when requested.
571  if (PrintImportFailures) {
572  dbgs() << "Missed imports into module " << ModName << "\n";
573  for (auto &I : ImportThresholds) {
574  auto &ProcessedThreshold = std::get<0>(I.second);
575  auto &CalleeSummary = std::get<1>(I.second);
576  auto &FailureInfo = std::get<2>(I.second);
577  if (CalleeSummary)
578  continue; // We are going to import.
579  assert(FailureInfo);
580  FunctionSummary *FS = nullptr;
581  if (!FailureInfo->VI.getSummaryList().empty())
582  FS = dyn_cast<FunctionSummary>(
583  FailureInfo->VI.getSummaryList()[0]->getBaseObject());
584  dbgs() << FailureInfo->VI
585  << ": Reason = " << getFailureName(FailureInfo->Reason)
586  << ", Threshold = " << ProcessedThreshold
587  << ", Size = " << (FS ? (int)FS->instCount() : -1)
588  << ", MaxHotness = " << getHotnessName(FailureInfo->MaxHotness)
589  << ", Attempts = " << FailureInfo->Attempts << "\n";
590  }
591  }
592 }
593 
594 #ifndef NDEBUG
597  if (const auto &VI = Index.getValueInfo(G)) {
598  auto SL = VI.getSummaryList();
599  if (!SL.empty())
600  return SL[0]->getSummaryKind() == GlobalValueSummary::GlobalVarKind;
601  }
602  return false;
603 }
604 
606 
607 template <class T>
609  T &Cont) {
610  unsigned NumGVS = 0;
611  for (auto &V : Cont)
612  if (isGlobalVarSummary(Index, getGUID(V)))
613  ++NumGVS;
614  return NumGVS;
615 }
616 #endif
617 
618 /// Compute all the import and export for every module using the Index.
620  const ModuleSummaryIndex &Index,
621  const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
624  // For each module that has function defined, compute the import/export lists.
625  for (auto &DefinedGVSummaries : ModuleToDefinedGVSummaries) {
626  auto &ImportList = ImportLists[DefinedGVSummaries.first()];
627  LLVM_DEBUG(dbgs() << "Computing import for Module '"
628  << DefinedGVSummaries.first() << "'\n");
629  ComputeImportForModule(DefinedGVSummaries.second, Index,
630  DefinedGVSummaries.first(), ImportList,
631  &ExportLists);
632  }
633 
634  // When computing imports we added all GUIDs referenced by anything
635  // imported from the module to its ExportList. Now we prune each ExportList
636  // of any not defined in that module. This is more efficient than checking
637  // while computing imports because some of the summary lists may be long
638  // due to linkonce (comdat) copies.
639  for (auto &ELI : ExportLists) {
640  const auto &DefinedGVSummaries =
641  ModuleToDefinedGVSummaries.lookup(ELI.first());
642  for (auto EI = ELI.second.begin(); EI != ELI.second.end();) {
643  if (!DefinedGVSummaries.count(*EI))
644  EI = ELI.second.erase(EI);
645  else
646  ++EI;
647  }
648  }
649 
650 #ifndef NDEBUG
651  LLVM_DEBUG(dbgs() << "Import/Export lists for " << ImportLists.size()
652  << " modules:\n");
653  for (auto &ModuleImports : ImportLists) {
654  auto ModName = ModuleImports.first();
655  auto &Exports = ExportLists[ModName];
656  unsigned NumGVS = numGlobalVarSummaries(Index, Exports);
657  LLVM_DEBUG(dbgs() << "* Module " << ModName << " exports "
658  << Exports.size() - NumGVS << " functions and " << NumGVS
659  << " vars. Imports from " << ModuleImports.second.size()
660  << " modules.\n");
661  for (auto &Src : ModuleImports.second) {
662  auto SrcModName = Src.first();
663  unsigned NumGVSPerMod = numGlobalVarSummaries(Index, Src.second);
664  LLVM_DEBUG(dbgs() << " - " << Src.second.size() - NumGVSPerMod
665  << " functions imported from " << SrcModName << "\n");
666  LLVM_DEBUG(dbgs() << " - " << NumGVSPerMod
667  << " global vars imported from " << SrcModName << "\n");
668  }
669  }
670 #endif
671 }
672 
673 #ifndef NDEBUG
675  StringRef ModulePath,
676  FunctionImporter::ImportMapTy &ImportList) {
677  LLVM_DEBUG(dbgs() << "* Module " << ModulePath << " imports from "
678  << ImportList.size() << " modules.\n");
679  for (auto &Src : ImportList) {
680  auto SrcModName = Src.first();
681  unsigned NumGVSPerMod = numGlobalVarSummaries(Index, Src.second);
682  LLVM_DEBUG(dbgs() << " - " << Src.second.size() - NumGVSPerMod
683  << " functions imported from " << SrcModName << "\n");
684  LLVM_DEBUG(dbgs() << " - " << NumGVSPerMod << " vars imported from "
685  << SrcModName << "\n");
686  }
687 }
688 #endif
689 
690 /// Compute all the imports for the given module in the Index.
692  StringRef ModulePath, const ModuleSummaryIndex &Index,
693  FunctionImporter::ImportMapTy &ImportList) {
694  // Collect the list of functions this module defines.
695  // GUID -> Summary
696  GVSummaryMapTy FunctionSummaryMap;
697  Index.collectDefinedFunctionsForModule(ModulePath, FunctionSummaryMap);
698 
699  // Compute the import list for this module.
700  LLVM_DEBUG(dbgs() << "Computing import for Module '" << ModulePath << "'\n");
701  ComputeImportForModule(FunctionSummaryMap, Index, ModulePath, ImportList);
702 
703 #ifndef NDEBUG
704  dumpImportListForModule(Index, ModulePath, ImportList);
705 #endif
706 }
707 
708 // Mark all external summaries in Index for import into the given module.
709 // Used for distributed builds using a distributed index.
711  StringRef ModulePath, const ModuleSummaryIndex &Index,
712  FunctionImporter::ImportMapTy &ImportList) {
713  for (auto &GlobalList : Index) {
714  // Ignore entries for undefined references.
715  if (GlobalList.second.SummaryList.empty())
716  continue;
717 
718  auto GUID = GlobalList.first;
719  assert(GlobalList.second.SummaryList.size() == 1 &&
720  "Expected individual combined index to have one summary per GUID");
721  auto &Summary = GlobalList.second.SummaryList[0];
722  // Skip the summaries for the importing module. These are included to
723  // e.g. record required linkage changes.
724  if (Summary->modulePath() == ModulePath)
725  continue;
726  // Add an entry to provoke importing by thinBackend.
727  ImportList[Summary->modulePath()].insert(GUID);
728  }
729 #ifndef NDEBUG
730  dumpImportListForModule(Index, ModulePath, ImportList);
731 #endif
732 }
733 
736  const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols,
739  if (!ComputeDead)
740  return;
741  if (GUIDPreservedSymbols.empty())
742  // Don't do anything when nothing is live, this is friendly with tests.
743  return;
744  unsigned LiveSymbols = 0;
746  Worklist.reserve(GUIDPreservedSymbols.size() * 2);
747  for (auto GUID : GUIDPreservedSymbols) {
748  ValueInfo VI = Index.getValueInfo(GUID);
749  if (!VI)
750  continue;
751  for (auto &S : VI.getSummaryList())
752  S->setLive(true);
753  }
754 
755  // Add values flagged in the index as live roots to the worklist.
756  for (const auto &Entry : Index) {
757  auto VI = Index.getValueInfo(Entry);
758  for (auto &S : Entry.second.SummaryList)
759  if (S->isLive()) {
760  LLVM_DEBUG(dbgs() << "Live root: " << VI << "\n");
761  Worklist.push_back(VI);
762  ++LiveSymbols;
763  break;
764  }
765  }
766 
767  // Make value live and add it to the worklist if it was not live before.
768  auto visit = [&](ValueInfo VI) {
769  // FIXME: If we knew which edges were created for indirect call profiles,
770  // we could skip them here. Any that are live should be reached via
771  // other edges, e.g. reference edges. Otherwise, using a profile collected
772  // on a slightly different binary might provoke preserving, importing
773  // and ultimately promoting calls to functions not linked into this
774  // binary, which increases the binary size unnecessarily. Note that
775  // if this code changes, the importer needs to change so that edges
776  // to functions marked dead are skipped.
778  if (!VI)
779  return;
780  for (auto &S : VI.getSummaryList())
781  if (S->isLive())
782  return;
783 
784  // We only keep live symbols that are known to be non-prevailing if any are
785  // available_externally, linkonceodr, weakodr. Those symbols are discarded
786  // later in the EliminateAvailableExternally pass and setting them to
787  // not-live could break downstreams users of liveness information (PR36483)
788  // or limit optimization opportunities.
789  if (isPrevailing(VI.getGUID()) == PrevailingType::No) {
790  bool KeepAliveLinkage = false;
791  bool Interposable = false;
792  for (auto &S : VI.getSummaryList()) {
793  if (S->linkage() == GlobalValue::AvailableExternallyLinkage ||
794  S->linkage() == GlobalValue::WeakODRLinkage ||
795  S->linkage() == GlobalValue::LinkOnceODRLinkage)
796  KeepAliveLinkage = true;
797  else if (GlobalValue::isInterposableLinkage(S->linkage()))
798  Interposable = true;
799  }
800 
801  if (!KeepAliveLinkage)
802  return;
803 
804  if (Interposable)
806  "Interposable and available_externally/linkonce_odr/weak_odr symbol");
807  }
808 
809  for (auto &S : VI.getSummaryList())
810  S->setLive(true);
811  ++LiveSymbols;
812  Worklist.push_back(VI);
813  };
814 
815  while (!Worklist.empty()) {
816  auto VI = Worklist.pop_back_val();
817  for (auto &Summary : VI.getSummaryList()) {
818  GlobalValueSummary *Base = Summary->getBaseObject();
819  // Set base value live in case it is an alias.
820  Base->setLive(true);
821  for (auto Ref : Base->refs())
822  visit(Ref);
823  if (auto *FS = dyn_cast<FunctionSummary>(Base))
824  for (auto Call : FS->calls())
825  visit(Call.first);
826  }
827  }
828  Index.setWithGlobalValueDeadStripping();
829 
830  unsigned DeadSymbols = Index.size() - LiveSymbols;
831  LLVM_DEBUG(dbgs() << LiveSymbols << " symbols Live, and " << DeadSymbols
832  << " symbols Dead \n");
833  NumDeadSymbols += DeadSymbols;
834  NumLiveSymbols += LiveSymbols;
835 }
836 
837 // Compute dead symbols and propagate constants in combined index.
839  ModuleSummaryIndex &Index,
840  const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols,
842  bool ImportEnabled) {
843  computeDeadSymbols(Index, GUIDPreservedSymbols, isPrevailing);
844  if (ImportEnabled) {
845  Index.propagateConstants(GUIDPreservedSymbols);
846  } else {
847  // If import is disabled we should drop read-only attribute
848  // from all summaries to prevent internalization.
849  for (auto &P : Index)
850  for (auto &S : P.second.SummaryList)
851  if (auto *GVS = dyn_cast<GlobalVarSummary>(S.get()))
852  GVS->setReadOnly(false);
853  }
854 }
855 
856 /// Compute the set of summaries needed for a ThinLTO backend compilation of
857 /// \p ModulePath.
859  StringRef ModulePath,
860  const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
861  const FunctionImporter::ImportMapTy &ImportList,
862  std::map<std::string, GVSummaryMapTy> &ModuleToSummariesForIndex) {
863  // Include all summaries from the importing module.
864  ModuleToSummariesForIndex[ModulePath] =
865  ModuleToDefinedGVSummaries.lookup(ModulePath);
866  // Include summaries for imports.
867  for (auto &ILI : ImportList) {
868  auto &SummariesForIndex = ModuleToSummariesForIndex[ILI.first()];
869  const auto &DefinedGVSummaries =
870  ModuleToDefinedGVSummaries.lookup(ILI.first());
871  for (auto &GI : ILI.second) {
872  const auto &DS = DefinedGVSummaries.find(GI);
873  assert(DS != DefinedGVSummaries.end() &&
874  "Expected a defined summary for imported global value");
875  SummariesForIndex[GI] = DS->second;
876  }
877  }
878 }
879 
880 /// Emit the files \p ModulePath will import from into \p OutputFilename.
881 std::error_code llvm::EmitImportsFiles(
882  StringRef ModulePath, StringRef OutputFilename,
883  const std::map<std::string, GVSummaryMapTy> &ModuleToSummariesForIndex) {
884  std::error_code EC;
885  raw_fd_ostream ImportsOS(OutputFilename, EC, sys::fs::OpenFlags::F_None);
886  if (EC)
887  return EC;
888  for (auto &ILI : ModuleToSummariesForIndex)
889  // The ModuleToSummariesForIndex map includes an entry for the current
890  // Module (needed for writing out the index files). We don't want to
891  // include it in the imports file, however, so filter it out.
892  if (ILI.first != ModulePath)
893  ImportsOS << ILI.first << "\n";
894  return std::error_code();
895 }
896 
898  LLVM_DEBUG(dbgs() << "Converting to a declaration: `" << GV.getName()
899  << "\n");
900  if (Function *F = dyn_cast<Function>(&GV)) {
901  F->deleteBody();
902  F->clearMetadata();
903  F->setComdat(nullptr);
904  } else if (GlobalVariable *V = dyn_cast<GlobalVariable>(&GV)) {
905  V->setInitializer(nullptr);
906  V->setLinkage(GlobalValue::ExternalLinkage);
907  V->clearMetadata();
908  V->setComdat(nullptr);
909  } else {
910  GlobalValue *NewGV;
911  if (GV.getValueType()->isFunctionTy())
912  NewGV =
913  Function::Create(cast<FunctionType>(GV.getValueType()),
915  else
916  NewGV =
917  new GlobalVariable(*GV.getParent(), GV.getValueType(),
918  /*isConstant*/ false, GlobalValue::ExternalLinkage,
919  /*init*/ nullptr, "",
920  /*insertbefore*/ nullptr, GV.getThreadLocalMode(),
921  GV.getType()->getAddressSpace());
922  NewGV->takeName(&GV);
923  GV.replaceAllUsesWith(NewGV);
924  return false;
925  }
926  return true;
927 }
928 
929 /// Fixup prevailing symbol linkages in \p TheModule based on summary analysis.
931  Module &TheModule, const GVSummaryMapTy &DefinedGlobals) {
932  auto updateLinkage = [&](GlobalValue &GV) {
933  // See if the global summary analysis computed a new resolved linkage.
934  const auto &GS = DefinedGlobals.find(GV.getGUID());
935  if (GS == DefinedGlobals.end())
936  return;
937  auto NewLinkage = GS->second->linkage();
938  if (NewLinkage == GV.getLinkage())
939  return;
940 
941  // Switch the linkage to weakany if asked for, e.g. we do this for
942  // linker redefined symbols (via --wrap or --defsym).
943  // We record that the visibility should be changed here in `addThinLTO`
944  // as we need access to the resolution vectors for each input file in
945  // order to find which symbols have been redefined.
946  // We may consider reorganizing this code and moving the linkage recording
947  // somewhere else, e.g. in thinLTOResolvePrevailingInIndex.
948  if (NewLinkage == GlobalValue::WeakAnyLinkage) {
949  GV.setLinkage(NewLinkage);
950  return;
951  }
952 
953  if (GlobalValue::isLocalLinkage(GV.getLinkage()) ||
954  // In case it was dead and already converted to declaration.
955  GV.isDeclaration())
956  return;
957  // Check for a non-prevailing def that has interposable linkage
958  // (e.g. non-odr weak or linkonce). In that case we can't simply
959  // convert to available_externally, since it would lose the
960  // interposable property and possibly get inlined. Simply drop
961  // the definition in that case.
963  GlobalValue::isInterposableLinkage(GV.getLinkage())) {
964  if (!convertToDeclaration(GV))
965  // FIXME: Change this to collect replaced GVs and later erase
966  // them from the parent module once thinLTOResolvePrevailingGUID is
967  // changed to enable this for aliases.
968  llvm_unreachable("Expected GV to be converted");
969  } else {
970  // If the original symbols has global unnamed addr and linkonce_odr linkage,
971  // it should be an auto hide symbol. Add hidden visibility to the symbol to
972  // preserve the property.
973  if (GV.hasLinkOnceODRLinkage() && GV.hasGlobalUnnamedAddr() &&
974  NewLinkage == GlobalValue::WeakODRLinkage)
975  GV.setVisibility(GlobalValue::HiddenVisibility);
976 
977  LLVM_DEBUG(dbgs() << "ODR fixing up linkage for `" << GV.getName()
978  << "` from " << GV.getLinkage() << " to " << NewLinkage
979  << "\n");
980  GV.setLinkage(NewLinkage);
981  }
982  // Remove declarations from comdats, including available_externally
983  // as this is a declaration for the linker, and will be dropped eventually.
984  // It is illegal for comdats to contain declarations.
985  auto *GO = dyn_cast_or_null<GlobalObject>(&GV);
986  if (GO && GO->isDeclarationForLinker() && GO->hasComdat())
987  GO->setComdat(nullptr);
988  };
989 
990  // Process functions and global now
991  for (auto &GV : TheModule)
992  updateLinkage(GV);
993  for (auto &GV : TheModule.globals())
994  updateLinkage(GV);
995  for (auto &GV : TheModule.aliases())
996  updateLinkage(GV);
997 }
998 
999 /// Run internalization on \p TheModule based on symmary analysis.
1001  const GVSummaryMapTy &DefinedGlobals) {
1002  // Declare a callback for the internalize pass that will ask for every
1003  // candidate GlobalValue if it can be internalized or not.
1004  auto MustPreserveGV = [&](const GlobalValue &GV) -> bool {
1005  // Lookup the linkage recorded in the summaries during global analysis.
1006  auto GS = DefinedGlobals.find(GV.getGUID());
1007  if (GS == DefinedGlobals.end()) {
1008  // Must have been promoted (possibly conservatively). Find original
1009  // name so that we can access the correct summary and see if it can
1010  // be internalized again.
1011  // FIXME: Eventually we should control promotion instead of promoting
1012  // and internalizing again.
1013  StringRef OrigName =
1015  std::string OrigId = GlobalValue::getGlobalIdentifier(
1016  OrigName, GlobalValue::InternalLinkage,
1017  TheModule.getSourceFileName());
1018  GS = DefinedGlobals.find(GlobalValue::getGUID(OrigId));
1019  if (GS == DefinedGlobals.end()) {
1020  // Also check the original non-promoted non-globalized name. In some
1021  // cases a preempted weak value is linked in as a local copy because
1022  // it is referenced by an alias (IRLinker::linkGlobalValueProto).
1023  // In that case, since it was originally not a local value, it was
1024  // recorded in the index using the original name.
1025  // FIXME: This may not be needed once PR27866 is fixed.
1026  GS = DefinedGlobals.find(GlobalValue::getGUID(OrigName));
1027  assert(GS != DefinedGlobals.end());
1028  }
1029  }
1030  return !GlobalValue::isLocalLinkage(GS->second->linkage());
1031  };
1032 
1033  // FIXME: See if we can just internalize directly here via linkage changes
1034  // based on the index, rather than invoking internalizeModule.
1035  internalizeModule(TheModule, MustPreserveGV);
1036 }
1037 
1038 /// Make alias a clone of its aliasee.
1040  Function *Fn = cast<Function>(GA->getBaseObject());
1041 
1042  ValueToValueMapTy VMap;
1043  Function *NewFn = CloneFunction(Fn, VMap);
1044  // Clone should use the original alias's linkage and name, and we ensure
1045  // all uses of alias instead use the new clone (casted if necessary).
1046  NewFn->setLinkage(GA->getLinkage());
1048  NewFn->takeName(GA);
1049  return NewFn;
1050 }
1051 
1052 // Internalize values that we marked with specific attribute
1053 // in processGlobalForThinLTO.
1055  for (auto &GV : M.globals())
1056  // Skip GVs which have been converted to declarations
1057  // by dropDeadSymbols.
1058  if (!GV.isDeclaration() && GV.hasAttribute("thinlto-internalize")) {
1059  GV.setLinkage(GlobalValue::InternalLinkage);
1060  GV.setVisibility(GlobalValue::DefaultVisibility);
1061  }
1062 }
1063 
1064 // Automatically import functions in Module \p DestModule based on the summaries
1065 // index.
1067  Module &DestModule, const FunctionImporter::ImportMapTy &ImportList) {
1068  LLVM_DEBUG(dbgs() << "Starting import for Module "
1069  << DestModule.getModuleIdentifier() << "\n");
1070  unsigned ImportedCount = 0, ImportedGVCount = 0;
1071 
1072  IRMover Mover(DestModule);
1073  // Do the actual import of functions now, one Module at a time
1074  std::set<StringRef> ModuleNameOrderedList;
1075  for (auto &FunctionsToImportPerModule : ImportList) {
1076  ModuleNameOrderedList.insert(FunctionsToImportPerModule.first());
1077  }
1078  for (auto &Name : ModuleNameOrderedList) {
1079  // Get the module for the import
1080  const auto &FunctionsToImportPerModule = ImportList.find(Name);
1081  assert(FunctionsToImportPerModule != ImportList.end());
1082  Expected<std::unique_ptr<Module>> SrcModuleOrErr = ModuleLoader(Name);
1083  if (!SrcModuleOrErr)
1084  return SrcModuleOrErr.takeError();
1085  std::unique_ptr<Module> SrcModule = std::move(*SrcModuleOrErr);
1086  assert(&DestModule.getContext() == &SrcModule->getContext() &&
1087  "Context mismatch");
1088 
1089  // If modules were created with lazy metadata loading, materialize it
1090  // now, before linking it (otherwise this will be a noop).
1091  if (Error Err = SrcModule->materializeMetadata())
1092  return std::move(Err);
1093 
1094  auto &ImportGUIDs = FunctionsToImportPerModule->second;
1095  // Find the globals to import
1096  SetVector<GlobalValue *> GlobalsToImport;
1097  for (Function &F : *SrcModule) {
1098  if (!F.hasName())
1099  continue;
1100  auto GUID = F.getGUID();
1101  auto Import = ImportGUIDs.count(GUID);
1102  LLVM_DEBUG(dbgs() << (Import ? "Is" : "Not") << " importing function "
1103  << GUID << " " << F.getName() << " from "
1104  << SrcModule->getSourceFileName() << "\n");
1105  if (Import) {
1106  if (Error Err = F.materialize())
1107  return std::move(Err);
1108  if (EnableImportMetadata) {
1109  // Add 'thinlto_src_module' metadata for statistics and debugging.
1110  F.setMetadata(
1111  "thinlto_src_module",
1112  MDNode::get(DestModule.getContext(),
1113  {MDString::get(DestModule.getContext(),
1114  SrcModule->getSourceFileName())}));
1115  }
1116  GlobalsToImport.insert(&F);
1117  }
1118  }
1119  for (GlobalVariable &GV : SrcModule->globals()) {
1120  if (!GV.hasName())
1121  continue;
1122  auto GUID = GV.getGUID();
1123  auto Import = ImportGUIDs.count(GUID);
1124  LLVM_DEBUG(dbgs() << (Import ? "Is" : "Not") << " importing global "
1125  << GUID << " " << GV.getName() << " from "
1126  << SrcModule->getSourceFileName() << "\n");
1127  if (Import) {
1128  if (Error Err = GV.materialize())
1129  return std::move(Err);
1130  ImportedGVCount += GlobalsToImport.insert(&GV);
1131  }
1132  }
1133  for (GlobalAlias &GA : SrcModule->aliases()) {
1134  if (!GA.hasName())
1135  continue;
1136  auto GUID = GA.getGUID();
1137  auto Import = ImportGUIDs.count(GUID);
1138  LLVM_DEBUG(dbgs() << (Import ? "Is" : "Not") << " importing alias "
1139  << GUID << " " << GA.getName() << " from "
1140  << SrcModule->getSourceFileName() << "\n");
1141  if (Import) {
1142  if (Error Err = GA.materialize())
1143  return std::move(Err);
1144  // Import alias as a copy of its aliasee.
1145  GlobalObject *Base = GA.getBaseObject();
1146  if (Error Err = Base->materialize())
1147  return std::move(Err);
1148  auto *Fn = replaceAliasWithAliasee(SrcModule.get(), &GA);
1149  LLVM_DEBUG(dbgs() << "Is importing aliasee fn " << Base->getGUID()
1150  << " " << Base->getName() << " from "
1151  << SrcModule->getSourceFileName() << "\n");
1152  if (EnableImportMetadata) {
1153  // Add 'thinlto_src_module' metadata for statistics and debugging.
1154  Fn->setMetadata(
1155  "thinlto_src_module",
1156  MDNode::get(DestModule.getContext(),
1157  {MDString::get(DestModule.getContext(),
1158  SrcModule->getSourceFileName())}));
1159  }
1160  GlobalsToImport.insert(Fn);
1161  }
1162  }
1163 
1164  // Upgrade debug info after we're done materializing all the globals and we
1165  // have loaded all the required metadata!
1166  UpgradeDebugInfo(*SrcModule);
1167 
1168  // Link in the specified functions.
1169  if (renameModuleForThinLTO(*SrcModule, Index, &GlobalsToImport))
1170  return true;
1171 
1172  if (PrintImports) {
1173  for (const auto *GV : GlobalsToImport)
1174  dbgs() << DestModule.getSourceFileName() << ": Import " << GV->getName()
1175  << " from " << SrcModule->getSourceFileName() << "\n";
1176  }
1177 
1178  if (Mover.move(std::move(SrcModule), GlobalsToImport.getArrayRef(),
1179  [](GlobalValue &, IRMover::ValueAdder) {},
1180  /*IsPerformingImport=*/true))
1181  report_fatal_error("Function Import: link error");
1182 
1183  ImportedCount += GlobalsToImport.size();
1184  NumImportedModules++;
1185  }
1186 
1187  internalizeImmutableGVs(DestModule);
1188 
1189  NumImportedFunctions += (ImportedCount - ImportedGVCount);
1190  NumImportedGlobalVars += ImportedGVCount;
1191 
1192  LLVM_DEBUG(dbgs() << "Imported " << ImportedCount - ImportedGVCount
1193  << " functions for Module "
1194  << DestModule.getModuleIdentifier() << "\n");
1195  LLVM_DEBUG(dbgs() << "Imported " << ImportedGVCount
1196  << " global variables for Module "
1197  << DestModule.getModuleIdentifier() << "\n");
1198  return ImportedCount;
1199 }
1200 
1201 static bool doImportingForModule(Module &M) {
1202  if (SummaryFile.empty())
1203  report_fatal_error("error: -function-import requires -summary-file\n");
1206  if (!IndexPtrOrErr) {
1207  logAllUnhandledErrors(IndexPtrOrErr.takeError(), errs(),
1208  "Error loading file '" + SummaryFile + "': ");
1209  return false;
1210  }
1211  std::unique_ptr<ModuleSummaryIndex> Index = std::move(*IndexPtrOrErr);
1212 
1213  // First step is collecting the import list.
1214  FunctionImporter::ImportMapTy ImportList;
1215  // If requested, simply import all functions in the index. This is used
1216  // when testing distributed backend handling via the opt tool, when
1217  // we have distributed indexes containing exactly the summaries to import.
1218  if (ImportAllIndex)
1220  ImportList);
1221  else
1223  ImportList);
1224 
1225  // Conservatively mark all internal values as promoted. This interface is
1226  // only used when doing importing via the function importing pass. The pass
1227  // is only enabled when testing importing via the 'opt' tool, which does
1228  // not do the ThinLink that would normally determine what values to promote.
1229  for (auto &I : *Index) {
1230  for (auto &S : I.second.SummaryList) {
1231  if (GlobalValue::isLocalLinkage(S->linkage()))
1232  S->setLinkage(GlobalValue::ExternalLinkage);
1233  }
1234  }
1235 
1236  // Next we need to promote to global scope and rename any local values that
1237  // are potentially exported to other modules.
1238  if (renameModuleForThinLTO(M, *Index, nullptr)) {
1239  errs() << "Error renaming module\n";
1240  return false;
1241  }
1242 
1243  // Perform the import now.
1244  auto ModuleLoader = [&M](StringRef Identifier) {
1245  return loadFile(Identifier, M.getContext());
1246  };
1247  FunctionImporter Importer(*Index, ModuleLoader);
1248  Expected<bool> Result = Importer.importFunctions(M, ImportList);
1249 
1250  // FIXME: Probably need to propagate Errors through the pass manager.
1251  if (!Result) {
1252  logAllUnhandledErrors(Result.takeError(), errs(),
1253  "Error importing module: ");
1254  return false;
1255  }
1256 
1257  return *Result;
1258 }
1259 
1260 namespace {
1261 
1262 /// Pass that performs cross-module function import provided a summary file.
1263 class FunctionImportLegacyPass : public ModulePass {
1264 public:
1265  /// Pass identification, replacement for typeid
1266  static char ID;
1267 
1268  explicit FunctionImportLegacyPass() : ModulePass(ID) {}
1269 
1270  /// Specify pass name for debug output
1271  StringRef getPassName() const override { return "Function Importing"; }
1272 
1273  bool runOnModule(Module &M) override {
1274  if (skipModule(M))
1275  return false;
1276 
1277  return doImportingForModule(M);
1278  }
1279 };
1280 
1281 } // end anonymous namespace
1282 
1284  ModuleAnalysisManager &AM) {
1285  if (!doImportingForModule(M))
1286  return PreservedAnalyses::all();
1287 
1288  return PreservedAnalyses::none();
1289 }
1290 
1292 INITIALIZE_PASS(FunctionImportLegacyPass, "function-import",
1293  "Summary Based Function Import", false, false)
1294 
1295 namespace llvm {
1296 
1298  return new FunctionImportLegacyPass();
1299 }
1300 
1301 } // end namespace llvm
static bool isInterposableLinkage(LinkageTypes Linkage)
Whether the definition of this global may be replaced by something non-equivalent at link time...
Definition: GlobalValue.h:337
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:81
const NoneType None
Definition: None.h:24
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
ThreadLocalMode getThreadLocalMode() const
Definition: GlobalValue.h:255
const GlobalObject * getBaseObject() const
raw_ostream & errs()
This returns a reference to a raw_ostream for standard error.
void thinLTOResolvePrevailingInModule(Module &TheModule, const GVSummaryMapTy &DefinedGlobals)
Resolve prevailing symbol linkages in TheModule based on the information recorded in the summaries du...
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
LLVMContext & Context
uint64_t GUID
Declare a type to represent a global unique identifier for a global value.
Definition: GlobalValue.h:493
LLVM_ATTRIBUTE_NORETURN void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:139
This class represents lattice values for constants.
Definition: AllocatorList.h:24
void print(const char *ProgName, raw_ostream &S, bool ShowColors=true, bool ShowKindLabel=true) const
Definition: SourceMgr.cpp:374
ArrayRef< T > getArrayRef() const
Definition: SetVector.h:64
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:78
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:64
Same, but only replaced by something equivalent.
Definition: GlobalValue.h:54
static MDString * get(LLVMContext &Context, StringRef Str)
Definition: Metadata.cpp:454
Implements a dense probed hash-table based set.
Definition: DenseSet.h:250
Available for inspection, not emission.
Definition: GlobalValue.h:50
static cl::opt< int > ImportCutoff("import-cutoff", cl::init(-1), cl::Hidden, cl::value_desc("N"), cl::desc("Only import first N functions if N>=0 (default -1)"))
std::error_code EmitImportsFiles(StringRef ModulePath, StringRef OutputFilename, const std::map< std::string, GVSummaryMapTy > &ModuleToSummariesForIndex)
Emit into OutputFilename the files module ModulePath will import from.
ArrayRef< ValueInfo > refs() const
Return the list of values referenced by this global value definition.
This file contains the declarations for metadata subclasses.
Function * CloneFunction(Function *F, ValueToValueMapTy &VMap, ClonedCodeInfo *CodeInfo=nullptr)
Return a copy of the specified function and add it to that function&#39;s module.
bool convertToDeclaration(GlobalValue &GV)
Converts value GV to declaration, or replaces with a declaration if it is an alias.
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:111
Externally visible function.
Definition: GlobalValue.h:49
static void ComputeImportForModule(const GVSummaryMapTy &DefinedGVSummaries, const ModuleSummaryIndex &Index, StringRef ModName, FunctionImporter::ImportMapTy &ImportList, StringMap< FunctionImporter::ExportSetTy > *ExportLists=nullptr)
Given the list of globals defined in a module, compute the list of imports as well as the list of "ex...
static StringRef getOriginalNameBeforePromote(StringRef Name)
Helper to obtain the unpromoted name for a global value (or the original name if not promoted)...
STATISTIC(NumFunctions, "Total number of functions")
bool isGlobalValueLive(const GlobalValueSummary *GVS) const
F(f)
Error takeError()
Take ownership of the stored error.
Definition: Error.h:553
std::string getGlobalIdentifier() const
Return the modified name for this global value suitable to be used as the key for a global lookup (e...
Definition: Globals.cpp:156
void reserve(size_type N)
Definition: SmallVector.h:376
static std::unique_ptr< Module > loadFile(const std::string &FileName, LLVMContext &Context)
static bool isLocalLinkage(LinkageTypes Linkage)
Definition: GlobalValue.h:321
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:221
GlobalValue::GUID getGUID() const
amdgpu Simplify well known AMD library false Value Value const Twine & Name
unsigned size() const
Definition: StringMap.h:112
static cl::opt< unsigned > ImportInstrLimit("import-instr-limit", cl::init(100), cl::Hidden, cl::value_desc("N"), cl::desc("Only import functions with less than N instructions"))
Limit on instruction count of imported functions.
static void 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)
Compute the list of functions to import for a given caller.
static cl::opt< float > ImportHotMultiplier("import-hot-multiplier", cl::init(10.0), cl::Hidden, cl::value_desc("x"), cl::desc("Multiply the `import-instr-limit` threshold for hot callsites"))
LLVMContext & getContext() const
Get the global data context.
Definition: Module.h:243
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
static bool isGlobalVarSummary(const ModuleSummaryIndex &Index, GlobalValue::GUID G)
The access may reference the value stored in memory.
static cl::opt< bool > PrintImportFailures("print-import-failures", cl::init(false), cl::Hidden, cl::desc("Print information for functions rejected for importing"))
static bool canImportGlobalVar(GlobalValueSummary *S)
Tagged union holding either a T or a Error.
Definition: CachePruning.h:23
static cl::opt< std::string > OutputFilename("o", cl::desc("Output filename"), cl::value_desc("filename"), cl::init("-"))
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:142
Error move(std::unique_ptr< Module > Src, ArrayRef< GlobalValue *> ValuesToLink, std::function< void(GlobalValue &GV, ValueAdder Add)> AddLazyFor, bool IsPerformingImport)
Move in the provide values in ValuesToLink from Src.
Definition: IRMover.cpp:1483
void propagateConstants(const DenseSet< GlobalValue::GUID > &PreservedSymbols)
Analyze index and detect unmodified globals.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
static cl::opt< float > ImportCriticalMultiplier("import-critical-multiplier", cl::init(100.0), cl::Hidden, cl::value_desc("x"), cl::desc("Multiply the `import-instr-limit` threshold for critical callsites"))
LinkageTypes getLinkage() const
Definition: GlobalValue.h:451
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:430
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:292
Class to hold module path string table and global value map, and encapsulate methods for operating on...
ArrayRef< std::unique_ptr< GlobalValueSummary > > getSummaryList() const
const std::string & getSourceFileName() const
Get the module&#39;s original source file name.
Definition: Module.h:220
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:157
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:176
static Constant * getBitCast(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1769
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata *> MDs)
Definition: Metadata.h:1166
#define P(N)
Same, but only replaced by something equivalent.
Definition: GlobalValue.h:52
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:419
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)
Definition: Function.h:136
GlobalValue::GUID getGUIDFromOriginalID(GlobalValue::GUID OriginalID) const
Return the GUID for OriginalId in the OidGuidMap.
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:154
bool renameModuleForThinLTO(Module &M, const ModuleSummaryIndex &Index, SetVector< GlobalValue *> *GlobalsToImport=nullptr)
Perform in-place global value handling on the given Module for exported local functions renamed and p...
void gatherImportedSummariesForModule(StringRef ModulePath, const StringMap< GVSummaryMapTy > &ModuleToDefinedGVSummaries, const FunctionImporter::ImportMapTy &ImportList, std::map< std::string, GVSummaryMapTy > &ModuleToSummariesForIndex)
Compute the set of summaries needed for a ThinLTO backend compilation of ModulePath.
Import information from summary.
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:69
Pass * createFunctionImportPass()
This pass performs iterative function importing from other modules.
ImportFailureReason
The different reasons selectCallee will chose not to import a candidate.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
unsigned instCount() const
Get the instruction count recorded for this function.
PrevailingType
PrevailingType enum used as a return type of callback passed to computeDeadSymbols.
bool UpgradeDebugInfo(Module &M)
Check the debug info version number, if it is out-dated, drop the debug info.
void ComputeCrossModuleImportForModuleFromIndex(StringRef ModulePath, const ModuleSummaryIndex &Index, FunctionImporter::ImportMapTy &ImportList)
Mark all external summaries in Index for import into the given module.
unsigned getAddressSpace() const
Return the address space of the Pointer type.
Definition: DerivedTypes.h:495
ValueTy lookup(StringRef Key) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: StringMap.h:347
auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1208
INITIALIZE_PASS(FunctionImportLegacyPass, "function-import", "Summary Based Function Import", false, false) namespace llvm
Function and variable summary information to aid decisions and implementation of importing.
static GUID getGUID(StringRef GlobalName)
Return a 64-bit global unique ID constructed from global value name (i.e.
Definition: GlobalValue.h:497
Error materialize()
Make sure this GlobalValue is fully read.
Definition: Globals.cpp:50
static unsigned numGlobalVarSummaries(const ModuleSummaryIndex &Index, T &Cont)
static const char * getFailureName(FunctionImporter::ImportFailureReason Reason)
static cl::opt< bool > ImportAllIndex("import-all-index", cl::desc("Import all external functions in index."))
Used when testing importing from distributed indexes via opt.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:160
void logAllUnhandledErrors(Error E, raw_ostream &OS, Twine ErrorBanner={})
Log all errors (if any) in E to OS.
Definition: Error.cpp:61
const std::string & getModuleIdentifier() const
Get the module identifier which is, essentially, the name of the module.
Definition: Module.h:209
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
static Function * replaceAliasWithAliasee(Module *SrcModule, GlobalAlias *GA)
Make alias a clone of its aliasee.
Struct that holds a reference to a particular GUID in a global value summary.
std::unique_ptr< Module > getLazyIRFileModule(StringRef Filename, SMDiagnostic &Err, LLVMContext &Context, bool ShouldLazyLoadMetadata=false)
If the given file holds a bitcode image, return a Module for it which does lazy deserialization of fu...
Definition: IRReader.cpp:53
static cl::opt< float > ImportInstrFactor("import-instr-evolution-factor", cl::init(0.7), cl::Hidden, cl::value_desc("x"), cl::desc("As we import functions, multiply the " "`import-instr-limit` threshold by this factor " "before processing newly imported functions"))
const char * getHotnessName(CalleeInfo::HotnessType HT)
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
Module.h This file contains the declarations for the Module class.
static void computeImportForReferencedGlobals(const FunctionSummary &Summary, const GVSummaryMapTy &DefinedGVSummaries, FunctionImporter::ImportMapTy &ImportList, StringMap< FunctionImporter::ExportSetTy > *ExportLists)
const DataFlowGraph & G
Definition: RDFGraph.cpp:211
static bool isAvailableExternallyLinkage(LinkageTypes Linkage)
Definition: GlobalValue.h:294
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:381
static bool doImportingForModule(Module &M)
static const GlobalValueSummary * selectCallee(const ModuleSummaryIndex &Index, ArrayRef< std::unique_ptr< GlobalValueSummary >> CalleeSummaryList, unsigned Threshold, StringRef CallerModulePath, FunctionImporter::ImportFailureReason &Reason, GlobalValue::GUID GUID)
Given a list of possible callee implementation for a call site, select one that fits the Threshold...
static ValueInfo updateValueInfoForIndirectCalls(const ModuleSummaryIndex &Index, ValueInfo VI)
void setLinkage(LinkageTypes LT)
Definition: GlobalValue.h:445
bool insert(MapEntryTy *KeyValue)
insert - Insert the specified key/value pair into the map.
Definition: StringMap.h:366
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
StringMap - This is an unconventional map that is specialized for handling keys that are "strings"...
Definition: StringMap.h:220
Expected< std::unique_ptr< ModuleSummaryIndex > > getModuleSummaryIndexForFile(StringRef Path, bool IgnoreEmptyThinLTOIndexFile=false)
Parse the module summary index out of an IR file and return the module summary index object if found...
static cl::opt< unsigned > Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"), cl::init(100), cl::Hidden)
GUID getGUID() const
Return a 64-bit global unique ID constructed from global value name (i.e.
Definition: GlobalValue.h:501
static cl::opt< float > ImportColdMultiplier("import-cold-multiplier", cl::init(0), cl::Hidden, cl::value_desc("N"), cl::desc("Multiply the `import-instr-limit` threshold for cold callsites"))
#define NDEBUG
Definition: regutils.h:48
ValueInfo getValueInfo(const GlobalValueSummaryMapTy::value_type &R) const
Return a ValueInfo for the index value_type (convenient when iterating index).
static cl::opt< bool > ComputeDead("compute-dead", cl::init(true), cl::Hidden, cl::desc("Compute dead symbols"))
bool withGlobalValueDeadStripping() const
Expected< bool > importFunctions(Module &M, const ImportMapTy &ImportList)
Import functions in Module M based on the supplied import list.
static cl::opt< ITMode > IT(cl::desc("IT block support"), cl::Hidden, cl::init(DefaultIT), cl::ZeroOrMore, cl::values(clEnumValN(DefaultIT, "arm-default-it", "Generate IT block based on arch"), clEnumValN(RestrictedIT, "arm-restrict-it", "Disallow deprecated IT based on ARMv8"), clEnumValN(NoRestrictedIT, "arm-no-restrict-it", "Allow IT blocks based on ARMv7")))
void ComputeCrossModuleImport(const ModuleSummaryIndex &Index, const StringMap< GVSummaryMapTy > &ModuleToDefinedGVSummaries, StringMap< FunctionImporter::ImportMapTy > &ImportLists, StringMap< FunctionImporter::ExportSetTy > &ExportLists)
Compute all the imports and exports for every module in the Index.
bool isFunctionTy() const
True if this is an instance of FunctionType.
Definition: Type.h:215
A raw_ostream that writes to a file descriptor.
Definition: raw_ostream.h:366
void emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:652
static cl::opt< bool > PrintImports("print-imports", cl::init(false), cl::Hidden, cl::desc("Print imported functions"))
StringRef modulePath() const
Get the path to the module containing this function.
static cl::opt< float > ImportHotInstrFactor("import-hot-evolution-factor", cl::init(1.0), cl::Hidden, cl::value_desc("x"), cl::desc("As we import functions called from hot callsite, multiply the " "`import-instr-limit` threshold by this factor " "before processing newly imported functions"))
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:56
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:215
#define I(x, y, z)
Definition: MD5.cpp:58
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:225
iterator end()
Definition: DenseMap.h:109
void thinLTOInternalizeModule(Module &TheModule, const GVSummaryMapTy &DefinedGlobals)
Internalize TheModule based on the information recorded in the summaries during global summary-based ...
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
ArrayRef< EdgeTy > calls() const
Return the list of <CalleeValueInfo, CalleeInfo> pairs.
Type * getValueType() const
Definition: GlobalValue.h:276
Keep one copy of named function when linking (weak)
Definition: GlobalValue.h:53
Rename collisions when linking (static functions).
Definition: GlobalValue.h:56
Function summary information to aid decisions and implementation of importing.
static void dumpImportListForModule(const ModuleSummaryIndex &Index, StringRef ModulePath, FunctionImporter::ImportMapTy &ImportList)
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:171
static GlobalValue::GUID getGUID(GlobalValue::GUID G)
void ComputeCrossModuleImportForModule(StringRef ModulePath, const ModuleSummaryIndex &Index, FunctionImporter::ImportMapTy &ImportList)
Compute all the imports for the given module using the Index.
void computeDeadSymbolsWithConstProp(ModuleSummaryIndex &Index, const DenseSet< GlobalValue::GUID > &GUIDPreservedSymbols, function_ref< PrevailingType(GlobalValue::GUID)> isPrevailing, bool ImportEnabled)
Compute dead symbols and run constant propagation in combined index after that.
static cl::opt< std::string > SummaryFile("summary-file", cl::desc("The summary file to use for function importing."))
Summary file to use for function importing when using -function-import from the command line...
ModuleSummaryIndex.h This file contains the declarations the classes that hold the module index and s...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
std::function< void(GlobalValue &)> ValueAdder
Definition: IRMover.h:65
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:566
The function importer is automatically importing function from other modules based on the provided su...
A vector that has set insertion semantics.
Definition: SetVector.h:41
Lightweight error class with error context and mandatory checking.
Definition: Error.h:158
void computeDeadSymbols(ModuleSummaryIndex &Index, const DenseSet< GlobalValue::GUID > &GUIDPreservedSymbols, function_ref< PrevailingType(GlobalValue::GUID)> isPrevailing)
Compute all the symbols that are "dead": i.e these that can&#39;t be reached in the graph from any of the...
static cl::opt< bool > EnableImportMetadata("enable-import-metadata", cl::init(true), cl::Hidden, cl::desc("Enable import metadata like 'thinlto_src_module'"))
iterator_range< global_iterator > globals()
Definition: Module.h:574
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
A container for analyses that lazily runs them and caches their results.
#define LLVM_DEBUG(X)
Definition: Debug.h:123
bool internalizeModule(Module &TheModule, std::function< bool(const GlobalValue &)> MustPreserveGV, CallGraph *CG=nullptr)
Helper function to internalize functions and variables in a Module.
Definition: Internalize.h:71
void collectDefinedFunctionsForModule(StringRef ModulePath, GVSummaryMapTy &GVSummaryMap) const
Collect for the given module the list of functions it defines (GUID -> Summary).
PointerType * getType() const
Global values are always pointers.
Definition: GlobalValue.h:274
static void internalizeImmutableGVs(Module &M)
Instances of this class encapsulate one diagnostic report, allowing printing to a raw_ostream as a ca...
Definition: SourceMgr.h:260