llvm/lib/Analysis/InlineOrder.cpp

   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
 287 std::unique_ptr<InlineOrder<std::pair<CallBase *, int>>>
 288 llvm::getDefaultInlineOrder(FunctionAnalysisManager &FAM,
 289                             const InlineParams &Params,
 290                             ModuleAnalysisManager &MAM, Module &M) {
 291   switch (UseInlinePriority) {
 292   case InlinePriorityMode::Size:
 293     LLVM_DEBUG(dbgs() << "    Current used priority: Size priority ---- \n");
 294     return std::make_unique<PriorityInlineOrder<SizePriority>>(FAM, Params);
 295
 296   case InlinePriorityMode::Cost:
 297     LLVM_DEBUG(dbgs() << "    Current used priority: Cost priority ---- \n");
 298     return std::make_unique<PriorityInlineOrder<CostPriority>>(FAM, Params);
 299
 300   case InlinePriorityMode::CostBenefit:
 301     LLVM_DEBUG(
 302         dbgs() << "    Current used priority: cost-benefit priority ---- \n");
 303     return std::make_unique<PriorityInlineOrder<CostBenefitPriority>>(FAM,
 304                                                                       Params);
 305   case InlinePriorityMode::ML:
 306     LLVM_DEBUG(dbgs() << "    Current used priority: ML priority ---- \n");
 307     return std::make_unique<PriorityInlineOrder<MLPriority>>(FAM, Params);
 308   }
 309   return nullptr;
 310 }
 311
 312 std::unique_ptr<InlineOrder<std::pair<CallBase *, int>>>
 313 llvm::getInlineOrder(FunctionAnalysisManager &FAM, const InlineParams &Params,
 314                      ModuleAnalysisManager &MAM, Module &M) {
 315   if (MAM.isPassRegistered<PluginInlineOrderAnalysis>()) {
 316     LLVM_DEBUG(dbgs() << "    Current used priority: plugin ---- \n");
 317     return MAM.getResult<PluginInlineOrderAnalysis>(M).Factory(FAM, Params, MAM,
 318                                                                M);
 319   }
 320   return getDefaultInlineOrder(FAM, Params, MAM, M);
 321 }