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", "Use ML.")));
37 
38 static cl::opt<int> ModuleInlinerTopPriorityThreshold(
39     "moudle-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 
43 namespace {
44 
45 llvm::InlineCost getInlineCostWrapper(CallBase &CB,
46                                       FunctionAnalysisManager &FAM,
47                                       const InlineParams &Params) {
48   Function &Caller = *CB.getCaller();
49   ProfileSummaryInfo *PSI =
50       FAM.getResult<ModuleAnalysisManagerFunctionProxy>(Caller)
51           .getCachedResult<ProfileSummaryAnalysis>(
52               *CB.getParent()->getParent()->getParent());
53 
54   auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(Caller);
55   auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & {
56     return FAM.getResult<AssumptionAnalysis>(F);
57   };
58   auto GetBFI = [&](Function &F) -> BlockFrequencyInfo & {
59     return FAM.getResult<BlockFrequencyAnalysis>(F);
60   };
61   auto GetTLI = [&](Function &F) -> const TargetLibraryInfo & {
62     return FAM.getResult<TargetLibraryAnalysis>(F);
63   };
64 
65   Function &Callee = *CB.getCalledFunction();
66   auto &CalleeTTI = FAM.getResult<TargetIRAnalysis>(Callee);
67   bool RemarksEnabled =
68       Callee.getContext().getDiagHandlerPtr()->isMissedOptRemarkEnabled(
69           DEBUG_TYPE);
70   return getInlineCost(CB, Params, CalleeTTI, GetAssumptionCache, GetTLI,
71                        GetBFI, PSI, RemarksEnabled ? &ORE : nullptr);
72 }
73 
74 class SizePriority {
75 public:
76   SizePriority() = default;
77   SizePriority(const CallBase *CB, FunctionAnalysisManager &,
78                const InlineParams &) {
79     Function *Callee = CB->getCalledFunction();
80     Size = Callee->getInstructionCount();
81   }
82 
83   static bool isMoreDesirable(const SizePriority &P1, const SizePriority &P2) {
84     return P1.Size < P2.Size;
85   }
86 
87 private:
88   unsigned Size = UINT_MAX;
89 };
90 
91 class CostPriority {
92 public:
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 
107 private:
108   int Cost = INT_MAX;
109 };
110 
111 class CostBenefitPriority {
112 public:
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 
173 private:
174   int Cost = INT_MAX;
175   int StaticBonusApplied = 0;
176   std::optional<CostBenefitPair> CostBenefit;
177 };
178 
179 class MLPriority {
180 public:
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 
195 private:
196   int Cost = INT_MAX;
197 };
198 
199 template <typename PriorityT>
200 class 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 
232 public:
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 
272 private:
273   SmallVector<CallBase *, 16> Heap;
274   std::function<bool(const CallBase *L, const CallBase *R)> isLess;
275   DenseMap<CallBase *, int> InlineHistoryMap;
276   DenseMap<const CallBase *, PriorityT> Priorities;
277   FunctionAnalysisManager &FAM;
278   const InlineParams &Params;
279 };
280 
281 } // namespace
282 
283 AnalysisKey llvm::PluginInlineOrderAnalysis::Key;
284 bool llvm::PluginInlineOrderAnalysis::HasBeenRegistered;
285 
286 std::unique_ptr<InlineOrder<std::pair<CallBase *, int>>>
287 llvm::getDefaultInlineOrder(FunctionAnalysisManager &FAM,
288                             const InlineParams &Params,
289                             ModuleAnalysisManager &MAM, Module &M) {
290   switch (UseInlinePriority) {
291   case InlinePriorityMode::Size:
292     LLVM_DEBUG(dbgs() << "    Current used priority: Size priority ---- \n");
293     return std::make_unique<PriorityInlineOrder<SizePriority>>(FAM, Params);
294 
295   case InlinePriorityMode::Cost:
296     LLVM_DEBUG(dbgs() << "    Current used priority: Cost priority ---- \n");
297     return std::make_unique<PriorityInlineOrder<CostPriority>>(FAM, Params);
298 
299   case InlinePriorityMode::CostBenefit:
300     LLVM_DEBUG(
301         dbgs() << "    Current used priority: cost-benefit priority ---- \n");
302     return std::make_unique<PriorityInlineOrder<CostBenefitPriority>>(FAM,
303                                                                       Params);
304   case InlinePriorityMode::ML:
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 
311 std::unique_ptr<InlineOrder<std::pair<CallBase *, int>>>
312 llvm::getInlineOrder(FunctionAnalysisManager &FAM, const InlineParams &Params,
313                      ModuleAnalysisManager &MAM, Module &M) {
314   if (llvm::PluginInlineOrderAnalysis::isRegistered()) {
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 }