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 class Module;
24 
25 template <typename T> class InlineOrder {
26 public:
27  using reference = T &;
28  using const_reference = const T &;
29 
30  virtual ~InlineOrder() {}
31 
32  virtual size_t size() = 0;
33 
34  virtual void push(const T &Elt) = 0;
35 
36  virtual T pop() = 0;
37 
38  virtual const_reference front() = 0;
39 
40  virtual void erase_if(function_ref<bool(T)> Pred) = 0;
41 
42  bool empty() { return !size(); }
43 };
44 
45 template <typename T, typename Container = SmallVector<T, 16>>
46 class DefaultInlineOrder : public InlineOrder<T> {
47  using reference = T &;
48  using const_reference = const T &;
49 
50 public:
51  size_t size() override { return Calls.size() - FirstIndex; }
52 
53  void push(const T &Elt) override { Calls.push_back(Elt); }
54 
55  T pop() override {
56  assert(size() > 0);
57  return Calls[FirstIndex++];
58  }
59 
60  const_reference front() override {
61  assert(size() > 0);
62  return Calls[FirstIndex];
63  }
64 
65  void erase_if(function_ref<bool(T)> Pred) override {
66  Calls.erase(std::remove_if(Calls.begin() + FirstIndex, Calls.end(), Pred),
67  Calls.end());
68  }
69 
70 private:
71  Container Calls;
72  size_t FirstIndex = 0;
73 };
74 
76 public:
78 
79  static bool isMoreDesirable(const InlineSizePriority &S1,
80  const InlineSizePriority &S2) {
81  return S1.Size < S2.Size;
82  }
83 
86  return InlineSizePriority(Callee->getInstructionCount());
87  }
88 
89  int Size;
90 };
91 
92 template <typename PriorityT>
93 class PriorityInlineOrder : public InlineOrder<std::pair<CallBase *, int>> {
94  using T = std::pair<CallBase *, int>;
95  using HeapT = std::pair<CallBase *, PriorityT>;
96  using reference = T &;
97  using const_reference = const T &;
98 
99  static bool cmp(const HeapT &P1, const HeapT &P2) {
100  return PriorityT::isMoreDesirable(P2.second, P1.second);
101  }
102 
103  // A call site could become less desirable for inlining because of the size
104  // growth from prior inlining into the callee. This method is used to lazily
105  // update the desirability of a call site if it's decreasing. It is only
106  // called on pop() or front(), not every time the desirability changes. When
107  // the desirability of the front call site decreases, an updated one would be
108  // pushed right back into the heap. For simplicity, those cases where
109  // the desirability of a call site increases are ignored here.
110  void adjust() {
111  bool Changed = false;
112  do {
113  CallBase *CB = Heap.front().first;
114  const PriorityT PreviousGoodness = Heap.front().second;
115  const PriorityT CurrentGoodness = PriorityT::evaluate(CB);
116  Changed = PriorityT::isMoreDesirable(PreviousGoodness, CurrentGoodness);
117  if (Changed) {
118  std::pop_heap(Heap.begin(), Heap.end(), cmp);
119  Heap.pop_back();
120  Heap.push_back({CB, CurrentGoodness});
121  std::push_heap(Heap.begin(), Heap.end(), cmp);
122  }
123  } while (Changed);
124  }
125 
126 public:
127  size_t size() override { return Heap.size(); }
128 
129  void push(const T &Elt) override {
130  CallBase *CB = Elt.first;
131  const int InlineHistoryID = Elt.second;
132  const PriorityT Goodness = PriorityT::evaluate(CB);
133 
134  Heap.push_back({CB, Goodness});
135  std::push_heap(Heap.begin(), Heap.end(), cmp);
136  InlineHistoryMap[CB] = InlineHistoryID;
137  }
138 
139  T pop() override {
140  assert(size() > 0);
141  adjust();
142 
143  CallBase *CB = Heap.front().first;
144  T Result = std::make_pair(CB, InlineHistoryMap[CB]);
145  InlineHistoryMap.erase(CB);
146  std::pop_heap(Heap.begin(), Heap.end(), cmp);
147  Heap.pop_back();
148  return Result;
149  }
150 
151  const_reference front() override {
152  assert(size() > 0);
153  adjust();
154 
155  CallBase *CB = Heap.front().first;
156  return *InlineHistoryMap.find(CB);
157  }
158 
159  void erase_if(function_ref<bool(T)> Pred) override {
160  auto PredWrapper = [=](HeapT P) -> bool {
161  return Pred(std::make_pair(P.first, 0));
162  };
163  llvm::erase_if(Heap, PredWrapper);
164  std::make_heap(Heap.begin(), Heap.end(), cmp);
165  }
166 
167 private:
169  DenseMap<CallBase *, int> InlineHistoryMap;
170 };
171 } // namespace llvm
172 #endif // LLVM_ANALYSIS_INLINEORDER_H
llvm::PriorityInlineOrder::push
void push(const T &Elt) override
Definition: InlineOrder.h:129
llvm
This file implements support for optimizing divisions by a constant.
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:30
llvm::SmallVector< HeapT, 16 >
llvm::InlineOrder< std::pair< CallBase *, int > >::const_reference
const std::pair< CallBase *, int > & const_reference
Definition: InlineOrder.h:28
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:1732
DenseMap.h
llvm::PriorityInlineOrder
Definition: InlineOrder.h:93
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::InlineOrder
Definition: InlineOrder.h:25
llvm::PriorityInlineOrder::front
const_reference front() override
Definition: InlineOrder.h:151
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:1590
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:159
llvm::CallBase::getCalledFunction
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation.
Definition: InstrTypes.h:1383
llvm::InlineOrder< std::pair< CallBase *, int > >::reference
std::pair< CallBase *, int > & reference
Definition: InlineOrder.h:27
llvm::InlineSizePriority::isMoreDesirable
static bool isMoreDesirable(const InlineSizePriority &S1, const InlineSizePriority &S2)
Definition: InlineOrder.h:79
llvm::InlineSizePriority::evaluate
static InlineSizePriority evaluate(CallBase *CB)
Definition: InlineOrder.h:84
llvm::InlineOrder::pop
virtual T pop()=0
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:168
llvm::DefaultInlineOrder::pop
T pop() override
Definition: InlineOrder.h:55
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:75
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::InlineOrder::empty
bool empty()
Definition: InlineOrder.h:42
llvm::ReplayInlineScope::Function
@ Function
llvm::DefaultInlineOrder
Definition: InlineOrder.h:46
llvm::InlineOrder::push
virtual void push(const T &Elt)=0
Module
Machine Check Debug Module
Definition: MachineCheckDebugify.cpp:122
llvm::PriorityInlineOrder::pop
T pop() override
Definition: InlineOrder.h:139
llvm::PriorityInlineOrder::size
size_t size() override
Definition: InlineOrder.h:127
Callee
amdgpu Simplify well known AMD library false FunctionCallee Callee
Definition: AMDGPULibCalls.cpp:206
llvm::DefaultInlineOrder::push
void push(const T &Elt) override
Definition: InlineOrder.h:53
adjust
Definition: AVRAsmBackend.cpp:33
llvm::DefaultInlineOrder::front
const_reference front() override
Definition: InlineOrder.h:60
llvm::InlineOrder::size
virtual size_t size()=0
llvm::DefaultInlineOrder::erase_if
void erase_if(function_ref< bool(T)> Pred) override
Definition: InlineOrder.h:65
Function.h
llvm::InlineOrder::front
virtual const_reference front()=0
llvm::InlineSizePriority::InlineSizePriority
InlineSizePriority(int Size)
Definition: InlineOrder.h:77
Instructions.h
SmallVector.h
llvm::DefaultInlineOrder::size
size_t size() override
Definition: InlineOrder.h:51
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1161
llvm::InlineSizePriority::Size
int Size
Definition: InlineOrder.h:89