vendor/llvm-project/llvmorg-16-init-18548-gb0daacf58f41

1 files changed, 305 insertions, 0 deletions

diff --git a/llvm/lib/Analysis/InlineOrder.cpp b/llvm/lib/Analysis/InlineOrder.cpp
new file mode 100644
index 000000000000..8d0e49936901
--- /dev/null
+++ b/llvm/lib/Analysis/InlineOrder.cpp
@@ -0,0 +1,305 @@
+//===- InlineOrder.cpp - Inlining order abstraction -*- C++ ---*-----------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/InlineOrder.h"
+#include "llvm/Analysis/AssumptionCache.h"
+#include "llvm/Analysis/BlockFrequencyInfo.h"
+#include "llvm/Analysis/GlobalsModRef.h"
+#include "llvm/Analysis/InlineAdvisor.h"
+#include "llvm/Analysis/InlineCost.h"
+#include "llvm/Analysis/OptimizationRemarkEmitter.h"
+#include "llvm/Analysis/ProfileSummaryInfo.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
+#include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/Support/CommandLine.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "inline-order"
+
+enum class InlinePriorityMode : int { Size, Cost, CostBenefit, ML };
+
+static cl::opt<InlinePriorityMode> UseInlinePriority(
+    "inline-priority-mode", cl::init(InlinePriorityMode::Size), cl::Hidden,
+    cl::desc("Choose the priority mode to use in module inline"),
+    cl::values(clEnumValN(InlinePriorityMode::Size, "size",
+                          "Use callee size priority."),
+               clEnumValN(InlinePriorityMode::Cost, "cost",
+                          "Use inline cost priority."),
+               clEnumValN(InlinePriorityMode::CostBenefit, "cost-benefit",
+                          "Use cost-benefit ratio."),
+               clEnumValN(InlinePriorityMode::ML, "ml",
+                          "Use ML.")));
+
+static cl::opt<int> ModuleInlinerTopPriorityThreshold(
+    "moudle-inliner-top-priority-threshold", cl::Hidden, cl::init(0),
+    cl::desc("The cost threshold for call sites that get inlined without the "
+             "cost-benefit analysis"));
+
+namespace {
+
+llvm::InlineCost getInlineCostWrapper(CallBase &CB,
+                                      FunctionAnalysisManager &FAM,
+                                      const InlineParams &Params) {
+  Function &Caller = *CB.getCaller();
+  ProfileSummaryInfo *PSI =
+      FAM.getResult<ModuleAnalysisManagerFunctionProxy>(Caller)
+          .getCachedResult<ProfileSummaryAnalysis>(
+              *CB.getParent()->getParent()->getParent());
+
+  auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(Caller);
+  auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & {
+    return FAM.getResult<AssumptionAnalysis>(F);
+  };
+  auto GetBFI = [&](Function &F) -> BlockFrequencyInfo & {
+    return FAM.getResult<BlockFrequencyAnalysis>(F);
+  };
+  auto GetTLI = [&](Function &F) -> const TargetLibraryInfo & {
+    return FAM.getResult<TargetLibraryAnalysis>(F);
+  };
+
+  Function &Callee = *CB.getCalledFunction();
+  auto &CalleeTTI = FAM.getResult<TargetIRAnalysis>(Callee);
+  bool RemarksEnabled =
+      Callee.getContext().getDiagHandlerPtr()->isMissedOptRemarkEnabled(
+          DEBUG_TYPE);
+  return getInlineCost(CB, Params, CalleeTTI, GetAssumptionCache, GetTLI,
+                       GetBFI, PSI, RemarksEnabled ? &ORE : nullptr);
+}
+
+class SizePriority {
+public:
+  SizePriority() = default;
+  SizePriority(const CallBase *CB, FunctionAnalysisManager &,
+               const InlineParams &) {
+    Function *Callee = CB->getCalledFunction();
+    Size = Callee->getInstructionCount();
+  }
+
+  static bool isMoreDesirable(const SizePriority &P1, const SizePriority &P2) {
+    return P1.Size < P2.Size;
+  }
+
+private:
+  unsigned Size = UINT_MAX;
+};
+
+class CostPriority {
+public:
+  CostPriority() = default;
+  CostPriority(const CallBase *CB, FunctionAnalysisManager &FAM,
+               const InlineParams &Params) {
+    auto IC = getInlineCostWrapper(const_cast<CallBase &>(*CB), FAM, Params);
+    if (IC.isVariable())
+      Cost = IC.getCost();
+    else
+      Cost = IC.isNever() ? INT_MAX : INT_MIN;
+  }
+
+  static bool isMoreDesirable(const CostPriority &P1, const CostPriority &P2) {
+    return P1.Cost < P2.Cost;
+  }
+
+private:
+  int Cost = INT_MAX;
+};
+
+class CostBenefitPriority {
+public:
+  CostBenefitPriority() = default;
+  CostBenefitPriority(const CallBase *CB, FunctionAnalysisManager &FAM,
+                      const InlineParams &Params) {
+    auto IC = getInlineCostWrapper(const_cast<CallBase &>(*CB), FAM, Params);
+    Cost = IC.getCost();
+    StaticBonusApplied = IC.getStaticBonusApplied();
+    CostBenefit = IC.getCostBenefit();
+  }
+
+  static bool isMoreDesirable(const CostBenefitPriority &P1,
+                              const CostBenefitPriority &P2) {
+    // We prioritize call sites in the dictionary order of the following
+    // priorities:
+    //
+    // 1. Those call sites that are expected to reduce the caller size when
+    //    inlined.  Within them, we prioritize those call sites with bigger
+    //    reduction.
+    //
+    // 2. Those call sites that have gone through the cost-benefit analysis.
+    //    Currently, they are limited to hot call sites.  Within them, we
+    //    prioritize those call sites with higher benefit-to-cost ratios.
+    //
+    // 3. Remaining call sites are prioritized according to their costs.
+
+    // We add back StaticBonusApplied to determine whether we expect the caller
+    // to shrink (even if we don't delete the callee).
+    bool P1ReducesCallerSize =
+        P1.Cost + P1.StaticBonusApplied < ModuleInlinerTopPriorityThreshold;
+    bool P2ReducesCallerSize =
+        P2.Cost + P2.StaticBonusApplied < ModuleInlinerTopPriorityThreshold;
+    if (P1ReducesCallerSize || P2ReducesCallerSize) {
+      // If one reduces the caller size while the other doesn't, then return
+      // true iff P1 reduces the caller size.
+      if (P1ReducesCallerSize != P2ReducesCallerSize)
+        return P1ReducesCallerSize;
+
+      // If they both reduce the caller size, pick the one with the smaller
+      // cost.
+      return P1.Cost < P2.Cost;
+    }
+
+    bool P1HasCB = P1.CostBenefit.has_value();
+    bool P2HasCB = P2.CostBenefit.has_value();
+    if (P1HasCB || P2HasCB) {
+      // If one has undergone the cost-benefit analysis while the other hasn't,
+      // then return true iff P1 has.
+      if (P1HasCB != P2HasCB)
+        return P1HasCB;
+
+      // If they have undergone the cost-benefit analysis, then pick the one
+      // with a higher benefit-to-cost ratio.
+      APInt LHS = P1.CostBenefit->getBenefit() * P2.CostBenefit->getCost();
+      APInt RHS = P2.CostBenefit->getBenefit() * P1.CostBenefit->getCost();
+      return LHS.ugt(RHS);
+    }
+
+    // Remaining call sites are ordered according to their costs.
+    return P1.Cost < P2.Cost;
+  }
+
+private:
+  int Cost = INT_MAX;
+  int StaticBonusApplied = 0;
+  std::optional<CostBenefitPair> CostBenefit;
+};
+
+class MLPriority {
+public:
+  MLPriority() = default;
+  MLPriority(const CallBase *CB, FunctionAnalysisManager &FAM,
+             const InlineParams &Params) {
+    auto IC = getInlineCostWrapper(const_cast<CallBase &>(*CB), FAM, Params);
+    if (IC.isVariable())
+      Cost = IC.getCost();
+    else
+      Cost = IC.isNever() ? INT_MAX : INT_MIN;
+  }
+
+  static bool isMoreDesirable(const MLPriority &P1, const MLPriority &P2) {
+    return P1.Cost < P2.Cost;
+  }
+
+private:
+  int Cost = INT_MAX;
+};
+
+template <typename PriorityT>
+class PriorityInlineOrder : public InlineOrder<std::pair<CallBase *, int>> {
+  using T = std::pair<CallBase *, int>;
+
+  bool hasLowerPriority(const CallBase *L, const CallBase *R) const {
+    const auto I1 = Priorities.find(L);
+    const auto I2 = Priorities.find(R);
+    assert(I1 != Priorities.end() && I2 != Priorities.end());
+    return PriorityT::isMoreDesirable(I2->second, I1->second);
+  }
+
+  bool updateAndCheckDecreased(const CallBase *CB) {
+    auto It = Priorities.find(CB);
+    const auto OldPriority = It->second;
+    It->second = PriorityT(CB, FAM, Params);
+    const auto NewPriority = It->second;
+    return PriorityT::isMoreDesirable(OldPriority, NewPriority);
+  }
+
+  // A call site could become less desirable for inlining because of the size
+  // growth from prior inlining into the callee. This method is used to lazily
+  // update the desirability of a call site if it's decreasing. It is only
+  // called on pop() or front(), not every time the desirability changes. When
+  // the desirability of the front call site decreases, an updated one would be
+  // pushed right back into the heap. For simplicity, those cases where
+  // the desirability of a call site increases are ignored here.
+  void adjust() {
+    while (updateAndCheckDecreased(Heap.front())) {
+      std::pop_heap(Heap.begin(), Heap.end(), isLess);
+      std::push_heap(Heap.begin(), Heap.end(), isLess);
+    }
+  }
+
+public:
+  PriorityInlineOrder(FunctionAnalysisManager &FAM, const InlineParams &Params)
+      : FAM(FAM), Params(Params) {
+    isLess = [&](const CallBase *L, const CallBase *R) {
+      return hasLowerPriority(L, R);
+    };
+  }
+
+  size_t size() override { return Heap.size(); }
+
+  void push(const T &Elt) override {
+    CallBase *CB = Elt.first;
+    const int InlineHistoryID = Elt.second;
+
+    Heap.push_back(CB);
+    Priorities[CB] = PriorityT(CB, FAM, Params);
+    std::push_heap(Heap.begin(), Heap.end(), isLess);
+    InlineHistoryMap[CB] = InlineHistoryID;
+  }
+
+  T pop() override {
+    assert(size() > 0);
+    adjust();
+
+    CallBase *CB = Heap.front();
+    T Result = std::make_pair(CB, InlineHistoryMap[CB]);
+    InlineHistoryMap.erase(CB);
+    std::pop_heap(Heap.begin(), Heap.end(), isLess);
+    Heap.pop_back();
+    return Result;
+  }
+
+  void erase_if(function_ref<bool(T)> Pred) override {
+    auto PredWrapper = [=](CallBase *CB) -> bool {
+      return Pred(std::make_pair(CB, 0));
+    };
+    llvm::erase_if(Heap, PredWrapper);
+    std::make_heap(Heap.begin(), Heap.end(), isLess);
+  }
+
+private:
+  SmallVector<CallBase *, 16> Heap;
+  std::function<bool(const CallBase *L, const CallBase *R)> isLess;
+  DenseMap<CallBase *, int> InlineHistoryMap;
+  DenseMap<const CallBase *, PriorityT> Priorities;
+  FunctionAnalysisManager &FAM;
+  const InlineParams &Params;
+};
+
+} // namespace
+
+std::unique_ptr<InlineOrder<std::pair<CallBase *, int>>>
+llvm::getInlineOrder(FunctionAnalysisManager &FAM, const InlineParams &Params) {
+  switch (UseInlinePriority) {
+  case InlinePriorityMode::Size:
+    LLVM_DEBUG(dbgs() << "    Current used priority: Size priority ---- \n");
+    return std::make_unique<PriorityInlineOrder<SizePriority>>(FAM, Params);
+
+  case InlinePriorityMode::Cost:
+    LLVM_DEBUG(dbgs() << "    Current used priority: Cost priority ---- \n");
+    return std::make_unique<PriorityInlineOrder<CostPriority>>(FAM, Params);
+
+  case InlinePriorityMode::CostBenefit:
+    LLVM_DEBUG(
+        dbgs() << "    Current used priority: cost-benefit priority ---- \n");
+    return std::make_unique<PriorityInlineOrder<CostBenefitPriority>>(FAM, Params);
+  case InlinePriorityMode::ML:
+    LLVM_DEBUG(
+        dbgs() << "    Current used priority: ML priority ---- \n");
+    return std::make_unique<PriorityInlineOrder<MLPriority>>(FAM, Params);
+  }
+  return nullptr;
+}