LLVM  13.0.0git
simple_ilist.h
Go to the documentation of this file.
1 //===- llvm/ADT/simple_ilist.h - Simple Intrusive List ----------*- 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_ADT_SIMPLE_ILIST_H
10 #define LLVM_ADT_SIMPLE_ILIST_H
11 
12 #include "llvm/ADT/ilist_base.h"
14 #include "llvm/ADT/ilist_node.h"
16 #include "llvm/Support/Compiler.h"
17 #include <algorithm>
18 #include <cassert>
19 #include <cstddef>
20 #include <functional>
21 #include <iterator>
22 #include <utility>
23 
24 namespace llvm {
25 
26 /// A simple intrusive list implementation.
27 ///
28 /// This is a simple intrusive list for a \c T that inherits from \c
29 /// ilist_node<T>. The list never takes ownership of anything inserted in it.
30 ///
31 /// Unlike \a iplist<T> and \a ilist<T>, \a simple_ilist<T> never deletes
32 /// values, and has no callback traits.
33 ///
34 /// The API for adding nodes include \a push_front(), \a push_back(), and \a
35 /// insert(). These all take values by reference (not by pointer), except for
36 /// the range version of \a insert().
37 ///
38 /// There are three sets of API for discarding nodes from the list: \a
39 /// remove(), which takes a reference to the node to remove, \a erase(), which
40 /// takes an iterator or iterator range and returns the next one, and \a
41 /// clear(), which empties out the container. All three are constant time
42 /// operations. None of these deletes any nodes; in particular, if there is a
43 /// single node in the list, then these have identical semantics:
44 /// \li \c L.remove(L.front());
45 /// \li \c L.erase(L.begin());
46 /// \li \c L.clear();
47 ///
48 /// As a convenience for callers, there are parallel APIs that take a \c
49 /// Disposer (such as \c std::default_delete<T>): \a removeAndDispose(), \a
50 /// eraseAndDispose(), and \a clearAndDispose(). These have different names
51 /// because the extra semantic is otherwise non-obvious. They are equivalent
52 /// to calling \a std::for_each() on the range to be discarded.
53 ///
54 /// The currently available \p Options customize the nodes in the list. The
55 /// same options must be specified in the \a ilist_node instantiation for
56 /// compatibility (although the order is irrelevant).
57 /// \li Use \a ilist_tag to designate which ilist_node for a given \p T this
58 /// list should use. This is useful if a type \p T is part of multiple,
59 /// independent lists simultaneously.
60 /// \li Use \a ilist_sentinel_tracking to always (or never) track whether a
61 /// node is a sentinel. Specifying \c true enables the \a
62 /// ilist_node::isSentinel() API. Unlike \a ilist_node::isKnownSentinel(),
63 /// which is only appropriate for assertions, \a ilist_node::isSentinel() is
64 /// appropriate for real logic.
65 ///
66 /// Here are examples of \p Options usage:
67 /// \li \c simple_ilist<T> gives the defaults. \li \c
68 /// simple_ilist<T,ilist_sentinel_tracking<true>> enables the \a
69 /// ilist_node::isSentinel() API.
70 /// \li \c simple_ilist<T,ilist_tag<A>,ilist_sentinel_tracking<false>>
71 /// specifies a tag of A and that tracking should be off (even when
72 /// LLVM_ENABLE_ABI_BREAKING_CHECKS are enabled).
73 /// \li \c simple_ilist<T,ilist_sentinel_tracking<false>,ilist_tag<A>> is
74 /// equivalent to the last.
75 ///
76 /// See \a is_valid_option for steps on adding a new option.
77 template <typename T, class... Options>
79  : ilist_detail::compute_node_options<T, Options...>::type::list_base_type,
81  typename ilist_detail::compute_node_options<T, Options...>::type> {
83  "Unrecognized node option!");
84  using OptionsT =
86  using list_base_type = typename OptionsT::list_base_type;
87  ilist_sentinel<OptionsT> Sentinel;
88 
89 public:
90  using value_type = typename OptionsT::value_type;
91  using pointer = typename OptionsT::pointer;
92  using reference = typename OptionsT::reference;
93  using const_pointer = typename OptionsT::const_pointer;
94  using const_reference = typename OptionsT::const_reference;
99  using size_type = size_t;
101 
102  simple_ilist() = default;
103  ~simple_ilist() = default;
104 
105  // No copy constructors.
106  simple_ilist(const simple_ilist &) = delete;
107  simple_ilist &operator=(const simple_ilist &) = delete;
108 
109  // Move constructors.
112  clear();
113  splice(end(), X);
114  return *this;
115  }
116 
117  iterator begin() { return ++iterator(Sentinel); }
118  const_iterator begin() const { return ++const_iterator(Sentinel); }
119  iterator end() { return iterator(Sentinel); }
120  const_iterator end() const { return const_iterator(Sentinel); }
121  reverse_iterator rbegin() { return ++reverse_iterator(Sentinel); }
123  return ++const_reverse_iterator(Sentinel);
124  }
125  reverse_iterator rend() { return reverse_iterator(Sentinel); }
127  return const_reverse_iterator(Sentinel);
128  }
129 
130  /// Check if the list is empty in constant time.
131  LLVM_NODISCARD bool empty() const { return Sentinel.empty(); }
132 
133  /// Calculate the size of the list in linear time.
135  return std::distance(begin(), end());
136  }
137 
138  reference front() { return *begin(); }
139  const_reference front() const { return *begin(); }
140  reference back() { return *rbegin(); }
141  const_reference back() const { return *rbegin(); }
142 
143  /// Insert a node at the front; never copies.
145 
146  /// Insert a node at the back; never copies.
148 
149  /// Remove the node at the front; never deletes.
150  void pop_front() { erase(begin()); }
151 
152  /// Remove the node at the back; never deletes.
153  void pop_back() { erase(--end()); }
154 
155  /// Swap with another list in place using std::swap.
156  void swap(simple_ilist &X) { std::swap(*this, X); }
157 
158  /// Insert a node by reference; never copies.
160  list_base_type::insertBefore(*I.getNodePtr(), *this->getNodePtr(&Node));
161  return iterator(&Node);
162  }
163 
164  /// Insert a range of nodes; never copies.
165  template <class Iterator>
166  void insert(iterator I, Iterator First, Iterator Last) {
167  for (; First != Last; ++First)
168  insert(I, *First);
169  }
170 
171  /// Clone another list.
172  template <class Cloner, class Disposer>
173  void cloneFrom(const simple_ilist &L2, Cloner clone, Disposer dispose) {
174  clearAndDispose(dispose);
175  for (const_reference V : L2)
176  push_back(*clone(V));
177  }
178 
179  /// Remove a node by reference; never deletes.
180  ///
181  /// \see \a erase() for removing by iterator.
182  /// \see \a removeAndDispose() if the node should be deleted.
184 
185  /// Remove a node by reference and dispose of it.
186  template <class Disposer>
187  void removeAndDispose(reference N, Disposer dispose) {
188  remove(N);
189  dispose(&N);
190  }
191 
192  /// Remove a node by iterator; never deletes.
193  ///
194  /// \see \a remove() for removing by reference.
195  /// \see \a eraseAndDispose() it the node should be deleted.
197  assert(I != end() && "Cannot remove end of list!");
198  remove(*I++);
199  return I;
200  }
201 
202  /// Remove a range of nodes; never deletes.
203  ///
204  /// \see \a eraseAndDispose() if the nodes should be deleted.
206  list_base_type::removeRange(*First.getNodePtr(), *Last.getNodePtr());
207  return Last;
208  }
209 
210  /// Remove a node by iterator and dispose of it.
211  template <class Disposer>
212  iterator eraseAndDispose(iterator I, Disposer dispose) {
213  auto Next = std::next(I);
214  erase(I);
215  dispose(&*I);
216  return Next;
217  }
218 
219  /// Remove a range of nodes and dispose of them.
220  template <class Disposer>
221  iterator eraseAndDispose(iterator First, iterator Last, Disposer dispose) {
222  while (First != Last)
223  First = eraseAndDispose(First, dispose);
224  return Last;
225  }
226 
227  /// Clear the list; never deletes.
228  ///
229  /// \see \a clearAndDispose() if the nodes should be deleted.
230  void clear() { Sentinel.reset(); }
231 
232  /// Clear the list and dispose of the nodes.
233  template <class Disposer> void clearAndDispose(Disposer dispose) {
234  eraseAndDispose(begin(), end(), dispose);
235  }
236 
237  /// Splice in another list.
239  splice(I, L2, L2.begin(), L2.end());
240  }
241 
242  /// Splice in a node from another list.
244  splice(I, L2, Node, std::next(Node));
245  }
246 
247  /// Splice in a range of nodes from another list.
248  void splice(iterator I, simple_ilist &, iterator First, iterator Last) {
249  list_base_type::transferBefore(*I.getNodePtr(), *First.getNodePtr(),
250  *Last.getNodePtr());
251  }
252 
253  /// Merge in another list.
254  ///
255  /// \pre \c this and \p RHS are sorted.
256  ///@{
257  void merge(simple_ilist &RHS) { merge(RHS, std::less<T>()); }
258  template <class Compare> void merge(simple_ilist &RHS, Compare comp);
259  ///@}
260 
261  /// Sort the list.
262  ///@{
263  void sort() { sort(std::less<T>()); }
264  template <class Compare> void sort(Compare comp);
265  ///@}
266 };
267 
268 template <class T, class... Options>
269 template <class Compare>
271  if (this == &RHS || RHS.empty())
272  return;
273  iterator LI = begin(), LE = end();
274  iterator RI = RHS.begin(), RE = RHS.end();
275  while (LI != LE) {
276  if (comp(*RI, *LI)) {
277  // Transfer a run of at least size 1 from RHS to LHS.
278  iterator RunStart = RI++;
279  RI = std::find_if(RI, RE, [&](reference RV) { return !comp(RV, *LI); });
280  splice(LI, RHS, RunStart, RI);
281  if (RI == RE)
282  return;
283  }
284  ++LI;
285  }
286  // Transfer the remaining RHS nodes once LHS is finished.
287  splice(LE, RHS, RI, RE);
288 }
289 
290 template <class T, class... Options>
291 template <class Compare>
293  // Vacuously sorted.
294  if (empty() || std::next(begin()) == end())
295  return;
296 
297  // Split the list in the middle.
298  iterator Center = begin(), End = begin();
299  while (End != end() && ++End != end()) {
300  ++Center;
301  ++End;
302  }
303  simple_ilist RHS;
304  RHS.splice(RHS.end(), *this, Center, end());
305 
306  // Sort the sublists and merge back together.
307  sort(comp);
308  RHS.sort(comp);
309  merge(RHS, comp);
310 }
311 
312 } // end namespace llvm
313 
314 #endif // LLVM_ADT_SIMPLE_ILIST_H
llvm
Definition: AllocatorList.h:23
llvm::simple_ilist::empty
LLVM_NODISCARD bool empty() const
Check if the list is empty in constant time.
Definition: simple_ilist.h:131
ilist_base.h
llvm::ilist_sentinel::empty
bool empty() const
Definition: ilist_node.h:248
llvm::simple_ilist::operator=
simple_ilist & operator=(simple_ilist &&X)
Definition: simple_ilist.h:111
llvm::simple_ilist::pop_front
void pop_front()
Remove the node at the front; never deletes.
Definition: simple_ilist.h:150
llvm::simple_ilist::simple_ilist
simple_ilist()=default
llvm::ilist_detail::SpecificNodeAccess< ilist_detail::compute_node_options< IRInstructionData, Options... >::type >::pointer
typename ilist_detail::compute_node_options< IRInstructionData, Options... >::type ::pointer pointer
Definition: ilist_node.h:212
llvm::simple_ilist::pop_back
void pop_back()
Remove the node at the back; never deletes.
Definition: simple_ilist.h:153
llvm::simple_ilist::clear
void clear()
Clear the list; never deletes.
Definition: simple_ilist.h:230
llvm::simple_ilist::front
const_reference front() const
Definition: simple_ilist.h:139
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
llvm::simple_ilist::merge
void merge(simple_ilist &RHS)
Merge in another list.
Definition: simple_ilist.h:257
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:224
llvm::simple_ilist::splice
void splice(iterator I, simple_ilist &, iterator First, iterator Last)
Splice in a range of nodes from another list.
Definition: simple_ilist.h:248
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::simple_ilist::rend
reverse_iterator rend()
Definition: simple_ilist.h:125
llvm::ilist_detail::SpecificNodeAccess< ilist_detail::compute_node_options< T, Options... >::type >::getNodePtr
static node_type * getNodePtr(pointer N)
Definition: ilist_node.h:216
llvm::simple_ilist::rbegin
const_reverse_iterator rbegin() const
Definition: simple_ilist.h:122
llvm::simple_ilist::clearAndDispose
void clearAndDispose(Disposer dispose)
Clear the list and dispose of the nodes.
Definition: simple_ilist.h:233
llvm::ilist_detail::SpecificNodeAccess
Definition: ilist_node.h:210
size_t
llvm::simple_ilist< IRInstructionData >::value_type
typename OptionsT::value_type value_type
Definition: simple_ilist.h:90
llvm::simple_ilist< IRInstructionData >::reference
typename OptionsT::reference reference
Definition: simple_ilist.h:92
llvm::ilist_detail::SpecificNodeAccess< ilist_detail::compute_node_options< IRInstructionData, Options... >::type >::const_pointer
typename ilist_detail::compute_node_options< IRInstructionData, Options... >::type ::const_pointer const_pointer
Definition: ilist_node.h:213
llvm::simple_ilist::rend
const_reverse_iterator rend() const
Definition: simple_ilist.h:126
llvm::simple_ilist::sort
void sort()
Sort the list.
Definition: simple_ilist.h:263
L2
add sub stmia L5 ldr L2
Definition: README.txt:201
ptrdiff_t
llvm::simple_ilist::removeAndDispose
void removeAndDispose(reference N, Disposer dispose)
Remove a node by reference and dispose of it.
Definition: simple_ilist.h:187
llvm::ilist_sentinel
Definition: ilist_node.h:29
llvm::simple_ilist::~simple_ilist
~simple_ilist()=default
merge
static LoopDeletionResult merge(LoopDeletionResult A, LoopDeletionResult B)
Definition: LoopDeletion.cpp:42
llvm::simple_ilist::erase
iterator erase(iterator First, iterator Last)
Remove a range of nodes; never deletes.
Definition: simple_ilist.h:205
First
into llvm powi allowing the code generator to produce balanced multiplication trees First
Definition: README.txt:54
Options
const char LLVMTargetMachineRef LLVMPassBuilderOptionsRef Options
Definition: PassBuilderBindings.cpp:48
llvm::simple_ilist::eraseAndDispose
iterator eraseAndDispose(iterator I, Disposer dispose)
Remove a node by iterator and dispose of it.
Definition: simple_ilist.h:212
llvm::AArch64CC::LE
@ LE
Definition: AArch64BaseInfo.h:249
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::simple_ilist::push_front
void push_front(reference Node)
Insert a node at the front; never copies.
Definition: simple_ilist.h:144
llvm::simple_ilist::end
const_iterator end() const
Definition: simple_ilist.h:120
type
AMD64 Optimization Manual has some nice information about optimizing integer multiplication by a constant How much of it applies to Intel s X86 implementation There are definite trade offs to xmm0 cvttss2siq rdx jb L3 subss xmm0 rax cvttss2siq rdx xorq rdx rax ret instead of xmm1 cvttss2siq rcx movaps xmm2 subss xmm2 cvttss2siq rax rdx xorq rax ucomiss xmm0 cmovb rax ret Seems like the jb branch has high likelihood of being taken It would have saved a few instructions It s not possible to reference and DH registers in an instruction requiring REX prefix divb and mulb both produce results in AH If isel emits a CopyFromReg which gets turned into a movb and that can be allocated a r8b r15b To get around isel emits a CopyFromReg from AX and then right shift it down by and truncate it It s not pretty but it works We need some register allocation magic to make the hack go which would often require a callee saved register Callees usually need to keep this value live for most of their body so it doesn t add a significant burden on them We currently implement this in however this is suboptimal because it means that it would be quite awkward to implement the optimization for callers A better implementation would be to relax the LLVM IR rules for sret arguments to allow a function with an sret argument to have a non void return type
Definition: README-X86-64.txt:70
llvm::AlignStyle::Center
@ Center
llvm::simple_ilist::insert
void insert(iterator I, Iterator First, Iterator Last)
Insert a range of nodes; never copies.
Definition: simple_ilist.h:166
llvm::simple_ilist::begin
iterator begin()
Definition: simple_ilist.h:117
llvm::simple_ilist::const_reverse_iterator
ilist_iterator< OptionsT, true, true > const_reverse_iterator
Definition: simple_ilist.h:98
llvm::simple_ilist::iterator
ilist_iterator< OptionsT, false, false > iterator
Definition: simple_ilist.h:95
llvm::simple_ilist::erase
iterator erase(iterator I)
Remove a node by iterator; never deletes.
Definition: simple_ilist.h:196
llvm::simple_ilist::simple_ilist
simple_ilist(simple_ilist &&X)
Definition: simple_ilist.h:110
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::simple_ilist< IRInstructionData >::const_reference
typename OptionsT::const_reference const_reference
Definition: simple_ilist.h:94
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::simple_ilist::push_back
void push_back(reference Node)
Insert a node at the back; never copies.
Definition: simple_ilist.h:147
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:840
llvm::simple_ilist::const_iterator
ilist_iterator< OptionsT, false, true > const_iterator
Definition: simple_ilist.h:96
llvm::simple_ilist::swap
void swap(simple_ilist &X)
Swap with another list in place using std::swap.
Definition: simple_ilist.h:156
llvm::simple_ilist::eraseAndDispose
iterator eraseAndDispose(iterator First, iterator Last, Disposer dispose)
Remove a range of nodes and dispose of them.
Definition: simple_ilist.h:221
Compare
QP Compare Ordered outs ins xscmpudp No builtin are required Or llvm fcmp order unorder compare DP QP Compare builtin are required DP Compare
Definition: README_P9.txt:309
llvm::sys::fs::remove
std::error_code remove(const Twine &path, bool IgnoreNonExisting=true)
Remove path.
this
Analysis the ScalarEvolution expression for r is this
Definition: README.txt:8
llvm::simple_ilist::rbegin
reverse_iterator rbegin()
Definition: simple_ilist.h:121
Compiler.h
Node
Definition: ItaniumDemangle.h:114
llvm::find_if
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1509
llvm::simple_ilist::cloneFrom
void cloneFrom(const simple_ilist &L2, Cloner clone, Disposer dispose)
Clone another list.
Definition: simple_ilist.h:173
llvm::empty
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
Definition: STLExtras.h:254
llvm::simple_ilist::operator=
simple_ilist & operator=(const simple_ilist &)=delete
llvm::simple_ilist::reverse_iterator
ilist_iterator< OptionsT, true, false > reverse_iterator
Definition: simple_ilist.h:97
llvm::simple_ilist::begin
const_iterator begin() const
Definition: simple_ilist.h:118
llvm::ilist_iterator
Iterator for intrusive lists based on ilist_node.
Definition: ilist_iterator.h:57
LLVM_NODISCARD
#define LLVM_NODISCARD
LLVM_NODISCARD - Warn if a type or return value is discarded.
Definition: Compiler.h:161
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1423
llvm::simple_ilist::splice
void splice(iterator I, simple_ilist &L2)
Splice in another list.
Definition: simple_ilist.h:238
llvm::ilist_detail::compute_node_options
Definition: ilist_node_options.h:121
llvm::simple_ilist::remove
void remove(reference N)
Remove a node by reference; never deletes.
Definition: simple_ilist.h:183
llvm::simple_ilist::end
iterator end()
Definition: simple_ilist.h:119
llvm::simple_ilist::back
const_reference back() const
Definition: simple_ilist.h:141
llvm::ilist_detail::check_options
Check whether options are valid.
Definition: ilist_node_options.h:95
N
#define N
llvm::simple_ilist
A simple intrusive list implementation.
Definition: simple_ilist.h:78
ilist_node.h
llvm::simple_ilist::front
reference front()
Definition: simple_ilist.h:138
llvm::simple_ilist::insert
iterator insert(iterator I, reference Node)
Insert a node by reference; never copies.
Definition: simple_ilist.h:159
llvm::simple_ilist::splice
void splice(iterator I, simple_ilist &L2, iterator Node)
Splice in a node from another list.
Definition: simple_ilist.h:243
llvm::simple_ilist::back
reference back()
Definition: simple_ilist.h:140
llvm::ilist_sentinel::reset
void reset()
Definition: ilist_node.h:243
ilist_iterator.h
ilist_node_options.h
llvm::simple_ilist::size
LLVM_NODISCARD size_type size() const
Calculate the size of the list in linear time.
Definition: simple_ilist.h:134