LLVM  8.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/DenseMap.h"
18 #include "llvm/ADT/None.h"
19 #include "llvm/ADT/Optional.h"
20 #include "llvm/ADT/STLExtras.h"
21 #include "llvm/ADT/SetVector.h"
22 #include "llvm/ADT/SmallPtrSet.h"
23 #include "llvm/ADT/SmallVector.h"
24 #include "llvm/ADT/Statistic.h"
25 #include "llvm/ADT/StringRef.h"
39 #include "llvm/IR/Attributes.h"
40 #include "llvm/IR/BasicBlock.h"
41 #include "llvm/IR/CallSite.h"
42 #include "llvm/IR/DataLayout.h"
43 #include "llvm/IR/DebugLoc.h"
44 #include "llvm/IR/DerivedTypes.h"
45 #include "llvm/IR/DiagnosticInfo.h"
46 #include "llvm/IR/Function.h"
47 #include "llvm/IR/InstIterator.h"
48 #include "llvm/IR/Instruction.h"
49 #include "llvm/IR/Instructions.h"
50 #include "llvm/IR/IntrinsicInst.h"
51 #include "llvm/IR/Metadata.h"
52 #include "llvm/IR/Module.h"
53 #include "llvm/IR/PassManager.h"
54 #include "llvm/IR/User.h"
55 #include "llvm/IR/Value.h"
56 #include "llvm/Pass.h"
57 #include "llvm/Support/Casting.h"
59 #include "llvm/Support/Debug.h"
64 #include <algorithm>
65 #include <cassert>
66 #include <functional>
67 #include <sstream>
68 #include <tuple>
69 #include <utility>
70 #include <vector>
71 
72 using namespace llvm;
73 
74 #define DEBUG_TYPE "inline"
75 
76 STATISTIC(NumInlined, "Number of functions inlined");
77 STATISTIC(NumCallsDeleted, "Number of call sites deleted, not inlined");
78 STATISTIC(NumDeleted, "Number of functions deleted because all callers found");
79 STATISTIC(NumMergedAllocas, "Number of allocas merged together");
80 
81 // This weirdly named statistic tracks the number of times that, when attempting
82 // to inline a function A into B, we analyze the callers of B in order to see
83 // if those would be more profitable and blocked inline steps.
84 STATISTIC(NumCallerCallersAnalyzed, "Number of caller-callers analyzed");
85 
86 /// Flag to disable manual alloca merging.
87 ///
88 /// Merging of allocas was originally done as a stack-size saving technique
89 /// prior to LLVM's code generator having support for stack coloring based on
90 /// lifetime markers. It is now in the process of being removed. To experiment
91 /// with disabling it and relying fully on lifetime marker based stack
92 /// coloring, you can pass this flag to LLVM.
93 static cl::opt<bool>
94  DisableInlinedAllocaMerging("disable-inlined-alloca-merging",
95  cl::init(false), cl::Hidden);
96 
97 namespace {
98 
100  No = 0,
101  Basic = 1,
102  Verbose = 2,
103 };
104 
105 } // end anonymous namespace
106 
108  "inliner-function-import-stats",
110  cl::values(clEnumValN(InlinerFunctionImportStatsOpts::Basic, "basic",
111  "basic statistics"),
112  clEnumValN(InlinerFunctionImportStatsOpts::Verbose, "verbose",
113  "printing of statistics for each inlined function")),
114  cl::Hidden, cl::desc("Enable inliner stats for imported functions"));
115 
116 /// Flag to add inline messages as callsite attributes 'inline-remark'.
117 static cl::opt<bool>
118  InlineRemarkAttribute("inline-remark-attribute", cl::init(false),
119  cl::Hidden,
120  cl::desc("Enable adding inline-remark attribute to"
121  " callsites processed by inliner but decided"
122  " to be not inlined"));
123 
125 
126 LegacyInlinerBase::LegacyInlinerBase(char &ID, bool InsertLifetime)
127  : CallGraphSCCPass(ID), InsertLifetime(InsertLifetime) {}
128 
129 /// For this class, we declare that we require and preserve the call graph.
130 /// If the derived class implements this method, it should
131 /// always explicitly call the implementation here.
138 }
139 
141 
142 /// Look at all of the allocas that we inlined through this call site. If we
143 /// have already inlined other allocas through other calls into this function,
144 /// then we know that they have disjoint lifetimes and that we can merge them.
145 ///
146 /// There are many heuristics possible for merging these allocas, and the
147 /// different options have different tradeoffs. One thing that we *really*
148 /// don't want to hurt is SRoA: once inlining happens, often allocas are no
149 /// longer address taken and so they can be promoted.
150 ///
151 /// Our "solution" for that is to only merge allocas whose outermost type is an
152 /// array type. These are usually not promoted because someone is using a
153 /// variable index into them. These are also often the most important ones to
154 /// merge.
155 ///
156 /// A better solution would be to have real memory lifetime markers in the IR
157 /// and not have the inliner do any merging of allocas at all. This would
158 /// allow the backend to do proper stack slot coloring of all allocas that
159 /// *actually make it to the backend*, which is really what we want.
160 ///
161 /// Because we don't have this information, we do this simple and useful hack.
163  Function *Caller, InlineFunctionInfo &IFI,
164  InlinedArrayAllocasTy &InlinedArrayAllocas, int InlineHistory) {
165  SmallPtrSet<AllocaInst *, 16> UsedAllocas;
166 
167  // When processing our SCC, check to see if CS was inlined from some other
168  // call site. For example, if we're processing "A" in this code:
169  // A() { B() }
170  // B() { x = alloca ... C() }
171  // C() { y = alloca ... }
172  // Assume that C was not inlined into B initially, and so we're processing A
173  // and decide to inline B into A. Doing this makes an alloca available for
174  // reuse and makes a callsite (C) available for inlining. When we process
175  // the C call site we don't want to do any alloca merging between X and Y
176  // because their scopes are not disjoint. We could make this smarter by
177  // keeping track of the inline history for each alloca in the
178  // InlinedArrayAllocas but this isn't likely to be a significant win.
179  if (InlineHistory != -1) // Only do merging for top-level call sites in SCC.
180  return;
181 
182  // Loop over all the allocas we have so far and see if they can be merged with
183  // a previously inlined alloca. If not, remember that we had it.
184  for (unsigned AllocaNo = 0, e = IFI.StaticAllocas.size(); AllocaNo != e;
185  ++AllocaNo) {
186  AllocaInst *AI = IFI.StaticAllocas[AllocaNo];
187 
188  // Don't bother trying to merge array allocations (they will usually be
189  // canonicalized to be an allocation *of* an array), or allocations whose
190  // type is not itself an array (because we're afraid of pessimizing SRoA).
192  if (!ATy || AI->isArrayAllocation())
193  continue;
194 
195  // Get the list of all available allocas for this array type.
196  std::vector<AllocaInst *> &AllocasForType = InlinedArrayAllocas[ATy];
197 
198  // Loop over the allocas in AllocasForType to see if we can reuse one. Note
199  // that we have to be careful not to reuse the same "available" alloca for
200  // multiple different allocas that we just inlined, we use the 'UsedAllocas'
201  // set to keep track of which "available" allocas are being used by this
202  // function. Also, AllocasForType can be empty of course!
203  bool MergedAwayAlloca = false;
204  for (AllocaInst *AvailableAlloca : AllocasForType) {
205  unsigned Align1 = AI->getAlignment(),
206  Align2 = AvailableAlloca->getAlignment();
207 
208  // The available alloca has to be in the right function, not in some other
209  // function in this SCC.
210  if (AvailableAlloca->getParent() != AI->getParent())
211  continue;
212 
213  // If the inlined function already uses this alloca then we can't reuse
214  // it.
215  if (!UsedAllocas.insert(AvailableAlloca).second)
216  continue;
217 
218  // Otherwise, we *can* reuse it, RAUW AI into AvailableAlloca and declare
219  // success!
220  LLVM_DEBUG(dbgs() << " ***MERGED ALLOCA: " << *AI
221  << "\n\t\tINTO: " << *AvailableAlloca << '\n');
222 
223  // Move affected dbg.declare calls immediately after the new alloca to
224  // avoid the situation when a dbg.declare precedes its alloca.
225  if (auto *L = LocalAsMetadata::getIfExists(AI))
226  if (auto *MDV = MetadataAsValue::getIfExists(AI->getContext(), L))
227  for (User *U : MDV->users())
228  if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(U))
229  DDI->moveBefore(AvailableAlloca->getNextNode());
230 
231  AI->replaceAllUsesWith(AvailableAlloca);
232 
233  if (Align1 != Align2) {
234  if (!Align1 || !Align2) {
235  const DataLayout &DL = Caller->getParent()->getDataLayout();
236  unsigned TypeAlign = DL.getABITypeAlignment(AI->getAllocatedType());
237 
238  Align1 = Align1 ? Align1 : TypeAlign;
239  Align2 = Align2 ? Align2 : TypeAlign;
240  }
241 
242  if (Align1 > Align2)
243  AvailableAlloca->setAlignment(AI->getAlignment());
244  }
245 
246  AI->eraseFromParent();
247  MergedAwayAlloca = true;
248  ++NumMergedAllocas;
249  IFI.StaticAllocas[AllocaNo] = nullptr;
250  break;
251  }
252 
253  // If we already nuked the alloca, we're done with it.
254  if (MergedAwayAlloca)
255  continue;
256 
257  // If we were unable to merge away the alloca either because there are no
258  // allocas of the right type available or because we reused them all
259  // already, remember that this alloca came from an inlined function and mark
260  // it used so we don't reuse it for other allocas from this inline
261  // operation.
262  AllocasForType.push_back(AI);
263  UsedAllocas.insert(AI);
264  }
265 }
266 
267 /// If it is possible to inline the specified call site,
268 /// do so and update the CallGraph for this operation.
269 ///
270 /// This function also does some basic book-keeping to update the IR. The
271 /// InlinedArrayAllocas map keeps track of any allocas that are already
272 /// available from other functions inlined into the caller. If we are able to
273 /// inline this call site we attempt to reuse already available allocas or add
274 /// any new allocas to the set if not possible.
276  CallSite CS, InlineFunctionInfo &IFI,
277  InlinedArrayAllocasTy &InlinedArrayAllocas, int InlineHistory,
278  bool InsertLifetime, function_ref<AAResults &(Function &)> &AARGetter,
281  Function *Caller = CS.getCaller();
282 
283  AAResults &AAR = AARGetter(*Callee);
284 
285  // Try to inline the function. Get the list of static allocas that were
286  // inlined.
287  InlineResult IR = InlineFunction(CS, IFI, &AAR, InsertLifetime);
288  if (!IR)
289  return IR;
290 
291  if (InlinerFunctionImportStats != InlinerFunctionImportStatsOpts::No)
292  ImportedFunctionsStats.recordInline(*Caller, *Callee);
293 
295 
297  mergeInlinedArrayAllocas(Caller, IFI, InlinedArrayAllocas, InlineHistory);
298 
299  return IR; // success
300 }
301 
302 /// Return true if inlining of CS can block the caller from being
303 /// inlined which is proved to be more beneficial. \p IC is the
304 /// estimated inline cost associated with callsite \p CS.
305 /// \p TotalSecondaryCost will be set to the estimated cost of inlining the
306 /// caller if \p CS is suppressed for inlining.
307 static bool
309  int &TotalSecondaryCost,
310  function_ref<InlineCost(CallSite CS)> GetInlineCost) {
311  // For now we only handle local or inline functions.
312  if (!Caller->hasLocalLinkage() && !Caller->hasLinkOnceODRLinkage())
313  return false;
314  // Try to detect the case where the current inlining candidate caller (call
315  // it B) is a static or linkonce-ODR function and is an inlining candidate
316  // elsewhere, and the current candidate callee (call it C) is large enough
317  // that inlining it into B would make B too big to inline later. In these
318  // circumstances it may be best not to inline C into B, but to inline B into
319  // its callers.
320  //
321  // This only applies to static and linkonce-ODR functions because those are
322  // expected to be available for inlining in the translation units where they
323  // are used. Thus we will always have the opportunity to make local inlining
324  // decisions. Importantly the linkonce-ODR linkage covers inline functions
325  // and templates in C++.
326  //
327  // FIXME: All of this logic should be sunk into getInlineCost. It relies on
328  // the internal implementation of the inline cost metrics rather than
329  // treating them as truly abstract units etc.
330  TotalSecondaryCost = 0;
331  // The candidate cost to be imposed upon the current function.
332  int CandidateCost = IC.getCost() - 1;
333  // This bool tracks what happens if we do NOT inline C into B.
334  bool callerWillBeRemoved = Caller->hasLocalLinkage();
335  // This bool tracks what happens if we DO inline C into B.
336  bool inliningPreventsSomeOuterInline = false;
337  for (User *U : Caller->users()) {
338  CallSite CS2(U);
339 
340  // If this isn't a call to Caller (it could be some other sort
341  // of reference) skip it. Such references will prevent the caller
342  // from being removed.
343  if (!CS2 || CS2.getCalledFunction() != Caller) {
344  callerWillBeRemoved = false;
345  continue;
346  }
347 
348  InlineCost IC2 = GetInlineCost(CS2);
349  ++NumCallerCallersAnalyzed;
350  if (!IC2) {
351  callerWillBeRemoved = false;
352  continue;
353  }
354  if (IC2.isAlways())
355  continue;
356 
357  // See if inlining of the original callsite would erase the cost delta of
358  // this callsite. We subtract off the penalty for the call instruction,
359  // which we would be deleting.
360  if (IC2.getCostDelta() <= CandidateCost) {
361  inliningPreventsSomeOuterInline = true;
362  TotalSecondaryCost += IC2.getCost();
363  }
364  }
365  // If all outer calls to Caller would get inlined, the cost for the last
366  // one is set very low by getInlineCost, in anticipation that Caller will
367  // be removed entirely. We did not account for this above unless there
368  // is only one caller of Caller.
369  if (callerWillBeRemoved && !Caller->hasOneUse())
370  TotalSecondaryCost -= InlineConstants::LastCallToStaticBonus;
371 
372  if (inliningPreventsSomeOuterInline && TotalSecondaryCost < IC.getCost())
373  return true;
374 
375  return false;
376 }
377 
378 static std::basic_ostream<char> &operator<<(std::basic_ostream<char> &R,
379  const ore::NV &Arg) {
380  return R << Arg.Val;
381 }
382 
383 template <class RemarkT>
384 RemarkT &operator<<(RemarkT &&R, const InlineCost &IC) {
385  using namespace ore;
386  if (IC.isAlways()) {
387  R << "(cost=always)";
388  } else if (IC.isNever()) {
389  R << "(cost=never)";
390  } else {
391  R << "(cost=" << ore::NV("Cost", IC.getCost())
392  << ", threshold=" << ore::NV("Threshold", IC.getThreshold()) << ")";
393  }
394  if (const char *Reason = IC.getReason())
395  R << ": " << ore::NV("Reason", Reason);
396  return R;
397 }
398 
399 static std::string inlineCostStr(const InlineCost &IC) {
400  std::stringstream Remark;
401  Remark << IC;
402  return Remark.str();
403 }
404 
405 /// Return the cost only if the inliner should attempt to inline at the given
406 /// CallSite. If we return the cost, we will emit an optimisation remark later
407 /// using that cost, so we won't do so from this function.
411  using namespace ore;
412 
413  InlineCost IC = GetInlineCost(CS);
414  Instruction *Call = CS.getInstruction();
416  Function *Caller = CS.getCaller();
417 
418  if (IC.isAlways()) {
419  LLVM_DEBUG(dbgs() << " Inlining " << inlineCostStr(IC)
420  << ", Call: " << *CS.getInstruction() << "\n");
421  return IC;
422  }
423 
424  if (IC.isNever()) {
425  LLVM_DEBUG(dbgs() << " NOT Inlining " << inlineCostStr(IC)
426  << ", Call: " << *CS.getInstruction() << "\n");
427  ORE.emit([&]() {
428  return OptimizationRemarkMissed(DEBUG_TYPE, "NeverInline", Call)
429  << NV("Callee", Callee) << " not inlined into "
430  << NV("Caller", Caller) << " because it should never be inlined "
431  << IC;
432  });
433  return IC;
434  }
435 
436  if (!IC) {
437  LLVM_DEBUG(dbgs() << " NOT Inlining " << inlineCostStr(IC)
438  << ", Call: " << *CS.getInstruction() << "\n");
439  ORE.emit([&]() {
440  return OptimizationRemarkMissed(DEBUG_TYPE, "TooCostly", Call)
441  << NV("Callee", Callee) << " not inlined into "
442  << NV("Caller", Caller) << " because too costly to inline " << IC;
443  });
444  return IC;
445  }
446 
447  int TotalSecondaryCost = 0;
448  if (shouldBeDeferred(Caller, CS, IC, TotalSecondaryCost, GetInlineCost)) {
449  LLVM_DEBUG(dbgs() << " NOT Inlining: " << *CS.getInstruction()
450  << " Cost = " << IC.getCost()
451  << ", outer Cost = " << TotalSecondaryCost << '\n');
452  ORE.emit([&]() {
453  return OptimizationRemarkMissed(DEBUG_TYPE, "IncreaseCostInOtherContexts",
454  Call)
455  << "Not inlining. Cost of inlining " << NV("Callee", Callee)
456  << " increases the cost of inlining " << NV("Caller", Caller)
457  << " in other contexts";
458  });
459 
460  // IC does not bool() to false, so get an InlineCost that will.
461  // This will not be inspected to make an error message.
462  return None;
463  }
464 
465  LLVM_DEBUG(dbgs() << " Inlining " << inlineCostStr(IC)
466  << ", Call: " << *CS.getInstruction() << '\n');
467  return IC;
468 }
469 
470 /// Return true if the specified inline history ID
471 /// indicates an inline history that includes the specified function.
473  Function *F, int InlineHistoryID,
474  const SmallVectorImpl<std::pair<Function *, int>> &InlineHistory) {
475  while (InlineHistoryID != -1) {
476  assert(unsigned(InlineHistoryID) < InlineHistory.size() &&
477  "Invalid inline history ID");
478  if (InlineHistory[InlineHistoryID].first == F)
479  return true;
480  InlineHistoryID = InlineHistory[InlineHistoryID].second;
481  }
482  return false;
483 }
484 
486  if (InlinerFunctionImportStats != InlinerFunctionImportStatsOpts::No)
488  return false; // No changes to CallGraph.
489 }
490 
492  if (skipSCC(SCC))
493  return false;
494  return inlineCalls(SCC);
495 }
496 
498  const BasicBlock *Block, const Function &Callee,
499  const Function &Caller, const InlineCost &IC) {
500  ORE.emit([&]() {
501  bool AlwaysInline = IC.isAlways();
502  StringRef RemarkName = AlwaysInline ? "AlwaysInline" : "Inlined";
503  return OptimizationRemark(DEBUG_TYPE, RemarkName, DLoc, Block)
504  << ore::NV("Callee", &Callee) << " inlined into "
505  << ore::NV("Caller", &Caller) << " with " << IC;
506  });
507 }
508 
509 static void setInlineRemark(CallSite &CS, StringRef message) {
510  if (!InlineRemarkAttribute)
511  return;
512 
513  Attribute attr = Attribute::get(CS->getContext(), "inline-remark", message);
515 }
516 
517 static bool
519  std::function<AssumptionCache &(Function &)> GetAssumptionCache,
521  bool InsertLifetime,
522  function_ref<InlineCost(CallSite CS)> GetInlineCost,
523  function_ref<AAResults &(Function &)> AARGetter,
525  SmallPtrSet<Function *, 8> SCCFunctions;
526  LLVM_DEBUG(dbgs() << "Inliner visiting SCC:");
527  for (CallGraphNode *Node : SCC) {
528  Function *F = Node->getFunction();
529  if (F)
530  SCCFunctions.insert(F);
531  LLVM_DEBUG(dbgs() << " " << (F ? F->getName() : "INDIRECTNODE"));
532  }
533 
534  // Scan through and identify all call sites ahead of time so that we only
535  // inline call sites in the original functions, not call sites that result
536  // from inlining other functions.
538 
539  // When inlining a callee produces new call sites, we want to keep track of
540  // the fact that they were inlined from the callee. This allows us to avoid
541  // infinite inlining in some obscure cases. To represent this, we use an
542  // index into the InlineHistory vector.
543  SmallVector<std::pair<Function *, int>, 8> InlineHistory;
544 
545  for (CallGraphNode *Node : SCC) {
546  Function *F = Node->getFunction();
547  if (!F || F->isDeclaration())
548  continue;
549 
551  for (BasicBlock &BB : *F)
552  for (Instruction &I : BB) {
553  CallSite CS(cast<Value>(&I));
554  // If this isn't a call, or it is a call to an intrinsic, it can
555  // never be inlined.
556  if (!CS || isa<IntrinsicInst>(I))
557  continue;
558 
559  // If this is a direct call to an external function, we can never inline
560  // it. If it is an indirect call, inlining may resolve it to be a
561  // direct call, so we keep it.
562  if (Function *Callee = CS.getCalledFunction())
563  if (Callee->isDeclaration()) {
564  using namespace ore;
565 
566  setInlineRemark(CS, "unavailable definition");
567  ORE.emit([&]() {
568  return OptimizationRemarkMissed(DEBUG_TYPE, "NoDefinition", &I)
569  << NV("Callee", Callee) << " will not be inlined into "
570  << NV("Caller", CS.getCaller())
571  << " because its definition is unavailable"
572  << setIsVerbose();
573  });
574  continue;
575  }
576 
577  CallSites.push_back(std::make_pair(CS, -1));
578  }
579  }
580 
581  LLVM_DEBUG(dbgs() << ": " << CallSites.size() << " call sites.\n");
582 
583  // If there are no calls in this function, exit early.
584  if (CallSites.empty())
585  return false;
586 
587  // Now that we have all of the call sites, move the ones to functions in the
588  // current SCC to the end of the list.
589  unsigned FirstCallInSCC = CallSites.size();
590  for (unsigned i = 0; i < FirstCallInSCC; ++i)
591  if (Function *F = CallSites[i].first.getCalledFunction())
592  if (SCCFunctions.count(F))
593  std::swap(CallSites[i--], CallSites[--FirstCallInSCC]);
594 
595  InlinedArrayAllocasTy InlinedArrayAllocas;
596  InlineFunctionInfo InlineInfo(&CG, &GetAssumptionCache, PSI);
597 
598  // Now that we have all of the call sites, loop over them and inline them if
599  // it looks profitable to do so.
600  bool Changed = false;
601  bool LocalChange;
602  do {
603  LocalChange = false;
604  // Iterate over the outer loop because inlining functions can cause indirect
605  // calls to become direct calls.
606  // CallSites may be modified inside so ranged for loop can not be used.
607  for (unsigned CSi = 0; CSi != CallSites.size(); ++CSi) {
608  CallSite CS = CallSites[CSi].first;
609 
610  Function *Caller = CS.getCaller();
612 
613  // We can only inline direct calls to non-declarations.
614  if (!Callee || Callee->isDeclaration())
615  continue;
616 
617  Instruction *Instr = CS.getInstruction();
618 
619  bool IsTriviallyDead = isInstructionTriviallyDead(Instr, &TLI);
620 
621  int InlineHistoryID;
622  if (!IsTriviallyDead) {
623  // If this call site was obtained by inlining another function, verify
624  // that the include path for the function did not include the callee
625  // itself. If so, we'd be recursively inlining the same function,
626  // which would provide the same callsites, which would cause us to
627  // infinitely inline.
628  InlineHistoryID = CallSites[CSi].second;
629  if (InlineHistoryID != -1 &&
630  InlineHistoryIncludes(Callee, InlineHistoryID, InlineHistory)) {
631  setInlineRemark(CS, "recursive");
632  continue;
633  }
634  }
635 
636  // FIXME for new PM: because of the old PM we currently generate ORE and
637  // in turn BFI on demand. With the new PM, the ORE dependency should
638  // just become a regular analysis dependency.
639  OptimizationRemarkEmitter ORE(Caller);
640 
641  Optional<InlineCost> OIC = shouldInline(CS, GetInlineCost, ORE);
642  // If the policy determines that we should inline this function,
643  // delete the call instead.
644  if (!OIC.hasValue()) {
645  setInlineRemark(CS, "deferred");
646  continue;
647  }
648 
649  if (!OIC.getValue()) {
650  // shouldInline() call returned a negative inline cost that explains
651  // why this callsite should not be inlined.
652  setInlineRemark(CS, inlineCostStr(*OIC));
653  continue;
654  }
655 
656  // If this call site is dead and it is to a readonly function, we should
657  // just delete the call instead of trying to inline it, regardless of
658  // size. This happens because IPSCCP propagates the result out of the
659  // call and then we're left with the dead call.
660  if (IsTriviallyDead) {
661  LLVM_DEBUG(dbgs() << " -> Deleting dead call: " << *Instr << "\n");
662  // Update the call graph by deleting the edge from Callee to Caller.
663  setInlineRemark(CS, "trivially dead");
664  CG[Caller]->removeCallEdgeFor(CS);
665  Instr->eraseFromParent();
666  ++NumCallsDeleted;
667  } else {
668  // Get DebugLoc to report. CS will be invalid after Inliner.
669  DebugLoc DLoc = CS->getDebugLoc();
670  BasicBlock *Block = CS.getParent();
671 
672  // Attempt to inline the function.
673  using namespace ore;
674 
676  CS, InlineInfo, InlinedArrayAllocas, InlineHistoryID,
677  InsertLifetime, AARGetter, ImportedFunctionsStats);
678  if (!IR) {
679  setInlineRemark(CS, std::string(IR) + "; " + inlineCostStr(*OIC));
680  ORE.emit([&]() {
681  return OptimizationRemarkMissed(DEBUG_TYPE, "NotInlined", DLoc,
682  Block)
683  << NV("Callee", Callee) << " will not be inlined into "
684  << NV("Caller", Caller) << ": " << NV("Reason", IR.message);
685  });
686  continue;
687  }
688  ++NumInlined;
689 
690  emit_inlined_into(ORE, DLoc, Block, *Callee, *Caller, *OIC);
691 
692  // If inlining this function gave us any new call sites, throw them
693  // onto our worklist to process. They are useful inline candidates.
694  if (!InlineInfo.InlinedCalls.empty()) {
695  // Create a new inline history entry for this, so that we remember
696  // that these new callsites came about due to inlining Callee.
697  int NewHistoryID = InlineHistory.size();
698  InlineHistory.push_back(std::make_pair(Callee, InlineHistoryID));
699 
700  for (Value *Ptr : InlineInfo.InlinedCalls)
701  CallSites.push_back(std::make_pair(CallSite(Ptr), NewHistoryID));
702  }
703  }
704 
705  // If we inlined or deleted the last possible call site to the function,
706  // delete the function body now.
707  if (Callee && Callee->use_empty() && Callee->hasLocalLinkage() &&
708  // TODO: Can remove if in SCC now.
709  !SCCFunctions.count(Callee) &&
710  // The function may be apparently dead, but if there are indirect
711  // callgraph references to the node, we cannot delete it yet, this
712  // could invalidate the CGSCC iterator.
713  CG[Callee]->getNumReferences() == 0) {
714  LLVM_DEBUG(dbgs() << " -> Deleting dead function: "
715  << Callee->getName() << "\n");
716  CallGraphNode *CalleeNode = CG[Callee];
717 
718  // Remove any call graph edges from the callee to its callees.
719  CalleeNode->removeAllCalledFunctions();
720 
721  // Removing the node for callee from the call graph and delete it.
722  delete CG.removeFunctionFromModule(CalleeNode);
723  ++NumDeleted;
724  }
725 
726  // Remove this call site from the list. If possible, use
727  // swap/pop_back for efficiency, but do not use it if doing so would
728  // move a call site to a function in this SCC before the
729  // 'FirstCallInSCC' barrier.
730  if (SCC.isSingular()) {
731  CallSites[CSi] = CallSites.back();
732  CallSites.pop_back();
733  } else {
734  CallSites.erase(CallSites.begin() + CSi);
735  }
736  --CSi;
737 
738  Changed = true;
739  LocalChange = true;
740  }
741  } while (LocalChange);
742 
743  return Changed;
744 }
745 
747  CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
748  ACT = &getAnalysis<AssumptionCacheTracker>();
749  PSI = getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
750  auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
751  auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & {
752  return ACT->getAssumptionCache(F);
753  };
754  return inlineCallsImpl(SCC, CG, GetAssumptionCache, PSI, TLI, InsertLifetime,
755  [this](CallSite CS) { return getInlineCost(CS); },
757 }
758 
759 /// Remove now-dead linkonce functions at the end of
760 /// processing to avoid breaking the SCC traversal.
762  if (InlinerFunctionImportStats != InlinerFunctionImportStatsOpts::No)
763  ImportedFunctionsStats.dump(InlinerFunctionImportStats ==
764  InlinerFunctionImportStatsOpts::Verbose);
765  return removeDeadFunctions(CG);
766 }
767 
768 /// Remove dead functions that are not included in DNR (Do Not Remove) list.
770  bool AlwaysInlineOnly) {
771  SmallVector<CallGraphNode *, 16> FunctionsToRemove;
772  SmallVector<Function *, 16> DeadFunctionsInComdats;
773 
774  auto RemoveCGN = [&](CallGraphNode *CGN) {
775  // Remove any call graph edges from the function to its callees.
776  CGN->removeAllCalledFunctions();
777 
778  // Remove any edges from the external node to the function's call graph
779  // node. These edges might have been made irrelegant due to
780  // optimization of the program.
782 
783  // Removing the node for callee from the call graph and delete it.
784  FunctionsToRemove.push_back(CGN);
785  };
786 
787  // Scan for all of the functions, looking for ones that should now be removed
788  // from the program. Insert the dead ones in the FunctionsToRemove set.
789  for (const auto &I : CG) {
790  CallGraphNode *CGN = I.second.get();
791  Function *F = CGN->getFunction();
792  if (!F || F->isDeclaration())
793  continue;
794 
795  // Handle the case when this function is called and we only want to care
796  // about always-inline functions. This is a bit of a hack to share code
797  // between here and the InlineAlways pass.
798  if (AlwaysInlineOnly && !F->hasFnAttribute(Attribute::AlwaysInline))
799  continue;
800 
801  // If the only remaining users of the function are dead constants, remove
802  // them.
804 
805  if (!F->isDefTriviallyDead())
806  continue;
807 
808  // It is unsafe to drop a function with discardable linkage from a COMDAT
809  // without also dropping the other members of the COMDAT.
810  // The inliner doesn't visit non-function entities which are in COMDAT
811  // groups so it is unsafe to do so *unless* the linkage is local.
812  if (!F->hasLocalLinkage()) {
813  if (F->hasComdat()) {
814  DeadFunctionsInComdats.push_back(F);
815  continue;
816  }
817  }
818 
819  RemoveCGN(CGN);
820  }
821  if (!DeadFunctionsInComdats.empty()) {
822  // Filter out the functions whose comdats remain alive.
823  filterDeadComdatFunctions(CG.getModule(), DeadFunctionsInComdats);
824  // Remove the rest.
825  for (Function *F : DeadFunctionsInComdats)
826  RemoveCGN(CG[F]);
827  }
828 
829  if (FunctionsToRemove.empty())
830  return false;
831 
832  // Now that we know which functions to delete, do so. We didn't want to do
833  // this inline, because that would invalidate our CallGraph::iterator
834  // objects. :(
835  //
836  // Note that it doesn't matter that we are iterating over a non-stable order
837  // here to do this, it doesn't matter which order the functions are deleted
838  // in.
839  array_pod_sort(FunctionsToRemove.begin(), FunctionsToRemove.end());
840  FunctionsToRemove.erase(
841  std::unique(FunctionsToRemove.begin(), FunctionsToRemove.end()),
842  FunctionsToRemove.end());
843  for (CallGraphNode *CGN : FunctionsToRemove) {
844  delete CG.removeFunctionFromModule(CGN);
845  ++NumDeleted;
846  }
847  return true;
848 }
849 
852  assert(InlinerFunctionImportStats != InlinerFunctionImportStatsOpts::No);
853  ImportedFunctionsStats->dump(InlinerFunctionImportStats ==
854  InlinerFunctionImportStatsOpts::Verbose);
855  }
856 }
857 
860  CGSCCUpdateResult &UR) {
861  const ModuleAnalysisManager &MAM =
862  AM.getResult<ModuleAnalysisManagerCGSCCProxy>(InitialC, CG).getManager();
863  bool Changed = false;
864 
865  assert(InitialC.size() > 0 && "Cannot handle an empty SCC!");
866  Module &M = *InitialC.begin()->getFunction().getParent();
868 
869  if (!ImportedFunctionsStats &&
870  InlinerFunctionImportStats != InlinerFunctionImportStatsOpts::No) {
872  llvm::make_unique<ImportedFunctionsInliningStatistics>();
874  }
875 
876  // We use a single common worklist for calls across the entire SCC. We
877  // process these in-order and append new calls introduced during inlining to
878  // the end.
879  //
880  // Note that this particular order of processing is actually critical to
881  // avoid very bad behaviors. Consider *highly connected* call graphs where
882  // each function contains a small amonut of code and a couple of calls to
883  // other functions. Because the LLVM inliner is fundamentally a bottom-up
884  // inliner, it can handle gracefully the fact that these all appear to be
885  // reasonable inlining candidates as it will flatten things until they become
886  // too big to inline, and then move on and flatten another batch.
887  //
888  // However, when processing call edges *within* an SCC we cannot rely on this
889  // bottom-up behavior. As a consequence, with heavily connected *SCCs* of
890  // functions we can end up incrementally inlining N calls into each of
891  // N functions because each incremental inlining decision looks good and we
892  // don't have a topological ordering to prevent explosions.
893  //
894  // To compensate for this, we don't process transitive edges made immediate
895  // by inlining until we've done one pass of inlining across the entire SCC.
896  // Large, highly connected SCCs still lead to some amount of code bloat in
897  // this model, but it is uniformly spread across all the functions in the SCC
898  // and eventually they all become too large to inline, rather than
899  // incrementally maknig a single function grow in a super linear fashion.
901 
904  .getManager();
905 
906  // Populate the initial list of calls in this SCC.
907  for (auto &N : InitialC) {
908  auto &ORE =
909  FAM.getResult<OptimizationRemarkEmitterAnalysis>(N.getFunction());
910  // We want to generally process call sites top-down in order for
911  // simplifications stemming from replacing the call with the returned value
912  // after inlining to be visible to subsequent inlining decisions.
913  // FIXME: Using instructions sequence is a really bad way to do this.
914  // Instead we should do an actual RPO walk of the function body.
915  for (Instruction &I : instructions(N.getFunction()))
916  if (auto CS = CallSite(&I))
917  if (Function *Callee = CS.getCalledFunction()) {
918  if (!Callee->isDeclaration())
919  Calls.push_back({CS, -1});
920  else if (!isa<IntrinsicInst>(I)) {
921  using namespace ore;
922  setInlineRemark(CS, "unavailable definition");
923  ORE.emit([&]() {
924  return OptimizationRemarkMissed(DEBUG_TYPE, "NoDefinition", &I)
925  << NV("Callee", Callee) << " will not be inlined into "
926  << NV("Caller", CS.getCaller())
927  << " because its definition is unavailable"
928  << setIsVerbose();
929  });
930  }
931  }
932  }
933  if (Calls.empty())
934  return PreservedAnalyses::all();
935 
936  // Capture updatable variables for the current SCC and RefSCC.
937  auto *C = &InitialC;
938  auto *RC = &C->getOuterRefSCC();
939 
940  // When inlining a callee produces new call sites, we want to keep track of
941  // the fact that they were inlined from the callee. This allows us to avoid
942  // infinite inlining in some obscure cases. To represent this, we use an
943  // index into the InlineHistory vector.
944  SmallVector<std::pair<Function *, int>, 16> InlineHistory;
945 
946  // Track a set vector of inlined callees so that we can augment the caller
947  // with all of their edges in the call graph before pruning out the ones that
948  // got simplified away.
949  SmallSetVector<Function *, 4> InlinedCallees;
950 
951  // Track the dead functions to delete once finished with inlining calls. We
952  // defer deleting these to make it easier to handle the call graph updates.
953  SmallVector<Function *, 4> DeadFunctions;
954 
955  // Loop forward over all of the calls. Note that we cannot cache the size as
956  // inlining can introduce new calls that need to be processed.
957  for (int i = 0; i < (int)Calls.size(); ++i) {
958  // We expect the calls to typically be batched with sequences of calls that
959  // have the same caller, so we first set up some shared infrastructure for
960  // this caller. We also do any pruning we can at this layer on the caller
961  // alone.
962  Function &F = *Calls[i].first.getCaller();
963  LazyCallGraph::Node &N = *CG.lookup(F);
964  if (CG.lookupSCC(N) != C)
965  continue;
966  if (F.hasFnAttribute(Attribute::OptimizeNone)) {
967  setInlineRemark(Calls[i].first, "optnone attribute");
968  continue;
969  }
970 
971  LLVM_DEBUG(dbgs() << "Inlining calls in: " << F.getName() << "\n");
972 
973  // Get a FunctionAnalysisManager via a proxy for this particular node. We
974  // do this each time we visit a node as the SCC may have changed and as
975  // we're going to mutate this particular function we want to make sure the
976  // proxy is in place to forward any invalidation events. We can use the
977  // manager we get here for looking up results for functions other than this
978  // node however because those functions aren't going to be mutated by this
979  // pass.
982  .getManager();
983 
984  // Get the remarks emission analysis for the caller.
985  auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(F);
986 
987  std::function<AssumptionCache &(Function &)> GetAssumptionCache =
988  [&](Function &F) -> AssumptionCache & {
989  return FAM.getResult<AssumptionAnalysis>(F);
990  };
991  auto GetBFI = [&](Function &F) -> BlockFrequencyInfo & {
992  return FAM.getResult<BlockFrequencyAnalysis>(F);
993  };
994 
995  auto GetInlineCost = [&](CallSite CS) {
997  auto &CalleeTTI = FAM.getResult<TargetIRAnalysis>(Callee);
998  return getInlineCost(CS, Params, CalleeTTI, GetAssumptionCache, {GetBFI},
999  PSI, &ORE);
1000  };
1001 
1002  // Now process as many calls as we have within this caller in the sequnece.
1003  // We bail out as soon as the caller has to change so we can update the
1004  // call graph and prepare the context of that new caller.
1005  bool DidInline = false;
1006  for (; i < (int)Calls.size() && Calls[i].first.getCaller() == &F; ++i) {
1007  int InlineHistoryID;
1008  CallSite CS;
1009  std::tie(CS, InlineHistoryID) = Calls[i];
1011 
1012  if (InlineHistoryID != -1 &&
1013  InlineHistoryIncludes(&Callee, InlineHistoryID, InlineHistory)) {
1014  setInlineRemark(CS, "recursive");
1015  continue;
1016  }
1017 
1018  // Check if this inlining may repeat breaking an SCC apart that has
1019  // already been split once before. In that case, inlining here may
1020  // trigger infinite inlining, much like is prevented within the inliner
1021  // itself by the InlineHistory above, but spread across CGSCC iterations
1022  // and thus hidden from the full inline history.
1023  if (CG.lookupSCC(*CG.lookup(Callee)) == C &&
1024  UR.InlinedInternalEdges.count({&N, C})) {
1025  LLVM_DEBUG(dbgs() << "Skipping inlining internal SCC edge from a node "
1026  "previously split out of this SCC by inlining: "
1027  << F.getName() << " -> " << Callee.getName() << "\n");
1028  setInlineRemark(CS, "recursive SCC split");
1029  continue;
1030  }
1031 
1032  Optional<InlineCost> OIC = shouldInline(CS, GetInlineCost, ORE);
1033  // Check whether we want to inline this callsite.
1034  if (!OIC.hasValue()) {
1035  setInlineRemark(CS, "deferred");
1036  continue;
1037  }
1038 
1039  if (!OIC.getValue()) {
1040  // shouldInline() call returned a negative inline cost that explains
1041  // why this callsite should not be inlined.
1042  setInlineRemark(CS, inlineCostStr(*OIC));
1043  continue;
1044  }
1045 
1046  // Setup the data structure used to plumb customization into the
1047  // `InlineFunction` routine.
1048  InlineFunctionInfo IFI(
1049  /*cg=*/nullptr, &GetAssumptionCache, PSI,
1050  &FAM.getResult<BlockFrequencyAnalysis>(*(CS.getCaller())),
1051  &FAM.getResult<BlockFrequencyAnalysis>(Callee));
1052 
1053  // Get DebugLoc to report. CS will be invalid after Inliner.
1054  DebugLoc DLoc = CS->getDebugLoc();
1055  BasicBlock *Block = CS.getParent();
1056 
1057  using namespace ore;
1058 
1059  InlineResult IR = InlineFunction(CS, IFI);
1060  if (!IR) {
1061  setInlineRemark(CS, std::string(IR) + "; " + inlineCostStr(*OIC));
1062  ORE.emit([&]() {
1063  return OptimizationRemarkMissed(DEBUG_TYPE, "NotInlined", DLoc, Block)
1064  << NV("Callee", &Callee) << " will not be inlined into "
1065  << NV("Caller", &F) << ": " << NV("Reason", IR.message);
1066  });
1067  continue;
1068  }
1069  DidInline = true;
1070  InlinedCallees.insert(&Callee);
1071 
1072  ++NumInlined;
1073 
1074  emit_inlined_into(ORE, DLoc, Block, Callee, F, *OIC);
1075 
1076  // Add any new callsites to defined functions to the worklist.
1077  if (!IFI.InlinedCallSites.empty()) {
1078  int NewHistoryID = InlineHistory.size();
1079  InlineHistory.push_back({&Callee, InlineHistoryID});
1080  for (CallSite &CS : reverse(IFI.InlinedCallSites))
1081  if (Function *NewCallee = CS.getCalledFunction())
1082  if (!NewCallee->isDeclaration())
1083  Calls.push_back({CS, NewHistoryID});
1084  }
1085 
1086  if (InlinerFunctionImportStats != InlinerFunctionImportStatsOpts::No)
1088 
1089  // Merge the attributes based on the inlining.
1091 
1092  // For local functions, check whether this makes the callee trivially
1093  // dead. In that case, we can drop the body of the function eagerly
1094  // which may reduce the number of callers of other functions to one,
1095  // changing inline cost thresholds.
1096  if (Callee.hasLocalLinkage()) {
1097  // To check this we also need to nuke any dead constant uses (perhaps
1098  // made dead by this operation on other functions).
1099  Callee.removeDeadConstantUsers();
1100  if (Callee.use_empty() && !CG.isLibFunction(Callee)) {
1101  Calls.erase(
1102  std::remove_if(Calls.begin() + i + 1, Calls.end(),
1103  [&Callee](const std::pair<CallSite, int> &Call) {
1104  return Call.first.getCaller() == &Callee;
1105  }),
1106  Calls.end());
1107  // Clear the body and queue the function itself for deletion when we
1108  // finish inlining and call graph updates.
1109  // Note that after this point, it is an error to do anything other
1110  // than use the callee's address or delete it.
1111  Callee.dropAllReferences();
1112  assert(find(DeadFunctions, &Callee) == DeadFunctions.end() &&
1113  "Cannot put cause a function to become dead twice!");
1114  DeadFunctions.push_back(&Callee);
1115  }
1116  }
1117  }
1118 
1119  // Back the call index up by one to put us in a good position to go around
1120  // the outer loop.
1121  --i;
1122 
1123  if (!DidInline)
1124  continue;
1125  Changed = true;
1126 
1127  // Add all the inlined callees' edges as ref edges to the caller. These are
1128  // by definition trivial edges as we always have *some* transitive ref edge
1129  // chain. While in some cases these edges are direct calls inside the
1130  // callee, they have to be modeled in the inliner as reference edges as
1131  // there may be a reference edge anywhere along the chain from the current
1132  // caller to the callee that causes the whole thing to appear like
1133  // a (transitive) reference edge that will require promotion to a call edge
1134  // below.
1135  for (Function *InlinedCallee : InlinedCallees) {
1136  LazyCallGraph::Node &CalleeN = *CG.lookup(*InlinedCallee);
1137  for (LazyCallGraph::Edge &E : *CalleeN)
1138  RC->insertTrivialRefEdge(N, E.getNode());
1139  }
1140 
1141  // At this point, since we have made changes we have at least removed
1142  // a call instruction. However, in the process we do some incremental
1143  // simplification of the surrounding code. This simplification can
1144  // essentially do all of the same things as a function pass and we can
1145  // re-use the exact same logic for updating the call graph to reflect the
1146  // change.
1147  LazyCallGraph::SCC *OldC = C;
1148  C = &updateCGAndAnalysisManagerForFunctionPass(CG, *C, N, AM, UR);
1149  LLVM_DEBUG(dbgs() << "Updated inlining SCC: " << *C << "\n");
1150  RC = &C->getOuterRefSCC();
1151 
1152  // If this causes an SCC to split apart into multiple smaller SCCs, there
1153  // is a subtle risk we need to prepare for. Other transformations may
1154  // expose an "infinite inlining" opportunity later, and because of the SCC
1155  // mutation, we will revisit this function and potentially re-inline. If we
1156  // do, and that re-inlining also has the potentially to mutate the SCC
1157  // structure, the infinite inlining problem can manifest through infinite
1158  // SCC splits and merges. To avoid this, we capture the originating caller
1159  // node and the SCC containing the call edge. This is a slight over
1160  // approximation of the possible inlining decisions that must be avoided,
1161  // but is relatively efficient to store.
1162  // FIXME: This seems like a very heavyweight way of retaining the inline
1163  // history, we should look for a more efficient way of tracking it.
1164  if (C != OldC && llvm::any_of(InlinedCallees, [&](Function *Callee) {
1165  return CG.lookupSCC(*CG.lookup(*Callee)) == OldC;
1166  })) {
1167  LLVM_DEBUG(dbgs() << "Inlined an internal call edge and split an SCC, "
1168  "retaining this to avoid infinite inlining.\n");
1169  UR.InlinedInternalEdges.insert({&N, OldC});
1170  }
1171  InlinedCallees.clear();
1172  }
1173 
1174  // Now that we've finished inlining all of the calls across this SCC, delete
1175  // all of the trivially dead functions, updating the call graph and the CGSCC
1176  // pass manager in the process.
1177  //
1178  // Note that this walks a pointer set which has non-deterministic order but
1179  // that is OK as all we do is delete things and add pointers to unordered
1180  // sets.
1181  for (Function *DeadF : DeadFunctions) {
1182  // Get the necessary information out of the call graph and nuke the
1183  // function there. Also, cclear out any cached analyses.
1184  auto &DeadC = *CG.lookupSCC(*CG.lookup(*DeadF));
1187  .getManager();
1188  FAM.clear(*DeadF, DeadF->getName());
1189  AM.clear(DeadC, DeadC.getName());
1190  auto &DeadRC = DeadC.getOuterRefSCC();
1191  CG.removeDeadFunction(*DeadF);
1192 
1193  // Mark the relevant parts of the call graph as invalid so we don't visit
1194  // them.
1195  UR.InvalidatedSCCs.insert(&DeadC);
1196  UR.InvalidatedRefSCCs.insert(&DeadRC);
1197 
1198  // And delete the actual function from the module.
1199  M.getFunctionList().erase(DeadF);
1200  ++NumDeleted;
1201  }
1202 
1203  if (!Changed)
1204  return PreservedAnalyses::all();
1205 
1206  // Even if we change the IR, we update the core CGSCC data structures and so
1207  // can preserve the proxy to the function analysis manager.
1208  PreservedAnalyses PA;
1210  return PA;
1211 }
InlinerFunctionImportStatsOpts
Definition: Inliner.cpp:99
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:68
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
bool doFinalization(CallGraph &CG) override
Remove now-dead linkonce functions at the end of processing to avoid breaking the SCC traversal...
Definition: Inliner.cpp:761
void setModuleInfo(const Module &M)
Set information like AllFunctions, ImportedFunctions, ModuleName.
bool hasLocalLinkage() const
Definition: GlobalValue.h:436
Diagnostic information for missed-optimization remarks.
DiagnosticInfoOptimizationBase::Argument NV
bool isNever() const
Definition: InlineCost.h:106
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:770
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:472
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:64
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.
void recordInline(const Function &Caller, const Function &Callee)
Record inline of.
void clear(IRUnitT &IR, llvm::StringRef Name)
Clear any cached analysis results for a single unit of IR.
Definition: PassManager.h:740
static InlineResult 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:275
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.
Implements a lazy call graph analysis and related passes for the new pass manager.
This file contains the declarations for metadata subclasses.
An immutable pass that tracks lazily created AssumptionCache objects.
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:107
A cache of @llvm.assume calls within a function.
Analysis pass providing the TargetTransformInfo.
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:714
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
Definition: Function.h:321
STATISTIC(NumFunctions, "Total number of functions")
A debug info location.
Definition: DebugLoc.h:34
F(f)
InlineResult 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...
Calculate and dump ThinLTO specific inliner stats.
static std::string inlineCostStr(const InlineCost &IC)
Definition: Inliner.cpp:399
InlineFunctionInfo - This class captures the data input to the InlineFunction call, and records the auxiliary results produced by it.
Definition: Cloning.h:177
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:162
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
AnalysisUsage & addRequired()
bool runOnSCC(CallGraphSCC &SCC) override
Main run interface method, this implements the interface required by the Pass class.
Definition: Inliner.cpp:491
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:364
unsigned getAlignment() const
Return the alignment of the memory that is being allocated by the instruction.
Definition: Instructions.h:113
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...
This file contains the simple types necessary to represent the attributes associated with functions a...
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:858
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:409
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:251
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
const T & getValue() const LLVM_LVALUE_FUNCTION
Definition: Optional.h:179
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:439
InlineResult is basically true or false.
Definition: InlineCost.h:137
#define DEBUG_TYPE
Definition: Inliner.cpp:74
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:536
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
bool hasLinkOnceODRLinkage() const
Definition: GlobalValue.h:427
SmallVector< CallSite, 8 > InlinedCallSites
All of the new call sites inlined into the caller.
Definition: Cloning.h:208
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:410
bool isAlways() const
Definition: InlineCost.h:105
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:939
void getAnalysisUsage(AnalysisUsage &Info) const override
For this class, we declare that we require and preserve the call graph.
Definition: Inliner.cpp:132
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:154
static MetadataAsValue * getIfExists(LLVMContext &Context, Metadata *MD)
Definition: Metadata.cpp:114
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
bool inlineCalls(CallGraphSCC &SCC)
This function performs the main work of the pass.
Definition: Inliner.cpp:746
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:630
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:129
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:371
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:1049
A node in the call graph.
static void emit_inlined_into(OptimizationRemarkEmitter &ORE, DebugLoc &DLoc, const BasicBlock *Block, const Function &Callee, const Function &Caller, const InlineCost &IC)
Definition: Inliner.cpp:497
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
A class used to represent edges in the call graph.
auto remove_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::remove_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1082
Used in the streaming interface as the general argument type.
iterator erase(const_iterator CI)
Definition: SmallVector.h:445
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:160
bool doInitialization(CallGraph &CG) override
doInitialization - This method is called before the SCC&#39;s of the program has been processed...
Definition: Inliner.cpp:485
size_t size() const
Definition: SmallVector.h:53
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1063
int getThreshold() const
Get the threshold against which the cost was computed.
Definition: InlineCost.h:117
const char * getReason() const
Get the reason of Always or Never.
Definition: InlineCost.h:123
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:106
unsigned first
Function * getFunction() const
Returns the function that this call graph node represents.
Definition: CallGraph.h:188
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:518
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:418
void removeDeadFunction(Function &F)
Remove a dead function from the call graph (typically to delete it).
ImportedFunctionsInliningStatistics ImportedFunctionsStats
Definition: Inliner.h:78
void emit(DiagnosticInfoOptimizationBase &OptDiag)
Output the remark via the diagnostic handler and to the optimization record file. ...
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
Definition: PassManager.h:1154
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:847
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:440
unsigned getABITypeAlignment(Type *Ty) const
Returns the minimum ABI-required alignment for the specified type.
Definition: DataLayout.cpp:722
void dropAllReferences()
dropAllReferences() - This method causes all the subinstructions to "let go" of all references that t...
Definition: Function.cpp:347
AssumptionCacheTracker * ACT
Definition: Inliner.h:76
bool removeDeadFunctions(CallGraph &CG, bool AlwaysInlineOnly=false)
Remove dead functions.
Definition: Inliner.cpp:769
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:133
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:941
void dump(bool Verbose)
Dump stats computed with InlinerStatistics class.
iterator_range< user_iterator > users()
Definition: Value.h:400
int getCost() const
Get the inline cost estimate.
Definition: InlineCost.h:111
int getCostDelta() const
Get the cost delta from the threshold for inlining.
Definition: InlineCost.h:132
bool hasComdat() const
Definition: GlobalObject.h:100
void addAttribute(unsigned i, Attribute::AttrKind Kind)
Definition: CallSite.h:337
static void setInlineRemark(CallSite &CS, StringRef message)
Definition: Inliner.cpp:509
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
Definition: CommandLine.h:605
amdgpu Simplify well known AMD library false Value Value * Arg
void filterDeadComdatFunctions(Module &M, SmallVectorImpl< Function *> &DeadComdatFunctions)
Filter out potentially dead comdat functions where other entries keep the entire comdat group alive...
SmallVector< AllocaInst *, 4 > StaticAllocas
StaticAllocas - InlineFunction fills this in with all static allocas that get copied into the caller...
Definition: Cloning.h:197
bool hasValue() const
Definition: Optional.h:183
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:133
FunTy * getCaller() const
Return the caller function for this call site.
Definition: CallSite.h:267
LegacyInlinerBase(char &ID)
Definition: Inliner.cpp:124
const char * message
Definition: InlineCost.h:138
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:56
SmallVector< WeakTrackingVH, 8 > InlinedCalls
InlinedCalls - InlineFunction fills this in with callsites that were inlined from the callee...
Definition: Cloning.h:201
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:224
#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:789
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:175
static Attribute get(LLVMContext &Context, AttrKind Kind, uint64_t Val=0)
Return a uniquified Attribute object.
Definition: Attributes.cpp:81
ProfileSummaryInfo * PSI
Definition: Inliner.h:77
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2033
CallGraphNode * getExternalCallingNode() const
Returns the CallGraphNode which is used to represent undetermined calls into the callgraph.
Definition: CallGraph.h:137
This header provides classes for managing passes over SCCs of the call graph.
bool isDeclaration() const
Return true if the primary definition of this global value is outside of the current translation unit...
Definition: Globals.cpp:206
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:566
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:348
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.
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:413
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
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.
This pass exposes codegen information to IR-level passes.
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:308
static cl::opt< InlinerFunctionImportStatsOpts > InlinerFunctionImportStats("inliner-function-import-stats", cl::init(InlinerFunctionImportStatsOpts::No), cl::values(clEnumValN(InlinerFunctionImportStatsOpts::Basic, "basic", "basic statistics"), clEnumValN(InlinerFunctionImportStatsOpts::Verbose, "verbose", "printing of statistics for each inlined function")), cl::Hidden, cl::desc("Enable inliner stats for imported functions"))
This header defines various interfaces for pass management in LLVM.
#define LLVM_DEBUG(X)
Definition: Debug.h:123
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:323
Statically lint checks LLVM IR
Definition: Lint.cpp:193
bool isDefTriviallyDead() const
isDefTriviallyDead - Return true if it is trivially safe to remove this function definition from the ...
Definition: Function.cpp:1275
const BasicBlock * getParent() const
Definition: Instruction.h:67
an instruction to allocate memory on the stack
Definition: Instructions.h:60
static cl::opt< bool > InlineRemarkAttribute("inline-remark-attribute", cl::init(false), cl::Hidden, cl::desc("Enable adding inline-remark attribute to" " callsites processed by inliner but decided" " to be not inlined"))
Flag to add inline messages as callsite attributes &#39;inline-remark&#39;.