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", 37 "Use ML."))); 38 39 static cl::opt<int> ModuleInlinerTopPriorityThreshold( 40 "moudle-inliner-top-priority-threshold", cl::Hidden, cl::init(0), 41 cl::desc("The cost threshold for call sites that get inlined without the " 42 "cost-benefit analysis")); 43 44 namespace { 45 46 llvm::InlineCost getInlineCostWrapper(CallBase &CB, 47 FunctionAnalysisManager &FAM, 48 const InlineParams &Params) { 49 Function &Caller = *CB.getCaller(); 50 ProfileSummaryInfo *PSI = 51 FAM.getResult<ModuleAnalysisManagerFunctionProxy>(Caller) 52 .getCachedResult<ProfileSummaryAnalysis>( 53 *CB.getParent()->getParent()->getParent()); 54 55 auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(Caller); 56 auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & { 57 return FAM.getResult<AssumptionAnalysis>(F); 58 }; 59 auto GetBFI = [&](Function &F) -> BlockFrequencyInfo & { 60 return FAM.getResult<BlockFrequencyAnalysis>(F); 61 }; 62 auto GetTLI = [&](Function &F) -> const TargetLibraryInfo & { 63 return FAM.getResult<TargetLibraryAnalysis>(F); 64 }; 65 66 Function &Callee = *CB.getCalledFunction(); 67 auto &CalleeTTI = FAM.getResult<TargetIRAnalysis>(Callee); 68 bool RemarksEnabled = 69 Callee.getContext().getDiagHandlerPtr()->isMissedOptRemarkEnabled( 70 DEBUG_TYPE); 71 return getInlineCost(CB, Params, CalleeTTI, GetAssumptionCache, GetTLI, 72 GetBFI, PSI, RemarksEnabled ? &ORE : nullptr); 73 } 74 75 class SizePriority { 76 public: 77 SizePriority() = default; 78 SizePriority(const CallBase *CB, FunctionAnalysisManager &, 79 const InlineParams &) { 80 Function *Callee = CB->getCalledFunction(); 81 Size = Callee->getInstructionCount(); 82 } 83 84 static bool isMoreDesirable(const SizePriority &P1, const SizePriority &P2) { 85 return P1.Size < P2.Size; 86 } 87 88 private: 89 unsigned Size = UINT_MAX; 90 }; 91 92 class CostPriority { 93 public: 94 CostPriority() = default; 95 CostPriority(const CallBase *CB, FunctionAnalysisManager &FAM, 96 const InlineParams &Params) { 97 auto IC = getInlineCostWrapper(const_cast<CallBase &>(*CB), FAM, Params); 98 if (IC.isVariable()) 99 Cost = IC.getCost(); 100 else 101 Cost = IC.isNever() ? INT_MAX : INT_MIN; 102 } 103 104 static bool isMoreDesirable(const CostPriority &P1, const CostPriority &P2) { 105 return P1.Cost < P2.Cost; 106 } 107 108 private: 109 int Cost = INT_MAX; 110 }; 111 112 class CostBenefitPriority { 113 public: 114 CostBenefitPriority() = default; 115 CostBenefitPriority(const CallBase *CB, FunctionAnalysisManager &FAM, 116 const InlineParams &Params) { 117 auto IC = getInlineCostWrapper(const_cast<CallBase &>(*CB), FAM, Params); 118 Cost = IC.getCost(); 119 StaticBonusApplied = IC.getStaticBonusApplied(); 120 CostBenefit = IC.getCostBenefit(); 121 } 122 123 static bool isMoreDesirable(const CostBenefitPriority &P1, 124 const CostBenefitPriority &P2) { 125 // We prioritize call sites in the dictionary order of the following 126 // priorities: 127 // 128 // 1. Those call sites that are expected to reduce the caller size when 129 // inlined. Within them, we prioritize those call sites with bigger 130 // reduction. 131 // 132 // 2. Those call sites that have gone through the cost-benefit analysis. 133 // Currently, they are limited to hot call sites. Within them, we 134 // prioritize those call sites with higher benefit-to-cost ratios. 135 // 136 // 3. Remaining call sites are prioritized according to their costs. 137 138 // We add back StaticBonusApplied to determine whether we expect the caller 139 // to shrink (even if we don't delete the callee). 140 bool P1ReducesCallerSize = 141 P1.Cost + P1.StaticBonusApplied < ModuleInlinerTopPriorityThreshold; 142 bool P2ReducesCallerSize = 143 P2.Cost + P2.StaticBonusApplied < ModuleInlinerTopPriorityThreshold; 144 if (P1ReducesCallerSize || P2ReducesCallerSize) { 145 // If one reduces the caller size while the other doesn't, then return 146 // true iff P1 reduces the caller size. 147 if (P1ReducesCallerSize != P2ReducesCallerSize) 148 return P1ReducesCallerSize; 149 150 // If they both reduce the caller size, pick the one with the smaller 151 // cost. 152 return P1.Cost < P2.Cost; 153 } 154 155 bool P1HasCB = P1.CostBenefit.has_value(); 156 bool P2HasCB = P2.CostBenefit.has_value(); 157 if (P1HasCB || P2HasCB) { 158 // If one has undergone the cost-benefit analysis while the other hasn't, 159 // then return true iff P1 has. 160 if (P1HasCB != P2HasCB) 161 return P1HasCB; 162 163 // If they have undergone the cost-benefit analysis, then pick the one 164 // with a higher benefit-to-cost ratio. 165 APInt LHS = P1.CostBenefit->getBenefit() * P2.CostBenefit->getCost(); 166 APInt RHS = P2.CostBenefit->getBenefit() * P1.CostBenefit->getCost(); 167 return LHS.ugt(RHS); 168 } 169 170 // Remaining call sites are ordered according to their costs. 171 return P1.Cost < P2.Cost; 172 } 173 174 private: 175 int Cost = INT_MAX; 176 int StaticBonusApplied = 0; 177 std::optional<CostBenefitPair> CostBenefit; 178 }; 179 180 class MLPriority { 181 public: 182 MLPriority() = default; 183 MLPriority(const CallBase *CB, FunctionAnalysisManager &FAM, 184 const InlineParams &Params) { 185 auto IC = getInlineCostWrapper(const_cast<CallBase &>(*CB), FAM, Params); 186 if (IC.isVariable()) 187 Cost = IC.getCost(); 188 else 189 Cost = IC.isNever() ? INT_MAX : INT_MIN; 190 } 191 192 static bool isMoreDesirable(const MLPriority &P1, const MLPriority &P2) { 193 return P1.Cost < P2.Cost; 194 } 195 196 private: 197 int Cost = INT_MAX; 198 }; 199 200 template <typename PriorityT> 201 class PriorityInlineOrder : public InlineOrder<std::pair<CallBase *, int>> { 202 using T = std::pair<CallBase *, int>; 203 204 bool hasLowerPriority(const CallBase *L, const CallBase *R) const { 205 const auto I1 = Priorities.find(L); 206 const auto I2 = Priorities.find(R); 207 assert(I1 != Priorities.end() && I2 != Priorities.end()); 208 return PriorityT::isMoreDesirable(I2->second, I1->second); 209 } 210 211 bool updateAndCheckDecreased(const CallBase *CB) { 212 auto It = Priorities.find(CB); 213 const auto OldPriority = It->second; 214 It->second = PriorityT(CB, FAM, Params); 215 const auto NewPriority = It->second; 216 return PriorityT::isMoreDesirable(OldPriority, NewPriority); 217 } 218 219 // A call site could become less desirable for inlining because of the size 220 // growth from prior inlining into the callee. This method is used to lazily 221 // update the desirability of a call site if it's decreasing. It is only 222 // called on pop() or front(), not every time the desirability changes. When 223 // the desirability of the front call site decreases, an updated one would be 224 // pushed right back into the heap. For simplicity, those cases where 225 // the desirability of a call site increases are ignored here. 226 void adjust() { 227 while (updateAndCheckDecreased(Heap.front())) { 228 std::pop_heap(Heap.begin(), Heap.end(), isLess); 229 std::push_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 adjust(); 256 257 CallBase *CB = Heap.front(); 258 T Result = std::make_pair(CB, InlineHistoryMap[CB]); 259 InlineHistoryMap.erase(CB); 260 std::pop_heap(Heap.begin(), Heap.end(), isLess); 261 Heap.pop_back(); 262 return Result; 263 } 264 265 void erase_if(function_ref<bool(T)> Pred) override { 266 auto PredWrapper = [=](CallBase *CB) -> bool { 267 return Pred(std::make_pair(CB, 0)); 268 }; 269 llvm::erase_if(Heap, PredWrapper); 270 std::make_heap(Heap.begin(), Heap.end(), isLess); 271 } 272 273 private: 274 SmallVector<CallBase *, 16> Heap; 275 std::function<bool(const CallBase *L, const CallBase *R)> isLess; 276 DenseMap<CallBase *, int> InlineHistoryMap; 277 DenseMap<const CallBase *, PriorityT> Priorities; 278 FunctionAnalysisManager &FAM; 279 const InlineParams &Params; 280 }; 281 282 } // namespace 283 284 std::unique_ptr<InlineOrder<std::pair<CallBase *, int>>> 285 llvm::getInlineOrder(FunctionAnalysisManager &FAM, const InlineParams &Params) { 286 switch (UseInlinePriority) { 287 case InlinePriorityMode::Size: 288 LLVM_DEBUG(dbgs() << " Current used priority: Size priority ---- \n"); 289 return std::make_unique<PriorityInlineOrder<SizePriority>>(FAM, Params); 290 291 case InlinePriorityMode::Cost: 292 LLVM_DEBUG(dbgs() << " Current used priority: Cost priority ---- \n"); 293 return std::make_unique<PriorityInlineOrder<CostPriority>>(FAM, Params); 294 295 case InlinePriorityMode::CostBenefit: 296 LLVM_DEBUG( 297 dbgs() << " Current used priority: cost-benefit priority ---- \n"); 298 return std::make_unique<PriorityInlineOrder<CostBenefitPriority>>(FAM, Params); 299 case InlinePriorityMode::ML: 300 LLVM_DEBUG( 301 dbgs() << " Current used priority: ML priority ---- \n"); 302 return std::make_unique<PriorityInlineOrder<MLPriority>>(FAM, Params); 303 } 304 return nullptr; 305 } 306