[llvm] Add enum iteration to Sequence

[gchatelet]

Summary

This patch allows iterating typed enum via the ADT/Sequence utility.

It also changes the original design to better separate concerns:

• StrongInt only deals with safe intmax_t operations,
• SafeIntIterator presents the iterator and reverse iterator interface but only deals with safe StrongInt internally.
• iota_range only deals with SafeIntIterator internally.
  
  This design ensures that operations are always valid. In particular, "Out of bounds" assertions fire when:
  • the value_type is not representable as an intmax_t
  • iterator operations make internal computation underflow/overflow
  • the internal representation cannot be converted back to value_type

[gchatelet]

This is a different take on D103900 which I had to revert because of the following UB operation.

[  DEATH   ] llvm-project/llvm/include/llvm/ADT/Sequence.h:198:68: runtime error: signed integer overflow: -9223372036854775808 - 1 cannot be represented in type 'long'

I think the new design is easier to reason about as all the casts and arithmetic operations are isolated and controlled.

[gchatelet]

• Use MathExtras functions instead of builtins for compiler compat

[gchatelet]

• Add documentation and remove unnecessary declarations

[gchatelet]

• Help readability by using operators instead of functino names

[gchatelet]

• Cleanup headers

[courbet]

llvm/include/llvm/ADT/Sequence.h

39

OverflowCheckingInt ?

47–50

Is there any reason to make the dtor user-provided ? This makes the class non trivially copyable.

57

use MathExtras's AddOverflow ?

84

so uintmax_t is no longer supported ? This should be noted somewhere. I'm wondering whether this is an issue or not...

230

This is no longer relevant, right ?

Also, add a note about signedness ?

[gchatelet]

• rebase
• Change StrongInt to SafeInt
• Add Begin and End value validity

[gchatelet]

llvm/include/llvm/ADT/Sequence.h

39

OverflowCheckingInt ?

I went with SafeInt as it's shorter and conveys the idea.

84

so uintmax_t is no longer supported ? This should be noted somewhere. I'm wondering whether this is an issue or not...

It is supported but not all of its values (no values above INTMAX_MAX are permitted).

I believe this is not a problem as this class is really about iterating values. It would be surprising to iterate values between INTMAX_MAX + 1 and UINTMAX_MAX.

[gchatelet]

• Fix documentation

[gchatelet]

llvm/include/llvm/ADT/Sequence.h

39

OverflowCheckingInt ?

I went with SafeInt as it's shorter and conveys the idea.

@courbet CheckedInt maybe?

[courbet]

llvm/include/llvm/ADT/Sequence.h

39

CheckedInt sounds good

[gchatelet]

• Rename SafeInt to CheckedInt

[gchatelet]

• rebase

llvm/include/llvm/ADT/Sequence.h

 /// values. The names are intentionally kept very short as they tend to occur
 /// in common and widely used contexts.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_SEQUENCE_H
 #define LLVM_ADT_SEQUENCE_H
 
-#include <cstddef>  //std::ptrdiff_t
-#include <iterator> //std::random_access_iterator_tag
+#include <cassert>     // assert
+#include <cstddef>     // std::ptrdiff_t
+#include <iterator>    // std::random_access_iterator_tag
+#include <limits>      // std::numeric_limits
+#include <type_traits> // std::underlying_type, std::is_enum
+
+#include "llvm/Support/MathExtras.h"
 
 namespace llvm {
 
 namespace detail {
 
-template <typename T, bool IsReversed> struct iota_range_iterator {
-  using iterator_category = std::random_access_iterator_tag;
-  using value_type = T;
-  using difference_type = std::ptrdiff_t;
-  using pointer = T *;
-  using reference = T &;
-
-private:
-  struct Forward {
-    static void increment(T &V) { ++V; }
-    static void decrement(T &V) { --V; }
-    static void offset(T &V, difference_type Offset) { V += Offset; }
-    static T add(const T &V, difference_type Offset) { return V + Offset; }
-    static difference_type difference(const T &A, const T &B) { return A - B; }
-  };
-
-  struct Reverse {
-    static void increment(T &V) { --V; }
-    static void decrement(T &V) { ++V; }
-    static void offset(T &V, difference_type Offset) { V -= Offset; }
-    static T add(const T &V, difference_type Offset) { return V - Offset; }
-    static difference_type difference(const T &A, const T &B) { return B - A; }
-  };
-
-  using Op = std::conditional_t<!IsReversed, Forward, Reverse>;
+template <typename T, typename U> bool canTypeFitValue(const U value) {
+  const intmax_t botT = intmax_t(std::numeric_limits<T>::min());
+  const intmax_t botU = intmax_t(std::numeric_limits<U>::min());
+  const uintmax_t topT = uintmax_t(std::numeric_limits<T>::max());
+  const uintmax_t topU = uintmax_t(std::numeric_limits<U>::max());
+  return !((botT > botU && value < static_cast<U>(botT)) ||
+           (topT < topU && value > static_cast<U>(topT)));
+}
 
-public:
+struct StrongInt {
   // default-constructible
-  iota_range_iterator() = default;
+  StrongInt() = default;
   // copy-constructible
-  iota_range_iterator(const iota_range_iterator &) = default;
-  // value constructor
-  explicit iota_range_iterator(T Value) : Value(Value) {}
+  StrongInt(const StrongInt &) = default;
   // copy-assignable
-  iota_range_iterator &operator=(const iota_range_iterator &) = default;
+  StrongInt &operator=(const StrongInt &) = default;
   // destructible
-  ~iota_range_iterator() = default;
+  ~StrongInt() = default;
 
-  // Can be compared for equivalence using the equality/inequality operators,
-  bool operator!=(const iota_range_iterator &RHS) const {
-    return Value != RHS.Value;
-  }
-  bool operator==(const iota_range_iterator &RHS) const {
-    return Value == RHS.Value;
+  bool operator==(const StrongInt &O) const { return Value == O.Value; }
+  bool operator!=(const StrongInt &O) const { return Value != O.Value; }
+
+  StrongInt safe_add(intmax_t Offset) const {
+    StrongInt Result;
+    if (AddOverflow(Value, Offset, Result.Value))
+      assertOutOfBounds();
+    return Result;
+  }
+
+  intmax_t safe_diff(StrongInt Other) const {
+    intmax_t Result;
+    if (SubOverflow(Value, Other.Value, Result))
+      assertOutOfBounds();
+    return Result;
+  }
+
+  // Convert to integral, asserts if Value cannot be represented as Integral.
+  template <typename Integral, typename std::enable_if_t<
+                                   std::is_integral<Integral>::value, bool> = 0>
+  Integral to() const {
+    if (!canTypeFitValue<Integral>(Value))
+      assertOutOfBounds();
+    return static_cast<Integral>(Value);
+  }
+
+  // Convert to enum, asserts if Value cannot be represented as Enum's
+  // underlying type.
+  template <typename Enum,
+            typename std::enable_if_t<std::is_enum<Enum>::value, bool> = 0>
+  Enum to() const {
+    using type = typename std::underlying_type<Enum>::type;
+    return Enum(to<type>());
+  }
+
+  // Integral constructor, asserts if Value cannot be represented as intmax_t.
+  template <typename Integral, typename std::enable_if_t<
+                                   std::is_integral<Integral>::value, bool> = 0>
+  static StrongInt from(Integral FromValue) {
+    if (!canTypeFitValue<intmax_t>(FromValue))
+      assertOutOfBounds();
+    StrongInt Result;
+    Result.Value = static_cast<intmax_t>(FromValue);
+    return Result;
+  }
+
+  // Enum constructor, asserts if Value cannot be represented as intmax_t.
+  template <typename Enum,
+            typename std::enable_if_t<std::is_enum<Enum>::value, bool> = 0>
+  static StrongInt from(Enum FromValue) {
+    using type = typename std::underlying_type<Enum>::type;
+    return from<type>(static_cast<type>(FromValue));
   }
 
+private:
+  static void assertOutOfBounds() { assert(false && "Out of bounds"); }
+
+  intmax_t Value;
+};
+
+template <typename T, bool IsReverse> struct SafeIntIterator {
+  using iterator_category = std::random_access_iterator_tag;
+  using value_type = T;
+  using difference_type = intmax_t;
+  using pointer = T *;
+  using reference = T &;
+
+  // Construct from T.
+  explicit SafeIntIterator(T Value) : SI(StrongInt::from<T>(Value)) {}
+  // Construct from other direction.
+  SafeIntIterator(const SafeIntIterator<T, !IsReverse> &O) : SI(O.SI) {}
+
+  // Dereference
+  value_type operator*() const { return SI.to<T>(); }
+  // Indexing
+  value_type operator[](intmax_t Offset) const { return *(*this + Offset); }
+
+  // Can be compared for equivalence using the equality/inequality operators.
+  bool operator==(const SafeIntIterator &O) const { return SI == O.SI; }
+  bool operator!=(const SafeIntIterator &O) const { return SI != O.SI; }
   // Comparison
-  bool operator<(const iota_range_iterator &Other) const {
-    return Op::difference(Value, Other.Value) < 0;
-  }
-  bool operator<=(const iota_range_iterator &Other) const {
-    return Op::difference(Value, Other.Value) <= 0;
-  }
-  bool operator>(const iota_range_iterator &Other) const {
-    return Op::difference(Value, Other.Value) > 0;
-  }
-  bool operator>=(const iota_range_iterator &Other) const {
-    return Op::difference(Value, Other.Value) >= 0;
+  bool operator<(const SafeIntIterator &O) const { return (*this - O) < 0; }
+  bool operator>(const SafeIntIterator &O) const { return (*this - O) > 0; }
+  bool operator<=(const SafeIntIterator &O) const { return (*this - O) <= 0; }
+  bool operator>=(const SafeIntIterator &O) const { return (*this - O) >= 0; }
+
+  // Pre Increment/Decrement
+  void operator++() { offset(1); }
+  void operator--() { offset(-1); }
+
+  // Post Increment/Decrement
+  SafeIntIterator operator++(int) {
+    const auto Copy = *this;
+    ++*this;
+    return Copy;
+  }
+  SafeIntIterator operator--(int) {
+    const auto Copy = *this;
+    --*this;
+    return Copy;
   }
 
-  // Dereference
-  T operator*() const { return Value; }
-  T operator[](difference_type Offset) const { return Op::add(Value, Offset); }
+  // Compound assignment operators
+  void operator+=(intmax_t Offset) { offset(Offset); }
+  void operator-=(intmax_t Offset) { offset(-Offset); }
 
   // Arithmetic
-  iota_range_iterator operator+(difference_type Offset) const {
-    return {Op::add(Value, Offset)};
-  }
-  iota_range_iterator operator-(difference_type Offset) const {
-    return {Op::add(Value, -Offset)};
-  }
+  SafeIntIterator operator+(intmax_t Offset) const { return add(Offset); }
+  SafeIntIterator operator-(intmax_t Offset) const { return add(-Offset); }
 
-  // Iterator difference
-  difference_type operator-(const iota_range_iterator &Other) const {
-    return Op::difference(Value, Other.Value);
+  // Difference
+  intmax_t operator-(const SafeIntIterator &O) const {
+    return IsReverse ? O.SI.safe_diff(SI) : SI.safe_diff(O.SI);
   }
 
-  // Pre/Post Increment
-  iota_range_iterator &operator++() {
-    Op::increment(Value);
-    return *this;
-  }
-  iota_range_iterator operator++(int) {
-    iota_range_iterator Tmp = *this;
-    Op::increment(Value);
-    return Tmp;
-  }
+private:
+  SafeIntIterator(const StrongInt &SI) : SI(SI) {}
 
-  // Pre/Post Decrement
-  iota_range_iterator &operator--() {
-    Op::decrement(Value);
-    return *this;
-  }
-  iota_range_iterator operator--(int) {
-    iota_range_iterator Tmp = *this;
-    Op::decrement(Value);
-    return Tmp;
+  StrongInt add(intmax_t Offset) const {
+    return SI.safe_add(IsReverse ? -Offset : Offset);
   }
 
-  // Compound assignment operators
-  iota_range_iterator &operator+=(difference_type Offset) {
-    Op::offset(Value, Offset);
-    return *this;
-  }
-  iota_range_iterator &operator-=(difference_type Offset) {
-    Op::offset(Value, -Offset);
-    return *this;
-  }
+  void offset(intmax_t Offset) { SI = add(Offset); }
 
-private:
-  T Value;
+  StrongInt SI;
+
+  // To allow construction from the other direction.
+  template <typename, bool> friend struct SafeIntIterator;
 };
 
 } // namespace detail
 
-template <typename ValueT> struct iota_range {
-  static_assert(std::is_integral<ValueT>::value,
-                "ValueT must be an integral type");
-
-  using value_type = ValueT;
-  using reference = ValueT &;
-  using const_reference = const ValueT &;
-  using iterator = detail::iota_range_iterator<value_type, false>;
+template <typename T> struct iota_range {
+  using value_type = T;
+  using reference = T &;
+  using const_reference = const T &;
+  using iterator = detail::SafeIntIterator<value_type, false>;
   using const_iterator = iterator;
-  using reverse_iterator = detail::iota_range_iterator<value_type, true>;
+  using reverse_iterator = detail::SafeIntIterator<value_type, true>;
   using const_reverse_iterator = reverse_iterator;
-  using difference_type = std::ptrdiff_t;
+  using difference_type = intmax_t;
   using size_type = std::size_t;
 
-  value_type Begin;
-  value_type End;
-
-  explicit iota_range(ValueT Begin, ValueT End) : Begin(Begin), End(End) {}
+  explicit iota_range(T Begin, T End, bool Inclusive)
+      : BeginValue(Begin), PastEndValue(End) {
+    assert(Begin <= End && "Begin must be less or equal to End.");
+    if (Inclusive)
+      ++PastEndValue;
+  }
 
-  size_t size() const { return End - Begin; }
-  bool empty() const { return Begin == End; }
+  size_t size() const { return PastEndValue - BeginValue; }
+  bool empty() const { return BeginValue == PastEndValue; }
 
-  auto begin() const { return const_iterator(Begin); }
-  auto end() const { return const_iterator(End); }
+  auto begin() const { return const_iterator(BeginValue); }
+  auto end() const { return const_iterator(PastEndValue); }
 
-  auto rbegin() const { return const_reverse_iterator(End - 1); }
-  auto rend() const { return const_reverse_iterator(Begin - 1); }
+  const_reverse_iterator rbegin() const { return PastEndValue - 1; }
+  const_reverse_iterator rend() const { return BeginValue - 1; }
 
 private:
-  static_assert(std::is_same<ValueT, std::remove_cv_t<ValueT>>::value,
-                "ValueT must not be const nor volatile");
+  static_assert(std::is_integral<T>::value || std::is_enum<T>::value,
+                "T must be an integral or enum type");
+  static_assert(std::is_same<T, std::remove_cv_t<T>>::value,
+                "T must not be const nor volatile");
+
+  iterator BeginValue;
+  iterator PastEndValue;
 };
 
-template <typename ValueT> auto seq(ValueT Begin, ValueT End) {
-  return iota_range<ValueT>(Begin, End);
+/// Iterate over an integral/enum type from Begin up to - but not including -
+/// End.
+/// Note on enum iteration: `seq` will generate each consecutive value, even if
+/// no enumerator with that value exists.
+template <typename T> auto seq(T Begin, T End) {
+  return iota_range<T>(Begin, End, false);
+}
+
+/// Iterate over an integral/enum type from Begin to End inclusive.
+/// Note on enum iteration: `seq_inclusive` will generate each consecutive
+/// value, even if no enumerator with that value exists.
+/// To prevent overflow, `End` must be different from INTMAX_MAX if T is signed
+/// (resp. UINTMAX_MAX if T is unsigned).
+template <typename T> auto seq_inclusive(T Begin, T End) {
+  return iota_range<T>(Begin, End, true);
 }
 
 } // end namespace llvm
 
 #endif // LLVM_ADT_SEQUENCE_H

llvm/include/llvm/Support/MachineValueType.h

 //===- Support/MachineValueType.h - Machine-Level types ---------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file defines the set of machine-level target independent types which
 // legal values in the code generator use.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_SUPPORT_MACHINEVALUETYPE_H
 #define LLVM_SUPPORT_MACHINEVALUETYPE_H
 
+#include "llvm/ADT/Sequence.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/TypeSize.h"
 #include <cassert>
 
 namespace llvm {
 
static MVT getVectorVT(MVT VT, ElementCount EC) {
       return getVectorVT(VT, EC.getKnownMinValue());
     }
 
     /// Return the value type corresponding to the specified type.  This returns
     /// all pointers as iPTR.  If HandleUnknown is true, unknown types are
     /// returned as Other, otherwise they are invalid.
     static MVT getVT(Type *Ty, bool HandleUnknown = false);
 
-  private:
-    /// A simple iterator over the MVT::SimpleValueType enum.
-    struct mvt_iterator {
-      SimpleValueType VT;
-
-      mvt_iterator(SimpleValueType VT) : VT(VT) {}
-
-      MVT operator*() const { return VT; }
-      bool operator!=(const mvt_iterator &LHS) const { return VT != LHS.VT; }
-
-      mvt_iterator& operator++() {
-        VT = (MVT::SimpleValueType)((int)VT + 1);
-        assert((int)VT <= MVT::MAX_ALLOWED_VALUETYPE &&
-               "MVT iterator overflowed.");
-        return *this;
-      }
-    };
-
-    /// A range of the MVT::SimpleValueType enum.
-    using mvt_range = iterator_range<mvt_iterator>;
-
   public:
     /// SimpleValueType Iteration
     /// @{
-    static mvt_range all_valuetypes() {
-      return mvt_range(MVT::FIRST_VALUETYPE,
-                       (MVT::SimpleValueType)(MVT::LAST_VALUETYPE + 1));
+    static auto all_valuetypes() {
+      return seq_inclusive(MVT::FIRST_VALUETYPE, MVT::LAST_VALUETYPE);
     }
 
-    static mvt_range integer_valuetypes() {
-      return mvt_range(MVT::FIRST_INTEGER_VALUETYPE,
-                       (MVT::SimpleValueType)(MVT::LAST_INTEGER_VALUETYPE + 1));
+    static auto integer_valuetypes() {
+      return seq_inclusive(MVT::FIRST_INTEGER_VALUETYPE,
+                           MVT::LAST_INTEGER_VALUETYPE);
     }
 
-    static mvt_range fp_valuetypes() {
-      return mvt_range(MVT::FIRST_FP_VALUETYPE,
-                       (MVT::SimpleValueType)(MVT::LAST_FP_VALUETYPE + 1));
+    static auto fp_valuetypes() {
+      return seq_inclusive(MVT::FIRST_FP_VALUETYPE, MVT::LAST_FP_VALUETYPE);
     }
 
-    static mvt_range vector_valuetypes() {
-      return mvt_range(MVT::FIRST_VECTOR_VALUETYPE,
-                       (MVT::SimpleValueType)(MVT::LAST_VECTOR_VALUETYPE + 1));
+    static auto vector_valuetypes() {
+      return seq_inclusive(MVT::FIRST_VECTOR_VALUETYPE,
+                           MVT::LAST_VECTOR_VALUETYPE);
     }
 
-    static mvt_range fixedlen_vector_valuetypes() {
-      return mvt_range(
-               MVT::FIRST_FIXEDLEN_VECTOR_VALUETYPE,
-               (MVT::SimpleValueType)(MVT::LAST_FIXEDLEN_VECTOR_VALUETYPE + 1));
+    static auto fixedlen_vector_valuetypes() {
+      return seq_inclusive(MVT::FIRST_FIXEDLEN_VECTOR_VALUETYPE,
+                           MVT::LAST_FIXEDLEN_VECTOR_VALUETYPE);
     }
 
-    static mvt_range scalable_vector_valuetypes() {
-      return mvt_range(
-               MVT::FIRST_SCALABLE_VECTOR_VALUETYPE,
-               (MVT::SimpleValueType)(MVT::LAST_SCALABLE_VECTOR_VALUETYPE + 1));
+    static auto scalable_vector_valuetypes() {
+      return seq_inclusive(MVT::FIRST_SCALABLE_VECTOR_VALUETYPE,
+                           MVT::LAST_SCALABLE_VECTOR_VALUETYPE);
     }
 
-    static mvt_range integer_fixedlen_vector_valuetypes() {
-      return mvt_range(
-       MVT::FIRST_INTEGER_FIXEDLEN_VECTOR_VALUETYPE,
-       (MVT::SimpleValueType)(MVT::LAST_INTEGER_FIXEDLEN_VECTOR_VALUETYPE + 1));
+    static auto integer_fixedlen_vector_valuetypes() {
+      return seq_inclusive(MVT::FIRST_INTEGER_FIXEDLEN_VECTOR_VALUETYPE,
+                           MVT::LAST_INTEGER_FIXEDLEN_VECTOR_VALUETYPE);
     }
 
-    static mvt_range fp_fixedlen_vector_valuetypes() {
-      return mvt_range(
-          MVT::FIRST_FP_FIXEDLEN_VECTOR_VALUETYPE,
-          (MVT::SimpleValueType)(MVT::LAST_FP_FIXEDLEN_VECTOR_VALUETYPE + 1));
+    static auto fp_fixedlen_vector_valuetypes() {
+      return seq_inclusive(MVT::FIRST_FP_FIXEDLEN_VECTOR_VALUETYPE,
+                           MVT::LAST_FP_FIXEDLEN_VECTOR_VALUETYPE);
     }
 
-    static mvt_range integer_scalable_vector_valuetypes() {
-      return mvt_range(
-       MVT::FIRST_INTEGER_SCALABLE_VECTOR_VALUETYPE,
-       (MVT::SimpleValueType)(MVT::LAST_INTEGER_SCALABLE_VECTOR_VALUETYPE + 1));
+    static auto integer_scalable_vector_valuetypes() {
+      return seq_inclusive(MVT::FIRST_INTEGER_SCALABLE_VECTOR_VALUETYPE,
+                           MVT::LAST_INTEGER_SCALABLE_VECTOR_VALUETYPE);
     }
 
-    static mvt_range fp_scalable_vector_valuetypes() {
-      return mvt_range(
-            MVT::FIRST_FP_SCALABLE_VECTOR_VALUETYPE,
-            (MVT::SimpleValueType)(MVT::LAST_FP_SCALABLE_VECTOR_VALUETYPE + 1));
+    static auto fp_scalable_vector_valuetypes() {
+      return seq_inclusive(MVT::FIRST_FP_SCALABLE_VECTOR_VALUETYPE,
+                           MVT::LAST_FP_SCALABLE_VECTOR_VALUETYPE);
     }
     /// @}
   };
 
 } // end namespace llvm
 
 #endif // LLVM_SUPPORT_MACHINEVALUETYPE_H

llvm/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp

assert(VT.getVectorNumElements() <
              InOp.getValueType().getVectorNumElements() &&
          "Input wasn't widened!");
 
   // We may need to further widen the operand until it has the same total
   // vector size as the result.
   EVT InVT = InOp.getValueType();
   if (InVT.getSizeInBits() != VT.getSizeInBits()) {
     EVT InEltVT = InVT.getVectorElementType();
-    for (int i = MVT::FIRST_VECTOR_VALUETYPE, e = MVT::LAST_VECTOR_VALUETYPE; i < e; ++i) {
-      EVT FixedVT = (MVT::SimpleValueType)i;
+    for (EVT FixedVT : MVT::vector_valuetypes()) {
       EVT FixedEltVT = FixedVT.getVectorElementType();
       if (TLI.isTypeLegal(FixedVT) &&
           FixedVT.getSizeInBits() == VT.getSizeInBits() &&
           FixedEltVT == InEltVT) {
         assert(FixedVT.getVectorNumElements() >= VT.getVectorNumElements() &&
                "Not enough elements in the fixed type for the operand!");
         assert(FixedVT.getVectorNumElements() != InVT.getVectorNumElements() &&
                "We can't have the same type as we started with!");
static EVT FindMemType(SelectionDAG& DAG, const TargetLowering &TLI,
   unsigned WidenEltWidth = WidenEltVT.getSizeInBits();
   unsigned AlignInBits = Align*8;
 
   // If we have one element to load/store, return it.
   EVT RetVT = WidenEltVT;
   if (!Scalable && Width == WidenEltWidth)
     return RetVT;
 
-  // See if there is larger legal integer than the element type to load/store.
-  unsigned VT;
   // Don't bother looking for an integer type if the vector is scalable, skip
   // to vector types.
   if (!Scalable) {
-    for (VT = (unsigned)MVT::LAST_INTEGER_VALUETYPE;
-         VT >= (unsigned)MVT::FIRST_INTEGER_VALUETYPE; --VT) {
-      EVT MemVT((MVT::SimpleValueType) VT);
+    // See if there is larger legal integer than the element type to load/store.
+    for (EVT MemVT : reverse(MVT::integer_valuetypes())) {
       unsigned MemVTWidth = MemVT.getSizeInBits();
       if (MemVT.getSizeInBits() <= WidenEltWidth)
         break;
       auto Action = TLI.getTypeAction(*DAG.getContext(), MemVT);
       if ((Action == TargetLowering::TypeLegal ||
            Action == TargetLowering::TypePromoteInteger) &&
           (WidenWidth % MemVTWidth) == 0 &&
           isPowerOf2_32(WidenWidth / MemVTWidth) &&
           (MemVTWidth <= Width ||
            (Align!=0 && MemVTWidth<=AlignInBits && MemVTWidth<=Width+WidenEx))) {
         if (MemVTWidth == WidenWidth)
           return MemVT;
         RetVT = MemVT;
         break;
       }
     }
   }
 
   // See if there is a larger vector type to load/store that has the same vector
   // element type and is evenly divisible with the WidenVT.
-  for (VT = (unsigned)MVT::LAST_VECTOR_VALUETYPE;
-       VT >= (unsigned)MVT::FIRST_VECTOR_VALUETYPE; --VT) {
-    EVT MemVT = (MVT::SimpleValueType) VT;
+  for (EVT MemVT : reverse(MVT::vector_valuetypes())) {
     // Skip vector MVTs which don't match the scalable property of WidenVT.
     if (Scalable != MemVT.isScalableVector())
       continue;
     unsigned MemVTWidth = MemVT.getSizeInBits().getKnownMinSize();
     auto Action = TLI.getTypeAction(*DAG.getContext(), MemVT);
     if ((Action == TargetLowering::TypeLegal ||
          Action == TargetLowering::TypePromoteInteger) &&
         WidenEltVT == MemVT.getVectorElementType() &&

llvm/tools/llvm-exegesis/lib/X86/Target.cpp

for (auto I : llvm::zip(Instr.Variables, VariableChoices)) {
 
     switch (Instr.getPrimaryOperand(Var).getExplicitOperandInfo().OperandType) {
     default:
       // We don't wish to explicitly explore this variable.
       Choices.emplace_back(); // But add invalid MCOperand to simplify logic.
       continue;
     case X86::OperandType::OPERAND_COND_CODE: {
       Exploration = true;
-      auto CondCodes = seq((int)X86::CondCode::COND_O,
-                           1 + (int)X86::CondCode::LAST_VALID_COND);
-      Choices.reserve(std::distance(CondCodes.begin(), CondCodes.end()));
+      auto CondCodes =
+          seq_inclusive(X86::CondCode::COND_O, X86::CondCode::LAST_VALID_COND);
+      Choices.reserve(CondCodes.size());
       for (int CondCode : CondCodes)
         Choices.emplace_back(MCOperand::createImm(CondCode));
       break;
     }
     }
   }
 
   // If we don't wish to explore any variables, defer to the baseline method.

llvm/tools/llvm-reduce/deltas/ReduceAttributes.cpp

public:
   void visitCallBase(CallBase &I) {
     visitAttributeList(I.getAttributes(), CallsToRefine[&I]);
   }
 
   void visitAttributeList(const AttributeList &AL,
                           AttrPtrVecVecTy &AttributeSetsToPreserve) {
     assert(AttributeSetsToPreserve.empty() && "Should not be sharing vectors.");
     AttributeSetsToPreserve.reserve(AL.getNumAttrSets());
-    for (unsigned SetIdx : seq(AL.index_begin(), AL.index_end())) {
+    for (unsigned SetIdx = AL.index_begin(), SetEndIdx = AL.index_end();
+         SetIdx != SetEndIdx; ++SetIdx) {
       AttrPtrIdxVecVecTy AttributesToPreserve;
       AttributesToPreserve.first = SetIdx;
       visitAttributeSet(AL.getAttributes(AttributesToPreserve.first),
                         AttributesToPreserve.second);
       if (!AttributesToPreserve.second.empty())
         AttributeSetsToPreserve.emplace_back(std::move(AttributesToPreserve));
     }
   }

llvm/unittests/ADT/SequenceTest.cpp

 //===- SequenceTest.cpp - Unit tests for a sequence abstraciton -----------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/Sequence.h"
+#include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
-#include <list>
+#include <algorithm>
+#include <numeric>
+#include <vector>
 
 using namespace llvm;
 
+using testing::ElementsAre;
+
 namespace {
 
-TEST(SequenceTest, Forward) {
-  int X = 0;
-  for (int I : seq(0, 10)) {
-    EXPECT_EQ(X, I);
-    ++X;
-  }
-  EXPECT_EQ(10, X);
-}
-
-TEST(SequenceTest, Backward) {
-  int X = 9;
-  for (int I : reverse(seq(0, 10))) {
-    EXPECT_EQ(X, I);
-    --X;
-  }
-  EXPECT_EQ(-1, X);
+using detail::canTypeFitValue;
+using detail::StrongInt;
+
+using IntegralTypes = testing::Types<uint8_t,   // 0
+                                     uint16_t,  // 1
+                                     uint32_t,  // 2
+                                     uint64_t,  // 3
+                                     uintmax_t, // 4
+                                     int8_t,    // 5
+                                     int16_t,   // 6
+                                     int32_t,   // 7
+                                     int64_t,   // 8
+                                     intmax_t   // 9
+                                     >;
+
+template <class T> class StrongIntTest : public testing::Test {};
+TYPED_TEST_SUITE(StrongIntTest, IntegralTypes);
+TYPED_TEST(StrongIntTest, Operations) {
+  using T = TypeParam;
+  auto Max = std::numeric_limits<T>::max();
+  auto Min = std::numeric_limits<T>::min();
+
+  // We bail out for types that are not entirely representable within intmax_t.
+  if (!canTypeFitValue<intmax_t>(Max) || !canTypeFitValue<intmax_t>(Min))
+    return;
+
+  // All representable values convert back and forth.
+  EXPECT_EQ(StrongInt::from(Min).template to<T>(), Min);
+  EXPECT_EQ(StrongInt::from(Max).template to<T>(), Max);
+
+  // Addition -2, -1, 0, 1, 2.
+  const T Expected = Max / 2;
+  const StrongInt Actual = StrongInt::from(Expected);
+  EXPECT_EQ(Actual.safe_add(-2).template to<T>(), Expected - 2);
+  EXPECT_EQ(Actual.safe_add(-1).template to<T>(), Expected - 1);
+  EXPECT_EQ(Actual.safe_add(0).template to<T>(), Expected);
+  EXPECT_EQ(Actual.safe_add(1).template to<T>(), Expected + 1);
+  EXPECT_EQ(Actual.safe_add(2).template to<T>(), Expected + 2);
+
+  // EQ/NEQ
+  EXPECT_EQ(Actual, Actual);
+  EXPECT_NE(Actual, Actual.safe_add(1));
+
+  // Difference
+  EXPECT_EQ(Actual.safe_diff(Actual), 0);
+  EXPECT_EQ(Actual.safe_add(1).safe_diff(Actual), 1);
+  EXPECT_EQ(Actual.safe_diff(Actual.safe_add(2)), -2);
+}
+
+TEST(StrongIntTest, Enums) {
+  enum UntypedEnum { A = 3 };
+  EXPECT_EQ(StrongInt::from(A).to<UntypedEnum>(), A);
+
+  enum TypedEnum : uint32_t { B = 3 };
+  EXPECT_EQ(StrongInt::from(B).to<TypedEnum>(), B);
+
+  enum class ScopedEnum : uint16_t { C = 3 };
+  EXPECT_EQ(StrongInt::from(ScopedEnum::C).to<ScopedEnum>(), ScopedEnum::C);
+}
+
+#if defined(GTEST_HAS_DEATH_TEST) && !defined(NDEBUG)
+TEST(StrongIntDeathTest, OutOfBounds) {
+  // Values above 'INTMAX_MAX' are not representable.
+  EXPECT_DEATH(StrongInt::from<uintmax_t>(INTMAX_MAX + 1ULL), "Out of bounds");
+  EXPECT_DEATH(StrongInt::from<uintmax_t>(UINTMAX_MAX), "Out of bounds");
+  // Casting to narrower type asserts when out of bounds.
+  EXPECT_DEATH(StrongInt::from(-1).to<uint8_t>(), "Out of bounds");
+  EXPECT_DEATH(StrongInt::from(256).to<uint8_t>(), "Out of bounds");
+  // Operations leading to intmax_t overflow assert.
+  EXPECT_DEATH(StrongInt::from(INTMAX_MAX).safe_add(1), "Out of bounds");
+  EXPECT_DEATH(StrongInt::from(INTMAX_MIN).safe_add(-1), "Out of bounds");
+  EXPECT_DEATH(
+      StrongInt::from(INTMAX_MIN).safe_diff(StrongInt::from(INTMAX_MAX)),
+      "Out of bounds");
+}
+#endif
+
+TEST(SafeIntIteratorTest, Operations) {
+  detail::SafeIntIterator<int, false> Forward(0);
+  detail::SafeIntIterator<int, true> Reverse(0);
+
+  const auto SetToZero = [&]() {
+    Forward = detail::SafeIntIterator<int, false>(0);
+    Reverse = detail::SafeIntIterator<int, true>(0);
+  };
+
+  // Equality / Comparisons
+  SetToZero();
+  EXPECT_EQ(Forward, Forward);
+  EXPECT_LT(Forward - 1, Forward);
+  EXPECT_LE(Forward, Forward);
+  EXPECT_LE(Forward - 1, Forward);
+  EXPECT_GT(Forward + 1, Forward);
+  EXPECT_GE(Forward, Forward);
+  EXPECT_GE(Forward + 1, Forward);
+
+  EXPECT_EQ(Reverse, Reverse);
+  EXPECT_LT(Reverse - 1, Reverse);
+  EXPECT_LE(Reverse, Reverse);
+  EXPECT_LE(Reverse - 1, Reverse);
+  EXPECT_GT(Reverse + 1, Reverse);
+  EXPECT_GE(Reverse, Reverse);
+  EXPECT_GE(Reverse + 1, Reverse);
+
+  // Dereference
+  SetToZero();
+  EXPECT_EQ(*Forward, 0);
+  EXPECT_EQ(*Reverse, 0);
+
+  // Indexing
+  SetToZero();
+  EXPECT_EQ(Forward[2], 2);
+  EXPECT_EQ(Reverse[2], -2);
+
+  // Pre-increment
+  SetToZero();
+  ++Forward;
+  EXPECT_EQ(*Forward, 1);
+  ++Reverse;
+  EXPECT_EQ(*Reverse, -1);
+
+  // Pre-decrement
+  SetToZero();
+  --Forward;
+  EXPECT_EQ(*Forward, -1);
+  --Reverse;
+  EXPECT_EQ(*Reverse, 1);
+
+  // Post-increment
+  SetToZero();
+  EXPECT_EQ(*(Forward++), 0);
+  EXPECT_EQ(*Forward, 1);
+  EXPECT_EQ(*(Reverse++), 0);
+  EXPECT_EQ(*Reverse, -1);
+
+  // Post-decrement
+  SetToZero();
+  EXPECT_EQ(*(Forward--), 0);
+  EXPECT_EQ(*Forward, -1);
+  EXPECT_EQ(*(Reverse--), 0);
+  EXPECT_EQ(*Reverse, 1);
+
+  // Compound assignment operators
+  SetToZero();
+  Forward += 1;
+  EXPECT_EQ(*Forward, 1);
+  Reverse += 1;
+  EXPECT_EQ(*Reverse, -1);
+  SetToZero();
+  Forward -= 2;
+  EXPECT_EQ(*Forward, -2);
+  Reverse -= 2;
+  EXPECT_EQ(*Reverse, 2);
+
+  // Arithmetic
+  SetToZero();
+  EXPECT_EQ(*(Forward + 3), 3);
+  EXPECT_EQ(*(Reverse + 3), -3);
+  SetToZero();
+  EXPECT_EQ(*(Forward - 4), -4);
+  EXPECT_EQ(*(Reverse - 4), 4);
+
+  // Difference
+  SetToZero();
+  EXPECT_EQ(Forward - Forward, 0);
+  EXPECT_EQ(Reverse - Reverse, 0);
+  EXPECT_EQ((Forward + 1) - Forward, 1);
+  EXPECT_EQ(Forward - (Forward + 1), -1);
+  EXPECT_EQ((Reverse + 1) - Reverse, 1);
+  EXPECT_EQ(Reverse - (Reverse + 1), -1);
+}
+
+TEST(SequenceTest, Iteration) {
+  EXPECT_THAT(seq(-4, 5), ElementsAre(-4, -3, -2, -1, 0, 1, 2, 3, 4));
+  EXPECT_THAT(reverse(seq(-4, 5)), ElementsAre(4, 3, 2, 1, 0, -1, -2, -3, -4));
+
+  EXPECT_THAT(seq_inclusive(-4, 5),
+              ElementsAre(-4, -3, -2, -1, 0, 1, 2, 3, 4, 5));
+  EXPECT_THAT(reverse(seq_inclusive(-4, 5)),
+              ElementsAre(5, 4, 3, 2, 1, 0, -1, -2, -3, -4));
 }
 
 TEST(SequenceTest, Distance) {
   const auto Forward = seq(0, 10);
   EXPECT_EQ(std::distance(Forward.begin(), Forward.end()), 10);
   EXPECT_EQ(std::distance(Forward.rbegin(), Forward.rend()), 10);
 }
 

llvm/unittests/CodeGen/ScalableVectorMVTsTest.cpp

 #include "llvm/Support/TypeSize.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
 
 namespace {
 
 TEST(ScalableVectorMVTsTest, IntegerMVTs) {
-  for (auto VecTy : MVT::integer_scalable_vector_valuetypes()) {
+  for (MVT VecTy : MVT::integer_scalable_vector_valuetypes()) {
     ASSERT_TRUE(VecTy.isValid());
     ASSERT_TRUE(VecTy.isInteger());
     ASSERT_TRUE(VecTy.isVector());
     ASSERT_TRUE(VecTy.isScalableVector());
     ASSERT_TRUE(VecTy.getScalarType().isValid());
 
     ASSERT_FALSE(VecTy.isFloatingPoint());
   }
 }
 
 TEST(ScalableVectorMVTsTest, FloatMVTs) {
-  for (auto VecTy : MVT::fp_scalable_vector_valuetypes()) {
+  for (MVT VecTy : MVT::fp_scalable_vector_valuetypes()) {
     ASSERT_TRUE(VecTy.isValid());
     ASSERT_TRUE(VecTy.isFloatingPoint());
     ASSERT_TRUE(VecTy.isVector());
     ASSERT_TRUE(VecTy.isScalableVector());
     ASSERT_TRUE(VecTy.getScalarType().isValid());
 
     ASSERT_FALSE(VecTy.isInteger());
   }

llvm/unittests/IR/ConstantRangeTest.cpp

EnumerateTwoConstantRanges(
           ForeachNumInConstantRange(
               CR2, [&](const APInt &N2) { Exhaustive &= icmp(Pred, N1, N2); });
         });
         EXPECT_EQ(CR1.icmp(Pred, CR2), Exhaustive);
       });
 }
 
 TEST(ConstantRange, ICmp) {
-  for (auto Pred : seq<unsigned>(CmpInst::Predicate::FIRST_ICMP_PREDICATE,
-                                 1 + CmpInst::Predicate::LAST_ICMP_PREDICATE))
-    ICmpTestImpl((CmpInst::Predicate)Pred);
+  for (auto Pred : seq_inclusive(CmpInst::Predicate::FIRST_ICMP_PREDICATE,
+                                 CmpInst::Predicate::LAST_ICMP_PREDICATE))
+    ICmpTestImpl(Pred);
 }
 
 TEST(ConstantRange, MakeGuaranteedNoWrapRegion) {
   const int IntMin4Bits = 8;
   const int IntMax4Bits = 7;
   typedef OverflowingBinaryOperator OBO;
 
   for (int Const : {0, -1, -2, 1, 2, IntMin4Bits, IntMax4Bits}) {

mlir/lib/Dialect/Linalg/IR/LinalgOps.cpp

getCollapsedOutputDimFromInputShape(OpBuilder &builder, Location loc,
                                     int64_t dimIndex, Value src,
                                     ArrayRef<AffineMap> reassociationMap) {
   AffineMap map = reassociationMap[dimIndex];
   unsigned startPos =
       map.getResults().front().cast<AffineDimExpr>().getPosition();
   unsigned endPos = map.getResults().back().cast<AffineDimExpr>().getPosition();
   AffineExpr expr;
   SmallVector<Value, 2> dynamicDims;
-  for (auto dim : llvm::seq(startPos, endPos + 1)) {
+  for (auto dim : llvm::seq_inclusive(startPos, endPos)) {
     dynamicDims.push_back(builder.createOrFold<tensor::DimOp>(loc, src, dim));
     AffineExpr currExpr = builder.getAffineSymbolExpr(dim - startPos);
     expr = (expr ? expr * currExpr : currExpr);
   }
   return applyMapToValues(builder, loc,
                           AffineMap::get(0, endPos - startPos + 1, expr),
                           dynamicDims)[0];
 }

 static llvm::DenseMap<int64_t, int64_t>
 getExpandedDimToCollapsedDimMap(ArrayRef<AffineMap> reassociation) {
   llvm::DenseMap<int64_t, int64_t> expandedDimToCollapsedDim;
   for (auto map : enumerate(reassociation)) {
     unsigned startPos =
         map.value().getResults().front().cast<AffineDimExpr>().getPosition();
     unsigned endPos =
         map.value().getResults().back().cast<AffineDimExpr>().getPosition();
-    for (auto dim : llvm::seq(startPos, endPos + 1)) {
+    for (auto dim : llvm::seq_inclusive(startPos, endPos)) {
       expandedDimToCollapsedDim[dim] = map.index();
     }
   }
   return expandedDimToCollapsedDim;
 }
 
 /// For an expanding reshape op, compute the value for a dimension of the output
 /// from the shape of the input.