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