LLVM  15.0.0git
InlineOrder.h
Go to the documentation of this file.
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"
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 
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;
84 
85  static PriorityT evaluate(const CallBase *CB) {
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:
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
llvm::InlinePriority::updateAndCheckDecreased
virtual bool updateAndCheckDecreased(const CallBase *CB)=0
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::SizePriority::update
void update(const CallBase *CB) override
Definition: InlineOrder.h:103
llvm::Function
Definition: Function.h:60
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
llvm::SizePriority
Definition: InlineOrder.h:81
llvm::InlineOrder< std::pair< CallBase *, int > >::const_reference
const std::pair< CallBase *, int > & const_reference
Definition: InlineOrder.h:26
llvm::erase_if
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
Definition: STLExtras.h:1807
DenseMap.h
llvm::PriorityInlineOrder
Definition: InlineOrder.h:114
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::InlineOrder
Definition: InlineOrder.h:23
I1
@ I1
Definition: DXILOpLowering.cpp:37
llvm::InlinePriority
Definition: InlineOrder.h:73
llvm::PriorityInlineOrder::pop
T pop() override
Definition: InlineOrder.h:153
llvm::remove_if
auto remove_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::remove_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1656
llvm::PriorityInlineOrder::erase_if
void erase_if(function_ref< bool(T)> Pred) override
Definition: InlineOrder.h:173
P2
This might compile to this xmm1 xorps xmm0 movss xmm0 ret Now consider if the code caused xmm1 to get spilled This might produce this xmm1 movaps xmm0 movaps xmm1 movss xmm0 ret since the reload is only used by these we could fold it into the producing something like xmm1 movaps xmm0 ret saving two instructions The basic idea is that a reload from a spill if only one byte chunk is bring in zeros the one element instead of elements This can be used to simplify a variety of shuffle where the elements are fixed zeros This code generates ugly probably due to costs being off or< 4 x float > * P2
Definition: README-SSE.txt:278
InstrTypes.h
llvm::CallBase::getCalledFunction
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
Definition: InstrTypes.h:1396
llvm::PriorityInlineOrder::push
void push(const T &Elt) override
Definition: InlineOrder.h:143
llvm::PriorityInlineOrder::PriorityInlineOrder
PriorityInlineOrder(std::unique_ptr< InlinePriority > PriorityPtr)
Definition: InlineOrder.h:134
llvm::InlineOrder< std::pair< CallBase *, int > >::reference
std::pair< CallBase *, int > & reference
Definition: InlineOrder.h:25
STLFunctionalExtras.h
llvm::PriorityInlineOrder::front
const_reference front() override
Definition: InlineOrder.h:165
llvm::InlinePriority::update
virtual void update(const CallBase *CB)=0
llvm::InlinePriority::~InlinePriority
virtual ~InlinePriority()=default
llvm::InlineOrder::pop
virtual T pop()=0
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLFunctionalExtras.h:36
llvm::DefaultInlineOrder::pop
T pop() override
Definition: InlineOrder.h:53
llvm::InlineOrder::erase_if
virtual void erase_if(function_ref< bool(T)> Pred)=0
llvm::DenseMap
Definition: DenseMap.h:716
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:152
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::move
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1675
llvm::InlineOrder::empty
bool empty()
Definition: InlineOrder.h:40
function
print Print MemDeps of function
Definition: MemDepPrinter.cpp:82
llvm::InlinePriority::hasLowerPriority
virtual bool hasLowerPriority(const CallBase *L, const CallBase *R) const =0
llvm::InlineOrder::~InlineOrder
virtual ~InlineOrder()=default
llvm::DefaultInlineOrder
Definition: InlineOrder.h:44
llvm::InlineOrder::push
virtual void push(const T &Elt)=0
llvm::PriorityInlineOrder::size
size_t size() override
Definition: InlineOrder.h:141
Callee
amdgpu Simplify well known AMD library false FunctionCallee Callee
Definition: AMDGPULibCalls.cpp:186
llvm::DefaultInlineOrder::push
void push(const T &Elt) override
Definition: InlineOrder.h:51
adjust
Definition: AVRAsmBackend.cpp:33
llvm::DefaultInlineOrder::front
const_reference front() override
Definition: InlineOrder.h:58
llvm::InlineOrder::size
virtual size_t size()=0
std
Definition: BitVector.h:851
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end
iterator end()
Definition: DenseMap.h:84
llvm::DefaultInlineOrder::erase_if
void erase_if(function_ref< bool(T)> Pred) override
Definition: InlineOrder.h:63
llvm::InlineOrder::front
virtual const_reference front()=0
SmallVector.h
llvm::SizePriority::updateAndCheckDecreased
bool updateAndCheckDecreased(const CallBase *CB) override
Definition: InlineOrder.h:105
llvm::DefaultInlineOrder::size
size_t size() override
Definition: InlineOrder.h:49
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1174
llvm::codeview::PublicSymFlags::Function
@ Function