1 //===- InlineAdvisor.cpp - analysis pass implementation -------------------===//
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 inlining decision-making APIs.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "llvm/Analysis/InlineAdvisor.h"
15 #include "llvm/ADT/Statistic.h"
16 #include "llvm/Analysis/InlineCost.h"
17 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
18 #include "llvm/Analysis/ProfileSummaryInfo.h"
19 #include "llvm/Analysis/TargetLibraryInfo.h"
20 #include "llvm/Analysis/TargetTransformInfo.h"
21 #include "llvm/IR/Instructions.h"
22 #include "llvm/Support/raw_ostream.h"
23 
24 #include <sstream>
25 
26 using namespace llvm;
27 #define DEBUG_TYPE "inline"
28 
29 // This weirdly named statistic tracks the number of times that, when attempting
30 // to inline a function A into B, we analyze the callers of B in order to see
31 // if those would be more profitable and blocked inline steps.
32 STATISTIC(NumCallerCallersAnalyzed, "Number of caller-callers analyzed");
33 
34 /// Flag to add inline messages as callsite attributes 'inline-remark'.
35 static cl::opt<bool>
36     InlineRemarkAttribute("inline-remark-attribute", cl::init(false),
37                           cl::Hidden,
38                           cl::desc("Enable adding inline-remark attribute to"
39                                    " callsites processed by inliner but decided"
40                                    " to be not inlined"));
41 
42 // An integer used to limit the cost of inline deferral.  The default negative
43 // number tells shouldBeDeferred to only take the secondary cost into account.
44 static cl::opt<int>
45     InlineDeferralScale("inline-deferral-scale",
46                         cl::desc("Scale to limit the cost of inline deferral"),
47                         cl::init(-1), cl::Hidden);
48 
49 /// Return true if inlining of CB can block the caller from being
50 /// inlined which is proved to be more beneficial. \p IC is the
51 /// estimated inline cost associated with callsite \p CB.
52 /// \p TotalSecondaryCost will be set to the estimated cost of inlining the
53 /// caller if \p CB is suppressed for inlining.
54 static bool
55 shouldBeDeferred(Function *Caller, InlineCost IC, int &TotalSecondaryCost,
56                  function_ref<InlineCost(CallBase &CB)> GetInlineCost) {
57   // For now we only handle local or inline functions.
58   if (!Caller->hasLocalLinkage() && !Caller->hasLinkOnceODRLinkage())
59     return false;
60   // If the cost of inlining CB is non-positive, it is not going to prevent the
61   // caller from being inlined into its callers and hence we don't need to
62   // defer.
63   if (IC.getCost() <= 0)
64     return false;
65   // Try to detect the case where the current inlining candidate caller (call
66   // it B) is a static or linkonce-ODR function and is an inlining candidate
67   // elsewhere, and the current candidate callee (call it C) is large enough
68   // that inlining it into B would make B too big to inline later. In these
69   // circumstances it may be best not to inline C into B, but to inline B into
70   // its callers.
71   //
72   // This only applies to static and linkonce-ODR functions because those are
73   // expected to be available for inlining in the translation units where they
74   // are used. Thus we will always have the opportunity to make local inlining
75   // decisions. Importantly the linkonce-ODR linkage covers inline functions
76   // and templates in C++.
77   //
78   // FIXME: All of this logic should be sunk into getInlineCost. It relies on
79   // the internal implementation of the inline cost metrics rather than
80   // treating them as truly abstract units etc.
81   TotalSecondaryCost = 0;
82   // The candidate cost to be imposed upon the current function.
83   int CandidateCost = IC.getCost() - 1;
84   // If the caller has local linkage and can be inlined to all its callers, we
85   // can apply a huge negative bonus to TotalSecondaryCost.
86   bool ApplyLastCallBonus = Caller->hasLocalLinkage() && !Caller->hasOneUse();
87   // This bool tracks what happens if we DO inline C into B.
88   bool InliningPreventsSomeOuterInline = false;
89   unsigned NumCallerUsers = 0;
90   for (User *U : Caller->users()) {
91     CallBase *CS2 = dyn_cast<CallBase>(U);
92 
93     // If this isn't a call to Caller (it could be some other sort
94     // of reference) skip it.  Such references will prevent the caller
95     // from being removed.
96     if (!CS2 || CS2->getCalledFunction() != Caller) {
97       ApplyLastCallBonus = false;
98       continue;
99     }
100 
101     InlineCost IC2 = GetInlineCost(*CS2);
102     ++NumCallerCallersAnalyzed;
103     if (!IC2) {
104       ApplyLastCallBonus = false;
105       continue;
106     }
107     if (IC2.isAlways())
108       continue;
109 
110     // See if inlining of the original callsite would erase the cost delta of
111     // this callsite. We subtract off the penalty for the call instruction,
112     // which we would be deleting.
113     if (IC2.getCostDelta() <= CandidateCost) {
114       InliningPreventsSomeOuterInline = true;
115       TotalSecondaryCost += IC2.getCost();
116       NumCallerUsers++;
117     }
118   }
119 
120   if (!InliningPreventsSomeOuterInline)
121     return false;
122 
123   // If all outer calls to Caller would get inlined, the cost for the last
124   // one is set very low by getInlineCost, in anticipation that Caller will
125   // be removed entirely.  We did not account for this above unless there
126   // is only one caller of Caller.
127   if (ApplyLastCallBonus)
128     TotalSecondaryCost -= InlineConstants::LastCallToStaticBonus;
129 
130   // If InlineDeferralScale is negative, then ignore the cost of primary
131   // inlining -- IC.getCost() multiplied by the number of callers to Caller.
132   if (InlineDeferralScale < 0)
133     return TotalSecondaryCost < IC.getCost();
134 
135   int TotalCost = TotalSecondaryCost + IC.getCost() * NumCallerUsers;
136   int Allowance = IC.getCost() * InlineDeferralScale;
137   return TotalCost < Allowance;
138 }
139 
140 namespace llvm {
141 static std::basic_ostream<char> &operator<<(std::basic_ostream<char> &R,
142                                             const ore::NV &Arg) {
143   return R << Arg.Val;
144 }
145 
146 template <class RemarkT>
147 RemarkT &operator<<(RemarkT &&R, const InlineCost &IC) {
148   using namespace ore;
149   if (IC.isAlways()) {
150     R << "(cost=always)";
151   } else if (IC.isNever()) {
152     R << "(cost=never)";
153   } else {
154     R << "(cost=" << ore::NV("Cost", IC.getCost())
155       << ", threshold=" << ore::NV("Threshold", IC.getThreshold()) << ")";
156   }
157   if (const char *Reason = IC.getReason())
158     R << ": " << ore::NV("Reason", Reason);
159   return R;
160 }
161 } // namespace llvm
162 
163 std::string llvm::inlineCostStr(const InlineCost &IC) {
164   std::stringstream Remark;
165   Remark << IC;
166   return Remark.str();
167 }
168 
169 void llvm::setInlineRemark(CallBase &CB, StringRef Message) {
170   if (!InlineRemarkAttribute)
171     return;
172 
173   Attribute Attr = Attribute::get(CB.getContext(), "inline-remark", Message);
174   CB.addAttribute(AttributeList::FunctionIndex, Attr);
175 }
176 
177 /// Return the cost only if the inliner should attempt to inline at the given
178 /// CallSite. If we return the cost, we will emit an optimisation remark later
179 /// using that cost, so we won't do so from this function. Return None if
180 /// inlining should not be attempted.
181 Optional<InlineCost>
182 llvm::shouldInline(CallBase &CB,
183                    function_ref<InlineCost(CallBase &CB)> GetInlineCost,
184                    OptimizationRemarkEmitter &ORE) {
185   using namespace ore;
186 
187   InlineCost IC = GetInlineCost(CB);
188   Instruction *Call = &CB;
189   Function *Callee = CB.getCalledFunction();
190   Function *Caller = CB.getCaller();
191 
192   if (IC.isAlways()) {
193     LLVM_DEBUG(dbgs() << "    Inlining " << inlineCostStr(IC)
194                       << ", Call: " << CB << "\n");
195     return IC;
196   }
197 
198   if (!IC) {
199     LLVM_DEBUG(dbgs() << "    NOT Inlining " << inlineCostStr(IC)
200                       << ", Call: " << CB << "\n");
201     if (IC.isNever()) {
202       ORE.emit([&]() {
203         return OptimizationRemarkMissed(DEBUG_TYPE, "NeverInline", Call)
204                << NV("Callee", Callee) << " not inlined into "
205                << NV("Caller", Caller) << " because it should never be inlined "
206                << IC;
207       });
208     } else {
209       ORE.emit([&]() {
210         return OptimizationRemarkMissed(DEBUG_TYPE, "TooCostly", Call)
211                << NV("Callee", Callee) << " not inlined into "
212                << NV("Caller", Caller) << " because too costly to inline "
213                << IC;
214       });
215     }
216     setInlineRemark(CB, inlineCostStr(IC));
217     return None;
218   }
219 
220   int TotalSecondaryCost = 0;
221   if (shouldBeDeferred(Caller, IC, TotalSecondaryCost, GetInlineCost)) {
222     LLVM_DEBUG(dbgs() << "    NOT Inlining: " << CB
223                       << " Cost = " << IC.getCost()
224                       << ", outer Cost = " << TotalSecondaryCost << '\n');
225     ORE.emit([&]() {
226       return OptimizationRemarkMissed(DEBUG_TYPE, "IncreaseCostInOtherContexts",
227                                       Call)
228              << "Not inlining. Cost of inlining " << NV("Callee", Callee)
229              << " increases the cost of inlining " << NV("Caller", Caller)
230              << " in other contexts";
231     });
232     setInlineRemark(CB, "deferred");
233     // IC does not bool() to false, so get an InlineCost that will.
234     // This will not be inspected to make an error message.
235     return None;
236   }
237 
238   LLVM_DEBUG(dbgs() << "    Inlining " << inlineCostStr(IC) << ", Call: " << CB
239                     << '\n');
240   return IC;
241 }
242 
243 void llvm::emitInlinedInto(OptimizationRemarkEmitter &ORE, DebugLoc DLoc,
244                            const BasicBlock *Block, const Function &Callee,
245                            const Function &Caller, const InlineCost &IC) {
246   ORE.emit([&]() {
247     bool AlwaysInline = IC.isAlways();
248     StringRef RemarkName = AlwaysInline ? "AlwaysInline" : "Inlined";
249     return OptimizationRemark(DEBUG_TYPE, RemarkName, DLoc, Block)
250            << ore::NV("Callee", &Callee) << " inlined into "
251            << ore::NV("Caller", &Caller) << " with " << IC;
252   });
253 }
254