xref: /openbsd-src/gnu/llvm/llvm/lib/Analysis/InlineOrder.cpp (revision d415bd752c734aee168c4ee86ff32e8cc249eb16)
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