LLVM  14.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"
13 #include "llvm/ADT/SmallVector.h"
14 #include "llvm/IR/Function.h"
15 #include "llvm/IR/Instruction.h"
16 #include "llvm/IR/Instructions.h"
17 #include <algorithm>
18 #include <utility>
19 
20 namespace llvm {
21 class CallBase;
22 class Function;
23 
24 template <typename T> class InlineOrder {
25 public:
26  using reference = T &;
27  using const_reference = const T &;
28 
29  virtual ~InlineOrder() {}
30 
31  virtual size_t size() = 0;
32 
33  virtual void push(const T &Elt) = 0;
34 
35  virtual T pop() = 0;
36 
37  virtual const_reference front() = 0;
38 
39  virtual void erase_if(function_ref<bool(T)> Pred) = 0;
40 
41  bool empty() { return !size(); }
42 };
43 
44 template <typename T, typename Container = SmallVector<T, 16>>
45 class DefaultInlineOrder : public InlineOrder<T> {
46  using reference = T &;
47  using const_reference = const T &;
48 
49 public:
50  size_t size() override { return Calls.size() - FirstIndex; }
51 
52  void push(const T &Elt) override { Calls.push_back(Elt); }
53 
54  T pop() override {
55  assert(size() > 0);
56  return Calls[FirstIndex++];
57  }
58 
59  const_reference front() override {
60  assert(size() > 0);
61  return Calls[FirstIndex];
62  }
63 
64  void erase_if(function_ref<bool(T)> Pred) override {
65  Calls.erase(std::remove_if(Calls.begin() + FirstIndex, Calls.end(), Pred),
66  Calls.end());
67  }
68 
69 private:
70  Container Calls;
71  size_t FirstIndex = 0;
72 };
73 
75 public:
77 
78  static bool isMoreDesirable(const InlineSizePriority &S1,
79  const InlineSizePriority &S2) {
80  return S1.Size < S2.Size;
81  }
82 
85  return InlineSizePriority(Callee->getInstructionCount());
86  }
87 
88  int Size;
89 };
90 
91 template <typename PriorityT>
92 class PriorityInlineOrder : public InlineOrder<std::pair<CallBase *, int>> {
93  using T = std::pair<CallBase *, int>;
94  using HeapT = std::pair<CallBase *, PriorityT>;
95  using reference = T &;
96  using const_reference = const T &;
97 
98  static bool cmp(const HeapT &P1, const HeapT &P2) {
99  return PriorityT::isMoreDesirable(P2.second, P1.second);
100  }
101 
102  // A call site could become less desirable for inlining because of the size
103  // growth from prior inlining into the callee. This method is used to lazily
104  // update the desirability of a call site if it's decreasing. It is only
105  // called on pop() or front(), not every time the desirability changes. When
106  // the desirability of the front call site decreases, an updated one would be
107  // pushed right back into the heap. For simplicity, those cases where
108  // the desirability of a call site increases are ignored here.
109  void adjust() {
110  bool Changed = false;
111  do {
112  CallBase *CB = Heap.front().first;
113  const PriorityT PreviousGoodness = Heap.front().second;
114  const PriorityT CurrentGoodness = PriorityT::evaluate(CB);
115  Changed = PriorityT::isMoreDesirable(PreviousGoodness, CurrentGoodness);
116  if (Changed) {
117  std::pop_heap(Heap.begin(), Heap.end(), cmp);
118  Heap.pop_back();
119  Heap.push_back({CB, CurrentGoodness});
120  std::push_heap(Heap.begin(), Heap.end(), cmp);
121  }
122  } while (Changed);
123  }
124 
125 public:
126  size_t size() override { return Heap.size(); }
127 
128  void push(const T &Elt) override {
129  CallBase *CB = Elt.first;
130  const int InlineHistoryID = Elt.second;
131  const PriorityT Goodness = PriorityT::evaluate(CB);
132 
133  Heap.push_back({CB, Goodness});
134  std::push_heap(Heap.begin(), Heap.end(), cmp);
135  InlineHistoryMap[CB] = InlineHistoryID;
136  }
137 
138  T pop() override {
139  assert(size() > 0);
140  adjust();
141 
142  CallBase *CB = Heap.front().first;
143  T Result = std::make_pair(CB, InlineHistoryMap[CB]);
144  InlineHistoryMap.erase(CB);
145  std::pop_heap(Heap.begin(), Heap.end(), cmp);
146  Heap.pop_back();
147  return Result;
148  }
149 
150  const_reference front() override {
151  assert(size() > 0);
152  adjust();
153 
154  CallBase *CB = Heap.front().first;
155  return *InlineHistoryMap.find(CB);
156  }
157 
158  void erase_if(function_ref<bool(T)> Pred) override {
159  auto PredWrapper = [=](HeapT P) -> bool {
160  return Pred(std::make_pair(P.first, 0));
161  };
162  llvm::erase_if(Heap, PredWrapper);
163  std::make_heap(Heap.begin(), Heap.end(), cmp);
164  }
165 
166 private:
168  DenseMap<CallBase *, int> InlineHistoryMap;
169 };
170 } // namespace llvm
171 #endif // LLVM_ANALYSIS_INLINEORDER_H
llvm::PriorityInlineOrder::push
void push(const T &Elt) override
Definition: InlineOrder.h:128
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
T
llvm::Function
Definition: Function.h:62
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::InlineOrder::~InlineOrder
virtual ~InlineOrder()
Definition: InlineOrder.h:29
llvm::SmallVector< HeapT, 16 >
llvm::InlineOrder< std::pair< CallBase *, int > >::const_reference
const std::pair< CallBase *, int > & const_reference
Definition: InlineOrder.h:27
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:1830
DenseMap.h
llvm::PriorityInlineOrder
Definition: InlineOrder.h:92
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::InlineOrder
Definition: InlineOrder.h:24
llvm::PriorityInlineOrder::front
const_reference front() override
Definition: InlineOrder.h:150
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:1688
Instruction.h
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
llvm::PriorityInlineOrder::erase_if
void erase_if(function_ref< bool(T)> Pred) override
Definition: InlineOrder.h:158
llvm::CallBase::getCalledFunction
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation.
Definition: InstrTypes.h:1398
llvm::InlineOrder< std::pair< CallBase *, int > >::reference
std::pair< CallBase *, int > & reference
Definition: InlineOrder.h:26
llvm::InlineSizePriority::isMoreDesirable
static bool isMoreDesirable(const InlineSizePriority &S1, const InlineSizePriority &S2)
Definition: InlineOrder.h:78
llvm::InlineSizePriority::evaluate
static InlineSizePriority evaluate(CallBase *CB)
Definition: InlineOrder.h:83
llvm::InlineOrder::pop
virtual T pop()=0
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:223
llvm::DefaultInlineOrder::pop
T pop() override
Definition: InlineOrder.h:54
llvm::InlineOrder::erase_if
virtual void erase_if(function_ref< bool(T)> Pred)=0
llvm::DenseMap
Definition: DenseMap.h:714
llvm::InlineSizePriority
Definition: InlineOrder.h:74
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::InlineOrder::empty
bool empty()
Definition: InlineOrder.h:41
llvm::DefaultInlineOrder
Definition: InlineOrder.h:45
llvm::InlineOrder::push
virtual void push(const T &Elt)=0
llvm::PriorityInlineOrder::pop
T pop() override
Definition: InlineOrder.h:138
llvm::PriorityInlineOrder::size
size_t size() override
Definition: InlineOrder.h:126
Callee
amdgpu Simplify well known AMD library false FunctionCallee Callee
Definition: AMDGPULibCalls.cpp:185
llvm::DefaultInlineOrder::push
void push(const T &Elt) override
Definition: InlineOrder.h:52
adjust
Definition: AVRAsmBackend.cpp:33
llvm::DefaultInlineOrder::front
const_reference front() override
Definition: InlineOrder.h:59
llvm::InlineOrder::size
virtual size_t size()=0
llvm::DefaultInlineOrder::erase_if
void erase_if(function_ref< bool(T)> Pred) override
Definition: InlineOrder.h:64
Function.h
llvm::InlineOrder::front
virtual const_reference front()=0
llvm::InlineSizePriority::InlineSizePriority
InlineSizePriority(int Size)
Definition: InlineOrder.h:76
Instructions.h
SmallVector.h
llvm::DefaultInlineOrder::size
size_t size() override
Definition: InlineOrder.h:50
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1176
llvm::codeview::PublicSymFlags::Function
@ Function
llvm::InlineSizePriority::Size
int Size
Definition: InlineOrder.h:88