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