|
173
|
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 InlineAdvisorAnalysis and DefaultInlineAdvisor, and
|
|
|
11 // related types.
|
|
|
12 //
|
|
|
13 //===----------------------------------------------------------------------===//
|
|
|
14
|
|
|
15 #include "llvm/Analysis/InlineAdvisor.h"
|
|
|
16 #include "llvm/ADT/Statistic.h"
|
|
|
17 #include "llvm/Analysis/InlineCost.h"
|
|
|
18 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
|
|
|
19 #include "llvm/Analysis/ProfileSummaryInfo.h"
|
|
|
20 #include "llvm/Analysis/TargetLibraryInfo.h"
|
|
|
21 #include "llvm/Analysis/TargetTransformInfo.h"
|
|
|
22 #include "llvm/IR/Instructions.h"
|
|
|
23 #include "llvm/Support/raw_ostream.h"
|
|
|
24
|
|
|
25 #include <sstream>
|
|
|
26
|
|
|
27 using namespace llvm;
|
|
|
28 #define DEBUG_TYPE "inline"
|
|
|
29
|
|
|
30 // This weirdly named statistic tracks the number of times that, when attempting
|
|
|
31 // to inline a function A into B, we analyze the callers of B in order to see
|
|
|
32 // if those would be more profitable and blocked inline steps.
|
|
|
33 STATISTIC(NumCallerCallersAnalyzed, "Number of caller-callers analyzed");
|
|
|
34
|
|
|
35 /// Flag to add inline messages as callsite attributes 'inline-remark'.
|
|
|
36 static cl::opt<bool>
|
|
|
37 InlineRemarkAttribute("inline-remark-attribute", cl::init(false),
|
|
|
38 cl::Hidden,
|
|
|
39 cl::desc("Enable adding inline-remark attribute to"
|
|
|
40 " callsites processed by inliner but decided"
|
|
|
41 " to be not inlined"));
|
|
|
42
|
|
|
43 // An integer used to limit the cost of inline deferral. The default negative
|
|
|
44 // number tells shouldBeDeferred to only take the secondary cost into account.
|
|
|
45 static cl::opt<int>
|
|
|
46 InlineDeferralScale("inline-deferral-scale",
|
|
|
47 cl::desc("Scale to limit the cost of inline deferral"),
|
|
|
48 cl::init(-1), cl::Hidden);
|
|
|
49
|
|
|
50 namespace {
|
|
|
51 class DefaultInlineAdvice : public InlineAdvice {
|
|
|
52 public:
|
|
|
53 DefaultInlineAdvice(DefaultInlineAdvisor *Advisor, CallBase &CB,
|
|
|
54 Optional<InlineCost> OIC, OptimizationRemarkEmitter &ORE)
|
|
|
55 : InlineAdvice(Advisor, CB, OIC.hasValue()), OriginalCB(&CB), OIC(OIC),
|
|
|
56 ORE(ORE), DLoc(CB.getDebugLoc()), Block(CB.getParent()) {}
|
|
|
57
|
|
|
58 private:
|
|
|
59 void recordUnsuccessfulInliningImpl(const InlineResult &Result) override {
|
|
|
60 using namespace ore;
|
|
|
61 llvm::setInlineRemark(*OriginalCB, std::string(Result.getFailureReason()) +
|
|
|
62 "; " + inlineCostStr(*OIC));
|
|
|
63 ORE.emit([&]() {
|
|
|
64 return OptimizationRemarkMissed(DEBUG_TYPE, "NotInlined", DLoc, Block)
|
|
|
65 << NV("Callee", Callee) << " will not be inlined into "
|
|
|
66 << NV("Caller", Caller) << ": "
|
|
|
67 << NV("Reason", Result.getFailureReason());
|
|
|
68 });
|
|
|
69 }
|
|
|
70
|
|
|
71 void recordInliningWithCalleeDeletedImpl() override {
|
|
|
72 emitInlinedInto(ORE, DLoc, Block, *Callee, *Caller, *OIC);
|
|
|
73 }
|
|
|
74
|
|
|
75 void recordInliningImpl() override {
|
|
|
76 emitInlinedInto(ORE, DLoc, Block, *Callee, *Caller, *OIC);
|
|
|
77 }
|
|
|
78
|
|
|
79 private:
|
|
|
80 CallBase *const OriginalCB;
|
|
|
81 Optional<InlineCost> OIC;
|
|
|
82 OptimizationRemarkEmitter &ORE;
|
|
|
83
|
|
|
84 // Capture the context of CB before inlining, as a successful inlining may
|
|
|
85 // change that context, and we want to report success or failure in the
|
|
|
86 // original context.
|
|
|
87 const DebugLoc DLoc;
|
|
|
88 const BasicBlock *const Block;
|
|
|
89 };
|
|
|
90
|
|
|
91 } // namespace
|
|
|
92
|
|
|
93 std::unique_ptr<InlineAdvice>
|
|
|
94 DefaultInlineAdvisor::getAdvice(CallBase &CB, FunctionAnalysisManager &FAM) {
|
|
|
95 Function &Caller = *CB.getCaller();
|
|
|
96 ProfileSummaryInfo *PSI =
|
|
|
97 FAM.getResult<ModuleAnalysisManagerFunctionProxy>(Caller)
|
|
|
98 .getCachedResult<ProfileSummaryAnalysis>(
|
|
|
99 *CB.getParent()->getParent()->getParent());
|
|
|
100
|
|
|
101 auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(Caller);
|
|
|
102 auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & {
|
|
|
103 return FAM.getResult<AssumptionAnalysis>(F);
|
|
|
104 };
|
|
|
105 auto GetBFI = [&](Function &F) -> BlockFrequencyInfo & {
|
|
|
106 return FAM.getResult<BlockFrequencyAnalysis>(F);
|
|
|
107 };
|
|
|
108 auto GetTLI = [&](Function &F) -> const TargetLibraryInfo & {
|
|
|
109 return FAM.getResult<TargetLibraryAnalysis>(F);
|
|
|
110 };
|
|
|
111
|
|
|
112 auto GetInlineCost = [&](CallBase &CB) {
|
|
|
113 Function &Callee = *CB.getCalledFunction();
|
|
|
114 auto &CalleeTTI = FAM.getResult<TargetIRAnalysis>(Callee);
|
|
|
115 bool RemarksEnabled =
|
|
|
116 Callee.getContext().getDiagHandlerPtr()->isMissedOptRemarkEnabled(
|
|
|
117 DEBUG_TYPE);
|
|
|
118 return getInlineCost(CB, Params, CalleeTTI, GetAssumptionCache, GetTLI,
|
|
|
119 GetBFI, PSI, RemarksEnabled ? &ORE : nullptr);
|
|
|
120 };
|
|
|
121 auto OIC = llvm::shouldInline(CB, GetInlineCost, ORE);
|
|
|
122 return std::make_unique<DefaultInlineAdvice>(this, CB, OIC, ORE);
|
|
|
123 }
|
|
|
124
|
|
|
125 InlineAdvice::InlineAdvice(InlineAdvisor *Advisor, CallBase &CB,
|
|
|
126 bool IsInliningRecommended)
|
|
|
127 : Advisor(Advisor), Caller(CB.getCaller()), Callee(CB.getCalledFunction()),
|
|
|
128 IsInliningRecommended(IsInliningRecommended) {}
|
|
|
129
|
|
|
130 void InlineAdvisor::markFunctionAsDeleted(Function *F) {
|
|
|
131 assert((!DeletedFunctions.count(F)) &&
|
|
|
132 "Cannot put cause a function to become dead twice!");
|
|
|
133 DeletedFunctions.insert(F);
|
|
|
134 }
|
|
|
135
|
|
|
136 void InlineAdvisor::freeDeletedFunctions() {
|
|
|
137 for (auto *F : DeletedFunctions)
|
|
|
138 delete F;
|
|
|
139 DeletedFunctions.clear();
|
|
|
140 }
|
|
|
141
|
|
|
142 void InlineAdvice::recordInliningWithCalleeDeleted() {
|
|
|
143 markRecorded();
|
|
|
144 Advisor->markFunctionAsDeleted(Callee);
|
|
|
145 recordInliningWithCalleeDeletedImpl();
|
|
|
146 }
|
|
|
147
|
|
|
148 AnalysisKey InlineAdvisorAnalysis::Key;
|
|
|
149
|
|
|
150 bool InlineAdvisorAnalysis::Result::tryCreate(InlineParams Params,
|
|
|
151 InliningAdvisorMode Mode) {
|
|
|
152 switch (Mode) {
|
|
|
153 case InliningAdvisorMode::Default:
|
|
|
154 Advisor.reset(new DefaultInlineAdvisor(Params));
|
|
|
155 break;
|
|
|
156 case InliningAdvisorMode::Development:
|
|
|
157 // To be added subsequently under conditional compilation.
|
|
|
158 break;
|
|
|
159 case InliningAdvisorMode::Release:
|
|
|
160 // To be added subsequently under conditional compilation.
|
|
|
161 break;
|
|
|
162 }
|
|
|
163 return !!Advisor;
|
|
|
164 }
|
|
|
165
|
|
|
166 /// Return true if inlining of CB can block the caller from being
|
|
|
167 /// inlined which is proved to be more beneficial. \p IC is the
|
|
|
168 /// estimated inline cost associated with callsite \p CB.
|
|
|
169 /// \p TotalSecondaryCost will be set to the estimated cost of inlining the
|
|
|
170 /// caller if \p CB is suppressed for inlining.
|
|
|
171 static bool
|
|
|
172 shouldBeDeferred(Function *Caller, InlineCost IC, int &TotalSecondaryCost,
|
|
|
173 function_ref<InlineCost(CallBase &CB)> GetInlineCost) {
|
|
|
174 // For now we only handle local or inline functions.
|
|
|
175 if (!Caller->hasLocalLinkage() && !Caller->hasLinkOnceODRLinkage())
|
|
|
176 return false;
|
|
|
177 // If the cost of inlining CB is non-positive, it is not going to prevent the
|
|
|
178 // caller from being inlined into its callers and hence we don't need to
|
|
|
179 // defer.
|
|
|
180 if (IC.getCost() <= 0)
|
|
|
181 return false;
|
|
|
182 // Try to detect the case where the current inlining candidate caller (call
|
|
|
183 // it B) is a static or linkonce-ODR function and is an inlining candidate
|
|
|
184 // elsewhere, and the current candidate callee (call it C) is large enough
|
|
|
185 // that inlining it into B would make B too big to inline later. In these
|
|
|
186 // circumstances it may be best not to inline C into B, but to inline B into
|
|
|
187 // its callers.
|
|
|
188 //
|
|
|
189 // This only applies to static and linkonce-ODR functions because those are
|
|
|
190 // expected to be available for inlining in the translation units where they
|
|
|
191 // are used. Thus we will always have the opportunity to make local inlining
|
|
|
192 // decisions. Importantly the linkonce-ODR linkage covers inline functions
|
|
|
193 // and templates in C++.
|
|
|
194 //
|
|
|
195 // FIXME: All of this logic should be sunk into getInlineCost. It relies on
|
|
|
196 // the internal implementation of the inline cost metrics rather than
|
|
|
197 // treating them as truly abstract units etc.
|
|
|
198 TotalSecondaryCost = 0;
|
|
|
199 // The candidate cost to be imposed upon the current function.
|
|
|
200 int CandidateCost = IC.getCost() - 1;
|
|
|
201 // If the caller has local linkage and can be inlined to all its callers, we
|
|
|
202 // can apply a huge negative bonus to TotalSecondaryCost.
|
|
|
203 bool ApplyLastCallBonus = Caller->hasLocalLinkage() && !Caller->hasOneUse();
|
|
|
204 // This bool tracks what happens if we DO inline C into B.
|
|
|
205 bool InliningPreventsSomeOuterInline = false;
|
|
|
206 unsigned NumCallerUsers = 0;
|
|
|
207 for (User *U : Caller->users()) {
|
|
|
208 CallBase *CS2 = dyn_cast<CallBase>(U);
|
|
|
209
|
|
|
210 // If this isn't a call to Caller (it could be some other sort
|
|
|
211 // of reference) skip it. Such references will prevent the caller
|
|
|
212 // from being removed.
|
|
|
213 if (!CS2 || CS2->getCalledFunction() != Caller) {
|
|
|
214 ApplyLastCallBonus = false;
|
|
|
215 continue;
|
|
|
216 }
|
|
|
217
|
|
|
218 InlineCost IC2 = GetInlineCost(*CS2);
|
|
|
219 ++NumCallerCallersAnalyzed;
|
|
|
220 if (!IC2) {
|
|
|
221 ApplyLastCallBonus = false;
|
|
|
222 continue;
|
|
|
223 }
|
|
|
224 if (IC2.isAlways())
|
|
|
225 continue;
|
|
|
226
|
|
|
227 // See if inlining of the original callsite would erase the cost delta of
|
|
|
228 // this callsite. We subtract off the penalty for the call instruction,
|
|
|
229 // which we would be deleting.
|
|
|
230 if (IC2.getCostDelta() <= CandidateCost) {
|
|
|
231 InliningPreventsSomeOuterInline = true;
|
|
|
232 TotalSecondaryCost += IC2.getCost();
|
|
|
233 NumCallerUsers++;
|
|
|
234 }
|
|
|
235 }
|
|
|
236
|
|
|
237 if (!InliningPreventsSomeOuterInline)
|
|
|
238 return false;
|
|
|
239
|
|
|
240 // If all outer calls to Caller would get inlined, the cost for the last
|
|
|
241 // one is set very low by getInlineCost, in anticipation that Caller will
|
|
|
242 // be removed entirely. We did not account for this above unless there
|
|
|
243 // is only one caller of Caller.
|
|
|
244 if (ApplyLastCallBonus)
|
|
|
245 TotalSecondaryCost -= InlineConstants::LastCallToStaticBonus;
|
|
|
246
|
|
|
247 // If InlineDeferralScale is negative, then ignore the cost of primary
|
|
|
248 // inlining -- IC.getCost() multiplied by the number of callers to Caller.
|
|
|
249 if (InlineDeferralScale < 0)
|
|
|
250 return TotalSecondaryCost < IC.getCost();
|
|
|
251
|
|
|
252 int TotalCost = TotalSecondaryCost + IC.getCost() * NumCallerUsers;
|
|
|
253 int Allowance = IC.getCost() * InlineDeferralScale;
|
|
|
254 return TotalCost < Allowance;
|
|
|
255 }
|
|
|
256
|
|
|
257 namespace llvm {
|
|
|
258 static std::basic_ostream<char> &operator<<(std::basic_ostream<char> &R,
|
|
|
259 const ore::NV &Arg) {
|
|
|
260 return R << Arg.Val;
|
|
|
261 }
|
|
|
262
|
|
|
263 template <class RemarkT>
|
|
|
264 RemarkT &operator<<(RemarkT &&R, const InlineCost &IC) {
|
|
|
265 using namespace ore;
|
|
|
266 if (IC.isAlways()) {
|
|
|
267 R << "(cost=always)";
|
|
|
268 } else if (IC.isNever()) {
|
|
|
269 R << "(cost=never)";
|
|
|
270 } else {
|
|
|
271 R << "(cost=" << ore::NV("Cost", IC.getCost())
|
|
|
272 << ", threshold=" << ore::NV("Threshold", IC.getThreshold()) << ")";
|
|
|
273 }
|
|
|
274 if (const char *Reason = IC.getReason())
|
|
|
275 R << ": " << ore::NV("Reason", Reason);
|
|
|
276 return R;
|
|
|
277 }
|
|
|
278 } // namespace llvm
|
|
|
279
|
|
|
280 std::string llvm::inlineCostStr(const InlineCost &IC) {
|
|
|
281 std::stringstream Remark;
|
|
|
282 Remark << IC;
|
|
|
283 return Remark.str();
|
|
|
284 }
|
|
|
285
|
|
|
286 void llvm::setInlineRemark(CallBase &CB, StringRef Message) {
|
|
|
287 if (!InlineRemarkAttribute)
|
|
|
288 return;
|
|
|
289
|
|
|
290 Attribute Attr = Attribute::get(CB.getContext(), "inline-remark", Message);
|
|
|
291 CB.addAttribute(AttributeList::FunctionIndex, Attr);
|
|
|
292 }
|
|
|
293
|
|
|
294 /// Return the cost only if the inliner should attempt to inline at the given
|
|
|
295 /// CallSite. If we return the cost, we will emit an optimisation remark later
|
|
|
296 /// using that cost, so we won't do so from this function. Return None if
|
|
|
297 /// inlining should not be attempted.
|
|
|
298 Optional<InlineCost>
|
|
|
299 llvm::shouldInline(CallBase &CB,
|
|
|
300 function_ref<InlineCost(CallBase &CB)> GetInlineCost,
|
|
|
301 OptimizationRemarkEmitter &ORE) {
|
|
|
302 using namespace ore;
|
|
|
303
|
|
|
304 InlineCost IC = GetInlineCost(CB);
|
|
|
305 Instruction *Call = &CB;
|
|
|
306 Function *Callee = CB.getCalledFunction();
|
|
|
307 Function *Caller = CB.getCaller();
|
|
|
308
|
|
|
309 if (IC.isAlways()) {
|
|
|
310 LLVM_DEBUG(dbgs() << " Inlining " << inlineCostStr(IC)
|
|
|
311 << ", Call: " << CB << "\n");
|
|
|
312 return IC;
|
|
|
313 }
|
|
|
314
|
|
|
315 if (!IC) {
|
|
|
316 LLVM_DEBUG(dbgs() << " NOT Inlining " << inlineCostStr(IC)
|
|
|
317 << ", Call: " << CB << "\n");
|
|
|
318 if (IC.isNever()) {
|
|
|
319 ORE.emit([&]() {
|
|
|
320 return OptimizationRemarkMissed(DEBUG_TYPE, "NeverInline", Call)
|
|
|
321 << NV("Callee", Callee) << " not inlined into "
|
|
|
322 << NV("Caller", Caller) << " because it should never be inlined "
|
|
|
323 << IC;
|
|
|
324 });
|
|
|
325 } else {
|
|
|
326 ORE.emit([&]() {
|
|
|
327 return OptimizationRemarkMissed(DEBUG_TYPE, "TooCostly", Call)
|
|
|
328 << NV("Callee", Callee) << " not inlined into "
|
|
|
329 << NV("Caller", Caller) << " because too costly to inline "
|
|
|
330 << IC;
|
|
|
331 });
|
|
|
332 }
|
|
|
333 setInlineRemark(CB, inlineCostStr(IC));
|
|
|
334 return None;
|
|
|
335 }
|
|
|
336
|
|
|
337 int TotalSecondaryCost = 0;
|
|
|
338 if (shouldBeDeferred(Caller, IC, TotalSecondaryCost, GetInlineCost)) {
|
|
|
339 LLVM_DEBUG(dbgs() << " NOT Inlining: " << CB
|
|
|
340 << " Cost = " << IC.getCost()
|
|
|
341 << ", outer Cost = " << TotalSecondaryCost << '\n');
|
|
|
342 ORE.emit([&]() {
|
|
|
343 return OptimizationRemarkMissed(DEBUG_TYPE, "IncreaseCostInOtherContexts",
|
|
|
344 Call)
|
|
|
345 << "Not inlining. Cost of inlining " << NV("Callee", Callee)
|
|
|
346 << " increases the cost of inlining " << NV("Caller", Caller)
|
|
|
347 << " in other contexts";
|
|
|
348 });
|
|
|
349 setInlineRemark(CB, "deferred");
|
|
|
350 // IC does not bool() to false, so get an InlineCost that will.
|
|
|
351 // This will not be inspected to make an error message.
|
|
|
352 return None;
|
|
|
353 }
|
|
|
354
|
|
|
355 LLVM_DEBUG(dbgs() << " Inlining " << inlineCostStr(IC) << ", Call: " << CB
|
|
|
356 << '\n');
|
|
|
357 return IC;
|
|
|
358 }
|
|
|
359
|
|
|
360 void llvm::emitInlinedInto(OptimizationRemarkEmitter &ORE, DebugLoc DLoc,
|
|
|
361 const BasicBlock *Block, const Function &Callee,
|
|
|
362 const Function &Caller, const InlineCost &IC) {
|
|
|
363 ORE.emit([&]() {
|
|
|
364 bool AlwaysInline = IC.isAlways();
|
|
|
365 StringRef RemarkName = AlwaysInline ? "AlwaysInline" : "Inlined";
|
|
|
366 return OptimizationRemark(DEBUG_TYPE, RemarkName, DLoc, Block)
|
|
|
367 << ore::NV("Callee", &Callee) << " inlined into "
|
|
|
368 << ore::NV("Caller", &Caller) << " with " << IC;
|
|
|
369 });
|
|
|
370 }
|
