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,
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 the cost only if the inliner should attempt to inline at the given
339 /// CallSite. If we return the cost, we will emit an optimisation remark later
340 /// using that cost, so we won't do so from this function.
344  using namespace ore;
345  InlineCost IC = GetInlineCost(CS);
346  Instruction *Call = CS.getInstruction();
348  Function *Caller = CS.getCaller();
349 
350  if (IC.isAlways()) {
351  DEBUG(dbgs() << " Inlining: cost=always"
352  << ", Call: " << *CS.getInstruction() << "\n");
353  return IC;
354  }
355 
356  if (IC.isNever()) {
357  DEBUG(dbgs() << " NOT Inlining: cost=never"
358  << ", Call: " << *CS.getInstruction() << "\n");
359  ORE.emit([&]() {
360  return 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  });
365  return None;
366  }
367 
368  if (!IC) {
369  DEBUG(dbgs() << " NOT Inlining: cost=" << IC.getCost()
370  << ", thres=" << IC.getThreshold()
371  << ", Call: " << *CS.getInstruction() << "\n");
372  ORE.emit([&]() {
373  return OptimizationRemarkMissed(DEBUG_TYPE, "TooCostly", Call)
374  << NV("Callee", Callee) << " not inlined into "
375  << NV("Caller", Caller) << " because too costly to inline (cost="
376  << NV("Cost", IC.getCost())
377  << ", threshold=" << NV("Threshold", IC.getThreshold()) << ")";
378  });
379  return None;
380  }
381 
382  int TotalSecondaryCost = 0;
383  if (shouldBeDeferred(Caller, CS, IC, TotalSecondaryCost, GetInlineCost)) {
384  DEBUG(dbgs() << " NOT Inlining: " << *CS.getInstruction()
385  << " Cost = " << IC.getCost()
386  << ", outer Cost = " << TotalSecondaryCost << '\n');
387  ORE.emit(OptimizationRemarkMissed(DEBUG_TYPE, "IncreaseCostInOtherContexts",
388  Call)
389  << "Not inlining. Cost of inlining " << NV("Callee", Callee)
390  << " increases the cost of inlining " << NV("Caller", Caller)
391  << " in other contexts");
392 
393  // IC does not bool() to false, so get an InlineCost that will.
394  // This will not be inspected to make an error message.
395  return None;
396  }
397 
398  DEBUG(dbgs() << " Inlining: cost=" << IC.getCost()
399  << ", thres=" << IC.getThreshold()
400  << ", Call: " << *CS.getInstruction() << '\n');
401  return IC;
402 }
403 
404 /// Return true if the specified inline history ID
405 /// indicates an inline history that includes the specified function.
407  Function *F, int InlineHistoryID,
408  const SmallVectorImpl<std::pair<Function *, int>> &InlineHistory) {
409  while (InlineHistoryID != -1) {
410  assert(unsigned(InlineHistoryID) < InlineHistory.size() &&
411  "Invalid inline history ID");
412  if (InlineHistory[InlineHistoryID].first == F)
413  return true;
414  InlineHistoryID = InlineHistory[InlineHistoryID].second;
415  }
416  return false;
417 }
418 
420  if (InlinerFunctionImportStats != InlinerFunctionImportStatsOpts::No)
422  return false; // No changes to CallGraph.
423 }
424 
426  if (skipSCC(SCC))
427  return false;
428  return inlineCalls(SCC);
429 }
430 
431 static bool
433  std::function<AssumptionCache &(Function &)> GetAssumptionCache,
435  bool InsertLifetime,
436  function_ref<InlineCost(CallSite CS)> GetInlineCost,
437  function_ref<AAResults &(Function &)> AARGetter,
439  SmallPtrSet<Function *, 8> SCCFunctions;
440  DEBUG(dbgs() << "Inliner visiting SCC:");
441  for (CallGraphNode *Node : SCC) {
442  Function *F = Node->getFunction();
443  if (F)
444  SCCFunctions.insert(F);
445  DEBUG(dbgs() << " " << (F ? F->getName() : "INDIRECTNODE"));
446  }
447 
448  // Scan through and identify all call sites ahead of time so that we only
449  // inline call sites in the original functions, not call sites that result
450  // from inlining other functions.
452 
453  // When inlining a callee produces new call sites, we want to keep track of
454  // the fact that they were inlined from the callee. This allows us to avoid
455  // infinite inlining in some obscure cases. To represent this, we use an
456  // index into the InlineHistory vector.
457  SmallVector<std::pair<Function *, int>, 8> InlineHistory;
458 
459  for (CallGraphNode *Node : SCC) {
460  Function *F = Node->getFunction();
461  if (!F || F->isDeclaration())
462  continue;
463 
465  for (BasicBlock &BB : *F)
466  for (Instruction &I : BB) {
467  CallSite CS(cast<Value>(&I));
468  // If this isn't a call, or it is a call to an intrinsic, it can
469  // never be inlined.
470  if (!CS || isa<IntrinsicInst>(I))
471  continue;
472 
473  // If this is a direct call to an external function, we can never inline
474  // it. If it is an indirect call, inlining may resolve it to be a
475  // direct call, so we keep it.
476  if (Function *Callee = CS.getCalledFunction())
477  if (Callee->isDeclaration()) {
478  using namespace ore;
479  ORE.emit(OptimizationRemarkMissed(DEBUG_TYPE, "NoDefinition", &I)
480  << NV("Callee", Callee) << " will not be inlined into "
481  << NV("Caller", CS.getCaller())
482  << " because its definition is unavailable"
483  << setIsVerbose());
484  continue;
485  }
486 
487  CallSites.push_back(std::make_pair(CS, -1));
488  }
489  }
490 
491  DEBUG(dbgs() << ": " << CallSites.size() << " call sites.\n");
492 
493  // If there are no calls in this function, exit early.
494  if (CallSites.empty())
495  return false;
496 
497  // Now that we have all of the call sites, move the ones to functions in the
498  // current SCC to the end of the list.
499  unsigned FirstCallInSCC = CallSites.size();
500  for (unsigned i = 0; i < FirstCallInSCC; ++i)
501  if (Function *F = CallSites[i].first.getCalledFunction())
502  if (SCCFunctions.count(F))
503  std::swap(CallSites[i--], CallSites[--FirstCallInSCC]);
504 
505  InlinedArrayAllocasTy InlinedArrayAllocas;
506  InlineFunctionInfo InlineInfo(&CG, &GetAssumptionCache, PSI);
507 
508  // Now that we have all of the call sites, loop over them and inline them if
509  // it looks profitable to do so.
510  bool Changed = false;
511  bool LocalChange;
512  do {
513  LocalChange = false;
514  // Iterate over the outer loop because inlining functions can cause indirect
515  // calls to become direct calls.
516  // CallSites may be modified inside so ranged for loop can not be used.
517  for (unsigned CSi = 0; CSi != CallSites.size(); ++CSi) {
518  CallSite CS = CallSites[CSi].first;
519 
520  Function *Caller = CS.getCaller();
522 
523  // We can only inline direct calls to non-declarations.
524  if (!Callee || Callee->isDeclaration())
525  continue;
526 
527  Instruction *Instr = CS.getInstruction();
528 
529  bool IsTriviallyDead = isInstructionTriviallyDead(Instr, &TLI);
530 
531  int InlineHistoryID;
532  if (!IsTriviallyDead) {
533  // If this call site was obtained by inlining another function, verify
534  // that the include path for the function did not include the callee
535  // itself. If so, we'd be recursively inlining the same function,
536  // which would provide the same callsites, which would cause us to
537  // infinitely inline.
538  InlineHistoryID = CallSites[CSi].second;
539  if (InlineHistoryID != -1 &&
540  InlineHistoryIncludes(Callee, InlineHistoryID, InlineHistory))
541  continue;
542  }
543 
544  // FIXME for new PM: because of the old PM we currently generate ORE and
545  // in turn BFI on demand. With the new PM, the ORE dependency should
546  // just become a regular analysis dependency.
547  OptimizationRemarkEmitter ORE(Caller);
548 
549  Optional<InlineCost> OIC = shouldInline(CS, GetInlineCost, ORE);
550  // If the policy determines that we should inline this function,
551  // delete the call instead.
552  if (!OIC)
553  continue;
554 
555  // If this call site is dead and it is to a readonly function, we should
556  // just delete the call instead of trying to inline it, regardless of
557  // size. This happens because IPSCCP propagates the result out of the
558  // call and then we're left with the dead call.
559  if (IsTriviallyDead) {
560  DEBUG(dbgs() << " -> Deleting dead call: " << *Instr << "\n");
561  // Update the call graph by deleting the edge from Callee to Caller.
562  CG[Caller]->removeCallEdgeFor(CS);
563  Instr->eraseFromParent();
564  ++NumCallsDeleted;
565  } else {
566  // Get DebugLoc to report. CS will be invalid after Inliner.
567  DebugLoc DLoc = CS->getDebugLoc();
568  BasicBlock *Block = CS.getParent();
569 
570  // Attempt to inline the function.
571  using namespace ore;
572  if (!InlineCallIfPossible(CS, InlineInfo, InlinedArrayAllocas,
573  InlineHistoryID, InsertLifetime, AARGetter,
574  ImportedFunctionsStats)) {
575  ORE.emit(
576  OptimizationRemarkMissed(DEBUG_TYPE, "NotInlined", DLoc, Block)
577  << NV("Callee", Callee) << " will not be inlined into "
578  << NV("Caller", Caller));
579  continue;
580  }
581  ++NumInlined;
582 
583  if (OIC->isAlways())
584  ORE.emit(OptimizationRemark(DEBUG_TYPE, "AlwaysInline", DLoc, Block)
585  << NV("Callee", Callee) << " inlined into "
586  << NV("Caller", Caller) << " with cost=always");
587  else
588  ORE.emit([&]() {
589  return OptimizationRemark(DEBUG_TYPE, "Inlined", DLoc, Block)
590  << NV("Callee", Callee) << " inlined into "
591  << NV("Caller", Caller)
592  << " with cost=" << NV("Cost", OIC->getCost())
593  << " (threshold=" << NV("Threshold", OIC->getThreshold())
594  << ")";
595  });
596 
597  // If inlining this function gave us any new call sites, throw them
598  // onto our worklist to process. They are useful inline candidates.
599  if (!InlineInfo.InlinedCalls.empty()) {
600  // Create a new inline history entry for this, so that we remember
601  // that these new callsites came about due to inlining Callee.
602  int NewHistoryID = InlineHistory.size();
603  InlineHistory.push_back(std::make_pair(Callee, InlineHistoryID));
604 
605  for (Value *Ptr : InlineInfo.InlinedCalls)
606  CallSites.push_back(std::make_pair(CallSite(Ptr), NewHistoryID));
607  }
608  }
609 
610  // If we inlined or deleted the last possible call site to the function,
611  // delete the function body now.
612  if (Callee && Callee->use_empty() && Callee->hasLocalLinkage() &&
613  // TODO: Can remove if in SCC now.
614  !SCCFunctions.count(Callee) &&
615 
616  // The function may be apparently dead, but if there are indirect
617  // callgraph references to the node, we cannot delete it yet, this
618  // could invalidate the CGSCC iterator.
619  CG[Callee]->getNumReferences() == 0) {
620  DEBUG(dbgs() << " -> Deleting dead function: " << Callee->getName()
621  << "\n");
622  CallGraphNode *CalleeNode = CG[Callee];
623 
624  // Remove any call graph edges from the callee to its callees.
625  CalleeNode->removeAllCalledFunctions();
626 
627  // Removing the node for callee from the call graph and delete it.
628  delete CG.removeFunctionFromModule(CalleeNode);
629  ++NumDeleted;
630  }
631 
632  // Remove this call site from the list. If possible, use
633  // swap/pop_back for efficiency, but do not use it if doing so would
634  // move a call site to a function in this SCC before the
635  // 'FirstCallInSCC' barrier.
636  if (SCC.isSingular()) {
637  CallSites[CSi] = CallSites.back();
638  CallSites.pop_back();
639  } else {
640  CallSites.erase(CallSites.begin() + CSi);
641  }
642  --CSi;
643 
644  Changed = true;
645  LocalChange = true;
646  }
647  } while (LocalChange);
648 
649  return Changed;
650 }
651 
653  CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
654  ACT = &getAnalysis<AssumptionCacheTracker>();
655  PSI = getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
656  auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
657  auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & {
658  return ACT->getAssumptionCache(F);
659  };
660  return inlineCallsImpl(SCC, CG, GetAssumptionCache, PSI, TLI, InsertLifetime,
661  [this](CallSite CS) { return getInlineCost(CS); },
663 }
664 
665 /// Remove now-dead linkonce functions at the end of
666 /// processing to avoid breaking the SCC traversal.
668  if (InlinerFunctionImportStats != InlinerFunctionImportStatsOpts::No)
669  ImportedFunctionsStats.dump(InlinerFunctionImportStats ==
670  InlinerFunctionImportStatsOpts::Verbose);
671  return removeDeadFunctions(CG);
672 }
673 
674 /// Remove dead functions that are not included in DNR (Do Not Remove) list.
676  bool AlwaysInlineOnly) {
677  SmallVector<CallGraphNode *, 16> FunctionsToRemove;
678  SmallVector<Function *, 16> DeadFunctionsInComdats;
679 
680  auto RemoveCGN = [&](CallGraphNode *CGN) {
681  // Remove any call graph edges from the function to its callees.
682  CGN->removeAllCalledFunctions();
683 
684  // Remove any edges from the external node to the function's call graph
685  // node. These edges might have been made irrelegant due to
686  // optimization of the program.
688 
689  // Removing the node for callee from the call graph and delete it.
690  FunctionsToRemove.push_back(CGN);
691  };
692 
693  // Scan for all of the functions, looking for ones that should now be removed
694  // from the program. Insert the dead ones in the FunctionsToRemove set.
695  for (const auto &I : CG) {
696  CallGraphNode *CGN = I.second.get();
697  Function *F = CGN->getFunction();
698  if (!F || F->isDeclaration())
699  continue;
700 
701  // Handle the case when this function is called and we only want to care
702  // about always-inline functions. This is a bit of a hack to share code
703  // between here and the InlineAlways pass.
704  if (AlwaysInlineOnly && !F->hasFnAttribute(Attribute::AlwaysInline))
705  continue;
706 
707  // If the only remaining users of the function are dead constants, remove
708  // them.
710 
711  if (!F->isDefTriviallyDead())
712  continue;
713 
714  // It is unsafe to drop a function with discardable linkage from a COMDAT
715  // without also dropping the other members of the COMDAT.
716  // The inliner doesn't visit non-function entities which are in COMDAT
717  // groups so it is unsafe to do so *unless* the linkage is local.
718  if (!F->hasLocalLinkage()) {
719  if (F->hasComdat()) {
720  DeadFunctionsInComdats.push_back(F);
721  continue;
722  }
723  }
724 
725  RemoveCGN(CGN);
726  }
727  if (!DeadFunctionsInComdats.empty()) {
728  // Filter out the functions whose comdats remain alive.
729  filterDeadComdatFunctions(CG.getModule(), DeadFunctionsInComdats);
730  // Remove the rest.
731  for (Function *F : DeadFunctionsInComdats)
732  RemoveCGN(CG[F]);
733  }
734 
735  if (FunctionsToRemove.empty())
736  return false;
737 
738  // Now that we know which functions to delete, do so. We didn't want to do
739  // this inline, because that would invalidate our CallGraph::iterator
740  // objects. :(
741  //
742  // Note that it doesn't matter that we are iterating over a non-stable order
743  // here to do this, it doesn't matter which order the functions are deleted
744  // in.
745  array_pod_sort(FunctionsToRemove.begin(), FunctionsToRemove.end());
746  FunctionsToRemove.erase(
747  std::unique(FunctionsToRemove.begin(), FunctionsToRemove.end()),
748  FunctionsToRemove.end());
749  for (CallGraphNode *CGN : FunctionsToRemove) {
750  delete CG.removeFunctionFromModule(CGN);
751  ++NumDeleted;
752  }
753  return true;
754 }
755 
758  CGSCCUpdateResult &UR) {
759  const ModuleAnalysisManager &MAM =
760  AM.getResult<ModuleAnalysisManagerCGSCCProxy>(InitialC, CG).getManager();
761  bool Changed = false;
762 
763  assert(InitialC.size() > 0 && "Cannot handle an empty SCC!");
764  Module &M = *InitialC.begin()->getFunction().getParent();
766 
767  // We use a single common worklist for calls across the entire SCC. We
768  // process these in-order and append new calls introduced during inlining to
769  // the end.
770  //
771  // Note that this particular order of processing is actually critical to
772  // avoid very bad behaviors. Consider *highly connected* call graphs where
773  // each function contains a small amonut of code and a couple of calls to
774  // other functions. Because the LLVM inliner is fundamentally a bottom-up
775  // inliner, it can handle gracefully the fact that these all appear to be
776  // reasonable inlining candidates as it will flatten things until they become
777  // too big to inline, and then move on and flatten another batch.
778  //
779  // However, when processing call edges *within* an SCC we cannot rely on this
780  // bottom-up behavior. As a consequence, with heavily connected *SCCs* of
781  // functions we can end up incrementally inlining N calls into each of
782  // N functions because each incremental inlining decision looks good and we
783  // don't have a topological ordering to prevent explosions.
784  //
785  // To compensate for this, we don't process transitive edges made immediate
786  // by inlining until we've done one pass of inlining across the entire SCC.
787  // Large, highly connected SCCs still lead to some amount of code bloat in
788  // this model, but it is uniformly spread across all the functions in the SCC
789  // and eventually they all become too large to inline, rather than
790  // incrementally maknig a single function grow in a super linear fashion.
792 
793  // Populate the initial list of calls in this SCC.
794  for (auto &N : InitialC) {
795  // We want to generally process call sites top-down in order for
796  // simplifications stemming from replacing the call with the returned value
797  // after inlining to be visible to subsequent inlining decisions.
798  // FIXME: Using instructions sequence is a really bad way to do this.
799  // Instead we should do an actual RPO walk of the function body.
800  for (Instruction &I : instructions(N.getFunction()))
801  if (auto CS = CallSite(&I))
802  if (Function *Callee = CS.getCalledFunction())
803  if (!Callee->isDeclaration())
804  Calls.push_back({CS, -1});
805  }
806  if (Calls.empty())
807  return PreservedAnalyses::all();
808 
809  // Capture updatable variables for the current SCC and RefSCC.
810  auto *C = &InitialC;
811  auto *RC = &C->getOuterRefSCC();
812 
813  // When inlining a callee produces new call sites, we want to keep track of
814  // the fact that they were inlined from the callee. This allows us to avoid
815  // infinite inlining in some obscure cases. To represent this, we use an
816  // index into the InlineHistory vector.
817  SmallVector<std::pair<Function *, int>, 16> InlineHistory;
818 
819  // Track a set vector of inlined callees so that we can augment the caller
820  // with all of their edges in the call graph before pruning out the ones that
821  // got simplified away.
822  SmallSetVector<Function *, 4> InlinedCallees;
823 
824  // Track the dead functions to delete once finished with inlining calls. We
825  // defer deleting these to make it easier to handle the call graph updates.
826  SmallVector<Function *, 4> DeadFunctions;
827 
828  // Loop forward over all of the calls. Note that we cannot cache the size as
829  // inlining can introduce new calls that need to be processed.
830  for (int i = 0; i < (int)Calls.size(); ++i) {
831  // We expect the calls to typically be batched with sequences of calls that
832  // have the same caller, so we first set up some shared infrastructure for
833  // this caller. We also do any pruning we can at this layer on the caller
834  // alone.
835  Function &F = *Calls[i].first.getCaller();
836  LazyCallGraph::Node &N = *CG.lookup(F);
837  if (CG.lookupSCC(N) != C)
838  continue;
839  if (F.hasFnAttribute(Attribute::OptimizeNone))
840  continue;
841 
842  DEBUG(dbgs() << "Inlining calls in: " << F.getName() << "\n");
843 
844  // Get a FunctionAnalysisManager via a proxy for this particular node. We
845  // do this each time we visit a node as the SCC may have changed and as
846  // we're going to mutate this particular function we want to make sure the
847  // proxy is in place to forward any invalidation events. We can use the
848  // manager we get here for looking up results for functions other than this
849  // node however because those functions aren't going to be mutated by this
850  // pass.
853  .getManager();
854 
855  // Get the remarks emission analysis for the caller.
856  auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(F);
857 
858  std::function<AssumptionCache &(Function &)> GetAssumptionCache =
859  [&](Function &F) -> AssumptionCache & {
860  return FAM.getResult<AssumptionAnalysis>(F);
861  };
862  auto GetBFI = [&](Function &F) -> BlockFrequencyInfo & {
863  return FAM.getResult<BlockFrequencyAnalysis>(F);
864  };
865 
866  auto GetInlineCost = [&](CallSite CS) {
868  auto &CalleeTTI = FAM.getResult<TargetIRAnalysis>(Callee);
869  return getInlineCost(CS, Params, CalleeTTI, GetAssumptionCache, {GetBFI},
870  PSI, &ORE);
871  };
872 
873  // Now process as many calls as we have within this caller in the sequnece.
874  // We bail out as soon as the caller has to change so we can update the
875  // call graph and prepare the context of that new caller.
876  bool DidInline = false;
877  for (; i < (int)Calls.size() && Calls[i].first.getCaller() == &F; ++i) {
878  int InlineHistoryID;
879  CallSite CS;
880  std::tie(CS, InlineHistoryID) = Calls[i];
882 
883  if (InlineHistoryID != -1 &&
884  InlineHistoryIncludes(&Callee, InlineHistoryID, InlineHistory))
885  continue;
886 
887  // Check if this inlining may repeat breaking an SCC apart that has
888  // already been split once before. In that case, inlining here may
889  // trigger infinite inlining, much like is prevented within the inliner
890  // itself by the InlineHistory above, but spread across CGSCC iterations
891  // and thus hidden from the full inline history.
892  if (CG.lookupSCC(*CG.lookup(Callee)) == C &&
893  UR.InlinedInternalEdges.count({&N, C})) {
894  DEBUG(dbgs() << "Skipping inlining internal SCC edge from a node "
895  "previously split out of this SCC by inlining: "
896  << F.getName() << " -> " << Callee.getName() << "\n");
897  continue;
898  }
899 
900  Optional<InlineCost> OIC = shouldInline(CS, GetInlineCost, ORE);
901  // Check whether we want to inline this callsite.
902  if (!OIC)
903  continue;
904 
905  // Setup the data structure used to plumb customization into the
906  // `InlineFunction` routine.
907  InlineFunctionInfo IFI(
908  /*cg=*/nullptr, &GetAssumptionCache, PSI,
909  &FAM.getResult<BlockFrequencyAnalysis>(*(CS.getCaller())),
910  &FAM.getResult<BlockFrequencyAnalysis>(Callee));
911 
912  // Get DebugLoc to report. CS will be invalid after Inliner.
913  DebugLoc DLoc = CS->getDebugLoc();
914  BasicBlock *Block = CS.getParent();
915 
916  using namespace ore;
917  if (!InlineFunction(CS, IFI)) {
918  ORE.emit(
919  OptimizationRemarkMissed(DEBUG_TYPE, "NotInlined", DLoc, Block)
920  << NV("Callee", &Callee) << " will not be inlined into "
921  << NV("Caller", &F));
922  continue;
923  }
924  DidInline = true;
925  InlinedCallees.insert(&Callee);
926 
927  if (OIC->isAlways())
928  ORE.emit(OptimizationRemark(DEBUG_TYPE, "AlwaysInline", DLoc, Block)
929  << NV("Callee", &Callee) << " inlined into "
930  << NV("Caller", &F) << " with cost=always");
931  else
932  ORE.emit(
933  OptimizationRemark(DEBUG_TYPE, "Inlined", DLoc, Block)
934  << NV("Callee", &Callee) << " inlined into " << NV("Caller", &F)
935  << " with cost=" << NV("Cost", OIC->getCost())
936  << " (threshold=" << NV("Threshold", OIC->getThreshold()) << ")");
937 
938  // Add any new callsites to defined functions to the worklist.
939  if (!IFI.InlinedCallSites.empty()) {
940  int NewHistoryID = InlineHistory.size();
941  InlineHistory.push_back({&Callee, InlineHistoryID});
942  for (CallSite &CS : reverse(IFI.InlinedCallSites))
943  if (Function *NewCallee = CS.getCalledFunction())
944  if (!NewCallee->isDeclaration())
945  Calls.push_back({CS, NewHistoryID});
946  }
947 
948  // Merge the attributes based on the inlining.
950 
951  // For local functions, check whether this makes the callee trivially
952  // dead. In that case, we can drop the body of the function eagerly
953  // which may reduce the number of callers of other functions to one,
954  // changing inline cost thresholds.
955  if (Callee.hasLocalLinkage()) {
956  // To check this we also need to nuke any dead constant uses (perhaps
957  // made dead by this operation on other functions).
958  Callee.removeDeadConstantUsers();
959  if (Callee.use_empty() && !CG.isLibFunction(Callee)) {
960  Calls.erase(
961  std::remove_if(Calls.begin() + i + 1, Calls.end(),
962  [&Callee](const std::pair<CallSite, int> &Call) {
963  return Call.first.getCaller() == &Callee;
964  }),
965  Calls.end());
966  // Clear the body and queue the function itself for deletion when we
967  // finish inlining and call graph updates.
968  // Note that after this point, it is an error to do anything other
969  // than use the callee's address or delete it.
970  Callee.dropAllReferences();
971  assert(find(DeadFunctions, &Callee) == DeadFunctions.end() &&
972  "Cannot put cause a function to become dead twice!");
973  DeadFunctions.push_back(&Callee);
974  }
975  }
976  }
977 
978  // Back the call index up by one to put us in a good position to go around
979  // the outer loop.
980  --i;
981 
982  if (!DidInline)
983  continue;
984  Changed = true;
985 
986  // Add all the inlined callees' edges as ref edges to the caller. These are
987  // by definition trivial edges as we always have *some* transitive ref edge
988  // chain. While in some cases these edges are direct calls inside the
989  // callee, they have to be modeled in the inliner as reference edges as
990  // there may be a reference edge anywhere along the chain from the current
991  // caller to the callee that causes the whole thing to appear like
992  // a (transitive) reference edge that will require promotion to a call edge
993  // below.
994  for (Function *InlinedCallee : InlinedCallees) {
995  LazyCallGraph::Node &CalleeN = *CG.lookup(*InlinedCallee);
996  for (LazyCallGraph::Edge &E : *CalleeN)
997  RC->insertTrivialRefEdge(N, E.getNode());
998  }
999 
1000  // At this point, since we have made changes we have at least removed
1001  // a call instruction. However, in the process we do some incremental
1002  // simplification of the surrounding code. This simplification can
1003  // essentially do all of the same things as a function pass and we can
1004  // re-use the exact same logic for updating the call graph to reflect the
1005  // change.
1006  LazyCallGraph::SCC *OldC = C;
1007  C = &updateCGAndAnalysisManagerForFunctionPass(CG, *C, N, AM, UR);
1008  DEBUG(dbgs() << "Updated inlining SCC: " << *C << "\n");
1009  RC = &C->getOuterRefSCC();
1010 
1011  // If this causes an SCC to split apart into multiple smaller SCCs, there
1012  // is a subtle risk we need to prepare for. Other transformations may
1013  // expose an "infinite inlining" opportunity later, and because of the SCC
1014  // mutation, we will revisit this function and potentially re-inline. If we
1015  // do, and that re-inlining also has the potentially to mutate the SCC
1016  // structure, the infinite inlining problem can manifest through infinite
1017  // SCC splits and merges. To avoid this, we capture the originating caller
1018  // node and the SCC containing the call edge. This is a slight over
1019  // approximation of the possible inlining decisions that must be avoided,
1020  // but is relatively efficient to store.
1021  // FIXME: This seems like a very heavyweight way of retaining the inline
1022  // history, we should look for a more efficient way of tracking it.
1023  if (C != OldC && llvm::any_of(InlinedCallees, [&](Function *Callee) {
1024  return CG.lookupSCC(*CG.lookup(*Callee)) == OldC;
1025  })) {
1026  DEBUG(dbgs() << "Inlined an internal call edge and split an SCC, "
1027  "retaining this to avoid infinite inlining.\n");
1028  UR.InlinedInternalEdges.insert({&N, OldC});
1029  }
1030  InlinedCallees.clear();
1031  }
1032 
1033  // Now that we've finished inlining all of the calls across this SCC, delete
1034  // all of the trivially dead functions, updating the call graph and the CGSCC
1035  // pass manager in the process.
1036  //
1037  // Note that this walks a pointer set which has non-deterministic order but
1038  // that is OK as all we do is delete things and add pointers to unordered
1039  // sets.
1040  for (Function *DeadF : DeadFunctions) {
1041  // Get the necessary information out of the call graph and nuke the
1042  // function there. Also, cclear out any cached analyses.
1043  auto &DeadC = *CG.lookupSCC(*CG.lookup(*DeadF));
1046  .getManager();
1047  FAM.clear(*DeadF);
1048  AM.clear(DeadC);
1049  auto &DeadRC = DeadC.getOuterRefSCC();
1050  CG.removeDeadFunction(*DeadF);
1051 
1052  // Mark the relevant parts of the call graph as invalid so we don't visit
1053  // them.
1054  UR.InvalidatedSCCs.insert(&DeadC);
1055  UR.InvalidatedRefSCCs.insert(&DeadRC);
1056 
1057  // And delete the actual function from the module.
1058  M.getFunctionList().erase(DeadF);
1059  }
1060 
1061  if (!Changed)
1062  return PreservedAnalyses::all();
1063 
1064  // Even if we change the IR, we update the core CGSCC data structures and so
1065  // can preserve the proxy to the function analysis manager.
1066  PreservedAnalyses PA;
1068  return PA;
1069 }
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:667
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:99
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:406
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
LazyCallGraph::SCC & updateCGAndAnalysisManagerForFunctionPass(LazyCallGraph &G, LazyCallGraph::SCC &C, LazyCallGraph::Node &N, CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR)
Helper to update the call graph after running a function pass.
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:856
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:87
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:262
STATISTIC(NumFunctions, "Total number of functions")
A debug info location.
Definition: DebugLoc.h:34
F(f)
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:165
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:65
Module & getModule() const
Returns the module the call graph corresponds to.
Definition: CallGraph.h:114
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:425
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.
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:122
InstrTy * getInstruction() const
Definition: CallSite.h:92
PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG, CGSCCUpdateResult &UR)
Definition: Inliner.cpp:756
static Optional< InlineCost > shouldInline(CallSite CS, function_ref< InlineCost(CallSite CS)> GetInlineCost, OptimizationRemarkEmitter &ORE)
Return the cost only if the inliner should attempt to inline at the given CallSite.
Definition: Inliner.cpp:342
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:248
This file provides interfaces used to build and manipulate a call graph, which is a very useful tool ...
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:47
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
amdgpu Simplify well known AMD library false Value * Callee
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:406
bool isAlways() const
Definition: InlineCost.h:98
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:769
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:203
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:652
An analysis pass based on the new PM to deliver ProfileSummaryInfo.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
Definition: CommandLine.h:626
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:363
Diagnostic information for applied optimization remarks.
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:823
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:374
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:419
int getThreshold() const
Get the threshold against which the cost was computed.
Definition: InlineCost.h:110
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:188
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:432
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:410
void removeDeadFunction(Function &F)
Remove a dead function from the call graph (typically to delete it).
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:837
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
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:675
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:97
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:104
int getCostDelta() const
Get the cost delta from the threshold for inlining.
Definition: InlineCost.h:118
bool hasComdat() const
Definition: GlobalObject.h:100
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
Definition: CommandLine.h:601
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:74
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:120
FunTy * getCaller() const
Return the caller function for this call site.
Definition: CallSite.h:267
LegacyInlinerBase(char &ID)
Definition: Inliner.cpp:82
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
#define N
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
CallGraphNode * getExternalCallingNode() const
Returns the CallGraphNode which is used to represent undetermined calls into the callgraph.
Definition: CallGraph.h:137
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:107
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
SmallDenseSet< std::pair< LazyCallGraph::Node *, LazyCallGraph::SCC * >, 4 > & InlinedInternalEdges
A hacky area where the inliner can retain history about inlining decisions that mutated the call grap...
This represents the llvm.dbg.declare instruction.
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