LLVM  14.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 /// This routine provides some synthesis utilities to produce sequences of
10 /// values. The names are intentionally kept very short as they tend to occur
11 /// in common and widely used contexts.
12 ///
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLVM_ADT_SEQUENCE_H
16 #define LLVM_ADT_SEQUENCE_H
17 
18 #include <cassert> // assert
19 #include <iterator> // std::random_access_iterator_tag
20 #include <limits> // std::numeric_limits
21 #include <type_traits> // std::underlying_type, std::is_enum
22 
23 #include "llvm/Support/MathExtras.h" // AddOverflow / SubOverflow
24 
25 namespace llvm {
26 
27 namespace detail {
28 
29 // Returns whether a value of type U can be represented with type T.
30 template <typename T, typename U> bool canTypeFitValue(const U Value) {
31  const intmax_t BotT = intmax_t(std::numeric_limits<T>::min());
32  const intmax_t BotU = intmax_t(std::numeric_limits<U>::min());
33  const uintmax_t TopT = uintmax_t(std::numeric_limits<T>::max());
34  const uintmax_t TopU = uintmax_t(std::numeric_limits<U>::max());
35  return !((BotT > BotU && Value < static_cast<U>(BotT)) ||
36  (TopT < TopU && Value > static_cast<U>(TopT)));
37 }
38 
39 // An integer type that asserts when:
40 // - constructed from a value that doesn't fit into intmax_t,
41 // - casted to a type that cannot hold the current value,
42 // - its internal representation overflows.
43 struct CheckedInt {
44  // Integral constructor, asserts if Value cannot be represented as intmax_t.
45  template <typename Integral, typename std::enable_if_t<
46  std::is_integral<Integral>::value, bool> = 0>
47  static CheckedInt from(Integral FromValue) {
48  if (!canTypeFitValue<intmax_t>(FromValue))
49  assertOutOfBounds();
50  CheckedInt Result;
51  Result.Value = static_cast<intmax_t>(FromValue);
52  return Result;
53  }
54 
55  // Enum constructor, asserts if Value cannot be represented as intmax_t.
56  template <typename Enum,
57  typename std::enable_if_t<std::is_enum<Enum>::value, bool> = 0>
58  static CheckedInt from(Enum FromValue) {
59  using type = typename std::underlying_type<Enum>::type;
60  return from<type>(static_cast<type>(FromValue));
61  }
62 
63  // Equality
64  bool operator==(const CheckedInt &O) const { return Value == O.Value; }
65  bool operator!=(const CheckedInt &O) const { return Value != O.Value; }
66 
67  CheckedInt operator+(intmax_t Offset) const {
68  CheckedInt Result;
69  if (AddOverflow(Value, Offset, Result.Value))
70  assertOutOfBounds();
71  return Result;
72  }
73 
74  intmax_t operator-(CheckedInt Other) const {
75  intmax_t Result;
76  if (SubOverflow(Value, Other.Value, Result))
77  assertOutOfBounds();
78  return Result;
79  }
80 
81  // Convert to integral, asserts if Value cannot be represented as Integral.
82  template <typename Integral, typename std::enable_if_t<
83  std::is_integral<Integral>::value, bool> = 0>
84  Integral to() const {
85  if (!canTypeFitValue<Integral>(Value))
86  assertOutOfBounds();
87  return static_cast<Integral>(Value);
88  }
89 
90  // Convert to enum, asserts if Value cannot be represented as Enum's
91  // underlying type.
92  template <typename Enum,
93  typename std::enable_if_t<std::is_enum<Enum>::value, bool> = 0>
94  Enum to() const {
95  using type = typename std::underlying_type<Enum>::type;
96  return Enum(to<type>());
97  }
98 
99 private:
100  static void assertOutOfBounds() { assert(false && "Out of bounds"); }
101 
102  intmax_t Value;
103 };
104 
105 template <typename T, bool IsReverse> struct SafeIntIterator {
106  using iterator_category = std::random_access_iterator_tag;
107  using value_type = T;
108  using difference_type = intmax_t;
109  using pointer = T *;
110  using reference = T &;
111 
112  // Construct from T.
113  explicit SafeIntIterator(T Value) : SI(CheckedInt::from<T>(Value)) {}
114  // Construct from other direction.
116 
117  // Dereference
118  value_type operator*() const { return SI.to<T>(); }
119  // Indexing
120  value_type operator[](intmax_t Offset) const { return *(*this + Offset); }
121 
122  // Can be compared for equivalence using the equality/inequality operators.
123  bool operator==(const SafeIntIterator &O) const { return SI == O.SI; }
124  bool operator!=(const SafeIntIterator &O) const { return SI != O.SI; }
125  // Comparison
126  bool operator<(const SafeIntIterator &O) const { return (*this - O) < 0; }
127  bool operator>(const SafeIntIterator &O) const { return (*this - O) > 0; }
128  bool operator<=(const SafeIntIterator &O) const { return (*this - O) <= 0; }
129  bool operator>=(const SafeIntIterator &O) const { return (*this - O) >= 0; }
130 
131  // Pre Increment/Decrement
132  void operator++() { offset(1); }
133  void operator--() { offset(-1); }
134 
135  // Post Increment/Decrement
137  const auto Copy = *this;
138  ++*this;
139  return Copy;
140  }
142  const auto Copy = *this;
143  --*this;
144  return Copy;
145  }
146 
147  // Compound assignment operators
148  void operator+=(intmax_t Offset) { offset(Offset); }
149  void operator-=(intmax_t Offset) { offset(-Offset); }
150 
151  // Arithmetic
152  SafeIntIterator operator+(intmax_t Offset) const { return add(Offset); }
153  SafeIntIterator operator-(intmax_t Offset) const { return add(-Offset); }
154 
155  // Difference
156  intmax_t operator-(const SafeIntIterator &O) const {
157  return IsReverse ? O.SI - SI : SI - O.SI;
158  }
159 
160 private:
161  SafeIntIterator(const CheckedInt &SI) : SI(SI) {}
162 
163  static intmax_t getOffset(intmax_t Offset) {
164  return IsReverse ? -Offset : Offset;
165  }
166 
167  CheckedInt add(intmax_t Offset) const { return SI + getOffset(Offset); }
168 
169  void offset(intmax_t Offset) { SI = SI + getOffset(Offset); }
170 
171  CheckedInt SI;
172 
173  // To allow construction from the other direction.
174  template <typename, bool> friend struct SafeIntIterator;
175 };
176 
177 } // namespace detail
178 
179 template <typename T> struct iota_range {
180  using value_type = T;
181  using reference = T &;
182  using const_reference = const T &;
187  using difference_type = intmax_t;
188  using size_type = std::size_t;
189 
190  explicit iota_range(T Begin, T End, bool Inclusive)
191  : BeginValue(Begin), PastEndValue(End) {
192  assert(Begin <= End && "Begin must be less or equal to End.");
193  if (Inclusive)
194  ++PastEndValue;
195  }
196 
197  size_t size() const { return PastEndValue - BeginValue; }
198  bool empty() const { return BeginValue == PastEndValue; }
199 
200  auto begin() const { return const_iterator(BeginValue); }
201  auto end() const { return const_iterator(PastEndValue); }
202 
203  auto rbegin() const { return const_reverse_iterator(PastEndValue - 1); }
204  auto rend() const { return const_reverse_iterator(BeginValue - 1); }
205 
206 private:
207  static_assert(std::is_integral<T>::value || std::is_enum<T>::value,
208  "T must be an integral or enum type");
209  static_assert(std::is_same<T, std::remove_cv_t<T>>::value,
210  "T must not be const nor volatile");
211 
212  iterator BeginValue;
213  iterator PastEndValue;
214 };
215 
216 /// Iterate over an integral/enum type from Begin up to - but not including -
217 /// End.
218 /// Note on enum iteration: `seq` will generate each consecutive value, even if
219 /// no enumerator with that value exists.
220 /// Note: Begin and End values have to be within [INTMAX_MIN, INTMAX_MAX] for
221 /// forward iteration (resp. [INTMAX_MIN + 1, INTMAX_MAX] for reverse
222 /// iteration).
223 template <typename T> auto seq(T Begin, T End) {
224  return iota_range<T>(Begin, End, false);
225 }
226 
227 /// Iterate over an integral/enum type from Begin to End inclusive.
228 /// Note on enum iteration: `seq_inclusive` will generate each consecutive
229 /// value, even if no enumerator with that value exists.
230 /// Note: Begin and End values have to be within [INTMAX_MIN, INTMAX_MAX - 1]
231 /// for forward iteration (resp. [INTMAX_MIN + 1, INTMAX_MAX - 1] for reverse
232 /// iteration).
233 template <typename T> auto seq_inclusive(T Begin, T End) {
234  return iota_range<T>(Begin, End, true);
235 }
236 
237 } // end namespace llvm
238 
239 #endif // LLVM_ADT_SEQUENCE_H
llvm::iota_range::empty
bool empty() const
Definition: Sequence.h:198
llvm::detail::SafeIntIterator::operator-=
void operator-=(intmax_t Offset)
Definition: Sequence.h:149
llvm::iota_range::size_type
std::size_t size_type
Definition: Sequence.h:188
llvm::iota_range::const_iterator
iterator const_iterator
Definition: Sequence.h:184
llvm::detail::SafeIntIterator::operator+
SafeIntIterator operator+(intmax_t Offset) const
Definition: Sequence.h:152
MathExtras.h
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::detail::SafeIntIterator::operator==
bool operator==(const SafeIntIterator &O) const
Definition: Sequence.h:123
llvm::detail::SafeIntIterator::operator--
void operator--()
Definition: Sequence.h:133
llvm::iota_range::rbegin
auto rbegin() const
Definition: Sequence.h:203
llvm::detail::SafeIntIterator::operator>
bool operator>(const SafeIntIterator &O) const
Definition: Sequence.h:127
llvm::detail::SafeIntIterator::operator--
SafeIntIterator operator--(int)
Definition: Sequence.h:141
llvm::detail::SafeIntIterator::operator>=
bool operator>=(const SafeIntIterator &O) const
Definition: Sequence.h:129
llvm::detail::SafeIntIterator< value_type, false >::iterator_category
std::random_access_iterator_tag iterator_category
Definition: Sequence.h:106
llvm::detail::CheckedInt::from
static CheckedInt from(Enum FromValue)
Definition: Sequence.h:58
llvm::iota_range::const_reverse_iterator
reverse_iterator const_reverse_iterator
Definition: Sequence.h:186
llvm::iota_range::const_reference
const T & const_reference
Definition: Sequence.h:182
llvm::detail::CheckedInt::operator+
CheckedInt operator+(intmax_t Offset) const
Definition: Sequence.h:67
llvm::detail::SafeIntIterator
Definition: Sequence.h:105
llvm::detail::SafeIntIterator::SafeIntIterator
friend struct SafeIntIterator
Definition: Sequence.h:174
llvm::detail::SafeIntIterator::SafeIntIterator
SafeIntIterator(T Value)
Definition: Sequence.h:113
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::iota_range::iterator
detail::SafeIntIterator< value_type, false > iterator
Definition: Sequence.h:183
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:81
llvm::detail::SafeIntIterator::operator<
bool operator<(const SafeIntIterator &O) const
Definition: Sequence.h:126
llvm::detail::SafeIntIterator::operator[]
value_type operator[](intmax_t Offset) const
Definition: Sequence.h:120
llvm::detail::SafeIntIterator::operator-
intmax_t operator-(const SafeIntIterator &O) const
Definition: Sequence.h:156
llvm::detail::CheckedInt
Definition: Sequence.h:43
llvm::detail::SafeIntIterator< value_type, false >::difference_type
intmax_t difference_type
Definition: Sequence.h:108
llvm::detail::SafeIntIterator::operator++
SafeIntIterator operator++(int)
Definition: Sequence.h:136
llvm::iota_range::value_type
T value_type
Definition: Sequence.h:180
llvm::detail::SafeIntIterator::operator++
void operator++()
Definition: Sequence.h:132
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:884
llvm::detail::SafeIntIterator::operator*
value_type operator*() const
Definition: Sequence.h:118
llvm::seq_inclusive
auto seq_inclusive(T Begin, T End)
Iterate over an integral/enum type from Begin to End inclusive.
Definition: Sequence.h:233
llvm::detail::SafeIntIterator::operator!=
bool operator!=(const SafeIntIterator &O) const
Definition: Sequence.h:124
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:197
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:74
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::detail::CheckedInt::to
Enum to() const
Definition: Sequence.h:94
llvm::detail::CheckedInt::operator==
bool operator==(const CheckedInt &O) const
Definition: Sequence.h:64
llvm::detail::SafeIntIterator::operator-
SafeIntIterator operator-(intmax_t Offset) const
Definition: Sequence.h:153
llvm::iota_range::size
size_t size() const
Definition: Sequence.h:197
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:187
llvm::detail::SafeIntIterator< value_type, false >::pointer
value_type * pointer
Definition: Sequence.h:109
llvm::iota_range::end
auto end() const
Definition: Sequence.h:201
llvm::iota_range::begin
auto begin() const
Definition: Sequence.h:200
llvm::detail::SafeIntIterator::operator+=
void operator+=(intmax_t Offset)
Definition: Sequence.h:148
llvm::detail::SafeIntIterator< value_type, false >::reference
value_type & reference
Definition: Sequence.h:110
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:910
llvm::iota_range::reverse_iterator
detail::SafeIntIterator< value_type, true > reverse_iterator
Definition: Sequence.h:185
llvm::detail::SafeIntIterator< value_type, false >::value_type
value_type value_type
Definition: Sequence.h:107
llvm::detail::SafeIntIterator::SafeIntIterator
SafeIntIterator(const SafeIntIterator< T, !IsReverse > &O)
Definition: Sequence.h:115
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
llvm::seq
auto seq(T Begin, T End)
Iterate over an integral/enum type from Begin up to - but not including - End.
Definition: Sequence.h:223
llvm::iota_range::reference
T & reference
Definition: Sequence.h:181
llvm::iota_range::iota_range
iota_range(T Begin, T End, bool Inclusive)
Definition: Sequence.h:190
llvm::detail::SafeIntIterator::operator<=
bool operator<=(const SafeIntIterator &O) const
Definition: Sequence.h:128
llvm::iota_range
Definition: Sequence.h:179
llvm::detail::CheckedInt::to
Integral to() const
Definition: Sequence.h:84
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::detail::canTypeFitValue
bool canTypeFitValue(const U Value)
Definition: Sequence.h:30
llvm::iota_range::rend
auto rend() const
Definition: Sequence.h:204
llvm::detail::CheckedInt::from
static CheckedInt from(Integral FromValue)
Definition: Sequence.h:47
llvm::detail::CheckedInt::operator!=
bool operator!=(const CheckedInt &O) const
Definition: Sequence.h:65
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1172