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