LLVM  13.0.0git
ilist_iterator.h
Go to the documentation of this file.
1 //===- llvm/ADT/ilist_iterator.h - Intrusive List Iterator ------*- 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_ILIST_ITERATOR_H
10 #define LLVM_ADT_ILIST_ITERATOR_H
11 
12 #include "llvm/ADT/ilist_node.h"
13 #include <cassert>
14 #include <cstddef>
15 #include <iterator>
16 #include <type_traits>
17 
18 namespace llvm {
19 
20 namespace ilist_detail {
21 
22 /// Find const-correct node types.
23 template <class OptionsT, bool IsConst> struct IteratorTraits;
24 template <class OptionsT> struct IteratorTraits<OptionsT, false> {
25  using value_type = typename OptionsT::value_type;
26  using pointer = typename OptionsT::pointer;
27  using reference = typename OptionsT::reference;
30 };
31 template <class OptionsT> struct IteratorTraits<OptionsT, true> {
32  using value_type = const typename OptionsT::value_type;
33  using pointer = typename OptionsT::const_pointer;
34  using reference = typename OptionsT::const_reference;
37 };
38 
39 template <bool IsReverse> struct IteratorHelper;
42 
43  template <class T> static void increment(T *&I) { I = Access::getNext(*I); }
44  template <class T> static void decrement(T *&I) { I = Access::getPrev(*I); }
45 };
48 
49  template <class T> static void increment(T *&I) { I = Access::getPrev(*I); }
50  template <class T> static void decrement(T *&I) { I = Access::getNext(*I); }
51 };
52 
53 } // end namespace ilist_detail
54 
55 /// Iterator for intrusive lists based on ilist_node.
56 template <class OptionsT, bool IsReverse, bool IsConst>
61 
64 
65 public:
66  using value_type = typename Traits::value_type;
67  using pointer = typename Traits::pointer;
68  using reference = typename Traits::reference;
70  using iterator_category = std::bidirectional_iterator_tag;
71  using const_pointer = typename OptionsT::const_pointer;
72  using const_reference = typename OptionsT::const_reference;
73 
74 private:
75  using node_pointer = typename Traits::node_pointer;
76  using node_reference = typename Traits::node_reference;
77 
78  node_pointer NodePtr = nullptr;
79 
80 public:
81  /// Create from an ilist_node.
82  explicit ilist_iterator(node_reference N) : NodePtr(&N) {}
83 
84  explicit ilist_iterator(pointer NP) : NodePtr(Access::getNodePtr(NP)) {}
85  explicit ilist_iterator(reference NR) : NodePtr(Access::getNodePtr(&NR)) {}
86  ilist_iterator() = default;
87 
88  // This is templated so that we can allow constructing a const iterator from
89  // a nonconst iterator...
90  template <bool RHSIsConst>
92  std::enable_if_t<IsConst || !RHSIsConst, void *> = nullptr)
93  : NodePtr(RHS.NodePtr) {}
94 
95  // This is templated so that we can allow assigning to a const iterator from
96  // a nonconst iterator...
97  template <bool RHSIsConst>
98  std::enable_if_t<IsConst || !RHSIsConst, ilist_iterator &>
100  NodePtr = RHS.NodePtr;
101  return *this;
102  }
103 
104  /// Explicit conversion between forward/reverse iterators.
105  ///
106  /// Translate between forward and reverse iterators without changing range
107  /// boundaries. The resulting iterator will dereference (and have a handle)
108  /// to the previous node, which is somewhat unexpected; but converting the
109  /// two endpoints in a range will give the same range in reverse.
110  ///
111  /// This matches std::reverse_iterator conversions.
112  explicit ilist_iterator(
114  : ilist_iterator(++RHS.getReverse()) {}
115 
116  /// Get a reverse iterator to the same node.
117  ///
118  /// Gives a reverse iterator that will dereference (and have a handle) to the
119  /// same node. Converting the endpoint iterators in a range will give a
120  /// different range; for range operations, use the explicit conversions.
122  if (NodePtr)
125  }
126 
127  /// Const-cast.
129  if (NodePtr)
131  const_cast<typename ilist_iterator<OptionsT, IsReverse,
132  false>::node_reference>(*NodePtr));
134  }
135 
136  // Accessors...
138  assert(!NodePtr->isKnownSentinel());
139  return *Access::getValuePtr(NodePtr);
140  }
141  pointer operator->() const { return &operator*(); }
142 
143  // Comparison operators
144  friend bool operator==(const ilist_iterator &LHS, const ilist_iterator &RHS) {
145  return LHS.NodePtr == RHS.NodePtr;
146  }
147  friend bool operator!=(const ilist_iterator &LHS, const ilist_iterator &RHS) {
148  return LHS.NodePtr != RHS.NodePtr;
149  }
150 
151  // Increment and decrement operators...
153  NodePtr = IsReverse ? NodePtr->getNext() : NodePtr->getPrev();
154  return *this;
155  }
157  NodePtr = IsReverse ? NodePtr->getPrev() : NodePtr->getNext();
158  return *this;
159  }
161  ilist_iterator tmp = *this;
162  --*this;
163  return tmp;
164  }
166  ilist_iterator tmp = *this;
167  ++*this;
168  return tmp;
169  }
170 
171  /// Get the underlying ilist_node.
172  node_pointer getNodePtr() const { return static_cast<node_pointer>(NodePtr); }
173 
174  /// Check for end. Only valid if ilist_sentinel_tracking<true>.
175  bool isEnd() const { return NodePtr ? NodePtr->isSentinel() : false; }
176 };
177 
178 template <typename From> struct simplify_type;
179 
180 /// Allow ilist_iterators to convert into pointers to a node automatically when
181 /// used by the dyn_cast, cast, isa mechanisms...
182 ///
183 /// FIXME: remove this, since there is no implicit conversion to NodeTy.
184 template <class OptionsT, bool IsConst>
187  using SimpleType = typename iterator::pointer;
188 
189  static SimpleType getSimplifiedValue(const iterator &Node) { return &*Node; }
190 };
191 template <class OptionsT, bool IsConst>
193  : simplify_type<ilist_iterator<OptionsT, false, IsConst>> {};
194 
195 } // end namespace llvm
196 
197 #endif // LLVM_ADT_ILIST_ITERATOR_H
llvm::ilist_detail::IteratorHelper< true >::decrement
static void decrement(T *&I)
Definition: ilist_iterator.h:50
llvm::ilist_iterator::operator--
ilist_iterator operator--(int)
Definition: ilist_iterator.h:160
llvm::ilist_iterator::operator*
reference operator*() const
Definition: ilist_iterator.h:137
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::ilist_iterator::getNodePtr
node_pointer getNodePtr() const
Get the underlying ilist_node.
Definition: ilist_iterator.h:172
pointer
Replace within non kernel function use of LDS with pointer
Definition: AMDGPUReplaceLDSUseWithPointer.cpp:443
llvm::ilist_iterator::getNonConst
ilist_iterator< OptionsT, IsReverse, false > getNonConst() const
Const-cast.
Definition: ilist_iterator.h:128
llvm::ilist_iterator::ilist_iterator
ilist_iterator(pointer NP)
Definition: ilist_iterator.h:84
llvm::ilist_iterator::const_reference
typename OptionsT::const_reference const_reference
Definition: ilist_iterator.h:72
tmp
alloca< 16 x float >, align 16 %tmp2=alloca< 16 x float >, align 16 store< 16 x float > %A,< 16 x float > *%tmp %s=bitcast< 16 x float > *%tmp to i8 *%s2=bitcast< 16 x float > *%tmp2 to i8 *call void @llvm.memcpy.i64(i8 *%s, i8 *%s2, i64 64, i32 16) %R=load< 16 x float > *%tmp2 ret< 16 x float > %R } declare void @llvm.memcpy.i64(i8 *nocapture, i8 *nocapture, i64, i32) nounwind which compiles to:_foo:subl $140, %esp movaps %xmm3, 112(%esp) movaps %xmm2, 96(%esp) movaps %xmm1, 80(%esp) movaps %xmm0, 64(%esp) movl 60(%esp), %eax movl %eax, 124(%esp) movl 56(%esp), %eax movl %eax, 120(%esp) movl 52(%esp), %eax< many many more 32-bit copies > movaps(%esp), %xmm0 movaps 16(%esp), %xmm1 movaps 32(%esp), %xmm2 movaps 48(%esp), %xmm3 addl $140, %esp ret On Nehalem, it may even be cheaper to just use movups when unaligned than to fall back to lower-granularity chunks. Implement processor-specific optimizations for parity with GCC on these processors. GCC does two optimizations:1. ix86_pad_returns inserts a noop before ret instructions if immediately preceded by a conditional branch or is the target of a jump. 2. ix86_avoid_jump_misspredicts inserts noops in cases where a 16-byte block of code contains more than 3 branches. The first one is done for all AMDs, Core2, and "Generic" The second one is done for:Atom, Pentium Pro, all AMDs, Pentium 4, Nocona, Core 2, and "Generic" Testcase:int x(int a) { return(a &0xf0)> >4 tmp
Definition: README.txt:1347
llvm::ilist_iterator::operator=
std::enable_if_t< IsConst||!RHSIsConst, ilist_iterator & > operator=(const ilist_iterator< OptionsT, IsReverse, RHSIsConst > &RHS)
Definition: ilist_iterator.h:99
llvm::ilist_detail::SpecificNodeAccess
Definition: ilist_node.h:210
llvm::ilist_iterator::ilist_iterator
ilist_iterator(reference NR)
Definition: ilist_iterator.h:85
llvm::ilist_iterator::operator->
pointer operator->() const
Definition: ilist_iterator.h:141
llvm::ilist_detail::SpecificNodeAccess::getValuePtr
static pointer getValuePtr(node_type *N)
Definition: ilist_node.h:224
ptrdiff_t
llvm::ilist_detail::IteratorHelper
Definition: ilist_iterator.h:39
llvm::ilist_iterator::ilist_iterator
ilist_iterator(node_reference N)
Create from an ilist_node.
Definition: ilist_iterator.h:82
llvm::simplify_type
Definition: ilist_iterator.h:178
false
Definition: StackSlotColoring.cpp:142
llvm::ilist_iterator::operator==
friend bool operator==(const ilist_iterator &LHS, const ilist_iterator &RHS)
Definition: ilist_iterator.h:144
llvm::simplify_type< ilist_iterator< OptionsT, false, IsConst > >::getSimplifiedValue
static SimpleType getSimplifiedValue(const iterator &Node)
Definition: ilist_iterator.h:189
llvm::ilist_detail::IteratorTraits< OptionsT, false >::pointer
typename OptionsT::pointer pointer
Definition: ilist_iterator.h:26
llvm::ilist_iterator::ilist_iterator
ilist_iterator()=default
llvm::ilist_detail::IteratorTraits< OptionsT, false >::value_type
typename OptionsT::value_type value_type
Definition: ilist_iterator.h:25
llvm::ilist_detail::NodeAccess
An access class for ilist_node private API.
Definition: ilist_node.h:163
llvm::ilist_iterator::ilist_iterator
ilist_iterator(const ilist_iterator< OptionsT, IsReverse, RHSIsConst > &RHS, std::enable_if_t< IsConst||!RHSIsConst, void * >=nullptr)
Definition: ilist_iterator.h:91
llvm::ilist_detail::IteratorTraits
Find const-correct node types.
Definition: ilist_iterator.h:23
llvm::ilist_iterator::operator++
ilist_iterator operator++(int)
Definition: ilist_iterator.h:165
llvm::ilist_iterator::operator++
ilist_iterator & operator++()
Definition: ilist_iterator.h:156
llvm::ilist_iterator::reference
typename Traits::reference reference
Definition: ilist_iterator.h:68
llvm::ilist_detail::IteratorHelper< false >::decrement
static void decrement(T *&I)
Definition: ilist_iterator.h:44
const
aarch64 promote const
Definition: AArch64PromoteConstant.cpp:232
llvm::ilist_detail::IteratorTraits< OptionsT, true >::reference
typename OptionsT::const_reference reference
Definition: ilist_iterator.h:34
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::ilist_node_impl
Implementation for an ilist node.
Definition: ilist_node.h:39
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::ilist_iterator::operator!=
friend bool operator!=(const ilist_iterator &LHS, const ilist_iterator &RHS)
Definition: ilist_iterator.h:147
llvm::ilist_iterator::ilist_iterator
ilist_iterator(const ilist_iterator< OptionsT, !IsReverse, IsConst > &RHS)
Explicit conversion between forward/reverse iterators.
Definition: ilist_iterator.h:112
llvm::ilist_iterator::isEnd
bool isEnd() const
Check for end. Only valid if ilist_sentinel_tracking<true>.
Definition: ilist_iterator.h:175
llvm::ilist_detail::IteratorHelper< false >::increment
static void increment(T *&I)
Definition: ilist_iterator.h:43
llvm::AMDGPU::HSAMD::Kernel::Arg::Key::IsConst
constexpr char IsConst[]
Key for Kernel::Arg::Metadata::mIsConst.
Definition: AMDGPUMetadata.h:190
llvm::simplify_type< ilist_iterator< OptionsT, false, IsConst > >::SimpleType
typename iterator::pointer SimpleType
Definition: ilist_iterator.h:187
llvm::ilist_iterator::iterator_category
std::bidirectional_iterator_tag iterator_category
Definition: ilist_iterator.h:70
Node
Definition: ItaniumDemangle.h:114
llvm::ilist_detail::IteratorTraits< OptionsT, true >::value_type
const typename OptionsT::value_type value_type
Definition: ilist_iterator.h:32
llvm::ilist_iterator::operator--
ilist_iterator & operator--()
Definition: ilist_iterator.h:152
llvm::ilist_detail::IteratorHelper< true >::increment
static void increment(T *&I)
Definition: ilist_iterator.h:49
llvm::ilist_iterator
Iterator for intrusive lists based on ilist_node.
Definition: ilist_iterator.h:57
llvm::ilist_iterator::const_pointer
typename OptionsT::const_pointer const_pointer
Definition: ilist_iterator.h:71
llvm::ilist_detail::IteratorTraits< OptionsT, true >::pointer
typename OptionsT::const_pointer pointer
Definition: ilist_iterator.h:33
llvm::ilist_iterator::getReverse
ilist_iterator< OptionsT, !IsReverse, IsConst > getReverse() const
Get a reverse iterator to the same node.
Definition: ilist_iterator.h:121
N
#define N
llvm::ilist_detail::IteratorTraits< OptionsT, false >::reference
typename OptionsT::reference reference
Definition: ilist_iterator.h:27
ilist_node.h
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1815
llvm::ilist_iterator::value_type
typename Traits::value_type value_type
Definition: ilist_iterator.h:66
llvm::ilist_iterator::pointer
typename Traits::pointer pointer
Definition: ilist_iterator.h:67