LLVM  9.0.0svn
ModuleSummaryAnalysis.cpp
Go to the documentation of this file.
1 //===- ModuleSummaryAnalysis.cpp - Module summary index builder -----------===//
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 pass builds a ModuleSummaryIndex object for the module, to be written
10 // to bitcode or LLVM assembly.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 #include "llvm/ADT/ArrayRef.h"
16 #include "llvm/ADT/DenseSet.h"
17 #include "llvm/ADT/MapVector.h"
18 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/ADT/SetVector.h"
20 #include "llvm/ADT/SmallPtrSet.h"
21 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/ADT/StringRef.h"
26 #include "llvm/Analysis/LoopInfo.h"
29 #include "llvm/IR/Attributes.h"
30 #include "llvm/IR/BasicBlock.h"
31 #include "llvm/IR/CallSite.h"
32 #include "llvm/IR/Constant.h"
33 #include "llvm/IR/Constants.h"
34 #include "llvm/IR/Dominators.h"
35 #include "llvm/IR/Function.h"
36 #include "llvm/IR/GlobalAlias.h"
37 #include "llvm/IR/GlobalValue.h"
38 #include "llvm/IR/GlobalVariable.h"
39 #include "llvm/IR/Instructions.h"
40 #include "llvm/IR/IntrinsicInst.h"
41 #include "llvm/IR/Intrinsics.h"
42 #include "llvm/IR/Metadata.h"
43 #include "llvm/IR/Module.h"
45 #include "llvm/IR/Use.h"
46 #include "llvm/IR/User.h"
49 #include "llvm/Pass.h"
50 #include "llvm/Support/Casting.h"
52 #include <algorithm>
53 #include <cassert>
54 #include <cstdint>
55 #include <vector>
56 
57 using namespace llvm;
58 
59 #define DEBUG_TYPE "module-summary-analysis"
60 
61 // Option to force edges cold which will block importing when the
62 // -import-cold-multiplier is set to 0. Useful for debugging.
66  "force-summary-edges-cold", cl::Hidden, cl::location(ForceSummaryEdgesCold),
67  cl::desc("Force all edges in the function summary to cold"),
70  "all-non-critical", "All non-critical edges."),
71  clEnumValN(FunctionSummary::FSHT_All, "all", "All edges.")));
72 
74  "module-summary-dot-file", cl::init(""), cl::Hidden,
75  cl::value_desc("filename"),
76  cl::desc("File to emit dot graph of new summary into."));
77 
78 // Walk through the operands of a given User via worklist iteration and populate
79 // the set of GlobalValue references encountered. Invoked either on an
80 // Instruction or a GlobalVariable (which walks its initializer).
81 // Return true if any of the operands contains blockaddress. This is important
82 // to know when computing summary for global var, because if global variable
83 // references basic block address we can't import it separately from function
84 // containing that basic block. For simplicity we currently don't import such
85 // global vars at all. When importing function we aren't interested if any
86 // instruction in it takes an address of any basic block, because instruction
87 // can only take an address of basic block located in the same function.
88 static bool findRefEdges(ModuleSummaryIndex &Index, const User *CurUser,
89  SetVector<ValueInfo> &RefEdges,
91  bool HasBlockAddress = false;
93  Worklist.push_back(CurUser);
94 
95  while (!Worklist.empty()) {
96  const User *U = Worklist.pop_back_val();
97 
98  if (!Visited.insert(U).second)
99  continue;
100 
101  ImmutableCallSite CS(U);
102 
103  for (const auto &OI : U->operands()) {
104  const User *Operand = dyn_cast<User>(OI);
105  if (!Operand)
106  continue;
107  if (isa<BlockAddress>(Operand)) {
108  HasBlockAddress = true;
109  continue;
110  }
111  if (auto *GV = dyn_cast<GlobalValue>(Operand)) {
112  // We have a reference to a global value. This should be added to
113  // the reference set unless it is a callee. Callees are handled
114  // specially by WriteFunction and are added to a separate list.
115  if (!(CS && CS.isCallee(&OI)))
116  RefEdges.insert(Index.getOrInsertValueInfo(GV));
117  continue;
118  }
119  Worklist.push_back(Operand);
120  }
121  }
122  return HasBlockAddress;
123 }
124 
126  ProfileSummaryInfo *PSI) {
127  if (!PSI)
129  if (PSI->isHotCount(ProfileCount))
131  if (PSI->isColdCount(ProfileCount))
134 }
135 
136 static bool isNonRenamableLocal(const GlobalValue &GV) {
137  return GV.hasSection() && GV.hasLocalLinkage();
138 }
139 
140 /// Determine whether this call has all constant integer arguments (excluding
141 /// "this") and summarize it to VCalls or ConstVCalls as appropriate.
145  std::vector<uint64_t> Args;
146  // Start from the second argument to skip the "this" pointer.
147  for (auto &Arg : make_range(Call.CS.arg_begin() + 1, Call.CS.arg_end())) {
148  auto *CI = dyn_cast<ConstantInt>(Arg);
149  if (!CI || CI->getBitWidth() > 64) {
150  VCalls.insert({Guid, Call.Offset});
151  return;
152  }
153  Args.push_back(CI->getZExtValue());
154  }
155  ConstVCalls.insert({{Guid, Call.Offset}, std::move(Args)});
156 }
157 
158 /// If this intrinsic call requires that we add information to the function
159 /// summary, do so via the non-constant reference arguments.
161  const CallInst *CI, SetVector<GlobalValue::GUID> &TypeTests,
162  SetVector<FunctionSummary::VFuncId> &TypeTestAssumeVCalls,
163  SetVector<FunctionSummary::VFuncId> &TypeCheckedLoadVCalls,
164  SetVector<FunctionSummary::ConstVCall> &TypeTestAssumeConstVCalls,
165  SetVector<FunctionSummary::ConstVCall> &TypeCheckedLoadConstVCalls,
166  DominatorTree &DT) {
167  switch (CI->getCalledFunction()->getIntrinsicID()) {
168  case Intrinsic::type_test: {
169  auto *TypeMDVal = cast<MetadataAsValue>(CI->getArgOperand(1));
170  auto *TypeId = dyn_cast<MDString>(TypeMDVal->getMetadata());
171  if (!TypeId)
172  break;
173  GlobalValue::GUID Guid = GlobalValue::getGUID(TypeId->getString());
174 
175  // Produce a summary from type.test intrinsics. We only summarize type.test
176  // intrinsics that are used other than by an llvm.assume intrinsic.
177  // Intrinsics that are assumed are relevant only to the devirtualization
178  // pass, not the type test lowering pass.
179  bool HasNonAssumeUses = llvm::any_of(CI->uses(), [](const Use &CIU) {
180  auto *AssumeCI = dyn_cast<CallInst>(CIU.getUser());
181  if (!AssumeCI)
182  return true;
183  Function *F = AssumeCI->getCalledFunction();
184  return !F || F->getIntrinsicID() != Intrinsic::assume;
185  });
186  if (HasNonAssumeUses)
187  TypeTests.insert(Guid);
188 
189  SmallVector<DevirtCallSite, 4> DevirtCalls;
191  findDevirtualizableCallsForTypeTest(DevirtCalls, Assumes, CI, DT);
192  for (auto &Call : DevirtCalls)
193  addVCallToSet(Call, Guid, TypeTestAssumeVCalls,
194  TypeTestAssumeConstVCalls);
195 
196  break;
197  }
198 
199  case Intrinsic::type_checked_load: {
200  auto *TypeMDVal = cast<MetadataAsValue>(CI->getArgOperand(2));
201  auto *TypeId = dyn_cast<MDString>(TypeMDVal->getMetadata());
202  if (!TypeId)
203  break;
204  GlobalValue::GUID Guid = GlobalValue::getGUID(TypeId->getString());
205 
206  SmallVector<DevirtCallSite, 4> DevirtCalls;
209  bool HasNonCallUses = false;
210  findDevirtualizableCallsForTypeCheckedLoad(DevirtCalls, LoadedPtrs, Preds,
211  HasNonCallUses, CI, DT);
212  // Any non-call uses of the result of llvm.type.checked.load will
213  // prevent us from optimizing away the llvm.type.test.
214  if (HasNonCallUses)
215  TypeTests.insert(Guid);
216  for (auto &Call : DevirtCalls)
217  addVCallToSet(Call, Guid, TypeCheckedLoadVCalls,
218  TypeCheckedLoadConstVCalls);
219 
220  break;
221  }
222  default:
223  break;
224  }
225 }
226 
227 static bool isNonVolatileLoad(const Instruction *I) {
228  if (const auto *LI = dyn_cast<LoadInst>(I))
229  return !LI->isVolatile();
230 
231  return false;
232 }
233 
235  const Function &F, BlockFrequencyInfo *BFI,
237  bool HasLocalsInUsedOrAsm,
238  DenseSet<GlobalValue::GUID> &CantBePromoted,
239  bool IsThinLTO) {
240  // Summary not currently supported for anonymous functions, they should
241  // have been named.
242  assert(F.hasName());
243 
244  unsigned NumInsts = 0;
245  // Map from callee ValueId to profile count. Used to accumulate profile
246  // counts for all static calls to a given callee.
247  MapVector<ValueInfo, CalleeInfo> CallGraphEdges;
248  SetVector<ValueInfo> RefEdges;
250  SetVector<FunctionSummary::VFuncId> TypeTestAssumeVCalls,
251  TypeCheckedLoadVCalls;
252  SetVector<FunctionSummary::ConstVCall> TypeTestAssumeConstVCalls,
253  TypeCheckedLoadConstVCalls;
254  ICallPromotionAnalysis ICallAnalysis;
256 
257  // Add personality function, prefix data and prologue data to function's ref
258  // list.
259  findRefEdges(Index, &F, RefEdges, Visited);
260  std::vector<const Instruction *> NonVolatileLoads;
261 
262  bool HasInlineAsmMaybeReferencingInternal = false;
263  for (const BasicBlock &BB : F)
264  for (const Instruction &I : BB) {
265  if (isa<DbgInfoIntrinsic>(I))
266  continue;
267  ++NumInsts;
268  if (isNonVolatileLoad(&I)) {
269  // Postpone processing of non-volatile load instructions
270  // See comments below
271  Visited.insert(&I);
272  NonVolatileLoads.push_back(&I);
273  continue;
274  }
275  findRefEdges(Index, &I, RefEdges, Visited);
276  auto CS = ImmutableCallSite(&I);
277  if (!CS)
278  continue;
279 
280  const auto *CI = dyn_cast<CallInst>(&I);
281  // Since we don't know exactly which local values are referenced in inline
282  // assembly, conservatively mark the function as possibly referencing
283  // a local value from inline assembly to ensure we don't export a
284  // reference (which would require renaming and promotion of the
285  // referenced value).
286  if (HasLocalsInUsedOrAsm && CI && CI->isInlineAsm())
287  HasInlineAsmMaybeReferencingInternal = true;
288 
289  auto *CalledValue = CS.getCalledValue();
290  auto *CalledFunction = CS.getCalledFunction();
291  if (CalledValue && !CalledFunction) {
292  CalledValue = CalledValue->stripPointerCastsNoFollowAliases();
293  // Stripping pointer casts can reveal a called function.
294  CalledFunction = dyn_cast<Function>(CalledValue);
295  }
296  // Check if this is an alias to a function. If so, get the
297  // called aliasee for the checks below.
298  if (auto *GA = dyn_cast<GlobalAlias>(CalledValue)) {
299  assert(!CalledFunction && "Expected null called function in callsite for alias");
300  CalledFunction = dyn_cast<Function>(GA->getBaseObject());
301  }
302  // Check if this is a direct call to a known function or a known
303  // intrinsic, or an indirect call with profile data.
304  if (CalledFunction) {
305  if (CI && CalledFunction->isIntrinsic()) {
307  CI, TypeTests, TypeTestAssumeVCalls, TypeCheckedLoadVCalls,
308  TypeTestAssumeConstVCalls, TypeCheckedLoadConstVCalls, DT);
309  continue;
310  }
311  // We should have named any anonymous globals
312  assert(CalledFunction->hasName());
313  auto ScaledCount = PSI->getProfileCount(&I, BFI);
314  auto Hotness = ScaledCount ? getHotness(ScaledCount.getValue(), PSI)
318 
319  // Use the original CalledValue, in case it was an alias. We want
320  // to record the call edge to the alias in that case. Eventually
321  // an alias summary will be created to associate the alias and
322  // aliasee.
323  auto &ValueInfo = CallGraphEdges[Index.getOrInsertValueInfo(
324  cast<GlobalValue>(CalledValue))];
325  ValueInfo.updateHotness(Hotness);
326  // Add the relative block frequency to CalleeInfo if there is no profile
327  // information.
328  if (BFI != nullptr && Hotness == CalleeInfo::HotnessType::Unknown) {
329  uint64_t BBFreq = BFI->getBlockFreq(&BB).getFrequency();
330  uint64_t EntryFreq = BFI->getEntryFreq();
331  ValueInfo.updateRelBlockFreq(BBFreq, EntryFreq);
332  }
333  } else {
334  // Skip inline assembly calls.
335  if (CI && CI->isInlineAsm())
336  continue;
337  // Skip direct calls.
338  if (!CalledValue || isa<Constant>(CalledValue))
339  continue;
340 
341  // Check if the instruction has a callees metadata. If so, add callees
342  // to CallGraphEdges to reflect the references from the metadata, and
343  // to enable importing for subsequent indirect call promotion and
344  // inlining.
345  if (auto *MD = I.getMetadata(LLVMContext::MD_callees)) {
346  for (auto &Op : MD->operands()) {
347  Function *Callee = mdconst::extract_or_null<Function>(Op);
348  if (Callee)
349  CallGraphEdges[Index.getOrInsertValueInfo(Callee)];
350  }
351  }
352 
353  uint32_t NumVals, NumCandidates;
354  uint64_t TotalCount;
355  auto CandidateProfileData =
357  &I, NumVals, TotalCount, NumCandidates);
358  for (auto &Candidate : CandidateProfileData)
359  CallGraphEdges[Index.getOrInsertValueInfo(Candidate.Value)]
360  .updateHotness(getHotness(Candidate.Count, PSI));
361  }
362  }
363 
364  // By now we processed all instructions in a function, except
365  // non-volatile loads. All new refs we add in a loop below
366  // are obviously constant. All constant refs are grouped in the
367  // end of RefEdges vector, so we can use a single integer value
368  // to identify them.
369  unsigned RefCnt = RefEdges.size();
370  for (const Instruction *I : NonVolatileLoads) {
371  Visited.erase(I);
372  findRefEdges(Index, I, RefEdges, Visited);
373  }
374  std::vector<ValueInfo> Refs = RefEdges.takeVector();
375  // Regular LTO module doesn't participate in ThinLTO import,
376  // so no reference from it can be readonly, since this would
377  // require importing variable as local copy
378  if (IsThinLTO)
379  for (; RefCnt < Refs.size(); ++RefCnt)
380  Refs[RefCnt].setReadOnly();
381 
382  // Explicit add hot edges to enforce importing for designated GUIDs for
383  // sample PGO, to enable the same inlines as the profiled optimized binary.
384  for (auto &I : F.getImportGUIDs())
385  CallGraphEdges[Index.getOrInsertValueInfo(I)].updateHotness(
389 
390  bool NonRenamableLocal = isNonRenamableLocal(F);
391  bool NotEligibleForImport =
392  NonRenamableLocal || HasInlineAsmMaybeReferencingInternal;
393  GlobalValueSummary::GVFlags Flags(F.getLinkage(), NotEligibleForImport,
394  /* Live = */ false, F.isDSOLocal(),
395  F.hasLinkOnceODRLinkage() && F.hasGlobalUnnamedAddr());
396  FunctionSummary::FFlags FunFlags{
397  F.hasFnAttribute(Attribute::ReadNone),
398  F.hasFnAttribute(Attribute::ReadOnly),
399  F.hasFnAttribute(Attribute::NoRecurse), F.returnDoesNotAlias(),
400  // FIXME: refactor this to use the same code that inliner is using.
401  // Don't try to import functions with noinline attribute.
402  F.getAttributes().hasFnAttribute(Attribute::NoInline)};
403  auto FuncSummary = llvm::make_unique<FunctionSummary>(
404  Flags, NumInsts, FunFlags, /*EntryCount=*/0, std::move(Refs),
405  CallGraphEdges.takeVector(), TypeTests.takeVector(),
406  TypeTestAssumeVCalls.takeVector(), TypeCheckedLoadVCalls.takeVector(),
407  TypeTestAssumeConstVCalls.takeVector(),
408  TypeCheckedLoadConstVCalls.takeVector());
409  if (NonRenamableLocal)
410  CantBePromoted.insert(F.getGUID());
411  Index.addGlobalValueSummary(F, std::move(FuncSummary));
412 }
413 
414 static void
416  DenseSet<GlobalValue::GUID> &CantBePromoted) {
417  SetVector<ValueInfo> RefEdges;
419  bool HasBlockAddress = findRefEdges(Index, &V, RefEdges, Visited);
420  bool NonRenamableLocal = isNonRenamableLocal(V);
421  GlobalValueSummary::GVFlags Flags(V.getLinkage(), NonRenamableLocal,
422  /* Live = */ false, V.isDSOLocal(),
424 
425  // Don't mark variables we won't be able to internalize as read-only.
427  !V.hasComdat() && !V.hasAppendingLinkage() && !V.isInterposable() &&
429  auto GVarSummary = llvm::make_unique<GlobalVarSummary>(Flags, VarFlags,
430  RefEdges.takeVector());
431  if (NonRenamableLocal)
432  CantBePromoted.insert(V.getGUID());
433  if (HasBlockAddress)
434  GVarSummary->setNotEligibleToImport();
435  Index.addGlobalValueSummary(V, std::move(GVarSummary));
436 }
437 
438 static void
440  DenseSet<GlobalValue::GUID> &CantBePromoted) {
441  bool NonRenamableLocal = isNonRenamableLocal(A);
442  GlobalValueSummary::GVFlags Flags(A.getLinkage(), NonRenamableLocal,
443  /* Live = */ false, A.isDSOLocal(),
445  auto AS = llvm::make_unique<AliasSummary>(Flags);
446  auto *Aliasee = A.getBaseObject();
447  auto AliaseeVI = Index.getValueInfo(Aliasee->getGUID());
448  assert(AliaseeVI && "Alias expects aliasee summary to be available");
449  assert(AliaseeVI.getSummaryList().size() == 1 &&
450  "Expected a single entry per aliasee in per-module index");
451  AS->setAliasee(AliaseeVI, AliaseeVI.getSummaryList()[0].get());
452  if (NonRenamableLocal)
453  CantBePromoted.insert(A.getGUID());
454  Index.addGlobalValueSummary(A, std::move(AS));
455 }
456 
457 // Set LiveRoot flag on entries matching the given value name.
459  if (ValueInfo VI = Index.getValueInfo(GlobalValue::getGUID(Name)))
460  for (auto &Summary : VI.getSummaryList())
461  Summary->setLive(true);
462 }
463 
465  const Module &M,
466  std::function<BlockFrequencyInfo *(const Function &F)> GetBFICallback,
467  ProfileSummaryInfo *PSI) {
468  assert(PSI);
469  bool EnableSplitLTOUnit = false;
470  if (auto *MD = mdconst::extract_or_null<ConstantInt>(
471  M.getModuleFlag("EnableSplitLTOUnit")))
472  EnableSplitLTOUnit = MD->getZExtValue();
473  ModuleSummaryIndex Index(/*HaveGVs=*/true, EnableSplitLTOUnit);
474 
475  // Identify the local values in the llvm.used and llvm.compiler.used sets,
476  // which should not be exported as they would then require renaming and
477  // promotion, but we may have opaque uses e.g. in inline asm. We collect them
478  // here because we use this information to mark functions containing inline
479  // assembly calls as not importable.
482  // First collect those in the llvm.used set.
483  collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ false);
484  // Next collect those in the llvm.compiler.used set.
485  collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ true);
486  DenseSet<GlobalValue::GUID> CantBePromoted;
487  for (auto *V : Used) {
488  if (V->hasLocalLinkage()) {
489  LocalsUsed.insert(V);
490  CantBePromoted.insert(V->getGUID());
491  }
492  }
493 
494  bool HasLocalInlineAsmSymbol = false;
495  if (!M.getModuleInlineAsm().empty()) {
496  // Collect the local values defined by module level asm, and set up
497  // summaries for these symbols so that they can be marked as NoRename,
498  // to prevent export of any use of them in regular IR that would require
499  // renaming within the module level asm. Note we don't need to create a
500  // summary for weak or global defs, as they don't need to be flagged as
501  // NoRename, and defs in module level asm can't be imported anyway.
502  // Also, any values used but not defined within module level asm should
503  // be listed on the llvm.used or llvm.compiler.used global and marked as
504  // referenced from there.
507  // Symbols not marked as Weak or Global are local definitions.
508  if (Flags & (object::BasicSymbolRef::SF_Weak |
510  return;
511  HasLocalInlineAsmSymbol = true;
512  GlobalValue *GV = M.getNamedValue(Name);
513  if (!GV)
514  return;
515  assert(GV->isDeclaration() && "Def in module asm already has definition");
517  /* NotEligibleToImport = */ true,
518  /* Live = */ true,
519  /* Local */ GV->isDSOLocal(),
521  CantBePromoted.insert(GV->getGUID());
522  // Create the appropriate summary type.
523  if (Function *F = dyn_cast<Function>(GV)) {
524  std::unique_ptr<FunctionSummary> Summary =
525  llvm::make_unique<FunctionSummary>(
526  GVFlags, /*InstCount=*/0,
528  F->hasFnAttribute(Attribute::ReadNone),
529  F->hasFnAttribute(Attribute::ReadOnly),
530  F->hasFnAttribute(Attribute::NoRecurse),
531  F->returnDoesNotAlias(),
532  /* NoInline = */ false},
533  /*EntryCount=*/0, ArrayRef<ValueInfo>{},
540  Index.addGlobalValueSummary(*GV, std::move(Summary));
541  } else {
542  std::unique_ptr<GlobalVarSummary> Summary =
543  llvm::make_unique<GlobalVarSummary>(
544  GVFlags, GlobalVarSummary::GVarFlags(),
546  Index.addGlobalValueSummary(*GV, std::move(Summary));
547  }
548  });
549  }
550 
551  bool IsThinLTO = true;
552  if (auto *MD =
553  mdconst::extract_or_null<ConstantInt>(M.getModuleFlag("ThinLTO")))
554  IsThinLTO = MD->getZExtValue();
555 
556  // Compute summaries for all functions defined in module, and save in the
557  // index.
558  for (auto &F : M) {
559  if (F.isDeclaration())
560  continue;
561 
562  DominatorTree DT(const_cast<Function &>(F));
563  BlockFrequencyInfo *BFI = nullptr;
564  std::unique_ptr<BlockFrequencyInfo> BFIPtr;
565  if (GetBFICallback)
566  BFI = GetBFICallback(F);
567  else if (F.hasProfileData()) {
568  LoopInfo LI{DT};
569  BranchProbabilityInfo BPI{F, LI};
570  BFIPtr = llvm::make_unique<BlockFrequencyInfo>(F, BPI, LI);
571  BFI = BFIPtr.get();
572  }
573 
574  computeFunctionSummary(Index, M, F, BFI, PSI, DT,
575  !LocalsUsed.empty() || HasLocalInlineAsmSymbol,
576  CantBePromoted, IsThinLTO);
577  }
578 
579  // Compute summaries for all variables defined in module, and save in the
580  // index.
581  for (const GlobalVariable &G : M.globals()) {
582  if (G.isDeclaration())
583  continue;
584  computeVariableSummary(Index, G, CantBePromoted);
585  }
586 
587  // Compute summaries for all aliases defined in module, and save in the
588  // index.
589  for (const GlobalAlias &A : M.aliases())
590  computeAliasSummary(Index, A, CantBePromoted);
591 
592  for (auto *V : LocalsUsed) {
593  auto *Summary = Index.getGlobalValueSummary(*V);
594  assert(Summary && "Missing summary for global value");
595  Summary->setNotEligibleToImport();
596  }
597 
598  // The linker doesn't know about these LLVM produced values, so we need
599  // to flag them as live in the index to ensure index-based dead value
600  // analysis treats them as live roots of the analysis.
601  setLiveRoot(Index, "llvm.used");
602  setLiveRoot(Index, "llvm.compiler.used");
603  setLiveRoot(Index, "llvm.global_ctors");
604  setLiveRoot(Index, "llvm.global_dtors");
605  setLiveRoot(Index, "llvm.global.annotations");
606 
607  for (auto &GlobalList : Index) {
608  // Ignore entries for references that are undefined in the current module.
609  if (GlobalList.second.SummaryList.empty())
610  continue;
611 
612  assert(GlobalList.second.SummaryList.size() == 1 &&
613  "Expected module's index to have one summary per GUID");
614  auto &Summary = GlobalList.second.SummaryList[0];
615  if (!IsThinLTO) {
616  Summary->setNotEligibleToImport();
617  continue;
618  }
619 
620  bool AllRefsCanBeExternallyReferenced =
621  llvm::all_of(Summary->refs(), [&](const ValueInfo &VI) {
622  return !CantBePromoted.count(VI.getGUID());
623  });
624  if (!AllRefsCanBeExternallyReferenced) {
625  Summary->setNotEligibleToImport();
626  continue;
627  }
628 
629  if (auto *FuncSummary = dyn_cast<FunctionSummary>(Summary.get())) {
630  bool AllCallsCanBeExternallyReferenced = llvm::all_of(
631  FuncSummary->calls(), [&](const FunctionSummary::EdgeTy &Edge) {
632  return !CantBePromoted.count(Edge.first.getGUID());
633  });
634  if (!AllCallsCanBeExternallyReferenced)
635  Summary->setNotEligibleToImport();
636  }
637  }
638 
639  if (!ModuleSummaryDotFile.empty()) {
640  std::error_code EC;
642  if (EC)
643  report_fatal_error(Twine("Failed to open dot file ") +
644  ModuleSummaryDotFile + ": " + EC.message() + "\n");
645  Index.exportToDot(OSDot);
646  }
647 
648  return Index;
649 }
650 
651 AnalysisKey ModuleSummaryIndexAnalysis::Key;
652 
656  auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
658  M,
659  [&FAM](const Function &F) {
660  return &FAM.getResult<BlockFrequencyAnalysis>(
661  *const_cast<Function *>(&F));
662  },
663  &PSI);
664 }
665 
667 
668 INITIALIZE_PASS_BEGIN(ModuleSummaryIndexWrapperPass, "module-summary-analysis",
669  "Module Summary Analysis", false, true)
673  "Module Summary Analysis", false, true)
674 
676  return new ModuleSummaryIndexWrapperPass();
677 }
678 
680  : ModulePass(ID) {
682 }
683 
685  auto *PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
686  Index.emplace(buildModuleSummaryIndex(
687  M,
688  [this](const Function &F) {
689  return &(this->getAnalysis<BlockFrequencyInfoWrapperPass>(
690  *const_cast<Function *>(&F))
691  .getBFI());
692  },
693  PSI));
694  return false;
695 }
696 
698  Index.reset();
699  return false;
700 }
701 
703  AU.setPreservesAll();
706 }
ArrayRef< InstrProfValueData > getPromotionCandidatesForInstruction(const Instruction *I, uint32_t &NumVals, uint64_t &TotalCount, uint32_t &NumCandidates)
Returns reference to array of InstrProfValueData for the given instruction I.
IterTy arg_end() const
Definition: CallSite.h:583
const GlobalObject * getBaseObject() const
bool hasDLLExportStorageClass() const
Definition: GlobalValue.h:264
iterator_range< use_iterator > uses()
Definition: Value.h:354
bool hasLocalLinkage() const
Definition: GlobalValue.h:435
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:776
uint64_t GUID
Declare a type to represent a global unique identifier for a global value.
Definition: GlobalValue.h:492
IterTy arg_begin() const
Definition: CallSite.h:579
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
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
amdgpu Simplify well known AMD library false FunctionCallee Value const Twine & Name
GlobalValueSummary * getGlobalValueSummary(const GlobalValue &GV, bool PerModuleIndex=true) const
Returns the first GlobalValueSummary for GV, asserting that there is only one if PerModuleIndex.
void findDevirtualizableCallsForTypeTest(SmallVectorImpl< DevirtCallSite > &DevirtCalls, SmallVectorImpl< CallInst *> &Assumes, const CallInst *CI, DominatorTree &DT)
Given a call to the intrinsic @llvm.type.test, find all devirtualizable call sites based on the call ...
CallSite CS
The call site itself.
This is the interface to build a ModuleSummaryIndex for a module.
Implements a dense probed hash-table based set.
Definition: DenseSet.h:249
bool isColdCount(uint64_t C)
Returns true if count C is considered cold.
Analysis providing profile information.
This class represents a function call, abstracting a target machine&#39;s calling convention.
bool hasAvailableExternallyLinkage() const
Definition: GlobalValue.h:422
This file contains the declarations for metadata subclasses.
uint64_t getFrequency() const
Returns the frequency as a fixpoint number scaled by the entry frequency.
uint64_t Offset
The offset from the address point to the virtual function.
bool isInterposable() const
Return true if this global&#39;s definition can be substituted with an arbitrary definition at link time...
Definition: GlobalValue.h:419
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
Definition: Function.h:323
This class implements a map that also provides access to all stored values in a deterministic order...
Definition: MapVector.h:37
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1185
F(f)
void initializeModuleSummaryIndexWrapperPassPass(PassRegistry &)
block Block Frequency true
This defines the Use class.
bool isHotCount(uint64_t C)
Returns true if count C is considered hot.
ModuleSummaryIndex buildModuleSummaryIndex(const Module &M, std::function< BlockFrequencyInfo *(const Function &F)> GetBFICallback, ProfileSummaryInfo *PSI)
Direct function to compute a ModuleSummaryIndex from a given module.
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1218
void findDevirtualizableCallsForTypeCheckedLoad(SmallVectorImpl< DevirtCallSite > &DevirtCalls, SmallVectorImpl< Instruction *> &LoadedPtrs, SmallVectorImpl< Instruction *> &Preds, bool &HasNonCallUses, const CallInst *CI, DominatorTree &DT)
Given a call to the intrinsic @llvm.type.checked.load, find all devirtualizable call sites based on t...
bool hasSection() const
Definition: GlobalValue.h:269
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:80
An analysis pass based on legacy pass manager to deliver ProfileSummaryInfo.
bool isDSOLocal() const
Definition: GlobalValue.h:279
static AnalysisKey * ID()
Returns an opaque, unique ID for this analysis type.
Definition: PassManager.h:405
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
This file contains the simple types necessary to represent the attributes associated with functions a...
Legacy analysis pass which computes BlockFrequencyInfo.
static void CollectAsmSymbols(const Module &M, function_ref< void(StringRef, object::BasicSymbolRef::Flags)> AsmSymbol)
Parse inline ASM and collect the symbols that are defined or referenced in the current module...
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
std::pair< ValueInfo, CalleeInfo > EdgeTy
<CalleeValueInfo, CalleeInfo> call edge pair.
GlobalValue * getNamedValue(StringRef Name) const
Return the global value in the module with the specified name, of arbitrary type. ...
Definition: Module.cpp:113
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
module summary analysis
LinkageTypes getLinkage() const
Definition: GlobalValue.h:450
Class to hold module path string table and global value map, and encapsulate methods for operating on...
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
bool doFinalization(Module &M) override
doFinalization - Virtual method overriden by subclasses to do any necessary clean up after all passes...
bool hasAppendingLinkage() const
Definition: GlobalValue.h:432
static void computeAliasSummary(ModuleSummaryIndex &Index, const GlobalAlias &A, DenseSet< GlobalValue::GUID > &CantBePromoted)
Interface to identify indirect call promotion candidates.
ForceSummaryHotnessType
Types for -force-summary-edges-cold debugging option.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
bool hasLinkOnceODRLinkage() const
Definition: GlobalValue.h:426
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
bool hasName() const
Definition: Value.h:250
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
A call site that could be devirtualized.
Metadata * getModuleFlag(StringRef Key) const
Return the corresponding value if Key appears in module flags, otherwise return null.
Definition: Module.cpp:310
An analysis pass based on the new PM to deliver ProfileSummaryInfo.
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
Definition: CommandLine.h:652
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:91
bool returnDoesNotAlias() const
Determine if the parameter or return value is marked with NoAlias attribute.
Definition: Function.h:588
This file contains the declarations for the subclasses of Constant, which represent the different fla...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:370
Represent the analysis usage information of a pass.
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
INITIALIZE_PASS_BEGIN(ModuleSummaryIndexWrapperPass, "module-summary-analysis", "Module Summary Analysis", false, true) INITIALIZE_PASS_END(ModuleSummaryIndexWrapperPass
static void addIntrinsicToSummary(const CallInst *CI, SetVector< GlobalValue::GUID > &TypeTests, SetVector< FunctionSummary::VFuncId > &TypeTestAssumeVCalls, SetVector< FunctionSummary::VFuncId > &TypeCheckedLoadVCalls, SetVector< FunctionSummary::ConstVCall > &TypeTestAssumeConstVCalls, SetVector< FunctionSummary::ConstVCall > &TypeCheckedLoadConstVCalls, DominatorTree &DT)
If this intrinsic call requires that we add information to the function summary, do so via the non-co...
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
op_range operands()
Definition: User.h:237
bool hasProfileData(bool IncludeSynthetic=false) const
Return true if the function is annotated with profile data.
Definition: Function.h:308
static GUID getGUID(StringRef GlobalName)
Return a 64-bit global unique ID constructed from global value name (i.e.
Definition: GlobalValue.h:496
static void addVCallToSet(DevirtCallSite Call, GlobalValue::GUID Guid, SetVector< FunctionSummary::VFuncId > &VCalls, SetVector< FunctionSummary::ConstVCall > &ConstVCalls)
Determine whether this call has all constant integer arguments (excluding "this") and summarize it to...
static void computeVariableSummary(ModuleSummaryIndex &Index, const GlobalVariable &V, DenseSet< GlobalValue::GUID > &CantBePromoted)
Class to represent profile counts.
Definition: Function.h:260
VectorType takeVector()
Clear the MapVector and return the underlying vector.
Definition: MapVector.h:55
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
Optional< uint64_t > getProfileCount(const Instruction *CallInst, BlockFrequencyInfo *BFI, bool AllowSynthetic=false)
Returns the profile count for CallInst.
Struct that holds a reference to a particular GUID in a global value summary.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
static bool isNonRenamableLocal(const GlobalValue &GV)
GlobalVariable * collectUsedGlobalVariables(const Module &M, SmallPtrSetImpl< GlobalValue *> &Set, bool CompilerUsed)
Given "llvm.used" or "llvm.compiler.used" as a global name, collect the initializer elements of that ...
Definition: Module.cpp:598
Analysis pass which computes BlockFrequencyInfo.
Vector takeVector()
Clear the SetVector and return the underlying vector.
Definition: SetVector.h:66
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false...
Definition: SmallPtrSet.h:377
static bool findRefEdges(ModuleSummaryIndex &Index, const User *CurUser, SetVector< ValueInfo > &RefEdges, SmallPtrSet< const User *, 8 > &Visited)
cl::opt< std::string > ModuleSummaryDotFile("module-summary-dot-file", cl::init(""), cl::Hidden, cl::value_desc("filename"), cl::desc("File to emit dot graph of new summary into."))
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.
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:374
static void computeFunctionSummary(ModuleSummaryIndex &Index, const Module &M, const Function &F, BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI, DominatorTree &DT, bool HasLocalsInUsedOrAsm, DenseSet< GlobalValue::GUID > &CantBePromoted, bool IsThinLTO)
bool hasGlobalUnnamedAddr() const
Definition: GlobalValue.h:199
Intrinsic::ID getIntrinsicID() const LLVM_READONLY
getIntrinsicID - This method returns the ID number of the specified function, or Intrinsic::not_intri...
Definition: Function.h:193
BlockFrequency getBlockFreq(const BasicBlock *BB) const
getblockFreq - Return block frequency.
Result run(Module &M, ModuleAnalysisManager &AM)
amdgpu Simplify well known AMD library false FunctionCallee Callee
void setPreservesAll()
Set by analyses that do not transform their input at all.
GUID getGUID() const
Return a 64-bit global unique ID constructed from global value name (i.e.
Definition: GlobalValue.h:500
ValueInfo getValueInfo(const GlobalValueSummaryMapTy::value_type &R) const
Return a ValueInfo for the index value_type (convenient when iterating index).
bool hasComdat() const
Definition: GlobalObject.h:99
ValueInfo getOrInsertValueInfo(GlobalValue::GUID GUID)
Return a ValueInfo for GUID.
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
Definition: CommandLine.h:627
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Analysis providing branch probability information.
A raw_ostream that writes to a file descriptor.
Definition: raw_ostream.h:365
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
void addGlobalValueSummary(const GlobalValue &GV, std::unique_ptr< GlobalValueSummary > Summary)
Add a global value summary for a value.
Establish a view to a call site for examination.
Definition: CallSite.h:892
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation.
Definition: InstrTypes.h:1264
#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
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
Rename collisions when linking (static functions).
Definition: GlobalValue.h:55
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:91
Flags specific to function summaries.
static bool isNonVolatileLoad(const Instruction *I)
FunctionSummary::ForceSummaryHotnessType ForceSummaryEdgesCold
cl::opt< FunctionSummary::ForceSummaryHotnessType, true > FSEC("force-summary-edges-cold", cl::Hidden, cl::location(ForceSummaryEdgesCold), cl::desc("Force all edges in the function summary to cold"), cl::values(clEnumValN(FunctionSummary::FSHT_None, "none", "None."), clEnumValN(FunctionSummary::FSHT_AllNonCritical, "all-non-critical", "All non-critical edges."), clEnumValN(FunctionSummary::FSHT_All, "all", "All edges.")))
const std::string & getModuleInlineAsm() const
Get any module-scope inline assembly blocks.
Definition: Module.h:248
bool isDeclaration() const
Return true if the primary definition of this global value is outside of the current translation unit...
Definition: Globals.cpp:205
bool isCallee(Value::const_user_iterator UI) const
Determine whether the passed iterator points to the callee operand&#39;s Use.
Definition: CallSite.h:150
ModuleSummaryIndex.h This file contains the declarations the classes that hold the module index and s...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
ModulePass * createModuleSummaryIndexWrapperPass()
A vector that has set insertion semantics.
Definition: SetVector.h:40
bool runOnModule(Module &M) override
runOnModule - Virtual method overriden by subclasses to process the module being operated on...
static void setLiveRoot(ModuleSummaryIndex &Index, StringRef Name)
Group flags (Linkage, NotEligibleToImport, etc.) as a bitfield.
print Print MemDeps of function
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
A single uniqued string.
Definition: Metadata.h:603
A container for analyses that lazily runs them and caches their results.
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:70
LocationClass< Ty > location(Ty &L)
Definition: CommandLine.h:448
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
static CalleeInfo::HotnessType getHotness(uint64_t ProfileCount, ProfileSummaryInfo *PSI)
Legacy wrapper pass to provide the ModuleSummaryIndex object.
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:1044