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     Cost = IC.getCost();
 118     StaticBonusApplied = IC.getStaticBonusApplied();
 119     CostBenefit = IC.getCostBenefit();
 120   }
 121
 122   static bool isMoreDesirable(const CostBenefitPriority &P1,
 123                               const CostBenefitPriority &P2) {
 124     // We prioritize call sites in the dictionary order of the following
 125     // priorities:
 126     //
 127     // 1. Those call sites that are expected to reduce the caller size when
 128     //    inlined.  Within them, we prioritize those call sites with bigger
 129     //    reduction.
 130     //
 131     // 2. Those call sites that have gone through the cost-benefit analysis.
 132     //    Currently, they are limited to hot call sites.  Within them, we
 133     //    prioritize those call sites with higher benefit-to-cost ratios.
 134     //
 135     // 3. Remaining call sites are prioritized according to their costs.
 136
 137     // We add back StaticBonusApplied to determine whether we expect the caller
 138     // to shrink (even if we don't delete the callee).
 139     bool P1ReducesCallerSize =
 140         P1.Cost + P1.StaticBonusApplied < ModuleInlinerTopPriorityThreshold;
 141     bool P2ReducesCallerSize =
 142         P2.Cost + P2.StaticBonusApplied < ModuleInlinerTopPriorityThreshold;
 143     if (P1ReducesCallerSize || P2ReducesCallerSize) {
 144       // If one reduces the caller size while the other doesn't, then return
 145       // true iff P1 reduces the caller size.
 146       if (P1ReducesCallerSize != P2ReducesCallerSize)
 147         return P1ReducesCallerSize;
 148
 149       // If they both reduce the caller size, pick the one with the smaller
 150       // cost.
 151       return P1.Cost < P2.Cost;
 152     }
 153
 154     bool P1HasCB = P1.CostBenefit.has_value();
 155     bool P2HasCB = P2.CostBenefit.has_value();
 156     if (P1HasCB || P2HasCB) {
 157       // If one has undergone the cost-benefit analysis while the other hasn't,
 158       // then return true iff P1 has.
 159       if (P1HasCB != P2HasCB)
 160         return P1HasCB;
 161
 162       // If they have undergone the cost-benefit analysis, then pick the one
 163       // with a higher benefit-to-cost ratio.
 164       APInt LHS = P1.CostBenefit->getBenefit() * P2.CostBenefit->getCost();
 165       APInt RHS = P2.CostBenefit->getBenefit() * P1.CostBenefit->getCost();
 166       return LHS.ugt(RHS);
 167     }
 168
 169     // Remaining call sites are ordered according to their costs.
 170     return P1.Cost < P2.Cost;
 171   }
 172
 173 private:
 174   int Cost = INT_MAX;
 175   int StaticBonusApplied = 0;
 176   std::optional<CostBenefitPair> CostBenefit;
 177 };
 178
 179 class MLPriority {
 180 public:
 181   MLPriority() = default;
 182   MLPriority(const CallBase *CB, FunctionAnalysisManager &FAM,
 183              const InlineParams &Params) {
 184     auto IC = getInlineCostWrapper(const_cast<CallBase &>(*CB), FAM, Params);
 185     if (IC.isVariable())
 186       Cost = IC.getCost();
 187     else
 188       Cost = IC.isNever() ? INT_MAX : INT_MIN;
 189   }
 190
 191   static bool isMoreDesirable(const MLPriority &P1, const MLPriority &P2) {
 192     return P1.Cost < P2.Cost;
 193   }
 194
 195 private:
 196   int Cost = INT_MAX;
 197 };
 198
 199 template <typename PriorityT>
 200 class PriorityInlineOrder : public InlineOrder<std::pair<CallBase *, int>> {
 201   using T = std::pair<CallBase *, int>;
 202
 203   bool hasLowerPriority(const CallBase *L, const CallBase *R) const {
 204     const auto I1 = Priorities.find(L);
 205     const auto I2 = Priorities.find(R);
 206     assert(I1 != Priorities.end() && I2 != Priorities.end());
 207     return PriorityT::isMoreDesirable(I2->second, I1->second);
 208   }
 209
 210   bool updateAndCheckDecreased(const CallBase *CB) {
 211     auto It = Priorities.find(CB);
 212     const auto OldPriority = It->second;
 213     It->second = PriorityT(CB, FAM, Params);
 214     const auto NewPriority = It->second;
 215     return PriorityT::isMoreDesirable(OldPriority, NewPriority);
 216   }
 217
 218   // A call site could become less desirable for inlining because of the size
 219   // growth from prior inlining into the callee. This method is used to lazily
 220   // update the desirability of a call site if it's decreasing. It is only
 221   // called on pop(), not every time the desirability changes. When the
 222   // desirability of the front call site decreases, an updated one would be
 223   // pushed right back into the heap. For simplicity, those cases where the
 224   // desirability of a call site increases are ignored here.
 225   void pop_heap_adjust() {
 226     std::pop_heap(Heap.begin(), Heap.end(), isLess);
 227     while (updateAndCheckDecreased(Heap.back())) {
 228       std::push_heap(Heap.begin(), Heap.end(), isLess);
 229       std::pop_heap(Heap.begin(), Heap.end(), isLess);
 230     }
 231   }
 232
 233 public:
 234   PriorityInlineOrder(FunctionAnalysisManager &FAM, const InlineParams &Params)
 235       : FAM(FAM), Params(Params) {
 236     isLess = [&](const CallBase *L, const CallBase *R) {
 237       return hasLowerPriority(L, R);
 238     };
 239   }
 240
 241   size_t size() override { return Heap.size(); }
 242
 243   void push(const T &Elt) override {
 244     CallBase *CB = Elt.first;
 245     const int InlineHistoryID = Elt.second;
 246
 247     Heap.push_back(CB);
 248     Priorities[CB] = PriorityT(CB, FAM, Params);
 249     std::push_heap(Heap.begin(), Heap.end(), isLess);
 250     InlineHistoryMap[CB] = InlineHistoryID;
 251   }
 252
 253   T pop() override {
 254     assert(size() > 0);
 255     pop_heap_adjust();
 256
 257     CallBase *CB = Heap.pop_back_val();
 258     T Result = std::make_pair(CB, InlineHistoryMap[CB]);
 259     InlineHistoryMap.erase(CB);
 260     return Result;
 261   }
 262
 263   void erase_if(function_ref<bool(T)> Pred) override {
 264     auto PredWrapper = [=](CallBase *CB) -> bool {
 265       return Pred(std::make_pair(CB, InlineHistoryMap[CB]));
 266     };
 267     llvm::erase_if(Heap, PredWrapper);
 268     std::make_heap(Heap.begin(), Heap.end(), isLess);
 269   }
 270
 271 private:
 272   SmallVector<CallBase *, 16> Heap;
 273   std::function<bool(const CallBase *L, const CallBase *R)> isLess;
 274   DenseMap<CallBase *, int> InlineHistoryMap;
 275   DenseMap<const CallBase *, PriorityT> Priorities;
 276   FunctionAnalysisManager &FAM;
 277   const InlineParams &Params;
 278 };
 279
 280 } // namespace
 281
 282 AnalysisKey llvm::PluginInlineOrderAnalysis::Key;
 283 bool llvm::PluginInlineOrderAnalysis::HasBeenRegistered;
 284
 285 std::unique_ptr<InlineOrder<std::pair<CallBase *, int>>>
 286 llvm::getDefaultInlineOrder(FunctionAnalysisManager &FAM,
 287                             const InlineParams &Params,
 288                             ModuleAnalysisManager &MAM, Module &M) {
 289   switch (UseInlinePriority) {
 290   case InlinePriorityMode::Size:
 291     LLVM_DEBUG(dbgs() << "    Current used priority: Size priority ---- \n");
 292     return std::make_unique<PriorityInlineOrder<SizePriority>>(FAM, Params);
 293
 294   case InlinePriorityMode::Cost:
 295     LLVM_DEBUG(dbgs() << "    Current used priority: Cost priority ---- \n");
 296     return std::make_unique<PriorityInlineOrder<CostPriority>>(FAM, Params);
 297
 298   case InlinePriorityMode::CostBenefit:
 299     LLVM_DEBUG(
 300         dbgs() << "    Current used priority: cost-benefit priority ---- \n");
 301     return std::make_unique<PriorityInlineOrder<CostBenefitPriority>>(FAM,
 302                                                                       Params);
 303   case InlinePriorityMode::ML:
 304     LLVM_DEBUG(dbgs() << "    Current used priority: ML priority ---- \n");
 305     return std::make_unique<PriorityInlineOrder<MLPriority>>(FAM, Params);
 306   }
 307   return nullptr;
 308 }
 309
 310 std::unique_ptr<InlineOrder<std::pair<CallBase *, int>>>
 311 llvm::getInlineOrder(FunctionAnalysisManager &FAM, const InlineParams &Params,
 312                      ModuleAnalysisManager &MAM, Module &M) {
 313   if (llvm::PluginInlineOrderAnalysis::isRegistered()) {
 314     LLVM_DEBUG(dbgs() << "    Current used priority: plugin ---- \n");
 315     return MAM.getResult<PluginInlineOrderAnalysis>(M).Factory(FAM, Params, MAM,
 316                                                                M);
 317   }
 318   return getDefaultInlineOrder(FAM, Params, MAM, M);
 319 }