xref: /llvm-project/llvm/lib/Analysis/InlineOrder.cpp (revision d3b95ecc98d204badbffa1840be7b7a06652a0a3) 
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, OptRatio };
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 
35 namespace {
36 
37 class InlinePriority {
38 public:
39   virtual ~InlinePriority() = default;
40   virtual bool hasLowerPriority(const CallBase *L, const CallBase *R) const = 0;
41   virtual void update(const CallBase *CB) = 0;
42   virtual bool updateAndCheckDecreased(const CallBase *CB) = 0;
43 };
44 
45 class SizePriority : public InlinePriority {
46   using PriorityT = unsigned;
47   DenseMap<const CallBase *, PriorityT> Priorities;
48 
49   PriorityT evaluate(const CallBase *CB) {
50     Function *Callee = CB->getCalledFunction();
51     return Callee->getInstructionCount();
52   }
53 
54   bool isMoreDesirable(const PriorityT &P1, const PriorityT &P2) const {
55     return P1 < P2;
56   }
57 
58 public:
59   bool hasLowerPriority(const CallBase *L, const CallBase *R) const override {
60     const auto I1 = Priorities.find(L);
61     const auto I2 = Priorities.find(R);
62     assert(I1 != Priorities.end() && I2 != Priorities.end());
63     return isMoreDesirable(I2->second, I1->second);
64   }
65 
66   // Update the priority associated with CB.
67   void update(const CallBase *CB) override { Priorities[CB] = evaluate(CB); };
68 
69   bool updateAndCheckDecreased(const CallBase *CB) override {
70     auto It = Priorities.find(CB);
71     const auto OldPriority = It->second;
72     It->second = evaluate(CB);
73     const auto NewPriority = It->second;
74     return isMoreDesirable(OldPriority, NewPriority);
75   }
76 };
77 
78 class CostPriority : public InlinePriority {
79   using PriorityT = int;
80   DenseMap<const CallBase *, PriorityT> Priorities;
81   std::function<InlineCost(const CallBase *)> getInlineCost;
82 
83   PriorityT evaluate(const CallBase *CB) {
84     auto IC = getInlineCost(CB);
85     int cost = 0;
86     if (IC.isVariable())
87       cost = IC.getCost();
88     else
89       cost = IC.isNever() ? INT_MAX : INT_MIN;
90     return cost;
91   }
92 
93   bool isMoreDesirable(const PriorityT &P1, const PriorityT &P2) const {
94     return P1 < P2;
95   }
96 
97 public:
98   CostPriority() = delete;
99   CostPriority(std::function<InlineCost(const CallBase *)> getInlineCost)
100       : getInlineCost(getInlineCost){};
101 
102   bool hasLowerPriority(const CallBase *L, const CallBase *R) const override {
103     const auto I1 = Priorities.find(L);
104     const auto I2 = Priorities.find(R);
105     assert(I1 != Priorities.end() && I2 != Priorities.end());
106     return isMoreDesirable(I2->second, I1->second);
107   }
108 
109   // Update the priority associated with CB.
110   void update(const CallBase *CB) override { Priorities[CB] = evaluate(CB); };
111 
112   bool updateAndCheckDecreased(const CallBase *CB) override {
113     auto It = Priorities.find(CB);
114     const auto OldPriority = It->second;
115     It->second = evaluate(CB);
116     const auto NewPriority = It->second;
117     return isMoreDesirable(OldPriority, NewPriority);
118   }
119 };
120 
121 class PriorityInlineOrder : public InlineOrder<std::pair<CallBase *, int>> {
122   using T = std::pair<CallBase *, int>;
123   using reference = T &;
124   using const_reference = const T &;
125 
126   // A call site could become less desirable for inlining because of the size
127   // growth from prior inlining into the callee. This method is used to lazily
128   // update the desirability of a call site if it's decreasing. It is only
129   // called on pop() or front(), not every time the desirability changes. When
130   // the desirability of the front call site decreases, an updated one would be
131   // pushed right back into the heap. For simplicity, those cases where
132   // the desirability of a call site increases are ignored here.
133   void adjust() {
134     while (PriorityPtr->updateAndCheckDecreased(Heap.front())) {
135       std::pop_heap(Heap.begin(), Heap.end(), isLess);
136       std::push_heap(Heap.begin(), Heap.end(), isLess);
137     }
138   }
139 
140 public:
141   PriorityInlineOrder(std::unique_ptr<InlinePriority> PriorityPtr)
142       : PriorityPtr(std::move(PriorityPtr)) {
143     isLess = [this](const CallBase *L, const CallBase *R) {
144       return this->PriorityPtr->hasLowerPriority(L, R);
145     };
146   }
147 
148   size_t size() override { return Heap.size(); }
149 
150   void push(const T &Elt) override {
151     CallBase *CB = Elt.first;
152     const int InlineHistoryID = Elt.second;
153 
154     Heap.push_back(CB);
155     PriorityPtr->update(CB);
156     std::push_heap(Heap.begin(), Heap.end(), isLess);
157     InlineHistoryMap[CB] = InlineHistoryID;
158   }
159 
160   T pop() override {
161     assert(size() > 0);
162     adjust();
163 
164     CallBase *CB = Heap.front();
165     T Result = std::make_pair(CB, InlineHistoryMap[CB]);
166     InlineHistoryMap.erase(CB);
167     std::pop_heap(Heap.begin(), Heap.end(), isLess);
168     Heap.pop_back();
169     return Result;
170   }
171 
172   void erase_if(function_ref<bool(T)> Pred) override {
173     auto PredWrapper = [=](CallBase *CB) -> bool {
174       return Pred(std::make_pair(CB, 0));
175     };
176     llvm::erase_if(Heap, PredWrapper);
177     std::make_heap(Heap.begin(), Heap.end(), isLess);
178   }
179 
180 private:
181   SmallVector<CallBase *, 16> Heap;
182   std::function<bool(const CallBase *L, const CallBase *R)> isLess;
183   DenseMap<CallBase *, int> InlineHistoryMap;
184   std::unique_ptr<InlinePriority> PriorityPtr;
185 };
186 
187 } // namespace
188 
189 static llvm::InlineCost getInlineCostWrapper(CallBase &CB,
190                                              FunctionAnalysisManager &FAM,
191                                              const InlineParams &Params) {
192   Function &Caller = *CB.getCaller();
193   ProfileSummaryInfo *PSI =
194       FAM.getResult<ModuleAnalysisManagerFunctionProxy>(Caller)
195           .getCachedResult<ProfileSummaryAnalysis>(
196               *CB.getParent()->getParent()->getParent());
197 
198   auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(Caller);
199   auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & {
200     return FAM.getResult<AssumptionAnalysis>(F);
201   };
202   auto GetBFI = [&](Function &F) -> BlockFrequencyInfo & {
203     return FAM.getResult<BlockFrequencyAnalysis>(F);
204   };
205   auto GetTLI = [&](Function &F) -> const TargetLibraryInfo & {
206     return FAM.getResult<TargetLibraryAnalysis>(F);
207   };
208 
209   Function &Callee = *CB.getCalledFunction();
210   auto &CalleeTTI = FAM.getResult<TargetIRAnalysis>(Callee);
211   bool RemarksEnabled =
212       Callee.getContext().getDiagHandlerPtr()->isMissedOptRemarkEnabled(
213           DEBUG_TYPE);
214   return getInlineCost(CB, Params, CalleeTTI, GetAssumptionCache, GetTLI,
215                        GetBFI, PSI, RemarksEnabled ? &ORE : nullptr);
216 }
217 
218 std::unique_ptr<InlineOrder<std::pair<CallBase *, int>>>
219 llvm::getInlineOrder(FunctionAnalysisManager &FAM, const InlineParams &Params) {
220   switch (UseInlinePriority) {
221   case InlinePriorityMode::Size:
222     LLVM_DEBUG(dbgs() << "    Current used priority: Size priority ---- \n");
223     return std::make_unique<PriorityInlineOrder>(
224         std::make_unique<SizePriority>());
225 
226   case InlinePriorityMode::Cost:
227     LLVM_DEBUG(dbgs() << "    Current used priority: Cost priority ---- \n");
228     return std::make_unique<PriorityInlineOrder>(
229         std::make_unique<CostPriority>([&](const CallBase *CB) -> InlineCost {
230           return getInlineCostWrapper(const_cast<CallBase &>(*CB), FAM, Params);
231         }));
232 
233   default:
234     llvm_unreachable("Unsupported Inline Priority Mode");
235     break;
236   }
237   return nullptr;
238 }
239