LLVM  9.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 = llvm::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) {
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.
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 (!KeepAliveLinkage)
804  return;
805 
806  if (Interposable)
808  "Interposable and available_externally/linkonce_odr/weak_odr symbol");
809  }
810 
811  for (auto &S : VI.getSummaryList())
812  S->setLive(true);
813  ++LiveSymbols;
814  Worklist.push_back(VI);
815  };
816 
817  while (!Worklist.empty()) {
818  auto VI = Worklist.pop_back_val();
819  for (auto &Summary : VI.getSummaryList()) {
820  if (auto *AS = dyn_cast<AliasSummary>(Summary.get())) {
821  // If this is an alias, visit the aliasee VI to ensure that all copies
822  // are marked live and it is added to the worklist for further
823  // processing of its references.
824  visit(AS->getAliaseeVI());
825  continue;
826  }
827 
828  Summary->setLive(true);
829  for (auto Ref : Summary->refs())
830  visit(Ref);
831  if (auto *FS = dyn_cast<FunctionSummary>(Summary.get()))
832  for (auto Call : FS->calls())
833  visit(Call.first);
834  }
835  }
836  Index.setWithGlobalValueDeadStripping();
837 
838  unsigned DeadSymbols = Index.size() - LiveSymbols;
839  LLVM_DEBUG(dbgs() << LiveSymbols << " symbols Live, and " << DeadSymbols
840  << " symbols Dead \n");
841  NumDeadSymbols += DeadSymbols;
842  NumLiveSymbols += LiveSymbols;
843 }
844 
845 // Compute dead symbols and propagate constants in combined index.
847  ModuleSummaryIndex &Index,
848  const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols,
850  bool ImportEnabled) {
851  computeDeadSymbols(Index, GUIDPreservedSymbols, isPrevailing);
852  if (ImportEnabled) {
853  Index.propagateConstants(GUIDPreservedSymbols);
854  } else {
855  // If import is disabled we should drop read-only attribute
856  // from all summaries to prevent internalization.
857  for (auto &P : Index)
858  for (auto &S : P.second.SummaryList)
859  if (auto *GVS = dyn_cast<GlobalVarSummary>(S.get()))
860  GVS->setReadOnly(false);
861  }
862 }
863 
864 /// Compute the set of summaries needed for a ThinLTO backend compilation of
865 /// \p ModulePath.
867  StringRef ModulePath,
868  const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
869  const FunctionImporter::ImportMapTy &ImportList,
870  std::map<std::string, GVSummaryMapTy> &ModuleToSummariesForIndex) {
871  // Include all summaries from the importing module.
872  ModuleToSummariesForIndex[ModulePath] =
873  ModuleToDefinedGVSummaries.lookup(ModulePath);
874  // Include summaries for imports.
875  for (auto &ILI : ImportList) {
876  auto &SummariesForIndex = ModuleToSummariesForIndex[ILI.first()];
877  const auto &DefinedGVSummaries =
878  ModuleToDefinedGVSummaries.lookup(ILI.first());
879  for (auto &GI : ILI.second) {
880  const auto &DS = DefinedGVSummaries.find(GI);
881  assert(DS != DefinedGVSummaries.end() &&
882  "Expected a defined summary for imported global value");
883  SummariesForIndex[GI] = DS->second;
884  }
885  }
886 }
887 
888 /// Emit the files \p ModulePath will import from into \p OutputFilename.
889 std::error_code llvm::EmitImportsFiles(
890  StringRef ModulePath, StringRef OutputFilename,
891  const std::map<std::string, GVSummaryMapTy> &ModuleToSummariesForIndex) {
892  std::error_code EC;
893  raw_fd_ostream ImportsOS(OutputFilename, EC, sys::fs::OpenFlags::F_None);
894  if (EC)
895  return EC;
896  for (auto &ILI : ModuleToSummariesForIndex)
897  // The ModuleToSummariesForIndex map includes an entry for the current
898  // Module (needed for writing out the index files). We don't want to
899  // include it in the imports file, however, so filter it out.
900  if (ILI.first != ModulePath)
901  ImportsOS << ILI.first << "\n";
902  return std::error_code();
903 }
904 
906  LLVM_DEBUG(dbgs() << "Converting to a declaration: `" << GV.getName()
907  << "\n");
908  if (Function *F = dyn_cast<Function>(&GV)) {
909  F->deleteBody();
910  F->clearMetadata();
911  F->setComdat(nullptr);
912  } else if (GlobalVariable *V = dyn_cast<GlobalVariable>(&GV)) {
913  V->setInitializer(nullptr);
914  V->setLinkage(GlobalValue::ExternalLinkage);
915  V->clearMetadata();
916  V->setComdat(nullptr);
917  } else {
918  GlobalValue *NewGV;
919  if (GV.getValueType()->isFunctionTy())
920  NewGV =
921  Function::Create(cast<FunctionType>(GV.getValueType()),
923  "", GV.getParent());
924  else
925  NewGV =
926  new GlobalVariable(*GV.getParent(), GV.getValueType(),
927  /*isConstant*/ false, GlobalValue::ExternalLinkage,
928  /*init*/ nullptr, "",
929  /*insertbefore*/ nullptr, GV.getThreadLocalMode(),
930  GV.getType()->getAddressSpace());
931  NewGV->takeName(&GV);
932  GV.replaceAllUsesWith(NewGV);
933  return false;
934  }
935  return true;
936 }
937 
938 /// Fixup prevailing symbol linkages in \p TheModule based on summary analysis.
940  Module &TheModule, const GVSummaryMapTy &DefinedGlobals) {
941  auto updateLinkage = [&](GlobalValue &GV) {
942  // See if the global summary analysis computed a new resolved linkage.
943  const auto &GS = DefinedGlobals.find(GV.getGUID());
944  if (GS == DefinedGlobals.end())
945  return;
946  auto NewLinkage = GS->second->linkage();
947  if (NewLinkage == GV.getLinkage())
948  return;
949 
950  // Switch the linkage to weakany if asked for, e.g. we do this for
951  // linker redefined symbols (via --wrap or --defsym).
952  // We record that the visibility should be changed here in `addThinLTO`
953  // as we need access to the resolution vectors for each input file in
954  // order to find which symbols have been redefined.
955  // We may consider reorganizing this code and moving the linkage recording
956  // somewhere else, e.g. in thinLTOResolvePrevailingInIndex.
957  if (NewLinkage == GlobalValue::WeakAnyLinkage) {
958  GV.setLinkage(NewLinkage);
959  return;
960  }
961 
962  if (GlobalValue::isLocalLinkage(GV.getLinkage()) ||
963  // In case it was dead and already converted to declaration.
964  GV.isDeclaration())
965  return;
966  // Check for a non-prevailing def that has interposable linkage
967  // (e.g. non-odr weak or linkonce). In that case we can't simply
968  // convert to available_externally, since it would lose the
969  // interposable property and possibly get inlined. Simply drop
970  // the definition in that case.
972  GlobalValue::isInterposableLinkage(GV.getLinkage())) {
973  if (!convertToDeclaration(GV))
974  // FIXME: Change this to collect replaced GVs and later erase
975  // them from the parent module once thinLTOResolvePrevailingGUID is
976  // changed to enable this for aliases.
977  llvm_unreachable("Expected GV to be converted");
978  } else {
979  // If all copies of the original symbol had global unnamed addr and
980  // linkonce_odr linkage, it should be an auto hide symbol. In that case
981  // the thin link would have marked it as CanAutoHide. Add hidden visibility
982  // to the symbol to preserve the property.
983  if (NewLinkage == GlobalValue::WeakODRLinkage &&
984  GS->second->canAutoHide()) {
985  assert(GV.hasLinkOnceODRLinkage() && GV.hasGlobalUnnamedAddr());
986  GV.setVisibility(GlobalValue::HiddenVisibility);
987  }
988 
989  LLVM_DEBUG(dbgs() << "ODR fixing up linkage for `" << GV.getName()
990  << "` from " << GV.getLinkage() << " to " << NewLinkage
991  << "\n");
992  GV.setLinkage(NewLinkage);
993  }
994  // Remove declarations from comdats, including available_externally
995  // as this is a declaration for the linker, and will be dropped eventually.
996  // It is illegal for comdats to contain declarations.
997  auto *GO = dyn_cast_or_null<GlobalObject>(&GV);
998  if (GO && GO->isDeclarationForLinker() && GO->hasComdat())
999  GO->setComdat(nullptr);
1000  };
1001 
1002  // Process functions and global now
1003  for (auto &GV : TheModule)
1004  updateLinkage(GV);
1005  for (auto &GV : TheModule.globals())
1006  updateLinkage(GV);
1007  for (auto &GV : TheModule.aliases())
1008  updateLinkage(GV);
1009 }
1010 
1011 /// Run internalization on \p TheModule based on symmary analysis.
1013  const GVSummaryMapTy &DefinedGlobals) {
1014  // Declare a callback for the internalize pass that will ask for every
1015  // candidate GlobalValue if it can be internalized or not.
1016  auto MustPreserveGV = [&](const GlobalValue &GV) -> bool {
1017  // Lookup the linkage recorded in the summaries during global analysis.
1018  auto GS = DefinedGlobals.find(GV.getGUID());
1019  if (GS == DefinedGlobals.end()) {
1020  // Must have been promoted (possibly conservatively). Find original
1021  // name so that we can access the correct summary and see if it can
1022  // be internalized again.
1023  // FIXME: Eventually we should control promotion instead of promoting
1024  // and internalizing again.
1025  StringRef OrigName =
1027  std::string OrigId = GlobalValue::getGlobalIdentifier(
1028  OrigName, GlobalValue::InternalLinkage,
1029  TheModule.getSourceFileName());
1030  GS = DefinedGlobals.find(GlobalValue::getGUID(OrigId));
1031  if (GS == DefinedGlobals.end()) {
1032  // Also check the original non-promoted non-globalized name. In some
1033  // cases a preempted weak value is linked in as a local copy because
1034  // it is referenced by an alias (IRLinker::linkGlobalValueProto).
1035  // In that case, since it was originally not a local value, it was
1036  // recorded in the index using the original name.
1037  // FIXME: This may not be needed once PR27866 is fixed.
1038  GS = DefinedGlobals.find(GlobalValue::getGUID(OrigName));
1039  assert(GS != DefinedGlobals.end());
1040  }
1041  }
1042  return !GlobalValue::isLocalLinkage(GS->second->linkage());
1043  };
1044 
1045  // FIXME: See if we can just internalize directly here via linkage changes
1046  // based on the index, rather than invoking internalizeModule.
1047  internalizeModule(TheModule, MustPreserveGV);
1048 }
1049 
1050 /// Make alias a clone of its aliasee.
1052  Function *Fn = cast<Function>(GA->getBaseObject());
1053 
1054  ValueToValueMapTy VMap;
1055  Function *NewFn = CloneFunction(Fn, VMap);
1056  // Clone should use the original alias's linkage and name, and we ensure
1057  // all uses of alias instead use the new clone (casted if necessary).
1058  NewFn->setLinkage(GA->getLinkage());
1060  NewFn->takeName(GA);
1061  return NewFn;
1062 }
1063 
1064 // Internalize values that we marked with specific attribute
1065 // in processGlobalForThinLTO.
1067  for (auto &GV : M.globals())
1068  // Skip GVs which have been converted to declarations
1069  // by dropDeadSymbols.
1070  if (!GV.isDeclaration() && GV.hasAttribute("thinlto-internalize")) {
1071  GV.setLinkage(GlobalValue::InternalLinkage);
1072  GV.setVisibility(GlobalValue::DefaultVisibility);
1073  }
1074 }
1075 
1076 // Automatically import functions in Module \p DestModule based on the summaries
1077 // index.
1079  Module &DestModule, const FunctionImporter::ImportMapTy &ImportList) {
1080  LLVM_DEBUG(dbgs() << "Starting import for Module "
1081  << DestModule.getModuleIdentifier() << "\n");
1082  unsigned ImportedCount = 0, ImportedGVCount = 0;
1083 
1084  IRMover Mover(DestModule);
1085  // Do the actual import of functions now, one Module at a time
1086  std::set<StringRef> ModuleNameOrderedList;
1087  for (auto &FunctionsToImportPerModule : ImportList) {
1088  ModuleNameOrderedList.insert(FunctionsToImportPerModule.first());
1089  }
1090  for (auto &Name : ModuleNameOrderedList) {
1091  // Get the module for the import
1092  const auto &FunctionsToImportPerModule = ImportList.find(Name);
1093  assert(FunctionsToImportPerModule != ImportList.end());
1094  Expected<std::unique_ptr<Module>> SrcModuleOrErr = ModuleLoader(Name);
1095  if (!SrcModuleOrErr)
1096  return SrcModuleOrErr.takeError();
1097  std::unique_ptr<Module> SrcModule = std::move(*SrcModuleOrErr);
1098  assert(&DestModule.getContext() == &SrcModule->getContext() &&
1099  "Context mismatch");
1100 
1101  // If modules were created with lazy metadata loading, materialize it
1102  // now, before linking it (otherwise this will be a noop).
1103  if (Error Err = SrcModule->materializeMetadata())
1104  return std::move(Err);
1105 
1106  auto &ImportGUIDs = FunctionsToImportPerModule->second;
1107  // Find the globals to import
1108  SetVector<GlobalValue *> GlobalsToImport;
1109  for (Function &F : *SrcModule) {
1110  if (!F.hasName())
1111  continue;
1112  auto GUID = F.getGUID();
1113  auto Import = ImportGUIDs.count(GUID);
1114  LLVM_DEBUG(dbgs() << (Import ? "Is" : "Not") << " importing function "
1115  << GUID << " " << F.getName() << " from "
1116  << SrcModule->getSourceFileName() << "\n");
1117  if (Import) {
1118  if (Error Err = F.materialize())
1119  return std::move(Err);
1120  if (EnableImportMetadata) {
1121  // Add 'thinlto_src_module' metadata for statistics and debugging.
1122  F.setMetadata(
1123  "thinlto_src_module",
1124  MDNode::get(DestModule.getContext(),
1125  {MDString::get(DestModule.getContext(),
1126  SrcModule->getSourceFileName())}));
1127  }
1128  GlobalsToImport.insert(&F);
1129  }
1130  }
1131  for (GlobalVariable &GV : SrcModule->globals()) {
1132  if (!GV.hasName())
1133  continue;
1134  auto GUID = GV.getGUID();
1135  auto Import = ImportGUIDs.count(GUID);
1136  LLVM_DEBUG(dbgs() << (Import ? "Is" : "Not") << " importing global "
1137  << GUID << " " << GV.getName() << " from "
1138  << SrcModule->getSourceFileName() << "\n");
1139  if (Import) {
1140  if (Error Err = GV.materialize())
1141  return std::move(Err);
1142  ImportedGVCount += GlobalsToImport.insert(&GV);
1143  }
1144  }
1145  for (GlobalAlias &GA : SrcModule->aliases()) {
1146  if (!GA.hasName())
1147  continue;
1148  auto GUID = GA.getGUID();
1149  auto Import = ImportGUIDs.count(GUID);
1150  LLVM_DEBUG(dbgs() << (Import ? "Is" : "Not") << " importing alias "
1151  << GUID << " " << GA.getName() << " from "
1152  << SrcModule->getSourceFileName() << "\n");
1153  if (Import) {
1154  if (Error Err = GA.materialize())
1155  return std::move(Err);
1156  // Import alias as a copy of its aliasee.
1157  GlobalObject *Base = GA.getBaseObject();
1158  if (Error Err = Base->materialize())
1159  return std::move(Err);
1160  auto *Fn = replaceAliasWithAliasee(SrcModule.get(), &GA);
1161  LLVM_DEBUG(dbgs() << "Is importing aliasee fn " << Base->getGUID()
1162  << " " << Base->getName() << " from "
1163  << SrcModule->getSourceFileName() << "\n");
1164  if (EnableImportMetadata) {
1165  // Add 'thinlto_src_module' metadata for statistics and debugging.
1166  Fn->setMetadata(
1167  "thinlto_src_module",
1168  MDNode::get(DestModule.getContext(),
1169  {MDString::get(DestModule.getContext(),
1170  SrcModule->getSourceFileName())}));
1171  }
1172  GlobalsToImport.insert(Fn);
1173  }
1174  }
1175 
1176  // Upgrade debug info after we're done materializing all the globals and we
1177  // have loaded all the required metadata!
1178  UpgradeDebugInfo(*SrcModule);
1179 
1180  // Link in the specified functions.
1181  if (renameModuleForThinLTO(*SrcModule, Index, &GlobalsToImport))
1182  return true;
1183 
1184  if (PrintImports) {
1185  for (const auto *GV : GlobalsToImport)
1186  dbgs() << DestModule.getSourceFileName() << ": Import " << GV->getName()
1187  << " from " << SrcModule->getSourceFileName() << "\n";
1188  }
1189 
1190  if (Mover.move(std::move(SrcModule), GlobalsToImport.getArrayRef(),
1191  [](GlobalValue &, IRMover::ValueAdder) {},
1192  /*IsPerformingImport=*/true))
1193  report_fatal_error("Function Import: link error");
1194 
1195  ImportedCount += GlobalsToImport.size();
1196  NumImportedModules++;
1197  }
1198 
1199  internalizeImmutableGVs(DestModule);
1200 
1201  NumImportedFunctions += (ImportedCount - ImportedGVCount);
1202  NumImportedGlobalVars += ImportedGVCount;
1203 
1204  LLVM_DEBUG(dbgs() << "Imported " << ImportedCount - ImportedGVCount
1205  << " functions for Module "
1206  << DestModule.getModuleIdentifier() << "\n");
1207  LLVM_DEBUG(dbgs() << "Imported " << ImportedGVCount
1208  << " global variables for Module "
1209  << DestModule.getModuleIdentifier() << "\n");
1210  return ImportedCount;
1211 }
1212 
1213 static bool doImportingForModule(Module &M) {
1214  if (SummaryFile.empty())
1215  report_fatal_error("error: -function-import requires -summary-file\n");
1218  if (!IndexPtrOrErr) {
1219  logAllUnhandledErrors(IndexPtrOrErr.takeError(), errs(),
1220  "Error loading file '" + SummaryFile + "': ");
1221  return false;
1222  }
1223  std::unique_ptr<ModuleSummaryIndex> Index = std::move(*IndexPtrOrErr);
1224 
1225  // First step is collecting the import list.
1226  FunctionImporter::ImportMapTy ImportList;
1227  // If requested, simply import all functions in the index. This is used
1228  // when testing distributed backend handling via the opt tool, when
1229  // we have distributed indexes containing exactly the summaries to import.
1230  if (ImportAllIndex)
1232  ImportList);
1233  else
1235  ImportList);
1236 
1237  // Conservatively mark all internal values as promoted. This interface is
1238  // only used when doing importing via the function importing pass. The pass
1239  // is only enabled when testing importing via the 'opt' tool, which does
1240  // not do the ThinLink that would normally determine what values to promote.
1241  for (auto &I : *Index) {
1242  for (auto &S : I.second.SummaryList) {
1243  if (GlobalValue::isLocalLinkage(S->linkage()))
1244  S->setLinkage(GlobalValue::ExternalLinkage);
1245  }
1246  }
1247 
1248  // Next we need to promote to global scope and rename any local values that
1249  // are potentially exported to other modules.
1250  if (renameModuleForThinLTO(M, *Index, nullptr)) {
1251  errs() << "Error renaming module\n";
1252  return false;
1253  }
1254 
1255  // Perform the import now.
1256  auto ModuleLoader = [&M](StringRef Identifier) {
1257  return loadFile(Identifier, M.getContext());
1258  };
1259  FunctionImporter Importer(*Index, ModuleLoader);
1260  Expected<bool> Result = Importer.importFunctions(M, ImportList);
1261 
1262  // FIXME: Probably need to propagate Errors through the pass manager.
1263  if (!Result) {
1264  logAllUnhandledErrors(Result.takeError(), errs(),
1265  "Error importing module: ");
1266  return false;
1267  }
1268 
1269  return *Result;
1270 }
1271 
1272 namespace {
1273 
1274 /// Pass that performs cross-module function import provided a summary file.
1275 class FunctionImportLegacyPass : public ModulePass {
1276 public:
1277  /// Pass identification, replacement for typeid
1278  static char ID;
1279 
1280  explicit FunctionImportLegacyPass() : ModulePass(ID) {}
1281 
1282  /// Specify pass name for debug output
1283  StringRef getPassName() const override { return "Function Importing"; }
1284 
1285  bool runOnModule(Module &M) override {
1286  if (skipModule(M))
1287  return false;
1288 
1289  return doImportingForModule(M);
1290  }
1291 };
1292 
1293 } // end anonymous namespace
1294 
1296  ModuleAnalysisManager &AM) {
1297  if (!doImportingForModule(M))
1298  return PreservedAnalyses::all();
1299 
1300  return PreservedAnalyses::none();
1301 }
1302 
1304 INITIALIZE_PASS(FunctionImportLegacyPass, "function-import",
1305  "Summary Based Function Import", false, false)
1306 
1307 namespace llvm {
1308 
1310  return new FunctionImportLegacyPass();
1311 }
1312 
1313 } // 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:336
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:645
ThreadLocalMode getThreadLocalMode() const
Definition: GlobalValue.h:254
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:492
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:373
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:65
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
Implements a dense probed hash-table based set.
Definition: DenseSet.h:249
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:116
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:155
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:320
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:221
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:244
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: CachePruning.h:22
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:1513
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: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"))
LinkageTypes getLinkage() const
Definition: GlobalValue.h:450
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:221
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:156
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:1782
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:153
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:1192
unsigned getAddressSpace() const
Definition: Globals.cpp:110
unsigned getAddressSpace() const
Return the address space of the Pointer type.
Definition: DerivedTypes.h:526
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:346
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:1213
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:496
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:159
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:210
#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)
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:841
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:202
static bool isAvailableExternallyLinkage(LinkageTypes Linkage)
Definition: GlobalValue.h:293
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:444
bool insert(MapEntryTy *KeyValue)
insert - Insert the specified key/value pair into the map.
Definition: StringMap.h:365
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:219
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:500
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:214
A raw_ostream that writes to a file descriptor.
Definition: raw_ostream.h:365
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:108
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:275
Keep one copy of named function when linking (weak)
Definition: GlobalValue.h:52
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: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:64
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:565
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:587
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:273
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:259