LLVM  16.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); }
119  iterator end() { return iterator(Sentinel); }
124  }
128  }
129 
130  /// Check if the list is empty in constant time.
131  [[nodiscard]] bool empty() const { return Sentinel.empty(); }
132 
133  /// Calculate the size of the list in linear time.
134  [[nodiscard]] size_type size() const { return std::distance(begin(), end()); }
135 
136  reference front() { return *begin(); }
137  const_reference front() const { return *begin(); }
138  reference back() { return *rbegin(); }
139  const_reference back() const { return *rbegin(); }
140 
141  /// Insert a node at the front; never copies.
143 
144  /// Insert a node at the back; never copies.
146 
147  /// Remove the node at the front; never deletes.
148  void pop_front() { erase(begin()); }
149 
150  /// Remove the node at the back; never deletes.
151  void pop_back() { erase(--end()); }
152 
153  /// Swap with another list in place using std::swap.
154  void swap(simple_ilist &X) { std::swap(*this, X); }
155 
156  /// Insert a node by reference; never copies.
158  list_base_type::insertBefore(*I.getNodePtr(), *this->getNodePtr(&Node));
159  return iterator(&Node);
160  }
161 
162  /// Insert a range of nodes; never copies.
163  template <class Iterator>
164  void insert(iterator I, Iterator First, Iterator Last) {
165  for (; First != Last; ++First)
166  insert(I, *First);
167  }
168 
169  /// Clone another list.
170  template <class Cloner, class Disposer>
171  void cloneFrom(const simple_ilist &L2, Cloner clone, Disposer dispose) {
172  clearAndDispose(dispose);
173  for (const_reference V : L2)
174  push_back(*clone(V));
175  }
176 
177  /// Remove a node by reference; never deletes.
178  ///
179  /// \see \a erase() for removing by iterator.
180  /// \see \a removeAndDispose() if the node should be deleted.
182 
183  /// Remove a node by reference and dispose of it.
184  template <class Disposer>
185  void removeAndDispose(reference N, Disposer dispose) {
186  remove(N);
187  dispose(&N);
188  }
189 
190  /// Remove a node by iterator; never deletes.
191  ///
192  /// \see \a remove() for removing by reference.
193  /// \see \a eraseAndDispose() it the node should be deleted.
195  assert(I != end() && "Cannot remove end of list!");
196  remove(*I++);
197  return I;
198  }
199 
200  /// Remove a range of nodes; never deletes.
201  ///
202  /// \see \a eraseAndDispose() if the nodes should be deleted.
204  list_base_type::removeRange(*First.getNodePtr(), *Last.getNodePtr());
205  return Last;
206  }
207 
208  /// Remove a node by iterator and dispose of it.
209  template <class Disposer>
210  iterator eraseAndDispose(iterator I, Disposer dispose) {
211  auto Next = std::next(I);
212  erase(I);
213  dispose(&*I);
214  return Next;
215  }
216 
217  /// Remove a range of nodes and dispose of them.
218  template <class Disposer>
219  iterator eraseAndDispose(iterator First, iterator Last, Disposer dispose) {
220  while (First != Last)
221  First = eraseAndDispose(First, dispose);
222  return Last;
223  }
224 
225  /// Clear the list; never deletes.
226  ///
227  /// \see \a clearAndDispose() if the nodes should be deleted.
228  void clear() { Sentinel.reset(); }
229 
230  /// Clear the list and dispose of the nodes.
231  template <class Disposer> void clearAndDispose(Disposer dispose) {
232  eraseAndDispose(begin(), end(), dispose);
233  }
234 
235  /// Splice in another list.
237  splice(I, L2, L2.begin(), L2.end());
238  }
239 
240  /// Splice in a node from another list.
242  splice(I, L2, Node, std::next(Node));
243  }
244 
245  /// Splice in a range of nodes from another list.
246  void splice(iterator I, simple_ilist &, iterator First, iterator Last) {
247  list_base_type::transferBefore(*I.getNodePtr(), *First.getNodePtr(),
248  *Last.getNodePtr());
249  }
250 
251  /// Merge in another list.
252  ///
253  /// \pre \c this and \p RHS are sorted.
254  ///@{
255  void merge(simple_ilist &RHS) { merge(RHS, std::less<T>()); }
256  template <class Compare> void merge(simple_ilist &RHS, Compare comp);
257  ///@}
258 
259  /// Sort the list.
260  ///@{
261  void sort() { sort(std::less<T>()); }
262  template <class Compare> void sort(Compare comp);
263  ///@}
264 };
265 
266 template <class T, class... Options>
267 template <class Compare>
269  if (this == &RHS || RHS.empty())
270  return;
271  iterator LI = begin(), LE = end();
272  iterator RI = RHS.begin(), RE = RHS.end();
273  while (LI != LE) {
274  if (comp(*RI, *LI)) {
275  // Transfer a run of at least size 1 from RHS to LHS.
276  iterator RunStart = RI++;
277  RI = std::find_if(RI, RE, [&](reference RV) { return !comp(RV, *LI); });
278  splice(LI, RHS, RunStart, RI);
279  if (RI == RE)
280  return;
281  }
282  ++LI;
283  }
284  // Transfer the remaining RHS nodes once LHS is finished.
285  splice(LE, RHS, RI, RE);
286 }
287 
288 template <class T, class... Options>
289 template <class Compare>
291  // Vacuously sorted.
292  if (empty() || std::next(begin()) == end())
293  return;
294 
295  // Split the list in the middle.
296  iterator Center = begin(), End = begin();
297  while (End != end() && ++End != end()) {
298  ++Center;
299  ++End;
300  }
302  RHS.splice(RHS.end(), *this, Center, end());
303 
304  // Sort the sublists and merge back together.
305  sort(comp);
306  RHS.sort(comp);
307  merge(RHS, comp);
308 }
309 
310 } // end namespace llvm
311 
312 #endif // LLVM_ADT_SIMPLE_ILIST_H
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
ilist_base.h
llvm::PseudoProbeAttributes::Sentinel
@ Sentinel
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:148
llvm::PseudoProbeReservedId::Last
@ Last
pointer
Replace within non kernel function use of LDS with pointer
Definition: AMDGPUReplaceLDSUseWithPointer.cpp:631
llvm::simple_ilist::simple_ilist
simple_ilist()=default
llvm::ilist_detail::SpecificNodeAccess< ilist_detail::compute_node_options< MachineInstr, Options... >::type >::pointer
typename ilist_detail::compute_node_options< MachineInstr, Options... >::type ::pointer pointer
Definition: ilist_node.h:213
llvm::simple_ilist::pop_back
void pop_back()
Remove the node at the back; never deletes.
Definition: simple_ilist.h:151
llvm::simple_ilist::clear
void clear()
Clear the list; never deletes.
Definition: simple_ilist.h:228
llvm::simple_ilist::front
const_reference front() const
Definition: simple_ilist.h:137
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:235
llvm::simple_ilist::merge
void merge(simple_ilist &RHS)
Merge in another list.
Definition: simple_ilist.h:255
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:226
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:246
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:217
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
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:231
llvm::ilist_detail::SpecificNodeAccess
Definition: ilist_node.h:211
size_t
llvm::simple_ilist< MachineInstr, Options... >::value_type
typename OptionsT::value_type value_type
Definition: simple_ilist.h:90
llvm::simple_ilist< MachineInstr, Options... >::reference
typename OptionsT::reference reference
Definition: simple_ilist.h:92
llvm::ilist_detail::SpecificNodeAccess< ilist_detail::compute_node_options< MachineInstr, Options... >::type >::const_pointer
typename ilist_detail::compute_node_options< MachineInstr, Options... >::type ::const_pointer const_pointer
Definition: ilist_node.h:214
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:261
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:185
llvm::ilist_sentinel
Definition: ilist_node.h:30
llvm::simple_ilist::~simple_ilist
~simple_ilist()=default
merge
static LoopDeletionResult merge(LoopDeletionResult A, LoopDeletionResult B)
Definition: LoopDeletion.cpp:53
llvm::simple_ilist::erase
iterator erase(iterator First, iterator Last)
Remove a range of nodes; never deletes.
Definition: simple_ilist.h:203
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:210
llvm::AArch64CC::LE
@ LE
Definition: AArch64BaseInfo.h:268
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1657
llvm::simple_ilist::push_front
void push_front(reference Node)
Insert a node at the front; never copies.
Definition: simple_ilist.h:142
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:164
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:194
llvm::simple_ilist::simple_ilist
simple_ilist(simple_ilist &&X)
Definition: simple_ilist.h:110
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::simple_ilist< MachineInstr, Options... >::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:145
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
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:154
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:219
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.
llvm::simple_ilist::empty
bool empty() const
Check if the list is empty in constant time.
Definition: simple_ilist.h:131
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:156
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:1736
llvm::simple_ilist::cloneFrom
void cloneFrom(const simple_ilist &L2, Cloner clone, Disposer dispose)
Clone another list.
Definition: simple_ilist.h:171
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::simple_ilist::splice
void splice(iterator I, simple_ilist &L2)
Splice in another list.
Definition: simple_ilist.h:236
llvm::ilist_detail::compute_node_options
Definition: ilist_node_options.h:123
llvm::simple_ilist::size
size_type size() const
Calculate the size of the list in linear time.
Definition: simple_ilist.h:134
llvm::simple_ilist::remove
void remove(reference N)
Remove a node by reference; never deletes.
Definition: simple_ilist.h:181
llvm::simple_ilist::end
iterator end()
Definition: simple_ilist.h:119
llvm::simple_ilist::back
const_reference back() const
Definition: simple_ilist.h:139
llvm::ilist_detail::check_options
Check whether options are valid.
Definition: ilist_node_options.h:97
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:136
llvm::simple_ilist::insert
iterator insert(iterator I, reference Node)
Insert a node by reference; never copies.
Definition: simple_ilist.h:157
llvm::simple_ilist::splice
void splice(iterator I, simple_ilist &L2, iterator Node)
Splice in a node from another list.
Definition: simple_ilist.h:241
llvm::simple_ilist::back
reference back()
Definition: simple_ilist.h:138
ilist_iterator.h
ilist_node_options.h