LLVM  14.0.0git
PriorityWorklist.h
Go to the documentation of this file.
1 //===- PriorityWorklist.h - Worklist with insertion priority ----*- 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 /// \file
10 ///
11 /// This file provides a priority worklist. See the class comments for details.
12 ///
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLVM_ADT_PRIORITYWORKLIST_H
16 #define LLVM_ADT_PRIORITYWORKLIST_H
17 
18 #include "llvm/ADT/DenseMap.h"
19 #include "llvm/ADT/STLExtras.h"
20 #include "llvm/ADT/SmallVector.h"
21 #include "llvm/Support/Compiler.h"
22 #include <algorithm>
23 #include <cassert>
24 #include <cstddef>
25 #include <iterator>
26 #include <type_traits>
27 #include <vector>
28 
29 namespace llvm {
30 
31 /// A FILO worklist that prioritizes on re-insertion without duplication.
32 ///
33 /// This is very similar to a \c SetVector with the primary difference that
34 /// while re-insertion does not create a duplicate, it does adjust the
35 /// visitation order to respect the last insertion point. This can be useful
36 /// when the visit order needs to be prioritized based on insertion point
37 /// without actually having duplicate visits.
38 ///
39 /// Note that this doesn't prevent re-insertion of elements which have been
40 /// visited -- if you need to break cycles, a set will still be necessary.
41 ///
42 /// The type \c T must be default constructable to a null value that will be
43 /// ignored. It is an error to insert such a value, and popping elements will
44 /// never produce such a value. It is expected to be used with common nullable
45 /// types like pointers or optionals.
46 ///
47 /// Internally this uses a vector to store the worklist and a map to identify
48 /// existing elements in the worklist. Both of these may be customized, but the
49 /// map must support the basic DenseMap API for mapping from a T to an integer
50 /// index into the vector.
51 ///
52 /// A partial specialization is provided to automatically select a SmallVector
53 /// and a SmallDenseMap if custom data structures are not provided.
54 template <typename T, typename VectorT = std::vector<T>,
55  typename MapT = DenseMap<T, ptrdiff_t>>
57 public:
58  using value_type = T;
59  using key_type = T;
60  using reference = T&;
61  using const_reference = const T&;
62  using size_type = typename MapT::size_type;
63 
64  /// Construct an empty PriorityWorklist
65  PriorityWorklist() = default;
66 
67  /// Determine if the PriorityWorklist is empty or not.
68  bool empty() const {
69  return V.empty();
70  }
71 
72  /// Returns the number of elements in the worklist.
73  size_type size() const {
74  return M.size();
75  }
76 
77  /// Count the number of elements of a given key in the PriorityWorklist.
78  /// \returns 0 if the element is not in the PriorityWorklist, 1 if it is.
79  size_type count(const key_type &key) const {
80  return M.count(key);
81  }
82 
83  /// Return the last element of the PriorityWorklist.
84  const T &back() const {
85  assert(!empty() && "Cannot call back() on empty PriorityWorklist!");
86  return V.back();
87  }
88 
89  /// Insert a new element into the PriorityWorklist.
90  /// \returns true if the element was inserted into the PriorityWorklist.
91  bool insert(const T &X) {
92  assert(X != T() && "Cannot insert a null (default constructed) value!");
93  auto InsertResult = M.insert({X, V.size()});
94  if (InsertResult.second) {
95  // Fresh value, just append it to the vector.
96  V.push_back(X);
97  return true;
98  }
99 
100  auto &Index = InsertResult.first->second;
101  assert(V[Index] == X && "Value not actually at index in map!");
102  if (Index != (ptrdiff_t)(V.size() - 1)) {
103  // If the element isn't at the back, null it out and append a fresh one.
104  V[Index] = T();
105  Index = (ptrdiff_t)V.size();
106  V.push_back(X);
107  }
108  return false;
109  }
110 
111  /// Insert a sequence of new elements into the PriorityWorklist.
112  template <typename SequenceT>
113  std::enable_if_t<!std::is_convertible<SequenceT, T>::value>
114  insert(SequenceT &&Input) {
115  if (std::begin(Input) == std::end(Input))
116  // Nothing to do for an empty input sequence.
117  return;
118 
119  // First pull the input sequence into the vector as a bulk append
120  // operation.
121  ptrdiff_t StartIndex = V.size();
122  V.insert(V.end(), std::begin(Input), std::end(Input));
123  // Now walk backwards fixing up the index map and deleting any duplicates.
124  for (ptrdiff_t i = V.size() - 1; i >= StartIndex; --i) {
125  auto InsertResult = M.insert({V[i], i});
126  if (InsertResult.second)
127  continue;
128 
129  // If the existing index is before this insert's start, nuke that one and
130  // move it up.
131  ptrdiff_t &Index = InsertResult.first->second;
132  if (Index < StartIndex) {
133  V[Index] = T();
134  Index = i;
135  continue;
136  }
137 
138  // Otherwise the existing one comes first so just clear out the value in
139  // this slot.
140  V[i] = T();
141  }
142  }
143 
144  /// Remove the last element of the PriorityWorklist.
145  void pop_back() {
146  assert(!empty() && "Cannot remove an element when empty!");
147  assert(back() != T() && "Cannot have a null element at the back!");
148  M.erase(back());
149  do {
150  V.pop_back();
151  } while (!V.empty() && V.back() == T());
152  }
153 
155  T Ret = back();
156  pop_back();
157  return Ret;
158  }
159 
160  /// Erase an item from the worklist.
161  ///
162  /// Note that this is constant time due to the nature of the worklist implementation.
163  bool erase(const T& X) {
164  auto I = M.find(X);
165  if (I == M.end())
166  return false;
167 
168  assert(V[I->second] == X && "Value not actually at index in map!");
169  if (I->second == (ptrdiff_t)(V.size() - 1)) {
170  do {
171  V.pop_back();
172  } while (!V.empty() && V.back() == T());
173  } else {
174  V[I->second] = T();
175  }
176  M.erase(I);
177  return true;
178  }
179 
180  /// Erase items from the set vector based on a predicate function.
181  ///
182  /// This is intended to be equivalent to the following code, if we could
183  /// write it:
184  ///
185  /// \code
186  /// V.erase(remove_if(V, P), V.end());
187  /// \endcode
188  ///
189  /// However, PriorityWorklist doesn't expose non-const iterators, making any
190  /// algorithm like remove_if impossible to use.
191  ///
192  /// \returns true if any element is removed.
193  template <typename UnaryPredicate>
194  bool erase_if(UnaryPredicate P) {
195  typename VectorT::iterator E =
196  remove_if(V, TestAndEraseFromMap<UnaryPredicate>(P, M));
197  if (E == V.end())
198  return false;
199  for (auto I = V.begin(); I != E; ++I)
200  if (*I != T())
201  M[*I] = I - V.begin();
202  V.erase(E, V.end());
203  return true;
204  }
205 
206  /// Reverse the items in the PriorityWorklist.
207  ///
208  /// This does an in-place reversal. Other kinds of reverse aren't easy to
209  /// support in the face of the worklist semantics.
210 
211  /// Completely clear the PriorityWorklist
212  void clear() {
213  M.clear();
214  V.clear();
215  }
216 
217 private:
218  /// A wrapper predicate designed for use with std::remove_if.
219  ///
220  /// This predicate wraps a predicate suitable for use with std::remove_if to
221  /// call M.erase(x) on each element which is slated for removal. This just
222  /// allows the predicate to be move only which we can't do with lambdas
223  /// today.
224  template <typename UnaryPredicateT>
225  class TestAndEraseFromMap {
226  UnaryPredicateT P;
227  MapT &M;
228 
229  public:
230  TestAndEraseFromMap(UnaryPredicateT P, MapT &M)
231  : P(std::move(P)), M(M) {}
232 
233  bool operator()(const T &Arg) {
234  if (Arg == T())
235  // Skip null values in the PriorityWorklist.
236  return false;
237 
238  if (P(Arg)) {
239  M.erase(Arg);
240  return true;
241  }
242  return false;
243  }
244  };
245 
246  /// The map from value to index in the vector.
247  MapT M;
248 
249  /// The vector of elements in insertion order.
250  VectorT V;
251 };
252 
253 /// A version of \c PriorityWorklist that selects small size optimized data
254 /// structures for the vector and map.
255 template <typename T, unsigned N>
257  : public PriorityWorklist<T, SmallVector<T, N>,
258  SmallDenseMap<T, ptrdiff_t>> {
259 public:
260  SmallPriorityWorklist() = default;
261 };
262 
263 } // end namespace llvm
264 
265 #endif // LLVM_ADT_PRIORITYWORKLIST_H
i
i
Definition: README.txt:29
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::PriorityWorklist::pop_back
void pop_back()
Remove the last element of the PriorityWorklist.
Definition: PriorityWorklist.h:145
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::PriorityWorklist::insert
bool insert(const T &X)
Insert a new element into the PriorityWorklist.
Definition: PriorityWorklist.h:91
llvm::PriorityWorklist::size
size_type size() const
Returns the number of elements in the worklist.
Definition: PriorityWorklist.h:73
llvm::SmallPriorityWorklist::SmallPriorityWorklist
SmallPriorityWorklist()=default
DenseMap.h
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:224
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::PriorityWorklist
A FILO worklist that prioritizes on re-insertion without duplication.
Definition: PriorityWorklist.h:56
llvm::MipsISD::Ret
@ Ret
Definition: MipsISelLowering.h:116
STLExtras.h
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:206
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
llvm::LazyCallGraph::SCC
An SCC of the call graph.
Definition: LazyCallGraph.h:422
ptrdiff_t
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::PriorityWorklist::erase_if
bool erase_if(UnaryPredicate P)
Erase items from the set vector based on a predicate function.
Definition: PriorityWorklist.h:194
llvm::PriorityWorklist::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: PriorityWorklist.h:154
llvm::PriorityWorklist< llvm::LazyCallGraph::SCC *, SmallVector< llvm::LazyCallGraph::SCC *, N >, SmallDenseMap< llvm::LazyCallGraph::SCC *, ptrdiff_t > >::size_type
typename SmallDenseMap< llvm::LazyCallGraph::SCC *, ptrdiff_t > ::size_type size_type
Definition: PriorityWorklist.h:62
llvm::PriorityWorklist::back
const T & back() const
Return the last element of the PriorityWorklist.
Definition: PriorityWorklist.h:84
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::PriorityWorklist::erase
bool erase(const T &X)
Erase an item from the worklist.
Definition: PriorityWorklist.h:163
Index
uint32_t Index
Definition: ELFObjHandler.cpp:84
llvm::SmallPriorityWorklist
A version of PriorityWorklist that selects small size optimized data structures for the vector and ma...
Definition: PriorityWorklist.h:256
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::PriorityWorklist::empty
bool empty() const
Determine if the PriorityWorklist is empty or not.
Definition: PriorityWorklist.h:68
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:1609
llvm::PriorityWorklist::PriorityWorklist
PriorityWorklist()=default
Construct an empty PriorityWorklist.
Compiler.h
llvm::PriorityWorklist::clear
void clear()
Reverse the items in the PriorityWorklist.
Definition: PriorityWorklist.h:212
llvm::PriorityWorklist::insert
std::enable_if_t<!std::is_convertible< SequenceT, T >::value > insert(SequenceT &&Input)
Insert a sequence of new elements into the PriorityWorklist.
Definition: PriorityWorklist.h:114
std
Definition: BitVector.h:838
LLVM_NODISCARD
#define LLVM_NODISCARD
LLVM_NODISCARD - Warn if a type or return value is discarded.
Definition: Compiler.h:161
SmallVector.h
llvm::PriorityWorklist::count
size_type count(const key_type &key) const
Count the number of elements of a given key in the PriorityWorklist.
Definition: PriorityWorklist.h:79