1 //===- InlineOrder.h - 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 #ifndef LLVM_ANALYSIS_INLINEORDER_H 10 #define LLVM_ANALYSIS_INLINEORDER_H 11 12 #include "llvm/ADT/DenseMap.h" 13 #include "llvm/ADT/STLFunctionalExtras.h" 14 #include "llvm/ADT/SmallVector.h" 15 #include "llvm/IR/InstrTypes.h" 16 #include <algorithm> 17 #include <utility> 18 19 namespace llvm { 20 class CallBase; 21 class Function; 22 23 template <typename T> class InlineOrder { 24 public: 25 using reference = T &; 26 using const_reference = const T &; 27 28 virtual ~InlineOrder() = default; 29 30 virtual size_t size() = 0; 31 32 virtual void push(const T &Elt) = 0; 33 34 virtual T pop() = 0; 35 36 virtual const_reference front() = 0; 37 38 virtual void erase_if(function_ref<bool(T)> Pred) = 0; 39 40 bool empty() { return !size(); } 41 }; 42 43 template <typename T, typename Container = SmallVector<T, 16>> 44 class DefaultInlineOrder : public InlineOrder<T> { 45 using reference = T &; 46 using const_reference = const T &; 47 48 public: 49 size_t size() override { return Calls.size() - FirstIndex; } 50 51 void push(const T &Elt) override { Calls.push_back(Elt); } 52 53 T pop() override { 54 assert(size() > 0); 55 return Calls[FirstIndex++]; 56 } 57 58 const_reference front() override { 59 assert(size() > 0); 60 return Calls[FirstIndex]; 61 } 62 63 void erase_if(function_ref<bool(T)> Pred) override { 64 Calls.erase(std::remove_if(Calls.begin() + FirstIndex, Calls.end(), Pred), 65 Calls.end()); 66 } 67 68 private: 69 Container Calls; 70 size_t FirstIndex = 0; 71 }; 72 73 class InlinePriority { 74 public: 75 virtual ~InlinePriority() = default; 76 virtual bool hasLowerPriority(const CallBase *L, const CallBase *R) const = 0; 77 virtual void update(const CallBase *CB) = 0; 78 virtual bool updateAndCheckDecreased(const CallBase *CB) = 0; 79 }; 80 81 class SizePriority : public InlinePriority { 82 using PriorityT = unsigned; 83 DenseMap<const CallBase *, PriorityT> Priorities; 84 85 static PriorityT evaluate(const CallBase *CB) { 86 Function *Callee = CB->getCalledFunction(); 87 return Callee->getInstructionCount(); 88 } 89 90 static bool isMoreDesirable(const PriorityT &P1, const PriorityT &P2) { 91 return P1 < P2; 92 } 93 94 bool hasLowerPriority(const CallBase *L, const CallBase *R) const override { 95 const auto I1 = Priorities.find(L); 96 const auto I2 = Priorities.find(R); 97 assert(I1 != Priorities.end() && I2 != Priorities.end()); 98 return isMoreDesirable(I2->second, I1->second); 99 } 100 101 public: 102 // Update the priority associated with CB. 103 void update(const CallBase *CB) override { Priorities[CB] = evaluate(CB); }; 104 105 bool updateAndCheckDecreased(const CallBase *CB) override { 106 auto It = Priorities.find(CB); 107 const auto OldPriority = It->second; 108 It->second = evaluate(CB); 109 const auto NewPriority = It->second; 110 return isMoreDesirable(OldPriority, NewPriority); 111 } 112 }; 113 114 class PriorityInlineOrder : public InlineOrder<std::pair<CallBase *, int>> { 115 using T = std::pair<CallBase *, int>; 116 using reference = T &; 117 using const_reference = const T &; 118 119 // A call site could become less desirable for inlining because of the size 120 // growth from prior inlining into the callee. This method is used to lazily 121 // update the desirability of a call site if it's decreasing. It is only 122 // called on pop() or front(), not every time the desirability changes. When 123 // the desirability of the front call site decreases, an updated one would be 124 // pushed right back into the heap. For simplicity, those cases where 125 // the desirability of a call site increases are ignored here. 126 void adjust() { 127 while (PriorityPtr->updateAndCheckDecreased(Heap.front())) { 128 std::pop_heap(Heap.begin(), Heap.end(), isLess); 129 std::push_heap(Heap.begin(), Heap.end(), isLess); 130 } 131 } 132 133 public: 134 PriorityInlineOrder(std::unique_ptr<InlinePriority> PriorityPtr) 135 : PriorityPtr(std::move(PriorityPtr)) { 136 isLess = [this](const CallBase *L, const CallBase *R) { 137 return this->PriorityPtr->hasLowerPriority(L, R); 138 }; 139 } 140 141 size_t size() override { return Heap.size(); } 142 143 void push(const T &Elt) override { 144 CallBase *CB = Elt.first; 145 const int InlineHistoryID = Elt.second; 146 147 Heap.push_back(CB); 148 PriorityPtr->update(CB); 149 std::push_heap(Heap.begin(), Heap.end(), isLess); 150 InlineHistoryMap[CB] = InlineHistoryID; 151 } 152 153 T pop() override { 154 assert(size() > 0); 155 adjust(); 156 157 CallBase *CB = Heap.front(); 158 T Result = std::make_pair(CB, InlineHistoryMap[CB]); 159 InlineHistoryMap.erase(CB); 160 std::pop_heap(Heap.begin(), Heap.end(), isLess); 161 Heap.pop_back(); 162 return Result; 163 } 164 165 const_reference front() override { 166 assert(size() > 0); 167 adjust(); 168 169 CallBase *CB = Heap.front(); 170 return *InlineHistoryMap.find(CB); 171 } 172 173 void erase_if(function_ref<bool(T)> Pred) override { 174 auto PredWrapper = [=](CallBase *CB) -> bool { 175 return Pred(std::make_pair(CB, 0)); 176 }; 177 llvm::erase_if(Heap, PredWrapper); 178 std::make_heap(Heap.begin(), Heap.end(), isLess); 179 } 180 181 private: 182 SmallVector<CallBase *, 16> Heap; 183 std::function<bool(const CallBase *L, const CallBase *R)> isLess; 184 DenseMap<CallBase *, int> InlineHistoryMap; 185 std::unique_ptr<InlinePriority> PriorityPtr; 186 }; 187 } // namespace llvm 188 #endif // LLVM_ANALYSIS_INLINEORDER_H 189