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