1bdd1243dSDimitry Andric //===- InlineOrder.cpp - Inlining order abstraction -*- C++ ---*-----------===// 2bdd1243dSDimitry Andric // 3bdd1243dSDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4bdd1243dSDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 5bdd1243dSDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6bdd1243dSDimitry Andric // 7bdd1243dSDimitry Andric //===----------------------------------------------------------------------===// 8bdd1243dSDimitry Andric 9bdd1243dSDimitry Andric #include "llvm/Analysis/InlineOrder.h" 10bdd1243dSDimitry Andric #include "llvm/Analysis/AssumptionCache.h" 11bdd1243dSDimitry Andric #include "llvm/Analysis/BlockFrequencyInfo.h" 12bdd1243dSDimitry Andric #include "llvm/Analysis/GlobalsModRef.h" 13bdd1243dSDimitry Andric #include "llvm/Analysis/InlineAdvisor.h" 14bdd1243dSDimitry Andric #include "llvm/Analysis/InlineCost.h" 15bdd1243dSDimitry Andric #include "llvm/Analysis/OptimizationRemarkEmitter.h" 16bdd1243dSDimitry Andric #include "llvm/Analysis/ProfileSummaryInfo.h" 17bdd1243dSDimitry Andric #include "llvm/Analysis/TargetLibraryInfo.h" 18bdd1243dSDimitry Andric #include "llvm/Analysis/TargetTransformInfo.h" 19bdd1243dSDimitry Andric #include "llvm/Support/CommandLine.h" 20bdd1243dSDimitry Andric 21bdd1243dSDimitry Andric using namespace llvm; 22bdd1243dSDimitry Andric 23bdd1243dSDimitry Andric #define DEBUG_TYPE "inline-order" 24bdd1243dSDimitry Andric 25bdd1243dSDimitry Andric enum class InlinePriorityMode : int { Size, Cost, CostBenefit, ML }; 26bdd1243dSDimitry Andric 27bdd1243dSDimitry Andric static cl::opt<InlinePriorityMode> UseInlinePriority( 28bdd1243dSDimitry Andric "inline-priority-mode", cl::init(InlinePriorityMode::Size), cl::Hidden, 29bdd1243dSDimitry Andric cl::desc("Choose the priority mode to use in module inline"), 30bdd1243dSDimitry Andric cl::values(clEnumValN(InlinePriorityMode::Size, "size", 31bdd1243dSDimitry Andric "Use callee size priority."), 32bdd1243dSDimitry Andric clEnumValN(InlinePriorityMode::Cost, "cost", 33bdd1243dSDimitry Andric "Use inline cost priority."), 34bdd1243dSDimitry Andric clEnumValN(InlinePriorityMode::CostBenefit, "cost-benefit", 35bdd1243dSDimitry Andric "Use cost-benefit ratio."), 3606c3fb27SDimitry Andric clEnumValN(InlinePriorityMode::ML, "ml", "Use ML."))); 37bdd1243dSDimitry Andric 38bdd1243dSDimitry Andric static cl::opt<int> ModuleInlinerTopPriorityThreshold( 395f757f3fSDimitry Andric "module-inliner-top-priority-threshold", cl::Hidden, cl::init(0), 40bdd1243dSDimitry Andric cl::desc("The cost threshold for call sites that get inlined without the " 41bdd1243dSDimitry Andric "cost-benefit analysis")); 42bdd1243dSDimitry Andric 43bdd1243dSDimitry Andric namespace { 44bdd1243dSDimitry Andric 45bdd1243dSDimitry Andric llvm::InlineCost getInlineCostWrapper(CallBase &CB, 46bdd1243dSDimitry Andric FunctionAnalysisManager &FAM, 47bdd1243dSDimitry Andric const InlineParams &Params) { 48bdd1243dSDimitry Andric Function &Caller = *CB.getCaller(); 49bdd1243dSDimitry Andric ProfileSummaryInfo *PSI = 50bdd1243dSDimitry Andric FAM.getResult<ModuleAnalysisManagerFunctionProxy>(Caller) 51bdd1243dSDimitry Andric .getCachedResult<ProfileSummaryAnalysis>( 52bdd1243dSDimitry Andric *CB.getParent()->getParent()->getParent()); 53bdd1243dSDimitry Andric 54bdd1243dSDimitry Andric auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(Caller); 55bdd1243dSDimitry Andric auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & { 56bdd1243dSDimitry Andric return FAM.getResult<AssumptionAnalysis>(F); 57bdd1243dSDimitry Andric }; 58bdd1243dSDimitry Andric auto GetBFI = [&](Function &F) -> BlockFrequencyInfo & { 59bdd1243dSDimitry Andric return FAM.getResult<BlockFrequencyAnalysis>(F); 60bdd1243dSDimitry Andric }; 61bdd1243dSDimitry Andric auto GetTLI = [&](Function &F) -> const TargetLibraryInfo & { 62bdd1243dSDimitry Andric return FAM.getResult<TargetLibraryAnalysis>(F); 63bdd1243dSDimitry Andric }; 64bdd1243dSDimitry Andric 65bdd1243dSDimitry Andric Function &Callee = *CB.getCalledFunction(); 66bdd1243dSDimitry Andric auto &CalleeTTI = FAM.getResult<TargetIRAnalysis>(Callee); 67bdd1243dSDimitry Andric bool RemarksEnabled = 68bdd1243dSDimitry Andric Callee.getContext().getDiagHandlerPtr()->isMissedOptRemarkEnabled( 69bdd1243dSDimitry Andric DEBUG_TYPE); 70bdd1243dSDimitry Andric return getInlineCost(CB, Params, CalleeTTI, GetAssumptionCache, GetTLI, 71bdd1243dSDimitry Andric GetBFI, PSI, RemarksEnabled ? &ORE : nullptr); 72bdd1243dSDimitry Andric } 73bdd1243dSDimitry Andric 74bdd1243dSDimitry Andric class SizePriority { 75bdd1243dSDimitry Andric public: 76bdd1243dSDimitry Andric SizePriority() = default; 77bdd1243dSDimitry Andric SizePriority(const CallBase *CB, FunctionAnalysisManager &, 78bdd1243dSDimitry Andric const InlineParams &) { 79bdd1243dSDimitry Andric Function *Callee = CB->getCalledFunction(); 80bdd1243dSDimitry Andric Size = Callee->getInstructionCount(); 81bdd1243dSDimitry Andric } 82bdd1243dSDimitry Andric 83bdd1243dSDimitry Andric static bool isMoreDesirable(const SizePriority &P1, const SizePriority &P2) { 84bdd1243dSDimitry Andric return P1.Size < P2.Size; 85bdd1243dSDimitry Andric } 86bdd1243dSDimitry Andric 87bdd1243dSDimitry Andric private: 88bdd1243dSDimitry Andric unsigned Size = UINT_MAX; 89bdd1243dSDimitry Andric }; 90bdd1243dSDimitry Andric 91bdd1243dSDimitry Andric class CostPriority { 92bdd1243dSDimitry Andric public: 93bdd1243dSDimitry Andric CostPriority() = default; 94bdd1243dSDimitry Andric CostPriority(const CallBase *CB, FunctionAnalysisManager &FAM, 95bdd1243dSDimitry Andric const InlineParams &Params) { 96bdd1243dSDimitry Andric auto IC = getInlineCostWrapper(const_cast<CallBase &>(*CB), FAM, Params); 97bdd1243dSDimitry Andric if (IC.isVariable()) 98bdd1243dSDimitry Andric Cost = IC.getCost(); 99bdd1243dSDimitry Andric else 100bdd1243dSDimitry Andric Cost = IC.isNever() ? INT_MAX : INT_MIN; 101bdd1243dSDimitry Andric } 102bdd1243dSDimitry Andric 103bdd1243dSDimitry Andric static bool isMoreDesirable(const CostPriority &P1, const CostPriority &P2) { 104bdd1243dSDimitry Andric return P1.Cost < P2.Cost; 105bdd1243dSDimitry Andric } 106bdd1243dSDimitry Andric 107bdd1243dSDimitry Andric private: 108bdd1243dSDimitry Andric int Cost = INT_MAX; 109bdd1243dSDimitry Andric }; 110bdd1243dSDimitry Andric 111bdd1243dSDimitry Andric class CostBenefitPriority { 112bdd1243dSDimitry Andric public: 113bdd1243dSDimitry Andric CostBenefitPriority() = default; 114bdd1243dSDimitry Andric CostBenefitPriority(const CallBase *CB, FunctionAnalysisManager &FAM, 115bdd1243dSDimitry Andric const InlineParams &Params) { 116bdd1243dSDimitry Andric auto IC = getInlineCostWrapper(const_cast<CallBase &>(*CB), FAM, Params); 117*0fca6ea1SDimitry Andric if (IC.isVariable()) 118bdd1243dSDimitry Andric Cost = IC.getCost(); 119*0fca6ea1SDimitry Andric else 120*0fca6ea1SDimitry Andric Cost = IC.isNever() ? INT_MAX : INT_MIN; 121bdd1243dSDimitry Andric StaticBonusApplied = IC.getStaticBonusApplied(); 122bdd1243dSDimitry Andric CostBenefit = IC.getCostBenefit(); 123bdd1243dSDimitry Andric } 124bdd1243dSDimitry Andric 125bdd1243dSDimitry Andric static bool isMoreDesirable(const CostBenefitPriority &P1, 126bdd1243dSDimitry Andric const CostBenefitPriority &P2) { 127bdd1243dSDimitry Andric // We prioritize call sites in the dictionary order of the following 128bdd1243dSDimitry Andric // priorities: 129bdd1243dSDimitry Andric // 130bdd1243dSDimitry Andric // 1. Those call sites that are expected to reduce the caller size when 131bdd1243dSDimitry Andric // inlined. Within them, we prioritize those call sites with bigger 132bdd1243dSDimitry Andric // reduction. 133bdd1243dSDimitry Andric // 134bdd1243dSDimitry Andric // 2. Those call sites that have gone through the cost-benefit analysis. 135bdd1243dSDimitry Andric // Currently, they are limited to hot call sites. Within them, we 136bdd1243dSDimitry Andric // prioritize those call sites with higher benefit-to-cost ratios. 137bdd1243dSDimitry Andric // 138bdd1243dSDimitry Andric // 3. Remaining call sites are prioritized according to their costs. 139bdd1243dSDimitry Andric 140bdd1243dSDimitry Andric // We add back StaticBonusApplied to determine whether we expect the caller 141bdd1243dSDimitry Andric // to shrink (even if we don't delete the callee). 142bdd1243dSDimitry Andric bool P1ReducesCallerSize = 143bdd1243dSDimitry Andric P1.Cost + P1.StaticBonusApplied < ModuleInlinerTopPriorityThreshold; 144bdd1243dSDimitry Andric bool P2ReducesCallerSize = 145bdd1243dSDimitry Andric P2.Cost + P2.StaticBonusApplied < ModuleInlinerTopPriorityThreshold; 146bdd1243dSDimitry Andric if (P1ReducesCallerSize || P2ReducesCallerSize) { 147bdd1243dSDimitry Andric // If one reduces the caller size while the other doesn't, then return 148bdd1243dSDimitry Andric // true iff P1 reduces the caller size. 149bdd1243dSDimitry Andric if (P1ReducesCallerSize != P2ReducesCallerSize) 150bdd1243dSDimitry Andric return P1ReducesCallerSize; 151bdd1243dSDimitry Andric 152bdd1243dSDimitry Andric // If they both reduce the caller size, pick the one with the smaller 153bdd1243dSDimitry Andric // cost. 154bdd1243dSDimitry Andric return P1.Cost < P2.Cost; 155bdd1243dSDimitry Andric } 156bdd1243dSDimitry Andric 157bdd1243dSDimitry Andric bool P1HasCB = P1.CostBenefit.has_value(); 158bdd1243dSDimitry Andric bool P2HasCB = P2.CostBenefit.has_value(); 159bdd1243dSDimitry Andric if (P1HasCB || P2HasCB) { 160bdd1243dSDimitry Andric // If one has undergone the cost-benefit analysis while the other hasn't, 161bdd1243dSDimitry Andric // then return true iff P1 has. 162bdd1243dSDimitry Andric if (P1HasCB != P2HasCB) 163bdd1243dSDimitry Andric return P1HasCB; 164bdd1243dSDimitry Andric 165bdd1243dSDimitry Andric // If they have undergone the cost-benefit analysis, then pick the one 166bdd1243dSDimitry Andric // with a higher benefit-to-cost ratio. 167bdd1243dSDimitry Andric APInt LHS = P1.CostBenefit->getBenefit() * P2.CostBenefit->getCost(); 168bdd1243dSDimitry Andric APInt RHS = P2.CostBenefit->getBenefit() * P1.CostBenefit->getCost(); 169bdd1243dSDimitry Andric return LHS.ugt(RHS); 170bdd1243dSDimitry Andric } 171bdd1243dSDimitry Andric 172bdd1243dSDimitry Andric // Remaining call sites are ordered according to their costs. 173bdd1243dSDimitry Andric return P1.Cost < P2.Cost; 174bdd1243dSDimitry Andric } 175bdd1243dSDimitry Andric 176bdd1243dSDimitry Andric private: 177bdd1243dSDimitry Andric int Cost = INT_MAX; 178bdd1243dSDimitry Andric int StaticBonusApplied = 0; 179bdd1243dSDimitry Andric std::optional<CostBenefitPair> CostBenefit; 180bdd1243dSDimitry Andric }; 181bdd1243dSDimitry Andric 182bdd1243dSDimitry Andric class MLPriority { 183bdd1243dSDimitry Andric public: 184bdd1243dSDimitry Andric MLPriority() = default; 185bdd1243dSDimitry Andric MLPriority(const CallBase *CB, FunctionAnalysisManager &FAM, 186bdd1243dSDimitry Andric const InlineParams &Params) { 187bdd1243dSDimitry Andric auto IC = getInlineCostWrapper(const_cast<CallBase &>(*CB), FAM, Params); 188bdd1243dSDimitry Andric if (IC.isVariable()) 189bdd1243dSDimitry Andric Cost = IC.getCost(); 190bdd1243dSDimitry Andric else 191bdd1243dSDimitry Andric Cost = IC.isNever() ? INT_MAX : INT_MIN; 192bdd1243dSDimitry Andric } 193bdd1243dSDimitry Andric 194bdd1243dSDimitry Andric static bool isMoreDesirable(const MLPriority &P1, const MLPriority &P2) { 195bdd1243dSDimitry Andric return P1.Cost < P2.Cost; 196bdd1243dSDimitry Andric } 197bdd1243dSDimitry Andric 198bdd1243dSDimitry Andric private: 199bdd1243dSDimitry Andric int Cost = INT_MAX; 200bdd1243dSDimitry Andric }; 201bdd1243dSDimitry Andric 202bdd1243dSDimitry Andric template <typename PriorityT> 203bdd1243dSDimitry Andric class PriorityInlineOrder : public InlineOrder<std::pair<CallBase *, int>> { 204bdd1243dSDimitry Andric using T = std::pair<CallBase *, int>; 205bdd1243dSDimitry Andric 206bdd1243dSDimitry Andric bool hasLowerPriority(const CallBase *L, const CallBase *R) const { 207bdd1243dSDimitry Andric const auto I1 = Priorities.find(L); 208bdd1243dSDimitry Andric const auto I2 = Priorities.find(R); 209bdd1243dSDimitry Andric assert(I1 != Priorities.end() && I2 != Priorities.end()); 210bdd1243dSDimitry Andric return PriorityT::isMoreDesirable(I2->second, I1->second); 211bdd1243dSDimitry Andric } 212bdd1243dSDimitry Andric 213bdd1243dSDimitry Andric bool updateAndCheckDecreased(const CallBase *CB) { 214bdd1243dSDimitry Andric auto It = Priorities.find(CB); 215bdd1243dSDimitry Andric const auto OldPriority = It->second; 216bdd1243dSDimitry Andric It->second = PriorityT(CB, FAM, Params); 217bdd1243dSDimitry Andric const auto NewPriority = It->second; 218bdd1243dSDimitry Andric return PriorityT::isMoreDesirable(OldPriority, NewPriority); 219bdd1243dSDimitry Andric } 220bdd1243dSDimitry Andric 221bdd1243dSDimitry Andric // A call site could become less desirable for inlining because of the size 222bdd1243dSDimitry Andric // growth from prior inlining into the callee. This method is used to lazily 223bdd1243dSDimitry Andric // update the desirability of a call site if it's decreasing. It is only 2245f757f3fSDimitry Andric // called on pop(), not every time the desirability changes. When the 2255f757f3fSDimitry Andric // desirability of the front call site decreases, an updated one would be 2265f757f3fSDimitry Andric // pushed right back into the heap. For simplicity, those cases where the 2275f757f3fSDimitry Andric // desirability of a call site increases are ignored here. 2285f757f3fSDimitry Andric void pop_heap_adjust() { 229bdd1243dSDimitry Andric std::pop_heap(Heap.begin(), Heap.end(), isLess); 2305f757f3fSDimitry Andric while (updateAndCheckDecreased(Heap.back())) { 231bdd1243dSDimitry Andric std::push_heap(Heap.begin(), Heap.end(), isLess); 2325f757f3fSDimitry Andric std::pop_heap(Heap.begin(), Heap.end(), isLess); 233bdd1243dSDimitry Andric } 234bdd1243dSDimitry Andric } 235bdd1243dSDimitry Andric 236bdd1243dSDimitry Andric public: 237bdd1243dSDimitry Andric PriorityInlineOrder(FunctionAnalysisManager &FAM, const InlineParams &Params) 238bdd1243dSDimitry Andric : FAM(FAM), Params(Params) { 239bdd1243dSDimitry Andric isLess = [&](const CallBase *L, const CallBase *R) { 240bdd1243dSDimitry Andric return hasLowerPriority(L, R); 241bdd1243dSDimitry Andric }; 242bdd1243dSDimitry Andric } 243bdd1243dSDimitry Andric 244bdd1243dSDimitry Andric size_t size() override { return Heap.size(); } 245bdd1243dSDimitry Andric 246bdd1243dSDimitry Andric void push(const T &Elt) override { 247bdd1243dSDimitry Andric CallBase *CB = Elt.first; 248bdd1243dSDimitry Andric const int InlineHistoryID = Elt.second; 249bdd1243dSDimitry Andric 250bdd1243dSDimitry Andric Heap.push_back(CB); 251bdd1243dSDimitry Andric Priorities[CB] = PriorityT(CB, FAM, Params); 252bdd1243dSDimitry Andric std::push_heap(Heap.begin(), Heap.end(), isLess); 253bdd1243dSDimitry Andric InlineHistoryMap[CB] = InlineHistoryID; 254bdd1243dSDimitry Andric } 255bdd1243dSDimitry Andric 256bdd1243dSDimitry Andric T pop() override { 257bdd1243dSDimitry Andric assert(size() > 0); 2585f757f3fSDimitry Andric pop_heap_adjust(); 259bdd1243dSDimitry Andric 2605f757f3fSDimitry Andric CallBase *CB = Heap.pop_back_val(); 261bdd1243dSDimitry Andric T Result = std::make_pair(CB, InlineHistoryMap[CB]); 262bdd1243dSDimitry Andric InlineHistoryMap.erase(CB); 263bdd1243dSDimitry Andric return Result; 264bdd1243dSDimitry Andric } 265bdd1243dSDimitry Andric 266bdd1243dSDimitry Andric void erase_if(function_ref<bool(T)> Pred) override { 267bdd1243dSDimitry Andric auto PredWrapper = [=](CallBase *CB) -> bool { 2687a6dacacSDimitry Andric return Pred(std::make_pair(CB, InlineHistoryMap[CB])); 269bdd1243dSDimitry Andric }; 270bdd1243dSDimitry Andric llvm::erase_if(Heap, PredWrapper); 271bdd1243dSDimitry Andric std::make_heap(Heap.begin(), Heap.end(), isLess); 272bdd1243dSDimitry Andric } 273bdd1243dSDimitry Andric 274bdd1243dSDimitry Andric private: 275bdd1243dSDimitry Andric SmallVector<CallBase *, 16> Heap; 276bdd1243dSDimitry Andric std::function<bool(const CallBase *L, const CallBase *R)> isLess; 277bdd1243dSDimitry Andric DenseMap<CallBase *, int> InlineHistoryMap; 278bdd1243dSDimitry Andric DenseMap<const CallBase *, PriorityT> Priorities; 279bdd1243dSDimitry Andric FunctionAnalysisManager &FAM; 280bdd1243dSDimitry Andric const InlineParams &Params; 281bdd1243dSDimitry Andric }; 282bdd1243dSDimitry Andric 283bdd1243dSDimitry Andric } // namespace 284bdd1243dSDimitry Andric 28506c3fb27SDimitry Andric AnalysisKey llvm::PluginInlineOrderAnalysis::Key; 28606c3fb27SDimitry Andric bool llvm::PluginInlineOrderAnalysis::HasBeenRegistered; 28706c3fb27SDimitry Andric 288bdd1243dSDimitry Andric std::unique_ptr<InlineOrder<std::pair<CallBase *, int>>> 28906c3fb27SDimitry Andric llvm::getDefaultInlineOrder(FunctionAnalysisManager &FAM, 29006c3fb27SDimitry Andric const InlineParams &Params, 29106c3fb27SDimitry Andric ModuleAnalysisManager &MAM, Module &M) { 292bdd1243dSDimitry Andric switch (UseInlinePriority) { 293bdd1243dSDimitry Andric case InlinePriorityMode::Size: 294bdd1243dSDimitry Andric LLVM_DEBUG(dbgs() << " Current used priority: Size priority ---- \n"); 295bdd1243dSDimitry Andric return std::make_unique<PriorityInlineOrder<SizePriority>>(FAM, Params); 296bdd1243dSDimitry Andric 297bdd1243dSDimitry Andric case InlinePriorityMode::Cost: 298bdd1243dSDimitry Andric LLVM_DEBUG(dbgs() << " Current used priority: Cost priority ---- \n"); 299bdd1243dSDimitry Andric return std::make_unique<PriorityInlineOrder<CostPriority>>(FAM, Params); 300bdd1243dSDimitry Andric 301bdd1243dSDimitry Andric case InlinePriorityMode::CostBenefit: 302bdd1243dSDimitry Andric LLVM_DEBUG( 303bdd1243dSDimitry Andric dbgs() << " Current used priority: cost-benefit priority ---- \n"); 30406c3fb27SDimitry Andric return std::make_unique<PriorityInlineOrder<CostBenefitPriority>>(FAM, 30506c3fb27SDimitry Andric Params); 306bdd1243dSDimitry Andric case InlinePriorityMode::ML: 30706c3fb27SDimitry Andric LLVM_DEBUG(dbgs() << " Current used priority: ML priority ---- \n"); 308bdd1243dSDimitry Andric return std::make_unique<PriorityInlineOrder<MLPriority>>(FAM, Params); 309bdd1243dSDimitry Andric } 310bdd1243dSDimitry Andric return nullptr; 311bdd1243dSDimitry Andric } 31206c3fb27SDimitry Andric 31306c3fb27SDimitry Andric std::unique_ptr<InlineOrder<std::pair<CallBase *, int>>> 31406c3fb27SDimitry Andric llvm::getInlineOrder(FunctionAnalysisManager &FAM, const InlineParams &Params, 31506c3fb27SDimitry Andric ModuleAnalysisManager &MAM, Module &M) { 31606c3fb27SDimitry Andric if (llvm::PluginInlineOrderAnalysis::isRegistered()) { 31706c3fb27SDimitry Andric LLVM_DEBUG(dbgs() << " Current used priority: plugin ---- \n"); 31806c3fb27SDimitry Andric return MAM.getResult<PluginInlineOrderAnalysis>(M).Factory(FAM, Params, MAM, 31906c3fb27SDimitry Andric M); 32006c3fb27SDimitry Andric } 32106c3fb27SDimitry Andric return getDefaultInlineOrder(FAM, Params, MAM, M); 32206c3fb27SDimitry Andric } 323