LLVM 19.0.0git
InlineOrder.cpp
Go to the documentation of this file.
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
20
21using namespace llvm;
22
23#define DEBUG_TYPE "inline-order"
24
25enum class InlinePriorityMode : int { Size, Cost, CostBenefit, ML };
26
28 "inline-priority-mode", cl::init(InlinePriorityMode::Size), cl::Hidden,
29 cl::desc("Choose the priority mode to use in module inline"),
31 "Use callee size priority."),
33 "Use inline cost priority."),
35 "Use cost-benefit ratio."),
36 clEnumValN(InlinePriorityMode::ML, "ml", "Use ML.")));
37
39 "module-inliner-top-priority-threshold", cl::Hidden, cl::init(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,
47 const InlineParams &Params) {
48 Function &Caller = *CB.getCaller();
51 .getCachedResult<ProfileSummaryAnalysis>(
52 *CB.getParent()->getParent()->getParent());
53
55 auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & {
57 };
58 auto GetBFI = [&](Function &F) -> BlockFrequencyInfo & {
60 };
61 auto GetTLI = [&](Function &F) -> const TargetLibraryInfo & {
63 };
64
66 auto &CalleeTTI = FAM.getResult<TargetIRAnalysis>(Callee);
67 bool RemarksEnabled =
68 Callee.getContext().getDiagHandlerPtr()->isMissedOptRemarkEnabled(
70 return getInlineCost(CB, Params, CalleeTTI, GetAssumptionCache, GetTLI,
71 GetBFI, PSI, RemarksEnabled ? &ORE : nullptr);
72}
73
74class SizePriority {
75public:
76 SizePriority() = default;
77 SizePriority(const CallBase *CB, FunctionAnalysisManager &,
78 const InlineParams &) {
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(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(const_cast<CallBase &>(*CB), FAM, Params);
117 Cost = IC.getCost();
118 StaticBonusApplied = IC.getStaticBonusApplied();
119 CostBenefit = IC.getCostBenefit();
120 }
121
122 static bool isMoreDesirable(const CostBenefitPriority &P1,
123 const CostBenefitPriority &P2) {
124 // We prioritize call sites in the dictionary order of the following
125 // priorities:
126 //
127 // 1. Those call sites that are expected to reduce the caller size when
128 // inlined. Within them, we prioritize those call sites with bigger
129 // reduction.
130 //
131 // 2. Those call sites that have gone through the cost-benefit analysis.
132 // Currently, they are limited to hot call sites. Within them, we
133 // prioritize those call sites with higher benefit-to-cost ratios.
134 //
135 // 3. Remaining call sites are prioritized according to their costs.
136
137 // We add back StaticBonusApplied to determine whether we expect the caller
138 // to shrink (even if we don't delete the callee).
139 bool P1ReducesCallerSize =
140 P1.Cost + P1.StaticBonusApplied < ModuleInlinerTopPriorityThreshold;
141 bool P2ReducesCallerSize =
142 P2.Cost + P2.StaticBonusApplied < ModuleInlinerTopPriorityThreshold;
143 if (P1ReducesCallerSize || P2ReducesCallerSize) {
144 // If one reduces the caller size while the other doesn't, then return
145 // true iff P1 reduces the caller size.
146 if (P1ReducesCallerSize != P2ReducesCallerSize)
147 return P1ReducesCallerSize;
148
149 // If they both reduce the caller size, pick the one with the smaller
150 // cost.
151 return P1.Cost < P2.Cost;
152 }
153
154 bool P1HasCB = P1.CostBenefit.has_value();
155 bool P2HasCB = P2.CostBenefit.has_value();
156 if (P1HasCB || P2HasCB) {
157 // If one has undergone the cost-benefit analysis while the other hasn't,
158 // then return true iff P1 has.
159 if (P1HasCB != P2HasCB)
160 return P1HasCB;
161
162 // If they have undergone the cost-benefit analysis, then pick the one
163 // with a higher benefit-to-cost ratio.
164 APInt LHS = P1.CostBenefit->getBenefit() * P2.CostBenefit->getCost();
165 APInt RHS = P2.CostBenefit->getBenefit() * P1.CostBenefit->getCost();
166 return LHS.ugt(RHS);
167 }
168
169 // Remaining call sites are ordered according to their costs.
170 return P1.Cost < P2.Cost;
171 }
172
173private:
174 int Cost = INT_MAX;
175 int StaticBonusApplied = 0;
176 std::optional<CostBenefitPair> CostBenefit;
177};
178
179class MLPriority {
180public:
181 MLPriority() = default;
182 MLPriority(const CallBase *CB, FunctionAnalysisManager &FAM,
183 const InlineParams &Params) {
184 auto IC = getInlineCostWrapper(const_cast<CallBase &>(*CB), FAM, Params);
185 if (IC.isVariable())
186 Cost = IC.getCost();
187 else
188 Cost = IC.isNever() ? INT_MAX : INT_MIN;
189 }
190
191 static bool isMoreDesirable(const MLPriority &P1, const MLPriority &P2) {
192 return P1.Cost < P2.Cost;
193 }
194
195private:
196 int Cost = INT_MAX;
197};
198
199template <typename PriorityT>
200class PriorityInlineOrder : public InlineOrder<std::pair<CallBase *, int>> {
201 using T = std::pair<CallBase *, int>;
202
203 bool hasLowerPriority(const CallBase *L, const CallBase *R) const {
204 const auto I1 = Priorities.find(L);
205 const auto I2 = Priorities.find(R);
206 assert(I1 != Priorities.end() && I2 != Priorities.end());
207 return PriorityT::isMoreDesirable(I2->second, I1->second);
208 }
209
210 bool updateAndCheckDecreased(const CallBase *CB) {
211 auto It = Priorities.find(CB);
212 const auto OldPriority = It->second;
213 It->second = PriorityT(CB, FAM, Params);
214 const auto NewPriority = It->second;
215 return PriorityT::isMoreDesirable(OldPriority, NewPriority);
216 }
217
218 // A call site could become less desirable for inlining because of the size
219 // growth from prior inlining into the callee. This method is used to lazily
220 // update the desirability of a call site if it's decreasing. It is only
221 // called on pop(), not every time the desirability changes. When the
222 // desirability of the front call site decreases, an updated one would be
223 // pushed right back into the heap. For simplicity, those cases where the
224 // desirability of a call site increases are ignored here.
225 void pop_heap_adjust() {
226 std::pop_heap(Heap.begin(), Heap.end(), isLess);
227 while (updateAndCheckDecreased(Heap.back())) {
228 std::push_heap(Heap.begin(), Heap.end(), isLess);
229 std::pop_heap(Heap.begin(), Heap.end(), isLess);
230 }
231 }
232
233public:
234 PriorityInlineOrder(FunctionAnalysisManager &FAM, const InlineParams &Params)
235 : FAM(FAM), Params(Params) {
236 isLess = [&](const CallBase *L, const CallBase *R) {
237 return hasLowerPriority(L, R);
238 };
239 }
240
241 size_t size() override { return Heap.size(); }
242
243 void push(const T &Elt) override {
244 CallBase *CB = Elt.first;
245 const int InlineHistoryID = Elt.second;
246
247 Heap.push_back(CB);
248 Priorities[CB] = PriorityT(CB, FAM, Params);
249 std::push_heap(Heap.begin(), Heap.end(), isLess);
250 InlineHistoryMap[CB] = InlineHistoryID;
251 }
252
253 T pop() override {
254 assert(size() > 0);
255 pop_heap_adjust();
256
257 CallBase *CB = Heap.pop_back_val();
258 T Result = std::make_pair(CB, InlineHistoryMap[CB]);
259 InlineHistoryMap.erase(CB);
260 return Result;
261 }
262
263 void erase_if(function_ref<bool(T)> Pred) override {
264 auto PredWrapper = [=](CallBase *CB) -> bool {
265 return Pred(std::make_pair(CB, InlineHistoryMap[CB]));
266 };
267 llvm::erase_if(Heap, PredWrapper);
268 std::make_heap(Heap.begin(), Heap.end(), isLess);
269 }
270
271private:
273 std::function<bool(const CallBase *L, const CallBase *R)> isLess;
274 DenseMap<CallBase *, int> InlineHistoryMap;
277 const InlineParams &Params;
278};
279
280} // namespace
281
283bool llvm::PluginInlineOrderAnalysis::HasBeenRegistered;
284
285std::unique_ptr<InlineOrder<std::pair<CallBase *, int>>>
287 const InlineParams &Params,
289 switch (UseInlinePriority) {
291 LLVM_DEBUG(dbgs() << " Current used priority: Size priority ---- \n");
292 return std::make_unique<PriorityInlineOrder<SizePriority>>(FAM, Params);
293
295 LLVM_DEBUG(dbgs() << " Current used priority: Cost priority ---- \n");
296 return std::make_unique<PriorityInlineOrder<CostPriority>>(FAM, Params);
297
300 dbgs() << " Current used priority: cost-benefit priority ---- \n");
301 return std::make_unique<PriorityInlineOrder<CostBenefitPriority>>(FAM,
302 Params);
304 LLVM_DEBUG(dbgs() << " Current used priority: ML priority ---- \n");
305 return std::make_unique<PriorityInlineOrder<MLPriority>>(FAM, Params);
306 }
307 return nullptr;
308}
309
310std::unique_ptr<InlineOrder<std::pair<CallBase *, int>>>
314 LLVM_DEBUG(dbgs() << " Current used priority: plugin ---- \n");
315 return MAM.getResult<PluginInlineOrderAnalysis>(M).Factory(FAM, Params, MAM,
316 M);
317 }
318 return getDefaultInlineOrder(FAM, Params, MAM, M);
319}
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
Definition: CommandLine.h:693
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This is the interface for a simple mod/ref and alias analysis over globals.
static cl::opt< int > ModuleInlinerTopPriorityThreshold("module-inliner-top-priority-threshold", cl::Hidden, cl::init(0), cl::desc("The cost threshold for call sites that get inlined without the " "cost-benefit analysis"))
InlinePriorityMode
Definition: InlineOrder.cpp:25
static cl::opt< InlinePriorityMode > UseInlinePriority("inline-priority-mode", cl::init(InlinePriorityMode::Size), cl::Hidden, cl::desc("Choose the priority mode to use in module inline"), cl::values(clEnumValN(InlinePriorityMode::Size, "size", "Use callee size priority."), clEnumValN(InlinePriorityMode::Cost, "cost", "Use inline cost priority."), clEnumValN(InlinePriorityMode::CostBenefit, "cost-benefit", "Use cost-benefit ratio."), clEnumValN(InlinePriorityMode::ML, "ml", "Use ML.")))
#define DEBUG_TYPE
Definition: InlineOrder.cpp:23
#define F(x, y, z)
Definition: MD5.cpp:55
FunctionAnalysisManager FAM
ModuleAnalysisManager MAM
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This pass exposes codegen information to IR-level passes.
Value * RHS
Value * LHS
Class for arbitrary precision integers.
Definition: APInt.h:76
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:348
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:500
A function analysis which provides an AssumptionCache.
A cache of @llvm.assume calls within a function.
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:214
Analysis pass which computes BlockFrequencyInfo.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1457
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
Definition: InstrTypes.h:1696
Function * getCaller()
Helper to get the caller (the parent function).
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:655
Represents the cost of inlining a function.
Definition: InlineCost.h:89
virtual T pop()=0
virtual size_t size()=0
virtual void erase_if(function_ref< bool(T)> Pred)=0
virtual void push(const T &Elt)=0
const BasicBlock * getParent() const
Definition: Instruction.h:150
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
Definition: PassManager.h:783
Used for dynamically loading instances of InlineOrder as plugins.
Definition: InlineOrder.h:52
Analysis providing profile information.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
Analysis pass providing the TargetTransformInfo.
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
An efficient, type-erasing, non-owning reference to a callable.
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
Definition: CommandLine.h:718
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:450
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
InlineCost getInlineCost(CallBase &Call, const InlineParams &Params, TargetTransformInfo &CalleeTTI, function_ref< AssumptionCache &(Function &)> GetAssumptionCache, function_ref< const TargetLibraryInfo &(Function &)> GetTLI, function_ref< BlockFrequencyInfo &(Function &)> GetBFI=nullptr, ProfileSummaryInfo *PSI=nullptr, OptimizationRemarkEmitter *ORE=nullptr)
Get an InlineCost object representing the cost of inlining this callsite.
std::unique_ptr< InlineOrder< std::pair< CallBase *, int > > > getDefaultInlineOrder(FunctionAnalysisManager &FAM, const InlineParams &Params, ModuleAnalysisManager &MAM, Module &M)
std::unique_ptr< InlineOrder< std::pair< CallBase *, int > > > getInlineOrder(FunctionAnalysisManager &FAM, const InlineParams &Params, ModuleAnalysisManager &MAM, Module &M)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
Definition: STLExtras.h:2031
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: Analysis.h:26
Thresholds to tune inline cost analysis.
Definition: InlineCost.h:205