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