LLVM 18.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() or front(), not every time the desirability changes. When
222 // the desirability of the front call site decreases, an updated one would be
223 // pushed right back into the heap. For simplicity, those cases where
224 // the desirability of a call site increases are ignored here.
225 void adjust() {
226 while (updateAndCheckDecreased(Heap.front())) {
227 std::pop_heap(Heap.begin(), Heap.end(), isLess);
228 std::push_heap(Heap.begin(), Heap.end(), isLess);
229 }
230 }
231
232public:
233 PriorityInlineOrder(FunctionAnalysisManager &FAM, const InlineParams &Params)
234 : FAM(FAM), Params(Params) {
235 isLess = [&](const CallBase *L, const CallBase *R) {
236 return hasLowerPriority(L, R);
237 };
238 }
239
240 size_t size() override { return Heap.size(); }
241
242 void push(const T &Elt) override {
243 CallBase *CB = Elt.first;
244 const int InlineHistoryID = Elt.second;
245
246 Heap.push_back(CB);
247 Priorities[CB] = PriorityT(CB, FAM, Params);
248 std::push_heap(Heap.begin(), Heap.end(), isLess);
249 InlineHistoryMap[CB] = InlineHistoryID;
250 }
251
252 T pop() override {
253 assert(size() > 0);
254 adjust();
255
256 CallBase *CB = Heap.front();
257 T Result = std::make_pair(CB, InlineHistoryMap[CB]);
258 InlineHistoryMap.erase(CB);
259 std::pop_heap(Heap.begin(), Heap.end(), isLess);
260 Heap.pop_back();
261 return Result;
262 }
263
264 void erase_if(function_ref<bool(T)> Pred) override {
265 auto PredWrapper = [=](CallBase *CB) -> bool {
266 return Pred(std::make_pair(CB, 0));
267 };
268 llvm::erase_if(Heap, PredWrapper);
269 std::make_heap(Heap.begin(), Heap.end(), isLess);
270 }
271
272private:
274 std::function<bool(const CallBase *L, const CallBase *R)> isLess;
275 DenseMap<CallBase *, int> InlineHistoryMap;
278 const InlineParams &Params;
279};
280
281} // namespace
282
284bool llvm::PluginInlineOrderAnalysis::HasBeenRegistered;
285
286std::unique_ptr<InlineOrder<std::pair<CallBase *, int>>>
288 const InlineParams &Params,
290 switch (UseInlinePriority) {
292 LLVM_DEBUG(dbgs() << " Current used priority: Size priority ---- \n");
293 return std::make_unique<PriorityInlineOrder<SizePriority>>(FAM, Params);
294
296 LLVM_DEBUG(dbgs() << " Current used priority: Cost priority ---- \n");
297 return std::make_unique<PriorityInlineOrder<CostPriority>>(FAM, Params);
298
301 dbgs() << " Current used priority: cost-benefit priority ---- \n");
302 return std::make_unique<PriorityInlineOrder<CostBenefitPriority>>(FAM,
303 Params);
305 LLVM_DEBUG(dbgs() << " Current used priority: ML priority ---- \n");
306 return std::make_unique<PriorityInlineOrder<MLPriority>>(FAM, Params);
307 }
308 return nullptr;
309}
310
311std::unique_ptr<InlineOrder<std::pair<CallBase *, int>>>
315 LLVM_DEBUG(dbgs() << " Current used priority: plugin ---- \n");
316 return MAM.getResult<PluginInlineOrderAnalysis>(M).Factory(FAM, Params, MAM,
317 M);
318 }
319 return getDefaultInlineOrder(FAM, Params, MAM, M);
320}
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
Definition: CommandLine.h:680
#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:620
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
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:112
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:1190
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
Definition: InstrTypes.h:1412
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:652
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:90
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:1058
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:1200
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:705
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
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:2021
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
Thresholds to tune inline cost analysis.
Definition: InlineCost.h:205