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 20 using namespace llvm; 21 22 #define DEBUG_TYPE "inline-order" 23 24 namespace { 25 26 class InlinePriority { 27 public: 28 virtual ~InlinePriority() = default; 29 virtual bool hasLowerPriority(const CallBase *L, const CallBase *R) const = 0; 30 virtual void update(const CallBase *CB) = 0; 31 virtual bool updateAndCheckDecreased(const CallBase *CB) = 0; 32 }; 33 34 class SizePriority : public InlinePriority { 35 using PriorityT = unsigned; 36 DenseMap<const CallBase *, PriorityT> Priorities; 37 38 PriorityT evaluate(const CallBase *CB) { 39 Function *Callee = CB->getCalledFunction(); 40 return Callee->getInstructionCount(); 41 } 42 43 bool isMoreDesirable(const PriorityT &P1, const PriorityT &P2) const { 44 return P1 < P2; 45 } 46 47 public: 48 bool hasLowerPriority(const CallBase *L, const CallBase *R) const override { 49 const auto I1 = Priorities.find(L); 50 const auto I2 = Priorities.find(R); 51 assert(I1 != Priorities.end() && I2 != Priorities.end()); 52 return isMoreDesirable(I2->second, I1->second); 53 } 54 55 // Update the priority associated with CB. 56 void update(const CallBase *CB) override { Priorities[CB] = evaluate(CB); }; 57 58 bool updateAndCheckDecreased(const CallBase *CB) override { 59 auto It = Priorities.find(CB); 60 const auto OldPriority = It->second; 61 It->second = evaluate(CB); 62 const auto NewPriority = It->second; 63 return isMoreDesirable(OldPriority, NewPriority); 64 } 65 }; 66 67 class CostPriority : public InlinePriority { 68 using PriorityT = int; 69 DenseMap<const CallBase *, PriorityT> Priorities; 70 std::function<InlineCost(const CallBase *)> getInlineCost; 71 72 PriorityT evaluate(const CallBase *CB) { 73 auto IC = getInlineCost(CB); 74 int cost = 0; 75 if (IC.isVariable()) 76 cost = IC.getCost(); 77 else 78 cost = IC.isNever() ? INT_MAX : INT_MIN; 79 return cost; 80 } 81 82 bool isMoreDesirable(const PriorityT &P1, const PriorityT &P2) const { 83 return P1 < P2; 84 } 85 86 public: 87 CostPriority() = delete; 88 CostPriority(std::function<InlineCost(const CallBase *)> getInlineCost) 89 : getInlineCost(getInlineCost){}; 90 91 bool hasLowerPriority(const CallBase *L, const CallBase *R) const override { 92 const auto I1 = Priorities.find(L); 93 const auto I2 = Priorities.find(R); 94 assert(I1 != Priorities.end() && I2 != Priorities.end()); 95 return isMoreDesirable(I2->second, I1->second); 96 } 97 98 // Update the priority associated with CB. 99 void update(const CallBase *CB) override { Priorities[CB] = evaluate(CB); }; 100 101 bool updateAndCheckDecreased(const CallBase *CB) override { 102 auto It = Priorities.find(CB); 103 const auto OldPriority = It->second; 104 It->second = evaluate(CB); 105 const auto NewPriority = It->second; 106 return isMoreDesirable(OldPriority, NewPriority); 107 } 108 }; 109 110 class PriorityInlineOrder : public InlineOrder<std::pair<CallBase *, int>> { 111 using T = std::pair<CallBase *, int>; 112 using reference = T &; 113 using const_reference = const T &; 114 115 // A call site could become less desirable for inlining because of the size 116 // growth from prior inlining into the callee. This method is used to lazily 117 // update the desirability of a call site if it's decreasing. It is only 118 // called on pop() or front(), not every time the desirability changes. When 119 // the desirability of the front call site decreases, an updated one would be 120 // pushed right back into the heap. For simplicity, those cases where 121 // the desirability of a call site increases are ignored here. 122 void adjust() { 123 while (PriorityPtr->updateAndCheckDecreased(Heap.front())) { 124 std::pop_heap(Heap.begin(), Heap.end(), isLess); 125 std::push_heap(Heap.begin(), Heap.end(), isLess); 126 } 127 } 128 129 public: 130 PriorityInlineOrder(std::unique_ptr<InlinePriority> PriorityPtr) 131 : PriorityPtr(std::move(PriorityPtr)) { 132 isLess = [this](const CallBase *L, const CallBase *R) { 133 return this->PriorityPtr->hasLowerPriority(L, R); 134 }; 135 } 136 137 size_t size() override { return Heap.size(); } 138 139 void push(const T &Elt) override { 140 CallBase *CB = Elt.first; 141 const int InlineHistoryID = Elt.second; 142 143 Heap.push_back(CB); 144 PriorityPtr->update(CB); 145 std::push_heap(Heap.begin(), Heap.end(), isLess); 146 InlineHistoryMap[CB] = InlineHistoryID; 147 } 148 149 T pop() override { 150 assert(size() > 0); 151 adjust(); 152 153 CallBase *CB = Heap.front(); 154 T Result = std::make_pair(CB, InlineHistoryMap[CB]); 155 InlineHistoryMap.erase(CB); 156 std::pop_heap(Heap.begin(), Heap.end(), isLess); 157 Heap.pop_back(); 158 return Result; 159 } 160 161 const_reference front() override { 162 assert(size() > 0); 163 adjust(); 164 165 CallBase *CB = Heap.front(); 166 return *InlineHistoryMap.find(CB); 167 } 168 169 void erase_if(function_ref<bool(T)> Pred) override { 170 auto PredWrapper = [=](CallBase *CB) -> bool { 171 return Pred(std::make_pair(CB, 0)); 172 }; 173 llvm::erase_if(Heap, PredWrapper); 174 std::make_heap(Heap.begin(), Heap.end(), isLess); 175 } 176 177 private: 178 SmallVector<CallBase *, 16> Heap; 179 std::function<bool(const CallBase *L, const CallBase *R)> isLess; 180 DenseMap<CallBase *, int> InlineHistoryMap; 181 std::unique_ptr<InlinePriority> PriorityPtr; 182 }; 183 184 } // namespace 185 186 static llvm::InlineCost getInlineCostWrapper(CallBase &CB, 187 FunctionAnalysisManager &FAM, 188 const InlineParams &Params) { 189 Function &Caller = *CB.getCaller(); 190 ProfileSummaryInfo *PSI = 191 FAM.getResult<ModuleAnalysisManagerFunctionProxy>(Caller) 192 .getCachedResult<ProfileSummaryAnalysis>( 193 *CB.getParent()->getParent()->getParent()); 194 195 auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(Caller); 196 auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & { 197 return FAM.getResult<AssumptionAnalysis>(F); 198 }; 199 auto GetBFI = [&](Function &F) -> BlockFrequencyInfo & { 200 return FAM.getResult<BlockFrequencyAnalysis>(F); 201 }; 202 auto GetTLI = [&](Function &F) -> const TargetLibraryInfo & { 203 return FAM.getResult<TargetLibraryAnalysis>(F); 204 }; 205 206 Function &Callee = *CB.getCalledFunction(); 207 auto &CalleeTTI = FAM.getResult<TargetIRAnalysis>(Callee); 208 bool RemarksEnabled = 209 Callee.getContext().getDiagHandlerPtr()->isMissedOptRemarkEnabled( 210 DEBUG_TYPE); 211 return getInlineCost(CB, Params, CalleeTTI, GetAssumptionCache, GetTLI, 212 GetBFI, PSI, RemarksEnabled ? &ORE : nullptr); 213 } 214 215 std::unique_ptr<InlineOrder<std::pair<CallBase *, int>>> 216 llvm::getInlineOrder(InlinePriorityMode UseInlinePriority, 217 FunctionAnalysisManager &FAM, const InlineParams &Params) { 218 switch (UseInlinePriority) { 219 case InlinePriorityMode::NoPriority: 220 return std::make_unique<DefaultInlineOrder<std::pair<CallBase *, int>>>(); 221 222 case InlinePriorityMode::Size: 223 LLVM_DEBUG(dbgs() << " Current used priority: Size priority ---- \n"); 224 return std::make_unique<PriorityInlineOrder>( 225 std::make_unique<SizePriority>()); 226 227 case InlinePriorityMode::Cost: 228 LLVM_DEBUG(dbgs() << " Current used priority: Cost priority ---- \n"); 229 return std::make_unique<PriorityInlineOrder>( 230 std::make_unique<CostPriority>([&](const CallBase *CB) -> InlineCost { 231 return getInlineCostWrapper(const_cast<CallBase &>(*CB), FAM, Params); 232 })); 233 234 default: 235 llvm_unreachable("Unsupported Inline Priority Mode"); 236 break; 237 } 238 return nullptr; 239 } 240