1//===- InlineOrder.cpp - Inlining order abstraction -*- C++ ---*-----------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "llvm/Analysis/InlineOrder.h"
10#include "llvm/Analysis/AssumptionCache.h"
11#include "llvm/Analysis/BlockFrequencyInfo.h"
12#include "llvm/Analysis/GlobalsModRef.h"
13#include "llvm/Analysis/InlineAdvisor.h"
14#include "llvm/Analysis/InlineCost.h"
15#include "llvm/Analysis/OptimizationRemarkEmitter.h"
16#include "llvm/Analysis/ProfileSummaryInfo.h"
17#include "llvm/Analysis/TargetLibraryInfo.h"
18#include "llvm/Analysis/TargetTransformInfo.h"
19#include "llvm/Support/CommandLine.h"
20
21using namespace llvm;
22
23#define DEBUG_TYPE "inline-order"
24
25enum class InlinePriorityMode : int { Size, Cost, CostBenefit, ML };
26
27static cl::opt<InlinePriorityMode> UseInlinePriority(
28 "inline-priority-mode", cl::init(Val: InlinePriorityMode::Size), cl::Hidden,
29 cl::desc("Choose the priority mode to use in module inline"),
30 cl::values(clEnumValN(InlinePriorityMode::Size, "size",
31 "Use callee size priority."),
32 clEnumValN(InlinePriorityMode::Cost, "cost",
33 "Use inline cost priority."),
34 clEnumValN(InlinePriorityMode::CostBenefit, "cost-benefit",
35 "Use cost-benefit ratio."),
36 clEnumValN(InlinePriorityMode::ML, "ml", "Use ML.")));
37
38static cl::opt<int> ModuleInlinerTopPriorityThreshold(
39 "module-inliner-top-priority-threshold", cl::Hidden, cl::init(Val: 0),
40 cl::desc("The cost threshold for call sites that get inlined without the "
41 "cost-benefit analysis"));
42
43namespace {
44
45llvm::InlineCost getInlineCostWrapper(CallBase &CB,
46 FunctionAnalysisManager &FAM,
47 const InlineParams &Params) {
48 Function &Caller = *CB.getCaller();
49 ProfileSummaryInfo *PSI =
50 FAM.getResult<ModuleAnalysisManagerFunctionProxy>(IR&: Caller)
51 .getCachedResult<ProfileSummaryAnalysis>(
52 IR&: *CB.getParent()->getParent()->getParent());
53
54 auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(IR&: Caller);
55 auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & {
56 return FAM.getResult<AssumptionAnalysis>(IR&: F);
57 };
58 auto GetBFI = [&](Function &F) -> BlockFrequencyInfo & {
59 return FAM.getResult<BlockFrequencyAnalysis>(IR&: F);
60 };
61 auto GetTLI = [&](Function &F) -> const TargetLibraryInfo & {
62 return FAM.getResult<TargetLibraryAnalysis>(IR&: F);
63 };
64
65 Function &Callee = *CB.getCalledFunction();
66 auto &CalleeTTI = FAM.getResult<TargetIRAnalysis>(IR&: Callee);
67 bool RemarksEnabled =
68 Callee.getContext().getDiagHandlerPtr()->isMissedOptRemarkEnabled(
69 DEBUG_TYPE);
70 return getInlineCost(Call&: CB, Params, CalleeTTI, GetAssumptionCache, GetTLI,
71 GetBFI, PSI, ORE: RemarksEnabled ? &ORE : nullptr);
72}
73
74class SizePriority {
75public:
76 SizePriority() = default;
77 SizePriority(const CallBase *CB, FunctionAnalysisManager &,
78 const InlineParams &) {
79 Function *Callee = CB->getCalledFunction();
80 Size = Callee->getInstructionCount();
81 }
82
83 static bool isMoreDesirable(const SizePriority &P1, const SizePriority &P2) {
84 return P1.Size < P2.Size;
85 }
86
87private:
88 unsigned Size = UINT_MAX;
89};
90
91class CostPriority {
92public:
93 CostPriority() = default;
94 CostPriority(const CallBase *CB, FunctionAnalysisManager &FAM,
95 const InlineParams &Params) {
96 auto IC = getInlineCostWrapper(CB&: const_cast<CallBase &>(*CB), FAM, Params);
97 if (IC.isVariable())
98 Cost = IC.getCost();
99 else
100 Cost = IC.isNever() ? INT_MAX : INT_MIN;
101 }
102
103 static bool isMoreDesirable(const CostPriority &P1, const CostPriority &P2) {
104 return P1.Cost < P2.Cost;
105 }
106
107private:
108 int Cost = INT_MAX;
109};
110
111class CostBenefitPriority {
112public:
113 CostBenefitPriority() = default;
114 CostBenefitPriority(const CallBase *CB, FunctionAnalysisManager &FAM,
115 const InlineParams &Params) {
116 auto IC = getInlineCostWrapper(CB&: const_cast<CallBase &>(*CB), FAM, Params);
117 if (IC.isVariable()) {
118 Cost = IC.getCost();
119 StaticBonusApplied = IC.getStaticBonusApplied();
120 CostBenefit = IC.getCostBenefit();
121 } else {
122 Cost = IC.isNever() ? INT_MAX : INT_MIN;
123 StaticBonusApplied = 0;
124 CostBenefit = std::nullopt;
125 }
126 }
127
128 static bool isMoreDesirable(const CostBenefitPriority &P1,
129 const CostBenefitPriority &P2) {
130 // We prioritize call sites in the dictionary order of the following
131 // priorities:
132 //
133 // 1. Those call sites that are expected to reduce the caller size when
134 // inlined. Within them, we prioritize those call sites with bigger
135 // reduction.
136 //
137 // 2. Those call sites that have gone through the cost-benefit analysis.
138 // Currently, they are limited to hot call sites. Within them, we
139 // prioritize those call sites with higher benefit-to-cost ratios.
140 //
141 // 3. Remaining call sites are prioritized according to their costs.
142
143 // We add back StaticBonusApplied to determine whether we expect the caller
144 // to shrink (even if we don't delete the callee).
145 bool P1ReducesCallerSize =
146 P1.Cost + P1.StaticBonusApplied < ModuleInlinerTopPriorityThreshold;
147 bool P2ReducesCallerSize =
148 P2.Cost + P2.StaticBonusApplied < ModuleInlinerTopPriorityThreshold;
149 if (P1ReducesCallerSize || P2ReducesCallerSize) {
150 // If one reduces the caller size while the other doesn't, then return
151 // true iff P1 reduces the caller size.
152 if (P1ReducesCallerSize != P2ReducesCallerSize)
153 return P1ReducesCallerSize;
154
155 // If they both reduce the caller size, pick the one with the smaller
156 // cost.
157 return P1.Cost < P2.Cost;
158 }
159
160 bool P1HasCB = P1.CostBenefit.has_value();
161 bool P2HasCB = P2.CostBenefit.has_value();
162 if (P1HasCB || P2HasCB) {
163 // If one has undergone the cost-benefit analysis while the other hasn't,
164 // then return true iff P1 has.
165 if (P1HasCB != P2HasCB)
166 return P1HasCB;
167
168 // If they have undergone the cost-benefit analysis, then pick the one
169 // with a higher benefit-to-cost ratio.
170 APInt LHS = P1.CostBenefit->getBenefit() * P2.CostBenefit->getCost();
171 APInt RHS = P2.CostBenefit->getBenefit() * P1.CostBenefit->getCost();
172 return LHS.ugt(RHS);
173 }
174
175 // Remaining call sites are ordered according to their costs.
176 return P1.Cost < P2.Cost;
177 }
178
179private:
180 int Cost = INT_MAX;
181 int StaticBonusApplied = 0;
182 std::optional<CostBenefitPair> CostBenefit;
183};
184
185class MLPriority {
186public:
187 MLPriority() = default;
188 MLPriority(const CallBase *CB, FunctionAnalysisManager &FAM,
189 const InlineParams &Params) {
190 auto IC = getInlineCostWrapper(CB&: const_cast<CallBase &>(*CB), FAM, Params);
191 if (IC.isVariable())
192 Cost = IC.getCost();
193 else
194 Cost = IC.isNever() ? INT_MAX : INT_MIN;
195 }
196
197 static bool isMoreDesirable(const MLPriority &P1, const MLPriority &P2) {
198 return P1.Cost < P2.Cost;
199 }
200
201private:
202 int Cost = INT_MAX;
203};
204
205template <typename PriorityT> class PriorityInlineOrder : public InlineOrder {
206 bool hasLowerPriority(const CallBase *L, const CallBase *R) const {
207 const auto I1 = Priorities.find(L);
208 const auto I2 = Priorities.find(R);
209 assert(I1 != Priorities.end() && I2 != Priorities.end());
210 return PriorityT::isMoreDesirable(I2->second, I1->second);
211 }
212
213 bool updateAndCheckDecreased(const CallBase *CB) {
214 auto It = Priorities.find(CB);
215 const auto OldPriority = It->second;
216 It->second = PriorityT(CB, FAM, Params);
217 const auto NewPriority = It->second;
218 return PriorityT::isMoreDesirable(OldPriority, NewPriority);
219 }
220
221 // A call site could become less desirable for inlining because of the size
222 // growth from prior inlining into the callee. This method is used to lazily
223 // update the desirability of a call site if it's decreasing. It is only
224 // called on pop(), not every time the desirability changes. When the
225 // desirability of the front call site decreases, an updated one would be
226 // pushed right back into the heap. For simplicity, those cases where the
227 // desirability of a call site increases are ignored here.
228 void pop_heap_adjust() {
229 std::pop_heap(first: Heap.begin(), last: Heap.end(), comp: isLess);
230 while (updateAndCheckDecreased(CB: Heap.back())) {
231 std::push_heap(first: Heap.begin(), last: Heap.end(), comp: isLess);
232 std::pop_heap(first: Heap.begin(), last: Heap.end(), comp: isLess);
233 }
234 }
235
236public:
237 PriorityInlineOrder(FunctionAnalysisManager &FAM, const InlineParams &Params)
238 : FAM(FAM), Params(Params) {
239 isLess = [&](const CallBase *L, const CallBase *R) {
240 return hasLowerPriority(L, R);
241 };
242 }
243
244 size_t size() override { return Heap.size(); }
245
246 void push(CallBase *CB) override {
247 Heap.push_back(Elt: CB);
248 Priorities[CB] = PriorityT(CB, FAM, Params);
249 std::push_heap(first: Heap.begin(), last: Heap.end(), comp: isLess);
250 }
251
252 CallBase *pop() override {
253 assert(size() > 0);
254 pop_heap_adjust();
255
256 return Heap.pop_back_val();
257 }
258
259 void erase_if(function_ref<bool(CallBase *)> Pred) override {
260 llvm::erase_if(C&: Heap, P: Pred);
261 std::make_heap(first: Heap.begin(), last: Heap.end(), comp: isLess);
262 }
263
264private:
265 SmallVector<CallBase *, 16> Heap;
266 std::function<bool(const CallBase *L, const CallBase *R)> isLess;
267 DenseMap<const CallBase *, PriorityT> Priorities;
268 FunctionAnalysisManager &FAM;
269 const InlineParams &Params;
270};
271
272} // namespace
273
274AnalysisKey llvm::PluginInlineOrderAnalysis::Key;
275
276std::unique_ptr<InlineOrder>
277llvm::getDefaultInlineOrder(FunctionAnalysisManager &FAM,
278 const InlineParams &Params,
279 ModuleAnalysisManager &MAM, Module &M) {
280 switch (UseInlinePriority) {
281 case InlinePriorityMode::Size:
282 LLVM_DEBUG(dbgs() << " Current used priority: Size priority ---- \n");
283 return std::make_unique<PriorityInlineOrder<SizePriority>>(args&: FAM, args: Params);
284
285 case InlinePriorityMode::Cost:
286 LLVM_DEBUG(dbgs() << " Current used priority: Cost priority ---- \n");
287 return std::make_unique<PriorityInlineOrder<CostPriority>>(args&: FAM, args: Params);
288
289 case InlinePriorityMode::CostBenefit:
290 LLVM_DEBUG(
291 dbgs() << " Current used priority: cost-benefit priority ---- \n");
292 return std::make_unique<PriorityInlineOrder<CostBenefitPriority>>(args&: FAM,
293 args: Params);
294 case InlinePriorityMode::ML:
295 LLVM_DEBUG(dbgs() << " Current used priority: ML priority ---- \n");
296 return std::make_unique<PriorityInlineOrder<MLPriority>>(args&: FAM, args: Params);
297 }
298 return nullptr;
299}
300
301std::unique_ptr<InlineOrder> llvm::getInlineOrder(FunctionAnalysisManager &FAM,
302 const InlineParams &Params,
303 ModuleAnalysisManager &MAM,
304 Module &M) {
305 if (MAM.isPassRegistered<PluginInlineOrderAnalysis>()) {
306 LLVM_DEBUG(dbgs() << " Current used priority: plugin ---- \n");
307 return MAM.getResult<PluginInlineOrderAnalysis>(IR&: M).Factory(FAM, Params, MAM,
308 M);
309 }
310 return getDefaultInlineOrder(FAM, Params, MAM, M);
311}
312