LLVM  6.0.0svn
Inliner.cpp
Go to the documentation of this file.
1 //===- Inliner.cpp - Code common to all inliners --------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements the mechanics required to implement inlining without
11 // missing any calls and updating the call graph. The decisions of which calls
12 // are profitable to inline are implemented elsewhere.
13 //
14 //===----------------------------------------------------------------------===//
15 
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/Statistic.h"
28 #include "llvm/IR/CallSite.h"
29 #include "llvm/IR/DataLayout.h"
30 #include "llvm/IR/DiagnosticInfo.h"
31 #include "llvm/IR/InstIterator.h"
32 #include "llvm/IR/Instructions.h"
33 #include "llvm/IR/IntrinsicInst.h"
34 #include "llvm/IR/Module.h"
35 #include "llvm/Support/Debug.h"
40 using namespace llvm;
41 
42 #define DEBUG_TYPE "inline"
43 
44 STATISTIC(NumInlined, "Number of functions inlined");
45 STATISTIC(NumCallsDeleted, "Number of call sites deleted, not inlined");
46 STATISTIC(NumDeleted, "Number of functions deleted because all callers found");
47 STATISTIC(NumMergedAllocas, "Number of allocas merged together");
48 
49 // This weirdly named statistic tracks the number of times that, when attempting
50 // to inline a function A into B, we analyze the callers of B in order to see
51 // if those would be more profitable and blocked inline steps.
52 STATISTIC(NumCallerCallersAnalyzed, "Number of caller-callers analyzed");
53 
54 /// Flag to disable manual alloca merging.
55 ///
56 /// Merging of allocas was originally done as a stack-size saving technique
57 /// prior to LLVM's code generator having support for stack coloring based on
58 /// lifetime markers. It is now in the process of being removed. To experiment
59 /// with disabling it and relying fully on lifetime marker based stack
60 /// coloring, you can pass this flag to LLVM.
61 static cl::opt<bool>
62  DisableInlinedAllocaMerging("disable-inlined-alloca-merging",
63  cl::init(false), cl::Hidden);
64 
65 namespace {
67  No = 0,
68  Basic = 1,
69  Verbose = 2,
70 };
71 
72 cl::opt<InlinerFunctionImportStatsOpts> InlinerFunctionImportStats(
73  "inliner-function-import-stats",
74  cl::init(InlinerFunctionImportStatsOpts::No),
76  "basic statistics"),
77  clEnumValN(InlinerFunctionImportStatsOpts::Verbose, "verbose",
78  "printing of statistics for each inlined function")),
79  cl::Hidden, cl::desc("Enable inliner stats for imported functions"));
80 } // namespace
81 
83  : CallGraphSCCPass(ID), InsertLifetime(true) {}
84 
85 LegacyInlinerBase::LegacyInlinerBase(char &ID, bool InsertLifetime)
86  : CallGraphSCCPass(ID), InsertLifetime(InsertLifetime) {}
87 
88 /// For this class, we declare that we require and preserve the call graph.
89 /// If the derived class implements this method, it should
90 /// always explicitly call the implementation here.
97 }
98 
100 
101 /// Look at all of the allocas that we inlined through this call site. If we
102 /// have already inlined other allocas through other calls into this function,
103 /// then we know that they have disjoint lifetimes and that we can merge them.
104 ///
105 /// There are many heuristics possible for merging these allocas, and the
106 /// different options have different tradeoffs. One thing that we *really*
107 /// don't want to hurt is SRoA: once inlining happens, often allocas are no
108 /// longer address taken and so they can be promoted.
109 ///
110 /// Our "solution" for that is to only merge allocas whose outermost type is an
111 /// array type. These are usually not promoted because someone is using a
112 /// variable index into them. These are also often the most important ones to
113 /// merge.
114 ///
115 /// A better solution would be to have real memory lifetime markers in the IR
116 /// and not have the inliner do any merging of allocas at all. This would
117 /// allow the backend to do proper stack slot coloring of all allocas that
118 /// *actually make it to the backend*, which is really what we want.
119 ///
120 /// Because we don't have this information, we do this simple and useful hack.
122  Function *Caller, InlineFunctionInfo &IFI,
123  InlinedArrayAllocasTy &InlinedArrayAllocas, int InlineHistory) {
124  SmallPtrSet<AllocaInst *, 16> UsedAllocas;
125 
126  // When processing our SCC, check to see if CS was inlined from some other
127  // call site. For example, if we're processing "A" in this code:
128  // A() { B() }
129  // B() { x = alloca ... C() }
130  // C() { y = alloca ... }
131  // Assume that C was not inlined into B initially, and so we're processing A
132  // and decide to inline B into A. Doing this makes an alloca available for
133  // reuse and makes a callsite (C) available for inlining. When we process
134  // the C call site we don't want to do any alloca merging between X and Y
135  // because their scopes are not disjoint. We could make this smarter by
136  // keeping track of the inline history for each alloca in the
137  // InlinedArrayAllocas but this isn't likely to be a significant win.
138  if (InlineHistory != -1) // Only do merging for top-level call sites in SCC.
139  return;
140 
141  // Loop over all the allocas we have so far and see if they can be merged with
142  // a previously inlined alloca. If not, remember that we had it.
143  for (unsigned AllocaNo = 0, e = IFI.StaticAllocas.size(); AllocaNo != e;
144  ++AllocaNo) {
145  AllocaInst *AI = IFI.StaticAllocas[AllocaNo];
146 
147  // Don't bother trying to merge array allocations (they will usually be
148  // canonicalized to be an allocation *of* an array), or allocations whose
149  // type is not itself an array (because we're afraid of pessimizing SRoA).
151  if (!ATy || AI->isArrayAllocation())
152  continue;
153 
154  // Get the list of all available allocas for this array type.
155  std::vector<AllocaInst *> &AllocasForType = InlinedArrayAllocas[ATy];
156 
157  // Loop over the allocas in AllocasForType to see if we can reuse one. Note
158  // that we have to be careful not to reuse the same "available" alloca for
159  // multiple different allocas that we just inlined, we use the 'UsedAllocas'
160  // set to keep track of which "available" allocas are being used by this
161  // function. Also, AllocasForType can be empty of course!
162  bool MergedAwayAlloca = false;
163  for (AllocaInst *AvailableAlloca : AllocasForType) {
164 
165  unsigned Align1 = AI->getAlignment(),
166  Align2 = AvailableAlloca->getAlignment();
167 
168  // The available alloca has to be in the right function, not in some other
169  // function in this SCC.
170  if (AvailableAlloca->getParent() != AI->getParent())
171  continue;
172 
173  // If the inlined function already uses this alloca then we can't reuse
174  // it.
175  if (!UsedAllocas.insert(AvailableAlloca).second)
176  continue;
177 
178  // Otherwise, we *can* reuse it, RAUW AI into AvailableAlloca and declare
179  // success!
180  DEBUG(dbgs() << " ***MERGED ALLOCA: " << *AI
181  << "\n\t\tINTO: " << *AvailableAlloca << '\n');
182 
183  // Move affected dbg.declare calls immediately after the new alloca to
184  // avoid the situation when a dbg.declare precedes its alloca.
185  if (auto *L = LocalAsMetadata::getIfExists(AI))
186  if (auto *MDV = MetadataAsValue::getIfExists(AI->getContext(), L))
187  for (User *U : MDV->users())
188  if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(U))
189  DDI->moveBefore(AvailableAlloca->getNextNode());
190 
191  AI->replaceAllUsesWith(AvailableAlloca);
192 
193  if (Align1 != Align2) {
194  if (!Align1 || !Align2) {
195  const DataLayout &DL = Caller->getParent()->getDataLayout();
196  unsigned TypeAlign = DL.getABITypeAlignment(AI->getAllocatedType());
197 
198  Align1 = Align1 ? Align1 : TypeAlign;
199  Align2 = Align2 ? Align2 : TypeAlign;
200  }
201 
202  if (Align1 > Align2)
203  AvailableAlloca->setAlignment(AI->getAlignment());
204  }
205 
206  AI->eraseFromParent();
207  MergedAwayAlloca = true;
208  ++NumMergedAllocas;
209  IFI.StaticAllocas[AllocaNo] = nullptr;
210  break;
211  }
212 
213  // If we already nuked the alloca, we're done with it.
214  if (MergedAwayAlloca)
215  continue;
216 
217  // If we were unable to merge away the alloca either because there are no
218  // allocas of the right type available or because we reused them all
219  // already, remember that this alloca came from an inlined function and mark
220  // it used so we don't reuse it for other allocas from this inline
221  // operation.
222  AllocasForType.push_back(AI);
223  UsedAllocas.insert(AI);
224  }
225 }
226 
227 /// If it is possible to inline the specified call site,
228 /// do so and update the CallGraph for this operation.
229 ///
230 /// This function also does some basic book-keeping to update the IR. The
231 /// InlinedArrayAllocas map keeps track of any allocas that are already
232 /// available from other functions inlined into the caller. If we are able to
233 /// inline this call site we attempt to reuse already available allocas or add
234 /// any new allocas to the set if not possible.
236  CallSite CS, InlineFunctionInfo &IFI,
237  InlinedArrayAllocasTy &InlinedArrayAllocas, int InlineHistory,
238  bool InsertLifetime, function_ref<AAResults &(Function &)> &AARGetter,
240  Function *Callee = CS.getCalledFunction();
241  Function *Caller = CS.getCaller();
242 
243  AAResults &AAR = AARGetter(*Callee);
244 
245  // Try to inline the function. Get the list of static allocas that were
246  // inlined.
247  if (!InlineFunction(CS, IFI, &AAR, InsertLifetime))
248  return false;
249 
250  if (InlinerFunctionImportStats != InlinerFunctionImportStatsOpts::No)
251  ImportedFunctionsStats.recordInline(*Caller, *Callee);
252 
254 
256  mergeInlinedArrayAllocas(Caller, IFI, InlinedArrayAllocas, InlineHistory);
257 
258  return true;
259 }
260 
261 /// Return true if inlining of CS can block the caller from being
262 /// inlined which is proved to be more beneficial. \p IC is the
263 /// estimated inline cost associated with callsite \p CS.
264 /// \p TotalSecondaryCost will be set to the estimated cost of inlining the
265 /// caller if \p CS is suppressed for inlining.
266 static bool
268  int &TotalSecondaryCost,
269  function_ref<InlineCost(CallSite CS)> GetInlineCost) {
270 
271  // For now we only handle local or inline functions.
272  if (!Caller->hasLocalLinkage() && !Caller->hasLinkOnceODRLinkage())
273  return false;
274  // Try to detect the case where the current inlining candidate caller (call
275  // it B) is a static or linkonce-ODR function and is an inlining candidate
276  // elsewhere, and the current candidate callee (call it C) is large enough
277  // that inlining it into B would make B too big to inline later. In these
278  // circumstances it may be best not to inline C into B, but to inline B into
279  // its callers.
280  //
281  // This only applies to static and linkonce-ODR functions because those are
282  // expected to be available for inlining in the translation units where they
283  // are used. Thus we will always have the opportunity to make local inlining
284  // decisions. Importantly the linkonce-ODR linkage covers inline functions
285  // and templates in C++.
286  //
287  // FIXME: All of this logic should be sunk into getInlineCost. It relies on
288  // the internal implementation of the inline cost metrics rather than
289  // treating them as truly abstract units etc.
290  TotalSecondaryCost = 0;
291  // The candidate cost to be imposed upon the current function.
292  int CandidateCost = IC.getCost() - 1;
293  // This bool tracks what happens if we do NOT inline C into B.
294  bool callerWillBeRemoved = Caller->hasLocalLinkage();
295  // This bool tracks what happens if we DO inline C into B.
296  bool inliningPreventsSomeOuterInline = false;
297  for (User *U : Caller->users()) {
298  CallSite CS2(U);
299 
300  // If this isn't a call to Caller (it could be some other sort
301  // of reference) skip it. Such references will prevent the caller
302  // from being removed.
303  if (!CS2 || CS2.getCalledFunction() != Caller) {
304  callerWillBeRemoved = false;
305  continue;
306  }
307 
308  InlineCost IC2 = GetInlineCost(CS2);
309  ++NumCallerCallersAnalyzed;
310  if (!IC2) {
311  callerWillBeRemoved = false;
312  continue;
313  }
314  if (IC2.isAlways())
315  continue;
316 
317  // See if inlining of the original callsite would erase the cost delta of
318  // this callsite. We subtract off the penalty for the call instruction,
319  // which we would be deleting.
320  if (IC2.getCostDelta() <= CandidateCost) {
321  inliningPreventsSomeOuterInline = true;
322  TotalSecondaryCost += IC2.getCost();
323  }
324  }
325  // If all outer calls to Caller would get inlined, the cost for the last
326  // one is set very low by getInlineCost, in anticipation that Caller will
327  // be removed entirely. We did not account for this above unless there
328  // is only one caller of Caller.
329  if (callerWillBeRemoved && !Caller->hasOneUse())
330  TotalSecondaryCost -= InlineConstants::LastCallToStaticBonus;
331 
332  if (inliningPreventsSomeOuterInline && TotalSecondaryCost < IC.getCost())
333  return true;
334 
335  return false;
336 }
337 
338 /// Return true if the inliner should attempt to inline at the given CallSite.
339 static bool shouldInline(CallSite CS,
340  function_ref<InlineCost(CallSite CS)> GetInlineCost,
342  using namespace ore;
343  InlineCost IC = GetInlineCost(CS);
344  Instruction *Call = CS.getInstruction();
345  Function *Callee = CS.getCalledFunction();
346  Function *Caller = CS.getCaller();
347 
348  if (IC.isAlways()) {
349  DEBUG(dbgs() << " Inlining: cost=always"
350  << ", Call: " << *CS.getInstruction() << "\n");
351  ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "AlwaysInline", Call)
352  << NV("Callee", Callee)
353  << " should always be inlined (cost=always)");
354  return true;
355  }
356 
357  if (IC.isNever()) {
358  DEBUG(dbgs() << " NOT Inlining: cost=never"
359  << ", Call: " << *CS.getInstruction() << "\n");
360  ORE.emit(OptimizationRemarkMissed(DEBUG_TYPE, "NeverInline", Call)
361  << NV("Callee", Callee) << " not inlined into "
362  << NV("Caller", Caller)
363  << " because it should never be inlined (cost=never)");
364  return false;
365  }
366 
367  if (!IC) {
368  DEBUG(dbgs() << " NOT Inlining: cost=" << IC.getCost()
369  << ", thres=" << (IC.getCostDelta() + IC.getCost())
370  << ", Call: " << *CS.getInstruction() << "\n");
371  ORE.emit(OptimizationRemarkMissed(DEBUG_TYPE, "TooCostly", Call)
372  << NV("Callee", Callee) << " not inlined into "
373  << NV("Caller", Caller) << " because too costly to inline (cost="
374  << NV("Cost", IC.getCost()) << ", threshold="
375  << NV("Threshold", IC.getCostDelta() + IC.getCost()) << ")");
376  return false;
377  }
378 
379  int TotalSecondaryCost = 0;
380  if (shouldBeDeferred(Caller, CS, IC, TotalSecondaryCost, GetInlineCost)) {
381  DEBUG(dbgs() << " NOT Inlining: " << *CS.getInstruction()
382  << " Cost = " << IC.getCost()
383  << ", outer Cost = " << TotalSecondaryCost << '\n');
384  ORE.emit(OptimizationRemarkMissed(DEBUG_TYPE, "IncreaseCostInOtherContexts",
385  Call)
386  << "Not inlining. Cost of inlining " << NV("Callee", Callee)
387  << " increases the cost of inlining " << NV("Caller", Caller)
388  << " in other contexts");
389  return false;
390  }
391 
392  DEBUG(dbgs() << " Inlining: cost=" << IC.getCost()
393  << ", thres=" << (IC.getCostDelta() + IC.getCost())
394  << ", Call: " << *CS.getInstruction() << '\n');
395  ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "CanBeInlined", Call)
396  << NV("Callee", Callee) << " can be inlined into "
397  << NV("Caller", Caller) << " with cost=" << NV("Cost", IC.getCost())
398  << " (threshold="
399  << NV("Threshold", IC.getCostDelta() + IC.getCost()) << ")");
400  return true;
401 }
402 
403 /// Return true if the specified inline history ID
404 /// indicates an inline history that includes the specified function.
406  Function *F, int InlineHistoryID,
407  const SmallVectorImpl<std::pair<Function *, int>> &InlineHistory) {
408  while (InlineHistoryID != -1) {
409  assert(unsigned(InlineHistoryID) < InlineHistory.size() &&
410  "Invalid inline history ID");
411  if (InlineHistory[InlineHistoryID].first == F)
412  return true;
413  InlineHistoryID = InlineHistory[InlineHistoryID].second;
414  }
415  return false;
416 }
417 
419  if (InlinerFunctionImportStats != InlinerFunctionImportStatsOpts::No)
421  return false; // No changes to CallGraph.
422 }
423 
425  if (skipSCC(SCC))
426  return false;
427  return inlineCalls(SCC);
428 }
429 
430 static bool
432  std::function<AssumptionCache &(Function &)> GetAssumptionCache,
434  bool InsertLifetime,
435  function_ref<InlineCost(CallSite CS)> GetInlineCost,
436  function_ref<AAResults &(Function &)> AARGetter,
438  SmallPtrSet<Function *, 8> SCCFunctions;
439  DEBUG(dbgs() << "Inliner visiting SCC:");
440  for (CallGraphNode *Node : SCC) {
441  Function *F = Node->getFunction();
442  if (F)
443  SCCFunctions.insert(F);
444  DEBUG(dbgs() << " " << (F ? F->getName() : "INDIRECTNODE"));
445  }
446 
447  // Scan through and identify all call sites ahead of time so that we only
448  // inline call sites in the original functions, not call sites that result
449  // from inlining other functions.
451 
452  // When inlining a callee produces new call sites, we want to keep track of
453  // the fact that they were inlined from the callee. This allows us to avoid
454  // infinite inlining in some obscure cases. To represent this, we use an
455  // index into the InlineHistory vector.
456  SmallVector<std::pair<Function *, int>, 8> InlineHistory;
457 
458  for (CallGraphNode *Node : SCC) {
459  Function *F = Node->getFunction();
460  if (!F || F->isDeclaration())
461  continue;
462 
464  for (BasicBlock &BB : *F)
465  for (Instruction &I : BB) {
466  CallSite CS(cast<Value>(&I));
467  // If this isn't a call, or it is a call to an intrinsic, it can
468  // never be inlined.
469  if (!CS || isa<IntrinsicInst>(I))
470  continue;
471 
472  // If this is a direct call to an external function, we can never inline
473  // it. If it is an indirect call, inlining may resolve it to be a
474  // direct call, so we keep it.
475  if (Function *Callee = CS.getCalledFunction())
476  if (Callee->isDeclaration()) {
477  using namespace ore;
478  ORE.emit(OptimizationRemarkMissed(DEBUG_TYPE, "NoDefinition", &I)
479  << NV("Callee", Callee) << " will not be inlined into "
480  << NV("Caller", CS.getCaller())
481  << " because its definition is unavailable"
482  << setIsVerbose());
483  continue;
484  }
485 
486  CallSites.push_back(std::make_pair(CS, -1));
487  }
488  }
489 
490  DEBUG(dbgs() << ": " << CallSites.size() << " call sites.\n");
491 
492  // If there are no calls in this function, exit early.
493  if (CallSites.empty())
494  return false;
495 
496  // Now that we have all of the call sites, move the ones to functions in the
497  // current SCC to the end of the list.
498  unsigned FirstCallInSCC = CallSites.size();
499  for (unsigned i = 0; i < FirstCallInSCC; ++i)
500  if (Function *F = CallSites[i].first.getCalledFunction())
501  if (SCCFunctions.count(F))
502  std::swap(CallSites[i--], CallSites[--FirstCallInSCC]);
503 
504  InlinedArrayAllocasTy InlinedArrayAllocas;
505  InlineFunctionInfo InlineInfo(&CG, &GetAssumptionCache, PSI);
506 
507  // Now that we have all of the call sites, loop over them and inline them if
508  // it looks profitable to do so.
509  bool Changed = false;
510  bool LocalChange;
511  do {
512  LocalChange = false;
513  // Iterate over the outer loop because inlining functions can cause indirect
514  // calls to become direct calls.
515  // CallSites may be modified inside so ranged for loop can not be used.
516  for (unsigned CSi = 0; CSi != CallSites.size(); ++CSi) {
517  CallSite CS = CallSites[CSi].first;
518 
519  Function *Caller = CS.getCaller();
520  Function *Callee = CS.getCalledFunction();
521 
522  // We can only inline direct calls to non-declarations.
523  if (!Callee || Callee->isDeclaration())
524  continue;
525 
526  Instruction *Instr = CS.getInstruction();
527 
528  bool IsTriviallyDead = isInstructionTriviallyDead(Instr, &TLI);
529 
530  int InlineHistoryID;
531  if (!IsTriviallyDead) {
532  // If this call site was obtained by inlining another function, verify
533  // that the include path for the function did not include the callee
534  // itself. If so, we'd be recursively inlining the same function,
535  // which would provide the same callsites, which would cause us to
536  // infinitely inline.
537  InlineHistoryID = CallSites[CSi].second;
538  if (InlineHistoryID != -1 &&
539  InlineHistoryIncludes(Callee, InlineHistoryID, InlineHistory))
540  continue;
541  }
542 
543  // FIXME for new PM: because of the old PM we currently generate ORE and
544  // in turn BFI on demand. With the new PM, the ORE dependency should
545  // just become a regular analysis dependency.
546  OptimizationRemarkEmitter ORE(Caller);
547 
548  // If the policy determines that we should inline this function,
549  // delete the call instead.
550  if (!shouldInline(CS, GetInlineCost, ORE))
551  continue;
552 
553  // If this call site is dead and it is to a readonly function, we should
554  // just delete the call instead of trying to inline it, regardless of
555  // size. This happens because IPSCCP propagates the result out of the
556  // call and then we're left with the dead call.
557  if (IsTriviallyDead) {
558  DEBUG(dbgs() << " -> Deleting dead call: " << *Instr << "\n");
559  // Update the call graph by deleting the edge from Callee to Caller.
560  CG[Caller]->removeCallEdgeFor(CS);
561  Instr->eraseFromParent();
562  ++NumCallsDeleted;
563  } else {
564  // Get DebugLoc to report. CS will be invalid after Inliner.
565  DebugLoc DLoc = Instr->getDebugLoc();
566  BasicBlock *Block = CS.getParent();
567 
568  // Attempt to inline the function.
569  using namespace ore;
570  if (!InlineCallIfPossible(CS, InlineInfo, InlinedArrayAllocas,
571  InlineHistoryID, InsertLifetime, AARGetter,
572  ImportedFunctionsStats)) {
573  ORE.emit(
574  OptimizationRemarkMissed(DEBUG_TYPE, "NotInlined", DLoc, Block)
575  << NV("Callee", Callee) << " will not be inlined into "
576  << NV("Caller", Caller));
577  continue;
578  }
579  ++NumInlined;
580 
581  // Report the inline decision.
582  ORE.emit(OptimizationRemark(DEBUG_TYPE, "Inlined", DLoc, Block)
583  << NV("Callee", Callee) << " inlined into "
584  << NV("Caller", Caller));
585 
586  // If inlining this function gave us any new call sites, throw them
587  // onto our worklist to process. They are useful inline candidates.
588  if (!InlineInfo.InlinedCalls.empty()) {
589  // Create a new inline history entry for this, so that we remember
590  // that these new callsites came about due to inlining Callee.
591  int NewHistoryID = InlineHistory.size();
592  InlineHistory.push_back(std::make_pair(Callee, InlineHistoryID));
593 
594  for (Value *Ptr : InlineInfo.InlinedCalls)
595  CallSites.push_back(std::make_pair(CallSite(Ptr), NewHistoryID));
596  }
597  }
598 
599  // If we inlined or deleted the last possible call site to the function,
600  // delete the function body now.
601  if (Callee && Callee->use_empty() && Callee->hasLocalLinkage() &&
602  // TODO: Can remove if in SCC now.
603  !SCCFunctions.count(Callee) &&
604 
605  // The function may be apparently dead, but if there are indirect
606  // callgraph references to the node, we cannot delete it yet, this
607  // could invalidate the CGSCC iterator.
608  CG[Callee]->getNumReferences() == 0) {
609  DEBUG(dbgs() << " -> Deleting dead function: " << Callee->getName()
610  << "\n");
611  CallGraphNode *CalleeNode = CG[Callee];
612 
613  // Remove any call graph edges from the callee to its callees.
614  CalleeNode->removeAllCalledFunctions();
615 
616  // Removing the node for callee from the call graph and delete it.
617  delete CG.removeFunctionFromModule(CalleeNode);
618  ++NumDeleted;
619  }
620 
621  // Remove this call site from the list. If possible, use
622  // swap/pop_back for efficiency, but do not use it if doing so would
623  // move a call site to a function in this SCC before the
624  // 'FirstCallInSCC' barrier.
625  if (SCC.isSingular()) {
626  CallSites[CSi] = CallSites.back();
627  CallSites.pop_back();
628  } else {
629  CallSites.erase(CallSites.begin() + CSi);
630  }
631  --CSi;
632 
633  Changed = true;
634  LocalChange = true;
635  }
636  } while (LocalChange);
637 
638  return Changed;
639 }
640 
642  CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
643  ACT = &getAnalysis<AssumptionCacheTracker>();
644  PSI = getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
645  auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
646  auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & {
647  return ACT->getAssumptionCache(F);
648  };
649  return inlineCallsImpl(SCC, CG, GetAssumptionCache, PSI, TLI, InsertLifetime,
650  [this](CallSite CS) { return getInlineCost(CS); },
652 }
653 
654 /// Remove now-dead linkonce functions at the end of
655 /// processing to avoid breaking the SCC traversal.
657  if (InlinerFunctionImportStats != InlinerFunctionImportStatsOpts::No)
658  ImportedFunctionsStats.dump(InlinerFunctionImportStats ==
659  InlinerFunctionImportStatsOpts::Verbose);
660  return removeDeadFunctions(CG);
661 }
662 
663 /// Remove dead functions that are not included in DNR (Do Not Remove) list.
665  bool AlwaysInlineOnly) {
666  SmallVector<CallGraphNode *, 16> FunctionsToRemove;
667  SmallVector<Function *, 16> DeadFunctionsInComdats;
668 
669  auto RemoveCGN = [&](CallGraphNode *CGN) {
670  // Remove any call graph edges from the function to its callees.
671  CGN->removeAllCalledFunctions();
672 
673  // Remove any edges from the external node to the function's call graph
674  // node. These edges might have been made irrelegant due to
675  // optimization of the program.
677 
678  // Removing the node for callee from the call graph and delete it.
679  FunctionsToRemove.push_back(CGN);
680  };
681 
682  // Scan for all of the functions, looking for ones that should now be removed
683  // from the program. Insert the dead ones in the FunctionsToRemove set.
684  for (const auto &I : CG) {
685  CallGraphNode *CGN = I.second.get();
686  Function *F = CGN->getFunction();
687  if (!F || F->isDeclaration())
688  continue;
689 
690  // Handle the case when this function is called and we only want to care
691  // about always-inline functions. This is a bit of a hack to share code
692  // between here and the InlineAlways pass.
693  if (AlwaysInlineOnly && !F->hasFnAttribute(Attribute::AlwaysInline))
694  continue;
695 
696  // If the only remaining users of the function are dead constants, remove
697  // them.
699 
700  if (!F->isDefTriviallyDead())
701  continue;
702 
703  // It is unsafe to drop a function with discardable linkage from a COMDAT
704  // without also dropping the other members of the COMDAT.
705  // The inliner doesn't visit non-function entities which are in COMDAT
706  // groups so it is unsafe to do so *unless* the linkage is local.
707  if (!F->hasLocalLinkage()) {
708  if (F->hasComdat()) {
709  DeadFunctionsInComdats.push_back(F);
710  continue;
711  }
712  }
713 
714  RemoveCGN(CGN);
715  }
716  if (!DeadFunctionsInComdats.empty()) {
717  // Filter out the functions whose comdats remain alive.
718  filterDeadComdatFunctions(CG.getModule(), DeadFunctionsInComdats);
719  // Remove the rest.
720  for (Function *F : DeadFunctionsInComdats)
721  RemoveCGN(CG[F]);
722  }
723 
724  if (FunctionsToRemove.empty())
725  return false;
726 
727  // Now that we know which functions to delete, do so. We didn't want to do
728  // this inline, because that would invalidate our CallGraph::iterator
729  // objects. :(
730  //
731  // Note that it doesn't matter that we are iterating over a non-stable order
732  // here to do this, it doesn't matter which order the functions are deleted
733  // in.
734  array_pod_sort(FunctionsToRemove.begin(), FunctionsToRemove.end());
735  FunctionsToRemove.erase(
736  std::unique(FunctionsToRemove.begin(), FunctionsToRemove.end()),
737  FunctionsToRemove.end());
738  for (CallGraphNode *CGN : FunctionsToRemove) {
739  delete CG.removeFunctionFromModule(CGN);
740  ++NumDeleted;
741  }
742  return true;
743 }
744 
747  CGSCCUpdateResult &UR) {
748  const ModuleAnalysisManager &MAM =
749  AM.getResult<ModuleAnalysisManagerCGSCCProxy>(InitialC, CG).getManager();
750  bool Changed = false;
751 
752  assert(InitialC.size() > 0 && "Cannot handle an empty SCC!");
753  Module &M = *InitialC.begin()->getFunction().getParent();
755 
756  // We use a single common worklist for calls across the entire SCC. We
757  // process these in-order and append new calls introduced during inlining to
758  // the end.
759  //
760  // Note that this particular order of processing is actually critical to
761  // avoid very bad behaviors. Consider *highly connected* call graphs where
762  // each function contains a small amonut of code and a couple of calls to
763  // other functions. Because the LLVM inliner is fundamentally a bottom-up
764  // inliner, it can handle gracefully the fact that these all appear to be
765  // reasonable inlining candidates as it will flatten things until they become
766  // too big to inline, and then move on and flatten another batch.
767  //
768  // However, when processing call edges *within* an SCC we cannot rely on this
769  // bottom-up behavior. As a consequence, with heavily connected *SCCs* of
770  // functions we can end up incrementally inlining N calls into each of
771  // N functions because each incremental inlining decision looks good and we
772  // don't have a topological ordering to prevent explosions.
773  //
774  // To compensate for this, we don't process transitive edges made immediate
775  // by inlining until we've done one pass of inlining across the entire SCC.
776  // Large, highly connected SCCs still lead to some amount of code bloat in
777  // this model, but it is uniformly spread across all the functions in the SCC
778  // and eventually they all become too large to inline, rather than
779  // incrementally maknig a single function grow in a super linear fashion.
781 
782  // Populate the initial list of calls in this SCC.
783  for (auto &N : InitialC) {
784  // We want to generally process call sites top-down in order for
785  // simplifications stemming from replacing the call with the returned value
786  // after inlining to be visible to subsequent inlining decisions.
787  // FIXME: Using instructions sequence is a really bad way to do this.
788  // Instead we should do an actual RPO walk of the function body.
789  for (Instruction &I : instructions(N.getFunction()))
790  if (auto CS = CallSite(&I))
791  if (Function *Callee = CS.getCalledFunction())
792  if (!Callee->isDeclaration())
793  Calls.push_back({CS, -1});
794  }
795  if (Calls.empty())
796  return PreservedAnalyses::all();
797 
798  // Capture updatable variables for the current SCC and RefSCC.
799  auto *C = &InitialC;
800  auto *RC = &C->getOuterRefSCC();
801 
802  // When inlining a callee produces new call sites, we want to keep track of
803  // the fact that they were inlined from the callee. This allows us to avoid
804  // infinite inlining in some obscure cases. To represent this, we use an
805  // index into the InlineHistory vector.
806  SmallVector<std::pair<Function *, int>, 16> InlineHistory;
807 
808  // Track a set vector of inlined callees so that we can augment the caller
809  // with all of their edges in the call graph before pruning out the ones that
810  // got simplified away.
811  SmallSetVector<Function *, 4> InlinedCallees;
812 
813  // Track the dead functions to delete once finished with inlining calls. We
814  // defer deleting these to make it easier to handle the call graph updates.
815  SmallVector<Function *, 4> DeadFunctions;
816 
817  // Loop forward over all of the calls. Note that we cannot cache the size as
818  // inlining can introduce new calls that need to be processed.
819  for (int i = 0; i < (int)Calls.size(); ++i) {
820  // We expect the calls to typically be batched with sequences of calls that
821  // have the same caller, so we first set up some shared infrastructure for
822  // this caller. We also do any pruning we can at this layer on the caller
823  // alone.
824  Function &F = *Calls[i].first.getCaller();
825  LazyCallGraph::Node &N = *CG.lookup(F);
826  if (CG.lookupSCC(N) != C)
827  continue;
828  if (F.hasFnAttribute(Attribute::OptimizeNone))
829  continue;
830 
831  DEBUG(dbgs() << "Inlining calls in: " << F.getName() << "\n");
832 
833  // Get a FunctionAnalysisManager via a proxy for this particular node. We
834  // do this each time we visit a node as the SCC may have changed and as
835  // we're going to mutate this particular function we want to make sure the
836  // proxy is in place to forward any invalidation events. We can use the
837  // manager we get here for looking up results for functions other than this
838  // node however because those functions aren't going to be mutated by this
839  // pass.
842  .getManager();
843  std::function<AssumptionCache &(Function &)> GetAssumptionCache =
844  [&](Function &F) -> AssumptionCache & {
845  return FAM.getResult<AssumptionAnalysis>(F);
846  };
847  auto GetBFI = [&](Function &F) -> BlockFrequencyInfo & {
848  return FAM.getResult<BlockFrequencyAnalysis>(F);
849  };
850 
851  auto GetInlineCost = [&](CallSite CS) {
852  Function &Callee = *CS.getCalledFunction();
853  auto &CalleeTTI = FAM.getResult<TargetIRAnalysis>(Callee);
854  return getInlineCost(CS, Params, CalleeTTI, GetAssumptionCache, {GetBFI},
855  PSI);
856  };
857 
858  // Get the remarks emission analysis for the caller.
859  auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(F);
860 
861  // Now process as many calls as we have within this caller in the sequnece.
862  // We bail out as soon as the caller has to change so we can update the
863  // call graph and prepare the context of that new caller.
864  bool DidInline = false;
865  for (; i < (int)Calls.size() && Calls[i].first.getCaller() == &F; ++i) {
866  int InlineHistoryID;
867  CallSite CS;
868  std::tie(CS, InlineHistoryID) = Calls[i];
869  Function &Callee = *CS.getCalledFunction();
870 
871  if (InlineHistoryID != -1 &&
872  InlineHistoryIncludes(&Callee, InlineHistoryID, InlineHistory))
873  continue;
874 
875  // Check whether we want to inline this callsite.
876  if (!shouldInline(CS, GetInlineCost, ORE))
877  continue;
878 
879  // Setup the data structure used to plumb customization into the
880  // `InlineFunction` routine.
881  InlineFunctionInfo IFI(
882  /*cg=*/nullptr, &GetAssumptionCache, PSI,
883  &FAM.getResult<BlockFrequencyAnalysis>(*(CS.getCaller())),
884  &FAM.getResult<BlockFrequencyAnalysis>(Callee));
885 
886  if (!InlineFunction(CS, IFI))
887  continue;
888  DidInline = true;
889  InlinedCallees.insert(&Callee);
890 
891  // Add any new callsites to defined functions to the worklist.
892  if (!IFI.InlinedCallSites.empty()) {
893  int NewHistoryID = InlineHistory.size();
894  InlineHistory.push_back({&Callee, InlineHistoryID});
895  for (CallSite &CS : reverse(IFI.InlinedCallSites))
896  if (Function *NewCallee = CS.getCalledFunction())
897  if (!NewCallee->isDeclaration())
898  Calls.push_back({CS, NewHistoryID});
899  }
900 
901  // Merge the attributes based on the inlining.
903 
904  // For local functions, check whether this makes the callee trivially
905  // dead. In that case, we can drop the body of the function eagerly
906  // which may reduce the number of callers of other functions to one,
907  // changing inline cost thresholds.
908  if (Callee.hasLocalLinkage()) {
909  // To check this we also need to nuke any dead constant uses (perhaps
910  // made dead by this operation on other functions).
911  Callee.removeDeadConstantUsers();
912  if (Callee.use_empty() && !CG.isLibFunction(Callee)) {
913  Calls.erase(
914  std::remove_if(Calls.begin() + i + 1, Calls.end(),
915  [&Callee](const std::pair<CallSite, int> &Call) {
916  return Call.first.getCaller() == &Callee;
917  }),
918  Calls.end());
919  // Clear the body and queue the function itself for deletion when we
920  // finish inlining and call graph updates.
921  // Note that after this point, it is an error to do anything other
922  // than use the callee's address or delete it.
923  Callee.dropAllReferences();
924  assert(find(DeadFunctions, &Callee) == DeadFunctions.end() &&
925  "Cannot put cause a function to become dead twice!");
926  DeadFunctions.push_back(&Callee);
927  }
928  }
929  }
930 
931  // Back the call index up by one to put us in a good position to go around
932  // the outer loop.
933  --i;
934 
935  if (!DidInline)
936  continue;
937  Changed = true;
938 
939  // Add all the inlined callees' edges as ref edges to the caller. These are
940  // by definition trivial edges as we always have *some* transitive ref edge
941  // chain. While in some cases these edges are direct calls inside the
942  // callee, they have to be modeled in the inliner as reference edges as
943  // there may be a reference edge anywhere along the chain from the current
944  // caller to the callee that causes the whole thing to appear like
945  // a (transitive) reference edge that will require promotion to a call edge
946  // below.
947  for (Function *InlinedCallee : InlinedCallees) {
948  LazyCallGraph::Node &CalleeN = *CG.lookup(*InlinedCallee);
949  for (LazyCallGraph::Edge &E : *CalleeN)
950  RC->insertTrivialRefEdge(N, E.getNode());
951  }
952  InlinedCallees.clear();
953 
954  // At this point, since we have made changes we have at least removed
955  // a call instruction. However, in the process we do some incremental
956  // simplification of the surrounding code. This simplification can
957  // essentially do all of the same things as a function pass and we can
958  // re-use the exact same logic for updating the call graph to reflect the
959  // change..
960  C = &updateCGAndAnalysisManagerForFunctionPass(CG, *C, N, AM, UR);
961  DEBUG(dbgs() << "Updated inlining SCC: " << *C << "\n");
962  RC = &C->getOuterRefSCC();
963  }
964 
965  // Now that we've finished inlining all of the calls across this SCC, delete
966  // all of the trivially dead functions, updating the call graph and the CGSCC
967  // pass manager in the process.
968  //
969  // Note that this walks a pointer set which has non-deterministic order but
970  // that is OK as all we do is delete things and add pointers to unordered
971  // sets.
972  for (Function *DeadF : DeadFunctions) {
973  // Get the necessary information out of the call graph and nuke the
974  // function there. Also, cclear out any cached analyses.
975  auto &DeadC = *CG.lookupSCC(*CG.lookup(*DeadF));
978  .getManager();
979  FAM.clear(*DeadF);
980  AM.clear(DeadC);
981  auto &DeadRC = DeadC.getOuterRefSCC();
982  CG.removeDeadFunction(*DeadF);
983 
984  // Mark the relevant parts of the call graph as invalid so we don't visit
985  // them.
986  UR.InvalidatedSCCs.insert(&DeadC);
987  UR.InvalidatedRefSCCs.insert(&DeadRC);
988 
989  // And delete the actual function from the module.
990  M.getFunctionList().erase(DeadF);
991  }
992 
993  if (!Changed)
994  return PreservedAnalyses::all();
995 
996  // Even if we change the IR, we update the core CGSCC data structures and so
997  // can preserve the proxy to the function analysis manager.
1000  return PA;
1001 }
InlinerFunctionImportStatsOpts
Definition: Inliner.cpp:66
uint64_t CallInst * C
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:69
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:109
bool doFinalization(CallGraph &CG) override
Remove now-dead linkonce functions at the end of processing to avoid breaking the SCC traversal...
Definition: Inliner.cpp:656
void setModuleInfo(const Module &M)
Set information like AllFunctions, ImportedFunctions, ModuleName.
bool hasLocalLinkage() const
Definition: GlobalValue.h:416
Diagnostic information for missed-optimization remarks.
DiagnosticInfoOptimizationBase::Argument NV
bool isNever() const
Definition: InlineCost.h:98
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:687
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
static bool InlineHistoryIncludes(Function *F, int InlineHistoryID, const SmallVectorImpl< std::pair< Function *, int >> &InlineHistory)
Return true if the specified inline history ID indicates an inline history that includes the specifie...
Definition: Inliner.cpp:405
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
auto remove_if(R &&Range, UnaryPredicate P) -> decltype(std::begin(Range))
Provide wrappers to std::remove_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:858
void recordInline(const Function &Caller, const Function &Callee)
Record inline of.
virtual InlineCost getInlineCost(CallSite CS)=0
This method must be implemented by the subclass to determine the cost of inlining the specified call ...
SCC * lookupSCC(Node &N) const
Lookup a function&#39;s SCC in the graph.
Analysis providing profile information.
An immutable pass that tracks lazily created AssumptionCache objects.
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:89
A cache of .assume calls within a function.
Analysis pass providing the TargetTransformInfo.
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:697
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
Definition: Function.h:254
STATISTIC(NumFunctions, "Total number of functions")
A debug info location.
Definition: DebugLoc.h:34
Calculate and dump ThinLTO specific inliner stats.
InlineFunctionInfo - This class captures the data input to the InlineFunction call, and records the auxiliary results produced by it.
Definition: Cloning.h:176
static void mergeInlinedArrayAllocas(Function *Caller, InlineFunctionInfo &IFI, InlinedArrayAllocasTy &InlinedArrayAllocas, int InlineHistory)
Look at all of the allocas that we inlined through this call site.
Definition: Inliner.cpp:121
A proxy from a FunctionAnalysisManager to an SCC.
A node in the call graph for a module.
Definition: CallGraph.h:161
bool skipSCC(CallGraphSCC &SCC) const
Optional passes call this function to check whether the pass should be skipped.
void getAnalysisUsage(AnalysisUsage &Info) const override
getAnalysisUsage - For this class, we declare that we require and preserve the call graph...
Support structure for SCC passes to communicate updates the call graph back to the CGSCC pass manager...
Represents the cost of inlining a function.
Definition: InlineCost.h:64
Module & getModule() const
Returns the module the call graph corresponds to.
Definition: CallGraph.h:110
bool InlineFunction(CallInst *C, InlineFunctionInfo &IFI, AAResults *CalleeAAR=nullptr, bool InsertLifetime=true)
InlineFunction - This function inlines the called function into the basic block of the caller...
AnalysisUsage & addRequired()
bool runOnSCC(CallGraphSCC &SCC) override
Main run interface method, this implements the interface required by the Pass class.
Definition: Inliner.cpp:424
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:361
unsigned getAlignment() const
Return the alignment of the memory that is being allocated by the instruction.
Definition: Instructions.h:109
An analysis pass based on legacy pass manager to deliver ProfileSummaryInfo.
Diagnostic information for optimization analysis remarks.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
This class is a functor to be used in legacy module or SCC passes for computing AA results for a func...
bool isLibFunction(Function &F) const
Test whether a function is a known and defined library function tracked by the call graph...
Function * removeFunctionFromModule(CallGraphNode *CGN)
Unlink the function from this module, returning it.
Definition: CallGraph.cpp:114
InstrTy * getInstruction() const
Definition: CallSite.h:89
PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG, CGSCCUpdateResult &UR)
Definition: Inliner.cpp:745
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:250
This file provides interfaces used to build and manipulate a call graph, which is a very useful tool ...
#define F(x, y, z)
Definition: MD5.cpp:55
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:142
Class to represent array types.
Definition: DerivedTypes.h:369
A lazily constructed view of the call graph of a module.
const int LastCallToStaticBonus
Definition: InlineCost.h:46
DiagnosticInfoOptimizationBase::setIsVerbose setIsVerbose
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:428
#define DEBUG_TYPE
Definition: Inliner.cpp:42
void removeDeadConstantUsers() const
If there are any dead constant users dangling off of this constant, remove them.
Definition: Constants.cpp:475
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
bool hasLinkOnceODRLinkage() const
Definition: GlobalValue.h:407
SmallVector< CallSite, 8 > InlinedCallSites
All of the new call sites inlined into the caller.
Definition: Cloning.h:207
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:404
bool isAlways() const
Definition: InlineCost.h:97
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
Definition: STLExtras.h:771
void getAnalysisUsage(AnalysisUsage &Info) const override
For this class, we declare that we require and preserve the call graph.
Definition: Inliner.cpp:91
void removeAnyCallEdgeTo(CallGraphNode *Callee)
Removes all call edges from this node to the specified callee function.
Definition: CallGraph.cpp:196
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
static MetadataAsValue * getIfExists(LLVMContext &Context, Metadata *MD)
Definition: Metadata.cpp:114
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
bool inlineCalls(CallGraphSCC &SCC)
This function performs the main work of the pass.
Definition: Inliner.cpp:641
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:624
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:116
SmallPtrSetImpl< LazyCallGraph::RefSCC * > & InvalidatedRefSCCs
The set of invalidated RefSCCs which should be skipped if they are found in RCWorklist.
SmallPtrSetImpl< LazyCallGraph::SCC * > & InvalidatedSCCs
The set of invalidated SCCs which should be skipped if they are found in CWorklist.
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:372
Diagnostic information for applied optimization remarks.
Represent the analysis usage information of a pass.
A node in the call graph.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
A class used to represent edges in the call graph.
iterator erase(const_iterator CI)
Definition: SmallVector.h:449
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
bool doInitialization(CallGraph &CG) override
doInitialization - This method is called before the SCC&#39;s of the program has been processed...
Definition: Inliner.cpp:418
void getAAResultsAnalysisUsage(AnalysisUsage &AU)
A helper for the legacy pass manager to populate AU to add uses to make sure the analyses required by...
Type * getAllocatedType() const
Return the type that is being allocated by the instruction.
Definition: Instructions.h:102
unsigned first
Function * getFunction() const
Returns the function that this call graph node represents.
Definition: CallGraph.h:181
void clear(IRUnitT &IR)
Clear any cached analysis results for a single unit of IR.
Definition: PassManager.h:657
A function analysis which provides an AssumptionCache.
static bool inlineCallsImpl(CallGraphSCC &SCC, CallGraph &CG, std::function< AssumptionCache &(Function &)> GetAssumptionCache, ProfileSummaryInfo *PSI, TargetLibraryInfo &TLI, bool InsertLifetime, function_ref< InlineCost(CallSite CS)> GetInlineCost, function_ref< AAResults &(Function &)> AARGetter, ImportedFunctionsInliningStatistics &ImportedFunctionsStats)
Definition: Inliner.cpp:431
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:298
Analysis pass which computes BlockFrequencyInfo.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:423
void removeDeadFunction(Function &F)
Remove a dead function from the call graph (typically to delete it).
#define E
Definition: LargeTest.cpp:27
ImportedFunctionsInliningStatistics ImportedFunctionsStats
Definition: Inliner.h:77
void emit(DiagnosticInfoOptimizationBase &OptDiag)
Output the remark via the diagnostic handler and to the optimization record file. ...
auto find(R &&Range, const T &Val) -> decltype(std::begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:839
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
Definition: PassManager.h:1062
static cl::opt< bool > DisableInlinedAllocaMerging("disable-inlined-alloca-merging", cl::init(false), cl::Hidden)
Flag to disable manual alloca merging.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
Module.h This file contains the declarations for the Module class.
Provides information about what library functions are available for the current target.
static LocalAsMetadata * getIfExists(Value *Local)
Definition: Metadata.h:438
unsigned getABITypeAlignment(Type *Ty) const
Returns the minimum ABI-required alignment for the specified type.
Definition: DataLayout.cpp:682
const size_t N
void dropAllReferences()
dropAllReferences() - This method causes all the subinstructions to "let go" of all references that t...
Definition: Function.cpp:325
AssumptionCacheTracker * ACT
Definition: Inliner.h:75
bool removeDeadFunctions(CallGraph &CG, bool AlwaysInlineOnly=false)
Remove dead functions.
Definition: Inliner.cpp:664
Node * lookup(const Function &F) const
Lookup a function in the graph which has already been scanned and added.
BBTy * getParent() const
Get the basic block containing the call site.
Definition: CallSite.h:94
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
void mergeAttributesForInlining(Function &Caller, const Function &Callee)
Merge caller&#39;s and callee&#39;s attributes.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:923
void dump(bool Verbose)
Dump stats computed with InlinerStatistics class.
iterator_range< user_iterator > users()
Definition: Value.h:395
static bool InlineCallIfPossible(CallSite CS, InlineFunctionInfo &IFI, InlinedArrayAllocasTy &InlinedArrayAllocas, int InlineHistory, bool InsertLifetime, function_ref< AAResults &(Function &)> &AARGetter, ImportedFunctionsInliningStatistics &ImportedFunctionsStats)
If it is possible to inline the specified call site, do so and update the CallGraph for this operatio...
Definition: Inliner.cpp:235
int getCost() const
Get the inline cost estimate.
Definition: InlineCost.h:103
int getCostDelta() const
Get the cost delta from the threshold for inlining.
Definition: InlineCost.h:111
bool hasComdat() const
Definition: GlobalObject.h:100
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
Definition: CommandLine.h:599
void filterDeadComdatFunctions(Module &M, SmallVectorImpl< Function *> &DeadComdatFunctions)
Filter out potentially dead comdat functions where other entries keep the entire comdat group alive...
Basic Alias true
SmallVector< AllocaInst *, 4 > StaticAllocas
StaticAllocas - InlineFunction fills this in with all static allocas that get copied into the caller...
Definition: Cloning.h:196
The basic data container for the call graph of a Module of IR.
Definition: CallGraph.h:70
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:120
FunTy * getCaller() const
Return the caller function for this call site.
Definition: CallSite.h:264
LegacyInlinerBase(char &ID)
Definition: Inliner.cpp:82
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:280
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
SmallVector< WeakTrackingVH, 8 > InlinedCalls
InlinedCalls - InlineFunction fills this in with callsites that were inlined from the callee...
Definition: Cloning.h:200
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:218
#define I(x, y, z)
Definition: MD5.cpp:58
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:706
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:174
ProfileSummaryInfo * PSI
Definition: Inliner.h:76
static bool shouldInline(CallSite CS, function_ref< InlineCost(CallSite CS)> GetInlineCost, OptimizationRemarkEmitter &ORE)
Return true if the inliner should attempt to inline at the given CallSite.
Definition: Inliner.cpp:339
CallGraphNode * getExternalCallingNode() const
Returns the CallGraphNode which is used to represent undetermined calls into the callgraph.
Definition: CallGraph.h:133
bool isDeclaration() const
Return true if the primary definition of this global value is outside of the current translation unit...
Definition: Globals.cpp:200
FunTy * getCalledFunction() const
Return the function being called if this is a direct call, otherwise return null (if it&#39;s an indirect...
Definition: CallSite.h:104
bool isArrayAllocation() const
Return true if there is an allocation size parameter to the allocation instruction that is not 1...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:545
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction has no side ef...
Definition: Local.cpp:293
LLVM Value Representation.
Definition: Value.h:73
An SCC of the call graph.
CallGraphSCC - This is a single SCC that a CallGraphSCCPass is run on.
#define DEBUG(X)
Definition: Debug.h:118
AssumptionCache & getAssumptionCache(Function &F)
Get the cached assumptions for a function.
print Print MemDeps of function
bool hasOneUse() const
Return true if there is exactly one user of this value.
Definition: Value.h:408
This is the interface for LLVM&#39;s primary stateless and local alias analysis.
inst_range instructions(Function *F)
Definition: InstIterator.h:134
A container for analyses that lazily runs them and caches their results.
static bool shouldBeDeferred(Function *Caller, CallSite CS, InlineCost IC, int &TotalSecondaryCost, function_ref< InlineCost(CallSite CS)> GetInlineCost)
Return true if inlining of CS can block the caller from being inlined which is proved to be more bene...
Definition: Inliner.cpp:267
int * Ptr
LazyCallGraph::SCC & updateCGAndAnalysisManagerForFunctionPass(LazyCallGraph &G, LazyCallGraph::SCC &C, LazyCallGraph::Node &N, CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR, bool DebugLogging=false)
Helper to update the call graph after running a function pass.
This represents the llvm.dbg.declare instruction.
Definition: IntrinsicInst.h:89
The optimization diagnostic interface.
bool use_empty() const
Definition: Value.h:322
bool isDefTriviallyDead() const
isDefTriviallyDead - Return true if it is trivially safe to remove this function definition from the ...
Definition: Function.cpp:1228
const BasicBlock * getParent() const
Definition: Instruction.h:66
DenseMap< ArrayType *, std::vector< AllocaInst * > > InlinedArrayAllocasTy
Definition: Inliner.cpp:99
an instruction to allocate memory on the stack
Definition: Instructions.h:60