LLVM  16.0.0git
Sequence.h
Go to the documentation of this file.
1 //===- Sequence.h - Utility for producing sequences of values ---*- 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 /// \file
9 /// Provides some synthesis utilities to produce sequences of values. The names
10 /// are intentionally kept very short as they tend to occur in common and
11 /// widely used contexts.
12 ///
13 /// The `seq(A, B)` function produces a sequence of values from `A` to up to
14 /// (but not including) `B`, i.e., [`A`, `B`), that can be safely iterated over.
15 /// `seq` supports both integral (e.g., `int`, `char`, `uint32_t`) and enum
16 /// types. `seq_inclusive(A, B)` produces a sequence of values from `A` to `B`,
17 /// including `B`.
18 ///
19 /// Examples with integral types:
20 /// ```
21 /// for (int x : seq(0, 3))
22 /// outs() << x << " ";
23 /// ```
24 ///
25 /// Prints: `0 1 2 `.
26 ///
27 /// ```
28 /// for (int x : seq_inclusive(0, 3))
29 /// outs() << x << " ";
30 /// ```
31 ///
32 /// Prints: `0 1 2 3 `.
33 ///
34 /// Similar to `seq` and `seq_inclusive`, the `enum_seq` and
35 /// `enum_seq_inclusive` functions produce sequences of enum values that can be
36 /// iterated over.
37 /// To enable iteration with enum types, you need to either mark enums as safe
38 /// to iterate on by specializing `enum_iteration_traits`, or opt into
39 /// potentially unsafe iteration at every callsite by passing
40 /// `force_iteration_on_noniterable_enum`.
41 ///
42 /// Examples with enum types:
43 /// ```
44 /// namespace X {
45 /// enum class MyEnum : unsigned {A = 0, B, C};
46 /// } // namespace X
47 ///
48 /// template <> struct enum_iteration_traits<X::MyEnum> {
49 /// static contexpr bool is_iterable = true;
50 /// };
51 ///
52 /// class MyClass {
53 /// public:
54 /// enum Safe { D = 3, E, F };
55 /// enum MaybeUnsafe { G = 1, H = 2, I = 4 };
56 /// };
57 ///
58 /// template <> struct enum_iteration_traits<MyClass::Safe> {
59 /// static contexpr bool is_iterable = true;
60 /// };
61 /// ```
62 ///
63 /// ```
64 /// for (auto v : enum_seq(MyClass::Safe::D, MyClass::Safe::F))
65 /// outs() << int(v) << " ";
66 /// ```
67 ///
68 /// Prints: `3 4 `.
69 ///
70 /// ```
71 /// for (auto v : enum_seq(MyClass::MaybeUnsafe::H, MyClass::MaybeUnsafe::I,
72 /// force_iteration_on_noniterable_enum))
73 /// outs() << int(v) << " ";
74 /// ```
75 ///
76 /// Prints: `2 3 `.
77 ///
78 //===----------------------------------------------------------------------===//
79 
80 #ifndef LLVM_ADT_SEQUENCE_H
81 #define LLVM_ADT_SEQUENCE_H
82 
83 #include <cassert> // assert
84 #include <iterator> // std::random_access_iterator_tag
85 #include <limits> // std::numeric_limits
86 #include <type_traits> // std::is_integral, std::is_enum, std::underlying_type,
87  // std::enable_if
88 
89 #include "llvm/Support/MathExtras.h" // AddOverflow / SubOverflow
90 
91 namespace llvm {
92 
93 // Enum traits that marks enums as safe or unsafe to iterate over.
94 // By default, enum types are *not* considered safe for iteration.
95 // To allow iteration for your enum type, provide a specialization with
96 // `is_iterable` set to `true` in the `llvm` namespace.
97 // Alternatively, you can pass the `force_iteration_on_noniterable_enum` tag
98 // to `enum_seq` or `enum_seq_inclusive`.
99 template <typename EnumT> struct enum_iteration_traits {
100  static constexpr bool is_iterable = false;
101 };
102 
104  explicit force_iteration_on_noniterable_enum_t() = default;
105 };
106 
109 
110 namespace detail {
111 
112 // Returns whether a value of type U can be represented with type T.
113 template <typename T, typename U> bool canTypeFitValue(const U Value) {
114  const intmax_t BotT = intmax_t(std::numeric_limits<T>::min());
115  const intmax_t BotU = intmax_t(std::numeric_limits<U>::min());
116  const uintmax_t TopT = uintmax_t(std::numeric_limits<T>::max());
117  const uintmax_t TopU = uintmax_t(std::numeric_limits<U>::max());
118  return !((BotT > BotU && Value < static_cast<U>(BotT)) ||
119  (TopT < TopU && Value > static_cast<U>(TopT)));
120 }
121 
122 // An integer type that asserts when:
123 // - constructed from a value that doesn't fit into intmax_t,
124 // - casted to a type that cannot hold the current value,
125 // - its internal representation overflows.
126 struct CheckedInt {
127  // Integral constructor, asserts if Value cannot be represented as intmax_t.
128  template <typename Integral,
129  std::enable_if_t<std::is_integral<Integral>::value, bool> = 0>
130  static CheckedInt from(Integral FromValue) {
131  if (!canTypeFitValue<intmax_t>(FromValue))
132  assertOutOfBounds();
133  CheckedInt Result;
134  Result.Value = static_cast<intmax_t>(FromValue);
135  return Result;
136  }
137 
138  // Enum constructor, asserts if Value cannot be represented as intmax_t.
139  template <typename Enum,
140  std::enable_if_t<std::is_enum<Enum>::value, bool> = 0>
141  static CheckedInt from(Enum FromValue) {
142  using type = std::underlying_type_t<Enum>;
143  return from<type>(static_cast<type>(FromValue));
144  }
145 
146  // Equality
147  bool operator==(const CheckedInt &O) const { return Value == O.Value; }
148  bool operator!=(const CheckedInt &O) const { return Value != O.Value; }
149 
150  CheckedInt operator+(intmax_t Offset) const {
151  CheckedInt Result;
152  if (AddOverflow(Value, Offset, Result.Value))
153  assertOutOfBounds();
154  return Result;
155  }
156 
157  intmax_t operator-(CheckedInt Other) const {
158  intmax_t Result;
159  if (SubOverflow(Value, Other.Value, Result))
160  assertOutOfBounds();
161  return Result;
162  }
163 
164  // Convert to integral, asserts if Value cannot be represented as Integral.
165  template <typename Integral,
166  std::enable_if_t<std::is_integral<Integral>::value, bool> = 0>
167  Integral to() const {
168  if (!canTypeFitValue<Integral>(Value))
169  assertOutOfBounds();
170  return static_cast<Integral>(Value);
171  }
172 
173  // Convert to enum, asserts if Value cannot be represented as Enum's
174  // underlying type.
175  template <typename Enum,
176  std::enable_if_t<std::is_enum<Enum>::value, bool> = 0>
177  Enum to() const {
178  using type = std::underlying_type_t<Enum>;
179  return Enum(to<type>());
180  }
181 
182 private:
183  static void assertOutOfBounds() { assert(false && "Out of bounds"); }
184 
185  intmax_t Value;
186 };
187 
188 template <typename T, bool IsReverse> struct SafeIntIterator {
189  using iterator_category = std::random_access_iterator_tag;
190  using value_type = T;
191  using difference_type = intmax_t;
192  using pointer = T *;
193  using reference = T &;
194 
195  // Construct from T.
196  explicit SafeIntIterator(T Value) : SI(CheckedInt::from<T>(Value)) {}
197  // Construct from other direction.
199 
200  // Dereference
201  value_type operator*() const { return SI.to<T>(); }
202  // Indexing
203  value_type operator[](intmax_t Offset) const { return *(*this + Offset); }
204 
205  // Can be compared for equivalence using the equality/inequality operators.
206  bool operator==(const SafeIntIterator &O) const { return SI == O.SI; }
207  bool operator!=(const SafeIntIterator &O) const { return SI != O.SI; }
208  // Comparison
209  bool operator<(const SafeIntIterator &O) const { return (*this - O) < 0; }
210  bool operator>(const SafeIntIterator &O) const { return (*this - O) > 0; }
211  bool operator<=(const SafeIntIterator &O) const { return (*this - O) <= 0; }
212  bool operator>=(const SafeIntIterator &O) const { return (*this - O) >= 0; }
213 
214  // Pre Increment/Decrement
215  void operator++() { offset(1); }
216  void operator--() { offset(-1); }
217 
218  // Post Increment/Decrement
220  const auto Copy = *this;
221  ++*this;
222  return Copy;
223  }
225  const auto Copy = *this;
226  --*this;
227  return Copy;
228  }
229 
230  // Compound assignment operators
231  void operator+=(intmax_t Offset) { offset(Offset); }
232  void operator-=(intmax_t Offset) { offset(-Offset); }
233 
234  // Arithmetic
235  SafeIntIterator operator+(intmax_t Offset) const { return add(Offset); }
236  SafeIntIterator operator-(intmax_t Offset) const { return add(-Offset); }
237 
238  // Difference
239  intmax_t operator-(const SafeIntIterator &O) const {
240  return IsReverse ? O.SI - SI : SI - O.SI;
241  }
242 
243 private:
244  SafeIntIterator(const CheckedInt &SI) : SI(SI) {}
245 
246  static intmax_t getOffset(intmax_t Offset) {
247  return IsReverse ? -Offset : Offset;
248  }
249 
250  CheckedInt add(intmax_t Offset) const { return SI + getOffset(Offset); }
251 
252  void offset(intmax_t Offset) { SI = SI + getOffset(Offset); }
253 
254  CheckedInt SI;
255 
256  // To allow construction from the other direction.
257  template <typename, bool> friend struct SafeIntIterator;
258 };
259 
260 } // namespace detail
261 
262 template <typename T> struct iota_range {
263  using value_type = T;
264  using reference = T &;
265  using const_reference = const T &;
270  using difference_type = intmax_t;
271  using size_type = std::size_t;
272 
273  explicit iota_range(T Begin, T End, bool Inclusive)
274  : BeginValue(Begin), PastEndValue(End) {
275  assert(Begin <= End && "Begin must be less or equal to End.");
276  if (Inclusive)
277  ++PastEndValue;
278  }
279 
280  size_t size() const { return PastEndValue - BeginValue; }
281  bool empty() const { return BeginValue == PastEndValue; }
282 
283  auto begin() const { return const_iterator(BeginValue); }
284  auto end() const { return const_iterator(PastEndValue); }
285 
286  auto rbegin() const { return const_reverse_iterator(PastEndValue - 1); }
287  auto rend() const { return const_reverse_iterator(BeginValue - 1); }
288 
289 private:
290  static_assert(std::is_integral<T>::value || std::is_enum<T>::value,
291  "T must be an integral or enum type");
292  static_assert(std::is_same<T, std::remove_cv_t<T>>::value,
293  "T must not be const nor volatile");
294 
295  iterator BeginValue;
296  iterator PastEndValue;
297 };
298 
299 /// Iterate over an integral type from Begin up to - but not including - End.
300 /// Note: Begin and End values have to be within [INTMAX_MIN, INTMAX_MAX] for
301 /// forward iteration (resp. [INTMAX_MIN + 1, INTMAX_MAX] for reverse
302 /// iteration).
303 template <typename T, typename = std::enable_if_t<std::is_integral<T>::value &&
304  !std::is_enum<T>::value>>
305 auto seq(T Begin, T End) {
306  return iota_range<T>(Begin, End, false);
307 }
308 
309 /// Iterate over an integral type from Begin to End inclusive.
310 /// Note: Begin and End values have to be within [INTMAX_MIN, INTMAX_MAX - 1]
311 /// for forward iteration (resp. [INTMAX_MIN + 1, INTMAX_MAX - 1] for reverse
312 /// iteration).
313 template <typename T, typename = std::enable_if_t<std::is_integral<T>::value &&
314  !std::is_enum<T>::value>>
315 auto seq_inclusive(T Begin, T End) {
316  return iota_range<T>(Begin, End, true);
317 }
318 
319 /// Iterate over an enum type from Begin up to - but not including - End.
320 /// Note: `enum_seq` will generate each consecutive value, even if no
321 /// enumerator with that value exists.
322 /// Note: Begin and End values have to be within [INTMAX_MIN, INTMAX_MAX] for
323 /// forward iteration (resp. [INTMAX_MIN + 1, INTMAX_MAX] for reverse
324 /// iteration).
325 template <typename EnumT,
326  typename = std::enable_if_t<std::is_enum<EnumT>::value>>
327 auto enum_seq(EnumT Begin, EnumT End) {
329  "Enum type is not marked as iterable.");
330  return iota_range<EnumT>(Begin, End, false);
331 }
332 
333 /// Iterate over an enum type from Begin up to - but not including - End, even
334 /// when `EnumT` is not marked as safely iterable by `enum_iteration_traits`.
335 /// Note: `enum_seq` will generate each consecutive value, even if no
336 /// enumerator with that value exists.
337 /// Note: Begin and End values have to be within [INTMAX_MIN, INTMAX_MAX] for
338 /// forward iteration (resp. [INTMAX_MIN + 1, INTMAX_MAX] for reverse
339 /// iteration).
340 template <typename EnumT,
341  typename = std::enable_if_t<std::is_enum<EnumT>::value>>
342 auto enum_seq(EnumT Begin, EnumT End, force_iteration_on_noniterable_enum_t) {
343  return iota_range<EnumT>(Begin, End, false);
344 }
345 
346 /// Iterate over an enum type from Begin to End inclusive.
347 /// Note: `enum_seq_inclusive` will generate each consecutive value, even if no
348 /// enumerator with that value exists.
349 /// Note: Begin and End values have to be within [INTMAX_MIN, INTMAX_MAX - 1]
350 /// for forward iteration (resp. [INTMAX_MIN + 1, INTMAX_MAX - 1] for reverse
351 /// iteration).
352 template <typename EnumT,
353  typename = std::enable_if_t<std::is_enum<EnumT>::value>>
354 auto enum_seq_inclusive(EnumT Begin, EnumT End) {
356  "Enum type is not marked as iterable.");
357  return iota_range<EnumT>(Begin, End, true);
358 }
359 
360 /// Iterate over an enum type from Begin to End inclusive, even when `EnumT`
361 /// is not marked as safely iterable by `enum_iteration_traits`.
362 /// Note: `enum_seq_inclusive` will generate each consecutive value, even if no
363 /// enumerator with that value exists.
364 /// Note: Begin and End values have to be within [INTMAX_MIN, INTMAX_MAX - 1]
365 /// for forward iteration (resp. [INTMAX_MIN + 1, INTMAX_MAX - 1] for reverse
366 /// iteration).
367 template <typename EnumT,
368  typename = std::enable_if_t<std::is_enum<EnumT>::value>>
369 auto enum_seq_inclusive(EnumT Begin, EnumT End,
371  return iota_range<EnumT>(Begin, End, true);
372 }
373 
374 } // end namespace llvm
375 
376 #endif // LLVM_ADT_SEQUENCE_H
llvm::iota_range::empty
bool empty() const
Definition: Sequence.h:281
llvm::detail::SafeIntIterator::operator-=
void operator-=(intmax_t Offset)
Definition: Sequence.h:232
llvm::enum_seq_inclusive
auto enum_seq_inclusive(EnumT Begin, EnumT End)
Iterate over an enum type from Begin to End inclusive.
Definition: Sequence.h:354
llvm::iota_range::size_type
std::size_t size_type
Definition: Sequence.h:271
llvm::iota_range::const_iterator
iterator const_iterator
Definition: Sequence.h:267
llvm::detail::SafeIntIterator::operator+
SafeIntIterator operator+(intmax_t Offset) const
Definition: Sequence.h:235
MathExtras.h
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::detail::SafeIntIterator::operator==
bool operator==(const SafeIntIterator &O) const
Definition: Sequence.h:206
llvm::detail::SafeIntIterator::operator--
void operator--()
Definition: Sequence.h:216
llvm::iota_range::rbegin
auto rbegin() const
Definition: Sequence.h:286
llvm::detail::SafeIntIterator::operator>
bool operator>(const SafeIntIterator &O) const
Definition: Sequence.h:210
llvm::detail::SafeIntIterator::operator--
SafeIntIterator operator--(int)
Definition: Sequence.h:224
llvm::detail::SafeIntIterator::operator>=
bool operator>=(const SafeIntIterator &O) const
Definition: Sequence.h:212
llvm::detail::SafeIntIterator< value_type, false >::iterator_category
std::random_access_iterator_tag iterator_category
Definition: Sequence.h:189
llvm::detail::CheckedInt::from
static CheckedInt from(Enum FromValue)
Definition: Sequence.h:141
llvm::iota_range::const_reverse_iterator
reverse_iterator const_reverse_iterator
Definition: Sequence.h:269
llvm::iota_range::const_reference
const T & const_reference
Definition: Sequence.h:265
llvm::detail::CheckedInt::operator+
CheckedInt operator+(intmax_t Offset) const
Definition: Sequence.h:150
llvm::enum_iteration_traits
Definition: Sequence.h:99
llvm::detail::SafeIntIterator
Definition: Sequence.h:188
llvm::detail::SafeIntIterator::SafeIntIterator
friend struct SafeIntIterator
Definition: Sequence.h:257
llvm::detail::SafeIntIterator::SafeIntIterator
SafeIntIterator(T Value)
Definition: Sequence.h:196
llvm::seq_inclusive
auto seq_inclusive(T Begin, T End)
Iterate over an integral type from Begin to End inclusive.
Definition: Sequence.h:315
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::iota_range::iterator
detail::SafeIntIterator< value_type, false > iterator
Definition: Sequence.h:266
llvm::max
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
llvm::detail::SafeIntIterator::operator<
bool operator<(const SafeIntIterator &O) const
Definition: Sequence.h:209
llvm::detail::SafeIntIterator::operator[]
value_type operator[](intmax_t Offset) const
Definition: Sequence.h:203
llvm::force_iteration_on_noniterable_enum_t
Definition: Sequence.h:103
llvm::detail::SafeIntIterator::operator-
intmax_t operator-(const SafeIntIterator &O) const
Definition: Sequence.h:239
llvm::detail::CheckedInt
Definition: Sequence.h:126
llvm::detail::SafeIntIterator< value_type, false >::difference_type
intmax_t difference_type
Definition: Sequence.h:191
llvm::detail::SafeIntIterator::operator++
SafeIntIterator operator++(int)
Definition: Sequence.h:219
SI
@ SI
Definition: SIInstrInfo.cpp:7882
llvm::iota_range::value_type
T value_type
Definition: Sequence.h:263
llvm::seq
auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
Definition: Sequence.h:305
llvm::detail::SafeIntIterator::operator++
void operator++()
Definition: Sequence.h:215
llvm::AddOverflow
std::enable_if_t< std::is_signed< T >::value, T > AddOverflow(T X, T Y, T &Result)
Add two signed integers, computing the two's complement truncated result, returning true if overflow ...
Definition: MathExtras.h:825
llvm::detail::SafeIntIterator::operator*
value_type operator*() const
Definition: Sequence.h:201
llvm::detail::SafeIntIterator::operator!=
bool operator!=(const SafeIntIterator &O) const
Definition: Sequence.h:207
llvm::force_iteration_on_noniterable_enum_t::force_iteration_on_noniterable_enum_t
force_iteration_on_noniterable_enum_t()=default
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:264
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
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::detail::CheckedInt::operator-
intmax_t operator-(CheckedInt Other) const
Definition: Sequence.h:157
llvm::detail::CheckedInt::to
Enum to() const
Definition: Sequence.h:177
llvm::detail::CheckedInt::operator==
bool operator==(const CheckedInt &O) const
Definition: Sequence.h:147
llvm::detail::SafeIntIterator::operator-
SafeIntIterator operator-(intmax_t Offset) const
Definition: Sequence.h:236
llvm::enum_iteration_traits::is_iterable
static constexpr bool is_iterable
Definition: Sequence.h:100
llvm::iota_range::size
size_t size() const
Definition: Sequence.h:280
llvm::min
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:357
llvm::iota_range::difference_type
intmax_t difference_type
Definition: Sequence.h:270
llvm::detail::SafeIntIterator< value_type, false >::pointer
value_type * pointer
Definition: Sequence.h:192
llvm::iota_range::end
auto end() const
Definition: Sequence.h:284
llvm::iota_range::begin
auto begin() const
Definition: Sequence.h:283
llvm::enum_seq
auto enum_seq(EnumT Begin, EnumT End)
Iterate over an enum type from Begin up to - but not including - End.
Definition: Sequence.h:327
llvm::detail::SafeIntIterator::operator+=
void operator+=(intmax_t Offset)
Definition: Sequence.h:231
llvm::detail::SafeIntIterator< value_type, false >::reference
value_type & reference
Definition: Sequence.h:193
llvm::SubOverflow
std::enable_if_t< std::is_signed< T >::value, T > SubOverflow(T X, T Y, T &Result)
Subtract two signed integers, computing the two's complement truncated result, returning true if an o...
Definition: MathExtras.h:851
llvm::force_iteration_on_noniterable_enum
constexpr force_iteration_on_noniterable_enum_t force_iteration_on_noniterable_enum
Definition: Sequence.h:108
llvm::iota_range::reverse_iterator
detail::SafeIntIterator< value_type, true > reverse_iterator
Definition: Sequence.h:268
llvm::detail::SafeIntIterator< value_type, false >::value_type
value_type value_type
Definition: Sequence.h:190
llvm::detail::SafeIntIterator::SafeIntIterator
SafeIntIterator(const SafeIntIterator< T, !IsReverse > &O)
Definition: Sequence.h:198
llvm::iota_range::reference
T & reference
Definition: Sequence.h:264
llvm::iota_range::iota_range
iota_range(T Begin, T End, bool Inclusive)
Definition: Sequence.h:273
llvm::detail::SafeIntIterator::operator<=
bool operator<=(const SafeIntIterator &O) const
Definition: Sequence.h:211
llvm::iota_range
Definition: Sequence.h:262
llvm::detail::CheckedInt::to
Integral to() const
Definition: Sequence.h:167
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::detail::canTypeFitValue
bool canTypeFitValue(const U Value)
Definition: Sequence.h:113
llvm::iota_range::rend
auto rend() const
Definition: Sequence.h:287
llvm::detail::CheckedInt::from
static CheckedInt from(Integral FromValue)
Definition: Sequence.h:130
llvm::detail::CheckedInt::operator!=
bool operator!=(const CheckedInt &O) const
Definition: Sequence.h:148
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1251