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