llvm-project

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
    "module-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
    if (IC.isVariable())
118
      Cost = IC.getCost();
119
    else
120
      Cost = IC.isNever() ? INT_MAX : INT_MIN;
121
    StaticBonusApplied = IC.getStaticBonusApplied();
122
    CostBenefit = IC.getCostBenefit();
123
  }
124

125
  static bool isMoreDesirable(const CostBenefitPriority &P1,
126
                              const CostBenefitPriority &P2) {
127
    // We prioritize call sites in the dictionary order of the following
128
    // priorities:
129
    //
130
    // 1. Those call sites that are expected to reduce the caller size when
131
    //    inlined.  Within them, we prioritize those call sites with bigger
132
    //    reduction.
133
    //
134
    // 2. Those call sites that have gone through the cost-benefit analysis.
135
    //    Currently, they are limited to hot call sites.  Within them, we
136
    //    prioritize those call sites with higher benefit-to-cost ratios.
137
    //
138
    // 3. Remaining call sites are prioritized according to their costs.
139

140
    // We add back StaticBonusApplied to determine whether we expect the caller
141
    // to shrink (even if we don't delete the callee).
142
    bool P1ReducesCallerSize =
143
        P1.Cost + P1.StaticBonusApplied < ModuleInlinerTopPriorityThreshold;
144
    bool P2ReducesCallerSize =
145
        P2.Cost + P2.StaticBonusApplied < ModuleInlinerTopPriorityThreshold;
146
    if (P1ReducesCallerSize || P2ReducesCallerSize) {
147
      // If one reduces the caller size while the other doesn't, then return
148
      // true iff P1 reduces the caller size.
149
      if (P1ReducesCallerSize != P2ReducesCallerSize)
150
        return P1ReducesCallerSize;
151

152
      // If they both reduce the caller size, pick the one with the smaller
153
      // cost.
154
      return P1.Cost < P2.Cost;
155
    }
156

157
    bool P1HasCB = P1.CostBenefit.has_value();
158
    bool P2HasCB = P2.CostBenefit.has_value();
159
    if (P1HasCB || P2HasCB) {
160
      // If one has undergone the cost-benefit analysis while the other hasn't,
161
      // then return true iff P1 has.
162
      if (P1HasCB != P2HasCB)
163
        return P1HasCB;
164

165
      // If they have undergone the cost-benefit analysis, then pick the one
166
      // with a higher benefit-to-cost ratio.
167
      APInt LHS = P1.CostBenefit->getBenefit() * P2.CostBenefit->getCost();
168
      APInt RHS = P2.CostBenefit->getBenefit() * P1.CostBenefit->getCost();
169
      return LHS.ugt(RHS);
170
    }
171

172
    // Remaining call sites are ordered according to their costs.
173
    return P1.Cost < P2.Cost;
174
  }
175

176
private:
177
  int Cost = INT_MAX;
178
  int StaticBonusApplied = 0;
179
  std::optional<CostBenefitPair> CostBenefit;
180
};
181

182
class MLPriority {
183
public:
184
  MLPriority() = default;
185
  MLPriority(const CallBase *CB, FunctionAnalysisManager &FAM,
186
             const InlineParams &Params) {
187
    auto IC = getInlineCostWrapper(const_cast<CallBase &>(*CB), FAM, Params);
188
    if (IC.isVariable())
189
      Cost = IC.getCost();
190
    else
191
      Cost = IC.isNever() ? INT_MAX : INT_MIN;
192
  }
193

194
  static bool isMoreDesirable(const MLPriority &P1, const MLPriority &P2) {
195
    return P1.Cost < P2.Cost;
196
  }
197

198
private:
199
  int Cost = INT_MAX;
200
};
201

202
template <typename PriorityT>
203
class PriorityInlineOrder : public InlineOrder<std::pair<CallBase *, int>> {
204
  using T = std::pair<CallBase *, int>;
205

206
  bool hasLowerPriority(const CallBase *L, const CallBase *R) const {
207
    const auto I1 = Priorities.find(L);
208
    const auto I2 = Priorities.find(R);
209
    assert(I1 != Priorities.end() && I2 != Priorities.end());
210
    return PriorityT::isMoreDesirable(I2->second, I1->second);
211
  }
212

213
  bool updateAndCheckDecreased(const CallBase *CB) {
214
    auto It = Priorities.find(CB);
215
    const auto OldPriority = It->second;
216
    It->second = PriorityT(CB, FAM, Params);
217
    const auto NewPriority = It->second;
218
    return PriorityT::isMoreDesirable(OldPriority, NewPriority);
219
  }
220

221
  // A call site could become less desirable for inlining because of the size
222
  // growth from prior inlining into the callee. This method is used to lazily
223
  // update the desirability of a call site if it's decreasing. It is only
224
  // called on pop(), not every time the desirability changes. When the
225
  // desirability of the front call site decreases, an updated one would be
226
  // pushed right back into the heap. For simplicity, those cases where the
227
  // desirability of a call site increases are ignored here.
228
  void pop_heap_adjust() {
229
    std::pop_heap(Heap.begin(), Heap.end(), isLess);
230
    while (updateAndCheckDecreased(Heap.back())) {
231
      std::push_heap(Heap.begin(), Heap.end(), isLess);
232
      std::pop_heap(Heap.begin(), Heap.end(), isLess);
233
    }
234
  }
235

236
public:
237
  PriorityInlineOrder(FunctionAnalysisManager &FAM, const InlineParams &Params)
238
      : FAM(FAM), Params(Params) {
239
    isLess = [&](const CallBase *L, const CallBase *R) {
240
      return hasLowerPriority(L, R);
241
    };
242
  }
243

244
  size_t size() override { return Heap.size(); }
245

246
  void push(const T &Elt) override {
247
    CallBase *CB = Elt.first;
248
    const int InlineHistoryID = Elt.second;
249

250
    Heap.push_back(CB);
251
    Priorities[CB] = PriorityT(CB, FAM, Params);
252
    std::push_heap(Heap.begin(), Heap.end(), isLess);
253
    InlineHistoryMap[CB] = InlineHistoryID;
254
  }
255

256
  T pop() override {
257
    assert(size() > 0);
258
    pop_heap_adjust();
259

260
    CallBase *CB = Heap.pop_back_val();
261
    T Result = std::make_pair(CB, InlineHistoryMap[CB]);
262
    InlineHistoryMap.erase(CB);
263
    return Result;
264
  }
265

266
  void erase_if(function_ref<bool(T)> Pred) override {
267
    auto PredWrapper = [=](CallBase *CB) -> bool {
268
      return Pred(std::make_pair(CB, InlineHistoryMap[CB]));
269
    };
270
    llvm::erase_if(Heap, PredWrapper);
271
    std::make_heap(Heap.begin(), Heap.end(), isLess);
272
  }
273

274
private:
275
  SmallVector<CallBase *, 16> Heap;
276
  std::function<bool(const CallBase *L, const CallBase *R)> isLess;
277
  DenseMap<CallBase *, int> InlineHistoryMap;
278
  DenseMap<const CallBase *, PriorityT> Priorities;
279
  FunctionAnalysisManager &FAM;
280
  const InlineParams &Params;
281
};
282

283
} // namespace
284

285
AnalysisKey llvm::PluginInlineOrderAnalysis::Key;
286
bool llvm::PluginInlineOrderAnalysis::HasBeenRegistered;
287

288
std::unique_ptr<InlineOrder<std::pair<CallBase *, int>>>
289
llvm::getDefaultInlineOrder(FunctionAnalysisManager &FAM,
290
                            const InlineParams &Params,
291
                            ModuleAnalysisManager &MAM, Module &M) {
292
  switch (UseInlinePriority) {
293
  case InlinePriorityMode::Size:
294
    LLVM_DEBUG(dbgs() << "    Current used priority: Size priority ---- \n");
295
    return std::make_unique<PriorityInlineOrder<SizePriority>>(FAM, Params);
296

297
  case InlinePriorityMode::Cost:
298
    LLVM_DEBUG(dbgs() << "    Current used priority: Cost priority ---- \n");
299
    return std::make_unique<PriorityInlineOrder<CostPriority>>(FAM, Params);
300

301
  case InlinePriorityMode::CostBenefit:
302
    LLVM_DEBUG(
303
        dbgs() << "    Current used priority: cost-benefit priority ---- \n");
304
    return std::make_unique<PriorityInlineOrder<CostBenefitPriority>>(FAM,
305
                                                                      Params);
306
  case InlinePriorityMode::ML:
307
    LLVM_DEBUG(dbgs() << "    Current used priority: ML priority ---- \n");
308
    return std::make_unique<PriorityInlineOrder<MLPriority>>(FAM, Params);
309
  }
310
  return nullptr;
311
}
312

313
std::unique_ptr<InlineOrder<std::pair<CallBase *, int>>>
314
llvm::getInlineOrder(FunctionAnalysisManager &FAM, const InlineParams &Params,
315
                     ModuleAnalysisManager &MAM, Module &M) {
316
  if (llvm::PluginInlineOrderAnalysis::isRegistered()) {
317
    LLVM_DEBUG(dbgs() << "    Current used priority: plugin ---- \n");
318
    return MAM.getResult<PluginInlineOrderAnalysis>(M).Factory(FAM, Params, MAM,
319
                                                               M);
320
  }
321
  return getDefaultInlineOrder(FAM, Params, MAM, M);
322
}
323